Kihagyás

Összkapcsolás

Megvalósítások

  • Skatulyázott ciklusos összekapcsolás
    • nested loop join
  • blokk-skatulyázott ciklusos összekapcsolás
    • block-nested loop join
  • Indexelt skatulyázott ciklusos összekapcsolás
    • index nested loop join
  • Összefésüléses rendező összekapcsolás
    • sort-merge join
  • Hasításos összekapcsolás
    • hash-join

Nested Loop

#struct RowR<'a>{
#    a: &'a str,
#    b: &'a str,
#    c: &'a str,
#}
#struct RowS<'a>{
#    c: &'a str,
#    d: &'a str,
#    e: &'a str,    
#}
#struct RowT<'a>{
#    a: &'a str,
#    b: &'a str,
#    c: &'a str,
#    d: &'a str,
#    e: &'a str,
#}
#impl <'a>PartialEq <RowS<'a>> for RowR<'a>{
#    fn eq(&self, other: &RowS) -> bool{
#        self.c == other.c
#    }
#}
#
#fn join<'a>(r:&RowR<'a>, s:&RowS<'a>) -> RowT<'a> {
#    RowT {a:r.a,b:r.b,c:r.c, d:s.d,e:s.e}
#}
#
#fn print(t:&RowT){
#    println!("|{:<5}|{:<5}|{:<5}|{:<5}|{:<5}|", t.a, t.b, t.c, t.d, t.e);
#}
#
#fn printR(r: &[RowR]){
#    println!("R:\n|{:<5}|{:<5}|{:<5}|", "A", "B", "C");
#    r.iter().for_each(|r|{
#        println!("|{:<5}|{:<5}|{:<5}|", r.a,r.b,r.c);
#    })
#}
#
#fn printS(s: &[RowS]){
#    println!("S:\n|{:<5}|{:<5}|{:<5}|", "C", "D", "E");
#    s.iter().for_each(|s|{
#        println!("|{:<5}|{:<5}|{:<5}|", s.c,s.d,s.e);
#    })
#}
#
#fn main(){
#    let rows_r = [
#        RowR{a:"r_a1",b:"r_b1", c:"x"},
#        RowR{a:"r_a2",b:"r_b2", c:"y"},
#        RowR{a:"r_a3",b:"r_b3", c:"z"},
#        RowR{a:"r_a4",b:"r_b4", c:"w"},
#    ];
#    let rows_s = [
#        RowS{d:"s_d1",e:"s_e1", c:"x"},
#        RowS{d:"s_d2",e:"s_e2", c:"x"},
#        RowS{d:"s_d3",e:"s_e3", c:"y"},
#        RowS{d:"s_d4",e:"s_e4", c:"w"},
#    ];
#    let R = rows_r.iter();
#    printR(&rows_r);
#    printS(&rows_s);
#    println!("T:\n|{:<5}|{:<5}|{:<5}|{:<5}|{:<5}|", "A", "B", "C", "D", "E");
#
    R.for_each(|t_r|{
#    let S = rows_s.iter();
        S.for_each(|t_s|{
            if t_r == t_s{
                print(&join(t_r,t_s));
            }
        })
    })
#}
  • Bármilyen összekapcsolási feltételnél működik
    • ha nics illesztési feltétel, akkor direkt szorzatot (\(\times\)) adja vissza
  • S belső reláció
  • R külső reláció

Tekintve, hogy ritkán fér el mindkét reláció a memóriába, ezt nem igazán látni magában

Block-Nested Loop

Költség - Block-nest

  • Legjobb, ha elfér a reláció a memóriában
  • legrosszabb eset, ha mindkét relációból csak 1-1 lap fér memo-ba 
#struct RowR<'a>{
#    a: &'a str,
#    b: &'a str,
#    c: &'a str,
#}
#struct RowS<'a>{
#    c: &'a str,
#    d: &'a str,
#    e: &'a str,    
#}
#struct RowT<'a>{
#    a: &'a str,
#    b: &'a str,
#    c: &'a str,
#    d: &'a str,
#    e: &'a str,
#}
#impl <'a>PartialEq <RowS<'a>> for RowR<'a>{
#    fn eq(&self, other: &RowS) -> bool{
#        self.c == other.c
#    }
#}
#
#fn join<'a>(r:&RowR<'a>, s:&RowS<'a>) -> RowT<'a> {
#    RowT {a:r.a,b:r.b,c:r.c, d:s.d,e:s.e}
#}
#
#fn print(t:&RowT){
#    println!("|{:<5}|{:<5}|{:<5}|{:<5}|{:<5}|", t.a, t.b, t.c, t.d, t.e);
#}
#
#fn printR(r: &[RowR]){
#    println!("R:\n|{:<5}|{:<5}|{:<5}|", "A", "B", "C");
#    r.iter().for_each(|r|{
#        println!("|{:<5}|{:<5}|{:<5}|", r.a,r.b,r.c);
#    })
#}
#
#fn printS(s: &[RowS]){
#    println!("S:\n|{:<5}|{:<5}|{:<5}|", "C", "D", "E");
#    s.iter().for_each(|s|{
#        println!("|{:<5}|{:<5}|{:<5}|", s.c,s.d,s.e);
#    })
#}
#
#fn main(){
#    let rows_r = [[
#        RowR{a:"r_a1",b:"r_b1", c:"x"},
#        RowR{a:"r_a2",b:"r_b2", c:"y"},
#        RowR{a:"r_a3",b:"r_b3", c:"z"},
#        RowR{a:"r_a4",b:"r_b4", c:"w"},
#    ]];
#    let rows_s = [[
#        RowS{d:"s_d1",e:"s_e1", c:"x"},
#        RowS{d:"s_d2",e:"s_e2", c:"x"},
#        RowS{d:"s_d3",e:"s_e3", c:"y"},
#        RowS{d:"s_d4",e:"s_e4", c:"w"},
#    ]];
#    let R = rows_r.iter();
#    printR(&rows_r[0]);
#    printS(&rows_s[0]);
#    println!("T:\n|{:<5}|{:<5}|{:<5}|{:<5}|{:<5}|", "A", "B", "C", "D", "E");
#
    R.for_each(|pages_in_R| {
#       let S = rows_s.iter();
        S.for_each(|pages_in_S| {
#           let pageR = pages_in_R.iter();
            pageR.for_each(|t_r|{
#               let pageS = pages_in_S.iter();
                pageS.for_each(|t_s|{
                    if t_r == t_s{
                        print(&join(t_r,t_s));
                    }
                })
            })
        })
    })
#}

Index Nested Loop

  • Index a belső reláción (S)
  • A külső reláció (R) minden rekordjánál keressük a belső index alapján illeszkedő rekordokat S-ből

Költség - Index nest

  • \(B_R\) \(+\) \(N_R\) \(\times\) c
    • c a belső index kiválasztási költsége
    • c = keresési költség + találat mérete
      • Klaszterindexnél \(c=\href{./05_1_CostMath.md#hti}{HT_i}+{\huge \lceil}\dfrac{\href{./05_1_CostMath.md#scar}{SC(A,R)}}{\href{./05_1_CostMath.md#fr}{F_S}}{\huge\rceil} = \log(\text{index méret})+{\huge \lceil}\dfrac{\href{./05_1_CostMath.md#nr}{N_S}}{\href{./05_1_CostMath.md#var}{V(A,S)}\times\href{./05_1_CostMath.md#fr}{F_S}}{\huge\rceil} = \log(\text{index méret})+{\huge \lceil}\dfrac{\href{./05_1_CostMath.md#br}{B_S}}{\href{./05_1_CostMath.md#var}{V(A,S)}}{\huge\rceil} \approx {\huge \lceil}\dfrac{\href{./05_1_CostMath.md#br}{B_S}}{\href{./05_1_CostMath.md#var}{V(A,S)}}{\huge\rceil}\)
    • Mert a logaritmus tag lassabb...
  • \(\dfrac{\href{./05_1_CostMath.md#br}{B_R}+\href{./05_1_CostMath.md#nr}{N_R}\times\href{./05_1_CostMath.md#br}{B_S}}{\href{./05_1_CostMath.md#var}{V(A,S)}}\)
  • Kevesebb rekordot a külső tartalmazzon (ha lehet, kthxbye)

Sort Merge

  • A relációk rendezettek az öszekapcsolás mezői szerint
  • Összefésüljük a rendezett relációkat
    • mutatók mindkét relációba
    • beolvasunk S-ből egy rekordcsoportot, ahol a kapcsolás attribútuma illeszkedik
    • beolvassuk a rekordokat R-ből, és faldolgozzuk
  • Rendezettség miatt csak egyszer kell végigolvasni
  • rendezés költsége \(+\) \(B_R\) + \(B_S\)

Hash

  • R és S-ben ugyanazt a h() hash függvényt használjuk a kapcsolási mezőkön
  • felosztjuk a rekordokat a memóriában elférő részekre (lapok)
    • Fontos, hogy mind \(R_i\) és \(S_i\) férjen el a memóriában egyszerre
  • At illeszkedő partíciók rekordjait összekapcsoljuk
    • hiszen ha nem illeszkedne, arra h() mást kell(!) adjon
    • Az így kapott indexelt lapokat(partíciókat) skatulyázott ciklussal össze tudjuk majd kapcsolni
  • \(2\)(\(B_R\) + \(B_S\)) \(+\) (\(B_R\) + \(B_S\))

Méretbecslés