How PostgreSQL Generates All Query Execution Plans

When a relational database like PostgreSQL receives a SQL query, there is rarely just one way to execute it. SQL is declarative: you specify what data you want, not how the engine should retrieve it.

A single SQL query can yield dozens or even thousands of functionally equivalent execution paths that return the exact same result set. The responsibility of finding the fastest path falls on the Query Planner and Optimizer.

Before PostgreSQL can choose the cheapest path using its Cost-Based Optimizer (CBO), it must first systematically construct the candidate search space. Here is an architectural breakdown of how PostgreSQL generates execution plans.

---

The Query Execution Lifecycle

When a client submits an arbitrary SQL query to PostgreSQL, it passes through several discrete stages:

graph TD
    A[Client SQL Query] --> B[Parser & Lexer]
    B --> C[Parse Tree]
    C --> D[Rewrite System / Analyzer]
    D --> E[Query Tree]
    E --> F[Planner & Optimizer]
    subgraph Plan Generation & Costing
        F --> G[Generate Candidate Access Paths]
        G --> H[Generate Join Trees & Algorithms]
        H --> I[Cost-Based Evaluation CBO]
    end
    I --> J[Optimal Execution Plan]
    J --> K[Executor Engine]
    K --> L[Result Set to Client]

1. Parsing: The SQL text is converted into a structured parse tree.
2. Analysis and Rewrite: System catalogs validate relations, column types, and apply rewrite rules (such as expanding views).
3. Planning and Optimization: The planner generates valid access paths, evaluates join orders, assigns costs, and outputs the cheapest plan tree.
4. Execution: The executor iterates through the selected plan tree nodes using a volcano-style iterator model (calling ExecProcNode on operators) to fetch and return rows.

---

1. Candidate Table Access Paths (Scan Selection)

The first step in plan generation involves determining how each base table (leaf node in the query tree) can be accessed. Rather than blindly picking an index or falling back to a full table scan, PostgreSQL builds a candidate set of access paths for every relation in the FROM clause.

Consider the query:

SELECT * 
FROM blogs 
WHERE user_id = 1729 
ORDER BY timestamp;

For the blogs relation, the planner evaluates multiple scan candidates:

• Sequential Scan (Seq Scan): Always added to the candidate list as the universal baseline. It reads every heap page sequentially from disk/shared buffers.
• Index Scan on Filter Predicates: If an index exists on user_id, an Index Scan or Bitmap Index Scan path is added. This path traverses the B-Tree index to locate matching tuple IDs (ctids), then retrieves the corresponding heap pages.
• Index Scan on Ordering Predicates: If an index exists on timestamp, the planner considers scanning blogs via the timestamp index. While this might require scanning more rows to satisfy user_id = 1729, it provides rows in pre-sorted order, eliminating a downstream, potentially expensive Sort operator.

All viable scan paths are added to the table’s candidate set to be carried forward into join planning.

---

2. Join Algorithms and Strategies

When multiple tables are involved, PostgreSQL must determine the algorithm used to combine intermediate tuples. Relational engines rely on three primary join implementations:

Join Algorithm	Mechanism	Best Suited For
Nested Loop Join	For every outer row, scan the inner relation. Highly optimized when the inner side can use an index lookup.	Small outer datasets, indexed inner datasets, or non-equijoins.
Merge Join	Both relations must be sorted on the join key. The engine steps through both streams in parallel to find matches.	Large datasets that are already sorted (e.g., via an index) or equijoins with large outputs.
Hash Join	Loads the entire inner relation into an in-memory hash table (hashed by the join key), then streams the outer relation against it.	Large, unsorted relations with equijoin predicates where the build table fits into work_mem.

For a two-table join (e.g., blogs and users), the planner does not arbitrarily pick an algorithm; it evaluates all feasible physical implementations:

• Nested Loop(blogs, users) and Nested Loop(users, blogs)
• Merge Join(blogs, users) and Merge Join(users, blogs)
• Hash Join(blogs, users) and Hash Join(users, blogs)

Swapping the inner and outer relation matters significantly. For example, in a Hash Join, the inner relation is used to build the hash table. Building on the smaller relation saves memory and avoids spilling hash batches to disk (temp_files).

---

3. Join Order Permutations and Combinatorial Explosion

Join order dictates which tables are joined first and which intermediate results are joined later. This problem is mathematically similar to the Matrix Chain Multiplication problem in dynamic programming.

The Importance of Join Sequence

If you join three tables ($A$, $B$, and $C$):

$$(A \bowtie B) \bowtie C \quad \text{vs.} \quad A \bowtie (B \bowtie C)$$

While both yield identical rows, if joining $A$ and $B$ first filters out 99% of the candidate rows, the subsequent join with $C$ processes a fraction of the data. Conversely, joining $B$ and $C$ first might produce a massive intermediate Cartesian-like cross-product, drastically degrading performance.

Exhaustive Search vs. GEQO

As the number of tables ($N$) grows, the number of join order permutations grows factorially or catalan-like depending on the join tree shape (left-deep, right-deep, or bushy trees):

$\text{Total Permutations} \propto O(N!) \text{ or } O\left(\frac{(2N-2)!}{(N-1)!}\right)$

To prevent the planning phase from consuming more time and memory than query execution itself, PostgreSQL introduces a cut-off threshold:

geqo_threshold = 12 (default)

• Exhaustive Dynamic Programming ($N < \text{geqo\_threshold}$): If the FROM clause contains fewer than 12 relations, PostgreSQL performs an exhaustive search across join orders, pruning strictly dominated sub-paths using dynamic programming (System R style).
• Genetic Query Optimizer / GEQO ($N \ge \text{geqo\_threshold}$): When joining 12 or more relations, exhaustive enumeration becomes computationally prohibitive. PostgreSQL shifts to a heuristic, randomized genetic algorithm. It treats join orders as chromosomes, simulating mutations and cross-overs to converge on a near-optimal join order in bounded time.

---

4. Projection and Predicate Pushdown

Beyond scans and joins, the planner applies algebraic transformations to optimize intermediate data volume:

• Predicate Pushdown: Filtering conditions (WHERE clauses) are evaluated at the lowest possible layer—ideally at the storage engine level during the scan—preventing unneeded tuples from traversing the operator pipeline.
• Early Projection (Projection Pushdown): Only the columns specified in SELECT and those necessary for join/filter operations are passed up the execution tree. Stripping unused attributes early reduces tuple width, preserves CPU cache locality, and minimizes memory footprint inside hash tables and sort buffers.

---

Cost Estimation Preview

Once the search space of candidate plans is assembled, the planner passes each plan to the Cost-Based Optimizer (CBO). The CBO computes a synthetic scalar cost using database statistics (collected by ANALYZE and stored in pg_statistic / pg_stats), evaluating:

• I/O Costs: Estimated random disk page accesses (random_page_cost) vs. sequential disk page accesses (seq_page_cost).
• CPU Costs: Tuple processing overhead (cpu_tuple_cost), operator evaluation cost (cpu_operator_cost), and index evaluation cost (cpu_index_tuple_cost).

The plan with the lowest cumulative cost is selected and handed off to the executor.

---

Summary of Key Concepts

• Declarative Optimization: Relational query planners determine the how for a declarative what, mapping out multiple equivalent physical strategies.
• Multi-Path Scans: The optimizer adds sequential scans alongside all relevant index scans (filters and orderings) to relation candidate sets.
• Join Variations: The engine generates combinations across three core join algorithms: Nested Loop, Hash Join, and Merge Join, testing both orientations (inner vs. outer).
• Combinatorial Trade-offs: Join order dictates intermediate cardinality. PostgreSQL balances exhaustive search with heuristic exploration via geqo_threshold (default: 12 tables).
• Pushdown Principles: Projections and predicates are pushed as close to the storage layer as possible to reduce intermediate data movement.