von Markus Winand.

Ein genauer Blick auf die Index Include-Klausel


Einige Datenbanken, nämlich Microsoft SQL Server, IBM Db2 und PostgreSQL (seit Version 11), unterstützen eine Include-Klausel bei der Create Index-Anweisung. Die Einführung dieser Klausel bei PostgreSQL ist auch der Anlass für diesen längst überfälligen Artikel über die Include-Klausel.

Bevor es an die Details geht, möchte ich noch eine kurze Wiederholung über die allgemeine Funktion von (non-clustered) B-Tree Indizes und dem allmächtigen Index-Only-Scan machen.

Inhalt:

  1. Wiederholung: B-Tree Indizes
  2. Wiederholung: Index-Only-Scan
  3. Die Include-Klausel
  4. Filter auf Include-Spalten
  5. Unique-Indizes mit Include-Klausel
  6. Compatibility
  7. PostgreSQL: Kein Filter vor der Sichtbarkeitsprüfung

Wiederholung: B-Tree Indizes

Um die Include-Klausel zu verstehen, muss man zuerst wissen, dass die Nutzung eines Indexes mit der Verwendung von Datenstrukturen auf bis zu drei Ebenen einhergeht.

  • Der B-Baum

  • Die doppelt verkettete Liste auf der untersten Ebene des B-Baumes

  • Die Tabelle

Die ersten beiden Strukturen bilden zusammen einen Index und könnten demzufolge in einem Punkt „B-Tree Index“ zusammengefasst werden. Ich bevorzuge jedoch die getrennte Darstellung, da diese Strukturen verschiedene Funktionen erfüllen und die Performance unterschiedlich beeinflussen. Darüber hinaus erfordert die Erklärung der Include-Klausel diese Trennung.

Tabellendaten...Tabellendaten...KEYKEYKEYKEYTabelleIndexDoppeltverkettete Liste

Im allgemeinen Fall beginnt die Datenbanksoftware damit den B-Baum abzusteigen, um den ersten passenden Eintrag in der doppelt verketteten Liste zu finden (1). Danach wird die doppelt verkettete Liste verfolgt, bis alle passenden Einträge gefunden wurden (2). Zuletzt werden die entsprechenden Einträge aus der Tabelle geladen (3). Die beiden letzten Schritte können auch verschränkt ablaufen – das ist für das Verständnis des allgemeinen Konzeptes aber nicht relevant.

Tabellendaten...Tabellendaten...KEYKEYKEYKEYTabelleIndexDoppeltverkettete Liste

Die folgenden Formeln geben ein grobes Gefühl dafür, wie viele Leseoperationen bei jedem dieser Schritte durchgeführt werden. Der Gesamtaufwand eines Indexzugriffes ist die Summe dieser drei Komponenten.0

  • Der B-Baum: log100(<Zeilen in Tabelle>) — meist weniger als 5.

  • Die doppelt verkettete Liste: <Zeilen, die aus dem Index gelesen werden> / 100.

  • Die Tabelle: <Zeilen, die aus der Tabelle gelesen werden>.1

Wenn man nur wenige Zeilen lädt, trägt der B-Baum meist den größten Teil zum Gesamtaufwand bei. Sobald man aber auch nur eine Hand voll Zeilen aus der Tabelle lädt, übernimmt der Tabellenzugriff die Führung. In beiden Fällen – wenige oder viele Zeilen – ist der Beitrag der doppelt verketteten Liste in der Regel gering, weil Einträge mit ähnlichen Werten in der doppelt verketteten Liste nebeneinander liegen, sodass mit einem Lesezugriff 100 oder noch mehr Zeilen auf einmal geladen werden können. Die Formel berücksichtigt das mit einem entsprechenden Divisor.2

Beachte

Wenn du jetzt denkst „deswegen haben wir Clustered Indizes“, lies bitte meinen Artikel Unsinnige Defaults: Primärschlüssel als Clusterschlüssel.

Die allgemeinste Idee der Optimierung ist, dasselbe Ergebnis mit weniger Aufwand zu erreichen. Bei Indexzugriffen bedeutet das, dass die Datenbanksoftware den Zugriff auf eine Datenstruktur unterlässt, wenn sie keine Daten von dort benötigt.3

Lies mehr über den Aufbau und die Funktion von B-Tree Indizes in Kapitel 1, „Anatomie eines SQL Indexes von SQL Performance Explained.

Wiederholung: Index-Only-Scan

Der Index-Only-Scan macht genau das: er unterlässt den Zugriff auf die Tabelle, wenn die benötigten Daten auch in der doppelt verketteten Liste des Indexes stehen.

Der folgende Index und die Abfrage darunter – aus Index-Only-Scan – sind ein Beispiel dafür.

CREATE INDEX idx
    ON sales
     ( subsidiary_id, eur_value )
SELECT SUM(eur_value)
  FROM sales
 WHERE subsidiary_id = ?

Auf den ersten Blick könnte man sich fragen, warum die Spalte eur_value überhaupt im Index ist – schließlich kommt sie nicht in der Where-Klausel vor.

B-Tree Indizes helfen vielen Klauseln

Es ist ein weit verbreiteter Irrglaube, dass Indizes nur der Where-Klausel helfen.

B-Tree Indizes können auch den order by, group by, select und anderen Klauseln helfen. Es ist lediglich die B-Baum-Struktur des Indexes, nicht die doppelt verkettete Liste, die nur von der Where-Klausel genutzt werden kann.

Der wichtige Punkt ist, dass der B-tree Index alle Spalten beinhaltet, die die Abfrage benötigt – die Datenbanksoftware muss daher nicht auf die Tabelle selbst zugreifen. Diese Technik wird als Index-Only-Scan bezeichnet.

Tabellendaten...Tabellendaten...KEYKEYKEYKEYTabelleIndexDoppeltverkettete Liste

Wenn man die Formeln von oben anwendet stellt sich heraus, dass der Vorteil sehr gering ist, wenn die Where-Klausel nur wenige Zeilen trifft. Trifft sie jedoch viele Zeilen – z. B. Millionen –, kann die Anzahl der notwendigen Leseoperationen im Wesentlichen auf ein Hundertstel reduziert werden.

Beachte

Es ist nicht selten, dass ein Index-Only-Scan eine Abfrage um ein oder zwei Größenordnungen beschleunigt.

Das Beispiel nutzt die Tatsache, dass die doppelt verkettete Liste – das sind die Blattknoten das B-Baumes – die Spalte eur_value beinhaltet. Obwohl die anderen Knoten des B-Baumens diese Spalte auch beinhalten, hat diese Information für diese Abfrage dort keinen Nutzen.

Die Include-Klausel

Die Include-Klausel erlaubt uns zu unterscheiden, welche Spalten wir im ganzen Index benötigen (Schlüsselspalten) und welche wir nur in der doppelt verketteten Liste brauchen (Include-Spalten). Anders ausgedrückt kann man damit Spalten aus den Nicht-Blattknoten entfernen, wenn man sie dort nicht braucht.

Mit der Include-Klausel kann man den Index für diese Abfrage verfeinern:

CREATE INDEX idx
    ON sales ( subsidiary_id )
     INCLUDE ( eur_value )

Da die Abfrage diesen Index noch immer mit einem Index-Only-Scan nutzen kann, bleibt die Geschwindigkeit im Wesentlichen unverändert.

KEYKEYKEYKEYINCLUDEINCLUDEINCLUDEINCLUDEKEYKEYKEYKEYKEYKEYKEYKEYKEYKEYKEYTabellendaten...Tabellendaten...TabelleIndexDoppeltverkettete Liste

Neben den in der Abbildung offensichtlichen Änderungen gibt es auch einen sehr subtilen Unterschied: die Reihenfolge der Einträge in der doppelt verketteten Liste berücksichtigt die Include-Spalten nicht. Der Index ist ausschließlich nach seinen Schlüsselspalten sortiert.4 Daraus ergeben sich zwei Konsequenzen: Include-Spalten können keine Sortierung ersetzten und werden bei der Prüfung der Eindeutigkeit (unique) nicht berücksichtigt (siehe Unten).

“Covering Index”

Der Ausdruck „Covering Index“ tritt oft im Zusammenhang mit Index-Only-Scans oder der Include-Klausel auf. Da der Begriff oft mit verschiedenen Bedeutungen verwendet wird, vermeide ich Ihn.

Entscheidend ist, ob eine bestimmte Abfrage einen bestimmten Index für einem Index-Only-Scan nutzen kann. Ob dieser Index eine Include-Klausel hat oder alle Tabellenspalten beinhaltet, ist irrelevant.

Im Vergleich zum ursprünglichen Index hat die neue Definition mit der Include-Klausel einige Vorteile:

  • Der B-Baum könnte weniger Ebenen haben (<~40%)

    Da die Knoten über der doppelt verketteten Liste die Spalten aus der Include-Klausel nicht beinhalten, kann die Datenbank mehr Verzweigungen pro Block abbilden sodass ein flacherer Baum entstehen könnte.

  • Der Index ist geringfügig kleiner (<~3%)

    Da die Nicht-Blattknoten die Include-Spalten nicht speichern, ist der Index insgesamt natürlich auch ein wenig kleiner. Da die Blattknoten jedoch den Großteil des Indexes ausmachen, ist dieser Effekt sehr klein.

  • Der Grund für diese Spalten im Index ist dokumentiert

    Das ist mit Sicherheit der unterschätzteste Vorteil der Include-Klausel: In der Indexdefinition selbst ist ersichtlich, wofür diese Spalten benutzt werden.

Den letzten Punkt möchte ich genauer erläutern.

Wenn man einen bestehenden Index erweitert, ist es sehr hilfreich zu wissen, warum der Index aktuell so definiert ist, wie er es eben ist. Aus diesem Wissen ergeben sich die Freiheiten, die man bei der Änderung hat, ohne andere Abfragen negativ zu beeinflussen.

Die folgende Abfrage erläutert das.

SELECT *
  FROM sales
 WHERE subsidiary_id = ?
 ORDER BY ts DESC
 FETCH FIRST 1 ROW ONLY

Die Abfrage liefert für eine gegebene Filiale – wie zuvor – den letzten Verkauf zurück (die Spalte ts steht für time stamp).

Ein Index mit den Schlüsselspalten (subsidiary_id, ts) wäre für diese Abfrage ideal. Damit könnte die Datenbanksoftware direkt zum letzten Eintrag für die Filiale navigieren und diesen direkt zurückliefern. Dafür müssen nicht alle Einträge für diese Filiale gelesen oder sortiert werden, da die doppelt verkettetet Liste nach dem Indexschlüssel sortiert ist, und der Eintrag mit dem größten Ts-Wert jeweils als letztes pro subsidiary_id gespeichert ist. Mit diesem Ablauf ist die Abfrage im Wesentlichen so schnell wie ein Primärschlüsselzugriff. Siehe ORDER BY indizieren und Top-N-Zeilen abfragen für weitere Details zu dieser Technik.

Gratis Sticker

Nur für kurze Zeit: Use The Index, Luke! Sticker flattern gratis zu dir nach Hause. Einfach die Lieferadresse hier im Formular angeben. Kaffeetassen sind auch reduziert!

Bevor man jedoch einen neuen Index für diese Abfrage anlegt, sollte man unbedingt prüfen, ob ein bestehender Index so geändert werden kann, dass er diesen Zugriffsweg unterstützt. Einen neuen Index anlegen hat nämlich einen deutlich größeren Einfluss auf den Wartungsaufwand als das Erweitern eines bestehenden Indexes. Dabei muss man natürlich sicherstellen, dass die Änderung keine negativen Auswirkungen auf andere Abfragen hat.

Wenn man sich dazu die aktuelle Indexdefinition ansieht, steht man vor einem Problem:

CREATE INDEX idx
    ON sales
     ( subsidiary_id, eur_value )

Wenn dieser Index die Order By-Klausel der oberen Abfrage unterstützen soll, müsste man die Spalte ts zwischen den beiden bestehenden Indexspalten einfügen:

CREATE INDEX idx
    ON sales
     ( subsidiary_id, ts, eur_value )

Das würde den Index für Abfragen, die die eur_value Spalte an zweiter Stelle benötigen weniger nützlich machen – das ist der Fall, wenn eur_value in der Where- oder Order By-Klausel verwendet wird. Wenn man nicht weiß, ob es solche Abfragen gibt, birgt diese Änderung ein enormes Risiko, andere Abfragen negativ zu beeinflussen. Im Zweifel ist es meist das Beste, den bestehenden Index unverändert zu belassen und für die neue Abfrage einen eigenen Index anzulegen.

Wenn man beim Versuch einen bestehenden Index zu erweitern jedoch auf den folgenden Index stößt, ergibt sich ein völlig anderes Bild.

CREATE INDEX idx
    ON sales ( subsidiary_id )
     INCLUDE ( eur_value )

Da die Spalte eur_value in der Include-Klausel ist, ist sie nur in den Blattknoten vorhanden und kann daher weder für Indexsuchen – wohl aber zum filtern – noch zum Sortieren herangezogen werden. Eine weitere Spalte an das Ende des Schlüssels anzuhängen ist eine relativ sichere Option.

CREATE INDEX idx
    ON sales ( subsidiary_id, ts )
     INCLUDE ( eur_value )

Obwohl noch immer ein Restrisiko besteht, dass andere Abfragen unter dieser Änderung leiden, ist es dieses Restrisiko meist wert ist eingegangen zu werden.5

Für die Evolution des Indexdesigns ist es daher wichtig, Spalten in die Include-Klausel zu legen, wenn man sie nur in der doppelt verketteten Liste braucht. Spalten, die man für einen Index-Only-Scan in den Index aufnimmt, sind das wichtigste Beispiel.

Filter auf Include-Spalten

Bisher haben wir die Include-Klausel nur für Index-Only-Scans genutzt. Es gibt aber noch andere Fälle, in denen es genügt eine Spalte in die doppelt verkettete Liste eines Indexes aufzunehmen.

SELECT *
  FROM sales
 WHERE subsidiary_id = ?
   AND notes LIKE '%search term%'

Bei diesem Beispiel habe ich den Suchwert ausnahmsweise als Literal direkt in den SQL-Text geschrieben, damit man die Wildcardzeichen sieht. In einem Programm würde man natürlich Bindparamter verwenden.

Wie würde ein guter Index für diese Abfrage aussehen? Natürlich muss die Spalte subsidiary_id an erster Stelle stehen. Im letzten Index von Oben ist diese Anforderung bereits erfüllt.

CREATE INDEX idx
    ON sales ( subsidiary_id, ts )
     INCLUDE ( eur_value )

Bei der Ausführung der Abfrage mit diesem Index kommen alle drei eingangs beschienenen Schritte zur Anwendung: (1) zuerst wird der B-Baum genutzt, um den ersten Eintrag für die gesuchte Filiale zu finden; (2) danach wir die doppelt verkettete Liste verfolgt, bis alle Einträge gefunden wurden; (3) zuletzt werden die entsprechenden Zeilen aus der Tabelle geladen, der Like-Filter auf die Spalte notes angewendet und die verbleibenden Zeilen ausgegeben.

Das Problem ist der letzte Schritt dieses Ablaufes: beim Tabellenzugriff werden Zeilen geladen, ohne zu wissen ob diese Zeilen für das Endergebnis benötigt werden. Letztendlich hat der Tabellenzugriff den größten Einfluss auf die Gesamtperformance, wenn mehr als ganz wenige Zeilen geladen werden. Den Tabellenzugriff für Zeilen durchzuführen, die nicht abgefragt wurden, ist eine riesige Performancesünde.

Wichtig

Vermeide es, Zeilen zu laden, die das Endergebnis nicht beeinflussen.

Die Herausforderung bei dieser Abfrage ist die Infix-Suche mit Like. B-tree Indizes unterstützen das Suchen mit führendem Wildcard-Zeichen nicht. Was B-tree Indizes sehr wohl unterstützten ist das Filtern mit solchen Like-Mustern. Beachte die Hervorhebung: Suchen vs. Filtern.

Wenn die Spalte notes also in der doppelt verketteten Liste ist, kann die Datenbanksoftware den Like-Filter prüfen bevor der Tabellenzugriff erfolgt (nicht PostgreSQL: siehe Unten). Das erspart den Tabellenzugriff bei Zeilen, die dem Muster nicht entsprechen. Wenn die Tabelle noch weitere Spalten hat, wird für passende Zeilen trotzdem ein Tabellenzugriff durchgeführt, um die diese Spalten zu laden.

CREATE INDEX idx
    ON sales ( subsidiary_id, ts )
     INCLUDE ( eur_value, notes )

Obwohl dieser Ablauf kein Index-Only-Scan ist, kann die Performance nahe an die eines Index-Only-Scans kommen, wenn das Like-Muster nur von wenigen Zeilen erfüllt wird. Um umgekehrten Fall, wenn das Like-Muster auf alle Zeilen passt, kann die Abfrage etwas langsamer werden, weil die doppelt verkettete Liste länger ist. Der Punkt, an dem die Vorteile überwiegen ist jedoch einfach zu erreichen: für eine bessere Gesamtperformance ist es oft ausreichend, wenn der Like-Filter nur wenige Prozent der Zeilen verwirft. Im Detail hängt das von der Größe der betroffenen Spalten ab.

Unique-Indizes mit Include-Klausel

Zu guter Letzt gibt es noch einen völlig anderen Aspekt der Include-Klausel: Unique-Indexes mit Include-Klausel berücksichtigen für die Eindeutigkeit nur die Schlüsselspalten.

Damit kann man zusätzliche Spalten in Unique-Indizes aufnehmen, ohne das Eindeutigkeitskriterium zu verändern.

CREATE UNIQUE INDEX …
    ON … ( id )
 INCLUDE ( payload )

Dieser Index verhindert doppelte Werte in der Spalte Id,6 unterstützt für die folgende Abfrage aber dennoch einen Index-Only-Scan:

SELECT payload
  FROM …
 WHERE id = ?

Für dieses Verhalten braucht man nicht unbedingt die Include-Klausel: Wenn die Datenbanksoftware zwischen Unique Constraints und Unique Indizes unterscheidet, benötigt man für einen Unique Constraint lediglich einen Index, der die Unique-Spalten am Beginn des Schlüssels hat. Weitere Spalten sind kein Problem.

Bei der Oracle-Datenbank ist die entsprechende Syntax wie folgt:

CREATE INDEX …
    ON … ( id, payload )
ALTER TABLE … ADD UNIQUE ( id )
      USING INDEX …

Compatibility

PostgreSQL: Kein Filter vor der Sichtbarkeitsprüfung

Die PostgreSQL-Datenbank hat bei der Anwendung von Filtern auf Indexebene eine Einschränkung. Kurz gesagt werden auf Indexebene außer in wenigen Fällen keine Filter angewendet. Bei diesen wenigen Fällen funktioniert das Filtern jedoch nur, wenn die entsprechenden Spalten Teil des Indexschlüssels sind – nicht also, wenn die Spalten in der Include-Klausel stehen. Das heißt, dass das verschieben einer Schlüsselspalte in die Include-Klausel auch dann negative Folgen haben kann, wenn die Spalte dort aufgrund der oben beschriebenen Logik noch immer zum Filtern genutzt werden könnte.

Um die Hintergründe dieser Einschränkung zu verstehen, muss man etwas weiter ausholen. Es beginnt damit, dass PostgreSQL alte Zeilenversionen in der Tabelle selbst aufbewahrt, bis sie für keine Transaktion mehr sichtbar und sie der Vacuum-Prozess zu einem späteren Zeitpunkt aus der Tabelle löscht.

Um zu wissen, ob eine bestimmte Zeilenversion für eine Transaktion sichtbar ist, hat jede Tabelle zwei Systemspalten, die anzeigen wann die Zeilenversion erzeugt und gelöscht wurde: xmin und xmax. Nur wenn die aktuelle Transaktion in diesen xmin/xmax-Bereich fällt, ist die Zeilenversion sichtbar.7

Leider sind die xmin/xmax-Werte nicht im Index gespeichert.8

Wenn PostgreSQL sich einen Indexeintrag ansieht, kann es noch nicht wissen ob dieser Eintrag für die aktuelle Transaktion sichtbar ist oder nicht. Der Eintrag könnte bereits gelöscht sein, oder er noch nicht committed. Um herauszufinden, ob dieser Eintrag sichtbar ist, lädt PostgreSQL normalerweise die xmin/xmax-Werte aus der Tabelle und prüft dann die Sichtbarkeit.

Daraus folgt, dass es in PostgreSQL eigentlich keinen Index-Only-Scan gibt. Egal wie viele Spalten man in den Index packt, PostgreSQL muss immer noch in die Tabelle sehen, um die Sichtbarkeit zu prüfen.

Dennoch gibt es in PostgreSQL eine Index Only Scan-Operation. Aber auch diese muss die Sichtbarkeit durch einen Zugriff auf Daten außerhalb des Indexes prüfen. Anstatt direkt in die Tabelle zu gehen, prüft der PostgreSQL Index Only Scan zuerst die sogenannte Visibility Map. Da diese Datenstruktur sehr dicht ist, kann die Prüfung der Sichtbarkeit mit weniger Lesezugriffen beantwortet werden – das ist zumindest die Idee. Die Visibility Map kann jedoch nicht immer eine definitive Antwort geben: entweder bestätigt die Visibility Map, dass eine Zeile sichtbar ist, oder sie kann keine Aussage über die Sichtbarkeit abgeben. Im zweiten Fall muss selbst die Index Only Scan-Operation noch auf die Tabelle zugreifen, um xmin und xmax zu laden (“Heap Fetches” in explain analyze).

Nach diesem Sichtbarkeitsexkurs können wir uns nun wieder dem Filtern auf Indexebene zuwenden.

SQL erlaubt auch in der Where-Klausel beliebig komplexe Ausdrücke. Solche Ausdrücke können natürlich auch Laufzeitfehler, wie z. B. “division by zero”, verursachen. Wenn PostgreSQL solche Ausdrücke auflöst, bevor die Sichtbarkeit bestätigt ist, könnten also Laufzeitfehler aufgrund von Daten auftreten, die für die Abfrage nicht sichtbar sind. Um das zu vermeiden prüft PostgreSQL die Sichtbarkeit grundsätzlich bevor solche Filter angewendet werden.

Für diese grundsätzliche Regel gibt es jedoch eine Ausnahme. Da die Sichtbarkeit nicht während der Suche im Index geprüft werden kann, müssen Operatoren, die für Indexsuchen verwendet werden können, immer sicher zu benutzen sein. Das sind also jene Operatoren, die in den entsprechenden Operatorklasse definiert sind. Wenn eine einfache Filterung einen solchen Operator benutzt, kann PostgreSQL diese Filter anwenden, ohne zuvor die Sichtbarkeit zu prüfen, da die Verwendung dieses Operators als sicher gilt. Die Krux dabei ist, dass nur die Schlüsselspalten eine zugeordnete Operatorklasse haben. Spalten in der Include-Klausel haben keine – Filter auf diesen Spalten können nicht angewendet werden, bevor die Sichtbarkeit bestätigt ist. Das ist zumindest mein Verständnis einer Diskussion auf der PostgreSQL Hackers Mailingliste.

Zur Demonstration können wir das vorherige Beispiel verwenden.

CREATE INDEX idx
    ON sales ( subsidiary_id, ts )
     INCLUDE ( eur_value, notes )
SELECT *
  FROM sales
 WHERE subsidiary_id = ?
   AND notes LIKE '%search term%'

Dabei könnte der folgende, verkürzt dargestellte Ausführungsplan erzeugt werden:

                     QUERY PLAN
----------------------------------------------
Index Scan using idx on sales (actual rows=16)
  Index Cond: (subsidiary_id = 1)
  Filter: (notes ~~ '%search term%')
  Rows Removed by Filter: 240
  Buffers: shared hit=54

Die Like-Bedingung wird in Filter, nicht in Index Cond angezeigt. Das Bedeutet, dass diese Bedingung auf Tabellenebene angewendet wurde. Die Zahl der Lesezugriffe (shared hits) ist für 16 Zeilen auch verdächtig hoch.

Bei einem Bitmap Index/Heap Scan wird dieses Phänomen noch deutlicher:

                       QUERY PLAN
-----------------------------------------------
Bitmap Heap Scan on sales (actual rows=16)
  Recheck Cond: (idsubsidiary_id= 1)
  Filter: (notes ~~ '%search term%')
  Rows Removed by Filter: 240
  Heap Blocks: exact=52
  Buffers: shared hit=54
  -> Bitmap Index Scan on idx (actual rows=256)
       Index Cond: (subsidiary_id = 1)
       Buffers: shared hit=2

Der Bitmap Index Scan erwähnt die Like-Bedingung überhaupt nicht. Stattdessen liefert er 256 Zeilen, weit mehr als die 16, die die Where-Klausel erfüllen.

Beachte, dass das in diesem Fall keine Besonderheit der Include-Klausel ist. Wenn man die Include-Spalten in den Schlüssel verschiebt, erhält man dasselbe Ergebnis.

CREATE INDEX idx
    ON sales ( subsidiary_id, ts, eur_value, notes)
                        QUERY PLAN
-----------------------------------------------
Bitmap Heap Scan on sales (actual rows=16)
  Recheck Cond: (subsidiary_id = 1)
  Filter: (notes ~~ '%search term%')
  Rows Removed by Filter: 240
  Heap Blocks: exact=52
  Buffers: shared hit=54
  -> Bitmap Index Scan on idx (actual rows=256)
       Index Cond: (subsidiary_id = 1)
       Buffers: shared hit=2

Das liegt daran, dass der Like-Operator nicht Teil der Operatorklasse ist und daher nicht als sicher angesehen wird.

Verwendet man eine Operation aus der Operatorklasse, wie zum Beispiel Ist-Gleich, verändert sich das Verhalten.

SELECT *
  FROM sales
 WHERE subsidiary_id = ?
   AND notes = 'search term'

Diesmal berücksichtigt der Bitmap Index Scan alle Bedingungen und liefert nur 16 Zeilen an den Tabellenzugriff.

                QUERY PLAN
----------------------------------------------
Bitmap Heap Scan on sales (actual rows=16)
  Recheck Cond: (subsidiary_id = 1
             AND notes = 'search term')
  Heap Blocks: exact=16
  Buffers: shared hit=18
  -> Bitmap Index Scan on idx (actual rows=16)
       Index Cond: (subsidiary_id = 1 
                AND notes = 'search term')
       Buffers: shared hit=2

Beachte jedoch, dass dieses Verhalten nur mit Schlüsselspalten erreicht werden kann. Wenn man die Spalte notes wieder in die Include-Klausel verschiebt, hat sie keine Operatorklasse mehr, sodass der Ist-Gleich-Operator nicht mehr als sicher angesehen wird und die Bedingung erst nach der Sichtbarkeitsprüfung auf Tabellenebene angewendet wird.

                     QUERY PLAN
-----------------------------------------------
Bitmap Heap Scan on sales (actual rows=16)
  Recheck Cond: (id = 1)
  Filter: (notes = 'search term')
  Rows Removed by Filter: 240
  Heap Blocks: exact=52
  Buffers: shared hit=54
  -> Bitmap Index Scan on idx (actual rows=256)
       Index Cond: (id = 1)
       Buffers: shared hit=2

Über den Autor

Foto von Markus Winand

Markus Winand ist der SQL Renaissance Botschafter auf der Mission, Entwickler auf die Evolution von SQL im 21. Jahrhundert aufmerksam zu machen. Markus kann als Trainer, Sprecher und Berater auf winand.at engagiert werden.

Sein Buch bei Amazon kaufen

Titelbild von „SQL Performance Explained“: Eichhörnchen läuft durchs Grass

Die Essenz: SQL-Tuning auf 200 Seiten

Bei Amazon kaufen
(Taschenbuch)

Taschenbuch und PDF auch auf Markus' Webseite erhältlich.

Sein Training

Markus verwandelt veraltetes SQL-92-Wissen in solides und zeitgemäßes SQL-Know-how

Erfahren Sie mehr»

Fußnoten

0

Unter der Annahme, dass in jeden Indexblock 100 Einträge passen.

1

Das entspricht dem schlimmsten Fall, wenn jede Zeile in einem anderen Block liegt—d. h. der schlechteste Clustering Factor.

2

Die doppelt verkettete Liste kann dennoch zum limitierenden Faktor werden: z. B. bei einem Index-Only-Scan oder, allgemeiner ausgedrückt, wenn deutlich weniger Zeilen aus der Tabelle als aus der doppelt verketteten Liste geladen werden.

3

Der INDEX FAST FULL SCAN der Oracle-Datenbank ist ein extremes Beispiel: dabei wird nur eine Struktur, die Blattknoten des B-Baumes, teilweise genutzt. Die Tatsache, dass die Blattknoten eine doppelt verkettete Liste bilden ist dabei irrelevant. Ich wundere mich dennoch, warum die Oracle Datenbank den FAST FULL INDEX SCAN nur als Index-Only-Scan nutzt.

4

Der Grund dafür ist einfach: Beim Einfügen einer neuen Zeile unterstützt der B-Baum nur die Suche nach dem Schlüsselwert. Selbst wenn die Einträge in der doppelt verketteten Liste sortiert wären, gäbe es keinen direkten Weg an die Stelle, wo die neue Zeile einzufügen ist.

5

Das Restrisiko ist im Wesentlichen der Clustering Factor – insbesondere bei der Oracle-Datenbank. Siehe Automatisch optimierter Clustering-Faktor. Ein weiteres Risiko ist die Länge der doppelt verketteten Liste.

6

Außer doppelte Null-Werte, welche von Unique-Constraints angenommen werden. Siehe Null in Unique Constraints auf modern-sql.com.

7

Diese Darstellung ist natürlich vereinfacht: Liest “How Postgres Makes Transactions Atomic” um zu erfahren, wie Snapshots in PostgreSQL funktionieren.

8

Es ist verlockend, xmin und xmax in die Include-Klausel aufzunehmen, das führt jedoch lediglich zur Fehlermeldung “index creation on system columns is not supported”. Für die Wartung von xmax im Index müssen alle Indizes bei jeder Update- oder Delete-Anweisung aktualisiert werden.

„Use The Index, Luke!“ von Markus Winand ist unter einer Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License lizenziert.
Impressum | Kontakt | KEINE GEWÄHR | Handelsmarken | Datenschutz und DSGVO | CC-BY-NC-ND 3.0 Lizenz