Thread

1. [SQL/PGQ] Early pruning for GRAPH_TABLE path generation

   Junwang Zhao <zhjwpku@gmail.com> — 2026-05-09T07:25:03Z

   Hi hackers,
   
   In [1], Satya proposed a PoC to limit the total number of GRAPH_TABLE
   path combinations to prevent memory exhaustion. While I agree that
   path explosion is a real concern, I do not think we should impose such
   a limit before generate_queries_for_path_pattern_recurse(). In many
   cases, most candidate paths can be eliminated later by
   generate_query_for_graph_path().
   
   The current implementation has a different problem:
   generate_queries_for_path_pattern_recurse() first enumerates complete
   path combinations, and only later does generate_query_for_graph_path()
   check whether the selected edge elements actually connect the adjacent
   vertex elements. We can improve this by pruning infeasible path
   prefixes early during DFS.
   
   This patch adds an early feasibility check during DFS path
   construction. After appending a new path_element to the current
   prefix, we verify whether the prefix can still satisfy edge-vertex
   adjacency constraints:
     - if the new element is an edge, check it against any
   already-selected elements in the current prefix
     - if the new element is a vertex, check only the immediately preceding edge
   
   The second case is sufficient because repeated vertex variables are
   merged into a single path_factor before DFS begins. So appending a
   vertex only adds a new constraint to the edge directly before it in
   the factorized path. Any later edge referencing the same factor will
   be checked when that edge itself is appended.
   
   This does not change query generation semantics. It only avoids
   exploring full-length paths that would later be rejected by
   generate_query_for_graph_path().
   
   Using the property graph from [1]
   
   CREATE temp TABLE v1 (id int PRIMARY KEY, val int);
   CREATE temp TABLE v2 (id int PRIMARY KEY, val int);
   CREATE temp TABLE v3 (id int PRIMARY KEY, val int);
   CREATE temp TABLE v4 (id int PRIMARY KEY, val int);
   CREATE temp TABLE v5 (id int PRIMARY KEY, val int);
   CREATE temp TABLE v6 (id int PRIMARY KEY, val int);
   CREATE temp TABLE v7 (id int PRIMARY KEY, val int);
   CREATE temp TABLE v8 (id int PRIMARY KEY, val int);
   CREATE temp TABLE e1 (id int PRIMARY KEY, src int, dest int);
   CREATE temp TABLE e2 (id int PRIMARY KEY, src int, dest int);
   CREATE temp TABLE e3 (id int PRIMARY KEY, src int, dest int);
   CREATE temp TABLE e4 (id int PRIMARY KEY, src int, dest int);
   CREATE temp TABLE e5 (id int PRIMARY KEY, src int, dest int);
   CREATE temp TABLE e6 (id int PRIMARY KEY, src int, dest int);
   CREATE temp TABLE e7 (id int PRIMARY KEY, src int, dest int);
   CREATE temp TABLE e8 (id int PRIMARY KEY, src int, dest int);
   CREATE PROPERTY GRAPH g5
       VERTEX TABLES (
           v1 LABEL vl PROPERTIES (id, val) LABEL vl2 PROPERTIES (id, val),
           v2 LABEL vl PROPERTIES (id, val),
           v3 LABEL vl PROPERTIES (id, val),
           v4 LABEL vl PROPERTIES (id, val),
           v5 LABEL vl PROPERTIES (id, val),
           v6 LABEL vl PROPERTIES (id, val),
           v7 LABEL vl PROPERTIES (id, val),
           v8 LABEL vl PROPERTIES (id, val)
       )
       EDGE TABLES (
           e1 SOURCE KEY (src) REFERENCES v1 (id) DESTINATION KEY (dest)
   REFERENCES v2 (id) LABEL el PROPERTIES (id),
           e2 SOURCE KEY (src) REFERENCES v2 (id) DESTINATION KEY (dest)
   REFERENCES v3 (id) LABEL el PROPERTIES (id),
           e3 SOURCE KEY (src) REFERENCES v3 (id) DESTINATION KEY (dest)
   REFERENCES v4 (id) LABEL el PROPERTIES (id),
           e4 SOURCE KEY (src) REFERENCES v4 (id) DESTINATION KEY (dest)
   REFERENCES v5 (id) LABEL el PROPERTIES (id),
           e5 SOURCE KEY (src) REFERENCES v5 (id) DESTINATION KEY (dest)
   REFERENCES v6 (id) LABEL el PROPERTIES (id),
           e6 SOURCE KEY (src) REFERENCES v6 (id) DESTINATION KEY (dest)
   REFERENCES v7 (id) LABEL el PROPERTIES (id),
           e7 SOURCE KEY (src) REFERENCES v7 (id) DESTINATION KEY (dest)
   REFERENCES v8 (id) LABEL el PROPERTIES (id),
           e8 SOURCE KEY (src) REFERENCES v8 (id) DESTINATION KEY (dest)
   REFERENCES v1 (id) LABEL el PROPERTIES (id)
       );
   
   SELECT count(*) FROM GRAPH_TABLE (g5 MATCH (a IS
   vl2)-[e1]->(b)-[e2]->(c)-[e3]->(d)-[e4]->(e) COLUMNS (a.id AS aid));
   
   head:
   
   # 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: 5388.629 ms (00:05.389)
   
   # 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: 5195.827 ms (00:05.196)
   
   patched:
   
   [local] zjw@postgres:5432-5924=# 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: 11.827 ms
   
   [local] zjw@postgres:5432-5924=# 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: 2.924 ms
   
   As you can see, the results are quite promising.
   
   Unfortunately, I cannot attach the patch to this email because of
   company security policy restrictions (I will do so once I get my own
   Mac). If you are interested, please check [2] on GitHub.
   
   [1] https://www.postgresql.org/message-id/flat/CAHg%2BQDfDwcM4%3DDSiAV6Ly89YQ5EcMhzO1-9x%3DmGG1WJzODcAig%40mail.gmail.com
   [2] https://github.com/zhjwpku/postgres/commit/bdc1c7ea9729285f105e650c0f5bd032802a85d8
   
   -- 
   Regards
   Junwang Zhao
   
   
   
   

2. Re: [SQL/PGQ] Early pruning for GRAPH_TABLE path generation

   Henson Choi <assam258@gmail.com> — 2026-05-09T14:52:16Z

   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], 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] 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]
   https://www.postgresql.org/message-id/CAHg%2BQDe8JU%2BERqA2xwjrg_ZptvH_v0T6PS9_P_ZgyYzD5h-Grw%40mail.gmail.com
   [2]
   https://www.postgresql.org/message-id/flat/20230625.210509.1276733411677577841.t-ishii%40sranhm.sra.co.jp
   

3. Re: [SQL/PGQ] Early pruning for GRAPH_TABLE path generation

   Junwang Zhao <zhjwpku@gmail.com> — 2026-05-12T00:57:09Z

   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] https://www.postgresql.org/message-id/CAHg%2BQDe8JU%2BERqA2xwjrg_ZptvH_v0T6PS9_P_ZgyYzD5h-Grw%40mail.gmail.com
   > [2] https://www.postgresql.org/message-id/flat/20230625.210509.1276733411677577841.t-ishii%40sranhm.sra.co.jp
   
   
   
   -- 
   Regards
   Junwang Zhao
   

4. Re: [SQL/PGQ] Early pruning for GRAPH_TABLE path generation

   Henson Choi <assam258@gmail.com> — 2026-05-12T10:28:02Z

   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 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]
   > https://www.postgresql.org/message-id/CAHg%2BQDe8JU%2BERqA2xwjrg_ZptvH_v0T6PS9_P_ZgyYzD5h-Grw%40mail.gmail.com
   > > [2]
   > https://www.postgresql.org/message-id/flat/20230625.210509.1276733411677577841.t-ishii%40sranhm.sra.co.jp
   >
   >
   >
   > --
   > Regards
   > Junwang Zhao
   >
   

5. Re: [SQL/PGQ] Early pruning for GRAPH_TABLE path generation

   Junwang Zhao <zhjwpku@gmail.com> — 2026-05-13T14:20:01Z

   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] https://www.postgresql.org/message-id/CAHg%2BQDe8JU%2BERqA2xwjrg_ZptvH_v0T6PS9_P_ZgyYzD5h-Grw%40mail.gmail.com
   >> > [2] https://www.postgresql.org/message-id/flat/20230625.210509.1276733411677577841.t-ishii%40sranhm.sra.co.jp
   >>
   >>
   >>
   >> --
   >> Regards
   >> Junwang Zhao
   
   
   
   --
   Regards
   Junwang Zhao
   

6. Re: [SQL/PGQ] Early pruning for GRAPH_TABLE path generation

   Henson Choi <assam258@gmail.com> — 2026-05-13T16:32:25Z

   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
   

7. Re: [SQL/PGQ] Early pruning for GRAPH_TABLE path generation

   Junwang Zhao <zhjwpku@gmail.com> — 2026-05-14T00:38:41Z

   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
   
   
   
   

8. Re: [SQL/PGQ] Early pruning for GRAPH_TABLE path generation

   Ashutosh Bapat <ashutosh.bapat.oss@gmail.com> — 2026-05-14T06:25:51Z

   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
   
   
   
   

9. Re: [SQL/PGQ] Early pruning for GRAPH_TABLE path generation

   Junwang Zhao <zhjwpku@gmail.com> — 2026-05-14T15:30:46Z

   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