SQL Server – Why Execution Plan Chooses Scan Over Index?

An indexed column in InnoDB always has an additional key to the gen_clust_index (aka Clustered Index) attached to it. This would be traversed by the first query to get to row 4000000 in the order of the index. Since it is the only column being requested, access to the table is unnecessary.

The second query has to collect the non-indexed column from the table along with the indexed column into a temp table. The temp table is then sorted before presenting the non-indexed column as SELECT output.

Notice another contrast

• The table count is 4636881
• The EXPLAIN plan for the first query traversed 4000010 indexed_column keys. No need to read the last 636871 keys.
• The EXPLAIN plan for the second query traversed 4636881 rows ordered by indexed_column. For every row picking up the non-indexed column out of the table, the indexed column (already sorted by the index) is looked up and comes along for the ride. The tmp table gets ordered by the indexed column, and mysqld then dismisses the first 4000000 rows, leaving 10 rows. All that interaction between table and index just for 10 rows is the bottleneck.

COMMON THINGS

In both instances, the query specfies the number of rows to traverse. Since the number of rows in the table is 4636881, we should readily expect a full scan. The contrast becomes apparent when the MySQL Query Optimizer decides where to perform the full scan.

• The first query is referencing an indexed column only in the SELECT list and the WHERE clause. The MySQL Query Optimizer chooses to perform a full index scan with no need to contact the table since everything needed is in the index.
• The second query is referencing an indexed column in the WHERE clause. However, it must reach out the table to retrieve the corresponding non-indexed column. The MySQL Query Optmizer was tipped off by the query that it must not use the index becasue of the number of rows it was expected to read. As a rule of thumb for any RDBMS, if more than 5% of a table has to be read to fulfill a query, the MySQL Query Optimizer will just throw the index 'under the bus' and do a full table scan.

Doing the math, here is what MySQL Query optimizer computes:

• 5% of 4636881 is 231844
• The second query is commanded to read 4000000 rows, which is way higher than 231844
• MySQL Query Optimizer realizes there would be too much interaction between table (because of the non-indexed column) and index (because of the indexed column) to get the needed data. It decides to read the table only (because both the indexed and non-indexed columns are residing together in the table) rather than bounce back and forth between them.

In my honest opinion, with the row count of the table, the present indexes the table has, and the number of rows prescribed by the query, the MySQL Query Optimizer made the correct decision.

RECOMMENDATION

Create this index

ALTER TABLE `table` ADD INDEX mynewndx (indexed_column,some_other_column);

and your second query will never touch the table again going forward. The MySQL Query Optimizer will behave quite differently when it sees this new index.

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.