order of clauses in “EXISTS (…) OR EXISTS (…)”

Question

I have a class of queries that test for the existence of one of two things. It is of the form

SELECT CASE
  WHEN EXISTS (SELECT 1 FROM ...)
  OR EXISTS (SELECT 1 FROM ...)
THEN 1 ELSE 0 END;

The actual statement is generated in C and executed as an ad-hoc query over an ODBC connection.

It has recently come to light that the second SELECT will probably be faster than the first SELECT in most cases and that switching the order of the two EXISTS clauses caused a drastic speedup in at least one abusive test case we had just created.

The obvious thing to do is just go ahead and switch the two clauses, but I wanted to see if someone more familiar with SQL Server would care to weigh in on this. It feels like I am relying on coincidence and an "implementation detail".

(It also seems like if SQL Server were smarter, it would execute both EXISTS clauses in parallel and let whichever one one completed first short-circuit the other.)

Is there a better way to get SQL Server to consistently improve the running time of such a query?

Update

Thank you for your time and interest in my question. I was not expecting questions about the actual query plans, but I am willing to share them.

This is for a software component that supports SQL Server 2008R2 and greater. The shape of the data can be quite different depending on configuration and use. My coworker thought of making this change to the query because the (in the example) dbf_1162761$z$rv$1257927703 table will always have greater or equal to the number of rows in it than the dbf_1162761$z$dd$1257927703 table -- sometimes significantly more (orders of magnitude).

Here is the abusive case I mentioned. The first query is the slow one and takes about 20 seconds. The second query completes in an instant.

For what it's worth, the "OPTIMIZE FOR UNKNOWN" bit was also added recently because parameter sniffing was trashing certain cases.

Original query:

SELECT CASE
  WHEN EXISTS (SELECT 1 FROM zumero.dbf_1162761$z$rv$1257927703 rv INNER JOIN zumero.dbf_1162761$t$tx tx ON tx.txid=rv.txid WHERE tx.generation BETWEEN 1500 AND 2502)
  OR EXISTS (SELECT 1 FROM zumero.dbf_1162761$z$dd$1257927703 dd INNER JOIN zumero.dbf_1162761$t$tx tx ON tx.txid=dd.txid WHERE tx.generation BETWEEN 1500 AND 2502)
THEN 1 ELSE 0 END
OPTION (OPTIMIZE FOR UNKNOWN)

Original plan:

|--Compute Scalar(DEFINE:([Expr1006]=CASE WHEN [Expr1007] THEN (1) ELSE (0) END))
     |--Nested Loops(Left Semi Join, DEFINE:([Expr1007] = [PROBE VALUE]))
          |--Constant Scan
          |--Concatenation
               |--Nested Loops(Inner Join, WHERE:([scale].[zumero].[dbf_1162761$z$rv$1257927703].[txid] as [rv].[txid]=[scale].[zumero].[dbf_1162761$t$tx].[txid] as [tx].[txid]))
               |    |--Clustered Index Scan(OBJECT:([scale].[zumero].[dbf_1162761$z$rv$1257927703].[PK__dbf_1162__97770A2F62EEAE79] AS [rv]), WHERE:([scale].[zumero].[dbf_1162761$z$rv$1257927703].[txid] as [rv].[txid]>(0)))
               |    |--Index Seek(OBJECT:([scale].[zumero].[dbf_1162761$t$tx].[gendex] AS [tx]), SEEK:([tx].[generation] >= (1500) AND [tx].[generation] <= (2502)) ORDERED FORWARD)
               |--Nested Loops(Inner Join, OUTER REFERENCES:([tx].[txid]))
                    |--Clustered Index Scan(OBJECT:([scale].[zumero].[dbf_1162761$t$tx].[PK__dbf_1162__E3BA953EC2197789] AS [tx]),  WHERE:([scale].[zumero].[dbf_1162761$t$tx].[generation] as [tx].[generation]>=(1500) AND [scale].[zumero].[dbf_1162761$t$tx].[generation] as [tx].[generation]<=(2502)) ORDERED FORWARD)
                    |--Index Seek(OBJECT:([scale].[zumero].[dbf_1162761$z$dd$1257927703].[n$dbf_1162761$z$dd$txid$1257927703] AS [dd]), SEEK:([dd].[txid]=[scale].[zumero].[dbf_1162761$t$tx].[txid] as [tx].[txid]),  WHERE:([scale].[zumero].[dbf_1162761$z$dd$1257927703].[txid] as [dd].[txid]>(0)) ORDERED FORWARD)

Fixed query:

SELECT CASE
  WHEN EXISTS (SELECT 1 FROM zumero.dbf_1162761$z$dd$1257927703 dd INNER JOIN zumero.dbf_1162761$t$tx tx ON tx.txid=dd.txid WHERE tx.generation BETWEEN 1500 AND 2502)
  OR EXISTS (SELECT 1 FROM zumero.dbf_1162761$z$rv$1257927703 rv INNER JOIN zumero.dbf_1162761$t$tx tx ON tx.txid=rv.txid WHERE tx.generation BETWEEN 1500 AND 2502)
THEN 1 ELSE 0 END
OPTION (OPTIMIZE FOR UNKNOWN)

Fixed plan:

|--Compute Scalar(DEFINE:([Expr1006]=CASE WHEN [Expr1007] THEN (1) ELSE (0) END))
     |--Nested Loops(Left Semi Join, DEFINE:([Expr1007] = [PROBE VALUE]))
          |--Constant Scan
          |--Concatenation
               |--Nested Loops(Inner Join, OUTER REFERENCES:([tx].[txid]))
               |    |--Clustered Index Scan(OBJECT:([scale].[zumero].[dbf_1162761$t$tx].[PK__dbf_1162__E3BA953EC2197789] AS [tx]),  WHERE:([scale].[zumero].[dbf_1162761$t$tx].[generation] as [tx].[generation]>=(1500) AND [scale].[zumero].[dbf_1162761$t$tx].[generation] as [tx].[generation]<=(2502)) ORDERED FORWARD)
               |    |--Index Seek(OBJECT:([scale].[zumero].[dbf_1162761$z$dd$1257927703].[n$dbf_1162761$z$dd$txid$1257927703] AS [dd]), SEEK:([dd].[txid]=[scale].[zumero].[dbf_1162761$t$tx].[txid] as [tx].[txid]),  WHERE:([scale].[zumero].[dbf_1162761$z$dd$1257927703].[txid] as [dd].[txid]>(0)) ORDERED FORWARD)
               |--Nested Loops(Inner Join, WHERE:([scale].[zumero].[dbf_1162761$z$rv$1257927703].[txid] as [rv].[txid]=[scale].[zumero].[dbf_1162761$t$tx].[txid] as [tx].[txid]))
                    |--Clustered Index Scan(OBJECT:([scale].[zumero].[dbf_1162761$z$rv$1257927703].[PK__dbf_1162__97770A2F62EEAE79] AS [rv]), WHERE:([scale].[zumero].[dbf_1162761$z$rv$1257927703].[txid] as [rv].[txid]>(0)))
                    |--Index Seek(OBJECT:([scale].[zumero].[dbf_1162761$t$tx].[gendex] AS [tx]), SEEK:([tx].[generation] >= (1500) AND [tx].[generation] <= (2502)) ORDERED FORWARD)

Answer 1

As a general rule of thumb, SQL Server will execute the parts of a CASE statement in order but is free to reorder OR conditions. For some queries you can get consistently better performance by changing the order of the WHEN expressions inside a CASE statement. Sometimes you can also get better performance when changing the order of conditions in an OR statement, but it isn't guaranteed behavior.

It's probably best to walk through it with a simple example. I'm testing against SQL Server 2016 so it's possible that you won't get the exact same results on your machine, but as far as I know the same principles apply. First I'll put one million integers from 1 to 1000000 in two tables, one with a clustered index and one as a heap:

CREATE TABLE dbo.X_HEAP (ID INT NOT NULL, FLUFF VARCHAR(100));

INSERT INTO dbo.X_HEAP  WITH (TABLOCK)
SELECT TOP (1000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), REPLICATE('Z', 100)
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);

CREATE TABLE dbo.X_CI (ID INT NOT NULL, FLUFF VARCHAR(100), PRIMARY KEY (ID));

INSERT INTO dbo.X_CI  WITH (TABLOCK)
SELECT TOP (1000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), REPLICATE('Z', 100)
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);

Consider the following query:

SELECT CASE
  WHEN EXISTS (SELECT 1 FROM dbo.X_HEAP WHERE ID = 500000)
  OR EXISTS (SELECT 1 FROM dbo.X_CI WHERE ID = 500000)
THEN 1 ELSE 0 END;

We know that evaluating the subquery against X_CI will be much cheaper than the subquery against X_HEAP, especially when there isn't a matching row. If there isn't a matching row then we only need to do a few logical reads against the the table with a clustered index. However, we would need to scan all of the rows of the heap to know that there isn't a matching row. The optimizer knows this too. Broadly speaking, using a clustered index to look up one row is very cheap compared to scanning a table.

For this example data I would write the query like this:

SELECT CASE
  WHEN EXISTS (SELECT 1 FROM dbo.X_CI WHERE ID = 500000) THEN 1 
  WHEN EXISTS (SELECT 1 FROM dbo.X_HEAP WHERE ID = 500000) THEN 1 
ELSE 0 END;

That effectively forces SQL Server to run the subquery against the table with a clustered index first. Here are the results from SET STATISTICS IO, TIME ON:

Table 'X_CI'. Scan count 0, logical reads 3, physical reads 0

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

Looking at the query plan, if the seek at label 1 returns any data than the scan at label 2 isn't required and won't happen:

The following query is much less efficient:

SELECT CASE
  WHEN EXISTS (SELECT 1 FROM dbo.X_HEAP WHERE ID = 500000) THEN 1 
  WHEN EXISTS (SELECT 1 FROM dbo.X_CI WHERE ID = 500000) THEN 1 
ELSE 0 END
OPTION (MAXDOP 1);

Looking at the query plan, we see that the scan at label 2 always happens. If a row is found then the seek at label 1 is skipped. That isn't the order that we wanted:

The performance results back that up:

Table 'X_HEAP'. Scan count 1, logical reads 7247

SQL Server Execution Times: CPU time = 15 ms, elapsed time = 22 ms.

Going back to the original query, for this query I see the seek and the scan evaluated in the order that is good for performance:

SELECT CASE
  WHEN EXISTS (SELECT 1 FROM dbo.X_HEAP WHERE ID = 500000)
  OR EXISTS (SELECT 1 FROM dbo.X_CI WHERE ID = 500000)
THEN 1 ELSE 0 END;

And in this query they are evaluated in the opposite order:

SELECT CASE
  WHEN EXISTS (SELECT 1 FROM dbo.X_CI WHERE ID = 500000)
  OR EXISTS (SELECT 1 FROM dbo.X_HEAP WHERE ID = 500000)
THEN 1 ELSE 0 END;

However, unlike the previous pair of queries, there's nothing forcing the SQL Server query optimizer to evaluate one before the other. You should not rely on that behavior for anything important.

In conclusion, if you need one subquery to be evaluated before the other then use a CASE statement or some other method to force ordering. Otherwise feel free to order subqueries in an OR condition however you want, but know that there's no guarantee that the optimizer will execute them in the order as written.

Addendum:

A natural follow up question is what can you do if you want SQL Server to decide which query is cheaper and to execute that one first? All of the methods so far appear to be implemented by SQL Server in the order that the query is written, even if it's not guaranteed behavior for some of them.

Here is one option that appears to work for the simple demo tables:

SELECT CASE
  WHEN EXISTS (
    SELECT 1
    FROM (
        SELECT TOP 2 1 t
        FROM 
        (
            SELECT 1 ID

            UNION ALL

            SELECT TOP 1 ID 
            FROM dbo.X_HEAP 
            WHERE ID = 50000 
        ) h
        CROSS JOIN
        (
            SELECT 1 ID

            UNION ALL

            SELECT TOP 1 ID 
            FROM dbo.X_CI
            WHERE ID = 50000
        ) ci
    ) cnt
    HAVING COUNT(*) = 2
)
THEN 1 ELSE 0 END;

You can find a db fiddle demo here. Changing the order of the derived tables does not change the query plan. In both queries the X_HEAP table is not touched. In other words, the query optimizer appears to execute the cheaper query first. I can't recommend using something like this in production so it's here for mostly curiosity value. There may be a much simpler way to accomplish the same thing.