【总结】数据库查询优化技术一：概述

数据库管理系统最基本的操作包括查询、插入、删除和修改等，简称CRUD。

查询的执行，就是查询处理的过程，即数据库按用户指定的SQL语句中的语义，执行语义所限定的操作。为了提高查询语句的执行效率，必须对查询语句进行优化。

查询优化技术，就是对查询语句进行优化的技术，运用查询技术实现数据操纵功能的过程是确定给定查询的高效执行计划的过程。

执行计划，就是查询树，它由一系列内部的操作符组成，这些操作符按一定的运算关系构成查询的一个执行方案。查询优化的追求目标，就是在数据库查询优化引擎生成一个执行策略的过程中，尽量使查询的总开销（总开销通常包括IO、CPU、网络传输等）达到最小。

数据库查询优化技术主要包括：

• 查询重用技术
• 查询重写规则
• 查询算法优化技术
• 并行查询优化技术
• 分布式查询优化技术
• 其他方面（如框架结构）的优化技术

这6项技术构成了一个“广义的数据库查询优化”的概念。与相对应的“狭义的数据库查询优化”，只包括“查询重写规则”和“查询算法优化”，这是多数书籍在提及“数据库查询优化”时所限定的范围。

从优化的内容角度看，查询优化分为：

• 代数优化（逻辑优化），主要依据关系代数的等价变换做一些逻辑变换。“查询重写规则”属于这种方式，运用了关系代数和启发式规则。
• 非代数优化（物理优化），主要根据数据读取、表连接方式、表连接顺序、排序等技术对查询进行优化。“查询算法优化”属于这种方式，运用了基于代价估算的多表连接算法求解最小花费的技术。

对查询优化技术进行分类的角度：

本文主要包括以下内容：

• 查询优化引擎能做什么样的查询优化操作。
• 查询优化引擎为什么能进行查询优化。

数据库调优为了使数据库应用运行得更快，面向整个数据库管理系统，目标是

• 提高数据库的吞吐量
• 减少的响应时间

数据库调优的方式通常有：

数据库调优通常分为5阶段：

数据库调优涉及的技术：

查询重用是指尽可能利用先前的执行结果，以达到节约查询计算全过程的时间并减少资源消耗的目的。
目前查询重用技术主要集中在两个方面：

• 查询结果的重用，节约了查询计划生成时间和查询执行过程的时间，减少了查询执行全过程的资源消耗。
• 查询计划的重用，减少了查询计划生成的时间和资源消耗。

查询重用技术的弊端，如果结果集很大会消耗很大的内存资源，同样的SQL不同用户获取的结果集可能不完全相同。好处，节约了CPU和IO消耗。

查询重写是查询语句的一种等价转换，即对于任何相关模式的任意状态都会产生相同的结果（相同的关系替代两个表达式中相应的关系，所得到的结果是相同的）。
查询重写有两个目标：

• 将查询转换为等价的、效率更高的形式，例如将效率低的谓词转换为效率高的谓词、消除重复条件等。
• 尽量将查询重写为等价、简单且不受表顺序限制的形式，为物理查询优化阶段提供更多的选择，如视图的重写、子查询的合并转换等。

关系代数的等价变换规则对查询重写提供了理论上的支持。查询重写后，查询优化器可能生成多个连接路径，可以从候选者中择优。

查询重写技术优化思路主要包括：

• 将过程性查询转换为描述性的查询，如视图重写。
• 将复杂的查询（如嵌套子查询、外连接、嵌套连接）尽可能转换为多表连接查询。
• 将效率低的谓词转换为等价的效率高的谓词（如等价谓词重写）。
• 利用等式和不等式的性质，简化WHERE、HAVING和ON条件。

常见的查询重写技术类型，每一类都有自己的规则，这些规则没有确定的、统一的规律，但重写的核心一定是“等价转换”，只有等价才能转换。

查询优化即求解给定查询语句的高效执行计划的过程。
查询计划，也称为查询树，它由一系列内部的操作符组成，这些操作符按一定的运算关系构成查询的一个执行方案。
查询计划，从形式上看是一颗二叉树，树叶是每个单表对象，两个树叶的父结点是一个连接操作符（如左外连接操作符，A left-out join B）连接后的中间结果（另外还有一些其他结点如排序操作等也可以作为中间结果），这个结果是一个临时“关系”，这样直至根结点。

一个查询计划涉及的主要“关系结点”包括：

• 单表结点。考虑单表的数据获取方式，是直接通过IO获取，还是通过索引获取，亦或是先通过索引定位再通过IO获取数据。这是一个从物理存储到内存解析成逻辑字段的过程。
• 两表结点。考虑两表以何种方式连接、代价有多大、连接路径有哪些等。表示的是内存中的元组怎么进行元组间的连接。不同的连接算法导致的连接效率不同，如Hash连接、嵌套连接、归并连接等。
• 多表中间结点。考虑多表连接顺序如何构成代价最少的“执行计划”。许多数据库采用左深树、右深树、紧密树3种方式或其中一部分对多表进行连接，得到多种连接路径。

生成最好的查询计划的策略通常有两个：

• 基于规则优化。根据经验或一些已经探知或被证明有效的方式，定义为“规则”（如根据关系代数得知的规则、根据经验得知的规则等），用这些规则化简查询计划生成过程中符合可被化简的操作，使用启发式规则排除一些明显不好的存取路径，这就是基于规则的优化。
• 基于代价优化。根据一个代价评估模型，在生成查询计划的过程中，计算每条存取路径（存取路径主要包括上述3个“关系结点”）的花费，然后选择代价最小的作为子路径，这样直至所有表连接完毕得到一个完整的路径。主流数据库都采用了基于代价策略进行优化的技术。

查询优化器的实现，多是两种优化策略组合使用，如MySQL和PostgreSQL就采取了基于规则和代价估算的查询优化策略。

多表连接使用最广泛的优化算法有如下几种：

查询的基本操作是选择、投影和连接。选择和投影的优化规则适用于SPJ（Select-Project-Join）和非SPJ（SPJ+GROUPBY等操作）。连接包括两表连接和多表连接。多表连接是其中最难的，因为多表连接有多种连接次序，所以查询的执行计划的数目随表个数呈指数级增长，搜索空间极度膨胀，仅搜索花费最小的查询计划就开销巨大，这是查询优化器实现时需要考虑的问题。

在单机数据库系统中，给定一个查询（Query），查询优化算法只需找到查询的一个具有最小执行花费的执行计划。但在并行数据库系统中，需要把查询工作分解为一些可以并行运行的子执行计划。一些商业数据库提供了并行查询的功能，用以优化查询执行操作。
一个查询能否并行执行，取决于以下因素：

• 系统中的可用资源，如内存、高速缓存中的数据量等。
• CPU的数目。
• 运算中的特定代数运算符，如多表连接的单表扫描可以并行进行。不同商业数据库，对查询并行的实现也不相同。在同一个SQL内，查询并行可分为两种：
• 操作内并行。将同一操作如单表扫描操作、两表连接操作、排序操作等分解成多个独立的子操作，由不同的CPU同时执行。
• 操作间并行。一条SQL查询语句可以分解成多个子操作，由多个CPU执行。

在分布式数据库系统中，查询优化的重点是：

• 查询策略优化，主要是节点间数据传输策略。
• 局部处理优化，传统的单节点数据库的查询优化技术。

在查询优化策略中，数据的通信开销是优化算法考虑的主要因素。分布式查询优化以减少传输的次数和数据量作为查询优化的目标。所以，分布式数据库系统中的代价估算模型，除了考虑CPU代价和IO代价外，还要考虑通过网络在结点间传输数据的代价。

代价估算模型：总代价=IO代价+CPU代价+通信代价

数据库的查询性能，还取决于其他一些因素，如数据库集群系统中的SD（Share Disk）集群和SN（Share Nothing）集群，不同的架构查询优化技术也不同。SD集群采用的是共享存储方式，在数据的读写时可能产生读写冲突，单表扫描会受到影响。SN集群采用的是非共享式存储方式，所以在考虑了通信代价后单结点的优化方式依然适用。

• 《数据库查询优化的艺术：原理解析和SQL性能优化》，李海翔