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

Hi Henson,

On Tue, May 12, 2026 at 6:28 PM Henson Choi <assam258(at)gmail(dot)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(at)gmail(dot)com>님이 작성:
>>
>> Hi Henson,
>>
>> On Sat, May 9, 2026 at 10:52 PM Henson Choi <assam258(at)gmail(dot)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