数据库系统发展历史

数据库系统产生于20世纪60年代中期，至今有近50多年的历史，其发展经历了三代演变，造就了四位图灵奖得主，发展成为一门计算机基础学科，带动了一个巨大的软件产业。

数据库系统是操作系统之上最重要的基础设施之一，被称为软件产业的常青树，特别是它所支撑起来的大数据、人工智能应用，更是发展迅猛。

面对发展快速的数据库领域，以及人类所拥有的数据量爆发式增长，如何对海量数据进行管理、分析、挖掘便变得尤为重要。SQL优化器正是为了解决以上问题而诞生的。

查询优化器简介

SQL优化器，其中最重要的一个组件是查询优化器，是数据库系统的重要组成部分。特别是对于现代大数据系统，执行计划的搜索空间异常庞大，研究人员研究了许多方法对执行计划空间进行裁剪，以减少搜索空间的代价。

在当今数据库系统领域，查询优化器可以说是必备组件，不管是关系型数据库系统Oracle、MySQL，流处理领域的Flink、Storm，批处理领域的Hive、Spark SQL，还是文本搜索领域的Elasticsearch等，都会内嵌一个查询优化器。

有的数据库系统会采用自研的优化器，而有的则会采用开源的查询优化器插件，比如Apache Calcite就是一个优秀的开源查询优化器插件。而像Oracle数据库的查询优化器，则是Oracle公司自研的一个核心组件，负责解析SQL，其目的是按照一定的原则来获取目标SQL在当前情形下执行的最高效执行路径。

这里拓展一下，关于查询优化器所要解决的核心问题：具有多个连接操作的复杂查询优化。不少学者相继提出了基于左线性树的查询优化算法、基于右线性树的查询优化算法、基于片段式右线性树的查询优化算法、基于浓密树的查询优化算法、基于操作森林的查询优化算法等。这些算法在搜索代价和最终获得的查询计划的效率之间有着不同的权衡。

总的来说，查询优化器在很大程度上决定了一个数据库系统的性能，优化器的作用就好比找到两点之间的最短路径。

RBO(Rule-Based Optimization)

RBO: Rule-Based Optimization也即“基于规则的优化器”，该优化器按照硬编码在数据库中的一系列规则来决定SQL的执行计划。

以Oracle数据库为例，RBO根据Oracle指定的优先顺序规则，对指定的表进行执行计划的选择。比如在规则中：索引的优先级大于全表扫描。

通过Oracle的这个例子我们可以感受到，在RBO中，有着一套严格的使用规则，只要你按照规则去写SQL语句，无论数据表中的内容怎样，也不会影响到你的“执行计划”，也就是说RBO对数据不“敏感”。这就要求开发人员非常了解RBO的各项细则，不熟悉规则的开发人员写出来的SQL性能可能非常差。

但在实际的过程中，数据的量级会严重影响同样SQL的性能，这也是RBO的缺陷所在。毕竟规则是死的，数据是变化的，所以RBO生成的执行计划往往是不可靠的，不是最优的。

CBO(Cost-Based Optimization)

CBO: Cost-Based Optimization也即“基于代价的优化器”，该优化器通过根据优化规则对关系表达式进行转换，生成多个执行计划，然后CBO会通过根据统计信息(Statistics)和代价模型(Cost Model)计算各种可能“执行计划”的“代价”，即COST，从中选用COST最低的执行方案，作为实际运行方案。

CBO依赖数据库对象的统计信息，统计信息的准确与否会影响CBO做出最优的选择。

以Oracle数据库为例，统计信息包括SQL执行路径的I/O、网络资源、CPU的使用情况。

目前各大数据库和大数据计算引擎都倾向于使用CBO，例如从Oracle 10g开始，Oracle已经彻底放弃RBO，转而使用CBO；而Hive在0.14版本中也引入了CBO。

参考文献

[1] 《数据库系统导论》(第5版) 王珊,萨师煊
[2] Oracle SQL优化器简介[https://www.cnblogs.com/mzq123/p/10398701.html]
[3] SQL优化器简介[https://www.cnblogs.com/jixin/p/10500096.html]
[4] 深入浅出Calcite与SQL CBO（Cost-Based Optimizer）优化[https://www.cnblogs.com/listenfwind/p/13192259.html]
[5] SQL优化器原理——查询优化器综述[https://zhuanlan.zhihu.com/p/40478975]