Bitmaps in Microsoft SQL Server 2000

  • Artikel

Veröffentlicht: 15. Dez 2001 | Aktualisiert: 15. Jun 2004

Zusammenfassung: Microsoft SQL Server verwendet seit Version 7.0 interne Bitmaps, um die Abfrageausführung zu beschleunigen. Angesichts der Einführung neuer Operatoren in SQL Server 2000 können jetzt weitere Verfahren zur Bitmapfilterung eingesetzt werden, um für große Datasets noch schnellere Abfrageergebnisse zu erzielen.

* * *

Auf dieser Seite

Einführung Einführung
SQL Server 7.0 SQL Server 7.0
SQL Server 2000 SQL Server 2000
Schlussfolgerung Schlussfolgerung

Einführung

In diesem Artikel wird zunächst die Verwendung von Bitmaps für die Abfrageoptimierung in Microsoft SQL Server 7.0 beschrieben. Anschließend wird die erweiterte Anwendung in SQL Server 2000™ erläutert.

 

SQL Server 7.0

Microsoft SQL Server 7.0 verwendet Bitmaps im Hintergrund in allen Hashverknüpfungen. Eine Hashverknüpfung umfasst Erstellungs- und Testphasen. In der Erstellungsphase werden alle Verbindungsschlüssel in einer der verknüpften Tabellen (diese wird auch als äußere Tabelle bezeichnet) per Hash in eine Hashtabelle übertragen. Bei diesem Hashalgorithmus erstellt SQL Server nebenbei eine separate Bitmap, in der "0" für "kein Schlüsselwert in der äußeren Tabelle wird per Hash in dieses Bit übertragen" steht und "1" bedeutet, dass "einer oder mehrere Schlüsselwerte in der äußeren Tabelle per Hash in dieses Bit übertragen werden".

Die Größe der Bitmap wird während der Abfrageoptimierung festgelegt und hängt davon ab, wie viele eindeutige Werte in der äußeren Tabelle erwartet werden. Sobald für alle Zeilen in der äußeren Tabelle ein Hashalgorithmus ausgeführt wurde, enthält die Bitmap Nullen und Einsen. Dann wird jeder Schlüssel in der Testtabelle (diese wird auch als innere Tabelle bezeichnet) unter Verwendung desselben Hashalgorithmus übertragen, der auch für die äußeren Schlüssel verwendet wird.

Vor dem Überprüfen und Durchsuchen der Hashtabelle aus der Erstellungsphase wird zunächst die Bitmap überprüft. Wenn der entsprechende Eintrag den Wert "0" enthält, kann die Zeile keine Übereinstimmung in der äußeren Tabelle haben und wird daher entfernt.

Da das Testen der Bitmap wesentlich weniger kostenaufwendig ist als das Durchsuchen der Hashtabelle, werden Zeilen in der inneren Tabelle, die keinen Verknüpfungsdatensatz erstellen, wesentlich schneller verarbeitet als ohne die Bitmap. Die Bitmaps werden automatisch erstellt und sind in der Showplanausgabe nicht sichtbar, da sie einen integralen Bestandteil von Hashverknüpfungen darstellen.

 

SQL Server 2000

Microsoft SQL Server 2000 verwendet ähnliche Bitmaps äußerst effizient - nicht nur in Hashverknüpfungen, sondern auch außerhalb von Verknüpfungsoperatoren, um Zeilen zu löschen, deren Schlüsselwerte keine Verknüpfungsdatensätze erzeugen können. Die Showplanausgabe umfasst einen Bitmap Create-Operator für die Erstellung der Bitmaps. Diese Bitmaps werden während der Abfrageoptimierung automatisch in die Abfragepläne eingefügt. Im Folgenden sehen Sie ein Beispiel für eine Abfrage, die einen Plan mit solchen Bitmaps verwendet:

SELECT  S_NAME,   S_ADDRESS ,S_PHONE ,S_COMMENT ,PS_PARTKEY  
   FROM    SUPPLIER ,PARTSUPP 
   WHERE   S_SUPPKEY = PS_SUPPKEY AND  
PS_PARTKEY between 5000 AND 5999

Diese Abfrage wählt alle Lieferanten aus der Tabelle SUPPLIER aus, die Teile der 5000er-Serie (Teilschlüssel zwischen 5000 und 5999) produzieren. Neben der Tabelle SUPPLIER verwenden wir außerdem die Tabelle PARTSUPP (Teilelieferanten), die für jedes Teil so viele Datensätze enthält, wie es unterschiedliche Lieferanten gibt, die das gleiche Teil herstellen. In Abbildung 1 sehen Sie nachfolgend den grafischen Showplan, der von SQL Server 2000 erstellt wurde.

Bild01

Abbildung 1. Ausführungsplan für Beispielabfrage

Die Bitmap wird vor der Hashverknüpfung an der äußeren Eingabeseite der Verknüpfung für jeden Datenstrom erstellt. Wenn der oben abgebildete grafische Showplan von rechts nach links und von oben nach unten gelesen wird, ist der Scan der Tabelle PARTSUPP parallel. Der folgende Austauschoperator (Parallelism/Repartition Streams) verteilt die Zeilen anschließend unter Verwendung der Schlüsselwerte, so dass sie sich vor der parallelen Hashübereinstimmung (Verknüpfung) in übereinstimmenden Datenströmen mit den neu verteilten Zeilen der Tabelle SUPPLIER befinden. Der oberste Zweig wird zuerst ausgeführt, und bis zur Auffüllung der Hashtabelle in der Hashverknüpfung erfolgen im unteren Zweig keine Aktivitäten.

Wenn die Tabelle SUPPLIER gescannt wird, haben wir die Bitmaps im oberen Zweig bereits unter Verwendung der PARTSUPP-Schlüssel (die Spalte PS_SUPPKEY in dieser Abfrage) erstellt. Für jeden Datenstrom, der in die Hashverknüpfung eintritt, gibt es eine Bitmap. Wenn die SUPPLIER-Zeilen direkt nach dem Scan in den Austauschoperator eintreten, entscheiden wir zunächst, in welchen Datenstrom sie eintreten sollten. Anschließend wird die Zeile entfernt, falls die Bitmap für diesen Datenstrom in dem Eintrag, der dem Schlüsselwert (der Spalte S_SUPPKEY) entspricht, den Wert "0" aufweist. Die irrelevanten Zeilen werden somit noch vor ihrer Platzierung im eigentlichen Ausgabedatenstrom für den Austausch entfernt.

SQL Server 2000 verwendet diese Bitmaps nur in parallelen Abfrageplänen. Dies ist darauf zurückzuführen, dass bei Verwendung des Austauschoperators keine zusätzliche Ersparnis neben den Bitmaps in den Hashverknüpfungen erfolgt. Abgesehen von dem oben genannten Szenario mit Hashverknüpfungen verwendet SQL Server 2000 Bitmaps auch für Mergeverknüpfungen, doch auch hier nur in parallelen Plänen und nur, wenn im äußeren Zweig ein SORT-Operator vorhanden ist. Der SORT-Operator veranlasst SQL Server, alle äußeren Zeilen vor den Zeilen aus der inneren Tabelle zu verarbeiten, und ermöglicht uns daher das Erstellen der Bitmap. Ohne einen SORT-Operator im äußeren Zweig werden die Zeilen der äußeren und inneren Tabellen der Mergeverknüpfung simultan verarbeitet, so dass die Verwendung von Bitmaps nicht möglich ist.

Testergebnisse zeigen eine erhöhte Geschwindigkeit

Im Allgemeinen hängt die Leistungssteigerung durch die Bitmapweitergabe davon ab, wie viele Zeilen herausgefiltert werden. Da diese Zahl variieren kann, kann die Leistungssteigerung zwischen "kaum messbar" und "ganz erheblich" liegen, je nachdem, wie aufwendig die anderen bei der Abfrageausführung verwendeten Operatoren sind.

Abbildung 2 veranschaulicht die Geschwindigkeitssteigerungen, die beim Testen von drei komplexen Abfragen für große Datenbanken (Tabellen: 134 GB, Indizes: 45 GB) gemessen wurden. Die Tests wurden in unserem Labor unter Verwendung eines 8-Wege-Computers mit 550 MHz und 4 GB RAM ausgeführt.

  • Abfrage A ist eine Verknüpfung von drei Tabellen (die größte enthält mehr als 100 GB an Daten) mit einer Aggregation und Sortierung des Ergebnisses.

  • Abfrage B ist eine Abfrage mit einer korrelierten Unterabfrage.

  • Abfrage C ist eine Verknüpfung von sechs Tabellen mit einer Aggregation zusätzlich zur Verknüpfung.

Bild02

Abbildung 2. Bitmapfilterung optimiert komplexe Abfragen bei drei großen Datenbanken

 

Schlussfolgerung

Die Verwendung von Bitmaps bei der Abfrageoptimierung ist eines der vielen Verfahren, die von SQL Server 2000 angewendet werden, um die schnellsten Ergebnisse für große Datasets (z.B. in Unternehmensdatenbanken) zu liefern. Durch eine Verringerung der Anzahl der zu verarbeitenden Zeilen werden Abfragen für innere und äußere Verknüpfungen effizienter, Daten werden schnell zurückgegeben, und die Serververarbeitung wird minimiert.