《数据库系统概念》17-查询优化

一、查询优化是为处理查询找出一个好的策略的过程。一个查询一般有多种方法可以计算出结果，系统负责将用户输入的查询转换成能够更有效执行的等价查询。

复杂的查询操作涉及多级存取磁盘的操作，由于从磁盘中传输数据比从内存中要慢得多，所以有必要进行查询优化，以选择一个能够最小化磁盘存取的方法。

有很多等价规则可供将一个表达式转化成等价表达式，可以使用这些规则系统地产生与所给查询等价的所有表达式。

选择查询处理策略的第一步就是找到一个关系代数表达式，使它与所给的表示是等价并且据估计有更小的执行代价。

二、数据库系统为执行一个操作所选择的策略依赖于每个关系的大小和列值的分布情况。数据库系统可以为每个关系r存储统计信息，从而能够基于这些可靠消息选择合适的策略。这些统计信息包括：关系r中的元组数；关系r中的一个记录的大小；关系r中某个特定属性中出现的不同取值的数目等。这些统计信息使得我们可以估计各种操作的结果集的大小和执行操作的代价。当处理一个查询的过冲中有多个索引可用于辅助的时候，关系的统计信息特别有用，这些信息对查询处理策略的选择有很大的影响。

三、对于每个表达式，可以用一些等价规则产生多个可选的执行计划，然后从中选择代价最小的执行计划。为了减少需要产生的可选表达式和执行计划的数量，产生了多种优化技术，比如可以使用启发式的方法，来减少优化的代价。用于关系代数查询转换的启发式规则包括“及早执行选择操作”、“及早执行投影操作”、“避免笛卡尔积操作”等。

还可以使用物化视图来加速查询处理。当原关系发生修改时，需要用增量的视图维护来高效地更新物化视图。利用包含一个操作的输入的变化量的代数表达式，能够完成对该操作的变化量的计算。其他与物化视图相关的问题还包括如何借助物化视图进行查询优化和如何选择需要待物化的视图。

学习资料：Database System Concepts, by Abraham Silberschatz, Henry F.Korth, S.Sudarshan