Craig Freedman’s Query Processing Series – December 2006: The Semi-join Transformation

Part 7 of my series on Craig Freedman’s SQL Server query-processing blog (part 6, November 2006, is here). December 2006 brought a single article before a longer writing break — but it’s a gem about optimizer internals, and it answers a very practical indexing question along the way.

All plan screenshots in this post are my own, made in SSMS with “Include Actual Execution Plan” (Ctrl+M). Want to follow along? Run this one-time setup in a scratch database (it uses GENERATE_SERIES, so SQL Server 2022 or later) — the cleanup is at the bottom of the post:

-- One-time setup for the examples in this post
CREATE TABLE dbo.T1 (a INT, b INT);   -- the big preserved side: 10,000 rows
CREATE TABLE dbo.T2 (a INT, b INT);   -- the small lookup side:     100 rows
INSERT dbo.T1 SELECT value, value FROM GENERATE_SERIES(0, 9999);
INSERT dbo.T2 SELECT value, value FROM GENERATE_SERIES(0, 99);

28. Semi-join Transformation (December 4, 2006)

Setting: an EXISTS query where a big table (10,000 rows) is filtered against a small one (100 rows). The natural plan is a hash right semi-join — build on the small table, probe with the big one. Now the practical question: you want an index nested loops plan, so where does the index go? Intuition says on the small inner table. Craig shows that’s a dead end: 10,000 lookups against the small table still lose to the hash join. The winning move is the counter-intuitive one — index the big table.

The starting point, without any indexes — a hash right semi-join, build on the 100-row T2, probe with the 10,000-row T1:

SELECT * FROM dbo.T1
WHERE EXISTS (SELECT * FROM dbo.T2 WHERE T2.a = T1.a);
Execution plan of a Hash Match (Right Semi Join) with the 100-row table T2 as build input and the 10,000-row table T1 as probe

With that index in place, something surprising appears in the plan: the semi-join is gone, replaced by an inner join. That’s the semi-join transformation: a semi-join only needs each preserved row returned once, so the optimizer can deduplicate the lookup side (here a stream aggregate over the small table’s 100 values) and then run a plain inner join against the big table’s index — 100 index seeks instead of touching 10,000 rows. And because it’s now an ordinary inner join, the whole toolbox of join orders and algorithms opens up.

Here it is: after indexing the big table, the same EXISTS query compiles to a Distinct Sort over T2’s 100 values feeding a Nested Loops Inner Join that seeks into T1’s new index — 100 seeks instead of 10,000 probed rows, and no semi-join in sight:

CREATE CLUSTERED INDEX T1a ON dbo.T1 (a);

SELECT * FROM dbo.T1
WHERE EXISTS (SELECT * FROM dbo.T2 WHERE T2.a = T1.a);
Execution plan of the semi-join transformation: Table Scan of T2 into a Distinct Sort, then a Nested Loops (Inner Join) with a Clustered Index Seek on T1

The transformation pays off in two situations: when it unlocks an index seek on the preserved side, as above; and when the lookup side is huge but full of duplicates — Craig’s second example collapses a 10,000-row all-duplicates table into a one-row hash table before the join. Best of all, with a unique index on the lookup side the deduplication step is free and the optimizer applies the transformation without any extra operators at all. A nice reminder that the optimizer reasons about your uniqueness guarantees — one more reason to declare them.

Both situations, reproduced. First the duplicate collapse: drop the index again, and aim the EXISTS at a 10,000-row table containing a single repeated value — a Hash Match (Aggregate) crushes it to one row before an inner hash join:

DROP INDEX T1a ON dbo.T1;
CREATE TABLE dbo.T3 (a INT, b INT);
INSERT dbo.T3 SELECT 0, value FROM GENERATE_SERIES(0, 9999);

SELECT * FROM dbo.T1
WHERE EXISTS (SELECT * FROM dbo.T3 WHERE T3.a = T1.a);
Execution plan where a Hash Match (Aggregate) collapses the 10,000-row duplicate table T3 to one row before an inner hash join with T1

And the free variant: declare uniqueness on the lookup side and the dedup step vanishes — a plain Hash Match (Inner Join), no semi-join, no aggregate:

CREATE UNIQUE CLUSTERED INDEX T2a ON dbo.T2 (a);

SELECT * FROM dbo.T1
WHERE EXISTS (SELECT * FROM dbo.T2 WHERE T2.a = T1.a);
Execution plan of the EXISTS query with a unique index on T2: a plain Hash Match (Inner Join) without any deduplication operator

This closes out 2006 — six months, 28 articles, and a complete foundation: iterators, plans, access paths, joins, aggregation, subqueries, parallelism and partitioned tables. In the next part I move into 2007, where Craig switches gears to isolation levels and concurrency before returning to operators.

Done experimenting? This removes everything the setup created:

-- Cleanup
DROP TABLE IF EXISTS dbo.T1, dbo.T2, dbo.T3;