Arrêtez le COUNT(DISTINCT) sur des milliards de lignes : HyperLogLog dans PostgreSQL

Quand votre équipe produit vous demande "combien de viewers uniques ont regardé chaque seconde de cette vidéo ?", la première réponse qui vient à l'esprit est un bon vieux COUNT(DISTINCT viewer_hash). Simple, lisible, évident. Et totalement inutilisable à grande échelle.

Cet article s'inspire d'un retour d'expérience publié sur dev.to par Ahmet Gedik, développeur backend chez TrendVidStream, une plateforme de streaming multi-région. Leur stack est délibérément sobre — PHP 8.4, PostgreSQL, des crons, des déploiements FTP — mais leur problème de cardinalité, lui, n'a rien de sobre.

Le problème : 40 millions d'événements par jour

Chaque lecteur vidéo envoie un heartbeat toutes les cinq secondes : identifiant vidéo, hash anonymisé du viewer, région, et position dans la vidéo. Sur 8 régions, cela représente environ 40 millions d'événements par jour. L'objectif : afficher une heatmap sous la barre de lecture, indiquant seconde par seconde combien de viewers uniques regardaient à cet instant précis.

La requête naïve ressemble à ceci :

SELECT second_bucket, COUNT(DISTINCT viewer_hash)
FROM video_events
WHERE video_id = $1
  AND event_day = $2
GROUP BY second_bucket
ORDER BY second_bucket;

Avec 90 jours de rétention, on parle de 3,6 milliards de lignes. Le temps de réponse sur cette requête ? Plusieurs minutes. Rédhibitoire pour une UI temps réel.

La solution : l'extension postgresql-hll

HyperLogLog (HLL) est un algorithme probabiliste de comptage de cardinalité. Il ne compte pas exactement — il estime — mais avec une précision configurable et une empreinte mémoire dérisoire. Au lieu de stocker chaque valeur distincte, il maintient une structure compacte qui permet d'estimer le nombre d'éléments uniques avec une erreur typique inférieure à 1 %.

L'extension postgresql-hll intègre ce type de données directement dans PostgreSQL. L'idée est d'agréger les hashes en temps réel plutôt que de les stocker bruts, puis de ne requêter que les agrégats.

Schéma de la table d'agrégats

CREATE TABLE video_second_hll (
  video_id     BIGINT        NOT NULL,
  region       TEXT          NOT NULL,
  event_day    DATE          NOT NULL,
  second_bucket SMALLINT     NOT NULL,  -- 0..86399
  viewers_hll  hll           NOT NULL DEFAULT hll_empty(),
  PRIMARY KEY (video_id, region, event_day, second_bucket)
);

Chaque ligne ne stocke plus des événements bruts, mais un sketch HLL représentant l'ensemble des viewers pour une seconde donnée. La taille typique d'un sketch : quelques kilooctets, quelle que soit la cardinalité réelle.

Insertion via upsert

Le worker PHP (exécuté en cron toutes les minutes) pousse les heartbeats agrégés :

INSERT INTO video_second_hll
  (video_id, region, event_day, second_bucket, viewers_hll)
VALUES
  ($1, $2, $3, $4, hll_add(hll_empty(), hll_hash_text($5)))
ON CONFLICT (video_id, region, event_day, second_bucket)
DO UPDATE SET
  viewers_hll = hll_union(
    video_second_hll.viewers_hll,
    EXCLUDED.viewers_hll
  );

L'opération hll_union fusionne deux sketches HLL — ce qui permet aussi de combiner les régions a posteriori sans re-scanner les événements bruts.

Requête de lecture pour la heatmap

SELECT
  second_bucket,
  ROUND(hll_cardinality(hll_union_agg(viewers_hll)))::INT AS unique_viewers
FROM video_second_hll
WHERE video_id   = $1
  AND event_day  = $2
GROUP BY second_bucket
ORDER BY second_bucket;

Temps de réponse constaté : moins de 50 ms pour une vidéo avec des milliers de secondes et plusieurs régions. Contre plusieurs minutes avec l'approche naive.

Les paramètres qui comptent vraiment

HyperLogLog expose deux paramètres principaux dans l'extension :

• log2m : taille du registre (de 4 à 31). Une valeur de 14 donne une erreur standard d'environ 0,81 % — amplement suffisant pour une heatmap.
• regwidth : largeur des registres en bits (1 à 8). La valeur par défaut de 5 couvre des cardinalités jusqu'à plusieurs milliards.

-- Créer un sketch avec précision explicite
SELECT hll_empty(14, 5);

Pour la plupart des cas d'usage analytics, les valeurs par défaut sont raisonnables. N'augmentez log2m que si vous avez besoin d'une précision inférieure à 0,5 % sur des cardinalités très élevées — cela multiplie la taille des sketches.

Ce que cela change côté PHP

Du côté applicatif, l'intégration est transparente. Avec PDO ou doctrine/dbal, les sketches HLL sont manipulés comme des chaînes opaques. Aucune bibliothèque PHP spécifique n'est nécessaire : toute la logique HLL reste dans PostgreSQL.

$stmt = $pdo->prepare(<<<SQL
    SELECT second_bucket,
           ROUND(hll_cardinality(hll_union_agg(viewers_hll)))::INT AS unique_viewers
    FROM video_second_hll
    WHERE video_id = ? AND event_day = ?
    GROUP BY second_bucket
    ORDER BY second_bucket
SQL);
$stmt->execute([$videoId, $day]);
$heatmap = $stmt->fetchAll(PDO::FETCH_KEY_PAIR);

Le tableau résultant mappe chaque seconde à son nombre estimé de viewers uniques — prêt à être sérialisé en JSON pour le frontend.

Conclusion

HyperLogLog n'est pas une solution universelle. Si vous avez besoin d'un comptage exact, d'un débogage viewer par viewer, ou que votre volumétrie reste raisonnable, COUNT(DISTINCT) reste parfaitement valide.

Mais dès que vous atteignez des dizaines de millions d'événements quotidiens et que votre question est "combien d'uniques ?" plutôt que "qui exactement ?", l'extension postgresql-hll offre un rapport précision/performance/complexité imbattable — sans changer de base de données, sans infrastructure supplémentaire, et sans réécrire votre stack PHP.

Le vrai enseignement de ce retour d'expérience : le bon algorithme vaut mieux que le meilleur matériel. Un sketch de quelques Ko remplace 3,6 milliards de lignes, et la requête passe de plusieurs minutes à 50 ms sur le même serveur.

Source originale : Building Per-Second Video Heatmap Analytics with HyperLogLog in Postgres par Ahmet Gedik sur dev.to.