如果說選一篇在優化器架構上，被引用次數最多的文獻，應該非這篇論文莫屬了，還記得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年間資料庫的發展産生了極為深遠的影響。