List of Bitmapset (was Re: ExecRTCheckPerms() and many prunable partitions) - Mailing list pgsql-hackers

[ 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);