第6章 查询优化

null第6章 查询优化第6章 查询优化本章内容参考 数据库概念(第四版) by A. Silberschatz Chapter 14 Optimization 简介+自学 本章要解决的关键问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 如何找到具有最低求值代价的求值计划 主要内容主要内容概述 用于代价估算的统计信息 关系代数表达式的转换 基于代价的优化算法 物化视图与视图维护 概述概述一个给定查询有多种可选择的求值方法 等价表达式 一个操作有若干不同算法(Chapter 5) 一个查询求值方法的好坏带来的代价差别可能是巨大的 例如: 执行r X s 后续选择r.A = s.B 比执行一个同样条件的连接慢得多 需要估算操作的代价 依赖于数据库维护的统计信息 例如元组数, 连接属性的不同值的数目, 等等 需要对中间结果估算统计信息以便对复杂表达式计算代价概述概述概述概述对一个表达式的查询求值 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 的生成涉及几个步骤: 生成逻辑上等价的表达式 利用等价规则将一个表达式转换成另一个等价的表达式 注解(Annotate)结果表达式以得到其他查询计划 基于估算代价选择最廉价的计划 整个过程称为基于代价的优化用于代价估算的统计信息(回顾)用于代价估算的统计信息(回顾)nr : 关系r 中的元组个数 br : 包含r 中元组的块数 sr : r 中元组的大小 fr : r 的块因子 — 即, 能放入一块之中的r 的元组数 V(A, r): r 中出现的A属性上的不同值的个数; 等于A(r)的大小 SC(A, r): 关系r 中属性A的选择基数, 满足A上等值条件的平均记录数 若r 中元组在文件中连续存放, 则: 关于索引的目录信息(回顾)关于索引的目录信息(回顾)fi : 索引i 的内节点的平均扇出, 适用于树结构索引,如B+树 HTi :索引i 的层数 — 即高度 对于关系r上A 属性的平衡树索引 (如B+-树) HTi = logfi(V(A,r)) 对于散列索引, HTi 为1 LBi :索引i 的底层索引块数 — 即索引叶子层的块数查询代价的度量(回顾)查询代价的度量(回顾)典型地, 磁盘存取是决定性的代价, 也相对容易估算 来自磁盘的块传送次数被用作求值的实际代价的度量 假设所有块传送都具有相同代价 实际的优化器不作此假设, 并区分顺序与随机磁盘存取 不包括写输出到磁盘的代价 记算法A的代价估算为EA统计信息: 例统计信息: 例faccount= 20 (一块可放入account 的20个元组) V(branch-name, account) = 50 (50个分行) V(balance, account) = 500 (500 个不同的balance 值) account = 10,000 (account 有10,000条元组) 假设account 上存在下列索引: 属性branch-name上的主B+-树索引 属性balance上的辅助B+-树索引选择的大小估算选择的大小估算等值选择 A=v(r) SC(A, r) : 满足选择的记录数 SC(A, r)/fr : 这些记录将占用的块数 二分搜索的代价估算为 键属性上的等值条件: SC(A,r) = 1选择的大小估算选择的大小估算涉及比较的选择 形如AV (r )的选择 令c 表示满足条件的估算元组数 若 min(A,r) 和 max(A,r) 在目录中可得 c = 0 if v < min(A,r) c = 若没有统计信息, c 可假设为 nr / 2 A  V(r) 的情形是对称的复杂选择的实现复杂选择的实现条件I 的选择度是关系r 中一条元组满足I 的概率,如果si 是r 中满足的元组数, 则i 的选择度为si /nr 合取: 1 2. . .  n (r). 结果中元组数的估算值为: 析取: 1 2 . . .  n (r).结果中元组数的估算值为: 否定: (r). 元组数的估算值为: nr – size((r))连接的大小的估算连接的大小的估算卡氏积 r x s 包含 nr .ns 元组, 每个元组占用sr + ss 字节 若 R  S = , 则 r s 等同于 r x s 若 R  S 是R 的键, 则s 的一条元组将与r 的最多一条元组连接 因此, r s 中的元组数不大于s 中的元组数 若 R  S 在S 中是引用R 的外键, 则r s中的元组数正好等于s中的元组数 R  S 是引用S 的外键的情形是对称的 在查询例depositor customer 中, depositor 中的customer-name 是customer 的外键 因此, 结果具有 ndepositor 条元组, 即 5000连接操作: 例子连接操作: 例子连续用例: depositor customer 连接例的目录信息: ncustomer = 10,000 fcustomer = 25, 这意味着 bcustomer =10000/25 = 400 ndepositor = 5000 fdepositor = 50, 这意味着 bdepositor = 5000/50 = 100 V(customer-name, depositor) = 2500, 这意味着每个顾客平均有2个depositor 还假设depositor 中的customer-name是customer 上的外键连接的大小的估算连接的大小的估算若 R  S = {A} 不是R 或S的键 如果我们假设R 中每个元组t 都在R S中产成元组, 则R S中的元组数估算为: 若正好相反, 估算值为: 这两个估算值的较小者可能更准确连接的大小的估算连接的大小的估算例:不利用有关外键的信息计算 depositor customer 的大小估算: V(customer-name, depositor) = 2500, 且 V(customer-name, customer) = 10000 两个估算为 5000 * 10000/2500 = 20,000 及 5000 * 10000/10000 = 5000 我们选择其中的较小估算, 在本情形下等于我们以前利用外键的计算结果其他操作的大小估算其他操作的大小估算投影: 估算大小 A(r) = V(A,r) 聚合: 估算大小AgF(r) = V(A,r) 集合运算 对于同一关系上选择的并/交: 重写并利用选择的大小估算 例如 1 (r)  2 (r) 可重写为1v2 (r) 对于在不同关系上的操作: r  s 的估算大小 = r 的大小 + s 的大小 r  s 的估算大小 = r 的大小与s 的大小之最小者 r – s 的估算大小 = r 上面这三种估算都可能不精确, 但提供了大小的上界其他操作的大小估算其他操作的大小估算外连接: r s 的估算大小= r s 的大小+ r 的大小 右外连接的情形是对称的 r s的估算大小 = r s 的大小+ r 的大小+ s 的大小 不同值个数的估算不同值个数的估算选择:  (r) 若 强制A 取一个特定值(e.g., A = 3) : V(A, (r)) = 1 若 强制A 取一个特定集合中的某个值(e.g., (A = 1 V A = 3 V A = 4 )): V(A, (r)) = 指定值的个数 若选择条件 形如 A op v,其中op 为比较运算符(e.g.,A<=5): 估算V(A, (r)) = V(A,r) * s 其中 s 是本选择的选择度 其他情况: 利用近似估算 min(V(A,r), n (r) ) 更准确的估算可利用概率论得到, 但是本估算一般就很管用不同值个数的估算不同值个数的估算连接: r s 若A中所有属性都来自r 估算V(A, r s) = min (V(A,r), n r s) 若A包含来自r 的属性A1和来自s 的属性A2, 则估算V(A,r s) = min(V(A1,r)*V(A2 – A1,s), V(A1 – A2,r)*V(A2,s), nr s) 利用概率论可以得到更精确的估算, 但这已经很好了 不同值个数的估算不同值个数的估算投影的不同值个数的估算是直接的 在A (r) 中与在r 中是相同的 对聚合的分组属性也是一样 对于聚合值 对min(A) 和max(A),不同值个数可估算为min(V(A,r), V(G,r)), 其中G表示分组属性 对其他聚合函数, 假设所有值都不同, 并利用V(G,r)关系代数表达式的转换关系代数表达式的转换如果在每个合法的数据库实例上, 两个关系代数表达式都生成同样的元组集合, 则这两个关系代数表达式称为等价的 注意: 元组次序是无关的 在SQL中, 输入和输出都是元组的多重集合 如果在每个合法的数据库实例上, 两个关系代数表达式都生成同样的元组多重集合, 则这两个表达式在关系代数的多重集合版本下称为等价的 等价规则说明了两种形式的表达式是等价的，即可以用一个表达式替换另一个等价规则等价规则1. 合取选择操作可以分解称个体选择的序列: 2. 选择操作是可交换的: 3. 一个投影操作序列中只有最后一个是必要的, 其余皆可省略: 选择可与笛卡儿积及 连接结合: (E1 X E2) = E1  E2 1(E1 2 E2) = E1 1 2 E2 等价规则等价规则5.  连接操作 (及自然连接) 可交换: E1  E2 = E2  E1 6. (a) 自然连接操作是可结合的: (E1 E2) E3 = E1 (E2 E3) (b)  连接按如下方式是可结合的: (E1 1 E2) 2  3 E3 = E1 2 3 (E2 2 E3) 其中2 仅涉及来自E2 和E3的属性等价规则 等价规则 7. 在下面两个条件下, 选择操作对 连接操作有分配律: (a) 当0中的所有属性仅涉及被连接表达式之一(E1)的属性时: 0E1  E2) = (0(E1))  E2 (b) 当1 仅涉及E1的属性且2仅涉及E2的属性时: 1 E1  E2) = (1(E1))  ( (E2))等价规则等价规则8. 投影操作对 连接操作的分配律如下: (a) 若 仅涉及来自L1  L2的属性: (b) 考虑连接 E1  E2 若 L1 和 L2 分别是来自E1和E2的属性集合 令 L3 是连接条件中涉及的E1的属性, 但不在L1  L2中, 并且 令 L4是连接条件中涉及的E2的属性,但不在L1  L2中等价规则等价规则集合运算并和交都是可交换的: E1  E2 = E2  E1 E1  E2 = E2  E1 集合差不是可交换的 集合并和交都是可结合的: (E1  E2)  E3 = E1  (E2  E3) (E1  E2)  E3 = E1  (E2  E3) 选择操作对,  和–可分配:  (E1 – E2) =  (E1) – (E2) 类似地可用和 替换– 同样:  (E1 – E2) = (E1) – E2 类似地可用 替换 – , 但不能用  12. 投影操作对并可分配: L(E1  E2) = (L(E1))  (L(E2)) 等价规则的图示等价规则的图示转换例转换例查询: 找出所有在位于Brooklyn的某分行具有帐户的客户的姓名 customer-name(branch-city = “Brooklyn” (branch (account depositor))) 利用规则7a转换. customer-name ((branch-city =“Brooklyn” (branch)) (account depositor)) 尽可能早地执行选择可以减少待连接关系的大小 多步转换例多步转换例查询: 找出所有在位于Brooklyn的某分行具有帐户且帐户余额超过$1000的客户的姓名: customer-name((branch-city = “Brooklyn”  balance > 1000 (branch (account depositor))) 利用连接结合性 (Rule 6a)的转换: customer-name((branch-city = “Brooklyn”  balance > 1000 (branch (account)) depositor) 第二种形式提供了应用“尽早执行选择”规则的机会, 导致子表达式 branch-city = “Brooklyn” (branch)  balance > 1000 (account) 因此一系列的转换是有用的多步转换多步转换投影操作:例投影操作:例当计算 (branch-city = “Brooklyn” (branch) account ) 时得到一个关系, 其模式为: (branch-name, branch-city, assets, account-number, balance) 利用等价规则8a和8b下推投影; 从中间结果删除不必要的属性可得:  customer-name ((  account-number ( (branch-city = “Brooklyn” (branch) account )) depositor)customer-name((branch-city = “Brooklyn” (branch) account) depositor) 连接次序:例连接次序:例对所有关系 r1, r2, 及r3 (r1 r2) r3 = r1 (r2 r3 ) 若r2 r3 很大且r1 r2 较小, 选择 (r1 r2) r3 从而计算并存储一个较小的临时关系 结合律的使用原则: 先做连接结果较小的 如果先作的这部分小到只有一行或几行， 总运算量小 问题：要机器自动作优化，比较难连接次序：例 连接次序：例 考虑表达式 customer-name ((branch-city = “Brooklyn” (branch)) account depositor) 可以先计算account depositor, 再将结果与 branch-city = “Brooklyn” (branch) 连接 但account depositor 可能是个大关系 由于更可能仅仅少部分银行客户在位于的分行开帐户, 因此更好的做法是先计算: branch-city = “Brooklyn” (branch) account连接次序：例连接次序：例等价表达式的枚举等价表达式的枚举查询优化器利用等价规则来系统地生成等价于给定表达式的表达式 从概念上说, 通过重复执行下列步骤直至找不到更多表达式来生成所有等价表达式 对每个当前找到的表达式, 利用所有可用的等价规则, 并增加新生成的表达式到当前找到的表达式集合中 上述方法的时间空间代价都很大等价表达式的枚举等价表达式的枚举通过共享公共子表达式可减少空间需求: 当利用一等价规则可从E2生成E1, 通常两者仅有顶层不同, 下面的子树是相同的, 故可以共享 例如, 当应用连接结合律时 通过不生成所有表达式可减少时间需求求值计划求值计划求值计划确切定义了对每个操作采用什么算法, 以及各操作的执行是如何协调的求值计划的选择求值计划的选择选择求值计划时必须考虑求值算法的相互影响 原因：独立地为每个操作都选择最廉价算法未必总体最佳 例如 归并连接可能比散列连接代价高, 但是可以提供有序输出, 从而减少外层聚合操作的代价 嵌套循环连接可能提供流水线化的机会 实际的查询优化器结合了下列两大类方法的要素: 1. 搜索所有计划并以基于代价的方式选择最佳计划 2. 利用启发式规则选择计划基于代价的优化基于代价的优化考虑为r1 r2 . . . rn找到最佳连接次序 组合爆炸:上面的表达式共有(2(n – 1))!/(n – 1)! 种不同的连接次序, 当n = 7, 即有665280, 当n = 10, 结果大于1760亿! 没有必要生成所有连接次序 利用动态规划, {r1, r2, . . . rn}的任何子集的最小代价连接次序只计算一次并保存为将来所用 优化中的动态规划优化中的动态规划要找到 n个关系的最佳连接树: 为找到n个关系的集合S 进行连接的最佳方案, 考虑所有可能的形如S1 (S – S1)的方案, 其中S1 是S 的任意非空子集 递归计算连接S 的所有子集的代价, 以找出每个方案的代价, 然后选择2n – 1 种可能方案中代价最小者 当计算出任意子集的方案, 保存该方案,并在需要的时候重用之, 而不是重新计算 动态规划连接次序优化算法连接次序优化算法左深连接树左深连接树左深连接树中, 每个连接的右手边输入是个关系, 而不是中间连接的结果优化的代价优化的代价为找到n个关系的集合的最佳左深连接树: Consider n alternatives with one relation as right-hand side input and the other n-1 relations as left-hand side input Using (recursively computed and stored) least-cost join order for each alternative on left-hand-side, choose the cheapest of the n alternatives 利用动态规划, 优化的时间复杂度为O(3n) 当n = 10, 此数为59000而不是1760亿! 空间复杂度为: O(2n) 基于代价优化中有收益的排序次序基于代价优化中有收益的排序次序考虑表达式 (r1 r2 r3) r4 r5 有收益的排序次序是指元组的一个特定排序次序, 对以后的操作可能有用 生成 r1 r2 r3 结果时再与r4 或r5的公共属性上排序, 也许有用, 但在仅与r1和r2公共的属性上排序就没用 利用归并连接计算 r1 r2 r3 可能代价更高, 但可能提供按一个有收益的次序排序的输出 对n个给定关系集合的每个子集找出最佳连接次序是不够的,必须对每个子集的每个有收益排序次序找出最佳连接次序 前面的动态规划算法做简单扩展 通常,有收益次序的数目很小且不显著影响时间/空间复杂度启发式优化启发式优化即使用了动态规划, 基于代价的优化还是很昂贵，系统可以使用启发式来减少在基于代价方式中必须考虑的可选方案的数目 启发式优化利用一套规则来转换查询树, 这些规则通常(但不是所有情况)都能改善执行性能 启发性规则：来自经验，不保证成功，还可能不相容 如：“三思而后行” VS “当断不断，反受其乱” 启发性规则启发性规则尽早执行选择 (减少元组数目) 尽早执行投影 (减少属性数目) 在其他类似操作之前执行最具限制性的选择和连接操作 某些系统只使用启发式, 其他的结合了启发式与部分基于代价的优化典型的启发式优化步骤典型的启发式优化步骤1. 分解合取选择成为一个单选择操作序列(Equiv. rule 1.) 2. 将选择操作移到查询树下方以便尽早执行(Equiv. rules 2, 7a, 7b, 11) 3. 首先执行能产生最小关系的选择和连接操作 (Equiv. rule 6) 4. 笛卡儿积操作后接选择条件用连接操作替换 (Equiv. rule 4a) 5. 将投影属性列表分解并尽可能移到查询树下方, 必要时创建新投影(Equiv. rules 3, 8a, 8b, 12) 6. 确认其操作可以流水线化的子树, 并利用流水线执行之查询优化器的结构查询优化器的结构System R/Starburst 优化器只考虑左深连接次序, 这减少了优化复杂性并生成适应流水线求值的方案 System R/Starburst 还利用启发式来在查询树中下推选择和投影 Oracle的某些版本中使用了启发式优化: 反复选出下一步“最佳”连接的关系 从 n 个开始点的每一个开始,从中挑选最佳 对于使用辅助索引的扫描, 某些优化器考虑了包含元组的页在缓冲区中的概率 SQL的复杂查询导致了查询优化的复杂 如嵌套子查询查询优化器的结构查询优化器的结构某些查询优化器集成了启发式选择和替换存取方案的生成 System R 和Starburst 基于SQL嵌套块概念使用了层次式过程 启发式重写后接基于代价的连接次序优化 即使使用了启发式, 基于代价的查询优化仍然带来大量开销 这个开销通常被查询执行时的节省更多地补偿, 尤其是较慢的磁盘存取数目的减少Optimizing Nested Subqueries(略)Optimizing Nested Subqueries(略)SQL conceptually treats nested subqueries in the where clause as functions that take parameters and return a single value or set of values Parameters are variables from outer level query that are used in the nested subquery; such variables are called correlation variables E.g. select customer-name from borrower where exists (select * from depositor where depositor.customer-name = borrower.customer-name)Optimizing Nested SubqueriesOptimizing Nested SubqueriesConceptually, nested subquery is executed once for each tuple in the cross-product generated by the outer level from clause Such evaluation is called correlated evaluation Note: other conditions in where clause may be used to compute a join (instead of a cross-product) before executing the nested subqueryOptimizing Nested SubqueriesOptimizing Nested SubqueriesCorrelated evaluation may be quite inefficient since a large number of calls may be made to the nested query there may be unnecessary random I/O as a result SQL optimizers attempt to transform nested subqueries to joins where possible, enabling use of efficient join techniquesOptimizing Nested SubqueriesOptimizing Nested SubqueriesE.g.: earlier nested query can be rewritten as select customer-name from borrower, depositor where depositor.customer-name = borrower.customer-name Note: above query doesn’t correctly deal with duplicates, can be modified to do so as we will see In general, it is not possible/straightforward to move the entire nested subquery from clause into the outer level query from clause A temporary relation is created instead, and used in body of outer level queryOptimizing Nested SubqueriesOptimizing Nested SubqueriesIn general, SQL queries of the form below can be rewritten as shown Rewrite: select … from L1 where P1 and exists (select * from L2 where P2) To: create table t1 as select distinct V from L2 where P21 select … from L1, t1 where P1 and P22 P21 contains predicates in P2 that do not involve any correlation variables P22 reintroduces predicates involving correlation variables, with relations renamed appropriately V contains all attributes used in predicates with correlation variablesOptimizing Nested SubqueriesOptimizing Nested SubqueriesIn our example, the original nested query would be transformed to create table t1 as select distinct customer-name from depositor select customer-name from borrower, t1 where t1.customer-name = borrower.customer-name The process of replacing a nested query by a query with a join (possibly with a temporary relation) is called decorrelation.Optimizing Nested SubqueriesOptimizing Nested SubqueriesDecorrelation is more complicated when the nested subquery uses aggregation, or when the result of the nested subquery is used to test for equality, or when the condition linking the nested subquery to the other query is ‘not exists’, and so on.物化视图物化视图物化视图是计算并存储内容的视图 考虑视图 create view branch-total-loan(branch-name, total-loan) as select branch-name, sum(amount) from loan group by branch-name 如果频繁需要总贷款额, 那么物化上述视图将很有用 节省了查找许多元组并累加其数额的工作物化视图维护物化视图维护保持物化视图相对基础数据为最新的任务称为物化视图维护 物化视图可通过每次更新时重新计算得到维护 更好的选择是利用增量视图维护 利用对数据库关系的改变来计算物化视图的改变, 从而得到更新物化视图维护物化视图维护视图维护可通过下列做到 手工定义视图定义中每个关系上的插入, 删除, 修改触发器 每当数据库关系被更新时利用手写代码更新视图 数据库直接支持增量视图维护增量视图维护对一个关系或表达式的改变(插入和删除)称为其差异 从r 中插入和删除的元组集合记为 ir 及 dr 为简化描述, 只考虑插入和删除 更新元组替换为先删除元组再插入更新后元组 我们描述当给定输入的改变时, 如何计算每个关系操作结果上的改变 然后概述如何处理关系代数表达式连接操作连接操作考虑物化视图v = r s 以及对r 的更新 令 rold 和 rnew 表示关系r 的新旧状态 考虑对r 的插入情况: 我们可以将 rnew s 写为 (rold  ir) s 并将上式重写为 (rold s)  (ir s) 但 (rold s) 正是物化视图的旧值, 故视图的增量改变正是 ir s 因此, 对插入 vnew = vold (ir s) 类似地对删除 vnew = vold – (dr s)选择和投影操作选择和投影操作选择: 考虑视图v = (r). vnew = vold (ir) vnew = vold - (dr) 投影是更复杂的操作 R = (A,B), 且r(R) = { (a,2), (a,3)} A(r) 具有单个元组 (a). 如果我们从r 中删除元组(a,2), 我们不能从A(r)中删除元组(a), 但是若我们又删除了(a,3), 我们就应该删除该元组选择和投影操作选择和投影操作对投影A(r)中的每个元组, 我们将保存一个计数, 即它被导出了多少次 当对r 插入元组时, 如果结果元组已经在A(r) 中, 我们就递增它的计数, 否则加入一条新元组且计数值为1 当对r 删除元组时, 我们递减A(r) 中对应元组的计数值 若计数值变成0, 我们从A(r) 中删除该元组聚合操作聚合操作count : v = Agcount(B)(r). 当插入元组集合ir 时 对ir 中的每条元组r, 若对应分组已经存在于v中, 我们递增其计数, 否则增加一条新元组, 其count = 1 当删除元组集合dr 时 对ir 中的每条元组, 我们查找t.A在v中的分组, 并从该组计数中减去1. 若计数变成0, 从 v 中删除分组t.A的元组 sum: v = Agsum (B)(r) 我们以类似于计数的方式来维护总和, 只是要加/减B值而非对计数的加/减1 另外我们维护计数以便发现没有元组的分组. 这样的分组要从v中删除 不能简单的测试 sum = 0 (why?) 为处理avg, 我们维护sum 和count 分别聚合值, 最后再相除聚合操作聚合操作min, max: v = Agmin (B) (r). 处理r 上插入是直截了当的. 删除时维护聚合值 min 及 max 可能更昂贵. 我们必须检查同组中的 r 的其他元组以找出新的最大最小值其他操作其他操作集合交: v = r  s 当插入一条元组到r 时我们检查它是否存在于s中, 如果是则加入到v 中 当从r 删除一条元组时, 若它存在于交集中则删除之 更新s 是对称的 其他集合操作(并与差)以类似方式处理 外连接的处理方式基本与连接相同, 但需要一些额外工作处理表达式处理表达式为处理整个表达式, 我们导出计算对每个子表达式结果的增量改变的表达式, 从最小表达式开始 例如考虑 E1 E2 , 其中E1和E2 都可能是复杂表达式 假设要插入E1的元组集合由D1给出 早先已算出, 因为较小子表达式先处理 则要插入E1 E2的元组集合为 D1 E2 这正是维护连接的通常的方法 查询优化与物化视图查询优化与物化视图重写查询以利用物化视图: 有物化视图v = r s 可用 用户提交了查询 r s t 我们可以重写查询为v t 是否这么做取决于两种选择的代价估算 用视图定义代替物化视图的使用: 有物化视图v = r s 可用, 但是上面无任何索引 用户提交查询 A=10(v). 再假设 s 在公共属性B上有索引, r 在属性A上有索引. 此查询的最佳方案可能是用r s 替换 v, 这导致查询方案A=10(r) s 应该扩展查询优化器以考虑所有上述替代方案并选择最佳总体方案 物化视图选择物化视图选择物化视图选择: “最该物化的视图集合是哪些?”. 此决定必须在系统负载的基础上做出 索引与物化视图一样, 索引选择问题密切相关, 尽管更简单些 某些数据库系统提供工具来帮助数据库管理员做出索引和物化视图的选择End of ChapterEnd of Chapter(Extra slides with details of selection cost estimation follow)Selection Cost Estimate ExampleSelection Cost Estimate ExampleNumber of blocks is baccount = 500: 10,000 tuples in the relation; each block holds 20 tuples. Assume account is sorted on branch-name. V(branch-name,account) is 50 10000/50 = 200 tuples of the account relation pertain to Perryridge branch 200/20 = 10 blocks for these tuples A binary search to find the first record would take log2(500) = 9 block accesses Total cost of binary search is 9 + 10 -1 = 18 block accesses (versus 500 for linear scan)branch-name = “Perryridge”(account)Selections Using IndicesSelections Using IndicesIndex scan – search algorithms that use an index; condition is on search-key of index. A3 (primary index on candidate key, equality). Retrieve a single record that satisfies the corresponding equality condition EA3 = HTi + 1 A4 (primary index on nonkey, equality) Retrieve multiple records. Let the search-key attribute be A. A5 (equality on search-key of secondary index). Retrieve a single record if the search-key is a candidate key EA5 = HTi + 1 Retrieve multiple records (each may be on a different block) if the search-key is not a candidate key. EA3 = HTi + SC(A,r)Cost Estimate Example (Indices)Cost Estimate Example (Indices)Since V(branch-name, account) = 50, we expect that 10000/50 = 200 tuples of the account relation pertain to the Perryridge branch. Since the index is a clustering index, 200/20 = 10 block reads are required to read the account tuples. Several index blocks must also be read. If B+-tree index stores 20 pointers per node, then the B+-tree index must have between 3 and 5 leaf nodes and the entire tree has a depth of 2. Therefore, 2 index blocks must be read. This strategy requires 12 total block reads.Consider the query is branch-name = “Perryridge”(account), with the primary index on branch-name.Selections Involving ComparisonsSelections Involving ComparisonsA6 (primary index, comparison). The cost estimate is: where c is the estimated number of tuples satisfying the condition. In absence of statistical information c is assumed to be nr/2. A7 (secondary index, comparison). The cost estimate: where c is defined as before. (Linear file scan may be cheaper if c is large!).selections of the form AV(r) or A  V(r) by using a linear file scan or binary search, or by using indices in the following ways:Example of Cost Estimate for Complex SelectionExample of Cost Estimate for Complex SelectionConsider a selection on account with the following condition: where branch-name = “Perryridge” and balance = 1200 Consider using algorithm A8: The branch-name index is clustering, and if we use it the cost estimate is 12 block reads (as we saw before). The balance index is non-clustering, and V(balance, account = 500, so the selection would retrieve 10,000/500 = 20 accounts. Adding the index block reads, gives a cost estimate of 22 block reads. Thus using branch-name index is preferable, even though its condition is less selective. If both indices were non-clustering, it would be preferable to use the balance index.Example (Cont.)Example (Cont.)Consider using algorithm A10: Use the index on balance to retrieve set S1 of pointers to records with balance = 1200. Use index on branch-name to retrieve-set S2 of pointers to records with branch-name = Perryridge”. S1  S2 = set of pointers to records with branch-name = “Perryridge” and balance = 1200. The number of pointers retrieved (20 and 200), fit into a single leaf page; we read four index blocks to retrieve the two sets of pointers and compute their intersection. Estimate that one tuple in 50 * 500 meets both conditions. Since naccount = 10000, conservatively overestimate that S1  S2 contains one pointer. The total estimated cost of this strategy is five block reads.