IM<sup>2</sup>: Improved MIN/MAX window functions optimizer in relational database

SONG Guang-xuan; ZHAO Da-peng; WANG Xiao-ling

doi:10.3969/j.issn.1000-5641.2018.01.010

Issue 1

Jan. 2018

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2018 > (1): 103-116

SONG Guang-xuan, ZHAO Da-peng, WANG Xiao-ling. IM2: Improved MIN/MAX window functions optimizer in relational database[J]. Journal of East China Normal University (Natural Sciences), 2018, (1): 103-116. doi: 10.3969/j.issn.1000-5641.2018.01.010

Citation:

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 Sciences), 2018, (1): 103-116. doi: 10.3969/j.issn.1000-5641.2018.01.010

Citation:

PDF( 700 KB)

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

doi: 10.3969/j.issn.1000-5641.2018.01.010

Shanghai Key Laboratory of Trustworthy Computing, School of Computer Science and Software Engineering, East China Normal University, Shanghai 200062, China

Received Date: 2016-10-21
Publish Date: 2018-01-25

Abstract

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 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 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.
- window function,
- MIN/MAX,
- performance optimization,
- PostgreSQL

FullText(HTML)

References(19)

References

[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. doi: 10.14778/1687553
[2]	EISENBERG A, MELTON J. Formerly known as SQL3[J]. ACM SIGMOD Record, 1999, 28(12):131-138. https://www.researchgate.net/publication/246223263_formerly_known_as_SQL3
[3]	EISENBERG A, MELTON J, KULKARNI K, et al. SQL:2003 has been published[J]. ACM SIGMOD Record, 2004, 33(1):119-126. doi: 10.1145/974121
[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. doi: 10.1007/s00778-009-0171-0
[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. http://dl.acm.org/citation.cfm?id=1066193
[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. doi: 10.1145/1058150
[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. http://dl.acm.org/citation.cfm?id=2063793
[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. http://dl.acm.org/citation.cfm?id=1316720
[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 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.225.3771
[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. http://dl.acm.org/citation.cfm?id=673628
[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. doi: 10.14778/2350229
[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. http://www.sciencedirect.com/science/article/pii/B978012088469850084X
[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. doi: 10.1007/BFb0014183
[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. http://www.sciencedirect.com/science/article/pii/B9780127224428500781
[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. doi: 10.14778/2794367
[17]	WESLEY R, XU F. Incremental computation of common windowed holistic aggregates[J]. Proceedings of the VLDB Endowment, 2016, 9(12):1221-1232. doi: 10.14778/2994509
[18]	马建松, 王科强, 宋光旋, 等.面向MAX/MIN优化的SQL Window函数处理[J].计算机学报, 2016, 39(10):2149-2160. doi: 10.11897/SP.J.1016.2016.02149
[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. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=1410162