Usefulness of a multi-attribute index

Question

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.

Answer 1

Yes, but it depends on which index key you search by.

Think of it like one of those old "white pages" phone books. In a phone book, people are ordered on the pages in the order LastName, FirstName. That means there are two components to the phone book's index.

If you're looking for all of the people with the last name of "Smith", you just find the first "Smith" (easy to do since it's in order), then keep reading until you see someone who's not a "Smith".

But if you're looking for all of people with the name "William", you're going to have a tough time. You'll have to scan each and every entry in the phone book, collecting answers, even though FirstName is in the phone book's "index".

Database indexes (conceptually) work the exact same way.

Answer 2

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 "selective enough", then it will likely use it. If not, it likely won't.

Here's an illustration on Oracle XE 11g.

SQL> create table T
  2  as select object_name a, rownum b, rownum c
  3  from all_objects;
Table created.
SQL> create index T_ab on T(a,b);
Index created.

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

SQL> set autotrace traceonly explain
SQL> 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> create table Q
  2  as select 'a' a, rownum b, rownum c
  3  from all_objects;
Table created.
SQL> create index Q_ab on Q(a,b);
Index created.

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

SQL> set autotrace traceonly explain
SQL> 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> 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> 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.)

Answer 3

PostgreSQL experience.

We have table with 3 columns

table test with columns
 id, first, second

then we have two indexes

first_second_idx (first, second)
first_idx (first)

then if we use statement (1)

 select * from test where first = 'whatever';

query planner should use index first_idx ( 'whatever' value is for example 5% of all records). It's faster because index is smaller so there is less read.

For query (2)

select * from test where first = 'whatever' and second = 'something'

it's obvious that index first_second_idx will be used

But if we remove first_idx in both queries planer should use first_second_idx.

If there is no index for this table full table scan will be triggered.

So if you have both types of queries from application:

1. use only first_second_idx if
   • speed of (1) query is gratifying
   • there is a lot of inserts updates and second index will slow those operations
   • table test have a lot of records and disc space and/or memory (there is always used more memory when read from both indexes) is important
2. use both indexes if
   • speed for both queries is crucial
   • speed of insert update is not so important
   • disc space and memory is not so important