Fonctions HyperLogLog++ en langage SQL standard

L'algorithme HyperLogLog++ (HLL++) estime la cardinalité à partir des résumés. Si vous ne souhaitez pas utiliser les résumés et que vous n'avez pas besoin d'une précision personnalisée, envisagez d'utiliser des fonctions d'agrégation approximative avec une précision définie par le système.

Les fonctions HLL++ sont des fonctions d'agrégation approximative. Elles requièrent généralement moins de mémoire que les fonctions d'agrégation exacte, telles que COUNT(DISTINCT), mais elles engendrent également une incertitude statistique. Ainsi, les fonctions HLL++ sont adaptées aux flux de données volumineux pour lesquels l'utilisation linéaire de la mémoire est difficile, ainsi que pour les données qui sont déjà approximatives.

BigQuery accepte les fonctions HLL++ suivantes :

HLL_COUNT.INIT

HLL_COUNT.INIT(input [, precision])

Description

Fonction d'agrégation qui prend une ou plusieurs valeurs input et les agrège dans un nouveau résumé HLL++. Chaque résumé est représenté à l'aide du type de données BYTES. Vous pouvez ensuite fusionner des résumés à l'aide de HLL_COUNT.MERGE ou de HLL_COUNT.MERGE_PARTIAL. Si aucune fusion n'est nécessaire, vous pouvez extraire le nombre final de valeurs distinctes du résumé à l'aide de HLL_COUNT.EXTRACT.

Cette fonction accepte un paramètre facultatif, precision. Ce dernier définit la précision de l'estimation au détriment de la mémoire supplémentaire requise pour traiter les résumés ou les stocker sur disque. Le tableau suivant indique les valeurs de précision autorisées, la taille maximale de résumé par groupe et l'intervalle de confiance (IC) des précisions types :

Précision Taille maximale de résumé (Kio) IC à 65 % IC à 95 % IC à 99 %
10 1 ±3,25 % ±6,50 % ±9,75 %
11 2 ±2,30 % ±4,60 % ±6,89 %
12 4 ±1,63 % ±3,25 % ±4,88 %
13 8 ±1,15 % ±2,30 % ±3,45 %
14 16 ±0,81 % ±1,63 % ±2,44 %
15 (par défaut) 32 ±0,57 % ±1,15 % ±1,72 %
16 64 ±0,41 % ±0,81 % ±1,22 %
17 128 ±0,29 % ±0,57 % ±0,86 %
18 256 ±0,20 % ±0,41 % ±0,61 %
19 512 ±0,14 % ±0,29 % ±0,43 %
20 1 024 ±0,10 % ±0,20 % ±0,30 %
21 2 048 ±0,07 % ±0,14 % ±0,22 %
22 4 096 ±0,05 % ±0,10 % ±0,15 %
23 8 192 ±0,04 % ±0,07 % ±0,11 %
24 16 384 ±0,03 % ±0,05 % ±0,08 %

Si l'entrée est NULL, cette fonction renvoie NULL.

Pour plus d'informations, consultez l'article HyperLogLog dans la pratique : Ingénierie algorithmique d'un algorithme avancé d'estimation de la cardinalité.

Types d'entrée acceptés

INT64, NUMERIC, BIGNUMERIC, STRING, BYTES

Type renvoyé

BYTES

Exemple

SELECT
  HLL_COUNT.INIT(respondent) AS respondents_hll,
  flavor,
  country
FROM UNNEST([
  STRUCT(1 AS respondent, "Vanilla" AS flavor, "CH" AS country),
  (1, "Chocolate", "CH"),
  (2, "Chocolate", "US"),
  (2, "Strawberry", "US")])
GROUP BY flavor, country;

HLL_COUNT.MERGE

HLL_COUNT.MERGE(sketch)

Description

Fonction d'agrégation qui renvoie la cardinalité de plusieurs résumés HLL++ en calculant leur union.

Chaque sketch doit avoir la même précision et être initialisée sur le même type. Les tentatives de fusion de résumés ayant des précisions différentes ou pour des types différents entraînent une erreur. Par exemple, vous ne pouvez pas fusionner un résumé initialisé à partir de données INT64 avec un résumé initialisé à partir de données STRING.

Cette fonction ignore les valeurs NULL lors de la fusion de résumés. Si la fusion ne se produit sur aucune ligne ou seulement sur des valeurs NULL, la fonction renvoie 0.

Types d'entrée acceptés

BYTES

Type renvoyé

INT64

Exemple

SELECT HLL_COUNT.MERGE(respondents_hll) AS num_respondents, flavor
FROM (
  SELECT
    HLL_COUNT.INIT(respondent) AS respondents_hll,
    flavor,
    country
  FROM UNNEST([
    STRUCT(1 AS respondent, "Vanilla" AS flavor, "CH" AS country),
    (1, "Chocolate", "CH"),
    (2, "Chocolate", "US"),
    (2, "Strawberry", "US")])
  GROUP BY flavor, country)
GROUP BY flavor;

HLL_COUNT.MERGE_PARTIAL

HLL_COUNT.MERGE_PARTIAL(sketch)

Description

Fonction d'agrégation qui prend une ou plusieurs entrées sketch HLL++ et les fusionne dans un nouveau résumé.

Cette fonction renvoie NULL s'il n'y a aucune entrée ou si toutes les entrées sont NULL.

Types d'entrée acceptés

BYTES

Type renvoyé

BYTES

Exemple

SELECT HLL_COUNT.MERGE_PARTIAL(respondents_hll) AS num_respondents, flavor
FROM (
  SELECT
    HLL_COUNT.INIT(respondent) AS respondents_hll,
    flavor,
    country
  FROM UNNEST([
    STRUCT(1 AS respondent, "Vanilla" AS flavor, "CH" AS country),
    (1, "Chocolate", "CH"),
    (2, "Chocolate", "US"),
    (2, "Strawberry", "US")])
  GROUP BY flavor, country)
GROUP BY flavor;

HLL_COUNT.EXTRACT

HLL_COUNT.EXTRACT(sketch)

Description

Fonction scalaire qui extrait une estimation de la cardinalité d'un seul résumé HLL++.

Si sketch est NULL, cette fonction renvoie une estimation de la cardinalité égale à 0.

Types d'entrée acceptés

BYTES

Type renvoyé

INT64

Exemple

SELECT
  flavor,
  country,
  HLL_COUNT.EXTRACT(respondents_hll) AS num_respondents
FROM (
  SELECT
    HLL_COUNT.INIT(respondent) AS respondents_hll,
    flavor,
    country
  FROM UNNEST([
    STRUCT(1 AS respondent, "Vanilla" AS flavor, "CH" AS country),
    (1, "Chocolate", "CH"),
    (2, "Chocolate", "US"),
    (2, "Strawberry", "US")])
  GROUP BY flavor, country);

+------------+---------+-----------------+
| flavor     | country | num_respondents |
+------------+---------+-----------------+
| Vanilla    | CH      | 1               |
| Chocolate  | CH      | 1               |
| Chocolate  | US      | 1               |
| Strawberry | US      | 1               |
+------------+---------+-----------------+

À propos de l'algorithme HLL++

L'algorithme HLL++ améliore l'algorithme HLL en évaluant plus précisément les cardinalités de toutes tailles. L'algorithme HLL++ inclut une fonction de hachage 64 bits, une représentation creuse pour réduire les besoins en mémoire, ainsi que la correction de biais empirique pour les faibles estimations de cardinalité.

À propos des résumés

Un résumé est une synthèse d'un flux de données volumineux. Vous pouvez extraire des statistiques d'un résumé pour estimer des statistiques particulières des données d'origine ou fusionner des résumés pour synthétiser plusieurs flux de données. Un résumé présente les caractéristiques suivantes :

  • Il compresse les données brutes en une représentation en mémoire fixe.
  • Il est asymptotiquement plus petit que l'entrée.
  • Il s'agit de la forme sérialisée d'une structure de données sous-linéaire en mémoire.
  • Il nécessite généralement moins de mémoire que l'entrée utilisée pour la création.

Les résumés permettent l'intégration à d'autres systèmes. Par exemple, il est possible de créer des résumés dans des applications externes, telles que Cloud Dataflow, ou Apache Spark, et de les utiliser dans BigQuery et inversement. Les résumés permettent également de créer des agrégations intermédiaires pour les fonctions non additives telles que COUNT(DISTINCT).