3.5. Join Algorithms

PostgreSQL supports the join types defined by the SQL standard, including INNER JOIN, LEFT/RIGHT OUTER JOIN, and FULL OUTER JOIN. For simplicity, this chapter focuses on NATURAL INNER JOIN.

PostgreSQL uses three primary join algorithms to execute these operations: Nested Loop Join, Merge Join, and Hash Join. Both Nested Loop Join and Merge Join have several variations.

The following subsections explain these join algorithms.

Section Contents

3.5.1. Nested Loop Join
3.5.2. Merge Join
3.5.3. Hash Join
3.5.4. Join Access Paths and Join Nodes

Cardinality Estimation in Multi-table Joins

As mentioned in Section 3.2.4, cardinality estimation for multi-table joins is calculated under the assumption that columns are statistically independent.

If correlations exist between columns, estimation accuracy decreases. Consequently, the query planner may fail to create an efficient plan.

Database engineers and administrators should remain mindful of this limitation.