banniere

Le portail francophone de la géomatique


Toujours pas inscrit ? Mot de passe oublié ?
Nom d'utilisateur    Mot de passe              Toujours pas inscrit ?   Mot de passe oublié ?

Annonce

Rencontres QGIS 2025

L'appel à participation est ouvert jusqu'au 19 janvier 2025!

#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)

Hors 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

preliator a écrit:

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

Hors 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

preliator a écrit:

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

Hors 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

Hors 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 smile

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

Hors 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...

Hors 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 big_smile

(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

Hors 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 smile

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 smile

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

 

Pied de page des forums

Powered by FluxBB