3.5.1. Nested Loop Join
The nested loop join is the most fundamental join operation and can be applied to all join conditions. PostgreSQL supports the standard nested loop join along with five variations.
3.5.1.1. Nested Loop Join
The nested loop join requires no start-up operation; therefore, the start-up cost is $0$:
$$ \begin{align} \text{'start-up cost'} = 0. \end{align} $$The run cost of a nested loop join is proportional to the product of the sizes of the outer and inner tables.
Specifically, the $\text{'run cost'}$ is $O(N_{\text{outer}} \times N_{\text{inner}})$, where $N_{\text{outer}}$ and $N_{\text{inner}}$ represent the number of tuples in the outer and inner tables, respectively.
More precisely, the run cost is defined by the following equation:
$$ \begin{align} \text{'run cost'} = (\text{cpu_operator_cost} + \text{cpu_tuple_cost}) \times N_{\text{outer}} \times N_{\text{inner}} + C_{\text{inner}} \times N_{\text{outer}} + C_{\text{outer}} \end{align} $$where $C_{\text{outer}}$ and $C_{\text{inner}}$ are the scanning costs of the outer and inner tables.
Figure. 3.19. Nested loop join.
While the planner always estimates the cost of a standard nested loop join, this specific operation is rarely selected for the final plan. Instead, more efficient variations — described in the following sections — are typically used.
3.5.1.2. Materialized Nested Loop Join
The standard nested loop join must scan all tuples of the inner table for every tuple read from the outer table. Since scanning the entire inner table repeatedly is a costly process, PostgreSQL supports the materialized nested loop join to reduce the total scanning cost of the inner table.
Before executing the join, the executor scans the inner table once and writes the tuples to work_mem or a temporary file. This process utilizes the temporary tuple storage module described in the below.
Materialization allows for more efficient processing of inner table tuples compared to relying on the buffer manager, especially when all tuples fit within work_mem.
Figure 3.20 illustrates the operation of the materialized nested loop join. Internally, scanning materialized tuples is referred to as a rescan.
Figure 3.20. Materialized nested loop join.
PostgreSQL provides a temporary tuple storage module used for materializing tables, creating batches in hybrid hash joins, and other internal operations. This module is composed of functions defined in tuplestore.c.
These functions store and read a sequence of tuples to or from work_mem or temporary files. The choice between work_mem and temporary files depends on the total size of the tuples being stored.
The following example demonstrates how the executor processes a materialized nested loop join plan tree and how the costs are estimated.
|
|
The executor processes the plan nodes in the following order:
-
Line 7: The executor creates the materialized representation of the inner table tbl_b by performing a sequential scan (Line 8).
-
Line 4: The executor carries out the nested loop join operation. The outer table is tbl_a, and the inner table is the materialized tbl_b.
The following section describes the cost estimation for the Materialize (Line 7) and Nested Loop (Line 4) operations. This estimation assumes that all materialized inner tuples are stored in work_mem.
Materialize:
As there is no start-up operation required, the start-up cost is $0$:
$$ \begin{align} \text{'start-up cost'} = 0 \end{align} $$The run cost is defined by the following equation:
$$ \begin{align} \text{'run cost'} = 2 \times \text{cpu_operator_cost} \times N_{\text{inner}} \end{align} $$Substituting the values for this example:
$$ \begin{align} \text{'run cost'} = 2 \times 0.0025 \times 5000 = 25.0 \end{align} $$The total cost is the sum of the start-up cost, the total cost of the preceding sequential scan, and the run cost of the materialization itself:
$$ \begin{align} \text{'total cost'} = (\text{'start-up cost'} + \text{'total cost of seq scan'}) + \text{'run cost'} \end{align} $$Therefore,
$$ \begin{align} \text{'total cost'} = (0.0 + 73.0) + 25.0 = 98.0 \end{align} $$(Materialized) Nested Loop:
As there is no start-up operation, the start-up cost is $0$:
$$ \begin{align} \text{'start-up cost'} = 0 \end{align} $$Before the run cost is estimated, the rescan cost must be determined. This cost is defined by the following equation:
$$ \begin{align} \text{'rescan cost'} = \text{cpu_operator_cost} \times N_{\text{inner}} \end{align} $$In this example:
$$ \begin{align} \text{'rescan cost'} = (0.0025) \times 5000 = 12.5 \end{align} $$The run cost is defined as follows:
$$ \begin{align} \text{'run cost'} &= (\text{cpu_operator_cost} + \text{cpu_tuple_cost}) \times N_{\text{inner}} \times N_{\text{outer}} \\ &+ \text{'rescan cost'} \times (N_{\text{outer}} - 1) + C^{\text{total}}_{\text{outer,seqscan}} + C^{\text{total}}_{\text{materialize}} \end{align} $$where $C_{\text{outer,seqscan}}^{\text{total}}$ is the total scan cost of the outer table and $C^{\text{total}}_{\text{materialize}}$ is the total cost of the materialization. Therefore:
$$ \begin{align} \text{'run cost'} = (0.0025 + 0.01) \times 5000 \times 10000 + 12.5 \times (10000 - 1) + 145.0 + 98.0 = 750230.5 \end{align} $$3.5.1.3. Indexed Nested Loop Join
If an index exists on the inner table that can be used to look up tuples satisfying the join condition for each tuple of the outer table, the planner considers using this index to search the inner table directly instead of performing a sequential scan. This variation is called an indexed nested loop join (see Figure 3.21).
Figure 3.21. Indexed nested loop join.
Despite its name, this algorithm processes the outer table in a single loop, allowing it to perform the join operation efficiently.
A specific example of the indexed nested loop join is shown below:
|
|
Line 6 displays the cost of accessing the inner table. This represents the cost of looking up the inner table for a tuple that satisfies the index condition (id = b.id) shown in Line 7.
In this index condition, ‘b.id’ is the value of the outer table attribute used in the join. Whenever a tuple is retrieved from the outer table via sequential scan, the index scan path in Line 6 identifies the corresponding inner tuples to be joined. In other words, this index scan path uses the outer table values as parameters to find matching inner tuples.
Such a path is called a parameterized (index) path. Further details are provided in the optimizer README.
The start-up cost of this nested loop join equals the start-up cost of the index scan in Line 6:
$$ \begin{align} \text{'start-up cost'} = 0.285 \end{align} $$The total cost of the indexed nested loop join is defined by the following equation:
$$ \begin{align} \text{'total cost'} = (\text{cpu_tuple_cost} + C^{\text{total}}_{\text{inner,parameterized}}) \times N_{\text{outer}} + C^{\text{run}}_{\text{outer,seqscan}} \end{align} $$where $C^{\text{total}}_{\text{inner,parameterized}}$ is the total cost of the parameterized inner index scan.
In this example:
$$ \begin{align} \text{'total cost'} = (0.01 + 0.3625) \times 5000 + 73.0 = 1935.5 \end{align} $$The run cost is determined as follows:
$$ \begin{align} \text{'run cost'} = 1935.5 - 0.285 = 1935.215 \end{align} $$As demonstrated above, the total cost of the indexed nested loop join is $O(N_{\text{outer}})$.
3.5.1.4. Other Variations
If an index exists on the outer table and its attributes are involved in the join condition, it can be used for an index scan instead of a sequential scan.
In particular, if an index attribute can serve as an access predicate in the WHERE clause, the search range of the outer table is narrowed. This can drastically reduce the cost of the nested loop join.
PostgreSQL supports three variations of the nested loop join with an outer index scan, as illustrated in Figure 3.22.
Figure 3.22. The three variations of the nested loop join with an outer index scan.
The EXPLAIN results for these join variations are shown below:
(a) Nested loop join with outer index scan
testdb=# SET enable_hashjoin TO off;
SET
testdb=# SET enable_mergejoin TO off;
SET
testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_b AS b WHERE c.id = b.id AND c.id = 500;
QUERY PLAN
--------------------------------------------------------------------------------
Nested Loop (cost=0.29..93.81 rows=1 width=16)
-> Index Scan using tbl_c_pkey on tbl_c c (cost=0.29..8.30 rows=1 width=8)
Index Cond: (id = 500)
-> Seq Scan on tbl_b b (cost=0.00..85.50 rows=1 width=8)
Filter: (id = 500)
(5 rows)(2) Materialized nested loop join with outer index scan
testdb=# SET enable_hashjoin TO off;
SET
testdb=# SET enable_mergejoin TO off;
SET
testdb=# EXPLAIN SELECT * FROM tbl_c AS c, tbl_b AS b WHERE c.id = b.id AND c.id < 40 AND b.id < 10;
QUERY PLAN
---------------------------------------------------------------------------------
Nested Loop (cost=0.29..99.76 rows=1 width=16)
Join Filter: (c.id = b.id)
-> Index Scan using tbl_c_pkey on tbl_c c (cost=0.29..8.97 rows=39 width=8)
Index Cond: (id < 40)
-> Materialize (cost=0.00..85.55 rows=9 width=8)
-> Seq Scan on tbl_b b (cost=0.00..85.50 rows=9 width=8)
Filter: (id < 10)
(7 rows)(3) Indexed nested loop join with outer index scan
testdb=# SET enable_hashjoin TO off;
SET
testdb=# SET enable_mergejoin TO off;
SET
testdb=# EXPLAIN SELECT * FROM tbl_a AS a, tbl_d AS d WHERE a.id = d.id AND a.id < 40;
QUERY PLAN
---------------------------------------------------------------------------------
Nested Loop (cost=0.57..173.06 rows=20 width=16)
-> Index Scan using tbl_a_pkey on tbl_a a (cost=0.29..8.97 rows=39 width=8)
Index Cond: (id < 40)
-> Index Scan using tbl_d_pkey on tbl_d d (cost=0.28..4.20 rows=1 width=8)
Index Cond: (id = a.id)
(5 rows)