Recette
#12 |
|
Février 2011 |
Le problème
|
Tuscan Local Council |
Tuscan County |
Neighbour LC |
County |
Région |
ANGHIARI |
AREZZO |
CITERNA |
PERUGIA |
UMBRIA |
AREZZO |
AREZZO |
MONTE SANTA MARIA TIBERINA |
PERUGIA |
UMBRIA |
BIBBIENA |
AREZZO |
BAGNO DI ROMAGNA |
FORLI' - CESENA |
EMILIA-ROMAGNA |
CHIUSI DELLA VERNA |
AREZZO |
BAGNO DI ROMAGNA |
FORLI' - CESENA |
EMILIA-ROMAGNA |
CHIUSI DELLA VERNA |
AREZZO |
VERGHERETO |
FORLI' - CESENA |
EMILIA-ROMAGNA |
... |
... |
... |
... |
... |
SELECT lc1.lc_name AS
"Local Council", |
Cette première requête est simple:
la fonction ST_Touches(geom1, geom2) évalue la relation spatiale existant entre chaque couple de Local Councils.
la table local_council
est scannée deux fois, afin de réaliser la jointure;
En
d'autres mots, cette requête permet d'évaluer chaque Local Council
à un autre, de manière permutative.
On doit mettre en place deux alias (AS lc1 / AS lc2) pour identifier de façon non ambiguë les Local Councils.
Cependant, une approche aussi simpliste implique plusieurs problèmes:
cette requête va sûrement
retourner un résultat correct: mais le temps de calcul sera
long.
[trop long].
l'explication est relativement simple: l'évaluation ST_Touches() implique un grand nombre de calculs complexes, et représente une étape très lourde
logiquement on devrait répéter cette opération sur les millions de couples possibles.
conclusion: répéter des millions de fois une grosse opération aboutit à une requête extrêmement lente !
SELECT lc1.lc_name AS
"Local Council", |
Heureusement, on peut réaliser ces requêtes spatiales d'une manière plus rapide et efficace:
on va utiliser l'Index Spatial [aka R*Tree]
cela va rajouter de la complexité à notre code SQL, mais permettra un gain de temps non négligeable.
Comment ça marche: le R*Tree est scanné dans un premier temps, afin d'évaluer le Minimum Bounding Rectangles [MBRs] des deux géométries:
cette étape s'effectue très rapidement, et permet d'écarter de nombreux couples pour qui ont est sûr qu'ils ne partagent pas une limite commune.
Ainsi, le nombre d'opérations impliquant ST_Touches() sera frottement réduit.
Tout ceci réduit grandement le temps de calcul global.
Au niveau syntaxique, l'utilisation de l'index spatial nécessite simplement l'utilisation d'une sous requête:
L' Index Spatial R*Tree est stocké dans une table séparée.
les noms des tables sont étroitement liés: l'Index Spatial correspondant à la table myTbl et à la colonne géométrique myGeom se nomme idx_myTbl_myGeom.
la clause MATCH RTreeIntersects() est utilisée afin de sélectionner rapidement toute géométrie intéressante, en évaluant simplement son MBR.
MbrMinX() etc... sont utilisés afin d'identifier les points extrêmes du MBR filtré.
Voici ce qui se passe étape par étape:
un élément Géométrique est choisi dans la première instance de la table local_councils (lc1.geometry)
Puis l'index spatial R*Tree est scanné afin d'identifier tous les objets géométriques de la deuxième instance de la table local_councils ( lc2.geometry)
Seuls les objets satisfaisant la contrainte (intersection des MBR) seront sélectionnes via l'Index Spatial.
enfin, ST_Touches() sera évalué: mais uniquement sur les objets pré-filtrés.
SELECT lc1.lc_name AS
"Tuscan Local Council", |
Bien, maintenant que nous avons résolu le sujet de l'Index
Spatial, la réécriture de la requête ne pose plus de problèmes
Etant donné qu'il s'agit d'une requète complexe, des
informations supplémentaires ne vous feront pas de mal:
on a réaliser deux JOINtures: une entre local_councils et counties, et une autre entre counties et regions
Etant donné que l'on a utilisé deux instances de la table local_councils, il faut réaliser une jointure pour chaque instance
le paramètre r1.region_name LIKE 'toscana' permet de focaliser la recherche de voisins sur la TOSCANE (region).
le paramètre r1.region_id <> r2.region_id permet de s'assurer que seuls les Local Councils non TOSCANs seront pris en compte pour l'évaluation des voisins.
seuls les Local Councils Toscans ayant une limite voisine avec un Local Council non Toscans vont être sélectionnés avec cette requête
SELECT lc1.lc_name AS
"Tuscan Local Council", |
Même requête, mais avec une syntaxe de JOINture différente.
Réaliser des analyses spatiales n'est pas toujours une tâche
facile. |
|
Author: Alessandro Furieri a.furieri@lqt.it |
This work is licensed under the Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) license. |
|
|
|
Permission is granted to copy, distribute and/or modify this
document under the terms of the |