Join algorithms (nested loop, sort-merge, hash join) in DBMS Theory - Time & Space Complexity

Time Complexity: Join algorithms (nested loop, sort-merge, hash join)

O(n^2) for Nested Loop, O(n log n) for Sort-Merge, O(n) for Hash Join

Understanding Time Complexity

When databases combine tables using joins, the method chosen affects how long it takes. Understanding time complexity helps us see how the work grows as tables get bigger.

We want to know: How does the time to join tables change as the number of rows increases?

Scenario Under Consideration

Analyze the time complexity of these three common join methods.

-- Nested Loop Join
FOR each row in TableA LOOP
  FOR each row in TableB LOOP
    IF join condition matches THEN
      output joined row;
    END IF;
  END LOOP;
END LOOP;

-- Sort-Merge Join
Sort TableA and TableB on join key;
Merge rows by scanning both sorted tables once;

-- Hash Join
Build hash table on smaller table using join key;
Probe hash table with rows from larger table;

These snippets show how each join method processes rows to combine tables.

Identify Repeating Operations

Look at the main repeated steps in each join:

• Nested Loop Join: Two loops, one inside the other, checking every pair of rows.
• Sort-Merge Join: Sorting both tables, then one pass through both sorted lists.
• Hash Join: Building a hash table from one table, then checking each row of the other table against it.

How Execution Grows With Input

Imagine both tables have n rows:

Input Size (n)	Approx. Operations
10	Nested Loop: 100, Sort-Merge: ~66 + 20, Hash Join: ~10 + 10
100	Nested Loop: 10,000, Sort-Merge: ~1,300 + 200, Hash Join: ~100 + 100
1000	Nested Loop: 1,000,000, Sort-Merge: ~20,000 + 2,000, Hash Join: ~1000 + 1000

Nested loops grow very fast as tables get bigger, while sort-merge and hash join grow more slowly, roughly doubling or slightly more.

Final Time Complexity

Time Complexity: O(n^2) for Nested Loop Join, O(n log n) for Sort-Merge Join, and O(n) for Hash Join

This means nested loops take much longer as tables grow, sorting takes more time but less than nested loops, and hashing is usually fastest for large tables.

Common Mistake

[X] Wrong: "All join methods take the same time regardless of table size."

[OK] Correct: Different join methods handle data differently, so their time grows at different rates as tables get bigger.

Interview Connect

Knowing how join methods scale helps you explain database performance clearly. This skill shows you understand how data size affects query speed, a key part of working with databases.

Self-Check

What if one table is much smaller than the other? How would that affect the time complexity of each join method?