One index, 467x faster: reading a PostgreSQL B-tree from the inside

I loaded five million orders into PostgreSQL 18.6 and asked for the 40 that belong to customer 4242. Without an index the query took 54.2 ms. After one CREATE INDEX it took 0.116 ms, which is 467 times faster. This post goes through the two query plans line by line, opens the index with pageinspect to see how deep the tree really is, and lists what the index costs you in return.

Everything below ran in the official Docker image on a laptop. Your timings will be different, but the shape of the plans and the depth of the tree should match.

The numbers, in one table

Setup

Port 5433 on the host, because 5432 was already taken on my machine.

docker run -d --name pg -e POSTGRES_PASSWORD=secret -p 5433:5432 postgres
docker exec -it pg psql -U postgres

psql (18.6 (Debian 18.6-1.pgdg13+2))
Type "help" for help.output

The table has nothing special in it: an id, a customer id, an amount and a timestamp.

CREATE TABLE orders (
  id          bigserial PRIMARY KEY,
  customer_id int NOT NULL,
  amount      numeric(10,2),
  created_at  timestamptz DEFAULT now()
);
INSERT INTO orders (customer_id, amount) VALUES (4242, 59.90);

Then five million random orders. customer_id is a random number up to 100,000, so each customer ends up with about 50 orders. Customer 4242 has 40, counting the one I inserted by hand.

\timing
INSERT INTO orders (customer_id, amount, created_at)
SELECT (random()*100000)::int,
       round((random()*500)::numeric, 2),
       now() - random() * interval '365 days'
FROM generate_series(1, 5000000);
ANALYZE orders;

INSERT 0 5000000
Time: 8890.199 ms (00:08.890)
ANALYZE
Time: 548.042 msoutput

ANALYZE matters here. The planner decides between a sequential scan and an index scan from the table statistics, and right after a bulk insert those statistics are out of date.

Plan 1: no index

EXPLAIN (ANALYZE, COSTS OFF, BUFFERS OFF)
SELECT * FROM orders WHERE customer_id = 4242;

 Gather (actual time=0.431..54.169 rows=40.00 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Seq Scan on orders (actual time=1.917..51.563 rows=13.33 loops=3)
         Filter: (customer_id = 4242)
         Rows Removed by Filter: 1666654
 Planning Time: 0.117 ms
 Execution Time: 54.199 msoutput

How to read it, from the inside out:

• Parallel Seq Scan, loops=3. Two background workers plus the main process split the table into three parts. Each one reads its share of the pages and checks every row against the filter.
• Rows Removed by Filter: 1666654. This number is per process. Three processes times about 1.67 million is the whole table: five million rows read and thrown away to keep 40.
• rows=13.33. Also an average per process: 40 rows found, divided by three.
• Gather. Collects the rows from the three processes into one result.

BUFFERS OFF is there because since PostgreSQL 18, EXPLAIN ANALYZE prints buffer statistics by default. I turned them off to keep the output short. The decimals in rows=40.00 are also new in 18.

Parallel workers make this faster than a single process would be, but they do not change how much work there is. The query time grows with the size of the table, not with the size of the result.

The index

CREATE INDEX orders_customer_idx ON orders (customer_id);

CREATE INDEX
Time: 783.994 msoutput

CREATE INDEX without a type gives you a B-tree, the default in PostgreSQL. A B-tree is a tree of 8 KB pages:

• Leaf pages at the bottom hold every customer_id in sorted order, each with a pointer (a TID: page number and position) to the row in the table.
• Inner pages above them hold only boundaries that say which child page covers which range of keys.
• One root page at the top.

A lookup starts at the root and follows one child per level until it reaches a leaf. Leaf pages are also linked to their neighbours, so a range condition like customer_id BETWEEN 4000 AND 4300 finds the first key and then walks sideways.

Plan 2: with the index

 Bitmap Heap Scan on orders (actual time=0.024..0.093 rows=40.00 loops=1)
   Recheck Cond: (customer_id = 4242)
   Heap Blocks: exact=40
   ->  Bitmap Index Scan on orders_customer_idx (actual time=0.013..0.013 rows=40.00 loops=1)
         Index Cond: (customer_id = 4242)
         Index Searches: 1
 Planning Time: 0.138 ms
 Execution Time: 0.116 msoutput

This plan has two steps:

1. Bitmap Index Scan. One descent of the tree (Index Searches: 1, another field that is new in PostgreSQL 18) finds the 40 matching keys and their TIDs. It took 0.013 ms.
2. Bitmap Heap Scan. The TIDs are sorted by page, and then those table pages are read in physical order.

Heap Blocks: exact=40 is the line I find most useful. The 40 orders sit on 40 different table pages. That makes sense: apart from the first one, they were generated at random positions among five million inserts. So the index turned “read every page of a 287 MB table” into “read a few index pages and 40 table pages”.

Recheck Cond is listed because a bitmap can become lossy when it runs out of memory. Then it only remembers whole pages, and the rows have to be checked again. Here every block was exact, so no rows were rechecked.

The planner chose a bitmap scan over a plain index scan. For a handful of rows spread across many pages, the two are close. The planner picks from its cost estimates, and with a different number of matching rows it may choose a plain Index Scan.

How deep is the tree?

The pageinspect extension can read index pages directly. bt_metap reads the metapage of a B-tree:

CREATE EXTENSION pageinspect;
SELECT level, root FROM bt_metap('orders_customer_idx');

 level | root
-------+------
     2 |  290output

Leaves are level 0, so a root at level 2 means three levels: root, one level of inner pages, leaves. Five million keys fit in a tree that is three pages deep, because each 8 KB page holds hundreds of keys. Every lookup reads the root, one inner page and one leaf.

The tree also grows slowly. Each extra level multiplies the capacity by a few hundred, so this table could grow a lot before a fourth level appears.

What the index costs

SELECT pg_size_pretty(pg_relation_size('orders'))              AS table,
       pg_size_pretty(pg_relation_size('orders_customer_idx')) AS index;

 table  | index
--------+-------
 287 MB | 34 MBoutput

• Disk and memory. 34 MB is about 12% of the table, for one integer column. The index pages also compete with table pages for the shared buffer cache.
• Writes. Every INSERT now adds a key to the tree too. An UPDATE can avoid touching the index only when no indexed column changes and the new row version fits on the same page (a HOT update).
• Building it. 784 ms here. A plain CREATE INDEX blocks writes to the table while it runs. On a production table, CREATE INDEX CONCURRENTLY avoids that, but it takes longer and cannot run inside a transaction.

So index the columns your queries actually filter or join on, and check with EXPLAIN ANALYZE that the plan uses the index.

Repeat it yourself

docker run -d --name pg -e POSTGRES_PASSWORD=secret -p 5433:5432 postgres
docker exec -it pg psql -U postgres

CREATE TABLE orders (id bigserial PRIMARY KEY, customer_id int NOT NULL,
  amount numeric(10,2), created_at timestamptz DEFAULT now());
INSERT INTO orders (customer_id, amount, created_at)
SELECT (random()*100000)::int, round((random()*500)::numeric, 2),
       now() - random() * interval '365 days'
FROM generate_series(1, 5000000);
ANALYZE orders;

EXPLAIN (ANALYZE, COSTS OFF, BUFFERS OFF) SELECT * FROM orders WHERE customer_id = 4242;
CREATE INDEX orders_customer_idx ON orders (customer_id);
EXPLAIN (ANALYZE, COSTS OFF, BUFFERS OFF) SELECT * FROM orders WHERE customer_id = 4242;

CREATE EXTENSION pageinspect;
SELECT level, root FROM bt_metap('orders_customer_idx');
SELECT pg_size_pretty(pg_relation_size('orders')), pg_size_pretty(pg_relation_size('orders_customer_idx'));

Because the data is random, customer 4242 will have a different number of orders on your machine. Any customer id below 100,000 works.

docker rm -f pg

Sources

• B-tree indexes (PostgreSQL docs)
• Using EXPLAIN (PostgreSQL docs)
• Bitmap scans and combining indexes (PostgreSQL docs)
• pageinspect (PostgreSQL docs)
• CREATE INDEX, including CONCURRENTLY (PostgreSQL docs)
• Heap-only tuples (HOT) (PostgreSQL docs)
• PostgreSQL 18 release notes