Simplify the uniqueness proof for self-join elimination

From: Richard Guo <guofenglinux(at)gmail(dot)com>
To: Pg Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
Subject: Simplify the uniqueness proof for self-join elimination
Date: 2026-11-13 09:35:21
Message-ID: CAMbWs4_nGbOX63mP351Zfu3fue86fqfp5yxvVeTeULTDsY35Uw@mail.gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

While working on the UniqueKeys stuff, I noticed that the self-join
elimination code puts its uniqueness proof logic into several places
that are also used by other parts of the planner. This makes the
UniqueKeys work harder than it should be, because I have to take care
of SJE-specific things in places that are not related to SJE at all.

To remove a self-join, SJE needs to prove that each row of the removed
relation can only match its own row in the kept relation. Currently
it passes the self-join quals and all the restriction clauses of the
kept relation to innerrel_is_unique(), and lets
relation_has_unique_index_for() report back which restriction clauses
it used. Then it checks that the removed relation also has these
clauses. For this, an extra_clauses output parameter is added to
innerrel_is_unique(), is_innerrel_unique_for(), rel_is_distinct_for()
and relation_has_unique_index_for(). Also the UniqueRelInfo cache
entries have self_join and extra_clauses fields, and the cache lookups
need to handle them specially. IMHO it doesn't seem like a good
design to scatter SJE-specific logic across these functions in such an
ad hoc way.

Another problem is that the result depends on the order of the
indexes. This is the kind of plan instability users can't reason
about. relation_has_unique_index_for() stops at the first unique
index that it can prove, and if this index uses a restriction clause
that only the kept relation has, SJE just gives up, even if another
index could work. For example, with the table sj (a int unique, b
int, c int unique) from join.sql, and a unique index on (a, b, c), for
the query below

SELECT * FROM sj j1, sj j2
WHERE j1.b = j2.b AND j1.c = 3 AND j2.a = 2 AND j2.c = 3;

the join is not removed. This is because the index on (a, b, c) is
tried first, and it needs j2.a = 2, which j1 does not have. However,
the unique index on c together with the shared restriction c = 3 is
enough to remove the join.

So I'd like to propose the attached patch. With this patch, SJE first
finds out the restriction clauses that both relations have, and then
calls relation_has_unique_index_for() directly with the self-join
quals and these shared clauses. Since SJE does not go through
innerrel_is_unique() any more, we can remove the extra_clauses
parameters as well as all the code around that. Also, unique_for_rels
can be a plain list of Relids again, so we can remove UniqueRelInfo
structure and all the special handling around it.

One might worry that SJE does not use the cache any more. But within
SJE, the cached entries never get hit, because each pair of relations
is checked only once, and if anything is removed, we restart and
rebuild all the RelOptInfos, which discards every cache entry. The
only benefit of the SJE cache might be that join search may reuse the
entries from the *final* SJE pass, which only happens when a table is
joined to itself, and at the cost of at most one extra
relation_has_unique_index_for() call. I think this is fine, as it is
very cheap compared to the rest of planning. OTOH, because now more
self-joins can be removed, we actually can save a lot of planning
time, since join search has fewer relations to deal with.

The patch also removes the requirement that the two relations must
have a join clause between them. The shared restriction clauses alone
can prove that the join is removable, such as "WHERE j1.a = 2 AND j2.a
= 2" with a unique index on a. This enables us to remove even more
self-joins than before.

(This is a master-only patch.)

Any thoughts?

- Richard

Attachment Content-Type Size
v1-0001-Simplify-the-uniqueness-proof-for-self-join-elimi.patch application/octet-stream 23.6 KB

Browse pgsql-hackers by date

  From Date Subject
Next Message Peter Eisentraut 2026-11-13 09:36:29 Re: -Wcast-qual home stretch
Previous Message Amit Kapila 2026-11-13 09:32:53 Re: DOCS - CREATE PUBLICATION wording re 'ONLY' for partitioned tables.