Loading... # Ch.9 关系查询处理和查询优化 ## 9.1 查询优化在关系数据库中的重要性和可能性 ### 重要性 关系系统的查询优化减轻了用户选择存取路径的负担，用户只要提出干什么，而不必指出怎么干 查询优化的优点不仅在于用户**不必考虑如何最好的表达查询以获得较好的效率**，而且在于**系统可以比用户程序的优化做得更好** ### 可能性 1. **可以从数据字典中获取许多统计信息，优化器可以根据这些信息选择有效的执行计划**，而用户程序难以获得这些信息 2. 如果数据库的物理统计信息改变，**系统可以自动对查询进行重新优化已选择相适应的执行计划** 3. 优化器可以考虑数十、数百种不同的执行计划，**从中选出较优的一种** 4. 优化器中**包括了许多复杂的优化技术**，这些优化技术往往只有最好的程序员才能掌握 ## 9.2 估算下列操作需要多少次磁盘快读 假设 $R(A,B)$, $S(B,C,D)$ 的情况如下：$R$ 有20000个元组，$S$ 有1200个元组，一个块上能装40个$R$的元组，能装30个$S$的元组 ### 9.2.1 $R$ 上没有索引, ``SELECT * FROM R`` 需要对R进行全表扫描， $$ N = 20000/40=500 $$ ### 9.2.2 $R$ 中 $A$ 为主码, 其上有三层B+树索引, ``SELECT * FROM R WHERE A=10`` 对 $R$ 进行索引扫描, $$ N=3+1 $$ 其中3块为B+树索引块, 1块数据块 ### 9.2.3 嵌套循环连接 $R \Join S$ $R$ 本身 $20000/40=500$ 块, $S$ 本身 $1200/30=40$ 块, 以 $S$ 为外表, 假设内存分配的块数为 $k$, 嵌套循环连接需要的块数 $$ N=40+\lceil \frac{40}{k-1} \rceil \times 500 $$ ### 9.2.4 排序合并连接 $R \Join S$, 区分 $R$ 与 $S$ 在 $B$ 属性上有序和无序两种情况 #### 排序状况下 $$ N=500+40=540 $$ #### 没有排序状况下 $$ N=540 + 2 \times 500 \times (\log_2{500}+1) + 2 \times 40 \times (\log_2{40}+1) $$ ## 9.3 代数优化 ### 9.3.1 连接、笛卡尔积交换律 $$ E_1 \times E_2 \equiv E_2 \times E_1 $$ $$ E_1 \Join E_2 \equiv E_2 \Join E_1 $$ $$ E_1 \Join_{F} E_2 \equiv E_2 \Join_{F} E_1 $$ ### 9.3.2 连接、笛卡尔积结合律 $$ (E_1 \times E_2) \times E_3 \equiv E_1 \times (E_2 \times E_3) $$ $$ (E_1 \Join E_2) \Join E_3 \equiv E_1 \Join (E_2 \Join E_3) $$ $$ (E_1 \Join_{F} E_2) \Join_{F} E_3 \equiv E_1 \Join_{F} (E_2 \Join_{F} E_3) $$ ### 9.3.3 投影的串接定律 $$ \prod\nolimits_{A_1,A_2,\cdots,A_n}(\prod\nolimits_{B_1,B_2,\cdots,B_m}(E)) \equiv \prod\nolimits_{A_1,A_2,\cdots,A_n}(E) $$ 其中 $\{A_1,A_2,\cdots,A_n\}$ 构成 $\{B_1,B_2,\cdots,B_m\}$ 的子集 ### 9.3.4 选择的串接定律 $$ \sigma_{F_1}(\sigma_{F_2}(E)) \equiv \sigma_{F_1 \land F_2}(E) $$ 其中 $E$ 是关系代数表达式，$F_1$、$F_2$是选择条件 ### 9.3.5 选择的串接定律 若选择条件 $F$ 只涉及 $A_1,A_2,\cdots,A_n$ $$ \sigma_F(\prod\nolimits_{A_1,A_2,\cdots,A_n}(E)) \equiv \prod\nolimits_{A_1,A_2,\cdots,A_n}(\sigma_F(E)) $$ 若F中有涉及不适于 $\{A_1,A_2,\cdots,A_n\}$ 的属性 $\{B_1,B_2,\cdots,B_m\}$ ，则有更一般的规则 $$ \prod\nolimits_{A_1,A_2,\cdots,A_n}(\sigma_F(E)) \equiv \prod\nolimits_{A_1,A_2,\cdots,A_n}(\sigma_F(\prod\nolimits_{A_1,A_2,\cdots,A_n,B_1,B_2,\cdots,B_m}(E))) $$ ### 9.3.6 选择和笛卡尔积的交换律 若$F$中涉及的属性都是$E_1$的属性，则 $$ \sigma_F(E_1 \times E_2) \equiv \sigma_F(E_1) \times E_2 $$ 若$F=F_1 \land F_2$, 且$F_1$只涉及$E_1$中的属性，$F_2$只涉及$E_2$中的属性， $$ \sigma_F(E_1 \times E_2) \equiv \sigma_{F_1}(E_1) \times \sigma_{F_2}(E_2) $$ 若$F_1$只涉及$E_1$中的属性，$F_2$涉及$E_1$和$E_2$中的属性，则 $$ \sigma_F(E_1 \times E_2) \equiv \sigma_{F_2}(\sigma_{F_1}(E_1) \times E_2) $$ 使部分选择在笛卡尔积前先做 ### 9.3.7 选择和并的分配律 设$E=E_1\cup E_2$, $E_1$、$E_2$有相同的属性名，则 $$ \sigma_F(E_1 \cup E_2) \equiv \sigma_F(E_1) \cup \sigma_F(E_2) $$ ### 9.3.8 选择和差的分配律 设$E=E_1\cup E_2$, $E_1$、$E_2$有相同的属性名，则 $$ \sigma_F(E_1 - E_2) \equiv \sigma_F(E_1) - \sigma_F(E_2) $$ ### 9.3.9 选择对自然连接的分配律 $F$ 只涉及 $E_1$、$E_2$ 的公共属性 $$ \sigma_F(E_1 \Join E_2) \equiv \sigma_F(E_1) \Join \sigma_F(E_2) $$ ### 9.3.10 投影与笛卡尔积的分配律 设$E_1$、$E_2$是两个关系表达式, $A_1,A_2,\cdots,A_n$ 是 $E_1$ 的属性, $B_1,B_2,\cdots,B_m$ 是 $E_2$ 的属性, 则 $$ \prod\nolimits_{A_1,A_2,\cdots,A_n,B_1,B_2,\cdots,B_m}(E_1 \times E_2) \equiv \prod\nolimits_{A_1,A_2,\cdots,A_n}(E_1) \cup \prod\nolimits_{B_1,B_2,\cdots,B_m}(E_2) $$ ### 9.3.11 选择与并的分配律 设$E_1$、$E_2$有相同的属性名，则 $$ \prod\nolimits_{A_1,A_2,\cdots,A_n}(E_1 \cup E_2) \equiv \prod\nolimits_{A_1,A_2,\cdots,A_n}(E_1) \cup \prod\nolimits_{A_1,A_2,\cdots,A_n}(E_2) $$ ## 9.4 查询树的启发式优化 ### 9.4.1 典型的启发式规则 1. 选择运算应尽可能先做 2. 把投影运算和选择运算同时进行 3. 把投影同其前或后的双目运算结合起来 4. 把某些选择同在它前面要执行的笛卡尔积结合起来称为一个连接运算 5. 找出公共子表达式 ### 9.4.2 关系表达式的优化算法 > 算法：关系表达式的优化 > 输入：一个表达关系是的查询树 > 输出：优化的查询树 1. 利用等价变换规则4，把形如$\sigma_{F_1 \land F_2 \land \cdots \land F_n}(E)$的表达式变换为 $\sigma_{F_1}(\sigma_{F_2}(\cdots (\sigma_{F_n}(E))\cdots))$ 2. 对于每一个选择，利用等价变换规则4-9尽可能把它移到书的叶端 3. 对每一个投影，利用等价变换规则3、5、10、11中的一般形式尽可能移向书的叶端 4. 利用等价变换规则3-5，把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影，使多个选择或投影能同时执行，或在一次扫描中全部完成 5. 把上述得到的语法树的内节点分组。每一双目运算($\times, \Join, \cup, -$)和他所有的直接祖先(这些直接足协是$\sigma, \prod$运算)为一组。如果其后代直到叶子全是单目运算，则也将他们并入改组，但当双目运算是笛卡尔积($\times$)，而且后面不是与它组成等值连接的选择是，则不能把运算与这个双目运算组成一组。把这些单目运算单独分为一组。 ## 9.5 关系数据库管理系统查询优化一般准则 1. 选择运算应尽可能先做 2. 把投影运算和选择运算同时进行 3. 把投影同其前或后的双目运算结合起来 4. 把某些选择同在它前面要执行的笛卡尔积结合起来称为一个连接运算 5. 找出公共子表达式 6. 选取合适的连接算法 其中1-5是代数优化策略，6是物理优化 ## 9.6 关系数据库管理系统查询优化一般步骤 1. 把查询转化为某种内部表示，通常为语法树 2. 把语法树转换成标准(优化)形式, 即利用优化算法把原始的语法树转换成优化的形式 3. 选择低层的存取路径 4. 生成查询计划，选择所需代价最小的计划进行执行 最后修改：2021 年 07 月 21 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏