2007年第12期JISUANJIYUXIANDAIHUA总第148期:100622475(2007)1220010204一种改进的MDX查询优化算法黄立峰,蒋外文(中南大学信息科学与工程学院,湖南长沙410083)摘要:近年来数据仓库成为数据库研究领域中最活跃的一个分支,而该领域的一个核心就是OLAP查询优化问题。多维表达式(MDX)为多条相关的OLAP查询语句同时查询提供了接口。如何利用数据仓库中大量的冗余实化视图去加速OLAP的查询,国外学者对该问题进行了大量分析并提出了一些优化算法。本文对上述算法进行了研究,发现其对实化视图的利用并不充分,于是提出了改进算法并进行了验证。实验表明本算法对查询性能有明显提高。:TP30116文献标识码:AAnImprovedOptimizingAlgorithmforMDXQueryHUANGLi2feng,JIANGWai2wen(CollegeofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083,China)Abstract:Recently,datawarehousebecomesamostactivebranchinthedatabaseresearcharea,andacoreofthisfieldistheproblemofOLAPquery.Multi2dimensionalexpressions(MDX)priovideaninterfaceforaskingseveralrelatedOLAPqueriessimultaneously.InordertoutilizingthehugenumberofredundantmaterializedviewstoaccelerateOLAPoperationsindataware2house,manyforeignresearcherspresentedsomeoptimizationalgorithms.Thispaperstudiesthealgorithms,noticesthefactofthematerializedviews’utilizationratioislower,soitdevelopsanimprovedalgorithm.Experimentsindicatethatthequeryperfor2(Multi2DimensionalExpressions)即MDX。它允许在一条MDX表达式中提出多个相关的OLAP查询。若给定一个实化视图集合,对于这多个相关的OLA0引言近年来随着经济全球化不断深入,不管是跨国公司还是中小企业都感到了前所未有的压力,为了在竞争中脱颖而出,纷纷建立了自己的商务智能系统。而该系统的核心就是数据仓库,它存储着大量的数以TB级的企业历史数据。如何在拥有海量数据的数据仓库中以可以接受的成本提取对企业决策分析有用的信息,国内外学者进行了广泛的研究。比如为了加速OLAP查询,常常采用存储一些冗余数据即实化视图技术等。但大部分论文都假定OLAP查询总是以每次一条的方式送给系统处理,其实在多用户环境下完全可以同时提交若干条OLAP查询。2000年左询来说总是可以找到全局执行时间最小的计划。Zhao等人[2]最早对该问题进行了研究,并提出了三种新的操作及算法:基于哈希星型联接的共享扫描、基于索引星型联接的共享联接、基于哈希及索引星型联接的共享扫描和共享联接。通过这些操作可以找出多个相关并发OLAP查询的共享子任务,如事实表的扫描、哈希表的建立、索引联接中的事实[3]而达到减少执行代价的目的。PanosKalnis等人采用TPC2H和APB标准对文献[2]中的算法在实际环境下进行了检验,发现在很多情况下随着实化视图的增多,执行计划成本反而有所上升。针对这些问题PanosKalnis等人提出了改进的贪婪算法:BV收稿日期:2006211213作者简介:黄立峰(19722),男(土家族),湖南湘西人,中南大学信息科学与工程学院硕士研究生,研究方向:数据仓库应用;蒋外文(19482)男湖南长沙人教授研究方向:多维数据仓库及其应用研究(3)GG(GlobalGreedyalgorithm)算法:与ETPLG算法相似,但它允许修改已经构建好的执行计划。文献[3]对上述算法进行了检验,随着实化视图的增加上述算法并没有取得很好的效果。图1为一个多查询优化的实例,{v1,v2,v3}为实化视图能很好工作,但当某些查询没有对应的实化视图回答时性能有一定程度的下降。采用Jae2youngCHANG等人的研究成果[4],本文对BVF算法进行了改进使它能最大限度地利用已存在的实化视图,从而加速OLAP查询。1相关研究在文献[1]中描述一条MDX语句可以分解成多条SQL查询的集合Q。从而把优化MDX转化为对查询集合Q的优化,并通过寻找和构建集合Q中的共享子任务来优化查询,这种情况和SQL中的多查询优化有一定的相似。文献[1]中的第一个操作为基于哈希星型连接的共享扫描。设q1,q2为能被同一视图v回答的两条查询,从而它们也共享一些或全部维度。为回答q1需要构建哈希表,当查询q2时显然不必重建与q1有公共维度的哈希表,同时也不...