如果说选一篇在优化器框架上，被引用次数最多的文献，应该非这篇论文莫属了，还记得Andy Pavlo在cmu的课程中提到IBM Research的一群大神们，是怎么一人一个模块来负责System R的设计的，而关于Join order enumeration，Selinger可以说是开创了dynamic programing based 的bottom-up的搜索空间算法的先河，直至今日，很多成熟的商业或开源数据库系统仍在沿用这套框架，比如Oracle / DB2 / PostgreSQL ...
最优化理论
众所周知，在广阔的plan space中寻找最优解是一个NP-hard问题，如果不采用某种特定的search路径或策略，其成本是无法接受的，而动态规划就提供了这样一个策略。
从本质上，动态规划基于成本最优假设（在最优的方案当中，取局部结构来看其方案也是最优的），将寻找全局最优解的问题分解为了对于局部最优解的迭代，不断通过子问题的局部最优，获取更大问题的局部最优，直到全局。
这里所谓的局部最优解，落到关系代数的表述方式上，就是指在当前的join子树上，获取到的已知最优结果，需要将其和计算的cost进行缓存，供子树的上层（也就是父问题）继续迭代。
看起来问题并不复杂，但对于join这样的关系代数运算来说，由于可能存在不同的执行方式（hash join/sort merge/NestLoop ...)，下一层子树的输出的特性不同，对于上一层join执行的cost会产生不同的影响，比如如下子树：
假设由于t2表很小，在考虑第一个join时，可能有左右两图中的两种选择，而基于最优原则，在下层的小子树上，我们选择了in-memory hash join，但当迭代到上一层的join node时，由于sort merge join对于两侧的input有顺序要求，因此也许在考虑下层join时，选用sort merge join可以保留住t2.a上的有序性，从而避免了对hash join结果的排序操作而代价更低。
从以上的例子可以看到，局部最优解是有前提条件的，理论上，带有不同输出特性的子问题，被划分到不同的等价类中，属于不同的局部问题，因此应该各自维护最优解，这些局部最优解的集合都可以传递到上层以供后续迭代，这样动态规划的问题就不再是一个线性的迭代，而是自底向上，树形展开的迭代过程。
Paper
有了以上的基本概念，再去理解System-R对于join ordering的处理就相对简单了，上文所提到的每个join node的输出特性，就是描述join之后数据所具有的某种物理属性，在System-R中，这种物理属性是数据的有序性，称为Interesting Order。
当然这篇paper不止是join ordering，也包含单表access path的选择，cost计算，selectivity估算等，下面一一详述。
整体框架
整体框架包含以下4个组件:
-
Parser
通过yacc解析，生成基本的Parse tree
-
Optimizer
-
从Catalog中读取元数据+统计信息，先做语义检查
-
确定各个query block的求值顺序，对每个query block，计算cost并生成最优plan, plan使用ASL语言进行描述
-
将ASL语言 -> machine code，对外暴露为一个函数，其中每个嵌套query block plan，都是一个子函数
-
Executor
执行machine code，过程中会调用RSI(Relational Storage Interface)接口，访问RSS存储层获取数据，RSI接口是OPEN -> NEXT -> CLOSE的方式，每次获取一个tuple。
-
RSS （Relational Storage System）
-
按page组织tuple数据，分为data page/index page，tuple不跨page，page逻辑上组成segment，一个segment可包含多个relation的page，relation不跨segment。
-
一个Page中可能包含多表的tuple。
优化流程
先给出示例用的SQL语句和schema：
SELECT NAME,TITLE,SAL,DNAME FROM EMP,DEPT,JOB WHERE TITLE=‘CLERK’ AND LOC=‘DENVER’ AND EMP.DNO=DEPT.DNO AND EMP.JOB=JOB.JOB
整个过程是自底向上的，因此遵从单表 -> 两表 -> 三表... 的顺序，我们依次来看：
-
单表access path选择
单表cost是两表join cost的基础，cost中包含IO + CPU两部分
pages fetched是IO部分，包含index page + data page的读取代价
RSICALL是进入RSS层的次数，正比于cpu的计算量，也就是 的乘积，即返回上层的tuple数。
W 是权重比例，描述IO和cpu的成本权重。
Cost的计算要利用统计信息和选择率：
统计信息
Relation : NCARD（tuple数量），TCARD(data page数量)，P（page占segment比例）
Index : NDV(index key的NDV), NINDX(index page数量)
以上信息可以从System catalog中获取
选择率
，表示在scan时能够满足谓词的数据行比例，不同谓词具有不同的计算公式：
1) column = value
有索引： 无索引
2) column1 = column2
两边都有索引：
一边有索引：
无索引 :
3) column > value or column between value1 AND value2
属于range scan，对于有索引，且是数值类型的，假设均匀分布，
4) column IN list(...)
假设所有value分布相同，使用list value个数 * 每个value的选择率
5) 不同谓词的逻辑组合AND/OR/NOT，基于谓词间独立性假设进行计算
由以上情况，可以计算出任意predicate的selectivity。
综上，可以看到Cost受到Cardinality + Selectivity的影响，由对应谓词和统计信息一起决定。最终单表的优化结果是 Cardinality + Interesting order + access cost 三个维度，结合示例中的SQL:
上图中，每个表右侧的一条竖线，代表一种access path，线的上方是访问方式(index scan / segment scan），下方是产生的Cardinality + Cost + Interesting Order。假设后续join对DEPT和JOB的输出Interesting Order要求是DNO和JOB，以DEPT为例，第二种access path不产生order且其cost已经比第一种要大，这里可以直接prune掉。
-
两表join
在选择join order时有两个基本的启发规则：
-
只考虑左深树的join tree形态，在System-R那个年代，内存和CPU还非常原始，采用这种策略来限制搜索空间非常明智，既可以极大的减少空间膨胀，也可以选出足够优的计划。
-
在选择下一个inner table时，总是选择和已选择的join tables有join条件的，尽量把笛卡尔积的计算放到最后，这也是比较符合直觉的，笛卡尔积会导致中间结果爆炸，因此拖到最后一般来说是影响最小的。（HyPer中对于join order的新DP算法中，仍然延续了这样的假设）
扩展到多表时，可以先看一下Search tree的概念，先给出2个直观的图：
结合Figure 2中的单表的access path选择，形成如上单表的search tree，中间节点层代表了访问的单表，而其下的一条到leaf node的边，则表示了单表的可能访问方式。比如EMP下面的两条边，分别对应Index EMP.DNO的访问方式和Index EMP.JOB的访问方式，因此在leaf node上产生的Interesting Order也有所不同。
再将两个表组合起来
这个图看起来很复杂，但从root节点出发只关注任一条到leaf节点的路径，就对应着一种两表join的特定组合方式，以最左侧路径为例：
(EMP,DEPT）中间节点代表了这两个表的组合，其向下延伸的第一条边是Index EMP.DNO，表示用index scan的方式访问EMP表，而再下一条边是Index DEPT.DNO，表示用index scan方式访问DEPT表，由此到达leaf node，这样就形成了两表的一种Join组合，产生了特定的(Cost + Cardinality + Interesting Order）的组合，每一条root -> leaf的边都代表这样的一种join组合。
在leaf level的各种join组合枚举完后，对每个等价类（相同table set+相同interesting order）内，选出一个最优方案，prune掉等价类内其他分支。
join cost计算和join的物理算法有关
1）NestLoop Join
N是所有join prefix产生的Cardinality，可以用所有prefix table的Cardinality乘积 * 所有已apply谓词(连接/过滤)选择率的乘积来计算
每个C-都是单表的access cost。
现在MySQL在做join cost的计算时，依然沿用这个公式。
2）Sort Merge Join
总结
System R针对join ordering问题，开创性的使用基于动态规划的方法，结合Interesting Order形成等价类的方式，来对search space进行高效搜索。不仅如此，其对于selectivity的计算，cost的计算方式，影响非常深远，相信早期的商业数据库大多采用类似的代价估算方式(MySQL直至今日仍然如此）。对后续30年间数据库的发展产生了极为深远的影响。