Switching Between Correlation Models When a Database's Data Drifts

A database query optimizer has to guess how many rows each part of a query will return before it runs the query. For decades it has made that guess by assuming that columns are independent: if 10% of cars are red and 10% are electric, it assumes 1% are red electric cars. On real, skewed data this assumption fails badly, and the errors multiply across joins. Newer estimators model the correlations directly. Some fit a Bayesian network, a compact graph of which columns depend on which. Others use neural networks over per-column histograms, or adapt from recent query results. They improve estimates a great deal on static data. What they handle poorly is a specific kind of change. When the relationship between columns shifts while each column's own distribution stays the same, per-column statistics do not move at all. A model that has not seen enough of the new relationship then keeps trusting its old structure, or falls back to something too simple.

We propose to treat this as a sequential model-selection problem and to solve it with Grünwald's switching method. The switching method is a way of shifting belief among candidate models over time so that a complex model takes over as soon as the data supports it. A plain Bayesian average waits much longer. Here the candidates are density models of increasing correlation complexity, from full independence up to a rich Bayesian network, each maintained over both a long and a short history window. We score them on the log-likelihood of newly inserted tuples. That signal arrives with every insert and needs no executed-query feedback. The result is an estimator whose adaptation speed after a correlation shift can be analyzed and measured, and whose one free prior (how often we expect the best model to change) we can test for sensitivity directly.

Core Claim

Three facts from the literature combine into one testable claim. First, Grünwald shows in The Catch-Up Phenomenon in Bayesian Inference that static Bayesian model averaging gives a more complex, correct model too little weight for too long. Simpler wrong models win early on, and a switch distribution borrowed from expert-tracking algorithms removes this lag without losing consistency. Second, BayesCard updates Bayesian-network parameters in milliseconds as data changes. Its structure and its effective prior still reflect the past, so immediately after a shift the new regime has almost no effective sample size, which is exactly the setting where catch-up lag occurs. Third, ALECE adapts to changing data by refreshing single-column histograms that feed an attention network. That mechanism is blind by construction to changes in correlation that leave every marginal fixed. Correlated attributes of the kind documented in Multi-Dimensional Substring Selectivity Estimation can change their joint pattern in exactly this way.

Our claim is that a switch distribution over a small family of correlation models, fed by tuple log-likelihoods from the insert stream, will recover accurate cardinality estimates after marginal-preserving correlation drift in far fewer inserts than two alternatives: incremental Bayesian-network updating, and histogram-refresh neural estimators. It will also give up little accuracy under stationary data. The contribution is not a new density model. It is the adaptation rule, the diagnostic benchmark that isolates correlation-only drift, and a measurement of catch-up lag in a database setting where it has never been studied.

Research Program

The estimator keeps a set of "experts," each a density model over a table or a join-connected group of tables. The complexity ladder has three rungs. The bottom rung is the independence model, which reproduces what PostgreSQL-style per-column statistics compute. The middle rung is a tree-structured Bayesian network in the spirit of the lightweight junction-tree models of Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions. The top rung is a BayesCard-style ensemble. Each rung is maintained over two horizons: all data since the last structure build, and a recent window of inserts. This gives six experts. They are cheap because BayesCard-type parameter updates are incremental, and because the recent-window experts rebuild their structure only in the background.

For every inserted tuple $x_t$, each expert $k$ assigns a predictive probability $p_k(x_t)$. The combined weights follow the fixed-share form of the switch distribution:

$$w_{t+1}(k) \propto \alpha \cdot \tfrac{1}{K} + (1-\alpha)\, w_t(k)\, p_k(x_t),$$

where $w_t(k)$ is expert $k$'s weight before tuple $t$, $K$ is the number of experts, and $\alpha$ is the meta-prior switching rate, meaning the prior probability that the best expert changes at any given step. Cardinality estimates come from the weight-averaged selectivity. The alternative is to use the top-weighted expert alone, and we compare both. Deletes and updates enter as removals and re-insertions. When executed-query feedback is available, the true cardinalities can serve as a second, delayed loss stream. We treat that as an optional add-on, not the core, so that we can separate what the unsupervised insert signal buys by itself.

Two analyses accompany the build. The first measures catch-up lag directly. After a shift at time $t_0$, we count the inserts needed until the estimator's median Q-error on queries that touch the changed columns returns within a factor of 1.5 of an oracle model trained on post-shift data only. We compare this count for the switch distribution, plain Bayesian model averaging, and the single best static expert. The second studies prior sensitivity. Grünwald leaves open how sensitive switching is to its meta-prior, so we sweep $\alpha$ over five orders of magnitude and report how catch-up lag and stationary-regime accuracy trade off. A flat curve would mean the method is safe to deploy untuned. A sharp one would mean $\alpha$ must be tied to a measured drift rate.

Baselines

The naive reference point is PostgreSQL's default estimator, which uses single-column histograms and assumes independence. The file gives no Q-error for it under drift, but ALECE reports that its correlation-aware plans run up to 2.7× faster end to end across STATS, JOB-light and TPC-H. Beating it is a floor, not a result.

The most direct competitor is incremental BayesCard, which fits Bayesian-network ensembles and updates their parameters as data arrives. It is the natural choice because our top expert is essentially BayesCard, so any gain must come from the switching rule. BayesCard reports a 95th-percentile Q-error of about 2.05 on CENSUS, against about 178 for DeepDB and about 174 for FLAT, and a 13.3% end-to-end improvement on IMDB, near a stated maximum of 14.2%. We will run it with the same insert stream and give it the same background compute budget for structure relearning that our recent-window experts receive, in two variants: periodic full rebuild, and sliding-window rebuild. Beating it means a lower catch-up lag at matched compute with no worse stationary Q-error.

The strongest drift-adaptive competitor is FLAIR, from In-Context Adaptation to Concept Drift for Learned Database Operations. FLAIR adapts through a forward pass over a first-in-first-out memory of recently executed queries and their true cardinalities, using a model meta-trained on synthetic priors. It reports a 22.5% reduction in geometric-mean Q-error, up to 5.2× faster adaptation than DeepDB, ALECE and DDUp, and up to 1.9× end-to-end speedup in PostgreSQL. Its signal comes from query feedback, so it can in principle notice correlation drift that histograms miss. That makes it the real competitor on our question. We will give it the same query stream and memory size, and our feedback-free variant will see no query results at all. Beating it means matching or beating its post-shift Q-error trajectory without using query feedback, or clearly beating it once both use feedback. Whether FLAIR's code is available is not stated in the file. If it is not, we will reimplement its memory protocol on top of ALECE's featurizer and label the result as a reimplementation.

We also run ALECE and CEDA. CEDA uses adversarial domain adaptation and reports mean Q-error falling from 8.36 to 4.87 and 99th-percentile Q-error from 93.00 to 17.61 on JOB-light workload shift. Both represent histogram- and workload-alignment approaches. The key ablation replaces the switch distribution with plain Bayesian model averaging over the same six experts, with $\alpha = 0$. A second ablation removes the short-horizon experts, which separates "switch complexity" from "switch recency."

Why not just…?

Why not just use exponential forgetting in BayesCard's parameter updates? Forgetting makes parameters track recent data. It does not change which columns the network connects, and after a correlation shift the old structure is often the error itself. It is also a close cousin of our short-horizon experts, so this is a real threat. The sliding-window BayesCard baseline at matched rebuild compute settles it. If that baseline matches our catch-up lag, the switching layer adds nothing and we will say so.

Why not just detect drift and retrain? Univariate detectors such as the incremental Kolmogorov-Smirnov test of Fast Unsupervised Online Drift Detection Using Incremental Kolmogorov-Smirnov Test are fast. They examine one column at a time, however, so they cannot fire on marginal-preserving drift, and our benchmark checks this directly. Multivariate classifier tests such as Sequential Covariate Shift Detection Using Classifier Two-Sample Tests can fire. Detect-then-retrain still leaves the latency gap that FLAIR documents, where queries run on bad plans until the rebuild finishes. We include a classifier-test-triggered BayesCard rebuild as a baseline. Our method should win on the area under the post-shift Q-error curve, although the detector may tie us on final accuracy.

Why not just rely on FLAIR's query feedback? Feedback arrives only for queries that are actually executed. It covers regions of the data the workload happens to touch, and it lags behind inserts. Tuple likelihoods cover every insert immediately. The experiment that decides this runs workloads that rarely touch the drifted columns until after the shift, and then suddenly do. If FLAIR still adapts as fast, the insert signal is redundant.

Proposed Experiments

The central benchmark is marginal-preserving correlation drift built on real data. On CENSUS and DMV, and on STATS and IMDB for joins, we take a correlated column pair and, from a chosen insert onward, stream tuples in which one column's values are shuffled within strata. This keeps every single-column histogram exactly fixed while destroying or rewiring the dependence. We also run the reverse direction, where correlation appears in previously independent columns, and a reverting schedule in which the shift oscillates, following Lee's observation that real drift fluctuates and reverts. For controlled sweeps, the CardinalityEstimationTestbed generator's --corr and --skew settings let us change correlation strength mid-stream at fixed marginals and at Zipfian skew levels like those Faloutsos describes. For contrast, we include ordinary marginal drift, where histogram-based methods should do well.

The metrics are median, 95th- and 99th-percentile Q-error over time, catch-up lag as defined above, estimation latency, update cost per insert, and end-to-end PostgreSQL execution time on JOB-light and STATS. The file reports no Q-error for any method under marginal-preserving correlation drift. The only reported drift numbers are the FLAIR, CEDA and ALECE figures above, and those were measured on their own drift protocols.

Three results would be decisive. First, histogram-refresh estimators such as ALECE should show no improvement after a marginal-preserving shift, because their inputs do not change. If they do improve, our framing of the gap is wrong. Second, the switch distribution should cut catch-up lag relative to plain model averaging by a large factor, and should match the best static expert within noise under stationary data. This is the direct test of whether Grünwald's result carries over to relational density models. Third, the $\alpha$ sweep should show a wide range of values that works well. If it shows instead that performance depends sharply on the meta-prior, prior sensitivity has simply moved up a level, and we would report that as the main finding.