Grohrock.consulting

Excel, Datenbanken und mehr

Kategorie: Datenbank

lag() und lead() – weg mit den Self-Joins

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.

rank() versus row_number()

Immer wieder kommt es vor, dass innerhalb von SQL-Anweisungen Duplikate herausgefiltert werden müssen; beispielsweise wenn Daten mit einem gewissen Zeitfenster auch rückwirkend geladen werden (immer die letzten 2 Tage). Theoretisch sollten das mit einem simplen distinct zu lösen sein, allerdings nicht immer und auch nicht fehlerfrei. Was passiert zum Beispiel, wenn die Daten in einem Staging Layer mit Zeitstempel versehen werden und sich in diesem SL die Daten von zwei oder mehr Ladeprozessen kumulieren? Was passiert, wenn fehlerhafte Daten kommen? Prominente Möglichkeiten, solche Duplikate zu filtern sind rank() oder row_number(), aber welche Lösung ist besser und welche schlechter?

Gehen wir von folgendem Beispiel aus:

create table #test (col1 int, col2 varchar(10), datum date);

insert into #test values (342,'Queue_ABC','2016-11-20');
insert into #test values (342,'Queue_JKL','2016-11-20');
insert into #test values (23,'Queue_DEF','2016-11-21');
insert into #test values (23,'Queue_GHI','2016-11-20');

An zwei Tagen wurden Daten in ein Staging Layer geladen und nun soll daraus der Operational Data Store gefüllt werden. Möglichkeit eins, wir erstellen mit rank() eine Rangfolge der Daten und filtern uns dann den höchsten Rang heraus.

select
 col1
 ,col2
 ,datum
 ,rank() over (partition by col1 order by datum desc) as rang
from #test
;

Das Ergebnis:

col1 col2 datum rang
23 Queue_DEF 21.11.2016 1
23 Queue_GHI 20.11.2016 2
342 Queue_ABC 20.11.2016 1
342 Queue_JKL 20.11.2016 1

Wie man sieht, hat das Vorgehen beim Wert 23 funktioniert, aber beim Wert 342 werden wir auch jetzt Duplikate erzeugen, wenn wir mit where rang=1 selektieren. Es spielt hierbei keine Rolle, ob so etwas auch im Normalfall passieren kann oder ob es sich hier einfach um einen Datenfehler handelt. Fakt ist, dass dadurch unter Umständen zu Problemen mit Restriktionen kommen kann. Eine Möglichkeit, dieser Herausforderung zu begegnen ist die Verwendung von row_number() statt rank(), also folgendermaßen:

select
 col1
 ,col2
 ,datum
 ,row_number() over (partition by col1 order by datum desc) as rang
from #test
;

Das Ergebnis:

col1 col2 datum rang
23 Queue_DEF 21.11.2016 1
23 Queue_GHI 20.11.2016 2
342 Queue_ABC 20.11.2016 1
342 Queue_JKL 20.11.2016 2

Nun haben wir tatsächlich nur noch einen einzigen Datensatz mit rang=1 pro Wert in col1. Wichtig hierbei ist, dass weder rank() noch row_number() deterministisch sind. Heißt das für die Wertekombination col1=342 und rang=1 kann das Ergebnis in col2 bei jeder Abfrage variieren.

So ganz rosa ist die Welt natürlich nicht, denn während wir so unseren ODS vor Duplikaten schützen, müssen wir damit leben, dass in so einem Fall die Datenbank für uns bestimmt, welcher Wert im Endeffekt geladen wird.

Reverse-Engineering mit dem SAP PowerDesigner – Spalten mit hoher Kardinalität

Irgendwo zwischen lustig und peinlich rangiert meines Erachtens folgende Problematik. Mit Hilfe des SAP PowerDesigners soll aus einer Datenbank ein Modell erstellt werden und eigentlich klappt auch alles ganz gut, bis auf einmal folgende Fehlermeldung erscheint:

value X out of range for destination

Wobei X einen ziemlich hohen Wert einnimmt. Die Tabelle wird dabei nicht mehr vollständig geladen, heißt man hat zu wenige Spalten im Modell. Was nun?

Zielführend war hier das manuelle Ausführen der Abfrage, die man im PowerDesigner unter „Database > Edit current DBMS“ findet, indem man zur Option „Script\Objects\Column\SqlListQuery“ navigiert. Beim Betrachten der Spalte „coln“ wurde auch schnell klar, woran der Fehler liegt. Die Kardinalität der Problemspalte lag bei etwa 2,8 Milliarden, also jenseits der Grenze eines Signed-Int-Feldes und von daher der Fehler.

Abhilfe schafft hier das Auskommentieren der entsprechenden Abfragesegmente (Vorsicht mit Kommata, aus diesem Grund habe ich es auf dem Bild in die nächste Zeile gerückt und dort auskommentiert):

value X out of range for destination

Vorsicht allerdings, denn ich kann nicht garantieren, dass dadurch alle Funktionen bei der Datenmodellierung erhalten bleiben. Sollte man z. B. über den PowerDesigner einen Index erstellen wollen, kann ich mir gut vorstellen, dass es hier zu Problemen kommt. Für das reine Reverse-Engineering allerdings funktioniert die Methode wunderbar.

Läuft mit WordPress & Theme erstellt von Anders Norén