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

Hello again,

On 2026-07-16 15:46, ayoub(dot)kazar(at)data-bene(dot)io wrote:
> On 2026-07-16 14:27, Ashutosh Bapat wrote:
>> Hi Ayoub,
>>
>> Thanks for the proposal. I think it's useful.
>>
>> On Thu, Jul 16, 2026 at 2:46 PM <ayoub(dot)kazar(at)data-bene(dot)io> wrote:
>>>
>>> Hello everyone,
>>>
>>> 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).
>>>
>>> What can we do
>>> --------------
>>>
>>> For the case where src and dest vertex patterns are different path
>>> factors, but same path element,
>>> the edge relation RTE is replaced with a UNION ALL subquery:
>>>
>>> (SELECT src, dst, ...other cols... FROM edge -- forward
>>> branch
>>> UNION ALL
>>> SELECT dst, src, ...other cols... FROM edge -- backward
>>> branch
>>> WHERE NOT (src = dst)) -- this
>>> excludes
>>> self-loops
>>
>>>
>>>
>>> Benchamrks
>>> ----------
>>> Using LSQB from LDBC [1], [2] picking only Q6 and Q9 which are the
>>> hardest queries (very large intermediate results) in the benchmark
>>> (doing undirected edge patterns, which is our target for
>>> improvement).
>>> Everything is ran on an Intel 1255U, 16GB RAM (everything warm),
>>> using
>>> Docker, running vscode and firefox at the same time.
>>>
>>> From [2] you can see query shapes, dataset sizes, degree
>>> distribution,
>>> etc.
>>
>> [2] points to a paper from where I couldn't find ready-to-run script
>> to verify your results. Will it be possible for you to create a
>> stand-alone benchmark or point to scripts which can be run against
>> PostgreSQL with less efforts?
>
> Here's a github repo [3] containing a full benchmark fork from original
> implementation.
> To run a specific system's benchs, cd into the system's dir and run:
>
> To download data:
> export MAX_SF=1
> scripts/download-projected-fk-data-sets.sh (SQL/PGQ uses this)
> scripts/download-merged-fk-data-sets.sh (SQL only systems should use
> this schema)
>
> set MAX_SF to your max scale factor you want (everything below it will
> be downloaded), original readme talks about these anyway too.
>
>
> export SF=1
> ./init-and-load.sh && ./run.sh && ./stop.sh
>
> ./init-and-load.sh only loads and starts the container so you can do
> whatever you want with psql later.
> ./run.sh runs the benchmark queries (for postgres SQL/PGQ i've only put
> queries that are supported, queries with multi path patterns are left
> out as SQL only (not relevant to our discussion))
>
> Postgres systems also have config with them too that you can change
> (they are set to something that matches my machine)
> For postgres-patched you should compile our patch and build image for
> it (see readme.md in postgres-patched).
>
> ./stop.sh kills the container
>
> You can also use benchmark.sh which runs different systems with
> different SFs (at choice) all together in same script.
>
> You find the results in results dir.
>
>
>>
>>>
>>> Here are both queries so you don't have to...
>>>
>>> Q6:
>>> SELECT count(*)
>>> FROM GRAPH_TABLE (lsqb
>>> MATCH (person1 IS Person)-[k IS knows]-(person2 IS Person)-[k2
>>> IS
>>> knows]-(person3 IS Person)-[hi IS hasInterest]->(T IS Tag)
>>> WHERE person1.id <> person3.id
>>> COLUMNS (1 AS dummy)
>>> );
>>>
>>> Q9:
>>> SELECT count(*)
>>> FROM GRAPH_TABLE (lsqb
>>> MATCH (person1 IS Person)-[k IS knows]-(person2 IS Person)-[k2 IS
>>> knows]-(person3 IS Person)-[hi IS hasInterest]->(T IS Tag)
>>> WHERE person1.id <> person3.id
>>> COLUMNS (person1.id as p1_id, person3.id as p3_id)
>>> ) g
>>> LEFT JOIN (select person1id, person2id FROM Person_knows_Person UNION
>>> ALL select person2id, person1id from Person_knows_person) pkp3
>>> ON pkp3.Person1Id = g.p1_id
>>> AND pkp3.Person2Id = g.p3_id
>>> WHERE pkp3.Person1Id IS NULL;
>>>
>>
>> These queries have 7-way joins. But I think the join of interest here
>> is only (person1 IS Person)-[k IS knows]-(person2 IS Person). If you
>> could show results with just that path pattern, it will be easier to
>> understand how the plan changes.
>
> Understandable, so using the LSQB dataset of SF 1, we craft simple
> query to see the optimization:
>
> In PostgreSQL 19beta1
>
> explain analyze SELECT count(*)
> FROM GRAPH_TABLE (lsqb
> MATCH (person1 IS Person)-[k IS knows]-(person2 IS Person)
> COLUMNS (1 AS dummy)
> );
>
> QUERY PLAN
> --------------------------------------------------------------------------------------------------------------------------------------------------------------
> Aggregate (cost=263539476.97..263539476.97 rows=1 width=8) (actual
> time=179822.587..179822.588 rows=1.00 loops=1)
> Buffers: shared hit=726452684
> -> Nested Loop (cost=1.04..263538345.50 rows=452586 width=0)
> (actual time=6.756..179801.924 rows=452586.00 loops=1)
> Buffers: shared hit=726452684
> -> Nested Loop (cost=0.00..1512845.50 rows=121000000
> width=16) (actual time=0.036..5676.880 rows=121000000.00 loops=1)
> Buffers: shared hit=98
> -> Seq Scan on person (cost=0.00..159.00 rows=11000
> width=8) (actual time=0.017..2.172 rows=11000.00 loops=1)
> Buffers: shared hit=49
> -> Materialize (cost=0.00..214.00 rows=11000 width=8)
> (actual time=0.000..0.164 rows=11000.00 loops=11000)
> Storage: Memory Maximum Storage: 472kB
> Buffers: shared hit=49
> -> Seq Scan on person person_1
> (cost=0.00..159.00 rows=11000 width=8) (actual time=0.006..0.390
> rows=11000.00 loops=1)
> Buffers: shared hit=49
> -> Bitmap Heap Scan on person_knows_person (cost=1.04..2.16
> rows=1 width=16) (actual time=0.001..0.001 rows=0.00 loops=121000000)
> Recheck Cond: (((person.id = person1id) AND (person_1.id
> = person2id)) OR ((person_1.id = person1id) AND (person.id =
> person2id)))
> Heap Blocks: exact=452586
> Buffers: shared hit=726452586
> -> BitmapOr (cost=1.04..1.04 rows=1 width=0) (actual
> time=0.001..0.001 rows=0.00 loops=121000000)
> Buffers: shared hit=726000000
> -> Bitmap Index Scan on person_knows_person_pkey
> (cost=0.00..0.52 rows=1 width=0) (actual time=0.000..0.000 rows=0.00
> loops=121000000)
> Index Cond: ((person1id = person.id) AND
> (person2id = person_1.id))
> Index Searches: 121000000
> Buffers: shared hit=363000000
> -> Bitmap Index Scan on person_knows_person_pkey
> (cost=0.00..0.52 rows=1 width=0) (actual time=0.001..0.001 rows=0.00
> loops=121000000)
> Index Cond: ((person1id = person_1.id) AND
> (person2id = person.id))
> Index Searches: 121000000
> Buffers: shared hit=363000000
> Planning Time: 0.358 ms
> Execution Time: 179822.739 ms
> (29 rows)
>
>
>
> In PostgreSQL patched:
>
>
> QUERY PLAN
> ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> Finalize Aggregate (cost=9483.00..9483.01 rows=1 width=8) (actual
> time=37.633..39.226 rows=1.00 loops=1)
> Buffers: shared hit=2790
> -> Gather (cost=9482.78..9482.99 rows=2 width=8) (actual
> time=37.459..39.219 rows=3.00 loops=1)
> Workers Planned: 2
> Workers Launched: 2
> Buffers: shared hit=2790
> -> Partial Aggregate (cost=8482.78..8482.79 rows=1 width=8)
> (actual time=33.023..33.027 rows=1.00 loops=3)
> Buffers: shared hit=2790
> -> Hash Join (cost=593.00..8012.52 rows=188106
> width=0) (actual time=2.452..30.330 rows=150862.00 loops=3)
> Hash Cond: (person_knows_person_1.person1id =
> person_1.id)
> Buffers: shared hit=2790
> -> Hash Join (cost=296.50..7222.05 rows=188106
> width=8) (actual time=1.241..18.724 rows=150862.00 loops=3)
> Hash Cond: (person_knows_person_1.person2id
> = person.id)
> Buffers: shared hit=2643
> -> Parallel Append (cost=0.00..6431.58
> rows=188106 width=16) (actual time=0.014..7.103 rows=150862.00 loops=3)
> Buffers: shared hit=2496
> -> Parallel Seq Scan on
> person_knows_person person_knows_person_1 (cost=0.00..2911.92
> rows=132448 width=16) (actual time=0.009..2.916 rows=75431.00 loops=3)
> Filter: (person1id <> person2id)
> Buffers: shared hit=1248
> -> Parallel Seq Scan on
> person_knows_person (cost=0.00..2579.14 rows=133114 width=16) (actual
> time=0.010..2.370 rows=113146.50 loops=2)
> Buffers: shared hit=1248
> -> Hash (cost=159.00..159.00 rows=11000
> width=8) (actual time=1.170..1.170 rows=11000.00 loops=3)
> Buckets: 16384 Batches: 1 Memory
> Usage: 558kB
> Buffers: shared hit=147
> -> Seq Scan on person
> (cost=0.00..159.00 rows=11000 width=8) (actual time=0.012..0.338
> rows=11000.00 loops=3)
> Buffers: shared hit=147
> -> Hash (cost=159.00..159.00 rows=11000 width=8)
> (actual time=1.154..1.155 rows=11000.00 loops=3)
> Buckets: 16384 Batches: 1 Memory Usage:
> 558kB
> Buffers: shared hit=147
> -> Seq Scan on person person_1
> (cost=0.00..159.00 rows=11000 width=8) (actual time=0.029..0.418
> rows=11000.00 loops=3)
> Buffers: shared hit=147
> Planning Time: 0.454 ms
> Execution Time: 39.359 ms
> (33 rows)
>
> Time: 40.419 ms
>
> Both have same setup, indexes, etc.
>
>>
>> Your query has two such edges in any direction, which is an indicator
>> that you have thought about multiple any directional queries as well.
>> Adding a test like that in graph_table.sql would be helpful; we have
>> queries with one edge in any direction but not multiple.
>>
>>> Format:
>>> Postgres-Version ScaleFactor Query-Number Latency(s) query result
>>> (count(*))
>>>
>>> SF 0.1:
>>> PostgreSQL-PGQ (v19beta1) 0.1 6 91.6983 55607896
>>> PostgreSQL-PGQ (v19beta1) 0.1 9 99.2815 51009398
>>> PostgreSQL-Patched 0.1 6 1.6103 55607896
>>> PostgreSQL-Patched 0.1 9 2.1719 51009398
>>>
>>> SF 0.3: (timeout set to 300 seconds)
>>> PostgreSQL-PGQ (v19beta1) 0.3 6 300.0021 TIMEOUT
>>> PostgreSQL-PGQ (v19beta1) 0.3 9 300.3658 TIMEOUT
>>> PostgreSQL-Patched 0.3 6 9.1556 285509755
>>> PostgreSQL-Patched 0.3 9 11.0674 268837983
>>>
>>> SF 1: (timeout set to 40 minutes)
>>> PostgreSQL-PGQ (v19beta1) 1 6 2400.1786 TIMEOUT
>>> PostgreSQL-PGQ (v19beta1) 1 9 2400.1071 TIMEOUT
>>> PostgreSQL-Patched 1 6 41.7566 1668134320
>>> PostgreSQL-Patched 1 9 98.0370 1596153418
>>>
>>
>> It's hard for me to understand what all those numbers are (some column
>> headers would help). I can guess, but it's better to be sure. And if
>> my guess is correct the results are impressive.
> The format of header is same as mentioned:
> Postgres-Version ScaleFactor Query-Number Latency(s) query
> result(number of rows: its a count(*))
>
> Example:
> PostgreSQL-Patched 0.3 6 9.1556 285509755
>
> PostgreSQL-Patched: is the system being benchmarked.
> 0.3 is the scale factor.
> 6 is the query number in the LSQB benchmark.
> 9.1556 execution time in seconds.
> 285509755 row count (all queries are count(*) at the very end).
>
>>
>> Does your optimization work only when the source and destination are
>> the same vertex tables OR it works for different source and
>> destination tables as well? Your example indicates the first, so
>> please confirm.
>
> If i'm not mistaken, semantically we only return both directions
> results if source and destination are the same vertex tables, think of
> (person)-[works_at]-(company) ; this relation would've been defined
> where person is its source and company as it destination, so we would
> never return an edge row that is directed from company -> person,
> therefore we only care about a same vertex tables case (for the same
> reason it was for the original implementation with OR).
>
>>
>> I am wondering whether we have an opportunity for some kind of planner
>> optimization here. What you are effectively claiming is query Q1 below
>> performs worse than query Q2 below.
>> Q1. SELECT * from t1 a, t2 b, t1 a where a.key = b.src_key AND
>> b.dst_key = c.key OR c.key = b.src_key AND b.dst_key = a.key
>> Q2. SELECT * FROM t1 a, t2 b, t1 a WHERE a.key = b.src_key AND
>> b.dst_key = c.key UNION ALL SELECT * FROM t1 a, t2 b, t1 a WHERE c.key
>> = b.src_key AND b.dst_key = a.key
>
> Q2 is the equivalent of what Oracle does, its makes a UNION ALL between
> two queries that each work on a single direction.
>
> What our patch does: It generates both edge directions (tuples) with
> UNION ALL, then continue its join back to the vertices, so we only
> replaced the edge path_element's RTE_RELATION by emitting basically the
> same edge table but its tuples are directed in both directions
>
> (SELECT src, dst, ...other cols... FROM edge) -- this is forward branch
> UNION ALL
> (SELECT dst, src, ...other cols... FROM edge WHERE NOT (src = dst) )
> -- this is backward branch
> )
> This would emit from the original edge table containing an edge (src=1,
> dest=2)
> the result of:
> (src=1, dest=2)
> (src=2, dest=1)
>
> at this point the only thing left is joining back.
>
> WHERE NOT (src = dst) to exclude self loops (which would have already
> appeared in the forward branch)
>
> DuckPGQ does same approach as this patch, but it has a bug where it
> duplicates the self loop edge rows, hence the usage of WHERE NOT (src =
> dst) in one of the branches.
>
>>
>> I see that BitmapOr is performing some kind of UNION ALL within it.
>> Why isn't that speeding up the first query? Is it that the plan with
>> BitmapOr doesn't use parallel query? Is there some opportunity to
>> improve BitmapOr itself? I could not find the unpatched EXPLAIN
>> ANALYZE plans to figure that out myself.
> I didn't understand this very well, but we'll comeback to it after this
> when the previous clarifications have made it clearer.
>>
>> I think if you use a smaller dataset which is large enough to show the
>> performance difference and use queries with smaller path patterns, you
>> will be able to finish the queries within a reasonable time and get
>> full EXPLAIN ANALYZE plans even for unpatched SQL/PGQ.
>
>
> Regards,
> Ayoub

Previously i wrote:
>> The subqueries are eventually pulled up by the planner as its a simple
>> union containing simple subquries too, everything should be pulled up
>> with >> pull_up_simple_union_all and pull_up_simple_subquery (if i'm
>> not mistaked)
Indeed i missed something about this, the actual place where i child
subquery is append-able or not is at `is_safe_append_member` in
src/backend/optimizer/prep/prepjointree.c

The inaccurate part is about UNION ALL child queries ALWAYS being pulled
up, when a child has a WHERE clause, it can't be pulled up, because we
don't have quals in AppendRelInfo. In our case, that child is the
backward branch that has src != dest that eliminates duplicate edge
loops.

The previous patch got lucky and had the subqueries pulled up for
another reason, at the very end of planning `trivial_subqueryscan` asks
the question on every subquery "is this actually doing any work ?"
> * We can delete it if it has no qual to check and the targetlist just
> * regurgitates the output of the child plan.
the RTE_SUBQUERY for the backward branch doesn't have a qual (the src !=
dest qual is actually below ; in the underlying scan), but:

If the path does the edge-vertex linking with a hash join or merge join,
the RTE_SUBQUERY still doesn't have a qual, good for us:
explain SELECT *
FROM GRAPH_TABLE (lsqb
MATCH (p1 IS Person)-[k IS knows]-(p2 IS Person)
COLUMNS (p1.id AS p1id, p2.id AS p2id)
);
QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Hash Join (cost=92.50..1069.84 rows=36179 width=16)
Hash Cond: (person_knows_person.person2id = person_1.id)
-> Hash Join (cost=46.25..928.39 rows=36179 width=16)
Hash Cond: (person_knows_person.person1id = person.id)
-> Append (cost=0.00..786.93 rows=36179 width=16)
-> Seq Scan on person_knows_person (cost=0.00..280.35
rows=18135 width=16)
-> Seq Scan on person_knows_person person_knows_person_1
(cost=0.00..325.69 rows=18044 width=16)
Filter: (person1id <> person2id)
-> Hash (cost=25.00..25.00 rows=1700 width=8)
-> Seq Scan on person (cost=0.00..25.00 rows=1700
width=8)
-> Hash (cost=25.00..25.00 rows=1700 width=8)
-> Seq Scan on person person_1 (cost=0.00..25.00 rows=1700
width=8)
(12 rows)

Now the problem is if a nested loop join is considered where our edge
UNION ALL becomes parametrized:

explain SELECT *
FROM GRAPH_TABLE (lsqb
MATCH (p1 IS Person)-[k IS knows]-(p2 IS Person)-[k2 IS
knows]-(p3 IS Person)
COLUMNS (p1.id AS p1id, p2.id AS p2id)
);

QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Gather (cost=1001.13..719821.01 rows=289123 width=16)
Workers Planned: 2
-> Nested Loop (cost=1.13..689908.71 rows=120468 width=16)
-> Nested Loop (cost=0.85..654330.07 rows=120468 width=24)
-> Nested Loop (cost=0.56..5882.58 rows=9238 width=24)
-> Nested Loop (cost=0.28..3154.25 rows=9238
width=16)
-> Parallel Append (cost=0.00..426.22
rows=9237 width=16)
-> Parallel Index Only Scan using
person_knows_person_pkey on person_knows_person person_knows_person_2
(cost=0.29..215.66 rows=6504 width=16)
Filter: (person1id <> person2id)
-> Parallel Seq Scan on
person_knows_person (cost=0.00..164.37 rows=6537 width=16)
-> Index Only Scan using person_pkey on
person (cost=0.28..0.30 rows=1 width=8)
Index Cond: (id =
person_knows_person_2.person2id)
-> Index Only Scan using person_pkey on person
person_1 (cost=0.28..0.30 rows=1 width=8)
Index Cond: (id =
person_knows_person_2.person1id)
-> Memoize (cost=0.30..376.92 rows=63 width=16)
Cache Key: person_1.id
Cache Mode: logical
Estimates: capacity=1700 distinct keys=1700
lookups=9238 hit percent=81.60%
-> Append (cost=0.29..376.91 rows=63 width=16)
-> Index Only Scan using
person_knows_person_pkey on person_knows_person person_knows_person_1
(cost=0.29..0.47 rows=8 width=16)
Index Cond: (person1id = person_1.id)
-> Subquery Scan on unnamed_subquery
(cost=0.00..376.12 rows=55 width=16)
Filter: (person_1.id =
unnamed_subquery.person1id)
-> Seq Scan on person_knows_person
person_knows_person_3 (cost=0.00..237.91 rows=11057 width=16)
Filter: (person1id <> person2id)
-> Index Only Scan using person_pkey on person person_2
(cost=0.28..0.30 rows=1 width=8)
Index Cond: (id = person_knows_person_1.person2id)
(27 rows)

In our last chance of getting the child pulled up in
`trivial_subqueryscan`, the RTE_SUBQUERY now has a qual `Filter:
(person_1.id = unnamed_subquery.person1id)`, this comes with some extra
cost (i don't think we want that ?).

I see a solution to this, but it can be considered dirty:
Lets try to not rely on `trivial_subqueryscan` and make sure children
are guaranteed to be pulled up in `is_safe_append_member`, our issue was
the WHERE clause in backward branch, so if we try to rewrite the query
into something like this:
SELECT ....
FROM person p1
JOIN (
SELECT p1, p2 FROM (
-- Fwd Branch
SELECT person1id as p1, person2id as p2, true AS is_fwd
FROM person_knows_person

UNION ALL

-- Bwd Branch
SELECT person2id as p1, person1id as p2, false AS is_fwd
FROM person_knows_person
) unnamed_subquery
WHERE is_fwd OR p1 <> p2 -- Outer filter
) knows ON p1.id = knows.p1;

Now both branches don't have a qual, the `WHERE is_fwd OR p1 <> p2` will
be pushed to each branch ; in fwd branch it will be folded and evaluated
as true, in bwd branch only the intended src <> dest stays.

If we think that the subquery scan node is definitely undesirable for
the types of effects it can have on plan, i find this a fine idea that
falls into the patch's goal (if i didn't miss other planner details), i
hope there's any more elegant way to do it.

There are other fixes for the original patch, i'll leave them after
discussing this part.

Regards,
Ayoub