Les index spatiaux dans SQL Server 2012 / SQL Azure

Depuis SQL Server 2008, les données spatiales sont des types de premier ordre dans SQL Server. J’ai eu l’occasion de manipuler ces types sur plusieurs projets. Plus récemment, j’ai rencontré un problème de performance sur des requêtes faisant intervenir des données spatiales. L’occasion de creuser un peu plus les index spatiaux :).

Prenons un exemple, nous voulons connaître l’ensemble des routes qui croisent la ligne du nouveau TGV Nice-Brest (oui, c’est bien une ligne de TGV fictive :) ) :

Quand nous exécutons cette requête, SQL Server va devoir parcourir l’ensemble des lignes de la table Routes et, pour chacune des lignes, appeler la méthode STIntersects() pour savoir si il y a bien une intersection entre l’objet courant et @TraceLigneTGV.

Pour comparer l’intersection de deux rectangles, cela nécessite au maximum 32 comparaisons. Je n’ai parlé ici que de deux rectangles. Si on prend trois rectangles, on passe à 96 (32 x 3) comparaisons. Imaginez le nombre de comparaisons pour l’ensemble des segments de droites composant l’ensemble des routes de France…

A noter que cet algorithme est un des plus simples pour l’intersection de rectangles simples. Il existe également un autre algorithme basé sur les centres et les rayons des rectangles. Lignes, polygones et les autres opérations géométriques ont leur propres algorithmes, un peu plus complexes, mais beaucoup plus efficaces. Cet exemple n’est là que pour montrer la complexité de telles opérations…et ainsi l’intérêt du système d’index. Si on reprend notre exemple, on se doute qu’effectuer toutes ces comparaisons pour l’ensemble des routes ne peut pas être efficace. De plus, n’importe quel humain se doute que la route Toulouse-Bayonne ne traversera pas la ligne de TGV Nice-Brest. La route Paris-Strasbourg non plus. On sait donc intuitivement qu’il y a des zones qui ne peuvent contenir que des lignes à exclure de notre résultat. Il faudrait donc arriver à créer un découpage suffisamment efficace et pertinent pour nous aider à exclure les objets géométriques que l’on sait par avance non pertinent pour notre requête.

On entrevoit alors une solution intéressante :

Avec l’arrivé des types geometry et geography, un nouveau type d’index est arrivé, le spatial index. Quand cet index existe sur une colonne de type spatial, c’est cet index qui est utilisé comme filtre primaire. Il retourne donc un set d’enregistrements plus affiné au filtre secondaire, qui – bien qu’il soit lent- retourne le résultat plus rapidement, ayant moins de résultats en entrée à analyser. Si il n’y a pas d’index, le filtre primaire est bypassé, et le filtre secondaire est exécuté sur l’ensemble du data set.

Vous savez peut-être que SQL Server organise ses index sous forme d’arbre B (B-tree). C’est un stockage de données sous une forme triée et permettant une exécution des opérations d’insertion et de suppression en temps amorti logarithmique… En clair, les données sont stockées sous une forme triée spécifique qui permet à chaque noeud de contenir plusieurs clés, et de limiter les opérations d’équilibrage de l’arbre à l’ajout ou la suppression d’éléments.

Il faut donc, pour cela pouvoir organiser l’ensemble de nos éléments en plages à plusieurs niveaux. Là aussi, avoir ce principe est très simple avec des nombres (1-200, contenant des sous-groupes 1-50,51-100,101-150,151-200), mais bien plus complexe avec des formes géométriques/géographiques.

Ainsi, l’objet en orange est situé dans les cellules 2-Niveau1, 3-Niveau2. Si l’on souhaite répondre à la question “Est-ce que l’objet vert est en intersection avec l’objet orange?” Il suffit de lire le premier niveau d’index pour obtenir la réponse.

L’index spatial dans SQL Server peut avoir 3 différentes densités : (4x4 – 16 cases), Medium (8x8 – 64 cases) ou High (16x16 – 256 cases). Il est donc possible d’augmenter la résolution de la grille. Ce faisant, plus la résolution sera importante, plus la taille de l’index – et donc son coût en création et maintenance – sera important.

En dehors de la précision, l’index géographique a une autre caractéristique essentielle : il est composé de 4 niveaux. Ce nombre est fixe, mais il est possible d’ajuster la finesse de la grille séparément pour chacun des niveaux : par défaut à Medium. Si on reprend notre réflexion sur les routes et le trajet TGV, on pourrait imaginer avoir la France découpée tout d’abord à 16 cases, puis en 64 cases (grosso modo équivalentes à un demi-département). En ajustant ainsi l’index, cela nous permet d’exclure plus de la moitié des routes seulement en lisant l’index de premier niveau. A noter que si les 4 niveaux sont avec une résolution de grille à Medium, cela représente tout de même 64 puissance 4 : 16,7 Million de cellules.

Ce nombre est important, mais la répartition l’est tout autant. Ainsi un index défini avec les résolutions HMMM et MMMH produisent le même nombre de cellules, mais que le résultat ainsi que leurs performances sont sensiblement différents. C’est à vous – en fonction de vos données et de leur répartition – de choisir et d’ajuster ces paramètres.

Ce processus peut être complexe, et là également, des règles ont été posées pour limiter le temps d’exécution de ce processus :

Hormis l’anecdote, cela a une importance plus ou moins majeure par rapport à SQL Server. Est-ce que vos données et traitement utilisent l’altitude ? Avez-vous besoin d’une précision inférieure à 1 mètre ? Si oui, alors, vous devrez certainement vous soucier du SRID. En effet, il existe de nombreux référentiels spatiaux (plus de 4000), qui apportent de précisions différentes, soit sur la terre entière, soit sur des portions spécifiques de la Terre.

  Les projections sont donc indispensables pour effectuer des calculs et des recherches sur les type géographiques. SQL Server réalise pour nous cette projection, au besoin. Celle-ci est déterminée par le SRID des objets géographiques. Si le sujet des projections vous intéresse, je vous conseille la lecture de l’article Flat maps for a Round planet sur MSDN.

Pour les types géographiques, seules trois méthodes sont supportées : STIntersects(), STEquals() et STDistance(). Comme l’explique la documentation, ces méthodes doivent être utilisées dans la clause WHERE pour pouvoir utiliser l’index.

Les types géométriques nous laissent un peu plus de possibilités, en supportant STContains(), STDistance(), STEquals(), STIntersects(), STOverlaps(), STTouches() et STWithin(). En plus de l’utilisation dans une clause WHERE, vous pouvez également utiliser ces méthodes dans les clauses JOIN ON.

Les limites des index spatiaux sont également très liés à leur configuration : résolution des grilles, zone englobante, etc…

La documentation officielle n’explicite pas beaucoup plus de restrictions sur les index spatiaux.

Comme nous l’avons déjà vu, la résolution des différentes grilles est également un point très important, et souvent négligé. Je n’ai pas de recettes magique pour trouver automatiquement les résolutions adaptées à vos données et à vos requêtes…à part du travail et de la réflexion :).

Et n’oubliez pas que les requêtes spatiales sont avant tout des requêtes. Vous savez déjà comment les optimiser ;).