Inside Presto Optimizer
Tags: presto, sql, database, bigdata
Published: 2021-04-20 06:49:23

# Abstract
Presto is an open-source distributed SQL query engine for big data. Presto provides a connector API to interact with different data sources, including RDBMSs, NoSQL products, Hadoop, and stream processing systems. Created by Facebook, Presto received wide adoption by the open-source world ([Presto](https://github.com/prestodb), [Trino](https://github.com/trinodb)) commercial companies (e.g., [Ahana](https://ahana.io/), [Qubole](https://www.qubole.com/)).

Presto comes with a sophisticated query optimizer that applies various rewrites to the query plan. In this blog post series, we investigate the internals of Presto optimizer. In the first part, we discuss the optimizer interface and the design of the rule-based optimizer.

Please refer to the [original paper](https://research.fb.com/publications/presto-sql-on-everything/) by Facebook to get a better understanding of Presto's capabilities and design.

We will use the Presto Foundation fork [version 0.245](https://github.com/prestodb/presto/tree/release-0.245) for this blog post.

# Relational Tree
Presto optimizer works with relational operators. Similarly to other SQL optimizers, such as [Apache Calcite](https://www.querifylabs.com/blog/assembling-a-query-optimizer-with-apache-calcite), Presto performs syntax and semantic analysis of the original SQL string and then produces the logical relational tree:
1. The ANTLR-based [parser](https://github.com/prestodb/presto/blob/release-0.245/presto-parser/src/main/antlr4/com/facebook/presto/sql/parser/SqlBase.g4) converts the original query string into an abstract syntax tree (AST)
1. The [analyzer](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/analyzer/Analyzer.java#L77) performs the semantic validation of the AST.
1. The [converter](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/RelationPlanner.java) creates the logical relational tree from the AST.

Every node in the tree represents a relational operation and implements a common [PlanNode](https://github.com/prestodb/presto/blob/release-0.245/presto-spi/src/main/java/com/facebook/presto/spi/plan/PlanNode.java) interface, which exposes a unique node's ID, node's inputs, and node's output. The interface also allows traversing the tree with a visitor pattern, used extensively during the optimization. Examples of relational operations: [TableScanNode](https://github.com/prestodb/presto/blob/release-0.245/presto-spi/src/main/java/com/facebook/presto/spi/plan/TableScanNode.java), [ProjectNode](https://github.com/prestodb/presto/blob/release-0.245/presto-spi/src/main/java/com/facebook/presto/spi/plan/ProjectNode.java), [FilterNode](https://github.com/prestodb/presto/blob/release-0.245/presto-spi/src/main/java/com/facebook/presto/spi/plan/FilterNode.java), [AggregationNode](https://github.com/prestodb/presto/blob/release-0.245/presto-spi/src/main/java/com/facebook/presto/spi/plan/AggregationNode.java), [JoinNode](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/plan/JoinNode.java).

Consider the following query:
```sql
SELECT 
    orderstatus, 
    SUM(totalprice) 
FROM orders 
GROUP BY orderstatus
```

The associated query plan might look like this:
![Presto plan](https://uploads-ssl.webflow.com/5fe5c475cb3c75040200bfe6/607d33d2b04e03f8aad679dd_plan-example.png)

# Optimizer Interface

When the logical plan is ready, we can start applying optimizations to it. In Presto, there is the general [PlanOptimizer](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/optimizations/PlanOptimizer.java) interface that every optimization phase implements. The interface accepts one relational tree and produces another.

```java
public interface PlanOptimizer
{
    PlanNode optimize(
        PlanNode plan,
        Session session,
        TypeProvider types,
        PlanVariableAllocator variableAllocator,
        PlanNodeIdAllocator idAllocator,
        WarningCollector warningCollector
    );
}
```

The optimization program builder [PlanOptimizers](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/PlanOptimizers.java#L212) creates a list of optimizers that are invoked sequentially on the relational tree. Optimization problems often split into several phases to keep logical and computational complexity under control. In Presto, there are more than 70 optimization phases that every relational tree will pass through.

The majority of optimization phases use the rule-based optimizer that we will discuss further. Other phases rely on custom optimizers that make no use rules but apply a custom transformation logic. For example, the [PredicatePushDown](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/optimizations/PredicatePushDown.java) optimizer moves filters down in the relational tree, and [PruneUnreferencedOutputs](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/optimizations/PruneUnreferencedOutputs.java) removes unused fields that could be generated during the AST conversion or the previous optimization phases. We will discuss the most important custom optimizers in the second part of this blog post series.

Presto may also [reoptimize](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/PlanOptimizers.java#L620) the query plan in runtime. The details of this process are out of the scope of this blog post.

# Rule-Based Optimizer

Presto uses the rule-based [IterativeOptimizer](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/IterativeOptimizer.java) for the majority of optimization phases. In rule-based optimization, you provide the relational tree and a set of pluggable optimization rules. A **rule** is a self-contained code that defines the relational tree **pattern** it should be applied to and the **transformation** logic. The optimizer then applies the rules to the relational tree using some algorithm. The main advantage of rule-based optimizers is extensibility. Instead of having a monolithic optimization algorithm, you split the optimizer into smaller self-contained rules. To extend the optimizer, you create a new rule that doesn't affect the rest of the optimizer code. Please refer to our [blog post](https://www.querifylabs.com/blog/rule-based-query-optimization) to get more details about rule-based optimization.

Rule-based optimizers could be either cost-based or heuristic. In [cost-based optimizers](https://www.querifylabs.com/blog/what-is-cost-based-optimization), a particular transformation is chosen based on the estimated cost assigned to a plan. Heuristic optimizers don't use costs and could produce arbitrary bad plans in the worst case. Presto relies on a rule-based heuristic optimization, although some specific rules use costs internally to pick a single transformation from multiple alternatives. An example is the [ReorderJoins](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/rule/ReorderJoins.java#L102) rule that selects a single join order with the least cost from multiple alternatives.

We now describe the most important parts of the Presto rule-based optimizer: the `Memo` class, rule matching, and the search algorithm.

## MEMO
MEMO is a data structure used primarily in cost-based optimizers to encode multiple alternative plans efficiently. The main advantage of MEMO is that multiple alternative plans could be encoded in a very compact form. We discuss the design of MEMO in one of our [blog posts](https://www.querifylabs.com/blog/memoization-in-cost-based-optimizers).

Presto also uses a MEMO-like data structure. There is the [Memo](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/Memo.java) class that stores groups. The optimizer [initializes](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/IterativeOptimizer.java#L89) the `Memo`, which populates groups via a recursive traversal of the relational tree. However, every group in `Memo` may have only [one operator](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/Memo.java#L254). That is, Presto doesn't store multiple equivalent operators in a group. Instead, as we will see below, Presto unconditionally replaces the current operator with the transformed operator. Therefore, the `Memo` class in Presto is not a MEMO data structure in a classical sense because it doesn't track equivalent operators. In Presto, you may think of the group as a convenient wrapper over an operator, used mostly to track operators' reachability during the optimization process.

![Presto MEMO](https://uploads-ssl.webflow.com/5fe5c475cb3c75040200bfe6/607d35a463c67eb5fef29ffd_memo.png)

## Rule Matching

To optimize the relational tree, you should provide the optimizer with one or more rules. Every rule in Presto implements the [Rule](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/Rule.java) interface.

First, the interface defines the [pattern](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/Rule.java#L35), which may target an arbitrary part of the tree. It could be a single operator (filter in the [PruneFilterColumns](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/rule/PruneFilterColumns.java#L37) rule), multiple operators (filter on top of the filter in the [MergeFilters](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/rule/MergeFilters.java#L34) rule), an operator with a predicate (join pattern in the [ReorderJoins](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/rule/ReorderJoins.java#L114) rule), or anything else.

Second, the interface defines the [transformation logic](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/Rule.java#L42). The result of the transformation could be either a new operator that replaces the previous one or no-op if the rule failed to apply the transformation for whatever reason.

## Search Algorithm

Now, as we understand the Presto rule-based optimizer's core concepts, let's take a look at the search algorithm.
1. The `Memo` class is [initialized](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/IterativeOptimizer.java#L89) with the original relational tree, as we discussed above.
1. For every `Memo` group, starting with the root, the method [exploreGroup](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/IterativeOptimizer.java#L102) is invoked. We look for rules that [match](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/IterativeOptimizer.java#L133) the current operator and fire them. If a rule produces an alternative operator, it [replaces](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/IterativeOptimizer.java#L144) the original operator unconditionally. The process continues until there are no more available transformations for the current operator. Then we optimize operators' inputs. If an alternative input is found, it may open up more optimizations for the parent operator, so we [reoptimize](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/IterativeOptimizer.java#L108) the parent. Presto relies on timeouts to terminate the optimization process if some rules continuously replace each other's results. Think of `b JOIN a`, that replaces `a JOIN b`, that replaces `b JOIN a`, etc. You may run the [TestIterativeOptimizer](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/test/java/com/facebook/presto/sql/planner/iterative/TestIterativeOptimizer.java) test to see this behavior in action.
1. In the end, we [extract](https://github.com/prestodb/presto/blob/release-0.245/presto-main/src/main/java/com/facebook/presto/sql/planner/iterative/IterativeOptimizer.java#L99) the final plan from `Memo`.

This is it. The search algorithm is very simple and straightforward.

The main drawback is that the optimizer is heuristic and cannot consider multiple alternative plans concurrently. That is, at every point in time, Presto has only one plan that it may transform further. In the [original paper](https://research.fb.com/publications/presto-sql-on-everything/) from 2019, Facebook engineers mentioned that they explore an option to add a cost-based optimizer:

> We are in the process of enhancing the optimizer to perform a more comprehensive exploration of the search space using a cost-based evaluation of plans based on the techniques introduced by the Cascades framework.

There is also a [document](https://github.com/prestodb/presto/wiki/New-Optimizer) dated back to 2017 with some design ideas around cost-based optimization.

# Summary

In this blog post, we explored the design of the Presto optimizer. The optimization process is split into multiple sequential phases. Every phase accepts a relational tree and produces another relational tree. Most phases use a rule-based heuristic optimizer, while some rules rely on custom logic without rules. There were some thoughts to add the cost-based optimizer to Presto, but it hasn't happened yet.

In the second part of this series, we will explore the concrete optimization rules and custom phases of Presto's query optimization. Stay tuned!

We are always ready to help you with your SQL query optimizer design. Just [let us know](https://www.querifylabs.com/#contact-form).