Thread: List of Bitmapset (was Re: ExecRTCheckPerms() and many prunable partitions)
[ I'm intentionally forking this off as a new thread, so as to
not confuse the cfbot about what's the live patchset on the
ExecRTCheckPerms thread. ]
Amit Langote <amitlangote09@gmail.com> writes:
> On Sat, Nov 12, 2022 at 1:46 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> The main thing I was wondering about in connection with that
>> was whether to assume that there could be other future applications
>> of the logic to perform multi-bitmapset union, intersection,
>> etc. If so, then I'd be inclined to choose different naming and
>> put those functions in or near to bitmapset.c. It doesn't look
>> like Amit's code needs anything like that, but maybe somebody
>> has an idea about other applications?
> Yes, simple storage of multiple Bitmapsets in a List somewhere in a
> parse/plan tree sounded like that would have wider enough use to add
> proper node support for. Assuming you mean trying to generalize
> VarAttnoSet in your patch 0004 posted at [2], I wonder if you want to
> somehow make its indexability by varno / RT index a part of the
> interface of the generic code you're thinking for it?
For discussion's sake, here's my current version of that 0004 patch,
rewritten to use list-of-bitmapset as the data structure. (This
could actually be pulled out of the outer-join-vars patchset and
committed independently, just as a minor performance improvement.
It doesn't quite apply cleanly to HEAD, but pretty close.)
As it stands, the new functions are still in util/clauses.c, but
if we think they could be of general use it'd make sense to move them
either to nodes/bitmapset.c or to some new file under backend/nodes.
Some other thoughts:
* The multi_bms prefix is a bit wordy, so I was thinking of shortening
the function names to mbms_xxx. Maybe that's too brief.
* This is a pretty short list of functions so far. I'm not eager
to build out a bunch of dead code though. Is it OK to leave it
with just this much functionality until someone needs more?
* I'm a little hesitant about whether the API actually should be
List-of-Bitmapset, or some dedicated struct as I had in the previous
version of 0004. This version is way less invasive in prepjointree.c
than that was, but the reason is there's ambiguity about what the
forced_null_vars Lists actually contain, which feels error-prone.
Comments?
regards, tom lane
commit 998723891b3ecea420ed77ff9de475f7b6c54cda
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date: Sun Nov 13 14:44:28 2022 -0500
Rewrite reduce_outer_joins' matching of Vars.
Adding varnullingrels breaks the logic in reduce_outer_joins_pass2
that detects antijoins by matching upper-level "Var IS NULL" tests to
strict join quals. The problem of course is that the upper Var is
no longer equal() to the one in the join qual, since the former will
now be marked as being nulled by the outer join.
Now, this logic was always pretty brute-force: doing list_intersect
on a list full of Vars isn't especially cheap. So let's fix it by
creating a better-suited data structure, namely a list of per-RTE
bitmaps of relevant Vars' attnos.
(I wonder if there aren't other applications for a list-of-bitmaps data
structure, which might lead to wanting this to be a general-purpose
data structure on the same level as Bitmapset. But for now I just
settled for writing enough primitives for the immediate problem.)
Discussion: https://postgr.es/m/CAMbWs4-mvPPCJ1W6iK6dD5HiNwoJdi6mZp=-7mE8N9Sh+cd0tQ@mail.gmail.com
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 4821b7a71f..1e22ddd100 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -2753,7 +2753,7 @@ reduce_outer_joins_pass1(Node *jtnode)
* state2: where to accumulate info about successfully-reduced joins
* root: toplevel planner state
* nonnullable_rels: set of base relids forced non-null by upper quals
- * forced_null_vars: list of Vars forced null by upper quals
+ * forced_null_vars: multi-bitmapset of Var attnos forced null by upper quals
*
* Returns info in state2 about outer joins that were successfully simplified.
* Joins that were fully reduced to inner joins are all added to
@@ -2790,8 +2790,8 @@ reduce_outer_joins_pass2(Node *jtnode,
pass_nonnullable_rels = bms_add_members(pass_nonnullable_rels,
nonnullable_rels);
pass_forced_null_vars = find_forced_null_vars(f->quals);
- pass_forced_null_vars = list_concat(pass_forced_null_vars,
- forced_null_vars);
+ pass_forced_null_vars = multi_bms_add_members(pass_forced_null_vars,
+ forced_null_vars);
/* And recurse --- but only into interesting subtrees */
Assert(list_length(f->fromlist) == list_length(state1->sub_states));
forboth(l, f->fromlist, s, state1->sub_states)
@@ -2899,7 +2899,7 @@ reduce_outer_joins_pass2(Node *jtnode,
if (jointype == JOIN_LEFT)
{
List *nonnullable_vars;
- List *overlap;
+ Relids overlap;
/* Find Vars in j->quals that must be non-null in joined rows */
nonnullable_vars = find_nonnullable_vars(j->quals);
@@ -2909,11 +2909,9 @@ reduce_outer_joins_pass2(Node *jtnode,
* forced_null_vars overlap: we need to know if the overlap
* includes any RHS variables.
*/
- overlap = list_intersection(nonnullable_vars,
- forced_null_vars);
- if (overlap != NIL &&
- bms_overlap(pull_varnos(root, (Node *) overlap),
- right_state->relids))
+ overlap = multi_bms_intersect_relids(nonnullable_vars,
+ forced_null_vars);
+ if (bms_overlap(overlap, right_state->relids))
jointype = JOIN_ANTI;
}
@@ -2972,8 +2970,8 @@ reduce_outer_joins_pass2(Node *jtnode,
/* OK to merge upper and local constraints */
local_nonnullable_rels = bms_add_members(local_nonnullable_rels,
nonnullable_rels);
- local_forced_null_vars = list_concat(local_forced_null_vars,
- forced_null_vars);
+ local_forced_null_vars = multi_bms_add_members(local_forced_null_vars,
+ forced_null_vars);
}
}
else
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 4cca2888b4..8b999af07e 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -1308,6 +1308,113 @@ contain_leaked_vars_walker(Node *node, void *context)
context);
}
+
+/*
+ * multi_bms_add_member
+ * Add a new member to a list of bitmapsets.
+ *
+ * This is like bms_add_member, but for lists of bitmapsets.
+ * The new member is identified by the zero-based index of the List
+ * element it should go into, and the bit number to be set therein.
+ */
+List *
+multi_bms_add_member(List *mbms, int index1, int index2)
+{
+ Bitmapset *bms;
+ ListCell *lc;
+
+ if (index1 < 0 || index2 < 0)
+ elog(ERROR, "negative bitmapset member not allowed");
+ /* Add empty elements as needed */
+ while (list_length(mbms) <= index1)
+ mbms = lappend(mbms, NULL);
+ /* Update the target element */
+ lc = list_nth_cell(mbms, index1);
+ bms = (Bitmapset *) lfirst(lc);
+ bms = bms_add_member(bms, index2);
+ lfirst(lc) = bms;
+ return mbms;
+}
+
+/*
+ * multi_bms_add_members
+ * Add all members of set b to set a.
+ *
+ * This is like bms_add_members, but for lists of bitmapsets.
+ */
+List *
+multi_bms_add_members(List *a, const List *b)
+{
+ ListCell *lca,
+ *lcb;
+
+ /* Add empty elements to a, as needed */
+ while (list_length(a) < list_length(b))
+ a = lappend(a, NULL);
+ /* forboth will stop at the end of the shorter list, which is fine */
+ forboth(lca, a, lcb, b)
+ {
+ Bitmapset *bmsa = (Bitmapset *) lfirst(lca);
+ const Bitmapset *bmsb = (const Bitmapset *) lfirst(lcb);
+
+ bmsa = bms_add_members(bmsa, bmsb);
+ lfirst(lca) = bmsa;
+ }
+ return a;
+}
+
+/*
+ * multi_bms_int_members
+ * Reduce set a to its intersection with set b.
+ *
+ * This is like bms_int_members, but for lists of bitmapsets.
+ */
+static List *
+multi_bms_int_members(List *a, const List *b)
+{
+ ListCell *lca,
+ *lcb;
+
+ /* Remove any elements of a that are no longer of use */
+ a = list_truncate(a, list_length(b));
+ /* forboth will stop at the end of the shorter list, which is fine */
+ forboth(lca, a, lcb, b)
+ {
+ Bitmapset *bmsa = (Bitmapset *) lfirst(lca);
+ const Bitmapset *bmsb = (const Bitmapset *) lfirst(lcb);
+
+ bmsa = bms_int_members(bmsa, bmsb);
+ lfirst(lca) = bmsa;
+ }
+ return a;
+}
+
+/*
+ * multi_bms_intersect_relids
+ * Identify the bitmapsets having common members in a and b.
+ *
+ * The result is a Bitmapset of the list indexes of elements that overlap.
+ */
+Relids
+multi_bms_intersect_relids(const List *a, const List *b)
+{
+ Relids result = NULL;
+ ListCell *lca,
+ *lcb;
+
+ /* forboth will stop at the end of the shorter list, which is fine */
+ forboth(lca, a, lcb, b)
+ {
+ const Bitmapset *bmsa = (const Bitmapset *) lfirst(lca);
+ const Bitmapset *bmsb = (const Bitmapset *) lfirst(lcb);
+
+ if (bms_overlap(bmsa, bmsb))
+ result = bms_add_member(result, foreach_current_index(lca));
+ }
+ return result;
+}
+
+
/*
* find_nonnullable_rels
* Determine which base rels are forced nonnullable by given clause.
@@ -1566,7 +1673,7 @@ find_nonnullable_rels_walker(Node *node, bool top_level)
* find_nonnullable_vars
* Determine which Vars are forced nonnullable by given clause.
*
- * Returns a list of all level-zero Vars that are referenced in the clause in
+ * Returns the set of all level-zero Vars that are referenced in the clause in
* such a way that the clause cannot possibly return TRUE if any of these Vars
* is NULL. (It is OK to err on the side of conservatism; hence the analysis
* here is simplistic.)
@@ -1578,8 +1685,9 @@ find_nonnullable_rels_walker(Node *node, bool top_level)
* the expression to have been AND/OR flattened and converted to implicit-AND
* format.
*
- * The result is a palloc'd List, but we have not copied the member Var nodes.
- * Also, we don't bother trying to eliminate duplicate entries.
+ * Attnos of the identified Vars are returned in a "multi_bms" List of
+ * Bitmapsets. List indexes correspond to relids (varnos), while the per-rel
+ * Bitmapsets hold varattnos offset by FirstLowInvalidHeapAttributeNumber.
*
* top_level is true while scanning top-level AND/OR structure; here, showing
* the result is either FALSE or NULL is good enough. top_level is false when
@@ -1608,7 +1716,9 @@ find_nonnullable_vars_walker(Node *node, bool top_level)
Var *var = (Var *) node;
if (var->varlevelsup == 0)
- result = list_make1(var);
+ result = multi_bms_add_member(result,
+ var->varno,
+ var->varattno - FirstLowInvalidHeapAttributeNumber);
}
else if (IsA(node, List))
{
@@ -1623,9 +1733,9 @@ find_nonnullable_vars_walker(Node *node, bool top_level)
*/
foreach(l, (List *) node)
{
- result = list_concat(result,
- find_nonnullable_vars_walker(lfirst(l),
- top_level));
+ result = multi_bms_add_members(result,
+ find_nonnullable_vars_walker(lfirst(l),
+ top_level));
}
}
else if (IsA(node, FuncExpr))
@@ -1657,7 +1767,12 @@ find_nonnullable_vars_walker(Node *node, bool top_level)
switch (expr->boolop)
{
case AND_EXPR:
- /* At top level we can just recurse (to the List case) */
+
+ /*
+ * At top level we can just recurse (to the List case), since
+ * the result should be the union of what we can prove in each
+ * arm.
+ */
if (top_level)
{
result = find_nonnullable_vars_walker((Node *) expr->args,
@@ -1689,7 +1804,7 @@ find_nonnullable_vars_walker(Node *node, bool top_level)
if (result == NIL) /* first subresult? */
result = subresult;
else
- result = list_intersection(result, subresult);
+ result = multi_bms_int_members(result, subresult);
/*
* If the intersection is empty, we can stop looking. This
@@ -1788,8 +1903,8 @@ find_nonnullable_vars_walker(Node *node, bool top_level)
* side of conservatism; hence the analysis here is simplistic. In fact,
* we only detect simple "var IS NULL" tests at the top level.)
*
- * The result is a palloc'd List, but we have not copied the member Var nodes.
- * Also, we don't bother trying to eliminate duplicate entries.
+ * As with find_nonnullable_vars, we return the varattnos of the identified
+ * Vars in a List of Bitmapsets.
*/
List *
find_forced_null_vars(Node *node)
@@ -1804,7 +1919,9 @@ find_forced_null_vars(Node *node)
var = find_forced_null_var(node);
if (var)
{
- result = list_make1(var);
+ result = multi_bms_add_member(result,
+ var->varno,
+ var->varattno - FirstLowInvalidHeapAttributeNumber);
}
/* Otherwise, handle AND-conditions */
else if (IsA(node, List))
@@ -1815,8 +1932,8 @@ find_forced_null_vars(Node *node)
*/
foreach(l, (List *) node)
{
- result = list_concat(result,
- find_forced_null_vars(lfirst(l)));
+ result = multi_bms_add_members(result,
+ find_forced_null_vars((Node *) lfirst(l)));
}
}
else if (IsA(node, BoolExpr))
diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h
index ff242d1b6d..b80ae3fa45 100644
--- a/src/include/optimizer/clauses.h
+++ b/src/include/optimizer/clauses.h
@@ -38,6 +38,10 @@ extern bool contain_nonstrict_functions(Node *clause);
extern bool contain_exec_param(Node *clause, List *param_ids);
extern bool contain_leaked_vars(Node *clause);
+extern List *multi_bms_add_member(List *mbms, int index1, int index2);
+extern List *multi_bms_add_members(List *a, const List *b);
+extern Relids multi_bms_intersect_relids(const List *a, const List *b);
+
extern Relids find_nonnullable_rels(Node *clause);
extern List *find_nonnullable_vars(Node *clause);
extern List *find_forced_null_vars(Node *node);
Re: List of Bitmapset (was Re: ExecRTCheckPerms() and many prunable partitions)
From
Amit Langote
Date:
On Mon, Nov 14, 2022 at 11:57 PM Tom Lane <tgl@sss.pgh.pa.us> wrote: > Amit Langote <amitlangote09@gmail.com> writes: > > On Sat, Nov 12, 2022 at 1:46 AM Tom Lane <tgl@sss.pgh.pa.us> wrote: > >> The main thing I was wondering about in connection with that > >> was whether to assume that there could be other future applications > >> of the logic to perform multi-bitmapset union, intersection, > >> etc. If so, then I'd be inclined to choose different naming and > >> put those functions in or near to bitmapset.c. It doesn't look > >> like Amit's code needs anything like that, but maybe somebody > >> has an idea about other applications? > > > Yes, simple storage of multiple Bitmapsets in a List somewhere in a > > parse/plan tree sounded like that would have wider enough use to add > > proper node support for. Assuming you mean trying to generalize > > VarAttnoSet in your patch 0004 posted at [2], I wonder if you want to > > somehow make its indexability by varno / RT index a part of the > > interface of the generic code you're thinking for it? > > For discussion's sake, here's my current version of that 0004 patch, > rewritten to use list-of-bitmapset as the data structure. (This > could actually be pulled out of the outer-join-vars patchset and > committed independently, just as a minor performance improvement. > It doesn't quite apply cleanly to HEAD, but pretty close.) > > As it stands, the new functions are still in util/clauses.c, but > if we think they could be of general use it'd make sense to move them > either to nodes/bitmapset.c or to some new file under backend/nodes. These multi_bms_* functions sound generic enough to me, so +1 to put them in nodes/bitmapset.c. Or even a new file if the API should involve a dedicated struct enveloping the List as you write below. > Some other thoughts: > > * The multi_bms prefix is a bit wordy, so I was thinking of shortening > the function names to mbms_xxx. Maybe that's too brief. FWIW, multi_bms_* naming sounds fine to me. > * This is a pretty short list of functions so far. I'm not eager > to build out a bunch of dead code though. Is it OK to leave it > with just this much functionality until someone needs more? +1 > * I'm a little hesitant about whether the API actually should be > List-of-Bitmapset, or some dedicated struct as I had in the previous > version of 0004. This version is way less invasive in prepjointree.c > than that was, but the reason is there's ambiguity about what the > forced_null_vars Lists actually contain, which feels error-prone. Are you thinking of something like a MultiBitmapset that wraps the multi_bms List? That sounds fine to me. Another option is to make the generic API be List-of-Bitmapset but keep VarAttnoSet in prepjointree.c and put the List in it. IMHO, VarAttnoSet is definitely more self-documenting for that patch's purposes. + * The new member is identified by the zero-based index of the List + * element it should go into, and the bit number to be set therein. + */ +List * +multi_bms_add_member(List *mbms, int index1, int index2) The comment sounds a bit ambiguous, especially the ", and the bit number to be set therein." part. If you meant to describe the arguments, how about mentioning their names too, as in: The new member is identified by 'index1', the zero-based index of the List element it should go into, and 'index2' specifies the bit number to be set therein. + /* Add empty elements to a, as needed */ + while (list_length(a) < list_length(b)) + a = lappend(a, NULL); + /* forboth will stop at the end of the shorter list, which is fine */ Isn't this comment unnecessary given that the while loop makes both lists be the same length? -- Thanks, Amit Langote EDB: http://www.enterprisedb.com
Re: List of Bitmapset (was Re: ExecRTCheckPerms() and many prunable partitions)
From
Alvaro Herrera
Date:
On 2022-Nov-14, Tom Lane wrote: > For discussion's sake, here's my current version of that 0004 patch, > rewritten to use list-of-bitmapset as the data structure. I feel that there should be more commentary that explains what a multi-bms is. Not sure where, maybe just put it near the function that first appears in the file. > * The multi_bms prefix is a bit wordy, so I was thinking of shortening > the function names to mbms_xxx. Maybe that's too brief. I don't think the "ulti_" bytes add a lot, and short names are better. Either you know what a mbms is, or you don't. If the latter, then you jump to one of these functions in order to find out what the data structure is; after that, you can read the code and it should be clear enough. > * This is a pretty short list of functions so far. I'm not eager > to build out a bunch of dead code though. Is it OK to leave it > with just this much functionality until someone needs more? I agree with not adding dead code. > * I'm a little hesitant about whether the API actually should be > List-of-Bitmapset, or some dedicated struct as I had in the previous > version of 0004. This version is way less invasive in prepjointree.c > than that was, but the reason is there's ambiguity about what the > forced_null_vars Lists actually contain, which feels error-prone. Hmm ... if somebody makes a mistake, does the functionality break in obvious ways, or is it very hard to pinpoint what happened? > +/* > + * multi_bms_add_member > + * Add a new member to a list of bitmapsets. > + * > + * This is like bms_add_member, but for lists of bitmapsets. > + * The new member is identified by the zero-based index of the List > + * element it should go into, and the bit number to be set therein. > + */ > +List * > +multi_bms_add_member(List *mbms, int index1, int index2) Maybe s/index1/listidx/ or bitmapidx and s/index2/bitnr/ ? -- Álvaro Herrera PostgreSQL Developer — https://www.EnterpriseDB.com/ "La rebeldía es la virtud original del hombre" (Arthur Schopenhauer)
Alvaro Herrera <alvherre@alvh.no-ip.org> writes:
> On 2022-Nov-14, Tom Lane wrote:
>> For discussion's sake, here's my current version of that 0004 patch,
>> rewritten to use list-of-bitmapset as the data structure.
> I feel that there should be more commentary that explains what a
> multi-bms is. Not sure where, maybe just put it near the function that
> first appears in the file.
Right. I split the new functions out to new files multibitmapset.h/.c,
so that the file headers can carry the overall explanation. (I duplicated
the text between .h and .c, which is also true of bitmapset.h/.c, but
maybe that's overkill.)
>> * The multi_bms prefix is a bit wordy, so I was thinking of shortening
>> the function names to mbms_xxx. Maybe that's too brief.
> I don't think the "ulti_" bytes add a lot, and short names are better.
Yeah, after sleeping on it I like mbms.
>> * This is a pretty short list of functions so far. I'm not eager
>> to build out a bunch of dead code though. Is it OK to leave it
>> with just this much functionality until someone needs more?
> I agree with not adding dead code.
I concluded that the only thing that makes this an odd set of functions
to start out with is the lack of mbms_is_member; it seems asymmetric
to have mbms_add_member but not mbms_is_member. So I added that.
I'm content to let the rest grow out as needed.
>> * I'm a little hesitant about whether the API actually should be
>> List-of-Bitmapset, or some dedicated struct as I had in the previous
>> version of 0004. This version is way less invasive in prepjointree.c
>> than that was, but the reason is there's ambiguity about what the
>> forced_null_vars Lists actually contain, which feels error-prone.
> Hmm ... if somebody makes a mistake, does the functionality break in
> obvious ways, or is it very hard to pinpoint what happened?
Now that Bitmapset is a full-fledged Node type, we can make use of
castNode checks to verify that the input Lists contain what we expect.
That seems probably sufficient to catch coding errors.
>> +multi_bms_add_member(List *mbms, int index1, int index2)
> Maybe s/index1/listidx/ or bitmapidx and s/index2/bitnr/ ?
Right. I used listidx and bitidx.
regards, tom lane
diff --git a/src/backend/nodes/Makefile b/src/backend/nodes/Makefile
index d7b4261b47..4368c30fdb 100644
--- a/src/backend/nodes/Makefile
+++ b/src/backend/nodes/Makefile
@@ -21,6 +21,7 @@ OBJS = \
extensible.o \
list.o \
makefuncs.o \
+ multibitmapset.o \
nodeFuncs.o \
nodes.o \
outfuncs.o \
diff --git a/src/backend/nodes/README b/src/backend/nodes/README
index 64937fe254..489a67eb89 100644
--- a/src/backend/nodes/README
+++ b/src/backend/nodes/README
@@ -58,6 +58,7 @@ FILES IN THIS DIRECTORY (src/backend/nodes/)
Specialized manipulation functions:
bitmapset.c - Bitmapset support
list.c - generic list support
+ multibitmapset.c - List-of-Bitmapset support
params.c - Param support
tidbitmap.c - TIDBitmap support
value.c - support for value nodes
diff --git a/src/backend/nodes/meson.build b/src/backend/nodes/meson.build
index 8e0d4039f2..c4f3897ef2 100644
--- a/src/backend/nodes/meson.build
+++ b/src/backend/nodes/meson.build
@@ -3,6 +3,7 @@ backend_sources += files(
'extensible.c',
'list.c',
'makefuncs.c',
+ 'multibitmapset.c',
'nodeFuncs.c',
'nodes.c',
'params.c',
diff --git a/src/backend/nodes/multibitmapset.c b/src/backend/nodes/multibitmapset.c
new file mode 100644
index 0000000000..9a2ac8c81b
--- /dev/null
+++ b/src/backend/nodes/multibitmapset.c
@@ -0,0 +1,158 @@
+/*-------------------------------------------------------------------------
+ *
+ * multibitmapset.c
+ * 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
+ *
+ * IDENTIFICATION
+ * src/backend/nodes/multibitmapset.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "nodes/multibitmapset.h"
+
+
+/*
+ * mbms_add_member
+ * Add a new member to a multibitmapset.
+ *
+ * The new member is identified by "listidx", the zero-based index of the
+ * List element it should go into, and "bitidx", which specifies the bit
+ * number to be set therein.
+ *
+ * This is like bms_add_member, but for multibitmapsets.
+ */
+List *
+mbms_add_member(List *a, int listidx, int bitidx)
+{
+ Bitmapset *bms;
+ ListCell *lc;
+
+ if (listidx < 0 || bitidx < 0)
+ elog(ERROR, "negative multibitmapset member index not allowed");
+ /* Add empty elements as needed */
+ while (list_length(a) <= listidx)
+ a = lappend(a, NULL);
+ /* Update the target element */
+ lc = list_nth_cell(a, listidx);
+ bms = lfirst_node(Bitmapset, lc);
+ bms = bms_add_member(bms, bitidx);
+ lfirst(lc) = bms;
+ return a;
+}
+
+/*
+ * mbms_add_members
+ * Add all members of set b to set a.
+ *
+ * This is like bms_add_members, but for multibitmapsets.
+ */
+List *
+mbms_add_members(List *a, const List *b)
+{
+ ListCell *lca,
+ *lcb;
+
+ /* Add empty elements to a, as needed */
+ while (list_length(a) < list_length(b))
+ a = lappend(a, NULL);
+ /* forboth will stop at the end of the shorter list, which is fine */
+ forboth(lca, a, lcb, b)
+ {
+ Bitmapset *bmsa = lfirst_node(Bitmapset, lca);
+ const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);
+
+ bmsa = bms_add_members(bmsa, bmsb);
+ lfirst(lca) = bmsa;
+ }
+ return a;
+}
+
+/*
+ * mbms_int_members
+ * Reduce set a to its intersection with set b.
+ *
+ * This is like bms_int_members, but for multibitmapsets.
+ */
+List *
+mbms_int_members(List *a, const List *b)
+{
+ ListCell *lca,
+ *lcb;
+
+ /* Remove any elements of a that are no longer of use */
+ a = list_truncate(a, list_length(b));
+ /* forboth will stop at the end of the shorter list, which is fine */
+ forboth(lca, a, lcb, b)
+ {
+ Bitmapset *bmsa = lfirst_node(Bitmapset, lca);
+ const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);
+
+ bmsa = bms_int_members(bmsa, bmsb);
+ lfirst(lca) = bmsa;
+ }
+ return a;
+}
+
+/*
+ * mbms_is_member
+ * Is listidx/bitidx a member of A?
+ *
+ * This is like bms_is_member, but for multibitmapsets.
+ */
+bool
+mbms_is_member(int listidx, int bitidx, const List *a)
+{
+ const Bitmapset *bms;
+
+ /* XXX better to just return false for negative indexes? */
+ if (listidx < 0 || bitidx < 0)
+ elog(ERROR, "negative multibitmapset member index not allowed");
+ if (listidx >= list_length(a))
+ return false;
+ bms = list_nth_node(Bitmapset, a, listidx);
+ return bms_is_member(bitidx, bms);
+}
+
+/*
+ * mbms_overlap_sets
+ * Identify the bitmapsets having common members in a and b.
+ *
+ * The result is a bitmapset of the list indexes of bitmapsets that overlap.
+ */
+Bitmapset *
+mbms_overlap_sets(const List *a, const List *b)
+{
+ Bitmapset *result = NULL;
+ ListCell *lca,
+ *lcb;
+
+ /* forboth will stop at the end of the shorter list, which is fine */
+ forboth(lca, a, lcb, b)
+ {
+ const Bitmapset *bmsa = lfirst_node(Bitmapset, lca);
+ const Bitmapset *bmsb = lfirst_node(Bitmapset, lcb);
+
+ if (bms_overlap(bmsa, bmsb))
+ result = bms_add_member(result, foreach_current_index(lca));
+ }
+ return result;
+}
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index b4b9099eb6..f4cdb879c2 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -28,6 +28,7 @@
#include "catalog/pg_type.h"
#include "funcapi.h"
#include "nodes/makefuncs.h"
+#include "nodes/multibitmapset.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/optimizer.h"
@@ -2769,7 +2770,7 @@ reduce_outer_joins_pass1(Node *jtnode)
* state: state data collected by phase 1 for this node
* root: toplevel planner state
* nonnullable_rels: set of base relids forced non-null by upper quals
- * forced_null_vars: list of Vars forced null by upper quals
+ * forced_null_vars: multibitmapset of Vars forced null by upper quals
*/
static void
reduce_outer_joins_pass2(Node *jtnode,
@@ -2799,8 +2800,8 @@ reduce_outer_joins_pass2(Node *jtnode,
pass_nonnullable_rels = bms_add_members(pass_nonnullable_rels,
nonnullable_rels);
pass_forced_null_vars = find_forced_null_vars(f->quals);
- pass_forced_null_vars = list_concat(pass_forced_null_vars,
- forced_null_vars);
+ pass_forced_null_vars = mbms_add_members(pass_forced_null_vars,
+ forced_null_vars);
/* And recurse --- but only into interesting subtrees */
Assert(list_length(f->fromlist) == list_length(state->sub_states));
forboth(l, f->fromlist, s, state->sub_states)
@@ -2897,7 +2898,7 @@ reduce_outer_joins_pass2(Node *jtnode,
if (jointype == JOIN_LEFT)
{
List *nonnullable_vars;
- List *overlap;
+ Bitmapset *overlap;
/* Find Vars in j->quals that must be non-null in joined rows */
nonnullable_vars = find_nonnullable_vars(j->quals);
@@ -2907,11 +2908,8 @@ reduce_outer_joins_pass2(Node *jtnode,
* forced_null_vars overlap: we need to know if the overlap
* includes any RHS variables.
*/
- overlap = list_intersection(nonnullable_vars,
- forced_null_vars);
- if (overlap != NIL &&
- bms_overlap(pull_varnos(root, (Node *) overlap),
- right_state->relids))
+ overlap = mbms_overlap_sets(nonnullable_vars, forced_null_vars);
+ if (bms_overlap(overlap, right_state->relids))
jointype = JOIN_ANTI;
}
@@ -2964,8 +2962,8 @@ reduce_outer_joins_pass2(Node *jtnode,
/* OK to merge upper and local constraints */
local_nonnullable_rels = bms_add_members(local_nonnullable_rels,
nonnullable_rels);
- local_forced_null_vars = list_concat(local_forced_null_vars,
- forced_null_vars);
+ local_forced_null_vars = mbms_add_members(local_forced_null_vars,
+ forced_null_vars);
}
}
else
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 317c10c2b9..33790a4f46 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -31,6 +31,7 @@
#include "funcapi.h"
#include "miscadmin.h"
#include "nodes/makefuncs.h"
+#include "nodes/multibitmapset.h"
#include "nodes/nodeFuncs.h"
#include "nodes/subscripting.h"
#include "nodes/supportnodes.h"
@@ -1566,7 +1567,7 @@ find_nonnullable_rels_walker(Node *node, bool top_level)
* find_nonnullable_vars
* Determine which Vars are forced nonnullable by given clause.
*
- * Returns a list of all level-zero Vars that are referenced in the clause in
+ * Returns the set of all level-zero Vars that are referenced in the clause in
* such a way that the clause cannot possibly return TRUE if any of these Vars
* is NULL. (It is OK to err on the side of conservatism; hence the analysis
* here is simplistic.)
@@ -1578,8 +1579,9 @@ find_nonnullable_rels_walker(Node *node, bool top_level)
* the expression to have been AND/OR flattened and converted to implicit-AND
* format.
*
- * The result is a palloc'd List, but we have not copied the member Var nodes.
- * Also, we don't bother trying to eliminate duplicate entries.
+ * Attnos of the identified Vars are returned in a multibitmapset (a List of
+ * Bitmapsets). List indexes correspond to relids (varnos), while the per-rel
+ * Bitmapsets hold varattnos offset by FirstLowInvalidHeapAttributeNumber.
*
* top_level is true while scanning top-level AND/OR structure; here, showing
* the result is either FALSE or NULL is good enough. top_level is false when
@@ -1608,7 +1610,9 @@ find_nonnullable_vars_walker(Node *node, bool top_level)
Var *var = (Var *) node;
if (var->varlevelsup == 0)
- result = list_make1(var);
+ result = mbms_add_member(result,
+ var->varno,
+ var->varattno - FirstLowInvalidHeapAttributeNumber);
}
else if (IsA(node, List))
{
@@ -1623,9 +1627,9 @@ find_nonnullable_vars_walker(Node *node, bool top_level)
*/
foreach(l, (List *) node)
{
- result = list_concat(result,
- find_nonnullable_vars_walker(lfirst(l),
- top_level));
+ result = mbms_add_members(result,
+ find_nonnullable_vars_walker(lfirst(l),
+ top_level));
}
}
else if (IsA(node, FuncExpr))
@@ -1657,7 +1661,12 @@ find_nonnullable_vars_walker(Node *node, bool top_level)
switch (expr->boolop)
{
case AND_EXPR:
- /* At top level we can just recurse (to the List case) */
+
+ /*
+ * At top level we can just recurse (to the List case), since
+ * the result should be the union of what we can prove in each
+ * arm.
+ */
if (top_level)
{
result = find_nonnullable_vars_walker((Node *) expr->args,
@@ -1689,7 +1698,7 @@ find_nonnullable_vars_walker(Node *node, bool top_level)
if (result == NIL) /* first subresult? */
result = subresult;
else
- result = list_intersection(result, subresult);
+ result = mbms_int_members(result, subresult);
/*
* If the intersection is empty, we can stop looking. This
@@ -1788,8 +1797,8 @@ find_nonnullable_vars_walker(Node *node, bool top_level)
* side of conservatism; hence the analysis here is simplistic. In fact,
* we only detect simple "var IS NULL" tests at the top level.)
*
- * The result is a palloc'd List, but we have not copied the member Var nodes.
- * Also, we don't bother trying to eliminate duplicate entries.
+ * As with find_nonnullable_vars, we return the varattnos of the identified
+ * Vars in a multibitmapset.
*/
List *
find_forced_null_vars(Node *node)
@@ -1804,7 +1813,9 @@ find_forced_null_vars(Node *node)
var = find_forced_null_var(node);
if (var)
{
- result = list_make1(var);
+ result = mbms_add_member(result,
+ var->varno,
+ var->varattno - FirstLowInvalidHeapAttributeNumber);
}
/* Otherwise, handle AND-conditions */
else if (IsA(node, List))
@@ -1815,8 +1826,8 @@ find_forced_null_vars(Node *node)
*/
foreach(l, (List *) node)
{
- result = list_concat(result,
- find_forced_null_vars(lfirst(l)));
+ result = mbms_add_members(result,
+ find_forced_null_vars((Node *) lfirst(l)));
}
}
else if (IsA(node, BoolExpr))
diff --git a/src/include/nodes/multibitmapset.h b/src/include/nodes/multibitmapset.h
new file mode 100644
index 0000000000..8c6695aeda
--- /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 */
Amit Langote <amitlangote09@gmail.com> writes:
> On Mon, Nov 14, 2022 at 11:57 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> + * The new member is identified by the zero-based index of the List
>> + * element it should go into, and the bit number to be set therein.
> The comment sounds a bit ambiguous, especially the ", and the bit
> number to be set therein." part. If you meant to describe the
> arguments, how about mentioning their names too, as in:
Done that way in the patch I just posted.
>> + /* forboth will stop at the end of the shorter list, which is fine */
> Isn't this comment unnecessary given that the while loop makes both
> lists be the same length?
No, the while loop ensures that a is at least as long as b.
It could have started out longer, though.
regards, tom lane
Re: List of Bitmapset (was Re: ExecRTCheckPerms() and many prunable partitions)
From
Amit Langote
Date:
On Wed, Nov 16, 2022 at 3:25 AM Tom Lane <tgl@sss.pgh.pa.us> wrote: > Amit Langote <amitlangote09@gmail.com> writes: > > On Mon, Nov 14, 2022 at 11:57 PM Tom Lane <tgl@sss.pgh.pa.us> wrote: > >> + * The new member is identified by the zero-based index of the List > >> + * element it should go into, and the bit number to be set therein. > > > The comment sounds a bit ambiguous, especially the ", and the bit > > number to be set therein." part. If you meant to describe the > > arguments, how about mentioning their names too, as in: > > Done that way in the patch I just posted. Thanks. > >> + /* forboth will stop at the end of the shorter list, which is fine */ > > > Isn't this comment unnecessary given that the while loop makes both > > lists be the same length? > > No, the while loop ensures that a is at least as long as b. > It could have started out longer, though. Oops, I missed that case. The latest version looks pretty good to me. -- Thanks, Amit Langote EDB: http://www.enterprisedb.com