PaperlayerView exact revision on arXiv

Source-linked AI summary

Lero: A Learning-to-Rank Query Optimizer

Rong Zhu, Wei Chen, Bolin Ding, Xingguang Chen, Andreas Pfadler, Ziniu Wu, Jingren Zhou

arXiv:2302.06873v2cs.DBcs.AI

TL;DR

Predicting plan latency is difficult and costly, motivating Lero to learn which of two plans is better rather than estimate exact cost. Built on a native optimizer, Lero reduces execution time in PostgreSQL and other learned optimizers in its reported experiments.

  • Problem

    Predicting plan latency is difficult and costly because it depends on data, workload, and system conditions, while accurate estimates do not necessarily improve plan selection.

    Source: §1.1 · p. 2

  • Method

    Lero builds on the native optimizer and trains a pairwise model to rank candidate plans, continuously learning from their observed performance.

    Source: §1 · p. 1, §2 · p. 3

  • Results

    Lero reduces PostgreSQL’s native optimizer execution time by up to 70% and other learned query optimizers’ execution time by up to 37%.

    Source: §1.2 · p. 3

  • Takeaways & Limitations

    In the reported evaluation, Lero adapts to various query workloads and dynamically changing data while maintaining stable performance.

    Source: §1.2 · p. 3

    The paper assumes a constant resource budget per plan execution; modeling different budgets would require runtime observations under varied budgets.

    Source: §5 · p. 8

Abstract

from arXiv · show

A recent line of works apply machine learning techniques to assist or rebuild cost-based query optimizers in DBMS. While exhibiting superiority in some benchmarks, their deficiencies, e.g., unstable performance, high training cost, and slow model updating, stem from the inherent hardness of predicting the cost or latency of execution plans using machine learning models. In this paper, we introduce a learning-to-rank query optimizer, called Lero, which builds on top of a native query optimizer and continuously learns to improve the optimization performance. The key observation is that the relative order or rank of plans, rather than the exact cost or latency, is sufficient for query optimization. Lero employs a pairwise approach to train a classifier to compare any two plans and tell which one is better. Such a binary classification task is much easier than the regression task to predict the cost or latency, in terms of model efficiency and accuracy. Rather than building a learned optimizer from scratch, Lero is designed to leverage decades of wisdom of databases and improve the native query optimizer. With its non-intrusive design, Lero can be implemented on top of any existing DBMS with minimal integration efforts. We implement Lero and demonstrate its outstanding performance using PostgreSQL. In our experiments, Lero achieves near optimal performance on several benchmarks. It reduces the plan execution time of the native optimizer in PostgreSQL by up to 70% and other learned query optimizers by up to 37%. Meanwhile, Lero continuously learns and automatically adapts to query workloads and changes in data.

1 INTRODUCTION

Lero addresses the difficulty and cost of predicting plan latency by learning to rank plans while building on the native optimizer. The introduction presents its pairwise model, plan exploration, and reported execution-time reductions.

1.1 From Heuristic-Based Costing Models to Machine Learning Models

  • Traditional cost-based optimizers use estimated costs to select plans, while learned approaches replace or augment optimizer components with machine-learning models.The introduction describes end-to-end systems that predict plan values and systems that steer a native optimizer using candidate plans.Source: §1.1 · pp. 1–2
  • Existing learned optimizers can suffer unstable performance, high learning cost, and slow model updating as data and execution latency change.The introduction notes that some models require tens to hundreds of training iterations, with complex datasets taking days or weeks.Source: §1.1 · p. 2
  • Latency prediction is difficult because execution depends on data, workload, and system conditions, while training requires extensive plan execution, data collection, and model search.The introduction questions whether optimization requires predicting exact latency, since more accurate cost or cardinality estimates do not necessarily improve optimization.Source: §1.1 · p. 2

1.2 A Learning-to-Rank Query Optimizer

  • Lero trains a pairwise classifier to identify the better of two plans rather than predict exact latency or cardinality.The introduction describes pairwise training as requiring fewer samples and less training time than pointwise approaches.Source: §1.2 · p. 2
  • Lero retains the native optimizer’s initial behavior, explores optimization opportunities, and uses a non-intrusive design intended to integrate with existing DBMSs.It is designed to avoid a lengthy cold-start training process and leverage existing database optimization experience.Source: §1.2 · p. 3
  • Lero reduces PostgreSQL’s native optimizer execution time by up to 70% and other learned query optimizers’ execution time by up to 37%.The reported evaluation also says Lero adapts faster with stable performance to varied workloads and dynamically changing data.Source: §1.2 · p. 3

2 SYSTEM OVERVIEW

Lero generates candidate plans with the native optimizer, selects among them using a pairwise comparator, and trains that comparator from execution statistics. Candidate plans support both query execution and model learning.

2 SYSTEM OVERVIEW

  • Lero’s pairwise approach compares two plans and continuously learns from their observed performance.The system overview characterizes pairwise ranking as balancing model accuracy and learning efficiency for this task.Source: §2 · p. 3
  • For each query, the explorer generates diversified candidate plans with the native optimizer, and the comparator selects one for execution.The comparator learns from executed plan pairs labeled by which plan is better, using execution latency as the performance metric; ties are broken arbitrarily.Source: §2 · p. 3
  • In the background, the trainer executes other candidate plans when resources become available, stores their statistics, and uses them to update the comparator.This uses otherwise idle resources to gather observations without affecting normal database services; the exploration strategy can migrate to databases with a cardinality estimator.Source: §2 · pp. 3–4
  • The explorer varies subquery cardinality estimates before passing them to the native optimizer to produce candidate plans of different quality and diversity.The candidates are intended to include potentially good plans while giving the comparator examples to distinguish better from worse plans.Source: §2 · p. 3

3 A LEARNED PLAN COMPARATOR

Lero’s comparator learns to rank plans pairwise rather than predict their latency, using plan embeddings to compare candidates. It is pretrained from native optimizer costs, then updated from execution data to adapt to changing workloads and data.

3.1 Model Design

  • PlanEmb encodes tree-structured plans using operator, cardinality, output-width, and table features, then applies tree convolution to produce an embedding.Estimated cost is excluded because it is strongly correlated with cardinality and row width and may add cost-model inaccuracy.Source: §3.1 · p. 4
  • Pairwise comparison uses the difference between plan embeddings to rank plans, rather than requiring an embedding to predict latency or another performance metric.The comparison output is a logistic score, and the smaller one-dimensional embedding is more preferable.Source: §3.1 · p. 4
  • The comparator’s commutativity and transitivity properties induce a total order, allowing Lero to select the plan with the minimum embedding.The randomized comparison procedure assigns preference probabilities to the two plans.Source: §3.1 · p. 4

3.2 Model Training

  • Lero pretrains on synthetic plans labeled with native estimated costs, then trains pairwise on executed candidates labeled by their measured latencies.The online training data comes from runtime statistics, and shared embedding parameters are updated using gradients from both plans in each pair.Source: §3.2 · p. 5
  • Because relative plan order is more robust than latency labels when data changes, the authors report that the comparator adapts quickly as tuples are inserted or deleted.The authors say their experimental study verifies this intuition.Source: §3.2 · p. 5

4 PLAN EXPLORATION STRATEGY

Lero explores candidates by tuning cardinality estimates and uses its comparator to select among them. Its heuristic explorer focuses on promising nearby plans and grouped subqueries, while background executions provide data for continued learning.

4 PLAN EXPLORATION STRATEGY

  • Lero explores candidates both to find a good execution plan and to expose promising alternatives for pairwise evaluation and model updates.The authors contrast this with query-level hint strategies, which can miss combinations of locally optimal operations and depend on system-specific hint sets.Source: §4 · pp. 5–6

4.1 Cardinality as Knob for Plan Explorer

  • The explorer scales cardinality estimates before the native cost model generates candidates, a platform-independent tuning approach supported by interfaces in most DBMSs.Different estimates can change join orders and physical operations; candidate plans can also vary in shape.Source: §4.1 · p. 6
  • Under mild cost-model assumptions, brute-force tuning can produce a plan no worse than the optimal plan by a factor of α^4, but its combinations are too costly to enumerate.The method relies on tuning estimates across subqueries, and the resulting candidate list is too long for model training.Source: §4.1 · p. 6

4.2 Priority-Based Heuristic Methods

  • The heuristic explores scaling factors nearest 1 first, tunes estimates for all size-k subqueries together, and generates at most O(q·log_α Δ) candidates.Grouping exploits the tendency for same-sized subqueries to be underestimated together; larger subqueries can be harder to estimate because of cross-table correlations.Source: §4.2 · p. 7
  • Scaling estimates can encourage different plan shapes and join orders: small factors favor bushy plans in one example and large factors favor a different join order in another.For the join-order example, small factors favor the plan that first joins the larger estimated pair, while large factors favor the other plan.Source: §4.2 · p. 7
  • The implementation tunes estimates through a hook to the native cardinality estimator, and the PostgreSQL version uses pg_hint_plan for that hook.The authors say the approach can be ported to databases with similar cardinality-estimator interfaces.Source: §4.2 · p. 7

5 EXTENSIONS AND DISCUSSION

The comparator can use multidimensional plan embeddings, while the paper’s evaluated design assumes a constant resource budget per plan. Incorporating budget information is proposed as a possible extension, with broader-budget training left for future work.

5 EXTENSIONS AND DISCUSSION

  • The comparator can be extended to d-dimensional plan embeddings and a learnable linear comparison layer.The proposed extension aims to summarize more statistical and structural information about each plan.Source: §5 · pp. 7–8
  • The paper assumes a constant resource budget for each plan execution.The discussion treats resource allocation and performance isolation as separate from query optimization.Source: §5 · p. 8
  • Adding resource budget to comparator features could support comparisons under different runtime budgets, but training would need observations across those budgets.The authors leave this augmented design for future work.Source: §5 · p. 8

6 EXPERIMENTAL EVALUATION

Lero performs better than PostgreSQL and competing learned optimizers across the reported benchmarks, while experiments examine deployment, adaptation, and design choices. Its advantages include low optimization overhead and near-fastest-found performance on several benchmarks.

6.2.1 Performance with Stable Models.

  • Lero achieves the best overall performance, with execution time 70%, 44%, 21%, and 13% less than PostgreSQL on IMDB, STATS, TPC-H, and TPC-DS, respectively.Lero is close to the fastest found plans on STATS, TPC-H, and TPC-DS; it also reduces execution time versus Bao by 26%, 25%, 37%, and 5% on those four benchmarks, respectively, and is around 20% faster than Bao+ on three benchmarks.Source: §6.2.1 · p. 9

6.2.2 Analysis of Performance Improvement/Regression.

  • After 200 IMDB queries and 100 queries on each other benchmark, Lero consistently beats PostgreSQL; on STATS, accumulated execution time is 47% lower than PostgreSQL, 38% than Bao, and 23% than Bao+.Lero consistently outperforms PostgreSQL across benchmarks, while Bao and Bao+ sometimes perform worse; only 9 of 146 STATS queries slowed down by more than one second for Lero, versus 29 each for Bao and Bao+.Source: §6.2.3 · pp. 9–10, §6.2.2 · p. 9

6.3 Query Optimization Cost

  • Lero’s extra optimization cost is at most 2.4% of execution time on IMDB and below 0.1% on STATS, TPC-H, and TPC-DS.The added work is generating candidate plans and using the comparator to select one.Source: §6.3 · p. 10

6.4 Adapting to Dynamic Data

  • On dynamic STATS data, Lero beats PostgreSQL, Bao, and Bao+ in both deployment and stable-model settings; after 1,000 queries, accumulated execution time is 50% below PostgreSQL and 38% below Bao/Bao+.After all data changes, Lero’s performance is 33%, 29%, and 10% better than PostgreSQL, Bao, and Bao+, respectively.Source: §6.4 · p. 10

6.5 Importance of Pre-Training

  • Pre-training lets Lero consistently outperform PostgreSQL after 100 queries, compared with nearly 200 queries for a cold-start model.The pre-training procedure takes around five minutes per benchmark and does not require executing queries.Source: §6.5 · pp. 10–11

6.6 Plan Exploration Strategies

  • Lero’s plan explorer generates fewer candidate plans per query than hint-set tuning, with a higher percentage faster than PostgreSQL and greater diversity; it also outperforms random exploration.Replacing Lero’s explorer with hint-set tuning performs worse.Source: §6.6 · p. 11

6.7 Effects of Idle Resource

  • With only 12.5% of earlier queries’ candidate plans executed on idle resources, Lero converges after 500 queries on IMDB and 200 on STATS.Limited idle resource slows learning and convergence but has little impact on ultimate performance; Lero’s initial performance is no worse than PostgreSQL’s.Source: §6.7 · pp. 11–12, Table 4 · p. 12

6.8 Comparison with Balsa

  • On the original JOB workload, Balsa matches or outperforms Bao but performs worse than Bao+ and Lero, even after comprehensive training.The comparison uses 94 training queries and 19 test queries, with both random and slowest-query test splits.Source: §6.8 · p. 12

7 RELATED WORK

Prior learned query-optimization work often targets individual components, while end-to-end approaches and optimizer steering still face difficulties associated with predicting cost or latency. Lero combines plan exploration with pairwise plan comparison for end-to-end optimization.

7 RELATED WORK

  • Learning-based work on individual optimizer components, including cardinality estimation, cost models, and plan enumeration, does not necessarily improve overall query-optimization performance.The approaches include query-driven and data-driven cardinality estimation [50], learned cost models, and join-order methods [23].Source: §7 · p. 12
  • End-to-end learned optimizers and Bao’s hint-based steering of a native optimizer face deficiencies associated with predicting cost or latency.Lero instead combines plan exploration and pairwise comparison to improve end-to-end optimization quality.Source: §7 · p. 12
  • Unlike index tuning with a pairwise classifier, Lero uses a plan explorer and comparator together to search query-optimization plan space, with different feature encodings and model architectures.The index-tuning comparator determines whether a plan under a new index configuration improves on the initial configuration.Source: §7 · p. 12

8 CONCLUSIONS

Lero applies pairwise learning-to-rank and a plan exploration strategy alongside the native optimizer to improve query optimization. PostgreSQL experiments demonstrate improved query performance and adaptation to changing data and workloads.

8 CONCLUSIONS

  • Lero trains a binary classifier to compare plans rather than predict exact latency or cardinalities, and combines that pairwise approach with the native optimizer and plan exploration.The conclusion describes the approach as more efficient and effective for query optimization.Source: §8 · p. 12
  • Extensive PostgreSQL evaluation demonstrates improved query performance and adaptation to changing data and workloads.The conclusion does not specify quantitative results in this passage.Source: §8 · p. 13

A COMPARATOR WITH 𝑑-𝑑𝑖𝑚EMBEDDING

  • The appendix extends the comparator from one-dimensional to d-dimensional plan embeddings by changing the final embedding layer’s output dimension and using a learnable linear comparison layer.The comparator takes two d-dimensional plan embeddings and outputs which plan is better.Source: A COMPARATOR WITH 𝑑-𝑑𝑖𝑚EMBEDDING · p. 14

A.1 Selecting the Best Plan using Comparators

For d-dimensional embeddings, Lero selects the plan with the most randomized wins across pairwise comparisons. With one-dimensional embeddings, choosing the lowest embedding gives the same selection in expectation.

A.1 Selecting the Best Plan using Comparators

  • For d-dimensional embeddings, Lero compares candidate plans pairwise and selects the plan with the most randomized wins, breaking ties arbitrarily.Randomized wins count the other candidates that the pairwise selection algorithm ranks below a given plan.Source: §A.1 · p. 14
  • With one-dimensional embeddings, the lowest PlanEmb value determines the comparator’s preferred plan and selects the best candidate in expectation.The paper states that this choice has the most randomized wins in expectation.Source: §A.1 · p. 14
  • The d-dimensional selection rule maximizes expected randomized wins for the candidate with the lowest PlanEmb value.The paper establishes this property from its expected-wins expression.Source: §A.1 · p. 14

A.2 Performance of Comparator with Different Dimension of Plan Embedding

Higher-dimensional plan embeddings performed worse than one-dimensional embeddings in the reported IMDB and STATS experiments. The authors use one-dimensional embeddings, citing their performance and simpler plan selection.

A.2 Performance of Comparator with Different Dimension of Plan Embedding

  • 1.4 times to 2.2 times as long: on IMDB, Lero with d∈{2, 4, 8, 16} took longer than with d=1; on STATS, d>1 also exceeded native PostgreSQL.On STATS, execution time with d>1 was around 1.8 times longer than with d=1.Source: Table 5 · p. 14, §A.2 · p. 14
  • Higher-dimensional embeddings require more training data and time, and the training workload may not capture enough information for plan comparison.The authors say this may result in selecting a plan that is not the best one.Source: §A.2 · p. 15
  • Lero uses one-dimensional embeddings because they already improve on the native optimizer and make best-plan selection more convenient than with d>1.With d>1, PlanEmb does not define a total order over plans, although Proposition 3 gives an equivalent selection method.Source: §A.2 · p. 15

B EXPLORATION HEURISTIC BASED ON PLAN DIAGRAM

Plan diagrams vary query predicate parameters to expose alternative plans that may avoid selectivity-sensitive choices. Their candidate coverage is constrained: generating them beyond two tables is unaffordable, while tuning two tables may not provide sufficiently diverse plans.

B EXPLORATION HEURISTIC BASED ON PLAN DIAGRAM

  • Errors in predicate-selectivity estimates can propagate through plan search, producing wrong join orders and suboptimal join types.A diagram varies one or more predicate parameters to map regions to optimizer plans.Source: B EXPLORATION HEURISTIC BASED ON PLAN… · p. 15
  • Varying predicate parameters creates plan-diagram candidates that may improve on selectivity-error-sensitive plan choices and explore uncertainty in the native optimizer’s selectivity estimates.Within each region of the parameter space, the optimizer outputs the same plan.Source: B EXPLORATION HEURISTIC BASED ON PLAN… · p. 15
  • Beyond two tuned tables, generating a plan diagram is unaffordable; at two tables, candidates may lack diversity, with under 3% average improvement and under 5% of queries faster than PostgreSQL.On STATS, even the best plan-diagram candidate did not provide significant performance improvement.Source: B EXPLORATION HEURISTIC BASED ON PLAN… · p. 15

C.1 Rank-Specific Analysis

Lero selects plans with stronger rank-specific results than other query optimizers, and its comparator model outperforms the alternative from on IMDB and TPC-H. The comparison also highlights the value of encoding plan structure for plan selection.

C.1 Rank-Specific Analysis

  • Lero selects plans in P1 and P5 for a much higher percentage of queries than other query optimizers.The rank-specific metrics record the ratio of queries whose selected plan falls among the top-k fastest plans; Table 6 reports results for P1 and P5.Source: Table 6 · p. 15, §C.1 · p. 15

C.2 Effects of Comparator Model

  • On IMDB and TPC-H, Lero performs much worse when using the comparator model from instead of its own.Figure 11 presents performance curves for Lero with different comparator models.Source: Figure 11 · p. 15, §C.2 · p. 15
  • For plan selection, Lero encodes node-level operator, estimate, and table information and uses tree convolution to capture plan structure and table correlations.The comparator in flattens a plan into per-operator totals for estimated costs and processed data, which fits its index-selection goal.Source: §C.2 · p. 15
Loading 2302.06873v2…