Window Function Expression: Let the Self-Join Enter
Author:
Open Access
- 1 May 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 17 (9) , 2162-2174
Abstract
Window function expressions (WFEs) became part of the SQL:2003 standard, and since then, they have often been implemented in database systems (DBS). They are especially essential to OLAP DBSs, and people use them daily. Even though WFEs are a heavily used part of the SQL language, the amount of research done on their optimization in the last two decades is not significant. WFE does not extend the expressive power of the SQL language, but it makes writing SQL queries easier and more transparent. DBSs always compile SQL queries with WFE using a sequence of partition-sort-compute operators, which we call a linear strategy. Plans resulting from the linear strategy are robust and, in many cases, efficient. This article introduces an alternative strategy using a self-join, which is not considered in the current DBSs. We call it the self-join strategy, and it is based on an SQL query transformation where the result query uses a self-join query plan to compute WFE. One output of this work is a tool that can automatically perform such SQL query transformations. We created a microbenchmark showing that the self-join strategy is more effective than the linear strategy in many cases. We also performed a cost-based experiment to evaluate the query optimizers' ability to select an appropriate strategy. The article's main aim is to show that usage of the self-join strategy for queries with WFE is beneficial if selected in a cost-based manner.Keywords
This publication has 17 references indexed in Scilit:
- T-Rex: Optimizing Pattern Search on Time SeriesProceedings of the ACM on Management of Data, 2023
- Data dependencies for query optimization: a surveyThe VLDB Journal, 2021
- Quantifying TPC-H choke points and their optimizationsProceedings of the VLDB Endowment, 2020
- How to Architect a Query Compiler, Revisited2018
- Incremental computation of common windowed holistic aggregatesProceedings of the VLDB Endowment, 2016
- Efficient processing of window functions in analytical SQL queriesProceedings of the VLDB Endowment, 2015
- Accelerating queries with group-by and join by groupjoinProceedings of the VLDB Endowment, 2011
- Towards optimal range mediansTheoretical Computer Science, 2011
- Enhanced subquery optimizations in OracleProceedings of the VLDB Endowment, 2009
- Query optimizationACM Computing Surveys, 1996