1. The Same Query, a 6000x Difference#

The same point lookup, differing by just one index, measured a time difference of three orders of magnitude.

A orders table with 200,000 rows, querying WHERE user_id = 12345:

More common and more troublesome than “no index added” is an index was added but didn’t take effect. For example, this one:

1
SELECT COUNT(*) FROM o WHERE created_at LIKE '2026-06%';

There’s clearly an index on created_at, yet EXPLAIN QUERY PLAN gives:

1
SCAN o USING COVERING INDEX ix_c

The entire index was scanned, 18.5 ms. Yet a semantically almost equivalent formulation:

1
SELECT COUNT(*) FROM o WHERE created_at BETWEEN '2026-06-01' AND '2026-06-30';

The plan becomes SEARCH o USING COVERING INDEX ix_c (created_at>? AND created_at<?), 0.97 ms. A 19x difference, just from the choice of formulation (the reason is in Section 5).

NOTE

Experimental environment: SQLite 3.42 (Python’s built-in sqlite3 module, in-memory database), orders table with 200,000 rows of random data, fixed seed to ensure reproducibility. SQLite was chosen because it has zero dependencies and the conclusions can be verified on the spot. The principles also hold for MySQL and PostgreSQL, but the execution plan output format and several optimization details vary by engine—Section 8 provides a comparison. The in-memory database has no disk I/O, so the absolute timings below are all optimistic, and the cost of table lookups is especially underestimated.

The table creation and data generation script for reproduction:

1
import sqlite3, random
2

3
con = sqlite3.connect(":memory:")
4
cur = con.cursor()
5
cur.execute("""
6
CREATE TABLE orders (
7
  id INTEGER PRIMARY KEY,   -- In SQLite this is the rowid, equivalent to a clustered index
8
  user_id INTEGER NOT NULL, status TEXT NOT NULL,
9
  amount INTEGER NOT NULL, created_at TEXT NOT NULL, note TEXT)
10
""")
11

12
rnd = random.Random(42)      #Fixed seed, data is reproducible
13
cur.executemany("INSERT INTO orders(user_id,status,amount,created_at,note) VALUES (?,?,?,?,?)",
14
    [(rnd.randint(1, 50_000), rnd.choice(["paid", "pending", "refunded"]),
15
      rnd.randint(1, 100_000),
16
      f"2026-{rnd.randint(1,12):02d}-{rnd.randint(1,28):02d}T10:00:00", "n" * 20)
17
     for _ in range(200_000)])
18
con.commit()
19

20
cur.execute("CREATE INDEX idx_user_status_amount ON orders(user_id, status, amount)")
21
con.commit()
22
cur.execute("ANALYZE")       #Update statistics, otherwise the cost model may be guessing blindly
23
con.commit()

2. B+ Tree: Where the Speed Comes From#

The essence of an index is replacing “row-by-row scanning” with “tree lookup.” A B+ tree has three key properties:

1. Only leaf nodes store data (or pointers to data); internal nodes store only keys and child pointers;
2. Leaf nodes are linked by a linked list, naturally supporting range scans and sequential traversal;
3. All leaf nodes have the same depth, so the query path length is predictable—there’s no “lucky and fast” scenario.

Property 1 determines how short the tree can be. Taking InnoDB as an example, a page is 16 KB, the primary key is a bigint (8 bytes) plus an in-page pointer (about 6 bytes), so an internal node can hold about 16KB / 14B ≈ 1170 key-value pairs; a leaf page, estimating 1 KB per row, can hold about 16 rows. Thus:

In other words, a table with twenty million rows takes only 3 page accesses to go from root to leaf. This is the decisive advantage of B+ trees over B trees: internal nodes carry no data, so the same page can hold more branches, making the tree shorter—and each level reduced in tree height means one fewer random I/O. Although hash indexes can achieve O(1) equality lookups, they completely lack support for ranges and sorting, so they cannot replace B+ trees as general-purpose indexes.

TIP

The row counts above are order-of-magnitude estimates; the actual numbers depend on page size, row width, and primary key type. Just remember the intuition that “three levels can hold tens of millions”—don’t treat the specific numbers as conclusions.

3. Leftmost Prefix: The Column Order of a Composite Index Is the Rule#

A composite index (user_id, status, amount) is sorted in the B+ tree in this order: first compare user_id, if equal then compare status, then compare amount. This yields a hard rule: an index can only be used for lookup by conditions that “match consecutively starting from the leftmost column.”

Measured (index is (user_id, status, amount)):

1
WHERE user_id = 1
2
  -> SEARCH orders USING COVERING INDEX idx_user_status_amount (user_id=?)
3

4
WHERE user_id = 1 AND status = 'paid'
5
  -> SEARCH ... (user_id=? AND status=?)
6

7
WHERE user_id = 1 AND status = 'paid' AND amount > 100
8
  -> SEARCH ... (user_id=? AND status=? AND amount>?)
9

10
WHERE status = 'paid'                      --Skip the leftmost column
11
  -> SEARCH orders USING COVERING INDEX idx_status (status=?)   ← took a different index
12

13
WHERE amount > 100
14
  -> SCAN orders USING COVERING INDEX idx_user_status_amount    ← note this line

The last one is particularly worth staring at: it’s not “using the index for lookup,” but scanning the entire index. The index is smaller than the table, so scanning the index is still cheaper than scanning the table, but it’s still O(n). SEARCH (tree lookup) and SCAN ... USING INDEX (full index scan) are two completely different things—be sure to distinguish them when reading execution plans. This is also where many people mistakenly believe “the index took effect.”

1
WHERE user_id = 1 AND status > 'paid' AND amount = 500
2
  -> SEARCH ... (user_id=? AND status>?)              ← amount is not in the lookup key
3

4
WHERE user_id = 1 AND status = 'paid' AND amount = 500
5
  -> SEARCH ... (user_id=? AND status=? AND amount=?)  ← all three columns are used

4. Covering Indexes: Eliminating Table Lookups#

If all the columns a query needs are in the index, the engine doesn’t have to go back to the table. SQLite will explicitly write USING COVERING INDEX in the plan:

1
SELECT user_id, amount FROM orders WHERE user_id = 12345
2
  -> SEARCH orders USING COVERING INDEX ix_user_amount (user_id=?)   0.0026 ms
3

4
SELECT user_id, amount, note FROM orders WHERE user_id = 12345
5
  -> SEARCH orders USING INDEX ix_user_amount (user_id=?)            0.0041 ms
6
                                                       ↑ missing COVERING, requires table lookup

In the microbenchmark on this in-memory database, the table lookup was only about 1.6 times more expensive—but this is precisely an illusion flattened out by memory: an in-memory database has no random disk I/O, and the essential cost of a table lookup is “random access by primary key/physical location.” On real storage, this gap is often on the order of dozens of times, which is also why “put all the columns the query needs into the index” has become one of the most effective optimization techniques.

The other side of the coin is: a covering index usually means a wider index, taking up more space and writing more slowly (Section 7). In addition, PostgreSQL’s index-only scan also requires visibility map support—only pages marked by VACUUM can completely avoid accessing the heap, and tables that have just been bulk-written often cannot enjoy this optimization.

5. Four Ways to Silently Invalidate an Index#

1
WHERE substr(created_at,1,4) = '2026'      --There is an index on created_at
2
  -> SCAN orders USING COVERING INDEX idx_created

1
CREATE INDEX idx_year ON orders(substr(created_at,1,4));
2

3
--The plan immediately becomes:
4
-- SEARCH orders USING INDEX idx_year (<expr>=?)

1
--Don't write it this way
2
WHERE substr(created_at,1,4) = '2026'
3
--Change to an explicit range
4
WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01'

1
PRAGMA case_sensitive_like = ON;
2
--Afterward: SEARCH o USING COVERING INDEX ix_c (created_at>? AND created_at<?)

1
WHERE user_id + 0 = 1        -> SCAN orders USING COVERING INDEX ...

1
WHERE created_at LIKE '%06-12%'   --Contains a leading %

6. Sorting, Pagination, and Indexes#

The leaves of a B+ tree are ordered, so if the sort columns can follow the index order, an extra sort can be avoided. SQLite will explicitly tell you with USE TEMP B-TREE FOR ORDER BY that it sorted one extra time.

Under the premise of user_id = 1, when the index is (user_id, status, amount):

1
ORDER BY status
2
  -> SEARCH ... (user_id=?)                        ← no additional sorting
3

4
ORDER BY amount
5
  -> SEARCH ... (user_id=?)
6
  -> USE TEMP B-TREE FOR ORDER BY                  ← one extra sort
7

8
ORDER BY created_at
9
  -> SEARCH ... (user_id=?)
10
  -> USE TEMP B-TREE FOR ORDER BY

Reason: once user_id is fixed, the remaining order in the index is (status, amount). ORDER BY status follows exactly this order; ORDER BY amount skips status, and the order is no longer guaranteed in any way.

This explains why sort columns should be placed at the end of a composite index: equality conditions lock down the prefix, the sort columns follow the index order, and there must be no break in between.

1
SELECT id, amount FROM orders ORDER BY id LIMIT 20 OFFSET 100000;

1
SELECT id, amount FROM orders
2
WHERE user_id = 1 AND id > :last_id    --The id of the last record on the previous page
3
ORDER BY id
4
LIMIT 20;

7. Selectivity, and Indexes Are Not Free#

Selectivity = number of distinct values / total number of rows. A column with selectivity close to 1 (primary key, user_id) allows the index to cut the result down to very few rows; a column with selectivity close to 0 (status with only three possible values) may have an equality query hit one third of the rows.

Here I need to correct a popular claim. I tested it with status:

1
WHERE status = 'paid'     --Only 3 distinct values, matching about 1/3 of the rows
2
  -> SEARCH orders USING INDEX idx_status2 (status=?)

The optimizer did not abandon the index. So “an index on a low-cardinality column is bound to be useless” is an overly absolute conclusion. The real problem with low cardinality is not “the index cannot be used,” but that the large number of rows filtered out still have to be looked up one by one in the table—too many random accesses, and the benefit is eaten up by the table lookup cost. Whether to abandon the index depends on the engine’s cost model and statistics, which is also why stale statistics can suddenly make a plan worse.

8. How to Diagnose: An Actionable Process#

Don’t guess—let the engine speak for itself.

Step 1: Get the execution plan.

PostgreSQL’s ANALYZE gives the real elapsed time and actual row counts, and BUFFERS gives cache hit information—when “the optimizer’s estimated row count” differs greatly from “the actual row count,” it is usually stale statistics, and this itself is an important clue.

Step 2: Look at the keywords. SCAN / Seq Scan / type: ALL are bad signals; SEARCH ... USING INDEX / Index Scan / Index Only Scan / ref / range are good signals. Be sure to distinguish SEARCH (tree search) from SCAN ... USING INDEX (full index scan)—the difference is O(log n) versus O(n).

Step 3: Controlled experiments. Comment out the suspicious conditions one by one, then get the plan again. Whether an equality condition was changed to a range, or a function was wrapped around a column, the plan will tell you immediately.

Step 4: Small first, then large. First confirm that the plan is correct at a small data volume (if the plan is wrong, it will only get worse as the data grows), then measure the real elapsed time with the real data volume. If the plan looks good but the elapsed time is poor, the problem is most likely in the number of table lookups or the data distribution, not in the index itself.

Step 5: Update statistics. ANALYZE (SQLite / PostgreSQL) or ANALYZE TABLE (MySQL). When a plan suddenly gets worse, this is the first thing to do.

9. Summary#

• Indexes replace linear scans with tree lookups; the “shortness” of the B+ tree and its “ordered leaves” are the two core advantages;
• The column order of a composite index determines whether it can be used: equality first, range after, sort last;
• Covering indexes eliminate table lookups and are usually the single-point optimization with the biggest payoff;
• Wrapping columns in functions, type mismatches, LIKE prefixes (depending on the engine and collation), and leading wildcards are the four most common silent failures;
• Indexes have a clear write cost and space cost—it’s a trade-off, not free acceleration.

One final piece of advice: every conclusion in this article comes with actual measured output, but they all come from SQLite. The principles can be transferred, but the specifics may differ for a given engine, a given version, or even a given state of statistics. Run EXPLAIN once on the database you’re actually optimizing—that’s more reliable than memorizing any conclusion.

References#

• SQLite: EXPLAIN QUERY PLAN output description
• SQLite: Query Optimizer Overview (including LIKE optimization and leftmost prefix)
• SQLite: The Query Planner
• PostgreSQL: Using EXPLAIN
• PostgreSQL: Index-Only Scans and Covering Indexes
• Use The Index, Luke!—A guide to SQL indexing and tuning for developers