V poslednφch letech, kdy ka₧d² v²robce databßzovΘho software usiluje o jeho nejv∞tÜφ v²kon, se m∙₧eme setkat s pon∞kud tajemn²m v²razem prefetch. T∞₧ko °φci, jak se s tφmto slovem vyrovnat v ΦeÜtin∞. P°itom jde v podstat∞ pouze o to, ₧e pro n∞kterΘ dotazy naΦte S╪BD z disku vφce strßnek ne₧ jednu. Zkrßtka, Φte si data ôdo zßsobyö. Abychom pochopili, k Φemu je dobrΘ, je t°eba se podφvat trochu blφ₧e na nejmocn∞jÜφho nep°φtele rychlΘho zpracovßnφ databßzov²ch dotaz∙, tj. na diskovΘ za°φzenφ.

O magnetickΘm disku (MD) se °φkß, ₧e jde o mΘdium s p°φm²m p°φstupem. Firma IBM ho uvedla na trh v r. 1956. M∞l pr∙m∞r dv∞ stopy a mo₧nost ulo₧it na krychlov² centimetr 2,5 znaku s dobou p°φstupu 100 ms. V roce 1963 byl pr∙m∞r disku redukovßn na 14 palc∙ a v²slednΘ za°φzenφ se stalo zßkladem velkokapacitnφch disk∙ na dobu vφce ne₧ 30 let. DneÜnφ nejpokroΦilejÜφ pevnΘ disky majφ pr∙m∞r 3,5 palce a jsou schopny udr₧et 6 milion∙ znak∙ na krychlov² centimetr s dobou p°φstupu 12 milisekund.

P°φm² p°φstup znamenß, ₧e lze p°φmo p°eΦφst nebo zapsat strßnku, znßme-li jejφ adresu na disku. MD, Φi lΘpe diskov² svazek, je soustava kotouΦ∙ na spoleΦnΘ ose, otßΦejφcφ se konstantnφ rychlostφ t. K MD lze p°ibli₧ovat ramφnko s Φtecφmi a zßpisov²mi hlavami. Hlavy existujφ pro ka₧d² kotouΦ, pro ka₧d² z jeho dvou povrch∙. Data na povrchu kotouΦe se uklßdajφ na soust°ednΘ kru₧nice - stopy. PodstatnΘ je, ₧e stopy, aΦ r∙zn²ch pr∙m∞r∙, majφ na konkrΘtnφm MD stejnou kapacitu. Proto₧e ramφnko s hlavami dosßhne umφst∞nφ v₧dy tak, ₧e hlavy jsou schopny b²t aktivnφ na stopßch o stejnΘm pr∙m∞ru, je v²hodnΘ zavΘst jednotku - cylindr (nebo vßlec). Cylindr se sklßdß ze vÜech stop o stejnΘm pr∙m∞ru. Pro zßpis a Φtenφ je podstatnΘ, ₧e v₧dy jedna hlava m∙₧e b²t v danΘm Φase aktivnφ, tj. na MD lze zapisovat nebo Φφst strßnku v₧dy na jednΘ stop∞. Nßrys diskovΘho za°φzenφ je na obrßzku 1.

Fyzickß adresa strßnky je u standardnφch diskov²ch za°φzenφch dßna trojicφ (Φφslo cylindru, Φφslo stopy, Φφslo strßnky). Vhodn∞jÜφ je ovÜem pou₧φvat transformaci t∞chto adres do lineßrnφho prostoru relativnφch adres 0,1,...,M-1. Velikost strßnky je volitelnß.

Pro provoz MD jsou rozhodujφcφ t°i parametry:

s (seek) - pr∙m∞rn² Φas p°esunu ramφnka z cylindru k n∞jakΘmu jinΘmu cylindru

r (rotational delay) - Φas rovn² polovin∞ otßΦky disku (pr∙m∞rnΘ rotaΦnφ zpo₧d∞nφ)

btt (block transfer time) - Φas pot°ebn² k p°enosu strßnky z MD do vnit°nφ pam∞ti nebo z vnit°nφ pam∞ti na MD.

Nap°. Φtenφ strßnky si m∙₧eme p°edstavit tak, ₧e ramφnko musφ najet k cylindru, na jeho₧ stop∞ je umφst∞na hledanß strßnka, systΘm vyΦkß v pr∙m∞ru polovinu otßΦky k najetφ zaΦßtku strßnky na urΦitΘ stop∞ na p°φsluÜnou hlaviΦku, systΘm Φte strßnku z danΘho mφsta a p°enßÜφ ji do bufferu ve vnit°nφ pam∞ti.

povrchy

stopa 0 READ/WRITE

hlavy

stopa 1

a) pohled na povrch disku

ramφnka

p°φstupov² mechanismus osa

Obr. 1: Model diskovΘho za°φzenφ

B∞₧nß rychlost otßΦenφ disku je 60 otßΦek/s, standardem se vÜak stßvajφ disky dokonce s 90 otßΦkami/s. Co se t²Φe velikosti disk∙, u za°φzenφ schopnΘho nΘst GByte dat se m∙₧eme s deseti povrchy a stopami pro 40.000 Byte. Jeden cylindr tedy m∙₧e pojmout 400.000 Byte. Diskovß jednotka pak obsahuje 2.500 cylindr∙.

NßhodnΘ p°eΦtenφ jednΘ strßnky o velikosti 4000 Byte vy₧aduje cca 0.025 s, tj. za jednu vte°inu lze provΘst 40 I/O operacφ. Tento ·daj zφskßme z typick²ch hodnot s = 0,016, r = 0,008 a btt = 0,001 (pro 4000 Byte). Je z°ejmΘ, ₧e jde o velkΘ hodnoty, specißln∞ u parametr∙ s a r. B∞₧nou strategiφ uklßdßnφ na disk tedy je uklßdat data na po sob∞ nßsledujφcφch cylindrech. DalÜφ roli p°i zpracovßnφ bude z°ejm∞ hrßt velikost strßnky. Ta je dnes u databßzov²ch server∙ nastavitelnß. B∞₧nΘ jsou hodnoty 4 KByte, existujφ vÜak i 2KBytovΘ strßnky, v poslednφ dob∞ nenφ vzßcnostφ velikost vφce n∞₧ 8 KByte. Nap°. u SYBASE Sever 11 lze pou₧φvat strßnky velikosti 2 - 16 KByte.

Uva₧ujme nynφ p°φklad tabulky ZAM╠STNANEC obsahujφcφ 200.000 °ßdk∙, z nich₧ ka₧d² mß 200 Byte. P°i velikosti strßnek 4 KByte a jejich 70% napln∞nφ, je t°eba pro celou tabulku vyhradit 14.286 strßnek. V p°φpad∞ i t∞ch nejednoduÜÜφch dotaz∙, nenφ-li pro tabulku vytvo°en ₧ßdn² index, je nevyhnutelnΘ pou₧φt sekvenΦnφ prohledßvßnφ, tj. je nutnΘ p°eΦφst v nejhorÜφm p°φpad∞ 14.286 strßnek.

Kolik takovΘ Φtenφ stojφ, lze snadno spoΦφst jako 14.286/40 = 357,15 s, co₧ je jist∞ dost ne·nosnΘ. Ve skuteΦnosti ale situace nenφ tak tragickß. P°edpoklßdßme-li strßnky ulo₧enΘ za sebou, pak nenφ nutnΘ pou₧φt odhad pro nßhodn² p°φstup. Parametr s=0 (byl nastaven na poΦßtku Φtenφ) a dßle by se zdßlo, ₧e staΦφ Φφst strßnky tak, ₧e se pln∞ vyu₧ije celß otßΦka disku, tj. ₧e vlastn∞ staΦφ vzφt btt, p°iΦem₧ celkov² Φas by byl 14.286 * btt = 14 s. Tato ·vaha ovÜem nenφ sprßvnß, proto₧e Φtenφ dvou po sob∞ jdoucφch strßnek zvlßÜ¥ nelze technicky za°φdit. DokonΦenφ operace Φtenφ toti₧ pot°ebuje jistou dobu, v nφ₧ se ovÜem disk o kousek pootoΦφ. Je tedy nutnΘ Φφst dalÜφ strßnku a₧ po provedenφ celΘ otßΦky.

P°eΦtenφ strßnky tedy stojφ 2r + btt, tj. 0,017 s. Tabulka ZAM╠STNANEC tedy po₧aduje pro p°eΦtenφ 242,86 s, co₧ je po°ßd moc. Ka₧dΘho jist∞ napadne mo₧nost Φφst strßnky ôob jednuö. Jist∞, i to je mo₧nΘ, nicmΘn∞ efekt nemusφ b²t v₧dy dostateΦn². P°i paralelnφm zpracovßnφ transakcφ m∙₧e b²t ramφnko disku v pr∙b∞hu Φtenφ posunuto k p°eΦtenφ jinΘ strßnky.

Jinou mo₧nost nabφzφ jistß paralelizace I/O operacφ, kterou docφlφme rozmφst∞nφm tabulky na vφce disk∙. Hovo°φ se o ôpßskovßnφ disk∙ö (disk striping). P°edstavme si 10 disk∙, na kterΘ rozlo₧φme strßnky s °ßdky relace zam∞stnanec zp∙sobem X MOD Y, tj. do skupin { 1, 11, 21, ...} na 1. disk, { 2, 12, 22, ... } na 2. disk, atd., tj. na 10. disku jsou strßnky { 10, 20, 30, ...} . Pak p°i paralelnφm Φtenφ z 10. disk∙ by se p∙vodnφ Φas Φtenφ celΘ tabulky redukoval na 1/10. P°esto₧e z hlediska naÜeho dotazu vypadß danΘ °eÜenφ atraktivn∞, a nekterΘ S╪BD je nabφzejφ, nejde o univerzßlnφ b∞₧n∞ pou₧φvan² p°φstup. Slo₧itΘ m∙₧e toti₧ b²t vyvß₧enφ systΘmu u jin²ch typ∙ dotaz∙. V∞tÜφ zßt∞₧ jednoho z disk∙ se stßvß brzdou pro dalÜφ.

Dobr²m kompromisem mezi pßskovßnφm a jednouch²m sekvenΦnφm Φtenφm se stßvß metoda nazvanß angl. prefetch, nebo tΘ₧ vφcestrßnkovΘ I/O. Jde o to, ₧e lze p°eΦφst n∞kolik po sob∞ jdoucφch strßnek najednou tak, jakoby tvo°ily jeden blok. Nap°. S╪BD DB/2 takto m∙₧e p°eΦφst 32 strßnek (maximßln∞ dokonce 64 strßnek). P°i nßhodnΘm Φtenφ 32 strßnek bychom pot°ebovali °as 32(0,016 + 0,008 + 0,001) = 32 * 0, 25 = 0, 8 s. P°i p°eΦtenφ 32 strßnek jako jeden celek vÜak staΦφ 0,016 + 0,008 + 32 * 0,001 = 0,056 s. Za vte°inu lze tedy p°eΦφst 571 strßnek.

Aplikujeme-li metodu na tabulku ZAM╠STNANEC, obdr₧φme Φas 14.286/571 = 25 s. A toto je ji₧ skuteΦnß ·spora. Pot°ebujeme pouze dostateΦn∞ velkou vnit°nφ pam∞¥, tj. pro sekvenΦnφ prefetch 32 strßnek se p°edpoklßdß vφce ne₧ 1000 strßnek (4 MByte) jako prostor pro buffery. P°i menÜφm prostoru pro buffery lze mφsto 32 strßnek pou₧φt odpovφdajφcφ menÜφ mno₧stvφ (nap°. 16 nebo 8).

VÜimn∞me si. ₧e prefetch m∙₧e b²t kombinovßn s pßskovßnφm, tj. Φteme-li n-tou strßnku lze p°eΦφst k nßsledujφcφch n + 1, n + 2, ..., n + k (pro vhodnΘ k) z k disk∙ vlastn∞ najednou. D∙le₧itß je dßle velikost strßnek.

Zßv∞rem se krßtce zmφnφme jeÜt∞ o jednΘ variant∞ ôrychlΘhoö Φtenφ strßnek. Jde o tzv. list prefetch. kdy se p°eΦte seznam strßnek ne nutn∞ po sob∞ jdoucφch ovÜem Φtenφ sekvence je naprogramovßno tak, aby se co nejlΘpe vyu₧ily pohyby ramφnka. Tento prefetch je pomalejÜφ ne₧ sekvenΦnφ prefetch, ale rychlejÜφ ne₧ pouhΘ nßhodnΘ Φtenφ strßnek.

OpravdovΘ vyu₧itφ tohoto zajφmavΘho zp∙sobu Φtenφ strßnek ocenφ v S╪BD a₧ jeho optimalizßtor. Ten na zßklad∞ jist²ch znalostφ o po₧adavcφch na vyhodnocenφ dotazu m∙₧e rozhodnout, kolik strßnek a zdali v∙bec se n∞jak² prefetch uskuteΦnφ. Pam∞tnφci nakonec poznßvajφ, ₧e ideu prefetch znajφ ji₧ ze 70. let, tj. z obdobφ nßvrh∙ virtußlnφch pam∞tφ. Dnes nab²vß v souvislosti s databßzemi na novΘm v²znamu. Zv∞tÜuje mo₧nosti optimalizace, proto₧e lze vyu₧φt znalostφ o tom, kterΘ strßnky bude aplikace pot°ebovat na zßklad∞ stavu aplikace samΘ. V²zkum predikce a jejφho pou₧itφ pro Φtenφ strßnek aplikaci ôdo zßsobyö se tak stßvß dalÜφ atraktivnφ alternativou v databßzovΘ technologii.