Re: ANSI SQL proposal: SELECT DISTINCT ON (... ORDER BY ...) and UNION DISTINCT ON (... ORDER BY ...)

On Sat, Oct 17, 2026 at 8:54 PM Manu <manuelreyesbravo(at)gmail(dot)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