Data-intensive Computing Systems Query Optimization (Costbased optimization) Shivnath Babu Query Optimization Problem Pick the best plan from the space of physical plans Cost-Based Optimization Prune the space of plans using heuristics Estimate cost for remaining plans Be smart about how you iterate through plans Pick the plan with least cost Focus on queries with joins Heuristics for pruning plan space Predicates as early as possible Avoid plans with cross products Only left-deep join trees Physical Plan Selection Logical Query Plan P1 P2 …. Pn Physical plans C1 C2 …. Cn Costs Pick minimum cost one Review of Notation T (R) : Number of tuples in R B (R) : Number of blocks in R Simple Cost Model Cost (R S) = T(R) + T(S) All other operators have 0 cost Note: The simple cost model used for illustration only Cost Model Example X T(X) + T(T) T T(R) + T(S) R S Total Cost: T(R) + T(S) + T(T) + T(X) Selinger Algorithm Dynamic Programming based Dynamic Programming: General algorithmic paradigm Exploits “principle of optimality” Useful reading: Chapter 16, Introduction to Algorithms, Cormen, Leiserson, Rivest Principle of Optimality Optimal for “whole” made up from optimal for “parts” Principle of Optimality Query: R1 R2 R3 R4 R5 Optimal Plan: R5 R1 R4 R3 R2 Principle of Optimality Query: R1 R2 R3 R4 R5 Optimal Plan: R5 R1 R4 R3 R2 Optimal plan for joining R3, R2, R4, R1 Principle of Optimality Query: R1 R2 R3 R4 R5 Optimal Plan: R5 R1 R4 R3 R2 Optimal plan for joining R3, R2, R4 Exploiting Principle of Optimality Query: R1 R2 … Rn R1 R2 R3 Optimal for joining R1, R2, R3 R2 R3 R1 Sub-Optimal for joining R1, R2, R3 Exploiting Principle of Optimality Ri Rj R2 R3 Sub-Optimal for joining R1,…,Rn R1 A sub-optimal sub-plan cannot lead to an optimal plan Selinger Algorithm: Query: R1 R2 R3 Progress of algorithm { R1, R2, R3, R4 } { R1, R2, R3 } { R1, R2, R4 } {