Warning: include_once(/var/www/html/pmwiki-2.2.86/cookbook/soap4pmwiki/soap4pmwiki.php): failed to open stream: No such file or directory in /var/www/html/fields/dbp15/local/config.php on line 4

Warning: include_once(): Failed opening '/var/www/html/pmwiki-2.2.86/cookbook/soap4pmwiki/soap4pmwiki.php' for inclusion (include_path='.:/opt/php/lib/php') in /var/www/html/fields/dbp15/local/config.php on line 4

Warning: Cannot modify header information - headers already sent by (output started at /var/www/html/fields/dbp15/local/config.php:4) in /var/www/html/pmwiki-2.2.86/pmwiki.php on line 1250
Datenbankpraktikum SS 2015 - D - Query Execution

Query Execution Modul

Hendrik Langebrake

Quelldatei: https://github.com/OsnaCS/uosql-server/blob/master/server/src/query.rs

Die Aufgabe des Query Execution Modules ist es, einen vom Parser erzeugten abstrakten Syntax Baum zu interpretieren und die notwendigen Funktionen der Speicherengine aufzurufen.

Dafür ist nach außen die Methode execute_from_ast(_,_) sichtbar,

fn execute_from_ast<'a>(query: Query, user: &'a mut auth::User) -> Result<ResultSet, ExecutionError>

ihr wird der Syntax Baum und der ausführende Nutzer übergeben. Letzteres ist notwendig um bei gewissen Abfragen wie z.B. "delete" und "update" die Authorität des Nutzers prüfen zu können und um mitzuführen, in welcher Datanbank dieser momentan arbeitet. Als Ergebnis liefert execute_from_ast(_,_) entweder ein Result Set, welches dann im Client angezeigt werden kann, oder einen Execution Error, der die Fehlerursache beschreibt.

Query:
INSERT INTO Studenten VALUES (951674, "Susi")
 
Syntax Baum:
ManipulationStmt(
	InsertStmt {
		tid: "Studenten",
		col: [],
		val: [Int(951674), String("Susi")]
	}
)

Die Interpretation eines Syntax Baumes läuft im Allgemeinen so ab, dass anhand der Wurzel und der inneren Knoten des Baumes (im Beispiel: ManipulationStmt und InsertStmt) intern die passenden Funktionen aufgerufen werden, die dann die Daten in den Blättern des Baumes (im Beispiel: Table ID: "Studenten", Values: 951674, "Susi") queryspezifisch mit der Speicherengine verarbeiten.
Bisher unterstützt das Query Execution Modul die Verarbeitung von Use, Create, Drop, Alter, und Select Statements, eine Updatefunktionalität kann erst umgesetzt werden, wenn die Speicherengine komplexere Bedingungsverarbeitung bei ihrer Updatemethode implementiert. Im Folgenden wird die Datenverarbeitung an zwei ausgewählten Beispielen näher erläutert.

Beispiele

"Insert Into" - Query:

Die Datenblätter des Insert-Into-Syntaxbaumes enthalten die ID der Zieltabelle (im Beispiel: tid), die Spalten, für die Werte spezefiziert werden (col) und schließlich die einzufügenden Werte (val).

Über das an die Top-Level-Methode übergebene Nutzer-Objekt wird bestimmt, auf welche Datenbank sich die Tabellen-ID bezieht. Ist die Tabelle in dieser Datenbank vorhanden wird anhand der Metadaten geprüft, ob die einzufügenden Werte die für die Tabelle passende Anzahl und die passenden Datentypen haben.
Ist dies der Fall, werden die einzufügenden Werte in einen Bytevektor konvertiert und der Insert-Funktion der Tabellenengine übergeben, die dann die neue Zeile in die entsprechende Datei schreibt.
Der Rückgabewert bei einem Insert Statement ist ein leeres Result Set.

"Select" - Query:

Query:
SELECT s.Name AS Name FROM Studenten s WHERE s.MatrNr = 951674 LIMIT 100
 
Syntax Baum:
SelectStmt {
	Target {
		alias: Some("s"), col: Name, rename: "Name"
		},
	tid: ["Studenten"],
	alias: {"s": "Studenten"},
	cond: Leaf(
		Condition {
			aliascol: Some("s")
			col: "MatrNr"
			op: Equ
			rhs: Int(951674)
			}
		),
	order: [],
	limit: { count: 100 }
}

Für jede ID aus dem Vektor im Blatt "tid" des Syntax Baumes wird die Existenz der Zieltabelle geprüft, falls diese existiert wird sie in ein großes Kreuzprodukt geladen. Gleichzeitig wird eine Hashmap angelegt, die von einem Alias oder einer Tabellen-ID auf eine zweite Hashmap verweist, in der von den Tabelleneigenen Spalten auf die entsprechenden Spalten im zu bearbeitenden Kreuzprodukt verwiesen wird. Dies erlaubt eine freie Handhabung von optionalem Alias-/ oder Tabellen-ID-Präfix vor Spaltennamen in Where-Teilen einer Select-Query.

Die erstellte Hashmap und das Kreuzprodukt werden zur weiteren Bearbeitung an eine Methode übergeben, die den Bedingungsbaum (im Syntaxbaum ist dieser im Knoten "cond" zu finden) des Where-Teiles rekursiv abarbeitet:
An einem AND-Knoten wird zuerst die linke Seite berechnet, die Ergebnismenge wird dann mit der Bedingung der rechten Seite weiter verringert.
Ein OR Knoten erweitert die Ergebnismenge der linken Bedingung mit der Ergebnismenge der rechten Bedingung.
Bedingungsblätter (Leaf) enthalten die grundlegende Bedingung nach der ein Ergebnis berechnet werden soll. Nach der Prüfung der Bedingung auf legitime Vergleichswerte unter Zuhilfenahme der Metadaten der Zieltabelle wird die bisherige Ergebnismenge mit der Lookup-Funktion der Engine, der die Bedingung als Bytevektor übergeben wird, weiter verringert.

Die berechnete Ergebnismenge wird nun auf die Spalten projiziert, die im Knoten "Target" des Syntaxbaumes spezifiziert sind. An dieser Stelle werden auch Umbenennungen der Zielspalten und die Limitbeschränkung der Spaltenzahl berücksichtigt.
Der Rückgabewert eines Select Statements ist ein Resultset, das den gestellten Bedingungen genügt und bereit zum Senden an den Client ist.

Verbesserungen:

An der Abarbeitung von Where-Bedingungen kann noch viel optimiert werden. Die nächstliegende Verbesserung ist, die Tabellen erst dann von der Festplatte zu lesen, wenn sie in der Berechnung der Blätter eines Bedingungs-Baumes benötigt werden. Dies erfordert zusätzliche Verwaltungsarbeit, sollte aber leicht umzusetzen sein.

Des weiteren kann an den Bedingungsblättern Delete statt Lookup verwendet werden, dies wird aber erst effektiv wenn die Speicherengine bei Delete sinnvolles Speichermanagement einsetzt.


Autor: Hendrik Langebrake


Page last modified on September 25, 2015, at 02:27 PM