数据库系统原理复习解读.ppt

第14章 Query Optimization 关系代数等价变换规则 基于代价最小的和启发式查询优化方法 做题（注意利用选择、投影简化查询） June 2010 Database System Concepts -Final Examination * Step1：使用rule1，将conjunctive（连接的） selection 分解为多个单独的选择操作，以使单个选择操作尽可能沿查询树下移（尽早执行选择操作，以减少中间计算结果） Step2：根据选择操作的交换率和分配率，利用rule2, rule7.a, rule7.b, rule11， 将查询树上的每个选择操作尽可能移向叶节点，以便尽早执行选择操作 Step3：根据连接操作的结合律和交换率，使用rule6，重新安排查询树中的叶结点，使得具有restrictive selection特征的叶结点先执行 restrictive selection：执行此操作后，产生的结果关系最小（所含元组最少） Steps in Heuristic Optimization Step4：利用rule4.a, 以连接操作代替相邻的选择和笛卡尔乘积操作 Step5：利用rule3, 8.a, 8.b,12, 将查询树上的投影操作尽可能下移，以便尽早执行投影操作，减少中间计算结果 Step6：将最后的查询树分解为多个子树，使子树中的各操作可以采用流水线方式执行（见第13章13.7.2中关于流水线的介绍)，以减少对外设的访问次数,e.g. Fig.14.5 （见书上） 流水线：通过减少查询执行中产生的临时文件数，我们可以提高查询执行的效率。减少临时文件数是通过将多个关系操作组合成一个操作的流水线来实现的。其中一个操作的结果将传送到流水线的下一个操作。这样的执行叫做流水线执行。(见书上13.7.2.1) Steps in Heuristic Optimization (cont.) Consider the following relations in banking enterprise database, where the primary keys are underlined branch (branch-name, branch-city, assets), loan ( loan-number, branch-name , amount) borrower( customer-name, loan-number, borrow-date) customer (customer-name, customer-street, customer-city) account (account-number, branch-name, balance) depositor (customer-name, account-number , deposit-date) Example Three For the query “ Find the names of all customers who have an loan at any branch that is located in Brooklyn and have assets more than $100,000, requiring that loan-amount is less than $1000” give an SQL statement for this query given a initial query tree for the query, and convert it into an optimized query tree by means of heuristic optimization Example Three (cont.) SQL select customer-name from borrower, loan, branch where loan.loan-number=borrower.loan-number and branch.branch-name=loan.branch-name and branch-city=”Brooklyn” and assets100000 and amount1000 Example Three (cont.) ? customer-name ?loan.loan-number ? customer- name, loan-number borrower ( custome