Source-linked AI summary
An End-to-End Learning-based Cost Estimator
Ji Sun, Guoliang Li
TL;DR
Traditional estimators struggle with correlations across columns, while prior learning-based methods generally estimate cardinality rather than cost and have difficulty representing complex structures. This paper proposes an end-to-end tree-structured estimator that jointly predicts cost and cardinality using query-plan, predicate, metadata, and data features, including pattern-based string encodings. Experiments on real-world datasets showed that the method outperformed existing techniques.
Problem
Traditional cost and cardinality estimation cannot capture correlations between multiple columns, while existing learning-based methods estimate cardinality but not cost and struggle with complex structures.
Method
The paper uses an end-to-end tree-structured neural model that extracts query and physical-operation features and encodes numeric and string predicates for joint cost and cardinality estimation.
Results
Experiments on real-world datasets showed that the proposed method outperformed existing techniques.
Takeaways & Limitations
The framework provides a single learning-based estimator for both query cost and cardinality while representing complex query-plan and predicate structures.
Abstract
from arXiv · showhide
Cost and cardinality estimation is vital to query optimizer, which can guide the plan selection. However traditional empirical cost and cardinality estimation techniques cannot provide high-quality estimation, because they cannot capture the correlation between multiple columns. Recently the database community shows that the learning-based cardinality estimation is better than the empirical methods. However, existing learning-based methods have several limitations. Firstly, they can only estimate the cardinality, but cannot estimate the cost. Secondly, convolutional neural network (CNN) with average pooling is hard to represent complicated structures, e.g., complex predicates, and the model is hard to be generalized. To address these challenges, we propose an effective end-to-end learning-based cost estimation framework based on a tree-structured model, which can estimate both cost and cardinality simultaneously. To the best of our knowledge, this is the first end-to-end cost estimator based on deep learning. We propose effective feature extraction and encoding techniques, which consider both queries and physical operations in feature extraction. We embed these features into our tree-structured model. We propose an effective method to encode string values, which can improve the generalization ability for predicate matching. As it is prohibitively expensive to enumerate all string values, we design a patten-based method, which selects patterns to cover string values and utilizes the patterns to embed string values. We conducted experiments on real-world datasets and experimental results showed that our method outperformed baselines.
1. INTRODUCTION
Traditional estimators can produce poor query plans because they miss correlations across columns and require DBA fine-tuning, while prior learning-based work mainly estimates cardinality and struggles with complex structures. The paper introduces a tree-structured end-to-end estimator that jointly predicts cost and cardinality and improves generalization to complex predicates.
- Traditional cost and cardinality estimators miss correlations between multiple columns and require fine-tuning by DBAs.
- Existing learning-based methods estimate cardinality but not cost, while CNNs with average pooling represent complex predicates and tree-structured plans poorly.
- The proposed end-to-end tree-structured model estimates cost and cardinality simultaneously and can represent complex predicates with numeric and string values.
- The framework extracts and encodes features from both queries and physical execution, then embeds them into the tree-structured model.
- A pattern-based string encoding method selects patterns to cover string values, improving generalization without enumerating all possible strings.
- Experiments on real-world datasets showed that the proposed method outperformed existing approaches.
2. RELATED WORK
Related work describes traditional histogram and sketching approaches and prior learning-based methods for cardinality or performance prediction. These methods have limitations in modeling column correlations, complex query plans, or automatically learned operation features.
- Histogram-based cardinality estimation divides values into buckets, but it is not effective at estimating correlations between different columns.
- Figure 1 contrasts traditional cost estimation with learning-based cost estimation.
- Prior join-tree representation work does not support query plans with complex tree structures or complex queries.
3. OVERVIEW OF END-TO-END COST ESTIMATOR
The estimator generates labeled physical plans, extracts query and database features, and processes plan trees bottom-up to predict cost and cardinality. Its design targets large estimation errors in traditional methods, especially for joins involving correlated tables.
- Cost estimation predicts execution cost for optimizer plan selection, while cardinality estimation predicts tuples in a query or subquery result.
- Traditional methods can estimate leaf-node cardinality reasonably but incur increasingly large errors for joins as correlations between tables accumulate.
- The framework generates queries and optimizer physical plans, then records each plan's real cost and real cardinality as training data.
- Its feature extractor encodes physical operations, predicates, metadata, and data-related samples into vectors.
- A tree-structured model follows the query-plan tree and estimates each plan's cost and cardinality bottom-up from its subplans.
- During online estimation, previously evaluated subplans can be retrieved from representation memory, while new subplans are recursively encoded and evaluated.
4. TREE-BASED LEARNING MODEL
The model encodes query plans and predicates as tree-structured representations, combining operation, metadata, predicate, and sample-bitmap features. It uses recursive neural representations and separate estimation outputs to address information loss while estimating plan cost and cardinality.
- Feature extraction and encoding: Four feature types—operation, metadata, predicate, and sample bitmap—are extracted and embedded into vectors for each plan node.Operation uses one-hot encoding, while metadata and sample bitmap use bitmap vectors; sparse vectors are transformed into dense representations.
- Feature extraction and encoding: Compound predicates are encoded by mapping their tree structures to DFS sequences, appending empty nodes for backtracking, and concatenating predicate vectors.This one-to-one mapping produces a unique vector for each distinct complex predicate tree.
- Tree model architecture: The embedding, representation, and estimation layers mirror the plan structure, with each representation unit learning global and local vectors for a sub-plan.The tree-structured representation recursively follows the query plan and converts sparse node features into learned representations.
- Embedding layer: Predicate tree pooling preserves Boolean structure by using fully connected networks at leaves, max pooling for OR, and min pooling for AND.The design trains only leaf nodes and is described as enabling efficient batch training, faster convergence, and better performance.
- Representation layer: The representation layer recursively propagates information from leaves to the root using shared neural units and LSTM cells.This design targets information vanishing and space explosion by representing intermediate sub-plan results with learned vectors rather than data sketches.
5. STRING EMBEDDING
The paper represents sparse string predicates with learned embeddings and pattern-based substring extraction. It selects compact rule sets to cover workload strings, then indexes extracted substrings for query encoding.
- String values are harder to learn than numeric values because they are sparse and discrete rather than continuous.
- Hash-bitmap embeddings capture string similarity but not co-occurrence, motivating representations that learn co-existing string values from dataset tuples.
- The method extracts workload- or future-workload-relevant substrings using generalized patterns instead of encoding only literal query strings.
- Rule Generation: Each extraction rule combines a pattern, a string function, and a substring size, while candidate rules are generated for prefix, suffix, and substring predicates.
- Rule Selection: Rule selection minimizes the number of rules covering workload strings under an upper bound on extracted substrings, an NP-hard set-cover formulation addressed greedily.
- String Indexing: A prefix or suffix trie stores extracted substrings and codes, with query representation chosen from the longest matching prefix or suffix.
6. EXPERIMENTS
Experiments on real workloads evaluate estimation quality, string-predicate encoding, and efficiency. The tree-structured and multitask designs improve cost and cardinality estimation, while batching substantially reduces evaluation time.
- Experimental setup: Experiments use real IMDB data and JOB workloads, including numeric-only and complex string predicates, with PostgreSQL plans used for training.IMDB contains 22 tables, and the JOB workload includes 113 test queries.
- Experimental setup: The evaluation compares representation, predicate-embedding, and estimation variants for cardinality and cost targets.Compared representations include LSTM and neural networks; predicate models include Min-Max Pooling and tree-LSTM.
- Numeric workloads: 20% lower mean error for cardinality and 40% lower mean error for cost are reported for the tree-structured model on JOB-light versus MSCN.The tree-structured advantage is more evident on harder queries, where bitmap bias or zero-tuple cases can cause large errors.
- Numeric workloads: More than 2 times lower maximum cost error is reported on Scale, with multitask learning improving generalization on complex queries.The paper summarizes sample bitmaps, tree structure, LSTM, and multitask learning as improving estimation quality.
- String workloads: String embedding improves complex-query estimation by learning correlations among strings, columns, and tables; rule-based embedding further improves cardinality results.On multi-table JOB queries, string embedding improves cost error substantially, including 2 times lower mean and 99th errors for the compared cost models.
- Efficiency: Batch evaluation improves estimation efficiency by one order of magnitude, while TPool is 50% faster than TLSTM and TPoolBatch is 2 times faster than TLSTMBatch.The reported explanation is reduced tree-node computation and increased parallelism for batching, while tree-pooling replaces some predicate-model neural networks.
7. CONCLUSION
The paper concludes that its tree-structured, end-to-end estimator jointly predicts cost and cardinality while encoding query operations, metadata, predicates, and samples. String-value encoding improves generalization, and real-data experiments outperform existing techniques.
- Conclusion: The proposed end-to-end tree-structured estimator predicts both query cost and cardinality.Its model comprises embedding, representation, and estimation layers.
- Conclusion: The model encodes query operations, metadata, query predicates, and samples as inputs.These features are incorporated into the estimator's learning pipeline.
- Conclusion: String-value encoding is designed to improve the model's generalization ability.The conclusion presents this as a central component of the proposed estimator.
- Conclusion: Experiments on real datasets show that the proposed method outperforms existing techniques.The conclusion states this as the overall experimental finding.