馮凱平

0 前言

在關(guān)系數(shù)據(jù)庫(kù)中,最難處理和優(yōu)化的一個(gè)邏輯操作符是連接（JOIN），由于多個(gè)關(guān)系連接時(shí)可以有很多不同的順序,因此對(duì)應(yīng)于查詢的執(zhí)行計(jì)劃的數(shù)目會(huì)隨著該查詢包含的關(guān)系個(gè)數(shù)呈指數(shù)級(jí)增長(zhǎng),當(dāng)關(guān)系個(gè)數(shù)很多時(shí),將導(dǎo)致搜索空間極度膨脹。[1]因此，當(dāng)連接操作涉及多個(gè)關(guān)系時(shí)，需要考慮連接順序。人們?cè)O(shè)計(jì)了多種連接順序及方法，如遺傳算法、模擬退火算法、蟻群算法、左偏樹連接法等，其中左偏樹連接其代價(jià)是較低的且容易實(shí)現(xiàn)。

1 連接順序的選擇

當(dāng)對(duì)兩個(gè)關(guān)系選擇連接順序時(shí)，一般來(lái)說(shuō)將較小的關(guān)系先讀入主存，這樣可以較好地匹配來(lái)自另一個(gè)關(guān)系中的元組，當(dāng)與另一個(gè)關(guān)系連接時(shí)，每次讀入一個(gè)塊，并將關(guān)系中的元組和已存入內(nèi)存中的元組進(jìn)行連接操作。

1.1 連接樹

做如下符號(hào)約定:πL為投影(L為投影屬性)、σC為選擇(c為選擇條件)、∞C為連接(c為連接條件)、×為關(guān)系的迪卡爾積、T(R)為關(guān)系R的元組數(shù)目、V(R，A)為關(guān)系R中屬性A不同取值的種類數(shù)目。

假設(shè)有以下四個(gè)數(shù)據(jù)表，學(xué)籍表:XJ（姓名，年齡，專業(yè)，特質(zhì)，…）、試題庫(kù)表:ST（題號(hào)，適合專業(yè)，難度，…）、選課表:XK（課程，適用專業(yè)，姓名，…）、答題表:DT（考生姓名，題號(hào)，作答，用時(shí)，分值，…）。

實(shí)例1:查詢專業(yè)為烹飪工藝、選修了“食品化學(xué)”課程的學(xué)生姓名。

Select b.姓名

From XK as a inner join XJ as b a.姓名=b.姓名

Where b.專業(yè)=”烹飪工藝”and課程=”食品化學(xué)”（1）

式（1）的邏輯代數(shù)樹結(jié)構(gòu)[2]。如圖1所示:

圖1 式(1)的代數(shù)樹

選擇XJ作為第一個(gè)變?cè)ㄗ笞冊(cè)?，其依?jù)是，一個(gè)學(xué)生可以選擇多門課程，如果規(guī)定每位學(xué)生必須選擇一門以上的課程，那么關(guān)系XJ的規(guī)模必定小于XK，而且XJ又進(jìn)行了σ年齡＝20的選擇操作，致使XJ的規(guī)模進(jìn)一步縮小。所以選擇XJ作為第一變?cè)獮樽罴选?/p>

對(duì)于兩個(gè)關(guān)系的連接，其樹結(jié)構(gòu)只有兩種情形，原則上可以任意取一個(gè)關(guān)系作為第一變?cè)?。?dāng)關(guān)系多于兩個(gè)時(shí)，如n個(gè)，樹的形狀數(shù)目T（n）按下式遞歸增長(zhǎng):[3][4]

四個(gè)關(guān)系中其中的三種樹結(jié)構(gòu)，如圖2所示:

圖2 四個(gè)關(guān)系的連接方法

把每一個(gè)關(guān)系（葉結(jié)點(diǎn)）放在樹中不同的位置進(jìn)行排序，共有4!=24種排序方法。當(dāng)n=4時(shí)，T（4）=5，此時(shí)，總的樹形結(jié)構(gòu)共5*4！=120種。

1.2 左偏連接樹

左偏樹是一棵二叉樹，圖2a）中，所有的葉結(jié)點(diǎn)都在右方，是左偏樹，根據(jù)各個(gè)變?cè)帕许樞虻牟煌灿?4種樹形可供選擇。圖2c）則為右偏樹，圖2b）為緊密樹。左偏樹有以下兩項(xiàng)優(yōu)點(diǎn):[3]

第一，查詢計(jì)劃的搜索可以用于較大的查詢；

第二，基于左偏樹查詢算法的查詢計(jì)劃比其他種類的樹結(jié)構(gòu)的算法更加有效。

實(shí)際應(yīng)用中，作為一個(gè)葉結(jié)點(diǎn)，中間還可以帶有其他操作符號(hào)，如圖1，左結(jié)點(diǎn)加入了選擇操作。

考慮圖2a）左偏樹。假設(shè)4個(gè)關(guān)系規(guī)模的大小順序是XJ、XK、ST、DT，以左變?cè)_(kāi)始建立樹關(guān)系，其意義在于以樹左方的變?cè)獌?yōu)先存儲(chǔ)在主存中。在進(jìn)行XJ∞XK連接操作之前，首先將XJ存入內(nèi)存，然后計(jì)算XJ∞XK并存儲(chǔ)。用B表示緩沖區(qū)塊，此時(shí)占用的內(nèi)存緩沖區(qū)大小為B(XJ)+B(XJ∞XK)。由于XJ和XK是四個(gè)關(guān)系較小的，所以主存緩沖區(qū)應(yīng)當(dāng)能夠容納這些塊。下一步計(jì)算XJ∞XK∞ST并存入主存中，現(xiàn)在XJ已無(wú)保留的必要，所以緩沖區(qū)塊的大小為B(XJ∞XK)+B(XJ∞XK∞XT)。同理，當(dāng)再加入DT的連接后不再保留XJ∞XK。緩沖區(qū)可以存儲(chǔ)連接的最終結(jié)果。

如果采用圖2c）右偏樹，首先將XJ存入主存緩沖區(qū)，用于“建立關(guān)系”，緊接著將XK∞ST∞D(zhuǎn)T載入內(nèi)存進(jìn)行XJ的“關(guān)系試探”，但是要計(jì)算XK∞ST∞D(zhuǎn)T需要將XK放入緩沖區(qū)以建立關(guān)系，然后計(jì)算出ST∞D(zhuǎn)T作為XK的試探關(guān)系。但是ST∞D(zhuǎn)T需要先將ST讀入緩沖區(qū)?，F(xiàn)在內(nèi)存中同時(shí)有XJ、XK、ST3個(gè)關(guān)系。此意味著如果要進(jìn)行n個(gè)葉結(jié)點(diǎn)的右偏樹連接，就必須先將n-1個(gè)關(guān)系同時(shí)讀入內(nèi)存中，增加了緩沖區(qū)數(shù)目。而左偏樹任何時(shí)候最多每次連接僅需開(kāi)辟兩個(gè)緩沖區(qū)容納兩個(gè)關(guān)系即可。

如果一個(gè)連接在主存中只能獲得有限個(gè)緩沖區(qū)，當(dāng)緩沖區(qū)過(guò)多時(shí)，將增加磁盤訪問(wèn)次數(shù)、加重CPU及I/O時(shí)間開(kāi)銷，最終使得所有算法的性能降低。

2 多屬性連接的代價(jià)估計(jì)

實(shí)例2:自適應(yīng)型考試是一種新型的先進(jìn)測(cè)試方式，它為學(xué)生選取的題目適應(yīng)學(xué)生特質(zhì)?，F(xiàn)需查詢所選擇的題目適合本人專業(yè)，且題目難度與自身特質(zhì)相適應(yīng)的學(xué)生。以題目難度與特質(zhì)相差0.3為判定標(biāo)準(zhǔn)。將特質(zhì)與難度都分成30個(gè)等級(jí)區(qū)間（實(shí)際應(yīng)用中會(huì)出現(xiàn)缺值）。其SQL表達(dá)式為:

XJ和ST的T、V參數(shù)。根據(jù)其數(shù)據(jù)值，XJ與ST的連接概率做如下估計(jì)，如表1所示:

表1 XJ與ST的T、V參數(shù)表

假設(shè)XJ中有一元組x，ST中有元組s，將屬性“專業(yè)”和“適合專業(yè)”用Zy表示。如果V（XJ，Zy）≥V（ST，Zy），根據(jù)“值集包含”原理那么s的Zy必然出現(xiàn)在XJ中的諸Zy值之一。因此，x具有與s相同Zy的概率是1/V（XJ，Zy）。類似，如果V（XJ，Zy）

由此得知，在Zy上的相同概率是1/max（V（XJ，Zy），V（ST，Zy））。

同理，將學(xué)生“特質(zhì)”和題目“難度”用Na表示，關(guān)于x和s在Na上取相同值的概率的方法應(yīng)當(dāng)是1/max（V（XJ，Na），V（ST，Na））。

由于Zy和Na值是獨(dú)立的，元組在Zy和Na上相同的概率是這些因子之積。因此，源自XJ和ST的迪卡爾積T（XJ）·T（ST）元組中，在Zy和Na上匹配的期望值是:[4][5][6]

式（3）的最終估計(jì)值為1000*2000/(max(15,20)max(18,27))=3703個(gè)元組。

3 多個(gè)關(guān)系連接的代價(jià)估計(jì)

3.1 多關(guān)系連接代價(jià)估計(jì)方法

假設(shè)有n個(gè)關(guān)系R1、R2、……Rn，進(jìn)行以下連接操作:S=R1∞R2∞…∞Rn。

假設(shè)屬性A出現(xiàn)在k（1≤k≤n）個(gè)Ri中，在此k個(gè)關(guān)系中，值的集合的個(gè)數(shù)（即V（Ri，A）的各個(gè)值，其中i=1,2,…k）滿足v1≤v2≤…≤vk，次序從最小到最大。假設(shè)從每個(gè)關(guān)系中選一個(gè)元組，所選的元組在屬性A上相同的概率是多少？

考慮從具有最小數(shù)目的A值v1的關(guān)系中選取的元組t1。根據(jù)值集包含原理，這v1個(gè)值中的每一個(gè)值是在其他具有屬性A的關(guān)系中所發(fā)現(xiàn)的A值中。考慮屬性A上有vi個(gè)值的關(guān)系。它所選的元組ti在屬性A上與ti相同的概率是1/vi。由于這個(gè)結(jié)論對(duì)于所有i=2,3…,k均為真，因此所有k個(gè)元組在A上相同的概率是積1/v2v3…vk。由此可得到以下規(guī)則:

從每個(gè)關(guān)系中元組數(shù)的積出發(fā)，然后，對(duì)于至少出現(xiàn)兩次的屬性A，除以除了V（R，A）中最小值之外的所有值。[3][4]

3.2 多關(guān)系連接代價(jià)估計(jì)實(shí)例分析

實(shí)例3:假定有3個(gè)關(guān)系的T、V統(tǒng)計(jì)值?？紤]連接R（a,b,c）∞S（b,c,d）∞U（b,e），如表2所示:

表2 R、S與U的T、V參數(shù)表

為估計(jì)此連接大小，先將3個(gè)關(guān)系的T值做積操作，即1000×2000×5000。接著，查找那些出現(xiàn)多于兩次的屬性，它們是b出現(xiàn)3次，c兩次。將積除以V（R,b）、V（S,b）、V（U,b）中較大的兩個(gè)值，它們是50和200。最后，再除以V（R,c）、V（S,c）中較大的一個(gè)，即200。其估計(jì)結(jié)果是:

1000×2000×5000/（50×200×200）＝5000

實(shí)例4有以下3個(gè)關(guān)系:

將XJ、ST、DT3個(gè)關(guān)系中具有同類性質(zhì)的屬性特質(zhì)、難度、分值用符號(hào)Na表示；屬性姓名、考生姓名用Xm表示；作答、答案用Da表示；題號(hào)用Th表示。某次考試后3個(gè)關(guān)系的屬性值，如表3所示:

統(tǒng)計(jì)中等特質(zhì)水平（16-25）的考生作答較大難度題目（25-30）的得分情況。

作如下假設(shè):沒(méi)有特低特質(zhì)（1-12）區(qū)間的考生、沒(méi)有特低難度（1-3）區(qū)間的試題。

按左偏樹進(jìn)行連接操作:

Select a.姓名,c.分值

From Xs as a,Ti as b,Dt as c

Where a.姓名=c.考生姓名and b.題號(hào)=c.題號(hào)and b.答案=c.作答and(b.難度>="25"and b.難度<="30")and(a.特質(zhì)>="16"and a.特質(zhì)<="25")

統(tǒng)計(jì)它們之間連接（即S＝Xs ∞Ti∞D(zhuǎn)t）之后的大小:

4 結(jié)束語(yǔ)

多連接查詢的優(yōu)化是一個(gè)復(fù)雜問(wèn)題。本文通過(guò)應(yīng)用實(shí)例分析，重點(diǎn)闡述了基于左偏樹平均值統(tǒng)計(jì)的數(shù)據(jù)查詢優(yōu)化過(guò)程中連接操作代價(jià)的估計(jì)方法。這種算法通過(guò)各個(gè)關(guān)系之間的大小順序作為選擇連接下一個(gè)關(guān)系的依據(jù)，使得估計(jì)過(guò)程簡(jiǎn)單、明了。在關(guān)系數(shù)目不是太多時(shí)是一種比較好的選擇。誠(chéng)然，當(dāng)連接關(guān)系較多時(shí)，可以考慮其他估計(jì)方法，如遺傳統(tǒng)計(jì)法、群蟻統(tǒng)計(jì)法等。

[1]王瑩,徐鑫.GAAA算法在數(shù)據(jù)庫(kù)多連接查詢優(yōu)化中的研究應(yīng)用[J].云南師范大學(xué)學(xué)報(bào).2011,31(1),54-56.

[2]伍軍云,徐少平,林振榮等.一種新的關(guān)系數(shù)據(jù)庫(kù)查詢優(yōu)化方法[J]計(jì)算機(jī)與現(xiàn)代化.2006,7,33-35.

[3]Hector Garcia-Molina,Jeffrey D.Ullman,Jennifer Widom.Database System Implementation[M].Palo Alto,California:Stanford University,2001,3.

[4]郭聰莉,朱莉,李向.基于蟻群算法的多連接查詢優(yōu)化方法計(jì)[J].計(jì)算機(jī)工程.2009,35(10),173-175.

[5]彭建平,王變琴.再探多連接查詢優(yōu)化方法[J].中山大學(xué)學(xué)報(bào).2001,40(2),27-30.

[6]李志偉.基于貪婪策略的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化研究[j]計(jì)算機(jī)工程與設(shè)計(jì).2010,31(17),3838-3840.