一种改进的MDX查询优化算法

2007年第 12期J ISUANJ I YU X IANDA IHUA总第 148期文章编号 : 1006 22475 ( 2007) 1220010 204一种改进的 MDX查询优化算法黄立峰 ,蒋外文(中南大学信息科学与工程学院 ,湖南 长沙 410083 )摘要 :近年来数据仓库成为数据库研究领域中最活跃的一个分支 ,而该领域的一个核心就是 OLA P查询优化问题 。多维表达式 (MDX)为多条相关的 OLA P查询语句同时查询提供了接口 。如何利用数据仓库中大量的冗余实化视图去加速OLA P的查询 ,国外学者对该问题进行了大量分析并提出了一些优化算法 。本文对上述算法进行了研究 ,发现其对实化 视图的利用并不充分 ,于是提出了改进算法并进行了验证 。实验表明本算法对查询性能有明显提高 。关键词 :数据仓库 : 实化视图 ; MDX; 多查询中图分类号 : TP30116文献标识码 : AAn Im proved O p t im iz in g A lgor ithm for M D X QueryHUAN G L i2feng, J IAN G W a i2wen( Co llege of Info rm a tion Sc ience and Enginee ring, Cen tra l Sou th U n ive rsity, Changsha 410083, Ch ina)A b stra c t: R ecen tly, da ta wa rehou se becom e s a mo st ac tive b ranch in the da taba se re sea rch a rea, and a co re of th is fie ld is thep rob lem of OLA P que ry. M u lti2d im en siona l exp re ssion s (MDX ) p riovide an in te rface fo r a sk ing seve ra l re la ted OLA P que rie s sim u ltaneou sly. In o rde r to u tilizing the huge num be r of redundan t m a te ria lized view s to acce le ra te OLA P op e ra tion s in da ta wa re2 hou se, m any fo re ign re sea rche rs p re sen ted som e op tim iza tion a lgo rithm s. Th is p ap e r stud ie s the a lgo rithm s, no tice s the fac t of them a te ria lized view su tiliza tion ra tio is lowe r, so it deve lop s an imp roved a lgo rithm. Exp e rim en ts ind ica te tha t the que ry p e rfo r2m ace is h ighe r than befo re.Key word s: da ta wa rehou se; m a te ria lized view; MDX; m u lti2que ry(M u lti2D im en siona l Exp re ssion s) 即 MDX。它 允 许 在一条 MDX表达式中提出多个相关的 OLA P查询 。若 给定一个实化视图集合 ,对于这多个相关的 OLA P查0 引言近年来随着经济全球化不断深入 ,不管是跨国公司还是中小企业都感到了前所未有的压力 ,为了在竞 争中脱颖而出 ,纷纷建立了自己的商务智能系统 。而 该系统的核心就是数据 仓库 , 它 存 储着 大量 的数 以TB 级的企业历史数据 。如何在拥有海量数据的数据仓库中以可以接受的成本提取对企业决策分析有用 的信息 ,国内外学者进行了广泛的研究 。比如为了加速 OLA P查询 ,常常采用存储一些冗余数据即实化视 图技术等 。但大部分论文都假定 OLA P 查询总是以每次一条的方式送给系统处理 ,其实在多用户环境下完全可以同时提交若干条 OLA P 查询 。 2000 年左右 微软推出了面向多维数据源的 A P I接口标准即“O lEDB fo r OLA P ” 1 , 在 该 标 准 中 定 义 了 多 维 表 达 式询来说 总 是 可 以 找 到 全 局 执 行 时 间 最 小 的 计 划 。 2 Zhao等人最早对该问题进行了研究 , 并提出了三种新的操作及算法 : 基于哈希星型联接的共享扫描 、基于索引星型联接的共享联接 、基于哈希及索引星型联接的共享扫描和共享联接 。通过这些操作可以找 出多个相关并发 OLA P查询的共享子任务 ,如事实表 的扫描 、哈希表的建立 、索引联接中的事实表过滤 ,从 3 而达到减少执行代价的目的 。 Pano s Ka ln is等人 采用 TPC 2H 和 A PB 标准对文献 2 中的算法在实际环 境下进行了检验 ,发现在很多情况下随着实化视图的 增多 ,执行 计划 成 本反 而有 所 上升 。针对 这些 问 题Pano s Ka ln is等人提 出 了改 进的 贪 婪算 法 : BV F。本文在对 BV F 算法分析时发现 ,大多数情况下算法都收稿日期 : 2006211213作者简介 :黄立峰 ( 19722) ,男 (土家族 ) ,湖南湘西人 , 中南大学信息科学与工程学院硕士研究生 ,研究方向 : 数据仓库应用 ;蒋外文 ( 1948 2) ,男 ,湖南长沙人 ,教授 ,研究方向 :多维数据仓库及其应用研究 。( 3 ) GG ( Globa l Greedy a lgo rithm )算法 :与 ETPL G算法相似 ,但它允许修改已经构建好的执行计划 。 文献 3 对上述算法进行了检验 ,随着实化视图的增加上述算法并没有取得很好的效果 。图 1 为一个多查询 优 化的 实例 , v1 , v2 , v3 为 实化 视图 的 集 合 , q1 , q2 为两个查询 。假定所有查询采用哈希星能很好工作 ,但当某些查询没有对应的实化视图回答时性能有 一 定程 度的 下降 。采 用 Jae2young CHAN G等人的研究成果 4 ,本文对 BV F 算法进行了改进使 它能最大限度地利用已 存在 的 实化 视图 , 从 而加 速OLA P查询 。1 相关研究在文献 1 中描述一条 MDX 语句可以分解成多 条 SQL 查询的集合 Q。从而把优化 MDX 转化为对 查询集合 Q 的优化 ,并通过寻找和构建集合 Q 中的 共享子任务来优化查询 , 这种情况和 SQL 中的多查 询优化有一定的相似 。文献 1 中的第一个操作为基于哈希星型连接 的共享扫描 。设 q1 , q2 为能被同一视图 v回答的两条查询 ,从而 它 们也 共享 一些 或 全部 维度 。为回 答q1 需要构建哈希表 ,当查询 q2 时显然不必重建与 q1有公共维度的哈希表 ,同时也不必再次扫描视图 v。 在文献 3 中给出了执行代价的计算公式 :设 Q 为一个查询集合 , MV 为实化视图集合 ,且 qQ , m vMV。如果 v被不止一个查询使用 ,则它对 整个执行代价的贡献为 :型 , t= 1 , t( v) = Size ( v) /10 , t( q, m v ( q) )I/Oha sh_ jo inCPU22= 10 。 GG算法将把使查询代价增加最小的视图和查询联接起来 ,如 q1 与 v1 , q2 安排给 v2 ,则整个代价 为 277. 5 ,而 q1 , q2 用 v3 查询的话代价为 224。可见当存在多张实化视图可以回答查询时 , GG算法并没 有找到较优的方案 。tha sh( v) = Size ( v) tI/O + tha sh_ jo in ( v)( 1 )MV图 1 多查询优化问题实例 | v1 | =100, | v2 | =150, | v3| =200为了克 服 这 个 问 题 文 献 3 提 出 了 BV F ( B e st V iew F irst)算法 , 简单地说就是 : 不是采用一个一个 地增加查询来构建查询计划 ,而是使用至顶而下的方 式 ,每次迭代总是选择最有贡献的视图 (基于共享操 作对查询 Q 最有利 )加入全局计划 ,直到所有的查询 都被覆盖时结束 。作者已证明 BV F提供的计划随实 化视图数量的增加单调下降 。大多数情况下 BV F 算 法能工作得很好 ,当一部分查询没有找到适当的实化 视图来回答时 ,性能有一定程度的下降 。2 改进算法我们知道大部分 OLA P 查询基本上都是聚集查 询 ,提高实化视图的利用率可以避免查询巨大的事实 表 ,从而大大改进 OLA P查询 。正是由于没有恰当的 实化视图 ,才造成 BV F 算法性能的下降 。当前在利 用实化视图方面存在很多限制 ,如 : 当实化视图不包 括查询的某个属性时 ,就不能利用该视图 。针对这个 问题文献 4 进行了研究 ,发现当实化视图满足一定 条件时经过处理完全可以利用 。这里简要陈述一下其核心思想 ,为了表达方便 , 所有查询和视图都采用关系代数表达 ,以下是将使用 的一些概念 : p R:用属性 p 投影关系 R。 c R:选择满足谓词 c关系 R 中的所有行 。 S :自然连接 S中所有关系 。Size ( v)为 v中元组数量 , tI/O 为把一个元组从磁盘读入内存所需时间 , tha sh_jo in为 v中的维建立哈希表和执 行哈希连接所需时间 。假定 q能被实化视图 v回答 ,其 中 vmv ( q) ,则整个执行代价的增加部分为 :tha sh( q, m v ( q) ) = Size (m v ( q) ) tCPU ( q, m v ( q) )( 2 )q 中 )QtCPU ( q, m v ( q ) ) 为每个元组处理选择 (在和评估聚集函数所花时间 。设 MV 为 MV 的子集且被选择来回答 Q 中的查询 ,则整个执行计划代价为 :tha shha shha sh tMV ( v) +tQ ( q, m v ( q) )( 3 )to ta l =qQ , m v ( q) MV vMV 寻找优化执行计划等价于使 tha sh最小 ,这是一个to ta lN P难度问题 。第二个操作为基于索引连接的共享扫描 。设 q1 , q2 能被同一视图 v所回答 ,假定每个维度与视图 v建有位 图索引连接 。采用“或 ”操作将两张位图合并为一张共享位图 ,并用它去搜索视图 v,再根据各自的过滤器分别聚集 。其执行代价与前面相似 ,唯一不同是它能根据索 引的选择性 (见文献 3 )进行调整 。第三个操作为前两个操作的综合即基于哈希和索引星型连接的共享扫描 ,即前面两种操作的联合 。 文献 2 中提出了三种算法来构建执行计划 :( 1 ) TPLO ( Two Pha se Loca l Op tim a l a lgo rithm )算 法 :分别为每个查询构建优化执行计划 ,然后合并为统一的执行计划 。( 2 ) ETPL G ( Extended Two Pha se Loca l Greedy a l2 go rithm )算法 :递增式地构建执行计划每次增加一个 优化的查询 。12计 算 机与现代 化2007年第 12期W h ile AQ If AQ 中的 q i没有视图匹配Then 调用 Greedy_ sea rch ( q, MV )得到重写查询 q i/ / newSe t为共享操作的查询集合newSe t. que rie s = q iGloba lp lan = Globa lp lannewSe tAQ = AQ 2 qAQ; q已被重写 e lse 设 be st_view为最有贡献视图newSe t. an swe red_by_view = be st_viewnewSe t. que rie s = qAQ: q为 be st_view所回答 Globa lp lan = Globa lp lannewSe tAMV = AMV 2be st_viewAQ = AQ 2 qAQ: q为 be st_view 所回答 R e tu rn Globa lp lan 其中找到查询重写的算法如下 : 算法 Greedy_ sea rch ( q, MV )Op tim a lQ ue ry = q W h ile ( TUR E) M axCo stSaving = 0 fo r each vMV fo r each renam e of Op tim a lQ ue ry and v if Op tim a lQ ue ry and v满足充分条件 q= R efo rm u la tion (Op tim a lQ ue ry, v, Co stSavin)if co stsaving M axCo stSaving M axCo stSaving = co stsavingCu rren tOp tim a l = qIf M axCo stSaving = 0R e tu rn Op tim a lQ ue ryE lse Op tim a lQ ue ry = Cu rren tOp tim a lG g, a R:按照属性集合 g分组集表达式 a。a ttr ( R ) : R 中关系的属性集合 。R ,然后应用聚基于这些假定 ,查询 Q 和实化视图 V 可以表示为 :Q: p (Q ) , a (Q ) R T V: p (V ) , a (V ) R S G g (Q ) , a (Q ) c (Q ) G g (V ) , a (V ) c (V ) R 是 Q 和 V 中公共关系的集合 , T是 Q 中的关系集合但不属于 V , S是 V 中的关系集 合但 不属 于 Q , T和 S没有任何公共属性除了参与 Q 和 V 的自然 连接外 。考虑图 2所示的查询树 , ( a)中表示为 Q 的一颗查询树 , ( b)是 Q 的一颗等价查询树 ,对 R 的一些操作转化为查询子树 A。假定视图 V 包含产生子 树 A 所有的行和属性 ,那么就可以用 V 来替代 A ,其中谓词 c (Q )被分解为 c 和 c ”,找到 Q 的能利用 V的重写查询 Q ,就可优化查询 。图 2 Q 的等价查询树由于篇幅所限不再详述 , 仅给出 ( a ) , ( c ) 查询 树等价的充分条件 ,详细内容参见文献 4 。充分条件 :( 1 ) S在 V 中为无用连接和选择 ,存在谓词集合 c, c由c (V )中的属性并上 a ttr ( T)组成 , c (Q )等价于 ccR (V ) 。( 2 )存在 g和 a, G g (Q , a (Q ) 能分解为 G g, a和G gR (V ) , aR (V ) 。( 3 )设 m = a | aa ttr ( R ) ,同时 a在 c中 、gp (Q )中或 a ttr ( R ) a ttr ( T)中提及 2p (V ) ,从而 m 要么为空要么通 过连接别的视图而得到恢复 。显然当 BVF算法中的某些查询无法找到恰当的实 化视图时 ,如满足上述充分条件 ,则可以得到重写查询从而避免查询事实表 。下面给出改进算法的伪码 。算法 BV F_P (MV , Q )/ / MV = v1, v2, , v |MV | 为实化视图的集合/ / Q = q1, q2, , q |Q | 为查询集合AMV =MV / /AMV 为没有分配的实化视图集合AQ = Q / /AQ 为没有分配的查询集合Globa lp lan = 分析与结论首先我们对改进算法进行定性分析 ,算法3Greedy_ sea rch ( q, MV )的时间复杂度 O ( |MV | | q | 2 ) 。如果Q 中的查询全部都能在 MV 找到匹配的视图 ,则改进算法与 BV F的时间复杂度相一致为 O ( |MV | | Q | 2 ) 。算法 BV F_H (MV , Q )最坏情况发生在 Q 中查询都没有适当视图匹配将调用算法 Greedy_ sea rch ( q, MV ) ,此时为多项式时间复杂度为 O ( |MV | 2 | q | 2 |Q | ) 。而 由于没视图可利用 BV F算法时间复杂度将变为 O ( | F | |Q | 2 ) ( | F |为事实表的行数 ) ,显然 | F |要远大于 |MV | 2 ,因此使用改进算法可以获得更好的查询性能 。的谓词操作等 。进一步的工作 ,将研究如何有效地使多查询优化算法与 cache控制技术相结合 ,从而更好 地发挥 MDX查询的优点 。参考文献 :M ic ro soft Co rpo ra ted . OL E DB fo r OLA P D e sign Sp ec ifica2 tion DB /OL . h ttp: / /m sdn2. m ic ro soft. com / en2u s / li2 b ra ry /m s145506. a sp x, 2006 207 221.Zhao Y, D e shp ande P M , N augh ton J F, Shuk la A. Sim u lta2 neou s op tim iztion and eva lua tion of m u ltip le d im en sion que2 rie s J . S IGMOD R eco rd, 1998 , 27 ( 2 ) : 271 2282.Pano s Ka ln is, D im itris Pap ad ia s. M u lti2que ry op tim iza tion fo r on2line ana lytica l p roce ssing J . Info rm a tion System ,2003, 28 ( 2) : 4572473.J ae2young Chang, H an2joon Kim. P roce ssing aggrega te que rie s w ith m a te ria lized view s in da ta wa rehou se environ2 m en t J . IE ICE2TRAN S. IN F&SYST. , 2005, 88 ( 4 ) : 726 2738. 1 2 图 3 实化视图表的数量其次我们采用 TPC2H 数据库对算法进行了比较 实验 ,实验平台为 : CPU 为 P III733 ,操作系统为 W in2 dow s 2000 Se rve r,编程工具为 V isua l C + 6. 0。发现 改进算法获得了较高的重写查询率 。从图 3 的实验 图表中 ,可以看出改进算法比原算法重写查询率要高15 % 38 % ,从而使执行代价有 5 % 11 %左右幅度 的下降 。本算法也存在一些不足之处 ,如不支持复杂 3 4 (上接第 9页 )5 结论及展望系统 成 功 实 现 了 多 分 辨 率 造 型 技 术 与 基 于 NURB S的参数曲面造型技术的融合 , 既可以进行传 统方式造型又可以进行三角网格划分 、网格化简 、几 何形体小波 分解 与重 构等 操 作 , 丰富 了 系 统 造 型 手 段 ,提高了处理复杂形体的能力 。但本系统还需要进 一步完善 ,例如 ,交互编辑功能需要增强