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

*Classification: * Privacy: Basic Personal Data; Export Control:
Not Technical; National Security: Not National Security; Company
Classification: Airbus Amber; Business or Private Data: Business data

Hello,

Thanks for the message, it was helpful. I was far too focused on the
DFS part and completely forgot your decomposition into outer and
inner tree.
I already wanted to redo my implementation to make the changes
clearer, so that is as good a time as any to correct it. It should also
make the code far simpler.

However, considering b1f106c80[1], I am unsure how to proceed.
I think I will either reimplement only what I need, or build upon the
parent (like I did before).

Best Regards,
Henri GASC

1:
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=b1f106c80cbeb18d3a0219994d98a51a6eca8ede

On Mon, Sep 7, 2026 at 3:39 PM Henson Choi <assam258(at)gmail(dot)com> wrote:

> 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
>
The information in this e-mail is confidential. The contents may not be disclosed or used by anyone other than the addressee. Access to this e-mail by anyone else is unauthorised.
If you are not the intended recipient, please notify Airbus immediately and delete this e-mail.
Airbus cannot accept any responsibility for the accuracy or completeness of this e-mail as it has been sent over public networks. If you have any concerns over the content of this message or its Accuracy or Integrity, please contact Airbus immediately.
All outgoing e-mails from Airbus are checked using regularly updated virus scanning software but you should take whatever measures you deem to be appropriate to ensure that this message and any attachments are virus free.