|
|
|
|
| 查询处理是指从数据库中提取数据的一系列活动。这一系列活动包括：将高级数据库语言表示的查询语句翻译成为能在文件系统这一物理层次上实现的表达式，为优化查询进行各种转换，以及查询的实际执行。
|
|
|
|
|
| 查询处理的代价通常取决于磁盘的访问，磁盘的访问比内存访问速度要慢。对于一个给定的查询，可以有许多可能的处理策略，复杂查询更是如此。就所需的磁盘访问次数而言，策略好坏差别很大，有时甚至相差几个数量级。所以，系统多花一点时间选择一个较好的查询策略是很值得的。
|
|
|
|
|
| 查询优化是为了查询选择最有效的查询计划的过程。查询优化一方面是在关系代数级进行优化，要做的是力图找出与给定表达式等价，但执行效率更高的一个表达式。查询优化的另一方面涉及查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法以及将使用的特定索引等等。
|
|
|
| 一个查询往往会有许多实现办法，关键是如何找出一个与之等价的且操作时间又少的表达式。下面将专门讨论这个问题。
|
|
|
|
|
| 关系系统的查询优化是关系数据库管理系统实现的关键技术，又是关系系统的优点。因为，用户只要提出“干什么”，不必指出“怎么干”。在关系代数表达式中需要指出若干关系的操作步骤，问题是怎样做才能保证省时、省空间、效率高，这就是查询优化的问题。
|
|
|
| 需要注意的是，在关系代数运算中，笛卡儿积、连接运算最费时间和空间，究竟应采用什么样的策略，节省时间空间。这就是优化的准则。
|
|
|
|
|
|
|
| （1）提早执行选取运算。对于有选择运算的表达式，应优化成尽可能先执行选择运算的等价表达式，以得到较小的中间结果，减少运算量和从外存读块的次数。
|
|
|
| （2）合并乘积与其后的选择运算为连接运算。在表达式中，当乘积运算后面是选择运算时，应该合并为连接运算，使选择与乘积一道完成，以避免做完乘积后，需再扫描一个大的乘积关系进行选择运算。
|
|
|
| （3）将投影运算与其后的其他运算同时进行，以避免重复扫描关系。
|
|
|
| （4）将投影运算和其前后的二目运算结合起来，使得没有必要为去掉某些字段再扫描一遍关系。
|
|
|
| （5）在执行连接前对关系适当地预处理，就能快速地找到要连接的元组。方法有两种：索引连接法、排序合并连接法。
|
|
|
| （6）存储公共子表达式。对于有公共子表达式的结果应存于外存（中间结果），这样，当从外存读出它的时间比计算的时间少时，就可节约操作时间。
|
|
|
|
|
| 优化的策略均涉及关系代数表达式，所以讨论关系代数表达式的等价变换规则显得十分重要。常用的等价变换规则有如下10种。
|
|
|
|
|
| 设E1和E2是关系代数表达式，F是连接运算的条件，则有：
|
|
|
|
|
|
|
| 设E1、E2、E3是关系代数表达式，F1、F2是连接运算的条件，则有：
|
|
|
|
|
|
|
| 设E是关系代数表达式，A1，…，An和B1，…，Bm是属性名，且B1，…，Bm是A1，…，An的子集。则有：
|
|
|
|
|
|
|
|
|
| 设E是关系代数表达式，F1、F2是选取条件表达式，选择的串接定律说明选择条件可以合并，则有：
|
|
|
|
|
|
|
| 设E是关系代数表达式，F是选取条件表达式，并且只涉及A1，…，An属性，则有：
|
|
|
|
|
| 若F中有不属于A1，…，An属性，B1，…，Bm，那么有更一般的规则：
|
|
|
|
|
| 该规则可将投影分裂为两个，使得其中的一个可能被移到树的叶端。
|
|
|
|
|
|
|
|
|
| 如果F=F1∧F2，并且，F1只涉及E1中的属性，F2只涉及E2中的属性，则有：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 设E1、E2是两个关系表达式，A1，…，An是E1中的属性，B1，…，Bm是E2中的属性，则：
|
|
|
|
|
|
|
|
|
|
|
|
|
| 利用上述的等价变换规则可以对关系代数表达式进行优化，使得优化后的关系代数表达式符合上述的6条基本优化的准则。
|
|
|
|
|
|
|
|
|
|
|
（1）利用规则4将形如 变换为：
|
|
|
|
|
| （2）对每一个选择，利用规则4~8尽可能将它移到树的叶端。
|
|
|
| （3）对每一个投影，利用规则3、9、10，5中的一般形式尽可能将它移到树的叶端。
|
|
|
| （4）利用规则3~5将选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时进行，或在一次扫描中全部完成。
|
|
|
（5）将上述得到的语法树的内节点分组。每一双目运算（×，∪， ，-）和它所有的直接祖先为一组（这些直接祖先是σ，π运算）。如果其后代直到叶子全部是单目运算，则将它并入该组。
|
|
|
| （6）生成一个程序，每组节点的计算是程序中的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。
|
|
|
