Keep graph in Ram

[esdras-kid]

To optimize performance for large graphs, I have some ideas that could potentially improve the process. Currently, with every call to pgRouting, there is a time overhead for loading the graph from the PostgreSQL database and building the Boost C++ graph structure internally before running the algorithm.

My idea is to explore two possible approaches:

Keep the Graph in RAM:

It is possible to load the entire graph from the PostgreSQL database into RAM and keep it there during the lifetime of the application or API. By doing so, subsequent calls to the routing algorithm can directly access the graph data in memory, significantly reducing the overhead of loading the graph from the database each time.

Generate Boost Graph Structure in RAM:

If keeping the entire graph in RAM is not feasible due to size constraints, another approach is to generate the Boost C++ graph structure directly in memory and cache it for subsequent algorithm calls.

[cvvergara]

Hi @esdras-kid

The thought looks interesting, but with the experience with graphs "on real roadneworks":

• The road network for a car
• is different for a pedestrian
• is different for a truck A that weight X
• is different for a truck B with weight Y and height Z.
• is different at different times of day

But there might be problems where the graph might be static for a long period of time. We meet on gitter and discussions with all developers take place at discourse.osgeo.org (look for pgrouting-dev)

[robe2]

thread on users was started about this topic - https://discourse.osgeo.org/t/graph-in-memory/111494

The jitter is also accessible via matrix https://matrix.to/#/#pgrouting:osgeo.org

[joto]

I can only second that original request. It seems to me a lot of use cases would benefit from a pre-built graph and it would somewhat close the huge performance gap between pgRouting and specialized routing engines.

And it really would become interesting if it would be possible to "prepare" graphs and then merge several of those graphs for each request. Then I could split the area of interest into tiles, generate a graph for each tile, and add an additional graph that only contains the interstate highways. When the query comes in, I merge the tiled graphs nearest the source and target, add the interstate overlay and run the query on that.

The largest problem might be where to store the "prepared" graph. But even if it is not possible to do that prepare for the whole database, just for a single session or transaction, it could be useful.

[cvvergara]

How it works now, hooked to an API:

The idea in my mind: A first call on the API

Subsequent calls on the API

Note that I have this image in my mind since 9 years ago: https://github.com/cvvergara/presentations/tree/gh-pages/2015/future files: animation1.gif animation3.gif & animation3.gif

Made a toy example of that idea here (yet again 9 years ago): https://github.com/pgRouting/pgrouting/tree/pgrouting-2.2.4/src/linecommand/src