Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|InfMenZhNagyFeladat}} ==Feladat== Szamitsa ki az indexalapu egymasba agyazott hurok (indexed nested loop) modszerrel vegrehajtott join kolts…”

2012-10-21T20:34:27Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|InfMenZhNagyFeladat}} ==Feladat== Szamitsa ki az indexalapu egymasba agyazott hurok (indexed nested loop) modszerrel vegrehajtott join kolts…”

Új lap

{{GlobalTemplate|Infoszak|InfMenZhNagyFeladat}}

==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.

====<span style="color:red"> ''ezt a módszert nem Sorted Merge Join-nak hívják? az ugye nem azonos a Nested loop join-nal??'' -- Habib </span> ====
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

====<span style="color:red"> ''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 </span> ====

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.

-- [[PallosPeter|Peti]] - 2006.12.04.

[[Category:Infoszak]]

InfMenZhNagyFeladat - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|InfMenZhNagyFeladat}} ==Feladat== Szamitsa ki az indexalapu egymasba agyazott hurok (indexed nested loop) modszerrel vegrehajtott join kolts…”