Abstract
Analytic functions represent the state-of-the-art way of performing complex data analysis within a single SQL statement. In particular, an important class of analytic functions that has been frequently used in commercial systems to support OLAP and decision support applications is the class of window functions. A window function returns for each input tuple a value derived from applying a function over a window of neighboring tuples. However, existing window function evaluation approaches are based on a naive sorting scheme. In this paper, we study the problem of optimizing the evaluation of window functions. We propose several efficient techniques, and identify optimization opportunities that allow us to optimize the evaluation of a set of window functions. We have integrated our scheme into PostgreSQL. Our comprehensive experimental study on the TPC-DS datasets as well as synthetic datasets and queries demonstrate significant speedup over existing approaches.
Introduction
Analytic window functions, such as RANK(), AVG(), and SUM() combined with an OVER clause, are indispensable tools in modern SQL for performing complex calculations across sets of rows related to the current row. Unlike traditional aggregate functions, window functions do not collapse rows into a single output; instead, they append the result to each individual row.
As shown in the table above, a single query can compute multiple rankings (e.g., RANK_IN_DEPT and GLOBALRANK) based on different partitioning and ordering criteria. While powerful, the computational cost of these operations is high, primarily due to the data reordering required for each function.
The Performance Bottleneck: Full Sort
The traditional method for evaluating window functions is the "Full Sort" (FS) approach. For every window function in a query, the database engine typically performs a complete sort of the entire dataset to satisfy the specific PARTITION BY and ORDER BY requirements of that function.
When a query involves multiple window functions with different requirements, the system executes a chain of these expensive sorts. This "naive" approach becomes a significant bottleneck as data volumes grow, leading to redundant work and excessive memory usage.
Proposed Optimization Techniques
To address these inefficiencies, this research introduces three core optimizations:
1. Hashed Sort (HS)
Standard sorting orders the entire dataset. However, window functions only require that rows belonging to the same partition are grouped together; the relative order of the partitions themselves is irrelevant. Hashed Sort exploits this by hashing rows into buckets based on partition keys and sorting each bucket independently. This method is significantly more memory-resilient than global sorting.
2. Segmented Sort (SS)
Segmented Sort is designed to leverage "interesting orders" left behind by previous operations. If the data is already partially sorted (e.g., by a previous window function), SS identifies "segments" that share a common prefix and only sorts the remaining attributes within those segments. This avoids the overhead of a complete re-sort and drastically reduces tuple comparisons.
3. Cover Set-based Optimization (CSO)
Determining the most efficient sequence to evaluate multiple window functions is an NP-hard problem. The authors propose a heuristic framework called Cover Set-based Optimization. CSO groups window functions into "cover sets" that can share a single reordering operation and prioritizes the use of Segmented Sort over more expensive alternatives.
Experimental Results
The proposed techniques were integrated into PostgreSQL and tested against industry-standard TPC-DS benchmarks (14.3GB, 72 million tuples) and synthetic datasets.
- Efficiency: Segmented Sort consistently outperformed both Full Sort and Hashed Sort by avoiding redundant partitioning work.
- Robustness: Hashed Sort maintained stable performance even under tight memory constraints, avoiding the performance degradation seen when Full Sort spills to disk.
- Global Gains: In complex queries with many window functions, the CSO-optimized execution plans were significantly faster than standard PostgreSQL and commercial "Ordering Group" approaches. Optimization overhead remained negligible (under 15ms).
Conclusion
By moving beyond the naive Full Sort paradigm, this work demonstrates that window function evaluation can be made significantly more efficient. The combination of Hashed Sort, Segmented Sort, and a heuristic optimization framework provides a robust solution for modern OLAP workloads. Future work includes refining cost models to account for increasing row widths and exploring graph-based parallel evaluation models.
Summary updated