一提到關系型資料庫，我禁不住想：有些東西被忽視了。關系型資料庫無處不在，而且種類繁多，從小巧實用的 SQLite 到強大的 Teradata 。但很少有文章講解資料庫是如何工作的。你可以自己谷歌/百度一下『關系型資料庫原理』，看看結果多麼的稀少【譯者注：百度為您找到相關結果約1,850,000個…】 ，而且找到的那些文章都很短。現在如果你查找最近時髦的技術（大資料、NoSQL或JavaScript），你能找到更多深入探讨它們如何工作的文章。
難道關系型資料庫已經太古老太無趣，除了大學教材、研究文獻和書籍以外，沒人願意講了嗎？
作為一個開發人員，我不喜歡用我不明白的東西。而且，資料庫已經使用了40年之久，一定有理由的。多年以來，我花了成百上千個小時來真正領會這些我每天都在用的、古怪的黑盒子。關系型資料庫非常有趣，因為它們是基于實用而且可複用的概念。如果你對了解一個資料庫感興趣，但是從未有時間或意願來刻苦鑽研這個内容廣泛的課題，你應該喜歡這篇文章。
雖然本文标題很明确，但我的目的并不是講如何使用資料庫。是以，你應該已經掌握怎麼寫一個簡單的 join query（聯接查詢）和CRUD操作（建立讀取更新删除），否則你可能無法了解本文。這是唯一需要你了解的，其他的由我來講解。
我會從一些計算機科學方面的知識談起，比如時間複雜度。我知道有些人讨厭這個概念，但是沒有它你就不能了解資料庫内部的巧妙之處。由于這是個很大的話題，我将集中探讨我認為必要的内容：資料庫處理SQL查詢的方式。我僅僅介紹資料庫背後的基本概念，以便在讀完本文後你會對底層到底發生了什麼有個很好的了解。
【譯者注：關于時間複雜度。計算機科學中，算法的時間複雜度是一個函數，它定量描述了該算法的運作時間。如果不了解這個概念建議先看看維基或百度百科，對于了解文章下面的内容很有幫助】
由于本文是個長篇技術文章，涉及到很多算法和資料結構知識，你盡可以慢慢讀。有些概念比較難懂，你可以跳過，不影響了解整體内容。
這篇文章大約分為3個部分：
底層和上層資料庫元件概況
查詢優化過程概況
事務和緩沖池管理概況
很久很久以前（在一個遙遠而又遙遠的星系……)，開發者必須确切地知道他們的代碼需要多少次運算。他們把算法和資料結構牢記于心，因為他們的計算機運作緩慢，無法承受對CPU和記憶體的浪費。
在這一部分，我将提醒大家一些這類的概念，因為它們對了解資料庫至關重要。我還會介紹資料庫索引的概念。
O(1) vs O(n^2)
現今很多開發者不關心時間複雜度……他們是對的。
但是當你應對大量的資料（我說的可不隻是成千上萬哈）或者你要争取毫秒級操作，那麼了解這個概念就很關鍵了。而且你猜怎麼着，資料庫要同時處理這兩種情景！我不會占用你太長時間，隻要你能明白這一點就夠了。這個概念在下文會幫助我們了解什麼是基于成本的優化。
時間複雜度用來檢驗某個算法處理一定量的資料要花多長時間。為了描述這個複雜度，計算機科學家使用數學上的『簡明解釋算法中的大O符号』。這個表示法用一個函數來描述算法處理給定的資料需要多少次運算。
比如，當我說『這個算法是适用 O(某函數())』，我的意思是對于某些資料，這個算法需要 某函數(資料量) 次運算來完成。
重要的不是資料量，而是當資料量增加時運算如何增加。時間複雜度不會給出确切的運算次數，但是給出的是一種理念。
圖中可以看到不同類型的複雜度的演變過程，我用了對數尺來建這個圖。具體點兒說，資料量以很快的速度從1條增長到10億條。我們可得到如下結論：
綠：O(1)或者叫常數階複雜度，保持為常數（要不人家就不會叫常數階複雜度了）。
紅：O(log(n))對數階複雜度，即使在十億級資料量時也很低。
粉：最糟糕的複雜度是 O(n^2)，平方階複雜度，運算數快速膨脹。
黑和藍：另外兩種複雜度（的運算數也是）快速增長。
資料量低時，O(1) 和 O(n^2)的差別可以忽略不計。比如，你有個算法要處理2000條元素。
O(1) 算法會消耗 1 次運算
O(log(n)) 算法會消耗 7 次運算
O(n) 算法會消耗 2000 次運算
O(n*log(n)) 算法會消耗 14,000 次運算
O(n^2) 算法會消耗 4,000,000 次運算
O(1) 和 O(n^2) 的差別似乎很大（4百萬）,但你最多損失 2 毫秒，隻是一眨眼的功夫。确實，當今處理器每秒可處理上億次的運算。這就是為什麼性能和優化在很多IT項目中不是問題。
我說過，面臨海量資料的時候，了解這個概念依然很重要。如果這一次算法需要處理 1,000,000 條元素（這對資料庫來說也不算大）。
O(1) 算法會消耗 1 次運算
O(log(n)) 算法會消耗 14 次運算
O(n) 算法會消耗 1,000,000 次運算
O(n*log(n)) 算法會消耗 14,000,000 次運算
O(n^2) 算法會消耗 1,000,000,000,000 次運算
我沒有具體算過，但我要說，用O(n^2) 算法的話你有時間喝杯咖啡（甚至再續一杯！）。如果在資料量後面加個0，那你就可以去睡大覺了。
為了讓你能明白
搜尋一個好的哈希表會得到 O(1) 複雜度
搜尋一個均衡的樹會得到 O(log(n)) 複雜度
搜尋一個陣列會得到 O(n) 複雜度
最好的排序算法具有 O(n*log(n)) 複雜度
糟糕的排序算法具有 O(n^2) 複雜度
注：在接下來的部分，我們将會研究這些算法和資料結構。
有多種類型的時間複雜度
一般情況場景
最佳情況場景
最差情況場景
時間複雜度經常處于最差情況場景。
這裡我隻探讨時間複雜度，但複雜度還包括：
算法的記憶體消耗
算法的磁盤 I/O 消耗
當然還有比 n^2 更糟糕的複雜度，比如：
n^4：差勁！我将要提到的一些算法具備這種複雜度。
3^n：更差勁！本文中間部分研究的一些算法中有一個具備這種複雜度（而且在很多資料庫中還真的使用了）。
階乘 n：你永遠得不到結果，即便在少量資料的情況下。
n^n：如果你發展到這種複雜度了，那你應該問問自己IT是不是你的菜。
注：我并沒有給出『大O表示法』的真正定義，隻是利用這個概念。可以看看維基百科上的這篇文章。
當你要對一個集合排序時你怎麼做？什麼？調用 sort() 函數……好吧，算你對了……但是對于資料庫，你需要了解這個 sort() 函數的工作原理。
優秀的排序算法有好幾個，我側重于最重要的一種：合并排序。你現在可能還不了解資料排序有什麼用，但看完查詢優化部分後你就會知道了。再者，合并排序有助于我們以後了解資料庫常見的聯接操作，即合并聯接 。
與很多有用的算法類似，合并排序基于這樣一個技巧：将 2 個大小為 N/2 的已排序序列合并為一個 N 元素已排序序列僅需要 N 次操作。這個方法叫做合并。
我們用個簡單的例子來看看這是什麼意思：
通過此圖你可以看到，在 2 個 4元素序列裡你隻需要疊代一次，就能建構最終的8元素已排序序列，因為兩個4元素序列已經排好序了：
1) 在兩個序列中，比較目前元素（目前=頭一次出現的第一個）
2) 然後取出最小的元素放進8元素序列中
3) 找到（兩個）序列的下一個元素，(比較後)取出最小的
重複1、2、3步驟，直到其中一個序列中的最後一個元素
然後取出另一個序列剩餘的元素放入8元素序列中。
這個方法之是以有效，是因為兩個4元素序列都已經排好序，你不需要再『回到』序列中查找比較。
【譯者注：合并排序詳細原理，其中一個動圖（原圖較長，我做了删減）清晰的示範了上述合并排序的過程，而原文的叙述似乎沒有這麼清晰，不動戳大。】
既然我們明白了這個技巧，下面就是我的合并排序僞代碼。
arraymergeSortarray
length
return
//recursive calls
left_array right_arraysplit_into_2_equally_sized_arrays
arraynew_left_arraymergeSortleft_array
arraynew_right_arraymergeSortright_array
//merging the 2 small ordered arrays into a big one
arrayresultmergenew_left_arraynew_right_array
returnresult
合并排序是把問題拆分為小問題，通過解決小問題來解決最初的問題（注：這種算法叫分治法，即『分而治之、各個擊破』）。如果你不懂，不用擔心，我第一次接觸時也不懂。如果能幫助你了解的話，我認為這個算法是個兩步算法：
拆分階段，将序列分為更小的序列
排序階段，把小的序列合在一起（使用合并算法）來構成更大的序列
在拆分階段過程中，使用3個步驟将序列分為一進制序列。步驟數量的值是 log(N) （因為 N=8, log(N)=3）。【譯者注：底數為2，下文有說明】
我怎麼知道這個的？
我是天才！一句話：數學。道理是每一步都把原序列的長度除以2，步驟數就是你能把原序列長度除以2的次數。這正好是對數的定義（在底數為2時）。
在排序階段，你從一進制序列開始。在每一個步驟中，你應用多次合并操作，成本一共是 N=8 次運算。
第一步，4 次合并，每次成本是 2 次運算。
第二步，2 次合并，每次成本是 4 次運算。
第三步，1 次合并，成本是 8 次運算。
因為有 log(N) 個步驟，整體成本是 N*log(N) 次運算。
【譯者注：這個完整的動圖示範了拆分和排序的全過程，不動戳大。】
合并排序的強大之處
為什麼這個算法如此強大？
你可以更改算法，以便于節省記憶體空間，方法是不建立新的序列而是直接修改輸入序列。
注：這種算法叫『原地算法』(in-place algorithm)
你可以更改算法，以便于同時使用磁盤空間和少量記憶體而避免巨量磁盤 I/O。方法是隻向記憶體中加載目前處理的部分。在僅僅100MB的記憶體緩沖區内排序一個幾個GB的表時，這是個很重要的技巧。
注：這種算法叫『外部排序』(external sorting)。
你可以更改算法，以便于在 多處理器/多線程/多伺服器 上運作。
比如，分布式合并排序是Hadoop（那個著名的大資料架構）的關鍵元件之一。
這個算法可以點石成金（事實如此！）
這個排序算法在大多數（如果不是全部的話）資料庫中使用，但是它并不是唯一算法。如果你想多了解一些，你可以看看 這篇論文，探讨的是資料庫中常用排序算法的優勢和劣勢。
陣列，樹和哈希表
既然我們已經了解了時間複雜度和排序背後的理念，我必須要向你介紹3種資料結構了。這個很重要，因為它們是現代資料庫的支柱。我還會介紹資料庫索引的概念。
二維陣列是最簡單的資料結構。一個表可以看作是個陣列，比如：
這個二維陣列是帶有行與列的表：
每個行代表一個主體
列用來描述主體的特征
每個列儲存某一種類型對資料（整數、字元串、日期……）
雖然用這個方法儲存和視覺化資料很棒，但是當你要查找特定的值它就很糟糕了。 舉個例子，如果你要找到所有在 UK 工作的人，你必須檢視每一行以判斷該行是否屬于 UK 。這會造成 N 次運算的成本（N 等于行數），還不賴嘛，但是有沒有更快的方法呢？這時候樹就可以登場了（或開始起作用了）。
樹和資料庫索引
二叉查找樹是帶有特殊屬性的二叉樹，每個節點的關鍵字必須：
比儲存在左子樹的任何鍵值都要大
比儲存在右子樹的任何鍵值都要小
【譯者注：binary search tree，二叉查找樹/二叉搜尋樹，或稱 Binary Sort Tree 二叉排序樹。見百度百科 】
這個樹有 N=15 個元素。比方說我要找208：
我從鍵值為 136 的根開始，因為 136<208，我去找節點136的右子樹。
398>208，是以我去找節點398的左子樹
250>208，是以我去找節點250的左子樹
200<208，是以我去找節點200的右子樹。但是 200 沒有右子樹，值不存在（因為如果存在，它會在 200 的右子樹）
現在比方說我要找40
我從鍵值為136的根開始，因為 136>40，是以我去找節點136的左子樹。
80>40，是以我去找節點 80 的左子樹
40=40，節點存在。我抽取出節點内部行的ID（圖中沒有畫）再去表中查找對應的 ROW ID。
知道 ROW ID我就知道了資料在表中對精确位置，就可以立即擷取資料。
最後，兩次查詢的成本就是樹内部的層數。如果你仔細閱讀了合并排序的部分，你就應該明白一共有 log(N)層。是以這個查詢的成本是 log(N)，不錯啊！
回到我們的問題
上文說的很抽象，我們回來看看我們的問題。這次不用傻傻的數字了，想象一下前表中代表某人的國家的字元串。假設你有個樹包含表中的列『country』：
如果你想知道誰在 UK 工作
你在樹中查找代表 UK 的節點
在『UK 節點』你會找到 UK 員工那些行的位置
這次搜尋隻需 log(N) 次運算，而如果你直接使用陣列則需要 N 次運算。你剛剛想象的就是一個資料庫索引。
B+樹索引
查找一個特定值這個樹挺好用，但是當你需要查找兩個值之間的多個元素時，就會有大麻煩了。你的成本将是 O(N)，因為你必須查找樹的每一個節點，以判斷它是否處于那 2 個值之間（例如，對樹使用中序周遊）。而且這個操作不是磁盤I/O有利的，因為你必須讀取整個樹。我們需要找到高效的範圍查詢方法。為了解決這個問題，現代資料庫使用了一種修訂版的樹，叫做B+樹。在一個B+樹裡：
隻有最底層的節點（葉子節點）才儲存資訊（相關表的行位置）
其它節點隻是在搜尋中用來指引到正确節點的。
【譯者注：參考 B+樹 ， 二叉樹周遊維基百科】
你可以看到，節點更多了（多了兩倍）。确實，你有了額外的節點，它們就是幫助你找到正确節點的『決策節點』（正确節點儲存着相關表中行的位置）。但是搜尋複雜度還是在 O(log(N))（隻多了一層）。一個重要的不同點是，最底層的節點是跟後續節點相連接配接的。
用這個 B+樹，假設你要找40到100間的值：
你隻需要找 40（若40不存在則找40之後最貼近的值），就像你在上一個樹中所做的那樣。
然後用那些連接配接來收集40的後續節點，直到找到100。
比方說你找到了 M 個後續節點，樹總共有 N 個節點。對指定節點的搜尋成本是 log(N)，跟上一個樹相同。但是當你找到這個節點，你得通過後續節點的連接配接得到 M 個後續節點，這需要 M 次運算。那麼這次搜尋隻消耗了 M+log(N) 次運算，差別于上一個樹所用的 N 次運算。此外，你不需要讀取整個樹（僅需要讀 M+log(N) 個節點）,這意味着更少的磁盤通路。如果 M 很小（比如 200 行）并且 N 很大（1,000,000），那結果就是天壤之别了。
然而還有新的問題（又來了！）。如果你在資料庫中增加或删除一行（進而在相關的 B+樹索引裡）：
你必須在B+樹中的節點之間保持順序，否則節點會變得一團糟，你無法從中找到想要的節點。
你必須盡可能降低B+樹的層數，否則 O(log(N)) 複雜度會變成 O(N)。
換句話說，B+樹需要自我整理和自我平衡。謝天謝地，我們有智能删除和插入。但是這樣也帶來了成本：在B+樹中，插入和删除操作是 O(log(N)) 複雜度。是以有些人聽到過使用太多索引不是個好主意這類說法。沒錯，你減慢了快速插入/更新/删除表中的一個行的操作，因為資料庫需要以代價高昂的每索引 O(log(N)) 運算來更新表的索引。再者，增加索引意味着給事務管理器帶來更多的工作負荷（在本文結尾我們會探讨這個管理器）。
想了解更多細節，你可以看看 Wikipedia 上這篇關于B+樹的文章。如果你想要資料庫中實作B+樹的例子，看看MySQL核心開發人員寫的這篇文章 和 這篇文章。兩篇文章都緻力于探讨 innoDB(MySQL引擎)如何處理索引。
我們最後一個重要的資料結構是哈希表。當你想快速查找值時，哈希表是非常有用的。而且，了解哈希表會幫助我們接下來了解一個資料庫常見的聯接操作，叫做『哈希聯接』。這個資料結構也被資料庫用來儲存一些内部的東西（比如鎖表或者緩沖池，我們在下文會研究這兩個概念）。
哈希表這種資料結構可以用關鍵字來快速找到一個元素。為了建構一個哈希表，你需要定義：
元素的關鍵字
關鍵字的哈希函數。關鍵字計算出來的哈希值給出了元素的位置（叫做哈希桶）。
關鍵字比較函數。一旦你找到正确的哈希桶，你必須用比較函數在桶内找到你要的元素。
一個簡單的例子
我們來看一個形象化的例子：
這個哈希表有10個哈希桶。因為我懶，我隻給出5個桶，但是我知道你很聰明，是以我讓你想象其它的5個桶。我用的哈希函數是關鍵字對10取模，也就是我隻保留元素關鍵字的最後一位，用來查找它的哈希桶：
如果元素最後一位是 0，則進入哈希桶0，
如果元素最後一位是 1，則進入哈希桶1，
如果元素最後一位是 2，則進入哈希桶2，
…我用的比較函數隻是判斷兩個整數是否相等。
【譯者注：取模運算】
比方說你要找元素 78：
哈希表計算 78 的哈希碼，等于 8。
查找哈希桶 8，找到的第一個元素是 78。
傳回元素 78。
查詢僅耗費了 2 次運算（1次計算哈希值，另一次在哈希桶中查找元素）。
現在，比方說你要找元素 59：
哈希表計算 59 的哈希碼，等于9。
查找哈希桶 9，第一個找到的元素是 99。因為 99 不等于 59， 那麼 99 不是正确的元素。
用同樣的邏輯，查找第二個元素(9)，第三個(79)，……，最後一個(29)。
元素不存在。
搜尋耗費了 7 次運算。
一個好的哈希函數
你可以看到，根據你查找的值，成本并不相同。
如果我把哈希函數改為關鍵字對 1,000,000 取模（就是說取後6位數字），第二次搜尋隻消耗一次運算，因為哈希桶 00059 裡面沒有元素。真正的挑戰是找到好的哈希函數，讓哈希桶裡包含非常少的元素。
在我的例子裡，找到一個好的哈希函數很容易，但這是個簡單的例子。當關鍵字是下列形式時，好的哈希函數就更難找了：
1 個字元串（比如一個人的姓）
2 個字元串（比如一個人的姓和名）
2 個字元串和一個日期（比如一個人的姓、名和出生年月日）
如果有了好的哈希函數，在哈希表裡搜尋的時間複雜度是 O(1)。
陣列 vs 哈希表
為什麼不用陣列呢？
嗯，你問得好。
一個哈希表可以隻裝載一半到記憶體，剩下的哈希桶可以留在硬碟上。
用陣列的話，你需要一個連續記憶體空間。如果你加載一個大表，很難配置設定足夠的連續記憶體空間。
用哈希表的話，你可以選擇你要的關鍵字（比如，一個人的國家和姓氏）。
想要更詳細的資訊，你可以閱讀我在Java HashMap 上的文章，是關于高效哈希表實作的。你不需要了解Java就能了解文章裡的概念。
我們已經了解了資料庫内部的基本元件，現在我們需要回來看看資料庫的全貌了。
資料庫是一個易于通路和修改的資訊集合。不過簡單的一堆檔案也能達到這個效果。事實上，像SQLite這樣最簡單的資料庫也隻是一堆檔案而已，但SQLite是精心設計的一堆檔案，因為它允許你：
使用事務來確定資料的安全和一緻性
快速處理百萬條以上的資料
資料庫一般可以用如下圖形來了解：
撰寫這部分之前，我讀過很多書/論文，它們都以自己的方式描述資料庫。是以，我不會特别關注如何組織資料庫或者如何命名各種程序，因為我選擇了自己的方式來描述這些概念以适應本文。差別就是不同的元件，總體思路為：資料庫是由多種互互相動的元件構成的。
程序管理器（process manager）：很多資料庫具備一個需要妥善管理的程序/線程池。再者，為了實作納秒級操作，一些現代資料庫使用自己的線程而不是作業系統線程。
網絡管理器（network manager）：網路I/O是個大問題，尤其是對于分布式資料庫。是以一些資料庫具備自己的網絡管理器。
檔案系統管理器（File system manager）：磁盤I/O是資料庫的首要瓶頸。具備一個檔案系統管理器來完美地處理OS檔案系統甚至取代OS檔案系統，是非常重要的。
記憶體管理器（memory manager）：為了避免磁盤I/O帶來的性能損失，需要大量的記憶體。但是如果你要處理大容量記憶體你需要高效的記憶體管理器，尤其是你有很多查詢同時使用記憶體的時候。
安全管理器（Security Manager）：用于對使用者的驗證和授權。
用戶端管理器（Client manager）：用于管理用戶端連接配接。
備份管理器（Backup manager）：用于儲存和恢複資料。
複原管理器（Recovery manager）：用于崩潰後重新開機資料庫到一個一緻狀态。
監控管理器（Monitor manager）：用于記錄資料庫活動資訊和提供監控資料庫的工具。
Administration管理器（Administration manager）：用于儲存中繼資料（比如表的名稱和結構），提供管理資料庫、模式、表空間的工具。【譯者注：好吧，我真的不知道Administration manager該翻譯成什麼，有知道的麻煩告知，不勝感激……】
查詢管理器：
查詢解析器（Query parser）：用于檢查查詢是否合法
查詢重寫器（Query rewriter）：用于預優化查詢
查詢優化器（Query optimizer）：用于優化查詢
查詢執行器（Query executor）：用于編譯和執行查詢
資料管理器：
事務管理器（Transaction manager）：用于處理事務
緩存管理器（Cache manager）：資料被使用之前置于記憶體，或者資料寫入磁盤之前置于記憶體
資料通路管理器（Data access manager）：通路磁盤中的資料
在本文剩餘部分，我會集中探讨資料庫如何通過如下程序管理SQL查詢的：
用戶端管理器
查詢管理器
資料管理器（含複原管理器）
用戶端管理器
用戶端管理器是處理用戶端通信的。用戶端可以是一個（網站）伺服器或者一個最終使用者或最終應用。用戶端管理器通過一系列知名的API（JDBC, ODBC, OLE-DB …）提供不同的方式來通路資料庫。
用戶端管理器也提供專有的資料庫通路API。
當你連接配接到資料庫時：
管理器首先檢查你的驗證資訊（使用者名和密碼），然後檢查你是否有通路資料庫的授權。這些權限由DBA配置設定。
然後，管理器檢查是否有空閑程序（或線程）來處理你對查詢。
管理器還會檢查資料庫是否負載很重。
管理器可能會等待一會兒來擷取需要的資源。如果等待時間達到逾時時間，它會關閉連接配接并給出一個可讀的錯誤資訊。
然後管理器會把你的查詢送給查詢管理器來處理。
因為查詢處理程序不是『不全則無』的，一旦它從查詢管理器得到資料，它會把部分結果儲存到一個緩沖區并且開始給你發送。
如果遇到問題，管理器關閉連接配接，向你發送可讀的解釋資訊，然後釋放資源。
查詢管理器
這部分是資料庫的威力所在，在這部分裡，一個寫得糟糕的查詢可以轉換成一個快速執行的代碼，代碼執行的結果被送到用戶端管理器。這個多步驟操作過程如下：
查詢首先被解析并判斷是否合法
然後被重寫，去除了無用的操作并且加入預優化部分
接着被優化以便提升性能，并被轉換為可執行代碼和資料通路計劃。
然後計劃被編譯
最後，被執行
這裡我不會過多探讨最後兩步，因為它們不太重要。
看完這部分後，如果你需要更深入的知識，我建議你閱讀：
關于成本優化的初步研究論文(1979)：關系型資料庫系統存取路徑選擇。這個篇文章隻有12頁，而且具備計算機一般水準就能了解。
非常好、非常深入的 DB2 9.X 如何優化查詢的介紹
非常好的PostgreSQL如何優化查詢的介紹。這是一篇最通俗易懂的文檔，因為它講的是『我們來看看在這種情況下，PostgreSQL給出了什麼樣的查詢計劃』，而不是『我們來看看PostgreSQL用的什麼算法』。
官方SQLite優化文檔。『易于』閱讀，因為SQLite用的是簡單規則。再者，這是唯一真正解釋SQLite如何工作的官方文檔。
非常好的SQL Server 2005 如何優化查詢的介紹
Oracle 12c 優化白皮書
2篇查詢優化的教程，第一篇第二篇。教程來自《資料庫系統概念》的作者，很好的讀物，集中讨論磁盤I/O，但是要求具有很好的計算機科學水準。
另一個原理教程，這篇教程我覺得更易懂，不過它僅關注聯接運算符（join operators）和磁盤I/O。
查詢解析器
每一條SQL語句都要送到解析器來檢查文法，如果你的查詢有錯，解析器将拒絕該查詢。比如，如果你寫成”SLECT …” 而不是 “SELECT …”，那就沒有下文了。
但這還不算完，解析器還會檢查關鍵字是否使用正确的順序，比如 WHERE 寫在 SELECT 之前會被拒絕。
然後，解析器要分析查詢中的表和字段，使用資料庫中繼資料來檢查：
表是否存在
表的字段是否存在
對某類型字段的 運算 是否 可能（比如，你不能将整數和字元串進行比較，你不能對一個整數使用 substring() 函數）
接着，解析器檢查在查詢中你是否有權限來讀取（或寫入）表。再強調一次：這些權限由DBA配置設定。
在解析過程中，SQL 查詢被轉換為内部表示（通常是一個樹）。
如果一切正常，内部表示被送到查詢重寫器。
查詢重寫器
在這一步，我們已經有了查詢的内部表示，重寫器的目标是：
預優化查詢
避免不必要的運算
幫助優化器找到合理的最佳解決方案
重寫器按照一系列已知的規則對查詢執行檢測。如果查詢比對一種模式的規則，查詢就會按照這條規則來重寫。下面是（可選）規則的非詳盡的清單：
視圖合并：如果你在查詢中使用視圖，視圖就會轉換為它的 SQL 代碼。
子查詢扁平化：子查詢是很難優化的，是以重寫器會嘗試移除子查詢
MySQLSELECTPERSON.*
PERSON
WHEREPERSON.person_key
(SELECTMAILS.person_key
MAILS
WHEREMAILS.mail’christophe%’);
會轉換為：
MySQL
SELECTPERSON.*
PERSON,MAILS
WHEREPERSON.person_key=MAILS.person_key
MAILS.mail’christophe%’;
去除不必要的運算符：比如，如果你用了 DISTINCT，而其實你有 UNIQUE 限制（這本身就防止了資料出現重複），那麼 DISTINCT 關鍵字就被去掉了。
排除備援的聯接：如果相同的 JOIN 條件出現兩次，比如隐藏在視圖中的 JOIN 條件，或者由于傳遞性産生的無用 JOIN，都會被消除。
常數計算指派：如果你的查詢需要計算，那麼在重寫過程中計算會執行一次。比如 WHERE AGE > 10+2 會轉換為 WHERE AGE > 12 ， TODATE(“日期字元串”) 會轉換為 datetime 格式的日期值。
（進階）分區裁剪（Partition Pruning）：如果你用了分區表，重寫器能夠找到需要使用的分區。
（進階）物化視圖重寫（Materialized view rewrite）：如果你有個物化視圖比對查詢謂詞的一個子集，重寫器将檢查視圖是否最新并修改查詢，令查詢使用物化視圖而不是原始表。
（進階）自定義規則：如果你有自定義規則來修改查詢（就像 Oracle policy），重寫器就會執行這些規則。
（進階）OLAP轉換：分析/加窗 函數，星形聯接，ROLLUP 函數……都會發生轉換（但我不确定這是由重寫器還是優化器來完成，因為兩個程序聯系很緊，必須看是什麼資料庫）。
【譯者注： 物化視圖 。謂詞，predicate，條件表達式的求值傳回真或假的過程】
重寫後的查詢接着送到優化器，這時候好玩的就開始了。
研究資料庫如何優化查詢之前我們需要談談統計，因為沒有統計的資料庫是愚蠢的。除非你明确訓示，資料庫是不會分析自己的資料的。沒有分析會導緻資料庫做出（非常）糟糕的假設。
但是，資料庫需要什麼類型的資訊呢？
我必須（簡要地）談談資料庫和作業系統如何儲存資料。兩者使用的最小機關叫做頁或塊（預設 4 或 8 KB）。這就是說如果你僅需要 1KB，也會占用一個頁。要是頁的大小為 8KB，你就浪費了 7KB。
回來繼續講統計！ 當你要求資料庫收集統計資訊，資料庫會計算下列值：
表中行和頁的數量
表中每個列中的：
唯一值
資料長度（最小，最大，平均）
資料範圍（最小，最大，平均）
表的索引資訊
這些統計資訊會幫助優化器估計查詢所需的磁盤 I/O、CPU、和記憶體使用
對每個列的統計非常重要。
比如，如果一個表 PERSON 需要聯接 2 個列： LAST_NAME, FIRST_NAME。
根據統計資訊，資料庫知道FIRST_NAME隻有 1,000 個不同的值，LAST_NAME 有 1,000,000 個不同的值。
是以，資料庫就會按照 LAST_NAME, FIRST_NAME 聯接。
因為 LAST_NAME 不大可能重複，多數情況下比較 LAST_NAME 的頭 2 、 3 個字元就夠了，這将大大減少比較的次數。
不過，這些隻是基本的統計。你可以讓資料庫做一種進階統計，叫直方圖。直方圖是列值分布情況的統計資訊。例如：
出現最頻繁的值
分位數 【譯者注：http://baike.baidu.com/view/1323572.htm】
這些額外的統計會幫助資料庫找到更佳的查詢計劃，尤其是對于等式謂詞（例如： WHERE AGE = 18 ）或範圍謂詞（例如： WHERE AGE > 10 and AGE < 40），因為資料庫可以更好的了解這些謂詞相關的數字類型資料行（注：這個概念的技術名稱叫選擇率）。
統計資訊儲存在資料庫中繼資料内，例如（非分區）表的統計資訊位置：
Oracle： USER / ALL / DBA_TABLES 和 USER / ALL / DBA_TAB_COLUMNS
DB2： SYSCAT.TABLES 和 SYSCAT.COLUMNS
統計資訊必須及時更新。如果一個表有 1,000,000 行而資料庫認為它隻有 500 行，沒有比這更糟糕的了。統計唯一的不利之處是需要時間來計算，這就是為什麼資料庫大多預設情況下不會自動計算統計資訊。資料達到百萬級時統計會變得困難，這時候，你可以選擇僅做基本統計或者在一個資料庫樣本上執行統計。
舉個例子，我參與的一個項目需要處理每表上億條資料的庫，我選擇隻統計10%，結果造成了巨大的時間消耗。本例證明這是個糟糕的決定，因為有時候 Oracle 10G 從特定表的特定列中選出的 10% 跟全部 100% 有很大不同（對于擁有一億行資料的表，這種情況極少發生）。這次錯誤的統計導緻了一個本應 30 秒完成的查詢最後執行了 8 個小時，查找這個現象根源的過程簡直是個噩夢。這個例子顯示了統計的重要性。
注：當然了，每個資料庫還有其特定的更進階的統計。如果你想了解更多資訊，讀讀資料庫的文檔。話雖然這麼說，我已經盡力了解統計是如何使用的了，而且我找到的最好的官方文檔來自PostgreSQL。
查詢優化器
所有的現代資料庫都在用基于成本的優化（即CBO）來優化查詢。道理是針對每個運算設定一個成本，通過應用成本最低廉的一系列運算，來找到最佳的降低查詢成本的方法。
為了了解成本優化器的原理，我覺得最好用個例子來『感受』一下這個任務背後的複雜性。這裡我将給出聯接 2 個表的 3 個方法，我們很快就能看到即便一個簡單的聯接查詢對于優化器來說都是個噩夢。之後，我們會了解真正的優化器是怎麼做的。
對于這些聯接操作，我會專注于它們的時間複雜度，但是，資料庫優化器計算的是它們的 CPU 成本、磁盤 I/O 成本、和記憶體需求。時間複雜度和 CPU 成本的差別是，時間成本是個近似值（給我這樣的懶家夥準備的）。而 CPU 成本，我這裡包括了所有的運算，比如：加法、條件判斷、乘法、疊代……還有呢：
每一個進階代碼運算都要特定數量的低級 CPU 運算。
對于 Intel Core i7、Intel Pentium 4、AMD Opteron…等，（就 CPU 周期而言）CPU 的運算成本是不同的，也就是說它取決于 CPU 的架構。
使用時間複雜度就容易多了（至少對我來說），用它我也能了解到 CBO 的概念。由于磁盤 I/O 是個重要的概念，我偶爾也會提到它。請牢記，大多數時候瓶頸在于磁盤 I/O 而不是 CPU 使用。
在研究 B+樹的時候我們談到了索引，要記住一點，索引都是已經排了序的。
僅供參考：還有其他類型的索引，比如位圖索引，在 CPU、磁盤I/O、和記憶體方面與B+樹索引的成本并不相同。
另外，很多現代資料庫為了改善執行計劃的成本，可以僅為目前查詢動态地生成臨時索引。
在應用聯接運算符（join operators）之前，你首先需要獲得資料。以下就是獲得資料的方法。
注：由于所有存取路徑的真正問題是磁盤 I/O，我不會過多探讨時間複雜度。
【譯者注：四種類型的Oracle索引掃描介紹 】
如果你讀過執行計劃，一定看到過『全掃描』（或隻是『掃描』）一詞。簡單的說全掃描就是資料庫完整的讀一個表或索引。就磁盤 I/O 而言，很明顯全表掃描的成本比索引全掃描要高昂。
其他類型的掃描有索引範圍掃描，比如當你使用謂詞 ” WHERE AGE > 20 AND AGE < 40 ” 的時候它就會發生。
當然，你需要在 AGE 字段上有索引才能用到索引範圍掃描。
在第一部分我們已經知道，範圍查詢的時間成本大約是 log(N)+M，這裡 N 是索引的資料量，M 是範圍内估測的行數。多虧有了統計我們才能知道 N 和 M 的值（注： M 是謂詞 “ AGE > 20 AND AGE < 40 ” 的選擇率）。另外範圍掃描時，你不需要讀取整個索引，是以在磁盤 I/O 方面沒有全掃描那麼昂貴。
如果你隻需要從索引中取一個值你可以用唯一掃描。
根據 ROW ID 存取
多數情況下，如果資料庫使用索引，它就必須查找與索引相關的行，這樣就會用到根據 ROW ID 存取的方式。
例如，假如你運作：
MySQL
SELECTLASTNAME,FIRSTNAMEPERSONWHEREAGE=28
如果 person 表的 age 列有索引，優化器會使用索引找到所有年齡為 28 的人，然後它會去表中讀取相關的行，這是因為索引中隻有 age 的資訊而你要的是姓和名。
但是，假如你換個做法：
MySQL
SELECTTYPE_PERSON.CATEGORYPERSON,TYPE_PERSON
WHEREPERSON.AGE=TYPE_PERSON.AGE
PERSON 表的索引會用來聯接 TYPE_PERSON 表，但是 PERSON 表不會根據行ID 存取，因為你并沒有要求這個表内的資訊。
雖然這個方法在少量存取時表現很好，這個運算的真正問題其實是磁盤 I/O。假如需要大量的根據行ID存取，資料庫也許會選擇全掃描。
我沒有列舉所有的存取路徑，如果你感興趣可以讀一讀 Oracle文檔。其它資料庫裡也許叫法不同但背後的概念是一樣的。
聯接運算符
那麼，我們知道如何擷取資料了，那現在就把它們聯接起來！
我要展現的是3個個常用聯接運算符：合并聯接（Merge join），哈希聯接（Hash Join）和嵌套循環聯接（Nested Loop Join）。但是在此之前，我需要引入新詞彙了：内關系和外關系（ inner relation and outer relation） 【譯者注： “内關系和外關系” 這個說法來源不明，跟查詢的“内聯接（INNER JOIN） 、外聯接（OUTER JOIN） ” 不是一個概念 。隻查到百度百科詞條：關系資料庫 裡提到“每個表格（有時被稱為一個關系）……” 。 其他參考連結 “Merge Join” “Hash Join” “Nested Loop Join” 】。 一個可以是：
上一個運算的中間結果（比如上一個聯接運算的結果）
當你聯接兩個關系時，聯接算法對兩個關系的處理是不同的。在本文剩餘部分，我将假定：
外關系是左側資料集
内關系是右側資料集
比如， A JOIN B 是 A 和 B 的聯接，這裡 A 是外關系，B 是内關系。
多數情況下， A JOIN B 的成本跟 B JOIN A 的成本是不同的。
在這一部分，我還将假定外關系有 N 個元素，内關系有 M 個元素。要記住，真實的優化器通過統計知道 N 和 M 的值。
注：N 和 M 是關系的基數。【譯者注： 基數 】
嵌套循環聯接
嵌套循環聯接是最簡單的。
道理如下：
針對外關系的每一行
檢視内關系裡的所有行來尋找比對的行
下面是僞代碼：
nested_loop_joinarrayouterarrayinner
outer
inner
match_join_condition
write_result_in_output
由于這是個雙疊代，時間複雜度是 O(N*M)。
在磁盤 I/O 方面， 針對 N 行外關系的每一行，内部循環需要從内關系讀取 M 行。這個算法需要從磁盤讀取 N+ N*M 行。但是，如果内關系足夠小，你可以把它讀入記憶體，那麼就隻剩下 M + N 次讀取。這樣修改之後，内關系必須是最小的，因為它有更大機會裝入記憶體。
在CPU成本方面沒有什麼差別，但是在磁盤 I/O 方面，最好最好的，是每個關系隻讀取一次。
當然，内關系可以由索引代替，對磁盤 I/O 更有利。
由于這個算法非常簡單，下面這個版本在内關系太大無法裝入記憶體時，對磁盤 I/O 更加有利。道理如下：
為了避免逐行讀取兩個關系，
你可以成簇讀取，把（兩個關系裡讀到的）兩簇資料行儲存在記憶體裡，
比較兩簇資料，保留比對的，
然後從磁盤加載新的資料簇來繼續比較
直到加載了所有資料。
可能的算法如下：
// improved version to reduce the disk I/O.
nested_loop_join_v2outerinner
bunch outer
// ba is now in memory
bunch inner
// bb is now in memory
match_join_condition
write_result_in_output
使用這個版本，時間複雜度沒有變化，但是磁盤通路降低了：
用前一個版本，算法需要 N + N*M 次通路（每次通路讀取一行）。
用新版本，磁盤通路變為 外關系的資料簇數量 + 外關系的資料簇數量 * 内關系的資料簇數量。
增加資料簇的尺寸，可以降低磁盤通路。
哈希聯接更複雜，不過在很多場合比嵌套循環聯接成本低。
哈希聯接的道理是：
1) 讀取内關系的所有元素
2) 在記憶體裡建一個哈希表
3) 逐條讀取外關系的所有元素
4) （用哈希表的哈希函數）計算每個元素的哈希值，來查找内關系裡相關的哈希桶内
5) 是否與外關系的元素比對。
在時間複雜度方面我需要做些假設來簡化問題：
内關系被劃分成 X 個哈希桶
哈希函數幾乎均勻地分布每個關系内資料的哈希值，就是說哈希桶大小一緻。
外關系的元素與哈希桶内的所有元素的比對，成本是哈希桶内元素的數量。
時間複雜度是 (M/X) * (N/X) + 建立哈希表的成本(M) + 哈希函數的成本 * N 。
如果哈希函數建立了足夠小規模的哈希桶，那麼複雜度就是 O(M+N)。
還有個哈希聯接的版本，對記憶體有利但是對磁盤 I/O 不夠有利。 這回是這樣的：
1) 計算内關系和外關系雙方的哈希表
2) 儲存哈希表到磁盤
3) 然後逐個哈希桶比較（其中一個讀入記憶體，另一個逐行讀取）。
合并聯接是唯一産生排序的聯接算法。
注：這個簡化的合并聯接不區分内表或外表；兩個表扮演同樣的角色。但是真實的實作方式是不同的，比如當處理重複值時。
1.（可選）排序聯接運算：兩個輸入源都按照聯接關鍵字排序。
2.合并聯接運算：排序後的輸入源合并到一起。
我們已經談到過合并排序，在這裡合并排序是個很好的算法（但是并非最好的，如果記憶體足夠用的話，還是哈希聯接更好）。
然而有時資料集已經排序了，比如：
如果表内部就是有序的，比如聯接條件裡一個索引組織表 【譯者注： index-organized table 】
如果關系是聯接條件裡的一個索引
如果聯接應用在一個查詢中已經排序的中間結果
這部分與我們研究過的合并排序中的合并運算非常相似。不過這一次呢，我們不是從兩個關系裡挑選所有元素，而是隻挑選相同的元素。道理如下：
1) 在兩個關系中，比較目前元素（目前=頭一次出現的第一個）
2) 如果相同，就把兩個元素都放入結果，再比較兩個關系裡的下一個元素
3) 如果不同，就去帶有最小元素的關系裡找下一個元素（因為下一個元素可能會比對）
4) 重複 1、2、3步驟直到其中一個關系的最後一個元素。
因為兩個關系都是已排序的，你不需要『回頭去找』，是以這個方法是有效的。
該算法是個簡化版，因為它沒有處理兩個序列中相同資料出現多次的情況（即多重比對）。真實版本『僅僅』針對本例就更加複雜，是以我才選擇簡化版。
如果兩個關系都已經排序，時間複雜度是 O(N+M)
如果兩個關系需要排序，時間複雜度是對兩個關系排序的成本：O(N*Log(N) + M*Log(M))
對于計算機極客，我給出下面這個可能的算法來處理多重比對（注：對于這個算法我不保證100%正确）：
mergeJoinrelationrelation
relation output
integera_key
integerb_key
whilea_keyb_key
a_keyb_key
a_key
a_keyb_key
b_key
//Join predicate satisfied
write_result_in_outputa_keyb_key
//We need to be careful when we increase the pointers
a_keyb_key
b_key
b_keya_key
a_key
b_keya_keyb_keya_key
b_key
a_key
while
哪個算法最好？
如果有最好的，就沒必要弄那麼多種類型了。這個問題很難，因為很多因素都要考慮，比如：
空閑記憶體：沒有足夠的記憶體的話就跟強大的哈希聯接拜拜吧（至少是完全記憶體中哈希聯接）。
兩個資料集的大小。比如，如果一個大表聯接一個很小的表，那麼嵌套循環聯接就比哈希聯接快，因為後者有建立哈希的高昂成本；如果兩個表都非常大，那麼嵌套循環聯接CPU成本就很高昂。
是否有索引：有兩個 B+樹索引的話，聰明的選擇似乎是合并聯接。
結果是否需要排序：即使你用到的是未排序的資料集，你也可能想用成本較高的合并聯接（帶排序的），因為最終得到排序的結果後，你可以把它和另一個合并聯接串起來（或者也許因為查詢用 ORDER BY/GROUP BY/DISTINCT 等操作符隐式或顯式地要求一個排序結果）。
關系是否已經排序：這時候合并聯接是最好的候選項。
聯接的類型：是等值聯接（比如 tableA.col1 = tableB.col2 ）？ 還是内聯接？外聯接？笛卡爾乘積？或者自聯接？有些聯接在特定環境下是無法工作的。
資料的分布：如果聯接條件的資料是傾斜的（比如根據姓氏來聯接人，但是很多人同姓），用哈希聯接将是個災難，原因是哈希函數将産生分布極不均勻的哈希桶。
如果你希望聯接操作使用多線程或多程序。
想要更詳細的資訊，可以閱讀DB2, ORACLE 或 SQL Server)的文檔。
簡化的例子
我們已經研究了 3 種類型的聯接操作。
現在，比如說我們要聯接 5 個表，來獲得一個人的全部資訊。一個人可以有：
多個手機号（MOBILES）
多個郵箱（MAILS）
多個位址（ADRESSES）
多個銀行賬号（BANK_ACCOUNTS）
換句話說，我們需要用下面的查詢快速得到答案：
MySQL
SELECT*PERSON,MOBILES,MAILS,ADRESSES,BANK_ACCOUNTS
WHERE
PERSON.PERSON_ID=MOBILES.PERSON_ID
PERSON.PERSON_ID=MAILS.PERSON_ID
PERSON.PERSON_ID=ADRESSES.PERSON_ID
PERSON.PERSON_ID=BANK_ACCOUNTS.PERSON_ID
作為一個查詢優化器，我必須找到處理資料最好的方法。但有 2 個問題：
每個聯接使用那種類型？
我有 3 種可選（哈希、合并、嵌套），同時可能用到 0, 1 或 2 個索引（不必說還有多種類型的索引）。
按什麼順序執行聯接？
比如，下圖顯示了針對 4 個表僅僅 3 次聯接，可能采用的執行計劃：
那麼下面就是我可能采取的方法：
1) 采取粗暴的方式
用資料庫統計，計算每種可能的執行計劃的成本，保留最佳方案。但是，會有很多可能性。對于一個給定順序的聯接操作，每個聯接有三種可能性：哈希、合并、嵌套，那麼總共就有 3^4 種可能性。确定聯接的順序是個二叉樹的排列問題，會有 (2*4)!/(4+1)! 種可能的順序。對本例這個相當簡化了的問題，我最後會得到 3^4*(2*4)!/(4+1)! 種可能。
抛開專業術語，那相當于 27,216 種可能性。如果給合并聯接加上使用 0,1 或 2 個 B+樹索引，可能性就變成了 210,000種。我是不是告訴過你這個查詢其實非常簡單嗎？
2) 我大叫一聲辭了這份工作
很有誘惑力，但是這樣一來，你不會的到查詢結果，而我需要錢來付賬單。
3) 我隻嘗試幾種執行計劃，挑一個成本最低的。
由于不是超人，我不能算出所有計劃的成本。相反，我可以武斷地從全部可能的計劃中選擇一個子集，計算它們的成本，把最佳的計劃給你。
4) 我用聰明的規則來降低可能性的數量
有兩種規則：
我可以用『邏輯』規則，它能去除無用的可能性，但是無法過濾大量的可能性。比如： 『嵌套聯接的内關系必須是最小的資料集』。
我接受現實，不去找最佳方案，用更激進的規則來大大降低可能性的數量。比如：『如果一個關系很小，使用嵌套循環聯接，絕不使用合并或哈希聯接。』
在這個簡單的例子中，我最後得到很多可能性。但現實世界的查詢還會有其他關系運算符，像 OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT … 這意味着更多的可能性。
那麼，資料庫是如何處理的呢？
動态程式設計，貪婪算法和啟發式算法
關系型資料庫會嘗試我剛剛提到的多種方法，優化器真正的工作是在有限時間裡找到一個好的解決方案。
多數時候，優化器找到的不是最佳的方案，而是一個『不錯』的
對于小規模的查詢，采取粗暴的方式是有可能的。但是為了讓中等規模的查詢也能采取粗暴的方式，我們有辦法避免不必要的計算，這就是動态程式設計。
這幾個字背後的理念是，很多執行計劃是非常相似的。看看下圖這幾種計劃：
它們都有相同的子樹（A JOIN B），是以，不必在每個計劃中計算這個子樹的成本，計算一次，儲存結果，當再遇到這個子樹時重用。用更正規的說法，我們面對的是個重疊問題。為了避免對部分結果的重複計算，我們使用記憶法。
對于計算機極客，下面是我在先前給你的教程裡找到的一個算法。我不提供解釋，是以僅在你已經了解動态程式設計或者精通算法的情況下閱讀（我提醒過你哦）：
procedure findbestplan
bestplaninfinite
returnbestplan
// else bestplan[S] has not been computed earlier, compute it now
contains relation
bestplanbestplanbased
accessing
empty subset
findbestplan
findbestplan
algorithm joining results
bestplan
bestplan
bestplan『execute execute
results using』
returnbestplan
針對大規模查詢，你也可以用動态程式設計方法，但是要附加額外的規則（或者稱為啟發式算法）來減少可能性。
如果我們僅分析一個特定類型的計劃（例如左深樹 left-deep tree，參考)，我們得到 n*2^n 而不是 3^n。
如果我們加上邏輯規則來避免一些模式的計劃（像『如果一個表有針對指定謂詞的索引，就不要對表嘗試合并聯接，要對索引』），就會在不給最佳方案造成過多傷害的前提下，減少可能性的數量。【譯者注：原文應該是有兩處筆誤： as=has, to=too】
如果我們在流程裡增加規則（像『聯接運算先于其他所有的關系運算』），也能減少大量的可能性。
但是，優化器面對一個非常大的查詢，或者為了盡快找到答案（然而查詢速度就快不起來了），會應用另一種算法，叫貪婪算法。
原理是按照一個規則（或啟發）以漸進的方式制定查詢計劃。在這個規則下，貪婪算法逐漸尋找最佳算法，先處理一條JOIN，接着每一步按照同樣規則加一條新的JOIN。
我們來看個簡單的例子。比如一個針對5張表（A,B,C,D,E）4次JOIN 的查詢，為了簡化我們把嵌套JOIN作為可能的聯接方式，按照『使用最低成本的聯接』規則。
直接從 5 個表裡選一個開始（比如 A）
計算每一個與 A 的聯接（A 作為内關系或外關系）
發現 “A JOIN B” 成本最低
計算每一個與 “A JOIN B” 的結果聯接的成本（“A JOIN B” 作為内關系或外關系）
發現 “(A JOIN B) JOIN C” 成本最低
計算每一個與 “(A JOIN B) JOIN C” 的結果聯接的成本 ……
最後确定執行計劃 “( ( (A JOIN B) JOIN C) JOIN D ) JOIN E )”
因為我們是武斷地從表 A 開始，我們可以把同樣的算法用在 B，然後 C，然後 D, 然後 E。最後保留成本最低的執行計劃。
順便說一句，這個算法有個名字，叫『最近鄰居算法』。
抛開細節不談，隻需一個良好的模型和一個 N*log(N) 複雜度的排序，問題就輕松解決了。這個算法的複雜度是 O(N*log(N)) ，對比一下完全動态程式設計的 O(3^N)。如果你有個20個聯接的大型查詢，這意味着 26 vs 3,486,784,401 ，天壤之别！
這個算法的問題是，我們做的假設是：找到 2 個表的最佳聯接方法，保留這個聯接結果，再聯接下一個表，就能得到最低的成本。但是：
即使在 A, B, C 之間，A JOIN B 可得最低成本
(A JOIN C) JOIN B 也許比 (A JOIN B) JOIN C 更好。
為了改善這一狀況，你可以多次使用基于不同規則的貪婪算法，并保留最佳的執行計劃。
[ 如果你已經受夠了算法話題，就直接跳到下一部分。這部分對文章餘下的内容不重要。] 【譯者注：我也很想把這段跳過去 -_- 】
很多計算機科學研究者熱衷于尋找最佳的執行計劃，他們經常為特定問題或模式探尋更好的解決方案，比如：
如果查詢是星型聯接（一種多聯接查詢），某些資料庫使用一種特定的算法。
如果查詢是并行的，某些資料庫使用一種特定的算法。 ……
其他算法也在研究之中，就是為了替換在大型查詢中的動态程式設計算法。貪婪算法屬于一個叫做啟發式算法的大家族，它根據一條規則（或啟發），儲存上一步找到的方法，『附加』到目前步驟來進一步搜尋解決方法。有些算法根據特定規則，一步步的應用規則但不總是保留上一步找到的最佳方法。它們統稱啟發式算法。
比如，基因算法就是一種：
一個方法代表一種可能的完整查詢計劃
每一步保留了 P 個方法（即計劃），而不是一個。
0) P 個計劃随機建立
1) 成本最低的計劃才會保留
2) 這些最佳計劃混合在一起産生 P 個新的計劃
3) 一些新的計劃被随機改寫
4) 1，2，3步重複 T 次
5) 然後在最後一次循環，從 P 個計劃裡得到最佳計劃。
循環次數越多，計劃就越好。
這是魔術？不，這是自然法則：适者生存！
PostgreSQL 實作了基因算法，但我并沒有發現它是不是預設使用這種算法的。
資料庫中還使用了其它啟發式算法，像『模拟退火算法（Simulated Annealing）』、『互動式改良算法（Iterative Improvement）』、『雙階段優化算法（Two-Phase Optimization）』…..不過，我不知道這些算法目前是否在企業級資料庫應用了，還是僅僅用在研究型資料庫。
如果想進一步了解，這篇研究文章介紹兩個更多可能的算法《資料庫查詢優化中聯接排序問題的算法綜述》，你可以去閱讀一下。
真實的優化器
[ 這段不重要，可以跳過 ]
然而，所有上述羅裡羅嗦的都非常理論化，我是個開發者而不是研究者，我喜歡具體的例子。
我們來看看 SQLite 優化器 是怎麼工作的。這是個輕量化資料庫，它使用一種簡單優化器，基于帶有附加規則的貪婪算法，來限制可能性的數量。
SQLite 在有 CROSS JOIN 操作符時從不給表重新排序
使用嵌套聯接
外聯接始終按順序評估
3.8.0之前的版本使用『最近鄰居』貪婪算法來搜尋最佳查詢計劃
等等……我們見過這個算法！真是巧哈！
從3.8.0版本（釋出于2015年）開始，SQLite使用『N最近鄰居』貪婪算法來搜尋最佳查詢計劃
我們再看看另一個優化器是怎麼工作的。IBM DB2 跟所有企業級資料庫都類似，我讨論它是因為在切換到大資料之前，它是我最後真正使用的資料庫。
看過官方文檔後，我們了解到 DB2 優化器可以讓你使用 7 種級别的優化：
對聯接使用貪婪算法
0 – 最小優化，使用索引掃描和嵌套循環聯接，避免一些查詢重寫
1 – 低級優化
2 – 完全優化
對聯接使用動态程式設計算法
3 – 中等優化和粗略的近似法
5 – 完全優化，使用帶有啟發式的所有技術
7 – 完全優化，類似級别5，但不用啟發式
9 – 最大優化，完全不顧開銷，考慮所有可能的聯接順序，包括笛卡爾乘積
可以看到 DB2 使用貪婪算法和動态程式設計算法。當然，他們不會把自己的啟發算法分享出來的，因為查詢優化器是資料庫的看家本領。
DB2 的預設級别是 5，優化器使用下列特性： 【譯者注：以下出現的一些概念我沒有做考證，因為[ 這段不重要，可以跳過 ]】
使用所有可用的統計，包括線段樹（frequent-value）和分位數統計（quantile statistics）。
使用所有查詢重寫規則（含物化查詢表路由，materialized query table routing），除了在極少情況下适用的計算密集型規則。
使用動态程式設計模拟聯接
有限使用組合内關系（composite inner relation）
對于涉及查找表的星型模式，有限使用笛卡爾乘積
考慮寬泛的通路方式，含清單預取（list prefetch，注：我們将讨論什麼是清單預取），index ANDing（注：一種對索引的特殊操作），和物化查詢表路由。
預設的，DB2 對聯接排列使用受啟發式限制的動态程式設計算法。
其它情況 (GROUP BY, DISTINCT…) 由簡單規則處理。
查詢計劃緩存
由于建立查詢計劃是耗時的，大多資料庫把計劃儲存在查詢計劃緩存，來避免重複計算。這個話題比較大，因為資料庫需要知道什麼時候更新過時的計劃。辦法是設定一個上限，如果一個表的統計變化超過了上限，關于該表的查詢計劃就從緩存中清除。
查詢執行器
在這個階段，我們有了一個優化的執行計劃，再編譯為可執行代碼。然後，如果有足夠資源（記憶體，CPU），查詢執行器就會執行它。計劃中的操作符 (JOIN, SORT BY …) 可以順序或并行執行，這取決于執行器。為了獲得和寫入資料，查詢執行器與資料管理器互動，本文下一部分來讨論資料管理器。
資料管理器
在這一步，查詢管理器執行了查詢，需要從表和索引擷取資料，于是向資料管理器提出請求。但是有 2 個問題：
關系型資料庫使用事務模型，是以，當其他人在同一時刻使用或修改資料時，你無法得到這部分資料。
資料提取是資料庫中速度最慢的操作，是以資料管理器需要足夠聰明地獲得資料并儲存在記憶體緩沖區内。
在這一部分，我沒看看關系型資料庫是如何處理這兩個問題的。我不會講資料管理器是怎麼獲得資料的，因為這不是最重要的（而且本文已經夠長的了！）。
緩存管理器
我已經說過，資料庫的主要瓶頸是磁盤 I/O。為了提高性能，現代資料庫使用緩存管理器。
查詢執行器不會直接從檔案系統拿資料，而是向緩存管理器要。緩存管理器有一個記憶體緩存區，叫做緩沖池，從記憶體讀取資料顯著地提升資料庫性能。對此很難給出一個數量級，因為這取決于你需要的是哪種操作：
順序通路（比如：全掃描） vs 随機通路（比如：按照row id通路）
以及資料庫使用的磁盤類型：
7.2k/10k/15k rpm的硬碟
RAID 1/5/…
要我說，記憶體比磁盤要快100到10萬倍。
然而，這導緻了另一個問題（資料庫總是這樣…)，緩存管理器需要在查詢執行器使用資料之前得到資料，否則查詢管理器不得不等待資料從緩慢的磁盤中讀出來。
這個問題叫預讀。查詢執行器知道它将需要什麼資料，因為它了解整個查詢流，而且通過統計也了解磁盤上的資料。道理是這樣的：
當查詢執行器處理它的第一批資料時
會告訴緩存管理器預先裝載第二批資料
當開始處理第二批資料時
告訴緩存管理器預先裝載第三批資料，并且告訴緩存管理器第一批可以從緩存裡清掉了。
緩存管理器在緩沖池裡儲存所有的這些資料。為了确定一條資料是否有用，緩存管理器給緩存的資料添加了額外的資訊（叫闩鎖）。
有時查詢執行器不知道它需要什麼資料，有的資料庫也不提供這個功能。相反，它們使用一種推測預讀法（比如：如果查詢執行器想要資料1、3、5，它不久後很可能會要 7、9、11），或者順序預讀法（這時候緩存管理器隻是讀取一批資料後簡單地從磁盤加載下一批連續資料）。
為了監控預讀的工作狀況，現代資料庫引入了一個度量叫緩沖/緩存命中率，用來顯示請求的資料在緩存中找到而不是從磁盤讀取的頻率。
注：糟糕的緩存命中率不總是意味着緩存工作狀态不佳。更多資訊請閱讀Oracle文檔。
緩沖隻是容量有限的記憶體空間，是以，為了加載新的資料，它需要移除一些資料。加載和清除緩存需要一些磁盤和網絡I/O的成本。如果你有個經常執行的查詢，那麼每次都把查詢結果加載然後清除，效率就太低了。現代資料庫用緩沖區置換政策來解決這個問題。
緩沖區置換政策
多數現代資料庫(至少 SQL Server, MySQL, Oracle 和 DB2)使用 LRU 算法。
LRU代表最近最少使用（Least Recently Used）算法，背後的原理是：在緩存裡保留的資料是最近使用的，是以更有可能再次使用。
為了更好的了解，我假設緩沖區裡的資料沒有被闩鎖鎖住（就是說是可以被移除的）。在這個簡單的例子裡，緩沖區可以儲存 3 個元素：
1：緩存管理器（簡稱CM）使用資料1，把它放入空的緩沖區
2：CM使用資料4，把它放入半載的緩沖區
3：CM使用資料3，把它放入半載的緩沖區
4：CM使用資料9，緩沖區滿了，是以資料1被清除，因為它是最後一個最近使用的，資料9加入到緩沖區
5：CM使用資料4，資料4已經在緩沖區了，是以它再次成為第一個最近使用的。
6：CM使用資料1，緩沖區滿了，是以資料9被清除，因為它是最後一個最近使用的，資料1加入到緩沖區
這個算法效果很好，但是有些限制。如果對一個大表執行全表掃描怎麼辦？換句話說，當表/索引的大小超出緩沖區會發生什麼？使用這個算法會清除之前緩存内所有的資料，而且全掃描的資料很可能隻使用一次。
為了防止這個現象，有些資料庫增加了特殊的規則，比如Oracle文檔中的描述：
『對非常大的表來說，資料庫通常使用直接路徑來讀取，即直接加載區塊[……]，來避免填滿緩沖區。對于中等大小的表，資料庫可以使用直接讀取或緩存讀取。如果選擇緩存讀取，資料庫把區塊置于LRU的尾部，防止清空目前緩沖區。』
還有一些可能，比如使用進階版本的LRU，叫做 LRU-K。例如，SQL Server 使用 LRU-2。
這個算法的原理是把更多的曆史記錄考慮進來。簡單LRU（也就是 LRU-1），隻考慮最後一次使用的資料。LRU-K呢：
考慮資料最後第K次使用的情況
資料使用的次數加進了權重
一批新資料加載進入緩存，舊的但是經常使用的資料不會被清除（因為權重更高）
但是這個算法不會保留緩存中不再使用的資料
是以資料如果不再使用，權重值随着時間推移而降低
計算權重是需要成本的，是以SQL Server隻是使用 K=2，這個值性能不錯而且額外開銷可以接受。
關于LRU-K更深入的知識，可以閱讀早期的研究論文（1993）：資料庫磁盤緩沖的LRU-K頁面置換算法
當然還有其他管理緩存的算法，比如：
2Q（類LRU-K算法）
CLOCK（類LRU-K算法）
MRU（最新使用的算法，用LRU同樣的邏輯但不同的規則）
LRFU（Least Recently and Frequently Used，最近最少使用最近最不常用）
我隻探讨了讀緩存 —— 在使用之前預先加載資料。用來儲存資料、成批刷入磁盤，而不是逐條寫入資料進而造成很多單次磁盤通路。
要記住，緩沖區儲存的是頁（最小的資料機關）而不是行（邏輯上/人類習慣的觀察資料的方式）。緩沖池内的頁如果被修改了但還沒有寫入磁盤，就是髒頁。有很多算法來決定寫入髒頁的最佳時機，但這個問題與事務的概念高度關聯，下面我們就談談事務。
事務管理器
最後但同樣重要的，是事務管理器，我們将看到這個程序是如何保證每個查詢在自己的事務内執行的。但開始之前，我們需要了解ACID事務的概念。
“I’m on acid”
一個ACID事務是一個工作單元，它要保證4個屬性：
原子性（Atomicity）: 事務『要麼全部完成，要麼全部取消』，即使它持續運作10個小時。如果事務崩潰，狀态回到事務之前（事務復原）。
隔離性（Isolation）: 如果2個事務 A 和 B 同時運作，事務 A 和 B 最終的結果是相同的，不管 A 是結束于 B 之前/之後/運作期間。
持久性（Durability）: 一旦事務送出（也就是成功執行）,不管發生什麼（崩潰或者出錯），資料要儲存在資料庫中。
一緻性（Consistency）: 隻有合法的資料（依照關系限制和函數限制）能寫入資料庫，一緻性與原子性和隔離性有關。
在同一個事務内，你可以運作多個SQL查詢來讀取、建立、更新和删除資料。當兩個事務使用相同的資料，麻煩就來了。經典的例子是從賬戶A到賬戶B的彙款。假設有2個事務：
事務1（T1）從賬戶A取出100美元給賬戶B
事務2（T2）從賬戶A取出50美元給賬戶B
我們回來看看ACID屬性：
原子性確定不管 T1 期間發生什麼（伺服器崩潰、網絡中斷…），你不能出現賬戶A 取走了100美元但沒有給賬戶B 的現象（這就是資料不一緻狀态）。
隔離性確定如果 T1 和 T2 同時發生，最終A将減少150美元，B将得到150美元，而不是其他結果，比如因為 T2 部分抹除了 T1 的行為，A減少150美元而B隻得到50美元（這也是不一緻狀态）。
持久性確定如果 T1 剛剛送出，資料庫就發生崩潰，T1 不會消失得無影無蹤。
一緻性確定錢不會在系統内生成或滅失。
[以下部分不重要，可以跳過]
現代資料庫不會使用純粹的隔離作為預設模式，因為它會帶來巨大的性能消耗。SQL一般定義4個隔離級别：
串行化(Serializable，SQLite預設模式）：最進階别的隔離。兩個同時發生的事務100%隔離，每個事務有自己的『世界』。
可重複讀（Repeatable read，MySQL預設模式）：每個事務有自己的『世界』，除了一種情況。如果一個事務成功執行并且添加了新資料，這些資料對其他正在執行的事務是可見的。但是如果事務成功修改了一條資料，修改結果對正在運作的事務不可見。是以，事務之間隻是在新資料方面突破了隔離，對已存在的資料仍舊隔離。
舉個例子，如果事務A運作”SELECT count(1) from TABLE_X” ，然後事務B在 TABLE_X 加入一條新資料并送出，當事務A再運作一次 count(1)結果不會是一樣的。
這叫幻讀（phantom read）。
讀取已送出（Read committed，Oracle、PostgreSQL、SQL Server預設模式）：可重複讀+新的隔離突破。如果事務A讀取了資料D，然後資料D被事務B修改（或删除）并送出，事務A再次讀取資料D時資料的變化（或删除）是可見的。
這叫不可重複讀（non-repeatable read）。
讀取未送出（Read uncommitted）：最低級别的隔離，是讀取已送出+新的隔離突破。如果事務A讀取了資料D，然後資料D被事務B修改（但并未送出，事務B仍在運作中），事務A再次讀取資料D時，資料修改是可見的。如果事務B復原，那麼事務A第二次讀取的資料D是無意義的，因為那是事務B所做的從未發生的修改（已經復原了嘛）。
這叫髒讀（dirty read）。
多數資料庫添加了自定義的隔離級别（比如 PostgreSQL、Oracle、SQL Server的快照隔離），而且并沒有實作SQL規範裡的所有級别（尤其是讀取未送出級别）。
預設的隔離級别可以由使用者/開發者在建立連接配接時覆寫（隻需要增加很簡單的一行代碼）。
確定隔離性、一緻性和原子性的真正問題是對相同資料的寫操作（增、更、删）：
如果所有事務隻是讀取資料，它們可以同時工作，不會更改另一個事務的行為。
如果（至少）有一個事務在修改其他事務讀取的資料，資料庫需要找個辦法對其它事務隐藏這種修改。而且，它還需要確定這個修改操作不會被另一個看不到這些資料修改的事務擦除。
這個問題叫并發控制。
最簡單的解決辦法是依次執行每個事務（即順序執行），但這樣就完全沒有伸縮性了，在一個多處理器/多核伺服器上隻有一個核心在工作，效率很低。
理想的辦法是，每次一個事務建立或取消時：
監控所有事務的所有操作
檢查是否2個（或更多）事務的部分操作因為讀取/修改相同的資料而存在沖突
重新編排沖突事務中的操作來減少沖突的部分
按照一定的順序執行沖突的部分（同時非沖突事務仍然在并發運作）
考慮事務有可能被取消
用更正規的說法，這是對沖突的排程問題。更具體點兒說，這是個非常困難而且CPU開銷很大的優化問題。企業級資料庫無法承擔等待幾個小時，來尋找每個新事務活動最好的排程，是以就使用不那麼理想的方式以避免更多的時間浪費在解決沖突上。
為了解決這個問題，多數資料庫使用鎖和/或資料版本控制。這是個很大的話題，我會集中探讨鎖，和一點點資料版本控制。
如果一個事務需要一條資料
它就把資料鎖住
如果另一個事務也需要這條資料
它就必須要等第一個事務釋放這條資料
這個鎖叫排他鎖。
但是對一個僅僅讀取資料的事務使用排他鎖非常昂貴，因為這會迫使其它隻需要讀取相同資料的事務等待。是以就有了另一種鎖，共享鎖。
共享鎖是這樣的：
如果一個事務隻需要讀取資料A
它會給資料A加上『共享鎖』并讀取
如果第二個事務也需要僅僅讀取資料A
它會給資料A加上『共享鎖』并讀取
如果第三個事務需要修改資料A
它會給資料A加上『排他鎖』，但是必須等待另外兩個事務釋放它們的共享鎖。
同樣的，如果一塊資料被加上排他鎖，一個隻需要讀取該資料的事務必須等待排他鎖釋放才能給該資料加上共享鎖。
鎖管理器是添加和釋放鎖的程序，在内部用一個哈希表儲存鎖資訊（關鍵字是被鎖的資料），并且了解每一塊資料是：
被哪個事務加的鎖
哪個事務在等待資料解鎖
但是使用鎖會導緻一種情況，2個事務永遠在等待一塊資料：
在本圖中：
事務A 給 資料1 加上排他鎖并且等待擷取資料2
事務B 給 資料2 加上排他鎖并且等待擷取資料1
這叫死鎖。
在死鎖發生時，鎖管理器要選擇取消（復原）一個事務，以便消除死鎖。這可是個艱難的決定：
殺死資料修改量最少的事務（這樣能減少復原的成本）？
殺死持續時間最短的事務，因為其它事務的使用者等的時間更長？
殺死能用更少時間結束的事務（避免可能的資源饑荒）？
一旦發生復原，有多少事務會受到復原的影響？
在作出選擇之前，鎖管理器需要檢查是否有死鎖存在。
哈希表可以看作是個圖表（見上文圖），圖中出現循環就說明有死鎖。由于檢查循環是昂貴的（所有鎖組成的圖表是很龐大的），經常會通過簡單的途徑解決：使用逾時設定。如果一個鎖在逾時時間内沒有加上，那事務就進入死鎖狀态。
鎖管理器也可以在加鎖之前檢查該鎖會不會變成死鎖，但是想要完美的做到這一點還是很昂貴的。是以這些預檢經常設定一些基本規則。
實作純粹的隔離最簡單的方法是：事務開始時擷取鎖，結束時釋放鎖。就是說，事務開始前必須等待確定自己能加上所有的鎖，當事務結束時釋放自己持有的鎖。這是行得通的，但是為了等待所有的鎖，大量的時間被浪費了。
更快的方法是兩段鎖協定（Two-Phase Locking Protocol，由 DB2 和 SQL Server使用），在這裡，事務分為兩個階段：
成長階段：事務可以獲得鎖，但不能釋放鎖。
收縮階段：事務可以釋放鎖（對于已經處理完而且不會再次處理的資料），但不能獲得新鎖。
這兩條簡單規則背後的原理是：
釋放不再使用的鎖，來降低其它事務的等待時間
防止發生這類情況：事務最初獲得的資料，在事務開始後被修改，當事務重新讀取該資料時發生不一緻。
這個規則可以很好地工作，但有個例外：如果修改了一條資料、釋放了關聯的鎖後，事務被取消（復原），而另一個事務讀到了修改後的值，但最後這個值卻被復原。為了避免這個問題，所有獨占鎖必須在事務結束時釋放。
當然了，真實的資料庫使用更複雜的系統，涉及到更多類型的鎖（比如意向鎖，intention locks）和更多的粒度（行級鎖、頁級鎖、分區鎖、表鎖、表空間鎖），但是道理是相同的。
我隻探讨純粹基于鎖的方法，資料版本控制是解決這個問題的另一個方法。
版本控制是這樣的：
每個事務可以在相同時刻修改相同的資料
每個事務有自己的資料拷貝（或者叫版本）
如果2個事務修改相同的資料，隻接受一個修改，另一個将被拒絕，相關的事務復原（或重新運作）
這将提高性能，因為：
讀事務不會阻塞寫事務
寫事務不會阻塞讀
沒有『臃腫緩慢』的鎖管理器帶來的額外開銷
除了兩個事務寫相同資料的時候，資料版本控制各個方面都比鎖表現得更好。隻不過，你很快就會發現磁盤空間消耗巨大。
資料版本控制和鎖機制是兩種不同的見解：樂觀鎖和悲觀鎖。兩者各有利弊，完全取決于使用場景（讀多還是寫多）。關于資料版本控制，我推薦這篇非常優秀的文章，講的是PostgreSQL如何實作多版本并發控制的。
一些資料庫，比如DB2（直到版本 9.7）和 SQL Server（不含快照隔離）僅使用鎖機制。其他的像PostgreSQL, MySQL 和 Oracle 使用鎖和滑鼠版本控制混合機制。我不知道是否有僅用版本控制的資料庫（如果你知道請告訴我）。
[2015-08-20更新]一名讀者告訴我：
Firebird 和 Interbase 用不帶鎖的版本控制。
版本控制對索引的影響挺有趣的：有時唯一索引會出現重複，索引的條目會多于表行數，等等。
如果你讀過不同級别的隔離那部分内容，你會知道，提高隔離級别就會增加鎖的數量和事務等待加鎖的時間。這就是為什麼多數資料庫預設不會使用最進階别的隔離（即串行化）。
當然，你總是可以自己去主流資料庫（像MySQL, PostgreSQL 或 Oracle）的文檔裡查一下。
日志管理器
我們已經知道，為了提升性能，資料庫把資料儲存在記憶體緩沖區内。但如果當事務送出時伺服器崩潰，崩潰時還在記憶體裡的資料會丢失，這破壞了事務的持久性。
你可以把所有資料都寫在磁盤上，但是如果伺服器崩潰，最終資料可能隻有部分寫入磁盤，這破壞了事務的原子性。
事務作出的任何修改必須是或者撤銷，或者完成。
有 2 個辦法解決這個問題：
影子副本/頁（Shadow copies/pages）：每個事務建立自己的資料庫副本（或部分資料庫的副本），并基于這個副本來工作。一旦出錯，這個副本就被移除；一旦成功，資料庫立即使用檔案系統的一個把戲，把副本替換到資料中，然後删掉『舊』資料。
事務日志（Transaction log）：事務日志是一個存儲空間，在每次寫盤之前，資料庫在事務日志中寫入一些資訊，這樣當事務崩潰或復原，資料庫知道如何移除或完成尚未完成的事務。
WAL（預寫式日志）
影子副本/頁在運作較多事務的大型資料庫時制造了大量磁盤開銷，是以現代資料庫使用事務日志。事務日志必須儲存在穩定的存儲上，我不會深挖存儲技術，但至少RAID磁盤是必須的，以防磁盤故障。
多數資料庫（至少是Oracle, SQL Server, DB2, PostgreSQL, MySQL 和 SQLite) 使用預寫日志協定（Write-Ahead Logging protocol ，WAL）來處理事務日志。WAL協定有 3 個規則：
1) 每個對資料庫的修改都産生一條日志記錄，在資料寫入磁盤之前日志記錄必須寫入事務日志。
2) 日志記錄必須按順序寫入；記錄 A 發生在記錄 B 之前，則 A 必須寫在 B 之前。
3) 當一個事務送出時，在事務成功之前，送出順序必須寫入到事務日志。
這個工作由日志管理器完成。簡單的了解就是，日志管理器處于緩存管理器（cache manager）和資料通路管理器（data access manager，負責把資料寫入磁盤）之間，每個 update / delete / create / commit / rollback 操作在寫入磁盤之前先寫入事務日志。簡單，對吧？
回答錯誤！ 我們研究了這麼多内容，現在你應該知道與資料庫相關的每一件事都帶着『資料庫效應』的詛咒。好吧，我們說正經的，問題在于，如何找到寫日志的同時保持良好的性能的方法。如果事務日志寫得太慢，整體都會慢下來。
ARIES
1992年，IBM 研究人員『發明』了WAL的增強版，叫 ARIES。ARIES 或多或少地在現代資料庫中使用，邏輯未必相同，但AIRES背後的概念無處不在。我給發明加了引号是因為，按照MIT這門課的說法，IBM 的研究人員『僅僅是寫了事務恢複的最佳實踐方法』。AIRES 論文發表的時候我才 5 歲，我不關心那些酸溜溜的科研人員老掉牙的閑言碎語。事實上，我提及這個典故，是在開始探讨最後一個技術點前讓你輕松一下。我閱讀過這篇 ARIES 論文 的大量篇幅，發現它很有趣。在這一部分我隻是簡要的談一下 ARIES，不過我強烈建議，如果你想了解真正的知識，就去讀那篇論文。
ARIES 代表『資料庫恢複原型算法』（Algorithms for Recovery and Isolation Exploiting Semantics）。
這個技術要達到一個雙重目标：
1) 寫日志的同時保持良好性能
2) 快速和可靠的資料恢複
有多個原因讓資料庫不得不復原事務：
因為使用者取消
因為伺服器或網絡故障
因為事務破壞了資料庫完整性（比如一個列有唯一性限制而事務添加了重複值）
有時候（比如網絡出現故障），資料庫可以恢複事務。
這怎麼可能呢？為了回答這個問題，我們需要了解日志裡儲存的資訊。
事務的每一個操作（增/删/改）産生一條日志，由如下内容組成：
LSN：一個唯一的日志序列号（Log Sequence Number）。LSN是按時間順序配置設定的 * ，這意味着如果操作 A 先于操作 B，log A 的 LSN 要比 log B 的 LSN 小。
TransID：産生操作的事務ID。
PageID：被修改的資料在磁盤上的位置。磁盤資料的最小機關是頁，是以資料的位置就是它所處頁的位置。
PrevLSN：同一個事務産生的上一條日志記錄的連結。
UNDO：取消本次操作的方法。
比如，如果操作是一次更新，UNDO将或者儲存元素更新前的值/狀态（實體UNDO），或者回到原來狀态的反向操作（邏輯UNDO） **。
REDO：重複本次操作的方法。 同樣的，有 2 種方法：或者儲存操作後的元素值/狀态，或者儲存操作本身以便重複。
…：（供您參考，一個 ARIES 日志還有 2 個字段：UndoNxtLSN 和 Type）。
進一步說，磁盤上每個頁（儲存資料的，不是儲存日志的）都記錄着最後一個修改該資料操作的LSN。
*LSN的配置設定其實更複雜，因為它關系到日志存儲的方式。但道理是相同的。
** ARIES 隻使用邏輯UNDO，因為處理實體UNDO太過混亂了。
注：據我所知，隻有 PostgreSQL 沒有使用UNDO，而是用一個垃圾回收服務來删除舊版本的資料。這個跟 PostgreSQL 對資料版本控制的實作有關。
為了更好的說明這一點，這有一個簡單的日志記錄示範圖，是由查詢 “UPDATE FROM PERSON SET AGE = 18;” 産生的，我們假設這個查詢是事務18執行的。【譯者注： SQL 語句原文如此，應該是作者筆誤 】
每條日志都有一個唯一的LSN，連結在一起的日志屬于同一個事務。日志按照時間順序連結（連結清單的最後一條日志是最後一個操作産生的）。
日志緩沖區
為了防止寫日志成為主要的瓶頸，資料庫使用了日志緩沖區。
當查詢執行器要求做一次修改：
1) 緩存管理器将修改存入自己的緩沖區；
2) 日志管理器将相關的日志存入自己的緩沖區；
3) 到了這一步，查詢執行器認為操作完成了（是以可以請求做另一次修改）；
4) 接着（不久以後）日志管理器把日志寫入事務日志，什麼時候寫日志由某算法來決定。
5) 接着（不久以後）緩存管理器把修改寫入磁盤，什麼時候寫盤由某算法來決定。
當事務送出，意味着事務每一個操作的 1 2 3 4 5 步驟都完成了。寫事務日志是很快的，因為它隻是『在事務日志某處增加一條日志』；而資料寫盤就更複雜了，因為要用『能夠快速讀取的方式寫入資料』。
STEAL 和 FORCE 政策
出于性能方面的原因，第 5 步有可能在送出之後完成，因為一旦發生崩潰，還有可能用REDO日志恢複事務。這叫做 NO-FORCE政策。
資料庫可以選擇FORCE政策（比如第 5 步在送出之前必須完成）來降低恢複時的負載。
另一個問題是，要選擇資料是一步步的寫入（STEAL政策），還是緩沖管理器需要等待送出指令來一次性全部寫入（NO-STEAL政策）。選擇STEAL還是NO-STEAL取決于你想要什麼：快速寫入但是從 UNDO 日志恢複緩慢，還是快速恢複。
總結一下這些政策對恢複的影響：
STEAL/NO-FORCE 需要 UNDO 和 REDO: 性能高，但是日志和恢複過程更複雜 (比如 ARIES)。多數資料庫選擇這個政策。 注：這是我從多個學術論文和教程裡看到的，但并沒有看到官方文檔裡顯式說明這一點。
STEAL/ FORCE 隻需要 UNDO.
NO-STEAL/NO-FORCE 隻需要 REDO.
NO-STEAL/FORCE 什麼也不需要: 性能最差，而且需要巨大的記憶體。
Ok，有了不錯的日志，我們來用用它們！
假設新來的實習生讓資料庫崩潰了（首要規矩：永遠是實習生的錯。），你重新開機了資料庫，恢複過程開始了。
ARIES從崩潰中恢複有三個階段：
1) 分析階段：恢複程序讀取全部事務日志，來重建崩潰過程中所發生事情的時間線，決定哪個事務要復原（所有未送出的事務都要復原）、崩潰時哪些資料需要寫盤。
2) Redo階段：這一關從分析中選中的一條日志記錄開始，使用 REDO 來将資料庫恢複到崩潰之前的狀态。
在REDO階段，REDO日志按照時間順序處理（使用LSN）。
對每一條日志，恢複程序需要讀取包含資料的磁盤頁LSN。
如果LSN（磁盤頁）>= LSN（日志記錄），說明資料已經在崩潰前寫到磁盤（但是值已經被日志之後、崩潰之前的某個操作覆寫），是以不需要做什麼。
如果LSN（磁盤頁）< LSN（日志記錄），那麼磁盤上的頁将被更新。
即使将被復原的事務，REDO也是要做的，因為這樣簡化了恢複過程（但是我相信現代資料庫不會這麼做的）。
3) Undo階段：這一階段復原所有崩潰時未完成的事務。復原從每個事務的最後一條日志開始，并且按照時間倒序處理UNDO日志（使用日志記錄的PrevLSN）。
恢複過程中，事務日志必須留意恢複過程的操作，以便寫入磁盤的資料與事務日志相一緻。一個解決辦法是移除被取消的事務産生的日志記錄，但是這個太困難了。相反，ARIES在事務日志中記錄補償日志，來邏輯上删除被取消的事務的日志記錄。
當事務被『手工』取消，或者被鎖管理器取消（為了消除死鎖），或僅僅因為網絡故障而取消，那麼分析階段就不需要了。對于哪些需要 REDO 哪些需要 UNDO 的資訊在 2 個記憶體表中：
事務表（儲存目前所有事務的狀态）
髒頁表（儲存哪些資料需要寫入磁盤）
當新的事務産生時，這兩個表由緩存管理器和事務管理器更新。因為是在記憶體中，當資料庫崩潰時它們也被破壞掉了。
分析階段的任務就是在崩潰之後，用事務日志中的資訊重建上述的兩個表。為了加快分析階段，ARIES提出了一個概念：檢查點（check point），就是不時地把事務表和髒頁表的内容，還有此時最後一條LSN寫入磁盤。那麼在分析階段當中，隻需要分析這個LSN之後的日志即可。
寫這篇文章之前，我知道這個題目有多大，也知道寫這樣一篇深入的文章會相當耗時。最後證明我過于樂觀了，實際上花了兩倍于預期的時間，但是我學到了很多。
如果你想很好地了解資料庫，我推薦這篇研究論文：《資料庫系統架構》，對資料庫有很好的介紹（共110頁），而且非計算機專業人士也能讀懂。這篇論文出色的幫助我制定了本文的寫作計劃，它沒有像本文那樣專注于資料結構和算法，更多的講了架構方面的概念。
如果你仔細閱讀了本文，你現在應該了解一個資料庫是多麼的強大了。鑒于文章很長，讓我來提醒你我們都學到了什麼：
B+樹索引概述
資料庫的全局概述
基于成本的優化概述，特别專注了聯接運算
緩沖池管理概述
事務管理概述
但是，資料庫包含了更多的聰明巧技。比如，我并沒有談到下面這些棘手的問題：
如何管理資料庫叢集和全局事務
如何在資料庫運作的時候産生快照
如何高效地存儲（和壓縮）資料
如何管理記憶體
是以，當你不得不在問題多多的 NoSQL資料庫和堅如磐石的關系型資料庫之間抉擇的時候，要三思而行。不要誤會，某些 NoSQL資料庫是很棒的，但是它們畢竟還年輕，隻是解決了少量應用關注的一些特定問題。
最後說一句，如果有人問你資料庫的原理是什麼，你不用逃之夭夭，現在你可以回答：
或者，就讓他/她來看本文吧。
參考文獻：
1.《關系型資料庫的原理》。
![【MySQL資料庫】資料庫索引事務1.索引2.事務[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)