When will a FAST_FORWARD cursor have a work table (and is this something to avoid)?

Question

Background

I noticed whilst experimenting with running total queries that sometimes the estimated plan just shows a "Fetch Query"

and the actual plan shows repeated Fetches from the Clustered Index Scan

on other occasions (e.g when adding a TOP to the query) the estimated plan shows a "Population Query" stage that populates a work table

With the actual plan showing a clustered index scan to populate the work table then repeated seeks against that work table.

Question

1. What criteria does SQL Server use in choosing one approach over the other?
2. Would I be right in thinking that the first method (without the additional work table population step) is more efficient?

(Bonus question: If anyone could explain why each scan in the first query counts as 2 logical reads that might be quite enlightening too)

Additional Information

I have found this article here which explains that FAST_FORWARD cursors can either use a dynamic plan or a static plan. The first query in this case appears to be using a dynamic plan and the second one a static plan.

I've also found that if I try

SET @C2 = CURSOR DYNAMIC TYPE_WARNING FOR SELECT TOP ...

The cursor gets implicitly converted to a keyset cursor so it is clear that the TOP construct is not supported for dynamic cursors, perhaps for the reasons in Ruben's answer - Still looking for a definitive explanation of this.

However I have also read that dynamic cursors tend to be slower than their static counterparts (source 1, source 2) which seems surprising to me given that the static variety have to read the source data, copy it, then read the copy rather than just read the source data. The article I referenced earlier mentions that dynamic cursors use markers. Can anyone explain what these are? Is it just a RID or the CI key, or something different?

Script

SET STATISTICS IO OFF

CREATE TABLE #T ( ord INT IDENTITY PRIMARY KEY, total INT, Filler char(8000))

INSERT INTO #T (total) VALUES (37),(80),(55),(31),(53)

DECLARE @running_total INT, 
    @ord INT, 
    @total INT
    
SET @running_total = 0
SET STATISTICS IO ON
DECLARE @C1 AS CURSOR;
SET @C1 = CURSOR FAST_FORWARD FOR SELECT ord, total FROM #T ORDER BY ord;
OPEN @C1;
PRINT 'Initial FETCH C1'
FETCH NEXT FROM @C1 INTO @ord, @total ;
WHILE @@FETCH_STATUS = 0
BEGIN
  SET @running_total = @running_total + @total
  PRINT 'FETCH C1'
  FETCH NEXT FROM @C1 INTO @ord, @total ;
END

SET @running_total = 0
SET STATISTICS IO ON
DECLARE @C2 AS CURSOR;
SET @C2 = CURSOR FAST_FORWARD FOR SELECT TOP 5 ord, total FROM #T ORDER BY ord;
OPEN @C2;
PRINT 'Initial FETCH C2'
FETCH NEXT FROM @C2 INTO @ord, @total ;
WHILE @@FETCH_STATUS = 0
BEGIN
  SET @running_total = @running_total + @total
  PRINT 'FETCH C2'
  FETCH NEXT FROM @C2 INTO @ord, @total ;
END

PRINT 'End C2'
DROP TABLE #T 

Nielson

One explanation might be that the work table gives some consistency. The top 5 is retrieved in one transaction, it's like a snapshot. Without the worktable, you could get a top 5 containing rows that were never in the table together. – Desert

@Desert - Might be something like that. In this specific case I am using a local #temp table so SQL Server could (potentially) recognize that it will be consistent anyway as other transactions can't modify it. I also just tried SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED and still see the same results. (And SET ROWCOUNT 5 leaves both plans unchanged too) – Nielson

Answer 1

What criteria does SQL Server use in choosing one approach over the other?

It is primarily a cost-based decision. Quoting from the article you linked to, "In situations where the dynamic plan looks promising, the cost comparison may be heuristically skipped. This occurs mainly for extremely cheap queries, though the details are esoteric."

Would I be right in thinking that the first method (without the additional work table population step) is more efficient?

It depends. Dynamic and static cursor plans have different strengths and weaknesses. If all rows will eventually be touched, the static plan is likely to perform better. More on this in a moment.

It is clear that the TOP construct is not supported for dynamic cursors

This is true. All iterators in a dynamic cursor plan must be able to save and restore state, scan forward and backward, process one input row for each output row, and be non-blocking. Top, in general, does not satisfy all these requirements; the class CQScanTopNew does not implement the necessary Set/Get/Goto/Marker(), and ReverseDirection() methods (among others).

I have also read that dynamic cursors tend to be slower than their static counterparts.

This is often true, for Transact-SQL cursors, where most or all of the cursor set is touched. There is a cost associated with saving and restoring the state of a dynamic query plan. Where a single row is processed on each call, and all rows eventually touched, this save/restore overhead is maximized.

Static cursors have the overhead of making a copy of the set (which may be the dominant factor for a large set), but the per-row cost of retrieval is quite small. Keysets have a higher per-row retrieval overhead than static because they must outer join back to the source tables to retrieve non-key columns.

Dynamic cursors are optimal when a relatively small fraction of the set is accessed, and/or retrieval is not row-at-a-time. This is a typical access pattern in many common cursor scenarios, just not the ones blog posts tend to test :)

If anyone could explain why each scan in the first query counts as 2 logical reads that might be quite enlightening too

This is down to the way state is saved for the scan, and the way reads are counted.

The article I referenced earlier mentions that dynamic cursors use markers. Can anyone explain what these are? Is it just a RID or the CI key, or something different?

Markers exist for each iterator in a dynamic cursor plan, not just access methods. The 'marker' is all the state information necessary to restart the plan iterator at the point it left off. For an access method, an RID or index key (with uniquifier if necessary) is a big part of this, but not the whole story by any means.

However

Thanks. Information on the internals of cursors seems quite hard to come by! – Nielson

Answer 2

Just a hunch, but normally a TOP-ORDER BY requires SQL Server to buffer the result in some way (either the index scan's result or indeed the entire result in a temp structure, or anything in between).

One could argue that for cursors this is also necessary even when ordering by the primary key (as in your example), as you cannot allow a TOP 5 cursor to unexpectedly return less than 5 rows when the corresponding SELECT does return exactly 5 rows (or worse: the cursor returns more than 5 rows).

This weird situation could theoretically happen when there are deletes or inserts on the table after the index scan's range has already been determined for the cursor, and the inserts/deletes fall within the index scan's range, but you're not yet done fetching. To prevent this from happening, they might err on the safe side here. (And they just didn't optimize for #temp tables.)

A question though: does SQL Server allow a FETCH FROM SELECT TOP n without an ORDER BY clause? (Haven't got a SQL Server instance running here.) Might be interesting to know what plan that causes.

Buck

For a TOP ... ORDER BY that can be satisfied by following an index normally the result is not buffered in a spool or something. A TOP iterator is just added to the plan that counts the number of rows and stops requesting rows from the child iterators when the target is reached. For a general (non cursor) query unless at serializable or snapshot isolation level there are no attempts to mitigate against rows being inserted or deleted mid query and indeed it is possible to read the same row twice if it moves mid scan. Not sure why a cursor with TOP would need stricter semantics? – Nielson

The difference between a cursor and a normal query is that a normal query cannot execute additional DML statements while iterating. When you're using a cursor you can. These DML statements could affect the TOP...ORDER BY. – Buck

That's a good point (+1). It could be a kind of a Halloween Protection issue. – Nielson

Also, without an ORDER BY the main thing is updates (which can be locked until you've passed the physical row or page). This means that as long as you're streaming through the cursor, the table can get progressively unlocked. With an ORDER BY, this is not the case, and you might need a broad table or index lock until you've closed the cursor, otherwise you could get inconsistent results. When you're performing a TOP 5 on a 1000 row table, that's what you want, so the query optimizer may decide it's better to make a snapshot in advance, so it can lock only the selected rows. – Buck

Also, when there is no ORDER BY clause then there is an implicit ORDER BY. From my experience this seems to be the columns in the SELECT clause and also in their order, all ASCENDING; however there may be some logic to use Keys or indexed columns over non-indexed columns. I'm not 100% sure of the logic SQL Server uses there, but as I said my experience is that it is usually ordered the same as the columns are listed in the SELECT clause. – Friel

@Friel - There is definitely no implicit order by you can rely on. If you use DISTINCT you may see the behaviour you describe as an artefact of the sort operation but no guarantees as it may use a hash aggregate instead. For other queries you may well observe that the order is in index key order due to the access methods used but again you can't rely on this as paralellism, IAM ordered scans or merry-go-round scanning could all change this observed behaviour. If you need an ORDER BY you should specify it explicitly. – Nielson

@Buck - I'm not that convinced by this explanation now. I just tried SELECT ord, total FROM #T WHERE total = 37 ORDER BY ord and that doesn't populate a work table and indeed if inside the FETCH I do INSERT INTO #T (total) VALUES(37) I generate an infinite loop. So it seems there is no inherent objection to a query affecting its own results while iterating? – Nielson

@Martin - I just tested this and the difference appears to be that TOP is missing from your last query. Adding TOP causes the population again. Also note that using TOP 1 does not cause the populate. So I think that SQL Server is trying to prevent the possibility of the infinite loop you describe on TOP queries (which makes sense). – Buck

@Buck - Yes the TOP is missing. The point I was trying to make was that if a query with a WHERE can affect its own results then what is so semantically special about TOP? – Nielson

@Martin - I think a couple of things: a TOP query should never be able to get into an infinite loop, and the ordering should remain consistent (i.e., the results should remain ordered as you fetch). I'm not saying that a population is required for this to remain guaranteed, but that does seem to be the implementation SQL Server uses. – Buck

@Buck - Not convinced enough to mark this as the answer but as you might be right will give this the benefit of the doubt for bounty purposes! – Nielson

@Martin - As long as no-one from the SQL Server Team chimes in, it will remain speculative for sure. But thanks for the bounty. – Buck