User's Guide and Reference

How a spatial index is generated

A spatial index is generated using envelopes. The envelope is a geometry itself and represents the minimum and maximum X and Y extent of a geometry. For most geometries, the envelope is a box, but for horizontal and vertical linestrings the envelope is a two-point linestring. For points, the envelope is the point itself. For more information about envelopes, see Envelope.

The spatial index is constructed on a spatial column by making one or more entries for the intersections of each geometry's envelope with the grid. An intersection is recorded as the internal ID of the geometry and minimum X and Y coordinates of the grid cell intersected. For example, the polygon in Figure 7 intersects the grid on coordinates (20,30), (30,30), (40,30), (20,40), (30,40), (40,40), (20,50), (30,50), and (40,50). See Table 38 for minimum X and Y coordinates for all the geometries in Figure 7.

If multiple grid levels exist, DB2 Spatial Extender attempts to use the lowest grid level possible. When a geometry has intersected four or more grid cells at a given level, it is promoted to the next higher level. Therefore, a spatial index that has the three grid levels of 10.0e0, 100.0e0, and 1000.0e0, DB2 Spatial Extender will first intersect each geometry with the level 10.0e0 grid. If a geometry intersects with four or more 10.0e0 grid cells, it is promoted and intersected with the level 100.0e0 grid. If four or more intersections result at the 100.0e0 level, the geometry is promoted to the 1000.0e0 level. At the 1000.0e0 level, the intersections must be entered into the spatial index because this is the highest possible level.

Figure 7 illustrates how four different types of geometries intersect a 10.0e grid. All 23 intersections for the four geometries are recorded in the spatial index.

Figure 7. Application of a 10.0e0 grid level

Table 38 lists the geometries and their corresponding grid intersections. The envelopes of four different geometries types intersect the 10.0e grid. The minimum X and Y coordinate of each grid cell that it intersects are entered into the spatial index.

Table 38. The 10.0e0 grid cell entries for the example geometries

Geometry	Grid X	Grid Y
Polygon	20.0	30.0
Polygon	30.0	30.0
Polygon	40.0	30.0
Polygon	20.0	40.0
Polygon	30.0	40.0
Polygon	40.0	40.0
Polygon	20.0	50.0
Polygon	30.0	50.0
Polygon	40.0	50.0
Vertical linestring	50.0	30.0
Vertical linestring	50.0	40.0
Vertical linestring	50.0	50.0
Point	20.0	20.0
Horizontal linestring	20.0	20.0
Horizontal linestring	30.0	20.0
Horizontal linestring	40.0	20.0
Horizontal linestring	50.0	20.0
Horizontal linestring	60.0	20.0
Horizontal linestring	20.0	30.0
Horizontal linestring	30.0	30.0
Horizontal linestring	40.0	30.0
Horizontal linestring	50.0	30.0
Horizontal linestring	60.0	30.0

Figure 8 displays how the number of intersections is greatly reduced to eight by the addition of grid levels 30.0e0 and 60.0e0. In this case, the polygon identified as geometry 1 is promoted to grid level 30.0e0 and the linestring identified as geometry 4 is promoted to grid level 60.0e0. Instead of the nine and ten intersections that geometries had at the 10.0e0 level, they have only two after promotion.

Figure 8. Effect of adding grid levels 30.0e0 and 60.0e0. The envelope of the polygon identified as geometry 1 intersects nine grid cells. The envelope of the vertical linestring identified as geometry 2 intersects three grid cells. The envelope of the point identified as geometry 3 intersects just one grid cell. The envelope of the linestring identified as geometry 4 intersects ten grid cells.

DB2 Spatial Extender takes the grid level parameters specified in the CREATE INDEX statement and checks each spatial object to determine the coordinates and number of grid blocks in which the object exists. In Figure 8, the grid levels 10.0e0, 30.0e0, and 60.0e0 are displayed with ever-increasing line weights and different shades of gray. The vertical linestring and the point envelope cell intersections are entered into the index at the 10.0e0 grid level, because both generate less than four intersections. The polygon intersects nine 10.0e0 grid cells, and is therefore promoted to the 30.0e0 grid level. At this level, the polygon intersects two grid cells, which are entered into the index. The linestring identified as geometry 4 intersects ten 10.0e0 grid cells, and is therefore promoted to the 30.0e0 grid level. Yet at this level, it intersects six grid cells, so it is again promoted to the 60.0e0 grid level, where it generates two intersections. The linestring 60.0e0 grid intersections are then entered into the index. If the linestring had generated four or more intersections at this level, they still would have been entered into the index because this is the highest level at which a geometry can be promoted.

Table 39. The intersections of the geometries in the three-tiered index

Geometry	Grid X	Grid Y
The intersections between the vertical linestring and the point in the level 1 (10.0e0 grid size)
2	50.0	30.0
2	50.0	40.0
2	50.0	50.0
3	20.0	20.0
The intersections of the polygon in the level 2 (30.0e0 grid size)
1	0.0	30.0
1	30.0	30.0
The intersections of the linestring in the level 3 (60.0e0 grid size)
4	0.0	0.0
4	60.0	0.0

DB2 Spatial Extender does not actually create a polygon grid structure of any kind. DB2 Spatial Extender manifests each grid level parametrically by defining the origin at the X,Y offset of the columns' spatial reference system. It then extends the grid into positive coordinate space. Using a parametric grid, DB2 Spatial Extender generates the intersections mathematically.