Estimation du nombre de valeurs distinctes

Snowflake utilise HyperLogLog pour estimer le nombre approximatif de valeurs distinctes dans un ensemble de données. HyperLogLog est un algorithme d’estimation de cardinalité de pointe, capable d’estimer des cardinalités distinctes de billions de liges avec une erreur relative moyenne de quelques %.

HyperLogLog peut être utilisé à la place de COUNT(DISTINCT …) dans les situations où l’estimation de la cardinalité est acceptable.

Dans ce chapitre :

Vue d’ensemble

Snowflake fournit une implémentation corrigée du biais de l’algorithme HyperLogLog présenté dans HyperLogLog : l’analyse d’un algorithme d’estimation de cardinalité presque optimal par Flajolet et al.

Nous recommandons d’utiliser HyperLogLog chaque fois que l’entrée est potentiellement importante et qu’un résultat approximatif est acceptable. L’erreur relative moyenne de notre implémentation HyperLogLog est de 1,62338% (c’est-à-dire la différence relative moyenne par rapport au résultat COUNT(DISTINCT …) correspondant).

Fonctions SQL

Les Fonctions d’agrégation suivants sont fournis pour estimer la cardinalité en utilisant HyperLogLog :

  • HLL: Renvoie une approximation de la cardinalité distincte de l’entrée.

  • HLL_ACCUMULATE: Ignore l’étape d’estimation finale et retourne l’état HyperLogLog à la fin d’une agrégation.

  • HLL_COMBINE: Combine (c’est-à-dire fusionne) les états d’entrée en un seul état de sortie.

  • HLL_ESTIMATE: Calcule une estimation de cardinalité d’un état HyperLogLog produit par HLL_ACCUMULATE et HLL_COMBINE.

  • HLL_EXPORT: Convertit des états HyperLogLog depuis le format BINARY en OBJECT (qui peuvent ensuite être imprimés et exportés en JSON).

  • HLL_IMPORT: Convertit des états HyperLogLog depuis le format OBJECT au format BINARY.

Détails de l’implémentation

Notre implémentation hache des lignes d’entrée en valeurs 64 bits, dont les 12 bits supérieurs ou « de précision » sont utilisés pour partitionner les valeurs d’entrée en « sous-flux » (comme indiqué dans le document sur l’algorithme HyperLogLog ; voir le lien du document ci-dessus pour plus de détails). Cela donne une erreur relative moyenne de :

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

En d’autres termes, pour une requête où COUNT(DISTINCT …) renverrait un résultat de 1,000,000, HyperLogLog renvoie généralement un résultat compris dans la plage de 983,767 à 1,016,234

Pour chaque sous-flux, HyperLogLog maintient le nombre maximal de zéros d’en-tête (entre 0 et 52 pour les valeurs de 64 bits à précision = 12). La représentation la plus simple de cet état est un simple tableau d’octets, un octet pour chacun des sous-flux 2^12 = 4096. Notre implémentation nécessite en effet au maximum 4096 octets (2^precision = 2^12 = 4096) de mémoire par groupe d’agrégation. Techniquement, seulement 6 bits (au lieu de 8 bits) sont requis par sous-flux, mais nous préférons faire une économie d’espace pour de meilleures performances de calcul.

Pour les petites cardinalités d’entrée, la plupart des sous-flux ne seront jamais touchés. Ainsi, plutôt que d’allouer un bloc entier de 4096 octets par groupe d’agrégations dès le départ, notre implémentation utilise une représentation « éparse » optimisée en espace de cet état à chaque que cela peut être utile. Par conséquent, le coût de la mémoire de HyperLogLog peut être nettement inférieur à 4096 octets par groupe d’agrégations (jusqu’à environ 32 octets par groupe d’agrégations). Ceci permet d’estimer la cardinalité sur de nombreux groupes d’agrégations (en millions, voire en milliards, comme déterminé par la clause GROUP BY ou OVER de la requête) utilisant moins de mémoire et de temps CPU qu’une requête COUNT(DISTINCT …) correspondante.

Dans le (rare) cas où une table d’entrée extrêmement grande et que de nombreux groupes d’agrégations font que HyperLogLog dépasse son budget mémoire total, Snowflake est toujours capable de se déverser dans l’espace temporaire et d’effectuer une agrégation récursive, comme avec toute autre fonction d’agrégation.

Format d’état exporté

L’état de l’algorithme HyperLogLog peut être exporté et importé (ou réimporté) en utilisant respectivement les fonctions HLL_EXPORT et HLL_IMPORT. L’état exporté est de type OBJECT et contient les champs suivants.

Format dense

version

Numéro de version de l’implémentation HyperLogLog.

precision

Nombre d’octets de valeur de hachage à utiliser pour sélectionner les sous-flux. Actuellement fixé à 12.

dense

Un tableau d’entiers, chacun contenant le nombre maximum de zéros d’en-tête + 1 pour le sous-flux correspondant. 0 indique que le sous-flux correspondant n’a pas encore été atteint. Les valeurs légales sont comprises entre 0 et 53. L’indice de sous-flux correspondant est donné par la position de l’élément dans le tableau.

Par exemple :

{
  "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]
}

Format épars

version

Numéro de version de l’implémentation HyperLogLog.

precision

Nombre d’octets de valeur de hachage à utiliser pour sélectionner les sous-flux. Actuellement fixé à 12.

sparse

indices: Un tableau d’entiers, chacun contenant un indice de sous-flux (base 0). Les valeurs légales sont comprises entre 0 et 4095.

maxLzCounts: Un tableau d’entiers, chacun contenant le nombre maximum de zéros d’en-tête + 1 pour le sous-flux correspondant. 0 indique que le sous-flux correspondant n’a pas encore été atteint.

Les valeurs légales sont comprises entre 0 et 53. Le sous-flux pour un nombre donné de zéros d’en-tête est donné par l’élément correspondant dans le tableau indices.

Les tableaux indices et maxLzCounts doivent avoir la même longueur. La fonction HLL_IMPORT vérifie également que les indices de sous-flux se trouvent dans la plage valide et qu’il n’y a pas d’indices de sous-flux en double. Le tableau indices ne doit pas être trié. Les zéros d’en-tête ne sont pas validés. Les valeurs invalides ne causeront pas d’échec de la requête, mais entraîneront des résultats indéfinis pour les éléments suivants HLL_ESTIMATE.

Par exemple :

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

Exemples

Configuration de l’environnement :

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

SELECT COUNT(*) FROM uservisits;

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

Étape 1 :

Créez une table qui contient la date du calendrier (année/mois/jour) et la structure HLL. Nous utilisons HLL_EXPORT pour stocker la structure binaire sous forme d’objet texte :

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

Étape 2 :

Nous pouvons calculer les IPs uniques par mois en agrégeant la structure HLL de chaque jour de l’étape 1. Nous utilisons HLL_IMPORT pour transformer le texte en structure binaire, puis HLL_COMBINE pour combiner plusieurs structures HLL en une seule structure, puis HLL_ESTIMATE pour calculer le nombre de valeurs distinctes :

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

Comparaison :

Nous comparons l’utilisation de l’agrégation en utilisant les fonctions HLL à HLL dans les données de niveau de détail. Dans ce cas, HLL() est équivalent à HLL_ESTIMATE(HLL_COMBINE(HLL_IMPORT())) de l’étape 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

Comme vous pouvez le voir, l’agrégation des structures HLL est significativement plus rapide que l’agrégation sur les données de base, par exemple 1,3 seconde contre 149 secondes dans ce petit exemple, ce qui représente une diminution du temps de requête de 100.