MIME-Version: 1.0
References: <CAFQUnFjb9TgaiO9b1as9qkxc_9PLZpszawwraDw9685r9USP8Q@mail.gmail.com>
In-Reply-To: <CAFQUnFjb9TgaiO9b1as9qkxc_9PLZpszawwraDw9685r9USP8Q@mail.gmail.com>
From: Dmytro Astapov <dastapov@gmail.com>
Date: Wed, 26 Feb 2025 19:31:58 +0000
Message-ID: <CAFQUnFi1tZyGxcfbusOdw-71r6w-LnpKgOOGV-6mpH-fbTaPww@mail.gmail.com>
Subject: Re: Relaxing constraints on BitmapAnd eligibility?
To: pgsql-hackers@lists.postgresql.org
Content-Type: multipart/mixed; boundary="000000000000385278062f10a102"
Archived-At: <https://www.postgresql.org/message-id/CAFQUnFi1tZyGxcfbusOdw-71r6w-LnpKgOOGV-6mpH-fbTaPww%40mail.gmail.com>
Precedence: bulk

--000000000000385278062f10a102
Content-Type: multipart/alternative; boundary="000000000000385277062f10a100"

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

Hi!

I am (still) very unsure if the code change I mentioned will make sense,
but documentation chage could perhaps look like something along these lines=
?


Best regards, Dmytro


On Tue, Feb 25, 2025 at 9:14=E2=80=AFPM Dmytro Astapov <dastapov@gmail.com>=
 wrote:

> Hi!
>
> I've been investigating why postgres does not do BitmapAnd of two
> well-suited indexes, and reading indxpath.c
>
> In my case, there is a table (d date, col1 int, col2 int) -- types not
> really important -- and there are two indices on (d,col1) and (d, col2).
>
> For queries that do WHERE d>=3DX AND col1=3DY AND col2=3DZ postgres will =
never
> BitmapAnd those two indices because both indexes include (d) and we have =
a
> condition on (d). Here is a full example, which could also be seen here:
> https://www.db-fiddle.com/f/uPLx5bRtDEoZw3Dx4kkwKh/0:
>
> begin;
>
> CREATE TABLE test_table (
>     d date,
>     col1 int,
>     col2 int
> );
>
> INSERT INTO test_table (d, col1, col2)
> SELECT
>     d.date,
>     c1.val as col1,
>     c2.val as col2
> FROM
>     generate_series(
>         '2023-01-01'::date,
>         '2023-12-31'::date,
>         '1 day'::interval
>     ) as d(date),
>     generate_series(1, 1000) as c1(val),
>     generate_series(1, 1000) as c2(val)
> WHERE
>     random() < 0.001;
>
> create index on test_table(col1,d);
> create index on test_table(col2,d);
>
> -- This uses BitmapAnd
> explain select * from test_table where col1=3D123 and col2=3D321;
>
> -- This does not use BitmapAnd, even though it could!
> explain select * from test_table where col1=3D123 and col2=3D321 and d >=
=3D
> '2023-05-05';
>
> I checked that BitmapAnd is rejected by this
> <https://github.com/postgres/postgres/blob/master/src/backend/optimizer/p=
ath/indxpath.c#L1878>
> line in choose_bitmap_and:
>
>    if (bms_overlap(pathinfo->clauseids, clauseidsofar))
>       continue; /* consider it redundant */
>
> There is a comment on choose_bitmap_and that explains the rationale of
> this check, but reading it I can't help but feel that what the comment
> describes is this condition:
>
>    if (bms_is_subset(pathinfo->clauseids, clauseidsofar))
>       continue; /* consider it redundant */
>
> And indeed, in my (admittedly not super-extensive) testing changing
> bms_overlap to bms_is_subset leads to better faster execution plans.
>
> Is it possible that this condition could thus be relaxed?
>
> Even if I am wrong, and the condition absolutely should be bms_overlap, I
> feel that this restriction is very very hard to discover and perhaps
> https://www.postgresql.org/docs/current/indexes-bitmap-scans.html should
> mention that compound indexes that have columns in common will never be
> combined?
>
> Best regards, Dmytro
>

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

<div dir=3D"ltr"><div>Hi!</div><div><br></div><div>I am (still) very unsure=
 if the code change I mentioned will make sense, but documentation chage co=
uld perhaps look like something along these lines?</div><div><br></div><div=
><br></div><div><div dir=3D"ltr" class=3D"gmail_signature" data-smartmail=
=3D"gmail_signature"><div dir=3D"ltr"><div><br></div><div>Best regards, Dmy=
tro</div></div></div></div><br></div><br><div class=3D"gmail_quote gmail_qu=
ote_container"><div dir=3D"ltr" class=3D"gmail_attr">On Tue, Feb 25, 2025 a=
t 9:14=E2=80=AFPM Dmytro Astapov &lt;<a href=3D"mailto:dastapov@gmail.com">=
dastapov@gmail.com</a>&gt; wrote:<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"><div dir=3D"ltr"><div>Hi!</div><div><br></div><div>I&#39;=
ve been investigating why postgres does not do BitmapAnd of two well-suited=
 indexes, and reading indxpath.c</div><div><br></div><div>In my case, there=
 is a table (d date, col1 int, col2 int) -- types not really important -- a=
nd there are two indices on (d,col1) and (d, col2).</div><div><br></div><di=
v>For queries that do WHERE d&gt;=3DX AND col1=3DY AND col2=3DZ postgres wi=
ll never BitmapAnd those two indices because both indexes include (d) and w=
e have a condition on (d). Here is a full example, which could also be seen=
 here: <a href=3D"https://www.db-fiddle.com/f/uPLx5bRtDEoZw3Dx4kkwKh/0" tar=
get=3D"_blank">https://www.db-fiddle.com/f/uPLx5bRtDEoZw3Dx4kkwKh/0</a>:</d=
iv><div><br></div><div>begin;<br><br>CREATE TABLE test_table (<br>=C2=A0 =
=C2=A0 d date,<br>=C2=A0 =C2=A0 col1 int,<br>=C2=A0 =C2=A0 col2 int<br>);<b=
r><br>INSERT INTO test_table (d, col1, col2)<br>SELECT<br>=C2=A0 =C2=A0 d.d=
ate,<br>=C2=A0 =C2=A0 c1.val as col1,<br>=C2=A0 =C2=A0 c2.val as col2<br>FR=
OM<br>=C2=A0 =C2=A0 generate_series(<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 &#39;20=
23-01-01&#39;::date,<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 &#39;2023-12-31&#39;::d=
ate,<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 &#39;1 day&#39;::interval<br>=C2=A0 =C2=
=A0 ) as d(date),<br>=C2=A0 =C2=A0 generate_series(1, 1000) as c1(val),<br>=
=C2=A0 =C2=A0 generate_series(1, 1000) as c2(val)<br>WHERE<br>=C2=A0 =C2=A0=
 random() &lt; 0.001;<br><br>create index on test_table(col1,d);<br>create =
index on test_table(col2,d);<br></div><div><br></div><div>-- This uses Bitm=
apAnd</div><div>explain select * from test_table where col1=3D123 and col2=
=3D321;<br><br>-- This does not use BitmapAnd, even though it could!<br>exp=
lain select * from test_table where col1=3D123 and col2=3D321 and d &gt;=3D=
 &#39;2023-05-05&#39;;</div><div><br></div><div>I checked that BitmapAnd is=
 rejected by <a href=3D"https://github.com/postgres/postgres/blob/master/sr=
c/backend/optimizer/path/indxpath.c#L1878" target=3D"_blank">this</a> line =
in choose_bitmap_and:</div><div><br></div><div>=C2=A0 =C2=A0if (bms_overlap=
(pathinfo-&gt;clauseids, clauseidsofar))<br>=C2=A0 =C2=A0 =C2=A0 continue;	=
	/* consider it redundant */</div><div><br></div><div>There is a comment on=
 choose_bitmap_and that explains the rationale of this check, but reading i=
t I can&#39;t help but feel that what the comment describes=C2=A0is this co=
ndition:</div><div><br></div><div><div>=C2=A0 =C2=A0if (bms_is_subset(pathi=
nfo-&gt;clauseids, clauseidsofar))<br>=C2=A0 =C2=A0 =C2=A0 continue; /* con=
sider it redundant */</div><div><br></div></div><div><div dir=3D"ltr" class=
=3D"gmail_signature"><div dir=3D"ltr"><div>And indeed, in my (admittedly no=
t super-extensive) testing changing bms_overlap to bms_is_subset leads to b=
etter faster execution plans.=C2=A0</div><div><br></div><div>Is it possible=
 that this condition could thus be relaxed?</div><div><br></div><div>Even i=
f I am wrong, and the condition absolutely should be bms_overlap, I feel th=
at this restriction is very very hard to discover and perhaps=C2=A0<a href=
=3D"https://www.postgresql.org/docs/current/indexes-bitmap-scans.html" targ=
et=3D"_blank">https://www.postgresql.org/docs/current/indexes-bitmap-scans.=
html</a> should mention that compound indexes that have columns in common w=
ill never be combined?</div><div><br></div><div>Best regards, Dmytro</div><=
/div></div></div></div>
</blockquote></div>

--000000000000385277062f10a100--
--000000000000385278062f10a102
Content-Type: text/x-patch; charset="US-ASCII"; name="v1-0001-Bitmap-restrictions.patch"
Content-Disposition: attachment; 
	filename="v1-0001-Bitmap-restrictions.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_m7mban7k0>
X-Attachment-Id: f_m7mban7k0

ZGlmZiAtLWdpdCBhL2RvYy9zcmMvc2dtbC9pbmRpY2VzLnNnbWwgYi9kb2Mvc3JjL3NnbWwvaW5k
aWNlcy5zZ21sCmluZGV4IDZkNzMxZTA3MDEuLmRlNjNkMjNkN2IgMTAwNjQ0Ci0tLSBhL2RvYy9z
cmMvc2dtbC9pbmRpY2VzLnNnbWwKKysrIGIvZG9jL3NyYy9zZ21sL2luZGljZXMuc2dtbApAQCAt
NjgyLDYgKzY4MiwxNSBAQCBDUkVBVEUgSU5ERVggdGVzdDNfZGVzY19pbmRleCBPTiB0ZXN0MyAo
aWQgREVTQyBOVUxMUyBMQVNUKTsKICAgIGJlc3QgbWF0Y2ggdGhlIGNvbW1vbiB0eXBlcy4KICAg
PC9wYXJhPgogCisgIDxwYXJhPgorICAgIE5vdGUgdGhhdCBpZiB0aGVyZSBhcmUgbXVsdGlwbGUg
aW5kZXhlcyBmb3IgYSBnaXZlbiBjb2x1bW4sIHRoZXkgd291bGQKKyAgICBuZXZlciBiZSBjb21i
aW5lZC4gRm9yIGV4YW1wbGUsIGlmIHlvdSBoYXZlIG11bHRpY29sdW1uIGluZGV4ZXMKKyAgICBv
biA8bGl0ZXJhbD4oeCwgeik8L2xpdGVyYWw+IGFuZCA8bGl0ZXJhbD4oeSwgeik8L2xpdGVyYWw+
LCB0aGV5IHdvdWxkCisgICAgbmV2ZXIgYmUgY29tYmluZWQgZm9yIHF1ZXJpZXMgaW52b2x2aW5n
IDxsaXRlcmFsPno8L2xpdGVyYWw+LiBIb3dldmVyLCBpZgorICAgIHlvdXIgcXVlcnkgb25seSBp
bnZvbHZlcyA8bGl0ZXJhbD54PC9saXRlcmFsPiBhbmQgPGxpdGVyYWw+eTwvbGl0ZXJhbD4sCisg
ICAgdGhlbiBwbGFubmVyIGNhbiBwb3RlbnRpYWxseSBjaG9vc2UgdG8gY29tYmluZSB0aG9zZSBp
bmRleGVzLgorICA8L3BhcmE+CisKICA8L3NlY3QxPgogCiAK
--000000000000385278062f10a102--