Es ist die wahrscheinlich häufigste Frage zur Indizierung überhaupt: Ist es besser, einen Index pro Spalte anzulegen oder einen Index über alle Spalten einer where-Klausel? In den meisten Fällen ist die Antwort sehr einfach: Ein Index über mehrere Spalten ist besser.„Zusammengesetzte Schlüssel“ erklärt mehrspaltige Indizes im Detail.
Es gibt aber Abfragen, die ein einzelner Index nicht optimal unterstützen kann – egal, wie man den Index definiert. Das sind Abfragen mit zwei oder mehr unabhängigen Bereichsbedingungen wie im folgenden Beispiel:
SELECT first_name, last_name, date_of_birth
FROM employees
WHERE UPPER(last_name) < ?
AND date_of_birth < ?Es gibt keinen B-Tree-Index, mit dem die Abfrage ohne Filterprädikat ausgeführt werden kann. Dazu muss man sich nur vor Augen führen, dass ein Index eine verkette Liste ist.
Definiert man den Index als UPPER(LAST_NAME), DATE_OF_BIRTH (in dieser Reihenfolge), beginnt die Liste mit A und endet bei Z. Das Geburtsdatum wird nur berücksichtigt, wenn ein Name mehrfach vorkommt. Dreht man die Indexdefinition um, stehen die ältesten Mitarbeiter am Anfang, die jüngsten am Ende. In diesem Fall haben die Namen die untergeordnete Rolle.
Man kann die Indexdefinition drehen und wenden, wie man will. Die Einträge werden immer entlang einer Kette angeordnet. Am einen Ende stehen die kleinen Einträge, am anderen die großen. Daher kann ein Index nur eine Bereichsbedingung als Zugriffsprädikat unterstützen. Um zwei unabhängige Bereichsbedingungen zu unterstützen, braucht man zwei Achsen. Wie bei einem Schachbrett, zum Beispiel. Dann würde die Abfrage von oben die Einträge einer Ecke betreffen. Ein B-Tree-Index ist aber nicht wie ein Schachbrett – er ist wie eine Kette. Es gibt keine Ecke.
Hinweis in eigener Sache
Ich lebe von SQL-Schulungen, SQL-Tuning und Beratung sowie dem Verkauf meines Buches „SQL Performance Explained“. Mehr auf winand.at.
Natürlich kann man das Filterprädikat in Kauf nehmen und trotzdem einen mehrspaltigen Index benutzen. Das wird in den meisten Fällen auch die beste Lösung sein. Dann sollte die selektivere Spalte zuerst in der Indexdefinition stehen, damit sie für das Zugriffsprädikat genutzt werden kann. Hier könnte der Mythos der „selektivsten Spalte zuerst“ seinen Ursprung haben. Die Regel gilt aber nur, wenn ein Filterprädikat ohnehin unvermeidlich ist.
Die andere Option ist, zwei unabhängige Indizes zu verwenden. Einen für jede Spalte. Dann muss die Datenbank beide Indizes durchsuchen und die Ergebnisse kombinieren. Alleine die doppelte Indexsuche ist schon ein erhöhter Aufwand, weil zwei Indexbäume durchwandert werden müssen. Darüber hinaus ist das Kombinieren der Zwischenergebnisse sehr CPU- und speicherintensiv.
Beachte
Ein Indexzugriff ist schneller als zwei.
Zum Kombinieren mehrerer Indexzugriffe werden zwei Methoden verwendet. Das ist einerseits der Index-Join. Kapitel 4, „Die Join-Operation“, erklärt die entsprechenden Algorithmen. Bei der zweiten Methode bedient man sich einer Funktion aus dem Data-Warehouse-Bereich.
Das Data-Warehouse ist die Mutter aller Ad-hoc-Abfragen. Mit wenigen Klicks kann man beliebige Bedingungen kombinieren. Es ist unmöglich, vorherzusagen, welche Spaltenkombinationen in der where-Klausel auftreten werden. Das macht das Indizieren, wie es bisher beschrieben wurde, weitgehend unmöglich.
Daher gibt es für den Data-Warehouse-Bereich einen speziellen Index-Typen: den sogenannten Bitmap-Index. Die Stärke von Bitmap-Indizes ist, dass sie verhältnismäßig einfach kombiniert werden können. Das heißt, dass man passable Performance erhält, wenn man jede Spalte einzeln indiziert. Dennoch sind Bitmap-Indizes unterlegen, wenn man die Abfrage kennt und einen mehrspaltigen B-Tree-Index dafür anlegen kann.
Die größte Schwäche der Bitmap-Indizes ist die katastrophale insert-, update- und delete-Performance. Parallele Schreiboperationen sind de facto unmöglich. Das ist in einem Data-Warehouse kein großes Problem, da die Ladeprozesse koordiniert werden können. Bei Online-Applikationen sind Bitmap-Indizes aber kaum einsetzbar.
Wichtig
Bitmap-Indizes sind für Online-Transaktionsverarbeitung (OLTP) kaum einsetzbar.
Viele Datenbanken bieten eine Hybrid-Lösung zwischen B-Tree- und Bitmap-Index an. In Ermangelung einer besseren Lösung können sie die Ergebnisse mehrerer B-Tree-Suchen zur Ausführungszeit in Bitmap-Strukturen umwandeln. Diese können dann effizient kombiniert werden. Da die Bitmap-Strukturen dafür nicht gespeichert werden, wird das Problem der schlechten Schreib-Performance umgangen. Stattdessen benötigt diese Operation sehr viel Speicher- und CPU-Ressourcen. Alles in allem kann man diese Methode durchaus als „Verzweiflungstat“ bezeichnen.
