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
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)
Special cases
-------------
1. Same path factor (self-referencing pattern, e.g. (p)-[k]-(p)):
pf->src_pf == pf->dest_pf. In this case either orientation already
satisfies the join, so the UNION ALL is skipped entirely.
2. Self-loop deduplication:
With a UNION ALL, a self-loop edge (src = dst) would appear once in
the forward branch and once in the backward branch, giving two result
rows for a single physical edge. From the regress tests and 19beta1
behaviour, i understand that the SQL/PGQ standard
enforces that an edge orientation is unqiue, so a (src=1, dest=1)
appears once.
The backward branch therefore carries a NOT(src = dst) filter (built
by
build_edge_self_loop_filter()) to prevent duplication, note that src
and dest can be composite.
Permissions
-----------
Although i'm not much familiar with permissions, i followed the same
idea done in all of rewriteGraphTable, subqueries have their own
perminfos which will be individually evalued later on.
Also for both directions subqueries i set the same selectedCols for the
columns of the edge, which are all non-dropped columns of the edge
table.
I hope i didn't misunderstand how it should be in column permissions.
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.
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;
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
---------------
I'll be showing query plans for SF 0.1 Q6 as an example:
PostgreSQL-PGQ (v19beta1)
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=119023133.69..119023133.70 rows=1 width=8) (actual
time=87598.444..87598.445 rows=1.00 loops=1)
Buffers: shared hit=260492732
-> Nested Loop (cost=1.97..118978584.96 rows=17819493 width=0)
(actual time=2.890..86862.439 rows=55607896.00 loops=1)
Buffers: shared hit=260492732
-> Nested Loop (cost=1.68..118531927.95 rows=17819493
width=8) (actual time=2.866..80452.271 rows=55607896.00 loops=1)
Buffers: shared hit=260484267
-> Nested Loop (cost=1.38..118288857.60 rows=773376
width=8) (actual time=2.852..78406.879 rows=2393846.00 loops=1)
Buffers: shared hit=260481060
-> Nested Loop (cost=0.69..6217068.50
rows=61622719 width=24) (actual time=0.955..6768.780 rows=61622730.00
loops=1)
Join Filter: (person.id <> person_2.id)
Rows Removed by Join Filter: 36270
Buffers: shared hit=11596294
-> Nested Loop (cost=0.69..5292154.25
rows=36270 width=16) (actual time=0.945..3463.242 rows=36270.00 loops=1)
Buffers: shared hit=11596286
-> Nested Loop (cost=0.00..36179.25
rows=2890000 width=16) (actual time=0.031..140.342 rows=2890000.00
loops=1)
Buffers: shared hit=16
-> Seq Scan on person person_1
(cost=0.00..25.00 rows=1700 width=8) (actual time=0.017..0.332
rows=1700.00 loops=1)
Buffers: shared hit=8
-> Materialize
(cost=0.00..33.50 rows=1700 width=8) (actual time=0.000..0.026
rows=1700.00 loops=1700)
Storage: Memory Maximum
Storage: 70kB
Buffers: shared hit=8
-> Seq Scan on person
person_2 (cost=0.00..25.00 rows=1700 width=8) (actual time=0.007..0.099
rows=1700.00 loops=1)
Buffers: shared hit=8
-> Bitmap Heap Scan on
person_knows_person person_knows_person_1 (cost=0.69..1.81 rows=1
width=16) (actual time=0.001..0.001 rows=0.01 loops=2890000)
Recheck Cond: (((person_1.id =
person1id) AND (person_2.id = person2id)) OR ((person_2.id = person1id)
AND (person_1.id = person2id)))
Heap Blocks: exact=36270
Buffers: shared hit=11596270
-> BitmapOr (cost=0.69..0.69
rows=1 width=0) (actual time=0.001..0.001 rows=0.00 loops=2890000)
Buffers: shared
hit=11560000
-> Bitmap Index Scan on
person_knows_person_pkey (cost=0.00..0.34 rows=1 width=0) (actual
time=0.000..0.000 rows=0.01 loops=2890000)
Index Cond:
((person1id = person_1.id) AND (person2id = person_2.id))
Index Searches:
2890000
Buffers: shared
hit=5780000
-> Bitmap Index Scan on
person_knows_person_pkey (cost=0.00..0.34 rows=1 width=0) (actual
time=0.000..0.000 rows=0.01 loops=2890000)
Index Cond:
((person1id = person_2.id) AND (person2id = person_1.id))
Index Searches:
2890000
Buffers: shared
hit=5780000
-> Materialize (cost=0.00..33.50 rows=1700
width=8) (actual time=0.000..0.025 rows=1700.00 loops=36270)
Storage: Memory Maximum Storage: 70kB
Buffers: shared hit=8
-> Seq Scan on person
(cost=0.00..25.00 rows=1700 width=8) (actual time=0.006..0.197
rows=1700.00 loops=1)
Buffers: shared hit=8
-> Bitmap Heap Scan on person_knows_person
(cost=0.69..1.81 rows=1 width=16) (actual time=0.001..0.001 rows=0.04
loops=61622730)
Recheck Cond: (((person.id = person1id) AND
(person_1.id = person2id)) OR ((person_1.id = person1id) AND (person.id
= person2id)))
Heap Blocks: exact=2393846
Buffers: shared hit=248884766
-> BitmapOr (cost=0.69..0.69 rows=1
width=0) (actual time=0.001..0.001 rows=0.00 loops=61622730)
Buffers: shared hit=246490920
-> Bitmap Index Scan on
person_knows_person_pkey (cost=0.00..0.34 rows=1 width=0) (actual
time=0.000..0.000 rows=0.02 loops=61622730)
Index Cond: ((person1id =
person.id) AND (person2id = person_1.id))
Index Searches: 61622730
Buffers: shared hit=123245460
-> Bitmap Index Scan on
person_knows_person_pkey (cost=0.00..0.34 rows=1 width=0) (actual
time=0.000..0.000 rows=0.02 loops=61622730)
Index Cond: ((person1id =
person_1.id) AND (person2id = person.id))
Index Searches: 61622730
Buffers: shared hit=123245460
-> Memoize (cost=0.30..0.83 rows=24 width=16) (actual
time=0.000..0.000 rows=23.23 loops=2393846)
Cache Key: person_2.id
Cache Mode: logical
Estimates: capacity=1700 distinct keys=1700
lookups=773376 hit percent=99.78%
Hits: 2392308 Misses: 1538 Evictions: 0
Overflows: 0 Memory Usage: 1787kB
Buffers: shared hit=3207
-> Index Only Scan using
person_hasinterest_tag_pkey on person_hasinterest_tag (cost=0.29..0.82
rows=24 width=16) (actual time=0.002..0.003 rows=23.28 loops=1538)
Index Cond: (personid = person_2.id)
Heap Fetches: 0
Index Searches: 1538
Buffers: shared hit=3207
-> Memoize (cost=0.30..0.31 rows=1 width=8) (actual
time=0.000..0.000 rows=1.00 loops=55607896)
Cache Key: person_hasinterest_tag.tagid
Cache Mode: logical
Estimates: capacity=3904 distinct keys=3904
lookups=17819493 hit percent=99.98%
Hits: 55603664 Misses: 4232 Evictions: 0 Overflows: 0
Memory Usage: 463kB
Buffers: shared hit=8465
-> Index Only Scan using tag_pkey on tag
(cost=0.29..0.30 rows=1 width=8) (actual time=0.001..0.001 rows=1.00
loops=4232)
Index Cond: (id = person_hasinterest_tag.tagid)
Heap Fetches: 0
Index Searches: 4232
Buffers: shared hit=8465
Planning:
Buffers: shared hit=24
Planning Time: 2.211 ms
Time: 87608.729 ms (01:27.609)
---------------
The goal of the patch is to try and avoid this:
-> Bitmap Heap Scan on person_knows_person (cost=0.69..1.81 rows=1
width=16) (actual time=0.001..0.001 rows=0.04 loops=61622730)
Recheck Cond: (((person.id = person1id) AND (person_1.id =
person2id)) OR ((person_1.id = person1id) AND (person.id = person2id)))
Heap Blocks: exact=2393846
Buffers: shared hit=248884766
-> BitmapOr (cost=0.69..0.69 rows=1 width=0) (actual
time=0.001..0.001 rows=0.00 loops=61622730)
Buffers: shared hit=246490920
-> Bitmap Index Scan on person_knows_person_pkey
(cost=0.00..0.34 rows=1 width=0) (actual time=0.000..0.000 rows=0.02
loops=61622730)
Index Cond: ((person1id = person.id) AND (person2id
= person_1.id))
Index Searches: 61622730
Buffers: shared hit=123245460
-> Bitmap Index Scan on person_knows_person_pkey
(cost=0.00..0.34 rows=1 width=0) (actual time=0.000..0.000 rows=0.02
loops=61622730)
Index Cond: ((person1id = person_1.id) AND
(person2id = person.id))
Index Searches: 61622730
Buffers: shared hit=123245460
:
---------------
The UNION ALL patch gives this:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------
Finalize Aggregate (cost=86444.69..86444.70 rows=1 width=8) (actual
time=1594.615..1605.134 rows=1.00 loops=1)
Buffers: shared hit=13124
-> Gather (cost=86444.47..86444.68 rows=2 width=8) (actual
time=1582.094..1605.127 rows=2.00 loops=1)
Workers Planned: 1
Workers Launched: 1
Buffers: shared hit=13124
-> Partial Aggregate (cost=85444.47..85444.48 rows=1 width=8)
(actual time=1584.226..1585.179 rows=1.00 loops=2)
Buffers: shared hit=13124
-> Parallel Hash Join (cost=7796.34..59370.67
rows=10429521 width=0) (actual time=230.138..1101.048 rows=27803948.00
loops=2)
Hash Cond: (person_hasinterest_tag.personid =
person_2.id)
Buffers: shared hit=13124
-> Nested Loop (cost=0.58..2617.87 rows=23041
width=8) (actual time=0.161..11.623 rows=19585.00 loops=2)
Buffers: shared hit=12424
-> Parallel Index Only Scan using
person_hasinterest_tag_pkey on person_hasinterest_tag
(cost=0.29..840.11 rows=23041 width=16) (actual time=0.051..1.468
rows=19585.00 loops=2
)
Heap Fetches: 875
Index Searches: 1
Buffers: shared hit=187
-> Memoize (cost=0.30..0.32 rows=1 width=8)
(actual time=0.000..0.000 rows=1.00 loops=39170)
Cache Key: person_hasinterest_tag.tagid
Cache Mode: logical
Estimates: capacity=3926 distinct
keys=3926 lookups=23041 hit percent=82.96%
Hits: 15232 Misses: 3058 Evictions: 0
Overflows: 0 Memory Usage: 335kB
Buffers: shared hit=12237
Worker 0: Hits: 17823 Misses: 3057
Evictions: 0 Overflows: 0 Memory Usage: 335kB
-> Index Only Scan using tag_pkey on
tag (cost=0.29..0.31 rows=1 width=8) (actual time=0.001..0.001
rows=1.00 loops=6115)
Index Cond: (id =
person_hasinterest_tag.tagid)
Heap Fetches: 107
Index Searches: 6115
Buffers: shared hit=12237
-> Parallel Hash (cost=3787.95..3787.95
rows=320625 width=16) (actual time=226.165..227.116 rows=1196923.00
loops=2)
Buckets: 4194304 (originally 1048576)
Batches: 1 (originally 1) Memory Usage: 169696kB
Buffers: shared hit=700
-> Parallel Hash Join
(cost=1141.26..3787.95 rows=320625 width=16) (actual time=7.547..66.224
rows=1196923.00 loops=2)
Hash Cond:
(person_knows_person_2.person1id = person_1.id)
Join Filter: (person.id <> person_2.id)
Rows Removed by Join Filter: 18135
Buffers: shared hit=700
-> Hash Join (cost=48.25..816.65
rows=15075 width=16) (actual time=0.176..3.078 rows=18135.00 loops=2)
Hash Cond:
(person_knows_person_2.person2id = person.id)
Buffers: shared hit=340
-> Parallel Append
(cost=0.00..728.73 rows=15074 width=16) (actual time=0.012..1.213
rows=18135.00 loops=2)
Buffers: shared hit=320
-> Seq Scan on
person_knows_person person_knows_person_2 (cost=0.00..386.69 rows=18044
width=16) (actual time=0.020..0.995 rows=18135.00 loops=1)
Filter: (person1id <>
person2id)
Buffers: shared
hit=160
-> Parallel Seq Scan on
person_knows_person (cost=0.00..266.68 rows=10668 width=16) (actual
time=0.002..0.551 rows=18135.00 loops=1)
Buffers: shared
hit=160
-> Hash (cost=27.00..27.00
rows=1700 width=8) (actual time=0.152..0.153 rows=1700.00 loops=2)
Buckets: 2048 Batches: 1
Memory Usage: 83kB
Buffers: shared hit=20
-> Seq Scan on person
(cost=0.00..27.00 rows=1700 width=8) (actual time=0.011..0.053
rows=1700.00 loops=2)
Buffers: shared
hit=20
-> Parallel Hash (cost=904.58..904.58
rows=15075 width=32) (actual time=7.239..7.241 rows=18135.00 loops=2)
Buckets: 65536 Batches: 1
Memory Usage: 2816kB
Buffers: shared hit=360
-> Hash Join
(cost=96.50..904.58 rows=15075 width=32) (actual time=0.340..4.534
rows=18135.00 loops=2)
Hash Cond:
(person_knows_person_3.person1id = person_2.id)
Buffers: shared hit=360
-> Hash Join
(cost=48.25..816.65 rows=15075 width=24) (actual time=0.158..2.826
rows=18135.00 loops=2)
Hash Cond:
(person_knows_person_3.person2id = person_1.id)
Buffers: shared
hit=340
-> Parallel Append
(cost=0.00..728.73 rows=15074 width=16) (actual time=0.018..1.097
rows=18135.00 loops=2)
Buffers: shared
hit=320
-> Seq Scan on
person_knows_person person_knows_person_3 (cost=0.00..386.69 rows=18044
width=16) (actual time=0.032..1.032 rows=18135.00 loops=1)
Filter:
(person1id <> person2id)
Buffers:
shared hit=160
-> Parallel
Seq Scan on person_knows_person person_knows_person_1
(cost=0.00..266.68 rows=10668 width=16) (actual time=0.006..0.207
rows=9067.50
loops=2)
Buffers:
shared hit=160
-> Hash
(cost=27.00..27.00 rows=1700 width=8) (actual time=0.129..0.130
rows=1700.00 loops=2)
Buckets: 2048
Batches: 1 Memory Usage: 83kB
Buffers: shared
hit=20
-> Seq Scan on
person person_1 (cost=0.00..27.00 rows=1700 width=8) (actual
time=0.011..0.042 rows=1700.00 loops=2)
Buffers:
shared hit=20
-> Hash
(cost=27.00..27.00 rows=1700 width=8) (actual time=0.166..0.166
rows=1700.00 loops=2)
Buckets: 2048
Batches: 1 Memory Usage: 83kB
Buffers: shared
hit=20
-> Seq Scan on
person person_2 (cost=0.00..27.00 rows=1700 width=8) (actual
time=0.028..0.077 rows=1700.00 loops=2)
Buffers: shared
hit=20
Planning:
Buffers: shared hit=32
Planning Time: 9.442 ms
Execution Time: 1605.346 ms
(82 rows)
Time: 1615.777 ms (00:01.616)
---------------
Here's also another plan from patched version on SF 1:
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Finalize Aggregate (cost=1540136.99..1540137.00 rows=1 width=8)
(actual time=39407.590..39411.145 rows=1.00 loops=1)
Buffers: shared hit=7089
-> Gather (cost=1540136.77..1540136.98 rows=2 width=8) (actual
time=39376.380..39411.138 rows=3.00 loops=1)
Workers Planned: 2
Workers Launched: 2
Buffers: shared hit=7089
-> Partial Aggregate (cost=1539136.77..1539136.78 rows=1
width=8) (actual time=39374.325..39374.331 rows=1.00 loops=3)
Buffers: shared hit=7089
-> Parallel Hash Join (cost=16706.64..1090714.77
rows=179368801 width=0) (actual time=89.914..29316.892 rows=556044773.33
loops=3)
Hash Cond: (person_knows_person_2.person2id =
person_1.id)
Join Filter: (person.id <> person_2.id)
Rows Removed by Join Filter: 3493080
Buffers: shared hit=7089
-> Parallel Hash Join (cost=6342.79..42247.34
rows=4370837 width=16) (actual time=29.291..285.672 rows=3493080.00
loops=3)
Hash Cond: (person_knows_person_2.person1id =
person_2.id)
Buffers: shared hit=4299
-> Parallel Append (cost=0.00..6431.58
rows=188106 width=16) (actual time=0.009..15.821 rows=150862.00 loops=3)
Buffers: shared hit=2496
-> Parallel Seq Scan on
person_knows_person person_knows_person_2 (cost=0.00..2911.92
rows=132448 width=16) (actual time=0.006..8.338 rows=75431.00 loops=3)
Filter: (person1id <> person2id)
Buffers: shared hit=1248
-> Parallel Seq Scan on
person_knows_person person_knows_person_1 (cost=0.00..2579.14
rows=133114 width=16) (actual time=0.008..3.772 rows=113146.50 loops=2)
Buffers: shared hit=1248
-> Parallel Hash (cost=4463.40..4463.40
rows=150351 width=16) (actual time=29.011..29.013 rows=85198.67 loops=3)
Buckets: 262144 Batches: 1 Memory
Usage: 14080kB
Buffers: shared hit=1803
-> Hash Join (cost=730.30..4463.40
rows=150351 width=16) (actual time=1.985..16.399 rows=85198.67 loops=3)
Hash Cond:
(person_hasinterest_tag.tagid = tag.id)
Buffers: shared hit=1803
-> Hash Join
(cost=296.50..3634.83 rows=150351 width=24) (actual time=0.740..8.790
rows=85198.67 loops=3)
Hash Cond:
(person_hasinterest_tag.personid = person_2.id)
Buffers: shared hit=1587
-> Parallel Seq Scan on
person_hasinterest_tag (cost=0.00..2943.51 rows=150351 width=16)
(actual time=0.009..1.821 rows=85198.67 loops=3)
Buffers: shared
hit=1440
-> Hash
(cost=159.00..159.00 rows=11000 width=8) (actual time=0.681..0.681
rows=11000.00 loops=3)
Buckets: 16384
Batches: 1 Memory Usage: 558kB
Buffers: shared
hit=147
-> Seq Scan on
person person_2 (cost=0.00..159.00 rows=11000 width=8) (actual
time=0.011..0.215 rows=11000.00 loops=3)
Buffers: shared
hit=147
-> Hash (cost=232.80..232.80
rows=16080 width=8) (actual time=1.114..1.114 rows=16080.00 loops=3)
Buckets: 16384 Batches: 1
Memory Usage: 757kB
Buffers: shared hit=216
-> Seq Scan on tag
(cost=0.00..232.80 rows=16080 width=8) (actual time=0.049..0.379
rows=16080.00 loops=3)
Buffers: shared
hit=216
-> Parallel Hash (cost=8012.52..8012.52
rows=188106 width=24) (actual time=59.638..59.640 rows=150862.00
loops=3)
Buckets: 524288 Batches: 1 Memory Usage:
28928kB
Buffers: shared hit=2790
-> Hash Join (cost=593.00..8012.52
rows=188106 width=24) (actual time=1.961..34.498 rows=150862.00 loops=3)
Hash Cond:
(person_knows_person_3.person1id = person_1.id)
Buffers: shared hit=2790
-> Hash Join (cost=296.50..7222.05
rows=188106 width=16) (actual time=0.745..21.304 rows=150862.00 loops=3)
Hash Cond:
(person_knows_person_3.person2id = person.id)
Buffers: shared hit=2643
-> Parallel Append
(cost=0.00..6431.58 rows=188106 width=16) (actual time=0.012..8.223
rows=150862.00 loops=3)
Buffers: shared hit=2496
-> Parallel Seq Scan on
person_knows_person person_knows_person_3 (cost=0.00..2911.92
rows=132448 width=16) (actual time=0.009..3.161 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.009..2.629 rows=113146.50 loops=2)
Buffers: shared
hit=1248
-> Hash (cost=159.00..159.00
rows=11000 width=8) (actual time=0.684..0.684 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.009..0.205
rows=11000.00 loops=3)
Buffers: shared
hit=147
-> Hash (cost=159.00..159.00
rows=11000 width=8) (actual time=1.138..1.138 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.039..0.451
rows=11000.00 loops=3)
Buffers: shared hit=147
Planning:
Buffers: shared hit=28
Planning Time: 6.743 ms
Execution Time: 39411.297 ms
(74 rows)
Time: 39422.030 ms (00:39.422)
---------------
Q9 SF 1 (where v19beta1, timesout after 30 min):
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Finalize Aggregate (cost=1958681.23..1958681.24 rows=1 width=8)
(actual time=95340.881..95900.581 rows=1.00 loops=1)
Buffers: shared hit=9366
-> Gather (cost=1958681.01..1958681.22 rows=2 width=8) (actual
time=95210.881..95900.488 rows=2.00 loops=1)
Workers Planned: 1
Workers Launched: 1
Buffers: shared hit=9366
-> Partial Aggregate (cost=1957681.01..1957681.02 rows=1
width=8) (actual time=95203.491..95204.497 rows=1.00 loops=2)
Buffers: shared hit=9366
-> Parallel Hash Join (cost=588976.14..1482881.25
rows=189919907 width=0) (actual time=35680.505..77352.339
rows=798076709.00 loops=2)
Hash Cond: (person_hasinterest_tag.personid =
person_2.id)
Buffers: shared hit=9366
-> Hash Join (cost=433.80..3772.08 rows=150351
width=8) (actual time=6.910..119.288 rows=127798.00 loops=2)
Hash Cond: (person_hasinterest_tag.tagid =
tag.id)
Buffers: shared hit=1584
-> Parallel Seq Scan on
person_hasinterest_tag (cost=0.00..2943.51 rows=150351 width=16)
(actual time=0.502..50.401 rows=127798.00 loops=2)
Buffers: shared hit=1440
-> Hash (cost=232.80..232.80 rows=16080
width=8) (actual time=5.210..5.211 rows=16080.00 loops=2)
Buckets: 16384 Batches: 1 Memory
Usage: 757kB
Buffers: shared hit=144
-> Seq Scan on tag (cost=0.00..232.80
rows=16080 width=8) (actual time=1.179..4.232 rows=16080.00 loops=2)
Buffers: shared hit=144
-> Parallel Hash (cost=516172.63..516172.63
rows=5789577 width=16) (actual time=35596.218..35597.107
rows=34241366.00 loops=2)
Buckets: 67108864 (originally 16777216)
Batches: 1 (originally 1) Memory Usage: 4130784kB
Buffers: shared hit=7782
-> Parallel Hash Right Anti Join
(cost=178053.88..516172.63 rows=5789577 width=16) (actual
time=12849.164..14538.771 rows=34241366.00 loops=2)
Hash Cond:
((person_knows_person_2.person1id = person.id) AND
(person_knows_person_2.person2id = person_2.id))
Buffers: shared hit=7782
-> Parallel Append
(cost=0.00..6101.16 rows=188578 width=16) (actual time=0.357..12.373
rows=226293.00 loops=2)
Buffers: shared hit=2496
-> Parallel Seq Scan on
person_knows_person person_knows_person_2 (cost=0.00..2579.14
rows=133114 width=16) (actual time=0.283..7.070 rows=226293.00 loops=1)
Buffers: shared hit=1248
-> Parallel Seq Scan on
person_knows_person person_knows_person_3 (cost=0.00..2579.14
rows=133114 width=16) (actual time=0.277..4.205 rows=113146.50 loops=2)
Buffers: shared hit=1248
-> Parallel Hash
(cost=62262.35..62262.35 rows=7719435 width=24) (actual
time=12193.778..12194.638 rows=35795105.00 loops=2)
Buckets: 67108864 (originally
33554432) Batches: 1 (originally 1) Memory Usage: 4709216kB
Buffers: shared hit=5286
-> Parallel Hash Join
(cost=10660.34..62262.35 rows=7719435 width=24) (actual
time=71.602..2761.515 rows=35795105.00 loops=2)
Hash Cond:
(person_knows_person_4.person1id = person_1.id)
Join Filter: (person.id <>
person_2.id)
Rows Removed by Join
Filter: 226293
Buffers: shared hit=5286
-> Hash Join
(cost=296.50..7222.05 rows=188106 width=16) (actual time=0.648..77.824
rows=226293.00 loops=2)
Hash Cond:
(person_knows_person_4.person2id = person.id)
Buffers: shared
hit=2594
-> Parallel Append
(cost=0.00..6431.58 rows=188106 width=16) (actual time=0.003..30.267
rows=226293.00 loops=2)
Buffers: shared
hit=2496
-> Parallel
Seq Scan on person_knows_person person_knows_person_4
(cost=0.00..2911.92 rows=132448 width=16) (actual time=0.003..34.763
rows=226293.00 loops=1)
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.150..3.771 rows=113146.50 loops=2)
Buffers:
shared hit=1248
-> Hash
(cost=159.00..159.00 rows=11000 width=8) (actual time=0.594..0.594
rows=11000.00 loops=2)
Buckets: 16384
Batches: 1 Memory Usage: 558kB
Buffers: shared
hit=98
-> Seq Scan on
person (cost=0.00..159.00 rows=11000 width=8) (actual time=0.012..0.179
rows=11000.00 loops=2)
Buffers:
shared hit=98
-> Parallel Hash
(cost=8012.52..8012.52 rows=188106 width=32) (actual time=70.230..70.706
rows=226293.00 loops=2)
Buckets: 524288
Batches: 1 Memory Usage: 32480kB
Buffers: shared
hit=2692
-> Hash Join
(cost=593.00..8012.52 rows=188106 width=32) (actual time=1.442..41.974
rows=226293.00 loops=2)
Hash Cond:
(person_knows_person_5.person1id = person_2.id)
Buffers: shared
hit=2692
-> Hash Join
(cost=296.50..7222.05 rows=188106 width=24) (actual time=0.662..25.976
rows=226293.00 loops=2)
Hash
Cond: (person_knows_person_5.person2id = person_1.id)
Buffers:
shared hit=2594
->
Parallel Append (cost=0.00..6431.58 rows=188106 width=16) (actual
time=0.009..9.680 rows=226293.00 loops=2)
Buffers: shared hit=2496
->
Parallel Seq Scan on person_knows_person person_knows_person_5
(cost=0.00..2911.92 rows=132448 width=16) (actual time=0.009..3.833
rows=113146.50 loops=2)
Filter: (person1id <> person2id)
Buffers: shared hit=1248
->
Parallel Seq Scan on person_knows_person person_knows_person_1
(cost=0.00..2579.14 rows=133114 width=16) (actual time=0.003..4.001
rows=226293.00 loops=1)
Buffers: shared hit=1248
-> Hash
(cost=159.00..159.00 rows=11000 width=8) (actual time=0.611..0.612
rows=11000.00 loops=2)
Buckets: 16384 Batches: 1 Memory Usage: 558kB
Buffers: shared hit=98
->
Seq Scan on person person_1 (cost=0.00..159.00 rows=11000 width=8)
(actual time=0.007..0.205 rows=11000.00 loops=2)
Buffers: shared hit=98
-> Hash
(cost=159.00..159.00 rows=11000 width=8) (actual time=0.732..0.758
rows=11000.00 loops=2)
Buckets:
16384 Batches: 1 Memory Usage: 558kB
Buffers:
shared hit=98
-> Seq
Scan on person person_2 (cost=0.00..159.00 rows=11000 width=8) (actual
time=0.032..0.277 rows=11000.00 loops=2)
Buffers: shared hit=98
Planning:
Buffers: shared hit=28
Planning Time: 9.533 ms
Execution Time: 95907.385 ms
(86 rows)
Time: 95969.259 ms (01:35.969)
---------------
And given just an EXPLAIN on same query in 19beta1 shows how hard it
becomes in terms of cost:
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=9075272598.85..9075272598.86 rows=1 width=8)
-> Hash Join (cost=442061350.76..9074461389.95 rows=324483560
width=0)
Hash Cond: (person_2.id = person_hasinterest_tag.personid)
-> Nested Loop (cost=442053054.93..9068345496.87
rows=13964691 width=8)
-> Hash Right Anti Join
(cost=442053053.89..983461976.92 rows=3733495045 width=24)
Hash Cond: ((person_knows_person_2.person1id =
person.id) AND (person_knows_person_2.person2id = person_2.id))
-> Append (cost=0.00..9284.79 rows=452586
width=16)
-> Seq Scan on person_knows_person
person_knows_person_2 (cost=0.00..3510.93 rows=226293 width=16)
-> Seq Scan on person_knows_person
person_knows_person_3 (cost=0.00..3510.93 rows=226293 width=16)
-> Hash (cost=338215222.00..338215222.00
rows=4977993393 width=24)
-> Nested Loop (cost=1.04..338215222.00
rows=4977993393 width=24)
Join Filter: (person.id <> person_2.id)
-> Nested Loop
(cost=1.04..263538345.50 rows=452586 width=16)
-> Nested Loop
(cost=0.00..1512845.50 rows=121000000 width=16)
-> Seq Scan on person
person_1 (cost=0.00..159.00 rows=11000 width=8)
-> Materialize
(cost=0.00..214.00 rows=11000 width=8)
-> Seq Scan on
person person_2 (cost=0.00..159.00 rows=11000 width=8)
-> Bitmap Heap Scan on
person_knows_person person_knows_person_1 (cost=1.04..2.16 rows=1
width=16)
Recheck Cond:
(((person_1.id = person1id) AND (person_2.id = person2id)) OR
((person_2.id = person1id) AND (person_1.id = person2id)))
-> BitmapOr
(cost=1.04..1.04 rows=1 width=0)
-> Bitmap Index Scan
on person_knows_person_pkey (cost=0.00..0.52 rows=1 width=0)
Index Cond:
((person1id = person_1.id) AND (person2id = person_2.id))
-> Bitmap Index Scan
on person_knows_person_pkey (cost=0.00..0.52 rows=1 width=0)
Index Cond:
((person1id = person_2.id) AND (person2id = person_1.id))
-> Materialize (cost=0.00..214.00
rows=11000 width=8)
-> Seq Scan on person
(cost=0.00..159.00 rows=11000 width=8)
-> Bitmap Heap Scan on person_knows_person
(cost=1.04..2.16 rows=1 width=16)
Recheck Cond: (((person.id = person1id) AND
(person_1.id = person2id)) OR ((person_1.id = person1id) AND (person.id
= person2id)))
-> BitmapOr (cost=1.04..1.04 rows=1 width=0)
-> Bitmap Index Scan on
person_knows_person_pkey (cost=0.00..0.52 rows=1 width=0)
Index Cond: ((person1id = person.id)
AND (person2id = person_1.id))
-> Bitmap Index Scan on
person_knows_person_pkey (cost=0.00..0.52 rows=1 width=0)
Index Cond: ((person1id = person_1.id)
AND (person2id = person.id))
-> Hash (cost=5100.88..5100.88 rows=255596 width=8)
-> Hash Join (cost=433.80..5100.88 rows=255596 width=8)
Hash Cond: (person_hasinterest_tag.tagid = tag.id)
-> Seq Scan on person_hasinterest_tag
(cost=0.00..3995.96 rows=255596 width=16)
-> Hash (cost=232.80..232.80 rows=16080 width=8)
-> Seq Scan on tag (cost=0.00..232.80
rows=16080 width=8)
(39 rows)
---------------
I find this a valuable improvement for its cost of implementation, so
should be worth it.
What do you think?
Refs:
[1] https://github.com/ldbc/lsqb
[2] https://ir.cwi.nl/pub/31398/31398.pdf
Regards,
Ayoub KAZAR
From a9fd702d108b34cd0885886b88f0397c2bd7df25 Mon Sep 17 00:00:00 2001
From: AyoubKAZ <[email protected]>
Date: Wed, 15 Jul 2026 02:22:56 +0200
Subject: [PATCH] Rewrite undirected edge patterns in GRAPH_TABLE using UNION
ALL
Previously, undirected edge patterns (-[e]-) were rewritten by combining
the join conditions for both traversal directions into a single OR qual
(src=v1 AND dst=v2 OR src=v2 AND dst=v1). This usually implied using an unefficient BitmapOR scan or the full evaluation of the disjunction, which
becomes particularly costly when intermediate result sets are large, as is
typical in graph queries with undirected edges.
Instead, replace the edge relation with a UNION ALL subquery consisting of
two scans of the edge table: a forward scan that projects columns as-is,
and a backward scan that swaps the source and destination key columns.
This allows the outer query to use a single equi-join to match edges
traversed in either direction.
When the source and destination vertex patterns share the same path factor
(e.g., (p)-[k]-(p)), the forward orientation already satisfies both
directions through a single equi-join, so the UNION ALL is skipped
entirely.
When the UNION ALL is used, a self-loop edge (srckey = destkey) would
appear in both branches and be returned twice, violating the SQL/PGQ
standard. A NOT(srckey = destkey) filter applied to the backward branch,
built by build_edge_self_loop_filter(), prevents this duplication.
---
src/backend/rewrite/rewriteGraphTable.c | 336 ++++++++++++++++++++++--
1 file changed, 310 insertions(+), 26 deletions(-)
diff --git a/src/backend/rewrite/rewriteGraphTable.c b/src/backend/rewrite/rewriteGraphTable.c
index cdb1f4c0dca..28173947927 100644
--- a/src/backend/rewrite/rewriteGraphTable.c
+++ b/src/backend/rewrite/rewriteGraphTable.c
@@ -44,6 +44,7 @@
#include "utils/lsyscache.h"
#include "utils/ruleutils.h"
#include "utils/syscache.h"
+#include "utils/rel.h"
/*
@@ -101,6 +102,8 @@ static Query *generate_union_from_pathqueries(List **pathqueries);
static List *get_path_elements_for_path_factor(Oid propgraphid, struct path_factor *pf);
static bool is_property_associated_with_label(Oid labeloid, Oid propoid);
static Node *get_element_property_expr(Oid elemoid, Oid propoid, int rtindex);
+static Query *generate_undirected_edge_union_query(struct path_element *pe);
+static Node *build_edge_self_loop_filter(TupleDesc tupdesc, int nkeys, int16 *src_key_attnums, int16 *dest_key_attnums, Oid *eq_ops);
/*
* Convert GRAPH_TABLE clause into a subquery using relational
@@ -159,6 +162,16 @@ rewriteGraphTable(Query *parsetree, int rt_index)
* table on their respective keys. Hence the query representing one path
* consists of JOINs between edge and vertex tables.
*
+ * For undirected edge patterns (-[e]-), when the edge's source and destination vertex patterns are different path
+ * factors, but same path element, the edge relation is replaced
+ * by a UNION ALL subquery that duplicates and reverses the key columns, so that
+ * a single equi-join can match edges traversed in either direction. If the
+ * source and destination vertex patterns share the same path factor (e.g.
+ * (p)-[k]-(p)), either of the two orientations is satisfied by a single equi-join, so the
+ * UNION ALL is skipped. When the UNION ALL is used, the backward branch
+ * carries a NOT(srckey = destkey) filter so that self-loop edges are not
+ * returned twice.
+ *
* generate_queries_for_path_pattern() starts the recursion but actual work is
* done by generate_queries_for_path_pattern_recurse().
* generate_query_for_graph_path() constructs a query for a given path.
@@ -431,6 +444,7 @@ generate_query_for_graph_path(RangeTblEntry *rte, List *graph_path)
RangeTblRef *rtr;
Relation rel;
ParseNamespaceItem *pni;
+ bool use_union_all = false;
Assert(pf->kind == VERTEX_PATTERN || IS_EDGE_PATTERN(pf->kind));
@@ -458,30 +472,32 @@ generate_query_for_graph_path(RangeTblEntry *rte, List *graph_path)
/*
* An edge pattern in any direction matches edges in both
- * directions, try swapping source and destination. When the
- * source and destination is the same vertex table, quals
- * corresponding to either direction may get satisfied. Hence OR
- * the quals corresponding to both the directions.
+ * directions. When the source and destination is the same vertex
+ * table, we will replace the edge relation with a UNION ALL
+ * subquery that duplicates and reverses the edge table keys.
*/
if (pf->kind == EDGE_PATTERN_ANY &&
dest_pe->elemoid == pe->srcvertexid &&
src_pe->elemoid == pe->destvertexid)
{
- List *src_quals = copyObject(pe->dest_quals);
- List *dest_quals = copyObject(pe->src_quals);
- Expr *rev_edge_qual;
-
- /* Swap the source and destination varnos in the quals. */
- ChangeVarNodes((Node *) dest_quals, pe->path_factor->src_pf->factorpos + 1,
- pe->path_factor->dest_pf->factorpos + 1, 0);
- ChangeVarNodes((Node *) src_quals, pe->path_factor->dest_pf->factorpos + 1,
- pe->path_factor->src_pf->factorpos + 1, 0);
-
- rev_edge_qual = makeBoolExpr(AND_EXPR, list_concat(src_quals, dest_quals), -1);
if (edge_qual)
- edge_qual = makeBoolExpr(OR_EXPR, list_make2(edge_qual, rev_edge_qual), -1);
+ {
+ if (pf->src_pf != pf->dest_pf)
+ use_union_all = true;
+ }
else
- edge_qual = rev_edge_qual;
+ {
+ List *src_quals = copyObject(pe->dest_quals);
+ List *dest_quals = copyObject(pe->src_quals);
+
+ /* Swap the source and destination varnos in the quals. */
+ ChangeVarNodes((Node *) dest_quals, pe->path_factor->src_pf->factorpos + 1,
+ pe->path_factor->dest_pf->factorpos + 1, 0);
+ ChangeVarNodes((Node *) src_quals, pe->path_factor->dest_pf->factorpos + 1,
+ pe->path_factor->src_pf->factorpos + 1, 0);
+
+ edge_qual = makeBoolExpr(AND_EXPR, list_concat(src_quals, dest_quals), -1);
+ }
}
/*
@@ -507,13 +523,31 @@ generate_query_for_graph_path(RangeTblEntry *rte, List *graph_path)
* unprivileged data access through a property graph. This is inline
* with the views being security_invoker by default.
*/
- rel = table_open(pe->reloid, AccessShareLock);
- pni = addRangeTableEntryForRelation(make_parsestate(NULL), rel, AccessShareLock,
- NULL, true, false);
- table_close(rel, NoLock);
- path_query->rtable = lappend(path_query->rtable, pni->p_rte);
- path_query->rteperminfos = lappend(path_query->rteperminfos, pni->p_perminfo);
- pni->p_rte->perminfoindex = list_length(path_query->rteperminfos);
+ if (IS_EDGE_PATTERN(pf->kind) && use_union_all)
+ {
+ Query *union_query = generate_undirected_edge_union_query(pe);
+
+ pni = addRangeTableEntryForSubquery(make_parsestate(NULL), union_query, makeAlias("edge_union", NIL), true, false);
+ path_query->rtable = lappend(path_query->rtable, pni->p_rte);
+
+ /*
+ * RTE_SUBQUERY does not have rteperminfo, but relations within
+ * the subquery already have their perminfos evaluated by
+ * executor.
+ */
+
+ pni->p_rte->perminfoindex = 0;
+ }
+ else
+ {
+ rel = table_open(pe->reloid, AccessShareLock);
+ pni = addRangeTableEntryForRelation(make_parsestate(NULL), rel, AccessShareLock,
+ NULL, true, false);
+ table_close(rel, NoLock);
+ path_query->rtable = lappend(path_query->rtable, pni->p_rte);
+ path_query->rteperminfos = lappend(path_query->rteperminfos, pni->p_perminfo);
+ pni->p_rte->perminfoindex = list_length(path_query->rteperminfos);
+ }
rtr = makeNode(RangeTblRef);
rtr->rtindex = list_length(path_query->rtable);
fromlist = lappend(fromlist, rtr);
@@ -562,8 +596,17 @@ generate_query_for_graph_path(RangeTblEntry *rte, List *graph_path)
vars = pull_vars_of_level((Node *) list_make2(qual_exprs, path_query->targetList), 0);
foreach_node(Var, var, vars)
{
- RTEPermissionInfo *perminfo = getRTEPermissionInfo(path_query->rteperminfos,
- rt_fetch(var->varno, path_query->rtable));
+ RangeTblEntry *var_rte = rt_fetch(var->varno, path_query->rtable);
+ RTEPermissionInfo *perminfo;
+
+ /*
+ * Subqueries handle their own permissions, in this case anything
+ * below the UNION ALL subquery.
+ */
+ if (var_rte->rtekind == RTE_SUBQUERY)
+ continue;
+
+ perminfo = getRTEPermissionInfo(path_query->rteperminfos, var_rte);
/* Must offset the attnum to fit in a bitmapset */
perminfo->selectedCols = bms_add_member(perminfo->selectedCols,
@@ -573,6 +616,247 @@ generate_query_for_graph_path(RangeTblEntry *rte, List *graph_path)
return path_query;
}
+/*
+ * Construct a UNION ALL subquery over the edge relation that presents each
+ * edge row in both its forward orientation (srckey, destkey) and its backward
+ * orientation (destkey, srckey). This is used for undirected edge patterns
+ * (-[e]-) when the source and destination vertex patterns are different path
+ * factors. A NOT(srckey = destkey) filter on the backward branch prevents
+ * self-loop edges from being returned twice.
+ */
+static Query *
+generate_undirected_edge_union_query(struct path_element *pe)
+{
+ Query *subquery = makeNode(Query);
+ Query *fwd_query = makeNode(Query);
+ Query *bwd_query = makeNode(Query);
+ Relation rel;
+ HeapTuple eletup;
+ Datum datum;
+ Datum *d1,
+ *d2;
+ int n1,
+ n2;
+ int16 *src_key_attnums;
+ int16 *dest_key_attnums;
+ Oid *eq_ops;
+ ParseNamespaceItem *fwd_pni;
+ ParseNamespaceItem *bwd_pni;
+ SetOperationStmt *sostmt;
+ TupleDesc tupdesc;
+ RangeTblRef *fwd_rtr;
+ RangeTblRef *bwd_rtr;
+
+ subquery->commandType = CMD_SELECT;
+ fwd_query->commandType = CMD_SELECT;
+ bwd_query->commandType = CMD_SELECT;
+
+ rel = table_open(pe->reloid, AccessShareLock);
+
+ eletup = SearchSysCache1(PROPGRAPHELOID, ObjectIdGetDatum(pe->elemoid));
+ if (!eletup)
+ elog(ERROR, "cache lookup failed for property graph element %u", pe->elemoid);
+
+ datum = SysCacheGetAttrNotNull(PROPGRAPHELOID, eletup, Anum_pg_propgraph_element_pgesrckey);
+ deconstruct_array_builtin(DatumGetArrayTypeP(datum), INT2OID, &d1, NULL, &n1);
+ datum = SysCacheGetAttrNotNull(PROPGRAPHELOID, eletup, Anum_pg_propgraph_element_pgedestkey);
+ deconstruct_array_builtin(DatumGetArrayTypeP(datum), INT2OID, &d2, NULL, &n2);
+
+ {
+ Datum *d3;
+ int n3;
+
+ datum = SysCacheGetAttrNotNull(PROPGRAPHELOID, eletup, Anum_pg_propgraph_element_pgesrceqop);
+ deconstruct_array_builtin(DatumGetArrayTypeP(datum), OIDOID, &d3, NULL, &n3);
+ Assert(n1 == n3);
+ eq_ops = palloc(n1 * sizeof(Oid));
+ for (int i = 0; i < n1; i++)
+ eq_ops[i] = DatumGetObjectId(d3[i]);
+ }
+
+ Assert(n1 == n2);
+ src_key_attnums = palloc(n1 * sizeof(int16));
+ dest_key_attnums = palloc(n1 * sizeof(int16));
+ for (int i = 0; i < n1; i++)
+ {
+ src_key_attnums[i] = DatumGetInt16(d1[i]);
+ dest_key_attnums[i] = DatumGetInt16(d2[i]);
+ }
+
+ ReleaseSysCache(eletup);
+
+ fwd_pni = addRangeTableEntryForRelation(make_parsestate(NULL), rel, AccessShareLock, NULL, true, false);
+ fwd_query->rtable = list_make1(fwd_pni->p_rte);
+ fwd_query->rteperminfos = list_make1(fwd_pni->p_perminfo);
+ fwd_pni->p_rte->perminfoindex = 1;
+ {
+ RangeTblRef *rtr = makeNode(RangeTblRef);
+
+ rtr->rtindex = 1;
+ fwd_query->jointree = makeFromExpr(list_make1(rtr), NULL);
+ }
+
+ bwd_pni = addRangeTableEntryForRelation(make_parsestate(NULL), rel, AccessShareLock, NULL, true, false);
+ bwd_query->rtable = list_make1(bwd_pni->p_rte);
+ bwd_query->rteperminfos = list_make1(bwd_pni->p_perminfo);
+ bwd_pni->p_rte->perminfoindex = 1;
+ {
+ RangeTblRef *rtr = makeNode(RangeTblRef);
+
+ rtr->rtindex = 1;
+ bwd_query->jointree = makeFromExpr(list_make1(rtr), NULL);
+ }
+
+ sostmt = makeNode(SetOperationStmt);
+ sostmt->op = SETOP_UNION;
+ sostmt->all = true;
+
+ tupdesc = RelationGetDescr(rel);
+
+ bwd_query->jointree->quals = build_edge_self_loop_filter(tupdesc, n1, src_key_attnums, dest_key_attnums, eq_ops);
+
+ for (int i = 0; i < tupdesc->natts; i++)
+ {
+ Form_pg_attribute att = TupleDescAttr(tupdesc, i);
+ TargetEntry *tle1,
+ *tle2,
+ *out_tle;
+ Var *fwd_var,
+ *bwd_var,
+ *out_var;
+ int bwd_attnum;
+ Form_pg_attribute bwd_att;
+
+ if (att->attisdropped)
+ {
+ Node *null_expr = (Node *) makeNullConst(att->atttypid, att->atttypmod, att->attcollation);
+
+ tle1 = makeTargetEntry((Expr *) null_expr, i + 1, pstrdup(""), false);
+ fwd_query->targetList = lappend(fwd_query->targetList, tle1);
+
+ tle2 = makeTargetEntry((Expr *) copyObject(null_expr), i + 1, pstrdup(""), false);
+ bwd_query->targetList = lappend(bwd_query->targetList, tle2);
+ }
+ else
+ {
+ RTEPermissionInfo *fwd_perminfo = getRTEPermissionInfo(fwd_query->rteperminfos, fwd_pni->p_rte);
+ RTEPermissionInfo *bwd_perminfo = getRTEPermissionInfo(bwd_query->rteperminfos, bwd_pni->p_rte);
+
+ /*
+ * Mark each column as selected in both perminfos. The backward
+ * query reads bwd_attnum rather than att->attnum, since key
+ * columns are swapped; non-key columns are identical in both.
+ */
+ fwd_var = makeVar(1, att->attnum, att->atttypid, att->atttypmod, att->attcollation, 0);
+ tle1 = makeTargetEntry((Expr *) fwd_var, i + 1, pstrdup(NameStr(att->attname)), false);
+ fwd_query->targetList = lappend(fwd_query->targetList, tle1);
+ fwd_perminfo->selectedCols = bms_add_member(fwd_perminfo->selectedCols,
+ att->attnum - FirstLowInvalidHeapAttributeNumber);
+
+ bwd_attnum = att->attnum;
+ for (int k = 0; k < n1; k++)
+ {
+ if (src_key_attnums[k] == att->attnum)
+ bwd_attnum = dest_key_attnums[k];
+ else if (dest_key_attnums[k] == att->attnum)
+ bwd_attnum = src_key_attnums[k];
+ }
+ bwd_att = TupleDescAttr(tupdesc, bwd_attnum - 1);
+ bwd_var = makeVar(1, bwd_attnum, bwd_att->atttypid, bwd_att->atttypmod, bwd_att->attcollation, 0);
+ tle2 = makeTargetEntry((Expr *) bwd_var, i + 1, pstrdup(NameStr(att->attname)), false);
+ bwd_query->targetList = lappend(bwd_query->targetList, tle2);
+ bwd_perminfo->selectedCols = bms_add_member(bwd_perminfo->selectedCols,
+ bwd_attnum - FirstLowInvalidHeapAttributeNumber);
+ }
+
+ sostmt->colTypes = lappend_oid(sostmt->colTypes, att->atttypid);
+ sostmt->colTypmods = lappend_int(sostmt->colTypmods, att->atttypmod);
+ sostmt->colCollations = lappend_oid(sostmt->colCollations, att->attcollation);
+
+ out_var = makeVar(1, i + 1, att->atttypid, att->atttypmod, att->attcollation, 0);
+ out_tle = makeTargetEntry((Expr *) out_var, i + 1, pstrdup(NameStr(att->attname)), false);
+ subquery->targetList = lappend(subquery->targetList, out_tle);
+ }
+
+ table_close(rel, NoLock);
+
+ fwd_rtr = makeNode(RangeTblRef);
+ fwd_rtr->rtindex = 1;
+ bwd_rtr = makeNode(RangeTblRef);
+ bwd_rtr->rtindex = 2;
+ sostmt->larg = (Node *) fwd_rtr;
+ sostmt->rarg = (Node *) bwd_rtr;
+
+ fwd_pni = addRangeTableEntryForSubquery(make_parsestate(NULL), fwd_query, NULL, false, false);
+ bwd_pni = addRangeTableEntryForSubquery(make_parsestate(NULL), bwd_query, NULL, false, false);
+
+ subquery->rtable = list_make2(fwd_pni->p_rte, bwd_pni->p_rte);
+ subquery->setOperations = (Node *) sostmt;
+ subquery->jointree = makeFromExpr(NIL, NULL);
+
+ return subquery;
+}
+
+/*
+ * Generate a qualification expression to filter out self-loop edges.
+ */
+static Node *
+build_edge_self_loop_filter(TupleDesc tupdesc, int nkeys,
+ int16 *src_key_attnums, int16 *dest_key_attnums,
+ Oid *eq_ops)
+{
+ List *quals = NIL;
+ Expr *eq_all;
+ Node *qual;
+ ParseState *pstate = make_parsestate(NULL);
+
+ for (int i = 0; i < nkeys; i++)
+ {
+ Form_pg_attribute src_att = TupleDescAttr(tupdesc, src_key_attnums[i] - 1);
+ Form_pg_attribute dest_att = TupleDescAttr(tupdesc, dest_key_attnums[i] - 1);
+ Var *src_var = makeVar(1, src_key_attnums[i], src_att->atttypid, src_att->atttypmod, src_att->attcollation, 0);
+ Var *dest_var = makeVar(1, dest_key_attnums[i], dest_att->atttypid, dest_att->atttypmod, dest_att->attcollation, 0);
+ List *args;
+ Oid actual_arg_types[2];
+ Oid declared_arg_types[2];
+ HeapTuple tup;
+ Form_pg_operator opform;
+ OpExpr *linkqual;
+
+ tup = SearchSysCache1(OPEROID, ObjectIdGetDatum(eq_ops[i]));
+ if (!HeapTupleIsValid(tup))
+ elog(ERROR, "cache lookup failed for operator %u", eq_ops[i]);
+ opform = (Form_pg_operator) GETSTRUCT(tup);
+
+ args = list_make2(src_var, dest_var);
+ actual_arg_types[0] = exprType((Node *) src_var);
+ actual_arg_types[1] = exprType((Node *) dest_var);
+ declared_arg_types[0] = opform->oprleft;
+ declared_arg_types[1] = opform->oprright;
+ make_fn_arguments(pstate, args, actual_arg_types, declared_arg_types);
+
+ linkqual = makeNode(OpExpr);
+ linkqual->opno = opform->oid;
+ linkqual->opfuncid = opform->oprcode;
+ linkqual->opresulttype = opform->oprresult;
+ linkqual->opretset = false;
+ /* opcollid and inputcollid will be set by parse_collate.c */
+ linkqual->args = args;
+ linkqual->location = -1;
+
+ ReleaseSysCache(tup);
+ quals = lappend(quals, linkqual);
+ }
+
+ eq_all = (list_length(quals) > 1
+ ? (Expr *) makeBoolExpr(AND_EXPR, quals, -1)
+ : (Expr *) linitial(quals));
+ qual = (Node *) makeBoolExpr(NOT_EXPR, list_make1(eq_all), -1);
+
+ assign_expr_collations(pstate, qual);
+ return qual;
+}
+
/*
* Construct a query which would not return any rows.
*
--
2.34.1
