Chapter 08 · Index Engineering and Access Path Design
B-Tree Index Structure, Selectivity, Cardinality, and Leftmost-Prefix Rules
Design the first useful access paths from evidence: understand B-tree ordering, distinguish estimated cardinality from measured distinctness, and test exactly which parts of a composite index constrain a query.
Learning outcomes
A production index is not a magic “speed switch.” It is an ordered access structure whose usefulness depends on the query shape, data distribution, and the optimizer’s estimate of how much work each access path will perform. Chapter 07 established that an InnoDB secondary index is itself a B-tree and that its leaf entries carry the clustered key. This lesson turns that storage fact into query-design judgment.
Explain how B-tree key ordering supports equality, range, and ordered access without claiming that every indexed query is faster.
Distinguish true distinct-value counts, selectivity, SHOW INDEX cardinality estimates, and optimizer row estimates.
Predict the ordinary leftmost prefixes available from a composite index and recognize where a gap or range changes later-key usefulness.
Use SHOW INDEX, EXPLAIN, and EXPLAIN ANALYZE as evidence rather than relying on index naming or intuition.
Diagnose a tempting low-selectivity single-column index and replace it only when a workload-shaped alternative demonstrates benefit.
Start with a realistic access-path problem
ServiceHub’s operations screen is slow when a dispatcher asks for one tenant’s open work orders from the last 30 days. A developer proposes three indexes—one on tenant_id, one on status, and one on opened_at—because all three columns appear in the WHERE clause. That advice ignores how B-tree keys are ordered and how MySQL normally selects one access path per table reference.
A B-tree index stores keys in sorted order. A composite index has more than one key part. Cardinality in SHOW INDEX is an estimate of the number of distinct values. Selectivity is a workload-design ratio—roughly distinct values divided by rows for a key or prefix. EXPLAIN shows optimizer estimates; EXPLAIN ANALYZE executes the statement and adds actual iterator timing and row counts.
Build the disposable index lab
Use a local MySQL Community Server 8.4.10 instance. The data is synthetic and the schema is disposable; later lessons add and remove indexes freely. The recursive CTE creates 20,000 rows—large enough to expose plan choices on many laptops without pretending it models your production hardware.
DROP DATABASE IF EXISTS servicehub_index_lab;CREATE DATABASE servicehub_index_lab CHARACTER SET utf8mb4 COLLATE utf8mb4_0900_ai_ci;USE servicehub_index_lab;CREATE TABLE technicians ( technician_id BIGINT UNSIGNED NOT NULL, tenant_id INT UNSIGNED NOT NULL, display_name VARCHAR(100) NOT NULL, team_code VARCHAR(20) NOT NULL, PRIMARY KEY (technician_id), KEY ix_technicians_tenant_team (tenant_id, team_code, technician_id)) ENGINE=InnoDB;CREATE TABLE work_orders ( work_order_id BIGINT UNSIGNED NOT NULL AUTO_INCREMENT, tenant_id INT UNSIGNED NOT NULL, site_id INT UNSIGNED NOT NULL, technician_id BIGINT UNSIGNED NULL, status VARCHAR(16) NOT NULL, priority TINYINT UNSIGNED NOT NULL, opened_at DATETIME(6) NOT NULL, closed_at DATETIME(6) NULL, customer_name VARCHAR(120) NOT NULL, summary VARCHAR(255) NOT NULL, details TEXT NOT NULL, metadata JSON NOT NULL, PRIMARY KEY (work_order_id), KEY ix_work_orders_technician (technician_id), CONSTRAINT fk_work_orders_technician FOREIGN KEY (technician_id) REFERENCES technicians(technician_id)) ENGINE=InnoDB;INSERT INTO technicians VALUES (101,1,'Ana Ruiz','north'),(102,1,'Mina Park','north'), (201,2,'Omar Haddad','central'),(301,3,'Noah Chen','south');SET SESSION cte_max_recursion_depth = 25000;INSERT INTO work_orders (tenant_id,site_id,technician_id,status,priority,opened_at,closed_at, customer_name,summary,details,metadata)WITH RECURSIVE seq AS ( SELECT 1 AS n UNION ALL SELECT n+1 FROM seq WHERE n < 20000)SELECT 1 + MOD(n,40), 1 + MOD(n,500), CASE WHEN MOD(n,11)=0 THEN NULL ELSE 100 + MOD(n,220) END, ELT(1+MOD(n,5),'open','assigned','waiting','closed','cancelled'), 1 + MOD(n,4), TIMESTAMP('2026-01-01 00:00:00') + INTERVAL MOD(n,180) DAY + INTERVAL MOD(n,86400) SECOND, CASE WHEN MOD(n,5)=3 THEN TIMESTAMP('2026-01-01 00:00:00') + INTERVAL MOD(n,180) DAY + INTERVAL (MOD(n,86400)+7200) SECOND ELSE NULL END, CONCAT('Customer ',LPAD(MOD(n,900),3,'0')), CONCAT(ELT(1+MOD(n,6),'Network','Power','Cooling','Sensor','Access','Pump'),' incident ',n), CONCAT('ServiceHub diagnostic narrative for work order ',n,' at site ',MOD(n,500),'.'), JSON_OBJECT( 'sla_minutes', ELT(1+MOD(n,4),30,60,120,240), 'skill_codes', JSON_ARRAY(10+MOD(n,7),20+MOD(n,5)), 'source', ELT(1+MOD(n,3),'portal','phone','monitor'))FROM seq;ANALYZE TABLE work_orders;USE servicehub_index_lab;SELECT COUNT(*) AS rows_total, COUNT(DISTINCT tenant_id) AS tenants, COUNT(DISTINCT status) AS statuses, MIN(opened_at) AS first_opened, MAX(opened_at) AS last_openedFROM work_orders;SHOW INDEX FROM work_orders;The deterministic generator yields 20,000 rows, 40 tenant values, and 5 status values. Those counts are facts about this lab. The Cardinality values shown by SHOW INDEX, by contrast, are optimizer statistics and can be approximate.
Why ordered composite keys matter
Create one index whose key order matches the dispatcher query:
CREATE INDEX ix_wo_tenant_status_opened ON work_orders (tenant_id, status, opened_at, work_order_id);ANALYZE TABLE work_orders;SHOW INDEX FROM work_orders WHERE Key_name='ix_wo_tenant_status_opened';Conceptually, the B-tree is ordered first by tenant_id. Within each tenant value it is ordered by status; within that pair it is ordered by opened_at; ties finally include work_order_id. That nested ordering is the reason the ordinary leftmost prefixes are (tenant_id), (tenant_id,status), (tenant_id,status,opened_at), and the full key.
| Predicate shape | Ordinary B-tree access expectation | Reason |
|---|---|---|
tenant_id=7 | Can seek on the first key part. | The search begins at a leftmost prefix. |
tenant_id=7 AND status='open' | Can narrow the contiguous key interval further. | Both leading parts are fixed. |
tenant_id=7 AND status='open' AND opened_at>=... | Can form a range inside the tenant/status slice. | Equalities lead into a range. |
status='open' | Cannot use status as an ordinary leftmost range by itself. | The first key part is unconstrained; skip scan is a separate cost-based optimization discussed in Lesson 4. |
tenant_id=7 AND opened_at>=... | The tenant prefix is useful, but the gap at status prevents the later date from behaving like the contiguous three-part range above. | Composite ordering has a missing key part. |
Observe estimates, then observe execution
EXPLAIN FORMAT=TREESELECT work_order_id, opened_atFROM work_ordersWHERE tenant_id=7 AND status='open' AND opened_at >= '2026-05-01'ORDER BY opened_at, work_order_idLIMIT 25;EXPLAIN ANALYZESELECT work_order_id, opened_atFROM work_ordersWHERE tenant_id=7 AND status='open' AND opened_at >= '2026-05-01'ORDER BY opened_at, work_order_idLIMIT 25;EXPLAIN FORMAT=TREESELECT work_order_id, opened_atFROM work_ordersWHERE status='open' AND opened_at >= '2026-05-01'LIMIT 25;Record the chosen key, access type, estimated rows, actual rows, loops, and whether a separate sort appears. Do not copy an exact timing from this lesson: cache warmth, CPU, filesystem, and optimizer statistics differ. The evidence to carry forward is structural—what interval MySQL can search and how many rows it actually visits on your instance.
SELECT COUNT(*) AS n, COUNT(DISTINCT tenant_id) AS tenant_distinct, COUNT(DISTINCT tenant_id,status) AS tenant_status_distinct, COUNT(DISTINCT tenant_id,status,DATE(opened_at)) AS prefix_distinctFROM work_orders;SELECT INDEX_NAME, SEQ_IN_INDEX, COLUMN_NAME, CARDINALITYFROM information_schema.STATISTICSWHERE TABLE_SCHEMA='servicehub_index_lab' AND TABLE_NAME='work_orders' AND INDEX_NAME='ix_wo_tenant_status_opened'ORDER BY SEQ_IN_INDEX;INFORMATION_SCHEMA.STATISTICS.CARDINALITY is not a contractual exact count. It is statistics used for planning. If estimates look implausible after substantial data change, ANALYZE TABLE is evidence-oriented maintenance—not a guarantee that a specific plan must follow.
Tempting but ineffective: index the low-selectivity status alone
Because there are only five status values, a status-only index may match thousands of rows. Create it as an experiment rather than assuming it helps:
CREATE INDEX ix_wo_status_only ON work_orders(status);ANALYZE TABLE work_orders;EXPLAIN ANALYZESELECT work_order_id, customer_name, detailsFROM work_ordersWHERE status='open';SHOW INDEX FROM work_orders WHERE Key_name='ix_wo_status_only';The optimizer may use the index, may prefer another index, or may decide that scanning a large fraction of the table is cheaper. Any of those choices can be rational for this small lab. The failure is the slogan “indexed means fast,” not a specific expected plan. For the dispatcher screen, the corrected comparison is the composite index that isolates one tenant and status before applying the date range.
DROP INDEX ix_wo_status_only ON work_orders;SHOW INDEX FROM work_orders;Hands-on investigation
Run each query twice—once to inspect the plan and once with EXPLAIN ANALYZE. Predict the usable ordinary key prefix before executing it. Then explain any difference between your prediction and the optimizer’s chosen plan.
EXPLAIN ANALYZE SELECT work_order_id FROM work_orders WHERE tenant_id=12;EXPLAIN ANALYZE SELECT work_order_id FROM work_orders WHERE tenant_id=12 AND status='waiting';EXPLAIN ANALYZE SELECT work_order_id FROM work_orders WHERE tenant_id=12 AND status='waiting' AND opened_at BETWEEN '2026-02-01' AND '2026-03-01';EXPLAIN ANALYZE SELECT work_order_id FROM work_orders WHERE tenant_id=12 AND opened_at BETWEEN '2026-02-01' AND '2026-03-01';EXPLAIN ANALYZE SELECT work_order_id FROM work_orders WHERE status='waiting';Knowledge check
- What does the leftmost-prefix rule describe?
- Why is SHOW INDEX Cardinality not the same thing as COUNT(DISTINCT ...)?
- What usually happens after equality conditions followed by a range condition in a composite key?
- Why can a status-only index be a poor tradeoff even though status is queried often?
- What does EXPLAIN ANALYZE add beyond EXPLAIN?
Reveal answers
- Which leading key parts of an ordered composite index can form ordinary index search intervals. It does not say later columns are never useful for filtering, covering, sorting, ICP, or skip scan.
- Cardinality is an optimizer statistics estimate; COUNT(DISTINCT ...) computes the result for the data read by that statement.
- The equalities can narrow the prefix, then the range defines an interval; later key parts generally no longer extend that same contiguous range in the simple way equalities do.
- If each status matches a large share of rows, it may filter weakly while still adding storage and write-maintenance cost.
- It executes the statement and reports actual iterator timing/row activity in addition to planning information; those timings are local observations, not portable guarantees.
Production judgment and bridge
Do not optimize a schema by counting indexes. Start from query shapes, row counts, distribution, sort requirements, and write rates. A composite index is justified when its ordered prefix cuts meaningful work for important queries—or when it supplies required ordering/coverage at acceptable write cost. Chapter 09 will go deeper into statistics and plan engineering; this chapter stays focused on index design.
Lesson 2 asks the next design question: when several predicates and output columns matter, what key order gives the most reusable access path, when is an index covering, and how do you detect that multiple indexes are merely overlapping each other?