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

摘要：

窗口函数作为一种分析型的OLAP函数加入SQL(Structured Query Language)标准已有十多年,而且随着分析型应用需求的增长窗口函数有着越来越广泛的应用前景.窗口函数的语法非常简单,却可以表达诸如rank、moving average、cumulative sum等复杂的查询.尽管目前主流的商业数据库几乎都支持窗口函数,但是现有的执行策略效率低下,不能满足大批量数据的处理需求.本文主要针对窗口函数中MIN和MAX聚集函数,提出了一种改进的IM2优化策略,可以有效地提升窗口函数的执行效率.本文不仅从时空复杂性理论分析层面进行了证明,而且与已有算法进行了对比实验,证明了本文方法的高效性;另外在目前主流的开源数据库PostgreSQL中实现本文算法,与SQL Server对比有着显著的优化效果.

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

分类号：TP311(计算技术、计算机技术)

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

在线出版日期：2018-05-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：103-116