Subject: Re: Revert: Remove useless self-joins *and* -DREALLOCATE_BITMAPSETS make server crash, regress test fail.

From: David Rowley <[email-masked]>
Date: Wed, 8 May 2024 10:47:32 +1200

On Wed, 8 May 2024 at 10:40, Tom Lane <[email-masked]> wrote:
>
> David Rowley <[email-masked]> writes:
> > We could make the policy copy-on-modify.  If you put bms_copy around
> > the bms_del_member() calls in remove_rel_from_query(), does it pass
> > then?
>
> Didn't test, but that route seems awfully invasive and fragile: how
> will we find all the places to modify, or ensure that the policy
> is followed by future patches?

REALLOCATE_BITMAPSETS was invented for this and IMO, it found exactly
the problem it was invented to find.

Copy-on-modify is our policy for node mutation. Why is it ok there but
awfully fragile here?

David

---

From: Tom Lane <[email-masked]>
Date: Tue, 07 May 2024 18:55:56 -0400

> the problem it was invented to find.

Not in a way that gives me any confidence that we found *all* the
problems.  If check-world finds a problem that the core tests did not,
then there's no reason to think there aren't still more issues that
check-world happened not to trip over either.

> Copy-on-modify is our policy for node mutation. Why is it ok there but

It's only partly our policy: there are all those places where we don't
do it that way.  The main problem that I see for trying to be 100%
consistent in that way is that once you modify a sub-node, full
copy-on-modify dictates replacing every ancestor node all the way to
the top of the tree.  That's clearly impractical in the planner data
structures.  So where are we going to stop exactly?

			regards, tom lane

---

From: David Rowley <[email-masked]>
Date: Wed, 8 May 2024 11:03:16 +1200

On Wed, 8 May 2024 at 10:55, Tom Lane <[email-masked]> wrote:
> problems.

Here are some statements I believe to be true:
1. If REALLOCATE_BITMAPSETS is defined then modifications to a
Bitmapset will make a copy and free the original.
2. If a query runs successfully without REALLOCATE_BITMAPSETS and
Assert fails due to an invalid Bitmapset when REALLOCATE_BITMAPSETS is
defined, then we have > 1 pointer pointing to the same set and not all
of them are being updated when the members are added/removed.

Given the above, I can't see what Bitmapset sharing problems we won't
find with REALLOCATE_BITMAPSETS.

Can you share the exact scenario you're worried that we won't find so
I can understand your concern?

David

---

From: Tom Lane <[email-masked]>
Date: Tue, 07 May 2024 19:18:09 -0400

> find with REALLOCATE_BITMAPSETS.

Anything where the trouble spots are in a code path we fail to
exercise with our available test suites.  If you think there are
no such code paths, I'm sorry to disillusion you.

I spent a little bit of time wondering if we could find problems in a
more static way by marking bitmapset fields as "const", but I fear
that would create a huge number of false positives.

			regards, tom lane

---

From: Tom Lane <[email-masked]>
Date: Wed, 08 May 2024 14:24:04 -0400

I traced down the other failure I was seeing in check-world, and
found that it came from deconstruct_distribute doing this:

        distribute_quals_to_rels(root, my_quals,
                                 jtitem,
                                 sjinfo,
                                 root->qual_security_level,
                                 jtitem->qualscope,
                                 ojscope, jtitem->nonnullable_rels,
                                 NULL,    /* incompatible_relids */
                                 true,    /* allow_equivalence */
                                 false, false,    /* not clones */
                                 postponed_oj_qual_list);

where jtitem->nonnullable_rels is the same as the jtitem's left_rels,
which ends up as the syn_lefthand of the join's SpecialJoinInfo, and
then when remove_rel_from_query tries to adjust the syn_lefthand it
breaks the outer_relids of whatever RestrictInfos got made here.

I was able to fix that by not letting jtitem->nonnullable_rels be
the same as left_rels.  The attached alternative_1.patch does pass
check-world.  But I find it mighty unprincipled: the JoinTreeItem
data structures are full of shared relid sets, so why is this
particular sharing not OK?  I still don't have any confidence that
there aren't more problems.

Along about here I started to wonder how come we are only seeing
SpecialJoinInfo-vs-RestrictInfo sharing as a problem, when surely
there is plenty of cross-RestrictInfo sharing going on as well.
(The above call is perfectly capable of making a lot of RestrictInfos,
all with the same outer_relids.)  That thought led me to look at
remove_rel_from_restrictinfo, and darn if I didn't find this:

    /*
     * The clause_relids probably aren't shared with anything else, but let's
     * copy them just to be sure.
     */
    rinfo->clause_relids = bms_copy(rinfo->clause_relids);
    ...
    /* Likewise for required_relids */
    rinfo->required_relids = bms_copy(rinfo->required_relids);

So the reason we don't see cross-RestrictInfo breakage is that
analyzejoins.c is careful not to modify the original relid sets
when modifying a RestrictInfo.  (This comment is clearly wrong.)

And that leads to the thought that we can fix our current sharing
problems by similarly avoiding overwriting the original sets
in remove_rel_from_query.  The attached alternative-2.patch
attacks it that way, and also passes check-world.

I like alternative-2.patch a lot better, not least because it
only adds cycles when join removal actually fires.  Basically
this is putting the onus on the data structure modifier to
cope with shared bitmapsets, rather than trying to say that
sharing is disallowed.

Thoughts?

			regards, tom lane

diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index e2c68fe6f9..4198e9c83a 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -979,7 +979,7 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode,
 													right_item->inner_join_rels);
 				jtitem->left_rels = left_item->qualscope;
 				jtitem->right_rels = right_item->qualscope;
-				jtitem->nonnullable_rels = left_item->qualscope;
+				jtitem->nonnullable_rels = bms_copy(left_item->qualscope);
 				break;
 			case JOIN_SEMI:
 				/* This node belongs to parent_domain, as do its children */
@@ -1053,7 +1053,7 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode,
 				jtitem->left_rels = left_item->qualscope;
 				jtitem->right_rels = right_item->qualscope;
 				/* each side is both outer and inner */
-				jtitem->nonnullable_rels = jtitem->qualscope;
+				jtitem->nonnullable_rels = bms_copy(jtitem->qualscope);
 				break;
 			default:
 				/* JOIN_RIGHT was eliminated during reduce_outer_joins() */
@@ -1888,7 +1888,7 @@ deconstruct_distribute_oj_quals(PlannerInfo *root,
 	qualscope = bms_union(sjinfo->syn_lefthand, sjinfo->syn_righthand);
 	qualscope = bms_add_member(qualscope, sjinfo->ojrelid);
 	ojscope = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
-	nonnullable_rels = sjinfo->syn_lefthand;
+	nonnullable_rels = bms_copy(sjinfo->syn_lefthand);
 
 	/*
 	 * If this join can commute with any other ones per outer-join identity 3,
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index aa72592567..1c9acf864c 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -390,6 +390,17 @@ remove_rel_from_query(PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
 	{
 		SpecialJoinInfo *sjinf = (SpecialJoinInfo *) lfirst(l);
 
+		/*
+		 * initsplan.c is fairly cavalier about allowing SpecialJoinInfos'
+		 * lefthand/righthand relid sets to be shared with other data
+		 * structures.  Ensure that we don't modify the original relid sets.
+		 * (The commute_xxx sets are always per-SpecialJoinInfo though.)
+		 */
+		sjinf->min_lefthand = bms_copy(sjinf->min_lefthand);
+		sjinf->min_righthand = bms_copy(sjinf->min_righthand);
+		sjinf->syn_lefthand = bms_copy(sjinf->syn_lefthand);
+		sjinf->syn_righthand = bms_copy(sjinf->syn_righthand);
+		/* Now remove relid and ojrelid bits from the sets: */
 		sjinf->min_lefthand = bms_del_member(sjinf->min_lefthand, relid);
 		sjinf->min_righthand = bms_del_member(sjinf->min_righthand, relid);
 		sjinf->syn_lefthand = bms_del_member(sjinf->syn_lefthand, relid);
@@ -551,8 +562,10 @@ static void
 remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
 {
 	/*
-	 * The clause_relids probably aren't shared with anything else, but let's
-	 * copy them just to be sure.
+	 * initsplan.c is fairly cavalier about allowing RestrictInfos to share
+	 * relid sets with other RestrictInfos (and SpecialJoinInfos for that
+	 * matter).  To avoid breaking things, make sure this RestrictInfo has its
+	 * own clause_relids set before we modify it.
 	 */
 	rinfo->clause_relids = bms_copy(rinfo->clause_relids);
 	rinfo->clause_relids = bms_del_member(rinfo->clause_relids, relid);

---

From: Tom Lane <[email-masked]>
Date: Wed, 08 May 2024 14:49:17 -0400

BTW, now that I've wrapped my head around what's happening here,
I believe that -DREALLOCATE_BITMAPSETS is introducing a bug where
there was none before.  The changes that left-join removal makes
won't cause any of these sets to go to empty, so the bms_del_member
calls won't free the sets but just modify them in-place.  And the
same change will/should be made in every relevant relid set, so
the fact that the sets may be shared isn't hurting anything.

This is, of course, pretty fragile and I'm totally on board with
making it safer.  But there's no live bug in released branches,
and not in HEAD either unless you add -DREALLOCATE_BITMAPSETS.
That accounts for the lack of related field reports, and it means
we don't really need to back-patch anything.

This conclusion also reinforces my previously-vague feeling that
we should not consider making -DREALLOCATE_BITMAPSETS the default in
debug builds, as was proposed upthread.  It's really a fundamentally
different behavior, and I strongly suspect that it can mask bugs as
well as introduce them (by hiding sharing in cases that'd be less
benign than this turns out to be).  I'd rather not do development on
top of bitmapset infrastructure that acts entirely different from
production bitmapset infrastructure.

			regards, tom lane

---

From: David Rowley <[email-masked]>
Date: Thu, 9 May 2024 10:02:06 +1200

> the fact that the sets may be shared isn't hurting anything.

FWIW, it just feels like we're willing to accept that the
bms_del_member() is not updating all copies of the set in this case as
that particular behaviour is ok for this particular case. I know
you're not proposing this, but I don't think that would warrant
relaxing REALLOCATE_BITMAPSETS to not reallocate Bitmapsets on
bms_del_member() and bms_del_members().

If all we have to do to make -DREALLOCATE_BITMAPSETS builds happy in
make check-world is to add a bms_copy inside the bms_del_member()
calls in remove_rel_from_query(), then I think it's a small price to
pay to allow us to maintain the additional coverage that
REALLOCATE_BITMAPSETS provides. That seems like a small price to pay
when the gains are removing an entire join.

> production bitmapset infrastructure.

My primary interest in this feature is using it to catch bugs that
we're unlikely to ever hit in the regression tests.  For example, the
planner works when there are <= 63 RTEs but falls over when there are
64 because some bms_add_member() must reallocate more memory to store
the 64th RTI in a Bitmapset. I'd like to have something to make it
more likely we'll find bugs like this before the release instead of
someone having a crash when they run some obscure query shape
containing > 63 RTEs 2 or 4 years after the release.

I'm happy Andrew added this to prion. Thanks for doing that.

David

---

From: David Rowley <[email-masked]>
Date: Thu, 9 May 2024 10:07:22 +1200

> cope with shared bitmapsets, rather than trying to say that

I'm fine with this one as it's the same as what I already mentioned
earlier.  I had imagined doing bms_del_member(bms_copy ... but maybe
the compiler is able to optimise away the additional store. Likely, it
does not matter much as pallocing memory likely adds far more overhead
anyway.

David

---

From: Tom Lane <[email-masked]>
Date: Wed, 08 May 2024 18:16:19 -0400

> you're not proposing this,

No, I'm not.  I was just trying to explain how come there's not
a visible bug.  I quite agree that this is too fragile to leave
as-is going forward.  (One thing I'm wondering about is whether
we should back-patch despite the lack of visible bug, just in
case some future back-patch relies on the safer behavior.)

>> debug builds, as was proposed upthread.

> containing > 63 RTEs 2 or 4 years after the release.

Again, I think -DREALLOCATE_BITMAPSETS adds a valuable testing weapon.
But if we make that the default in debug builds, then we'll get next
door to zero testing of the behavior without it, and that seems like
a really bad idea given how different the behavior is.

(Speaking of which, I wonder how many buildfarm members build without
--enable-cassert.  The answer could well be "zero", and that's likely
not good.)

> I'm happy Andrew added this to prion. Thanks for doing that.

+1

			regards, tom lane

---

From: Tom Lane <[email-masked]>
Date: Wed, 08 May 2024 18:40:33 -0400

> does not matter much as pallocing memory likely adds far more overhead

I actually wrote it that way to start with, but undid it after
noticing that the existing code in remove_rel_from_restrictinfo
does it in separate steps, and thinking that that was good for
both separation of concerns and a cleaner git history.  I too
can't believe that an extra fetch will be noticeable compared
to the cost of the adjacent bms_xxx operations.

			regards, tom lane

---

From: Richard Guo <[email-masked]>
Date: Thu, 9 May 2024 10:43:31 +0800

> to the cost of the adjacent bms_xxx operations.

I also think it seems better to do bms_copy in separate steps, not only
because this keeps consistent with the existing code in
remove_rel_from_restrictinfo, but also because we need to do
bms_del_member twice for each lefthand/righthand relid set.

Speaking of consistency, do you think it would improve the code's
readability if we rearrange the code in remove_rel_from_query so that
the modifications of the same relid set are grouped together, just like
what we do in remove_rel_from_restrictinfo?  I mean something like:

   sjinf->min_lefthand = bms_copy(sjinf->min_lefthand);
   sjinf->min_lefthand = bms_del_member(sjinf->min_lefthand, relid);
   sjinf->min_lefthand = bms_del_member(sjinf->min_lefthand, ojrelid);

   ...

Thanks
Richard

---

From: Tom Lane <[email-masked]>
Date: Thu, 09 May 2024 11:07:08 -0400

> bms_del_member twice for each lefthand/righthand relid set.

Yeah.  Of course, we don't need a bms_copy() in the second one,
but that'd just add even more asymmetry and chance for confusion.

> what we do in remove_rel_from_restrictinfo?

I left it alone, just because it didn't seem worth cluttering "git
blame" here.

			regards, tom lane