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

doi:10.3969/j.issn.1000-5641.2018.01.010

华东师范大学学报(自然科学版) ›› 2018, Vol. 2018 ›› Issue (1): 103-116.doi: 10.3969/j.issn.1000-5641.2018.01.010

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

宋光旋, 赵大鹏, 王晓玲

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

收稿日期:2016-10-21 出版日期:2018-01-25 发布日期:2018-01-11
作者简介:宋光旋,男,硕士研究生,研究方向为数据库.E-mail:guangxuan_song@163.com.
基金资助:
国家自然科学基金（61170085，61472141）；上海市重点学科建设项目（B412）；上海市可信物联网软件协同创新中心项目（ZF1213）

IM²: 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

Received:2016-10-21 Online:2018-01-25 Published:2018-01-11

摘要/Abstract

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

关键词: window函数, MIN/MAX, 执行优化, PostgreSQL

Abstract: 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 withthegrowthofthedemandstheanalyticalapplications. 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 IM² algorithm, an improved algorithm for the MAX/MIN window functions, which effectively improves the efficiency. And we prove the effectiveness of the IM² algorithm 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 IM² algorithm.

Key words: window function, MIN/MAX, performance optimization, PostgreSQL

中图分类号:

TP311

宋光旋, 赵大鹏, 王晓玲. IM²:一种改进的MIN/MAX窗口函数优化技术[J]. 华东师范大学学报(自然科学版), 2018, 2018(1): 103-116.

SONG Guang-xuan, ZHAO Da-peng, WANG Xiao-ling. IM²: Improved MIN/MAX window functions optimizer in relational database[J]. Journal of East China Normal University(Natural Sc, 2018, 2018(1): 103-116.

参考文献

[1] BELLAMKONDA S, AHMED R, WITKOWSKI A, et al. Enhanced subquery optimizations in oracle[J]. Proceedings of the VLDB Endowment, 2009, 2(2):1366-1377.
[2] EISENBERG A, MELTON J. Formerly known as SQL3[J]. ACM SIGMOD Record, 1999, 28(12):131-138.
[3] EISENBERG A, MELTON J, KULKARNI K, et al. SQL:2003 has been published[J]. ACM SIGMOD Record, 2004, 33(1):119-126.
[4] JIN C Q, YI K, CHEN L, et al. Sliding-window top-k, queries on uncertain streams[J]. The VLDB Journal, 2010, 19(3):411-435.
[5] LI J, MAIER D, TUFTE K, et al. Semantics and evaluation techniques for window aggregates in data streams[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, 2005:311-322.
[6] LI J, MAIER D, TUFTE K, et al. No pane, no gain:Efficient evaluation of sliding-window aggregates over data streams[J]. ACM SIGMOD Record, 2005, 34(1):39-44.
[7] GUIRGUIS S, SHARAF M A, CHRYSANTHIS P K, et al. Optimized processing of multiple aggregate continuous queries[C]//Proceedings of the 20th ACM international conference on Information and Knowledge Management. ACM, 2012:1515-1524.
[8] ARASU A, WIDOM J. Resource sharing in continuous sliding-window aggregates[C]//Proceedings of the 30th International Conference on Very Large Data Bases. VLDB Endowment, 2004:336-347.
[9] LAW Y N, WANG H X, ZANIOLO C. Relational languages and data models for continuous queries on sequences and data streams[J]. ACM Transactions on Database Systems, 2011, 36(2):8:1-8:32
[10] CHATZIANTONIOU D, ROSS K A. Querying multiple features of groups in relational databases[C]//Proceedings of the 22nd International Conference on Very Large Data Bases. 1997:295-306.
[11] BELLAMKONDA S, BORZKAYA T, GHOSH B, et al. Analytic functions in oracle 8i[R/OL].[2016-09-01]. http://www-db.stanford.edu/dbseminar/Archive/SpringY2000/speakers/agupta/paper.pdf.
[12] CAO Y, CHAN C Y, LI J, et al. Optimization of analytic window functions[J]. Proceedings of the VLDB Endowment, 2012, 5(11):1244-1255.
[13] NEUMANN T, MOERKOTTE G. A combined framework for grouping and order optimization[C]//Proceedings of the 30th International Conference on Very Large Data Bases. VLDB Endowment, 2004:960-971.
[14] SIMMEN D, SHEKITA E, MALKEMUS T. Fundamental techniques for order optimization[C]//Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. ACM, 1996:57-67.
[15] WANG X Y, CHERNIACK M. Avoiding sorting and grouping in processing queries[C]//Proceedings of the International Conference on Very Large Data Bases. VLDB Endowment, 2003:826-837.
[16] LEIS V, KUNDHIKANJANA K, KEMPER A, et al. Efficient processing of window functions in analytical SQL queries[J]. Proceedings of the VLDB Endowment, 2015, 8(10):1058-1069.
[17] WESLEY R, XU F. Incremental computation of common windowed holistic aggregates[J]. Proceedings of the VLDB Endowment, 2016, 9(12):1221-1232.
[18] 马建松, 王科强, 宋光旋,等. 面向MAX/MIN优化的SQL Window函数处理[J]. 计算机学报, 2016, 39(10):2149-2160.
[19] LIN X, YUAN Y, WANG W, et al. Stabbing the sky:Efficient skyline computation over sliding windows[C]//Proceedings of the 21st International Conference on Data Engineering. IEEE, 2005:502-513.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	于萍, 胡卉芪, 钱卫宁. 基于遗传算法的多目标货物配载研究[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 185-198.
[2]	马晓琴, 郭小鹤, 薛峪峰, 杨琳, 陈远哲. 针对命名实体识别的数据增强技术[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 14-23.
[3]	纪宇, 何一璇, 吴国群, 吴敏. 基于Prony-like方法的第一类贝塞尔函数逼近[J]. 华东师范大学学报(自然科学版), 2019, 2019(6): 42-60.
[4]	谢青成, 毛嘉莉, 刘婷. 城市共享单车的动态调度策略[J]. 华东师范大学学报(自然科学版), 2019, 2019(6): 88-102.
[5]	申航杰, 琚生根, 孙界平. 基于模糊聚类和支持向量回归的成绩预测[J]. 华东师范大学学报(自然科学版), 2019, 2019(5): 66-73,84.
[6]	江群, 戴戈南, 张森, 葛又铭, 刘玉葆. 基于用户偏好的最优路径搜索[J]. 华东师范大学学报(自然科学版), 2019, 2019(5): 100-112.
[7]	刘子豪, 胡卉芪, 徐瑞, 周烜. 基于LevelDB的二维数据二级索引实现[J]. 华东师范大学学报(自然科学版), 2019, 2019(5): 159-167.
[8]	张涛, 张小磊, 李宇明, 张春熙, 张蓉. Woodpecker+:基于数据特征的自定义负载性能评测[J]. 华东师范大学学报(自然科学版), 2019, 2019(5): 190-202.
[9]	高志强, 袁敏, 张杰. 面向用户需求的云桌面推荐方法研究[J]. 华东师范大学学报(自然科学版), 2019, 2019(4): 97-110.
[10]	黄平, 杜德慧. 一种基于SysML/MARTE/pCCSL的信息物理融合系统协同建模方法[J]. 华东师范大学学报(自然科学版), 2019, 2019(1): 48-57.
[11]	徐阳, 王志杰, 钱诗友. 基于分布式平台Spark的空间文本查询分析[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 120-134,153.
[12]	张衡, 陈良育. Levenshtein算法优化及在题库判重中的应用[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 154-163.
[13]	麻友, 岳昆, 张子辰, 王笑一, 郭建斌. 基于知识图谱和LDA模型的社会媒体数据抽取[J]. 华东师范大学学报(自然科学版), 2018, 2018(5): 183-194.
[14]	王彦朝, 胡卉芪, 张召, 刘小兵, 段惠超. 数据存储与处理分离架构下的子链接消除及优化[J]. 华东师范大学学报(自然科学版), 2018, 2018(4): 90-98.
[15]	李捷荧, 李宇明, 张小磊, 张蓉. Woodpecker:支持细粒度冲突模拟的数据库测试框架[J]. 华东师范大学学报(自然科学版), 2018, 2018(2): 77-88.