Re: [PATCH] Rewrite undirected edge patterns in GRAPH_TABLE using UNION ALL

Hi Ayoub,

I spent some time researching this problem. Here's what I found.

On Thu, Jul 16, 2026 at 7:16 PM <ayoub(dot)kazar(at)data-bene(dot)io> wrote:

> On 2026-07-16 14:27, Ashutosh Bapat wrote:
> > On Thu, Jul 16, 2026 at 2:46 PM <ayoub(dot)kazar(at)data-bene(dot)io> wrote:
>
> >> The attached patch changes how GRAPH_TABLE rewrites undirected edge
> >> patterns
> >> (-[e]-) to UNION ALL subquery instead of emitting an OR on both
> >> directions quals.
> >>
> >> Background
> >> ----------
> >>
> >> When an undirected edge pattern matches an edge table whose source and
> >> destination vertex table are the same, the current implementation
> >> combines the equi-join
> >> conditions for both traversal directions into a single OR qual:
> >>
> >> WHERE (e.src = v1.id AND e.dst = v2.id)
> >> OR (e.src = v2.id AND e.dst = v1.id)
> >>
> >> This generally implies using BitmapOr or a full OR evaluation which is
> >> very unefficient in queries with large intermediate results (see
> >> benchmarks below).
> >>
>

JOIN with OR was discussed previously at [1]. I think optimizing this query
pattern is better since it will help such queries generally not just when
they are generated by graph query rewrite.

>
> Q2 is the equivalent of what Oracle does, its makes a UNION ALL between
> two queries that each work on a single direction.
>

Oracle implements OR-expansion tranformation as a planner optimization [2].
I guess that it is writing graph query as JOIN with OR but the optimizer is
turning it into UNION instead of graph query rewriter turning it into a
UNION. Have you checked at what stage does Oracle introduce UNION?

The discussion in [1] seems to have stalled because there was no clear
proof of the transform being correct. Given that other products have
implemented the transformation, there is possibility that the proof of
correctness exists. It might be better to find that proof and resurrect the
old thread.

Also, given that the OR expansion was later replaced by cost based OR
expansion, the transformation may not always yield optimal results. So, we
should not always rewrite the undirected edge as UNION as the patch does.

[1]
https://www.postgresql.org/message-id/CAKJS1f9OPfZ4n9ozTeDMLpq6y10Ms3dVgQnepZ8xC0LyEcLNdQ%40mail.gmail.com
[2]
https://blogs.oracle.com/optimizer/optimizer-transformations-or-expansion

--
Best Wishes,
Ashutosh Bapat