[SQL/PGQ] Early pruning for GRAPH_TABLE path generation

Hi Junwang,

Thanks for an interesting thread, and for picking this up — it has
been a useful occasion to re-examine assumptions I had carried over
from a different graph model.

My background is on AgensGraph, where labels form an inheritance
hierarchy (rather than Neo4j-style multi-label tag sets), so a path
pattern rewrites against a single parent table per position and the
fan-out across labels is left to the planner's existing inheritance
machinery. The rewriter never enumerates per-element combinations, so
an N^K blow-up like Satya's was simply not on the radar there.

SQL/PGQ instead designates graph identity through the schema itself,
so each pattern position carries a set of candidate element tables
and the rewriter has to materialize each schema-feasible join
combination — a (vertex, edge, vertex, ...) sequence of element
tables — as its own SELECT branch, with all such branches joined by
UNION ALL. The number of *feasible* join combinations is bounded by
the schema graph's connectivity and is usually small; the current
rewriter's naive shape, however, is to enumerate the full N^K
candidate space first and reject infeasible combinations only
afterwards. The patch tackles exactly that part.

To be clear, I do not mean this as a criticism of the original
implementer. For sizeable features I tend to prefer a deliberately
naive implementation first — getting the full functionality working
end-to-end before optimizing — and that approach is even more
valuable in team settings, since a working baseline lets additional
contributors join much earlier. The current shape of
generate_queries_for_path_pattern_recurse() reads exactly like such a
baseline, and this patch is precisely the kind of focused follow-up
improvement it invites.

When I thought about this independently, I had reached for the dual
formulation — "extend the prefix only along feasible edges" rather
than "enumerate everything and prune" — and my intuition was that the
two should produce the same surviving set, though I have not worked
that through rigorously. Either way, your "early pruning" framing is
the better one for the patch itself: it stays close to the existing
code structure and lets the change read as a small refinement of
generate_queries_for_path_pattern_recurse() rather than a
reorganization of how candidates are walked. That makes review and
incremental landing materially easier.

The same reframing also explains, after the fact, why the discrepancy
between Ashutosh's quick runs and Satya's 81 GB case was so large:
the cost being measured is in large part infeasible enumeration,
which a forward-moved check eliminates regardless of pattern length
or schema size in realistic graphs.

I have not gone through the patch at the code level yet, but the
shape of the problem and of your fix is clear enough from the
description. My personal take, with that caveat, is that early
pruning, together with the CHECK_FOR_INTERRUPTS that Satya already
proposed in the earlier thread [1]/messages/by-id/CAHg+QDe8JU+ERqA2xwjrg_ZptvH_v0T6PS9_P_ZgyYzD5h-Grw@mail.gmail.com, feels like the right pair to
land first; the explicit hard limit, in turn, is probably best
revisited only if a real case turns up where even those two combined
are not enough. That keeps the immediate change narrow and
semantics-preserving while leaving the policy question open for
evidence rather than upfront estimation.

There is a fairly recent precedent in PostgreSQL itself that I think
supports this ordering. I have been following — and participating in
— Tatsuo Ishii's Row Pattern Recognition thread [2]/messages/by-id/20230625.210509.1276733411677577841.t-ishii@sranhm.sra.co.jp since earlier
this year, and that work ran into a structurally similar concern: in
its earlier implementation the engine could undergo a combinatorial
explosion of pattern-candidate states. A memory-based limit was
floated as one mitigation, but it never actually converged into a
design — the conversation around an explicit limit simply faded out
as a layered set of pruning and early-termination rules accumulated
incrementally and brought the state space back under control. CFI
and stack-depth checks, by contrast, were treated as independently
necessary throughout and stayed in the design.

The shape of this thread feels analogous, and the same staged
approach (structural fix + CFI first, hard limit only if a residual
case genuinely demands it) is, I suspect, what will hold up
here as well.

I'll set aside time separately to do a proper line-by-line review and
follow up.

Regards,
Henson

[1]: /messages/by-id/CAHg+QDe8JU+ERqA2xwjrg_ZptvH_v0T6PS9_P_ZgyYzD5h-Grw@mail.gmail.com
/messages/by-id/CAHg+QDe8JU+ERqA2xwjrg_ZptvH_v0T6PS9_P_ZgyYzD5h-Grw@mail.gmail.com
[2]: /messages/by-id/20230625.210509.1276733411677577841.t-ishii@sranhm.sra.co.jp
/messages/by-id/20230625.210509.1276733411677577841.t-ishii@sranhm.sra.co.jp

Hi Henson,

On Sat, May 9, 2026 at 10:52 PM Henson Choi <assam258@gmail.com> wrote:

Hi Junwang,

Thanks for an interesting thread, and for picking this up — it has
been a useful occasion to re-examine assumptions I had carried over
from a different graph model.

My background is on AgensGraph, where labels form an inheritance
hierarchy (rather than Neo4j-style multi-label tag sets), so a path
pattern rewrites against a single parent table per position and the
fan-out across labels is left to the planner's existing inheritance
machinery. The rewriter never enumerates per-element combinations, so
an N^K blow-up like Satya's was simply not on the radar there.

Thanks for the input, good to know.

SQL/PGQ instead designates graph identity through the schema itself,
so each pattern position carries a set of candidate element tables
and the rewriter has to materialize each schema-feasible join
combination — a (vertex, edge, vertex, ...) sequence of element
tables — as its own SELECT branch, with all such branches joined by
UNION ALL. The number of *feasible* join combinations is bounded by
the schema graph's connectivity and is usually small; the current
rewriter's naive shape, however, is to enumerate the full N^K
candidate space first and reject infeasible combinations only
afterwards. The patch tackles exactly that part.

To be clear, I do not mean this as a criticism of the original
implementer. For sizeable features I tend to prefer a deliberately
naive implementation first — getting the full functionality working
end-to-end before optimizing — and that approach is even more
valuable in team settings, since a working baseline lets additional
contributors join much earlier. The current shape of
generate_queries_for_path_pattern_recurse() reads exactly like such a
baseline, and this patch is precisely the kind of focused follow-up
improvement it invites.

When I thought about this independently, I had reached for the dual
formulation — "extend the prefix only along feasible edges" rather
than "enumerate everything and prune" — and my intuition was that the
two should produce the same surviving set, though I have not worked
that through rigorously. Either way, your "early pruning" framing is
the better one for the patch itself: it stays close to the existing
code structure and lets the change read as a small refinement of
generate_queries_for_path_pattern_recurse() rather than a
reorganization of how candidates are walked. That makes review and
incremental landing materially easier.

The same reframing also explains, after the fact, why the discrepancy
between Ashutosh's quick runs and Satya's 81 GB case was so large:
the cost being measured is in large part infeasible enumeration,
which a forward-moved check eliminates regardless of pattern length
or schema size in realistic graphs.

I have not gone through the patch at the code level yet, but the
shape of the problem and of your fix is clear enough from the
description. My personal take, with that caveat, is that early
pruning, together with the CHECK_FOR_INTERRUPTS that Satya already
proposed in the earlier thread [1], feels like the right pair to
land first; the explicit hard limit, in turn, is probably best
revisited only if a real case turns up where even those two combined
are not enough. That keeps the immediate change narrow and
semantics-preserving while leaving the policy question open for
evidence rather than upfront estimation.

Agreed, I add a CHECK_FOR_INTERRUPTS to the patch now, see
the attached.

There is a fairly recent precedent in PostgreSQL itself that I think
supports this ordering. I have been following — and participating in
— Tatsuo Ishii's Row Pattern Recognition thread [2] since earlier
this year, and that work ran into a structurally similar concern: in
its earlier implementation the engine could undergo a combinatorial
explosion of pattern-candidate states. A memory-based limit was
floated as one mitigation, but it never actually converged into a
design — the conversation around an explicit limit simply faded out
as a layered set of pruning and early-termination rules accumulated
incrementally and brought the state space back under control. CFI
and stack-depth checks, by contrast, were treated as independently
necessary throughout and stayed in the design.

The shape of this thread feels analogous, and the same staged
approach (structural fix + CFI first, hard limit only if a residual
case genuinely demands it) is, I suspect, what will hold up
here as well.

Thanks for the insightful analysis, it's extremely helpful.

I'll set aside time separately to do a proper line-by-line review and
follow up.

Regards,
Henson

[1] /messages/by-id/CAHg+QDe8JU+ERqA2xwjrg_ZptvH_v0T6PS9_P_ZgyYzD5h-Grw@mail.gmail.com
[2] /messages/by-id/20230625.210509.1276733411677577841.t-ishii@sranhm.sra.co.jp

--
Regards
Junwang Zhao

Hi Junwang,

Thanks for the v1 patch -- I walked through it carefully. The
direction holds up well; the notes below are non-blocking, with one
concrete request and a handful of nits.

## On the approach

"Enumerate and prune early" is the right shape for a first cut:
the DFS keeps its existing structure, and we just stop extending a
prefix as soon as the newly appended element makes adjacency
impossible. Label/kind filtering already keeps slot sizes small in
typical cases, so a structural fix at the DFS boundary captures the
remaining blow-up without reshuffling the candidate set itself.

Glad to see CHECK_FOR_INTERRUPTS folded in alongside the structural
fix -- that pairing alone should be enough; a hard limit only needs
to come back if a residual case demands it.

## On correctness

The DFS is a nested loop: outer picks a vertex for the vertex slot,
inner picks an edge for the adjacent edge slot. The new helper just
compares vertex.elemoid against edge.srcvertexid/destvertexid -- both
catalog-derived, fixed before the DFS starts. The pre-patch code
evaluates the same equality at the end of the full N x M x ...
expansion (via edge_qual == NULL in generate_query_for_graph_path);
the patch hoists it into the inner loop body. Same equality, same
surviving set. Direction handling is preserved the same way --
reverse_ok starts true only for EDGE_PATTERN_ANY, so the undirected
case keeps its src<->dest cross comparison.

The patch is also stack-neutral: both pre-existing recursive
functions already carry check_stack_depth() at entry
(generate_queries_for_path_pattern_recurse,
generate_setop_from_pathqueries), and the new helpers are
non-recursive.

## One request: regression test

Three cases would together cover the new code paths well:

1. A long chain pattern that survives pruning but used to enumerate
the full N^K product (the g5 chain from your benchmark is a
natural fit). Not currently covered in
src/test/regress/sql/graph_table.sql -- worth adding.

2. A cyclic variant whose closing edge has both endpoints already
in the prefix -- this is the only path that fires both if-blocks
of graph_path_edge_is_feasible() simultaneously. Already covered
by the existing `(a)-[b]->(a)-[b]->(a)` tests in graph_table.sql,
since same-name vertex patterns are merged into a single path
factor before DFS; worth noting in the commit message rather
than adding a new test.

3. A pattern where an edge slot has all its candidates pruned --
to cover the empty-pathqueries route into
generate_query_for_empty_path_pattern(). Already covered by the
reversed-direction `MATCH (o IS orders)-[IS customer_orders]->
(c IS customers)` test in graph_table.sql, which yields zero
rows because no edge in the catalog satisfies that adjacency.
Same note: worth flagging as newly reachable via pruning.

## Nits (all stylistic -- feel free to skip)

1. In graph_path_prefix_is_feasible_with_new_element(), the
`if (!IS_EDGE_PATTERN(prev_pe->path_factor->kind)) return true;`
branch is unreachable -- gram.y enforces V-E alternation, and
the path-factor linkage code in
generate_queries_for_path_pattern() re-asserts it. Tightening
to `Assert(IS_EDGE_PATTERN(...))` would match the rest of the
file.

2. `normal_ok` / `reverse_ok` reads slightly off from this file's
diction. Consider `feasible` / `rev_feasible` -- the asymmetric
`rev_` prefix matches the existing `edge_qual` / `rev_edge_qual`
in generate_query_for_graph_path(), and echoes the function name
itself.

3. A one-line comment above the V-E alternation check (whether
kept as `if` or tightened per nit 1) citing parse analysis would
save the next reader a trip through gram.y.

4. In the prune branch of generate_queries_for_path_pattern_recurse(),
a one-liner noting that an exhausted level returns an empty list,
which the caller routes to generate_query_for_empty_path_pattern(),
would help -- pre-existing behavior, but far more reachable after
the patch.

## On the trailing edge_qual guard

The `if (edge_qual == NULL) return NULL;` in
generate_query_for_graph_path() becomes unreachable after the patch,
but worth keeping as a defensive backstop -- it is the literal dual
of the helper's check, and removing it would only tighten coupling
for no measurable gain. A short comment marking it as such would help.

Regards,
Henson

2026년 5월 12일 (화) 오전 9:57, Junwang Zhao <zhjwpku@gmail.com>님이 작성:

Hi Henson,

On Tue, May 12, 2026 at 6:28 PM Henson Choi <assam258@gmail.com> wrote:

Hi Junwang,

Thanks for the v1 patch -- I walked through it carefully. The
direction holds up well; the notes below are non-blocking, with one
concrete request and a handful of nits.

## On the approach

"Enumerate and prune early" is the right shape for a first cut:
the DFS keeps its existing structure, and we just stop extending a
prefix as soon as the newly appended element makes adjacency
impossible. Label/kind filtering already keeps slot sizes small in
typical cases, so a structural fix at the DFS boundary captures the
remaining blow-up without reshuffling the candidate set itself.

Glad to see CHECK_FOR_INTERRUPTS folded in alongside the structural
fix -- that pairing alone should be enough; a hard limit only needs
to come back if a residual case demands it.

## On correctness

The DFS is a nested loop: outer picks a vertex for the vertex slot,
inner picks an edge for the adjacent edge slot. The new helper just
compares vertex.elemoid against edge.srcvertexid/destvertexid -- both
catalog-derived, fixed before the DFS starts. The pre-patch code
evaluates the same equality at the end of the full N x M x ...
expansion (via edge_qual == NULL in generate_query_for_graph_path);
the patch hoists it into the inner loop body. Same equality, same
surviving set. Direction handling is preserved the same way --
reverse_ok starts true only for EDGE_PATTERN_ANY, so the undirected
case keeps its src<->dest cross comparison.

The patch is also stack-neutral: both pre-existing recursive
functions already carry check_stack_depth() at entry
(generate_queries_for_path_pattern_recurse,
generate_setop_from_pathqueries), and the new helpers are
non-recursive.

Thanks for the correctness analysis.

## One request: regression test

Three cases would together cover the new code paths well:

1. A long chain pattern that survives pruning but used to enumerate
the full N^K product (the g5 chain from your benchmark is a
natural fit). Not currently covered in
src/test/regress/sql/graph_table.sql -- worth adding.

Added as v2-0002.

2. A cyclic variant whose closing edge has both endpoints already
in the prefix -- this is the only path that fires both if-blocks
of graph_path_edge_is_feasible() simultaneously. Already covered
by the existing `(a)-[b]->(a)-[b]->(a)` tests in graph_table.sql,
since same-name vertex patterns are merged into a single path
factor before DFS; worth noting in the commit message rather
than adding a new test.

3. A pattern where an edge slot has all its candidates pruned --
to cover the empty-pathqueries route into
generate_query_for_empty_path_pattern(). Already covered by the
reversed-direction `MATCH (o IS orders)-[IS customer_orders]->
(c IS customers)` test in graph_table.sql, which yields zero
rows because no edge in the catalog satisfies that adjacency.
Same note: worth flagging as newly reachable via pruning.

I added the following paragraph to the commit message, feel free to
recommend wording.

The cyclic case where a closing edge has both endpoints already
in the prefix is already exercised by the existing same-variable
loop patterns in graph_table.sql (e.g. (a)-[b]->(a)-[b]->(a)),
because repeated vertex names are merged into a single path factor
before DFS. Likewise, the "all edge candidates pruned" path into
generate_query_for_empty_path_pattern() is already hit by the
MATCH (o IS orders)-[IS customer_orders]->(c IS customers) case,
where no catalog edge matches the declared direction; pruning just
makes those branches easier to reach. Neither case needs a
dedicated new test beyond what is already there.

## Nits (all stylistic -- feel free to skip)

1. In graph_path_prefix_is_feasible_with_new_element(), the
`if (!IS_EDGE_PATTERN(prev_pe->path_factor->kind)) return true;`
branch is unreachable -- gram.y enforces V-E alternation, and
the path-factor linkage code in
generate_queries_for_path_pattern() re-asserts it. Tightening
to `Assert(IS_EDGE_PATTERN(...))` would match the rest of the
file.

Yeah, for a pattern such as (a)-[e1]-(b)-[e2]-(a)-[e3]-(c), the path_factors
is V(a), E(e1), V(b), E(e2), E(e3), V(c), though not totally V-E alternation,
for a Vertex, we can sure that the prev_pe is always Edge, so changed
to Assert.

2. `normal_ok` / `reverse_ok` reads slightly off from this file's
diction. Consider `feasible` / `rev_feasible` -- the asymmetric
`rev_` prefix matches the existing `edge_qual` / `rev_edge_qual`
in generate_query_for_graph_path(), and echoes the function name
itself.

Changed.

3. A one-line comment above the V-E alternation check (whether
kept as `if` or tightened per nit 1) citing parse analysis would
save the next reader a trip through gram.y.

I added the following, feel free to suggest wording.

/*
* Merged duplicate vertices only drop redundant factors from path_factors,
* not from the DFS path; preceding slot is always an edge for a vertex.
*/

4. In the prune branch of generate_queries_for_path_pattern_recurse(),
a one-liner noting that an exhausted level returns an empty list,
which the caller routes to generate_query_for_empty_path_pattern(),
would help -- pre-existing behavior, but far more reachable after
the patch.

Added, feel free to suggest wording.

## On the trailing edge_qual guard

The `if (edge_qual == NULL) return NULL;` in
generate_query_for_graph_path() becomes unreachable after the patch,
but worth keeping as a defensive backstop -- it is the literal dual
of the helper's check, and removing it would only tighten coupling
for no measurable gain. A short comment marking it as such would help.

Added.

Regards,
Henson

2026년 5월 12일 (화) 오전 9:57, Junwang Zhao <zhjwpku@gmail.com>님이 작성:

Hi Henson,

On Sat, May 9, 2026 at 10:52 PM Henson Choi <assam258@gmail.com> wrote:

Hi Junwang,

Thanks for an interesting thread, and for picking this up — it has
been a useful occasion to re-examine assumptions I had carried over
from a different graph model.

My background is on AgensGraph, where labels form an inheritance
hierarchy (rather than Neo4j-style multi-label tag sets), so a path
pattern rewrites against a single parent table per position and the
fan-out across labels is left to the planner's existing inheritance
machinery. The rewriter never enumerates per-element combinations, so
an N^K blow-up like Satya's was simply not on the radar there.

Thanks for the input, good to know.

SQL/PGQ instead designates graph identity through the schema itself,
so each pattern position carries a set of candidate element tables
and the rewriter has to materialize each schema-feasible join
combination — a (vertex, edge, vertex, ...) sequence of element
tables — as its own SELECT branch, with all such branches joined by
UNION ALL. The number of *feasible* join combinations is bounded by
the schema graph's connectivity and is usually small; the current
rewriter's naive shape, however, is to enumerate the full N^K
candidate space first and reject infeasible combinations only
afterwards. The patch tackles exactly that part.

To be clear, I do not mean this as a criticism of the original
implementer. For sizeable features I tend to prefer a deliberately
naive implementation first — getting the full functionality working
end-to-end before optimizing — and that approach is even more
valuable in team settings, since a working baseline lets additional
contributors join much earlier. The current shape of
generate_queries_for_path_pattern_recurse() reads exactly like such a
baseline, and this patch is precisely the kind of focused follow-up
improvement it invites.

When I thought about this independently, I had reached for the dual
formulation — "extend the prefix only along feasible edges" rather
than "enumerate everything and prune" — and my intuition was that the
two should produce the same surviving set, though I have not worked
that through rigorously. Either way, your "early pruning" framing is
the better one for the patch itself: it stays close to the existing
code structure and lets the change read as a small refinement of
generate_queries_for_path_pattern_recurse() rather than a
reorganization of how candidates are walked. That makes review and
incremental landing materially easier.

The same reframing also explains, after the fact, why the discrepancy
between Ashutosh's quick runs and Satya's 81 GB case was so large:
the cost being measured is in large part infeasible enumeration,
which a forward-moved check eliminates regardless of pattern length
or schema size in realistic graphs.

I have not gone through the patch at the code level yet, but the
shape of the problem and of your fix is clear enough from the
description. My personal take, with that caveat, is that early
pruning, together with the CHECK_FOR_INTERRUPTS that Satya already
proposed in the earlier thread [1], feels like the right pair to
land first; the explicit hard limit, in turn, is probably best
revisited only if a real case turns up where even those two combined
are not enough. That keeps the immediate change narrow and
semantics-preserving while leaving the policy question open for
evidence rather than upfront estimation.

Agreed, I add a CHECK_FOR_INTERRUPTS to the patch now, see
the attached.

There is a fairly recent precedent in PostgreSQL itself that I think
supports this ordering. I have been following — and participating in
— Tatsuo Ishii's Row Pattern Recognition thread [2] since earlier
this year, and that work ran into a structurally similar concern: in
its earlier implementation the engine could undergo a combinatorial
explosion of pattern-candidate states. A memory-based limit was
floated as one mitigation, but it never actually converged into a
design — the conversation around an explicit limit simply faded out
as a layered set of pruning and early-termination rules accumulated
incrementally and brought the state space back under control. CFI
and stack-depth checks, by contrast, were treated as independently
necessary throughout and stayed in the design.

The shape of this thread feels analogous, and the same staged
approach (structural fix + CFI first, hard limit only if a residual
case genuinely demands it) is, I suspect, what will hold up
here as well.

Thanks for the insightful analysis, it's extremely helpful.

I'll set aside time separately to do a proper line-by-line review and
follow up.

Regards,
Henson

[1] /messages/by-id/CAHg+QDe8JU+ERqA2xwjrg_ZptvH_v0T6PS9_P_ZgyYzD5h-Grw@mail.gmail.com
[2] /messages/by-id/20230625.210509.1276733411677577841.t-ishii@sranhm.sra.co.jp

--
Regards
Junwang Zhao

--
Regards
Junwang Zhao

Hi Junwang,

Thanks for the quick turnaround on v2. Walked through it against the
prior notes -- everything reads well; one small thing on 0002 to fix
before the next spin, inline below.

1. A long chain pattern that survives pruning but used to enumerate

the full N^K product (the g5 chain from your benchmark is a
natural fit). Not currently covered in
src/test/regress/sql/graph_table.sql -- worth adding.

Added as v2-0002.

The g5 chain is a good fit. One nit: the comment above the SELECT
has a U+2192 arrow in both the .sql and the .out -- unless a regress
case is specifically exercising encoding, these stay ASCII-only, so
please replace with a plain `->` in both files.

I added the following paragraph to the commit message, feel free to
recommend wording.

The cyclic case where a closing edge has both endpoints already
in the prefix is already exercised by the existing same-variable
loop patterns in graph_table.sql (e.g. (a)-[b]->(a)-[b]->(a)),
because repeated vertex names are merged into a single path factor
before DFS. Likewise, the "all edge candidates pruned" path into
generate_query_for_empty_path_pattern() is already hit by the
MATCH (o IS orders)-[IS customer_orders]->(c IS customers) case,
where no catalog edge matches the declared direction; pruning just
makes those branches easier to reach. Neither case needs a
dedicated new test beyond what is already there.

Good.

## Nits (all stylistic -- feel free to skip)

1. In graph_path_prefix_is_feasible_with_new_element(), the
`if (!IS_EDGE_PATTERN(prev_pe->path_factor->kind)) return true;`
branch is unreachable -- gram.y enforces V-E alternation, and
the path-factor linkage code in
generate_queries_for_path_pattern() re-asserts it. Tightening
to `Assert(IS_EDGE_PATTERN(...))` would match the rest of the
file.

Yeah, for a pattern such as (a)-[e1]-(b)-[e2]-(a)-[e3]-(c), the
path_factors
is V(a), E(e1), V(b), E(e2), E(e3), V(c), though not totally V-E
alternation,
for a Vertex, we can sure that the prev_pe is always Edge, so changed
to Assert.

Thanks -- I hadn't realized path_factors isn't strictly V-E
alternating; your E(e2), E(e3) example pins down the actual
invariant the Assert relies on.

2. `normal_ok` / `reverse_ok` reads slightly off from this file's
diction. Consider `feasible` / `rev_feasible` -- the asymmetric
`rev_` prefix matches the existing `edge_qual` / `rev_edge_qual`
in generate_query_for_graph_path(), and echoes the function name
itself.

Changed.

3. A one-line comment above the V-E alternation check (whether
kept as `if` or tightened per nit 1) citing parse analysis would
save the next reader a trip through gram.y.

I added the following, feel free to suggest wording.

/*
* Merged duplicate vertices only drop redundant factors from path_factors,
* not from the DFS path; preceding slot is always an edge for a vertex.
*/

+1, and actually a better framing than the gram.y pointer I
originally suggested -- this is the invariant the Assert relies on.

4. In the prune branch of generate_queries_for_path_pattern_recurse(),
a one-liner noting that an exhausted level returns an empty list,
which the caller routes to generate_query_for_empty_path_pattern(),
would help -- pre-existing behavior, but far more reachable after
the patch.

Added, feel free to suggest wording.

Good.

## On the trailing edge_qual guard

The `if (edge_qual == NULL) return NULL;` in
generate_query_for_graph_path() becomes unreachable after the patch,
but worth keeping as a defensive backstop -- it is the literal dual
of the helper's check, and removing it would only tighten coupling
for no measurable gain. A short comment marking it as such would help.

Added.

Thanks.

With the ASCII fix in 0002, no further comments from my side.

Regards,
Henson

Hi Henson,

On Thu, May 14, 2026 at 12:32 AM Henson Choi <assam258@gmail.com> wrote:

Hi Junwang,

Thanks for the quick turnaround on v2. Walked through it against the
prior notes -- everything reads well; one small thing on 0002 to fix
before the next spin, inline below.

1. A long chain pattern that survives pruning but used to enumerate
the full N^K product (the g5 chain from your benchmark is a
natural fit). Not currently covered in
src/test/regress/sql/graph_table.sql -- worth adding.

Added as v2-0002.

The g5 chain is a good fit. One nit: the comment above the SELECT
has a U+2192 arrow in both the .sql and the .out -- unless a regress
case is specifically exercising encoding, these stay ASCII-only, so
please replace with a plain `->` in both files.

Agreed, I've applied the change in my machine, will wait for some more
comments and send a new version together later.

I added the following paragraph to the commit message, feel free to
recommend wording.

The cyclic case where a closing edge has both endpoints already
in the prefix is already exercised by the existing same-variable
loop patterns in graph_table.sql (e.g. (a)-[b]->(a)-[b]->(a)),
because repeated vertex names are merged into a single path factor
before DFS. Likewise, the "all edge candidates pruned" path into
generate_query_for_empty_path_pattern() is already hit by the
MATCH (o IS orders)-[IS customer_orders]->(c IS customers) case,
where no catalog edge matches the declared direction; pruning just
makes those branches easier to reach. Neither case needs a
dedicated new test beyond what is already there.

Good.

## Nits (all stylistic -- feel free to skip)

1. In graph_path_prefix_is_feasible_with_new_element(), the
`if (!IS_EDGE_PATTERN(prev_pe->path_factor->kind)) return true;`
branch is unreachable -- gram.y enforces V-E alternation, and
the path-factor linkage code in
generate_queries_for_path_pattern() re-asserts it. Tightening
to `Assert(IS_EDGE_PATTERN(...))` would match the rest of the
file.

Yeah, for a pattern such as (a)-[e1]-(b)-[e2]-(a)-[e3]-(c), the path_factors
is V(a), E(e1), V(b), E(e2), E(e3), V(c), though not totally V-E alternation,
for a Vertex, we can sure that the prev_pe is always Edge, so changed
to Assert.

Thanks -- I hadn't realized path_factors isn't strictly V-E
alternating; your E(e2), E(e3) example pins down the actual
invariant the Assert relies on.

2. `normal_ok` / `reverse_ok` reads slightly off from this file's
diction. Consider `feasible` / `rev_feasible` -- the asymmetric
`rev_` prefix matches the existing `edge_qual` / `rev_edge_qual`
in generate_query_for_graph_path(), and echoes the function name
itself.

Changed.

3. A one-line comment above the V-E alternation check (whether
kept as `if` or tightened per nit 1) citing parse analysis would
save the next reader a trip through gram.y.

I added the following, feel free to suggest wording.

/*
* Merged duplicate vertices only drop redundant factors from path_factors,
* not from the DFS path; preceding slot is always an edge for a vertex.
*/

+1, and actually a better framing than the gram.y pointer I
originally suggested -- this is the invariant the Assert relies on.

4. In the prune branch of generate_queries_for_path_pattern_recurse(),
a one-liner noting that an exhausted level returns an empty list,
which the caller routes to generate_query_for_empty_path_pattern(),
would help -- pre-existing behavior, but far more reachable after
the patch.

Added, feel free to suggest wording.

Good.

## On the trailing edge_qual guard

The `if (edge_qual == NULL) return NULL;` in
generate_query_for_graph_path() becomes unreachable after the patch,
but worth keeping as a defensive backstop -- it is the literal dual
of the helper's check, and removing it would only tighten coupling
for no measurable gain. A short comment marking it as such would help.

Added.

Thanks.

With the ASCII fix in 0002, no further comments from my side.

Will do, thanks :-)

Regards,
Henson

--
Regards
Junwang Zhao

Hi Junwang,
Thanks for working on this. The performance improvement is impressive.
I haven't verified it myself though at this time.

Henson said it right. The first version separately enumeration and
conversion clearly to keep things simple. Things like variable length
element patterns, embedded path patterns can change the way we
enumerate the paths. Whatever the enumeration method is failing early
is best strategy. However, the question is whether your implementation
of "failing early" is going to make it difficult implement the above
mentioned advanced features or simplify it or not affect those at all.
We need to think and discuss a bit.

Delaying "failing early" implementation till we implement those
features is safest strategy. If the lack of it makes the feature
prohibitively useless, we will need to implement it early and deal
with the difficulties it brings. But the examples so far are mostly
artificial, not practical. That doesn't make me feel like it's worth
taking the risk. There are many other bugs that need to be fixed.

I am very glad that this patch demonstrates that "failing early"
improves things significantly. So we will incorporate this strategy
sooner or later.

On Thu, May 14, 2026 at 6:08 AM Junwang Zhao <zhjwpku@gmail.com> wrote:

Some cosmetic comments on v2

+ if (list_length(graph_path) == 1)
+ return true;

I would move this earlier in the function, to make it more readable.

rev_feasible is clever, but may need more comments.

How do we make sure that the edge direction checks in
generate_query_for_graph_path and graph_path_edge_is_feasible remain
consistent? What I had in mind instead was to start constructing Join
tree while we are creating paths so that edge direction feasibility
checks also create the edge connection quals avoiding the duplicate
logic. However, we will need to make sure that any unusable objects we
create during that process are discarded in time.

It will be better to place CHECK_FOR_INTERRUPTS alongside stack depth
check. But for it to be added there, we need an evidence that the
function is really consuming a lot of time. Your earlier measurements
hint towards that, but they are overall query times. Can you please
share actual time spent in this function out of the total execution
time?

If you separate CHECK_FOR_INTERRUPTS change as a separate patch, it
can be committed independent of the optimization.

--
Best Wishes,
Ashutosh Bapat

Hi Ashutosh,

On Thu, May 14, 2026 at 2:26 PM Ashutosh Bapat
<ashutosh.bapat.oss@gmail.com> wrote:

Hi Junwang,
Thanks for working on this. The performance improvement is impressive.
I haven't verified it myself though at this time.

Henson said it right. The first version separately enumeration and
conversion clearly to keep things simple. Things like variable length
element patterns, embedded path patterns can change the way we
enumerate the paths. Whatever the enumeration method is failing early
is best strategy. However, the question is whether your implementation
of "failing early" is going to make it difficult implement the above
mentioned advanced features or simplify it or not affect those at all.
We need to think and discuss a bit.

Yeah, it makes sense to me.

Delaying "failing early" implementation till we implement those
features is safest strategy. If the lack of it makes the feature
prohibitively useless, we will need to implement it early and deal
with the difficulties it brings. But the examples so far are mostly
artificial, not practical. That doesn't make me feel like it's worth
taking the risk. There are many other bugs that need to be fixed.

I am very glad that this patch demonstrates that "failing early"
improves things significantly. So we will incorporate this strategy
sooner or later.

Sure, let's find out what's the best way.

On Thu, May 14, 2026 at 6:08 AM Junwang Zhao <zhjwpku@gmail.com> wrote:

Some cosmetic comments on v2

+ if (list_length(graph_path) == 1)
+ return true;

I would move this earlier in the function, to make it more readable.

Done in attached v3.

rev_feasible is clever, but may need more comments.

Added.

How do we make sure that the edge direction checks in
generate_query_for_graph_path and graph_path_edge_is_feasible remain
consistent? What I had in mind instead was to start constructing Join
tree while we are creating paths so that edge direction feasibility
checks also create the edge connection quals avoiding the duplicate
logic. However, we will need to make sure that any unusable objects we
create during that process are discarded in time.

It will be better to place CHECK_FOR_INTERRUPTS alongside stack depth
check. But for it to be added there, we need an evidence that the
function is really consuming a lot of time. Your earlier measurements
hint towards that, but they are overall query times. Can you please
share actual time spent in this function out of the total execution
time?

I added temporary time logs around the generate_queries_for_path_pattern_recurse
in generate_queries_for_path_pattern, and got the path expansion
time consuming.

query time:

[local] zjw@postgres:5432-97559=# SELECT count(*) FROM GRAPH_TABLE (g5
MATCH (a IS
vl2)-[e1]->(b)-[e2]->(c)-[e3]->(d)-[e4]->(e) COLUMNS (a.id AS aid));
count
-------
0
(1 row)

Time: 5577.000 ms (00:05.577)

path expansion time:

2026-05-14 23:22:41.513 CST [97559] LOG: GRAPH_TABLE path expansion
took 4648.482 ms and generated 1 path queries

If you separate CHECK_FOR_INTERRUPTS change as a separate patch, it
can be committed independent of the optimization.

That's v3-0001 now.

Summary:

v3-0001: adds CHECK_FOR_INTERRUPTS() in recursive graph path query
generation to keep query cancellation responsive on complex patterns.
v3-0002: adds temporary timing logs to measure performance during
GRAPH_TABLE path expansion, not to be committed.
v3-0003: the failing early(or early pruning) logic with comments resolved.
v3-0004: adds a test which enumerates the full N^K combinations before
the early pruning logic, with Henson's last comment resolved.

--
Best Wishes,
Ashutosh Bapat

--
Regards

Junwang Zhao