From: Tom Lane <tgl@sss.pgh.pa.us>
To: pgsql-committers@lists.postgresql.org
Subject: pgsql: Invent "multibitmapsets", and use them to speed up antijoin dete
Date: Wed, 16 Nov 2022 18:59:03 +0000
Message-ID: <E1ovNck-000UYW-On@gemulon.postgresql.org> (raw)
Invent "multibitmapsets", and use them to speed up antijoin detection.
Implement a data structure that is a List of Bitmapsets, which is
essentially a 2-D boolean array except that the rows need not all
be the same width. Operations such as union and intersection are
meaningful for these, just as they are for Bitmapsets. Eventually
we might build many of the same operations that we have written for
Bitmapsets, but for the first use-case we just need a few.
That first use-case is for antijoin detection: reduce_outer_joins
needs to find the set of Vars that are certain to be non-null in a
successfully joined (not null-extended) left join row, and also
find the set of Vars subject to higher-level IS NULL constraints,
and intersect them. We had been doing this by making Lists of
the Var nodes and then using list_intersect, which works but is
pretty inefficient compared to a bitmapset-like intersection.
Potentially it's O(N^2) if there are a lot of Vars involved,
which fortunately there generally aren't; still it's not great.
Moreover, that method requires the Vars of interest to be exactly
equal() in the join condition and the upper IS NULL condition,
which is problematic for my WIP patch that labels Vars according
to which outer joins have possibly nulled them.
Discussion: https://postgr.es/m/892228.1668437838@sss.pgh.pa.us
Discussion: https://postgr.es/m/CAMbWs4-mvPPCJ1W6iK6dD5HiNwoJdi6mZp=-7mE8N9Sh+cd0tQ@mail.gmail.com
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/e9e26b5e7166e6f1873efd58f3d5a4ba22cc3d8f
Modified Files
--------------
src/backend/nodes/Makefile | 1 +
src/backend/nodes/README | 1 +
src/backend/nodes/meson.build | 1 +
src/backend/nodes/multibitmapset.c | 162 ++++++++++++++++++++++++++++++
src/backend/optimizer/prep/prepjointree.c | 20 ++--
src/backend/optimizer/util/clauses.c | 39 ++++---
src/include/nodes/multibitmapset.h | 39 +++++++
7 files changed, 238 insertions(+), 25 deletions(-)
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients from your mail client; the link fills in
the headers below: reply via email
Some clients, webmail especially, drop In-Reply-To and References from
a link, and the reply then starts a new thread: use the mbox below.
To: pgsql-committers@postgresql.org
Cc: tgl@sss.pgh.pa.us
Subject: Re: pgsql: Invent "multibitmapsets", and use them to speed up antijoin dete
In-Reply-To: <E1ovNck-000UYW-On@gemulon.postgresql.org>
References: <E1ovNck-000UYW-On@gemulon.postgresql.org>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox