IM2: Improved MIN/MAX window functions optimizer in relational database
-
摘要: 窗口函数作为一种分析型的OLAP函数加入SQL（Structured Query Language）标准已有十多年，而且随着分析型应用需求的增长窗口函数有着越来越广泛的应用前景.窗口函数的语法非常简单，却可以表达诸如rank、moving average、cumulative sum等复杂的查询.尽管目前主流的商业数据库几乎都支持窗口函数，但是现有的执行策略效率低下，不能满足大批量数据的处理需求.本文主要针对窗口函数中MIN和MAX聚集函数，提出了一种改进的IM2优化策略，可以有效地提升窗口函数的执行效率.本文不仅从时空复杂性理论分析层面进行了证明，而且与已有算法进行了对比实验，证明了本文方法的高效性；另外在目前主流的开源数据库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 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 IM2 algorithm, an improved algorithm for the MAX/MIN window functions, which effectively improves the efficiency. And we prove the effectiveness of the IM2 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 IM2 algorithm.-
Key words:
- window function /
- MIN/MAX /
- performance optimization /
- PostgreSQL
-
图 2 边框定义为ROWS BETWEENT 10 PRECEDING AND 10 FOLLOWING时MIN/MAX函数的执行过程
Fig. 2 Execution process of MIN/MAX with ROWS BETWEENT 10 PRECEDING AND 10 FOLLOWING
图 6 不同 $k$ 值下SQL-1执行时间(170 MB)
Fig. 6 Execution time of SQL-1 with different $k$ (170 MB)
图 7 不同 $k$ 值下SQL-1执行时间(1.7 GB)
Fig. 7 Execution time of SQL-1 with different $k$ (1.7 GB)
图 8 不同 $k$ 值下SQL-2执行时间(170 MB)
Fig. 8 Execution time of SQL-2 with different $k$ (170 MB)
图 9 不同 $k$ 值下SQL-2执行时间(1.7 GB)
Fig. 9 Execution time of SQL-2 with different $k$ (1.7 GB)
表 1
算法1 PostgreSQL MIN/MAX执行算法 输入:经过重排序的表 $T'$
输出:每个元组所对应的MAX/MIN函数值1. FOR表 $T'$ 中的每一个分区 $P$ DO
2. FOR分区 $P$ 中的每一个窗口
3. 初始化 $W_i\cdot h$ 、 $W_i\cdot t$ 、 $W_i\cdot V$ ;
4. IF $W_i\cdot h==W_{i-1}\cdot h$ THEN
5. $W_i\cdot V\leftarrow W_{i-1}\cdot V;$
6. FOR each row in ( $W_{i-1}{\cdot} t$ , $W_i\cdot t$ ] DO
7. $W_i\cdot V\leftarrow $ transfunc ( $W_i\cdot V, R_m$ );
8. ELSE
9. FOR each row in [ $W_i\cdot h, W_i\cdot t$ ] DO
10. $W_i\cdot V\leftarrow $ transfunc ( $W_i\cdot V, R_m$ );
11. RETURN $W_i\cdot V$ ;
下载: 导出CSV
表
算法2 IM $^{2}$ MAX函数优化算法 输入: PARTITION和ORDER之后的表 $T$
输出:每个元组所对应的MAX/MIN函数值1. FOR $T$ 中的每一个分区 $P$ DO
2. 初始化SW结构;
3. FOR分区 $P$ 中的每一个窗口 $W_i$ DO
4. 初始化 $W_i\cdot h$ 、 $W_i\cdot t$ 、 $W_i\cdot V$ ;
5. IF $W_i\cdot h==W_{i-1}\cdot h$ THEN
6. $W_i\cdot V\leftarrow W_{i-1}\cdot V$ ;
7. FOR rows in ( $W_{i-1}\cdot t, W_i\cdot t$ ) DO
8. $W_i\cdot V\leftarrow$ transfunc ( $W_i\cdot V, R_m$ )
9. IF $W_i\cdot V>{\rm SW}\cdot {\rm value} [{\rm cur}{\rm P}]$ THEN
10. resetSW $({\rm SW}, \; r_m, \; W_i\cdot V)$ ;
11. ELSE
12. updateSW( ${\rm SW}, R_m$ );
13. SW.TAIL $\leftarrow W_i\cdot t$ ;
14. ELSE IF $W_i\cdot h\leq {\rm SW}\cdot {\rm HEAD}\lceil {\rm curP} \rceil$ THEN
15. $W_i\cdot V\leftarrow {\rm SW.value}[{\rm curP}]$ ;
16. FOR rows in ( ${\rm SW}.{\rm TAIL}, W_i\cdot t$ )DO
17. $W_i\cdot V\leftarrow$ transfunc( $W_i\cdot V$ , $R_m$ );
18. IF $W_i\cdot V>{\rm SW}.{\rm value}[{\rm cur P}]$ THEN
19. resetSW( ${\rm SW}, \; r_m, \;W_i\cdot V$ )
20. ELSE
21. updateSW( ${\rm SW}, R_m$ );
22. SW.TAIL $\leftarrow W_{i}, t$
23. ELSE IF $W_k\cdot h\leq {\rm SW}.{\rm HEAD}\lceil {\rm curP}+{\rm actN}-1 \rceil$
24. THEN
25. SW.curPOS $\leftarrow {\rm findpos} ({\rm SW}, \;W_i\cdot h);$
26. $W_i\cdot V\leftarrow {\rm SW}.{\rm value}\lceil {\rm curP}\rceil$
27. FOR rows in ( ${\rm SW}.{\rm TAIL}, \;W_i\cdot t$ )DO
28. $W_i\cdot V\leftarrow$ transfunc( $W_i\cdot V, \; R_m$ );
29. IF $W_i\cdot V>{\rm SW.value}\lceil {\rm curP} \rceil$ THEN
30. resetSW $({\rm SW}, \;r_m, \;W_i\cdot V)$
31. ELSE
32. updateSW( ${\rm SW}, \;R_m$ );
33. SW.TAIL $\leftarrow W_i\cdot t$
34. ELSE
35. FOR each row in [ $W_i\cdot s, \;W_i\cdot e$ ]DO
36. $W_i\cdot V\leftarrow $ transfunc( $W_i\cdot V, \;R_m$ );
37. IF $W_i\cdot TV>{\rm SW.value}\lceil {\rm curP} \rceil$ THEN
38. resetSW $({\rm SW}, \;r_m, \;W_i\cdot V)$
39. ELSE
40. updateSW( ${\rm SW}, \;R_m$ );
41. SW.TAIL $\leftarrow W_i\cdot t$
42. RETURN $W_i\cdot TV$ ;
下载: 导出CSV
-
[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 -
点击查看大图
图(10) / 表(2)
计量
- 文章访问数: 184
- HTML全文浏览量: 46
- PDF下载量: 379
- 被引次数: 0