NeuroCard: One Cardinality Estimator for All Tables

1 INTRODUCTION

• NeuroCard samples from joins instead of fully computing them, using precomputed key weights to preserve the join distribution.The weights are computed by dynamic programming; the method is described as linear in data size.Source: §1 · p. 2
• Lossless column factorization splits high-cardinality columns into lower-cardinality bit chunks for autoregressive modeling, reducing model size.The passage gives 100,000s or more distinct values as an example of columns that can cause model growth.Source: §1 · p. 2
• 8.5× maximum Q-error on JOB-light uses 4 MB, a 4.6× improvement over the previous state of the art.JOB-light contains 6 tables and basic filters.Source: §1 · p. 2
• On JOB-light-ranges, NeuroCard achieves up to 15–34× higher accuracy than previous solutions, including DeepDB, MSCN [15], and IBJS.Source: §1 · p. 2
• On 16-table JOB-M, NeuroCard offers 10× higher accuracy than conventional approaches with a 27 MB model.Source: §1 · p. 2
• A single deep autoregressive model captures correlations across schema joins without independence assumptions and can estimate queries over any subset of tables.The model learns the distribution across all tables in the schema.Source: §1 · p. 2

2 OVERVIEW OF NEUROCARD

• The schema and submitted queries are assumed acyclic, so the join schema can be treated as a tree.The passage notes that §4.2 discusses relaxations.Source: §2 · p. 2

2.1 Goals and Solutions

• NeuroCard learns the full outer join because it contains information needed for queries over subsets that an inner join may omit.The overview motivates one estimator partly because possible join templates grow exponentially with the number of tables.Source: §2.1 · p. 3
• Uniform samples from the full join avoid materializing it; dynamic programming computes join counts in linear time in database size.The passage reports 13 seconds for 6 tables in JOB-light and 4 minutes for 16 tables in JOB-M; sampling assumes indexes on join keys.Source: §2.1 · p. 3
• When a query omits tables, NeuroCard downscales estimates by the omitted tables' fanout so selectivity refers to the queried subset.The overview illustrates that failing to account for a missing table's fanout can change the estimated row count.Source: §2.1 · p. 3
• Deep autoregressive models estimate the full-join distribution while capturing correlations among columns without independence assumptions.NeuroCard applies Naru's approach to the full join and optimizes construction and inference for this setting.Source: §2.1 · p. 3

2.2 Putting It All Together

• Building the estimator prepares join indexes and count tables, then trains the autoregressive model on batches of sampled tuples.The sampler can fulfill batch requests in the background using multiple sampling threads.Source: §2.2 · p. 3
• At query time, Monte Carlo integration on the learned model and schema-subsetting adjustments produce cardinality estimates for joins with arbitrary range selections.Source: §2.2 · p. 3

3.1 Probabilistic Modeling of Tables

• Autoregressive factorization represents the joint distribution as conditional distributions, whereas independence assumptions can lose information about column correlations.Deep autoregressive models approximate these conditional distributions with compact neural networks.Source: §3.1 · p. 4

3.2 Naru: Deep Autoregressive Models as Cardinality Estimators

• Naru models tuples with a deep autoregressive network that predicts each column conditioned on prior columns, and estimates query probabilities by progressive sampling.NeuroCard applies this approach to the full outer join, using simple random samples to learn its distribution.Source: §3.2 · p. 4

3.3 Join Problem Formulation

• NeuroCard estimates join queries on any subset of schema tables by learning a fully autoregressive model over the full outer join.Its inference extends progressive sampling with column factorization and a fanout adjustment for schema subsetting.Source: §3.3 · p. 4, §3.2 · p. 4
• The supported formulation covers acyclic schemas and multi-way, multi-key equi-joins, with equality and range filters on discrete or numerical columns.Uncaptured joins can be estimated by combining single-table estimates with classical heuristics, at lower accuracy.Source: §3.3 · p. 4

3.4 Model architecture

• ResMADE embeds dictionary-encoded column IDs, passes them through masked residual blocks, and produces conditional-distribution logits.The masks enforce autoregressive ordering; wildcard skipping trains marginalization tokens for inference.Source: §3.4 · p. 5

4.1 Algorithm

• The sampler draws join keys using full-join occurrence weights, then looks up base-table content columns to construct each sampled tuple.After join counts are computed, sample generation is parallelizable while preserving the i.i.d. property.Source: §4.1 · p. 5
• O(|T1| + ··· + |TN|): bottom-up dynamic programming computes join counts in time linear in the total number of tuples across tables.The counts provide weights for top-down sampling through the join tree, producing simple random samples from the full join.Source: §4.1 · p. 5, §4 · p. 5

4.2 Comparison with other samplers

• Uniform, independent full-join samples rule out methods that violate either requirement; NeuroCard adapts the Exact Weight algorithm for full outer joins.The cited comparison notes that reservoir sampling scans the full join and produces dependent samples.Source: §4.2 · pp. 5–6

5 LOSSLESS COLUMN FACTORIZATION

• 128 MB to 250 KB (>500×): slicing a column value into N-bit subcolumns reduces the embedding space needed for a 10^6-value example.Each subcolumn requires an embedding matrix sized for at most 2^N values.Source: §5 · p. 6
• Autoregressive modeling captures correlations among factorized subcolumns, so the combination has no inherent information loss.Smaller N creates more subcolumns and can reduce statistical efficiency; in practice, lower-bit settings generally underperform higher ones by a nonsignificant margin.Source: §5 · p. 6
• Range filters on an original column are translated into conditional filters on its high- and low-bit subcolumns during inference.The low-bit range depends on the sampled high-bit value.Source: §5 · pp. 6–7

Schema subsetting

• A full-join model can misestimate a query restricted to an inner join, so NeuroCard uses indicator columns to constrain inference to tuples with partners in every queried table.In the example, the naive estimate is 3 rows instead of 2; constraining all three table indicators gives the correct count.Source: §6 · p. 7
• For queries omitting tables, NeuroCard scales down estimates by omitted-table fanouts, which account for tuple duplication introduced by the full join.Fanout values are added to sampled tuples on the fly; their lookup adds negligible overhead.Source: §6 · p. 7
• For multi-key joins, the method selects one downscaling key for each omitted table along its unique path to a queried table in the acyclic schema graph.The per-key fanout definition supports general equi-joins, including joins where both keys contain duplicates, without requiring PK-FK joins.Source: §6 · pp. 7–8
• Inference combines progressive sampling with virtual indicator and fanout columns, treating those columns like regular learned columns to handle schema subsetting.The model places indicators and then fanouts after content columns in its autoregressive ordering; early benchmarks favored this over placing virtual columns earlier.Source: §6 · pp. 7–8

7 EVALUATION

• NeuroCard outperforms the best prior methods by 4–34× in accuracy, with a maximum error of 8.5× on JOB-light.On JOB-light-ranges and JOB-M, it achieves orders of magnitude higher accuracy than prior approaches.Source: §7 · p. 8
• A few million tuples learned in less than 5 minutes suffice for best-in-class accuracy, and learning cross-table correlations and unbiased join sampling are the most impactful components.The evaluation also studies NeuroCard's construction and query efficiency.Source: §7 · p. 8

7.1 Experimental Setup

• The evaluation uses three IMDB workloads: JOB-light, JOB-light-ranges, and JOB-M, covering 6-table and 16-table schemas and queries joining 2–11 tables.JOB-light-ranges adds varied range filters; JOB-M includes multiple join keys and a full join five times larger than the other workloads.Source: §7.1 · p. 8
• The evaluation reports Q-error distributions at p100, p99, p95, and the median, with actual and estimated cardinalities bounded below by 1.Q-error is the multiplicative deviation of an estimated cardinality from the true cardinality; timing tests use an AWS EC2 VM with a V100 GPU and 32 vCPUs.Source: §7.1 · p. 9
• JOB-light-ranges and JOB-M have median selectivities more than 100× lower than JOB-light, and minimum selectivities 1000× lower.Their selectivity spectra are wider, reflecting greater filter variety.Source: §7.1 · p. 9

7.2 Compared Approaches

• MSCN represents supervised query-driven estimation, while E2E provides the best reported JOB-light numbers from a deep supervised network.MSCN predicts from query features and sample bitmaps; for JOB-light-ranges, the authors generated 10K training queries with true cardinality labels.Source: §7.2 · p. 9
• DeepDB represents unsupervised data-driven estimation with models for selected table subsets, assuming conditional independence across subsets.The comparison includes versions modeling up to two-table joins and, in the larger configuration, three-table joins.Source: §7.2 · p. 9
• Index-based Join Sampling estimates cardinality by sampling a query's join graph and applying table filters on the fly, with a maximum sample size of 10,000.Postgres v12 is also included; it uses one-dimensional histograms and heuristics to combine them.Source: §7.2 · p. 9
• The authors omit classical density models, random sampling, and wavelets because prior studies reported them behind deep autoregressive models or DeepDB.NeuroCard is implemented on Naru's codebase, using ResMADE by default and a Transformer variant for complex benchmarks.Source: §7.2 · p. 9

7.3.1 JOB-light.

• 8.5× maximum Q-error on JOB-light uses 3.8 MB and improves by > 8× over the best prior method when controlling for size.The comparison covers 70 queries.Source: §7.3.1 · p. 9
• Postgres has the least accurate median, while IBJS degrades sharply at the tail and MSCN and E2E outperform earlier methods but lag data-driven estimators.The paper attributes IBJS’s tail errors to practical-size samples rarely hitting low-density queries in a large joint space.Source: §7.3.1 · p. 9
• NeuroCard is 4–8× better than DeepDB at the 99th-percentile and maximum errors, while DeepDB is slightly better at lower quantiles on JOB-light.DeepDB-large is 8.4× bigger and trained on 54M tuples, yet trails NeuroCard by more than 4× at the tail.Source: §7.3.1 · p. 9

7.3.2 JOB-light-ranges.

• Up to 15−34× improvement over the best prior methods, with the best accuracy across all error quantiles, on JOB-light-ranges.NeuroCard’s gains over enlarged MSCN and DeepDB are 1.4×, 2.6×, 9.6×, and 34× at median, 95th, 99th, and maximum error, respectively.Source: §7.3.2 · p. 10, Table 3 · p. 10

7.3.3 JOB-M.

• On JOB-M, NeuroCard offers more than 10× better accuracy across the board; for the 16-table full outer join, column factorization reduces vanilla model size from 900 MB to 27 MB.Source: §7.3.3 · p. 10, Table 4 · p. 10

7.4 Efficiency

• About 2–3M training tuples suffice for best-in-class p99 accuracy; using ∼10^7 samples from a 10^12-point population is only 0.001% of the data.More samples help, but returns diminish; the authors interpret this as evidence of statistical generalization to unseen data points.Source: §7.4 · p. 10
• Four sampling threads saturate the GPU; at ∼40K tuples/second, 3M tuples take about 1.25 minutes, and join-count tables take 13 seconds to calculate.The paper attributes efficient construction to parallel sampling and accelerated GPU computation.Source: §7.4 · p. 10
• NeuroCard’s inference latency is predictable, with a 17 ms median and 12 ms minimum, while DeepDB ranges from ∼1 ms to ∼100 ms.The paper attributes NeuroCard’s latency to the neural autoregressive model’s higher floating-point operation count.Source: §7.4 · pp. 10–11

7.5 Dissecting NeuroCard

• Using IBJS as a biased full-join sampler significantly reduces accuracy, with the median-error increase indicating distribution mismatch.The paper ranks this sampling choice as the second most important design decision.Source: §7.5 · p. 11, Table 5 · p. 11
• Smaller factorization bits cause a small accuracy drop, while disabling factorization performs best but uses the most space.For model sizing, enlarging embeddings is markedly more useful than enlarging feedforward layers.Source: §7.5 · p. 11, Table 5 · p. 11
• The per-table variant that combines estimates under independence has the lowest accuracy, unlike a single model that learns inter-table correlations.Source: §7.5 · p. 11, Table 5 · p. 11
• Uniform join samples are 10^4× less accurate than the autoregressive model at the tail, where many queries have no sample hits.Conditional probabilities enable progressive sampling, which the standalone sample-based estimator cannot use.Source: §7.5 · p. 11, Table 5 · p. 11
• For new datasets, start with the Base configuration and increase sizing within the budget, prioritizing factorization bits, embeddings, then feedforward width and layer count.The authors suggest setting training tuples by early stopping or a time budget, starting with a few to 10+ million.Source: §7.5 · p. 11

• Fast incremental updates recover most of NeuroCard’s accuracy with minimal overhead, while full retraining takes only a few minutes and achieves the highest accuracy.The comparison simulates five time-ordered database snapshots; fast updates use 1% of the original samples and retraining uses 100%.Source: §7.6 · pp. 11–12

• Classical multidimensional histograms capture inter-column correlations, while graphical models trade precision for efficiency through independence assumptions and require costly structure learning.The discussion traces unsupervised density estimation to System R’s one-dimensional histograms.Source: §8 · p. 12
• DeepDB and NeuroCard both model full outer joins, but NeuroCard uses a deep autoregressive model without independence assumptions, whereas DeepDB uses SPNs on selected table subsets.DeepDB assumes conditional independence across subsets; NeuroCard reports up to 34× better accuracy.Source: §8 · p. 12
• Deep autoregressive models learn complex high-dimensional distributions and expose conditional distributions; NeuroCard extends single-table Naru to joins [48].Source: §8 · p. 12
• Supervised query-driven estimators learn from query examples and can handle query feedback and complex predicates, but NeuroCard is described as more robust to out-of-distribution queries.The paper also notes that sampled tuples from NeuroCard’s learned distribution can support complex predicates.Source: §8 · p. 12
• NeuroCard uses uniform, independent join samples for training; IBJS and Wander Join estimate counts and aggregates but do not provide the uniform join samples it requires.NeuroCard adopts the linear-time Exact Weight algorithm.Source: §8 · p. 12
• The paper presents NeuroCard as a core that could support tasks beyond query optimization, including data imputation and indexing.Source: §8 · p. 12

9 CONCLUSION

• 4–34× better than prior methods in join-cardinality accuracy, using a single per-schema model.Source: §9 · p. 12
• NeuroCard combines join sampling and deep self-supervised learning to model all tables’ correlations without independence assumptions.Source: §9 · p. 12
• The model achieves assumption-free probabilistic modeling for more than a dozen tables while remaining compact and efficient to learn.Source: §9 · p. 12