BUG #19922: CYCLE/SEARCH with a window in the recursive term: could not find replacement targetlist entry

Started by PG Bug reporting form3 days ago4 messagesbugs
Jump to latest
#1PG Bug reporting form
noreply@postgresql.org

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

#2Tom Lane
tgl@sss.pgh.pa.us
In reply to: PG Bug reporting form (#1)
Re: BUG #19922: CYCLE/SEARCH with a window in the recursive term: could not find replacement targetlist entry

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

#3Nitin Motiani
nitinmotiani@google.com
In reply to: Tom Lane (#2)
Re: BUG #19922: CYCLE/SEARCH with a window in the recursive term: could not find replacement targetlist entry

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

Attachments:

t259455_3
v1-0001-Fix-SEARCH-CYCLE-when-the-recursive-term-has-resj.patchapplication/x-patch; name=v1-0001-Fix-SEARCH-CYCLE-when-the-recursive-term-has-resj.patchDownload+111-2
#4Tom Lane
tgl@sss.pgh.pa.us
In reply to: Nitin Motiani (#3)
Re: BUG #19922: CYCLE/SEARCH with a window in the recursive term: could not find replacement targetlist entry

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