資料庫的語句編譯主要步驟：

  • 詞法分析/語法分析：建立查詢的分析樹；
  • 查詢計劃重寫：分析樹被轉化為初始查詢計劃（查詢的代數表達式），然後將查詢計劃轉化為一個預期執行時間較小的等價計劃；
  • 物理計劃生成與執行：將邏輯查詢計劃的每一個操作符選擇實現演算法並選擇這些操作符的執行順序，邏輯計劃被轉化為物理查詢計劃；然後將這些計劃應用到資料庫的數據上，得到並返回結果；

本文先將簡單介紹物理查詢計劃的執行（最後一階段），後續將介紹編譯的各個階段。

1. 物理計劃操作符

這裡介紹物理的一些基本操作類型，首先介紹以下表掃描相關的策略。

表掃描策略，即讀一個關係R的所有元組或滿足謂詞的元組，掃描的基本方法：

  • 表-掃描：掃描整表；
  • 索引-掃描：根據索引進行掃描；
  • 順序-掃描：內存排序，多路歸併排序；

1.1 基本操作

這裡將物理基本操作分成如下三類：

  • 一次單個元組，一元操作：不需要一次性裝入整個關係，甚至不需要關係的大部分，例如：選擇，投影。可以一次選擇一個塊，使用內存緩衝區，併產生輸出。
  • 整個關係，一元操作：一次從內存中看到所有或大部分元組，因此，一趟演算法侷限於大小為約為M（內存中可緩衝區的數量）或更小的關係。例如：分組操作符，去重操作符。
  • 整個關係，二元操作：其他操作類型，例如：並，交，差，連接和積的集合形式以及包形式。至少每一個關係都要求至少一個操作對象的大小限制在M以內。

2. 一趟演算法

這裡主要介紹基本操作符的一趟演算法和嵌套循環鏈接（Nested-Loop-Join）。

2.1 基本操作符的一趟演算法

一個操作對象數據較少，能夠一次性讀入內存。下面將對前面提到的三類操作符進行分別敘述。

1) 一次單個元組操作

將數據讀入緩衝區，然後執行一元操作，把數據寫入到緩衝區，最後輸出到指定位置。

2) 整個關係的一元操作

對於去重操作：為了去重，我們可以一次一個地讀取R的每一塊，然後對每一個元組，需要判斷：

(1). 第一次看到元組，將它複製到輸出；

(2). 以前見過這個元組，不必輸出它；

對於分組操作：在每一個元組創建一個項，根據具體分組操作進行執行：

(1). 對於MIN，MAX聚集來說，分別與當前值進行判斷，如果合適，則將結果修改為新的值；

(2). 對於任意COUNT聚集，每個元組加1；

(3). 對於SUM，如果不為NULL，則累加值加上屬性的值；

(4). AVG，需要記錄兩個欄位，SUM和COUNT；

3）二元操作

先將較小的關係讀入到內存中，並進行處理；然後再處理另一個關係；對於不同的操作，具體如下：

(1) 集合併：將S讀到內存的M-1個緩衝區中，並建立一個查找結構，然後將S複製到輸出；然後讀取R的每一個元組t，觀察t是否在S中，如果不在則複製t到輸出，否則跳過；

(2) 集合交：將S讀到M-1個緩衝區中，並建立關鍵字的查找結構；然後讀取R的每一個塊，並對R的每一個元組t，觀察t是否也在S中。如果在，則複製t到輸出，否則跳過；

(3) 集合差（S-R）：將S讀到內存並建立查找結構，然後讀取R的每一塊，並依次檢查每一個元組t，如果t在S中，那麼將t從S的內存中刪除。最後將S剩餘的元組複製到輸出；

(4) 包交：每一個不同元組有對應的計數，包交即按照對應元組的計數進行交集計算，例如，<(a, 3), (b,4)> 和<(a, 2), (b, 5)>，則包交為<(a,2),(b,4)>；計算方法為與集合交相似，只是在記錄中有計數器，然後根據計數器進行計算；

(5) 包差：包差與包交相對應，對於上例中，包差結果為：<(a, 1)>;

(6) 積：將S讀到內存中，然後讀取R的每一個塊，對於R中的每一個元組t，與內存中S的每一個元組連接，在每一個連接而成的元組一形成後將其輸出；

(7) 自然連接：R（X，Y）和S（Y，Z），讀取S的所有元組，並構造以Y的屬性為查找關鍵字的內存查找結構；讀R每一塊，利用R元組t中的Y屬性作為查找關鍵字在S中查找，在S中每一個匹配的元組，將它與t連接後形成一個元組，並將結果輸出。

2.2 嵌套循環鏈接

1) 基於元組的嵌套循環連接演算法

For S的每個元組s DO：
For R中的每個元組r DO：
IF r與s連接形成元組t THEN：
output t；

2) 基於塊的嵌套循環連接演算法

(1) 對作為操作對象的兩個關係的訪問均按塊組織；

(2)使用儘可能多的內存來存儲屬於關係S的元組，S是外層循環的關係；

For S中每一大小為M-1塊的chunk：
將這些塊讀入主存緩衝區中；
將其元組組織為查找結構，查找關鍵字是R和S的公共屬性；
For R的每個塊b：
將b讀入主存；
FOR 塊b的每一個元組t DO
找出s在主存中的元組中那些能與t連接的元組；
輸出t與這些元組中每一個的連接；

3. 兩趟演算法

數據量太大而無法裝入可利用的內存；可以採用多趟的演算法進行處理，這裡介紹兩趟演算法，更多趟的演算法與兩趟演算法基本上類似。這裡介紹一下三種演算法：

  • 基於排序的兩趟演算法；
  • 基於散列的兩趟演算法；
  • 基於索引的演算法；

3.1 基於排序的兩趟演算法

這裡先介紹兩階段歸併排序，然後利用排序進行對應的操作符操作。

3.1.1 兩階段多路歸併排序

下面是兩階段多路歸併的演算法：

階段1: 不斷將R中元組放到M個緩衝區，利用內存排序演算法對它們進行排序，並將排序結果存到外存中；
階段2: 將排好序的子表進行歸併：將M-1個有序子表進行歸併，執行以下操作：
1）找到所有子表中第一個元素的最小值；
2）將最小的元素移到輸出塊的第一個可用位置；
3）如果輸出塊已滿，則寫入到外存，並初始化輸出緩衝區；
4）如果剛被取出最小元素的緩衝塊的元素已耗盡，則將同一個有序子表中的下一個塊讀入到元素耗盡的緩衝塊。如果沒有塊，則不執行操作。

3.1.2 利用排序去重

在第二階段不斷地複製每一塊的第一個未考慮的元組t到輸出塊，並忽略與它相同的所有元組，同時將t拷貝到輸出塊，並將輸出塊中所有的t刪除。因此，輸出塊對R的任何一個元組都只有一個實例；且它們是有序的。

3.1.3 利用排序分組和聚集

具體演算法如下：

1）將R的元組每次讀取M塊到內存中，用L的元組屬性作為排序關鍵字，對每M塊進行排序，並將結果寫入到外存；
2）為每個子表使用一個主存緩衝區，並將每一個子表的第一塊裝入其緩衝區；
3）在緩衝區可以獲取的第一個元組反覆查找排序關鍵字（分組屬性）的最小值，這個最小值v成為下一分組，我們為它：
a）準備在這個分組的列表上計算所有聚集；
b）檢查每個排序關鍵字為v的元組，並累積所需聚集；
c）如果一個緩衝區空了，則用同一子表中的下一個塊替換它；

3.1.4 基於排序的並演算法

具體演算法如下：

1）創建R和S的排序子表；
2）為R和S的每一個子表使用一個內存緩衝區，用對應子表的第一塊初始化個緩衝區；
3）重複地在所有緩衝區中查找剩餘的第一個元組t，將t複製到輸出，並且從緩衝區中刪除t的所有副本。

3.1.5 基於排序的交和差演算法

基本演算法框架與並演算法類似，在處理時採取以下策略：

  • 對於集合交，如果t在R和S中都出現就輸出t；
  • 對於包交，輸出t的次數是R和S中出現次數的最小值，如果有一個次數為0，則不輸出；
  • 對於集合差，R-S，當且僅當t出現在R中但不出現在S中時，輸出t；
  • 對於包差，R-S，輸出t的次數是t在R中出現的次數減去在S中出現的次數，當R次數不大於S中的次數時，則不輸出；

3.1.6 基於排序的連接演算法

首先介紹一個簡單演算法，然後介紹一個較為有效的連接演算法。

1). 簡單演算法

(1) 用Y作為排序關鍵字，使用多路歸併演算法對S和R分別進行排序;
(2) 僅用兩個緩衝區，分別讀入S和R的最小緩衝塊，重複以下操作：
a） 在當前S和R的塊的前端查找連接屬性Y的最小值y；
b） 如果y在另一個關係的前部沒有出現，則刪除具有排序關鍵字y的元組；
c） 否則，找到兩個關係中具有排序關鍵字y的所有元組。如果需要從排序的R和/或S中讀取塊，直到確定每一個每一個關係都不再有y的元組；
d） 通過連接R和S中具有共同的y值的元組所能形成的所有元組；
e） 如果一個關係在內存中已沒有未考慮的元組，則重新載入緩衝區；

2). 更為有效的演算法

歸併（排序）-連接演算法。

1） 用Y作為排序關鍵字，為R和S創建大小為M的排序子表；
2） 將每一個子表的第一塊調進緩衝區，假設總共不超過M個子表；
3） 重複地在所有子表的第一個可以得到元組中查找最小的Y-值y。識別兩個關係中具有Y-值y的所有元組，輸出R和S中具有此公共Y-值所有元組的連接。

3.2 基於散列的兩趟演算法

首先將一個關係劃分到M-1個桶中：M-1個緩衝區，如果緩衝區滿，則寫入到磁碟。

3.2.1 基於散列的去重演算法

加入每個桶足夠小，而能夠裝入到內存，那麼基於散列的兩趟演算法就可行。基本思想就是對每一個桶單獨進行處理。

3.2.2 基於散列的分組和聚集演算法

將關係劃分成桶後，然後對每一個桶進行單獨的處理。

其他基於散列的演算法也類似，包括：基於散列的並，交，差，連接等演算法。

3.3 基於索引的演算法

本章節將將蛋介紹基於索引的相關演算法。

3.3.1 聚集和非聚集索引

如果一個關係的元組緊縮到能夠存儲的這些元組的儘可能少的塊中，那麼關係就是聚集的。

如果索引查詢關鍵字的一定固定值的所有元組都出現在能夠容納它們的儘可能少的塊中，那麼就是聚集索引。

3.3.2 基於索引的操作

主要介紹基於索引的選擇，連接等操作。

1） 基於索引的選擇

如果是聚集的，那麼有性能的優化，如果是非聚集的，仍需要讀取整表；

2） 基於索引的連接

對於S（X，Y）和R（Y，Z），分別在Y上建立索引。對於R中的每一個塊的每一個元組，根據S的Y索引進行查找，如果找到則輸出。

3） 使用有效索引連接

可以採用普通的排序連接，zig-zag連接，類似歸併方法。

4.多趟演算法

使用多趟的演算法可以在兩趟演算法基礎上進行擴展。

例如對於兩階段多路排序演算法，進行擴展：

1）基礎：如果R可以裝入M個塊中，那麼讀入內存，使用內存排序，並將排序結果寫入內存；
2）歸納：如果R不能夠裝入內存，將R的塊分成M個組，稱作R1，R2，...，R3。對每個i=1，2，...，M，遞歸排序。然後將M個排序的子表合併。

5. 緩衝區管理策略

1）最近最少使用（LRU）：丟出最長時間內沒有讀或寫的塊；

2）先進先出（FIFO）：被同一個塊佔用時間最長的緩衝區被清空；

3）「時鐘」演算法（第二次機會）：每個緩衝區有一個標誌（0或1），當一個塊被讀入或訪問後，置為1；如果需要新的緩衝區時，按照順時針旋轉，查找到第一個為0的塊，如果標誌時1，則設為0；

4）系統控制：使用強制方式保護一些數據塊；

6. 總結

本文主要介紹資料庫中物理計劃執行，介紹了數據量較小的一趟演算法，數據量較大的兩趟演算法和多趟演算法，最後介紹了緩衝區管理的策略。

參考文章/書本：

  • 《資料庫系統基礎教程》
  • 《資料庫系統實現》
  • 《資料庫系統概念》

推薦閱讀：

相關文章