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 <[email protected]> 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
