Interoperable Informationssysteme - 1 Klemens Böhm Systeme 3: Queryoptimierung für heterogene Umgebungen

Interoperable Informationssysteme - 1Klemens Böhm

Systeme 3:

Queryoptimierung für heterogene Umgebungen


ErweiterbarkeitZwei Arten der Erweiterbarkeit:

1. Herkömmliche Anfragen im relationalen Datenmodell, Komponenten mit unterschiedlichen Fähigkeiten:

Hinzufügen neuer Komponenten, Query-Optimizer über Komponenten

und ihre Fähigkeiten informieren, Berücksichtigung der neuen Komponenten

bei Queryplanerzeugung.

2. Externe Funktionen: Unterschiedliche Folgen von Aufrufen

können äquivalent sein, Berücksichtigung bei der Query-Planerzeugung.

Ziel: Zuhörer soll die Arten der Erweiterbarkeit + Mechanismen kennen.

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

Adaptivität


Erweiterbarkeit im Sinne von 1. Erweiterbarkeit heisst hier:

Erweiterbarkeit des Suchraums, d.h. der Menge der Pläne, die betrachtet werden.

Annahmen bezüglich des Szenarios: Komponenten sind unterschiedlich leistungsfähig.

Beispiele:– Tabelle in Spreadsheet oder RDBMS,– Daten in Informationssystem à la sbb.ch

oder in (full-fledged) SQL-Datenbank. Möglichst grossen Teil der Queries

von den Komponenten ausführen lassen. Ansatz: Garlic-Middleware, IBM Almaden,

Verwendung des DB2-Query Optimizers.

Einleitung

Erweiterbar-keit 1

- Übersicht

- Interesting Orders

- Production Rules

- P. Rules – Q.Planerz.

- externe Sourcen

Erweiterbar-keit 2

Adaptivität


Abfolge Interesting Orders,

das sind Eigenschaften eines Queryplans, Production Rules

(Ansatz basiert auf Production Rules),Production Rules geben an, wie Querypläne aufgebaut sein können,

Zusammenhang Production Rules – Queryplanerzeugung,

Production Rules für externe Sourcen.

Einleitung

Erweiterbar-keit 1

-Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität


Annahmen Keine Replikation, relationales Modell, keine Heterogenität auf der Modellierungsebene.

Einleitung

Erweiterbar-keit 1

- Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität


Properties eines Plans Äquivalenz von Algebraausdrücken:

nicht nur, welcher Teil des Querygraphen evaluiert wird, sondern auch weitere Eigenschaften des Plans – Beispiele: Sortierung:

Erster Plan ist u.U. besser, will jene Sortierung später noch einmal gebraucht werden kann. D.h. Pläne nur dann identisch, wenn auch Sortierung gleich.

Client-Server Verteilung, d.h. wo befinden sich die Tupel.

GetA

Sort

GetB

Sort GetA

GetB

Sort-Merge Hash

Einleitung

Erweiterbar-keit 1

- Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität


Properties eines Plans Menge von Eigenschaften (Properties)

für jeden Plan. Property-Werte: Vergleichbarkeit

von logisch äquivalenten Plänen. Properties: u.a. Input

für Kostenmodell. Property-Vektor: erweiterbar. Interesting Orders.

Einleitung

Erweiterbar-keit 1

- Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität


Properties eines Plans mit Garlic “Relational” (Was?)

TABLES Menge der zugegriffenen Tables, COLS Menge der zugegriffenen Spalten

(Projektion verringert diese Menge.)

PREDS Menge der angewendeten Prädikate,

“Physikalisch” (Wie?) ORDER Reihenfolge der Tupel

(d.h. Liste von Spalten), SITE Site, wo sich Tupel befinden, TEMP ‘TRUE’ gdw. Tupel in Temp-Table

materialisiert sind, “Geschätzt” (Wieviel?)

CARD Geschätzte Anzahl von Tupeln, COST Geschätzte Kosten.

Einleitung

Erweiterbar-keit 1

- Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität

InterestingOrders


Beispiel Zwei Sourcen:

Lehrveranstaltungs-Datenbank, Komponente zur Verwaltung von Emails,

Komponente kann Emails zurückgeben,keine Selektion, keine Joins.

Beispielquery:

Algebra-Operatoren: Project, Join – mit der üblichen Bedeutung, PushDown – gibt Teilquery

zur Ausführung an Komponente weiter, Fetch extrahiert Attribute.

select m.Bodyfrom Inbox m, Classes cwhere m.Subject=c.Course

and c.Prof=‘Schek’

Einleitung

Erweiterbar-keit 1

- Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität

D.h. wir wollen alle Mails, in denen es um Lehrveranstaltungenvon Prof. Schek geht.


‘Source’ - gibt an,wo Output produziert wird.(zusätzliches Property, das zuvor noch nicht erwähnt wurde)

Garlic-Queryplan mit PropertiesTables: {Inbox m, Classes c}Columns: {m.Body}Preds: {c.Prof=‘Schek’, m.Subject=c.Course}Source: {Garlic}Temp: falseOrder: NIL

Tables: {Inbox m}Columns: {m.OID, m.Subject, m.Body}Preds: {}Source: {Garlic}Temp: falseOrder: NIL

Tables: {Inbox m, Classes c}Columns: {m.OID, m.Subject, m.Body, c.OID, c.Course}Preds: {c.Prof=‘Schek’, m.Subject=c.Course}Source: {Garlic}Temp: falseOrder: NIL

Tables: {Inbox m}Columns: {m.OID}Preds: {}Source: {Mail}Temp: falseOrder: NIL

Tables: {Classes c}Columns: {c.OID, c.Course}Preds: {c.Prof=‘Schek’}Source: {DB2}Temp: falseOrder: NIL

Project

Join

Fetch (m, {Subject, Body})

PushDown(Mail) PushDown(DB2)

Entspricht Teilgraphdes Querygraphen(vgl. Dynamic Programming)

Fetch extrahiert Attribute

Einleitung

Erweiterbar-keit 1

- Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität

select m.Bodyfrom Inbox m, Classes cwhere m.Subject=c.Course

and c.Prof=‘Schek’


Erweiterbare Queryoptimierung Motivation – noch einmal, ausführlicher:

neue Operator-Implementierung hinzunehmen, Komponente mit bestimmten Fähigkeiten

dazunehmen/wegnehmen. Menge der möglichen Pläne

darf nicht hartkodiert sein, muss explizit beschrieben werden.

Einleitung

Erweiterbar-keit 1

- Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität


Production Rules

Regeln ‘funktionieren’ wie Regeln einer Grammatik. Regeln spezifizieren, wie Queryalgebra-Ausdrücke

aus anderen Ausdrücken zusammengesetzt sind. STARs - ‘Strategy Alternative Rules’. p := joinPlan(optPlan(Sj), Rj)

wäre hartkodierte Regel im Dynamic Programming Algorithmus.

Andere Regel für bushy Trees.

Einleitung

Erweiterbar-keit 1

- Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität


Production Rules – Beispiel Beispiele (für Regeln, nicht für Anwendung):

JoinRoot(T1,T2,P) ::= NestedLoopJoin(T1,T2,P) JoinRoot(T1,T2,P) ::= HashJoin(T1,T2,P)

Conditions: none; Functions: none Regeln anwendbar, bis nur noch Terminalsymbole

(d.h. Algebraoperatoren, für die Implementierung existiert):

NestedLoopJoin(T1, T2, P) ::= NLJ(FetchCols(T1, NeedAttr(T1, P)),

Scan(Temp(FetchCols(T2,NeedAttr(T2,P)))), P)Conditions: none

NeedAttr(Plan, Preds) ermittelt die Attribute der Kollektionen in Plan, die zur Berechnung der Prädikate in Preds gebraucht werden.

Einleitung

Erweiterbar-keit 1

- Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität


Regelanwendung Grammatik: Startsymbol und mind. eine Regel,

die Ersetzung für Startsymbol definiert. Sinngemäss gleiches Vorgehen hier:

Unterschiedliche Startausdrücke (Startsymbole), die dann expandiert werden.1. Phase - einen Startausdruck für jede Relation

2. Phase - schrittweise ein Startsymbol (‘JoinRoot’) für Teilgraphen

des Querygraphen, dessen Teilgraphen schon analysiert wurden;

Bedingungen für Regelanwendungen erlauben einzustellen, ob bushy/linear oder ob kartesisches Produkt;

Prunen suboptimaler Teilausdrücke.

Einleitung

Erweiterbar-keit 1

- Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität


Beispiel: Regeln für externe Sourcen Beispiel hier: Join-Evaluierung durch die Sourcen.

Weitere JoinRoot-Regel:JoinRoot(T1,T2,P) ::= RepoJoin(T1,T2,P)C: keine; F: keine.

Wrapper implementiert Funktion plan_join. Sie liefert Ergebnis, wenn Wrapper Join evaluieren kann, z.B.

plan_join(T1, T2, P) = R_Join(T1, T2, P) Condition: T1.Source = T2.Source.Function: keine

RepoJoin(T1, T2, P) := pplan_join(T1, T2, P): PushDown(p)C: T1.Source = T2.Source; T1.Source ‘Garlic’;

plan_join(T1, T2, P) ist definiert für den Wrapper von T1.Source.

F: keine

Einleitung

Erweiterbar-keit 1

- Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität


Zusammenfassung Production Rules beschreiben,

wie Teilquery evaluiert werden kann. Startsymbol

entspricht Teilgraph der Query, werden nacheinander abgearbeitet,

von kleinen zu grossen Queries. Funktion plan_join

Wrapper implementiert sie, wird aufgerufen zur Überprüfung,

ob Regel anwendbar.

Einleitung

Erweiterbar-keit 1

- Übersicht


- Production Rules


- externe Sourcen

Erweiterbar-keit 2

Adaptivität


Motivation, erster Teil Viele Szenarien

erfordern Aufruf benutzerdefinierter Funktionen in Queries.

Benutzerdefinierte Funktionen enkapsulieren Zugriff auf existierende Komponenten.

Unterschied zu eben:Externe Funktionen in Queries erlaubt.

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

- Motivation

- Rewrite Rules

-Queryplan- erzeugung

Adaptivität


Beispiel RDBMS mit Relation ‘Business’,

Attribute: ID, Name, Art des Business, Adresse, Telefon, Grösse, Gewinn,

Komponente für Spatial Data Management (d.h. geographische Daten) – Funktionen: Map – selektiert alle Punkte der Landkarte,

die Geschäften entsprechen, Map_Restaurant – dto. Restaurants, Inside – erwartet Punkt und rechteckiges Fenster,

liefert boolschen Wert Mapclip – erwartet Fenster,

liefert Punkte, die Geschäften entsprechen. Query: “Alle Punkte zu Geschäften in gegebenem Fenster.”

Evaluierungsalternativen: Map, gefolgt von Inside, Mapclip.

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

- Motivation

- Rewrite Rules


Adaptivität


Beispiel 2 Query: “Alle Restaurants in Wipkingen.”

(Rechteck-Fenster, das Wipkingen entspricht, sei gegeben.)

Evaluierungsalternativen: Map_Restaurant, gefolgt von Inside, Mapclip + Zugriff auf Relation ‘Business’

+ Schnittmengenbildung.

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

- Motivation

- Rewrite Rules


Adaptivität


Motivation, Fortsetzung Queryoptimierer braucht semantische,

anwendungsspezifische Information, d.h. Anwendungsprogrammierer muss sie bereitstellen.

Beispiel: Query-Optimizer muss wissen, dass ‘Map, gefolgt von Inside’, sowie ‘Mapclip’ äquivalent sind.

Spezifikation sollte möglichst einfach sein, z.B. deklarativ.

Rewrite Rules, die als Input für den Queryoptimizer dienen.

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

- Motivation

- Rewrite Rules


Adaptivität


Datalog-Notation (1) Query: “Selektiere alle Restaurants im Fenster w,

die besser verdienen, als Grösse erwarten lässt.” SQL-Statement:

select Business.Name, Map.Locationfrom Business, Mapwhere Business.Type = ‘Restaurant’

and Business.ID = Map.IDand Inside(w, Map.Location)and Business.Earning > Expected-

Revenue(Business.Size)

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

- Motivation

- Rewrite Rules


Adaptivität


Datalog-Notation (2) Datalog-Notation:

Query(name, location) :-Business(name, Restaurant, earn, size, id),Map(id, location), Inside(w, location),Expect_Revenue(size, exp), earn > exp

Erläuterung: <name, location>-Paar ist Ergebnis der Query, wenn gilt: Tupel in Business mit …

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

- Motivation

- Rewrite Rules


Adaptivität


Rewrite Rules Beispiel für Rewrite Rule –

sie spezifiziert Äquivalenz von vorangegangener Folie:Map(id, loc), Inside(window, loc)-> Mapclip(id, loc, window)

Die folgenden Queries müssen also stets das gleiche Ergebnis liefern: Ql(id, loc, window) :-

Map(id, loc), Inside(window, loc) Qr(id, loc, window) :- Mapclip(id, loc, window)

Regel ist anwendbar auf Queries: Query(name, loc) :-

Business(name, Restaurant, earn, size, id),Map(id, loc), Inside(w, loc), Intersect(w1, w2, w)

wird zu Query(name, loc) :-

Business(name, Restaurant, earn, size, id),Mapclip(id, loc, w), Intersect(w1, w2, w)

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

- Motivation

- Rewrite Rules


Adaptivität

OK, dass andere Variablennamen.


Safety Constraint Unterschied zwischen Datenbank-Relationen und Prädikaten,

z.B. ‘Business’ vs. ‘Inside’:Man kann alle Tupel aus Relation ‘Business’ holen, man kann aber nicht explizit alle (Fenster, Punkt)-Paare bilden, die inside erfüllen.

Beide Argumente von inside müssen gebunden sein, d.h. expliziter Zugriff auf andere Relation instanziiert Variable loc.

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

- Motivation

- Rewrite Rules


Adaptivität


Soundness Rewrite Rule darf keine Variable enthalten, die nur auf

linker Seite vorkommt, und die auch in Literal ‘ausserhalb der Transformationsregel’ vorkommt.

D.h. Regelanwendung ist sound oder nicht, nicht Regel selbst.

Beispiel: Query:

Query(loc) :-Business(bname, Restaurant, earn, size, id),Map(id, loc), Owner(bname, bob)

Transformationsregel:Business(bname, Restaurant, earn, size, id),

Map(id, loc) <-> Map_Restaurant(id, loc) Nicht äquivalente Query:

Query(loc) :-Map_Restaurant(id, loc), Owner(bname, bob)

Kein Zusammenhang zwischen id und bname mehr.

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

- Motivation

- Rewrite Rules


Adaptivität


Queryplanerzeugung Prinzip (wird gleich verfeinert):

1. Erzeugung aller zur Ausgangsquery äquivalenten Query durch Anwenden der Rewrite Rules.

2. Planerzeugung für alle in Schritt 1 generierten Queries und Auswahl des billigsten Plans.

Regeln nicht unkontrolliert anwenden - Illustration: Integritätsbedingung:

Alle Restaurants sind im Fenster w. Mapclip ist weniger aufwendig, wenn Fenster klein. Regel:

Business(bname, Restaurant, earn, size, id),Mapclip(id, loc, window) -> Business(bname, Restaurant, earn, size, id),Mapclip(id, loc, small_win), Intersect(window, w, small_win)

Abhilfe: Dummy-Prädikate einführen. Welches Prädikat muss umbenannt werden?

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

- Motivation

- Rewrite Rules

- Queryplan- erzeugung

Adaptivität


Wiederverwertung optimaler Pläne Äquivalente Queries

haben i.a. identische Subqueries, mit dem o.g. Vorgehen werden diese Subqueries

mehrmals optimiert, ineffizient. Hashtabelle, die jede Subquery

auf entsprechenden optimalen Plan abbildet, als Hilfsstruktur.

Vor der Planerzeugung für jede Subquery wird die Hashtabelle konsultiert.

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

- Motivation

- Rewrite Rules

- Queryplan- erzeugung

Adaptivität


Queryoptimierung in verteilten, heterogenen Systemen – neue Verfahren

Variante 1: Erzeugung mehrerer Pläne zur Compile-Zeit,

unterschiedliche Pläne sind für unterschiedliche Datenbank-Zustände unterschiedlich gut.

Auswahl aus diesen Alternativen zur Laufzeit. Variante 2:

Ausführung eines (zur Compilezeit oder Laufzeit ermittelten) Plans,

Wenn Abweichung tatsächlicher von erwarteten Kosten > gegebener Schwellenwert: Zwischenergebnis materialisieren, nochmals optimieren.

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

Adaptivität


Berechnung der Response Timebei verteilter Query Execution (1)

1. Berechnung des Ressourcenverbrauchs jedes Operators,

2. Berechnung der Auslastung jeder Ressource durch parallele Operatoren,

3. Antwortzeit dieser parallelen Operatoren –Maximum der in 1. und 2. berechneten Zeiten.

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

Adaptivität


Berechnung der Response Timebei verteilter Query Execution (2)

Beispiel:

Annahmen: Jeder Join kostet 200 s CPU-Zeit, Shipping eines Join-Ergebnisses kostet 130 s, alle weiteren Kosten sind Null.

Alternativen dauern 600 s bzw. 200 s.

Einleitung

Erweiterbar-keit 1

Erweiterbar-keit 2

Adaptivität join

A B

join

C D

join

display

join

A B

join

C D

join

display

join

A D

join

C B

join

display

Plan zur Compile-Zeit Plan 1 Plan 2

Documents

Interoperable Informationssysteme - 1 Klemens Böhm Systeme 3: Queryoptimierung für heterogene Umgebungen