Selinger(Op+mizer( 6.814/6.830(Lecture(10(October(07,(2010((Slides(gently(offered(by(Sam(Madden) The(Problem • How(to(order(a(series(of(N(joins,(e.g.,((A.a(=(B.b(AND(A.c(=(D.d(AND(B.e(=(C.f(N!(ways(to(order(joins((e.g.,(ABCD,(ACBD,(….)((NV1)!(plans(per(ordering((e.g.,((((AB)C)D),(((AB)(CD),(…)(Mul+ple(implementa+ons((e.g.,(hash,(nested(loops,(etc)(• Naïve(approach(doesn’t(scale,(e.g.,(for(20Vway(join(– 10!(x(9!(=(1.3(x(10(^(12(– 20!(x(19!(=(2.9(x(10(^(35(Selinger(Op+miza+ons • Le^Vdeep(only((((AB)C)D)((eliminate((NV1)!)(• PushVdown(selec+o n s(• Don’t(consider(cross(products(• Dynamic(programming(algorithm(Dynamic(Programming R((set(of(rela+ons(to(join((e.g.,(ABCD)(For(∂(in({1...|R|}:(for(S(in({all(length(∂(subsets(of(R}:(( optjoin(S)(=(a(join((SVa),((((where(a(is(the(single(rela+on(that(minimizes:(( ( ( cost(optjoin(SVa))(+((( ( ( min.(cost(to(join((SVa)(to(a(+((( ( ( min.(access(cost(for(a%optjoin(SVa)(is(cached(from(previous(itera+on Example optjoin(ABCD)((–(assume(all(joins(are(NL(∂=1(A(=(best(way(to(access(A((((( (e.g.,(sequen+al(scan,(or(predicate(pushdown(into(index...)(B(=(best(way(to(access(B(C(=(best(way(to(access(C((D(=(best(way(to(access(D( Total(cost(computa+ons:(choose(N,1),(where(N(is(number(of(rela+ons(Subplan Best/choice Cost A index 100 B seq(scan 50 … Cache Subplan Best/choice Cost A index 100 B seq(scan 50 … Cache Example optjoin(ABCD)(∂=2({A,B}(=(AB(or(BA((( (using(previously(computed(best(way(to(access(A(and(B)({B,C}(=(BC(or(CB({C,D}(=(CD(or(DC({A,C}(=(AC(or(CA({A,D}(=(AD(or(DA({B,D}(=(BD(or(DB Total(cost(computa+ons:(choose(N,2)(x(2(Subplan Best/choice Cost A index 100 B seq(scan 50 {A,B} BA 156({B,C} BC 98(… Example optjoin(ABCD)(∂=3({A,B,C}(=(remove(A,(compare(A({B,C})(to(({B,C})A(remove(B,(compare(B({A,C})(to(({A,C})B(remove(C,(compare(C({A,B})(to(({A,B})C({A,B,D}(=(remove(A,(compare(A({B,D})(to(({B,D})A(((( ((….({A,C,D}(=(…({B,C,D}(=(…(Already(computed(–(lookup(in(cache Total(cost(computa+ons:(choose(N,3)(x(3(x(2(Cache Subplan Best/choice Cost A index 100 B seq(scan 50 {A,B} BA 156({B,C} BC 98(… Subplan Best/choice Cost A index 100 B seq(scan 50 {A,B} BA 156({B,C} BC 98({A,B,C} BCA 125(… {B,C,D} BCD 115(Subplan Best/choice Cost A index 100 B seq(scan 50 {A,B} BA 156({B,C} BC 98({A,B,C} BCA 125(… {B,C,D} BCD 115(Example optjoin(ABCD)(∂=4({A,B,C,D}(=(remove(A,(compare(A({B,C,D})(to(({B,C,D})A(remove(B,(compare(B({A,C,D})(to(({A,C,D})B(remove(C,(compare(C({A,B,D})(to(({A,B,D})C(remove(D,(compare(D({A,B,C})(to(({A,B,C})D(Total(cost(computa+ons:(choose(N,4)(x(4(x(2(Already(computed(–(lookup(in(cache Cache Final/answer/is/plan/with/minimum/cost/of/these/four/Subplan Best/choice Cost A index 100 B seq(scan 50 {A,B} BA 156({B,C} BC 98({A,B,C} BCA 125({B,C,D} BCD 115({A,B,C,D} ABCD 215(Complexity choose(n,1)(+(choose(n,2)(+(…(+(choose(n,n)(total(subsets(considered(All(subsets(of(a(size(n(set(=(power(set(of(n(=(2^n(Equiv.(to(compu+ng(all(binary(strings(of(size(n((000,001,010,100,011,101,110,111(Each(bit(represents(whether(an(item(is(in(or(out(o f(set(Complexity((con+nued) For(each(subset,(k(ways(to(remove(1(join(k(<(n(m(ways(to(join(1(rela+on(with(remainder(Total(cost:((O(nm2^n)(plan(evalua+ons(n(=(20,(m(=(2(4.1(x(10^7(Interes+ng(Orders • Some(queries(need(data(in(sorted(order(– Some(plans(produce(sorted(data((e.g.,(using(an(index(scan(or(merge(join(• May(be(nonVop+mal(way(to(join(data,(but(overall(op+mal(plan(– Avoids(final(sort(• In(cache,(maintain(best(overall(plan,(plus(best(plan(fo r(each(interes+ng(order(• At(end,(compare(cost(of(( best(plan(+(sort(into(order(((to(( best(in(order(plan(• Increases(complexity(by(factor(of(k+1,(where(k(is(number(of(interes+ng(orders(Example SELEC T (A.f3,(B.f2(FROM(A,B(where(A .f3(=(B.f4((ORDER(BY(A.f3(Subplan Best/choice Cost Best/in/A.f3/order Cost/ A index 100 index 100 B seq(scan 50 seqscan 50 {A,B} BA(hash 156( AB(merge( 180(compare:((( cost(sort(output))(+(156(to((180( MIT OpenCourseWarehttp://ocw.mit.edu 6.830 / 6.814 Database SystemsFall 2010 For information about citing these materials or our Terms of Use, visit: