Le nombre de valeurs distinctes.¶

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 4 096 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.

Exemples¶

Configuration de l’environnement :

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

SELECT COUNT(*) FROM uservisits;

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

Copy

É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;

Copy

É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

Copy

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

Copy

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.