簡介

? ?SQL的查詢分為兩個過程希痴。一是SQL語句解析者甲，二是SQL語句執(zhí)行。第一個過程會將SQL涉及的操作進行分解砌创，并應(yīng)用一些代數(shù)理論虏缸，將查詢過程進行一些優(yōu)化，比如將選擇操作提前嫩实，這樣可以減少后續(xù)操作的數(shù)據(jù)量刽辙。第二個過程會根據(jù)關(guān)系的一些元數(shù)據(jù)和目前可用的內(nèi)存等參數(shù)，選擇合適的查詢算法甲献。本教程會詳細介紹SQL的各種查詢算法及適用場景扫倡。

? ? SQL查詢算法大致分為一趟算法，兩趟算法和多趟算法竟纳，一趟算法只需讀一次磁盤撵溃，但需要較多內(nèi)存。兩趟算法需要先讀一次磁盤锥累，在內(nèi)存中對數(shù)據(jù)進行某些處理后將處理的結(jié)果寫會磁盤缘挑，再讀取一次進行最終的處理。多躺算法和兩趟算法原理一致桶略，只不過需要更多次讀寫操作语淘，本教程重點描述一趟算法和兩趟算法。

為描述算法的性能和使用場景际歼，需要一些參數(shù)用于描述惶翻，主要有三個參數(shù)：

B(R):關(guān)系R的所有元組所需的塊的數(shù)目。

T(R):關(guān)系R的元組數(shù)目

?V(R,a)：關(guān)系R中a對應(yīng)列上不同值的數(shù)目

關(guān)系的操作符可以分為三大類鹅心，如下：

1 一次單個元組吕粗，一元操作。這類操作（選擇和投影）不需要一次在內(nèi)存中裝入整個關(guān)系旭愧，甚至也不需要關(guān)系的大部分颅筋。這樣宙暇，我們一次讀一個磁盤塊，使用內(nèi)存緩沖區(qū)產(chǎn)生輸出议泵。

2 整個關(guān)系占贫，一元操作。這類操作（分組和去重）需要一次從內(nèi)存中看到所有或大部分元組先口。

3 整個關(guān)系型奥，二元操作。這類操作比如交集碉京，并集厢汹，差集，連接等收夸。

一趟算法

一次單個元組

一次單個元組的選擇運算和投影運算較為簡單，一次讀取R的一個數(shù)據(jù)塊到內(nèi)存緩沖區(qū)即可血崭，無論B(R)有多大卧惜，我們只要求輸入緩沖區(qū)滿足即可,如下圖所示

整個關(guān)系的一元操作

消除重復(fù)

為了消除重復(fù)，我們可以一次一個的讀取R的每一塊夹纫，但對于每一個元組咽瓷，我們需要判定：

1 這是我們第一次看到這個元組，這是將它復(fù)制到輸出

2 我們從前沒見過這個元組舰讹，這時不必輸出它

如下圖所示茅姜，我們需要一個緩沖區(qū)來存儲關(guān)系R中的非重復(fù)元組，所以要求

分組

分組操作給我們零個或多個分組屬性以及可能的一個或多個聚集屬性月匣。如果我們在內(nèi)存中為每一個組創(chuàng)建一個項钻洒，我們就可以一次一塊地掃描R的元組，并根據(jù)每一個元組的值來更新對應(yīng)的聚集屬性锄开，常見的聚集屬性包括最小值素标，最大值，count萍悴，平均值等头遭。

整個關(guān)系的二元操作

關(guān)系的二元操作(R和S)包含并，交癣诱，差计维，積和連接。一般要求將一個較小的關(guān)系S讀入內(nèi)存撕予，另一個關(guān)系一次一塊的進行處理鲫惶，這樣只需要滿足即可

集合并

我們將S讀到內(nèi)存的M-1個緩沖區(qū)并建立一個查找結(jié)果，其查找關(guān)鍵字是整個元組实抡。所有這些元組也都將復(fù)制到輸出剑按。然后我們一次一塊的將R的每一塊讀到第M個緩沖區(qū)疾就。對于R的每一個元組t，我們觀察t是否在S中艺蝴，如果不在猬腰，我們就將t復(fù)制到輸出。如果t在S中猜敢，忽略即可姑荷。

集合交

將S讀到M-1個緩沖區(qū)并建立整個元組作為查找關(guān)鍵字的查找結(jié)果。讀取R的每一個塊缩擂，并且對R的每一個元組t鼠冕，觀察t是否也在S中，如果在胯盯，我們將t復(fù)制到輸出懈费，如果不在，則忽略t博脑。

集合差

將S讀到M-1個緩沖區(qū)并建立整個元組作為查找關(guān)鍵字的查找結(jié)果憎乙。

為計算R-S，我們讀取R的每一個塊并檢查塊中的每一個元組t叉趣。如果t在S中泞边，那么忽略t。如果t不在S中疗杉，則將t復(fù)制到輸出阵谚。

為計算S-R，我們讀取R的每一個塊烟具，并以此檢查每一個元組t梢什。如果t在S中，那么我們從內(nèi)存S的副本里刪除t朝聋，而如果t不在S中绳矩，不做任何處理。在考慮完R的每一個元組后玖翅，將S中剩余的元組復(fù)制到輸出翼馆。

包并

這個比較特殊，對R和S都一次一塊的進行處理金度，并將每一個元組都復(fù)制到輸出即可应媚。

包交

將S讀到M-1個緩沖區(qū)，我們把每一個不同的元組與一個計數(shù)聯(lián)系起來猜极，其初始值是該元組在S中出現(xiàn)的次數(shù)中姜。元組t的多個副本并不分別存儲。接著，我們讀取R的每一塊丢胚，并對R的每一個元組t翩瓜，我們觀察t是否在S中出現(xiàn)。如果不出現(xiàn)携龟，那么我們忽略t兔跌。如果t在S中出現(xiàn)，并且與t對應(yīng)的計數(shù)值仍為正值峡蟋，那么我們輸出t并將計數(shù)減1.如果t在S中出現(xiàn)坟桅，但是它的計數(shù)器已經(jīng)到0，那么我們?nèi)圆惠敵鰐蕊蝗。

包差

為計算S-R仅乓，我們將S的元組讀到內(nèi)存中，并統(tǒng)計每個不同元組出現(xiàn)的次數(shù)蓬戚。對R的每個元組t夸楣，觀察t是否在S中出現(xiàn)，如果是子漩，我們將對應(yīng)的計數(shù)減1.組后豫喧，我們將內(nèi)存中計數(shù)是正數(shù)的每一個元組復(fù)制到輸出，并且復(fù)制它的次數(shù)等于其計數(shù)痛单。

為計算R-S嘿棘，我們也將S復(fù)制到內(nèi)存劲腿，對R的每一個元組t旭绒，我們觀察t是否在S中出現(xiàn)。如果不出現(xiàn)焦人，我們將t復(fù)制到輸出挥吵。如果t確實在S中出現(xiàn)，那么我們看與t對應(yīng)的計數(shù)c的當(dāng)前值花椭。如果c=0忽匈，那么我們將t復(fù)制到輸出。如果c>0,那么不將t復(fù)制到輸出矿辽，但是將c值減1.

積

將S讀到內(nèi)存的M-1個緩沖區(qū)丹允，不需要特殊的數(shù)據(jù)結(jié)構(gòu)。然后讀取R的每一個塊袋倔，并且對R的每一個元組t粹湃，將t與內(nèi)存中S的每一個元組連接并輸出乾吻。

自然連接

假設(shè)R(X,Y)與S(Y,Z)連接。讀取S的所有元組，并且用它們構(gòu)造一個以Y的屬性為查找關(guān)鍵字的內(nèi)存查找結(jié)構(gòu)静袖，將內(nèi)存的M-1塊用于這一目的。將R的每一塊讀到剩下的一個緩沖區(qū)中，對R的每一個元組t，利用查找結(jié)構(gòu)找到S中與t在Y的所有屬性上相符合的元組承冰。對于S中每一個匹配的元組，將它與t連接后形成一個新的元組并輸出食零。

嵌套循環(huán)連接

該算法其實思路很簡單困乒，即嵌套循環(huán)遍歷兩個關(guān)系的所有元組。算法優(yōu)點是可以適用于任何大小的關(guān)系慌洪，沒必要有一個關(guān)系必須能裝入內(nèi)存中顶燕，具體來說，遍歷的時候可以按元組依次遍歷冈爹，也可以按塊依次遍歷涌攻，原理都一樣。按塊遍歷的算法如下：

分析一下上面的算法频伤，外層迭代次數(shù)書B(S)/M-1,每一次迭代時恳谎，我們讀取S的M-1個塊和R的B(R)個塊，總的磁盤讀取數(shù)量為B(S)(M-1+B(R))/(M-1),近似為B(S)B(R)/M.

迄今為止的算法總結(jié)如下：

基于排序的兩趟算法

原理是利用外部排序算法的思路憋肖，對一個很大的關(guān)系R（無法一次讀到內(nèi)存）進行排序因痛，排序過程中完成關(guān)系的各種操作，可大致分為兩個階段：

階段1:不斷將R中的元組放入M個緩沖區(qū)岸更，利用內(nèi)存排序算法對它們進行排序鸵膏，并將排序得到的子表存入磁盤

階段2:將排好序的字表進行歸并。在這個階段怎炊，最多能對M-1個有序字表進行歸并谭企，這就限制了R的大小。即需要滿足,或者近似為评肆。

該算法稱為兩階段多路歸并排序（Two-Phase债查，Multiway Merge-Sort），簡稱TPMMS瓜挽。

利用排序去除重復(fù)

采取上述TPMMS的思路盹廷，在第二趟中，我們不斷地復(fù)制每一塊的第一個未考慮的元組t到輸出久橙，并將輸入塊中所有的t刪除即可俄占。

利用排序進行分組和聚集

1 將R的元組每次讀取M塊到內(nèi)存，用L的分組屬性作為排序關(guān)鍵字淆衷，對每M塊排序缸榄，并將每一個排好序的子表寫到磁盤

2 為每一個子表使用一個內(nèi)存緩沖區(qū)，并首先將每一個子表的第一個塊裝入其緩沖區(qū)

3 在緩沖區(qū)可以獲得的第一個元組中反復(fù)查找關(guān)鍵字的最小值吭敢。這個最小值v稱為下一分組碰凶，我們?yōu)樗?/p>

a）準(zhǔn)備在這個分組的列表L上計算所有聚集

b）檢查每個排序關(guān)鍵字為v的元組，并且累計所需聚集

c）如果一個緩沖區(qū)空了，則用同一個子表的下一個塊替換它

d)當(dāng)不再有關(guān)鍵字為v的元組時欲低，輸出一個由L的分組屬性和對應(yīng)聚集值構(gòu)成的元組辕宏。

基于排序的并算法

1 在第一趟的時候，創(chuàng)建R和S的排序子表

2 為R和S的每一個子表使用一個內(nèi)存緩沖區(qū)砾莱，用對應(yīng)子表的第一塊初始化各緩沖區(qū)

3 重復(fù)地在所有緩沖區(qū)中查找剩余的第一個元組t瑞筐。將t復(fù)制到輸出，并從緩沖區(qū)刪除t的所有副本腊瑟。

基于排序的交和差算法

大體思路都是一樣的聚假，具體差異如下：

對于集合交，如果t在R和S中同時出現(xiàn)就輸出t

對于包交闰非，輸出t的次數(shù)是它在R和S中出現(xiàn)的最小次數(shù)

對于集合差膘格，R-S，當(dāng)其僅當(dāng)t出現(xiàn)在R中但不在S中時輸出t

對于包差财松，R-S瘪贱，輸出t的次數(shù)是t在R中出現(xiàn)的次數(shù)減去S中出現(xiàn)的次數(shù)

基于排序的連接算法

1 用R和S的公共屬性Y作為排序關(guān)鍵字，用TPMMS對R進行排序

2 用TPMMS對S進行排序

3 歸并排好序的R和S辆毡，我們需要兩個緩沖區(qū)

a）在當(dāng)前R和S的塊的前端尋找Y的最小值y

b）如果y在另一個關(guān)系中沒有出現(xiàn)菜秦，刪除關(guān)鍵字為Y的元組

c）否則，找出兩個關(guān)系中關(guān)鍵字為y的所有元組舶掖。

d）輸出通過連接R和S中拒用共同y值的元組

e）如果一個關(guān)系在內(nèi)存中已沒有未考慮的元組球昨，就重新加載一個新的塊

上述算法的磁盤I/O數(shù)為5 * (B(R)+B(S)),實際上，如果內(nèi)存夠大眨攘，可以將兩個關(guān)系一起在內(nèi)存中用TPMMS進行排序主慰，排序后直接對所有塊進行歸并操作，沒必要將關(guān)系再寫會磁盤期犬，這樣磁盤I/O數(shù)會變成3*(B(R)+B(S))

基于排序的算法總結(jié)如下：

基于散列的兩趟算法

基于散列的算法和基于排序的方法類似河哑，也是將關(guān)系R分成很多小的關(guān)系來單獨處理避诽，但散列不會對這些子關(guān)系進行排序龟虎，而是將其散列到不同的桶中，因為散列函數(shù)是根據(jù)關(guān)鍵字計算的沙庐，所有有相同關(guān)鍵字的元組都在一個桶中鲤妥，這樣就可以一次一個桶進行處理。只要一個桶的元組數(shù)目小到能裝入內(nèi)存拱雏，我們就可以用一趟算法來處理相應(yīng)的操作棉安，不再贅述，相應(yīng)操作的性能如下：

基于索引的兩趟算法

如果一個關(guān)系的元組緊縮到能存儲這些元組的盡可能少的塊中铸抑，那么這個關(guān)系就是“聚簇”的贡耽，我們迄今為止所做的分析都假設(shè)關(guān)系是“聚簇”的。假如關(guān)系R上有一個索引，如果該索引某個固定值的所有元組都出現(xiàn)在能容納它們的盡可能少的塊中蒲赂，則稱該索引為聚簇索引阱冶。請注意一個非聚簇的關(guān)系不能夠有一個聚簇索引，但一個聚簇的關(guān)系可以有非聚簇索引滥嘴。

基于索引的選擇

如果R沒有索引木蹬，那么選擇操作的磁盤I/O最好只能是B(R)。如果R不是一個聚簇的關(guān)系若皱，磁盤I/O甚至可能是T(R)镊叁。對于特定值的查詢，如果這個屬性正好有索引并且是聚簇的走触，需要的磁盤I/O為B(R)/V(R,a);如果是非聚簇的晦譬，需要的磁盤I/O為T(R)/V(R,a)

基于索引的連接

考慮R(X,Y)和S(Y，Z),假設(shè)S有一個屬性Y的索引互广，那么計算這個連接的一種方式是檢查R的每一個塊蛔添，并考慮R中的每一個元組t，利用索引找到與t對應(yīng)的元組并進行連接操作兜辞。假設(shè)R是聚簇的迎瞧，我們需要B(R)次磁盤I/O來獲取R的所有元組，如果是非聚簇的逸吵，則需要T(R)次磁盤I/O凶硅。對R的每一個元組，我們必須讀取S的T(S)/V(S,Y)個元組扫皱。如果S在Y上有一個非聚簇的索引足绅，則需要的磁盤I/O為T(R)T(S)/V(S,Y);如果S在Y上有一個聚簇索引，則需要的磁盤I/O為T(R)B(S)/V(S,Y)韩脑。

假如R和S在Y上的索引都是有序的氢妈，只需依次順序讀取兩個關(guān)系的所有塊進行比較即可，磁盤I/O為B(R)+B(S);如果只有一個關(guān)系上的索引是有序的段多，可以對另一個關(guān)系先用TPMMS算法進行排序并寫會首量，然后再一起進行merge，效率也非常高进苍。