Hi Henri,
> I do not think now is the time for this, for three reasons
Let me put the proposal in one place first. It is to replace the array
that is sized up front with a doubly-linked list; up/down is what forms
the links; and those links belong on the individual nodes of
inner_plan, not on the GraphScan.
Taking the three in turn: I agree with the third, I agree with the
principle of the second but would like to move one thing ahead of the
commit, and on the first I explained myself badly.
1. On only GraphScanState benefiting
This is where I explained myself badly.
Each depth has its own copy of inner_plan, and the copies are
copyObject() of the same Plan, so their nodes correspond one to one.
up/down holds that correspondence on the nodes themselves: a node's
down is the node in the same position in the next depth's copy.
With the links on every node, two things fall out at once.
The root's chain is the per-depth copies laid out in order. So
GraphScan moves between depths by following down from inner_head and
coming back along up. It does not carry a structure of its own; it
rides the root node's chain.
A non-root node's chain is that node's counterparts, one per depth.
EXPLAIN prints the whole tree under "Inner", so every node in it, the
Append and each scan below it alike, has to merge its instrumentation
with its counterparts. That chain is what they merge along.
So up/down is not a field for GraphScan's sake. There is one link per
node inside inner_plan, and GraphScan borrows one of them, the root's.
The ones carrying the field are every node type that can appear under
a GraphScan.
With the counterparts held by the nodes, the merge is:
static bool
agg_chain_walker(PlanState *ps, void *ctx)
{
if (ps->instrument != NULL)
{
for (PlanState *p = ps->down; p != NULL; p = p->down)
{
if (p->instrument == NULL)
continue;
InstrEndLoop(p->instrument);
InstrAggNode(ps->instrument, p->instrument);
}
}
return planstate_tree_walker(ps, agg_chain_walker, ctx);
}
One pass over the tree, each node folding its own chain, and the
existing walker keeps handling every child shape for free. Without the
links on the nodes, this pairing has to be rebuilt on the merging side
every time, and that logic then lives inside GraphScan -- one node type
carrying a problem that every node in the subtree has.
2. On committing a working version first
Agreed as a principle. But there is one part of what I proposed that I
think has to be settled before a commit.
ExecInitGraphScan() builds every depth up front. With an unbounded
quantifier max_depth is clamped to max_graph_stack_depth + 1, so
ndepths is max_graph_stack_depth + 2 (about a thousand), and each
GraphScan does, at every execution:
- one palloc0 of the frames array, ndepths entries
- four palloc's per frame (vid, vidnull, edge_props, edge_propsnull)
- ExecInitNode(copyObject(inner_plan)) once per frame
The third is the one that matters. inner_plan is a UNION ALL over the
matching edge element tables, so each copy is an Append over the
per-element scans, and a parameterized index scan there does
index_open() and index_beginscan(); for btree that attaches two
BTScanPosData. A two-hop query pays all of it, and a pattern with
three quantified hops pays it three times over. And the cost scales
with max_graph_stack_depth, not with the data.
The way to fix it is your own "lazy-init the frames when reached":
create a depth's copy the first time that depth is reached. Doing
that changes the data structure too. A stack that descends a depth at
a time and backtracks wants something you extend one step at a time
and can step back through -- a doubly-linked list -- rather than an
array sized up front. The links from point 1 are that list, and the
root's chain is this stack.
3. On this thread being the wrong place
Agreed, and I should have said so myself.
Let me be clearer about why I brought up WITH RECURSIVE, though. I am
not proposing to implement it here. The point was only that the same
structure would serve WITH RECURSIVE too -- that it is not specific to
GraphScan. What that structure tidies up in this code is points 1 and
2.
4. The attached patch
wip-graphscan-planstate-updown.txt applies on top of v2-0008. It is
not a submission for this CF entry and I am not asking you to fold it
in. It builds and the graph_table regression test passes.
Best regards,
Henson
From: Henson Choi <[email protected]>
Date: Thu, 17 Sep 2026 04:13:38 +0000
Subject: [PATCH] Replace GraphScan's per-depth frames with a PlanState
up/down chain
GraphScanState currently keeps a frames[] array, sized to
max_graph_stack_depth + 2 (1002 with the default of 1000) and built
eagerly in ExecInitGraphScan, where each element bundles two things of
very different character: inner_state, an expensive ExecInitNode'd
copy of the per-depth 1-hop expansion plan, and the vertex and
edge-property values reached at that depth, which are cheap scalars.
Because both live in one struct, the whole array -- inner_state
included -- gets built to the traversal's theoretical upper bound
rather than the depth actually reached, and EXPLAIN, which only ever
inspects frames[0], cannot show or account for the other copies' cost.
Split the two concerns. Add a generic up/down pointer pair to
PlanState, letting a node type thread its own PlanState copies into
a chain independent of lefttree/righttree; GraphScanState now grows
this chain lazily, one copy per depth, the first time that depth is
reached (graph_push), and never shrinks it, so a later traversal
that revisits an already-reached depth reuses the existing copy.
The scalar per-depth data moves to a separate GraphVidData array,
indexed directly by depth and grown by repalloc doubling as needed,
independent of the PlanState chain's own length.
For EXPLAIN ANALYZE, a new generic ExecShutdownPlanStateChain() walks
a node's up/down chain, finalizes each non-head element's current
instrumentation cycle via InstrEndLoop() (which nothing else in the
tree would otherwise call for these copies), and folds it into the
head's totals via InstrAggNode() -- the same InstrEndLoop-then-
InstrAggNode order ExplainNode() itself relies on for the node it
prints. ExecShutdownGraphScan() becomes a one-line call to this,
hooked into ExecShutdownNode_walker() the same way Gather already is.
Known limitation: this merges only the root of each copy into the head
copy's root; nodes below the root are never merged with their
counterparts. The merge has to happen node by node over the whole
copy, which this patch does not do.
This is a design proposal rather than a finished patch: up/down on
PlanState needs its own review before going anywhere near master.
---
src/backend/commands/explain.c | 6 +-
src/backend/executor/execProcnode.c | 46 ++++
src/backend/executor/nodeGraphScan.c | 379 ++++++++++++++++++++----------
src/include/executor/executor.h | 1 +
src/include/executor/nodeGraphScan.h | 43 ++--
src/include/nodes/execnodes.h | 59 ++++-
src/test/regress/expected/graph_table.out | 178 ++++++++++++++
src/test/regress/sql/graph_table.sql | 9 +
8 files changed, 558 insertions(+), 163 deletions(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 3fded53c3b3..c6290138c3b 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -2432,9 +2432,9 @@ ExplainNode(PlanState *planstate, List *ancestors,
"Subquery", NULL, es);
break;
case T_GraphScan:
- /* the inner 1-hop expansion lives in the first depth
frame */
- if (((GraphScanState *)
planstate)->frames[0].inner_state != NULL)
- ExplainNode(((GraphScanState *)
planstate)->frames[0].inner_state,
+ /* the inner 1-hop expansion's depth-0 copy is the
permanent head */
+ if (((GraphScanState *) planstate)->inner_head != NULL)
+ ExplainNode(((GraphScanState *)
planstate)->inner_head,
ancestors, "Inner",
NULL, es);
break;
case T_CustomScan:
diff --git a/src/backend/executor/execProcnode.c
b/src/backend/executor/execProcnode.c
index 837fa9bbe43..787d95f4ac7 100644
--- a/src/backend/executor/execProcnode.c
+++ b/src/backend/executor/execProcnode.c
@@ -765,6 +765,49 @@ ExecShutdownNode(PlanState *node)
(void) ExecShutdownNode_walker(node, NULL);
}
+/*
+ * ExecShutdownPlanStateChain
+ *
+ * A node type may thread its own PlanState instances into a doubly-linked
+ * sibling chain via up/down, orthogonal to lefttree/righttree (see the
+ * comment on PlanState.up/down in execnodes.h) -- e.g. GraphScan does this
+ * to give each depth of a graph traversal its own copy of the same inner
+ * plan. Such a chain is not reached by the normal planstate_tree_walker
+ * recursion, so it is this call, not ExecShutdownNode() on the chain's
+ * owner, that gives each PlanState in it a shutdown chance and rolls their
+ * instrumentation into the chain's head -- the one instance the owner
+ * exposes to EXPLAIN. The owning node calls this once, on its own head,
+ * from its own ExecShutdownXXX() function.
+ *
+ * A node further down the chain is finalized (InstrEndLoop) before being
+ * merged in: EXPLAIN only ever finalizes the current cycle of the node it
+ * is about to print (ExplainNode(), right before printing), which for this
+ * chain is only ever the head, so a chain member's last cycle would
+ * otherwise still be unfinalized (instrument->running) when InstrAggNode
+ * asserts against that.
+ */
+void
+ExecShutdownPlanStateChain(PlanState *head)
+{
+ PlanState *p;
+
+ if (head == NULL)
+ return;
+
+ for (p = head; p != NULL; p = p->down)
+ ExecShutdownNode(p);
+
+ if (head->instrument != NULL)
+ {
+ for (p = head->down; p != NULL; p = p->down)
+ if (p->instrument != NULL)
+ {
+ InstrEndLoop(p->instrument);
+ InstrAggNode(head->instrument, p->instrument);
+ }
+ }
+}
+
static bool
ExecShutdownNode_walker(PlanState *node, void *context)
{
@@ -793,6 +836,9 @@ ExecShutdownNode_walker(PlanState *node, void *context)
case T_GatherState:
ExecShutdownGather((GatherState *) node);
break;
+ case T_GraphScanState:
+ ExecShutdownGraphScan((GraphScanState *) node);
+ break;
case T_ForeignScanState:
ExecShutdownForeignScan((ForeignScanState *) node);
break;
diff --git a/src/backend/executor/nodeGraphScan.c
b/src/backend/executor/nodeGraphScan.c
index 2a25f382f52..6bf5b846bb9 100644
--- a/src/backend/executor/nodeGraphScan.c
+++ b/src/backend/executor/nodeGraphScan.c
@@ -11,9 +11,24 @@
* per-depth copies of the planned 1-hop expansion (the inner plan, a UNION
* ALL of the matching edge element tables).
*
- * Each depth frame owns its own PlanState copy of the inner plan, so a
- * frame's scan cursor is independent and backtracking simply resumes the
- * parent frame's cursor (no bookkeeping needed).
+ * Two orthogonal structures track a depth, each responsible for one thing:
+ *
+ * - GraphScanState.inner_head/inner walk a chain of per-depth copies of
+ * the inner plan, threaded through PlanState.up/down -- a field every
+ * PlanState has, not specific to this node type. A copy is created and
+ * linked in the first time graph_push() reaches that depth; backtracking
+ * only moves GraphScanState.inner and never unlinks or frees a copy, so
+ * a copy created for an earlier, deeper traversal (from a previous seed)
+ * is simply reused when a later seed reaches that depth again. This is
+ * why the number of copies actually materialized tracks the deepest
+ * point ever reached by this GraphScan, not the plan's maximum possible
+ * depth. Each copy's scan cursor is only (re)started (via ExecReScan)
+ * the first time it is stepped after becoming the current depth, so
+ * backtracking resumes it exactly where it left off.
+ * - GraphScanState.vids is a small array, indexed directly by depth and
+ * grown on demand, of the per-depth scalar data (the vertex reached at
+ * that depth, and the VLE property values of the edge that led there).
+ * This has nothing to do with any PlanState, so it is kept separate.
*
* An edge is traversable from the current vertex iff the edge element's
* source vertex element matches the current vertex's element and each source
@@ -50,22 +65,22 @@
static TupleTableSlot *ExecGraphScan(PlanState *pstate);
static void build_arms(GraphScanState * node);
static void build_arm_keys(List *keys, int *nkeys, FmgrInfo **eq, Oid **colls);
+static PlanState * graph_init_inner(GraphScanState * node);
static bool graph_fetch_seed(GraphScanState * node);
-static void graph_bind_side(GraphScanState * node, GraphDepthFrameData * fr,
+static void graph_bind_side(GraphScanState * node, GraphVidData * vd,
bool active, int
first_slot, int nslots);
-static void graph_bind_vertex_params(GraphScanState * node,
-
GraphDepthFrameData * fr);
+static void graph_bind_vertex_params(GraphScanState * node, GraphVidData * vd);
static bool graph_next(GraphScanState * node);
-static bool graph_step(GraphScanState * node, GraphDepthFrameData * fr);
-static bool try_traverse(GraphDepthFrameData * fr, TupleTableSlot *eslot,
+static bool graph_step(GraphScanState * node);
+static bool try_traverse(GraphVidData * vd, TupleTableSlot *eslot,
GraphScanArmData * arm, bool
match_src,
Oid *newelem, int *newnkeys,
Datum *newvid,
bool *newnull);
static bool graph_try_edge(GraphScanState * node,
- GraphDepthFrameData * fr,
TupleTableSlot *eslot,
+ GraphVidData * vd,
TupleTableSlot *eslot,
Oid *newelem, int *newnkeys,
Datum *newvid,
bool *newnull, Datum
*eprops, bool *epropsnull);
-static bool edge_key_matches(GraphDepthFrameData * fr, TupleTableSlot *eslot,
+static bool edge_key_matches(GraphVidData * vd, TupleTableSlot *eslot,
GraphScanArmData *
arm, bool issrc);
static int graph_find_arm(GraphScanState * node, Oid relid);
static void graph_push(GraphScanState * node, Oid newelem, int newnkeys,
@@ -143,7 +158,7 @@ static bool
graph_fetch_seed(GraphScanState * node)
{
EState *estate = node->ss.ps.state;
- GraphDepthFrameData *fr = &node->frames[0];
+ GraphVidData *vd = &node->vids[0];
ListCell *lc;
int k = 0;
bool hasnull = false;
@@ -151,16 +166,17 @@ graph_fetch_seed(GraphScanState * node)
graph_reset(node);
/*
- * Every depth frame must (re)start its inner scan for the current
vertex
- * of the new traversal (see GraphDepthFrameData.need_init); the
(re)scan
- * happens lazily in graph_step, when the current-vertex parameters are
- * bound.
+ * Every depth materialized so far must (re)start its inner plan copy's
+ * scan for the current vertex of the new traversal (see
+ * GraphVidData.need_init); the (re)scan happens lazily in graph_step,
+ * when the current-vertex parameters are bound. Depths not yet reached
+ * don't have a vids[] entry yet.
*/
- for (int d = 0; d < node->ndepths; d++)
- node->frames[d].need_init = true;
+ for (int d = 0; d < node->frames_reached; d++)
+ node->vids[d].need_init = true;
- fr->vid_elem = node->seed_elem;
- fr->vid_nkeys = list_length(node->seed_params);
+ vd->vid_elem = node->seed_elem;
+ vd->vid_nkeys = list_length(node->seed_params);
foreach(lc, node->seed_params)
{
Node *item = (Node *) lfirst(lc);
@@ -185,8 +201,8 @@ graph_fetch_seed(GraphScanState * node)
isnull = con->constisnull;
}
- fr->vid[k] = value;
- fr->vidnull[k] = isnull;
+ vd->vid[k] = value;
+ vd->vidnull[k] = isnull;
if (isnull)
hasnull = true;
k++;
@@ -197,20 +213,21 @@ graph_fetch_seed(GraphScanState * node)
return false;
node->cur_depth = 0;
+ node->inner = node->inner_head;
node->seed_emitted = false;
return true;
}
/*
* Bind one side -- source (forward) or destination (reverse) -- of the
- * current (innermost frame's) vertex key values into the PARAM_EXEC slots
- * that parameterize the inner 1-hop arm scans. Slots beyond the current
+ * current (innermost) vertex key values into the PARAM_EXEC slots that
+ * parameterize the inner 1-hop arm scans. Slots beyond the current
* vertex's key width, and the whole slot range of an inactive direction,
* are bound to NULL: "key = NULL" matches no rows, so the corresponding arm
* variants produce nothing.
*/
static void
-graph_bind_side(GraphScanState * node, GraphDepthFrameData * fr,
+graph_bind_side(GraphScanState * node, GraphVidData * vd,
bool active, int first_slot, int nslots)
{
EState *estate = node->ss.ps.state;
@@ -221,9 +238,9 @@ graph_bind_side(GraphScanState * node, GraphDepthFrameData
* fr,
&estate->es_param_exec_vals[lfirst_int(list_nth_cell(node->vertex_params,
first_slot + k))];
- if (active && k < fr->vid_nkeys && !fr->vidnull[k])
+ if (active && k < vd->vid_nkeys && !vd->vidnull[k])
{
- prm->value = fr->vid[k];
+ prm->value = vd->vid[k];
prm->isnull = false;
}
else
@@ -235,26 +252,26 @@ graph_bind_side(GraphScanState * node,
GraphDepthFrameData * fr,
}
/*
- * Bind the current (innermost frame's) vertex key values into the PARAM_EXEC
- * slots that parameterize the inner 1-hop arm scans. The forward (source
- * key) parameters are filled when the scan traverses out of the vertex's
- * source side (outgoing/undirected); the reverse (destination key)
- * parameters when it traverses in (incoming/undirected).
+ * Bind the current (innermost) vertex key values into the PARAM_EXEC slots
+ * that parameterize the inner 1-hop arm scans. The forward (source key)
+ * parameters are filled when the scan traverses out of the vertex's source
+ * side (outgoing/undirected); the reverse (destination key) parameters when
+ * it traverses in (incoming/undirected).
*/
static void
-graph_bind_vertex_params(GraphScanState * node, GraphDepthFrameData * fr)
+graph_bind_vertex_params(GraphScanState * node, GraphVidData * vd)
{
if (node->vertex_params == NIL)
return;
/* forward (source key) slots come first, then reverse (dest key) slots
*/
- graph_bind_side(node, fr, node->fwd_active, 0, node->max_nsrc);
- graph_bind_side(node, fr, node->rev_active, node->max_nsrc,
node->max_ndst);
+ graph_bind_side(node, vd, node->fwd_active, 0, node->max_nsrc);
+ graph_bind_side(node, vd, node->rev_active, node->max_nsrc,
node->max_ndst);
}
/*
- * Try to advance the traversal one edge from the current (innermost) frame,
- * backtracking when a frame is exhausted. Returns false when the current
+ * Try to advance the traversal one edge from the current (innermost) depth,
+ * backtracking when a depth is exhausted. Returns false when the current
* seed is exhausted (caller must fetch a new seed).
*/
static bool
@@ -262,9 +279,7 @@ graph_next(GraphScanState * node)
{
for (;;)
{
- GraphDepthFrameData *fr = &node->frames[node->cur_depth];
-
- if (graph_step(node, fr))
+ if (graph_step(node))
{
/* descended one edge; emit whenever the new depth is
deep enough */
if (node->cur_depth >= node->min_depth)
@@ -272,10 +287,11 @@ graph_next(GraphScanState * node)
continue; /* not deep enough yet;
descend further */
}
- /* this frame is exhausted: backtrack */
+ /* this depth is exhausted: backtrack */
if (node->cur_depth <= 0)
{
node->cur_depth = -1; /* need a new seed */
+ node->inner = NULL;
return false;
}
graph_backtrack(node);
@@ -283,13 +299,14 @@ graph_next(GraphScanState * node)
}
/*
- * Pull the next traversable edge from the given frame's inner scan. Returns
- * true if a new depth was pushed onto the stack.
+ * Pull the next traversable edge from the current depth's inner plan copy.
+ * Returns true if a new depth was pushed onto the stack.
*/
static bool
-graph_step(GraphScanState * node, GraphDepthFrameData * fr)
+graph_step(GraphScanState * node)
{
GraphScan *plan = castNode(GraphScan, node->ss.ps.plan);
+ GraphVidData *vd = &node->vids[node->cur_depth];
TupleTableSlot *eslot;
Oid newelem;
int newnkeys;
@@ -304,35 +321,34 @@ graph_step(GraphScanState * node, GraphDepthFrameData *
fr)
return false;
/*
- * The current frame already sits at (or beyond) the effective maximum
+ * The current depth already sits at (or beyond) the effective maximum
* depth: no further descent is allowed. Its single row was emitted
when
- * this depth was pushed; further calls just exhaust the frame.
+ * this depth was pushed; further calls just exhaust the depth.
*/
if (node->cur_depth >= node->max_depth)
return false;
/*
* The inner arm scans are parameterized on the current vertex; bind it
- * (the frame's vertex) before pulling any rows. Parameterized index
- * scans only re-evaluate their scan keys when (re)started, so a frame
- * whose vertex was (re)set (a fresh push or a new seed) must have its
- * inner scan rescanned now, first and only time it is stepped for that
- * vertex.
+ * before pulling any rows. Parameterized index scans only re-evaluate
+ * their scan keys when (re)started, so a depth whose vertex was (re)set
+ * (a fresh push or a new seed) must have its inner plan copy rescanned
+ * now, first and only time it is stepped for that vertex.
*/
- graph_bind_vertex_params(node, fr);
- if (fr->need_init)
+ graph_bind_vertex_params(node, vd);
+ if (vd->need_init)
{
- ExecReScan(fr->inner_state);
- fr->need_init = false;
+ ExecReScan(node->inner);
+ vd->need_init = false;
}
for (;;)
{
- eslot = ExecProcNode(fr->inner_state);
+ eslot = ExecProcNode(node->inner);
if (TupIsNull(eslot))
return false;
- if (graph_try_edge(node, fr, eslot, &newelem, &newnkeys, newvid,
+ if (graph_try_edge(node, vd, eslot, &newelem, &newnkeys, newvid,
newnull, newprops,
newpropsnull))
{
graph_push(node, newelem, newnkeys, newvid, newnull,
newprops,
@@ -349,7 +365,7 @@ graph_step(GraphScanState * node, GraphDepthFrameData * fr)
* the opposite side. The direction of the hop decides which side is tried.
*/
static bool
-try_traverse(GraphDepthFrameData * fr, TupleTableSlot *eslot,
+try_traverse(GraphVidData * vd, TupleTableSlot *eslot,
GraphScanArmData * arm, bool match_src,
Oid *newelem, int *newnkeys, Datum *newvid,
bool *newnull)
@@ -371,7 +387,7 @@ try_traverse(GraphDepthFrameData * fr, TupleTableSlot
*eslot,
next_first = arm->arm_src_first;
}
- if (!edge_key_matches(fr, eslot, arm, match_src))
+ if (!edge_key_matches(vd, eslot, arm, match_src))
return false;
*newelem = next_elem;
@@ -387,7 +403,7 @@ try_traverse(GraphDepthFrameData * fr, TupleTableSlot
*eslot,
* the next vertex plus the edge's VLE property values.
*/
static bool
-graph_try_edge(GraphScanState * node, GraphDepthFrameData * fr,
+graph_try_edge(GraphScanState * node, GraphVidData * vd,
TupleTableSlot *eslot, Oid *newelem, int *newnkeys,
Datum *newvid, bool *newnull, Datum *eprops,
bool *epropsnull)
@@ -411,22 +427,22 @@ graph_try_edge(GraphScanState * node, GraphDepthFrameData
* fr,
{
case GRAPH_DIR_INCOMING:
/* traverse the edge from its destination (the current
vertex) */
- matched = try_traverse(fr, eslot, arm, false,
+ matched = try_traverse(vd, eslot, arm, false,
newelem,
newnkeys, newvid, newnull);
break;
case GRAPH_DIR_UNDIRECTED:
/* traverse from either endpoint; try the source side
first */
- matched = try_traverse(fr, eslot, arm, true,
+ matched = try_traverse(vd, eslot, arm, true,
newelem,
newnkeys, newvid, newnull);
if (!matched)
- matched = try_traverse(fr, eslot, arm, false,
+ matched = try_traverse(vd, eslot, arm, false,
newelem, newnkeys, newvid, newnull);
break;
default: /* GRAPH_DIR_OUTGOING */
/* traverse the edge from its source (the current
vertex) */
- matched = try_traverse(fr, eslot, arm, true,
+ matched = try_traverse(vd, eslot, arm, true,
newelem,
newnkeys, newvid, newnull);
break;
}
@@ -446,7 +462,7 @@ graph_try_edge(GraphScanState * node, GraphDepthFrameData *
fr,
* destination) vertex element must equal the current vertex's element.
*/
static bool
-edge_key_matches(GraphDepthFrameData * fr, TupleTableSlot *eslot,
+edge_key_matches(GraphVidData * vd, TupleTableSlot *eslot,
GraphScanArmData * arm, bool issrc)
{
int n;
@@ -467,9 +483,9 @@ edge_key_matches(GraphDepthFrameData * fr, TupleTableSlot
*eslot,
elem = arm->arm_dstvertex;
}
- if (fr->vid_elem != elem)
+ if (vd->vid_elem != elem)
return false;
- if (fr->vid_nkeys != n)
+ if (vd->vid_nkeys != n)
return false;
for (i = 0; i < n; i++)
@@ -480,7 +496,7 @@ edge_key_matches(GraphDepthFrameData * fr, TupleTableSlot
*eslot,
Oid eqcoll;
edatum = slot_getattr(eslot, first + i + 1, &eisnull);
- if (eisnull || fr->vidnull[i])
+ if (eisnull || vd->vidnull[i])
return false;
if (issrc)
@@ -494,7 +510,7 @@ edge_key_matches(GraphDepthFrameData * fr, TupleTableSlot
*eslot,
eqcoll = arm->arm_dstcoll[i];
}
- if (!DatumGetBool(FunctionCall2Coll(eq, eqcoll, edatum,
fr->vid[i])))
+ if (!DatumGetBool(FunctionCall2Coll(eq, eqcoll, edatum,
vd->vid[i])))
return false;
}
return true;
@@ -511,8 +527,16 @@ graph_find_arm(GraphScanState * node, Oid relid)
}
/*
- * Push a new depth frame for a traversed edge. Enforces max_graph_stack_depth
- * via a shared counter on the EState (summed over all active GraphScans).
+ * Push a new depth for a traversed edge. Enforces max_graph_stack_depth via
+ * a shared counter on the EState (summed over all active GraphScans).
+ *
+ * The inner plan copy one deeper than the current one (node->inner->down)
+ * and the vids[] entry for that depth are both created the first time this
+ * depth is reached; a later seed that reaches the same depth again just
+ * reuses both (graph_step() (re)starts the reused copy's scan through
+ * need_init, set below). This is why the cost of reaching a new depth
+ * tracks the deepest point ever reached by this GraphScan, not the plan's
+ * maximum possible depth.
*/
static void
graph_push(GraphScanState * node, Oid newelem, int newnkeys,
@@ -520,8 +544,8 @@ graph_push(GraphScanState * node, Oid newelem, int newnkeys,
bool *epropsnull)
{
int d = node->cur_depth + 1;
- GraphDepthFrameData *nfr = &node->frames[d];
EState *estate = node->ss.ps.state;
+ GraphVidData *nv;
estate->es_graph_stack_depth++;
if (estate->es_graph_stack_depth > max_graph_stack_depth)
@@ -530,37 +554,91 @@ graph_push(GraphScanState * node, Oid newelem, int
newnkeys,
errhint("Increase
max_graph_stack_depth and retry, or try "
"to remove the
infinite loop")));
- nfr->vid_elem = newelem;
- nfr->vid_nkeys = newnkeys;
- memcpy(nfr->vid, newvid, sizeof(Datum) * newnkeys);
- memcpy(nfr->vidnull, newnull, sizeof(bool) * newnkeys);
- memcpy(nfr->edge_props, eprops, sizeof(Datum) * node->nprops);
- memcpy(nfr->edge_propsnull, epropsnull, sizeof(bool) * node->nprops);
- /* the new vertex's inner scan must (re)start (see graph_step) */
- nfr->need_init = true;
+ if (d >= node->frames_reached)
+ {
+ /*
+ * First time this depth is reached: create + link a new copy.
This
+ * runs from inside the ExecProcNode recursion (graph_step() ->
+ * graph_try_edge() -> graph_push()), which happens in the
per-query
+ * context (see src/backend/executor/README, "Memory
Management"),
+ * the same context ExecInitGraphScan() itself ran in -- so no
+ * explicit context switch is needed here.
+ */
+ PlanState *cur = node->inner;
+ PlanState *newps = graph_init_inner(node);
+
+ if (newps != NULL)
+ {
+ newps->up = cur;
+ cur->down = newps;
+ }
+ node->inner = newps;
+
+ if (d >= node->vids_capacity)
+ {
+ int newcap =
Max(node->vids_capacity * 2, d + 1);
+
+ node->vids = repalloc(node->vids, sizeof(GraphVidData)
* newcap);
+ memset(&node->vids[node->vids_capacity], 0,
+ sizeof(GraphVidData) * (newcap -
node->vids_capacity));
+ node->vids_capacity = newcap;
+ }
+
+ nv = &node->vids[d];
+ nv->vid = palloc(sizeof(Datum) * Max(node->frame_vid_width, 1));
+ nv->vidnull = palloc(sizeof(bool) * Max(node->frame_vid_width,
1));
+ nv->edge_props = palloc(sizeof(Datum) * Max(node->nprops, 1));
+ nv->edge_propsnull = palloc(sizeof(bool) * Max(node->nprops,
1));
+
+ node->frames_reached = d + 1;
+ }
+ else
+ {
+ /* reuse the copy and vids[] entry from an earlier, deeper
traversal */
+ node->inner = node->inner->down;
+ nv = &node->vids[d];
+ }
+
+ nv->vid_elem = newelem;
+ nv->vid_nkeys = newnkeys;
+ memcpy(nv->vid, newvid, sizeof(Datum) * newnkeys);
+ memcpy(nv->vidnull, newnull, sizeof(bool) * newnkeys);
+ memcpy(nv->edge_props, eprops, sizeof(Datum) * node->nprops);
+ memcpy(nv->edge_propsnull, epropsnull, sizeof(bool) * node->nprops);
+ /* the new vertex's inner plan copy must (re)start (see graph_step) */
+ nv->need_init = true;
node->cur_depth = d;
}
-/* Pop the innermost depth frame (called only for depth > 0). */
+/* Pop the innermost depth (called only for depth > 0). */
static void
graph_backtrack(GraphScanState * node)
{
node->ss.ps.state->es_graph_stack_depth--;
Assert(node->ss.ps.state->es_graph_stack_depth >= 0);
+ node->inner = node->inner->up;
node->cur_depth--;
}
-/* Pop all active frames; the scan becomes ready for a new seed. */
+/*
+ * Pop to depth 0; the scan becomes ready for a new seed. This only moves
+ * node->inner back toward the head -- it never unlinks an inner plan copy
+ * or forgets a vids[] entry, so depths reached by a previous, deeper
+ * traversal stay available (via inner_head->down->down->... and
+ * vids[1..frames_reached-1]) for a later seed to reuse.
+ */
static void
graph_reset(GraphScanState * node)
{
while (node->cur_depth > 0)
{
node->ss.ps.state->es_graph_stack_depth--;
+ node->inner = node->inner->up;
node->cur_depth--;
}
Assert(node->ss.ps.state->es_graph_stack_depth >= 0);
node->cur_depth = -1;
+ node->inner = NULL;
node->seed_emitted = false;
}
@@ -614,14 +692,14 @@ ExecGraphScan(PlanState *pstate)
/*
* Fill the scan's output slot for the path currently on the stack: seed
- * keys (frame 0), terminal keys (innermost frame), and VLE edge-list arrays.
+ * keys (depth 0), terminal keys (innermost depth), and VLE edge-list arrays.
*/
static void
graph_build_row(GraphScanState * node, TupleTableSlot *slot)
{
GraphScan *plan = castNode(GraphScan, node->ss.ps.plan);
- GraphDepthFrameData *seedfr = &node->frames[0];
- GraphDepthFrameData *endfr = &node->frames[node->cur_depth];
+ GraphVidData *seedvd = &node->vids[0];
+ GraphVidData *endvd = &node->vids[node->cur_depth];
int amp;
MemoryContext oldcxt;
@@ -630,16 +708,16 @@ graph_build_row(GraphScanState * node, TupleTableSlot
*slot)
amp = 0;
foreach_int(attno, plan->seed_key_cols)
{
- slot->tts_values[attno - 1] = seedfr->vid[amp];
- slot->tts_isnull[attno - 1] = seedfr->vidnull[amp];
+ slot->tts_values[attno - 1] = seedvd->vid[amp];
+ slot->tts_isnull[attno - 1] = seedvd->vidnull[amp];
amp++;
}
amp = 0;
foreach_int(attno, plan->terminal_key_cols)
{
- slot->tts_values[attno - 1] = endfr->vid[amp];
- slot->tts_isnull[attno - 1] = endfr->vidnull[amp];
+ slot->tts_values[attno - 1] = endvd->vid[amp];
+ slot->tts_isnull[attno - 1] = endvd->vidnull[amp];
amp++;
}
@@ -681,7 +759,9 @@ graph_emit_row(GraphScanState * node, TupleTableSlot *slot)
/*
* Build the VLE edge-list array for property pi: the property's value over
* every traversed edge of the current path, in traversal order; an empty
- * array when the path has no edges.
+ * array when the path has no edges. vids[1..cur_depth] are indexed
+ * directly -- no risk of reading a depth left over from an earlier, deeper
+ * traversal, since the loop bound is cur_depth itself.
*/
static Datum
graph_build_edge_array(GraphScanState * node, TupleTableSlot *slot,
@@ -701,10 +781,10 @@ graph_build_edge_array(GraphScanState * node,
TupleTableSlot *slot,
for (int d = 1; d <= node->cur_depth; d++)
{
- GraphDepthFrameData *fr = &node->frames[d];
+ GraphVidData *vd = &node->vids[d];
astate =
- accumArrayResult(astate, fr->edge_props[pi],
fr->edge_propsnull[pi],
+ accumArrayResult(astate, vd->edge_props[pi],
vd->edge_propsnull[pi],
elemtype,
CurrentMemoryContext);
}
@@ -714,11 +794,29 @@ graph_build_edge_array(GraphScanState * node,
TupleTableSlot *slot,
return makeArrayResult(astate, CurrentMemoryContext);
}
+/*
+ * Make one new copy of the inner (1-hop) expansion plan, or NULL if there is
+ * none. Called once, eagerly, for depth 0 from ExecInitGraphScan(); called
+ * again lazily, from graph_push(), the first time the traversal reaches a
+ * new depth -- see the file header comment.
+ */
+static PlanState *
+graph_init_inner(GraphScanState * node)
+{
+ GraphScan *plan = castNode(GraphScan, node->ss.ps.plan);
+
+ if (plan->inner_plan == NULL)
+ return NULL;
+
+ return ExecInitNode(copyObject(plan->inner_plan), node->ss.ps.state,
+ node->eflags);
+}
+
GraphScanState *
ExecInitGraphScan(GraphScan * node, EState *estate, int eflags)
{
GraphScanState *scanstate;
- int maxwidth;
+ GraphVidData *vd0;
/* check for unsupported flags */
Assert(!(eflags & EXEC_FLAG_MARK));
@@ -736,6 +834,7 @@ ExecInitGraphScan(GraphScan * node, EState *estate, int
eflags)
scanstate->ss.ps.plan = (Plan *) node;
scanstate->ss.ps.state = estate;
scanstate->ss.ps.ExecProcNode = ExecGraphScan;
+ scanstate->eflags = eflags; /* for graph_init_inner(), called
lazily too */
ExecAssignExprContext(estate, &scanstate->ss.ps);
@@ -757,12 +856,12 @@ ExecInitGraphScan(GraphScan * node, EState *estate, int
eflags)
/*
* Effective maximum depth. Explicit bounds are honored; unbounded (or
* absurdly large) ones are clamped to max_graph_stack_depth + 1 so that
- * the traversal-depth guard below fires instead of looping forever.
+ * the traversal-depth guard in graph_push() fires instead of looping
+ * forever. Note this bounds how deep the traversal may go, not how
+ * much is allocated up front -- see graph_push().
*/
if (node->max_depth < 0 || node->max_depth > max_graph_stack_depth)
scanstate->max_depth = max_graph_stack_depth + 1;
- scanstate->ndepths = scanstate->max_depth + 1;
- scanstate->frames = palloc0(sizeof(GraphDepthFrameData) *
scanstate->ndepths);
/* Compile the per-arm edge element metadata. */
build_arms(scanstate);
@@ -778,39 +877,33 @@ ExecInitGraphScan(GraphScan * node, EState *estate, int
eflags)
ExecInitResultTypeTL(&scanstate->ss.ps);
ExecAssignScanProjectionInfo(&scanstate->ss);
- /*
- * Build the depth frames: every frame owns a copy of the inner (1-hop)
- * expansion plan so that each frame's scan cursor is independent.
- */
- maxwidth = Max(list_length(node->seed_params),
- Max(node->max_nsrc, node->max_ndst));
- scanstate->tmp_vid = palloc(sizeof(Datum) * Max(maxwidth, 1));
- scanstate->tmp_vidnull = palloc(sizeof(bool) * Max(maxwidth, 1));
+ scanstate->frame_vid_width = Max(list_length(node->seed_params),
+
Max(node->max_nsrc, node->max_ndst));
+ scanstate->tmp_vid = palloc(sizeof(Datum) *
Max(scanstate->frame_vid_width, 1));
+ scanstate->tmp_vidnull = palloc(sizeof(bool) *
Max(scanstate->frame_vid_width, 1));
scanstate->tmp_props = palloc(sizeof(Datum) * Max(scanstate->nprops,
1));
scanstate->tmp_propsnull = palloc(sizeof(bool) * Max(scanstate->nprops,
1));
- for (int d = 0; d < scanstate->ndepths; d++)
- {
- GraphDepthFrameData *fr = &scanstate->frames[d];
+ /*
+ * Only depth 0 is materialized up front -- it is always needed. Deeper
+ * copies of the inner plan, and their vids[] entries, are created
+ * lazily as graph_push() actually reaches them (see the file header
+ * comment); this avoids paying for up to max_graph_stack_depth extra
+ * copies on traversals that never get that deep.
+ */
+ scanstate->inner_head = graph_init_inner(scanstate);
+ scanstate->inner = NULL;
- fr->vid = palloc(sizeof(Datum) * Max(maxwidth, 1));
- fr->vidnull = palloc(sizeof(bool) * Max(maxwidth, 1));
- fr->edge_props = palloc(sizeof(Datum) * Max(scanstate->nprops,
1));
- fr->edge_propsnull = palloc(sizeof(bool) *
Max(scanstate->nprops, 1));
+ scanstate->vids_capacity = 1;
+ scanstate->vids = palloc0(sizeof(GraphVidData));
+ scanstate->frames_reached = 1;
- /*
- * Initialize the inner (1-hop) expansion eagerly (so EXPLAIN
can
- * display it); mark the frame for a re-started scan
(need_init) so
- * the inner index scans pick up the current-vertex parameters,
which
- * are bound later, at the frame's first step.
- */
- if (node->inner_plan != NULL)
- fr->inner_state =
- ExecInitNode(copyObject(node->inner_plan),
estate, eflags);
- else
- fr->inner_state = NULL;
- fr->need_init = true;
- }
+ vd0 = &scanstate->vids[0];
+ vd0->vid = palloc(sizeof(Datum) * Max(scanstate->frame_vid_width, 1));
+ vd0->vidnull = palloc(sizeof(bool) * Max(scanstate->frame_vid_width,
1));
+ vd0->edge_props = palloc(sizeof(Datum) * Max(scanstate->nprops, 1));
+ vd0->edge_propsnull = palloc(sizeof(bool) * Max(scanstate->nprops, 1));
+ vd0->need_init = true;
/*
* initialize child expressions
@@ -824,11 +917,23 @@ ExecInitGraphScan(GraphScan * node, EState *estate, int
eflags)
void
ExecEndGraphScan(GraphScanState * node)
{
+ PlanState *p;
+ PlanState *next;
+
graph_reset(node);
- for (int d = 0; d < node->ndepths; d++)
- if (node->frames[d].inner_state != NULL)
- ExecEndNode(node->frames[d].inner_state);
+ /* Individual part: each depth's own inner plan copy, walked via
up/down. */
+ for (p = node->inner_head; p != NULL; p = next)
+ {
+ next = p->down;
+ ExecEndNode(p);
+ }
+
+ /*
+ * Common part, last: nothing beyond what memory-context teardown
already
+ * reclaims (arms[]/vids[]/tmp_* are plain palloc'd in the query's own
+ * context) -- noted here to keep the two-phase order explicit.
+ */
}
void
@@ -839,9 +944,23 @@ ExecReScanGraphScan(GraphScanState * node)
if (node->ss.ps.chgParam != NULL)
{
- for (int d = 0; d < node->ndepths; d++)
- if (node->frames[d].inner_state != NULL)
-
UpdateChangedParamSet(node->frames[d].inner_state,
-
node->ss.ps.chgParam);
+ for (PlanState *p = node->inner_head; p != NULL; p = p->down)
+ UpdateChangedParamSet(p, node->ss.ps.chgParam);
}
}
+
+/*
+ * Give every depth's own copy of the inner plan a chance to shut down and
+ * roll their instrumentation into inner_head's -- the copy EXPLAIN actually
+ * displays as the "Inner" child (see explain.c). This is inner_head's own
+ * action on its down-chain (see the PlanState.up/down comment in
+ * execnodes.h and ExecShutdownPlanStateChain()), not something GraphScan
+ * does by reaching into it from the outside; without it, EXPLAIN ANALYZE
+ * would report only depth 0's share of the work instead of the total
+ * across every depth this GraphScan actually visited.
+ */
+void
+ExecShutdownGraphScan(GraphScanState * node)
+{
+ ExecShutdownPlanStateChain(node->inner_head);
+}
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 8bb6c7bda2f..c3687badba2 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -301,6 +301,7 @@ extern void ExecSetExecProcNode(PlanState *node,
ExecProcNodeMtd function);
extern Node *MultiExecProcNode(PlanState *node);
extern void ExecEndNode(PlanState *node);
extern void ExecShutdownNode(PlanState *node);
+extern void ExecShutdownPlanStateChain(PlanState *head);
extern void ExecSetTupleBound(int64 tuples_needed, PlanState *child_node);
/*
diff --git a/src/include/executor/nodeGraphScan.h
b/src/include/executor/nodeGraphScan.h
index ef9a310a399..807966a1ed5 100644
--- a/src/include/executor/nodeGraphScan.h
+++ b/src/include/executor/nodeGraphScan.h
@@ -21,6 +21,7 @@ typedef struct FmgrInfo FmgrInfo;
extern GraphScanState * ExecInitGraphScan(GraphScan * node, EState *estate,
int eflags);
extern void ExecEndGraphScan(GraphScanState * node);
extern void ExecReScanGraphScan(GraphScanState * node);
+extern void ExecShutdownGraphScan(GraphScanState * node);
/*
* One compiled edge element arm of the GraphScan's inner 1-hop expansion.
@@ -58,39 +59,35 @@ typedef struct GraphScanArmData
} GraphScanArmData;
/*
- * One depth frame of the DFS: a copy of the inner 1-hop expansion plan,
- * plus the vertex reached at this depth and the VLE property values of the
- * edge that led here.
+ * Per-depth scalar data of the DFS: the vertex reached at a given depth,
+ * plus the VLE property values of the edge that led there. This has
+ * nothing to do with any PlanState -- it is indexed directly by depth in
+ * GraphScanState.vids, grown on demand (see graph_push()), independent of
+ * the PlanState.up/down chain that links the per-depth copies of the inner
+ * 1-hop expansion plan (a generic PlanState field, not specific to
+ * GraphScan; see the comment on GraphScanState).
*
- * frames[0] holds the seed vertex (no edge); frames[d] (d >= 1) holds the
- * vertex reached after traversing the d-th edge of the current path. The
- * inner scan state of a frame acts as a cursor: it is only started (rescan)
- * when the frame is first pushed, and never again, so backtracking resumes
- * the parent's scan exactly where it left off.
+ * need_init is true until the depth's copy of the inner plan (found via the
+ * PlanState.up/down chain, at the same depth) has been (re)started for the
+ * current vertex: the executor (re)initializes or rescans it the first time
+ * the depth is stepped after a push or a new seed, when the current-vertex
+ * PARAM_EXEC parameters are bound. Parameterized index scans only
+ * re-evaluate their scan keys on (re)scan, so restarting like this is what
+ * keeps them in sync with the vertex.
*/
-typedef struct GraphDepthFrameData
+typedef struct GraphVidData
{
- PlanState *inner_state; /* own copy of the inner 1-hop
expansion */
-
- /*
- * True until the frame's inner scan has been (re)started for the
current
- * vertex: the executor (re)initializes or rescans it the first time the
- * frame is stepped after a push or a new seed, when the current-vertex
- * PARAM_EXEC parameters are bound. Parameterized index scans only
- * re-evaluate their scan keys on (re)scan, so restarting like this is
- * what keeps them in sync with the vertex.
- */
- bool need_init;
-
Oid vid_elem; /* vertex element of
the current vertex */
int vid_nkeys; /* key width of the
current vertex */
Datum *vid; /* current vertex key values */
bool *vidnull;
Datum *edge_props; /* [nprops] VLE property values of the
edge
- * into this
frame (frame 0: unused) */
+ * into this
depth (depth 0: unused) */
bool *edge_propsnull;
-} GraphDepthFrameData;
+ bool need_init;
+
+} GraphVidData;
#endif /* NODEGRAPHSCAN_H */
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index c79d581793e..86a70b900dc 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1209,6 +1209,17 @@ typedef struct PlanState
PlanState *lefttree; /* input plan tree(s) */
PlanState *righttree;
+ /*
+ * Orthogonal to lefttree/righttree: a node type may thread its own
+ * PlanState instances (e.g. several per-depth copies of the same
+ * subplan, owned and walked by that node type alone) into a doubly-
+ * linked sibling chain via up/down, independent of and in addition to
+ * whatever tree shape lefttree/righttree describe. Unused (NULL) by
+ * most node types.
+ */
+ PlanState *up;
+ PlanState *down;
+
List *initPlan; /* Init SubPlanState nodes
(un-correlated expr
* subselects)
*/
List *subPlan; /* SubPlanState nodes in my expressions
*/
@@ -1922,8 +1933,20 @@ typedef struct SubqueryScanState
* GraphScanState is used for scanning a graph pattern seek (a
single
* quantified hop) in the range table. The variable-length hop is
* traversed with a depth-first search over per-depth copies of the
- * inner 1-hop expansion plan (struct GraphDepthFrameData, defined
in
- * executor/nodeGraphScan.h).
+ * inner 1-hop expansion plan. Two orthogonal structures track
this,
+ * one per concern:
+ *
+ * - The PlanState.up/down chain (a generic field of every
PlanState,
+ * not specific to GraphScan) links the depth-0..N copies of the
+ * inner plan itself: inner_head is the permanent depth-0 copy,
+ * inner is the copy at the innermost depth of the path
currently on
+ * the stack. Walked for EXPLAIN, ExecEndGraphScan(), and
+ * ExecReScanGraphScan()'s chgParam propagation.
+ * - vids (struct GraphVidData, defined in
executor/nodeGraphScan.h) is
+ * a small array, indexed directly by depth and grown on demand,
of
+ * the cheap per-depth scalar data (the vertex reached at that
depth,
+ * and the VLE property values of the edge that led there) that
has
+ * nothing to do with any particular PlanState.
* ----------------
*/
typedef struct GraphScanState
@@ -1934,11 +1957,33 @@ typedef struct GraphScanState
int min_depth;
int max_depth;
- /* Depth frames: one per active path level, [0..ndepths-1]. */
- int ndepths;
- struct GraphDepthFrameData *frames;
- int cur_depth; /* innermost active
frame; -1 = need a new
- * seed */
+ /*
+ * inner_head is the permanent depth-0 copy of the inner plan, created
+ * once at init and never freed until the node ends. inner is the copy
+ * at the innermost depth of the path currently on the stack (NULL when
+ * cur_depth < 0, i.e. a new seed is needed). Deeper copies are created
+ * lazily and linked in via PlanState.up/down the first time
+ * graph_push() reaches that depth; see nodeGraphScan.c.
+ */
+ PlanState *inner_head;
+ PlanState *inner;
+ int cur_depth; /* inner's depth; -1 =
need a new seed */
+
+ /*
+ * Per-depth scalar data (struct GraphVidData), indexed [0..
+ * frames_reached-1] directly by depth; vids_capacity is the allocated
+ * size, repalloc'd (doubling) as frames_reached grows past it. Grows
+ * only to the deepest point ever actually reached by this GraphScan,
+ * not to the plan's maximum possible depth.
+ */
+ struct GraphVidData *vids;
+ int vids_capacity;
+ int frames_reached;
+
+ int eflags; /* saved from
ExecInitGraphScan(), for
+ * lazily
initializing later PlanState
+ * copies */
+ int frame_vid_width; /* per-depth
vid/vidnull array size */
bool need_seed; /* params may hold a new seed
(set on rescan) */
bool seed_emitted; /* zero-hop seed row already emitted */
diff --git a/src/test/regress/expected/graph_table.out
b/src/test/regress/expected/graph_table.out
index 5173934e296..bea1c85c9d6 100644
--- a/src/test/regress/expected/graph_table.out
+++ b/src/test/regress/expected/graph_table.out
@@ -1224,6 +1224,184 @@ SELECT src, dst FROM GRAPH_TABLE (g1 MATCH (a IS
vl1)-[e IS el1]->{1,3}(c IS vl3
v11 | v33
(3 rows)
+-- EXPLAIN on a GraphScan: the plan shows "Graph Scan" plus its inner
+-- (1-hop expansion) child. COSTS OFF keeps this deterministic.
+EXPLAIN (COSTS OFF)
+SELECT src, dst FROM GRAPH_TABLE (g1 MATCH (a IS vl1)-[e IS el1]->{1,3}(c IS
vl3) COLUMNS (a.vname AS src, c.vname AS dst)) ORDER BY src, dst;
+ QUERY PLAN
+----------------------------------------------------------------------------------------------
+ Sort
+ Sort Key: v1.vname, v2.vname
+ -> Append
+ -> Hash Join
+ Hash Cond: ((v2.id1 = graph_scan.gs_term) AND (v2.id2 =
graph_scan.gs_term_1))
+ -> Seq Scan on v2
+ -> Hash
+ -> Nested Loop
+ -> Seq Scan on v1
+ -> Graph Scan on graph_scan
+ Filter: (v1.id = graph_scan.gs_seed)
+ min_depth: 1
+ max_depth: 3
+ direction: outgoing
+ -> Append
+ -> Seq Scan on e1_2
+ Filter: (id_1 = $0)
+ -> Seq Scan on e1_2
+ Filter: ((id_2_1 = $2) AND
(id_2_2 = $3))
+ -> Bitmap Heap Scan on e1_3
+ Recheck Cond: (id_1 = $0)
+ -> Bitmap Index Scan on e1_3_pkey
+ Index Cond: (id_1 = $0)
+ -> Bitmap Heap Scan on e1_3
+ Recheck Cond: (id_3 = $2)
+ -> Bitmap Index Scan on e1_3_pkey
+ Index Cond: (id_3 = $2)
+ -> Seq Scan on e2_1
+ Filter: ((id_2_1 = $0) AND
(id_2_2 = $1))
+ -> Seq Scan on e2_1
+ Filter: (id_1 = $2)
+ -> Nested Loop
+ -> Nested Loop
+ -> Seq Scan on v1 v1_1
+ -> Graph Scan on graph_scan_1
+ Filter: (v1_1.id = graph_scan_1.gs_seed)
+ min_depth: 1
+ max_depth: 3
+ direction: outgoing
+ -> Append
+ -> Seq Scan on e1_2
+ Filter: (id_1 = $4)
+ -> Seq Scan on e1_2
+ Filter: ((id_2_1 = $6) AND (id_2_2 =
$7))
+ -> Bitmap Heap Scan on e1_3
+ Recheck Cond: (id_1 = $4)
+ -> Bitmap Index Scan on e1_3_pkey
+ Index Cond: (id_1 = $4)
+ -> Bitmap Heap Scan on e1_3
+ Recheck Cond: (id_3 = $6)
+ -> Bitmap Index Scan on e1_3_pkey
+ Index Cond: (id_3 = $6)
+ -> Seq Scan on e2_1
+ Filter: ((id_2_1 = $4) AND (id_2_2 =
$5))
+ -> Seq Scan on e2_1
+ Filter: (id_1 = $6)
+ -> Index Scan using v3_pkey on v3
+ Index Cond: (id = graph_scan_1.gs_term)
+(58 rows)
+
+-- same, with ANALYZE: exercises actually running the inner plan copies
+-- (not just planning/displaying them).
+EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
+SELECT src, dst FROM GRAPH_TABLE (g1 MATCH (a IS vl1)-[e IS el1]->{1,3}(c IS
vl3) COLUMNS (a.vname AS src, c.vname AS dst)) ORDER BY src, dst;
+ QUERY PLAN
+-----------------------------------------------------------------------------------------------------------
+ Sort (actual rows=7.00 loops=1)
+ Sort Key: v1.vname, v2.vname
+ Sort Method: quicksort Memory: 25kB
+ Buffers: shared hit=115
+ -> Append (actual rows=7.00 loops=1)
+ Buffers: shared hit=115
+ -> Hash Join (actual rows=5.00 loops=1)
+ Hash Cond: ((v2.id1 = graph_scan.gs_term) AND (v2.id2 =
graph_scan.gs_term_1))
+ Buffers: shared hit=53
+ -> Seq Scan on v2 (actual rows=3.00 loops=1)
+ Buffers: shared hit=1
+ -> Hash (actual rows=9.00 loops=1)
+ Buckets: 1024 Batches: 1 Memory Usage: 9kB
+ Buffers: shared hit=52
+ -> Nested Loop (actual rows=9.00 loops=1)
+ Buffers: shared hit=52
+ -> Seq Scan on v1 (actual rows=3.00 loops=1)
+ Buffers: shared hit=1
+ -> Graph Scan on graph_scan (actual rows=3.00
loops=3)
+ Filter: (v1.id = graph_scan.gs_seed)
+ min_depth: 1
+ max_depth: 3
+ direction: outgoing
+ Buffers: shared hit=51
+ -> Append (actual rows=0.90 loops=10)
+ Buffers: shared hit=51
+ -> Seq Scan on e1_2 (actual rows=1.00
loops=3)
+ Filter: (id_1 = $0)
+ Rows Removed by Filter: 2
+ Buffers: shared hit=3
+ -> Seq Scan on e1_2 (actual rows=0.00
loops=3)
+ Filter: ((id_2_1 = $2) AND
(id_2_2 = $3))
+ Rows Removed by Filter: 3
+ Buffers: shared hit=3
+ -> Bitmap Heap Scan on e1_3 (actual
rows=0.67 loops=3)
+ Recheck Cond: (id_1 = $0)
+ Heap Blocks: exact=1
+ Buffers: shared hit=4
+ -> Bitmap Index Scan on
e1_3_pkey (actual rows=0.67 loops=3)
+ Index Cond: (id_1 = $0)
+ Index Searches: 3
+ Buffers: shared hit=3
+ -> Bitmap Heap Scan on e1_3 (actual
rows=0.00 loops=3)
+ Recheck Cond: (id_3 = $2)
+ -> Bitmap Index Scan on
e1_3_pkey (actual rows=0.00 loops=3)
+ Index Cond: (id_3 = $2)
+ Index Searches: 0
+ -> Seq Scan on e2_1 (actual rows=0.00
loops=3)
+ Filter: ((id_2_1 = $0) AND
(id_2_2 = $1))
+ Rows Removed by Filter: 2
+ Buffers: shared hit=3
+ -> Seq Scan on e2_1 (actual rows=0.00
loops=3)
+ Filter: (id_1 = $2)
+ Rows Removed by Filter: 2
+ Buffers: shared hit=3
+ -> Nested Loop (actual rows=2.00 loops=1)
+ Buffers: shared hit=62
+ -> Nested Loop (actual rows=9.00 loops=1)
+ Buffers: shared hit=52
+ -> Seq Scan on v1 v1_1 (actual rows=3.00 loops=1)
+ Buffers: shared hit=1
+ -> Graph Scan on graph_scan_1 (actual rows=3.00 loops=3)
+ Filter: (v1_1.id = graph_scan_1.gs_seed)
+ min_depth: 1
+ max_depth: 3
+ direction: outgoing
+ Buffers: shared hit=51
+ -> Append (actual rows=0.90 loops=10)
+ Buffers: shared hit=51
+ -> Seq Scan on e1_2 (actual rows=1.00
loops=3)
+ Filter: (id_1 = $4)
+ Rows Removed by Filter: 2
+ Buffers: shared hit=3
+ -> Seq Scan on e1_2 (actual rows=0.00
loops=3)
+ Filter: ((id_2_1 = $6) AND (id_2_2 =
$7))
+ Rows Removed by Filter: 3
+ Buffers: shared hit=3
+ -> Bitmap Heap Scan on e1_3 (actual
rows=0.67 loops=3)
+ Recheck Cond: (id_1 = $4)
+ Heap Blocks: exact=1
+ Buffers: shared hit=4
+ -> Bitmap Index Scan on e1_3_pkey
(actual rows=0.67 loops=3)
+ Index Cond: (id_1 = $4)
+ Index Searches: 3
+ Buffers: shared hit=3
+ -> Bitmap Heap Scan on e1_3 (actual
rows=0.00 loops=3)
+ Recheck Cond: (id_3 = $6)
+ -> Bitmap Index Scan on e1_3_pkey
(actual rows=0.00 loops=3)
+ Index Cond: (id_3 = $6)
+ Index Searches: 0
+ -> Seq Scan on e2_1 (actual rows=0.00
loops=3)
+ Filter: ((id_2_1 = $4) AND (id_2_2 =
$5))
+ Rows Removed by Filter: 2
+ Buffers: shared hit=3
+ -> Seq Scan on e2_1 (actual rows=0.00
loops=3)
+ Filter: (id_1 = $6)
+ Rows Removed by Filter: 2
+ Buffers: shared hit=3
+ -> Index Scan using v3_pkey on v3 (actual rows=0.22 loops=9)
+ Index Cond: (id = graph_scan_1.gs_term)
+ Index Searches: 9
+ Buffers: shared hit=10
+ Planning:
+ Buffers: shared hit=46
+(104 rows)
+
-- Locking clause on GRAPH_TABLE
SELECT * FROM GRAPH_TABLE (g1 MATCH (src IS vl1) COLUMNS (src.vname)) gt FOR
UPDATE OF gt; -- not supported
ERROR: FOR UPDATE cannot be applied to GRAPH_TABLE
diff --git a/src/test/regress/sql/graph_table.sql
b/src/test/regress/sql/graph_table.sql
index 8f5c98c0c6e..2d2fcdaa6da 100644
--- a/src/test/regress/sql/graph_table.sql
+++ b/src/test/regress/sql/graph_table.sql
@@ -680,6 +680,15 @@ SELECT src, dst FROM GRAPH_TABLE (g1 MATCH (a IS vl1)-[e
IS el1]->{1,2}(c IS vl3
-- graph-level WHERE mixing a relational and a VLE-list reference
SELECT src, dst FROM GRAPH_TABLE (g1 MATCH (a IS vl1)-[e IS el1]->{1,3}(c IS
vl3) WHERE cardinality(e.ename) = 1 AND a.vname = 'v11' COLUMNS (a.vname AS
src, c.vname AS dst)) ORDER BY src, dst;
+-- EXPLAIN on a GraphScan: the plan shows "Graph Scan" plus its inner
+-- (1-hop expansion) child. COSTS OFF keeps this deterministic.
+EXPLAIN (COSTS OFF)
+SELECT src, dst FROM GRAPH_TABLE (g1 MATCH (a IS vl1)-[e IS el1]->{1,3}(c IS
vl3) COLUMNS (a.vname AS src, c.vname AS dst)) ORDER BY src, dst;
+-- same, with ANALYZE: exercises actually running the inner plan copies
+-- (not just planning/displaying them).
+EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
+SELECT src, dst FROM GRAPH_TABLE (g1 MATCH (a IS vl1)-[e IS el1]->{1,3}(c IS
vl3) COLUMNS (a.vname AS src, c.vname AS dst)) ORDER BY src, dst;
+
-- Locking clause on GRAPH_TABLE
SELECT * FROM GRAPH_TABLE (g1 MATCH (src IS vl1) COLUMNS (src.vname)) gt FOR
UPDATE OF gt; -- not supported
SELECT * FROM GRAPH_TABLE (g1 MATCH (src IS vl1) COLUMNS (src.vname)) gt FOR
UPDATE; -- ignored
