Hello again,
On 2026-07-16 15:46, [email protected] 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 <[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
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
