A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration

1 INTRODUCTION

• Cardinality estimation, cost modeling, and plan enumeration jointly determine whether a cost-based optimizer can find an optimal plan in reasonable time.The optimizer estimates intermediate tuple counts, estimates plan costs, and searches semantically equivalent join orders.Source: §1 · p. 1
• The survey covers research aimed at improving cardinality estimation, cost models, and plan enumeration.It also summarizes why these components fall short.Source: §1 · p. 1
• Cardinality-estimation work is categorized as synopsis-based, sampling-based, or learning-based.The paper also discusses approaches for improving cost models and handling large queries.Source: §1 · p. 1
• The survey covers both learning-based and non-learning methods and offers possible future directions for each optimizer component.It focuses on the optimizer rather than AI use across other DBMS areas.Source: §1 · p. 2

2.1 Cardinality Estimation

• Cardinality estimates can err because of simplified distribution assumptions, cross-table correlations, error propagation across joins, and user-defined functions.Histograms may omit true data distributions; multi-histograms require substantial storage, and cross-table synopses are difficult to obtain.Source: §2.1 · p. 2

2.2 Cost Model

• Cost estimates depend on hardware, implementation, processed tuples, and database state, while cardinality errors and non-linear runtime relationships can produce inaccurate costs.Distributed, parallel, cloud, and cross-platform settings further increase cost-model complexity.Source: §2.2 · p. 2

2.3 Plan Enumeration

• Plan enumeration is NP-hard, and exhaustive search is prohibitive for large multi-join queries; heuristics can sacrifice optimality to keep optimization time reasonable.Search-space pruning and errors in cardinality or cost estimates are additional limitations.Source: §2.3 · p. 2

3 CARDINALITY ESTIMATION

• Cardinality-estimation methods are divided into three major strategies, presented as a classification.The supplied text does not name the three strategies.Source: §3 · p. 2, Figure 2 · p. 3
• The methods seek to approximate data distributions while using less storage.Source: §3 · p. 3
• Some proposed methods combine different techniques, including examples cited as.Source: §3 · p. 3

3.1 Synopsis-based methods

• Synopsis-based methods use statistics structures such as histograms and sketches to record data information.The survey distinguishes this work from an earlier synopsis survey focused on aspects relevant to approximate query processing.Source: §3.1 · p. 3

3.1.1 Histogram.

• Histogram research covers faster construction, new bucket-partitioning methods, and query-feedback construction.Some methods use sampling or merging to reduce construction costs, while others target better accuracy or incremental updates.Source: §3.1.1 · p. 3

3.1.2 Sketch.

• Sketches summarize column values or join attributes to estimate distinct counts, tuple frequencies, and join sizes.The reviewed join sketches focus on two tables without filters and support single-column equi-joins; adding a filter through an imaginary table can substantially worsen estimates.Source: §3.1.2 · p. 3

3.1.3 Other Techniques.

• TuG represents tuple sets or attribute values as graph nodes and their join relationships as edges, then estimates selectivity by traversing the graph.Its construction is time-consuming; it also cannot be built without relationships between tables and cannot be used on large datasets.Source: §3.1.3 · pp. 3–4

• Sampling methods estimate cardinality by running a query over sampled tuples, with accuracy depending on how closely the samples reflect the original data.The survey traces work from independent to correlated sampling and emphasizes how later methods address earlier shortcomings.Source: §3.2 · p. 4
• For equi-joins, Haas et al. favor page-level sampling combined with indexes when available, and page-level cross-product sampling otherwise; bifocal sampling separates sparse and dense join values.Bifocal sampling uses t_cross for dense-dense cases and t_index for the other cases, requiring an extra frequency pass and indexes for those other cases.Source: §3.2 · p. 4
• End-biased sampling stores frequent join values and correlates sampling decisions across tables, but supports only two-table equi-joins and requires an extra frequency pass.Without indexes, the extra pass is needed to compute join-attribute frequencies.Source: §3.2 · p. 4
• CS2 propagates samples through a join graph and uses a reverse estimator for queries without the source table, but repeated graph traversals can be slow without indexes.It also requires unpredictable space to store samples.Source: §3.2 · p. 4
• Correlated sampling often has lower variance than independent Bernoulli sampling, but Bernoulli sampling can be better when many join values are frequent.The authors suggest a one-pass high-frequency-value detector as a possible response.Source: §3.2 · p. 4
• Chen and Yi combine correlated value sampling with independent tuple sampling, while CSDL-Opt outperforms their method when samples or join-value density are small.Wu et al. also use online sampling to correct possible errors in optimizer-generated plans.Source: §3.2 · p. 4

3.3.1 Supervised Methods.

• Other supervised approaches include KDE for single-table predicates and QuickSel's uniform mixture models; Bayesian-network methods model limited dependencies, with multi-table validation absent for one approach.The Bayesian-network approach of Tzoumas et al. captures dependencies between at most two relations, and constructing cross-table statistics requires joins.Source: §3.3.1 · pp. 4–5, §3.3.2 · p. 6
• Neural approaches model queries as operation sequences or trees, and MSCN represents tables, joins, and predicates with separate networks whose outputs feed a final network.Tree-LSTM estimates cardinality and cost simultaneously; the recurrent model described here focuses on left-deep plans.Source: §3.3.1 · pp. 5–6
• Supervised estimators include query-template models trained on query features and regression models that add histograms or domain knowledge as features.Domain knowledge can improve estimation accuracy and, because it updates quickly with data distributions, support robustness to dataset updates.Source: §3.3.1 · pp. 4–5
• Local neural models target separate query templates to avoid sparse encoding in a single schema-wide model, but collecting true cardinalities with sample queries is time-consuming.Pre-aggregating base data with a data cube is described as an alternative for executing example queries.Source: §3.3.1 · pp. 5–6

3.3.2 Unsupervised Methods.

• Naru estimates selectivity from an autoregressive model's conditional densities using the product rule, with progressive sampling for range conditions and wildcard-skipping for wildcard conditions.A later approach adds adaptive sampling for range queries and workload-weighted training.Source: §3.3.2 · p. 6
• Unsupervised join estimators include RSPN models built over join results and an extension of Naru built over full outer joins with lossless column factorization and join count tables.The latter supports queries on subsets of tables.Source: §3.3.2 · p. 6

3.4.1 Summaries.

• Histograms face rapidly increasing storage for d-dimensional summaries and difficulty capturing cross-table correlations; synopsis methods also cannot estimate intermediate or final relations when a child is itself intermediate.Cross-table histograms require joins and are difficult to update, while sketches do not handle filtered joins well.Source: §3.4.1 · p. 6
• Sampling can capture cross-table correlations, but updates can make samples stale, and storage and retrieval become costly on large datasets.The survey states that current sampling methods support only equi-joins.Source: §3.4.1 · p. 6
• Supervised models are often workload-specific and need retraining after workload shifts, while data changes affect both learning categories and studied update handling covers only appended tuples in one table.The survey reports Naru as robust to workload shifts while MSCN and KDE are sensitive to training queries.Source: §3.4.1 · p. 6
• The comparison is preliminary because experimental settings differ, although the survey reports method [103] as superior to others in its experiments.The survey also notes that learning-based methods can still have substantial model size.Source: §3.4.1 · p. 6

3.4.2 Possible Future Directions.

• Future work includes efficient model training and updates, hybridizing query-driven and data-driven approaches, and experiments across systems, workloads, scales, distributions, storage, accuracy, and update-efficiency trade-offs.The survey notes that some complex models have long training and update times and that current data-change methods do not handle deletes or updates.Source: §3.4.2 · p. 7

4 COST MODEL

• Cost-model studies are grouped into improving existing models, building new models, and predicting single-query performance; concurrent-query prediction is excluded.The survey treats single-query prediction as potentially replaceable for cost estimation within a cost-based optimizer.Source: §4 · p. 7

4.1 Quality Improvement of Existing Cost Model

• Existing-model improvements address distinct targets, including UDF costs, main-memory hash joins, and joint latency and monetary-cost estimation in multi-cloud settings.The multi-cloud model combines charging policies with estimated execution time.Source: §4.1 · p. 7

4.2 Cost Model Alternatives

• Learning-based cost alternatives approximate the mapping from annotated plans to scalar costs, with examples ranging from neural networks and tree-LSTMs to workload-derived models.SCOPE’s model uses operator-input and operator-subgraph models with a meta-ensemble, including partition count as a resource-planning feature.Source: §4.2 · p. 8

4.3 Query Performance Prediction

• Single-query performance prediction includes calibrated cost models with sampled operator cardinalities, resource models, and plan- or operator-level latency models.Neo predicts physical-plan latency using query-level and plan-level encodings.Source: §4.3 · p. 8

4.4.1 Summaries.

• The survey’s synthesis says learned models can capture complex cost relationships, but supervised models may need retraining when workloads shift or data changes.It identifies tree-LSTM cost modeling as an example that captures data, operator-level, and subplan information.Source: §4.4.1 · p. 8
• The proposed directions include incorporating economic cost into cloud optimization and balancing learning-model accuracy against training time.The passage notes that real-system cost models are lightweight and that methods from cardinality estimation may also apply.Source: §4.4.1 · pp. 8–9

5.1.1 Dynamic Programming.

• Dynamic-programming approaches range from left-deep search and bushy-tree generation to graph-based enumeration of connected subgraphs for bushy trees without cross products.The graph-based method avoids checking connectivity and combinations during generation.Source: §5.1.1 · p. 9

5.1.2 Top-down Strategies.

• TDMinCutLazy partitions join graphs using minimal cuts and cost-bound pruning, while later top-down methods refine valid-partition generation and extend support to generalized joins.TDMinCutBranch generates cross-product-free partitions directly; TD-MinCutConservative is reported to have better runtime performance than it.Source: §5.1.2 · p. 9

5.1.3 Large Queries.

• Large-query methods include greedy join ordering, incremental dynamic programming, query simplification before DP, and enumerate-rank-merge strategies.Neumann and Radke select among DP, restricted DP, and a large-query method according to query type and table count.Source: §5.1.3 · p. 9
• A mixed-integer linear-programming approach minimizes plan cost while producing a left-deep tree, approximating scan and join costs with linear functions.The linear approximations satisfy MILP’s linearity requirements.Source: §5.1.4 · p. 9

5.1.4 Others.

• For FK-FK joins, an n-ary join operator extends the plan space and is paired with a new cost model in an OLAP system.The operator processes FK-FK joins represented by a core graph.Source: §5.1.4 · p. 9

• In join-order selection, reinforcement learning treats current subtrees as the state and combining two subtrees as an action, with reward assigned to the final action as query cost or latency.Intermediate actions receive zero reward.Source: §5.2 · p. 10
• ReJoin, DQ, and Yu et al. use different encodings and model choices, with some methods trained on optimizer costs and then fine-tuned using running time.Yu et al. combine DRL with tree-LSTM representations; DQ also encodes physical-operator choices.Source: §5.2 · p. 10
• SkinnerDB learns from execution slices of the current query, unlike the described methods that learn from previous queries.Different slices may select different join orders.Source: §5.2 · p. 10

5.3 Our Insights

• Non-learning methods improve efficiency and support for general join cases, while top-down search offers extensibility such as new transformation rules and branch-and-bound pruning.Both dynamic programming and top-down approaches have been implemented in database systems.Source: §5.3.1 · p. 10

5.3.1 Summaries.

• Learning-based methods plan quickly and the reported state-of-the-art method outperforms non-learning methods in experiments, but real-system integration remains unresolved.The survey also identifies large-query support, non-PK-FK and non-inner joins, and adaptation to schema or data changes as directions for further work.Source: §5.3.1 · p. 10

• The survey covers traditional and learning-based methods for cardinality estimation, cost models, and plan enumeration, and offers future directions for each.Source: §6 · p. 10
• Learning-based methods increasingly outperform traditional methods, but long training and updating times remain challenges.Source: §6 · p. 10
• Robustness to workload shifts and data changes, and faster model updates, remain open questions; traditional methods retain theoretical guarantees and are widely adopted in real systems.The paper also sees potential to improve traditional methods with new algorithms and data structures, and to apply traditional-method ideas to learning-based methods.Source: §6 · p. 10