3

I'm learning about execution plans, and have a question regarding the relationship between a Table Spool and correlated subquery (I'm following this tutorial, don't mind the typos).

I've created the following table:

CREATE TABLE student (
  ID INT IDENTITY(1, 1),
  CX_Name VARCHAR(50),
  CX_PhoneNum VARCHAR(50),
  CX_Address VARCHAR(MAX),
  CX_Credit INT
)

Then inserted values:

INSERT INTO student
VALUES (
  'Alen',
  '9625788954',
  'London',
  500
) 
GO 100
 
INSERT INTO student
VALUES (
  'Frank',
  '962445785',
  'Germany',
  1400
)
GO 100

Then executed the following query, which includes a correlated subquery:

SELECT ID, CX_Name, CX_Credit
FROM student CX1 
WHERE CX_Credit >= (
    SELECT AVG(CX_Credit)
    FROM student CX2
    WHERE CX1.ID = CX2.ID
)

The execution plan is:

enter image description here

The tutorial explains (bold is mine):

SQL Server Engine reads the data from the table first, sort the data before dividing it into segments, then create a temp table to store the data groups.

On the other part of the explain plan, the SQL Server Engine reads from the Table Spool, then calculate the average credit value for each group using the Stream Aggregate operator.

The last Table Spool operator will read the grouped data and join it to retrieve the values higher than the average value.

The three Table Spool operators will use the same temp table created at the first time.

I don't understand the bolded sentence, in two ways:

  1. The correlated subquery has to be re-executed for each student record. Then what does grouping has to do here?
  2. In what way does a group is "stored" inside the table spool?

1 Answer 1

2

How the execution plan works

The Segment Spool stores the rows for one group at a time. The subtree is executed once per group. At the end of processing for each group, the spool is truncated, and processing repeats for the next group of rows.

I wrote about the full details in Partitioning and the Common Subexpression Spool.

The Segment Spool iterator always appears as the immediate parent of a Segment iterator. The two leaf-level Table Spool iterators shown in the plan are secondary spools, which only replay rows saved by the primary spool.

The Segment Spool lazily writes rows into its worktable, until the start of a new group is signalled. Once the Segment Spool has a complete group in its worktable, one row (not the whole group) is returned to its parent (the top-level Nested Loops operator in this example).

The data values stored in this one row are not important; they do not contribute to the final result. The point is that this single row is received on the outer input of the parent Nested Loops iterator. This causes the iterator to execute its inner input once per group.

Your example

In your example, the grouping is implied by the correlation on ID:

WHERE CX1.ID = CX2.ID

Where CX1.ID is an outer reference.

Given the original query (missing CX2 alias added inside the AVG):

SELECT ID, CX_Name, CX_Credit
FROM student CX1 
WHERE CX_Credit >= (
    SELECT AVG(CX2.CX_Credit)
    FROM student CX2
    WHERE CX1.ID = CX2.ID
)

Yes, in principle each row from CX1 results in an average being computed over all rows from CX2 where the ID matches the current ID value in the outer row. It is in that sense that groups are formed.

In general, executing the query literally in that way would be quite inefficient, and result in the same average being computed multiple times. That's why we have an optimizer; to find an equivalent physical plan that produces the same logical results, just more efficiently. In this case, that would mean computing the group average once and cross joining it to the rows in the current group by replaying the spool.

More to the point, the spool here solves the problem of computing an aggregate over rows we haven't seen in the stream yet. Consider that the final plan only accesses the base table once, despite there being two references to it in the original query. It can be more efficient to save the rows in a group once and replay them, rather than access the base table once per outer row.

For example, say we prevent the optimizer from turning the query specification into a "group-by apply":

SELECT ID, CX_Name, CX_Credit
FROM student CX1 
WHERE CX_Credit >= (
    SELECT AVG(CX2.CX_Credit)
    FROM student CX2
    WHERE CX1.ID = CX2.ID
)
OPTION (QUERYRULEOFF GenGbApplySimple);

The execution plan now has two table accesses:

Without group-by apply

If we go even further in restricting the optimization tricks available, we get closer to the literal interpretation of the original:

SELECT ID, CX_Name, CX_Credit
FROM student CX1 
WHERE CX_Credit >= (
    SELECT AVG(CX2.CX_Credit)
    FROM student CX2
    WHERE CX1.ID = CX2.ID
)
OPTION 
(
    QUERYRULEOFF GenGbApplySimple, 
    LOOP JOIN, 
    FORCE ORDER, 
    NO_PERFORMANCE_SPOOL
);

Pretty literal


An equivalent query specification you might find more intuitive is:

SELECT
    S1.ID,
    S1.CX_Name,
    S1.CX_Credit
FROM 
(
    SELECT 
        S.*, 
        avg_credit = AVG(S.CX_Credit) OVER (
            PARTITION BY S.ID)
    FROM dbo.student AS S
) AS S1
WHERE
    S1.CX_Credit >= S1.avg_credit;

The example given isn't very useful because ID is effectively unique. The optimizer cannot guarantee that without some sort of constraint, so it adds a spool defensively. If we ensure ID is unique:

CREATE UNIQUE INDEX i ON dbo.student (ID);

The original query produces a join plan with no aggregation (since an aggregate on a maximum of one row is redundant):

join

Try the examples in my blog posts below instead. You can use https://dbfiddle.uk/ which has the option to start with a fresh copy of the AdventureWorks database each time.

Further reading

Other related posts of mine:

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.