Spatial Indexing

When to use a Spatial Index?

Spatial indexes improve significantly the performance of certain type of spatial relationship queries but they don’t have an impact on all spatial functions so it is certainly a good idea to choose wisely when and what to index. Geography data types benefit for the following queries from a spatial index:

• geography1.STIntersects(geography2)
• geography1.STEquals(geography2)
• geography1.STDistance(geography2)
• geography1.STDistance(geography2)

Geometry data types on the other side can make use of spatial indexes for the following functions:

• geometry1.STContains(geometry2)
• geometry1.STDistance(geometry2)
• geometry1.STDistance(geometry2)
• geometry1.STEquals(geometry2)
• geometry1.STIntersects(geometry2)
• geometry1. STOverlaps (geometry2)
• geometry1.STTouches(geometry2)
• geometry1.STWithin(geometry2)

What exactly is a Spatial Index?

The spatial index in SQL Server 2008 is organized as a B-tree index which means the spatial data are represented in the linear order of a B-tree. The number of cells in X- and Y-direction is always the same and can be 4 x 4 for LOW grid density, 8 x 8 for MEDIUM grid density or 16 x 16 for a HIGH grid density. There are 4 indexing levels and a grid density can be set for each individual level.

The SQL Server uses a tessellation algorithm to dissect the spatial objects into cells. During this process it uses the following rules:

• Cells are numbered from within a level from left to right and from top to bottom
• As soon as a cell is entirely covered by the spatial objects for this cell the tessellation will abort for this particular cell. In the example below we have a hexagon in cell 4 on level 1. In level 2 this hexagon completely covers cell 7. Further tessellation for this cell, which is then globally addressed as 4.7 is not necessary. The other cells, which are partly covered by the spatial object will be further tessellated in the subsequent levels.
• While creating the spatial index we define how many cells per object we want to have as a maximum. As soon as this is limit is reached or exceeded no further levels will be tessellated.
• The index only contains the deepest cell. In the example below we have an object which is amongst others covered by the cell 4.4.4.7. Form this information we can deduct that it is also covered by the cells 4.4.4 in level 3, 4.4 in level 2 and 4 in level 1. Thus it will not be necessary to store the information for lower levels in the index.
  

The tessellation itself works different for geography and geometry data types. Geometries are projected to the “flat-earth” and thus we can further restrict the indexing area by defining the minimum bounding rectangle which is basically an envelope around all our geometries.

For geography data types this is not necessary. Here we have a projection from the “round earth” to a flat object as described below. Basically we project the “round earth” on 2 pyramids, flatten these pyramids and then start the tessellation. As a result we have a restriction that a spatial object must be fully located in a single, logical hemisphere.

How to Create a Spatial Index

To create a spatial index we need to have a clustered primary key on a non-spatial column in the database table (such as on an “id” field). The spatial index itself is created with the following SQL-statement for a geometry:

CREATE SPATIAL INDEX SI_AddressPoint
  ON AddressPoint(Geom)
  USING GEOMETRY_GRID
  WITH (
    BOUNDING_BOX = (xmin=-4.2, ymin=50.3, xmax=-4.1, ymax=50.4),
    GRIDS = (LEVEL_1 = LOW, 
             LEVEL_2 = LOW, 
             LEVEL_3 = HIGH, 
             LEVEL_4 = HIGH),
             CELLS_PER_OBJECT = 16)

For a geography the syntax is slightly different and as mentioned above we do not need a BOUNDING_BOX:

CREATE SPATIAL INDEX SI_AddressPoint
  ON AddressPoint(Geom)
  USING GEOGRAPHY_GRID
  WITH (
    GRIDS = (LEVEL_1 = LOW, 
             LEVEL_2 = LOW, 
             LEVEL_3 = HIGH, 
             LEVEL_4 = HIGH),
             CELLS_PER_OBJECT = 16)

The SQL-statement can also be declared with graphical support through the SQL Server Management Studio. When you are in the design view of a table, right-click on the row for the spatial column and select “Spatial Indexes” from the context menu.

You will now find a dialogue which allows you to configure the index.