betaFeedback

WorksComputer Science

SWatcher+: A Holistic Approach to Deploying Learned Cardinality Estimators in a Dynamic Setting

Abstract

Cardinality estimation (CE) is crucial in database query optimization. Although recent advances have improved accuracy, deploying machine-learned CE models in dynamic databases remains challenging due to data updates and workload shifts. Retraining can be costly, but existing practices offer little guidance on when and how to update models, resulting in simple periodic retaining strategies that are suboptimal. We propose SWatcher+, a framework that adapts learned CE to dynamic workloads by monitoring data updates and query feedback. SWatcher+ selectively monitors high-impact subqueries for which wrong estimates lead to poor plan performance, and it proactively applies corrections to estimates during query optimization. This strategy enables immediate adaption to data and workload shifts without waiting for full model retraining, and carefully balances the cost and benefit of monitoring and adaption versus retraining. Our experiments show that SWatcher+ offers a better trade-off between query performance and overhead compared with existing approaches, making it a more practical solution for deploying learned CE in dynamic settings.

ACM Reference Format:

Yuxi Liu, Vincent Capol, Xiao Hu, Pankaj K. Agarwal, and Jun Yang. 2018. SWatcher+: A Holistic Approach to Deploying Learned Cardinality Estimators in a Dynamic Setting. In Proceedings of Make sure to enter the correct conference title from your rights confirmation email (Conference acronym ’XX). ACM, New York, NY, USA, 15 pages. https://doi.org/XXXXXXX.XXXXXXX

Introduction

Most database query optimizers rely heavily on cardinality estimation (CE) to generate query plans. Recent advances in learned CE [9, 28, 29, 30, 35, 36, 37, 41, 42, 54, 56], where a machine learning model is trained on the database instance and/or query execution feedback, show promise in improving CE accuracy. However, deploying learned CE remains challenging, because dynamic database changes can render models inadequate. Since fine-grained incremental model updates can be expensive, most learned models try to stay up to date by retraining or, if applicable, fine-tuning (e.g., for deep learning [48, 56]). When to schedule costly refreshes, however, is unclear. A popular approach is periodic refresh [6, 23, 24, 27, 56]. The periodic can be defined in terms of time or the number of data updates since the last refresh, but guidance on how to set such periods is often lacking. There is a need to develop a smarter framework for deploying learned CE in a dynamic setting.

This paper explores several ideas to address this challenge. The first idea is monitoring. We would like to monitor both data updates and query feedback for clues to refresh the model. Ignoring data updates makes us too reactive—we will miss cases when data has changed significantly but not enough queries have witnessed the effect. On the other hand, ignoring the query workload may cause unnecessary refreshes—often, parts of the database are rarely queried, so refreshing the model in response to changes to these parts will not improve query performance. The second idea is estimation correction. Instead of using information collected from data updates and query feedback to refresh the CE model, which can be costly, we can use it to correct estimates by an outdated model. This idea has been tried by LEO [45] years before the advent of modern learned CE models: LEO remembers any estimation errors in excess of 5% and uses them to correct future estimates. There is no need to wait until the next refresh to benefit from the corrections.

However, combining these ideas into an effective solution that delivers practical, end-to-end gains is not trivial. We approach the problem of deploying learned CE in a dynamic setting holistically. Instead of focusing narrowly on improving CE accuracy, we look at the ultimate impact of model estimates on query performance, as well as the overall operational cost, including the overhead of monitoring, refresh, and correction. First, monitoring incurs overhead, but its benefit is not always clear. Many CE errors may not actually impact plan quality [20]. Second, correcting CE errors for some subqueries (e.g., only single-table selections) may sometimes lead to worse plans. This counterintuitive effect has been noted in [20] and confirmed in our experiments. Finally, retraining the CE model does not guarantee more accurate estimates where accuracy actually matters. Overall, deploying learned CE in a dynamic setting requires a delicate balancing act between benefit and cost.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Conference acronym ’XX, Woodstock, NY

© 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/XXXXXXX.XXXXXXX Contributions. Going beyond the basic ideas of monitoring and correction, we propose SWatcher+. “+” represents the idea of increasing the benefit of monitoring by using monitored information proactively, to correct model estimates during optimization, without waiting for model refresh. “S” in SWatcher+ is the idea of making monitoring and correction selective based on their benefit, to reduce overhead. We only monitor the cardinalities of subqueries for which correction is expected to tangibly affect plan performance.

Importantly, noting that correcting selection cardinalities alone may have little (or even negative) impact, we also monitor information about joins. We show that while exact single-table selection cardinalities can be maintained efficiently, maintaining exact cardinalities of join subqueries is not cost-effective. Instead, we only cache recent compensating correction factors for join subqueries. Though less accurate, such information is cheaply available even for joins involving more than two tables, and it helps avoid the pitfall of applying only selection corrections.

Lastly, SWatcher+ triggers a model refresh by detecting when it is watching too many “correction-worthy” cardinalities, rather than detecting a high aggregate CE error. This policy allows SWatcher+ to cap data update processing time and realize when the model is making too many consequential mistakes.

SWatcher+ is also designed to be generally applicable, without being tied to any particular learned CE model or database system. We have experimented with using to SWatcher+ to deploy three different CE models—MSCN [18], JGMP [41], and Naru [56]—with PostgreSQL, and holistically compared its benefits and costs against competing deployment strategies. The results demonstrate that SWatcher+, with a fixed configuration and minimal parameter tuning, delivers superior end-to-end performance.

  • Comparing SWatcher+ with the popular practice of periodic refresh, with MSCN as the model, SWatcher+ achieves 44.3–101.4% of the end-to-end running time of periodic refresh, outperforming it in 14 out of the 16 query templates, even when the refresh period is configured optimally post hoc. With JGMP and Naru, SWatcher+ achieves 56.1–99.5% and 87.84–98.84% (resp.) of periodic refresh’s end-to-end running time, beating it consistently.

  • SWatcher+’s selective monitoring and correction strategy readily beats simpler monitoring and correction strategies, including our best-effort implementation of LEO’s strategy [45].

  • SWatcher+’s method of maintaining compensating correction factors for join subqueries instead of exact cardinalities is effective in taming the overhead while delivering query performance gains, even for complex queries involving multi-table joins.

  • SWatcher+ naturally adapts its behavior to the workload: for complex OLAP-style queries, it monitors and corrects more for bigger improvements in query performance; for simple OLTP-style queries with little room for improvement, it automatically scales back on monitoring and correction to avoid overhead.

Framework and Preliminaries

Before presenting SWatcher+, we first describe a general framework, called WATCHER, for deploying learned CE models in database systems in a dynamic setting; we describe a basic monitoring strategy (§ 3) and SWatcher+ (§ 4) within this framework.

Learned CE Model. WATCHER assumes access to a learned model that can be refreshed to predict the cardinalities of subqueries. Model refresh in general can use query feedback—namely, queries and their true cardinalities observed during execution—as well as the current database state if needed. Our default approach targets models whose refresh takes considerable time, but we have also evaluated how it compares with, and complements, models that support incremental updates.

Importantly, WATCHER makes no assumption about how m works internally. Our goal is not making any specific model better by modifying it; instead, we seek to deploy a given model in the smartest way possible while working around its limitations. Therefore, our approach is orthogonal to and complements research in improving models themselves to be more robust in dynamic settings, e.g., [36, 49, 50].

Access to Data and Queries. WATCHER assumes access to the data update stream (e.g., by monitoring the database log [7]). The framework is notified of each update and can read its content for processing. We can also query the database for additional information as needed. WATCHER also assumes access to the stream of queries against the database. Additionally, it is possible to inspect a query plan π\pi (for query QQ) and its execution to obtain the cardinality of the result set produced by each of its subplans. With PostgreSQL, for example, such information is available with the EXPLAIN ANALYZE command. However, since there are many options for π\pi, WATCHER does not, in general, assume that the cardinality of every possible subquery qq of QQ is observable from the execution of π\pi, since π\pi may not contain a subplan that corresponds to qq. Hence, it may issue additional queries to the database to acquire subquery cardinalities; more details are in later sections.

Interfacing with Query Optimizer. WATCHER assumes the model m to be external to (as opposed to integrated into) the database query optimizer, a setup typical in learned CE research. It can make a call Opt⁡(Q,κ)\operatorname{Opt}(Q,\kappa) to the optimizer to optimize a query QQ using a set κ={(q1,card⁡^(q1)),…,(qk,card⁡^(qk))}\kappa=\{(q_1,\widehat{\operatorname{card}}(q_1)),\ldots,(q_k,\widehat{\operatorname{card}}(q_k))\} of cardinality estimates card⁡^(qi)\widehat{\operatorname{card}}(q_i) of some subqueries qiq_i, 1≤i≤k1\leq i\leq k, of QQ. As is commonly done in literature [8, 20, 25, 52], instead of specifying CE for all possible subqueries, which would be too costly, κ\kappa overrides CE only for a “relevant” subset of subqueries, while leaving the estimation of others to the database optimizer (which may depend on those specified in κ\kappa). Furthermore, after obtaining a plan π\pi, WATCHER asks the database system to execute the query QQ using it. Finally, SWatcher+ additionally assumes it can make a call Cost⁡(π,κ)\operatorname{Cost}(\pi,\kappa) to the optimizer to estimate the cost of π\pi given a set κ\kappa of relevant cardinality estimates, without executing π\pi. For our PostgreSQL-based implementation, we use the same mechanism in [8, 52] for cardinality injection, and pg_hint_plan [33] for specifying the plan to execute (EXPLAIN ANALYZE) and cost (EXPLAIN).

Architecture and Overview. Figure 1 depicts the system architecture of WATCHER. The framework acts as an intermediary between the CE model and the underlying database system. Basically, it maintains a carefully selected watchset WW consisting of subqueries from the workload whose cardinalities are maintained up-to-date with respect to the current database state. This practice is analogous to incrementally maintaining data summaries such as histograms in databases, but as discussed in later sections, we are much more careful in selecting what to maintain, based on both the query workload and which estimation errors actually matter for query performance. It may also maintain additional information that is updated upon data updates and/or query feedback for query optimization and triggering model refreshes. Watcher’s behavior is characterized by the following three aspects:

Figure 1. System architecture for the Watcher framework that interfaces with both the learned CE model and the database system.

  • Processing each data update. The data updates are used to incrementally update the cardinalities of WW to keep them up-to-date.

  • Processing each query. Watcher intercepts each incoming query and, using the information it maintains, optionally corrects cardinality estimates that would otherwise be returned directly by the CE model. Moreover, it obtains query execution feedback (including observed true cardinalities) from the database system. It may update the watchset WW, i.e., insert some subqueries into WW or evict some from WW. It may also request additional information from the database system to update its internal state.

  • Triggering and preparing for model refresh. Using information maintained in its internal state, Watcher decides when to refresh the CE model. It leverages information already present in its internal state, and it may additionally query the database, to prepare training data for model refreshes.

We first describe a basic approach implementing the Watcher framework, called Watcher1D, using the idea of monitoring alone (Section 3). Then, we describe our main approach, called SWatcher+ that maintains a more carefully selected and significantly smaller watchset and also maintains a coarse approximation of “correction factors” for join subqueries, thereby achieving a much better cost-benefit balance (Section 4).

Basic Monitoring

This section describes Watcher1D, a basic implementation of our framework. It maintains as its watchset WW a reservoir sample of single-table selection subqueries from the query workload. For instance, suppose we observe SQL 1 below from the query workload:

SQL 1: a query of TJQ013a used in Section 5

SELECT * FROM store_sales, store, customer_demographics,
household_demographics, customer_address, date_dim
WHERE s_store_sk = ss_store_sk
  AND ss_sold_date_sk = d_date_sk AND ss_hdemo_sk = hd_demo_sk
  AND cd_demo_sk = ss_cdemo_sk AND ss_addr_sk = ca_address_sk
  AND ss_sales_price BETWEEN 32.78 AND 207.53
  AND hd_dep_count BETWEEN 1 AND 4;

WW may include subqueries σ32.78≤ss_sales_price≤207.53store_sales\sigma_{32.78\leq ss\_sales\_price\leq207.53}\mathrm{store\_sales}, and σ1≤hd_dep_count≤4household_demographics\sigma_{1\leq hd\_dep\_count\leq4}\mathrm{household\_demographics}.

For each q∈Wq \in W, Watcher1D tracks card⁡(q)\operatorname{card}(q), the cardinality of qq estimated by the CE model mm, and card⁡(q)\operatorname{card}(q), the true cardinality of qq. We also index the subqueries in WW by the tables they reference such that, for any table RR, we can quickly retrieve WR⊆WW_R \subseteq W, the subset of subqueries corresponding to RR.

Given the data update stream, Watcher1D tracks the true cardinalities of watchset queries, and uses them to assess model accuracy and support model refresh. It monitors an aggregate error measure over WW and uses it to trigger model retraining; the training data comes conveniently from WW, which already tracks true cardinalities. However, our experiments show that even with careful data structure design and implementation, the maintenance overhead can easily outweigh their potential benefit. This limitation then motivates selective monitoring and correction used by SWatcher+ in Section 4. Now we describe these steps in more detail:

Processing Queries. For each query QQ, we identify the set of single-table selection subqueries {q}\{q\} as candidate watchset queries. Whether each candidate qq is admitted to the watchset WW follows the standard reservoir sampling procedure. A previously watched query may be evicted to keep the size of WW at nwatchn_{\mathrm{watch}}.

We call the optimizer with the relevant cardinalities κ^\hat{\kappa} estimated by mm to obtain plan π=Opt⁡(Q,κ^)\pi= \operatorname{Opt}(Q,\hat{\kappa}). We record the estimated cardinality of each candidate watchset query qq as card⁡(q)\operatorname{card}(q). After executing π\pi, we record the observed true cardinality of each qq as card⁡(q)\operatorname{card}(q). Such information, when available, can be parsed from the output of EXPLAIN ANALYZE. Sometimes, the chosen π\pi may not execute qq as an independent subquery.1 In such cases, we execute a countering query over σRQ\sigma_R Q to obtain card⁡(q)\operatorname{card}(q). These additional queries are counted towards the overhead of the approach.

Processing Data Updates. To process each data update concerning a row rr in table RR, for each query q=σpRq = \sigma_p R in WRW_R, we test its selection condition pp on rr. If rr passes pp, we increment card⁡(q)\operatorname{card}(q) if rr is being inserted, or decrement card⁡(q)\operatorname{card}(q) if rr is being deleted. This processing ensures that card⁡(⋅)\operatorname{card}(\cdot) is kept up to date for watchset queries. This linear-time approach has low overhead because of its simple implementation, which works well in practice since WRW_R is usually not large. If WRW_R is large, more sophisticated data structures can achieve logarithmic query and update costs; see [2] for details.

Retraining CE Model. To decide when to trigger retraining of the CE model mm, we check an aggregate error measure, described further below, after processing each data update and query, because both factors can affect model performance. If either data distribution or query distribution is known to be stable, we may decrease the frequency of checks for data updates and queries accordingly.

For the aggregate error measure, we use the 90-th percentile of Q-error [31], computed from card⁡(⋅)\operatorname{card}(\cdot) and card⁡^(⋅)\widehat{\operatorname{card}}(\cdot) over ntestn_{\mathrm{test}} queries sampled from WW. Unlike average or root-mean-square error, this quantile-based error is less sensitive to a handful of outliers. Such outliers arise often in predictions of learned CE models, but they may not indicate overall model inadequacy; a quantile-based error threshold avoids unnecessary retraining caused by these outliers.

When the aggregate error exceeds a prescribed threshold ϵ\epsilon, we trigger retraining of the CE model m\mathfrak{m}. The training dataset is constructed by sampling ntrainn_{\mathrm{train}} watchset queries out of W\mathcal{W}. Since we track their up-to-date cardinalities, we do not need to rerun these queries to acquire the training data, which significantly reduces the end-to-end latency of retraining. Finally, retraining does not guarantee that the aggregate error will fall below ϵ\epsilon. Whenever retraining fails to reach the target, we apply an exponential backoff on ϵ\epsilon, i.e., setting a new target ϵ\epsilon for the next retraining by multiplying ϵ\epsilon by a factor of 1.5. If the post-training error eventually falls back to a lower previous level, the previous level can be restored.

Analysis. By monitoring true cardinalities of queries sampled from the workload, Watcher1D allows retraining decisions to be informed jointly by data and query distributions, in contrast to methods [23, 24, 36] that rely on less reliable heuristics. Also, Watcher1D provides up-to-date training data at no additional cost, in contrast to methods that must run additional queries for retraining [23, 49].

The cost of Watcher1D has three components. First, for each update on table RR, updating the true cardinalities for the subset WR\mathcal{W}_R of the watchset takes O(∣WR∣)O(|\mathcal{W}_R|) time (or O(log⁡∣WR∣)O(\log|\mathcal{W}_R|) with an advanced data structure). Second, for each query QQ, beyond the inference cost for κ^\hat{\kappa}, true cardinalities are typically obtained for free from the execution; otherwise, they are collected via additional single-table counting queries (such cases are rare in practice and incur negligible overhead, as shown in experiments in the full version [2]). Third, retraining incurs a cost; computing and checking the aggregate error measure has negligible cost, and as discussed, generating the training dataset requires no extra query cost.

However, as we will see from experiments in § 5, the query execution time savings in practice cannot justify the high overhead of maintaining W\mathcal{W} for Watcher1D. For example, for a setup with query/update rate of 1/100 and nwatch=1500n_{\mathrm{watch}} = 1500, 62.7% of Watcher1D’s overhead goes to processing data updates; 4.3% goes to processing queries (entirely due to CE model inference); the remaining 33.0% goes to retraining. Overall, Watcher1D incurs 116 seconds of additional overhead, only to reduce plan execution time by 66 seconds compared with a baseline with no retraining.

We trace this unfavorable trade-off to two limitations. First, Watcher1D uses monitored information only to trigger and support model refresh, a severe underutilization of an expensive resource. We should derive higher, more immediate utility from actively maintained true cardinalities instead of waiting until model refresh. Second, Watcher1D focuses only on CE errors for single-table selection subqueries, even though CE errors for join subqueries are often more critical [20, 21, 52]. At the same time, maintaining true cardinalities for join subqueries is even costlier than for selection subqueries (as shown by experiments on Watcher2D, an extension of Watcher1D, in § 5.3). Therefore, we need a more cost-effective approach for join CE than incremental maintenance. We next present SWatcher+ to address these limitations.

SWatcher+

We now describe SWatcher+, our main algorithm. As discussed in § 1, the “S” in SWatcher+ stands for the idea of selectively monitoring only selection subqueries for which CE errors indeed affect plan quality; the “+” in SWatcher+ stands for the idea of proactively incorporating monitored information during query optimization, instead of waiting for model refresh. To avoid the pitfall of correcting selection CE errors alone (an observation confirmed in Section 5.1.2), we cache compensating correction factors for joins (instead of maintaining true join cardinalities) and apply them together with selection cardinality corrections.

SWatcher+ maintains the following two main data structures:

  • Watchset W\mathcal{W}. Like Watcher1D, W\mathcal{W} is a subset of single-table selection subqueries observed in the query workload. However, instead of maintaining W\mathcal{W} as a reservoir sample and uses it in model refresh, SWatcher+ admits/evicts queries to/from W\mathcal{W} based on their benefit to query plan efficiency, and proactively corrects the model m\mathfrak{m}’s estimates with the true cardinalities in W\mathcal{W}.

  • Cache F\mathcal{F} of compensating correction factors. The entries are indexed by the signature of an executed query plan π\pi from which such factors were observed. More precisely, the signature has the form (J,C)(J,C), where JJ denotes the set of tables joined by π\pi and, as needed, the join predicate (when workload contains queries joining the same tables using different join conditions); CC denotes the (non-empty) set of single-table selection subqueries in W\mathcal{W} whose monitored true cardinalities were used for correction when π\pi was obtained. Given a signature (J,C)(J,C), F\mathcal{F} stores a mapping FJ,C\mathcal{F}_{J,C} from each join subplan over tables J′⊆JJ' \subseteq J to a compensating correction factor denoted FJ,C(J′)\mathcal{F}_{J,C}(J'). Multiplying FJ,C(J′)\mathcal{F}_{J,C}(J') with the CE (after correcting CC) of that subplan would yield its observed result cardinality. F\mathcal{F} also records some basic information about the entry, namely the timestamp when it is cached, the query that created it, and that query’s execution/planning times.

Overview of SWatcher+ by three aspects. 1) To process a data update, SWatcher+ follows the same procedure as that of Watcher1D in Section 3.2. The query processing aspect is more elaborate than that of Watcher1D. In the pre-execution stage, SWatcher+ consults W\mathcal{W} and F\mathcal{F} to correct any model estimates for query optimization, without waiting until refresh. In the post-execution stage, based on execution feedback, SWatcher+ updates information in W\mathcal{W} and F\mathcal{F} if applicable, and then decides whether to admit/evict subqueries to/from W\mathcal{W}, potentially with additional analysis overhead. We detail the steps in § 4.1. 3) As for model refresh, SWatcher+ decides its timing based on the number of watchset queries — a large number indicates that many CE errors are impacting query performance, so refresh may be beneficial. Details are in § 4.2. Finally, § 4.3 concludes with cost analysis and discussion. Table 1 lists the parameters used by SWatcher+ discussed below.

StageUsage
θsim\theta_{\mathrm{sim}}Correction — Minimum similarity score for two approximately matching single-table selection conditions
θExec\theta_{\mathrm{Exec}}Admission — Minimum execution time for monitoring a QQ
θOpt\theta_{\mathrm{Opt}}Admission — Minimum optimization time for monitoring a QQ
θgain\theta_{\mathrm{gain}}Admission — Minimum estimated speed up of plan cost for monitoring a QQ
θnwatch\theta_{\mathrm{nwatch}}Refresh — Maximum tolerated ∣W∣|W| before refresh

Table 1. SWatcher+’s threshold parameters.

Processing Queries

Pre-Execution. Upon receiving a query QQ, SWatcher+ first uses the CE model m\mathfrak{m} to obtain the cardinality estimates κ^\hat{\kappa}. SWatcher+ then corrects κ^\hat{\kappa} using W\mathcal{W} and F\mathcal{F} as follows. First, for each single-table selection subquery q=σpRq = \sigma_{p}R of QQ, SWatcher+ searches for a watchset query σp′R\sigma_{p'}R in WR\mathcal{W}_R whose p′p' matches pp either exactly or approximately. We say that two conditions pp and p′p' approximately match if their Jaccard similarity [15], denoted by sim⁡(p,p′)\operatorname{sim}(p,p') (computed under practical assumptions), is no less than a prescribed threshold θsim\theta_{\mathrm{sim}}. For example, consider range conditions p=[l,u)p = [l,u) and p′=[l′,u′)p' = [l',u') on the same column. If pp and p′p' overlap, we compute sim⁡(p,p′)\operatorname{sim}(p,p') as min⁡(u,u′)−max⁡(l,l′)max⁡(u,u′)−min⁡(l,l′)\frac{\min(u,u')-\max(l,l')}{\max(u,u')-\min(l,l')}, or 0 otherwise. If multiple watchset queries have conditions that approximately match pp, SWatcher+ selects the query q~\tilde{q} with condition p~\tilde{p} that achieves the highest similarity with pp. It then heuristically corrects2 the model estimate card⁡^(q)\widehat{\operatorname{card}}(q) as card⁡(p∧¬p~)+sim⁡(p∧p~,p~)⋅card⁡(q~)\operatorname{card}(p \land\neg\tilde{p})+\operatorname{sim}(p \land\tilde{p},\tilde{p})\cdot\operatorname{card}(\tilde{q}). Intuitively, the first term estimates the cardinality of the portion of pp outside p~\tilde{p}, while the second term scales the true cardinality of p~\tilde{p} down to its intersection with pp. When pp and p~\tilde{p} match exactly (sim⁡(p,p~)=1\operatorname{sim}(p,\tilde{p})=1), the correction reduces to replacing card⁡^(q)\widehat{\operatorname{card}}(q) with card⁡(q~)\operatorname{card}(\tilde{q}).

Example 4.1. As shown in Figure 2, Q2Q_2 arrives after Q1Q_1 in the stream of queries and updates. Suppose that Q1Q_1’s single-selection subquery q1q_1 is admitted to W\mathcal{W} and not evicted yet. If q1q_1’s condition is the most similar to q2q_2’s — with similarity 259.94−141.06266.16−129.7=87.12%\frac{259.94-141.06}{266.16-129.7}=87.12\% exceeding the threshold θsim=80%\theta_{\mathrm{sim}}=80\% — then card⁡(q1)\operatorname{card}(q_1) is used to correct card⁡^(q2)\widehat{\operatorname{card}}(q_2) and κ^[ss]\hat{\kappa}[\mathrm{ss}]. The corrected CE is entered into κ~[ss]\tilde{\kappa}[\mathrm{ss}].

SWatcher+: example of corrections to both single-table selection and join cardinalities

Figure 2. SWatcher+: example of corrections to both single-table selection and join cardinalities. SS, HJ, IS, MJ, and NL denote the operators SeqScan, HashJoin, IndexScan, MergeJoin, and NestedLoop, respectively. Corr denotes correction factors. True/Est/Corrected denote true/estimated/corrected cardinalities, respectively.

Second, SWatcher+ further corrects join cardinality estimates in κ^\hat{\kappa} using F\mathcal{F} when necessary. Let JQJ_Q denote the set of tables joined by QQ and CQC_Q the set of watchset queries used in the correction step above. Join CE correction may be needed if CQC_Q is not empty. SWatcher+ first searches for F\mathcal{F} entries indexed by (JQ,CQ)(J_Q,C_Q). If no exact match exists, it instead identifies a set of indices {(Ji,Ci)}\{(J_i,C_i)\} such that the JiJ_i’s are disjoint, each CiC_i equals the restriction of CQC_Q to the tables in JiJ_i, and the union of the JiJ_i’s maximally covers JQJ_Q.3 We illustrate this process in [2]. Recall that for each (Ji,Ci)(J_i,C_i), FJi,Ci\mathcal{F}_{J_i,C_i} stores the compensating correction factors for subplans joining subsets of JiJ_i. SWatcher+ applies correction in a bottom-up fashion. After correcting single-table selection CEs in the first step, consider a join involving two tables J′J' where at least one input cardinality is corrected. SWatcher+ first obtains the revised output CE (induced by the corrected inputs), then multiplies it by FJi,Ci(J′)\mathcal{F}_{J_i,C_i}(J'), the compensating correction factor recorded for J′J', and use the result as

the corrected CE. We then repeat this process for three-table joins, four-table joins, etc., until the join involving all of JiJ_i.

Example 4.2. Continuing with Theorem 4.1, κ~[ss⋈hd]\tilde{\kappa}[\mathrm{ss}\bowtie\mathrm{hd}] is computed from κ~[ss]\tilde{\kappa}[\mathrm{ss}] and the join selectivity between ss and hd, estimated by the optimizer. It is refined by the compensating corrections factors in F{ss,hd,ca,sc,cd},{q1}\mathcal{F}_{\{\mathrm{ss},\mathrm{hd},\mathrm{ca},\mathrm{sc},\mathrm{cd}\},\{q_1\}} (ss ⋈\bowtie hd), which was cached after executing Q1Q_1 using the plan illustrated as the tree on the left in Figure 2. Then, we update κ~[ss⋈hd]\tilde{\kappa}[\mathrm{ss}\bowtie\mathrm{hd}]. This process is repeated for ss ⋈\bowtie hd ⋈\bowtie ca, ss ⋈\bowtie hd ⋈\bowtie ca ⋈\bowtie s, and beyond, using the compensating corrections factor stored in the index (Ji={ss,hd,ca,s,cd,d},Ci={q1})(J_i=\{\mathrm{ss},\mathrm{hd},\mathrm{ca},\mathrm{s},\mathrm{cd},\mathrm{d}\}, C_i=\{q_1\}). At the end, κ~\tilde{\kappa}, corresponding to the blue bottom-up path in the tree on the right, is injected to get the optimal plan Opt⁡(Q2,κ~)\operatorname{Opt}(Q_2,\tilde{\kappa}). Notably, as shown in Figure 2, it is not necessarily the same as the plan for Q1Q_1.

Let κ~\tilde{\kappa} be the final set of cardinality estimates with all corrections (if any), in contrast to the set κ^\hat{\kappa} of uncorrected cardinality estimates. SWatcher+ invokes Opt⁡(Q,κ~)\operatorname{Opt}(Q,\tilde{\kappa}) to obtain the execution plan π\pi, and records its estimated cost Cost⁡(π,κ~)\operatorname{Cost}(\pi,\tilde{\kappa}) and planning time T⁡Opt(Q)\operatorname{T}_{\mathrm{Opt}}(Q).

Post-Execution. After observing the execution of π\pi, SWatcher+ first performs basic bookkeeping. Let Texec(π)T_{\mathrm{exec}}(\pi) denote the total execution time. If any correction was applied, SWatcher+ updates the cache F\mathcal{F} of compensating correction factors by creating a new mapping FJQ,CQ\mathcal{F}_{J_Q,C_Q}, replacing any existing entry with the same signature. Specifically, for each subplan of π\pi joining tables J′⊆JQJ'\subseteq J_Q, SWatcher+ records the factor FJQ,CQ(J′)\mathcal{F}_{J_Q,C_Q}(J') as the observed output cardinality of that join subplan divided by the estimate obtained using the selection corrections in CQC_Q but without join corrections otherwise. Equivalently, applying this factor to the inputs corrected by W\mathcal{W} recovers the currently observed join cardinality. SWatcher+ also records metadata for the entry, including the creation timestamp, query QQ, and its observed execution/planning times.

Next, for each single-table selection subquery q=σpRq=\sigma_pR of QQ, SWatcher+ decides whether to admit qq as a watchset query (if q∉Wq\notin\mathcal{W}) or evict it (if q∈Wq\in\mathcal{W}). Conceptually, qq is worth monitoring if correcting its CE by its true cardinality leads to a faster query plan by a large margin — at least a speedup of θgain\theta_{\mathrm{gain}}. Since qq’s true cardinality is available from the execution (or by an additional counting query if needed, as discussed in Section 3), one could evaluate this admission condition by re-optimizing QQ with this correction to qq, executing the new plan, and measure its speedup over the plan obtained by using no CE correction. However, the overhead would be unacceptable. Instead, we estimate the potential improvement without any new query execution. To further reduce the need to reoptimize, we heuristically apply quick checks using two thresholds to eliminate any QQ not worthy of monitoring: θExec\theta_{\mathrm{Exec}}, minimum execution time for QQ, and θOpt\theta_{\mathrm{Opt}}, maximum optimization time for QQ.

Intuitively, there is little benefit to meddle with a query that already runs fast, and there is too much overhead to meddle with a query whose optimization takes long. The details are explained below.

Suppose qq is not a watchset query. 1) Quick checks: If TExec(π^)<θTExecT_{\mathrm{Exec}}(\hat{\pi}) < \theta_{T_{\mathrm{Exec}}} or TOpt(Q)>θTOptT_{\mathrm{Opt}}(Q) > \theta_{T_{\mathrm{Opt}}}, do not admit qq. 2) Speedup check: Let κ^\hat{\kappa} the set of model-estimated cardinalities. Let κ′\kappa' the set of estimates formed by the observed true cardinalities for qq and all join subplans of π\pi involving qq, plus uncorrected cardinality estimates for all other single-table subplans. We invoke the optimizer to obtain the baseline plan π^=Opt⁡(Q,κ^)\hat{\pi} = \operatorname{Opt}(Q,\hat{\kappa}), as well as the plan π′=Opt⁡(Q,κ′)\pi' = \operatorname{Opt}(Q,\kappa'), which would be obtained by admitting qq (alone). Let κ⋆\kappa^{\star} the set of true cardinalities observed freely from the execution of π\pi. Comparing their costs under κ⋆\kappa^{\star} yields the estimated speedup: gain⁡(q)=Cost⁡(π^,κ⋆)/Cost⁡(π′,κ⋆)\operatorname{gain}(q) = \operatorname{Cost}(\hat{\pi},\kappa^{\star})/\operatorname{Cost}(\pi',\kappa^{\star}). We admit qq if and only if gain⁡(q)≥θgain\operatorname{gain}(q) \ge\theta_{\mathrm{gain}}. When admitting qq into WW, we record its observed true cardinality card⁡(q)\operatorname{card}(q) and the speedup gain⁡(q)\operatorname{gain}(q).

Suppose qq is a watchset query. We proceed with the following steps. 1) Quick checks: If TExec(π)⋅gain⁡(q)<θTExecT_{\mathrm{Exec}}(\pi) \cdot\operatorname{gain}(q) < \theta_{T_{\mathrm{Exec}}} or TOpt(Q)>θTOptT_{\mathrm{Opt}}(Q) > \theta_{T_{\mathrm{Opt}}}, evict qq. Here, TExec(π)⋅gain⁡(q)T_{\mathrm{Exec}}(\pi) \cdot\operatorname{gain}(q) estimates the execution time that would have been observed without watching qq, using the previously recorded speedup. 2) Speedup check: SWatcher+ computes gain⁡(q)\operatorname{gain}(q) in the exact way described above, and evict qq if and only if gain⁡(q)<θgain\operatorname{gain}(q) < \theta_{\mathrm{gain}}. If qq is evicted, we also purge the entries in F\mathcal{F} indexed by any (J,C)(J,C) where q∈Cq \in C; otherwise, gain⁡(q)\operatorname{gain}(q) is updated.

Retraining CE Model

After admitting a new watchset query, SWatcher+ checks the size of the watchset. If ∣W∣|W| exceeds a prescribed threshold θnwatch\theta_{n_{\mathrm{watch}}}, we trigger refresh of the CE model m\mathfrak{m}. To obtain the training set, we first add all watchset queries with their up-to-date true cardinalities, as in § 3. Since WW is small and no longer an unbiased sample of the query workload in this case, it is augmented by randomly sampling queries from the workload, so that the size of the training set reaches ntrainn_{\mathrm{train}}. We assume SWatcher+ has access to some representation of the query workload to sample from, such as a query log.5 However, since these additional queries were not monitored, SWatcher+ queries the database to acquire their true cardinalities.

After retraining m\mathfrak{m}, SWatcher+ re-initializes WW to reflect the new m\mathfrak{m}. This process is nearly identical to that in § 4.1—specifically when qq is not yet a watchset query. The key difference is that fresh TExec(π)T_{\mathrm{Exec}}(\pi) and TOpt(Q)T_{\mathrm{Opt}}(Q) are unavailable, since data updates may have occurred or the plan may change due to the new m\mathfrak{m}. Therefore, for each qq, to avoid query execution, SWatcher+ instead uses the most recent cached values from WW and F\mathcal{F}.6 Finally, we clear F\mathcal{F}.

Note that re-initialization of WW does not guarantee that ∣W∣|W| fall below θnwatch\theta_{n_{\mathrm{watch}}} following refresh. In the unlikely event where the threshold is immediately violated, we apply exponential backoff on θnwatch\theta_{n_{\mathrm{watch}}}, similar to the process described in § 3.

Cost Analysis and Discussion

Like Watcher1D, the cost of SWatcher+ has three components: processing data updates, processing queries, and retraining. By being more selective in which queries to monitor, the size of WW is much smaller than Watcher1D’s—typically 90% less in our experiments in § 5. For the cost of processing queries, the extra overhead in making CE corrections using WW and F\mathcal{F} and bookkeeping is minimal. However, for a query QQ containing kk single-table selection subqueries, the speed-up check could result in up to k+1k+1 Opt⁡(⋅)\operatorname{Opt}(\cdot) calls (one to get the baseline plan π^\hat{\pi} and one for correcting each subquery) plus k+1k+1 Cost⁡(⋅)\operatorname{Cost}(\cdot) calls (to estimate their costs under true cardinalities). Luckily, in practice, quick checks—i.e., assessing whether a query will run sufficiently long without corrections and whether optimization time is short—eliminate 40%–80% of these calls, as observed in our experiments (§ 5). Note that an extra counting query may be needed if the plan executed did not use a selection subquery, but such cases are rare, as discussed in § 3. On the other hand, by proactively applying CE corrections, SWatcher+ typically improves query plans and reduce query execution times more effectively than Watcher1D. However, each refresh of the CE model is more expensive in SWatcher+, because SWatcher+ may need to execute additional queries to construct a large enough training set, plus additional optimizer calls (linear in the size of the training set) to re-initialize WW. § 5 will demonstrate the overall effectiveness of SWatcher+ in comparison with other approaches.

The five parameters listed in Table 1 are straightforward to set and require little tuning (detailed in § 5), although we also include alternative settings as ablation studies in § 5 and in [2]. As an exception, setting of θnwatch\theta_{n_{\mathrm{watch}}} is primarily driven by users’ desire to cap the overhead in processing data updates. We believe it is possible to extend SWatcher+ to avoid this parameter altogether: with no bound on ∣W∣|W|, we would control the watchset contents by tracking both the benefit (query performance) and cost (incurred for data updates) of each watchset query to ensure positive net benefit over time; model retraining would then be forced if “thrashing” of WW is observed. We leave further investigation as future work.

Experiments

We have conducted extensive experiments comparing SWatcher+ with other methods (codes in [1]). To briefly summarize our results here and in the full version [2], SWatcher+ consistently achieves superior overall performance, even when competing methods are configured with post hoc-optimal settings. SWatcher+’s selective monitoring and correction strategies are key to its effectiveness, allowing it to adapt gracefully to workloads with diverse characteristics ranging from OLTP to OLAP. In particular, for OLTP queries where ML-based CE models may not be cost-effective, SWatcher+ automatically avoids unnecessary monitoring and model refreshes, while baseline methods incur high overhead.

Implementation. We implemented the Watcher framework in Python 3 on top of PostgreSQL V16.2, with cardinality injection implemented using the methods in [8, 52], and plan hinting facilitated by pg_hint_plan [33]. Reported execution times are the median of three repetitions through our experiments. All experiments are conducted on a Linux server with 8 Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz processors and 1TB of disk storage.

CE models tested. To assess Watcher’s ability to work with different CE models, we choose three models: MSCN [18], JGMP [41] and Naru [56]. MSCN is known for its low complexity and training/inference overhead [8, 47]; here we use it as a purely query-driven model by disabling MSCN’s bitmaps so that it learns only from query feedback. JGMP is a more advanced model that incorporates data samples from each table as well as PostgreSQL’s up-to-date single-table selectivity estimates. It is shown to achieve an accuracy comparable to or better than MSCN with even fewer training samples, albeit with a higher training and inference overhead. Naru directly learns the underlying data distribution and naturally supports incremental model updates without retraining from scratch.

Data and updates. We conduct experiments using both DSB [4, 5] and IMDB/JOB-light [14, 17, 21] benchmarks. We focus primarily on DSB, as its data and queries better match our setting (see details below), and use IMDB/JOB-light to further validate SWatcher+’s effectiveness on a real-world benchmark. DSB contains a large amount of timestamped data, making it easy to construct an update workload. We have tested DSB under scale factors of 2 and 10; results on 10 are presented in [2] and show similar conclusions. To simulate data distribution shifts, we first generate all benchmark tables under default settings. In the DSB schema, we identify the following fact tables with timestamp columns as “dynamic”: tables ss, cs, ws with *_sold_date_sk; tables sr, cr, wr with *_returned_date_sk, and table inv with inv_date_sk. To generate a dynamic workload, we use a 60-day sliding window: as it moves forward, tuples corresponding to the oldest date are deleted, and tuples for the next date are inserted. The initial database instance contains data with *_date_sk between 2450815 and 2450874. After applying 60 days of updates, the final database instance reflects a 60-day forward shift with *_date_sk between 2450875 and 2450934, representing a completely different database state. The dimension tables remain unchanged throughout. The third column of Table 2 lists, for some query templates we evaluated, the total number of data updates relevant to each query, ranging from 0.08 to 1.55 million. For IMDB, following the same procedure, only title.production_year is a timestamp column and is used to stream the data. The initial instance contains data from 1900 to 1959; after applying 60 years of updates, the final instance covers 1960 to 2013. Each workload contains a total of 2.45M data updates.

Template# tables# updatesP50/P75 TExec_{\mathrm{Exec}}†Avg. TOpt_{\mathrm{Opt}}†θExec_{\mathrm{Exec}}†
Q013a60.30M459/5423400
Q013b60.30M483/7403400
Q01860.14M465/4873450
Q01960.30M206/2973250
Q04050.14M2/232
Q07291.30M435/66516700
Q085a80.08M1/285
Q085b80.08M1/485
Q09950.14M54/83280
Q10080.30M928/12607600
Q10190.41M38/466750
Q10291.55M45/479550
TJQ013a60.30M80/1433400
TJQ013b60.30M96/4724400
THJQ10080.30M134/31010400
FJQ10080.30M101/1849400

Table 2. DSB Query templates and the associated information. The templates cover a wide range of join types and predicate types. †: the percentiles (P50, P75) and averages (Avg.) are measured over the initial query set. θExec_{\mathrm{Exec}} is the configuration for SWatcher+. The last three columns are presented in ms.

Queries. DSB features many complex query templates. To ensure that we can run all approaches and underlying CE models and to make the results possible to interpret, we prepare our query templates as follows: i) we filter out DSB query templates that did not involve any dynamic tables or lacked selection conditions on them; ii) we remove templates with complex predicates such as LIKE or disjunctions; and iii) we further restrict the number of selection conditions in each template to one to four (without changing join conditions).7 Table 2 summarizes the DSB templates we use. The query templates join 5 to 9 tables and include 12 templates (prefix “Q”) with one additional selection condition each, 2 templates (“TJQ”) with two, 1 template (“THJQ”) with three, and 1 template (“FJQ”) with four. For the real workload, due to space limit, we select the five largest JOB-light templates (all three 5-table and two 4-table joins), retaining all predicates except those on production_year. The numerical IDs are the same as the numbering in DSB and JOB-light respectively. Full queries are in the full version [2].

Next, we generate the query workload by instantiating query constants in the templates using uniformly sampling from the appropriate domains. For example, a query generated from Q101 may include the selection condition ss_sales_price / ss_list_price BETWEEN 0.49 AND 0.89, where 0.49 and 0.89 are randomly generated.

Combined workloads & evaluation metrics. To obtain a combined query/update workload for testing, we generate 3000 queries and mix them at different rates with data updates:

  • 3-batch: each with 20 days of updates followed by 1000 queries.

  • 6-batch: each with 10 days of updates followed by 500 queries;

  • 60-batch: daily updates followed by 50 queries.

Before evaluation starts on the testing workload, all methods are given a number of training queries, randomly generated from the same query distribution as the testing workload, along with information obtained by executing them on the initial database instance. Such information includes single-table true cardinalities (required by Watcher1D, SWatcher+), multi-table join true cardinalities (required by Watcher2D and baselines), execution time, planning time, and plan cost (required for SWatcher+), as well as any additional information required for training the underlying CE models.

Since the overall workload performance can be difficult to interpret for a mixture of different query templates, we choose a simpler experimental design where we evaluate each query template in a separate workload. We refer to a 6-batch workload testing a query template by the template itself (e.g., Q013a, TJQ013b), while 3-batch and 60-batch results are presented in the full version [2]. We apply the same 6-batch workload generation to IMDB/JOB-light, but with only 600 queries mixed with data updates, as these queries run substantially longer than those in DSB.

Across templates, the above workloads cover a wide range of characteristics from OLAP to OLTP. Since DSB is OLAP-centric, many templates are complex and expensive (e.g., Q013a, Q013b, and Q100) and hence stand to benefit more from accurate CEs. On the other hand, the way we extracted templates from DSB led to a few (e.g., Q040, Q101) whose execution times are lower than their optimization times, resulting in workloads resembling OLTP. Intuitively, when there is little room for improving execution times, a smart system should avoid paying maintenance and optimization costs for such templates. We keep such templates in our workloads to study how different approaches adapt to them.

For metrics, we use Q-error [31] to measure CE (in-)accuracy and define overhead as the end-to-end running time excluding query execution, including CE model inference time and the cost of maintaining required information for each method.

Methods & parameters setup. For following methods, the training set size is 1500 for MSCN and 128 for JGMP (128 is the smallest number tested in [41] in which JGMP still outperforms MSCN). Naru uses 10 training epochs and 2 incremental update epochs (following the recommendations in [47, 55, 56]).

  • True: Always inject true cardinalities for monitored subqueries, with no overhead accounting. While unrealistic, it allows us to evaluate the benefit and limit of knowing true cardinalities.

  • Baseline: Always use the same CE model with no updates.

  • Periodic: Periodically refresh the model after every XX days of data updates, where X∈{10,20,30}X \in\{10, 20, 30\} reflects varying degrees of timeliness. For instance, in a 6-batch setting, X=10X = 10 is ideal because it triggers refresh immediately after every batch of updates, while X=20X = 20 means that the 1st, 3rd, and 5th batches are handled by models that lag behind by 10 days of updates.

  • LEO: We implemented the monitor-and-correct approach from LEO [45], adapting it to our setting while remaining as faithful as we could. Specifically, LEO records adjustments needed for a subquery whenever the estimate deviates from the truth by at least 5%. For an incoming query, LEO applies an adjustment if it matches a tracked subquery with at least 80% similarity. LEO also updates the adjustments according to data updates.

  • Watcher1D: Deploy the model with Watcher1D, using nwatch=ntest=ntrain=1500n_{\mathrm{watch}} = n_{\mathrm{test}} = n_{\mathrm{train}} = 1500 for MSCN and 128 for JGMP; ϵ\epsilon is 90th (P90) or 95th (P95) percentile of the Q-errors observed during training.

  • SWatcher+: Deploy the model with SWatcher+. We set θsim=0.8\theta_{\mathrm{sim}} = 0.8, θnwatch=600\theta_{\mathrm{nwatch}} = 600, and θTopt=10%\theta_{\mathrm{Topt}} = 10\% of θExec\theta_{\mathrm{Exec}} (ablation studies in [2] shows that changing the two of them within sensible ranges have little impact on results). For θExec\theta_{\mathrm{Exec}}, we choose a value to separate slow and fast queries in the training set when evident (see example in [2]); otherwise, we set θExec\theta_{\mathrm{Exec}} to around the 50th or 75th percentile. These settings are summarized in Table 2. Next, the choice of θgain\theta_{\mathrm{gain}}, as with the training data size, depends on the characteristic of the underlying model. We set θgain=10%\theta_{\mathrm{gain}} = 10\% for MSCN/Naru and 100.01% for JGMP: since JGMP generally produces better estimates at higher overhead, it makes sense for SWatcher+ to be more aggressive in monitoring and correcting with a lower θgain\theta_{\mathrm{gain}}. Finally, as an ablation study, we also test a SWatcher+ version without correcting join subqueries, though the default (with such corrections) performs better overall.

MSCN with/without Watcher

We start with DSB results of applying Watcher with MSCN as the underlying CE model; results for JGMP and Naru are discussed in Section 5.3. We focus on workloads with a single selection condition here (i.e., those starting with “Q”); results for multiple selection conditions (“TJQ”, “THJQ”, and “FJQ”) are discussed in Section 5.2. The IMDB/JOB-light results are presented in Section 5.4.

For each single-selection query template, we measure the end-to-end running time for each method and report the results using their configuration optimized for the lowest running time. For these workloads, we let True acquire and inject true cardinalities for single-table selections for free. We report the Periodic setting with the best performing period length (XX) observed post hoc, which is impractical in a real deployment.8 We present the results for the 6-batch setting in Figure 3a, and those for the 3-batch and 60-batch settings in [2]. In Figure 3a (and later in Figure 5 for JGMP and Naru), all end-to-end running times are normalized against True’s, shown in the X-axis labels. We divide the query templates into four groups below based on key observations about their results; we will dive deeper into Groups 1 and 2 later.

Normalized end-to-end running time across all methods

Figure 3. Normalized end-to-end running time, including both total query execution time (represented by the lower portion of the bar with darker shade) and overhead (upper portion with lighter shade), using MSCN as the CE model, across all methods. A number is above the bar if its height falls outside the scope. The number below the template name is the end-to-end running time of True, used for normalization. Figure 3a is discussed in § 5.1, while Figures 3b to 3d are discussed in § 5.3.

Normalized end-to-end running time using JGMP/Naru as the black-box

Figure 5. Normalized end-to-end running time using JGMP/Naru as the black-box; same format as Figure 3.

Group 1 (True-improves): Q013a, Q013b, Q100. These templates exhibit a noticeable performance gap of approximately 10% between True and Baseline, indicating that injecting true selection cardinalities into the monitored subqueries significantly improves query execution times. SWatcher+ achieves the lowest end-to-end running time, outperforming Baseline, Periodic, Watcher1D, and LEO. By applying corrections rather than refresh, SWatcher+ achieves total query execution times that are often closer to those achieved with true cardinalities than those using updated models from Periodic. In contrast, Watcher1D (resp. LEO) incurs much higher overhead due to the cost of maintaining a large W (resp. set of adjustments), which outweighs execution time savings. A more detailed analysis is provided in Section 5.1.1.

Group 2 (True-backfires): Q018, Q040, Q072. For this group, injecting true selection cardinalities can backfire, causing a query to execute slower than Baseline. The reason is that PostgreSQL, while given true selection cardinalities, still relies on wrong assumptions about join selectivities and therefore can produce worse final plans. SWatcher+ mitigates this issue by also correcting join CE using the cache J\mathcal{J}, while Periodic, Watcher1D, and LEO, which focus solely on improving selection CE accuracy, are less dependable. Notably, Periodic performs best with infrequent refresh (only once), which results in lower selection CE accuracy but faster query plans than True. While Watcher1D performs okay for Q018 and Q072, its backfires poorly for Q040. LEO always incurs highest overhead because it corrects selection CEs whenever possible. Among all methods, SWatcher+ is the most consistent in avoiding backfires with acceptable overhead. Section 5.1.2 provides further details.

Group 3 (True-oblivious): Q019, Q099. This group reflects cases where query performance is relatively insensitive to CE accuracy, resulting in similar query execution times across all methods. Overhead cost can still make a difference: with selective monitoring, SWatcher+ achieves a 5% to 20% lower overhead than Periodic and Watcher1D, and much lower than LEO. For Q019, SWatcher+ does not add any items to its WW. For Q099, it maintains a small WW with only 2 items, applying corrections to 1.17% of queries, Nonetheless, the overhead from SWatcher+’s WW admission checks still results in a slightly larger overhead than Baseline. In comparison, Periodic and Watcher1D often trigger unnecessary refreshes that add more overhead without performance gains; LEO incurs the highest overhead in maintaining and applying adjustments.

Group 4 (Opt-dominated): Q085a, Q085b, Q099, Q100. This group comprises queries that finish in a very short time, with total query execution times of ≤100\le100s over the entire workload. Additionally, each query’s planning time is observed to be 2×2\times to 4×4\times its execution time. In this case, SWatcher+ performs the same as Baseline since no queries pass the admission check, avoiding most overhead. However, both Periodic and Watcher1D incur non-trivial overheads due to unnecessary refreshes, and LEO wastes resources on unnecessary adjustments. For instance, in Q101, Periodic spends 39.18s for a single refresh cycle (including collecting data for retraining); Watcher1D takes 20.51s for a single refresh cycle and 99.78s for maintaining WW; LEO spends 165.47s on adjustments. These costs exceed the total query execution time, which remains under 90s.

Analysis of True-improves (Q013b)

We take a closer look at Q013b from Group 1 (True-improves). First, we compare various parameter settings for all methods and show a detailed breakdown of running times in Table 3. For Periodic, refreshing after every batch of updates (X=10X = 10) achieves the lowest total query execution time Texec(Q)T_{\mathrm{exec}}(Q) (excluding overhead during planning)—over 20s shorter than the other XX values—though it incurs the highest retraining time and consequently loses to X=30X = 30 in terms of end-to-end running time. For Watcher1D, using ϵ\epsilon of P95 saves two refreshes (over 40s) compared with P90 but results in an additional 17s of total query execution time; both configurations incur high overhead for maintaining a WW of 1500 subqueries. For LEO, applying adjustments leads to great savings in query execution time in “potent region” (defined later in Figure 4) but is less impressive in total

MethodSettings†Total Texec(Q)T_{\mathrm{exec}}(Q)Retraining TimeOverhead on queriesOverhead on updatesTotal Texec(Q)T_{\mathrm{exec}}(Q) in potent region
True-985.080(0)0075.44
Baseline-1087.640(0)5.230154.53
PeriodicX=10X=101014.33171.68(6)5.85-109.33
PeriodicX=20X=201042.6177(3)5.93-118.13
PeriodicX=30X=301035.2438.04(1)5.88-109.33
Watcher1Dϵ=P90\epsilon=P901022.0662.98(3)5.4292.22115.40
Watcher1Dϵ=P95\epsilon=P951039.6420.7(1)5.5395.37128.30
LEO-1014.580(0)19.03172.6782.31
SWatcher+θgain=110%\theta_{\mathrm{gain}}=110\% no join correction1021.890(0)28.183.70110.13
SWatcher+θgain=110%\theta_{\mathrm{gain}}=110\%989.530(0)26.713.4295.32
SWatcher+θgain=101%\theta_{\mathrm{gain}}=101\% no join correction1011.960(0)27.575.3199.92
SWatcher+θgain=101%\theta_{\mathrm{gain}}=101\%985.670(0)26.314.8890.68

Table 3. Q013b: componentized running times. †: the parameters, shared within the same method and detailed previously, are omitted. The last five columns are in seconds. The “Retraining Time” column includes the number of refreshes triggered in parentheses. Highlighted rows achieve the lowest end-to-end running time (i.e., the sum of the third through sixth columns) for each method and serve as the representatives in Figure 3a.

Q013b ideal saving computed and ordered by the difference in execution time between Baseline’s and True’s

Figure 4. Q013b: “ideal saving” computed and ordered by the difference in execution time between Baseline’s and True’s.

Texec(Q)T_{\mathrm{exec}}(Q). Also, LEO’s overhead is prohibitive, though no retraining is needed. Finally, for SWatcher+, starting from the baseline of θgain=110%\theta_{\mathrm{gain}} = 110\% and no join correction, enabling join correction yields significant savings (>30>30s) in total query execution time; lowering θgain\theta_{\mathrm{gain}} to 101% also yields marginal improvement (<10<10s). While SWatcher+’s corrections and admission-eviction checks add more overhead to queries than Periodic, Watcher1D, and LEO, this cost is justified by the bigger improvements in total query execution time. Moreover, with selective monitoring, SWatcher+ keeps ∣W∣<50|W| < 50 in all cases, resulting in much lower overhead in processing data updates than Watcher1D and LEO.

Excluding overhead on data updates, Watcher1D achieves lower running time than Periodic when both perform the same number of refreshes, suggesting that Watcher1D identifies better timing for retraining. Watcher1D also requires less retraining time than Periodic by skipping the collection of new training data. Neither benefits, however, can justify Watcher1D’s high overhead for maintaining a large W\mathcal{W} on data updates.

Next, as discussed in § 1, sometimes inaccurate CEs have little impact on query performance; ideally, we would like to avoid the overhead of correcting them. For Q013b, Figure 4 shows, for each of its 3000 queries, the “ideal saving” achievable by True over Baseline through injecting true selection cardinalities. We order these queries by the amount of ideal saving. The results show that for the leftmost 5% queries, injection backfires; the majority of the queries (in the middle) are insensitive to CE accuracy; the rightmost 10% of queries, located in what we call the “potent region”, stand to benefit from accurate CEs, potentially saving at least 49ms per query. This region is exactly the target of SWatcher+. As shown in the last column of Table 3, SWatcher+ has fast query execution time in the potent region, outperformed only by LEO. However, LEO’s consistent adjustments strategy, agnostic to performance impact, cannot reliably produce benefits: e.g., it has higher overall TExec(Q)T_{\mathrm{Exec}}(Q) than SWatcher+, as shown in Table 3, and it backfires more, as shown later in Section 5.1.2. The unreliable benefit, coupled with its high overhead for processing data updates, makes LEO fall short overall compared with SWatcher+. As a trade-off, by targeting only “potent region”, SWatcher+ does not produce CEs as accurate overall as the accuracy-driven baselines: for the 3000 queries in Q013b, SWatcher+ (across different setups) yields a P90 ∈[2.15,2.20]\in[2.15, 2.20], whereas LEO achieves 1.20, Periodic [1.87, 2.19], and Watcher1D [1.96, 2.19]. Additional percentile results are presented in the full version [2]. Nevertheless, as shown above, this accuracy gap does not always translate into a performance advantage.

Finally, when join correction is on and θgain=101%\theta_{\mathrm{gain}} = 101\%, SWatcher+ selects only 1% of single-table selection subqueries and corrects only 13% of the queries in this workload. Among queries in the potent region (Figure 4), however, SWatcher+ corrects 58% of them, and 89% of those corrected are among the top 1% most potent. In short, SWatcher+ focuses its efforts on queries with high payoff.

5.1.2 Analysis of True-backfires. In Q018, Q040, and Q072, respectively, 16.2%, 33%, and 19.87% of the queries experience a slowdown of at least 50ms per query due to injection of true cardinalities. Meanwhile, 83%, 66.9%, and 75% queries remain insensitive, and only a small fraction of queries run faster when true cardinalities are injected. The primary reason for this backfiring is the lack of accurate estimation for other subqueries. Correcting selection subquery cardinalities sometimes worsens join CEs, leading to a worse

overall plan. We observe serious backfiring for LEO, which applies adjustments to over 90% of all queries. Furthermore, since LEO is not selective about what to maintain, the overhead is significant as well. SWatcher+ mitigates the issue in two ways. First, as observed in Q040, the admission-ejection checks effectively determine cases when injecting more accurate CEs would not improve performance, thereby avoiding caching ineffective subqueries in W\mathcal{W} and preventing undesirable corrections. Second, as demonstrated in Q018 and Q072, SWatcher+ further applies corrections to join CEs, counteracting the inaccuracies stemmed from injecting selection subqueries solely, and guiding plan selection back on track. Overall, among queries for which True backfires, SWatcher+ achieves the following improvements in total query execution time compared with True: 53s (22.3%) in Q018, 283s (98.2%) in Q040, and 67s (23.5%) in Q072. As an example, for Q018, about 89.1% of the queries receive corrections in both selection and two-table join subqueries, contributing 73.6% of the total savings for this query template.

The growth, utilization, and memory overhead of W\mathcal{W} and F\mathcal{F}, along with the overhead of additional single-table query executions across all workloads in Figure 3, are presented in detail in [2].

Multi-Selections over Joins (TJQ/THJQ/FJQ)

We now turn our attention to results for templates with multiple selection conditions over joins. We first discuss templates TJQ013a and TJQ013b, which are 6-table joins involving local selections on ss and hd joined on ss_hd=sk=hd_demo_sk. The three subqueries of interest are σ\sigma(ss), σ\sigma(hd), and σ\sigma(ss) ⋈\bowtie σ\sigma(hd). For these workloads, we let True acquire and inject true cardinalities for all three subqueries of interest for free. Here, we add the method Watcher1D+Watcher2D, where Watcher2D incrementally maintains cardinalities for joins involving local selections on both joining tables (more details are available in [2]). We omit LEO here due to poor scalability, as its adjustment updates incur unaffordable overhead under data updates (similar to the issue faced by Watcher2D discussed below). For all three Periodic instances, we set X=30X = 30, while in Watcher1D+Watcher2D, ϵ=P90\epsilon= P90. For Baseline, Periodic, and Watcher1D+Watcher2D, the CE models are trained for all three subqueries of interest. Finally, SWatcher+ trains models for σ\sigma(ss) and σ\sigma(hd), but relies on its F\mathcal{F} for join CE correction.

As shown in Figure 3b, for TJQ013a and TJQ013b, SWatcher+ outperforms Periodic and Watcher1D+Watcher2D, achieving query execution times close to or, interestingly, even better than True’s. The reason is that SWatcher+ goes beyond correcting the two-way join σ\sigma(ss) ⋈\bowtie σ\sigma(hd); its correction factor caching is able to capture corrections for other join patterns with acceptable overhead. In contrast, for Watcher1D+Watcher2D, maintaining W\mathcal{W} in Watcher2D accounts for 86% of the overhead, exceeding 60% of the total end-to-end running time for both templates. This overhead renders maintaining accurate join cardinalities impractical even for two-way joins; handling larger joins would be infeasible.

In Figure 3c and Figure 3d, we observe similar trends for THJQ100 and FJQ100, both 8-table joins. These templates have more relevant selection-join subqueries than TJQ013a and TJQ013b, making Watcher1D’s monitoring prohibitively expensive; therefore, we remove Watcher1D+Watcher2D from comparison. Other methods are evaluated under the same setting as before. Again, SWatcher+’s join correction using cached correction factors is lightweight and effective, allowing it to correct join CE for subqueries such as σ(ss)⋈σ(item)⋈σ(c)\sigma(\mathrm{ss}) \bowtie\sigma(\mathrm{item}) \bowtie\sigma(\mathrm{c}) and σ(ss)⋈σ(item)⋈σ(c)⋈σ(cd)\sigma(\mathrm{ss}) \bowtie\sigma(\mathrm{item}) \bowtie\sigma(\mathrm{c}) \bowtie\sigma(\mathrm{cd}), without paying the cost maintaining their true cardinalities. Even though such corrections are heuristic and approximate, they help to make SWatcher+ achieve substantially better end-to-end performance than other methods.

Finally, as mentioned earlier at the beginning of Section 5 (Footnote 7), we limit the number of selection predicates in query templates. The phenomenon that additional selections tend to decrease over query execution time can be seen here in Figure 3b to Figure 3d when comparing TJQ013a, TJQ013b, and THJQ100/FJQ100, and earlier in Figure 3a when comparing Q013a, Q013b, and Q100. Hence, the limit on the number of selections helps us ensure a sufficient range of table selectivities that expose more plan choices for evaluation.

JGMP/Naru with/without Watcher

In addition to MSCN, we extend the experiments (Figure 5) to evaluate the effectiveness of Watcher over a sample-efficient CE model (JGMP) and a data-driven CE model (Naru) that support incremental updates, respectively. Despite the different design trade-offs of MSCN vs. JGMP vs. Naru, applying SWatcher+ to JGMP/Naru requires only changes to the training data size (or training/incremental update epochs) and θgain\theta_{\mathrm{gain}}, as explained in the setup.

JGMP. Figure 5a mirrors Figure 3a, but shows when JGMP is used as the underlying CE model instead of MSCN.10 On the same workloads, JGMP achieves better CE accuracy than MSCN but incurs higher (re-)training (even with fewer training queries) costs and higher inference costs, consistent with [41]. The reason is that JGMP requires fresh samples from the tables for each retraining, and uses PostgreSQL’s up-to-date single-table selection estimates for inference, thereby making it more aware of the current database state. Comparing Figure 3a and Figure 5a, we observe a shift: more templates, e.g., Q100 (True-improves for MSCN), Q018 and Q072 (True-backfires for MSCN), now fall into True-oblivious, indicating that JGMP’s improved accuracy makes query performance less sensitive to CE errors. It also generally reduces the adjustments LEO requires. Moreover, since JGMP models are more sample-efficient, they yield a significantly smaller nwatchn_{\mathrm{watch}} and lower overhead in Watcher1D compared with MSCN. As a result, Watcher1D outperforms Periodic in two workloads—Q013b and Q085b—despite the latter’s post hoc use of the optimal refresh interval.

Next, SWatcher+ outperforms Baseline, Watcher1D and Periodic across groups True-improves, True-backfires, and opt-dominated. Such consistency demonstrates that SWatcher+’s corrections effectively improve query execution times and justify the overhead of maintaining WW. Even in True-oblivious, which consists of workloads less sensitive to CE errors, SWatcher+ still outperforms others in 4 out of 5 templates, because it correctly identifies the limited benefits of corrections and instead skips refreshes. Finally, on 3 of 11 templates, Q019, Q099, and Q102, LEO outperforms SWatcher+. In these cases, where CEs have little impact, JGMP’s strength lets LEO requires fewer adjustments (though still more than SWatcher+), while SWatcher+ still incurs some overhead assessing potential performance gains before determining they are not worthwhile. Because SWatcher+ backtracks quickly, the end-to-end gap remains small and its query execution times remain competitive.

Naru. Naru is a data-driven CE model that can be incrementally updated with insertions but not deletions. Because our workloads contain both insertions and deletions, we explore two variants with day-aligned update intervals (XX=10,20,30) following Naru’s original strategy [56]. Naru-Inc incrementally updates the model using insertions but ignores deletions; Naru-Ret, retrains the model from scratch, accounting for both insertions and deletions. Empirically, Naru-Inc performs better and is therefore selected for subsequent evaluation; additional details are in [2].

Figure 5b compares Naru-Inc with SWatcher+ using Naru-Inc as the underlying CE model, on one representative template for each of the four groups. As shown in Figure 5b, Naru-Inc’s behavior is unstable alone, but SWatcher+-Naru-Inc is more consistent and outperforms Naru-Inc in end-to-end running time across templates. For Q013a (True-improves), SWatcher+ proactively corrects the errors caused by Naru-Inc ignoring data deletions during incremental model updates. For Q040 (True-backfires), Naru-Inc manages to produce reasonably accurate estimates, but plan performance degrades slightly due to backfiring. For Q019 (True-oblivious), Naru-Inc’s inaccurate estimates happen to improve plan performance. In all above cases, SWatcher+ produces better plans than Naru-Inc with lower or comparable overhead. Q102 (opt-dominated) is the only template where Naru-Inc’s plans are slightly better (though the difference is small because opt-dominated queries are fast in the first place), but the difference is reversed for end-to-end running time because SWatcher+ incurs less overhead. Overall, these results show that Naru-Inc, an incrementally updatable data-driven CE model, also benefits from SWatcher+, further demonstrate the utility and adaptivity of our framework across different CE models.

Results of IMDB/JOB-Light

IMDB/JOB-light results are presented in Figure 6. We evaluate Watcher1D and LEO only on Q36, where total query execution time is roughly 1000 seconds across all methods; however, their maintenance overhead accounts for approximately 70% and 90% of this time, respectively. Since both methods incur this maintenance overhead scaling linearly with the number of updates, which is identical across all templates, this cost is clearly prohibitive for the remaining templates as well.

Normalized end-to-end running time on IMDB using MSCN

Figure 6. Normalized end-to-end running time on IMDB using MSCN; same format as Figure 3.

We also group the five templates by observed behavior: Q36, Q44, and Q70 fall into the True-backfires group; Q66 into True-oblivious; and Q68 into opt-dominated. The observations are consistent with the DSB results. Across all groups, SWatcher+ consistently outperforms Periodic. When accurate CEs actually backfire or have little impact, Periodic can perform comparably end-to-end – but only under its least frequent retraining interval, a setting identifiable only post hoc. In contrast, SWatcher+ adapts automatically by monitoring the impact of CE accuracy on query performance.

Related Work

There is growing interest in adapting learning-based CE models on evolving databases. Unlike Watcher, which is model-agnostic, these works build dedicated models that (re-)train or fine-tune upon detecting distribution shifts [6, 27, 37, 47, 48, 56]. DDUp [19] targets data drift on CE models based on neural networks. Warper [23] detects drift statistically and retrains, using GANs to generate new samples that are labeled by extra executions. Wu et al. [49] mitigates workload drift with a replay buffer. Another line of work improves model robustness: RobustMSCN [36] reduces retraining frequency at the cost of higher model complexity, and NeuroCDF [50] enhances generalization to OOD queries. Hybrid approaches ALECE [25] and [10] can directly incorporate data updates. Despite these advances, how to deploy CE models in dynamic environments remains unsolved. In practice, significant data changes still necessitate frequent retraining/refreshing.

WATCHER is a great fit for query-driven CE methods, due to their ability to leverage query workloads. Recent studies on Amazon Redshift [51] found that many real-world queries repeatedly access similar regions. Query-driven CE models span from traditional statistical summaries [3, 44] to ML-based approaches [6, 13, 18, 27, 32, 34, 37, 41, 48]. Among the above, we have tested WATCHER with: MSCN [18], which uses a multi-set query representation, remains a leading query-driven cardinality estimator [16, 47], and with JGMP [41], which has demonstrated better sample efficiency.

Another class of CE models is data-driven, with underlying techniques again spanning from traditional data summaries [10, 22, 26, 38, 39] to ML [9, 12, 48, 54, 56, 59]. They are generally robust to workload. However, modeling joint data distributions is hard and less effective for complex queries, and maintaining such models is expensive, often demanding frequent updates [36]. Specifically, DeepDB [12] incrementally updates the model for every insertion (although deletion support is stated by the paper, implementation is unavailable [11]). Naru [56] incrementally updates the model on each new batch of data appends, but batching strategy is still fixed and day-aligned. As shown in § 5.4, WATCHER can also benefit data-driven CE models, making effective CE corrections while intelligently timing model refreshes.

The idea of guiding future optimization with query feedback has been explored for decades, beginning with LEO [45] and later productized in Microsoft SQL Server as CE feedback [43]. The latter focuses on en/dis-abling optimizer options—such as assuming predicate correlation/independence—rather than deploying learned CE models. LEO [45] targets correcting optimizer CE errors, but as discussed in § 1 and § 5, its maintenance and correction decisions are based purely on CE error, whereas WATCHER’s decision is holistic. Additionally, WATCHER considers practical retraining for learned CE models, whereas LEO assumes traditional CE models.

More recently, work on end-to-end learned query optimization [28, 46, 53, 57, 58] tackles the entire optimization problem, directly returning high-performing plans using models trained on observed executions, rather than breaking the problem down into CE, costing, and search. For example, BayesQO [46] uses Bayesian optimization to search for plans for recurring queries. These approaches require substantial training and/or preparation cost, which can be amortized over time assuming that significant data and workload distribution changes happen rarely. Our work instead operates within the classical optimizer pipeline, focusing specifically on improving CE, and targets a more dynamic setting.

Conclusion and Future Work

In this paper, we have studied the deployment problem of learned CE models in dynamic settings. We take a holistic approach in both design and evaluation, considering the ultimate impact of CE on query performance, as well as the overhead in maintaining, retraining, and using CE models. Our results highlight the pitfall of either fixating on improving single-table CEs (simply because it is easy to do) or overcommitting on maintaining join CEs (simply because it may yield greater improvements in query performance). Instead, our SWatcher+ effectively reduces overhead by judiciously deciding what to maintain through a benefit-based analysis. By design, it automatically identifies high-impact CEs that warrant dedicated monitoring efforts, better handles backfiring queries caused by over-reliance on one-dimensional corrections, and avoids unnecessary retraining. Our experiments demonstrate that SWatcher+ performs well even without the benefit of hindsight, outperforming periodic retraining even when the latter is given an optimal post hoc interval. Furthermore, SWatcher+ delivers reasonable performance even in challenging cases where the benefit margin is razor-thin.

There are several future directions to improve SWatcher+, e.g., monitoring/modeling update costs explicitly, batch-based processing of updates and counting queries, sketching for maintaining CEs under updates, assessing benefits of CE corrections using signals beyond estimated costs, etc., which we detail in [2]. While there is room for improvement, we believe that SWatcher+, along with its key principles—selective monitoring, active CE correction, and a focus on end-to-end running time rather than raw CE error metrics—offers a practical solution for deploying learned CE models and valuable insights to inform future advancements in this area.

References

References

  1. [1]Anonymous Author(s). 2026. [Codes] SWatcher+: A Holistic Approach to Deploying Learned Cardinality Estimators in a Dynamic Setting. https://anonymous.4open.science/r/Watcher-SIGMOD2027/README.md
  2. [2]Anonymous Author(s). 2026. [Full Version] SWatcher+: A Holistic Approach to Deploying Learned Cardinality Estimators in a Dynamic Setting. https://anonymous.4open.science/r/Watcher-SIGMOD2027/fullversion.pdf
  3. [3]N. Bruno, S. Chaudhuri, and L. Gravano. 2001. STHoles: A multidimensional workload-aware histogram. In Proc. 20th ACM SIGMOD Int. Conf. Management Data, 211–222.
  4. [4]Bailu Ding, Surajit Chaudhuri, Johannes Gehrke, and Vivek Narasayya. 2021. DSB: A decision support benchmark for workload-driven and traditional database systems. Proceedings of the VLDB Endowment 14, 13 (2021), 3376–3388.DOI
  5. [5]Bailu Ding, Surajit Chaudhuri, Johannes Gehrke, and Vivek Narasayya. 2021. DSB Github Repository: SPJ templates. https://github.com/microsoft/dsb/tree/main/query_templates_pg/spj_queries. Accessed: September 27, 2023.
  6. [6]Anshuman Dutt, Chi Wang, Azade Nazi, Srikanth Kandula, Vivek Narasayya, and Surajit Chaudhuri. 2019. Selectivity estimation for range predicates using lightweight models. Proc. VLDB Endow. 12, 9 (May 2019), 1044–1057. doi:10.14778/3329772.3329780DOI
  7. [7]The PostgreSQL Global Development Group. 2026. PostgreSQL: Write-Ahead Logging (WAL). https://www.postgresql.org/docs/current/wal-intro.html. Accessed: 2026-05-11.
  8. [8]Han, Yuxing and Wu, Ziniu and Wu, Peizhi and Zhu, Rong and Yang, Jingyi and Liang, Tan Wei and Zeng, Kai and Cong, Gao and Qin, Yanzhao and Pfadler, Andreas and Qian, Zhengping and Zhou, Jingren and Li, Jiangneng, and Cui, Bin. 2022. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. VLDB 15, 4 (2022).
  9. [9]S. Hasan, S. Thirumuruganathan, J. Augustine, N. Koudas, and G. Das. 2020. Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries. In Proc. 39th ACM SIGMOD Int. Conf. Management Data, 1035–1050.DOI
  10. [10]Mike Heddes, Igor Nunes, Tony Givargis, and Alex Nicolau. 2024. Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries. Proc. ACM Manag. Data 2, 3, Article 129 (May 2024), 26 pages. doi:10.1145/3654932DOI
  11. [11]B. Hilprecht, A. Schmidt, M. Kulessa, A. Molina, K. Kersting, and C. Binnig. 2019. DeepDB codebase. https://github.com/DataManagementLab/deepdb-public/tree/master. Accessed: 2026-04-13.
  12. [12]B. Hilprecht, A. Schmidt, M. Kulessa, A. Molina, K. Kersting, and C. Binnig. 2019. DeepDB: learn from data, not from queries! Proc. VLDB Endow. 13, 7 (2019), 992–1005.
  13. [13]Xiao Hu, Yuxi Liu, Haibo Xiu, Pankaj K. Agarwal, Debmalya Panigrahi, Sudeepa Roy, and Jun Yang. 2022. Selectivity Functions of Range Queries are Learnable. In SIGMOD (Philadelphia, PA, USA) (SIGMOD ’22), 959–972.
  14. [14]Inc IMDB.com. 2019. IMDB. https://www.imdb.com/. Accessed: 2026-05-11.
  15. [15]Paul Jaccard. 1901. Etude de la distribution florale dans une portion des Alpes et du Jura. Bulletin de la Societe Vaudoise des Sciences Naturelles 37 (01 1901), 547–579. doi:10.5169/seals-264650
  16. [16]Kyoungmin Kim, Jisung Jung, In Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. 2022. Learned Cardinality Estimation: An In-depth Study. In Proceedings of the 2022 International Conference on Management of Data (Philadelphia, PA, USA) (SIGMOD ’22). Association for Computing Machinery, New York, NY, USA, 1214–1227. doi:10.1145/3514221.3526154DOI
  17. [17]Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. 2019. Job-light Workload. https://github.com/andreaskipf/learnedcardinalities/blob/master/workloads/job-light.sql. Accessed: 2026-05-11.
  18. [18]Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. 2019. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR. www.cidrdb.org.
  19. [19]Meghdad Kurmanji and Peter Triantafillou. 2023. Detect, Distill and Update: Learned DB Systems Facing Out of Distribution Data. Proc. ACM Manag. Data 1, 1, Article 33 (may 2023), 27 pages. doi:10.1145/3588713DOI
  20. [20]Kukjin Lee, Anshuman Dutt, Vivek Narasayya, and Surajit Chaudhuri. 2023. Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server. Proc. VLDB Endow. 16, 11 (July 2023), 2871–2883. doi:10.14778/3611479.3611494
  21. [21]Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2015. How good are query optimizers, really? Proc. VLDB Endow. 9, 3 (Nov. 2015), 204–215. doi:10.14778/2850583.2850594DOI
  22. [22]Viktor Leis, Bernhard Radke, Andrey Gubichev, Alfons Kemper, and Thomas Neumann. 2017. Cardinality Estimation Done Right: Index-Based Join Sampling. In Cidr.
  23. [23]Beibin Li, Yao Lu, and Srikanth Kandula. 2022. Warper: Efficiently Adapting Learned Cardinality Estimators to Data and Workload Drifts. In Proceedings of the 2022 International Conference on Management of Data.DOI
  24. [24]Beibin Li, Yao Lu, Chi Wang, and Srikanth Kandula. 2021. Cardinality Estimation: Is Machine Learning a Silver Bullet? In AIDB. https://www.microsoft.com/en-us/research/publication/cardinality-estimation-is-machine-learning-a-silver-bullet/
  25. [25]Pengfei Li, Wenqing Wei, Rong Zhu, Bolin Ding, Jingren Zhou, and Hua Lu. 2023. ALEC: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads. Proc. VLDB Endow. 17, 2 (Oct. 2023), 197–210. doi:10.14778/3626292.3626302DOI
  26. [26]R. J. Lipton, J. F. Naughton, and D. A. Schneider. 1990. Practical selectivity estimation through adaptive sampling. In Proc. 9th ACM SIGMOD Int. Conf. Management Data, 1–11.
  27. [27]Jie Liu, Wenjiang Dong, Qingqing Zhou, and Dong Li. 2021. Fauce: fast and accurate deep ensembles with uncertainty for cardinality estimation. Proc. VLDB Endow. 14, 11 (July 2021), 1950–1963. doi:10.14778/3476249.3476254DOI
  28. [28]Ryan Marcus, Parimajan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Alizadeh, and Tim Kraska. 2021. Bao: Making Learned Query Optimization Practical. In Proceedings of the 2021 International Conference on Management of Data (Virtual Event, China) (SIGMOD ’21). Association for Computing Machinery, New York, NY, USA, 1275–1288. doi:10.1145/3448016.3452838DOI
  29. [29]R. Marcus, P. Negi, H. Mao, C. Zhang, M. Alizadeh, T. Kraska, O. Papaemmanouil, and N. Tatbul. 2019. Neo: A learned query optimizer. 12, 11 (2019), 1705–1718.DOI
  30. [30]R. Marcus and O. Papaemmanouil. 2018. Deep reinforcement learning for join order enumeration. In aiDM. 1–4.DOI
  31. [31]Guido Moerkotte, Thomas Neumann, and Gabriele Steidl. 2009. Preventing bad plans by bounding the impact of cardinality estimation errors. Proceedings of the VLDB Endowment 2, 1 (2009), 982–993.DOI
  32. [32]Magnus Müller, Lucas Woltmann, and Wolfgang Lehner. 2023. Enhanced Featurization of Queries with Mixed Combinations of Predicates for ML-based Cardinality Estimation. In Proceedings 26th International Conference on Extending Database Technology, EDBT 2023, Ioannina, Greece, March 28–31, 2023, Julia Stoyanovich, Jens Teubner, Nikos Mamoulis, Evaggelia Pitoura, Jan Mühlig, Katja Hose, Sourav S. Bhowmick, and Matteo Lissandrini (Eds.). OpenProceedings.org, 273–284. doi:10.48786/EDBT.2023.22DOI
  33. [33]Satoshi Nagayasu. 2023. pg_hint_plan. https://github.com/ossc-db/pg_hint_plan. Accessed: September 27, 2023.
  34. [34]Parimajan Negi, Ryan Marcus, Andreas Kipf, Hongzi Mao, Nesime Tatbul, Tim Kraska, and Mohammad Alizadeh. 2021. Flow-loss: learning cardinality estimates that matter. Proc. VLDB Endow. 14, 11 (July 2021), 2019–2032. doi:10.14778/3476249.3476259DOI
  35. [35]P. Negi, R. Marcus, H. Mao, N. Tatbul, T. Kraska, and M. Alizadeh. 2020. Cost-Guided Cardinality Estimation: Focus Where it Matters. In Proc. 36th Annu. IEEE Int. Conf. Data Eng. IEEE, 154–157.DOI
  36. [36]Parimajan Negi, Ziniu Wu, Andreas Kipf, Nesime Tatbul, Ryan Marcus, Sam Madden, Tim Kraska, and Mohammad Alizadeh. 2023. Robust Query Driven Cardinality Estimation under Changing Workloads. Proc. VLDB Endow. 16, 6 (feb 2023), 1520–1533. doi:10.14778/3583140.3583164
  37. [37]Y. Park, S. Zhong, and B. Mozafari. 2020. Quicksel: Quick selectivity learning with mixture models. In Proc. 39th ACM SIGMOD Int. Conf. Management Data., 1017–1033.DOI
  38. [38]V. Poosala, P. J. Haas, Y. E. Ioannidis, and E. J. Shekita. 1996. Improved histograms for selectivity estimation of range predicates. ACM Sigmod Record 25, 2 (1996), 294–305.
  39. [39]V. Poosala and Y. E. Ioannidis. 1997. Selectivity estimation without the attribute value independence assumption. In VLDB, Vol. 97. Citeseer, 486–495.
  40. [40]Silvan Reiner and Michael Grossniklaus. 2023. Github repository for JGMP. https://github.com/dbis-ukon/jgmp. Accessed: March 27, 2025.
  41. [41]Silvan Reiner and Michael Grossniklaus. 2023. Sample-Efficient Cardinality Estimation Using Geometric Deep Learning. Proc. VLDB Endow. 17, 4 (Dec. 2023), 740–752. doi:10.14778/3636218.3636229DOI
  42. [42]Diogo R. R. Z. R. Z. H. Z. ?
  43. [43]Microsoft SQL Server. 2025. Cardinality estimation (CE) feedback. https://learn.microsoft.com/en-us/sql/relational-databases/performance/intelligent-query-processing-cardinality-estimation-feedback?view=sql-server-ver16. Accessed: Sep 18, 2025.
  44. [44]U. Srivastava, P. J. Haas, V. Markl, M. Kutsch, and T. M. Tran. 2006. Isomer: Consistent histogram construction using query feedback. In Proc. 22th Annu. IEEE Int. Conf. Data Eng. 39–39.DOI
  45. [45]Michael Stillger, Guy M. Lohman, Volker Markl, and Mokhtar Kandil. 2001. LEO - DB2’s Learning Optimizer. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB ’01). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 19–28.
  46. [46]Jeffrey Tao, Natalie Maus, Haydn Jones, Yimeng Zeng, Jacob R. Gardner, and Ryan Marcus. 2025. Learned Offline Query Planning via Bayesian Optimization. Proc. ACM Manag. Data 3, 3, Article 179 (June 2025), 29 pages. doi:10.1145/3725316DOI
  47. [47]Xiaoying Wang, Changbo Qu, Weiyuan Wu, Yanniang Wang, and Qingqing Zhou. 2021. Are we ready for learned cardinality estimation? Proc. VLDB Endow. 14, 9 (May 2021), 1640–1654. doi:10.14778/3461535.3461552DOI
  48. [48]Peizhi Wu and Gao Cong. 2021. A unified deep model of learning from both data and queries for cardinality estimation. In Proceedings of the 2021 International Conference on Management of Data. 2009–2022.DOI
  49. [49]Peizhi Wu and Zachary G. Ives. 2024. Modeling Shifting Workloads for Learned Database Systems. Proc. ACM Manag. Data 2, 1, Article 38 (mar 2024), 27 pages. doi:10.1145/3639293DOI
  50. [50]Peizhi Wu, Haoshu Xu, Ryan Marcus, and Zachary G. Ives. 2025. A Practical Theory of Generalization in Selectivity Learning. Proc. VLDB Endow. 18, 6 (Aug. 2025), 1811–1824. doi:10.14778/3725688.3725708DOI
  51. [51]Ziniu Wu, Ryan Marcus, Zhenghen Chun Liu, Parimanjan Negi, Vikram Nathan, Pascal Pfeil, Gaurav Saxena, Mohammad Rahman, Balakrishnan Narayanaswamy, and Tim Kraska. 2024. Stage: Query Execution Time Prediction in Amazon Redshift. arXiv:2403.02286 [cs.DB] https://arxiv.org/abs/2403.02286
  52. [52]Haibo Xie, Pankaj K Agarwal, and Jun Yang. 2024. PAQO: Penalty-aware robust plan selection in query optimization. Proceedings of the VLDB Endowment 17, 13 (2024).
  53. [53]Zhongheng Yang, Wei-Lin Chiang, Sifei Luan, Gautam Mittal, Michael Luo, and Ion Stoica. 2022. Balsa: Learning a Query Optimizer Without Expert Demonstrations. 931–944. doi:10.1145/3514221.3517885DOI
  54. [54]Zhongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. 2020. NeuroCard: one cardinality estimator for all tables. Proceedings of the VLDB Endowment 14, 1 (2020), 61–73.
  55. [55]Z. Yang, E. Liang, A. Kamsetty, C. Wu, Y. Duan, X. Chen, P. Abbeel, J. M. Hellerstein, S. Krishnan, and I. Stoica. 2019. Codebase of Naru. https://github.com/naru-project/naru/tree/master. Accessed: 2026-04-13.
  56. [56]Z. Yang, E. Liang, A. Kamsetty, C. Wu, Y. Duan, X. Chen, P. Abbeel, J. M. Hellerstein, S. Krishnan, and I. Stoica. 2019. Deep unsupervised cardinality estimation. Proc. VLDB Endow. 13, 3 (2019), 279–292.DOI
  57. [57]Zixuan Yi, Yao Tian, Zachary G. Ives, and Ryan Marcus. 2024. Low Rank Approximation for Learned Query Optimization. In Proceedings of the Seventh International Workshop on Exploiting Artificial Intelligence Techniques for Data Management (Santiago, AA, Chile) (aiDM ’24). Association for Computing Machinery, New York, NY, USA, Article 4, 5 pages. doi:10.1145/3663742.3663974
  58. [58]Rong Zhu, Wei Chen, Bolin Ding, Xingguang Chen, Andreas Pfadler, Ziniu Wu, and Jingren Zhou. 2023. Lero: A Learning-to-Rank Query Optimizer. Proc. VLDB Endow. 16, 6 (Feb. 2023), 1466–1479. doi:10.14778/3583140.3583160DOI
  59. [59]Rong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng, Andreas Pfadler, Zhengping Qian, Jingren Zhou, and Bin Cui. 2020. FLAT: fast, lightweight and accurate method for cardinality estimation. arXiv preprint arXiv:2011.09022 (2020).arxiv.org/abs/2011.09022

Paper details

vlnc:W_ar7772r4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents