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.
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: 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