Advanced Databases
Query optimisation
Topic 2: query processing aspects query optimisation
Outline: Basisregels algebraïsche herschrijving Van SQL naar XRA Schattingen Queryplan-generatie
1
Algebraïsche herschrijving
2
Van SQL naar XRA
• gebruik de cascading rule voor de selectie om de conjunctie “op maat”” te knippen: σP1, …, Pn(E) = σ P1(…(σ Pn(E))…) • push down selections waar mogelijk • combineer Cartesian Products met selecties om deze als join te formuleren • optimaliseer de joinvolgorde • voeg projecties toe om de grootte van operanden te minimaliseren • onderken mogelijkheden voor combineren operatoren (σ en π samen in één scan) en pipelining
Syntax voor simpleSQL
::= <SFW> ::= () <SFW> ::= SELECT <SelList> FROM WHERE
3
4
Van SQL naar XRA
Van SQL naar XRA
Syntax voor simple SQL
Voorbeeld:
::= ::= ::= ::=
MovieStar (name, address, gender, birthdate) StarsIn (title, year, starName)
AND IN = LIKE <Pattern>
::= 5
6
1
Van SQL naar XRA: voorbeeld
Van SQL naar XRA: voorbeeld
SELECT title FROM StarsIn WHERE starName IN ( SELECT name FROM MovieStar WHERE birthdate LIKE ‘%1960’ )
7
Van SQL naar XRA: voorbeeld
8
Van SQL naar XRA: voorbeeld
Transformatie van in SFW parse tree naar XRA parse tree 1. 2. 3.
Start met het cartesisch product van alle relaties in de Zet hierboven de selectie met Zet hierboven een projectie op de <SelList>
9
10
Van SQL naar XRA: voorbeeld
Van SQL naar XRA: voorbeeld
Complicatie: IN
Complicatie: IN
11
12
2
Van SQL naar XRA: voorbeeld
Van SQL naar XRA: voorbeeld
SELECT DISTINCT m1.title, m1.year FROM StarsIn m1 WHERE m1.year – 40 <= ( SELECT AVG(birthdate) FROM StarsIn m2, MovieStar s WHERE m2.starName = s.name AND AND m1.title = m2.title AND m1.year = m2.year )
13
Van SQL naar XRA: voorbeeld
14
Van SQL naar XRA: voorbeeld
15
Van SQL naar XRA
16
Schattingen
Groeperen van commutatieve en associatieve binaire operatoren
De keuze voor een bepaalde executiemethode wordt bepaald aan de hand van schattingen van de kosten. Deze worden bijgehouden door het DBMS (system catalog) Voor de base tables zijn allerlei statistieken voorhanden Voor tussentijdse resultaten zijn er methoden om deze gegevens te schatten 17
18
3
Schattingen
Schattingen: projectie
Entries van de catalog ten behoeve van tabel R
Catalog voor R’ := πA(R)
• B(R): het aantal blocks dat R omvat • T(R): het aantal tupels in R • V(R.A): het aantal verschillende waarden van attribuut A in R • Min(R.A): minimale waarde in kolom A • Max(R.A): maximale waarde in kolom A • S(R): size; breedte tupel in bytes
• T(R’) = • V(R’.A) = Catalog voor R’ := πAB(R)
19
20
Schattingen: histogrammen
Schattingen: selectie
Gedetailleerde info betreffende waarden in kolom A.
Catalog voor R’ := σP(R) onderscheid: A = c, A <= c, A <> c
• Equal-width histogram frequenties gespecificeerd per interval van vaste grootte
• T(R’) = • V(R’.A) =
• Equal-height histogram intervalgrootte is variabel om ruwweg dezelfde kolmhoogte te verkrijgen (percentielen)
21
• Most-frequent-values individuele waarden gespecificeerd, met histogrammen voor de overige waarden
Schattingen: histogrammen
Schattingen: histogrammen
Equal width histogram
Equal-height histogram 0%
leeftijd 0 23
20%
15
40%
60%
80%
31
49
72
22
100%
110 24
4
Schattingen: histogrammen
Schattingen: join
Onderhoud van histogrammen
Catalog voor U := R
S
met joinattribuut A
• Compleet, periodiek • Incrementeel
• T(U) = • V(U.A) = • V(U.B) =
– aanpassing T(R) voor elke update – schat T(R) aan de hand van # blocks in B-tree index
25
Nog meer schattingen
26
Physical plan space
union intersection difference duplicate elimination grouping
Kan nogal groot zijn Case study: join ordering gangbare restrictie: left deep trees (zie links)
27
Join ordering
28
Dynamic programming De beste manier om R1, R2, …, Rn te joinen:
Dynamic programming Greedy heuristic kies in elke stap de relatie die het kleinste tussenresultaat geeft Vuistregel bereken “exacte” oplossing tot n ~= 6 pas daarboven een heuristiek toe
29
R1 join (de beste manier om R2, R3, …, Rn te joinen)
R2 join (de beste manier om R1, R3, …, Rn te joinen) ….
Rn join (de beste manier om R1, R2, …, Rn-1 te joinen)
30
5
Dynamic programming: voorbeeld
Dynamic programming: voorbeeld
31
Dynamic programming: voorbeeld
32
Dynamic programming: voorbeeld
33
34
6
