BUG #19923: SEARCH/CYCLE with DISTINCT in the recursive term: rows depend on input order

From: PG Bug reporting form <noreply(at)postgresql(dot)org>
To: pgsql-bugs(at)lists(dot)postgresql(dot)org
Cc: tharakan(at)gmail(dot)com
Subject: BUG #19923: SEARCH/CYCLE with DISTINCT in the recursive term: rows depend on input order
Date: 2026-11-19 06:44:17
Message-ID: 19923-24cef1e958fa2370@postgresql.org
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-bugs

The following bug has been logged on the website:

Bug reference: 19923
Logged by: Robins Tharakan
Email address: tharakan(at)gmail(dot)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

Browse pgsql-bugs by date

  From Date Subject
Next Message Fujii Masao 2026-11-19 07:14:21 Re: BUG #19776: pg_combinebackup ignores the truncation_block_length of an intermediate incremental backup
Previous Message shihao zhong 2026-11-19 05:09:11 Re: BUG #19899: PL/Python backend crashes (SIGSEGV) when converting a column value to a Python object fails