The number of cells along the axes of a grid determines its density: the larger the number, the denser the grid. For example, an 8x8 grid (which produces 64 cells), is denser than a 4x4 grid (which produces 16 cells). Grid density is defined on a per-level basis.

The CREATE SPATIAL INDEX Transact-SQL statement supports a GRIDS clause that enables you to specify different grid densities at different levels. The grid density for a given level is specified by using one of the following keywords:

The default is MEDIUM on all levels.

You can control the decomposition process by specifying nondefault grid densities. For example, different grid densities on different levels might be useful for fine tuning an index based on size of the indexed space and the objects in the spatial column.

Note:
The grid densities of a spatial index are visible in the level_1_grid, level_2_grid, level_3_grid, and level_4_grid columns of the sys.spatial_index_tessellations catalog view.

To limit the number of touched cells that are recorded for an object, the tessellation process applies several tessellation rules. These rules determine the depth of the tessellation process and which of the touched cells are recorded in the index.

These rules are as follows:

• The covering rule
  If the object completely covers a cell, that cell is said to be covered by the object. A covered cell is counted and is not tessellated. This rule applies at all levels of the grid hierarchy. The covering rule simplifies the tessellation process and reduces the amount of data that a spatial index records.
  
• The cells-per-object rule
  This rule enforces the cells-per-object limit, which determines the maximum number of cells that can be counted for each object, except on level 1. At lower levels, the cells-per-object rule controls the amount of information that can be recorded about the object.
  
• The deepest-cell rule
  The deepest-cell rule generates the best approximation of an object by recording only the only bottom-most cells that have been tessellated for the object. Parent cells do not contribute to the cells-per-object count, and they are not recorded in the index.
  

These tessellation rules are applied recursively on each grid level. The rest of this section describes the tessellation rules in more detail.

If an object completely covers a cell, that cell is said to be covered by the object. For example, in the following illustration, one of the second-level cells, 15.11, is completely covered by the middle portion of an octagon.

A covered cell is counted and recorded in the index, and the cell is not tessellated any further.

The extent of tessellation of each object depends primarily on the cells-per-object limit of the spatial index. This limit defines the maximum number of cells that tessellation can count per object. Note, however, that the cells-per-object rule is not enforced for level 1, so it is possible to exceed this limit. If the level-1 count reaches, or exceeds, the cells-per-object limit, no further tessellation occurs at the lower levels.

As long as the count is less than the cells-per-object limit, the tessellation process continues. Starting with the lowest-number touched cell (for example, cell 15.6 in the preceding illustration), the process tests each cell to evaluate whether to count it or tessellate it. If tessellating a cell would exceed the cells-per-object limit, the cell is counted and not tessellated. Otherwise, the cell is tessellated, and the lower-level cells that are touched by the object are counted. The tessellation process continues in this way, breadth-wise, across the level. This process is repeated recursively for the lower-level grids of the tessellated cells until the limit is reached or there are no more cells to count.

For example, consider the preceding illustration, which shows an octagon that fits completely into cell 15 of the level-1 grid. In the figure, cell 15 has been tessellated, dissecting the octagon into nine level-2 cells. This illustration assumes that the cells-per-object limit is 9 or more. If the cells-per-object limit were 8 or less, however, cell 15 would not be tessellated, and only that cell 15 would be counted for the object.

By default, the cells-per-object limit is 16 cells per object, which provides a satisfactory trade-off between space and precision for most spatial indexes. However, the CREATE SPATIAL INDEX Transact-SQL statement supports a CELLS_PER_OBJECT=n clause that enables you to specify a cells-per-object limit between 1 and 8192, inclusive.

Note:
The cells_per_object setting of a spatial index is visible in the sys.spatial_index_tessellations catalog view.

The deepest-cell rule exploits the fact that every lower-level cell belongs to the cell above it: a level-4 cell belongs to a level-3 cell, a level-3 cell belongs to a level-2 cell, and a level-2 cell belongs to a level-1 cell. For example, an object that belongs to cell 1.1.1.1 also belongs to cell 1.1.1, cell 1.1, and cell 1. Knowledge of such cell-hierarchy relationships is built into the query processor. Therefore, only the deepest-level cells need to be recorded in the index, minimizing the information that the index needs to store.

In the following illustration, a relatively small diamond-shaped polygon is tessellated. The index uses the default cells-per-object limit of 16, which is not reached for this small object. Therefore, tessellation continues down to level 4. The polygon resides in the following level-1 through level-3 cells: 4, 4.4, and 4.4.10 and 4.4.14. However, using the deepest-cell rule, the tessellation counts only the twelve level-4 cells: 4.4.10.13-15 and 4.4.14.1-3, 4.4.14.5-7, and 4.4.14.9-11.

Geometry grid tessellation is the default tessellation scheme for the geometry data type, and in SQL Server 2008, it is the only such tessellation scheme. This section discusses aspects of geometry grid tessellation that are relevant to working with spatial indexes: supported methods and bounding boxes.

Note:
You can explicitly specify this tessellation scheme by using the USING GEOMETRY_GRID clause of the CREATE SPATIAL INDEX Transact-SQL statement.

Supported Geometry Methods

The Bounding Box

Geometric data occupies a plane that can be infinite. In SQL Server 2008, however, a spatial index requires a finite space. To establish a finite space for decomposition, the geometry grid tessellation scheme requires a rectangular bounding box. The bounding box is defined by four coordinates, (x-min,y-min) and (x-max,y-max), which are stored as properties of the spatial index. These coordinates represent the following:

• x-min is the x-coordinate of the lower-left corner of the bounding box.
  
• y-min is the y-coordinate of the lower-left corner.
  
• x-max is the x-coordinate of the upper-right corner.
  
• y-max is the y-coordinate of upper-right corner.
  

Note:
These coordinates are specified by the BOUNDING_BOX clause of the CREATE SPATIAL INDEX Transact-SQL statement.

The (x-min,y-min) and (x-max,y-max) coordinates determine the placement and dimensions of the bounding box. The space outside of the bounding box is treated as a single cell that is numbered 0.

The spatial index decomposes the space inside the bounding box. The level-1 grid of the grid hierarchy fills the bounding box. To place a geometric object in the grid hierarchy, the spatial index compares the coordinates of the object to the bounding-box coordinates.

The following illustration shows the points defined by the (x-min,y-min) and (x-max,y-max) coordinates of the bounding box. The top-level of the grid hierarchy is shown as a 4x4 grid. For the purpose of illustration, the lower levels are omitted. The space outside of the bounding box is indicated by a zero (0). Note that object 'A' extends partly beyond the box, and object 'B' lies completely outside the box in cell 0.

A bounding box corresponds to some portion of an application's spatial data. Whether the bounding-box of the index completely contains the data stored in the spatial column, or only contains a portion, is up to the application. Only operations computed on objects that are entirely inside of the bounding box benefit from the spatial index. Therefore, to gain the greatest advantage from a spatial index on a geometry column, you need to specify a bounding-box that contains all or most of the objects.

Note:
The grid densities of a spatial index are visible in the bounding_box_xmin, bounding_box_ymin, bounding_box_xmax, and bounding_box_ymax columns of the sys.spatial_index_tessellations catalog view.

This tessellation scheme applies only to a geography column. This section summarizes the methods that are supported by geography grid tessellation and discusses how geodetic space is projected onto a plane, which is then decomposed into a grid hierarchy.

Note:
You can explicitly specify this tessellation scheme by using the USING GEOGRAPHY_GRID clause of the CREATE SPATIAL INDEX Transact-SQL statement.

Supported Geography Methods

Projection of the Geodetic Space onto a Plane

Computations on geography instances (objects) treat the space containing the objects as a geodetic ellipsoid. To decompose this space, the geography grid tessellation scheme divides the surface of the ellipsoid into its upper and lower hemispheres and then performs the following steps:

1. Projects each hemisphere onto the facets of a quadrilateral pyramid.
   
2. Flattens the two pyramids.
   
3. Joins the flattened pyramids to form a non-Euclidean plane.
   

The following illustration shows a schematic view of the three-step decomposition process. In the pyramids, the dotted lines represent the boundaries of the four facets of each pyramid. Steps 1 and 2 illustrate the geodetic ellipsoid, using a green horizontal line to represent the equatorial longitude line and a series of green vertical lines to represent several latitude lines. Step 1 shows the pyramids being projected over the two hemispheres. Step 2 shows the pyramids being flattened. Step 3 illustrates the flattened pyramids, after they have been combined to form a plane, showing a number of projected longitude lines. Notice that these projected lines are straightened and vary in length, depending on where they fall on the pyramids.

Once the space has been projected onto the plane, the plane is decomposed into the four-level grid hierarchy. Different levels can use different grid densities. The following illustration shows the plane after it has been decomposed into a 4x4 level-1 grid. For the purposes of illustration, the lower-levels of the grid hierarchy are omitted. In actuality, the plane is fully decomposed into a four-level grid hierarchy. After the decomposition process finishes, the geographic data is read, row by row, from the geography column, and the tessellation process is performed for each object in turn.