3.5.3. Hash Join

Similar to the merge join, the hash join is restricted to natural joins and equi-joins.

The behavior of a hash join in PostgreSQL depends on the sizes of the tables involved. If the inner table is small enough (specifically, if its size is 25% or less of work_mem), a simple two-phase in-memory hash join is performed. Otherwise, a hybrid hash join with a skew method is used.

This subsection describes the execution of both hash join methods.

3.5.3.1. In-Memory Hash Join

The in-memory hash join is processed within work_mem.

The hash table area is referred to as a batch in PostgreSQL. A batch contains hash slots, internally called buckets. The number of buckets is determined by the ExecChooseHashTableSize() function defined in nodeHash.c; this number is always $2^{n}$, where $n$ is an integer.

The in-memory hash join consists of two phases: the build phase and the probe phase.

• Build Phase: All tuples of the inner table are inserted into a batch.
• Probe Phase: Each tuple of the outer table is compared with the inner tuples in the batch and joined if the join condition is satisfied.

The following example illustrates this operation. Assume the following query is executed using a hash join:

testdb=# SELECT * FROM tbl_outer AS outer, tbl_inner AS inner WHERE inner.attr1 = outer.attr2;

The operation of the hash join is detailed below, with reference to Figures 3.26 and 3.27.

• (1) Create a batch in work_mem.
  In this example, the batch has 8 buckets ($2^{3}$).

• (2) Insert the first tuple of the inner table into the corresponding bucket.
  The process is as follows:

  1. Calculate the hash key of the first tuple’s join attribute.
     In this example, the hash key for ‘attr1’ is calculated using the built-in hash function based on the condition ‘inner.attr1 = outer.attr2’.

  2. Insert the tuple into the corresponding bucket.
     For example, if the hash key in binary notation is ‘0x000…001’ (ending in ‘001’), the tuple is inserted into the bucket with key ‘001’.

  In this documentation, this insertion operation used to build a batch is represented by the operator: $\oplus$

• (3) Insert the remaining tuples of the inner table.

• (4) Probe the first tuple of the outer table.
  The process is as follows:

  1. Calculate the hash key of the join attribute for the first outer tuple. In this example, assume the hash key for ‘attr2’ is ‘0x000…100’ (ending in ‘100’).
  2. Compare the outer tuple with the inner tuples in the batch. Since the hash key ends in ‘100’, the executor retrieves the tuples in the bucket with key ‘100’ and compares the attribute values.
  3. If the join condition is satisfied, the outer tuple and the corresponding inner tuple are joined. If not, the executor performs no action.
     

  In this example, the bucket for key ‘100’ contains Tuple_C. If ‘attr1’ of Tuple_C equals ‘attr2’ of the outer tuple (Tuple_W), the tuples are joined and stored in memory or a temporary file.
  
  In this documentation, such operation to probe a batch is represented by the operator: $\otimes$

• (5) Probe the remaining tuples of the outer table.

3.5.3.2. Hybrid Hash Join with Skew

When the tuples of the inner table cannot be stored in a single batch within work_mem, PostgreSQL uses a hybrid hash join with a skew algorithm. This method is a specialized variation of the standard hybrid hash join.

3.5.3.2.1. Basic Concept of Hybrid Hash Join

In the initial build and probe phases, PostgreSQL prepares multiple batches. The number of batches is determined by the ExecChooseHashTableSize() function and is always $2^{m}$, where $m$ is an integer. At this stage, only one batch (Batch 0) is allocated in work_mem, while the remaining batches are created as temporary files. Tuples belonging to these secondary batches are written to disk and saved using the temporary tuple storage feature.

Figure 3.28 illustrates how tuples are distributed across four ($2^{2}$) batches. In this case, the destination batch for each tuple is determined by the first two bits of the last five bits of the tuple’s hash key.

• Batch_0 stores tuples where the last five bits are between ‘00000’ and ‘00111’.
• Batch_1 stores tuples where the last five bits are between ‘01000’ and ‘01111’ and so on.

In a hybrid hash join, the build and probe phases are repeated for each batch. During the first round, all batches are created, and the first batches (Batch_0) of both the inner and outer tables are processed immediately.

In contrast, processing the second and subsequent batches requires writing to and reloading from temporary files, which is a costly process.

To optimize this, PostgreSQL also prepares a special batch called skew to process high-frequency tuples more efficiently during the first round.

3.5.3.2.2. The Skew Batch

The skew batch stores inner table tuples that are expected to join with outer table tuples possessing high Most Common Value (MCV) frequencies for the join attribute. To illustrate this mechanism, consider the following example.

Assume two tables: ‘customers’ and ‘purchase_history’.

• customers table: 10,000 rows with attributes ’name’ and ‘address’.
• purchase_history table: 1,000,000 rows with attributes ‘customer_name’ and ‘purchased_item’.
• Data Distribution: The top 10% of customers account for 70% of all purchases.

The following section describes how the hybrid hash join with skew performs in the first round when this query is executed:

testdb=# SELECT * FROM customers AS c, purchase_history AS h WHERE c.name = h.customer_name;

When the customers table is the inner table and purchase_history is the outer table, the top 10% of customers are stored in the skew batch based on the MCV statistics of the purchase_history table. It is important to note that the outer table’s MCV values are referenced to identify which inner table tuples should be inserted into the skew batch.

In the probe phase of the first round, 70% of the tuples from the outer table (purchase_history) are joined immediately with the tuples stored in the skew batch. Consequently, a more non-uniform distribution in the outer table allows a larger portion of the join to be processed in the first round, significantly reducing the overhead of writing to and reading from temporary files.

3.5.3.2.3. Operational Flow of Hybrid Hash Join with Skew

The following steps describe the operation of a hybrid hash join with skew. Refer to Figures 3.29 through 3.32.

• (1) Create a batch and a skew batch in work_mem.

• (2) Create temporary batch files for storing inner table tuples.
  In this example, three batch files are created because the inner table is divided into four batches.

• (3) Perform the build operation for the first tuple of the inner table.
  The details are as follows:

  1. If the tuple’s join attribute matches an MCV, insert it into the skew batch. Otherwise, proceed to step 2.
     In this example, if the tuple represents one of the top 10% customers, it is inserted into the skew batch.
  2. Calculate the hash key for the tuple and insert it into the corresponding batch (either the in-memory Batch 0 or a temporary file for Batches 1-3).

• (4) Perform the build operation for the remaining tuples of the inner table.

• (5) Create temporary batch files for storing outer table tuples.

• (6) Probe the skew batch if the join attribute matches an MCV.
  If the attribute of the first outer tuple matches a value in the MCV list, the executor performs a probe operation against the skew batch. Otherwise, it proceeds to step (7).
  In this example, purchase records for the top 10% of customers will be compared with tuples in the skew batch at this stage.

• (7) Perform the probe operation for the first tuple.
  Depending on the hash key, the following process occurs:

  • If the tuple belongs to Batch_0, perform the probe operation immediately against the in-memory batch.
  • Otherwise, insert the tuple into the corresponding temporary batch file (Batches 1-3).

• (8) Perform the probe operation for the remaining tuples of the outer table.
  Note that in this example, 70% of the outer table tuples are processed via the skew batch in the first round without disk I/O.

• (9) Remove the skew batch and clear Batch_0 to prepare for the second round.

• (10) Perform the build operation using the batch file ‘batch_1_in’.

• (11) Perform the probe operation using the tuples stored in the batch file ‘batch_1_out’.

• (12) Perform build and probe operations using batch files ‘batch_2_in’ and ‘batch_2_out’.

• (13) Perform build and probe operations using batch files ‘batch_3_in’ and ‘batch_3_out’.

3.5.3.3. Index Scans in Hash Join

PostgreSQL utilizes index scans within a hash join whenever possible. A specific example is shown below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

testdb=# EXPLAIN SELECT * FROM pgbench_accounts AS a, pgbench_branches AS b
testdb-#                                              WHERE a.bid = b.bid AND a.aid BETWEEN 100 AND 1000;
                                                QUERY PLAN
------------------------------------------------------------------------------------------------------
 Hash Join  (cost=1.88..51.93 rows=865 width=461)
   Hash Cond: (a.bid = b.bid)
   -> Index Scan using pgbench_accounts_pkey on pgbench_accounts a  (cost=0.43..47.73 rows=865 width=97)
        Index Cond: ((aid >= 100) AND (aid <= 1000))
   -> Hash  (cost=1.20..1.20 rows=20 width=364)
         -> Seq Scan on pgbench_branches b  (cost=0.00..1.20 rows=20 width=364)
(6 rows)

• Line 7: During the probe phase, the executor identifies and retrieves the required tuples from the pgbench_accounts table using an index scan. This occurs because the WHERE clause includes a condition on the ‘aid’ column, which is indexed.

Using an index scan during the probe phase restricts the number of outer table tuples that need to be probed against the hash table, improving overall performance.