PIQL PERFORMANCE INSIGHTFUL QUERY LANGUAGE. NDBI006, Jan Drozen,

PIQL – PERFORMANCE INSIGHTFUL QUERY LANGUAGE NDBI006, Jan Drozen, 7.4.2015

Motivace Moderní (typicky webové) projekty vyžadují:  zpracování velkého množství dat  minimální dobu odezvy  maximální propustnost (počet požadavků za jednotku času)  minimální náklady  horizontální

škálovatelnost

CAP-teorém 

Consistency 



Availability 



všechny uzly vidí stejná data systém bude dostupný (bude vracet odpovědi na dotazy)

Partitioning 

systém je distribuovaný a je schopný pracovat i po výpadku některé jeho části

CAP-teorém 

V distribuovaném systému nelze zaručit stoprocentně C, A i P najednou.  dokázáno  možnost  nejsou

přesouvat váhu podle důležitosti

to binární čísla  např. slabší konzistence za cenu vyšší dostupnosti

Motivace 

přechod od tradičních relačních SŘBD k NoSQL systémům v



dnešní době možná spíše už NewSQL

Př.  Facebook

– 200 000 000 000 zobrazení stránky s přístupem do databáze za měsíc



✞ SQL

Přístup bez SQL 

Používají se jednoduchá úložiště typu klíč-hodnota  get(),



put(i)

Dotazovací logika je implementovaná na aplikační úrovni  programování

na nízké úrovni

Přístup bez SQL 

Nemáme spravovatelnost  zálohování / obnovy  dobře prozkoumané a ověřené postupy  podporu 



Ale získáme kontrolu nad ukládáním/získáváním dat  schopnost určit složitost dotazů 

PIQL   

 

Performance Insightful Query Language [:pickle:] „podmnožina“ SQL s předvídatelnou výkonností/složitostí nezávislý na datové vrstvě automatický výběr a údržba indexů

PIQL 





garantuje horní mez na počet a velikost vstupních / výstupních operací provedených při vyhodnocování dotazu předpokládá, že pracuje nad distribuovaným úložištěm typu klíč-hodnota odezva v podobě složitosti v nejhorším případě při kompilaci dotazu  

primárně předdefinované dotazy (obdobně jako uložené procedury) podporované i interaktivní dotazy

PIQL 



jazyková podpora pro efektivní zpracování objemných výsledků dotazů (např. stránkování) možnost výměny konzistence za dostupnost nebo výkon

Alternativní přístup  

komplexní aplikační vrstvy př. Cassandra čtyřdimenzionální tabulka  řádky obsahují supersloupce  ty obsahují rodiny sloupců  ty obsahují řádky hodnot  plus navíc volitelné časové razítko 

https://maxgrinev.files.wordpress.com/2010/07/twitterschema-tweets.png

Alternativní přístup 



př. vyhledání všech zpráv obsahujících dané slovo řešení: programátor musí ručně vytvořit invertovaný index podle obsahu zpráv

https://maxgrinev.files.wordpress.com/2010/07/twitterschema-tweets.png

Příklad pomocí PIQL QUERY inboxSearch FETCH message OF user BY recipient WHERE user = [this] AND message.text CONTAINS [1: word] ORDER BY timestamp

PIQL - předpoklady 

Dva základní předpoklady:  základní

operace datového úložiště typu klíč-hodnota mají předvídatelnou složitost bez ohledu na objem dat nebo frekvenci dotazů  jazyk je určen pro jednoduché dotazy (typicky pro webové aplikace)

PIQL 1.0 

data jsou uložena v silně typovaných entity-setech 

analogie relací

ENTITY user { string name, string password, string email, string hometown PRIMARY(name) }

ENTITY thought { int timestamp, string thought, FOREIGN KEY owner REF user PRIMARY(owner, timestamp) }

ENTITY subscription { bool approved, FOREIGN KEY owner REF user MAX 5000, FOREIGN KEY target REF user PRIMARY(owner, target) }

PIQL 1.0 - příklad 

aplikace SCADr   

zjednodušení Twitteru uživatel může sdílet krátké textové zprávy jiný uživatel může tyto zprávy sledovat

ENTITY user { string name, string password, string email, string hometown PRIMARY(name) }

ENTITY thought { int timestamp, string thought, FOREIGN KEY owner REF user PRIMARY(owner, timestamp) }

ENTITY subscription { bool approved, FOREIGN KEY owner REF user MAX 5000, FOREIGN KEY target REF user PRIMARY(owner, target) }

Parametrizované dotazy 

dotazy mají název 

 

dotazy vracejí pouze jeden typ dotazy mohou obsahovat parametry 





název funkce

[pořadí:parametr]

kompilátor může i tak určit horní mez složitosti potřebných operací při vyhodnocení dotazu se za parametry substituují konkrétní hodnoty

Příklad - selekce 

vyhledání profilu podle uživatelského jména: QUERY userByName FETCH user WHERE user.name = [1:name]



vyhledávací predikát je nadmnožinou primárního klíče 

stačí jedna get() operace

Příklad - selekce 

vyhledání uživatele podle města: QUERY FETCH WHERE LIMIT



není jasné, kolik uživatelů je z daného města (selektivita) 

 



userByHometown user user.hometown = [1:hometown] [1:count] MAX 100

ve schématu není definovaná kardinalita

v PIQL je povinná klauzule LIMIT pro predikáty neobsahující primární klíč provede se operace range_get() na (automaticky vytvořeném) indexu uživatelů podle města máme zajištěno, že ve výsledku nebude více než 100 řádků

Příklad - spojení 

nejnovější příspěvky některého uživatele: QUERY userThoughts FETCH thought OF user BY owner WHERE user.name = [1:username] ORDER BY timestamp LIMIT [2:count] MAX 100



omezený range_get() na indexu podle autora a časového razítka 

 

v tomto případě primární klíč

máme zaručeno, že se provede nejvýše jeden range_get(), který vrátí nejvíce 100 řádků spojení se dá provádět pouze na definovaných entitách

Stránkování 

v některých případech je LIMIT příliš restriktivní 



např. příspěvky daného uživatele setřízené chronologicky starší než posledních 100 příspěvků

v PIQL speciální PAGINATE operátor použitelný místo LIMITu  serializovatelný iterátor 





efektivní

bez iterátorů možné pomocí LIMITu 

neefektivní (kvadratické)

Omezení kardinality programátorem 

obvyklé v aplikacích  např.

na Facebooku nemohl mít v jednu dobu uživatel více než 5000 přátel



pomocí takovýchto omezení může kompilátor odhadovat horní mez složitosti  omezení

v rámci schématu, ne dotazu

Omezení kardinality programátorem příklad 

nejnovější příspěvky všech uživatelů, které odebírá daný uživatel a kde byl odběr schválený

1. Najde uživatele podle primárního klíče me.username = [1:username]

2. Najde všechny odběry uživatele pomocí relace owner mezi entitami user a subscription subscription of user by target

QUERY thoughtstream FETCH thought OF user AS friend BY owner OF subscription BY target OF user AS me BY owner WHERE me.username=[1:username] AND approved = true ORDER BY timestamp LIMIT [2:count] MAX 100

Omezení kardinality programátorem příklad 

nejnovější příspěvky všech uživatelů, které odebírá daný uživatel a kde byl odběr schválený

3. Najde všechny uživatele, na které se odběry váží pomocí relace target user OF subscription BY target

4. Vyfiltruje jen schválené odběry approved = true

5. Najde příspěvky nalezených uživatelů thought OF user BY owner

6. Setřídí podle časového razítka ORDER BY timestamp

QUERY thoughtstream FETCH thought OF user AS friend BY owner OF subscription BY target OF user AS me BY owner WHERE me.username=[1:username] AND approved = true ORDER BY timestamp LIMIT [2:count] MAX 100

PIQL – exekuční plán 

příklad: TopK(10) => 10 Sort(descending:timestamp) => 10 * 5000 IndexJoin("ent_thought", thought:owner == subscription:owner, descending: timestamp) => 10 * 5000 Select("approved" == true) => 5000 IndexLookup("ent_subscription", subscription:owner == [username]) => 5000 Total Reads = 5000 + 10 * 5000 Other Work = 5000 + (10 * 5000) * log(10 * 5000) + 10

PIQL – aktualizace schématu 

ve webových aplikacích často dochází ke změnám schématu  NoSQL



databáze typicky nemají dané schéma

je vhodné, aby změny schématu příliš nedegradovaly celkovou výkonnost systému

PIQL – aktualizace schématu 

Nasazení nového schématu probíhá v několika fázích:    

aplikace je aktualizována, pokud používá zastaralé atributy nebo dotazy zkompiluje se nová verze PIQL schématu obsahující nové atributy nebo dotazy nová verze schématu se začíná rozesílat na jednotlivé uzly aktualizují se entity a indexy tak, aby odpovídaly novému schématu  

 

aktualizuje se aplikační kód tak, aby používal nové atributy nebo dotazy nová verze je zpřístupněna 





pokud k nim někdo přistupuje postupně

postupně jednotlivým uživatelům všem najednou

Umožňuje konzistentní výkon v průběhu aktualizace a efektivní rollback v případě chyby ve kterékoli fázi.

PIQL - implementace 



napsáno v jazyce Scala programátor píšící webovou aplikaci spustí PIQL kompilátor na vytvořené schéma (entity a dotazy) 



vytvoří se JAR archiv obsahující třídy pro entity a dotazy

programátor pak využívá JAR knihovnu pro komunikaci s úložištěm

//Creation val u = new user u.name = "marmbrus" u.save //Retrieval val u = Queries.userByName("marmbrus")

PIQL - implementace 

pro dotazování se používají operátory, obdobně jako v relačních databázích  musí



být upraveny pro obecné úložiště klíč-hodnota

dvě kategorie  vzdálený

operátor  lokální operátor

PIQL – vzdálené operátory  

provádí akce na úložišti např.  načtení

entity podle primárního klíče, vyhledávání rozsahů podle indexu, spojení podle indexu



garantují omezený výsledek

PIQL – lokální operátory 



PIQL obdoba setřízení a selekce z relačních databází umožňují pracovat pouze s omezenými daty  pro

garanci výkonnosti

PIQL - konzistence 

možnost řízení konzistence pomocí mechanizmů blízkých NoSQL  quorum



v případě potřeby silné konzistence tradiční prostředky distribuovaných systému  dvoufázový

commit protokol

PIQL - atomicita  



obdobně jako konzistence možnost využívat write-ahead logování, pokud je vyžadována atomicita pokud jsou povoleny občasné inkonzistence v indexech, je možné logování vypnout

PIQL - výkonnost 





SCADr schéma, 10 000 uživatelů/server, každý 20 příspěvků, náhodné sledování příspěvků deseti uživatelů s uniformní distribucí test 1 uživatel/server, 5 minut načítání sledovaných příspěvků Amazon EC2 – 1.7GB RAM, 1 výpočetní jednotka

PIQL - výkonnost 





test 100 – 1 000 000 uživatelů potvrzena očekávaná lineární závislost propustnosti latence zůstává přibližně konstantní

Shrnutí 



díky požadavkům (webových) aplikací se upouští od relačních databází, což s sebou přináší i komplikace a potenciální rizika na druhou stranu přístup k datům na nízké úrovni může mít i výkonnostní benefity

Shrnutí 

PIQL – performance insightful query language  deklarativní

jazyk  transparentní složitost  obecné úložiště typu klíč-hodnota 

V dnešní době možná spíše NewSQL přístup  článek

z r. 2010

Zdroje 



PIQL: A Performance Insightful Query Language Michael Armbrust, Stephen Tu, Armando Fox, Michael J. Franklin, David A. Patterson, Nick Lanham, Beth Trushkowsky, Jesse Trutna EECS Department, University of California, Berkeley SIGMOD’10, June 6–11, 2010, Indianapolis, Indiana, USA The Case For PIQL: A Performance Insightful Query Language Michael Armbrust, Nick Lanham, Stephen Tu, Armando Fox, Michael J. Franklin, David A. Patterson University of California, Berkeley SoCC’10, June 10–11, 2010, Indianapolis, Indiana, USA