Fondo
En modo de fila tradicional planes de ejecución, SQL Server puede introducir un operador de mapa de bits como parte de la realización temprana de reducción de semiunión antes de un hash paralelo o combinación de combinación. El mapa de bits se construye a partir de la entrada de compilación y se usa para filtrar filas en la entrada de la sonda antes de que lleguen a la combinación. He escrito sobre row-mode mapas de bits antes y también están cubiertos en la documentación.
Este artículo trata sobre el modo por lotes mapas de bits, que tienen una implementación muy diferente. Ha habido mejoras importantes desde la primera aparición del motor de ejecución en modo por lotes en SQL Server 2012. Los detalles proporcionados aquí se aplican a SQL Server 2017, la versión lanzada más recientemente al momento de escribir este artículo. Las características específicas de las versiones anteriores se mencionarán en línea a medida que avancemos.
El Optimizador de Consultas
El único operador de combinación que puede ejecutarse en modo por lotes es la combinación hash. El optimizador de consultas decide si una unión hash en modo por lotes (serie o paralelo) debe tener un mapa de bits o no. El optimizador evalúa la utilidad potencial de un mapa de bits calculando la selectividad de una hipotética semiunión de las entradas de combinación hash en la(s) clave(s) de combinación.
Una semiunión tiene sentido, porque la función del filtrado de mapa de bits es eliminar filas del lado de la sonda que no existen en el lado de la construcción. Si la selectividad estimada de la semiunión es 0,75 o menos, el optimizador considera que vale la pena usar un filtro de mapa de bits en modo por lotes. En otras palabras, se especifica un mapa de bits si el cálculo de semiunión indica que el mapa de bits eliminaría el 25 % o más de las filas del lado de la sonda.
La selectividad de semiunión exacta solo se usa para determinar si la unión hash debe tener un mapa de bits o no. La estimación de selectividad del lado de la sonda (visible como un efecto en las estimaciones de cardinalidad) se modifica para reflejar el hecho de que los mapas de bits generalmente no son perfectos para eliminar filas no calificadas. Este es particularmente el caso cuando el mapa de bits se implementa usando un filtro Bloom, que puede generar falsos positivos (filas del lado de la sonda que pasan el filtro, pero no se unen con el lado de construcción).
Redondeo de selectividad
El optimizador tiene en cuenta esta incertidumbre redondeando la selectividad de la unión semi a una potencia de diez. Lo hace tomando el logaritmo en base 10 antes de redondear. Por ejemplo, una selectividad de semiunión de 0,316 da un log10 valor fraccionalmente por debajo de -0.5, que se redondea a -1. La selectividad del lado de la sonda resultante es 10 =0,1. Por el contrario, una selectividad de semiunión de 0,317 da un log10 valor justo por encima de -0,5, que se redondea a cero. Por lo tanto, la selectividad del lado de la sonda es 10 =1 (todas las filas pasan). Las posibles selectividades del mapa de bits del lado de la sonda resultantes de esta serie de cálculos son 1, 0,1, 0,01, 0,001, etc. Tenga en cuenta que aún se puede usar un mapa de bits cuando la selectividad estimada se redondea a 1 (todas las filas pasan el predicado).
Operadores y estimaciones de cardinalidad
No hay un mapa de bits separado operador para una unión hash en modo por lotes. En su lugar, el operador hash join tiene un Bitmap Creator propiedad (establecida en verdadero), o falta la propiedad (no establecida en falso). Esta diferencia entre la ejecución en modo fila y en modo por lotes hace que sea menos fácil ver si se está creando un mapa de bits, pero refleja con mayor precisión el proceso subyacente:en la ejecución en modo fila, el mapa de bits El operador llena el mapa de bits a medida que las filas fluyen a través de él, una a la vez, antes de llegar a la entrada de compilación de combinación hash. En otras palabras, el mapa de bits y la tabla hash se construyen simultáneamente bajo la ejecución en modo fila. En el modo por lotes, la tabla hash está completamente construida antes de que se cree el mapa de bits (más sobre esto en breve).
El optimizador de consultas no toma decisiones basadas en costos sobre la posición de un filtro de mapa de bits de modo por lotes en el lado de la sonda de la unión hash. Simplemente asume que la selectividad del mapa de bits se aplicará a todos los operadores secundarios en el lado de la sonda. En realidad, el mapa de bits solo se empuja hacia abajo en el lado de la sonda una vez que el optimizador ha seleccionado un único plan de ejecución final. Si el mapa de bits no se puede desplazar hasta un operador de hoja, las estimaciones de cardinalidad se verán un poco extrañas. Esta es una compensación que podría mejorarse en el futuro.
El motor de ejecución
Mientras que el optimizador decide si se debe usar o no un mapa de bits de modo por lotes de unión hash, el motor de ejecución del modo por lotes decide el tipo de mapa de bits para usar en tiempo de ejecución. Esta decisión se basa en la información estadística recopilada sobre las claves de unión del lado de la compilación durante la compilación de la tabla hash. Como se mencionó anteriormente, en contraste con la ejecución en modo de fila, las uniones hash en modo por lotes primero construyen completamente la tabla hash, antes de realizar un paso por separado sobre la tabla hash para construir el mapa de bits.
Mapas de bits simples
Hay dos tipos principales de mapa de bits de unión hash en modo por lotes. Un sencillo bitmap contiene un bit para cada uno de un rango contiguo de valores del lado de construcción. Por ejemplo, un mapa de bits simple de un byte es capaz de indicar si están presentes o no ocho valores del lado de construcción contiguos. Los valores de 0 a 7 inclusive se pueden codificar en el mapa de bits configurando el bit correspondiente. Un valor de 5 establecería el bit 5, que tiene el valor posicional de 2. Podríamos codificar el conjunto {1, 5, 7} como 2 + 2 + 2 =2 + 32 + 128 =162 =101000102 . Un rango de valores que no comienza en cero se puede codificar de la misma manera compensando todos los valores por el valor mínimo presente en el conjunto (que sabemos por las estadísticas de la tabla hash).
Un mapa de bits simple tiene la ventaja de almacenar datos exactos información sobre los valores del lado de la compilación realmente presentes, a costa de requerir memoria proporcional al rango de valores presentes.
mapas de bits complejos
El segundo tipo de mapa de bits es un filtro Bloom. Esto establece uno o más bits en la estructura del mapa de bits según el resultado de aplicar una o más funciones hash a cada valor del lado de la construcción. Probamos las coincidencias aplicando las mismas funciones hash a cada valor del lado de la sonda. Si alguna de las funciones hash identifica un bit que no está configurado, podemos estar seguros de que el valor de la sonda actual no aparece en el lado de la compilación.
Dado que un filtro Bloom es una estructura probabilística, es posible que no filtremos algunos valores de sondeo que no tengan una coincidencia del lado de la construcción (falso positivo), pero nunca filtraremos un valor que esté presente (falso negativo). En otras palabras, un filtro Bloom nos dice "tal vez una coincidencia" o "definitivamente no una coincidencia". La tasa de falsos positivos se puede reducir utilizando más bits por clave (un mapa de bits más grande) o más funciones hash. Para ser claros, un filtro Bloom puede producir un filtrado exacto, pero también puede que no.
Los filtros Bloom presentan una alternativa eficiente en espacio y tiempo cuando un mapa de bits simple es inviable debido a las necesidades de espacio. La implementación del modo por lotes de SQL Server de un filtro Bloom está optimizada para arquitecturas modernas de caché de CPU y se conoce internamente como un mapa de bits complejo. . Los mapas de bits complejos admiten varias columnas de unión y todos los tipos de datos en modo por lotes desde SQL Server 2014.
Elección de mapa de bits
Si SQL Server elige un simple o complejo (Bloom filter) mapa de bits depende del rango de valores del lado de la compilación (a partir de las estadísticas de la tabla hash). Hay una advertencia importante sobre la palabra "rango", que se explicará en la siguiente sección. Mientras tanto, así es como el motor de ejecución elige el tipo de mapa de bits:
- Un pequeño mapa de bits simple se usa cuando el rango de valores es 2 (8,388,608) o menos. Este es el número de bits en 1 MB.
- Cuando el rango de valores es mayor que 2 pero menor o igual a 2 (8 MB), el motor de ejecución elige entre un mapa de bits grande y simple y un mapa de bits complejo calculando la memoria requerida para cada opción y eligiendo la más pequeña. Un mapa de bits grande y simple puede tener un tamaño de hasta 8 MB. El tamaño de un mapa de bits complejo depende del número de bits por clave necesarios para representar adecuadamente los datos. Valores más distintos normalmente significan un mapa de bits complejo más grande.
- Si el rango de valores supera los 2 bits, un mapa de bits complejo se utiliza.
Sobre el rango de valores
El rango de los valores mencionados anteriormente se basa en el binario interno representación de los datos. Por ejemplo, smallint los valores 128 y 255 pueden representarse como 0x0080 y 0x00FF , dando un rango de 0x7F (127) valores binarios. Este rango funcionaría bien con un pequeño mapa de bits simple.
Por otro lado, el datetime los valores "1900-01-01" y "1900-01-02" pueden representarse en 8 bytes como 0x0000000100000000 y 0x0000000200000000 (cuatro bytes para días y cuatro bytes para ticks después de la medianoche). Esta representación segmentada da un rango binario de 0x0100000000 (4,294,967,296) para esos dos valores de ejemplo, que es demasiado grande para caber en un mapa de bits simple (incluso uno grande). Los tipos de datos con representaciones binarias complejas (por ejemplo, intercambio de bytes) normalmente no funcionarán bien con mapas de bits simples.
Otra complicación es que los datos del modo por lotes están normalizados — convertido a un diseño binario que funciona bien con instrucciones vectorizadas — y siempre tiene un tamaño de 64 bits. Los valores que no caben en 64 bits se almacenan "fuera de fila", con un puntero de 64 bits en fila. Por cierto, este diseño binario no es el mismo que informa una conversión de T-SQL a un tipo binario.
Sin embargo, el diseño normalizado es lo suficientemente similar para tipos enteros (por ejemplo, integer y bigint ) que los mapas de bits simples siguen siendo útiles para rangos de estos tipos de datos. Otros tipos con una representación binaria similar a un número entero (por ejemplo, money y date ) también son adecuados.
Un ejemplo más:un conjunto de integer valores en el rango de 1 a 8,388,608 simplemente encajar en un mapa de bits simple pequeño de 1 MB, usando un bit por valor entero posible en el rango. El rango puede tener una compensación fija, por lo que también cabría un rango de enteros de 10 000 000 a 18 388 607 (con una compensación de diez millones). Tenga en cuenta que el número de valores presentes no importa, solo el rango. Dos valores de 0 y 8 388 607 llenarán el pequeño rango de mapa de bits simple, así como un conjunto de todos los valores posibles entre esos dos extremos.
Tablas de Rango
Cuando el motor de ejecución en modo por lotes decide crear un grande y simple mapa de bits o un complejo mapa de bits para una unión hash, también crea una tabla de rango. no construir una tabla de rango para pequeño mapas de bits simples.
La tabla de rango es una estructura de 128 KB de tamaño fijo compuesta por 8192 pares de valores de 8 bytes que especifican un rango (bajo, alto) de valores presentes en la tabla hash. Una tabla de rango se puede construir en cualquier tipo de datos compatible con la ejecución en modo por lotes. Durante el escaneo de la tabla hash terminada, cada lote de datos se usa para completar el mapa de bits y la tabla de rangos.
Para cada valor del lote, se usa una función hash para ubicar un depósito (un par de valores de rango) en la tabla de rango. Si el depósito no se utiliza actualmente, el valor se almacena en valores de 8 bytes tanto altos como bajos. Si el balde ya está en uso, se llena el siguiente balde (y así sucesivamente, hasta que se encuentra un balde vacío).
Si la tabla de rangos se llena en un tercio (se usaron 2730 de 8192 cubos), las entradas usadas se copian, el rango de cubos se duplica y luego los valores guardados se reinsertan de la misma manera que antes (aunque la función hash tiene en cuenta el nuevo tamaño de cubeta). Los cubos superpuestos se fusionan y el proceso de duplicación continúa hasta que el número de cubos usados cae por debajo de 2730. Por ejemplo, dos cubos que inicialmente contienen los "rangos" (1-1) y (2-2) pueden fusionarse en un solo cubo de rango de (1-2) después de duplicar el primer rango.
Una vez que todos los lotes de datos de la tabla hash se han procesado en la tabla de rangos, se realiza una combinación final de cubos y, luego, una ordenación rápida en el lugar coloca los cubos en orden de valor. Esto permite que una búsqueda binaria ubique un segmento de rango dado un valor particular de interés.
El resultado neto de toda esta actividad es producir un conjunto de hasta 2730 rangos distintos que describen los datos en la tabla hash (además del gran mapa de bits simple o complejo).
Usando la tabla de rango
La tabla de rango se usa cuando un filtro de mapa de bits de unión hash se inserta en un operador de exploración de almacén de columnas del lado de la sonda. Cada segmento de almacén de columnas tiene metadatos de catálogo sobre los valores de datos mínimos y máximos presentes en el segmento. El motor de ejecución puede utilizar esta información para realizar búsquedas binarias en la tabla de rangos de mapas de bits para encontrar una coincidencia. Si no se encuentra ninguna coincidencia, el motor de ejecución puede omitir el segmento por completo.
Esta optimización del tiempo de ejecución también se produce para la lectura anticipada, por lo que el motor puede incluso evitar leer segmentos en la memoria que sabe que el filtro de la tabla de rangos eliminará. Cualquier segmento no eliminado por la tabla de rango aún se filtra utilizando el mapa de bits. Esta combinación da como resultado que se elimine el número máximo de filas lo antes posible.
Aunque una tabla de rangos no está construida para un mapa de bits pequeño y simple, esa estructura también se puede usar para lograr la eliminación de segmentos porque se conoce el rango de valores (incluido cualquier desplazamiento). Es lo suficientemente pequeño como para que no valga la pena dividirlo en subintervalos mediante una tabla de intervalos.
Cuando el mapa de bits no se empuja hacia abajo en un escaneo de almacén de columnas, aún se puede evaluar como un filtro de modo por lotes regular para lograr una reducción de semiunión antes de la unión hash. Esto es mucho menos eficiente que la eliminación de segmentos o el filtrado durante el análisis del almacén de columnas, pero sigue siendo mejor que el filtrado en la combinación hash.
Mapas de bits y datos comprimidos
La aplicación de un mapa de bits de modo por lotes de unión hash a los datos del almacén de columnas como parte del análisis puede producir un rendimiento muy bueno, pero requiere que los datos de segmento impuros se descompriman antes de que se pueda aplicar el mapa de bits. Esta descompresión se puede realizar de manera eficiente utilizando las instrucciones SIMD, pero sigue siendo un trabajo adicional.
SQL Server 2016 introdujo la capacidad de crear un mapa de bits para predicados generales en datos de segmento codificados por diccionario. El predicado se evalúa con las entradas del diccionario para producir un nuevo pequeño mapa de bits con cada bit establecido que indica una entrada de diccionario que satisface el predicado. La aplicación de este mapa de bits puede ser extremadamente rápida, especialmente si el mapa de bits cabe en un solo registro SIMD. SQL Server aún puede usar SIMD si el mapa de bits no encaja, pero recopilar bits de un mapa de bits en memoria es un poco menos eficiente que en el caso del registro.
Esta optimización de 2016 se puede aplicar a cualquier predicado insertado en un escaneo de almacén de columnas, incluido un "predicado" de mapa de bits creado por una unión hash ascendente. Para ser claros, SQL Server toma el mapa de bits de unión hash y crea un nuevo mapa de bits (mucho más pequeño) utilizando las entradas del diccionario. Este nuevo mapa de bits se aplica a los datos del segmento antes de la descompresión. La optimización se puede monitorear con el evento extendido column_store_expression_filter_bitmap_set . Cuando se usa un mapa de bits de diccionario, el miembro del evento filter_on_compressed_data_type se completará el miembro. Por lo general, esto contendrá el valor RAWBITMAP . Existe una optimización adicional para convertir el mapa de bits del diccionario comprimido en un filtro de comparación si el mapa de bits del diccionario representa un solo rango contiguo de valores. En ese caso, verá algo diferente a RAWBITMAP (por ejemplo, LTGT para una comparación menor que/mayor que).
Eventos extendidos y Trace Flags
La capacidad general de compilar filtros desplazados hacia abajo (incluidos los mapas de bits generados por una unión hash en modo por lotes) en un escaneo de almacén de columnas en un mapa de bits se puede deshabilitar con el indicador de seguimiento de nivel de sesión 9361. La optimización de mapa de bits de datos comprimidos específica se puede deshabilitar con la sesión Marca de rastreo de nivel 9362. La conversión de un mapa de bits de diccionario con un solo rango contiguo a un filtro de comparación se puede deshabilitar con el indicador de rastreo 9363. Lamentablemente, no hay marcas de rastreo de compilación minorista que informen mensajes informativos sobre mapas de bits en modo por lotes o filtro empujado hacia abajo compilación.
Hay algunos eventos extendidos que producen información sobre mapas de bits en modo por lotes de unión hash. Los más útiles son:
query_execution_column_store_segment_scan_startedquery_execution_column_store_segment_scan_finishedcolumn_store_expression_filter_bitmap_setcolumn_store_segment_eliminate
Cuando un mapa de bits de modo por lotes de combinación hash se empuja hacia abajo en un escaneo de almacén de columnas, el evento "iniciado" informa BITMAP_SIMPLE o BITMAP_COMPLEX como el filter_type . No distingue entre mapas de bits simples pequeños y grandes, ni informa nada sobre la tabla de rango. Los metadatos de eventos extendidos contienen otros valores para column_store_filter_type que incluyen BITMAP_SIMPLE_LARGE entre otras cosas, pero el evento extendido actualmente no produce esta salida cuando se usa un mapa de bits grande y simple. Quizás esto se corrija en una versión futura.
El indicador de rastreo global 646 se puede usar para informar sobre la eliminación de segmentos habilitada por la tabla de rango (o un pequeño mapa de bits simple). Reporta información similar al segmento eliminar evento extendido. Todas las marcas de seguimiento mencionadas en esta sección no están documentadas ni son compatibles.
Pensamientos finales
Los mapas de bits en modo por lotes pueden ser extremadamente efectivos cuando los tipos de datos correctos (64 bits como máximo y tipo entero) y el mapa de bits se puede empujar hacia abajo a un escaneo de almacén de columnas, especialmente si los datos del segmento usan compresión RLE (almacenamiento puro), o si el mapa de bits se puede compilar en otro mapa de bits en datos de diccionario.
Sería bueno que los planes de ejecución reportaran información más detallada sobre los mapas de bits de unión hash, al menos para decir qué tipo de mapa de bits se creó. Tal como está, solo tenemos el Creador de mapas de bits propiedad y algunos eventos extendidos con los que trabajar. Esto hace que el análisis detallado del plan sea un poco más difícil de lo que debería ser, dadas las enormes ganancias de rendimiento que se pueden lograr aprovechando todas las optimizaciones inteligentes integradas en el motor de ejecución para datos de almacén de columnas y uniones hash en modo por lotes.
Demostraciones, ilustraciones y una discusión más detallada de los puntos principales discutidos en este artículo están disponibles en mi sitio personal en Batch Mode Bitmap Demos.
