Estimativa do número de valores distintos

O Snowflake usa HyperLogLog para estimar o número aproximado de valores distintos em um conjunto de dados. O HyperLogLog é um algoritmo de estimativa de cardinalidade de última geração, capaz de estimar cardinalidades distintas de trilhões de linhas com um erro relativo médio de baixa porcentagem.

O HyperLogLog pode ser usado no lugar de COUNT(DISTINCT …) em situações em que a estimativa de cardinalidade é aceitável.

Neste tópico:

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.

Formato denso

version

Número da versão da implementação HyperLogLog.

precision

Número de bits de valor com hash a serem usados para selecionar subfluxos. Atualmente fixado em 12.

dense

Um conjunto de inteiros, cada um contendo a contagem máxima de zeros à esquerda +1 para o subfluxo correspondente. 0 indica que o subfluxo correspondente ainda não foi atingido. Os valores permitidos estão na faixa de 0 a 53. O índice do subfluxo correspondente é dado pela posição do elemento na matriz.

Por exemplo:

{
  "version" : 3,
  "precision" : 12,
  "dense" : [3,3,3,3,5,3,4,3,5,6,2,4,4,7,5,6,6,3,2,2,3,2,4,5,5,5,2,5,5,3,6,1,4,2,2,4,4,5,2,5,...,4,6,3]
}
Copy

Formato esparso

version

Número da versão da implementação HyperLogLog.

precision

Número de bits de valor com hash a serem usados para selecionar subfluxos. Atualmente fixado em 12.

sparse

indices: Um conjunto de números inteiros, cada um contendo um índice de subfluxo (base 0). Os valores permitidos estão na faixa de 0 a 4095.

maxLzCounts: Um conjunto de inteiros, cada um contendo a contagem máxima de zeros à esquerda +1 para o subfluxo correspondente. 0 indica que o subfluxo correspondente ainda não foi atingido.

Os valores permitidos estão na faixa de 0 a 53. O subfluxo para uma determinada contagem de zeros à esquerda é dado pelo elemento correspondente na matriz indices.

As matrizes indices e maxLzCounts devem ter o mesmo comprimento. A função HLL_IMPORT também verifica se os índices de subfluxo estão na faixa válida e se não há índices de subfluxo duplicados. A matriz indices não precisa ser classificada. As contagens de zeros à esquerda não são validadas. Valores inválidos não causarão falhas nas consultas, mas levarão a resultados indefinidos para HLL_ESTIMATE.

Por exemplo:

{
  "version" : 3,
  "precision" : 12,
  "sparse" : {
    "indices": [1131,1241,1256,1864,2579,2699,3730],
    "maxLzCounts":[2,4,2,1,3,2,1]
  }
}
Copy

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.