PaperlayerView exact revision on arXiv

Source-linked AI summary

Flow-Loss: Learning Cardinality Estimates That Matter

Parimarjan Negi, Ryan Marcus, Andreas Kipf, Hongzi Mao, Nesime Tatbul, Tim Kraska, Mohammad Alizadeh

arXiv:2101.04964v1cs.DB

TL;DR

Learned cardinality estimators can improve average accuracy without improving the query plans that matter to an optimizer. Flow-Loss approximates optimizer cost and search with a differentiable flow-based objective to train for better plans. The paper reports improved plan costs and runtimes despite worse estimation accuracy than Q-Error, with better robustness when workloads differ from training queries.

  • Problem

    Learned cardinality estimation has emphasized average estimation accuracy, although estimates differ in how much they affect optimizer plan choices.

    Source: §1 · p. 1

  • Method

    Flow-Loss approximates optimizer cost and dynamic-programming search analytically, recasting plan search as flow routing on a plan graph to train cardinality estimates for better plans.

    Source: §1 · p. 1, §10 · p. 12

  • Results

    Flow-Loss models improve plan costs despite worse average estimation accuracy than Q-Error models, and typically improve over PostgreSQL estimates across workloads unlike Q-Error models that can regress under workload shifts.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Postgres Plan Cost offers an alternative to Q-Error for evaluating cardinality estimators, and Flow-Loss can help models generalize to queries from templates not seen in training.

    Source: §10 · p. 12

    P-Cost and Flow-Loss are defined over left-deep plans; extending them to bushy plans is more challenging because a corresponding graph would produce exponentially more paths.

    Source: §5.2 · p. 5

Abstract

from arXiv · show

Previous approaches to learned cardinality estimation have focused on improving average estimation error, but not all estimates matter equally. Since learned models inevitably make mistakes, the goal should be to improve the estimates that make the biggest difference to an optimizer. We introduce a new loss function, Flow-Loss, that explicitly optimizes for better query plans by approximating the optimizer's cost model and dynamic programming search algorithm with analytical functions. At the heart of Flow-Loss is a reduction of query optimization to a flow routing problem on a certain plan graph in which paths correspond to different query plans. To evaluate our approach, we introduce the Cardinality Estimation Benchmark, which contains the ground truth cardinalities for sub-plans of over 16K queries from 21 templates with up to 15 joins. We show that across different architectures and databases, a model trained with Flow-Loss improves the cost of plans (using the PostgreSQL cost model) and query runtimes despite having worse estimation accuracy than a model trained with Q-Error. When the test set queries closely match the training queries, both models improve performance significantly over PostgreSQL and are close to the optimal performance (using true cardinalities). However, the Q-Error trained model degrades significantly when evaluated on queries that are slightly different (e.g., similar but not identical query templates), while the Flow-Loss trained model generalizes better to such situations. For example, the Flow-Loss model achieves up to 1.5x better runtimes on unseen templates compared to the Q-Error model, despite leveraging the same model architecture and training data.

1. INTRODUCTION

Learned cardinality estimators can improve average accuracy while still misleading an optimizer, because estimates differ in how much they affect plan choices. Flow-Loss trains models to prioritize estimates that improve plans, and the paper reports better plan costs and runtime robustness despite worse average estimation accuracy than Q-Error.

1. INTRODUCTION

  • Estimator errors are inevitable, and their impact differs: some sub-plan estimates affect optimizer decisions while others may have no effect.The paper identifies limited model capacity, training data, and differences between training and testing conditions as sources of error.Source: §1 · p. 1
  • Flow-Loss emphasizes estimates that matter to query performance, unlike Q-Error, which can reward a more accurate estimate that leads the optimizer to choose a worse plan.In the example, Estimator2 has smaller cardinality error than Estimator1 but misleads the optimizer to choose Plan2.Source: §1 · p. 1, Figure 1 · p. 1
  • Flow-Loss approximates plan cost and dynamic-programming search with differentiable functions, enabling gradient-based improvement of estimates relevant to query plans.The paper reports that optimizing this objective also improves plans under PostgreSQL’s cost model and optimizer.Source: §1 · pp. 1–2
  • Flow-Loss models improve generated-plan costs despite worse average estimation accuracy than Q-Error, and avoid the performance drops Q-Error models can show under workload shifts.Q-Error models can be up to 1.5× slower than PostgreSQL’s default estimates on diverging workloads; Flow-Loss models typically improve over them.Source: §1 · p. 2
  • The paper introduces Postgres Plan Cost, Flow-Loss, and the Cardinality Estimation Benchmark, which is over 100× larger than JOB and contains more complex queries.It also reports that Flow-Loss can produce almost equally good plans from approximate query-processing training data.Source: §1 · p. 2
  • With approximate query-processing training data, Q-Error models have over 10× worse 99th-percentile Q-Error and PostgreSQL costs than Flow-Loss models.Approximate query processing is 10–100× faster than computing true cardinalities.Source: §1 · p. 2

2. RELATED WORK

Prior cardinality-estimation research includes traditional statistical methods, unsupervised learned models, and supervised approaches. Comparatively few supervised studies demonstrate improved query performance, which this work targets by using the optimizer’s search and cost algorithms.

2. RELATED WORK

  • Traditional cardinality estimators use histograms, sampling, kernel density estimation, wavelets, and singular value decomposition.Many recent learned approaches focus on single-table selectivity [36], while extending these to joins using join sampling is non-trivial.Source: §2 · p. 2
  • Unsupervised approaches include probabilistic graphical models, sum-product networks, and deep autoregressive models.NeuroCard does not support the complex analytical workloads studied here, such as queries with self joins.Source: §2 · p. 2
  • Although supervised learning works report improved estimation accuracy, only a few demonstrate improved query performance [15].This work learns cardinalities for a traditional DBMS optimizer while using the optimizer’s own search and cost algorithms.Source: §2 · p. 2
  • Other query-performance learning approaches include learning the optimizer, its hints, or its cost model, as well as re-optimization and bounding worst-case cardinalities.The paper describes these approaches as complementary to its method.Source: §2 · p. 2

3. OVERVIEW

The overview frames cardinality estimation as a problem of improving the estimates that influence optimizer decisions, rather than treating all estimates equally. It approximates cost and plan search analytically, then uses a differentiable flow formulation to connect edge costs to plans.

3. OVERVIEW

  • Q-Error-style losses treat each estimate alike, while the paper seeks to focus model capacity on estimates that affect plan quality and tolerate larger errors elsewhere.The motivation is that optimizer decisions may be sensitive to some sub-plans and unaffected by others.Source: §3 · p. 2
  • The approach approximates both optimizer components—the cost model and dynamic-programming search—with analytical functions combined into a differentiable loss.The cost model maps cardinality estimates to join costs, and the search maps join costs to an optimal plan.Source: §3 · p. 3, Figure 2 · p. 3
  • A simple cost approximation includes terms for joins with and without indexes, and the paper reports that it works well on its workloads.The paper says a more precise approximation is possible and analyzes its fit to PostgreSQL’s cost model in §6.1.Source: §3 · p. 3
  • Left-deep plans correspond to paths in a plan graph, where each edge represents a join and the cheapest plan is the shortest path from S to D.Changing cardinality estimates changes edge costs and can therefore change which path is shortest.Source: §3 · p. 3
  • A shortest-path objective alone has no gradient for most edge costs, because small cost changes usually leave the selected path unchanged.The overview addresses this with a soft shortest-path formulation that treats the plan graph as an electrical circuit, distributing flow over low-resistance paths.Source: §3 · p. 3

4. DEFINITIONS

The definitions establish the plan graph and its correspondence between paths and left-deep plans, then define edge costs and the true cost of the plan selected using estimated cardinalities. They also clarify that P-Cost is not a distance metric.

4. DEFINITIONS

  • A sub-plan is a subset of query tables that can be joined using inner joins; the paper’s setup ignores cross-joins and assumes joined columns have indexes.For the Q1 example, kt ⋈ t is a sub-plan, but kt ⋈ ci is not.Source: §4 · p. 4
  • The plan graph is a directed acyclic graph whose nodes are sub-plans and whose edges represent joins between a sub-plan and a base table.A path from S to D corresponds to a left-deep plan.Source: §4 · p. 4
  • The cardinality vector records sub-plan cardinalities, and the cost model assigns a cost to each join edge from that vector.The simple model includes indexed and unindexed nested-loop terms; λ = 0.001 models an index on the base table.Source: §4 · p. 4
  • P-Opt selects the cheapest path using the estimated cardinalities, while P-Cost sums the true edge costs along that selected path.For fixed true cardinalities, P-Cost is lowest when the estimates equal the true values.Source: §4 · p. 4
  • P-Cost is not a distance metric because it does not satisfy symmetry, though that does not prevent its use in the loss function.The paper says an online appendix constructs a pseudometric from P-Cost to compare cardinality vectors.Source: §4 · p. 4

5. FLOW-LOSS

Flow-Loss addresses the fact that P-Cost reflects plan quality but has almost no gradient for most cardinality estimates. It replaces the optimizer’s single cheapest-path choice with differentiable electrical flows over plan-graph paths.

5. FLOW-LOSS

  • P-Cost is unsuitable for gradient-based training because small estimate changes usually leave the chosen cheapest path unchanged, so its gradient is almost always zero.The paper introduces Flow-Loss as an alternative with gradients for cardinalities in the plan graph.Source: §5 · p. 4

5.1 From Shortest Path to Electrical Flows

  • The plan graph treats query plans as paths; Flow-Loss replaces a single shortest path with electrical flows distributed across paths according to their costs.The flow sends one unit from source to destination while conserving flow at intermediate nodes.Source: §5.1 · pp. 4–5
  • Flow-Loss uses estimated edge costs as resistances and weights true edge costs by squared estimated flows, making the loss differentiable with respect to cardinality estimates.The flows minimize true energy dissipation when estimates equal true cardinalities.Source: §5.1 · p. 5

5.2 Discussion

  • Flow-Loss is defined over left-deep plans; explicitly representing bushy plans would create exponentially more paths, though the same sub-plans are generally relevant to both.The discussion notes that the best left-deep plan often performs reasonably relative to the best overall plan.Source: §5.2 · p. 5
  • Because join-edge costs are often linear in cardinalities, scaling all estimates together may leave plan choices unchanged, so Flow-Loss does not anchor outputs to true values.Explicit penalties for deviations or a cost model sensitive to absolute cardinalities are possible; the paper reports good PostgreSQL performance without anchoring in its workloads.Source: §5.2 · p. 5

6. FLOW-LOSS ANALYSIS

This analysis examines how Flow-Loss relates to PostgreSQL plan costs and how its response to estimate errors differs from Q-Error. It also describes how the loss directs model capacity toward estimates that matter to query performance.

6.1 Cost Model

  • P-Cost and PostgreSQL Plan Cost mostly follow the same trends across two workloads, although their scales need not match.P-Cost serves as a signal for improving estimates that lead to high costs, rather than as a precise reproduction of PostgreSQL’s cost model.Source: §6.1 · p. 6, Figure 5 · p. 6

6.2 Shape of Loss Functions

  • For a single sub-plan, Flow-Loss responds differently to under- and overestimates depending on whether its paths are costly or good, unlike Q-Error’s identical response across nodes.Underestimating a node on expensive paths can make bad plans appear cheaper; overestimating nodes on good paths can make those paths appear more expensive.Source: §6.2 · p. 6, Figure 7 · p. 6
  • Flow-Loss can penalize overestimates on near-optimal paths even when PPC stays flat, reflecting that small cardinality changes could make those paths cheapest.When two sub-plan estimates are varied together, Flow-Loss is highest when both are underestimated, in line with PPC’s behavior.Source: §6.2 · pp. 6–7, Figure 8 · p. 6

6.3 Benefits of Flow-Loss

  • Flow-Loss guides limited model capacity toward estimates that affect plans and tolerates errors on sub-plans that typically do not worsen them.The paper presents this domain-specific regularization as a way to handle noisy or missing training data, including approximate cardinalities from fast sampling.Source: §6.3 · p. 7

7. FEATURIZATION AND MODELS

The models use features for tables, joins, predicates, and plan-graph context, and compare two neural architectures with Q-Error and Flow-Loss. The added graph features describe neighboring plans and PostgreSQL estimates.

Featurization

  • Sub-plan features combine table, join, predicate, and plan-graph vectors; predicate encodings include normalization or feature hashing, with PostgreSQL table estimates added to table features.The plan-graph vector also includes PostgreSQL’s sub-plan cost and cardinality estimates, which are log-transformed.Source: §7 · p. 7

Models

  • FCNN concatenates the feature vectors into a 1-D input, while MSCN extends a set-based architecture to include plan-graph features.FCNN is lightweight and efficient to train but does not scale with increasing database size; MSCN scales but trains less efficiently.Source: §7 · pp. 7–8

Featurization

  • The plan-graph vector captures immediate child count, join costs, and each child’s cardinality relative to its parent, alongside the sub-plan’s PostgreSQL estimates.These neighboring-node properties are included because they could help models generalize to new queries.Source: §7 · p. 7

8. Cardinality Estimation Benchmark (CEB)

CEB provides a large workload of query templates and labeled sub-plans, while a modified wander-join procedure generates approximate training labels more quickly than ground-truth computation. The dataset’s query generator accounts for correlated predicates.

8.1 Dataset

  • CEB contains over 16K queries and true cardinalities for over 4M sub-plans across IMDb and StackExchange, including queries with five to sixteen joins.It provides hundreds of queries per hand-crafted template, addressing the limited training data in JOB and the smaller join counts of earlier supervised-learning workloads.Source: §8.1 · p. 8, Table 1 · p. 8
  • The query generator samples correlated predicate values together, using dependencies and group-by queries to avoid combinations that produce zero or very few results.The TOML configuration specifies a predefined query template and generation rules.Source: §8.1 · p. 8

8.2 Approximate Training Data

  • For approximate training labels, the modified wander-join method filters base tables before random walks and reuses filtered tables across sub-plans and queries.Applying filters first makes the walks faster, while reusing filtered tables makes that one-time filtering cost practical for training-data generation.Source: §8.2 · p. 8
  • Wander-join estimates are 10×–100× faster than ground-truth generation; for the largest template, they take under five minutes versus about five hours on one core.The authors report that this proof-of-concept implementation yields almost equally good plans.Source: §8.2 · p. 9

9. EXPERIMENTS

Across the experiments, Flow-Loss generally improves plan cost and is more robust to unseen templates than Q-Error, despite worse estimation accuracy. Results vary by workload and partition, and the StackExchange evaluation uses substituted labels for timed-out sub-plans.

9.2 Testing on unseen templates

  • On unseen templates, Flow-Loss models outperform Q-Error models on PPC and degrade more gracefully; runtime improvements are also evident on unseen queries.Across partitions, Flow-Loss shows significant gains on some, smaller regressions on others, and similar performance on many.Source: §9 · p. 9, §9.2 · p. 9, Figure 10 · p. 10

9.1 Testing on seen templates

  • On seen IMDb templates, Flow-Loss models have worse Q-Error but lower mean PPC than Q-Error models, approaching true-cardinality PPC; runtimes are similar across learned models.Training with wander-join estimates is almost as good as training with true cardinalities, and Flow-Loss is more robust to their noise than Q-Error in tail performance.Source: §9.1 · p. 9, Table 2 · p. 10

9.2 Testing on unseen templates

  • For an unseen-template partition, Flow-Loss closely tracks PPC on learning curves, while the Q-Error model is erratic on the test set and has worse Q-Error but better PPC.The selected best partition improves across all runtime percentiles; even on the median partition, Flow-Loss does better at the tail.Source: §9.2 · pp. 9–10, Figure 15 · p. 11
  • On JOB, both Flow-Loss models slightly improve PPC over PostgreSQL with similar runtimes, while the Q-Error MSCN model has higher variance and performs significantly worse.JOB is used for evaluation rather than supervised training because it has too few queries.Source: §9.2 · p. 11, Figure 16 · p. 11
  • On unseen templates, Q-Error models become almost 10× worse at the 90th and 99th Q-Error percentiles, while Flow-Loss models worsen by about 1.5×.On JOB, Flow-Loss models even have better estimation accuracy than Q-Error models.Source: §9.2 · p. 11, Figure 17 · p. 12
  • Flow-Loss handles removal of featurization components on seen templates better than Q-Error, while both losses worsen on unseen templates without PostgreSQL features.Plan-graph features also appear to help generalization; training Flow-Loss adds a 3–5× training-time overhead over Q-Error.Source: §9.2 · pp. 11–12, Figure 18 · p. 12

9.3 StackExchange workload

  • On StackExchange seen templates, both losses improve over PostgreSQL and perform similarly, but Flow-Loss improves significantly over Q-Error on unseen templates.Timed-out sub-plans are assigned a large constant, which can artificially inflate PPC and increase its variance; three unseen partitions improve by over 20 seconds on average.Source: §9.3 · p. 12, Figure 19 · p. 12

10. CONCLUSIONS

The paper presents PPC as a useful runtime proxy and Flow-Loss as a differentiable objective for training cardinality estimators. It concludes that Flow-Loss can improve plan-relevant estimates and robustness, including with approximate training labels.

10. CONCLUSIONS

  • PPC is presented as a useful proxy for runtimes and an alternative to Q-Error for evaluating cardinality estimators.The conclusion describes Flow-Loss as a smooth, differentiable approximation to PPC that supports gradient-based model training.Source: §10 · p. 12
  • Flow-Loss can guide models toward cardinalities with greater impact on query performance and help them generalize to unseen templates and learn from AQP-generated data.The conclusion links this robustness to avoiding overfitting to estimates unlikely to improve query performance.Source: §10 · p. 12
  • Avoiding ground-truth labels could support practical adoption because generating them is expensive and data updates can quickly make them stale.Source: §10 · p. 12

A. METRIC BASED ON PLAN-COST

The appendix defines a plan-cost-based pseudometric and derives how to compute plan-graph flows, Flow-Loss, and its gradient from cardinality-dependent edge costs.

A. METRIC BASED ON PLAN-COST

  • P-Error extends P-Cost to compare cardinality vectors, and is a pseudometric because it satisfies nonnegativity, symmetry, and the triangle inequality while distinct vectors can have zero distance.The triangle-inequality proof uses the definition of P-Error and the absolute-value inequality.Source: A. METRIC BASED ON PLAN-COST · p. 15

B.1 Computing Flows

  • The plan graph is modeled as an electrical circuit: edge costs determine resistances, and node voltages satisfy one-unit source and destination flow constraints plus intermediate flow conservation.The resulting linear system is over-determined, so the derivation says to remove the first equation in practice.Source: §B.1 · p. 15
  • The voltage system is represented with B(Y), a deterministic function of the cost model and cardinalities, allowing voltages to be solved from fixed constraints, including with a pseudoinverse if needed.Edge flows are then computed from voltage differences and inverse edge costs using Ohm’s law.Source: §B.1 · p. 16

B.2 Flow-Loss

  • Flow-Loss sums true edge costs weighted by the flows computed using estimated cardinalities, evaluating those estimated flows against costs from true cardinalities.The loss is expressed as a sum over all edges in the plan graph.Source: §B.2 · p. 16

B.3 Flow-Loss gradient

  • The Flow-Loss gradient propagates through inverse edge costs, and its cost-function Jacobian is sparse because each edge cost depends on only two cardinality estimates.The derivation also reuses intermediate results from the flow computation in neural-network forward and backward passes.Source: §B.3 · pp. 16–17

C.1 StackExchange timeouts

On StackExchange, unusual join graphs in three of six templates cause many subquery timeouts when generating ground-truth sub-plan cardinalities.

C.1 StackExchange timeouts

  • 3 of the 6 StackExchange templates have a large proportion of timeouts while generating ground-truth sub-plan data.The paper attributes this to an unusual join graph.Source: §C.1 · p. 17
  • The q-s-u sub-plan can combine filtered questions and users without a direct q-u relationship, producing a blow-up that leads to timeouts.The joins on user and answer are related, but question and user are not related without answer; the shared site join means this is not technically a cross-join.Source: §C.1 · p. 17
  • The paper notes that such join graphs can arise in natural queries about users answering questions with particular tags.Its example asks for locations of users who answer StackOverflow questions tagged with JavaScript.Source: §C.1 · p. 17
Loading 2101.04964v1…