How Indexes Work

An index is a separate structure that maps column values to row locations, so the database can find rows without reading the whole table. The default index type in PostgreSQL, MySQL, SQL Server, and Oracle is a B+tree.

This lesson builds a 200,000 row table and checks each claim with EXPLAIN (COSTS OFF), which prints only the plan shape. Parallel plans are switched off so the output is stable.

SQL

SET max_parallel_workers_per_gather = 0;

CREATE TABLE accounts AS
SELECT i AS id,
       'user' || i || '@example.com' AS email,
       (ARRAY['IN','US','UK','DE','FR','JP','BR','CA','AU','SG'])[i % 10 + 1] AS country,
       CASE WHEN i % 1000 = 0 THEN 'banned'
            WHEN i % 3 = 0 THEN 'inactive'
            ELSE 'active' END AS status,
       18 + i % 50 AS age,
       DATE '2020-01-01' + i / 150 AS signup_date,
       (i * 37) % 10000 AS balance
FROM generate_series(1, 200000) AS i;

ALTER TABLE accounts ADD PRIMARY KEY (id);
ANALYZE accounts;

SELECT count(*) AS total_rows, count(DISTINCT country) AS countries FROM accounts;

Output

 total_rows | countries 
------------+-----------
     200000 |        10
(1 row)

ANALYZE collects the statistics the planner uses. Run it after loading data.

Example 1: B+tree structure

A B+tree has three kinds of pages.

The root page and internal pages hold sorted keys and pointers to child pages.
Leaf pages hold the keys with row locations and are linked to their neighbours, which makes range scans fast.
All leaves are at the same depth, so every lookup reads the same number of pages.

flowchart TD
    R["Root: 40 | 80"] --> A["Internal: 10 | 20 | 30"]
    R --> B["Internal: 50 | 60 | 70"]
    R --> C["Internal: 90 | 100"]
    A --> L1["Leaf: 1..9 -> rows"]
    A --> L2["Leaf: 10..19 -> rows"]
    B --> L3["Leaf: 50..59 -> rows"]
    B --> L4["Leaf: 60..69 -> rows"]
    C --> L5["Leaf: 90..99 -> rows"]
    L1 -.-> L2
    L2 -.-> L3
    L3 -.-> L4
    L4 -.-> L5

A lookup starts at the root, follows one pointer per level down to a leaf, and reads the row location there. Dotted arrows are the leaf-to-leaf links used by range scans.

Example 2: fan-out and tree height

The fan-out is the number of child pointers per page. An 8 kB page holds roughly 200 to 500 index entries, depending on key size. The height is about log(rows) / log(fan-out).

SQL

SELECT rows,
       ceil(log(200, rows))  AS height_fanout_200,
       ceil(log(500, rows))  AS height_fanout_500
FROM (VALUES (200000::numeric), (1000000), (100000000), (10000000000)) AS t(rows);

Output

    rows     | height_fanout_200 | height_fanout_500 
-------------+-------------------+-------------------
      200000 |                 3 |                 2
     1000000 |                 3 |                 3
   100000000 |                 4 |                 3
 10000000000 |                 5 |                 4
(4 rows)

A table of 100 million rows needs 3 to 4 page reads to find one key. The upper levels stay in memory, so usually only the leaf and the table page come from disk.

Example 3: sequential scan vs index scan

Without an index on email, the only option is to read every page.

SQL

EXPLAIN (COSTS OFF)
SELECT * FROM accounts WHERE email = 'user123456@example.com';

Output

                     QUERY PLAN                     
----------------------------------------------------
 Seq Scan on accounts
   Filter: (email = 'user123456@example.com'::text)
(2 rows)

Add an index and run the same query.

SQL

CREATE INDEX idx_accounts_email ON accounts (email);

EXPLAIN (COSTS OFF)
SELECT * FROM accounts WHERE email = 'user123456@example.com';

Output

                       QUERY PLAN                       
--------------------------------------------------------
 Index Scan using idx_accounts_email on accounts
   Index Cond: (email = 'user123456@example.com'::text)
(2 rows)

Seq Scan reads the whole table. Index Scan walks the tree, then fetches the matching row from the table.

Example 4: index scan, index-only scan, bitmap scan

Scan	What it does	Chosen when
Index Scan	Walks the index, fetches each row from the table in index order	Few rows match, or the order is needed
Index Only Scan	Answers from the index alone, no table access	All needed columns are in the index and the pages are marked all-visible
Bitmap Index Scan + Bitmap Heap Scan	Collects matching row locations, sorts them by page, then reads each table page once	A moderate share of rows matches

SQL

VACUUM ANALYZE accounts;
CREATE INDEX idx_accounts_signup ON accounts (signup_date);
CREATE INDEX idx_accounts_age ON accounts (age);

-- one row, all columns needed: Index Scan
EXPLAIN (COSTS OFF) SELECT * FROM accounts WHERE email = 'user42@example.com';

-- only the indexed column is needed: Index Only Scan
EXPLAIN (COSTS OFF) SELECT email FROM accounts WHERE email = 'user42@example.com';

-- about 2% of rows scattered over the table: Bitmap scan
EXPLAIN (COSTS OFF) SELECT * FROM accounts WHERE age = 30;

-- same share of rows, but stored next to each other: Index Scan
EXPLAIN (COSTS OFF) SELECT * FROM accounts WHERE signup_date BETWEEN '2021-01-01' AND '2021-01-20';

DROP INDEX idx_accounts_age;

Output

                     QUERY PLAN                     
----------------------------------------------------
 Index Scan using idx_accounts_email on accounts
   Index Cond: (email = 'user42@example.com'::text)
(2 rows)

                      QUERY PLAN                      
------------------------------------------------------
 Index Only Scan using idx_accounts_email on accounts
   Index Cond: (email = 'user42@example.com'::text)
(2 rows)

                 QUERY PLAN                  
---------------------------------------------
 Bitmap Heap Scan on accounts
   Recheck Cond: (age = 30)
   ->  Bitmap Index Scan on idx_accounts_age
         Index Cond: (age = 30)
(4 rows)

                                         QUERY PLAN                                          
---------------------------------------------------------------------------------------------
 Index Scan using idx_accounts_signup on accounts
   Index Cond: ((signup_date >= '2021-01-01'::date) AND (signup_date <= '2021-01-20'::date))
(2 rows)

A bitmap scan is useful when matching rows are scattered. Here signup_date follows the row order, so matching rows are adjacent and a plain index scan is cheap.

An index-only scan depends on the visibility map, which VACUUM maintains. In a table with many recent updates, an index-only scan may still visit the table.

Example 5: composite index and the leftmost prefix rule

A composite (multi-column) index is sorted by the first column, then by the second within equal first values. It helps queries that filter on a leftmost prefix of its columns.

SQL

CREATE INDEX idx_accounts_country_status_age ON accounts (country, status, age);

-- uses the index: country is the first column
EXPLAIN (COSTS OFF) SELECT * FROM accounts WHERE country = 'IN' AND status = 'banned';

-- uses the index: first two columns
EXPLAIN (COSTS OFF) SELECT * FROM accounts WHERE country = 'IN' AND status = 'banned' AND age = 30;

-- skips the first column
EXPLAIN (COSTS OFF) SELECT * FROM accounts WHERE status = 'banned' AND age = 30;

Output

                                 QUERY PLAN                                 
----------------------------------------------------------------------------
 Bitmap Heap Scan on accounts
   Recheck Cond: ((country = 'IN'::text) AND (status = 'banned'::text))
   ->  Bitmap Index Scan on idx_accounts_country_status_age
         Index Cond: ((country = 'IN'::text) AND (status = 'banned'::text))
(4 rows)

                                     QUERY PLAN                                      
-------------------------------------------------------------------------------------
 Index Scan using idx_accounts_country_status_age on accounts
   Index Cond: ((country = 'IN'::text) AND (status = 'banned'::text) AND (age = 30))
(2 rows)

                          QUERY PLAN                          
--------------------------------------------------------------
 Index Scan using idx_accounts_country_status_age on accounts
   Index Cond: ((status = 'banned'::text) AND (age = 30))
(2 rows)

The third query has no condition on country. PostgreSQL can still scan the whole index and test status and age on every entry, which reads far more of the index than a prefix lookup does. Oracle and MySQL 8.0.13+ can use a skip scan, which probes each distinct value of the first column, when that column has few distinct values. PostgreSQL 18 adds a similar skip scan.

Example 6: column order, equality before range

Columns compared with = go first, and the range column goes last. Inside the index, entries with the same country are sorted by signup_date, so one contiguous slice matches both conditions.

SQL

DROP INDEX idx_accounts_signup;
CREATE INDEX idx_accounts_signup_country ON accounts (signup_date, country);

EXPLAIN (COSTS OFF)
SELECT * FROM accounts
WHERE country = 'JP' AND signup_date BETWEEN '2022-01-01' AND '2022-02-01';

DROP INDEX idx_accounts_signup_country;
CREATE INDEX idx_accounts_country_signup ON accounts (country, signup_date);

EXPLAIN (COSTS OFF)
SELECT * FROM accounts
WHERE country = 'JP' AND signup_date BETWEEN '2022-01-01' AND '2022-02-01';

Output

                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Index Scan using idx_accounts_signup_country on accounts
   Index Cond: ((signup_date >= '2022-01-01'::date) AND (signup_date <= '2022-02-01'::date) AND (country = 'JP'::text))
(2 rows)

                                                          QUERY PLAN                                                          
------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on accounts
   Recheck Cond: ((country = 'JP'::text) AND (signup_date >= '2022-01-01'::date) AND (signup_date <= '2022-02-01'::date))
   ->  Bitmap Index Scan on idx_accounts_country_signup
         Index Cond: ((country = 'JP'::text) AND (signup_date >= '2022-01-01'::date) AND (signup_date <= '2022-02-01'::date))
(4 rows)

With (signup_date, country), the scan covers every entry in the date range, for all countries, and checks country on each one. With (country, signup_date), the scan starts at the first JP entry in the date range and stops at the last, so it reads only matching entries.

Example 7: covering index with INCLUDE

INCLUDE stores extra columns in the leaf pages without making them part of the sort key. A query that needs only those columns runs as an index-only scan.

SQL

CREATE INDEX idx_accounts_country_cover ON accounts (country) INCLUDE (balance);

EXPLAIN (COSTS OFF)
SELECT country, balance FROM accounts WHERE country = 'SG' AND balance > 9990;

Output

                          QUERY PLAN                          
--------------------------------------------------------------
 Index Only Scan using idx_accounts_country_cover on accounts
   Index Cond: (country = 'SG'::text)
   Filter: (balance > 9990)
(3 rows)

Included columns make the index larger and slower to update. SQL Server supports INCLUDE too. MySQL InnoDB has no INCLUDE; a covering index there lists all columns in the key.

Example 8: partial index

A partial index covers only rows matching a WHERE condition. It is smaller and cheaper to maintain.

SQL

CREATE INDEX idx_accounts_banned ON accounts (id) WHERE status = 'banned';

SELECT pg_size_pretty(pg_relation_size('idx_accounts_banned')) AS partial_size,
       pg_size_pretty(pg_relation_size('idx_accounts_email'))  AS full_size;

EXPLAIN (COSTS OFF) SELECT id FROM accounts WHERE status = 'banned' AND id > 100000;

Output

 partial_size | full_size 
--------------+-----------
 16 kB        | 7960 kB
(1 row)

                      QUERY PLAN                       
-------------------------------------------------------
 Index Only Scan using idx_accounts_banned on accounts
   Index Cond: (id > 100000)
(2 rows)

The query condition must imply the index predicate for the planner to use the index. SQL Server calls these filtered indexes. MySQL and Oracle have no direct equivalent.

Example 9: expression index

An index on a column cannot serve a predicate that wraps the column in a function. Index the expression instead.

SQL

EXPLAIN (COSTS OFF) SELECT id FROM accounts WHERE upper(email) = 'USER77@EXAMPLE.COM';

CREATE INDEX idx_accounts_upper_email ON accounts (upper(email));

EXPLAIN (COSTS OFF) SELECT id FROM accounts WHERE upper(email) = 'USER77@EXAMPLE.COM';

Output

                      QUERY PLAN                       
-------------------------------------------------------
 Seq Scan on accounts
   Filter: (upper(email) = 'USER77@EXAMPLE.COM'::text)
(2 rows)

                           QUERY PLAN                            
-----------------------------------------------------------------
 Bitmap Heap Scan on accounts
   Recheck Cond: (upper(email) = 'USER77@EXAMPLE.COM'::text)
   ->  Bitmap Index Scan on idx_accounts_upper_email
         Index Cond: (upper(email) = 'USER77@EXAMPLE.COM'::text)
(4 rows)

The query must use exactly the same expression as the index. MySQL 8 supports functional indexes, and Oracle calls them function-based indexes.

Example 10: unique index

A unique index enforces uniqueness and is also used for lookups. PRIMARY KEY and UNIQUE constraints create one automatically.

SQL

CREATE UNIQUE INDEX uq_accounts_email ON accounts (email);

INSERT INTO accounts (id, email, country, status, age, signup_date, balance)

VALUES (300000, 'user1@example.com', 'IN', 'active', 30, DATE '2024-01-01', 0);

Output

ERROR:  duplicate key value violates unique constraint "uq_accounts_email"
DETAIL:  Key (email)=(user1@example.com) already exists.

NULL values do not conflict in a unique index in PostgreSQL, so many rows can hold NULL. SQL Server allows only one NULL.

Example 11: index types

Type	Best for	Operators	Notes
B-tree	Equality, ranges, sorting, prefix `LIKE`	`= < > BETWEEN`, `ORDER BY`	Default
Hash	Equality only	`=`	Smaller for long keys, no range or sort
GIN	Many values per row: arrays, `jsonb`, full text	`@> && @@`	Slow to update, fast to search
GiST	Geometry, ranges, nearest neighbour	`&& <@ <->`	Extensible; used by PostGIS
BRIN	Huge tables where values follow physical order	`= < >`	Stores min and max per block range, very small

signup_date grows with id, so it follows the physical order and suits BRIN.

SQL

CREATE INDEX idx_accounts_signup_brin ON accounts USING brin (signup_date);
SELECT pg_size_pretty(pg_relation_size('idx_accounts_signup_brin')) AS brin_size,
       pg_size_pretty(pg_relation_size('idx_accounts_country_signup')) AS btree_size;

SELECT correlation FROM pg_stats
WHERE tablename = 'accounts' AND attname = 'signup_date';

Output

 brin_size | btree_size 
-----------+------------
 24 kB     | 1712 kB
(1 row)

 correlation 
-------------
           1
(1 row)

A correlation near 1 means the column order matches the physical row order.

Example 12: clustered vs secondary indexes

	InnoDB (MySQL)	PostgreSQL
Table storage	Rows stored inside the primary key B+tree (clustered index)	Rows stored in an unordered heap
Secondary index leaf	Holds the primary key value	Holds the heap location (`ctid`)
Secondary lookup	Two tree walks: secondary, then primary key	One tree walk, then a heap fetch
Range scan on primary key	Rows are adjacent on disk	Rows are adjacent only if inserted in order

SQL Server also has a clustered index (one per table). Oracle uses heap tables by default and offers index-organized tables.

PostgreSQL rows have a physical location, ctid (page number, row number).

SQL

SELECT ctid, id FROM accounts WHERE id IN (1, 2, 3, 200000) ORDER BY id;

Output

   ctid    |   id   
-----------+--------
 (0,1)     |      1
 (0,2)     |      2
 (0,3)     |      3
 (2001,15) | 200000
(4 rows)

Example 13: cost of indexes on writes

Every INSERT and DELETE changes every index on the table. An UPDATE changes an index only if an indexed column changes. Otherwise PostgreSQL can do a HOT update (heap-only tuple), which leaves the indexes untouched. HOT needs free space in the same page, so this table is created with fillfactor = 50.

SQL

CREATE TABLE hot_demo (id int PRIMARY KEY, indexed_col int, plain_col int) WITH (fillfactor = 50);
CREATE INDEX idx_hot_demo_indexed ON hot_demo (indexed_col);
INSERT INTO hot_demo SELECT i, i, i FROM generate_series(1, 1000) AS i;

UPDATE hot_demo SET plain_col = plain_col + 1;

SELECT pg_stat_force_next_flush();
SELECT n_tup_upd, n_tup_hot_upd FROM pg_stat_user_tables WHERE relname = 'hot_demo';

UPDATE hot_demo SET indexed_col = indexed_col + 1;

SELECT pg_stat_force_next_flush();
SELECT n_tup_upd, n_tup_hot_upd FROM pg_stat_user_tables WHERE relname = 'hot_demo';

Output

 pg_stat_force_next_flush 
--------------------------
 
(1 row)

 n_tup_upd | n_tup_hot_upd 
-----------+---------------
      1000 |          1000
(1 row)

 pg_stat_force_next_flush 
--------------------------
 
(1 row)

 n_tup_upd | n_tup_hot_upd 
-----------+---------------
      2000 |          1000
(1 row)

The first update changes an unindexed column, and all updated rows are HOT. The second changes an indexed column, so it adds no HOT updates: every new row version needs a new entry in idx_hot_demo_indexed. Each extra index adds work to every write and uses disk and cache.

Example 14: selectivity and low-cardinality columns

Selectivity is the fraction of rows a condition returns. Cardinality is the number of distinct values. An index pays off when a condition returns a small fraction of the table.

SQL

SELECT attname, n_distinct FROM pg_stats
WHERE tablename = 'accounts' AND attname IN ('id', 'email', 'country', 'status')
ORDER BY attname;

SELECT status, count(*) FROM accounts GROUP BY status ORDER BY status;

Output

 attname | n_distinct 
---------+------------
 country |         10
 email   |         -1
 id      |         -1
 status  |          3
(4 rows)

  status  | count  
----------+--------
 active   | 133200
 banned   |    200
 inactive |  66600
(3 rows)

A negative n_distinct is a fraction of the row count: -1 means every value is distinct. status = 'active' matches two thirds of the table. An index on status gives the planner no benefit for that value.

SQL

DROP INDEX idx_accounts_banned;
CREATE INDEX idx_accounts_status ON accounts (status);
ANALYZE accounts;

EXPLAIN (COSTS OFF) SELECT * FROM accounts WHERE status = 'active';
EXPLAIN (COSTS OFF) SELECT * FROM accounts WHERE status = 'banned';

Output

             QUERY PLAN              
-------------------------------------
 Seq Scan on accounts
   Filter: (status = 'active'::text)
(2 rows)

                    QUERY PLAN                    
--------------------------------------------------
 Index Scan using idx_accounts_status on accounts
   Index Cond: (status = 'banned'::text)
(2 rows)

The same column and index give different plans depending on the value, because the planner reads per-value frequencies from statistics.

Example 15: when the planner ignores an index

Cause	Example
Condition matches a large share of rows	`status = 'active'`
Function or expression on the column	`WHERE balance + 1 = 5000`
Type mismatch that forces a cast on the column	`WHERE id::text = '5'`
Leading wildcard	`LIKE '%abc'`
Table is small	Reading one page is cheaper than an index
Stale statistics	Table changed a lot since `ANALYZE`

SQL

EXPLAIN (COSTS OFF) SELECT * FROM accounts WHERE balance + 1 = 5000;
EXPLAIN (COSTS OFF) SELECT * FROM accounts WHERE id::text = '5';
ANALYZE departments;
EXPLAIN (COSTS OFF) SELECT * FROM departments WHERE name = 'Sales';

Output

            QUERY PLAN            
----------------------------------
 Seq Scan on accounts
   Filter: ((balance + 1) = 5000)
(2 rows)

             QUERY PLAN             
------------------------------------
 Seq Scan on accounts
   Filter: ((id)::text = '5'::text)
(2 rows)

            QUERY PLAN            
----------------------------------
 Seq Scan on departments
   Filter: (name = 'Sales'::text)
(2 rows)

The departments table has 5 rows in one page, so a sequential scan is the cheapest plan even though name has a unique index.

Example 16: unused and duplicate indexes, and index size

Unused indexes cost write time and disk space. pg_stat_user_indexes counts scans per index since the statistics were last reset.

SQL

SELECT pg_stat_force_next_flush();

SELECT s.indexrelname, pg_size_pretty(pg_relation_size(s.indexrelid)) AS size
FROM pg_stat_user_indexes s
JOIN pg_index i ON i.indexrelid = s.indexrelid
WHERE s.relname = 'accounts' AND s.idx_scan = 0 AND NOT i.indisunique
ORDER BY s.indexrelname;

Output

 pg_stat_force_next_flush 
--------------------------
 
(1 row)

        indexrelname         |  size   
-----------------------------+---------
 idx_accounts_country_cover  | 4416 kB
 idx_accounts_country_signup | 1712 kB
 idx_accounts_email          | 7960 kB
 idx_accounts_signup_brin    | 24 kB
 idx_accounts_status         | 1376 kB
 idx_accounts_upper_email    | 7960 kB
(6 rows)

The list shows indexes never scanned since the statistics started. idx_scan counts every scan, including the ones the planner runs to estimate a value range, so a small non-zero count does not prove an index is useful.

Duplicates have the same table, columns, and predicate. After Example 10, idx_accounts_email duplicates uq_accounts_email.

SQL

SELECT indrelid::regclass AS tbl, array_agg(indexrelid::regclass ORDER BY indexrelid::regclass::text) AS duplicate_indexes
FROM pg_index
GROUP BY indrelid, indkey, indpred::text, indexprs::text
HAVING count(*) > 1
ORDER BY 1;

Output

   tbl    |           duplicate_indexes            
----------+----------------------------------------
 accounts | {idx_accounts_email,uq_accounts_email}
(1 row)

Before dropping an index with idx_scan = 0, check that statistics cover a full business cycle (month-end jobs), that the index does not back a constraint, and that replicas do not use it.

Interview questions

Why is a B+tree used? It is balanced, shallow (height 4 to 5 for 10 billion rows), and leaf pages are linked for range scans.
What is the leftmost prefix rule? A composite index serves conditions on its first column, or first two, and so on, but not on later columns alone.
Clustered vs non-clustered? A clustered index defines the physical order of the rows (one per table). A non-clustered index is a separate structure pointing to rows.
Why can an index make a query slower? It adds write cost, and for low-selectivity conditions random table access costs more than a sequential scan.
What is a covering index? An index containing every column a query needs, so no table access is required.
Why is the index ignored? Low selectivity, a function on the column, a type cast, a leading wildcard, a small table, or stale statistics.

Summary

A B+tree lookup reads one page per level; 100 million rows need 3 to 4 levels.
Put equality columns first and range columns last in a composite index. Queries must use a leftmost prefix.
Covering, partial, and expression indexes target specific queries and keep the index small.
Indexes speed up reads and slow down writes. Low-cardinality columns rarely help.
Use pg_stat_user_indexes and pg_relation_size to find unused and oversized indexes.

Next: Query Plans explains how to read EXPLAIN output, and Fixing Slow Queries applies it.