IM^2:一种改进的MIN/MAX窗口函数优化技术  

IM^2:Improved MIN/MAX window functions optimizer in relational database

作　　者：宋光旋 赵大鹏 王晓玲 SONG Guang-xuan;ZHAO Da-peng;WANG Xiao-ling(Shanghai Key Laboratory of Trustworthy Computing, School of Computer Science and Software Engineering, East China Normal University,Shanghai 200062, China)

机构地区：[1]华东师范大学,计算机科学与软件工程学院,上海市高可信计算重点实验室,上海200062

出　　处：《华东师范大学学报（自然科学版）》2018年第1期103-116,共14页Journal of East China Normal University(Natural Science)

基　　金：国家自然科学基金(61170085,61472141);上海市重点学科建设项目(B412);上海市可信物联网软件协同创新中心项目(ZF1213)

摘　　要：窗口函数作为一种分析型的OLAP函数加入SQL(Structured Query Language)标准已有十多年,而且随着分析型应用需求的增长窗口函数有着越来越广泛的应用前景.窗口函数的语法非常简单,却可以表达诸如rank、moving average、cumulative sum等复杂的查询.尽管目前主流的商业数据库几乎都支持窗口函数,但是现有的执行策略效率低下,不能满足大批量数据的处理需求.本文主要针对窗口函数中MIN和MAX聚集函数,提出了一种改进的IM^2优化策略,可以有效地提升窗口函数的执行效率.本文不仅从时空复杂性理论分析层面进行了证明,而且与已有算法进行了对比实验,证明了本文方法的高效性;另外在目前主流的开源数据库PostgreSQL中实现本文算法,与SQL Server对比有着显著的优化效果.Window functions,also known as analytic OLAP functions,is a part of the SQL standard,and has been extensively studied during the past decade.And the window function has more and more extensive application prospects with the growth of the demands the analytical applications.Despite its simple syntax,window functions can express many complex queries,such as ranking,moving average,cumulative sum and so on.Although almost all the current mainstream commercial database support window function,the existing implementation strategy is inefficient,and is not suitable for processing big data.In this paper,we propose the IM2algorithm,an improved algorithm for the MAX/MIN window functions,which effectively improves the efficiency.And we prove the effectiveness of the IM2algorithm the theoretical complexity analysis.Additionally,we implement the algorithm in PostgreSQL and conduct extensive experiments on real world data to demonstrate the efficiency of the IM2algorithm.

关 键 词：window函数 MIN/MAX 执行优化 POSTGRESQL 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]