Vor einiger Zeit habe ich mich beruflich einem alten Codesegment gewidmet, da die Ausführungszeiten mit etwa 120 Minuten viel zu hoch waren. Einige Analysen und Optimierungen später lief das Codesegment dann in etwa 5 Minuten durch. Grund: Self-Joins wurden konsequent eliminiert, da die Datenbank durch die mehreren Milliarden Datensätze komplett in die Knie gezwungen wurde.

Da ich die Beispiele hier natürlich nicht am Original zeigen kann, habe ich ein ähnliches Szenario mit Telefondaten aufbereitet. Die Test-Tabelle hat 1.464.730 Zeilen und besteht aus folgenden Spalten:

  • call_id (primary key, eindeutige ID für jeden Anruf)
  • line_id (auf welcher Warteschlange kam der Anruf rein)
  • employee_id
  • call_start_time
  • call_end_time

Die Anrufe folgen einer einfachen Nummerierung nach Zeitpunkt des Eingangs, unabhängig vom Mitarbeiter. Die Aufgabenstellung lautet nun, für jeden Mitarbeiter die jeweils nächste call_id und call_start_time zu ermitteln, damit im Nachgang die Zeit zwischen einzelnen Anrufen gemessen werden kann.

Das fragliche Codeelement verwendete für ein solches Szenario einen Self-Join mit min()-Funktion, also angewendet auf das Anruf-Beispiel folgendes:

select
    a.call_id
  , a.employee_id
  , min(b.call_id) as next_call_id
  , a.call_end_time
  , min(b.call_start_time) as next_call_start_time
from calls a
inner join calls b on
  a.employee_id = b.employee_id
where b.call_start_time >= a.call_end_time
group by
    a.call_id
  , a.employee_id
  , a.line_id
  , a.call_end_time
;

Mit meinen 1464730 Zeilen komme ich bei dieser Abfrage auf etwa 90 Sekunden Ausführungszeit. Die Hauptkosten entfallen dabei – Überraschung – auf den Join.

Ausführungsplan mit min()

Der Trick ist nun, den Self-Join zu entfernen und das geht ganz wunderbar mit den Funktionen lag() und lead(). Ich möchte an dieser Stelle kein umfangreiches Tutorial schreiben, denn die Artikel der MSDN sind wirklich gut, von daher nur die Schlüsselfakten. lag() und lead() sind Funktionen, die in das Resultset greifen und aus einer anderen Zeile ein Ergebnis ziehen. Sie sind nicht deterministisch, heißt Abfragen müssen so geschrieben werden, dass das Ergebnis nur eindeutig sein kann (z.B. indem partition by und order by korrekt gewählt werden).

Verwendet man nun für das Anruf-Beispiel die lead()-Funktion, sieht die Abfrage folgendermaßen aus:

select
    a.call_id
  , a.employee_id
  , lead(a.call_id,1) over (partition by employee_id order by call_id asc) as [next_call_id]
  , a.call_end_time
  , lead(a.call_start_time,1) over (partition by employee_id order by call_id asc) as next_call_start_time
from calls a
;

Durch die gleiche over()-Klausel wird sichergestellt, dass beide lead()-Funktionen auch das Ergebnis aus der gleichen Zeile nehmen. Da die call_id eindeutig ist, besteht nicht die Gefahr einer Mehrdeutigkeit.

Die Ausführungszeit dieser Variante beträgt nur noch 8 Sekunden. Netter Nebeneffekt ist übrigens, dass es bei fehlendem nächsten Anruf einfach ein NULL in der entsprechenden Zelle gibt, welches man dann filtern kann oder auch nicht.

Ausführungsplan mit lead()

Insgesamt also eine sehr kleine Änderung mit sehr großer Auswirkung. Der größte Aufwand entfällt bei dieser Lösung auf die Sortierung, heißt hier kann noch mal optimiert werden.

Als nächstes habe ich also einen Covering-Index erstellt, der sämtliche Spalten der Abfrage beinhaltet. Wichtig ist hierbei die Reihenfolge der Index-Sortierung. Da in der Abfrage nach der employee_id partitioniert wird, muss die Reihenfolge im Index folgendermaßen aussehen:

  • employee_id (Partitionierung zuerst)
  • call_id (Dann Sortierkriterium innerhalb der Partition)
  • call_start_time
  • call_end_time

Der daraus resultierende Abfrageplan sieht nunmehr folgendermaßen aus:

Ausführungsplan mit lead() und verbessertem Index

Die Abfrage kann direkt auf den Index zugreifen und benötigt lediglich dessen B-Baum, wodurch rechenintensive Operationen vermieden werden. Bei meiner Zeilananzahl war kein relevanter Unterschied bei der Ausführungszeit mehr festzustellen, aber im Hinterkopf sollte man doch immer das Original haben, das mit den Milliarden von Datensätzen.