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

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

Oops, forgot to put ref to repo:

[3] https://github.com/AyoubKaz07/lsqb-fork