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

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).

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 |
+-------------------------+------------------------+

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 |
+-----------------------------+----------------------------+

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 |
+-----------------------------+----------------------------+

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

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 |
+-----------+----------------------+

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 |
+-----------+----------------------+

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 |
+-----------+----------------------+

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 |
+-----------+-----------------+

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

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

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

SELECT
  COUNT(DISTINCT my_column)
FROM my_table;

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

SELECT
  my_key_1,
  my_key_2,
  COUNT(DISTINCT my_column)
FROM my_table
GROUP BY my_key_1, my_key_2;

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;

SELECT
  my_key_1,
  my_key_2,
  COUNT(DISTINCT my_column)
FROM my_table
GROUP BY ROLLUP(my_key_1, my_key_2);

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;

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;

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;

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;

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;