The Effect of Join Order on Cardinality

Adjust join order to manage the growth of intermediate result sets.

In this lesson, you will learn how the sequence in which you join tables significantly impacts the size of intermediate results, known as cardinality.

When we write a query involving three or more tables, the database engine must perform the joins in a specific order. Even though joins are commutative (the final result is the same regardless of order), the intermediate results—the temporary sets created during the process—can vary wildly in size. Managing these "working sets" is the key to efficient execution.

The Problem of "Bloat"

Imagine you are joining three tables: Students, Enrollments, and Courses.

Students: 1,000 rows
Enrollments: 10,000 rows
Courses: 100 rows

If we join Students to Enrollments first, we create an intermediate set of 10,000 rows. If we then join that to Courses, we process a relatively stable amount of data.

However, if we accidentally perform a join that behaves like a Cartesian product or joins a massive, unfiltered table too early, the intermediate cardinality can explode. For example, if you join a large Logs table to a small Users table before filtering, you might temporarily hold millions of rows in memory, even if the final result set after applying a WHERE clause is only five rows.

Strategic Sequencing

To keep cardinality low, we aim to perform "restrictive" joins early. We want to reduce the size of the working set as quickly as possible.

-- Join order matters for performance
SELECT *
FROM Students s
JOIN Enrollments e ON s.id = e.student_id  -- Creates a smaller set
JOIN Courses c ON e.course_id = c.id      -- Final filter
WHERE s.status = 'Active';                -- Ideally, push this filter down

By joining tables that share highly selective criteria first, we ensure that the database engine carries the smallest possible volume of data through each subsequent step of the relational algebra tree. If we process the largest tables at the end—after they have been significantly "trimmed" by previous filters or joins—we prevent the system from wasting memory on unnecessary data combinations.

Key Takeaway: Controlling join order allows you to minimize the size of intermediate result sets, preventing performance bottlenecks caused by processing excessively large temporary data structures.