Hello,
I've been thinking about a scan strategy that is sort of in between a bitmap scan and an index scan, and I wanted to check whether this has been explored before much or if there's a
reason it wouldn't work well in practice.
Example scenario where it could be useful: you need the first N rows ordered by a B-tree column, filtered by a condition on another column with a GIN index, e.g. full text search. Today I believe Postgres has two options that use indexes:
1. Bitmap scan on the filter index → heap fetch all matches → sort → limit. Can be expensive
when there are many matches but you only want a few results returned.
2. Index scan on the B-tree → recheck the filter condition against the heap for each
row. Can be expensive when the match rate is low and many non-matching rows are found before finding N hits.
The idea for the new scan strategy is: build the TID bitmap from the filter index first (same as a bitmap scan would), then walk the B-tree in order, but instead of going to the heap to check the
filter condition, check each TID against the bitmap. Matching TIDs get returned
directly in order.
I built a small proof of concept as a pgrx extension against PG 18 to try and test this:
https://github.com/lauri3new/ordered-bitmap-scan. The benchmarks there show it using fewer buffer hits than either a bitmap scan or index scan for the example data distribution - which is quite skewed to show the benefit.
I want to caveat that I am a web backend developer and not a Postgres expert by any means, so there's probably good reasons this isn't a thing (planner cost or benefit is too small/niche). I would appreciate though any pointers to prior discussion or feedback on whether this is worth looking into further or not.
Thanks
