The labs on this site need JavaScript to run. The same content is written out below.

Learn › Database › Indexes and execution plans

Indexes and full table scans

Why is the index not used even though it exists?

There are two ways to find the rows that match a condition: read the table from beginning to end (a full table scan), or find the positions in an index and read only those rows. Which one is cheaper depends on the share of rows the condition matches, and the optimizer chooses by looking at statistics.

Conceptual model · A cost model fitted to a rule of thumb

Concepts in this lab

Index

A data structure that keeps the values of specific columns separately, in sorted form, so that the wanted rows of a table can be found quickly. Without one, the whole table must be read to find the rows that match a condition. Reads get faster, but it must also be updated every time data is inserted, updated, or deleted, so it costs write performance and storage space.

B-tree index

The index structure that most relational databases use by default. It is a balanced tree that keeps values sorted, and each node holds many keys, so the height of the tree is low. You can find a value by going down only a few levels from the root. Because the values are sorted, it is used not only for equality lookups but also for range lookups and sorting.

Full table scan

A way of finding the rows that match a condition by reading every row of the table from beginning to end. It is chosen when no index can be used for the condition, or when an index exists but the optimizer judges that reading everything is better because too many rows match the condition. When it is used to find a few rows in a large table, it causes performance problems.

Query execution plan (EXPLAIN)

The plan that the database decides on for how to run a query. It shows which indexes are used, in what order the tables are joined, and how many rows the database expects to read. You view it by putting EXPLAIN in front of the query, and it is the starting point for finding the cause when a query is slow.

Optimizer

The database component that chooses, among the several ways a SQL statement can be executed, the one that is expected to cost the least. It decides based on statistics such as the number of rows in a table and the distribution of values. If the statistics differ from the real data, it can choose an inefficient way.

Cardinality and selectivity

Cardinality is the number of distinct values in a column. The more distinct values there are (for example, a national ID number or an email address), the fewer rows one condition leaves and the more effective an index is. The fewer kinds of values there are (for example, gender), the more rows match a condition and the less effective an index is. Selectivity is the cardinality divided by the number of rows in the table; the closer it is to 1, the better a single condition narrows down the rows.

Try these

• Default settings — Of 100,000 rows, only 0.1% match the condition. The index reads only 100 rows.
• Same query, no index — To find 100 rows, it reads all 100,000 rows.
• When half the rows match — Even with an index, the optimizer chooses a full table scan.
• Forcing the index anyway — It actually costs more.
• Near the boundary: 20% and 30% — Run it at 20%, then change to 30% and compare.
• No index on 10,000,000 rows — It gets slower in proportion to the extra rows.

Running with the default settings

1. The query arrives. The optimizer looks at statistics to decide how to run it. The table has about 100,000 rows, and the optimizer expects the condition status = 'CANCELED' to match about 100 rows (0.1%).
2. Method 1, full table scan: read the table from beginning to end, in order, and check the condition on each row. It reads 100,000 rows. Reading in order is cheap per row. Estimated cost: 100,000.
3. Method 2, index: find the positions of the 100 matching entries in the index, then go to the table one entry at a time to read the other columns. It reads fewer rows, but each one means jumping to a different place in the table, so the cost per row is higher (assumed here to be 4 times as much). Estimated cost: 402.
4. The optimizer chooses the method with the lower cost: the index.
5. Starting from the root of the index (a B-tree), it goes down 2 levels to find the first position that matches the condition. At each level, it narrows the range among the sorted keys. Even with 100,000 rows, 2 levels are enough to get there.
6. From that position, it reads along the index to collect the 100 matching entries, and for each entry it reads the row from the table. The rows that do not match the condition were never read.

Result of this run

• The lower the share of matching rows (the better the selectivity), the greater the benefit of the index. A full table scan would have cost 100,000, about 249 times as much.

Code

CREATE INDEX idx_orders_status ON orders (status);

SELECT *
  FROM orders
 WHERE status = 'CANCELED';   -- 0.1% of all rows

Assumptions of this model

The costs are a simple model made to show the relationship. The cost of reading one row in order is assumed to be 1, and the cost of reading one row from the table through the index is assumed to be 4. With this ratio, a full table scan becomes better when more than about 25% of the rows match, which is fitted to the rule of thumb often given in books about MySQL that a full table scan is better when more than 20 to 25% of all rows match. The real optimizer calculates in more detail, using the number of pages, the share that is already in memory, column statistics, and so on, so the boundary differs from case to case. The number of B-tree levels is calculated by assuming that a node holds 500 keys. If you select only columns that are in the index instead of SELECT *, the query does not need to go to the table, and the calculation changes. This is covered in the "Composite and covering indexes" lab.

Previous lab: Binary search and B-trees · Next lab: Composite and covering indexes