Proper Index for WHERE X <> 1 AND Y <> 1 ORDER BY Z

Question

I have a relatively large table that is accessed in exactly one way, by exactly one query (on the read side).

The query filters the table by two columns (both bit), and sorts by a third column (an integer). Note that the query names the columns (it doesn't actually use "*"). The "TOP 1000" is intentional and is part of the production query:

The query is generated--not sure why it generates the way it does.

SELECT TOP 1000
     *
FROM
     MyTable m
WHERE
     m.IsFlag1 != 1
     AND m.IsFlag2 != 1
ORDER BY
     m.SomeId

I have a covering index, with the main columns being IsFlag1 and IsFlag2.

The execution plan shows and Index seek on this index, and then a sort. The sort takes up 97% of the cost of the query according to the execution plan.

I tried adding SomeId as a main column of the index (the third column), but the execution plan remained the same.

I then tried adding a covering index using only SomeId as a main column, leaving the original index in place. The execution plan then does an index scan on the new query, and the operator cost is significantly lower (and is functionally much faster).

All that said, I'd like to optimize this query as much as possible. Is there a way to modify the index so that it simply does a seek?

Answer 1

In general it is not possible to use an index seek on a condition x <> 1 and y <> 1.

With an index on x,y the best you can do is convert it into two range seeks (x < 1 and x > 1) with a residual predicate on y <> 1 (and this wouldn't be able to use additional index key columns to avoid a sort)

For a bit column as it can only have three values. 0, 1, NULL logically WHERE bit_column <> 1 is equivalent to WHERE bit_column = 0 but seems SQL Server doesn't take advantage of that here and convert the <> to = conditions for you.

Adding a couple of check constraints does the job though even though these are apparently redundant in that they don't actually restrict the allowable values for the datatype in any way (for NULL if a check constraint evaluates to UNKNOWN it counts as passing)

CREATE TABLE MyTable
  (
     Foo     INT,
     IsFlag1 BIT NULL CHECK (IsFlag1 IN (0, 1)),
     IsFlag2 BIT NULL CHECK (IsFlag2 IN (0, 1)),
     SomeId  INT
  );

CREATE NONCLUSTERED INDEX ix
  ON MyTable(IsFlag1, IsFlag2, SomeId)
  INCLUDE (Foo); 

The plan now does show a seek on IsFlag1 = 0 AND IsFlag2 = 0

Or alternatively this filtered index also avoids the need for a SORT

CREATE NONCLUSTERED INDEX ix 
           ON MyTable(SomeId) 
           INCLUDE (Foo,IsFlag1, IsFlag2) 
           WHERE IsFlag1 != 1 and IsFlag2 != 1

It does a scan of the filtered index (the qualifying rows ordered by SomeId) with a TOP to stop scanning after the 1,000 rows are retrieved. IsFlag1, IsFlag2 are INCLUDE-d in the index to avoid an unnecessary look up that occurs without this.

Answer 2

A filtered index will allow you to eliminate the sort operator in your query.

CREATE INDEX IX_myTable_SomeId_filtered on myTable (SomeId) where (    IsFlag1 <> 1
AND IsFlag2 <> 1 )

The index will only contains rows that match your query, and they'll be stored in the correct order to avoid the sort.