Help on understanding multiple columns on an index?

Question

Assume I have a table called "table" and I have 3 columns, a, b, and c.

What does it mean to have a non-clustered index on columns a,b?

Is a nonclustered index on columns a,b the same as a nonclustered index on columns b,a? (Note the order).

Also, Is a nonclustered index on column a the same as a nonclustered index on a,c?

I was looking at the website sqlserver performance and they had these dmv scripts where it would tell you if you had overlapping indexes and I believe it was saying that having an index on a is the same as a,b, so it is redundant. Is this true about indexes?

One last question is why is the clustered index put on the primary key. Most of the time the primary key is not queried against, so shouldn't the clustered index be on the most queried column. I am probably missing something here like having it on the primary key speeds up joins?

Great explanations. Should I turn this into a wiki and change the title index explanation?

Answer 1

This is turning into a more-general introduction to indexing, but I suspect you'll still find it useful. The first two paragraphs especially speak to your question.

Clustered vs Non-clustered

This refers to how the table is physically arranged on disk. A clustered index works by sorting the physical pages and rows in a table on disk based on the index definition. Non-clustered indexes use a separate location on disk to store a copy of the columns in the index (and only those columns), plus a pointer to the source records. For this reason, clustered indexes are often faster because they will always cover any data you need in the query. However, you only get one of them because otherwise you'd duplicate the entire table. It's also important to know that adding non-clustered indexes to a table actually slows down write operations like inserts and updates, because the database has to rebuild the index, or at least certain pages in the index.

Index Order

An index on (A,B) is not the same as on (B,A). If the first case, records in the index are ordered by column A first, and column B only effects the index order when you have duplicate values for A. Searching the index with a column B value only won't help you, because you still have to scan through every record in the index to find all your matching values in B. In the second case, the reverse happens: records are ordered by column B first, and column A only helps when you have duplicate values for A. Searching that index with a column A value only won't help you.

Covering Indexes

Sometimes a database can fulfill the requirements of a query entirely from an index. In this case, the index is said to be a "covering" index for that query. This is advantageous because indexes are often cached in memory, and so the database may not have to go do disk at all. To understand this, imagine an index on (A,B) where there are very few duplicate values for A. Including A in the index seems wasteful, unless you have a query that runs often that looks for a particular value of A and also needs B. This index will now save a lot work going back to the original table to retrieve B.

Selectivity

Selectivity is a value from 0 to 1 (often expressed as a percentage) that tells you how unique each value in an index is. A selectivity of 1 or 100% means there are no duplicates. A selectivity of 0 means there is only one value in the column. Generally, a higher selectivity (approaching 1) is better for indexes.

To demonstrate this, think about what would happen with a low-selectivity index. For example, you try to speed up a query by adding an index to a bit column in a table with 10000 records. In this case (assuming uniform distribution), the selectivity is .5. You run your query, and the index returns 5000 records. But each of those records still has to go back to the original table, and since the index order doesn't match the table order it would have to do a lot of separate look-ups into the table. Instead, it's likely faster to just scan through the entire table start to finish to retrieve the needed data.

Selectivity explains why you would want to cluster on the primary key. Since the clustered index tells the database how to order the table, going for anything less than 100% selectivity here means a query will have to scan the table more often. Clustering on the primary key gives you perfect selectivity. And since this primary key is often used as the record pointer in other indexes, you want to keep it as small as possible (ie, an integer identity column).

There's a good article on the selectivity and indexing here:
http://www.akadia.com/services/ora_index_selectivity.html

Sargable

This refers to whether the database is able to use a particular filter with an index.

As we have shown, indexes normally work by first sorting the data into a specific order, so that lookups into that index can use something efficient like a tree-based search rather than a slower linear search. Anything that can't be effectively compared with sorted data can't be used with an index. A good example is the LIKE operator. This is sargable:

SELECT * FROM [Table] WHERE [Column] LIKE @Value + '%'

but this is not sargable:

SELECT * FROM [Table] WHERE [Column] LIKE '%' + @Value + '%'

Some other things that can make a filter un-sargable are non-deterministic functions (and there are more of those than you think).

Per-Column Indexes

A common mistake I've seen is to have a separate index for each column in the table. For example, someone will take a table with columns (A,B,C,D) and create four separate indexes, one each for A, B, C, D, believing they have now indexed every column and so every query should be fast. In fact, this is rarely helpful for reasons I hope I've already explained, and will often make things worse rather than better because the database will now need to update these indexes for every change to the data.

Answer 2

A non-clustered index on (a, b) is a "copy" of a part of the table whose rows are sorted on a then on b and contain the reference to the original row.

It helps to run the queries like this:

SELECT  *
FROM    mytable
WHERE   a = @A
        AND b = @B

, this:

SELECT  *
FROM    mytable
ORDER BY
        a, b

, this:

SELECT  *
FROM    mytable
WHERE   a = @A
ORDER BY
        b

and many others.

For instance, we have a table like this:

#       col1    col2    col3
1       1       1       1
2       1       4       8
3       7       2       3
4       3       3       9
5       8       9       4
6       2       2       7
7       5       3       5
8       3       9       4

If we create an index on (col2, col3), it will contain the following data:

col2    col3    #
1       1       1
2       3       3
2       7       6
3       5       7
3       9       4
4       8       2
9       4       5
9       4       8

, i. e. sorted first on col2, then on col3, then on the reference to the row.

It's easy to see that this index is an index on col2 just as well (sorting on (col2, col3) implies sorting on col2 alone).

Order matters, so if we create an index on (col3, col2), the rows will be sorted differently:

col2    col3    #
1       1       1
2       3       3
9       4       5
9       4       8
3       5       7
2       7       6
4       8       2
3       9       4

This index is an index on col3 too.

If we want to find the rows within a certain range of (col2, col3) we just take a slice from the ordered data:

SELECT  col2, col3
FROM    mytable
WHERE   col2 BETWEEN 2 AND 3

col2    col3    #
1       1       1
----
2       3       3
2       7       6
3       5       7
3       9       4
----
4       8       2
9       4       5
9       4       8

Easy to see that we cannot take this slice on col3 using this index, since col3 is not ordered by itself.

The "reference" mentioned above is a RID of the row (a pointer to the place in the tablespace), if the table is non-clustered itself, or the value of the table's cluster key if the table is clustered.

A clustered index does not create a shadow copy of the values. Instead, it rearranges the tables rows themselves.

If you create a clustered index on (col2, col3) above, it will just rearrange the table rows:

#       col1    col2    col3
1       1       1       1
3       7       2       3
6       2       2       7
7       5       3       5
4       3       3       9
2       1       4       8
5       8       9       4
8       3       9       4

Clustered or non-clustered, therefore, is a storage method rather than an index.

In Oracle, this is called index-organized table (rows are sorted), as opposed to a heap-organized table (rows are not sorted).