By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
Help with an interesting Postgres question: Why isn't an Index Only Scan used on a partition accessed via the parent table?.
CREATE TABLE edges(
src integer,
dst integer,
data integer
);
INSERT INTO edges VALUES (1, 2, 1);
INSERT INTO edges VALUES (2, 3, 1);
INSERT INTO edges VALUES (3, 2, 1); -- This entry creates a loop
INSERT INTO edges VALUES (1, 4, 1);
INSERT INTO edges VALUES (4, 5, 1);
INSERT INTO edges VALUES (5, 2, 1);
INSERT INTO edges VALUES (1, 4, 2);
INSERT INTO edges VALUES (4, 5, 2);
INSERT INTO edges VALUES (4, 6, 2);
CREATE TABLE
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
INSERT 0 1
WITH RECURSIVE paths AS (
-- For simplicity assume node 1 is the start
-- we'll have two starting nodes for data = 1 and 2
SELECT DISTINCT
src as node
, data as data
, 0 as depth
, src::text as path
, false as is_cycle
, ARRAY[src] as path_array
FROM edges
WHERE src IN ( 1,2)
UNION ALL
SELECT DISTINCT
edges.dst
, edges.data
, depth + 1
, paths.path || '->' || edges.dst::text
, dst = ANY(path_array)
, path_array || dst
FROM paths
JOIN edges
ON edges.src = paths.node
AND edges.data = paths.data
AND NOT is_cycle
)
SELECT * FROM paths;
| node | data | depth | path | is_cycle | path_array |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | f | {1} |
| 1 | 2 | 0 | 1 | f | {1} |
| 2 | 1 | 0 | 2 | f | {2} |
| 2 | 1 | 1 | 1->2 | f | {1,2} |
| 3 | 1 | 1 | 2->3 | f | {2,3} |
| 4 | 1 | 1 | 1->4 | f | {1,4} |
| 4 | 2 | 1 | 1->4 | f | {1,4} |
| 2 | 1 | 2 | 2->3->2 | t | {2,3,2} |
| 3 | 1 | 2 | 1->2->3 | f | {1,2,3} |
| 5 | 1 | 2 | 1->4->5 | f | {1,4,5} |
| 5 | 2 | 2 | 1->4->5 | f | {1,4,5} |
| 6 | 2 | 2 | 1->4->6 | f | {1,4,6} |
| 2 | 1 | 3 | 1->2->3->2 | t | {1,2,3,2} |
| 2 | 1 | 3 | 1->4->5->2 | f | {1,4,5,2} |
| 3 | 1 | 4 | 1->4->5->2->3 | f | {1,4,5,2,3} |
| 2 | 1 | 5 | 1->4->5->2->3->2 | t | {1,4,5,2,3,2} |
SELECT 16