PA152: Efektivní využívání DB
1. Úvod
Vlastislav Dohnal
PA152, Vlastislav Dohnal, FI MUNI, 2015 2
Poděkování
 Zdrojem materiálů tohoto předmětu jsou:
Přednášky CS245, CS345, CS345
 Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer
Widom
 Stanford University, California
Přednášky dřívější verze PA152 (podzim 2008)
 Pavel Rychlý
 Fakulta informatiky, Masarykova Univerzita
PA152, Vlastislav Dohnal, FI MUNI, 2015 3
Literatura
 Knihy
Database Systems Implementation
 Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer
Widom
 Prentice Hall, 2000
 Signatura knihovny D89
Database Systems: The Complete Book
 Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer
Widom
 2nd edition, Prentice Hall, 2009
 Signatura knihovny D147
PA152, Vlastislav Dohnal, FI MUNI, 2015 4
Požadavky pro ukončení ZKOUŠKOU
 Vypracování 3 domácích úloh
 zadání pošlu e-mailem
 každá hodnocená 0-5 body
 odevzdání v termínu (pozdě  0 bodů)
 samostatné vypracování (opis  0 bodů)
 Složení zkouškové písemky
 6 příkladů, každý za 6 bodů
 Hodnocení
 Součet bodů z domácích úloh a zkouškové
písemky
 A ≥ 47, B ≥ 42, C ≥ 37, D ≥ 32, E ≥ 27, F < 27
PA152, Vlastislav Dohnal, FI MUNI, 2015 5
Požadavky pro ukončení ZÁPOČTEM
 Vypracování 3 domácích úloh
 zadání pošlu e-mailem
 každá hodnocená 0-5 body
 odevzdání v termínu (pozdě  0 bodů)
 samostatné vypracování (opis  0 bodů)
 Hodnocení
 ≥ 10 bodů z domácích úloh
 Pozor:
 některé studijní obory mají PA152 jako povinný
předmět, pak musíte mít zapsánu zkoušku
PA152, Vlastislav Dohnal, FI MUNI, 2015 6
Základní pojmy
 „Databáze“
 „Programuje“ většina programátorů
 potřebuje každá firma
 je součástí většiny aplikací
 Relační model
 Struktura – data v relacích (tabulkách)
 Operace – dotazování, modifikace
 SQL, relační algebra
 Databázový systém
 kolekce nástrojů pro ukládání a zpracování dat
 Databáze
 data, která nás zajímají, která zpracováváme
 kolekce relací, integritních omezení, indexů, …
 Schéma databáze vs. instance databáze
PA152, Vlastislav Dohnal, FI MUNI, 2015 7
Příklad implementace DB systému
 Implementovat databázi je snadné:
příkaz: relace  výsledek
 Relace jsou v souborech na disku
Relace R je v /usr/db/R
Miller # 123 # CS
Peterhansel # 522 # EE
.
.
.
PA152, Vlastislav Dohnal, FI MUNI, 2015 8
Příklad 2
 Seznam platných relací v adresáři
/usr/db/directory
R # name # STR # id # INT # dept STR …
R2 # C # STR # A # INT …
..
.
PA152, Vlastislav Dohnal, FI MUNI, 2015 9
Příklad 3
 Dotaz v „SQL“
& select A,B
from R,S
where R.A = S.A and S.C > 100
A B
123 CAR
522 CAT
&
PA152, Vlastislav Dohnal, FI MUNI, 2015 10
Příklad 4
select * from R where podmínka
 Zpracování dotazu
1. přečti adresář (dictionary) a zjisti atributy
relace R
2. čti soubor R a pro každý řádek:
a. vyhodnoť podmínku
b. pokud je platná, přidej do výsledku
PA152, Vlastislav Dohnal, FI MUNI, 2015 11
Příklad 5
select A,B from R,S where podmínka
 Zpracování dotazu
1. Přečti adresář a získej atributy R a S
2. Čti soubor R a pro každý řádek:
a. Čti soubor S a pro každý řádek:
i. Spoj oba řádky (n-tice)
ii. Vyhodnoť podmínku
iii. Pokud je platná,
proveď projekci a přidej do výsledku
PA152, Vlastislav Dohnal, FI MUNI, 2015 12
Problémy implementace
 Způsob ukládání
Řádky formátovány pomocí oddělovačů
 Změna hodnoty vede ke změně v celém souboru
Neúsporné ukládání
Mazání je drahé
 Vyhledávání je drahé
Nejsou indexy
 Hledání podle primárního klíče je pomalé
 Vždy je nutné přečíst celou relaci
PA152, Vlastislav Dohnal, FI MUNI, 2015 13
Problémy implementace
 Žádné souběžné zpracování
 Žádná spolehlivost
Možná ztráta dat
Operace nemusí být dokončena
 Žádné zajištění přístupu
Přístup na úrovni systému souborů (filesystem)
Práva jsou příliš hrubozrnná
 Není API, není GUI
PA152, Vlastislav Dohnal, FI MUNI, 2015 14
Osnova kurzu
 Úložiště dat
Hierarchie pamětí, RAID, výpadky, …
 Struktura ukládání dat
Záznamy, bloky, …
 Indexování
Stromy, hašování, …
 Zpracování dotazů
Odhad ceny, způsoby spojování relací, …
 Optimalizace dotazů
Vytváření indexů, problémy pohledů, rozdělování
relací, …
PA152, Vlastislav Dohnal, FI MUNI, 2015 15
Osnova kurzu
 Optimalizace databáze
Úpravy relačního schéma, monitorování db, …
 Transakční zpracování
Souběžné zpracování, zamykání, logování, uváznutí, …
 Bezpečnost
Práva, ochrana dat, …
PA152, Vlastislav Dohnal, FI MUNI, 2015 16
Databázový systém
 DBMS (Database Management System)
Datová abstrakce
PA152, Vlastislav Dohnal, FI MUNI, 2015 17
Hlavní součásti databázového systému
 Storage Manager
správa bloků na disku
správa vyrovnávací paměti
 Query Processor
překlad dotazu, optimalizace
vyhodnocení dotazu
 Transaction Manager
atomičnost, izolovanost a trvalost transakcí
PA152, Vlastislav Dohnal, FI MUNI, 2015 18
Části databázového systému
Buffer Manager
DDL Compiler
DB Admin
Query Compiler Transaction Manager
User/application
Logging & RecoveryExecution Engine
File Manager
Index/record Manager
Buffers
Storage
Concurrency Control
Lock Table
read/write pages
page commands
index/record
requests
query plan
query/update
transaction commandsDDL commands
log pages
PA152, Vlastislav Dohnal, FI MUNI, 2015 19
 Primární
vyrovnávací (cache)
 procesor
hlavní (operační)
 RAM
 Sekundární
disk, flash
 Terciární
záložní
 pásky, optické disky
Hierarchie pamětí
Rychlost
Kapacita
PA152, Vlastislav Dohnal, FI MUNI, 2015 20
Mooreův zákon
 Počet tranzistorů
Zdvojnásobení cca každé 2 roky
Rychlost procesorů
Kapacita pamětí
 Kapacita disků?
Kryder's Law – 1000 more in 15 years
Pozor: nikoli pro rychlost disku
PA152, Vlastislav Dohnal, FI MUNI, 2015 21
Mooreův zákon
PA152, Vlastislav Dohnal, FI MUNI, 2015 22
Paměťová úložiště
 Cache
 Nejrychlejší a nejdražší, závislé na napájení
 RAM
 Rychlé – 10-100 ns (1 ns = 10–9 s)
 Přiliš malé nebo drahé pro uložení celé databáze
 Závislé na napájení
 Flash
 Rychlé čtení, nezávislost na napájení
 Pomalý zápis – nejdříve smazat, pak zápis
 Zapisuje se celá oblast (banka)
 Omezený počet zapisovacích cyklů
PA152, Vlastislav Dohnal, FI MUNI, 2015 23
Paměťová úložiště
 Rotační disk
Velká kapacita, nezávislost na napájení
Čtení a zápis téměř stejně rychlé
PA152, Vlastislav Dohnal, FI MUNI, 2015 24
Rotační disk
 Přístupová doba (access time)
 Čas mezi požadavkem na čtení/zápis a počátkem
přenosu dat
 Data jsou blokována
 atomická jednotka čtení je sektor/diskový blok
 Složky přístupové doby
 Vystavení hlaviček (seek time) – 4-10 ms
 Přesun na správnou stopu disku
 Average seek time = ½ nejhorší případ seek time
 Rotační zpoždění – 4-11ms (5400-15k rpm)
 Čas pro otočení disku na správný sektor
 Average latency = ½ nejhorší případ latency
PA152, Vlastislav Dohnal, FI MUNI, 2015 25
Rotační disk (pokrač.)
Přenosová rychlost
 Rychlost čtení/zápisu dat z/na disk
 50-200MB/s, nižší pro vnitřní stopy
 Rychlost řadiče
Více disků připojených na jeden řadič
SATA 3.0 (6Gb/s, 600 MB/s)
SAS-2 (6Gb/s, 600MB/s)
Host Bus
Adapter
PA152, Vlastislav Dohnal, FI MUNI, 2015 26
Rotační disk (pokrač.)
 Vlastnosti
Náhodné čtení je pomalé
 access time can be up to 20ms
Sekvenční čtení je rychlé
 Optimalizace přístupu v HW
Cache
 Buffery pro zápis, zálohovány baterií nebo flash
Algoritmy pro minimalizaci pohybu hlavičky
 Algoritmus „výtah“
 Fungují pouze při velkém počtu požadavků
současně
PA152, Vlastislav Dohnal, FI MUNI, 2015 27
Rotační disk (pokrač.)
 Příklad SATAII disk, 7200rpm, 100MB/s
 Avg seek time = 8.9ms
 Avg latency = (1/(7200/60))*0.5=0.00417s=4.17ms
Čtení sektoru (512B) = 13.07ms + 4.88μs
10MB souvisle = 13.07ms + 100ms = 113ms
 souvislé čtení obsahuje i
 přesun na další stopu – změna povrchu / cylindru
 toto zanedbáváme
10MB náhodně = 20480*13.07488ms = 268s
Rotační disk (pokrač.)
186
0,722
2,052
64,12
0 20 40 60 80 100 120 140 160 180 200
Sequential
Random 4KiB
Random 4KiB
(queue 32)
Random 512 KiB
MB/s
MB/s
PA152, Vlastislav Dohnal, FI MUNI, 2015 28
Western Digital 10EZEX 1TB, SATA3, 7200 RPM, sustained transfer rate 150 MB/s
PA152, Vlastislav Dohnal, FI MUNI, 2015 29
Diskové operace
 Přístup po blocích (atomická jednotka)
Skupina sousedních sektorů
Typicky 4KB – 16KB
 Čtení bloku
 Zápis bloku
Zápis a ověření (otočení disku + čtení !)
 Modifikace bloku:
Čtení
Změna v paměti
Zápis a ověření
PA152, Vlastislav Dohnal, FI MUNI, 2015 30
Algoritmy v DB
 Pracují s bloky
 Minimalizují počet náhodně čtených bloků
 Náklady na čtení a zápis jsou stejné
PA152, Vlastislav Dohnal, FI MUNI, 2015 31
Databáze na FI
 MySQL, PostgreSQL, Oracle
 PostgreSQL http://www.postgresql.org/
Zdarma i pro komerční aplikace
Technické informace http://www.fi.muni.cz/tech/unix/databaze.xhtml
 Podle návodu si vytvořte účet
Pro připojení použijte pgAdmin http://www.pgadmin.org/
Nebo phpPgAdmin http://phppgadmin.sourceforge.net/
 Dostupný na https://mufin.fi.muni.cz/phppgadmin/
 Zvolte server DB FI MUNI,
 databázi pgdb,
 schéma podle Vašeho loginu
Nebo Adminer https://mufin.fi.muni.cz/adminer/