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

Started by Ayoub Kazarabout 2 hours ago1 messageshackers

kazarayoub2004@gmail.com

about 2 hours ago

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]https://github.com/ldbc/lsqb, [2]https://ir.cwi.nl/pub/31398/31398.pdf 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]https://ir.cwi.nl/pub/31398/31398.pdf 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:

---------------

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

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

Attachments: