The Complete Guide to SQL Joins and Join Strategies

How It Works

1. Build Phase
   The database picks the smaller of the two input tables (called the build side) and loads it into memory, creating a hash table keyed by the join column.

2. Probe Phase
   It then scans the larger table (called the probe side), applies the same hash function to the join column, and looks for matches in the hash table.

3. Optional: Partitioning
   If the build side is too large to fit in memory, it may be partitioned into smaller chunks, potentially spilling to disk—this is known as a grace hash join.

Visualization

Think of it like scanning a phone book (build side), storing names by first letter, and then rapidly checking an incoming list (probe side) to find matches in the correct letter bucket.

Performance Notes

• Fast for large joins, assuming the build side fits in memory.

• Insensitive to sort order (unlike merge joins).

• Used heavily in data warehouses (e.g., joining small dimension tables to large fact tables).

• Not ideal for non-equi joins (e.g., <, >).

Real-World Usage

Hash joins power many warehouse-style queries like:

SELECT f.order_id, d.region
FROM fact_sales f
JOIN dim_store d ON f.store_id = d.store_id;

Here, dim_store is small and becomes the build side, while fact_sales is scanned and matched against the hash buckets.

What Is Nested Loop Join?

The nested loop join is the simplest algorithm—conceptually and operationally. It checks every possible combination of rows, making it brute-force but flexible.

How It Works

1. For each row in the outer table:

2. Scan every row in the inner table.

3. For each pair, evaluate the join condition.

4. If the condition matches, return the combined row.

This is often how you would implement a join manually in code if you didn’t know better.

Optimizations

• When the inner table has an index on the join column, this becomes an Index Nested Loop Join, dramatically reducing scan time.

• If the outer table is filtered heavily, the number of loop iterations shrinks, making it viable even for larger data.

Best Used When

• One table is small (or highly filtered).

• No suitable hash or sort order is available.

• Joins are non-equi (e.g., range joins like a.created_at < b.cutoff).

Real-World Usage

Nested loops are common in OLTP systems:

SELECT u.name, o.order_id
FROM users u
JOIN orders o ON u.user_id = o.user_id
WHERE u.status = 'active';

If users is filtered down to a handful of rows, the system may use a nested loop join—even if orders has millions of rows.

Performance Trade-Offs

• Very flexible (supports any condition), but

• O(n²) worst-case complexity for full scans.

• Depends heavily on indexes or small row counts.

What Is Merge Join (Sort-Merge Join)?

The merge join is ideal when both input tables are already sorted by the join key. It’s highly efficient because it can walk both inputs in lockstep—like zipping two ordered lists.

How It Works

1. Sort both tables by the join key (if not already sorted).

2. Start from the beginning of both.

3. Compare keys:

   • If equal, emit a match and advance both.

   • If not, advance the lower-key row.

4. Repeat until both tables are exhausted.

Visualization

Think of it like merging two sorted Excel sheets: you scroll down both sheets at the same time and compare values as you go.

When It Shines

• Both sides are pre-sorted, or

• Indexes can be used to access rows in order.

Drawbacks

• Sorting is expensive if not already in place.

• Only works for equi-joins.

• Not suited for hash-based partitioned data in distributed systems unless a sort phase is introduced.

Use Case

SELECT a.id, b.name
FROM orders a
JOIN customers b ON a.customer_id = b.customer_id
ORDER BY a.customer_id;

Summary: Choosing the Right Join Algorithm

In practice, modern engines (like StarRocks, PostgreSQL, or Spark SQL) choose join algorithms automatically based on cost-based optimization (CBO) and runtime statistics. But knowing how they work helps you write queries that play to the engine’s strengths—and avoid accidentally triggering expensive plans.

Want to go deeper? We can next explore distributed join strategies like broadcast joins, shuffle joins, and colocate joins — especially relevant when working in MPP systems like StarRocks or BigQuery.

When to Use Which Join Strategy

Distributed join strategies are essential for scalable, high-performance analytics. Whether you're designing queries for batch reporting or real-time dashboards, understanding these strategies—and how they’re executed behind the scenes—helps you anticipate bottlenecks, control costs, and design better data systems.

FAQ: SQL Joins, Algorithms, and Execution Strategies

1. What happens when a join condition is omitted?

If you omit the join condition in a regular JOIN (e.g., INNER JOIN or LEFT JOIN), the result is a Cartesian product, equivalent to a CROSS JOIN. Every row from the left table is combined with every row from the right table. This is rarely what you want for large tables and can quickly balloon to billions of rows.

2. Can you join on non-equality conditions (e.g., <, >, BETWEEN)?

Yes, but not all join algorithms support them:

• Hash joins support only equi-joins (e.g., a.id = b.id).

• Merge joins and nested loop joins can handle range-based or inequality joins, such as:

SELECT *
FROM events e
JOIN time_windows t ON e.timestamp BETWEEN t.start_time AND t.end_time;

However, range joins can be expensive and may default to nested loop joins unless indexes or pre-sorted data are available.

3. What’s the difference between JOIN and INNER JOIN?

They're the same. By SQL standard, JOIN defaults to INNER JOIN. This means:

SELECT * FROM A JOIN B ON A.id = B.id;

is functionally equivalent to:

SELECT * FROM A INNER JOIN B ON A.id = B.id;

4. How does a database engine choose a join algorithm?

Modern query engines use a cost-based optimizer (CBO) to decide. The optimizer analyzes:

• Table sizes and row count estimates

• Availability of indexes

• Whether the inputs are sorted

• Memory and network cost estimates

• Distribution (single-node or multi-node)

Based on this, it selects a plan—often visible via EXPLAIN or EXPLAIN ANALYZE.

In StarRocks, for example, the optimizer may automatically select a bucket shuffle join if table metadata indicates compatible bucketing.

5. What if a join returns duplicate rows—why is that happening?

Duplicates occur when the join key matches multiple rows on either side. For example:

-- If user_id = 1 appears 3 times in orders, and once in users
-- the result will have 3 rows for that user
SELECT *
FROM users
JOIN orders ON users.user_id = orders.user_id;

To eliminate duplicates, consider using DISTINCT or aggregation, but only if semantically appropriate. Duplicates are expected in many-to-one or many-to-many joins.

6. Do indexes improve join performance in distributed systems?

Not directly.

In distributed systems like StarRocks or Trino, index-based optimizations (e.g., index nested loop joins) are not typically used, because:

• Tables are columnar and optimized for bulk scan + vectorized processing.

• Joins are handled using hashing or shuffling, not indexed lookups.

• Indexes are more relevant for OLTP-style systems like PostgreSQL or MySQL.

However, pre-sorting and bucketing data can play a similar role in optimizing distributed joins.

7. What’s the performance impact of joining large tables without filtering?

Joining two large tables (e.g., billions of rows each) without filters or selective predicates can:

• Force shuffle joins, incurring heavy network traffic

• Require large memory buffers for intermediate data

• Overwhelm worker nodes or cause out-of-memory (OOM) errors

Best practice: Filter as early as possible. Push predicates down before the join to reduce data volume.

8. How do distributed joins handle data skew (e.g., one key is very frequent)?

Data skew (e.g., 90% of rows sharing a single join key) causes load imbalance:

• Shuffle joins: One node may receive a disproportionate amount of data for that key.

• Broadcast joins: Not affected by skew but still subject to memory limits.

To mitigate skew:

• Use salting or key splitting to artificially break up the skewed key.

• Use colocated joins when possible to preserve data affinity.

• StarRocks also supports adaptive query execution, which can sometimes handle skew dynamically.

9. Is FULL OUTER JOIN supported by all distributed engines?

Not always.

• Engines like StarRocks and Spark SQL support FULL OUTER JOIN, but it’s more complex to execute in a distributed setting because it requires tracking unmatched rows on both sides, which may reside on different nodes.

• Some engines do not support full outer joins or simulate them using a UNION of LEFT and RIGHT joins.

Check engine-specific documentation before relying on FULL OUTER JOIN in production.

10. Can you mix join strategies in a single query?

Yes. Complex queries involving multiple joins may use different algorithms or distribution strategies per join.

For example:

SELECT ...
FROM big_fact_table f
JOIN small_dim_1 d1 ON f.key1 = d1.key
JOIN small_dim_2 d2 ON f.key2 = d2.key;

• The optimizer may choose a broadcast join for d1

• A shuffle join for d2 if it's slightly larger

• And fall back to a nested loop for a correlated subquery elsewhere

This is known as a hybrid join plan, and it’s common in cost-based optimization.

11. How do materialized views affect join strategy?

Materialized views (MVs) precompute joins, so queries on top of MVs often avoid the join altogether at runtime.

In StarRocks:

• If a join result is already materialized, the optimizer can rewrite the query to scan from the MV instead of computing the join again.

• This drastically reduces compute time, memory use, and network I/O.

• MVs also help with bucket shuffle joins, as the MV can be pre-bucketed on the join key.

12. What happens if the join key contains NULLs?

By SQL standard:

• NULL = NULL is not true, so rows with NULL join keys do not match in INNER or OUTER joins.

• In LEFT JOIN, if the left-side key is NULL, you get a row with NULLs from the right side.

• In FULL OUTER JOIN, if both join keys are NULL, no match will occur.

To explicitly join on NULLs, you’d need to add logic like:

ON a.key = b.key OR (a.key IS NULL AND b.key IS NULL)

But this is rarely advisable due to performance complexity.