Re: Introducing find_all_inheritors_ordered()

> On Sep 5, 2026, at 05:48, Zsolt Parragi <zsolt(dot)parragi(at)percona(dot)com> wrote:
>
> On Fri, 04 Sep 2026, Ewan Young <kdbase(dot)hack(at)gmail(dot)com> wrote:
>> - Kahn's algorithm implementation looks right.
>
> Not entirely, the implementation assumes that the graph is a DAG with
> an assert, which unfortunately isn't the case:
>
> At src/backend/commands/tablecmds.c:17958-17964 (ATExecAddInherit)
>
> This is not completely bulletproof because of race conditions: in
> multi-level inheritance trees, someone else could concurrently be
> making another inheritance link that closes the loop but does not join
> either of the rels we have locked. ... find_all_inheritors() will
> cope with circularity anyway, so don't sweat it too much."
>
> This can be reproduced a parallel alter, e.g.:
>
> With r->b, b->c, d->e already in place:
> S1: begin; alter table d inherit c; -- AEL(d), SUE(c), AS(d,e)
> S2: begin; alter table b inherit e; -- AEL(b), SUE(e), AS(b,c)
> S1: commit;
> S2: commit;
>
> And then alters can either hit the
>
> Assert(list_length(ordered) == list_length(agenda));
>
> assertion in debug builds or end up with a inconsistent results in
> release builds.

Hi Zsolt,

Thanks for pointing out that, I didn’t notice that piece of comments before.

My understanding is that PG doesn’t intend to support cyclic inheritance. The code explicitly rejects it:
```
if (list_member_oid(children, RelationGetRelid(parent_rel)))
ereport(ERROR,
(errcode(ERRCODE_DUPLICATE_TABLE),
errmsg("circular inheritance not allowed"),
errdetail("\"%s\" is already a child of \"%s\".",
parent->relname,
RelationGetRelationName(child_rel))));
```

However, concurrent ALTER TABLE … INHERIT commands may create cycles, and preventing that would be too expensive. So, find_all_inheritors() handles cycles defensively.

Therefore, find_all_inheritors_ordered() should not be a general replacement for find_all_inheritors(). ATExecAddInherit() can continue using find_all_inheritors(), allowing ALTER TABLE … INHERIT to succeed if its check finds that the new link would not create a cycle. Other DDL commands that don’t change inheritance and need a topological ordering can use find_all_inheritors_ordered(). I have updated the function’s header comment to explain this and replaced the assertion with an error.

For the ALTER TABLE … ALTER CONSTRAINT … NOT ENFORCED command that this patch updates, the existing implementation recursively checks parents’ enforceability. A cycle can cause it to exceed the stack depth limit, so it is reasonable to fail the command when a cycle is detected.

Going one step further, perhaps ATExecAddInherit() could also use find_all_inheritors_ordered(). That would change the behavior: if the child being altered is in a cycle, or has descendants in a cycle, the command would fail, requiring the user to break the cycle first. This would not prevent concurrent commands from creating a cycle, but it could reveal an existing, unintended cycle that users might otherwise be unaware of.

PFA v2.

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/