Optimisation requête postgis

Tioneb · Novembre 16, 2019, 8:44

Je suis confronté à une difficulté avec une requête postgis. Actuellement, avec seulement 1000 points en bdd de données, je suis à environ à 12 secondes pour générer ma page web, ce qui est énorme
Donc j’imagine qu’avec 50 ou 100 ou 200 fois plus de points et plusieurs personnes qui font des recherches en même temps, j’aurai le temps d’aller boire un café … ou de me pendre

J’ai deux options, soit optimiser la requête et arriver à un temps de chargement optimal ou bien tricher un peu en faisant des pré-calculs, que je stocke en bdd. Franchement, la deuxième option, n’a rien d’idéale, ça supposerait de parcourir toutes les données de façon régulière et générer/updater la data qui va bien.

Donc c’est pour ça que je crie au secours et appelle à votre expérience pour voir ce qu’il est possible de faire.

La requête me permet de récupérer l’ensemble des POIs situé de part et d’autre d’une trace (en fonction d’un point de départ).
Et la sous requête qui calcule la distance entre le point de départ et le point affiché, pour pouvoir afficher les POIs dans l’ordre. Cette sous-requête est donc appelée pour chaque point d’arrivée potentiel.
Pour afficher le kilométrage, je rappelle une deuxième fois l’équivalent de la sous requête. Ce qui n’est pas franchement idéal…

La requ^te pour récupérer la liste des POIs :

    def poi_around_trace_from__(poi, trace, dist)
      distance_sql = <<-SQL
      SELECT
        ST_Distance(tr.path::geography, pta.lonlat::geography) +
        ST_Distance(tr.path::geography, poi.lonlat::geography) +
        ST_Length(ST_LineSubstring(
          tr.path,
          least(ST_LineLocatePoint(tr.path, pta.lonlat::geometry), ST_LineLocatePoint(tr.path, poi.lonlat::geometry)),
          greatest(ST_LineLocatePoint(tr.path, pta.lonlat::geometry), ST_LineLocatePoint(tr.path, poi.lonlat::geometry))),false)  AS dst_line, poi.*
      FROM traces tr, pois pta, (
        SELECT poi.* AS pois
        FROM traces tr, pois pta, pois poi
        WHERE tr.id = #{trace.id}
        AND pta.id = #{poi.id}
        AND ST_DWithin(ST_LineSubstring(
                tr.path,
                ST_LineLocatePoint(tr.path, pta.lonlat::geometry) + (#{dist} * 1000) / (tr.length * 1000) ,
                ST_LineLocatePoint(way.path, pta.lonlat::geometry) + #{end_point} / ST_Length(way.path, false))::geography,
                poi.lonlat::geography,
                200)
          ) as poi
        WHERE tr.id = #{trace.id}
        AND pta.id = #{poi.id}
        AND poi.id = poi.id
        ORDER BY dst_line ASC
      SQL
      Rails.cache.fetch(['sql-distance', trace, poi, dist]) {
        Poi.find_by_sql(distance_sql)
      }
    end

la requête pour le calcul des distances :

    
    def distance_along_way_to(poi1, poi2, way)
      distance_sql = <<-SQL
      SELECT
        ST_Distance(way.path::geography, pta.lonlat::geography) +
        ST_Distance(way.path::geography, ptb.lonlat::geography) +
        ST_Length(ST_LineSubstring(
          way.path,
          least(ST_LineLocatePoint(way.path, pta.lonlat::geometry), ST_LineLocatePoint(way.path, ptb.lonlat::geometry)),
          greatest(ST_LineLocatePoint(way.path, pta.lonlat::geometry), ST_LineLocatePoint(way.path, ptb.lonlat::geometry))),false)  AS dst_line
        FROM ways way, pois pta, pois ptb
        WHERE way.id = #{way.id}
          AND pta.id = #{poi1.id}
          AND ptb.id = #{poi2.id}
      SQL
      Rails.cache.fetch(['sql-distance', way, poi1, poi2]) {
        Poi.find_by_sql(distance_sql).first.dst_line
      }
    end

Je met également un explain de la première requête, si ça peut aider, moi, je ne sais pas l’interpréter

"Sort  (cost=46.67..46.71 rows=15 width=209)"
"  Sort Key: (((_st_distance((tr.path)::geography, pta.lonlat, '0'::double precision, true) + _st_distance((tr.path)::geography, poi.lonlat, '0'::double precision, true)) + st_length((st_linesubstring(tr.path, LEAST(st_linelocatepoint(tr.path, (pta.lonlat)::geometry), st_linelocatepoint(tr.path, (poi.lonlat)::geometry)), GREATEST(st_linelocatepoint(tr.path, (pta.lonlat)::geometry), st_linelocatepoint(tr.path, (poi.lonlat)::geometry))))::geography, false)))"
"  ->  Nested Loop  (cost=0.00..46.38 rows=15 width=209)"
"        Join Filter: st_dwithin((st_linesubstring(tr_1.path, (st_linelocatepoint(tr_1.path, (pta_1.lonlat)::geometry) + ('20000'::double precision / (tr_1.length * '1000'::double precision))), (st_linelocatepoint(tr_1.path, (pta_1.lonlat)::geometry) + ('200000'::double precision / st_length((tr_1.path)::geography, false)))))::geography, poi.lonlat, '2000'::double precision)"
"        ->  Nested Loop  (cost=0.00..7.23 rows=1 width=136)"
"              ->  Nested Loop  (cost=0.00..4.64 rows=1 width=104)"
"                    ->  Nested Loop  (cost=0.00..3.61 rows=1 width=64)"
"                          ->  Seq Scan on traces tr  (cost=0.00..1.02 rows=1 width=32)"
"                                Filter: (id = 2)"
"                          ->  Seq Scan on pois pta  (cost=0.00..2.58 rows=1 width=32)"
"                                Filter: (id = 2)"
"                    ->  Seq Scan on traces tr_1  (cost=0.00..1.02 rows=1 width=40)"
"                          Filter: (id = 2)"
"              ->  Seq Scan on pois pta_1  (cost=0.00..2.58 rows=1 width=32)"
"                    Filter: (id = 2)"
"        ->  Seq Scan on pois poi  (cost=0.00..2.46 rows=46 width=201)"
"              Filter: (id IS NOT NULL)"

Je trouverais dommage, après avoir passé autant de temps sur Postgis, à ne pas pouvoir utiliser l’outil et devoir me rabattre sur le système bricolé des pré-calculs

Mais je suis sûr qu’il existe une solution, sinon faut 'expliquer comment google fait pour afficher aussi vite ses itinéraire sur une map

yvecai · Novembre 16, 2019, 10:17

Je suis pas expert et je vais peut être dire une c., mais rajouter des &&BBOX dans les sous-requêtes, avec les bons index, c’est une piste qui m’a souvent tiré d’affaire.

Tioneb · Novembre 17, 2019, 2:06

J’ai regardé les bbox, mais comment déterminer de façon automatisée les coordonnées de ces bbox ?
De plus, je ne suis pas sur et je vais peut être dire une grosse connerie, mais il semblerait que les bbox soient automatiques autour de chaque geom… ?

Tioneb · Novembre 18, 2019, 2:48

Bon, j’ai avancé un peu… et gagné quelques secondes, mais je suis encore au alentours 9 sec par page contre 2,5 sec, une fois la page mise en cache.
En plus, j’ai du rajouter une vérification supplémentaire => du coup, me suis rendu compte que j’avais des appels qui se répétaient.
Du coup je me suis orienté vers des CTE, j’ai vu qu’il y avait des avis partagés vs les tables temporaires, voilà ce que j’ai fait :

WITH locate_point_a AS (
  select ST_LineLocatePoint(tr.path, pta.lonlat::geometry) AS locate_point_a
  FROM traces tr, pois pta
  WHERE tr.id = 2
	  AND pta.id = 2
  ),
  path_length AS (
  SELECT ST_Length(tr.path, false) AS path_length
  FROM traces tr
  WHERE tr.id = 2
  )
  
      SELECT
        ST_Distance(tr.path::geography, pta.lonlat::geography) +
        ST_Distance(tr.path::geography, poi.lonlat::geography) +
        ST_Length(ST_LineSubstring(
          tr.path,
          least(locate_point_a, ST_LineLocatePoint(tr.path, poi.lonlat::geometry)),
          greatest(locate_point_a, ST_LineLocatePoint(tr.path, poi.lonlat::geometry))),false)  AS dst_line, poi.*
      FROM traces tr, pois pta, locate_point_a,  (
        SELECT poi.* AS pois
        FROM traces tr, pois pta, pois poi, locate_point_a, path_length
        WHERE tr.id = 2
        AND pta.id = 2
        and poi.active = true
        AND ST_DWithin(ST_LineSubstring(
                tr.path,
                locate_point_a + (20 * 1000) / (tr.length * 1000) ,
                ( CASE
                  WHEN (locate_point_a + (200 * 1000)/ path_length) > 1.0
                  THEN 1
                  ELSE
                  locate_point_a + (200 * 1000)/ path_length
                  end
                ))::geography,
                poi.lonlat::geography,
                2000)
          ) as poi
        WHERE tr.id = 2
		AND pta.id = 2			   
		AND poi.id = poi.id
        ORDER BY dst_line ASC

yvecai · Novembre 18, 2019, 5:11

Aussi, pourquoi utiliser des ::geography? ::geometry est moins gourmand en calcul et bien souvent suffisant.

Tioneb · Novembre 18, 2019, 7:56

Effectivement ta remarque est très judicieuse… et aussitôt appliquée. On tombe maintenant aux alentours de 6 secondes, c’est déjà mieux…

Est ce que les CTE ont un impact important sur la perf ? Car je pourrais en faire un troisième, avec ST_LineLocatePoint(tr.path, pta.lonlat::geometry), mais comme c’est dépendant du résultat de la sous requête, je ne sais pas trop comment le gérer…

Pour éviter de parcourir toute la table, il y a pas un moyen de faire une pré-selection des POIs dans un périmètre donné ? Est ce qu’une table temporaire indexée aurait du sens ?

Sinon, comment vous faites pour vous y retrouver dans queries imbriquées, j’avoue que je m’arrache parfois un peu les cheveux

EDIT :
Bon, fausse joie, avec les geometry, mon rendu est faussé et le order by_distance est complètement erroné (ce qui n’est pas surprenant) et qui explique pourquoi j’étais parti sur des geography

yvecai · Novembre 19, 2019, 4:33

http://www.postgis.fr/chrome/site/docs/workshop-foss4g/doc/indexing.html
&&!

Pour les distances en ‘geometry’ st_distancespheroid() devrait aider.

Tioneb · Novembre 19, 2019, 12:26

Bon, je viens de tenter
ST_Distance_Spheroid avec 'SPHEROID[“WGS 84”,6378137,298.257223563] (st_distancespheroid a été remplacé)
paradoxalement, j’ai temps de requêtes qui sont beaucoup plus longs… en local (mais je n’ai pas beaucoup de données) c’est du presque fois deux par rapport à ST_Distance. En prod, toujours avec moins de 1000 points, je suis à 9 secondes environ.

Dans la foulée j’ai également tenté ST_Distance_Sphere => pas beaucoup mieux.

Concernant l’approche avec les index, pourrais tu m’expliquer un peu (j’ai fais un petit dessin pour simplifier la chose) :

Sinon, j’ai bien deux index :
=> t.index [“lonlat”], name: “index_pois_on_lonlat”, using: :gist
=> t.index [“path”], name: “index_traces_on_path”, using: :gist

Si j’ai bien compris, tous les points situés dans la zone rose de part et d’autre de la linestring seront pris en compte ?
A, B, C, D ne feront dont pas parti de la liste ca il n’intersectent pas avec la bbox de la linestring ?

Par contre, je vois pas trop comment faire au niveau de ma requête ? au niveau de la sous requête ?

cquest · Novembre 24, 2019, 8:08

La requête me permet de récupérer l’ensemble des POIs situé de part et d’autre d’une trace (en fonction d’un point de départ).
Et la sous requête qui calcule la distance entre le point de départ et le point affiché, pour pouvoir afficher les POIs dans l’ordre. Cette sous-requête est donc appelée pour chaque point d’arrivée potentiel.
Pour afficher le kilométrage, je rappelle une deuxième fois l’équivalent de la sous requête. Ce qui n’est pas franchement idéal…

Je préfère repartir de zéro que de ta requête qui me semble bien trop complexe…

Il y a deux choses à faire:

sélectionner les points à proximité de la trace (linestring)
calculer l’ordre de ces points projetés sur la trace

J’imagine donc une table « route » et une « poi » chacune avec un champ geom (geometry), en WGS84 (EPSG:4326) nécessaire pour le passage geometry ↔ geography.

On commence par le 1) !

Si on veut chercher à une certaine distance métrique, le plus simple (et rapide) donne quelque chose comme

ST_Buffer(route.geom::geography, distance)::geometry → retourne un buffer à une distance métrique autour de la route

Ensuite on cherche les points qui sont en intersection avec ST_Intersects

SELECT p.* FROM route JOIN poi p ON (ST_Intersects(ST_Buffer(route.geom::geography, dist)::geometry, p.geom) WHERE route.id = monid;

Si il y a un index gist sur poi.geom ça ira très vite car ST_Intersects l’utilisera. Un index géo sur routes n’aura par contre aucun intérêt vu que c’est pas de ce côté qu’on cherche des données, un index sur l’id sera par contre bienvenu si il y a beaucoup de routes.

Pour le 2)

ST_ClosestPoint permet de trouver le point sur la route le plus proche d’un poi sélectionné dans la première requête et ST_LineLocatePoint permettra de connaitre sa position relative sur le linestring… donc pour avoir l’ordre ça donne:

ST_LineLocatePoint(route.geom, ST_Closestpoint(route.geom, poi.geom))

Pour ça, aucun index ne sera utile vu que ce n’est que du calcul entre objet déjà sélectionnés et pas de la sélection.

Globalement la requête ressemblera à:

SELECT p.*
FROM route
JOIN poi p ON ST_Intersects(ST_Buffer(route.geom::geography, dist)::geometry, p.geom)
WHERE route.id = monid
ORDER BY ST_LineLocatePoint(route.geom, ST_Closestpoint(route.geom, poi.geom));

^ je n’ai pas testé, c’est « à main levée », mais l’idée est là

Après faut adapter si besoin, mais c’est quand même bien plus simple et compréhensible, non ?

Tioneb · Novembre 26, 2019, 5:33

Hello Quest et merci pour ton coup de pouce.

Plusieurs remarques, la requête que tu suggères est effectivement plus simple et plus lisible, mais :

en local et avec seulement 30 pois, je suis à environ 1.30 minutes J’ai même pas essayé de tester en pré-prod, me serai pris un time-out. J’ai pourtant les index sur le geom
ta requête est partielle (par rapport à la mienne) et ne prends pas en compte la première partie. C’est normal, la requête est pas évidente à lire. mais en soi ce n’est pas forcément un souci, je peux avoir une méthode qui fait le travail en amont

J’ai fait un petit schéma, c’est toujours plus explicite.

J’ai une trace (T), un point de départ (D) et une distance en Km. Ces 3 éléments me permettent de définir A et A’. C’est dans la zone comprise entre A et A’ que je dois trouver les pois autour de la trace (en vert sur le schéma).
Ta requête elle, permet de trouver l’ensemble des pois pour toute la trace.

Si l’on reprend ta logique, je pourrais avoir deux queries dans ce style. Ca te permettra peut être de mieux comprendre.

Je pourrais avoir une première query qui permet de faire un substring sur la trace (j’ai mis des valeurs fixes pour simplifier)

      SELECT
      ST_LineSubstring(
      tr.path,
      ST_LineLocatePoint(tr.path, pta.lonlat::geometry) + 20000 / ST_Length(tr.path, false),
      ST_LineLocatePoint(tr.path, pta.lonlat::geometry) + 40000 / ST_Length(tr.path, false)
      )::geography
      FROM traces tr, pois pta
      where tr.id = 2
      AND pta.id = 2

Qui retourne : substring de la trace (A =>A’)

ensuite j’appelle ta requête (à laquelle j’envoie je résultat de la première requète (substring) ) pour récupérer les fameux pois :

SELECT p.*
FROM route
JOIN poi p ON ST_Intersects(ST_Buffer(route.geom::geography, dist)::geometry, p.geom)
WHERE route.id = monid
ORDER BY ST_LineLocatePoint(route.geom, ST_Closestpoint(route.geom, poi.geom));

Ou bien, faire une seule requête avec les deux ? Je ne sais pas ce qui serait le plus pertinent.

Toujours est-il, le temps de requête est beaucoup plus élevé que ma requête initiale, pourtant tu as l’air de dire que ta solution devrait être beaucoup plus rapide. J’ai pourtant les index dont tu parles (index_pois_on_id & index_pois_on_lonlat (GIST))

Visiblement la longueur de la trace n’influe pas sur la requête ? J’ai effectué un test sur un extrait de trace, avec seulement 2 POIs en sortie et je suis à 12,5 secondes de traitement.

Voilà le explain si ça peut aider

"Sort  (cost=24.25..24.29 rows=15 width=209)"
"  Sort Key: (st_linelocatepoint(tr.path, st_closestpoint(tr.path, (p.lonlat)::geometry)))"
"  ->  Nested Loop  (cost=0.14..23.96 rows=15 width=209)"
"        Join Filter: st_intersects(((geography(st_transform(st_buffer(st_transform(geometry((tr.path)::geography), _st_bestsrid((tr.path)::geography, (tr.path)::geography)), '2000'::double precision), 4326)))::geometry)::geography, p.lonlat)"
"        ->  Index Scan using tracks_pkey on tracks tr  (cost=0.14..8.16 rows=1 width=32)"
"              Index Cond: (id = 1)"
"        ->  Seq Scan on pois p  (cost=0.00..2.46 rows=46 width=201)"

cquest · Décembre 2, 2019, 11:08

Ces temps sont délirants vu le faible nombre de POI que tu as dans ta base de test.

Un EXPLAIN ANALYZE permettra de connaitre le temps exact à chaque étape, et pas uniquement ce que le planner prévoit.