Source-linked AI summary
Neo: A Learned Query Optimizer
Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska, Olga Papaemmanouil, Nesime Tatbul
TL;DR
Query optimizers are powerful but costly to engineer and maintain, while prior learning methods had not demonstrated a complete optimizer at commercial-level performance. Neo uses deep neural networks, reinforcement learning, learned search, and bootstrapping from an existing optimizer to generate plans end to end. Across four database systems and three query datasets, Neo consistently matches or outperforms commercial optimizers, though its current scope remains constrained by query forms, database specificity, and bootstrap requirements.
Problem
Query optimizers require extensive expert engineering and maintenance, while prior learning approaches had not shown an entire optimizer achieving state-of-the-art performance.
Method
Neo is an end-to-end learned optimizer that replaces traditional optimizer components with neural models, uses reinforcement learning, and bootstraps from an existing expert optimizer.
Results
Across four database systems and three query datasets, Neo consistently outperforms or matches existing commercial query optimizers.
Takeaways & Limitations
Neo provides evidence that a learned optimizer can achieve commercial-level query-planning performance and sometimes surpass commercial systems.
Takeaways & Limitations
Neo requires known rewrite rules, supports only project-select-equijoin-aggregate queries, does not generalize across databases, and requires a traditional optimizer for bootstrapping.
Abstract
from arXiv · showhide
Query optimization is one of the most challenging problems in database systems. Despite the progress made over the past decades, query optimizers remain extremely complex components that require a great deal of hand-tuning for specific workloads and datasets. Motivated by this shortcoming and inspired by recent advances in applying machine learning to data management challenges, we introduce Neo (Neural Optimizer), a novel learning-based query optimizer that relies on deep neural networks to generate query executions plans. Neo bootstraps its query optimization model from existing optimizers and continues to learn from incoming queries, building upon its successes and learning from its failures. Furthermore, Neo naturally adapts to underlying data patterns and is robust to estimation errors. Experimental results demonstrate that Neo, even when bootstrapped from a simple optimizer like PostgreSQL, can learn a model that offers similar performance to state-of-the-art commercial optimizers, and in some cases even surpass them.
1. INTRODUCTION
Neo addresses the difficulty of building and maintaining high-performance query optimizers by learning the optimization process end to end. The paper positions Neo as an optimizer that can learn from existing systems, generalize to unseen queries, and approach or exceed commercial performance.
- Motivation: Query optimizers can speed query execution by orders of magnitude, but building and maintaining them requires extensive expert engineering.The paper describes optimizer construction as an expert-driven process that becomes harder as execution and storage engines evolve.
- Motivation: Prior learning approaches improved individual components, but did not demonstrate an entire optimizer with state-of-the-art or commercial-level performance.Earlier methods relied on human-engineered cost models, heuristics, or cardinality estimation and lacked end-to-end evidence.
- Neo: Neo integrates learned query representation, cost modeling, search, cardinality estimation, physical operator selection, and index selection into an end-to-end optimizer.Its design replaces several traditional optimizer components with machine-learning models and a learned search strategy.
- Results: Neo can match or outperform commercial optimizers, while adapting to cardinality-estimation accuracy and customer preferences such as worst-case versus relative performance.The reported results include outperforming commercial optimizers on their own execution engines even when Neo is bootstrapped from PostgreSQL.
- Neo: After training on a representative workload, Neo generalizes to queries it has not encountered before and can learn dataset-specific representations of correlations.The paper evaluates feature engineering and proposes row vector embeddings to represent correlations within the underlying data.
2. LEARNING FRAMEWORK OVERVIEW
Neo replaces the major components of traditional query optimization with learned models and combines expert demonstrations with reinforcement learning. It iteratively improves from observed plan latencies, using neural prediction and search to guide optimization.
- Learning Framework Overview: Neo replaces traditional optimizer components with learned query representations, a neural cost model, learned search, and learned cardinality estimation.Reinforcement learning and learning from demonstration integrate these components into an end-to-end optimizer.
- Expertise Collection: A traditional optimizer supplies initial query execution plans and latencies from a representative sample workload, even when unrelated to the execution engine.These plan/latency pairs form Neo’s initial Experience and bootstrap its value model.
- Model Building: Neo trains a deep neural value model to predict the final execution time of partial or complete plans, then retrains it as new plan latencies arrive.The process repeats for each user query, creating a feedback loop from predicted performance to observed latency.
- Learning Framework Overview: Neo uses a neural network to evaluate plan desirability and a search routine to identify promising execution plans, paralleling AlphaGo’s move evaluation and search.Both systems bootstrap their cost models from expert-generated demonstrations because reinforcement learning is sample-inefficient.
3. QUERY FEATURIZATION
Neo represents queries and partial execution plans as vectors so its value network can predict plan latency. Query encodings capture predicates, while plan encodings describe operators, relations, and scan choices.
- Notation: A partial execution plan is a forest of trees whose internal nodes are joins and whose leaves are table, index, or unspecified scans.Unspecified scans remain undecided until the plan is refined.
- Notation: A complete execution plan has one tree, no unspecified scans, and all execution decisions determined.A plan becomes a subplan of another when scans are specified and its subtrees are combined with joins.
- Query Encoding: Neo’s query encoding captures plan-independent query information, including involved tables and predicates.Its column predicate vector supports one-hot, histogram, and R-Vector representations with increasing expressive power and precomputation requirements.
- Query Encoding: The one-hot encoding records predicate existence, Histogram records predicted selectivity, and R-Vector supplies semantically relevant predicate information.R-Vector is the most expensive option because it requires a model built over the database data.
- Plan Encoding: Plan vectors encode join types and relation-specific scan types, while nonleaf nodes aggregate the corresponding information from their child nodes.Unspecified scans are represented as both index and table scans, and multiple roots can represent subplans awaiting a join.
4. VALUE NETWORK
Neo’s value network estimates the best achievable latency from partial query plans, then combines learned plan evaluation with search to generate complete execution plans. Its tree-based architecture captures local plan patterns, while value iteration uses observed latencies to improve decisions over time.
- Value Network: The value network approximates the best possible latency achievable by completing a partial execution plan.Because the optimal completion is unknown in advance, Neo uses the best latency observed so far as an approximation target.
- Training Objective: Neo trains its value model from complete plans with known latencies and can use alternative cost functions to reflect user preferences.The cost may target total workload latency or performance relative to a specified baseline.
- Network Architecture: The network combines query-level features with dynamically sized plan-tree features through fully connected layers, spatial replication, and tree convolutions.The query representation is transformed through fully connected layers, then replicated across plan-tree nodes before tree processing.
- Tree Convolution: Tree convolution filters slide across parent-child triangles to detect local execution-plan patterns, such as join combinations and operator-relevant properties.Shared filters can process arbitrarily sized plan trees, and multiple layers can build increasingly complex representations.
- DNN-Guided Plan Search: Neo combines the value network with a search procedure because the network predicts plan quality but does not directly produce an execution plan.The resulting value-iteration approach alternates between estimating plan values and using those estimates to guide search.
- DNN-Guided Plan Search: Combining value estimation with search makes Neo less sensitive to value-model noise or inaccuracies and produces significantly better query plans than value-based selection without search.The paper contrasts search-guided value iteration with greedy action selection in Q-learning-style approaches.
5. ROW VECTOR EMBEDDINGS
Neo’s row-vector embeddings represent query predicates using semantic relationships learned from database values, including correlations within and across tables. These representations provide signals for optimization when conventional cardinality assumptions are inaccurate and can help with previously unseen predicates.
- R-Vector Featurization: R-Vector represents each query predicate using semantically relevant row-vector information learned from the database itself.It is Neo’s most advanced predicate encoding and requires constructing a model over database data.
- R-Vector Featurization: Word2vec embeddings exploit the parallel between words in sentences and correlated values appearing together in database rows.Neo uses these embeddings to encode relationships across columns and tables.
- R-Vector Featurization: Neo trains embeddings from table rows and from partially denormalized joins to capture both within-table and cross-table correlations.The second variant joins large fact tables with smaller foreign-key-related tables before treating resulting rows as training sentences.
- R-Vector Featurization: The t-SNE projection shows semantically meaningful clusters of actor names whose relationships span multiple IMDB tables.Nearby points in the projection represent nearby points in the original high-dimensional embedding space.
- Analysis: Correlated keywords and genres have higher embedding similarity and higher true cardinality, giving the model a feature that can partly substitute for precise cardinality estimation.The example compares keyword-genre relationships such as “love” and “romance.”
- Analysis: Neo selected hash joins instead of PostgreSQL’s nested loop joins and executed the example query 60% faster.PostgreSQL’s uniformity and independence assumptions led it to estimate the final joined cardinality near 1.
- Analysis: Row-vector embeddings can provide useful information for predicates not encountered during training when those predicates have similar learned correlations.The paper presents this as an advantage of learning semantic relationships in the database.
- Limitations: The technique lacks formal guarantees that word2vec will produce helpful features and is supported as early evidence mainly for similar semantically rich datasets.The authors state that they do not know whether the approach works on every imaginable database.
6. EXPERIMENTS
Neo is evaluated across multiple database systems and workloads using held-out queries, with PostgreSQL-generated plans providing initial expertise. It improves on PostgreSQL and matches or exceeds commercial optimizers in most reported settings.
- Experimental setup: Experiments generally train on 80% of queries and test on the remaining 20%, with TPC-H using disjoint query templates.Results use fifty randomly initialized neural networks and a 250ms search cutoff.
- Experimental setup: Neo is evaluated on PostgreSQL, SQLite, Microsoft SQL Server, and Oracle across JOB, TPC-H, and Corp workloads.Corp contains a 2TB dataset and 8,000 internal-dashboard queries.
- Overall performance: After 100 training iterations, Neo produces PostgreSQL JOB plans taking 60% of the original optimizer’s average execution time.The comparison uses R-Vector encoding on a held-out workload, where lower relative performance is better.
- Overall performance: 10% faster plans are reported for Neo than for commercial optimizers on Microsoft SQL Server for JOB and Corp.The improvement comes from query plans without runtime system modifications; TPC-H is the exception where Neo does not outperform both commercial systems.
- Overall performance: Neo creates plans as good as or better than open-source and commercial optimizers, although the cited comparison reports median performance after 100 training episodes.The authors identify reduced-episode training time and robustness to imputations as follow-up questions.
6.3 Training Time
Neo’s training behavior is assessed through learning curves, wall-clock milestones, feature comparisons, generalization tests, robustness analyses, and per-query outcomes. It can become competitive within hours, while performance depends on representations and can vary across queries.
- Convergence and training: Neo is evaluated after every episode over 100 training episodes, using relative performance to the native optimizer with median curves.An episode retrains the network, chooses and executes plans for training queries, and adds results to experience.
- Convergence and training: Neo consistently learns to outperform PostgreSQL in less than two hours and matches or exceeds every optimizer within half a day.These times exclude training the query encoding; 1-Hot and Histogram encoding costs are negligible in the cited discussion.
- Demonstration data: Randomly sampled join orderings can increase JOB query execution times by 100x to 1000x relative to a reasonable plan, making zero-knowledge latency training difficult.The authors describe demonstration data as a practical way to avoid exceptionally poor initial plans.
- Featurization: R-Vector encodings provide the best overall JOB performance, while 1-Hot performs worst and Histogram improves over 1-Hot by representing predicate cardinality.The R-Vector advantage is attributed to greater semantic information about the underlying database.
- Robustness to estimation errors: Neo’s output varies with PostgreSQL cardinality estimates for queries with at most three joins but largely ignores them for queries with more than three joins.With true cardinalities as inputs, the model varies predictions across join counts, indicating feature reliance changes with reliability.
- Per-query performance: Neo improves many JOB queries by up to 40 seconds but makes some slower, including query 24a, which becomes 8.5 seconds slower.The authors conclude that Neo can respond to different optimization goals and be customized for user needs.
6.5 Search
The search analysis examines how optimization time and query complexity interact. Queries with more joins require more search time because their plan spaces are larger.
- Search-time sensitivity: Neo’s query performance is measured relative to the best observed performance while varying a fixed search-time cutoff.The experiment uses PostgreSQL executions and queries selected by join count from JOB.
- Search-time sensitivity: Queries with more joins require more optimization time because they have larger search spaces.The authors note that 250ms is acceptable for a 17-join query in many scenarios, though other options may be preferable when it is not.
6.6 Row vector training time
R-Vector training time grows with dataset size and may be substantial, but the resulting query-processing gains can repay this cost under sustained workloads.
- Training cost: Row-vector training time is proportional to dataset size for both the joins and no-joins variants.The implementation uses gensim without additional optimizations; JOB is approximately 4GB.
- Training cost: Row-vector training can take three hours on JOB and up to 27 hours on Corp.The reported range illustrates the practical cost of constructing the representations.
- Payback: The joins variant averages 5% faster query processing than Histogram, while the no-joins variant averages 3% faster.On Corp, the authors estimate the joins variant pays back after 540 hours of processing, versus 15 hours for the no-joins variant.
- Scope boundary: Neo’s row-vector behavior on changing databases is not analyzed, leaving possible staleness and retraining requirements for future work.The impact depends on how quickly the underlying data distribution shifts.
7. RELATED WORK
Prior work explored learning components of query optimization, including adaptive processing, join-order search, scheduling, and cardinality estimation. These efforts motivated Neo’s end-to-end learning-based optimizer.
- LEO learned from cardinality-estimation mistakes but still depended on human-engineered cost models, search strategies, and developer-tuned heuristics.
- Earlier systems used reinforcement learning for fine-grained adaptive query processing and dynamic execution improvement.
- ReJOIN extended deep reinforcement learning for join-order enumeration, while Decima learned workload-specific scheduling policies with graph neural networks.
8. CONCLUSIONS
Neo is presented as an end-to-end neural optimizer that generates efficient query plans and iteratively improves through reinforcement learning and search. Across multiple systems and datasets, it matches or outperforms commercial optimizers, while generalization and bootstrapping remain future directions.
- Neo is the first end-to-end learning optimizer to generate highly efficient query execution plans using deep neural networks.
- Neo iteratively improves through reinforcement learning combined with a search strategy.
- Across four database systems and three query datasets, Neo consistently outperforms or matches commercial optimizers tuned over decades.
- Future work includes generalizing learned models to unseen schemas and evaluating bootstrapping from more primitive or advanced commercial optimizers.
A. NEURAL NETWORK MODEL
Neo’s value network combines query-level information with tree-structured plan representations, processes the augmented forest using tree convolutions, pools node features, and predicts a state value.
- The model passes query-level information through fully connected layers, then appends the resulting vector to every tree node.
- Tree convolution applies filterbanks recursively to each node and its left and right children while preserving the tree structure.
- Three consecutive tree convolution layers process the forest, with each tree convolved independently using its filterbank.
- Dynamic pooling takes the elementwise maximum across every channel, flattening all tree nodes into one vector of size finalout.
- Final fully connected layers reduce the pooled representation to a scalar used to predict the value of a particular state.