Remove duplicates by using the HLL feature in ApsaraDB for SelectDB - ApsaraDB for SelectDB: Central de Documentação do Alibaba Cloud

O HyperLogLog (HLL) é um algoritmo de deduplicação aproximada integrado ao ApsaraDB for SelectDB. Quando contagens distintas exatas não são necessárias, o HLL executa mais rápido e consome muito menos memória que o COUNT DISTINCT, tornando-o ideal para cargas de trabalho analíticas em grande escala, como contagens diárias de visitantes únicos (UV) e estatísticas de visualizações de página.

O HLL apresenta complexidade de espaço O(log(logn)) e complexidade de tempo O(n). A taxa de erro típica varia entre 1% e 2%, dependendo do tamanho do conjunto de dados e da função de hash utilizada.

Quando usar o HLL

Use o HLL quando as duas condições a seguir forem verdadeiras:

O conjunto de dados é grande e atingiu uma escala em que o custo da deduplicação exata se torna elevado.
Resultados aproximados são aceitáveis, como em contagens diárias de UV ou estatísticas de visualizações de página.

Para deduplicação exata, use COUNT DISTINCT.

Como o HLL funciona

O HLL é uma evolução do algoritmo LogLog baseada no ensaio de Bernoulli.

Base matemática

Um ensaio de Bernoulli consiste em lançar uma moeda repetidamente até obter a face frontal, registrando o número de lançamentos como k. Repita o experimento n vezes. O maior número de lançamentos entre todos os ensaios é k_max.

Por meio da estimativa de máxima verossimilhança (MLE), calcula-se a cardinalidade estimada (número total de valores distintos) da seguinte forma:

n = 2^k_max

Registrar apenas k_max basta para estimar a cardinalidade, sem necessidade de armazenar os valores brutos.

Erro de estimativa

Uma única rodada de estimativa apresenta alta taxa de erro quando n é pequeno. Por exemplo, após três ensaios com k_max = 6, a fórmula resulta em 2^6 = 64, valor muito distante do n = 3 real. O erro diminui à medida que o número de ensaios aumenta.

Implementação do HLL no SelectDB

O recurso HLL no SelectDB implementa o algoritmo HLL na prática. Uma coluna HLL armazena o estado intermediário de computação em vez de valores brutos. O SelectDB agrega continuamente esse estado para reduzir o volume de dados e acelerar consultas. A taxa de erro dos resultados obtidos com o recurso HLL é de aproximadamente 1%.

Use o HLL apenas como coluna de valor (não como coluna de chave), com o tipo de agregação HLL_UNION. O sistema determina automaticamente o comprimento da coluna com base no grau de agregação; não especifique comprimento nem valor padrão.

Esse recurso substitui frequentemente o COUNT DISTINCT e funciona em conjunto com o ROLLUP para calcular contagens de UV de forma eficiente em diferentes intervalos de tempo.

Funções HLL

Função	Descrição
`HLL_UNION_AGG(hll)`	Função de agregação. Calcula a cardinalidade estimada em todas as linhas correspondentes às condições da consulta.
`HLL_CARDINALITY(hll)`	Calcula a cardinalidade estimada para um único valor de coluna HLL.
`hll_hash(column_name)`	Gera um valor de coluna HLL a partir da coluna de source especificada. Use esta função ao inserir ou importar dados.

Nota

Para consultar uma coluna HLL, use HLL_UNION_AGG. Não há suporte para selecione direta de valores brutos da coluna HLL.

Contagem de visitantes únicos por data

Este exemplo crie uma tabela agregada, carrega dados de amostra e consulta contagens de UV usando HLL.

Etapa 1: Criar uma tabela com coluna 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"
);

Importante

Ao defina uma coluna HLL:

Defina o tipo da coluna como hll e o tipo de agregação como hll_union.
Não configure uma coluna HLL como coluna de chave.
Não especifique comprimento ou valor padrão — o sistema define o comprimento automaticamente.

Etapa 2: Importar dados

Prepare um arquivo CSV (test_hll.csv) com o seguinte conteúdo:

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

Todos os métodos de importação usam hll_hash(id) para popular a coluna HLL pv a partir da coluna 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

Uma carga bem-sucedida retorna:

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

Etapa 3: Consultar contagens de UV

UV total em todas as datas

SELECT HLL_UNION_AGG(pv) FROM test_hll;

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

Esse resultado equivale a COUNT(DISTINCT pv):

SELECT COUNT(DISTINCT pv) FROM test_hll;

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

UV por data

SELECT HLL_UNION_AGG(pv) FROM test_hll GROUP BY dt;

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