Re: Performance improvement for joins where outer side is unique

David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
> On 27 January 2017 at 12:39, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> 2. In these same cases (unique/semi/anti joins), it is possible to avoid
>> mark/restore overhead in a mergejoin, because we can tweak the executor
>> logic to not require backing up the inner side.

> I've made modifications in the attached to add this optimization, and
> it's quite a significant improvement.

Cool ... validates my gut feeling that that was worth incorporating.

>> ... IOW, would it hurt to drop the SpecialJoinInfo
>> tie-in and just rely on the generic cache?

> I agree that special handling of one join type is not so pretty.
> However, LEFT JOINs still remain a bit special as they're the only
> ones we currently perform join removal on, and the patch modifies that
> code to make use of the new flag for those. This can improve planner
> performance of join removal when a join is removed successfully, as
> the previous code had to recheck uniqueness of each remaining LEFT
> JOIN again, whereas the new code only checks uniqueness of ones not
> previously marked as unique. This too likely could be done with the
> cache, although I'm a bit concerned with populating the cache, then
> performing a bunch of LEFT JOIN removals and leaving relids in the
> cache which no longer exist. Perhaps it's OK. I've just not found
> proofs in my head yet that it is.

TBH, I do not like that tie-in at all. I don't believe that it improves
any performance, because if analyzejoins.c detects that the join is
unique, it will remove the join; therefore there is nothing to cache.
(This statement depends on the uniqueness test being the last removability
test, but it is.) And running mark_unique_joins() multiple times is ugly
and adds cycles whenever it cannot prove a join unique, because it'll keep
trying to do so. So I'm pretty inclined to drop the connection to
analyzejoins.c altogether, along with mark_unique_joins(), and just use
the generic positive/negative cache mechanism you added for all join types.

It's possible that it'd make sense for analyzejoins.c to add a negative
cache entry about any join that it tries and fails to prove unique.
Your point about cache maintenance is valid, but a simple answer there
would just be to flush the cache whenever we remove a rel. (Although
I'm dubious that we need to: how could a removable rel be part of the
min outer rels for any surviving rel?)

>> * Because of where we apply the short-circuit logic in the executor,
>> it's only safe to consider the inner rel as unique if it is provably
>> unique using only the join clauses that drive the primary join mechanism
>> (ie, the "joinquals" not the "otherquals"). We already do ignore quals
>> that are pushed-down to an outer join, so that's good, but there's an
>> oversight: we will use a qual that is mergejoinable even if it's not
>> hashjoinable. That means we could get the wrong answers in a hash join.

> hmm. I'm having trouble understanding why this is a problem for Unique
> joins, but not for join removal?

Ah, you know what, that's just mistaken. I was thinking that we
short-circuited the join on the strength of the hash (or merge) quals
only, but actually we check all the joinquals first. As long as the
uniqueness proof uses only joinquals and not conditions that will end up
as otherquals, it's fine.

> However you mentioning this cause me to notice that this is only true
> in the patch for left joins, and the other join types are not
> consistent with that.

Hm, perhaps, but the example you show isn't proving that, because it's
choosing to put a1 on the inside in the innerjoin case, and a1 certainly
isn't unique for this query. We can't see whether a2 was detected as
unique.

regards, tom lane