Re: [SQL/PGQ] Early pruning for GRAPH_TABLE path generation

Hi Ashutosh,

On Thu, May 14, 2026 at 2:26 PM Ashutosh Bapat
<ashutosh(dot)bapat(dot)oss(at)gmail(dot)com> wrote:
>
> Hi Junwang,
> Thanks for working on this. The performance improvement is impressive.
> I haven't verified it myself though at this time.
>
> Henson said it right. The first version separately enumeration and
> conversion clearly to keep things simple. Things like variable length
> element patterns, embedded path patterns can change the way we
> enumerate the paths. Whatever the enumeration method is failing early
> is best strategy. However, the question is whether your implementation
> of "failing early" is going to make it difficult implement the above
> mentioned advanced features or simplify it or not affect those at all.
> We need to think and discuss a bit.

Yeah, it makes sense to me.

>
> Delaying "failing early" implementation till we implement those
> features is safest strategy. If the lack of it makes the feature
> prohibitively useless, we will need to implement it early and deal
> with the difficulties it brings. But the examples so far are mostly
> artificial, not practical. That doesn't make me feel like it's worth
> taking the risk. There are many other bugs that need to be fixed.
>
> I am very glad that this patch demonstrates that "failing early"
> improves things significantly. So we will incorporate this strategy
> sooner or later.

Sure, let's find out what's the best way.

>
> On Thu, May 14, 2026 at 6:08 AM Junwang Zhao <zhjwpku(at)gmail(dot)com> wrote:
> >
>
> Some cosmetic comments on v2
>
> + if (list_length(graph_path) == 1)
> + return true;
>
> I would move this earlier in the function, to make it more readable.

Done in attached v3.

>
> rev_feasible is clever, but may need more comments.

Added.

>
> How do we make sure that the edge direction checks in
> generate_query_for_graph_path and graph_path_edge_is_feasible remain
> consistent? What I had in mind instead was to start constructing Join
> tree while we are creating paths so that edge direction feasibility
> checks also create the edge connection quals avoiding the duplicate
> logic. However, we will need to make sure that any unusable objects we
> create during that process are discarded in time.
>
> It will be better to place CHECK_FOR_INTERRUPTS alongside stack depth
> check. But for it to be added there, we need an evidence that the
> function is really consuming a lot of time. Your earlier measurements
> hint towards that, but they are overall query times. Can you please
> share actual time spent in this function out of the total execution
> time?

I added temporary time logs around the generate_queries_for_path_pattern_recurse
in generate_queries_for_path_pattern, and got the path expansion
time consuming.

query time:

[local] zjw(at)postgres:5432-97559=# SELECT count(*) FROM GRAPH_TABLE (g5
MATCH (a IS
vl2)-[e1]->(b)-[e2]->(c)-[e3]->(d)-[e4]->(e) COLUMNS (a.id AS aid));
count
-------
0
(1 row)

Time: 5577.000 ms (00:05.577)

path expansion time:

2026-05-14 23:22:41.513 CST [97559] LOG: GRAPH_TABLE path expansion
took 4648.482 ms and generated 1 path queries

>
> If you separate CHECK_FOR_INTERRUPTS change as a separate patch, it
> can be committed independent of the optimization.

That's v3-0001 now.

Summary:

v3-0001: adds CHECK_FOR_INTERRUPTS() in recursive graph path query
generation to keep query cancellation responsive on complex patterns.
v3-0002: adds temporary timing logs to measure performance during
GRAPH_TABLE path expansion, not to be committed.
v3-0003: the failing early(or early pruning) logic with comments resolved.
v3-0004: adds a test which enumerates the full N^K combinations before
the early pruning logic, with Henson's last comment resolved.

>
> --
> Best Wishes,
> Ashutosh Bapat

--
Regards

Junwang Zhao