ANSI SQL proposal: SELECT DISTINCT ON (... ORDER BY ...) and UNION DISTINCT ON (... ORDER BY ...)
Hi Vik
Finally had time to put this SQL Standard Propoasl together.
Please take a quick look and tell me what is missing or wrong and what
the next steps should be.
For example, should I mention somewhere that PostgreSQL supports a
partial version of the SELECT DISTINCT ON () ?
Regarding PGQ in PostgreSQL, this should allow a plain SQL target for
arbitrary length graph queries and at least some types of path finding
queries.
I hope to have some working PoC code for PostgreSQL within the next
few days so I can share actual working versions of both sample
recursive graph queries and the "overlay of read-only table" queries I
talked to you about.
-----
Hannu
Attachments:
xxx000-distinct-on-clause.mdtext/markdown; charset=US-ASCII; name=xxx000-distinct-on-clause.mdDownload
Here is a patch set implementing this
On Sat, Aug 1, 2026 at 3:08 PM Hannu Krosing <hannuk@google.com> wrote:
Show quoted text
Hi Vik
Finally had time to put this SQL Standard Propoasl together.
Please take a quick look and tell me what is missing or wrong and what
the next steps should be.For example, should I mention somewhere that PostgreSQL supports a
partial version of the SELECT DISTINCT ON () ?Regarding PGQ in PostgreSQL, this should allow a plain SQL target for
arbitrary length graph queries and at least some types of path finding
queries.I hope to have some working PoC code for PostgreSQL within the next
few days so I can share actual working versions of both sample
recursive graph queries and the "overlay of read-only table" queries I
talked to you about.-----
Hannu
Attachments:
t253274_20001-Refactor-set-operation-group-clauses-to-decouple-fro.patchapplication/x-patch; name=0001-Refactor-set-operation-group-clauses-to-decouple-fro.patchDownload+80-68
0003-Support-UNION-DISTINCT-ON-for-non-recursive-set-oper.patchapplication/x-patch; name=0003-Support-UNION-DISTINCT-ON-for-non-recursive-set-oper.patchDownload+268-53
0004-Support-dynamic-pruning-in-recursive-UNION-DISTINCT-.patchapplication/x-patch; name=0004-Support-dynamic-pruning-in-recursive-UNION-DISTINCT-.patchDownload+275-6
0002-Support-inline-ORDER-BY-in-DISTINCT-ON-for-SELECT-an.patchapplication/x-patch; name=0002-Support-inline-ORDER-BY-in-DISTINCT-ON-for-SELECT-an.patchDownload+459-31
Rebased
Attachments:
t253274_3v2-0001-Refactor-set-operation-group-clauses-to-decouple-fro.patchapplication/x-patch; name=v2-0001-Refactor-set-operation-group-clauses-to-decouple-fro.patchDownload+80-68
v2-0004-Support-dynamic-pruning-in-recursive-UNION-DISTINCT-.patchapplication/x-patch; name=v2-0004-Support-dynamic-pruning-in-recursive-UNION-DISTINCT-.patchDownload+275-6
v2-0003-Support-UNION-DISTINCT-ON-for-non-recursive-set-oper.patchapplication/x-patch; name=v2-0003-Support-UNION-DISTINCT-ON-for-non-recursive-set-oper.patchDownload+268-52
v2-0002-Support-inline-ORDER-BY-in-DISTINCT-ON-for-SELECT-an.patchapplication/x-patch; name=v2-0002-Support-inline-ORDER-BY-in-DISTINCT-ON-for-SELECT-an.patchDownload+459-31
On 01/08/2026 15:08, Hannu Krosing wrote:
Hi Vik
Finally had time to put this SQL Standard Propoasl together.
Please take a quick look and tell me what is missing or wrong and what
the next steps should be.
SQL doesn't actually need DISTINCT ON. Two syntaxes already provide it:
SELECT user_id, status, updated_at,
ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY updated_at
DESC) as rn
FROM user_statuses
QUALIFY rn = 1
SELECT user_id, status, updated_at
FROM user_statuses
ORDER BY updated_at DESC
FETCH FIRST ALL PARTITIONS BY user_id, 1 ROW ONLY
However, putting the ordering inside the DISTINCT ON is a big
improvement for postgres, imo.
SELECT DISTINCT ON (user_id ORDER BY updated_at DESC)
user_id, status, updated_at
FROM user_statuses
ORDER BY status
We can't get rid of the old way of doing it, but that shouldn't prevent
us from having the new version.
I don't understand what the use case for UNION DISTINCT ON is. Could you
please provide one?
--
Vik Fearing
On Thu, Sep 17, 2026 at 2:43 PM Vik Fearing <vik@postgresfriends.org> wrote:
I don't understand what the use case for UNION DISTINCT ON is. Could you
please provide one?
Here it is:
I have put it here in HTML format for clarity for human readers, and also
to see what the automatically generated plaintext format looks like when I
check it on mailing list and download it back from the mailing list
archives.
1. The Canonical Sample: Shortest Path Search (WITH RECURSIVE)
The primary motivating use case for UNION DISTINCT ON (...) is
breadth-first search / shortest path pathfinding (such as in Dijkstra's
algorithm or grid traversal like Advent of Code Day 12).
Standard SQL recursion with UNION ALL and CYCLE only performs path-local
cycle detection (it prevents visiting a node already in the current descent
path). It cannot prevent exploring sub-optimal paths if another branch
already reached that node faster, resulting in a combinatorial explosion of
paths.
With UNION DISTINCT ON (r, c ORDER BY len), earlier or shorter paths to a
given key replace or prune longer paths:
Schema & Setup:
CREATE TABLE day12_test (
rownr SERIAL PRIMARY KEY,
data TEXT
);
INSERT INTO day12_test (data) VALUES
('Sabqponm'),
('abcryxxl'),
('accszExk'),
('acctuvwj'),
('abdefghi');
CREATE TABLE day12_pointmap AS
SELECT rownr AS r
, c::int
, h
, (CASE h WHEN 'S' THEN 0 WHEN 'E' THEN 25 ELSE ascii(h) - 97 END) AS
height
FROM day12_test
, unnest(regexp_split_to_array(data, '')) WITH ORDINALITY u(h, c);
CREATE UNIQUE INDEX day12_pointmap_undx ON day12_pointmap(r, c) INCLUDE (h,
height);
Query Using UNION DISTINCT ON:
WITH RECURSIVE search_path AS (
-- Non-recursive term: Start position
SELECT 0 AS len, *
FROM day12_pointmap
WHERE h = 'S'
-- Deduplicates coordinates across all paths, keeping the minimum step
length:
UNION DISTINCT ON (r, c ORDER BY len)
-- Recursive term: Step to adjacent qualifying coordinates
SELECT len + 1 AS len
, p.r, p.c, p.h
, p.height
FROM day12_pointmap p
JOIN search_path sp
ON (p.c, p.r) = ANY (ARRAY[(sp.c, sp.r - 1), (sp.c, sp.r + 1),
(sp.c - 1, sp.r), (sp.c + 1, sp.r)])
AND p.height <= sp.height + 1
)
SELECT *
FROM search_path;
------------------------------
Show quoted text
--
Vik Fearing
At first glance it looks very much like what DuckDB does with USING
KEY syntax they have described here
https://www.cidrdb.org/cidr2023/papers/p14-hirn.pdf
I learned about DuckDB USING KEY just 2 days ago from
https://lnkd.in/p/ebCwa9Wk
-----
Hannu
Subject: [PATCH v3 0/5] Support UNION DISTINCT ON and inline DISTINCT
ON (... ORDER BY ...)
Hi hackers,
Attached is v3 of the patch series introducing:
1. Inline ORDER BY inside DISTINCT ON for SELECT queries:
SELECT DISTINCT ON (a ORDER BY b DESC) a, b, c FROM t ORDER BY c;
Along with HashAggregate support for DISTINCT ON tie-breaking via
ReplaceTupleHashEntryIfBetter().
2. UNION DISTINCT ON (expr [, ...] [ORDER BY sort_expr [, ...]]) for
non-recursive set operations:
SELECT a, b FROM t1
UNION DISTINCT ON (a ORDER BY b DESC)
SELECT a, b FROM t2;
3. Dynamic state-space pruning in recursive CTEs (WITH RECURSIVE) using
UNION DISTINCT ON (key ORDER BY cost), enabling Bellman-Ford /
shortest-path and optimal state-space search directly in SQL without
infinite loops or post-hoc filtering.
Changes in v3:
- Fixed tuple extraction in ReplaceTupleHashEntryIfBetter() to use a
dedicated TupleTableSlot and slot_getattr() instead of
minimal_tuple_getattr(), ensuring safe handling of pass-by-reference /
varlena attributes and arbitrary targetlist column positions.
- Evaluated sort comparators in table->tempcxt with per-comparison memory
context resets and added in-place MinimalTuple overwrite when the
replacement tuple fits in the existing allocation.
- Extracted shared ExecPrepareTupleSortSupport() helper and properly
initialized ssup_cxt in both HashAggregate and RecursiveUnion.
- Replaced RecursiveUnion result_table Tuplestore materialization with
direct TupleHashIterator scanning, added seed-phase deduplication before
populating working_table, and added intra-wave obsolete-tuple pruning.
- Replaced pre-parse col_in_distinct_on() inspection with standard
targetlist resolution via transformDistinctOnClause() and post-type-
resolution build_distinct_sort_clause().
- Normalized SetOperationStmt groupClauses and sortClauses so
tleSortGroupRef == resno holds uniformly across set-operation planning,
and enabled MergeAppend + Unique paths for UNION DISTINCT ON with inline
ORDER BY.
- Added support for nested / multi-way UNION DISTINCT ON set-operation
trees, guarded Append child flattening when groupClauses/sortClauses
differ, and extended subquery WHERE pushdown safety checks to inspect
nested set-operation trees recursively.
- Added EXPLAIN "Sort Key:" output for HashAggregate and RecursiveUnion
when tie-breaker sort columns are active, and added full pg_get_viewdef()
deparsing in ruleutils.c for both SELECT DISTINCT ON (... ORDER BY ...)
and UNION DISTINCT ON (... [ORDER BY ...]).
- Expanded regression test coverage in select_distinct_on.sql and
union.sql.
Hannu Krosing (5):
Refactor set operation group clauses to decouple from targetlist
positions
Support inline ORDER BY in DISTINCT ON for SELECT and enable HashAgg
Support UNION DISTINCT ON for non-recursive set operations
Support dynamic pruning in recursive UNION DISTINCT ON
Fix bugs, security issues, and optimizations in DISTINCT ON and UNION
DISTINCT ON
doc/src/sgml/ref/select.sgml | 47 ++-
src/backend/commands/explain.c | 25 +-
src/backend/executor/execGrouping.c | 136 ++++++
src/backend/executor/nodeAgg.c | 151 +++++--
src/backend/executor/nodeRecursiveunion.c | 234 ++++++++++-
src/backend/nodes/nodeFuncs.c | 2 +
src/backend/optimizer/path/allpaths.c | 62 ++-
src/backend/optimizer/path/equivclass.c | 45 +-
src/backend/optimizer/plan/createplan.c | 88 ++++
src/backend/optimizer/plan/planner.c | 239 +++++++----
src/backend/optimizer/prep/prepunion.c | 91 ++--
src/backend/optimizer/util/pathnode.c | 7 +-
src/backend/parser/analyze.c | 204 +++++++--
src/backend/parser/gram.y | 45 +-
src/backend/parser/parse_clause.c | 34 +-
src/backend/parser/parse_cte.c | 28 ++
src/backend/rewrite/rewriteSearchCycle.c | 27 +-
src/backend/utils/adt/ruleutils.c | 34 +-
src/include/executor/executor.h | 11 +
src/include/executor/nodeAgg.h | 2 +
src/include/nodes/execnodes.h | 6 +
src/include/nodes/parsenodes.h | 4 +
src/include/nodes/pathnodes.h | 2 +
src/include/nodes/plannodes.h | 14 +
src/include/optimizer/pathnode.h | 4 +-
src/include/parser/parse_clause.h | 3 +-
.../regress/expected/select_distinct_on.out | 239 +++++++++++
src/test/regress/expected/union.out | 390 ++++++++++++++++++
src/test/regress/sql/select_distinct_on.sql | 128 ++++++
src/test/regress/sql/union.sql | 202 +++++++++
30 files changed, 2251 insertions(+), 253 deletions(-)
Show quoted text
On Fri, Sep 18, 2026 at 7:01 PM Hannu Krosing <hannuk@google.com> wrote:
At first glance it looks very much like what DuckDB does with USING
KEY syntax they have described here
https://www.cidrdb.org/cidr2023/papers/p14-hirn.pdfI learned about DuckDB USING KEY just 2 days ago from
https://lnkd.in/p/ebCwa9Wk-----
Hannu
Attachments:
t253274_7v3-0001-Refactor-set-operation-group-clauses-to-decouple-.patchtext/x-patch; charset=US-ASCII; name=v3-0001-Refactor-set-operation-group-clauses-to-decouple-.patchDownload+80-68
v3-0002-Support-inline-ORDER-BY-in-DISTINCT-ON-for-SELECT.patchtext/x-patch; charset=US-ASCII; name=v3-0002-Support-inline-ORDER-BY-in-DISTINCT-ON-for-SELECT.patchDownload+459-31
v3-0003-Support-UNION-DISTINCT-ON-for-non-recursive-set-o.patchtext/x-patch; charset=US-ASCII; name=v3-0003-Support-UNION-DISTINCT-ON-for-non-recursive-set-o.patchDownload+268-52
v3-0004-Support-dynamic-pruning-in-recursive-UNION-DISTIN.patchtext/x-patch; charset=US-ASCII; name=v3-0004-Support-dynamic-pruning-in-recursive-UNION-DISTIN.patchDownload+275-6
v3-0005-Fix-bugs-security-issues-and-optimizations-in-DIS.patchtext/x-patch; charset=US-ASCII; name=v3-0005-Fix-bugs-security-issues-and-optimizations-in-DIS.patchDownload+1526-457
Hi Hannu,
3. Dynamic state-space pruning in recursive CTEs (WITH RECURSIVE) using
UNION DISTINCT ON (key ORDER BY cost), enabling Bellman-Ford /
shortest-path and optimal state-space search directly in SQL without
infinite loops or post-hoc filtering.
I ran a measured review of v3 on current master (7787aec8ab), looking only at
three things: correct results, memory safety, and the performance claim. No
opinion on syntax or the standard -- every number is from a differential
harness (row_number() and classic DISTINCT ON for the non-recursive cases,
Bellman-Ford in Python for the recursive ones).
Correctness: 0 divergences in ~42,000 random cases (24,000 with asserts,
17,975 under ASan+UBSan), across inline DISTINCT ON, UNION DISTINCT ON
(including nested/multi-way and under an outer WHERE pushdown), and recursive
shortest-path on random digraphs with cycles, zero-weight cycles and negative
edges. 15% of the non-recursive cases were also run through a view and a second
view rebuilt from pg_get_viewdef(), and 25% of the recursive ones added SEARCH
or CYCLE; all matched.
Memory: clean on the full series (0001..0005) -- 0 ASan/UBSan/assert reports in
~18,000 cases plus the regression and isolation suites. The 0005 fixes are
load-bearing: with only 0001..0004, the spill- and merge-heavy corpora bring
back several distinct failures -- an ASan SEGV, a UBSan null-pointer deref at
varatt.h:463, Assert(MemoryContextIsValid) and Assert(numCols <= pathkeys),
plus wrong results. So the executor changes in 0005 are closing real defects.
Performance: the recursive case is the strong one. Shortest path on a 5x5 grid
is 0.87 ms with UNION DISTINCT ON vs 715 ms with UNION ALL + CYCLE (~820x, and
19,633x fewer rows materialized); the UNION ALL form no longer finishes within
2 GB of temp from 6x6 up, while the new path does 100x100 in 43 ms and a
100k-node random graph in ~1.1 s. For plain grouping it depends on cardinality:
with ~1,000 groups the inline HashAgg path is ~3.6x faster than classic
DISTINCT ON or row_number() (73 vs 267/272 ms), but with 200k groups it is
slower -- inline 237 vs 218 ms for classic DISTINCT ON, and UNION DISTINCT ON
630 vs 462 ms for the classic rewrite over UNION ALL (~1.36x). No regression of
the untouched features was resolvable (CI95 overlap, ~1-3% resolution).
One small thing: with an unnamed first branch, the error HINT for an unknown
ORDER BY column names the internal alias ("Perhaps you meant to reference the
column unnamed_subquery.dst"). Plain UNION ... ORDER BY of an unknown column
behaves the same on master, so it looks pre-existing rather than new.
Happy to share the harness and the per-case numbers if they are useful.
Regards,
Manu
On Sat, Oct 17, 2026 at 8:54 PM Manu <manuelreyesbravo@gmail.com> wrote:
Hi Hannu,
3. Dynamic state-space pruning in recursive CTEs (WITH RECURSIVE) using
UNION DISTINCT ON (key ORDER BY cost), enabling Bellman-Ford /
shortest-path and optimal state-space search directly in SQL without
infinite loops or post-hoc filtering.I ran a measured review of v3 on current master (7787aec8ab), looking only at
three things: correct results, memory safety, and the performance claim.
Thanks!
No opinion on syntax or the standard --
Understood. We plan to work on getting the wider approval for the
syntax after the PostgrteSQL v19 release.
every number is from a differential
harness (row_number() and classic DISTINCT ON for the non-recursive cases,
Bellman-Ford in Python for the recursive ones).Correctness: 0 divergences in ~42,000 random cases (24,000 with asserts,
17,975 under ASan+UBSan), across inline DISTINCT ON, UNION DISTINCT ON
(including nested/multi-way and under an outer WHERE pushdown), and recursive
shortest-path on random digraphs with cycles, zero-weight cycles and negative
edges. 15% of the non-recursive cases were also run through a view and a second
view rebuilt from pg_get_viewdef(), and 25% of the recursive ones added SEARCH
or CYCLE; all matched.
Thanks!
Memory: clean on the full series (0001..0005) -- 0 ASan/UBSan/assert reports in
~18,000 cases plus the regression and isolation suites. The 0005 fixes are
load-bearing: with only 0001..0004, the spill- and merge-heavy corpora bring
back several distinct failures -- an ASan SEGV, a UBSan null-pointer deref at
varatt.h:463, Assert(MemoryContextIsValid) and Assert(numCols <= pathkeys),
plus wrong results. So the executor changes in 0005 are closing real defects.
Thanks for confirming 0005 has fixed these!
Performance: the recursive case is the strong one. Shortest path on a 5x5 grid
is 0.87 ms with UNION DISTINCT ON vs 715 ms with UNION ALL + CYCLE (~820x, and
19,633x fewer rows materialized); the UNION ALL form no longer finishes within
2 GB of temp from 6x6 up, while the new path does 100x100 in 43 ms and a
100k-node random graph in ~1.1 s.
Thanks!
Did you try to reach the limits where UNION DISTINCT ON fails to finish ?
For plain grouping it depends on cardinality:
with ~1,000 groups the inline HashAgg path is ~3.6x faster than classic
DISTINCT ON or row_number() (73 vs 267/272 ms), but with 200k groups it is
slower -- inline 237 vs 218 ms for classic DISTINCT ON, and UNION DISTINCT ON
630 vs 462 ms for the classic rewrite over UNION ALL (~1.36x). No regression of
the untouched features was resolvable (CI95 overlap, ~1-3% resolution).
Did you have you any insights about why the reversal of relative
performance happens at 200k groups ?
Is it about Hash vs Ordered grouping behaviour or something else?
One small thing: with an unnamed first branch, the error HINT for an unknown
ORDER BY column names the internal alias ("Perhaps you meant to reference the
column unnamed_subquery.dst"). Plain UNION ... ORDER BY of an unknown column
behaves the same on master, so it looks pre-existing rather than new.
I wonder if there is a nice way to fix it ?
What would be a good name for the unnamed first branch to use in error
messages ?
Happy to share the harness and the per-case numbers if they are useful.
Thanks, I will very likely ask for them at some point.
---
Hannu
Hi Hannu,
On Sun, Oct 25, 2026 at 12:48 PM Hannu Krosing <hannuk@google.com>
wrote:
Did you try to reach the limits where UNION DISTINCT ON fails to finish ?
Not to exhaustion, but the largest shapes I tried all finish on v3,
one run each with a 120 s cap:
grid 1000x1000 (1M nodes): 62.5 s, 1999 iterations
random digraph, 1M nodes, 4M edges: 18.5 s
adversarial DAG, 800 nodes: 11.0 s
The DAG is the slow one per node: edge i->j costs (j-i)^2, so the
cheapest path is the unit chain and every node improves once per
wave; time grows about n^3 (27 ms at 100 nodes, 1.4 s at 400).
The one shape that does not finish is a negative cycle: with no
fixpoint it keeps improving costs until statement_timeout, as
Bellman-Ford without cycle detection. If there are shapes you care
about, I can run them.
Did you have you any insights about why the reversal of relative
performance happens at 200k groups ?Is it about Hash vs Ordered grouping behaviour or something else?
Both: hash vs ordered, plus an estimate problem on the UNION side,
which the attached diff fixes. I re-measured on master 126976a8ff with
v3, on a ladder of 1k to 500k groups, in two independent passes with
all cells alternated. Percentages below are first pass / second pass;
the tables are in measurements.txt.
UNION DISTINCT ON plans its HashAggregate for as many groups as there
are input rows. build_setop_child_paths() estimates each branch over
its whole target list (prepunion.c:683 with v3 applied), and with a
unique id every branch looks fully distinct, so the estimate is
2,000,000 whatever the key and the hash table is sized for it: 40 MB
with 200k actual groups, against 16 MB with the diff, which takes the
estimate over the DISTINCT ON key only, summed over the branches as
for a plain UNION. Against the classic rewrite over UNION ALL, at
200k groups:
v3 as posted: +6.9% / -1.5% (the second within noise)
v3 with the diff: -14.5% / -21.2%
and with the diff -44% / -46% at 100k groups, -68% / -68% at 1k. The
other callers of build_setop_child_paths() pass NIL and behave as
before. make check and isolation pass on -O2 and on cassert+ASan, and
the oracle from my first mail gives 4,500 of 4,500 cases OK.
On the inline side the reversal from my October 17 mail does not
reproduce on 126976a8ff with this data: the HashAgg path is
-25.1% / -30.6% against classic DISTINCT ON at 200k groups, and
roughly even at 500k (+5.2% / +0.1%).
Where hash still loses, it is hash vs ordered:
UNION at 500k groups, with the diff: +26% / +22%
inline at 200k, work_mem = 4MB (the table spills): +14% / +10%
inline at 500k, work_mem = 4MB: +36% / +34%
Counted with perf stat, the hash path runs fewer instructions than the
sort but takes more cache misses once the table outgrows the L3 (16 MB
here; 500k groups is 36 MB even with the diff). The planner cannot see
that: in cost_agg() (costsize.c:2889-2900) the in-memory hashed cost
grows with the input rows only, so it picks HashAggregate at every
size on the ladder, at a fifth to a third of the Sort+Unique cost. A
plain GROUP BY on master is costed the same way, so I would treat the
remaining crossover as master's costing rather than something for v3.
I wonder if there is a nice way to fix it ?
What would be a good name for the unnamed first branch to use in error
messages ?
It turns out not to come from v3. With ge(src, dst, cost), plain
master gives the same HINT for
SELECT 1 AS node, 0 AS c UNION SELECT dst, src + cost FROM ge
ORDER BY cost;
The name comes from 585e31fcb6d (September 2025), which replaced the
"*SELECT* n" aliases with generated names. A set operation's branches
can never be referenced from its ORDER BY, so I think the hint should
not offer them at all, and a DETAIL could name the branch by position
("the second UNION branch"). That is master code, a small thread of
its own; I can put a patch together if you think it is worth it.
Thanks, I will very likely ask for them at some point.
It is attached as harness.txt: the differential oracle, the ladder
above, a small runner for alternated rounds, and the recursive cases.
The diff is yours to fold into your next version however you like.
Regards,
Manu