Join Algorithms, Semijoin/Antijoin Transformations, Derived Tables, and Materialization

Learning outcomes

Two SQL statements can express the same business question while presenting different optimization opportunities. MySQL may reorder inner joins, use indexed nested-loop lookups, build a hash table for an equijoin, transform an EXISTS into a semijoin, transform eligible negated forms into an antijoin, or merge/materialize a derived table or common table expression (CTE). The skill is not memorizing flags—it is recognizing operators and validating their work.

Nested lookups versus hash joins

When an outer iterator produces a row and MySQL probes an index on the inner table, you can think of the execution as a nested sequence of lookups. When an equijoin has no useful join index, MySQL 8.4 can use a hash join: build a hash structure from one input and probe it with the other. Neither algorithm is universally superior; the optimizer chooses according to available access paths and costs.

Create two small disposable tables whose join key is intentionally unindexed:

USE servicehub_plan_lab;DROP TABLE IF EXISTS hash_left,hash_right;CREATE TABLE hash_left (id INT PRIMARY KEY, k INT NOT NULL, payload CHAR(20)) ENGINE=InnoDB;CREATE TABLE hash_right (id INT PRIMARY KEY, k INT NOT NULL, payload CHAR(20)) ENGINE=InnoDB;SET SESSION cte_max_recursion_depth=10000;INSERT INTO hash_leftWITH RECURSIVE s AS (SELECT 1 n UNION ALL SELECT n+1 FROM s WHERE n<5000)SELECT n,MOD(n,800),RPAD('L',20,'L') FROM s;INSERT INTO hash_rightWITH RECURSIVE s AS (SELECT 1 n UNION ALL SELECT n+1 FROM s WHERE n<4000)SELECT n,MOD(n,800),RPAD('R',20,'R') FROM s;ANALYZE TABLE hash_left,hash_right;EXPLAIN FORMAT=TREESELECT COUNT(*) FROM hash_left AS l JOIN hash_right AS r ON r.k=l.k;EXPLAIN ANALYZESELECT COUNT(*) FROM hash_left AS l JOIN hash_right AS r ON r.k=l.k;

Expected plan pattern on MySQL 8.4 when hash join is applicable: TREE output contains an Inner hash join plus a Hash child. If your build selects a different legal plan, record it rather than rewriting the lesson result. Now add a real join index and observe the candidate set change.

CREATE INDEX ix_hash_right_k ON hash_right(k);ANALYZE TABLE hash_right;EXPLAIN FORMAT=TREESELECT COUNT(*) FROM hash_left AS l JOIN hash_right AS r ON r.k=l.k;EXPLAIN ANALYZESELECT COUNT(*) FROM hash_left AS l JOIN hash_right AS r ON r.k=l.k;

The new index does not guarantee a nested lookup for every dataset, but it gives the optimizer another strategy to cost. Compare actual rows, loops, and timing instead of declaring one algorithm “modern” and therefore always faster.

Semijoin: “does a match exist?”

An ordinary inner join returns an outer row once for every matching inner row. An existence question usually wants at most one copy of the outer row. MySQL can transform eligible IN or EXISTS subqueries into semijoin strategies such as table pullout, first match, loose scan, duplicate weedout, or materialization.

EXPLAIN FORMAT=TREESELECT c.customer_id,c.segmentFROM customers AS cWHERE EXISTS (  SELECT 1  FROM work_orders AS w  WHERE w.customer_id=c.customer_id    AND w.status='open');EXPLAIN ANALYZESELECT c.customer_id,c.segmentFROM customers AS cWHERE EXISTS (  SELECT 1 FROM work_orders AS w  WHERE w.customer_id=c.customer_id AND w.status='open');

Do not insist that one specific semijoin strategy appear; strategy selection is cost-based. The semantic requirement is that each qualifying customer appears once because the question asks whether at least one matching open work order exists.

Antijoin: “does no match exist?” and NULL awareness

NOT EXISTS naturally expresses customers with no matching row. Eligible negated subqueries can be transformed to antijoins. This is usually easier to reason about than NOT IN when NULL can appear in the subquery result, because SQL three-valued logic can make NOT IN unexpectedly unknown.

EXPLAIN FORMAT=TREESELECT c.customer_idFROM customers AS cWHERE NOT EXISTS (  SELECT 1 FROM work_orders AS w  WHERE w.customer_id=c.customer_id AND w.status='open');EXPLAIN ANALYZESELECT c.customer_idFROM customers AS cWHERE NOT EXISTS (  SELECT 1 FROM work_orders AS w  WHERE w.customer_id=c.customer_id AND w.status='open');

Look for antijoin-oriented TREE operators or a semantically equivalent strategy. The goal is to connect SQL meaning to optimizer transformation, not to memorize one printed phrase.

Derived tables: merge when possible, materialize when needed

A simple derived table may be merged into the outer query, effectively removing a materialization boundary. Aggregation, DISTINCT, grouping, window functions, and other constructs can prevent merging and require a temporary result.

-- Simple derived table: often mergeable.EXPLAIN FORMAT=TREESELECT d.work_order_id,d.customer_idFROM (  SELECT work_order_id,customer_id,tenant_id,status  FROM work_orders) AS dWHERE d.tenant_id=17 AND d.status='open';-- Aggregation creates a meaningful boundary: materialization is plausible/required.EXPLAIN FORMAT=TREESELECT c.customer_id,c.segment,x.open_countFROM customers AS cJOIN (  SELECT customer_id,COUNT(*) AS open_count  FROM work_orders  WHERE status='open'  GROUP BY customer_id) AS x ON x.customer_id=c.customer_idWHERE c.tenant_id=17;EXPLAIN ANALYZESELECT c.customer_id,c.segment,x.open_countFROM customers AS cJOIN (  SELECT customer_id,COUNT(*) AS open_count  FROM work_orders  WHERE status='open'  GROUP BY customer_id) AS x ON x.customer_id=c.customer_idWHERE c.tenant_id=17;

When materialized, MySQL creates an internal temporary result for the derived table and may add an index to that temporary structure when beneficial. Do not assume “temporary table” means a coding mistake; sometimes materialization is exactly the cheapest legal execution strategy.

CTEs follow similar merge/materialize reasoning

Nonrecursive CTEs can also be merged or materialized depending on query structure and optimizer decisions. A CTE referenced multiple times may be materialized once and reused, depending on the plan. Recursive CTEs are a different mechanism and are not treated as ordinary merge candidates.

EXPLAIN FORMAT=TREEWITH recent AS (  SELECT work_order_id,customer_id,tenant_id,status,opened_at  FROM work_orders  WHERE opened_at >= '2026-06-01')SELECT c.segment,COUNT(*)FROM recent AS rJOIN customers AS c ON c.customer_id=r.customer_idWHERE r.tenant_id=17 AND r.status='open'GROUP BY c.segment;

If the CTE disappears into the outer plan, that is evidence of merging. If a materialization operator appears, explain which SQL feature or reuse pattern makes a separate result reasonable.

When a hint is useful: controlled experiment only

Optimizer hints such as NO_MERGE, SEMIJOIN, NO_SEMIJOIN, or join-order hints can isolate a hypothesis. They should not be the first teaching tool because enabling an optimization only permits it when applicable; it does not necessarily force one physical operator, and hint behavior can evolve.

Verification and cleanup

DROP TABLE IF EXISTS hash_left,hash_right;SHOW INDEX FROM work_orders;SELECT VERSION() AS server_version;

Summary and next step

You can now recognize several optimizer strategies without reducing tuning to flags. Lesson 5 combines everything into a plan-regression workflow using baselines, invisible indexes, statistics checks, and carefully bounded hints.

Authoritative references

• MySQL 8.4 — Hash Join Optimization
• MySQL 8.4 — Semijoin and Antijoin Transformations
• MySQL 8.4 — Subquery/Derived/CTE Optimization
• MySQL 8.4 — Derived Tables