Early Pruning for GRAPH_TABLE Path Generation (SQL/PGQ)

Architectural Context

SQL/PGQ (SQL Property Graph Queries), landed as a feature in PostgreSQL's SQL-standard graph query surface, is implemented as a query rewriter: a GRAPH_TABLE (... MATCH pattern ...) expression is expanded into a UNION ALL of conventional SQL SELECT branches, one per schema-feasible assignment of element tables (vertex tables and edge tables) to the positions in the MATCH pattern. The executor itself never sees "graph" concepts — all of the graph semantics are discharged at rewrite time into relational joins against the underlying vertex/edge tables declared in CREATE PROPERTY GRAPH.

This design choice has an important consequence: the rewriter must enumerate, for a pattern of K positions where each position has up to N candidate element tables, up to N^K combinations. Only combinations whose edge tables' SOURCE/DESTINATION references are consistent with the adjacent vertex positions are actually schema-feasible — the rest correspond to joins that could never produce a row and are dropped. In realistic property graph schemas, the feasible set is small (bounded by the schema-graph's connectivity), but the candidate space is exponential in pattern length.

The Core Problem

The current implementation in generate_queries_for_path_pattern_recurse() takes a deliberately naive approach:

1. Walk the pattern positions via DFS, building up complete path-element tuples (full-length combinations) of (vertex-table, edge-table, vertex-table, ...).
2. After a complete combination is assembled, hand it to generate_query_for_graph_path(), which checks whether the edge tables' foreign-key endpoints actually match the vertex tables at the adjacent positions. Infeasible combinations are discarded here.

This is a classic "enumerate-then-filter" structure. Its cost is dominated by infeasible combinations that are built to full length only to be thrown away. On the reporter's cycle-of-8 schema (v1..v8, e1..e8 forming a directed ring) with a 5-position pattern (a)-[e1]->(b)-[e2]->(c)-[e3]->(d)-[e4]->(e) and one vertex label having two label bindings (so extra candidates at position a), the rewriter spends ~5.2 seconds constructing and rejecting combinations that a single-edge feasibility check would have killed instantly. This is the same class of pathology behind Satya's earlier 81 GB memory-consumption case on the related thread [1].

The Proposed Fix

Junwang Zhu's patch moves the edge/vertex adjacency feasibility check inside the DFS recursion, so infeasible prefixes are pruned before the DFS extends them. The rules are:

• When appending an edge element to the current prefix, check the edge's SOURCE/DESTINATION references against whichever vertex path_factors at adjacent positions are already bound in the prefix.
• When appending a vertex element, check it only against the immediately preceding edge.

The asymmetry is justified by a preprocessing step already present in the rewriter: repeated vertex variables (same name appearing at multiple positions) are merged into a single path_factor before DFS begins. This is crucial — it means once a vertex factor is bound, any later edge whose adjacency touches the same factor will see the already-bound vertex when that edge is checked at append time. Therefore, checking a vertex only against its immediately preceding edge is sufficient; any "downstream" edge referring back to this vertex factor will perform its own check on append.

The patch is explicitly semantics-preserving: the surviving set of generated SELECT branches is unchanged; only the traversal order and the moment of rejection change. The reported speedup on the demonstration query is roughly 450×–1800× (5196 ms → 2.9–11.8 ms), with the variance reflecting cache effects on a trivial final workload.

Relation to Satya's Earlier Proposal

On the prior thread [1], Satya proposed a hard upper bound on the total number of generated path combinations, imposed before generate_queries_for_path_pattern_recurse() runs, to prevent the 81 GB memory blow-up. Junwang's position is that such a cap is the wrong layer of defense: it operates on the raw candidate space (N^K), whereas the real problem is that we never needed to explore most of that space in the first place. Early pruning attacks the cause; a hard limit treats the symptom and introduces a user-visible policy decision (what limit, configurable how, error or truncate?).

Henson's reply reinforces this framing with two observations:

1. Schema design contrast with AgensGraph. In AgensGraph, labels form an inheritance hierarchy, so a pattern position rewrites to a single parent table and the planner's existing inheritance expansion handles fan-out. The N^K explosion is structurally absent. SQL/PGQ, by standards mandate, binds graph identity through the schema and gives each position a set of candidate element tables — so the rewriter unavoidably has a combinatorial enumeration to perform. This is not a bug to be capped; it is the shape of the problem, and the right response is a smart enumeration, not a truncated dumb one.

2. Precedent from Row Pattern Recognition. Henson points to Tatsuo Ishii's ongoing RPR thread [2], where an initially similar combinatorial-state-explosion concern was eventually resolved through an accumulation of structural pruning rules rather than a hard state-count limit. CHECK_FOR_INTERRUPTS and stack-depth checks stayed as independently-necessary safety nets; a numeric cap did not converge into a design.

The recommended landing order that emerges from the discussion is:

1. Early pruning (this patch) — structural, semantics-preserving.
2. CHECK_FOR_INTERRUPTS inside the recursion (from Satya's earlier thread) — safety net for any residual pathological schema.
3. A hard combination cap — deferred pending evidence that (1)+(2) are insufficient.

Dual Formulation: "Extend Along Feasible Edges"

Henson mentions having independently reached for a dual formulation — rather than "enumerate then prune," drive the DFS forward only along feasible extensions (i.e., given the currently bound vertex at position i, only iterate over edges whose SOURCE matches it when extending to position i+1). He conjectures this produces the same surviving set but has not proved it rigorously.

The two formulations are indeed equivalent in output for this problem, because the feasibility predicate is a conjunction of local adjacency constraints and the DFS explores each prefix once. The practical difference is that the dual formulation would require restructuring the candidate-iteration loop to be driven by the edge table's FK metadata rather than by the position's full candidate list — a larger code change. Henson explicitly endorses the "early pruning" framing as the better patch shape: a minimal diff against generate_queries_for_path_pattern_recurse() that reviewers can evaluate as a local refinement. This is a pragmatic review-ergonomics judgment, not a claim that one algorithm is inherently better.

Process and Patch-Submission Observation

The author notes he cannot attach the patch due to corporate security policy and links to a GitHub commit instead. This is a minor but recurring friction in pgsql-hackers — patches not submitted as attachments do not get picked up by the CFbot or the commitfest workflow — and will need to be resolved before the patch can move through normal review channels.

Outstanding Questions

• A line-by-line review has not yet been done; Henson committed to one as a follow-up.
• The interaction with repeated-edge variables (as opposed to repeated vertex variables, which the factorization handles) is not explicitly discussed in the patch description and warrants verification in review.
• Whether the immediate-predecessor-only check for vertex appends remains correct if the factorization preprocessor is ever changed should be documented as an invariant in a comment at the check site.