第15讲:(第14章) RDBMS的查询优化技术 重庆大学计算机学院,课程名称: 数据库系统 -,项目驱动目标：数据库系统如何实现对复杂的查询进行优化！ 一、查询优化概述 二 、基于等价表达式的优化 三 、选择执行计划 四 、嵌套查询与优化 五 、物化视图与优化 主要讨论问题：如何通过表达式转换实现优化 如何选择执行计划什么是基于代价的优化什么是启发式优化嵌套子查询如何优化 什么是物化视图能否用于优化,第14讲： RDBMS的查询优化技术,Exercise 15,一 查询优化概述,Alternative ways of evaluating a given queryEquivalent expressionsDifferent algorithms for each operation,Introduction -等价表示,1-1 查询操作可以优化？,一 查询优化概述,An evaluation plan defines exactly what algorithm is used for each operation, and how the execution of the operations is coordinated.协调/配合,Evaluation Plan,流水线-合并工作,1-2 什么是查询操作估算计划？,Cost difference between evaluation plans for a query can be enormousE.g. seconds vs. days in some casesSteps in cost-based query optimizationGenerate logically equivalent expressions using equivalence rulesAnnotate注释 resultant expressions to get alternative query plansChoose the cheapest plan based on estimated costEstimation of plan cost based on:Statistical information about relations. Examples:number of tuples, number of distinct values for an attributeStatistics estimation for intermediate resultsto compute cost of complex expressionsCost formulae for algorithms(如上次课学习的部分算法的代价估算公式), computed using statistics,查询优化步骤与考虑因素,一 查询优化概述,1-3 查询优化应考虑哪些因素？,二 基于等价表达式的优化,Two relational algebra expressions are said to be equivalent if the two expressions generate the same set of tuples on every legal database instanceNote: order of tuples is irrelevantIn SQL, inputs and outputs are multisets多重集/包 of tuplesTwo expressions in the multiset version of the relational algebra are said to be equivalent if the two expressions generate the same multiset of tuples on every legal database instance. An equivalence rule says that expressions of two forms are equivalentCan replace expression of first form by second, or vice versa,Transformation of Relational Expressions转换,2.1 等价表达式,问题1答案,1.Conjunctive selection operations can be deconstructed into a sequence of individual selections.2.Selection operations are commutative.Only the last in a sequence of projection operations is needed, the others can be omitted. (前提：属性组L1，L2，L3,逐一被后者包含) Selections can be combined with Cartesian products and theta joins.(E1 X E2) = E1 E2 1(E1 2 E2) = E1 1 2 E2,Equivalence Rules,5. Theta-join operations (and natural joins) are commutative.E1 E2 = E2 E1,返回,2.1 等价表达式,2-1 有哪些基本的等价规则？,6.(a) Natural join operations are associative: (E1 E2) E3 = E1 (E2 E3)(b) Theta joins are associative in the following manner: (E1 1 E2) 2 3 E3 = E1 1 3 (E2 2 E3) where 2 involves attributes from only E2 and E3.,7.The selection operation distributes over the theta join operation under the following two conditions:(a) When all the attributes in 0 involve only the attributes of one of the expressions (E1) being joined. 0E1 E2) = (0(E1) E2 (b) When 1 involves only the attributes of E1 and 2 involves only the attributes of E2. 1 E1 E2) = (1(E1) ( (E2),返回,2.1 等价表达式,Equivalence Rules-续1,8.The projection operation distributes over the theta join operation as follows:(a) Let L1 and L2 be sets of attributes from E1 and E2, respectively, and if involves only attributes from L1 L2:(b) Consider a join E1 E2. Let L1 and L2 be sets of attributes （部分属性集） from E1 and E2, respectively. Let L3 be attributes of E1 that are involved in join condition , but are not in L1 L2, and let L4 be attributes of E2 that are involved in join condition , but are not in L1 L2.,2.1 等价表达式,Equivalence Rules-续2,The set operations union and intersection are commutative E1 E2 = E2 E1 E1 E2 = E2 E1 (set difference is not commutative).Set union and intersection are associative. (E1 E2) E3 = E1 (E2 E3) (E1 E2) E3 = E1 (E2 E3)The selection operation distributes over , and . (E1 E2) = (E1) (E2) (and similarly for and in place of ).Also: (E1 E2) = (E1) E2 (and similarly for in place of , but not for ).12.The projection operation distributes over union L(E1 E2) = (L(E1) (L(E2),2.1 等价表达式,Equivalence Rules-续3,Pictorial Depiction of Equivalence Rules-图示,规则5,规则6（a）,规则7（a）,2.1 等价表达式,2-2 等价规则直观图示什么样？,2-3 选择操作下移有助于优化？,2.2 优化法-选择下移,Query1: Find the names of all customers who have an account at some branch located in Brooklyn.customer_name(branch_city = “Brooklyn”(branch (account depositor)下移选择：Transformation using rule 7a. customer_name (branch_city =“Brooklyn” (branch) (account depositor)优化原则：Performing the selection as early as possible reduces the size of the relation to be joined. 更多的例子(more),