Query Optimization with Historical-Based Optimization Framework in Presto

    By: 

    Jay Narale, Software Engineer, Uber

    In this blog I’ll discuss the historical-based optimization (HBO), a framework open-sourced by Meta (see their presentation from PrestoCon) and used in Presto. The HBO framework enables advanced query optimization techniques by leveraging historical execution statistics. This approach offers a more efficient query execution strategy through its unique cost estimation, plan transformations, and the incorporation of historical data. Let’s explore how this framework revolutionizes query optimization and boosts query performance in distributed systems.

    Understanding the Need for Query Optimization

    Query optimization is essential in distributed data processing systems like Presto because multiple execution paths can yield the same result. The efficiency of these paths, however, can differ drastically, impacting both speed and resource usage.

    For example, consider two ways to execute a query that performs a join between two tables:

    • Plan A: Aggregate data first, then filter, and finally join.
    • Plan B: Filter the data first, then aggregate, and perform the join.

    In most cases, Plan B is more efficient because it reduces the data set earlier in the process, thus minimizing the computational workload. This type of decision-making happens during the query optimization phase, and the optimizer must choose the most efficient execution plan based on various rules and heuristics.

    Overview of Presto’s Query Optimizer

    Presto uses a rule-based optimizer built on a core data structure called the plan. The query optimizer applies a series of transformations to this plan, optimizing it before it’s executed by workers. Each transformation is governed by specific rules. For example, one rule might remove unnecessary operations, while another reorders joins for more efficiency.

    Presto relies on heuristic-based optimization, in contrast to more complex cost-based optimizers like Volcano or Cascades, seen in engines like Calcite. In Presto, each transformation yields only one “best” plan at a given time. This framework allows for faster decision-making but can miss out on globally optimal plans without historical or cost-based insights.

    Historical-Based Optimization (HBO) in Presto

    The HBO framework provides a significant enhancement by introducing historical statistics into Presto’s optimization process. This approach relies on past query execution data, such as row counts, data sizes, and plan shapes, to refine future optimizations.

    a) Plan Structure and Rules

    Each optimization rule in Presto evaluates the structure of a query plan. For instance, a rule might define that if a plan involves a specific join type, it can be reordered for efficiency. These transformations are applied iteratively until the best plan is produced.

    However, what sets HBO apart is its integration of cost metrics into these transformations. Using historical statistics, the optimizer can now better assess the CPU, memory, and network requirements of a given plan and make more informed decisions.

    b) Cost Metrics and Plan Comparison

    One key aspect of HBO is its use of plan costs to compare different query plans. Plan cost is represented as a vector of metrics, including CPU, memory, and network usage. The vector is then reduced to a weighted scalar value, making it easier to compare plans and select the most efficient one.

    For example, if a query is compute-heavy, the optimizer may give more weight to CPU usage while reducing the emphasis on memory consumption. This dynamic tuning makes the HBO framework highly adaptable to specific workloads.

    Optimization Example Using HBO

    Consider a real-world example where HBO shines. In a benchmark query (Query 5 from the TPC-H dataset), the optimizer initially selected an inefficient join ordering, leading to the left side of the join having 150 rows and the right side having 2.8 billion rows. This imbalance resulted in unnecessary data transfer and memory usage.

    After applying historical statistics, the optimizer revised the join order so that the smaller table (150 rows) was used on the build side of the join, reducing the amount of data transferred over the network. Additionally, this allowed for a broadcast join (which is faster), replacing the initial hash join. The result was a significant performance improvement due to the better utilization of resources.

    Presto’s Historical-Based Optimization Framework Architecture

    The HBO framework integrates seamlessly with Presto’s query lifecycle, as illustrated below:

    1. SQL Query Submission: Users submit their SQL queries.
    2. Planning Phase: Presto generates a plan through its series of transformations, applying optimizers along the way.
    3. Historical Statistics Store: The optimizer fetches historical statistics from a Redis store, which holds information on past plan executions.
    4. Local Memory Caching: These statistics are cached locally for each query, reducing the overhead of fetching data from Redis multiple times during query execution.
    5. Execution Phase: Workers execute the optimized plan, and statistics about this run are stored back in Redis for future optimizations.

    a) Fetching Historical Stats

    The HBO optimizer fetches relevant statistics by mapping each node in the query plan to a corresponding stats-equivalent plan node. This node remains consistent even after multiple transformations, ensuring that the stats fetched align accurately with the query being optimized.

    b) Updating the Statistics

    Once query execution is complete, execution stats are aggregated and stored back into the Redis store. By maintaining an updated store of plan-node statistics, Presto can optimize future queries more effectively, utilizing historical insights to reduce execution time and resource consumption.

    Implementation and Deployment

    To leverage HBO in your Presto deployments, follow these steps (you can also check out the docs for full instructions)

    1. Redis Setup: Install Redis as the external store for historical statistics.
    2. Install HBO Plugin: The open-sourced HBO plugin is available via Meta’s repository. Install it as part of your Presto deployment
    3. Configure the Plugin: Fine-tune the configuration, such as the TTL for stored statistics and the maximum size of the plan history.
    4. Monitor Performance: Metrics for fetching and storing stats can be monitored via the JMX exporter.

    Performance and Results

    Deploying HBO in production clusters yielded impressive results, especially for queries involving complex joins. The P90 latency for fetching stats was approximately 10 microseconds, and the P99 latency was 105 microseconds.

    While there is some added planning time, the performance gains during execution far outweigh this cost, especially in large query environments where plan optimizations can lead up to 50% improvements in query speed.

    Conclusion

    The historical-based optimization (HBO) framework represents a significant leap forward for query optimization in Presto. By integrating historical execution statistics into the planning process, Presto is now capable of making more informed, cost-based decisions that can drastically improve query performance. With support for Redis-based storage and efficient local caching mechanisms, HBO offers a scalable solution for handling complex, distributed query workloads in production environments.

    For teams using Presto in production, adopting HBO can lead to measurable improvements in resource efficiency and query execution times, making it a valuable addition to the modern data infrastructure toolkit.

    I presented this at a Presto virtual meetup, which you watch on-demand here.

    Please check our paper which we presented at VLDB 24 here for more details.