Usefulness of a multi-attribute index If an index has more than one attribute in it, is there any speed gained in a select statement whose where clause uses one of the attributes in the index?

For example, take a table T with an index on attributes a and b. Is the index useful for the query:

select * from T where a='foo'


I ask because the book I'm reading has the following statement which I have trouble understanding:


  If the key for the multiattribute index is really the concatenation of the attributes in some order, then we can even use this index to find all the tuples with a given value in the first of the attributes.
For example, take a table T with an index on attributes a and b. Is the index useful for the query:
select * from T where a='foo'


There are two questions there:

Can an index on (a,b) be used at all for this query?
The answer to that is generally yes. Maybe not all databases have that capacity, but most mainstream ones do AFAIK. Replace the select with select a,b from ... and the engine could not only use the index, but not access the actual table at all to answer the query.

Will the optimizer choose to use the index?
That will depend on the database system and how much information the optimizer has about the data. If it can determine that the first column is &quot;selective enough&quot;, then it will likely use it. If not, it likely won't.


Here's an illustration on Oracle XE 11g.
SQL&gt; create table T
  2  as select object_name a, rownum b, rownum c
  3  from all_objects;
Table created.
SQL&gt; create index T_ab on T(a,b);
Index created.

SQL&gt; exec dbms_stats.gather_table_stats(ownname=&gt;user, tabname=&gt;'T');
PL/SQL procedure successfully completed.

SQL&gt; set autotrace traceonly explain
SQL&gt; select * from T where a = 'foo';

Execution Plan
------------------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |      |     1 |    27 |     3   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| T    |     1 |    27 |     3   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN      | T_AB |     1 |       |     2   (0)| 00:00:01 |
------------------------------------------------------------------------------------

The all_objects view contains information about all the objects (tables, views, procedures, etc.) present in the database. The object_name fields isn't unique, but there aren't a lot of duplicates (in this database at least), so that leading field itself is very selective.
The cost of doing a range scan on the index, then looking up the estimated one row by rowid is going to be much less than doing a full table scan, so the optimizer takes that route.
This is a fairly usual situation and plan, you'll likely come across it a lot (or something similar on other database engines).
Now here's a different scenario where the optimizer can use a detailed picture of the actual contents of the columns to optimize things differently:
SQL&gt; create table Q
  2  as select 'a' a, rownum b, rownum c
  3  from all_objects;
Table created.
SQL&gt; create index Q_ab on Q(a,b);
Index created.

SQL&gt; exec dbms_stats.gather_table_stats(ownname=&gt;user, tabname=&gt;'Q');
PL/SQL procedure successfully completed.

SQL&gt; set autotrace traceonly explain
SQL&gt; select * from Q where a = 'a';

Execution Plan
--------------------------------------------------------------------------
| Id  | Operation     | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |  | 18085 |   176K|    15   (7)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| Q    | 18085 |   176K|    15   (7)| 00:00:01 |
--------------------------------------------------------------------------

SQL&gt; select * from Q where a = 'z';

Execution Plan
------------------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |      |     1 |    10 |     3   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| Q    |     1 |    10 |     3   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN      | Q_AB |     1 |       |     2   (0)| 00:00:01 |
------------------------------------------------------------------------------------

The table is intentionally completely skewed, the first column has 'a' as its only value. If the optimizer knows that, then it can opt for different paths based on the actual queried key value, as see above.
If 'a' is requested, using the index is a bad move - you'd need to traverse the whole index and the whole table to get all the rows, which is (potentially a lot) more costly than just scanning the table.
If the value requested is not 'a', scanning the index is much more efficient since it will likely return no rows.
Here's something perhaps a bit more surprising: the index on (a,b) can actually be used when the where clause filters on b only.
SQL&gt; select * from Q where b = 1000;

Execution Plan
------------------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |      |     1 |    10 |     3   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| Q    |     1 |    10 |     3   (0)| 00:00:01 |
|*  2 |   INDEX SKIP SCAN       | Q_AB |     1 |       |     2   (0)| 00:00:01 |
------------------------------------------------------------------------------------

This works because the leading column has few distinct values, but the second column is essentially unique. Think of it as the optimizer partitioning the index by the first column, then doing a binary search on each partition. That's going to be efficient if the number of partitions is small and the other criteria are fairly selective. (i.e. doesn't work for table T in this example.)