Premiers pas avec postgresql-hll

postgresql-hll est une extension PostgreSQL qui implémente l’algorithme HyperLogLog (HLL). HyperLogLog est un algorithme qui permet de régler les problèmes de performances sur les requêtes de type count-distinct en approximant le nombre d’éléments distinct.

Dans la pratique, on loggue des événements qui ont des dates, les requêtes effectuées à des fins statistiques nécessitent des count-distinct. Par exemple combien de personnes ont déclenché l’événement loggué, et combien de personnes différentes ?

Avec un jeu de test simple, on se rend vite compte de la lenteur de cette requête

testhll=# create table display (id serial primary key, id_campaign int, id_tag int, datelog timestamp, id_member int);
CREATE TABLE

testhll=# insert into display (id_campaign, id_tag, datelog, id_member)
    select c, t, current_date - d, m
    from
        generate_series(1, 10) c,
        generate_series(1, 10) t,
        generate_series(1, 100) d,
        generate_series(1, 1000) m;
INSERT 0 10000000

testhll=# select id_campaign, count(id_member) as display, count(distinct id_member) as unique_display from display group by id_campaign;
id_campaign | display | unique_display
-------------+---------+----------------
1 | 1000000 |           1000
2 | 1000000 |           1000
...
10 | 1000000 |           1000
(10 rows)
Time: 51582.891 ms

testhll=# select datelog::date, count(distinct id_member) from display where datelog::date > '2015-04-01' group by 1 order by 1;
datelog   | count
------------+-------
2015-04-02 |  1000
2015-04-03 |  1000
2015-04-04 |  1000
...
2015-04-22 |  1000
(21 rows)
Time: 13191.161 ms

Ce jeu de test simple contient 10 millions de lignes, le comptage des membres distinct par campagne prend 51s, et le comptage par date pour le mois d’avril prend lui 13s.

Installation de postgres-hll

Vous devez avoir une installation de PostgreSQL déjà fonctionnelle; j’ai testé ici sur une 9.3 sur Ubuntu-serveur. Vous devez également installer postgresql-server-dev-9.3 pour pouvoir compiler l’extension postgresql-hll.

$ sudo apt-get install postgresql-server-dev-9.3 -y

$ git clone https://github.com/aggregateknowledge/postgresql-hll.git
$ cd postgresql-hll/

$ make

$ sudo make install

L’extension peut ensuite être installée sur la base de données.

testhll=# create extension hll;
CREATE EXTENSION

L’agrégation des données

Il s’agit maintenant d’agréger nos données dans une table qui contiendra un set hll « members » pour chaque campagne, tag et date

testhll=# CREATE TABLE daily_uniques (
id_campaign int,
id_tag int,
date date,
members hll
);
CREATE TABLE

testhll=# INSERT INTO daily_uniques(id_campaign, id_tag, date, members)
    SELECT
        id_campaign, id_tag, datelog::date, hll_add_agg(hll_hash_integer(id_member))
    FROM
        display
    GROUP BY
        id_campaign, id_tag, datelog::date;
INSERT 0 10000

Les extractions

testhll=# select id_campaign, hll_cardinality(hll_union_agg(members)) as unique_display FROM daily_uniques group by id_campaign;
id_campaign |  unique_display
-------------+------------------
6 | 999.702072461621
8 | 999.702072461621
...
7 | 999.702072461621
(10 rows)
Time: 233.538 ms

233ms pour un résultat similaire à la première requête, c’est 200 fois plus rapide.

testhll=# select date, hll_cardinality(hll_union_agg(members)) as unique_display FROM daily_uniques WHERE date > '2015-04-01' group by date order by date;
date    |  unique_display
------------+------------------
2015-04-02 | 999.702072461621
2015-04-03 | 999.702072461621
...
2015-04-22 | 999.702072461621
(21 rows)
Time: 56.098 ms

là encore, le résultat est 200 fois plus rapide à obtenir.

Liens, références

About the Author: Guillaume Luchet

Guillaume Luchet est Directeur de la R&D et Lead Développeur chez Bilendi Technology, entrepreneur et développeur freelance.