Join Processing Algorithms

4
6

Introduction

A SQL join describes how records from different tables should match. It does not normally specify the algorithm the database must use to find those matches.

The database chooses a physical join method based on the query and available access paths. Nested-loop, hash, and merge joins solve the same matching problem in different ways, each with its own strengths and costs.

One Join, Several Execution Methods

Consider these two tables:

Students

student_id

name

department_id

101

Asha

10

102

Ravi

20

103

Meera

10

104

Neha

NULL

Departments

department_id

department_name

10

Engineering

20

Finance

30

Sales

The query is:

SELECT s.name, d.department_name
FROM students AS s
INNER JOIN departments AS d
ON s.department_id = d.department_id;

Its matching records are:

name

department_name

Asha

Engineering

Ravi

Finance

Meera

Engineering

The displayed order is illustrative. Without ORDER BY, the query does not guarantee it.

Neha has no match because ordinary equality does not evaluate to true for a NULL department ID.

Nested-Loop Join

A nested-loop join takes a record from one input and searches the other input for matches.

The inputs are commonly called:

  • Outer input: Supplies the records processed one at a time.

  • Inner input: Is searched for each outer record.

For our example, the database could take Asha’s record and compare department ID 10 with every department record. It then repeats the process for Ravi, Meera, and Neha.

A basic nested-loop algorithm can require approximately m × n comparisons for inputs containing m and n records.

It is straightforward and can evaluate many kinds of join conditions, but repeatedly scanning a large inner input can be expensive.

Block Nested-Loop Join

A block nested-loop variation processes a group of outer records together.

Instead of scanning the inner input separately for every outer record, it scans that input for a buffered block of outer records. This can reduce repeated page reads.

Its effectiveness depends on available buffer space and input sizes.

Index Nested-Loop Join

If the inner input has a suitable index, the database can perform an index lookup for each outer record.

For example:

  1. Read Asha’s department ID, 10.

  2. Look up 10 in the department index.

  3. Retrieve Engineering.

  4. Repeat for the remaining students.

This avoids scanning every department record for each student.

An index nested-loop join can work well when the outer input is small and inner lookups are selective. However, a large outer input can still cause many lookups and scattered page accesses.

An index helps only when the join condition and index organization support useful access.

Index Nested-Loop Join

Index Nested-Loop Join

Hash Join

A hash join commonly handles equality conditions such as:

s.department_id = d.department_id

It has two main phases.

Build Phase

The database reads one input and builds a hash table using the join key.

Using departments as the build input, the hash table associates keys 10, 20, and 30 with their department records.

The smaller filtered input is often a useful build-side candidate because it requires less memory, although the optimizer considers other factors too.

Hash join build and probe

Hash join build and probe

Probe Phase

The database reads the other input and hashes each join key to find candidate matches.

Asha’s key 10 reaches the group containing Engineering. Ravi’s key 20 reaches Finance.

Matching hash values are not enough. The database must check the actual join keys because different values can produce the same hash.

For the ordinary equality join shown here, Neha’s NULL key produces no match.

If the build structure exceeds available memory, the database may partition data and spill to temporary storage. Hash joins are not generally a solution for arbitrary inequality conditions.

Sort-Merge Join

A sort-merge join processes inputs ordered by their join keys.

For the example, the relevant non-null student keys are 10, 10, 20, while the department keys are 10, 20, 30.

The algorithm compares the current keys:

  • If one is smaller, advance that input.

  • If they are equal, produce the matching combinations.

  • Continue until no further matches are possible.

Both students with key 10 match Engineering.

When duplicate keys occur on both sides, every qualifying combination must be produced. Processing those groups may require buffering or revisiting records.

Existing indexes or earlier operations may provide the required ordering. Otherwise, sorting adds work and may spill to storage.

Merge joins are particularly useful for equality joins with suitably ordered inputs. Additional supported conditions depend on the database.

Sort-Merge Join

Sort-Merge Join

Comparing the Algorithms

Algorithm

Main requirement or opportunity

Main cost to consider

Basic nested loop

Can evaluate many join conditions

Repeated comparisons and inner scans

Block nested loop

Buffer space for outer blocks

Repeated inner scans for each block

Index nested loop

Useful index on the inner input

Number and cost of index lookups

Hash join

Equality join keys

Build memory and possible spilling

Sort-merge join

Inputs ordered by join keys

Sorting and duplicate-group handling

No single method is always fastest. A small indexed lookup workload and a large batch join can favor different algorithms.

How the Optimizer Chooses

The optimizer considers estimated input sizes after filtering, available indexes, key distribution, ordering, and memory requirements.

For queries involving several tables, it also chooses a join order. Joining two inputs early can either reduce later work or create a large intermediate result.

Useful checks include:

  • Are estimated and actual record counts close?

  • Is a nested loop performing unexpectedly many inner lookups?

  • Is a hash join spilling?

  • Is a merge join paying for large sorts?

  • Are duplicate keys creating more output than expected?

The join algorithm explains part of the cost, but input preparation and output size matter too.

Summary

Nested-loop joins search for matches repeatedly, index nested loops accelerate those searches, hash joins organize equality keys, and merge joins walk ordered inputs together.

The best choice depends on filtered input sizes, indexes, ordering, memory, and the number of matching records. Execution plans help reveal which strategy the database selected and where its work is concentrated.

CS Core

Read Similar Blogs

Comments0