Skip to content

Cellular Anatomy of PostgreSQL: The Query Processing & Execution Engine

1. Introduction: The Central Nervous System of Query Execution

When an SQL text string ("SELECT * FROM orders WHERE amount > 100;") arrives over the network socket from an application client, how does the PostgreSQL engine transform that string into mechanical disk block reads, CPU comparisons, and result packets?

The database engine processes every query through a strict 5-stage metabolic pipeline:

[SQL Text String]
       |
       v  1. Parser (gram.y / scan.l)
[Abstract Syntax Tree (RawStmt)]
       |
       v  2. Analyzer (parse_analyze.c)
[Parsed & Validated Query Tree (Query)]
       |
       v  3. Rewriter (rewriteHandler.c)
[Rewritten Query Tree (Views inlined, RLS policies attached)]
       |
       v  4. Planner / Optimizer (planner.c)
[Physical Execution Plan Tree (PlannedStmt)]
       |
       v  5. Executor (execMain.c / Volcano Iterator)
[Stream of Result Tuples]

2. Stages 1–4: From Human SQL to Physical Execution Tree

Stage 1: Parsing (Lexer & Parser)

  • Located in src/backend/parser/scan.l (Flex Lexer) and gram.y (Bison Parser).
  • Converts raw text into tokens (SELECT, FROM, identifiers) and builds a raw parse tree of C structs (SelectStmt, ResTarget, RangeVar).
  • Zero Catalog Lookups: The parser knows grammar rules, but does not know if the table orders actually exists.

Stage 2: Semantic Analysis (parse_analyze)

  • Located in src/backend/parser/analyze.c.
  • Looks up table and column names in the system catalog (pg_class, pg_attribute).
  • Resolves types, resolves operators, checks column permissions, and transforms the raw tree into a typed Query struct.

Stage 3: The Query Rewriter (QueryRewrite)

  • Expands database Views: Replaces table references with the view's underlying subquery.
  • Applies Row-Level Security (RLS): Transparently rewrites the WHERE clause to inject security policies (WHERE tenant_id = '...').
  • Applies table Rules (CREATE RULE).

Stage 4: The Optimizer / Planner (standard_planner)

  • Located in src/backend/optimizer/plan/planner.c.
  • Calculates statistical costs (\(C_{seq}\), \(C_{index}\), \(C_{hash}\), \(C_{nestloop}\)) using table statistics (pg_statistic).
  • Outputs a tree of physical plan nodes: a PlannedStmt containing nodes like SeqScan, IndexScan, HashJoin, Sort, or Aggregate.

3. Stage 5: The Volcano Iterator Execution Model

PostgreSQL executes queries using the Volcano (Iterator) Model (designed by Goetz Graefe).

In this architecture, every node in the execution plan tree is an iterator that exposes three fundamental C interface functions: 1. ExecInitNode(): Recursively initializes the plan node, allocates memory contexts, and prepares child nodes. 2. ExecProcNode(): Demands and returns exactly ONE tuple at a time (TupleTableSlot). 3. ExecEndNode(): Recursively shuts down the plan tree and frees memory.

                  +-----------------------------------+
                  |         Limit Node                |
                  +-----------------+-----------------+
                                    ^
                   Demand 1 Tuple   |  Returns 1 Tuple
                                    v
                  +-----------------+-----------------+
                  |         Sort Node                 |
                  +-----------------+-----------------+
                                    ^
                   Demand 1 Tuple   |  Returns 1 Tuple
                                    v
                  +-----------------+-----------------+
                  |      Nested Loop Join Node        |
                  +--------+-----------------+--------+
                          /                   \
        Demand Outer Row /                     \ Demand Inner Row
                        v                       v
          +-------------+-------+       +-------+-------------+
          | Index Scan: orders  |       | Index Scan: users   |
          +---------------------+       +---------------------+

The Stream-Driven Advantage:

PostgreSQL never materializes an entire query result into memory unless an explicit blocking node requires it (such as a full SORT or HASH JOIN). * For a 50-million row query with LIMIT 10, the execution engine only pulls 10 tuples from the root node and immediately halts execution! Memory consumption is near-zero.

4. The Anatomy of a Tuple Slot: TupleTableSlot

Located in src/include/executor/tuptable.h. To pass rows between plan nodes without expensive copying, the executor wraps data in a polymorphic TupleTableSlot:

The 4 Physical Flavors of TupleTableSlot:

  1. TTS_HEAPTUPLE: Points to a physical disk tuple directly inside shared_buffers or a private heap tuple.
  2. TTS_BUFFERED: Pins the 8KB page in shared_buffers while reading. Unpins when the slot is cleared.
  3. TTS_VIRTUAL: A zero-copy optimization! The slot contains no tuple bytes; it simply holds an array of memory pointers pointing directly to values in preceding expressions.
  4. TTS_MINIMAL: A stripped-down tuple with no xmin/xmax/infomask headers, used inside in-memory Hash tables and Sort runs to save RAM.

5. Memory Management: MemoryContext (Why Postgres Never Leaks)

In C applications, managing memory (malloc() and free()) is notorious for memory leaks and dangling pointers. PostgreSQL completely avoids manual free() tracking through Hierarchical Memory Contexts (AllocSet) (src/backend/utils/mmgr/aset.c).

                    TopMemoryContext (Lives for entire connection lifetime)
                              |
                +-------------+-------------+
                |                           |
        CacheMemoryContext          MessageContext (Reset after every network packet)
                                            |
                                    ExecutorState (Created when query starts)
                                            |
                                    ExprContext (Reset per evaluated row!)

The Cellular Mechanism:

  • When a query begins, Postgres allocates memory in the ExecutorState context.
  • During expression evaluation (e.g., computing md5(col) in a loop of 100,000 rows), memory is allocated in an ExprContext.
  • At the end of every row iteration, Postgres does NOT call free() on individual pointers. It calls MemoryContextReset(), which instantly wipes the entire memory pool in a single CPU operation!
  • When the query completes, the entire ExecutorState tree is destroyed. Memory leaks are structurally impossible.