Pages: 1
- Sujet précédent - Lenteur - Calculer plus courte distance entre deux points - Sujet suivant
#1 Thu 02 April 2020 22:44
- preliator
- Participant assidu
- Date d'inscription: 17 Nov 2018
- Messages: 433
Lenteur - Calculer plus courte distance entre deux points
Bonjour à tous,
Je dispose d'une couche de points assez conséquente (un peu plus de 1 million), et je voudrais sélectionner la plus courte distance séparant chaque point de cette même couche à un autre (plus proche voisin). Après quelques recherches sur internet, je me suis tourné vers la clause Cross Join Lateral.
Cependant, la requête ne se termine jamais (plus de 5h sans finalisation). J'ai comparé avec la Matrice des distances de QGis, et là le temps de calcul semble être bien plus rapide (environs 10% toute les 5 minutes). Je me dit que la cause se trouve peut être dans la requête mal formulée.
Voici la requête que j'ai utilisé :
Code:
with couche_points as (select * from public.centroides_batis_all) select p.id, t.id_2, t.dist from couche_points p cross join lateral( select r.id as id_2, p.geom <-> r.geom as dist from couche_points r where p.id <> r.id order by p.geom <-> r.geom limit 1) as t
Pourtant, tout m'a l'air bon. Existe t-il une différence de performance entre PostGis et QGis ?
Merci à vous.
Hors ligne
#2 Fri 03 April 2020 11:59
- Nicolas Ribot
- Membre
- Lieu: Toulouse
- Date d'inscription: 9 Sep 2005
- Messages: 1554
Re: Lenteur - Calculer plus courte distance entre deux points
Bonjour,
• Le premier with ne sert a rien, autant référencer centroides_batis_all dans la requête principale.
• Existe-t-il un index geo sur la colonne geom de la table ? (et analyze lancé apres la création de l'index)
• Mettez plutot WHERE p.id < r.id: ca permet de ne tester qu'une combinaison A-B, au lieu de tester A-B et B-A, comme c'est fait avec p.id <> r.id
Avec index, sur 1M de points, ca doit etre très rapide sur postgis. (qq sec au plus)
(120s sur un test de 1M de centroids de parcelles)
Nicolas
Dernière modification par Nicolas Ribot (Fri 03 April 2020 12:12)
En ligne
#3 Fri 03 April 2020 12:23
- Nicolas Ribot
- Membre
- Lieu: Toulouse
- Date d'inscription: 9 Sep 2005
- Messages: 1554
Re: Lenteur - Calculer plus courte distance entre deux points
Bonjour à tous,
Pourtant, tout m'a l'air bon. Existe t-il une différence de performance entre PostGis et QGis ?
Merci à vous.
Postgis et QGIS ont chacun leurs algorithmes pour le traitement géo. Donc oui, il peut exister de grosses différences de perf suivant les opérations spatiales.
Pour certaines d'entre elles, QGIS se sert de GEOS (a travers ogr par exemple). GEOS est une bibliothèque spatiale qui est aussi utilisée dans PostGIS.
Même dans ce cas, il peut y avoir des différences notables de perf pour la même opération.
Nico
En ligne
#4 Fri 03 April 2020 12:34
- preliator
- Participant assidu
- Date d'inscription: 17 Nov 2018
- Messages: 433
Re: Lenteur - Calculer plus courte distance entre deux points
Merci pour votre réponse ! Effectivement, en ajoutant un index et en modifiant "p.id < r.id", ça a marché.
Code:
CREATE INDEX index_maisons ON centroides_batis_all USING GIST (geom); select p.id, t.id_2, t.dist from centroides_batis_all p cross join lateral( select r.id as id_2, p.geom <-> r.geom as dist from centroides_batis_all r where p.id < r.id order by p.geom <-> r.geom limit 1) as t
Mais ça m'a quand même pris 16 minutes ... peut être que ma machine atteint ses limites ? (J'ai un processeur de presque 9 ans, et 16 Gb de Ram).
Hors ligne
#5 Fri 03 April 2020 13:45
- Nicolas Ribot
- Membre
- Lieu: Toulouse
- Date d'inscription: 9 Sep 2005
- Messages: 1554
Re: Lenteur - Calculer plus courte distance entre deux points
Merci pour votre réponse ! Effectivement, en ajoutant un index et en modifiant "p.id < r.id", ça a marché.
Mais ça m'a quand même pris 16 minutes ... peut être que ma machine atteint ses limites ? (J'ai un processeur de presque 9 ans, et 16 Gb de Ram).
Quelle est la ram allouée à PG ? la base a été réglée pour la machine, ou c'est la conf par défaut qui est active ?
(show shared_buffers)
Les disques aussi ont leur importance (surtout lors du premier accès aux données, pour les mettre en ram). la bd est sur un disque dédié, rapide, ou sur le meme disque que l'OS ?
avez-vous lancé un analyze <table> apres la création de l'index géo ?
Nicolas
En ligne
#6 Fri 03 April 2020 15:52
- preliator
- Participant assidu
- Date d'inscription: 17 Nov 2018
- Messages: 433
Re: Lenteur - Calculer plus courte distance entre deux points
Je n'avais pas connaissance de ces paramètres. Tout est mis par défaut, lors de l'installation.
En faisant "show shared_buffers", la valeur renvoyée est 128 mb. Est-il possible de monter cette valeur ? D'après internet, je ne dois pas dépasser 512MB.
Je n'ai pas non plus lancé l'analyze après la création de l'index. Je l'ai lancé à l'instant (j'ai tenté de créer l'index spatial, maos il existe déjà), et ça m'a affiché "ANALYZE".
Merci.
Dernière modification par preliator (Fri 03 April 2020 16:02)
Hors ligne
#7 Fri 03 April 2020 17:05
- Nicolas Ribot
- Membre
- Lieu: Toulouse
- Date d'inscription: 9 Sep 2005
- Messages: 1554
Re: Lenteur - Calculer plus courte distance entre deux points
Je vous recommande la lecture de la doc sur la conf postgresql: peu de paramètres a changer, mais certains ont une grande influence (https://www.postgresql.org/docs/9.6/run … ource.html).
Si, bien sur, on peut mettre beaucoup de 512 MB aux shared buffers ! Heureusement d'ailleurs: cette mémoire est celle qui stocke les données pendant une requête.
Juste pour rire, la conf du serveur LeBonCoin, PostgreSQL, en 2012:
max_connections = 600
shared_buffers = 130 Gb
effective_cache_size = 750 Gb
work_mem = 24 Mb
random_page_cost = 2
(https://www.postgresql.fr/temoignages/le_bon_coin)
Il y a des sites en ligne qui permettent de tuner un peu son serveur en fonction de ses usages (ici par exemple: https://pgtune.leopard.in.ua/#/)
Si votre serveur ne fait quasiment que du PG, vous pouvez mettre 1/4 à 1/3 de la ram pour les shared_buffers.
Nicolas
En ligne
#8 Fri 03 April 2020 17:06
- preliator
- Participant assidu
- Date d'inscription: 17 Nov 2018
- Messages: 433
Re: Lenteur - Calculer plus courte distance entre deux points
Merci beaucoup pour ces informations
Hors ligne
#9 Sat 04 April 2020 07:52
- Theos2000
- Participant assidu
- Date d'inscription: 15 Jun 2015
- Messages: 221
Re: Lenteur - Calculer plus courte distance entre deux points
J'ai utilisé récemment PGTunes (https://pgtune.leopard.in.ua/#/) qui permet de configurer des paramètres assez important dans le fichier postgresql.conf. Par contre faite une sauvegarde de ce fichier avant toute modification et bien penser a arrêter le "service" postgresql avant toute modification et le redémarrer par la suite avant de lancer l'interface de commande
Hors ligne
#10 Sat 04 April 2020 13:11
- tumasgiu
- Membre
- Lieu: Ajaccio
- Date d'inscription: 5 Jul 2010
- Messages: 1160
Re: Lenteur - Calculer plus courte distance entre deux points
Salut,
Je pense qu'il y aurait deux moyens d’accélérer votre requête,
sans considération de matériel et de tuning, qui sont bien sûr tres importants:
1) L'organisation de vos données.
Vos données (lignes de bdd) sont organisées en une multitude de fichiers,
que PostgreSQL appelle des "pages".
Un index consiste à indiquer au moteur sur quelle page se trouve (probablement) une donnée
basée sur une de ses propriétés.
Chaque page indiquée par l'index doit être scannée entièrement pour trouver les lignes correspondantes.
Plus les lignes concernées par l'index sont éparpillées sur un nombre important de page,
plus longue sera votre requête, car il faudra autant de lectures de page.
Vous avez donc tout intérêt à ce que les données soient organisées à l'intérieur de ces fichiers selon un ordre
précis, de manière à minimiser le nombre de page à lire.
Vous avez à votre disposition la commande CLUSTER, qui permet de réorganiser les lignes selon un index ou une fonction.
2) La sous requête utilisant l'operateur de knn.
Je ne crois pas que sous cette forme votre requête tire parti de l'index, puisqu'aucune des opérandes de <-> n'est une constante,
cf. la doc :
Index only kicks in if one of the geometries is a constant (not in a subquery/cte). e.g. 'SRID=3005;POINT(1011102 450541)'::geometry instead of a.geom
Pour vous en assurer vous pouvez lancer votre requête avec EXPLAIN.
[EDIT] après avoir testé, en fait si l'index fonctionne bien ! [/EDIT]
Votre requête liste actuellement tout les voisins de chaque points et les ordonne par distance.
Vous pourriez restreindre la recherche avec un buffer, cela réduira le nombre de ligne à tester,
et déclenchera sans doute l'utilisation de l'index :
Code:
select p.id, t.id_2, t.dist from centroides_batis_all p cross join lateral( select r.id as id_2, p.geom <-> r.geom as dist from centroides_batis_all r where p.id < r.id AND st_dwithin(p.geom, r.geom, TAILLE_DU_BUFFER) order by p.geom <-> r.geom limit 1) as t
Évidemment il faut déterminer la taille du buffer de façon à ce que chaque point
puisse avoir un plus proche voisin. Cela dépends de la distribution géographique
de vos points.
Ensuite, est ce que vos données a vocation à évoluer souvent ?
votre requête est elle exécutée un grand nombre de fois ?
Si la réponse à la première question est non et à la seconde est oui,
alors rien ne vous empêche de créer une colonne identifiant le plus proche voisin
de chaque ligne, ou alors peut être une vue matérialisée.
Vous échangez du temps de calcul contre un peu d'espace disque, ce qui
est un choix qui se fait assez souvent en informatique.
Dernière modification par tumasgiu (Sat 04 April 2020 14:04)
Hors ligne
#11 Sat 04 April 2020 13:34
- Nicolas Ribot
- Membre
- Lieu: Toulouse
- Date d'inscription: 9 Sep 2005
- Messages: 1554
Re: Lenteur - Calculer plus courte distance entre deux points
Hello !
Je crois que c'est plutot la commande CLUSTER TABLE (https://www.postgresql.org/docs/12/sql-cluster.html) qui permet de réorganiser les données de la table en suivant l'ordre d'un index: lors de l'appel a l'index, les données qu'il faut aller chercher dans la table sont alors ordonnées physiquement comme l'index => plus rapide a aller chercher (surtout sur des disques mécaniques ou la localisation physique des données sur le disque est importante pour la perf).
Lors de la création, un index est écrit dans le bon ordre par défaut (ordre naturel de l'operateur d'index).
REINDEX est surtout utile lorsque l'index est cassé, ou que la table a subit de nombreuses modifs (insert/update/delete).
L'opérateur distance <-> déclenche bien l'usage des index, meme dans le cas d'un self join. (la partie lateral rendant un des champs constant vis a vis de l'index, je crois).
C'est bien l'intéret de ce "nouvel" opérateur dans PostGIS. Il évite d'utiliser des distances ou buffers, qui par nature ne permettent pas de trouver une réponse exacte: il y a aura tjs un dataset dans lequel la distance min entre deux objets est supérieure au buffer qu'on utilise. Et si on utilise un trop gros buffer, l'index n'est plus selectif et donc inutile.
Le plan de la requête KNN:
Code:
QUERY PLAN Nested Loop (cost=0.29..571924.24 rows=1000000 width=48) (actual time=0.275..125458.410 rows=999999 loops=1) Output: p.id, r.id, ((p.geom <-> r.geom)), st_makeline(p.geom, r.geom) Buffers: shared hit=15148569 -> Seq Scan on work_nico.testpt p (cost=0.00..18264.00 rows=1000000 width=36) (actual time=0.011..88.278 rows=1000000 loops=1) Output: p.geom, p.id Buffers: shared hit=8264 -> Limit (cost=0.29..0.53 rows=1 width=44) (actual time=0.124..0.124 rows=1 loops=1000000) Output: r.id, ((p.geom <-> r.geom)), r.geom Buffers: shared hit=15140305 -> Index Scan using testpt_geom_gist on work_nico.testpt r (cost=0.29..82053.62 rows=333333 width=44) (actual time=0.124..0.124 rows=1 loops=1000000) Output: r.id, (p.geom <-> r.geom), r.geom Order By: (r.geom <-> p.geom) Filter: (p.id < r.id) Rows Removed by Filter: 11 Buffers: shared hit=15140305 Planning time: 0.350 ms Execution time: 125517.935 ms
(la meme requete, sur 10000 lignes au lieu de 1M, sans index, prend deja 33s)
Nico
En ligne
#12 Sat 04 April 2020 13:34
- Nicolas Ribot
- Membre
- Lieu: Toulouse
- Date d'inscription: 9 Sep 2005
- Messages: 1554
Re: Lenteur - Calculer plus courte distance entre deux points
Ah je vois que tu viens de corriger REINDEX/CLUSTER...
sorry pour le bruit...
En ligne
#13 Sat 04 April 2020 13:44
- Nicolas Ribot
- Membre
- Lieu: Toulouse
- Date d'inscription: 9 Sep 2005
- Messages: 1554
Re: Lenteur - Calculer plus courte distance entre deux points
Avec 128 Mo de ram, il se peut que toutes les données ne tiennent pas en mémoire, PG doit alors les stocker dans des fichiers tmp et les traiter par lot.
La volumétrie de ma table de test (1M de lignes), avec index geo:
Code:
select pg_size_pretty(pg_total_relation_size('work_nico.testpt')) as tot_size, pg_size_pretty(pg_relation_size('work_nico.testpt')) as rel_size, pg_size_pretty(pg_indexes_size('work_nico.testpt')) as indexes_size; tot_size rel_size indexes_size 142 MB 65 MB 77 MB
Où l'index est plus volumineux que les data elles-mêmes
(un exemple plus extreme: la table osm_polygon france, avec index sur tous les champs: index 3.5x plus gros que les data !
tot_size rel_size indexes_size
98 GB 22 GB 76 GB
)
Nico
En ligne
#14 Sat 04 April 2020 13:57
- preliator
- Participant assidu
- Date d'inscription: 17 Nov 2018
- Messages: 433
Re: Lenteur - Calculer plus courte distance entre deux points
Un grand merci pour toute vos informations
Hors ligne
#15 Sat 04 April 2020 14:00
- tumasgiu
- Membre
- Lieu: Ajaccio
- Date d'inscription: 5 Jul 2010
- Messages: 1160
Re: Lenteur - Calculer plus courte distance entre deux points
Ah je vois que tu viens de corriger REINDEX/CLUSTER...
sorry pour le bruit...
Non, non, c'était intéressant
Oui j'ai corrigé la mauvaise commande et la mauvaise information sur l'utilisation de l'index.
REINDEX concerne en effet la reconstruction d'index corrompus ou bloatés.
Pour l'opérateur <->, la doc m'a un peu induit en erreur, je pense qu'elle devrait être un peu
plus explicite, non ?
(la partie lateral rendant un des champs constant vis a vis de l'index, je crois).
C'est la réflexion que je me suis faite après avoir écrit mon message, j'étais pas vraiment sur et j'ai fait un test,
dans un premier temps avec 1G points, j'ai vite abandonné en attendant la construction de l'index :p,
pour me borner a 1M.
L'utilisation du buffer permet tout de même de réduire le temps d’exécution ( ~4 fois moins dans mon test ), mais cela peut être au prix
de l'exhaustivité. Tout dépends du cas d'utilisation je dirais.
Dernière modification par tumasgiu (Sat 04 April 2020 14:01)
Hors ligne
Pages: 1
- Sujet précédent - Lenteur - Calculer plus courte distance entre deux points - Sujet suivant