9 - Kapcsolás költségszámítás

A \(Q(A,B) \Join R(B,C) \Join S(C,D)\) háromféle kiszámítási módja és költsége feltéve, hogy \(Q,R,S\) paraméterek egyeznek, \(Q.B\) ls \(S.C\)-re klaszterindexünk van

a) balról jobbra

b) balról jobbra, memóriában hozzákapcsolva a harmadik táblával

c) a középső ténytábla soraihoz kapcsolva a szélső dimenziótáblákat

Feltevések

\(T_Q=T_R=T_S=T\)
- (ugyanannyi sorunk van)
\(B_Q=B_R=B_S=B\)
- (ugyanannyi helyet foglalnak)
\(I_Q=I_R=I_S=I\)
- (Az előforudló értékek száma is azonos. képméret)

Előzetes számítások - Példa kapcsolás

Nézzük meg, hogy hogyan is lehetne \(R(A,B)\Join S(B,C)\)-t összekötni, ha mindkettőn B indexelt
Az azonos értékhez tartozó sorokat az index alapján olvassuk be a táblából, majd memóriában kapcsoljuk
Feltehetjük, hogy az összekapcsolandó sorok elférnek a memóriában
- \(\dfrac{B_R}{I} + \dfrac{B_S}{I} \leq M\)
- Illetve \(R.B \subseteq S.B\)

Egy indexel történő beolvasás költsége kb annyi, mint a beolvasott blokkok száma

\[ \dfrac{B_R}{I_{R.B}} \text{, illetve } \dfrac{B_S}{I_{S.B}} \]

Előzetes számítások - Teljes költség

Beolvassuk R-t, majd mindes sorához index szerint S-t

\[ B_R+T_R \times \dfrac{B_S}{I_{S.B}}\,;~~ I_{R.B}=I_{S.B}=I: \]

1. Join I/O költsége

We don't bother writing the output here

\[ B_R+T_R\times \dfrac{B_S}{I} \]

2. Sorok száma

\[ T_{R\Join S}=T_R\times \dfrac{T_S}{I} \]

Ezt hogy kaptuk?

\[ T_{R\Join S}=I_{R.B}\times \left( \dfrac{T_R}{I_{R.B}} \times \dfrac{T_S}{I_{S.B}} \right) \]

Gondold meg:

Annyi rekord mindenképp kell, mint ahány sora R-nek van, hogy hozzá kapcsoljunk (Egyenletesség)

R indexéhez pedig a direkt szorzat per képméret költséget szorozzuk

Használjuk az index egyenlőségének feltevését:

\(\xRightarrow{I_{R.B}~=~I_{S.B}~=~I}~~ T_{R\Join S}\;=\;I\times \left( \dfrac{T_R}{I} \times \dfrac{T_S}{I} \right)\)

\(\Longrightarrow~~T_{R\Join S}=T_R\times \dfrac{T_S}{I}\)

3. Output mérete

\[ \dfrac{T_R \times B_S + T_S \times B_R}{I} \]

Descartes példa

\(R\times S\) esetén \(T_R \times B_S + T_S \times B_R\) lenne

Hold onto your képlets, you'll need them later...

Vissza a feladathoz

\(Q(A,B)\Join R(B,C)\)


Output mérete	\(\orange{\dfrac{2\times T\times B}{I}}\)
Sorok Száma	\(\blue{\dfrac{T^2}{I}}\)
I/O költség	\(\green{B + \dfrac{T\times B}{I}}\)

Output beillesztve Az output tételünkbe:

\[ \dfrac{\blue{\frac{T^2}{I}}\times B + \orange{\frac{2T B}{I}}\times T}{I} ~=~3T^2\times \dfrac{B}{I^2} \]

Teljes Join I/O mérete


Az 1. Join költsége	\(B+T\times\frac{B}{I}\)
Az 1. Join kiírása	\(\dfrac{2TB}{I}\)
A 2. Join költsége	\(\dfrac{2TB}{I} + \dfrac{\left(\frac{2TB}{I}\times B\right)}{I}\)
A teljes output kiírása	\(\dfrac{2T^2B}{I^2}\)

(A) végeredmény

\[ B+\dfrac{5TB}{I}+\dfrac{4T^2B}{I^2} \]

Mindent összegezve

(B) végeredmény

\[ B+\dfrac{TB}{I}+\dfrac{4T^2B}{I^2} \]

Megspórolhattuk az 1. join kiírását majd beolvasását, ami \(2\left(\dfrac{2TB}{I}\right)\) lenne

(C) végeredmény

\[ B+\dfrac{2TB}{I}+\dfrac{3T^2B}{I^2} \]

Érdemes meggondolni, hogy B) és C) közötti különbség \(\dfrac{4T^2B}{I^2}-\dfrac{TB}{I}\)

Nagyságrendileg a \(\frac{T}{I}\) gányados fel fog robbanni, tehát C) a leghatékonyabb módszer

A végtelenben nézve B) és C) aránya \(\frac34\)