查询优化器是数据库中比较难懂的部分，其它的还有事务处理，尤其是融合了隔离级别以及不同的锁、MVCC 实现之后。
简介
SQL 是一个声明式的语言，其标明了需要什么样的结果，但并未告知如何执行，而且随着大数据、OLAP、异构、Stream、Graph 等的出现，对优化器提出了新的挑战。
优化算法分成了：Rule Based Optimizer, RBO 基于规则的优化器、Cost Based Optimizer, CBO 基于成本的优化器、Heuristic Based Optimizer, HBO 启发式优化器。相比单纯的 RBO 来说 CBO 可以实时的根据 CPU、IO、Net 等代价进行优化。
历史
基本上从 1979 年 Selinger 发布的 Access Path Selection 开启了 CBO 时代，后面有又陆续出现了 Starburst (1988)、Volcano (1993)、Cascades (1995) 等等，每年数据库三大会也有很多优化器相关论文。
优化器很大的问题是搜索空间的指数级放大，从而导致当前大部分的实现都是启发式算法，进而可能导致执行计划并非最优的。而且，对 CBO 来说，底层的 Scan 算子如何快速更新统计信息，降低上层算子的失真。
而且，还有核心点，如何保证优化器的稳定性。
基本概念
Cardinality VS. Selectivity
Cardinality 基数，表示表中 Unique 行数，可以通过 Distinct() 函数查询，例如 示例数据库 中可以通过 SELECT COUNT(DISTINCT(deptno)) FROM employee; 查询。
Selectivity 选择率，通常指查询会从表中返回多大比例的数据，也可以通过 Cardinality/TotalRows 表示，选择率越高那么索引就越有效，例如上述的 deptno 相比 gender 要更加有效，可以过滤更多数据。
Logical VS. Physical
当 SQL 转换为关系代数的表达式树之后，可以看到各个节点的先后执行顺序，也就是逻辑执行计划，但是此时还不确定具体如何执行，例如 Join 可能有 NestedLoop Join、Hash Join、SortMerge Join 等，Scan 可能有 Index Scan、Seq Scan 等。
通常将执行树中的各个节点称为 Operator ，可以是逻辑的也可以是物理的，在转换过程中，习惯通过如下方式描述：
Exploration/Transformation产生等价的逻辑计划，通常是基于规则的实现。Implementation将逻辑计划转换为对应的物理计划，如上，一个逻辑执行计划可能会对应多个物理执行计划。
BottomUp VS. TopDown
目前比较常用的两种优化器搜索策略：
BottomUp Dynamic Programming从零开始，由下往上遍历计划树，找到完整的执行计划，包括 SystemR、PostgreSQL、DB2 等。TopDown Memorization从目标开始，由上往下遍历计划树找到最优计划，包括 Cascades、SQLServer 等。
其中 TopDown 方式可以方便作等价转换，而且方便进行剪枝操作，而 BottomUp 因为无法确定父节点属性，需要枚举各种可能的输出。相对来说，TopDown 搜索空间更大、耗时高，通常用于 AP 系统上；在 TP 系统上需要 FastPath 或者提前结束搜索。
Cascades
Volcano/Cascades 是经典的优化器框架，分别产自论文 The Volcano Optimizer Generator 以及 The Cascades Framework for Query Optimization，两篇的主要作者都是 Goetz Graefe，后者是对前者的优化，核心提出了 Memo 缓存历史信息，从而减少重复搜索。
当前很多数据库采用该模型，例如 Greenplum Orca、Apache Calcite、CockroachDB、TiDB 等等。
Pattern Rule
包括了 Heuristic (RBO) 和 Cascades (CBO) 两类，会通过 Pattern 匹配树，然后通过 Rule 转换为新的节点。
Memo
Property
任务调度
优化器的搜索过程本质上递归的动态规划，是 CPU 密集型任务，核心是易扩展、多核调度。
将不同类型封装为 Task ，然后进行调度，其中 Orca 提供了并行能力，不过当前大部分是串行能力。
统计信息
在基于 CBO 的改写和转换阶段，会生成多个物理执行计划，会通过估算每个算子的执行代价 (CPU、内存、网络、IO 等)，选择代价最低的一条路径作为最终物理查询计划。
统计信息是 CBO 的重要组成部分，统计信息是否准确决定了代价估算是否准确，对于 CBO 选择最优 Plan 至关重要，进而决定了 CBO 优化器的性能好坏。
egg
全称是 E-Graph Good，基于 E-Graph 理论实现的库，可用于简化表达式，更多的可以参考 官网 的介绍。以官方的示例为例，由三部分组成：
e-node对应每个独立节点，可以是变量、常量、操作符。e-class由多个e-node组成，其语义等价，可以相互替换。e-graph就是整体的了。
RisingLight 实验性质的 OLAP 引擎，其优化器基于 EGG 实现。