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

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