Transformation Example:Pushing Projections IIcustomer_name((pranch_city=Brooklyn(branch)account)depositor) When we compute (branch_city="Brooklyn"(branch)account we obtain a relation whose schema is: (branch_name,branch_city,assets,account_number,balance) Push projections using equivalence rules 8a and 8b;eliminate unneeded attributes from intermediate results to get: Πcustomer name( IlaccounLnumber((branch_city="Brookty(branch)account Xdepositor) Performing the projection as early as possible reduces the size of the relation to be joined. Database System Concepts-5th Edition,Oct 5,2006. 14.17 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 14.17 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006. Transformation Example: Pushing Projections When we compute (branch_city = “Brooklyn” (branch) account ) we obtain a relation whose schema is: (branch_name, branch_city, assets, account_number, balance) Push projections using equivalence rules 8a and 8b; eliminate unneeded attributes from intermediate results to get: customer_name (( account_number ( (branch_city = “Brooklyn” (branch) account )) depositor ) Performing the projection as early as possible reduces the size of the relation to be joined. customer_name((branch_city = “Brooklyn” (branch) account) depositor)
Join Ordering Example For all relations r.r2.and ra, (1r2)凶r3=r1W(r2☒r3) (Join Associativity） If r2ra is quite large and nr2 is small,we choose (r12)r3 so that we compute and store a smaller temporary relation. Database System Concepts-5th Edition,Oct 5,2006. 14.18 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 14.18 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006. Join Ordering Example For all relations r1, r2, and r3 , (r1 r2 ) r3 = r1 (r2 r3 ) (Join Associativity) If r2 r3 is quite large and r1 r2 is small, we choose (r1 r2 ) r3 so that we compute and store a smaller temporary relation
Join Ordering Example (Cont.) Consider the expression TΠcustomer_name(（pranch_.ciy="Brooklyn(branch》) (account凶depositor) Could compute account depositor first,and join result with branch_city="Brooklyn(branch) but a account depositor is likely to be a large relation. Only a small fraction of the bank's customers are likely to have accounts in branches located in Brooklyn it is better to compute branch_city="Brooklyn(branch)Xaccount first. Database System Concepts-5th Edition,Oct 5,2006. 14.19 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 14.19 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006. Join Ordering Example (Cont.) Consider the expression customer_name ((branch_city = “Brooklyn” (branch)) (account depositor)) Could compute account depositor first, and join result with branch_city = “Brooklyn” (branch) but account depositor is likely to be a large relation. Only a small fraction of the bank’s customers are likely to have accounts in branches located in Brooklyn it is better to compute branch_city = “Brooklyn” (branch) account first
Enumeration of Equivalent Expressions Query optimizers use equivalence rules to systematically generate expressions equivalent to the given expression Can generate all equivalent expressions as follows: Repeat apply all applicable equivalence rules on every equivalent expression found so far add newly generated expressions to the set of equivalent expressions Until no new equivalent expressions are generated above The above approach is very expensive in space and time Two approaches Optimized plan generation based on transformation rules Special case approach for queries with only selections,projections and joins Database System Concepts-5th Edition,Oct 5,2006. 14.20 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 14.20 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006. Enumeration of Equivalent Expressions Query optimizers use equivalence rules to systematically generate expressions equivalent to the given expression Can generate all equivalent expressions as follows: Repeat apply all applicable equivalence rules on every equivalent expression found so far add newly generated expressions to the set of equivalent expressions Until no new equivalent expressions are generated above The above approach is very expensive in space and time Two approaches Optimized plan generation based on transformation rules Special case approach for queries with only selections, projections and joins
Implementing Transformation Based Optimization Space requirements reduced by sharing common sub-expressions: when E1 is generated from E2 by an equivalence rule,usually only the top level of the two are different,subtrees below are the same and can be shared using pointers E.g.when applying join commutativity E1 E2 Same sub-expression may get generated multiple times Detect duplicate sub-expressions and share one copy Time requirements are reduced by not generating all expressions Dynamic programming We will study only the special case of dynamic programming for join order optimization Database System Concepts-5thEdition,Oct 5,2006. 14.21 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 14.21 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006. Implementing Transformation Based Optimization Space requirements reduced by sharing common sub-expressions: when E1 is generated from E2 by an equivalence rule, usually only the top level of the two are different, subtrees below are the same and can be shared using pointers E.g. when applying join commutativity Same sub-expression may get generated multiple times Detect duplicate sub-expressions and share one copy Time requirements are reduced by not generating all expressions Dynamic programming We will study only the special case of dynamic programming for join order optimization E1 E2