Part 5 of my series on Craig Freedman’s SQL Server query-processing blog (part 4, September 2006, is here). October 2006 wraps up the subquery story with decorrelation, answers a reader question about OR-predicates and indexes, and kicks off the parallelism chapter. Summaries in my own words; all of it still applies today.
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. Fair warning about the last table: it’s 1,000,000 rows (~250 MB) and only needed for the parallelism figure at the end, so feel free to skip it:
-- One-time setup for the examples in this post
CREATE TABLE dbo.T1 (a INT, b INT);
CREATE TABLE dbo.T2 (a INT, b INT, c INT);
CREATE TABLE dbo.U (a INT, b INT, c INT, x CHAR(200));
CREATE UNIQUE CLUSTERED INDEX Ua ON dbo.U (a);
CREATE INDEX Ub ON dbo.U (b);
CREATE INDEX Uc ON dbo.U (c);
INSERT dbo.U SELECT value, value, value, value FROM GENERATE_SERIES(0, 999);
-- Optional, only for the parallelism figure: 1,000,000 rows, ~250 MB
CREATE TABLE dbo.P (a INT, x CHAR(200));
INSERT dbo.P SELECT value, value FROM GENERATE_SERIES(0, 999999);
20. Decorrelating Subqueries (October 4, 2006)
Decorrelation is the optimizer rewriting a correlated subquery into a plain join, so the two tables can be scanned independently and any join algorithm and order becomes available. It isn’t always possible — the previous month’s Assert example is one blocker — and Craig shows how razor-thin the line is: a correlated MAX subquery with WHERE T2.b < T1.b cannot be decorrelated, but change the < to = and suddenly the whole subquery can be pre-computed as a GROUP BY over the join key and joined to the outer table.
The real lesson is that the optimizer picks where the aggregate goes based on the data: pre-aggregate below the join when there are few groups and many outer rows, pull the aggregation above the join (grouping on the outer table’s unique key) when the outer table is small, and switch the whole thing to hash aggregate plus hash join when both sides get big. Same query, three fundamentally different plans — decorrelation is what makes that menu possible.
Here are two of those shapes on the same query. First, load 10,000 rows into T2 while T1 stays empty: with a tiny outer table the aggregation is pulled above the join — Nested Loops first, then Stream Aggregate, then the Filter applying the > comparison:
INSERT dbo.T2 SELECT value, value, value FROM GENERATE_SERIES(0, 9999);
SELECT * FROM dbo.T1
WHERE T1.a > (SELECT MAX(T2.a) FROM dbo.T2 WHERE T2.b = T1.b);
Now fill T1 with 10,000 rows too, and the same query switches to the third shape: a Hash Match (Aggregate) pre-computes the MAX per T2.b group below the join, and a Hash Join matches the two big inputs:
INSERT dbo.T1 SELECT value, value FROM GENERATE_SERIES(0, 9999);
SELECT * FROM dbo.T1
WHERE T1.a > (SELECT MAX(T2.a) FROM dbo.T2 WHERE T2.b = T1.b);
21. Introduction to Parallel Query Execution (October 11, 2006)
The parallelism series starts with the model. SQL Server parallelizes a query by horizontally partitioning the data: split the input into roughly equal streams, give each thread its own copy of the same operator, and let them run independently — for a hash aggregate, for example, a hash function on the grouping columns decides which thread owns which groups, so no coordination between threads is needed. This is why parallelism scales nearly linearly, and why it’s not “pipeline parallelism”: the degree of parallelism isn’t limited by the number of operators in the plan.
Craig is also clear about the costs: parallelism adds overhead, so it’s for big queries on servers with few concurrent queries — an OLTP box with many concurrent sessions keeps its CPUs busy without it. The optimizer decides cost-based whether to produce a parallel plan, but the DOP is chosen at execution time, not stored in the cached plan — from the CPU count, the “max degree of parallelism” setting and the MAXDOP hint. And a detail that still surprises people in sys.dm_os_tasks today: a parallel query can use more threads than its DOP, because DOP counts threads per operator branch, not per plan.
22. Index Union (October 18, 2006)
A reader question interrupts the parallelism series, and the answer is a classic. An OR across two different columns (WHERE b = 1 OR c < 3) can’t be answered by a seek on either single index — each index would miss rows that only satisfy the other predicate. Faced with that, the optimizer often just scans. But with enough data it produces an index union: seek both non-clustered indexes, concatenate the results, and remove duplicates — effectively rewriting the OR as a UNION of two single-predicate queries.
With an inequality in the mix, that looks like this — a seek on each index, a Concatenation, and a Sort (Distinct Sort) to remove the duplicates:
SELECT a FROM dbo.U WHERE b = 1 OR c < 3;
The refinement is in the dedup step. With inequality predicates the results need a Sort Distinct, which costs memory. But when both predicates are equalities, each index seek returns rows ordered by the clustering key (the equality freezes the leading column), so the plan can use a merge union — Merge Join (Concatenation) — plus a memory-free stream aggregate for the duplicates. Two caveats to remember: the union only carries the columns all indexes have in common (usually just the clustering key), so asking for more columns brings a bookmark lookup back; and cascaded merge unions handle three or more OR’d predicates.
Make both predicates equalities and the Sort is gone — Merge Join (Concatenation) plus a Stream Aggregate do the deduplication without a memory grant:
SELECT a FROM dbo.U WHERE b = 1 OR c = 3;
And the first caveat made visible: ask for b and c as well, and the union (which only carries the shared clustering key a) has to bolt a Key Lookup onto the result to fetch them:
SELECT a, b, c FROM dbo.U WHERE b = 1 OR c = 3;
23. The Parallelism Operator, aka Exchange (October 25, 2006)
The operator that makes parallelism happen. An exchange is secretly two iterators: a producer at the top of one branch that packs rows into packets and pushes them out, and a consumer at the bottom of the next branch that unpacks them — the only push-based data flow in an otherwise pull-based execution model, which is exactly what lets the threads on both sides run independently.
Craig then gives the taxonomy that still decodes every parallel plan: Gather Streams (DOP producers, one consumer — the top of every parallel plan, since results must return to the single connection thread), Repartition Streams (DOP to DOP), and Distribute Streams (one to DOP). Rows are routed by partitioning type — broadcast, round robin, hash, range, or demand — and an exchange can be merging (order-preserving) or not. Once you can read these three exchange types and their properties, parallel plans stop looking mysterious.
The simplest of the three, produced by a selective query on the 1,000,000-row table from the setup: a parallel Table Scan (note the yellow parallelism arrows on the operator icons) topped by a Parallelism (Gather Streams) exchange that funnels the streams back to the single connection thread:
SELECT * FROM dbo.P WHERE a < 1000;
Done experimenting? This removes everything the setup created:
-- Cleanup
DROP TABLE IF EXISTS dbo.T1, dbo.T2, dbo.U, dbo.P;