Breaking out of a recursive query in Postgres 11

Question

I'm having some trouble getting the correct data out of a tree structure, where I only want the first nodes in a branch matching criteria to be the result of the query.

I have this table of domains:

create table domains(
 id bigint,
 domain_name varchar,
 parent_id bigint,
 valid boolean
)
insert into domains values
 (1, 'example.com', null, false),
 (2, 'a.example.com', 1, true),
 (3, 'b.example.com', 1, false),
 (4, 'c.b.example.com', 3, true),
 (5, 'd.a.example.com', 2, true)

This gives this tree, with the valid domains in green:

domain graph

Based on this, I want a.example.com and c.b.example.com to be returned as valid domains. Had the top level domain example.com been valid, only that should be returned. ("valid" is just a flag determined elsewhere.)

I have a recursive query that fetches the whole domain tree:

WITH RECURSIVE valid_domains AS (
 SELECT id, domain_name, valid FROM domains
 WHERE parent_id IS NULL
 UNION ALL
 SELECT d.id, d.domain_name, d.valid FROM domains d
 JOIN valid_domains vd ON d.parent_id = vd.id
)
SELECT * FROM valid_domains

...but then my stumbling block is figuring out how to filter on valid domains and break that branch when I hit one that's valid, without returning any valid domains below it.

I've looked at window functions, but haven't been able to mesh that with the recursive query thus far. Am I taking the wrong approach by making this recursive in the first place?

Answer 1

WITH RECURSIVE cte AS (
 SELECT id, domain_name, valid 
 FROM domains
 WHERE parent_id IS NULL
UNION ALL
 SELECT domains.id, domains.domain_name, domains.valid 
 FROM domains
 JOIN cte ON domains.parent_id = cte.id
 WHERE NOT cte.valid -- stop recursion when valid node reached
)
SELECT id, domain_name
FROM cte
WHERE valid

fiddle

Answer 2

You were almost there:

WITH RECURSIVE valid_domains AS (
 SELECT id, domain_name, valid FROM domains
 WHERE parent_id IS NULL
 UNION ALL
 SELECT d.id, d.domain_name, d.valid FROM domains d
 JOIN valid_domains vd ON d.parent_id = vd.id
)
SELECT *
FROM valid_domains
WHERE valid
LIMIT 1;

I suppose you need to filter only valid answer and then just use LIMIT to get only the first result...

You might want to add an ORDER BY clause, though...

• Akina: The author needs ALL valid roots, not only one.