空间查询优化

空间查询优化蒋苏蓉'石青青2黄志良1(空军雷达学院计算机教研室,武汉430010 )(华中科技大学计算机学院武汉430074 )E-mail jiangsr@hotmail.com摘要.由于空间数据的复杂性,空间查询需要建立自己的代价模型。该文首先介绍了建立四叉树直方图来对空间查询的选择性进行估计然后在此基础上对DM-SDB的查询代价进行估计并使用该代价模型对DM--SDB的多连接查询进行优化。关键词空间查询优化 代价模型 选择性多连接查 询.文章编号1002- -8331-< 2004 )09- -0188-03文献标识码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树结80年代以来随着新的数据库应用领域的出现如地理信点访问次数来衡量,而且该模型支持对谓词选择性S的估计。息系统(GIS)计算机辅助设计/制造(CAD/CAM)图象和多媒但是该模型对空间数据对象的位置和大小的不统一分布考虑体数据库等"1空间数据库技术逐渐成为数据库领域的一个研:不够。究热点。由于空间数据的数据量大数据结构复杂操作代价昂对空间谓词的选择性估计文献[3]中介绍了基于R树的贵等特点对空间查询进行优化将是空间数据库研究的一个重空间查询的选择性估计方法。给定一个空间关系R ,它包含N点和难点。个均匀分布于二维矩形空间r的矩形数据对象r的宽度为在空间查询优化领域至今还没有提出-套完整的优化系D。高度为D、,W.g和Hag是R中对象的平均宽度和长度给定统设计方案。目前的主要研究方法是建立-个空间查询的代价窗口q=( qx/ qyr)(qx。 qgy。)的窗口查询的选择性为:模型对空间操作的代价进行估计操作代价主要包括执行代价1 1 +qx. -qx,Hg+9Y-9Y1和I/O代价。同时还要对空间谓词的选择性,即满足对查询条S=min|1D件对象的数目与源对象集合数目的比值进行估计。谓词选择性使用上述方法也可以对空间连接查询的选择性进行估计。在很大程度上决定了空间谓词的执行顺序。对于实际的空间数据来说其对象的大小和位置分布是不统一安全空间数据库管理系统DM-SDB是在笔者所在的研究的,上面方法对空间查询的代价和选择性估计存在较大误差。所研制的国产分布式多媒体数据库管理系统DM3的基础上建因此在很多系统中都使用直方图方法将整个空间按对象的大立的空间数据库系统。该文首先提出了建立四叉树直方图来对小或位置划分为-定的区域,每个区域称为-个桶( bucket)空间查询的选择性进行估计然后在此基础上给出了DM-SDB在每个桶中可以假定对象满足统一分布这样可以使用上述的查询代价模型,并使用该代价模型对DM-SDB的多连接查选择性估计公式来估计每个桶中的选择性再把它们累加即得询进行优化。到整个查询的选择性。在直方图方法中最关键的就是划分空间对象的标准在已2空间查询的代价和选择性估计有的研究中主要有下面三种划分方式叫(1 )相等划分:此种划空间查询-般分为过滤和求精两部分川,目前的优化方法分的目标是使结果中的每个桶在某种标准下是相等的如相等主要集中在过滤阶段而且代价模型与空间数据组织形势即空.的面积和中国煤化工此种划分是按某种空间间索引密切相关。比较著名的是Theodoridis等人在文献[2]中索引结构|YHC N M H Go(3 )Skew-Aware划分:提出的一个模型来估计窗口查询和连接查询的代价。该模型的此种划分便用-元空间划分( bianry space partitionings ,BSPs )分析过程是基于R树的,但最终代价公式只依赖于数据对象和spatialskew的概念将空间对象划分到-个个的桶中。基金项目科技部中小企业创新基金资助作者简介蒋苏蓉,女硕士主要研究信息处理多媒体技术。石青青男硕士研究生研究方向为空间数据库技术。188 2004.9 计算机工程与应用采用相等划分的仍然会产生很多对象的位置分布和大小.扫描数据对象,根据对象的MBR信息确定每个数据对象所属不统一的桶,而且它需要所有的对象都保存在内存中增加了的四叉树结点 并记录相关统计信息;系统开销。索引划分最常用的是基于R树的索引划分,但由遍历四叉树,记录有效的的桶Bi ;于R树的插入算法会产生新的结点,这将导致桶中对象的不END ;统一。虽然R树不需要索引|结构和数据完全保存在内存中,但由此方法建立的直方图,可以同时表现出对象的空间分布仍然要对数据进行多次访问。Skew-Aware划分只考虑桶中对和大小等统计信息,而且在每-个桶中的对象都是近似统-分布的。象的数目对对象大小的差异考虑不够。3.2选择性估计3四叉树直方图.为了估计一个窗口查询的选择性,必须估计一个桶B,中鉴于上节的分析,提出建立四叉树直方图的方法，来对整与查询窗口相交的对象数的比例,假设该比例为f。根据前面个空间进行划分。该划分是基于对象的最小边界矩形MBR.在直方|图QT-Histogram的建立过程,可以假设每个桶中的对象每个桶中不需要存储对象指针只存储其包含的对象的数目和都满足统一分布。桶中对象MBR的平均长度和宽度,以及包含这些对象的矩形对于四叉树直方图中的的一个桶B, 其边界用左下角和右区域即结点的边界。上角坐标表示(xx)6x。此) q=(qx/ qy)6qx。gy.]是查询窗口的MBR B,中对象MBR的平均宽度和高度分别为Wag和3.1划分 数据对象四叉树直方图的建立使用四叉树结构5。四叉树是一个递Hy。e如果q与B,不相交f=0如果q完全包含B,f=1如果B,归的数据结构,每个结点代表空间中的一个矩形区域每个结完全包含q ,或与q部分相交则f等于q与B,中一个对象相点最多可以有4个子结点每个子结点代表父结点所表示区域交的概率。如果q与B,中的一个对象相交则它与该对象在x,的一个象限。这样,一个四叉树的根结点将数据空间划分为4y轴上的投影分别相交。假设x;为q与B,中的一个对象。在x轴上相交的概率,个象限(西北NW东北NE西南sw东南SE),每一个象限又根据有关文献的选择性估计方法则有:可以进-步递归地划分为更多的象限,如图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四叉树及 数据对象的划分Jf;xN,降低每个桶中数据对象的差异是所有直方图技术的共同i为四叉树直方图中桶的序号N为关系中的对象数。目标。因此划分算法需要考虑数据对象的如下属性(1对象的对于2元连接查询,假设两个关系R和s中对象的数目位置。一个桶包含的对象必须在空间上彼此靠近这样可以减分别为N,和N2o首先对两个关系分别建立四叉树直方图其中.少一个桶中的无用区域。(2对象的大小。一个桶中对象的大小对R建立直方图后形成的桶为(B, B2.. Bm)S建立直方图决定了该桶与一个查询窗口相交的对象的预期数目。后形成的桶为(B, B2... B.)n和m分别为两个直方图中桶建立四叉树直方图时。先要建立-一个具有L层的完全四叉的数目。设桶B,;中的对象与桶B,中的对象相交的概率为f后树结构。L是直方图建立算法的一个参数,它表示四叉树的层( 1≤i≤n 1≤j≤m )两个桶中对象数目分别为Nx和Ngo将一数。不同层的结点表示数据空间中的不同尺寸的分区。个直方图中的桶作为查询窗口,对两个直方图中的每-对桶用在整个空间中-个数据对象所属的层是它在该四叉树中上面公式计算其相交的对象二元组的数目再把所有结果累加的最大层(离根结点最远的层),即数据对象MBR的长度和宽除以R和S的笛卡儿积的秩,即得到两个关系连接的结果选度小于或等于该层结点的长度和宽度。为数据对象选定层之择性估计其公式表示如下:后选择包含该对象MBR中心的结点为该对象所属结点。在分配对象的过程中,要计算每-个结点所包含的对象数和对象2 Ss;N;NyMBR的平均长度和宽度。S=DNN;N,当所有数据对象都被分配到相应结点后某些结点自身或对于多连接查询,设M(M≥3)个关系为R R.. Rw,每其子孙结点可能不包含任何数据对象,即这些结点不包含任何个关系中对象的数目为N( 1≤i≤M)其查询图为Q S;为Q[]统计信息,因此要去掉无用结点,只保留有效的桶在这些桶B,[i]=true中国煤化工选择性。这里只考虑非(i为桶的序号冲记录桶的边界信息桶中的对象数目以及对循环查询YHCNMH G计为:象MBR的平均长度和宽度。四叉树直方图的建。立算法如下:S=_ II SVi j0il0F=rneCreateHistogramBEGIN建立一个L层的完全四叉树;4 DM-SDB查询代价估计计算机工程与应用2004.9 189 .在DM--SDB中实现了基于R*树的窗口查询、连接查询和则执行计划P的总代价为:多连接查询。窗口查询和连接查询的实现方法采用文[6]中的查询方法并将其推广到两颗不等高的R*树。对于多连接的查COSTP-COST,(R, R, >+cOSTw。(0。)询处理，文献[7]根据其与约束满足问题(constraintsatisfactionmproblems ,CSPs )之间的相似性将系统搜索算法(用于CSPs )5DM-SDB的多连接查询优化与R*树结合起来提出了WR( Windown Reduction)算法。在对于多连接查询,有多种不同的连接顺序,即多个查询计DM-SDB中对其进行了改进,使用文[6]中的方法来处理前两个划。必须选择-个代价较小的计划作为执行计划。在传统关系关系再将得到的2元组用WR算法来-次对后面的关系进行数据库贪婪算法阁是一种普遍使用的连接顺序选择算法它一搜索。目前只考虑非循环查询。在已有基于R树的代价模型中,操作代价主要是计算R .次为连接顺序做一个决定,并且从不返回,或者说一旦做出决树的结点访问次数,在R-tree的每-层计算结点被访问的概定便不再重新考虑。在DM- -SDB中使用该算法对多连接查询率。在DM-SDB中仍将采用该方式来计算查询代价所不同的进行优化找出-个代价相对较小的执行计划。设n个空间关系索引为(RI R... R,),其查询图为Q ,是采用上节提出的直方图模型来计算结点访问的概率。DM-SDB的对多连接查询的优化算法如下:在大部分代价模型中都需要统计R树每.-层结点的一-些Optimization( Query Q00 R _Node R凹)信息(如每层结点的平均范围、结点的密度等),因此在代价模(1对任意Qlili]=true ,计算COSTr R[] R[]);型中，首先访问每个关系的索引,对除根结点以外的每一层都(2 )取最小的COSTe作为R[j]和 R[]进行RtreeJoin ;COST建立一个3层的四叉树直方图来统计每一层结点的信息。在访(P)= COSTaS R[] R[]);问R树的同时，对数据对象的MBR也建立四叉树直方图来保存数据对象的相关统计信息,同时还要计算数据对象MBR(3)在剩下的R树中对任意R[] ,如果Q[i][k]=true ,计算的平均宽度和高度。每隔一段时间,如果某些关系的数据发生并选择使COST( P)+COSTw( R[&] )最小的R[]作为下一步连接变化则要重新建立该关系的统计信息。的关系。4.1窗口查询和2元连接查询的代价计算(4如果所有R树都已确定连接顺序则结束否则转(3)对于窗口查询,假设R树的高度为h(根结点为h层),使用上节的方法计算除根结点以外每一层的结点的选择性s;6结论( 1≤i≤h-1 ).并设每一层的结点数为N,则基于一颗R树R ,该文提出的空间查询优化方法还存在很多不完善的地方,查询窗口为q的选择查询的代价为:如代价模型需要进一步完善不支持复杂的空间谓词,不能对复杂空间查询进行优化等。空间查询优化的主要目的是提高查COSTw(R q)=1+ ZS.N,询处理的速度,因此应该使空间查询真正能够满足实际应用的对于2元连接查询,设两颗R树分别为R和R2树的高.需求。但是实际应用可能对数据表示和访问方式有不同的要度分别为h,和1n2,并且假设h≥h2 S是连接查询在,层的结求,即使同一种应用也可能随着时间的变化提出新的要求,如.点选择性N是R:在1;层的结点数根据文[2]中的代价计算使用新的索引结构、增加新的空间谓词。由此可见,空间查询优化系统必须具有可扩展性,即系统必须适应新的索引结构新方法其结点访问次数为的空间谓词和新的查询算法。(收稿日期: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多 连接查询的代价计算11(1)对于多连接查询,假设P=((0 2)p..... po )是一个查询.2.Y Theodoridis E Stefanakis T llisiEffcient Cost Models for Spatial计划其中变量对应的R树分别为(R R2.. R.)其中前两个Queries Using P-tees[J]IEEE Transactions on Knowledge and Data变量使用JoinQuery算法进行初始化,后面的变量使用WR算Engineering 2000 ;12(1)法按顺序进行初始化。该查询的代价分为两部分第-部分为3.Mamoulis N ,Papadias D.Seletivity Estimation of Complex Spatial一个2元连接查询的代价第=部分中每-个变量初始化的代Queries价为-个窗口查询的代价。4.S Acharta ,V Poosala S Ramaswamy Sectivily Estimation in Spatial在第二部分的代价计算中假设前面k-1个变量都已初始.DatabasesC.In Proc ACM SIGMOD Int Conf on Management of Data ,化对于每一步WR前面h-1个变量有多少个结果就必须在Philadelphia Pennsylvania ,1999 :13~24R.上执行多少次窗口查询,因此其代价为前面k-1个关系产5.H Samet.The quadtree and related hierarchical data struturesJLACM生的结果数与窗口查询的代价的乘积。假设对第k:个变量进行Computing Surveys ,1984 ;16( 2 ):187-260初始化则其查询窗口q:为与其直接关联的变量0_-1所在关系6.T Brinkhe中国煤化工Procesing of Spatial Joins中包含所有对象MBR的矩形为中心,宽度和高度为对象平均Using R-YHCNMH Gnnf Mangment " Doua，宽度和高度的一个窗口Sm为R和R,进行连接的选择性则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 著.杨冬青唐世渭等译.数据Vm nck MmIo)-true库系统实现[M].北京机械工业出版社2001190 2004.9 计算机工程 与应用