PA152: Efektivní využívání DB
1. Úvod
Vlastislav Dohnal
PA152, Vlastislav Dohnal, FI MUNI, 2011 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
 Pavel Rychlý
 Fakulta informatiky, Masarykova Univerzita
PA152, Vlastislav Dohnal, FI MUNI, 2011 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, 2011 4
Požadavky
Ukončení předmětu:
Zkouškou
 Vypracování 3 domácích úloh
 zadání pošlu e-mailem
 odevzdání v termínu
 Složení zkouškové písemky
 6 příkladů, každý za 3 body
 A ≥ 17, B ≥ 15, C ≥ 13, D ≥ 11, E ≥ 9, F < 9
Zápočtem
 Vypracování 3 domácích úloh
 a odevzdání v termínu
PA152, Vlastislav Dohnal, FI MUNI, 2011 5
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
PA152, Vlastislav Dohnal, FI MUNI, 2011 6
Příklad
 Implementovat databázi je snadné:
relace  příkaz  výsledek
 Relace jsou v souborech na disku
Relace R je v /usr/db/R
Novák # 123 # CS
Starý # 522 # EE
.
.
.
PA152, Vlastislav Dohnal, FI MUNI, 2011 7
Příklad 2
 Seznam platných relací v adresáři
/usr/db/directory
R # jmeno # STR # id # INT …
R2 # C # STR # A # INT …
.
..
PA152, Vlastislav Dohnal, FI MUNI, 2011 8
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, 2011 9
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, 2011 10
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á, přidej do výsledku
PA152, Vlastislav Dohnal, FI MUNI, 2011 11
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, 2011 12
Problémy implementace
 Žádné souběžné zpracování
 Žádná spolehlivost
Možná ztráta dat
Operace nemusí být dokončena
 Žádná bezpečnost
Přístup na úrovni systému souborů
(filesystem)
Práva jsou příliš hrubozrná
 Není API, není GUI
PA152, Vlastislav Dohnal, FI MUNI, 2011 13
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, 2011 14
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, 2011 15
Databázový systém
 DBMS (Database Management System)
Architektura:
PA152, Vlastislav Dohnal, FI MUNI, 2011 16
Čá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, 2011 17
Části databázového systému
Buffer Manager
DDL Compiler
DB Admin
Query Compiler Transaction Manager
User/application
Logging & RecoveryExecution Engine
Storage Manager
Index/record Manager
Buffers
Storage
Concurrency Control
Lock Table
read/write pages
page commands
index/record
requests
query plan
query/update
transaction commands DDL commands
log pages
PA152, Vlastislav Dohnal, FI MUNI, 2011 18
 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, 2011 19
Mooreův zákon
 Zdvojnásobení tranzistorů za cca každé
2 roky
Rychlost procesorů
Kapacita pamětí
Kapacita disků (Kryder's Law)
 Pozor: neplatí pro rychlost disku
PA152, Vlastislav Dohnal, FI MUNI, 2011 20
Mooreův zákon
PA152, Vlastislav Dohnal, FI MUNI, 2011 21
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ávislé 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, 2011 22
Diskové úložiště
 Rotační disk
Velká kapacita, nezávislý na napájení
Čtení a zápis téměř stejně rychlé
PA152, Vlastislav Dohnal, FI MUNI, 2011 23
Rotační disk
 Přístupová doba (access time)
Čas mezi požadavkem na čtení/zápis a
počátkem přenosu dat
 Složky:
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, 2011 24
Rotační disk (pokrač.)
Přenosová rychlost
 Rychlost čtení/zápisu dat z/na disk
 25-100MB/s, nižší pro vnitřní stopy
 Rychlost řadiče
Více disků připojených na jeden řadič
SATAII (3Gb/s) – 350 MB/s
SCSI Ultra 320 – 320 MB/s
PA152, Vlastislav Dohnal, FI MUNI, 2011 25
Rotační disk
 Vlastnosti
Náhodné čtení je pomalé – access time 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žadavku
současně
PA152, Vlastislav Dohnal, FI MUNI, 2011 26
Rotační disk
 Příklad
SATAII disk, 7200rpm, 300MB/s, 8.9ms seek
 Avg seek time = 8.9ms
 Avg latency = (1/(7200/60))*0.5=0.00417s=4.17ms
Čtení sektoru (512B) = 13.07ms + 1.63μs
10MB souvisle = 13.07ms + 33.3ms
10MB náhodně = 20480*13.07163ms = 268s
PA152, Vlastislav Dohnal, FI MUNI, 2011 27
Diskové operace
 Přístup po blocích (atomická jednotka)
Skupina sousedních sektorů
Typicky 4KB – 16KB
 Čtení / zápis bloku
 Modifikace bloku:
Čtení
Změna v paměti
Zápis
Ověření = otočení disku + čtení !
PA152, Vlastislav Dohnal, FI MUNI, 2011 28
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, 2011 29
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