Many-groups follow-up: where HashAgg DISTINCT ON wins and loses Builds: master 126976a8ff + Hannu's v3 0001..0005 ("v3"), the same plus the attached nocfbot-union-distinct-on-estimate-on-v3.diff.txt ("v3+fix"), and master alone ("master", for the classic forms). -O2. All in one lane: 4 Zen 5 cores sharing a 16 MB L3; rounds whose calibration micro-benchmark ran >8% slower than idle were discarded and retried. Data: two tables of 1,000,000 rows; gK has K distinct values (uniform); zK is skewed (K * random()^3). work_mem = 64MB unless noted, no parallel. Inline: SELECT DISTINCT ON (gK ORDER BY s DESC, id) gK, s, id FROM big1 vs classic SELECT DISTINCT ON (gK) ... ORDER BY gK, s DESC, id (master). UNION: big1 UNION DISTINCT ON (gK ORDER BY s DESC, id) big2 vs classic DISTINCT ON over big1 UNION ALL big2 (master). Two independent passes, every cell alternated with all the others; each number below is a median in ms, first pass then second (10 / 12 clean rounds). The second pass ran ~4% faster across the board, so compare within a pass; the deltas are median differences with a bootstrap 95% CI, per pass. Inline DISTINCT ON (1M rows), ms v3 hash v3 sort classic g1000 91 90 310 306 310 306 g10000 102 100 280 273 282 276 g50000 115 112 267 257 265 256 g100000 142 127 264 258 265 257 g200000 193 175 258 254 258 252 g500000 267 246 252 247 254 246 z10000 102 99 300 289 293 287 z200000 158 144 267 262 269 261 work_mem 4MB (the hash table spills): g200000 203 193 178 175 g500000 253 239 186 179 192-byte text in the output: g1000 102 97 483 569 g200000 350 343 420 412 UNION DISTINCT ON (2 x 1M rows), ms v3 hash v3+fix hash classic g1000 201 197 186 188 590 590 g10000 231 222 206 204 533 527 g50000 291 263 233 229 491 490 g100000 385 333 275 263 490 486 g200000 511 475 409 380 478 483 g500000 643 606 587 561 466 461 z10000 226 217 202 200 558 552 z200000 442 388 313 295 502 496 Deltas (new vs reference), first pass / second pass: inline 1k, v3 hash vs classic: -70.5% [-72.4..-70.1] / -70.5% [-70.9..-70.3] inline 200k, v3 hash vs classic: -25.1% [-32.1..-13.6] / -30.6% [-31.8..-29.6] inline 500k, v3 hash vs classic: +5.2% [+0.4..+10.4] / +0.1% [-0.9..+1.6] inline 200k, 4MB, v3 hash vs classic: +14.2% [+8.9..+22.5] / +10.4% [+8.1..+12.7] inline 500k, 4MB, v3 hash vs classic: +35.9% [+30.8..+39.5] / +33.6% [+31.6..+35.1] UNION 1k, v3+fix vs classic: -68.4% [-69.7..-62.8] / -68.1% [-68.3..-67.6] UNION 100k, v3+fix vs classic: -43.8% [-46.7..-41.4] / -45.9% [-47.3..-45.3] UNION 200k, v3 vs classic: +6.9% [+4.6..+16.8] / -1.5% [-4.4..+3.4] UNION 200k, v3+fix vs classic: -14.5% [-18.1..-3.6] / -21.2% [-23.3..-15.8] UNION 200k, v3+fix vs v3: -20.0% [-27.1..-9.8] / -20.0% [-24.1..-14.1] UNION 500k, v3+fix vs classic: +26.0% [+20.6..+35.5] / +21.8% [+20.5..+24.1] UNION z200k, v3+fix vs classic: -37.6% [-40.2..-26.8] / -40.5% [-41.4..-37.4] Tried and dropped, each on top of v3+fix (same passes; the fix does not touch the inline path, so v3 is the inline reference): Bump instead of AllocSet for the tuples, inline 200k: -5.2% [-19.4..+9.3] / -2.6% [-6.6..+0.7] sort keys cached in the entry, inline 1k: -6.9% [-7.9..-5.2] / -13.0% [-13.8..-11.4] sort keys cached in the entry, inline 200k: +7.5% [-7.1..+20.5] / +10.8% [+9.0..+13.4] charging the tie-break comparisons in create_agg_path(): no plan changes anywhere on the ladder (HashAggregate stays at ~1/4 of the Sort+Unique cost). Planner choice: HashAggregate at every point of the ladder, for v3 and v3+fix alike; its estimated cost is a fifth to a third of Sort+Unique. UNION DISTINCT ON, estimated groups and hash table memory (EXPLAIN ANALYZE): groups K est. v3 est. fix actual memory v3 memory fix -------- ------- -------- -------- --------- ---------- 1000 2000000 2000 1000 32857 kB 153 kB 10000 2000000 19931 10000 33305 kB 1049 kB 50000 2000000 96801 50000 34841 kB 4121 kB 100000 2000000 184533 100000 36889 kB 8217 kB 200000 2000000 338055 199991 40985 kB 16409 kB 500000 2000000 678786 490827 53273 kB 36889 kB Recursive UNION DISTINCT ON (node ORDER BY cost), shortest path from node 1, one run each on v3, other lane (8 Zen 5c cores, 8 MB L3), 120 s cap: grid 200x200 (40k nodes): 441 ms, 399 iterations grid 500x500 (250k nodes): 7.1 s, 999 iterations grid 1000x1000 (1M nodes): 62.5 s, 1999 iterations random, 100k nodes, 400k edges: 1.2 s, 28 iterations random, 1M nodes, 4M edges: 18.5 s, 33 iterations adversarial DAG, 100 nodes: 27 ms, 100 iterations adversarial DAG, 200 nodes: 187 ms, 200 iterations adversarial DAG, 400 nodes: 1.4 s, 400 iterations adversarial DAG, 800 nodes: 11.0 s, 800 iterations negative cycle (3 nodes): never finishes (statement_timeout 20 s) (adversarial DAG: edge i->j costs (j-i)^2, so the cheapest path is the unit chain and every node improves once per wave; time grows ~n^3)