Plano de fundo
No modo de linha tradicional planos de execução, o SQL Server pode introduzir um operador Bitmap como parte da execução antecipada de redução de semi-junção antes de um hash paralelo ou junção de mesclagem. O bitmap é construído a partir da entrada de compilação e usado para filtrar linhas na entrada do probe antes que elas atinjam a junção. Eu escrevi sobre o modo de linha bitmaps antes e eles também são abordados na documentação.
Este artigo é sobre o modo em lote bitmaps, que têm uma implementação muito diferente. Houve grandes melhorias desde a primeira aparição do mecanismo de execução do modo de lote no SQL Server 2012. Os detalhes fornecidos aqui se aplicam ao SQL Server 2017 — a versão lançada mais recentemente no momento da redação. Recursos específicos de versões anteriores serão mencionados inline à medida que avançamos.
O Otimizador de Consulta
O único operador de junção que pode ser executado no modo de lote é a junção de hash. O otimizador de consulta decide se uma junção de hash no modo de lote (serial ou paralelo) deve ter um bitmap ou não. O otimizador avalia a utilidade potencial de um bitmap calculando a seletividade de uma hipotética semi join das entradas de junção de hash na(s) chave(s) de junção.
Uma semijunção faz sentido, porque a função da filtragem de bitmap é remover linhas do lado do teste que não existem no lado da compilação. Se a seletividade estimada da semijunção for 0,75 ou menos, o otimizador considera que vale a pena usar um filtro de bitmap de modo de lote. Em outras palavras, um bitmap é especificado se o cálculo de semijunção indicar que 25% ou mais das linhas do lado da sonda seriam eliminadas pelo bitmap.
A seletividade de semijunção exata é usada apenas para determinar se a junção de hash deve ter um bitmap ou não. A estimativa de seletividade do lado da sonda (visível como um efeito nas estimativas de cardinalidade) é modificada para refletir o fato de que os bitmaps geralmente não são perfeitos na remoção de linhas não qualificadas. Este é particularmente o caso quando o bitmap é implementado usando um filtro Bloom, que pode gerar falsos positivos (linhas do lado da sonda que passam pelo filtro, mas não se unem ao lado da compilação).
Arredondamento de seletividade
O otimizador leva em conta essa incerteza arredondando a seletividade de semijunção para uma potência de dez. Ele faz isso tomando o logaritmo de base 10 antes do arredondamento. Por exemplo, uma seletividade de semijunção de 0,316 fornece um log10 valor fracionado abaixo de -0,5, que é arredondado para -1. A seletividade do lado da sonda resultante é 10 =0,1. Por outro lado, uma seletividade de semijunção de 0,317 fornece um log10 valor logo acima de -0,5, que é arredondado para zero. A seletividade do lado da sonda é, portanto, 10 =1 (todas as linhas passam). As possíveis seletividades de bitmap do lado da sonda resultantes dessa série de cálculos são 1, 0,1, 0,01, 0,001 e assim por diante. Observe que um bitmap ainda pode ser usado quando a seletividade estimada é arredondada para 1 (todas as linhas passam pelo predicado).
Operadores e estimativas de cardinalidade
Não há Bitmap separado operador para uma junção de hash no modo de lote. Em vez disso, o operador de junção de hash tem um Criador de Bitmap propriedade (definida como verdadeira) ou a propriedade está ausente (não definida como falsa). Essa diferença entre a execução em modo de linha e em lote torna menos fácil ver se um bitmap está sendo criado, mas reflete com mais precisão o processo subjacente:Na execução em modo de linha, o Bitmap O operador preenche o bitmap à medida que as linhas fluem por ele, uma de cada vez, antes de atingir a entrada de compilação de junção de hash. Em outras palavras, o bitmap e a tabela de hash são criados simultaneamente na execução do modo de linha. No modo de lote, a tabela de hash é totalmente construída antes que o bitmap seja criado (mais sobre isso em breve).
O otimizador de consulta não faz escolhas baseadas em custo sobre a posição de um filtro de bitmap de modo em lote no lado do probe da junção de hash. Ele simplesmente assume que a seletividade do bitmap se aplicará a todos os operadores filhos no lado do teste. Na realidade, o bitmap só é empurrado para o lado do probe quando um único plano de execução final é selecionado pelo otimizador. Se o bitmap não puder ser empurrado até o operador folha, as estimativas de cardinalidade parecerão um pouco estranhas. Esta é uma troca que pode ser melhorada no futuro.
O mecanismo de execução
Enquanto o otimizador decide se um bitmap de modo de lote de junção de hash deve ser usado ou não, o mecanismo de execução de modo de lote decide o tipo de bitmap para usar em tempo de execução. Essa decisão é informada por informações estatísticas coletadas sobre as chaves de junção do lado da compilação durante a compilação da tabela de hash. Como mencionado anteriormente, em contraste com a execução em modo de linha, as junções de hash em modo de lote constroem completamente a tabela de hash primeiro, antes que uma passagem separada pela tabela de hash seja executada para construir o bitmap.
Bitmaps simples
Existem dois tipos principais de bitmap de junção de hash no modo de lote. Um simples bitmap contém um bit para cada um de um intervalo contíguo de valores do lado da compilação. Por exemplo, um bitmap simples de um byte é capaz de indicar se oito valores contíguos do lado de construção estão presentes ou não. Os valores de 0 a 7 inclusive podem ser codificados no bitmap definindo o bit correspondente. Um valor de 5 definiria o bit 5, que tem o valor posicional de 2. Poderíamos codificar o conjunto {1, 5, 7} como 2 + 2 + 2 =2 + 32 + 128 =162 =101000102 . Um intervalo de valores que não começa em zero pode ser codificado da mesma maneira, compensando todos os valores pelo valor mínimo presente no conjunto (que conhecemos das estatísticas da tabela de hash).
Um bitmap simples tem a vantagem de armazenar exatas informações sobre os valores do lado da compilação realmente presentes, ao custo de exigir memória proporcional ao intervalo de valores presentes.
Bitmaps complexos
O segundo tipo de bitmap é um filtro Bloom. Isso define um ou mais bits na estrutura de bitmap de acordo com o resultado da aplicação de uma ou mais funções de hash para cada valor do lado da compilação. Testamos as correspondências aplicando as mesmas funções de hash a cada valor do lado da sonda. Se alguma das funções de hash identificar um bit que não está definido, podemos ter certeza de que o valor do teste atual não aparece no lado da compilação.
Como um filtro Bloom é uma estrutura probabilística, podemos não filtrar alguns valores de teste que não têm uma correspondência no lado da construção (falso positivo), mas nunca filtraremos um valor que está presente (falso negativo). Em outras palavras, um filtro Bloom nos diz “talvez uma correspondência” ou “definitivamente não é uma correspondência”. A taxa de falsos positivos pode ser reduzida usando mais bits por chave (um bitmap maior) ou mais funções de hash. Para ser claro, um filtro Bloom pode produzir filtragem exata, mas também pode não ser.
Os filtros Bloom apresentam uma alternativa eficiente em termos de espaço e tempo quando um bitmap simples é inviável devido aos requisitos de espaço. A implementação do modo de lote do SQL Server de um filtro Bloom é otimizada para arquiteturas de cache de CPU modernas e é conhecida internamente como um bitmap complexo . Bitmaps complexos deram suporte a várias colunas de junção e todos os tipos de dados de modo de lote desde o SQL Server 2014.
Escolha de bitmap
Se o SQL Server escolhe um simples ou complexo (filtro Bloom) bitmap depende do intervalo de valores do lado da compilação (das estatísticas da tabela de hash). Há uma ressalva importante para a palavra “intervalo” lá, que será explicada na próxima seção. Enquanto isso, é assim que o mecanismo de execução escolhe o tipo de bitmap:
- Um pequeno bitmap simples é usado quando o intervalo de valores é 2 (8.388.608) ou menos. Este é o número de bits em 1 MB.
- Quando o intervalo de valores é maior que 2, mas menor ou igual a 2 (8 MB), o mecanismo de execução escolhe entre um bitmap simples grande e um bitmap complexo calculando a memória necessária para cada opção e escolhendo a menor. Um bitmap simples grande pode ter até 8 MB de tamanho. O tamanho de um bitmap complexo depende do número de bits por chave necessários para representar adequadamente os dados. Valores mais distintos normalmente significam um bitmap complexo maior.
- Se o intervalo de valores for além de 2 bits, um bitmap complexo é usado.
Sobre o intervalo de valores
O intervalo dos valores mencionados acima é baseado no binário interno representação dos dados. Por exemplo, o
smallint os valores 128 e 255 podem ser representados como 0x0080 e 0x00FF , fornecendo um intervalo de 0x7F (127) valores binários. Esse intervalo funcionaria bem com um pequeno bitmap simples. Por outro lado, o
datetime os valores "1900-01-01" e "1900-01-02" podem ser representados em 8 bytes como 0x0000000100000000 e 0x0000000200000000 (quatro bytes para dias e quatro bytes para ticks após a meia-noite). Essa representação segmentada fornece um intervalo binário de 0x0100000000 (4.294.967.296) para esses dois valores de exemplo, que é muito grande para caber em um bitmap simples (mesmo um grande). Tipos de dados com representações binárias complexas (por exemplo, troca de bytes) normalmente não funcionarão bem com bitmaps simples. Uma complicação adicional é que os dados do modo de lote são normalizados — convertido em um layout binário que funciona bem com instruções vetorizadas — e sempre tem 64 bits de tamanho. Os valores que não cabem em 64 bits são armazenados “fora da linha”, com um ponteiro de 64 bits na linha. Esse layout binário não é o mesmo relatado por uma conversão T-SQL em um tipo binário.
No entanto, o layout normalizado é semelhante o suficiente para tipos inteiros (por exemplo,
integer e bigint ) que bitmaps simples ainda são úteis para intervalos desses tipos de dados. Outros tipos com uma representação binária do tipo inteiro (por exemplo, money e date ) também são adequados. Mais um exemplo:Um conjunto de
integer valores no intervalo de 1 a 8.388.608 serão apenas caber em um bitmap simples pequeno de 1 MB, usando um bit por valor inteiro possível no intervalo. O intervalo pode ter um deslocamento fixo, portanto, um intervalo inteiro de 10.000.000 a 18.388.607 também caberia (com um deslocamento de dez milhões). Observe que o número de valores presentes não importa, apenas o intervalo. Dois valores de 0 e 8.388.607 preencherão o pequeno intervalo de bitmap simples tão bem quanto um conjunto de todos os valores possíveis entre esses dois extremos. Tabelas de intervalo
Quando o mecanismo de execução do modo em lote decide criar um grande e simples bitmap ou um complexo bitmap para uma junção de hash, ele também cria uma tabela de intervalo. Ele não construir uma tabela de intervalo para pequeno bitmaps simples.
A tabela de intervalo é uma estrutura de 128 KB de tamanho fixo composta de 8.192 pares de valores de 8 bytes que especificam um intervalo (baixo, alto) de valores presentes na tabela de hash. Uma tabela de intervalo pode ser construída em qualquer tipo de dados compatível com a execução em modo de lote. Durante a varredura da tabela de hash finalizada, cada lote de dados é usado para preencher o bitmap e a tabela de alcance.
Para cada valor no lote, uma função de hash é usada para localizar um bucket (par de valores de intervalo) na tabela de intervalo. Se o bucket não estiver sendo usado no momento, o valor será armazenado em valores de 8 bytes baixo e alto. Se o balde já estiver em uso, o próximo balde será preenchido (e assim por diante, até que um balde vazio seja localizado).
Se a tabela de intervalo ficar um terço cheia (2.730 de 8.192 buckets usados), as entradas usadas são copiadas, o intervalo de bucket é dobrado, então os valores salvos são reinseridos da mesma maneira que antes (embora a função hash leve em consideração o novo tamanho do balde). Quaisquer buckets sobrepostos são mesclados e o processo de duplicação continua até que o número de buckets usados caia abaixo de 2.730. Por exemplo, dois buckets que contêm inicialmente os 'intervalos' (1-1) e (2-2) podem ser mesclados em um único bucket de intervalo de (1-2) após a duplicação do primeiro intervalo.
Depois que todos os lotes de dados da tabela de hash forem processados na tabela de intervalo, uma mesclagem final de bucket é executada e, em seguida, um quicksort in-loco coloca os buckets em ordem de valor. Isso permite que uma pesquisa binária localize um intervalo de intervalo dado um determinado valor de interesse.
O resultado líquido de toda essa atividade é produzir um conjunto de até 2.730 intervalos distintos que descrevem os dados na tabela de hash (além do grande bitmap simples ou complexo).
Usando a tabela de intervalo
A tabela de intervalo é usada quando um filtro de bitmap de junção de hash é enviado para um operador de verificação columnstore do lado do probe. Cada segmento columnstore tem metadados de catálogo sobre os valores de dados mínimos e máximos presentes no segmento. O mecanismo de execução pode usar essas informações para pesquisar uma correspondência na tabela de intervalo de bitmap. Se nenhuma correspondência for encontrada, o mecanismo de execução poderá pular o segmento completamente.
Essa otimização do tempo de execução também ocorre para leitura antecipada, de modo que o mecanismo pode até evitar a leitura de segmentos na memória que ele sabe que serão eliminados pelo filtro da tabela de intervalo. Quaisquer segmentos não eliminados pela tabela de intervalo ainda são filtrados usando o bitmap. Essa combinação resulta na eliminação do número máximo de linhas o mais cedo possível.
Embora uma tabela de intervalo não seja criada para um bitmap pequeno e simples, essa estrutura também pode ser usada para obter a eliminação de segmento porque o intervalo de valores é conhecido (incluindo qualquer deslocamento). É pequeno o suficiente para não valer a pena particioná-lo em subintervalos usando uma tabela de intervalos.
Quando o bitmap não é enviado para uma verificação de columnstore, ele ainda pode ser avaliado como um filtro de modo de lote regular para obter redução de semijunção antes da junção de hash. Isso é muito menos eficiente do que a eliminação de segmento ou filtragem durante a verificação de columnstore, mas ainda é melhor do que filtrar na própria junção de hash.
Bitmaps e dados compactados
A aplicação de um bitmap de modo de lote de junção de hash aos dados columnstore como parte da verificação pode produzir um desempenho muito bom, mas exige que os dados de segmento impuros sejam descompactados antes que o bitmap possa ser aplicado. Essa descompressão pode ser realizada de forma eficiente usando instruções SIMD, mas ainda é um trabalho extra.
O SQL Server 2016 introduziu a capacidade de criar um bitmap para predicados gerais em dados de segmento codificados por dicionário. O predicado é avaliado em relação às entradas do dicionário para produzir um novo bitmap pequeno com cada bit definido indicando uma entrada de dicionário que satisfaça o predicado. A aplicação deste bitmap pode ser extremamente rápida, especialmente se o bitmap caber em um único registro SIMD. O SQL Server ainda pode usar o SIMD se o bitmap não couber, mas a coleta de bits de um bitmap na memória é um pouco menos eficiente do que o caso no registro.
Essa otimização de 2016 pode ser aplicada a qualquer predicado enviado para uma varredura de columnstore, incluindo um "predicado" de bitmap criado por uma junção de hash upstream. Para ser claro, o SQL Server usa o bitmap de junção de hash e cria um novo bitmap (muito menor) usando as entradas do dicionário. Esse novo bitmap é aplicado aos dados do segmento antes da descompactação. A otimização pode ser monitorada com o evento estendido
column_store_expression_filter_bitmap_set . Quando um bitmap de dicionário é usado, o membro do evento filter_on_compressed_data_type membro será preenchido. Normalmente, isso conterá o valor RAWBITMAP . Existe uma otimização adicional para converter o bitmap de dicionário compactado em um filtro de comparação se o bitmap de dicionário representar um único intervalo contíguo de valores. Nesse caso, você verá algo diferente de RAWBITMAP (por exemplo, LTGT para uma comparação menor que/maior que). Eventos estendidos e sinalizadores de rastreamento
A capacidade geral de compilar filtros empurrados para baixo (incluindo bitmaps gerados por uma junção de hash de modo em lote) em uma varredura de columnstore em um bitmap pode ser desabilitada com o sinalizador de rastreamento de nível de sessão 9361. A otimização específica de bitmap de dados compactados pode ser desabilitada com session sinalizador de rastreamento de nível 9362. A conversão de um bitmap de dicionário com um único intervalo contíguo em um filtro de comparação pode ser desativada com o sinalizador de rastreamento 9363. Infelizmente, não há sinalizadores de rastreamento de compilação de varejo que relatem mensagens informativas sobre bitmaps de modo de lote ou filtro empurrado compilação.
Existem alguns eventos estendidos que produzem informações sobre bitmaps de modo de lote de junção de hash. Os mais úteis são:
query_execution_column_store_segment_scan_startedquery_execution_column_store_segment_scan_finishedcolumn_store_expression_filter_bitmap_setcolumn_store_segment_eliminate
Quando um bitmap de modo de lote de junção de hash é enviado para uma verificação de columnstore, o evento “started” relata
BITMAP_SIMPLE ou BITMAP_COMPLEX como o filter_type . Ele não distingue entre bitmaps simples pequenos e grandes, nem relata nada sobre a tabela de intervalo. Os metadados do evento estendido contêm outros valores para column_store_filter_type que incluem BITMAP_SIMPLE_LARGE entre outras coisas, mas o evento estendido atualmente não produz essa saída quando um bitmap simples grande é usado. Talvez isso seja corrigido em uma versão futura. O sinalizador de rastreamento global 646 pode ser usado para relatar informações sobre a eliminação de segmento habilitada pela tabela de intervalo (ou um pequeno bitmap simples). Ele relata informações semelhantes ao segmento eliminar evento estendido. Todos os sinalizadores de rastreamento mencionados nesta seção não são documentados e não têm suporte.
Considerações finais
Os bitmaps do modo de lote podem ser extremamente eficazes quando os tipos de dados corretos (máximo de 64 bits e tipo inteiro) são usados e o bitmap pode ser enviado para uma varredura columnstore, especialmente se os dados do segmento usarem compactação RLE (armazenamento puro) ou se o bitmap puder ser compilado em outro bitmap nos dados do dicionário.
Seria bom se os planos de execução relatassem informações mais detalhadas sobre bitmaps de junção de hash — pelo menos para dizer que tipo de bitmap foi criado. Do jeito que está, temos apenas o Criador de Bitmap propriedade e alguns eventos estendidos para trabalhar. Isso torna a análise detalhada do plano um pouco mais difícil do que deveria ser, considerando os enormes ganhos de desempenho que podem ser obtidos aproveitando todas as otimizações inteligentes incorporadas ao mecanismo de execução para dados de armazenamento de colunas e junções de hash no modo de lote.
Demos, ilustrações e mais discussões sobre os principais pontos discutidos neste artigo estão disponíveis em meu site pessoal em Batch Mode Bitmap Demos.
