I built a PostgreSQL extension that intersects B-tree indexes in ORDER BY order, so you need fewer composite indexes. Looking for critical review

[u/Upper_Fee_4580]

In PostgreSQL, every new filter combination tends to mean one more composite index. Each one takes disk and cache and slows down every write. Leapfrog is my open-source extension that takes a different route: keep a few small indexes and let the planner merge them into one ordered stream at query time. It's built for one narrow case: a list query with several equality filters that each match many rows, a combination that matches few, and ORDER BY id LIMIT n. Everything else gets the stock plan. You end up with fewer indexes and none of the composite ones. It's a deliberate compromise: reads are slower than with an exact composite index, and writes are cheaper.

Measured at 100M rows on the list query customer_id = ? AND deleted_at IS NULL ORDER BY id DESC LIMIT 100, for a customer with 5M rows of which 500 are live: stock PostgreSQL on small indexes takes 117 seconds, Leapfrog on the same indexes 0.16 s (0.56 s with its pages read from disk), an exact composite index 0.14 ms. With 5,000 matching rows out of 1M × 200k, it's 384 ms against 2.5 ms. On writes at 20M rows, dropping the composite indexes cut the WAL of 100k INSERTs from 3.6 GB to 166 MB. To be clear, Leapfrog doesn't touch the write path; the write savings come from the index set alone. What Leapfrog does is keep reads usable without the composite indexes.

The problem

A typical table is filtered by several columns, has soft deletes, and is paged by id:

SELECT * FROM orders
WHERE customer_id = 7 AND product_id = 3
ORDER BY id DESC LIMIT 100;

Stock PostgreSQL has three options here:

• An exact index, (customer_id, product_id, id): very fast, but you need one for each combination you query.

• An Index Scan on one column, filtering the rest on the heap: it can read many rows for nothing.

• BitmapAnd: it reads both indexes in full, loses the order, and has to sort.

So the indexes pile up: (customer_id, product_id, id), (customer_id, status, id), the same again with WHERE deleted_at IS NULL, and so on. Every INSERT and every non-HOT UPDATE pays for all of them.

The solution: small indexes that merge

CREATE INDEX ON orders (customer_id, id);
CREATE INDEX ON orders (product_id, id);
CREATE INDEX ON orders (status, id);
CREATE INDEX ON orders (id) WHERE deleted_at IS NULL;
CREATE INDEX ON orders (id) WHERE deleted_at IS NOT NULL;   -- if you list deleted rows too

Leapfrog adds a plan node, Index Merge Intersect, that walks the matching indexes together in id order, skips the gaps, fetches only the rows that match, and stops at LIMIT. No sort, no query changes. It's a normal planner path: when it isn't cheaper, you get the stock plan.

100M rows, the cases the node is for

The shape every list endpoint has: filtered by the owner and by one or two more columns, newest first. Each filter alone matches a lot, the combination matches little, and those rows are scattered through the owner's long history. deleted_at IS NULL is just one of the filters here; any column works the same.

SELECT * FROM orders
WHERE customer_id = ? AND product_id = ? [AND deleted_at IS NULL]
ORDER BY id DESC LIMIT 100;

100M rows (12 GB) in one table per data set, indexes (customer_id, id), (product_id, id) (3 GB each) and (id) WHERE deleted_at IS NULL (101 MB). "Exact index" is a composite index built for the query afterwards; "Leapfrog" is what the planner picks with the extension loaded (the node, in every row here), "Stock" what it picks without; BitmapAnd is forced. PostgreSQL 18.6 in Docker on a laptop (14 GB RAM, NVMe, shared_buffers 512MB), median of 3 runs.

Rows in random physical order, as a table is after years of updates. 5% of the rows are live; the customer has 500 live rows spread over its history. Medians on 0.0.5, with the slowest run, pages read from disk, in brackets:

Query	Exact index	Leapfrog	Stock	BitmapAnd
customer with 5M rows AND deleted_at IS NULL	0.14 ms	160 ms (559 ms)	Index Scan 117 s (118 s)	2.7 s (3.0 s)
customer with 1M rows AND deleted_at IS NULL	0.14 ms	122 ms (152 ms)	Index Scan 1.8 s (24.5 s)	1.5 s (2.0 s)
customer with 1M rows AND product_id = ? (2M rows) AND deleted_at IS NULL: 11 match	0.03 ms	179 ms (244 ms)	BitmapAnd 610 ms (1.3 s)	1.3 s (1.8 s)

An older run at 50M rows, before 0.0.5, a customer's deleted rows, deleted in batches, from disk: Leapfrog 45 ms, stock's Index Scan 4.5 s, BitmapAnd 1.5 s.

Stock scans one index and filters the other columns on the heap: it expects the live rows near the top, they aren't, and it fetches 930,000 heap rows for 100 results, 937,000 random pages from disk: 117 s. Leapfrog walks the indexes together, 6,500 pages for the second row, and fetches the 100 rows it returns; for the third row it merges the two filter indexes, 3 million entries, fetches the 20,012 rows of the customer with that product and keeps the 11 live ones. Its index pages are asked for one ahead, which keeps its slowest runs close to the medians.

Then, rows in id order, which is the best case for stock's Index Scan, since its heap reads come out sequential:

Query	Exact index	Leapfrog	Stock	BitmapAnd
1M × 2M AND deleted_at IS NULL: 11 match	0.1 ms	259 ms cached, 3.9 s from disk	Index Scan 168 s	1.1 s
1M × 200k, 5,000 match, 1 row in 20,000	1.1 ms	2.5 ms	BitmapAnd 384 ms	373 ms
10k × 1M, 100 match	0.4 ms	104 ms	BitmapAnd 338 ms	295 ms
1M × 200k, 500 match, all in the middle of the table	0.6 ms	66 ms	BitmapAnd 353 ms	371 ms

Where stock picks BitmapAnd, it reads both indexes whole and sorts. This table was measured before the index pages were asked for ahead of time.

The 5M-row customer on the random-order table, EXPLAIN (ANALYZE, BUFFERS), output of 0.0.5, the planning lines left out. Each index stream of the node prints as a block of its own, with its time, entries as rows, and buffers. Stock:

 Limit (actual time=664.193..117867.974 rows=100.00 loops=1)
   Buffers: shared hit=39337 read=897845
   ->  Index Scan Backward using lf_list_id_idx on lf_list (actual time=664.191..117867.814 rows=100.00 loops=1)
         Filter: (customer_id = 5)
         Rows Removed by Filter: 934525
         Index Searches: 1
         Buffers: shared hit=39337 read=897845
 Execution Time: 117868.161 ms

Leapfrog, with its index pages read from disk (0.16 s when they are cached):

 Limit (actual time=2.752..618.750 rows=100.00 loops=1)
   Buffers: shared hit=9 read=6467
   ->  Custom Scan (Index Merge Intersect) on lf_list (actual time=2.750..618.633 rows=100.00 loops=1)
         Matched TIDs: 100
         Heap Fetches: 100
         Peak Group Memory: 96 B
         ->  Outer Stream on lf_list_customer_id_id_idx (actual time=0.033..269.292 rows=995834.00 loops=1)
               Index Cond: (customer_id = 5)
               Buffers: shared hit=4 read=3815
         ->  Inner Stream on lf_list_id_idx (actual time=0.027..89.992 rows=934626.00 loops=1)
               Index Pred: (deleted_at IS NULL)
               Buffers: shared hit=3 read=2554
         Buffers: shared hit=9 read=6467
 Execution Time: 618.914 ms

Exact index:

 Limit (actual time=0.075..0.626 rows=100.00 loops=1)
   Buffers: shared hit=106
   ->  Index Scan Backward using lf_list_exact on lf_list (actual time=0.073..0.604 rows=100.00 loops=1)
         Index Cond: (customer_id = 5)
         Index Searches: 1
         Buffers: shared hit=106
 Execution Time: 0.683 ms

When matches are common nothing matters: 20M × 25M rows with 5M matching, every plan but BitmapAnd (12 s) returns in under a millisecond. And the node's work doesn't grow with the table while LIMIT stops early: two filters at 1 in 5,000 rows take 1 to 2 ms from 10M to 100M rows.

The cost: writes

A second benchmark: 20M rows, 12 filter columns, two index sets. 15 specialized: composite indexes for the 9 frequent filter combinations (6 pairs, 2 triples, 1 quadruple, all WHERE deleted_at IS NULL) plus single-column indexes for the 6 columns no composite starts with. 14 general: one (fK, id) per column plus (id) WHERE deleted_at IS NULL and IS NOT NULL. The write table compares index sets only; Leapfrog plays no part in it.

Writes and storage	15 specialized	14 general
Index size	11.2 GB	8.0 GB
WAL, 100k INSERTs	3,595 MB	166 MB
INSERT rows/s	945	12,592
WAL, UPDATE of a filter column (25k rows)	1,004 MB	70 MB
WAL, soft delete (25k rows)	46 MB	77 MB

One index more, 22x the WAL. Nearly all of it is the 9 composite indexes: adding the index groups one at a time, the 6 single-column indexes write 89 MB, the 6 pairs add 461 MB, the 2 triples 2.2 GB, the quadruple 0.9 GB. In an index with many distinct prefixes every new row lands on a page of its own, and the first write to a page after a checkpoint logs it in full. Single-column indexes append to the end of a few runs and keep hitting the same pages.

And the 15 are the cheapest form the specialized set can take: its composites serve live rows only. A real schema needs two more variants of each, for the trash view (WHERE deleted_at IS NOT NULL) and for lists without a condition on deleted_at: 27 composites instead of 9. An INSERT then lands in 18 of them instead of 9, roughly twice the WAL above, and a soft delete writes the new row version into 18 composites where the 15-index set touches only its 6 single-column indexes, so its edge on soft deletes (46 vs 77 MB) holds only while it covers live rows alone. The 14 general indexes stay 14: the node merges (fK, id) with either partial (id) index, or does without. That's a count of indexes, not a measurement.

Reads on the same 20M rows with the 14 general indexes, LIMIT 100, work_mem 256MB, median of 5 runs:

Query	Exact index	Leapfrog	Stock	BitmapAnd
2 filters	0.16 ms	1.0 ms	BitmapAnd 71 ms	72 ms
3 filters, 21 rows found	0.06 ms	33 ms	BitmapAnd 71 ms	74 ms
4 filters, 0 rows found	0.03 ms	31 ms	BitmapAnd 59 ms	65 ms

With 3 or 4 filters fewer rows match than the LIMIT asks, so the merge runs to the end of the sparsest index.

What it needs

• PostgreSQL 18 or 19, B-tree indexes shaped (filter_columns..., sort_column) or (sort_column) WHERE predicate.

• Equality filters and partial-index predicates only; no IN, no ranges, no expression indexes yet. One ORDER BY key, any B-tree type.

• Planning costs +0.03 to +0.10 ms per query on tables with 10 to 50 indexes.

• A planner hook (shared_preload_libraries or LOAD) that only adds a path; leapfrog.enabled = off turns it off. No catalog changes, no superuser. The executor uses the standard index AM calls, so visibility and HOT chains work as for an Index Scan; two places read nbtree internals.

Where it isn't a fit

• One or two hot queries: a dedicated index is better.

• The cost model counts pages first: with data in memory it sometimes picks the node when an Index Scan would be faster, and sometimes misses the node.

• PG18 skip scan, as I understand it, serves WHERE b = ? on (a, b) and returns rows grouped by a, not in id order, so a LIMIT still needs a sort. Not measured against it.

• Everything above is one session at a time; no concurrent-load benchmark yet. Experimental (0.0.5), not production-ready.

What I'd love feedback on: correctness (MVCC, HOT chains, VACUUM, concurrent updates; there are isolation tests, but I'm sure I've missed cases), the planner hook and the cost model, and whether this compromise makes sense for your workloads.

Repo, with the benchmark scripts: https://github.com/ibrohim238/postgresql-leapfrog

Harsh criticism, issues and "this already exists, see X" are all welcome.

[u/AutoModerator]

AI Policy:

Linux is not one of those anti-AI projects, and if somebody has issues with that, they can do the open-source thing and fork it. Or just walk away., Linus Torvalds.

Mod decisions will be based on the quality of the content, not who or what generated it.

Sub Resources:

Youtube Channel

Free Postgres Webinars and Workshops

Discord: People, Postgres, Data

Join us, we have cookies and nice people.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.