Introducing find_all_inheritors_ordered()

Hi all,

On Mon, Aug 31, 2026 at 2:34 PM Chao Li <li.evan.chao@gmail.com> wrote:

Hi,

This is follow-up work to patch [1], which fixed a bug when altering a CHECK constraint's enforceability. The fix was not very elegant. It had to use upward recursion to traverse all ancestors when deciding a child table's enforceability. This was because the existing function find_all_inheritors() returns a list of descendants without ensuring that parents precede their children.

This patch introduces a new function, find_all_inheritors_ordered(), which guarantees that every ancestor in the returned list appears before its descendants. With this new function, the original fix in commit 0cd17fdd3c0 is significantly simplified. The function could also potentially benefit other features that need to traverse inheritance trees in parent-before-child order.

This patch also strengthens an existing test by adding another level of inheritance. My first version of the implementation failed with the following case:
```
Root ———————————————> child
\ /
\ ——————> a —————> b /
```
(The diagram might not display well. Basically, “child" has parents “b" and “root", “b" has parent “a”, “a” has parent “root")

The current version uses Kahn's topological sorting algorithm, which handles this case correctly. Please see the attached patch for details.

[1] /messages/by-id/E74C57FA-1DD0-4C8E-8FB1-538034752592@gmail.com

I reviewed and tested the patch. I was able to reproduce the ordering
issue with find_all_inheritors() using a multiple-inheritance
hierarchy where a descendant can be returned before one of its
ancestors. After the patch, verified that the
find_all_inheritors_ordered() returns the relations in
ancestor-before-descendant order for the same hierarchy. And also
reviewed the changes in tablecmds.c. The removal of the
changing_conids handling and the upward recursive check looks correct
to me. The ordered traversal ensures that the affected parent
constraints are processed before their descendants, and the
CommandCounterIncrement() makes the updated parent constraint state
visible to subsequent processing. The updated regression test provides
coverage for a deeper inheritance hierarchy with multiple inheritance.
I also verified that the existing CHECK constraint enforceability
behavior is preserved. The inherit and constraints regression test
suites were executed successfully. The complete check-world test suite
was also run and all tests passed. I did not find any correctness
issues with the patch and the patch looks good to me.

Regards,
Solai

On Thu, Jul 30, 2026 at 4:35 PM Chao Li <li.evan.chao@gmail.com> wrote:

Hi,

This is follow-up work to patch [1], which fixed a bug when altering a CHECK constraint's enforceability. The fix was not very elegant. It had to use upward recursion to traverse all ancestors when deciding a child table's enforceability. This was because the existing function find_all_inheritors() returns a list of descendants without ensuring that parents precede their children.

This patch introduces a new function, find_all_inheritors_ordered(), which guarantees that every ancestor in the returned list appears before its descendants. With this new function, the original fix in commit 0cd17fdd3c0 is significantly simplified. The function could also potentially benefit other features that need to traverse inheritance trees in parent-before-child order.

This patch also strengthens an existing test by adding another level of inheritance. My first version of the implementation failed with the following case:
```
Root ———————————————> child
\ /
\ ——————> a —————> b /
```
(The diagram might not display well. Basically, “child" has parents “b" and “root", “b" has parent “a”, “a” has parent “root")

The current version uses Kahn's topological sorting algorithm, which handles this case correctly. Please see the attached patch for details.

I reviewed and tested v1 on top of master (ac1ccbea98f). The idea is a
clear improvement over the changing_conids + upward recursion in
0cd17fdd3c0: with parents guaranteed to be visited first, a child only
ever needs to look at the *current* state of its direct parents, and the
CommandCounterIncrement() makes that state visible. That also matches
what ATExecAlterConstrInheritability() already does
(AlterConstrUpdateConstraintEntry() followed by CCI), so there is
precedent for the CCI inside the ALTER CONSTRAINT recursion.

What I checked:

- Kahn's algorithm implementation looks right. Every non-root node
enters the agenda as somebody's child and gets indegree++ at that
moment, so indegrees are exactly the number of in-tree parents;
appending to a List while iterating it with foreach_oid() is
explicitly allowed by pg_list.h; dynahash entries do not move on
HASH_ENTER, so keeping "current" across the inner loop is fine.
Lock acquisition is identical to find_all_inheritors() (one
find_inheritance_children(lockmode) call per node).

- Regression: 243/243 pass (cassert build). I also confirmed that the
extended test really guards the ordering: if I swap the call site back
to find_all_inheritors() but keep the simplified tablecmds.c logic,
p1_c1 stays ENFORCED and the test fails, because BFS order visits
p1_c1 before p1/p2.

A few small things:

1. Stale comments left behind in tablecmds.c. The block comment above
the ATCheckCheckConstrHasEnforcedParent() call in
ATExecAlterCheckConstrEnforceability() still says "remains ENFORCED
and is not part of this ALTER" and "another parent outside this
ALTER may still enforce ... Partitions do not need this recursive
parent check". The "not part of this ALTER" qualification and the
word "recursive" no longer describe the code. Likewise,
ATCheckCheckConstrHasEnforcedParent() no longer recurses, so its
"Since this function recurses, it could be driven to stack overflow"
comment and the check_stack_depth() call can go.

2. OrderedSeenRelsEntry is missing from src/tools/pgindent/typedefs.list
(that is why pgindent produced "} OrderedSeenRelsEntry;"
instead of "} OrderedSeenRelsEntry;"). Adding it fixes the layout.

3. Possible simplifications in find_all_inheritors_ordered():

- The root is the only node that can have indegree 0 (see above), so
the loop over agenda looking for zero-indegree nodes can be
replaced by worklist = list_make1_oid(parentrelId), perhaps with an
Assert or a comment explaining why.

- "ordered" is always identical to "worklist": nodes are appended to
worklist in exactly the order they are emitted. You could drop
"ordered" and just list_copy(worklist) into the caller's context.

Other than the comment cleanup, this looks good to me.

[1] /messages/by-id/E74C57FA-1DD0-4C8E-8FB1-538034752592@gmail.com

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

--
Regards,
Ewan Young

On Fri, 04 Sep 2026, Ewan Young <kdbase.hack@gmail.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.

On Sep 5, 2026, at 05:48, Zsolt Parragi <zsolt.parragi@percona.com> wrote:

On Fri, 04 Sep 2026, Ewan Young <kdbase.hack@gmail.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/

On Mon, 07 Sep 2026, Chao Li <li.evan.chao@gmail.com> wrote:

My understanding is that PG doesn’t intend to support cyclic inheritance. The code explicitly rejects it:

To me it seems like that it discourages it and tries to prevent it where it's possible to do so with reasonable effort, but it ends up trying to support it because it's a valid scenario that can happen in some workloads (as long as that also doesn't require too much effort).

A cycle can cause it to exceed the stack depth limit, so it is reasonable to fail the command when a cycle is detected.

Or it might succeed in other cases.

Here's a repro with an isolation test. Perm 1 fails on master, works with the patch. Perm 2 works on master, fails with the patch.
We could improve this by only using the new function in the enforced direction, I don't have a better idea currently. With that, the patched behavior would be the same as on master.

setup
{
CREATE TABLE r (x int CONSTRAINT cc CHECK (x > 0));
CREATE TABLE a (x int CONSTRAINT cc CHECK (x > 0));
CREATE TABLE b (x int CONSTRAINT cc CHECK (x > 0));
CREATE TABLE c (x int CONSTRAINT cc CHECK (x > 0));
CREATE TABLE d (x int CONSTRAINT cc CHECK (x > 0));
ALTER TABLE a INHERIT r;
ALTER TABLE b INHERIT a;
ALTER TABLE d INHERIT c;
}

teardown
{
DROP TABLE IF EXISTS r, a, b, c, d CASCADE;
}

session s1
step s1b { BEGIN; }
step s1i { ALTER TABLE c INHERIT b; }
step s1c { COMMIT; }

session s2
step s2b { BEGIN; }
step s2i { ALTER TABLE a INHERIT d; }
step s2c { COMMIT; }

session s3
step s3pre { ALTER TABLE r ALTER CONSTRAINT cc NOT ENFORCED;
ALTER TABLE c ALTER CONSTRAINT cc NOT ENFORCED; }
step s3e { SELECT inhrelid::regclass::text AS child,
inhparent::regclass::text AS parent
FROM pg_inherits
WHERE inhrelid::regclass::text IN ('r','a','b','c','d')
ORDER BY 1, 2; }
step s3not { ALTER TABLE r ALTER CONSTRAINT cc NOT ENFORCED; }
step s3enf { ALTER TABLE r ALTER CONSTRAINT cc ENFORCED; }
step s3s { SELECT conrelid::regclass::text AS rel, conenforced
FROM pg_constraint
WHERE conname = 'cc'
AND conrelid::regclass::text IN ('r','a','b','c','d')
ORDER BY 1; }

permutation s1b s2b s1i s2i s1c s2c s3e s3not s3s
permutation s1b s2b s3pre s1i s2i s1c s2c s3e s3enf s3s

Zsolt Parragi <zsolt.parragi@percona.com> writes:

On Mon, 07 Sep 2026, Chao Li <li.evan.chao@gmail.com> wrote:

My understanding is that PG doesn’t intend to support cyclic inheritance. The code explicitly rejects it:

To me it seems like that it discourages it and tries to prevent it
where it's possible to do so with reasonable effort, but it ends up
trying to support it because it's a valid scenario that can happen in
some workloads (as long as that also doesn't require too much effort).

Why is it a valid scenario, and how would we reach it? It's going to
cause tons of problems if it can happen, so I'd rather put effort into
blocking it than making some parts of the system cope.

I have a different concern about the patch as it stands: the
data-gathering part is unnecessarily duplicative of
find_all_inheritors. It does its best to look like it's doing
something different, but actually it computes exactly the same list
of relation OIDs and the same number-of-parents data. And indeed
it had better be doing the same things in the same order, because
otherwise we'd be risking deadlock failures instead of simple
blocking when two processes are acquiring exclusive locks on
overlapping inheritance trees. (Note the comment about "we need to be
sure all backends lock children in the same order to avoid needless
deadlocks" in find_inheritance_children.) I don't like having two
independent implementations that are invisibly tied like that: if
they diverge, we might not notice until somebody makes a bug report
and somebody else figures out what's causing the deadlock. So IMO
those two functions need to be revised to use a common data-gathering
step.

regards, tom lane

On Sep 8, 2026, at 06:16, Zsolt Parragi <zsolt.parragi@percona.com> wrote:

On Mon, 07 Sep 2026, Chao Li <li.evan.chao@gmail.com> wrote:

My understanding is that PG doesn’t intend to support cyclic inheritance. The code explicitly rejects it:

To me it seems like that it discourages it and tries to prevent it
where it's possible to do so with reasonable effort, but it ends up
trying to support it because it's a valid scenario that can happen in
some workloads (as long as that also doesn't require too much effort).

I think an important problem is that, in your earlier example, two users independently execute ALTER TABLE … INHERIT, but the commands together create an inheritance cycle without either user being notified. Even if PG currently tolerates this, I think preventing it would be preferable.

As Tom pointed out, cycles can also cause problems elsewhere in the system. So I agree that we should investigate whether we can prevent their creation at a reasonable cost.

A cycle can cause it to exceed the stack depth limit, so it is reasonable to fail the command when a cycle is detected.

Or it might succeed in other cases.

Here's a repro with an isolation test. Perm 1 fails on master, works
with the patch. Perm 2 works on master, fails with the patch.
We could improve this by only using the new function in the enforced
direction, I don't have a better idea currently. With that, the
patched behavior would be the same as on master.

This is a valid point. ENFORCED doesn’t need to check parents’ enforceability, so we can still use find_all_inheritors() to tolerate potential cycles and use find_all_inheritors_ordered() only for NOT ENFORCED. This preserves master’s success/failure outcomes in your test, while replacing the stack-depth error with an explicit cycle error. I have updated the code in v3.

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

On Sep 8, 2026, at 07:38, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Zsolt Parragi <zsolt.parragi@percona.com> writes:

On Mon, 07 Sep 2026, Chao Li <li.evan.chao@gmail.com> wrote:

My understanding is that PG doesn’t intend to support cyclic inheritance. The code explicitly rejects it:

To me it seems like that it discourages it and tries to prevent it
where it's possible to do so with reasonable effort, but it ends up
trying to support it because it's a valid scenario that can happen in
some workloads (as long as that also doesn't require too much effort).

Why is it a valid scenario, and how would we reach it? It's going to
cause tons of problems if it can happen, so I'd rather put effort into
blocking it than making some parts of the system cope.

+1

I can look into if we can prevent concurrent ALTER TABLE ... INHERIT commands from creating cycles at a reasonable cost, and start a separate discussion.

I have a different concern about the patch as it stands: the
data-gathering part is unnecessarily duplicative of
find_all_inheritors. It does its best to look like it's doing
something different, but actually it computes exactly the same list
of relation OIDs and the same number-of-parents data. And indeed
it had better be doing the same things in the same order, because
otherwise we'd be risking deadlock failures instead of simple
blocking when two processes are acquiring exclusive locks on
overlapping inheritance trees. (Note the comment about "we need to be
sure all backends lock children in the same order to avoid needless
deadlocks" in find_inheritance_children.) I don't like having two
independent implementations that are invisibly tied like that: if
they diverge, we might not notice until somebody makes a bug report
and somebody else figures out what's causing the deadlock. So IMO
those two functions need to be revised to use a common data-gathering
step.

That’s a good point. In the initial version, I tried to avoid touching find_all_inheritors(), which resulted in some duplicate code. In v3, I have refactored the two functions to share the data-gathering and locking code.

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

On Tue, 08 Sep 2026, Chao Li <li.evan.chao@gmail.com> wrote:

Why is it a valid scenario, and how would we reach it? It's going to
cause tons of problems if it can happen, so I'd rather put effort into
blocking it than making some parts of the system cope.

+1

I can look into if we can prevent concurrent ALTER TABLE ... INHERIT commands from creating cycles at a reasonable cost, and start a separate discussion.

+1 for that, if it is doable, I didn't investigate it further than the comment's claim that it is too difficult.

I didn't want to say that I think it is a real-usable scenario, I meant valid as currently reachable (as showcased by the isolation tester spec I posted), that probably wasn't the best word to describe it.