BUG #19923: SEARCH/CYCLE with DISTINCT in the recursive term: rows depend on input order
The following bug has been logged on the website:
Bug reference: 19923
Logged by: Robins Tharakan
Email address: tharakan@gmail.com
PostgreSQL version: Unsupported/Unknown
Operating system: Debian 13 (x86_64)
Description:
A recursive query with a SEARCH or CYCLE clause returns rows that
depend on the order of its input when its recursive term uses DISTINCT
or GROUP BY.
On master, REL_19_STABLE and REL_18_STABLE, the CYCLE form
also fails this assertion in assert-enabled builds:
TRAP: failed Assert("OidIsValid(eqop)"), File: "allpaths.c",
Line: 4602
This appears to be separate from BUG #19922, and thus filed separately.
Commit
======
Affects: REL_14_STABLE 853b35f35b1 (2026-11-10)
REL_15_STABLE 6ee74fe7389 (2026-11-18)
REL_16_STABLE f8bd8d39783 (2026-11-18)
REL_17_STABLE 6c8717359a4 (2026-11-18)
REL_18_STABLE 9107706245e (2026-11-18), with the assertion
REL_19_STABLE f66932c8dd4 (2026-11-19), with the assertion
Master: ba11c483900 (2026-11-19), the newest commit tested
Built with --enable-cassert --enable-debug at -O0, and master also
without --enable-cassert at -O2 (gcc 14.2.0, Debian 13, x86_64).
Error Log
=========
TRAP: failed Assert("OidIsValid(eqop)"), File: "allpaths.c", Line: 4602,
PID: 1405985
LOG: client backend (PID 1405985) was terminated by signal 6: Aborted
Backtrace (v18+)
================
#0 ExceptionalCondition (...) at assert.c:35
#1 pushdown_var_grouping_eqop (...) at allpaths.c:4602
#2 grouping_conflict_walker (...) at clauses.c:6576
#5 grouping_conflict_walker (...) at clauses.c:6710
#6 expression_has_grouping_conflict (...) at clauses.c:6533
#7 qual_is_pushdown_safe (...) at allpaths.c:4569
#8 set_subquery_pathlist (...) at allpaths.c:2774
#9 set_rel_size (...) at allpaths.c:472
#14 subquery_planner (...) at planner.c:1368
#15 recurse_set_operations (...) at prepunion.c:252
#16 generate_recursion_path (...) at prepunion.c:405
SQL
===
-- 1. On 18 and later, assert-enabled builds end the session with the
-- TRAP above. 14 to 17 return (1, f, {(1)}) and (1, t, {(1),(1)}).
WITH RECURSIVE t(x) AS (
SELECT 1
UNION ALL
SELECT DISTINCT x FROM t
) CYCLE x SET m USING p
SELECT * FROM t;
-- 2. Edges 1->3, 2->3, 3->1, starting from 1 and 2. On 14 to 17, and
-- in builds without assertions, 4 rows:
-- (1,f,{(1)}) (3,f,{(1),(3)}) (1,t,{(1),(3),(1)}) (2,f,{(2)})
WITH RECURSIVE e(src, dst) AS (VALUES (1, 3), (2, 3), (3, 1)),
t(x) AS (
SELECT * FROM (VALUES (1), (2)) v(x)
UNION ALL
SELECT DISTINCT e.dst FROM t JOIN e ON e.src = t.x
) CYCLE x SET m USING p
SELECT * FROM t ORDER BY p::text;
-- 3. The same, starting from 2 and 1: 5 rows.
-- (1,f,{(1)}) (2,f,{(2)}) (3,f,{(2),(3)}) (1,f,{(2),(3),(1)})
-- (3,t,{(2),(3),(1),(3)})
WITH RECURSIVE e(src, dst) AS (VALUES (1, 3), (2, 3), (3, 1)),
t(x) AS (
SELECT * FROM (VALUES (2), (1)) v(x)
UNION ALL
SELECT DISTINCT e.dst FROM t JOIN e ON e.src = t.x
) CYCLE x SET m USING p
SELECT * FROM t ORDER BY p::text;
-- 4. Query 2 with UNION in place of DISTINCT: 7 rows on every branch,
-- those of queries 2 and 3 together.
WITH RECURSIVE e(src, dst) AS (VALUES (1, 3), (2, 3), (3, 1)),
t(x) AS (
SELECT * FROM (VALUES (1), (2)) v(x)
UNION
SELECT e.dst FROM t JOIN e ON e.src = t.x
) CYCLE x SET m USING p
SELECT * FROM t ORDER BY p::text;
-- 5. SEARCH, no cycles: edges 1->3, 2->3, 3->4, starting from 1 and 2.
-- Every branch: (1,{(1)}) (3,{(1),(3)}) (4,{(1),(3),(4)}) (2,{(2)})
WITH RECURSIVE e(src, dst) AS (VALUES (1, 3), (2, 3), (3, 4)),
t(x) AS (
SELECT * FROM (VALUES (1), (2)) v(x)
UNION ALL
SELECT DISTINCT e.dst FROM t JOIN e ON e.src = t.x
) SEARCH DEPTH FIRST BY x SET s
SELECT * FROM t ORDER BY s;
-- 6. The same, starting from 2 and 1:
-- (1,{(1)}) (2,{(2)}) (3,{(2),(3)}) (4,{(2),(3),(4)})
WITH RECURSIVE e(src, dst) AS (VALUES (1, 3), (2, 3), (3, 4)),
t(x) AS (
SELECT * FROM (VALUES (2), (1)) v(x)
UNION ALL
SELECT DISTINCT e.dst FROM t JOIN e ON e.src = t.x
) SEARCH DEPTH FIRST BY x SET s
SELECT * FROM t ORDER BY s;
Queries 2 and 3 differ only in the order of their two starting rows,
but query 2 returns 4 rows, query 3 returns 5. SEARCH DEPTH FIRST
(queries 5 and 6) returns the same nodes in either order, but nodes
3 and 4 carry the path from whichever start came first.
- The assertion fails on master through REL_18_STABLE
- REL_17_STABLE through REL_14_STABLE + release builds run every query
and return the rows given in its comments
Found using SQLsmith, SQLReduce and Claude.
-
Robins Tharakan
Databricks
PG Bug reporting form <noreply@postgresql.org> writes:
A recursive query with a SEARCH or CYCLE clause returns rows that
depend on the order of its input when its recursive term uses DISTINCT
or GROUP BY.
Hm, I see no GROUP BY in your examples?
The proximate cause of the problem seems to be that we add extra
columns to the righthand subquery without any consideration for
the fact that if it has a DISTINCT clause then that clause suggests
that we need to include the new columns in the DISTINCT-ing.
But we don't actually do so. Pre-v18 planner versions seem to
tolerate the inconsistency, at least to the point of not crashing,
while currently we don't. But I think this is definitely the
rewriter's error not the planner's.
Before we invest a lot of effort in fixing that, I think we
ought to push back a little on whether this is actually a sensible
thing to do. I see nothing in the SQL spec forbidding it, but
including the extra columns in the DISTINCT list seems to carry
a risk of splitting what the user expected to be a single output
row into multiple rows. OTOH, if we avoided that by converting
DISTINCT to DISTINCT ON, we'd have uncertainty about which
extra-column values get emitted. The only way that this is stable
is if the extra columns are absolutely, positively guaranteed to
be immutable functions of the regular columns. Do we want to
assume that? The main hazard I see is that we allow a much
wider range of <cycle mark value> and <non-cycle mark value>
than the spec contemplates, eg we will happily take
"timestamptz 'now'" as a mark value. I'm not entirely convinced
that mark values of non-built-in datatypes couldn't cause a problem.
The SQL spec's definition of SEARCH/CYCLE via rewrite rule definitely
results in including the added columns in any DISTINCT behavior.
If the committee thought about this issue, they must have decided that
they believe in the immutability of the added columns --- which may
well be the reason that they restrict the mark values to be literals.
Thoughts?
regards, tom lane
I wrote:
... The only way that this is stable
is if the extra columns are absolutely, positively guaranteed to
be immutable functions of the regular columns. Do we want to
assume that? The main hazard I see is that we allow a much
wider range of <cycle mark value> and <non-cycle mark value>
than the spec contemplates, eg we will happily take
"timestamptz 'now'" as a mark value.
Oh wait, you can reach the issue without anything terribly fancy,
because while we require the mark values to be constants, we don't
insist on them being of identical type, and will insert a cast
instead. If the cast is mutable, say timestamp to timestamptz,
then so is the cycle expression. I'm not sure we have any casts
that are volatile enough to change output mid-query, but we don't
forbid that.
regards, tom lane
Oh, I have it: the right fix here is to leave the right subquery's
tlist entirely alone, and instead compute the extra columns in its
parent query. The reason we didn't see a problem for #19922 in
the lefthand subquery is that it's done that way for the lefthand
subquery; but for some reason we didn't do it like that for the
righthand one.
Now that I look more closely, I think that the SQL spec's rewrite
rule actually directs us to do it like that. So there's no
semantic hazard in the spec, only in our implementation.
regards, tom lane
I wrote:
Oh, I have it: the right fix here is to leave the right subquery's
tlist entirely alone, and instead compute the extra columns in its
parent query.
Ah, that doesn't work: there's no way to get the sequence column
out of the subquery.
What does work is to make the DISTINCT structure valid again by
converting it to DISTINCT ON, as in the trivial patch attached.
Despite my worries an hour ago, it doesn't seem like this will
cause a problem for any remotely-sane behavior of the mark column.
Also, if I'm not mistaken, it reverts the behavior to what we did
pre-v18. I've not dug to see exactly where the planner goes wrong
now with the inconsistent hasDistinctOn setting, but it doesn't
matter: rewriteSearchAndCycle is clearly at fault for generating
an inconsistent query.
regards, tom lane