Postgres 16

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
CREATE TABLE document(
   id   INTEGER  NOT NULL
  ,type VARCHAR(12) NOT NULL
);
INSERT INTO document(id,type) VALUES (1,'invalid_type');
INSERT INTO document(id,type) VALUES (2,'valid_type_a');
INSERT INTO document(id,type) VALUES (3,'invalid_type');
INSERT INTO document(id,type) VALUES (4,'valid_type_a');
INSERT INTO document(id,type) VALUES (5,'invalid_type');
INSERT INTO document(id,type) VALUES (6,'valid_type_b');
INSERT INTO document(id,type) VALUES (7,'invalid_type');
INSERT INTO document(id,type) VALUES (8,'valid_type_b');
INSERT INTO document(id,type) VALUES (9,'invalid_type');
INSERT INTO document(id,type) VALUES (10,'valid_type_a');
INSERT INTO document(id,type) VALUES (11,'valid_type_a');
INSERT INTO document(id,type) VALUES (12,'invalid_type');
INSERT INTO document(id,type) VALUES (13,'invalid_type');
INSERT INTO document(id,type) VALUES (14,'invalid_type');
INSERT INTO document(id,type) VALUES (15,'valid_type_b');

CREATE TABLE relation(
   relationId       INTEGER  NOT NULL
  ,parentDocumentId INTEGER  NOT NULL
  ,childDocumentId  INTEGER  NOT NULL
);
INSERT INTO relation(relationId,parentDocumentId,childDocumentId) VALUES (1,1,2);
INSERT INTO relation(relationId,parentDocumentId,childDocumentId) VALUES (2,1,3);
INSERT INTO relation(relationId,parentDocumentId,childDocumentId) VALUES (3,2,4);
INSERT INTO relation(relationId,parentDocumentId,childDocumentId) VALUES (4,2,5);
INSERT INTO relation(relationId,parentDocumentId,childDocumentId) VALUES (5,3,6);
INSERT INTO relation(relationId,parentDocumentId,childDocumentId) VALUES (6,6,7);
INSERT INTO relation(relationId,parentDocumentId,childDocumentId) VALUES (7,8,9);
INSERT INTO relation(relationId,parentDocumentId,childDocumentId) VALUES (8,9,10);
INSERT INTO relation(relationId,parentDocumentId,childDocumentId) VALUES (9,12,13);
INSERT INTO relation(relationId,parentDocumentId,childDocumentId) VALUES (10,13,14);
INSERT INTO relation(relationId,parentDocumentId,childDocumentId) VALUES (11,13,15);

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

INSERT 0 1

INSERT 0 1

INSERT 0 1

INSERT 0 1

INSERT 0 1

INSERT 0 1

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

INSERT 0 1

INSERT 0 1

create index ix1 on relation (childDocumentId, parentDocumentId);

CREATE INDEX

create index ix2 on document (id);

CREATE INDEX

with recursive
n (id, lvl, cid, burned) as (
  select id, 1, id, false from document where type like 'v%'
 union all
  select n.id, n.lvl + 1, d.id, d.type like 'v%'
  from n
  join relation r on r.childDocumentId = n.cid and not n.burned
  join document d on d.id = r.parentDocumentId
)
select *
from (
  select distinct on (id) * from n order by id, lvl desc
) x
where not burned;

id
lvl
cid
burned

2
2
1
f

6
3
1
f

8
1
8
f

11
1
11
f

15
3
12
f

SELECT 5