Progress SQL92 Optimalizátor

Jan Lánskýzizelevak@matfyz.cz

19.2.2004 Progress SQL92 Optimalizátor 2

Obsah

1) Úvod a přehled2) SQL92 server a optimalizátor3) Stromová reprezentace dotazu4) Transformace dotazu před optimalizací5) Optimalizace6) Prohlížení výsledku optimalizace7) Ovlivnění optimalizace

19.2.2004 Progress SQL92 Optimalizátor 3

1. Úvod a přehled

• Progress SQL92 server• Systém na vykonávání SQL příkazů z různých

klientů (ODBC, JDBC, embedded SQL)• Skládá se z mnoha komponent, např.:

• Komunikační manažer – komunikace s klienty• Relační ukládací manažer – I/O operace• Optimalizátor dotazů

19.2.2004 Progress SQL92 Optimalizátor 4

1. Úvod a přehled

• Optimalizátor dotazů• Najít nejrychlejší cestu, jak vykonat dotaz a

vrátit požadovaná data v co nejkratším čase.• Vyrobí specifický plán vyhodnocení• Vybere metody vyhodnocování a jejich pořadí

19.2.2004 Progress SQL92 Optimalizátor 5

1. Úvod a přehled

• Postupy optimalizátoru• Dekompozice – rozklad dotazu na základní

elementy (tabulky, sloupce, predikáty)• Operace relační algebry (projekce, restrikce,

spojení, třídění)• Kompozice – spojovaní restrikcí nebo spojení

do sekvencí navazujících kroků (pipeline)• Cenová analýza – vybírá nejlevnější operace

19.2.2004 Progress SQL92 Optimalizátor 6

2. SQL92 server a optimalizátor

Optimalizátor

Cenový m.

Statistický m.

Prováděcí m.Autorizační m.Parser Pohledový m.

Manažer SQL dotazů

Transakční relační ukládací manažer

Komunikační m.

M. Schémat

19.2.2004 Progress SQL92 Optimalizátor 7

3. Stromová reprezentace dotazu

• Dotaz se přetransformuje do relační algebry• Operace jsou uzly stromu

• Restrikce (where a join klauzule)• Projekce • Třídění (order by kluazule)• Tabulka (čtení dat z tabulky za pomoci

defaultního indexu (prohlížení tabulky) nebo speciálního indexu (prohlížení indexu)

19.2.2004 Progress SQL92 Optimalizátor 8

3. Stromová reprezentace dotazu• SELECT Jméno, DatumObjednávky• FROM zákazníci, objednávky• WHERE objednávky.DatumObjednávky = objednávky.DatumDodání

Tabulkazákazníci

projekce

restrikce

spojení

Tabulkaobjednávky

Jméno, DatumObjednávky

objednávky.DatumObjednávky = objednávky.DatumDodání

19.2.2004 Progress SQL92 Optimalizátor 9

4.Transformace dotazu

• Počáteční strom dotazu vyrobí parser• Poddotazy a predikáty ALL a ANY nahradí

spojením• Pohledy jsou nahrazeny svojí definicí

19.2.2004 Progress SQL92 Optimalizátor 10

5. Optimalizace

• Fáze optimalizačního procesu• Restrikce co nejblíže listům• Použití indexů pro restrikce• Optimalizace spojení• Optimalizace třídění• Použití indexů pro MAX a MIN funkce• Setřídění před prohledáváním

19.2.2004 Progress SQL92 Optimalizátor 11

5. Optimalizace

• Informace pro počítání ceny dotazu• Cenové metriky pro různé typy operací• Definice indexů• Vlastnosti spojovacích algoritmů• Selekce sloupců• Filtrovací faktory• Velikosti tabulek

• Je-li na výběr více variant, bere se ta nejlevnější

19.2.2004 Progress SQL92 Optimalizátor 12

5.1 Restrikce směrem k listům

• Posunutím restrikcí blíže listům se sníží množství zpracovávaných dat.

• Restrikce použité při spojení nelze posunout níže než je ono spojení.

• Je-li více restrikcí posunuto na stejnou pozici, lze je spojit do jedné.

19.2.2004 Progress SQL92 Optimalizátor 13

5.1 Restrikce směrem k listům• SELECT zaměstnanci.Jméno• FROM zaměstnanci, oddělení• WHERE zaměstnanci.ČísloOddělení = oddělení.ČísloOddělění• AND zaměstnanci.Plat>4000 AND zaměstnanci.Plat<=6000

spojení

t. zaměstnanci

projekce

restrikce

t. oddělení

zaměstnanci.Jméno

zaměstnanci.ČísloOddělení = oddělení.ČísloOddělění

zaměstnanci.Plat>4000, zaměstnanci.Plat<=6000

19.2.2004 Progress SQL92 Optimalizátor 14

5.2 Použití indexů pro restrikce

• Máme-li index na atribut v restrikci nemusíme procházet tabulku sekvenčně

• Při rovnosti na několik hodnot provedeme několik vyhledání podle indexu

• V případě intervalu najdeme jeho jednu mez a sekvenčně procházíme do nelezení druhé meze.

19.2.2004 Progress SQL92 Optimalizátor 15

5.2 Použití indexů pro restrikce• SELECT zaměstnanci.Jméno• FROM zaměstnanci• WHERE zaměstnanci.ČísloOddělení = 10 • AND zaměstnanci.Plat>6000

t. zaměstnanci

projekce

restrikce

zaměstnanci.Jméno

Index ZaměstnanciIndČísloOddělení = 10

zaměstnanci.Plat>6000

19.2.2004 Progress SQL92 Optimalizátor 16

5.2 Použití indexů pro restrikce

• Výběr nejlepšího indexu• Předpříprava výrazů v predikátech• Výběr indexů použitelných pro restrikce• Výběr nejlepšího

19.2.2004 Progress SQL92 Optimalizátor 17

5.2.1 Transformace predikátů

• sloupec = konstanta1 OR sloupec = konstanta2 sloupec IN (konstanta1, konstanta2)

• sloupec = konstanta1 OR sloupec IN (konstanta2, konstanta3) sloupec IN (konstanta1, konstanta2, konstanta3)

• sloupec LIKE “ABC%“ sloupec BETWEEN “ABC + %x0“ AND “ABC + %xff“

19.2.2004 Progress SQL92 Optimalizátor 18

5.2.2 Výběr indexů

• Pro každý predikát se najdou indexy které obsahují sloupce z predikátu.

• Pro takto najité indexy se zkontroluje zda se dá použít na operátor predikátu (=,<,, atd.)

• Pokud je index víceatributový, testuje se shoda klíče se sloupci predikátu

19.2.2004 Progress SQL92 Optimalizátor 19

5.2.3 Výběr nejlepšího index

• Pokud dala předchozí fáze alespoň jednoho kandidáty

• Výběr nejlepšího kandidáta je založen na nejnižší ceně.

• Cena vítěze se porovná se sekvenčním procházením a lepší z variant se použije.

19.2.2004 Progress SQL92 Optimalizátor 20

5.3 Optimalizace spojení

• Řešíme dva odlišné problémy• Pořadí spojení • Algoritmus pro spojení

19.2.2004 Progress SQL92 Optimalizátor 21

5.3.1 Pořadí spojení

• Zjištění velikostí sekektivit tabulek, které se budou spojovat.

• Join kardinalita = velikost * selektivita• Jako první se bude provádět spojení, které bude

mít nejmenší join kardinalitu výsledku.• Join kardinalita (A join B on podm)= join

kardinalita A * join kardinalita (B) * selektivita (podm)

19.2.2004 Progress SQL92 Optimalizátor 22

5.3.1 Pořadí spojení - příklad

Jsou spojovací podmínky mezi: T2 a T1 a T3, mezi T1 a T3 a T4, mezi T3 a T4

Řešení:1. T2 a T12. Výsledek1 s T33. Výsledek2 s T4

tabulka T1 T2 T3 T4kardinalita 3000 2000 5000 7000

19.2.2004 Progress SQL92 Optimalizátor 23

5.3.2 Výběr algoritmu spojení

• Typy algoritmů• Rozšířený algoritmus hnízděných cyklů (ANL)• Spojení sléváním• Algoritmus hnízděných cyklů

• Optimalizátor vybere algoritmus, jehož předpoklady jsou splněny a má nejmenší cenu.

19.2.2004 Progress SQL92 Optimalizátor 24

5.3.3 Algoritmus ANL

• Rozšířený algoritmus hnízděných cyklů• Prochází levý podstrom a pro každý jeho řádek

provede vyhledání podle indexu v pravém podstromu a v něm pak sekvenčně dohledává stejné hodnoty.

• Nutné podmínky• Pravý podstrom má index na atribut podle kterého se

provádí spojení• Tento index nebyl použit pro žádné jiná hledání

19.2.2004 Progress SQL92 Optimalizátor 25

5.3.4 Spojení sléváním

• Dvoufázový algoritmus• 1. fáze sort • 2. Fáze slévání

• Většinou nebývá použit, ANL mívá nižší cenu.

19.2.2004 Progress SQL92 Optimalizátor 26

5.3.5 Vnořené cykly

• Ve vnějším cyklu procházíme výsledek levého podstromu a pro každý jeho řádek projdeme celý výsledek pravého podstromu.

• Může být použit kdykoliv, ale má vysokou cenu.

• Pro malé velikosti podstromu nicméně může být nejvýhodnější.

19.2.2004 Progress SQL92 Optimalizátor 27

5.4 Optimalizace třídění

• Optimalizují se dva typy situací• Zabránění redundantnímu třídění• Náhrada sekvenčního prohledávání a

následného třídění za třídění a vyhledávání podle setříděného indexu.

19.2.2004 Progress SQL92 Optimalizátor 28

5.4.1 Redundantní třídění

• Netřídíme, pokud ke třídění dostaneme setříděný vstup.• Například máme-li na dotaz, ve kterém se na

jeden atribut používá GROUP BY a ORDER BY, stačí třídit jednou.

19.2.2004 Progress SQL92 Optimalizátor 29

5.4.2 Předsunutí třídění

• Náhrada sekvenčního prohledávání a následného třídění za třídění a vyhledávání podle setříděného indexu.

19.2.2004 Progress SQL92 Optimalizátor 30

5.5 Užití indexů pro MAX, MIN

• Existuje-li index na atribut, který je argumentem funkce, použijeme ho, místo sekvenčního procházení tabulky.

• Podíváme se na první (nebo poslední) indexovanou hodnotu.

19.2.2004 Progress SQL92 Optimalizátor 31

5.6 Setřídění před prohledáváním

• Někdy se může vyplatit místo sekvenčního vyhledávání atribut setřídit a vytvořit index.

• Výhodné pro tabulky v listech.• Nebo, hledáme-li v tabulce postupně téměř

všechny hodnoty.

19.2.2004 Progress SQL92 Optimalizátor 32

6. Prohlížení optimalizace

• Progress SQL92 Server má virtuální systémovou tabulku _Sql_Qplan

• create table “Sql_Qplan“ (• “_Pnumber“ integer not null,• “_Ptype“ integer not null,• “_Dtype“ integer not null,• “_Description“ varchar(255) not null,• “_Dseq“ integer not null• );

19.2.2004 Progress SQL92 Optimalizátor 33

6. Prohlížení optimalizace

• _Pnumber – číslo plánu, řazeno sestupně• _Ptype – číslo typu plánu• _Dtype - nepoužito• _Description – slovní popis plánu• _Dseq – číslo řádku plánu

19.2.2004 Progress SQL92 Optimalizátor 34

7. Ovlivnění optimalizace

• Plán vyhodnocení je závislý na optimalizačním algoritmu a na vstupech používaných optimalizátorem• Samotný SQL dotaz• Informace ze schémat tabulek, indexy• Statistické informace o frekvenci dat bez

indexů, statistickém rozložení dat, velikost tabulek.

19.2.2004 Progress SQL92 Optimalizátor 35

7. Ovlivnění optimalizace

• WHERE predikáty ovlivňují počty zpracovávaných řádků, čím více selektivní, tím lépe.

• Používané sloupce by měli mít index.• Pravidelně volat UPDATE STATISTICS

19.2.2004 Progress SQL92 Optimalizátor 36

Literatura

• The Progress RDBMS SQL92 Optimizer• Progress Version 9.1D• Author: SQL Engineering Group• Edition 1, September 2002