SQL to Relational Algebra: Query Optimization

From SQL to a Logical Plan

A SQL query describes the what (the desired result), not the how (the steps to get it). The database's first job is to parse this query into a more structured, procedural format that it can work with. This process typically involves a few stages:

1. SQL Query: The raw text from the application.
2. Abstract Syntax Tree (AST): The parser turns the text into a tree structure representing the query's components.
3. Logical Plan: The AST is converted into an initial plan using relational algebra operators. This plan is "logical" because it defines the sequence of operations but not the specific algorithm for each (e.g., it says "join," not "hash join").
4. Physical Plan: The optimizer transforms the logical plan and annotates it with specific algorithms, creating a physical plan that the execution engine can run.

At its core, a logical plan is an expression in relational algebra, which we can visualize as a tree. The leaves of the tree are the tables, and data flows up from the leaves through a series of operators until the final result is produced at the root.

Here are a few basic examples of this translation:

To get a better sense of this process in action, let's watch the beginning of a lecture from CMU's database course.

The Canonical Translation of SELECT-FROM-WHERE

As you saw in the video, the most direct, or "canonical," way to translate a simple SELECT-FROM-WHERE query follows a standard recipe. This process forms the initial logical plan that the optimizer will then improve.

For a query of the form:

SELECT attribute_list
FROM R1, R2, ...
WHERE condition;

The canonical translation into relational algebra is:
${\pi }_{\text{attribute\_list}}\left({\sigma }_{\text{condition}}(R_1\times R_2\times \dots )\right)$

This corresponds to a tree with three levels of operators:

1. Cartesian Products (×): At the bottom, all tables in the FROM clause are combined using Cartesian products.
2. Selection (σ): In the middle, the WHERE clause condition is applied as a filter.
3. Projection (π): At the top, the SELECT list is used to discard unwanted columns.

Let's ground this with a formal, written explanation.

This canonical translation is conceptually simple but, as the video highlighted, operationally very inefficient. No modern database would actually execute a large Cartesian product if it could be avoided. This initial translation is merely a starting point.

From Canonical Plan to Optimized Logical Plan

The real power of translating SQL to relational algebra is that it gives the optimizer a mathematical structure that can be transformed using a set of equivalence rules. The optimizer's first job is to apply these rules to convert the naive canonical plan into a more efficient logical plan.

The most important initial transformation is to replace Cartesian products followed by selections with joins.

Let's watch how these transformations are applied to improve our initial plan.

These rewrites—pushing down selections and projections, and converting products to joins—are heuristic rules that almost always result in a better plan by reducing the size of intermediate results flowing up the operator tree.

SELECT E.ename
FROM Emp E, Dept D
WHERE E.did = D.did AND D.dname = 'Toy';

Handling More Complex SQL Constructs

Real-world SQL includes more than just simple SELECT-FROM-WHERE blocks. The translation process must also handle JOIN syntax, subqueries, GROUP BY, and set operations. While the details can get complex, the principle remains the same: convert the SQL construct into an equivalent relational algebra operator or expression.

Let's briefly survey how this is done by looking at the relevant sections of the reference document. You don't need to memorize every rule, but you should understand that a corresponding algebraic construct exists for each SQL feature.

This systematic translation for a wide range of SQL features is what makes relational algebra the lingua franca of query optimization. It provides a consistent framework for representing and manipulating any query, no matter how complex.

Conclusion

In this lesson, we've bridged the gap between declarative SQL and the procedural world of query execution. You've learned how database systems translate SQL queries into logical plans represented by relational algebra, which is the essential first step toward finding an efficient execution strategy.

Key Takeaways:

• SQL is "What," Relational Algebra is "How": Translation turns a declarative specification into a procedural plan.
• Canonical Translation: A simple SELECT-FROM-WHERE query can be naively translated to a Project(Select(Cross-Product)) structure. This is a crucial starting point but is highly inefficient.
• Relational Algebra Enables Optimization: The true purpose of this translation is to represent the query in a form where algebraic equivalence rules can be applied.
• Key Transformations: The most important initial optimizations involve replacing cross products with joins and "pushing down" selections and projections as early as possible to reduce the amount of data processed by subsequent operators.
• A Rich Toolkit: The extended relational algebra has operators (like semi-join, anti-join, and aggregation) to handle the full spectrum of SQL features, including subqueries and GROUP BY.

Preview of the Next Lesson

We've seen that we can transform a logical plan into different, but equivalent, forms. For example, (A ⋈ B) ⋈ C is equivalent to A ⋈ (B ⋈ C). But how does the optimizer know which form is better? In our next lesson, we will focus on the rules and heuristics for this process. We will dive deeper into how to apply logical query transformations, such as predicate pushdown and join reordering, to systematically improve a query plan.