Uso de bitmaps para computar valores distintos para agregações hierárquicas

Se você estiver contando valores distintos para agregações hierárquicas (por exemplo, conjuntos de agrupamento múltiplos, valores acumulados ou cubos), pode melhorar o desempenho produzindo bitmaps que representam os valores distintos e calculando o número de valores distintos destes bitmaps. Usar esta abordagem pode ser mais rápido do que usar COUNT(DISTINCT <expr>).

Este tópico explica como usar bitmaps para contar valores distintos.

Para outras técnicas de contagem de valores distintos, consulte Cálculo do número de valores distintos.

Neste tópico:

Introdução

Ao calcular o número de valores distintos para agregações hierárquicas (por exemplo, vários conjuntos de agrupamento, valores acumulados ou cubos), você pode acelerar o cálculo produzindo e consultando um bitmap que represente o conjunto de todos os valores distintos possíveis.

  • Neste bitmap, você define os bits que correspondem aos valores distintos que estão presentes nos dados.

  • Ao calcular o número de valores distintos, você usa as funções de bitmap para contar os bits que estão definidos no bitmap (em vez de consultar a tabela com COUNT(DISTINCT <expressão>)).

As funções de bitmap podem desempenhar melhor que COUNT(DISTINCT <expressão>) sob as seguintes condições:

  • A consulta realiza uma agregação hierárquica (por exemplo, para múltiplos conjuntos de agrupamentos, valores acumulados ou cubos) que conta valores distintos.

    Ao contrário de COUNT(DISTINCT <expressão>) (que precisa ser executada para cada grupo), você pode compor e reutilizar bitmaps chamando as funções de bitmap. Isto pode reduzir o custo do plano de consulta.

  • O intervalo de valores é denso (por exemplo, o valor é gerado por uma sequência)

    Observe que se o intervalo de valores for esparso, é possível usar a função de janela DENSE_RANK para transformar o intervalo esparso de valores em um intervalo denso de valores.

  • O intervalo de valores é pequeno. Uma grande variedade de valores pode requerer vários bitmaps que não cabem na memória principal e devem ser salvos em disco.

Além disso, para melhorar ainda mais o desempenho, é possível calcular esses bitmaps com antecedência (por exemplo, em uma exibição materializada), em vez de durante a consulta, e usar esses bitmaps pré-calculados em sua consulta.

Como os bitmaps identificam valores distintos

Um bitmap é um pedaço contíguo de memória que é armazenado como um tipo de dado BINARY. Um bitmap é uma matriz de bits que podem ser definidos individualmente. Por exemplo, um bitmap de 4 bytes consiste em 32 bits (4 bytes * 8 bits por byte).

Para cada valor distinto possível, você pode usar um bit do bitmap para representar a presença ou ausência do valor distinto nos dados. Por exemplo, se os valores 3 e 5 estiverem presentes nos dados, você pode definir o 3º e 5º bits como 1 no bitmap. (Se os valores distintos não forem valores numéricos, é preciso mapear os valores para valores numéricos).

Para as funções de bitmap no Snowflake, o tamanho padrão de um bitmap é 32.768 bits (4 KiB). Observe que este tamanho não corresponde ao tamanho físico do valor BINARY. Internamente, as funções de bitmap gerenciam a representação física do bitmap, que pode não ser um bitmap real. (Por exemplo, as funções podem utilizar um vetor de índice). O tamanho físico de um bitmap pode variar de 10 bytes a 4108 bytes.

Se o número de valores distintos for maior que 32.768 bits, são necessários vários bitmaps para representar todos os valores. O processo de divisão dos bits para valores distintos em diferentes bitmaps é chamado de bucketização. Por exemplo, os bits para os valores distintos que vão de 1 - 65.536 estão separados em dois buckets distintos. O bitmap em um bucket representa os valores 1 - 32.768, e o bitmap no outro bucket representa os valores 32.769 - 65.536. O bitmap em cada bucket contém um subconjunto dos bits que representam os valores distintos.

O diagrama a seguir mostra a representação lógica de um bitmap. (Como mencionado anteriormente, a representação física do bitmap no valor BINARY pode ser diferente).

Logical representation of a bitmap

Um valor distinto é representado pela combinação de um bucket contendo um bitmap e um bit que é definido nesse bitmap. Para identificar o bucket e o bit que representa um valor específico, use as seguintes funções:

  • Chame BITMAP_BUCKET_NUMBER para identificar o bucket que contém o bitmap que tem o bit para o valor.

  • Chame BITMAP_BIT_POSITION para identificar a posição baseada em zero do bit dentro do bitmap para o valor.

Por exemplo, o valor numérico 1 é representado pelo bit na posição 0 no bitmap 1:

select bitmap_bucket_number(1), bitmap_bit_position(1);

+-------------------------+------------------------+
| BITMAP_BUCKET_NUMBER(1) | BITMAP_BIT_POSITION(1) |
|-------------------------+------------------------|
|                       1 |                      0 |
+-------------------------+------------------------+
Copy

O valor numérico 32.768 é representado pelo bit na posição 32.767 no bitmap 1:

select bitmap_bucket_number(32768), bitmap_bit_position(32768);

+-----------------------------+----------------------------+
| BITMAP_BUCKET_NUMBER(32768) | BITMAP_BIT_POSITION(32768) |
|-----------------------------+----------------------------|
|                           1 |                      32767 |
+-----------------------------+----------------------------+
Copy

Como outro exemplo, o valor numérico 32.769 é representado pelo bit na posição 0 no bitmap 2:

select bitmap_bucket_number(32769), bitmap_bit_position(32769);

+-----------------------------+----------------------------+
| BITMAP_BUCKET_NUMBER(32769) | BITMAP_BIT_POSITION(32769) |
|-----------------------------+----------------------------|
|                           2 |                          0 |
+-----------------------------+----------------------------+
Copy

Criação de bitmaps

Para criar bitmaps que representem todos os valores distintos possíveis, chame a função BITMAP_CONSTRUCT_AGG em uma instrução SELECT:

  1. Passe o valor retornado por BITMAP_BIT_POSITION para a coluna para a função BITMAP_CONSTRUCT_AGG.

  2. Na instrução SELECT, selecione BITMAP_BUCKET_NUMBER e use GROUP BY para agregar os resultados de um determinado bitmap (identificado pelo “número do bucket”).

BITMAP_CONSTRUCT_AGG é uma função de agregação. A agregação neste contexto significa definir o bit para um valor distinto, se alguma linha tiver esse valor distinto. Se várias linhas contêm o valor 3, BITMAP_CONSTRUCT_AGG apenas define o bit para 3 uma vez e não altera o valor do bit para as linhas adicionais que contêm 3.

Por exemplo, crie a seguinte tabela contendo uma coluna de valores numéricos. Insira dois valores distintos, um dos quais é maior que 32768.

CREATE OR REPLACE TABLE bitmap_test_values (val INT);
insert into bitmap_test_values values (1), (32769);
Copy

Execute o seguinte comando para produzir bitmaps com bits que representam os valores distintos:

-- Display the bitmap in hexadecimal
alter session set binary_output_format='hex';

select bitmap_bucket_number(val) as bitmap_id,
    bitmap_construct_agg(bitmap_bit_position(val)) as bitmap
    from bitmap_test_values
    group by bitmap_id;

+-----------+----------------------+
| BITMAP_ID | BITMAP               |
|-----------+----------------------|
|         1 | 00010000000000000000 |
|         2 | 00010000000000000000 |
+-----------+----------------------+
Copy

Nota

A coluna BITMAP contém uma representação física do bitmap, que não é necessariamente o bitmap real. Neste exemplo, a coluna contém um vetor de índice que representa o bitmap.

Um vetor de índice é uma forma pela qual as funções do bitmap armazenam a representação física do bitmap. Dependendo do número de valores representados pelo bitmap, as funções de bitmap podem usar diferentes representações físicas para o bitmap.

Você não deve esperar que o valor binário do bitmap seja armazenado em um formato específico. Para determinar quais bits são definidos, use as funções de bitmap (em vez de examinar você mesmo o valor binário).

A inserção de linhas adicionais com os mesmos valores não altera o bitmap resultante. A função BITMAP_CONSTRUCT_AGG define o bit para um valor distinto apenas uma vez.

insert into bitmap_test_values values (32769), (32769), (1);

select bitmap_bucket_number(val) as bitmap_id,
    bitmap_construct_agg(bitmap_bit_position(val)) as bitmap
    from bitmap_test_values
    group by bitmap_id;

+-----------+----------------------+
| BITMAP_ID | BITMAP               |
|-----------+----------------------|
|         1 | 00010000000000000000 |
|         2 | 00010000000000000000 |
+-----------+----------------------+
Copy

A inserção de outros valores distintos produz um bitmap diferente no qual os bits correspondentes para esses valores são definidos.

insert into bitmap_test_values values (2), (3), (4);

select bitmap_bucket_number(val) as bitmap_id,
    bitmap_construct_agg(bitmap_bit_position(val)) as bitmap
    from bitmap_test_values
    group by bitmap_id;

+-----------+----------------------+
| BITMAP_ID | BITMAP               |
|-----------+----------------------|
|         1 | 00040000010002000300 |
|         2 | 00010000000000000000 |
+-----------+----------------------+
Copy

Agregação de bitmaps

Se você precisar agregar diferentes bitmaps no mesmo bucket (identificado pelo número do bucket retornado por BITMAP_BUCKET_NUMBER), chame BITMAP_OR_AGG.

Cálculo do número de valores distintos a partir de bitmaps

Para obter a contagem total dos valores distintos dos bitmaps, chame BITMAP_COUNT, passando um bitmap criado por BITMAP_CONSTRUCT_AGG ou BITMAP_OR_AGG.

Por exemplo:

select bitmap_bucket_number(val) as bitmap_id,
    bitmap_count(bitmap_construct_agg(bitmap_bit_position(val))) as distinct_values
    from bitmap_test_values
    group by bitmap_id;

+-----------+-----------------+
| BITMAP_ID | DISTINCT_VALUES |
|-----------+-----------------|
|         1 |               4 |
|         2 |               1 |
+-----------+-----------------+
Copy

Uso de bitmaps para melhorar o desempenho das consultas

Os exemplos a seguir demonstram como utilizar as funções de bitmap como uma alternativa à COUNT(DISTINCT <expressão>).

Exemplo 1: Contar os valores distintos em uma única tabela

Suponha que você queira contar o número de valores distintos em my_column. A tabela a seguir compara as instruções SQL para realizar esta tarefa com COUNT(DISTINCT expression) e as funções de bitmap.

Exemplo com COUNT(DISTINCT <expressão>)

Exemplo com funções de bitmap

SELECT
  COUNT(DISTINCT my_column)
FROM my_table;
Copy
SELECT SUM(cnt) FROM (
  SELECT
    BITMAP_COUNT(BITMAP_CONSTRUCT_AGG(BITMAP_BIT_POSITION(my_column))) cnt
  FROM my_table
  GROUP BY BITMAP_BUCKET_NUMBER(my_table)
);
Copy

Observe que se o intervalo de valores em my_column for 0 a 32.768, você pode usar esta instrução mais simples em seu lugar:

-- If the full value range of my_column fits into the bitmap:
--   MIN(my_column) >= 0 AND MAX(my_column) < 32,768
SELECT
  BITMAP_COUNT(BITMAP_CONSTRUCT_AGG(my_column))
FROM my_table;
Copy

Exemplo 2: Usar GROUP BY para calcular as contagens por grupo

Suponha que você queira contar o número de valores distintos em my_column por my_key_1 e my_key_2. A tabela a seguir compara as instruções SQL para realizar esta tarefa com COUNT(DISTINCT expression) e as funções de bitmap.

Exemplo com COUNT(DISTINCT <expressão>)

Exemplo com funções de bitmap

SELECT
  my_key_1,
  my_key_2,
  COUNT(DISTINCT my_column)
FROM my_table
GROUP BY my_key_1, my_key_2;
Copy
SELECT my_key_1, my_key_2, SUM(cnt) FROM (
  SELECT
    my_key_1,
    my_key_2,
    BITMAP_COUNT(BITMAP_CONSTRUCT_AGG(BITMAP_BIT_POSITION(my_column))) cnt
  FROM my_table
  GROUP BY my_key_1, my_key_2, BITMAP_BUCKET_NUMBER(my_column)
)
GROUP BY my_key_1, my_key_2;
Copy

Exemplo 3: Usar GROUP BY ROLLUP para acumular contagens por grupo

As funções de bitmap funcionam ainda mais eficientemente para consultas agregadas GROUP BY ROLLUP. Os bitmaps podem ser compostos (em contraste com COUNT(DISTINCT <expressão>)), o que resulta em menos trabalho de computação e tempos de execução menores.

Suponha que você queira acumular o número de valores distintos em my_column por my_key_1 e my_key_2. A tabela a seguir compara as instruções SQL para realizar esta tarefa com COUNT(DISTINCT expression) e as funções de bitmap.

Exemplo com COUNT(DISTINCT <expressão>)

Exemplo com funções de bitmap

SELECT
  my_key_1,
  my_key_2,
  COUNT(DISTINCT my_column)
FROM my_table
GROUP BY ROLLUP(my_key_1, my_key_2);
Copy
SELECT my_key_1, my_key_2, SUM(cnt) FROM (
  SELECT
    my_key_1,
    my_key_2,
    BITMAP_COUNT(BITMAP_CONSTRUCT_AGG(BITMAP_BIT_POSITION(my_column))) cnt
  FROM my_table
  GROUP BY ROLLUP(my_key_1, my_key_2), BITMAP_BUCKET_NUMBER(my_column)
)
GROUP BY my_key_1, my_key_2;
Copy

Pré-computação de bitmaps

Para melhorar o desempenho, você pode pré-computar as contagens de valores distintos em uma tabela ou exibição materializada.

Por exemplo, suponha que seu data warehouse contenha uma tabela de fatos com múltiplas dimensões. Você pode definir uma exibição materializada que constrói os bitmaps para realizar uma pré-computação ou pré-agregação grosseira antes de computar os agregados ou cubos finais que requerem uma COUNT(DISTINCT <expressão>).

O exemplo seguinte cria uma tabela contendo os bitmaps e utiliza esta tabela para calcular o número de valores distintos, agregados por diferentes dimensões.

A seguinte instrução cria uma tabela chamada precompute que contém os bitmaps e as informações do bucket:

CREATE TABLE precompute AS
SELECT
  my_dimension_1,
  my_dimension_2,
  BITMAP_BUCKET_NUMBER(my_column) bucket,
  BITMAP_CONSTRUCT_AGG(BITMAP_BIT_POSITION(my_column)) bmp
FROM my_table
GROUP BY 1, 2, 3;
Copy

A seguinte instrução calcula os agregados para my_dimension_1 e my_dimension_2:

SELECT
  my_dimension_1,
  my_dimension_2,
  SUM(BITMAP_COUNT(bmp))
FROM precompute
GROUP BY 1, 2;
Copy

A seguinte instrução calcula o agregado somente para my_dimension_1:

SELECT my_dimension_1, SUM(cnt) FROM (
  SELECT
    my_dimension_1,
    BITMAP_COUNT(BITMAP_OR_AGG(bmp)) cnt
  FROM precompute
  GROUP BY 1, bucket
)
GROUP BY 1;
Copy

A seguinte instrução calcula o agregado somente para my_dimension_2:

SELECT my_dimension_2, SUM(cnt) FROM (
  SELECT
    my_dimension_2,
    BITMAP_COUNT(BITMAP_OR_AGG(bmp)) cnt
  FROM precompute
  GROUP BY 1, bucket
)
GROUP BY 1;
Copy