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