Flow-Loss: Learning Cardinality Estimates That Matter

Abstract

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.

References in corpus (10)

• Neo: A Learned Query Optimizer
• Deep Unsupervised Cardinality Estimation
• Kohn-Sham equations as regularizer: building prior knowledge into machine-learned physics
• Learning to Optimize Join Queries With Deep Reinforcement Learning
• SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning
• Privacy-preserving Machine Learning through Data Obfuscation
• Charagram: Embedding Words and Sentences via Character n-grams
• NeuroCard: One Cardinality Estimator for All Tables
• An Empirical Analysis of Deep Learning for Cardinality Estimation
• Adaptive Cardinality Estimation

Cited by in corpus (4)

• Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation
• Fine-Grained Modeling and Optimization for Intelligent Resource Management in Big Data Processing
• A Unified Transferable Model for ML-Enhanced DBMS
• Simpli-Squared: A Very Simple Yet Unexpectedly Powerful Join Ordering Algorithm Without Cardinality Estimates