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

Hello Ashutosh,
Thanks for the review

From: Ashutosh Bapat <ashutosh(dot)bapat(dot)oss(at)gmail(dot)com>
To: ayoub kazar <ayoub(dot)kazar(at)data-bene(dot)io>
Cc: pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>
Date: Thursday, 30 July 2026 2:21 PM CEST
Subject: 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 < [ mailto:ayoub(dot)kazar(at)data-bene(dot)io | ayoub(dot)kazar(at)data-bene(dot)io ] > wrote:

BQ_BEGIN
On 2026-07-16 14:27, Ashutosh Bapat wrote:
> On Thu, Jul 16, 2026 at 2:46 PM < [ mailto:ayoub(dot)kazar(at)data-bene(dot)io | 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 = [ http://v1.id/ | v1.id ] AND e.dst = [ http://v2.id/ | v2.id ] )
>> OR (e.src = [ http://v2.id/ | v2.id ] AND e.dst = [ http://v1.id/ | 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.

BQ_END

BQ_BEGIN

BQ_BEGIN

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

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?

BQ_END
Its using the cost based OR expansion from the plans i saw, so yes i suppose it is originally writing the graph query as JOIN with OR.
From many query plans that i saw from test queries, the only time the query was planned with an OR instead of UNION ALL was when stats weren't gathered and had very few rows, in all other tries it was all UNION ALL plans.

I just saw that the idea is patented [3] ; granted in 2018, i don't know much about patents but i see from the claims that we ONLY can't do a cost based optimization of this same idea (if we decided to) ?

BQ_BEGIN

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.

BQ_END
The only proof which is in the last message of thread:

for a query:
SELECT * FROM any_v WHERE (A OR B OR C).

we do:

SELECT * FROM any_v WHERE A
UNION ALL
SELECT * FROM any_v WHERE B AND !A
UNION ALL
SELECT * FROM any_v WHERE C AND !A AND !(B AND !A);
where !(Expr) means (NOT (expr) OR (EXPR) IS NULL)

This is the only thing i thought of which guarantees correctness when i was working on the patch.
I just check with the patent now, it discusses the same proof for de-duplicating results.

BQ_BEGIN

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.

BQ_END
As mentioned above from what i noticed from some tests on Oracle query plans nearly everytime an OR expansion was applied, given both this patch's idea (UNION ALL only on edge table to generate two directions data -> then join separately) is a special case of the OR expansion, i find it interesting to see if we can try to prove that in all cases we would want this instead of the normal OR that mostly implies the bitmap scan ; which might suggest handling this "easier" case in rewrite for graph queries.

BQ_BEGIN

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

BQ_END

[3] [ https://patents.justia.com/patent/20150234888 | https://patents.justia.com/patent/20150234888 ]

Regards,
Ayoub

BQ_BEGIN

BQ_END