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.

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.

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.

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.

Doch obwohl die Row-Values-Syntax im Standard definiert wird, un­ter­stüt­zen sie nur wenige Datenbanken. SQL Server 2017 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.

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

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

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

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.