Estimated row size in bytes is an important factor used by the SQL Server optimizer to estimate query cost, and I’ve found an anomaly in the estimated costing algorithm for the Sort operator, as well as in the actual cost of sorting long data.The estimated cost of a Sort seems to take a giant jump when the estimated row size exceeds 4000 bytes, but that jump in estimated cost doesn’t correspond to any jump in actual cost.

It’s important to note that the jump does not depend on the length of the sort key, but only on the length of the row data being carried along. The cost estimate for sorting a estimated-to-be-long row on a short key is much greater than for sorting an estimated-to-be-medium-length row on the same short key.  

Look at the estimated plan for this batch:

select top 5 replicate(LastName,50)
from AdventureWorks.Person.Contact order by reverse(EmailAddress)
select top 5 replicate(LastName,100)
from AdventureWorks.Person.Contact order by reverse(EmailAddress)

The same plan is used for each query:

Scan clustered index
Compute replicate() and reverse()
Sort/Top N on reverse() result
Return results

There is a huge difference in the estimated cost of the Sort operator:

First query Sort operator
Estimated cost: 1.320954
Estimated row size: 2563
Second query Sort operator
Estimated cost: 226.219608
Estimated row size: 4063

The jump from 1.3 to 226.2 occurs when the estimated row size exceeds 4000 bytes, and I still see the same jump when I change the 50 and 100 to 78 and 79.
If I time these queries (I put in the TOP specification only so the output to the client doesn’t dominate the timing), there is no sudden jump when the row gets to any particular size. However, in a more complex query, the goofy cost estimate for the long rows could really mess up the optimizer and cause real differences in run time by causing bad plans to be chosen.

I looked a little further to try to discover any anomalies in the actual cost of sorting based on key length, and I did find something interesting. Sorting data of type nvarchar(max) is much slower than sorting identical data of type nvarchar(not max), even if the data is the same size, but the optimizer does not seem to know this. In addition, the optimizer gives the same row size estimates for a replicate() result on nvarchar(max) regardless of the number of replications. This latter issue might make sense for (max) values in a table, where the row only contains a pointer and part of the data, but I don’t know if it makes sense here, where the (max) data is computed.

Consider this repro:

set statistics time on
dbcc dropcleanbuffers
dbcc freeproccache
go
select top 5 replicate(LastName,50)
from AdventureWorks.Person.Contact order by reverse(EmailAddress)
go
dbcc dropcleanbuffers
dbcc freeproccache
goselect top 5 replicate(LastName,150)
from AdventureWorks.Person.Contact order by reverse(EmailAddress)
go
dbcc dropcleanbuffers
dbcc freeproccache
go
select top 5 replicate(cast(LastName as nvarchar(max)),50)
from AdventureWorks.Person.Contact order by reverse(EmailAddress)
go
dbcc dropcleanbuffers
dbcc freeproccache
go
select top 5 replicate(cast(LastName as nvarchar(max)),150)
from AdventureWorks.Person.Contact order by reverse(EmailAddress)
go

The estimated row size is different for queries 1 and 2, and the 4000-byte row size threshold results in the same disparate cost estimates as before. However, the estimated row size for queries 3 and 4 are the same. Furthermore, sorting the data as nvarchar(max) takes much longer. The actual CPU times of the four queries are as follows:

47 ms
110 ms
1109 ms
2672 ms

So sorting identical data as nvarchar(max) instead of as nvarchar takes 20 times as long, but the optimizer does not know this. Why (to both parts)?

This isn’t something I’ve seen in production or mentioned in the newsgroups, but as the max and xml types gain more use, I won’t be surprised to see consequences both of the bad costing and the slow sorting of computed (max) data.