Remove duplicates by using the HLL feature in ApsaraDB for SelectDB - ApsaraDB for SelectDB

HyperLogLog (HLL) est un algorithme de déduplication approximative intégré à ApsaraDB for SelectDB. Lorsque des décomptes distincts exacts ne sont pas requis, HLL s'exécute plus rapidement et consomme beaucoup moins de mémoire que COUNT DISTINCT. Il convient ainsi aux charges analytiques à grande échelle, telles que le décompte quotidien des visiteurs uniques (UV) ou les statistiques de pages vues.

HLL présente une complexité spatiale de O(log(logn)) et une complexité temporelle de O(n). Le taux d'erreur typique se situe entre 1 % et 2 %. Ce taux dépend de la taille du jeu de données et de la fonction de hachage utilisée.

Cas d'usage de HLL

Utilisez HLL lorsque les deux conditions suivantes sont réunies :

Le jeu de données est volumineux et atteint une échelle où le coût d'une déduplication exacte devient élevé.
Un résultat approximatif est acceptable, par exemple pour le décompte quotidien des UV ou les statistiques de pages vues.

Pour une déduplication exacte, utilisez plutôt COUNT DISTINCT.

Fonctionnement de HLL

HLL est une version améliorée de l'algorithme LogLog fondée sur l'épreuve de Bernoulli.

Fondement mathématique

Une épreuve de Bernoulli correspond à une expérience de lancer de pièce : lancez une pièce de manière répétée jusqu'à l'apparition de la face avant, puis notez le nombre de lancers sous la forme k. Répétez cette expérience n fois. Le nombre maximal de lancers observés sur l'ensemble des épreuves est noté k_max.

Par estimation du maximum de vraisemblance (MLE), la cardinalité estimée (nombre total de valeurs distinctes) s'exprime ainsi :

n = 2^k_max

Enregistrer uniquement la valeur k_max suffit à estimer la cardinalité ; le stockage des valeurs brutes n'est jamais nécessaire.

Erreur d'estimation

Une seule série d'estimations présente un taux d'erreur élevé lorsque n est petit. Par exemple, après trois épreuves avec k_max = 6, la formule donne 2^6 = 64, ce qui s'éloigne fortement de la valeur réelle n = 3. L'erreur diminue à mesure que le nombre d'épreuves augmente.

Implémentation de HLL dans SelectDB

La fonctionnalité HLL de SelectDB constitue une implémentation technique de l'algorithme HLL. Une colonne HLL stocke un état de calcul intermédiaire plutôt que des valeurs brutes. SelectDB agrège cet état en continu afin de réduire le volume de données et d'accélérer les requêtes. Le taux d'erreur des résultats obtenus via cette fonctionnalité avoisine 1 %.

HLL s'utilise exclusivement comme colonne de valeur (et non comme colonne clé), avec le type d'agrégation HLL_UNION. Le système détermine automatiquement la longueur de la colonne selon le degré d'agrégation ; vous n'avez donc ni longueur ni valeur par défaut à spécifier.

HLL remplace couramment COUNT DISTINCT et s'associe à la fonctionnalité ROLLUP pour calculer efficacement les UV sur différentes plages temporelles.

Fonctions HLL

Fonction	Description
`HLL_UNION_AGG(hll)`	Fonction d'agrégation. Calcule la cardinalité estimée sur l'ensemble des lignes correspondant aux conditions de la requête.
`HLL_CARDINALITY(hll)`	Calcule la cardinalité estimée pour une valeur unique d'une colonne HLL.
`hll_hash(column_name)`	Génère une valeur de colonne HLL à partir de la colonne source spécifiée. Utilisez cette fonction lors de l'insertion ou de l'importation de données.

Remarque

Pour interroger une colonne HLL, utilisez HLL_UNION_AGG. La sélection directe des valeurs brutes d'une colonne HLL n'est pas prise en charge.

Décompte des visiteurs uniques par date

Cet exemple montre comment créer une table d'agrégation, charger des données d'échantillon et interroger les UV à l'aide de HLL.

Étape 1 : Créer une table avec une colonne HLL

CREATE TABLE test_hll(
    dt date,
    id int,
    name char(10),
    province char(10),
    os char(10),
    pv hll hll_union
)
Aggregate KEY (dt,id,name,province,os)
distributed by hash(id) buckets 10
PROPERTIES(
    "replication_num" = "1",
    "in_memory"="false"
);

Important

Lors de la définition d'une colonne HLL :

Définissez le type de colonne sur hll et le type d'agrégation sur hll_union.
Ne configurez pas une colonne HLL comme colonne clé.
Ne spécifiez ni longueur ni valeur par défaut, car le système définit automatiquement la longueur.

Étape 2 : Importer des données

Préparez un fichier CSV (test_hll.csv) contenant les éléments suivants :

2022-05-05,10001,Test 01,Beijing,windows
2022-05-05,10002,Test 01,Beijing,linux
2022-05-05,10003,Test 01,Beijing,macos
2022-05-05,10004,Test 01,Hebei,windows
2022-05-06,10001,Test 01,Shanghai,windows
2022-05-06,10002,Test 01,Shanghai,linux
2022-05-06,10003,Test 01,Jiangsu,macos
2022-05-06,10004,Test 01,Shaanxi,windows

Toutes les méthodes d'importation utilisent hll_hash(id) pour alimenter la colonne HLL pv à partir de la colonne id.

Stream Load

curl --location-trusted -u root: \
  -H "label:label_test_hll_load" \
  -H "column_separator:," \
  -H "columns:dt,id,name,province,os,pv=hll_hash(id)" \
  -T test_hll.csv \
  http://127.0.0.1:8030/api/demo/test_hll/_stream_load

Un chargement réussi renvoie le résultat suivant :

{
    "TxnId": 693,
    "Label": "label_test_hll_load",
    "TwoPhaseCommit": "false",
    "Status": "Success",
    "Message": "OK",
    "NumberTotalRows": 8,
    "NumberLoadedRows": 8,
    "NumberFilteredRows": 0,
    "NumberUnselectedRows": 0,
    "LoadBytes": 320,
    "LoadTimeMs": 23,
    "BeginTxnTimeMs": 0,
    "StreamLoadPutTimeMs": 1,
    "ReadDataTimeMs": 0,
    "WriteDataTimeMs": 9,
    "CommitAndPublishTimeMs": 11
}

Broker Load

LOAD LABEL demo.test_hlllabel
(
    DATA INFILE("hdfs://hdfs_host:hdfs_port/user/doris_test_hll/data/input/file")
    INTO TABLE `test_hll`
    COLUMNS TERMINATED BY ","
    (dt,id,name,province,os)
    SET (
        pv = HLL_HASH(id)
    )
);

Étape 3 : Interroger les UV

UV totaux sur toutes les dates

SELECT HLL_UNION_AGG(pv) FROM test_hll;

+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
+---------------------+
1 row in set (0.00 sec)

Ce résultat équivaut à celui de COUNT(DISTINCT pv) :

SELECT COUNT(DISTINCT pv) FROM test_hll;

+----------------------+
| count(DISTINCT `pv`) |
+----------------------+
|                    4 |
+----------------------+
1 row in set (0.01 sec)

UV par date

SELECT HLL_UNION_AGG(pv) FROM test_hll GROUP BY dt;

+---------------------+
| hll_union_agg(`pv`) |
+---------------------+
|                   4 |
|                   4 |
+---------------------+
2 rows in set (0.01 sec)