Regression pgr_ksp much slower than 2.3

robe2 commented 7 years ago

Let me know if you need this dataset.

I run this query:


SELECT 
    k.path_id AS sol, 
    k.path_seq AS lgn, 
    COALESCE(a.name || ': ' || s.city || ' - ' || t.city, 'Total Trip') AS leg,
    CASE WHEN k.edge = -1 THEN k.agg_cost ELSE NULL END AS total_cost
FROM 
    pgr_ksp(
        'SELECT id, source, target, price_us AS cost FROM of.routes ',
        (SELECT id FROM of.airports WHERE icao = 'KEWR'), 
        (SELECT id FROM of.airports WHERE icao = 'VABB'),
        3, 
        directed := TRUE
    ) AS k LEFT JOIN 
    of.routes AS r ON k.edge = r.id LEFT JOIN 
    of.airports AS s ON r.source = s.id LEFT JOIN 
    of.airports AS t ON r.target = t.id LEFT JOIN 
    of.airlines AS a ON r.airline_id = a.airline_id
ORDER BY k.path_id, k.path_seq;

Expected behavior and actual behavior

In 2.3.2 I get the same answers though they are sorted a little different, performance is faster:


 sol | lgn |                     leg                      | total_cost
-----+-----+----------------------------------------------+------------
   1 |   1 | United Airlines: Newark - Mumbai             |       NULL
   1 |   2 | Total Trip                                   |     879.26
   2 |   1 | Delta Air Lines: Newark - Amsterdam          |       NULL
   2 |   2 | KLM Royal Dutch Airlines: Amsterdam - Mumbai |       NULL
   2 |   3 | Total Trip                                   |     941.54
   3 |   1 | Etihad Airways: Newark - Brussels            |       NULL
   3 |   2 | Jet Airways: Brussels - Mumbai               |       NULL
   3 |   3 | Total Trip                                   |     944.55
(8 rows)

Time: 308.019 ms

Steps to reproduce the problem

Install pgRouting 2.4.0 rc1. In 2.4.0 the time is much slower and yields:


 sol | lgn |                     leg                      | total_cost
-----+-----+----------------------------------------------+------------
   1 |   1 | United Airlines: Newark - Mumbai             |       NULL
   1 |   2 | Total Trip                                   |     879.26
   2 |   1 | Etihad Airways: Newark - Brussels            |       NULL
   2 |   2 | Jet Airways: Brussels - Mumbai               |       NULL
   2 |   3 | Total Trip                                   |     944.55
   3 |   1 | Delta Air Lines: Newark - Amsterdam          |       NULL
   3 |   2 | KLM Royal Dutch Airlines: Amsterdam - Mumbai |       NULL
   3 |   3 | Total Trip                                   |     941.54
(8 rows)

Time: 13920.660 ms

Specifications like the version of pgRouting/PostGIS and PostgreSQL as well as Operating System

Use the commands:

SELECT version();
SELECT postgis_full_version();
SELECT pgr_version();

cvvergara commented 7 years ago

https://github.com/pgRouting/pgrouting/blob/develop/NEWS#L21 The ordering fix needs extra sort for the output.

when doing this fixed an ordering detail on withPointsKSP

From the documentation: Example: Left side driving topology with details.

SELECT * FROM pgr_withPointsKSP(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
        'SELECT pid, edge_id, fraction, side from pointsOfInterest',
        -1, -2, 2,
        driving_side := 'l', details := true);

output:

 seq | path_id | path_seq | node | edge | cost | agg_cost 
-----+---------+----------+------+------+------+----------
   1 |       1 |        1 |   -1 |    1 |  0.6 |        0
   2 |       1 |        2 |    2 |    4 |  0.7 |      0.6
   3 |       1 |        3 |   -6 |    4 |  0.3 |      1.3
   4 |       1 |        4 |    5 |    8 |    1 |      1.6
   5 |       1 |        5 |    6 |   11 |    1 |      2.6
   6 |       1 |        6 |   11 |   13 |    1 |      3.6
   7 |       1 |        7 |   12 |   15 |  0.6 |      4.6
   8 |       1 |        8 |   -2 |   -1 |    0 |      5.2
   9 |       2 |        1 |   -1 |    1 |  0.6 |        0
  10 |       2 |        2 |    2 |    4 |  0.7 |      0.6
  11 |       2 |        3 |   -6 |    4 |  0.3 |      1.3
  12 |       2 |        4 |    5 |    8 |    1 |      1.6
  13 |       2 |        5 |    6 |    9 |    1 |      2.6
  14 |       2 |        6 |    9 |   15 |    1 |      3.6
  15 |       2 |        7 |   12 |   15 |  0.6 |      4.6
  16 |       2 |        8 |   -2 |   -1 |    0 |      5.2
(16 rows)

both routes have equal cost but the one marked as second, should be first because:

   5 |       1 |        5 |    6 |   11 |    1 |      2.6
   6 |       1 |        6 |   11 |   13 |    1 |      3.6

VS

 13 |       2 |        5 |    6 |    9 |    1 |      2.6
 14 |       2 |        6 |    9 |   15 |    1 |      3.6

the 9 is smaller than the 11

new output:

 seq | path_id | path_seq | node | edge | cost | agg_cost 
-----+---------+----------+------+------+------+----------
   1 |       1 |        1 |   -1 |    1 |  0.6 |        0
   2 |       1 |        2 |    2 |    4 |  0.7 |      0.6
   3 |       1 |        3 |   -6 |    4 |  0.3 |      1.3
   4 |       1 |        4 |    5 |    8 |    1 |      1.6
   5 |       1 |        5 |    6 |    9 |    1 |      2.6
   6 |       1 |        6 |    9 |   15 |    1 |      3.6
   7 |       1 |        7 |   12 |   15 |  0.6 |      4.6
   8 |       1 |        8 |   -2 |   -1 |    0 |      5.2
   9 |       2 |        1 |   -1 |    1 |  0.6 |        0
  10 |       2 |        2 |    2 |    4 |  0.7 |      0.6
  11 |       2 |        3 |   -6 |    4 |  0.3 |      1.3
  12 |       2 |        4 |    5 |    8 |    1 |      1.6
  13 |       2 |        5 |    6 |   11 |    1 |      2.6
  14 |       2 |        6 |   11 |   13 |    1 |      3.6
  15 |       2 |        7 |   12 |   15 |  0.6 |      4.6
  16 |       2 |        8 |   -2 |   -1 |    0 |      5.2

cvvergara commented 7 years ago

btw, withpointsKSP and KSP use internally the same code

robe2 commented 7 years ago

Okay seems to be back to normal after we figured out winnie was in debug and used latest cvergara that forces release mode.


SELECT * FROM pgr_version();
 version |    tag    |   hash    | branch  | boost
---------+-----------+-----------+---------+--------
 2.4.0   | v2.4.0-rc | af9546d05 | develop | 1.59.0
(1 row)

SELECT
    k.path_id AS sol,
    k.path_seq AS lgn,
    COALESCE(a.name || ': ' || s.city || ' - ' || t.city, 'Total Trip') AS le
    CASE WHEN k.edge = -1 THEN k.agg_cost ELSE NULL END AS total_cost
FROM
    pgr_ksp(
        'SELECT id, source, target, price_us AS cost FROM of.routes ',
        (SELECT id FROM of.airports WHERE icao = 'KEWR'),
        (SELECT id FROM of.airports WHERE icao = 'VABB'),
        3,
        directed := TRUE
    ) AS k LEFT JOIN
    of.routes AS r ON k.edge = r.id LEFT JOIN
    of.airports AS s ON r.source = s.id LEFT JOIN
    of.airports AS t ON r.target = t.id LEFT JOIN
    of.airlines AS a ON r.airline_id = a.airline_id
ORDER BY k.path_id, k.path_seq;
 sol | lgn |                     leg                      | total_cost
-----+-----+----------------------------------------------+------------
   1 |   1 | United Airlines: Newark - Mumbai             |       NULL
   1 |   2 | Total Trip                                   |     879.26
   2 |   1 | Etihad Airways: Newark - Brussels            |       NULL
   2 |   2 | Jet Airways: Brussels - Mumbai               |       NULL
   2 |   3 | Total Trip                                   |     944.55
   3 |   1 | Delta Air Lines: Newark - Amsterdam          |       NULL
   3 |   2 | KLM Royal Dutch Airlines: Amsterdam - Mumbai |       NULL
   3 |   3 | Total Trip                                   |     941.54
(8 rows)

Time: 322.038 ms

pgRouting / pgrouting