Speed up pgr_createTopology on large networks?

[kimonkrenz]

Is there a way to speed up pgr_createTopology, or modify the number of processed edges per iteration used in pgr_createTopology?

Frequent creations of topologies of larger networks (i.e. 1-8million edges) are very time consuming.
The algorithm processes 1000 edges per second (approx.), while neither RAM nor CPU are being maxed (not even 5%), resulting in approx. 30min for a 2 million edge network.

NOTICE:  PROCESSING:
NOTICE:  pgr_createTopology('road_network', 0.0001, 'geom', 'id', 'source', 'target', rows_where := 'true', clean := t)
NOTICE:  Performing checks, please wait .....
NOTICE:  Creating Topology, Please wait...
NOTICE:  1000 edges processed
NOTICE:  2000 edges processed
NOTICE:  3000 edges processed
NOTICE:  4000 edges processed 
...

Nb. the input table is vacuumed, clustered and columns geom, id, source and target are indexed.

Similar questions have been posted at alternative forums (e.g. stackexchange, or stackexchange). Unfortunately, existing solutions are for Python which I am not using, or other suggestions don't show any effect.

Set up:
macOS Big Sur 11.6 (20G165), 3.1 GHz Quad-Core Intel Core i7, 16 GB 2133 MHz LPDDR3
PostgreSQL 14.1 on x86_64-apple-darwin20.6.0, compiled by Apple clang version 13.0.0 (clang-1300.0.29.3), 64-bit
POSTGIS="3.1.4 ded6c34" [EXTENSION] PGSQL="140" GEOS="3.10.2-CAPI-1.16.0" SFCGAL="1.4.0" PROJ="7.2.1" GDAL="GDAL 3.4.1, released 2021/12/27" LIBXML="2.9.12" LIBJSON="0.15" LIBPROTOBUF="1.4.0" WAGYU="0.5.0 (Internal)" TOPOLOGY RASTER
pgRouting 3.3.0

[TimMcCauley]

@kimonkrenz this is not a full answer to your problem yet but you may experience some speedups using https://docs.pgrouting.org/latest/en/pgr_extractVertices.html instead and afterwards computing contracted edges again https://gis.stackexchange.com/questions/422316/postgis-unsplit-merge-lines-that-have-coincident-endpoints ? What do you think @cvvergara?

[Phyks]

For my particular use case, I need to run a pgr_connectedComponents analysis on my graph (40M edges). Trying to run it directly leads into a malloc error:

invalid memory alloc request size 1080000000

So I though I could look into the contraction part to downsize my graph, and tried to run pgr_contraction as per your example. I get the exact same malloc issue with pgr_contraction.

This is not so much a blocking issue when using pgr_dijkstra since, although my graph is large, routing is very local and I can easily filter out geometries with a bounding box to reduce number of considered edges.

I'm thinking about tiling the runs of pgr_contraction or pgr_connectedComponents (by gridding with tiles of a few degrees latitude/longitude for instance) and then merging the results. But maybe someone around would have a better idea?

I'm also quite surprised by the malloc error message. I'm not sure about the unit of the number displayed, but if I'm counting right, this should not be much more than 1GB (while my laptop certainly does not have plenty of RAM, it should have at least 10GB free).

Thanks!

[Phyks]

For my particular use case, I need to run a pgr_connectedComponents analysis on my graph (40M edges). Trying to run it directly leads into a malloc error:

invalid memory alloc request size 1080000000

So I though I could look into the contraction part to downsize my graph, and tried to run pgr_contraction as per your example. I get the exact same malloc issue with pgr_contraction.

This is not so much a blocking issue when using pgr_dijkstra since, although my graph is large, routing is very local and I can easily filter out geometries with a bounding box to reduce number of considered edges.

I'm thinking about tiling the runs of pgr_contraction or pgr_connectedComponents (by gridding with tiles of a few degrees latitude/longitude for instance) and then merging the results. But maybe someone around would have a better idea?

I'm also quite surprised by the malloc error message. I'm not sure about the unit of the number displayed, but if I'm counting right, this should not be much more than 1GB (while my laptop certainly does not have plenty of RAM, it should have at least 10GB free).

Thanks!

EDIT: My malloc issue looks like #291 but I'm not seeing much solutions there :/

[TimMcCauley]

This unfortunately leaves my realm of knowledge, the only thing I can think of is tinkering around with the memory settings in postgresql.conf - you can have a look at pgtune for some ideas.

[Phyks]

I have the exact same issue with a default postgresql.conf or one from pgtune.

My current postgresql.conf looks like:

#------------------------------------------------------------------------------
# CUSTOMIZED OPTIONS
#------------------------------------------------------------------------------

# Add settings for extensions here

# https://pgtune.leopard.in.ua/
# DB Version: 14
# OS Type: linux
# DB Type: mixed
# Total Memory (RAM): 12 GB
# CPUs num: 4
# Connections num: 50
# Data Storage: ssd

max_connections = 50
shared_buffers = 3GB
effective_cache_size = 9GB
maintenance_work_mem = 768MB
checkpoint_completion_target = 0.9
wal_buffers = 16MB
default_statistics_target = 100
random_page_cost = 1.1
effective_io_concurrency = 200
work_mem = 15728kB
min_wal_size = 1GB
max_wal_size = 4GB
max_worker_processes = 4
max_parallel_workers_per_gather = 2
max_parallel_workers = 4
max_parallel_maintenance_workers = 2

And the error message:

db=# (SELECT component, node FROM pgr_connectedComponents(
        'SELECT id, source, target, cost  FROM edges'
));
ERREUR:  invalid memory alloc request size 1080000000
CONTEXTE : fonction SQL « pgr_connectedcomponents », instruction 1

I'll post on the pgRouting ML, it might get more visibility there to finalize an end to end recipe for handling large graphs with pgr_extractVertices.

[TimMcCauley]

@cvvergara 👋🏽 have you seen something similar on larger graphs?