Interoperable Informationssysteme - 1 Klemens Böhm Systeme 2: Query Processing - Grundlagen

Interoperable Informationssysteme - 1Klemens Böhm

Systeme 2: Query Processing -

Grundlagen


Interoperabilität – Architektur

Wrapper

Source

Mediator

Wrapper

Source

Client

Wrapper

Source

Anfragen sind deklarativ, Ausführung muss gefunden werden.

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Mediatoren und Wrapper Aufgaben des Mediators:

Parsen der Query, Query Rewrite, Query Optimization, Ausführung eines Teils der Anfrage, Verwaltung des globalen Schemas.

Aufgabe des Wrappers: Übersetzen jedes Requests des Mediators

in die Sprache der zugrundeliegenden Komponente,

Übersetzen des Anfrageergebnisses ins Mediator-Format; Konformität zum globalen Schema.

Mediatoren und Wrapper sind Bestandteile der Software-Architektur.

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Gliederung im folgenden Problem im folgenden:

Wie geht Query Processing? Vorgehen:

Aussagen zu Query Processing allgemein (nicht-verteilter Fall)

Query Processing im verteilten, heterogenen Fall:

– Middleware für Information Integration:Harmony

– Erweiterbarkeit• Hinzunehmen neuer Komponenten,• benutzerdefinierte, externe Funktionen,

– Adaptivität.

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Query Processing - Schritte

Parsing: Umwandlung der Query in interne Repräsentation Query Validation:

Überprüfung, ob die Query nur zulässige Referenzen auf existierende Datenbankobjekte enthält.

View Resolution: Expandieren von Views/Integritätsbedingungen in die Query,

Optimization: Erzeugung eines ausführbaren Plans, Plan Compilation:

Umwandlung des Plans in direkt ausführbare Repräsentation, Execution.

Parsing

Query Validation

View Resolution

Optimization

Plan Compilation

Execution

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell

Klassisches Modell,wird später z.T. gekippt.


Algebraische Darstellung von Queries

Operatoren haben eine oder mehr Input-Mengen und erzeugen eine (oder mehr) Output-Menge(n).

Blätter entsprechen Quellen, z.B. Relationen.

Getp,Person Geta,Account

p.age<30 a,balance>10000

name

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell

„Gib‘ mir die Namen der Personen,die jünger als 30 sind und mehr als 10000 auf einem Konto haben.“


Logische u. physische Algebraausdrücke

Intersection

Set A Set B

Merge-Join (Intersect)

Sort Sort

File Scan A File Scan B

Logische Operatoren drücken aus, welches die Zwischenergebnisse sind.

Physische Operatoren geben an, wie die Queryevaluierung abläuft.

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Logische und physische AlgebraWarum Unterscheidung? Physical Algebra ist systemspezifisch,

z.B. unterschiedliche Join-Implementierungen:Nested-Loop, Sort-Merge, Hash.

Nur Operatoren der physischen Algebra haben Kosten.

Unterschiedliche Operatoren: Weniger Operatoren auf logischer Ebene,

z.B. kein Sort.D.h. Sortiertheit ist keine logische Eigenschaft, logische Sicht ist Mengen-Sicht.

Physische Operatoren implementieren mehrere oder nur Teile von logischen Operatoren(z.B. Join-Implementierung enthält Projektion, Duplicate-Removal)

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Operator-Implementierung

Alternativen: “set-at-a-time”, “tuple-at-a-time”.

‘Set-at-a-time’:

- evaluiert Operatoren nacheinander.



name

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Operator-Implementierung -‘Tuple-at-a-Time’

‘Tuple-at-a-time’ implementiert Iteratorkonzept.

Üblicherweise einheitliche Operationen: open

(baut beim Hash-Join z.B. Hash-Tabelle auf), next,

erst next erklären, am Beispiel des -Operators

close.



name

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Operator-Implementierung -‘Tuple-at-a-Time’ (2)

Iteratorkonzept - Erläuterungen: Ergebnis und Zwischenergebnisse

sind Folge von Tupeln (aber auch andere Granularität möglich),

jeder Operator implementiert Iterator über sein Zwischenergebnis,

Operator ruft Input-Operator auf, um nächsten Tupel etc. zu bestimmen.

‘Tuple-at-a-time’ ist zwar i.d.R. schneller, funktioniert aber nicht immer bei Updates.Beispiel:“Erhöhe das Einkommen von den 10% der Mitarbeiter, die am wenigsten verdienen, um CHF 200,--.”

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Meta-OperatorenInput wird nicht manipuliert,

stattdessen Kontroll-Funktion: Wechsel von einer Granularität zur anderen,

Ziel: Reduzierung der Netz-Belastung.

Caching.

Getp,Person

Geta,Account


Receive

Send

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Queryoptimierung/Querypläne

Grundprobleme: Query ist (per Definition) deklarativ,

macht keine Aussagen zur Ausführungsreihenfolge.Man benötigt aber ausführbaren Plan.

Ziel ist nicht unbedingt, optimalen Plan zu finden,guter Plan reicht im allgemeinen.Optimierungszeit verlängert Gesamtdauer des Query Processing.

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Gängige graphische Darstellung einer (Select-Project-Join) Query (SPJ-Query), z.B.

select v2.Namefrom p in produkt, v in verkauf, v2 in verkaeufer,

g in geschaeft, s in stadtwhereg.location == s and

s.bundesland == bayern ...

Query Graph

produkt

verkaeufer

verkaufgeschaeft

stadt

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Join-Prädikate vs. Selektionsprädikate

Selektionsprädikat -Prädikat, das sich auf eine Relation bezieht Beispiel: “verkaeufer.name == ‘Bischoff’”, würde im Querygraph durch Zykel dargestellt,

wird aber oft weggelassen,

Selektionsprädikate werden _üblicherweise_ so früh wie möglich evaluiert.

produkt

verkaeufer

verkaufgeschaeft

stadt

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Join-Prädikate vs. Selektionsprädikate

Join-Prädikat -Prädikat, das sich auf zwei Relationen bezieht, entspricht Kante im Querygraph,

bei frei definierbaren Prädikaten kann Join-Prädikat sich auf mehr als zwei Relationen beziehen.

produkt

verkaeufer

verkaufgeschaeft

stadt

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell

QuerypläneMenge der möglichen Pläne: ‘left-deep’ vs. ‘bushy’

dazwischen: Beschränkung der Tiefe des rechten Teilbaums

left-deep - als Liste von Relationen darstellbar. kartesisches Produkt oder nicht.Differenzierungen werden gebraucht für

Queryplanerzeugung – was genau wird erzeugt?

stadt geschaeft

verkauf

produkt

verkaeufer

stadt geschaeft

produkt verkauf

verkaeufer


Query Optimierung Queryoptimierung :=

Erzeugung eines guten Queryplans,nicht in erster Linie des besten.

zentrales Problem bei Queryoptimierung:Anordnung der Joins (Join Enumeration)

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Bottom-Up Query Optimierung Schrittweises Vorgehen:

Schritt k berechnet besten Plan für zusammenhängenden Teilgraphen der Grösse k.

Vorgehen: Man erzeugt mehrere sog. Kandidaten-Pläne, und zwar durch Verknüpfung optimaler Teilpläne (hier im Algorithmus alle optimalen Teilpläne der Grösse k-1).

Streng genommen müsste man noch beweisen, dass Teilpläne des optimalen Plans für ihren Teilplan optimal sind.

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Bottom-Up Query Optimierung

procedure DP:

for i := 2 to n do {for all S {R1, …, Rn} s.t. ||S||=i do {

bestPlan := a dummy plan w/ infinite cost

for all Rj, Sj s.t. S = {Rj} Sj do {

p := joinPlan(optPlan(Sj), Rj)

if cost(p) cost(bestPlan)

bestPlan := p}

optPlan(S) := bestPlan}}

return (optPlan({R1, …, Rn}))

Subgraphen müssen zusammenhängend sein.

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Bottom-Up Query Optimierung - Erläuterungen

Algorithmus implementiert nur Join-Enumeration. Menge der möglichen Pläne ist hartkodiert

(s.b. Animation auf voriger Folie), Bottom-up Query Optimierung

= Dynamic Programming.

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Kostenmodellierung Man hat mehrere mögliche Pläne

für eine Query (bzw. für eine Teilquery), muss sich für einen entscheiden.

Übliches Kriterium: Dauer der Ausführung, aber auch andere Kosten denkbar, z.B. Ressourcenverbrauch oder pekuniäre Kosten

externe Kosten apriori nicht bekannt, Schätzung (Kostenmodell) erforderlich.

Kostenmodell sollte realistisch, aber nicht zu ausgefeilt sein(Gesamtkosten = Kosten Queryoptimierung + Kosten Queryevaluierung)

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell


Sortieraufwand

Kostenmodellierung - Beispiel Nested-Loop Join ohne Indexunterstützung

R1 wird stückweise eingelesen und mit R2 gejoint; Main Memory gross R2 wird nur einmal gelesen.

Sort-Merge Join, Relationen sind sortiert.

Sort-Merge Join, Relationen sind unsortiert.

2

1

1 121 RR

R bms

bbRRC

Anzahl Blocks,die R1 belegt.

GrösseMain Memory

2121 RR bbRRC

222111

loglog21 RRmsRRRmsR bbbbbbRRC

Motivation

Query Proc.Basics

ÜbersichtQ. Proc.

log. vs.phys. Alg.

Queryeval.

Optimie-rungen

Queryplan-erzeugung

Kosten-modell.


Kostenmodellierung Das ist nur die halbe Wahrheit:

Man muss auch die Grösse des Join-Ergebnisses abschätzen, um Kosten der darauf aufbauenden Operatoren schätzen zu können,

sehr schwierig, da von der Werteverteilung in den Relationen abhängig.

Motivation

Query Proc.Basics

-Übersicht Q. Proc.

- log. vs. phys. Alg.

- Queryeval.

- Optimie- rungen

- Queryplan- erzeugung

- Kosten- modell.

Infrastruktur

Erweiterbar-keit 1

Erweiterbar-keit 2

Adaptivität


Plädoyer für Heuristiken für die Queryoptimierung

Anzahl der möglichen Querypläne wächst exponentiell mit der Anzahl der Join-Prädikate.

Vollständige Aufzählung der Pläne i.d.R. nur möglich für Queries mit ca. sechs Joins.

Grosse Queries kommen vor: Datenbank-Frontends erzeugen automatisch

komplexe Query-Statements, komplexe Sichtdefinitionen, die der User i.a. nicht sieht, OLAP-Queries.

Menge möglicher Querypläne vergrössert sich in nicht-konventionellen Szenarien. - Beispiele: Client-Server Verteilung, benutzerdefinierte Prädikate.

D.h. man kann in Wirklichkeit nicht alle Pläne aufzählen.

Motivation

Query Proc.Basics

-Übersicht Q. Proc.

- log. vs. phys. Alg.

- Queryeval.

- Optimie- rungen

- Queryplan- erzeugung

- Kosten- modell.

Infrastruktur

Erweiterbar-keit 1

Erweiterbar-keit 2

Adaptivität

Documents

Interoperable Informationssysteme - 1 Klemens Böhm Systeme 2: Query Processing - Grundlagen