多關(guān)系連接順序選擇與代價估計

馮凱平

0 前言

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

1 連接順序的選擇

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

1.1 連接樹

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

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

實例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作為第一個變元（左變元），其依據(jù)是，一個學(xué)生可以選擇多門課程，如果規(guī)定每位學(xué)生必須選擇一門以上的課程，那么關(guān)系XJ的規(guī)模必定小于XK，而且XJ又進(jìn)行了σ年齡＝20的選擇操作，致使XJ的規(guī)模進(jìn)一步縮小。所以選擇XJ作為第一變元為最佳。

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

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

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

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

1.2 左偏連接樹

左偏樹是一棵二叉樹，圖2a）中，所有的葉結(jié)點都在右方，是左偏樹，根據(jù)各個變元排列順序的不同，共有24種樹形可供選擇。圖2c）則為右偏樹，圖2b）為緊密樹。左偏樹有以下兩項優(yōu)點:[3]

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

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

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

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

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

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

2 多屬性連接的代價估計

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

XJ和ST的T、V參數(shù)。根據(jù)其數(shù)據(jù)值，XJ與ST的連接概率做如下估計，如表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值是獨立的，元組在Zy和Na上相同的概率是這些因子之積。因此，源自XJ和ST的迪卡爾積T（XJ）·T（ST）元組中，在Zy和Na上匹配的期望值是:[4][5][6]

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

3 多個關(guān)系連接的代價估計

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

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

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

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

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

3.2 多關(guān)系連接代價估計實例分析

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

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

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

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

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

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

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

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

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

Select a.姓名,c.分值

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

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

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

4 結(jié)束語

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

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

[2]伍軍云,徐少平,林振榮等.一種新的關(guān)系數(shù)據(jù)庫查詢優(yōu)化方法[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ī)工程.2009,35(10),173-175.

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

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