TY - GEN
T1 - WeTune
T2 - 2022 ACM SIGMOD International Conference on the Management of Data, SIGMOD 2022
AU - Wang, Zhaoguo
AU - Zhou, Zhou
AU - Yang, Yicun
AU - Ding, Haoran
AU - Hu, Gansen
AU - Ding, Ding
AU - Tang, Chuzhe
AU - Chen, Haibo
AU - Li, Jinyang
N1 - Funding Information:
We thank all anonymous reviewers for their constructive feedback and suggestions. This work is supported in part by National Natural Science Foundation of China (No. 62132014, 61902242, 62172272), the HighTech Support Program from Shanghai Committee of Science and Technology (No. 20ZR1428100). Ding Ding is supported by a DeepMind fellowship. Zhaoguo Wang ([email protected]) is the corresponding author.
Publisher Copyright:
© 2022 ACM.
PY - 2022/6/10
Y1 - 2022/6/10
N2 - Query rewriting transforms a relational database query into an equivalent but more efficient one, which is crucial for the performance of database-backed applications. Such rewriting relies on pre-specified rewrite rules. In existing systems, these rewrite rules are discovered through manual insights and accumulate slowly over the years. In this paper, we present WeTune, a rule generator that automatically discovers new rewrite rules. Inspired by compiler superoptimization, WeTune enumerates all valid logical query plans up to a certain size and tries to discover equivalent plans that could potentially lead to more efficient rewrites. The core challenge is to determine which set of conditions (aka constraints) allows one to prove the equivalence between a pair of query plans. We address this challenge by enumerating combinations of "interesting"constraints that relate tables and their attributes between each pair of queries. We also propose a new SMT-based verifier to verify the equivalence of a query pair under different enumerated constraints. To evaluate the usefulness of rewrite rules discovered by WeTune, we apply them on the SQL queries collected from the 20 most popular open-source web applications on GitHub. WeTune successfully optimizes 247 queries that existing databases cannot optimize, resulting in substantial performance improvements.
AB - Query rewriting transforms a relational database query into an equivalent but more efficient one, which is crucial for the performance of database-backed applications. Such rewriting relies on pre-specified rewrite rules. In existing systems, these rewrite rules are discovered through manual insights and accumulate slowly over the years. In this paper, we present WeTune, a rule generator that automatically discovers new rewrite rules. Inspired by compiler superoptimization, WeTune enumerates all valid logical query plans up to a certain size and tries to discover equivalent plans that could potentially lead to more efficient rewrites. The core challenge is to determine which set of conditions (aka constraints) allows one to prove the equivalence between a pair of query plans. We address this challenge by enumerating combinations of "interesting"constraints that relate tables and their attributes between each pair of queries. We also propose a new SMT-based verifier to verify the equivalence of a query pair under different enumerated constraints. To evaluate the usefulness of rewrite rules discovered by WeTune, we apply them on the SQL queries collected from the 20 most popular open-source web applications on GitHub. WeTune successfully optimizes 247 queries that existing databases cannot optimize, resulting in substantial performance improvements.
KW - SQL solver
KW - query rewriting
KW - rewrite rule discovery
UR - http://www.scopus.com/inward/record.url?scp=85132741472&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85132741472&partnerID=8YFLogxK
U2 - 10.1145/3514221.3526125
DO - 10.1145/3514221.3526125
M3 - Conference contribution
AN - SCOPUS:85132741472
T3 - Proceedings of the ACM SIGMOD International Conference on Management of Data
SP - 94
EP - 107
BT - SIGMOD 2022 - Proceedings of the 2022 International Conference on Management of Data
PB - Association for Computing Machinery
Y2 - 12 June 2022 through 17 June 2022
ER -