2017-08-14

---

layout: post

title:? "如果有人問(wèn)你關(guān)系型數(shù)據(jù)庫(kù)的原理，叫他看這篇文章(轉(zhuǎn))"

date:? 2018-03-10 12:00:00 +0800

categories: 讀書(shū)筆記

tags:? 讀書(shū)筆記數(shù)據(jù)庫(kù) 關(guān)系型數(shù)據(jù)庫(kù)

author: cm

---

* content

{:toc}

[原文](http://blog.jobbole.com/100349/)

> 本文由伯樂(lè)在線 - Panblack 翻譯，黃利民校稿禁熏。未經(jīng)許可蛤奢，禁止轉(zhuǎn)載！英文出處：Christophe Kalenzaga。歡迎加入翻譯組楞泼。

一提到關(guān)系型數(shù)據(jù)庫(kù)炮捧，我禁不住想：有些東西被忽視了庶诡。關(guān)系型數(shù)據(jù)庫(kù)無(wú)處不在，而且種類(lèi)繁多咆课，從小巧實(shí)用的 SQLite 到強(qiáng)大的 Teradata 末誓。但很少有文章講解數(shù)據(jù)庫(kù)是如何工作的。你可以自己谷歌/百度一下『關(guān)系型數(shù)據(jù)庫(kù)原理』书蚪，看看結(jié)果多么的稀少*【譯者注：百度為您找到相關(guān)結(jié)果約1,850,000個(gè)…】* 喇澡，而且找到的那些文章都很短。現(xiàn)在如果你查找最近時(shí)髦的技術(shù)（大數(shù)據(jù)殊校、NoSQL或JavaScript）晴玖，你能找到更多深入探討它們?nèi)绾喂ぷ鞯奈恼隆?/p>

難道關(guān)系型數(shù)據(jù)庫(kù)已經(jīng)太古老太無(wú)趣，除了大學(xué)教材为流、研究文獻(xiàn)和書(shū)籍以外呕屎，沒(méi)人愿意講了嗎闽寡？

![](http://ww3.sinaimg.cn/mw690/7cc829d3jw1f3drdkrg19j208c08w3z1.jpg)

作為一個(gè)開(kāi)發(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)掌握怎么寫(xiě)一個(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è)概念建議先看看[維基](https://en.wikipedia.org/wiki/Time_complexity)或[百度百科](http://baike.baidu.com/view/104946.htm)彻消，對(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)的星系……)锥忿，開(kāi)發(fā)者必須確切地知道他們的代碼需要多少次運(yùn)算牛郑。他們把算法和數(shù)據(jù)結(jié)構(gòu)牢記于心，因?yàn)樗麄兊挠?jì)算機(jī)運(yùn)行緩慢敬鬓，無(wú)法承受對(duì)CPU和內(nèi)存的浪費(fèi)淹朋。

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

### O(1) vs O(n\^2)

現(xiàn)今很多開(kāi)發(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)』](http://blog.jobbole.com/55184/)淘这。這個(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ù)，但是給出的是一種理念筹陵。

![](http://ww2.sinaimg.cn/mw690/7cc829d3jw1f3drdktjmvj20ez0bggmz.jpg)

圖中可以看到不同類(lèi)型的復(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è)均衡的樹(shù)會(huì)得到 O(log(n)) 復(fù)雜度? （比如二分搜索帅掘，如10000000個(gè)排序的數(shù)，搜索20次就能找到結(jié)果）

* 搜索一個(gè)陣列會(huì)得到 O(n) 復(fù)雜度? ? ? ? ? （順序掃描最差情況）

* 最好的排序算法具有 O(n*log(n)) 復(fù)雜度

* 糟糕的排序算法具有 O(n\^2) 復(fù)雜度? ? ? （平方相乘）

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

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

* 一般情況場(chǎng)景

* 最佳情況場(chǎng)景

* 最差情況場(chǎng)景

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

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

* 算法的內(nèi)存消耗

* 算法的磁盤(pán) I/O 消耗

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

* n\^4：差勁！我將要提到的一些算法具備這種復(fù)雜度迫靖。

* 3\^n：更差勁院峡！本文中間部分研究的一些算法中有一個(gè)具備這種復(fù)雜度（而且在很多數(shù)據(jù)庫(kù)中還真的使用了）。

* 階乘 n：你永遠(yuǎn)得不到結(jié)果系宜，即便在少量數(shù)據(jù)的情況下照激。

```

n=4

1*2*3*4

```

* n\^n：如果你發(fā)展到這種復(fù)雜度了，那你應(yīng)該問(wèn)問(wèn)自己IT是不是你的菜盹牧。

注：我并沒(méi)有給出『大O表示法』的真正定義俩垃，只是利用這個(gè)概念』恫撸可以看看維基百科上的[這篇文章](https://en.wikipedia.org/wiki/Big_O_notation)吆寨。

### 合并排序

當(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)接** 。

#### 合并

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

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

![](http://ww2.sinaimg.cn/mw690/7cc829d3jw1f3drdlx1osj20b5069mxt.jpg)

通過(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ì)原理](http://blog.jobbole.com/79293/)，其中一個(gè)動(dòng)圖（原圖較長(zhǎng)荔睹，我做了刪減）清晰的演示了上述合并排序的過(guò)程狸演，而原文的敘述似乎沒(méi)有這么清晰，不動(dòng)戳大僻他∠啵】

![](http://ww2.sinaimg.cn/mw690/7cc829d3jw1f3drdn5ynkg208w05cjsj.gif)

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

```

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;

```

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

* 拆分階段哈恰，將序列分為更小的序列

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

#### 拆分階段

![](http://ww4.sinaimg.cn/large/7cc829d3jw1f3drdnwywaj20gl08ljst.jpg)

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

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

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

#### 排序階段

![](http://ww2.sinaimg.cn/large/7cc829d3jw1f3drdoof0qj20gn0a0mz3.jpg)

在排序階段紧显，你從一元序列開(kāi)始讲衫。在每一個(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)戳大【被】*

![](http://ww2.sinaimg.cn/mw690/7cc829d3jw1f3drdpmohcg208c05040x.gif)

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

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

因?yàn)椋?/p>

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

注：這種算法叫『原地算法』([in-place algorithm](https://en.wikipedia.org/wiki/In-place_algorithm))

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

注：這種算法叫『外部排序』([external sorting](https://en.wikipedia.org/wiki/External_sorting))迁霎。

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

比如，分布式合并排序是[Hadoop](https://hadoop.apache.org/docs/stable/api/org/apache/hadoop/mapreduce/Reducer.html)（那個(gè)著名的大數(shù)據(jù)框架）的關(guān)鍵組件之一秘豹。

* 這個(gè)算法可以點(diǎn)石成金（事實(shí)如此Ｐ）

這個(gè)排序算法在大多數(shù)（如果不是全部的話）數(shù)據(jù)庫(kù)中使用，但是它并不是唯一算法。如果你想多了解一些啄刹，你可以看看 [這篇論文](http://wwwlgis.informatik.uni-kl.de/archiv/wwwdvs.informatik.uni-kl.de/courses/DBSREAL/SS2005/Vorlesungsunterlagen/Implementing_Sorting.pdf)涮坐，探討的是數(shù)據(jù)庫(kù)中常用排序算法的優(yōu)勢(shì)和劣勢(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ù)索引的概念。

這種算法也叫二分搜索（**binary search**）

#### 1 陣列

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

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209229967045.jpg)

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

* 每個(gè)行代表一個(gè)主體

* 列用來(lái)描述主體的特征

* 每個(gè)列保存某一種類(lèi)型對(duì)數(shù)據(jù)（整數(shù)、字符串句柠、日期……）

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

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

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

* 比保存在左子樹(shù)的任何鍵值都要大

* 比保存在右子樹(shù)的任何鍵值都要小

【譯者注：binary search tree，二叉查找樹(shù)/二叉搜索樹(shù)鹰贵，或稱(chēng) Binary Sort Tree 二叉排序樹(shù)晴氨。見(jiàn)百度百科】

##### 概念

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209239491701.jpg)

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

* 我從鍵值為 136 的根開(kāi)始碉输，因?yàn)?136<208籽前，我去找節(jié)點(diǎn)136的右子樹(shù)。

* 398>208敷钾，所以我去找節(jié)點(diǎn)398的左子樹(shù)

* 250>208枝哄，所以我去找節(jié)點(diǎn)250的左子樹(shù)

* 200<208，所以我去找節(jié)點(diǎn)200的右子樹(shù)阻荒。但是 200 沒(méi)有右子樹(shù)挠锥，值不存在（因?yàn)槿绻嬖冢鼤?huì)在 200 的右子樹(shù)）

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

* 我從鍵值為136的根開(kāi)始侨赡，因?yàn)?136>40蓖租，所以我去找節(jié)點(diǎn)136的左子樹(shù)粱侣。

* 80>40，所以我去找節(jié)點(diǎn) 80 的左子樹(shù)

* 40=40蓖宦，節(jié)點(diǎn)存在齐婴。我抽取出節(jié)點(diǎn)內(nèi)部行的ID（圖中沒(méi)有畫(huà)）再去表中查找對(duì)應(yīng)的 ROW ID。

* 知道 ROW ID我就知道了數(shù)據(jù)在表中對(duì)精確位置稠茂，就可以立即獲取數(shù)據(jù)柠偶。

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

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

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

* 如果你想知道誰(shuí)在 UK 工作

* 你在樹(shù)中查找代表 UK 的節(jié)點(diǎn)

* 在『UK 節(jié)點(diǎn)』你會(huì)找到 UK 員工那些行的位置

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

#### 2 B+樹(shù)索引

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

* 只有最底層的節(jié)點(diǎn)（葉子節(jié)點(diǎn)）才保存信息（相關(guān)表的行位置）

* 其它節(jié)點(diǎn)只是在**搜索中**用來(lái)指引到**正確節(jié)點(diǎn)**的。

【譯者注：參考[ B+樹(shù) ](http://baike.baidu.com/view/1168762.htm)塞俱， [二叉樹(shù)遍歷](http://baike.baidu.com/view/549587.htm)? ? [維基百科](https://en.wikipedia.org/wiki/Tree_traversal)】

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209240934641.jpg)

你可以看到姐帚，節(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ù)生棍，假設(shè)你要找40到100間的值：

* 你只需要找 40（若40不存在則找40之后最貼近的值）颤霎，就像你在上一個(gè)樹(shù)中所做的那樣。

* 然后用那些連接來(lái)收集40的后續(xù)節(jié)點(diǎn)涂滴，直到找到100友酱。

比方說(shuō)你找到了 M 個(gè)后續(xù)節(jié)點(diǎn)，樹(shù)總共有 N 個(gè)節(jié)點(diǎn)柔纵。對(duì)指定節(jié)點(diǎn)的搜索成本是 log(N)缔杉，跟上一個(gè)樹(shù)相同。但是當(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è)樹(shù)所用的 N 次運(yùn)算霸琴。此外，你不需要讀取整個(gè)樹(shù)（僅需要讀 M+log(N) 個(gè)節(jié)點(diǎn)）,這意味著更少的磁盤(pán)訪問(wèn)昭伸。如果 M 很形喑恕（比如 200 行）并且 N 很大（1,000,000），那結(jié)果就是天壤之別了庐杨。

然而還有新的問(wèn)題（又來(lái)了Ｑ〉鳌）。如果你在數(shù)據(jù)庫(kù)中增加或刪除一行（從而在相關(guān)的 B+樹(shù)索引里）：

* 你必須在B+樹(shù)中的節(jié)點(diǎn)之間保持順序灵份，否則節(jié)點(diǎn)會(huì)變得一團(tuán)糟仁堪，你無(wú)法從中找到想要的節(jié)點(diǎn)。

* 你必須盡可能降低B+樹(shù)的層數(shù)各吨，否則 O(log(N)) 復(fù)雜度會(huì)變成 O(N)枝笨。

換句話說(shuō)，B+樹(shù)需要自我整理和自我平衡揭蜒。謝天謝地横浑，我們有智能刪除和插入。但是這樣也帶來(lái)了成本：在B+樹(shù)中屉更，插入和刪除操作是 O(log(N)) 復(fù)雜度徙融。所以有些人聽(tīng)到過(guò)**使用太多索引不是個(gè)好主意**這類(lèi)說(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ù)的文章](https://en.wikipedia.org/wiki/B%2B_tree)。如果你想要數(shù)據(jù)庫(kù)中實(shí)現(xiàn)B+樹(shù)的例子职车，看看MySQL核心開(kāi)發(fā)人員寫(xiě)的[這篇文章](http://blog.jcole.us/2013/01/07/the-physical-structure-of-innodb-index-pages/) 和 [這篇文章](http://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/)瘫俊。兩篇文章都致力于探討 innoDB(MySQL引擎)如何處理索引。

#### 3 哈希表

我們最后一個(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è)形象化的例子：

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209251879854.jpg)

這個(gè)哈希表有10個(gè)哈希桶李破。因?yàn)槲覒谐韬澹抑唤o出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)算](http://baike.baidu.com/view/4887065.htm)】

比方說(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)存，剩下的哈希桶可以留在硬盤(pán)上茸炒。

* 用陣列的話愕乎，你需要一個(gè)連續(xù)內(nèi)存空間阵苇。如果你加載一個(gè)大表，很難分配足夠的連續(xù)內(nèi)存空間感论。

* 用哈希表的話绅项，你可以選擇你要的關(guān)鍵字（比如，一個(gè)人的國(guó)家和姓氏）比肄。

想要更詳細(xì)的信息快耿，你可以閱讀我在[Java HashMap](http://coding-geek.com/how-does-a-hashmap-work-in-java/) 上的文章，是關(guān)于高效哈希表實(shí)現(xiàn)的芳绩。你不需要了解Java就能理解文章里的概念掀亥。

## 二全局概覽

我們已經(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)理解：

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209278136645.jpg)

撰寫(xiě)這部分之前笔呀，我讀過(guò)很多書(shū)/論文幢踏，它們都以自己的方式描述數(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）**：磁盤(pán)I/O是數(shù)據(jù)庫(kù)的首要瓶頸焕数。**具備一個(gè)文件系統(tǒng)管理器來(lái)完美地處理OS文件系統(tǒng)甚至取代OS文件系統(tǒng)纱昧，是非常重要的。

* 內(nèi)存管理器（memory manager）：為了避免磁盤(pán)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ù)（比如表的名稱(chēng)和結(jié)構(gòu)），提供管理數(shù)據(jù)庫(kù)的猛、模式耀盗、表空間的工具。

*【譯者注：好吧卦尊，我真的不知道Administration manager該翻譯成什么叛拷，有知道的麻煩告知，不勝感激……】*

* ……

**查詢管理器：**

查詢解析器（Query parser）：用于檢查查詢是否合法

查詢重寫(xiě)器（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ù)寫(xiě)入磁盤(pán)之前置于內(nèi)存

* 數(shù)據(jù)訪問(wèn)管理器（Data access manager）：訪問(wèn)磁盤(pán)中的數(shù)據(jù)

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

* 客戶端管理器

* 查詢管理器

* 數(shù)據(jù)管理器（含復(fù)原管理器）

## 三客戶端管理器

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209283969615.jpg)

客戶端管理器是處理客戶端通信的√视眩客戶端可以是一個(gè)（網(wǎng)站）服務(wù)器或者一個(gè)最終用戶或最終應(yīng)用『С拢客戶端管理器通過(guò)一系列知名的API（JDBC, ODBC, OLE-DB …）提供不同的方式來(lái)訪問(wèn)數(shù)據(jù)庫(kù)震庭。

客戶端管理器也提供專(zhuān)有的數(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ū)并且開(kāi)始給你發(fā)送涧尿。**

* 如果遇到問(wèn)題，管理器關(guān)閉連接危彩，向你發(fā)送可讀的解釋信息徒欣，然后釋放資源逐样。

## 四查詢管理器

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209284730602.jpg)

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

* 查詢首先被**解析**并判斷是否合法

* 然后被**重寫(xiě)**，去除了無(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)存取路徑選擇](http://www.cs.berkeley.edu/~brewer/cs262/3-selinger79.pdf)酷宵。這個(gè)篇文章只有12頁(yè)亥贸，而且具備計(jì)算機(jī)一般水平就能理解。

* 非常好浇垦、非常深入的 DB2 9.X 如何優(yōu)化查詢的[介紹](http://infolab.stanford.edu/~hyunjung/cs346/db2-talk.pdf)

* 非常好的PostgreSQL如何優(yōu)化查詢的介紹炕置。這是一篇最通俗易懂的文檔，因?yàn)樗v的是『我們來(lái)看看在這種情況下男韧，PostgreSQL給出了什么樣的查詢計(jì)劃』朴摊，而不是『我們來(lái)看看PostgreSQL用的什么算法』。

* 官方[SQLite優(yōu)化文檔](https://www.sqlite.org/optoverview.html)此虑∩醺伲『易于』閱讀，因?yàn)镾QLite用的是簡(jiǎn)單規(guī)則朦前。再者介杆，這是唯一真正解釋SQLite如何工作的官方文檔。

* 非常好的SQL Server 2005 如何優(yōu)化查詢的[介紹](https://blogs.msdn.com/cfs-filesystemfile.ashx/__key/communityserver-components-postattachments/00-08-50-84-93/QPTalk.pdf)

* Oracle 12c 優(yōu)化[白皮書(shū)](http://www.oracle.com/technetwork/database/bi-datawarehousing/twp-optimizer-with-oracledb-12c-1963236.pdf)

* 2篇查詢優(yōu)化的教程韭寸，[第一篇](http://codex.cs.yale.edu/avi/db-book/db6/slide-dir/PPT-dir/ch12.ppt) [第二篇](http://codex.cs.yale.edu/avi/db-book/db6/slide-dir/PPT-dir/ch13.ppt)春哨。教程來(lái)自《數(shù)據(jù)庫(kù)系統(tǒng)概念》的作者，很好的讀物恩伺，集中討論磁盤(pán)I/O赴背，但是要求具有很好的計(jì)算機(jī)科學(xué)水平。

* 另一個(gè)[原理教程](https://www.informatik.hu-berlin.de/de/forschung/gebiete/wbi/teaching/archive/sose05/dbs2/slides/09_joins.pdf)莫其，這篇教程我覺(jué)得更易懂癞尚，不過(guò)它僅關(guān)注聯(lián)接運(yùn)算符（join operators）和磁盤(pán)I/O。

### 查詢解析器

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

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

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

* **表是否存在**

* 表的**字段**是否存在

* 對(duì)某類(lèi)型字段的 **運(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è)樹(shù)）。

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

### 查詢重寫(xiě)器

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

* 預(yù)優(yōu)化查詢

* 避免不必要的運(yùn)算

* 幫助優(yōu)化器找到合理的最佳解決方案

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

* 視圖合并：如果你在查詢中使用視圖概行，視圖就會(huì)轉(zhuǎn)換為它的 SQL 代碼。

* 子查詢扁平化：子查詢是很難優(yōu)化的弧岳，因此重寫(xiě)器會(huì)嘗試移除子查詢

例如：

MySQL

```

SELECT PERSON.*

FROM PERSON

WHERE PERSON.person_key IN

(SELECT MAILS.person_key

FROM MAILS

WHERE MAILS.mail LIKE 'christophe%');

```

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

```

SELECT PERSON.*

FROM PERSON, MAILS

WHERE PERSON.person_key = MAILS.person_key

and MAILS.mail LIKE 'christophe%';

```

* 去除不必要的運(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ì)算热幔，那么在重寫(xiě)過(guò)程中計(jì)算會(huì)執(zhí)行一次。比如 WHERE AGE > 10+2 會(huì)轉(zhuǎn)換為 WHERE AGE > 12 讼庇， TODATE(“日期字符串”) 會(huì)轉(zhuǎn)換為 datetime 格式的日期值绎巨。

* （高級(jí)）分區(qū)裁剪（Partition Pruning）：如果你用了分區(qū)表，重寫(xiě)器能夠找到需要使用的分區(qū)蠕啄。

* （高級(jí)）物化視圖重寫(xiě)（Materialized view rewrite）：如果你有個(gè)物化視圖匹配查詢謂詞的一個(gè)子集场勤，重寫(xiě)器將檢查視圖是否最新并修改查詢戈锻，令查詢使用物化視圖而不是原始表。

* （高級(jí)）自定義規(guī)則：如果你有自定義規(guī)則來(lái)修改查詢（就像 Oracle policy）和媳，重寫(xiě)器就會(huì)執(zhí)行這些規(guī)則格遭。

* （高級(jí)）OLAP轉(zhuǎn)換：分析/加窗函數(shù)，星形聯(lián)接留瞳，ROLLUP 函數(shù)……都會(huì)發(fā)生轉(zhuǎn)換（但我不確定這是由重寫(xiě)器還是優(yōu)化器來(lái)完成拒迅，因?yàn)閮蓚€(gè)進(jìn)程聯(lián)系很緊，必須看是什么數(shù)據(jù)庫(kù)）她倘。

*【譯者注：物化視圖? 璧微。謂詞，predicate帝牡，條件表達(dá)式的求值返回真或假的過(guò)程】*

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

### 統(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ù)需要什么類(lèi)型的信息呢瓷炮？

我必須（簡(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ì)查詢所需的磁盤(pán) 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ù)字類(lèi)型數(shù)據(jù)行（注：這個(gè)概念的技術(shù)名稱(chēng)叫**選擇率**）憎兽。

統(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](https://www.informatik.hu-berlin.de/de/forschung/gebiete/wbi/teaching/archive/sose05/dbs2/slides/09_joins.pdf)。

### 查詢優(yōu)化器

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209308313727.jpg)

所有的現(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ì)專(zhuān)注于它們的時(shí)間復(fù)雜度，但是和蚪，**數(shù)據(jù)庫(kù)優(yōu)化器計(jì)算的是它們的 CPU 成本止状、磁盤(pán) 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 的概念杀赢。由于磁盤(pán) I/O 是個(gè)重要的概念烘跺，我偶爾也會(huì)提到它。請(qǐng)牢記脂崔，**大多數(shù)時(shí)候瓶頸在于磁盤(pán) I/O 而不是 CPU 使用滤淳。**

#### 索引

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

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

另外煤蹭，很多現(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)題是磁盤(pán) I/O稽物，我不會(huì)過(guò)多探討時(shí)間復(fù)雜度奄毡。

【譯者注：[四種類(lèi)型的Oracle索引掃描介紹](http://soft.chinabyte.com/database/16/11806516.shtml)? 】

##### 全掃描

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

但是如果取得值很多盗忱，又很零散，全掃描不一定差羊赵。

##### 范圍掃描

其他類(lèi)型的掃描有**索引范圍掃描**趟佃，比如當(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è)索引，**因此在磁盤(pán) I/O 方面沒(méi)有全掃描那么昂貴**毒返。

##### 唯一掃描

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

##### 根據(jù) ROW ID 存取

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

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

```

SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28

```

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

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

```

SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON

WHERE PERSON.AGE = TYPE_PERSON.AGE

```

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í)是磁盤(pán) I/O霍骄。假如需要大量的根據(jù)行ID存取，數(shù)據(jù)庫(kù)也許會(huì)選擇全掃描淡溯。

##### 其它路徑

我沒(méi)有列舉所有的存取路徑读整，如果你感興趣可以讀一讀 [Oracle文檔](https://docs.oracle.com/database/121/TGSQL/tgsql_optop.htm)。其它數(shù)據(jù)庫(kù)里也許叫法不同但背后的概念是一樣的咱娶。

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

參考

[數(shù)據(jù)庫(kù)多表連接方式介紹－HASH-JOIN](https://www.cnblogs.com/shangyu/p/6055181.html)

那么米间，我們知道如何獲取數(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）](http://baike.baidu.com/view/672349.htm)? 德迹、[外聯(lián)接（OUTER JOIN）](http://baike.baidu.com/view/1213593.htm)? ” 不是一個(gè)概念。只查到百度百科詞條：[關(guān)系數(shù)據(jù)庫(kù)](http://baike.baidu.com/view/68348.htm) 里提到“每個(gè)表格（有時(shí)被稱(chēng)為一個(gè)關(guān)系）……” 。其他參考鏈接 [“Merge Join”](https://en.wikipedia.org/wiki/Sort-merge_join)? [“Hash Join”](https://en.wikipedia.org/wiki/Hash_join)? [“Nested Loop Join”](https://en.wikipedia.org/wiki/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 的值。

外關(guān)系 - 驅(qū)動(dòng)表? - N

內(nèi)關(guān)系 - 被驅(qū)動(dòng)表? - M

在提到SQL語(yǔ)句的執(zhí)行計(jì)劃時(shí)愤惰，我們常常提到驅(qū)動(dòng)表苇经，那么，什么是驅(qū)動(dòng)表宦言，驅(qū)動(dòng)表一定是表嗎扇单？所謂驅(qū)動(dòng)表，又稱(chēng)為外層表奠旺，就是在嵌套循環(huán)連接和哈希連接中蜘澜，用來(lái)最先獲得數(shù)據(jù)，并以此表的數(shù)據(jù)為依據(jù)响疚，逐步獲得其他表的數(shù)據(jù)鄙信，直至最終查詢到所有滿足條件的數(shù)據(jù)的第一個(gè)表。排序合并連接由于不存在優(yōu)先訪問(wèn)那張表的順序問(wèn)題稽寒，因此也沒(méi)有驅(qū)動(dòng)表的概念扮碧。值得注意的是，

注：N 和 M 是關(guān)系的基數(shù)杏糙∩魍酰【譯者注： [基數(shù)](http://baike.baidu.com/subview/131521/5127870.htm) 】

##### 嵌套循環(huán)聯(lián)接（Nested loop join）

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

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209322001714.jpg)

道理如下：

* 針對(duì)外關(guān)系的每一行

* 查看內(nèi)關(guān)系里的所有行來(lái)尋找匹配的行

下面是偽代碼：

```

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

```

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

在磁盤(pán) I/O 方面，針對(duì) N 行外關(guān)系的每一行谅河，內(nèi)部循環(huán)需要從內(nèi)關(guān)系讀取 M 行咱旱。這個(gè)算法需要從磁盤(pán)讀取 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ū)別狐粱，但是在磁盤(pán) I/O 方面，最好最好的胆数，是每個(gè)關(guān)系只讀取一次肌蜻。

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

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

* 為了避免逐行讀取兩個(gè)關(guān)系酸休，

* 你可以成簇讀取，把（兩個(gè)關(guān)系里讀到的）兩簇?cái)?shù)據(jù)行保存在內(nèi)存里祷杈，

* 比較兩簇?cái)?shù)據(jù)，保留匹配的渗饮，

* 然后從磁盤(pán)加載新的數(shù)據(jù)簇來(lái)繼續(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

```

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

* 用前一個(gè)版本私蕾，算法需要 N + N*M 次訪問(wèn)（每次訪問(wèn)讀取一行）。

* 用新版本胡桃，磁盤(pá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ù)簇的尺寸，可以降低磁盤(pán)訪問(wèn)翠胰。

##### 哈希聯(lián)接(HASH-JOIN)

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

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209324622230.jpg)

哈希聯(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)是否與外關(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 + 創(chuàng)建哈希表的成本(M) + 哈希函數(shù)的成本 * N 轻纪。

如果哈希函數(shù)創(chuàng)建了足夠小規(guī)模的哈希桶油额，那么復(fù)雜度就是 O(M+N)。

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

1) 計(jì)算內(nèi)關(guān)系和外關(guān)系雙方的哈希表

2) 保存哈希表到磁盤(pán)

3) 然后逐個(gè)哈希桶比較（其中一個(gè)讀入內(nèi)存，另一個(gè)逐行讀任依蕖）衬以。

##### 合并聯(lián)接(sort merge-join)

合并聯(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](http://blog.csdn.net/dnnyyq/article/details/5195472) 】

* 如果關(guān)系是聯(lián)接條件里的一個(gè)索引

* 如果聯(lián)接應(yīng)用在一個(gè)查詢中已經(jīng)排序的中間結(jié)果

###### 合并聯(lián)接

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209334055469.jpg)

這部分與我們研究過(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%正確）：

```

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

```

##### 哪個(gè)算法最好？

如果有最好的坡疼，就沒(méi)必要弄那么多種類(lè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+樹(shù)索引的話，聰明的選擇似乎是合并聯(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)接的類(lèi)型：是**等值聯(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](https://www-01.ibm.com/support/knowledgecenter/SSEPGG_9.7.0/com.ibm.db2.luw.admin.perf.doc/doc/c0005311.html), [ORACLE](http://docs.oracle.com/cd/B28359_01/server.111/b28274/optimops.htm#i76330) 或 [SQL Server](https://technet.microsoft.com/en-us/library/ms191426(v=sql.105).aspx))的文檔屋摔。

#### 簡(jiǎn)化的例子

我們已經(jīng)研究了 3 種類(lèi)型的聯(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

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

```

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

* 每個(gè)聯(lián)接使用那種類(lèi)型糠睡？

我有 3 種可選（哈希挽鞠、合并、嵌套）狈孔，同時(shí)可能用到 0, 1 或 2 個(gè)索引（不必說(shuō)還有多種類(lèi)型的索引）信认。

* 按什么順序執(zhí)行聯(lián)接？

比如均抽，下圖顯示了針對(duì) 4 個(gè)表僅僅 3 次聯(lián)接嫁赏，可能采用的執(zhí)行計(jì)劃：

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209468679794.jpg)

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

* 1) 采取粗暴的方式

用數(shù)據(jù)庫(kù)統(tǒng)計(jì)，**計(jì)算每種可能的執(zhí)行計(jì)劃的成本**到忽，保留最佳方案橄教。但是清寇，會(huì)有很多可能性。對(duì)于一個(gè)給定順序的聯(lián)接操作护蝶，每個(gè)聯(lián)接有三種可能性：哈希华烟、合并、嵌套持灰，那么總共就有 3^4 種可能性盔夜。確定聯(lián)接的順序是個(gè)[二叉樹(shù)的排列問(wèn)題](https://en.wikipedia.org/wiki/Catalan_number)，會(huì)有 (2\*4)!/(4+1)! 種可能的順序堤魁。對(duì)本例這個(gè)相當(dāng)簡(jiǎn)化了的問(wèn)題喂链，我最后會(huì)得到 3\^4\*(2\*4)!/(4+1)! 種可能。

拋開(kāi)專(zhuān)業(yè)術(shù)語(yǔ)妥泉，那相當(dāng)于 27,216 種可能性椭微。如果給合并聯(lián)接加上使用 0,1 或 2 個(gè) B+樹(shù)索引，可能性就變成了 210,000種盲链。我是不是告訴過(guò)你這個(gè)查詢其實(shí)**非常簡(jiǎn)單**嗎蝇率？

* 2) 我大叫一聲辭了這份工作

很有誘惑力，但是這樣一來(lái)刽沾，你不會(huì)的到查詢結(jié)果本慕，而我需要錢(qián)來(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)接×祝』

在這個(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)規(guī)劃佑女，貪婪算法和啟發(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)規(guī)劃**紊选。

##### 動(dòng)態(tài)規(guī)劃

這幾個(gè)字背后的理念是轿腺，很多執(zhí)行計(jì)劃是非常相似的〈猿看看下圖這幾種計(jì)劃：

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209471414961.jpg)

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

應(yīng)用這一技術(shù)杠园，我們不再有 (2*N)!/(N+1)! 的復(fù)雜度顾瞪，而是“只有” 3\^N。在之前 4 個(gè)JOIN 的例子里抛蚁，這意味著將 336 次排序降為 81 次陈醒。如果是大一些的查詢，比如 8 個(gè) JOIN （其實(shí)也不是很大啦）瞧甩，就是將 57,657,600 次降為 6551 次钉跷。

【譯者注：這一小段漏掉了，感謝 nsos指出來(lái)肚逸。另外感謝 Clark Li 指出Dynamic Programing 應(yīng)該翻譯為動(dòng)態(tài)規(guī)劃爷辙。】

對(duì)于計(jì)算機(jī)極客彬坏，下面是我在先前給你的教程里找到的一個(gè)算法。我不提供解釋?zhuān)詢H在你已經(jīng)了解動(dòng)態(tài)規(guī)劃或者精通算法的情況下閱讀（我提醒過(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]

```

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

* 如果我們僅分析一個(gè)特定類(lèi)型的計(jì)劃（例如左深樹(shù) left-deep tree玷犹，[參考](http://wenku.baidu.com/view/54a48b7b852458fb770b56a0.html))混滔，我們得到 n*2^n 而不是 3^n。

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209472927240.jpg)

* 如果我們加上邏輯規(guī)則來(lái)避免一些模式的計(jì)劃（像『如果一個(gè)表有針對(duì)指定謂詞的索引歹颓，就不要對(duì)表嘗試合并聯(lián)接坯屿，要對(duì)索引』），就會(huì)在不給最佳方案造成過(guò)多傷害的前提下巍扛，減少可能性的數(shù)量领跛。【譯者注：原文應(yīng)該是有兩處筆誤： as=has, to=too】

* 如果我們?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è)開(kāi)始（比如 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 開(kāi)始路鹰，我們可以把同樣的算法用在 B岭皂，然后 C姓建，然后 D, 然后 E。最后保留成本最低的執(zhí)行計(jì)劃机断。

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

拋開(kāi)細(xì)節(jié)不談黎休，只需一個(gè)良好的模型和一個(gè) N\*log(N) 復(fù)雜度的排序浓领，問(wèn)題就輕松解決了玉凯。這個(gè)**算法的復(fù)雜度是 O(N*log(N))** ，**對(duì)比一下完全動(dòng)態(tài)規(guī)劃的 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)規(guī)劃算法逝撬。貪婪算法屬于一個(gè)叫做**啟發(fā)式算法**的大家族，它根據(jù)一條規(guī)則（或啟發(fā)）乓土，保存上一步找到的方法宪潮，『附加』到當(dāng)前步驟來(lái)進(jìn)一步搜尋解決方法。有些算法根據(jù)特定規(guī)則趣苏，一步步的應(yīng)用規(guī)則但不總是保留上一步找到的最佳方法狡相。它們統(tǒng)稱(chē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ī)改寫(xiě)

* 4) 1彬伦，2滔悉，3步重復(fù) T 次

* 5) 然后在最后一次循環(huán)伊诵，從 P 個(gè)計(jì)劃里得到最佳計(jì)劃。

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

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

[PostgreSQL](http://www.postgresql.org/docs/9.4/static/geqo-intro.html) 實(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)題的算法綜述](http://www.acad.bg/rismim/itc/sub/archiv/Paper6_1_2009.PDF)》，你可以去閱讀一下诀豁。

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

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

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

我們來(lái)看看 [SQLite 優(yōu)化器](https://www.sqlite.org/optoverview.html) 是怎么工作的烹骨。這是個(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年）開(kāi)始辣辫，SQLite使用『[N最近鄰居](https://www.sqlite.org/queryplanner-ng.html)』貪婪算法來(lái)搜尋最佳查詢計(jì)劃

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

看過(guò)[官方文檔](https://www-01.ibm.com/support/knowledgecenter/SSEPGG_9.7.0/com.ibm.db2.luw.admin.perf.doc/doc/r0005278.html)后谷遂，我們了解到 DB2 優(yōu)化器可以讓你使用 7 種級(jí)別的優(yōu)化：

* 對(duì)聯(lián)接使用貪婪算法

? ? *? ? 0 – 最小優(yōu)化葬馋，使用索引掃描和嵌套循環(huán)聯(lián)接，避免一些查詢重寫(xiě)

? ? *? ? 1 – 低級(jí)優(yōu)化

? ? *? ? 2 – 完全優(yōu)化

* 對(duì)聯(lián)接使用動(dòng)態(tài)規(guī)劃算法

? ? *? ? 3 – 中等優(yōu)化和粗略的近似法

? ? *? ? 5 – 完全優(yōu)化，使用帶有啟發(fā)式的所有技術(shù)

? ? *? ? 7 – 完全優(yōu)化点楼，類(lèi)似級(jí)別5扫尖，但不用啟發(fā)式

? ? *? ? 9 – 最大優(yōu)化，完全不顧開(kāi)銷(xiāo)掠廓，**考慮所有可能的聯(lián)接順序换怖，包括笛卡爾乘積**

可以看到 **DB2 使用貪婪算法和動(dòng)態(tài)規(guī)劃算法**。當(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ì)**切端，包括線段樹(shù)（frequent-value）和分位數(shù)統(tǒng)計(jì)（quantile statistics）彻坛。

* **使用所有查詢重寫(xiě)規(guī)則**（含物化查詢表路由，materialized query table routing）踏枣，除了在極少情況下適用的計(jì)算密集型規(guī)則昌屉。

* **使用動(dòng)態(tài)規(guī)劃模擬聯(lián)接**

*? ? 有限使用組合內(nèi)關(guān)系（composite inner relation）

*? ? 對(duì)于涉及查找表的星型模式，有限使用笛卡爾乘積

* 考慮寬泛的訪問(wèn)方式茵瀑，含列表預(yù)燃渫浴（list prefetch，注：我們將討論什么是列表預(yù)嚷碜颉）竞帽，index ANDing（注：一種對(duì)索引的特殊操作），和物化查詢表路由鸿捧。

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

其它情況 (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í)行器。為了獲得和寫(xiě)入數(shù)據(jù)敞嗡，查詢執(zhí)行器與數(shù)據(jù)管理器交互颁糟，本文下一部分來(lái)討論數(shù)據(jù)管理器。

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

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209479211879.jpg)

在這一步喉悴，查詢管理器執(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ù)的主要瓶頸是磁盤(pán) I/O锋叨。為了提高性能，現(xiàn)代數(shù)據(jù)庫(kù)使用緩存管理器宛篇。

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209479645383.jpg)

查詢執(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)）

* 讀還是寫(xiě)

以及數(shù)據(jù)庫(kù)使用的磁盤(pán)類(lèi)型：

* 7.2k/10k/15k rpm的硬盤(pán)

* SSD

* RAID 1/5/…

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

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

#### 預(yù)讀

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

* 當(dāng)查詢執(zhí)行器處理它的第一批數(shù)據(jù)時(shí)

* 會(huì)告訴緩存管理器預(yù)先裝載第二批數(shù)據(jù)

* 當(dāng)開(kāi)始處理第二批數(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)單地從磁盤(pán)加載下一批連續(xù)數(shù)據(jù)）讼油。

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

注：糟糕的緩存命中率不總是意味著緩存工作狀態(tài)不佳乏屯。更多信息請(qǐng)閱讀[Oracle文檔](http://docs.oracle.com/database/121/TGDBA/tune_buffer_cache.htm)。

緩沖只是容量有限的內(nèi)存空間瘦赫，因此辰晕，為了加載新的數(shù)據(jù)，它需要移除一些數(shù)據(jù)确虱。加載和清除緩存需要一些磁盤(pán)和網(wǎng)絡(luò)I/O的成本含友。如果你有個(gè)經(jīng)常執(zhí)行的查詢，那么每次都把查詢結(jié)果加載然后清除校辩，效率就太低了【轿剩現(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ù)是最近使用的，所以更有可能再次使用荧呐。

圖解：

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209480680569.jpg)

為了更好的理解汉形，我假設(shè)緩沖區(qū)里的數(shù)據(jù)沒(méi)有被閂鎖鎖住（就是說(shuō)是可以被移除的）倍阐。在這個(gè)簡(jiǎn)單的例子里概疆，緩沖區(qū)可以保存 3 個(gè)元素：

* 1：緩存管理器（簡(jiǎn)稱(chēng)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文檔](http://docs.oracle.com/database/121/CNCPT/memory.htm#i10221)中的描述：

『對(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ū)莽囤∶粒』

還有一些可能，比如使用高級(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ò)而且額外開(kāi)銷(xiāo)可以接受蔑水。

關(guān)于LRU-K更深入的知識(shí)，可以閱讀早期的研究論文（1993）：數(shù)[據(jù)庫(kù)磁盤(pán)緩沖的LRU-K頁(yè)面置換算法](http://www.cs.cmu.edu/~christos/courses/721-resources/p297-o_neil.pdf)

其他算法

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

* 2Q（類(lèi)LRU-K算法）

* CLOCK（類(lèi)LRU-K算法）

* MRU（最新使用的算法搀别，用LRU同樣的邏輯但不同的規(guī)則）

* LRFU（Least Recently and Frequently Used，**最近最少使用最近最不常用**）

* ……

#### 寫(xiě)緩沖區(qū)

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

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

### 事務(wù)管理器

最后但同樣重要的，是事務(wù)管理器檐春，我們將看到這個(gè)進(jìn)程是如何保證每個(gè)查詢?cè)谧约旱氖聞?wù)內(nèi)執(zhí)行的逻淌。但開(kāi)始之前，我們需要理解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ù)約束）能寫(xiě)入數(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(niǎo)只得到50美元（這也是不一致?tīng)顟B(tài)）。

* 持久性確保如果 T1 剛剛提交间涵，數(shù)據(jù)庫(kù)就發(fā)生崩潰仁热，T1 不會(huì)消失得無(wú)影無(wú)蹤。

* 一致性確保錢(qián)不會(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í)別可以由用戶/開(kāi)發(fā)者在建立連接時(shí)覆蓋（只需要增加很簡(jiǎn)單的一行代碼）决摧。

#### 并發(fā)控制

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

* 如果所有事務(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開(kāi)銷(xiāo)很大的優(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ù)加上共享鎖。

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209485365007.jpg)

鎖管理器是添加和釋放鎖的進(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ù)：

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209485562407.jpg)

在本圖中：

* 事務(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ù)開(kāi)始時(shí)獲取鎖，結(jié)束時(shí)釋放鎖绢片。就是說(shuō)滤馍，事務(wù)開(kāi)始前必須等待確保自己能加上所有的鎖，當(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ù)）等舔，但不能獲得新鎖倦炒。

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209486479567.jpg)

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

釋放不再使用的鎖，來(lái)降低其它事務(wù)的等待時(shí)間

防止發(fā)生這類(lèi)情況：事務(wù)最初獲得的數(shù)據(jù)软瞎，在事務(wù)開(kāi)始后被修改逢唤，當(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)，涉及到更多類(lèi)型的鎖（比如意向鎖伍茄，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ì)阻塞寫(xiě)事務(wù)

* 寫(xiě)事務(wù)不會(huì)阻塞讀

* 沒(méi)有『臃腫緩慢』的鎖管理器帶來(lái)的額外開(kāi)銷(xiāo)

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

數(shù)據(jù)版本控制和鎖機(jī)制是兩種不同的見(jiàn)解：**樂(lè)觀鎖和悲觀鎖**告丢。兩者各有利弊枪蘑，完全取決于使用場(chǎng)景（讀多還是寫(xiě)多）。關(guān)于數(shù)據(jù)版本控制岖免，我推薦[這篇非常優(yōu)秀的文章](http://momjian.us/main/writings/pgsql/mvcc.pdf)岳颇，講的是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)告訴我）闯参。

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

Firebird 和 Interbase 用不帶鎖的版本控制瞻鹏。

版本控制對(duì)索引的影響挺有趣的：有時(shí)唯一索引會(huì)出現(xiàn)重復(fù)，索引的條目會(huì)多于表行數(shù)鹿寨，等等新博。

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

當(dāng)然，你總是可以自己去主流數(shù)據(jù)庫(kù)（像[MySQL](http://dev.mysql.com/doc/refman/5.7/en/innodb-transaction-model.html), [PostgreSQL](http://www.postgresql.org/docs/9.4/static/mvcc.html) 或 [Oracle](http://docs.oracle.com/cd/B28359_01/server.111/b28318/consist.htm#i5337)）的文檔里查一下埂淮。

日志管理器

我們已經(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ù)都寫(xiě)在磁盤(pán)上叮盘，但是如果服務(wù)器崩潰，最終數(shù)據(jù)可能只有部分寫(xiě)入磁盤(pán)霹俺，這破壞了事務(wù)的原子性柔吼。

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

有 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ǔ)空間侧甫，在每次寫(xiě)盤(pán)之前珊佣，數(shù)據(jù)庫(kù)在事務(wù)日志中寫(xiě)入一些信息，這樣當(dāng)事務(wù)崩潰或回滾披粟，數(shù)據(jù)庫(kù)知道如何移除或完成尚未完成的事務(wù)咒锻。

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

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

多數(shù)數(shù)據(jù)庫(kù)（至少是Oracle, [SQL Server](https://technet.microsoft.com/en-us/library/ms186259(v=sql.105).aspx), [DB2](http://www.ibm.com/developerworks/data/library/techarticle/0301kline/0301kline.html), PostgreSQL, MySQL 和 [SQLite](https://www.sqlite.org/wal.html)) 使用**預(yù)寫(xiě)日志協(xié)議**（Write-Ahead Logging protocol ，WAL）來(lái)處理事務(wù)日志俺叭。WAL協(xié)議有 3 個(gè)規(guī)則：

* 1) 每個(gè)對(duì)數(shù)據(jù)庫(kù)的修改都產(chǎn)生一條日志記錄恭取，在數(shù)據(jù)寫(xiě)入磁盤(pán)之前日志記錄必須寫(xiě)入事務(wù)日志。

* 2) 日志記錄必須按順序?qū)懭胄饔保挥涗?A 發(fā)生在記錄 B 之前秽荤，則 A 必須寫(xiě)在 B 之前甜奄。

* 3) 當(dāng)一個(gè)事務(wù)提交時(shí)，在事務(wù)成功之前窃款，提交順序必須寫(xiě)入到事務(wù)日志课兄。

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209488947467.jpg)

這個(gè)工作由日志管理器完成。簡(jiǎn)單的理解就是晨继，日志管理器處于緩存管理器（cache manager）和數(shù)據(jù)訪問(wèn)管理器（data access manager烟阐，負(fù)責(zé)把數(shù)據(jù)寫(xiě)入磁盤(pán)）之間，每個(gè) update / delete / create / commit / rollback 操作在寫(xiě)入磁盤(pán)之前先寫(xiě)入事務(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)題在于，如何找到寫(xiě)日志的同時(shí)保持良好的性能的方法藏鹊。如果事務(wù)日志寫(xiě)得太慢润讥，整體都會(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這門(mén)課](http://db.csail.mit.edu/6.830/lectures/lec15-notes.pdf)的說(shuō)法冠绢，IBM 的研究人員『僅僅是寫(xiě)了事務(wù)恢復(fù)的最佳實(shí)踐方法』抚吠。AIRES 論文發(fā)表的時(shí)候我才 5 歲常潮，我不關(guān)心那些酸溜溜的科研人員老掉牙的閑言碎語(yǔ)。事實(shí)上楷力，我提及這個(gè)典故喊式，是在開(kāi)始探討最后一個(gè)技術(shù)點(diǎn)前讓你輕松一下。我閱讀過(guò)[這篇 ARIES 論文](http://www.cs.berkeley.edu/~brewer/cs262/Aries.pdf) 的大量篇幅萧朝，發(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) 寫(xiě)日志的同時(shí)保持良好性能

* 2) 快速和可靠的數(shù)據(jù)恢復(fù)

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

* 因?yàn)橛脩羧∠?/p>

* 因?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ù)在磁盤(pán)上的位置。磁盤(pán)數(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ō)，磁盤(pán)上每個(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í)行的笋除。【譯者注： SQL 語(yǔ)句原文如此炸裆，應(yīng)該是作者筆誤】

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209490069029.jpg)

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

##### 日志緩沖區(qū)

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

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209490253214.jpg)

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

* 1) 緩存管理器將修改存入自己的緩沖區(qū)惯殊；

* 2) 日志管理器將相關(guān)的日志存入自己的緩沖區(qū)酱吝；

* 3) 到了這一步，查詢執(zhí)行器認(rèn)為操作完成了（因此可以請(qǐng)求做另一次修改）土思；

* 4) 接著（不久以后）日志管理器把日志寫(xiě)入事務(wù)日志务热，什么時(shí)候?qū)懭罩居赡乘惴▉?lái)決定。

* 5) 接著（不久以后）緩存管理器把修改寫(xiě)入磁盤(pán)己儒，什么時(shí)候?qū)懕P(pán)由某算法來(lái)決定崎岂。

**當(dāng)事務(wù)提交，意味著事務(wù)每一個(gè)操作的 1 2 3 4 5 步驟都完成了**闪湾。寫(xiě)事務(wù)日志是很快的冲甘，因?yàn)樗皇恰涸谑聞?wù)日志某處增加一條日志』；而數(shù)據(jù)寫(xiě)盤(pán)就更復(fù)雜了途样，因?yàn)橐谩耗軌蚩焖僮x取的方式寫(xiě)入數(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ù)是一步步的寫(xiě)入（STEAL策略）**遏插，還是緩沖管理器需要等待提交命令來(lái)一次性全部寫(xiě)入（NO-STEAL策略）捂贿。選擇STEAL還是NO-STEAL取決于你想要什么：快速寫(xiě)入但是從 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ò)程開(kāi)始了。

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

* 1) 分析階段：恢復(fù)進(jìn)程讀取全部事務(wù)日志餐济，來(lái)重建崩潰過(guò)程中所發(fā)生事情的時(shí)間線耘擂，決定哪個(gè)事務(wù)要回滾（所有未提交的事務(wù)都要回滾）、崩潰時(shí)哪些數(shù)據(jù)需要寫(xiě)盤(pán)絮姆。

* 2) Redo階段：這一關(guān)從分析中選中的一條日志記錄開(kāi)始醉冤，使用 REDO 來(lái)將數(shù)據(jù)庫(kù)恢復(fù)到崩潰之前的狀態(tài)巴帮。

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

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

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

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

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

* 3) Undo階段：這一階段回滾所有崩潰時(shí)未完成的事務(wù)浅乔【笪梗回滾從每個(gè)事務(wù)的最后一條日志開(kāi)始，并且按照時(shí)間倒序處理UNDO日志（使用日志記錄的PrevLSN）靖苇。

恢復(fù)過(guò)程中席噩，事務(wù)日志必須留意恢復(fù)過(guò)程的操作，以便寫(xiě)入磁盤(pán)的數(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ù)需要寫(xiě)入磁盤(pán)）

當(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寫(xiě)入磁盤(pán)盹舞。那么在分析階段當(dāng)中产镐，只需要分析這個(gè)LSN之后的日志即可。

## 結(jié)語(yǔ)

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

如果你想很好地了解數(shù)據(jù)庫(kù)兼丰，我推薦這篇研究論文：[《數(shù)據(jù)庫(kù)系統(tǒng)架構(gòu)》](http://db.cs.berkeley.edu/papers/fntdb07-architecture.pdf)玻孟，對(duì)數(shù)據(jù)庫(kù)有很好的介紹（共110頁(yè)），而且非計(jì)算機(jī)專(zhuān)業(yè)人士也能讀懂鳍征。這篇論文出色的幫助我制定了本文的寫(xiě)作計(jì)劃黍翎，它沒(méi)有像本文那樣專(zhuān)注于數(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ù)索引概述

* 數(shù)據(jù)庫(kù)的全局概述

* 基于成本的優(yōu)化概述碰酝，特別專(zhuān)注了聯(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)在你可以回答：

![](http://ovblf5i76.bkt.clouddn.com/2018-03-14-15209491940108.jpg)

或者乾忱，就讓他/她來(lái)看本文吧讥珍。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市窄瘟，隨后出現(xiàn)的幾起案子衷佃，更是在濱河造成了極大的恐慌，老刑警劉巖蹄葱，帶你破解...
沈念sama閱讀 216,324評(píng)論 6贊 498
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件氏义，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡图云，警方通過(guò)查閱死者的電腦和手機(jī)惯悠，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,356評(píng)論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)竣况，“玉大人克婶，你說(shuō)我怎么就攤上這事〉と” “怎么了情萤？”我有些...
開(kāi)封第一講書(shū)人閱讀 162,328評(píng)論 0贊 353
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)摹恨。經(jīng)常有香客問(wèn)我紫岩，道長(zhǎng)，這世上最難降的妖魔是什么睬塌？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,147評(píng)論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任泉蝌，我火速辦了婚禮，結(jié)果婚禮上揩晴，老公的妹妹穿的比我還像新娘勋陪。我一直安慰自己，他們只是感情好硫兰，可當(dāng)我...
茶點(diǎn)故事閱讀 67,160評(píng)論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布诅愚。她就那樣靜靜地躺著，像睡著了一般。火紅的嫁衣襯著肌膚如雪违孝。梳的紋絲不亂的頭發(fā)上刹前，一...
開(kāi)封第一講書(shū)人閱讀 51,115評(píng)論 1贊 296
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音雌桑，去河邊找鬼喇喉。笑死，一個(gè)胖子當(dāng)著我的面吹牛校坑，可吹牛的內(nèi)容都是我干的拣技。我是一名探鬼主播，決...
沈念sama閱讀 40,025評(píng)論 3贊 417
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼耍目，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼膏斤！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起邪驮，我...
開(kāi)封第一講書(shū)人閱讀 38,867評(píng)論 0贊 274
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤莫辨，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后毅访，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體沮榜，經(jīng)...
沈念sama閱讀 45,307評(píng)論 1贊 310
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,528評(píng)論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年俺抽，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了敞映。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 39,688評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡磷斧，死狀恐怖振愿，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情弛饭，我是刑警寧澤冕末，帶...
沈念sama閱讀 35,409評(píng)論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站侣颂，受9級(jí)特大地震影響档桃，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜憔晒，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,001評(píng)論 3贊 325
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一藻肄、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧拒担，春花似錦嘹屯、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 31,657評(píng)論 0贊 22
一樁弒父案州弟，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至，卻和暖如春婆翔，著一層夾襖步出監(jiān)牢的瞬間拯杠，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 32,811評(píng)論 1贊 268
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工啃奴，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留潭陪，地道東北人。一個(gè)月前我還...
沈念sama閱讀 47,685評(píng)論 2贊 368
代替公主和親
正文我出身青樓纺腊，卻偏偏與公主長(zhǎng)得像畔咧，于是被迫代替她去往敵國(guó)和親茎芭。傳聞我的和親對(duì)象是個(gè)殘疾皇子揖膜，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,573評(píng)論 2贊 353

2017-08-14

推薦閱讀更多精彩內(nèi)容