查詢處理算法

主講教師：魏巍巍北京信息職業(yè)技術(shù)學(xué)院數(shù)據(jù)庫(kù)技術(shù)與應(yīng)用查詢處理算法創(chuàng)建采集任務(wù)01外部排序集合操作算法選擇操作算法010203目錄CONTENTS外部排序01關(guān)系的邏輯存儲(chǔ)結(jié)構(gòu)是二維表，表的元素是元組。不同的DBMS使用不同的物理存儲(chǔ)結(jié)構(gòu)存放關(guān)系。

一般地講，DBMS向操作系統(tǒng)申請(qǐng)若干個(gè)文件，把這些文件占用的磁盤(pán)空間作為一個(gè)整體進(jìn)行段頁(yè)式管理，一個(gè)頁(yè)面又叫做一塊（Block）。不同系統(tǒng)的塊的大小也不一樣，塊是DBMS的I/O單位。一個(gè)關(guān)系的元組被存儲(chǔ)在一個(gè)或多個(gè)塊中。外部排序?yàn)楸阌诿枋龊陀懻摚紫纫胍恍┯浱?hào)。用B(R)表示關(guān)系R占用的塊數(shù)，用T(R)表示R中元組的數(shù)目，用V(R，A)表示關(guān)系R在屬性A上不同值的個(gè)數(shù)。

在查詢處理中，需要內(nèi)存和磁盤(pán)操作，由于磁盤(pán)I/O操作涉及機(jī)械動(dòng)作，需要的時(shí)間與內(nèi)存操作相比要高幾個(gè)數(shù)量級(jí)。因此，在評(píng)估查詢處理算法時(shí)，一般用算法讀寫(xiě)的I/O塊數(shù)作為衡量單位。外部排序外部排序

排序是數(shù)據(jù)庫(kù)中最基本的操作之一。很多語(yǔ)句中執(zhí)行DISTINCT、GROUPBY和ORDERBY子句等都要使用排序操作。在數(shù)據(jù)庫(kù)環(huán)境下，排序操作對(duì)象的數(shù)量十分巨大，例如，對(duì)一個(gè)有幾百萬(wàn)元組的關(guān)系進(jìn)行排序就要使用外部排序算法。外部排序一個(gè)典型的外部排序算法分為內(nèi)部排序階段和歸并階段。其核心思想是根據(jù)內(nèi)存的大小，將存放在磁盤(pán)上待排序的關(guān)系邏輯上分為若干個(gè)段（run），一個(gè)段的大小以可使用的內(nèi)存大小為上限。在內(nèi)部排序階段，從磁盤(pán)上把一個(gè)段中的全部元組讀入內(nèi)存，使用我們熟悉的內(nèi)部排序算法，如快速排序，將這些元組排序，然后把它們寫(xiě)到磁盤(pán)臨時(shí)存放。處理完所有的段后，進(jìn)入歸并排序階段，采用多路歸并排序算法，經(jīng)過(guò)1趟或2趟歸并排序后，就完成對(duì)關(guān)系的排序。外部排序2000012王林……2000113張大民…2000278姜凡……2000256顧芳……2000014葛波……2000467……2000210……2000623……2000756……2000213……2000012……2000113……2000256……2000278……2000014……2000210……2000467……2000623……2000213……2000756……圖1對(duì)Student關(guān)系的內(nèi)部排序階段外部排序2000012

2000113

2000256

2000278

2000014

2000210

2000467

2000623

2000213

2000756

輸入緩沖區(qū)輸入緩沖區(qū)輸入緩沖區(qū)選擇算法輸出緩沖區(qū)圖2對(duì)Student關(guān)系的多路歸并階段200001220000142000113 20002102000213200025620002782000467 外部排序圖1是內(nèi)部排序示意圖，學(xué)號(hào)是排序?qū)傩裕僭O(shè)可用內(nèi)存大小為4個(gè)元組，10個(gè)元組分3次讀入內(nèi)存，排序后在磁盤(pán)上有3個(gè)有序的段。圖2是3路歸并示意圖，選擇算法從輸入緩沖區(qū)中選擇最小的學(xué)號(hào)，把該學(xué)號(hào)所在的元組放到輸出緩沖區(qū)，待緩沖區(qū)滿后，將緩沖區(qū)中的元組在輸出到磁盤(pán)。圖中為了節(jié)省空間，只給出了每個(gè)元組的學(xué)號(hào)屬性。一個(gè)輸入緩沖區(qū)和輸出緩沖區(qū)是一個(gè)或多個(gè)塊，選擇算法一般使用堆。外部排序如果可用內(nèi)存為M塊，則外部排序的I/O次數(shù)大約為：所有的DBMS都對(duì)外部排序算法進(jìn)行了最大限度的優(yōu)化，理論計(jì)算表明，對(duì)絕大數(shù)應(yīng)用而言，多路歸并階段只需要一趟即可。外部排序

集合操作算法02在SQL中，集合有兩種語(yǔ)義，即傳統(tǒng)的集合語(yǔ)義和包語(yǔ)義，二者的差別在于是否允許出現(xiàn)重復(fù)的元素。我們首先給出包語(yǔ)義的并、交和差運(yùn)算的定義。為了敘述方便，用記號(hào)tm表示元組t在集合中的出現(xiàn)次數(shù)，m>0表示t重復(fù)出現(xiàn)了m次，m=0，表示t沒(méi)有出現(xiàn)在集合中。集合操作算法1.包并兩個(gè)集合R和S包并的結(jié)果要包含R和S中的所有元組，用公式表示為：

R∪BS={tm+n|tm

R∧tn

S}圖3中關(guān)系R和S中都有元組（a2，b2，c1），這個(gè)元組在結(jié)果中重復(fù)出現(xiàn)了2次。ABCABCABCa1b1c1a1b2c2a1b1c1a1b2c2∪Ba1b3c2a1b2c2a2b2c1a2b2c1a2b2c1a1b2c2a1b3c2a2b2c1

圖3包并運(yùn)算集合操作算法2.包交

在傳統(tǒng)的集合中，如果t∈R∩S，則t∈R并且t∈S，即如果t出現(xiàn)在交的結(jié)果中，t在R和S中至少各出現(xiàn)一次。包中允許元組重復(fù)出現(xiàn)，因此，包交的定義如下：R∩BS={tk|tm

R∧tn

S,k=min(m,n)

}包交的例子如下圖所示：

集合操作算法圖4包交運(yùn)算

ABCa2b2c1a1b1c1a2b2c1a1b2c2a2b2c1R∩BABCa1b2c2a2b2c1a1b3c2a2b2c1SABCa1b2c2a2b2c1a2b2c1R∩S集合操作算法3.包差

差運(yùn)算類(lèi)似于并運(yùn)算，包差的定義為：R-B

S={tk|tmR∧tnS,k=max(0,m-n)}例如：ABCa1b1c1a1b2c2a1b1c1a2b2c1RABCa1b2c2a1b3c2a2b2c1SABCa1b1c1a1b1c1R-S-B圖5包差運(yùn)算集合操作算法采用的語(yǔ)義不同，實(shí)現(xiàn)集合操作的算法也不同。下面給出不同語(yǔ)義下集合并、交和差操作的算法。假設(shè)可用的內(nèi)存為M塊，參與操作的兩個(gè)關(guān)系是R和S，并且S為兩個(gè)關(guān)系中占用存儲(chǔ)空間較少的關(guān)系。一趟算法

如果滿足B(S)≤M–1的條件，則集合操作只需要讀關(guān)系R和S各一次，寫(xiě)結(jié)果關(guān)系一次，總的I/O次數(shù)等于2(B(R)+B(S))，這樣的算法叫做一趟算法。包語(yǔ)義下的操作不需要去除重復(fù)元組，實(shí)現(xiàn)起來(lái)相對(duì)簡(jiǎn)單集合操作算法集合并將Ｓ讀入內(nèi)存中的M－１個(gè)緩沖區(qū)建立一個(gè)查找結(jié)構(gòu)，例如，二叉查找樹(shù)。Do把Ｒ的一個(gè)塊讀到第Ｍ個(gè)緩沖區(qū)，對(duì)于這個(gè)緩沖區(qū)中的每個(gè)元組t，在查找結(jié)構(gòu)中查找是否有與t相同的元組，如果沒(méi)有，輸出t，否則，就不輸出。whileR中還有其它的塊輸出S的所有元組集合操作算法集合交

集合交的算法和集合并的算法不同之處在于，對(duì)于R的一個(gè)元組t，如果能在查找結(jié)構(gòu)中找到它，則輸出t，否則不輸出它。集合差

集合差是一種不可交換的操作，R-S不同于S-R。假設(shè)Ｒ為關(guān)系中較大的關(guān)系。在兩種情況下，將Ｓ讀到Ｍ－１個(gè)緩沖區(qū)中，建立查找結(jié)構(gòu)。

對(duì)于R-S，