Utilisation de bitmaps pour calculer des valeurs distinctes pour les agrégations hiérarchiques

Si vous comptez des valeurs distinctes pour des agrégations hiérarchiques (par exemple, des ensembles de groupements multiples, des rollups ou des cubes), vous pouvez améliorer les performances en produisant des bitmaps qui représentent ces valeurs distinctes et calculer le nombre de valeurs distinctes à partir de ces bitmaps. Cette approche peut être plus rapide que l’utilisation de COUNT(DISTINCT <expr>).

Cette rubrique explique comment utiliser les bitmaps pour compter des valeurs distinctes.

Pour d’autres techniques de comptage des valeurs distinctes, voir Calcul du nombre de valeurs distinctes.

Dans ce chapitre :

Introduction

Lorsque vous calculez le nombre de valeurs distinctes pour des agrégations hiérarchiques (par exemple, des ensembles de groupement multiples, des rollups ou des cubes), vous pouvez accélérer le calcul en produisant et en interrogeant un bitmap qui représente l’ensemble de toutes les valeurs distinctes possibles.

  • Dans ce bitmap, vous définissez les bits qui correspondent aux valeurs distinctes présentes dans les données.

  • Lors du calcul du nombre de valeurs distinctes, vous utilisez les fonctions bitmap pour compter les bits qui sont définis dans le bitmap (plutôt que d’interroger la table avec COUNT(DISTINCT <expression>)).

Les fonctions bitmap peuvent être plus performantes que COUNT(DISTINCT <expression>) dans les conditions suivantes :

  • La requête effectue une agrégation hiérarchique (par exemple pour des ensembles de groupements multiples, des rollups ou des cubes) qui compte les valeurs distinctes.

    Contrairement à COUNT(DISTINCT <expression>) (qui doit être exécutée pour chaque groupe), vous pouvez composer et réutiliser des bitmaps en appelant les fonctions bitmap. Cela peut réduire le coût du plan de requête.

  • La plage de valeurs est dense (par exemple, la valeur est générée par une séquence).

    Notez que si la plage de valeurs est éparse, vous pouvez utiliser la fonction de fenêtre DENSE_RANK pour transformer la plage de valeurs éparse en une plage de valeurs dense.

  • La plage de valeurs est petite. Une grande plage de valeurs peut nécessiter plusieurs bitmaps qui ne tiennent pas dans la mémoire principale et doivent être enregistrés sur le disque.

En outre, pour améliorer encore les performances, vous pouvez calculer ces bitmaps à l’avance (par exemple dans une vue matérialisée), plutôt que pendant la requête. De plus, vous pouvez utiliser ces bitmaps précalculés dans votre requête.

Compréhension de la façon dont les bitmaps identifient des valeurs distinctes

Un bitmap est un morceau de mémoire contigu qui est stocké comme un type de données BINARY. Un bitmap est en fait un tableau de bits qui peut être défini individuellement. Par exemple, un bitmap de 4 octets est constitué de 32 bits (4 octets * 8 bits par octet).

Pour chaque valeur distincte possible, vous pouvez utiliser un bit dans le bitmap pour représenter la présence ou l’absence de la valeur distincte dans les données. Par exemple, si les valeurs 3 et 5 sont présentes dans les données, vous pouvez définir les 3e et 5e bits sur 1 dans le bitmap. (Si les valeurs distinctes ne sont pas des valeurs numériques, vous devez mapper les valeurs en valeurs numériques).

Pour les fonctions bitmap de Snowflake, la taille par défaut d’un bitmap est de 32 768 bits (4 KiB). Notez que cette taille ne correspond pas à la taille physique de la valeur BINARY. En interne, les fonctions bitmap gèrent la représentation physique du bitmap, qui peut ne pas être un bitmap réel. (Par exemple, les fonctions peuvent utiliser un vecteur d’index). La taille physique d’un bitmap peut varier de 10 octets à 4 108 octets.

Si le nombre de valeurs distinctes est supérieur à 32 768 bits, plusieurs bitmaps sont nécessaires pour représenter toutes les valeurs. Le processus qui consiste à diviser les bits correspondant à des valeurs distinctes en différents bitmaps est appelé « mise en compartiment ». Par exemple, les bits des valeurs distinctes allant de 1 à 65 536 sont répartis en deux compartiments distincts. Le bitmap dans un compartiment représente les valeurs 1 - 32 768, et le bitmap dans l’autre compartiment représente les valeurs 32 769 - 65 536. Le bitmap de chaque compartiment contient un sous-ensemble de bits représentant les valeurs distinctes.

Le schéma suivant montre la représentation logique d’un bitmap. (Comme mentionné précédemment, la représentation physique du bitmap dans la valeur BINARY peut être différente).

Logical representation of a bitmap

Une valeur distincte est représentée par la combinaison d’un compartiment contenant un bitmap et d’un bit qui est défini dans ce bitmap. Pour identifier le compartiment et le bit qui représente une valeur spécifique, utilisez les fonctions suivantes :

  • Appelez BITMAP_BUCKET_NUMBER pour identifier le compartiment contenant le bitmap qui a le bit de la valeur.

  • Appelez BITMAP_BIT_POSITION pour identifier la position basée sur le zéro du bit dans le bitmap pour la valeur.

Par exemple, la valeur numérique 1 est représentée par le bit à la position 0 dans le bitmap 1 :

select bitmap_bucket_number(1), bitmap_bit_position(1);

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

La valeur numérique 32 768 est représentée par le bit à la position 32 767 dans le bitmap 1 :

select bitmap_bucket_number(32768), bitmap_bit_position(32768);

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

Autre exemple, la valeur numérique 32 769 est représentée par le bit à la position 0 dans le bitmap 2 :

select bitmap_bucket_number(32769), bitmap_bit_position(32769);

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

Création de bitmaps

Pour créer des bitmaps qui représentent toutes les valeurs distinctes possibles, appelez la fonction BITMAP_CONSTRUCT_AGG dans une instruction SELECT :

  1. Passez la valeur retournée par BITMAP_BIT_POSITION pour la colonne à la fonction BITMAP_CONSTRUCT_AGG.

  2. Dans l’instruction SELECT, sélectionnez BITMAP_BUCKET_NUMBER et utilisez GROUP BY pour agréger les résultats pour un bitmap donné (identifié par le « numéro de compartiment »).

BITMAP_CONSTRUCT_AGG est une fonction d’agrégation. Dans ce contexte, l’agrégation consiste à activer le bit d’une valeur distincte si n’importe quelle ligne possède cette valeur distincte. Si plusieurs lignes contiennent la valeur 3, BITMAP_CONSTRUCT_AGG n’active qu’une seule fois le bit pour 3 et ne modifie pas la valeur du bit pour les lignes supplémentaires qui contiennent 3.

Par exemple, créez la table suivante contenant une colonne de valeurs numériques. Insérez deux valeurs distinctes, dont l’une est supérieure à 32 768.

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

Exécutez la commande suivante pour produire des bitmaps avec des bits qui représentent les valeurs distinctes :

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

Note

La colonne BITMAP contient une représentation physique du bitmap, qui n’est pas nécessairement le bitmap réel. Dans cet exemple, la colonne contient un vecteur d’indexation qui représente le bitmap.

Un vecteur d’indexation est un moyen par lequel les fonctions bitmap stockent la représentation physique du bitmap. En fonction du nombre de valeurs représentées par le bitmap, les fonctions bitmap peuvent utiliser différentes représentations physiques pour le bitmap.

Vous ne devez pas vous attendre à ce que la valeur binaire du bitmap soit dans un format spécifique. Pour déterminer quels bits sont définis, utilisez les fonctions bitmap (plutôt que d’examiner vous-même la valeur binaire).

L’insertion de lignes supplémentaires avec les mêmes valeurs ne modifie pas le bitmap résultant. La fonction BITMAP_CONSTRUCT_AGG n’active qu’une seule fois le bit d’une valeur distincte.

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

L’insertion d’autres valeurs distinctes produit un bitmap différent dans lequel les bits correspondants à ces valeurs sont définis.

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

Agrégation de bitmaps

Si vous devez agréger différents bitmaps dans le même compartiment (identifié par le numéro de compartiment renvoyé par BITMAP_BUCKET_NUMBER), appelez BITMAP_OR_AGG.

Calcul du nombre de valeurs distinctes à partir des bitmaps

Pour obtenir le nombre total de valeurs distinctes à partir des bitmaps, appelez BITMAP_COUNT, en transmettant un bitmap créé par BITMAP_CONSTRUCT_AGG ou BITMAP_OR_AGG.

Par exemple :

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

Utilisation des bitmaps pour améliorer les performances des requêtes

Les exemples suivants montrent comment utiliser les fonctions bitmap comme alternative à COUNT(DISTINCT <expression>).

Exemple 1 : comptage des valeurs distinctes dans une seule table

Supposons que vous vouliez compter le nombre de valeurs distinctes dans my_column. Le tableau suivant compare les instructions SQL pour effectuer cette tâche avec COUNT(DISTINCT expression) et les fonctions bitmap.

Exemple avec COUNT(DISTINCT <expression>)

Example With Bitmap Functions

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

Notez que si la plage de valeurs dans my_column est de 0 à 32 768, vous pouvez utiliser cette instruction plus simple à la place :

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

Exemple 2 : utilisation de GROUP BY pour effectuer le comptage par groupe

Supposons que vous vouliez compter le nombre de valeurs distinctes dans my_column par my_key_1 et my_key_2. Le tableau suivant compare les instructions SQL pour effectuer cette tâche avec COUNT(DISTINCT expression) et les fonctions bitmap.

Exemple avec COUNT(DISTINCT <expression>)

Example With Bitmap Functions

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;

Exemple 3 : utilisation de GROUP BY ROLLUP pour remonter les comptages par groupe

Les fonctions bitmap sont encore plus efficaces pour les requêtes agrégées GROUP BY ROLLUP. Les bitmaps sont composables (contrairement aux COUNT(DISTINCT <expressions>)), ce qui permet de réduire le travail de calcul et les temps d’exécution.

Supposons que vous vouliez remonter le nombre de valeurs distinctes dans my_column par my_key_1 et my_key_2. Le tableau suivant compare les instructions SQL pour effectuer cette tâche avec COUNT(DISTINCT expression) et les fonctions bitmap.

Exemple avec COUNT(DISTINCT <expression>)

Example With Bitmap Functions

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écalcul des bitmaps

Pour améliorer les performances, vous pouvez précalculer le nombre de valeurs distinctes dans une table ou une vue matérialisée.

Par exemple, supposons que votre entrepôt de données contient une table de faits avec plusieurs dimensions. Vous pouvez définir une vue matérialisée qui construit les bitmaps pour effectuer un précalcul ou une pré-agrégation approximative avant de calculer les agrégats ou cubes finaux qui nécessitent une COUNT(DISTINCT <expression>).

L’exemple suivant crée une table contenant les bitmaps et utilise cette table pour calculer le nombre de valeurs distinctes, agrégées par différentes dimensions.

L’instruction suivante crée une table nommée precompute qui contient les bitmaps et les informations sur les compartiments :

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;

L’instruction suivante calcule les agrégats pour my_dimension_1 et my_dimension_2 :

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

L’instruction suivante calcule l’agrégat uniquement pour 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;

L’instruction suivante calcule l’agrégat uniquement pour 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;
Revenir au début