From Logical to Physical: Optimizing Query Execution

Hello! Welcome to the final lesson in our module on Query Optimization.

In our last session, we delved into the System R dynamic programming algorithm, a powerful method for determining the optimal logical plan—that is, the most efficient sequence of joins. We now have a blueprint of what operations to perform and in what order. Today, we'll learn how to turn that blueprint into a fully executable plan.

Our learning outcome is to translate a logical query plan into a physical plan by selecting appropriate algorithms for each operator. This is the crucial last step where the abstract relational algebra operators are mapped to concrete, highly-tuned algorithms that the database engine will actually run. For you, this is a fantastic look under the hood at how a database system makes its final, performance-critical decisions.

From Logical "What" to Physical "How"

Let's start by solidifying the distinction between logical and physical plans. A logical plan expresses the semantics of the query—the "what"—without committing to any specific implementation. A physical plan is the concrete execution strategy—the "how."

A logical Join operator simply states that two relations must be joined. A physical plan replaces this with a specific algorithm like Hash Join, Sort-Merge Join, or Index Nested Loop Join. Similarly, a logical Scan is replaced by a physical Table Scan or Index Scan.

To see this distinction explained clearly, let's watch a short segment from one of the CMU lectures.

#15 - Query Planning & Optimization (CMU Intro to Database Systems)

This video clip clearly explains the difference between logical and physical plans and their respective operators. It sets the stage perfectly for understanding today's topic.

Please watch from 14:01 to 17:26. Pay close attention to how Andy Pavlo describes the logical plan as defining 'what' to do, while the physical plan specifies 'how' to do it, including the choice of algorithms and access methods.

To make this even more concrete, here is a visualization of a physical query plan.

Physical Query Plan Example — This diagram illustrates a physical plan. Notice the specific operator choices like "File scan" and "Nested loop" join. The "on the fly" annotations indicate that the selection and projection are pipelined directly with the join output, avoiding the need to write intermediate results to disk.

Choosing the Best Physical Implementation

Even with a fixed logical plan (e.g., a specific join order), the optimizer's job is far from over. The choice of physical operators can change the query cost by orders of magnitude. The optimizer explores these choices, using its cost model to find the most efficient combination.

The following video provides an excellent walkthrough of this process. It starts with a naive, disastrously slow physical plan and iteratively transforms it into a highly efficient one by making smarter choices for the physical operators.

#15 - Query Planning & Optimization (CMU Intro to Database Systems)

This is a key video for today's lesson. It demonstrates, step-by-step, how different physical plan choices for the same logical query lead to dramatically different performance. This is the core of physical query optimization.

Watch from 03:29 to 11:38. Follow along as the plan is improved by: Replacing a Cartesian Product with a Nested Loop Join. Swapping the Nested Loop Join for a Sort-Merge Join. Eliminating materialization costs through pipelining. Applying predicate pushdown to enable an efficient Index Nested Loop Join. Notice how each change is a decision about the physical implementation.

As you saw, the process is a search for the lowest-cost plan. The optimizer evaluates different algorithms for joins, different access paths for scans, and different data flow strategies (materialization vs. pipelining), all guided by the cost estimates we discussed in previous lessons.

Test your understanding!

Consider a join between Customers (1,000 pages) and Orders (500,000 pages) on Customers.c_custkey = Orders.o_custkey. A query also includes the filter Customers.c_mktsegment = 'BUILDING'.

Assume the optimizer has already decided on the logical plan: first apply the filter on Customers, then join the result with Orders.

If there is a B+ Tree index on Orders.o_custkey, which physical join algorithm is likely a top candidate? Why?
If both the filtered Customers relation and the Orders relation happen to be sorted on their respective custkey columns (perhaps due to an "interesting order" from a previous step), which physical join algorithm becomes extremely attractive?

Show answer

Index Nested Loop Join (INLJ) would be an excellent choice. The optimizer would scan the Customers table (perhaps using an index on c_mktsegment if one exists) to get the small set of customers in the 'BUILDING' segment. Then, for each of these customer tuples, it would use the c_custkey to perform a highly efficient probe into the B+ Tree index on Orders to find the matching orders.
Sort-Merge Join becomes the best choice. Since both inputs are already sorted on the join key, the "sort" phase of the algorithm is free. The database can proceed directly to the "merge" phase, which is a single, highly efficient linear scan through both relations. This would likely be cheaper than the repeated index probes of an INLJ.

Systematic Search: Bottom-Up vs. Top-Down

So, how does an optimizer systematically find this best physical plan? There are two main strategies.

1. Two-Phase Optimization (Bottom-Up)

This is the classic approach used by System R. It neatly separates logical and physical optimization.

Phase 1 (Logical Optimization): Find the single best logical plan (i.e., join order), just as we did in the last lesson using dynamic programming.
Phase 2 (Physical Optimization): Take the winning logical plan and traverse it. For each logical operator, enumerate the possible physical implementations. Calculate the cost of each, considering the physical properties of the data being fed into it (e.g., is it sorted?), and choose the cheapest physical operator. This process also determines where to insert operators like Sort if a downstream operator requires sorted input (e.g., for a Sort-Merge Join).

2. Integrated Optimization (Top-Down)

More modern optimizers, following the Volcano/Cascades framework, integrate logical and physical planning into a single, unified search. This approach is more flexible and powerful.

It works by applying a series of transformation rules to a query representation.

Logical-to-Logical Rules: These transform one logical plan into an equivalent logical plan (e.g., A ⋈ B -> B ⋈ A, or pushing down a predicate).
Logical-to-Physical Rules: These replace a logical operator with a concrete physical operator (e.g., Join -> Hash Join).

The optimizer starts with an initial high-level representation and explores the vast space of possible plans by applying these rules, pruning branches of the search that are provably more expensive than a plan it has already found.

Let's watch a video explaining this top-down approach and then look at a blog post from CockroachDB that describes their real-world implementation.

F2023 #14 - Query Planning & Optimization (CMU Intro to Database Systems)

To understand the modern alternative to the two-phase approach, this video explains the 'top-down' optimization strategy, pioneered by the Volcano and Cascades frameworks. It shows how logical and physical transformations are interleaved in a single search.

Watch from 49:51 to 56:45. Focus on the core idea: you start with a complete but abstract plan and recursively refine it by applying rules to make it more physical and concrete. This contrasts with the bottom-up approach of building a plan from individual tables.

Now, let's see how these concepts are applied in a real system. The following blog post from CockroachDB explains how their cost-based optimizer uses this transformation-based approach.

How we built a cost-based SQL optimizer

This technical blog from Cockroach Labs provides a great applied perspective on building a modern, cost-based optimizer. It reinforces the concepts of transformations and introduces a key data structure used to manage the search.

Please read the following sections: Under the Hood: This section visualizes a query plan as a tree, which is the basic structure the optimizer works with. Transformations: This is the core of the article. It shows how the optimizer applies a series of simple, incremental transformations to turn a terrible plan into a good one. Notice the example transformation expressed in their special language, Optgen. The Memo: This section describes the 'memo', an ingenious data structure used to efficiently store the massive number of equivalent plans generated during the search. This is a key implementation detail in modern optimizers.

Conclusion

Congratulations on completing the Query Optimization module! You've journeyed from parsing a SQL string all the way to a fully specified, cost-optimized physical execution plan. This final step—translating the logical plan to a physical one—is where the database commits to the exact algorithms that will run, a decision critical for performance.

Key Takeaways:

A logical plan specifies the sequence of operations (the "what"), while a physical plan specifies the concrete algorithms and access methods (the "how").
The optimizer's final task is to select the lowest-cost physical implementation for a given logical plan.
This selection involves costing out different physical operators like Hash Join vs. Sort-Merge Join and Index Scan vs. Table Scan, based on data statistics and physical properties.
Modern optimizers, like those based on the Volcano/Cascades framework, use a unified, rule-based search that interleaves logical transformations and physical operator selection.
Data structures like the Memo are essential for efficiently managing the exponential search space of possible plans.

Preview of the Next Lesson

So far, we have focused on executing a single query as fast as possible. But a real database system handles thousands of operations concurrently from many different users. In the next module, Concurrency Control, we will explore how a DBMS ensures that these simultaneous operations don't interfere with each other and corrupt the database. We will begin by defining serializability, the gold standard for correctness in concurrent transaction processing.