Understanding join strategies in PostgreSQL
Tags: database, sql, postgres
Published: 2023-10-24 08:00:00

One of the good practices for database design is normalization. We decompose data into multiple tables to avoid duplication and make data storage more organized. As an outcome, we need to join tables when querying the data. SQL engine needs to calculate the result of the join operation, and there are multiple join strategies (algorithms) that can be used. In this blogpost we’ll understand typical join algorithms and when they’re used.

## Overview

We’re going to use the [demodb](https://postgrespro.com/community/demodb). We at Metis provide [a docker container with this database](https://github.com/metis-data/postgresql-demo-database). 
Specifically, we’ll just use tables `ticket_flights` with ~8 million rows and flights with ~200 thousand rows. We can take a look [at the schema](https://postgrespro.com/docs/postgrespro/10/apjs02.html):


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/runms82ybaidxg24ex90.png)

Table `flights` has a primary key configured on the `flight_id` field. This means that the table is stored as a B-tree. Similarly, `ticket_flights` has a primary key configured on the tuple `(ticket_no, flight_id)`.

Before moving on, let’s also set parallel scans to 0 with the following query:

```
SET max_parallel_workers_per_gather = 0;
```

Parallel scans don’t change the algorithms, so we can ignore them in the scope of this article.

## Nested Loop Join

First and the simplest join strategy is called Nested Loop Join. It can be depicted with the following pseudocode:

```
For row1 in table1:
            	For row2 in table2:
                            	If (row1 == row2):
                                            	Add_ to_result(row1, row2)
```
 
We iterate over both tables with two loops, and join them naively. This has quadratic time complexity `O(size(table1) * size(table2))`. The memory complexity is `O(1)`.
Let’s now see that in action. Take this query:

```
EXPLAIN
SELECT *
FROM ticket_flights AS tf
JOIN flights AS f ON f.flight_id < tf.flight_id
```
 
And here is the plan we obtained:

```
Nested Loop  (cost=0.42..16532324955.82 rows=601044021228 width=95)
  ->  Seq Scan on ticket_flights tf  (cost=0.00..153851.52 rows=8391852 width=32)
  ->  Index Scan using flights_pkey on flights f  (cost=0.42..1253.81 rows=71622 width=63)
    	Index Cond: (flight_id < tf.flight_id)
```

 
We can see that the engine decided to use an index to scan the `flights` table. No index was used to scan the `ticket_flights` table which is bad - scanning the whole table requires reading all of the rows which amounts to plenty of data. We generally always want to avoid scanning the whole table when filtering, but we want to read as little data as possible. Next, both of these scans are joined with the Nested Loop algorithm.
 
```
Nested Loop  (cost=0.42..16532324955.82 rows=601044021228 width=95)
  ->  Seq Scan on ticket_flights tf  (cost=0.00..153851.52 rows=8391852 width=32)
  ->  Index Scan using flights_pkey on flights f  (cost=0.42..1253.81 rows=71622 width=63)
    	Index Cond: (flight_id > tf.flight_id)
```
 
Let’s see if changing the order of joins matters. Take this query:

```
EXPLAIN
SELECT *
FROM flights AS f
JOIN ticket_flights AS tf ON f.flight_id < tf.flight_id
```

And here is the plan we get:

```
Nested Loop  (cost=0.42..16532324955.82 rows=601044021228 width=95)
  ->  Seq Scan on ticket_flights tf  (cost=0.00..153851.52 rows=8391852 width=32)
  ->  Index Scan using flights_pkey on flights f  (cost=0.42..1253.81 rows=71622 width=63)
    	Index Cond: (flight_id < tf.flight_id)
```

The result is the same.
 
However, we can also see that changing the output aggregation can change the way we scan tables, but doesn’t change the algorithm. Let’s take this query
 
```
EXPLAIN
SELECT COUNT(*)
FROM ticket_flights AS tf
JOIN flights AS f ON f.flight_id < tf.flight_id
```
 
We get the following plan:
 
```
Aggregate  (cost=18034924512.89..18034924512.90 rows=1 width=8)
  ->  Nested Loop  (cost=0.42..16532314459.82 rows=601044021228 width=0)
    	->  Seq Scan on ticket_flights tf  (cost=0.00..153851.52 rows=8391852 width=4)
    	->  Index Only Scan using flights_pkey on flights f  (cost=0.42..1253.81 rows=71622 width=4)
          	Index Cond: (flight_id > tf.flight_id)
```

We can see that now we scan the `flights` table with `Index Only Scan`. This operation doesn’t even need to read the rows, it can get everything from the index which makes this operation even faster than the Index Scan. Next, scans are once again joined with the Nested Loop operation, and finally the Aggregate operation is executed to select the count of the rows.
 
## Hash Join
 
The next strategy is called Hash Join. The Hash Join algorithm consists of two phases. In the first phase we build a hashtable from one of the tables that we want to join. In the second phase we iterate over the rows of the latter table, and then find the match in the hashtable. The algorithm looks like this:
 
```
For row1 in table1:
hashtable.add(row1.id, row1)
 
For row2 in table2:
            	Row1 = hashtable.get(row2.id)
            	If (row1 == row2):
                            	Add_to_result(row1, row2)
```
 
The complexity is `O(size(table1) + size(table2))` if we assume that the hashing algorithm is good and we have `O(1)` lookup time. The memory complexity is `O(size(table1))` so the order matters. The engine generally prefers to hash the smaller table.
 
Let’s see that in action:
 
```
EXPLAIN
SELECT COUNT(*)
FROM ticket_flights AS tf
JOIN flights AS f ON f.flight_id = tf.flight_id
```
 
This is the plan:
 
```
Hash Join  (cost=9767.51..302691.07 rows=8391852 width=95)
  Hash Cond: (tf.flight_id = f.flight_id)
  ->  Seq Scan on ticket_flights tf  (cost=0.00..153851.52 rows=8391852 width=32)
  ->  Hash  (cost=4772.67..4772.67 rows=214867 width=63)
    	->  Seq Scan on flights f  (cost=0.00..4772.67 rows=214867 width=63)
```
 
We can see that the engine decided to scan the `flights` table and then build a hash table out of it. Next, it iterates over the `ticket_flights` table and matches the rows based on the condition.

If we swap the join order in the SQL query like this:

```
EXPLAIN
SELECT *
FROM flights AS f 
JOIN ticket_flights AS tf ON f.flight_id = tf.flight_id
```
 
then we get exactly the same plan:
 
```
Hash Join  (cost=9767.51..302691.07 rows=8391852 width=95)
  Hash Cond: (tf.flight_id = f.flight_id)
  ->  Seq Scan on ticket_flights tf  (cost=0.00..153851.52 rows=8391852 width=32)
  ->  Hash  (cost=4772.67..4772.67 rows=214867 width=63)
    	->  Seq Scan on flights f  (cost=0.00..4772.67 rows=214867 width=63)
```
 
The engine is allowed to do so. SQL queries are declarative, so they define what the result is, but they don’t dictate how the result is calculated.
 
However, if we add the aggregation:

```
EXPLAIN
SELECT COUNT(*)
FROM ticket_flights AS tf
JOIN flights AS f ON f.flight_id = tf.flight_id
```
 
Then we get this plan:

```
Aggregate  (cost=271560.70..271560.71 rows=1 width=8)
  ->  Hash Join  (cost=8298.51..250581.07 rows=8391852 width=0)
    	Hash Cond: (tf.flight_id = f.flight_id)
    	->  Seq Scan on ticket_flights tf  (cost=0.00..153851.52 rows=8391852 width=4)
    	->  Hash  (cost=4772.67..4772.67 rows=214867 width=4)
              ->  Seq Scan on flights f  (cost=0.00..4772.67 rows=214867 width=4)
```
 
You can see that the `flights` table is still scanned as before. There is no index scan this time.
 

## Merge Join

Merge join algorithm is used when we can iterate the rows in order. It works like this:
 
```
Table1_sorted = table1.sort();
Table2_sorted = table2.sort();
Row1 = table1_sorted.first()
Row2 = table2_sorted.first()
 
while row1 is not Null and row2 is not Null:
            	while row1 >= row2:
                            	if row1 == row2:
                                            	Add_to_result(row1, row2)
                            	Row2++
            	Row1++
``` 
 
The time complexity is `O(size(table1)*log(size(table1)) + size(table2)*log(size(table2)) + size(table1) + size(table2))`. The memory complexity is `O(size(table1) + size(table2))`.

However, if the data is already ordered, then we get `O(size(table1) + size(table2))` for time complexity and `O(1)` for memory complexity.
 
Let’s see that in action. First, disable the hash join strategy:

```
SET enable_hashjoin = off;
```
 
And then run this query:
 
```
EXPLAIN
SELECT *
FROM ticket_flights AS tf         	
JOIN flights AS f ON f.flight_id = tf.flight_id
```
 
We get the following plan:
 
```
Merge Join  (cost=1520511.52..1676140.76 rows=8391852 width=95)
  Merge Cond: (f.flight_id = tf.flight_id)
  ->  Index Scan using flights_pkey on flights f  (cost=0.42..8245.57 rows=214867 width=63)
  ->  Materialize  (cost=1520506.91..1562466.17 rows=8391852 width=32)
    	->  Sort  (cost=1520506.91..1541486.54 rows=8391852 width=32)
          	Sort Key: tf.flight_id
              ->  Seq Scan on ticket_flights tf  (cost=0.00..153851.52 rows=8391852 width=32)
```
 
 
We can see that the engine had to sort the `ticket_flights` table after scanning it. However, the `flights` table was already sorted because it has the B-tree already built for the primary key.
The reason `ticket_flights` table needs to be sorted is because the primary key consists of the ticket number and the flight id. However, the order of fields matters, so the flight id may not be stored in order.

## Summary

The engine can choose how to calculate the join of two tables. Various algorithms have different time and memory complexities, so it’s useful to understand how we can speed things up. We can do that by adding indexes or making sure that we use conditions that allow us to use the more efficient join operations.