Durch Ergebnisse blättern


Wenn das Anzeigen der ersten Seite mit einer pipelined Top-N-Abfrage effizient umgesetzt wurde, ergibt sich meist die Anforderung, die nächsten Seiten bei Bedarf nachzuladen. Dabei liegt die Herausforderung darin, die Ergebnisse der vorherigen Seiten zu überspringen. Man kann ihr mit zwei Methoden begegnen: Der Offset-Methode, die alle Zeilen von Anfang an nummeriert und jene ausschließt, die vor der gewünschten Seite liegen. Oder der Seek-Methode, die den letzten Eintrag der vorherigen Seite sucht und nur die darauffolgenden Einträge liefert.

Die folgenden Beispiele zeigen die weiter verbreitete Offset-Methode. Ihr Vorteil liegt in der einfachen Handhabung – vor allem bei Datenbanken, die ein eigenes Schlüsselwort dafür anbieten (offset). Mit der fetch first-Erweiterung wurde dieses Schlüsselwort sogar in den SQL-Standard aufge­nommen.

DB2

DB2 unterstützt das offset-Schlüsselwort des SQL-Standards nicht. Die einzig standard-konforme Alternative ist die ROW_NUMBER() Window-Function (siehe nächster Abschnitt). Dann gibt es noch zwei weitere Möglichkeiten, die beide nicht zu empfehlen sind: (1) unter Verwendung von db2set DB2_COMPATIBILITY_VECTOR=MYS auf limit und offset zurückgreifen – leider lässt sich offset dann nicht mit fetch first kombinieren; (2) unter Verwendung von auf die Oralcle ROWNUM Pseudo-Spalte zurückgreifen (siehe Oracle-Beispiel).

MySQL

MySQL und PostgreSQL verwenden die offset-Klausel, um die ersten Zeilen einer Top-N-Abfrage zu verwerfen. Die limit-Klausel wird erst danach angewendet.

SELECT *
  FROM sales
 ORDER BY sale_date DESC
 LIMIT 10 OFFSET 10
Oracle

Die Oracle Datenbank stellt die Pseudo-Spalte ROWNUM zur Verfügung, mit der jede Zeile nummeriert wird. Man kann auf ROWNUM aber keinen Größer-gleich(>=)-Filter anwenden. Dafür muss man den ROWNUM-Wert zuerst „materialisieren“, indem man ihn mit einem Alias umbenennt.

SELECT *
  FROM ( SELECT tmp.*, rownum rn
           FROM ( SELECT *
                    FROM sales
                   ORDER BY sale_date DESC
                ) tmp
          WHERE rownum <= 20
       )
 WHERE rn > 10

Beachte die Verwendung des Spalten-Alias RN für den unteren Grenz­wert und ROWNUM für den oberen.

PostgreSQL

Die fetch first-Erweiterung definiert auch eine offset ... rows-Klau­sel. PostgreSQL akzeptiert den offset-Zusatz aber nur ohne rows. Die zuvor verwendete limit/offset-Syntax (analog zu MySQL) kann aber auch noch bei aktuellen Versionen verwendet werden.

SELECT *
  FROM sales
 ORDER BY sale_date DESC
OFFSET 10
 FETCH NEXT 10 ROWS ONLY
SQL Server

Für die SQL Server TOP-Syntax gibt es keinen Zusatz, um Zeilen zu über­sprin­gen. Mit SQL Server 2012 („Denali“) wird jedoch die fetch first-Erweiterung eingeführt, wobei der offset-Zusatz zwingend anzugeben ist.

SELECT *
  FROM sales
 ORDER BY sale_date DESC
OFFSET 10 ROWS
 FETCH NEXT 10 ROWS ONLY

Ein weiterer Vorteil der Offset-Methode ist, dass man nur die Zeilen­num­mer benötigt, um eine beliebige Seite zu laden. Die Datenbank muss dafür aber alle Zeilen von Anfang an, bis zur gesuchte Seite, zählen. Abbildung 7.2 zeigt den Indexbereich, der mit dieser Methode beim Blättern bis zur vierten Seite gelesen wird.

Abbildung 7.2. Zugriff bei Offset-Methoden


Daraus ergeben sich aber auch zwei Nachteile: (1) die Seiten können sich durch das Einfügen neuer Verkäufe verschieben, da die Nummerierung bei jeder Abfrage neu durchgeführt wird; (2) die Antwortzeit steigt, je weiter man nach hinten blättert.

Die Seek-Methode vermeidet beide Probleme, da sie die Werte der vor­he­rigen Seite zur Abgrenzung verwendet. Das heißt, es werden nur Werte gesucht, die hinter dem letzten Eintrag der vorherigen Seite kommen müssen. In SQL ist das eine einfache where-Klausel. Anders ausgedrückt selektiert die Seek-Methode die Zeilen der vorherigen Seiten einfach nicht.

Das nächste Beispiel zeigt die Seek-Methode. Zur Veranschaulichung gehen wir vorerst davon aus, dass es nur einen Verkauf pro Tag gibt. Damit ist das Verkaufsdatum ein eindeutiger Schlüssel. Um alle Verkäufe zu selek­tie­ren, die im Ergebnis hinter einem bestimmten Verkauf kommen, muss man – aufgrund der abfallenden Sortierung – eine Kleiner-Bedingung (<) ver­wenden. Die fetch first-Klausel beschränkt das Ergebnis auf zehn Zeilen.

SELECT *
  FROM sales
 WHERE sale_date < ?
 ORDER BY sale_date DESC
 FETCH FIRST 10 ROWS ONLY

Anstatt einer Zeilennummer verwendet man den letzten Wert der vor­he­rigen Seite, um die Untergrenze festzulegen. Die Bedingung SALE_DATE < ? kann als Zugriffsprädikat bei einem Indexzugriff genutzt werden. Dadurch werden die Einträge der vorherigen Seiten tatsächlich übersprungen. Darüber hinaus verschieben sich die Seiten durch neue Verkäufe nicht.

Wenn es jedoch, wie in Abbildung 7.2 dargestellt, mehr als einen Verkauf pro Tag gibt, tritt ein Problem zum Vorschein: Verwendet man das letzte Datum der ersten Seite („gestern“), überspringt man alle Einträge von gestern – nicht nur die, die bereits auf der ersten Seite angezeigt wurden. Der Kern des Problems ist, dass die Sortierreihenfolge nicht eindeutig ist. Das ist jedoch die Voraussetzung dafür, dass eine einfache Kleiner- oder Größer-Bedingung den Seitenumbruch an der rich­tigen Stelle durchführen kann.

Ohne eindeutige Sortierreihenfolge ist das Ergebnis, per Definition, nicht in einer eindeutigen Reihenfolge. Der einzige Grund, warum man üblicher­weise konsistente Ergebnisse erhält, ist, dass die Datenbank die Abfrage üblicherweise auf die gleiche Weise ausführt. Die Datenbank könnte die Einträge mit dem gleichen SALE_DATE aber auch beliebig mischen. Die order by-Klausel wäre dann noch immer erfüllt. In modernen Datenbanken kann es wirklich vorkommen, dass die Reihenfolge bei jeder Ausführung anders ist. Nicht etwa, dass vorsätzlich gemischt wird, es könnte aber zu einer parallelen Ausführung kommen. Das heißt, dass derselbe Aus­füh­rungs­plan eine unterschiedliche Zeilenfolge liefern kann, da die Threads in einer „zufälligen“ Reihenfolge ablaufen.

Wichtig

Blättern erfordert eine eindeutige Sortierreihenfolge.

Selbst wenn das Pflichtenheft nur eine „Sortierung nach absteigendem Da­tum“ verlangt, muss man als Entwickler dafür sorgen, dass die order by-Klausel eine eindeutige Sortierreihenfolge festlegt. Dafür kann man grundsätzlich beliebige Spalten in die order by-Klausel aufnehmen – einfach nur, um die Sortierreihenfolge eindeutig zu machen. Wenn der Index, der für das pipelined order by genutzt wird, bereits weitere Spalten enthält, ist es ein guter Anfang diese Spalten in die order by-Klausel aufzunehmen. Dadurch kann dieser Index weiterhin für das pipelined order by genutzt werden. Wenn die Sortierreihenfolge damit noch immer nicht eindeutig ist, kann man noch beliebige eindeutige (unique) Spalten hinzufügen – dann muss man aber auch den Index dementsprechend erweitern.

Im folgende Beispiel wird daher zusätzlich mit dem Primärschlüssel sortiert und der Index entsprechend erweitert. Für eine korrekte Blätterfunktion muss man die „kommt hinter“-Logik aber auf beide Spalten gemeinsam anwenden:

CREATE INDEX sl_dtid ON sales (sale_date, sale_id);
SELECT *
  FROM sales
 WHERE (sale_date, sale_id) < (?, ?)
 ORDER BY sale_date DESC, sale_id DESC
 FETCH FIRST 10 ROWS ONLY;

Die where-Klausel nutzt die wenig bekannte Row-Values-Syntax. Damit werden mehrere Werte zu einer logischen Einheit zusammengefasst, auf die die Vergleichsoperatoren als Ganzes angewandt werden können. Wie auch bei skalaren Werten entspricht die Kleiner-Bedingung bei fallender Sortierung einem „kommt hinter“. Mehr dazu im Kasten „SQL Row Values“. Die where-Klausel fragt also nur Verkäufe ab, die hinter dem angegebenem SALE_DATE/SALE_ID-Paar kommen.

SQL Row Values

Neben einfachen, skalaren, Werten definiert der SQL-Standard auch sogenannte „row value constructors“. Das sind „gereihte An­sam­mlungen von Werten die eine Zeile oder einen Teil davon bilden“ [SQL:92, §7.1: <row value constructor>]. Syntaktisch sind „row value constructors“ eingeklammerte Listen. Man kennt und nutzt diese Syntax vor allem bei der insert-Anweisung.

Weniger bekannt ist, dass die Verwendung von „row value con­struc­tors“ auch in der where-Klausel zulässig ist. Der SQL-Standard definiert sogar sämtliche Vergleichsoperatoren dafür. Im Originalwortlaut ist der Kleiner-Operator zum Beispiel wie folgt definiert:

"Rx < Ry" is true if and only if RXi = RYi for all i < n and RXn < RYn for some n.

— SQL:92, §8.2.7.2

Wobei i und n jeweils Listenpositionen sind. Das bedeutet, dass ein Row-Value RX kleiner als RY ist, wenn ein beliebiger Wert RXn kleiner ist als der entsprechende Wert RYn und alle davor liegenden Werte-Paare gleich sind (RXi = RYi; für i<n).

Durch diese Definition ist der Ausdruck RX < RY gleichbedeutend mit RX wird vor RY einsortiert. Genau diese Bedingung braucht man für die Seek-Methode.

Doch obwohl die Row-Values-Syntax im Standard definiert wird, un­ter­stüt­zen sie nur wenige Datenbanken. SQL Server 2012 („Denali“) kennt row values überhaupt nicht. Die Oracle Datenbank kennt sie zwar, kann aber nur Gleichheits-Operatoren darauf anwenden (ORA-01796). MySQL kann row values korrekt evaluieren, benutzt sie aber beim Indexzugriff nur als Filterprädikat. PostgreSQL hingegen versteht die Syntax und kann den Index damit optimal nutzen – sofern ein passender vorhanden ist.

Trotzdem kann man eine Annäherung der Seek-Methode auch mit anderen Datenbanken umsetzen. Wenn auch nicht so elegant und effizient wie mit row values in PostgreSQL. Dazu muss man die where-Klausel mit „nor­ma­len“ Vergleichen formulieren, wie in diesem Beispiel:

SELECT *
  FROM ( SELECT *
           FROM sales
          WHERE sale_date <= ?
            AND NOT (sale_date = ? AND sale_id >= ?)
          ORDER BY sale_date DESC, sale_id DESC
       )
 WHERE rownum <= 10

Die where-Klausel besteht aus zwei Teilen. Der Erste betrachtet nur das SALE_DATE, allerdings mit einer Kleiner-gleich(<=)-Bedingung. Dieser Teil ist so einfach formuliert, dass ihn alle Datenbanken als Zugriffsprädikat nutzen können – dafür werden aber zu viele Einträge ausgewählt. Der zweite Teil entfernt die überschüssigen Ergebnisse, die bereits auf vor­he­ri­gen Seiten angezeigt wurden. „Gleichwertige Logik indizieren“ erklärt, warum die where-Klausel so formuliert wurde.

Gleichwertige Logik indizieren

Meistens kann man eine logische Bedingung auf mehrere Arten aus­drücken. Die oben verwendete Seek-Logik kann man zum Beispiel auch folgendermaßen umsetzen:

WHERE (
         (sale_date < ?)
       OR
         (sale_date = ? AND sale_id < ?)
      )

Diese Formulierung verwendet nur einschließende Ausdrücke und ist damit vielleicht sogar besser verständlich – zumindest für Men­schen. Datenbanken sehen das jedoch anders. Sie erkennen nicht, dass die where-Klausel alle Zeilen ab den angegebenen SALE_DATE und SALE_ID betrifft – vorausgesetzt der Wert für das SALE_DATE ist jeweils derselbe. Daher wird die vollständige where-Klausel nur als Filterprädikat genutzt. Man könnte zumindest erwarten, dass die Datenbank die Bedingung SALE_DATE <= ? aus den beiden Oder-Zweigen ableiten kann. Aber auch diesen Dienst verweigern sämtliche Datenbanken.

Diese redundante Bedingung kann man aber selbst in die where-Klausel aufnehmen – auch wenn das die Lesbarkeit nicht unbedingt verbessert:

WHERE sale_date <= ?
  AND (
         (sale_date < ?)
       OR
         (sale_date = ? AND sale_id < ?)
      )

Diesen Teil der where-Klausel können alle Datenbanken als Zugriffsprädikat nutzen. Die Klausel ist aber noch schwerer zu verstehen als die ursprünglich vorgestellte Variante. Bei der besteht auch nicht die Gefahr, dass der redundante („unnötige“) Teil der where-Klausel später wieder entfernt wird.

Der Ausführungsplan zeigt, dass die Datenbank den ersten Teil der where-Klausel als Zugriffsprädikat nutzt.

---------------------------------------------------------------
|Id | Operation                      | Name    |  Rows | Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT               |         |    10 |    4 |
|*1 |  COUNT STOPKEY                 |         |       |      |
| 2 |   VIEW                         |         |    10 |    4 |
| 3 |    TABLE ACCESS BY INDEX ROWID | SALES   | 50218 |    4 |
|*4 |     INDEX RANGE SCAN DESCENDING| SL_DTIT |     2 |    3 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter(ROWNUM<=10)
   4 - access("SALE_DATE"<=:SALE_DATE)
       filter("SALE_DATE"<>:SALE_DATE
           OR "SALE_ID"<TO_NUMBER(:SALE_ID))

Das Zugriffsprädikat auf SALE_DATE sorgt dafür, dass Tage, die bereits vollständig angezeigt wurden, übersprungen werden. Der zweite Teil der where-Klausel wird nur als Filterprädikat verwendet. Das heißt, dass die Datenbank zwar einige Einträge der vorherigen Seite(n) nochmals prüft, aber sofort verwirft. Abbildung 7.3 stellt die entsprechenden Zugriffswege dar.

Abbildung 7.3. Zugriff bei der Annäherung an die Seek-Methode


Abbildung 7.4 zeigt das Performanceverhalten der Offset- und Seek-Methoden im Vergleich. Anfangs genügt die Maßgenauigkeit nicht, um einen Unterschied zu erkennen. Ab Seite 20 gehen die Kurven aber deutlich auseinander.

Abbildung 7.4. Skalierung beim Laden der nächsten Seite


Aber natürlich hat auch die Seek-Methode ihre Nachteile. Das ist vor allem die deutlich kompliziertere Handhabung. Nicht nur, weil die where-Klausel sehr sorgfältig formuliert werden muss, sondern auch, weil man mit der Seek-Methode nicht zu beliebigen Seiten springen kann. Darüber hinaus muss man sämtliche Vergleichs- und Sortieroperationen „umdrehen“, wenn man zurückblättern will. Es sind aber ausgerechnet diese beiden Funktionen – Seiten überspringen und Zurückblättern –, die man beim Blättern durch unendliches Scrollen nicht benötigt.

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

Ü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.