Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

For a moderately complex query I am trying to optimize, I noticed that removing the TOP n clause changes the execution plan. I would have guessed that when a query includes TOP n the database engine would run the query ignoring the the TOP clause, and then at the end just shrink that result set down to the n number of rows that was requested. The graphical execution plan seems to indicate this is the case -- TOP is the "last" step. But it appears there is more going on.

My question is, how (and why) does a TOP n clause impact the execution plan of a query?

Here is a simplified version of what is going on in my case:

The query is matching rows from two tables, A and B.

Without the TOP clause, the optimizer estimates there will be 19k rows from table A and 46k rows from table B. The actual number of rows returned is 16k for A and 13k for B. A hash match is used to join these two results sets for a total of 69 rows (then a sort is applied). This query happens very quickly.

When I add TOP 1001 the optimizer does not use a hash match; instead it first sorts the results from table A (same estimate/actual of 19k/16k) and does a nested loop against table B. The estimated number of rows for table B is now 1, and the strange thing is that the TOP n directly affects the estimated number of executions (index seek) against B -- it appears to always be 2n+1, or in my case 2003. This estimate changes accordingly if I change TOP n. Of course, since this is a nested join the actual number of executions is 16k (the number of rows from table A) and this slows down the query.

The actual scenario is a bit more complex but this captures the basic idea/behavior. Both tables are searched using index seeks. This is SQL Server 2008 R2 Enterprise edition.

share|improve this question
    
TOP will introduce a sort operation in most cases. Does your query have an ORDER BY? –  Aaron Bertrand Sep 24 '12 at 19:34
    
Sometimes using TOP (100) PERCENT results in a more optimal query on SQL Server. It shouldn't, but it does on occasion. –  Simon Hughes Sep 24 '12 at 22:53
    
@AaronBertrand Yes, the query has an ORDER BY clause. Adding TOP changes where in the plan this sort occurs, but I'm more concerned about how it affects the number of executions of index seeks against table B... (of course the two may be related -- I don't know) –  David Sep 25 '12 at 0:21
1  
@SimonHughes I'd be interested to see some examples of that. –  Aaron Bertrand Sep 25 '12 at 0:22
    
@David, I think it will much more useful for other people to help if you post the actual execution plans somewhere, instead of describing them in a word problem. :-) –  Aaron Bertrand Sep 25 '12 at 0:26
show 1 more comment

2 Answers 2

up vote 16 down vote accepted

I would have guessed that when a query includes TOP n the database engine would run the query ignoring the the TOP clause, and then at the end just shrink that result set down to the n number of rows that was requested. The graphical execution plan seems to indicate this is the case -- TOP is the "last" step. But it appears there is more going on.

The way the above is phrased makes me think you may have an incorrect mental picture of how a query executes. An operator in a query plan is not a step (where the full result set of a previous step is evaluated by the next one.

SQL Server uses a pipelined execution model, where each operator exposes methods like Init(), GetRow(), and Close(). As the GetRow() name suggests, an operator produces one row at a time on demand (as required by its parent operator). This is documented in the Books Online Logical and Physical Operators reference, with more detail in my blog post Why Query Plans Run Backwards. This row-at-a-time model is essential in forming a sound intuition for query execution.

My question is, how (and why) does a TOP n clause impact the execution plan of a query?

Some logical operations like TOP, semi joins and the FAST n query hint affect the way the query optimizer costs execution plan alternatives. The basic idea is that one possible plan shape might return the first n rows more quickly than a different plan that was optimized to return all rows.

For example, indexed nested loops join is often the fastest way to return a small number of rows, though hash or merge join with scans might be more efficient on larger sets. The way the query optimizer reasons about these choices is by setting a Row Goal at a particular point in the logical tree of operations.

A row goal modifies the way query plan alternatives are costed. The essence of it is that the optimizer starts by costing each operator as if the full result set were required, sets a row goal at the appropriate point, and then works back down the plan tree estimating the number of rows it expects to need to examine to meet the row goal.

For example, a logical TOP(10) sets a row goal of 10 at a particular point in the logical query tree. The costs of operators leading up to the row goal are modified to estimate how many rows they need to produce to meet the row goal. This calculation can become complex, so it is easier to understand all this with a fully worked example and annotated execution plans. Row goals can affect more than the choice of join type or whether seeks and lookups are preferred to scans. More details on that here.

As always, an execution plan selected on the basis of a row goal is subject to the optimizer's reasoning abilities and the quality of information provided to it. Not every plan with a row goal will produce the required number of rows faster in practice, but according to the costing model it will.

Where a row goal plan proves not to be faster, there are usually ways to modify the query or provide better information to the optimizer such that the naturally selected plan is best. Which option is appropriate in your case depends on the details of course. The row goal feature is generally very effective (though there is a bug to watch out for when used in parallel execution plans).

Your particular query and plan may not be suitable for detailed analysis here (by all means provide an actual execution plan if you wish) but hopefully the ideas outlined here will allow you to make forward progress.

share|improve this answer
2  
Definitely take note of the fact that plans run from the left, calling the operator to the right as many times as required to satisfy the row goal required. The plan sucks rows through the pipeline, rather than pushing stuff from operator to the next. –  Rob Farley Sep 25 '12 at 7:43
    
+1. As always, great information. –  Thomas Stringer Sep 25 '12 at 12:18
1  
Thanks for the thorough answer (and related blog post). You say that when the row goal plan is slower there are ways to remedy this by modifying the query -- are there a general set of guidelines I can reference for this particular problem? –  David Sep 25 '12 at 15:15
    
@David It helps if the schema is relational (think 3NF) well-indexed, with accurate statistics (including multi-column or computed column ones where necessary), and the query itself is not over-complex and uses mostly relational operations. Potential remedies include trying different syntax, simplifying the query into multiple steps (using temporary tables), and - where all else fails - using optimizer hints. Sorry for the long answer, that is a Big Question :) –  Paul White Sep 25 '12 at 15:50
add comment

When you use TOP, the Optimizer sees an opportunity to do less work. If you ask for 10 rows, then there's a good chance it doesn't need to consume the whole set. So the TOP operator can be pushed much further to the right. It will keep requesting rows from the next operator (on its right), until it has received enough.

You point out that without TOP, the query sorts the data at the very end. If the engine could know how many rows were going to be satisfied by the join in advance, it may well choose to use a similar plan, positioning the TOP on the left. But with the effort to do a Hash Match being relatively high, and presumably no option for a Merge Join, the Optimizer might prefer to filter the TOP further to the right.

When table B is queried, it's fetching a single row at a time. That's why the estimate is 1. It also assumes that it'll only find that row 50% of the time. So it guesses it'll need 2n+1 seeks to find it.

share|improve this answer
    
That doesn't seem right that the estimated number of rows would change based on the way the data is being fetched. How it gets the data shouldn't affect the cardinality. A change in the way it fetches would instead be reflected in the number of executions, correct? –  David Sep 25 '12 at 2:01
    
The "Estimated number of rows" is per execution. In a Nested Loop, it's quite likely to execute more than once. –  Rob Farley Sep 25 '12 at 4:06
    
This would be different behavior than the Actual Number of Rows and (actual) number of executions then. If the actual plan shows 16,834 actual executions and 15,407 actual rows returned, I take this to mean it did 16k seeks but only found 15k matching the predicate. If it meant 15k rows per execution this would be 15k * 16k = 240 million rows -- about 10 times bigger than the table... –  David Sep 25 '12 at 5:14
    
Also, I am not sure I follow the last statement of your answer. When you say 2n+1 seeks to find "it", what do you mean by "it"? Surely not a single row? Do you mean that the optimizer assumes that for any given row in A there is a 50% chance it will be matched to B and therefore it will need to "try" 2003 rows from A in order to get 1001 matches from B? Is this behavior documented anywhere by Microsoft? And what does it have to do with the TOP clause? Thanks for your answer(s)/patience. –  David Sep 25 '12 at 5:23
    
Yes, Estimated Rows is per execution. Actual rows are total. Although, there is no problem having an operator returning more rows than are in the table, as it's very easy to demonstrate operators returning the same row multiple times. –  Rob Farley Sep 25 '12 at 7:09
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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