> On Sep 5, 2026, at 05:48, Zsolt Parragi <[email protected]> wrote: > > On Fri, 04 Sep 2026, Ewan Young <[email protected]> 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/
v2-0001-Add-find_all_inheritors_ordered.patch
Description: Binary data
