最新XML查询优化中的关键技术研究课件PPT.ppt 88页

'XML查询优化中的关键技术研究 问题的提出XML的特点自描述性半结构化可扩展性数据与显示分离XML应用的广泛增长数据交换，数据表示信息发布电子商务WebServices语义网格…XML数据规模和复杂度快速增长挑战：如何高效的处理大量，复杂的XML数据？存储查询更新…2---------------------------------------------------- 问题的提出（实例）SergeAbiteboulPeterBunemanDanSuciuMorganKaufmann128.8J.MchughJ.WidomProcessingofVLDB1999rootbooktitlepaperauthorspublisherpricetitleauthorsfromauthorSergeAbiteboulDataontheWeb:FromRelationstoSemistructuredDataandXMLPeterBunemanfrom>ProcessingofVLDB1999authorauthorauthorauthorDanSuciuMorganKaufmann128.8QueryOptimizationforXMLJ.MchughJ.WidowFor$bin//bookWhere$b/price>100Return{$t/title}$p$b.tag=book&$p.tag=price&$p>100&$t.tag=title$b$t影响查询效率的关键因素：复杂的数据结构灵活多变的查询语言路径表达式缺乏模式的支持3---------------------------------------------------- PatternTree及其简化PatternTree语法简化语义简化非叶节点简化referenceauthorbookauthornamereferenceauthorbookemailnameemailreferenceauthorbookemailreferencebookemailv1v2v3v4v5v6v1v2v4v5v1v2v4v6v5v1v2v5用XQuery,XPath等XML查询语言表示的查询语句转换为PatternTree。PatternTree的大小和复杂程度决定了查询执行的效率。PatternTree中包含冗余节点，需要优化。7---------------------------------------------------- 相关工作分析改进的Chase方法－－巧妙的先膨胀再收缩的方法把完整性约束作为冗余条件插入到查询表达式中，利用等价转换规则重写查询表达式达到优化的目的。。问题：由于XML数据结构和查询的复杂性，导致膨胀后无法完全收缩，造成简化的不彻底性。只能处理叶结点路径等价类方法把XML文档模式（DTD）划分为若干个路径等价类，每个类中的路径等价。将XPath转换为由简单路径构成的合取范式形式，利用路径等价类中的最短路径代替表达式中的路径。问题：需要对PTQ进行转换，占用大量优化时间。不确定路径的确定化，这实际上也是一种路径膨胀。8---------------------------------------------------- 基于模式的语义优化本文提出了一种利用模式信息指导的PatternTree语义优化方法。中心思想根据模式信息提取节点间的语义约束关系利用语义约束关系删除PatternTree中的冗余节点，从而减少PatternTree的规模，提高查询效率。冗余叶结点冗余非叶结点9---------------------------------------------------- referencebookreferencebookreferencepaperauthornameSchema中的完整性约束包括三种：纯祖先约束：若任意两节点u和v，有且仅有一条路径u/u1/…un/v,(n>=0),则u为v的纯祖先节点，记为uv。纯父约束：若任意两节点u和v，有且仅有一条边相连，则u为v的纯父节点，记为uv。同时出现约束：若任意一节点u，存在节点v，满足下列条件之一的，则v与u同时出现，记为vu。a)有vu，且v到u的路径中的节点出现次数为”-”或”+”；b)有vu，且u的出现次数为”-”或”+”；c)u与v有共同纯祖先节点r，并且r到两节点的路径中的节点出现次数为”-”或”+”；模式中的约束规则(book,no,(1,11,1),*)(title,no,(2,2,2),-)……(reference,r,(0,23,0),-)(email,no,(4,4,3),*)(name,no,(5,5,3),-)(chapter,r,(8,10,2),-)(author,no,(3,7,2),-)(address,no,(6,6,3),?)(paper,no,(12,22,1),+)10---------------------------------------------------- 规则一（简单叶节点冗余判断）：任一空心叶节点v，在Q中其父节点u，若在S中满足τ(u)τ(v)，则v为冗余节点。叶节点冗余判断referenceauthornamev1v3v4referenceauthorv1v311---------------------------------------------------- 叶节点冗余判断规则二（叶节点冗余判断）：在Q中，任一空心叶节点v，若存在任意节点u，v与u的最近共同祖先为r。若在S中满足:τ(u)τ(v)，并且τ(r)τ(v),τ(r)τ(u),则v为冗余节点。referencenameauthoremailv1v2v3v4referenceauthoremailv1v2v3v4nameauthorv5referenceauthoremailv1v3v4authorv5referenceauthoremailv1v3v412---------------------------------------------------- 非叶节点冗余判断规则三（非叶节点冗余判断）：任一非叶空心节点v,若r为v的父节点，u为v的唯一子节点。若满足下列条件中的一种，则v为冗余节点，删除后的Q’中对应路径为ru。若rvu,则若在S中有τ(r)τ(v),τ(r)τ(u),τ(v)τ(u)；若rv—u,则若在S中有τ(r)τ(v),τ(r)τ(u),τ(v)τ(u)；且u的递归标记为no；若r—vu,则若在S中有τ(r)τ(v),τ(r)τ(u),τ(v)τ(u)；若r—v—u,则若在S中有τ(r)τ(v),τ(r)τ(u),τ(v)τ(u)；且v的递归标记为no；referenceauthornamev1v3v4referencenamev1v413---------------------------------------------------- 同时出现判断方法(reference,-)(book,*)(email,*)(name,-)(chapter,-)(title,-)(author,-)(address,?)(paragraph,+)(paper,+)(book,no,(1,11,1),*)(title,no,(2,2,2),-)……(reference,r,(0,23,0),-)(email,no,(4,4,3),*)(name,no,(5,5,3),-)(chapter,r,(8,10,2),-)(author,no,(3,7,2),-)(address,no,(6,6,3),?)(paper,no,(12,22,1),+)编号同时出现的节点1reference,paper2Book,title,name,author,chapter,paragraph14---------------------------------------------------- 实验存储代价分析冗余节点判断比较判断效率分析15---------------------------------------------------- 存储代价分析编号长度节点等价类(KB)个数个数121413231818331854512156956112322712549538172211359361516100010401701200编号存储空间（KB）16---------------------------------------------------- 冗余节点判断比较冗余节点百分比编号确定路径冗余节点判断分析编号不确定路径冗余节点判断分析节点个数17---------------------------------------------------- 判断效率分析编号查表遍历时间时间(ms)(ms)10.30.120.50.130.10.3421.650.4160.50.770.10.180.51.890.20.21012.39.418---------------------------------------------------- 小结利用模式信息组织和提取约束条件，综合利用这些约束条件对查询树中的冗余节点进行判断，无须人为的增加中间节点。利用模式提供的纯路径隐含约束规则，简化层次结构之间的包含关系，不但可以删除查询树中的叶节点，而且可以在保留叶节点的同时删除某些冗余的中间节点。这种优化可大大提高利用结构连接求解XQuery的执行效率。实验结果证明了这一点。19---------------------------------------------------- 基于直方图的复杂路表达式选择性计算数据的相关性相关工作分析值-位置直方图直方图操作路径选择性计算20---------------------------------------------------- 数据的相关性itemitemitemitemtype=booktype=booktype=papertype=paperprice=1000price=1010price=4price=3(0,25)(1,4)(5,9)(19,24)(2,2)(3,3)(6,6)(7,7)(11,11)(20,20)(23,23)keykey(10,18)(8,8)(17,17)Purchase(12,12)(13,13)(14,14)(15,15)(16,16)keykeykeykey(21,21)key(22,22)key//Purchase/item[type=‘paper’][price>100]×50%×50%=25%值相关//Purchase/item[price<100]/key×50%结构相关21---------------------------------------------------- 相关工作分析相关工作：模式信息提取Lore直方图位置直方图StatiX模式信息＋多维值直方图XSketch问题：缺乏结构和值之间的桥梁22---------------------------------------------------- 基于直方图的选择性计算提出了一种新颖的二位直方图值－位置直方图用于抓住结构与值相关性。提出了用于选择性计算的直方图之间的操作利用执行代价树实现选择性的计算。无需独立性假设，有效的提高了计算的准确性，尤其在数据分布扭曲的情况下。23---------------------------------------------------- 值-位置直方图(VPH)坐标横轴为节点位置编码的start值坐标纵轴为节点值itemitemitemitemtype=booktype=booktype=papertype=paperprice=1000price=1010price=4price=3(0,25)(1,4)(5,9)(19,24)(2,2)(3,3)(6,6)(7,7)(11,11)(20,20)(23,23)keykey(10,18)(8,8)(17,17)Purchase(12,12)(13,13)(14,14)(15,15)(16,16)keykeykeykey(21,21)key(22,22)key24---------------------------------------------------- 位置直方图itemitemitemitemtype=booktype=booktype=papertype=paperprice=1000price=1010price=4price=3(0,25)(1,4)(5,9)(19,24)(2,2)(3,3)(6,6)(7,7)(11,11)(20,20)(23,23)keykey(10,18)(8,8)(17,17)Purchase(12,12)(13,13)(14,14)(15,15)(16,16)keykeykeykey(21,21)key(22,22)key(a)two-dimdistribution(b)PH(c)one-dimdistribution(d)PLHPLH[0][1][2][3]SA1201IA1201AL000025---------------------------------------------------- 直方图运算值选始位置(V)始位置转换(S)选后代(D)选祖先(A)自除后代(PD)自除祖先(PA)。参与运算的是直方图，运算的结果也是直方图。26---------------------------------------------------- 值选始位置(V)运算参数：值-位置直方图VPH[g][m],条件域[Pmin,Pmax]运算结果：始位置直方图SH[g]始位置直方图中格i的计算方法为：SH[i](0≤i＜g)=27---------------------------------------------------- 始位置转换(S)运算参数：位置直方图PH[g][g]，始位置直方图SH[g]运算结果：位置直方图PHP[g][g]位置直方图中格（i,j）的计算方法为：PHP[i][j](0≤i,j＜g)＝PH[i][j]×28---------------------------------------------------- 选后代(D)运算参数：PHA[g][g]，PHD[g][g]输出结果:PHD[g][g]ABCDstartend29---------------------------------------------------- 选祖先(A)运算参数：PHA[g][g]andPHD[g][g]输出结果:PHA[g][g]AendstartDCB30---------------------------------------------------- 自除后代(PD)运算参数：PH[g][g]输出结果:PHPD[g][g]PD(PH)for(m=g-1；m>=0；m--){for(n=0；n<=m；n++){if(PH[n][m]>=0){for(x=n+1；x<=m-1；x++){for(y=x；y<=m-1；y++){PH[x][y]=0;}}}}returnPH;}31---------------------------------------------------- 自除祖先(PA)运算参数：PH[g][g]输出结果:PHPA[g][g]For(m=0,m<=g-1,m++){for(n=m,n<=g-1,n++){if(PH[n][m]>=0){for(x=0,x<=n-1,x++){for(y=m+1,y<=g-1,y++){PH[x][y]=0;}}}}}32---------------------------------------------------- 构造简单代价树(PM)简单路径APH(a)PH(d)PH(ad)A//DDPH(a)PH(d)PH(ad)A//DA/BA/B33---------------------------------------------------- 构造代价树简单谓词[a>b]复杂路径n1/n2//n3//n4[a>v]34---------------------------------------------------- PM方法的缺点太多操作其中包含冗余操作改进：利用模式信息指导跳过一些不必要的操作35---------------------------------------------------- 模式指导的复杂路径表达式估计统计信息模型模式指导的代价树构造实验分析存储代价估计精确性计算效率小结36---------------------------------------------------- 统计信息模型统计信息模型(SI)用三元组[N,E,T]表示。N为节点类型集合，任意节点包含下列属性：N(tagName，Eid,C,R,V,L)E为边集合，表示节点之间的嵌套关系，为了简单起见，不区分属性边，T为直方图与Eid对照表。为了方便查找，我们以Eid为关键字在表上建立了B+树索引。37---------------------------------------------------- 模式指导的代价树构造定理：若路径中某中间节点无谓词约束，无嵌套标记，则该节点对其祖先，后代节点的选择性为100%。定理：若路径表达式某中间节点n2无谓词约束，有嵌套标记，则在形如路径φn1[p1]//n2/n3[p3]中对祖先，或在φn1[p1]/n2//n3[p3]中对后代的选择性为100％。根据上述定理与分析，在构造CT时，可以跳过那些对其他节点选择性为100％的中间节点。38---------------------------------------------------- 模式指导的代价树构造实例39---------------------------------------------------- 实验分析数据集合XMark结构复杂相关性低Bib结构简单相关性高测试方面：存储代价估计精确性估计代价40---------------------------------------------------- 存储代价Storage(KB)GridNum.ineachDim.(g)41---------------------------------------------------- 估计代价EstimationTime/QueryTeimEstimationTime/QueryTeimGridNum.ineachDim.(g)PHandPLHGridNum.ineachDim.(g)PM,SGMandXSketch42---------------------------------------------------- 估计精确性单个谓词RelativeErrorGridNum.ineachDim.(g)GridNum.ineachDim.(g)(a)BibDataSet(b)XMarkDataSetRelativeError43---------------------------------------------------- 估计精确性多个谓词RelativeErrorGridNum.ineachDim.(g)GridNum.ineachDim.(g)(a)BibDataSet(b)XMarkDataSetRelativeError44---------------------------------------------------- 小结提出模式与直方图相结合的统计信息模型，既从整体上把握了数据分布，又保留了局部的细节情况。可有效的提高代价计算的效率。实验证明在数据分布扭曲和数据结构复杂的情况下，本文均能获得有效精确的估计结果。这种方法既可用于最终结果大小的估计，也可用于中间结果计算和选择最优执行计划。45---------------------------------------------------- PatternTree最小简单分解策略问题的提出相关工作分析最小简单分解策略实验小结46---------------------------------------------------- 问题的提出查询分解的必要性PatternTree（PTQ）是复杂的树状结构，需要多个物理操作序列进行求解。查询分解是将PTQ转换为物理操作序列的过程，即将PTQ分解为多个查询片段，每个片断对应一种物理操作。查询分解策略对查询效率的影响分解粒度片断之间的相关性47---------------------------------------------------- 相关工作分析两两分解把路径细分为两两的祖先后代或父子对优点：便于应用导航操作和相关索引缺点：不能有效应用长路径索引跳过中间节点子串分解从路径分支合不确定路径处分解路径为多个子串优点：便于利用结构连接运算处理祖先后代等不确定路径缺点：受特定索引影响，适用于文档的高效过滤。48---------------------------------------------------- 最小简单分解策略定义:给定一个PTQ表达式P(Np,Ep)，若有一PTQ表达式Q(Nq,Eq)为其一个片断，则Q为简单片断当且仅当：(1)片断中最多只有一个节点为查询目标节点。(2)片断中最多只有一个节点是P中的分支节点，且该节点不存在子节点或后代节点。(3)片断中没有分支。片断可看作是PTQ的子树。定义简单片断的目的是为了使每个片断可用一种物理操作实现。每个片断作为优化的一个最小单位。每个简单片断对应一段没有分支的路径。定义：给定一PTQ表达式Q=(VQ,EQ),如果一个片断集合P={p|p是Q中的片断}是Q的一个简单分解，P的每个片断p都是最大的，即Q不存在另一个简单片断p’，且p’p，则P是Q的一个最小简单分解。av1bv2gv3cv4v5*ehfdv6xv7v8v9v10av1bv2gv3cv4v5*ehfdv6xv7v8v9v10av1bv2gv3cv4v5*ehfdv6xv7v8v9v10av1bv2gv3cv4v5*ehfdv6xv7v8v9v10(b)(a)(c)(d)49---------------------------------------------------- 实验测试平台测试集测试用例最小简单分解的有效性最小简单分解的效率50---------------------------------------------------- 测试平台，测试集WinXP中的NativeXML数据管理系统OrientX。P41.6GCPU,256MB内存，60G硬盘。测试集有两个，我们分别选取了规模为100K,1M,10M和20M的文档。Xmark[SWK+02]，数据模式包含550个不同类型的节点。由XMLSPY生成Bib数据集，数据模式含11个不同类型的节点。数据集DTD节点个数DTD规模文档规模文档节点个数遍历时间Xmark5504.3KB100KB1707156ms1MB169151.4s20MB33189430sBib11447B100KB6001317ms1MB590013.5s10MB42140139s51---------------------------------------------------- 测试用例sitelocationitemsiteitemlocationmailboxmailfromrootbibbookpricerootbibbookauthorpaperpagesyear(a)Q1(b)Q2(c)Q3(d)Q4PatternTree实例及最小简单分解52---------------------------------------------------- 最小简单分解的有效性导航策略最小简单分解策略简单分解策略查询执行策略的执行时间比较查询时间（ms）53---------------------------------------------------- 最小简单分解的效率100KB1M20MQ11368186363Q2213106916042Q1,Q2查询时间/分解时间100KB1M10MQ3160015200105600Q4410936529242922Q3,Q4查询时间/分解时间54---------------------------------------------------- 小结最小简单分解方法能够在最大范围内应用大粒度物理操作，从而有效的控制了中间结果的规模和存在周期。目前人们往往采用改进执行算法的方法减少中间结果的规模，而我们从逻辑优化层面找到了高效的解决方案。实验证明，最小简单分解方法是高效的。55---------------------------------------------------- 基于周期累加法的执行顺序选择问题的提出片段中间结果计算简单累加法周期累加法实验小结56---------------------------------------------------- 问题的提出在PTQ中，只有部分节点是需要输出的查询目标节点，其他节点只作为中间结果出现。当某个节点计算完成后，如果没有其他计算需要这个中间结果，则其生存周期结束，就可以让其他的中间结果代替他们在存储空间中的位置。如何在求解过程中尽量避免中间结果的产生和存在周期，是XML查询优化面临的一个关键问题。我们采用周期累加法计算中间结果规模，根据PTQ节点之间的连通性判断中间结果的生存周期，并且在计算时，考虑到相关节点之间的选择性影响，因而能够正确的估计执行时中间结果的规模，从而得到正确的执行顺序。57---------------------------------------------------- 片段中间结果计算生存周期：若执行顺序O1为：，片断中间结果计算方法：若某片断pci的状态为Sci，若与其连接的片断状态为{Sc1,Sc2,…Sck}，且Sc1<…