public inbox for [email protected]
help / color / mirror / Atom feedFrom: Joel Jacobson <[email protected]>
To: pgsql-hackers <[email protected]>
Cc: Arne Roland <[email protected]>
Cc: Anders Granlund <[email protected]>
Cc: Andreas Karlsson <[email protected]>
Cc: Vik Fearing <[email protected]>
Subject: Key joins
Date: Thu, 28 May 2026 20:47:50 +0200
Message-ID: <[email protected]> (raw)
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
view thread (26+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: Key joins
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox