SQL Joins and Join Strategies

What are SQL joins?

SQL joins are a cornerstone of relational databases. They allow us to combine data from multiple tables based on logical relationships, typically defined by foreign keys. Whether you're writing ad-hoc queries, building dashboards, or designing data pipelines, understanding joins is essential for writing efficient, correct SQL — especially when working with large datasets or distributed query engines like StarRocks, Trino, or BigQuery.

Let’s walk through the different types of joins, how they are executed under the hood, and how modern systems optimize join strategies for performance and scalability.

What Are the Different Types of Joins in SQL?

To understand how SQL joins work, let’s start with two commonly used example tables: one listing employees, and another tracking their salaries.

Table 1: Employees

Table 2: Salaries

We’ll use these two tables to demonstrate each join type in SQL and examine what kind of results they produce.

What Is Inner Join?

The Inner Join returns rows when there is at least one match in both tables. It is the most common type of join because it allows for the combination of rows between two tables wherever there is a matching column value.

Example - This example retrieves the names and salaries of employees whose IDs are present in both the employees and salaries tables:

SELECT a.name, b.salaryFROM employees aINNER JOIN salaries b ON a.employee_id = b.employee_id;

The query performs an Inner Join on employees and salaries using the employee_id column as the join condition. It will return rows only where there is a matching employee_id in both tables, ensuring that only employees with corresponding salary records are listed.

What Is Left Outer Join (Left Join)?

A Left Outer Join returns all rows from the left table, along with matched rows from the right table. If there is no match, the result from the right table will be NULL.

Example - Lists all employees and their salaries, including those employees who do not have a salary record:

SELECT a.name, b.salaryFROM employees aLEFT JOIN salaries b ON a.employee_id = b.employee_id;

This query lists every employee regardless of whether they have a matching salary record in the salaries table. For employees without salary records, the salary column in the result set will show NULL.

What Is Right Outer Join (Right Join)?

The Right Join returns all rows from the right table and the matched rows from the left table. If there is no match, the result is NULL on the side of the left table.

Example - To display all salary records along with the names of the employees, including salaries that do not match any employee ID:

SELECT a.name, b.salaryFROM employees aRIGHT JOIN salaries b ON a.employee_id = b.employee_id;

This query ensures every salary is listed along with the employee name if available. If a salary record does not have a corresponding employee record, the name field in the result will be NULL.

What Is Full Outer Join (Full Join)?

A Full Outer Join returns rows when there is a match in one of the tables. If there is no match, the result is NULL on the side of the table without a match.

Example - To combine all records from both employees and salaries, filling in NULL where there is no match on either side:

SELECT a.name, b.salaryFROM employees aFULL OUTER JOIN salaries b ON a.employee_id = b.employee_id;

This query displays all entries from both tables. Where an employee does not have a salary record, or a salary does not have an associated employee, the result will show NULL for the missing part.

What Is Cross Join?

The Cross Join returns the Cartesian product of rows from the tables in the join. It combines each row of the first table with each row of the second table.

Example - To illustrate the combination of every possible pair of rows from the two tables, regardless of any relationship between them:

SELECT a.name, b.salaryFROM employees aCROSS JOIN salaries b;

This query does not use a join condition. It simply multiplies each row from employees with each row from salaries, leading to every possible combination.

What Is Self Join?

A Self Join is employed to join a table to itself as if the table were two tables, temporarily renaming at least one table in the SQL statement to facilitate the join.

Example - To find relationships within the same table, such as identifying employees who are managed by other employees:

SELECT A.name AS Employee1, B.name AS Employee2FROM employees A, employees BWHERE A.manager_id = B.employee_id;

In this query, the employees table is joined to itself to compare each employee against each other to find matching manager-employee relationships. The result lists pairs of employees where one is the manager of the other.

What Is Semi Join?

A Semi Join is a specialized type of join that returns rows from the first table only if there is at least one matching row in the second table. Unlike Inner Join, it does not return any columns from the second table, nor does it duplicate the rows from the first table if there are multiple matches in the second table. It's particularly useful for filtering data based on the existence of a relationship in another table, without actually retrieving data from that other table.

Example - Filters employees based on the existence of corresponding salary records:

SELECT a.nameFROM employees aWHERE EXISTS (SELECT 1FROM salaries bWHERE a.employee_id = b.employee_id);

This query uses a subquery with the EXISTS operator to check for the presence of at least one matching row in the salaries table for each row in the employees table. It returns only the names of those employees who have corresponding entries in the salaries table.

What Is ANTI Join?

An ANTI Join returns rows from the first table where there are no corresponding rows in the second table. This join is useful for identifying records in one table that do not have related records in another table, which can be particularly helpful for data validation or identifying missing entries.

Example - Lists employees who do not have salary records:

SELECT a.nameFROM employees aWHERE NOT EXISTS (SELECT 1FROM salaries bWHERE a.employee_id = b.employee_id);

This query employs a subquery within the NOT EXISTS clause to check for the absence of matching rows in the salaries table. It returns the names of employees who do not have corresponding salary entries, effectively performing an exclusion filter.

What are JOIN Algorithms?

When you write a SQL query that includes a JOIN, you're describing what result you want—but not how to compute it. That job falls to the database engine, which selects a join algorithm to determine how rows from different tables are matched and combined based on the join condition (usually an equality comparison on a shared key).

Join algorithms are foundational to query performance. They define the mechanics of data access, comparison, and row combination—often at a low level that you don’t see unless you dig into execution plans. But understanding how they work is critical, especially when dealing with large tables or distributed systems, because the wrong algorithm can turn a 100ms query into a multi-minute one.

Why Join Algorithms Matter

Imagine trying to join a table with 10 million rows to another with 5 million. There are many ways to do this:

• Should we scan every row in both tables and compare all combinations (brute force)?
• Should we pre-sort the tables and scan them in sync?
• Should we build a hash table on one side to accelerate lookup?

Each approach has trade-offs. Some are faster but use more memory. Others are slower but more general-purpose. Which one gets used depends on many factors:

• Data size: Is one table tiny and the other huge, or are both large?
• Index availability: Is the join column indexed?
• Sort order: Are either of the inputs already sorted on the join key?
• Memory constraints: Can we afford to load a table into memory?
• Execution environment: Are we on a single machine, or a distributed system like StarRocks or Spark?

Understanding these variables helps you design queries—and sometimes tables—that are more optimizer-friendly and more efficient at runtime.

Let’s now break down the main types of join algorithms: Hash Join, Nested Loop Join, and Merge (Sort-Merge) Join. We’ll also examine how modern query engines make decisions about which one to use in different situations.

What Is Hash Join?

The hash join is the workhorse of modern analytical databases, especially in columnar systems and MPP (Massively Parallel Processing) environments. It's designed for equi-joins (e.g., a.key = b.key) and works well when one table is significantly smaller than the other.

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.regionFROM fact_sales fJOIN 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_idFROM users uJOIN orders o ON u.user_id = o.user_idWHERE 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.nameFROM orders aJOIN customers b ON a.customer_id = b.customer_idORDER BY a.customer_id;

If both tables are already indexed by customer_id, a merge join is ideal.

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.