Sfondo
Nella tradizionale modalità riga piani di esecuzione, SQL Server può introdurre un operatore Bitmap come parte dell'esecuzione della prima riduzione dei semi join prima di un hash parallelo o di un join join. La bitmap è costruita dall'input di compilazione e utilizzata per filtrare le righe sull'input del probe prima che raggiungano il join. Ho scritto di modalità riga bitmap prima e sono anche trattati nella documentazione.
Questo articolo riguarda la modalità batch bitmap, che hanno un'implementazione molto diversa. Sono stati apportati importanti miglioramenti dalla prima apparizione del motore di esecuzione in modalità batch in SQL Server 2012. I dettagli qui forniti si applicano a SQL Server 2017, la versione rilasciata più di recente al momento della scrittura. Le funzionalità specifiche delle versioni precedenti verranno menzionate in linea man mano che procediamo.
Lo Strumento per ottimizzare le query
L'unico operatore di join che può essere eseguito in modalità batch è hash join. Query Optimizer decide se un hash join in modalità batch (seriale o parallelo) deve avere una bitmap o meno. L'ottimizzatore valuta la potenziale utilità di una bitmap calcolando la selettività di un ipotetico semi join degli input di hash join sulle chiavi di join.
Un semi join ha senso, perché la funzione del filtro bitmap è rimuovere le righe dal lato probe che non esistono sul lato build. Se la selettività stimata del semi join è 0,75 o meno, l'ottimizzatore ritiene utile utilizzare un filtro bitmap in modalità batch. In altre parole, viene specificata una bitmap se il calcolo del semi join indica che il 25% o più delle righe lato sonda verranno eliminate dalla bitmap.
L'esatta selettività del semi join viene utilizzata solo per determinare se l'hash join deve avere una bitmap o meno. La stima della selettività lato sonda (visibile come effetto sulle stime di cardinalità) viene modificata per riflettere il fatto che le bitmap non sono generalmente perfette nella rimozione di righe non qualificate. Questo è particolarmente vero quando la bitmap viene implementata utilizzando un filtro Bloom, che può generare falsi positivi (righe lato sonda che superano il filtro, ma non si uniscono comunque al lato build).
Arrotondamento della selettività
L'ottimizzatore tiene conto di questa incertezza arrotondando la selettività del semi join a una potenza di dieci. Lo fa prendendo il logaritmo in base 10 prima di arrotondare. Ad esempio, una selettività semi join di 0,316 fornisce un log10 valore leggermente inferiore a -0,5, arrotondato per difetto a -1. La selettività lato sonda risultante è 10 =0,1. Al contrario, una selettività semi join di 0,317 fornisce un log10 valore appena superiore a -0,5, che viene arrotondato a zero. La selettività lato sonda è quindi 10 =1 (tutte le righe passano). Possibili selettività bitmap lato sonda risultanti da questa serie di calcoli sono 1, 0.1, 0.01, 0.001 e così via. Tieni presente che una bitmap può ancora essere utilizzata quando la selettività stimata viene arrotondata a 1 (tutte le righe superano il predicato).
Operatori e stime di cardinalità
Non esiste una Bitmap separata operatore per un hash join in modalità batch. Invece, l'operatore hash join ha un Bitmap Creator proprietà (impostata su true) o la proprietà è mancante (non impostata su false). Questa differenza tra l'esecuzione in modalità riga e in modalità batch rende meno facile vedere se viene creata una bitmap, ma riflette in modo più accurato il processo sottostante:nell'esecuzione in modalità riga, la Bitmap l'operatore popola la bitmap mentre le righe scorrono su di essa, una alla volta, prima di raggiungere l'input di compilazione dell'hash join. In altre parole, la bitmap e la tabella hash vengono create contemporaneamente nell'esecuzione in modalità riga. In modalità batch, la tabella hash è completamente compilata prima della creazione della bitmap (ne parleremo a breve).
Query Optimizer non effettua scelte basate sui costi sulla posizione di un filtro bitmap in modalità batch sul lato probe dell'hash join. Presuppone semplicemente che la selettività della bitmap si applicherà a tutti gli operatori figlio sul lato sonda. In realtà, la bitmap viene spostata verso il basso dal lato della sonda solo dopo che l'ottimizzatore ha selezionato un unico piano di esecuzione finale. Se la bitmap non può essere spinta fino in fondo a un operatore foglia, le stime di cardinalità sembreranno un po' strane. Questo è un compromesso che potrebbe essere migliorato in futuro.
Il motore di esecuzione
Mentre l'ottimizzatore decide se una bitmap in modalità batch di hash join deve essere utilizzata o meno, il motore di esecuzione in modalità batch decide il tipo di bitmap da utilizzare in fase di esecuzione. Questa decisione è informata dalle informazioni statistiche raccolte sulle chiavi di join lato build durante la creazione della tabella hash. Come accennato in precedenza, a differenza dell'esecuzione in modalità riga, gli hash join in modalità batch creano prima completamente la tabella hash, prima che venga eseguito un passaggio separato sulla tabella hash per creare la bitmap.
Bitmap semplici
Esistono due tipi principali di bitmap di hash join in modalità batch. Un semplice bitmap contiene un bit per ciascuno di un intervallo contiguo di valori lato build. Ad esempio, una semplice bitmap a un byte è in grado di indicare se sono presenti o meno otto valori lato build contigui. I valori da 0 a 7 inclusi possono essere codificati nella bitmap impostando il bit corrispondente. Un valore di 5 imposterebbe il bit 5, che ha il valore posizionale di 2. Potremmo codificare l'insieme {1, 5, 7} come 2 + 2 + 2 =2 + 32 + 128 =162 =101000102 . Un intervallo di valori che non parte da zero può essere codificato allo stesso modo sfalsando tutti i valori del valore minimo presente nell'insieme (che conosciamo dalle statistiche della tabella hash).
Una semplice bitmap ha il vantaggio di memorizzare esatta informazioni sui valori build-side effettivamente presenti, a costo di richiedere memoria proporzionale all'intervallo di valori presenti.
Bitmap complesse
Il secondo tipo di bitmap è un filtro Bloom. Questo imposta uno o più bit nella struttura bitmap in base al risultato dell'applicazione di una o più funzioni hash a ciascun valore lato build. Testiamo le corrispondenze applicando le stesse funzioni hash a ciascun valore lato sonda. Se una qualsiasi delle funzioni hash identifica un bit che non è impostato, possiamo essere sicuri che il valore del probe corrente non appare sul lato build.
Poiché un filtro Bloom è una struttura probabilistica, potremmo non filtrare alcuni valori di sonda che non hanno una corrispondenza lato build (falso positivo), ma non filtreremo mai un valore presente (falso negativo). In altre parole, un filtro Bloom ci dice "forse una corrispondenza" o "decisamente non una corrispondenza". Il tasso di falsi positivi può essere ridotto utilizzando più bit per chiave (una bitmap più grande) o più funzioni hash. Per essere chiari, un filtro Bloom può produrre un filtraggio esatto, ma potrebbe anche non farlo.
I filtri Bloom rappresentano un'alternativa efficiente in termini di spazio e tempo quando si tratta di una bitmap semplice non è fattibile per esigenze di spazio. L'implementazione in modalità batch di SQL Server di un filtro Bloom è ottimizzata per le moderne architetture della cache della CPU ed è nota internamente come bitmap complessa . Le bitmap complesse supportano più colonne di join e tutti i tipi di dati in modalità batch da SQL Server 2014.
Scelta bitmap
Se SQL Server sceglie un semplice o complesso (Filtro Bloom) la bitmap dipende dall'intervallo di valori lato build (dalle statistiche della tabella hash). C'è un avvertimento importante sulla parola "gamma", che sarà spiegato nella prossima sezione. Nel frattempo, ecco come il motore di esecuzione sceglie il tipo di bitmap:
- Una piccola semplice bitmap viene utilizzato quando l'intervallo di valori è 2 (8.388.608) o meno. Questo è il numero di bit in 1 MB.
- Quando l'intervallo di valori è maggiore di 2 ma minore o uguale a 2 (8 MB), il motore di esecuzione sceglie tra una bitmap semplice grande e una bitmap complessa calcolando la memoria richiesta per ciascuna opzione e scegliendo quella più piccola. Una semplice bitmap di grandi dimensioni può avere una dimensione massima di 8 MB. La dimensione di una bitmap complessa dipende dal numero di bit per chiave necessari per rappresentare adeguatamente i dati. Valori più distinti normalmente significano una bitmap complessa più grande.
- Se l'intervallo di valori è superiore a 2 bit, una bitmap complessa viene utilizzato.
Informazioni sull'intervallo di valori
La gamma dei valori di cui sopra si basa sul binario interno rappresentazione dei dati. Ad esempio, il smallint i valori 128 e 255 potrebbero essere rappresentati come 0x0080 e 0x00FF , fornendo un intervallo di 0x7F (127) valori binari. Questo intervallo funzionerebbe bene con una piccola semplice bitmap.
D'altra parte, il datetime i valori "1900-01-01" e "1900-01-02" potrebbero essere rappresentati in 8 byte come 0x0000000100000000 e 0x0000000200000000 (quattro byte per i giorni e quattro byte per i tick dopo la mezzanotte). Questa rappresentazione segmentata fornisce un intervallo binario di 0x0100000000 (4.294.967.296) per quei due valori di esempio, che è troppo grande per adattarsi a una semplice bitmap (anche grande). I tipi di dati con rappresentazioni binarie complesse (ad es. scambio di byte) in genere non funzionano bene con semplici bitmap.
Un'ulteriore complicazione è che i dati in modalità batch sono normalizzati — convertito in un layout binario che funziona bene con le istruzioni vettoriali — e ha sempre una dimensione di 64 bit. I valori che non possono rientrare in 64 bit vengono memorizzati "fuori riga", con un puntatore a 64 bit nella riga. A proposito, questo layout binario non è lo stesso riportato da una conversione T-SQL in un tipo binario.
Tuttavia, il layout normalizzato è abbastanza simile per i tipi interi (ad es. integer e bigint ) che semplici bitmap sono ancora utili per intervalli di questi tipi di dati. Altri tipi con una rappresentazione binaria di tipo intero (ad es. money e date ) sono adatti.
Un altro esempio:un insieme di integer i valori compresi tra 1 e 8.388.608 saranno solo adattarsi a una piccola semplice bitmap da 1 MB, utilizzando un bit per possibile valore intero nell'intervallo. L'intervallo può avere un offset fisso, quindi si adatterebbe anche un intervallo di interi da 10.000.000 a 18.388.607 (con un offset di dieci milioni). Nota che il numero dei valori presenti non importa, solo l'intervallo. Due valori di 0 e 8.388.607 riempiranno il piccolo intervallo di bitmap semplice così come un insieme di tutti i valori possibili tra questi due estremi.
Tabelle degli intervalli
Quando il motore di esecuzione in modalità batch decide di creare un large simple bitmap o un complesso bitmap per un hash join, crea anche una tabella di intervallo. non costruisci una tabella di intervallo per piccolo semplici bitmap.
La tabella dell'intervallo è una struttura a dimensione fissa da 128 KB composta da 8.192 coppie di valori a 8 byte che specificano un intervallo (basso, alto) di valori presenti nella tabella hash. È possibile creare una tabella di intervallo su qualsiasi tipo di dati compatibile con l'esecuzione in modalità batch. Durante la scansione della tabella hash finita, ogni batch di dati viene utilizzato per popolare la bitmap e la tabella degli intervalli.
Per ogni valore nel batch, viene utilizzata una funzione hash per individuare un bucket (coppia di valori di intervallo) nella tabella dell'intervallo. Se il bucket è attualmente inutilizzato, il valore viene archiviato con valori di 8 byte sia bassi che alti. Se il secchio è già in uso, viene riempito il secchio successivo (e così via, fino a trovare un secchio vuoto).
Se la tabella dell'intervallo diventa piena per un terzo (2.730 di 8.192 bucket utilizzati), le voci utilizzate vengono copiate, l'intervallo di bucket viene raddoppiato, quindi i valori salvati vengono reinseriti come prima (sebbene la funzione hash tenga conto di la nuova dimensione del secchio). Eventuali bucket sovrapposti vengono uniti e il processo di raddoppio continua finché il numero di bucket utilizzati non scende al di sotto di 2.730. Ad esempio, due bucket che inizialmente contengono gli "intervalli" (1-1) e (2-2) possono fondersi in un unico bucket di intervallo di (1-2) dopo il raddoppio del primo intervallo.
Una volta che tutti i batch di dati della tabella hash sono stati elaborati nella tabella dell'intervallo, viene eseguita un'unione di bucket finale, quindi un Quicksort sul posto mette i bucket in ordine di valore. Ciò consente a una ricerca binaria di individuare un intervallo di intervalli in base a un particolare valore di interesse.
Il risultato netto di tutta questa attività è di produrre un insieme di fino a 2.730 intervalli distinti che descrivono i dati nella tabella hash (oltre alla grande bitmap semplice o complessa).
Utilizzo della tabella intervalli
La tabella dell'intervallo viene utilizzata quando un filtro bitmap di join hash viene inserito in un operatore di scansione columnstore lato probe. Ogni segmento columnstore dispone di metadati del catalogo sui valori di dati minimi e massimi presenti nel segmento. Il motore di esecuzione può utilizzare queste informazioni per eseguire una ricerca binaria nella tabella dell'intervallo di bitmap per una corrispondenza. Se non viene trovata alcuna corrispondenza, il motore di esecuzione può saltare completamente il segmento.
Questa ottimizzazione del runtime si verifica anche per il read-ahead, quindi il motore può anche evitare di leggere nella memoria segmenti che sa saranno eliminati dal filtro della tabella degli intervalli. Tutti i segmenti non eliminati dalla tabella degli intervalli vengono comunque filtrati utilizzando la bitmap. Questa combinazione fa sì che il numero massimo di righe venga eliminato il prima possibile.
Sebbene una tabella di intervallo non sia creata per una semplice bitmap di piccole dimensioni, tale struttura può essere utilizzata anche per ottenere l'eliminazione del segmento poiché l'intervallo di valori è noto (incluso qualsiasi offset). È abbastanza piccolo da rendere inutile il partizionamento in sotto-intervalli usando una tabella di intervalli.
Quando la bitmap non viene trasferita in una scansione columnstore, può comunque essere valutata come un normale filtro in modalità batch per ottenere una riduzione del semi join prima dell'hash join. Questo è molto meno efficiente dell'eliminazione del segmento o del filtraggio durante la scansione del columnstore, ma è comunque meglio del filtraggio all'hash join stesso.
Bitmap e dati compressi
L'applicazione di una bitmap in modalità batch di hash join ai dati columnstore come parte della scansione può produrre prestazioni molto buone, ma richiede la decompressione dei dati del segmento impuri prima di poter applicare la bitmap. Questa decompressione può essere eseguita in modo efficiente utilizzando le istruzioni SIMD, ma è comunque un lavoro extra.
SQL Server 2016 ha introdotto la possibilità di creare una bitmap per predicati generali sui dati del segmento con codifica dizionario. Il predicato viene valutato rispetto alle voci del dizionario per produrre un nuovo piccola mappa di bit con ogni bit impostato che indica una voce del dizionario che soddisfa il predicato. L'applicazione di questa bitmap può essere estremamente veloce, soprattutto se la bitmap si inserisce in un unico registro SIMD. SQL Server può comunque utilizzare SIMD se la bitmap non si adatta, ma la raccolta di bit da una bitmap in memoria è un po' meno efficiente rispetto al caso nel registro.
Questa ottimizzazione del 2016 può essere applicata a qualsiasi predicato inserito in una scansione columnstore, incluso un "predicato" bitmap creato da un hash join a monte. Per essere chiari, SQL Server prende la bitmap di hash join e crea una nuova bitmap (molto più piccola) utilizzando le voci del dizionario. Questa nuova bitmap viene applicata ai dati del segmento prima della decompressione. L'ottimizzazione può essere monitorata con l'evento esteso column_store_expression_filter_bitmap_set . Quando viene utilizzata una bitmap del dizionario, il membro dell'evento filter_on_compressed_data_type il membro verrà popolato. Di solito questo conterrà il valore RAWBITMAP . Esiste un'ulteriore ottimizzazione per convertire la bitmap del dizionario compressa in un filtro di confronto se la bitmap del dizionario rappresenta un singolo intervallo contiguo di valori. In tal caso vedrai qualcosa di diverso da RAWBITMAP (es. LTGT per un confronto minore/maggiore).
Eventi estesi e flag di traccia
La capacità generale di compilare filtri push-down (incluse le bitmap generate da un hash join in modalità batch) su una scansione columnstore in una bitmap può essere disabilitata con il flag di traccia a livello di sessione 9361. L'ottimizzazione specifica della bitmap di dati compressi può essere disabilitata con la sessione flag di traccia di livello 9362. La conversione di una bitmap di dizionario con un singolo intervallo contiguo in un filtro di confronto può essere disabilitata con il flag di traccia 9363. Purtroppo non ci sono flag di traccia di build retail che riportano messaggi informativi sulle bitmap in modalità batch o sul filtro push-down compilazione.
Esistono alcuni eventi estesi che producono informazioni sulle bitmap in modalità batch di hash join. I più utili sono:
query_execution_column_store_segment_scan_startedquery_execution_column_store_segment_scan_finishedcolumn_store_expression_filter_bitmap_setcolumn_store_segment_eliminate
Quando una bitmap in modalità batch con join hash viene trasferita in una scansione columnstore, l'evento "avviato" segnala BITMAP_SIMPLE o BITMAP_COMPLEX come filter_type . Non distingue tra bitmap semplici piccole e grandi, né riporta nulla sulla tabella dell'intervallo. I metadati dell'evento esteso contengono altri valori per column_store_filter_type che includono BITMAP_SIMPLE_LARGE tra le altre cose, ma l'evento esteso non produce attualmente questo output quando viene utilizzata una bitmap semplice di grandi dimensioni. Forse questo verrà corretto in una versione futura.
Il flag di traccia globale 646 può essere utilizzato per riportare informazioni sull'eliminazione del segmento abilitata dalla tabella di intervallo (o da una piccola semplice bitmap). Riporta informazioni simili al segmento elimina l'evento esteso. Tutti i flag di traccia menzionati in questa sezione non sono documentati e non sono supportati.
Pensieri finali
Le bitmap in modalità batch possono essere estremamente efficaci quando sono tipi di dati corretti (max 64 bit e tipo intero) e la bitmap può essere trasferita a una scansione columnstore, soprattutto se i dati del segmento utilizzano la compressione RLE (pura memoria) o se la bitmap può essere compilata in un'altra bitmap sui dati del dizionario.
Potrebbe essere utile se i piani di esecuzione riportassero informazioni più dettagliate sulle bitmap di hash join, almeno per dire quale tipo di bitmap è stato creato. Così com'è, abbiamo solo il Bitmap Creator proprietà e alcuni eventi estesi con cui lavorare. Ciò rende l'analisi dettagliata del piano un po' più difficile di quanto dovrebbe essere, dati gli enormi guadagni in termini di prestazioni che possono essere realizzati sfruttando tutte le ottimizzazioni intelligenti integrate nel motore di esecuzione per i dati columnstore e gli hash join in modalità batch.
Demo, illustrazioni e ulteriori discussioni sui punti principali discussi in questo articolo sono disponibili sul mio sito personale in Batch Mode Bitmap Demos.
