Key joins

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?]
(/messages/by-id/86b9ec78-925c-1935-bc9d-6bad4ceb1f40@illuminatedcomputing.com)
[2] [RE: Parallel INSERT SELECT take 2]
(/messages/by-id/TY4PR01MB17718A4DE63020A9EA5E9CB6594382@TY4PR01MB17718.jpnprd01.prod.outlook.com)

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

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

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

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

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

On Thu, 28 May 2026 at 20:48, Joel Jacobson <joel@compiler.org> 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]https://keyjoin.org/#sec8.4

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

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

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]https://peter.eisentraut.org/blog/2023/04/04/sql-2023-is-finished-here-is-whats-new.

[1]: https://peter.eisentraut.org/blog/2023/04/04/sql-2023-is-finished-here-is-whats-new

/Joel

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

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

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