Re: Introducing find_all_inheritors_ordered()

On Thu, Jul 30, 2026 at 4:35 PM Chao Li <li(dot)evan(dot)chao(at)gmail(dot)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] https://postgr.es/m/E74C57FA-1DD0-4C8E-8FB1-538034752592@gmail.com
>
> Best regards,
> --
> Chao Li (Evan)
> HighGo Software Co., Ltd.
> https://www.highgo.com/
>
>

--
Regards,
Ewan Young