Avoid Cartesian Product — Solution & ExplanationProblems / Avoid Cartesian Product / EditorialApproachThe critical optimization is ensuring the join is an equi-join, not a cartesian product:

Equi-join on dept_id — each employee matches exactly one department.

Aggregate per department to get headcount, salary stats.

Compute budget_remaining as budget minus total salary.

The Cartesian TrapCommon mistakes that create accidental cross joins:

FROM employees, departments without a WHERE clause

Missing ON condition in JOIN

Joining on a non-unique column when you meant to use the primary key

With 30 employees and 5 departments:

Equi-join: 30 rows (correct)

Cross join: 150 rows (incorrect, inflated counts and sums)

At production scale (1M × 100), the cross join produces 100M rows, likely causing OOM errors or hour-long queries.Complexity

Equi-join: O(n + m) with hash join

Cross join: O(n × m) — quadratic and catastrophic at scale

Hints

Make sure your JOIN has an ON condition: e.dept_id = d.dept_id.

A comma-separated FROM clause (FROM a, b) without WHERE is a cross join.

In PySpark, use .join(departments, on='dept_id') — never .crossJoin().

Solve Avoid Cartesian Product yourself →