Několik poznámek ke sloupcovým databázím
Autor: Pavel Stěhule, 2015
Se sloupcovými databázemi se v posledních 5 letech setkávám stále častěji, a myslím si, že během následujících 5 let se s nimi setká stále více uživatelů. Jedná se o relativně starý koncept, který teprve v posledních 10 letech našel svoje uplatnění. Dneska téměř každé CPU použité na serverech má výkon a vlastnosti, které měly dříve pouze superpočítače. Také se analyzují větší data - u těch velkých chceme výsledky v řádu hodin, u těch středně velkých v minutách nebo ještě lépe ve vteřinách. Sloupcové databáze (zejména ty moderní) umí velice dobře využívat výkon CPU a tudíž mohou spočítat analytické úlohy velice rychle.
Když se pomyslně vrátím o 30-40 let zpátky do časů, kdy vznikaly klasické relační databáze, tak CPU výkonu (zrovna tak paměti) nebylo nazbyt. Na relačních databázích je zřetelně vidět, jak jsou navržené tak, aby dokázaly zpracovat hromadné zpracování dat s minimem zdrojů. Silně je preferováno sekvenční čtení, které bylo výrazně rychlejší než čtení s náhodným přístupem. Data jsou uloženy normalizovaně - což také znamená, že na jejich zpracování nebude potřeba příliš strojových instrukcí (často stačí načíst blok do paměti a použít N bajtů). Exekutor traverzuje prováděcí plán po řádcích a tak si vystačí minimem paměti. Interně jsou tyto databáze tvořené kombinací několika různých interpretů - o kompilaci do strojového kódu se prakticky nikdo nesnažil. IO operace byly tehdy takovým úzkým hrdlem, že optimalizace na úrovni CPU nepřinášela výrazný benefit. Nehledě na to, že na případnou kompilaci byste potřebovali další výkon CPU, kterého nebylo nazbyt (paradoxně úplně v nejdřevnějších dobách se dotazy skutečně kompilovaly do strojového kódu, ale jakmile bylo dost výkonu a paměti na adhoc optimalizaci a exekuci, tak se tato praxe opustila). Všechno se změnilo s nárůstem výkonu CPU a kapacit pamětí v posledních deseti letech. Volná paměť se může využít jako cache pro IO, čímž se přesouvá úzké hrdlo z IO na CPU, a to je zatím konečná klasických relačních databází. Každé zatím nalezené řešení má aspoň jednu zásadní nevýhodu. Paralelizace komplikuje kód aplikace, zvyšuje počet zámků, vynucuje mezi procesovou komunikaci a synchronizaci. Kompilace, případně JIT kompilace komplikuje kód, a výrazně zpomaluje start. Sloupcové databáze dosahují výrazně vyššího výkonu v agregaci (o řád až dva řády) bez paralelizace, bez kompilace. A to díky výrazně efektivnějšímu využití CPU.
Moderní CPU jsou extrémně výkonná,- tedy pokud nečekají na data. Maximální rychlost je podmíněna daty v cache CPU. Díky tomu, že v sloupcové databázi máme data uložena po sloupcích, tak je velice jednoduché, přirozené provádět operace v blocích, které odpovídají velikosti L1, L2 cache CPU. Pokud dokážeme (a u sloupcových databází to dokážeme docela snadno) minimalizovat počet výpadků cache, můžeme dosáhnout překvapivě vysoké rychlosti zpracování analytických úloh. V následující ukázce použiji dvourozměrné pole jako analogii k tabulce. Podmíněná agregace, podmíněný součet bych mohl implementovat následujícím způsobem:
int sum = 0;
for (r = 0; r < MAX_ROWS; r++)
if (rel[r, 12] = 1)
sum += rel[r, 10];
Analogicky bych tabulku ve sloupcových databází vyjádřil jako pole polí odpovídajících jednotlivým sloupcům. Podmíněný součet by mohl vypadat třeba takto:
int sum = 0;
int *s1 = rel[12];
int *s2 = rel[10];
for (r = 0; r < MAX_ROWS; r++)
if (s1[r] = 1)
sum += s2[r];
Druhý kód by měl být (při dostatečném počtu hodnot - stovky tisíc hodnot) výrazně rychlejší (s možností hardwarové akcelerace - viz SIMD instrukce). To ale není jediný trumf. Při analytických dotazech často čteme data jen několika málo sloupců z tabulky. U klasické databáze čteme vždy celé řádky - tedy i data sloupců, které se v dotazu neuplatní. Při použití jako OLTP databáze toto chování nemusí být až tak nevýhodné - je hodně velká šance, že během doby, kdy datová stránka bude v cache, přijde dotaz, který bude pracovat s ostatními (zatím nepoužitými sloupci). Navíc u OLTP databází se doporučuje navrhovat a používat rozumně spíš úzké tabulky.
U analytických databázi (OLAP) je to jinak. Často se pracuje s daty, které se nevejdou do cache (a tudíž tam nemají šanci zůstat). Navíc analytici rádi pracují s denormalizovaným schématem typu hvězda nebo sněhová vločka, které vede na široké velké tabulky. Zde čtení dat, které nepotřebujeme zamrzí. Jenom díky uložení dat do samostatných souborů po sloupcích může vést k velkému zrychlení provádění dotazů (ve chvíli, kdy se nám data nevejdou do cache, tak IO operace (čtení) zřetelně zpomalují provádění dotazů.
Posledním esem v rukávu (sloupcových databází) je komprimace dat. Na rozdíl od klasických databází se v jednom bloku nemíchají data různých typů, různého charakteru. Docela často lze taková data velice efektivně komprimovat - a jelikož máme dostatek výkonu v CPU, a dost paměti, tak si komprimaci můžeme bezpečně dovolit. Díky komprimaci můžeme výrazně snížit počet "pomalých" IO operací (Stejná data ve Vertice jsou třetinová vůči Postgresu). Vertica je expertem na komprimaci dat. Byť jsou data uloženy duplicitně (v tzv uspořádaných projekcích), jejich celková velikost bývá cca 1/3 odpovídající klasické relační databáze. Moderní sloupcové databáze toho umí víc - pro zájemce doporučuji prostudovat výbornou monografii The Design and Implementation of Modern Column-Oriented Database Systems , jejíž spoluautory jsou Daniel Abadi (jeden z hlavních vývojářů Vertiky) a Peter Bonz (jeden z vedoucích vývojářů a výzkumníků MonetDB ).
V následujících ukázkách vedle sebe postavím MonetDB, PostgreSQL (cstore) a PostgreSQL. PostgreSQL je zástupcem klasických řádkových relačních SQL databází. MonetDB je jednou z nejstarších sloupcových databází, která používá optimalizovaný sloupcový exekutor. Data jsou uložena nekomprimovaně po sloupcích (autoři doporučují použití souborového systému s transparentní komprimací). Nechybí podpora ANSI SQL včetně podpory uložených procedur. cstore můžeme považovat za mezistupeň mezi sloupcovými a řádkovými databázemi - data jsou uložené sloupcově, vlastní zpracování dotazu řeší exekutor Postgresu (tj data se zpracovávají po řádcích). Velkou výhodou cstore je jeho integrace do Postgresu (je to extenze Postgresu) - s vyjímkou nepodporovaných operací UPDATE a DELETE nemusíte poznat, že data nejsou uložena v Postgresu (pozor - tabulky v cstore jsou append only). Instalace a provoz jsou triviální.
Pro testování použiji databázi letů v USA z roku 2008 (29 sloupců, 7M řádek). Uvedené časy jsou pro minimálně druhé vykonání dotazu (čímž se na této velikosti dat (806MB v csv formátu) více méně potlačí vliv rychlosti IO operací (na mém notebooku)):
Mám čtyři dotazy (ukázka je z MonetDB):
- počet letů podle dnů v týdnu
sql>SELECT COUNT(*), dayofweek FROM x GROUP BY dayofweek ORDER BY 2; +---------+-----------+ | L1 | dayofweek | +=========+===========+ | 1036201 | 1 | | 1032049 | 2 | | 1039665 | 3 | | 1032224 | 4 | | 1035166 | 5 | | 857536 | 6 | | 976887 | 7 | +---------+-----------+ 7 tuples (56.551ms)
- počet letů podle měsíců
sql>SELECT COUNT(*), _month FROM x GROUP BY _month ORDER BY 2; +--------+--------+ | L1 | _month | +========+========+ | 605765 | 1 | | 569236 | 2 | | 616090 | 3 | | 598126 | 4 | | 606293 | 5 | | 608665 | 6 | | 627931 | 7 | | 612279 | 8 | | 540908 | 9 | | 556205 | 10 | | 523272 | 11 | | 544958 | 12 | +--------+--------+ 12 tuples (46.579ms)
- procento zrušených letů podle měsíců
sql>SELECT truncate(count(CASE cancelled WHEN 1 THEN 1 ELSE null END) / CAST(count(*) AS float)*100.0, 4), _month FROM x GROUP BY _month ORDER BY 2 desc; +------+--------+ | L4 | _month | +======+========+ | 3.26 | 12 | | 0.85 | 11 | | 0.58 | 10 | | 1.83 | 9 | | 1.60 | 8 | | 1.68 | 7 | | 1.79 | 6 | | 1.02 | 5 | | 1.73 | 4 | | 2.62 | 3 | | 3.61 | 2 | | 2.85 | 1 | +------+--------+ 12 tuples (85.598ms) - hledání maxim - počet letů a nejdelší vzdálenost letu
sql>SELECT count(*), max(distance) FROM x WHERE origin = 'ATL'; +--------+------+ | L1 | L2 | +========+======+ | 414513 | 4502 | +--------+------+ 1 tuple (115.353ms)
Všechny časy jsou pod nebo jen těsně nad 100ms. Z toho, že časy dotazů jsou perfektní, je vidět, že takové dotazy a zhruba taková velikost tabulek je přesně parketa MonetDB. MonetDB potřebuje, aby se mu aktivní data rozumně vešla do operační paměti (má příliš jednoduchou správu paměti, vždy celý sloupec natahuje do paměti a server nesmí aktivně swapovat). Na takto jednoduchých dotazech není co optimalizovat - jde pouze o rychlost rozbalení dat (separace vybraných sloupců z řádek) a rychlost volání agregačních funkcí.
Orientační měření na malých datech
| dotaz | PostgreSQL | cstore | cstore pglz | MonetDB |
|---|---|---|---|---|
| 1. | 1660 ms | 1504 ms | 1550 ms | 56ms |
| 2. | 1619 ms | 1509 ms | 1538 ms | 46ms |
| 3. | 3044 ms | 1940 ms | 1997 ms | 85ms |
| 4. | 1627 ms | 877 ms | 930 ms | 115ms |
Rád bych se zastavil u třetího dotazu - Lze jej částečně optimalizovat použitím podmíněné agregační funkce (v PostgreSQL od 9.4) - (2857 ms):
SELECT count(*) <b>FILTER</b> (WHERE cancelled = 1) / CAST(count(*) AS float)*100.0, _month FROM x GROUP BY _month ORDER BY 2 desc;
Tady bych ještě zmínil významný vliv pořadí sloupců na dobu běhu dotazu u Postgresu (tabulka má 683MB - tudíž se pohodlně vejde do paměti, a tak veškerá režie s CPU je dobře vidět). Zase abych Vás zbytečně nestrašil - na 7 mil. řádků je rozdíl 1 sec. Pokud bych čekal na IO, tak by ta 1 sekunda nehrála roli.
-- základní iterace nad tabulkou -- ukázka z PostgreSQL postgres=# SELECT count(*) FROM x; count --------- 7009728 (1 row) Time: 657.830 ms -- agregační funkce nad prvním sloupcem postgres=# SELECT count(_year) FROM x; count --------- 7009728 (1 row) Time: 832.020 ms -- agregační funkce nad 12 sloupcem postgres=# SELECT count(cancelled) FROM x; count --------- 7009728 (1 row) Time: 1850.515 ms
V cstore má tabulka 448 MB. Data jsou uložena nekomprimovaně - rozdíl vůči Postgresu dělají režijní data multigenerační architektury.
-- inicializace tabulky v <i>cstore</i>
<b>CREATE EXTENSION cstore_fdw</b>;
<b>CREATE SERVER cstore_server FOREIGN DATA WRAPPER cstore_fdw</b>;
<b>CREATE FOREIGN TABLE cs_x</b> (
_year smallint,
_month smallint,
...
nasdelay smallint,
securitydelay smallint,
lateaircraftdelay smallint
) <b>SERVER cstore_server</b>;
INSERT INTO cs_x SELECT * FROM x;
postgres=# SELECT count(cancelled) FROM cs_x;
count
---------
7009728
(1 row)
Time: 750.607 ms
postgres=# SELECT count(_year) FROM cs_x;
count
---------
7009728
(1 row)
Time: 768.073 ms
Zde je zřetelně vidět, že nezáleží na pořadí sloupce v tabulce. Pro relativně malá data je cstore rychlejší někde mezi 10 až 30%. Data do 1GB z dnešního pohledu nejsou velká, ale na druhou stranu - je to statistika všech letů v USA během jednoho roku.
cstore umí komprimovat v něm uložená data. Po komprimaci jsou data v cstore uložena do 160MB souboru. U malých datasetů dekomprimace cstore mírně zpomaluje (představuje pouze režii), což by nikoho nemělo překvapit - používá se interní komprimace z Postgresu, která vůbec není optimalizována pro použití v sloupcových databází.
Orientační měření na větších datech
Data do 1GB jsou relativně malá a na mém notebooku se vejdou do RAM - a tudíž efekt uložení dat ve sloupcích na IO operace je spíše malý. Proto jsem si vygeneroval ještě jednu sadu tabulek - jejich desetinásobek. Jelikož používám šifrovaný disk, tak by sloupcové databáze měly dát Postgresu dost na frak - bude velký rozdíl v objemu dešifrovaného obsahu.
DO $$ BEGIN FOR i IN 1..10 LOOP INSERT INTO xx SELECT * FROM x; END LOOP; END $$; ..
Tabulka xx má 6.8GB v Postgresu, 4.3GB v nekomprimovaném cstore, a 1.5GB v komprimovaném cstore. Jenom rozdíl velikost 5GB bude znamenat rozdíl v rychlosti minimálně minutu (na mém notebooku). Následující výsledky jsou pro první spuštění dotazu (kromě trvání dotazu je uvedena i intenzita čtení dat):
| dotaz | PostgreSQL | cstore | cstore pglz | MonetDB |
|---|---|---|---|---|
| 1. | 97sec(60MB/s) | 30sec(11MB/s) | 20sec(4MB/s) | 7sec |
| 2. | 96sec(60MB/s) | 22sec(11MB/s) | 19sec(2MB/s) | 7sec |
| 3. | 104sec(60MB/s) | 42sec(11MB/s) | 22sec(2.5MB/s) | 7sec |
| 4. | 105sec(60MB/s) | 30sec(19MB/s) | 17sec(11MB/s) | 2.5sec |
U Postgresu bych si mohl trochu pomoci indexy - s natlačením Postgresu do index only scanu bych se měl dostat na časy blízké cstore. Nicméně si nejsem jistý, jestli by se mi do toho v praxi chtělo. Index nad každým sloupečkem fakticky znamená extrémně pomalé INSERTy, UPDATEy - v Postgresu navíc efektivně vyblokujete tzv hot update - což je způsob modifikace řádku, který minimalizuje nutnost volání příkazu VACUUM.
S cstorem se dostávám na časy cca 25-50% Postgresu, přičemž je výrazně méně zatížené IO (které může rychleji obsluhovat ostatní uživatele). Při těchto úlohách je MonetDB 20x rychlejší než Postgres a 5-10x rychlejší než cstore (a pokud nalezne data v paměti - tak ještě může být MonetDB o další řád rychlejší). Tabulka s daty x má pouze 29 sloupců. V OLAPu se pracuje s tabulkami s více než stovky sloupců. Samozřejmě, že potom pouze uložení dat ve sloupcích vede k ohromnému zrychlení. Na této myšlence je založena existence forku PostgreSQL - Greenplum .
Rozdíl až o dva řády je ohromující, byť na testu, pro který je MonetDB navrhován a dlouhodobě optimalizován. Pro analytické úlohy (typicky masivní agregace) je sloupcové uložení dat evidentně výhodné. Opačná situace je u OLTP, ačkoliv je otázkou jak ještě dlouho (zítřek ještě bude patřit klasickým databázím, ale nepochybuji, že do pěti let bude většina velkých databází podporovat alternativní uložení dat ve sloupcích). INSERT, UPDATE, DELETE jednoho řádku (u řádkových databází) ovlivní typicky pouze jeden blok dat (jednu datovou stránku). U sloupcových databází pak v případě INSERTu a DELETE řádku musíme zmodifikovat N bloků, kde N je počet sloupců. A jelikož se u sloupcových databází používají větší bloky (32, 64KB), tak to znamená, že se musí manipulovat s větším objemem dat, a že se musí zapisovat větší objem dat.
Zatímco u klasických relačních databází řádkové DML operace jsou docela jednoduché a nenáročné, tak u sloupcových databází jsou drahé a netriviální, pokud mají být efektivní. Na druhou stranu u OLAP databází nepotřebujeme rychlé jednořádkové DML operace. Často se používají pouze operace typu masivního importu (bulk load). Také se tyto databáze označují jako databáze optimalizované pro čtení (read optimized).
postgres=# CREATE UNLOGGED TABLE x_c AS SELECT * FROM x; SELECT 7009728 Time: 19013.222 ms postgres=# INSERT INTO cs_x SELECT * FROM x; INSERT 0 7009728 Time: 30954.555 ms -- komprimovaný cstore postgres=# INSERT INTO cs_x_pglz SELECT * FROM x; INSERT 0 7009728 Time: 35206.968 ms -- MonetDB sql>INSERT INTO x1 SELECT * FROM x; 7009728 affected rows (21.0s)
Nicméně na první pohled MonetDB pomalými DML operacemi netrpí - jejich rychlost byla srovnatelná s PostgreSQL. Manipulace s daty je sice náročnější, ale rychleji se dohledají data, která se mají modifikovat.
MonetDB je hodně zajímá databáze. A její autoři jsou opravdu chytří lidé. Velmi dobře odhadli budoucí vývoj. MonetDB je v prvé řadě výzkumný projekt (a to jeden z nejcitovanějších (nejdůležitějších) v této oblasti). To, bohužel, také znamená, že vyjma akademické obce se o této databázi prakticky neví. Docela dlouhou dobu bylo SQL pouze jedním z možných API k této databázi. Teprve v posledních třech možná pěti letech se autoři víc soustředili na SQL a dotáhli jej do provozně použitelného stavu. Monetu nepomáhá ani slabší dokumentace - v podstatě chybí jakýkéliv ucelenější podrobnější informace. Víc než z dokumentace se dozvíte z prezentací a článků pro konference a sborníky (což je nepraktické, ale logické, protože tuto databázi nepíše komunita vývojářů pro uživatele, ale profesoři a doktorandi pro svůj výzkum). Pokud ale nepotřebujete vědět, jak MonetDB interně funguje, tak podle dokumentace jednoduše MonetDB nainstalujete a rozběhnete . Ukázkou jinakosti MonetDB může být už i pouhý výpis prováděcího jednoduššího plánu (to se opravdu nepodobá žádné jiné databázi):
sql>EXPLAIN SELECT count(*), max(distance) FROM x WHERE origin = 'ATL';
+-------------------------------------------------------------------------------------------------------------+
| mal |
+=============================================================================================================+
| function user.s3_1{autoCommit=true}(A0:str):void; |
| X_3 := sql.mvc(); |
| X_7:bat[:oid,:str] := sql.bind(X_3,"sys","x","origin",0); |
| X_4:bat[:oid,:oid] := sql.tid(X_3,"sys","x"); |
| X_56 := algebra.subselect(X_7,X_4,A0,A0,true,true,false); |
| (X_10,r1_10) := sql.bind(X_3,"sys","x","origin",2); |
| X_57 := algebra.subselect(r1_10,A0,A0,true,true,false); |
| X_13:bat[:oid,:str] := sql.bind(X_3,"sys","x","origin",1); |
| X_58 := algebra.subselect(X_13,X_4,A0,A0,true,true,false); |
| X_15 := sql.subdelta(X_56,X_4,X_10,X_57,X_58); |
| X_17 := sql.projectdelta(X_15,X_7,X_10,r1_10,X_13); |
| X_18 := aggr.count(X_17); |
| X_19:bat[:oid,:sht] := sql.bind(X_3,"sys","x","distance",0); |
| (X_21,r1_24) := sql.bind(X_3,"sys","x","distance",2); |
| X_23:bat[:oid,:sht] := sql.bind(X_3,"sys","x","distance",1); |
| X_24 := sql.projectdelta(X_15,X_19,X_21,r1_24,X_23); |
| X_25 := aggr.max(X_24); |
| X_26 := sql.resultSet(2,1,X_18); |
| sql.rsColumn(X_26,"sys.L1","L1","wrd",64,0,X_18); |
| sql.rsColumn(X_26,"sys.L2","L2","smallint",16,0,X_25); |
| X_38 := io.stdout(); |
| sql.exportResult(X_38,X_26); |
| end s3_1; |
| # querylog.define("explain select count(*), max(distance) from x where origin = \\'ATL\\';","default_pipe") |
| # optimizer.mitosis() |
| # optimizer.dataflow() |
+-------------------------------------------------------------------------------------------------------------+
26 tuples (1.249ms)
Vespod MonetDB je univerzální sloupcový databázový kernel "Goblin". Díky němu tato databáze nemusí být pouze sloupcovou SQL databází. Za posledních 15 let už byla: XQuery databází, RDF SPARQL databází, proudovou databází (DataCell). Vývojáři experimentují s podporou polí (SciQL ). Implementace nového interface spočívá "pouze" v napsání překladače do interního jazyka MAL - MonetDB Assembly Language . Nepřestává mne překvapovat, jak je tato architektura univerzální a při vší té komplexnosti rychlá. MonetDB zjevně vyvrací tvrzení, že SQL databáze jsou pomalé. Rychlost nezáleží na API, ale na tom, jak vhodně jsou uložena data, a jakým způsobem se zpracovávají.
Pro OLTP bych asi MonetDB nepoužil, jelikož pro něj platí omezení, že pouze jeden uživatel může efektivně modifikovat jeden sloupec (aktuálně pouze s optimistickým zamykáním) - to by v multiuživatelské OLTP aplikaci nefungovalo (sami autoři před takovým použitím varují). V případě analytické aplikace bych už asi váhal (tam, kde chci mít rychlé agregace a mám star schema) - Postgres funguje dobře - ale ten výkon Monetu vždy bude stát za úvahu. A pro všechny Rkaře - MonetDB je dobře integrován s Rkem .