CSE Roadmap

Core tier · about 2 hours · 6 parts

Part 4 of 6 · 2 min read

Why an index can still be slow

Think of an index that only narrows the search down to one department of a large building. It quickly tells you which floor to search. But you still have to walk into every single office on that floor and check each one individually for what you actually want.

In plain words: An index built on one set of columns may cover only part of a query's WHERE clause, applying that part during the index lookup while leaving the rest to be checked only after each candidate row is fetched from the table. If that index lookup alone matches a large number of rows, every one of them must be individually fetched from the table before the remaining filter can even be checked, and fetching many rows one at a time is expensive compared to a full scan's large sequential reads. The database only realizes this is the better plan if its statistics about the data's actual distribution are accurate; with stale or missing statistics, the optimizer can badly underestimate how many rows an index lookup will return and wrongly prefer the slower indexed plan.

A worked example. A query filtering on last_name and subsidiary_id uses an index covering only subsidiary_id. The index range scan returns every employee in that subsidiary, a thousand rows for a large subsidiary, each one individually fetched from the table before last_name can be checked, making the indexed plan slower overall than simply scanning the whole table once.

The key lines.

Example 2.1. Execution Plan with Revised Primary Key Index
---------------------------------------------------------------
|Id |Operation                   | Name         | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT            |              |    1 |   30 |
|*1 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES    |    1 |   30 |
|*2 | INDEX RANGE SCAN           | EMPLOYEES_PK | 40   |    2 |
---------------------------------------------------------------
Predicate Information:
  1 - filter("LAST_NAME"='WINAND')
  2 - access("SUBSIDIARY_ID"=30)

Statistics (query optimizer), selectivity

Statistics are the stored facts about a table's and index's actual data, such as distinct value counts and data distribution, that the optimizer relies on to estimate how many rows a filter will match. Selectivity is how large a share of a table's rows a given filter condition is expected to match; a highly selective filter matches few rows, a poorly selective one matches many.

Example: in the plan above, the index range scan's predicate shows it applying only subsidiary_id, leaving last_name to be checked afterward against every one of the fetched rows.