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

1 files changed, 39 insertions, 0 deletions

diff --git a/src/include/nodes/multibitmapset.h b/src/include/nodes/multibitmapset.h
new file mode 100644
index 00000000000..8c6695aeda7
--- /dev/null
+++ b/src/include/nodes/multibitmapset.h
@@ -0,0 +1,39 @@
+/*-------------------------------------------------------------------------
+ *
+ * multibitmapset.h
+ *	  Lists of Bitmapsets
+ *
+ * A multibitmapset is useful in situations where members of a set can
+ * be identified by two small integers; for example, varno and varattno
+ * of a group of Vars within a query.  The implementation is a List of
+ * Bitmapsets, so that the empty set can be represented by NIL.  (But,
+ * as with Bitmapsets, that's not the only allowed representation.)
+ * The zero-based index of a List element is the first identifying value,
+ * and the (also zero-based) index of a bit within that Bitmapset is
+ * the second identifying value.  There is no expectation that the
+ * Bitmapsets should all be the same size.
+ *
+ * The available operations on multibitmapsets are intended to parallel
+ * those on bitmapsets, for example union and intersection.  So far only
+ * a small fraction of that has been built out; we'll add more as needed.
+ *
+ *
+ * Copyright (c) 2022, PostgreSQL Global Development Group
+ *
+ * src/include/nodes/multibitmapset.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef MULTIBITMAPSET_H
+#define MULTIBITMAPSET_H
+
+#include "nodes/bitmapset.h"
+#include "nodes/pg_list.h"
+
+extern List *mbms_add_member(List *a, int listidx, int bitidx);
+extern List *mbms_add_members(List *a, const List *b);
+extern List *mbms_int_members(List *a, const List *b);
+extern bool mbms_is_member(int listidx, int bitidx, const List *a);
+extern Bitmapset *mbms_overlap_sets(const List *a, const List *b);
+
+#endif							/* MULTIBITMAPSET_H */