PA152: Efektivní využívání DB 3. Ukládání dat Vlastislav Dohnal PA152, Vlastislav Dohnal, FI MUNI, 2013 2 Souvislosti Datové elementy Záznamy Bloky Soubory Paměť PA152, Vlastislav Dohnal, FI MUNI, 2013 3 Osnova  Ukládání dat  Záznamy  Organizace bloků  Příklady PA152, Vlastislav Dohnal, FI MUNI, 2013 4 Uložení dat  Co chceme ukládat? jméno plat datum obrázek  Jak ukládat? bajty  posloupnost bajtů PA152, Vlastislav Dohnal, FI MUNI, 2013 5 Typy datových elementů  Celá čísla  Podle rozsahu: 2 bajty, 4 bajty  Např. 35 v 16 bitech  Obvykle přímý kód nebo inverzní kód  Reálná čísla  Plovoucí čárka  n bitů rozděleno na mantisu a exponent (dle IEEE 754)  Pevná čárka  Kódování každých 9 cifer (základ 10) do 4 bajtů  Uložení jako řetězec 00000000 00100011 PA152, Vlastislav Dohnal, FI MUNI, 2013 6 Typy datových elementů  Znaky Nejčastěji v ASCII kódování – 1 bajt Více bajtové znaky  UCS-2 – kódování UTF-8 do 16 bitů  Znaky s kódy 0 až 65535  UTF-8 – kódování variabilní délky  Znak může zabírat 1 až 3 bajty PA152, Vlastislav Dohnal, FI MUNI, 2013 7  Pravdivostní hodnota (boolean) Obvykle jako celé číslo True False Méně než 1 bajt nemá velký význam  Bitové pole Délka + bity  Tj. zaokrouhleno na celé bajty Typy datových elementů 1111 1111 0000 0000 PA152, Vlastislav Dohnal, FI MUNI, 2013 8 Typy datových elementů  Datum  počet dní od „počátku” (např. 1.1.1970)  řetězec YYYYMMDD (8 znaků)  YYYYDDD (7 znaků)  Proč ne YYMMDD?  Čas  počet sekund od půlnoci  počet milisekund nebo mikrosekund  řetězec HHMMSSFF  časové zóny – čas uložen v UTC  Ukládání – konverze z daného pásma do UTC PA152, Vlastislav Dohnal, FI MUNI, 2013 9 Typy datových elementů  Výčtový typ Očíslování hodnot  integer red  1, green  2, blue  3, yellow  4, ... PA152, Vlastislav Dohnal, FI MUNI, 2013 10 Typy datových elementů  Řetězce Pevná délka  Omezení velikosti  Kratší řetězce doplněny mezerami  Delší oříznuty Proměnlivá délka  Uložená délka, pak řetězec  Ukončení nulou  nutnost číst celý  nelze uložit nulu v textu Problém znakové sady (kódování) PA152, Vlastislav Dohnal, FI MUNI, 2013 11 Uložení datových elementů  Každý element „má“ svůj typ interpretace bitů velikost speciální hodnota „neznámá” (NULL)  Většinou pevná délka každý typ má svoji bitovou reprezentaci  Proměnlivá délka velikost na začátku hodnoty PA152, Vlastislav Dohnal, FI MUNI, 2013 12 Osnova  Ukládání dat  Záznamy  Organizace bloků  Příklady PA152, Vlastislav Dohnal, FI MUNI, 2013 13 Záznam (record)  Seznam souvisejících datových elementů Resp. jejich hodnot Fields, Attributes  Např. Zaměstnanec  jméno – Novák  plat – 1234  datum_přijetí – 1.1.2000 PA152, Vlastislav Dohnal, FI MUNI, 2013 14 Schéma záznamu  Popisuje strukturu záznamu  Uložené informace Počet atributů Typ / název každého atributu Pořadí atributu PA152, Vlastislav Dohnal, FI MUNI, 2013 15 Typy záznamů podle schématu  Pevný formát Schéma společné pro všechny záznamy  Je uloženo mimo záznamy (tzv. data dictionary)  Proměnlivý formát Každý záznam obsahuje svoje schéma Vhodné pro:  „řídké“ záznamy (hodně NULL)  opakování stejných atributů  vyvíjející se formát  změny schématu během života db PA152, Vlastislav Dohnal, FI MUNI, 2013 16 Typy záznamů podle délky  Pevná délka Každý záznam má stejnou délku (počet bajtů)  Proměnlivá délka Ušetření paměti Složitější implementace Možnost pro uložení velkých dat (obrázky, …) PA152, Vlastislav Dohnal, FI MUNI, 2013 17 Pří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 n o v á k 02 83 d l o u h ý 01 schéma záznamy  Zarovnání na „vhodnou“ délku  Rychlejší přístup k paměti zarovnané na 4 (8) bajtů PA152, Vlastislav Dohnal, FI MUNI, 2013 18 Příklad – proměnlivý formát i délka  Zaměstnanec: Nazýváno „Tagged fields“ Kódy identifikující názvy atributů mohou být přímo textové řetězce, tzv. tagy. 4I52 4S HCEČ46#Fields Codeidentifying fieldasid Integertype CodeforEname Stringtype Lengthofstr. PA152, Vlastislav Dohnal, FI MUNI, 2013 19 Příklad – opakující se atribut  Zaměstnanec má děti Vhodné v případě polí (arrays) atp.  Opakování atributu neznamená proměnlivou délku ani schéma Lze určit maximální počet opakování  Nevyužité místo vyplnit NULL 3 Jméno: Jan Novák Dítě: Tomáš Dítě: Pavel Novák Potápění Šachy -- PA152, Vlastislav Dohnal, FI MUNI, 2013 20 „Mezivarianta“  Mezi pevným a variabilním formátem  Přidání „typu záznamu“ 5 27 . . . . record type tells me what to expect (i.e. points to schema) record length PA152, Vlastislav Dohnal, FI MUNI, 2013 21 Hlavička záznamu  Ukládá další informace o záznamu (nesouvisející s hodnotami atributů) Čas vytvoření / změny / čtení záznamu Délka záznamu Počet atributů / ukazatel na schéma OID (Object Identifier) – „ID“ záznamu Pole pro NULL hodnoty  Jeden bit pro každý atribut … PA152, Vlastislav Dohnal, FI MUNI, 2013 22 Další problémy  Komprese Zvýšení rychlosti (méně čtu) Uvnitř záznamu (hodnoty zvlášť) Více záznamů  Efektivnější (lze vytvořit slovník)  Složitější  Kódování (šifrování) Co potom s indexy? Jak řešit rozsahové dotazy? … PA152, Vlastislav Dohnal, FI MUNI, 2013 23 Uložení objektů  Současné komerční DB podporují objekty Rozšíření relačních DBMS OODBMS  Objekt má atributy Jednoduché typy  uložit jako záznam Kolekce  vytvořit novou relaci a tam uložit  Referencovat pomocí OID PA152, Vlastislav Dohnal, FI MUNI, 2013 24 Uložení relace  Řádkové Zatím uvažovaná varianta  Sloupcové Hodnoty stejného atributu pohromadě  Příklad řádkového uložení: Order(id, cust, prod, store, price, date, qty) id1 cust1 prod1 store1 price1 date1 qty1 id2 cust2 prod2 store2 price2 date2 qty2 id3 cust3 prod3 store3 price3 date3 qty3 PA152, Vlastislav Dohnal, FI MUNI, 2013 25 Sloupcové uložení  Relace Order(id, cust, prod, store, price, date, qty) id1 cust1 id2 cust2 id3 cust3 id4 cust4 ... ... id1 prod1 id2 prod2 id3 prod3 id4 prod4 ... ... Id mohou ale nemusí být uloženy, lze využít pořadí hodnot … PA152, Vlastislav Dohnal, FI MUNI, 2013 26 Porovnání  Výhody sloupcového uložení Kompaktnější uložení (nezarovnávání na bajty, komprese, …) Efektivní čtení (např. pro data mining)  Zpracovávání mála atributů, ale všech hodnot  Výhody řádkového uložení Aktualizace / vkládání je rychlejší Efektivnější při přístupu k celým záznamům Mike Stonebraker, Elizabeth O'Neil, Pat O’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, FI MUNI, 2013 27 Osnova  Ukládání dat  Záznamy  Organizace bloků  Příklady PA152, Vlastislav Dohnal, FI MUNI, 2013 28 Uložení záznamů do bloků  Záznamy Pevné délky Proměnné délky  Bloky pevné velikosti záznamy soubor bloky … PA152, Vlastislav Dohnal, FI MUNI, 2013 29 Uložení záznamů do bloků  Techniky Oddělování záznamů  Separating records Rozdělování / nerozdělování záznamů  Spanned vs. unspanned Uspořádání záznamů  Sequencing Odkazy na záznamy  Indirection PA152, Vlastislav Dohnal, FI MUNI, 2013 30 Oddělování záznamů  Záznamy pevné délky Žádný oddělovač Pamatovat počet a ukazatel na první záznam  Oddělovač  Ukládání délek záznamů (nebo počátků) V rámci záznamu V hlavičce bloku R2R1 R3blok PA152, Vlastislav Dohnal, FI MUNI, 2013 31 Míchání (shlukování) záznamů  Záznamy různých relací v jednom bloku Některá data jsou vyžadována současně Uložit je společně  zrychlené čtení Složitější implementace PA152, Vlastislav Dohnal, FI MUNI, 2013 32 Míchání (shlukování) záznamů: příklad  Relace: zákazník (zid, jméno, adresa) vklady (zid, vkl_id, výše_vkladu)  Vhodné pro dotaz Q1:  SELECT jméno, adresa, výše_vkladu FROM vklady, zákazník WHERE vklady.zid = zákazník.zid AND zákazník.zid = 2354 (2354, ‘Petr Malý’, ‘Brno’) (2354, 999001, 100) (2354, 999010, 1500) blok … … PA152, Vlastislav Dohnal, FI MUNI, 2013 33 Míchání (shlukování) záznamů: příklad  Dotaz Q2: SELECT * FROM zákazník  Shlukování nevhodné pro Q2 Záleží na četnosti jednotlivých dotazů PA152, Vlastislav Dohnal, FI MUNI, 2013 34 Míchání (shlukování) záznamů  Řešení: Nemíchat v rámci bloku Ukládat bloky blízko sebe  Stejný válec disku PA152, Vlastislav Dohnal, FI MUNI, 2013 35 Rozdělování vs. nerozdělování záznamů  Nerozdělování každý záznam součástí jednoho bloku jednodušší, ale může plýtvat místem  Rozdělování Záznam „přetéká“ mezi bloky Nutné, pokud je záznam větší než blok! R1 R2 R3 R4 R5 blok 1 blok 2 … R1 R2 R3(a) R3(b) R6R5R4 R7(a) blok 1 blok 2 … PA152, Vlastislav Dohnal, FI MUNI, 2013 36 Rozděl. vs. nerozděl. záznamů: příklad  Nerozdělování záznamů 106 záznamů, každý 2 050 bajtů (pevná délka) Velikost bloku 4 096 bajtů Celkem alokováno: 106 * 4096B Celkem využito: 106 * 2050B Využití paměti: 50,05% blok 1 blok 2 2050 bajtů nevyužito 2046 2050 bajtů nevyužito 2046 R1 R2 PA152, Vlastislav Dohnal, FI MUNI, 2013 37 Rozdělování záznamů  Záznam „přetéká“ mezi bloky Musíme udržovat pořadí bloků  Lze používat ukazatele  Záznam je rozdělen na „fragmenty“ Bitový příznak, zda je fragmentován Ukazatel na další / předchozí fragment R1 R2 R3(a) R3(b) R6R5R4 R7(a) blok 1 blok 2 … PA152, Vlastislav Dohnal, FI MUNI, 2013 38 Rozdělování záznamů  Velký atribut The Oversized-Attribute Storage Technique  TOAST or "the best thing since sliced bread”**  Rozdělení záznamu (viz předchozí)  Resp. dlouhých hodnot ve velkém atributu Komprese Rozdělení do více fyzických záznamů (interně) ** [cit. dokumentace PostgreSQL] PA152, Vlastislav Dohnal, FI MUNI, 2013 39 Rozdělování záznamů  Velká data (LOB) Bez ohledu na typ: binární i textová Uloženo zvlášť  posloupnost bloků (jiného souboru) DB neindexuje, neumí uvnitř vyhledávat ** [cit. dokumentace PostgreSQL] PA152, Vlastislav Dohnal, FI MUNI, 2013 40 Uspořádání záznamů  Záznamy jsou v souboru (a bloku) uspořádány Podle hodnoty nějakého klíče Např. sekvenční soubor  Důvod: Efektivní čtení záznamů v daném pořadí Např. pro merge-join, order by, … PA152, Vlastislav Dohnal, FI MUNI, 2013 41 Uspořádání záznamů  Uložené za sebou  Zřetězený seznam R2R1 R3 … R2R1 R3 PA152, Vlastislav Dohnal, FI MUNI, 2013 42 Uspořádání záznamů  Přetoková oblast Záznamy jsou uložené za sebou  nutné reorganizace při aktualizaci Odkaz na přetokovou oblast / blok blok R1 R2 R3 R4 R5 hlavička R2.1 R1.3 R4.7 PA152, Vlastislav Dohnal, FI MUNI, 2013 43 Odkazy na záznamy  Použití Rozdělování záznamů Odkazování bloků / záznamů (viz indexy) Zřetězování bloků (viz indexy) OODBMS: objekty ukazují na jiné objekty PA152, Vlastislav Dohnal, FI MUNI, 2013 44 Odkazy na záznamy  Adresa záznamu V paměti (memory address)  přímá adresace  4 (8) bajtový ukazatel V úložišti (db address)  sekvence bajtů popisující umístění  přímá vs. nepřímá adresace PA152, Vlastislav Dohnal, FI MUNI, 2013 45 Odkazy na záznamy  Přímá adresace Fyzická adresa záznamu Adresa v úložišti  ID disku, stopu, povrch, blok, offset v bloku Nepraktické  Např. realokace bloku nebo záznamu PA152, Vlastislav Dohnal, FI MUNI, 2013 46 Odkazy na záznamy  Nepřímá adresace Záznam (i blok) je identifikován svým ID ID = logická adresa  libovolná posloupnost bitů Převodní tabulka (map table): ID  fyz. adresa fyz. adresaID rec ID r adresa a map table …… PA152, Vlastislav Dohnal, FI MUNI, 2013 47 Odkazy na záznamy  Nepřímá adresace Nevýhoda  Zvýšené náklady  Průchod map table Výhoda  Velká flexibilita  Mazání záznamů, vkládání  Optimalizace uložení bloků PA152, Vlastislav Dohnal, FI MUNI, 2013 48 Odkazy na záznamy  Vhodná varianta = kombinace  Fyz. adresa záznamu = fyz. adresa bloku + offset  Offset je pořadí záznamu v bloku  V hlavičce je obvykle seznam odkazů na záznamy.  Výhody  Lze přesouvat záznamy v bloku  Beze změny fyz. adresy  Lze přesunout záznam do jiného bloku  V původním místě udělám odkaz na nový blok + offset  Lze zrušit map table  Nevýhoda  Nízká flexibilita přesouvání bloků (defragmentace) PA152, Vlastislav Dohnal, FI MUNI, 2013 49 Odkazy na záznamy  Používaná varianta Adresa záznamu = ID souboru + číslo bloku + offset v bloku Uložení bloku určuje systém souborů (file system) File ID, Physical Block # Block ID File System Map PA152, Vlastislav Dohnal, FI MUNI, 2013 50 Odkazy na záznamy  Nepřímý odkaz v bloku Fyz. adresa záznamu = fyz. adr. bloku + offset R3 R4 R1 R2 blok volné místo hlavička PA152, Vlastislav Dohnal, FI MUNI, 2013 51 Hlavička bloku  Přítomná v každém bloku File ID (or RELATION ID or DB ID) ID bloku (tohoto) Adresář záznamů (odkazy na data záznamů) Ukazatel na volné místo (začátek, konec) Typ bloku  např. záznamy typu 4, přetoková oblast, TOAST záznamy, … Ukazatel na další blok (např. pro indexy) Čas modifikace (popř. verze) PA152, Vlastislav Dohnal, FI MUNI, 2013 52 Modifikace záznamů v bloku  Vkládání Obvykle snadné  Mazání Správa volného místa  Změna Stejná velikost  Ok Jiná velikost  Problém stejný jako při vkládání / mazání PA152, Vlastislav Dohnal, FI MUNI, 2013 53 Mazání záznamů  Problém s odkazy na smazané záznamy Musí být neplatné Nesmí odkazovat na jiná nová data Tzv. dangling pointers R1 ? smazaný záznam PA152, Vlastislav Dohnal, FI MUNI, 2013 54 Mazání záznamů  Přímá adresa záznamu (fyzická adresa) Označ jako smazané  Vytvořením značky (tombstone)  Stačí 1 bit  Implementace: obvykle několik bajtů (zarovnání) Oznámit volné místo  Zřetězení volných míst blok nelze znovu využít volné místo PA152, Vlastislav Dohnal, FI MUNI, 2013 55 Mazání záznamů  Nepřímá adresace Map table Smazaný záznam uvolní místo v bloku Náhrobek je v map table ID LOC 7788 Map Table Tuto položku nelze již znovu využít. PA152, Vlastislav Dohnal, FI MUNI, 2013 56 Mazání záznamů  Adresa záznamu je adr. bloku + offset Ihned uvolni místo Defragmentuj ostatní záznamy  volné místo je souvislé V adresáři záznamů nastav ukazatel na null blok volné místo R3 R4 R1 R2 PA152, Vlastislav Dohnal, FI MUNI, 2013 57 Mazání záznamů  Uložení ID záznamu přímo v záznamu Při čtení záznamu kontrolujeme ID na shodu PA152, Vlastislav Dohnal, FI MUNI, 2013 58 Vkládání záznamů  Neuspořádané záznamy Vkládáme na konec  Poslední blok, popř. nový 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, FI MUNI, 2013 59 Vkládání záznamů  Uspořádané záznamy Nemožné, pokud není nepřímá adresace ani se nepoužívají offsety 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 Ulož do přetokového bloku  Odkaz na přetokový blok je součástí hlavičky bloku PA152, Vlastislav Dohnal, FI MUNI, 2013 60 Aktualizace záznamů  Zvětšení délky záznamu Nemusí se vytvářet náhrobky Posunout následující záznamy Vytvořit přetokový blok …  Zmenšení délky záznamu dtto Zrušení uvolněných přetokových bloků PA152, Vlastislav Dohnal, FI MUNI, 2013 61 Správa vyrovnávací paměti  Různé strategie LRU, FIFO, pinned blocks, toss-immediate, …  Problém odkazování na záznamy v paměti Prohazování odkazů (swizzling)  Specifikum databází Někdy je nutné ponechat bloky v cache „déle“  Indexy, vyhodnocování spojení relací, … Správa vyrovnávací paměti  LRU Při každém přístupu aktualizovat čas přístupu  může být časově náročné  FIFO Uloží se čas načtení a ten se dále nemění  nevhodné pro stále používané bloky  Např. kořen B+ stromu  Pinned blocks Bloky trvale v paměti PA152, Vlastislav Dohnal, FI MUNI, 2013 62  Hodiny („Clock“) Efektivní aproximace LRU Ručka ukazuje na poslední načtený blok. Pro načtení nového bloku se ručka otáčí, dokud nenalezne volné místo (blok s nulou). Pak načte požadovaný blok a nastaví 1 Ručka při otáčení snižuje číslo (až na nulu).  Lze implementovat i pinned blocks. Jak? Správa vyrovnávací paměti PA152, Vlastislav Dohnal, FI MUNI, 2013 63 1 1 0 0 1 1 1 00 0 1 0 Správa vyrovnávací paměti  LRU a výpočet spojení dvou relací: Vnořené cykly: LRU nevhodný: přepisují se bloky relace s  Nutné použít pinned blocks pro relaci s PA152, Vlastislav Dohnal, FI MUNI, 2013 64 For each ts in s do For each tr in r do Join tr and ts r s s1 s2 r1 r2 r3 buffers 1 buffers s1 r1 r2 2 3 Načtení 1. záznamu z s a zpracovávání r 4 buffers r3 s2 r2 5 3 Načtení 2. záznamu z s 4 buffers r3 s2 r1 5 6 Zpracovávání r … PA152, Vlastislav Dohnal, FI MUNI, 2013 65 Prohazování odkazů  Změna odkazů při načtení bloku do paměti a zpět (při ukládání na disk)  Odkaz pak ukazuje do paměti a ne na disk Rec A blok 1 blok 2 blok 1 Paměť Disk PA152, Vlastislav Dohnal, FI MUNI, 2013 66 Prohazování odkazů  Po načtení bloku 2 je provedena změna odkazu Rec A blok 1 blok 2 blok 1 Paměť Disk Rec A blok 2 PA152, Vlastislav Dohnal, FI MUNI, 2013 67 Prohazování odkazů  Kdy: Automaticky – ihned po načtení Na žádost – při prvním použití Nikdy – vždy se používá překladová tabulka  Implementace: DB adresa je měněna na paměťovou adresu  Buduje se Translation table  dvojice (paměť. adresa, disková adresa) pro každý záznam Ukazatel má příznak, zda byl prohozen či ne PA152, Vlastislav Dohnal, FI MUNI, 2013 68 Osnova  Ukládání dat  Záznamy  Organizace bloků  Příklady PA152, Vlastislav Dohnal, FI MUNI, 2013 69 Vlastní implementace  Otázka náročnosti operací: Načtení záznamu s daným klíčem  Načtení následujícího záznamu Vložení / smazání / aktualizace záznamů Čtení celého souboru Reorganizace souboru Flexibilita Využití místa Složitost Výkonnost PA152, Vlastislav Dohnal, FI MUNI, 2013 70 Specializované systémy  BigTable Distribuované úložiště n-tic od Google Šká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  HBase Distribuované úložiště n-tic Open-source Apache projekt Hadoop http://hadoop.apache.org/ Vlastnosti BigTable a HBase  Nejsou relační databáze Tzv. NoSQL databáze  Storage as a “keyvalue” map row_id, column_id, time  value  Proměnné schéma relace  Verzování podle času  Uspořádané podle row_id PA152, Vlastislav Dohnal, FI MUNI, 2013 71