InfMenZhNagyFeladat

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

Feladat

Szamitsa ki az indexalapu egymasba agyazott hurok (indexed nested loop) modszerrel vegrehajtott join koltseget, ha elsodleges B* fa stukturaju indexeket hasznaltunk a join attributumok szerinti rekordeleresre! A blokkmeret 4000 byte. Melyik relacio legyen kulso hurokban? Hanyszoros valaszidot kapunk, ha az optimalizacio rosszul dont? Mivaltozik ha csak masodlagos (B* fa) index letezik join attributumokra?

 * 1. relacio: 12.000 rekord, rekordhossz: 330 byte, 6 byte-os kulcs, 4 byte-os mutato
 * 2. relacio: 150.000 rekord, rekordhossz: 100 byte, 10 byte-os kulcs, 4 byte-os mutato

A feladat megoldásához pontosan kell tudni, hogy mi a különbség az elsődleges és a másodlagos index között. Elsődleges index: Fizikailag rendezett adatbázist jelent. Minden egyes új rekordot a megfelelő helyre szúrunk be. Másodlagos index: Felépítünk egy B*-fát mely a csomópontjaiban (kulcs,mutató) párokat tartalmaz. Új rekord beszúrásakor a (kulcs,mutató) párokat módosítjuk.

Megoldás

Elsődleges index algoritmus

Ha elsődleges indexet használunk, akkor csak egyszer kell végigolvasni a relációk rekordjait, mert fizikailag rendezve vannak.

Vegyük az 'A' reláció első rekordját és addig olvassuk a 'B' reláció rekordjait, amíg nem találunk egyezést. Ezután beolvassuk a következő rekordot az 'A' relációból és a 'B' relációból is. (Mivel fizikailag rendezve van mindkét reláció, ezért biztosak lehetünk abban, hogy az 'A' reláció következő rekordja nem szerepelhet a 'B' reláció utoljára beolvasott rekordja előtt). A következő egyezés után ismét vesszük az 'A' reláció következő rekordját és a 'B' reláció következő rekordját. Ezt addig folytatjuk amíg végig nem olvastunk az egyik relációt.

ezt a módszert nem Sorted Merge Join-nak hívják? az ugye nem azonos a Nested loop join-nal?? -- Habib

A nested loop-nál nincs kikötve, hogy a második reláció rendezve legyen, de most rendezve van. Ugyanakkor a Nested loop az lenne, hogy az index segítségével érjük el a második relációt. szerintem.

Válasz

A join költsége az 'A' és a 'B' reláció blokkjainak a száma. Ebből látszik hogy itt mindegy hogy melyik reláció van a külső hurokban. A válaszidő mindkét esetben ugyanaz.

///

• gondolom ez nem igaz, mert a jegyzetben az indexed nested loop join költségére a képlet:

br * nr * c (ahol: c - a belső indexelt reláció kiválasztási költsége br / nr a külső reláció blokkszáma/rekordszáma)* ///

Számolás

E = Ba + Bb (ahol B a blokkszám, E a költség)

Ki kell számolni, hogy az egyes relációk rekordjai hány blokkban fognak elférni. A blokkméret 4000 byte. Ezért az első relációnál egy blokkban 4.000/300 egészrésze, vagyis 13 rekord fér el. A második relációnál 4.000/100 egészrésze, vagyis 40 rekord fér el. ==> az első reláció 12.000/13 felső egészrésze : 924 blokk -ban fér el. A második reláció 150.000 / 40 felső egészrésze = 3750 blokkban fér el ==> a teljes költség 3750 + 924 = 4674 blokk olvasás.

Másodlagos index algoritmus

Ha másodlagos indexet használunk, akkor egy kicsit bonyolultabb a helyzet.

Itt egy B* fában tárolunk (kulcs,mutató) párokat, amelyek alapján eljutunk a levelekben tárolt rekordokhoz. Ehhez legalább annyi blokkot kell beolvasni, mint amennyi a B* fa szintjeinek a száma. Ezért meg kell határozni a B*-fa szintjeinek a számát. Mivel megadták a (kulcs,mutató) párok méretét, ezért ki tudjuk számolni, hogy egy blokkba hány ilyen pár fér el (F). Egy csomópontból (vagyis blokkból) ennyi él fog kifelé mutatni. A blokkok (B) és mutatók (F) számból meg lehet határozni a B*- fa szintjeinek a számát (HT-t) a következő képlettel. HT = log_F (B) = ln(B)/ln(F) (áttérés új alapra) egészrész (ne felejtsük el hogy egy mutató nem egy rekordra, hanem egy blokkra mutat ezért ln(B)/ln(F) nem pedig ln(R)/ln(F)). A Join költsége a külső reláció blokkszáma (Bk) + belső reláció kiválasztásának költsége (HTb + 1) * a külső reláció rekordszámával. E = Bk + nk* (HTb + 1) (ahol Bk: külső reláció blokkszáma / HTb: belső (és rendezett) Reláció másodlagos index B*-fa szintjeinek a száma nk: külső reláció rekordjainak a száma)

Ezt a költséget meg kell határozni mind a két esetben és a kisebbet kell kiválasztani. Ezek után pedig meg kell határozni a kettő költség hányadosát.

Számolás

Tudjuk hogy:

• az első relációban a blokkok száma : 924
• a második relációban a blokkok száma : 3750

Az első relációnál egy blokkba 4000 / (6 + 4) = 400 (mutató,kulcs) pár fér el. A második relációnál egy blokkba 4000 / (10 + 4) egészrésze = 286 (mutató,kulcs) pár fér el.

A szintek száma:

• Az első relációban: ln(924)/ln(400) egész része = 1
• A második relációban ln(3750)/ln(286) egész része = 1

Amikor valaminek az egész részét veszed, akkor pont elhagysz valamennyi információt, tehát kimarad valami a fából, vagy tévedek? Itt nem pont felső egészt kéne venni? -- Habib

Ha az első reláció a külső E1 = 924 + 12.000 * (1+ 1) = 24.924

Ha a második reláció a külső E2 = 3750 + 150.000 * (1+ 1) = 303.750

Válasz a feladatra

Az első reláció legyen a külső hurokban, ha az optimalizáló rosszul dönt, akkor E2/E1 = 303.750 / 24.924 ~ 12 szeres válaszidőt kapunk.

-- Iwatt Róbert, info2002 - 2006.12.03.

-- Peti - 2006.12.04.