Inside PostgreSQL: How Queries Are Parsed, Optimized, and Executed

Relational Algebra and SQL

Relational algebra defines a set of operators (selection, projection, join, set operations, grouping, aggregation, etc.) that work on relations. SQL is a higher‑level, human‑readable language that is internally translated back into relational‑algebra operators before further processing. DataLog extends relational algebra with recursive capabilities.

PostgreSQL Query Processing Flow

The lifecycle of a user‑issued SQL statement in PostgreSQL consists of parsing, semantic analysis, optional rewrite, optimization, and execution.

Parsing The entry point pg_parse_query invokes the Flex scanner scan.l and the Bison parser gram.y . The parser produces a SelectStmt (or another statement node) that captures the syntactic structure of the query.

Semantic Check The function parse_analyze() calls the appropriate transformXXXXStmt() (e.g., transformSelectStmt() ) to verify object existence, column validity, and overall semantic correctness. It converts the SelectStmt into a richer Query structure that records internal object IDs, flags for aggregates, window functions, sub‑links, and expression nesting. Example of an illegal aggregate usage: select 1 from x where max(x2) > 1; Correct placement of aggregates using a nested query: select (select max(x.x2) from y) from x; Query Rewrite If user‑defined rewrite rules (created with CREATE RULE ) exist, they modify the Query tree; otherwise this step is skipped.

Query Optimization The planner receives the Query and produces a query plan. Major optimization phases include:

Sub‑query elimination (pulling sub‑queries to the top level and converting IN clauses to semi‑joins or hash joins).

Expression preprocessing (constant folding, predicate push‑down, simplifying sub‑links).

Group‑by column reduction via check_functional_grouping (removing functionally dependent columns).

Outer‑join to inner‑join conversion when safe.

Join‑order selection using condition‑driven dynamic programming.

Clause‑level optimizations for GROUP BY, ORDER BY, LIMIT, choosing between sort‑based and hash‑based algorithms based on cost estimates.

Query Execution The executor initializes the plan with ExecutorStart , runs it via ExecutorRun , and finalizes resources with ExecutorFinish . Execution interacts with the transaction manager, storage manager, and logging subsystem.

Sequential Scan (SeqScan) Algorithm

SeqScan is the simplest executor operator, scanning a table sequentially according to the physical page order.

Page Structure Each PostgreSQL page contains a header, an array of ItemIdData entries, and the tuple data. The header stores the LSN, the offset of the first free space ( pd_lower ), and the offset of the last tuple ( pd_upper ).

Initialization The entry function SeqNext creates a HeapScanDesc that points to the start block (normally block 0) and prepares to iterate over ItemId entries.

Sync Scan Optimization If another backend has recently scanned the same table, PostgreSQL records a “sync start page” in shared memory. New scans can begin at that page, reducing I/O by leveraging cached pages. The update interval is controlled by SYNC_SCAN_REPORT_INTERVAL (≈128 KB / BLCKSZ ).

Page Traversal For each page, the executor reads the pd_linp offset array, fetches the tuple address, and checks visibility with HeapTupleSatisfiesVisibility , which implements MVCC visibility rules.

Continuation After processing all tuples on a page, the executor moves to the next page, preserving the scan state in HeapScanDesc for subsequent calls.

These steps illustrate how PostgreSQL transforms a high‑level SQL statement into low‑level page reads and tuple evaluations, providing a concrete example of modern relational database query processing.