数据库查询优化器
所谓查询优化，目标是关系数据库下或者 newSQL 的 SQL Server 层对 SQL 语句进行优化，在不改变期望结果的情况下使得数据库引擎计划执行时间最短。狭义的查询优化技术是指逻辑优化与物理优化（在后面会细讲），广义上的查询优化技术包括从 SQL 语句输入开始，对 SQL 语句的重写，内部执行算法的优化，并行优化及分布式条件下的优化，还包括了外部缓存机制对于查询计划及查询结果的重用。
查询优化技术是数据库领域十分重要的技术，尤其在当前业务数据及业务请求规模不断增长的情况下显得尤为重要。这里从狭义的查询优化技术入手，从宏观上讲述查询优化器的架构及各个模块实现的主要功能任务，希望能够对大家了解及理解查询优化器有所帮助。
架构
SQL 语句经过语法分析器生成语法分析树，再通过查询优化器生成查询树及查询计划，最后交由执行器执行。
架构图
语法分析器
语法分析
语法分析是指对用户输入的 SQL 语句进行判断，纠正拼写错误及语法错误。如：
Select name, class_name
from student S, course C, sc SC
where S.sno = SC.sno and C.cno = SC.cno and C.cno = 22;
如果关键词如 Select 拼写错误，或者语句不符合 Select_From_Where 语法规范，将在此步骤检测出来。
语义检查
语义检测负责判断 SQL 语句中涉及的表及表中的属性列是否存在，如果 SQL 所操作的目标表或者属性列完全不存在那么后期的优化也是徒劳无果的。比如在上面的 SQL 例子中，将会判断以下存储对象或元数据是否存在。
属性列： name, class_name
相关表： student, course, sc
查询优化器
逻辑优化
逻辑优化简单来说就是根据关系代数的等价变换规则进行查询重写。首先传统关系代数运算符有并、交、差、积，对于 SQL 语句来说，专有运算符有选择、投影、连接、除。首先传统运算符在 SQL 语句中的体现为：
- 并 - union
Select * from R union Select * from S
- 交 - not in(not in)
Select * from R where kr not in (
Select kr from R where kr not in (
Select ks from S))
- 差 - not in
Select * from R where kr not in (Select ks from S)
- 积 - 无条件join
Select R.* , S.* from R , S
专有运算符的 SQL 表现：
- 选择 - condition
Select * from R where condition
- 投影 - 属性列
Select col_1,col_2+2 from R
- 连接 - condition 中 join 或者等值连接
Select r.col_1,s.col_2 from R,S where condition
- 除 - not exists(not exists)
Select Distinct r1.x from R,r1 where not exists (
Select S.y from S Where not exists (
Select * from R r2 where r2.x=r1.x and r2.y=S.y))
有了上述的运算符对应关系， SQL 语句就可以使用关系代数的等价变换进行优化。这里有一些例子：
逻辑优化举例
物理优化
物理优化是与实际存储相关的优化阶段。简单来说就是通过代价模型对表级操作算法的选择。
首先介绍代价模型，学过计算机系统结构的同学都知道，衡量计算机性能的重要指标就是相同任务或者指令的执行时间。那么与之相似，一个执行计划的优劣程度也可以使用时间来衡量。当然，数据库查询优化的目标也是在尽可能短的时间返回期望的结果。所以代价模型的宏观表达式为：总代价 = IO代价 + CPU代价
说回表级操作算法，这里有以下3类：
- 单表 ---> 扫描方式 ： 全表扫描、索引扫描
- 两表 ---> 连接方式 ： 嵌套循环连接、归并连接、哈希连接
- 多表 ---> 连接顺序 ： 动态规划、启发式、贪心、System R、遗传算法
单表扫描
单表扫描的选择主要通过选择率来判断，也就是满足条件的元组数（表中一行数据）占总元组数的比例。同时在许多文章中，这里满足条件的元祖数也称为基数，有: 选择率 = 基数 / 总元组数。
比如在条件筛选过后可能只有 1/1000 的元组被选到，那么通过索引扫描的方式访问整个表是很快的，但如果有 999/1000 的数据将会被筛选出来，那么通过全表扫描的方式或许更加有效。
两表连接
传统的两表连接方法有嵌套循环连接、归并连接及哈希连接。
- 嵌套循环连接 ： 相当于两个for循环，使用 A 表的一个元组去匹配 B 表的每一个元组，直到 A 表的所有元组都被访问完全。
- 归并连接 ： 先将 B 表按照匹配的属性列排序，然后使用 A 表的每一个元组匹配 B 表的元组，一旦出现不匹配的情况下那么直接开始下一轮循环匹配（因为排过序，后续的元组也将不匹配）。
- 哈希连接 ： 先将 A 表所有元组对应属性列 hash ，然后将 B 表的每个元组对应属性列使用相同的散列方法 hash，若值相等则匹配。
多表连接顺序
多表下是对各个表的连接顺序进行选择，比如 A、B、C 三个表，A、B 较大，C 较小，那么 AB 先连接可能产生的中间结果会比较大， 采用 BC-A 的连接顺序可能先得到的中间结果就会比较小，既节省计算资源又节省存储空间。常见的多表连接顺序的选择算法有动态规划、启发式、贪心、System R、遗传算法。PostgreSQl 中使用的算法为动态规划及遗传算法。
分布式查询优化
与单机的查询优化不同，分布式情况下目标数据可能分布在不同的节点上。因此对于代价模型来说，还需要加上数据传输的代价。同时由于分布式环境的复杂性，还要考虑到数据副本及底层数据库引擎异构（如关系型与 NoSQL ）和异制（数据模型及数据结构不相同，比如文件型及 KV）的问题。
分布式环境下如果两个要连接的表（A、B）在不同的节点上，这样的情况下有两种基本的连接算法：
- 直接连接：直接将 B 表整个传输到 A 表所在节点进行连接计算
- 半连接：只是将 B 表要连接的属性列传输到 A 表所在节点进行连接计算，计算完毕后传输回 B 表的节点筛选出匹配完成的元组
很明显，直接连接不适合目标表非常大的情况，但是半连接传输的次数较多。
最后
以上旨在帮助大家宏观认识数据库查询优化器，对查询优化器架构及各个模块功能有大体认识。
以下是几篇相关的经典论文：
