MIME-Version: 1.0
From: Laurence Newman <lenewman05@googlemail.com>
Date: Fri, 13 Mar 2026 12:08:59 +0000
Message-ID: <CAHueFRVqNuKQ0+LQPZVwMgJ+LpuTbZ21+ztwFbgPhBf9maFGYA@mail.gmail.com>
Subject: Index scan with bitmap filter - has this been explored
To: pgsql-general@postgresql.org
Content-Type: multipart/alternative; boundary="00000000000099e170064ce6bc57"
Archived-At: <https://www.postgresql.org/message-id/CAHueFRVqNuKQ0%2BLQPZVwMgJ%2BLpuTbZ21%2BztwFbgPhBf9maFGYA%40mail.gmail.com>
Precedence: bulk

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

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 =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 agai=
nst 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

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

<div dir=3D"ltr">Hello,<br><br>I&#39;ve been thinking about a scan strategy=
 that is sort of in between a bitmap scan and an=C2=A0 index=C2=A0scan, and=
 I wanted to check whether this has been explored before much or if there&#=
39;s a<br>reason it wouldn&#39;t work well in practice.<br><br>Example scen=
ario where it=C2=A0could 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 in=
dexes:<br><br>=C2=A0 =C2=A0 1. Bitmap scan on the filter index =E2=86=92 he=
ap fetch all matches =E2=86=92 sort =E2=86=92 limit. Can be expensive<br>=
=C2=A0when there are many matches but you only want a few results returned.=
<br>=C2=A0 =C2=A0 2. Index scan on the B-tree =E2=86=92 recheck the filter =
condition against the heap for each<br>=C2=A0row. Can be expensive when the=
 match rate is low and many non-matching rows are found before=C2=A0finding=
 N hits.<br><br>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<br>filter con=
dition, check each TID against the bitmap. Matching TIDs get returned<br>di=
rectly in order.<br><br>I built a small proof of concept as a pgrx extensio=
n against PG 18 to try and test this:<br><a href=3D"https://github.com/laur=
i3new/ordered-bitmap-scan">https://github.com/lauri3new/ordered-bitmap-scan=
</a>. The benchmarks there show it using fewer buffer hits than either a bi=
tmap scan or index scan for the example data distribution - which is quite =
skewed to show the benefit.<br><br>I want to caveat that I am a web backend=
 developer and not a Postgres expert by any means, so there&#39;s=C2=A0prob=
ably good reasons this=C2=A0isn&#39;t a thing (planner cost or benefit is t=
oo small/niche). I would appreciate though any pointers to prior discussion=
 or feedback on whether this is worth looking into further or not.<br><br>T=
hanks</div>

--00000000000099e170064ce6bc57--