Re: Making empty Bitmapsets always be NULL - Mailing list pgsql-hackers

Nathan Bossart <nathandbossart@gmail.com> writes:
> On Tue, Feb 28, 2023 at 04:59:48PM -0500, Tom Lane wrote:
>> When I designed the Bitmapset module, I set things up so that an empty
>> Bitmapset could be represented either by a NULL pointer, or by an
>> allocated object all of whose bits are zero.  I've recently come to
>> the conclusion that that was a bad idea and we should instead have
>> a convention like the longstanding invariant for Lists: an empty
>> list is represented by NIL and nothing else.

> +1

Thanks for looking at this.

> Unless there is a way to avoid the invariant violation that doesn't involve
> scanning the rest of the words before bms_first_member returns, +1 to
> removing it.  Perhaps we could add a num_members variable to the struct so
> that we know right away when the set becomes empty.  But maintaining that
> might be more trouble than it's worth.

bms_first_member is definitely legacy code, so let's just get
rid of it.  Done like that in 0001 below.  (This was slightly more
complex than I foresaw, because some of the callers were modifying
the result variables.  But they're probably cleaner this way anyway.)

>> I also discovered that nodeAppend.c is relying on bms_del_members
>> not reducing a non-empty set to NULL, because it uses the nullness
>> of appendstate->as_valid_subplans as a state boolean.

> The separate boolean certainly seems less fragile.  That might even be
> worthwhile independent of the rest of the patch.

Yeah.  I split out those executor fixes as 0002; 0003 is the changes
to bitmapsets proper, and then 0004 removes now-dead code.

            regards, tom lane

From b60df906e9894d061f3f37025b92c6b258e9c8fc Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Wed, 1 Mar 2023 17:02:30 -0500
Subject: [PATCH v2 1/4] Remove bms_first_member().

This function has been semi-deprecated ever since we invented
bms_next_member().  Its habit of scribbling on the input bitmapset
isn't great, plus for sufficiently large bitmapsets it would take
O(N^2) time to complete a loop.  Now we have the additional problem
that reducing the input to empty while leaving it still accessible
would violate a proposed invariant.  So let's just get rid of it,
after updating the few extant callers to use bms_next_member().

Discussion: https://postgr.es/m/1159933.1677621588@sss.pgh.pa.us
---
 contrib/file_fdw/file_fdw.c                |  9 ++---
 contrib/sepgsql/dml.c                      |  3 +-
 src/backend/access/heap/heapam.c           | 27 +++++---------
 src/backend/executor/nodeAgg.c             |  3 +-
 src/backend/nodes/bitmapset.c              | 42 ----------------------
 src/backend/optimizer/plan/subselect.c     |  3 +-
 src/backend/parser/parse_expr.c            |  2 +-
 src/backend/replication/logical/relation.c |  3 +-
 src/include/nodes/bitmapset.h              |  1 -
 9 files changed, 23 insertions(+), 70 deletions(-)

diff --git a/contrib/file_fdw/file_fdw.c b/contrib/file_fdw/file_fdw.c
index 8ccc167548..2d2b0b6a6b 100644
--- a/contrib/file_fdw/file_fdw.c
+++ b/contrib/file_fdw/file_fdw.c
@@ -858,7 +858,7 @@ check_selective_binary_conversion(RelOptInfo *baserel,
     ListCell   *lc;
     Relation    rel;
     TupleDesc    tupleDesc;
-    AttrNumber    attnum;
+    int            attidx;
     Bitmapset  *attrs_used = NULL;
     bool        has_wholerow = false;
     int            numattrs;
@@ -901,10 +901,11 @@ check_selective_binary_conversion(RelOptInfo *baserel,
     rel = table_open(foreigntableid, AccessShareLock);
     tupleDesc = RelationGetDescr(rel);

-    while ((attnum = bms_first_member(attrs_used)) >= 0)
+    attidx = -1;
+    while ((attidx = bms_next_member(attrs_used, attidx)) >= 0)
     {
-        /* Adjust for system attributes. */
-        attnum += FirstLowInvalidHeapAttributeNumber;
+        /* attidx is zero-based, attnum is the normal attribute number */
+        AttrNumber    attnum = attidx + FirstLowInvalidHeapAttributeNumber;

         if (attnum == 0)
         {
diff --git a/contrib/sepgsql/dml.c b/contrib/sepgsql/dml.c
index 3cc927c79e..8c8f6f1e3a 100644
--- a/contrib/sepgsql/dml.c
+++ b/contrib/sepgsql/dml.c
@@ -231,7 +231,8 @@ check_relation_privileges(Oid relOid,
     updated = fixup_whole_row_references(relOid, updated);
     columns = bms_union(selected, bms_union(inserted, updated));

-    while ((index = bms_first_member(columns)) >= 0)
+    index = -1;
+    while ((index = bms_next_member(columns, index)) >= 0)
     {
         AttrNumber    attnum;
         uint32        column_perms = 0;
diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 7eb79cee58..a84290c434 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -3859,9 +3859,6 @@ heap_attr_equals(TupleDesc tupdesc, int attrnum, Datum value1, Datum value2,
  * has_external indicates if any of the unmodified attributes (from those
  * listed as interesting) of the old tuple is a member of external_cols and is
  * stored externally.
- *
- * The input interesting_cols bitmapset is destructively modified; that is OK
- * since this is invoked at most once in heap_update.
  */
 static Bitmapset *
 HeapDetermineColumnsInfo(Relation relation,
@@ -3870,19 +3867,20 @@ HeapDetermineColumnsInfo(Relation relation,
                          HeapTuple oldtup, HeapTuple newtup,
                          bool *has_external)
 {
-    int            attrnum;
+    int            attidx;
     Bitmapset  *modified = NULL;
     TupleDesc    tupdesc = RelationGetDescr(relation);

-    while ((attrnum = bms_first_member(interesting_cols)) >= 0)
+    attidx = -1;
+    while ((attidx = bms_next_member(interesting_cols, attidx)) >= 0)
     {
+        /* attidx is zero-based, attrnum is the normal attribute number */
+        int            attrnum = attidx + FirstLowInvalidHeapAttributeNumber;
         Datum        value1,
                     value2;
         bool        isnull1,
                     isnull2;

-        attrnum += FirstLowInvalidHeapAttributeNumber;
-
         /*
          * If it's a whole-tuple reference, say "not equal".  It's not really
          * worth supporting this case, since it could only succeed after a
@@ -3890,9 +3888,7 @@ HeapDetermineColumnsInfo(Relation relation,
          */
         if (attrnum == 0)
         {
-            modified = bms_add_member(modified,
-                                      attrnum -
-                                      FirstLowInvalidHeapAttributeNumber);
+            modified = bms_add_member(modified, attidx);
             continue;
         }

@@ -3905,9 +3901,7 @@ HeapDetermineColumnsInfo(Relation relation,
         {
             if (attrnum != TableOidAttributeNumber)
             {
-                modified = bms_add_member(modified,
-                                          attrnum -
-                                          FirstLowInvalidHeapAttributeNumber);
+                modified = bms_add_member(modified, attidx);
                 continue;
             }
         }
@@ -3924,9 +3918,7 @@ HeapDetermineColumnsInfo(Relation relation,
         if (!heap_attr_equals(tupdesc, attrnum, value1,
                               value2, isnull1, isnull2))
         {
-            modified = bms_add_member(modified,
-                                      attrnum -
-                                      FirstLowInvalidHeapAttributeNumber);
+            modified = bms_add_member(modified, attidx);
             continue;
         }

@@ -3943,8 +3935,7 @@ HeapDetermineColumnsInfo(Relation relation,
          * member of external_cols.
          */
         if (VARATT_IS_EXTERNAL((struct varlena *) DatumGetPointer(value1)) &&
-            bms_is_member(attrnum - FirstLowInvalidHeapAttributeNumber,
-                          external_cols))
+            bms_is_member(attidx, external_cols))
             *has_external = true;
     }

diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 20d23696a5..5960e4a6c1 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -1646,7 +1646,8 @@ find_hash_columns(AggState *aggstate)
         }

         /* and add the remaining columns */
-        while ((i = bms_first_member(colnos)) >= 0)
+        i = -1;
+        while ((i = bms_next_member(colnos, i)) >= 0)
         {
             perhash->hashGrpColIdxInput[perhash->numhashGrpCols] = i;
             perhash->numhashGrpCols++;
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 98660524ad..10dbbdddf5 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -982,48 +982,6 @@ bms_join(Bitmapset *a, Bitmapset *b)
     return result;
 }

-/*
- * bms_first_member - find and remove first member of a set
- *
- * Returns -1 if set is empty.  NB: set is destructively modified!
- *
- * This is intended as support for iterating through the members of a set.
- * The typical pattern is
- *
- *            while ((x = bms_first_member(inputset)) >= 0)
- *                process member x;
- *
- * CAUTION: this destroys the content of "inputset".  If the set must
- * not be modified, use bms_next_member instead.
- */
-int
-bms_first_member(Bitmapset *a)
-{
-    int            nwords;
-    int            wordnum;
-
-    if (a == NULL)
-        return -1;
-    nwords = a->nwords;
-    for (wordnum = 0; wordnum < nwords; wordnum++)
-    {
-        bitmapword    w = a->words[wordnum];
-
-        if (w != 0)
-        {
-            int            result;
-
-            w = RIGHTMOST_ONE(w);
-            a->words[wordnum] &= ~w;
-
-            result = wordnum * BITS_PER_BITMAPWORD;
-            result += bmw_rightmost_one_pos(w);
-            return result;
-        }
-    }
-    return -1;
-}
-
 /*
  * bms_next_member - find next member of a set
  *
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 04eda4798e..22ffe4ca42 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -1481,7 +1481,8 @@ convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
      */
     clause_varnos = pull_varnos(root, whereClause);
     upper_varnos = NULL;
-    while ((varno = bms_first_member(clause_varnos)) >= 0)
+    varno = -1;
+    while ((varno = bms_next_member(clause_varnos, varno)) >= 0)
     {
         if (varno <= rtoffset)
             upper_varnos = bms_add_member(upper_varnos, varno);
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 7ff41acb84..78221d2e0f 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -2759,7 +2759,7 @@ make_row_comparison_op(ParseState *pstate, List *opname,
      * them ... this coding arbitrarily picks the lowest btree strategy
      * number.
      */
-    i = bms_first_member(strats);
+    i = bms_next_member(strats, -1);
     if (i < 0)
     {
         /* No common interpretation, so fail */
diff --git a/src/backend/replication/logical/relation.c b/src/backend/replication/logical/relation.c
index 9f139c64db..55bfa07871 100644
--- a/src/backend/replication/logical/relation.c
+++ b/src/backend/replication/logical/relation.c
@@ -227,7 +227,8 @@ logicalrep_report_missing_attrs(LogicalRepRelation *remoterel,

         initStringInfo(&missingattsbuf);

-        while ((i = bms_first_member(missingatts)) >= 0)
+        i = -1;
+        while ((i = bms_next_member(missingatts, i)) >= 0)
         {
             missingattcnt++;
             if (missingattcnt == 1)
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index 3d2225e1ae..c344ac04be 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -115,7 +115,6 @@ extern Bitmapset *bms_del_members(Bitmapset *a, const Bitmapset *b);
 extern Bitmapset *bms_join(Bitmapset *a, Bitmapset *b);

 /* support for iterating through the integer elements of a set: */
-extern int    bms_first_member(Bitmapset *a);
 extern int    bms_next_member(const Bitmapset *a, int prevbit);
 extern int    bms_prev_member(const Bitmapset *a, int prevbit);

--
2.31.1

From 8a5e732157f5faaac234ea037998ac278721edef Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Wed, 1 Mar 2023 17:27:34 -0500
Subject: [PATCH v2 2/4] Mop up some undue familiarity with the innards of
 Bitmapsets.

nodeAppend.c used non-nullness of appendstate->as_valid_subplans as
a state flag to indicate whether it'd done ExecFindMatchingSubPlans
(or some sufficient approximation to that).  This was pretty
questionable even in the beginning, since it wouldn't really work
right if there are no valid subplans.  It got more questionable
after commit 27e1f1456 added logic that could reduce as_valid_subplans
to an empty set: at that point we were depending on unspecified
behavior of bms_del_members, namely that it'd not return an empty
set as NULL.  It's about to start doing that, which breaks this
logic entirely.  Hence, add a separate boolean flag to signal
whether as_valid_subplans has been computed.

Also fix a previously-cosmetic bug in nodeAgg.c, wherein it ignored
the return value of bms_del_member instead of updating its pointer.

Discussion: https://postgr.es/m/1159933.1677621588@sss.pgh.pa.us
---
 src/backend/executor/nodeAgg.c    |  2 +-
 src/backend/executor/nodeAppend.c | 37 +++++++++++++++++++------------
 src/include/nodes/execnodes.h     |  1 +
 3 files changed, 25 insertions(+), 15 deletions(-)

diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 5960e4a6c1..19342a420c 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -1642,7 +1642,7 @@ find_hash_columns(AggState *aggstate)
             perhash->hashGrpColIdxHash[i] = i + 1;
             perhash->numhashGrpCols++;
             /* delete already mapped columns */
-            bms_del_member(colnos, grpColIdx[i]);
+            colnos = bms_del_member(colnos, grpColIdx[i]);
         }

         /* and add the remaining columns */
diff --git a/src/backend/executor/nodeAppend.c b/src/backend/executor/nodeAppend.c
index cb25499b3f..c185b11c67 100644
--- a/src/backend/executor/nodeAppend.c
+++ b/src/backend/executor/nodeAppend.c
@@ -157,7 +157,10 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
          * later calls to ExecFindMatchingSubPlans.
          */
         if (!prunestate->do_exec_prune && nplans > 0)
+        {
             appendstate->as_valid_subplans = bms_add_range(NULL, 0, nplans - 1);
+            appendstate->as_valid_subplans_identified = true;
+        }
     }
     else
     {
@@ -170,6 +173,7 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
         Assert(nplans > 0);
         appendstate->as_valid_subplans = validsubplans =
             bms_add_range(NULL, 0, nplans - 1);
+        appendstate->as_valid_subplans_identified = true;
         appendstate->as_prune_state = NULL;
     }

@@ -259,7 +263,7 @@ ExecInitAppend(Append *node, EState *estate, int eflags)
         appendstate->as_asyncresults = (TupleTableSlot **)
             palloc0(nasyncplans * sizeof(TupleTableSlot *));

-        if (appendstate->as_valid_subplans != NULL)
+        if (appendstate->as_valid_subplans_identified)
             classify_matching_subplans(appendstate);
     }

@@ -414,13 +418,11 @@ ExecReScanAppend(AppendState *node)
         bms_overlap(node->ps.chgParam,
                     node->as_prune_state->execparamids))
     {
+        node->as_valid_subplans_identified = false;
         bms_free(node->as_valid_subplans);
         node->as_valid_subplans = NULL;
-        if (nasyncplans > 0)
-        {
-            bms_free(node->as_valid_asyncplans);
-            node->as_valid_asyncplans = NULL;
-        }
+        bms_free(node->as_valid_asyncplans);
+        node->as_valid_asyncplans = NULL;
     }

     for (i = 0; i < node->as_nplans; i++)
@@ -574,11 +576,14 @@ choose_next_subplan_locally(AppendState *node)
         if (node->as_nasyncplans > 0)
         {
             /* We'd have filled as_valid_subplans already */
-            Assert(node->as_valid_subplans);
+            Assert(node->as_valid_subplans_identified);
         }
-        else if (node->as_valid_subplans == NULL)
+        else if (!node->as_valid_subplans_identified)
+        {
             node->as_valid_subplans =
                 ExecFindMatchingSubPlans(node->as_prune_state, false);
+            node->as_valid_subplans_identified = true;
+        }

         whichplan = -1;
     }
@@ -640,10 +645,11 @@ choose_next_subplan_for_leader(AppendState *node)
          * run-time pruning is disabled then the valid subplans will always be
          * set to all subplans.
          */
-        if (node->as_valid_subplans == NULL)
+        if (!node->as_valid_subplans_identified)
         {
             node->as_valid_subplans =
                 ExecFindMatchingSubPlans(node->as_prune_state, false);
+            node->as_valid_subplans_identified = true;

             /*
              * Mark each invalid plan as finished to allow the loop below to
@@ -715,10 +721,12 @@ choose_next_subplan_for_worker(AppendState *node)
      * run-time pruning is disabled then the valid subplans will always be set
      * to all subplans.
      */
-    else if (node->as_valid_subplans == NULL)
+    else if (!node->as_valid_subplans_identified)
     {
         node->as_valid_subplans =
             ExecFindMatchingSubPlans(node->as_prune_state, false);
+        node->as_valid_subplans_identified = true;
+
         mark_invalid_subplans_as_finished(node);
     }

@@ -866,10 +874,11 @@ ExecAppendAsyncBegin(AppendState *node)
     Assert(node->as_nasyncplans > 0);

     /* If we've yet to determine the valid subplans then do so now. */
-    if (node->as_valid_subplans == NULL)
+    if (!node->as_valid_subplans_identified)
     {
         node->as_valid_subplans =
             ExecFindMatchingSubPlans(node->as_prune_state, false);
+        node->as_valid_subplans_identified = true;

         classify_matching_subplans(node);
     }
@@ -1143,6 +1152,7 @@ classify_matching_subplans(AppendState *node)
 {
     Bitmapset  *valid_asyncplans;

+    Assert(node->as_valid_subplans_identified);
     Assert(node->as_valid_asyncplans == NULL);

     /* Nothing to do if there are no valid subplans. */
@@ -1161,9 +1171,8 @@ classify_matching_subplans(AppendState *node)
     }

     /* Get valid async subplans. */
-    valid_asyncplans = bms_copy(node->as_asyncplans);
-    valid_asyncplans = bms_int_members(valid_asyncplans,
-                                       node->as_valid_subplans);
+    valid_asyncplans = bms_intersect(node->as_asyncplans,
+                                     node->as_valid_subplans);

     /* Adjust the valid subplans to contain sync subplans only. */
     node->as_valid_subplans = bms_del_members(node->as_valid_subplans,
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 20f4c8b35f..e7eb1e666f 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1350,6 +1350,7 @@ struct AppendState
     ParallelAppendState *as_pstate; /* parallel coordination info */
     Size        pstate_len;        /* size of parallel coordination info */
     struct PartitionPruneState *as_prune_state;
+    bool        as_valid_subplans_identified;    /* is as_valid_subplans valid? */
     Bitmapset  *as_valid_subplans;
     Bitmapset  *as_valid_asyncplans;    /* valid asynchronous plans indexes */
     bool        (*choose_next_subplan) (AppendState *);
--
2.31.1

From 54644de166623238b2411c8710cd4bab9f97bfdc Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Wed, 1 Mar 2023 17:44:06 -0500
Subject: [PATCH v2 3/4] Require empty Bitmapsets to be represented as NULL.

When I designed the Bitmapset module, I set things up so that an empty
Bitmapset could be represented either by a NULL pointer, or by an
allocated object all of whose bits are zero.  I've recently come to
the conclusion that that was a bad idea and we should instead have a
convention like the longstanding invariant for Lists, whereby an empty
list is represented by NIL and nothing else.

To do this, we need to fix bms_intersect, bms_difference, and a couple
of other functions to check for having produced an empty result; but
then we can replace bms_is_empty(a) by a simple "a == NULL" test.

This is very likely a (marginal) win performance-wise, because we
call bms_is_empty many more times than those other functions put
together.  However, the real reason to do it is that we have various
places that have hand-implemented a rule about "this Bitmapset
variable must be exactly NULL if empty", so that they can use
checks-for-null in place of bms_is_empty calls in particularly hot
code paths.  That is a really fragile, mistake-prone way to do things,
and I'm surprised that we've seldom been bitten by it.  It's not well
documented at all which variables have this property, so you can't
readily tell which code might be violating those conventions.  By
making the convention universal, we can eliminate a subtle source of
bugs.

Discussion: https://postgr.es/m/1159933.1677621588@sss.pgh.pa.us
---
 src/backend/nodes/bitmapset.c | 67 ++++++++++++++++++++++++++---------
 src/include/nodes/bitmapset.h | 10 +++---
 2 files changed, 56 insertions(+), 21 deletions(-)

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 10dbbdddf5..c43de74cdf 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -5,10 +5,8 @@
  *
  * A bitmap set can represent any set of nonnegative integers, although
  * it is mainly intended for sets where the maximum value is not large,
- * say at most a few hundred.  By convention, a NULL pointer is always
- * accepted by all operations to represent the empty set.  (But beware
- * that this is not the only representation of the empty set.  Use
- * bms_is_empty() in preference to testing for NULL.)
+ * say at most a few hundred.  By convention, we always represent the
+ * empty set by a NULL pointer.
  *
  *
  * Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -66,6 +64,8 @@
 #error "invalid BITS_PER_BITMAPWORD"
 #endif

+static bool bms_is_empty_internal(const Bitmapset *a);
+

 /*
  * bms_copy - make a palloc'd copy of a bitmapset
@@ -104,10 +104,10 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
     {
         if (b == NULL)
             return true;
-        return bms_is_empty(b);
+        return false;
     }
     else if (b == NULL)
-        return bms_is_empty(a);
+        return false;
     /* Identify shorter and longer input */
     if (a->nwords <= b->nwords)
     {
@@ -151,9 +151,9 @@ bms_compare(const Bitmapset *a, const Bitmapset *b)

     /* Handle cases where either input is NULL */
     if (a == NULL)
-        return bms_is_empty(b) ? 0 : -1;
+        return (b == NULL) ? 0 : -1;
     else if (b == NULL)
-        return bms_is_empty(a) ? 0 : +1;
+        return +1;
     /* Handle cases where one input is longer than the other */
     shortlen = Min(a->nwords, b->nwords);
     for (i = shortlen; i < a->nwords; i++)
@@ -282,6 +282,12 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
     resultlen = result->nwords;
     for (i = 0; i < resultlen; i++)
         result->words[i] &= other->words[i];
+    /* If we computed an empty result, we must return NULL */
+    if (bms_is_empty_internal(result))
+    {
+        pfree(result);
+        return NULL;
+    }
     return result;
 }

@@ -300,12 +306,22 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
         return NULL;
     if (b == NULL)
         return bms_copy(a);
+
+    /*
+     * In Postgres' usage, an empty result is a very common case, so it's
+     * worth optimizing for that by testing bms_nonempty_difference().  This
+     * saves us a palloc/pfree cycle compared to checking after-the-fact.
+     */
+    if (!bms_nonempty_difference(a, b))
+        return NULL;
+
     /* Copy the left input */
     result = bms_copy(a);
     /* And remove b's bits from result */
     shortlen = Min(a->nwords, b->nwords);
     for (i = 0; i < shortlen; i++)
         result->words[i] &= ~b->words[i];
+    /* Need not check for empty result, since we handled that case above */
     return result;
 }

@@ -323,7 +339,7 @@ bms_is_subset(const Bitmapset *a, const Bitmapset *b)
     if (a == NULL)
         return true;            /* empty set is a subset of anything */
     if (b == NULL)
-        return bms_is_empty(a);
+        return false;
     /* Check common words */
     shortlen = Min(a->nwords, b->nwords);
     for (i = 0; i < shortlen; i++)
@@ -362,10 +378,10 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
     {
         if (b == NULL)
             return BMS_EQUAL;
-        return bms_is_empty(b) ? BMS_EQUAL : BMS_SUBSET1;
+        return BMS_SUBSET1;
     }
     if (b == NULL)
-        return bms_is_empty(a) ? BMS_EQUAL : BMS_SUBSET2;
+        return BMS_SUBSET2;
     /* Check common words */
     result = BMS_EQUAL;            /* status so far */
     shortlen = Min(a->nwords, b->nwords);
@@ -554,7 +570,7 @@ bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
     if (a == NULL)
         return false;
     if (b == NULL)
-        return !bms_is_empty(a);
+        return true;
     /* Check words in common */
     shortlen = Min(a->nwords, b->nwords);
     for (i = 0; i < shortlen; i++)
@@ -696,12 +712,13 @@ bms_membership(const Bitmapset *a)
 }

 /*
- * bms_is_empty - is a set empty?
+ * bms_is_empty_internal - is a set empty?
  *
- * This is even faster than bms_membership().
+ * This is now used only locally, to detect cases where a function has
+ * computed an empty set that we must now get rid of.
  */
-bool
-bms_is_empty(const Bitmapset *a)
+static bool
+bms_is_empty_internal(const Bitmapset *a)
 {
     int            nwords;
     int            wordnum;
@@ -786,6 +803,12 @@ bms_del_member(Bitmapset *a, int x)
     bitnum = BITNUM(x);
     if (wordnum < a->nwords)
         a->words[wordnum] &= ~((bitmapword) 1 << bitnum);
+    /* If we computed an empty result, we must return NULL */
+    if (bms_is_empty_internal(a))
+    {
+        pfree(a);
+        return NULL;
+    }
     return a;
 }

@@ -922,6 +945,12 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
         a->words[i] &= b->words[i];
     for (; i < a->nwords; i++)
         a->words[i] = 0;
+    /* If we computed an empty result, we must return NULL */
+    if (bms_is_empty_internal(a))
+    {
+        pfree(a);
+        return NULL;
+    }
     return a;
 }

@@ -943,6 +972,12 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
     shortlen = Min(a->nwords, b->nwords);
     for (i = 0; i < shortlen; i++)
         a->words[i] &= ~b->words[i];
+    /* If we computed an empty result, we must return NULL */
+    if (bms_is_empty_internal(a))
+    {
+        pfree(a);
+        return NULL;
+    }
     return a;
 }

diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index c344ac04be..14de6a9ff1 100644
--- a/src/include/nodes/bitmapset.h
+++ b/src/include/nodes/bitmapset.h
@@ -5,10 +5,8 @@
  *
  * A bitmap set can represent any set of nonnegative integers, although
  * it is mainly intended for sets where the maximum value is not large,
- * say at most a few hundred.  By convention, a NULL pointer is always
- * accepted by all operations to represent the empty set.  (But beware
- * that this is not the only representation of the empty set.  Use
- * bms_is_empty() in preference to testing for NULL.)
+ * say at most a few hundred.  By convention, we always represent the
+ * empty set by a NULL pointer.
  *
  *
  * Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -102,7 +100,9 @@ extern int    bms_num_members(const Bitmapset *a);

 /* optimized tests when we don't need to know exact membership count: */
 extern BMS_Membership bms_membership(const Bitmapset *a);
-extern bool bms_is_empty(const Bitmapset *a);
+
+/* NULL is now the only allowed representation of an empty bitmapset */
+#define bms_is_empty(a)  ((a) == NULL)

 /* these routines recycle (modify or free) their non-const inputs: */

--
2.31.1

From ae52bce53b203fdee7427963613bf00e42dcddea Mon Sep 17 00:00:00 2001
From: Tom Lane <tgl@sss.pgh.pa.us>
Date: Wed, 1 Mar 2023 17:52:25 -0500
Subject: [PATCH v2 4/4] Remove local optimizations of empty Bitmapsets into
 null pointers.

These are all dead code now that it's done centrally.

Discussion: https://postgr.es/m/1159933.1677621588@sss.pgh.pa.us
---
 src/backend/executor/execUtils.c         | 10 +---------
 src/backend/optimizer/path/indxpath.c    |  3 ---
 src/backend/optimizer/plan/subselect.c   |  9 ---------
 src/backend/optimizer/util/pathnode.c    |  6 ------
 src/backend/optimizer/util/placeholder.c |  2 --
 src/backend/optimizer/util/relnode.c     |  7 -------
 src/backend/rewrite/rewriteManip.c       | 19 ++++---------------
 src/pl/plpgsql/src/pl_exec.c             |  7 ++-----
 8 files changed, 7 insertions(+), 56 deletions(-)

diff --git a/src/backend/executor/execUtils.c b/src/backend/executor/execUtils.c
index c33a3c0bec..cfa95a07e4 100644
--- a/src/backend/executor/execUtils.c
+++ b/src/backend/executor/execUtils.c
@@ -877,15 +877,7 @@ UpdateChangedParamSet(PlanState *node, Bitmapset *newchg)
      * include anything else into its chgParam set.
      */
     parmset = bms_intersect(node->plan->allParam, newchg);
-
-    /*
-     * Keep node->chgParam == NULL if there's not actually any members; this
-     * allows the simplest possible tests in executor node files.
-     */
-    if (!bms_is_empty(parmset))
-        node->chgParam = bms_join(node->chgParam, parmset);
-    else
-        bms_free(parmset);
+    node->chgParam = bms_join(node->chgParam, parmset);
 }

 /*
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 011a0337da..9f4698f2a2 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -949,9 +949,6 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,

     /* We do not want the index's rel itself listed in outer_relids */
     outer_relids = bms_del_member(outer_relids, rel->relid);
-    /* Enforce convention that outer_relids is exactly NULL if empty */
-    if (bms_is_empty(outer_relids))
-        outer_relids = NULL;

     /* Compute loop_count for cost estimation purposes */
     loop_count = get_loop_count(root, rel->relid, outer_relids);
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 22ffe4ca42..052263aea6 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -2825,15 +2825,6 @@ finalize_plan(PlannerInfo *root, Plan *plan,
     /* but not any initplan setParams */
     plan->extParam = bms_del_members(plan->extParam, initSetParam);

-    /*
-     * For speed at execution time, make sure extParam/allParam are actually
-     * NULL if they are empty sets.
-     */
-    if (bms_is_empty(plan->extParam))
-        plan->extParam = NULL;
-    if (bms_is_empty(plan->allParam))
-        plan->allParam = NULL;
-
     return plan->allParam;
 }

diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index d749b50578..e8e06397a9 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -2372,12 +2372,6 @@ calc_nestloop_required_outer(Relids outerrelids,
     /* ... and remove any mention of now-satisfied outer rels */
     required_outer = bms_del_members(required_outer,
                                      outerrelids);
-    /* maintain invariant that required_outer is exactly NULL if empty */
-    if (bms_is_empty(required_outer))
-    {
-        bms_free(required_outer);
-        required_outer = NULL;
-    }
     return required_outer;
 }

diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c
index 9c6cb5eba7..b1723578e6 100644
--- a/src/backend/optimizer/util/placeholder.c
+++ b/src/backend/optimizer/util/placeholder.c
@@ -125,8 +125,6 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
      */
     rels_used = pull_varnos(root, (Node *) phv->phexpr);
     phinfo->ph_lateral = bms_difference(rels_used, phv->phrels);
-    if (bms_is_empty(phinfo->ph_lateral))
-        phinfo->ph_lateral = NULL;    /* make it exactly NULL if empty */
     phinfo->ph_eval_at = bms_int_members(rels_used, phv->phrels);
     /* If no contained vars, force evaluation at syntactic location */
     if (bms_is_empty(phinfo->ph_eval_at))
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 9ad44a0508..68fd033595 100644
--- a/src/backend/optimizer/util/relnode.c
+++ b/src/backend/optimizer/util/relnode.c
@@ -772,8 +772,6 @@ build_join_rel(PlannerInfo *root,
      */
     joinrel->direct_lateral_relids =
         bms_del_members(joinrel->direct_lateral_relids, joinrel->relids);
-    if (bms_is_empty(joinrel->direct_lateral_relids))
-        joinrel->direct_lateral_relids = NULL;

     /*
      * Construct restrict and join clause lists for the new joinrel. (The
@@ -1024,11 +1022,6 @@ min_join_parameterization(PlannerInfo *root,
      */
     result = bms_union(outer_rel->lateral_relids, inner_rel->lateral_relids);
     result = bms_del_members(result, joinrelids);
-
-    /* Maintain invariant that result is exactly NULL if empty */
-    if (bms_is_empty(result))
-        result = NULL;
-
     return result;
 }

diff --git a/src/backend/rewrite/rewriteManip.c b/src/backend/rewrite/rewriteManip.c
index 04718f66c0..d28d0da621 100644
--- a/src/backend/rewrite/rewriteManip.c
+++ b/src/backend/rewrite/rewriteManip.c
@@ -1247,16 +1247,11 @@ remove_nulling_relids_mutator(Node *node,
             !bms_is_member(var->varno, context->except_relids) &&
             bms_overlap(var->varnullingrels, context->removable_relids))
         {
-            Relids        newnullingrels = bms_difference(var->varnullingrels,
-                                                        context->removable_relids);
-
-            /* Micro-optimization: ensure nullingrels is NULL if empty */
-            if (bms_is_empty(newnullingrels))
-                newnullingrels = NULL;
             /* Copy the Var ... */
             var = copyObject(var);
             /* ... and replace the copy's varnullingrels field */
-            var->varnullingrels = newnullingrels;
+            var->varnullingrels = bms_difference(var->varnullingrels,
+                                                 context->removable_relids);
             return (Node *) var;
         }
         /* Otherwise fall through to copy the Var normally */
@@ -1268,26 +1263,20 @@ remove_nulling_relids_mutator(Node *node,
         if (phv->phlevelsup == context->sublevels_up &&
             !bms_overlap(phv->phrels, context->except_relids))
         {
-            Relids        newnullingrels = bms_difference(phv->phnullingrels,
-                                                        context->removable_relids);
-
             /*
-             * Micro-optimization: ensure nullingrels is NULL if empty.
-             *
              * Note: it might seem desirable to remove the PHV altogether if
              * phnullingrels goes to empty.  Currently we dare not do that
              * because we use PHVs in some cases to enforce separate identity
              * of subexpressions; see wrap_non_vars usages in prepjointree.c.
              */
-            if (bms_is_empty(newnullingrels))
-                newnullingrels = NULL;
             /* Copy the PlaceHolderVar and mutate what's below ... */
             phv = (PlaceHolderVar *)
                 expression_tree_mutator(node,
                                         remove_nulling_relids_mutator,
                                         (void *) context);
             /* ... and replace the copy's phnullingrels field */
-            phv->phnullingrels = newnullingrels;
+            phv->phnullingrels = bms_difference(phv->phnullingrels,
+                                                context->removable_relids);
             /* We must also update phrels, if it contains a removable RTI */
             phv->phrels = bms_difference(phv->phrels,
                                          context->removable_relids);
diff --git a/src/pl/plpgsql/src/pl_exec.c b/src/pl/plpgsql/src/pl_exec.c
index ffd6d2e3bc..b0a2cac227 100644
--- a/src/pl/plpgsql/src/pl_exec.c
+++ b/src/pl/plpgsql/src/pl_exec.c
@@ -6240,12 +6240,9 @@ setup_param_list(PLpgSQL_execstate *estate, PLpgSQL_expr *expr)
     Assert(expr->plan != NULL);

     /*
-     * We only need a ParamListInfo if the expression has parameters.  In
-     * principle we should test with bms_is_empty(), but we use a not-null
-     * test because it's faster.  In current usage bits are never removed from
-     * expr->paramnos, only added, so this test is correct anyway.
+     * We only need a ParamListInfo if the expression has parameters.
      */
-    if (expr->paramnos)
+    if (!bms_is_empty(expr->paramnos))
     {
         /* Use the common ParamListInfo */
         paramLI = estate->paramLI;
--
2.31.1