Do you know your query does not run directly on the postgreSQL server, it is taken in and then planned upon, optimized and then run, Reminds me of a certain certain compilation process, will be discussing both of them in this one.

When you give a SQL query to a PostgreSQL server, it doesn’t just directly execute your query.

It plans it first.

Consider a simple query:

SELECT * FROM blogs
WHERE user_id = '1739'
ORDER BY ts;

At a high level, the actual processing looks something like:

SQL
 ↓
Parse + Analyze
 ↓
Rewrite
 ↓
Generate Possible Execution Paths
 ↓
Estimate Cardinalities
 ↓
Estimate Cost
 ↓
Choose Join Order
 ↓
Choose Join Algorithms
 ↓
Choose Scan / Access Methods
 ↓
Physical Plan
 ↓
Executor

The planner and optimizer part actually contains these kinds of steps:

1. Generate possible execution paths

2. Estimate cardinalities

3. Estimate cost

4. Choose join order

5. Choose join algorithms

6. Choose scan/access methods

7. Build the physical plan

But these steps are not necessarily sequential.

It is more like:

                SQL
                 ↓
       What does the query mean?
                 ↓
       Generate alternatives
          /      |       \
       Scan    Join     Sort
        |       |        |
      paths   orders   methods
          \      |      /
           Cost estimation
                 ↓
          Cheapest plan
                 ↓
              Executor

Even the individual steps mentioned in the planner don’t necessarily happen one after another in the exact order above.

So, how does a planner plan a query?

#

1. It looks at the scan

#

The planner may check which columns need to be scanned, whether indexes are available for the columns involved, and which candidate access paths can help search for the required data.

The goal is to optimize the overall cost.

There can be multiple ways of getting the same data, and the planner needs to figure out which one is expected to be cheaper.

2. Then there are joins

#

Suppose we have a query that joins blogs and users.

The planner needs to consider different ways of performing that join.

It can potentially consider:

• User -> Blog

• Blog -> User

And for each of these, there are different join algorithms.

There are actually three major ways joins work:

• Nested Loop Join

• Merge Join

• Hash Join

So conceptually, you can think of the planner considering possibilities such as:

User -> Blog
    ├── Nested Loop
    ├── Merge Join
    └── Hash Join

Blog -> User
    ├── Nested Loop
    ├── Merge Join
    └── Hash Join

And this gets much more interesting as the number of relations increases.

Interestingly, if you have joins beyond a certain threshold, PostgreSQL can transfer join-order optimization to Genetic Query Optimization (GEQO).

Before that, PostgreSQL can perform a more exhaustive search over possible join orders / join trees.

The purpose here is to decide the strategy in which the join operations should happen.

Why?

Because this is a trade-off between query planning time and query execution time.

You don’t want to spend too much time searching for the perfect plan if the search itself starts becoming expensive.

Instead, PostgreSQL can use statistics and heuristics to reduce the search space.

You can also configure the threshold at which GEQO is used.

You can think of it like:

Small join search space
        ↓
Standard optimizer

Large join search space
        ↓
GEQO
        ↓
Heuristic search

3. Projection and Column Pruning

#

The planner knows which columns are required by each part of the query and can avoid carrying unnecessary columns through intermediate plan nodes where possible.

The planner attaches projection only to the most appropriate plans and prunes unnecessary projections from others, saving compute.

At the storage level, PostgreSQL stores table data in the form of a heap.

So when you scan the heap, conceptually, you only need to carry forward the data that is required for things like the WHERE clause and the SELECT clause. The remaining columns don’t need to be carried through the rest of the plan.

PostgreSQL also uses a buffer cache / shared buffers to cache database pages in memory.

The executor generally works with pages and tuples and pulls them through the buffer manager.

After reading all of this — how a declarative statement made by the user gets sent to the database, optimized, turned into a physical plan, and finally executed — it reminds me of a certain process.

THE COMPILATION OF CODE.

Both compilers and query optimizers take a high-level description of computation and search for a more efficient lower-level representation that preserves its semantics.

And then they execute it.

Compilation

#

The compilation process for something like C++ in a nutshell looks like:

C++ Source
    ↓
Lexical Analysis
    ↓
Parsing
    ↓
AST
    ↓
Semantic Analysis
    ↓
IR
    ↓
Optimization
    ↓
Machine Code Generation
    ↓
Executable

Or you might have read about it earlier as a division between frontend and backend stages of compilation.

Front-End — Analysis Phase

#

Lexical Analysis: Reads the source code text and converts character streams into meaningful units called tokens, such as keywords, identifiers, and operators.

Syntax Analysis / Parsing: Takes the tokens and builds a tree structure, such as a parse tree or syntax tree, to check whether the code follows the language’s grammar rules.

Semantic Analysis: Checks for logical and type consistency, ensuring that operations use compatible data types and valid scopes.

Intermediate Code Generation: Creates a machine-independent intermediate representation of the code that acts as a bridge between high-level and low-level code.

Back-End — Synthesis Phase

#

Code Optimization: Improves the intermediate code to make the final program run faster or use less memory without changing its output.

Code Generation: Translates the optimized intermediate code into final target machine code or assembly code.

The similarities

#

The similarities between the two have these components mapped to each other.

This is conceptual, not an actual one-to-one mapping:

Once you see it, it almost shouts at you:

Damn, everything boils down to similar fundamental principles. xD xD xD

Both are trying to solve a search problem

#

Especially when you zoom into the optimization part of both processes, you realize that both have a search problem.

A compiler creates a search space of possible ways to execute a program and tries to find a way that works well considering things like:

• Register allocation

• Instruction sequences

• Loop transformations

• etc.

While in databases, during optimization, you have to find things like:

• The best join order

• The best access method

• Other physical operator choices

• Parallelization strategies

• Aggregation strategies

• etc.

The core of both processes is the same.

You describe your intent in a declarative way, without going down to the basics of exactly how and which process should be used inside it.

You describe what you want in an abstract fashion.

The respective processing layers take this as an input and produce a finalized, deterministic output.

For the ones with low attention span, describing it in a nutshell:

High-level intent
       ↓
Multiple valid implementations
       ↓
Search / optimization
       ↓
Cost model / heuristics
       ↓
Good implementation
       ↓
Execution

Both query optimization and compiler optimization are search problems because a high-level program/query can have many semantically equivalent implementations.

The optimizer must explore a subset of those possibilities and use a cost model to choose an implementation that is expected to perform well.

Neither PostgreSQL nor a modern compiler exhaustively searches the entire space. Doing so would generally be computationally infeasible.

The interesting engineering problem is therefore not just finding an optimal solution, but finding a sufficiently good solution within a reasonable optimization budget.

Is there any core difference in methodology?

#

Yes.

A compiler produces code that will run n number of times.

So if compilation takes some extra time, it isn’t necessarily a headache. You can afford to spend more time during compilation because that cost can be amortized over many executions.

In databases, the query may be run just once.

Or the next time it is run, it may be run with separate values.

So planning time itself becomes a concern.

If you remember, we discussed Genetic Query Optimization earlier.

It was for the same reason.

In a nutshell:

A compiler may spend significant time optimizing code because that cost can be amortized over millions or billions of executions.

A database planner often has a much smaller optimization budget because a query may only execute once.

Therefore, query optimization is fundamentally a trade-off between planning time and execution time.