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 <[email protected]> wrote: > 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 > > > >
