Subject: Index scan with bitmap filter - has this been explored

From: Laurence Newman <[email-masked]>
Date: Fri, 13 Mar 2026 12:08:59 +0000

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

---

From: Tomas Vondra <[email-masked]>
Date: Mon, 16 Mar 2026 00:38:54 +0100

Hello Laurence,

I think pgsql-hackers would be a better list to discuss this.
pgsql-general is a user list, while pgsql-hakers is about development.
So I'm CCing that list, and let's continue the discussion there (you may
need to subscribe to that list, if you're not a subscriber already).

FWIW we're in the final push for PG19 features, so people are focusing o
that for the next ~month. It may take time to get feedback.

On 3/13/26 13:08, Laurence Newman wrote:
> bitmap scan and an  index scan, and I wanted to check whether this has
> been explored before much or if there's a

I'm not aware of any formal implementation proposal, but that does not
mean it couldn't be a good idea (at least for some use cases).

> 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:
> 
>     2. Index scan on the B-tree → recheck the filter condition against
> the heap for each

There's also the possibility to create a an index with all the columns
(aka covering index), in which case we don't need to actually visit the
heap in most cases thanks to IOS.

But that is imperfect for various reasons - sometimes the index can't
have all the columns, and then we don't check any filters. That could be
improved without inventing a new "hybrid" scan.

But even then there are cases where doing what you describe could be
interesting. For example, it'd allow combining indexes with different
index AMs (e.g. btree + gist). Which covering indexes can't do easily.

Something similar applies to vector search, where I'm not sure covering
indexes are viable. Maybe allowing to pass a bitmap to the index scan
would be helpful.

> 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

It's hard to give clear opinion without looking at this much deeper, but
it seems interesting and possibly worth exploring.

> 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 <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 think it'd be helpful to include at least some benchmark numbers, so
that people can get an idea without having to build/run.

> (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.
> 

I'm not aware of any prior discussions or reasons why this would not
work (or be competitive with other solutions). I think there's
definitely a lot of open questions. It's not just about the execution,
but also about generating the interesting paths (with indexes used as
inputs for other indexes) and costing.

regards

-- 
Tomas Vondra

---

From: Alexandre Felipe <[email-masked]>
Date: Fri, 20 Mar 2026 13:43:43 +0000

That is a sound idea.
There are some middle ground that this would cover some middle ground.

Will we rewrite postgres in rust? No more need for resource owner tracking!

> it seems interesting and possibly worth exploring.

I have a lower reputation at stake, so I can write some opinions :)

Laurence,
It might be obvious for some, but I will write it either way:
This could be implemented as an execution node instead of an index
access method. The next step would be to update the planner to
choose the new node when it is advantageous doing so.

My suggestion is to have a GUC parameter so that you can easily
enable or disable it, then you can run benchmarks and see how much
it helps. If it hurts you blame (or fix) the planner. Having one more
tool can't make the chosen query execution worse. And the planning
time difference should be negligible.

As said in the repository README.md

> Bitmap scan on the GIN index — finds all matching rows and then
> heap-fetch every match, sort them by created_at, and return the top
> 10. If there are many matching rows then this can be expensive.

> B-tree index scan on created_at — walks rows in order and checks
> each one against the text search condition. If there are many
> non-matching rows then it can be expensive finding 10 hits.

The proposed alternative is to access two indices before checking the
table data. So the savings must come from either, (1) sorting cost,
very small for top 10, (2) wasted table heap page access.

#A
GIN -> bitmap -> heap.
(GIN + Bitmap + Heap) * NumMatches + TopNSort
say (g + b + h) * n1 + n1 * log(t) * x

#B
(Index + Heap + @@) * (rows after oldest match), assuming no cover index.
say (s + h + r + @@) * n2

#C
ordered-bitmap-scan
(Gin + Bitmap) * NumMatches + (Index * (rows after oldest match))
(g + b) * n1 + s * n2 + t * h

> If there are many
> non-matching rows then it can be expensive finding 10 hits.

This problem is still there, the difference is that the cost per
non-matching
row is reduced.

Let's think in one dimension taking, if n2 is small, #B < #A < #C. If n2 is
too large
#C > #B > #A. So at both ends your method is worse than what is already
there.

So when is it promising?

When the term h * n1 dominates in the bitmap scan, and h * n2 dominates
in the index scan. If the documents are toasted, and we have mostly
appended documents the scan will be mostly sequential, but backwards.

You have to consider the selectivity of the tsvector filter,
to the speedup potential (I would start with cost(IndexOnlyScan) /
cost(IndexScan)).

For your example, when you are accessing the most recent examples if
the collection has mostly appends, that is similar to a sequential scan
but backwards.

Tomas,
do we currently combine I/O when the index fetches pages backwards
p, p-1, p-2, ... instead of p, p+1, p+2, ...

If the bitmap is sparse enough the bitmap index scan will behave as
a random access pattern. So let's assume everything to be random
from now on.

For the sake of example,
Let's assume that the cost of an index only scan is 100x lower than fetching
a tsvector from a row.
And let's assume that the matching documents are distributed uniformly
among the rest of the table.

The proposed approach could be up to 100x faster (when all documents match)
But if only 0.1% matches, then just the index scan would be 10x slower.
Because you can't jump to the next match without checking all the matches
in between.

Regards,
Alexandre