一提到關(guān)系型數(shù)據(jù)庫(kù)，我禁不住想：有些東西被忽視了。關(guān)系型數(shù)據(jù)庫(kù)無(wú)處不在，而且種類繁多，從小巧實(shí)用的 SQLite 到強(qiáng)大的 Teradata 。但很少有文章講解數(shù)據(jù)庫(kù)是如何工作的。你可以自己谷歌/百度一下『關(guān)系型數(shù)據(jù)庫(kù)原理』，看看結(jié)果多么的稀少 ，而且找到的那些文章都很短?，F(xiàn)在如果你查找最近時(shí)髦的技術(shù)（大數(shù)據(jù)、NoSQL或JAVAScript），你能找到更多深入探討它們?nèi)绾喂ぷ鞯奈恼隆ｋy道關(guān)系型數(shù)據(jù)庫(kù)已經(jīng)太古老太無(wú)趣，除了大學(xué)教材、研究文獻(xiàn)和書籍以外，沒(méi)人愿意講了嗎？

 

作為一個(gè)開發(fā)人員，我不喜歡用我不明白的東西。而且，數(shù)據(jù)庫(kù)已經(jīng)使用了40年之久，一定有理由的。多年以來(lái)，我花了成百上千個(gè)小時(shí)來(lái)真正領(lǐng)會(huì)這些我每天都在用的、古怪的黑盒子。關(guān)系型數(shù)據(jù)庫(kù)非常有趣，因?yàn)樗鼈兪腔趯?shí)用而且可復(fù)用的概念。如果你對(duì)了解一個(gè)數(shù)據(jù)庫(kù)感興趣，但是從未有時(shí)間或意愿來(lái)刻苦鉆研這個(gè)內(nèi)容廣泛的課題，你應(yīng)該喜歡這篇文章。

雖然本文標(biāo)題很明確，但我的目的并不是講如何使用數(shù)據(jù)庫(kù)。因此，你應(yīng)該已經(jīng)掌握怎么寫一個(gè)簡(jiǎn)單的 join query（聯(lián)接查詢）和CRUD操作（創(chuàng)建讀取更新刪除），否則你可能無(wú)法理解本文。這是唯一需要你了解的，其他的由我來(lái)講解。

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

（關(guān)于時(shí)間復(fù)雜度。計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。如果不了解這個(gè)概念建議先看看維基或百度百科，對(duì)于理解文章下面的內(nèi)容很有幫助）

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

這篇文章大約分為3個(gè)部分：

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

回到基礎(chǔ)

很久很久以前（在一個(gè)遙遠(yuǎn)而又遙遠(yuǎn)的星系……)，開發(fā)者必須確切地知道他們的代碼需要多少次運(yùn)算。他們把算法和數(shù)據(jù)結(jié)構(gòu)牢記于心，因?yàn)樗麄兊挠?jì)算機(jī)運(yùn)行緩慢，無(wú)法承受對(duì)CPU和內(nèi)存的浪費(fèi)。

在這一部分，我將提醒大家一些這類的概念，因?yàn)樗鼈儗?duì)理解數(shù)據(jù)庫(kù)至關(guān)重要。我還會(huì)介紹數(shù)據(jù)庫(kù)索引的概念。

O(1) vs O(n^2)

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

但是當(dāng)你應(yīng)對(duì)大量的數(shù)據(jù)（我說(shuō)的可不只是成千上萬(wàn)哈）或者你要爭(zhēng)取毫秒級(jí)操作，那么理解這個(gè)概念就很關(guān)鍵了。而且你猜怎么著，數(shù)據(jù)庫(kù)要同時(shí)處理這兩種情景！我不會(huì)占用你太長(zhǎng)時(shí)間，只要你能明白這一點(diǎn)就夠了。這個(gè)概念在下文會(huì)幫助我們理解什么是基于成本的優(yōu)化。

概念

時(shí)間復(fù)雜度用來(lái)檢驗(yàn)?zāi)硞€(gè)算法處理一定量的數(shù)據(jù)要花多長(zhǎng)時(shí)間。為了描述這個(gè)復(fù)雜度，計(jì)算機(jī)科學(xué)家使用數(shù)學(xué)上的『簡(jiǎn)明解釋算法中的大O符號(hào)』。這個(gè)表示法用一個(gè)函數(shù)來(lái)描述算法處理給定的數(shù)據(jù)需要多少次運(yùn)算。

比如，當(dāng)我說(shuō)『這個(gè)算法是適用 O(某函數(shù)())』，我的意思是對(duì)于某些數(shù)據(jù)，這個(gè)算法需要 某函數(shù)(數(shù)據(jù)量) 次運(yùn)算來(lái)完成。

重要的不是數(shù)據(jù)量，而是當(dāng)數(shù)據(jù)量增加時(shí)運(yùn)算如何增加。時(shí)間復(fù)雜度不會(huì)給出確切的運(yùn)算次數(shù)，但是給出的是一種理念。

 

圖中可以看到不同類型的復(fù)雜度的演變過(guò)程，我用了對(duì)數(shù)尺來(lái)建這個(gè)圖。具體點(diǎn)兒說(shuō)，數(shù)據(jù)量以很快的速度從1條增長(zhǎng)到10億條。我們可得到如下結(jié)論：

• 綠：O(1)或者叫常數(shù)階復(fù)雜度，保持為常數(shù)（要不人家就不會(huì)叫常數(shù)階復(fù)雜度了）。
• 紅：O(log(n))對(duì)數(shù)階復(fù)雜度，即使在十億級(jí)數(shù)據(jù)量時(shí)也很低。
• 粉：最糟糕的復(fù)雜度是 O(n^2)，平方階復(fù)雜度，運(yùn)算數(shù)快速膨脹。
• 黑和藍(lán)：另外兩種復(fù)雜度（的運(yùn)算數(shù)也是）快速增長(zhǎng)。

例子

數(shù)據(jù)量低時(shí)，O(1) 和 O(n^2)的區(qū)別可以忽略不計(jì)。比如，你有個(gè)算法要處理2000條元素。

• O(1) 算法會(huì)消耗 1 次運(yùn)算
• O(log(n)) 算法會(huì)消耗 7 次運(yùn)算
• O(n) 算法會(huì)消耗 2000 次運(yùn)算
• O(n*log(n)) 算法會(huì)消耗 14,000 次運(yùn)算
• O(n^2) 算法會(huì)消耗 4,000,000 次運(yùn)算

O(1) 和 O(n^2) 的區(qū)別似乎很大（4百萬(wàn)）,但你最多損失 2 毫秒，只是一眨眼的功夫。確實(shí)，當(dāng)今處理器每秒可處理上億次的運(yùn)算。這就是為什么性能和優(yōu)化在很多IT項(xiàng)目中不是問(wèn)題。

我說(shuō)過(guò)，面臨海量數(shù)據(jù)的時(shí)候，了解這個(gè)概念依然很重要。如果這一次算法需要處理 1,000,000 條元素（這對(duì)數(shù)據(jù)庫(kù)來(lái)說(shuō)也不算大）。

• O(1) 算法會(huì)消耗 1 次運(yùn)算
• O(log(n)) 算法會(huì)消耗 14 次運(yùn)算
• O(n) 算法會(huì)消耗 1,000,000 次運(yùn)算
• O(n*log(n)) 算法會(huì)消耗 14,000,000 次運(yùn)算
• O(n^2) 算法會(huì)消耗 1,000,000,000,000 次運(yùn)算

我沒(méi)有具體算過(guò)，但我要說(shuō)，用O(n^2) 算法的話你有時(shí)間喝杯咖啡（甚至再續(xù)一杯?。?。如果在數(shù)據(jù)量后面加個(gè)0，那你就可以去睡大覺(jué)了。

繼續(xù)深入

為了讓你能明白

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

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

有多種類型的時(shí)間復(fù)雜度

• 一般情況場(chǎng)景
• 最佳情況場(chǎng)景
• 最差情況場(chǎng)景

時(shí)間復(fù)雜度經(jīng)常處于最差情況場(chǎng)景。

這里我只探討時(shí)間復(fù)雜度，但復(fù)雜度還包括：

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

當(dāng)然還有比 n^2 更糟糕的復(fù)雜度，比如：

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

注：我并沒(méi)有給出『大O表示法』的真正定義，只是利用這個(gè)概念?？梢钥纯淳S基百科上的這篇文章。

合并排序

當(dāng)你要對(duì)一個(gè)集合排序時(shí)你怎么做？什么？調(diào)用 sort() 函數(shù)……好吧，算你對(duì)了……但是對(duì)于數(shù)據(jù)庫(kù)，你需要理解這個(gè) sort() 函數(shù)的工作原理。

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

合并

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

我們用個(gè)簡(jiǎn)單的例子來(lái)看看這是什么意思：

 

通過(guò)此圖你可以看到，在 2 個(gè) 4元素序列里你只需要迭代一次，就能構(gòu)建最終的8元素已排序序列，因?yàn)閮蓚€(gè)4元素序列已經(jīng)排好序了：

• 1) 在兩個(gè)序列中，比較當(dāng)前元素（當(dāng)前=頭一次出現(xiàn)的第一個(gè)）
• 2) 然后取出最小的元素放進(jìn)8元素序列中
• 3) 找到（兩個(gè)）序列的下一個(gè)元素，(比較后)取出最小的
• 重復(fù)1、2、3步驟，直到其中一個(gè)序列中的最后一個(gè)元素
• 然后取出另一個(gè)序列剩余的元素放入8元素序列中。

這個(gè)方法之所以有效，是因?yàn)閮蓚€(gè)4元素序列都已經(jīng)排好序，你不需要再『回到』序列中查找比較?！竞喜⑴判蛟敿?xì)原理，其中一個(gè)動(dòng)圖（原圖較長(zhǎng)，我做了刪減）清晰的演示了上述合并排序的過(guò)程，而原文的敘述似乎沒(méi)有這么清晰，不動(dòng)戳大?！?/p>

 

既然我們明白了這個(gè)技巧，下面就是我的合并排序偽代碼。

C

 

合并排序是把問(wèn)題拆分為小問(wèn)題，通過(guò)解決小問(wèn)題來(lái)解決最初的問(wèn)題（注：這種算法叫分治法，即『分而治之、各個(gè)擊破』）。如果你不懂，不用擔(dān)心，我第一次接觸時(shí)也不懂。如果能幫助你理解的話，我認(rèn)為這個(gè)算法是個(gè)兩步算法：

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

拆分階段

 

在拆分階段過(guò)程中，使用3個(gè)步驟將序列分為一元序列。步驟數(shù)量的值是 log(N) （因?yàn)?N=8, log(N)=3）?！咀g者注：底數(shù)為2，下文有說(shuō)明】

我怎么知道這個(gè)的？

我是天才！一句話：數(shù)學(xué)。道理是每一步都把原序列的長(zhǎng)度除以2，步驟數(shù)就是你能把原序列長(zhǎng)度除以2的次數(shù)。這正好是對(duì)數(shù)的定義（在底數(shù)為2時(shí)）。

排序階段

 

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

• 第一步，4 次合并，每次成本是 2 次運(yùn)算。
• 第二步，2 次合并，每次成本是 4 次運(yùn)算。
• 第三步，1 次合并，成本是 8 次運(yùn)算。

因?yàn)橛?log(N) 個(gè)步驟，整體成本是 N*log(N) 次運(yùn)算。

【這個(gè)完整的動(dòng)圖演示了拆分和排序的全過(guò)程，不動(dòng)戳大。】

 

合并排序的強(qiáng)大之處

為什么這個(gè)算法如此強(qiáng)大？

因?yàn)椋?/p>

• 你可以更改算法，以便于節(jié)省內(nèi)存空間，方法是不創(chuàng)建新的序列而是直接修改輸入序列。

注：這種算法叫『原地算法』(in-place algorithm)

• 你可以更改算法，以便于同時(shí)使用磁盤空間和少量?jī)?nèi)存而避免巨量磁盤 I/O。方法是只向內(nèi)存中加載當(dāng)前處理的部分。在僅僅100MB的內(nèi)存緩沖區(qū)內(nèi)排序一個(gè)幾個(gè)GB的表時(shí)，這是個(gè)很重要的技巧。

注：這種算法叫『外部排序』(external sorting)。

• 你可以更改算法，以便于在 多處理器/多線程/多服務(wù)器 上運(yùn)行。

比如，分布式合并排序是Hadoop（那個(gè)著名的大數(shù)據(jù)框架）的關(guān)鍵組件之一。

• 這個(gè)算法可以點(diǎn)石成金（事實(shí)如此?。?/li>

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

陣列，樹和哈希表

既然我們已經(jīng)了解了時(shí)間復(fù)雜度和排序背后的理念，我必須要向你介紹3種數(shù)據(jù)結(jié)構(gòu)了。這個(gè)很重要，因?yàn)樗鼈兪乾F(xiàn)代數(shù)據(jù)庫(kù)的支柱。我還會(huì)介紹數(shù)據(jù)庫(kù)索引的概念。

陣列

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

 

這個(gè)二維陣列是帶有行與列的表：

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

雖然用這個(gè)方法保存和視覺(jué)化數(shù)據(jù)很棒，但是當(dāng)你要查找特定的值它就很糟糕了。 舉個(gè)例子，如果你要找到所有在 UK 工作的人，你必須查看每一行以判斷該行是否屬于 UK 。這會(huì)造成 N 次運(yùn)算的成本（N 等于行數(shù)），還不賴嘛，但是有沒(méi)有更快的方法呢？這時(shí)候樹就可以登場(chǎng)了（或開始起作用了）。

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

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

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

【譯者注：binary search tree，二叉查找樹/二叉搜索樹，或稱 Binary Sort Tree 二叉排序樹。見(jiàn)百度百科 】

概念

 

這個(gè)樹有 N=15 個(gè)元素。比方說(shuō)我要找208：

• 我從鍵值為 136 的根開始，因?yàn)?136<208，我去找節(jié)點(diǎn)136的右子樹。
• 398>208，所以我去找節(jié)點(diǎn)398的左子樹
• 250>208，所以我去找節(jié)點(diǎn)250的左子樹
• 200<208，所以我去找節(jié)點(diǎn)200的右子樹。但是 200 沒(méi)有右子樹，值不存在（因?yàn)槿绻嬖?，它?huì)在 200 的右子樹）

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

• 我從鍵值為136的根開始，因?yàn)?136>40，所以我去找節(jié)點(diǎn)136的左子樹。
• 80>40，所以我去找節(jié)點(diǎn) 80 的左子樹
• 40=40，節(jié)點(diǎn)存在。我抽取出節(jié)點(diǎn)內(nèi)部行的ID（圖中沒(méi)有畫）再去表中查找對(duì)應(yīng)的 ROW ID。
• 知道 ROW ID我就知道了數(shù)據(jù)在表中對(duì)精確位置，就可以立即獲取數(shù)據(jù)。

最后，兩次查詢的成本就是樹內(nèi)部的層數(shù)。如果你仔細(xì)閱讀了合并排序的部分，你就應(yīng)該明白一共有 log(N)層。所以這個(gè)查詢的成本是 log(N)，不錯(cuò)啊！

回到我們的問(wèn)題

上文說(shuō)的很抽象，我們回來(lái)看看我們的問(wèn)題。這次不用傻傻的數(shù)字了，想象一下前表中代表某人的國(guó)家的字符串。假設(shè)你有個(gè)樹包含表中的列『country』：

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

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

B+樹索引

查找一個(gè)特定值這個(gè)樹挺好用，但是當(dāng)你需要查找兩個(gè)值之間的多個(gè)元素時(shí)，就會(huì)有大麻煩了。你的成本將是 O(N)，因?yàn)槟惚仨毑檎覙涞拿恳粋€(gè)節(jié)點(diǎn)，以判斷它是否處于那 2 個(gè)值之間（例如，對(duì)樹使用中序遍歷）。而且這個(gè)操作不是磁盤I/O有利的，因?yàn)槟惚仨氉x取整個(gè)樹。我們需要找到高效的范圍查詢方法。為了解決這個(gè)問(wèn)題，現(xiàn)代數(shù)據(jù)庫(kù)使用了一種修訂版的樹，叫做B+樹。在一個(gè)B+樹里：

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

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

 

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

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

• 你只需要找 40（若40不存在則找40之后最貼近的值），就像你在上一個(gè)樹中所做的那樣。
• 然后用那些連接來(lái)收集40的后續(xù)節(jié)點(diǎn)，直到找到100。

比方說(shuō)你找到了 M 個(gè)后續(xù)節(jié)點(diǎn)，樹總共有 N 個(gè)節(jié)點(diǎn)。對(duì)指定節(jié)點(diǎn)的搜索成本是 log(N)，跟上一個(gè)樹相同。但是當(dāng)你找到這個(gè)節(jié)點(diǎn)，你得通過(guò)后續(xù)節(jié)點(diǎn)的連接得到 M 個(gè)后續(xù)節(jié)點(diǎn)，這需要 M 次運(yùn)算。那么這次搜索只消耗了 M+log(N) 次運(yùn)算，區(qū)別于上一個(gè)樹所用的 N 次運(yùn)算。此外，你不需要讀取整個(gè)樹（僅需要讀 M+log(N) 個(gè)節(jié)點(diǎn)）,這意味著更少的磁盤訪問(wèn)。如果 M 很?。ū热?200 行）并且 N 很大（1,000,000），那結(jié)果就是天壤之別了。

然而還有新的問(wèn)題（又來(lái)了?。Ｈ绻阍跀?shù)據(jù)庫(kù)中增加或刪除一行（從而在相關(guān)的 B+樹索引里）：

• 你必須在B+樹中的節(jié)點(diǎn)之間保持順序，否則節(jié)點(diǎn)會(huì)變得一團(tuán)糟，你無(wú)法從中找到想要的節(jié)點(diǎn)。
• 你必須盡可能降低B+樹的層數(shù)，否則 O(log(N)) 復(fù)雜度會(huì)變成 O(N)。

換句話說(shuō)，B+樹需要自我整理和自我平衡。謝天謝地，我們有智能刪除和插入。但是這樣也帶來(lái)了成本：在B+樹中，插入和刪除操作是 O(log(N)) 復(fù)雜度。所以有些人聽(tīng)到過(guò)使用太多索引不是個(gè)好主意這類說(shuō)法。沒(méi)錯(cuò)，你減慢了快速插入/更新/刪除表中的一個(gè)行的操作，因?yàn)閿?shù)據(jù)庫(kù)需要以代價(jià)高昂的每索引 O(log(N)) 運(yùn)算來(lái)更新表的索引。再者，增加索引意味著給事務(wù)管理器帶來(lái)更多的工作負(fù)荷（在本文結(jié)尾我們會(huì)探討這個(gè)管理器）。

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

哈希表

我們最后一個(gè)重要的數(shù)據(jù)結(jié)構(gòu)是哈希表。當(dāng)你想快速查找值時(shí)，哈希表是非常有用的。而且，理解哈希表會(huì)幫助我們接下來(lái)理解一個(gè)數(shù)據(jù)庫(kù)常見(jiàn)的聯(lián)接操作，叫做『哈希聯(lián)接』。這個(gè)數(shù)據(jù)結(jié)構(gòu)也被數(shù)據(jù)庫(kù)用來(lái)保存一些內(nèi)部的東西（比如鎖表或者緩沖池，我們?cè)谙挛臅?huì)研究這兩個(gè)概念）。

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

• 元素的關(guān)鍵字關(guān)鍵字的哈希函數(shù)。關(guān)鍵字計(jì)算出來(lái)的哈希值給出了元素的位置（叫做哈希桶）。關(guān)鍵字比較函數(shù)。一旦你找到正確的哈希桶，你必須用比較函數(shù)在桶內(nèi)找到你要的元素。

一個(gè)簡(jiǎn)單的例子

我們來(lái)看一個(gè)形象化的例子：

 

這個(gè)哈希表有10個(gè)哈希桶。因?yàn)槲覒?，我只給出5個(gè)桶，但是我知道你很聰明，所以我讓你想象其它的5個(gè)桶。我用的哈希函數(shù)是關(guān)鍵字對(duì)10取模，也就是我只保留元素關(guān)鍵字的最后一位，用來(lái)查找它的哈希桶：

• 如果元素最后一位是 0，則進(jìn)入哈希桶0，
• 如果元素最后一位是 1，則進(jìn)入哈希桶1，
• 如果元素最后一位是 2，則進(jìn)入哈希桶2，
• …我用的比較函數(shù)只是判斷兩個(gè)整數(shù)是否相等。

【譯者注：取模運(yùn)算】

比方說(shuō)你要找元素 78：

• 哈希表計(jì)算 78 的哈希碼，等于 8。
• 查找哈希桶 8，找到的第一個(gè)元素是 78。
• 返回元素 78。
• 查詢僅耗費(fèi)了 2 次運(yùn)算（1次計(jì)算哈希值，另一次在哈希桶中查找元素）。

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

• 哈希表計(jì)算 59 的哈希碼，等于9。
• 查找哈希桶 9，第一個(gè)找到的元素是 99。因?yàn)?99 不等于 59， 那么 99 不是正確的元素。
• 用同樣的邏輯，查找第二個(gè)元素(9)，第三個(gè)(79)，……，最后一個(gè)(29)。
• 元素不存在。
• 搜索耗費(fèi)了 7 次運(yùn)算。

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

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

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

在我的例子里，找到一個(gè)好的哈希函數(shù)很容易，但這是個(gè)簡(jiǎn)單的例子。當(dāng)關(guān)鍵字是下列形式時(shí)，好的哈希函數(shù)就更難找了：

• 1 個(gè)字符串（比如一個(gè)人的姓）
• 2 個(gè)字符串（比如一個(gè)人的姓和名）
• 2 個(gè)字符串和一個(gè)日期（比如一個(gè)人的姓、名和出生年月日）
• …

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

陣列 vs 哈希表

為什么不用陣列呢？

嗯，你問(wèn)得好。

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

全局概覽

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

數(shù)據(jù)庫(kù)是一個(gè)易于訪問(wèn)和修改的信息集合。不過(guò)簡(jiǎn)單的一堆文件也能達(dá)到這個(gè)效果。事實(shí)上，像SQLite這樣最簡(jiǎn)單的數(shù)據(jù)庫(kù)也只是一堆文件而已，但SQLite是精心設(shè)計(jì)的一堆文件，因?yàn)樗试S你：

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

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

 

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

核心組件：

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

工具：

• 備份管理器（Backup manager）：用于保存和恢復(fù)數(shù)據(jù)。
• 復(fù)原管理器（Recovery manager）：用于崩潰后重啟數(shù)據(jù)庫(kù)到一個(gè)一致?tīng)顟B(tài)。
• 監(jiān)控管理器（Monitor manager）：用于記錄數(shù)據(jù)庫(kù)活動(dòng)信息和提供監(jiān)控?cái)?shù)據(jù)庫(kù)的工具。
• Administration管理器（Administration manager）：用于保存元數(shù)據(jù)（比如表的名稱和結(jié)構(gòu)），提供管理數(shù)據(jù)庫(kù)、模式、表空間的工具?！咀g者注：好吧，我真的不知道Administration manager該翻譯成什么，有知道的麻煩告知，不勝感激……】
• ……

查詢管理器：

• 查詢解析器（Query parser）：用于檢查查詢是否合法
• 查詢重寫器（Query rewriter）：用于預(yù)優(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ù)訪問(wèn)管理器（Data access manager）：訪問(wèn)磁盤中的數(shù)據(jù)

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

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

客戶端管理器

 

客戶端管理器是處理客戶端通信的?？蛻舳丝梢允且粋€(gè)（網(wǎng)站）服務(wù)器或者一個(gè)最終用戶或最終應(yīng)用?？蛻舳斯芾砥魍ㄟ^(guò)一系列知名的API（JDBC, ODBC, OLE-DB …）提供不同的方式來(lái)訪問(wèn)數(shù)據(jù)庫(kù)。

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

當(dāng)你連接到數(shù)據(jù)庫(kù)時(shí)：

• 管理器首先檢查你的驗(yàn)證信息（用戶名和密碼），然后檢查你是否有訪問(wèn)數(shù)據(jù)庫(kù)的授權(quán)。這些權(quán)限由DBA分配。
• 然后，管理器檢查是否有空閑進(jìn)程（或線程）來(lái)處理你對(duì)查詢。
• 管理器還會(huì)檢查數(shù)據(jù)庫(kù)是否負(fù)載很重。
• 管理器可能會(huì)等待一會(huì)兒來(lái)獲取需要的資源。如果等待時(shí)間達(dá)到超時(shí)時(shí)間，它會(huì)關(guān)閉連接并給出一個(gè)可讀的錯(cuò)誤信息。
• 然后管理器會(huì)把你的查詢送給查詢管理器來(lái)處理。
• 因?yàn)椴樵兲幚磉M(jìn)程不是『不全則無(wú)』的，一旦它從查詢管理器得到數(shù)據(jù)，它會(huì)把部分結(jié)果保存到一個(gè)緩沖區(qū)并且開始給你發(fā)送。
• 如果遇到問(wèn)題，管理器關(guān)閉連接，向你發(fā)送可讀的解釋信息，然后釋放資源。

查詢管理器

 

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

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

這里我不會(huì)過(guò)多探討最后兩步，因?yàn)樗鼈儾惶匾?/p>

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

• 關(guān)于成本優(yōu)化的初步研究論文(1979)：關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)存取路徑選擇。這個(gè)篇文章只有12頁(yè)，而且具備計(jì)算機(jī)一般水平就能理解。
• 非常好、非常深入的 DB2 9.X 如何優(yōu)化查詢的介紹
• 非常好的PostgreSQL如何優(yōu)化查詢的介紹。這是一篇最通俗易懂的文檔，因?yàn)樗v的是『我們來(lái)看看在這種情況下，PostgreSQL給出了什么樣的查詢計(jì)劃』，而不是『我們來(lái)看看PostgreSQL用的什么算法』。
• 官方SQLite優(yōu)化文檔?！阂子凇婚喿x，因?yàn)镾QLite用的是簡(jiǎn)單規(guī)則。再者，這是唯一真正解釋SQLite如何工作的官方文檔。
• 非常好的SQL Server 2005 如何優(yōu)化查詢的介紹
• Oracle 12c 優(yōu)化白皮書
• 2篇查詢優(yōu)化的教程，第一篇 第二篇。教程來(lái)自《數(shù)據(jù)庫(kù)系統(tǒng)概念》的作者，很好的讀物，集中討論磁盤I/O，但是要求具有很好的計(jì)算機(jī)科學(xué)水平。
• 另一個(gè)原理教程，這篇教程我覺(jué)得更易懂，不過(guò)它僅關(guān)注聯(lián)接運(yùn)算符（join operators）和磁盤I/O。

查詢解析器

每一條SQL語(yǔ)句都要送到解析器來(lái)檢查語(yǔ)法，如果你的查詢有錯(cuò)，解析器將拒絕該查詢。比如，如果你寫成”SLECT …” 而不是 “SELECT …”，那就沒(méi)有下文了。

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

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

• 表是否存在
• 表的字段是否存在
• 對(duì)某類型字段的 運(yùn)算 是否 可能（比如，你不能將整數(shù)和字符串進(jìn)行比較，你不能對(duì)一個(gè)整數(shù)使用 substring() 函數(shù)）

接著，解析器檢查在查詢中你是否有權(quán)限來(lái)讀取（或?qū)懭耄┍怼Ｔ購(gòu)?qiáng)調(diào)一次：這些權(quán)限由DBA分配。

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

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

查詢重寫器

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

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

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

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

例如：

MySQL

 

會(huì)轉(zhuǎn)換為：

MySQL

 

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

【物化視圖 ，謂詞，predicate，條件表達(dá)式的求值返回真或假的過(guò)程】

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

統(tǒng)計(jì)

研究數(shù)據(jù)庫(kù)如何優(yōu)化查詢之前我們需要談?wù)劷y(tǒng)計(jì)，因?yàn)闆](méi)有統(tǒng)計(jì)的數(shù)據(jù)庫(kù)是愚蠢的。除非你明確指示，數(shù)據(jù)庫(kù)是不會(huì)分析自己的數(shù)據(jù)的。沒(méi)有分析會(huì)導(dǎo)致數(shù)據(jù)庫(kù)做出（非常）糟糕的假設(shè)。

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

我必須（簡(jiǎn)要地）談?wù)剶?shù)據(jù)庫(kù)和操作系統(tǒng)如何保存數(shù)據(jù)。兩者使用的最小單位叫做頁(yè)或塊（默認(rèn) 4 或 8 KB）。這就是說(shuō)如果你僅需要 1KB，也會(huì)占用一個(gè)頁(yè)。要是頁(yè)的大小為 8KB，你就浪費(fèi)了 7KB。

回來(lái)繼續(xù)講統(tǒng)計(jì)！ 當(dāng)你要求數(shù)據(jù)庫(kù)收集統(tǒng)計(jì)信息，數(shù)據(jù)庫(kù)會(huì)計(jì)算下列值：

• 表中行和頁(yè)的數(shù)量
• 表中每個(gè)列中的：
  唯一值
  數(shù)據(jù)長(zhǎng)度（最小，最大，平均）
  數(shù)據(jù)范圍（最小，最大，平均）

• 表的索引信息

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

對(duì)每個(gè)列的統(tǒng)計(jì)非常重要。比如，如果一個(gè)表 PERSON 需要聯(lián)接 2 個(gè)列： LAST_NAME, FIRST_NAME。根據(jù)統(tǒng)計(jì)信息，數(shù)據(jù)庫(kù)知道FIRST_NAME只有 1,000 個(gè)不同的值，LAST_NAME 有 1,000,000 個(gè)不同的值。因此，數(shù)據(jù)庫(kù)就會(huì)按照 LAST_NAME, FIRST_NAME 聯(lián)接。因?yàn)?LAST_NAME 不大可能重復(fù)，多數(shù)情況下比較 LAST_NAME 的頭 2 、 3 個(gè)字符就夠了，這將大大減少比較的次數(shù)。

不過(guò)，這些只是基本的統(tǒng)計(jì)。你可以讓數(shù)據(jù)庫(kù)做一種高級(jí)統(tǒng)計(jì)，叫直方圖。直方圖是列值分布情況的統(tǒng)計(jì)信息。例如：

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

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

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

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

統(tǒng)計(jì)信息必須及時(shí)更新。如果一個(gè)表有 1,000,000 行而數(shù)據(jù)庫(kù)認(rèn)為它只有 500 行，沒(méi)有比這更糟糕的了。統(tǒng)計(jì)唯一的不利之處是需要時(shí)間來(lái)計(jì)算，這就是為什么數(shù)據(jù)庫(kù)大多默認(rèn)情況下不會(huì)自動(dòng)計(jì)算統(tǒng)計(jì)信息。數(shù)據(jù)達(dá)到百萬(wàn)級(jí)時(shí)統(tǒng)計(jì)會(huì)變得困難，這時(shí)候，你可以選擇僅做基本統(tǒng)計(jì)或者在一個(gè)數(shù)據(jù)庫(kù)樣本上執(zhí)行統(tǒng)計(jì)。

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

注：當(dāng)然了，每個(gè)數(shù)據(jù)庫(kù)還有其特定的更高級(jí)的統(tǒng)計(jì)。如果你想了解更多信息，讀讀數(shù)據(jù)庫(kù)的文檔。話雖然這么說(shuō)，我已經(jīng)盡力理解統(tǒng)計(jì)是如何使用的了，而且我找到的最好的官方文檔來(lái)自PostgreSQL。

查詢優(yōu)化器

 

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

為了理解成本優(yōu)化器的原理，我覺(jué)得最好用個(gè)例子來(lái)『感受』一下這個(gè)任務(wù)背后的復(fù)雜性。這里我將給出聯(lián)接 2 個(gè)表的 3 個(gè)方法，我們很快就能看到即便一個(gè)簡(jiǎn)單的聯(lián)接查詢對(duì)于優(yōu)化器來(lái)說(shuō)都是個(gè)噩夢(mèng)。之后，我們會(huì)了解真正的優(yōu)化器是怎么做的。

對(duì)于這些聯(lián)接操作，我會(huì)專注于它們的時(shí)間復(fù)雜度，但是，數(shù)據(jù)庫(kù)優(yōu)化器計(jì)算的是它們的 CPU 成本、磁盤 I/O 成本、和內(nèi)存需求。時(shí)間復(fù)雜度和 CPU 成本的區(qū)別是，時(shí)間成本是個(gè)近似值（給我這樣的懶家伙準(zhǔn)備的）。而 CPU 成本，我這里包括了所有的運(yùn)算，比如：加法、條件判斷、乘法、迭代……還有呢：

• 每一個(gè)高級(jí)代碼運(yùn)算都要特定數(shù)量的低級(jí) CPU 運(yùn)算。
• 對(duì)于 Intel Core i7、Intel Pentium 4、AMD Opteron…等，（就 CPU 周期而言）CPU 的運(yùn)算成本是不同的，也就是說(shuō)它取決于 CPU 的架構(gòu)。

使用時(shí)間復(fù)雜度就容易多了（至少對(duì)我來(lái)說(shuō)），用它我也能了解到 CBO 的概念。由于磁盤 I/O 是個(gè)重要的概念，我偶爾也會(huì)提到它。請(qǐng)牢記，大多數(shù)時(shí)候瓶頸在于磁盤 I/O 而不是 CPU 使用。

索引

在研究 B+樹的時(shí)候我們談到了索引，要記住一點(diǎn)，索引都是已經(jīng)排了序的。

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

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

存取路徑

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

注：由于所有存取路徑的真正問(wèn)題是磁盤 I/O，我不會(huì)過(guò)多探討時(shí)間復(fù)雜度。

【四種類型的Oracle索引掃描介紹 】

全掃描

如果你讀過(guò)執(zhí)行計(jì)劃，一定看到過(guò)『全掃描』（或只是『掃描』）一詞。簡(jiǎn)單的說(shuō)全掃描就是數(shù)據(jù)庫(kù)完整的讀一個(gè)表或索引。就磁盤 I/O 而言，很明顯全表掃描的成本比索引全掃描要高昂。

范圍掃描

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

當(dāng)然，你需要在 AGE 字段上有索引才能用到索引范圍掃描。

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

唯一掃描

如果你只需要從索引中取一個(gè)值你可以用唯一掃描。

根據(jù) ROW ID 存取

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

例如，假如你運(yùn)行：

MySQL

 

如果 person 表的 age 列有索引，優(yōu)化器會(huì)使用索引找到所有年齡為 28 的人，然后它會(huì)去表中讀取相關(guān)的行，這是因?yàn)樗饕兄挥?age 的信息而你要的是姓和名。

但是，假如你換個(gè)做法：

MySQL

 

PERSON 表的索引會(huì)用來(lái)聯(lián)接 TYPE_PERSON 表，但是 PERSON 表不會(huì)根據(jù)行ID 存取，因?yàn)槟悴](méi)有要求這個(gè)表內(nèi)的信息。

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

其它路徑

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

聯(lián)接運(yùn)算符

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

我要展現(xiàn)的是3個(gè)個(gè)常用聯(lián)接運(yù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)系” 這個(gè)說(shuō)法來(lái)源不明，跟查詢的“內(nèi)聯(lián)接（INNER JOIN） 、外聯(lián)接（OUTER JOIN） ” 不是一個(gè)概念 。只查到百度百科詞條：關(guān)系數(shù)據(jù)庫(kù) 里提到“每個(gè)表格（有時(shí)被稱為一個(gè)關(guān)系）……” 。 其他參考鏈接 “Merge Join” “Hash Join” “Nested Loop Join”】 。 一個(gè)關(guān)系可以是：

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

當(dāng)你聯(lián)接兩個(gè)關(guān)系時(shí)，聯(lián)接算法對(duì)兩個(gè)關(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 個(gè)元素，內(nèi)關(guān)系有 M 個(gè)元素。要記住，真實(shí)的優(yōu)化器通過(guò)統(tǒng)計(jì)知道 N 和 M 的值。

注：N 和 M 是關(guān)系的基數(shù)。

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

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

 

道理如下：

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

下面是偽代碼：

C

 

由于這是個(gè)雙迭代，時(shí)間復(fù)雜度是 O(N*M)。

在磁盤 I/O 方面， 針對(duì) N 行外關(guān)系的每一行，內(nèi)部循環(huán)需要從內(nèi)關(guān)系讀取 M 行。這個(gè)算法需要從磁盤讀取 N+ N*M 行。但是，如果內(nèi)關(guān)系足夠小，你可以把它讀入內(nèi)存，那么就只剩下 M + N 次讀取。這樣修改之后，內(nèi)關(guān)系必須是最小的，因?yàn)樗懈髾C(jī)會(huì)裝入內(nèi)存。

在CPU成本方面沒(méi)有什么區(qū)別，但是在磁盤 I/O 方面，最好最好的，是每個(gè)關(guān)系只讀取一次。

當(dāng)然，內(nèi)關(guān)系可以由索引代替，對(duì)磁盤 I/O 更有利。

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

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

可能的算法如下：

C

 

使用這個(gè)版本，時(shí)間復(fù)雜度沒(méi)有變化，但是磁盤訪問(wèn)降低了：

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

哈希聯(lián)接

哈希聯(lián)接更復(fù)雜，不過(guò)在很多場(chǎng)合比嵌套循環(huán)聯(lián)接成本低。

 

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

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

在時(shí)間復(fù)雜度方面我需要做些假設(shè)來(lái)簡(jiǎn)化問(wèn)題：

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

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

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

• 1) 計(jì)算內(nèi)關(guān)系和外關(guān)系雙方的哈希表
• 2) 保存哈希表到磁盤
• 3) 然后逐個(gè)哈希桶比較（其中一個(gè)讀入內(nèi)存，另一個(gè)逐行讀取）。

合并聯(lián)接

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

注：這個(gè)簡(jiǎn)化的合并聯(lián)接不區(qū)分內(nèi)表或外表；兩個(gè)表扮演同樣的角色。但是真實(shí)的實(shí)現(xiàn)方式是不同的，比如當(dāng)處理重復(fù)值時(shí)。

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

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

排序

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

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

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

合并聯(lián)接

 

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

• 1) 在兩個(gè)關(guān)系中，比較當(dāng)前元素（當(dāng)前=頭一次出現(xiàn)的第一個(gè)）
• 2) 如果相同，就把兩個(gè)元素都放入結(jié)果，再比較兩個(gè)關(guān)系里的下一個(gè)元素
• 3) 如果不同，就去帶有最小元素的關(guān)系里找下一個(gè)元素（因?yàn)橄乱粋€(gè)元素可能會(huì)匹配）
• 4) 重復(fù) 1、2、3步驟直到其中一個(gè)關(guān)系的最后一個(gè)元素。

因?yàn)閮蓚€(gè)關(guān)系都是已排序的，你不需要『回頭去找』，所以這個(gè)方法是有效的。

該算法是個(gè)簡(jiǎn)化版，因?yàn)樗鼪](méi)有處理兩個(gè)序列中相同數(shù)據(jù)出現(xiàn)多次的情況（即多重匹配）。真實(shí)版本『僅僅』針對(duì)本例就更加復(fù)雜，所以我才選擇簡(jiǎn)化版。

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

如果兩個(gè)關(guān)系需要排序，時(shí)間復(fù)雜度是對(duì)兩個(gè)關(guān)系排序的成本：O(N*Log(N) + M*Log(M))

對(duì)于計(jì)算機(jī)極客，我給出下面這個(gè)可能的算法來(lái)處理多重匹配（注：對(duì)于這個(gè)算法我不保證100%正確）：

C

 

哪個(gè)算法最好？

如果有最好的，就沒(méi)必要弄那么多種類型了。這個(gè)問(wèn)題很難，因?yàn)楹芏嘁蛩囟家紤]，比如：

• 空閑內(nèi)存：沒(méi)有足夠的內(nèi)存的話就跟強(qiáng)大的哈希聯(lián)接拜拜吧（至少是完全內(nèi)存中哈希聯(lián)接）。
• 兩個(gè)數(shù)據(jù)集的大小。比如，如果一個(gè)大表聯(lián)接一個(gè)很小的表，那么嵌套循環(huán)聯(lián)接就比哈希聯(lián)接快，因?yàn)楹笳哂袆?chuàng)建哈希的高昂成本；如果兩個(gè)表都非常大，那么嵌套循環(huán)聯(lián)接CPU成本就很高昂。
• 是否有索引：有兩個(gè) B+樹索引的話，聰明的選擇似乎是合并聯(lián)接。
• 結(jié)果是否需要排序：即使你用到的是未排序的數(shù)據(jù)集，你也可能想用成本較高的合并聯(lián)接（帶排序的），因?yàn)樽罱K得到排序的結(jié)果后，你可以把它和另一個(gè)合并聯(lián)接串起來(lái)（或者也許因?yàn)椴樵冇?ORDER BY/GROUP BY/DISTINCT 等操作符隱式或顯式地要求一個(gè)排序結(jié)果）。
• 關(guān)系是否已經(jīng)排序：這時(shí)候合并聯(lián)接是最好的候選項(xiàng)。
• 聯(lián)接的類型：是等值聯(lián)接（比如 tableA.col1 = tableB.col2 ）？ 還是內(nèi)聯(lián)接？外聯(lián)接？笛卡爾乘積？或者自聯(lián)接？有些聯(lián)接在特定環(huán)境下是無(wú)法工作的。
• 數(shù)據(jù)的分布：如果聯(lián)接條件的數(shù)據(jù)是傾斜的（比如根據(jù)姓氏來(lái)聯(lián)接人，但是很多人同姓），用哈希聯(lián)接將是個(gè)災(zāi)難，原因是哈希函數(shù)將產(chǎn)生分布極不均勻的哈希桶。
• 如果你希望聯(lián)接操作使用多線程或多進(jìn)程。

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

簡(jiǎn)化的例子

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

現(xiàn)在，比如說(shuō)我們要聯(lián)接 5 個(gè)表，來(lái)獲得一個(gè)人的全部信息。一個(gè)人可以有：

• 多個(gè)手機(jī)號(hào)（MOBILES）
• 多個(gè)郵箱（MAILS）
• 多個(gè)地址（ADRESSES）
• 多個(gè)銀行賬號(hào)（BANK_ACCOUNTS）

換句話說(shuō)，我們需要用下面的查詢快速得到答案：

MySQL

 

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

• 每個(gè)聯(lián)接使用那種類型？
  我有 3 種可選（哈希、合并、嵌套），同時(shí)可能用到 0, 1 或 2 個(gè)索引（不必說(shuō)還有多種類型的索引）。

• 按什么順序執(zhí)行聯(lián)接？
  比如，下圖顯示了針對(duì) 4 個(gè)表僅僅 3 次聯(lián)接，可能采用的執(zhí)行計(jì)劃：

 

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

• 1) 采取粗暴的方式
  用數(shù)據(jù)庫(kù)統(tǒng)計(jì)，計(jì)算每種可能的執(zhí)行計(jì)劃的成本，保留最佳方案。但是，會(huì)有很多可能性。對(duì)于一個(gè)給定順序的聯(lián)接操作，每個(gè)聯(lián)接有三種可能性：哈希、合并、嵌套，那么總共就有 3^4 種可能性。確定聯(lián)接的順序是個(gè)二叉樹的排列問(wèn)題，會(huì)有 (2*4)!/(4+1)! 種可能的順序。對(duì)本例這個(gè)相當(dāng)簡(jiǎn)化了的問(wèn)題，我最后會(huì)得到 3^4*(2*4)!/(4+1)! 種可能。
  拋開專業(yè)術(shù)語(yǔ)，那相當(dāng)于 27,216 種可能性。如果給合并聯(lián)接加上使用 0,1 或 2 個(gè) B+樹索引，可能性就變成了 210,000種。我是不是告訴過(guò)你這個(gè)查詢其實(shí)非常簡(jiǎn)單嗎？

• 2) 我大叫一聲辭了這份工作
  很有誘惑力，但是這樣一來(lái)，你不會(huì)的到查詢結(jié)果，而我需要錢來(lái)付賬單。

• 3) 我只嘗試幾種執(zhí)行計(jì)劃，挑一個(gè)成本最低的。
  由于不是超人，我不能算出所有計(jì)劃的成本。相反，我可以武斷地從全部可能的計(jì)劃中選擇一個(gè)子集，計(jì)算它們的成本，把最佳的計(jì)劃給你。

• 4) 我用聰明的規(guī)則來(lái)降低可能性的數(shù)量
  有兩種規(guī)則：
  我可以用『邏輯』規(guī)則，它能去除無(wú)用的可能性，但是無(wú)法過(guò)濾大量的可能性。比如： 『嵌套聯(lián)接的內(nèi)關(guān)系必須是最小的數(shù)據(jù)集』。
  我接受現(xiàn)實(shí)，不去找最佳方案，用更激進(jìn)的規(guī)則來(lái)大大降低可能性的數(shù)量。比如：『如果一個(gè)關(guān)系很小，使用嵌套循環(huán)聯(lián)接，絕不使用合并或哈希聯(lián)接?！?/li>

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

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

動(dòng)態(tài)編程，貪婪算法和啟發(fā)式算法

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

多數(shù)時(shí)候，優(yōu)化器找到的不是最佳的方案，而是一個(gè)『不錯(cuò)』的

對(duì)于小規(guī)模的查詢，采取粗暴的方式是有可能的。但是為了讓中等規(guī)模的查詢也能采取粗暴的方式，我們有辦法避免不必要的計(jì)算，這就是動(dòng)態(tài)編程。

動(dòng)態(tài)編程

這幾個(gè)字背后的理念是，很多執(zhí)行計(jì)劃是非常相似的?？纯聪聢D這幾種計(jì)劃：

 

它們都有相同的子樹（A JOIN B），所以，不必在每個(gè)計(jì)劃中計(jì)算這個(gè)子樹的成本，計(jì)算一次，保存結(jié)果，當(dāng)再遇到這個(gè)子樹時(shí)重用。用更正規(guī)的說(shuō)法，我們面對(duì)的是個(gè)重疊問(wèn)題。為了避免對(duì)部分結(jié)果的重復(fù)計(jì)算，我們使用記憶法。

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

C

 

針對(duì)大規(guī)模查詢，你也可以用動(dòng)態(tài)編程方法，但是要附加額外的規(guī)則（或者稱為啟發(fā)式算法）來(lái)減少可能性。

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

 

• 如果我們加上邏輯規(guī)則來(lái)避免一些模式的計(jì)劃（像『如果一個(gè)表有針對(duì)指定謂詞的索引，就不要對(duì)表嘗試合并聯(lián)接，要對(duì)索引』），就會(huì)在不給最佳方案造成過(guò)多傷害的前提下，減少可能性的數(shù)量。
• 如果我們?cè)诹鞒汤镌黾右?guī)則（像『聯(lián)接運(yùn)算先于其他所有的關(guān)系運(yùn)算』），也能減少大量的可能性。
• ……

貪婪算法

但是，優(yōu)化器面對(duì)一個(gè)非常大的查詢，或者為了盡快找到答案（然而查詢速度就快不起來(lái)了），會(huì)應(yīng)用另一種算法，叫貪婪算法。

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

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

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

因?yàn)槲覀兪俏鋽嗟貜谋?A 開始，我們可以把同樣的算法用在 B，然后 C，然后 D, 然后 E。最后保留成本最低的執(zhí)行計(jì)劃。

順便說(shuō)一句，這個(gè)算法有個(gè)名字，叫『最近鄰居算法』。

拋開細(xì)節(jié)不談，只需一個(gè)良好的模型和一個(gè) N*log(N) 復(fù)雜度的排序，問(wèn)題就輕松解決了。這個(gè)算法的復(fù)雜度是 O(N*log(N)) ，對(duì)比一下完全動(dòng)態(tài)編程的 O(3^N)。如果你有個(gè)20個(gè)聯(lián)接的大型查詢，這意味著 26 vs 3,486,784,401 ，天壤之別！

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

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

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

其他算法

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

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

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

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

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

• 一個(gè)方法代表一種可能的完整查詢計(jì)劃
• 每一步保留了 P 個(gè)方法（即計(jì)劃），而不是一個(gè)。
• 0) P 個(gè)計(jì)劃隨機(jī)創(chuàng)建
• 1) 成本最低的計(jì)劃才會(huì)保留
• 2) 這些最佳計(jì)劃混合在一起產(chǎn)生 P 個(gè)新的計(jì)劃
• 3) 一些新的計(jì)劃被隨機(jī)改寫
• 4) 1，2，3步重復(fù) T 次
• 5) 然后在最后一次循環(huán)，從 P 個(gè)計(jì)劃里得到最佳計(jì)劃。

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

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

PostgreSQL 實(shí)現(xiàn)了基因算法，但我并沒(méi)有發(fā)現(xiàn)它是不是默認(rèn)使用這種算法的。

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

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

真實(shí)的優(yōu)化器

[ 這段不重要，可以跳過(guò) ]

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

我們來(lái)看看 SQLite 優(yōu)化器 是怎么工作的。這是個(gè)輕量化數(shù)據(jù)庫(kù)，它使用一種簡(jiǎn)單優(yōu)化器，基于帶有附加規(guī)則的貪婪算法，來(lái)限制可能性的數(shù)量。

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

我們?cè)倏纯戳硪粋€(gè)優(yōu)化器是怎么工作的。IBM DB2 跟所有企業(yè)級(jí)數(shù)據(jù)庫(kù)都類似，我討論它是因?yàn)樵谇袚Q到大數(shù)據(jù)之前，它是我最后真正使用的數(shù)據(jù)庫(kù)。

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

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

可以看到 DB2 使用貪婪算法和動(dòng)態(tài)編程算法。當(dāng)然，他們不會(huì)把自己的啟發(fā)算法分享出來(lái)的，因?yàn)椴樵儍?yōu)化器是數(shù)據(jù)庫(kù)的看家本領(lǐng)。

DB2 的默認(rèn)級(jí)別是 5，優(yōu)化器使用下列特性： 【以下出現(xiàn)的一些概念我沒(méi)有做考證，因?yàn)閇 這段不重要，可以跳過(guò) ]】

• 使用所有可用的統(tǒng)計(jì)，包括線段樹（frequent-value）和分位數(shù)統(tǒng)計(jì)（quantile statistics）。
• 使用所有查詢重寫規(guī)則（含物化查詢表路由，materialized query table routing），除了在極少情況下適用的計(jì)算密集型規(guī)則。
• 使用動(dòng)態(tài)編程模擬聯(lián)接
• 有限使用組合內(nèi)關(guān)系（composite inner relation）
• 對(duì)于涉及查找表的星型模式，有限使用笛卡爾乘積
• 考慮寬泛的訪問(wèn)方式，含列表預(yù)?。╨ist prefetch，注：我們將討論什么是列表預(yù)取），index ANDing（注：一種對(duì)索引的特殊操作），和物化查詢表路由。

默認(rèn)的，DB2 對(duì)聯(lián)接排列使用受啟發(fā)式限制的動(dòng)態(tài)編程算法。

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

查詢計(jì)劃緩存

由于創(chuàng)建查詢計(jì)劃是耗時(shí)的，大多數(shù)據(jù)庫(kù)把計(jì)劃保存在查詢計(jì)劃緩存，來(lái)避免重復(fù)計(jì)算。這個(gè)話題比較大，因?yàn)閿?shù)據(jù)庫(kù)需要知道什么時(shí)候更新過(guò)時(shí)的計(jì)劃。辦法是設(shè)置一個(gè)上限，如果一個(gè)表的統(tǒng)計(jì)變化超過(guò)了上限，關(guān)于該表的查詢計(jì)劃就從緩存中清除。

查詢執(zhí)行器

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

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

 

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

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

在這一部分，我沒(méi)看看關(guān)系型數(shù)據(jù)庫(kù)是如何處理這兩個(gè)問(wèn)題的。我不會(huì)講數(shù)據(jù)管理器是怎么獲得數(shù)據(jù)的，因?yàn)檫@不是最重要的（而且本文已經(jīng)夠長(zhǎng)的了！）。

緩存管理器

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

 

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

• 順序訪問(wèn)（比如：全掃描） vs 隨機(jī)訪問(wèn)（比如：按照row id訪問(wèn)）
• 讀還是寫

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

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

要我說(shuō)，內(nèi)存比磁盤要快100到10萬(wàn)倍。

然而，這導(dǎo)致了另一個(gè)問(wèn)題（數(shù)據(jù)庫(kù)總是這樣…)，緩存管理器需要在查詢執(zhí)行器使用數(shù)據(jù)之前得到數(shù)據(jù)，否則查詢管理器不得不等待數(shù)據(jù)從緩慢的磁盤中讀出來(lái)。

預(yù)讀

這個(gè)問(wèn)題叫預(yù)讀。查詢執(zhí)行器知道它將需要什么數(shù)據(jù)，因?yàn)樗私庹麄€(gè)查詢流，而且通過(guò)統(tǒng)計(jì)也了解磁盤上的數(shù)據(jù)。道理是這樣的：

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

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

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

為了監(jiān)控預(yù)讀的工作狀況，現(xiàn)代數(shù)據(jù)庫(kù)引入了一個(gè)度量叫緩沖/緩存命中率，用來(lái)顯示請(qǐng)求的數(shù)據(jù)在緩存中找到而不是從磁盤讀取的頻率。

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

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

緩沖區(qū)置換策略

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

LRU

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

圖解：

 

為了更好的理解，我假設(shè)緩沖區(qū)里的數(shù)據(jù)沒(méi)有被閂鎖鎖?。ň褪钦f(shuō)是可以被移除的）。在這個(gè)簡(jiǎn)單的例子里，緩沖區(qū)可以保存 3 個(gè)元素：

• 1：緩存管理器（簡(jiǎn)稱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被清除，因?yàn)樗亲詈笠粋€(gè)最近使用的，數(shù)據(jù)9加入到緩沖區(qū)
• 5：CM使用數(shù)據(jù)4，數(shù)據(jù)4已經(jīng)在緩沖區(qū)了，所以它再次成為第一個(gè)最近使用的。
• 6：CM使用數(shù)據(jù)1，緩沖區(qū)滿了，所以數(shù)據(jù)9被清除，因?yàn)樗亲詈笠粋€(gè)最近使用的，數(shù)據(jù)1加入到緩沖區(qū)
• ……

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

改進(jìn)

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

『對(duì)非常大的表來(lái)說(shuō)，數(shù)據(jù)庫(kù)通常使用直接路徑來(lái)讀取，即直接加載區(qū)塊[……]，來(lái)避免填滿緩沖區(qū)。對(duì)于中等大小的表，數(shù)據(jù)庫(kù)可以使用直接讀取或緩存讀取。如果選擇緩存讀取，數(shù)據(jù)庫(kù)把區(qū)塊置于LRU的尾部，防止清空當(dāng)前緩沖區(qū)?！?/p>

還有一些可能，比如使用高級(jí)版本的LRU，叫做 LRU-K。例如，SQL Server 使用 LRU-2。

這個(gè)算法的原理是把更多的歷史記錄考慮進(jìn)來(lái)。簡(jiǎn)單LRU（也就是 LRU-1），只考慮最后一次使用的數(shù)據(jù)。LRU-K呢：

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

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

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

其他算法

當(dāng)然還有其他管理緩存的算法，比如：

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

寫緩沖區(qū)

我只探討了讀緩存 —— 在使用之前預(yù)先加載數(shù)據(jù)。用來(lái)保存數(shù)據(jù)、成批刷入磁盤，而不是逐條寫入數(shù)據(jù)從而造成很多單次磁盤訪問(wèn)。

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

事務(wù)管理器

最后但同樣重要的，是事務(wù)管理器，我們將看到這個(gè)進(jìn)程是如何保證每個(gè)查詢?cè)谧约旱氖聞?wù)內(nèi)執(zhí)行的。但開始之前，我們需要理解ACID事務(wù)的概念。

“I’m on acid”

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

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

 

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

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

我們回來(lái)看看ACID屬性：

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

[以下部分不重要，可以跳過(guò)]

現(xiàn)代數(shù)據(jù)庫(kù)不會(huì)使用純粹的隔離作為默認(rèn)模式，因?yàn)樗鼤?huì)帶來(lái)巨大的性能消耗。SQL一般定義4個(gè)隔離級(jí)別：

• 串行化(Serializable，SQLite默認(rèn)模式）：最高級(jí)別的隔離。兩個(gè)同時(shí)發(fā)生的事務(wù)100%隔離，每個(gè)事務(wù)有自己的『世界』。
• 可重復(fù)讀（Repeatable read，MySQL默認(rèn)模式）：每個(gè)事務(wù)有自己的『世界』，除了一種情況。如果一個(gè)事務(wù)成功執(zhí)行并且添加了新數(shù)據(jù)，這些數(shù)據(jù)對(duì)其他正在執(zhí)行的事務(wù)是可見(jiàn)的。但是如果事務(wù)成功修改了一條數(shù)據(jù)，修改結(jié)果對(duì)正在運(yùn)行的事務(wù)不可見(jiàn)。所以，事務(wù)之間只是在新數(shù)據(jù)方面突破了隔離，對(duì)已存在的數(shù)據(jù)仍舊隔離。
  舉個(gè)例子，如果事務(wù)A運(yùn)行”SELECT count(1) from TABLE_X” ，然后事務(wù)B在 TABLE_X 加入一條新數(shù)據(jù)并提交，當(dāng)事務(wù)A再運(yùn)行一次 count(1)結(jié)果不會(huì)是一樣的。
  這叫幻讀（phantom read）。
• 讀取已提交（Read committed，Oracle、PostgreSQL、SQL Server默認(rèn)模式）：可重復(fù)讀+新的隔離突破。如果事務(wù)A讀取了數(shù)據(jù)D，然后數(shù)據(jù)D被事務(wù)B修改（或刪除）并提交，事務(wù)A再次讀取數(shù)據(jù)D時(shí)數(shù)據(jù)的變化（或刪除）是可見(jiàn)的。
  這叫不可重復(fù)讀（non-repeatable read）。
• 讀取未提交（Read uncommitted）：最低級(jí)別的隔離，是讀取已提交+新的隔離突破。如果事務(wù)A讀取了數(shù)據(jù)D，然后數(shù)據(jù)D被事務(wù)B修改（但并未提交，事務(wù)B仍在運(yùn)行中），事務(wù)A再次讀取數(shù)據(jù)D時(shí)，數(shù)據(jù)修改是可見(jiàn)的。如果事務(wù)B回滾，那么事務(wù)A第二次讀取的數(shù)據(jù)D是無(wú)意義的，因?yàn)槟鞘鞘聞?wù)B所做的從未發(fā)生的修改（已經(jīng)回滾了嘛）。
  這叫臟讀（dirty read）。

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

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

并發(fā)控制

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

• 如果所有事務(wù)只是讀取數(shù)據(jù)，它們可以同時(shí)工作，不會(huì)更改另一個(gè)事務(wù)的行為。
• 如果（至少）有一個(gè)事務(wù)在修改其他事務(wù)讀取的數(shù)據(jù)，數(shù)據(jù)庫(kù)需要找個(gè)辦法對(duì)其它事務(wù)隱藏這種修改。而且，它還需要確保這個(gè)修改操作不會(huì)被另一個(gè)看不到這些數(shù)據(jù)修改的事務(wù)擦除。

這個(gè)問(wèn)題叫并發(fā)控制。

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

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

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

用更正規(guī)的說(shuō)法，這是對(duì)沖突的調(diào)度問(wèn)題。更具體點(diǎn)兒說(shuō)，這是個(gè)非常困難而且CPU開銷很大的優(yōu)化問(wèn)題。企業(yè)級(jí)數(shù)據(jù)庫(kù)無(wú)法承擔(dān)等待幾個(gè)小時(shí)，來(lái)尋找每個(gè)新事務(wù)活動(dòng)最好的調(diào)度，因此就使用不那么理想的方式以避免更多的時(shí)間浪費(fèi)在解決沖突上。

鎖管理器

為了解決這個(gè)問(wèn)題，多數(shù)數(shù)據(jù)庫(kù)使用鎖和/或數(shù)據(jù)版本控制。這是個(gè)很大的話題，我會(huì)集中探討鎖，和一點(diǎn)點(diǎn)數(shù)據(jù)版本控制。

悲觀鎖

原理是：

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

但是對(duì)一個(gè)僅僅讀取數(shù)據(jù)的事務(wù)使用排他鎖非常昂貴，因?yàn)檫@會(huì)迫使其它只需要讀取相同數(shù)據(jù)的事務(wù)等待。因此就有了另一種鎖，共享鎖。

共享鎖是這樣的：

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

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

 

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

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

死鎖

但是使用鎖會(huì)導(dǎo)致一種情況，2個(gè)事務(wù)永遠(yuǎn)在等待一塊數(shù)據(jù)：

 

在本圖中：

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

這叫死鎖。

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

• 殺死數(shù)據(jù)修改量最少的事務(wù)（這樣能減少回滾的成本）？
• 殺死持續(xù)時(shí)間最短的事務(wù)，因?yàn)槠渌聞?wù)的用戶等的時(shí)間更長(zhǎng)？
• 殺死能用更少時(shí)間結(jié)束的事務(wù)（避免可能的資源饑荒）？
• 一旦發(fā)生回滾，有多少事務(wù)會(huì)受到回滾的影響？

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

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

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

兩段鎖

實(shí)現(xiàn)純粹的隔離最簡(jiǎn)單的方法是：事務(wù)開始時(shí)獲取鎖，結(jié)束時(shí)釋放鎖。就是說(shuō)，事務(wù)開始前必須等待確保自己能加上所有的鎖，當(dāng)事務(wù)結(jié)束時(shí)釋放自己持有的鎖。這是行得通的，但是為了等待所有的鎖，大量的時(shí)間被浪費(fèi)了。

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

• 成長(zhǎng)階段：事務(wù)可以獲得鎖，但不能釋放鎖。
• 收縮階段：事務(wù)可以釋放鎖（對(duì)于已經(jīng)處理完而且不會(huì)再次處理的數(shù)據(jù)），但不能獲得新鎖。

 

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

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

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

多說(shuō)幾句

當(dāng)然了，真實(shí)的數(shù)據(jù)庫(kù)使用更復(fù)雜的系統(tǒng)，涉及到更多類型的鎖（比如意向鎖，intention locks）和更多的粒度（行級(jí)鎖、頁(yè)級(jí)鎖、分區(qū)鎖、表鎖、表空間鎖），但是道理是相同的。

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

版本控制是這樣的：

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

這將提高性能，因?yàn)椋?/p>

• 讀事務(wù)不會(huì)阻塞寫事務(wù)
• 寫事務(wù)不會(huì)阻塞讀
• 沒(méi)有『臃腫緩慢』的鎖管理器帶來(lái)的額外開銷

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

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

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

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

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

日志管理器

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

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

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

有 2 個(gè)辦法解決這個(gè)問(wèn)題：

• 影子副本/頁(yè)（Shadow copies/pages）：每個(gè)事務(wù)創(chuàng)建自己的數(shù)據(jù)庫(kù)副本（或部分?jǐn)?shù)據(jù)庫(kù)的副本），并基于這個(gè)副本來(lái)工作。一旦出錯(cuò)，這個(gè)副本就被移除；一旦成功，數(shù)據(jù)庫(kù)立即使用文件系統(tǒng)的一個(gè)把戲，把副本替換到數(shù)據(jù)中，然后刪掉『舊』數(shù)據(jù)。
• 事務(wù)日志（Transaction log）：事務(wù)日志是一個(gè)存儲(chǔ)空間，在每次寫盤之前，數(shù)據(jù)庫(kù)在事務(wù)日志中寫入一些信息，這樣當(dāng)事務(wù)崩潰或回滾，數(shù)據(jù)庫(kù)知道如何移除或完成尚未完成的事務(wù)。

WAL（預(yù)寫式日志）

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

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

• 1) 每個(gè)對(duì)數(shù)據(jù)庫(kù)的修改都產(chǎn)生一條日志記錄，在數(shù)據(jù)寫入磁盤之前日志記錄必須寫入事務(wù)日志。
• 2) 日志記錄必須按順序?qū)懭?；記?A 發(fā)生在記錄 B 之前，則 A 必須寫在 B 之前。
• 3) 當(dāng)一個(gè)事務(wù)提交時(shí)，在事務(wù)成功之前，提交順序必須寫入到事務(wù)日志。

 

這個(gè)工作由日志管理器完成。簡(jiǎn)單的理解就是，日志管理器處于緩存管理器（cache manager）和數(shù)據(jù)訪問(wèn)管理器（data access manager，負(fù)責(zé)把數(shù)據(jù)寫入磁盤）之間，每個(gè) update / delete / create / commit / rollback 操作在寫入磁盤之前先寫入事務(wù)日志。簡(jiǎn)單，對(duì)吧？

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

ARIES

1992年，IBM 研究人員『發(fā)明』了WAL的增強(qiáng)版，叫 ARIES。ARIES 或多或少地在現(xiàn)代數(shù)據(jù)庫(kù)中使用，邏輯未必相同，但AIRES背后的概念無(wú)處不在。我給發(fā)明加了引號(hào)是因?yàn)?，按照MIT這門課的說(shuō)法，IBM 的研究人員『僅僅是寫了事務(wù)恢復(fù)的最佳實(shí)踐方法』。AIRES 論文發(fā)表的時(shí)候我才 5 歲，我不關(guān)心那些酸溜溜的科研人員老掉牙的閑言碎語(yǔ)。事實(shí)上，我提及這個(gè)典故，是在開始探討最后一個(gè)技術(shù)點(diǎn)前讓你輕松一下。我閱讀過(guò)這篇 ARIES 論文 的大量篇幅，發(fā)現(xiàn)它很有趣。在這一部分我只是簡(jiǎn)要的談一下 ARIES，不過(guò)我強(qiáng)烈建議，如果你想了解真正的知識(shí)，就去讀那篇論文。

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

這個(gè)技術(shù)要達(dá)到一個(gè)雙重目標(biāo)：

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

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

• 因?yàn)橛脩羧∠?/li>
• 因?yàn)榉?wù)器或網(wǎng)絡(luò)故障
• 因?yàn)槭聞?wù)破壞了數(shù)據(jù)庫(kù)完整性（比如一個(gè)列有唯一性約束而事務(wù)添加了重復(fù)值）
• 因?yàn)樗梨i

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

這怎么可能呢？為了回答這個(gè)問(wèn)題，我們需要了解日志里保存的信息。

日志

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

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

進(jìn)一步說(shuō)，磁盤上每個(gè)頁(yè)（保存數(shù)據(jù)的，不是保存日志的）都記錄著最后一個(gè)修改該數(shù)據(jù)操作的LSN。

*LSN的分配其實(shí)更復(fù)雜，因?yàn)樗P(guān)系到日志存儲(chǔ)的方式。但道理是相同的。

** ARIES 只使用邏輯UNDO，因?yàn)樘幚砦锢鞺NDO太過(guò)混亂了。

注：據(jù)我所知，只有 PostgreSQL 沒(méi)有使用UNDO，而是用一個(gè)垃圾回收服務(wù)來(lái)刪除舊版本的數(shù)據(jù)。這個(gè)跟 PostgreSQL 對(duì)數(shù)據(jù)版本控制的實(shí)現(xiàn)有關(guān)。

為了更好的說(shuō)明這一點(diǎn)，這有一個(gè)簡(jiǎn)單的日志記錄演示圖，是由查詢 “UPDATE FROM PERSON SET AGE = 18;” 產(chǎn)生的，我們假設(shè)這個(gè)查詢是事務(wù)18執(zhí)行的。

 

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

日志緩沖區(qū)

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

 

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

• 1) 緩存管理器將修改存入自己的緩沖區(qū)；
• 2) 日志管理器將相關(guān)的日志存入自己的緩沖區(qū)；
• 3) 到了這一步，查詢執(zhí)行器認(rèn)為操作完成了（因此可以請(qǐng)求做另一次修改）；
• 4) 接著（不久以后）日志管理器把日志寫入事務(wù)日志，什么時(shí)候?qū)懭罩居赡乘惴▉?lái)決定。
• 5) 接著（不久以后）緩存管理器把修改寫入磁盤，什么時(shí)候?qū)懕P由某算法來(lái)決定。

當(dāng)事務(wù)提交，意味著事務(wù)每一個(gè)操作的 1 2 3 4 5 步驟都完成了。寫事務(wù)日志是很快的，因?yàn)樗皇恰涸谑聞?wù)日志某處增加一條日志』；而數(shù)據(jù)寫盤就更復(fù)雜了，因?yàn)橐谩耗軌蚩焖僮x取的方式寫入數(shù)據(jù)』。

STEAL 和 FORCE 策略

出于性能方面的原因，第 5 步有可能在提交之后完成，因?yàn)橐坏┌l(fā)生崩潰，還有可能用REDO日志恢復(fù)事務(wù)。這叫做 NO-FORCE策略。

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

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

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

• STEAL/NO-FORCE 需要 UNDO 和 REDO: 性能高，但是日志和恢復(fù)過(guò)程更復(fù)雜 (比如 ARIES)。多數(shù)數(shù)據(jù)庫(kù)選擇這個(gè)策略。 注：這是我從多個(gè)學(xué)術(shù)論文和教程里看到的，但并沒(méi)有看到官方文檔里顯式說(shuō)明這一點(diǎn)。
• STEAL/ FORCE 只需要 UNDO.
• NO-STEAL/NO-FORCE 只需要 REDO.
• NO-STEAL/FORCE 什么也不需要: 性能最差，而且需要巨大的內(nèi)存。

關(guān)于恢復(fù)

Ok，有了不錯(cuò)的日志，我們來(lái)用用它們！

假設(shè)新來(lái)的實(shí)習(xí)生讓數(shù)據(jù)庫(kù)崩潰了（首要規(guī)矩：永遠(yuǎn)是實(shí)習(xí)生的錯(cuò)。），你重啟了數(shù)據(jù)庫(kù)，恢復(fù)過(guò)程開始了。

ARIES從崩潰中恢復(fù)有三個(gè)階段：

• 1) 分析階段：恢復(fù)進(jìn)程讀取全部事務(wù)日志，來(lái)重建崩潰過(guò)程中所發(fā)生事情的時(shí)間線，決定哪個(gè)事務(wù)要回滾（所有未提交的事務(wù)都要回滾）、崩潰時(shí)哪些數(shù)據(jù)需要寫盤。
• 2) Redo階段：這一關(guān)從分析中選中的一條日志記錄開始，使用 REDO 來(lái)將數(shù)據(jù)庫(kù)恢復(fù)到崩潰之前的狀態(tài)。

在REDO階段，REDO日志按照時(shí)間順序處理（使用LSN）。

對(duì)每一條日志，恢復(fù)進(jìn)程需要讀取包含數(shù)據(jù)的磁盤頁(yè)LSN。

如果LSN（磁盤頁(yè)）>= LSN（日志記錄），說(shuō)明數(shù)據(jù)已經(jīng)在崩潰前寫到磁盤（但是值已經(jīng)被日志之后、崩潰之前的某個(gè)操作覆蓋），所以不需要做什么。

如果LSN（磁盤頁(yè)）< LSN（日志記錄），那么磁盤上的頁(yè)將被更新。

即使將被回滾的事務(wù)，REDO也是要做的，因?yàn)檫@樣簡(jiǎn)化了恢復(fù)過(guò)程（但是我相信現(xiàn)代數(shù)據(jù)庫(kù)不會(huì)這么做的）。

• 3) Undo階段：這一階段回滾所有崩潰時(shí)未完成的事務(wù)?；貪L從每個(gè)事務(wù)的最后一條日志開始，并且按照時(shí)間倒序處理UNDO日志（使用日志記錄的PrevLSN）。

 

恢復(fù)過(guò)程中，事務(wù)日志必須留意恢復(fù)過(guò)程的操作，以便寫入磁盤的數(shù)據(jù)與事務(wù)日志相一致。一個(gè)解決辦法是移除被取消的事務(wù)產(chǎn)生的日志記錄，但是這個(gè)太困難了。相反，ARIES在事務(wù)日志中記錄補(bǔ)償日志，來(lái)邏輯上刪除被取消的事務(wù)的日志記錄。

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

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

當(dāng)新的事務(wù)產(chǎn)生時(shí)，這兩個(gè)表由緩存管理器和事務(wù)管理器更新。因?yàn)槭窃趦?nèi)存中，當(dāng)數(shù)據(jù)庫(kù)崩潰時(shí)它們也被破壞掉了。

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

結(jié)語(yǔ)

寫這篇文章之前，我知道這個(gè)題目有多大，也知道寫這樣一篇深入的文章會(huì)相當(dāng)耗時(shí)。最后證明我過(guò)于樂(lè)觀了，實(shí)際上花了兩倍于預(yù)期的時(shí)間，但是我學(xué)到了很多。

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

如果你仔細(xì)閱讀了本文，你現(xiàn)在應(yīng)該了解一個(gè)數(shù)據(jù)庫(kù)是多么的強(qiáng)大了。鑒于文章很長(zhǎng)，讓我來(lái)提醒你我們都學(xué)到了什么：

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

但是，數(shù)據(jù)庫(kù)包含了更多的聰明巧技。比如，我并沒(méi)有談到下面這些棘手的問(wèn)題：

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

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

最后說(shuō)一句，如果有人問(wèn)你數(shù)據(jù)庫(kù)的原理是什么，你不用逃之夭夭，現(xiàn)在你可以回答：給你篇文章自己看~