shootingstar (#18) - Function shortest_path_shooting_star is SLOW (#217) - Message List

Function shortest_path_shooting_star is SLOW

Hi!!....

I'm using the function "shortest_path_shooting_star" and it returns the result perfectly but depending of the number of data the performance is slower. For example i created two tables.

Table 1 have this structure, the name of this table is "mtxlinks":

gid2 integer NOT NULL, source integer, target integer, "cost" double precision, reverse_cost double precision, to_cost double precision, x1 double precision, y1 double precision, x2 double precision, y2 double precision, "rule" text, id_cc1 integer, CONSTRAINT "PK_mtxlinks2" PRIMARY KEY (gid2)

Table 2 have the same structure, the name of this table is "mtxlinks2":

gid2 integer NOT NULL, source integer, target integer, "cost" double precision, reverse_cost double precision, to_cost double precision, x1 double precision, y1 double precision, x2 double precision, y2 double precision, "rule" text, id_cc1 integer, CONSTRAINT "PK_mtxlinks" PRIMARY KEY (gid2)

To know the number of rows:

select count(*) from mtxlinks ... this return: 507.770

select count(*) from mtxlinks2 .... this return: 77.463

When i run this SP:

SELECT "edge_id" FROM shortest_path_shooting_star(

'SELECT gid2 as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM mtxlinks2 order by gid2' ,113037234 ,113048625 , false , true )

in the table 1 "mtxlinks" is very very slow.... but in the table 2 "mtxlinks2" is very fast.

To analize this i execute EXPLAIN ANALYZE SELECT on the SP at the table "mtxlinks ":

EXPLAIN ANALYZE SELECT "edge_id" FROM shortest_path_shooting_star(

'SELECT gid2 as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM mtxlinks order by gid2' ,113037234 ,113048625 , false , true )

this return : "Function Scan on shortest_path_shooting_star (cost=0.00..12.50 rows=1000 width=4) (actual time=34172.209..34172.272 rows=45 loops=1)" and "Total runtime: 34172.372 ms".

EXPLAIN ANALYZE SELECT on the SP at the table "mtxlinks2":

EXPLAIN ANALYZE SELECT "edge_id" FROM shortest_path_shooting_star(

'SELECT gid2 as id, source, target, cost, reverse_cost, x1, y1, x2, y2, rule, to_cost FROM mtxlinks2 order by gid2' ,113037234 ,113048625 , false , true )

this return :

"Function Scan on shortest_path_shooting_star (cost=0.00..12.50 rows=1000 width=4) (actual time=4836.670..4836.733 rows=45 loops=1)" and "Total runtime: 4836.830 ms"

How can i fix that? How can i improve the speed of the function? is depends on columns? depend about the number of data? Becouse in the example www.ridethecity.com is very fast and i guess that they have more number of data ....

Help me please...

Thanks..

mhungc
02/10/09 04:16:04 (22 months ago)
Tree View Flat View (newer first) Flat View (older first)
  • Message #775

    First thing: it doesn't help to speed up things if you post the same question two times at different places or create a ticket. I don't have the time to check if both are just copy & paste, so I just answer this one.

    There are several ways to improve shortest path queries:

    • Create indices (gid, source, target, geometry index)
    • Select only the data of the area (BBOX) you really need. You might want to use "wrappers" for that (did you read through the tutorials?)

    If this doesn't help yet:

    • Prepare some data that might not change like cost columns for example.
    • Renumber ID's (best is your max. ID is not higher than the number of links)

    These are the ones that came to my mind now, but if this still doesn't help, just ask again.

    Half a million links is not that much and you should get a result more fast. But there is a limitation which depends on your hardware, but you won't be able to load a network of a few million links and get the route in a reasonable time.

    daniel
    02/10/09 08:50:26 (22 months ago)
    • Message #776

      Sorry Daniel it will not happen again :S .

      Thanks for your help.

      I'm trying the "wrappers" like this

      SELECT gid , AsText?(the_geom) AS the_geom

      FROM shootingstar_sp('mtxlinks', 67051413, 30000300, 0.1, 'cost', true, true)

      But I'm realizing that it return me a result depends of the buffer for example 0.1 in my case with this parameter "67051413, 30000300" not working but if a change this 0.1 to 0.3 it works. Is very fast when the buffer is 0.1 but if a change this variable it become slow....

      Can you help me with this?.

      And another cuestion Daniel... What you mean in :

      "Prepare some data that might not change like cost columns for example."

      and

      "Renumber ID's (best is your max. ID is not higher than the number of links)" ?

      Thanks a lot!!

      mhungc
      02/11/09 03:40:32 (22 months ago)
      • Message #778

        The "buffer" value in the wrapper extends your bounding box (which is defined by your start and end point). This buffer is in the same unit as your geometry is. In your case it seems to be degree, I guess. You might agree that increasing the buffer from 0.1 degree to 0.3 extends your area you load to memory a lot.

        So the buffer value needs to be tested: as small as possible to keep the loaded area small, but large enough not to get wrong results. I sometimes looked for the longest link in my network and set the buffer this value.

        Preparing the data means that instead of joining tables to calculate a cost value from several parameters (ie. speed, length, road type, etc.), you could precalculate this as a new attribute. It's same as you probably did with the start and end x/y for shooting star. Of course you could do this with every query, but this value will hardly change, so you can do it in advance and it will increase the speed.

        Nevertheless data loading is the most important parameter to improve the query.

        daniel
        02/11/09 18:08:59 (22 months ago)
        • Message #780

          I will check my data Daniel.

          Another questions my friend....

          We can use shootingstar_sp with "functional Classes"? becouse our data contains this. Or exist others functions that working with long paths and return a result faster?

          Thanks!

          mhungc
          02/12/09 04:25:28 (22 months ago)
          • Message #781

            We can use shootingstar_sp with "functional Classes"?

            You mean something like road classes? Similar to this maybe: WorkshopFOSS4G2008/ch11

            Or exist others functions that working with long paths ...

            Sorry, but I didn't understand this.

            daniel
            02/12/09 10:01:09 (22 months ago)
            • Message #787

              Thanks Daniel,

              For the first question I will read the documment...

              I mean in "Or exist others functions that working with long paths ..." that if exist another function to improve the algorithm with long paths?, becouse for Short paths when i use "shootingstar_sp" with a degree 0.1 or 0.2 or the function "shortest_path_shooting_star" the result that they return us is very fast but for long paths is very slow......and in the "shootingstar_sp" the parameter degree is very intuitive to use becouse i dont know how calculate it respect the points or the parameter the_geom geometry".

              i hope explain it well becouse my english is very basic jejejej.

              Thanks Daniel.

              mhungc
              02/12/09 22:06:36 (22 months ago)
              • Message #791

                Short answer: Unfortunately they don't exist (yet).

                Long answer: There are several techniques (approaches, algorithms) that try to solve this issue. Dozens of research papers, studies, etc.. It is just not trivial to implement them. It's a matter of time and money.

                Open source answer: we are waiting for code contribution or sponsorship. ;-)

                daniel
                02/13/09 09:41:48 (22 months ago)
Tree View Flat View (newer first) Flat View (older first)