空間查詢優(yōu)化蔣蘇蓉'石青青2黃志良1(空軍雷達(dá)學(xué)院計(jì)算機(jī)教研室,武漢430010 )(華中科技大學(xué)計(jì)算機(jī)學(xué)院武漢430074 )E-mail jiangsr@hotmail.com摘要.由于空間數(shù)據(jù)的復(fù)雜性,空間查詢需要建立自己的代價(jià)模型。該文首先介紹了建立四叉樹直方圖來對(duì)空間查詢的選擇性進(jìn)行估計(jì)然后在此基礎(chǔ)上對(duì)DM-SDB的查詢代價(jià)進(jìn)行估計(jì)并使用該代價(jià)模型對(duì)DM--SDB的多連接查詢進(jìn)行優(yōu)化。關(guān)鍵詞空間查詢優(yōu)化 代價(jià)模型 選擇性多連接查 詢.文章編號(hào)1002- -8331-< 2004 )09- -0188-03文獻(xiàn)標(biāo)識(shí)碼A中圖分類號(hào)TP311.11Spatial Query OptimizationJiang Surong' Shi Qingqing2 Huang Zhiliang'( Radar Institute of Air Force ,Wuhan 430010 )( Huazhong University of Science and Technology ,W uhan 430074 )Abstract : Since the complexity of spatial data spatial query should have their own cost models.In this paper ,we firstproduce the quadtree histograms which can estimate the selectivity of spatial query ,and use these histogramsestimate query cost of DM- -SDB.Then we use the cost models to optimize M- way join query of DM- SDB.Keywords : Spatial query optimization Cost model selectivity ,Multi-join query引言集合本身的屬性和查詢條件，而操作代價(jià)則用查詢中R樹結(jié)80年代以來隨著新的數(shù)據(jù)庫應(yīng)用領(lǐng)域的出現(xiàn)如地理信點(diǎn)訪問次數(shù)來衡量,而且該模型支持對(duì)謂詞選擇性S的估計(jì)。息系統(tǒng)(GIS)計(jì)算機(jī)輔助設(shè)計(jì)/制造(CAD/CAM)圖象和多媒但是該模型對(duì)空間數(shù)據(jù)對(duì)象的位置和大小的不統(tǒng)一分布考慮體數(shù)據(jù)庫等"1空間數(shù)據(jù)庫技術(shù)逐漸成為數(shù)據(jù)庫領(lǐng)域的一個(gè)研:不夠。究熱點(diǎn)。由于空間數(shù)據(jù)的數(shù)據(jù)量大數(shù)據(jù)結(jié)構(gòu)復(fù)雜操作代價(jià)昂對(duì)空間謂詞的選擇性估計(jì)文獻(xiàn)[3]中介紹了基于R樹的貴等特點(diǎn)對(duì)空間查詢進(jìn)行優(yōu)化將是空間數(shù)據(jù)庫研究的一個(gè)重空間查詢的選擇性估計(jì)方法。給定一個(gè)空間關(guān)系R ,它包含N點(diǎn)和難點(diǎn)。個(gè)均勻分布于二維矩形空間r的矩形數(shù)據(jù)對(duì)象r的寬度為在空間查詢優(yōu)化領(lǐng)域至今還沒有提出-套完整的優(yōu)化系D。高度為D、,W.g和Hag是R中對(duì)象的平均寬度和長(zhǎng)度給定統(tǒng)設(shè)計(jì)方案。目前的主要研究方法是建立-個(gè)空間查詢的代價(jià)窗口q=( qx/ qyr)(qx。 qgy。)的窗口查詢的選擇性為:模型對(duì)空間操作的代價(jià)進(jìn)行估計(jì)操作代價(jià)主要包括執(zhí)行代價(jià)1 1 +qx. -qx,Hg+9Y-9Y1和I/O代價(jià)。同時(shí)還要對(duì)空間謂詞的選擇性,即滿足對(duì)查詢條S=min|1D件對(duì)象的數(shù)目與源對(duì)象集合數(shù)目的比值進(jìn)行估計(jì)。謂詞選擇性使用上述方法也可以對(duì)空間連接查詢的選擇性進(jìn)行估計(jì)。在很大程度上決定了空間謂詞的執(zhí)行順序。對(duì)于實(shí)際的空間數(shù)據(jù)來說其對(duì)象的大小和位置分布是不統(tǒng)一安全空間數(shù)據(jù)庫管理系統(tǒng)DM-SDB是在筆者所在的研究的,上面方法對(duì)空間查詢的代價(jià)和選擇性估計(jì)存在較大誤差。所研制的國產(chǎn)分布式多媒體數(shù)據(jù)庫管理系統(tǒng)DM3的基礎(chǔ)上建因此在很多系統(tǒng)中都使用直方圖方法將整個(gè)空間按對(duì)象的大立的空間數(shù)據(jù)庫系統(tǒng)。該文首先提出了建立四叉樹直方圖來對(duì)小或位置劃分為-定的區(qū)域,每個(gè)區(qū)域稱為-個(gè)桶( bucket)空間查詢的選擇性進(jìn)行估計(jì)然后在此基礎(chǔ)上給出了DM-SDB在每個(gè)桶中可以假定對(duì)象滿足統(tǒng)一分布這樣可以使用上述的查詢代價(jià)模型,并使用該代價(jià)模型對(duì)DM-SDB的多連接查選擇性估計(jì)公式來估計(jì)每個(gè)桶中的選擇性再把它們累加即得詢進(jìn)行優(yōu)化。到整個(gè)查詢的選擇性。在直方圖方法中最關(guān)鍵的就是劃分空間對(duì)象的標(biāo)準(zhǔn)在已2空間查詢的代價(jià)和選擇性估計(jì)有的研究中主要有下面三種劃分方式叫(1 )相等劃分:此種劃空間查詢-般分為過濾和求精兩部分川,目前的優(yōu)化方法分的目標(biāo)是使結(jié)果中的每個(gè)桶在某種標(biāo)準(zhǔn)下是相等的如相等主要集中在過濾階段而且代價(jià)模型與空間數(shù)據(jù)組織形勢(shì)即空.的面積和中國煤化工此種劃分是按某種空間間索引密切相關(guān)。比較著名的是Theodoridis等人在文獻(xiàn)[2]中索引結(jié)構(gòu)|YHC N M H Go(3 )Skew-Aware劃分:提出的一個(gè)模型來估計(jì)窗口查詢和連接查詢的代價(jià)。該模型的此種劃分便用-元空間劃分( bianry space partitionings ,BSPs )分析過程是基于R樹的,但最終代價(jià)公式只依賴于數(shù)據(jù)對(duì)象和spatialskew的概念將空間對(duì)象劃分到-個(gè)個(gè)的桶中?；痦?xiàng)目科技部中小企業(yè)創(chuàng)新基金資助作者簡(jiǎn)介蔣蘇蓉,女碩士主要研究信息處理多媒體技術(shù)。石青青男碩士研究生研究方向?yàn)榭臻g數(shù)據(jù)庫技術(shù)。188 2004.9 計(jì)算機(jī)工程與應(yīng)用采用相等劃分的仍然會(huì)產(chǎn)生很多對(duì)象的位置分布和大小.掃描數(shù)據(jù)對(duì)象,根據(jù)對(duì)象的MBR信息確定每個(gè)數(shù)據(jù)對(duì)象所屬不統(tǒng)一的桶,而且它需要所有的對(duì)象都保存在內(nèi)存中增加了的四叉樹結(jié)點(diǎn) 并記錄相關(guān)統(tǒng)計(jì)信息;系統(tǒng)開銷。索引劃分最常用的是基于R樹的索引劃分,但由遍歷四叉樹,記錄有效的的桶Bi ;于R樹的插入算法會(huì)產(chǎn)生新的結(jié)點(diǎn),這將導(dǎo)致桶中對(duì)象的不END ;統(tǒng)一。雖然R樹不需要索引|結(jié)構(gòu)和數(shù)據(jù)完全保存在內(nèi)存中,但由此方法建立的直方圖,可以同時(shí)表現(xiàn)出對(duì)象的空間分布仍然要對(duì)數(shù)據(jù)進(jìn)行多次訪問。Skew-Aware劃分只考慮桶中對(duì)和大小等統(tǒng)計(jì)信息,而且在每-個(gè)桶中的對(duì)象都是近似統(tǒng)-分布的。象的數(shù)目對(duì)對(duì)象大小的差異考慮不夠。3.2選擇性估計(jì)3四叉樹直方圖.為了估計(jì)一個(gè)窗口查詢的選擇性,必須估計(jì)一個(gè)桶B,中鑒于上節(jié)的分析,提出建立四叉樹直方圖的方法，來對(duì)整與查詢窗口相交的對(duì)象數(shù)的比例,假設(shè)該比例為f。根據(jù)前面?zhèn)€空間進(jìn)行劃分。該劃分是基于對(duì)象的最小邊界矩形MBR.在直方|圖QT-Histogram的建立過程,可以假設(shè)每個(gè)桶中的對(duì)象每個(gè)桶中不需要存儲(chǔ)對(duì)象指針只存儲(chǔ)其包含的對(duì)象的數(shù)目和都滿足統(tǒng)一分布。桶中對(duì)象MBR的平均長(zhǎng)度和寬度,以及包含這些對(duì)象的矩形對(duì)于四叉樹直方圖中的的一個(gè)桶B, 其邊界用左下角和右區(qū)域即結(jié)點(diǎn)的邊界。上角坐標(biāo)表示(xx)6x。此) q=(qx/ qy)6qx。gy.]是查詢窗口的MBR B,中對(duì)象MBR的平均寬度和高度分別為Wag和3.1劃分 數(shù)據(jù)對(duì)象四叉樹直方圖的建立使用四叉樹結(jié)構(gòu)5。四叉樹是一個(gè)遞Hy。e如果q與B,不相交f=0如果q完全包含B,f=1如果B,歸的數(shù)據(jù)結(jié)構(gòu),每個(gè)結(jié)點(diǎn)代表空間中的一個(gè)矩形區(qū)域每個(gè)結(jié)完全包含q ,或與q部分相交則f等于q與B,中一個(gè)對(duì)象相點(diǎn)最多可以有4個(gè)子結(jié)點(diǎn)每個(gè)子結(jié)點(diǎn)代表父結(jié)點(diǎn)所表示區(qū)域交的概率。如果q與B,中的一個(gè)對(duì)象相交則它與該對(duì)象在x,的一個(gè)象限。這樣,一個(gè)四叉樹的根結(jié)點(diǎn)將數(shù)據(jù)空間劃分為4y軸上的投影分別相交。假設(shè)x;為q與B,中的一個(gè)對(duì)象。在x軸上相交的概率,個(gè)象限(西北NW東北NE西南sw東南SE),每一個(gè)象限又根據(jù)有關(guān)文獻(xiàn)的選擇性估計(jì)方法則有:可以進(jìn)-步遞歸地劃分為更多的象限,如圖1所示。fx, =min(1Wmg +min(x qx。 )-max(x qx, )x一x,同理q與B,中的對(duì)象在y軸上相交的概率為fx=min(H. +min(y. qy。)-max(y qy )E-SE-NEx。-x則查詢窗口q與B,中的對(duì)象相交的概率為:f;=fx,xf;WNEESWSB-SWISE-SE J對(duì)于窗口查詢其選擇性圖1四叉樹及 數(shù)據(jù)對(duì)象的劃分Jf;xN,降低每個(gè)桶中數(shù)據(jù)對(duì)象的差異是所有直方圖技術(shù)的共同i為四叉樹直方圖中桶的序號(hào)N為關(guān)系中的對(duì)象數(shù)。目標(biāo)。因此劃分算法需要考慮數(shù)據(jù)對(duì)象的如下屬性(1對(duì)象的對(duì)于2元連接查詢,假設(shè)兩個(gè)關(guān)系R和s中對(duì)象的數(shù)目位置。一個(gè)桶包含的對(duì)象必須在空間上彼此靠近這樣可以減分別為N,和N2o首先對(duì)兩個(gè)關(guān)系分別建立四叉樹直方圖其中.少一個(gè)桶中的無用區(qū)域。(2對(duì)象的大小。一個(gè)桶中對(duì)象的大小對(duì)R建立直方圖后形成的桶為(B, B2.. Bm)S建立直方圖決定了該桶與一個(gè)查詢窗口相交的對(duì)象的預(yù)期數(shù)目。后形成的桶為(B, B2... B.)n和m分別為兩個(gè)直方圖中桶建立四叉樹直方圖時(shí)。先要建立-一個(gè)具有L層的完全四叉的數(shù)目。設(shè)桶B,;中的對(duì)象與桶B,中的對(duì)象相交的概率為f后樹結(jié)構(gòu)。L是直方圖建立算法的一個(gè)參數(shù),它表示四叉樹的層( 1≤i≤n 1≤j≤m )兩個(gè)桶中對(duì)象數(shù)目分別為Nx和Ngo將一數(shù)。不同層的結(jié)點(diǎn)表示數(shù)據(jù)空間中的不同尺寸的分區(qū)。個(gè)直方圖中的桶作為查詢窗口,對(duì)兩個(gè)直方圖中的每-對(duì)桶用在整個(gè)空間中-個(gè)數(shù)據(jù)對(duì)象所屬的層是它在該四叉樹中上面公式計(jì)算其相交的對(duì)象二元組的數(shù)目再把所有結(jié)果累加的最大層(離根結(jié)點(diǎn)最遠(yuǎn)的層),即數(shù)據(jù)對(duì)象MBR的長(zhǎng)度和寬除以R和S的笛卡兒積的秩,即得到兩個(gè)關(guān)系連接的結(jié)果選度小于或等于該層結(jié)點(diǎn)的長(zhǎng)度和寬度。為數(shù)據(jù)對(duì)象選定層之擇性估計(jì)其公式表示如下:后選擇包含該對(duì)象MBR中心的結(jié)點(diǎn)為該對(duì)象所屬結(jié)點(diǎn)。在分配對(duì)象的過程中,要計(jì)算每-個(gè)結(jié)點(diǎn)所包含的對(duì)象數(shù)和對(duì)象2 Ss;N;NyMBR的平均長(zhǎng)度和寬度。S=DNN;N,當(dāng)所有數(shù)據(jù)對(duì)象都被分配到相應(yīng)結(jié)點(diǎn)后某些結(jié)點(diǎn)自身或?qū)τ诙噙B接查詢,設(shè)M(M≥3)個(gè)關(guān)系為R R.. Rw,每其子孫結(jié)點(diǎn)可能不包含任何數(shù)據(jù)對(duì)象,即這些結(jié)點(diǎn)不包含任何個(gè)關(guān)系中對(duì)象的數(shù)目為N( 1≤i≤M)其查詢圖為Q S;為Q[]統(tǒng)計(jì)信息,因此要去掉無用結(jié)點(diǎn),只保留有效的桶在這些桶B,[i]=true中國煤化工選擇性。這里只考慮非(i為桶的序號(hào)沖記錄桶的邊界信息桶中的對(duì)象數(shù)目以及對(duì)循環(huán)查詢YHCNMH G計(jì)為:象MBR的平均長(zhǎng)度和寬度。四叉樹直方圖的建。立算法如下:S=_ II SVi j0il0F=rneCreateHistogramBEGIN建立一個(gè)L層的完全四叉樹;4 DM-SDB查詢代價(jià)估計(jì)計(jì)算機(jī)工程與應(yīng)用2004.9 189 .在DM--SDB中實(shí)現(xiàn)了基于R*樹的窗口查詢、連接查詢和則執(zhí)行計(jì)劃P的總代價(jià)為:多連接查詢。窗口查詢和連接查詢的實(shí)現(xiàn)方法采用文[6]中的查詢方法并將其推廣到兩顆不等高的R*樹。對(duì)于多連接的查COSTP-COST,(R, R, >+cOSTw。(0。)詢處理，文獻(xiàn)[7]根據(jù)其與約束滿足問題(constraintsatisfactionmproblems ,CSPs )之間的相似性將系統(tǒng)搜索算法(用于CSPs )5DM-SDB的多連接查詢優(yōu)化與R*樹結(jié)合起來提出了WR( Windown Reduction)算法。在對(duì)于多連接查詢,有多種不同的連接順序,即多個(gè)查詢計(jì)DM-SDB中對(duì)其進(jìn)行了改進(jìn),使用文[6]中的方法來處理前兩個(gè)劃。必須選擇-個(gè)代價(jià)較小的計(jì)劃作為執(zhí)行計(jì)劃。在傳統(tǒng)關(guān)系關(guān)系再將得到的2元組用WR算法來-次對(duì)后面的關(guān)系進(jìn)行數(shù)據(jù)庫貪婪算法閣是一種普遍使用的連接順序選擇算法它一搜索。目前只考慮非循環(huán)查詢。在已有基于R樹的代價(jià)模型中,操作代價(jià)主要是計(jì)算R .次為連接順序做一個(gè)決定,并且從不返回,或者說一旦做出決樹的結(jié)點(diǎn)訪問次數(shù),在R-tree的每-層計(jì)算結(jié)點(diǎn)被訪問的概定便不再重新考慮。在DM- -SDB中使用該算法對(duì)多連接查詢率。在DM-SDB中仍將采用該方式來計(jì)算查詢代價(jià)所不同的進(jìn)行優(yōu)化找出-個(gè)代價(jià)相對(duì)較小的執(zhí)行計(jì)劃。設(shè)n個(gè)空間關(guān)系索引為(RI R... R,),其查詢圖為Q ,是采用上節(jié)提出的直方圖模型來計(jì)算結(jié)點(diǎn)訪問的概率。DM-SDB的對(duì)多連接查詢的優(yōu)化算法如下:在大部分代價(jià)模型中都需要統(tǒng)計(jì)R樹每.-層結(jié)點(diǎn)的一-些Optimization( Query Q00 R _Node R凹)信息(如每層結(jié)點(diǎn)的平均范圍、結(jié)點(diǎn)的密度等),因此在代價(jià)模(1對(duì)任意Qlili]=true ,計(jì)算COSTr R[] R[]);型中，首先訪問每個(gè)關(guān)系的索引,對(duì)除根結(jié)點(diǎn)以外的每一層都(2 )取最小的COSTe作為R[j]和 R[]進(jìn)行RtreeJoin ;COST建立一個(gè)3層的四叉樹直方圖來統(tǒng)計(jì)每一層結(jié)點(diǎn)的信息。在訪(P)= COSTaS R[] R[]);問R樹的同時(shí)，對(duì)數(shù)據(jù)對(duì)象的MBR也建立四叉樹直方圖來保存數(shù)據(jù)對(duì)象的相關(guān)統(tǒng)計(jì)信息,同時(shí)還要計(jì)算數(shù)據(jù)對(duì)象MBR(3)在剩下的R樹中對(duì)任意R[] ,如果Q[i][k]=true ,計(jì)算的平均寬度和高度。每隔一段時(shí)間,如果某些關(guān)系的數(shù)據(jù)發(fā)生并選擇使COST( P)+COSTw( R[&] )最小的R[]作為下一步連接變化則要重新建立該關(guān)系的統(tǒng)計(jì)信息。的關(guān)系。4.1窗口查詢和2元連接查詢的代價(jià)計(jì)算(4如果所有R樹都已確定連接順序則結(jié)束否則轉(zhuǎn)(3)對(duì)于窗口查詢,假設(shè)R樹的高度為h(根結(jié)點(diǎn)為h層),使用上節(jié)的方法計(jì)算除根結(jié)點(diǎn)以外每一層的結(jié)點(diǎn)的選擇性s;6結(jié)論( 1≤i≤h-1 ).并設(shè)每一層的結(jié)點(diǎn)數(shù)為N,則基于一顆R樹R ,該文提出的空間查詢優(yōu)化方法還存在很多不完善的地方,查詢窗口為q的選擇查詢的代價(jià)為:如代價(jià)模型需要進(jìn)一步完善不支持復(fù)雜的空間謂詞,不能對(duì)復(fù)雜空間查詢進(jìn)行優(yōu)化等。空間查詢優(yōu)化的主要目的是提高查COSTw(R q)=1+ ZS.N,詢處理的速度,因此應(yīng)該使空間查詢真正能夠滿足實(shí)際應(yīng)用的對(duì)于2元連接查詢,設(shè)兩顆R樹分別為R和R2樹的高.需求。但是實(shí)際應(yīng)用可能對(duì)數(shù)據(jù)表示和訪問方式有不同的要度分別為h,和1n2,并且假設(shè)h≥h2 S是連接查詢?cè)?層的結(jié)求,即使同一種應(yīng)用也可能隨著時(shí)間的變化提出新的要求,如.點(diǎn)選擇性N是R:在1;層的結(jié)點(diǎn)數(shù)根據(jù)文[2]中的代價(jià)計(jì)算使用新的索引結(jié)構(gòu)、增加新的空間謂詞。由此可見,空間查詢優(yōu)化系統(tǒng)必須具有可擴(kuò)展性,即系統(tǒng)必須適應(yīng)新的索引結(jié)構(gòu)新方法其結(jié)點(diǎn)訪問次數(shù)為的空間謂詞和新的查詢算法。(收稿日期:2003年5月)COST,(R, R2 )=2+2(s; Nw,i; N.,+S; Ne,i; Ne)參考文獻(xiàn)(h-(h,-h2 )h-h2+1≤l≤h,-1其中(2=111≤l≤h,-hz1.S Shekhar et al.Spatial DatabasesNeed-sJ.IEEE Transactions on Knowledge and Data Engineering 1999 ;4.2多 連接查詢的代價(jià)計(jì)算11(1)對(duì)于多連接查詢,假設(shè)P=((0 2)p..... po )是一個(gè)查詢.2.Y Theodoridis E Stefanakis T llisiEffcient Cost Models for Spatial計(jì)劃其中變量對(duì)應(yīng)的R樹分別為(R R2.. R.)其中前兩個(gè)Queries Using P-tees[J]IEEE Transactions on Knowledge and Data變量使用JoinQuery算法進(jìn)行初始化,后面的變量使用WR算Engineering 2000 ;12(1)法按順序進(jìn)行初始化。該查詢的代價(jià)分為兩部分第-部分為3.Mamoulis N ,Papadias D.Seletivity Estimation of Complex Spatial一個(gè)2元連接查詢的代價(jià)第=部分中每-個(gè)變量初始化的代Queries價(jià)為-個(gè)窗口查詢的代價(jià)。4.S Acharta ,V Poosala S Ramaswamy Sectivily Estimation in Spatial在第二部分的代價(jià)計(jì)算中假設(shè)前面k-1個(gè)變量都已初始.DatabasesC.In Proc ACM SIGMOD Int Conf on Management of Data ,化對(duì)于每一步WR前面h-1個(gè)變量有多少個(gè)結(jié)果就必須在Philadelphia Pennsylvania ,1999 :13~24R.上執(zhí)行多少次窗口查詢,因此其代價(jià)為前面k-1個(gè)關(guān)系產(chǎn)5.H Samet.The quadtree and related hierarchical data struturesJLACM生的結(jié)果數(shù)與窗口查詢的代價(jià)的乘積。假設(shè)對(duì)第k:個(gè)變量進(jìn)行Computing Surveys ,1984 ;16( 2 ):187-260初始化則其查詢窗口q:為與其直接關(guān)聯(lián)的變量0_-1所在關(guān)系6.T Brinkhe中國煤化工Procesing of Spatial Joins中包含所有對(duì)象MBR的矩形為中心,寬度和高度為對(duì)象平均Using R-YHCNMH Gnnf Mangment " Doua，寬度和高度的一個(gè)窗口Sm為R和R,進(jìn)行連接的選擇性則19937.Papadias D ,Mamoulis N ,Delis B.Algorithms for Querying by SpatialWR的查詢代價(jià)為:Strueture.VLDB ,1998COSTw(D。=IIN; IDSm COSTw(R: Ae )8.H Garcia- -Molina J D Ullman J Widom 著.楊冬青唐世渭等譯.數(shù)據(jù)Vm nck MmIo)-true庫系統(tǒng)實(shí)現(xiàn)[M].北京機(jī)械工業(yè)出版社2001190 2004.9 計(jì)算機(jī)工程 與應(yīng)用