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

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 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.

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.

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.

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

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 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.

--
Best Wishes,
Ashutosh Bapat