MySQL Index Selectivity and Cardinality Explained

An index is useful when it helps MySQL skip most of the table. How good a column is for that is its selectivity.

Text

PLAIN

selectivity = number of distinct values / number of rows

A column with unique values (email, order number): selectivity 1.0. A lookup returns one row. Excellent.
A column with few values (is_active with 2 values, status with 4): low selectivity. A lookup returns a large share of the table.

query.sql

SQL

SET SESSION cte_max_recursion_depth = 100000;

CREATE TABLE users (
    id INT AUTO_INCREMENT PRIMARY KEY,
    email VARCHAR(60) NOT NULL,
    country CHAR(2) NOT NULL,
    is_active TINYINT(1) NOT NULL,
    plan VARCHAR(10) NOT NULL
);
INSERT INTO users (email, country, is_active, plan)
WITH RECURSIVE n AS (SELECT 1 AS i UNION ALL SELECT i + 1 FROM n WHERE i < 40000)
SELECT CONCAT('user', i, '@example.com'), ELT(1 + MOD(i, 6), 'IN', 'US', 'DE', 'BR', 'GB', 'JP'), IF(MOD(i, 50) = 0, 0, 1), IF(MOD(i, 100) = 0, 'pro', 'free') FROM n;

Measure the selectivity

query.sql

SQL

SELECT COUNT(*) AS total_rows,
       COUNT(DISTINCT email)     AS distinct_emails,
       COUNT(DISTINCT country)   AS distinct_countries,
       COUNT(DISTINCT is_active) AS distinct_is_active,
       COUNT(DISTINCT plan)      AS distinct_plans
FROM users;

Output

OUTPUT

+------------+-----------------+--------------------+--------------------+----------------+
| total_rows | distinct_emails | distinct_countries | distinct_is_active | distinct_plans |
+------------+-----------------+--------------------+--------------------+----------------+
|      40000 |           40000 |                  6 |                  2 |              2 |
+------------+-----------------+--------------------+--------------------+----------------+
1 row in set

email: 40,000 distinct in 40,000 rows. Selectivity 1.0.
country: 6 distinct values. About 6,700 rows per country.
is_active and plan: 2 values each.

Low selectivity: little benefit, real cost

query.sql

SQL

CREATE INDEX idx_active ON users (is_active);
CREATE INDEX idx_country ON users (country);
ANALYZE TABLE users;

SELECT is_active, COUNT(*) AS users FROM users GROUP BY is_active ORDER BY is_active;

Output

OUTPUT

+-------------+---------+----------+----------+
| Table       | Op      | Msg_type | Msg_text |
+-------------+---------+----------+----------+
| learn.users | analyze | status   | OK       |
+-------------+---------+----------+----------+
1 row in set

+-----------+-------+
| is_active | users |
+-----------+-------+
|         0 |   800 |
|         1 | 39200 |
+-----------+-------+
2 rows in set

98 percent of the users are active. Now look at what MySQL plans for the common and for the rare value:

query.sql

SQL

1
2

EXPLAIN FORMAT=TRADITIONAL SELECT id, email FROM users WHERE is_active = 1;
EXPLAIN FORMAT=TRADITIONAL SELECT id, email FROM users WHERE is_active = 0;

Output

OUTPUT

+----+-------------+-------+------------+------+---------------+------------+---------+-------+-------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key        | key_len | ref   | rows  | filtered | Extra |
+----+-------------+-------+------------+------+---------------+------------+---------+-------+-------+----------+-------+
|  1 | SIMPLE      | users | NULL       | ref  | idx_active    | idx_active | 1       | const | 19613 |   100.00 | NULL  |
+----+-------------+-------+------------+------+---------------+------------+---------+-------+-------+----------+-------+
1 row in set

+----+-------------+-------+------------+------+---------------+------------+---------+-------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key        | key_len | ref   | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+------------+---------+-------+------+----------+-------+
|  1 | SIMPLE      | users | NULL       | ref  | idx_active    | idx_active | 1       | const |  800 |   100.00 | NULL  |
+----+-------------+-------+------------+------+---------------+------------+---------+-------+------+----------+-------+
1 row in set

MySQL uses idx_active for both. For the common value its estimate (rows) is only about 20,000, but the truth is 39,200 rows, because the statistics of an index cannot see how skewed the values are. Using the index for 98 percent of the table means 39,200 index entries, each followed by a lookup of the full row. That is more work than one straight scan. EXPLAIN ANALYZE shows the real work, and IGNORE INDEX shows the alternative:

query.sql

SQL

1
2

EXPLAIN ANALYZE SELECT id, email FROM users WHERE is_active = 1;
EXPLAIN ANALYZE SELECT id, email FROM users IGNORE INDEX (idx_active) WHERE is_active = 1;

Output

OUTPUT

+-------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                       |
+-------------------------------------------------------------------------------------------------------------------------------+
| -> Index lookup on users using idx_active (is_active=1)  (cost=2082 rows=19613) (actual time=0.629..58.5 rows=39200 loops=1)
 |
+-------------------------------------------------------------------------------------------------------------------------------+
1 row in set

+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN                                                                                                                                                                                                |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Filter: (users.is_active = 1)  (cost=3963 rows=19613) (actual time=0.09..12.6 rows=39200 loops=1)
    -> Table scan on users  (cost=3963 rows=39226) (actual time=0.0888..9.92 rows=40000 loops=1)
 |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set

Compare the actual time and rows of the two plans (the numbers differ on every run, so this block is not compared). For this query the index gives no gain and costs space and write time. The rule: an index on a column with very few values only pays off when you search for the rare value.

The rare value is a different story

For is_active = 0 the index finds 800 rows (2 percent) directly: that is a real saving, and the plan above shows an accurate rows: 800. If you only ever look for the rare value, a small index on that column can be worth having. The overall number of distinct values hides this. The real measure is: “what fraction of the table does this query’s condition return?” A small fraction (a few percent at most) is where an index helps.

Cardinality and statistics

SHOW INDEX reports an estimated cardinality (the number of distinct values). The optimizer uses this to guess how many rows a condition returns, and to decide the join order and which index to use.

query.sql

SQL

SELECT index_name, column_name, cardinality
FROM information_schema.statistics
WHERE table_schema = 'learn' AND table_name = 'users'
ORDER BY index_name;

Output

OUTPUT

+-------------+-------------+-------------+
| INDEX_NAME  | COLUMN_NAME | CARDINALITY |
+-------------+-------------+-------------+
| idx_active  | is_active   |           2 |
| idx_country | country     |           6 |
| PRIMARY     | id          |       39226 |
+-------------+-------------+-------------+
3 rows in set

(Cardinality is a sampled estimate, so the numbers differ from server to server.) InnoDB samples a number of index pages to estimate it. Run ANALYZE TABLE after big data changes to refresh it. Bad statistics are a common reason for a bad plan.

Histograms (MySQL 8.0)

An index’s cardinality tells how many distinct values there are, but not how they are distributed. The plan column has no index. 99 percent of the users are free and 1 percent are pro, but the optimizer has no idea how common pro is. It uses a default guess of 10 percent (the filtered column of EXPLAIN shows 10.00):

query.sql

SQL

EXPLAIN FORMAT=TRADITIONAL SELECT id FROM users WHERE plan = 'pro';

Output

OUTPUT

+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows  | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+-------------+
|  1 | SIMPLE      | users | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 39226 |    10.00 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+-------------+
1 row in set

A histogram records the real distribution. The optimizer uses it for columns without an index (for indexed columns it uses the index statistics). Create one and look at the plan again:

query.sql

SQL

ANALYZE TABLE users UPDATE HISTOGRAM ON plan, is_active WITH 16 BUCKETS;
SELECT column_name, histogram->>'$."histogram-type"' AS type, histogram->>'$."number-of-buckets-specified"' AS buckets
FROM information_schema.column_statistics
WHERE schema_name = 'learn' AND table_name = 'users'
ORDER BY column_name;
EXPLAIN FORMAT=TRADITIONAL SELECT id FROM users WHERE plan = 'pro';

Output

OUTPUT

+-------------+-----------+----------+------------------------------------------------------+
| Table       | Op        | Msg_type | Msg_text                                             |
+-------------+-----------+----------+------------------------------------------------------+
| learn.users | histogram | status   | Histogram statistics created for column 'is_active'. |
| learn.users | histogram | status   | Histogram statistics created for column 'plan'.      |
+-------------+-----------+----------+------------------------------------------------------+
2 rows in set

+-------------+-----------+---------+
| COLUMN_NAME | type      | buckets |
+-------------+-----------+---------+
| is_active   | singleton | 16      |
| plan        | singleton | 16      |
+-------------+-----------+---------+
2 rows in set

+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows  | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+-------------+
|  1 | SIMPLE      | users | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 39226 |     1.00 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+-------+----------+-------------+
1 row in set

Histograms help the optimizer estimate WHERE plan = 'pro' correctly, and choose a better join order. They cost nothing at write time (they are not updated automatically: run the statement again after the data changes). Remove one with ANALYZE TABLE users DROP HISTOGRAM ON plan;.

A practical checklist

Question	Answer
Will the query return a small fraction of the table?	Index candidates
Is the column in `WHERE` / `JOIN` / `ORDER BY` of a frequent query?	Index candidates
Does the column have only a few values and the common value is queried?	Probably no index
Is the column combined with a selective one in a composite index?	A low-selectivity column can be a useful second or third column
Is the table small (under a few thousand rows)?	Usually no extra index needed

A low-selectivity column inside a composite index

status alone is a poor index. (customer_id, status) is a good one: customer_id narrows the search, and status narrows it further or lets the index cover a grouping (Composite Indexes).

lightbulb

Use EXPLAIN, not guesswork

MySQL decides whether to use an index from statistics. If you doubt that an index helps, test the real query with EXPLAIN and, better, with EXPLAIN ANALYZE on realistic data.