Sketches HyperLogLog dans BigQuery

COUNT(DISTINCT user_id) oblige BigQuery à conserver chaque valeur distincte en mémoire pour la déduplication. Pour des fenêtres glissantes de 7, 30 et 90 jours, chaque fenêtre scanne indépendamment toutes les données sous-jacentes.

Les sketches HyperLogLog++ (HLL++) résolvent ce problème. Ce sont des structures de données probabilistes qui estiment la cardinalité (le nombre de valeurs distinctes) avec une précision de ~97 à 99 %. La propriété essentielle : ils sont composables. Vous pouvez précalculer des sketches quotidiens, puis les fusionner pour n’importe quelle plage de dates arbitraire en quelques millisecondes.

Comment fonctionne HLL++ (le modèle mental)

Il n’est pas nécessaire de comprendre l’algorithme complet pour bien l’utiliser, mais le modèle mental aide.

Un sketch est un résumé compact des valeurs distinctes qu’il a observées. Il ne stocke pas les valeurs réelles — il stocke une empreinte statistique de taille fixe. Quand vous fusionnez deux sketches, le résultat est équivalent à avoir observé toutes les valeurs des deux ensembles. C’est la propriété additive qui rend les sketches puissants : la fusion du sketch du lundi et de celui du mardi donne le comptage distinct correct pour lundi+mardi, sans rescanner les données d’aucune des deux journées.

La contrepartie est la précision. Les sketches donnent un comptage approché, pas exact. Le taux d’erreur dépend du paramètre de précision. Pour la plupart des cas d’usage analytics, l’approximation est suffisamment bonne pour être indiscernable d’un comptage exact, et les économies de coûts sont considérables.

Le pattern précalcul-et-fusion

C’est le pattern que vous utiliserez en production. Il fonctionne en deux étapes :

Étape 1 : Précalculer les sketches quotidiens

Exécutez ceci une fois pour créer la table historique, puis ajoutez des données quotidiennement via une requête planifiée ou un modèle dbt :

CREATE OR REPLACE TABLE `project.dataset.daily_user_sketches` AS
SELECT
  event_date,
  HLL_COUNT.INIT(user_id, 15) AS user_sketch
FROM `project.dataset.events`
GROUP BY event_date;

Le paramètre 15 est la précision (plus de détails ci-dessous). Chaque ligne de cette table correspond à une date avec un sketch résumant tous les user_id distincts pour ce jour. Le sketch fait quelques Ko quelle que soit la quantité d’utilisateurs.

Étape 2 : Fusionner les sketches pour n’importe quelle plage de dates

SELECT HLL_COUNT.MERGE(user_sketch) AS unique_users_30d
FROM `project.dataset.daily_user_sketches`
WHERE event_date >= DATE_SUB(CURRENT_DATE(), INTERVAL 30 DAY);

Cette requête lit 30 lignes (un sketch par jour), les fusionne et retourne le comptage distinct approché. Elle s’exécute en quelques millisecondes qu’il y ait 1 million ou 100 millions d’utilisateurs. Comparez cela à un COUNT(DISTINCT user_id) sur 30 jours de données brutes d’événements, qui scanne des téraoctets.

Vous pouvez ajouter n’importe quelle dimension à la table de sketches pour permettre le découpage :

CREATE OR REPLACE TABLE `project.dataset.daily_user_sketches_by_country` AS
SELECT
  event_date,
  geo_country,
  HLL_COUNT.INIT(user_id, 15) AS user_sketch
FROM `project.dataset.events`
GROUP BY event_date, geo_country;

Vous pouvez maintenant obtenir les utilisateurs uniques par pays pour n’importe quelle plage de dates en ajoutant un filtre pays à la requête de fusion.

APPROX_COUNT_DISTINCT vs HLL_COUNT

BigQuery offre une fonction plus simple pour les comptages approchés :

SELECT APPROX_COUNT_DISTINCT(user_id) AS approx_users
FROM `project.dataset.events`
WHERE event_date >= '2025-01-01';

APPROX_COUNT_DISTINCT est pratique pour les requêtes ponctuelles. Elle est plus rapide que COUNT(DISTINCT) exact et utilise moins de mémoire. Mais elle a une limitation fondamentale : elle n’est pas composable.

Vous ne pouvez pas additionner le APPROX_COUNT_DISTINCT d’hier et celui d’aujourd’hui pour obtenir un comptage valide sur 2 jours. Les utilisateurs présents les deux jours seraient comptés deux fois. La fonction donne une approximation pour une seule requête, pas un bloc pour la pré-agrégation.

Utilisez APPROX_COUNT_DISTINCT pour l’exploration ad hoc. Utilisez HLL_COUNT.INIT et HLL_COUNT.MERGE pour les métriques de production, les tableaux de bord et tout ce qui nécessite des fenêtres glissantes ou des plages de dates flexibles.

Le paramètre de précision

Le paramètre de précision (plage valide : 10 à 24) contrôle le compromis entre exactitude et taille du sketch :

La précision 15 donne environ 0,4 % d’erreur. Sur une métrique d’1 million d’utilisateurs uniques, c’est +/- 4 000 utilisateurs. Pour pratiquement toutes les décisions métier, c’est indiscernable d’un comptage exact.

GA4 utilise la précision 14 pour les comptages d’utilisateurs et 12 pour les sessions en interne. Si Google considère que c’est suffisamment précis pour son propre produit analytics, c’est probablement suffisant pour vos tableaux de bord.

Une précision plus élevée signifie des sketches plus grands, donc plus de stockage et des fusions légèrement plus lentes. La différence est négligeable pour les tables de sketches quotidiens (quelques centaines de Ko par ligne à la précision 15), mais importante si vous stockez des sketches à très haute cardinalité dimensionnelle (par utilisateur, par URL de page).

Métriques à fenêtres glissantes

Le pattern précalcul-et-fusion excelle pour les fenêtres glissantes. Une exigence courante pour les tableaux de bord :

-- 7-day, 30-day, and 90-day unique users in one query
SELECT
  (SELECT HLL_COUNT.MERGE(user_sketch)
   FROM `project.dataset.daily_user_sketches`
   WHERE event_date >= DATE_SUB(CURRENT_DATE(), INTERVAL 7 DAY)) AS unique_users_7d,

  (SELECT HLL_COUNT.MERGE(user_sketch)
   FROM `project.dataset.daily_user_sketches`
   WHERE event_date >= DATE_SUB(CURRENT_DATE(), INTERVAL 30 DAY)) AS unique_users_30d,

  (SELECT HLL_COUNT.MERGE(user_sketch)
   FROM `project.dataset.daily_user_sketches`
   WHERE event_date >= DATE_SUB(CURRENT_DATE(), INTERVAL 90 DAY)) AS unique_users_90d;

Avec un COUNT(DISTINCT) exact, chaque fenêtre scanne la table complète des événements bruts pour sa plage de dates. La fenêtre de 90 jours à elle seule peut scanner des téraoctets. Avec les sketches, les trois fenêtres lisent depuis la petite table de sketches et retournent en moins d’une seconde.

Impact sur les performances

• Vitesse d’exécution : 4 à 8× plus rapide que COUNT(DISTINCT) exact sur les mêmes données
• Consommation de slots : 8× plus faible car les sketches nécessitent beaucoup moins de mémoire que la déduplication complète
• Fenêtres glissantes : Un comptage d’utilisateurs uniques sur 90 jours qui prenait 30 secondes avec le comptage exact prend 200 millisecondes avec les fusions de sketches
• Stockage : Une table de sketches quotidiens pour un dataset d’un milliard d’utilisateurs fait des mégaoctets, pas des téraoctets

Le gain de performance vient du précalcul unique et des requêtes multiples. Le calcul quotidien des sketches s’exécute une fois (ou de manière incrémentale via un modèle incrémental dbt). Les chargements ultérieurs de tableaux de bord, les requêtes ad hoc et les appels API lisent depuis la table de sketches plutôt que les événements bruts.

Quand ne pas utiliser HLL++

Les sketches sont inappropriés pour :

• Comptages exacts requis par la réglementation ou les contrats : Reporting financier, métriques SLA où +/- 1 % a des implications légales
• Très faibles cardinalités : Si vous avez moins de 10 000 valeurs distinctes, le comptage exact est suffisamment peu coûteux et l’erreur d’approximation peut être proportionnellement perceptible
• Cas d’usage autres que le comptage distinct : HLL++ ne fait qu’estimer la cardinalité. Pour d’autres analytics approchés (percentiles, quantiles), utilisez APPROX_QUANTILES

Pour les utilisateurs uniques, les sessions uniques, les appareils uniques et les URLs de pages uniques sur des fenêtres temporelles, les sketches HLL++ réduisent à la fois le coût et la latence de manière significative. Le calcul du modèle de coût favorise les réponses approchées quand le comptage exact est prohibitivement coûteux.