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

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