| From: | Chengpeng Yan <chengpeng_yan(at)outlook(dot)com> |
|---|---|
| To: | Richard Guo <guofenglinux(at)gmail(dot)com> |
| Cc: | Pg Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org> |
| Subject: | Re: Simplify the uniqueness proof for self-join elimination |
| Date: | 2026-11-22 07:47:16 |
| Message-ID: | 4A3914FA-A246-43EA-8245-BA3B69D91A63@outlook.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
Hi,
> On Nov 13, 2026, at 17:35, Richard Guo <guofenglinux(at)gmail(dot)com> wrote:
>
> 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
> <v1-0001-Simplify-the-uniqueness-proof-for-self-join-elimi.patch>
Thanks for working on this. I think the patch is worthwhile. As you
described, it:
1. moves the SJE-specific logic out of the shared uniqueness-proof code,
so those functions no longer need to know about SJE and stay focused
on their own job;
2. removes the dependency on index order, which is the kind of plan
instability users can't reason about;
3. allows SJE to remove more self-joins than before.
I've reviewed the patch and didn't find any issues. The change looks
reasonable and valuable to me.
--
Best regards,
Chengpeng Yan
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Stepan Neretin | 2026-11-22 09:16:31 | Re: FATAL: could not send end-of-streaming message to primary: no COPY in progress |
| Previous Message | Tender Wang | 2026-11-22 07:45:48 | Fix stale source values in MERGE RETURNING after a cross-partition update |