數(shù)據(jù)庫原理解釋

一提到關(guān)系型數(shù)據(jù)庫，我禁不住想：有些東西被忽視了宴抚。關(guān)系型數(shù)據(jù)庫無處不在，而且種類繁多甫煞，從小巧實用的 SQLite 到強大的 Teradata 菇曲。但很少有文章講解數(shù)據(jù)庫是如何工作的。你可以自己谷歌/百度一下『關(guān)系型數(shù)據(jù)庫原理』抚吠，看看結(jié)果多么的稀少【譯者注：百度為您找到相關(guān)結(jié)果約1,850,000個…】常潮，而且找到的那些文章都很短。現(xiàn)在如果你查找最近時髦的技術(shù)（大數(shù)據(jù)埃跷、NoSQL或JavaScript）蕊玷，你能找到更多深入探討它們?nèi)绾喂ぷ鞯奈恼隆?/p>

難道關(guān)系型數(shù)據(jù)庫已經(jīng)太古老太無趣，除了大學教材弥雹、研究文獻和書籍以外垃帅，沒人愿意講了嗎？

image

作為一個開發(fā)人員剪勿，我不喜歡用我不明白的東西贸诚。而且，數(shù)據(jù)庫已經(jīng)使用了40年之久厕吉，一定有理由的酱固。多年以來，我花了成百上千個小時來真正領(lǐng)會這些我每天都在用的头朱、古怪的黑盒子运悲。關(guān)系型數(shù)據(jù)庫非常有趣，因為它們是基于實用而且可復用的概念项钮。如果你對了解一個數(shù)據(jù)庫感興趣班眯，但是從未有時間或意愿來刻苦鉆研這個內(nèi)容廣泛的課題，你應(yīng)該喜歡這篇文章烁巫。

雖然本文標題很明確署隘，但我的目的并不是講如何使用數(shù)據(jù)庫擒滑。因此况鸣，你應(yīng)該已經(jīng)掌握怎么寫一個簡單的 join query（聯(lián)接查詢）和CRUD操作（創(chuàng)建讀取更新刪除），否則你可能無法理解本文幼衰。這是唯一需要你了解的阿弃，其他的由我來講解诊霹。

我會從一些計算機科學方面的知識談起羞延，比如時間復雜度。我知道有些人討厭這個概念畅哑，但是沒有它你就不能理解數(shù)據(jù)庫內(nèi)部的巧妙之處肴楷。由于這是個很大的話題，我將集中探討我認為必要的內(nèi)容：數(shù)據(jù)庫處理SQL查詢的方式荠呐。我僅僅介紹數(shù)據(jù)庫背后的基本概念赛蔫，以便在讀完本文后你會對底層到底發(fā)生了什么有個很好的了解。

【譯者注：關(guān)于時間復雜度泥张。計算機科學中呵恢，算法的時間復雜度是一個函數(shù)，它定量描述了該算法的運行時間媚创。如果不了解這個概念建議先看看維基或百度百科渗钉，對于理解文章下面的內(nèi)容很有幫助】

由于本文是個長篇技術(shù)文章，涉及到很多算法和數(shù)據(jù)結(jié)構(gòu)知識钞钙，你盡可以慢慢讀鳄橘。有些概念比較難懂，你可以跳過芒炼，不影響理解整體內(nèi)容瘫怜。

這篇文章大約分為3個部分：

底層和上層數(shù)據(jù)庫組件概況
查詢優(yōu)化過程概況
事務(wù)和緩沖池管理概況

回到基礎(chǔ)

很久很久以前（在一個遙遠而又遙遠的星系……)，開發(fā)者必須確切地知道他們的代碼需要多少次運算本刽。他們把算法和數(shù)據(jù)結(jié)構(gòu)牢記于心鲸湃，因為他們的計算機運行緩慢，無法承受對CPU和內(nèi)存的浪費子寓。

在這一部分暗挑，我將提醒大家一些這類的概念，因為它們對理解數(shù)據(jù)庫至關(guān)重要斜友。我還會介紹數(shù)據(jù)庫索引的概念炸裆。

O(1) vs O(n^2)

現(xiàn)今很多開發(fā)者不關(guān)心時間復雜度……他們是對的。

但是當你應(yīng)對大量的數(shù)據(jù)（我說的可不只是成千上萬哈）或者你要爭取毫秒級操作鲜屏，那么理解這個概念就很關(guān)鍵了烹看。而且你猜怎么著，數(shù)據(jù)庫要同時處理這兩種情景墙歪！我不會占用你太長時間听系，只要你能明白這一點就夠了贝奇。這個概念在下文會幫助我們理解什么是基于成本的優(yōu)化虹菲。

概念

時間復雜度用來檢驗?zāi)硞€算法處理一定量的數(shù)據(jù)要花多長時間。為了描述這個復雜度掉瞳，計算機科學家使用數(shù)學上的『簡明解釋算法中的大O符號』毕源。這個表示法用一個函數(shù)來描述算法處理給定的數(shù)據(jù)需要多少次運算浪漠。

比如，當我說『這個算法是適用 O(某函數(shù)())』霎褐，我的意思是對于某些數(shù)據(jù)址愿，這個算法需要某函數(shù)(數(shù)據(jù)量) 次運算來完成。

重要的不是數(shù)據(jù)量冻璃，而是當數(shù)據(jù)量增加時運算如何增加响谓。時間復雜度不會給出確切的運算次數(shù)，但是給出的是一種理念省艳。

image

圖中可以看到不同類型的復雜度的演變過程娘纷，我用了對數(shù)尺來建這個圖。具體點兒說跋炕，數(shù)據(jù)量以很快的速度從1條增長到10億條赖晶。我們可得到如下結(jié)論：

綠：O(1)或者叫常數(shù)階復雜度，保持為常數(shù)（要不人家就不會叫常數(shù)階復雜度了）辐烂。
紅：O(log(n))對數(shù)階復雜度遏插，即使在十億級數(shù)據(jù)量時也很低。
粉：最糟糕的復雜度是 O(n^2)纠修，平方階復雜度胳嘲，運算數(shù)快速膨脹。
黑和藍：另外兩種復雜度（的運算數(shù)也是）快速增長分瘾。

例子

數(shù)據(jù)量低時胎围，O(1) 和 O(n^2)的區(qū)別可以忽略不計。比如德召，你有個算法要處理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) 的區(qū)別似乎很大（4百萬）,但你最多損失 2 毫秒，只是一眨眼的功夫上岗。確實福荸，當今處理器每秒可處理上億次的運算。這就是為什么性能和優(yōu)化在很多IT項目中不是問題肴掷。

我說過敬锐，面臨海量數(shù)據(jù)的時候，了解這個概念依然很重要呆瞻。如果這一次算法需要處理 1,000,000 條元素（這對數(shù)據(jù)庫來說也不算大）台夺。

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) 算法的話你有時間喝杯咖啡（甚至再續(xù)一杯２椤）。如果在數(shù)據(jù)量后面加個0，那你就可以去睡大覺了滚朵。

繼續(xù)深入

為了讓你能明白

搜索一個好的哈希表會得到 O(1) 復雜度
搜索一個均衡的樹會得到 O(log(n)) 復雜度
搜索一個陣列會得到 O(n) 復雜度
最好的排序算法具有 O(n*log(n)) 復雜度
糟糕的排序算法具有 O(n^2) 復雜度

注：在接下來的部分冤灾，我們將會研究這些算法和數(shù)據(jù)結(jié)構(gòu)。

有多種類型的時間復雜度

一般情況場景
最佳情況場景
最差情況場景

時間復雜度經(jīng)常處于最差情況場景辕近。

這里我只探討時間復雜度韵吨，但復雜度還包括：

算法的內(nèi)存消耗
算法的磁盤 I/O 消耗

當然還有比 n^2 更糟糕的復雜度，比如：

n^4：差勁移宅！我將要提到的一些算法具備這種復雜度归粉。
3^n：更差勁！本文中間部分研究的一些算法中有一個具備這種復雜度（而且在很多數(shù)據(jù)庫中還真的使用了）漏峰。
階乘 n：你永遠得不到結(jié)果盏浇，即便在少量數(shù)據(jù)的情況下。
n^n：如果你發(fā)展到這種復雜度了芽狗，那你應(yīng)該問問自己IT是不是你的菜绢掰。

注：我并沒有給出『大O表示法』的真正定義，只是利用這個概念童擎〉尉ⅲ可以看看維基百科上的這篇文章。

合并排序

當你要對一個集合排序時你怎么做顾复？什么班挖？調(diào)用 sort() 函數(shù)……好吧，算你對了……但是對于數(shù)據(jù)庫芯砸，你需要理解這個 sort() 函數(shù)的工作原理萧芙。

優(yōu)秀的排序算法有好幾個，我側(cè)重于最重要的一種：合并排序假丧。你現(xiàn)在可能還不了解數(shù)據(jù)排序有什么用双揪，但看完查詢優(yōu)化部分后你就會知道了。再者包帚，合并排序有助于我們以后理解數(shù)據(jù)庫常見的聯(lián)接操作渔期，即合并聯(lián)接。

合并

與很多有用的算法類似渴邦，合并排序基于這樣一個技巧：將 2 個大小為 N/2 的已排序序列合并為一個 N 元素已排序序列僅需要 N 次操作疯趟。這個方法叫做合并。

我們用個簡單的例子來看看這是什么意思：

image

通過此圖你可以看到谋梭，在 2 個 4元素序列里你只需要迭代一次信峻，就能構(gòu)建最終的8元素已排序序列，因為兩個4元素序列已經(jīng)排好序了：

1. 在兩個序列中瓮床，比較當前元素（當前=頭一次出現(xiàn)的第一個）
1. 然后取出最小的元素放進8元素序列中
1. 找到（兩個）序列的下一個元素盹舞，(比較后)取出最小的
重復1姨夹、2、3步驟矾策，直到其中一個序列中的最后一個元素
然后取出另一個序列剩余的元素放入8元素序列中。

這個方法之所以有效峭沦，是因為兩個4元素序列都已經(jīng)排好序贾虽，你不需要再『回到』序列中查找比較。

【譯者注：合并排序詳細原理吼鱼，其中一個動圖（原圖較長蓬豁，我做了刪減）清晰的演示了上述合并排序的過程，而原文的敘述似乎沒有這么清晰菇肃，不動戳大地粪。】

image

既然我們明白了這個技巧琐谤，下面就是我的合并排序偽代碼蟆技。

array  mergeSort(array  a)

 if(length(a)==1)

      return  a[0];

 end  if

 //recursive calls

 [left_array right_array]  :=  split_into_2_equally_sized_arrays(a);

 array  new_left_array  :=  mergeSort(left_array);

 array  new_right_array  :=  mergeSort(right_array);

 //merging the 2 small ordered arrays into a big one

 array  result  :=  merge(new_left_array,new_right_array);

 return  result;

合并排序是把問題拆分為小問題，通過解決小問題來解決最初的問題（注：這種算法叫分治法斗忌，即『分而治之质礼、各個擊破』）。如果你不懂织阳，不用擔心眶蕉，我第一次接觸時也不懂。如果能幫助你理解的話唧躲，我認為這個算法是個兩步算法：

拆分階段造挽，將序列分為更小的序列
排序階段，把小的序列合在一起（使用合并算法）來構(gòu)成更大的序列

拆分階段

image

在拆分階段過程中弄痹，使用3個步驟將序列分為一元序列饭入。步驟數(shù)量的值是 log(N) （因為 N=8, log(N)=3）「卣妫【譯者注：底數(shù)為2圣拄，下文有說明】

我怎么知道這個的？

~~我是天才毁欣！~~一句話：數(shù)學庇谆。道理是每一步都把原序列的長度除以2，步驟數(shù)就是你能把原序列長度除以2的次數(shù)凭疮。這正好是對數(shù)的定義（在底數(shù)為2時）饭耳。

排序階段

image

在排序階段，你從一元序列開始执解。在每一個步驟中寞肖，你應(yīng)用多次合并操作纲酗，成本一共是 N=8 次運算。

第一步新蟆，4 次合并觅赊，每次成本是 2 次運算。
第二步琼稻，2 次合并吮螺，每次成本是 4 次運算。
第三步帕翻，1 次合并鸠补，成本是 8 次運算。

因為有 log(N) 個步驟嘀掸，整體成本是 N*log(N) 次運算紫岩。

【譯者注：這個完整的動圖演示了拆分和排序的全過程，不動戳大睬塌∪颍】

image

合并排序的強大之處

為什么這個算法如此強大？

因為：

你可以更改算法揩晴，以便于節(jié)省內(nèi)存空間梨与，方法是不創(chuàng)建新的序列而是直接修改輸入序列。
注：這種算法叫『原地算法』(in-place algorithm)
你可以更改算法文狱，以便于同時使用磁盤空間和少量內(nèi)存而避免巨量磁盤 I/O粥鞋。方法是只向內(nèi)存中加載當前處理的部分。在僅僅100MB的內(nèi)存緩沖區(qū)內(nèi)排序一個幾個GB的表時瞄崇，這是個很重要的技巧呻粹。
注：這種算法叫『外部排序』(external sorting)。
你可以更改算法苏研，以便于在多處理器/多線程/多服務(wù)器上運行等浊。
比如，分布式合并排序是Hadoop（那個著名的大數(shù)據(jù)框架）的關(guān)鍵組件之一摹蘑。
這個算法可以點石成金（事實如此３镅唷）

這個排序算法在大多數(shù)（如果不是全部的話）數(shù)據(jù)庫中使用，但是它并不是唯一算法衅鹿。如果你想多了解一些撒踪，你可以看看這篇論文，探討的是數(shù)據(jù)庫中常用排序算法的優(yōu)勢和劣勢大渤。

陣列制妄，樹和哈希表

既然我們已經(jīng)了解了時間復雜度和排序背后的理念，我必須要向你介紹3種數(shù)據(jù)結(jié)構(gòu)了泵三。這個很重要耕捞，因為它們是現(xiàn)代數(shù)據(jù)庫的支柱衔掸。我還會介紹數(shù)據(jù)庫索引的概念。

陣列

二維陣列是最簡單的數(shù)據(jù)結(jié)構(gòu)俺抽。一個表可以看作是個陣列敞映，比如：

image

這個二維陣列是帶有行與列的表：

每個行代表一個主體
列用來描述主體的特征
每個列保存某一種類型對數(shù)據(jù)（整數(shù)、字符串磷斧、日期……）

雖然用這個方法保存和視覺化數(shù)據(jù)很棒振愿，但是當你要查找特定的值它就很糟糕了。舉個例子绽诚，如果你要找到所有在 UK 工作的人牲平，你必須查看每一行以判斷該行是否屬于 UK 。這會造成 N 次運算的成本（N 等于行數(shù)），還不賴嘛癌蓖，但是有沒有更快的方法呢？這時候樹就可以登場了（或開始起作用了）钧敞。

樹和數(shù)據(jù)庫索引

二叉查找樹是帶有特殊屬性的二叉樹糊渊，每個節(jié)點的關(guān)鍵字必須：

比保存在左子樹的任何鍵值都要大
比保存在右子樹的任何鍵值都要小

【譯者注：binary search tree，二叉查找樹/二叉搜索樹销凑，或稱 Binary Sort Tree 二叉排序樹丛晌。見百度百科】

概念

image.png

這個樹有 N=15 個元素。比方說我要找208：

我從鍵值為 136 的根開始斗幼，因為 136<208澎蛛，我去找節(jié)點136的右子樹。
398>208蜕窿，所以我去找節(jié)點398的左子樹
250>208谋逻，所以我去找節(jié)點250的左子樹
200<208，所以我去找節(jié)點200的右子樹桐经。但是 200 沒有右子樹毁兆，值不存在（因為如果存在，它會在 200 的右子樹）

現(xiàn)在比方說我要找40

我從鍵值為136的根開始阴挣，因為 136>40气堕，所以我去找節(jié)點136的左子樹。
80>40畔咧，所以我去找節(jié)點 80 的左子樹
40=40茎芭，節(jié)點存在。我抽取出節(jié)點內(nèi)部行的ID（圖中沒有畫）再去表中查找對應(yīng)的 ROW ID誓沸。
知道 ROW ID我就知道了數(shù)據(jù)在表中對精確位置骗爆，就可以立即獲取數(shù)據(jù)。

最后蔽介，兩次查詢的成本就是樹內(nèi)部的層數(shù)摘投。如果你仔細閱讀了合并排序的部分煮寡，你就應(yīng)該明白一共有 log(N)層。所以這個查詢的成本是 log(N)犀呼，不錯靶宜骸！

回到我們的問題

上文說的很抽象外臂，我們回來看看我們的問題坐儿。這次不用傻傻的數(shù)字了，想象一下前表中代表某人的國家的字符串宋光。假設(shè)你有個樹包含表中的列『country』：

如果你想知道誰在 UK 工作
你在樹中查找代表 UK 的節(jié)點
在『UK 節(jié)點』你會找到 UK 員工那些行的位置

這次搜索只需 log(N) 次運算貌矿，而如果你直接使用陣列則需要 N 次運算。你剛剛想象的就是一個數(shù)據(jù)庫索引罪佳。

B+樹索引

查找一個特定值這個樹挺好用逛漫，但是當你需要查找兩個值之間的多個元素時，就會有大麻煩了赘艳。你的成本將是 O(N)酌毡，因為你必須查找樹的每一個節(jié)點，以判斷它是否處于那 2 個值之間（例如蕾管，對樹使用中序遍歷）枷踏。而且這個操作不是磁盤I/O有利的，因為你必須讀取整個樹掰曾。我們需要找到高效的范圍查詢方法旭蠕。為了解決這個問題，現(xiàn)代數(shù)據(jù)庫使用了一種修訂版的樹旷坦，叫做B+樹下梢。在一個B+樹里：

只有最底層的節(jié)點（葉子節(jié)點）才保存信息（相關(guān)表的行位置）
其它節(jié)點只是在搜索中用來指引到正確節(jié)點的。

【譯者注：參考 B+樹塞蹭，二叉樹遍歷維基百科】

image.png

你可以看到孽江，節(jié)點更多了（多了兩倍）。確實番电，你有了額外的節(jié)點岗屏，它們就是幫助你找到正確節(jié)點的『決策節(jié)點』（正確節(jié)點保存著相關(guān)表中行的位置）。但是搜索復雜度還是在 O(log(N))（只多了一層）漱办。一個重要的不同點是这刷，最底層的節(jié)點是跟后續(xù)節(jié)點相連接的。

用這個 B+樹娩井，假設(shè)你要找40到100間的值：

你只需要找 40（若40不存在則找40之后最貼近的值）暇屋，就像你在上一個樹中所做的那樣。
然后用那些連接來收集40的后續(xù)節(jié)點洞辣，直到找到100咐刨。

比方說你找到了 M 個后續(xù)節(jié)點昙衅，樹總共有 N 個節(jié)點。對指定節(jié)點的搜索成本是 log(N)定鸟，跟上一個樹相同而涉。但是當你找到這個節(jié)點，你得通過后續(xù)節(jié)點的連接得到 M 個后續(xù)節(jié)點联予，這需要 M 次運算啼县。那么這次搜索只消耗了 M+log(N) 次運算，區(qū)別于上一個樹所用的 N 次運算沸久。此外季眷，你不需要讀取整個樹（僅需要讀 M+log(N) 個節(jié)點）,這意味著更少的磁盤訪問。如果 M 很芯砜琛（比如 200 行）并且 N 很大（1,000,000）子刮，那結(jié)果就是天壤之別了。

然而還有新的問題（又來了Ｋ薪摺）话告。如果你在數(shù)據(jù)庫中增加或刪除一行（從而在相關(guān)的 B+樹索引里）：

你必須在B+樹中的節(jié)點之間保持順序兼搏，否則節(jié)點會變得一團糟卵慰，你無法從中找到想要的節(jié)點。
你必須盡可能降低B+樹的層數(shù)佛呻，否則 O(log(N)) 復雜度會變成 O(N)裳朋。

換句話說，B+樹需要自我整理和自我平衡吓著。謝天謝地鲤嫡，我們有智能刪除和插入。但是這樣也帶來了成本：在B+樹中绑莺，插入和刪除操作是 O(log(N)) 復雜度暖眼。所以有些人聽到過使用太多索引不是個好主意這類說法。沒錯纺裁，你減慢了快速插入/更新/刪除表中的一個行的操作诫肠，因為數(shù)據(jù)庫需要以代價高昂的每索引 O(log(N)) 運算來更新表的索引。再者欺缘，增加索引意味著給事務(wù)管理器帶來更多的工作負荷（在本文結(jié)尾我們會探討這個管理器）栋豫。

想了解更多細節(jié)，你可以看看 Wikipedia 上這篇關(guān)于B+樹的文章谚殊。如果你想要數(shù)據(jù)庫中實現(xiàn)B+樹的例子丧鸯，看看MySQL核心開發(fā)人員寫的這篇文章和這篇文章。兩篇文章都致力于探討 innoDB(MySQL引擎)如何處理索引嫩絮。

哈希表

我們最后一個重要的數(shù)據(jù)結(jié)構(gòu)是哈希表丛肢。當你想快速查找值時围肥，哈希表是非常有用的。而且摔踱，理解哈希表會幫助我們接下來理解一個數(shù)據(jù)庫常見的聯(lián)接操作虐先，叫做『哈希聯(lián)接』蛹批。這個數(shù)據(jù)結(jié)構(gòu)也被數(shù)據(jù)庫用來保存一些內(nèi)部的東西（比如鎖表或者緩沖池寡键，我們在下文會研究這兩個概念）。

哈希表這種數(shù)據(jù)結(jié)構(gòu)可以用關(guān)鍵字來快速找到一個元素笛厦。為了構(gòu)建一個哈希表，你需要定義：

元素的關(guān)鍵字
關(guān)鍵字的哈希函數(shù)劝贸。關(guān)鍵字計算出來的哈希值給出了元素的位置（叫做哈希桶）姨谷。
關(guān)鍵字比較函數(shù)。一旦你找到正確的哈希桶映九，你必須用比較函數(shù)在桶內(nèi)找到你要的元素梦湘。

一個簡單的例子

我們來看一個形象化的例子：

image

這個哈希表有10個哈希桶。因為我懶件甥，我只給出5個桶捌议，但是我知道你很聰明，所以我讓你想象其它的5個桶引有。我用的哈希函數(shù)是關(guān)鍵字對10取模瓣颅，也就是我只保留元素關(guān)鍵字的最后一位，用來查找它的哈希桶：

如果元素最后一位是 0轿曙，則進入哈希桶0弄捕，
如果元素最后一位是 1僻孝，則進入哈希桶1导帝，
如果元素最后一位是 2，則進入哈希桶2穿铆，
…我用的比較函數(shù)只是判斷兩個整數(shù)是否相等您单。

【譯者注：取模運算】

比方說你要找元素 78：

哈希表計算 78 的哈希碼，等于 8荞雏。
查找哈希桶 8虐秦，找到的第一個元素是 78。
返回元素 78凤优。
查詢僅耗費了 2 次運算（1次計算哈希值悦陋，另一次在哈希桶中查找元素）。

現(xiàn)在筑辨，比方說你要找元素 59：

哈希表計算 59 的哈希碼俺驶，等于9。
查找哈希桶 9棍辕，第一個找到的元素是 99暮现。因為 99 不等于 59还绘，那么 99 不是正確的元素。
用同樣的邏輯栖袋，查找第二個元素(9)拍顷，第三個(79)，……塘幅，最后一個(29)昔案。
元素不存在。
搜索耗費了 7 次運算电媳。

一個好的哈希函數(shù)

你可以看到爱沟，根據(jù)你查找的值，成本并不相同匆背。

如果我把哈希函數(shù)改為關(guān)鍵字對 1,000,000 取模（就是說取后6位數(shù)字）呼伸，第二次搜索只消耗一次運算，因為哈希桶 00059 里面沒有元素钝尸。真正的挑戰(zhàn)是找到好的哈希函數(shù)括享，讓哈希桶里包含非常少的元素。

在我的例子里珍促，找到一個好的哈希函數(shù)很容易铃辖，但這是個簡單的例子。當關(guān)鍵字是下列形式時猪叙，好的哈希函數(shù)就更難找了：

1 個字符串（比如一個人的姓）
2 個字符串（比如一個人的姓和名）
2 個字符串和一個日期（比如一個人的姓娇斩、名和出生年月日）
…

如果有了好的哈希函數(shù)，在哈希表里搜索的時間復雜度是 O(1)穴翩。

陣列 vs 哈希表

為什么不用陣列呢犬第？

嗯，你問得好芒帕。

一個哈希表可以只裝載一半到內(nèi)存歉嗓，剩下的哈希桶可以留在硬盤上。
用陣列的話背蟆，你需要一個連續(xù)內(nèi)存空間鉴分。如果你加載一個大表，很難分配足夠的連續(xù)內(nèi)存空間带膀。
用哈希表的話志珍，你可以選擇你要的關(guān)鍵字（比如，一個人的國家和姓氏）垛叨。

想要更詳細的信息伦糯，你可以閱讀我在Java HashMap 上的文章，是關(guān)于高效哈希表實現(xiàn)的。你不需要了解Java就能理解文章里的概念舔株。

全局概覽

我們已經(jīng)了解了數(shù)據(jù)庫內(nèi)部的基本組件莺琳，現(xiàn)在我們需要回來看看數(shù)據(jù)庫的全貌了。

數(shù)據(jù)庫是一個易于訪問和修改的信息集合载慈。不過簡單的一堆文件也能達到這個效果惭等。事實上，像SQLite這樣最簡單的數(shù)據(jù)庫也只是一堆文件而已办铡，但SQLite是精心設(shè)計的一堆文件辞做，因為它允許你：

使用事務(wù)來確保數(shù)據(jù)的安全和一致性
快速處理百萬條以上的數(shù)據(jù)

數(shù)據(jù)庫一般可以用如下圖形來理解：

image

撰寫這部分之前，我讀過很多書/論文寡具，它們都以自己的方式描述數(shù)據(jù)庫秤茅。所以，我不會特別關(guān)注如何組織數(shù)據(jù)庫或者如何命名各種進程童叠，因為我選擇了自己的方式來描述這些概念以適應(yīng)本文框喳。區(qū)別就是不同的組件，總體思路為：數(shù)據(jù)庫是由多種互相交互的組件構(gòu)成的厦坛。

核心組件：

進程管理器（process manager）：很多數(shù)據(jù)庫具備一個需要妥善管理的進程/線程池五垮。再者，為了實現(xiàn)納秒級操作杜秸，一些現(xiàn)代數(shù)據(jù)庫使用自己的線程而不是操作系統(tǒng)線程放仗。
網(wǎng)絡(luò)管理器（network manager）：網(wǎng)路I/O是個大問題，尤其是對于分布式數(shù)據(jù)庫撬碟。所以一些數(shù)據(jù)庫具備自己的網(wǎng)絡(luò)管理器诞挨。
文件系統(tǒng)管理器（File system manager）：磁盤I/O是數(shù)據(jù)庫的首要瓶頸。具備一個文件系統(tǒng)管理器來完美地處理OS文件系統(tǒng)甚至取代OS文件系統(tǒng)呢蛤，是非常重要的惶傻。
內(nèi)存管理器（memory manager）：為了避免磁盤I/O帶來的性能損失，需要大量的內(nèi)存顾稀。但是如果你要處理大容量內(nèi)存你需要高效的內(nèi)存管理器达罗，尤其是你有很多查詢同時使用內(nèi)存的時候坝撑。
安全管理器（Security Manager）：用于對用戶的驗證和授權(quán)静秆。
客戶端管理器（Client manager）：用于管理客戶端連接着降。
……

工具：

備份管理器（Backup manager）：用于保存和恢復數(shù)據(jù)周瞎。
復原管理器（Recovery manager）：用于崩潰后重啟數(shù)據(jù)庫到一個一致狀態(tài)。
監(jiān)控管理器（Monitor manager）：用于記錄數(shù)據(jù)庫活動信息和提供監(jiān)控數(shù)據(jù)庫的工具请琳。
Administration管理器（Administration manager）：用于保存元數(shù)據(jù)（比如表的名稱和結(jié)構(gòu)）侨拦，提供管理數(shù)據(jù)庫殊橙、模式、表空間的工具∨蚵【譯者注：好吧叠纹，我真的不知道Administration manager該翻譯成什么，有知道的麻煩告知敞葛，不勝感激……】
……

查詢管理器：

查詢解析器（Query parser）：用于檢查查詢是否合法
查詢重寫器（Query rewriter）：用于預優(yōu)化查詢
查詢優(yōu)化器（Query optimizer）：用于優(yōu)化查詢
查詢執(zhí)行器（Query executor）：用于編譯和執(zhí)行查詢

數(shù)據(jù)管理器：

事務(wù)管理器（Transaction manager）：用于處理事務(wù)
緩存管理器（Cache manager）：數(shù)據(jù)被使用之前置于內(nèi)存誉察，或者數(shù)據(jù)寫入磁盤之前置于內(nèi)存
數(shù)據(jù)訪問管理器（Data access manager）：訪問磁盤中的數(shù)據(jù)

在本文剩余部分，我會集中探討數(shù)據(jù)庫如何通過如下進程管理SQL查詢的：

客戶端管理器
查詢管理器
數(shù)據(jù)管理器（含復原管理器）

客戶端管理器

image

客戶端管理器是處理客戶端通信的惹谐〕制客戶端可以是一個（網(wǎng)站）服務(wù)器或者一個最終用戶或最終應(yīng)用“奔。客戶端管理器通過一系列知名的API（JDBC, ODBC, OLE-DB …）提供不同的方式來訪問數(shù)據(jù)庫鸿秆。

客戶端管理器也提供專有的數(shù)據(jù)庫訪問API。

當你連接到數(shù)據(jù)庫時：

管理器首先檢查你的驗證信息（用戶名和密碼）怎囚，然后檢查你是否有訪問數(shù)據(jù)庫的授權(quán)卿叽。這些權(quán)限由DBA分配。
然后恳守，管理器檢查是否有空閑進程（或線程）來處理你的查詢附帽。
管理器還會檢查數(shù)據(jù)庫是否負載很重。
管理器可能會等待一會兒來獲取需要的資源井誉。如果等待時間達到超時時間蕉扮，它會關(guān)閉連接并給出一個可讀的錯誤信息。
然后管理器會把你的查詢送給查詢管理器來處理颗圣。
因為查詢處理進程不是『不全則無』的喳钟，一旦它從查詢管理器得到數(shù)據(jù)，它會把部分結(jié)果保存到一個緩沖區(qū)并且開始給你發(fā)送在岂。
如果遇到問題奔则，管理器關(guān)閉連接，向你發(fā)送可讀的解釋信息蔽午，然后釋放資源易茬。

查詢管理器

image

這部分是數(shù)據(jù)庫的威力所在，在這部分里及老，一個寫得糟糕的查詢可以轉(zhuǎn)換成一個快速執(zhí)行的代碼抽莱，代碼執(zhí)行的結(jié)果被送到客戶端管理器。這個多步驟操作過程如下：

查詢首先被解析并判斷是否合法
然后被重寫骄恶，去除了無用的操作并且加入預優(yōu)化部分
接著被優(yōu)化以便提升性能食铐，并被轉(zhuǎn)換為可執(zhí)行代碼和數(shù)據(jù)訪問計劃。
然后計劃被編譯
最后僧鲁，被執(zhí)行

這里我不會過多探討最后兩步虐呻，因為它們不太重要象泵。

看完這部分后，如果你需要更深入的知識斟叼，我建議你閱讀：

關(guān)于成本優(yōu)化的初步研究論文(1979)：關(guān)系型數(shù)據(jù)庫系統(tǒng)存取路徑選擇偶惠。這個篇文章只有12頁，而且具備計算機一般水平就能理解朗涩。
非常好洲鸠、非常深入的 DB2 9.X 如何優(yōu)化查詢的介紹
非常好的PostgreSQL如何優(yōu)化查詢的介紹。這是一篇最通俗易懂的文檔馋缅，因為它講的是『我們來看看在這種情況下扒腕，PostgreSQL給出了什么樣的查詢計劃』，而不是『我們來看看PostgreSQL用的什么算法』萤悴。
官方SQLite優(yōu)化文檔瘾腰。『易于』閱讀覆履，因為SQLite用的是簡單規(guī)則蹋盆。再者，這是唯一真正解釋SQLite如何工作的官方文檔硝全。
非常好的SQL Server 2005 如何優(yōu)化查詢的介紹
Oracle 12c 優(yōu)化白皮書
2篇查詢優(yōu)化的教程栖雾，第一篇第二篇。教程來自《數(shù)據(jù)庫系統(tǒng)概念》的作者伟众，很好的讀物析藕，集中討論磁盤I/O，但是要求具有很好的計算機科學水平凳厢。
另一個原理教程账胧，這篇教程我覺得更易懂，不過它僅關(guān)注聯(lián)接運算符（join operators）和磁盤I/O先紫。

查詢解析器

每一條SQL語句都要送到解析器來檢查語法治泥，如果你的查詢有錯，解析器將拒絕該查詢遮精。比如居夹，如果你寫成”SLECT …” 而不是 “SELECT …”，那就沒有下文了本冲。

但這還不算完准脂，解析器還會檢查關(guān)鍵字是否使用正確的順序，比如 WHERE 寫在 SELECT 之前會被拒絕眼俊。

然后意狠，解析器要分析查詢中的表和字段，使用數(shù)據(jù)庫元數(shù)據(jù)來檢查：

表是否存在
表的字段是否存在
對某類型字段的運算是否可能（比如疮胖，你不能將整數(shù)和字符串進行比較环戈，你不能對一個整數(shù)使用 substring() 函數(shù)）

接著，解析器檢查在查詢中你是否有權(quán)限來讀扰炀摹（或?qū)懭耄┍碓喝Ｔ購娬{(diào)一次：這些權(quán)限由DBA分配。

在解析過程中性昭，SQL 查詢被轉(zhuǎn)換為內(nèi)部表示（通常是一個樹）拦止。

如果一切正常，內(nèi)部表示被送到查詢重寫器糜颠。

查詢重寫器

在這一步汹族，我們已經(jīng)有了查詢的內(nèi)部表示，重寫器的目標是：

預優(yōu)化查詢
避免不必要的運算
幫助優(yōu)化器找到合理的最佳解決方案

重寫器按照一系列已知的規(guī)則對查詢執(zhí)行檢測其兴。如果查詢匹配一種模式的規(guī)則顶瞒，查詢就會按照這條規(guī)則來重寫。下面是（可選）規(guī)則的非詳盡的列表：

視圖合并：如果你在查詢中使用視圖元旬，視圖就會轉(zhuǎn)換為它的 SQL 代碼榴徐。
子查詢扁平化：子查詢是很難優(yōu)化的，因此重寫器會嘗試移除子查詢

例如：MySQL

FROM  PERSON
WHERE  PERSON.person_key  IN
(SELECT  MAILS.person_key
FROM  MAILS
WHERE  MAILS.mail  LIKE  'christophe%');

會轉(zhuǎn)換為：MySQL

SELECT  PERSON.*
FROM  PERSON,  MAILS
WHERE  PERSON.person_key  =  MAILS.person_key
and  MAILS.mail  LIKE  'christophe%';

去除不必要的運算符：比如匀归，如果你用了 DISTINCT坑资，而其實你有 UNIQUE 約束（這本身就防止了數(shù)據(jù)出現(xiàn)重復），那么 DISTINCT 關(guān)鍵字就被去掉了穆端。
排除冗余的聯(lián)接：如果相同的 JOIN 條件出現(xiàn)兩次袱贮，比如隱藏在視圖中的 JOIN 條件，或者由于傳遞性產(chǎn)生的無用 JOIN体啰，都會被消除字柠。
常數(shù)計算賦值：如果你的查詢需要計算，那么在重寫過程中計算會執(zhí)行一次狡赐。比如 WHERE AGE > 10+2 會轉(zhuǎn)換為 WHERE AGE > 12 窑业， TODATE(“日期字符串”) 會轉(zhuǎn)換為 datetime 格式的日期值。
（高級）分區(qū)裁剪（Partition Pruning）：如果你用了分區(qū)表枕屉，重寫器能夠找到需要使用的分區(qū)常柄。
（高級）物化視圖重寫（Materialized view rewrite）：如果你有個物化視圖匹配查詢謂詞的一個子集，重寫器將檢查視圖是否最新并修改查詢搀擂，令查詢使用物化視圖而不是原始表西潘。
（高級）自定義規(guī)則：如果你有自定義規(guī)則來修改查詢（就像 Oracle policy），重寫器就會執(zhí)行這些規(guī)則哨颂。
（高級）OLAP轉(zhuǎn)換：分析/加窗函數(shù)喷市，星形聯(lián)接，ROLLUP 函數(shù)……都會發(fā)生轉(zhuǎn)換（但我不確定這是由重寫器還是優(yōu)化器來完成威恼，因為兩個進程聯(lián)系很緊品姓，必須看是什么數(shù)據(jù)庫）寝并。

【譯者注：物化視圖。謂詞腹备，predicate衬潦，條件表達式的求值返回真或假的過程】

重寫后的查詢接著送到優(yōu)化器，這時候好玩的就開始了植酥。

統(tǒng)計

研究數(shù)據(jù)庫如何優(yōu)化查詢之前我們需要談?wù)劷y(tǒng)計镀岛，因為沒有統(tǒng)計的數(shù)據(jù)庫是愚蠢的。除非你明確指示友驮，數(shù)據(jù)庫是不會分析自己的數(shù)據(jù)的漂羊。沒有分析會導致數(shù)據(jù)庫做出（非常）糟糕的假設(shè)。

但是卸留，數(shù)據(jù)庫需要什么類型的信息呢走越？

我必須（簡要地）談?wù)剶?shù)據(jù)庫和操作系統(tǒng)如何保存數(shù)據(jù)。兩者使用的最小單位叫做頁或塊（默認 4 或 8 KB）艾猜。這就是說如果你僅需要 1KB买喧，也會占用一個頁。要是頁的大小為 8KB匆赃，你就浪費了 7KB淤毛。

回來繼續(xù)講統(tǒng)計！當你要求數(shù)據(jù)庫收集統(tǒng)計信息算柳，數(shù)據(jù)庫會計算下列值：

表中行和頁的數(shù)量
表中每個列中的：
唯一值
數(shù)據(jù)長度（最小低淡，最大，平均）
數(shù)據(jù)范圍（最小瞬项，最大蔗蹋，平均）
表的索引信息

這些統(tǒng)計信息會幫助優(yōu)化器估計查詢所需的磁盤 I/O、CPU囱淋、和內(nèi)存使用

對每個列的統(tǒng)計非常重要猪杭。
比如，如果一個表 PERSON 需要聯(lián)接 2 個列： LAST_NAME, FIRST_NAME妥衣。
根據(jù)統(tǒng)計信息皂吮，數(shù)據(jù)庫知道FIRST_NAME只有 1,000 個不同的值，LAST_NAME 有 1,000,000 個不同的值税手。
因此蜂筹，數(shù)據(jù)庫就會按照 LAST_NAME, FIRST_NAME 聯(lián)接。
因為 LAST_NAME 不大可能重復芦倒，多數(shù)情況下比較 LAST_NAME 的頭 2 艺挪、 3 個字符就夠了，這將大大減少比較的次數(shù)兵扬。

不過麻裳，這些只是基本的統(tǒng)計口蝠。你可以讓數(shù)據(jù)庫做一種高級統(tǒng)計，叫直方圖掂器。直方圖是列值分布情況的統(tǒng)計信息亚皂。例如：

出現(xiàn)最頻繁的值
分位數(shù) 【譯者注：http://baike.baidu.com/view/1323572.htm】
…

這些額外的統(tǒng)計會幫助數(shù)據(jù)庫找到更佳的查詢計劃俱箱，尤其是對于等式謂詞（例如： WHERE AGE = 18 ）或范圍謂詞（例如： WHERE AGE > 10 and AGE < 40）国瓮，因為數(shù)據(jù)庫可以更好的了解這些謂詞相關(guān)的數(shù)字類型數(shù)據(jù)行（注：這個概念的技術(shù)名稱叫選擇率）。

統(tǒng)計信息保存在數(shù)據(jù)庫元數(shù)據(jù)內(nèi)狞谱，例如（非分區(qū)）表的統(tǒng)計信息位置：

Oracle： USER / ALL / DBA_TABLES 和 USER / ALL / DBA_TAB_COLUMNS
DB2： SYSCAT.TABLES 和 SYSCAT.COLUMNS

統(tǒng)計信息必須及時更新乃摹。如果一個表有 1,000,000 行而數(shù)據(jù)庫認為它只有 500 行，沒有比這更糟糕的了跟衅。統(tǒng)計唯一的不利之處是需要時間來計算孵睬，這就是為什么數(shù)據(jù)庫大多默認情況下不會自動計算統(tǒng)計信息。數(shù)據(jù)達到百萬級時統(tǒng)計會變得困難伶跷，這時候掰读，你可以選擇僅做基本統(tǒng)計或者在一個數(shù)據(jù)庫樣本上執(zhí)行統(tǒng)計。

舉個例子叭莫，我參與的一個項目需要處理每表上億條數(shù)據(jù)的庫蹈集，我選擇只統(tǒng)計10%，結(jié)果造成了巨大的時間消耗雇初。本例證明這是個糟糕的決定拢肆，因為有時候 Oracle 10G 從特定表的特定列中選出的 10% 跟全部 100% 有很大不同（對于擁有一億行數(shù)據(jù)的表，這種情況極少發(fā)生）靖诗。這次錯誤的統(tǒng)計導致了一個本應(yīng) 30 秒完成的查詢最后執(zhí)行了 8 個小時郭怪，查找這個現(xiàn)象根源的過程簡直是個噩夢。這個例子顯示了統(tǒng)計的重要性刊橘。

注：當然了鄙才，每個數(shù)據(jù)庫還有其特定的更高級的統(tǒng)計。如果你想了解更多信息促绵，讀讀數(shù)據(jù)庫的文檔攒庵。話雖然這么說，我已經(jīng)盡力理解統(tǒng)計是如何使用的了绞愚，而且我找到的最好的官方文檔來自PostgreSQL叙甸。

查詢優(yōu)化器

image

所有的現(xiàn)代數(shù)據(jù)庫都在用基于成本的優(yōu)化（即CBO）來優(yōu)化查詢。道理是針對每個運算設(shè)置一個成本位衩，通過應(yīng)用成本最低廉的一系列運算裆蒸，來找到最佳的降低查詢成本的方法。

為了理解成本優(yōu)化器的原理糖驴，我覺得最好用個例子來『感受』一下這個任務(wù)背后的復雜性僚祷。這里我將給出聯(lián)接 2 個表的 3 個方法佛致，我們很快就能看到即便一個簡單的聯(lián)接查詢對于優(yōu)化器來說都是個噩夢。之后辙谜，我們會了解真正的優(yōu)化器是怎么做的俺榆。

對于這些聯(lián)接操作，我會專注于它們的時間復雜度装哆，但是罐脊，數(shù)據(jù)庫優(yōu)化器計算的是它們的 CPU 成本、磁盤 I/O 成本蜕琴、和內(nèi)存需求萍桌。時間復雜度和 CPU 成本的區(qū)別是，時間成本是個近似值（給我這樣的懶家伙準備的）凌简。而 CPU 成本上炎，我這里包括了所有的運算，比如：加法雏搂、條件判斷藕施、乘法、迭代……還有呢：

每一個高級代碼運算都要特定數(shù)量的低級 CPU 運算凸郑。
對于 Intel Core i7裳食、Intel Pentium 4、AMD Opteron…等线椰，（就 CPU 周期而言）CPU 的運算成本是不同的胞谈，也就是說它取決于 CPU 的架構(gòu)。

使用時間復雜度就容易多了（至少對我來說）憨愉，用它我也能了解到 CBO 的概念烦绳。由于磁盤 I/O 是個重要的概念，我偶爾也會提到它配紫。請牢記径密，大多數(shù)時候瓶頸在于磁盤 I/O 而不是 CPU 使用。

索引

在研究 B+樹的時候我們談到了索引躺孝，要記住一點享扔，索引都是已經(jīng)排了序的捏雌。

僅供參考：還有其他類型的索引坝茎，比如位圖索引，在 CPU暴拄、磁盤I/O于个、和內(nèi)存方面與B+樹索引的成本并不相同氛魁。

另外，很多現(xiàn)代數(shù)據(jù)庫為了改善執(zhí)行計劃的成本，可以僅為當前查詢動態(tài)地生成臨時索引秀存。

存取路徑

在應(yīng)用聯(lián)接運算符（join operators）之前捶码，你首先需要獲得數(shù)據(jù)。以下就是獲得數(shù)據(jù)的方法或链。

注：由于所有存取路徑的真正問題是磁盤 I/O惫恼，我不會過多探討時間復雜度。

【譯者注：四種類型的Oracle索引掃描介紹】

全掃描

如果你讀過執(zhí)行計劃澳盐，一定看到過『全掃描』（或只是『掃描』）一詞祈纯。簡單的說全掃描就是數(shù)據(jù)庫完整的讀一個表或索引。就磁盤 I/O 而言洞就，很明顯全表掃描的成本比索引全掃描要高昂盆繁。

范圍掃描

其他類型的掃描有索引范圍掃描掀淘，比如當你使用謂詞 ” WHERE AGE > 20 AND AGE < 40 ” 的時候它就會發(fā)生。

當然革娄，你需要在 AGE 字段上有索引才能用到索引范圍掃描倾贰。

在第一部分我們已經(jīng)知道，范圍查詢的時間成本大約是 log(N)+M拦惋，這里 N 是索引的數(shù)據(jù)量匆浙，M 是范圍內(nèi)估測的行數(shù)。多虧有了統(tǒng)計我們才能知道 N 和 M 的值（注： M 是謂詞 “ AGE > 20 AND AGE < 40 ” 的選擇率）厕妖。另外范圍掃描時首尼，你不需要讀取整個索引，因此在磁盤 I/O 方面沒有全掃描那么昂貴言秸。

唯一掃描

如果你只需要從索引中取一個值你可以用唯一掃描软能。

根據(jù) ROW ID 存取

多數(shù)情況下，如果數(shù)據(jù)庫使用索引举畸，它就必須查找與索引相關(guān)的行查排，這樣就會用到根據(jù) ROW ID 存取的方式。

例如抄沮，假如你運行：

MySQL

SELECT  LASTNAME,  FIRSTNAME  from  PERSON  WHERE  AGE  =  28

如果 person 表的 age 列有索引跋核，優(yōu)化器會使用索引找到所有年齡為 28 的人，然后它會去表中讀取相關(guān)的行叛买，這是因為索引中只有 age 的信息而你要的是姓和名砂代。

但是，假如你換個做法：

MySQL

SELECT  TYPE_PERSON.CATEGORY  from  PERSON  ,TYPE_PERSON
WHERE  PERSON.AGE  =  TYPE_PERSON.AGE

PERSON 表的索引會用來聯(lián)接 TYPE_PERSON 表率挣，但是 PERSON 表不會根據(jù)行ID 存取刻伊，因為你并沒有要求這個表內(nèi)的信息。

雖然這個方法在少量存取時表現(xiàn)很好，這個運算的真正問題其實是磁盤 I/O娃圆。假如需要大量的根據(jù)行ID存取玫锋，數(shù)據(jù)庫也許會選擇全掃描。

其它路徑

我沒有列舉所有的存取路徑讼呢，如果你感興趣可以讀一讀 Oracle文檔撩鹿。其它數(shù)據(jù)庫里也許叫法不同但背后的概念是一樣的。

聯(lián)接運算符

那么悦屏，我們知道如何獲取數(shù)據(jù)了节沦，那現(xiàn)在就把它們聯(lián)接起來！

我要展現(xiàn)的是3個常用聯(lián)接運算符：合并聯(lián)接（Merge join）础爬，哈希聯(lián)接（Hash Join）和嵌套循環(huán)聯(lián)接（Nested Loop Join）甫贯。但是在此之前，我需要引入新詞匯了：內(nèi)關(guān)系和外關(guān)系（ inner relation and outer relation）【譯者注： “內(nèi)關(guān)系和外關(guān)系” 這個說法來源不明看蚜，跟查詢的“內(nèi)聯(lián)接（INNER JOIN）叫搁、外聯(lián)接（OUTER JOIN） ” 不是一個概念。只查到百度百科詞條：關(guān)系數(shù)據(jù)庫里提到“每個表格（有時被稱為一個關(guān)系）……” 供炎。其他參考鏈接 “Merge Join” “Hash Join” “Nested Loop Join” 】渴逻。一個關(guān)系可以是：

一個表
一個索引
上一個運算的中間結(jié)果（比如上一個聯(lián)接運算的結(jié)果）

當你聯(lián)接兩個關(guān)系時，聯(lián)接算法對兩個關(guān)系的處理是不同的音诫。在本文剩余部分惨奕，我將假定：

外關(guān)系是左側(cè)數(shù)據(jù)集
內(nèi)關(guān)系是右側(cè)數(shù)據(jù)集

比如， A JOIN B 是 A 和 B 的聯(lián)接竭钝，這里 A 是外關(guān)系梨撞，B 是內(nèi)關(guān)系。

多數(shù)情況下香罐， A JOIN B 的成本跟 B JOIN A 的成本是不同的卧波。

在這一部分，我還將假定外關(guān)系有 N 個元素穴吹，內(nèi)關(guān)系有 M 個元素幽勒。要記住，真實的優(yōu)化器通過統(tǒng)計知道 N 和 M 的值港令。

注：N 和 M 是關(guān)系的基數(shù)啥容。【譯者注：基數(shù) 】

嵌套循環(huán)聯(lián)接

嵌套循環(huán)聯(lián)接是最簡單的顷霹。

image

道理如下：

針對外關(guān)系的每一行
查看內(nèi)關(guān)系里的所有行來尋找匹配的行

下面是偽代碼：

nested_loop_join(array  outer,  array  inner)
  for  each  row  a  in  outer
    for  each  row  b  in  inner
      if  (match_join_condition(a,b))
        write_result_in_output(a,b)
      end  if
    end  for
 end  for

由于這是個雙迭代咪惠，時間復雜度是 O(N*M)。

在磁盤 I/O 方面淋淀，針對 N 行外關(guān)系的每一行遥昧，內(nèi)部循環(huán)需要從內(nèi)關(guān)系讀取 M 行。這個算法需要從磁盤讀取 N+ N*M 行。但是炭臭，如果內(nèi)關(guān)系足夠小永脓，你可以把它讀入內(nèi)存，那么就只剩下 M + N 次讀取鞋仍。這樣修改之后常摧，內(nèi)關(guān)系必須是最小的，因為它有更大機會裝入內(nèi)存威创。

在CPU成本方面沒有什么區(qū)別落午，但是在磁盤 I/O 方面，最好最好的肚豺，是每個關(guān)系只讀取一次溃斋。

當然，內(nèi)關(guān)系可以由索引代替吸申，對磁盤 I/O 更有利梗劫。

由于這個算法非常簡單，下面這個版本在內(nèi)關(guān)系太大無法裝入內(nèi)存時呛谜，對磁盤 I/O 更加有利在跳。道理如下：

為了避免逐行讀取兩個關(guān)系，
你可以成簇讀取隐岛，把（兩個關(guān)系里讀到的）兩簇數(shù)據(jù)行保存在內(nèi)存里，
比較兩簇數(shù)據(jù)瓷翻，保留匹配的聚凹，
然后從磁盤加載新的數(shù)據(jù)簇來繼續(xù)比較
直到加載了所有數(shù)據(jù)。

可能的算法如下：

// improved version to reduce the disk I/O.
nested_loop_join_v2(file outer,  file inner)
  for  each  bunch ba in  outer
    // ba is now in memory
    for  each  bunch bb in  inner
        // bb is now in memory
        for  each  row  a  in  ba
          for  each  row  b  in  bb
            if  (match_join_condition(a,b))
              write_result_in_output(a,b)
            end  if
          end  for
      end  for
    end  for
 end  for

使用這個版本齐帚，時間復雜度沒有變化妒牙，但是磁盤訪問降低了：

用前一個版本，算法需要 N + N*M 次訪問（每次訪問讀取一行）对妄。
用新版本湘今，磁盤訪問變?yōu)?外關(guān)系的數(shù)據(jù)簇數(shù)量 + 外關(guān)系的數(shù)據(jù)簇數(shù)量 * 內(nèi)關(guān)系的數(shù)據(jù)簇數(shù)量。
增加數(shù)據(jù)簇的尺寸剪菱，可以降低磁盤訪問摩瞎。

哈希聯(lián)接

哈希聯(lián)接更復雜，不過在很多場合比嵌套循環(huán)聯(lián)接成本低孝常。

image

哈希聯(lián)接的道理是：

1. 讀取內(nèi)關(guān)系的所有元素
1. 在內(nèi)存里建一個哈希表
1. 逐條讀取外關(guān)系的所有元素
1. （用哈希表的哈希函數(shù)）計算每個元素的哈希值旗们，來查找內(nèi)關(guān)系里相關(guān)的哈希桶內(nèi)
1. 是否與外關(guān)系的元素匹配。

在時間復雜度方面我需要做些假設(shè)來簡化問題：

內(nèi)關(guān)系被劃分成 X 個哈希桶
哈希函數(shù)幾乎均勻地分布每個關(guān)系內(nèi)數(shù)據(jù)的哈希值构灸，就是說哈希桶大小一致上渴。
外關(guān)系的元素與哈希桶內(nèi)的所有元素的匹配，成本是哈希桶內(nèi)元素的數(shù)量。

時間復雜度是 (M/X) * N + 創(chuàng)建哈希表的成本(M) + 哈希函數(shù)的成本 * N 稠氮。
如果哈希函數(shù)創(chuàng)建了足夠小規(guī)模的哈希桶曹阔，那么復雜度就是 O(M+N)。

還有個哈希聯(lián)接的版本隔披，對內(nèi)存有利但是對磁盤 I/O 不夠有利次兆。這回是這樣的：

1. 計算內(nèi)關(guān)系和外關(guān)系雙方的哈希表
1. 保存哈希表到磁盤
1. 然后逐個哈希桶比較（其中一個讀入內(nèi)存，另一個逐行讀惹旅獭）芥炭。

合并聯(lián)接

合并聯(lián)接是唯一產(chǎn)生排序的聯(lián)接算法。

注：這個簡化的合并聯(lián)接不區(qū)分內(nèi)表或外表恃慧；兩個表扮演同樣的角色园蝠。但是真實的實現(xiàn)方式是不同的，比如當處理重復值時痢士。

1.（可選）排序聯(lián)接運算：兩個輸入源都按照聯(lián)接關(guān)鍵字排序彪薛。

2.合并聯(lián)接運算：排序后的輸入源合并到一起。

排序

我們已經(jīng)談到過合并排序怠蹂，在這里合并排序是個很好的算法（但是并非最好的善延，如果內(nèi)存足夠用的話，還是哈希聯(lián)接更好）城侧。

然而有時數(shù)據(jù)集已經(jīng)排序了易遣，比如：

如果表內(nèi)部就是有序的，比如聯(lián)接條件里一個索引組織表【譯者注： index-organized table 】
如果關(guān)系是聯(lián)接條件里的一個索引
如果聯(lián)接應(yīng)用在一個查詢中已經(jīng)排序的中間結(jié)果

合并聯(lián)接

image

這部分與我們研究過的合并排序中的合并運算非常相似嫌佑。不過這一次呢豆茫，我們不是從兩個關(guān)系里挑選所有元素，而是只挑選相同的元素屋摇。道理如下：

1. 在兩個關(guān)系中揩魂，比較當前元素（當前=頭一次出現(xiàn)的第一個）
1. 如果相同，就把兩個元素都放入結(jié)果炮温，再比較兩個關(guān)系里的下一個元素
1. 如果不同火脉，就去帶有最小元素的關(guān)系里找下一個元素（因為下一個元素可能會匹配）
1. 重復 1、2柒啤、3步驟直到其中一個關(guān)系的最后一個元素倦挂。

因為兩個關(guān)系都是已排序的，你不需要『回頭去找』白修，所以這個方法是有效的妒峦。

該算法是個簡化版，因為它沒有處理兩個序列中相同數(shù)據(jù)出現(xiàn)多次的情況（即多重匹配）兵睛。真實版本『僅僅』針對本例就更加復雜肯骇，所以我才選擇簡化版窥浪。

如果兩個關(guān)系都已經(jīng)排序，時間復雜度是 O(N+M)

如果兩個關(guān)系需要排序笛丙，時間復雜度是對兩個關(guān)系排序的成本：O(NLog(N) + MLog(M))

對于計算機極客漾脂，我給出下面這個可能的算法來處理多重匹配（注：對于這個算法我不保證100%正確）：

mergeJoin(relation  a,  relation  b)
  relation output
  integer  a_key:=0;
  integer  b_key:=0;
  while  (a[a_key]!=null  and  b[b_key]!=null)
 if  (a[a_key]  <  b[b_key])
      a_key++;
 else  if  (a[a_key]  >  b[b_key])
      b_key++;
 else  //Join predicate satisfied
      write_result_in_output(a[a_key],b[b_key])
      //We need to be careful when we increase the pointers
      if  (a[a_key+1]  !=  b[b_key])
        b_key++;
      end  if
      if  (b[b_key+1]  !=  a[a_key])
        a_key++;
      end  if
      if  (b[b_key+1]  ==  a[a_key]  &&  b[b_key]  ==  a[a_key+1])
        b_key++;
        a_key++;
      end  if
    end  if
  end  while

哪個算法最好？

如果有最好的胚鸯，就沒必要弄那么多種類型了骨稿。這個問題很難，因為很多因素都要考慮姜钳，比如：

空閑內(nèi)存：沒有足夠的內(nèi)存的話就跟強大的哈希聯(lián)接拜拜吧（至少是完全內(nèi)存中哈希聯(lián)接）坦冠。
兩個數(shù)據(jù)集的大小。比如哥桥，如果一個大表聯(lián)接一個很小的表辙浑，那么嵌套循環(huán)聯(lián)接就比哈希聯(lián)接快，因為后者有創(chuàng)建哈希的高昂成本拟糕；如果兩個表都非常大判呕，那么嵌套循環(huán)聯(lián)接CPU成本就很高昂。
是否有索引：有兩個 B+樹索引的話送滞，聰明的選擇似乎是合并聯(lián)接侠草。
結(jié)果是否需要排序：即使你用到的是未排序的數(shù)據(jù)集，你也可能想用成本較高的合并聯(lián)接（帶排序的）犁嗅，因為最終得到排序的結(jié)果后边涕，你可以把它和另一個合并聯(lián)接串起來（或者也許因為查詢用 ORDER BY/GROUP BY/DISTINCT 等操作符隱式或顯式地要求一個排序結(jié)果）。
關(guān)系是否已經(jīng)排序：這時候合并聯(lián)接是最好的候選項愧哟。
聯(lián)接的類型：是等值聯(lián)接（比如 tableA.col1 = tableB.col2 ）奥吩？還是內(nèi)聯(lián)接？外聯(lián)接蕊梧？笛卡爾乘積？或者自聯(lián)接腮介？有些聯(lián)接在特定環(huán)境下是無法工作的肥矢。
數(shù)據(jù)的分布：如果聯(lián)接條件的數(shù)據(jù)是傾斜的（比如根據(jù)姓氏來聯(lián)接人，但是很多人同姓）叠洗，用哈希聯(lián)接將是個災(zāi)難甘改，原因是哈希函數(shù)將產(chǎn)生分布極不均勻的哈希桶。
如果你希望聯(lián)接操作使用多線程或多進程灭抑。

想要更詳細的信息十艾，可以閱讀DB2, ORACLE 或 SQL Server)的文檔。

簡化的例子

我們已經(jīng)研究了 3 種類型的聯(lián)接操作腾节。

現(xiàn)在忘嫉，比如說我們要聯(lián)接 5 個表荤牍，來獲得一個人的全部信息。一個人可以有：

多個手機號（MOBILES）
多個郵箱（MAILS）
多個地址（ADRESSES）
多個銀行賬號（BANK_ACCOUNTS）

換句話說庆冕，我們需要用下面的查詢快速得到答案：

MySQL

SELECT  *  from  PERSON,  MOBILES,  MAILS,ADRESSES,  BANK_ACCOUNTS
WHERE
PERSON.PERSON_ID  =  MOBILES.PERSON_ID
AND  PERSON.PERSON_ID  =  MAILS.PERSON_ID
AND  PERSON.PERSON_ID  =  ADRESSES.PERSON_ID
AND  PERSON.PERSON_ID  =  BANK_ACCOUNTS.PERSON_ID

作為一個查詢優(yōu)化器康吵，我必須找到處理數(shù)據(jù)最好的方法。但有 2 個問題：

每個聯(lián)接使用那種類型访递？
我有 3 種可選（哈希晦嵌、合并、嵌套）拷姿，同時可能用到 0, 1 或 2 個索引（不必說還有多種類型的索引）惭载。
按什么順序執(zhí)行聯(lián)接？
比如响巢，下圖顯示了針對 4 個表僅僅 3 次聯(lián)接描滔，可能采用的執(zhí)行計劃：

image

那么下面就是我可能采取的方法：

1. 采取粗暴的方式
  用數(shù)據(jù)庫統(tǒng)計，計算每種可能的執(zhí)行計劃的成本抵乓，保留最佳方案伴挚。但是，會有很多可能性灾炭。對于一個給定順序的聯(lián)接操作茎芋，每個聯(lián)接有三種可能性：哈希、合并蜈出、嵌套田弥，那么總共就有 3^4 種可能性。確定聯(lián)接的順序是個二叉樹的排列問題铡原，會有 (24)!/(4+1)! 種可能的順序偷厦。對本例這個相當簡化了的問題，我最后會得到 3^4(2*4)!/(4+1)! 種可能燕刻。
  拋開專業(yè)術(shù)語只泼，那相當于 27,216 種可能性。如果給合并聯(lián)接加上使用 0,1 或 2 個 B+樹索引卵洗，可能性就變成了 210,000種请唱。我是不是告訴過你這個查詢其實非常簡單嗎？
1. 我大叫一聲辭了這份工作
  很有誘惑力过蹂，但是這樣一來十绑，你不會的到查詢結(jié)果，而我需要錢來付賬單酷勺。
1. 我只嘗試幾種執(zhí)行計劃本橙，挑一個成本最低的。
  由于不是超人脆诉，我不能算出所有計劃的成本甚亭。相反贷币，我可以武斷地從全部可能的計劃中選擇一個子集，計算它們的成本狂鞋，把最佳的計劃給你片择。
1. 我用聰明的規(guī)則來降低可能性的數(shù)量有兩種規(guī)則：
  我可以用『邏輯』規(guī)則，它能去除無用的可能性骚揍，但是無法過濾大量的可能性字管。比如：『嵌套聯(lián)接的內(nèi)關(guān)系必須是最小的數(shù)據(jù)集』。
  我接受現(xiàn)實，不去找最佳方案，用更激進的規(guī)則來大大降低可能性的數(shù)量登夫。比如：『如果一個關(guān)系很小依疼，使用嵌套循環(huán)聯(lián)接绣檬，絕不使用合并或哈希聯(lián)接。』

在這個簡單的例子中，我最后得到很多可能性丁逝。但現(xiàn)實世界的查詢還會有其他關(guān)系運算符，像 OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT … 這意味著更多的可能性梭姓。

那么霜幼，數(shù)據(jù)庫是如何處理的呢？

動態(tài)規(guī)劃誉尖，貪婪算法和啟發(fā)式算法

關(guān)系型數(shù)據(jù)庫會嘗試我剛剛提到的多種方法罪既，優(yōu)化器真正的工作是在有限時間里找到一個好的解決方案。

多數(shù)時候铡恕，優(yōu)化器找到的不是最佳的方案琢感，而是一個『不錯』的

對于小規(guī)模的查詢，采取粗暴的方式是有可能的探熔。但是為了讓中等規(guī)模的查詢也能采取粗暴的方式驹针，我們有辦法避免不必要的計算，這就是動態(tài)規(guī)劃诀艰。

動態(tài)規(guī)劃

這幾個字背后的理念是牌捷，很多執(zhí)行計劃是非常相似的∥型裕看看下圖這幾種計劃：

image

它們都有相同的子樹（A JOIN B），所以喜滨，不必在每個計劃中計算這個子樹的成本捉捅，計算一次，保存結(jié)果虽风，當再遇到這個子樹時重用棒口。用更正規(guī)的說法寄月，我們面對的是個重疊問題。為了避免對部分結(jié)果的重復計算无牵，我們使用記憶法漾肮。

應(yīng)用這一技術(shù)，我們不再有 (2*N)!/(N+1)! 的復雜度茎毁，而是“只有” 3^N克懊。在之前 4 個JOIN 的例子里，這意味著將 336 次排序降為 81 次七蜘。如果是大一些的查詢谭溉，比如 8 個 JOIN （其實也不是很大啦），就是將 57,657,600 次降為 6551 次橡卤“缒睿【譯者注：這一小段漏掉了，感謝 nsos指出來碧库。另外感謝 Clark Li 指出Dynamic Programing 應(yīng)該翻譯為動態(tài)規(guī)劃柜与。】

對于計算機極客，下面是我在先前給你的教程里找到的一個算法嵌灰。我不提供解釋弄匕，所以僅在你已經(jīng)了解動態(tài)規(guī)劃或者精通算法的情況下閱讀（我提醒過你哦）：

procedure findbestplan(S)

if  (bestplan[S].cost infinite)

 return  bestplan[S]

// else bestplan[S] has not been computed earlier, compute it now

if  (S  contains only  1  relation)

 set bestplan[S].plan and  bestplan[S].cost based on the best way

 of accessing  S  /* Using selections on S and indices on S */

 else  for  each  non-empty subset S1 of  S  such that S1  !=  S

 P1=  findbestplan(S1)

 P2=  findbestplan(S  -  S1)

 A  =  best algorithm for  joining results of P1 and  P2

 cost  =  P1.cost  +  P2.cost  +  cost of  A

 if  cost  <  bestplan[S].cost

 bestplan[S].cost  =  cost

      bestplan[S].plan  =  『execute P1.plan;  execute P2.plan;

 join results of P1 and  P2 using  A』

return  bestplan[S]

針對大規(guī)模查詢，你也可以用動態(tài)規(guī)劃方法伞鲫，但是要附加額外的規(guī)則（或者稱為啟發(fā)式算法）來減少可能性粘茄。

如果我們僅分析一個特定類型的計劃（例如左深樹 left-deep tree，參考)秕脓，我們得到 n*2^n 而不是 3^n柒瓣。

image

如果我們加上邏輯規(guī)則來避免一些模式的計劃（像『如果一個表有針對指定謂詞的索引，就不要對表嘗試合并聯(lián)接吠架，要對索引』）芙贫，就會在不給最佳方案造成過多傷害的前提下，減少可能性的數(shù)量傍药』瞧剑【譯者注：原文應(yīng)該是有兩處筆誤： as=has, to=too】
如果我們在流程里增加規(guī)則（像『聯(lián)接運算先于其他所有的關(guān)系運算』），也能減少大量的可能性拐辽。
……

貪婪算法

但是拣挪，優(yōu)化器面對一個非常大的查詢，或者為了盡快找到答案（然而查詢速度就快不起來了）俱诸，會應(yīng)用另一種算法菠劝，叫貪婪算法。

原理是按照一個規(guī)則（或啟發(fā)）以漸進的方式制定查詢計劃睁搭。在這個規(guī)則下赶诊，貪婪算法逐步尋找最佳算法笼平，先處理一條JOIN，接著每一步按照同樣規(guī)則加一條新的JOIN舔痪。

我們來看個簡單的例子寓调。比如一個針對5張表（A,B,C,D,E）4次JOIN 的查詢，為了簡化我們把嵌套JOIN作為可能的聯(lián)接方式锄码，按照『使用最低成本的聯(lián)接』規(guī)則夺英。

直接從 5 個表里選一個開始（比如 A）
計算每一個與 A 的聯(lián)接（A 作為內(nèi)關(guān)系或外關(guān)系）
發(fā)現(xiàn) “A JOIN B” 成本最低
計算每一個與 “A JOIN B” 的結(jié)果聯(lián)接的成本（“A JOIN B” 作為內(nèi)關(guān)系或外關(guān)系）
發(fā)現(xiàn) “(A JOIN B) JOIN C” 成本最低
計算每一個與 “(A JOIN B) JOIN C” 的結(jié)果聯(lián)接的成本 ……
最后確定執(zhí)行計劃 “( ( (A JOIN B) JOIN C) JOIN D ) JOIN E )”

因為我們是武斷地從表 A 開始，我們可以把同樣的算法用在 B巍耗，然后 C秋麸，然后 D, 然后 E。最后保留成本最低的執(zhí)行計劃炬太。

順便說一句灸蟆，這個算法有個名字，叫『最近鄰居算法』亲族。

拋開細節(jié)不談炒考，只需一個良好的模型和一個 Nlog(N) 復雜度的排序，問題就輕松解決了霎迫。這個算法的復雜度是 O(Nlog(N)) 斋枢，對比一下完全動態(tài)規(guī)劃的 O(3^N)。如果你有個20個聯(lián)接的大型查詢知给，這意味著 26 vs 3,486,784,401 瓤帚，天壤之別！

這個算法的問題是涩赢，我們做的假設(shè)是：找到 2 個表的最佳聯(lián)接方法戈次，保留這個聯(lián)接結(jié)果，再聯(lián)接下一個表筒扒，就能得到最低的成本怯邪。但是：

即使在 A, B, C 之間，A JOIN B 可得最低成本
(A JOIN C) JOIN B 也許比 (A JOIN B) JOIN C 更好花墩。

為了改善這一狀況悬秉，你可以多次使用基于不同規(guī)則的貪婪算法，并保留最佳的執(zhí)行計劃冰蘑。

其他算法

[ 如果你已經(jīng)受夠了算法話題和泌，就直接跳到下一部分。這部分對文章余下的內(nèi)容不重要祠肥。] 【譯者注：我也很想把這段跳過去 -_- 】

很多計算機科學研究者熱衷于尋找最佳的執(zhí)行計劃允跑，他們經(jīng)常為特定問題或模式探尋更好的解決方案，比如：

如果查詢是星型聯(lián)接（一種多聯(lián)接查詢），某些數(shù)據(jù)庫使用一種特定的算法聋丝。
如果查詢是并行的，某些數(shù)據(jù)庫使用一種特定的算法工碾。 ……

其他算法也在研究之中弱睦，就是為了替換在大型查詢中的動態(tài)規(guī)劃算法。貪婪算法屬于一個叫做啟發(fā)式算法的大家族渊额，它根據(jù)一條規(guī)則（或啟發(fā)）况木，保存上一步找到的方法，『附加』到當前步驟來進一步搜尋解決方法旬迹。有些算法根據(jù)特定規(guī)則火惊，一步步的應(yīng)用規(guī)則但不總是保留上一步找到的最佳方法。它們統(tǒng)稱啟發(fā)式算法奔垦。

比如屹耐，基因算法就是一種：

一個方法代表一種可能的完整查詢計劃
每一步保留了 P 個方法（即計劃），而不是一個椿猎。
1. P 個計劃隨機創(chuàng)建
1. 成本最低的計劃才會保留
1. 這些最佳計劃混合在一起產(chǎn)生 P 個新的計劃
1. 一些新的計劃被隨機改寫
1. 1惶岭，2，3步重復 T 次
1. 然后在最后一次循環(huán)犯眠，從 P 個計劃里得到最佳計劃按灶。

循環(huán)次數(shù)越多，計劃就越好筐咧。

這是魔術(shù)鸯旁？不，這是自然法則：適者生存量蕊！

PostgreSQL 實現(xiàn)了基因算法铺罢，但我并沒有發(fā)現(xiàn)它是不是默認使用這種算法的。

數(shù)據(jù)庫中還使用了其它啟發(fā)式算法危融，像『模擬退火算法（Simulated Annealing）』畏铆、『交互式改良算法（Iterative Improvement）』、『雙階段優(yōu)化算法（Two-Phase Optimization）』…..不過吉殃，我不知道這些算法當前是否在企業(yè)級數(shù)據(jù)庫應(yīng)用了辞居，還是僅僅用在研究型數(shù)據(jù)庫。

如果想進一步了解蛋勺，這篇研究文章介紹兩個更多可能的算法《數(shù)據(jù)庫查詢優(yōu)化中聯(lián)接排序問題的算法綜述》瓦灶，你可以去閱讀一下。

真實的優(yōu)化器

[ 這段不重要抱完，可以跳過 ]

然而贼陶，所有上述羅里羅嗦的都非常理論化，我是個開發(fā)者而不是研究者，我喜歡具體的例子碉怔。

我們來看看 SQLite 優(yōu)化器是怎么工作的烘贴。這是個輕量化數(shù)據(jù)庫，它使用一種簡單優(yōu)化器撮胧，基于帶有附加規(guī)則的貪婪算法桨踪，來限制可能性的數(shù)量。

SQLite 在有 CROSS JOIN 操作符時從不給表重新排序
使用嵌套聯(lián)接
外聯(lián)接始終按順序評估
……
3.8.0之前的版本使用『最近鄰居』貪婪算法來搜尋最佳查詢計劃
等等……我們見過這個算法芹啥！真是巧哈锻离！
從3.8.0版本（發(fā)布于2015年）開始，SQLite使用『N最近鄰居』貪婪算法來搜尋最佳查詢計劃

我們再看看另一個優(yōu)化器是怎么工作的墓怀。IBM DB2 跟所有企業(yè)級數(shù)據(jù)庫都類似汽纠，我討論它是因為在切換到大數(shù)據(jù)之前，它是我最后真正使用的數(shù)據(jù)庫傀履。

看過官方文檔后虱朵，我們了解到 DB2 優(yōu)化器可以讓你使用 7 種級別的優(yōu)化：

對聯(lián)接使用貪婪算法
0 – 最小優(yōu)化，使用索引掃描和嵌套循環(huán)聯(lián)接啤呼，避免一些查詢重寫
1 – 低級優(yōu)化
2 – 完全優(yōu)化
對聯(lián)接使用動態(tài)規(guī)劃算法
3 – 中等優(yōu)化和粗略的近似法
5 – 完全優(yōu)化卧秘，使用帶有啟發(fā)式的所有技術(shù)
7 – 完全優(yōu)化，類似級別5官扣，但不用啟發(fā)式
9 – 最大優(yōu)化翅敌，完全不顧開銷，考慮所有可能的聯(lián)接順序惕蹄，包括笛卡爾乘積

可以看到 DB2 使用貪婪算法和動態(tài)規(guī)劃算法蚯涮。當然，他們不會把自己的啟發(fā)算法分享出來的卖陵，因為查詢優(yōu)化器是數(shù)據(jù)庫的看家本領(lǐng)遭顶。

DB2 的默認級別是 5，優(yōu)化器使用下列特性：【譯者注：以下出現(xiàn)的一些概念我沒有做考證泪蔫，因為[ 這段不重要棒旗，可以跳過 ]】

使用所有可用的統(tǒng)計，包括線段樹（frequent-value）和分位數(shù)統(tǒng)計（quantile statistics）撩荣。
使用所有查詢重寫規(guī)則（含物化查詢表路由铣揉，materialized query table routing），除了在極少情況下適用的計算密集型規(guī)則餐曹。
使用動態(tài)規(guī)劃模擬聯(lián)接
有限使用組合內(nèi)關(guān)系（composite inner relation）
對于涉及查找表的星型模式逛拱，有限使用笛卡爾乘積
考慮寬泛的訪問方式，含列表預忍ê铩（list prefetch朽合，注：我們將討論什么是列表預染懔健），index ANDing（注：一種對索引的特殊操作）曹步，和物化查詢表路由宪彩。

默認的，DB2 對聯(lián)接排列使用受啟發(fā)式限制的動態(tài)規(guī)劃算法箭窜。

其它情況 (GROUP BY, DISTINCT…) 由簡單規(guī)則處理毯焕。

查詢計劃緩存

由于創(chuàng)建查詢計劃是耗時的，大多數(shù)據(jù)庫把計劃保存在查詢計劃緩存磺樱，來避免重復計算。這個話題比較大婆咸，因為數(shù)據(jù)庫需要知道什么時候更新過時的計劃竹捉。辦法是設(shè)置一個上限，如果一個表的統(tǒng)計變化超過了上限尚骄，關(guān)于該表的查詢計劃就從緩存中清除块差。

查詢執(zhí)行器

在這個階段，我們有了一個優(yōu)化的執(zhí)行計劃倔丈，再編譯為可執(zhí)行代碼憨闰。然后，如果有足夠資源（內(nèi)存需五，CPU）鹉动，查詢執(zhí)行器就會執(zhí)行它。計劃中的操作符 (JOIN, SORT BY …) 可以順序或并行執(zhí)行宏邮，這取決于執(zhí)行器泽示。為了獲得和寫入數(shù)據(jù)，查詢執(zhí)行器與數(shù)據(jù)管理器交互蜜氨，本文下一部分來討論數(shù)據(jù)管理器械筛。

數(shù)據(jù)管理器

image

在這一步，查詢管理器執(zhí)行了查詢飒炎，需要從表和索引獲取數(shù)據(jù)埋哟，于是向數(shù)據(jù)管理器提出請求。但是有 2 個問題：

關(guān)系型數(shù)據(jù)庫使用事務(wù)模型郎汪，所以赤赊，當其他人在同一時刻使用或修改數(shù)據(jù)時，你無法得到這部分數(shù)據(jù)怒竿。
數(shù)據(jù)提取是數(shù)據(jù)庫中速度最慢的操作砍鸠，所以數(shù)據(jù)管理器需要足夠聰明地獲得數(shù)據(jù)并保存在內(nèi)存緩沖區(qū)內(nèi)。

在這一部分耕驰，我沒看看關(guān)系型數(shù)據(jù)庫是如何處理這兩個問題的爷辱。我不會講數(shù)據(jù)管理器是怎么獲得數(shù)據(jù)的，因為這不是最重要的（而且本文已經(jīng)夠長的了！）饭弓。

緩存管理器

我已經(jīng)說過双饥，數(shù)據(jù)庫的主要瓶頸是磁盤 I/O。為了提高性能弟断，現(xiàn)代數(shù)據(jù)庫使用緩存管理器咏花。

image

查詢執(zhí)行器不會直接從文件系統(tǒng)拿數(shù)據(jù)，而是向緩存管理器要阀趴。緩存管理器有一個內(nèi)存緩存區(qū)昏翰，叫做緩沖池，從內(nèi)存讀取數(shù)據(jù)顯著地提升數(shù)據(jù)庫性能刘急。對此很難給出一個數(shù)量級棚菊，因為這取決于你需要的是哪種操作：

順序訪問（比如：全掃描） vs 隨機訪問（比如：按照row id訪問）
讀還是寫

以及數(shù)據(jù)庫使用的磁盤類型：

7.2k/10k/15k rpm的硬盤
SSD
RAID 1/5/…

要我說，內(nèi)存比磁盤要快100到10萬倍叔汁。

然而统求，這導致了另一個問題（數(shù)據(jù)庫總是這樣…)，緩存管理器需要在查詢執(zhí)行器使用數(shù)據(jù)之前得到數(shù)據(jù)据块，否則查詢管理器不得不等待數(shù)據(jù)從緩慢的磁盤中讀出來码邻。

預讀

這個問題叫預讀。查詢執(zhí)行器知道它將需要什么數(shù)據(jù)另假，因為它了解整個查詢流像屋，而且通過統(tǒng)計也了解磁盤上的數(shù)據(jù)。道理是這樣的：

當查詢執(zhí)行器處理它的第一批數(shù)據(jù)時
會告訴緩存管理器預先裝載第二批數(shù)據(jù)
當開始處理第二批數(shù)據(jù)時
告訴緩存管理器預先裝載第三批數(shù)據(jù)浪谴，并且告訴緩存管理器第一批可以從緩存里清掉了开睡。
……

緩存管理器在緩沖池里保存所有的這些數(shù)據(jù)。為了確定一條數(shù)據(jù)是否有用苟耻，緩存管理器給緩存的數(shù)據(jù)添加了額外的信息（叫閂鎖）篇恒。

有時查詢執(zhí)行器不知道它需要什么數(shù)據(jù)，有的數(shù)據(jù)庫也不提供這個功能凶杖。相反胁艰，它們使用一種推測預讀法（比如：如果查詢執(zhí)行器想要數(shù)據(jù)1、3智蝠、5腾么，它不久后很可能會要 7、9杈湾、11）解虱，或者順序預讀法（這時候緩存管理器只是讀取一批數(shù)據(jù)后簡單地從磁盤加載下一批連續(xù)數(shù)據(jù)）。

為了監(jiān)控預讀的工作狀況漆撞，現(xiàn)代數(shù)據(jù)庫引入了一個度量叫緩沖/緩存命中率殴泰，用來顯示請求的數(shù)據(jù)在緩存中找到而不是從磁盤讀取的頻率于宙。

注：糟糕的緩存命中率不總是意味著緩存工作狀態(tài)不佳。更多信息請閱讀Oracle文檔悍汛。

緩沖只是容量有限的內(nèi)存空間捞魁，因此，為了加載新的數(shù)據(jù)离咐，它需要移除一些數(shù)據(jù)谱俭。加載和清除緩存需要一些磁盤和網(wǎng)絡(luò)I/O的成本。如果你有個經(jīng)常執(zhí)行的查詢宵蛀，那么每次都把查詢結(jié)果加載然后清除昆著，效率就太低了。現(xiàn)代數(shù)據(jù)庫用緩沖區(qū)置換策略來解決這個問題术陶。

緩沖區(qū)置換策略

多數(shù)現(xiàn)代數(shù)據(jù)庫(至少 SQL Server, MySQL, Oracle 和 DB2)使用 LRU 算法宣吱。

LRU

LRU代表最近最少使用（Least Recently Used）算法，背后的原理是：在緩存里保留的數(shù)據(jù)是最近使用的瞳别，所以更有可能再次使用。

圖解：

image

為了更好的理解杭攻，我假設(shè)緩沖區(qū)里的數(shù)據(jù)沒有被閂鎖鎖姿盍病（就是說是可以被移除的）。在這個簡單的例子里兆解，緩沖區(qū)可以保存 3 個元素：

1：緩存管理器（簡稱CM）使用數(shù)據(jù)1馆铁，把它放入空的緩沖區(qū)
2：CM使用數(shù)據(jù)4，把它放入半載的緩沖區(qū)
3：CM使用數(shù)據(jù)3锅睛，把它放入半載的緩沖區(qū)
4：CM使用數(shù)據(jù)9埠巨，緩沖區(qū)滿了，所以數(shù)據(jù)1被清除现拒，因為它是最后一個最近使用的辣垒，數(shù)據(jù)9加入到緩沖區(qū)
5：CM使用數(shù)據(jù)4，數(shù)據(jù)4已經(jīng)在緩沖區(qū)了印蔬，所以它再次成為第一個最近使用的勋桶。
6：CM使用數(shù)據(jù)1，緩沖區(qū)滿了霸株，所以數(shù)據(jù)9被清除枢舶，因為它是最后一個最近使用的兜挨，數(shù)據(jù)1加入到緩沖區(qū)
……

這個算法效果很好，但是有些限制鹃锈。如果對一個大表執(zhí)行全表掃描怎么辦？換句話說瞧预，當表/索引的大小超出緩沖區(qū)會發(fā)生什么屎债？使用這個算法會清除之前緩存內(nèi)所有的數(shù)據(jù)仅政，而且全掃描的數(shù)據(jù)很可能只使用一次。

改進

為了防止這個現(xiàn)象扔茅，有些數(shù)據(jù)庫增加了特殊的規(guī)則已旧，比如Oracle文檔中的描述：

『對非常大的表來說，數(shù)據(jù)庫通常使用直接路徑來讀取召娜，即直接加載區(qū)塊[……]运褪，來避免填滿緩沖區(qū)。對于中等大小的表玖瘸，數(shù)據(jù)庫可以使用直接讀取或緩存讀取秸讹。如果選擇緩存讀取，數(shù)據(jù)庫把區(qū)塊置于LRU的尾部璃诀，防止清空當前緩沖區(qū)劣欢。』

還有一些可能，比如使用高級版本的LRU价脾，叫做 LRU-K牧抵。例如，SQL Server 使用 LRU-2。

這個算法的原理是把更多的歷史記錄考慮進來映琳。簡單LRU（也就是 LRU-1），只考慮最后一次使用的數(shù)據(jù)谎脯。LRU-K呢：

考慮數(shù)據(jù)最后第K次使用的情況
數(shù)據(jù)使用的次數(shù)加進了權(quán)重
一批新數(shù)據(jù)加載進入緩存娱俺，舊的但是經(jīng)常使用的數(shù)據(jù)不會被清除（因為權(quán)重更高）
但是這個算法不會保留緩存中不再使用的數(shù)據(jù)
所以數(shù)據(jù)如果不再使用，權(quán)重值隨著時間推移而降低

計算權(quán)重是需要成本的，所以SQL Server只是使用 K=2慎冤，這個值性能不錯而且額外開銷可以接受。

關(guān)于LRU-K更深入的知識，可以閱讀早期的研究論文（1993）：數(shù)據(jù)庫磁盤緩沖的LRU-K頁面置換算法

其他算法

當然還有其他管理緩存的算法，比如：

2Q（類LRU-K算法）
CLOCK（類LRU-K算法）
MRU（最新使用的算法，用LRU同樣的邏輯但不同的規(guī)則）
LRFU（Least Recently and Frequently Used，最近最少使用最近最不常用）
……

寫緩沖區(qū)

我只探討了讀緩存 —— 在使用之前預先加載數(shù)據(jù)挨摸。用來保存數(shù)據(jù)锅移、成批刷入磁盤置逻，而不是逐條寫入數(shù)據(jù)從而造成很多單次磁盤訪問鬓催。

要記住，緩沖區(qū)保存的是頁（最小的數(shù)據(jù)單位）而不是行（邏輯上/人類習慣的觀察數(shù)據(jù)的方式）。緩沖池內(nèi)的頁如果被修改了但還沒有寫入磁盤布卡，就是臟頁崔挖。有很多算法來決定寫入臟頁的最佳時機薛匪，但這個問題與事務(wù)的概念高度關(guān)聯(lián)，下面我們就談?wù)勈聞?wù)。

事務(wù)管理器

最后但同樣重要的苞俘，是事務(wù)管理器做裙，我們將看到這個進程是如何保證每個查詢在自己的事務(wù)內(nèi)執(zhí)行的澜驮。但開始之前悍缠，我們需要理解ACID事務(wù)的概念廊蜒。

“I’m on acid”

一個ACID事務(wù)是一個工作單元著榴，它要保證4個屬性：

原子性（Atomicity）: 事務(wù)『要么全部完成，要么全部取消』，即使它持續(xù)運行10個小時。如果事務(wù)崩潰，狀態(tài)回到事務(wù)之前（事務(wù)回滾）疟呐。
隔離性（Isolation）: 如果2個事務(wù) A 和 B 同時運行珊泳，事務(wù) A 和 B 最終的結(jié)果是相同的，不管 A 是結(jié)束于 B 之前/之后/運行期間。
持久性（Durability）: 一旦事務(wù)提交（也就是成功執(zhí)行）,不管發(fā)生什么（崩潰或者出錯）衡创，數(shù)據(jù)要保存在數(shù)據(jù)庫中。
一致性（Consistency）: 只有合法的數(shù)據(jù)（依照關(guān)系約束和函數(shù)約束）能寫入數(shù)據(jù)庫，一致性與原子性和隔離性有關(guān)。

image

在同一個事務(wù)內(nèi)，你可以運行多個SQL查詢來讀取、創(chuàng)建京痢、更新和刪除數(shù)據(jù)疲陕。當兩個事務(wù)使用相同的數(shù)據(jù)携茂，麻煩就來了吩谦。經(jīng)典的例子是從賬戶A到賬戶B的匯款咐扭。假設(shè)有2個事務(wù)：

事務(wù)1（T1）從賬戶A取出100美元給賬戶B
事務(wù)2（T2）從賬戶A取出50美元給賬戶B

我們回來看看ACID屬性：

原子性確保不管 T1 期間發(fā)生什么（服務(wù)器崩潰、網(wǎng)絡(luò)中斷…），你不能出現(xiàn)賬戶A 取走了100美元但沒有給賬戶B 的現(xiàn)象（這就是數(shù)據(jù)不一致狀態(tài)）。
隔離性確保如果 T1 和 T2 同時發(fā)生，最終A將減少150美元硕蛹，B將得到150美元倔毙，而不是其他結(jié)果，比如因為 T2 部分抹除了 T1 的行為，A減少150美元而B只得到50美元（這也是不一致狀態(tài)）葡缰。
持久性確保如果 T1 剛剛提交缭受，數(shù)據(jù)庫就發(fā)生崩潰，T1 不會消失得無影無蹤。
一致性確保錢不會在系統(tǒng)內(nèi)生成或滅失。

[以下部分不重要甘萧，可以跳過]

現(xiàn)代數(shù)據(jù)庫不會使用純粹的隔離作為默認模式酸钦，因為它會帶來巨大的性能消耗。SQL一般定義4個隔離級別：

串行化(Serializable，SQLite默認模式）：最高級別的隔離。兩個同時發(fā)生的事務(wù)100%隔離，每個事務(wù)有自己的『世界』。
可重復讀（Repeatable read，MySQL默認模式）：每個事務(wù)有自己的『世界』，除了一種情況醋安。如果一個事務(wù)成功執(zhí)行并且添加了新數(shù)據(jù)，這些數(shù)據(jù)對其他正在執(zhí)行的事務(wù)是可見的叭首。但是如果事務(wù)成功修改了一條數(shù)據(jù)姻报，修改結(jié)果對正在運行的事務(wù)不可見厢破。所以，事務(wù)之間只是在新數(shù)據(jù)方面突破了隔離，對已存在的數(shù)據(jù)仍舊隔離。
舉個例子鲫骗，如果事務(wù)A運行”SELECT count(1) from TABLE_X” ，然后事務(wù)B在 TABLE_X 加入一條新數(shù)據(jù)并提交晴楔，當事務(wù)A再運行一次 count(1)結(jié)果不會是一樣的凑队。
這叫幻讀（phantom read）遗增。
讀取已提交（Read committed，Oracle、PostgreSQL、SQL Server默認模式）：可重復讀+新的隔離突破。如果事務(wù)A讀取了數(shù)據(jù)D，然后數(shù)據(jù)D被事務(wù)B修改（或刪除）并提交，事務(wù)A再次讀取數(shù)據(jù)D時數(shù)據(jù)的變化（或刪除）是可見的泽铛。
這叫不可重復讀（non-repeatable read）月褥。
讀取未提交（Read uncommitted）：最低級別的隔離，是讀取已提交+新的隔離突破瓢喉。如果事務(wù)A讀取了數(shù)據(jù)D宁赤，然后數(shù)據(jù)D被事務(wù)B修改（但并未提交，事務(wù)B仍在運行中）决左，事務(wù)A再次讀取數(shù)據(jù)D時，數(shù)據(jù)修改是可見的走贪。如果事務(wù)B回滾佛猛，那么事務(wù)A第二次讀取的數(shù)據(jù)D是無意義的，因為那是事務(wù)B所做的從未發(fā)生的修改（已經(jīng)回滾了嘛）坠狡。
這叫臟讀（dirty read）继找。

多數(shù)數(shù)據(jù)庫添加了自定義的隔離級別（比如 PostgreSQL、Oracle逃沿、SQL Server的快照隔離）婴渡，而且并沒有實現(xiàn)SQL規(guī)范里的所有級別（尤其是讀取未提交級別）。

默認的隔離級別可以由用戶/開發(fā)者在建立連接時覆蓋（只需要增加很簡單的一行代碼）凯亮。

并發(fā)控制

確保隔離性缩搅、一致性和原子性的真正問題是對相同數(shù)據(jù)的寫操作（增、更触幼、刪）：

如果所有事務(wù)只是讀取數(shù)據(jù)硼瓣，它們可以同時工作，不會更改另一個事務(wù)的行為置谦。
如果（至少）有一個事務(wù)在修改其他事務(wù)讀取的數(shù)據(jù)堂鲤，數(shù)據(jù)庫需要找個辦法對其它事務(wù)隱藏這種修改。而且媒峡，它還需要確保這個修改操作不會被另一個看不到這些數(shù)據(jù)修改的事務(wù)擦除瘟栖。

這個問題叫并發(fā)控制。

最簡單的解決辦法是依次執(zhí)行每個事務(wù)（即順序執(zhí)行）谅阿，但這樣就完全沒有伸縮性了半哟，在一個多處理器/多核服務(wù)器上只有一個核心在工作，效率很低签餐。

理想的辦法是寓涨，每次一個事務(wù)創(chuàng)建或取消時：

監(jiān)控所有事務(wù)的所有操作
檢查是否2個（或更多）事務(wù)的部分操作因為讀取/修改相同的數(shù)據(jù)而存在沖突
重新編排沖突事務(wù)中的操作來減少沖突的部分
按照一定的順序執(zhí)行沖突的部分（同時非沖突事務(wù)仍然在并發(fā)運行）
考慮事務(wù)有可能被取消

用更正規(guī)的說法，這是對沖突的調(diào)度問題氯檐。更具體點兒說戒良，這是個非常困難而且CPU開銷很大的優(yōu)化問題。企業(yè)級數(shù)據(jù)庫無法承擔等待幾個小時冠摄，來尋找每個新事務(wù)活動最好的調(diào)度糯崎，因此就使用不那么理想的方式以避免更多的時間浪費在解決沖突上几缭。

鎖管理器

為了解決這個問題，多數(shù)數(shù)據(jù)庫使用鎖和/或數(shù)據(jù)版本控制沃呢。這是個很大的話題年栓，我會集中探討鎖，和一點點數(shù)據(jù)版本控制薄霜。

悲觀鎖

原理是：

如果一個事務(wù)需要一條數(shù)據(jù)
它就把數(shù)據(jù)鎖住
如果另一個事務(wù)也需要這條數(shù)據(jù)
它就必須要等第一個事務(wù)釋放這條數(shù)據(jù)
這個鎖叫排他鎖韵洋。

但是對一個僅僅讀取數(shù)據(jù)的事務(wù)使用排他鎖非常昂貴，因為這會迫使其它只需要讀取相同數(shù)據(jù)的事務(wù)等待黄锤。因此就有了另一種鎖，共享鎖食拜。

共享鎖是這樣的：

如果一個事務(wù)只需要讀取數(shù)據(jù)A
它會給數(shù)據(jù)A加上『共享鎖』并讀取
如果第二個事務(wù)也需要僅僅讀取數(shù)據(jù)A
它會給數(shù)據(jù)A加上『共享鎖』并讀取
如果第三個事務(wù)需要修改數(shù)據(jù)A
它會給數(shù)據(jù)A加上『排他鎖』鸵熟，但是必須等待另外兩個事務(wù)釋放它們的共享鎖。

同樣的负甸，如果一塊數(shù)據(jù)被加上排他鎖流强，一個只需要讀取該數(shù)據(jù)的事務(wù)必須等待排他鎖釋放才能給該數(shù)據(jù)加上共享鎖。

image

鎖管理器是添加和釋放鎖的進程呻待，在內(nèi)部用一個哈希表保存鎖信息（關(guān)鍵字是被鎖的數(shù)據(jù)）打月，并且了解每一塊數(shù)據(jù)是：

被哪個事務(wù)加的鎖
哪個事務(wù)在等待數(shù)據(jù)解鎖

死鎖

但是使用鎖會導致一種情況，2個事務(wù)永遠在等待一塊數(shù)據(jù)：

image

在本圖中：

事務(wù)A 給數(shù)據(jù)1 加上排他鎖并且等待獲取數(shù)據(jù)2
事務(wù)B 給數(shù)據(jù)2 加上排他鎖并且等待獲取數(shù)據(jù)1

這叫死鎖蚕捉。

在死鎖發(fā)生時奏篙，鎖管理器要選擇取消（回滾）一個事務(wù)，以便消除死鎖迫淹。這可是個艱難的決定：

殺死數(shù)據(jù)修改量最少的事務(wù)（這樣能減少回滾的成本）秘通？
殺死持續(xù)時間最短的事務(wù)，因為其它事務(wù)的用戶等的時間更長敛熬？
殺死能用更少時間結(jié)束的事務(wù)（避免可能的資源饑荒）肺稀？
一旦發(fā)生回滾，有多少事務(wù)會受到回滾的影響应民？

在作出選擇之前话原，鎖管理器需要檢查是否有死鎖存在。

哈希表可以看作是個圖表（見上文圖）诲锹，圖中出現(xiàn)循環(huán)就說明有死鎖繁仁。由于檢查循環(huán)是昂貴的（所有鎖組成的圖表是很龐大的），經(jīng)常會通過簡單的途徑解決：使用超時設(shè)定归园。如果一個鎖在超時時間內(nèi)沒有加上改备，那事務(wù)就進入死鎖狀態(tài)。

鎖管理器也可以在加鎖之前檢查該鎖會不會變成死鎖蔓倍，但是想要完美的做到這一點還是很昂貴的悬钳。因此這些預檢經(jīng)常設(shè)置一些基本規(guī)則盐捷。

兩段鎖

實現(xiàn)純粹的隔離最簡單的方法是：事務(wù)開始時獲取鎖，結(jié)束時釋放鎖默勾。就是說碉渡，事務(wù)開始前必須等待確保自己能加上所有的鎖，當事務(wù)結(jié)束時釋放自己持有的鎖母剥。這是行得通的滞诺，但是為了等待所有的鎖，大量的時間被浪費了环疼。

更快的方法是兩段鎖協(xié)議（Two-Phase Locking Protocol习霹，由 DB2 和 SQL Server使用），在這里炫隶，事務(wù)分為兩個階段：

成長階段：事務(wù)可以獲得鎖淋叶，但不能釋放鎖。
收縮階段：事務(wù)可以釋放鎖（對于已經(jīng)處理完而且不會再次處理的數(shù)據(jù)）伪阶，但不能獲得新鎖煞檩。

image

這兩條簡單規(guī)則背后的原理是：

釋放不再使用的鎖，來降低其它事務(wù)的等待時間
防止發(fā)生這類情況：事務(wù)最初獲得的數(shù)據(jù)栅贴，在事務(wù)開始后被修改斟湃，當事務(wù)重新讀取該數(shù)據(jù)時發(fā)生不一致。

這個規(guī)則可以很好地工作檐薯，但有個例外：如果修改了一條數(shù)據(jù)凝赛、釋放了關(guān)聯(lián)的鎖后，事務(wù)被取消（回滾）坛缕，而另一個事務(wù)讀到了修改后的值哄酝，但最后這個值卻被回滾。為了避免這個問題祷膳，所有獨占鎖必須在事務(wù)結(jié)束時釋放陶衅。

多說幾句

當然了，真實的數(shù)據(jù)庫使用更復雜的系統(tǒng)直晨，涉及到更多類型的鎖（比如意向鎖搀军，intention locks）和更多的粒度（行級鎖、頁級鎖勇皇、分區(qū)鎖罩句、表鎖、表空間鎖）敛摘，但是道理是相同的门烂。

我只探討純粹基于鎖的方法，數(shù)據(jù)版本控制是解決這個問題的另一個方法。

版本控制是這樣的：

每個事務(wù)可以在相同時刻修改相同的數(shù)據(jù)
每個事務(wù)有自己的數(shù)據(jù)拷貝（或者叫版本）
如果2個事務(wù)修改相同的數(shù)據(jù)屯远，只接受一個修改蔓姚，另一個將被拒絕，相關(guān)的事務(wù)回滾（或重新運行）

這將提高性能慨丐，因為：

讀事務(wù)不會阻塞寫事務(wù)
寫事務(wù)不會阻塞讀
沒有『臃腫緩慢』的鎖管理器帶來的額外開銷

除了兩個事務(wù)寫相同數(shù)據(jù)的時候坡脐，數(shù)據(jù)版本控制各個方面都比鎖表現(xiàn)得更好。只不過房揭，你很快就會發(fā)現(xiàn)磁盤空間消耗巨大备闲。

數(shù)據(jù)版本控制和鎖機制是兩種不同的見解：樂觀鎖和悲觀鎖。兩者各有利弊捅暴，完全取決于使用場景（讀多還是寫多）恬砂。關(guān)于數(shù)據(jù)版本控制，我推薦這篇非常優(yōu)秀的文章蓬痒，講的是PostgreSQL如何實現(xiàn)多版本并發(fā)控制的泻骤。

一些數(shù)據(jù)庫，比如DB2（直到版本 9.7）和 SQL Server（不含快照隔離）僅使用鎖機制乳幸。其他的像PostgreSQL, MySQL 和 Oracle 使用鎖和鼠標版本控制混合機制。我不知道是否有僅用版本控制的數(shù)據(jù)庫（如果你知道請告訴我）钧椰。

[2015-08-20更新]一名讀者告訴我：

Firebird 和 Interbase 用不帶鎖的版本控制粹断。

版本控制對索引的影響挺有趣的：有時唯一索引會出現(xiàn)重復，索引的條目會多于表行數(shù)嫡霞，等等瓶埋。

如果你讀過不同級別的隔離那部分內(nèi)容，你會知道诊沪，提高隔離級別就會增加鎖的數(shù)量和事務(wù)等待加鎖的時間养筒。這就是為什么多數(shù)數(shù)據(jù)庫默認不會使用最高級別的隔離（即串行化）。

當然端姚，你總是可以自己去主流數(shù)據(jù)庫（像MySQL, PostgreSQL 或 Oracle）的文檔里查一下晕粪。

日志管理器

我們已經(jīng)知道，為了提升性能渐裸，數(shù)據(jù)庫把數(shù)據(jù)保存在內(nèi)存緩沖區(qū)內(nèi)巫湘。但如果當事務(wù)提交時服務(wù)器崩潰，崩潰時還在內(nèi)存里的數(shù)據(jù)會丟失昏鹃，這破壞了事務(wù)的持久性尚氛。

你可以把所有數(shù)據(jù)都寫在磁盤上，但是如果服務(wù)器崩潰洞渤，最終數(shù)據(jù)可能只有部分寫入磁盤阅嘶，這破壞了事務(wù)的原子性。

事務(wù)作出的任何修改必須是或者撤銷，或者完成讯柔。

有 2 個辦法解決這個問題：

影子副本/頁（Shadow copies/pages）：每個事務(wù)創(chuàng)建自己的數(shù)據(jù)庫副本（或部分數(shù)據(jù)庫的副本）抡蛙，并基于這個副本來工作。一旦出錯磷杏，這個副本就被移除溜畅；一旦成功，數(shù)據(jù)庫立即使用文件系統(tǒng)的一個把戲极祸，把副本替換到數(shù)據(jù)中慈格，然后刪掉『舊』數(shù)據(jù)。
事務(wù)日志（Transaction log）：事務(wù)日志是一個存儲空間遥金，在每次寫盤之前浴捆，數(shù)據(jù)庫在事務(wù)日志中寫入一些信息，這樣當事務(wù)崩潰或回滾稿械，數(shù)據(jù)庫知道如何移除或完成尚未完成的事務(wù)选泻。

WAL（預寫式日志）

影子副本/頁在運行較多事務(wù)的大型數(shù)據(jù)庫時制造了大量磁盤開銷，所以現(xiàn)代數(shù)據(jù)庫使用事務(wù)日志美莫。事務(wù)日志必須保存在穩(wěn)定的存儲上页眯，我不會深挖存儲技術(shù)，但至少RAID磁盤是必須的厢呵，以防磁盤故障窝撵。

多數(shù)數(shù)據(jù)庫（至少是Oracle, SQL Server, DB2, PostgreSQL, MySQL 和 SQLite) 使用預寫日志協(xié)議（Write-Ahead Logging protocol ，WAL）來處理事務(wù)日志襟铭。WAL協(xié)議有 3 個規(guī)則：

1. 每個對數(shù)據(jù)庫的修改都產(chǎn)生一條日志記錄碌奉，在數(shù)據(jù)寫入磁盤之前日志記錄必須寫入事務(wù)日志。
1. 日志記錄必須按順序?qū)懭牒挥涗?A 發(fā)生在記錄 B 之前赐劣，則 A 必須寫在 B 之前。
1. 當一個事務(wù)提交時哩都，在事務(wù)成功之前魁兼，提交順序必須寫入到事務(wù)日志。

image

這個工作由日志管理器完成漠嵌。簡單的理解就是璃赡，日志管理器處于緩存管理器（cache manager）和數(shù)據(jù)訪問管理器（data access manager，負責把數(shù)據(jù)寫入磁盤）之間献雅，每個 update / delete / create / commit / rollback 操作在寫入磁盤之前先寫入事務(wù)日志碉考。簡單，對吧挺身？

回答錯誤侯谁！我們研究了這么多內(nèi)容，現(xiàn)在你應(yīng)該知道與數(shù)據(jù)庫相關(guān)的每一件事都帶著『數(shù)據(jù)庫效應(yīng)』的詛咒。好吧墙贱，我們說正經(jīng)的热芹，問題在于，如何找到寫日志的同時保持良好的性能的方法惨撇。如果事務(wù)日志寫得太慢伊脓，整體都會慢下來。

ARIES

1992年魁衙，IBM 研究人員『發(fā)明』了WAL的增強版报腔，叫 ARIES。ARIES 或多或少地在現(xiàn)代數(shù)據(jù)庫中使用剖淀，邏輯未必相同纯蛾，但AIRES背后的概念無處不在。我給發(fā)明加了引號是因為纵隔，按照MIT這門課的說法翻诉，IBM 的研究人員『僅僅是寫了事務(wù)恢復的最佳實踐方法』。AIRES 論文發(fā)表的時候我才 5 歲捌刮，我不關(guān)心那些酸溜溜的科研人員老掉牙的閑言碎語碰煌。事實上，我提及這個典故绅作，是在開始探討最后一個技術(shù)點前讓你輕松一下芦圾。我閱讀過這篇 ARIES 論文的大量篇幅，發(fā)現(xiàn)它很有趣棚蓄。在這一部分我只是簡要的談一下 ARIES堕扶，不過我強烈建議碍脏，如果你想了解真正的知識梭依，就去讀那篇論文耻陕。

ARIES 代表『數(shù)據(jù)庫恢復原型算法』（Algorithms for Recovery and Isolation Exploiting Semantics）扩灯。

這個技術(shù)要達到一個雙重目標：

1. 寫日志的同時保持良好性能
1. 快速和可靠的數(shù)據(jù)恢復

有多個原因讓數(shù)據(jù)庫不得不回滾事務(wù)：

因為用戶取消
因為服務(wù)器或網(wǎng)絡(luò)故障
因為事務(wù)破壞了數(shù)據(jù)庫完整性（比如一個列有唯一性約束而事務(wù)添加了重復值）
因為死鎖

有時候（比如網(wǎng)絡(luò)出現(xiàn)故障）淹魄，數(shù)據(jù)庫可以恢復事務(wù)筑公。

這怎么可能呢武花？為了回答這個問題球涛，我們需要了解日志里保存的信息珍促。

日志

事務(wù)的每一個操作（增/刪/改）產(chǎn)生一條日志锨匆，由如下內(nèi)容組成：

LSN：一個唯一的日志序列號（Log Sequence Number）褥紫。LSN是按時間順序分配的 * 姜性，這意味著如果操作 A 先于操作 B，log A 的 LSN 要比 log B 的 LSN 小髓考。
TransID：產(chǎn)生操作的事務(wù)ID部念。
PageID：被修改的數(shù)據(jù)在磁盤上的位置。磁盤數(shù)據(jù)的最小單位是頁，所以數(shù)據(jù)的位置就是它所處頁的位置儡炼。
PrevLSN：同一個事務(wù)產(chǎn)生的上一條日志記錄的鏈接妓湘。
UNDO：取消本次操作的方法。
比如乌询，如果操作是一次更新榜贴，UNDO將或者保存元素更新前的值/狀態(tài)（物理UNDO），或者回到原來狀態(tài)的反向操作（邏輯UNDO） **妹田。
REDO：重復本次操作的方法唬党。同樣的，有 2 種方法：或者保存操作后的元素值/狀態(tài)秆麸，或者保存操作本身以便重復初嘹。
…：（供您參考，一個 ARIES 日志還有 2 個字段：UndoNxtLSN 和 Type）沮趣。

進一步說屯烦，磁盤上每個頁（保存數(shù)據(jù)的，不是保存日志的）都記錄著最后一個修改該數(shù)據(jù)操作的LSN房铭。

*LSN的分配其實更復雜驻龟，因為它關(guān)系到日志存儲的方式。但道理是相同的缸匪。

** ARIES 只使用邏輯UNDO翁狐，因為處理物理UNDO太過混亂了。

注：據(jù)我所知凌蔬，只有 PostgreSQL 沒有使用UNDO露懒，而是用一個垃圾回收服務(wù)來刪除舊版本的數(shù)據(jù)。這個跟 PostgreSQL 對數(shù)據(jù)版本控制的實現(xiàn)有關(guān)砂心。

為了更好的說明這一點懈词，這有一個簡單的日志記錄演示圖，是由查詢 “UPDATE FROM PERSON SET AGE = 18;” 產(chǎn)生的辩诞，我們假設(shè)這個查詢是事務(wù)18執(zhí)行的坎弯。【譯者注： SQL 語句原文如此译暂，應(yīng)該是作者筆誤】

image

每條日志都有一個唯一的LSN抠忘，鏈接在一起的日志屬于同一個事務(wù)。日志按照時間順序鏈接（鏈接列表的最后一條日志是最后一個操作產(chǎn)生的）外永。

日志緩沖區(qū)

為了防止寫日志成為主要的瓶頸崎脉，數(shù)據(jù)庫使用了日志緩沖區(qū)。

image

當查詢執(zhí)行器要求做一次修改：

1. 緩存管理器將修改存入自己的緩沖區(qū)伯顶；
1. 日志管理器將相關(guān)的日志存入自己的緩沖區(qū)囚灼；
1. 到了這一步呛踊，查詢執(zhí)行器認為操作完成了（因此可以請求做另一次修改）；
1. 接著（不久以后）日志管理器把日志寫入事務(wù)日志啦撮，什么時候?qū)懭罩居赡乘惴▉頉Q定谭网。
1. 接著（不久以后）緩存管理器把修改寫入磁盤，什么時候?qū)懕P由某算法來決定赃春。

當事務(wù)提交愉择，意味著事務(wù)每一個操作的 1 2 3 4 5 步驟都完成了。寫事務(wù)日志是很快的织中，因為它只是『在事務(wù)日志某處增加一條日志』锥涕；而數(shù)據(jù)寫盤就更復雜了，因為要用『能夠快速讀取的方式寫入數(shù)據(jù)』狭吼。

STEAL 和 FORCE 策略

出于性能方面的原因层坠，第 5 步有可能在提交之后完成，因為一旦發(fā)生崩潰刁笙，還有可能用REDO日志恢復事務(wù)破花。這叫做 NO-FORCE策略。

數(shù)據(jù)庫可以選擇FORCE策略（比如第 5 步在提交之前必須完成）來降低恢復時的負載疲吸。

另一個問題是座每，要選擇數(shù)據(jù)是一步步的寫入（STEAL策略），還是緩沖管理器需要等待提交命令來一次性全部寫入（NO-STEAL策略）摘悴。選擇STEAL還是NO-STEAL取決于你想要什么：快速寫入但是從 UNDO 日志恢復緩慢峭梳，還是快速恢復。

總結(jié)一下這些策略對恢復的影響：

STEAL/NO-FORCE 需要 UNDO 和 REDO: 性能高蹂喻，但是日志和恢復過程更復雜 (比如 ARIES)葱椭。多數(shù)數(shù)據(jù)庫選擇這個策略。注：這是我從多個學術(shù)論文和教程里看到的口四，但并沒有看到官方文檔里顯式說明這一點孵运。
STEAL/ FORCE 只需要 UNDO.
NO-STEAL/NO-FORCE 只需要 REDO.
NO-STEAL/FORCE 什么也不需要: 性能最差，而且需要巨大的內(nèi)存窃祝。

關(guān)于恢復

Ok掐松，有了不錯的日志踱侣，我們來用用它們粪小！

假設(shè)新來的實習生讓數(shù)據(jù)庫崩潰了（首要規(guī)矩：永遠是實習生的錯。）抡句，你重啟了數(shù)據(jù)庫探膊，恢復過程開始了。

ARIES從崩潰中恢復有三個階段：

1. 分析階段：恢復進程讀取全部事務(wù)日志待榔，來重建崩潰過程中所發(fā)生事情的時間線逞壁，決定哪個事務(wù)要回滾（所有未提交的事務(wù)都要回滾）流济、崩潰時哪些數(shù)據(jù)需要寫盤。
1. Redo階段：這一關(guān)從分析中選中的一條日志記錄開始腌闯，使用 REDO 來將數(shù)據(jù)庫恢復到崩潰之前的狀態(tài)绳瘟。
  在REDO階段，REDO日志按照時間順序處理（使用LSN）姿骏。
  對每一條日志糖声，恢復進程需要讀取包含數(shù)據(jù)的磁盤頁LSN。
  如果LSN（磁盤頁）>= LSN（日志記錄）分瘦，說明數(shù)據(jù)已經(jīng)在崩潰前寫到磁盤（但是值已經(jīng)被日志之后蘸泻、崩潰之前的某個操作覆蓋），所以不需要做什么嘲玫。
  如果LSN（磁盤頁）< LSN（日志記錄）悦施，那么磁盤上的頁將被更新。
  即使將被回滾的事務(wù)去团，REDO也是要做的抡诞，因為這樣簡化了恢復過程（但是我相信現(xiàn)代數(shù)據(jù)庫不會這么做的）。
1. Undo階段：這一階段回滾所有崩潰時未完成的事務(wù)土陪°迦蓿回滾從每個事務(wù)的最后一條日志開始，并且按照時間倒序處理UNDO日志（使用日志記錄的PrevLSN）旺坠。

恢復過程中乔遮，事務(wù)日志必須留意恢復過程的操作，以便寫入磁盤的數(shù)據(jù)與事務(wù)日志相一致取刃。一個解決辦法是移除被取消的事務(wù)產(chǎn)生的日志記錄蹋肮，但是這個太困難了。相反璧疗，ARIES在事務(wù)日志中記錄補償日志坯辩，來邏輯上刪除被取消的事務(wù)的日志記錄。

當事務(wù)被『手工』取消崩侠，或者被鎖管理器取消（為了消除死鎖）漆魔，或僅僅因為網(wǎng)絡(luò)故障而取消，那么分析階段就不需要了却音。對于哪些需要 REDO 哪些需要 UNDO 的信息在 2 個內(nèi)存表中：

事務(wù)表（保存當前所有事務(wù)的狀態(tài)）
臟頁表（保存哪些數(shù)據(jù)需要寫入磁盤）

當新的事務(wù)產(chǎn)生時改抡，這兩個表由緩存管理器和事務(wù)管理器更新。因為是在內(nèi)存中系瓢，當數(shù)據(jù)庫崩潰時它們也被破壞掉了阿纤。

分析階段的任務(wù)就是在崩潰之后，用事務(wù)日志中的信息重建上述的兩個表夷陋。為了加快分析階段欠拾，ARIES提出了一個概念：檢查點（check point）胰锌，就是不時地把事務(wù)表和臟頁表的內(nèi)容，還有此時最后一條LSN寫入磁盤藐窄。那么在分析階段當中资昧，只需要分析這個LSN之后的日志即可。

結(jié)語

寫這篇文章之前荆忍，我知道這個題目有多大榛搔，也知道寫這樣一篇深入的文章會相當耗時。最后證明我過于樂觀了东揣，實際上花了兩倍于預期的時間践惑，但是我學到了很多。

如果你想很好地了解數(shù)據(jù)庫嘶卧，我推薦這篇研究論文：《數(shù)據(jù)庫系統(tǒng)架構(gòu)》尔觉，對數(shù)據(jù)庫有很好的介紹（共110頁），而且非計算機專業(yè)人士也能讀懂芥吟。這篇論文出色的幫助我制定了本文的寫作計劃侦铜，它沒有像本文那樣專注于數(shù)據(jù)結(jié)構(gòu)和算法，更多的講了架構(gòu)方面的概念钟鸵。

如果你仔細閱讀了本文钉稍，你現(xiàn)在應(yīng)該了解一個數(shù)據(jù)庫是多么的強大了。鑒于文章很長棺耍，讓我來提醒你我們都學到了什么：

B+樹索引概述
數(shù)據(jù)庫的全局概述
基于成本的優(yōu)化概述贡未，特別專注了聯(lián)接運算
緩沖池管理概述
事務(wù)管理概述

但是，數(shù)據(jù)庫包含了更多的聰明巧技蒙袍。比如俊卤，我并沒有談到下面這些棘手的問題：

如何管理數(shù)據(jù)庫集群和全局事務(wù)
如何在數(shù)據(jù)庫運行的時候產(chǎn)生快照
如何高效地存儲（和壓縮）數(shù)據(jù)
如何管理內(nèi)存

所以，當你不得不在問題多多的 NoSQL數(shù)據(jù)庫和堅如磐石的關(guān)系型數(shù)據(jù)庫之間抉擇的時候害幅，要三思而行消恍。不要誤會，某些 NoSQL數(shù)據(jù)庫是很棒的以现，但是它們畢竟還年輕狠怨，只是解決了少量應(yīng)用關(guān)注的一些特定問題。

最后說一句邑遏，如果有人問你數(shù)據(jù)庫的原理是什么佣赖，你不用逃之夭夭，現(xiàn)在你可以回答：

image

或者无宿，就讓他/她來看本文吧茵汰。