Understanding PostgreSQL Query Optimizer: Rules, Subqueries, and Cost Models

Basic Principles of the Optimizer

The optimizer transforms a SQL statement into an execution plan using two major stages: rule‑based (logical) optimization and cost‑based (physical) optimization. Logical optimization rewrites the query tree with algebraic equivalence rules, while physical optimization selects the cheapest physical operators based on a cost model.

Syntax Tree Generation

Parsing begins with lexical analysis (scan.l) producing tokens, followed by grammar parsing (gram.y) that builds a syntax tree. The syntax tree is then converted to a query tree (semantic analysis) using system catalog metadata, and finally to a plan tree (execution plan).

Subquery and Subjoin Lifting

Subqueries appearing in the FROM clause are treated as subjoins. Lifting moves a subquery/subjoin to a higher level when it creates a nested‑loop pattern, reducing execution cost. PostgreSQL distinguishes ANY‑type and EXISTS‑type subjoins: ANY lifts only non‑correlated subjoins, EXISTS lifts only correlated ones. Examples:

SELECT * FROM STUDENT, (SELECT * FROM SCORE) AS sc;          -- subquery
SELECT (SELECT AVG(degree) FROM SCORE), sname FROM STUDENT;   -- subjoin
SELECT * FROM STUDENT WHERE EXISTS (SELECT A FROM SCORE WHERE SCORE.sno = STUDENT.sno);

Correlation determines whether lifting is beneficial; if a subjoin can be turned into a semi‑join, the optimizer may apply the transformation.

Selection Push‑Down and Equivalence Classes

Selection predicates are pushed as early as possible to filter rows before costly joins. Projection can also be pushed down using the distributive law σF(A×B) = σF1(A)×σF2(B). Equivalence‑class reasoning groups columns that are known to be equal (e.g., {TEACHER.tno, COURSE.tno, 5}) and generates additional predicates that can be further pushed.

-- Original query
SELECT sname FROM TEACHER t, COURSE c WHERE t.tno = 5 AND t.tno = c.tno;
-- After selection and projection push‑down
SELECT sname FROM (SELECT * FROM TEACHER WHERE tno = 5) tt,
                 (SELECT cname, tno FROM COURSE) cc
                 WHERE tt.tno = cc.tno;

Strictness of Expressions

An expression is *strict* if it returns NULL when any input is NULL; *wide‑strict* returns NULL or FALSE. Strict predicates allow outer‑join elimination because NULL‑augmented rows would be filtered out. PostgreSQL records strictness in the pg_proc.proisstrict column for functions, and treats IS NOT NULL as strict while IS NULL is not.

SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE SCORE.sno IS NULL; -- becomes ANTI JOIN

By recognizing strict predicates, the optimizer can convert left outer joins to inner joins or anti‑joins, enabling further push‑down and reducing work.

Key Takeaways

The optimizer builds a syntax tree, rewrites it using logical rules (subquery lifting, selection/projection push‑down, equivalence reasoning), then evaluates physical alternatives with a cost model, applying strictness analysis to eliminate unnecessary outer joins.