Home Dashboard Directory Help
Search

Implement Index Skip Scan by xor88


Status: 

Active


28
0
Sign in
to vote
Type: Suggestion
ID: 695044
Opened: 10/15/2011 7:28:15 AM
Access Restriction: Public
1
Workaround(s)
view

Description

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.

References:

http://stackoverflow.com/questions/1615893/does-sql-server-jump-leaves-when-using-a-composite-clustered-index
http://download.oracle.com/docs/cd/B10501_01/server.920/a96533/optimops.htm#51553
http://www.oracle-base.com/articles/9i/IndexSkipScanning.php

A skip scan is currently only possible on the partition column: http://blogs.msdn.com/b/craigfr/archive/2008/08/05/partitioned-indexes-in-sql-server-2008.aspx

Ken Waltrop speaks about this issue: http://social.msdn.microsoft.com/Forums/en-US/transactsql/thread/48de15ad-f8e9-4930-9f40-ca74946bc401/#44a72837-a114-4188-b3a3-7900e2a947ca

Details
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: http://msdn.microsoft.com/en-us/library/ms345599(SQL.105).aspx 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: http://sqlblog.com/blogs/joe_chang/archive/2011/06/13/oracle-index-skip-scan.aspx 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.
Sign in to post a workaround.
Posted by gfody on 6/26/2014 at 5:53 PM
As a workaround you can specify a criteria on the other column that will just match everything. For example "where FirstName = 'ABC' and Gender >= ''" - with the index (Gender, FirstName) you will get a seek plan.