基于Cache的聚集查询推送:一种有效的分布式查询处理机制
Cache-Based Aggregate Query Shipping: An Efficient Scheme of Distributed OLAP Query Processing
-
摘要: 1.本文的创新点本文包括以下主要创新点: (1)本文提出了聚集查询推送和可重用聚集查询推送两个分布式查询优化技术,以及支持两项新技术的增强型分布式查询处理引擎。分布式查询处理引擎基于查询表达式的代数等价变换,得到聚集查询推送计划或可重用聚集查询推送计划,并利用全局代价估计模型动态选择高效的查询推送计划。(2)本文综合语义缓存和动态视图缓存两种技术的优点,提出了复合视图缓存机制。该缓存机制支持聚集查询处理结果的缓存,有效地进行部分匹配处理。2.实现方法上述技术的主要实现方法如下。(1)聚集查询推送计划、可重用聚集查询推送计划和动态计划选择分布式查询处理引擎通常采用动态规划算法产生分布式查询计划。动态规划算法的重点是优化连接运算顺序,聚集和分组运算需要等到所有连接运算完成了以后才能执行。这样即使数据源具有聚集和分组运算能力,也无法将查询中包含的聚集和分组运算推送到数据源中执行。这样产生的分布式在线分析处理(OLAP)查询计划不够高效。本文将聚合分组转换原理应用在支持异构数据集成的分布式查询优化技术中。通过查询表达式的代数等价变换,在不改变查询操作语义的前提下,在连接运算之前构建出局部聚集/分组运算。然后,通过组合局部聚集运算与远程扫描运算,形成新的远程运算符:R_Agg或RR_Agg,实现聚集运算及可重用聚集运算推送处理。引入查询结果重用机制后,查询代价估计成为一个比较困难的问题。由于增加了分组字段,RR_Agg运算比R_Agg运算需要付出更长的执行时间。某些情况下,增加分组字段可能使远程数据库选择不同的物理执行计划,RR_Agg运算增加的执行时间不可忽视。如果查询结果并非热点数据,重用概率很小,就需要对推送运算符的代价和收益进行综合评估。论文提出了基于全局代价估计模型的贪婪式选择算法,在代价可接受的情况下,尽可能选择有较高收益的RR_Agg运算。(2)复合视图缓存机制复合视图缓存支持SPJA查询结果缓存。动态缓存表采用具有固定投影字段和分组字段表示缓存数据。多级缓存索引用于动态缓存表的快速定位。复合视图缓存为请求查询查找到动态缓存表以后,根据动态缓存表的内容,计算出提交给数据源获取剩余数据的剩余查询。剩余查询与请求查询包含相同类型的运算符,但选择过滤条件不同。剩余查询选择条件的通用计算方法是将请求查询选择条件与缓存查询选择条件合取否定式的合取结果转换为析取范式,然后再计算其中每一个合取表达式的结果。当查询选择条件包含谓词项数量大于1时,剩余查询选择条件通用计算方法时间复杂度和空间复杂度随着缓存查询合取式数量增长而成指数级增长。论文采用了基于逻辑规则的约简求补算法。在转换为析取范式之前,对缓存查询选择条件合取式进行约简,从而降低析取范式转换的时间,提高查询匹配性能。3.结论及未来待解决的问题论文提出了聚集查询推送、可重用聚集查询推送及复合视图机制三项新技术。基于TPC-H负载的测试表明,上述技术对提高分布式OLAP查询处理性能效果明显。与无缓存的选择查询推送测试相比,无缓存的聚集查询推送方法可以将查询处理平均时间缩短26%到54%;基于复合视图缓存的可重用聚集查询推送技术则将查询处理平均时间缩短达68%。与不支持部分匹配的典型动态缓存技术相比,缓存机制则可以比较明显地降低查询缺失元组数和查询处理的平均响应时间。本文后续研究的一个重要问题是如何选择包含聚集和多表连接的公共运算进行推送和重用。对于相似程度高的查询而言,重用聚集和多表连接的公共运算结果可能获得更好的性能提高。然而,需要更加完善的全局代价估计和计划选择方法来加以解决。4.实用价值或应用前景有效管理和分析规模巨大的商业数据,并从中找到有价值的决策支持信息是企业面临的重要问题。交互式访问的OLAP应用是支持大规模数据分析的一类重要应用。在分布式OLAP应用中,大部分查询都包含复杂的聚集和分组运算。聚集分组运算具有较高的计算代价,同时往往会产生远小于输入元组数量的运算结果。然而目前大多数查询处理方法对聚集函数运算的处理都延迟到全部连接处理完以后才进行。为了减少数据传输和分布式引擎负担,应尽可能将更多运算下推到远程数据库中执行。这种情况下,如何推送聚集运算、如何估计推送处理的代价、如何重用查询结果数据都是亟待解决的问题。本文提出的三项新技术可以比较有效的解决上述问题。本文的研究成果及后续研究在提高分布式OLAP查询处理性能上具有较高的实用价值。复合视图缓存作为一种扩展的语义缓存技术,在提高数据集成、数据仓库、互联网应用的查询处理性能方面也有比较广泛的应用前景。Abstract: Our study introduces a novel distributed query planrefinement phase in an enhanced architecture of distributed queryprocessing engine (DQPE). Query plan refinement generates potentiallyefficient distributed query plan by reusable aggregate query shipping(RAQS) approach. The approach improves response time at the cost ofpre-processing time. If the overheads could not be compensated byquery results reusage, RAQS is no more favorable. Therefore a globalcost estimation model is employed to get proper operators: RR\_Agg,R\_Agg, or R\_Scan.For the purpose of reusing results of queries with aggregate function in distributedquery processing, a multi-level hybrid view caching (HVC) scheme isintroduced. The scheme retains the advantages of partial match andaggregate query results caching. By our solution, evaluations withdistributed TPC-H queries show significant improvement on averageresponse time.