remove_useless_joins vs. bug #19560

I've traced through bug #19560 [1], and determined that what is
happening is this:

1. After flattening the CTE and recognizing that the join to it
can be discarded, we are left with the outer join between the
two real tables, plus a WHERE clause that looks like
"Var = PlaceHolderVar", where the PHV is marked as needing to
be evaluated above the outer join. So far so good.

2. Within deconstruct_jointree, we break the WHERE clause down
into an EquivalenceClass.

3. remove_useless_joins detects that the outer join's RHS is
unique and we don't need any values from the RHS above the join,
so we can remove that join too. It runs around and does a
not-great job of removing references to the removed RTE.

4. The EquivalenceClass now represents a base restriction clause,
since the only rel it still references is the one surviving relation
(the "items" table).

5. But we've already generated base restriction clauses, and
remove_useless_joins does nothing to reconsider that. So the
WHERE clause effectively disappears into the ether: it will
never get propagated into the generated plan.

I'm more than slightly astonished that nobody has reported this
before, because it seems like a failure mode that could be reached
fairly easily. I think it wasn't reachable before v16, because
before we had "nullingrels" we had to avoid treating clauses like
this one as EquivalenceClasses. But that seems like plenty of time
for someone to notice they were getting wrong answers.

Anyway, what to do? I imagine we could write some code in
analyzejoins.c to consider whether ECs give rise to base restriction
clauses that they didn't before. But that seems ugly and fragile.
More generally, there is nothing that is not ugly and fragile about
analyzejoins.c's relation removal logic, and the recent addition of
self-join elimination made that situation even worse. I think we
have a permanent maintenance gotcha there.

I have a modest proposal to make instead: let's nuke all that logic
from orbit. Revise analyzejoins.c so that it does join removals
working strictly on the jointree representation, which is simpler
and far more stable than any of the planner's derived data. Then,
if we successfully removed any joins, throw away all the derived
data and loop back around within query_planner() to redo
deconstruct_jointree and all the rest of it.

I'm not sure offhand what the implications would be for planning
speed. It's possible that this'd actually be faster, considering
what a mess the relation-removal logic is. But in any case, we
have a bug-prone maintenance nightmare there, and it will get
worse not better as people add more stuff to the planner. I think
the current approach is unsustainable.

I don't, at present, have a feeling for whether this approach would
lead to a back-patchable fix for the immediate bug. Maybe we'd take
the risk of a back-patch even if it's bigger than the average
back-patched change. I find it hard to believe that there are not
other bugs lurking in there, given that remove_leftjoinrel_from_query
intentionally only bothers to "update parts of the planner's data
structures that will actually be consulted later" but it has no good
way to be sure what those are, nor are there any forcing functions to
keep it in sync with what the rest of the code thinks. The SJE code
seems as bad or worse.

Thoughts?

regards, tom lane

[1] https://www.postgresql.org/message-id/19560-54cd7ede78d5e355%40postgresql.org