From: Henson Choi Date: Thu, 17 Sep 2026 11:30:00 +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. The chain is threaded through every node of a copy, not through the roots alone. Both copies are ExecInitNode() of copyObject() of the same Plan, so planstate_tree_walker() visits them in the same order: graph_link_copy() collects the previous copy in that order and walks the new one, pairing them up. A node's down is then the node in the same position at the next depth, and the root's chain is, as the special case, the per-depth copies in order -- which is what GraphScanState.inner follows when descending and backtracking, so no separate structure is needed for that. Every node needs its own link because EXPLAIN prints the whole tree below the "Inner" child. ExecShutdownPlanStateChain() accordingly makes one pass over the tree, each node folding its own chain via InstrEndLoop() and InstrAggNode() -- the same order ExplainNode() itself relies on for the node it prints. Shutdown stays on the root's chain, being per copy: ExecShutdownNode() recurses into a copy's tree by itself. ExecShutdownGraphScan() is a one-line call to this, hooked into ExecShutdownNode_walker() the same way Gather is. Two things are left open. Part of the rollup has to be done per node type. InstrAggNode() covers PlanState.instrument, but an index scan's Index Searches comes from IndexScanInstrumentation instead, so it keeps depth 0's value and now disagrees with the loops count beside it. explain.c's show_indexscan_info() already sums the parallel workers' copies of that counter in the same spot and the chain wants the same there. ExecShutdownPlanStateChain() also adds the same numbers again if it runs more than once, which a NO SCROLL cursor fetched in batches does. Running the rollup only once would instead drop everything after the first batch, so this needs to fold a delta. This is a design proposal rather than a finished patch: up/down on PlanState needs its own review before going anywhere near master. --- 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..da799169d5d 100644 --- a/src/backend/executor/execProcnode.c +++ b/src/backend/executor/execProcnode.c @@ -765,6 +765,67 @@ ExecShutdownNode(PlanState *node) (void) ExecShutdownNode_walker(node, NULL); } +/* + * Fold each node's own up/down chain into that node, over the whole tree. + * + * A chain member 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 a chain is only + * ever its head, so a member's last cycle would otherwise still be + * unfinalized (instrument->running) when InstrAggNode asserts against that. + */ +static bool +ExecAggPlanStateChain_walker(PlanState *node, void *context) +{ + if (node->instrument != NULL) + { + PlanState *p; + + for (p = node->down; p != NULL; p = p->down) + { + if (p->instrument == NULL) + continue; + InstrEndLoop(p->instrument); + InstrAggNode(node->instrument, p->instrument); + } + } + + return planstate_tree_walker(node, ExecAggPlanStateChain_walker, context); +} + +/* + * ExecShutdownPlanStateChain + * + * A node type may thread its own PlanState instances into doubly-linked + * sibling chains 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, linking the copies node by node. Such chains are 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 them + * a shutdown chance and rolls their instrumentation up. The owning node + * calls this once, on the head of the tree it exposes to EXPLAIN, from its + * own ExecShutdownXXX() function. + * + * Shutdown is per copy, so it walks head's own chain alone: ExecShutdownNode() + * recurses into each copy's tree by itself. The instrumentation rollup is + * per node instead -- EXPLAIN prints the whole tree below head, so every node + * in it, and not just head, has to take in what its counterparts recorded. + */ +void +ExecShutdownPlanStateChain(PlanState *head) +{ + PlanState *p; + + if (head == NULL) + return; + + for (p = head; p != NULL; p = p->down) + ExecShutdownNode(p); + + (void) ExecAggPlanStateChain_walker(head, NULL); +} + static bool ExecShutdownNode_walker(PlanState *node, void *context) { @@ -793,6 +854,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..81d7c14ff7b 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 @@ -41,6 +56,7 @@ #include "executor/executor.h" #include "executor/nodeGraphScan.h" #include "miscadmin.h" +#include "nodes/nodeFuncs.h" #include "optimizer/cost.h" #include "rewrite/rewriteGraphTable.h" #include "utils/array.h" @@ -50,22 +66,25 @@ 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 void graph_link_copy(PlanState *prev, PlanState *new); +static bool graph_collect_walker(PlanState *ps, void *context); +static bool graph_link_walker(PlanState *ps, void *context); 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 +162,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 +170,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 +205,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 +217,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 +242,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 +256,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 +283,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 +291,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 +303,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 +325,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 +369,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 +391,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 +407,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 +431,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 +466,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 +487,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 +500,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 +514,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 +531,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 +548,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 +558,88 @@ 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) + graph_link_copy(cur, 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 +693,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 +709,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 +760,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 +782,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 +795,101 @@ 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); +} + +/* + * Context for graph_link_copy(): the nodes of the copy being linked onto, in + * walk order, and a cursor over them while the new copy is walked. + */ +typedef struct GraphLinkContext +{ + List *nodes; /* PlanStates of the previous copy */ + ListCell *cur; /* next one to pair up */ +} GraphLinkContext; + +/* Collect one copy's PlanStates into context->nodes, in walk order. */ +static bool +graph_collect_walker(PlanState *ps, void *context) +{ + GraphLinkContext *ctx = (GraphLinkContext *) context; + + ctx->nodes = lappend(ctx->nodes, ps); + return planstate_tree_walker(ps, graph_collect_walker, context); +} + +/* Link each node of the new copy onto its counterpart in the previous one. */ +static bool +graph_link_walker(PlanState *ps, void *context) +{ + GraphLinkContext *ctx = (GraphLinkContext *) context; + PlanState *prev; + + Assert(ctx->cur != NULL); + prev = (PlanState *) lfirst(ctx->cur); + ctx->cur = lnext(ctx->nodes, ctx->cur); + + /* the two copies are ExecInitNode(copyObject()) of the same Plan */ + Assert(nodeTag(prev) == nodeTag(ps)); + Assert(prev->plan->plan_node_id == ps->plan->plan_node_id); + + ps->up = prev; + prev->down = ps; + + return planstate_tree_walker(ps, graph_link_walker, context); +} + +/* + * Thread a newly made copy of the inner plan onto the previous one, node by + * node rather than at the root alone. + * + * Both trees are ExecInitNode(copyObject()) of the same Plan, so they have + * the same shape and planstate_tree_walker() visits them in the same order; + * pairing them in that order gives every node the counterpart it has at the + * next depth. The root's own chain is then, as a special case, the + * per-depth copies in order -- which is what GraphScanState.inner walks when + * descending and backtracking, so no separate structure is needed for that. + * + * Every node needs its own link because EXPLAIN prints the whole tree below + * the "Inner" child: the instrumentation of each node, not just the root's, + * has to be merged across the depths (see ExecShutdownPlanStateChain()). + */ +static void +graph_link_copy(PlanState *prev, PlanState *new) +{ + GraphLinkContext ctx; + + ctx.nodes = NIL; + ctx.cur = NULL; + (void) graph_collect_walker(prev, &ctx); + + ctx.cur = list_head(ctx.nodes); + (void) graph_link_walker(new, &ctx); + Assert(ctx.cur == NULL); + + list_free(ctx.nodes); +} + 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 +907,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 +929,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 +950,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 +990,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 +1017,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..20da91d2067 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..bcee1e6f917 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -1209,6 +1209,16 @@ 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 +1932,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 +1956,32 @@ 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..45fa15b72ff 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=0.50 loops=10) + Filter: (id_1 = $0) + Rows Removed by Filter: 2 + Buffers: shared hit=10 + -> Seq Scan on e1_2 (actual rows=0.00 loops=10) + Filter: ((id_2_1 = $2) AND (id_2_2 = $3)) + Rows Removed by Filter: 3 + Buffers: shared hit=10 + -> Bitmap Heap Scan on e1_3 (actual rows=0.20 loops=10) + Recheck Cond: (id_1 = $0) + Heap Blocks: exact=1 + Buffers: shared hit=11 + -> Bitmap Index Scan on e1_3_pkey (actual rows=0.20 loops=10) + Index Cond: (id_1 = $0) + Index Searches: 3 + Buffers: shared hit=10 + -> Bitmap Heap Scan on e1_3 (actual rows=0.00 loops=10) + Recheck Cond: (id_3 = $2) + -> Bitmap Index Scan on e1_3_pkey (actual rows=0.00 loops=10) + Index Cond: (id_3 = $2) + Index Searches: 0 + -> Seq Scan on e2_1 (actual rows=0.20 loops=10) + Filter: ((id_2_1 = $0) AND (id_2_2 = $1)) + Rows Removed by Filter: 2 + Buffers: shared hit=10 + -> Seq Scan on e2_1 (actual rows=0.00 loops=10) + Filter: (id_1 = $2) + Rows Removed by Filter: 2 + Buffers: shared hit=10 + -> 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=0.50 loops=10) + Filter: (id_1 = $4) + Rows Removed by Filter: 2 + Buffers: shared hit=10 + -> Seq Scan on e1_2 (actual rows=0.00 loops=10) + Filter: ((id_2_1 = $6) AND (id_2_2 = $7)) + Rows Removed by Filter: 3 + Buffers: shared hit=10 + -> Bitmap Heap Scan on e1_3 (actual rows=0.20 loops=10) + Recheck Cond: (id_1 = $4) + Heap Blocks: exact=1 + Buffers: shared hit=11 + -> Bitmap Index Scan on e1_3_pkey (actual rows=0.20 loops=10) + Index Cond: (id_1 = $4) + Index Searches: 3 + Buffers: shared hit=10 + -> Bitmap Heap Scan on e1_3 (actual rows=0.00 loops=10) + Recheck Cond: (id_3 = $6) + -> Bitmap Index Scan on e1_3_pkey (actual rows=0.00 loops=10) + Index Cond: (id_3 = $6) + Index Searches: 0 + -> Seq Scan on e2_1 (actual rows=0.20 loops=10) + Filter: ((id_2_1 = $4) AND (id_2_2 = $5)) + Rows Removed by Filter: 2 + Buffers: shared hit=10 + -> Seq Scan on e2_1 (actual rows=0.00 loops=10) + Filter: (id_1 = $6) + Rows Removed by Filter: 2 + Buffers: shared hit=10 + -> 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 diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index 4139baa405b..8df25c72ca4 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -1168,9 +1168,11 @@ GrantTargetType GraphElementPattern GraphElementPatternKind GraphLabelRef +GraphLinkContext GraphPattern GraphPropertyRef GraphTableParseState +GraphVidData Group GroupByColInfo GroupByOrdering