Hintergrund
Im traditionellen Reihenmodus Ausführungsplänen kann SQL Server einen Bitmap-Operator als Teil der Durchführung einer frühen Semi-Join-Reduzierung einführen vor einem parallelen Hash oder Merge-Join. Die Bitmap wird aus der Build-Eingabe erstellt und verwendet, um Zeilen in der Sondeneingabe zu filtern, bevor sie den Join erreichen. Ich habe über row-mode geschrieben Bitmaps vor und sie werden auch in der Dokumentation behandelt.
In diesem Artikel geht es um den Batch-Modus Bitmaps, die eine ganz andere Implementierung haben. Seit dem ersten Erscheinen der Batch-Modus-Ausführungs-Engine in SQL Server 2012 wurden wesentliche Verbesserungen vorgenommen. Die hier angegebenen Details gelten für SQL Server 2017 – die zum Zeitpunkt des Schreibens aktuellste veröffentlichte Version. Funktionen, die für frühere Versionen spezifisch sind, werden im weiteren Verlauf erwähnt.
Der Abfrageoptimierer
Der einzige Join-Operator, der im Stapelmodus ausgeführt werden kann, ist Hash-Join. Der Abfrageoptimierer entscheidet, ob ein Batchmodus-Hash-Join (seriell oder parallel) eine Bitmap haben soll oder nicht. Der Optimierer bewertet die potenzielle Nützlichkeit einer Bitmap, indem er die Selektivität eines hypothetischen Semi-Joins berechnet der Hash-Join-Eingaben auf dem/den Join-Schlüssel(n).
Ein Semi-Join ist sinnvoll, da die Funktion der Bitmap-Filterung darin besteht, Zeilen von der Sondenseite zu entfernen, die auf der Build-Seite nicht vorhanden sind. Wenn die geschätzte Selektivität des Semi-Joins 0,75 beträgt oder weniger, hält es der Optimierer für sinnvoll, einen Bitmap-Filter im Stapelmodus zu verwenden. Mit anderen Worten, eine Bitmap wird angegeben, wenn die Semi-Join-Berechnung anzeigt, dass 25 % oder mehr der sondenseitigen Zeilen durch die Bitmap eliminiert würden.
Die exakte Semi-Join-Selektivität wird nur verwendet, um zu bestimmen, ob der Hash-Join eine Bitmap haben soll oder nicht. Die sondenseitige Selektivitätsschätzung (sichtbar als Effekt auf Kardinalitätsschätzungen) wird modifiziert, um die Tatsache widerzuspiegeln, dass Bitmaps im Allgemeinen nicht perfekt beim Entfernen nicht qualifizierter Zeilen sind. Dies ist insbesondere dann der Fall, wenn die Bitmap mithilfe eines Bloom-Filters implementiert wird, der falsch positive Ergebnisse erzeugen kann (prüfseitige Zeilen, die den Filter passieren, aber dennoch nicht mit der Erstellungsseite verbunden werden).
Selektivitätsrundung
Der Optimierer berücksichtigt diese Unsicherheit, indem er die Semi-Join-Selektivität auf eine Zehnerpotenz rundet. Dazu wird vor dem Runden der Basis-10-Logarithmus genommen. Beispielsweise ergibt eine Semi-Join-Selektivität von 0,316 log10 Wert geringfügig unter -0,5, der auf -1 abgerundet wird. Die resultierende sondenseitige Selektivität beträgt 10 =0,1. Im Gegensatz dazu ergibt eine Semi-Join-Selektivität von 0,317 einen log10 Wert knapp über -0,5, der auf Null gerundet wird. Die sondenseitige Selektivität ist daher 10 =1 (alle Reihen passen). Mögliche Bitmap-Selektivitäten auf der Sondenseite, die sich aus dieser Reihe von Berechnungen ergeben, sind 1, 0,1, 0,01, 0,001 und so weiter. Beachten Sie, dass eine Bitmap immer noch verwendet werden kann, wenn die geschätzte Selektivität auf 1 aufgerundet wird (alle Zeilen bestehen das Prädikat).
Operatoren und Kardinalitätsschätzungen
Es gibt kein separates Bitmap -Operator für einen Hash-Join im Stapelmodus. Stattdessen hat der Hash-Join-Operator entweder einen Bitmap Creator Eigenschaft (auf „true“ gesetzt) oder die Eigenschaft fehlt (nicht auf „false“ gesetzt). Dieser Unterschied zwischen der Ausführung im Zeilenmodus und im Stapelmodus macht es weniger einfach zu erkennen, ob eine Bitmap erstellt wird, spiegelt aber den zugrunde liegenden Prozess genauer wider:Bei der Ausführung im Zeilenmodus die Bitmap -Operator füllt die Bitmap, während Zeilen nacheinander durch sie hindurchfließen, bevor er die Hash-Join-Build-Eingabe erreicht. Mit anderen Worten, die Bitmap und die Hash-Tabelle werden gleichzeitig bei der Ausführung im Zeilenmodus erstellt. Im Batch-Modus wird die Hash-Tabelle vollständig erstellt, bevor die Bitmap erstellt wird (mehr dazu in Kürze).
Der Abfrageoptimierer trifft keine kostenbasierten Entscheidungen über die Position eines Batchmodus-Bitmap-Filters auf der Sondenseite des Hash-Joins. Es wird einfach angenommen, dass die Selektivität der Bitmap für alle untergeordneten Operatoren auf der Sondenseite gilt. In Wirklichkeit wird die Bitmap nur dann auf der Sondenseite nach unten geschoben, sobald ein einzelner endgültiger Ausführungsplan vom Optimierer ausgewählt wurde. Wenn die Bitmap nicht ganz nach unten zu einem Blattoperator verschoben werden kann, sehen Kardinalitätsschätzungen etwas seltsam aus. Dies ist ein Kompromiss, der in Zukunft verbessert werden könnte.
Die Ausführungsengine
Während der Optimierer entscheidet, ob ob eine Hash-Join-Batchmodus-Bitmap verwendet werden soll oder nicht, die Batchmodus-Ausführungsmaschine entscheidet über den Typ von Bitmap zur Laufzeit zu verwenden. Diese Entscheidung basiert auf statistischen Informationen, die während der Erstellung der Hash-Tabelle über die Verknüpfungsschlüssel auf der Erstellungsseite gesammelt wurden. Wie bereits erwähnt, erstellen Batch-Modus-Hash-Joins im Gegensatz zur Ausführung im Zeilenmodus zuerst die Hash-Tabelle vollständig, bevor ein separater Durchgang über die Hash-Tabelle durchgeführt wird, um die Bitmap zu erstellen.
Einfache Bitmaps
Es gibt zwei Haupttypen von Hash-Join-Bitmaps im Stapelmodus. Eine einfache Bitmap enthält ein Bit für jeden aus einem zusammenhängenden Bereich von buildseitigen Werten. Beispielsweise kann eine einfache Bitmap mit einem Byte angeben, ob acht zusammenhängende aufbauseitige Werte vorhanden sind oder nicht. Die Werte 0 bis einschließlich 7 können in die Bitmap kodiert werden, indem das entsprechende Bit gesetzt wird. Ein Wert von 5 würde Bit 5 setzen, das den Positionswert 2 hat. Wir könnten die Menge {1, 5, 7} als 2 + 2 + 2 =2 + 32 + 128 =162 =101000102
Eine einfache Bitmap hat den Vorteil, exakt zu speichern Informationen über die tatsächlich vorhandenen Build-seitigen Werte, auf Kosten des Speicherbedarfs, der proportional zum Bereich ist der vorhandenen Werte.
Komplexe Bitmaps
Der zweite Bitmap-Typ ist ein Bloom-Filter. Dies setzt ein oder mehrere Bits in der Bitmap-Struktur gemäß dem Ergebnis der Anwendung einer oder mehrerer Hash-Funktionen auf jeden Build-seitigen Wert. Wir testen auf Übereinstimmungen, indem wir dieselben Hash-Funktionen auf jeden probeseitigen Wert anwenden. Wenn eine der Hash-Funktionen ein nicht gesetztes Bit identifiziert, können wir sicher sein, dass der aktuelle Prüfwert nicht auf der Build-Seite erscheint.
Da es sich bei einem Bloom-Filter um eine probabilistische Struktur handelt, filtern wir möglicherweise einige Prüfwerte nicht heraus, die keine Build-seitige Übereinstimmung aufweisen (falsch positiv), aber wir werden niemals einen vorhandenen Wert herausfiltern (falsch negativ). Mit anderen Worten, ein Bloom-Filter sagt uns entweder „vielleicht eine Übereinstimmung“ oder „definitiv keine Übereinstimmung“. Die Rate der Fehlalarme kann reduziert werden, indem entweder mehr Bits pro Schlüssel (eine größere Bitmap) oder mehr Hash-Funktionen verwendet werden. Um es klar zu sagen, ein Bloom-Filter darf eine exakte Filterung erzeugen, aber möglicherweise auch nicht.
Bloom-Filter stellen eine platz- und zeiteffiziente Alternative dar, wenn eine einfache Bitmap verwendet wird ist aus Platzgründen nicht machbar. Die SQL Server-Batchmodus-Implementierung eines Bloom-Filters ist für moderne CPU-Cache-Architekturen optimiert und wird intern als komplexe Bitmap bezeichnet . Komplexe Bitmaps unterstützen seit SQL Server 2014 mehrere Verknüpfungsspalten und alle Datentypen im Batchmodus.
Bitmap-Auswahl
Ob SQL Server einen einfachen wählt oder komplex (Bloom-Filter)-Bitmap hängt vom Bereich ab von Build-seitigen Werten (aus Hash-Tabellen-Statistiken). Es gibt dort einen wichtigen Vorbehalt zum Wort „Range“, der im nächsten Abschnitt erklärt wird. In der Zwischenzeit wählt die Ausführungsmaschine den Bitmap-Typ folgendermaßen aus:
- Eine kleine einfache Bitmap wird verwendet, wenn der Wertebereich 2 (8.388.608) oder weniger beträgt. Dies ist die Anzahl der Bits in 1 MB.
- Wenn der Wertebereich größer als 2, aber kleiner oder gleich 2 (8 MB) ist, wählt die Ausführungs-Engine zwischen einer großen einfachen Bitmap und eine komplexe Bitmap indem Sie den erforderlichen Speicher für jede Option berechnen und die kleinere auswählen. Eine große einfache Bitmap kann bis zu 8 MB groß sein. Die Größe einer komplexen Bitmap hängt von der Anzahl der Bits pro Schlüssel ab, die benötigt werden, um die Daten angemessen darzustellen. Deutlichere Werte bedeuten normalerweise eine größere komplexe Bitmap.
- Wenn der Wertebereich über 2 Bit hinausgeht, eine komplexe Bitmap verwendet wird.
Über den Wertebereich
Der Bereich der oben genannten Werte basiert auf der internen Binärdatei Darstellung der Daten. Zum Beispiel smallint die Werte 128 und 255 könnten als 0x0080 dargestellt werden und 0x00FF , was einen Bereich von 0x7F ergibt (127) binäre Werte. Dieser Bereich würde gut mit einer kleinen einfachen Bitmap funktionieren.
Andererseits die datetime Werte „1900-01-01“ und „1900-01-02“ könnten in 8 Byte als 0x0000000100000000 dargestellt werden und 0x0000000200000000 (vier Bytes für Tage und vier Bytes für Ticks nach Mitternacht). Diese segmentierte Darstellung ergibt einen binären Bereich von 0x0100000000 (4.294.967.296) für diese beiden Beispielwerte, was viel zu groß ist, um in eine einfache Bitmap (sogar eine große) zu passen. Datentypen mit komplexen binären Darstellungen (z. B. Byte-Swapping) funktionieren normalerweise nicht gut mit einfachen Bitmaps.
Eine weitere Komplikation besteht darin, dass Daten im Batch-Modus normalisiert werden – in ein binäres Layout konvertiert, das gut mit vektorisierten Anweisungen funktioniert – und immer 64 Bit groß ist. Werte, die nicht in 64 Bit passen, werden „off row“ mit einem 64-Bit-Zeiger in der Zeile gespeichert. Dieses binäre Layout ist übrigens nicht dasselbe, wie es von einer T-SQL-Konvertierung in einen binären Typ gemeldet wird.
Trotzdem ist das normalisierte Layout ähnlich genug für Integer-Typen (z. B. integer und bigint ), dass einfache Bitmaps für Bereiche dieser Datentypen immer noch nützlich sind. Andere Typen mit einer ganzzahligen binären Darstellung (z. B. money und date ) sind ebenfalls geeignet.
Noch ein Beispiel:Ein Satz von integer Werte im Bereich von 1 bis 8.388.608 werden nur passen in eine 1 MB kleine einfache Bitmap, wobei ein Bit pro möglichem ganzzahligen Wert im Bereich verwendet wird. Der Bereich kann einen festen Offset haben, sodass ein ganzzahliger Bereich von 10.000.000 bis 18.388.607 auch passen würde (mit einem Offset von zehn Millionen). Beachten Sie, dass die Nummer der vorhandenen Werte spielt keine Rolle, nur der Bereich. Zwei Werte von 0 und 8.388.607 füllen den kleinen einfachen Bitmap-Bereich genauso gut wie eine Menge aller möglichen Werte zwischen diesen beiden Extremen.
Bereichstabellen
Wenn die Batchmodus-Ausführungs-Engine beschließt, eine große einfache zu erstellen Bitmap oder ein Komplex Bitmap für einen Hash-Join, es erstellt auch eine Bereichstabelle. Das tut es nicht Erstellen Sie eine Bereichstabelle für klein einfache Bitmaps.
Die Bereichstabelle ist eine 128-KB-Struktur mit fester Größe, die aus 8.192 Paaren von 8-Byte-Werten besteht, die einen (niedrigen, hohen) Wertebereich angeben, der in der Hash-Tabelle vorhanden ist. Eine Bereichstabelle kann auf jedem Datentyp erstellt werden, der mit der Stapelmodusausführung kompatibel ist. Während des Scannens der fertigen Hash-Tabelle wird jeder Datenstapel verwendet, um die Bitmap und zu füllen die Bereichstabelle.
Für jeden Wert im Stapel wird eine Hash-Funktion verwendet, um einen Bucket (Paar von Bereichswerten) in der Bereichstabelle zu lokalisieren. Wenn der Bucket derzeit nicht verwendet wird, wird der Wert sowohl in niedrigen als auch in hohen 8-Byte-Werten gespeichert. Wenn der Bucket bereits verwendet wird, wird stattdessen der nächste Bucket gefüllt (und so weiter, bis ein leerer Bucket gefunden wird).
Wenn die Range-Tabelle ein Drittel voll wird (2.730 von 8.192 Buckets verwendet), werden die verwendeten Einträge herauskopiert, der Bucket-Bereich verdoppelt, dann werden die gespeicherten Werte wie zuvor wieder eingefügt (allerdings berücksichtigt die Hash-Funktion die neue Eimergröße). Alle sich überschneidenden Buckets werden zusammengeführt, und der Verdopplungsprozess wird fortgesetzt, bis die Anzahl der verwendeten Buckets unter 2.730 fällt. Beispielsweise können zwei Buckets, die ursprünglich die „Bereiche“ (1-1) und (2-2) enthalten, nach der ersten Bereichsverdopplung zu einem einzelnen Bereichs-Bucket von (1-2) zusammengeführt werden.
Sobald alle Batches von Hash-Tabellendaten in die Bereichstabelle verarbeitet wurden, wird eine endgültige Bucket-Zusammenführung durchgeführt, dann bringt ein In-Place-Quicksort die Buckets in die Wertereihenfolge. Dies ermöglicht eine binäre Suche, um einen Range-Bucket mit einem bestimmten interessanten Wert zu lokalisieren.
Das Nettoergebnis all dieser Aktivitäten besteht darin, einen Satz von bis zu 2.730 unterschiedlichen Bereichen zu erzeugen, die die Daten in der Hash-Tabelle beschreiben (zusätzlich zu der großen einfachen oder komplexen Bitmap).
Verwendung der Bereichstabelle
Die Bereichstabelle wird verwendet, wenn ein Hash-Join-Bitmap-Filter in einen probeseitigen Columnstore-Scan-Operator verschoben wird. Jedes Columnstore-Segment verfügt über Katalogmetadaten zu den minimalen und maximalen Datenwerten, die im Segment vorhanden sind. Die Ausführungsmaschine kann diese Informationen verwenden, um die Bitmap-Bereichstabelle binär nach einer Übereinstimmung zu durchsuchen. Wenn keine Übereinstimmung gefunden wird, kann die Ausführungsmaschine das Segment vollständig überspringen.
Diese Laufzeitoptimierung tritt auch beim Vorauslesen auf, sodass die Engine sogar vermeiden kann, Segmente in den Speicher zu lesen, von denen sie weiß, dass sie durch den Bereichstabellenfilter eliminiert werden. Alle Segmente, die nicht durch die Bereichstabelle eliminiert wurden, werden immer noch unter Verwendung der Bitmap gefiltert. Diese Kombination führt dazu, dass die maximale Anzahl an Zeilen so früh wie möglich eliminiert wird.
Obwohl eine Bereichstabelle nicht für eine kleine einfache Bitmap erstellt wird, kann diese Struktur auch verwendet werden, um eine Segmenteliminierung zu erreichen, da der Wertebereich bekannt ist (einschließlich eines Offsets). Es ist so klein, dass es sich nicht lohnt, es mithilfe einer Bereichstabelle in Teilbereiche zu unterteilen.
Wenn die Bitmap nicht in einen Columnstore-Scan nach unten verschoben wird, kann sie dennoch als regulärer Batchmodusfilter ausgewertet werden, um vor dem Hash-Join eine Semi-Join-Reduzierung zu erzielen. Dies ist viel weniger effizient als das Eliminieren von Segmenten oder das Filtern während des Columnstore-Scans, aber es ist immer noch besser als das Filtern beim Hash-Join selbst.
Bitmaps und komprimierte Daten
Das Anwenden einer Hash-Join-Batchmodus-Bitmap auf Columnstore-Daten als Teil des Scans kann zu einer sehr guten Leistung führen, erfordert jedoch, dass unreine Segmentdaten dekomprimiert werden, bevor die Bitmap angewendet werden kann. Diese Dekomprimierung kann effizient mit SIMD-Anweisungen durchgeführt werden, ist aber immer noch zusätzliche Arbeit.
Mit SQL Server 2016 wurde die Möglichkeit eingeführt, eine Bitmap für allgemeine Prädikate für wörterbuchcodierte Segmentdaten zu erstellen. Das Prädikat wird anhand der Wörterbucheinträge ausgewertet, um ein neues zu erzeugen kleine Bitmap, wobei jedes gesetzte Bit einen Wörterbucheintrag anzeigt, der das Prädikat erfüllt. Das Anwenden dieser Bitmap kann extrem schnell sein, insbesondere wenn die Bitmap in ein einzelnes SIMD-Register passt. SQL Server kann immer noch SIMD verwenden, wenn die Bitmap nicht passt, aber das Sammeln von Bits aus einer In-Memory-Bitmap ist etwas weniger effizient als der In-Register-Fall.
Diese Optimierung von 2016 kann auf alle angewendet werden Prädikat, das in einen Columnstore-Scan geschoben wird, einschließlich eines Bitmap-Prädikats, das von einem Upstream-Hash-Join erstellt wurde. Um es deutlich zu machen, SQL Server nimmt die Hash-Join-Bitmap und erstellt eine neue (viel kleinere) Bitmap unter Verwendung der Wörterbucheinträge. Diese neue Bitmap wird vor der Dekomprimierung auf die Segmentdaten angewendet. Die Optimierung kann mit dem erweiterten Event column_store_expression_filter_bitmap_set überwacht werden . Wenn eine Wörterbuch-Bitmap verwendet wird, wird das Ereignismitglied filter_on_compressed_data_type Mitglied wird ausgefüllt. Normalerweise enthält diese den Wert RAWBITMAP . Eine weitere Optimierung besteht darin, die komprimierte Wörterbuch-Bitmap in einen Vergleichsfilter umzuwandeln, wenn die Wörterbuch-Bitmap einen einzelnen zusammenhängenden Wertebereich darstellt. In diesem Fall sehen Sie etwas anderes als RAWBITMAP (z. B. LTGT für einen kleiner/größer-als-Vergleich).
Erweiterte Ereignisse und Trace-Flags
Die allgemeine Möglichkeit zum Kompilieren von Pushdown-Filtern (einschließlich Bitmaps, die durch einen Batchmodus-Hash-Join generiert wurden) bei einem Columnstore-Scan in eine Bitmap kann mit dem Ablaufverfolgungsflag 9361 auf Sitzungsebene deaktiviert werden. Die spezifische Bitmap-Optimierung für komprimierte Daten kann mit Sitzung deaktiviert werden Ablaufverfolgungsflag 9362 auf -Ebene. Die Konvertierung einer Wörterbuch-Bitmap mit einem einzelnen zusammenhängenden Bereich in einen Vergleichsfilter kann mit Ablaufverfolgungsflag 9363 deaktiviert werden. Leider gibt es keine im Einzelhandel erstellten Ablaufverfolgungsflags, die Informationsmeldungen über Batchmodus-Bitmaps oder Pushdown-Filter melden Zusammenstellung.
Es gibt einige erweiterte Ereignisse, die Informationen über Hash-Join-Batchmodus-Bitmaps erzeugen. Die nützlichsten sind:
query_execution_column_store_segment_scan_startedquery_execution_column_store_segment_scan_finishedcolumn_store_expression_filter_bitmap_setcolumn_store_segment_eliminate
Wenn eine Hash-Join-Batchmodus-Bitmap in einen Columnstore-Scan nach unten geschoben wird, meldet das „gestartete“ Ereignis BITMAP_SIMPLE oder BITMAP_COMPLEX als filter_type . Es unterscheidet nicht zwischen kleinen und großen einfachen Bitmaps und gibt auch nichts über die Bereichstabelle aus. Die erweiterten Ereignismetadaten enthalten andere Werte für column_store_filter_type die BITMAP_SIMPLE_LARGE enthalten unter anderem, aber das erweiterte Ereignis erzeugt diese Ausgabe derzeit nicht, wenn eine große einfache Bitmap verwendet wird. Vielleicht wird dies in einer zukünftigen Version korrigiert.
Das globale Ablaufverfolgungsflag 646 kann verwendet werden, um Informationen über die durch die Bereichstabelle (oder eine kleine einfache Bitmap) aktivierte Segmenteliminierung zu melden. Es meldet ähnliche Informationen wie das Segment Elimination Extended Event. Alle in diesem Abschnitt erwähnten Trace-Flags sind nicht dokumentiert und werden nicht unterstützt.
Abschließende Gedanken
Bitmaps im Stapelmodus können äußerst effektiv sein, wenn die richtigen Datentypen verwendet werden (maximal 64 Bit und ganzzahlig) verwendet werden und die Bitmap auf einen Columnstore-Scan heruntergedrückt werden kann, insbesondere wenn die Segmentdaten RLE-Komprimierung (reine Speicherung) verwenden oder wenn die Bitmap auf Wörterbuchdaten in eine andere Bitmap kompiliert werden kann.
Es könnte nett sein, wenn Ausführungspläne detailliertere Informationen über Hash-Join-Bitmaps liefern würden – zumindest um zu sagen, welche Art von Bitmap erstellt wurde. So haben wir nur den Bitmap Creator -Eigenschaft und einige erweiterte Ereignisse, mit denen Sie arbeiten können. Dies macht eine detaillierte Plananalyse etwas schwieriger, als sie sein sollte, angesichts der enormen Leistungssteigerungen, die durch die Nutzung all der cleveren Optimierungen realisiert werden können, die in die Ausführungs-Engine für Columnstore-Daten und Hash-Joins im Batch-Modus integriert sind.
Demos, Illustrationen und weitere Diskussionen zu den in diesem Artikel behandelten Hauptpunkten sind auf meiner persönlichen Website unter Batch Mode Bitmap Demos verfügbar.
