ASC, DESC und NULLS FIRST/LAST indizieren


Gilt für
DB2Ja
MySQLNein
OracleJa
PostgreSQLJa
SQL ServerJa

Datenbanken können einen Index in beide Richtungen lesen. Das heißt, dass ein pipelined order by auch funktioniert, wenn die Indexreihenfolge im durchsuchten Indexbereich das genaue Gegenteil der order by-Klausel ist. Dennoch kann die Verwendung von ASC und DESC dazu führen, dass ein Index nicht mehr für ein pipelined order by verwendet werden kann. Aber auch dafür gibt es eine Lösung.

Im folgenden Beispiel wird ein Index in umgekehrter Richtung genutzt. Die Abfrage liefert alle Verkäufe seit gestern, aufgelistet nach fallendem Datum und fallender PRODUCT_ID:

SELECT sale_date, product_id, quantity
  FROM sales
 WHERE sale_date >= TRUNC(sysdate) - INTERVAL '1' DAY
 ORDER BY sale_date DESC, product_id DESC

Der Ausführungsplan zeigt, dass der Index in fallender Richtung gelesen wird.

DB2
Explain Plan
---------------------------------------------------------------------
ID | Operation                      |                     Rows | Cost
 1 | RETURN                         |                          |  688
 2 |  FETCH SALES                   |     394 of 394 (100.00%) |  688
 3 |   IXSCAN (REVERSE) SALES_DT_PR | 394 of 1009326 (   .04%) |   24

Predicate Information
 3 - STOP ((CURRENT DATE - 1 DAYS) <= Q1.SALE_DATE)

In der DB2-Datenbank können umgekehrte Index-Zugriffe durch die DISALLOW REVERSE SCAN-Klausel bei der Indexerstellung unterbunden werden.

Oracle
---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |  320 |  300 |
| 1 | TABLE ACCESS BY INDEX ROWID | SALES       |  320 |  300 |
|*2 |  INDEX RANGE SCAN DESCENDING| SALES_DT_PR |  320 |    4 |
---------------------------------------------------------------

Die Datenbank kann den Indexbaum also auch nutzen, um den letzten passenden Eintrag zu finden. Ausgehend davon wird die Blattknoten-Liste, wie in Abbildung 6.2 dargestellt, nach „oben“ verfolgt. Dafür sind die Blattknoten schließlich durch eine doppelt verkettete Liste verbunden.

Wichtig

Ein Index kann in beide Richtungen gelesen werden.

Abbildung 6.2. Rückwärts gelesener Index


Dafür ist jedoch entscheidend, dass die Indexreihenfolge im durchsuchten Indexbereich der order by-Klausel exakt entgegengesetzt ist.

Im nächsten Beispiel trifft diese Voraussetzung nicht zu, da die ASC- und DESC-Spezifikationen in der order by-Klausel gemischt werden.

SELECT sale_date, product_id, quantity
  FROM sales
 WHERE sale_date >= TRUNC(sysdate) - INTERVAL '1' DAY
 ORDER BY sale_date ASC, product_id DESC

Die Abfrage muss zuerst die Verkäufe von gestern, nach PRODUCT_ID ab­stei­gend sortiert, liefern. Dann erst die Heutigen – wieder mit fallender PRODUCT_ID. Dieser Vorgang ist in Abbildung 6.3 dargestellt. Um die Daten in der gewünschten Reihenfolge zu erhalten, müsste die Daten­bank beim Lesen des Indexes einen Sprung machen.

Abbildung 6.3. Unmögliches pipelined order by


Der Index enthält allerdings keinen entsprechenden Verweis, aus dem er­kenn­bar wäre, wo weitergelesen werden muss. Die Datenbank kann diesen Index daher nicht benutzen, um eine explizite Sortierung zu vermeiden.

Bei unseren Schlulungs-, Tuning-, und
Literaturangeboten ist für jeden was dabei

Die meisten Datenbanken bieten daher die Möglichkeit, die Indexreihen­folge an die order by-Klausel anzupassen. Konkret heißt das, dass die Indexdefinition ebenfalls ASC- und DESC-Spezifikationen enthalten kann:

  DROP INDEX sales_dt_pr;
CREATE INDEX sales_dt_pr
    ON sales (sale_date ASC, product_id DESC);

Damit entspricht die order by-Klausel wieder der Indexreihenfolge, sodass die Sortierung entfallen kann:

DB2
Explain Plan
-----------------------------------------------------------
ID | Operation            |                     Rows | Cost
 1 | RETURN               |                          |  675
 2 |  FETCH SALES         |     387 of 387 (100.00%) |  675
 3 |   IXSCAN SALES_DT_PR | 387 of 1009326 (   .04%) |   24

Predicate Information
 3 - START ((CURRENT DATE - 1 DAYS) <= Q1.SALE_DATE)
Oracle
---------------------------------------------------------------
|Id | Operation                   | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT            |             |  320 |  301 |
| 1 |  TABLE ACCESS BY INDEX ROWID| SALES       |  320 |  301 |
|*2 |   INDEX RANGE SCAN          | SALES_DT_PR |  320 |    4 |
---------------------------------------------------------------

Die neue Indexreihenfolge ist in Abbildung 6.4 dargestellt. Die geänderte Sortierung der zweiten Spalten dreht die Pfeile aus der vorherigen Abbil­dung quasi um. Dadurch fällt das Ende des ersten Pfeiles mit dem Anfang des zweiten zusammen, sodass der Index auch ohne „Sprung“ die gewünschte Reihenfolge liefert.

Wichtig

Wenn die order by-Klausel ASC- und DESC-Spezifikationen mischt, muss der Index ebenso definiert werden, um ein pipelined order by zu ermöglichen.

Dadurch wird die Benutzbarkeit des Indexes für die where-Klausel nicht beeinträchtigt.

Abbildung 6.4. Gegenläufig sortierter Index


Da ein Index ohnehin in beide Richtungen gelesen werden kann, macht ASC/DESC-Indizierung nur Sinn, wenn einzelne Spalten gegenläufig sortiert werden. Einzig Sekundär-Indizes auf Index-organisierte Tabellen können eine Ausnahme darstellen. Diese nehmen den Clustering-Key automatisch in den Index auf, ohne dass man die Möglichkeit hat, die Sortierreihenfolge selbst zu bestimmen. Falls man also ausgerechnet den Clustering Key ab­fallend sortieren muss, bleibt einem nichts anderes übrig, als alle anderen Spalten abfallend zu sortieren. Um die gewünschte Reihenfolge zu erhalten, muss der Index dann rückwärts gelesen werden.

Neben ASC und DESC sieht der SQL-Standard noch einen weiteren Zusatz zur order by-Klausel vor: NULLS LAST oder NULLS FIRST. Diese Möglichkeit, die Einordnung von NULL direkt zu steuern, wurde erst mit SQL:2003 als optionale Erweiterung in den Standard aufgenommen. Dementsprechend spärlich ist die Unterstützung der Datenbanken. Das ist insbesondere bedenklich, da der SQL-Standard die Sortierreihenfolge von NULL nicht fest­legt. Es ist nur definiert, dass sämtliche NULL-Einträge durch eine Sortierung zusammengelegt werden, nicht aber, ob sie vor oder nach allen anderen Einträgen eingeordnet werden. Daher müsste man die NULL-Sortierung streng genommen für alle „nullbaren“ Spalten in der order by-Klausel explizit angeben, um ein konsistentes Ergebnis zu erhalten.

Fakt ist aber, dass weder SQL Server 2012, noch MySQL 5.6 diese Erweiterung umsetzen. Die Oracle Datenbank unterstützte die NULLS-Sortierung zwar schon, bevor sie in den SQL-Standard aufgenommen wurde, akzeptiert sie jedoch in der aktuellen Version 11g noch immer nicht in der Indexdefinition. Daher kann eine Oracle Datenbank eine order by-Klausel mit NULLS FIRST nicht als pipelined order by durchführen. Einzig die PostgreSQL Datenbank unterstützt die NULLS-Sortierung seit Version 8.3 sowohl in der order by-Klausel als auch in der Indexdefinition.

Die folgende Übersicht fasst die Möglichkeiten verschiedener Datenbanken nochmal zusammen.

Wenn dir gefällt, wie ich die Dinge erkläre, wirst du meine Kurse lieben.

Abbildung 6.5. Datenbank/Funktions-Matrix


Über den Autor

Photo of Markus Winand
Markus Winand stimmt Entwickler auf SQL-Performance ein. Er hat das Buch SQL Performance Explained veröffentlicht und bietet inhouse Schulungen sowie Tuning-Leistungen auf http://winand.at/ an.