A long-standing challenge in databases is Robust Query Optimization (RQO) [12]. Query optimizers rely on selectivity and cost estimates to pick execution plans. When these estimates are inaccurate, the chosen plan can perform far worse than the optimal. There are various approaches towards robust query optimization; we focus on finding a robust query plan in this work: Instead of minimizing the plan cost given the estimated selectivities, which can be wrong, we look for a plan that "performs well" despite uncertainties in the estimates. In other words, when executed at the true selectivities, the plan is expected to incur a low penalty with respect to the cost of the true optimal plan. The resulting optimization problem is challenging because we must consider possible estimation errors and compare with the real optimal plans at the corrected selectivities, which amounts to exploring a neighborhood -rather than a single point -in the selectivity space. The optimization overhead can thus be higher than that for traditional query optimization.
Parametric Query Optimization (PQO) is a technique originally motivated by the desire to reduce optimization overhead for queries that follow the same template but differ in their parameter settings, which frequently arise in applications. Once PQO finds the optimal plan for a given query instance, it caches the plan and reuses it for future query instances whose estimated selectivities are close to the cached plan. Pushing the idea further, Kepler [15], the latest state of the art in PQO, employs deep learning to train a model that selects the right plan among a set of cached candidates.
Combining PQO and RQO is natural, because PQO helps to amortize query optimization overhead across multiple query instances. The potential of this combination was demonstrated in the recent RQO work of PARQO [46], which considered caching one robust plan per query template. However, opportunities for such reuses are limited because the choice of the robust plan varies across the selectivity space. There are better ways to reuse the computation in RQO: intuitively, RQO explores the neighborhood of each query instance; even if two query instances are not close enough to justify the same robust plan, the work of exploring their neighborhoods can still be shared.
Existing PQO approaches, on the other hand, are not designed to find robust plans. Some approaches have heuristics that favor caching plans that tend to be robust, e.g., plans that are close to being optimal at multiple points in the selectivity space. However, these approaches do not consider robustness when selecting plans at runtime. Furthermore, their ability to cache a robust plan depends heavily on what candidates were considered for caching in the first place. As a result, their candidate plans are either too focused on training queries (e.g., [40]) without accounting for errors in selectivity estimates, too spread across the entire selectivity space (e.g., [13]), and/or very expensive to acquire (e.g., Kepler [15], or [13] in high dimensions).
To overcome these limitations, we propose a new PQO system, PAR 2 QO (PARametric Penalty-Aware Robust Query Optimization). This work differs from classical PQO approaches, which primarily aim to amortize optimization overhead by caching point-wise optimal plans, without properly accounting for robustness. It also distinguishes itself from traditional RQO approaches, which focus on finding a single robust plan for a given query instance, without considering reuse opportunities across the broader selectivity space. PAR 2 QO combines both: it aims to produce robust plans as RQO, but leveraging PQO to amortize optimization overhead. Importantly, PAR 2 QO offers a systematic treatment of robustness, guided by a formal definition and development of new PQO and RQO techniques to enable their efficient integration. It is practical to deploy, requiring only non-intrusive access to existing query optimizers and reasonable training and setup time. It also makes its decisions in a transparent manner, with no "black-boxing, " which is easy to understand and debug. Specifically, we make the following technical contributions in this paper: • PAR 2 QO employs a novel method to sample the selectivity space to acquire candidate plans. Leveraging the training workload and a learned model of selectivity estimation errors, PAR 2 QO is able to focus on the most relevant regions of the selectivity space -not only points corresponding to the estimated selectivities of training queries, but also in the neighborhoods induced by uncertainty in these estimates. • PAR 2 QO uses a novel caching strategy in the form of planpenalty profiles, for a carefully selected subset of candidate plans. Instead of caching only the plans themselves, this data structure also caches their cost profiles at sampled selectivities, which allows the best robust plan to be computed at runtime, using a rigorously defined robustness objective. Instead of relying on a black box to predict the most robust plan, the optimization decision is explainable using the error model, plan profiles, and robustness objective. • By focusing its learning efforts on selectivity errors observed from training queries, PAR 2 QO uses only a tiny fraction of the training cost of Kepler. PAR 2 QO's learned error model informs the generation of candidate plans at preparation time and plan selection at runtime, and is able to achieve better query performance than Kepler despite shorter training time. • In the process of evaluating our approach and others, we observed that standard benchmarks such as JOB [27] and DSB [11] are lacking in the PQO setting, because they either offer no guidance on how to generate parameter settings for a query template, or generate them from simple distributions that fail to stress-test PQO. Therefore, we propose a new query workload generator, CARVER (CARdinality coVERage), aimed at generating queries to provide good coverage of the range of possible subquery cardinalities that the optimizer might encounter. When used as training workloads, CARVER also improves the robustness of PQO and its ability to generalize to new workloads. Overall, by defining the robust optimization objective clearly and designing methods accordingly, PAR 2 QO is able to guard against query performance degradations due to selectivity errors and deliver better overall query performance than previous approaches. Experiments show that PAR 2 QO consistently outperforms existing methods across various benchmarks and workloads, achieving up to 1.96× speedup over PostgreSQL and 1.83× over Kepler on JOB. It avoids severe regressions, incurs acceptable training cost, and supports fast inference times. Moreover, PAR 2 QO maintains robust performance under shifting data and query distributions.
Prerequisites. Our solution is designed to work on existing database systems without changing their plan space, execution engine, or optimization procedure. We only assume that the system supports (or can be easily extended to support) the following calls. First, given a query 𝑄, ˆ︁ Sel(𝑄) returns a vector of selectivity estimates for subqueries of 𝑄. Second, Opt(𝑄, s) returns the optimal execution plan for query 𝑄 given the selectivity vector s. Third, Cost(𝜋, s) returns the estimated cost of execution plan 𝜋 given the vector s of relevant selectivities. Typically, the cost of optimization is dominated by Opt; individual ˆ︁ Sel and Cost calls are far cheaper in comparison [17]. For our PostgreSQL-based implementation, we use EXPLAIN to obtain estimates of costs and relevant selectivities, the same mechanism in earlier work [21,46] for selectivity injection, and pg_hint_plan [34] for specifying the plan.
Parametric Query Optimization (PQO). A query template Γ has a set params(Γ) of query parameters drawn from various domains. A query (instance) 𝑄 following Γ, denoted by 𝑄 ∼ Γ, assigns a specific set params(𝑄) of values to the set of parameters in params(Γ).
To avoid repeating expensive Opt calls for workloads with many instances of the same query template, PQO precomputes and/or maintains information for Γ that enables it to efficiently find, for a given query 𝑄 ∼ Γ, an execution plan whose cost is not much higher than that of Opt(𝑄, ˆ︁ Sel(𝑄)), without making an Opt call. Typically, PQO uses a per-template plan cache, which contains a set of candidate plans for the template, and selects the best plan from them for each incoming query at runtime.
Robust Query Optimization (RQO). In reality, when optimizing a query 𝑄, the system does not have the true selectivities s, but instead their estimates s ˆ. To quantify the penalty of making a wrong selection and to define a "robust" plan formally, we adopt the following general framework of PARQO [46] based on stochastic optimization, which is flexible enough to encode many notions of robustness found in previous work and applications [1,4,44].
We assume a user-defined penalty function Penalty(𝜋, s) specifying the penalty incurred by executing a potentially non-optimal plan 𝜋 under the true selectivities s. We use the same default as PARQO, but note that our approach works for any choice of Penalty:
Here, Cost ★ (s) = Cost(Opt(𝑄, s), s) is the (surrogate) optimal cost, approximated by the estimated cost of the best plan obtained by the optimizer assuming the knowledge of the true selectivities s; Cost(𝜋, s) is the estimated cost of 𝜋 when executing under s. Equation (1) defines penalty to be proportional to the amount of cost exceeding the optimal, but only if it is beyond the prescribed tolerance (𝜏 = 0.2 following the convention [1,10,13,44,46]).
Since selectivities are uncertain, we model them as a random vector S. Assuming that S ∼ 𝑓 (s|s ˆ), the probability density function for the distribution of true selectivities s conditioned on the estimates s ˆ, we can then define the most robust plan for 𝑄 as the one that minimizes the expected penalty E[Penalty(𝜋, S) | ˆ︁ Sel(𝑄)].
Parametric Robust Query Optimization. The problem is defined as follows. Given a query template Γ, a (training) database instance D, and a (training) query workload 𝑊 of queries following Γ:
• (Cache preparation) Compute a data structure from D and 𝑊 .
• (Runtime plan selection) Given a query 𝑄 ∼ Γ, use the cached data structure to find a robust plan for 𝑄.
We first present two baseline solutions in Section 2.2 and then discuss our main solution in Section 3.
Parametric Query Workload Generation. In a "cold-start" variant of the above setup, the training query workload 𝑊 is not given. This variant requires addressing the following problem: given a query template Γ and a database instance D, generate query workload 𝑊 following Γ. Informally, we would like the generated workload to serve as a good workload for training and/or testing a parametric robust query optimizer. To this end, the generated queries should provide good coverage of the various selectivity scenarios that the optimizer can potentially encounter, including situations when the data distribution may change and the query distribution may be different. We present our solution in Section 4.
PARQO [46], a state-of-the-art robust query optimization framework, proposes caching one robust plan per template and reusing it opportunistically at runtime. This approach serves as a rather weak baseline for PQO; hence, we additionally propose a stronger baseline called PARQO ′ , which elevates it into a full-fledged solution for parametric robust query optimization. We first briefly review the components of PARQO below and then describe PARQO ′ .
Error Profiling. PARQO uses the database instance D and the query workload 𝑊 to learn an error model E for query template Γ that allows us to construct the conditional distribution of true selectivities 𝑓 (s|s ˆ) given the estimated selectivities s ˆ= ˆ︁ Sel(𝑄) for a query 𝑄 ∼ Γ. In general, optimizing a complex query may involve many selectivities, from single-table selections to multi-table selection-join subqueries; it would be infeasible to acquire all possible selectivities and represent the full joint distribution of all their errors. Therefore, PARQO chooses to model E using a collection of error profiles, each capturing a querylet, i.e., a small subquery template (up to a three-table selection-join) in Γ. We collect these profiles by comparing the optimizer estimates with the real subqueries cardinalities observed by executing 𝑊 over D. Each error profile contributes a factor to the joint distribution 𝑓 (s|s ˆ).
Finding a Robust Plan. Given a plan 𝑄 ∼ Γ and s ˆ= ˆ︁ Sel(𝑄), PARQO computes a robust plan for 𝑄 per Equation (1) as follows. First, to tame the complexity of subsequent optimization, PARQO identifies a small number of sensitive dimensions among those of s ˆwhose uncertainty impacts the penalty the most. This dimensionality reduction is guided by a careful sensitivity analysis that assesses each dimension's contribution to the overall variance in penalty, using Monte-Carlo sampling from 𝑓 (s|s ˆ). Second, PARQO draws a number of selectivity samples from 𝑓 (s|s ˆ) restricted to the sensitive dimensions, and invokes Opt with sampled selectivities to obtain a set of candidate plans. Finally, PARQO returns the candidate plan with the least expected penalty, estimated by recosting the plan at sampled selectivities and comparing its costs with the respective optimal plans at these locations.
Parametric Robust Query Optimization with PARQO. The method above is designed to find a robust plan for a single query instance. Since the overhead of finding a robust plan is high, PARQO caches a robust plan per query template. Let 𝑄 c denote the query that the cached robust plan was optimized for, and let s ˆc denote the estimated selectivities for 𝑄 c . At runtime, given a new query 𝑄 with the same template and estimated selectivities s ˆ, PARQO tests if the Kullback-Leibler (KL) divergence of 𝑓 (s|s ˆ) from 𝑓 (s|s ˆc) is below a prescribed threshold 𝜃 KL . If yes, 𝑄 and 𝑄 c will be almost indistinguishable from the perspective of a cardinality-based optimizer, so PARQO simply returns the cached plan for 𝑄. Otherwise, PARQO falls back to calling Opt(𝑄, s ˆ) to obtain a plan for 𝑄, with no guarantee of robustness.
PARQO ′ : A Stronger Baseline. We extend PARQO to obtain a strong baseline for PQO as follows. To prepare the cache:
• Learn an error model E from D and 𝑊 .
which consists of a set of candidate robust plans (𝜋 𝑖 ) along with the respective selectivities (s 𝑖 ) they were obtained under. Starting with an empty C, we iterate through each query 𝑄 ∈ 𝑊 with estimated selectivities s ˆ. We calculate the KL divergence of 𝑓 (s|s ˆ) from 𝑓 (s|s 𝑖 ) for each candidate ⟨𝜋 𝑖 , s 𝑖 ⟩ ∈ C. If the divergence is below 𝜃 KL for at least one existing candidate, meaning that 𝑄 is already "covered" by C, we move on. Otherwise, we find a robust plan 𝜋 for 𝑄 and add ⟨𝜋, s ˆ⟩ to C. At runtime, given a query 𝑄, we find the candidate ⟨𝜋 𝑖 , s 𝑖 ⟩ ∈ C that minimizes the KL divergence of 𝑓 (s| ˆ︁ Sel(𝑄)) from 𝑓 (s|s ˆ𝑖 ), and return 𝜋 𝑖 as a robust plan for 𝑄. No Opt or Cost calls are needed.
A main issue with PARQO ′ is that in order for a query 𝑄 to reuse a cached plan 𝜋 𝑖 reliably, 𝑓 (s| ˆ︁ Sel(𝑄)) must be very similar to 𝑓 (s|s 𝑖 ), so many ⟨𝜋 𝑖 , s 𝑖 ⟩ may be needed to cover the entire selectivity space. However, finding each robust plan to add to the cache is expensive, which makes the cache preparation cost high.
A key insight into beating the baseline in Section 2.2 is to reuse the computation involved in finding a robust plan, rather than reusing the result plans directly. We illustrate the opportunities for reusing computation with a simple conceptual example. For brevity, we will refer to ˆ︁ Sel(𝑄) as the "location" of query 𝑄 in the selectivity space. Intuitively, 𝑓 (s| ˆ︁ Sel(𝑄)) defines a "neighborhood" around (but not necessarily centered at) 𝑄, and finding a robust plan for 𝑄 involves exploring this neighborhood. Suppose PARQO ′ has cached two plans 𝜋 1 and 𝜋 2 whose neighborhoods are both near 𝑄's, but neither is close enough for 𝑄 to justify reuse. Nonetheless, the two neighborhoods together provide sufficient coverage for 𝑄's neighborhood. Recall that finding 𝜋 1 and 𝜋 2 in the first place required sampling plans in their neighborhoods. The same samples should be useful for finding a robust plan for 𝑄.
This insight leads us to our new solution PAR 2 QO. It changes the strategy of caching robust plans for previously seen queries of a template to caching a data structure 𝔓 called the plan-penalty profiles. On a high level, 𝔓 compactly represents how a set of robust plan candidates performs relative to the optimal plans (per Equation (1)) over a set of probe locations in the selectivity space. PAR 2 QO intelligently samples probe locations and uses the optimal plans to seed the set of candidate plans. This set may be too big, so for efficiency, PAR 2 QO further reduces this set to construct 𝔓. At runtime, given a query 𝑄, PAR 2 QO uses 𝔓 to estimate the expected penalties of candidate plans over 𝑓 (s| ˆ︁ Sel(𝑄)), by reweighing per-location penalties to remove sampling bias, and selects the best.
While the high-level idea is simple, interesting challenges lie in how to design an effective sampling scheme for probe locations and how to reduce the candidate plan set in order to facilitate the identification of robust plans at runtime. In the remainder of this
Training queries (𝑊) Error model (ℰ) Error profiling Probe location sampling Find & cost candidate plans (𝒫) at ℒ; perform reduction Probe locations (ℒ) Plan-penalty profiles (𝔓) Robust plan Offline cache preparation Runtime plan selection Query (𝑄) & est. selectivities (& 𝒔) section, we describe the details of PAR 2 QO, whose workflow is depicted in Figure 1. Cache preparation proceeds in three steps:
• Given D and query workload 𝑊 , learn an error model E. This step is the same as the error profiling step discussed in Section 2.2. • Sample a set L of probe locations (Section 3.1).
• Find and cost candidate plans at L, and reduce/summarize the information into the plan-penalty profiles 𝔓 (Section 3.2).
Selection of a robust plan at runtime is covered in Section 3.3. Finally, Section 3.4 presents an in-depth discussion of PAR 2 QO by contrasting it with other state-of-the-art approaches, highlighting the novelty of our solution and how it represents a more principled approach to achieving plan robustness, whose advantages will also be empirically demonstrated in Section 5.
There are two natural ideas. First, sampling should be informed by the query workload 𝑊 because, intuitively, we do not want to devote much effort to regions that do not matter to queries. Second, for each query 𝑄, we want to probe not only the location ˆ︁ Sel(𝑄), but also locations in the neighborhood defined by 𝑓 (s| ˆ︁ Sel(𝑄)), because they might yield the true optimal plan for 𝑄.
A naive approach is to randomly sample some locations in the neighborhood of each 𝑄, but there are two pitfalls. First, if the workload 𝑊 is skewed, some regions of the selectivity space will be over-sampled. Such high concentrations of samples are wasteful because they have diminishing returns on improving our understanding of these regions. Second, overemphasis on popular queries diverts resources from handling less common queries that may turn out to be costly and stand to benefit more from robust plans.
Our idea is to employ a check akin to the reuse check in PARQO ′ (Section 2.2) to prevent over-sampling in a region: if a query "hits" a region previously sampled, we do not sample more from this region. We also track how often a region is hit by queries in 𝑊 , which empirically captures the query distribution and allows us to estimate the sampling probabilities of probe locations, useful for bias correction later (Section 3.3).
The algorithm proceeds as follows. We organize the set of sampled probe locations into clusters {⟨L 𝑖 , s 𝑖 , ℎ 𝑖 ⟩}, where L 𝑖 denotes the set of probe locations in cluster 𝑖, s 𝑖 serves to remember the distribution 𝑓 (s|s 𝑖 ) from which L 𝑖 was sampled, and ℎ 𝑖 tracks how many queries in𝑊 hits this cluster. For each workload query 𝑄 ∈ 𝑊 , we find the cluster ⟨L 𝑖 , s 𝑖 , ℎ 𝑖 ⟩ that minimizes the KL divergence of 𝑓 (s| ˆ︁ Sel(𝑄)) from 𝑓 (s|s 𝑖 ). If this minimum divergence is below the prescribed threshold 𝜃 KL , we increment ℎ 𝑖 by one and move on. Otherwise, we sample 𝑛 locations from 𝑓 (s| ˆ︁ Sel(𝑄)), and create a new cluster {⟨L new , ˆ︁ Sel(𝑄), 1⟩}, where L new contains the newly sampled locations. At the end of the process, let 𝑚 ≤ |𝑊 | denote the final number of clusters. Overall, L is the union of all L 𝑖 's, with 𝑚𝑛 locations total. The lower-right quarter of Figure 2 graphically illustrates our probe location sampling approach, in comparison with previous work, which is further discussed in Section 3.4.
With the set L of probe locations, the next step is to invoke the query optimizer to find and cost candidate plans at L, and then post-process the resulting information into a plan-penalty profile 𝔓. Conceptually, 𝔓 is a matrix whose rows correspond to candidate plans and columns correspond to the probe locations. The entry 𝔓[𝜋, s] records the value of Penalty(𝜋, s) defined by Equation ( 1), and the row vector 𝔓[𝜋, •] represents the penalty profile for 𝜋.
As the first step in building 𝔓, we obtain an initial set P of candidate plans and construct a plan-cost matrix C, where each row vector C[𝜋, •] represents the cost profile of candidate plan 𝜋 ∈ P, i.e., its costs at all probe locations. To collect the set P, we call Opt(𝑄, s) to obtain the optimal plan for each probe location s ∈ L. Note that |P| ≤ |L| because it is possible for the optimizer to choose the same plan for multiple locations.
Then, for each distinct candidate 𝜋 ∈ P, we call Cost(𝜋, s) for each s ∈ L, and store the result in entry C[𝜋, s]. The overall running time of this step is dominated by |L| calls to Opt and |P| • |L| calls to Cost. At this point, we can simply compute 𝔓 from C by calculating each entry 𝔓[𝜋, •] using Equation (1), with Cost(𝜋, s) = C[𝜋, s] and Cost ★
However, the size of 𝔓 can be large because of the number of candidate plans. For example, in our experiments in Section 5, templates 22 and 24 from the JOB benchmark [27] produced more than 300 candidate plans. Hence, we next focus on reducing the set P of candidate plans to a small number 𝑘. After reduction, the size of 𝔓 becomes O(𝑘 |L|). Besides saving space and improving inference speed, a good plan reduction method can also help improve robustness (and hence query performance), which we will validate empirically in Section 5.
We consider two plan reduction methods below. The first method prefers choosing plans that are near-optimal at many probe locations, which heuristically reflects robustness. The second method is more conservative: it chooses a set of representative plans that can substitute for others, without second-guessing robustness at this point (later, the runtime plan selection procedure will pick, among these representatives, the best plan for the given query according to the more precise robustness criterion). We give an example comparing the results of these methods in the full version [47].
Reduction by 𝜏-Approximate Cover. The first method follows a natural heuristic: we prefer plans that are near-optimal at a large number of probe locations. The same heuristic and its variants have been employed by various PQO methods including QueryLog [40] and Kepler [15]. More precisely, we say that a plan 𝜋 covers probe location
where 𝜏 is the same as in Equation (1). Given 𝑘, the target number of candidate plans after reduction, we want to choose a subset of 𝑘 plans in P that together cover as many probe locations as possible.
This problem is an instance of the set cover problem [43], where a simple greedy algorithm offers an approximation ratio of 𝐻 (|L|) ≤ ln |L| + 1 (in terms of the number of candidates needed to cover all probe locations). In each step, we greedily pick the candidate plan that covers the most number of probe locations that have not been covered yet. The running time is O(|P| • |L|), with no optimizer calls, and is negligible compared with the time to acquire C.
We expect this method to work well in practice, because its heuristic generally reflects robustness. However, it can miss robust plans. The reason is that this heuristic, by considering the overall number of probe locations covered, reflects a "global" measure of robustness, but at runtime, robustness in fact depends on the "local" neighborhood around the query of interest.
Reduction by Cost Profile Similarity. Our second, more conservative, method aims to choose representative plans that can generally substitute for others. To capture the extent to which two plans 𝜋 and 𝜋 ′ can substitute for each other, we want a distance metric reflecting the similarity between their cost profiles C[𝜋, •] and
To this end, we adopt the Jensen-Shannon distance between the two discrete distributions 𝑃 and 𝑃 ′ represented by the respective profiles. More precisely, this distance is calculated as the square root of the average between the KL divergence from 𝑃 to 𝑀 and the KL divergence from 𝑃 ′ to 𝑀, where 𝑀 = (𝑃 + 𝑃 ′ )/2 is a mixture distribution of 𝑃 and 𝑃 ′ . An alternative would be the Wasserstein distance, which is better at capturing shape and location differences between distributions, but we choose Jensen-Shannon because of its low computational complexity.
Then, given the target number 𝑘, we want to choose a subset of plans in P that minimizes the maximum distance between any plan in P to its closest among the 𝑘 chosen. This problem is an instance of the metric 𝑘-center problem [43], and a range of clustering algorithms are applicable. Our implementation uses a simple greedy algorithm based on the farthest-first traversal, which gives an approximation ratio of 2. We choose the first candidate plan randomly from P and place it in our solution set 𝑆. While |S| < 𝑘, we add to 𝑆 the plan 𝜋 in P \ 𝑆 that maximizes the distance between 𝜋 and plans already in 𝑆. We stop and return 𝑆 once |S| = 𝑘. The running time is O(𝑘 • |P| • |L|), where the |L| factor reflects the running time of one distance computation. Again, there are no optimizer calls, so the cost is negligible compared with constructing C.
At runtime, PAR 2 QO has access to the error model E, the planpenalty profiles 𝔓 with 𝑘 candidate plans (Section 3.2), as well as additional information on the probe locations L (Section 3.1). Given a query 𝑄, PAR 2 QO uses E to derive 𝑓 (s| ˆ︁ Sel(𝑄)), the distribution of true selectivities conditioned on the estimates. Then, PAR 2 QO estimates the expected penalty (Section 2.1) for each of the 𝑘 candidate plans, and returns the plan with the lowest estimate. To estimate E[Penalty(𝜋, S) | ˆ︁ Sel(𝑄)] for candidate plan 𝜋, we use its penalty profile 𝔓[𝜋, •]. If the probe locations were sampled from 𝑓 (s| ˆ︁ Sel(𝑄)), the average penalty would yield an unbiased estimate of the expected penalty. However, since the probe locations were sampled differently, we must reweigh the penalties to correct the bias using the method of importance sampling.
The core idea is to reweigh the penalty at each probe location based on how likely that location is sampled from the target distribution 𝑓 (s| ˆ︁ Sel(𝑄)) and how likely that location is sampled from our sampling distribution. Recall from Section 3.1 that probe locations are organized into 𝑚 clusters with 𝑛 locations in each. For the 𝑖th cluster ⟨L 𝑖 , s 𝑖 , ℎ 𝑖 ⟩, its 𝑛 probe locations L 𝑖 = {s 𝑖,1 , s 𝑖,2 , . . . , s 𝑖,𝑛 } are sampled from 𝑓 (s|s 𝑖 ).
Since the 𝑖-th cluster was hit ℎ 𝑖 times by training queries, we estimate the sampling probability of this cluster as ℎ 𝑖 / ∑︁ 𝑚 𝑖=1 ℎ 𝑖 = ℎ 𝑖 /|𝑊 |, which measures how frequently Sel 1 Sel 2 Plan diagram's plans Sample uniformly in selectivity space Sel 1 Sel 2 QueryLog Sample and cost only at query points Sel 1 Sel 2 Over-concentration of samples possible Sample around each query point using fixed RCE strategy; cost only at query points Kepler Sel 1 Sel 2 Ensure just enough samples in every query region Sample and cost around query points according to error model PAR2QO Figure 2: Illustration of locations in a 2-d selectivity space where various PQO approaches obtain candidate plans (circles) and cost them (crosses), using training queries (squares) when applicable. a new query falls into cluster 𝑖 based on how many times it was encountered during training. Combining both components above, we estimate the sampling probability of a specific location to be 𝑠 𝑖,𝑗 as (ℎ 𝑖 /|𝑊 |) • 𝑓 (s 𝑖,𝑗 |s 𝑖 ). Meanwhile, the likelihood of this location under the target distribution is 𝑓 (s 𝑖,𝑗 | ˆ︁ Sel(𝑄)). Hence, overall, the expected penalty of 𝜋 is estimated as: 1
Since we use expected penalties to rank plans, we can simplify the above calculation into the following, by dropping terms that do not affect the ranking:
As an additional optimization, we can also cache the value of 𝑓 (s 𝑖,𝑗 |s 𝑖 ) when generating s 𝑖,𝑗 . Overall, the selection of the robust plan can be done by a single pass over 𝔓, so the running time is O(𝑘 |L|). No optimizer calls are needed except the single ˆ︁ Sel(𝑄) call to obtain the estimated selectivities.
We contrast PAR 2 QO with other PQO approaches, including two state-of-the-art systems, Kepler [15] and QueryLog [40]. Note that while previous PQO approaches do not specifically optimize for finding robust plans, many do have components whose heuristics favor keeping robust plans as candidates. We first highlight differences between PAR 2 QO and Kepler [15], illustrated by the lower-right and lower-left quarters of Figure 2.
(1) Kepler executes plans for all training queries as well as alternative plans obtained via row-count evolution (RCE). Measuring actual execution times makes Kepler robust against errors not only in selectivity estimation but also in plan cost models. In contrast, PAR 2 QO only executes (counting versions of) training queries (and no alternative plans) to learn an error model for selectivities, and it "trusts" Cost(𝜋, s) given correct s. Hence, PAR 2 QO spends significantly less time preparing its cache. In Section 5, we will see that focusing on selectivity errors delivers comparable or better query performance than Kepler despite a much lower initial cost. (2) Kepler explores the "neighborhood" of a training query 𝑄 using RCE, which perturbs subquery selectivities in order to discover more candidate plans. This method hence improves robustness, analogous to PAR 2 QO sampling from 𝑓 (s| ˆ︁ Sel(𝑄)) according to the error model (Section 3.1). However, RCE uses a fixed strategy for generating perturbations (exponentially spaced in selectivity ranges), which we believe is not as effective as PAR 2 QO's perturbations informed by the error model.
(3) The same 𝜏-approximate cover method in Section 3.2 is employed by Kepler to reduce the set of candidate plans. As discussed earlier, this method helps to improve "global" robustness (over the training workload). However, unlike PAR 2 QO, which has a built-in mechanism (Section 3.1) to avoid overrepresenting popular queries, the effectiveness of Kepler's plan reduction is susceptible to an imbalanced query workload. Moreover, in determining coverage, Kepler does not consider the costs of candidate plans at locations obtained by RCE; hence, its notion of coverage is much narrower than ours. (4) Kepler makes its runtime plan selection using a neural network, combined with a method to assess prediction uncertainty. However, it is difficult to justify plan choices and interpret uncertainty. In contrast, PAR 2 QO's plan selection is transparent; the availability of the error model and the plan penalty profiles makes the selection process easy to understand.
The last point above, on PAR 2 QO's advantage of interpretability over Kepler, also applies to other black-box methods. While effective in many scenarios, these methods obscure the rationale behind plan choices, making it difficult to interpret model behavior, diagnose the root causes of regressions, and implement corrections. In contrast, PAR 2 QO's decisions can be explained by the chosen plan's cost penalty profile and the error model of selectivity estimates, as our robustness objective is clearly defined. A recent system demonstration based on PARQO [48] shows how, given any two plans (e.g., robust vs. optimizer default), it can compare and inspect their robustness by visualizing their costs over the region of uncertainty surrounding the initial selectivity estimates. Users can see potential selectivities for which the robust plan avoids severe performance regressions. If, for any reason, robust plans frequently underperform because actual selectivity errors do not follow the error model, a clear corrective step would be to recalibrate the error model. Such ease of interpretability and diagnosis would be difficult if not impossible to achieve for black-box methods.
Next, we compare PAR 2 QO with PQO approaches that are not based on deep learning. The most recent representative is Query-Log [40], illustrated by the upper-right quarter of Figure 2. We also touch on some earlier approaches, including plan diagrams [13], illustrated by the upper-left quarter of Figure 2.
(1) To find candidate plans, previous work has generally used one of the following two methods. The first method, used by earlier approaches including the pioneering work of anorexic plan diagrams [13], attempts to cover the entire selectivity space, but quickly becomes intractable beyond 5-6 dimensions. The second method, used by QueryLog, is to sample past queries for candidate plans. However, QueryLog has no mechanism for further perturbing selectivities to obtain potentially better plans, like PAR 2 QO's sampling (Section 3.1) or Kepler's RCE. (2) To reduce the set of candidate plans, most PQO approaches, like Kepler, use the 𝜏-approximate cover method in Section 3.2 or some variants. For example, anorexic plan diagrams use the same method; QueryLog seeks a cover that minimizes an "aggregate sub-optimality" measure, which is close in spirit to this method. While this reduction naturally favors robust plans, its benefit is limited here because of how the candidates were generated in the first place: neither uniformly sampling the entire selectivity space nor focusing on the locations of the training queries alone comes close to PAR 2 QO in the ability to capture the effect of selectivity estimation errors on robustness. (3) To select among candidate plans at runtime, QueryLog employs a model using contextual multi-armed bandit learning, which can adapt dynamically over time, while earlier approaches generally perform no better than recosting all candidate plans for the query and picking the cheapest. None aims at picking a robust plan like PAR 2 QO does.
In summary, PAR 2 QO offers a systematic treatment of robustness -driven by a formal definition of robustness against errors in selectivity estimates -from initial learning of the error model, sampling of probe locations and candidate plans, construction of the plan-penalty profiles, to plan selection at runtime.
Training and testing query optimizers require a query workload, whose choice is not always clear. Synthetic benchmarks (e.g., DSB [11]) typically use standard distributions (e.g., Gaussian) to generate parameter settings for given templates. Alternatively, if the database has been operating for some time, past queries can be used for the workload. In either case, there is no guarantee that such workloads reflect future queries. If our goal is robust query optimization, it is natural to make training and testing queries cover the possible scenarios that a query optimizer may potentially encounter, as comprehensively as possible. Indeed, recent work on Kepler [15] generates parameter settings for a given query template by uniformly sampling rows from the full join result (with no selections applied), ensuring that every join result row has a chance to be covered by the generated query workload.
As argued in Section 1, however, we need a still better notion of coverage. Recall that a cost-based optimizer makes its decisions by estimating the selectivities of query predicates. Hence, it would be useful for the workload to include queries that exhibit a diverse range of selectivities. By randomly sampling final join result rows, Kepler will tend to overrepresent popular column values in its query parameters. Second, optimizer decisions are heavily influenced by the cardinalities of subqueries. Therefore, we should also generate scenarios that cover the range of possible subquery cardinalities, instead of focusing only on the final join result as Kepler does.
CARVER meets the above requirements by providing a flexible and powerful way for users to ensure that the generated queries provide good coverage of the optimization scenarios. Formally, given a database instance D and a query template Γ with a set params(Γ) of parameters, our goal is to generate a set of queries following the template Γ, where each query assigns a specific value to each parameter in params(Γ). Overall, CARVER works as follows. It randomly generates queries following template Γ from a mixture distribution {(𝑃 𝑘 , 𝑤 𝑘 )}, whose components (𝑃 𝑘 's) and associated weights (𝑤 𝑘 's) are specified by the user. Each component 𝑃 𝑘 is specified by a set of subquery templates {𝛾 𝑘,𝑗 } of Γ whose parameters form a disjoint partitioning of params(Γ). 𝑃 𝑘 is defined as the product distribution ∏︁ 𝑗 𝑃 𝑘,𝑗 , where each 𝑃 𝑘,𝑗 is a distribution governing the generation of values for params(𝛾 𝑘,𝑗 ) in the subquery template {𝛾 𝑘,𝑗 }.
We now describe the procedure for generating from 𝑃 𝑘 𝑗 for each params(𝛾 𝑘,𝑗 ). We assume that 𝛾 𝑘,𝑗 is a selection-join query template, and that it can be rewritten as 𝜎 𝜃 (𝑞), where 𝑞 is the (parameterless) base query obtained from 𝛾 𝑘,𝑗 by "removing" all atomic query predicates involving parameters, 1 and 𝜃 is the remainder predicate involving params(𝛾 𝑘,𝑗 ). The selectivity of a setting in params(𝛾 𝑘,𝑗 ) is defined as |𝜎 𝜃 (𝑞(D))|/|𝑞(D)| where 𝜃 is instantiated with the given setting. Users can specify a bucketization 𝐵 of the selectivity range (not necessarily equally spaced), e.g., 𝐵 = {[0, 0.5%), [0.5%, 1%), [1%, 2%), . . . , [90%, 1]}; CARVER will generate an equal number of params(𝛾 𝑘,𝑗 ) settings for each bucket of 𝐵, up to the number of possible settings for this bucket.
Intuitively, including a subquery in the definition of mixture component guides CARVER to ensure that its generated parameters provide good coverage of the possible subquery cardinalities. Additionally, including subqueries joining multiple tables and involving multiple query parameters ensures that CARVER accounts for dependencies among join and selection predicates.
Depending on the type and complexity of the remainder predicate 𝜃 , the generation procedure varies. We present several common cases below. Because of space constraints, we provide a detailed example and discuss additional challenges in the full version [47].
Equality Selections. Here, 𝜃 has the form
where each 𝐴 𝑖 is a column of some input table in 𝑞. First, we group the result rows of 𝑞 by 𝐴 1 , . . . , 𝐴 𝑛 and compute the row count for each group. The selectivity of 𝜃 for each group (using the group-by values for parameter setting) is simply the group row count divided by |𝑞|, the total of all group row counts. Second, we sort the groups by their counts and bucketize them according to 𝐵. Finally, we draw an equal number of samples from each bucket (unless limited by the number of groups available in the bucket). Note that the first and second steps can be computed conveniently in SQL using a SELECT-FROM-WHERE-GROUPBY-ORDERBY statement.
Note that the above procedure also handles the case of a single "not-equal-to" selection, i.e., 𝜃 has the form 𝐴 ≠ 𝑣, by computing the selectivity of 𝑣 as one minus its group row count divided by |𝑞|.
Inequality Selections. Suppose that 𝜃 has the form
As with the case of equality selections, we first group the result rows of 𝑞 by 𝐴 1 , . . . , 𝐴 𝑛 and compute the row count for each group. We then sort the groups by 𝐴 1 , . . . , 𝐴 𝑛 ; the result is conceptually a 𝑛-dimensional array A representing a discrete probability density function. Let A[𝑣 1 , . . . , 𝑣 𝑛 ] denotes the array entry for (𝑣 1 , . . . , 𝑣 𝑛 ). Next, we compute the cumulative density function (CDF) over A in-place (details to be presented shortly). We then sort A by the CDF values and bucketize them according to 𝐵. Finally, we draw an equal number of samples from each bucket (again, subject to availability). All processing before the CDF computation can be done easily in SQL.
In more detail, the CDF can be computed as follows, by accumulating A over one additional dimension at a time. In the first step, for each setting of 𝐴 1 , . . . , 𝐴 𝑛-1 to 𝑣 1 , . . . , 𝑣 𝑛-1 , we update the subarray A[𝑣 1 , . . . , 𝑣 𝑛-1 , *] to be the conditional CDF over 𝐴 𝑛 by computing the prefix sum over its elements. In general, the step accumulating over 𝐴 𝑖 updates each subarray A[𝑣 1 , . . . , 𝑣 𝑖 -1 , *, . . . ] to be the conditional CDF over 𝐴 𝑖 , . . . , 𝐴 𝑛 while setting 𝐴 1 , . . . , 𝐴 𝑖 -1 to 𝑣 1 , . . . , 𝑣 𝑖 -1 ; each such subarray is updated in-place as the prefix sum over its constituent subarrays updated in the previous step. The last step updates A to be the overall CDF.
The above procedure can be easily extended to support other inequality predicates: 𝐴 𝑖 < 𝑣 𝑖 can be supported by handling the bucket boundaries slightly differently; 𝐴 𝑖 > 𝑣 𝑖 and 𝐴 𝑖 ≥ 𝑣 𝑖 can be handled by reversing 𝐴 𝑖 (from ascending to descending) in the sort order of the groups. It is also possible to support range predicates in the form of 𝐴 𝑖 BETWEEN 𝑙 𝑖 AND 𝑢 𝑖 by conceptually duplicating the column 𝐴 𝑖 in input data as columns 𝐴 𝑙 𝑖 and 𝐴 𝑢 𝑖 , and handling the predicate as 𝐴 𝑙 𝑖 ≥ 𝑙 𝑖 ∧ 𝐴 𝑢 𝑖 ≤ 𝑢 𝑖 . LIKE Selection. Suppose that 𝜃 has the form 𝐴 LIKE 𝑣. The design space for the generation procedure is large. We describe below the token-based approach currently employed by CARVER. Exploration of alternative approaches, such as using language models to further classify different types of LIKE-operators [3], is left for future work. First, we make one pass over the result rows of 𝑞 to tokenize all 𝐴 values. If 𝐴 in general contains multi-word strings, we tokenize each 𝐴 value into words. Otherwise, we tokenize each 𝐴 value into characters. During the pass, we maintain the set of tokens along with the number of 𝑞 result rows whose 𝐴 value contains this token. Second, we sort the tokens by their counts and bucketize them according to 𝐵. Finally, the same sampling procedure is carried out over the buckets. Each token token sampled corresponds to the predicate 𝐴 LIKE '%token%'.
The above procedure can be extended to a conjunction of LIKE selections. For example, to handle 𝐴 1 LIKE 𝑣 1 ∧𝐴 2 LIKE 𝑣 2 , for each result row 𝑞, we will tokenize both 𝐴 1 and 𝐴 2 values and consider all pairs of tokens, one from 𝐴 1 and the other from 𝐴 2 . We maintain the set of token pairs along with the number of 𝑞 result rows whose 𝐴 1 and 𝐴 2 contain the tokens in the pair, respectively.
Databases and benchmarks. Here, we focus on experiments using JOB (Join Order Benchmark) [29], based on real-world IMDB data, consisting of 33 query templates. It is designed to challenge optimizers with skewed/correlated data distributions and intricate join relationships. We have also performed evaluation using DSB [11], a recently introduced industrial benchmark built on synthetic data, extending TPC-DS [35] with more sophisticated data distributions and correlations. Due to space constraints, however, its results are discussed only in the full version [47].
Workload synthesis. For JOB, we generate three different workloads: CARVER, Uniform, and Historical. For CARVER, we consider the one-component scenario by default, regarding all 2-table querylets as the set of subquery templates {𝛾 𝑘,𝑗 } in our generator, and the selectivity bucketing for each params(𝛾 𝑘,𝑗 ) is performed by partitioning the GROUP BY results into ten equally spaced selectivity ranges, i.e., 𝐵 = {[0, 10%), [10%, 20%), . . . , [90%, 1]}. For Uniform, we first perform a full join across all tables based on the join conditions specified in the query templates. We then sample params(Γ) uniformly from the join result, same as the synthetic method in Kepler [15]. For Historical, we follow the methodology in PARQO [46]; additional workload details are available in the full version [47]. For all workload generation methods, after initial synthesis, we further ensure only queries that return nonempty results are included. We synthesize 250 queries for each params(Γ): 50 queries are used to initialize and train PQO models; the remaining 200 queries serve as the testing workload for evaluation.
PAR 2 QO setup. We implement PAR 2 QO on top of PostgreSQL V16.2, leveraging plan and selectivity injection tools from prior work [21,34,46]. For each Γ, we learn the error model 𝑓 (s|s ˆ) using relevant querylets containing up to 3-table subqueries, following the same procedure in PARQO [46]. Unless otherwise specified, we set 𝑛 = 50 as the number of probe locations per cluster and 𝜃 KL = ln(200) as the prescribed KL divergence threshold. The sample size is user-configurable, and we demonstrate that even with this relatively small number of probe locations, PAR 2 QO achieves strong performance. The target upper bound on the number of candidate plans after reduction is max(0.2 • |P|, 10), where 10 ensures sufficient diversity when the initial |P| is small. For plan reduction, we use 𝜏-approximate cover (𝜏-Cover in short) by default. Section 5.3 further examines the impact of these choices.
The remainder of this section is structured as follows: First, we compare PAR 2 QO's query performance against others in Section 5.1. Next, Section 5.2 compares their overhead (training and inference). Section 5.3 evaluates the contributions of components and parameter settings in PAR 2 QO through a series of ablation studies. Then, Section 5.4 assesses plan robustness under data distribution shifts. Finally, Section 5.5 evaluates how CARVER outperforms other synthetic workloads in training optimizers.
We compare PAR 2 QO with the following methods:
• PostgreSQL: Here, we simply rely on PostgreSQL's default behavior, invoking its optimizer separately for each query instance. While this method serves as a useful comparison point, our goal goes beyond matching the optimizer's performance -we aim to enhance plan robustness and reduce optimization time in a parametric setting. To provide a more comprehensive evaluation, Section 5.3 further introduces stronger baselines. • Kepler: Kepler [15] is a state-of-the-art PQO method that learns from real query executions to predict the fastest plan. We use RCE to obtain candidate plans, prune candidates using its default greedy algorithm with a near-latency-optimal threshold of 1.2×, and train a model for each template. • PARQO and PARQO ′ : PARQO refers to the one-robust-planper-template approach previously proposed for PARQO [46], while PARQO ′ is the extension introduced in Section 2.2 that considers caching multiple robust plans obtained from training queries. Both methods use the same error profiles and expectedpenalty-based metric for robust plan selection as PAR 2 QO. • QueryLog ′ : Following the plan population method [40], this baseline obtains its initial candidate set from optimal plans observed in the training workload, and then applies 𝜏-Cover plan reduction. At runtime, it selects the plan with the lowest recost, Cost(𝜋, ˆ︁ Sel(𝑄)). • Bao: Bao [33] is a learned query optimizer that leverages reinforcement learning to generate hints for input queries. It serves as a baseline representing general-purpose learned optimizers that are not specifically tailored for the PQO setting.
For a fair comparison, all methods use the same set of training queries. Configuration of Bao is more involved; we followed the guidelines in its tutorial [32] to obtain a reasonable setting. All configuration details are available in the full version [47]. To reduce execution noise and simulate a warm-cache environment, we execute each selected plan 5 times and report the median latency as the final result. All experiments were conducted on a Linux server with 16 Intel(R) Core(TM) i9-11900 @ 2.50GHz processors.
Table 1 (ignore the Other Variants section for now) summarizes the results on JOB. PAR 2 QO outperforms other methods in terms of average execution latency and delivers the highest improvement on CARVER, achieving a 1.96× speedup over PostgreSQL. Recall that CARVER is a "harder" workload than Uniform and Historical, because it seeks to cover the full range of possible selectivities (Section 4). Kepler shows strong speedups on Uniform and Historical, but it achieves only a 1.07× speedup on CARVER. On Historical, both Kepler and PAR 2 QO reach approximately a speedup of 1.95× over PostgreSQL, higher than other baselines. PARQO ′ , PARQO, and Bao all achieve speedups, with PARQO ′ outperforming the other two, but it still underperforms PAR 2 QO. Meanwhile, QueryLog ′ shows slight regressions below PostgreSQL across all workloads, with the largest observed on CARVER at -1.10×.
Beyond average latency, our results show that PAR 2 QO achieves a superior balance between efficiency and robustness. To quantify, Table 1 shows the number of templates exhibiting either significant speedup/regression or severe regression, defined as follows:
• Significant speedup/regression: A change in query latency exceeding 1.2×/-1.2× compared with the PostgreSQL baseline. • Severe regression: A performance degradation worse than -2×.
Significant speedup highlights a method's ability to find more efficient plans; however, equally critical is the ability to avoid significant/severe regressions. While Kepler achieves the largest number of significant speedups (even outperforming PAR 2 QO in this regard), it is fragile -it frequently encounters severe regressions that significantly degrade its overall average latency. In contrast, PAR 2 QO avoids such extreme cases and maintains stable performance. On the other hand, while other baselines also rarely exhibit severe regressions, they are too conservative -most achieve much fewer significant speedups compared with PAR 2 QO (with the exception of PARQO ′ , which gets closer to PAR 2 QO but still underperforms). Bao fares very well in avoiding both significant and severe regressions, partly because it relies on hinting rather than direct plan injection, allowing PostgreSQL to moderate its behavior; however, it also achieves far fewer significant speedups.
Table 1: Average execution latency (ms) and counts of significant speedup (↑) / regression (↓) cases, by different PQO methods and their variants, across three workloads of JOB. Latencies within 5% of the best in respective columns are highlighted.
Uniform Historical
PostgreSQL 536 ms ---410 ms ---637 ms ---PAR 2 QO 273 (1.96×) 15 3 0 254 (1.61×) 14 2 0 326 (1.95×) 15 7 0 Kepler 499 (1.07×) 19 5 4 306 (1.34×) 15 5 2 328 (1.94×) 19 2 1 PARQO ′ 305 (1.76×) 14 7 0 305 (1.34×) 13 5 0 348 (1.83×) 16 4 0 PARQO 350 (1.53×) 9 2 0 383 (1.07×) 3 2 0 433 (1.47×) 9 5 0 QueryLog ′ 587 (-1.10×) 4 6 0 428 (-1.04×) 5 4 1 668 (-1.05×) 2 7 0 Bao 443 (1.21×) 5 1 0 325 (1.26×) 6 1 0 613 (1.04×) 8 2 1 Other Variants: Uni-BestCost 658 (-1.23×) 3 10 3 426 (-1.04×) 4 9 5 725 (-1.14×) 3 9 3 BestCost 344 (1.56×) 12 3 0 355 (1.15×) 12 3 0 400 (1.59×) 12 1 0 BestCost-bound 513 (1.04×) 10 2 0 362 (1.13×) 11 3 0 591 (1.08×) 9 1 0 Nearest 401 (1.34×) 13 9 2 422 (-1.03×) 9 6 1 377 (1.69×) 15 6 1 PAR 2 QO-sim 287 (1.87×) 14 4 0 270 (1.52×) 14 1 0 330 (1.93×) 17 5 0 PAR 2 QO-no-reduce 285 (1.88×) 14 4 0 255(1.61×) 14 2 0 339 (1.88×) 13 8 1 BestCost-sim 420 (1.28×) 11 9 1 402 (1.02×) 9 2 1 446 (1.43×) 8 3 0 BestCost-no-reduce 366 (1.46×) 8 3 0 390 (1.05×) 9 3 0 444 (1.43×) 7 4 0
To further analyze the performance at template-level, we focus on PAR 2 QO and Kepler, presenting detailed execution latency and speedup results in Figure 3. For clarity and simplicity, each template is labeled with the workload's initial letter plus its ID (e.g., 𝐶2 represents template 2 in CARVER, and 𝐻 1 is template 1 in Historical). We exclude templates in Figure 3 where neither PAR 2 QO nor Kepler exhibits significant speedup or regression. Results show that, overall, Kepler can achieve markedly higher speedups in certain scenarios. For instance, on 𝐶7 and 𝐶19, it attains 5.17× and 4.03× speedups, respectively, whereas PAR 2 QO only reaches 1.96× and 1.10×. Moreover, there are templates where Kepler provides a speedup but PAR 2 QO does not, such as 𝐻 4, 𝐻 8, 𝐻 19, 𝑈 22, and 𝑈 26. However, Figure 3 also highlights that PAR 2 QO effectively mitigates severe regressions: the worst performance degradation for PAR 2 QO occurs in 𝐻 4 (-1.81×), while Kepler's largest regression, observed in 𝐶10, exceeds -5×. These findings indicate that Kepler, by learning from real executions, can sometimes identify faster plans. However, these plans lack robustness and may fail to deliver consistent performance in practice. In contrast, PAR 2 QO effectively mitigates extreme performance degradations, leading to better overall execution latency.
Besides the execution latencies of query plans, other types of overhead -notably the one-time (or periodic) per-workload model preparation cost and the runtime per-query optimization cost -are also important practical considerations. After all, PQO was initially motivated by the desire to reduce the per-query optimization cost, which increases the query latencies observed by users. This subsection examines the overhead of various methods in comparison with PostgreSQL. Additional details are available in the full version [47].
Model preparation time. By model preparation time, we mean the period from receiving the training workload to completing the model setup and being ready to generate plans for new queries. For PAR 2 QO, the first step is profiling errors using the training workload, which takes less than 13 minutes on average per query template. Then, preparing the plan-cost matrix takes about 8.5 minutes per template on average (with the default setting of 𝑛 = 50,
10 1 10 2 10 3 Latency (ms) PAR²QO Kepler Postgres C1 C2 C3 C4 C6 C7 C8 C9 C10C11C12C13C14C15C16C17C18C19C20C21C23C24C26C27C28C30C31C32 -3X = 5X Speedup (+/-) 18.1X -5.0X 23.7X Baseline (a) CARVER Workload which results in |L| = 300 and |P| = 88). Subsequent plan reduction is very fast, completing under 500ms per template. Thus, the total preparation time for PAR 2 QO averages 21.5 minutes per JOB template. In contrast, Kepler requires a large number of query executions for training, where every query incurs many executions. Overall, Kepler's preparation time is over 6.5 hours per JOB template -more than 18× slower than PAR 2 QO. As a comparison point, PARQO ′ , without PAR 2 QO's smart method of sharing computation, suffers from the high cost of finding the robust plan for each anchor independently; it takes an average of 2.4 hours per JOB template, 6.7× slower than PAR 2 QO. Both Bao and QueryLog incur lower model preparation overhead, but it comes at the cost of reduced performance.
Inference time and model size. As a baseline, PostgreSQL's optimizers adds on average 67ms optimization overhead per JOB query. In comparison, Kepler is the fastest, under 1ms per query, thanks to its model directly outputting the query plan; PAR 2 QO's runtime overhead is 26ms, still considerably faster than PostgreSQL; Bao is the slowest, with 376ms per query, because it does not have the benefit of PQO. While PAR 2 QO's inference time is longer than Kepler because it still needs to carry out robustness-based plan selection at runtime, this overhead is a good trade-off in order to secure more robust and generally more efficient plans than Kepler, as shown in Section 5.1. As another comparison point, QueryLog ′ , despite its much simpler objective requiring no robustness evaluation, has a higher overhead (35.4ms) than PAR 2 QO, because merely recosting plan candidates adds considerable cost. This observation further demonstrates the effectiveness of computation caching in PAR 2 QO. Finally, all methods have practically acceptable model sizes: PAR 2 QO has a 0.2MB error model plus a 1.8MB cache (2.6MB before plan reduction), totaling no more than 2.1MB at runtime; Kepler and Bao's models use very compact neural networks, which take less than 1MB space at runtime.
To gain deeper insights, we design a series of experiments to evaluate the impact of various components and parameter settings in PAR 2 QO. Because of space constraints, we discuss only a subset of the results below and show an even smaller subset in Table 1, under the Other Variants section. Other results can be found in [47].
Impact of sample locations. First, we examine how PQO performance is affected by the locations from which we obtain candidate plans. To this end, we create a new variant called Uni-BestCost, which probes for its candidate plans using the same number of locations as PAR 2 QO, and similarly uses 𝜏-Cover to reduce this set. However, instead of PAR 2 QO's workload-and error-aware sampling-by-cluster strategy, Uni-BestCost samples locations uniformly at random within a hyperrectangle bounding all selectivities observed during training. Finally, when selecting plans at runtime, instead of optimizing for penalty-based robustness like PAR 2 QO, Uni-BestCost picks the candidate plan whose cost is the lowest given the estimated selectivities, just like QueryLog ′ . To isolate the effect of candidate plans for comparison, we create a second variant called BestCost, which is identical to Uni-BestCost except that it uses the same reduced set of candidate plans as PAR 2 QO.
Results for Uni-BestCost in Table 1 show that using more uniform samples from the observed selectivity range is not effective -not only does it perform far worse than PAR 2 QO, but it also underperforms QueryLog ′ despite examining more locations. On the other hand, BestCost performs significantly better and reverses Uni-BestCost's slowdown: for CARVER, the -1.23× slowdown improves to a 1.56× speedup, surpassing Kepler's 1.07×; for Uniform and Historical, while BestCost remains behind Kepler, it now achieves speedups over the PostgreSQL baseline. The dramatic improvement from Uni-BestCost to BestCost highlights the effectiveness of PAR 2 QO's sampling strategy in Section 3.1.
Impact of # of probe locations per cluster. We further examine the impact of 𝑛, the number of probe locations per sampling cluster, which influences |L|, the total number of sample locations. A larger 𝑛 can improve plan quality, but also increases training and inference costs. When increasing 𝑛 from 50 to 200, we observe improvements in some specific templates -for instance, 𝐻 4, which showed the largest regression in Figure 3, improves from a -1.90× regression to a 1.41× speedup. However, the overall performance across workloads remains largely unchanged, indicating that a larger 𝑛 provides diminishing returns in most cases. Since 𝑛 influences |L| directly and |P| indirectly, it can, in the worst case, blow up overhead quadratically. In practice, increases in overhead are milder but still significant: 3.3× training time and 2.1× inference time compared with 𝑛 = 50. On the other hand, when decreasing 𝑛 from 50 to 10, we observe a clear degradation in plan quality, but even in this case, PAR 2 QO (𝑛 = 10) is still better than Kepler for CARVER and comparable for Uniform and Historical, and consistently beats PostgreSQL, Bao, and PARQO. Further details are available in [47]. Overall, we find the setting of 𝑛 = 50 to be a good default, although smarter sampling strategies that increases 𝑛 adaptively on a per-template basis might be a fruitful future direction.
Impact of runtime plan selection criteria. Next, we study the impact of plan selection criteria on PQO performance. Note that the BestCost variant considered above differs from PAR 2 QO only in how it selects a plan at runtime. Since BestCost significantly underperforms PAR 2 QO as shown in Table 1, we can conclude that PAR 2 QO's penalty-based robustness objective is far superior to simply picking the plan with the lowest cost at estimated selectivities s ˆ. Here, for further comparison, we create two additional variants that consider alternative plan selection criteria used in previous work. First, BestCost-bound extends BestCost by incorporating a safety check, similar to the "cost check" in SRC [17]: it checks whether the cost of a candidate plan 𝜋 at s ˆremains within a bound (1 + 𝜆) of the cost of 𝜋 at the location where 𝜋 was optimized (we set 𝜆 = 2, as suggested by SRC [17]); if not, the system falls back to invoking the optimizer. Second, Nearest picks the candidate plan whose location in the selectivity space is closest to s ˆin ℓ 2 distance, following the idea of "selectivity check" in SRC [17].
From Table 1, we observe that applying the (1 + 𝜆) safety check degrades BestCost's performance, indicating that the fallback mechanism does not guarantee a plan with truly optimal execution performance. The root cause is that the estimated selectivities s ˆfor the given query may be wrong to begin with; using s ˆfor the safety check and falling back to the optimal plan at s ˆmay not be safe in reality. From Table 1, we also see that Nearest fares no better than BestCost and remains far behind PAR 2 QO. To conclude, with proper accounting for uncertainty in s ˆin its plan selection strategy, PAR 2 QO has a clear performance advantage over approaches that ignore uncertainty and/or are heuristic in nature.
Impact of plan reduction. By default, PAR 2 QO employs 𝜏-Cover for plan reduction. Recall that PAR 2 QO sets the upper bound on the number of plans (after reduction) to be max(0.2 • |P|, 10). For JOB, the average number of candidate plans obtained per template via sampling, |P|, is 88. We found that, on average, 9 candidate plans per template were sufficient to 𝜏-cover all candidates, justifying our choice of the default upper bound. In the end, PAR 2 QO kept on average 8 candidate plans per template. A smarter, template-specific selection of this upper bound and a theoretical justification of what is needed for complete coverage are interesting future directions.
To evaluate other options, we create two variants: PAR 2 QOsim, which reduces the candidate plan set by cost profile similarity (Section 3.3), and PAR 2 QO-no-reduce, which does not reduce the set at all. Results, shown in Table 1, indicate that both PAR 2 QO-sim and PAR 2 QO-no-reduce offer comparable performance as PAR 2 QO overall. In other words, effective plan reduction, which reduces runtime overhead, does not sacrifice plan performance. In fact, despite plan reduction, PAR 2 QO is able to slightly but consistently outperform PAR 2 QO-no-reduce, indicating that 𝜏-Cover may also help improve robustness -a point that we examine further below. A closer look at the resulting plans under both reduction methods is provided in the full version [47].
We also extend this ablation study to BestCost, which employs 𝜏-Cover for plan reduction but does not consider robustness explicitly when picking plans at runtime. We call the corresponding variants BestCost-sim and BestCost-no-reduce. Interestingly, from Table 1, we see that BestCost, with 𝜏-Cover plan reduction, noticeably outperforms BestCost-no-reduce, with no reduction. This improvement, more significant than that of PAR 2 QO over PAR 2 QOno-reduce, confirms the benefit of 𝜏-Cover in improving robustness, especially in the setting of BestCost where runtime plan selection is not robustness-based. In contrast, BestCost-sim does not offer such a benefit because its reduction method favors preserving plan diversity over robustness.
Previous experiments were conducted on a static database state. However, true robustness requires plans to maintain good performance even when data and their distributions evolve. In this experiment, we simulate real-world scenarios with shifting data distributions, which can introduce unforeseen variations in selectivity errors and plan performance.
We create multiple database instances from the original IMDB dataset using three "slicing" methods to get varying degrees of data distribution shifts. First, category-slicing [46] splits data by item categories (kind_type.kind), which produces the most dramatic distribution shifts. 2 Second, time-slicing [46] applies a 20% sliding window on production_year, generating 9 instances. Adjacent instances share overlapping data, while distant ones exhibit larger differences, producing smooth transitions and gradual shifts. Third, random-slicing randomly samples 20% of title along with associated data from other tables; it largely maintains the overall data distribution, representing the least challenging scenario.
For each dataset-slicing method, we synthesize three workloads (CARVER, Uniform, and Historical) by the same procedures in Section 5.1. PAR 2 QO and Kepler select plans based on one instance alone (called the "base" instance), which are then evaluated on the remaining instances. Note that PAR 2 QO's error model E is also 2 Table sizes can vary up to 51× (e.g. title in "Movie" vs. "Video game"), and template execution times may fluctuate up to 176× (e.g. C17 on "Movie" vs. "Video game"). The detailed selection criteria are described in the full version [47], along with additional experimental results. In summary, we find PAR 2 QO plans to be more robust than Kepler's across different data drift scenarios. For example, even under the most challenging category-slicing, the largest regression experienced by PAR 2 QO on non-base instances is no more than -2×. Interestingly, while we do not expect to beat PostgreSQL's plans (which have access to correct statistics on these instances), PAR 2 QO in fact performs better than PostgreSQL in quite a few cases, demonstrating that robust plans can offer protection against selectivity errors regardless of their causes. In contrast, Kepler suffers severe regression in some cases, with slowdowns of up to -6× compared to the baseline.
We design the following experiment to see how different learned methods perform when presented with unforeseen query workloads, and to evaluate how effective CARVER is as a training workload (in comparison with Uniform and Historical). First, we train each method exclusively on each one of these workloads; then, we test the method on a mixed workload, which samples queries with equal probability from all three workloads. This mixed testing workload simulates a setting where the testing queries are drawn from a distribution from the training one, which commonly arise in practice. We want to evaluate how PAR 2 QO, Kepler, and Bao perform this setting, and determine which training workload generally leads to models with best performance. The results are shown in Table 2. First, we see that PAR 2 QO adapts to the unforeseen testing workload much better than Kepler and Bao, regardless of the training workload used. PAR 2 QO still outperforms the PostgreSQL baseline significantly: 1.75× when trained with CARVER and ≥ 1.35× otherwise. On the other hand, Kepler and Bao experience overall slowdown, with far more templates experiencing significant regression. When trained using Historical, Kepler's -1.65× slowdown -a stark reversal of its 1.94× speedup in Table 1 -can be explained by the fact that Historical queries have less diverse parameter values, which makes it harder for Kepler's model to generalize. We also provide detailed template-level performance in Figure 4. 3 Similar to Figure 3, while Kepler achieves strong performance on some templates (e.g., 𝐶19 and 𝐶30), it also suffers severe degradation in others (e.g., 𝐻 3-4, 𝐻 23, and 𝐶31). In contrast, PAR 2 QO again avoids such extreme regressions effectively, even over this unforeseen query workload. Second, training using CARVER generally gives better performance than training using Uniform or Historical, regardless of the learned method tested. For PAR 2 QO and Bao, the advantages are clear (>25% and >11%, respectively). For Kepler, while CARVER's advantage over Historical is clear, its advantage over Uniform is more subtle but still evident from the fewer number of significant/severe regressions. Overall, these experiments confirm the superiority of CARVER over others for training learned optimizers.
Parametric Query Optimization. PQO has been extensively studied over the years [23,24]. The primary focus of traditional PQO methods is minimizing the optimizer's invocation through plan caching and reuse strategies, ensuring the plan's cost remains acceptable while avoiding unnecessary re-optimization [2,7,17]. Different approaches have been explored to address this challenge, including caching only one plan with the lowest expected cost for the entire selectivity space [1,7,8], caching a set of plans [17,20,25], or progressively caching multiple plans over time [2,6,26]. Some works propose to build density maps through query clustering to better capture selectivity variations [2,20], or building a "plan diagram" as a color-code visualization [13,37] to provide a structured view of the selectivity space and how different plans dominate various regions. For a more comprehensive review of traditional PQO techniques, we direct readers to [12]. Recent work, SCR [17] applies an online selectivity and cost check to evaluate if a cached plan can be reused guaranteeing the bound on cost suboptimality, and if a new plan needs to be added into the cache. Most recent efforts, including QueryLog [40] and Kepler [15], extend PQO by incorporating execution performance optimization and learning from query executions. QueryLog formalizes PQO problem as a two-step decision process, generating candidate plans and selecting the most suitable one. Kepler and PAR 2 QO adhere to this structure.
Since Kepler and QueryLog have been thoroughly discussed and compared with PAR 2 QO in Section 3.4, we omit further details here.
Robust query optimization. Traditional query optimizers often select plans that perform poorly in practice, with cardinality estimation errors being a primary cause of such degradations [27,28]. RQO aims to select robust plans that remain stable despite inaccuracies in cardinality estimates [31,49]. To quantify these uncertainties and guide robust plan selection, prior research assumes cardinality as a probability density function [4,9], a uniform distribution over the entire space [1], or within a bounding box [5,19]. More recent work has developed advanced plan selection techniques: Some approaches consider worst-case sub-optimality [16,36,41], define robustness metrics based on cost slope and integral [44], or compute optimality or near-optimality ranges as robustness indicators [14,45]. More recent work selects plans based on learned execution time distribution [30], and prioritizes plans using expected penalty [46]. Another line of research explores adaptive processing, where runtime observations guide dynamic plan switching to avoid poor plan executions [16,18,39,42,44]. For a comprehensive overview of techniques in robust query processing, we refer readers to this survey [22]. Previous work [10, 13-15, 37, 38, 40, 45] implicitly considers robustness when pruning plans, while PAR 2 QO takes a step further by directly integrating plan robustness into PQO.
Selecting a PQO method in practice involves a trade-off. Kepler can sometimes find the fastest plans with low inference latency but requires expensive model training and is prone to severe regressions. QueryLog is easy to set up but may fail to improve execution performance beyond the optimizer. By integrating penalty-aware robustness into PQO, PAR 2 QO achieves a better balance between efficiency, stability, and practicality. Future work includes further expanding the search space of robust plans; sharing computation across templates; and adapting the error model/cache dynamically for evolving database states and workloads.
The general procedure needs to handle subtleties that arise because of OR and NOT, which we omit here.
Templates 14, 20, and 29 are excluded in Figure
4, as both PAR 2 QO and Kepler's results show no significant speedup/regression beyond 1.2×.