Cardinality Tomography: Treat Runtime Observations as an Error-Attribution Problem

This follows the cross-domain structural transfer pattern, transferring network tomography’s “additive link metrics + path measurements + identifiability + probe design” to the query-optimization feedback loop. Reviewers may remember two aspects: an identifiability characterization of which join-edge errors can be uniquely recovered from subset-size observations, and the use of D-optimal design to choose subplans to execute or sample. Even if the numerical improvement is only a single-digit percentage, the framework could still be cited. This requires substantive identifiability results, rather than repackaging alone.

Runtime feedback usually corrects only the observed subplan: LEO-style methods store per-predicate adjustment factors, while Perron-style reoptimization uses only exactly observed subsets. We propose Cardinality Tomography. It assumes that, under the native estimator, the difference between log true cardinality and log estimated cardinality for subset S is approximately the sum of error atoms theta and phi for the join edges and base filters in S. Each observation (S, true size) is thus a row of linear measurements of latent variables. We maintain a linear-Gaussian posterior using recursive ridge/Kalman updates, with exponential forgetting for drift. Each update costs O(|atoms|^2), targeting completion within milliseconds. Corrected estimates propagate to all unobserved subsets and are reused across queries. Posterior variance has two uses: uncertainty-aware mid-query replanning gates, and selecting inexpensive probes by D-optimal or expected-plan-change criteria. Two central risks remain: filter–join correlation can violate additivity, and differentiation from LEO and ISOMER is narrow. The first phase and go/no-go criterion is therefore an offline additivity and identifiability study, followed by planned end-to-end PostgreSQL/DuckDB evaluation on STATS-CEB, JOB/CEB, DSB and NeurBench-style drift variants. There are currently no experimental results; all stated gains are hypotheses requiring validation.

Learned cardinality estimation is fragile under drift and unseen workloads, and retraining is expensive. Mid-query reoptimization uses only exactly observed subsets, does not learn across queries, and lacks a principled treatment of “when switching is worthwhile.” Existing feedback mechanisms have three gaps: (1) observations do not propagate to other subsets the optimizer will consider next; (2) they do not choose “what to observe”; (3) they cannot transfer across queries without retraining. Exact counting is inexpensive on a 64-core machine, making the stream of (subset, true size) observations almost free. What is missing is a way to use it without gradients or retraining and with uncertainty. This also matches the project constraints: millisecond overhead, no regression relative to the native optimizer, and minimal changes to PostgreSQL/DuckDB.

The field usually treats observed cardinalities as cache entries, as in LEO/Perron, or as training labels for a learned residual model. Viewing them as linear measurements of an additive log-error model—the network-tomography perspective—naturally raises the questions “which atoms are identifiable?” and “which subplans should be measured?” However, an experienced expert would expect this to work on foreign-key (FK) chains and fail under filter–join correlation, so the insight is only moderately non-obvious. Its value depends on whether offline experiments show additivity holds for enough subsets.

1. Error atoms and canonical keys: key theta_e by a canonical join-predicate pair and phi_f by a filter-predicate signature. Implement canonicalization in PostgreSQL/DuckDB, including alias resolution, predicate ordering and constant bucketing. The model is log true(S) - log est(S) = sum theta_e + sum phi_f + eps_S.
2. Hierarchical atom extension, addressing the filter–join-correlation objection: in addition to edge-only atoms, add filter-context-conditioned join atoms theta_{e|ctx}, with hierarchical shrinkage toward edge-only atoms. Fall back to coarser atoms when data is insufficient.
3. Online posterior: use a linear-Gaussian posterior, Kalman/recursive ridge, with prior variance by atom type—FK fan-out, M:N and so on—taken from historical error distributions. Each observation costs O(|atoms in S|^2) to update. Use exponential forgetting for drift and Huber loss to limit the effect of non-additive correlations.
4. Estimator hook: for any subset S', corrected estimate = native estimate * exp(A_S' * posterior mean), accompanied by posterior variance. Atoms with excessive variance fall back to the native estimate.
5. Uncertainty-aware mid-query replanning: update the posterior at a pipeline breaker and rerun dynamic programming (DP) for all unobserved subsets using corrected estimates. Switch only if expected gain exceeds switching cost plus an uncertainty margin, to control regressions.
6. Measurement design: candidate probes include early-terminated exact join counts and sample counts. Select them using greedy D-optimal or expected-plan-change/value-of-information criteria. For highly selective multiway joins, replace 1% uniform samples with correlated/join samples or early-terminated exact counts, and quantify probe error and cost separately.
7. Cross-query persistence: store atoms in a hash table with forgetting decay. Provide identifiability analysis through rank/condition-number analysis of the incidence matrix A, reporting which atoms are unidentifiable under the current observation set.
8. Plugin integration: use pg_hint_plan for plan replay and DuckDB’s extensible interface. The first version emphasizes offline replay; online mid-query switching is the second phase.

Use a single 64-core CPU machine, without a GPU. Replay PostgreSQL plans through pg_hint_plan and use DuckDB as the second engine. Construct templated streams, non-templated/ad hoc streams—CEB random templates and DSB with varied parameters—and drift streams with NeurBench-style inserts/deletes. First conduct an offline additivity study as the Phase 1 go/no-go, then online simulation, and finally end-to-end latency evaluation. Repeat each configuration, report variance and count regressions per query.

• datasets: STATS-CEB; JOB/CEB (IMDB); DSB; drift variants of STATS-CEB with NeurBench-style inserts/deletes.
• baselines: Native PostgreSQL and DuckDB estimates; faithfully implemented LEO with persistent per-predicate adjustment factors; exact-subplan cache + Perron-style reoptimization; ISOMER/maximum-entropy consistent-selectivity baseline; FactorJoin and NeuroCard fine-tuned after drift; a gradient-boosted residual model using observed cardinalities; pessimistic bounds from LpBound.
• metrics: P-error and Q-error on unobserved subsets; end-to-end P50/P90/P99 latency on drifting query streams; update time per observation; regressions relative to the native optimizer; posterior calibration/coverage; held-out explained variance R^2 of log-error; probe cost and probe error, reported separately.
• ablations: Edge-only vs. edge+filter vs. edge×filter-context hierarchical atoms vs. LEO per-predicate factors; propagation/joint inference vs. per-atom factor reuse alone, separating gain sources; with/without uncertainty-aware switching; greedy D-optimal vs. random probing; forgetting rate; Huber vs. squared loss; probe types: 1% uniform sample vs. join sample vs. early-terminated exact count; base-estimator strength: native PG vs. corrected PG vs. FactorJoin.
• expected: Hypotheses, not existing results: on templated drift streams, within approximately 10 queries after a drift event, unobserved-subset P-error is 1.5x to 2x lower than with an exact-subplan cache; end-to-end latency is 20–30% lower than with exact-subplan feedback. That number comes from the proposed templated-stream setting, which is favorable to the method; gains on ad hoc streams are expected to shrink considerably or disappear. Target update cost is below 1 ms, and performance without a GPU is expected to match fine-tuned FactorJoin. Gains are expected mainly on FK-chain joins, with limited improvements under strong filter–join correlation. A stronger base estimator is expected to reduce the gains.
• Falsification criteria: Stop or redirect if any criterion holds: (1) on JOB/STATS-CEB, held-out explained variance R^2 of log-error on unobserved subsets is below 0.5 or does not exceed LEO’s per-predicate-factor baseline; (2) even edge×filter-context hierarchical atoms produce no clear improvement; (3) there is no end-to-end gain over exact-subplan caching + LEO reoptimization; (4) atom reuse is too low on non-templated streams, cross-query gain is zero and within-query propagation also yields no benefit.

1. Days 1–3: obtain true cardinalities for every connected subset of 100 STATS-CEB/JOB queries. Reuse existing ground truth where possible; otherwise compute it offline on 64 cores, expected to take 1–2 days. Also export PostgreSQL’s native estimates for the corresponding subsets.
2. Days 3–4: implement atom canonicalization, using join pairs and filter signatures, and construct incidence matrix A. Report atom coverage, reuse rates and A’s rank/condition number as an initial identifiability assessment.
3. Days 4–7: fit the additive model by ridge regression and measure held-out R^2 on unobserved subsets and new queries sharing atoms. Also fit the edge×filter-context hierarchical variant and LEO’s per-predicate-factor baseline, comparing all three. This is the go/no-go point.
4. Days 7–10: simulate online arrivals, including synthetic drift, and compare P-error against exact-subplan caching. First implement Kalman recursion and measure time per update.
5. Days 10–12: replay plans through pg_hint_plan using corrected estimates. Measure latency and regressions on selected subset queries, initially assessing how P-error improvements translate into execution gains.
6. Days 12–14: summarize results and use kill_criterion to decide whether to continue, redirect—for example toward identifiability/measurement design—or stop. Also read the 2026 online linear-selectivity paper carefully and update the differentiation claims.

• Filter–join correlation makes log-error non-additive; atoms cannot be defined independently of co-occurring filters. The red team considers this the main error source on JOB/STATS. → Quantify this in Phase 1 by offline regression. Introduce edge×filter-context hierarchical atoms and shrinkage. Use Huber only as a fallback, not the primary solution. Stop under kill_criterion if R^2 misses the threshold.
• Differentiation from LEO, ISOMER and the 2026 online linear-selectivity work is too narrow, making the work incremental. → Implement LEO and maximum-entropy baselines faithfully; make identifiability theory and measurement design the main contributions; use ablations to separate propagation, probe design and uncertainty gating; read the 2026 paper early.
• Atoms are seldom reused on ad hoc workloads, eliminating cross-query gain; templated drift streams are favorable and may look constructed to favor the method. → Report non-templated streams too. Separate within-query propagation gains, including mid-query gains, from cross-query gains and report the method’s boundaries accurately.
• 1% uniform samples are unreliable for highly selective multiway joins, contaminating the posterior with probe error. → Use join/correlated samples or early-terminated exact counts. Model probe noise as observation-noise variance and quantify probe error and cost separately.
• Canonical keys are difficult for complex predicates such as LIKE, OR and expressions, leading to low coverage. → Initially restrict the scope to equality/range predicates and FK joins. Fall back to native estimates for predicates that cannot be canonicalized; measure and report coverage.
• Residual structure is weaker with strong base estimators, reducing gains; latency noise is high and a few queries dominate. → Ablate across several base estimators. Repeat runs and report per-query regression counts and confidence intervals. Use P-error as one of the more stable primary metrics.

• Q: LEO already turns observed cardinalities into per-predicate multiplicative adjustment factors, including local and join predicates, stores them in a persistent catalog and reuses them in later queries. These are “reusable error atoms.” Describing LEO as “exact subplan feedback” creates an unfair baseline. A: This objection is substantially correct and must be accepted. We will implement LEO faithfully from its paper, including per-predicate adjustment factors, as a main baseline and remove the claim “LEO = exact-subplan cache.” The remaining distinctions are joint additive inference—which can attribute a multi-edge subset observation to multiple atoms and propagate to unobserved subsets—posterior uncertainty, probe design and replanning gates. Whether these produce meaningful gains is an empirical question; the “propagation vs. factor reuse alone” ablation is designed to answer it. If gains are insignificant, the paper must shift toward identifiability analysis or be abandoned.
• Q: theta_e is keyed only by join-predicate pairs and shared across filter combinations, but the main PostgreSQL estimation errors on JOB, STATS-CEB and DSB arise from filter–join correlation, making theta_e depend on co-occurring filters. A: This is the central risk. The response has three steps: first measure by offline regression how much variance edge-only atoms explain; then introduce edge×filter-context hierarchical atoms; use Huber only for occasional outliers, since it cannot fix systematic bias. If R^2 remains below 0.5 after the hierarchical extension, stop under kill_criterion. There is no evidence yet that additivity holds on these benchmarks; experiments must answer that.
• Q: 1% sample probes are unreliable for highly selective multiway joins. The headline templated-stream comparison favors this method and does not test generalization. A: Agreed. Probes will use join samples or early-terminated exact counts, with probe error included as observation noise in the posterior and error/cost reported separately. Add non-templated/ad hoc streams—CEB random templates and DSB with varied parameters—and explicitly restrict the 20–30% figure to a hypothesis for templated drift streams. If ad hoc streams show no gain, report that boundary.
• Q: The source of the gains is unclear: LEO-style factor reuse, or Kalman updates and measurement design? A: Use a decomposition ablation: factor reuse alone, then add joint propagation, uncertainty gating and D-optimal probes incrementally. Compare with Perron-style reoptimization and ISOMER/maximum-entropy baselines under equal tuning and compute budgets. If most gains come from the first level, narrow the paper’s positioning accordingly.
• Q: The work overlaps with Selectivity Estimation for Linear Queries via Online Learning (2026), and risks being scooped. A: Only abstract-level evidence is available, so we cannot assert the extent of differentiation. In the first week, read it carefully and produce a distinction table covering the estimation target, native-estimator residuals vs. a feasible database region, end-to-end optimization evaluation and probe design. The risk of being scooped is real; completing identifiability and offline studies quickly may reduce it. Reposition if substantial overlap is found.

Suitable for optimizer and cardinality-estimation research at VLDB/SIGMOD, provided it delivers a working end-to-end PostgreSQL + DuckDB system, faithfully implemented strong baselines—LEO, ISOMER and Perron—and substantive identifiability/additivity analysis. If it is merely a LEO variant without clear theoretical or empirical differentiation, it is incremental and likely to be rejected; an analysis paper or short paper may be more appropriate. The current internal assessment is borderline: differentiation 2, realism 2, feasibility 4 and venue_fit 4.