Indexing Internals: Why Your Queries Are Slow and How to Fix Them


Your application is slow. You check the slow query log. There is a query taking 4 seconds: SELECT * FROM orders WHERE user_id = 12345. The orders table has 50 million rows. You add an index on user_id. The query now takes 2 milliseconds. You just made it 2000x faster without changing a line of application code.

This is the power of indexes. But indexes are not free. Every index you add slows down writes, uses storage, and adds complexity to the query planner’s job. Understanding how indexes work internally tells you exactly when to add one, what kind to add, and when to leave well enough alone.

What an index actually is

An index is a separate data structure that the database maintains alongside your table. It stores a subset of your data (the indexed columns) in a structure optimized for fast lookup, along with pointers back to the full rows in the main table.

Without an index, finding all orders for user 12345 requires scanning every row in the orders table (a full table scan). With an index on user_id, the database jumps directly to the relevant rows.

The tradeoff: every write (INSERT, UPDATE, DELETE) must update both the table and all indexes on that table. More indexes = slower writes.

B-tree indexes: the default

The B-tree (balanced tree) is the default index type in PostgreSQL, MySQL, and most SQL databases. It is a self-balancing tree where all leaf nodes are at the same depth.

graph TB
subgraph btree["B-Tree Index on user_id"]
  ROOT["Root
[1000, 5000, 9000]"]
  N1["Node
[100, 500]"]
  N2["Node
[1500, 3000]"]
  N3["Node
[6000, 7500]"]
  L1["Leaf
[1,2,3]
row pointers"]
  L2["Leaf
[200,300]
row pointers"]
  L3["Leaf
[600,800]
row pointers"]
  L4["Leaf
[1200,1400]
row pointers"]
  L5["Leaf
[2000,2500]
row pointers"]
  L6["Leaf
[5500,5800]
row pointers"]
  L7["Leaf
[7000,7200]
row pointers"]
  ROOT --> N1
  ROOT --> N2
  ROOT --> N3
  N1 --> L1
  N1 --> L2
  N2 --> L3
  N2 --> L4
  N2 --> L5
  N3 --> L6
  N3 --> L7
end

style ROOT fill:#EEEDFE,stroke:#534AB7,color:#3C3489
style N1 fill:#EEEDFE,stroke:#534AB7,color:#3C3489
style N2 fill:#EEEDFE,stroke:#534AB7,color:#3C3489
style N3 fill:#EEEDFE,stroke:#534AB7,color:#3C3489
style L1 fill:#E1F5EE,stroke:#0F6E56,color:#085041
style L2 fill:#E1F5EE,stroke:#0F6E56,color:#085041
style L3 fill:#E1F5EE,stroke:#0F6E56,color:#085041
style L4 fill:#E1F5EE,stroke:#0F6E56,color:#085041
style L5 fill:#E1F5EE,stroke:#0F6E56,color:#085041
style L6 fill:#E1F5EE,stroke:#0F6E56,color:#085041
style L7 fill:#E1F5EE,stroke:#0F6E56,color:#085041

How a B-tree lookup works:

  1. Start at the root node
  2. Compare the search value against the node’s keys to determine which child to follow
  3. Repeat until you reach a leaf node
  4. The leaf node contains the row pointers (heap tuple IDs)
  5. Fetch the actual rows from the table using those pointers

For a table with 50 million rows, a B-tree has about 5-6 levels. A lookup requires 5-6 page reads instead of millions. That is why it is so fast.

B-trees support:

  • Equality: WHERE user_id = 123
  • Range: WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31'
  • Prefix: WHERE name LIKE 'John%' (but not WHERE name LIKE '%John')
  • Sorting: ORDER BY user_id can use the index to avoid a sort

Hash indexes

Hash indexes store a hash of the indexed value and a pointer to the row. Lookup is O(1) - compute the hash, find the bucket, get the row.

Faster than B-tree for equality lookups. But hash indexes do not support range queries or sorting. They are only useful for WHERE column = value.

PostgreSQL supports hash indexes but they are rarely used because B-trees are fast enough for equality and also support ranges. MySQL InnoDB does not support explicit hash indexes (it has an adaptive hash index that it manages automatically).

Where hash indexes shine: In-memory databases like Redis use hash tables as their primary data structure. Memcached is essentially a giant hash table.

Composite indexes

A composite (multi-column) index covers multiple columns. The order of columns matters enormously.

An index on (user_id, created_at) supports:

  • WHERE user_id = 123 (uses the index)
  • WHERE user_id = 123 AND created_at > '2024-01-01' (uses the index fully)
  • ORDER BY user_id, created_at (uses the index for sorting)

But NOT:

  • WHERE created_at > '2024-01-01' (cannot use the index - user_id is not specified)

This is the leftmost prefix rule: a composite index can only be used if the query includes the leftmost columns of the index.

The rule of thumb: put the most selective column first (the one that filters out the most rows), then the next most selective, and so on.

Covering indexes

A covering index includes all the columns a query needs, so the database never has to fetch the actual row from the table.

-- Query
SELECT user_id, email, created_at FROM users WHERE user_id = 123;

-- Covering index
CREATE INDEX idx_users_covering ON users(user_id, email, created_at);

With a covering index, the database reads the index and returns the result directly. No table access needed. This is called an “index-only scan” in PostgreSQL.

Covering indexes are powerful for read-heavy queries but expensive in terms of storage and write overhead.

Where it breaks or gets interesting

Index selectivity

An index on a boolean column (is_active) with 99% of rows being true is nearly useless. The database might decide a full table scan is faster than using the index (fetching 99% of rows via index lookups is slower than just scanning the table sequentially).

High selectivity = few rows match = index is useful. Low selectivity = many rows match = index might not help.

Write amplification

Every index on a table adds overhead to every write. A table with 10 indexes requires 11 writes for every INSERT (1 for the table, 10 for the indexes). For write-heavy tables, fewer indexes is better.

Index bloat

When rows are updated or deleted, the old index entries are not immediately removed. They are marked as dead and cleaned up by the vacuum process (PostgreSQL) or purge thread (MySQL InnoDB). If vacuum cannot keep up, the index grows with dead entries, slowing down lookups. Monitor index bloat and run VACUUM regularly.

The query planner might not use your index

The query planner uses statistics about your data to decide whether to use an index. If the statistics are stale (run ANALYZE to update them), the planner might make wrong decisions. Also, certain query patterns prevent index use:

  • WHERE LOWER(email) = 'user@example.com' - Function on the column prevents index use. Fix: create a functional index on LOWER(email).
  • WHERE user_id + 1 = 123 - Arithmetic on the column prevents index use. Rewrite as WHERE user_id = 122.
  • WHERE user_id != 123 - Inequality on a low-selectivity column might not use the index.
graph LR
subgraph good["Index Used"]
  G1["WHERE user_id = 123"]
  G2["WHERE created_at > '2024-01-01'"]
  G3["WHERE user_id = 123
AND status = 'active'"]
  G4["ORDER BY user_id LIMIT 10"]
end

subgraph bad["Index NOT Used"]
  B1["WHERE LOWER(email) = 'x'"]
  B2["WHERE user_id + 1 = 124"]
  B3["WHERE status = 'active'
(no user_id prefix)"]
  B4["WHERE name LIKE '%john'"]
end

style good fill:#E1F5EE,stroke:#0F6E56,color:#085041
style bad fill:#FCEBEB,stroke:#A32D2D,color:#791F1F

Specialized index types

Partial indexes - Index only a subset of rows. CREATE INDEX ON orders(user_id) WHERE status = 'pending'. Smaller index, faster for queries that filter on the same condition.

Functional indexes - Index the result of a function. CREATE INDEX ON users(LOWER(email)). Enables case-insensitive lookups.

GIN indexes (PostgreSQL) - Generalized Inverted Index. Used for full-text search, JSONB queries, and array containment. Stores a mapping from each element to the rows containing it.

GiST indexes (PostgreSQL) - Generalized Search Tree. Used for geometric data, full-text search, and range types.

BRIN indexes (PostgreSQL) - Block Range Index. Stores min/max values for ranges of physical blocks. Tiny size, useful for naturally ordered data (timestamps in append-only tables). Not useful for random access.

Real-world indexing patterns

Time-series tables - Index on (entity_id, timestamp). Queries are almost always “get events for entity X in time range Y.” The composite index supports this perfectly. Use BRIN for the timestamp alone if you need range scans across all entities.

User activity tables - Index on user_id for per-user queries. Separate index on created_at for time-based queries. Composite index on (user_id, created_at) if you frequently query both.

Search - Full-text search with GIN index on a tsvector column (PostgreSQL). For complex search, use Elasticsearch instead.

Unique constraints - Always backed by an index. UNIQUE(email) creates a B-tree index on email automatically.

How to apply it in practice

The indexing workflow

  1. Identify slow queries - Use pg_stat_statements (PostgreSQL) or the slow query log (MySQL) to find queries taking more than 100ms.
  2. Run EXPLAIN ANALYZE - See the query plan. Look for “Seq Scan” on large tables - that is a missing index.
  3. Add the index - Create it CONCURRENTLY in production to avoid locking the table.
  4. Verify it is used - Run EXPLAIN ANALYZE again. Confirm the plan uses the new index.
  5. Monitor write performance - Check if write throughput dropped after adding the index.

When NOT to add an index

  • Small tables (under 10,000 rows) - Full scans are fast enough
  • Write-heavy tables where the write overhead outweighs the read benefit
  • Low-selectivity columns (boolean, status with few values)
  • Columns rarely used in WHERE clauses

FAQ

Q: How many indexes should a table have?

There is no fixed number, but a rough guideline: OLTP tables (frequent reads and writes) should have 3-5 indexes. More than 10 indexes on a frequently written table is a red flag. Analytical tables (mostly reads) can have more. The right number depends on your query patterns and write volume. Use pg_stat_user_indexes to find indexes that are never used and drop them.

Q: Does adding an index always make queries faster?

No. For small tables, a full scan is faster than an index lookup because the entire table fits in memory and sequential reads are faster than random reads. For low-selectivity columns, the index might return so many rows that the database decides a full scan is cheaper. The query planner makes this decision based on statistics. If you think an index should be used but is not, check the statistics with EXPLAIN ANALYZE and look at the estimated vs actual row counts.

Q: What is the difference between a clustered and non-clustered index?

A clustered index determines the physical order of rows in the table. There can only be one clustered index per table. In MySQL InnoDB, the primary key is always the clustered index - rows are stored in primary key order. In PostgreSQL, there is no clustered index by default (you can cluster a table with CLUSTER but it is a one-time operation, not maintained automatically). A non-clustered index is a separate structure with pointers to the actual rows. Most indexes are non-clustered. The benefit of a clustered index: range scans on the clustered key are very fast because the rows are physically adjacent on disk.

Interview questions

Q1: A query SELECT * FROM events WHERE user_id = 123 ORDER BY created_at DESC LIMIT 10 is slow on a table with 100 million rows. How do you fix it?

Strong answer: Add a composite index on (user_id, created_at DESC). This index supports both the filter on user_id and the sort on created_at. The database can use the index to find all events for user 123 in reverse chronological order and stop after 10 rows - it never needs to scan the full table or sort in memory. Without this index, the database would either do a full table scan or use an index on user_id alone (finding all events for user 123, then sorting them all in memory before returning 10). Run EXPLAIN ANALYZE before and after to confirm the plan changes from a sort + index scan to an index-only scan.

Q2: You have a table with 20 indexes. Writes are slow. How do you decide which indexes to remove?

Strong answer: Use pg_stat_user_indexes to find indexes with zero or very low idx_scan counts - these are never used by queries. Also look at idx_tup_read vs idx_tup_fetch - a high ratio means the index is being scanned but not many rows are being fetched (low selectivity). Before dropping any index, check if it is used for a unique constraint or foreign key (dropping it would break those). Test the impact: drop the index in a staging environment, run your query suite, and measure write throughput improvement. In production, drop indexes one at a time and monitor for query regressions.

Q3: Explain why WHERE LOWER(email) = 'user@example.com' does not use an index on the email column and how to fix it.

Strong answer: The index stores the original values of the email column. When you apply LOWER() to the column in the WHERE clause, the database cannot use the index because the index does not contain the lowercased values - it would need to apply LOWER() to every index entry to find matches, which is equivalent to a full scan. The fix is a functional index: CREATE INDEX ON users(LOWER(email)). This index stores the lowercased email values. The query WHERE LOWER(email) = 'user@example.com' can now use this index because the index values match what the query is looking for. Alternatively, enforce lowercase at the application layer (always store emails in lowercase) and use a regular index on email.