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