第4章关系数据库的查询优化处理.ppt

统计信息(续) （2）对基表的每个列 该列不同值的个数(m) 选择率(f) 如果不同值的分布是均匀的，f＝1/m 如果不同值的分布不均匀，则每个值的选择率＝具有该值的元组数/N 该列最大值 该列最小值 该列上是否已经建立了索引 索引类型(B+树索引、Hash索引、聚集索引) * / 70 统计信息(续) * / 70 （3）对索引(如B+树索引) 索引的层数(L) 不同索引值的个数 索引的选择基数S(有S个元组具有某个索引值) 索引的叶结点数(Y) 2.代价估算 （1）全表扫描算法的代价估算公式 如果基本表大小为B块，全表扫描算法的代价 cost＝B 如果选择条件是码＝值，那么平均搜索代价 cost＝B/2 * / 70 （2）索引扫描算法的代价估算公式 如果选择条件是码＝值 如［例4.1］中的C2，则采用该表的主索引 若为B+树，层数为L，需要存取B+树中从根结点到叶结点L块，再加上基本表中该元组所在的那一块，所以cost=L+1 如果选择条件涉及非码属性 如［例4.1］中的C3，若为B+树索引，选择条件是相等比较，S是索引的选择基数(有S个元组满足条件) 最坏的情况下，满足条件的元组可能会保存在不同的块上，此时，cost=L+S * / 70 如果比较条件是＞，＞＝，＜，＜＝操作 假设有一半的元组满足条件就要存取一半的叶结点 通过索引访问一半的表存储块cost=L+Y/2+B/2 如果可以获得更准确的选择基数，可以进一步修正Y/2与B/2 * / 70 （3）嵌套循环连接算法的代价估算公式 4.5.1中已经讨论过了嵌套循环连接算法的代价cost＝Br+Bs/(K-1) Br 如果需要把连接结果写回磁盘， cost＝Br+Bs/(K-1) Br +(Frs*Nr*Ns)/Mrs 其中Frs为连接选择性(join selectivity)，表示连接结果元组数的比例 Mrs是存放连接结果的块因子，表示每块中可以存放的结果元组数目。 * / 70 （4）排序-合并连接算法的代价估算公式 如果连接表已经按照连接属性排好序，则cost＝Br+Bs+(Frs*Nr*Ns)/Mrs。 如果必须对文件排序 需要在代价函数中加上排序的代价 对于包含B个块的文件排序的代价大约是(2*B)+(2*B*log2B) * / 70 小结 查询处理是RDBMS的核心，查询优化技术是查询处理的关键技术 本章讲解的优化方法 启发式代数优化 基于规则的存取路径优化 基于代价的优化 本章的目的：希望读者掌握查询优化方法的概念和技术 * / 70 小结(续) 比较复杂的查询，尤其是涉及连接和嵌套的查询 不要把优化的任务全部放在RDBMS上 应该找出RDBMS的优化规律，以写出适合RDBMS自动优化的SQL语句 对于RDBMS不能优化的查询需要重写查询语句，进行手工调整以优化性能 * / 71 把代数表达式Q1变换为Q2、 Q3， 即有选择和连接操作时，先做选择操作，这样参加连接的元组就可以大大减少，这是代数优化 在Q3中 SC表的选择操作算法有全表扫描和索引扫描2种方法，经过初步估算，索引扫描方法较优 对于S和SC表的连接，利用S表上的索引，采用index join代价也较小，这就是物理优化 * / 70 4.2 查询优化技术 4.2.1 手动优化与自动优化 自动优化与手动相比较，系统的自动优化有如下特征： （1）能够从数据字典中获取统计信息，根据这些信息选择有效地执行计划。用户手工优化时的程序则难以得到这些信息。 （2）当数据库物理统计信息改变时，系统可以自动进行重新优化已选择相适应的执行计划，而手工优化必须重新编写程序。 （3）从多种（如数百种）不同的执行计划中进行选择，而手工优化时，程序员一般只能考虑数种可能性。 （4）优化过程可能包含相当复杂的各种优化技术，这需要受过良好训练的专业人员才能掌握，而系统的自动优化是每个数据库使用人员（包括不具有专业训练的普通用户）都能拥有相应的优化技术。一个“好”的数据库系统，其中的查询优化应当是自动的，即由系统DBMS自动完成查询优化过程。 * / 70 4.2.2 查询优化器 1.查询优化器和三类优化技术 查询优化器所使用的技术可以分为三类： （1）规则优化技术 （2）物理优化技术 （3）代价估算优化技术 * / 70 2.关系查询优化的可行性 关系代数具有5种基本运算，这些运算本身和相互间满足一定的运算定律，例如，结合律、交换律、分配率和串接律等，这就意味着不同的关系代数表达式可以得到同一结果，因此用关系代数语言进行的查询就有进行的必要优化的可能。 （1）关系代数中的等价表达式 （2）等价的不同表达形式与相应查询效率间的必然联系 （3）获取较高查询效率表