空間查詢(xún)優(yōu)化

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