Bitmaps en mode batch dans SQL Server

Contexte

En mode ligne traditionnel plans d'exécution, SQL Server peut introduire un opérateur Bitmap dans le cadre de l'exécution précoce de la réduction des semi-jointures avant un hachage parallèle ou une jointure de fusion. Le bitmap est construit à partir de l'entrée de génération et utilisé pour filtrer les lignes sur l'entrée de sonde avant qu'elles n'atteignent la jointure. J'ai écrit sur le mode ligne bitmaps avant et ils sont également couverts dans la documentation.

Cet article concerne le mode batch bitmaps, qui ont une implémentation très différente. Des améliorations majeures ont été apportées depuis la première apparition du moteur d'exécution en mode batch dans SQL Server 2012. Les détails donnés ici s'appliquent à SQL Server 2017, la version la plus récente au moment de la rédaction. Les fonctionnalités spécifiques aux versions antérieures seront mentionnées en ligne au fur et à mesure.

L'optimiseur de requêtes

Le seul opérateur de jointure qui peut s'exécuter en mode batch est la jointure par hachage. L'optimiseur de requête décide si une jointure par hachage en mode batch (série ou parallèle) doit avoir un bitmap ou non. L'optimiseur évalue l'utilité potentielle d'un bitmap en calculant la sélectivité d'une hypothétique semi jointure des entrées de jointure de hachage sur la ou les clés de jointure.

Une semi-jointure a du sens, car la fonction du filtrage bitmap est de supprimer les lignes du côté de la sonde qui n'existent pas du côté de la construction. Si la sélectivité estimée de la semi-jointure est 0,75 ou moins, l'optimiseur considère qu'il vaut la peine d'utiliser un filtre bitmap en mode batch. En d'autres termes, un bitmap est spécifié si le calcul de semi-jointure indique que 25 % ou plus des lignes côté sonde seraient éliminées par le bitmap.

La sélectivité exacte de la semi-jointure n'est utilisée que pour déterminer si la jointure par hachage doit avoir un bitmap ou non. L'estimation de sélectivité côté sonde (visible en tant qu'effet sur les estimations de cardinalité) est modifiée pour refléter le fait que les bitmaps ne sont généralement pas parfaits pour supprimer les lignes non qualifiées. C'est notamment le cas lorsque le bitmap est implémenté à l'aide d'un filtre Bloom, qui peut générer des faux positifs (lignes côté sonde qui passent le filtre, mais ne rejoignent néanmoins pas le côté construction).

Arrondi sélectif

L'optimiseur tient compte de cette incertitude en arrondissant la sélectivité des semi-jointures à une puissance de dix. Pour ce faire, il prend le logarithme de base 10 avant d'arrondir. Par exemple, une sélectivité de semi-jointure de 0,316 donne un log₁₀ valeur légèrement inférieure à -0,5, qui est arrondie à -1. La sélectivité côté sonde qui en résulte est de 10 =0,1. En revanche, une sélectivité de semi-jointure de 0,317 donne un log₁₀ valeur juste au-dessus de -0,5, qui est arrondie à zéro. La sélectivité côté sonde est donc de 10 =1 (toutes les lignes passent). Les sélectivités bitmap côté sonde possibles résultant de cette série de calculs sont 1, 0,1, 0,01, 0,001, etc. Notez qu'un bitmap peut toujours être utilisé lorsque la sélectivité estimée est arrondie à 1 (toutes les lignes passent le prédicat).

Opérateurs et estimations de cardinalité

Il n'y a pas de Bitmap séparé opérateur pour une jointure par hachage en mode batch. Au lieu de cela, l'opérateur de jointure par hachage a soit un Bitmap Creator propriété (définie sur true) ou la propriété est manquante (non définie sur false). Cette différence entre l'exécution en mode ligne et en mode batch rend moins facile de voir si un bitmap est en cours de création, mais elle reflète plus précisément le processus sous-jacent :dans l'exécution en mode ligne, le Bitmap L'opérateur remplit le bitmap au fur et à mesure que les lignes le traversent, une par une, avant d'atteindre l'entrée de construction de la jointure par hachage. En d'autres termes, le bitmap et la table de hachage sont construits simultanément lors de l'exécution en mode ligne. En mode batch, la table de hachage est entièrement construite avant la création du bitmap (plus d'informations à ce sujet sous peu).

L'optimiseur de requête ne fait pas de choix basés sur les coûts concernant la position d'un filtre bitmap en mode batch du côté sonde de la jointure par hachage. Il suppose simplement que la sélectivité du bitmap s'appliquera à tous les opérateurs enfants du côté de la sonde. En réalité, le bitmap n'est poussé vers le bas du côté de la sonde qu'une fois qu'un seul plan d'exécution final a été sélectionné par l'optimiseur. Si le bitmap ne peut pas être poussé jusqu'à un opérateur feuille, les estimations de cardinalité sembleront un peu étranges. C'est un compromis qui pourrait être amélioré à l'avenir.

Le moteur d'exécution

Alors que l'optimiseur décide si un bitmap en mode batch joint par hachage doit être utilisé ou non, le moteur d'exécution en mode batch décide du type de bitmap à utiliser lors de l'exécution. Cette décision est éclairée par les informations statistiques recueillies sur les clés de jointure côté construction lors de la construction de la table de hachage. Comme mentionné précédemment, contrairement à l'exécution en mode ligne, les jointures par hachage en mode batch construisent d'abord complètement la table de hachage, avant qu'un passage séparé sur la table de hachage ne soit effectué pour construire le bitmap.

Bitmaps simples

Il existe deux principaux types de bitmap de jointure par hachage en mode batch. Un simple bitmap contient un bit pour chacune d'une plage contiguë de valeurs côté construction. Par exemple, un bitmap simple d'un octet est capable d'indiquer si huit valeurs contiguës côté construction sont présentes ou non. Les valeurs de 0 à 7 inclus peuvent être codées dans le bitmap en définissant le bit correspondant. Une valeur de 5 définirait le bit 5, qui a la valeur de position de 2. Nous pourrions coder l'ensemble {1, 5, 7} comme 2 + 2 + 2 =2 + 32 + 128 =162 =10100010_{2 . Une plage de valeurs qui ne commence pas à zéro peut être encodée de la même manière en décalant toutes les valeurs par la valeur minimale présente dans l'ensemble (que nous connaissons grâce aux statistiques de la table de hachage).}

Un simple bitmap a l'avantage de stocker exact des informations sur les valeurs côté construction réellement présentes, au prix d'une mémoire proportionnelle à la plage de valeurs présentes.

Bitmaps complexes

Le deuxième type de bitmap est un filtre Bloom. Cela définit un ou plusieurs bits dans la structure bitmap en fonction du résultat de l'application d'une ou plusieurs fonctions de hachage à chaque valeur côté construction. Nous testons les correspondances en appliquant les mêmes fonctions de hachage à chaque valeur côté sonde. Si l'une des fonctions de hachage identifie un bit qui n'est pas défini, nous pouvons être sûrs que la valeur actuelle de la sonde n'apparaît pas du côté de la construction.

Puisqu'un filtre Bloom est une structure probabiliste, nous pourrions ne pas filtrer certaines valeurs de sonde qui n'ont pas de correspondance côté construction (faux positif), mais nous ne filtrerons jamais une valeur qui est présente (faux négatif). En d'autres termes, un filtre Bloom nous dit soit "peut-être une correspondance" soit "certainement pas une correspondance". Le taux de faux positifs peut être réduit en utilisant plus de bits par clé (un bitmap plus grand) ou plus de fonctions de hachage. Pour être clair, un filtre Bloom peut produire un filtrage exact, mais il se peut aussi que ce ne soit pas le cas.

Les filtres Bloom présentent une alternative efficace en termes d'espace et de temps lorsqu'un simple bitmap est irréalisable par manque d'espace. L'implémentation en mode batch SQL Server d'un filtre Bloom est optimisée pour les architectures de cache CPU modernes et est connue en interne sous le nom de bitmap complexe . Les bitmaps complexes prennent en charge plusieurs colonnes de jointure et tous les types de données en mode batch depuis SQL Server 2014.

Choix Bitmap

Si SQL Server choisit un simple ou complexe Le bitmap (filtre Bloom) dépend de la plage des valeurs côté construction (à partir des statistiques de la table de hachage). Il y a une mise en garde importante au mot "gamme" ici, qui sera expliquée dans la section suivante. En attendant, voici comment le moteur d'exécution choisit le type de bitmap :

1. Un petit bitmap simple est utilisé lorsque la plage de valeurs est de 2 (8 388 608) ou moins. Il s'agit du nombre de bits dans 1 Mo.
2. Lorsque la plage de valeurs est supérieure à 2 mais inférieure ou égale à 2 (8 Mo), le moteur d'exécution choisit entre un grand bitmap simple et un bitmap complexe en calculant la mémoire requise pour chaque option et en choisissant la plus petite. Un grand bitmap simple peut avoir une taille maximale de 8 Mo. La taille d'un bitmap complexe dépend du nombre de bits par clé nécessaire pour représenter correctement les données. Des valeurs plus distinctes signifient normalement un bitmap plus complexe.
3. Si la plage de valeurs dépasse 2 bits, un bitmap complexe est utilisé.

À propos de la plage de valeurs

La gamme des valeurs mentionnées ci-dessus est basée sur le binaire interne représentation des données. Par exemple, le smallint les valeurs 128 et 255 peuvent être représentées par 0x0080 et 0x00FF , donnant une plage de 0x7F (127) valeurs binaires. Cette plage fonctionnerait bien avec un petit bitmap simple.

D'autre part, le datetime les valeurs "1900-01-01" et "1900-01-02" peuvent être représentées sur 8 octets sous la forme 0x0000000100000000 et 0x0000000200000000 (quatre octets pour les jours et quatre octets pour les ticks après minuit). Cette représentation segmentée donne une plage binaire de 0x0100000000 (4 294 967 296) pour ces deux exemples de valeurs, ce qui est beaucoup trop grand pour tenir dans un simple bitmap (même un grand). Les types de données avec des représentations binaires complexes (par exemple, échange d'octets) ne fonctionneront généralement pas bien avec des bitmaps simples.

Une autre complication est que les données en mode batch sont normalisées - converti en une disposition binaire qui fonctionne bien avec les instructions vectorisées - et a toujours une taille de 64 bits. Les valeurs qui ne peuvent pas tenir dans 64 bits sont stockées « hors ligne », avec un pointeur 64 bits dans la ligne. Cette disposition binaire n'est d'ailleurs pas la même que celle signalée par une conversion T-SQL en un type binaire.

Néanmoins, la disposition normalisée est suffisamment similaire pour les types entiers (par exemple, integer et bigint ) que les bitmaps simples sont toujours utiles pour les plages de ces types de données. D'autres types avec une représentation binaire de type entier (par exemple, money et date ) conviennent également.

Un autre exemple :un ensemble de integer les valeurs comprises entre 1 et 8 388 608 seront seulement tenir dans un petit bitmap simple de 1 Mo, en utilisant un bit par valeur entière possible dans la plage. La plage peut avoir un décalage fixe, donc une plage d'entiers de 10 000 000 à 18 388 607 conviendrait également (avec un décalage de dix millions). Notez que le numéro des valeurs présentes n'a pas d'importance, juste la plage. Deux valeurs de 0 et 8 388 607 rempliront la petite plage de bitmaps simples aussi bien qu'un ensemble de toutes les valeurs possibles entre ces deux extrêmes.

Tableaux de plages

Lorsque le moteur d'exécution en mode batch décide de construire un large simple bitmap ou un complexe bitmap pour une jointure par hachage, il construit également une table de plage. Ce n'est pas construire une table de gamme pour les petits bitmaps simples.

La table de plage est une structure de taille fixe de 128 Ko composée de 8 192 paires de valeurs de 8 octets spécifiant une plage (basse, haute) de valeurs présentes dans la table de hachage. Une table de plages peut être construite sur n'importe quel type de données compatible avec l'exécution en mode batch. Lors de l'analyse de la table de hachage terminée, chaque lot de données est utilisé pour remplir le bitmap et le tableau des plages.

Pour chaque valeur du lot, une fonction de hachage est utilisée pour localiser un seau (paire de valeurs de plage) dans la table de plage. Si le compartiment est actuellement inutilisé, la valeur est stockée dans des valeurs basses et hautes de 8 octets. Si le seau est déjà utilisé, le seau suivant est rempli à la place (et ainsi de suite, jusqu'à ce qu'un seau vide soit localisé).

Si la table de plages est pleine au tiers (2 730 seaux sur 8 192 utilisés), les entrées utilisées sont copiées, la plage de segments est doublée, puis les valeurs enregistrées sont réinsérées de la même manière qu'auparavant (bien que la fonction de hachage tienne compte de la nouvelle taille de godet). Tous les buckets qui se chevauchent sont fusionnés et le processus de doublement se poursuit jusqu'à ce que le nombre de buckets utilisés tombe en dessous de 2 730. Par exemple, deux buckets contenant initialement les "plages" (1-1) et (2-2) peuvent fusionner en un seul bucket de plage de (1-2) après le doublement de la première plage.

Une fois que tous les lots de données de la table de hachage ont été traités dans la table de plage, une fusion finale des compartiments est effectuée, puis un tri rapide sur place classe les compartiments par ordre de valeur. Cela permet à une recherche binaire de localiser un compartiment de plage en fonction d'une valeur particulière d'intérêt.

Le résultat net de toute cette activité est de produire un ensemble de jusqu'à 2 730 plages distinctes décrivant les données dans la table de hachage (en plus du grand bitmap simple ou complexe).

Utilisation de la table des plages

La table de plage est utilisée lorsqu'un filtre bitmap de jointure par hachage est poussé vers le bas dans un opérateur d'analyse columnstore côté sonde. Chaque segment columnstore possède des métadonnées de catalogue sur les valeurs de données minimales et maximales présentes dans le segment. Le moteur d'exécution peut utiliser ces informations pour rechercher une correspondance dans la table de plages de bitmaps. Si aucune correspondance n'est trouvée, le moteur d'exécution peut complètement ignorer le segment.

Cette optimisation de l'exécution se produit également pour la lecture anticipée, de sorte que le moteur peut même éviter de lire des segments dans la mémoire dont il sait qu'ils seront éliminés par le filtre de table de plage. Tous les segments non éliminés par la table de plage sont toujours filtrés à l'aide du bitmap. Cette combinaison permet d'éliminer le plus tôt possible le nombre maximum de lignes.

Bien qu'une table de plage ne soit pas construite pour un petit bitmap simple, cette structure peut également être utilisée pour réaliser l'élimination de segments car la plage de valeurs est connue (y compris tout décalage). Il est suffisamment petit pour qu'il ne soit pas utile de le partitionner en sous-plages à l'aide d'une table de plages.

Lorsque le bitmap n'est pas poussé vers le bas dans une analyse columnstore, il peut toujours être évalué comme un filtre en mode batch normal pour obtenir une réduction de semi-jointure avant la jointure par hachage. C'est beaucoup moins efficace que l'élimination des segments ou le filtrage lors de l'analyse du columnstore, mais c'est toujours mieux que le filtrage au niveau de la jointure de hachage elle-même.

Bitmaps et données compressées

L'application d'un bitmap en mode batch joint par hachage aux données du magasin de colonnes dans le cadre de l'analyse peut produire de très bonnes performances, mais cela nécessite la décompression des données de segment impures avant que le bitmap puisse être appliqué. Cette décompression peut être effectuée efficacement à l'aide des instructions SIMD, mais cela représente toujours un travail supplémentaire.

SQL Server 2016 a introduit la possibilité de créer un bitmap pour les prédicats généraux sur les données de segment codées par dictionnaire. Le prédicat est évalué par rapport aux entrées du dictionnaire pour produire un nouveau petit bitmap avec chaque bit défini indiquant une entrée de dictionnaire qui satisfait le prédicat. L'application de ce bitmap peut être extrêmement rapide, surtout si le bitmap tient dans un seul registre SIMD. SQL Server peut toujours utiliser SIMD si le bitmap ne tient pas, mais la collecte de bits à partir d'un bitmap en mémoire est un peu moins efficace que le cas du registre.

Cette optimisation de 2016 peut être appliquée à tout prédicat poussé dans une analyse columnstore, y compris un "prédicat" bitmap créé par une jointure de hachage en amont. Pour être clair, SQL Server prend le bitmap de jointure de hachage et crée un nouveau bitmap (beaucoup plus petit) à l'aide des entrées du dictionnaire. Ce nouveau bitmap est appliqué aux données du segment avant la décompression. L'optimisation peut être surveillée avec l'événement étendu column_store_expression_filter_bitmap_set . Lorsqu'un bitmap de dictionnaire est utilisé, le membre d'événement filter_on_compressed_data_type membre sera peuplé. Habituellement, cela contiendra la valeur RAWBITMAP . Une autre optimisation existe pour convertir le bitmap de dictionnaire compressé en un filtre de comparaison si le bitmap de dictionnaire représente une seule plage contiguë de valeurs. Dans ce cas, vous verrez autre chose que RAWBITMAP (par exemple LTGT pour une comparaison inférieure/supérieure à).

Événements étendus et indicateurs de trace

La possibilité générale de compiler des filtres poussés vers le bas (y compris les bitmaps générés par une jointure de hachage en mode batch) lors d'une analyse de columnstore dans un bitmap peut être désactivée avec l'indicateur de trace au niveau de la session 9361. L'optimisation spécifique des bitmaps de données compressées peut être désactivée avec la session -indicateur de trace de niveau 9362. La conversion d'un bitmap de dictionnaire avec une seule plage contiguë en un filtre de comparaison peut être désactivée avec l'indicateur de trace 9363. compilation.

Il existe quelques événements étendus qui produisent des informations sur les bitmaps en mode batch de jointure par hachage. Les plus utiles sont :

• query_execution_column_store_segment_scan_started
• query_execution_column_store_segment_scan_finished
• column_store_expression_filter_bitmap_set
• column_store_segment_eliminate

Lorsqu'un bitmap en mode batch de jointure par hachage est poussé vers le bas dans une analyse columnstore, l'événement "started" signale BITMAP_SIMPLE ou BITMAP_COMPLEX comme filter_type . Il ne fait pas de distinction entre les petits et les grands bitmaps simples, et ne rapporte rien sur la table des plages. Les métadonnées d'événement étendues contiennent d'autres valeurs pour column_store_filter_type qui incluent BITMAP_SIMPLE_LARGE entre autres choses, mais l'événement étendu ne produit pas actuellement cette sortie lorsqu'un grand bitmap simple est utilisé. Peut-être que cela sera corrigé dans une prochaine version.

L'indicateur de suivi global 646 peut être utilisé pour rapporter des informations sur l'élimination de segment activée par la table de plage (ou un petit bitmap simple). Il rapporte des informations similaires au segment éliminer l'événement étendu. Tous les indicateurs de trace mentionnés dans cette section sont non documentés et non pris en charge.

Réflexions finales

Les bitmaps en mode batch peuvent être extrêmement efficaces lorsque les types de données appropriés (64 bits max et de type entier) sont utilisés et le bitmap peut être déplacé vers un scan columnstore, en particulier si les données du segment utilisent la compression RLE (stockage pur), ou si le bitmap peut être compilé dans un autre bitmap sur les données du dictionnaire.

Ce serait bien si les plans d'exécution rapportaient des informations plus détaillées sur les bitmaps de jointure de hachage - au moins pour dire quel type de bitmap a été créé. En l'état, nous n'avons que le Bitmap Creator propriété et certains événements étendus avec lesquels travailler. Cela rend l'analyse détaillée du plan un peu plus difficile qu'elle ne devrait l'être, étant donné les énormes gains de performances qui peuvent être réalisés en tirant parti de toutes les optimisations intelligentes intégrées au moteur d'exécution pour les données columnstore et les jointures par hachage en mode batch.

Des démos, des illustrations et une discussion plus approfondie des principaux points abordés dans cet article sont disponibles sur mon site personnel à Batch Mode Bitmap Demos.