How much does an index need to narrow the results of a search in order to be useful?

Question

How much does an index need to narrow the results of a search in order to be useful in speeding up queries?

Some examples all across the spectrum:

• A column for storing true/false values obviously has only two unique values.
• A 'last name' column probably has many unique values (although it may not).
• A primary key column has all unique values.

I think that the goal of an index is to quickly narrow a search to a few rows, and that therefore, the last case is the best, the second is OK, and the first is useless.

Am I correct? If so, roughly where is the line of usefulness? For example, if an index can narrow the results to 1% of the rows, is that useful? What about 10% or 25%?

Answer 1

The diversity of a column's data is known as selectivity. Selectivity is useful to know when determining whether an index will be useful, but it is not the only thing that determines the speed benefit. Other factors include how fast the storage the index is on compared to the table, how much of the table/index is already cached, how large the index is in comparison to the table, and several other things.

Knowing the data-type of the column does not necessarily help us determine how selective an index on the column will be. Even a column constrained to two values might use those values for only a few rows and have the remainder NULL. On the other hand, a column that could have many distinct values could have the same value in every single row. Even with your id column where all the rows would have unique values, if you are searching for rows with an id >= 10, the index probably wouldn't be useful even though it is highly selective.

You can't use selectivity alone to determine whether an index will be useful or not because even if it returns 100% of the rows, if the index includes all the data necessary for the query it will be faster than using the table. On the other hand, for a small table it may be faster to query the whole thing even if the row being sought only represents 1% of the total.

Determining what indexes should be created is less about looking at the table structure than it is looking at the important queries and what data they need to retrieve.

Answer 2

In general, yes, you are correct. A b-tree index is more useful when it allows you to identify a relatively small fraction of the rows in the table that need to be returned.

As for what that cutoff is, it depends. Almost any modern enterprise relational database is going to have a cost-based optimizer that tries to work out the best query plan given a bunch of statistics about the distribution of data, the relative expense of different operations, etc. Different databases and different versions of the same database are going to rely on a pretty wide range of settings, statistics, and other bits of information in order to figure out where that cutoff is. My rough guess would be that when you're retrieving more than 10-15% of the rows that you're probably in the range where a table scan will be more efficient. But it is easy enough to come up with cases where you're better off with a table scan if the index only gets you 5% of the data or that you're better off using an index to retrieve 25% of the data.

Answer 3

Depends on the type of index! I presume you were thinking of an "ordinary" binary tree index. These are typically used by "planners" when maybe 10% of the rows of the table are expected to be retrieved. Why such a low percentage? Don't forget that the DBMS has to retrieve index blocks, not rows, and much of the data retrieved won't be scanned for the row being looked for (ie overhead). Also, an index itself uses space, it's certainly nowhere near a "free" or even constant-time (and hence space) operation.

See http://docs.oracle.com/cd/B28359_01/server.111/b28274/optimops.htm#autoId25 for a good overview of the considerations of the "planner" (at least, the ones thought of in a reasonably current version of Oracle).

The speed of certain disk-based operations impacts Oracle's decision to use either an index scan or a full-table scan too.

And in my answer so far I've assumed that we're talking about an ordinary index lookup for a value. There are many other index scans used in Oracle for example (see the link I provided).

Then there are also bitmap indexes: these store a bitmap (ie 0's and 1's, 1 for each row) for each unique value. These are ideal for booleans and other low cardinality columns (but can also be useful in other cases as some papers have shown).

The downside to bitmap indexes is that they are very expensive to update and hence most useful for mostly read-only databases (like decision support systems, data warehouses and the like).

Answer 4

Good answers, both. Most database engines will optimize queries to minimize disk I/O, so if an index doesn't narrow the choices to a rather small percentage of the table, the query optimizer will use a full table scan instead. This percentage varies between DB engines, but is usually on the order of 2-10%.

Binary columns do not generally make a good index used alone, but may be used in conjunction with another column.

An "id" column (for those who may not be familiar with Ruby/Rails, consider this an auto-incremented, unique, primary key integer column) most often MUST be indexed due to the nature of its use. If it is declared as the primary key, you don't need to declare an index ... it gets one anyway.

Varchar columns may or may not make a good index, depending on the contents. Many DB engines will allow you to index only the first columns of a varchar. Good example: first 8 of the last name plus first 4 of the first name.

There are exceptions to most rules; read up on the particular database you're using.

Answer 5

I recently took a SQL Skills immersion (IE1) event by Paul Randall and Kimberly Tripp, Kimberly being the authority on indexing and SQL Server internals.

I can't tell you theoretically when it would be ideal to use a index, I'm sure a math model could be created to tell you that. In practical terms within the SQL Server, In their demonstrations a index was used if it could avoid scanning 90% of the table. The results varied though. Sometimes it would use a table scan at a much lower percentage. It had to do with carnality in your statistics as well.

I can pull up the info and review it if you think it'll be useful to you.