BUG #19922: CYCLE/SEARCH with a window in the recursive term: could not find replacement targetlist entry
The following bug has been logged on the website:
Bug reference: 19922
Logged by: Robins Tharakan
Email address: tharakan@gmail.com
PostgreSQL version: Unsupported/Unknown
Operating system: Unsupported/Unknown
Description:
A recursive query with a CYCLE or SEARCH clause fails when its
recursive term has a resjunk column, such as a window function's
ORDER BY column.
With CYCLE, builds without assertions, and assert-enabled builds
of 17 and older, raise
ERROR: XX000: could not find replacement targetlist entry for attno 2
LOCATION: ReplaceVarFromTargetList, rewriteManip.c:1903
and assert-enabled builds of 18 and later fail an assertion before
that:
TRAP: failed Assert("OidIsValid(eqop)"), File: "allpaths.c",
Line: 4602
With SEARCH in place of CYCLE, the same recursive term fails on every
branch, with or without assertions:
ERROR: 42804: attribute 2 of type record has wrong type
DETAIL: Table has type integer, but query expects record[].
LOCATION: CheckVarSlotCompatibility, execExprInterp.c:2429
Commit
======
Master: 8303f2e13c5 (2026-11-18) affected
Also affects: REL_14_STABLE through REL_19_STABLE
Built with --enable-cassert --enable-debug at -O0, and master also
without --enable-cassert at -O2 (gcc 14.2.0, glibc 2.41, Debian 13,
x86_64).
Error Log
========
master (8303f2e13c5), query 1:
TRAP: failed Assert("OidIsValid(eqop)"), File: "allpaths.c", Line: 4602,
PID: 1176274
LOG: client backend (PID 1176274) was terminated by signal 6: Aborted
master without assertions, and REL_17_STABLE (6c8717359a4), query 1:
ERROR: could not find replacement targetlist entry for attno 2
Backtrace
========
The assertion on master, query 1:
#0 ExceptionalCondition (conditionName="OidIsValid(eqop)", ...)
#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. CYCLE, with the window's ORDER BY column in the recursive term.
-- Builds without assertions, and 17 and older:
-- ERROR: could not find replacement targetlist entry for attno 2
-- Assert-enabled builds of 18 and later end the session at
-- TRAP: failed Assert("OidIsValid(eqop)"), File: "allpaths.c"
-- It should return (1, f, {(1)}) and (1, t, {(1),(1)}).
WITH RECURSIVE t(x) AS (
SELECT 1
UNION ALL
SELECT max(x) OVER (ORDER BY x) FROM t
) CYCLE x SET m USING p
SELECT * FROM t;
-- 2. The same recursive term with SEARCH, on every branch:
-- ERROR: attribute 2 of type record has wrong type
-- It should return what the term without the window does:
-- 1 | {(1)}
-- 2 | {(1),(2)}
-- 3 | {(1),(2),(3)}
WITH RECURSIVE t(x) AS (
SELECT 1
UNION ALL
SELECT max(x) OVER (ORDER BY x) + 1 FROM t WHERE x < 3
) SEARCH DEPTH FIRST BY x SET o
SELECT * FROM t;
-- 3. Both clauses, on every branch, with or without assertions:
-- ERROR: could not find replacement targetlist entry for attno 4
-- It should return one empty row.
WITH RECURSIVE a AS (
SELECT NULL b, NULL ~ NULL c
UNION
SELECT NULL, NULL ~ max(NULL) OVER (PARTITION BY 0 ORDER BY 1) FROM a
) SEARCH BREADTH FIRST BY b SET d CYCLE c SET e USING f,
g AS (SELECT FROM a)
SELECT;
All three queries fail on master and every supported branch
(and on 14.25). A release build of master (no --enable-cassert, -O2)
raises the XX000 and 42804 errors.
A recursive term with DISTINCT fails the same assertion on 18 and
later, for a different reason: a regression of 44fb59fc605. I'm
reporting that separately.
Found using SQLsmith, SQLReduce and Claude.
-
Robins Tharakan
Databricks
PG Bug reporting form <noreply@postgresql.org> writes:
A recursive query with a CYCLE or SEARCH clause fails when its
recursive term has a resjunk column, such as a window function's
ORDER BY column.
Yeah; you can make it fail with a resjunk GROUP BY term too, such as
WITH RECURSIVE t(x) AS (
SELECT 1
UNION ALL
SELECT x+1 FROM t WHERE x < 3 GROUP BY x
) SEARCH DEPTH FIRST BY x SET o
SELECT * FROM t;
ERROR: attribute 2 of type record has wrong type
DETAIL: Table has type integer, but query expects record[].
I think the problem is that rewriteSearchAndCycle() is appending extra
items to the right subquery's tlist without regard for the possibility
that there are resjunk items in it. This goes against our general
expectation that resjunk entries come last, and in particular it
breaks the correspondence between the subquery's column name lists and
their corresponding tlist entries. The names that are meant to refer
to the added extra items instead refer to resjunk entries, causing
all sorts of jolliness later.
There may be a similar problem with the left subquery too, not sure.
I think the way to fix this is to inject the added columns before any
resjunk columns (renumbering the latter). I've got a hard stop coming
up shortly, but can look at this tomorrow if no one beats me to it.
regards, tom lane
Hi,
I looked into this following Tom's suggestion.
On Fri, Nov 20, 2026 at 3:17 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
I think the problem is that rewriteSearchAndCycle() is appending extra
items to the right subquery's tlist without regard for the possibility
that there are resjunk items in it. This goes against our general
expectation that resjunk entries come last, and in particular it
breaks the correspondence between the subquery's column name lists and
their corresponding tlist entries. The names that are meant to refer
to the added extra items instead refer to resjunk entries, causing
all sorts of jolliness later.
Thanks for the idea. I checked this and it indeed seemed to be the case.
I'm attaching a patch with the fix in this area. It detaches any resjunk
entries from the recursive term's tlist, adds the SEARCH/CYCLE columns,
then re-attaches the resjunk entries with new resnos, the same way
rewriteTargetListIU() handles junk entries.
There may be a similar problem with the left subquery too, not sure.
I checked this using LLM and the left side seems fine.
rewriteSearchAndCycle() wraps the non-recursive term in a new subquery
without touching its tlist, and the outer query only references columns
1..n of it. Here is one example I tested that was working fine on master.
WITH RECURSIVE t(x) AS (
SELECT max(n) OVER (ORDER BY s) FROM (VALUES (1, 'a')) v(n, s)
UNION ALL
SELECT x+1 FROM t WHERE x < 3
) SEARCH DEPTH FIRST BY x SET o CYCLE x SET m USING p
SELECT * FROM t;
x | o | m | p
---+---------------+---+---------------
1 | {(1)} | f | {(1)}
2 | {(1),(2)} | f | {(1),(2)}
3 | {(1),(2),(3)} | f | {(1),(2),(3)}
Thanks & Regards,
Nitin Motiani
Google
Nitin Motiani <nitinmotiani@google.com> writes:
On Fri, Nov 20, 2026 at 3:17 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
I think the problem is that rewriteSearchAndCycle() is appending extra
items to the right subquery's tlist without regard for the possibility
that there are resjunk items in it.
Thanks for the idea. I checked this and it indeed seemed to be the case.
I'm attaching a patch with the fix in this area.
Thanks for doing the legwork. I pushed this after rewriting the
initial hunk a little: I didn't like just assuming that we know the
number of non-resjunk columns. rewriteTargetListIU() splits the
tlist using explicit checks on the resjunk flags, and I think this
code should do the same. We can assert that the result matches the
CTE column list afterwards.
regards, tom lane