[Cartoweb-dev] urgent: pgdijkstra hacking (caching source connectivity)

[Sylvain Pasche]

Le vendredi 24 février 2006 à 17:45 +0000, Hugo Ferreira a écrit :
> Good day,
> 
> Currently I have an "heavy" problem with pgdijkstra... My routing
> tables has about 0.8 million rows. While pgdijkstra is able to find a
> route within it very quickly (hail to libboost :)), the loading of
> this 0.8 million rows takes about 30seconds on my 2xXEON with SCSI.
> 
> Therefore, I want to hack the source code to maintain a sort of cache.
> If we do a SELECT * FROM ROUTING in the past, and we're passing a
> boolean that says "use the cache if u done this query previously",
> then there's no need to reload the data from postgresql but use the
> already loaded data in the memory. 
> 
> I have two problems here:
> 
> a) I don't know how postgresql handles external calls. But if data is
> maintained between calls, then this would be very easy to implement. I
> could even make some functions like cache_data(query, id) and
> uncache_data(id), and then make a cached_shortest_path(id, ...); 

Actually, no data is maintained between calls. It uses palloc/pfree, for
which the manual says:

""When allocating memory, use the PostgreSQL functions palloc and pfree
instead of the corresponding C library functions malloc and free. The
memory allocated by palloc will be freed automatically at the end of
each transaction, preventing memory leaks.""

The nature of a database server makes it not very appropriate for
in-memory caching, as the system is made to free memory after each
transactions (stateless regarding internal datastructures). However, it
should be possible to keep the cache in the heap. But special care
should be taken for synchronisation and transactions.

I have not much experience with it, but I would first have a look at
some other postgresql extensions, to see how they deal with such a
situation (if they do).

An intermediate solution would be to store graphs in a pre-computated
form inside a table which could be loaded faster by boost. But that
would not beat a graph kept in memory in a cache.

> b) I can't compile pgdijkstra under windows. I know, i know.. But my
> deployment machine is a windows station so this IS a requirement...
> Basically I've installed cygin and I have mingw from dev-c++. But when
> I try to compile I get the following errors: 
> 
> C:\pgdijkstra>g++ -o2 -Ie:\cygwin\usr\include\boost-1_33_1 -c
> boost_wrapper.cpp
> In file included from e:\cygwin\usr\include\boost-1_33_1\boost
> \config.hpp:40,
>                  from boost_wrapper.cpp:22:
> e:\cygwin\usr\include\boost-1_33_1\boost\config
> \select_stdlib_config.hpp:20: uti
> lity: No such file or directory
> boost_wrapper.cpp:23: iostream: No such file or directory
> boost_wrapper.cpp:24: fstream: No such file or directory 
> In file included from boost_wrapper.cpp:26:
> e:\cygwin\usr\include\boost-1_33_1\boost\graph\graph_traits.hpp:14:
> iterator: No
>  such file or directory
> (...)
> I think this must have something to do with the slash and
> reverse-slash notation... Any ideas?? 

Looks like it does not find some files like utility or iostream headers.
Maybe check if they are available somewhere, or if some package is
missing. Sorry, I did not touch the Win32 build for some times, I can't
tell what's wrong exactly.

> I would appreciate any tips on this, since I need to get it done over
> this weekend. If it works, I will submit the patch for you guys to
> consider using it.

That may definitely be a good enhancement for pgdijkstra ;-)

Regards,

Sylvain