none
Execution plan changes according to the position of NOT EXISTS clause RRS feed

  • Question

  • Hello All,

    SQL 2005 64bit enterprise 9.00.4035.00

    I saw a strange behavior in SQL Server execution plan. It changes depends on where you have the NOT EXISTS clause.

    Below query ,highlighted part if you move from top to bottom, the entire plan change.

    When the highlighted part is in top, exec plan first join Employee table with EmergencyPool,  and later join  EmployeeAttributeValue and other tables. If we put it in bottom, plan just join EmployeeAttributeValue with Employee table and later join EmergencyPool and other tables.

    This make a big difference in query execution. 2 sec v/s 400 sec. I am not wondering why is this happening?

     

    <!-- [if gte mso 10]> <mce:style>

    SELECT TOP 1000 Employee. EmployeeID FROM Employee ( NOLOCK )

                WHERE   ( Employee. EmployeeStatusID= 2006362) AND

                            ( Employee. EmailStatusTypeID= 1) AND

                            ( Employee. IsTestID= 0)   AND

                            (( Employee. IsPayRoll= 1)) AND

                            ( Employee. DeptID IN ( 53))  

                            AND NOT EXISTS ( SELECT TOP 1 1 FROM EmergencyPool EmergencyPool ( NOLOCK ) WHERE Employee. EmployeeID = EmergencyPool. EmployeeID)  

                            AND (( Employee. LastResponseDate IS NULL AND Employee. CREATEDATE >= '10/9/2009 12:32:47 PM' ) OR Employee. LastResponseDate >= '4/9/2009 12:32:47 PM' )

                            AND ((( DATEPART ( yyyy, GETUTCDATE ()) - DATEPART ( YEAR , Employee. BirthDate) BETWEEN 40 AND 44)

                                              OR ( DATEPART ( yyyy, GETUTCDATE ()) - DATEPART ( YEAR , Employee. BirthDate) BETWEEN 35 AND 39) )

                            AND   EXISTS( SELECT TOP 1 1 FROM EmployeeAttributeValue pav ( NOLOCK ) WHERE Employee. EmployeeID = pav. EmployeeID

                                              AND pav. AttributeKeyID = 1001184 AND pav. AttributeValueID IN ( 2003118, 2003116))

                            AND ( Employee. GenderID IN ( 2000246))

                            AND ( Employee. CountryID IN ( 2000200)))

                            AND NOT EXISTS ( SELECT TOP 1 1 FROM TrackingEmployee stp ( NOLOCK ) WHERE stp. EmployeeID= Employee. EmployeeID

                                              AND ( stp. ResponseID= 61830  AND stp. WaveID= 81673))

                            AND NOT EXISTS ( SELECT TOP 1 1 FROM InvitesLQ ( NOLOCK )    WHERE InvitesLQ. EmployeeID= Employee. EmployeeID

                                        AND ( InvitesLQ. ResponseID= 61830     AND InvitesLQ. WaveID= 81673))  

                            AND NOT EXISTS ( SELECT TOP 1 1 FROM EmergencyPool EmergencyPool ( NOLOCK ) WHERE Employee. EmployeeID = EmergencyPool. EmployeeID)  

     

     

     

     

    Monday, April 19, 2010 8:51 PM

Answers

  • Adam (and everyone else still reading this thread):

    I came up with a really good example that demonstrates this difference in query execution... just from the order of the NOT EXISTS predicates.  This is what I'll be putting into a blog post.

    First, create a Customer table, a CustHugeRowSize (child) table, and a CustTeenyRowSize (child) table:

    if object_id('TempDB..#Customers','U') is not null drop table #Customers
    go
    create table #Customers 
    (
      CustomerID int primary key
     ,Name varchar(30)
    )
    go
     
    if object_id('TempDB..#CustHugeRowSize','U') is not null drop table #CustHugeRowSize
    go
    create table #CustHugeRowSize
    (
      CustomerID int
     ,SeqID int identity(1,1)
     ,Filler char(3500) default replicate('*',3500)
    )
    go
    create unique clustered index PK_CustHuge on #CustHugeRowSize(CustomerID,SeqID)
    go
     
    if object_id('TempDB..#CustTeenyRowSize','U') is not null drop table #CustTeenyRowSize
    go
    create table #CustTeenyRowSize
    (
      CustomerID int
     ,SeqID int identity(1,1)
     ,Junk bit default 0
    )
    go
    create unique clustered index PK_CustTeeny on #CustTeenyRowSize(CustomerID,SeqID)
    go
    

     

    Next, populate the Customer table with 100,000 rows, and populate the two child tables with 3 entries for each customer... except for CustomerID 98765:

    with 
     L0(c) as (select 0 union all select 0 union all select 0)    --3 Rows
     ,L1(c) as (select 0 from L0 a cross join L0 b cross join L0 c)  --27 Rows (3x3x3)
     ,L2(c) as (select 0 from L1 a cross join L1 b cross join L1 c)  --19683 Rows (27x27x27)
     ,L3(c) as (select 0 from L2 a cross join L2 b)          --387,420,489 Rows (19683x19683)
     ,NN(n) as (select row_number() over (order by (select 0)) from L3)
    insert #Customers (CustomerID,Name)
    select n,'Customer Number '+ltrim(str(n))
    from NN
    where n<=100000
     
    insert #CustHugeRowSize (CustomerID)
    select CustomerID
    from #Customers
    cross join (select 1 union all select 2 union all select 3) X(N)
    where CustomerID<>98765
    
    insert #CustTeenyRowSize (CustomerID)
    select CustomerID
    from #Customers
    cross join (select 1 union all select 2 union all select 3) X(N)
    where CustomerID<>98765
    

     

    Make sure statistics are completely up-to-date in the child tables:

    update statistics #CustHugeRowSize(PK_CustHuge) with fullscan
    update statistics #CustTeenyRowSize(PK_CustTeeny) with fullscan
    

     

    And now we have the two queries.  The only difference between them is the order of the NOT EXISTS predicates:

    select *
    from #Customers c
    where not exists (select * from #CustHugeRowSize where CustomerID=c.CustomerID)
     and not exists (select * from #CustTeenyRowSize where CustomerID=c.CustomerID)
    
    select *
    from #Customers c
    where not exists (select * from #CustTeenyRowSize where CustomerID=c.CustomerID)
     and not exists (select * from #CustHugeRowSize where CustomerID=c.CustomerID)
    

     

    The estimated query plan shows a relative cost of  98% : 2%  for the two queries.

    And, sure enough, if you run a trace on them, here are the results:

    Query#1:  CPU=1265,  Reads=151464,  Duration=28509ms
    Query#2:  CPU=161,  Reads=1160,  Duration=447ms

    The first query took almost 30 seconds... the second one less than half-a-second.

     

     


    --Brad (My Blog)
    Wednesday, April 21, 2010 11:54 PM
    Moderator
  • Hi Brad,

    I really appreciate the time and effort you took to analyze this and came up with perfect examples to demonstrate this. This is awesome, because most of the time replies I get are -- just update statistics /index fragmentation , remove top 1 etc,. But in your first reply onwards you really looked it in the right angle.

    You really deserve the MVP.

     

    Thanks

    B. Abraham

    I am not quite sure about the context of this post, but as I read it seems to point out that my advice is subpar and I am undeserving of the MVP award, which I find really offensive.  I have never suggested that with absolute certainty your problem was caused by dated stats or index fragmentation.  What I did do is give you the first steps to take when dealing with performance problems.  In most cases, problems such as these are a direct result of the optimizer making bad decisions with bad stats.  I also presented how the product is "SUPPOSED" to work in relation to predicate order or joins.  The optimizer is supposed to optimize the join and predicate ordering to create an optimal query plan.  As Brad has shown predicate ordering can make a difference.  This is a problem with the optimizer and the product not functioning as the SQL Dev team has publicized. I have been working with Brad and MSFT offline to figure out the behavior. I am still actively trying to resolve and get to the root of your issue and would appreciate more professional courtesy.

    I will post back my findings and any information from Microsoft.

    <<But I love this kind of stuff... I eat it up... I can't get enough.

    Me too, but I am also concerned about the misinformation of predicate and join optimization, which seemingly does not work under all circumstances.

     


    http://jahaines.blogspot.com/
    Thursday, April 22, 2010 4:46 PM
    Moderator
  • Hi BAbraham,

    I have heard back from MSFT and it seems that EXISTS/NOT EXISTS is not part of the join optimization process.  It may be incorporated in future releases of SQL Server.  Here is the offical post from Conor, http://blogs.msdn.com/conor_cunningham_msft/archive/2010/05/14/conor-vs-anti-semi-join-reordering.aspx

    for now it seems the best thing you can do is put the smaller tables further upstream, so that it helps filter the larger tables down stream.

    I have also posted additional comments stating that this behavior is not limited to ANTI-SEMI joins, but also occurs with correlated subqueries in the predicate.

    select *
    from #Customers c
    WHERE (select MAX([CustomerID]) from #CustHugeRowSize where CustomerID=c.CustomerID) IS NULL
    AND (select MAX([CustomerID]) from #CustTeenyRowSize where CustomerID=c.CustomerID) IS NULL
    
    select *
    from #Customers c
    WHERE (select MAX([CustomerID]) from #CustTeenyRowSize where CustomerID=c.CustomerID) IS NULL
    AND (select MAX([CustomerID]) from #CustHugeRowSize where CustomerID=c.CustomerID) IS NULL
    
    /*
    (1 row(s) affected)
    Table '#CustTeenyRowSize___________________________________________________________________________________________________00000000001D'. Scan count 1, logical reads 664, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table '#Customers__________________________________________________________________________________________________________00000000001B'. Scan count 1, logical reads 471, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table '#CustHugeRowSize____________________________________________________________________________________________________00000000001C'. Scan count 1, logical reads 150373, physical reads 2314, read-ahead reads 149999, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    
    (1 row(s) affected)
    
    (1 row(s) affected)
    Table '#CustHugeRowSize____________________________________________________________________________________________________00000000001C'. Scan count 1, logical reads 5, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table '#Customers__________________________________________________________________________________________________________00000000001B'. Scan count 1, logical reads 471, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table '#CustTeenyRowSize___________________________________________________________________________________________________00000000001D'. Scan count 1, logical reads 673, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    
    (1 row(s) affected)
    
    */

     


    http://jahaines.blogspot.com/
    Friday, May 14, 2010 4:01 PM
    Moderator

All replies

  • Hello All,

    SQL 2005 64bit enterprise 9.00.4035.00

    I saw a strange behavior in SQL Server execution plan. It changes depends on where you have the NOT EXISTS clause.

    Below query , if you move  ---------   AND NOT EXISTS ( SELECT TOP 1 1 FROM EmergencyPool EmergencyPool ( NOLOCK ) WHERE Employee. EmployeeID = EmergencyPool. EmployeeID)   -------------    from top to bottom, the entire plan change. ( I have it in top and bottom in below query)

    When the highlighted part is in top, exec plan first join Employee table with EmergencyPool,  and later join  EmployeeAttributeValue and other tables. If we put it in bottom, plan just join EmployeeAttributeValue with Employee table and later join EmergencyPool and other tables.

    This make a big difference in query execution. 2 sec v/s 400 sec. I am not wondering why is this happening?

     

    <!-- [if gte mso 10]> <mce:style>

    SELECT TOP 1000 Employee. EmployeeID FROM Employee ( NOLOCK )

                WHERE   ( Employee. EmployeeStatusID= 2006362) AND

                            ( Employee. EmailStatusTypeID= 1) AND

                            ( Employee. IsTestID= 0)   AND

                            (( Employee. IsPayRoll= 1)) AND

                            ( Employee. DeptID IN ( 53))  

                            AND NOT EXISTS ( SELECT TOP 1 1 FROM EmergencyPool EmergencyPool ( NOLOCK ) WHERE Employee. EmployeeID = EmergencyPool. EmployeeID)  

                            AND (( Employee. LastResponseDate IS NULL AND Employee. CREATEDATE >= '10/9/2009 12:32:47 PM' ) OR Employee. LastResponseDate >= '4/9/2009 12:32:47 PM' )

                            AND ((( DATEPART ( yyyy, GETUTCDATE ()) - DATEPART ( YEAR , Employee. BirthDate) BETWEEN 40 AND 44)

                                              OR ( DATEPART ( yyyy, GETUTCDATE ()) - DATEPART ( YEAR , Employee. BirthDate) BETWEEN 35 AND 39) )

                            AND   EXISTS( SELECT TOP 1 1 FROM EmployeeAttributeValue pav ( NOLOCK ) WHERE Employee. EmployeeID = pav. EmployeeID

                                              AND pav. AttributeKeyID = 1001184 AND pav. AttributeValueID IN ( 2003118, 2003116))

                            AND ( Employee. GenderID IN ( 2000246))

                            AND ( Employee. CountryID IN ( 2000200)))

                            AND NOT EXISTS ( SELECT TOP 1 1 FROM TrackingEmployee stp ( NOLOCK ) WHERE stp. EmployeeID= Employee. EmployeeID

                                              AND ( stp. ResponseID= 61830  AND stp. WaveID= 81673))

                            AND NOT EXISTS ( SELECT TOP 1 1 FROM InvitesLQ ( NOLOCK )    WHERE InvitesLQ. EmployeeID= Employee. EmployeeID

                                        AND ( InvitesLQ. ResponseID= 61830     AND InvitesLQ. WaveID= 81673))  

                            AND NOT EXISTS ( SELECT TOP 1 1 FROM EmergencyPool EmergencyPool ( NOLOCK ) WHERE Employee. EmployeeID = EmergencyPool. EmployeeID)  

     

     

     

     

    • Moved by Tom PhillipsModerator Monday, April 19, 2010 9:16 PM Possibly better answer from TSQL forum (From:SQL Server Database Engine)
    • Merged by KJian_ Friday, April 23, 2010 6:51 AM
    Monday, April 19, 2010 8:56 PM
  • I can't see the highlights in the post, but what might be happening is that the optimiser is allocating more memory to the query when you have it one way around vs the other. This can be due to the actual parameters you supplied and the data distribution in the table. If SQL thinks there will be lots of rows to process it will allocate more memory. When it has less memory it may need to spill to tempdb which causes the performance hit.

    You may be able to verify this by running the query and tracing with SQL Profiler with the 'Sort Warnings' option turned on.

     

    PS you should probably remove the TOP 1 clauses from inside the EXISTS clauses. I'm pretty sure these are pointless since you are just testing for existence. The optimiser will stop after it has found 1 row so you don't need to limit it in this way.

     

    Hope  that helps,

    Ben

    Monday, April 19, 2010 9:12 PM
  • Thanks Ben for the reply.

    The highlight didn't come through.

    Below the part which makes all difference. I have it in the query both places.

    AND NOT EXISTS ( SELECT TOP 1 1 FROM EmergencyPool EmergencyPool ( NOLOCK ) WHERE Employee. EmployeeID = EmergencyPool. EmployeeID)

    Monday, April 19, 2010 9:34 PM
  • Will you get the same problem after removing TOP 1 ?
    Premature optimization is the root of all evil in programming. (c) by Donald Knuth

    Naomi Nosonovsky, Sr. Programmer-Analyst

    My blog
    Monday, April 19, 2010 9:39 PM
    Moderator
  • I didn't know about this before, but what you say is true... and very interesting... but it makes sense when you think about it.

    The way that the optimizer puts together a NOT EXISTS query is by doing a LEFT ANTI SEMI JOIN, which means doing a LEFT JOIN and only keeping the data from the left side (SEMI) if there is NOT any match in the right side (ANTI).

    And LEFT JOINs (or RIGHT JOINs for that matter) depend on the order.

    For example... the following two queries in NorthWind will bring about two different query plans:

    SELECT *
    FROM Employees
    WHERE NOT EXISTS (SELECT * FROM Orders WHERE EmployeeID=Employees.EmployeeID)
      AND NOT EXISTS (SELECT * FROM EmployeeTerritories WHERE EmployeeID=Employees.EmployeeID)

    SELECT *
    FROM Employees
    WHERE NOT EXISTS (SELECT * FROM EmployeeTerritories WHERE EmployeeID=Employees.EmployeeID)
      AND NOT EXISTS (SELECT * FROM Orders WHERE EmployeeID=Employees.EmployeeID)

    The only difference between them is the order of the NOT EXISTS in the WHERE clause. 

    The first query above does a LEFT ANTI SEMI JOIN with Orders, then any employees that pass that test are involved in a LEFT ANTI SEMI JOIN with EmployeeTerritories.

    The second does the opposite (checks Territories first and then Orders).  If Northwind were a bigger database, and there were hundreds of employees with no orders (but every one of them had a territory), then the first query above would go slower than the second query, because the first query would have to JOIN the hundreds of employees with no orders to the Territories table, but the second query would end up with zero employees right away with the first join to Territories.

    So, the order of it IS important in how you incorporate the NOT EXISTS in your WHERE clause.


     


    --Brad (My Blog)
    Monday, April 19, 2010 9:47 PM
    Moderator
  • Can you post the execution plan? i.e. the .sqlplan file as XML
    Tuesday, April 20, 2010 9:22 AM
  • Sorry to tell that I double posted it. The same problem has been reproduced by Brad_Schulz<abbr class="affil"> in NorthWind database.</abbr>

    Below the link.

    http://social.msdn.microsoft.com/Forums/en-US/transactsql/thread/44dfa9bc-4438-46a3-92ea-113400d0b3a4

    Below the queries. We can clearly see the execution plans changes.

    SELECT *
    FROM Employees
    WHERE NOT EXISTS (SELECT * FROM Orders WHERE EmployeeID=Employees.EmployeeID)
      AND NOT EXISTS (SELECT * FROM EmployeeTerritories WHERE EmployeeID=Employees.EmployeeID)

    SELECT *
    FROM Employees
    WHERE NOT EXISTS (SELECT * FROM EmployeeTerritories WHERE EmployeeID=Employees.EmployeeID)
      AND NOT EXISTS (SELECT * FROM Orders WHERE EmployeeID=Employees.EmployeeID)

     

    Tuesday, April 20, 2010 8:52 PM
  • Anonymous...

    Would you mind posting your (actual... not estimated) query plans... the one with the NOT EXISTS at the beginning and the one with it at the end?

    I've confirmed the behavior I told you about in the other thread, but I can't duplicate such a huge discrepancy in time (2sec vs 400sec).

    If you can make your .SQLPLAN files available (right-click on graphical plan and SaveAs...) at a public site to download or just do a SET STATISTICS PROFILE ON and execute the queries and post the resulting query plans, I would be grateful.

    I'd like to blog about this phenomenon, but I'd like to get a sense of why your time discrepancies are so big.  Any info you can provide would be appreciated.

    Thanks...


    --Brad (My Blog)
    Tuesday, April 20, 2010 9:11 PM
    Moderator
  • @Brad,

    I dont find it odd that the optimizer made the choices that it did.  You have to remember that the optimizer is cost based.  This means that the plan it chooses is not always optimal but "good enough", you can see this in the "select" properties of the query plan.  In the northwind database (as shown above) the order was kept based on your ordering; however, this is never gauranteed.  The optimizer is free to rearrange a predicate or join as it sees fit.  I think what you are witnessing is the optimizer settling on a good enough plan based on the current statistics.  For example, why should the optimizer spend extra time calculating join orders when the optimizer only calculates that the increased performance will be milliseconds.....?  in this case, it does not make sense to work through more permutations; however, if the distribution of data is significantly different, the optimizer will evaluate more options, as it knows a few more permutations may yield a much more performant plan.

    @OP,

    I suspect that your statistics are severly out of date or your indexes are heavily fragmented.  There is absolutely no reason you should see this type of deviation.  Rebuild your indexes and update any manual stats you have on the table and you should see much better performance.


    http://jahaines.blogspot.com/
    Tuesday, April 20, 2010 10:15 PM
    Moderator
  • I made a post on the other thread but I will post it here also.

    @Brad,

    I dont find it odd that the optimizer made the choices that it did.  You have to remember that the optimizer is cost based.  This means that the plan it chooses is not always optimal but "good enough", you can see this in the "select" properties of the query plan.  In the northwind database (as shown above) the order was kept based on your ordering; however, this is never gauranteed.  The optimizer is free to rearrange a predicate or join as it sees fit.  I think what you are witnessing is the optimizer settling on a good enough plan based on the current statistics.  For example, why should the optimizer spend extra time calculating join orders when the optimizer only calculates that the increased performance will be milliseconds.....?  in this case, it does not make sense to work through more permutations; however, if the distribution of data is significantly different, the optimizer will evaluate more options, as it knows a few more permutations may yield a much more performant plan.

    @OP,

    I suspect that your statistics are severly out of date or your indexes are heavily fragmented.  There is absolutely no reason you should see this type of deviation.  Rebuild your indexes and update any manual stats you have on the table and you should see much better performance.


    http://jahaines.blogspot.com/
    Tuesday, April 20, 2010 10:16 PM
    Moderator
  • Thanks for jumping in, Adam...

    It's not that I find it odd, but that I find it interesting... I know that NOT EXISTS are translated to LEFT (ANTI SEMI) JOINs, so the order in which they are presented can make a difference, just as the order of LEFT JOINs can make a difference. 

    But correct me if that statement is untrue... I know that for INNER JOINs, the optimizer can apply them in any order it wishes; however, I believe that the order of multiple LEFT JOINs are done in the order they are written. 


    --Brad (My Blog)
    Tuesday, April 20, 2010 10:32 PM
    Moderator
  • Brad,

    A left join does preserve the base table; however, I believe the ordering for each of the ANTI tables is not gauranteed.

    In the example you posted, it is gauranteed that the base or preserved outer table will be Employee, but not that the EmployeeTerritories or Orders is joined in the order provided by the user.  Since both of these table relate to the same outer table, the optimizer gets the final say as to which order the joins are issued.  If you want more control over joins, you can use a "bushy joins", but the optimizer does a good job of this already. I will see if I can work up a sample to demonstrate this behavior.

    You can read more on bushy joins from Itzik's site. ,http://www.solidq.com/insidetsql/resources.htm (look in the tips and tricks link)


    http://jahaines.blogspot.com/
    Tuesday, April 20, 2010 11:49 PM
    Moderator
  • Hi Adam...

    In doing some experiments, it seems that in doing multiple OUTER JOINs, the optimizer can mix up the tables; however, the FROM table and the first table that is LEFT JOINed are always linked.

    In AdventureWorks:

    SELECT c.CustomerID
    FROM Sales.Customer c
    LEFT JOIN Sales.SalesOrderHeader h ON c.CustomerID=h.CustomerID
    LEFT JOIN Sales.StoreContact s ON c.CustomerID=s.CustomerID
    LEFT JOIN Sales.CustomerAddress a on c.CustomerID=a.CustomerID

    SELECT c.CustomerID
    FROM Sales.Customer c
    LEFT JOIN Sales.StoreContact s ON c.CustomerID=s.CustomerID
    LEFT JOIN Sales.SalesOrderHeader h ON c.CustomerID=h.CustomerID
    LEFT JOIN Sales.CustomerAddress a on c.CustomerID=a.CustomerID

    SELECT c.CustomerID
    FROM Sales.Customer c
    LEFT JOIN Sales.CustomerAddress a on c.CustomerID=a.CustomerID
    LEFT JOIN Sales.SalesOrderHeader h ON c.CustomerID=h.CustomerID
    LEFT JOIN Sales.StoreContact s ON c.CustomerID=s.CustomerID

    All three of the above query plans are different... but the only difference in the queries themselves is the order of the LEFT JOINs.

    In all three, the FROM table is linked to the first LEFT JOINed table... they seem to always be inextricably linked... so the order does matter (at least the order of the first table that is JOINed).

     


    --Brad (My Blog)
    Wednesday, April 21, 2010 12:15 AM
    Moderator
  • Here's a quick experiment I did...

    Consider the following 3 queries... we'll call them Query#1 and Query#2 and Query#3:

    --Query#1
    select CustomerID
    from Sales.Customer c
    where exists (select * from Sales.StoreContact where CustomerID=c.CustomerID)
     and exists (select * from Sales.SalesOrderHeader where CustomerID=c.CustomerID)
     and exists (select * from Sales.CustomerAddress where CustomerID=c.CustomerID)
    
    --Query#2
    select CustomerID
    from Sales.Customer c
    where exists (select * from Sales.SalesOrderHeader where CustomerID=c.CustomerID)
     and exists (select * from Sales.StoreContact where CustomerID=c.CustomerID)
     and exists (select * from Sales.CustomerAddress where CustomerID=c.CustomerID)
    
    --Query#3
    select CustomerID
    from Sales.Customer c
    where exists (select * from Sales.CustomerAddress where CustomerID=c.CustomerID)
     and exists (select * from Sales.SalesOrderHeader where CustomerID=c.CustomerID)
     and exists (select * from Sales.StoreContact where CustomerID=c.CustomerID)
    

     

    Same queries (but with different order of the NOT EXISTS)... same result set... but 3 different query plans... and 3 different behaviors:

    Query#1:  CPU=349, Reads=5188, Duration=490
    Query#2:  CPU=306, Reads=3255, Duration=458
    Query#3:  CPU=298, Reads=5361, Duration=402

     

     


    --Brad (My Blog)
    Wednesday, April 21, 2010 1:03 AM
    Moderator
  • Follow-up...

    Same queries except with NOT EXISTS (instead of just EXISTS):

    Query#1:  CPU=64, Reads=192, Duration=415
    Query#2:  CPU=39, Reads=192, Duration=356
    Query#3:  CPU=37, Reads=247, Duration=175

     


    --Brad (My Blog)
    Wednesday, April 21, 2010 1:28 AM
    Moderator
  • Adam (and everyone else still reading this thread):

    I came up with a really good example that demonstrates this difference in query execution... just from the order of the NOT EXISTS predicates.  This is what I'll be putting into a blog post.

    First, create a Customer table, a CustHugeRowSize (child) table, and a CustTeenyRowSize (child) table:

    if object_id('TempDB..#Customers','U') is not null drop table #Customers
    go
    create table #Customers 
    (
      CustomerID int primary key
     ,Name varchar(30)
    )
    go
     
    if object_id('TempDB..#CustHugeRowSize','U') is not null drop table #CustHugeRowSize
    go
    create table #CustHugeRowSize
    (
      CustomerID int
     ,SeqID int identity(1,1)
     ,Filler char(3500) default replicate('*',3500)
    )
    go
    create unique clustered index PK_CustHuge on #CustHugeRowSize(CustomerID,SeqID)
    go
     
    if object_id('TempDB..#CustTeenyRowSize','U') is not null drop table #CustTeenyRowSize
    go
    create table #CustTeenyRowSize
    (
      CustomerID int
     ,SeqID int identity(1,1)
     ,Junk bit default 0
    )
    go
    create unique clustered index PK_CustTeeny on #CustTeenyRowSize(CustomerID,SeqID)
    go
    

     

    Next, populate the Customer table with 100,000 rows, and populate the two child tables with 3 entries for each customer... except for CustomerID 98765:

    with 
     L0(c) as (select 0 union all select 0 union all select 0)    --3 Rows
     ,L1(c) as (select 0 from L0 a cross join L0 b cross join L0 c)  --27 Rows (3x3x3)
     ,L2(c) as (select 0 from L1 a cross join L1 b cross join L1 c)  --19683 Rows (27x27x27)
     ,L3(c) as (select 0 from L2 a cross join L2 b)          --387,420,489 Rows (19683x19683)
     ,NN(n) as (select row_number() over (order by (select 0)) from L3)
    insert #Customers (CustomerID,Name)
    select n,'Customer Number '+ltrim(str(n))
    from NN
    where n<=100000
     
    insert #CustHugeRowSize (CustomerID)
    select CustomerID
    from #Customers
    cross join (select 1 union all select 2 union all select 3) X(N)
    where CustomerID<>98765
    
    insert #CustTeenyRowSize (CustomerID)
    select CustomerID
    from #Customers
    cross join (select 1 union all select 2 union all select 3) X(N)
    where CustomerID<>98765
    

     

    Make sure statistics are completely up-to-date in the child tables:

    update statistics #CustHugeRowSize(PK_CustHuge) with fullscan
    update statistics #CustTeenyRowSize(PK_CustTeeny) with fullscan
    

     

    And now we have the two queries.  The only difference between them is the order of the NOT EXISTS predicates:

    select *
    from #Customers c
    where not exists (select * from #CustHugeRowSize where CustomerID=c.CustomerID)
     and not exists (select * from #CustTeenyRowSize where CustomerID=c.CustomerID)
    
    select *
    from #Customers c
    where not exists (select * from #CustTeenyRowSize where CustomerID=c.CustomerID)
     and not exists (select * from #CustHugeRowSize where CustomerID=c.CustomerID)
    

     

    The estimated query plan shows a relative cost of  98% : 2%  for the two queries.

    And, sure enough, if you run a trace on them, here are the results:

    Query#1:  CPU=1265,  Reads=151464,  Duration=28509ms
    Query#2:  CPU=161,  Reads=1160,  Duration=447ms

    The first query took almost 30 seconds... the second one less than half-a-second.

     

     


    --Brad (My Blog)
    Wednesday, April 21, 2010 11:54 PM
    Moderator
  • Hi Brad,

    I really appreciate the time and effort you took to analyze this and came up with perfect examples to demonstrate this. This is awesome, because  in your first reply onwards you really looked it in the right angle.

    You really deserve the MVP.

     

    Thanks

    B. Abraham

    Thursday, April 22, 2010 4:09 PM
  • Hi Brad,

    I really appreciate the time and effort you took to analyze this and came up with perfect examples to demonstrate this. This is awesome, because most of the time replies I get are -- just update statistics /index fragmentation , remove top 1 etc,. But in your first reply onwards you really looked it in the right angle.

    You really deserve the MVP.

     

    Thanks

    B. Abraham

    Wow, thanks!  You made my day.

    But I love this kind of stuff... I eat it up... I can't get enough.

    So this has been fun.  Adam and I and a couple other friends are digging deeper, consulting with some MSFT people to check into this behavior. 

    Despite what I said in my first message to you, the more I think of it, it now seems strange that the optimizer would behave this way.  With two LEFT JOINs referring only to the FROM table (and not to each other in any way), it seems that the optimizer SHOULD be able to arrange the join order in only one way (the "best" way in terms of cost) instead of always linking together the FROM table and the first LEFT JOINed table.

    I'll keep you posted on what we find out... and I'll put it in my blog too.

    BTW, don't pay any attention to the TOP 1 stuff in the EXISTS query... the optimizer will throw it out any way, so it doesn't matter if it's there or not.  In fact, the optimizer really couldn't care less what is in an EXISTS subquery except for the FROM table(s) and the WHERE clause... check out an article I wrote about it here:  http://bradsruminations.blogspot.com/2009/09/age-old-select-vs-select-1-debate.html

     


    --Brad (My Blog)
    Thursday, April 22, 2010 4:25 PM
    Moderator
  • Hi Brad,

    I really appreciate the time and effort you took to analyze this and came up with perfect examples to demonstrate this. This is awesome, because most of the time replies I get are -- just update statistics /index fragmentation , remove top 1 etc,. But in your first reply onwards you really looked it in the right angle.

    You really deserve the MVP.

     

    Thanks

    B. Abraham

    I am not quite sure about the context of this post, but as I read it seems to point out that my advice is subpar and I am undeserving of the MVP award, which I find really offensive.  I have never suggested that with absolute certainty your problem was caused by dated stats or index fragmentation.  What I did do is give you the first steps to take when dealing with performance problems.  In most cases, problems such as these are a direct result of the optimizer making bad decisions with bad stats.  I also presented how the product is "SUPPOSED" to work in relation to predicate order or joins.  The optimizer is supposed to optimize the join and predicate ordering to create an optimal query plan.  As Brad has shown predicate ordering can make a difference.  This is a problem with the optimizer and the product not functioning as the SQL Dev team has publicized. I have been working with Brad and MSFT offline to figure out the behavior. I am still actively trying to resolve and get to the root of your issue and would appreciate more professional courtesy.

    I will post back my findings and any information from Microsoft.

    <<But I love this kind of stuff... I eat it up... I can't get enough.

    Me too, but I am also concerned about the misinformation of predicate and join optimization, which seemingly does not work under all circumstances.

     


    http://jahaines.blogspot.com/
    Thursday, April 22, 2010 4:46 PM
    Moderator
  • Hi B. Abraham,

    I haven't been on the forums much in the past few days and didnt get a chance to respond to your response.  I wanted to clear the air and let you know that there are no hard feelings.  I wasn't sure of the context you posted originally, but your response did clear it up.    I am glad we can put this behind us and move forward.

    On a side note, this thread has been escalated to the MSFT dev team and I should be hearing something shortly.  I will keep you posted.

    Thanks,

    Adam


    http://jahaines.blogspot.com/
    Wednesday, April 28, 2010 7:44 PM
    Moderator
  • Hi BAbraham,

    I have heard back from MSFT and it seems that EXISTS/NOT EXISTS is not part of the join optimization process.  It may be incorporated in future releases of SQL Server.  Here is the offical post from Conor, http://blogs.msdn.com/conor_cunningham_msft/archive/2010/05/14/conor-vs-anti-semi-join-reordering.aspx

    for now it seems the best thing you can do is put the smaller tables further upstream, so that it helps filter the larger tables down stream.

    I have also posted additional comments stating that this behavior is not limited to ANTI-SEMI joins, but also occurs with correlated subqueries in the predicate.

    select *
    from #Customers c
    WHERE (select MAX([CustomerID]) from #CustHugeRowSize where CustomerID=c.CustomerID) IS NULL
    AND (select MAX([CustomerID]) from #CustTeenyRowSize where CustomerID=c.CustomerID) IS NULL
    
    select *
    from #Customers c
    WHERE (select MAX([CustomerID]) from #CustTeenyRowSize where CustomerID=c.CustomerID) IS NULL
    AND (select MAX([CustomerID]) from #CustHugeRowSize where CustomerID=c.CustomerID) IS NULL
    
    /*
    (1 row(s) affected)
    Table '#CustTeenyRowSize___________________________________________________________________________________________________00000000001D'. Scan count 1, logical reads 664, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table '#Customers__________________________________________________________________________________________________________00000000001B'. Scan count 1, logical reads 471, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table '#CustHugeRowSize____________________________________________________________________________________________________00000000001C'. Scan count 1, logical reads 150373, physical reads 2314, read-ahead reads 149999, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    
    (1 row(s) affected)
    
    (1 row(s) affected)
    Table '#CustHugeRowSize____________________________________________________________________________________________________00000000001C'. Scan count 1, logical reads 5, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table '#Customers__________________________________________________________________________________________________________00000000001B'. Scan count 1, logical reads 471, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    Table '#CustTeenyRowSize___________________________________________________________________________________________________00000000001D'. Scan count 1, logical reads 673, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
    
    (1 row(s) affected)
    
    */

     


    http://jahaines.blogspot.com/
    Friday, May 14, 2010 4:01 PM
    Moderator
  • Thanks Adam. You guys are a great help.

    As a temporary fix that's what we did to our application.( put the smaller tables further upstream). But now it confirmed that it's right way for the time being.

    Please continue good work of helping others.

    Bye for now.

    B. Abraham

     

    Friday, May 14, 2010 4:09 PM
  • >
    >I have also posted additional comments stating that this behavior is not
    >limited to ANTI-SEMI joins, but also occurs with correlated subqueries in the predicate.
    >

    ...And also occurs with OUTER JOINs in general.

    If you have multiple LEFT JOINs in a query, changing their order may result in a more efficient plan.

     


    --Brad (My Blog)
    Friday, May 14, 2010 4:48 PM
    Moderator
  • In case other people's answers were not clear enough: the order of the NOT EXISTS (or for that matter LEFT OUTER JOINS) do not affect the end result.

    Because of that, the optimizer is free to rearrange any of these NOT EXISTs, and will do so if the expected performance difference is big enough.

    For that to happen, the selectivity / rowcount of one NOT EXISTS should be significantly different from the selectivity / rowcount of the other.

    -- 

    Gert-Jan

    Saturday, May 22, 2010 8:06 PM