--fast 1. select top 100 * from test where c1 < 30000 order by c2
--slow 2. select top 101 * from test where c1 < 30000 order by c2
1. is more than two times faster than 2.
Why?
What a coinccident! I am on the same issue just at the time. I was considering implementing an algorithm like this: First populate the N rows to a table variable (with index on the sort column), then iterate through all left rows, adding one row to the table variable if bigger than min of the table, else discard it. This could be either done in sql or clr aggregate function. Then I thought maybe MS had already done it in the Top N stuff, so started to run a test against it.
CREATE TABLE [dbo].[NUM] ([n] int NOT NULL, s varchar(128) NULL, PRIMARY KEY CLUSTERED([n] ASC)) go -- populate data set nocount on declare @n int, @i int set @n=1000000 set @i = 0 while @n>0 begin if @i = 0 begin tran insert into dbo.NUM select @n, convert(varchar,@n + @i * 2) set @n=@n-1 set @i = (@i + 1) % 1000 if @i = 0 commit end GO -- test 1 select top ( XX ) cast(s as int), n from dbo.num order by cast(s as int) desc go -- test 2 set rowcount XX select cast(s as int), n from dbo.num order by cast(s as int) desc for test 1, duration < 1s, for any XX <= 100, and the duration is about 12s for any XX >100
for test 2, the duration is fixed at 4s for XX: 10 - 100,000.
The show-plan shows test 1 uses Top N sort op, while the test 2 uses Sort op. Ok I dont care about the sort op. The only thing I care is if MS has correctly implemented the Ton N Sort. MSDN stated about "Top N sort": "Top N Sort is similar to the Sort iterator, except that only the first N rows are needed, and not the entire result set. For small values of N, the SQL Server query execution engine attempts to perform the entire sort Operation in memory. For large values of N, the query execution engine resorts to the more generic method of sorting to which N is not a parameter."
As you can see, this statement sound like the algorithm I was intending to write myself. But the later part mentioned a "more generic method of sorting to which N is not a parameter", that exlains why no matter how XX changes for test1 after going beyong 100, the duration is always the same. Test 2 is also insensitive to N. So MS seems used 3 algorithm, in which two of them are used for "top N", one is for "set rowcount".
I do not think whether to perform it in memory or not will cause such a big difference. It's mainly due to that only one (the fastest one) uses the algorithm of just keeping the top N rows and then evict low ranking items when they fall below the N window.
I am using a sql 2005.
I also tested the "select top (@n)" variation. The result shows that "select top (@n)" is similar to "set rowcount...". The reason I tested the "select top (@n)" variation is that I was wondering if We could use plan-force to force it use the faster "Top N Sort". However it seems that "select top (@n)" is quite different from "select top (xx)" where xx is a constant, but similar to "set rowcount; ...". Guess it will not work, so I will not try to test if plan-force can do the job.
Just curious why MS choose not to use the "Top N Sort" algorithm always, instead to choose this so complex arrangement (i.e. some with "Top N Sort", some with the "Sort then Top"). I think, "Top N Sort" should always be used
