Re: [SQL/PGQ] Native executor for Graph query

*Classification: * Privacy: Basic Personal Data; Export Control:
Not Technical; National Security: Not National Security; Company
Classification: Not Applicable; Business or Private Data: Business data

Hello Henson,

While I agree this i a good way to improve the code and allow it to be
reused
in other plan nodes, I do not think now is the time for this, for three
reasons:

- Currently, this would only benefit GraphScanState. While I agree with the
WITH RECURSIVE argument and that the scope is outside this patch,
I think we can update GraphScanState after such a change is implemented.
This can also serve as an argument for such a change, that way we have
two (GraphScanState + WITH RECURSIVE) rather than one (
GraphScanState).
Moreover, waiting to get more eyes on the problem can only be beneficial
(see the last point).

- I would like us to first commit a working version and get feedback from
various real-world use cases before we try to optimize it with such a
change.
There are ways for us to lazy-init the frames when reached rather than all
at once (to reduce memory-foortprint). This would not solve the speed
issue,
but we can simply add the up/down fields to GraphScanState and move the
relevant code later when / if we want them on all PlanState.

- This patch submission seems like the wrong place (too niche) to
discuss a change on a structure this central.
Waiting for more input from more people should provide better
perspective on how such a change can be used in other PlanState-derived
nodes, and in the future.

Best regards,
Henri Gasc

On Thu, Sep 17, 2026 at 6:13 AM Henson Choi <assam258(at)gmail(dot)com> wrote:

> Hi Henri,
>
> > This series only implements the WALK syntax.
>
> Thanks for splitting this into separate files -- much easier to
> follow.
>
> I gave more thought to the spot I flagged in ExecInitGraphScan --
> every frame's inner_state is eagerly ExecInitNode'd up to
> max_graph_stack_depth (1001 by default), while explain.c only ever
> looks at frames[0] when printing the plan. I first thought "just
> delay ExecInitNode, keep the array" would be enough, but that only
> solves half the problem (the init cost) -- EXPLAIN ANALYZE would
> still report only frame 0's share. So here's a bigger structure I'd
> like to propose instead.
>
> How I understood the current structure
>
> One GraphScan handles a single quantified hop of the graph pattern,
> and inner_plan is the pre-planned, parameterized 1-hop expansion for
> it (taking the current vertex as a PARAM_EXEC, so it can use
> indexes).
>
> At execution time, GraphScanState keeps a frames[] array (each
> element a GraphDepthFrameData), and each element holds both
> inner_state (its own ExecInitNode(copyObject(inner_plan)) copy) and
> that depth's vertex/edge-property values together. The whole array
> is built at once in ExecInitGraphScan, regardless of how deep the
> traversal actually goes.
>
> The problem with this seems to be that two things of very different
> character -- inner_state, an expensive resource (a PlanState copy
> carrying locks and a subplan tree), and the vertex/edge-property
> values, which are cheap scalars -- are bundled together into one
> GraphDepthFrameData element. So the whole array ends up sized to
> the theoretical upper bound (max_graph_stack_depth) rather than the
> depth actually reached, and the expensive side (inner_state) gets
> built up to that same bound, on the same schedule as the cheap side.
>
> A structure I'd like to propose instead, briefly
>
> Splitting this into two separate concerns:
>
> First, factor "each depth needs its own copy of inner_plan" out into
> a generic PlanState-level mechanism. Add an up/down pointer pair to
> PlanState, letting a node thread its own PlanState copies into a
> chain, independent of lefttree/righttree.
>
> Second, keep the small scalar data -- "the vertex reached at this
> depth, and its edge properties" -- separate, since it has nothing to
> do with any PlanState. A lean GraphVidData array, owned by
> GraphScanState, indexed directly by depth and grown by repalloc
> (doubling) only when needed. This array only grows to the deepest
> point actually reached, independent of the up/down chain's length.
>
> Writing out how these two would actually move, step by step:
>
> Descending a depth (graph_push):
>
> 1. Look at the down pointer of the frame inner currently points to.
> 2. If down exists -- a copy already exists for this depth.
> Use it as-is and move inner there.
> 3. If down is NULL -- this depth is being reached for the first time.
> Make a new copy via graph_init_inner.
> Link it onto the end of the chain via up/down.
> Move inner there.
> 4. Either way, prepare this depth's slot in vids[].
> If it doesn't exist yet (past vids_capacity), repalloc-double it.
> Fill in the vertex key values and the edge properties that led
> here.
> 5. Set need_init to true.
> -- a marker for graph_step to call ExecReScan the first time it
> steps this frame (this part is unchanged from the current code).
>
> Backtracking (graph_backtrack):
>
> 1. Move inner one step toward up.
> 2. That's it -- the chain itself is never cut.
> Whatever was linked in via down stays there.
>
> Resetting for a new seed (graph_reset, graph_fetch_seed):
>
> 1. Backtrack repeatedly until inner reaches depth 0 (= inner_head).
> 2. No node in the chain gets freed.
> 3. Set need_init back to true on every frame made so far
> (vids[0..frames_reached-1]) -- they all need to ExecReScan
> against the new seed's vertex values.
> 4. When the traversal reaches the same depth again, it takes
> graph_push's step 2 (down already exists) and reuses it as-is.
>
> The pointer layout, drawn out
>
> What GraphScanState itself holds:
>
> GraphScanState
> inner_head ----> depth 0's PlanState copy (always exists, chain head)
> inner ----> the innermost depth's PlanState copy right now
> vids ----> GraphVidData[0 .. vids_capacity-1] (flat array)
> frames_reached = number of depths actually reached so far
>
> E.g. with the traversal currently at depth 2 (frames_reached = 3,
> i.e. depths 0/1/2 exist), the inner_head/down chain looks like this:
>
> inner_head inner
> | |
> v v
> PlanState(d0) PlanState(d1) PlanState(d2)
> <-up- <-up-
> -down-> -down->
> up = NULL up = d0 up = d1
> down = d1 down = d2 down = NULL
>
> Each arrow is just a pointer -- d0.down == d1, d1.up == d0, and so
> on, linked both ways. When graph_push first reaches a new depth, it
> links a new node onto the end of this chain and moves inner there.
> Backtracking just moves inner one step toward up without cutting the
> chain -- so when a later seed descends to the same depth again, it
> reuses the existing d1/d2 as-is.
>
> The vids array is entirely separate from this chain, indexed
> directly by depth number (kept ASCII-only so the columns don't get
> mangled in transit; the explanation is below the table):
>
> vids[0] vids[1] vids[2] vids[3]
> (depth 0) (depth 1) (depth 2) (reserved
> seed vertex vid, vidnull vid, vidnull via repalloc,
> no edge_props edge_props=e1 edge_props=e2 unused yet)
>
> |<--- frames_reached(=3) live entries --->|
>
> vids[0] is the seed vertex (depth 0, no incoming edge), and
> vids[1]/vids[2] are the vertex key and the incoming edge's
> properties (e1, e2) at each depth. vids[3] is just capacity
> vids_capacity already doubled into, not yet used by any depth --
> frames_reached(=3) means only vids[0..2] are "live" data.
>
> So the PlanState chain (an expensive resource -- locks, subplan
> trees) and the vids array (cheap scalar values) end up as two
> separate structures, each shaped for its own access pattern (a chain
> vs. a flat array).
>
> Struct changes needed, by struct
>
> PlanState (execnodes.h) -- add:
>
> up (PlanState *)
> down (PlanState *)
>
> GraphScanState (execnodes.h) -- drop ndepths/frames
> (GraphDepthFrameData *), add instead:
>
> inner_head (PlanState *)
> inner (PlanState *)
> vids (GraphVidData *)
> vids_capacity (int)
> frames_reached (int)
> eflags (int)
> frame_vid_width (int)
>
> GraphDepthFrameData (nodeGraphScan.h) -- retire it, replace with
> GraphVidData:
>
> vid_elem, vid_nkeys, vid, vidnull,
> edge_props, edge_propsnull, need_init (carried over as-is)
>
> drop the inner_state field
> (the PlanState.up/down chain takes its place)
>
> New functions that would target PlanState
>
> ExecShutdownPlanStateChain(PlanState *head)
> core-shared (execProcnode.c / executor.h)
>
> graph_init_inner(GraphScanState *node)
> internal to nodeGraphScan.c (static)
>
> ExecShutdownGraphScan(GraphScanState *node)
> nodeGraphScan.c / nodeGraphScan.h
>
> The struct members, one by one
>
> PlanState.up / PlanState.down
>
> Orthogonal to lefttree/righttree. A generic pair for
> when a node type needs to thread several of its own
> PlanState copies into a chain for its own reasons.
>
> Most node types would just leave these NULL. Nothing
> besides GraphScan would use it right now, but WITH
> RECURSIVE (mentioned below) looks like the same shape
> of problem, so it could reuse this field directly.
>
> GraphScanState.inner_head
>
> The depth-0 (seed) copy. Made once in ExecInitGraphScan
> and never freed until the node ends -- the chain head.
>
> Also where EXPLAIN would show the "Inner" child (this
> one spot now covers what used to be
> frames[0].inner_state in explain.c).
>
> GraphScanState.inner
>
> The current pointer to the innermost depth's copy for
> the path currently on the stack.
>
> NULL when cur_depth < 0 (a new seed is needed).
>
> GraphScanState.vids / vids_capacity / frames_reached
>
> The array of per-depth scalar data, its allocated size,
> and how many depths have actually been reached so far.
>
> frames_reached is both the live prefix length of this
> array and the current length of the up/down chain. When
> a new depth is first reached (graph_push), it would
> repalloc-double as needed.
>
> GraphScanState.eflags
>
> Storing the eflags ExecInitGraphScan received.
>
> graph_push needs to pass the same eflags when it
> ExecInitNode's a new copy later, during execution, but
> doesn't have it as a parameter at that point anymore, so
> it needs to be saved as a field.
>
> GraphScanState.frame_vid_width
>
> The widest of the seed key/source key/destination key
> widths. Used to size each depth's vid/vidnull arrays.
>
> Currently a local variable in ExecInitGraphScan
> (maxwidth), but graph_push would need it again too, so
> it'd make sense to move it to a field.
>
> The functions, one by one
>
> graph_init_inner(GraphScanState *node) -> PlanState *
>
> Would copyObject inner_plan and ExecInitNode one copy,
> returning it (NULL if inner_plan is NULL).
>
> ExecInitGraphScan would call it once for depth 0,
> graph_push once each time a new depth is first reached
> -- just pulling together what's currently duplicated in
> two places.
>
> ExecShutdownPlanStateChain(PlanState *head)
>
> Would take a whole up/down chain and do two things.
>
> (1) Call ExecShutdownNode on every element, giving each
> its own chance at asynchronous shutdown.
> (2) Roll every element's instrumentation into head's via
> InstrAggNode, except head's own.
>
> One thing to watch for here. ExplainNode only calls
> InstrEndLoop (right before printing) to finalize the
> cycle of the node it's about to print (head), at the
> spot with the "we haven't done ExecutorEnd yet" comment
> -- so any frame other than head would never get that
> call, and its last cycle would likely still be
> unfinalized (running=true) by the time this runs.
> Feeding that straight into InstrAggNode would probably
> hit its Assert(!add->running). Calling InstrEndLoop on
> each element first, before aggregating, should avoid
> that.
>
> This function shouldn't be GraphScan-specific -- putting
> it in the core (execProcnode.c) would let any node type
> that owns a PlanState chain and needs to roll it up at
> EXPLAIN time reuse it by just passing its own head.
>
> ExecShutdownGraphScan(GraphScanState *node)
>
> Would be one line:
> ExecShutdownPlanStateChain(node->inner_head).
>
> GraphScan would just say "here's where my chain starts"
> and hold no traversal/aggregation logic of its own.
>
> This would need a case T_GraphScanState hooked into
> execProcnode.c's ExecShutdownNode_walker switch -- the
> same hook Gather uses to merge parallel workers' stats
> into the leader's (called inside ExecutorRun, before
> ExplainPrintPlan).
>
> The rest of the functions
>
> Everything else -- ExecInitGraphScan, ExecEndGraphScan,
> ExecReScanGraphScan, graph_push, graph_fetch_seed, graph_step,
> graph_build_row, graph_build_edge_array, graph_bind_vertex_params and
> friends -- wouldn't be new, just mechanically changed from array
> indexing (frames[d]) to walking inner_head/inner and indexing
> vids[d].
>
> One thing worth flagging for graph_build_edge_array: indexing vids[]
> directly by cur_depth is safe (no risk of reading a leftover depth
> from an earlier, deeper traversal), but any new code that walks the
> up/down chain itself would need to bound its traversal by cur_depth
> (i.e. node->inner) -- since graph_reset only moves inner back and
> never cuts the chain, a frame left over from an earlier, deeper
> traversal could still be linked on via down.
>
> One more thing worth flagging. up/down would be a field on PlanState
> itself, so even though only GraphScan uses it, it gets added to
> every node type. That alone makes it a change worth reviewing
> carefully.
>
> That said, I'd like to point out what it buys in return. With
> up/down as a generic PlanState-level field, the instrumentation
> rollup ends up considerably simpler. ExecShutdownGraphScan can be
> just one line calling ExecShutdownPlanStateChain(node->inner_head)
> precisely because up/down isn't GraphScan's own, but a core mechanism
> reusable anywhere. GraphScan itself would need no traversal or
> aggregation logic beyond saying "here's where my chain starts" --
> if up/down were a GraphScan-only field, that traversal-plus-rollup
> logic would have to be written directly inside GraphScan's own code;
> pulling it out as a core mechanism would make that whole piece
> unnecessary.
>
> Weighed against adding two fields to PlanState, that amount of
> simplicity -- plus any other node type running into the same problem
> later being able to reuse it as-is -- makes me think this direction
> is the right one to take.
>
> Not urgent, just for reference -- the PlanState.up/down +
> ExecShutdownPlanStateChain combination above might also be useful
> for making WITH RECURSIVE actually execute depth-first. RecursiveUnion
> currently works by repeatedly filling a worktable, and SEARCH ... SET
> is handled at the parse_cte.c level by accumulating the path into an
> array column to sort by afterward (rather than changing the execution
> algorithm itself), so a genuinely depth-first execution would need
> something that parameterizes the recursive term per depth, creates it
> lazily, and backtracks -- which looks like roughly the same shape as
> what GraphScan uses here. That's well outside this patch's scope, but
> worth keeping in mind if this direction is taken further.
>
> Best regards,
> Henson
>
The information in this e-mail is confidential. The contents may not be disclosed or used by anyone other than the addressee. Access to this e-mail by anyone else is unauthorised.
If you are not the intended recipient, please notify Airbus immediately and delete this e-mail.
Airbus cannot accept any responsibility for the accuracy or completeness of this e-mail as it has been sent over public networks. If you have any concerns over the content of this message or its Accuracy or Integrity, please contact Airbus immediately.
All outgoing e-mails from Airbus are checked using regularly updated virus scanning software but you should take whatever measures you deem to be appropriate to ensure that this message and any attachments are virus free.