查詢執(zhí)行流水線法(數(shù)據(jù)庫)

時間：2022-12-14 12:30:01 | 來源：信息時代

時間：2022-12-14 12:30:01 來源：信息時代

    查詢執(zhí)行流水線法 : 執(zhí)行查詢計劃的一種方法。在查詢計劃樹的執(zhí)行過程中,子結(jié)點向父結(jié)點傳遞中間結(jié)果可有兩種方式: 實體化方式和流水線方式。當(dāng)內(nèi)存不足時,或父子操作符之間存在天然的阻塞關(guān)系時,子結(jié)點需要以實體化方式向父結(jié)點傳遞中間結(jié)果,即子結(jié)點的輸出結(jié)果將以臨時文件形式寫到磁盤上,父結(jié)點去磁盤上讀數(shù)據(jù)。子結(jié)點以流水線方式向父結(jié)點傳遞中間結(jié)果時,子結(jié)點操作符的輸出將寫到內(nèi)存緩沖區(qū)中,父結(jié)點操作符從緩沖區(qū)讀數(shù)據(jù),父子操作符可以并行執(zhí)行,而不必等待子操作符執(zhí)行結(jié)束。
查詢執(zhí)行的流水線過程可以分為需求驅(qū)動的流水線(demand-driven pipeline)和生產(chǎn)者驅(qū)動的流水線(producer-driven pipeline)兩種方式。需求驅(qū)動的流水線比生產(chǎn)者驅(qū)動的流水線更容易實現(xiàn),因而使用更廣泛。
需求驅(qū)動流水線執(zhí)行方式是一種自頂向下的執(zhí)行方式。系統(tǒng)反復(fù)地向流水線頂端的操作符發(fā)出需求元組的請求。每當(dāng)一個操作符收到需要元組的請求時,就計算下一個(幾個)元組并返回這些元組。若該操作符的輸入不是來自流水線,則下一個(幾個)元組可以由輸入關(guān)系中計算得到,同時系統(tǒng)記錄目前為止已返回了哪些元組。若該操作符的某個輸入來自流水線,那么該操作符也發(fā)出需求元組的請求以獲得來自流水線輸入的元組。使用來自流水線輸入的元組時,子操作符計算輸出元組,然后把它們傳給父操作符。
生產(chǎn)者驅(qū)動流水線是一種自底向上的執(zhí)行方式,各操作符并不等待元組請求,而是積極主動地產(chǎn)生元組。流水線底部的每個操作符不斷地產(chǎn)生元組并將它們放在輸出緩沖區(qū)中,直到緩沖區(qū)滿為止。流水線中任何其他層的操作符只要獲得較低層的輸入元組就產(chǎn)生輸出元組,直到其輸入緩沖區(qū)為空或輸出緩沖區(qū)充滿為止。一個操作符使用流水線輸入的一條元組后,將其從輸入緩沖區(qū)中刪除。一旦輸出緩沖區(qū)已滿或輸入緩沖區(qū)已空,操作符必須等待,直到其父操作符將元組從該緩沖區(qū)取走,或子操作符產(chǎn)生新的輸出元組。此時,該操作符接著產(chǎn)生更多的元組,直到輸出緩沖區(qū)再次滿了或輸入緩沖區(qū)再次空了為止。這個過程不斷重復(fù),直到該操作符產(chǎn)生所有的輸出元組為止。只有當(dāng)一個輸出緩沖區(qū)已滿或一個輸入緩沖區(qū)已空時,系統(tǒng)才需要在各操作符之間切換。在一個并行處理系統(tǒng)中,流水線中的操作符可在不同的處理器上并行執(zhí)行。
使用生產(chǎn)者驅(qū)動的流水線方法可以看成將數(shù)據(jù)從一棵操作符樹的底層推(push)上去的過程;而使用需求驅(qū)動的流水線方法可看成是從樹頂將數(shù)據(jù)拉(pull)上來的過程。在生產(chǎn)者驅(qū)動流水線中,元組的產(chǎn)生是積極的; 而在需求驅(qū)動流水線中,元組消極地(lazily)按需求產(chǎn)生。
需求驅(qū)動的流水線中的每個操作符可以用迭代器(iterator)來實現(xiàn),迭代器由三個函數(shù)組成: Open、GetNext和Close。Open函數(shù)負(fù)責(zé)初始化執(zhí)行操作符所需的數(shù)據(jù)結(jié)構(gòu),但本身并不獲得元組。GetNext函數(shù)負(fù)責(zé)返回符合條件的下一條元組,并對數(shù)據(jù)結(jié)構(gòu)作必要的調(diào)整以得到后續(xù)元組,同時設(shè)置一條元組是否已產(chǎn)生或已沒有元組可產(chǎn)生的標(biāo)志。GetNext函數(shù)通常在一個循環(huán)結(jié)構(gòu)中反復(fù)調(diào)用,以達(dá)到產(chǎn)生所有輸出的目的。迭代器維護(hù)了兩次調(diào)用GetNext之間的執(zhí)行狀態(tài),這樣下一個GetNext調(diào)用請求可以獲取后面的結(jié)果元組。Close函數(shù)進(jìn)行收尾工作,包括以各種方式清除DBMS的內(nèi)部結(jié)構(gòu),通知緩沖區(qū)管理器某些緩沖區(qū)已不再需要等。
下面是一個表掃描操作符迭代器的實現(xiàn)方法。其中Open()操作符掃描第一條元組,并將狀態(tài)置為true。GetNext()函數(shù)從前次記錄的位置繼續(xù)執(zhí)行,并返回下一條元組。
Open(R)
{
b:=關(guān)系R的第一個數(shù)據(jù)塊;
t:=塊b的第一條元組;
found:=true;
}
GetNext(R)
{
if(t已到達(dá)塊b最后一條元組后面){
b:=R的下一個數(shù)據(jù)塊;
if(沒有新的數(shù)據(jù)塊){
found:=false;
return;
}
else/*這時b是一個新數(shù)據(jù)塊*/
　　t:=塊b的第一條元組;
}
oldt:=t;
t:=塊b的下一條元組;
return oldt;
}
Close(R){
} /*無操作*/