how does multiple column index work in details

Question

if we have a table T1 with columns A,B,C,D,E and an index ( A,B,C) built for it

if we a SQL query joining on columns A,B or A,B,C or A, this index can still be used, but if the query is joining on B or C or B,C the index is totally useless

I know indexes are often implemented BTree , I want to know how is the implementation detail related with this ?

• user1822: All you ever wanted to know about indexes: use-the-index-luke.com
• zinking: use-the-index-luke.com/sql/where-clause this is indeed a very good book
• zinking: use-the-index-luke.com/sql/where-clause/the-equals-operator/… this is the detailed explaination on this topic.

Answer 1

This is not necessarily the case. Oracle, for example, has an access path known as an "index skip scan". See http://docs.oracle.com/cd/B10501_01/server.920/a96533/optimops.htm#51553

Basically, if there are few distinct values in column A, and the query restricts on column B (and optionally, column C), the executor will substitute each of the distinct values of column A in turn and probe the index for the supplied value of column B (and optionally, column C).

Postgresql can do something similar, but it is still labelled as an "index scan", see Working of indexes in PostgreSQL

• ypercubeᵀᴹ: There is a Connect item that one can vote for implementing this in SQL-Server: MS Connect: Implement Index Skip Scan
• zinking: I think this states that my assertion is not necessarily true. but without considering this, how does DB apply INDEX ABC on column AB join ? is that by comparing only the AB part of the index key ?