Re: [PATCH] Rewrite undirected edge patterns in GRAPH_TABLE using UNION ALL - Mailing list pgsql-hackers

On 2026-07-16 15:46, ayoub.kazar@data-bene.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.kazar@data-bene.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