SQL Spreadsheet. Jakub Čermák

SQL Spreadsheet Jakub Čermák [email protected]

Agenda • • • • •

Úvod, OLAP, Spreadsheet Rozšíření jazyka SQL pro spreadsheety Parametrizace Implementace − Analýza a optimalizace dotazu − Datová struktura, vyhodnocení

Výkonnost

OLTP, OLAP •

•

Online transaction processing − např. relační databáze − zaměřena na snadnou modifikaci ve víceuživatelském prostředí − uchovává jednotlivé relace

Online Analytical Processing − analýza (obchodních trendů) velkých objemů dat − mnohem (1000x) rychlejší než OLTP − uchovávání agregací namísto jednotlivých záznamů, přímý přístup přes indexy

OLAP kostka • • •

•

Tabulka faktů (fact table) − vícedimenzionální tabulka s daty − buňky (cell) jsou adresovatelné (očíslované), na rozdíl od relací

Measures − jednotlivé hodnoty (označené dimenzemi)

Dimenze (dimension) − Popisky measures

Příklad: − f(t, r, p,s ,c) − time, region, product − sales, cost

Spreadsheet • • •

př. Microsoft Excel pro analýzu obchodních dat vhodnější než SQL databáze − přímé adresování prvků, podpora formulí, dobré UI

Ale … − pouze 2D (řádek, sloupec) − málo škálovatelné

SQL Spreadsheet • •

•

rozšíření standardu SQL pro práci s ochodními daty a provádění analýz Oproti SQL − adresování dimenzemi, relace jsou ndimenzionální pole − podpora formulí, dopočítávání hodnot − snazší zápis, vyšší efektivita OLAP analýz − rekurzivní a cyklické formule

Oproti Spreasheetu − n-dimenzionální − lépe škálovatelný, mnohem výkonnější, větší podpora funkcí

Agenda • • • • •


Výkonnost

Definice • • •

•

PARTITION column (PBY) − rozdělení dat do disjunktních podmnožin (partitions) − podmnožiny uplně nezávislé, prostor pro optimalizace

DIMENSION column (DBY) − popisky dat, unikátní identifikace buňky v dané partition

MEASURES column (MEA) − vlasní data

Příklad: − f(t, r, p,s ,c) − time, region, product; sales, cost

Syntaxe spreadsheet clause <existing parts of a query block> SPREADSHEET PBY(cols) DBY(cols) MEA(cols) <processing options> (,,..,)

Příklad SELECT r,p,t,s FROM f SPREADSHEET PBY(r) DBY(p,t) MEA(s) ( s[p=‘dvd’,t=2002]=s[p=‘dvd’,t=2001]*1.6, s[p=‘vcr’,t=2002]= s[p=‘vcr’,t=2000]+s[p=‘vcr’,t=2001], s[p=‘tv’,t=2002]=avg(s)[p=‘tv’,1992
current value

SPREADSHEET PBY(r) DBY(p,t) MEA(s) ( s[‘vcr’,t<2002] = avg(s)[‘vcr’, cv(t)-2<=t
UPDATE / UPSERT • • • •

Mějme s[‘vcr’,t=2002] = … Co když daná buňka neexistuje? UPSERT mode (výchozí) − UPSERT s[‘vcr’,t=2002] = … − vytvoří buňku pokud neexistuje, jinak update

UPDATE mode − UPDATE s[‘vcr’,t=2002] = … − ignoruje neexistující buňky

•

Ale co udělá UPSERT s[‘tv‘, *] ?

Calculated member • • •

Nová dimenze, která není ve fact table; hodnoty se vypočítávají formulí Příklad − SPREADSHEET PBY(r) DBY(p,t) MEA(s) − (UPSERT s[‘tv’,*]=s[‘black-tv’, cv()] + s[‘white-tv’,cv()]) Konstanta

Je zkratkou za − UPSERT s[‘tv’,FOR t IN (SELECT DISTINCT t FROM input set)] = NULL, − UPDATE s[‘tv’,*]=s[‘black-tv’,cv()] + s[‘white-tv’,cv()]

Referenční spreadsheety • • •

Mám tabulku s jinou dimensionalitou − př. budget allocation (region, prediction)

Readonly přístup k jiným tabulkám během počítání Obdoba relačního JOINu − rychlejší, optimalizovanější

Referenční spreadsheety – př. SELECT r,t,s FROM f GROUP BY r,t SPREADSHEET REFERENCE budget ON (SELECT r,p FROM budget) DBY(r) MEA(p) DBY(r,t) MEA(s) ( s[‘west’,2002]=p[‘west’]*s[‘west’,2001], s[‘east’,2002]= s[‘east’,2001]+s[‘east’,2000] )

Řazení •

Řazení vyhodnocování jednotlivých buňek − Pokud je výpočet závislý na minulých hodnotách − s[‘vcr’,t<2002] = avg(s)[‘vcr’, cv(t)-2<=t
− ORDER BY

•

−

s[‘vcr’,t<2002] ORDER BY t ASC= avg(s)[‘vcr’, cv(t)-2<=t
Řazení vyhodnocování formulí − Při závislostech jednotlivých formulí na sobě (např. součet prodejů typů TV a pak součet všech TV + DVD) − Pro acyklické smečky formulá − Automatické – v lexikografickém pořadí − SEQUENTIAL ORDER – podle pořadí uvedení

Cykly a rekurze • • • • •

Formule jsou na sobě cyklicky závislé Nelze vyhodnocovat napoprvé př. s[1] = s[1] / 2 Omezení (výpočet běží jedna nenastane) − na počet iterací − na bool podmínku

Funkce PREVIOUS – minulá hodnota

SPREADSHEET DBY(x) MEA(s) ITERATE(10) UNTIL (PREVIOUS(s[1])-s[1] <= 1) (s[1]=s[1]/2)

Cyklus – př. SELECT account,b FROM SPREADSHEET DBY(account) MEA(balanceb) RULES IGNORE NAV ITERATE(100) UNTIL(ABS(b[‘net’]-PREVIOUS(b[‘net’]))<0.01) ( F1:b[‘interest’]=b[‘net’]*0.30, F2:b[‘net’]=b[‘salary’]+b[‘capitalgains’] - b[‘interest’]-b[‘tax’], F3:b[‘tax’]=(b[‘salary’]-b[‘interest’])*0.38 + b[‘capitalgains’]*0.28 )

Další instrukce • • •

ITERATE, AUTOMATIC|SEQUENTIAL ORDER nastavení UPSERT/UPDATE mode jako default IGNORE NAV – považuj NULL za 0 pro aritmetické operace

Změny tabulky faktů • •

Ve výchozím použití NEUPRAVUJE původní relaci (ani UPSERT) MERGE – propagace vypočítaných buňek zpět do relace

Změny tabulky faktů – př. MERGE INTO f USING ( SELECT r,p,t,s FROM f SPREADSHEET PBY(r) DBY(p,t) MEA(s) ( UPSERT s[‘tv’,*]=s[‘black-tv’,cv()] + s[‘white-tv’,cv()] ) ) v ON f.r = v.r AND f.p = v.p AND f.t = v.t WHEN MATCHED THEN UPDATE SET f.s=v.s WHEN NOT MATCHED THEN INSERT VALUES(v.r, v.p, v.t, v.s)

Agenda • • • • •


Výkonnost

Parametrizace SQL bloků • • •

Vytváření uložených funkcí pouze deklarativní (SQL) příkazy (narozdíl od Oracle, MSSQL) Silně typové funkce X slabě typové fce − kontrola typů při vytváření X spuštění − slabě typové: ANYTYPE jako typ

•

Při vykonávání se „dosadí“ do vnějšího dotazu − možnost optimalizace mezi dotazy

Příklad CREATE FUNCTION region_sales_2002 (f TABLE OF ROW(r VARCHAR,p VARCHAR,t INT,s NUMBER), region VARCHAR) RETURN MULTISET LANGUAGE SQL AS SELECT r,p,t,s FROM f_param f WHERE r = region SPREADSHEET PBY(r) DBY(p,t) MEA(s) ( s[‘vcr’,2002]=s[‘vcr’,1998]+s[‘vcr’,1999], s[‘dvd’,2002]=avg(s)[‘dvd’,1990
) SELECT r,p,t,s FROM region_sales_2002 ((SELECT reg,prod,time,sale FROM t),‘west’) WHERE p= ‘tv’;

Param. SQL Spreadsheet clause • •

Vytváření uložených procedur přijímající už spreadsheet (rozdělený na PBY, DBY, MEA) neboli vícedimenzionální pole − srovnej: předchozí přijímá relace

obsahující pouze spreadsheet klauzuli − srovnej: předchozí obsahuje SQL příkazy

Příklad CREATE PROCEDURE net_present_value (ARRAY DBY(i IN INTEGER) MEA(amount IN NUMBER,npv OUT NUMBER), rate NUMBER) LANGUAGE SQLSPREADSHEET AS RULES IGNORE NAV ( npv[1]=amount[1], npv[i>1] ORDER BY i = amount[CV(i)/POWER(1+rate,CV(i)]+ npv[CV(i)-1] )

Volání •

Přetypování − 2D pole s jednou dimenzí konstantní ([‘vcr‘, *]) − pokud tvar pole je kompatibilní s tvarem spreadsheetu

•

− implicitní (defaultní) přetypování − znovupoužití datových struktur => levné

Volání ze spreadsheet bloku

vyber MEA amount a npv a vytvoř 2D pole (pořád adresované všemi DBY sloupci)

SELECT year,i,prod,amount,npv FROM cash_flow SPREADSHEET DBY(prod,i) MEA(year,s,NULL npv) ( net_present_value((amount,npv)[‘vcr’,*],0.14), net_present_value((amount,npv)[‘dvd’,*],0.14) )

Agenda • • • • •


Výkonnost

Evaluation overview • •

•

•

3 fáze analýza a optimalizace − graf závislostí formulí − definice oboru (scope) dotazu − transformace formulí, přesuny a optimalizace predikátů − ....

tvorba datové struktury − random access struktura (hash tabulka, ale možné i jiné implementace)

vyhodnocení formulí − 3 různé algoritmy

Agenda • • • • •


Výkonnost

1. Graf závislostí • • •

• • •

orientovaný graf, vrcholy jsou formule, hrany jsou závislosti formulí R(F) buňky referencované na pravé straně L(F) buňky modifikované na levé straně

Formule F1 závisí na F2 (F2 -> F1) právě tehdy když R(F1) má neprázdný průnik s L(F2) Složité formule: předpoklad, že referencují vše sestavení částečného uspořádání formulí − rozdělení formulí do úrovní − formule závisí pouze na těch z nižší úrovně

1. Graf závislostí (2) • • • • • •

Zjištění cykličnosti grafu (výběr algoritmů) Nezávislé formule lze vyhodnocovat současně Závislé se musí vyhodnocovat popořadě Počet úrovní = minimální počet scanů − lze dosáhnout pro acyklický graf

Izolování acyklických částí grafu − optimalizace (acykl. alg. jsou rychlejší)

Pro sekvenční vyhodnocování − pořadí je pevně dané, ale graf se generuje pro minimalizaci počtu scanů

2. Prořezání (pruning) formulí • •

Vyhození formulí, které nakonec nebudou potřeba Definice:

•

− hodnota není využitá žádné další formuli − změněné buňky jsou vyfiltrovány vnějším dotazovacím blokem nebo nejsou referencovány ve vnějším bloku Algoritmus − sink node – takový, ze kterého nevedou hrany − −

−

FS <- množina všech sink nodes WHILE (FS is not empty), vyber Fi − IF (Fi splňuje definici): vyhoď Fi z množiny formulí vyhození může generovat nové sink nodes, ty je třeba přidat do FS

Příklad SELECT * FROM ( SELECT r, p, t, s FROM f SPREADSHEET PBY(r) DBY(p,t) MEA(s) UPDATE ( F1:s[‘dvd’,2000]=s[‘dvd’,1999]*1.2, F2:s[‘vcr’,2000]=s[‘vcr’,1998]+s[‘vcr’,1999], F3:s[‘tv’,2000]=avg(s)[‘tv’,1990
3. Přepis formulí •

Snížení počtu přepisů omezením podmínek

SELECT * FROM ( SELECT r,p,t,s FROM f SPREADSHEET PBY(r) DBY(p,t) MEA(s,c) UPDATE ( F1:s[*,2002]=c[cv(p),2002]*2, ) ) WHERE pin(‘dvd’,‘vcr’) and t ≥ 2000;

•

F1 může být vyhodnocena jen pro F1’:s[pin(‘dvd’,‘vcr’),2002]=c[cv(p),2002]*2

•

Výhodné spojit s předchozím krokem (generuje nové sink nodes)

4. Predicate pushing • •

posun PBY predikátů mezi vnitřním a vnějším blokem − vždy správné, filtrujeme celé partitiony

posun mezi nezávislými dimenzemi − nezávislá dimenze d − na levé i pravé straně formule má vždy stejnou hodnotu

•

− na d lze nahlížet jako na PBY

ohraničující obdélník (bounding rectangle) − rozsah dimenzí v dané formuli, zarovnaný na čtverec − pro dotaz: sjednocení ohraničujících obdélníků všech formulí − tyto spojené predikáty lze také posouvat

5. optimalizace agregací SELECT r,p,t,s,ps FROM t SPREADSHEET PBY(r) DBY(p,t) MEA(s,t,0 ps) UPDATE ( ps[*,*]=s[cv(p),cv(t)-1]* (1+slope(s,t)[cv(p),cv(t)-5<=t<=cv(t)-1]) )

•

•

naivní implementace: moc scanů díky agregaci nalevo lze nahradit klouzavou funkcí − operuje nad klouzavým (sliding) oknem − nativní implementace v Oracle: −

slope(s,t) OVER (PARTITION BY p ORDER BY t RANGE BETWEEN 5 PRECEDING AND 1 PRECEDING)

5. optimalizace agregací •

fce slope je tvořena fcemi count() a sum() a tedy spadá do kategorie „algebraických agregací“, které lze takto přepsat

•

obecně lze použít pokud: − formula není „samo“cyklická − 1 dim. agr. fce definuje okno relativní k cv() a ostatní dim. jsou kvalifikovány hodnotami z cv()

6. Opt. kvalifikovaných agregací • • •

agregace adresovaná přes diskrétní dimenzi (1
2. přístup vyžaduje málo náhodných přístupů − kvalifikovaná agregace − struktury jsou optimalizované pro náhodný přístup Efektivita:

Příklad SPREADSHEET DBY(p,t) MEA(s,0 mavg) ( mavg[‘dvd’,FOR t FROM 2000 TO 2001]= 1.05*AVG(s)[cv(),cv()-3<=t<=cv()-1] )

mavg[‘dvd’,FOR t FROM 2000 TO 2001]= 1.05*AVG(s)[cv(),FOR t FROM cv()-3 TO cv()-1 INCREMENT 1]

Agenda • • • • •


Výkonnost

Tvorba datové struktury • • •

mapování řádků do vícedimenzionální struktury podpora: náhodný přístup, efektivní přidávání 2úrovňová hashovací struktura − − − −

•

hash partition – na základě PBY sloupců 2. úroveň – na základě PBY&DBY sloupců efektivní vyhodnocení, minimalizace paměti velikost podle ohraničujícího obdélníku a dostupné paměti (dvojnásobek)

kolize – vytváření řetězců

Datová struktura (2) • •

disková hash cache − při nedostatku paměti − minimalizace počtu zápisů na disk (LRU, dirty flagy,...)

podporované operace − probe, update, upsert, insert, scans (podle DBY)

Vykonávání •

3 algoritmy

Auto-acyklický alg. • • •

Pro acyklické dotazy (nebo jejich části) Procházení podle úrovní (dependency graph) pro každou partition (PBY) a úroveň − pro každý záznam: spočítej agregaci (1 scan) − vyhodnoť jednoduché (bez existenčních podm. vlevo) formule (žádný scan) − pro každý záznam (scan) − najdi existeční formule (EF) pro daný záznam − pro každý záznam (scan) a spočítej každou agregaci z EF − vyhodnoť EF

Auto-cyklický alg. •

pro formule s cykly nebo mají příliš komplexní predikáty 1. vytvoření silně souvislých komponent − podle grafu závislostí

2. neSSC formule vyhodnoť jako acyklické 3. formule v SSC vyhodnoť max. Nkrát − při konvergenci se zastaví − N = počet buňek upserted nebo updated v 1. iteraci − acykl. graf zkonverguje po max. N iteracích −

nejhorší případ: formule jsou v opačném pořadí

− jinak cykl. graf – ohlásí chybu

Sekvenční alg. • •

Formule jsou vyhodnovány podle daného pořadí Obdoba auto-acyclic alg.

Paralelizace •

Možnost paralelizace dotazů podle PBY

Agenda • • • • •


Výkonnost

hash-join vs.sql spreadsheet

•

Data: 4 dimenzionální kostka, přes 22M řádků

Závěr, dotazy

SQL Spreadsheet. Jakub Čermák

Recommend Documents