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