Re: Tracking per-RelOptInfo uniqueness during planning

From: Richard Guo <guofenglinux(at)gmail(dot)com>
To: Ilia Evdokimov <ilidock95(at)gmail(dot)com>
Cc: Antonin Houska <ah(at)cybertec(dot)at>, Pg Hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>, Andy Fan <zhihuifan1213(at)163(dot)com>, David Rowley <dgrowleyml(at)gmail(dot)com>
Subject: Re: Tracking per-RelOptInfo uniqueness during planning
Date: 2026-11-18 07:00:35
Message-ID: CAMbWs49+HfLzaVP9X+Ltpa7HFOonovhz4PdEWJ=HwP4zwEat5g@mail.gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

(Sorry it took me so long to get back to this work.)

While working through Antonin's review of v4, I became less and less
happy with keeping UniqueKeys on join relations.

The number of keys on a join relation grows quickly, as Antonin
pointed out, because the union of a key from each side is a key of the
join. v4 caps the list at 8, but then which keys survive depends on
the order they are added in. Worse, a join relation's keys are
derived from whichever pair of input relations that the join search
tries first, and a different pair can give different keys. And we
build all these keys for every join relation in every query, though
most of them are ever looked at.

I've been trying a new idea on this. The idea is that we keep
UniqueKeys for base relations only. For a join relation, we work out
whether it is distinct for a given set of ECs at the time the question
is asked. If some base relation in the join has a UniqueKey within
that set, only one of its rows is possible, so the ECs of all its
columns can be added to the set, which may in turn cover a key of
another relation. We repeat that until every base relation is
accounted for or we get stuck. For example, in

SELECT * FROM a LEFT JOIN (b JOIN c ON b.x = c.id) ON a.x = b.id;

with unique indexes on b.id and c.id, the clause "a.x = b.id" fixes
b.id, that leaves one row of b, which fixes b.x and so c.id, and that
leaves one row of c. So the join of b and c is unique for a.

There is nothing to cap, the answer doesn't depend on the join order,
and a query that never asks pays nothing. The loop is just bitmapset
operations on the keys of the base relations, so it should be cheap.

I've split the implementation into small steps. Attached are the
first three I've got so far.

0001 detects unique inner sides of joins when the inner side is a
join, for plain tables and inner joins only.

0002 skips DISTINCT and GROUP BY steps whose input is already
distinct. A UniqueKey is marked null_aware if it also holds with
NULLs considered equal.

0003 skips a DISTINCT step that follows grouping or window functions.

There is still a lot of work to do, including outer joins, semi/anti
joins, child relations, partially aggregated relations and subqueries.
But I'd like to hear what people think of the approach first.

- Richard

Attachment Content-Type Size
v5-0001-Detect-unique-inner-sides-of-joins-when-the-inner.patch application/octet-stream 38.1 KB
v5-0002-Skip-DISTINCT-and-GROUP-BY-steps-when-the-input-i.patch application/octet-stream 43.8 KB
v5-0003-Skip-DISTINCT-steps-over-grouped-or-windowed-inpu.patch application/octet-stream 14.8 KB

In response to

Browse pgsql-hackers by date

  From Date Subject
Next Message Chao Li 2026-11-18 07:06:57 Re: [PATCH v1] Avoid deforming unused trailing columns in COPY TO
Previous Message Aleksander Alekseev 2026-11-18 07:00:28 Re: Validate GIN posting lists before decoding them