Mengen-basiertes Programmieren mit SQL - im Unterschied zu prozeduralen Programmiersprachen

• » Home
• »SQL-Praxis
• » Sql als mengen-basierte Sprache

1. Theoretischer Hintergrund

Ein entscheidendes Merkmal von Sql besteht darin, daß diese Programmiersprache mengenorientiert (englisch: set-oriented mit set = Menge) arbeitet. Jeder auszuführende Codeblock (Batch per OSql, gespeicherte Prozedur, Bcp-Abfragezeichenfolge) wird in einem ersten Schritt mit einem Parser auf syntaktische Korrektheit geprüft. Das Ergebnis ist jedoch nicht direkt ausführbar. Denn greift eine Abfrage bsp. auf mehrere Tabellen zu und verknüpft per WHERE ausgewählte Zeilen in einer JOIN-Klausel, so ist nicht festgelegt, in welcher Reihenfolge auf die einzelnen Tabellen zugegriffen und welche Anordnung für einen ON-Abschnitt mit einigen Bedingungen gewählt wird. Deshalb wird in einem zweiten Schritt ein Ausführungsplan erstellt, der all diese Dinge ermittelt. Bei der Erstellung des Ausführungsplans werden die Größen der beteiligten Tabellen, eventuell vorhandene Indices und Statistiken für einzelne Spalten berücksichtigt und versucht, eine möglichst günstige Ausführung zu ermitteln. Erst dieser Ausführungsplan wird anschließend kompiliert und im Prozedurcache zur Wiederverwendung zwischengespeichert. Diese Wiederverwendbarkeit von Ausführungsplänen, damit der Wegfall einer erneuten Kompilierung, ist wesentlich für eine hohe Leistung. Dieselbe Sql-Abfrage kann folglich, im Gegensatz zu vielen anderen Programmiersprachen, gänzlich unterschiedlich kompilierten Code erzeugen - in Abhängigkeit von der Größe und Datenstruktur der Tabellen zum Zeitpunkt der Kompilierung.

Diese Logik kann ihre Stärken jedoch nur dann wirklich entfalten, wenn Zeilen nicht einzeln, sondern blockweise, als Mengen von Zeilen verarbeitet werden. Gerade der abstrakte Ansatz der Schlüsselwörter WHERE, JOIN und GROUP BY, der - typisch für eine Sprache der vierten Generation - nur festlegt, was gemacht werden soll, nicht jedoch, wie dies erfolgen soll, ermöglicht es dem internen Optimierer, die relativ günstigste Lösung für den Ausführungsplan zu finden. Erst das Fehlen gewisser Befehle / Werkzeuge, das ein unerfahrener Datenbank-Programmierer vielleicht als Manko der Sprache empfindet, erlaubt die Erstellung eines optimierten Layers, der sich als variabler Ausführungsplan zwischen den Sql-Code und die eigentliche Ausführung schiebt. Enthält die Sprache zusätzliche prozedurale Elemente wie Cursor, Variablen und Schleifen, so neigen jedoch Programmierer, die hauptsächlich mit prozeduralen Sprachen arbeiten und Sql nur selten zum Zugriff auf Datenbanken einsetzen, dazu, diese Werkzeuge solcherart im Übermaß einzusetzen, daß der Code unnötig lange zur Ausführung benötigt. Dasselbe Problem kann auftreten, falls der Sql-Dialekt (etwa mySql) zwar selbst wenige prozeduralen Elemente kennt, diese jedoch von der umgebenden Wirtssprache (hier meist PHP) bereitgestellt und genutzt werden. Die folgenden Beispiele erläutern dieses Problem näher.

2. Einleuchtend: WHERE macht man nicht per Hand

Es wird eine Teilmenge der Daten für ein Update benötigt. Also erstellt man einen Cursor und durchläuft diesen.

Declare @id int,
	@info int

Declare cs_Daten CURSOR
	LOCAL FAST_FORWARD
FOR
-- Alle Daten auswählen
Select A.Id, A.Kriterium
From [wichtige-Daten]

Open cs_Daten
Fetch Next From cs_Daten Into @id, @info

While (@@Fetch_Status = 0)
Begin
	-- zeilenweise testen
	If @info > 0
		-- aktuelle Zeile suchen
		-- und aktualisieren
		Update [wichtige-Daten]
			Set [Zusatz-Info] = @info * 35
		Where Id = @id
	-- nächste Zeile holen
	Fetch Next From cs_Daten Into @id, @info
End
Close cs_Daten
Deallocate cs_Daten

Nun ja - der folgende Befehl liefert dasselbe Ergebnis:

Update [wichtige-Daten]
	Set [Zusatz-Info] = @info * 35
Where Kriterium > 0 -- (*)

Allerdings erstellt diese Technik zum einen kein zusätzliches Recordset, zum anderen werden in einem Schritt die benötigten Zeilen ausgewählt und geändert. Wird eine analoge Lösung in PHP konstruiert, so ist der Unterschied noch augenfälliger, da zunächst für das gesamte RecordSet und anschließend für jede zu aktualisierende Zeile die Grenze zwischen Wirtssprache und Sql überschritten werden muß. Ferner kann die Where-Bedingung (*) einen vorhandenen Index über der Kriterium-Spalte nutzen, wohingegen die den Cursor erstellende Select-Anweisung zwangsweise sämtliche Zeilen verarbeitet.

Augenfällig an diesem Beispiel ist, daß, sind vom Update nur sehr wenige Zeilen relativ zur Gesamtzahl der Zeilen betroffen, viele Zeilen unnötig heraustransportiert und anschließend verworfen werden. Betrifft das Update dagegen die meisten Zeilen der Tabelle [wichtige-Daten], so muß fast jede Zeile erneut gesucht und aktualisiert werden. Die Leistung ist also in allen Extremfällen schlecht.

3. Rang-Positionen korrigieren

Das obige Beispiel mag noch selbstverständlich erscheinen, da bei allen Update-Erläuterungen darauf verwiesen wird, daß zusätzliche Where-Einschränkungen genutzt werden können. Interessanter ist deshalb ein Beispiel, das Berechnungen in bezug auf die vorhandenen Zeilen benötigt.

Gegeben sei eine Tabelle <Rangliste>, die bsp. Sportler oder Bücher umfaßt, eine Spalte stellt die Rangposition der Zeile dar. Bei Sportlern mag man an eine Position nach Leistung, bei Büchern an die Position nach Verkaufszahlen denken. Nun scheiden Sportler aus (Wegzug, Doping, Ende der Karriere) oder nicht mehr lieferbare Bücher sollen aus der Liste entfernt werden. Die Primärschlüssel und Rangpositionen der zu entfernenden Zeilen mögen in der Tabelle [zu-entfernen] gesammelt sein. Die Rangpositionen der verbleibenden Einträge sind zu korrigieren.

Beispiel: Tabelle zu Beginn:

Id	Name	Rang
1055	Müller	1
7138	Schmidt	2
916	Mustermann (*)	3
3024	Keller	4
6211	Musterfrau (*)	5
4809	Schneider	6

Die beiden mit (*) gekennzeichneten Einträge sollen entfernt werden, so daß als Ergebnis gewünscht wird:

Id	Name	Rang
1055	Müller	1
7138	Schmidt	2
3024	Keller	3
4809	Schneider	4

3.1 Erste Lösung: Cursorbasiert mit Rangberechnung pro Zeile

Die erste Lösung könnte wie folgt aussehen:

Declare @id int,
	@Rang int

Declare cs_Rangliste Cursor
	Local Fast_Forward
For
Select A.Id, A.Rang From Rangliste

Open cs_Rangliste

Fetch Next From cs_Rangliste Into @id, @Rang

While (@@Fetch_Status = 0)
Begin
	-- Bestimme, ob Datensatz zu entfernen ist
	If ((Select Count(*) From [zu-entfernen] As A
		Where A.Id = @id) = 0)
	Begin
		-- Kein Entfernen, stattdessen neuen Rang
		Select @neuer_Rang = Count(*)
		From Rangliste As A
		Where A.Rang <= @Rang
		And A.Id Not In
			(Select B.Id From [zu-entfernen] As B)

		-- und Update
		Update Rangliste
			Set Rang = @neuer_Rang
		Where Id = @Id
	End
	Else
		-- ansonsten löschen
		Delete From Rangliste
		Where Id = @Id

	Fetch Next From cs_Rangliste Into @id, @Rang
End
Close cs_Rangliste
Deallocate cs_Rangliste

Nun ja - dies ist keine Lösung, sondern eine Arbeitsbeschaffungsmaßnahme. Nachdem alle Zeilen herauskopiert wurden, wird für jede Zeile bestimmt, ob sie entfernt werden soll. Falls ja, wird dies erledigt, falls nein, wird der neue Rang ermittelt. Dies gelingt, indem die Zahl der verbleibenden Datensätze ermittelt wird, deren Rang kleiner oder gleich dem Rang der aktuellen Zeile ist. Abschließend wird die Zeile mit dem neuen Rang aktualisiert.

Eine solche Lösung ist innerhalb von SQL nicht zu implementieren. Sie ist jedoch als Zwischenschritt empfehlenswert und wurde deshalb hier aufgeführt, um das Problem in seine Teilprobleme zu zerlegen und diese in eine sinnvolle Reihenfolge zu bringen.

Man beachte, daß eine solche Lösung innerhalb einer prozeduralen Sprache mit eigener Array-Struktur, also mit direktem Zugriff auf den Heap, durchaus hervorragend sein kann. Innerhalb von SQL ist die Lösung jedoch ungenügend, da für den internen Optimierer, der die Größe und Struktur der Tabellen berücksichtigen kann, nun nicht mehr allzuviel zu tun bleibt. Der Code ist selbst 'zu dicht' an den Einzelzeilen, daß kein Platz mehr für einen Layer bleibt.

3.2 Zweite Lösung: Sortiert-Cursorbasiert, mitlaufender Index und vorherige Löschung

Ein Nachteil der vorherigen Lösung besteht darin, daß beim Berechnen der neuen Rangposition jedesmal auf die Menge der verbleibenden Zeilen als Differenz zwischen der Gesamttabelle und der Menge der zu löschenden Zeilen Bezug genommen werden muß. Dies legt es nahe, in einem vorgeschalteten Schritt alle zu entfernenden Zeilen tatsächlich zu löschen. Eine zweite 'Optimierung' könnte darin bestehen, die verbleibenden Spalten nach ihrem Alt-Rang geordnet zu verarbeiten. Da jeder Rang höchstens erniedrigt wird, kann eine zusätzliche Variable zu Beginn auf 1 gesetzt werden und in jedem Schritt einmal erhöht werden. Damit steht der Rang ohne komplexe Berechnung zur Verfügung und kann direkt für das Update genutzt werden. Der Cursor muß damit nur noch die ID-Spalte, sortiert nach Rängen, zurückgeben.

Declare @id int,
	@neuer_Rang int

Delete From Rangliste
Where Id In
	(Select Id From [zu-entfernen])

Declare cs_Rangliste Cursor
	Local Fast_Forward
For
Select A.Id
From Rangliste As A
Order By A.Rang

Open cs_Rangliste

Fetch Next From cs_Rangliste Into @id

Set @neuer_Rang = 1

While (@@Fetch_Status = 0)
Begin
	Update Rangliste
		Set Rang = @neuer_Rang
	Where Id = @id

	Set @neuer_Rang = @neuer_Rang + 1

	Fetch Next From cs_Rangliste Into @id
End

Diese Lösung wirkt auf den ersten Blick schon 'ganz brauchbar'. Sie stellt eine 'prozedurale Optimierung' dar, da durch die Einführung der Variablen @neuer_Rang das Problem der Ermittlung des neuen Ranges auf die Sortierung des Cursors reduziert wird. Sie beharrt jedoch auf einer zeilenweisen Verarbeitung und kann nur hierdurch den Rang in der Variablen @neuer_Rang mittransportieren. Die Verbesserung durch den Verzicht auf eine Ermittlung des neuen Ranges pro Zeile wird erkauft mit einer verschärften Abhängigkeit von einem zeilenweisen Arbeiten. Wirklich mengenorientiert hieße, nicht mehr eine Zeile, sondern alle Zeilen auf einmal zu verarbeiten, so daß der Optimierer die effizienteste Lösung ermittelt und nur wenige Male auf die Tabelle zugegriffen wird. Denn die Anweisung zur Ermittlung der neuen Rangzahl und die Update-Bedingung impliziert das wiederholte Suchen von Zeilen. Daß in der Schleife zuvor die vorherige Position gefunden wurde, dies vergißt diese Logik.

3.3 Dritte Lösung: Mengenbasiert und ohne Cursor

Nach dem Löschen der zu entfernenden Zeilen läßt sich die in der ersten Lösung enthaltene Sql-Abfrage direkt nutzen, um den neuen Rangplatz zu jeder Zeile in einem Arbeitsschritt zu ermitteln. Dies leistet die folgende Selbstverknüpfung:

Select B.Id, Count(*)
From Rangliste As B Inner Join Rangliste As C
On B.Rang >= C.Rang
Group By B.Id

Jeder Zeile von A werden alle Zeilen mit einem Rang kleiner oder gleich dem Rang der Zeile zugeordnet. Die entstehende Verknüpfungstabelle wird entlang der Primärschlüssel mit Group By in Teiltabellen zerlegt und von jeder Teiltabelle die Zahl der Zeilen ermittelt. Dieser Wert - Zahl der Zeilen kleiner oder gleich dem aktuellen Rang dieser Zeile - ist gerade der neue Rang. Diese Berechnung wird jedoch nicht zeilenweise, sondern für die gesamte Tabelle auf einmal ausgeführt, so daß die Teiltabellen nicht temporär erzeugt, sondern lediglich die Zeilen im Index durchgezählt werden. Da die Spalte <Rang> so viele verschiedene Werte wie Zeilen enthält, eignet sie sich ideal für die Erstellung eines Index, der zur Ermittlung aller Vorgänger herangezogen werden kann. Damit wird zur Berechnung dieser Zwischentabelle nur auf Indices zugegriffen. Die Zwischentabelle kann als Unterabfrage in einem Join genutzt werden und ermöglicht so eine direkte Aktualisierung:

Update Rangliste

	Set Rang = D.neuer_Rang

From Rangliste As A Inner Join

	(Select B.Id,
		Count(*) As neuer_Rang
	From Rangliste As B Inner Join
		Rangliste As C
	On B.Rang >= C.Rang
	Group By B.Id) As D

On A.Id = D.Id

Das eigentliche Update wird hier auch zeilenweise durchgeführt, da für jede Zeile ein neuer Wert ermittelt werden muß. Es müssen jedoch keine Daten aus der Tabelle herauskopiert werden, alle Daten bleiben intern. Jeder Cursor kopiert dagegen implizit Werte, auch wenn er nur eine Liste von Primärschlüsseln erstellt. Ebenso werden beim Zugriff von einer Wirtssprache intern Kopien erstellt und nach außen transportiert. Ferner kann bei der Berechnung der Zwischentabelle optimiert werden, so daß die Berechnung einer Zwischentabelle für 1000 Zeilen effizienter ist als die Berechnung von tausend Einzelpositionen.

3.4 Vierte Lösung: Ausschluß der Zeilen ohne Rangveränderung

Die bisherige Lösung führt noch zu unnötigen Aktualisierungen, falls sich der Rang einer Zeile nicht ändert. Auch in diesem Fall wird die Zelle aktualisiert. Dies läßt sich dadurch verhindern, daß entweder die innere Tabelle mit einem Having-Vergleich zwischen Count(*) und B.Rang verkleinert wird oder daß zusätzlich die Spalte B.Rang exportiert und der Vergleich in der äußeren Where-Klausel durchgeführt wird.

Having-Vergleich in der Unterabfrage:

Delete From Rangliste
Where Id In
	(Select Id From [zu-entfernen])

Update Rangliste

	Set Rang = D.neuer_Rang

From Rangliste As A Inner Join

	(Select B.Id,
		Count(*) As neuer_Rang
	From Rangliste As B Inner Join
		Rangliste As C
	On B.Rang >= C.Rang
	Group By B.Id, B.range
	Having Count(*) < B.Rang) As D

On A.Id = D.Id

Export von B.Rang und Vergleich außerhalb:

Delete From Rangliste
Where Id In
	(Select Id From [zu-entfernen])

Update Rangliste

	Set Rang = D.neuer_Rang

From Rangliste As A Inner Join

	(Select B.Id, B.Rang,
		Count(*) As neuer_Rang
	From Rangliste As B Inner Join
		Rangliste As C
	On B.Rang >= C.Rang
	Group By B.Id) As D

On A.Id = D.Id

Where B.neuer_Rang < B.Rang

Da der Optimierer wahrscheinlich im ersten Fall erkennt, daß der in der Having-Klausel genutzte Ausdruck Count(*) mit der Ausgabespalte <neuer_Rang> identisch ist, dürfte Count(*) auch im ersten Fall nur einmal berechnet werden. Analog wird wahrscheinlich im zweiten Fall die Where-Klausel implizit in die Unterabfrage hineingezogen, so daß beide Versionen effektiv denselben Ablaufplan erzeugen könnten.

3.5 Fünfte Lösung: Direkte Verkleinerung der inneren Tabelle

Betrachtet man die obige Lösung nochmals genauer, so fällt auf, daß der minimale Rang der gelöschten Zeilen eine Grenze markiert. Alle Zeilen mit einem niedrigeren Rang werden nicht aktualisiert, alle Zeilen mit höherem Rang müssen vom Update bearbeitet werden. Zunächst könnte auf die Ergänzungen unter 3.4 verzichtet werden, falls der erste gelöschte Rang = 1 ist. Diese Bedingung kann nun jedoch auch direkt der Unterabfrage hinzugefügt werden, so daß diese auf die Zahl der tatsächlich zu aktualisierenden Zeilen eingeschränkt wird.

Delete From Rangliste
Where Id In
	(Select Id From [zu-entfernen])

Update Rangliste

	Set Rang = D.neuer_Rang

From Rangliste As A Inner Join

	(Select B.Id, B.Rang,
		Count(*) As neuer_Rang
	From Rangliste As B Inner Join
		Rangliste As C
	On B.Rang >= C.Rang
	Where B.Rang >

		(Select Min(E.Rang) From
		[zu-entfernen] As E)

	Group By B.Id) As D

On A.Id = D.Id

Die neue Unterabfrage in der Where-Klausel kann auch vorgezogen und das Minimum in einer Variablen abgelegt werden. Sofern es sich hierbei um eine einmalig ausgeführte Anweisung handelt, dürfte es keine Auswirkung auf die Performance geben.

4. Zusammenfassung

Sql kann seine Leistungsfähigkeit bei der Verarbeitung großer Datenmengen durch die Wiederverwendbarkeit von Ablaufplänen erst dann richtig ausspielen, wenn der Sql-Code mengenbasiert arbeiten darf. Dies kann erreicht werden durch:

• Kompakte und durchaus komplexe Sql-Anweisungen, die sagen, was zu tun sei, anstatt die Daten zeilenweise herauszuziehen und für jede Zeile diverse Einzelaktionen durchzuführen. Ein Verarbeiten von Einzelzeilen arbeitet zwar direkt an den Daten, es gibt jedoch keinen Platz mehr für einen Layer.
• Damit Verzicht auf wiederholten Datentransfer zwischen den Tabellen und Objekten der Umgebung wie Cursor und Variablen. Man beachte, daß dies kein spezielles mySql/PHP - Problem ist, bei dem zusätzlich die Sprach- oder Prozeßgrenze überschritten wird, sondern auch direkt für den Code serverseitig gespeicherter Prozeduren gilt.
• Erstellen geeigneter Indices. Eine Spalte mit Rangpositionen ist für einen Index ideal, da alle Zellen belegt und das Verhältnis von Zellwerten zu Zeilen immer 1:1, der Index also maximal selektiv ist. Indices auf Spalten mit nur wenigen Werten oder auf Spalten, die viele Null-Werte enthalten, blähen die Datenbank nur unnötig auf und verlangsamen die Einfügung neuer Werte ohne Performance-Gewinn für Abfragen.

Ergänzende Bemerkung: Das obige Problem der Korrektur von Rangpositionen tauchte bei der Entwicklung des Hauptprojektes Server-Daten: Die Web-Datenbank für erstklassige Unternehmen auf. Beim Upload einer Tabelle enthält die externe Datei einige Spalten in festgelegter Reihenfolge / Rang, dies entspricht einer Menge von Tabellenzeilen mit Spaltenname, Datentyp und Spaltenposition in der externen Datei. Sollen einige Spalten ignoriert, also beim Import übersprungen werden, so liefert die obige Anweisung die aktualisierten Rangpositionen für die Erstellung einer neuen Tabelle, ohne daß jede Upload-Spalte einzeln überprüft und alle Nachfolger individuell korrigiert werden müssen.