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

Hi Hannu,

On Sun, Oct 25, 2026 at 12:48 PM Hannu Krosing <hannuk(at)google(dot)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