Cardinality Tomography with Context-Conditioned Error Atoms

The pattern is cross-domain structural transfer: transfer network tomography—additive link metrics, path measurements, identifiability as row-space membership, and probe design—to cardinality feedback. Reviewers may remember the testable identifiability perspective, “which parts of runtime feedback can in principle be inferred,” and the use of a posterior regret gate for replanning. Even with limited numerical gains, this framework and gate could be citable contributions. This is only a possibility requiring experimental confirmation, not an established result.

Runtime-feedback methods—POP, Perron et al.’s reoptimization and LEO—either correct only observed subplans or apply heuristic corrections with context-free per-predicate factors. They do not perform joint credit assignment over overlapping observations or provide uncertainty. We propose Cardinality Tomography: for a connected subset S of query q, model log(card_true/card_est) as the sum of query-local edge atoms θ_{q,e} plus heavy-tailed noise. Filter context is fixed within the same query, so filter–join interactions are absorbed into the atoms. Across queries, a three-level hierarchical prior—edge; edge × filtered-side table; edge × adjacent-table filter signature—provides partial pooling. Each observation adds one row to a Kalman/recursive-ridge update, with a target update time below one millisecond. Empty results or truncated probes are handled as censored Tobit observations. Trust a correction only when the target subset’s row lies in the observed row space and is identifiable; otherwise fall back to the native estimate. Replanning is controlled by a posterior-sampled regret gate, and probes are selected by plan-level value of information. Planned PostgreSQL/DuckDB evaluation covers JOB, CEB, STATS-CEB, DSB and their drift variants. Internal review identifies a central risk: remaining mid-query decisions mostly involve unobserved edges, so gains may be small. The Week 1 offline kill experiment is therefore decisive. There are no experimental results; everything above is a hypothesis to be tested.

Cardinality-estimation errors dominate plan quality. Learned cardinality estimation (CE) is fragile under data drift, and retraining is expensive. Runtime feedback can bypass the assumption that estimates must be accurate before execution, but existing approaches treat observations as caches, training labels or per-predicate adjustments rather than interpreting overlapping observations jointly. Filter–join correlation is the main error source on JOB/STATS-CEB/DSB and can invalidate context-free factors. The target is a low-overhead path, without a GPU or retraining, that protects tail latency and limits regressions. However, “never interpreted jointly” is inaccurate: ISOMER and SeqMaxEnt already impose joint consistency on overlapping feedback. Differentiation must be narrowed to the points below.

Experts usually expect additive log-error models to fail under filter–join correlation, and treat observations as caches, labels or per-predicate factors. The shift here makes the query itself the atom’s context: filter context is constant within the query, so additivity need hold only across subsets of that query. Cross-query transfer becomes a hierarchical prior over query-local atoms rather than an assumption. However, this shift exposes a weakness: atoms for unobserved edges come only from the prior or probes; otherwise, the posterior reduces to a Bayesian version of LEO. Internal review calls this a fatal risk, and we agree it is the most likely point at which the idea will be falsified.

1. Additive atom model: r_q(S)=Σ_{e∈E(S)} θ_{q,e}+ε_S. Following the AC’s recommendation, node atoms for base-table filters must also be included, and the necessity of interaction terms such as edge × co-joined filtered table must be tested. Report within-query non-additive residuals directly.
2. Hierarchical prior: θ_{q,e} ~ N(μ_{e,c(q,e)}, τ²_type), with c at three context levels: edge; edge × filtered-side table; edge × adjacent-table filter signature. Unseen contexts shrink toward coarser levels.
3. Online posterior update: each observation (S, true size) adds a row to incidence matrix A, followed by a Kalman/recursive-ridge update costing O(|E(S)|²). For an unobserved S', output native×exp(A_S' mean), with variance A_S' Σ A_S'^T.
4. Noise and non-additivity: use per-subset Student-t noise, implemented with Huber/IRLS. Identifiability check: if A_S' is not in the row space of observed rows, use only the prior-mean component and report large variance; DP falls back to the native estimate.
5. Probe observations: prefer budget-limited, early-terminated exact joins or wander-join-style join sampling. Restrict hash-correlated sampling to single-key joins; the AC notes it is invalid for multi-key and cyclic joins. Handle empty or truncated results by moment-matched truncated-Gaussian Tobit updates, never as 0.
6. Mid-query replanning: update the posterior at a breaker, then rerun DP for all subsets with corrected estimates. Switch only when expected gain under posterior samples exceeds switching cost plus a margin, using a posterior-sampled regret gate.
7. Probe selection: greedily choose by expected change in plan cost, or value of information; use D-optimal design as an ablation baseline.
8. Cross-query update: after a query completes, update μ using its atoms’ posteriors, with exponential forgetting for drift.

Use PostgreSQL and DuckDB, primarily on a 64-core CPU machine without a GPU. Offline: enumerate true cardinalities of connected subsets, fit different keying schemes, and simulate the online arrival of 1–3 observations. Online: first replay plans through pg_hint_plan, then integrate a mid-query breaker hook. An exact-subplan baseline with the same probe budget is mandatory. Repeat the study over a strong base estimator, such as LpBound or learned CE, so gains can be attributed to joint attribution rather than probing.

• datasets: STATS-CEB; JOB and CEB (IMDB), including CEB random-template splits; DSB with varied parameters; drifting STATS-CEB with NeurBench-style inserts and deletes.
• baselines: Native PostgreSQL and DuckDB; faithfully implemented LEO with local/join per-predicate multiplicative factors and a persistent catalog; ISOMER/maximum-entropy consistent feedback with identical feedback inputs; exact-subplan reoptimization in the Perron/POP style, including an equal-probe-budget version; a template-indexed cardinality cache; a gradient-boosted residual model and FactorJoin fine-tuned under drift; pessimistic LpBound.
• metrics: Held-out explained variance of log-error on unobserved subsets by keying scheme; P-error and Q-error on unobserved subsets; end-to-end P50/P99 latency and per-query regression counts and magnitudes; update time per observation; posterior coverage/calibration, including censored probes; proportion of empty/truncated probes, probe cost and probe error, reported separately; fraction and error of subsets marked unidentifiable; fraction of subsets required by remaining DP decisions that lie in the observed row space.
• ablations: Keying: edge only, edge × filtered table, edge × filter signature, hierarchical query-local; inclusion of node/filter atoms and interactions; joint attribution vs. independent per-observation assignment, isolating the added value of credit assignment; propagation to unobserved subsets on/off; Tobit vs. naively setting results to zero; uniform 1% sampling vs. correlated sampling vs. bounded exact probes; identifiability gate on/off; VOI vs. D-optimal vs. random probes; posterior-sampled switching gate vs. a fixed threshold; forgetting rate; Huber vs. squared loss.
• expected: Unverified expectations: gains come mainly from within-query inference and are concentrated on queries with filter–join correlation; the target is P-error at least 2x lower than exact-subplan feedback and LEO. On held-out templates and ad hoc streams, gains are expected to shrink to the within-query component, which will be reported accurately. Target update time is below 1 ms. Strong base estimators have smaller, less structured residuals, so gains are likely to diminish. The AC regards 2x as optimistic; a more realistic outcome is better P-error with very little latency improvement. Latency, rather than P-error, should be the main result.
• Falsification criteria: In the Week 1 offline study, terminate if hierarchical query-local atoms explain less than 50% of log-error variance on unobserved JOB/STATS-CEB subsets, or improve by less than 15 percentage points over LEO-style context-free factors. Also terminate if, when simulating an already-executed prefix of a native plan—observing prefix subsets and predicting subsets needed by remaining DP decisions—the posterior cannot outperform exact-subplan caching and LEO. Terminate as well if end-to-end gains over exact-subplan feedback are not statistically significant on held-out-template splits.

1. Days 1–3: compute true cardinalities for all connected subsets of approximately 100 STATS-CEB and JOB queries, preferably reusing existing ground truth; this is expected to take 1–2 days on 64 cores.
2. Days 4–6: fit additive models under the four keying schemes with node atoms, plus LEO per-predicate factors. Report held-out explained variance by subset, query and held-out template, and report within-query non-additive residuals directly.
3. Days 7–9: after a native plan’s execution prefix, quantify the fraction of subsets needed by remaining DP decisions that lies in the observed row space. If this fraction is very low, reassess the claim of 2x P-error improvement first.
4. Days 10–13: simulate online arrivals of 1–3 observations per query and compare P-error with LEO, ISOMER-style inference and exact-subplan methods, including equal-probe-budget comparisons.
5. Day 14: characterize probe quality: empty-result rates under uniform and hash-correlated sampling, separating single-key from multi-key joins, and calibration of Tobit updates. Then apply the kill criterion. If it passes, begin pg_hint_plan replay and subsequently integrate a breaker hook.

• The edges involved in remaining mid-query decisions are all unobserved, so the posterior reduces to the cross-query prior—effectively Bayesian LEO—and within-query gains are small. The AC identifies this as fatal. → Quantify the fraction of identifiable subsets in Week 1. Use a VOI probe budget to obtain additional observations. If the fraction is too low, narrow the contribution to an identifiability framework plus regret gate, or redirect to a mainly cross-query setting.
• Edge-only atoms double-count base-table error, while an edge’s effective filter context varies across subsets, violating additivity. → Add node atoms and interactions and report non-additive residuals. Student-t noise and the identifiability gate limit harm, but may also cap gains.
• Hash-correlated sampling does not preserve an output fraction of approximately p for multi-key and cyclic joins, and most probes are truncated. → Use bounded exact-prefix execution or wander-join-style sampling and report the truncation rate. Tobit can ensure unbiasedness, not informativeness.
• Gains arise primarily from probes rather than attribution, and stronger base estimators reduce residuals. → Add equal-probe-budget baselines and experiments with strong base estimators.
• The work is close to LEO, ISOMER/SeqMaxEnt and the 2026 online-selectivity paper; the risk of being scooped is medium to high. → Read the 2026 paper carefully. The joint-vs.-independent ablation must show that credit assignment matters; otherwise do not pursue it as the main contribution.
• Canonicalizing filter signatures for complex predicates is cumbersome; cross-query repeatability in public benchmarks differs from real recurring workloads. → Initially support common predicate types only and fall back to coarser levels for the rest. State accurately that ad hoc streams yield only within-query gains.

• Q: Query-local edge atoms cannot absorb filter–join correlation, because an edge’s effective filter context varies across subsets within the same query. A: Partly correct. Additivity is reasonable only with fixed context, and there is currently no evidence that it holds within a query. Therefore, Week 1 directly measures non-additive residuals and adds interactions and node atoms. Large residuals trigger the kill criterion.
• Q: Edge-only atoms repeatedly count base-table estimation errors. Those errors enter every subset containing that table, independently of its degree. A: Agreed; this is a model-specification flaw. Add node atoms and report the required edge-only vs. edge+node ablation.
• Q: All remaining mid-query decisions involve unobserved edges, so within-query joint attribution does not help. A: This is the most serious objection, and we cannot refute it theoretically. It can only be tested empirically: quantify the fraction of subsets for remaining decisions that lies in the observed row space, and actively supplement observations through VOI probes. If the fraction is low, within-query gains may indeed be small or nonexistent, requiring a narrower claim.
• Q: It is wrong to say overlapping observations have never been interpreted jointly. ISOMER already enforces joint consistency, and SeqMaxEnt also treats feedback as linear measurements. A: Correct; that statement will be removed. Actual differentiation is narrowed to a Bayesian log-error posterior and calibrated uncertainty, an identifiability gate, censored probes, and plan-level VOI and regret gates. Direct comparison with ISOMER using the same feedback must show that these differences produce real gains.
• Q: Hash-correlated sampling does not preserve an output fraction of approximately p in multi-key joins. Most multiway-join probes on JOB/STATS will be truncated and uninformative. A: Correct. Replace probes with bounded exact-prefix execution or join sampling, restricting hash-correlated sampling to single-key joins. Report truncation rates and probe cost separately. If too few observations are informative, the probing approach is infeasible.
• Q: Gains may come from probes rather than attribution—the AC’s kill question. A: Answer through an equal-probe-budget exact-subplan baseline and the joint-vs.-independent ablation. Gains may indeed be small, and we will report them accurately.

Suitable for query-optimization research at VLDB/SIGMOD; the AC gives venue_fit 4. This requires end-to-end PostgreSQL/DuckDB integration and latency, rather than P-error alone, as the primary result. However, the overall internal AC verdict is borderline, with differentiation 2 and realism 2; the audience is real but fairly small. Commit the subsequent months only if the Week 1 kill experiment passes and the fraction of identifiable subsets is sufficiently high.