Journal of East China Normal University(Natural Sc ›› 2018, Vol. 2018 ›› Issue (1): 103-116.doi: 10.3969/j.issn.1000-5641.2018.01.010

Previous Articles     Next Articles

IM2: Improved MIN/MAX window functions optimizer in relational database

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

  1. 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: 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 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

CLC Number: