JOIN_SEMI planning question

Hello,

While looking at bug #15857[1], I wondered why the following two
queries get different plans, given the schema and data from the bug
report:

(1) SELECT COUNT (*)
      FROM a
      JOIN b
        ON a.id=b.base_id
     WHERE EXISTS (
           SELECT 1
             FROM c
            WHERE c.base_id = a.id
           );

(2) SELECT COUNT (*)
      FROM a
      JOIN b
        ON a.id=b.base_id
     WHERE EXISTS (
           SELECT 1
             FROM c
            WHERE c.base_id = b.base_id
           );

The only difference is a.id vs b.base_id in the WHERE clause, and
those are equivalent, and the planner knows it as we can see from the
join cond visible in the plan.  Query 1 gets a JOIN_UNIQUE_INNER for
BC (C is sorted, made unique and then hashed for an inner join with B)
while query 2 gets a JOIN_SEMI for BC (C is hashed for a semi join
with B).  In both cases JOIN_UNIQUE_INNER is considered for BC (though
it's later blocked for PHJ since commit aca127c1), but the better
JOIN_SEMI is considered only for query 2.

The relevant decision logic is in populate_joinrel_with_paths()'s
JOIN_SEMI case, where it considers which of JOIN_SEMI,
JOIN_UNIQUE_INNER and JOIN_UNIQUE_OUTER to add.

Here's my question: how could it ever be OK to sort/unique something
and put it in a hash table, but not OK to put exactly the same thing
in the hash table directly, with JOIN_SEMI logic to prevent multiple
matches?  And likewise for the inner side of other join strategies.
Or to put in in plain C, in what case would the following change be
wrong?

                        /*
                         * We might have a normal semijoin, or a case
where we don't have
                         * enough rels to do the semijoin but can
unique-ify the RHS and
                         * then do an innerjoin (see comments in
join_is_legal).  In the
                         * latter case we can't apply JOIN_SEMI joining.
                         */
-                       if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
-                               bms_is_subset(sjinfo->min_righthand,
rel2->relids))
+                       if ((bms_is_subset(sjinfo->min_lefthand,
rel1->relids) &&
+                                bms_is_subset(sjinfo->min_righthand,
rel2->relids)) ||
+                                bms_equal(sjinfo->syn_righthand, rel2->relids))
                        {
                                if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||

restriction_is_constant_false(restrictlist, joinrel, false))

Or to put it in the language of the comment, how could you ever have
enough rels to do a join between B and unique(C), but not enough rels
to do a semi-join between B and C?

I admit that I don't have a great grasp of equivalence classes,
(min|syn)_(left|right)hand or the join planning code in general,
having focused mostly on execution so far, so the above is a
cargo-cult change and I may be missing something fundamental...

Which plan wins is of course a costing matter, but having the
JOIN_SEMI option available has the advantage of being more profitably
parallelisable, which led me here.  With the above hack you get a
[Parallel] Hash Semi Join for BC with both queries (unless you set
work_mem higher and then you get a much slower merge join, but that's
an entirely separate problem).  Only one regression test plan changes
-- it's structurally similar to the bug report query, but at a glance
the new plan is better anyway.  The test still demonstrates what it
wants to demonstrate (namely that the absence or presence of a unique
index causes the plan to change, and with the above hack that is even
clearer because the two plans now differ only in "Nested Loop Semi
Join" vs "Nested Loop").

[1] https://www.postgresql.org/message-id/flat/15857-d1ba2a64bce0795e%40postgresql.org

-- 
Thomas Munro
https://enterprisedb.com