MIME-Version: 1.0
References: <CAHueFRVqNuKQ0+LQPZVwMgJ+LpuTbZ21+ztwFbgPhBf9maFGYA@mail.gmail.com>
 <f816bcdd-ad77-4538-a2dd-136c1e389c2e@vondra.me>
In-Reply-To: <f816bcdd-ad77-4538-a2dd-136c1e389c2e@vondra.me>
From: Alexandre Felipe <o.alexandre.felipe@gmail.com>
Date: Fri, 20 Mar 2026 13:43:43 +0000
Message-ID: <CAE8JnxOsU60o3PWkxiWPUfXBJNY0BNOmwQfULiuoFY_hL4t4SA@mail.gmail.com>
Subject: Re: Index scan with bitmap filter - has this been explored
To: Tomas Vondra <tomas@vondra.me>
Cc: Laurence Newman <lenewman05@googlemail.com>, pgsql-general@postgresql.org, 
	PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Content-Type: multipart/alternative; boundary="0000000000005d6065064d74e0af"
Archived-At: <https://www.postgresql.org/message-id/CAE8JnxOsU60o3PWkxiWPUfXBJNY0BNOmwQfULiuoFY_hL4t4SA%40mail.gmail.com>
Precedence: bulk

--0000000000005d6065064d74e0af
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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 =E2=80=94 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 =E2=80=94 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 fetchin=
g
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=E2=80=AFPM Tomas Vondra <tomas@vondra.me> wrot=
e:

> 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 =E2=86=92 heap fetch all matches=
 =E2=86=92 sort =E2=86=92
> > limit. Can be expensive
> >  when there are many matches but you only want a few results returned.
> >     2. Index scan on the B-tree =E2=86=92 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 fewe=
r
> > buffer hits than either a bitmap scan or index scan for the example dat=
a
> > 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 thin=
g
> > (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
>
>
>
>

--0000000000005d6065064d74e0af
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>That is a sound idea.</div><div>There are some middle=
 ground that this would cover some middle ground.</div><div><br></div><div>=
Will we rewrite postgres in rust? No more need for resource owner tracking!=
</div><div><br></div><div>&gt; It&#39;s hard to give clear opinion without =
looking at this much deeper, but<br>&gt; it seems interesting and possibly =
worth exploring.</div><div><br></div><div>I have a lower reputation at stak=
e, so I can write some opinions :)</div><div><br></div><div>Laurence,</div>=
<div>It might be obvious for some, but I will write it either way:</div><di=
v>This could be implemented as an execution node instead of an index=C2=A0<=
/div><div>access method. The next step would be to update the planner to</d=
iv><div>choose the new node when it is advantageous=C2=A0doing so.</div><di=
v><br></div><div>My suggestion is to have a GUC parameter so that you can e=
asily</div><div>enable or disable it, then you can run benchmarks and see h=
ow much</div><div>it helps. If it hurts you blame (or fix) the planner. Hav=
ing one more</div><div>tool can&#39;t make the chosen=C2=A0query execution =
worse. And the planning</div><div>time difference should be negligible.</di=
v><div><br></div><div>As said in the repository README.md</div><div><br></d=
iv><div>&gt; Bitmap scan on the GIN index =E2=80=94 finds all matching rows=
 and then</div><div>&gt; heap-fetch every match, sort them by created_at, a=
nd return the top=C2=A0</div><div>&gt; 10. If there are many matching rows =
then this can be expensive.<div><br></div><div>&gt; B-tree index scan on cr=
eated_at =E2=80=94 walks rows in order and checks=C2=A0</div><div>&gt; each=
 one against the text search condition. If there are many=C2=A0</div><div>&=
gt; non-matching rows then it can be expensive finding 10 hits.</div><div><=
div><br></div><div>The proposed alternative is to access two indices before=
 checking the</div><div>table data. So the savings must come from either, (=
1) sorting cost,</div><div>very small for top 10, (2) wasted table heap pag=
e access.</div><div><br></div><div>#A</div><div>GIN -&gt; bitmap -&gt; heap=
.</div><div>(GIN=C2=A0+ Bitmap=C2=A0+ Heap) * NumMatches=C2=A0+ TopNSort</d=
iv><div>say (g=C2=A0+ b=C2=A0+ h) * n1=C2=A0+ n1 * log(t) * x</div><div><br=
></div><div>#B</div><div>(Index=C2=A0+ Heap + @@) * (rows after oldest matc=
h), assuming no cover index.</div><div>say (s=C2=A0+ h + r=C2=A0+ @@) * n2<=
/div><div><br></div><div>#C</div><div>ordered-bitmap-scan</div><div>(Gin=C2=
=A0+ Bitmap) * NumMatches=C2=A0+ (Index * (rows after oldest match))</div><=
div>(g=C2=A0+ b) * n1=C2=A0+ s * n2=C2=A0+ t * h</div><div><br></div><div><=
div>&gt; If there are many=C2=A0</div><div>&gt; non-matching rows then it c=
an be expensive finding 10 hits.</div></div><div><br></div><div>This proble=
m is still there, the difference is that the cost per non-matching</div><di=
v>row is reduced.=C2=A0</div><div><br></div><div>Let&#39;s think in one dim=
ension taking, if n2 is small, #B &lt; #A &lt; #C. If n2 is too large</div>=
<div>#C &gt; #B &gt; #A. So at both ends your method is worse than what is =
already there.</div><div><br></div><div>So when is it promising?</div><div>=
<br></div><div><br></div><div>When the term h * n1 dominates in the bitmap =
scan, and h * n2 dominates=C2=A0</div><div>in the index scan. If the docume=
nts are toasted, and we have mostly=C2=A0</div><div>appended documents the =
scan will be mostly sequential, but backwards.</div><div><br></div><div>You=
 have to consider the selectivity of the=C2=A0tsvector filter,</div><div>to=
 the speedup potential (I would start with cost(IndexOnlyScan) / cost(Index=
Scan)).</div><div><br></div><div>For your example, when you are accessing t=
he most recent examples if=C2=A0</div><div>the collection has mostly append=
s, that is similar to a sequential scan</div><div>but backwards.</div><div>=
<div><br></div><div>Tomas,</div><div>do we currently combine I/O when the i=
ndex fetches pages backwards</div><div>p, p-1, p-2, ... instead of p, p+1, =
p+2, ...</div><div><br></div><div>If the bitmap is sparse enough the bitmap=
 index scan will behave as</div><div>a random access pattern. So let&#39;s =
assume everything to be random</div><div>from now on.</div><div><br></div><=
div>For the sake of example,=C2=A0</div><div>Let&#39;s assume that the cost=
 of an index only scan is 100x lower than fetching</div><div>a tsvector fro=
m a row.</div><div>And let&#39;s assume that the matching documents are dis=
tributed uniformly</div><div>among the rest of the table.</div><div><br></d=
iv><div>The proposed approach could be up to 100x faster (when all document=
s match)</div><div>But if only 0.1% matches, then just the index scan would=
 be 10x slower.</div><div>Because you can&#39;t jump to the next match with=
out checking all the matches</div><div>in between.</div><div><br></div><div=
><br></div><div>Regards,</div><div>Alexandre</div><div><br></div><div><br><=
/div><div><br></div><div><br></div><div><br></div></div></div></div><div><b=
r></div></div><br><div class=3D"gmail_quote gmail_quote_container"><div dir=
=3D"ltr" class=3D"gmail_attr">On Mon, Mar 16, 2026 at 9:24=E2=80=AFPM Tomas=
 Vondra &lt;<a href=3D"mailto:tomas@vondra.me">tomas@vondra.me</a>&gt; wrot=
e:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0=
.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hello Laurenc=
e,<br>
<br>
I think pgsql-hackers would be a better list to discuss this.<br>
pgsql-general is a user list, while pgsql-hakers is about development.<br>
So I&#39;m CCing that list, and let&#39;s continue the discussion there (yo=
u may<br>
need to subscribe to that list, if you&#39;re not a subscriber already).<br=
>
<br>
FWIW we&#39;re in the final push for PG19 features, so people are focusing =
o<br>
that for the next ~month. It may take time to get feedback.<br>
<br>
On 3/13/26 13:08, Laurence Newman wrote:<br>
&gt; Hello,<br>
&gt; <br>
&gt; I&#39;ve been thinking about a scan strategy that is sort of in betwee=
n a<br>
&gt; bitmap scan and an=C2=A0 index=C2=A0scan, and I wanted to check whethe=
r this has<br>
&gt; been explored before much or if there&#39;s a<br>
&gt; reason it wouldn&#39;t work well in practice.<br>
&gt; <br>
<br>
I&#39;m not aware of any formal implementation proposal, but that does not<=
br>
mean it couldn&#39;t be a good idea (at least for some use cases).<br>
<br>
&gt; Example scenario where it=C2=A0could be useful: you need the first N r=
ows<br>
&gt; ordered by a B-tree column, filtered by a condition on another column<=
br>
&gt; with a GIN index, e.g. full text search. Today I believe Postgres has<=
br>
&gt; two options that use indexes:<br>
&gt; <br>
&gt; =C2=A0 =C2=A0 1. Bitmap scan on the filter index =E2=86=92 heap fetch =
all matches =E2=86=92 sort =E2=86=92<br>
&gt; limit. Can be expensive<br>
&gt; =C2=A0when there are many matches but you only want a few results retu=
rned.<br>
&gt; =C2=A0 =C2=A0 2. Index scan on the B-tree =E2=86=92 recheck the filter=
 condition against<br>
&gt; the heap for each<br>
&gt; =C2=A0row. Can be expensive when the match rate is low and many non-ma=
tching<br>
&gt; rows are found before=C2=A0finding N hits.<br>
&gt; <br>
<br>
There&#39;s also the possibility to create a an index with all the columns<=
br>
(aka covering index), in which case we don&#39;t need to actually visit the=
<br>
heap in most cases thanks to IOS.<br>
<br>
But that is imperfect for various reasons - sometimes the index can&#39;t<b=
r>
have all the columns, and then we don&#39;t check any filters. That could b=
e<br>
improved without inventing a new &quot;hybrid&quot; scan.<br>
<br>
But even then there are cases where doing what you describe could be<br>
interesting. For example, it&#39;d allow combining indexes with different<b=
r>
index AMs (e.g. btree + gist). Which covering indexes can&#39;t do easily.<=
br>
<br>
Something similar applies to vector search, where I&#39;m not sure covering=
<br>
indexes are viable. Maybe allowing to pass a bitmap to the index scan<br>
would be helpful.<br>
<br>
&gt; The idea for the new scan strategy is: build the TID bitmap from the<b=
r>
&gt; filter index first (same as a bitmap scan would), then walk the B-tree=
<br>
&gt; in order, but instead of going to the heap to check the<br>
&gt; filter condition, check each TID against the bitmap. Matching TIDs get=
<br>
&gt; returned<br>
&gt; directly in order.<br>
&gt; <br>
<br>
It&#39;s hard to give clear opinion without looking at this much deeper, bu=
t<br>
it seems interesting and possibly worth exploring.<br>
<br>
&gt; I built a small proof of concept as a pgrx extension against PG 18 to<=
br>
&gt; try and test this:<br>
&gt; <a href=3D"https://github.com/lauri3new/ordered-bitmap-scan" rel=3D"no=
referrer" target=3D"_blank">https://github.com/lauri3new/ordered-bitmap-sca=
n</a> &lt;<a href=3D"https://github.com/" rel=3D"noreferrer" target=3D"_bla=
nk">https://github.com/</a><br>
&gt; lauri3new/ordered-bitmap-scan&gt;. The benchmarks there show it using =
fewer<br>
&gt; buffer hits than either a bitmap scan or index scan for the example da=
ta<br>
&gt; distribution - which is quite skewed to show the benefit.<br>
&gt; <br>
<br>
I think it&#39;d be helpful to include at least some benchmark numbers, so<=
br>
that people can get an idea without having to build/run.<br>
<br>
&gt; I want to caveat that I am a web backend developer and not a Postgres<=
br>
&gt; expert by any means, so there&#39;s=C2=A0probably good reasons this=C2=
=A0isn&#39;t a thing<br>
&gt; (planner cost or benefit is too small/niche). I would appreciate thoug=
h<br>
&gt; any pointers to prior discussion or feedback on whether this is worth<=
br>
&gt; looking into further or not.<br>
&gt; <br>
<br>
I&#39;m not aware of any prior discussions or reasons why this would not<br=
>
work (or be competitive with other solutions). I think there&#39;s<br>
definitely a lot of open questions. It&#39;s not just about the execution,<=
br>
but also about generating the interesting paths (with indexes used as<br>
inputs for other indexes) and costing.<br>
<br>
<br>
regards<br>
<br>
-- <br>
Tomas Vondra<br>
<br>
<br>
<br>
</blockquote></div>

--0000000000005d6065064d74e0af--