SelectDB precise deduplication - ApsaraDB for SelectDB: Central de Documentação do Alibaba Cloud

Quando seu conjunto de dados atinge centenas de milhões de linhas, a função COUNT(DISTINCT ...) torna-se lenta. Todos os valores distintos de cada nó são redistribuídos para um único nó de nível superior para realizar a mesclagem final. Esse processo cria um gargalo que aumenta conforme o volume de dados e o tamanho do bitmap. O ApsaraDB for SelectDB resolve esse problema com bitmaps ortogonais: os dados são distribuídos em buckets para que cada nó calcule sua própria interseção ou união de forma independente. Apenas os resultados reduzidos fluem para o nó de nível superior.

Como funcionam os bitmaps ortogonais

A execução padrão da função COUNT(DISTINCT ...) ocorre em dois estágios:

Scan (Node 1)              Scan (Node 2)
+---------+---------+      +---------+---------+
| user_id | tag     |      | user_id | tag     |
+---------+---------+      +---------+---------+
| 1       | A       |      | 3       | A       |
| 2       | B       |      | 4       | C       |
+---------+---------+      +---------+---------+
         |                          |
         +----------+  +-----------+
                    |  |
             Top-level node
         Receives ALL distinct values
         from every node, merges them
         (bottleneck: I/O + single-node compute)

Se um bitmap ultrapassar 1 GB, essa etapa final de mesclagem se torna o gargalo, tanto em E/S de rede quanto na pressão de computação em um único nó.

O ApsaraDB for SelectDB evita esse gargalo utilizando uma coluna hid (hash ID). Durante a criação da tabela, um algoritmo de hash atribui os IDs de usuário aos buckets. Os valores de bitmap em buckets diferentes são ortogonais (não sobrepostos), permitindo que cada bucket calcule seu próprio resultado independentemente:

Stage 1 (distributed): each bucket computes intersection/union locally
Stage 2 (merge): top-level node combines per-bucket results (small data only)

Essa abordagem elimina o gargalo de nó único e permite o dimensionamento para bilhões de linhas.

Limitações

Antes de começar, observe as seguintes restrições:

Modelo Aggregate Key obrigatório: A coluna bitmap deve estar em uma tabela que utilize o modelo Aggregate Key, com BITMAP_UNION como função de agregação.
Tabelas particionadas não suportadas: Não é possível usar funções de bitmap ortogonal em tabelas particionadas. Os limites das partições quebram a garantia de ortogonalidade entre os buckets, tornando os resultados não confiáveis.
Requisito de cardinalidade de hid: A cardinalidade da coluna hid deve ser pelo menos cinco vezes maior que o número de buckets. Isso garante uma distribuição equilibrada dos dados após o bucketing por hash.

Configurar a deduplicação de bitmap

Etapa 1: Criar a tabela

Crie uma tabela usando o modelo Aggregate Key com um campo Value do tipo bitmap e uma coluna hid para bucketing por hash.

CREATE TABLE `user_tag_bitmap` (
  `tag`     BIGINT(20)  NULL COMMENT "User tag",
  `hid`     SMALLINT(6) NULL COMMENT "Bucket ID",
  `user_id` BITMAP BITMAP_UNION NULL COMMENT "User bitmap"
) ENGINE=OLAP
AGGREGATE KEY(`tag`, `hid`)
COMMENT "OLAP"
DISTRIBUTED BY HASH(`hid`) BUCKETS 3;

A coluna hid divide o intervalo de user_id em grupos, atribuindo cada grupo a um único bucket. Isso assegura que os valores de bitmap entre os buckets sejam ortogonais.

Nota

Defina a cardinalidade de hid como pelo menos cinco vezes a contagem de buckets. Por exemplo, com 3 buckets, hid deve ter no mínimo 15 valores distintos.

Etapa 2: Importar dados

Utilize uma instrução LOAD LABEL para carregar os dados. A expressão ceil(tmp_user_id/500) calcula o valor de hid para cada linha, enquanto to_bitmap(tmp_user_id) converte o inteiro bruto em uma entrada de bitmap.

LOAD LABEL user_tag_bitmap_test
(
    DATA INFILE('hdfs://abc')
    INTO TABLE user_tag_bitmap
    COLUMNS TERMINATED BY ','
    (tmp_tag, tmp_user_id)
    SET (
        tag     = tmp_tag,
        hid     = ceil(tmp_user_id/500),
        user_id = to_bitmap(tmp_user_id)
    )
)

Nota

O divisor 500 não é fixo. Ajuste-o com base no intervalo esperado de IDs de usuário e na quantidade alvo de valores distintos de hid.

O formato dos dados de source consiste em duas colunas separadas por vírgula: tag e ID de usuário.

Durante a importação, o SelectDB atribui o mesmo valor de hid aos IDs de usuário no intervalo [1, 5000000) e os coloca no mesmo bucket. Os valores de bitmap entre os buckets permanecem ortogonais, o que reduz o custo computacional das operações de interseção e união.

Etapa 3: Consultar com funções de bitmap ortogonal

Após importar os dados, utilize as funções de bitmap ortogonal descritas na próxima seção. Para obter a lista completa de funções de bitmap padrão, consulte a referência de SQL.

Funções de bitmap ortogonal

As cinco funções a seguir oferecem suporte a consultas de bitmap em cenários ortogonais. As funções que retornam uma contagem substituem diretamente os padrões correspondentes de COUNT(DISTINCT ...), mas executam de maneira distribuída.

Função	Retorno	Caso de uso
`bitmap_orthogonal_intersect`	Bitmap	Calcular o bitmap de interseção entre tags
`orthogonal_bitmap_intersect_count`	Contagem	Contar usuários na interseção de múltiplas tags
`orthogonal_bitmap_union_count`	Contagem	Contar o total de usuários distintos entre tags
`orthogonal_bitmap_expr_calculate`	Bitmap	Avaliar expressões de set complexas (AND, OR, NOT)
`orthogonal_bitmap_expr_calculate_count`	Contagem	Contar resultados de expressões de set complexas

Nota

Não é possível usar funções de bitmap ortogonal em tabelas particionadas. Como as partições são ortogonais entre si, não há garantia de que os dados entre elas sejam ortogonais, o que tornaria os resultados não confiáveis.

bitmap_orthogonal_intersect

Calcula a interseção dos valores de bitmap nos valores de filtro especificados e retorna o resultado como um bitmap.

Sintaxe

bitmap_orthogonal_intersect(bitmap_column, column_to_filter, filter_values)

Parâmetros

Parâmetro	Descrição
`bitmap_column`	Coluna bitmap a ser agregada.
`column_to_filter`	Coluna de dimensão usada para filtragem.
`filter_values`	Lista de comprimento variável de valores para filtrar a coluna de dimensão.

Exemplo

SELECT BITMAP_COUNT(bitmap_orthogonal_intersect(user_id, tag, 13080800, 11110200))
FROM user_tag_bitmap
WHERE tag IN (13080800, 11110200);

Equivalente a:

-- Returns the count of users who appear in ALL specified tags
SELECT COUNT(DISTINCT user_id)
FROM user_tag_bitmap
WHERE tag IN (13080800, 11110200)
  AND <user_id appears in every tag>;

Durante a execução, o Estágio 1 filtra as linhas pelas tags especificadas e calcula a interseção de bitmap em todas as tags correspondentes por bucket. O Estágio 2 mescla iterativamente os bitmaps de interseção de cada bucket no resultado final.

orthogonal_bitmap_intersect_count

Calcula a interseção dos valores de bitmap e retorna a contagem diretamente. A semântica corresponde à de intersect_count, mas a execução é distribuída entre os buckets.A sintaxe é igual à da função intersect_count, mas a implementação é diferente.A sintaxe é igual à da função bitmap_union_count, mas a implementação é diferente.

Sintaxe

orthogonal_bitmap_intersect_count(bitmap_column, column_to_filter, filter_values)

Parâmetros

Parâmetro	Descrição
`bitmap_column`	Coluna bitmap a ser agregada.
`column_to_filter`	Coluna de dimensão usada para filtragem.
`filter_values`	Lista de comprimento variável de valores para filtrar a coluna de dimensão.

Exemplo

SELECT orthogonal_bitmap_intersect_count(user_id, tag, 1150000, 1150001, 390006)
FROM user_tag_bitmap
WHERE tag IN (1150000, 1150001, 390006);

Na execução, o Estágio 1 filtra pelas tags especificadas, calcula a interseção de bitmap em todas as tags correspondentes e conta o resultado por bucket. O Estágio 2 soma todas as contagens por bucket para obter o total final.

orthogonal_bitmap_union_count

Calcula a união dos valores de bitmap e retorna a contagem. A semântica corresponde à de BITMAP_UNION_COUNT, mas a execução é distribuída entre os buckets.

Sintaxe

orthogonal_bitmap_union_count(bitmap_column)

Parâmetros

Parâmetro	Descrição
`bitmap_column`	Coluna bitmap cujos valores são unidos e contados.

Exemplo

SELECT orthogonal_bitmap_union_count(user_id)
FROM user_tag_bitmap
WHERE tag IN (1150000, 1150001, 390006);

Equivalente a:

SELECT COUNT(DISTINCT user_id)
FROM user_tag_bitmap
WHERE tag IN (1150000, 1150001, 390006);

Durante a execução, o Estágio 1 calcula a união de bitmap por bucket e conta o resultado. O Estágio 2 soma todas as contagens por bucket para obter o total final.

orthogonal_bitmap_expr_calculate

Avalia uma expressão de set em colunas bitmap e retorna o resultado como um bitmap. Utilize esta função quando precisar do próprio bitmap para processamento adicional, em vez de apenas uma contagem.

Sintaxe

orthogonal_bitmap_expr_calculate(bitmap_column, filter_column, input_string)

Parâmetros

Parâmetro	Descrição
`bitmap_column`	Coluna bitmap a ser agregada.
`filter_column`	Coluna de dimensão usada para filtragem (a coluna chave para cálculo).
`input_string`	String de expressão de set sobre os valores da coluna chave.

A string input_string aceita os seguintes operadores:

Operador	Operação
`&`	Interseção
`	`	União
`-`	Diferença
`^`	XOR exclusivo
`\`	Caractere de escape

Exemplo

SELECT orthogonal_bitmap_expr_calculate(
    user_id,
    tag,
    '(833736|999777)&(1308083|231207)&(1000|20000-30000)'
)
FROM user_tag_bitmap
WHERE tag IN (833736, 999777, 130808, 231207, 1000, 20000, 30000);

Durante a execução, o Estágio 1 analisa input_string para determinar o filtro de tags, filtra os dados e aplica a expressão de bitmap às linhas filtradas por bucket. O Estágio 2 calcula a união de todos os resultados de bitmap por bucket e retorna o bitmap final.

orthogonal_bitmap_expr_calculate_count

Avalia uma expressão de set em colunas bitmap e retorna a contagem. A sintaxe e os parâmetros são idênticos aos de orthogonal_bitmap_expr_calculate.

Sintaxe

orthogonal_bitmap_expr_calculate_count(bitmap_column, filter_column, input_string)

Parâmetros

Parâmetro	Descrição
`bitmap_column`	Coluna bitmap a ser agregada.
`filter_column`	Coluna de dimensão usada para filtragem (a coluna chave para cálculo).
`input_string`	String de expressão de set sobre os valores da coluna chave. Aceita `&`, `	`, `-`, `^` e `\`.

Exemplo

SELECT orthogonal_bitmap_expr_calculate_count(
    user_id,
    tag,
    '(833736|999777)&(1308083|231207)&(1000|20000-30000)'
)
FROM user_tag_bitmap
WHERE tag IN (833736, 999777, 130808, 231207, 1000, 20000, 30000);

Na execução, o Estágio 1 analisa input_string, filtra os dados, aplica a expressão de bitmap e conta o resultado por bucket. O Estágio 2 calcula a união de todos os resultados de bitmap por bucket e retorna a contagem final.

Próximos passos

Referência de SQL — lista completa de funções de bitmap na seção Bitmap functions