Kapcsolás két táblával

Kétirányú összekapcsoláskor fontoljuk meg:

• A kapcsolási attribútumok rendezettek, vagy indexeltek?
• Bármelyik reláció befér-e a memóriába?
  • Igen, akkor mehet egy futamban
  • Fenébe, akkor \(\log_M B\) futamra lesz szükség
    • M a pufferoldalak száma
    • B a kissebb reláció oldalainak száma
• Algoritmus?
  • Nested Loop
  • Hash
  • Sort
  • Index

A példákban \(L\Join R\) sorrendet vesszük alapul.

Nested Loop Join

• Legrosszabb eset
• Direkt szorzathoz mást nem tudunk
• Ha se nem indexált, se nem rendezett az állomány a kapcsolási feltétel szerint
• Join:
  • Beolvas annyi oldalt L-ből, amennyit csak tud
  • Átadja a valamennyi oldalt egy R beli sornak
  • rest is history

Sort Merge Join

• Hasznos ha valamelyik reláció rendezett
• Ha a másik nem rendezett, azt megtesszük
  • helyben, ha elfér a memóriában
  • futamokban, ha nem
• Oszd fel a relációt \(M\) részre
• Rendezd, majd merge-eld a rendezett tömböket
  • utána mehet is a háttértárra
• Eredmény rendezett lesz a kapcsolási feltétel szerint (duh, most rendeztünk)
• Mind a két táblán így csak egyszer kell végigmenni
  • (a másodikon rendezést ne számold, az elveszi a varázst)

Hash Join

• Mindkét relációt ugyanazzal a hasítófüggvénnyel bontjuk szét
  • A hasítófüggvényt úgy kell megválasztani, hogy az eredmény vödrök (kosarak) beférjenek a memóriába
• A táblákat így csak egyszer kell bejárni
  • (és most tényleg)
• A kapcsoláskor a L kezd a memóriában, és R ből veszünk mellé rekordokat

Index Join

• Leggyakoribb eset
• A kapcsolási attribútum R-ben indexált
• R rekordjait az indexek előfordulása adja meg L-ből
• Ha az indexünk egy klaszter B fa, akkor sort-join alkalmazható csak az index használatával

Index Join - Költség

Többinél nem volt, evvan

• \(B_L + T_L \times C\)
• \(C\) basically az index alapú kiválasztás költsége a R-nek
  • Klaszterindexnél: \(C=\dfrac{B_R}{I}\)
  • Nem-klaszterindexnél: \(C=\dfrac{T_R}{I}\)