3.3 关系代数表达式的优化

在层次模型和网状模型中，用户使用过程化的语言表达查询要求、执行何种记录级的操作，以及操作的序列等，所以用户必须了解存取路径，系统要提供用户选择存取路径的手段，这样，查询效率便由用户的存取策略决定。在这两种模型中，要求用户有较高的数据库技术和程序设计水平。而在关系模型中，关系系统的查询优化都是由数据库管理系统来实现的，用户不必考虑如何表达查询以获得较好的效率，只要告诉系统“干什么”就可以了，因为系统可以比用户程序的“优化”做得更好。

由数据库管理系统来实现查询优化的优势如下。

1）优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。

2）如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。

3）优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。

4）优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。

实际系统对查询优化的具体实现不尽相同，但一般来说，可以归纳为四个步骤。

1）将查询转换成某种内部表示，通常是语法树。

2）根据一定的等价变换规则把语法树转换成标准（优化）形式。

3）选择低层的操作算法。对于语法树中的每一个操作都需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。

4）生成查询计划。查询计划也称查询执行方案，是由一系列内部操作组成的。这些内部操作按一定的次序构成查询的一个执行方案。通常这样的执行方案有多个，需要对每个执行计划计算代价，从中选择代价最小的一个。

总之，关系数据库查询优化的总目标是：选择有效的策略，求得给定关系表达式的值，达到提高DBMS系统效率的目标。