[pgrouting-users] pg_trsp Restrctions Table Index

Matt Geneau matt.geneau at gmail.com
Thu Nov 26 13:25:40 PST 2015


In case anyone is curious in the future about filtering which restrictions
are loaded:

Instead of doing the barbell bounding boxes directly in the select edge sql
passed to pg_trsp, I created a stored procedure that took in the two
endpoints and a distance value, which calls ST_DWithin() 3 times to return
all edges in a barbell shaped box, based on the distance value. The edge
query passed to pg_trsp is then just a select all edges, joined to the SP.

With this I was able to modify the restrictions query passed to pg_trsp to
also join the SP results to only load in restrictions that would apply to
the same barbell box edges.

In the end I found that it was actually significantly slower to do this
join with the restrictions table versus the standard select all
restrictions. This was true for restriction tables with 30k and 100k rows.

On the bright side, my barbell bounding box query seems to benefit
speed/cache wise from being in a stored procedure since I make several
parallel calls to pg_trsp using different cost functions.

Thanks Steve for your help.

Matt

On Wed, Nov 25, 2015 at 3:39 PM, Matt Geneau <matt.geneau at gmail.com> wrote:

>
>
> On Wed, Nov 25, 2015 at 3:12 PM, Stephen Woodbridge <
> woodbri at swoodbridge.com> wrote:
>
>> On 11/25/2015 2:35 PM, Matt Geneau wrote:
>>
>>> Hello,
>>>
>>> While looking at ways to speed up my routing queries with pg_trsp, I
>>> noticed my restrictions table is always being hit with sequential scans.
>>> I came across
>>>
>>> http://gis.stackexchange.com/questions/109156/pgrouting-what-index-should-have-the-restriction-table
>>> but unfortunately it has no answer.
>>>
>>> I tried guessing two indexes but they did not work. While looking
>>> through the trsp.c code on Github to see if that could point me in the
>>> right direction, I was unable to figure out how the restrictions are
>>> being loaded.
>>>
>>> Does anyone have any suggestions on the best way to index the
>>> restrictions table?
>>>
>>
>> Hi Matt,
>>
>> The answer to this really has to do with what you need from the
>> restrictions table for a given query.
>>
>> If you always pass the restrictions like: select * geom restrictions;
>> then you will always do a full table scan and load all the restrictions
>> regardless of whether or not you need them.
>>
>> So for example, if you are doing a bbox query on your edges, then it
>> makes sense to only load the restrictions based on that same bbox. But
>> since the restrictions tables does not have any geometry you need to fake
>> it with a join against your edge table.
>>
>> So if your edges are selected like:
>>     select * from edge_table where geom && bbox;
>>
>> Then you might consider a restriction query like:
>>     select a.*
>>       from restrictions a,
>>            (select gid from edge_table where geom && bbox) b
>>      where a.to_edge=b.gid;
>>
>> I'm using gid as the primary key on the edge table and that is also the
>> values that are in the restrictions table.
>>
>> In the above example you what indexes on edge_table.gid, edge_table.geom
>> and it might help to have restrictions.to_edge indexed also for the join.
>>
>> -Steve
>> _______________________________________________
>> Pgrouting-users mailing list
>> Pgrouting-users at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
>
>
> For some reason I was thinking the restrictions were loaded after the
> route is generated, but of course they all need to be loaded beforehand in
> order to get a valid route.
>
> Thanks your reply, your suggestions will definitely help.
>
> Thanks,
> Matt
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20151126/73522bb5/attachment.html>


More information about the Pgrouting-users mailing list