[讀書筆記](méi)《數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)》第4章查詢執(zhí)行

數(shù)據(jù)查詢處理

4.1 物理查詢計(jì)劃操作符介紹

物理查詢計(jì)劃由操作符構(gòu)成，每一個(gè)操作符實(shí)現(xiàn)計(jì)劃中的一步检访。物理操作符通常是一個(gè)關(guān)系代數(shù)操作符的特定實(shí)現(xiàn)慈省。

4.1.1 掃描表

讀關(guān)系R的整個(gè)內(nèi)容读存。

表掃描：順序讀塊微姊，一個(gè)接一個(gè)的讀取。
索引掃描：讀索引烫映，根據(jù)索引找到塊沼本，然后讀取。

4.1.2 掃描表時(shí)的排序

為啥要排序锭沟？其一抽兆，sql有order by，要求對(duì)關(guān)系排序族淮；其二辫红，很多關(guān)系代數(shù)操作算法要求數(shù)據(jù)是有序的。
如何實(shí)現(xiàn)排序呢祝辣？如按屬性a對(duì)關(guān)系R進(jìn)行排序贴妻。

如關(guān)系本身是按屬性a建立的索引，如B+樹索引或者其它按a排序的索引较幌，那么直接掃描即可
如排序的關(guān)系R很小揍瑟，則可以先進(jìn)行表掃描讀取到內(nèi)存中，然后內(nèi)存排序
如排序的關(guān)系R很大乍炉，無(wú)法一次全部load到內(nèi)存中绢片，則可以進(jìn)行多路歸并排序

4.1.3 物理操作符計(jì)算模型

如何估計(jì)每個(gè)操作符的代價(jià)呢？由于從磁盤中得到數(shù)據(jù)的時(shí)間比從內(nèi)存中大的多岛琼，因此底循，使用磁盤IO的數(shù)目作為衡量每個(gè)操作的代價(jià)標(biāo)準(zhǔn)。
另外槐瑞，有一個(gè)假設(shè)熙涤。假設(shè)，任何操作符的操作對(duì)象都位于磁盤上困檩，但操作符的結(jié)果放在內(nèi)存中祠挫。

4.1.4 衡量代價(jià)的參數(shù)

有以下三個(gè)參數(shù)

關(guān)系數(shù)據(jù)庫(kù)數(shù)據(jù)B。我們關(guān)心包含R的所有元組所需的塊的數(shù)目悼沿，這個(gè)塊的數(shù)目表示成B(R)等舔，如果我們知道指的是關(guān)系R，則可以表示成B糟趾。通常慌植，假設(shè)R是聚集的，因此R存儲(chǔ)在B個(gè)塊中义郑。
元組條數(shù)T蝶柿。關(guān)系R的所有元組條數(shù)為T，那么一個(gè)塊中的元組個(gè)數(shù)為T/B非驮。關(guān)系中數(shù)據(jù)的多少交汤。
字段不同值的個(gè)數(shù)V。關(guān)系中數(shù)據(jù)的分布劫笙。

我們需要用一個(gè)參數(shù)來(lái)表達(dá)操作符使用的內(nèi)存大小芙扎，假設(shè)內(nèi)存被分成緩沖區(qū)，緩沖區(qū)的大小與磁盤塊的大小相同邀摆。那么M表示一個(gè)特定的操作符執(zhí)行時(shí)可以獲得的內(nèi)存緩沖區(qū)的數(shù)目纵顾。

4.1.5 掃描操作符的IO代價(jià)

如果關(guān)系R是聚集的，那么表掃描操作符的磁盤IO數(shù)目近似為B栋盹。
如果關(guān)系R不是聚集的施逾，那么表掃描操作符的磁盤IO數(shù)目可能退化為T。

4.1.6 實(shí)現(xiàn)物理操作符的迭代器

許多物理操作符可以實(shí)現(xiàn)為迭代器例获。迭代器是三個(gè)方法的集合汉额，這三個(gè)方法允許物理操作符結(jié)果的使用者一次一個(gè)元組地得到這個(gè)結(jié)果。

Open()
GetNext()
Close()

為什么要使用迭代器榨汤？
迭代器與物化策略相反蠕搜，物化策略產(chǎn)生每個(gè)操作符的整個(gè)結(jié)果，或者將它存放在磁盤上收壕，或者允許它在內(nèi)存中占據(jù)空間妓灌。在使用迭代器時(shí)轨蛤，同一時(shí)刻活躍的操作有很多。元組按需要在操作符之間傳遞虫埂，這樣就減少了存儲(chǔ)要求祥山。但是，并非所有物理操作符對(duì)迭代方法或流水線的支持都是有意義的掉伏。在某些情況下缝呕，幾乎所有的工作都需要Open方法來(lái)完成，這就等效于物化方法了斧散。

4.2 一趟算法

怎么執(zhí)行邏輯查詢計(jì)劃中的每個(gè)單獨(dú)步驟供常？每一個(gè)操作符的算法是將邏輯查詢計(jì)劃轉(zhuǎn)變成物理查詢計(jì)劃過(guò)程中一個(gè)必不可少的部分。
關(guān)于各種操作符已提出很多算法鸡捐，大體上分為三類：

基于排序的方法
基于散列的方法
基于索引的方法

按照代價(jià)栈暇，可以分為三種：

一趟算法。僅從磁盤讀取一次數(shù)據(jù)闯参，要求操作的至少一個(gè)對(duì)象能完成裝入內(nèi)存
兩趟算法瞻鹏。數(shù)據(jù)量大，以至于不能裝入內(nèi)存鹿寨。特點(diǎn)是新博，先從磁盤讀一遍數(shù)據(jù)，用某種方式處理后脚草，將全部或絕大部分寫回磁盤赫悄，然后在第二趟中為了進(jìn)一步處理，再讀取一遍數(shù)據(jù)馏慨。
多趟算法埂淮。

操作符類型，可以分為三種：

一次單個(gè)元組写隶，一元操作倔撞。如選擇，投影慕趴，一次讀取一個(gè)元組痪蝇，就可以進(jìn)行處理
整個(gè)關(guān)系，一元操作冕房。如分組操作和去重操作
整個(gè)關(guān)系躏啰，二元操作。如并耙册，交给僵，差，連接和積的集合形式以及包形式详拙。

4.2.1 一次的單個(gè)元組操作的一趟算法

如選擇和投影操作帝际。
一次讀取R的一塊到輸入緩沖區(qū)蔓同，對(duì)每一個(gè)元組進(jìn)行操作，并將選出的元組或投影得到的元組移至輸出緩沖區(qū)胡本。無(wú)論關(guān)系R有多少塊B牌柄，只要內(nèi)存中有一個(gè)輸入緩沖區(qū)就可以畸悬，即M≥1侧甫。

4.2.2 整個(gè)關(guān)系的一元操作的一趟算法

如去重和分組聚合操作。

去重

一次一個(gè)地讀取R的每一塊蹋宦，對(duì)每一個(gè)元組：

第一次看到這個(gè)元組披粟，這時(shí)將它復(fù)制到輸出；
之前見(jiàn)到過(guò)這個(gè)元組冷冗，就不用復(fù)制到輸出了守屉。

關(guān)鍵是如何判斷元組是否見(jiàn)到過(guò)，可以采用具有大量桶的散列表蒿辙，或者某種形式的平衡二叉查找樹拇泛。

分組

分組操作，有零個(gè)或者多個(gè)分組屬性思灌，一個(gè)或多個(gè)聚集屬性俺叭。如下sql，user_id就是分組屬性泰偿，money就是聚集屬性熄守。在內(nèi)存中為每一個(gè)組（分組屬性的每一個(gè)值，如本例中的張三耗跛，李四）創(chuàng)建一個(gè)項(xiàng)裕照，我們可以一次一塊地掃描R的元組。每個(gè)組的項(xiàng)包括分組屬性的值和每個(gè)聚集的一個(gè)或多個(gè)累計(jì)值调塌。如

MIN和MAX操作晋南，比大小，每次處理一個(gè)元組時(shí)羔砾，如果合適负间，就更新這個(gè)值
COUNT操作，每次處理一個(gè)元組時(shí)蜒茄，就累加1
SUM操作唉擂，累加屬性值
AVG操作，保持兩個(gè)累加值檀葛，一個(gè)是個(gè)數(shù)玩祟，一個(gè)是屬性累加值，待關(guān)系讀取完后屿聋，計(jì)算均值

select user_id, sum(money) from salary group by user_id

4.2.3 二元操作的一趟算法

如并空扎，交藏鹊，差，積和連接转锈。
假設(shè)R和S兩個(gè)關(guān)系盘寡，R是數(shù)據(jù)較多的關(guān)系，S是數(shù)據(jù)較少的關(guān)系撮慨。將較少數(shù)據(jù)的S讀取到內(nèi)存中竿痰，并建立合適的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)（散列or平衡樹）要求元組可以快速插入砌溺，還可以快速檢索影涉。

集合并

將S讀取到內(nèi)存中并建立查找結(jié)構(gòu)。所有這些元組都復(fù)制到輸出规伐。然后一次讀取R的一個(gè)塊蟹倾，對(duì)于R的每一個(gè)元組，在內(nèi)存中判斷是否在S中猖闪，如果不在鲜棠，則復(fù)制到輸出，否則培慌，跳過(guò)豁陆。

集合交

與集合并唯一的不同時(shí)，不將S的元素都復(fù)制到輸出检柬。

集合差

將S讀取到內(nèi)存中并建立查找結(jié)構(gòu)献联。需考慮兩種情況：

R - S情況。一次讀取R的一個(gè)塊何址，檢查每個(gè)元組里逆，如果元組不在S中，則復(fù)制到輸出用爪，否則原押，不處理。
S - R情況偎血。一個(gè)讀取R的一個(gè)塊诸衔，檢查每個(gè)元組，如果元組在S中颇玷，則從S的內(nèi)存副本中刪除元組笨农，否則，不處理帖渠。最后留在S中的元組谒亦，全部復(fù)制到輸出。

積

笛卡爾積操作。將S讀取到內(nèi)存份招，不需要建立特殊的數(shù)據(jù)結(jié)構(gòu)切揭，因?yàn)椴恍枰M(jìn)行查找操作。
然后讀取R的每一個(gè)塊锁摔，并對(duì)塊中的每一個(gè)元組廓旬，與內(nèi)存中的S的每一個(gè)元組連接。輸出每一個(gè)連接而成元組谐腰。

4.3 嵌套循環(huán)連接

一趟半算法孕豹，兩個(gè)操作對(duì)象中有有一個(gè)元組僅讀取一次，另一個(gè)操作對(duì)象將重復(fù)讀取怔蚌。嵌套循環(huán)連接可以用于任何大小的關(guān)系巩步，不要求有一個(gè)關(guān)系必須能裝入內(nèi)存中。

4.3.1 基于元組的嵌套循環(huán)連接

嵌套循環(huán)連接中最簡(jiǎn)單的形式桦踊。計(jì)算R(X,Y)與S(Y,Z)的連接，邏輯如下

for(元組a in S){
  for(元組b in R){
    if(元組 a 和元組 b能形成元組t){
      則輸出t
    }  
  }
}

4.3.2 基于元組的嵌套循環(huán)連接的迭代器

適合用于迭代器結(jié)構(gòu)终畅。

4.3.3 基于塊的循環(huán)嵌套連接算法

假設(shè)S和R籍胯，每個(gè)關(guān)系都不能一次性全部加載到內(nèi)存，S是塊數(shù)較小的關(guān)系离福。則先將S的若干塊加載到內(nèi)存中杖狼，并建立查找結(jié)構(gòu)。然后將R的塊依次加載到內(nèi)存妖爷，并判斷R中的元組能否與S中的元組建立連接蝶涩，能則輸出，不能則跳過(guò)絮识。外層循環(huán)是塊數(shù)少的S绿聘，內(nèi)層要循環(huán)多次，即R要處理多次次舌。

4.4 基于排序的兩趟算法

兩趟算法熄攘，來(lái)自操作對(duì)象關(guān)系中的數(shù)據(jù)被讀到內(nèi)存，以某種方式處理彼念，再寫會(huì)磁盤挪圾，然后重新讀取磁盤以完成操作。為什么要這樣做逐沙？因?yàn)閿?shù)據(jù)量的關(guān)系哲思，太大了以至于無(wú)法全部一次性load進(jìn)入內(nèi)存中。
例如吩案，關(guān)系R可以被分成M個(gè)子表棚赔，每個(gè)字表可以再被分為M個(gè)緩沖區(qū)，內(nèi)存有M個(gè)緩存區(qū)，因此第一趟忆嗜，先對(duì)單獨(dú)的子表進(jìn)行排序己儒，第二趟，對(duì)所有的子表捆毫，先取子表的第一塊到內(nèi)存中闪湾，歸并排序。這樣就實(shí)現(xiàn)了绩卤，無(wú)法一次load這么多數(shù)據(jù)途样，但是依然可以對(duì)整體進(jìn)行排序。

4.4.1 兩階段多路歸并排序

兩階段多路歸并排序濒憋，算法如下

找到所有子表的第一個(gè)元素的最小值何暇，可以使用優(yōu)先隊(duì)列（堆）結(jié)構(gòu)實(shí)現(xiàn)
將最小元素移到輸出塊的第一個(gè)可用位置
如果輸出塊滿了，則溢出到磁盤存儲(chǔ)凛驮，重新創(chuàng)建一個(gè)輸出塊
如果輸入緩沖區(qū)的塊的數(shù)據(jù)被移除完了裆站，則用該子表的下一個(gè)數(shù)據(jù)塊（有序）來(lái)補(bǔ)充，如果子表讀取完了黔夭，則該輸入緩沖區(qū)為空

復(fù)雜度宏胯，第一遍讀取一次磁盤塊B(R)，寫一次磁盤塊B(R)本姥，第二遍肩袍，讀取一次磁盤塊B(R)，總計(jì)3B(R)次磁盤IO婚惫，而且要求B(R)<=M*M氛赐。

4.4.2 利用排序去重

與上述算法類似，第一遍先排序先舷，形成多個(gè)有序子表艰管；區(qū)別在于第二遍，在可用內(nèi)存中為每個(gè)有序子表分配一個(gè)緩沖塊密浑，并保存一個(gè)輸出緩沖塊蛙婴。遍歷每一塊的第一個(gè)元組，然后判斷該元組是否在輸出緩沖塊中尔破，如果在了吨铸，則忽略掉該元組腥光，并刪除掉子表中所有屬性值與該元組相同的元組漩怎。當(dāng)內(nèi)存輸入緩沖塊為空后趣竣，將該緩沖塊所屬子表的后續(xù)數(shù)據(jù)庫(kù)，加載到內(nèi)存胆剧，進(jìn)行處理絮姆；如果子表的數(shù)據(jù)塊都處理完成醉冤，則該內(nèi)存空間為空。當(dāng)輸出緩沖塊寫滿后篙悯，就溢出到磁盤蚁阳。
復(fù)雜度，第一遍讀取一次磁盤塊B(R)鸽照，寫一次磁盤塊B(R)螺捐，第二遍，讀取一次磁盤塊B(R)矮燎，總計(jì)3B(R)次磁盤IO定血，而且要求B(R)<=M*M。

4.4.3 利用排序進(jìn)行分組和聚集

邏輯如下

第一遍诞外，讀取R澜沟，可以Load進(jìn)入M個(gè)緩沖塊到內(nèi)存。然后根據(jù)分組字段對(duì)這些緩沖塊單獨(dú)排序峡谊，將每一個(gè)排好序的子表寫到磁盤茫虽。
第二遍，重新load排好序的子表靖苇，M個(gè)緩存塊對(duì)應(yīng)M個(gè)子表
在緩存塊中可以獲得的每一個(gè)元組中反復(fù)查找排序關(guān)鍵字的最小值席噩。這個(gè)最小值v成為下一分組。
a) 準(zhǔn)備在這個(gè)分組的列表L上計(jì)算所有的聚集贤壁，如計(jì)數(shù)和求和來(lái)代替平均。
b) 檢查每個(gè)排序關(guān)鍵字為v的元組埠忘，并累計(jì)所需的聚集脾拆。
c) 如果一個(gè)緩沖區(qū)空了，則用同一個(gè)子表的下一個(gè)塊替代它莹妒。

當(dāng)不在有排序關(guān)鍵字v的元組時(shí)名船，輸出一個(gè)有L的分組屬性和對(duì)應(yīng)的聚集值構(gòu)成的元組。
復(fù)雜度旨怠，第一遍讀取一次磁盤塊B(R)渠驼，寫一次磁盤塊B(R)，第二遍鉴腻，讀取一次磁盤塊B(R)迷扇，總計(jì)3B(R)次磁盤IO，而且要求B(R)<=M*M爽哎。

4.4.4 基于排序的并

第一趟蜓席，創(chuàng)建R和S的排序子表
為R和S的每個(gè)子表使用一個(gè)內(nèi)存緩沖區(qū)，用對(duì)應(yīng)子表的每一塊初始化各緩沖區(qū)
重復(fù)地在所有緩沖區(qū)中查找剩余塊的第一個(gè)元組课锌。將元組復(fù)制到輸出厨内，并從緩沖區(qū)中刪除元組所有的副本。當(dāng)輸入緩沖區(qū)變空或者輸出緩沖變滿時(shí)，采用與2PMMS相同的方式進(jìn)行處理雏胃。

需要讀取3（B(R)+B(S)）次磁盤IO

4.4.5 基于排序的交和差算法

與4.4.4基本相同请毛，區(qū)別的一點(diǎn)在于如何處理排序子表前部的元組t的副本。

交瞭亮，如果元組在R和S中都出現(xiàn)方仿，就輸出
差，R-S街州，當(dāng)且僅當(dāng)兼丰，t出現(xiàn)在R，但t沒(méi)出現(xiàn)在S中唆缴，才會(huì)輸出