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.

I've often read when one had to check existence of a row should always be done with EXISTS instead of with a COUNT.

Yet in several recent scenarios I've measured a performance improvement when using count.
The pattern goes like this:

LEFT JOIN (
    SELECT
        someID
        , COUNT(*)
    FROM someTable
    GROUP BY someID
) AS Alias ON (
    Alias.someID = mainTable.ID
)

I'm not familiar with methods to tell what's happening "inside" SQL Server so I was wondering if there was a unheralded flaw with EXISTS that gave perfectly sense to the measurements I've done (could EXISTS be RBAR?!).

Do you have some explanation to that phenomena?

EDIT:

Here's a full script you can run:

SET NOCOUNT ON
SET STATISTICS IO OFF

DECLARE @tmp1 TABLE (
    ID INT UNIQUE
)


DECLARE @tmp2 TABLE (
    ID INT
    , X INT IDENTITY
    , UNIQUE (ID, X)
)

; WITH T(n) AS (
    SELECT
        ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
    FROM master.dbo.spt_values AS S
) 
, tally(n) AS (
    SELECT
        T2.n * 100 + T1.n
    FROM T AS T1
    CROSS JOIN T AS T2
    WHERE T1.n <= 100
    AND T2.n <= 100
)
INSERT @tmp1
SELECT n
FROM tally AS T1
WHERE n < 10000


; WITH T(n) AS (
    SELECT
        ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
    FROM master.dbo.spt_values AS S
) 
, tally(n) AS (
    SELECT
        T2.n * 100 + T1.n
    FROM T AS T1
    CROSS JOIN T AS T2
    WHERE T1.n <= 100
    AND T2.n <= 100
)
INSERT @tmp2
SELECT T1.n
FROM tally AS T1
CROSS JOIN T AS T2
WHERE T1.n < 10000
AND T1.n % 3 <> 0
AND T2.n < 1 + T1.n % 15

PRINT '
COUNT Version:
'

WAITFOR DELAY '00:00:01'

SET STATISTICS IO ON
SET STATISTICS TIME ON

SELECT
    T1.ID
    , CASE WHEN n > 0 THEN 1 ELSE 0 END AS DoesExist
FROM @tmp1 AS T1
LEFT JOIN (
    SELECT
        T2.ID
        , COUNT(*) AS n
    FROM @tmp2 AS T2
    GROUP BY T2.ID
) AS T2 ON (
    T2.ID = T1.ID
)
WHERE T1.ID BETWEEN 5000 AND 7000
OPTION (RECOMPILE) -- Required since table are filled within the same scope

SET STATISTICS TIME OFF

PRINT '

EXISTS Version:'

WAITFOR DELAY '00:00:01'

SET STATISTICS TIME ON

SELECT
    T1.ID
    , CASE WHEN EXISTS (
        SELECT 1
        FROM @tmp2 AS T2
        WHERE T2.ID = T1.ID
    ) THEN 1 ELSE 0 END AS DoesExist
FROM @tmp1 AS T1
WHERE T1.ID BETWEEN 5000 AND 7000
OPTION (RECOMPILE) -- Required since table are filled within the same scope

SET STATISTICS TIME OFF 

On SQL Server 2008R2 (Seven 64bits) I get this result

COUNT Version:

Table '#455F344D'. Scan count 1, logical reads 8, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table '#492FC531'. Scan count 1, logical reads 30, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 81 ms.

EXISTS Version:

Table '#492FC531'. Scan count 1, logical reads 96, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table '#455F344D'. Scan count 1, logical reads 8, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 76 ms.

share|improve this question

migrated from stackoverflow.com Jul 15 '13 at 2:26

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

1  
Can you post the full query? –  GolezTrol Jul 10 '13 at 8:16
1  
I don't know what version/edition/OSs your running, but on my machine (Win7, x64, SQL Server 2012 Developer), for COUNT I get 0ms, 12ms and 0ms, 96ms, and for EXISTS I get 1ms, 1ms, and 16ms, 78ms. Which by my maths makes the EXISTS one marginally faster. –  Damien_The_Unbeliever Jul 10 '13 at 10:08
2  
You have too few records to get a meaningful comparison. The plan used by the optimizer will change as cardinalities increase. Also using temp tables vs table variables could change plans as well when statistics are considered. –  StrayCatDBA Jul 10 '13 at 11:40
4  
No EXISTS is not RBAR, both plans have a MERGE join that processes each input once. The difference between the plans is the size of the inputs considered. The COUNT version only processes rows from @tmp2 that match the BETWEEN 5000 AND 7000 predicate whereas the EXISTS one scans all rows in that table. Not sure why this is the case. –  Martin Smith Jul 13 '13 at 11:03
5  
Heh, you know, I have t-shirt with my username on it, but the first four letters crossed out ("<strike>RBAR</strike>RYYOUNG"). –  RBarryYoung Jul 13 '13 at 15:53

2 Answers 2

I've often read when one had to check existence of a row should always be done with EXISTS instead of with a COUNT.

It's very rare for anything to always be true, especially when it comes to databases. There are any number of ways to express the same semantic in SQL. If there is a useful rule of thumb, it might be to write queries using the most natural syntax available (and, yes, that is subjective) and only consider rewrites if the query plan or performance you get is unacceptable.

For what it's worth, my own take on the issue is that existence queries are most naturally expressed using EXISTS. It has also been my experience that EXISTS tends to optimize better than the OUTER JOIN reject NULL alternative. Using COUNT(*) and filtering on =0 is another alternative, that happens to have some support in the SQL Server query optimizer, but I have personally found this to be unreliable in more complex queries. In any case, EXISTS just seems much more natural (to me) than either of those alternatives.

I was wondering if there was a unheralded flaw with EXISTS that gave perfectly sense to the measurements I've done

Your particular example is interesting, because it highlights the way the optimizer deals with subqueries in CASE expressions (and EXISTS tests in particular).

Subqueries in CASE expressions

Consider the following (perfectly legal) query:

DECLARE @Base AS TABLE (a integer NULL);
DECLARE @When AS TABLE (b integer NULL);
DECLARE @Then AS TABLE (c integer NULL);
DECLARE @Else AS TABLE (d integer NULL);

SELECT
    CASE
        WHEN (SELECT W.b FROM @When AS W) = 1
            THEN (SELECT T.c FROM @Then AS T)
        ELSE (SELECT E.d FROM @Else AS E)
    END
FROM @Base AS B;

The semantics of CASE are that WHEN/ELSE clauses are generally evaluated in textual order. In the query above, it would be incorrect for SQL Server to return an error if the ELSE subquery returned more than one row, if the WHEN clause was satisfied. To respect these semantics, the optimizer produces a plan that uses pass-through predicates:

Pass-through predicates

The inner side of the nested loop joins are only evaluated when the pass-through predicate returns false. The overall effect is that CASE expressions are tested in order, and subqueries are only evaluated if no previous expression was satisfied.

CASE expressions with an EXISTS subquery

Where a CASE subquery uses EXISTS, the logical existence test is implemented as a semi-join, but rows that would normally be rejected by the semi-join have to be retained in case a later clause needs them. Rows flowing through this special kind of semi-join acquire a flag to indicate if the semi-join found a match or not. This flag is known as the probe column.

The details of the implementation is that the logical subquery is replaced by a correlated join ('apply') with a probe column. The work is performed by a simplification rule in the query optimizer called RemoveSubqInPrj (remove subquery in projection). We can see the details using trace flag 8606:

SELECT
    T1.ID,
    CASE
        WHEN EXISTS 
        (
            SELECT 1
            FROM #T2 AS T2
            WHERE T2.ID = T1.ID
        ) THEN 1 
    ELSE 0
    END AS DoesExist
FROM #T1 AS T1
WHERE T1.ID BETWEEN 5000 AND 7000
OPTION (QUERYTRACEON 3604, QUERYTRACEON 8606);

Part of the input tree showing the EXISTS test is shown below:

ScaOp_Exists 
    LogOp_Project
        LogOp_Select
            LogOp_Get TBL: #T2
            ScaOp_Comp x_cmpEq
                ScaOp_Identifier [T2].ID
                ScaOp_Identifier [T1].ID

This is transformed by RemoveSubqInPrj to a structure headed by:

LogOp_Apply (x_jtLeftSemi probe PROBE:COL: Expr1008)

This is the left semi-join apply with probe described previously. This initial transformation is the only one available in SQL Server query optimizers to date, and compilation will simply fail if this transformation is disabled.

One of the possible execution plan shapes for this query is a direct implementation of that logical structure:

NLJ Semi Join with Probe

The final Compute Scalar evaluates the result of the CASE expression using the probe column value:

Compute Scalar expression

The basic shape of the plan tree is preserved when the optimize considers other physical join types for the semi join. Only merge join supports a probe column, so a hash semi join, though logically possible, is not considered:

Merge with probe column

Notice the merge outputs an expression labelled Expr1008 (that the name is the same as before is a coincidence) though no definition for it appears on any operator in the plan. This is just the probe column again. As before, the final Compute Scalar uses this probe value to evaluate the CASE.

The problem is that the optimizer doesn't fully explore alternatives that only become worthwhile with merge (or hash) semi join. In the nested loops plan, there is no advantage to checking if rows in T2 match the range on every iteration. With a merge or hash plan, this could be a useful optimization.

If we add a matching BETWEEN predicate to T2 in the query, all that happens is that this check is performed for each row as a residual on the merge semi join (tough to spot in the execution plan, but it is there):

SELECT
    T1.ID,
    CASE
        WHEN EXISTS 
        (
            SELECT 1
            FROM #T2 AS T2
            WHERE T2.ID = T1.ID
            AND T2.ID BETWEEN 5000 AND 7000 -- New
        ) THEN 1 
    ELSE 0
    END AS DoesExist
FROM #T1 AS T1
WHERE T1.ID BETWEEN 5000 AND 7000;

Residual predicate

We would hope that the BETWEEN predicate would instead be pushed down to T2 resulting in a seek. Normally, the optimizer would consider doing this (even without the extra predicate in the query). It recognizes implied predicates (BETWEEN on T1 and the join predicate between T1 and T2 together imply the BETWEEN on T2) without them being present in the original query text. Unfortunately, the apply-probe pattern means this is not explored.

There are ways to write the query to produce seeks on both inputs to a merge semi join. One way involves writing the query in quite an unnatural way (defeating the reason I generally prefer EXISTS):

WITH T2 AS
(
    SELECT TOP (9223372036854775807) * 
    FROM #T2 AS T2 
    WHERE ID BETWEEN 5000 AND 7000
)
SELECT 
    T1.ID, 
    DoesExist = 
        CASE 
            WHEN EXISTS 
            (
                SELECT * FROM T2 
                WHERE T2.ID = T1.ID
            ) THEN 1 ELSE 0 END
FROM #T1 AS T1
WHERE T1.ID BETWEEN 5000 AND 7000;

TOP trick plan

I wouldn't be happy writing that query in a production environment, it's just to demonstrate that the desired plan shape is possible. If the real query you need to write uses CASE in this particular way, and performance suffers by there not being a seek on the probe side of a merge semi-join, you might consider writing the query using different syntax that produces the right results and a more efficient execution plan.

share|improve this answer

The "COUNT(*) vs EXISTS" argument is to do with checking whether a record exists. For example:

WHERE (SELECT COUNT(*) FROM Table WHERE ID=@ID)>0

vs

WHERE EXISTS(SELECT ID FROM Table WHERE ID=@ID)

Your SQL script isn't using COUNT(*) as a record exist check, and therefore I wouldn't say that its applicable in your scenario.

share|improve this answer
    
Any though/conclusion based on the script I posted? –  Serge Jul 10 '13 at 9:26

Your Answer

 
discard

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