public inbox for [email protected]
help / color / mirror / Atom feedKey joins
26+ messages / 6 participants
[nested] [flat]
* Key joins
@ 2026-05-28 18:47 Joel Jacobson <[email protected]>
0 siblings, 3 replies; 26+ messages in thread
From: Joel Jacobson @ 2026-05-28 18:47 UTC (permalink / raw)
To: pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
Hi hackers,
This patch implements a new SQL language feature, that we intent to
submit as a Change Proposal to the WG 3 SQL committee for the next
meeting in Stockholm in June. We would greatly appreciate any feedback
from the community.
Key Joins
---------
Mathematically, CROSS JOINs are a cartesian product, INNER JOINs a
subset of it, and OUTER JOINs potentially null-extend that subset. In
practice, however, most joins look up additional information along a
foreign key rather than resembling a cartesian product.
Today a written query does not convey whether a particular JOIN simply
enriches the referencing side, filters it, or fans it out:
-- both sums silently inflated by the fan-out
SELECT o.id, SUM(oi.amount), SUM(p.amount)
FROM orders o
LEFT JOIN order_items oi ON oi.order_id = o.id
LEFT JOIN payments p ON p.order_id = o.id
GROUP BY o.id;
The above example is based on a pgsql-generals thread [1].
We propose a new JOIN syntax that makes it easy to determine locally
that the immediate join result, before any further steps, just enriches
the referencing side with information from the referenced side, with
null-extension for OUTER JOINs. It conveys the author's intent, makes
the referencing side visually clear, and is enforced at compile time
against the schema. If we can't prove it, the user gets a compile-time
error.
Under FOR KEY the same query will not compile:
SELECT o.id, SUM(oi.amount), SUM(p.amount)
FROM orders o
LEFT JOIN order_items oi FOR KEY (order_id) -> o (id)
LEFT JOIN payments p FOR KEY (order_id) -> o (id)
GROUP BY o.id;
ERROR: key join from referencing relation p to referenced relation o cannot be proven
LINE 7: LEFT JOIN payments AS p FOR KEY (order_id) -> o (id)
^
DETAIL: Referenced columns o (id) are not proven unique. A preceding join may duplicate rows from referenced relation o.
Web demo
--------
The attached Discussion paper has also been published at https://keyjoin.org
with all examples in the paper runnable in the browser using a patched PGLite.
Patches
-------
0001
The first patch is an attempt to fix a problem discussed in thread [2], where
DROP FUNCTION can cause issues with concurrent dependency lookups. For key
joins, this issue also extends to ALTER FUNCTION.
The patch prevents stored expressions from depending on stale function
OIDs by locking referenced procedures before recording dependencies, and
by making CREATE OR REPLACE FUNCTION and ALTER FUNCTION take conflicting
locks before changing pg_proc.
0002
The second patch implements the FOR KEY join feature. As this is a
first prototype, there are definitively things that needs to be
improved. For example, we would love feedback on our the revalidation
logic and our dependency tracking approach, that adds a new deptype for
purpose of tracking the proof facts. Another problem we didn't find a
perfect solution to, was our need to expand views during parse for proof
checking and finding constraints.
The logics to compute the facts needed by the proof checker are kind of
complex, which is partially due to the ambition to not introduce
overhead to queries not using the new feature.
The patch comes with a massive test suite, that we understand will need
to be trimmed down to have a chance to be committable.
0003
The third patch adds information_schema.view_constraint_usage, that
shows what constraints a view depend on, due to usage of key joins in
the view's query. This is also part of the proposal.
Joel Jacobson
Vik Fearing
Andreas Karlsson
Arne Roland
Anders Granlund
[1] [Avoiding double-counting in aggregates with more than one join?]
(https://www.postgresql.org/message-id/flat/86b9ec78-925c-1935-bc9d-6bad4ceb1f40@illuminatedcomputing...)
[2] [RE: Parallel INSERT SELECT take 2]
(https://www.postgresql.org/message-id/TY4PR01MB17718A4DE63020A9EA5E9CB6594382%40TY4PR01MB17718.jpnpr...)
Attachments:
[application/x-gzip] v1-0003-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/2-v1-0003-Add-information_schema.view_constraint_usage.patch.gz)
download
[application/x-gzip] v1-0002-Implement-FOR-KEY-join-support.patch.gz (171.3K, ../../[email protected]/3-v1-0002-Implement-FOR-KEY-join-support.patch.gz)
download
[application/x-gzip] v1-0001-Lock-procedures-before-recording-dependencies.patch.gz (3.3K, ../../[email protected]/4-v1-0001-Lock-procedures-before-recording-dependencies.patch.gz)
download
[application/pdf] key_joins.pdf (208.6K, ../../[email protected]/5-key_joins.pdf)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-05-28 22:13 Joel Jacobson <[email protected]>
parent: Joel Jacobson <[email protected]>
2 siblings, 1 reply; 26+ messages in thread
From: Joel Jacobson @ 2026-05-28 22:13 UTC (permalink / raw)
To: pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Thu, May 28, 2026, at 20:47, Joel Jacobson wrote:
> Hi hackers,
>
> This patch implements a new SQL language feature, that we intent to
> submit as a Change Proposal to the WG 3 SQL committee for the next
> meeting in Stockholm in June. We would greatly appreciate any feedback
> from the community.
>
> Key Joins
> ---------
>
> Mathematically, CROSS JOINs are a cartesian product, INNER JOINs a
> subset of it, and OUTER JOINs potentially null-extend that subset. In
> practice, however, most joins look up additional information along a
> foreign key rather than resembling a cartesian product.
>
> Today a written query does not convey whether a particular JOIN simply
> enriches the referencing side, filters it, or fans it out:
>
> -- both sums silently inflated by the fan-out
> SELECT o.id, SUM(oi.amount), SUM(p.amount)
> FROM orders o
> LEFT JOIN order_items oi ON oi.order_id = o.id
> LEFT JOIN payments p ON p.order_id = o.id
> GROUP BY o.id;
>
> The above example is based on a pgsql-generals thread [1].
>
> We propose a new JOIN syntax that makes it easy to determine locally
> that the immediate join result, before any further steps, just enriches
> the referencing side with information from the referenced side, with
> null-extension for OUTER JOINs. It conveys the author's intent, makes
> the referencing side visually clear, and is enforced at compile time
> against the schema. If we can't prove it, the user gets a compile-time
> error.
>
> Under FOR KEY the same query will not compile:
>
> SELECT o.id, SUM(oi.amount), SUM(p.amount)
> FROM orders o
> LEFT JOIN order_items oi FOR KEY (order_id) -> o (id)
> LEFT JOIN payments p FOR KEY (order_id) -> o (id)
> GROUP BY o.id;
>
> ERROR: key join from referencing relation p to referenced relation o
> cannot be proven
> LINE 7: LEFT JOIN payments AS p FOR KEY (order_id) -> o (id)
> ^
> DETAIL: Referenced columns o (id) are not proven unique. A preceding
> join may duplicate rows from referenced relation o.
>
> Web demo
> --------
>
> The attached Discussion paper has also been published at https://keyjoin.org
> with all examples in the paper runnable in the browser using a patched PGLite.
>
> Patches
> -------
>
> 0001
> The first patch is an attempt to fix a problem discussed in thread [2], where
> DROP FUNCTION can cause issues with concurrent dependency lookups. For key
> joins, this issue also extends to ALTER FUNCTION.
>
> The patch prevents stored expressions from depending on stale function
> OIDs by locking referenced procedures before recording dependencies, and
> by making CREATE OR REPLACE FUNCTION and ALTER FUNCTION take conflicting
> locks before changing pg_proc.
>
> 0002
> The second patch implements the FOR KEY join feature. As this is a
> first prototype, there are definitively things that needs to be
> improved. For example, we would love feedback on our the revalidation
> logic and our dependency tracking approach, that adds a new deptype for
> purpose of tracking the proof facts. Another problem we didn't find a
> perfect solution to, was our need to expand views during parse for proof
> checking and finding constraints.
>
> The logics to compute the facts needed by the proof checker are kind of
> complex, which is partially due to the ambition to not introduce
> overhead to queries not using the new feature.
>
> The patch comes with a massive test suite, that we understand will need
> to be trimmed down to have a chance to be committable.
>
> 0003
> The third patch adds information_schema.view_constraint_usage, that
> shows what constraints a view depend on, due to usage of key joins in
> the view's query. This is also part of the proposal.
>
> Joel Jacobson
> Vik Fearing
> Andreas Karlsson
> Arne Roland
> Anders Granlund
>
> [1] [Avoiding double-counting in aggregates with more than one join?]
> (https://www.postgresql.org/message-id/flat/86b9ec78-925c-1935-bc9d-6bad4ceb1f40@illuminatedcomputing...)
> [2] [RE: Parallel INSERT SELECT take 2]
> (https://www.postgresql.org/message-id/TY4PR01MB17718A4DE63020A9EA5E9CB6594382%40TY4PR01MB17718.jpnpr...)
I noticed cfbot was red; I see I forgot to include these files in patch 0002:
src/test/modules/injection_points/expected/key_join_proof_race_record_proc_dep.out
src/test/modules/injection_points/specs/key_join_proof_race_record_proc_dep.spec
Fixed in new version attached.
/Joel
Attachments:
[application/x-gzip] v2-0003-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/2-v2-0003-Add-information_schema.view_constraint_usage.patch.gz)
download
[application/x-gzip] v2-0002-Implement-FOR-KEY-join-support.patch.gz (171.8K, ../../[email protected]/3-v2-0002-Implement-FOR-KEY-join-support.patch.gz)
download
[application/x-gzip] v2-0001-Lock-procedures-before-recording-dependencies.patch.gz (3.3K, ../../[email protected]/4-v2-0001-Lock-procedures-before-recording-dependencies.patch.gz)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-05-29 05:08 Joel Jacobson <[email protected]>
parent: Joel Jacobson <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Joel Jacobson @ 2026-05-29 05:08 UTC (permalink / raw)
To: pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Fri, May 29, 2026, at 00:13, Joel Jacobson wrote:
> On Thu, May 28, 2026, at 20:47, Joel Jacobson wrote:
>> Hi hackers,
>>
>> This patch implements a new SQL language feature, that we intent to
>> submit as a Change Proposal to the WG 3 SQL committee for the next
>> meeting in Stockholm in June. We would greatly appreciate any feedback
>> from the community.
...
>> The attached Discussion paper has also been published at https://keyjoin.org
>> with all examples in the paper runnable in the browser using a patched PGLite.
v3 is mostly a rebase over recent master changes.
0001: Serialize routine definition changes with dependency recording
0002: Implement FOR KEY join support
0003: Add information_schema.view_constraint_usage
Changes from v2:
* 0001 was reworked after 2fbb211 added generic dependency locking to
master. The patch now only keeps CREATE OR REPLACE FUNCTION /
ALTER FUNCTION serialization with dependency recording. This also
matches the wording change from e2b3573.
* 0002 race tests now expect the generic dependency-locking error path,
handle stale dependency lookups during proof revalidation, and avoid
timing-dependent deadlock/injection-point output in the function and
operator prelock tests.
* cfbot showed the ICU-dependent nondeterministic-collation tests in v2
failed when such collations were unavailable. Moved to a separate guarded
key_join_icu test.
* 0003 is unchanged.
/Joel
Attachments:
[application/x-gzip] v3-0003-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/2-v3-0003-Add-information_schema.view_constraint_usage.patch.gz)
download
[application/x-gzip] v3-0002-Implement-FOR-KEY-join-support.patch.gz (175.0K, ../../[email protected]/3-v3-0002-Implement-FOR-KEY-join-support.patch.gz)
download
[application/x-gzip] v3-0001-Serialize-routine-definition-changes-with-depende.patch.gz (1.9K, ../../[email protected]/4-v3-0001-Serialize-routine-definition-changes-with-depende.patch.gz)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-05-29 07:45 Joel Jacobson <[email protected]>
parent: Joel Jacobson <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Joel Jacobson @ 2026-05-29 07:45 UTC (permalink / raw)
To: pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Fri, May 29, 2026, at 07:08, Joel Jacobson wrote:
> On Fri, May 29, 2026, at 00:13, Joel Jacobson wrote:
>> On Thu, May 28, 2026, at 20:47, Joel Jacobson wrote:
>>> Hi hackers,
>>>
>>> This patch implements a new SQL language feature, that we intent to
>>> submit as a Change Proposal to the WG 3 SQL committee for the next
>>> meeting in Stockholm in June. We would greatly appreciate any feedback
>>> from the community.
> ...
>>> The attached Discussion paper has also been published at https://keyjoin.org
>>> with all examples in the paper runnable in the browser using a patched PGLite.
v4 is a small follow-up to fix a non-cassert build failure,
reported by cfbot on NetBSD/FreeBSD animals:
* 0002 removes assertion-only local variables in parse_key_join.c
that triggered -Werror=unused-but-set-variable.
* 0001 and 0003 are unchanged from v3.
/Joel
Attachments:
[application/x-gzip] v4-0003-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/2-v4-0003-Add-information_schema.view_constraint_usage.patch.gz)
download
[application/x-gzip] v4-0002-Implement-FOR-KEY-join-support.patch.gz (175.0K, ../../[email protected]/3-v4-0002-Implement-FOR-KEY-join-support.patch.gz)
download
[application/x-gzip] v4-0001-Serialize-routine-definition-changes-with-depende.patch.gz (1.9K, ../../[email protected]/4-v4-0001-Serialize-routine-definition-changes-with-depende.patch.gz)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-05-29 08:54 Joel Jacobson <[email protected]>
parent: Joel Jacobson <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Joel Jacobson @ 2026-05-29 08:54 UTC (permalink / raw)
To: pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Fri, May 29, 2026, at 09:45, Joel Jacobson wrote:
> On Fri, May 29, 2026, at 07:08, Joel Jacobson wrote:
>> On Fri, May 29, 2026, at 00:13, Joel Jacobson wrote:
>>> On Thu, May 28, 2026, at 20:47, Joel Jacobson wrote:
>>>> Hi hackers,
>>>>
>>>> This patch implements a new SQL language feature, that we intent to
>>>> submit as a Change Proposal to the WG 3 SQL committee for the next
>>>> meeting in Stockholm in June. We would greatly appreciate any feedback
>>>> from the community.
>> ...
>>>> The attached Discussion paper has also been published at https://keyjoin.org
>>>> with all examples in the paper runnable in the browser using a patched PGLite.
v5 is another small follow-up to fix a cfbot regression-test warning:
* 0002 renames the roles created by key_join.sql to use the required
regress_ prefix, so builds with ENFORCE_REGRESSION_TEST_NAME_RESTRICTIONS
do not emit warnings.
* 0001 and 0003 are unchanged from v4.
/Joel
Attachments:
[application/x-gzip] v5-0003-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/2-v5-0003-Add-information_schema.view_constraint_usage.patch.gz)
download
[application/x-gzip] v5-0002-Implement-FOR-KEY-join-support.patch.gz (175.0K, ../../[email protected]/3-v5-0002-Implement-FOR-KEY-join-support.patch.gz)
download
[application/x-gzip] v5-0001-Serialize-routine-definition-changes-with-depende.patch.gz (1.9K, ../../[email protected]/4-v5-0001-Serialize-routine-definition-changes-with-depende.patch.gz)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-05-29 10:50 Joel Jacobson <[email protected]>
parent: Joel Jacobson <[email protected]>
0 siblings, 0 replies; 26+ messages in thread
From: Joel Jacobson @ 2026-05-29 10:50 UTC (permalink / raw)
To: pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Fri, May 29, 2026, at 10:54, Joel Jacobson wrote:
> On Fri, May 29, 2026, at 09:45, Joel Jacobson wrote:
>> On Fri, May 29, 2026, at 07:08, Joel Jacobson wrote:
>>> On Fri, May 29, 2026, at 00:13, Joel Jacobson wrote:
>>>> On Thu, May 28, 2026, at 20:47, Joel Jacobson wrote:
>>>>> Hi hackers,
>>>>>
>>>>> This patch implements a new SQL language feature, that we intent to
>>>>> submit as a Change Proposal to the WG 3 SQL committee for the next
>>>>> meeting in Stockholm in June. We would greatly appreciate any feedback
>>>>> from the community.
>>> ...
>>>>> The attached Discussion paper has also been published at https://keyjoin.org
>>>>> with all examples in the paper runnable in the browser using a patched PGLite.
v6 fixes a cfbot failure in an injection_points isolation test:
* 0002 stabilizes the expected completion order in two key-join deadlock
tests using isolationtester permutation markers, instead of relying on
scheduler-dependent output order.
* 0001 and 0003 are unchanged from v5.
/Joel
Attachments:
[application/x-gzip] v6-0003-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/2-v6-0003-Add-information_schema.view_constraint_usage.patch.gz)
download
[application/x-gzip] v6-0002-Implement-FOR-KEY-join-support.patch.gz (175.0K, ../../[email protected]/3-v6-0002-Implement-FOR-KEY-join-support.patch.gz)
download
[application/x-gzip] v6-0001-Serialize-routine-definition-changes-with-depende.patch.gz (1.9K, ../../[email protected]/4-v6-0001-Serialize-routine-definition-changes-with-depende.patch.gz)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-05-29 12:04 Matthias van de Meent <[email protected]>
parent: Joel Jacobson <[email protected]>
2 siblings, 0 replies; 26+ messages in thread
From: Matthias van de Meent @ 2026-05-29 12:04 UTC (permalink / raw)
To: Joel Jacobson <[email protected]>; +Cc: pgsql-hackers; Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Thu, 28 May 2026 at 20:48, Joel Jacobson <[email protected]> wrote:
>
> Hi hackers,
>
> This patch implements a new SQL language feature, that we intent to
> submit as a Change Proposal to the WG 3 SQL committee for the next
> meeting in Stockholm in June. We would greatly appreciate any feedback
> from the community.
>
> Web demo
> --------
>
> The attached Discussion paper has also been published at https://keyjoin.org
> with all examples in the paper runnable in the browser using a patched PGLite.
Re: "8.4 Why Column Lists Instead of Constraint Names" [0]
It's mentioned that the use of named foreign key constraints as key
column list definitions is not part of the proposal because they are
not universally applicable. While I do understand that for some cases
(multiple mentions of the same target table, CTEs, subqueries, ...)
there won't be a (uniquely) named constraint to reference, in many
(possibly most) cases the FK constraint name _will_ uniquely identify
the base table pair to join, and I think that using the FK name should
be supported as a major QoL addition in this proposal.
Note that the FOR KEY (cols) -> alias (cols) is still useful for the
reasons why constraint names can't always be used, but it's probably
not something I'd ever try to use unless I really, really needed the
specific guarantees granted by the new processing while I was writing
the query. `FOR KEY (something) -> something (something)` just doesn't
feel natural to me.
Kind regards,
Matthias van de Meent
Databricks (https://www.databricks.com)
[0]: https://keyjoin.org/#sec8.4
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-05-29 12:51 Laurenz Albe <[email protected]>
parent: Joel Jacobson <[email protected]>
2 siblings, 1 reply; 26+ messages in thread
From: Laurenz Albe @ 2026-05-29 12:51 UTC (permalink / raw)
To: Joel Jacobson <[email protected]>; pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Thu, 2026-05-28 at 20:47 +0200, Joel Jacobson wrote:
> This patch implements a new SQL language feature, that we intent to
> submit as a Change Proposal to the WG 3 SQL committee for the next
> meeting in Stockholm in June. We would greatly appreciate any feedback
> from the community.
Your presentation at the pgconf.dev really convinced me that this is
a useful feature.
I had only one consideration:
> FROM orders o
> LEFT JOIN order_items oi FOR KEY (order_id) -> o (id)
In the spirit of looking more like SQL, how about replacing the
arrows with FROM and TO?
Either
a JOIN b FOR KEY (col1) TO (col2)
or, slightly more verbose and natural language-like:
a JOIN b FOR KEY FROM (col1) TO (col2)
And if the arrow points the other way,
a JOIN b FOR KEY (col1) FROM (col2)
or
a JOIN b FOR KEY TO (col1) FROM (col2)
Yours,
Laurenz Albe
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-05-29 13:21 Joel Jacobson <[email protected]>
parent: Laurenz Albe <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Joel Jacobson @ 2026-05-29 13:21 UTC (permalink / raw)
To: Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Fri, May 29, 2026, at 14:51, Laurenz Albe wrote:
> On Thu, 2026-05-28 at 20:47 +0200, Joel Jacobson wrote:
>> This patch implements a new SQL language feature, that we intent to
>> submit as a Change Proposal to the WG 3 SQL committee for the next
>> meeting in Stockholm in June. We would greatly appreciate any feedback
>> from the community.
>
> Your presentation at the pgconf.dev really convinced me that this is
> a useful feature.
Thanks for the opportunity of presenting.
> I had only one consideration:
>
>> FROM orders o
>> LEFT JOIN order_items oi FOR KEY (order_id) -> o (id)
>
> In the spirit of looking more like SQL, how about replacing the
> arrows with FROM and TO?
>
> Either
>
> a JOIN b FOR KEY (col1) TO (col2)
>
> or, slightly more verbose and natural language-like:
>
> a JOIN b FOR KEY FROM (col1) TO (col2)
>
> And if the arrow points the other way,
>
> a JOIN b FOR KEY (col1) FROM (col2)
>
> or
>
> a JOIN b FOR KEY TO (col1) FROM (col2)
We actually originally considered TO and FROM as keywords for indicating
direction, but FROM in a join clause causes confusion with the FROM
clause itself. Our user discussions over the last three years indicates
that arrows are clearer and less ambiguous.
It's also worth to mention that SQL/PGQ also uses ASCII arrows to
indicate direction for its graph pattern syntax [1].
[1] https://peter.eisentraut.org/blog/2023/04/04/sql-2023-is-finished-here-is-whats-new
/Joel
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-05-29 16:20 Laurenz Albe <[email protected]>
parent: Joel Jacobson <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Laurenz Albe @ 2026-05-29 16:20 UTC (permalink / raw)
To: Joel Jacobson <[email protected]>; pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Fri, 2026-05-29 at 15:21 +0200, Joel Jacobson wrote:
> In the spirit of looking more like SQL, how about replacing the
> > arrows with FROM and TO?
>
> We actually originally considered TO and FROM as keywords for indicating
> direction, but FROM in a join clause causes confusion with the FROM
> clause itself. Our user discussions over the last three years indicates
> that arrows are clearer and less ambiguous.
>
> It's also worth to mention that SQL/PGQ also uses ASCII arrows to
> indicate direction for its graph pattern syntax.
I understand the problem with FROM, and I have no objection to the
arrows.
Yours,
Laurenz Albe
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-05-31 08:05 Joel Jacobson <[email protected]>
parent: Laurenz Albe <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Joel Jacobson @ 2026-05-31 08:05 UTC (permalink / raw)
To: Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Fri, May 29, 2026, at 18:20, Laurenz Albe wrote:
> On Fri, 2026-05-29 at 15:21 +0200, Joel Jacobson wrote:
>> We actually originally considered TO and FROM as keywords for indicating
>> direction, but FROM in a join clause causes confusion with the FROM
>> clause itself. Our user discussions over the last three years indicates
>> that arrows are clearer and less ambiguous.
>>
>> It's also worth to mention that SQL/PGQ also uses ASCII arrows to
>> indicate direction for its graph pattern syntax.
>
> I understand the problem with FROM, and I have no objection to the
> arrows.
Thanks for reviewing.
v7 updates 0002 to match the revised Change Proposal wording for
GROUPING SETS/ROLLUP/CUBE:
* Row-coverage facts can now pass through GROUPING SETS, ROLLUP, and
CUBE when one expanded grouping set contains all key columns under the
same key identity. This is less conservative than v6: subtotal rows
with NULLs in omitted grouping columns do not invalidate row coverage,
since row coverage is about containment of all-non-null key values.
* Uniqueness and not-null handling for grouping sets remain conservative.
GROUPING SETS/ROLLUP/CUBE do not by themselves prove referenced
uniqueness or not-nullness; a following DISTINCT or simple GROUP BY can
still provide uniqueness where needed.
* 0001 and 0003 are unchanged from v6.
/Joel
Attachments:
[application/x-gzip] v7-0001-Serialize-routine-definition-changes-with-depende.patch.gz (1.9K, ../../[email protected]/2-v7-0001-Serialize-routine-definition-changes-with-depende.patch.gz)
download
[application/x-gzip] v7-0002-Implement-FOR-KEY-join-support.patch.gz (178.1K, ../../[email protected]/3-v7-0002-Implement-FOR-KEY-join-support.patch.gz)
download
[application/x-gzip] v7-0003-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/4-v7-0003-Add-information_schema.view_constraint_usage.patch.gz)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-05-31 14:40 Joel Jacobson <[email protected]>
parent: Joel Jacobson <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Joel Jacobson @ 2026-05-31 14:40 UTC (permalink / raw)
To: Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Sun, May 31, 2026, at 10:05, Joel Jacobson wrote:
> On Fri, May 29, 2026, at 18:20, Laurenz Albe wrote:
>> On Fri, 2026-05-29 at 15:21 +0200, Joel Jacobson wrote:
>>> We actually originally considered TO and FROM as keywords for indicating
>>> direction, but FROM in a join clause causes confusion with the FROM
>>> clause itself. Our user discussions over the last three years indicates
>>> that arrows are clearer and less ambiguous.
>>>
>>> It's also worth to mention that SQL/PGQ also uses ASCII arrows to
>>> indicate direction for its graph pattern syntax.
>>
>> I understand the problem with FROM, and I have no objection to the
>> arrows.
>
> Thanks for reviewing.
>
> v7 updates 0002 to match the revised Change Proposal wording for
> GROUPING SETS/ROLLUP/CUBE:
v8 fixes another nondeterministic isolation-test ordering issue seen by
cfbot on the FreeBSD machine.
0001 and 0003 are unchanged from v7.
/Joel
Attachments:
[application/x-gzip] v8-0001-Serialize-routine-definition-changes-with-depende.patch.gz (1.9K, ../../[email protected]/2-v8-0001-Serialize-routine-definition-changes-with-depende.patch.gz)
download
[application/x-gzip] v8-0002-Implement-FOR-KEY-join-support.patch.gz (178.1K, ../../[email protected]/3-v8-0002-Implement-FOR-KEY-join-support.patch.gz)
download
[application/x-gzip] v8-0003-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/4-v8-0003-Add-information_schema.view_constraint_usage.patch.gz)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-01 20:06 Joel Jacobson <[email protected]>
parent: Joel Jacobson <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Joel Jacobson @ 2026-06-01 20:06 UTC (permalink / raw)
To: Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Sun, May 31, 2026, at 16:40, Joel Jacobson wrote:
> On Sun, May 31, 2026, at 10:05, Joel Jacobson wrote:
>> On Fri, May 29, 2026, at 18:20, Laurenz Albe wrote:
>>> On Fri, 2026-05-29 at 15:21 +0200, Joel Jacobson wrote:
>>>> We actually originally considered TO and FROM as keywords for indicating
>>>> direction, but FROM in a join clause causes confusion with the FROM
>>>> clause itself. Our user discussions over the last three years indicates
>>>> that arrows are clearer and less ambiguous.
>>>>
>>>> It's also worth to mention that SQL/PGQ also uses ASCII arrows to
>>>> indicate direction for its graph pattern syntax.
>>>
>>> I understand the problem with FROM, and I have no objection to the
>>> arrows.
>>
>> Thanks for reviewing.
>>
>> v7 updates 0002 to match the revised Change Proposal wording for
>> GROUPING SETS/ROLLUP/CUBE:
>
> v8 fixes another nondeterministic isolation-test ordering issue seen by
> cfbot on the FreeBSD machine.
>
> 0001 and 0003 are unchanged from v7.
I noted a small error in 7.4.13 in the paper. The examples incorrectly
used "LEFT JOIN" instead of "JOIN", which made the claim "Both queries,
if accepted, would produce the same result rows" to not hold true.
Fixed subsection below:
===
7.4.13 Filtered Views and the PK Side
A key join through a filtered view on the PK side is rejected unless the
FK side supplies matching direct key-equality filter evidence; see
Section 7.3.2. This differs from a query that filters the base table
with a WHERE clause after the join:
For the examples below, assume orders has a NOT NULL customer_id that
references customers (id).
-- Accepted: join the full base table, then filter the result.
SELECT *
FROM orders AS o
JOIN customers AS c FOR KEY (id) <- o (customer_id)
WHERE c.active;
CREATE VIEW active_customers AS
SELECT * FROM customers WHERE active;
-- Rejected: the view is the PK side and lacks row coverage.
SELECT *
FROM orders AS o
JOIN active_customers AS ac FOR KEY (id) <- o (customer_id);
ERROR: key join from referencing relation o to referenced relation ac cannot be proven
ERROR: key join from referencing relation o to referenced relation ac cannot be proven
LINE 3: JOIN active_customers AS ac FOR KEY (id) <- o (customer_id);
^
DETAIL: Not every o (customer_id) value can be proven to have a matching ac row. Referenced relation ac is filtered before this key join. The relevant operation occurs inside view public.active_customers.
Both queries, if accepted, would produce the same result rows, but would
differ from the key join's perspective. In the first query, the join is
against the full customers table: every order is guaranteed to find its
matching customer, and the WHERE clause filters the result after the
join has been evaluated. In the second query, active_customers is the PK
side, and it is missing inactive customers. An order that references an
inactive customer will not find a match.
This asymmetry is inherent in row coverage. A key join guarantees that
the join will behave as a proper foreign key traversal, producing
exactly one match for each FK row. A filtered PK side breaks this
guarantee unless the missing PK values are matched by filters that
remove the corresponding FK rows before the join.
===
/Joel
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-01 20:36 Joel Jacobson <[email protected]>
parent: Joel Jacobson <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Joel Jacobson @ 2026-06-01 20:36 UTC (permalink / raw)
To: Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Mon, Jun 1, 2026, at 22:06, Joel Jacobson wrote:
> -- Rejected: the view is the PK side and lacks row coverage.
> SELECT *
> FROM orders AS o
> JOIN active_customers AS ac FOR KEY (id) <- o (customer_id);
> ERROR: key join from referencing relation o to referenced relation ac
> cannot be proven
> ERROR: key join from referencing relation o to referenced relation ac
> cannot be proven
> LINE 3: JOIN active_customers AS ac FOR KEY (id) <- o (customer_id);
> ^
> DETAIL: Not every o (customer_id) value can be proven to have a
> matching ac row. Referenced relation ac is filtered before this key
> join. The relevant operation occurs inside view public.active_customers.
Ops, that extra ERROR: line was a mistake, sorry about that.
The corresponding subsection has now also been fixed in the web version:
https://keyjoin.org/#sec7.4.13
/Joel
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-04 16:02 Joel Jacobson <[email protected]>
parent: Joel Jacobson <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Joel Jacobson @ 2026-06-04 16:02 UTC (permalink / raw)
To: Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Arne Roland <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On Mon, Jun 1, 2026, at 22:36, Joel Jacobson wrote:
> Ops, that extra ERROR: line was a mistake, sorry about that.
>
> The corresponding subsection has now also been fixed in the web version:
> https://keyjoin.org/#sec7.4.13
v9 rebases over Stamp 19beta1 and improves one type of error message in 0002.
The affected queries were already rejected correctly. The change is
only that DETAIL now first reports if there is not even a matching
referential constraint.
0001 and 0003 are unchanged from v8.
/Joel
Attachments:
[application/x-gzip] v9-0003-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/2-v9-0003-Add-information_schema.view_constraint_usage.patch.gz)
download
[application/x-gzip] v9-0002-Implement-FOR-KEY-join-support.patch.gz (178.6K, ../../[email protected]/3-v9-0002-Implement-FOR-KEY-join-support.patch.gz)
download
[application/x-gzip] v9-0001-Serialize-routine-definition-changes-with-depende.patch.gz (1.9K, ../../[email protected]/4-v9-0001-Serialize-routine-definition-changes-with-depende.patch.gz)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-04 22:41 Arne Roland <[email protected]>
parent: Joel Jacobson <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Arne Roland @ 2026-06-04 22:41 UTC (permalink / raw)
To: Joel Jacobson <[email protected]>; Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
Greetings,
the change with the new patch is, that the locking is less excessive.
Foreign key paths unnecessarily blocked concurrent DML. This version of
the patch relaxes the locking to a more balanced degree. In particular
every plainly reading SELECT now takes only an ACCESS SHARE.
Regards
Arne
On 2026-06-04 6:02 PM, Joel Jacobson wrote:
> On Mon, Jun 1, 2026, at 22:36, Joel Jacobson wrote:
>> Ops, that extra ERROR: line was a mistake, sorry about that.
>>
>> The corresponding subsection has now also been fixed in the web version:
>> https://keyjoin.org/#sec7.4.13
> v9 rebases over Stamp 19beta1 and improves one type of error message in 0002.
>
> The affected queries were already rejected correctly. The change is
> only that DETAIL now first reports if there is not even a matching
> referential constraint.
>
> 0001 and 0003 are unchanged from v8.
>
> /Joel
Attachments:
[application/gzip] v10-0003-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/2-v10-0003-Add-information_schema.view_constraint_usage.patch.gz)
download
[application/gzip] v10-0002-Implement-FOR-KEY-join-support.patch.gz (182.5K, ../../[email protected]/3-v10-0002-Implement-FOR-KEY-join-support.patch.gz)
download
[application/gzip] v10-0001-Serialize-routine-definition-changes-with-depend.patch.gz (1.9K, ../../[email protected]/4-v10-0001-Serialize-routine-definition-changes-with-depend.patch.gz)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-11 21:02 Tomas Vondra <[email protected]>
parent: Arne Roland <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Tomas Vondra @ 2026-06-11 21:02 UTC (permalink / raw)
To: Arne Roland <[email protected]>; Joel Jacobson <[email protected]>; Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
Hi,
I took a quick look at the patch over the past couple days. I don't have
a perfect understanding of how it works, but let me share what I have so
far, before I get distracted by other stuff.
I'm interested in this patch because there seems to be a possible
overlap with the overlap with the starjoin planning (in that maybe we
could try reusing some of the derived information for that).
It's a mix of random thoughts, high/low level, important/superficial in
no particular order.
1) It does not compile, ATExecSetRowSecurity seems to be missing
prev_rls or something like that. I simply commented this out, to get it
to compile.
2) fk_referenced_selected in find_key_join_match should be marked as
PG_USED_FOR_ASSERTS_ONLY, to fix compiler warning
3) It'd be helpful if the commit message for 0001 explained why this
change is needed. More clearly than now, I mean. The initial message in
this thread points at another thread as the source of this, but that
thread is huge so how are reviewers expected to find the explanation?
Don't explain just what the commit does, but why it's needed. Say, give
an example of how the old code fails.
4) I think there needs to be a README explaining how the feature works,
i.e. the design and trade offs. Alternatively, it could be explained in
a comment at the beginning of some .c file, but a README seems easier to
find. Without this, reviewers have to piece it from the sgml "user"
docs, and random comments all over the place.
5) It might be helpful if the README defined a couple terms introduced
by the patch, but not really defined anywhere. I mean terms like: join
point, proof, proof graph, fact, surface, "relation visible from". I can
guess what each of these means, but maybe I got it wrong.
Although, I now see "join point" was used in the docs before, so maybe
it's a well-known term?
6) Does it always have to be a "foreign key traversal"? Consider an
example like this:
create table dim (id serial primary key);
create table f (id serial primary key, did int);
select * from f left join dim for key (id) <- f(did);
Currently this fails because of no matching foreign key constraint, but
isn't that pretty much the same thing as if the table actually had the
foreign key (at least considering the cardinality of the join - it won't
change it by adding/removing rows).
I realize that'd contradict the "FOR KEY" part of this patch, but it's
also one of the things that might be beneficial for the starjoin
planning (in that we could maybe extend it to more cases). Although,
maybe we could check those constraints during planning, just like we
check the fkey_list.
7) The patch invents a new "FILTER" clause for joins:
[ FILTER (WHERE join_filter) ]
I understand why it's done - there may be additional join conditions, on
top of the FK equality. But I think it'll be rather confusing. We
already have a "Join Filter", which is used for join clauses that happen
to not be used as "proper" join conditions (e.g. Hash/Merge Cond), and
has to be evaluated "after" the join itself. And now we'd have another
kind of "join filter" ...
Is there a different that'd make this work without the FILTER? For
example, we might encode the "key join" information in the existing ON
(...) clause:
ON (KEY (oi.order_id) -> (o.id) AND ... other clauses ...)
but it seems not as readable. Or maybe just use something else than
"FILTER"? Not sure.
8) I don't understand this change in functioncmds:
/* Routine kind cannot change for an existing pg_proc OID. */
Assert(procForm->prokind != PROKIND_AGGREGATE);
The comment says we can't change OID, but the assert checks it's not an
aggregate functions. Isn't that misleading?
9) DefineView now adjusts the query ID. Why is that needed? Isn't that a
bit weird?
10) checkWellFormedRecursionWalker now recurses, but why is that needed?
11) It's not clear to me why we need p_creating_stored_object, and it's
not explained anywhere. Maybe it's obvious, but not to me.
12) I'm very skeptical anyone can meaningfully review parse_key_join.c.
It's 150KB with ~5200 lines (very dense, with pretty minimal comments).
That's a massive file. The chance of me declaring this committable is
about 0%, simply because I wouldn't believe I understand it.
I think it needs to be broken up into smaller pieces, somehow. I don't
know how, but perhaps it's possible to extract a "minimal feature"
handling some limited subset of cases, and then gradually expand it?
Furthermore, it seems a lot of that file is duplicate with code we
already have elsewhere. For example, couldn't it use a bunch of list
functions instead of writing a local version?
list_contains_equal_node -> list_member
append_dependencies_unique -> list_concat_unique
append_dependency_unique -> list_append_unique
...
There may be more such cases, I haven't looked for them.
13) I think the main question is whether parse-analyze is the right
place to handle this. I don't know. I assume one of the reasons for
doing that is to get an error when defining a view, or when altering an
object - e.g. like when dropping a function used by a view. Which seems
reasonable, people would not like views silently broken by DDL.
But it seems to be this also leads to a lot of code duplication, because
the parse analysis now has to "reimplement" a lot of the stuff already
done in later stages, after parse analyze. For example, we have the
root->fkey_list thing, but that's not available yet.
There's probably more such information - like innerrel_is_unique,
rel_is_distinct_for, relation_has_unique_index_for etc.
Maybe it's not worth it? What if we did this in the planner instead? How
much simpler would it get? My intuition is it'd get much smaller, but
maybe I'm wrong.
It'd probably mean it's not necessary to expand views during parse,
which was one of the problems mentioned at the beginning of this thread.
I suppose we'd need to keep additional information in the plan to know
which joins to check, etc.
14) If we wanted to use some of this for the starjoin planning stuff,
we'd need to propagate more information too, I think. But I'm not sure
about this - we already have the information about foreign keys, so if
key joins are tied to foreign keys, there would not be no new useful
information I suppose.
Plus, I don't want to make that patch dependent on people using new
syntax. If that can give us *additional* information, that would be a
different thing.
15) I'm not sure about using dependencies to store "proofs". Maybe it's
fine, but the existing deptypes are only about DROP behavior - whether
it's OK to drop either side automatically, etc.). But the new deptype
DEPENDENCY_KEYJOIN also carries additional meaning (i.e. it means this
is a proof). I don't see an immediate issue with it, though.
16) I was wondering what performance impact this has, roughly. So I
created a simple 4-way join with fact + 3 dimensions:
create table dim1 (id serial primary key, val text);
create table dim2 (id serial primary key, val text);
create table dim3 (id serial primary key, val text);
create table f (id serial primary key,
d1 int not null references dim1(id),
d2 int not null references dim2(id),
d3 int not null references dim3(id));
and then measured throughput with 2 queries
select * from f
join dim1 on (dim1.id = d1)
join dim2 on (dim2.id = d2)
join dim3 on (dim3.id = d3);
select * from f
join dim1 for key (id) <- f (d1)
join dim2 for key (id) <- f (d2)
join dim3 for key (id) <- f (d3);
which is the same query, except for the FOR KEY syntax. And I got this
(under explain, to only do the planning):
patched master
-----------------------------
join 25251 24906
keyjoin 17159
So that's ~30% regression compared to master / regular joins. I also
tried with join_collapse_limit=1 to eliminate the join order planning:
patched master
-----------------------------
join 31476 31252
keyjoin 19353
That's 40% regression. Of course, this is just explain - once there is
data in the table, and actual execution, the differences will be much
smaller. Still, it's not great.
I haven't looked very closely, but based on some quick profiling it
seems ensure_key_join_surface_facts / compute_key_join_relation_facts is
doing expensive stuff like findNotNullConstraintAttnum or
get_index_constraint, both of which do systable scans. That should
probably go through syscache or something like that.
regards
--
Tomas Vondra
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-12 00:20 Arne Roland <[email protected]>
parent: Tomas Vondra <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Arne Roland @ 2026-06-12 00:20 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; Joel Jacobson <[email protected]>; Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
Hi Tomas,
thank you for checking it out!
On 2026-06-11 11:02 PM, Tomas Vondra wrote:
> Hi,
>
> I took a quick look at the patch over the past couple days. I don't have
> a perfect understanding of how it works, but let me share what I have so
> far, before I get distracted by other stuff.
>
> I'm interested in this patch because there seems to be a possible
> overlap with the overlap with the starjoin planning (in that maybe we
> could try reusing some of the derived information for that).
>
> It's a mix of random thoughts, high/low level, important/superficial in
> no particular order.
>
>
> 1) It does not compile, ATExecSetRowSecurity seems to be missing
> prev_rls or something like that. I simply commented this out, to get it
> to compile.
Sorry, I am confused. There is the self contained block of
> @@ -18879,6 +18898,7 @@ ATExecSetRowSecurity(Relation rel, bool rls)
> Relation pg_class;
> Oid relid;
> HeapTuple tuple;
> + bool prev_rls;
>
> relid = RelationGetRelid(rel);
>
> @@ -18890,6 +18910,7 @@ ATExecSetRowSecurity(Relation rel, bool rls)
> if (!HeapTupleIsValid(tuple))
> elog(ERROR, "cache lookup failed for relation %u", relid);
>
> + prev_rls = ((Form_pg_class) GETSTRUCT(tuple))->relrowsecurity;
> ((Form_pg_class) GETSTRUCT(tuple))->relrowsecurity = rls;
> CatalogTupleUpdate(pg_class, &tuple->t_self, tuple);
>
> @@ -18898,6 +18919,21 @@ ATExecSetRowSecurity(Relation rel, bool rls)
>
> table_close(pg_class, RowExclusiveLock);
> heap_freetuple(tuple);
> +
> + /*
> + * Revalidate stored key-join proofs that depend on this relation. The
> + * key-join base-fact computation refuses to expose facts for a relation
> + * with row-level security enabled (parse_key_join.c), so flipping
> + * relrowsecurity can leave a stored proof unprovable. Revalidate
> + * whenever the flag actually changes; for the off-to-on transition the
> + * revalidation raises an error and aborts this DDL, while the on-to-off
> + * transition is a no-op for proofs that were already valid.
> + */
> + if (rls != prev_rls)
> + {
> + CommandCounterIncrement();
> + RevalidateDependentKeyJoinObjectsOnRelation(relid);
> + }
> }
Apart from that there shouldn't be any references to that. What
definition was missing?
> 2) fk_referenced_selected in find_key_join_match should be marked as
> PG_USED_FOR_ASSERTS_ONLY, to fix compiler warning
Thank you for spotting that.
> 3) It'd be helpful if the commit message for 0001 explained why this
> change is needed. More clearly than now, I mean. The initial message in
> this thread points at another thread as the source of this, but that
> thread is huge so how are reviewers expected to find the explanation?
>
> Don't explain just what the commit does, but why it's needed. Say, give
> an example of how the old code fails.
In short we need that to prevent objects our proof relies on to be
dropped or altered below us. I'll try to work that into the commit message.
> 4) I think there needs to be a README explaining how the feature works,
> i.e. the design and trade offs. Alternatively, it could be explained in
> a comment at the beginning of some .c file, but a README seems easier to
> find. Without this, reviewers have to piece it from the sgml "user"
> docs, and random comments all over the place.
>
>
> 5) It might be helpful if the README defined a couple terms introduced
> by the patch, but not really defined anywhere. I mean terms like: join
> point, proof, proof graph, fact, surface, "relation visible from". I can
> guess what each of these means, but maybe I got it wrong.
>
> Although, I now see "join point" was used in the docs before, so maybe
> it's a well-known term?
Thank you, I will try to come up with some better document explaining
the concept. For now I can mainly point you only to
https://keyjoin.org/#sec7.1, which gives a birds eye overview over how
the implementation and it's artifacts work.
Seeing your confusion, I think we should definitely reduce the amount of
terminology used. For instance "proof graph" is shorthand for the slice
of the catalog dependency graph contributed by key-join proofs
(depending object → proof object), i.e. the deptype='k' subgraph of the
dependency graph. I don't think we need to introduce this word as a new
concept. Thank you, this input is very valuable to improve this.
> 6) Does it always have to be a "foreign key traversal"? Consider an
> example like this:
>
> create table dim (id serial primary key);
> create table f (id serial primary key, did int);
> select * from f left join dim for key (id) <- f(did);
>
> Currently this fails because of no matching foreign key constraint, but
> isn't that pretty much the same thing as if the table actually had the
> foreign key (at least considering the cardinality of the join - it won't
> change it by adding/removing rows).
>
> I realize that'd contradict the "FOR KEY" part of this patch, but it's
> also one of the things that might be beneficial for the starjoin
> planning (in that we could maybe extend it to more cases). Although,
> maybe we could check those constraints during planning, just like we
> check the fkey_list.
This is a very different feature avoiding far less bugs than the
original key join. To give just once, consider
SELECT *
FROM customers cu
LEFT JOIN FOR KEY orders (id) <- cu (id)
WHERE customers.id = 122354;
We decided, this (among other) error classes, was important enough, we
pushed for stronger error guarantees, than just the uniqueness of the
referenced side. I still am convinced, this more save way of writing
queries is better for it's additional safety. I do think caring about
the foreign key gives the better syntax.
Do you think such constructions are very common for your customers?
Our proof framework with proof facts could potentially be leveraged to
proof such constructions too. We opted to keep this patch as minimal as
possible, since it's already huge. In the end our conquest is to get to
something, which is eventually commitable. This patch has a lot things
to get wrong. But I think as a second step adding support of other
schemas and handing this information of to the planer, should be a
fairly straight forward thing to do. Although it would add a few lines
on it's own, it's step, that I seems easier than landing a minimal
version of this patch.
> 7) The patch invents a new "FILTER" clause for joins:
>
> [ FILTER (WHERE join_filter) ]
>
> I understand why it's done - there may be additional join conditions, on
> top of the FK equality. But I think it'll be rather confusing. We
> already have a "Join Filter", which is used for join clauses that happen
> to not be used as "proper" join conditions (e.g. Hash/Merge Cond), and
> has to be evaluated "after" the join itself. And now we'd have another
> kind of "join filter" ...
>
> Is there a different that'd make this work without the FILTER? For
> example, we might encode the "key join" information in the existing ON
> (...) clause:
>
> ON (KEY (oi.order_id) -> (o.id) AND ... other clauses ...)
>
> but it seems not as readable. Or maybe just use something else than
> "FILTER"? Not sure.
This word has the benefit of being already a keyword and it solves the
problem rather clear cut. Do you think, there is something we could do
to make this better?
> 8) I don't understand this change in functioncmds:
>
> /* Routine kind cannot change for an existing pg_proc OID. */
> Assert(procForm->prokind != PROKIND_AGGREGATE);
>
> The comment says we can't change OID, but the assert checks it's not an
> aggregate functions. Isn't that misleading?
Maybe it would be cleaner to mention additionally, that "aggregates were
already rejected on the pre-lock tuple"? I actually think, that comment
is indeed stating a helpful invariant to explain why we are concurrency
save here.
> 9) DefineView now adjusts the query ID. Why is that needed? Isn't that a
> bit weird?
Sorry, does it? Could you point out where exactly? I might be too tired
to see it right now.
> 10) checkWellFormedRecursionWalker now recurses, but why is that needed?
Didn't in already recurse before? Didn't check the blame, but I do think
it's recursing for a long time.
I just see an added line to check the new filter clause for subqueries
or something to recurse into.
> 11) It's not clear to me why we need p_creating_stored_object, and it's
> not explained anywhere. Maybe it's obvious, but not to me.
Sorry, that's my oversight. We need to take stronger locks, if we store
something materially, to prevent concurrent changes, while we store it.
Where do you recon a better comment would be helpful? A longer comment
directly in the struct definition?
> 12) I'm very skeptical anyone can meaningfully review parse_key_join.c.
> It's 150KB with ~5200 lines (very dense, with pretty minimal comments).
> That's a massive file. The chance of me declaring this committable is
> about 0%, simply because I wouldn't believe I understand it.
>
> I think it needs to be broken up into smaller pieces, somehow. I don't
> know how, but perhaps it's possible to extract a "minimal feature"
> handling some limited subset of cases, and then gradually expand it?
I think there is serious complexity involved in just getting the basic
the architecture. That being said, I am very open to any idea of a
stepping stone to this.
It's something I thought a lot about during the last weeks. I am toying
with the thought of ripping out all changes related to anything stored
like views and sql functions as a minimal, minimal version. It's so bare
bone, I'm not terribly exited about doing that, but maybe it's a
necessary evil. Having thought about a lot of edge cases related to that
storing, As I see it, we wouldn't save a lot of lines of code with this,
but it makes reasoning about correctness easier. I can testament to the
complexity in reasoning and correctness it adds. Do you have any other
ideas for a stepping stone, that could reasonably land?
I think this one of the most fundamental questions to be answered,
before we optimize one of the paths. What is the first consumer of the
surface fact framework and how can we stage a minimal commit around it.
We need a committer to feel save to commit something with this
framework. If you have something notably smaller than this, I am all ears.
> Furthermore, it seems a lot of that file is duplicate with code we
> already have elsewhere. For example, couldn't it use a bunch of list
> functions instead of writing a local version?
>
> list_contains_equal_node -> list_member
> append_dependencies_unique -> list_concat_unique
> append_dependency_unique -> list_append_unique
> ...
>
> There may be more such cases, I haven't looked for them.
Thanks for bringing it up. I will look into that, once I've properly
gone through the other suggestions. I suspect there won't be many line
to save, but I'll have a look.
> 13) I think the main question is whether parse-analyze is the right
> place to handle this. I don't know. I assume one of the reasons for
> doing that is to get an error when defining a view, or when altering an
> object - e.g. like when dropping a function used by a view. Which seems
> reasonable, people would not like views silently broken by DDL.
>
> But it seems to be this also leads to a lot of code duplication, because
> the parse analysis now has to "reimplement" a lot of the stuff already
> done in later stages, after parse analyze. For example, we have the
> root->fkey_list thing, but that's not available yet.
>
> There's probably more such information - like innerrel_is_unique,
> rel_is_distinct_for, relation_has_unique_index_for etc.
>
> Maybe it's not worth it? What if we did this in the planner instead? How
> much simpler would it get? My intuition is it'd get much smaller, but
> maybe I'm wrong.
>
> It'd probably mean it's not necessary to expand views during parse,
> which was one of the problems mentioned at the beginning of this thread.
>
> I suppose we'd need to keep additional information in the plan to know
> which joins to check, etc.
If we want to use this for correctness and for proofs, we can't do it
plan time. We have DDL-writes to store proofs. In it's nature this is a
compile time feature.
Even if we don't include all of that in the first patch, this places
very severe limitations like the DDL issue, which would be just tooo
limiting to get to as an end place. I do think it's more reasonable how
to cut this up into more digestible pieces.
Even though the planner is messy, I feel more at home there than here in
the parser. I could see a world were we clean up some of those out of
the planner to make them available earlier some time in parsing. We
could push those variables forward to the planner to avoid redoing the
work. Each of these steps would need a careful performance check and I
am not sure how the real stepping stones would look like.
> 14) If we wanted to use some of this for the starjoin planning stuff,
> we'd need to propagate more information too, I think. But I'm not sure
> about this - we already have the information about foreign keys, so if
> key joins are tied to foreign keys, there would not be no new useful
> information I suppose.
>
> Plus, I don't want to make that patch dependent on people using new
> syntax. If that can give us *additional* information, that would be a
> different thing.
As I said above, if we figure out what information we want to propagate
this will be helpful. We will be able to propagate this. And if we can
get in a base patch with this architecture, adding this should be
straight forward.
One thing, that sounds fairly simple to derive from our proof, is the
proof graph. This means in every node we denote, this node can be
treated as cardinality preserving joined onto a different node. For
planning we need something more global, because we need to consider
something WHERE/HAVING, but the existence of such a clause shouldn't be
complex to check for.
> [...]
>
> 16) I was wondering what performance impact this has, roughly. So I
> created a simple 4-way join with fact + 3 dimensions:
>
> create table dim1 (id serial primary key, val text);
> create table dim2 (id serial primary key, val text);
> create table dim3 (id serial primary key, val text);
> create table f (id serial primary key,
> d1 int not null references dim1(id),
> d2 int not null references dim2(id),
> d3 int not null references dim3(id));
>
> and then measured throughput with 2 queries
>
> select * from f
> join dim1 on (dim1.id = d1)
> join dim2 on (dim2.id = d2)
> join dim3 on (dim3.id = d3);
>
> select * from f
> join dim1 for key (id) <- f (d1)
> join dim2 for key (id) <- f (d2)
> join dim3 for key (id) <- f (d3);
>
> which is the same query, except for the FOR KEY syntax. And I got this
> (under explain, to only do the planning):
>
> patched master
> -----------------------------
> join 25251 24906
> keyjoin 17159
>
> So that's ~30% regression compared to master / regular joins. I also
> tried with join_collapse_limit=1 to eliminate the join order planning:
>
> patched master
> -----------------------------
> join 31476 31252
> keyjoin 19353
>
> That's 40% regression. Of course, this is just explain - once there is
> data in the table, and actual execution, the differences will be much
> smaller. Still, it's not great.
>
> I haven't looked very closely, but based on some quick profiling it
> seems ensure_key_join_surface_facts / compute_key_join_relation_facts is
> doing expensive stuff like findNotNullConstraintAttnum or
> get_index_constraint, both of which do systable scans. That should
> probably go through syscache or something like that.
I'm not too surprised about ensure_key_join_surface_facts holding most
of the regression, since it's doing all the work. Since I spent no time
or thought on optimizing runtime thus far, I think there a lot of long
hanging fruits left. I'd prefer to sort out the architecture first, but
I think, we should be able to improve the parsetime of this feature by a
sizeable amount. I fully agree: Before committing this, we should hit
some of the relevant functions for a quick win.
> regards
>
I will probably work my way through this incrementally. I hope to have a
version incorporating your vast feedback next week.
Regards
Arne
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-12 17:26 Tomas Vondra <[email protected]>
parent: Arne Roland <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Tomas Vondra @ 2026-06-12 17:26 UTC (permalink / raw)
To: Arne Roland <[email protected]>; Joel Jacobson <[email protected]>; Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On 6/12/26 02:20, Arne Roland wrote:
> Hi Tomas,
>
> thank you for checking it out!
>
> On 2026-06-11 11:02 PM, Tomas Vondra wrote:
>> Hi,
>>
>> I took a quick look at the patch over the past couple days. I don't have
>> a perfect understanding of how it works, but let me share what I have so
>> far, before I get distracted by other stuff.
>>
>> I'm interested in this patch because there seems to be a possible
>> overlap with the overlap with the starjoin planning (in that maybe we
>> could try reusing some of the derived information for that).
>>
>> It's a mix of random thoughts, high/low level, important/superficial in
>> no particular order.
>>
>>
>> 1) It does not compile, ATExecSetRowSecurity seems to be missing
>> prev_rls or something like that. I simply commented this out, to get it
>> to compile.
>
> Sorry, I am confused. There is the self contained block of
>
>> @@ -18879,6 +18898,7 @@ ATExecSetRowSecurity(Relation rel, bool rls)
>> Relation pg_class;
>> Oid relid;
>> HeapTuple tuple;
>> + bool prev_rls;
>> relid = RelationGetRelid(rel);
>> @@ -18890,6 +18910,7 @@ ATExecSetRowSecurity(Relation rel, bool rls)
>> if (!HeapTupleIsValid(tuple))
>> elog(ERROR, "cache lookup failed for relation %u", relid);
>> + prev_rls = ((Form_pg_class) GETSTRUCT(tuple))->relrowsecurity;
>> ((Form_pg_class) GETSTRUCT(tuple))->relrowsecurity = rls;
>> CatalogTupleUpdate(pg_class, &tuple->t_self, tuple);
>> @@ -18898,6 +18919,21 @@ ATExecSetRowSecurity(Relation rel, bool rls)
>> table_close(pg_class, RowExclusiveLock);
>> heap_freetuple(tuple);
>> +
>> + /*
>> + * Revalidate stored key-join proofs that depend on this
>> relation. The
>> + * key-join base-fact computation refuses to expose facts for a
>> relation
>> + * with row-level security enabled (parse_key_join.c), so flipping
>> + * relrowsecurity can leave a stored proof unprovable. Revalidate
>> + * whenever the flag actually changes; for the off-to-on
>> transition the
>> + * revalidation raises an error and aborts this DDL, while the
>> on-to-off
>> + * transition is a no-op for proofs that were already valid.
>> + */
>> + if (rls != prev_rls)
>> + {
>> + CommandCounterIncrement();
>> + RevalidateDependentKeyJoinObjectsOnRelation(relid);
>> + }
>> }
> Apart from that there shouldn't be any references to that. What
> definition was missing?
I guess git-am gets confused in some way, because cfbot has the same
issue with this:
https://github.com/postgresql-cfbot/postgresql/actions/runs/27379594748/job/80912606962
>> 2) fk_referenced_selected in find_key_join_match should be marked as
>> PG_USED_FOR_ASSERTS_ONLY, to fix compiler warning
> Thank you for spotting that.
>> 3) It'd be helpful if the commit message for 0001 explained why this
>> change is needed. More clearly than now, I mean. The initial message in
>> this thread points at another thread as the source of this, but that
>> thread is huge so how are reviewers expected to find the explanation?
>>
>> Don't explain just what the commit does, but why it's needed. Say, give
>> an example of how the old code fails.
>
> In short we need that to prevent objects our proof relies on to be
> dropped or altered below us. I'll try to work that into the commit message.
Yeah, understood. I guess the question is where else we should adopt
this new idiom. AFAIK this is pretty much a TOCTOU bug - don't we have a
similar issue elsewhere?
>> 4) I think there needs to be a README explaining how the feature works,
>> i.e. the design and trade offs. Alternatively, it could be explained in
>> a comment at the beginning of some .c file, but a README seems easier to
>> find. Without this, reviewers have to piece it from the sgml "user"
>> docs, and random comments all over the place.
>>
>>
>> 5) It might be helpful if the README defined a couple terms introduced
>> by the patch, but not really defined anywhere. I mean terms like: join
>> point, proof, proof graph, fact, surface, "relation visible from". I can
>> guess what each of these means, but maybe I got it wrong.
>>
>> Although, I now see "join point" was used in the docs before, so maybe
>> it's a well-known term?
>
> Thank you, I will try to come up with some better document explaining
> the concept. For now I can mainly point you only to https://keyjoin.org/
> #sec7.1, which gives a birds eye overview over how the implementation
> and it's artifacts work.
>
> Seeing your confusion, I think we should definitely reduce the amount of
> terminology used. For instance "proof graph" is shorthand for the slice
> of the catalog dependency graph contributed by key-join proofs
> (depending object → proof object), i.e. the deptype='k' subgraph of the
> dependency graph. I don't think we need to introduce this word as a new
> concept. Thank you, this input is very valuable to improve this.
>
I'm not against introducing new terminology, at least not when there's
no established terminology in the code already. But it would be helpful
to explain what the new terms mean, and how they map to the structs and
catalogs (so that people don't have to deduce them).
>> 6) Does it always have to be a "foreign key traversal"? Consider an
>> example like this:
>>
>> create table dim (id serial primary key);
>> create table f (id serial primary key, did int);
>> select * from f left join dim for key (id) <- f(did);
>>
>> Currently this fails because of no matching foreign key constraint, but
>> isn't that pretty much the same thing as if the table actually had the
>> foreign key (at least considering the cardinality of the join - it won't
>> change it by adding/removing rows).
>>
>> I realize that'd contradict the "FOR KEY" part of this patch, but it's
>> also one of the things that might be beneficial for the starjoin
>> planning (in that we could maybe extend it to more cases). Although,
>> maybe we could check those constraints during planning, just like we
>> check the fkey_list.
> This is a very different feature avoiding far less bugs than the
> original key join. To give just once, consider
>
> SELECT *
> FROM customers cu
> LEFT JOIN FOR KEY orders (id) <- cu (id)
> WHERE customers.id = 122354;
>
I don't follow. What does this query illustrate?
>
> We decided, this (among other) error classes, was important enough, we
> pushed for stronger error guarantees, than just the uniqueness of the
> referenced side. I still am convinced, this more save way of writing
> queries is better for it's additional safety. I do think caring about
> the foreign key gives the better syntax.
>
> Do you think such constructions are very common for your customers?
>
I don't know, really. I was merely thinking about using this stuff for
the starjoin optimization patch. And that already handles joins on
foreign keys just fine, but extending to more queries might help.
> Our proof framework with proof facts could potentially be leveraged to
> proof such constructions too. We opted to keep this patch as minimal as
> possible, since it's already huge. In the end our conquest is to get to
> something, which is eventually commitable. This patch has a lot things
> to get wrong. But I think as a second step adding support of other
> schemas and handing this information of to the planer, should be a
> fairly straight forward thing to do. Although it would add a few lines
> on it's own, it's step, that I seems easier than landing a minimal
> version of this patch.
>
OK. I realize this probably goes against my suggestion to make the patch
smaller. I certainly don't insist on supporting it.
>> 7) The patch invents a new "FILTER" clause for joins:
>>
>> [ FILTER (WHERE join_filter) ]
>>
>> I understand why it's done - there may be additional join conditions, on
>> top of the FK equality. But I think it'll be rather confusing. We
>> already have a "Join Filter", which is used for join clauses that happen
>> to not be used as "proper" join conditions (e.g. Hash/Merge Cond), and
>> has to be evaluated "after" the join itself. And now we'd have another
>> kind of "join filter" ...
>>
>> Is there a different that'd make this work without the FILTER? For
>> example, we might encode the "key join" information in the existing ON
>> (...) clause:
>>
>> ON (KEY (oi.order_id) -> (o.id) AND ... other clauses ...)
>>
>> but it seems not as readable. Or maybe just use something else than
>> "FILTER"? Not sure.
> This word has the benefit of being already a keyword and it solves the
> problem rather clear cut. Do you think, there is something we could do
> to make this better?
Not at the moment, sorry.
>> 8) I don't understand this change in functioncmds:
>>
>> /* Routine kind cannot change for an existing pg_proc OID. */
>> Assert(procForm->prokind != PROKIND_AGGREGATE);
>>
>> The comment says we can't change OID, but the assert checks it's not an
>> aggregate functions. Isn't that misleading?
> Maybe it would be cleaner to mention additionally, that "aggregates were
> already rejected on the pre-lock tuple"? I actually think, that comment
> is indeed stating a helpful invariant to explain why we are concurrency
> save here.
I don't follow. The comment says we can't change OID of an existing
procedure. OK, sure. But the assert checks the procedure is not an
aggregate function. How is that comment an accurate description of the
purpose of the assert?
>> 9) DefineView now adjusts the query ID. Why is that needed? Isn't that a
>> bit weird?
> Sorry, does it? Could you point out where exactly? I might be too tired
> to see it right now.
>> 10) checkWellFormedRecursionWalker now recurses, but why is that needed?
>
> Didn't in already recurse before? Didn't check the blame, but I do think
> it's recursing for a long time.
>
> I just see an added line to check the new filter clause for subqueries
> or something to recurse into.
>
Oh, I see. My mistake, sorry.
>> 11) It's not clear to me why we need p_creating_stored_object, and it's
>> not explained anywhere. Maybe it's obvious, but not to me.
>
> Sorry, that's my oversight. We need to take stronger locks, if we store
> something materially, to prevent concurrent changes, while we store it.
>
> Where do you recon a better comment would be helpful? A longer comment
> directly in the struct definition?
>
Well, I guess it could be mentioned before the struct definition. And
then maybe also in the README explaining how this all fits together.
>> 12) I'm very skeptical anyone can meaningfully review parse_key_join.c.
>> It's 150KB with ~5200 lines (very dense, with pretty minimal comments).
>> That's a massive file. The chance of me declaring this committable is
>> about 0%, simply because I wouldn't believe I understand it.
>>
>> I think it needs to be broken up into smaller pieces, somehow. I don't
>> know how, but perhaps it's possible to extract a "minimal feature"
>> handling some limited subset of cases, and then gradually expand it?
>
> I think there is serious complexity involved in just getting the basic
> the architecture. That being said, I am very open to any idea of a
> stepping stone to this.
>
> It's something I thought a lot about during the last weeks. I am toying
> with the thought of ripping out all changes related to anything stored
> like views and sql functions as a minimal, minimal version. It's so bare
> bone, I'm not terribly exited about doing that, but maybe it's a
> necessary evil. Having thought about a lot of edge cases related to that
> storing, As I see it, we wouldn't save a lot of lines of code with this,
> but it makes reasoning about correctness easier. I can testament to the
> complexity in reasoning and correctness it adds. Do you have any other
> ideas for a stepping stone, that could reasonably land?
>
> I think this one of the most fundamental questions to be answered,
> before we optimize one of the paths. What is the first consumer of the
> surface fact framework and how can we stage a minimal commit around it.
> We need a committer to feel save to commit something with this
> framework. If you have something notably smaller than this, I am all ears.
>
I don't know how to split the patch, but I know that unless that happens
the patch is unlikely to move forward.
FWIW, it does not mean the parts have to be committed separately. It's
possible to review small pieces, and then squash them before commit to
get something "meaningful for users".
>> Furthermore, it seems a lot of that file is duplicate with code we
>> already have elsewhere. For example, couldn't it use a bunch of list
>> functions instead of writing a local version?
>>
>> list_contains_equal_node -> list_member
>> append_dependencies_unique -> list_concat_unique
>> append_dependency_unique -> list_append_unique
>> ...
>>
>> There may be more such cases, I haven't looked for them.
> Thanks for bringing it up. I will look into that, once I've properly
> gone through the other suggestions. I suspect there won't be many line
> to save, but I'll have a look.
OK, good.
>> 13) I think the main question is whether parse-analyze is the right
>> place to handle this. I don't know. I assume one of the reasons for
>> doing that is to get an error when defining a view, or when altering an
>> object - e.g. like when dropping a function used by a view. Which seems
>> reasonable, people would not like views silently broken by DDL.
>>
>> But it seems to be this also leads to a lot of code duplication, because
>> the parse analysis now has to "reimplement" a lot of the stuff already
>> done in later stages, after parse analyze. For example, we have the
>> root->fkey_list thing, but that's not available yet.
>>
>> There's probably more such information - like innerrel_is_unique,
>> rel_is_distinct_for, relation_has_unique_index_for etc.
>>
>> Maybe it's not worth it? What if we did this in the planner instead? How
>> much simpler would it get? My intuition is it'd get much smaller, but
>> maybe I'm wrong.
>>
>> It'd probably mean it's not necessary to expand views during parse,
>> which was one of the problems mentioned at the beginning of this thread.
>>
>> I suppose we'd need to keep additional information in the plan to know
>> which joins to check, etc.
>
> If we want to use this for correctness and for proofs, we can't do it
> plan time. We have DDL-writes to store proofs. In it's nature this is a
> compile time feature.
>
Is that actually true? If we check the correctness later in the planner,
we'd still get a failure. Why couldn't that verify all the proofs, just
like the parse-analyze? We may need to retain more information, ofc.
> Even if we don't include all of that in the first patch, this places
> very severe limitations like the DDL issue, which would be just tooo
> limiting to get to as an end place. I do think it's more reasonable how
> to cut this up into more digestible pieces.
>
I'm not sure what "DDL issue" is, sorry :-(
I may be missing something, but the main difference in behavior seems to
be for views - the current patch verifies the proofs when creating the
view / altering objects, and rejects those. And AFAICS after moving it
to the planner, that would not be the case anymore.
But for regular ad hoc queries there's not much difference, no? You'd
get a failure, no matter what.
> Even though the planner is messy, I feel more at home there than here in
> the parser. I could see a world were we clean up some of those out of
> the planner to make them available earlier some time in parsing. We
> could push those variables forward to the planner to avoid redoing the
> work. Each of these steps would need a careful performance check and I
> am not sure how the real stepping stones would look like.
>
I'm skeptical about moving this stuff to an earlier phase (so that the
parse can see it). You can try, but it probably requires moving a lot of
other stuff too, some of which may be expensive.
>> 14) If we wanted to use some of this for the starjoin planning stuff,
>> we'd need to propagate more information too, I think. But I'm not sure
>> about this - we already have the information about foreign keys, so if
>> key joins are tied to foreign keys, there would not be no new useful
>> information I suppose.
>>
>> Plus, I don't want to make that patch dependent on people using new
>> syntax. If that can give us *additional* information, that would be a
>> different thing.
>
> As I said above, if we figure out what information we want to propagate
> this will be helpful. We will be able to propagate this. And if we can
> get in a base patch with this architecture, adding this should be
> straight forward.
>
> One thing, that sounds fairly simple to derive from our proof, is the
> proof graph. This means in every node we denote, this node can be
> treated as cardinality preserving joined onto a different node. For
> planning we need something more global, because we need to consider
> something WHERE/HAVING, but the existence of such a clause shouldn't be
> complex to check for.
>
Understood.
>> [...]
>>
>> 16) I was wondering what performance impact this has, roughly. So I
>> created a simple 4-way join with fact + 3 dimensions:
>>
>> create table dim1 (id serial primary key, val text);
>> create table dim2 (id serial primary key, val text);
>> create table dim3 (id serial primary key, val text);
>> create table f (id serial primary key,
>> d1 int not null references dim1(id),
>> d2 int not null references dim2(id),
>> d3 int not null references dim3(id));
>>
>> and then measured throughput with 2 queries
>>
>> select * from f
>> join dim1 on (dim1.id = d1)
>> join dim2 on (dim2.id = d2)
>> join dim3 on (dim3.id = d3);
>>
>> select * from f
>> join dim1 for key (id) <- f (d1)
>> join dim2 for key (id) <- f (d2)
>> join dim3 for key (id) <- f (d3);
>>
>> which is the same query, except for the FOR KEY syntax. And I got this
>> (under explain, to only do the planning):
>>
>> patched master
>> -----------------------------
>> join 25251 24906
>> keyjoin 17159
>>
>> So that's ~30% regression compared to master / regular joins. I also
>> tried with join_collapse_limit=1 to eliminate the join order planning:
>>
>> patched master
>> -----------------------------
>> join 31476 31252
>> keyjoin 19353
>>
>> That's 40% regression. Of course, this is just explain - once there is
>> data in the table, and actual execution, the differences will be much
>> smaller. Still, it's not great.
>>
>> I haven't looked very closely, but based on some quick profiling it
>> seems ensure_key_join_surface_facts / compute_key_join_relation_facts is
>> doing expensive stuff like findNotNullConstraintAttnum or
>> get_index_constraint, both of which do systable scans. That should
>> probably go through syscache or something like that.
> I'm not too surprised about ensure_key_join_surface_facts holding most
> of the regression, since it's doing all the work. Since I spent no time
> or thought on optimizing runtime thus far, I think there a lot of long
> hanging fruits left. I'd prefer to sort out the architecture first, but
> I think, we should be able to improve the parsetime of this feature by a
> sizeable amount. I fully agree: Before committing this, we should hit
> some of the relevant functions for a quick win.
It's just a guess. I'm not sure fixing ensure_key_join_surface_facts
will make it much faster - it's possible, but I haven't tried. There are
probably more issues like this. But I'm also not surprised the patch has
this kind of issues, it's fine for an early WIP patch.
regards
--
Tomas Vondra
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-14 18:17 Arne Roland <[email protected]>
parent: Tomas Vondra <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Arne Roland @ 2026-06-14 18:17 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; Joel Jacobson <[email protected]>; Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
On 2026-06-12 7:26 PM, Tomas Vondra wrote:
>
> On 6/12/26 02:20, Arne Roland wrote:
>> Hi Tomas,
>>
>> thank you for checking it out!
>> [...]
>>
> I guess git-am gets confused in some way, because cfbot has the same
> issue with this:
>
> https://github.com/postgresql-cfbot/postgresql/actions/runs/27379594748/job/80912606962
I see. It's a rebase issue. The patch shouldn't apply cleanly on master,
but somehow it does. My next version will be rebased on the current
master again, but I want to work more of the feedback into the patch
before posting a new version here. At least more detailed documentation
and glossary, at best already some more finely grained split up.
> [...]
>>> 6) Does it always have to be a "foreign key traversal"? Consider an
>>> example like this:
>>>
>>> create table dim (id serial primary key);
>>> create table f (id serial primary key, did int);
>>> select * from f left join dim for key (id) <- f(did);
>>>
>>> Currently this fails because of no matching foreign key constraint, but
>>> isn't that pretty much the same thing as if the table actually had the
>>> foreign key (at least considering the cardinality of the join - it won't
>>> change it by adding/removing rows).
>>>
>>> I realize that'd contradict the "FOR KEY" part of this patch, but it's
>>> also one of the things that might be beneficial for the starjoin
>>> planning (in that we could maybe extend it to more cases). Although,
>>> maybe we could check those constraints during planning, just like we
>>> check the fkey_list.
>> This is a very different feature avoiding far less bugs than the
>> original key join. To give just once, consider
>>
>> SELECT *
>> FROM customers cu
>> LEFT JOIN FOR KEY orders (id) <- cu (id)
>> WHERE customers.id = 122354;
>>
> I don't follow. What does this query illustrate?
Most relevantly here it illustrates, that fks instead have additional
relevant guarantees compared to unique/primary key constraints for
making writing and reading queries easier and safer.
>> Our proof framework with proof facts could potentially be leveraged to
>> proof such constructions too. We opted to keep this patch as minimal as
>> possible, since it's already huge. In the end our conquest is to get to
>> something, which is eventually commitable. This patch has a lot things
>> to get wrong. But I think as a second step adding support of other
>> schemas and handing this information of to the planer, should be a
>> fairly straight forward thing to do. Although it would add a few lines
>> on it's own, it's step, that I seems easier than landing a minimal
>> version of this patch.
>>
> OK. I realize this probably goes against my suggestion to make the patch
> smaller. I certainly don't insist on supporting it.
I do want that though. It has advantages in using key joins in old
codebases with existing SQL without full refactoring. And it might be
ultimately helpful to the optimizer too. I just wonder about the best
order to get a simple case of the architecture in.
> [...]
>
>>> 8) I don't understand this change in functioncmds:
>>>
>>> /* Routine kind cannot change for an existing pg_proc OID. */
>>> Assert(procForm->prokind != PROKIND_AGGREGATE);
>>>
>>> The comment says we can't change OID, but the assert checks it's not an
>>> aggregate functions. Isn't that misleading?
>> Maybe it would be cleaner to mention additionally, that "aggregates were
>> already rejected on the pre-lock tuple"? I actually think, that comment
>> is indeed stating a helpful invariant to explain why we are concurrency
>> save here.
> I don't follow. The comment says we can't change OID of an existing
> procedure. OK, sure. But the assert checks the procedure is not an
> aggregate function. How is that comment an accurate description of the
> purpose of the assert?
it explains the invariant, why we can rely on our earlier pre-lock tuple
check. To me that seemed to be a relevant enough assumption about the
code to make it explicit in a comment.
> [...]
>>> 13) I think the main question is whether parse-analyze is the right
>>> place to handle this. I don't know. I assume one of the reasons for
>>> doing that is to get an error when defining a view, or when altering an
>>> object - e.g. like when dropping a function used by a view. Which seems
>>> reasonable, people would not like views silently broken by DDL.
>>>
>>> But it seems to be this also leads to a lot of code duplication, because
>>> the parse analysis now has to "reimplement" a lot of the stuff already
>>> done in later stages, after parse analyze. For example, we have the
>>> root->fkey_list thing, but that's not available yet.
>>>
>>> There's probably more such information - like innerrel_is_unique,
>>> rel_is_distinct_for, relation_has_unique_index_for etc.
>>>
>>> Maybe it's not worth it? What if we did this in the planner instead? How
>>> much simpler would it get? My intuition is it'd get much smaller, but
>>> maybe I'm wrong.
>>>
>>> It'd probably mean it's not necessary to expand views during parse,
>>> which was one of the problems mentioned at the beginning of this thread.
>>>
>>> I suppose we'd need to keep additional information in the plan to know
>>> which joins to check, etc.
>> If we want to use this for correctness and for proofs, we can't do it
>> plan time. We have DDL-writes to store proofs. In it's nature this is a
>> compile time feature.
>>
> Is that actually true? If we check the correctness later in the planner,
> we'd still get a failure. Why couldn't that verify all the proofs, just
> like the parse-analyze? We may need to retain more information, ofc.
>
>> Even if we don't include all of that in the first patch, this places
>> very severe limitations like the DDL issue, which would be just tooo
>> limiting to get to as an end place. I do think it's more reasonable how
>> to cut this up into more digestible pieces.
>>
> I'm not sure what "DDL issue" is, sorry :-(
>
> I may be missing something, but the main difference in behavior seems to
> be for views - the current patch verifies the proofs when creating the
> view / altering objects, and rejects those. And AFAICS after moving it
> to the planner, that would not be the case anymore.
>
> But for regular ad hoc queries there's not much difference, no? You'd
> get a failure, no matter what.
With DDL-issue I was eluding to a DDL command that attaches a query to
some object. Views, sql functions and policies all do that. I don't see
us doing that work planning time. Theoretically we could try to use a
new planner hook for that, to call the planner with an extra struct
element telling it about increased locking arrangements without the
intend to ever execute a query and abort after the proof.
However I do think this introduces more future complexity by entangling
separate concerns in the same code path, and I am not sure we are doing
ourselves a favor with this, even if we would save a hand full of lines.
I am not convinced I want to tackle that complexity on top of this
already non-trivial patch.
I intend to try to separate the DDL handling case out into it's own
patch of the patch series. While in lines of code is not that massive,
reasoning about those two individually is indeed simpler. Even just
getting to locking for the DDL-case right, isn't trivial.
I hope to get to that by the end of the now starting week.
>> Even though the planner is messy, I feel more at home there than here in
>> the parser. I could see a world were we clean up some of those out of
>> the planner to make them available earlier some time in parsing. We
>> could push those variables forward to the planner to avoid redoing the
>> work. Each of these steps would need a careful performance check and I
>> am not sure how the real stepping stones would look like.
>>
> I'm skeptical about moving this stuff to an earlier phase (so that the
> parse can see it). You can try, but it probably requires moving a lot of
> other stuff too, some of which may be expensive.
I have a high level general response and one tailored to this patch.
I'll start with this particular patch: For this patch I am mostly
concerned with not doing complex work twice: Once in the parser AND once
in the optimizer. And the below general thoughts are not easily actionable.
More generally:
Your skepticism is well placed. Every change there would warrant
benchmarking. I am just not completely convinced the planner is super
optimal in the way it works. I suspect a lot of code there has not been
optimized, because it's hard to wrap your head around it, that it
doesn't feel like an easy gain anymore.
While 1:1 pulling stuff out of the planner almost surely gives mostly
performance regressions, a clean architecture allowing more simple,
isolated performance improvements sounds beneficial, too. And I don't
want to open this can of worms right now.
I just recalled the time when Andres made the storage pluggable by
introducing a layer of pointers everywhere. The new storage interface
ended up being faster than the old.
This is not storage and I am not Andres. I just wanted to share
precedent, that a clear architecture with optimization disadvantages is
not necessarily always slower.
> regards
>
Regards
Arne
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-23 15:53 Arne Roland <[email protected]>
parent: Arne Roland <[email protected]>
0 siblings, 2 replies; 26+ messages in thread
From: Arne Roland @ 2026-06-23 15:53 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; Joel Jacobson <[email protected]>; Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
Hello together,
I created a rebased patch series. I added a short README as discussed
and split up the complex locking code into their own patch. Now 0001
(the similar to the old 0002) is still fairly big, but still covers
enough use case to be independently commitable. The stored object logic
has been moved out into it's own patch 0003, which contains all the
interesting concurrency considerations. The end result of our current
0004 compared to the old 0003 are only a hand full adjustments based on
Tomas comments and a few words sharpened in comments here and there as I
was reviewing the code all over again.
Furthermore thanks to Joel, there is now a new member 0005 of the patch
series, that includes improved psql autocompletion.
What I have considered, but ended up not including in this patch:
Homogenizing the planner utilities and the key join parser utilities.
The issue is, that we have such different data structures we need for
dependency tracking, we can't just use the planners functions. There
might be a world, where we could try to create a shared helper function
with some flags. But it seems to me, this doesn't increase the
simplicity of this patch by making the patch sprawl out even more than
it already does. There is a real trade off here and I included a comment
about this code for the future reader.
I am still investigating 0001 for further split up, since we are still
over 5200 loc, with the src/backend/parser/parse_key_join.c sitting
right below 4700 lines. My aim there is not to create a smaller patch
doing meaningful work, but a series like Tomas suggested, that might
make review easier. The current repost is far from perfect, but
hopefully easier to read than the prior patch series.
Regards
Arne
On 2026-06-14 8:17 PM, Arne Roland wrote:
>
> On 2026-06-12 7:26 PM, Tomas Vondra wrote:
>>
>> On 6/12/26 02:20, Arne Roland wrote:
>>> Hi Tomas,
>>>
>>> thank you for checking it out!
>>> [...]
>>>
>> I guess git-am gets confused in some way, because cfbot has the same
>> issue with this:
>>
>> https://github.com/postgresql-cfbot/postgresql/actions/runs/27379594748/job/80912606962
>>
> I see. It's a rebase issue. The patch shouldn't apply cleanly on
> master, but somehow it does. My next version will be rebased on the
> current master again, but I want to work more of the feedback into the
> patch before posting a new version here. At least more detailed
> documentation and glossary, at best already some more finely grained
> split up.
>> [...]
>>>> 6) Does it always have to be a "foreign key traversal"? Consider an
>>>> example like this:
>>>>
>>>> create table dim (id serial primary key);
>>>> create table f (id serial primary key, did int);
>>>> select * from f left join dim for key (id) <- f(did);
>>>>
>>>> Currently this fails because of no matching foreign key constraint,
>>>> but
>>>> isn't that pretty much the same thing as if the table actually had the
>>>> foreign key (at least considering the cardinality of the join - it
>>>> won't
>>>> change it by adding/removing rows).
>>>>
>>>> I realize that'd contradict the "FOR KEY" part of this patch, but it's
>>>> also one of the things that might be beneficial for the starjoin
>>>> planning (in that we could maybe extend it to more cases). Although,
>>>> maybe we could check those constraints during planning, just like we
>>>> check the fkey_list.
>>> This is a very different feature avoiding far less bugs than the
>>> original key join. To give just once, consider
>>>
>>> SELECT *
>>> FROM customers cu
>>> LEFT JOIN FOR KEY orders (id) <- cu (id)
>>> WHERE customers.id = 122354;
>>>
>> I don't follow. What does this query illustrate?
> Most relevantly here it illustrates, that fks instead have additional
> relevant guarantees compared to unique/primary key constraints for
> making writing and reading queries easier and safer.
>>> Our proof framework with proof facts could potentially be leveraged to
>>> proof such constructions too. We opted to keep this patch as minimal as
>>> possible, since it's already huge. In the end our conquest is to get to
>>> something, which is eventually commitable. This patch has a lot things
>>> to get wrong. But I think as a second step adding support of other
>>> schemas and handing this information of to the planer, should be a
>>> fairly straight forward thing to do. Although it would add a few lines
>>> on it's own, it's step, that I seems easier than landing a minimal
>>> version of this patch.
>>>
>> OK. I realize this probably goes against my suggestion to make the patch
>> smaller. I certainly don't insist on supporting it.
> I do want that though. It has advantages in using key joins in old
> codebases with existing SQL without full refactoring. And it might be
> ultimately helpful to the optimizer too. I just wonder about the best
> order to get a simple case of the architecture in.
>> [...]
>>
>>>> 8) I don't understand this change in functioncmds:
>>>>
>>>> /* Routine kind cannot change for an existing pg_proc OID. */
>>>> Assert(procForm->prokind != PROKIND_AGGREGATE);
>>>>
>>>> The comment says we can't change OID, but the assert checks it's
>>>> not an
>>>> aggregate functions. Isn't that misleading?
>>> Maybe it would be cleaner to mention additionally, that "aggregates
>>> were
>>> already rejected on the pre-lock tuple"? I actually think, that comment
>>> is indeed stating a helpful invariant to explain why we are concurrency
>>> save here.
>> I don't follow. The comment says we can't change OID of an existing
>> procedure. OK, sure. But the assert checks the procedure is not an
>> aggregate function. How is that comment an accurate description of the
>> purpose of the assert?
> it explains the invariant, why we can rely on our earlier pre-lock
> tuple check. To me that seemed to be a relevant enough assumption
> about the code to make it explicit in a comment.
>> [...]
>>>> 13) I think the main question is whether parse-analyze is the right
>>>> place to handle this. I don't know. I assume one of the reasons for
>>>> doing that is to get an error when defining a view, or when
>>>> altering an
>>>> object - e.g. like when dropping a function used by a view. Which
>>>> seems
>>>> reasonable, people would not like views silently broken by DDL.
>>>>
>>>> But it seems to be this also leads to a lot of code duplication,
>>>> because
>>>> the parse analysis now has to "reimplement" a lot of the stuff already
>>>> done in later stages, after parse analyze. For example, we have the
>>>> root->fkey_list thing, but that's not available yet.
>>>>
>>>> There's probably more such information - like innerrel_is_unique,
>>>> rel_is_distinct_for, relation_has_unique_index_for etc.
>>>>
>>>> Maybe it's not worth it? What if we did this in the planner
>>>> instead? How
>>>> much simpler would it get? My intuition is it'd get much smaller, but
>>>> maybe I'm wrong.
>>>>
>>>> It'd probably mean it's not necessary to expand views during parse,
>>>> which was one of the problems mentioned at the beginning of this
>>>> thread.
>>>>
>>>> I suppose we'd need to keep additional information in the plan to know
>>>> which joins to check, etc.
>>> If we want to use this for correctness and for proofs, we can't do it
>>> plan time. We have DDL-writes to store proofs. In it's nature this is a
>>> compile time feature.
>>>
>> Is that actually true? If we check the correctness later in the planner,
>> we'd still get a failure. Why couldn't that verify all the proofs, just
>> like the parse-analyze? We may need to retain more information, ofc.
>>
>>> Even if we don't include all of that in the first patch, this places
>>> very severe limitations like the DDL issue, which would be just tooo
>>> limiting to get to as an end place. I do think it's more reasonable how
>>> to cut this up into more digestible pieces.
>>>
>> I'm not sure what "DDL issue" is, sorry :-(
>>
>> I may be missing something, but the main difference in behavior seems to
>> be for views - the current patch verifies the proofs when creating the
>> view / altering objects, and rejects those. And AFAICS after moving it
>> to the planner, that would not be the case anymore.
>>
>> But for regular ad hoc queries there's not much difference, no? You'd
>> get a failure, no matter what.
>
> With DDL-issue I was eluding to a DDL command that attaches a query to
> some object. Views, sql functions and policies all do that. I don't
> see us doing that work planning time. Theoretically we could try to
> use a new planner hook for that, to call the planner with an extra
> struct element telling it about increased locking arrangements without
> the intend to ever execute a query and abort after the proof.
>
> However I do think this introduces more future complexity by
> entangling separate concerns in the same code path, and I am not sure
> we are doing ourselves a favor with this, even if we would save a hand
> full of lines. I am not convinced I want to tackle that complexity on
> top of this already non-trivial patch.
>
> I intend to try to separate the DDL handling case out into it's own
> patch of the patch series. While in lines of code is not that massive,
> reasoning about those two individually is indeed simpler. Even just
> getting to locking for the DDL-case right, isn't trivial.
>
> I hope to get to that by the end of the now starting week.
>
>>> Even though the planner is messy, I feel more at home there than
>>> here in
>>> the parser. I could see a world were we clean up some of those out of
>>> the planner to make them available earlier some time in parsing. We
>>> could push those variables forward to the planner to avoid redoing the
>>> work. Each of these steps would need a careful performance check and I
>>> am not sure how the real stepping stones would look like.
>>>
>> I'm skeptical about moving this stuff to an earlier phase (so that the
>> parse can see it). You can try, but it probably requires moving a lot of
>> other stuff too, some of which may be expensive.
>
> I have a high level general response and one tailored to this patch.
> I'll start with this particular patch: For this patch I am mostly
> concerned with not doing complex work twice: Once in the parser AND
> once in the optimizer. And the below general thoughts are not easily
> actionable.
>
> More generally:
>
> Your skepticism is well placed. Every change there would warrant
> benchmarking. I am just not completely convinced the planner is super
> optimal in the way it works. I suspect a lot of code there has not
> been optimized, because it's hard to wrap your head around it, that it
> doesn't feel like an easy gain anymore.
>
> While 1:1 pulling stuff out of the planner almost surely gives mostly
> performance regressions, a clean architecture allowing more simple,
> isolated performance improvements sounds beneficial, too. And I don't
> want to open this can of worms right now.
>
> I just recalled the time when Andres made the storage pluggable by
> introducing a layer of pointers everywhere. The new storage interface
> ended up being faster than the old.
> This is not storage and I am not Andres. I just wanted to share
> precedent, that a clear architecture with optimization disadvantages
> is not necessarily always slower.
>
>> regards
>>
> Regards
> Arne
>
Attachments:
[application/gzip] v11-0004-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/2-v11-0004-Add-information_schema.view_constraint_usage.patch.gz)
download
[application/gzip] v11-0002-Serialize-concurrent-routine-definition-changes.patch.gz (1.7K, ../../[email protected]/3-v11-0002-Serialize-concurrent-routine-definition-changes.patch.gz)
download
[application/gzip] v11-0001-Add-FOR-KEY-join-clause-and-parse-time-proof.patch.gz (84.4K, ../../[email protected]/4-v11-0001-Add-FOR-KEY-join-clause-and-parse-time-proof.patch.gz)
download
[application/gzip] v11-0003-Record-and-revalidate-FOR-KEY-proof-dependencies.patch.gz (113.8K, ../../[email protected]/5-v11-0003-Record-and-revalidate-FOR-KEY-proof-dependencies.patch.gz)
download
[application/gzip] v11-0005-Add-psql-tab-completion-for-FOR-KEY-joins.patch.gz (11.5K, ../../[email protected]/6-v11-0005-Add-psql-tab-completion-for-FOR-KEY-joins.patch.gz)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-25 11:15 Henson Choi <[email protected]>
parent: Arne Roland <[email protected]>
1 sibling, 1 reply; 26+ messages in thread
From: Henson Choi @ 2026-06-25 11:15 UTC (permalink / raw)
To: pgsql-hackers; +Cc: Arne Roland <[email protected]>; Tomas Vondra <[email protected]>; Joel Jacobson <[email protected]>; Laurenz Albe <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
Hi hackers,
Thank you for this interesting proposal. I have two questions that touch on
what I see as a fundamental tension in the design.
On SQL's evolution from How to What
As Codd put it, "The user of a relational system should not need to
know how the system stores and accesses data." Key Join, I would
argue, pulls in the opposite direction.
SQL has historically evolved away from procedural "how" toward declarative
"what" — users describe the result they want, and the optimizer figures out
how to get there. Foreign key constraints are a good example: once declared
in the schema, the optimizer can already exploit them for join elimination,
cardinality estimation, and so on. Key Join asks users to explicitly
annotate their queries with FK traversal semantics. Isn't that a step back
toward "how"?
Tomas Vondra raised a directly relevant point in his review:
> I'm interested in this patch because there seems to be a possible
> overlap with the starjoin planning (in that maybe we could try
> reusing some of the derived information for that).
And later:
> Plus, I don't want to make that patch dependent on people using
> new syntax. If that can give us additional information, that would
> be a different thing.
His second remark seems to carry an implicit question: if the optimizer
can already see the FK constraints, why does the user need to annotate
the query at all? Wouldn't automatic starjoin-style optimization be more
consistent with SQL's declarative philosophy? This reading is also
supported by his point 13, where he explicitly asks whether the planner
— rather than parse-analyze — might be the more appropriate place to
handle this, and notes that moving it there could substantially reduce
the code footprint.
On hints vs. syntax
Traditionally, when users have needed to pass extra information to the
optimizer — information the engine couldn't derive on its own — the
community has handled this through hints. Non-standard, yes, but they
leave the core syntax untouched and stay firmly in the optimizer's
domain. Key Join introduces this information as first-class syntax with
compile-time enforcement. What are the concrete advantages and
disadvantages of that choice compared to a hint-based approach?
Specifically:
The main advertised advantage is compile-time correctness enforcement
— catching fan-out bugs at parse time rather than silently producing
wrong results. Is that benefit sufficient to justify introducing "how"
semantics into SQL syntax proper? A hint could achieve the
optimizer-side benefits (starjoin planning, cardinality guidance)
without touching the grammar. What does the syntax approach give us
that a hint cannot?
I recognize that compile-time enforcement is genuinely valuable, and
that hints cannot be standardized through WG3. But I'd like to
understand how the authors weigh those tradeoffs, especially given
Tomas's observation that the planner already has access to FK
information and could potentially derive much of this automatically.
Best regards,
Henson
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-25 13:35 Arne Roland <[email protected]>
parent: Henson Choi <[email protected]>
0 siblings, 1 reply; 26+ messages in thread
From: Arne Roland @ 2026-06-25 13:35 UTC (permalink / raw)
To: [email protected]; pgsql-hackers; +Cc: Tomas Vondra <[email protected]>; Joel Jacobson <[email protected]>; Laurenz Albe <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
Hi Henson,
thank you for getting involved!
On 2026-06-25 1:15 PM, Henson Choi wrote:
> Hi hackers,
>
> Thank you for this interesting proposal. I have two questions that
> touch on what I see as a fundamental tension in the design.
>
> On SQL's evolution from How to What
>
> As Codd put it, "The user of a relational system should not need to
> know how the system stores and accesses data." Key Join, I would
> argue, pulls in the opposite direction.
>
> SQL has historically evolved away from procedural "how" toward
> declarative "what" — users describe the result they want, and the
> optimizer figures out how to get there. Foreign key constraints are a
> good example: once declared in the schema, the optimizer can already
> exploit them for join elimination, cardinality estimation, and so on.
> Key Join asks users to explicitly annotate their queries with FK
> traversal semantics. Isn't that a step back toward "how"?
I am 100% with you on that Codd quote. I love the declarative nature of
SQL and invited developers with imperative paradigms to change to
declarative ones. I'd argue that we describe what we want. Let me quote
our intent posted in the opening message of this thread:
> We propose a new JOIN syntax that makes it easy to determine locally
> that the immediate join result, before any further steps, just enriches
> the referencing side with information from the referenced side, with
> null-extension for OUTER JOINs. It conveys the author's intent, makes
> the referencing side visually clear, and is enforced at compile time
> against the schema.
I'd argue the intent is the enrichment, and which side is the one being
referenced. It has been my experience over the years that developers
have it. We are offering a way to express it. By its nature this patch
series adds something closer to an assertion. If anything that makes a
key join more declarative than an ordinary equijoin: We declare an
intent, and the schema settles the rest. This is expressed in more
detail in section 8.3 in our key_joins.pdf
[https://www.postgresql.org/message-id/00c30670-64e1-4c30-a349-784426d333df%40app.fastmail.com]
or in the web demo under https://keyjoin.org/#sec8.4. (The numbering is
slightly off because of versioning issues.) The proposed patch does not
alter how the planner or optimizer work in the slightest. Please help me
understand how we are taking a step toward "how"?
> Tomas Vondra raised a directly relevant point in his review:
>
> > I'm interested in this patch because there seems to be a possible
> > overlap with the starjoin planning (in that maybe we could try
> > reusing some of the derived information for that).
I do think that we want to use the same underlying proving
infrastructure. That comment is not about the semantics of our SQL
language or our interface with the code, but about reusing and sharing
logic, that we can get into the source code of our beloved project.
> And later:
>
> > Plus, I don't want to make that patch dependent on people using
> > new syntax. If that can give us additional information, that would
> > be a different thing.
>
> His second remark seems to carry an implicit question: if the optimizer
> can already see the FK constraints, why does the user need to annotate
> the query at all? Wouldn't automatic starjoin-style optimization be more
> consistent with SQL's declarative philosophy?
If you want to do optimization in the planner, you totally can. I think
we need more optimizer improvements. As the attempts in the prior thread
about the optimizations of star joins did that. Tomas just noted that he
is interested in using the underlying proof architecture for that.
This feature we are working on here is NOT a performance feature, it's
*only* a correctness feature. We as authors have different backgrounds
and different views. However I am very confident that we are in
agreement, this is solely a correctness feature.
I am very open to discuss and reason about the potential value of using
the infrastructure for improvements, because I have an interest in those
too. I do think that's currently beyond the scope of this thread,
because of the already fairly involved complexity of this patch.
Informally this feature is meant for query writers to say "if you can't
prove the referential correctness of this feature, please don't go ahead
and give me an error instead". This error is not an accidental artifact,
it sits at the core of this feature. Doing this compile time is very
helpful to build correct systems. We need to convey the intent of the
existence of a referential constraint in order for it to be proven.
Our current syntax also makes it much easier to review queries. For an
example, I'd refer you to our example in section 8.9 of our document,
which can be read here in the thread at the attached key_joins.pdf or
our online web demo at https://keyjoin.org/#sec8.10. The numbering is
slightly off because of versioning issues.
> This reading is also
> supported by his point 13, where he explicitly asks whether the planner
> — rather than parse-analyze — might be the more appropriate place to
> handle this, and notes that moving it there could substantially reduce
> the code footprint.
I have tried Tomas suggestion and found no substantial reduction in
complexity. One issue here is that we have different inputs, since we
are at parsing and not planning stage. Another that we have vastly
different outputs, since we need not only to know, that we are unique,
but exactly how, including the knowledge of the unique
constraints/indexes to record the pg_depend for stored objects with
attached key joins.
Despite us logically doing almost the same thing in the three helper
functions as the optimizer code does, for code architectural reasons,
the benefit of trying to use those functions seems questionable to me.
Small side note for completeness sake: We skip a few cases like
uniqueness of aggregates without group by clause, because in those we
know, that there can't be a referential constraint. We still encode the
uniqueness of that, but not in that function.
> On hints vs. syntax
>
> Traditionally, when users have needed to pass extra information to the
> optimizer — information the engine couldn't derive on its own — the
> community has handled this through hints. Non-standard, yes, but they
> leave the core syntax untouched and stay firmly in the optimizer's
> domain. Key Join introduces this information as first-class syntax with
> compile-time enforcement. What are the concrete advantages and
> disadvantages of that choice compared to a hint-based approach?
This patch series doesn't touch the optimizer at all nor should it. If
something like this gets committed, we will be able to harness some of
the underlying architecture for optimization purposes.
The reason why our intended correctness guarantees can't be achieved
through works in the optimizer is the proper enforcement of tracking the
correctness of the referential guarantees in catalog objects. Allow me
to quote from my earlier answer:
> With DDL-issue I was alluding to a DDL command that attaches a query
to some object. Views, sql functions and policies all do that.
> I don't see us doing that work planning time. Theoretically we could
try to use a new planner hook for that, to call the planner with an
> extra struct element telling it about increased locking arrangements
without the intent to ever execute a query and abort after the proof.
Structurally I don't really see a sane way to make this feature a
planner stage feature at all.
> Specifically:
>
> The main advertised advantage is compile-time correctness enforcement
> — catching fan-out bugs at parse time rather than silently producing
> wrong results. Is that benefit sufficient to justify introducing "how"
> semantics into SQL syntax proper? A hint could achieve the
> optimizer-side benefits (starjoin planning, cardinality guidance)
> without touching the grammar. What does the syntax approach give us
> that a hint cannot?
>
> I recognize that compile-time enforcement is genuinely valuable, and
> that hints cannot be standardized through WG3. But I'd like to
> understand how the authors weigh those tradeoffs, especially given
> Tomas's observation that the planner already has access to FK
> information and could potentially derive much of this automatically.
>
> Best regards,
> Henson
Our correctness guarantee is very different from a hint. A hint is
telling the optimizer "try to do this thing, if you can". Our
correctness guarantee is as of now not giving anything to the optimizer
and telling the parser "give me an error, if you can't prove my
assumptions". I struggle to see the overlap between the two.
Since you specifically raised the fan-out problem and wanted an opinion
from an author, I will share mine. Here I can't claim to speak for all
authors.
My opinion is that the fan-out problem alone is more than enough to
warrant a proper SQL syntax expansion. It has been a serious bug in
multiple codebases I have worked with.
Some of our analysis suggested to me, that preventing the fan out bug
might be possible with less complex logic. However this does not only
prevent the fan out problem, but a myriad of issues, a lot of which I
have seen in production systems too.
You can read more about our design rationale in chapter 8 in the
attached key_joins.pdf or online at https://keyjoin.org/#sec8. For an
understanding of the usefulness of the feature I suggest sections 7.2 to
7.6 again in the key_joins.pdf or online at https://keyjoin.org/#sec7.2.
Best regards
Arne
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-25 14:09 Henson Choi <[email protected]>
parent: Arne Roland <[email protected]>
0 siblings, 0 replies; 26+ messages in thread
From: Henson Choi @ 2026-06-25 14:09 UTC (permalink / raw)
To: Arne Roland <[email protected]>; +Cc: pgsql-hackers; Tomas Vondra <[email protected]>; Joel Jacobson <[email protected]>; Laurenz Albe <[email protected]>; Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
Hi Arne,
Thank you for the thorough and thoughtful response. As you suggested:
> "You can read more about our design rationale in chapter 8 in the
> attached key_joins.pdf or online at https://keyjoin.org/#sec8. For an
> understanding of the usefulness of the feature I suggest sections 7.2
> to 7.6 again in the key_joins.pdf or online at https://keyjoin.org/#sec7.2
."
I will read through these sections carefully and come back with further
comments.
I genuinely admire the ambition of bringing this to WG3. Pushing a
Change Proposal to the SQL standard is no small undertaking, and I
respect the effort behind it. I hope the Stockholm meeting goes well.
On a personal note — I work on PostgreSQL upstream contributions myself,
and I have long been interested in the SQL standard as a living
document rather than a fixed reference. If I ever reach the point of
wanting to raise a small question or propose a correction based on
something I encounter in implementation work, would it be alright to
reach out to you?
Best regards,
Henson
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-06-27 23:05 Arne Roland <[email protected]>
parent: Arne Roland <[email protected]>
1 sibling, 1 reply; 26+ messages in thread
From: Arne Roland @ 2026-06-27 23:05 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; Joel Jacobson <[email protected]>; Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
Hello together,
the main reason I'm re-positing is to fix a psql issue with the test tty
layout, to keep CF bot happy. The code itself wasn't altered there.
I also did some rewording in some comments and altered the way how to
lock against concurrent inheritance schema changes in the 0003 patch.
Regards
Arne
Attachments:
[application/gzip] v12-0002-Serialize-concurrent-routine-definition-changes.patch.gz (1.7K, ../../[email protected]/2-v12-0002-Serialize-concurrent-routine-definition-changes.patch.gz)
download
[application/gzip] v12-0003-Record-and-revalidate-FOR-KEY-proof-dependencies.patch.gz (115.8K, ../../[email protected]/3-v12-0003-Record-and-revalidate-FOR-KEY-proof-dependencies.patch.gz)
download
[application/gzip] v12-0001-Add-FOR-KEY-join-clause-and-parse-time-proof.patch.gz (84.2K, ../../[email protected]/4-v12-0001-Add-FOR-KEY-join-clause-and-parse-time-proof.patch.gz)
download
[application/gzip] v12-0004-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/5-v12-0004-Add-information_schema.view_constraint_usage.patch.gz)
download
[application/gzip] v12-0005-Add-psql-tab-completion-for-FOR-KEY-joins.patch.gz (11.6K, ../../[email protected]/6-v12-0005-Add-psql-tab-completion-for-FOR-KEY-joins.patch.gz)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
* Re: Key joins
@ 2026-07-08 00:19 Arne Roland <[email protected]>
parent: Arne Roland <[email protected]>
0 siblings, 0 replies; 26+ messages in thread
From: Arne Roland @ 2026-07-08 00:19 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; Joel Jacobson <[email protected]>; Laurenz Albe <[email protected]>; pgsql-hackers; +Cc: Anders Granlund <[email protected]>; Andreas Karlsson <[email protected]>; Vik Fearing <[email protected]>
Hi,
the attached patch set is my attempt to break it up in a granular way. I
will think about this further, but attached is my current patch, since
it seems much easier to read.
The difference to before is that the base commit is further broken up
into a series of it's own:
1. Only prove FOR KEY joins between two base tables
2. Mechanics for advanced error messages
3. Derived tables
4. GROUP BY and DISTINCT
5. FILTER (WHERE ...)
6. Tracking of referenced and referencing filter clauses
The later commits have only minor comment adjustments. The series should
be easier to read now, since the individual steps with very different
concerns are added one at a time. Please let me know, what you think.
Regards
Arne
On 2026-06-28 1:05 AM, Arne Roland wrote:
> Hello together,
>
> the main reason I'm re-positing is to fix a psql issue with the test
> tty layout, to keep CF bot happy. The code itself wasn't altered there.
>
> I also did some rewording in some comments and altered the way how to
> lock against concurrent inheritance schema changes in the 0003 patch.
>
> Regards
> Arne
>
Attachments:
[application/gzip] v13-0010-Add-psql-tab-completion-for-FOR-KEY-joins.patch.gz (11.5K, ../../[email protected]/3-v13-0010-Add-psql-tab-completion-for-FOR-KEY-joins.patch.gz)
download
[application/gzip] v13-0002-Add-error-details-to-FOR-KEY-join-rejections.patch.gz (7.9K, ../../[email protected]/4-v13-0002-Add-error-details-to-FOR-KEY-join-rejections.patch.gz)
download
[application/gzip] v13-0004-Derive-key-join-proof-facts-from-GROUP-BY-and-DI.patch.gz (17.0K, ../../[email protected]/5-v13-0004-Derive-key-join-proof-facts-from-GROUP-BY-and-DI.patch.gz)
download
[application/gzip] v13-0005-Add-a-join-local-FILTER-WHERE-.-clause.patch.gz (7.0K, ../../[email protected]/6-v13-0005-Add-a-join-local-FILTER-WHERE-.-clause.patch.gz)
download
[application/gzip] v13-0008-Record-and-revalidate-FOR-KEY-proof-dependencies.patch.gz (79.1K, ../../[email protected]/7-v13-0008-Record-and-revalidate-FOR-KEY-proof-dependencies.patch.gz)
download
[application/gzip] v13-0006-Prove-FOR-KEY-joins-whose-referenced-input-is-fi.patch.gz (40.4K, ../../[email protected]/8-v13-0006-Prove-FOR-KEY-joins-whose-referenced-input-is-fi.patch.gz)
download
[application/gzip] v13-0009-Add-information_schema.view_constraint_usage.patch.gz (2.9K, ../../[email protected]/9-v13-0009-Add-information_schema.view_constraint_usage.patch.gz)
download
[application/gzip] v13-0007-Serialize-concurrent-routine-definition-changes.patch.gz (1.7K, ../../[email protected]/10-v13-0007-Serialize-concurrent-routine-definition-changes.patch.gz)
download
[application/gzip] v13-0003-Prove-FOR-KEY-joins-over-derived-inputs.patch.gz (38.8K, ../../[email protected]/11-v13-0003-Prove-FOR-KEY-joins-over-derived-inputs.patch.gz)
download
[application/gzip] v13-0001-Add-FOR-KEY-join-clause-and-parse-time-proof.patch.gz (56.2K, ../../[email protected]/12-v13-0001-Add-FOR-KEY-join-clause-and-parse-time-proof.patch.gz)
download
^ permalink raw reply [nested|flat] 26+ messages in thread
end of thread, other threads:[~2026-07-08 00:19 UTC | newest]
Thread overview: 26+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-05-28 18:47 Key joins Joel Jacobson <[email protected]>
2026-05-28 22:13 ` Joel Jacobson <[email protected]>
2026-05-29 05:08 ` Joel Jacobson <[email protected]>
2026-05-29 07:45 ` Joel Jacobson <[email protected]>
2026-05-29 08:54 ` Joel Jacobson <[email protected]>
2026-05-29 10:50 ` Joel Jacobson <[email protected]>
2026-05-29 12:04 ` Matthias van de Meent <[email protected]>
2026-05-29 12:51 ` Laurenz Albe <[email protected]>
2026-05-29 13:21 ` Joel Jacobson <[email protected]>
2026-05-29 16:20 ` Laurenz Albe <[email protected]>
2026-05-31 08:05 ` Joel Jacobson <[email protected]>
2026-05-31 14:40 ` Joel Jacobson <[email protected]>
2026-06-01 20:06 ` Joel Jacobson <[email protected]>
2026-06-01 20:36 ` Joel Jacobson <[email protected]>
2026-06-04 16:02 ` Joel Jacobson <[email protected]>
2026-06-04 22:41 ` Arne Roland <[email protected]>
2026-06-11 21:02 ` Tomas Vondra <[email protected]>
2026-06-12 00:20 ` Arne Roland <[email protected]>
2026-06-12 17:26 ` Tomas Vondra <[email protected]>
2026-06-14 18:17 ` Arne Roland <[email protected]>
2026-06-23 15:53 ` Arne Roland <[email protected]>
2026-06-25 11:15 ` Henson Choi <[email protected]>
2026-06-25 13:35 ` Arne Roland <[email protected]>
2026-06-25 14:09 ` Henson Choi <[email protected]>
2026-06-27 23:05 ` Arne Roland <[email protected]>
2026-07-08 00:19 ` Arne Roland <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox