Re: [SQL/PGQ] Native executor for Graph query - Mailing list pgsql-hackers

Hi Henri,

You cited my VLE note as [1] back in July, so I owe you a careful
read.  The direction is right: taking execution out of the rewriter is
where Andres pointed.  My comment is about where the per-depth state
lives.

> I am open to any feedback you may have

Here is one.  The patch expresses the composite scan inside the node
rather than in the plan tree: GraphScan leaves lefttree and righttree
NULL and reimplements partition and view scanning inside
nodeGraphScan.c.  My impression reading it is that every kind of
scan -- foreign tables and the rest -- ends up having to be
reimplemented in there.  The per-depth state is then a stack of raw
TableScanDesc, and for anything but a plain table the cursor is one
per element rather than one per depth, so backtracking does not
propagate into a composite scan.

My suggestion is the following.  The note sketched the outer/inner
split and a per-depth stack of PlanStates; what it did not say, and
what I want to add, is that this has to work for an arbitrary inner
subtree:

    outer (lefttree)  = start vertices, scanned once
    inner (righttree) = edge scan for one vertex, parameterized

Push before descending, pop on backtrack, both against the inner
subtree.  What is pushed and popped is the PlanState: a depth reached
for the first time gets a new one, initialized as usual, and a depth
being reused is rescanned with the new parameter.  Each node type
implements this for its own state, so the inner can be an IndexScan,
an Append over partitions, a SubqueryScan over a view or a ForeignScan
without the graph node knowing which.

The part that needs care is shared state.  Some resources live on the
EState rather than on the node -- the parameter workspace, the SubPlan
states, the runtime pruning state -- so initializing or advancing one
depth's subplan has to be coordinated so that it does not disturb
another depth's.

Implementing this on every node type is a lot of work, so it may be
better to start with the few that matter -- Scan, IndexScan, Append --
and have the planner restrict a GraphScan's inner to those.  The set
can grow later without the shape changing.

What this buys is that the inner subplan is just a plan.  A single
label is a Scan or an IndexScan.  Several labels are an Append, and
the children under it need not be alike -- a sequential scan on one
table, an index scan on another, a ForeignScan on a third, whatever
the planner picks for each.  Partitioning and inheritance come along
the same way, since they are already Appends.

The same shape composes along the pattern as well.  If the outer is
itself a GraphScan, a multi-element pattern is a chain of these nodes,
each taking the vertex it needs from its outer.  A VLE element and a
fixed-length element then sit next to each other in that chain without
either having to know about the other.

A star pattern falls out of the same mechanism.  Since the inner is
parameterized from the outer tuple, the vertex it is parameterized by
does not have to be the last one on the path; any vertex already bound
will do.  So MATCH (a)->(b), (a)->(c) would be a chain again: the
first node binds a and b, and the second takes a, not b, from its
outer and scans the edges leaving it.  A branching pattern then needs
nothing beyond choosing which outer column parameterizes each inner.

There is a wider use for it as well.  If every PlanState could push
and pop, WITH RECURSIVE could be executed depth first, instead of
computing each level in turn and then sorting on the column that
SEARCH DEPTH FIRST adds.

I have another patch to wrap up, so I cannot give this much time at
the moment, but I hope it is of some use.

Best regards,
Henson