Traditional query optimizers are designed to be fast and stateless: each query is quickly optimized using approximate statistics, sent of to the execution engine, and promptly forgotten. Recent work on learned query optimization have shown that it is possible for a query optimizer to “learn from its mistakes,” correcting erroneous query plans the next time a plan is produced. But what if query optimizers could avoid mistakes entirely? This paper presents the idea of learned query superoptimization. A new generation of query superoptimizers could autonomously experiment to discover optimal plans using exploration-driven algorithms, iterative Bayesian optimization, and program synthesis. While such superoptimizers will take significantly longer to optimize a given query, superoptimizers have the potential to massively accelerate a large number of important repetitive queries being executed on data systems today.
highly repetitive. The same query template – and often the exact same query – might be executed many times.
Traditional cost-based query optimizers [1] are designed In fact, for many analytic dashboarding systems, the to be fast. When a new query arrives, the optimizer majority of cluster resources might go to executing a set of performs some computations using statistical cardinal- highly-repetitive queries (e.g., the hourly sales dashboard ity estimates, and produces a query plan. In this sense, executes nearly-identical queries every hour). traditional query optimizers can be viewed as cheap (com- Given the shape of these analytics workloads, does it pared to query execution) stateless functions. Each new make sense to view each query optimization as a cheap query is a blank slate, representing a “fire and forget” stateless function that only relies on optimizer statissystem. tics? This issue has been partially addressed by past
Past work on learned query optimization [2, 3, 4, 5, 6] work on parameterized or parametric query optimizahave addressed the “forget” component of “fire and forget” tion (PQO) [9, 10, 11] and query plan caching [12, 13], optimizers. Since every optimizer processes queries with which has mostly focused on further reducing optimizasimilar qualities (all querying the same database), one can tion times (as opposed to query latency) by avoiding say there is cross entropy (shared information) between repetitive work, although there are some exceptions [14]. each query. By learning a model of query performance Here, I propose learned query superoptimization. that takes advantage of this cross entropy, learned query Following the “anytime” model proposed in [15], this optimizers “learn from their mistakes.” Since learned paper considers: what if instead of bounding the query query optimizers are starting to see early commercial optimizer to a few hundred milliseconds, we instead used adoption [7, 8], we can conclude that the database com- hours or even days of computation to optimize a query? munity has made some progress on the “forget” element For queries that execute thousands or even millions of of traditional optimizers. times a year (as may be the case in large dashboard appli
But what about the “fire” element? Query optimizers cations), the additional optimization time could possibly are built so that optimization time is low compared to “pay for itself.” query execution time, so the cost of query optimization The thought of using significant resources on query can be seen as amortized over the query’s execution. The optimization may be viscerally unappealing to many in simplifying assumption at work here is that since each the database community. To assuage these feelings, note incoming query could be unlike anything seen before, that “superoptimization” is a common concept in prothe time spent optimizing any specific query might not gram compilation: since some programs are executed so be useful for optimizing other queries. When we view often, spending a significant amount of time optimizing a each query as arbitrary, this assumption seems valid. program may be worthwhile even if the program’s execu
But in many real applications, query workloads are tion time only improves marginally. If we are willing to Joint Workshops at 49th International Conference on Very Large Data spend extra time compiling our DBMSes to eke-out every Bases (VLDBW’23) — Workshop on Applied AI for Database Systems last drop of performance, why not give DBMS users the and Applications (AIDB’23), August 28 - September 1, 2023, Vancouver, same option for their queries? Canada This paper presents two orthogonal directions for fu$ rcmarcus@seas.upenn.edu (R. Marcus) ture research on learned query superoptimization.
0000-0002-1279-1124 (R. Marcus) © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 Exhaustive plan search (Section 3) It is well known ICntEernUatRionWal(CoCrBkYs4h.0o).p Proceedings (CEUR-WS.org) that cardinality estimates are often poor, and often the median query template that lived for six months to one year was executed over a 100, 000 times. With such a large percentage of cluster resources going to executing these repetitive queries, it seems reasonable to try and optimize repetitive queries specifically.
3. Exhaustive plan search Program synthesis (Section 4) While DBMSes seek to provide a fast implementation of the relational model to users, the abstractions of the relational model often seep into DBMS design. Bespoke systems (e.g., Millwheel [17], Bigtable [18]) fully discard the generality of the relational model, which allows them to use custom implementations that often outperform anything a general DBMS could ofer. Expanding on [ 19], what if program synthesis techniques we could automatically generate a bespoke data system for a user?
To begin, Section 2 will show summary statistics from a large, highly-repetitive workload that motivates the idea of query superoptimization. Then, Section 3 and 4 will discuss future directions for learned query superoptimization work.
Of course, modern analytics systems also get a good number of ad-hoc queries. While collaborating with a large corporation, I analyzed a year of query logs from an on-premise data warehouse to determine how often parameterized queries were executed. The results are summarized in Table 1.
There were nearly 11, 000 query templates that appeared in the logs for six months to a full year, and execution of those templates occupied 31% of the cluster’s resources throughout the 12-month period. It is worth noting that these queries are executed quite often: the A narrow search space Traditional optimizers must use heuristics to exclude parts of the exponentially-large search space. Unfortunately, these heuristics can exclude the optimal plan. For example, the PostgreSQL optimizer excludes any plan containing cross joins from consideration, but if two dimension tables are suficiently small, a cross join could be optimal. The reason traditional optimizers exclude cross joins is because plans with cross joins are almost always suboptimal, and even when a cross join is optimal, there is normally a near-optimal plan without a cross join. Nevertheless, while unusual, such heuristics can exclude optimal query plans without ifnding a near-optimal one [2].
the mercy of their cost models and cardinality estimators.
While cardinality estimators achieve reasonably good accuracy for table scans, estimator errors often reach catastrophic levels after only a few joins [16]. Thus, the optimizer must plan the final joins of a query plan (which are often the most significant) with virtually no statistics.
Even learned query optimization [4, 2, 3, 5] follow this paradigm: learned query optimizers still use heuristics to prune the plan space (e.g., the anytime search in [2]), and still only operate with pre-computed statistics: the only diference is that the pruning heuristic and statistics are learned.
What if we built a query superoptimizer that ignored both of these fundamental design principles? The simplest possible superoptimizer escaping this paradigm might “wrap” a traditional optimizer: execute the top queries produced by the traditional optimizer and pick the best one, budgeting for the highest possible. Such an optimizer would verify the quality of query plans on actual data, albeit in a crude fashion. Another possibility is using an evolutionary algorithm to search for better best of my knowledge, yet unstudied by the database or plans, as in [14], to use on-the-fly data sampling for join reinforcement learning community. planning as in [21], or to use various forms of cardinality injection [15]. 3.2. Design 2: latent space optimization
But we can do much better: it may be possible to build query superoptimizers that interleave machine learning A second possibility is inspired by recent work [26] applyand query execution. Next, I propose two possible sys- ing Bayesian techniques to molecular optimization, the tems using this paradigm. task of searching for molecules with particular properties. Translating from finding molecules to finding query 3.1. Design 1: repeated reinforcement plans, the fundamental idea is to encode query plans into a latent space, use Bayesian optimization techniques to learning optimize the plan within the latent space, and then deReinforcement learning powered optimizers like Neo [2], code the point in the latent space back into a query plan. Balsa [3], and Lero [5] work in episodes. Each episode Figure 1 shows an illustration of this process. corresponds to building a complete execution plan for a The motivation behind this idea is to translate the given query. Each episode also ends with a reward, the problem of query optimization from a “structural optisignal that the learned optimizer uses to adjust future mization” problem (i.e., a problem where the output must actions. have a particular structure, like a query plan) into a “con
Reinforcement learning algorithms must navigate the tinuous optimization” problem (i.e., a problem in which exploration-exploitation tradeof . In short, a learning agent the output is continuous). Once we have a continuous must choose to either (1) explore, trying something new problem, a large number of well-studied continuous opand potentially gaining valuable information, or (2) ex- timization algorithms can be applied (e.g., [27]). ploit, try something that is known to work already and Encoder & latent space The encoder’s : → R reap a reward. Existing learned query optimizers seek to goal is to map a query plan ∈ into a -dimensional perfectly balance exploration and exploitation, maximiz- latent space R using a neural network. We want poing long term rewards [22]. sitions in the latent space to be semantically relevant,
A learned query superoptimizer could tilt the scale meaning that we want similar points in the latent space significantly towards exploration. Doing so would cause to represent similar query plans and have similar perforthe underlying reinforcement learning algorithm to pro- mance properties (i.e., latency, IOs). One way to do this duce more diverse and risky plans. The superoptimizer is with an information bottleneck [28]: we train a model could then execute each plan, possibly on a sample of to predict the performance properties of a query, but we the database, and return the plan that works the best. make one of the last layers (possibly the second or third This procedure not only produces a higher quality plan, from the end) intentionally small. This forces the model but this procedure also gathers experience faster, allow- to learn a compact representation of the query plans in ing the underling reinforcement learning agent to learn the intentionally small layer, but also requires that the faster. intentionally small layer is organized in such a way that
An additional benefit to a reinforcement-learning pow- allows for predicting the performance properties of the ered superoptimizer is that many of the features and query. Such a model will not achieve high accuracy comsafety mechanisms built into current learned systems pared to models without an information bottleneck, but could be removed. For example, Bao [23] provides a num- accuracy is not our goal. We can now chop of the layers ber of tools, each using significant resources, to ensure after the information bottleneck, and use the resulting regressions do not occur. With a superoptimizer, no such network as an encoder: the information bottleneck layer advanced regression-avoiding tooling is needed, since serves as our latent space. the empirical quality of the query plan can be observed Decoder The decoder’s : R → job is to take a before optimization finishes. point in the latent space created by the encoder and trans
Tipping the balance towards exploration is far from an form the point back into a query plan. The decoder can be optimal solution. Since even a superoptimizer must oper- trained by diferentiating through the encoder, freezing ate in a limited time budget, choosing exactly which plans the weights of the encoder during the process. Archito test is an optimization problem on its own. Simply tecturally, the decoder can be anything that produces a selecting the first exploratory plans might be far from sequence, but a reasonable choice may be a transformer ideal, since all plans might explore the same part of the model [29] or an LSTM [30]. search space. Active learning techniques, like those used in Datafarm [24], might be applicable here. This particu- Bayesian optimization The core of a latent space query lar problem — choosing the ideal explorations before superoptimizer is Bayesian optimization. The query optisettling on a final, reward-granting decision — is, to the mization problem can be cast as a black-box optimization ⋈
C ⋈ A
B similar queries
C ⋈ A ⋈
B Encoder
Latent space
Decoder problem. Let the query plan 1 be the plan generated by a traditional query optimizer, which will be the initial condition for our optimization. Further, let () be the latency of , determined by executing the plan. The Bayesian optimization algorithm then searches for a vector ˆ such that: argmin (((1) + ˆ)) ^
Actor
stars Company produces
Movie
plan using the decoder . underlying optimizer will join the five relations together,
Bayesian optimization of expensive functions with con- possibly even changing the join order based on and tinuous inputs is a well-studied problem, with many algo- . Note that, because both stars and produces are rithms available [31]. Reinforcement learning powered many-to-many, using fewer than 5 relations would vioquery optimizers had to invent customized algorithms late second normal form. to deal with the specific challenges of query optimiza- Do we think this implementation is optimal? Of course tion. By tapping into a preexisting field like Bayesian not. Sure, using a relational database has great engineeroptimization (which have already had proven success in ing benefits, such as (1) the reuse of existing components, drug discovery [27], hardware design [32], and even ur- (2) the ability to extend the system to other queries, and ban planning [33]), a learned query superoptimizer may (3) most organizations already know how to maintain a be in reach in the near future. DBMS. But, if our data system’s job is to answer 1 as fast as possible, then we know that the algorithm executed by the relational database will not be optimal. 4. Program synthesis Instead of four joins, imagine we store two hashmaps: The previous proposals for query superoptimizers have one mapping each actor to a bitmap, where that bitmap all assumed that the final output of a query optimizer stores a 1 if the actor appears in that movie, and a second should be an executable query plan. In this section, we mapping each company to a bitmap, where that bitmap propose a “rethinking of the query optimization con- stores a 1 if the company produces that movie. Now, tract” [15] – specifically, we propose a query optimizer answering 1 is as simple as two hashmap lookups and that simultaneously optimizes query execution plans and a bitmap count-intersect. With a cuckoo hashmap and the underlying physical layout of the data. To illustrate smart prefetching, this could be implemented with only this potential, imagine writing a program that answers 6 cache misses. queries about the relationships between actors, movies, Figure 3 compares the performance of PostgreSQL and and production companies. The system only needs to be an implementation of the bespoke system implemented able to answer questions in the form of 1: in Rust using the standard library’s hashmap and Roaring [34] bitmaps. The bespoke solution is an order of 1: How many movies were produced by magnitude faster than the RDBMS. Further, a traditional company and starred actor ? RDBMS has no chance of replicating the execution strategy of the custom solution.1
You could implement this system using a relational database, containing five relations, as shown in the ER diagram in Figure 2. Answering the query for any and can now be done with a simple SQL query. The
intersection of them, but this is essentially just creating the customized solution inside of the DBMS, instead of allowing the DBMS optimizer to find an optimal plan.
The above question may seem trivial: a smart DBA could likely create a similar efect using clever materialized views [35]. To see how program synthesis could help in less trivial cases, imagine designing a system to answer 2:
2: How many movies were produced by and starred actor with a rating s.t.
1 < ≤ 2.
The rating of a movie can be stored as a computed attribute of Movie in Figure 2. Assuming a 5-star review system, a synthesized system similar to the system for 1 could store a bitmap for each discrete rating (i.e., a bitmap for 1 star films, 2 star films, 3 star films, etc.), and then queries could be answered by counting the number of bits in the appropriate bitmaps.
What the customized hashmap solution gains in speed, it loses in generality. Adding additional query types would require a significant re-write. Implementing transaction semantics for adding new actors, movies, or companies may be challenging. But, we know that bespoke data management systems are occasionally created for important applications (e.g., Google Ads [36], Microsoft’s SCOPE [37]), often at a high cost. Depending on the business value of answering 1 or 2 quickly, a more bespoke solution may be worthwhile.
How can we make DBMSes capable of automatically generating the customized hashmap solution for answering 1 or 2, while simultaneously providing the generality and ease-of-use of SQL? Even capturing 50% of 6. Conclusions the bespoke system’s performance in a generic RDBMS would be a huge win. This paper has proposed learned query superoptimiza
One possible way to make that happen is machine pro- tion, an opportunity for the database community to regramming [38], or getting computers to program them- define the task of query optimization for increasinglyselves. Imagine that we can map out the myriad of po- common repetitive analytic workloads. Many of the ideas tential optimizations, from bitmap intersections to aug- mentioned here will be pursued in the coming years. Colmented binary trees. It is possible that program synthesis laborators are welcome! techniques (e.g., [39]), taking only the schema and SQL Query optimization is one of the most well-studied problems in the database community, with a history spanning 50 years [1]. A change to the fundamental “contract” of the query optimizer was proposed in [15]. More recently, we have seen applications of machine learning techniques [47, 48, 49, 50, 51], especially reinforcement learning [2, 23, 3, 5, 52, 53], to the problem of query optimization. [19, 43] show how program synthesis techniques can be used to create custom-tailored relational layouts or key-value stores.
In general, machine programming [38] represents a distinct field of research, and includes work about garbage collection [54], static analysis [55], and program regression detection [56]. Bayesian optimization is a wellstudied area, and [31] provides a survey of this area. [26] inspired the latent space optimization proposed here.
The idea of autonomous experimentation on top of a database system has also been previously explored [57, 58]. To the best of my knowledge, the term “superoptimization” was coined in [59]. eficient parallel processing of massive data sets, [45] I. Trummer, CodexDB: synthesizing code for query Proceedings of the VLDB Endowment 1 (2008) 1265– processing from natural language instructions us1276. URL: https://dl.acm.org/doi/10.14778/1454159. ing GPT-3 codex, Proceedings of the VLDB En1454166. doi:10.14778/1454159.1454166. dowment 15 (2022) 2921–2928. URL: https://dl.acm. [38] J. Gottschlich, A. Solar-Lezama, N. Tatbul, org/doi/10.14778/3551793.3551841. doi:10.14778/ M. Carbin, M. Rinard, R. Barzilay, S. Amarasinghe, 3551793.3551841.
J. B. Tenenbaum, T. Mattson, The three pillars [46] X. Zhou, G. Li, C. Chai, J. Feng, A learned query of machine programming, in: Proceedings of rewrite system using Monte Carlo tree search, Prothe 2nd ACM SIGPLAN International Workshop ceedings of the VLDB Endowment 15 (2021) 46– on Machine Learning and Programming Lan- 58. URL: https://dl.acm.org/doi/10.14778/3485450. guages, MAPL 2018, Association for Computing 3485456. doi:10.14778/3485450.3485456. Machinery, Philadelphia, PA, USA, 2018, pp. 69–80. [47] A. Kipf, T. Kipf, B. Radke, V. Leis, P. Boncz, A. KemURL: https://doi.org/10.1145/3211346.3211355. per, Learned Cardinalities: Estimating Correlated doi:10.1145/3211346.3211355. Joins with Deep Learning, in: 9th Biennial Confer[39] A. Solar-Lezama, Program synthesis by sketch- ence on Innovative Data Systems Research, CIDR ing, Dissertation, University of California, ’19, 2019. URL: http://arxiv.org/abs/1809.00677. Berkeley, United States – California, 2008. [48] B. Hilprecht, C. Binnig, Zero-shot cost models for URL: https://www.proquest.com/docview/ out-of-the-box learned cost prediction, Proceedings 304698243/abstract/1F48A120BE794FFAPQ/1, iSBN: of the VLDB Endowment 15 (2022) 2361–2374. URL: 9781109097450. https://doi.org/10.14778/3551793.3551799. doi:10. [40] J. Ragan-Kelley, C. Barnes, A. Adams, S. Paris, F. Du- 14778/3551793.3551799. rand, S. Amarasinghe, Halide: a language and com- [49] J. Sun, G. Li, An end-to-end learning-based cost piler for optimizing parallelism, locality, and re- estimator, Proceedings of the VLDB Endowcomputation in image processing pipelines, ACM ment 13 (2019) 307–319. URL: https://doi.org/10. SIGPLAN Notices 48 (2013) 519–530. URL: https: 14778/3368289.3368296. doi:10.14778/3368289. //dl.acm.org/doi/10.1145/2499370.2462176. doi:10. 3368296.
1145/2499370.2462176. [50] S. Hasan, S. Thirumuruganathan, J. Augustine, [41] M. B. S. Ahmad, J. Ragan-Kelley, A. Cheung, N. Koudas, G. Das, Deep Learning Models for S. Kamil, Automatically translating image pro- Selectivity Estimation of Multi-Attribute Queries, cessing libraries to halide, ACM Transactions in: Proceedings of the 2020 ACM SIGMOD Inon Graphics 38 (2019) 204:1–204:13. URL: https: ternational Conference on Management of Data, //dl.acm.org/doi/10.1145/3355089.3356549. doi:10. SIGMOD ’20, Association for Computing Ma1145/3355089.3356549. chinery, New York, NY, USA, 2020, pp. 1035– [42] M. Vechev, E. Yahav, G. Yorsh, Abstraction-guided 1050. URL: https://doi.org/10.1145/3318464.3389741. synthesis of synchronization, in: Proceedings doi:10.1145/3318464.3389741. of the 37th annual ACM SIGPLAN-SIGACT sym- [51] R. Heinrich, M. Luthra, H. Kornmayer, C. Binnig, posium on Principles of programming languages, Zero-shot cost models for distributed stream proPOPL ’10, Association for Computing Machinery, cessing, in: Proceedings of the 16th ACM InNew York, NY, USA, 2010, pp. 327–338. URL: https: ternational Conference on Distributed and Event//dl.acm.org/doi/10.1145/1706299.1706338. doi:10. Based Systems, DEBS ’22, Association for Comput1145/1706299.1706338. ing Machinery, New York, NY, USA, 2022, pp. 85– [43] S. Idreos, K. Zoumpatianos, B. Hentschel, M. S. 90. URL: https://doi.org/10.1145/3524860.3539639.
Kester, D. Guo, The Data Calculator: Data Struc- doi:10.1145/3524860.3539639. ture Design and Cost Synthesis from First Princi- [52] H. Behr, V. Markl, Z. Kaoudi, Learn What Reples and Learned Cost Models, in: Proceedings ally Matters: A Learning-to-Rank Approach for of the 2018 International Conference on Manage- ML-based Query Optimization, in: B. Königment of Data, SIGMOD ’18, Association for Comput- Ries, S. Scherzinger, W. Lehner, G. Vossen (Eds.), ing Machinery, New York, NY, USA, 2018, pp. 535– Database Systems for Business, Technology, and 550. URL: https://doi.org/10.1145/3183713.3199671. the Web 2023, BTW ’23, Gesellschaft für Informatik doi:10.1145/3183713.3199671. e.V., 2023. doi:10.18420/BTW2023-25. [44] Immanuel Trummer, GenesisDB: Synthesizing Cus- [53] X. Yu, C. Chai, G. Li, J. Liu, Cost-Based or Learningtomized SQL Execution Engines from Natural Lan- Based? A Hybrid Query Optimizer for Query Plan guage Instructions Using GPT-3 Codex, Techni- Selection, Proceedings of the VLDB Endowment cal Report, Cornell, Ithaca. NY, 2022. URL: https: 15 (2022) 3924–3936. URL: https://dl.acm.org/doi/10. //rm.cab/genesisdb. 14778/3565838.3565846. doi:10.14778/3565838. 3565846. [54] L. Cen, R. Marcus, H. Mao, J. Gottschlich, M. Alizadeh, T. Kraska, Learned Garbage Collection, in: Proceedings of the 4th ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, MAPL @ PLDI ’20, ACM, 2020. doi:https://doi.org/10.
1145/3394450.3397469. [55] N. Hasabnis, J. Gottschlich, ControlFlag: a selfsupervised idiosyncratic pattern detection system for software control structures, in: Proceedings of the 5th ACM SIGPLAN International Symposium on Machine Programming, MAPS ’21, Association for Computing Machinery, New York, NY, USA, 2021, pp. 32–42. URL: https://doi.org/ 10.1145/3460945.3464954. doi:10.1145/3460945.
3464954. [56] M. Alam, J. Gottschlich, N. Tatbul, J. Turek, T. Mattson, A. Muzahid, A zero-positive learning approach for diagnosing software performance regressions, in: Proceedings of the 33rd International Conference on Neural Information Processing Systems, NeurIPS ’19, Curran Associates Inc., Red Hook, NY,
USA, 2019, pp. 11627–11639. [57] R. Snodgrass, Ergalics: A Natural Science of Computation, Position, University of Arizona, Tucson,
AZ, 2010. [58] S. Currim, R. T. Snodgrass, Y.-K. Suh, R. Zhang,
M. W. Johnson, C. Yi, DBMS metrology: measuring query time, in: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, SIGMOD ’13, Association for Computing Machinery, New York, NY, USA, 2013, pp. 421– 432. URL: https://doi.org/10.1145/2463676.2465331.
doi:10.1145/2463676.2465331. [59] H. Massalin, Superoptimizer: a look at the smallest program, ACM SIGARCH Computer Architecture News 15 (1987) 122–126. URL: https://doi.org/10. 1145/36177.36194. doi:10.1145/36177.36194.