小明考上了北清大学的计算机研究生，今年学校开了数据库原理的课程，小明对查询优化的部分不是很理解，虽然已经使出了洪荒之力，仍然觉得其中的部分原理有些晦涩难懂，于是小明打算问一下自己的哥哥大明，大明是一位资深的数据库内核开发的老码农，对Greenplum/HAWQ数据库有多年的内核开发经验，厚厚眼镜片上的圈圈像年轮一样深深的见证着大明十多年的从业经历，知道小明要来问问题，大明有点紧张，虽然自己做数据库内核好多年了，但是对优化器研究却不深入，如果被小明这样的小菜鸟问倒就尴尬了，于是大明只好临时抱佛脚，拿出了好多年不看的《数据库系统实现》啃了起来。
小明提出的第一个问题是：“为什么数据库要进行查询优化？”
大明推了推鼻梁上的眼镜，点上了一根中华深吸一口，火红的烟头奋力燃烧，由明及暗，几片烟灰飘飘渺渺的散落下来，又和大明吐出的云雾交缠在一起，即轻盈又律动，大明弹了弹烟灰，慢条斯理的说：“不止是数据库要进行优化，基本上所有的编程语言在编译的时候都会优化，比如你在编译C语言的时候，可以通过编译选项-o来指定进行哪个级别的优化，但是查询数据库的查询优化和C语言的优化还有些区别。”
“有哪些区别呢？”大明停顿了一下，凝视着小明，仿佛期望小明给出答案，或者是给小明腾挪出足够思考的空间，三五秒之后大明又自问自答道：“C语言是过程化语言，你已经指定好了需要执行的每一个步骤，但是SQL是描述性语言，它只指定了WHAT，而没有指定HOW，这样它的优化空间就大了，你说是不是？”
小明点了点头说：“对，也就是说条条大路通罗马，它比过程语言的选择更多，是不是这样？”大明笑道：“孺子可教也。虽然我们知道它的优化空间大，但具体如何优化呢？”
说着大明将身子向沙发里靠以靠，翘上二郎腿继续说：“通常来说分成两个层面，一个是基于规则的优化，另一个是基于代价的优化，基于规则的优化也可以叫逻辑优化或者规则优化，基于代价的优化也可以叫物理优化或者代价优化。”大明边说边用手比划着，手里的烟火也欢快的跳跃着。
“那为什么要进行这样的区分呢？优化就优化嘛，何必还分什么规则和代价呢？”，小明问道。
“分层不分层不是重点，有些优化器层次分的清楚点，有些优化器层次分的就不那么清楚，都只是优化手段而已。”大明感到有点心虚，再这么问下去恐怕要被问住，于是试图引开话题：“我们继续说说SQL语言吧，我们说它是一种介于关系演算和关系代数之间的语言，关系演算和关系代数你看过吧？”
小明想了想，好像自己上课的时候老师说过关系代数，但是没有说关系演算，于是说：“接触过一点，但也不是特别明白。”大明得意的说：“关系演算是纯描述性的语言，而关系代数呢，则包含了一些基本的关系操作，SQL主要借鉴的是关系演算，也包含了关系代数的一部分特点。”
大明看小明有点懵，顿了一下，然后继续说道：“你们上课的时候老师有没有说过关系代数的基本操作？”小明想了一下说：“好像说了，有投影、选择、连接、交集、差集这几个。”大明点点头说：“对的，还可以有一个叫重命名的，一共6个基本操作，另外结合实际应用在这些基本操作之上又扩展出了外连接、半连接、聚集操作、分组操作等等。”
大明又深吸了一口烟，优雅的吐了个烟圈，继续说道：“SQL语句虽然是描述性的，但是我们可以把它转化成一个关系代数表达式，而关系代数中呢，又有一些等价的规则，这样我们就能结合这些等价规则对关系代数表达式进行等价的转换。”
“进行等价转换的目的是找到性能更好的代数表达式吧？”小明问。
“对，就是这样。”大明投来赞许的目光。
“那么如何确定等价变换之后的表达式就能变得比变换之前性能更好呢？或者说为什么我们要进行这样的等价变换，而不是使用原来的表达式呢？”
大明愣了一下，仿佛没有想到小明会提出这样的问题，但是基于自己多年的忽悠经验，他定了定神，回答道：“这既有经验的成分，也有量化的考虑。例如将选择操作下推，就能优先过滤数据，那么表达式的上层计算结点就能降低计算量，因此很容易可以知道是能降低代价的。再例如我们通常会对相关的子查询进行提升，这是因为如果不提升这种子查询，那么它执行的时候就会产生一个嵌套循环，这种嵌套循环的执行代价是O(N^2)，这种复杂度已经是最坏的情况了，提升上来至少不会比它差，因此提升上来是有价值的。”大明心里对自己的临危不乱暗暗点了个赞。
大明看小明没有提问，继续说道：“这些基于关系代数等价规则做等价变换的优化，就是基于规则的优化，当然数据库本身也会结合实际的经验，产生一些优化规则，比如外连接消除，因为外连接优化起来不太方便，如果能把它消除掉，我们就有了更大的优化空间，这些统统都是基于规则的优化。同时这些都是建立在逻辑操作符上的优化，这也是为什么基于规则的优化也叫做逻辑优化。”
小明想了想，自己好像对逻辑操作符不太理解，连忙问：“逻辑操作符是啥？既然有物理优化，难道还有物理操作符吗？”
大明看自己的烟已经烧的只剩下过滤嘴了，连忙把烟头扔到烟灰缸，伸个懒腰继续说：“比如说吧，你在SQL语句里写上了两个表要做一个左外连接，那么数据库怎么来做这个左外连接呢？”
小明一头雾水的摇摇头，对大明投出了期待的眼神。
大明自问自答的继续说道：“数据库说我也不知道啊，你说的左外连接意思我懂，但我也不知道怎么实现啊？你需要告诉我实现方法啊，因此优化器还承担了一个任务，就是告诉执行器，怎么来实现一个左外连接。”
大明一边说，一边从茶几上把烟拿起来，准备再抽一根，却尴尬的发现，烟盒里一根烟都没有了，大明把空烟盒弹进垃圾桶，继续说：“数据库有哪些方法来实现一个左外连接呢？它可以用嵌套循环连接、哈希连接、归并连接等等，注意了，重要的事情说三遍，你看内连接、外连接是连接操作，嵌套循环连接、归并连接等也叫连接，但内连接、外连接这些就是逻辑操作符，而嵌套循环连接、归并连接这些就是物理操作符。所以你说对了，物理优化就是建立在物理操作符上的优化。”
大明又问小明：“你要从北京去上海，你说你怎么去？”
小明说：“坐高铁啊，又快又方便。”
大明继续问：“做高铁先去广州，然后倒车到上海行不行？”
小明说：“有点扎心了，这不是吃饱了撑的吗？”
大明追问：“为什么？”
小明说：“很明显，我有直达的高铁，即节省时间，又节省费用，先去广州再倒车？我脑子瓦特了？！”
大明笑了笑说：“不知不觉之间，你的大脑就建立了一个代价模型，那就是性价比，优化器作为数据库的大脑，也需要建立代价模型，对物理操作符计算代价，然后筛选出最优的物理操作符来，因此基于代价的优化是建立在物理操作符上的优化，所以也叫物理优化。”
小明觉得似乎懂了：“公司派我去上海出差就是一个逻辑操作符，它和我们写一个SQL语句要求数据库对两个表做左外连接类似，而去上海的实际路径有很多种，这些就像是物理操作符，我们对这些实际的物理路径计算代价之后，就可以选出来最好的路径了。”
大明掏出手机，分别打开了白兔地图APP和高达地图APP，输入了北京到上海的信息，然后拿给小明看，小明发现两家APP给出的最优路径是不一样的。小明若有所思的说：“看来代价模型很重要，代价模型是不是准确决定了最优路径选择的是不是准确。”
大明一拍大腿，笑着说：“太对了，所以我作为一个数据库内核的资深开发人员，需要不断的调整优化器的代价模型，以期望获得一个相对稳定的代价模型，不过仍然是任重道远啊。”