数据库课件第九章关系查询处理和查询优化.pptVIP

基于代价的优化（续） 2. 对基表的每个列 该列不同值的个数(m) 选择率(f) 如果不同值的分布是均匀的，f＝1/m 如果不同值的分布不均匀，则每个值的选择率＝具有该值的元组数/N 该列最大值 该列最小值 该列上是否已经建立了索引 索引类型(B+树索引、Hash索引、聚集索引) An Introduction to Database System 基于代价的优化（续） 3. 对索引(如B+树索引) 索引的层数(L) 不同索引值的个数 索引的选择基数S(有S个元组具有某个索引值) 索引的叶结点数(Y) An Introduction to Database System 基于代价的优化（续） 二、 代价估算示例 全表扫描算法的代价估算公式 如果基本表大小为B块，全表扫描算法的代价 cost＝B 如果选择条件是码＝值，那么平均有哪些信誉好的足球投注网站代价 cost＝B/2 An Introduction to Database System 基于代价的优化（续） 2. 索引扫描算法的代价估算公式 如果选择条件是码＝值 如［例1-C2］，则采用该表的主索引 若为B+树，层数为L，需要存取B+树中从根结点到叶结点L块，再加上基本表中该元组所在的那一块，所以cost=L+1 如果选择条件涉及非码属性 如［例1-C3］，若为B+树索引，选择条件是相等比较，S是索引的选择基数(有S个元组满足条件) 最坏的情况下，满足条件的元组可能会保存在不同的块上，此时，cost=L+S An Introduction to Database System 基于代价的优化（续） 如果比较条件是＞，＞＝，＜，＜＝操作 假设有一半的元组满足条件就要存取一半的叶结点 通过索引访问一半的表存储块cost=L+Y/2+B/2 如果可以获得更准确的选择基数，可以进一步修正Y/2与B/2 An Introduction to Database System 基于代价的优化（续） 3. 嵌套循环连接算法的代价估算公式 9.4.1中已经讨论过了嵌套循环连接算法的代价cost＝Br+Bs/(K-1) Br 如果需要把连接结果写回磁盘， cost＝Br+Bs/(K-1) Br +(Frs*Nr*Ns)/Mrs 其中Frs为连接选择性(join selectivity)，表示连接结果元组数的比例 Mrs是存放连接结果的块因子，表示每块中可以存放的结果元组数目。 An Introduction to Database System 基于代价的优化（续） 4. 排序-合并连接算法的代价估算公式 如果连接表已经按照连接属性排好序，则cost＝Br+Bs+(Frs*Nr*Ns)/Mrs。 如果必须对文件排序 需要在代价函数中加上排序的代价 对于包含B个块的文件排序的代价大约是(2*B)+(2*B*log2B) An Introduction to Database System 第九章 关系系统及其查询优化 9.1 关系数据库系统的查询处理 9.2 关系数据库系统的查询优化 9.3 代数优化 9.4 物理优化 9.5 小 结 An Introduction to Database System 9.5 小 结 查询处理是RDBMS的核心，查询优化技术是查询处理的关键技术 本章讲解的优化方法 启发式代数优化 基于规则的存取路径优化 基于代价的优化 本章的目的：希望读者掌握查询优化方法的概念和技术 An Introduction to Database System 小 结（续） 比较复杂的查询，尤其是涉及连接和嵌套的查询 不要把优化的任务全部放在RDBMS上 应该找出RDBMS的优化规律，以写出适合RDBMS自动优化的SQL语句 对于RDBMS不能优化的查询需要重写查询语句，进行手工调整以优化性能 An Introduction to Database System * 9.3 代 数 优 化 9.3.1 关系代数表达式等价变换规则 9.3.2 查询树的启发式优化 An Introduction to Database System 9.3.1 关系代数表达式等价变换规则 代数优化策略：通过对关系代数表达式的等价变换来提高查询效率 关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的 两个关系表达式E1和E2是等价的，可记为E1≡E2 An Introduction to Database System 关系代数表达式等价变换规则（续） 常用的等价变换规则： 1. 连接、笛卡尔积交换律 设E1和E2是关系代数表达式，F是连接运算的条件，则有 E1 × E2≡E2 ×