How joins are executed

2.1 A join is a pair generator followed by a filter

Physically, a join can be seen as two steps: form candidate pairs from the two inputs, then keep the pairs that satisfy the condition. An inner join discards everything that fails the condition. An outer join keeps the unmatched left or right rows and pads the missing side with NULL. A cross join is the special case where every pair is kept.

That model explains the first thing to check on a suspicious join: the number of candidate pairs. Two tables with n and m rows have n times m candidate pairs before the condition runs, and a condition that matches many pairs per row can multiply the result well beyond either input. The engine picks a smarter algorithm than materialising every pair, but no algorithm can fix a condition that is logically too loose.

2.2 Three ways to match rows

The nested loop algorithm takes a row from one input and looks for its partners in the other input. With no index it scans the whole second input, which costs n times m row checks. With an index on the join column it turns each lookup into a seek, and the cost drops to about n index probes. SQLite reports this family of plans as SCAN for the outer input and SEARCH for the inner input, and it can build an automatic index for the inner side when the statistics justify one.

The hash join builds a hash table on the join key of one input, then probes it with rows from the other input. It needs memory for the table, wins when neither side is indexed and the condition is equality, and shows up in PostgreSQL plans as Hash Join. The merge join sorts both inputs by the join key and walks them together, which wins when the inputs already arrive sorted, for example because an index on the join column exists. PostgreSQL reports Merge Join. A good interview answer names all three and gives one condition under which each wins.

2.3 Join order and the planner

The planner chooses which input to scan and which to search, and that decision changes the work. The usual heuristic is to drive with the filtered, smaller input and probe the larger one through an index. Without statistics, a planner can pick badly, and a query that runs in milliseconds with better information can crawl without it. ANALYZE in SQLite and ANALYZE in PostgreSQL refresh the statistics the planner reads.

The plan below joins students and enrollments. SQLite scans enrollments and looks up students by primary key, which is a seek on the rowid. That is the direction to expect when the filter is on the small side of the relationship: one student per enrollment is a single seek, while the reverse direction would multiply rows.

EXPLAIN QUERY PLAN
SELECT s.name, e.status
FROM students s
JOIN enrollments e ON s.student_id = e.student_id;

SCAN e
SEARCH s USING INTEGER PRIMARY KEY (rowid=?)

2.4 Trace a left join

Take SELECT c.course_code, i.name FROM courses c LEFT JOIN instructors i ON c.instructor_id = i.instructor_id. The first block is the left input: six courses, one of which has a NULL instructor_id. The second block is the joined result. Python Basics has no instructor, so the name column is NULL while the left-side row stays.

The condition matched five rows and produced one unmatched row, so a left join returns six rows. If the query swapped to RIGHT JOIN, the unmatched course would still be discarded and the unassigned instructor, Tara Singh, would appear with a NULL course instead. Redirecting a left join by writing a filter on the right table in WHERE is the next trap; the filter runs after the NULL padding, and a condition such as WHERE i.name <> 'Nadia Sheikh' also removes every row whose name is NULL.

SELECT c.course_code, c.title, c.instructor_id
FROM courses c
ORDER BY c.course_code;

course_code | title                   | instructor_id
------------+-------------------------+--------------
CN          | Computer Networks       | 3
DS          | Data Structures         | 2
ML          | Machine Learning Basics | 4
PY          | Python Basics           | NULL
SQL         | SQL and Databases       | 1
WEB         | Web Development         | 4

SELECT c.course_code, i.name
FROM courses c
LEFT JOIN instructors i ON c.instructor_id = i.instructor_id
ORDER BY c.course_code;

course_code | name
------------+-------------
CN          | Nadia Sheikh
DS          | Arjun Das
ML          | Vikram Rao
PY          | NULL
SQL         | Priya Menon
WEB         | Vikram Rao

2.5 Fan-out double counting

Joining a parent table to a child table repeats the parent's columns once per child row. That is correct for a detail report and wrong for an aggregate that was written against the parent table. The two queries below show the difference. The first sums the course fees once per course and gets 33994. The second sums the same fees once per enrollment and gets 72486, because each course repeats for every student who joined it.

The fix is to aggregate before joining, or to aggregate with a distinct-aware expression that matches the question. In this case SUM(DISTINCT c.fee) would hide the bug only by accident, because two courses can share the same fee. The reliable pattern is a summary subquery joined back to the parent, and module five shows that pattern. The lesson here is to check the grain of the two inputs before writing the aggregate.

SELECT SUM(c.fee) AS fee_per_course FROM courses c;
SELECT SUM(c.fee) AS fee_per_enrollment
FROM courses c JOIN enrollments e ON e.course_code = c.course_code;

fee_per_course
--------------
33994
fee_per_enrollment
------------------
72486

2.6 ON versus WHERE on an outer join

For an inner join, a condition in ON and the same condition in WHERE usually produce the same result. For an outer join they do not. The ON condition decides which right rows count as a match and leaves unmatched left rows in place with NULLs. A WHERE condition on the right table runs after padding, so it filters out the NULL rows and the query behaves like an inner join.

Compare the row counts below. The left join keeps 15 rows including the unmatched course CN. Adding WHERE e.status = 'active' drops CN and all inactive enrollments, leaving 10, which is exactly the inner join result. When the intent is "all courses, plus their active enrollments", the status condition belongs in ON, not in WHERE. This is the most common outer join bug in production reports.

SELECT COUNT(*) AS left_rows
FROM courses c LEFT JOIN enrollments e ON e.course_code = c.course_code;
SELECT COUNT(*) AS filtered_rows
FROM courses c LEFT JOIN enrollments e ON e.course_code = c.course_code
WHERE e.status = 'active';

left_rows
---------
15
filtered_rows
-------------
10

2.7 Set operation mechanics

UNION must remove duplicates, so it sorts or hashes the combined rows before returning them. UNION ALL skips that step and simply appends one result to the other, which is why it is cheaper and why interviewers ask for the difference. The count query below returns 8 rows for UNION and 14 for UNION ALL on the two city lists, because UNION collapses Delhi, Mumbai, Kolkata and Bengaluru that appear in both tables.

INTERSECT and EXCEPT also compare whole rows and need a comparable structure. SQLite sorts or hashes both inputs. The portable rule is to put the same number of columns in the same order on both sides, keep the types compatible, and use ORDER BY at the end only, where it can sort the combined result. ORDER BY inside the individual queries is not allowed in standard SQL without parentheses, and even where an engine accepts it the sort can be lost.

SELECT COUNT(*) AS union_rows
FROM (SELECT city FROM students UNION SELECT city FROM instructors);
SELECT COUNT(*) AS union_all_rows
FROM (SELECT city FROM students UNION ALL SELECT city FROM instructors);

union_rows
----------
8
union_all_rows
--------------
14

2.8 Where SQLite and PostgreSQL differ

Neither engine promises the join order the author wrote. The planner is free to build the same result another way, and the only stable contract is the result set, not the physical order of the rows.

2.9 Common mistakes

• Aggregating a parent column after joining to a child table and counting or summing it several times.
• Filtering the right side of a left join in WHERE and silently converting it to an inner join.
• Expecting a join to preserve row order. Only ORDER BY does that.
• Trusting a plan without statistics on a large table.
• Assuming UNION ALL is always safe on duplicate data that a later step treats as unique.