Database Indexing Explained: Why Queries Are Slow and How Indexes Fix Them

A database index is a separate data structure — maintained alongside your table — that allows the database engine to locate rows without reading every row in the table. When you run SELECT * FROM users WHERE email = 'alice@example.com' on a 10-million-row table with no index, the database reads all 10 million rows. With an index on email, it reads roughly 24 rows worth of tree nodes and returns the result in under a millisecond.

That is how database indexing works: the index stores the indexed column values in sorted order, along with pointers to the actual table rows. The database traverses the index structure — not the table — to find matching rows, then fetches only those rows directly.

Table with 10 million rows, no index:
SELECT * FROM users WHERE email = 'alice@example.com';
Time: 12,340ms — reads every row (Seq Scan)
 
Same query with an index on email:
CREATE INDEX idx_users_email ON users(email);
Time: 0.8ms — traverses index tree, fetches one row (Index Scan)

That is a 15,000× speedup from one statement. Most backend performance problems — before you reach the point of sharding, caching, or replication — are index problems.

What an Index Actually Is

Think of a book's index. Instead of reading every page to find "Redis", you look in the index and jump straight to the right pages. A database index works identically. Without it, the database performs a full table scan — reading every row. With one, it jumps straight to the matching rows.

The index is a separate structure stored on disk. It takes up space, and every write (INSERT, UPDATE, DELETE) must update it. That is the trade-off: indexes make reads faster at the cost of slightly slower writes and additional disk usage.

Most indexes in PostgreSQL, MySQL, and SQLite use a B-Tree (Balanced Tree) as their underlying data structure. Understanding why databases chose B-Trees — and how traversal works — makes the rest of indexing click immediately.

How B-Tree Indexes Work

A B-Tree is a self-balancing tree data structure that keeps data sorted and allows searches, insertions, and deletions in O(log n) time. The "B" stands for "balanced" — every leaf node is the same distance from the root.

Here is what a B-Tree index on a user_id column looks like for a small table:

                    [50]
                   /    \
            [25]            [75]
           /    \          /    \
       [10,20] [30,40] [60,70] [80,90]

Each internal node holds sorted key values and pointers to child nodes. Leaf nodes hold the actual index entries — key value plus a pointer (called a heap tuple pointer in PostgreSQL) to the physical row location on disk.

How a search works:

1. Query: WHERE user_id = 60
2. Start at root node [50] — 60 > 50, go right
3. Arrive at node [75] — 60 < 75, go left
4. Arrive at leaf node [60, 70] — found 60, follow heap pointer to fetch the row

With 10 million rows, a B-Tree has about 4–5 levels deep. The database finds any row in 4–5 I/O operations instead of scanning millions of rows.

Why databases use B-Trees specifically:

• Disk-friendly: B-Tree nodes are sized to match disk page sizes (typically 8KB in PostgreSQL). Each I/O read fetches a full node with many keys, making traversal efficient.
• Range queries: Because data is sorted, range queries (WHERE created_at BETWEEN '2024-01-01' AND '2024-06-01') work efficiently by finding the start point and scanning forward.
• High fan-out: Each node can hold hundreds of keys, keeping tree depth low even for very large tables.

-- Default index type in PostgreSQL is B-Tree
CREATE INDEX idx_users_email ON users(email);
 
-- Equivalent explicit syntax
CREATE INDEX idx_users_email ON users USING btree(email);

Types of Indexes

PostgreSQL supports several index types. Choosing the right one depends on your query patterns.

B-Tree Index (Default)

Use for: equality (=), range queries (<, >, BETWEEN), sorting (ORDER BY), and prefix matches (LIKE 'prefix%').

-- Equality lookup
CREATE INDEX idx_orders_customer ON orders(customer_id);
 
-- Range query — B-Tree handles this efficiently
CREATE INDEX idx_orders_created ON orders(created_at);
 
SELECT * FROM orders
WHERE created_at BETWEEN '2024-01-01' AND '2024-06-01';

Hash Index

Use for: equality lookups only. Faster than B-Tree for pure equality, but cannot handle range queries or sorting. In PostgreSQL, B-Tree is usually preferred because hash indexes are not WAL-logged before PostgreSQL 10 and do not support range queries.

CREATE INDEX idx_sessions_token ON sessions USING hash(session_token);
 
-- Only useful for exact match
SELECT * FROM sessions WHERE session_token = 'abc123';

Full-Text Index (GIN)

Use for: searching text content. Supports tsvector queries. A regular B-Tree cannot handle LIKE '%keyword%' efficiently — it requires a full scan. Full-text indexes tokenize the content and build an inverted index.

-- Add a tsvector column or use expression index
CREATE INDEX idx_posts_content_fts
ON posts USING GIN(to_tsvector('english', content));
 
-- Query using full-text search
SELECT * FROM posts
WHERE to_tsvector('english', content) @@ to_tsquery('english', 'database & indexing');

Partial Index

Use for: indexing only a subset of rows. When most queries filter on a condition, a partial index is smaller and faster than a full index.

-- Index only active users — ignores inactive/deleted rows entirely
CREATE INDEX idx_active_users_email
ON users(email) WHERE status = 'active';
 
-- This query uses the partial index
SELECT * FROM users
WHERE email = 'alice@example.com' AND status = 'active';
 
-- Index only unprocessed orders — a common pattern for job queues
CREATE INDEX idx_pending_orders
ON orders(created_at) WHERE processed = false;

Partial indexes are especially valuable when a small fraction of rows are "hot" (frequently queried) and you do not want to pay the write overhead of indexing every row.

Composite Index

Use for: queries that filter on multiple columns together. A single composite index is almost always more efficient than two separate single-column indexes.

-- Composite index on (country, status)
CREATE INDEX idx_users_country_status ON users(country, status);
 
-- Both columns used — index is highly efficient
SELECT * FROM users WHERE country = 'IN' AND status = 'active';

Column order in composite indexes matters significantly — covered in the next section.

Covering Index (Index-Only Scan)

Use for: queries that only need columns already in the index. When all columns in a SELECT are in the index, PostgreSQL can answer the query without touching the table at all — an Index Only Scan.

-- Covering index: includes all columns the query needs
CREATE INDEX idx_orders_covering
ON orders(customer_id) INCLUDE (order_total, created_at);
 
-- This query can be answered from the index alone — no table access
SELECT order_total, created_at
FROM orders
WHERE customer_id = 123;

The INCLUDE clause (PostgreSQL 11+) adds columns to the index leaf pages without making them part of the sort key — they are there purely for covering.

Index Selection: EXPLAIN ANALYZE

EXPLAIN ANALYZE is the primary tool for understanding whether PostgreSQL is using your indexes. It shows the query execution plan and actual timing.

EXPLAIN ANALYZE
SELECT * FROM users WHERE email = 'alice@example.com';

Without an index — Seq Scan:

Seq Scan on users  (cost=0.00..289483.00 rows=1 width=120)
                   (actual time=8234.123..12340.456 rows=1 loops=1)
  Filter: ((email)::text = 'alice@example.com'::text)
  Rows Removed by Filter: 9999999
Planning Time: 0.2 ms
Execution Time: 12340.5 ms

Key things to read:

• Seq Scan — reading every row in the table
• Rows Removed by Filter: 9999999 — it scanned 10M rows and threw away 9,999,999
• Execution Time: 12340.5 ms — 12 seconds

After adding an index — Index Scan:

CREATE INDEX idx_users_email ON users(email);
 
EXPLAIN ANALYZE
SELECT * FROM users WHERE email = 'alice@example.com';

Index Scan using idx_users_email on users
  (cost=0.56..8.58 rows=1 width=120)
  (actual time=0.412..0.418 rows=1 loops=1)
  Index Cond: ((email)::text = 'alice@example.com'::text)
Planning Time: 0.3 ms
Execution Time: 0.5 ms

• Index Scan using idx_users_email — using the index
• rows=1 — fetched exactly one row
• Execution Time: 0.5 ms — 24,000× faster

Spotting missing indexes:

Look for these red flags in EXPLAIN ANALYZE output:

Find slow queries automatically with pg_stat_statements:

-- Enable the extension first (requires superuser)
CREATE EXTENSION IF NOT EXISTS pg_stat_statements;
 
-- Find queries taking more than 1 second on average
SELECT
  query,
  calls,
  round(mean_exec_time::numeric, 2) AS avg_ms,
  round(total_exec_time::numeric, 2) AS total_ms
FROM pg_stat_statements
WHERE mean_exec_time > 1000
ORDER BY mean_exec_time DESC
LIMIT 20;

Composite Index Column Order

Column order in a composite index is one of the most misunderstood aspects of indexing. Getting it wrong means the index is partially or completely unused.

The leftmost prefix rule: A composite index (a, b, c) can be used for queries on (a), (a, b), or (a, b, c). It cannot be used for queries on (b) or (c) alone, or (b, c) without (a).

CREATE INDEX idx_users_country_status ON users(country, status);
 
-- Uses the index (country is leftmost)
SELECT * FROM users WHERE country = 'IN' AND status = 'active'; -- full index use
SELECT * FROM users WHERE country = 'IN';                        -- partial index use
 
-- Does NOT use the composite index
SELECT * FROM users WHERE status = 'active'; -- skips the leftmost column

Think of it like a phone book sorted first by last name, then by first name. You can find all "Sharma" entries fast, and all "Sharma, Akash" entries fast. But finding all people named "Akash" requires scanning the whole book.

Two rules for ordering composite index columns:

Rule 1 — Equality before range: Columns used in equality conditions (=) should come before columns used in range conditions (<, >, BETWEEN, LIKE).

-- Queries like: WHERE country = 'IN' AND created_at > '2024-01-01'
-- WRONG order: range column first
CREATE INDEX idx_wrong ON orders(created_at, country);
 
-- CORRECT order: equality column first
CREATE INDEX idx_correct ON orders(country, created_at);

With the correct index, PostgreSQL uses country = 'IN' to narrow to a small subset, then scans only that subset for the date range. With the wrong order, it may scan all dates first.

Rule 2 — Higher cardinality first (usually): Cardinality is the number of unique values in a column. email has very high cardinality (nearly unique per row). status has low cardinality (maybe 3–5 values).

For selective filtering, put the higher-cardinality column first — it eliminates more rows immediately.

-- 'email' has high cardinality, 'status' has low cardinality
-- Put email first for queries filtering on both
CREATE INDEX idx_users_email_status ON users(email, status);

Exception: if your queries always filter on the low-cardinality column first and it is an equality condition, put it first — the leftmost prefix rule takes priority over cardinality.

When Indexes Hurt Performance

Indexes are not free. Every index you add has costs that compound as your table grows.

Write Overhead

Every INSERT, UPDATE, or DELETE must update all indexes on the table. A table with 8 indexes pays 8× the write overhead compared to an unindexed table.

-- This table has 8 indexes
-- Every INSERT pays the cost of updating all 8 index structures
INSERT INTO orders (customer_id, product_id, status, ...) VALUES (...);

For write-heavy tables — logging tables, event streams, audit tables — excessive indexes can make writes catastrophically slow.

Index Bloat

PostgreSQL uses MVCC (Multi-Version Concurrency Control). When you UPDATE or DELETE rows, old versions are not immediately removed from indexes. Over time, indexes accumulate dead tuples — index entries pointing to rows that no longer exist. This is index bloat.

-- Check index bloat
SELECT
  schemaname,
  tablename,
  indexname,
  pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_stat_user_indexes
ORDER BY pg_relation_size(indexrelid) DESC;

A bloated index is larger than it needs to be and slower to traverse. Tables with frequent updates or deletes accumulate bloat fastest.

Over-Indexing and Dead Indexes

Adding indexes "just in case" is a common mistake. Dead indexes — indexes that no queries actually use — waste disk space and slow down all writes.

-- Find indexes that have never been used since last stats reset
SELECT
  schemaname,
  tablename,
  indexname,
  idx_scan AS times_used,
  pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_stat_user_indexes
WHERE idx_scan = 0
  AND schemaname NOT IN ('pg_catalog', 'information_schema')
ORDER BY pg_relation_size(indexrelid) DESC;

Any index with times_used = 0 is a candidate for removal. Drop it and recover the write overhead.

Low-Cardinality Columns

An index on a boolean column (e.g., is_deleted) with values true or false is often useless. If 50% of rows have is_deleted = false, the database might decide a full table scan is faster than using the index — because it would need to fetch half the table's rows anyway, making random I/O via index slower than sequential scan.

-- This index is often worthless
CREATE INDEX idx_users_is_deleted ON users(is_deleted); -- only 2 values!
 
-- A partial index is far more useful
CREATE INDEX idx_active_users ON users(email) WHERE is_deleted = false;

Index Maintenance

Indexes require periodic maintenance to stay performant. PostgreSQL provides two key tools.

VACUUM

VACUUM reclaims space from dead tuples (rows deleted or updated but not yet physically removed). Autovacuum runs automatically in modern PostgreSQL, but you can trigger it manually:

-- Vacuum a specific table (reclaims dead tuple space, updates statistics)
VACUUM ANALYZE users;
 
-- Full vacuum — rewrites the table, reclaims space to OS, locks table
-- Only use during maintenance windows
VACUUM FULL users;

VACUUM (without FULL) does not lock the table and is safe to run in production. VACUUM FULL rewrites the entire table and index and acquires an exclusive lock — use it sparingly.

REINDEX

REINDEX rebuilds an index from scratch, eliminating bloat and fixing any corruption. Use it when index bloat is severe or after large bulk operations.

-- Rebuild a specific index (locks the table in older PostgreSQL)
REINDEX INDEX idx_users_email;
 
-- Rebuild all indexes on a table
REINDEX TABLE users;
 
-- PostgreSQL 12+: CONCURRENTLY — rebuilds without locking
REINDEX INDEX CONCURRENTLY idx_users_email;

Monitoring Index Bloat

-- Estimate index bloat using pgstattuple extension
CREATE EXTENSION IF NOT EXISTS pgstattuple;
 
SELECT *
FROM pgstatindex('idx_users_email');
-- Returns: avg_leaf_density, leaf_fragmentation — high fragmentation means bloat

A healthy index has avg_leaf_density above 70%. If it drops below 50%, run REINDEX CONCURRENTLY.

When to Add an Index

Add an index when:

• You frequently query by a column in a WHERE clause on a large table
• You JOIN tables on a column (foreign keys almost always need indexes)
• You ORDER BY or GROUP BY a column in performance-critical queries

-- Foreign keys should always be indexed
-- Without this, JOINs do a full scan of the orders table
CREATE INDEX idx_orders_customer ON orders(customer_id);
 
-- Sorting columns benefit from indexes
CREATE INDEX idx_posts_created ON posts(created_at DESC);

Primary keys are automatically indexed. Foreign key columns are not automatically indexed in PostgreSQL — always add them manually.

Key Takeaways

• Without an index, the database reads every row — fine for small tables, catastrophic for millions of rows
• B-Tree indexes keep data sorted in a shallow tree; any value is found in ~4–5 I/O operations regardless of table size
• Use EXPLAIN ANALYZE to confirm whether your query uses an index — look for Seq Scan as a red flag
• In composite indexes, put equality columns before range columns, and follow the leftmost prefix rule
• Indexes speed up reads but slow down every write — audit and drop unused indexes regularly
• Partial indexes, covering indexes, and full-text indexes solve specific problems more efficiently than plain B-Trees
• Run VACUUM ANALYZE regularly; use REINDEX CONCURRENTLY when index bloat is high
• Foreign key columns almost always need indexes — missing them causes catastrophically slow JOINs

The single highest-ROI optimization for most backend applications is adding the right database indexes.

Frequently Asked Questions

What is a database index and why does it matter?

A database index is a separate data structure that stores a sorted copy of one or more column values along with pointers to the corresponding table rows. Without an index, every query that filters by a column requires reading every row in the table (a sequential scan). With an index, the database traverses a tree structure and fetches only the matching rows — turning a query that takes 12 seconds into one that takes under a millisecond on a 10-million-row table.

What is a B-Tree index?

A B-Tree (Balanced Tree) index is the default index type in PostgreSQL, MySQL, and most relational databases. It organizes index entries in a sorted, hierarchical tree structure where all leaf nodes are at the same depth. This structure allows the database to find any value in O(log n) time — roughly 24 comparisons for 10 million rows — and efficiently handles equality lookups, range queries, and sorting. Every CREATE INDEX statement without a USING clause creates a B-Tree index.

How do I know which columns to index?

Start with EXPLAIN ANALYZE on your slowest queries. Look for Seq Scan on large tables — those filter columns need indexes. Also check: columns in JOIN conditions (especially foreign keys), columns in WHERE clauses in high-frequency queries, and columns in ORDER BY for paginated queries. Use pg_stat_statements to identify which queries consume the most total time — those are your highest-impact targets.

What is a composite index and when should I use one?

A composite index covers multiple columns in a single index structure. Use one when your queries regularly filter on multiple columns together. A single composite index (country, status) is almost always more efficient than two separate indexes on country and status, because the database can use one tree traversal to filter by both. Remember the leftmost prefix rule: a composite index (a, b, c) is usable for queries on a, (a, b), or (a, b, c) — but not b or c alone.

Can too many indexes slow down my database?

Yes. Every index you add must be updated on every INSERT, UPDATE, and DELETE on that table. A table with 10 indexes pays 10× the write overhead versus an unindexed table. Over time, indexes also accumulate dead tuples (bloat) that waste space and slow traversal. Run pg_stat_user_indexes to find indexes with idx_scan = 0 — those are dead indexes that should be dropped.

What is a covering index?

A covering index is an index that contains all the columns a query needs to answer — so the database never needs to access the actual table. This results in an Index Only Scan, which is faster than a regular Index Scan because it eliminates the table heap fetch entirely. In PostgreSQL 11+, use the INCLUDE clause to add non-key columns to the index leaf pages: CREATE INDEX idx ON orders(customer_id) INCLUDE (order_total, created_at). A query selecting only order_total and created_at for a given customer_id can be answered entirely from this index.

How do I find missing indexes in PostgreSQL?

Three methods: (1) Run EXPLAIN ANALYZE on slow queries and look for Seq Scan with high Rows Removed by Filter. (2) Query pg_stat_user_tables for tables with high seq_scan counts — these tables have frequently-run queries with no usable index. (3) Enable pg_stat_statements and query it for slow queries, then run EXPLAIN ANALYZE on those queries to identify which filter columns lack indexes. Fixing a missing index on a hot table is usually the single highest-impact change you can make.

Related reading: Redis Caching Explained · Database Sharding