(论文)XML流数据查询结果的缓存管理

万方数据 杨卫东等：帆流数据查询结果的缓存管理2 0 8 1 能( f I l l l f l e d g e ) 演算系统，对于后一种情况，则需要使用缓存来管理结果或中间结果然而在基于x Q u e r y 的订L 流处理系统中，结果集的缓存管理通常是必需的，而且更为复杂 本文的工作集中于x M L 流环境下x Q u e 哆查询的缓存结果管理，迄今为止，这方面的研究工作还未受到应 有的重视与已有研究相比，本文工作主要包括： ( 1 ) 为了能够有效减少缓存的内存耗费，提高处理性能，指出x Q u e r y 结果集的缓存管理方法和应该遵循 的基本原则； ( 2 ) 通过运行时栈驱动的基于二进制的前缀编码，在运行时确定结果集中节点之间的关系，尽早构成返 回结果元组，避免了中间结果集之间的连接操作： ( 3 ) 支持递归文档的处理，通过定义一个查询的最低公共祖先谓词查询节点( 1 0 w e s tc o n l n l 锄c e s t o r p r e d i c a ：c cq u e r yn o d e ，简称L C A P Q N ) 来帮助尽早删除缓存中的节点，而不是等到整个文档结束之后 本文第1 节介绍相关研究工作，第2 节介绍X Q u e 巧的表示以及查询匹配算法第3 节集中讨论x Q u e D ，结 果集的缓存管理方法第4 节给出实验结果与分析第5 节给出本文的结论 1 相关研究工作 目前，已提出各种方法来处理皿。流数据，例如，基于自动机的方法 3 - 8 】、基于索引的方法【9 1 、基于B o o m F i l t e r 的方法【1 0 1 、基于p r n f e r 序列的方法【1 1 】以及其他方法【1 2 - 15 1 ，其中，大部分研究工作集中于v I L 数据流的查 询匹配技术，主要考虑的是改进x M L 流的查询匹配性能和查询处理的空间耗费，而较少考虑查询结果集的缓存 管理 就我们所知，迄今为止只有少量的x M L 流处理系统对相关缓存问题进行了初步研究例如，x s Q 0 7 】利用层 次的增强有限自动机来处理x P a t h 与x M L 流数据的匹配，其中也初步讨论了针对，a t h 的缓存管理问题X S Q 使用缓存区暂存可能的结果，其缓存操作是由自动机驱动的；文献【1 6 】针对基于x P a t h 带有谓词的全功能演算系 统讨论了缓存管理的最低边界，并给出相应算法，但是该方法只能处理非递归文档上面两项研究工作都没有讨 论基于x Q u e r y 的江L 流处理系统的缓存管理问题，文献 1 6 】称这是其下一步的工作T u r b o x P a t h 【l7 】讨论了 x Q u e f y 的缓存问题，但缓存中存放了一些中间结果，并需要在最后对中间结果进行元组集合之间的连接操作 F l u x 【1 8 】系统使用x M L 流的D T D 模式来减少x Q u e r y 计算时的缓存耗费，因而只适用于特定的情况需要指出 的是，这些研究工作都只能处理单个查询的查询匹配和 x 万方数据 2 0 8 2 面删口，脚册软件学报v 0 1 1 9 ，8 ，A u g l l s t2 0 0 8 f 缸s bi nd o c ( “，b i b x m l ”) ，b o o k w h e r c $ b p u b l i s h e “t e x t ( ) = “A d d i s o n W b s l e y ”锄d $ b y e a r 1 9 9 l r e t I l m ( b o o k ) $ b t i t l c $ b y e 盯 ( b o o k ) F i g 1 As 锄p l eX Q u e r y 图1x Q u e r y 示例 F i g 2C o 唧a c tq u e r yt r c eo f t h es a m p l eX Q u e 巧 图2X Q u e r y 示例的紧凑查询树 2 2 查询匹配算法 在对订L 流处理的过程中，我们对带有谓词的节点及其子节点采用自底向上的匹配过程；对于其他部分采 用自顶向下的匹配过程算法基于运行栈，分为O P E N 和C L O s E 两部分 o P E N ： 0 P E N 事件通过回调函数调用该旬柄，传入事件名字、元素名字和元素的文档层次 对每一个到达的沮。元素进行节点测试和文档层次检查 如果节点检查返回T R u E ( 事件名、节点名、文档层次匹配) ，则该节点被压入一个运行时栈若遇到的 节点是P Q N o d e 或谓词子树的子节点，则其状态标记的值设为F A L S E 若遇到的节点是一个查询的接受 节点且不是P Q N o d e 节点，则一个查询匹配发生如果该接受节点是P Q N o d e ，则需要等遇到C L O S E 事 件时才能判定文档与查询是否匹配 C L O S E ： 如果遇到的节点是0 Q N o d e ，则简单地将节点从栈中弹出如果遇到的节点是P Q N o d e 或谓词子树的子节 点，则执行下列步骤： 如果是叶子节点，则将其状态标记赋为T R U E ，意味着该节点匹配成功从运行栈弹出该节点，并将当前 栈顶节点( 当前栈顶节点是其父节点) 中相关的逻辑表达式中对应的项赋值为T R U E 如果是谓词子树中的中间节点，则计算其逻辑表达式( 此时，它的孩子节点都已处理过) 如果逻辑表达式 的值为T R U E ，则意味着该节点匹配，将其状态标记赋值为T R u E ；否则，将其状态标记赋值为F A L s E 从 栈中弹出该节点，并将当前栈顶节点的相关逻辑表达式中的对应项赋值为其状态标记的值( T R u E 或 F A L S E l 如果是一个查询的接受节点，则计算其逻辑表达式，并将逻辑表达式的结果赋给状态标记如果是 T R u E 则文档与该查询匹配；如果是F A L S E ，则文档与该查询不匹配 万方数据 万方数据 2 0 8 4 ( a ) D o c u m 朋te x a m p l cD ( 幻文档例子D l 励删口，矿孓咖忧脚软件学报v 0 1 1 9 ，N o 8 ，A u g u s t2 0 0 8 ( b ) Q l ( ”Q l ( c ) D o c u m e n te x 锄p l e b ( c ) 文档例子D 2 ( d ) Q 2 ( d ) Q 2 F i g 3S a n l p l e so fq u e r i e sa n dd o c u m e 曲 图3 查询和文档示例 3 2 基于运行时栈的前缀编码表示 各缓存池中的节点之间的关系比较复杂，例如祖先后代关系、父子关系、兄弟关系、共同祖先关系等，利 用基于前缀的编码方法可以快速判断( 常量时间) 它们之间的关系在实际实现中，我们使用二进制串前缀编码 方案【19 1 ，如图4 所示( 节点1 0 不是节点O 1 0 的祖先节点；节点0 1 0 与0 1 l O 是兄弟节点) 由于我们只需要在返回 结果的缓存管理时才会使用文档节点的二进制编码信息，因此，我们不是对整个文档编码，而是只对进入运行时 栈的节点编码，这样可以通过缩小编码的范围来提高处理效率 定理1 在第2 2 节的查询匹配算法中，对于x M L 文档D ( 它对应于一棵文档树乃和查询Q ，进入运行时栈 查询节点所对应文档元素构成了一棵文档树丁7 ，r 7 与原文档树r 同根，并且是r 的一棵子树 例如，图5 的右面是用户提交的查询Q 3 ，左面表示的是对应的一棵x M L 文档树D 3 在x M L 流处理过程中， 对于查询Q 3 ，进入运行时栈的节点对应的x M L 文档部分就是在文档树中用曲线勾勒出来的部分，它构成一棵 与原文档的同根的子树因此，由运行时栈驱动进行的前缀编码，只是对整个X M L 文档的一部分进行编码，而同 时又能正确地反映文档节点之间的关系 0 OO 1 0 O 1 1 01 0 O D 3Q 3 F i g 4 B i n a r y - C o d ep r e f i x F i g 5 R u n t i m e - S t a c k - D r i V e np r e f i xc o d es a m p l e 图4 二进制前缀编码图5 运行时栈驱动的前缀编码示例 3 3 删除操作 在对x M L 流的查询处理过程中，由于查询匹配的失败，某些缓存的元素应该及时删除，以节省缓存的内存 耗费以及提高性能这一点很容易实现如图6 所示，当遇到6 1 的结束标记时，可以确定6 1 和c l 不满足查询匹配 条件，因此，这时应该及时将6 1 和c 1 从缓存中删除( 如图6 中的B z 痧“所示) 另一种需要执行删除操作的情况是，在查询匹配成功时，除了要向用户分发查询结果集以外，直观上讲，同 时也应该从缓存中删除相应节点( 如图6 所示，在查询匹配成功时，( 6 2 ，c 2 ，龙) 构成返回结果的一个元组，则在向用 万方数据 杨卫东等：沮。流数据查询结果的缓存管理 只甲 然一 囵) 越习 2 口尼1 口 3 ( c 2 ) ( 1 e 2 ) 匝橱 D ， Q 5 口口 B u f f e r s F i g 7E x a m p l e so f b u f f c rn o d e se l i m i n a t i o n 图7 缓存节点删除例子 万方数据 2 0 8 6 J o u r n a lo fS o f t w a r e 软件学报V 0 1 1 9 ，N o 8 ，A u g u s t2 0 0 8 对于递归的嵌套文档，并且查询中的L C A P Q N 与返回节点之间包含”，就可能会出现这样一种情况：文档 中存在着处于不同层次上的多个节点与L C A P Q N 对应，这时，只能在遇到相应的最外层节点的关闭标记时执行 缓存的删除操作 3 4 多查询的缓存管理 前面讨论了针对单个查询的缓存管理问题在实际系统中，X M L 流数据处理系统通常面对的是大量用户， 因此要求系统具有同时处理大量查询的能力而来自用户的大量查询中，可能会具有许多共同的部分，共享其共 同部分可以节省系统的存储空间和执行时间，对改善系统性能非常重要我们将所有X Q u e r y 的紧凑查询树合并 为一个单一的共享前缀的紧凑查询树其中，节点名以及算子( “”或“”) 相同的前缀可以合并另外，若返回结果 中的节点是一个多个查询共享的节点，则缓存结果节点的缓存池被这些查询所共享( 合并方法类似于我们前面 的工作【1 2 1 ) 与共享前缀的紧凑查询树中的其他节点一样，共享的结果节点的缓存池关联有查询标识如果两个 缓存池被多个查询共享，则两个缓存池构成的缓存池链也同样被共享缓存结果的共享可以有效节省缓存空间 以及优化构造缓存结果元组的性能但是，缓存的共享可能延迟共享缓存节点的删除时间，因为对于一个查询而 言，可以删除的缓存节点可能还会被其他查询使用，而只有当共享该缓存节点的所有查询都认为这个节点“无 用”时，才可将其从缓存中删除 4 实验 我们用J a v a 实现了原型系统，称为L e o X S S I I 其中，使用I B M 的基于事件的X M L 解析器【2 0 1 系统运行的环 境是E c l i p s e 3 1 ，机器主频为2 7 G 内存为5 1 2 M 所有的实验都运行于W i n d o wX P 专业版我们使用X M a r k 2 l J ， D B L P t Z Z l 两个数据集进行实验在处理单个查询的情况下，我们通过改变查询的谓词节点个数( 表示查询的分支 数目) 、路径长度、“，广和“，出现的个数来产生查询实例，数据集的大小是8 M 一3 2 M 不等实验结果表明，在单查 询情况下，几乎对所有情况，内存耗费基本保持在常量( 不到1 M ) ，文档大小对其影响不大，处理时间随着X M L 文 档大小的逐步增加( 从8 3 m s 增加到1 6 5 m s ) 可以看出，单查询情况下系统通常表现良好 我们重点考虑在在同时处理大量X Q u e r y 的情况下，L e o X S S I I 在性能和内存使用方面的情况实验的度量 指标如下：( 1 ) 输入文档的大d 、, ( 1 0 K ，2 0 K ，5 0 K ，I M ，3 M ) ；( 2 ) 查询的数目( 50 0 0 - 1 0 00 0 0 ) ；( 3 ) 谓词节点的数目( 3 个) ；( 4 ) 返回结果所包含的元素个数( 1 个一3 个元素) 这里使用的数据集是D B L P , 使用X m a r k 数据集的结果与此 类似 图8 首先给出针对小文档的部分实验结果以查询的分支节点( P Q N o d e ) 数是3 、返回节点数是3 为例，我们 用查询生成器生成X Q u e r y ( 扩充Y F i l t e r 的查询生产器) ，其参数是：60 20 2 一h u mn e s t e 劫a t h s = 3 一 d i s t i n c t - - - T R U E ，其中。6 表示查询深度，两个0 2 表示“广和“轳出现的概率，3 表示谓词节点数，T R U E 表示每个查询 都不相同实验结果如图8 所示，其中，纵轴表示时间( m s x l 0 ) ，横轴表示查询个数，分别为50 0 0 ，1 0 0 0 0 ，5 00 0 0 ， 1 0 00 0 0 ，文档的大小为1 0 K ，2 0 K ，5 0 K 图9 显示了在文档大小为3 M 的情况下，系统内存的使用情况：随着查询数 目的增加，系统使用的内存逐步增加当查询数目很大时，每一个查询数目的返回结果数目虽然不同，但整体分 布情况大致相似，因此，对内存的使用影响不大 F i g 8E x p e r i m e n t1 图8 实验1 F i g 9E x p e r i m e n t2 图9 实验2 万方数据 杨卫东等：X M L 流数据查询结果的缓存管理 在图1 0 中，文档的大小分别是1 M 和3 M , X 轴表示查询的数目从50 0 0 递增到1 0 00 0 0 ，Y 轴表示性能的变 化情况，图表反映的是随着查询数目的递增( 从50 0 0 到1 0 0o o o ) ，查询的返回结果所包含元素的数目的变化，在 输入文档流分别为1 M 和3 M 的情况下，系统性能的变化情况由实验结果可以看出，随着查询数据的增加以及 文档大小的增加( 从1 M 到3 M ) ，系统的运行时间逐步递增当查询数目从5 00 0 0 增加到1 0 00 0 0 时，系统处理时 间增加幅度较大而输出结果包含的元素个数( 这里没有考虑输出结果的分布情况，即它们之间是祖先关系还是 兄弟关系等) ，对系统性能的影响也不明显 5 结束语 F i g 1 0E x p e r i m e n t3 图1 0 实验3 目前，X M L 流数据环境下，针对X Q u e r y 的返回结果的缓存管理还缺乏系统的研究，只有少数文献对此进行 了初步讨论与已有的研究工作相比，我们的方法具有如下的特点：利用运行时栈驱动的二进制前缀编码及早构 造结果元组，避免了大量中间结果节点之间的连接操作；能够及早删除“无用”节点；支持多查询的缓存管理进一 步的工作是完善我们的系统，并研究如何在分布环境下有效地向用户点对点地分发返回结果 1 h f e r e n e e s ： 【l 】X Q u e r y1 O ：A nX M Lq u e r yl a n g u a g e 2 0 0 7 h t t p ：l l w w w w 3 o r g T R x q u c r y f 2 】B e r g l u n dA ，B o a gS ，C h a m b e r i nD ，F e r n a n d e zM F ，K a yM ，R o b i eJ ，S i m e o nJ X M Lp a t hl a n g u a g e ( X P a t h ) 2 0 W 3 C 2 0 0 4 h t t p ：l l w w w w 3 o r g T R x p a t h 2 0 1 3 1 A l t i n c lM ，F r a n k l i NM J E f f i c i e n tf i l t e r i n go fX M Ld o c u m e n t sf o rs e l e c t i v ed i s s e m i n a t i o no fi n f o r m a t i o n I n ：A b b a d iA E ，B r o d i e M L ，C h a k r a v a r t h yS ，D a y a lU ，K a m e lN ，S c h l a g e t e rG ，W h a n gK Y ，e d s P r o c o ft h eV L D B2 0 0 0 S a nF r a n c i s c o ：M o r g a n K a u f m a n nP u b l i s h e r s 2 0 0 0 5 3 “ 4 1 D i a oY L ，A l t i n e lM ，F r a n k l i nM J ，Z h a n gH ，F i s c h e rP P a t hs h a r i n ga n dp r e d i c a t ee v a k m t i o nf o rh i g h - p e r f o r m a n c eX M L f i l t e r i n g A C MT r a n s o nD a t a b a s eS y s t e m ，2 0 0 3 ，2 8 ( 4 ) ：4 6 7 - 5 1 6 【5 】 G u p t aA ，S u c i uD S t r e a mp r o c e s s i n go fX P a t hq u e r i e sw i t hp r e d i c a t e s I n ：H a l e v yA Y ，I v e sZ G ，D o a nA H ，e d s P r o c o ft h eA C M S I G M O DC o n f S a nD i e g o ：A C MP r e s s ，2 0 0 3 4 1 9 - - 4 3 0 【6 】 G r e e nT J ，M i k l a nG 。O n i z u k aM ，S u c i uD P r o c e s s i n g Ls t r e a m sw i t hd e t e r m i n i s t i ca u t o m a t a I n ：C a l v a n e s eD ，L e n z e r i n iM ， M o t w a n iR ，e d s P r o c o f t h eI C D T2 0 0 3 B e r l m ：S p r i n g e r - V e r l a g 。2 0 0 3 1 7 3 - 1 8 9 【7 】P e n gF ，C h a w a t h eS S X S Q ：As t r e a m i n gX P a t he n g i n e A C MT r a n s o nD a t a b a s eS y s t e m s ，2 0 0 5 ，3 0 ( 2 ) ：5 7 7 - - 6 2 3 【8 】 G a oJ ，Y a n gD Q ，T a n gS W ，W a n gT J T r e e - A u t o m a t ab a s e de f f i c i e n tX P a t he v a l u a t i o no v e rX M Ld a t as t r e a m J o u r n a lo fS o f t w a r e ， 2 0 0 5 ，1 6 ( 2 ) ：2 2 3 - 2 3 2 ( i nC h i n e s e 晰t hE n g l i s ha b s t r a c t ) h t t p ：w w w j o s o r g c n 1 0 0 0 9 8 2 5 1 6 2 2 3 h u n 【9 】 B r u n oN ，G r a v a n oL ，K o u d a sN ，S r i v a s t a v aD N a v i g a t i o n v 鑫i n d e x - b a s e dX M Lm u l t i q u e r yp r o c e s s i n g I n ：D a y a lU ， R a m a m r i t h a mk V i j a y a r a m a nT M ，e d s P r o c o f t h eI C D E2 0 0 3 L o sA l a m i t o s ：I E E EC o m p u t e rS o c i e t y ，2 0 0 3 1 3 9 1 5 0 【1 0 】G o n gX Q ，Q i a nW N ，Y a nY ，Z h o uA Y B l o o mf i l t e r - b a s e dX M Lp a c k e t sf i l t e r i n gf o rm i l l i o n so fp a t hq u e r i e s I n ：P r o c o ft h e I C D E2 0 0 5 T o k y o ：I E E EC o m p u t e rS o c i e t y 2 0 0 5 8 9 0 - 9 0 1 【l l 】K w o nJ ，R a oP ，M o o nB ，L e eS F I S T ：S c a l a b l cX M Ld o c u m e n tf i l t e r i n gb ys e q u e n c i n gt w i gp a t t e r n s I n ：B 0 h mk J e n s e nC S ， H a a sL M ，K e r s t e nM L ，L a r s o nP A ，O o iB C ，e d s P r o c o f t h e D B2 0 0 5 T r o n d h e i m ：A C M ，2 0 0 5 2 1 7 - 2 2 8 万方数据 2 0 8 8 【1 2 】 【1 3 D 4 I 1 5 】 【1 6 】 1 7 】 【1 8 】 1 9 】 【2 0 】 2 q 【2 2 】 J o u r n a lo fS o f t w a r e 软件学报V 0 1 1 9 ，N o 8 ，A u g u s t2 0 0 8 Y a n gW D ，S h iB L C o m p l e xt w i gp a t t e r nq u e r yp r o c e s s i n go v e rX M Ls t r e a m s J o u r n a lo fS o f t w a r e ，2 0 0 7 ，l8 ( 4 ) ：8 9 3 - 9 0 4 ( i n C h i n e s ew i mE n g l i s ha b s t r a c t ) h t t p ：w w w j o s o r g c n 1 0 0 0 9 8 2 5 1 8 8 9 3 h t m H o uS ，J a c o b s e nH A P r e d i c a t e B a s e df i l t e r i n go fX P a t he x p r e s s i o n s I n ：R e u t e rA ，W h a n gK Y ，Z h a n gJ J ，e d s P r o c o ft h e2 2 n d I E E EI n t lC o n f o nD a t aE n g i n e e r i n g P i s c a t a w a y ：I n s t i t u t eo fE l e c t r i c a la n dE l e c t r o n i c sE n g i n e e r sC o m p u W rS o c i e t y ，2 0 0 6 5 3 C h e nY ，D a v i d a o nS B ，Z h e n gY F A ne f f i c i e n tX P a t hq u e r yp r o c e s s o rf o rX M Ls t r e a m s I n ：L i uL ，R e u t e rA ，W h a n gK Y ，J JZ h a n g ， e d s P r o c o ft h e2 2 n dI E E EI n t lC o n eo nD a t aE n g i n e e r i n g P i s c a t a w a y ：I n s t i t u t eo fE l e c t r i c a la n dE l e c t r o n i c sE n g i n e e r s C o m p u t e rS o c i e t y ，2 0 0 6 7 9 C a n d a nK S ，H s i u n gW P ，C h e nS T ，T a t e m u r aJ A g r a w a lD A F i l t e r ：A d a p t a b l eX M Lf i l t e r i n gw i t hp r e f i xc a c h i n ga n ds u f f i x c l u s t e r i n g I n ：D a y a lU ，W h a n gK Y ，L o m e tD B ，A l o n s oG ，L o h m a nG M ，K e r s t e nM L ，C h aS K , K i mY ke d s P r o c o ft h eV L D B 2 0 0 6 S e o u l ：A C M 2 0 0 6 5 5 9 - 5 7 0 Y o s s e fZ B ，F o n t o u r aM ，J o s i f o v s k iV B u f f e r i n gi nq u e r ye v a l u a t i o no v e rX M Ls t r e a m s I n ：L iC ，e d P r o c o ft h eP O D S2 0 0 5 N e wY o A ：A s s o c i a t i o nf o rC o m p u t i n gM a c h i n e r y ，2 0 0 5 2 1 6 - 2 2 7 J o s i f o v s k iV ，F o n t o u r aM ，B a r t aA Q u e r y i n gX M Ls t r e a m s T h eV L D BJ o u r n a l ，2 0 0 5 ，1 4 ( 2 ) ：1 9 7 - 2 1 0 K o c hC ，S c h e r z i n g e rS ，S e h w e i k a r d tN ，S t e g m a i e rB S c h e m a - B a s e ds c h e d u l i n go fe v e n tp r o c e s s o r sa n db u f f e rm i n i m i z a t i o nf o r q u e r i e so ns t r u c t u r e dd a ms t r e a m s I n ：N a s c i m e n t oM A ，0 z s uM T ，K o s s m a n nD ，M i l l e rl U ，B l a k e l e yJ A ，S c h i e f e rK B ，e d a P r o