■ ■ PA152: Efektivní využívání DB 3. Ukládání dat Vlastislav Dohnal Poděkování ■ Zdrojem materiálů tohoto předmětu jsou: D Přednášky CS245, CS345, CS345 ■ Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom ■ Stanford University, California D Přednášky dřívější verze PA152 ■ Pavel Rychlý ■ Fakulta informatiky, Masarykova Univerzita PA152, Vlastislav Dohnal, Fl MUNI, 2009 2 Osnova ■ Ukládání dat m Záznamy ■ Organizace bloků ■ Příklady PA152, Vlastislav Dohnal, Fl MUNI, 2009 3 Uložení dat ■ Co chceme ukládat? Djméno d plat d datum d obrázek ■ Jak ukládat? Dbajty -> posloupnost bajtů PA152, Vlastislav Dohnal, Fl MUNI, 2009 Typy datových elementů ■ Celá čísla d Podle rozsahu: 2 bajty, 4 bajty D Např. 35 v 16 bitech 00000000 00100011 d Obvykle přímý kód nebo inverzní kód Reálná čísla d Plovoucí čárka ■ n bitů rozděleno na mantisu a exponent D Pevná čárka ■ Kódování každých 9 cifer (základ 10) do 4 bajtů ■ Uložení jako řetězec PA152, Vlastislav Dohnal, Fl MUNI, 2009 Typy datových elementů ■ Znaky DNejčastěji v ASCII kódování - 1 bajt d Více bajtové znaky ■ UCS-2 - kódování do utf-8 do 16 bitů d Znaky s kódy 0 až 65535 ■ UTF-8 - kódování variabilní délky d Znak může zabírat 1 až 3 bajty PA152, Vlastislav Dohnal, Fl MUNI, 2009 6 Typy datových elementů ■ Pravdivostní hodnota (boolean) d Obvykle jako celé číslo d True 1111 1111 d False 0000 0000 d Méně než 1 bajt nemá velký význam Bitové pole d Délka + bity ■ Tj. zaokrouhleno na celé bajty PA152, Vlastislav Dohnal, Fl MUNI, 2009 7 Typy datových elementů ■ Datum a počet dní od „počátku" (např. 1.1.1970) D řetězec YYYYMMDD (8 znaků) - YYYYDDD (7 znaků) - Proč ne YYMMDD? ■ Čas a počet sekund od půlnoci ■ počet mikrosekund D řetězec HHMMSSFF a časové zóny - čas uložen v UTC ■ Ukládání - konverze z daného pásma do UTC PA152, Vlastislav Dohnal, Fl MUNI, 2009 Typy datových elementů ■ Výčtový typ d Očíslování hodnot -> integer d red -> 1, green ->■ 2, blue -> 3, yellow ->4, ... PA152, Vlastislav Dohnal, Fl MUNI, 2009 9 Typy datových elementu ■ Řetězce D Pevná délka ■ Omezení velikosti d Kratší řetězce doplněny mezerami d Delší oříznuty D Proměnlivá délka ■ Uložená délka, pak řetězec ■ Ukončení nulou d nutnost číst celý d nelze uložit nulu v textu D Problém znakové sady (kódování) PA152, Vlastislav Dohnal, Fl MUNI, 2009 Uložení datových elementů ■ Každý element „má" svůj typ d interpretace bitů d velikost d speciální hodnota „neznámá" (NULL) ■ Většinou pevná délka d každý typ má svoji bitovou reprezentaci ■ Proměnlivá délka d velikost na začátku hodnoty PA152, Vlastislav Dohnal, Fl MUNI, 2009 11 Osnova ■ Ukládání dat ■ Záznamy ■ Organizace bloků ■ Příklady PA152, Vlastislav Dohnal, Fl MUNI, 2009 Souvislosti Datové elementy Záznamy Bloky 4, Soubory ■ ■ Paměť PA152, Vlastislav Dohnal, Fl MUNI, 2009 Záznam (record) ■ Seznam souvisejících datových elementů d Resp. jejich hodnot d Fields, Attributes ■ Např. D Zaměstnanec ■ Jméno - Novák ■ Plat-1234 ■ datum_přijetí - 1.1.2000 PA152, Vlastislav Dohnal, Fl MUNI, 2009 14 Schéma záznamu ■ Popisuje strukturu záznamu ■ Uložené informace d Počet atributů d Typ / název každého atributu d Pořadí atributu PA152, Vlastislav Dohnal, Fl MUNI, 2009 ■ Pevný formát D Schéma společné pro všechny záznamy ■ Je uloženo mimo záznamy (tzv. data dictionary) ■ Proměnlivý formát d Každý záznam obsahuje svoje schéma D Vhodné pro: ■ „řídké" záznamy (hodně NULL) ■ opakování stejných atributů ■ vyvíjející se formát i změny schématu během života db PA152, Vlastislav Dohnal, Fl MUNI, 2009 16 ■ Pevná délka d Každý záznam má stejnou délku (počet bajtů) ■ Proměnlivá délka d Ušetření paměti d Složitější implementace d Možnost pro uložení velkých dat (obrázky, ...) PA152, Vlastislav Dohnal, Fl MUNI, 2009 17 Príklad - pevný formát i délka Zaměstnanec 1) id - 2 byte integer 2) jméno- 10 znaků 3) oddělení - 2 byte code 55 i i i i i i i i i n o vá k 02 83 i i i i i i i i i dlouhý 01 A r schéma j ■\ > záznamy j Zarovnání na „vhodnou" délku d Rychlejší přístup k paměti zarovnané na 4 (8) bajtů PA152, Vlastislav Dohnal, Fl MUNI, 2009 Príklad - proměnlivý formát i délka Zaměstnanec: 2 ill 1 5 11 I 46 4 |S |4 CECH Ol c/> ^ g; "43-^ Q_ ■--o uložit jako záznam d Kolekce -> vytvořit novou relaci a tam uložit ■ Referencovat pomocí Ol D PA152, Vlastislav Dohnal, Fl MUNI, 2009 24 Uložení relace ■ Řádkové d Zatím uvažovaná varianta ■ Sloupcové d Hodnoty stejného atributu pohromadě ■ Příklad řádkového uložení: DOrder(id, oust, prod, store, price, date, qty) id1 custl prodl store 1 pricel datel qty1 id2 cust2 prod2 store2 price2 date2 qty2 id3 cust3 prod3 store3 price3 date3 qty3 PA152, Vlastislav Dohnal, Fl MUNI, 2009 25 Sloupcové uložení ■ Relace DOrder(id, cust, prod, store, price, date, qty) ríďi custl id2 cust2 id3 cust3 id4 cust4 ■ ■ ■ ■ ■ ■ id1 proch id2 prod2 id3 prod3 id4 prod4 ■ ■ ■ ■ ■ ■ Id mohou ale nemusí být uloženy, lze využít pořadí hodnot PA152, Vlastislav Dohnal, Fl MUNI, 2009 26 Porovnání ■ Výhody sloupcového uložení D Kompaktnější uložení (nezarovnávání na bajty) D Efektivní čtení (např. pro data mining) ■ Zpracovávání mála atributů, ale všech hodnot ■ Výhody řádkového uložení d Aktualizace / vkládání je rychlejší d Efektivnější při přístupu k celým záznamům Mike Stonebreaker, Elizabeth 0'Neil, Pat 0'Neil, Xuedong Chen, et al.: C-Store: A Column-oriented DBMS, VLDB Conference, 2005. http://www.cs.umb.edu/~poneil/vldb05_cstore.pdf PA152, Vlastislav Dohnal, Fl MUNI, 2009 27 Osnova ■ Ukládání dat ■ Záznamy ■ Organizace bloků ■ Příklady PA152, Vlastislav Dohnal, Fl MUNI, 2009 Uložení záznamů do bloků ■ záznamy d pevné délky D proměnné délky ■ bloky pevné velikosti bloky soubor PA152, Vlastislav Dohnal, Fl MUNI, 2009 Uložení záznamů do bloků ■ Možnosti D Oddělování záznamů ■ separating records D Rozdělování / nerozdělování záznamů ■ spanned vs. unspanned D Uspořádání záznamů ■ sequencing D Odkazy na záznamy ■ indirection PA152, Vlastislav Dohnal, Fl MUNI, 2009 30 Oddělování záznamů ■ Záznamy pevné délky d Žádný oddělovač d Pamatovat počet a ukazatel na první záznam ■ Oddělovač ■ Ukládání délek záznamů (nebo počátků) d V rámci záznamu d V hlavičce bloku PA152, Vlastislav Dohnal, Fl MUNI, 2009 31 Míchání (shlukování) záznamů ■ Záznamy různých relací v jednom bloku d Některá data jsou vyžadována současně d Uložit je společně -> zrychlené čtení d Složitější implementace ■ Řešení: D Nemíchat v rámci bloku d Ukládat bloky blízko sebe ■ Stejný válec disku PA152, Vlastislav Dohnal, Fl MUNI, 2009 32 Príklad Shlukování záznamů vhodné Q1: d SELECT cname, ccity FROM deposit, customer WHERE deposit.dname = customer.cname blok customer.cname=SMITH deposit.dname=SMITH deposit.dname=SMITH PA152, Vlastislav Dohnal, Fl MUNI, 2009 33 Příklad pokr. ■ Q2: D SELECT * FROM customer ■ Shlukování nevhodné pro Q2 d Záleží na četnosti jednotlivých dotazů PA152, Vlastislav Dohnal, Fl MUNI, 2009 34 Míchání (shlukování) záznamů ■ Řešení: D Nemíchat v rámci bloku d Ukládat bloky blízko sebe ■ Stejný válec disku PA152, Vlastislav Dohnal, Fl MUNI, 2009 35 Rozdělování / nerozdělování záznamů ■ Nerozdělování d každý záznam součástí jednoho bloku Djednodušší, ale může plýtvat místem blok 1 blok 2 ■ Rozdělování d Záznam „přetéká" mezi bloky d Nutné pokud je záznam větší než blok blok 1 blok 2 Rl R2 R3(a) R3(b) R4 R5 R6 R7(a) PA152, Vlastislav Dohnal, Fl MUNI, 2009 36 Příklad ■ Nerozdělování záznamů d 106 záznamů, každý 2 050 bajtů (pevná délka) D Velikost bloku 4 096 bajtů blok 1 blok 2 D Celkem alokováno: 106 * 4096B D Celkem využito: 106 * 2050B D Využití paměti: 50% PA152, Vlastislav Dohnal, Fl MUNI, 2009 37 Rozdělování záznamu ■ Záznam „přetéká" mezi bloky d Musíme udržovat pořadí bloků ■ Lze používat ukazatele blokl blok 2 Rl R2 R3(a) R3(b) R4 R5 R6 R7(a) Záznam je rozdělen na „fragmenty" d Bitový příznak, zda je fragmentován d Ukazatel na další / předchozí fragment PA152, Vlastislav Dohnal, Fl MUNI, 2009 Rozdělování záznamu ■ Velký atribut D The Oversized-Attribute Storage Technique ■ TOAST or "the best thing since sliced bread,, D Rozdělení záznamu (viz předchozí) D Komprese d Rozdělení do více záznamů (interně) ■ Velká data (LOB) d Uloženo zvlášť - posloupnost bloků d DB neindexuje, neumí uvnitř vyhledávat PA152, Vlastislav Dohnal, Fl MUNI, 2009 Uspořádání záznamů ■ Záznamy jsou v souboru (a bloku) uspořádány d Podle hodnoty nějakého klíče DNapř. sekvenční soubor ■ Důvod: d Efektivní čtení záznamů v daném pořadí DNapř. pro merge-join, order by, ... PA152, Vlastislav Dohnal, Fl MUNI, 2009 40 Uspořádání záznamů ■ Uložené za sebou Rl R2 R3 ■ ■ ■ ■ Zřetězený seznam Rl R2 R3 PA152, Vlastislav Dohnal, Fl MUNI, 2009 41 Uspořádání záznamu ■ Přetoková oblast d Záznamy jsou uložené za sebou ■ nutné reorganizace při aktualizaci D ->• přetoková oblast | hlavička blok ~W[ R2 R3 R4 | R5 PA152, Vlastislav Dohnal, Fl MUNI, 2009 ^4 R2.1 R1.3 R4.7 Odkazy na záznamy ■ Potřeba kvůli: D Rozdělování záznamů d Odkazování bloků / záznamů (viz indexy) DZřetězování bloků (viz indexy) dOODBMS: objekty ukazují na jiné objekty ■ Adresa záznamu d V paměti: 4 (8) bajtový ukazatel d V úložišti: sekvence bajtů popisující ■ ID disku, stopa, povrch, blok, offset v bloku PA152, Vlastislav Dohnal, Fl MUNI, 2009 43 Odkazy na záznamy (2) ■ Fyzická adresa záznamu d Adresa v úložišti, nevhodné pro přímé použití ■ Např. realokace bloku nebo záznamu ■ Záznam (i blok) je identifikován svým ID DID (logická adresa): libovolná posloupnost bitů ■ Adresace je nepřímá d Převodní tabulka (map table): ID ->• fyz. adresa adresa a rec ID ^^ r ID fyz. adresa PA152, Vlastislav Dohnal, Fl MUNI, 2009 44 Odkazy na záznamy (3) ■ Nepřímá adresace d Nevýhoda: zvýšené náklady ■ průchod map table D Výhoda: velká flexibilita ■ Mazání záznamů, vkládání ■ Optimalizace uložení bloků PA152, Vlastislav Dohnal, Fl MUNI, 2009 Odkazy na záznamy (4) ■ Vhodná varianta D Fyz. adresa záznamu = fyz. adr. bloku + offset ■ Offset je pořadí záznamu v bloku d V hlavičce je obvykle seznam odkazů na záznamy. D Výhoda: ■ Lze přesouvat záznamy v bloku beze změny fyz. adresy ■ Lze přesunout záznam do jiného bloku d V původním místě udělám odkaz na nový blok + offset ■ Lze zrušit map table PA152, Vlastislav Dohnal, Fl MUNI, 2009 46 Odkazy na záznamy (5) ■ Používaná varianta D Adresa záznamu = ID souboru + číslo bloku + offset v bloku d Uložení bloku určuje systém souborů (file systém) File ID, _^ / File System\ _^ Physical Block # V MaP J Block ID PA152, Vlastislav Dohnal, Fl MUNI, 2009 47 Odkazy na záznamy (6) ■ Nepřímý odkaz v bloku d Fyz. adresa záznamu = fyz. adr. bloku + offset hlavička blok R3\ l R4 // \ Rl / lR2 A y volne m isto j PA152, Vlastislav Dohnal, Fl MUNI, 2009 48 Hlavička bloku ■ Informace přítomná v každém bloku D File ID (or RELATION ID or DB ID) DID bloku (tohoto) d Adresář záznamů (odkazy na data záznamů) d Ukazatel na volné místo (začátek, konec) D Typ bloku ■ např. záznamy typu 4, přetoková oblast, ... d Ukazatel na další blok (např. pro indexy) d Čas modifikace (popř. verze) PA152, Vlastislav Dohnal, Fl MUNI, 2009 49 Modifikace záznamu ■ Vkládání d Obvykle snadné ■ Mazání d Správa volného místa ■ Změna d Stejná velikost ■ ok d Jiná velikost ■ problém stejný jako při vkládání / mazání PA152, Vlastislav Dohnal, Fl MUNI, 2009 Mazání záznamů ■ Problém s odkazy na smazané záznamy d Musí být neplatné d Nesmí odkazovat na jiná nová data dTzv. dangling pointers Rl ^ w PA152, Vlastislav Dohnal, Fl MUNI, 2009 51 Mazání záznamů (2) ■ Adresa záznamu je offset v bloku D Ihned uvolni místo d Posuň ostatní záznamy, aby volné místo bylo souvislé d V adresáři záznamů nastav ukazatel na null blok } volné místo R4 // \ Rl7 ; R2 PA152, Vlastislav Dohnal, Fl MUNI, 2009 52 Mazání záznamu (3) Adresa záznamu je fyzická adresa _____ i blok ' r tkaj. nelze znovu využít volné místo D Označ jako smazané ■ Vytvořením značky (tombstone) ■ Stačí 1 bit, ale obvykle několik bajtů (zarovnání) D Oznámit volné místo ■ Zřetězení volných míst PA152, Vlastislav Dohnal, Fl MUNI, 2009 Mazání záznamů (4) ■ Nepřímá adresace d Map table d Smazaný záznam uvolní místo v bloku d Náhrobek je v map table Map Table Tuto položku nelze již znovu využít. ID LOC 7788 fcLsd. PA152, Vlastislav Dohnal, Fl MUNI, 2009 54 Mazání záznamu (5) ■ Uložení ID záznamu přímo v záznamu D Při čtení záznamu kontrolujeme ID na shodu PA152, Vlastislav Dohnal, Fl MUNI, 2009 Vkládání záznamů ■ Neuspořádané záznamy d Vkládáme na konec (poslední blok, popř. nový) d Vkládáme do volného místa v existujícím bloku ■ Může být problematické v případě proměnlivé délky záznamu PA152, Vlastislav Dohnal, Fl MUNI, 2009 56 Vkládání záznamů (2) ■ Uspořádané záznamy d Nemožné pokud není nepřímá adresace a nepoužívají se offsety d Najdi místo v „blízkém" bloku -> reorganizuj ■ Přesunutí posledního záznamu do následujícího bloku -» nutné přidat příznak do původního bloku D Ulož do přetokového bloku ■ Odkaz na přetokový blok je součástí hlavičky bloku PA152, Vlastislav Dohnal, Fl MUNI, 2009 57 Aktualizace záznamů ■ Zvětšení délky záznamu D Nemusí se vytvářet náhrobky D Posunout následující záznamy d Vytvořit přetokový blok D... ■ Zmenšení délky záznamu d dtto d Zrušení uvolněných přetokových bloků PA152, Vlastislav Dohnal, Fl MUNI, 2009 58 Správa vyrovnávací paměti ■ Různé strategie D LRU, FIFO, pinned blocks, ... ■ LRU nevhodný pro nested-loop join ■ Pinned blocks d Bloky trvale v paměti (připíchnuté) d Vhodné pro nested-loop join ■ Problém odkazování na záznamy v paměti d Prohazování odkazů (swizzling) PA152, Vlastislav Dohnal, Fl MUNI, 2009 59 Prohazování odkazů Změna odkazů při načtení bloku do paměti Da zpět (při ukládání na disk) Odkaz pak ukazuje do paměti a ne na disk Paměť bioki Disk blokl Rec A blok 2 PA152, Vlastislav Dohnal, Fl MUNI, 2009 60 Prohazování odkazů (2) ■ Po načtení bloku 2 je provedena změna odkazu Paměť bioki blok 2 Disk blokl ^ Rec A blok 2 PA152, Vlastislav Dohnal, Fl MUNI, 2009 61 Prohazování odkazů (3) ■ Implementace: d DB adresa je měněna na paměťovou adresu D Translation table d Ukazatel má příznak, zda byl prohozen či ne ■ Kdy: D Automaticky - ihned po načtení d Na žádost - při prvním použití d Nikdy - vždy se používá překladová tabulka PA152, Vlastislav Dohnal, Fl MUNI, 2009 62 Vlastní implementace Flexibility ----------- Space Utilization Complexity--------- Performance ■ Otázka náročnosti operací: d Načtení záznamu s daným klíčem ■ Načtení následujícího záznamu D Vložení / smazání / aktualizace záznamů d Čtení celého souboru d Reorganizace souboru PA152, Vlastislav Dohnal, Fl MUNI, 2009 63 Specializované implementace ■ BigTable d Distribuované úložiště od Google DSkálovatelost do petabajtů (1PB=1000TB) F. Chang, J. Dean, S. Ghemawat, et al.: Bigtable: A Distributed Storage System for Structured Data, Seventh Symposium on Operating System Design and Implementation (OSDI), 2006. http://labs.google.com/papers/bigtable-osdi06.pdf ■ Hadoop D Distribuované úložiště D Open-source Apache projekt http://hadoop.apache.org/ PA152, Vlastislav Dohnal, Fl MUNI, 2009