PA152: Efektivní využívání DB
10. Ladění schéma
Vlastislav Dohnal
PA152, Vlastislav Dohnal, FI MUNI, 2011 2
Poděkování
 Zdrojem materiálů tohoto předmětu jsou:
Database Tuning (slides)
 Dennis Shasha, Philippe Bonnet
 Morgan Kaufmann, 1st edition, 440 pages, 2002
 ISBN-13: 978-1558607538
 http://www.databasetuning.org/
PA152, Vlastislav Dohnal, FI MUNI, 2011 3
Schéma
 Schéma relace
Seznam atributů, jejich typů a integritních
omezení
Např.
 Relace student(uco, jmeno, prijmeni, datum_narozeni)
 Schéma databáze
Schéma všech relací
PA152, Vlastislav Dohnal, FI MUNI, 2011 4
Rozdíly ve schématech
 Stejná data lze uložit různými způsoby
 Příklad
Dodavatelé
 Adresa
Objednávky
 Výrobek, počet, dodavatel
PA152, Vlastislav Dohnal, FI MUNI, 2011 5
Rozdíly ve schématech
 Alternativy
Schéma 1
 Objednávka1(dodavatel_id, výrobek_id, počet,
dodavatel_adresa)
Schéma 2
 Objednávka2(dodavatel_id, výrobek_id, počet)
 Dodavatel(id, adresa)
 Rozdíly
Schéma 2 šetří místem
Schéma 1 nemusí zachovat adresu, pokud
není objednávka
PA152, Vlastislav Dohnal, FI MUNI, 2011 6
Rozdíly ve schématech
 Rozdíly ve výkonu
Častý přístup k adrese dodavatele
konkrétního výrobku
  schéma 1 je vhodnější (není potřeba spojení)
Mnoho objednávek
  schéma 1 plýtvá místem (relace bude mít
mnoho bloků)
PA152, Vlastislav Dohnal, FI MUNI, 2011 7
Teorie pro správný návrh schéma
 Normální formy
1NF, 2NF, 3NF, Boyce-Coddova NF, …
 Funkční závislost
A  B
 B funkčně závisí na A
 Hodnotu atributu B zjistíme, pokud známe hodnotu
atributu A
 Nechť t, s jsou řádky relace
Platí: t[A] = s[A]  t[B] = s[B]
PA152, Vlastislav Dohnal, FI MUNI, 2011 8
Teorie pro správný návrh schéma
 Objednávka1(dodavatel_id, výrobek_id,
počet, dodavatel_adresa)
 Příklad funkčních závislostí
dodavatel_id  dodavatel_adresa
dodavatel_id, výrobek_id  počet
PA152, Vlastislav Dohnal, FI MUNI, 2011 9
Teorie pro správný návrh schéma
 K je primární klíč
K  R
L  R pro libovolné L  K
 Tj. pro každý atribut A z R platí: K  A a L  A
 Příklad
Dodavatel(id, adresa)
id  adresa
id je primární klíč
PA152, Vlastislav Dohnal, FI MUNI, 2011 10
Teorie pro správný návrh schéma
 Příklad
Objednávka1(dodavatel_id, výrobek_id,
počet, dodavatel_adresa)
dodavatel_id  dodavatel_adresa
dodavatel_id, výrobek_id  počet
dodavatel_id, výrobek_id je primární klíč
PA152, Vlastislav Dohnal, FI MUNI, 2011 11
Normalizace schéma
 1NF – všechny atributy jsou atomické
 2NF – všechny atributy závisí na klíči
 3NF – všechny atributy závisí přímo na klíči
není tranzitivní závislost
 Normalizace = převod do 3NF
PA152, Vlastislav Dohnal, FI MUNI, 2011 12
Normalizace schéma
 Relace R je normalizovaná pokud
Pro každou funkční závislost X  A nad
atributy relace R platí, že X je (super-)klíč.
 Příklad
Objednávka1(dodavatel_id, výrobek_id,
počet, dodavatel_adresa)
 dodavatel_id  dodavatel_adresa
 dodavatel_id, výrobek_id  počet
Není normalizovaná
PA152, Vlastislav Dohnal, FI MUNI, 2011 13
Normalizace schéma
 Příklad
Objednávka2(dodavatel_id, výrobek_id,
počet)
 dodavatel_id, výrobek_id  počet
Dodavatel(id, adresa)
 id  adresa
Schéma je normalizované
PA152, Vlastislav Dohnal, FI MUNI, 2011 14
Příklad normalizace
 Banka
Zákazník má otevřený účet
Zákazník má korespondenční adresu
Účet je vedený konkrétní pobočkou banky
 Je relace normalizovaná?
Banka(zákazník, účet, adresa, pobočka)
PA152, Vlastislav Dohnal, FI MUNI, 2011 15
Příklad normalizace
 Relace
Banka(zákazník, účet, adresa, pobočka)
zákazník  účet
zákazník  adresa
účet  pobočka
 Zákazník je primární klíč
 Relace není normalizovaná
Máme tranzitivní závislost
PA152, Vlastislav Dohnal, FI MUNI, 2011 16
Příklad normalizace
 Rozklad relace na
Banka(zákazník, účet, adresa)
 zákazník  účet
 zákazník  adresa
Účet(účet, pobočka)
 účet  pobočka
Nyní již je normalizované
PA152, Vlastislav Dohnal, FI MUNI, 2011 17
Postup návrhu schéma
 Identifikace entit
Zákazník, dodavatel, objednávka, …
 Každá entita má atributy
Zákazník má adresu, telefon, …
 Entita musí splňovat:
1. Atribut nemá další atribut (je atomický).
2. Musí existovat funkční závislost pro každý
atribut.
PA152, Vlastislav Dohnal, FI MUNI, 2011 18
Postup návrhu schéma
 Každá entita je nová relace
 Vztah mezi entitami je vyjádřen novou
relací
PracujeNa(zaměstananec_id, projekt_id)
 Nalezení funkčních závislostí mezi všemi
atributy a kontrola normalizace schéma
Pokud existuje závislost AB  C, pak ABC
musí být ve stejné relaci.
PA152, Vlastislav Dohnal, FI MUNI, 2011 19
Vertikální dělení
 Entita zákazník má id, adresu a zbývající
kredit
Závislosti:
 id  adresa
 id  kredit
 Normalizované schéma
 Zákazník(id, adresa, kredit)
Nebo
 ZákazníkAdresa(id, adresa)
 ZákazníkKredit(id, kredit)
Které je vhodnější?
PA152, Vlastislav Dohnal, FI MUNI, 2011 20
Vertikální dělení
 Volba správného schéma závisí na
způsobu používání (dotazování)
Výpisy z účtu jsou posílány jednou měsíčně.
Kredit je měněn po každém telefonním
hovoru.
  Druhé schéma je vhodnější
Relace ZákazníkKredit bude menší
 Méně bloků, menší řídký index
 Může se vejít do paměti
  rychlejší table/index-scan
PA152, Vlastislav Dohnal, FI MUNI, 2011 21
Vertikální dělení
 Jedna relace je vhodnější než dvě
Pokud jsou atributy přistupovány současně
 není potřeba operace spojení
 Dvě relace jsou vhodnější
Atributy jsou přistupovány samostatně (nebo
některé řádově častěji)
Atributy jsou velké (dlouhé řetězce, …)
 Pozor LOB jsou uloženy mimo relace.
PA152, Vlastislav Dohnal, FI MUNI, 2011 22
Vertikální dělení
 Jiný příklad
Zákazník má id a adresu (ulice, místo, psč)
 Jaký má smysl schéma:
ZákazníkUlice(id, ulice)
ZákazníkMísto(id, místo, psč)
PA152, Vlastislav Dohnal, FI MUNI, 2011 23
Vertikální dělení – výkonnost
 R(X,Y,Z) - X číslo, Y a Z dlouhé řetězce
Rychlost závisí na stylu dotazování
0
0,005
0,01
0,015
0,02
No
Partitioning Query
XYZ
Vertical
Partitioning Query
XYZ
No
Partitioning Query
XY
Vertical
Partitioning Query
XY
Througput(queries/sec)Table-scan
Bez dělení:
R(X,Y,Z)
Vert. dělení:
R1(X,Y)
R2(X,Z)
SQLServer 2k
Windows 2k
PA152, Vlastislav Dohnal, FI MUNI, 2011 24
Vertikální dělení – výkonnost
 R(X,Y,Z) - X číslo, Y a Z dlouhé řetězce
Výběr 1 řádku, projekce XY nebo XYZ
0
200
400
600
800
1000
0 20 40 60 80 100
Throughput(queries/sec)
% of access that only concern XY
no vertical
partitioning
vertical
partitioning
Vert. dělení
Vhodné, pokud
vybírám XY častěji
než ve 20%
případů.
Spojení znamená
2 přístupy do
indexu.
PA152, Vlastislav Dohnal, FI MUNI, 2011 25
Vertikální spojování (antipartitioning)
 Začínáme s normalizovaným schématem
 Přidáváme atributy k jedné z relací
 Příklad
Akciový trh
 Historie cen akcií za posledních 3000 dní
 Makléř se rozhoduje hlavně podle posledních 10 dnů
Schéma
 AkcieDetail(akcie_id, datum_vydání, firma)
 AkcieCena(akcie_id, datum, cena)
PA152, Vlastislav Dohnal, FI MUNI, 2011 26
Vertikální spojování (antipartitioning)
 Schéma
AkcieDetail(akcie_id, datum_vydání, firma)
AkcieCena(akcie_id, datum, cena)
 Dotazování na 10ti denní historii je
náročné
I když je index na akcie_id, datum
Navíc pro další informace je třeba spojení s
AkcieDetail
PA152, Vlastislav Dohnal, FI MUNI, 2011 27
Vertikální spojování (antipartitioning)
 Proveďme replikaci dat
 Schéma
AkcieDetail(akcie_id, datum_vydání, firma,
cena_dnes, cena_včera, …,
cena_před_10_dny)
AkcieCena(akcie_id, datum, cena)
 Dotazování na 10ti denní historii je
1x prohledání indexu, není třeba spojení
PA152, Vlastislav Dohnal, FI MUNI, 2011 28
Vertikální spojování (antipartitioning)
 Nevýhoda
Replikace dat
 Ne příliš velká
 Lze odstranit neukládáním v AkcieCena
  dotazy na průměrné ceny se komplikují, …
PA152, Vlastislav Dohnal, FI MUNI, 2011 29
Ladění denormalizace
 Denormalizace
Porušení normalizace schéma
Pouze z důvodu rychlosti!
 Vhodné pro
Současný výběr atributů z různých relací
 Nevhodné pro
Časté aktualizace dat
  vyhledání „zdrojových“ dat kvůli replikaci
PA152, Vlastislav Dohnal, FI MUNI, 2011 30
Ladění denormalizace
 Příklad
 region(r_regionkey, r_name, r_comment);
 nation(n_nationkey, n_name, n_regionkey, n_comment);
 supplier(s_suppkey, s_name, s_address,
s_nationkey, s_phone, s_acctbal, s_comment);
 item(l_orderkey, l_partkey , l_suppkey, l_linenumber,
l_quantity, l_extendedprice, l_discount, l_tax,
l_returnflag, l_linestatus, l_shipdate, l_commitdate,
l_receiptdate, l_shipmode, l_comment);
 T(item) = 600 000
T(nation) = 25, T(region) = 5, T(supplier) = 500
 Dotaz: vyhledání položek (item) v regionu Evropa.
PA152, Vlastislav Dohnal, FI MUNI, 2011 31
Ladění denormalizace
 Denormalizovaná relace item
 itemdenormalized(l_orderkey, l_partkey, l_suppkey,
l_linenumber, l_quantity, l_extendedprice,
l_discount, l_tax, l_returnflag, l_linestatus,
l_shipdate, l_commitdate, l_receiptdate,
l_shipmode, l_comment, l_regionname);
 600 000 řádků
PA152, Vlastislav Dohnal, FI MUNI, 2011 32
Ladění denormalizace
 Dotazy:
SELECT l_orderkey, l_partkey, l_suppkey, l_linenumber,
l_quantity, l_extendedprice, l_discount, l_tax,
l_returnflag, l_linestatus, l_shipdate, l_commitdate,
l_receiptdate, l_shipinstruct, l_shipmode, l_comment, r_name
FROM item, region, supplier, nation
WHERE l_suppkey = s_suppkey AND s_nationkey = n_nationkey AND
n_regionkey = r_regionkey AND r_name = 'Europe';
SELECT l_orderkey, l_partkey, l_suppkey, l_linenumber,
l_quantity, l_extendedprice, l_discount, l_tax,
l_returnflag, l_linestatus, l_shipdate, l_commitdate,
l_receiptdate, l_shipinstruct, l_shipmode, l_comment, l_regionname
FROM itemdenormalized
WHERE l_regionname = 'Europe';
PA152, Vlastislav Dohnal, FI MUNI, 2011 33
Ladění denormalizace – výkonnost
 Dotaz
Najdi všechny položky evropských výrobců
0,0000
0,0005
0,0010
0,0015
0,0020
normalized denormalized
Throughput(Queries/sec)
Normalizované:
spojení 4 relací
Denormalizované:
jediná relace
30% vylepšení
Oracle 8i EE
Windows 2k
3x 18GB disk
(10000 ot.)
PA152, Vlastislav Dohnal, FI MUNI, 2011 34
Shlukované uložení relací
 Alternativa k denormalizaci
 Není vždy podporováno DB systémem
 Oracle
Shlukované uložení dvou relací
 Objednávka2(dodavatel_id, výrobek_id, počet)
 Dodavatel(id, adresa)
Uložení
 U záznamu dodavatele jsou uloženy jeho
objednávky
PA152, Vlastislav Dohnal, FI MUNI, 2011 35
Shlukované uložení relací
 Příklad
 Objednávka2(dodavatel_id, výrobek_id, počet)
 Dodavatel(id, adresa)
10, Inter-pro.cz Hodonín
10, 235, 5
10, 545, 10
11, Unikov Bzenec
11, 123, 30
11, 234, 2
11, 648, 10
11, 956, 1
12, Školex Modřice
12, 12, 50
12, 34, 120
…
PA152, Vlastislav Dohnal, FI MUNI, 2011 36
Horizontální dělení
 Rozděluje obsah tabulky podle řádků
Vertikální podle sloupců
 Důvod
Snížení objemu dat, se kterým se pracuje
Usnadnění mazání
 Použití
Archivace dat
Prostorové dělení
…
PA152, Vlastislav Dohnal, FI MUNI, 2011 37
Horizontální dělení
 Automaticky
Moderní (komerční) DB systémy
MS SQL Server 2005 a novější
Oracle …
 Ručně
S podporou DB systému
 Optimalizátor dotazů
Bez podpory DB systému
PA152, Vlastislav Dohnal, FI MUNI, 2011 38
Horizontální dělení
 Změny dotazů:
Automaticky
 Beze změny
Ručně
 S podporou DB systému
 Beze změny
 Dědičnost tabulek / definice pohledu (UNION ALL)
 Bez podpory DB systému
 Ruční změna dotazu
 Je třeba upravit seznam používaných tabulek ve FROM
části.
PA152, Vlastislav Dohnal, FI MUNI, 2011 39
Horizontální dělení – SQL Server
 MS SQL Server 2005 a novější
 Vytvoření dělicí funkce
 CREATE PARTITION FUNCTION
 Dělení na intervaly
 Vytvoření dělicího schéma
 CREATE PARTITION SCHEME
 Kam se budou data ukládat (na jaké oddíly úložiště)
 Vytvoření dělené tabulky
 CREATE TABLE … ON dělicí schéma
 Ukládaná data jsou automaticky dělena do oddílů
 Vytváření indexů
 CREATE INDEX
 Indexy jsou vytvářeny na oddílech tabulky, tj. automaticky
děleny
PA152, Vlastislav Dohnal, FI MUNI, 2011 40
Horizontální dělení – Oracle
 Oracle 9i a novější
Dělení podle rozsahu, výčtu (seznamu),
hašování
 Podporuje i dvojité rozdělení
 Oddíly se dělí na pododdíly
Přímo v CREATE TABLE
PA152, Vlastislav Dohnal, FI MUNI, 2011 41
Horizontální dělení – PostgreSQL
 PostgreSQL 8.2 a vyšší
Dělení podle rozsahu, výčtu (seznamu)
 Princip (http://www.postgresql.org/docs/current/static/ddl-partitioning.html)
Využití dědičnosti tabulek
Vytvoření základní tabulky
 Nebude ukládat data, bez indexů, …
Jednotlivé oddíly budou zděděné tabulky
 Pro každou tabulku definovat CHECK omezení
povolených dat
 Vytvoření případných indexů
PA152, Vlastislav Dohnal, FI MUNI, 2011 42
Horizontální dělení – PostgreSQL
 Princip
Vkládání záznamů
 Vkládání do primární tabulky
 Primární tabulka má pravidla pro vkládání
 Vkládání pouze do „nejnovějšího“ oddílu  jeden RULE
 Obecně je třeba mít RULE pro každý oddíl
 V případě pohledů se definuje INSTEAD OF trigger
PA152, Vlastislav Dohnal, FI MUNI, 2011 43
Horizontální dělení – PostgreSQL
 Příklad v db.fi.muni.cz, schéma xdohnal
Nerozdělená tabulka account
 Primární klíč id
 R(account) = 200 000
 V(account,home_city) = 5
Rozdělená tabulka account_parted
 Podle home_city (5 oddílů)
 Oddíly account_parted1 .. account_parted5
home_city | count
home_city1 | 40020
home_city2 | 40186
home_city3 | 39836
home_city4 | 39959
home_city5 | 39999
PA152, Vlastislav Dohnal, FI MUNI, 2011 44
Horizontální dělení – PostgreSQL
 Statistiky
Tabulka Řádků Velikost Indexy
account 200 000 41 984 kB 4 408 kB
account_parted 0 0 kB 8 kB
account_parted1 40 020 8 432 kB 896 kB
account_parted2 40 186 8 464 kB 896 kB
account_parted3 39 836 8 392 kB 888 kB
account_parted4 39 959 8 416 kB 896 kB
account_parted5 39 999 8 424 kB 896 kB
Celkem: 200 000 42 128 kB 4 472 kB
PA152, Vlastislav Dohnal, FI MUNI, 2011 45
Horizontální dělení – PostgreSQL
 Optimalizátor dotazů
Povolení kontroly omezení na oddílech
 Dotazy (porovnejte plány provádění)
select * from account where id=8;
select * from account_parted where id=8;
select count(*) from account where home_city='home_city1';
select count(*) from account_parted where home_city='home_city1';
select * from account where home_city='home_city1' and id=8;
select * from account_parted where home_city='home_city1' and id=8;
set constraint_exclusion=on;