21 Nested Loop

PostgreSQL 14 · Translated from Russian by Liudmila Mantrova · Chinese translation by Xiong Cancan

简体中文 · PG14English · PG14简体中文 · PG18 Русский · PG18

21.1 Join Types and Methods

Joins are a key feature of the SQL language; they serve as the foundation for its power and flexibility. Sets of rows (either retrieved from tables directly or received as the result of some other operations) are always joined pairwise.

There are several types of joins:

Inner joins. An inner join (specified as INNER JOIN, or simply JOIN) comprises those pairs of rows of two sets that satisfy a particular join condition. The join condition combines some columns of one set of rows with some columns of the other set; all the columns involved constitute the join key.

If the join condition demands that join keys of two sets be equal, such a join is called an equi-join; this is the most common join type.

A Cartesian product (CROSS JOIN) of two sets comprises all the possible pairs of rows of these sets—it is a special case of an inner join with a true condition.

Outer joins. A left outer join (specified as LEFT OUTER JOIN, or simply LEFT JOIN) extends the result of an inner join by those rows of the left set that have no match in the right set (the corresponding right-side columns are filled with NULL values).

The same is also true for a right outer join (RIGHT JOIN), down to the permutation of sets.

A full outer join (specified as FULL JOIN) comprises left and right outer joins, adding both right-side and left-side rows for which no match has been found.

Anti-Joins and Semi-Joins. A semi-join looks a lot like an inner join, but it includes only those rows of the left set that have a match in the right set (a row is included only once even if there are several matches).

An anti-join includes those rows of a set that have no match in the other set.

The SQL language has no explicit semi- and anti-joins, but the same outcome can be achieved using predicates like EXISTS and NOT EXISTS.

All these joins are logical operations. For example, an inner join is often described as a Cartesian product that has been cleared of the rows that do not satisfy the join condition. But at the physical level, an inner join is typically achieved via less expensive means.

PostgreSQL provides several join methods:

a nested loop join
a hash join
a merge join

Join methods are algorithms that implement logical operations of SQL joins. These basic algorithms often have special flavors tailored for particular join types, even though they may support only some of them. For example, a nested loop supports an inner join (represented in the plan by a Nested Loop node) and a left outer join (represented by a Nested Loop Left Join node), but it cannot be used for full joins.

Some flavors of the same algorithms can also be used by other operations, such as aggregation.

Different join methods perform best in different conditions; it is the job of the planner to choose the most cost-effective one.

21.2 Nested Loop Joins

The basic algorithm of the nested loop join functions as follows. The outer loop traverses all the rows of the first set (called the outer set). For each of these rows, the nested loop goes through the rows of the second set (called the inner set) to find the ones that satisfy the join condition. Each found pair is returned immediately as part of the query result.¹

The algorithm accesses the inner set as many times as there are rows in the outer set. Therefore, the efficiency of nested loop joins depends on several factors:

cardinality of the outer set of rows
availability of an access method that can efficiently fetch the rows of the inner set
recurrent access to the same rows of the inner set

Cartesian Product

A nested loop join is the most efficient way to find a Cartesian product, regardless of the number of rows in the sets:

=> EXPLAIN SELECT * FROM aircrafts_data a1
  CROSS JOIN aircrafts_data a2
WHERE a2.range > 5000;
                     QUERY PLAN
-----------------------------------------------------
 Nested Loop  (cost=0.00..2.78 rows=45 width=144)
   -> Seq Scan on aircrafts_data a1

outer set

    (cost=0.00..1.09 rows=9 width=72)
-> Materialize  (cost=0.00..1.14 rows=5 width=72)
    -> Seq Scan on aircrafts_data a2

inner set

           (cost=0.00..1.11 rows=5 width=72)
           Filter: (range > 5000)
(7 rows)

The Nested Loop node performs a join using the algorithm described above. It always has two child nodes: the one that is displayed higher in the plan corresponds to the outer set of rows, while the lower one represents the inner set.

In this example, the inner set is represented by the Materialize node.² This node returns the rows received from its child node, having saved them for future use (the rows are accumulated in memory until their total size reaches work_mem; then PostgreSQL starts spilling them into a temporary file on disk). If accessed again, the node reads the accumulated rows without calling the child node. Thus, the executor can avoid scanning the full table again and read only those rows that satisfy the condition. (default: 4MB)

A similar plan can also be built for a query that uses a regular equi-join:

=> EXPLAIN SELECT * FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
WHERE t.ticket_no = '0005432000284';
                           QUERY PLAN
----------------------------------------------------------------
 Nested Loop  (cost=0.99..25.05 rows=3 width=136)
   -> Index Scan using tickets_pkey on tickets t
       (cost=0.43..8.45 rows=1 width=104)
       Index Cond: (ticket_no = '0005432000284'::bpchar)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.58 rows=3 width=32)
       Index Cond: (ticket_no = '0005432000284'::bpchar)
(7 rows)

Having recognized the equality of the two values, the planner replaces the join condition tf.ticket_no = t.ticket_no by the tf.ticket_no = constant condition, virtually reducing an equi-join to a Cartesian product.³

Cardinality estimation. The cardinality of a Cartesian product is estimated at the product of cardinalities of the joined data sets: 3 = 1 × 3.

Cost estimation. The startup cost of the join operation combines the startup costs of all child nodes.

The full cost of the join includes the following components:

the cost of fetching all the rows of the outer set
the cost of a single retrieval of all the rows of the inner set (since the cardinality estimation of the outer set equals one)
the cost of processing each row to be returned

Here is a dependency graph for the cost estimation:

                           QUERY PLAN
----------------------------------------------------------------
 Nested Loop  (cost=0.99..25.05 rows=3 width=136)
   -> Index Scan using tickets_pkey on tickets t
       (cost=0.43..8.45 rows=1 width=104)

× 1

       Index Cond: (ticket_no = '0005432000284'::bpchar)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.58 rows=3 width=32)
       Index Cond: (ticket_no = '0005432000284'::bpchar)
(7 rows)

The cost of the join is calculated as follows:

=> SELECT 0.43 + 0.56 AS startup_cost,
  round((
    8.45 + 16.57 +
    3 * current_setting('cpu_tuple_cost')::real
  )::numeric, 2) AS total_cost;
 startup_cost | total_cost
--------------+------------
         0.99 |      25.05
(1 row)

Now let’s get back to the previous example:

=> EXPLAIN SELECT *
FROM aircrafts_data a1
  CROSS JOIN aircrafts_data a2
WHERE a2.range > 5000;
                     QUERY PLAN
-----------------------------------------------------
 Nested Loop  (cost=0.00..2.78 rows=45 width=144)
   -> Seq Scan on aircrafts_data a1
       (cost=0.00..1.09 rows=9 width=72)
   -> Materialize  (cost=0.00..1.14 rows=5 width=72)
       -> Seq Scan on aircrafts_data a2
           (cost=0.00..1.11 rows=5 width=72)
           Filter: (range > 5000)
(7 rows)

The plan now contains the Materialize node; having once accumulated the rows received from its child node, Materialize returns them much faster for all the subsequent calls.

In general, the total cost of a join comprises the following expenses:⁴

the cost of fetching all the rows of the outer set
the cost of the initial fetch of all the rows of the inner set (during which materialization is performed)
(N − 1)-fold cost of repeat fetches of rows of the inner set (here N is the number of rows in the outer set)
the cost of processing each row to be returned

The dependency graph here is as follows:

                    QUERY PLAN
--------------------------------------------------
 Nested Loop  (cost=0.00..2.78 rows=45 width=144)
   -> Seq Scan on aircrafts_data a1
       (cost=0.00..1.09 rows=9 width=72)

× 9

   -> Materialize
       (cost=0.00..1.14 rows=5 width=72)
       -> Seq Scan on aircrafts_data a2
           (cost=0.00..1.11 rows=5 width=72)
           Filter: (range > 5000)
(8 rows)

In this example, materialization reduces the cost of repeat data fetches. The cost of the first Materialize call is shown in the plan, but all the subsequent calls are not listed. I will not provide any calculations here,⁵ but in this particular case the estimation is 0.0125.

Thus, the cost of the join performed in this example is calculated as follows:

=> SELECT 0.00 + 0.00 AS startup_cost,
  round((
    1.09 + (1.14 + 8 * 0.0125) +
    45 * current_setting('cpu_tuple_cost')::real
  )::numeric, 2) AS total_cost;
 startup_cost | total_cost
--------------+------------
         0.00 |       2.78
(1 row)

Parameterized Joins

Now let’s consider a more common example that does not boil down to a Cartesian product:

=> CREATE INDEX ON tickets(book_ref);
=> EXPLAIN SELECT *
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
WHERE t.book_ref = '03A76D';
                           QUERY PLAN
----------------------------------------------------------------
 Nested Loop  (cost=0.99..45.68 rows=6 width=136)
   -> Index Scan using tickets_book_ref_idx on tickets t
       (cost=0.43..12.46 rows=2 width=104)
       Index Cond: (book_ref = '03A76D'::bpchar)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.58 rows=3 width=32)
       Index Cond: (ticket_no = t.ticket_no)
(7 rows)

Here the Nested Loop node traverses the rows of the outer set (tickets), and for each of these rows it searches for the corresponding rows of the inner set (flights), passing the ticket number (t.ticket_no) to the condition as a parameter. When the inner node (Index Scan) is called, it has to deal with the condition ticket_no = constant.

Cardinality estimation. The planner estimates that the filter condition by a booking number is satisfied by two rows of the outer set (rows=2), and each of these rows matches three rows of the inner set on average (rows=3).

Join selectivity is a fraction of the Cartesian product of the two sets that remains after the join. It is obvious that we must exclude those rows of both sets that contain NULL values in the join key since the equality condition will never be satisfied for them.

The estimated cardinality equals the cardinality of the Cartesian product (that is, the product of cardinalities of the two sets) multiplied by the selectivity.⁶

Here the estimated cardinality of the first (outer) set is two rows. Since no conditions are applied to the second (inner) set except for the join condition itself, the cardinality of the second set is taken as the cardinality of the ticket_flights table.

Since the joined tables are connected by a foreign key, the selectivity estimation relies on the fact that each row of the child table has exactly one matching row in the parent table. So the selectivity is taken as the inverse of the size of the table referred to by the foreign key.⁷

Thus, for the case when the ticket_no columns contain no NULL values, the estimation is as follows:

=> SELECT round(2 * tf.reltuples * (1.0 / t.reltuples)) AS rows
FROM pg_class t, pg_class tf
WHERE t.relname = 'tickets'
  AND tf.relname = 'ticket_flights';
 rows
------
    6
(1 row)

Clearly, tables can be also joined without using foreign keys. Then the selectivity will be taken as the estimated selectivities of the particular join conditions.⁸

For the equi-join in this example, the generic formula for selectivity estimation that assumes uniform distribution of values looks as follows: $\min\!\left(\frac{1}{nd_1},\frac{1}{nd_2}\right)$ , where nd₁ and nd₂ represent the number of distinct values of the join key in the first and second set, respectively.⁹ (p. 276)

Statistics on distinct values show that ticket numbers in the tickets table are unique (which is only to be expected, as the ticket_no column is the primary key), and the ticket_flights has about three matching rows for each ticket:

=> SELECT t.n_distinct, tf.n_distinct
FROM pg_stats t, pg_stats tf
WHERE t.tablename = 'tickets' AND t.attname = 'ticket_no'
  AND tf.tablename = 'ticket_flights' AND tf.attname = 'ticket_no';
 n_distinct | n_distinct
------------+-------------
         -1 | -0.30362356
(1 row)

The result would match the estimation for the join with the foreign key:

=> SELECT round(2 * tf.reltuples *
  least(1.0/t.reltuples, 1.0/tf.reltuples/0.30362356)
) AS rows
FROM pg_class t, pg_class tf
WHERE t.relname = 'tickets' AND tf.relname = 'ticket_flights';
 rows
------
    6
(1 row)

The planner tries to refine this baseline estimation whenever possible. It cannot use histograms at the moment, but it takes MCV lists into account if such statistics have been collected on the join key for both tables.¹⁰ The selectivity of the rows that appear in the list can be estimated more accurately, and only the remaining rows will have to rely on calculations that are based on uniform distribution. (p. 277)

In general, join selectivity estimation is likely to be more accurate if the foreign key is defined. It is especially true for composite join keys, as the selectivity is often largely underestimated in this case.

Using the EXPLAIN ANALYZE command, you can view not only the actual number of rows, but also the number of times the inner loop has been executed:

=> EXPLAIN (analyze, timing off, summary off) SELECT *
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
WHERE t.book_ref = '03A76D';
                            QUERY PLAN
-------------------------------------------------------------------
 Nested Loop  (cost=0.99..45.68 rows=6 width=136)
   (actual rows=8 loops=1)
   -> Index Scan using tickets_book_ref_idx on tickets t
       (cost=0.43..12.46 rows=2 width=104) (actual rows=2 loops=1)
       Index Cond: (book_ref = '03A76D'::bpchar)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.58 rows=3 width=32) (actual rows=4 loops=2)
       Index Cond: (ticket_no = t.ticket_no)
(8 rows)

The outer set contains two rows (actual rows=2); the estimation has been correct. So the Index Scan node was executed twice (loops=2), and each time it selected four rows on average (actual rows=4). Hence the total number of found rows: actual rows=8.

Note

I do not show the execution time of each stage of the plan (TIMING OFF) for the output to fit the limited width of the page; besides, on some platforms an output with timing enabled can significantly slow down query execution. But if we did include it, PostgreSQL would display an average value, just like for the row count. To get the total execution time, you should multiply this value by the number of iterations (loops).

Cost estimation. The cost estimation formula here is the same as in the previous examples.

Let’s recall our query plan:

=> EXPLAIN SELECT *
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
WHERE t.book_ref = '03A76D';
                           QUERY PLAN
----------------------------------------------------------------
 Nested Loop  (cost=0.99..45.68 rows=6 width=136)
   -> Index Scan using tickets_book_ref_idx on tickets t
       (cost=0.43..12.46 rows=2 width=104)
       Index Cond: (book_ref = '03A76D'::bpchar)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.58 rows=3 width=32)
       Index Cond: (ticket_no = t.ticket_no)
(7 rows)

In this case, the cost of each subsequent scan of the inner set is the same as that of the first scan. So we ultimately get the following figures:

=> SELECT 0.43 + 0.56 AS startup_cost,
  round((
    12.46 + 2 * 16.57 +
    6 * current_setting('cpu_tuple_cost')::real
  )::numeric, 2) AS total_cost;
 startup_cost | total_cost
--------------+------------
         0.99 |      45.66
(1 row)

Caching Rows (Memoization)

If the inner set is repeatedly scanned with the same parameter values (thus giving the same results), it may turn out to be beneficial to cache the rows of this set. (v. 14)

Such caching is performed by the Memoize¹¹ node. Being similar to the Materialize node, it is designed to handle parameterized joins and has a much more complex implementation:

The Materialize node simply materializes all the rows returned by its child node, while Memoize ensures that the rows returned for different parameter values are kept separately.
In the event of an overflow, the Materialize storage starts spilling rows to disk, while Memoize keeps all the rows in memory (there would otherwise be no point in caching).

Here is an example of a query that uses Memoize:

=> EXPLAIN SELECT * FROM flights f
  JOIN aircrafts_data a ON f.aircraft_code = a.aircraft_code
WHERE f.flight_no = 'PG0003';
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop  (cost=5.44..387.10 rows=113 width=135)
   -> Bitmap Heap Scan on flights f
       (cost=5.30..382.22 rows=113 width=63)
       Recheck Cond: (flight_no = 'PG0003'::bpchar)
       -> Bitmap Index Scan on flights_flight_no_scheduled_depart...
           (cost=0.00..5.27 rows=113 width=0)
           Index Cond: (flight_no = 'PG0003'::bpchar)
   -> Memoize  (cost=0.15..0.27 rows=1 width=72)
       Cache Key: f.aircraft_code
       Cache Mode: logical
       -> Index Scan using aircrafts_pkey on aircrafts_data a
           (cost=0.14..0.26 rows=1 width=72)
           Index Cond: (aircraft_code = f.aircraft_code)
(13 rows)

The size of the memory chunk that is used to store cached rows equals work_mem × hash_mem_multiplier. As implied by the second parameter’s name, cached rows are stored in a hash table (with open addressing).¹² The hash key (shown as Cache Key in the plan) is the parameter value (or several values if there are more than one parameter). (default: 4MB) (default: 1.0)

All the hash keys are bound into a list; one of its ends is considered cold (since it contains the keys that have not been used for a long time), while the other is hot (it stores recently used keys).

If a call on the Memoize node shows that the passed parameter values correspond to the already cached rows, these rows will be passed on to the parent node (Nested Loop) without checking the child node. The used hash key is then moved to the hot end of the list.

If the cache does not contain the required rows, the Memoize node pulls them from its child node, caches them, and passes them on to the node above. The corresponding hash key also becomes hot.

As new data is being cached, it can fill all the available memory. To free some space, the rows that correspond to cold keys get evicted. This eviction algorithm differs from the one used in the buffer cache but serves the same purpose. (p. 154)

Some parameter values may turn out to have so many matching rows that they do not fit into the allocated memory chunk, even if all the other rows are already evicted. Such parameters are skipped—it makes no sense to cache only some of the rows since the next call will still have to get all the rows from the child node.

Cost and cardinality estimations. These calculations are quite similar to what we have already seen above. We just have to bear in mind that the cost of the Memoize node shown in the plan has nothing to do with its actual cost: it is simply the cost of its child node increased by the cpu_tuple_cost value.¹³ (default: 0.01)

We have already come across a similar situation for the Materialize node: its cost is only calculated for subsequent scans¹⁴ and is not reflected in the plan.

Clearly, it only makes sense to use Memoize if it is cheaper than its child node. The cost of each subsequent Memoize scan depends on the expected cache access profile and the size of the memory chunk that can be used for caching. The calculated value is highly dependent on the accurate estimation of the number of distinct parameter values to be used in the scans of the inner set of rows.¹⁵ Based on this number, you can weigh the probabilities of the rows to be cached and to be evicted from the cache. The expected hits reduce the estimated cost, while potential evictions increase it. We will skip the details of these calculations here.

To figure out what is actually going on during query execution, we will use the EXPLAIN ANALYZE command, as usual:

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM flights f
  JOIN aircrafts_data a ON f.aircraft_code = a.aircraft_code
WHERE f.flight_no = 'PG0003';
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop (actual rows=113 loops=1)
   -> Bitmap Heap Scan on flights f
       (actual rows=113 loops=1)
       Recheck Cond: (flight_no = 'PG0003'::bpchar)
       Heap Blocks: exact=2
       -> Bitmap Index Scan on flights_flight_no_scheduled_depart...
           (actual rows=113 loops=1)
           Index Cond: (flight_no = 'PG0003'::bpchar)
   -> Memoize (actual rows=1 loops=113)
       Cache Key: f.aircraft_code
       Cache Mode: logical
       Hits: 112  Misses: 1  Evictions: 0  Overflows: 0  Memory
       Usage: 1kB
       -> Index Scan using aircrafts_pkey on aircrafts_data a
           (actual rows=1 loops=1)
           Index Cond: (aircraft_code = f.aircraft_code)
(16 rows)

This query selects the flights that follow the same route and are performed by aircraft of a particular type, so all the calls on the Memoize node use the same hash key. The first row has to be fetched from the table (Misses: 1), but all the subsequent rows are found in the cache (Hits: 112). The whole operation takes just 1 kB of memory.

The other two displayed values are zero: they represent the number of evictions and the number of cache overflows when it was impossible to cache all the rows related to a particular set of parameters. Large figures would indicate that the allocated cache is too small, which might be caused by inaccurate estimation of the number of distinct parameter values. Then the use of the Memoize node can turn out to be quite expensive. In the extreme case, you can forbid the planner to use caching by turning off the enable_memoize parameter. (default: on)

Outer Joins

The nested loop join can be used to perform the left outer join:

=> EXPLAIN SELECT *
FROM ticket_flights tf
  LEFT JOIN boarding_passes bp ON bp.ticket_no = tf.ticket_no
                              AND bp.flight_id = tf.flight_id
WHERE tf.ticket_no = '0005434026720';
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop Left Join  (cost=1.12..33.35 rows=3 width=57)
   Join Filter: ((bp.ticket_no = tf.ticket_no) AND (bp.flight_id =
   tf.flight_id))
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.58 rows=3 width=32)
       Index Cond: (ticket_no = '0005434026720'::bpchar)
   -> Materialize  (cost=0.56..16.62 rows=3 width=25)
       -> Index Scan using boarding_passes_pkey on boarding_passe...
           (cost=0.56..16.61 rows=3 width=25)
           Index Cond: (ticket_no = '0005434026720'::bpchar)
(10 rows)

Here the join operation is represented by the Nested Loop Left Join node. The planner has chosen a non-parameterized join with a filter: it performs identical scans of the inner set of rows (so this set is hidden behind the Materialize node) and returns the rows that satisfy the filter condition (Join Filter).

The cardinality of the outer join is estimated just like the one of the inner join, except that the calculated estimation is compared with the cardinality of the outer set of rows, and the bigger value is taken as the final result.¹⁶ In other words, the outer join never reduces the number of rows (but can increase it).

The cost estimation is similar to that of the inner join.

We must also keep in mind that the planner can select different plans for inner and outer joins. Even this simple example will have a different Join Filter if the planner is forced to use a nested loop join:

=> SET enable_mergejoin = off;
=> EXPLAIN SELECT *
FROM ticket_flights tf
  JOIN boarding_passes bp ON bp.ticket_no = tf.ticket_no
                         AND bp.flight_id = tf.flight_id
WHERE tf.ticket_no = '0005434026720';
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop  (cost=1.12..33.33 rows=3 width=57)
   Join Filter: (tf.flight_id = bp.flight_id)
   -> Index Scan using ticket_flights_pkey on ticket_flights tf
       (cost=0.56..16.58 rows=3 width=32)
       Index Cond: (ticket_no = '0005434026720'::bpchar)
   -> Materialize  (cost=0.56..16.62 rows=3 width=25)
       -> Index Scan using boarding_passes_pkey on boarding_passe...
           (cost=0.56..16.61 rows=3 width=25)
           Index Cond: (ticket_no = '0005434026720'::bpchar)
(9 rows)
=> RESET enable_mergejoin;

A slight difference in the total cost is caused by the fact that the outer join must also check ticket numbers to get the correct result if there is no match in the outer set of rows.

Right joins are not supported,¹⁷ as the nested loop algorithm treats the inner and outer sets differently. The outer set is scanned in full; as for the inner set, the index access allows reading only those rows that satisfy the join condition, so some of its rows may be skipped altogether.

A full join is not supported for the same reason.

Anti- and Semi-joins

Anti-joins and semi-joins are similar in the sense that for each row of the first (outer) set it is enough to find only one matching row in the second (inner) set.

An anti-join returns the rows of the first set only if they have no match in the second set: as soon as the executor finds the first matching row in the second set, it can exit the current loop: the corresponding row of the first set must be excluded from the result.

Anti-joins can be used to compute the NOT EXISTS predicate.

For example, let’s find aircraft models with undefined cabin configuration. The corresponding plan contains the Nested Loop Anti Join node:

=> EXPLAIN SELECT *
FROM aircrafts a
WHERE NOT EXISTS (
  SELECT * FROM seats s WHERE s.aircraft_code = a.aircraft_code
);
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop Anti Join  (cost=0.28..4.65 rows=1 width=40)
   -> Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 widt...
   -> Index Only Scan using seats_pkey on seats s
       (cost=0.28..5.55 rows=149 width=4)
       Index Cond: (aircraft_code = ml.aircraft_code)
(5 rows)

An alternative query without the NOT EXISTS predicate will have the same plan:

=> EXPLAIN SELECT a.*
FROM aircrafts a
  LEFT JOIN seats s ON a.aircraft_code = s.aircraft_code
WHERE s.aircraft_code IS NULL;
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop Anti Join  (cost=0.28..4.65 rows=1 width=40)
   -> Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 widt...
   -> Index Only Scan using seats_pkey on seats s
       (cost=0.28..5.55 rows=149 width=4)
       Index Cond: (aircraft_code = ml.aircraft_code)
(5 rows)

A semi-join returns those rows of the first set that have at least one match in the second set (again, there is no need to check the set for other matches—the result is already known).

A semi-join can be used to compute the EXISTS predicate. Let’s find the aircraft models with seats installed in the cabin:

=> EXPLAIN SELECT *
FROM aircrafts a
WHERE EXISTS (
  SELECT * FROM seats s
  WHERE s.aircraft_code = a.aircraft_code
);
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop Semi Join  (cost=0.28..6.67 rows=9 width=40)
   -> Seq Scan on aircrafts_data ml  (cost=0.00..1.09 rows=9 widt...
   -> Index Only Scan using seats_pkey on seats s
       (cost=0.28..5.55 rows=149 width=4)
       Index Cond: (aircraft_code = ml.aircraft_code)
(5 rows)

The Nested Loop Semi Join node represents the same-name join method. This plan (just like the anti-join plans above) provides the basic estimation of the number of rows in the seats table (rows=149), although it is enough to retrieve only one of them. The actual query execution stops after fetching the first row, of course:

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM aircrafts a
WHERE EXISTS (
  SELECT * FROM seats s
  WHERE s.aircraft_code = a.aircraft_code
);
                         QUERY PLAN
------------------------------------------------------------
 Nested Loop Semi Join (actual rows=9 loops=1)
   -> Seq Scan on aircrafts_data ml (actual rows=9 loops=1)
   -> Index Only Scan using seats_pkey on seats s
       (actual rows=1 loops=9)
       Index Cond: (aircraft_code = ml.aircraft_code)
       Heap Fetches: 0
(6 rows)

Cardinality estimation. The selectivity of a semi-join is estimated in the usual manner, except that the cardinality of the inner set is taken as one. For anti-joins, the estimated selectivity is subtracted from one, just like for negation.¹⁸

Cost estimation. For anti- and semi-joins, the cost estimation reflects the fact that the scan of the second set stops as soon as the first matching row is found.¹⁹

Non-Equi-joins

The nested loop algorithm allows joining sets of rows based on any join condition.

Obviously, if the inner set is a base table with an index created on it, and the join condition uses an operator that belongs to an operator class of this index, the access to the inner set can be quite efficient. But it is always possible to perform the join by calculating a Cartesian product of rows filtered by some condition—which can be absolutely arbitrary in this case. Like in the following query, which selects pairs of airports that are located close to each other: (p. 315)

=> CREATE EXTENSION earthdistance CASCADE;
=> EXPLAIN (costs off) SELECT *
FROM airports a1
  JOIN airports a2 ON a1.airport_code != a2.airport_code
                  AND a1.coordinates <@> a2.coordinates < 100;
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop
   Join Filter: ((ml.airport_code <> ml_1.airport_code) AND
   ((ml.coordinates <@> ml_1.coordinates) < '100'::double precisi...
   -> Seq Scan on airports_data ml
   -> Materialize
       -> Seq Scan on airports_data ml_1
(6 rows)

Parallel Mode

A nested loop join can participate in parallel plan execution.²⁰ (v. 9.6) (p. 300)

It is only the outer set that can be processed in parallel, as it can be scanned by several workers simultaneously. Having fetched an outer row, each worker then has to search for the matching rows in the inner set, which is done sequentially.

The query shown below includes several joins; it searches for passengers that have tickets for a particular flight:

=> EXPLAIN (costs off) SELECT t.passenger_name
FROM tickets t
  JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
  JOIN flights f ON f.flight_id = tf.flight_id
WHERE f.flight_id = 12345;
                             QUERY PLAN
---------------------------------------------------------------------
 Nested Loop
   -> Index Only Scan using flights_flight_id_status_idx on fligh...
       Index Cond: (flight_id = 12345)
   -> Gather
       Workers Planned: 2
       -> Nested Loop
           -> Parallel Seq Scan on ticket_flights tf
               Filter: (flight_id = 12345)
           -> Index Scan using tickets_pkey on tickets t
               Index Cond: (ticket_no = tf.ticket_no)
(10 rows)

At the upper level, the nested loop join is performed sequentially. The outer set consists of a single row of the flights table fetched by a unique key, so the use of a nested loop is justified even for a large number of inner rows.

The inner set is retrieved using a parallel plan. Each of the workers scans its own share of rows of the ticket_flights table and joins them with tickets using the nested loop algorithm. (p. 301)

backend/executor/nodeNestloop.c ↩︎
backend/executor/nodeMaterial.c ↩︎
backend/optimizer/path/equivclass.c ↩︎
backend/optimizer/path/costsize.c, initial_cost_nestloop andfinal_cost_nestloop function ↩︎
backend/optimizer/path/costsize.c, cost_rescan function ↩︎
backend/optimizer/path/costsize.c, calc_joinrel_size_estimate function ↩︎
backend/optimizer/path/costsize.c, get_foreign_key_join_selectivity function ↩︎
backend/optimizer/path/clausesel.c, clauselist_selectivity function ↩︎
backend/utils/adt/selfuncs.c, eqjoinsel function ↩︎
backend/utils/adt/selfuncs.c, eqjoinsel function ↩︎
backend/executor/nodeMemoize.c ↩︎
include/lib/simplehash.h ↩︎
backend/optimizer/util/pathnode.c, create_memoize_path function ↩︎
backend/optimizer/path/costsize.c, cost_memoize_rescan function ↩︎
backend/utils/adt/selfuncs.c, estimate_num_groups function ↩︎
backend/optimizer/path/costsize.c, calc_joinrel_size_estimate function ↩︎
backend/optimizer/path/joinpath.c, match_unsorted_outer function ↩︎
backend/optimizer/path/costsize.c, calc_joinrel_size_estimate function ↩︎
backend/optimizer/path/costsize.c, final_cost_nestloop function ↩︎
backend/optimizer/path/joinpath.c, consider_parallel_nestloop function ↩︎