Implement Index Skip Scan - by xor88

Status : 

  Won't Fix<br /><br />
		Due to several factors the product team decided to focus its efforts on other items.<br /><br />
		A more detailed explanation for the resolution of this particular item may have been provided in the comments section.

Sign in
to vote
ID 695044 Comments
Status Closed Workarounds
Type Suggestion Repros 0
Opened 10/15/2011 7:28:15 AM
Access Restriction Public


Lets say we have a table (ID, Gender, FirstName) and we define an index (Gender, FirstName). Where query for "where FirstName = 'ABC'".

Currently, this index can only be used for an index scan, not for a seek. However, SQL Server could use a so called skip scan, which exists in Oracle. It works like this:

1. seek to the very first row in the index. Remember its "Gender" value in a variable called @current.
2. Seek forward with the predicate "where Gender = @current and FirstName = 'ABC'". Return all rows.
3. See forward with the predicate "where Gender > @current" and store the new Gender value in @current.
4. Go to 2.

Using this algorithm, we can skip over the first indexed column, if it has low cardinality.

Benefits are:
1. Every multi-column index can be used to accelerate more queries before.
2. Existing queries will run faster just by installing the new version.
3. This eases migration from Oracle to SQL Server.
4. Can be used to very efficiently compute a distinct or group-by.


A skip scan is currently only possible on the partition column:

Ken Waltrop speaks about this issue:

Sign in to post a comment.
Posted by Daniel Adeniji on 3/23/2013 at 9:36 AM
I think each of us has ran into this problem a few times. And, we have solved it in few different ways:

a) Adding a new index
b) Changed the query to help it towards our preferred existing index
c) Added additional code to short-circuit the sql

Admittedly, this is a good Oracle Lead to follow...Later down the Engineering path it will redeemably open up other optimization paths.
Posted by Love Tech that works on 3/15/2013 at 2:46 AM
This isn't a problem when you write your own sql, as you can do a union.

However, when trying to optimise an MSCRM which ends up index scanning half a table on a non predictable basis, this would be invaluable, although I'd go further, and offer a multi-dimensional skip scan, say three deep.

eg. Select A from B where (C = 3 Or C = 5) And (D = 5 And E = 6)

plus Select A from B where (C = 3 Or C = 5) And (D = 7 or D = 9) And (E = 6 Or E = 11) -- this projects into an 8 way union, and with a three deep skip scan would cover most eventualities?

Or am I misunderstanding?

Posted by xor88 on 7/9/2012 at 12:00 PM
As the official documentation states, the "skip scan" algorithm is already partially implemented in SQL Server. Reference: I would be incredibly valuable to existing and new databases if the algorithm would be extended to all tables.
Posted by xor88 on 6/7/2012 at 1:45 PM
Joe Chang did an interesting blog post about the benefits of skip scans: I'm linking to it because it contains a (nasty) workaround. It would be so much nicer to have this capability baked in the product and always enabled.
Posted by xor88 on 10/17/2011 at 4:09 PM
I understand. Thanks!
Posted by Microsoft on 10/17/2011 at 2:58 PM
This is a good feedback, and we will certainly look at it for next releases, but given how close Denali is, we will not be able to fit this into this upcoming release by any means.