Use HLL functions for approximate deduplication and query acceleration - ApsaraDB for SelectDB

HyperLogLog (HLL) is an approximate deduplication algorithm built into ApsaraDB for SelectDB. When exact distinct counts are not required, HLL runs faster and uses far less memory than COUNT DISTINCT — making it practical for large-scale analytics workloads such as daily unique visitor (UV) counts and page view statistics.

HLL achieves a space complexity of O(log(logn)) and a time complexity of O(n). The typical error rate is 1%–2%. The actual error rate depends on the dataset size and the hash function used.

When to use HLL

Use HLL when both of the following conditions apply:

The dataset is large and the amount of data has reached a scale where the cost of accurate deduplication is high.
An approximate result is acceptable — for example, daily UV counts or page view statistics.

For exact deduplication, use COUNT DISTINCT instead.

How HLL works

HLL is an upgraded version of the LogLog algorithm. Its mathematical basis is the Bernoulli trial.

Mathematical basis

A Bernoulli trial is a coin-flip experiment: flip a coin repeatedly until the front side appears, and record the number of flips as k. Repeat the experiment n times. The maximum number of flips across all trials is k_max.

Using maximum likelihood estimation (MLE), the estimated cardinality (total number of distinct values) is:

n = 2^k_max

Recording only k_max is sufficient to estimate cardinality — you never need to store the raw values.

Estimation error

A single estimation round has a high error rate when n is small. For example, after three trials with k_max = 6, the formula gives 2^6 = 64, which is far from the actual n = 3. Error decreases as the number of trials grows.

How SelectDB implements HLL

The HLL feature in SelectDB is an engineering implementation of the HLL algorithm. An HLL column stores intermediate computation state rather than raw values. SelectDB continuously aggregates this state to reduce data volume and accelerate queries. The error rate of the estimation results obtained by using the HLL feature is about 1%.

HLL can only be used as a value column (not a key column), with the HLL_UNION aggregation type. The system determines the column length automatically based on the aggregation degree; you do not specify a length or a default value.

HLL is commonly used to replace COUNT DISTINCT and works with the ROLLUP feature to compute UV counts efficiently across time ranges.

HLL functions

Function	Description
`HLL_UNION_AGG(hll)`	Aggregate function. Calculates the estimated cardinality across all rows that match the query conditions.
`HLL_CARDINALITY(hll)`	Calculates the estimated cardinality for a single HLL column value.
`hll_hash(column_name)`	Generates an HLL column value from the specified source column. Use this function when inserting or importing data.

Note

To query an HLL column, use HLL_UNION_AGG. Direct selection of raw HLL column values is not supported.

Count unique visitors by date

This example creates an aggregate table, loads sample data, and queries UV counts using HLL.

Step 1: Create a table with an HLL column

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

When defining an HLL column:

Set the column type to hll and the aggregation type to hll_union.
Do not set an HLL column as a key column.
Do not specify a length or default value — the system sets the length automatically.

Step 2: Import data

Prepare a CSV file (test_hll.csv) with the following content:

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

All import methods use hll_hash(id) to populate the pv HLL column from the id column.

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

A successful load returns:

{
    "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)
    )
);

Step 3: Query UV counts

Total UV across all dates

SELECT HLL_UNION_AGG(pv) FROM test_hll;

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

This result is equivalent to COUNT(DISTINCT pv):

SELECT COUNT(DISTINCT pv) FROM test_hll;

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

UV by 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)