Re: Index scan with bitmap filter - has this been explored
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:
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.
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).
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.
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
filter condition, check each TID against the bitmap. Matching TIDs get
returned
directly in order.
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.
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.
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
Import Notes
Reply to msg id not found: CAHueFRVqNuKQ0+LQPZVwMgJ+LpuTbZ21+ztwFbgPhBf9maFGYA@mail.gmail.comReference msg id not found: CAHueFRVqNuKQ0+LQPZVwMgJ+LpuTbZ21+ztwFbgPhBf9maFGYA@mail.gmail.com
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's hard to give clear opinion without looking at this much deeper, but
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
On Mon, Mar 16, 2026 at 9:24 PM Tomas Vondra <tomas@vondra.me> wrote:
Show quoted text
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:
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.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).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.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
filter condition, check each TID against the bitmap. Matching TIDs get
returned
directly in order.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.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.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