第6章查询处理和优化

第6章查询处理和优化内容摘要：

符 ) 将第一层查询所涉及 R1表中的每条记录，代入虚线框所标出查询体， 此时 ，判断该记录是否满足查询条件。 存在什么问题。 能否再进行优化。 注意： 采用代入法时，尽可能作 “ 部分选择 ”。 SELECT A1 FROM R1 WHERE 比较符 CONST1 AND IN (SELECT A4 FROM R2 WHERE 比较符 ) RE R1. 比较符 CONST1 AND FROM R1’ WHERE R1’.A3 看作临时表 R1’ 将 R1’的每个元组逐个代入，检查限制条件是否满足，以减少需检查的上层查询所涉及表的元组数目。 有些 DBMS将嵌套查询转换为等效的非嵌套查询，但是这种方法不一定在所有情况下都可行。 依赖于存取路径的规则优化 代数优化不涉及存取路径，对各种操作的执 行策略无从选择。 只能在操作的次序和组合上做 一些变换和调整。 单靠代数优化比较粗糙，优化效果有限，合 理选择存取路径，往往能收到显著的效果。 本节结合存取路径的分析，讨论各种基本操作执行的策略及其选择原则。 选择操作的实现和优化 选择条件： 等值 = 范围 , 集合 IN,EXISTS,NOT EXISTS 复合 AND,OR 选择操作的执行策略与选择条件、可用的存取路径以及选取的元组数在整个关系中所占的比例有关。  实现方法：顺序扫描、尽量利用散列索引等方法。 选择操作选择存取路径的启发式规则： （ 1） 对于小关系， 顺序扫描。 （ 2） 若无索引、散列等存取路径可用，或估计选取的元组数占关系的比例较大（大于 20%）且有关属性上无簇集索引， 顺序扫描。 （ 3） 对于主键的等值选择，优先选用主键的索引或散列。 （ 4） 对于非主键的等值选择，若选取的元组数占关系的比例较小（小于 20%），可以用无序索引；否则只能用簇集索引或顺序扫描。 （ 为什么。 ） （ 5） .对于范围条件，先通过索引找到范围的边界，再通过索引的顺序集沿相应方向搜索， 如中选的元组数在关系中所占比例较大，宜采用簇集索引或顺序扫描。 （ 6）对于用 AND连接的合取选择条件：  优先选用多属性索引  若有多个可用的次索引，可用预查找处理，最后做其余条件检查  个别条件可用（ 3）（ 4）（ 5）之一，求得相应组，再将这些元组用其它条件筛选  顺序扫描 （ 7）用 OR连接的析取选择条件，尚无好的方法。 只能按其中各个条件分别选出一个元组集，再求这些元组集的并。 在 OR连接的诸条件中，只要有一个条件无合适的存取路径，就只能用顺序扫描。 连接操作的实现和优化 连接开销较大，为查询优化的重点，这里主要讨论二元连接（ Two Way Join）。 实现方法 （ nested loop） 1).嵌套循环 关系 R与 S进行连接操作，最原始的办法是取 R的一个元组，与 S的所有元组比较，凡是满足连接条件的元组就进行连接并且作为结果输出。 然后再取 R的下一个元组，和 S的所有元组比较，直到 R的所有元组比较完为止。 R S = R (n个 ) S (m个 ) i j 嵌套循环算法 /*设 R有 n个元组， S有 m个元组 */ i:=1,j:=1。 while(i≤n) do{while(j≤m) do{if R(i)[A] = S(j)[B] then 输出 R(i),S(j)至 T。 j := j + 1 } j:=1,i:=i+1 } T为 R和 S连接的结果 R为外关系（ outer relation） , S为内关系（ inner relation）。 事实上， 关系是以物理块为单位取到内存 ，设 R和 S各有一缓冲块 ， PR为 R的块因子（每块中所含的元组数）。 则 R每次 I/O取 PR个元组，可改进上述算法，使 S扫描一次可以与 R的。