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.

Given a simple three table join, query performance changes drastically when ORDER BY is included even with no rows returned. Actual problem scenario take 30 seconds to return zero rows but is instant when ORDER BY not included. Why?

SELECT * 
FROM tinytable t                          /* one narrow row */
JOIN smalltable s on t.id=s.tinyId        /* one narrow row */
JOIN bigtable b on b.smallGuidId=s.GuidId /* a million narrow rows */
WHERE t.foreignId=3                       /* doesn't match */
ORDER BY b.CreatedUtc          /* try with and without this ORDER BY */

I understand that I could have an index on bigtable.smallGuidId, but, I believe that would actually make it worse in this case.

Here's script to create/populate the tables for test. Curiously, it seems to matter that smalltable has an nvarchar(max) field. It also seems to matter that I'm joining on the bigtable with a guid (which I guess makes it want to use hash matching).

CREATE TABLE tinytable
  (
     id        INT PRIMARY KEY IDENTITY(1, 1),
     foreignId INT NOT NULL
  )

CREATE TABLE smalltable
  (
     id     INT PRIMARY KEY IDENTITY(1, 1),
     GuidId UNIQUEIDENTIFIER NOT NULL DEFAULT NEWID(),
     tinyId INT NOT NULL,
     Magic  NVARCHAR(max) NOT NULL DEFAULT ''
  )

CREATE TABLE bigtable
  (
     id          INT PRIMARY KEY IDENTITY(1, 1),
     CreatedUtc  DATETIME NOT NULL DEFAULT GETUTCDATE(),
     smallGuidId UNIQUEIDENTIFIER NOT NULL
  )

INSERT tinytable
       (foreignId)
VALUES(7)

INSERT smalltable
       (tinyId)
VALUES(1)

-- make a million rows 
DECLARE @i INT;

SET @i=20;

INSERT bigtable
       (smallGuidId)
SELECT GuidId
FROM   smalltable;

WHILE @i > 0
  BEGIN
      INSERT bigtable
             (smallGuidId)
      SELECT smallGuidId
      FROM   bigtable;

      SET @i=@i - 1;
  END 

I've tested on SQL 2005, 2008 and 2008R2 with same results.

share|improve this question

migrated from stackoverflow.com Jan 5 '12 at 17:54

This question came from our site for professional and enthusiast programmers.

5 Answers 5

up vote 17 down vote accepted

I agree with Martin Smith's answer, but the problem is not simply one of statistics, exactly. The statistics for the foreignId column (assuming automatic statistics are enabled) accurately show that no rows exist for a value of 3 (there's just one, with a value of 7):

DBCC SHOW_STATISTICS (tinytable, foreignId) WITH HISTOGRAM

statistics output

SQL Server knows that things might have changed since the statistics were captured, so there might be a row for value 3 when the plan is executed. In addition, any amount of time might elapse between plan compilation and execution (plans are cached for reuse, after all). As Martin says, SQL Server contains logic to detect when sufficient modifications have been made to justify recompiling any cached plan for optimality reasons.

None of this ultimately matters, however. With one edge-case exception, the optimizer will never estimate the number of rows produced by a table operation to be zero. If it can statically determine that the output must always be zero rows, the operation is redundant and will be removed completely.

The optimizer's model instead estimates a minimum of one row. Employing this heuristic tends to produce better plans on average than would be the case if a lower estimate was possible. A plan that produces a zero-row estimate at some stage would be useless from that point on in the processing stream, since there would be no basis to make cost-based decisions (zero rows is zero rows no matter what). If the estimate turns out to be wrong, the plan shape above the zero row estimate stands almost no chance of being reasonable.

The second factor is another modelling assumption called the Containment Assumption. This essentially says that if a query joins a range of values with another range of values, it is because the ranges overlap. Another way to put this is to say that the join is being specified because rows are expected to be returned. Without this reasoning, costs would be generally underestimated, resulting in poor plans for a broad range of common queries.

Essentially, what you have here is a query that doesn't fit the optimizer's model. There's nothing we can do to 'improve' estimates with multi-column or filtered indexes; there's no way to get an estimate lower than 1 row here. A real database might have foreign keys to ensure that this situation could not arise, but assuming that is not applicable here, we are left with using hints to correct the out-of-model condition. Any number of different hint approaches will work with this query. OPTION (FORCE ORDER) is one that happens to work well with the query as written.

share|improve this answer
1  
+1 Hadn't realised that. Guess it's quite a rare case when it makes such a difference. –  Martin Smith Jan 5 '12 at 17:52

You should add an index for your order by field(s) and you will see that speed will increase. See SQL Server 2008: Ordering by datetime is too slow

Try it, i don't think that your guess, that it will only make things slower, is right.

share|improve this answer

Turn on your Show Execution Plan button and you can see what's happening. Here's the plan for the "slow" query: enter image description here

And here's the "fast" query: enter image description here

Look at that - run together, the first query is ~33x more "expensive" (97:3 ratio). SQL is optimizing the first query to order the BigTable by datetime, then running a small "seek" loop over SmallTable & TinyTable, executing them 1 million times each (you can hover over the "Clustered Index Seek" icon to get more stats). So, the sort (27%), and 2 x 1 million "seeks" on small tables (23% and 46%) are the massive bulk of the expensive query. In comparison, the non-ORDER BY query performs a grand total of 3 scans.

Basically, you've found a hole in the SQL optimizer logic for your particular scenario. But as stated by TysHTTP, if you add an index (which slows down your insert/updates some), your scanning becomes crazy fast.

share|improve this answer

What's happening is SQL is deciding to run the order by before the restriction.

Try this:

SELECT *
(
SELECT * 
FROM tinytable t
    INNER JOIN smalltable s on t.id=s.tinyId
    INNER JOIN bigtable b on b.smallGuidId=s.GuidId
WHERE t.foreignId=3
) X
ORDER BY b.CreatedUtc

This gives you the improved performance (in this case where the returned result count is very small), without actually having the performance hit from adding another index. While it is odd when the SQL optimizer decides to perform the order by before join, it's likely because if you actually had return data then sorting it after the joins would take longer than sorting without.

Lastly, try running the following script and then see if the updated statistics and indexes fix the problem you're having:

EXEC [sp_MSforeachtable] @command1="RAISERROR('UPDATE STATISTICS(''?'') ...',10,1) WITH NOWAIT UPDATE STATISTICS ? "

EXEC [sp_MSforeachtable] @command1="RAISERROR('DBCC DBREINDEX(''?'') ...',10,1) WITH NOWAIT DBCC DBREINDEX('?')"

EXEC [sp_MSforeachtable] @command1="RAISERROR('UPDATE STATISTICS(''?'') ...',10,1) WITH NOWAIT UPDATE STATISTICS ? "
share|improve this answer

The basic problem here is one of statistics.

For both queries the estimated row count shows that it believes the final SELECT will return 1,048,580 rows (the same number of rows estimated to exist in bigtable) rather than the 0 that actually ensue.

Both your JOIN conditions do match and would preserve all rows. They end up getting eliminated because the single row in tinytable does not match the t.foreignId=3 predicate.

If you run

SELECT * 
FROM tinytable t  
WHERE t.foreignId=3  AND id=1 

and look at the estimated number of rows it is 1 rather than 0 and this error propagates throughout the plan. tinytable currently contains 1 row. The statistics would not get recompiled for this table until 500 row modifications have occurred so a matching row could be added and it wouldn't trigger a recompile.

The reason why the Join Order changes when you add the ORDER BY clause and there is a varchar(max) column in smalltable is because it estimates that varchar(max) columns will increase the rowsize by 4,000 bytes on average. Multiply that out by 1048580 rows and it means that the sort operation would need an estimated 4GB so it sensibly decides to do the SORT operation before the JOIN.

You can force the ORDER BY query to adopt the non ORDER BY join strategy with the use of hints as below.

SELECT *
FROM   tinytable t /* one narrow row */
       INNER MERGE JOIN smalltable s /* one narrow row */
                        INNER LOOP JOIN bigtable b
                          ON b.smallGuidId = s.GuidId /* a million narrow rows */
         ON t.id = s.tinyId
WHERE  t.foreignId = 3 /* doesn't match */
ORDER  BY b.CreatedUtc
OPTION (MAXDOP 1) 

The plan shows a sort operator with an estimated sub tree cost of nearly 12,000 and erroneous estimated row counts and estimated data size.

Plan

BTW I didn't find replacing the UNIQUEIDENTIFIER columns with integer ones altered things in my test.

share|improve this answer

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.