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;
