Estimativa do número de valores distintos¶

Visão geral¶

O Snowflake fornece uma implementação com correção de viés do algoritmo HyperLogLog apresentado em HyperLogLog: a análise de um algoritmo de estimativa de cardinalidade quase ideal por Flajolet et al.

Recomendamos usar o HyperLogLog sempre que a entrada for potencialmente grande e um resultado aproximado for aceitável. O erro relativo médio de nossa implementação HyperLogLog é 1,62338% (ou seja, a diferença relativa média do resultado correspondente COUNT(DISTINCT …) …).

Funções SQL¶

As seguintes Funções de agregação são fornecidas para estimar a cardinalidade usando HyperLogLog:

• HLL: Retorna uma aproximação da cardinalidade distinta da entrada.

• HLL_ACCUMULATE: Pula a etapa de estimativa final e retorna o estado HyperLogLog no final de uma agregação.

• HLL_COMBINE: Combina (ou seja, funde) os estados de entrada em um único estado de saída.

• HLL_ESTIMATE: Calcula uma estimativa de cardinalidade de um estado HyperLogLog produzido por HLL_ACCUMULATE e HLL_COMBINE.

• HLL_EXPORT: Converte os estados HyperLogLog do formato BINARY para um OBJECT (que pode então ser impresso e exportado como JSON).

• HLL_IMPORT: Converte os estados HyperLogLog do formato OBJECT para o formato BINARY.

Detalhes de implementação¶

Nossa implementação aplica hash em linhas de entrada para valores de 64 bits, dos quais os 12 bits superiores ou “precisão” (como referido no artigo do algoritmo HyperLogLog; consulte o link acima para detalhes) são usados para particionar valores de entrada nos chamados subfluxos. Isto produz um erro relativo médio de:

sqrt(3*ln(2)-1)/sqrt(2^precision) = 0.0162338 = 1.62338%

Em outras palavras, para uma consulta onde COUNT(DISTINCT …) retornaria um resultado de 1,000,000, o HyperLogLog normalmente retorna um resultado na faixa de 983,767 a 1,016,234.

Para cada subfluxo, o HyperLogLog mantém a contagem máxima de zeros à esquerda (entre 0 e 52 para valores de 64 bits com precisão = 12). A representação mais direta deste estado é uma simples matriz de bytes, um byte para cada um dos subfluxos 2^12 = 4096. Nossa implementação requer, de fato, no máximo 4096 bytes (2^precision = 2^12 = 4096) de memória por grupo de agregação. Tecnicamente, apenas 6 bits (em vez de 8 bits) são necessários por subfluxo, mas trocamos alguma eficiência espacial por eficiência computacional.

Para pequenas cardinalidades de entrada, a maioria dos subfluxos nunca será atingida. Assim, em vez de alocar um bloco inteiro de 4096 bytes por grupo de agregação logo no início, nossa implementação utiliza uma representação “esparsa” desse estado, otimizada em termos de espaço, sempre que isso for benéfico. Consequentemente, o custo de memória do HyperLogLog pode ser substancialmente inferior a 4096 bytes por grupo de agregação (até cerca de 32 bytes por grupo de agregação). Isto permite estimar a cardinalidade em muitos grupos de agregação (milhões ou mesmo bilhões, conforme determinado pela cláusula GROUP BY ou OVER da consulta), usando ordens de magnitude menos memória e tempo de CPU do que uma consulta COUNT(DISTINCT …) correspondente.

No caso (raro) em que uma tabela de entrada extremamente grande e muitos grupos de agregação fazem com que o HyperLogLog exceda seu orçamento total de memória, o Snowflake ainda é capaz de usar o espaço temporário e realizar agregação recursiva, como em qualquer outra função de agregação.

Formato do estado exportado¶

O estado do algoritmo HyperLogLog pode ser exportado e importado (ou reimportado) usando as funções HLL_EXPORT e HLL_IMPORT, respectivamente. O estado exportado é do tipo OBJECT e contém os seguintes campos.

Exemplos¶

Configuração do ambiente:

USE WAREHOUSE dontdrop;
USE DATABASE stressdb;
USE SCHEMA bdb_5nodes;

SELECT COUNT(*) FROM uservisits;

-----------+
 COUNT(*)  |
-----------+
 751754869 |
-----------+

Copy

Etapa 1:

Criar uma tabela que contenha a data do calendário (ano/mês/dia) e a estrutura HLL. Usamos HLL_EXPORT para armazenar a estrutura binária como um objeto de texto:

CREATE OR REPLACE TABLE daily_uniques
AS
SELECT
 visitdate,
 hll_export(hll_accumulate(sourceip)) AS hll_sourceip
FROM uservisits
GROUP BY visitdate;

Copy

Etapa 2:

Podemos calcular IPs únicos por mês, agregando a estrutura HLL de cada dia da Etapa 1. Usamos HLL_IMPORT para transformar o texto na estrutura binária, depois HLL_COMBINE para combinar múltiplas estruturas HLL em uma única estrutura, depois HLL_ESTIMATE para computar o número de valores distintos:

SELECT
  EXTRACT(year FROM visitdate) AS visit_year,
  EXTRACT(month FROM visitdate) AS visit_month,
  hll_estimate(hll_combine(hll_import(hll_sourceip))) AS distinct_ips
FROM daily_uniques
WHERE visitdate BETWEEN '2000-01-01' AND '2000-12-31'
GROUP BY 1,2
ORDER BY 1,2;

------------+-------------+--------------+
 VISIT_YEAR | VISIT_MONTH | DISTINCT_IPS |
------------+-------------+--------------+
       2000 |           1 |      1515168 |
       2000 |           2 |      1410289 |
       2000 |           3 |      1491997 |
       2000 |           4 |      1460837 |
       2000 |           5 |      1546647 |
       2000 |           6 |      1485599 |
       2000 |           7 |      1522643 |
       2000 |           8 |      1492831 |
       2000 |           9 |      1488507 |
       2000 |          10 |      1553201 |
       2000 |          11 |      1461140 |
       2000 |          12 |      1515772 |
------------+-------------+--------------+

Elapsed 1.3s

Copy

Compare:

Comparamos o uso da agregação usando as funções HLL para HLL nos dados em nível de detalhe. Neste caso, o HLL() é equivalente ao HLL_ESTIMATE(HLL_COMBINE(HLL_IMPORT())) da Etapa 2:

SELECT
  EXTRACT(year FROM visitdate) AS visit_year,
  EXTRACT(month FROM visitdate) AS visit_month,
  hll(sourceip) AS distinct_ips
FROM uservisits
WHERE visitdate BETWEEN '2000-01-01' AND '2000-12-31'
GROUP BY 1,2
ORDER BY 1,2;

------------+-------------+--------------+
 VISIT_YEAR | VISIT_MONTH | DISTINCT_IPS |
------------+-------------+--------------+
       2000 |           1 |      1515168 |
       2000 |           2 |      1410289 |
       2000 |           3 |      1491997 |
       2000 |           4 |      1460837 |
       2000 |           5 |      1546647 |
       2000 |           6 |      1485599 |
       2000 |           7 |      1522643 |
       2000 |           8 |      1492831 |
       2000 |           9 |      1488507 |
       2000 |          10 |      1553201 |
       2000 |          11 |      1461140 |
       2000 |          12 |      1515772 |
------------+-------------+--------------+

Elapsed 2m 29s

Copy

Como você pode ver, a agregação das estruturas HLL é significativamente mais rápida que a agregação sobre os dados de base, por exemplo, 1,3 segundos vs 149 segundos neste pequeno exemplo, o que representa uma diminuição de 100x no tempo de consulta.