Le jour où j’ai découvert les cellules spatiales
10/09/2015
remy

Lors de notre soirée mensuelle des Jedis d'EXPACEO, Cédric nous a fait part de son expérience en cellules spatiales au détour d’une problématique rencontrée en clientèle.

N’ayant pas encore de client dans l’aéronautique, nous étions tous curieux de comprendre de quoi il pourrait bien retourner avec un plan contenant des titres comme « De quoi parle-t-on ? » (Bonne question !), « Le jour où Microsoft a confondu les + et les –. » ou pire … « Comment sont nées les cellules ? ».

Le mystère fût levé : point de science-fiction ou de sciences naturelles, il s’agit bien évidemment de la gestion des index spatiaux sous SQL Server !

Au-delà de la whatthefuckitude assumée, Cédric nous a réexpliqué les bases d’un index B-Tree en SQL Server : à savoir que cet index B-Tree n’est pas un vrai B-Tree mais qu’il est en fait un B+Tree, restant pour autant linéaire.

Oui je sais, c’est subtil mais en même temps, il fallait venir.

D’où cette question qui nous interpelle tous (mais si) : comment SQL Server arrive à stocker des informations qui sont par nature en 2 dimensions (coordonnées GPS) dans un index qui n’en dispose que d’une seule ?

The Hierarchical Uniform Decomposition of Space : ou l’art d’aplanir un Rubik’s Cube

L’index spatial SQL Server est découpé sous forme d’une succession de 4 grilles. Pour affiner la précision des données géographiques que l’on stock dans l’index, on peut dimensionner indépendamment ces grilles d’une résolution de 4x4 à 16x16. En 4x4, la grille contiendra 16 segments qui pointeront chacun vers une sous-grille. On peut ainsi aller d’une résolution de 65536 cellules (16*16*16*16) à 4,3 milliards de cellules (256*256*256*256).

Maintenant, plus ma précision est grande et plus j’augmente mes chances que ma donnée ne tienne plus dans une seule cellule sur mes grilles bas niveau. C’est là où est mis en œuvre le principe de facettisation, ou tesselation :

Vous trouverez la représentation de la variation de la courbe de remplissage de l’espace d’Hilbert au verso de cette page html

Si je devais vous le résumer, ce que je ne ferais pas, je vous dirais qu’une fois aplanie, une donnée est répartie entre un certain nombre de cellules (CELLS_PER_OBJECT). Pour autant, ce nombre de cellules n’est pas illimité et doit être encadré : un objet ne peut dépasser 8192 cellules mais en pratique, on voudra limiter cet espace à 8 ou 16 cellules à des fins d’espace de stockage.

Pour retrouver ses billes, SQL Server aplani la donnée en suivant trois règles en fonction de la précision demandée (CELLS_PER_OBJECT) au moment de la création de l’index : Covering, Cells-Per-Object, Deepest-Cell.

Je ne vous ferez bien-évidemment pas l’affront de rentrer dans le détail de ces règles que nous maitrisons tous à la perfection…

J’avoue me poser la même question

Et c’est enfin que Cédric nous a exprimé cette vérité universelle : plus on est gros et plus on est lent. A tel point que SQL Server est parfaitement capable de ne pas vouloir utiliser votre gros et gras (mais précis !) index spatial au profit d’un bon vieux table scan propre sur lui.

Et c’est là toute la beauté de ce fabuleux outil qu’est une base de données : vous pouvez passer des semaines à lui demander de faire une chose à votre façon, elle n’en fera toujours qu’à sa tête. C’est son côté féminin !

 

Si vous vous posez la question de savoir ce que sont les Jedis d'EXPACEO, voici quelques photos de la soirée. Merci aux présents et un grand merci à Cédric pour sa présentation !

Ambiance studieuse d’avant présentation

Un teasing bien WTF

Tesselation, travaux pratiques : sur combiens de cellules est réparti le cul d’une bouteille de bière ?