How do composite indexes work?

Question

I've created composite indexes (indices for you mathematical folk) on tables before with an assumption of how they worked. I was just curious if my assumption is correct or not.

I assume that when you list the order of columns for the index, you are also specifying how the indexes will be grouped. For instance, if you have columns a, b, and c, and you specify the index in that same order a ASC, b ASC, and c ASC then the resultant index will essentially be many indexes for each "group" in a.

Is this correct? If not, what will the resultant index actually look like?

Answer 1

Composite indexes work just like regular indexes, except they have multi-values keys.

If you define an index on the fields (a,b,c) , the records are sorted first on a, then b, then c.

Example:

| A | B | C |
-------------
| 1 | 2 | 3 |
| 1 | 4 | 2 |
| 1 | 4 | 4 |
| 2 | 3 | 5 |
| 2 | 4 | 4 |
| 2 | 4 | 5 |

Answer 2

Composite index is like a plain alphabet index in a dictionary, but covering two or more letters, like this:

AA - page 1
AB - page 12

etc.

Table rows are ordered first by the first column in the index, then by the second one etc.

It's usable when you search by both columns OR by first column. If your index is like this:

AA - page 1
AB - page 12
…
AZ - page 245
BA - page 246
…

you can use it for searching on 2 letters ( = 2 columns in a table), or like a plain index on one letter:

A - page 1
B - page 246
…

Note that in case of a dictionary, the pages themself are alphabetically ordered. That's an example of a CLUSTERED index.

In a plain, non-CLUSTERED index, the references to pages are ordered, like in a history book:

Gaul, Alesia: pages 12, 56, 78
Gaul, Augustodonum Aeduorum: page 145
…
Gaul, Vellaunodunum: page 24
Egypt, Alexandria: pages 56, 194, 213, 234, 267

Composite indexes may also be used when you ORDER BY two or more columns. In this case a DESC clause may come handy.

See this article in my blog about using DESC clause in a composite index:

• Descending indexes

Answer 3

The most common implementation of indices uses B-trees to allow somewhat rapid lookups, and also reasonably rapid range scans. It's too much to explain here, but here's the Wikipedia article on B-trees. And you are right, the first column you declare in the create index will be the high order column in the resulting B-tree.

A search on the high order column amounts to a range scan, and a B-tree index can be very useful for such a search. The easiest way to see this is by analogy with the old card catalogs you have in libraries that have not yet converted to on line catalogs.

If you are looking for all the cards for Authors whose last name is "Clemens", you just go to the author catalog, and very quickly find a drawer that says "CLE- CLI" on the front. That's the right drawer. Now you do a kind of informal binary search in that drawer to quickly find all the cards that say "Clemens, Roger", or "Clemens, Samuel" on them.

But suppose you want to find all the cards for the authors whose first name is "Samuel". Now you're up the creek, because those cards are not gathered together in one place in the Author catalog. A similar phenomenon happens with composite indices in a database.

Different DBMSes differ in how clever their optimizer is at detecting index range scans, and accurately estimating their cost. And not all indices are B-trees. You'll have to read the docs for your specific DBMS to get the real info.

Answer 4

No. Resultant index will be single index but with compound key.

KeyX = A,B,C,D; KeyY = 1,2,3,4;

Index KeyX, KeyY will be actually: A1,A2,A3,B1,B3,C3,C4,D2

So that in case you need to find something by KeyX and KeyY - that will be fast and will use single index. Something like SELECT ... WHERE KeyX = "B" AND KeyY = 3.

But it's important to understand: WHERE KeyX = ? requests will use that index, while WHERE KeyY = ? will NOT use such index at all.

Answer 5

Which queries can be sped up by composite indices or not

In general, a composite index can only significantly speed up inequalities on the last column.

E.g. a x-y composite B-tree index would:

• efficiently speed up:
  • x = 1 and y = 2: equalities in both columns
  • x = 1 and y > 2: equality on first column plus inequality on the second column
• very limited speed up:
  • x > 1 and y > 2: inequalities on both columns, including the first
  • x > 1 and y = 2: inequality on the first column
  • y > 2: this is equivalent to x > -infinity and y > 2, so it is just the worse case possible for the compound B-tree index. Note however, this case could be solved efficiently with a B-tree index.

If you need inequalities on both columns, then you should look into spatial indices such as R-trees, I've given more details at: What is a SPATIAL INDEX and when should I use it?

E.g. consider the following index:

x|y

1|1
1|2
1|3
1|4
1|5
1|6

2|2
2|2
2|2
2|3
2|3
2|3
2|4
2|4
2|4

4|2
4|2
4|2
4|3
4|3
4|3
4|4
4|4
4|4

5|3
5|4
5|5
5|6
5|7
5|8

An index can only speed up a query very significantly if all the rows are side to side in the index.

So if for example we want:

x = 5 and y > 4

we get the contiguous:

5|5
5|6
5|7
5|8

But if we want:

x > 0 and y > 4

the result set would not be contiguous, and would mean a bunch of useless scanning:

1|5
1|6
5|5
5|6
5|7
5|8