The Art of Database Query Optimizer Principle and SQL Performance Optimization
从原理角度深度解读和展示数据库查询优化器的技术细节和全貌；从源码实现角度全方位深入分析MySQL和PostgreSQL两大主流开源数据库查询优化器的实现原理；从工程实践的角度对比了两大数据库的查询优化器的功能异同和实现异同。
查询优化技术
对查询语句(query)进行优化的技术就是查询优化技术,运用查询技术实现数据操纵(CURD)功能的过程是确定给定查询的高效执行计划的过程。执行计划就是查询树，它是由一系列内部的操作符组成，这些操作符按照一定的运算关系构成查询的一个执行方案。查询优化的追求目标在数据库查询优化引擎生成一个执行策略的过程，尽量使查询的总开销(IO,CPU,网络传输，MEM)达到最小
查询优化技术内容
广义和狭义
广义的数据库查询优化：查询重用技术，查询重写规则，查询算法优化技术，并行查询优化技术，分布式查询优化技术
狭义的数据库查询优化：查询重写规则，查询算法优化
优化的内容
代数优化：逻辑优化，逻辑优化主要依据关系代数的等价变换做一些逻辑变换。
非代数优化：物理优化，物理优化主要根据数据读取，表连接方式，表连接顺序，排序等技术对查询进行优化。查询算法优化属于物理优化方式，运用了基于代价估算的多表连接算法求解最小花费的技术。
查询重用技术
查询重用尽可能利用先前的执行结果，以达到节约查询计算全过程的时间并减少资源消耗的目的。目前查询重用技术主要集中在两个方面
查询结果的重用：在缓冲区中分配一块缓冲块，存放该SQL语句文本和最后的结果集，当遇到同样的SQL输入时，可直接把结果返回。查询结果的重用技术节约了查询计划生成时间和查询执行过程的时间，减少了查询执行全过程的资源消耗。
查询计划的重用：缓存一条查询语句的执行计划和其相应的语法树结构。查询计划的重用技术减少了查询计划生成的时间和资源消耗。
查询重用技术有利有弊，弊端就是查询结果集很大的话就会消耗很大的内存资源，同样的SQL不同用户获取的结果集可能完全不相同；好处就是节约了CPU和IO消耗。
查询重写规则
查询重写是一种查询语句的等价转换，即对于任何相关模式的任意状态都会产生相同的结果(相同的关系替代两个表达式中相应的关系，所得到的结果是相同的)查询重写的目标
将查询转换为等价的，效率更高的形式，例如将效率低的谓词转换为效率高的谓词，消除重复条件。
尽量将查询重写为等价，简单不受表顺序限制的形式，为物理查询优化阶段提供更多的选择，如视图的重写，子查询的合并转换等。
查询重写的依据是关系代数,关系代数的等价变换规则对查询重写提供了理论上的支持，查询重写后，查询优化器可能生出多个连接路径，可以从后选中择优。
查询重写技术可以从以下四个角度进行：[1]为逻辑优化，[2]为物理优化
语法级[1]：查询语言层的优化，基于语法进行优化
代数级[1]：形式逻辑进行优化，运用关系代数原理进行优化
语义级[1]：根据完整约束性，对查询语句进行语义理解，推知一些可以优化的操作
物理级[2]：基于代价估算模型，比较得出各种执行方式中代价最小的。
查询重写技术的优化思路主要分为以下步骤：
将过程性查询转换为描述性的查询，如视图重写。
将复杂的查询(如嵌套子查询，外连接，嵌套链接)尽可能转换为多表连接查询。
将效率低的谓词转换为效率高的谓词，消除重复条件(如等价谓词重写)。
利用等式和不等式的性质，简化WHERE，HAVING和ON条件
如何改进现有查询重写规则的效率，如何发现更多更有效的重写规则，是查询优化的研究内容之一。常见的查询重写技术类型，每一类都有自己的规则，这些规则没有确定的，统一的规律，但重写的核心一定是“等价转换”，只有等价才能转换。
查询算法优化
查询优化即求解给定查询语句的高效执行计划的过程。查询计划，也成为查询数，它由一系列内部的操作符组成，这些操作符按照一定的运算关系构成查询的一个执行方案。Simplicity，就是先将表A和表B连接得到中间结果，然后再和另外的表C连接得到新的中间结果的方式，直到所有的表连接完毕(连接操作就是操作符，这个实例有两个连接操作符。A连接B连接C，C连接B连接A就是两种不同的执行的方案，是两种不同的执行计划，查询优化要选出最高效的一个执行计划)。
查询计划，从形式上看是一颗二叉树，树叶是每个单表对象，两个树叶的父节点是一个连接操作符(如A left-outer join B)连接后的中间结果，这个结果是一个临时“关系”,这样直至根节点。所以从一个查询计划看，涉及的主要“关系节点”包括：
单表节点：单表的数据获取是直接通过IO获取，还是通过索引获取数据，或者是通过索引定位数据的位置后再经过IO到数据块中获取数据，这是一个从物理存储到内存解析成逻辑字段的过程，即符合冯.诺伊曼体系结构的要求(外层数据读入内存才能被处理)。
两表节点：表示的内存中的元组怎么进行元组间的连接，此时，元组通常已经存在了内存中，直接使用即可。这是一个完成用户语义的逻辑操作，但是只是局部操作，只涉及两个具体的关系。完成用户全部语义(用户连接的语义)需要配合多表的连接顺序的操作。不同的连接算法导致连接的效率不同，如数据多时可以使用Hash连接，外表数据量小且内表数据量大时可以使用嵌套连接，数据如果有序可使用归并连接或者先排序后使用归并连接等。
多表中间节点：考虑多表连接顺序如何构成代价最小的“执行计划”。即决定是AB先连接还是BC连接，这是一个比较花费大小的运算，如果判断连接的方式太多，也会导致效率问题。多个关系采用不同次序进行连接，如花费的CPU资源，内存资源差异可能比较大。许多数据库采用左深树，右深树，紧密树三种方式或其中一部分对多表进行连接，得到多种连接路径。
查询优化的目的就是生成最优的查询计划，生成最好的查询计划的策略通常有两个
基于规则优化(RBO)
根据经验或者一些已经探知或被证明有效的方式，定义为“规则”(如根据关系代数得知的规则，根据经验得知的规则等)，用这些规则化简查询计划生成过程中符合可被化简的操作，使用启发式规则排除一些明显不好的存取路径，这就是基于规则的优化
基于代价优化(CBO)
根据一个代价评估模型，在生成查询计划的过程中，计算每条存取路径(存取路径主要包括上述3个“关系节点”)的花费，然后选择代价最小的作为子路径，这样直至所有表连接完毕得到一个完整的路径。主流数据库都采用了基于代价策略进行优化的技术。
查询优化器的实现，多是两种优化策略的组合使用，如MySQL和PostgresSQL就采取了基于规则优化和代价估算的查询优化策略。
多表连接的优化算法中，使用最广泛的算法有如下几种：
SYSTEM-R算法
启发式搜索算法
贪婪算法
动态规划算法
遗传算法
并行查询优化
传统单机数据库系统中，给定一个查询(query)，查询优化算法只需要找到查询的一个具有最小执行花费的执行计划，这样的执行计划必定具有最快的响应时间。在并行数据库中，查询优化的目标是寻找具有最小响应时间的查询执行计划，这需要把查询工作分解为一些可以并行运行的子工作。一个查询是否可以并行执行，取决于以下因素：
系统中可用资源(内存，高速缓存中的数据量等)
CPU数目
运算中的特定代数运算符。如A，B，C，D 4个表进行连接，每个表的单表扫描可以并行运算(数据分布式存储)。在生成4个表连接的查询计划过程中，可选择A和B连接的同时C和D连接，这样连接操作可以并行运行。不同的商业数据库，对查询并行的实现也不尽相同。在同一个SQL内，查询并行可以分为两种
操作内并行：将同一个操作如单表扫描，两表连接操作，排序操作等分解成多个独立的子操作，由不同的CPU同时执行。
操作间并行：一条SQL查询语句可以拆分为多个子操作，由多个CPU执行。
分布式询优化
在分布式数据库系统中，查询策略优化(主要是数据传输策略，A，B两节点的数据进行连接，是A节点的数据传输到B节点或从B到A或各自进行过滤后再传输等)和局部处理优化（传统的单节点的数据库查询优化技术）是查询优化的重点。
在查询优化策略中，数据的通信开销是优化算法考虑的主要因素。分布式查询优化以减少传输的次数和数据量作为查询的优化目标。所以分布式数据库系统中的代价估算模型，除了考虑CPU代价和IO代价外，还要考虑通过网络节点间数据传输的代价，这是分布式并行查询优化技术与传统单节点数据库系统最大的不同之处。
在分布式数据库系统中，代价估算模型的计算公式为：总代价 = IO代价 + CPU代价 + 通信代价
其他优化
数据库的查询性能还取决于一些其他因素，如数据库集群系统中SD(Share Disk)集群和SN(Share Nothing)集群和SM(share Memory)
SD:共享式存储方式，每个CPU使用自己私有磁盘
SN:非共享式存储方式，不存在集中存储，没有资源竞争，多用户访问，横向扩充资源，独立的内存，操作系统，磁盘
SM:多CPU共享一片内存，CPU之间通过内部通讯机制进行通讯
