New data technologies are being invented all the time. While it’s impossible to track them all, understanding the core design patterns behind these innovations is crucial. Why? Because these patterns reveal the specific problems they were designed to solve, making it easier for you to evaluate and adopt the right solutions or address performance and data modeling challenges in your existing systems.

In this post, I’ll focus on join types, using a scenario where we have two datasets: T1 with N records and a join column k1, and T2 with M records and a join column k2. Let’s assume N > M for simplicity.

You might be surprised to learn that there are only three main types of joins, though many variations exist. Understanding these core joins is crucial.

1. Nested Loop Join:

This join compares every record in T1 to every record in T2, resulting in a time complexity of O(N * M). However, several optimizations can improve performance:

• If T2 has a B-tree index on k2, the time complexity becomes O(N * log M) on average.
• If k2 has a hash index, the average case becomes O(N).
• If k2 is sorted, applying a binary search results in O(N * log M) on average.

When to Use: Best for small tables, when you have an index on join columns, or for non-equi joins (e.g., <=, >=, <, >, != conditions on key columns).

Disadvantages: Inefficient and slow for large datasets.

2. Sort-Merge Join:

In this join, both datasets are sorted on their respective key columns (T1 by k1 and T2 by k2) with a time complexity of O(N log N + M log M). Once sorted, the merge step has an average time complexity of O(N + M). Therefore, the overall complexity is roughly O(N log N) (simplifying by omitting the smaller terms).

When to Use: Best for large datasets, especially if one or both tables are already sorted or have a B-tree index on the key column. It also supports non-equi joins (e.g., <=, >=, <, >, != conditions) and generalizes well to distributed algorithms.

Disadvantages: High overhead for small datasets and computationally expensive if data is not pre-sorted. Less efficient than hash joins for equality joins on unsorted data.

3. Hash Join:

In a hash join, the key values from T2 are hashed and stored in a temporary hash table. Then T1 is scanned, and the hash values of k1 are computed to look them up in the temporary hash table. The average case time complexity is O(N + M), or simply O(N).

When to Use: Ideal for large tables, equi-joins, unsorted data, and when sufficient memory is available to build a hash table. Generalizes well to distributed algorithms.

Disadvantages: Not suitable for non-equality joins (e.g., <=, >=, <, >, !=). Can be memory-intensive for very large tables, and performance suffers if the hash table doesn’t fit in memory.

A General Note: In the worst-case scenario, all joins degrade to O(N * M). This typically happens when a large percentage of the key column values are repeated, causing inefficiencies.

Wait a minute—what about real life, where tables often don’t fit into memory, and joins involve network and I/O to physical storage? You’re absolutely right. What I’ve described so far are the basic algorithms. In real-world databases and distributed systems like Spark, I/O and networking play a major role. This has led to various optimizations, such as Block Nested Loop Join, Batched Key Access Join, Broadcast Joins, Shuffle Hash Join, Semi Join, and many others. However, at their core, all of these are just variations of the three fundamental joins: Nested Loop Join, Sort-Merge Join, and Hash Join.