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

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