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

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