Consider two tables, P500000 and R5000, each of which contains a column that is a geospatial shape (column A in table P500000 and column B in table R5000).
For simplicity, the two tables have MBRs as their shapes, but any type of shape can be used by passing the MBR of the shape to the tessellation function and then doing the overlap comparison between the two shapes via the ST_Overlaps method in the final WHERE clause.
The following statement counts the number of objects that overlap between the two tables.
SELECT COUNT(*) FROM ( SELECT * FROM P500000 A ,TABLE(tessellate(A.rkey, A.xmin, A.ymin, A.xmax, A.ymax, 0, 0, 100, 100, 100, 100 ) )T1 WHERE A.rkey = T1.out_key ) S1 ,( SELECT * FROM R5000 B ,TABLE( Tessellate(B.rkey, B.xmin, B.ymin, B.xmax, B.ymax, 0, 0, 100, 100, 100, 100 ) )T2 WHERE B.rkey = T2.out_key )S2 WHERE S1.cellid = S2.cellid AND S1.xmax >= S2.xmin and S1.xmin <= S2.xmax AND S1.ymax >= S2.ymin and S1.ymin <= S2.ymax;
Here is how the tessellation works in the preceding example.
- We define a tessellation grid that is large enough to contain the universe of shapes within our two tables and we define a granularity that is reasonable given the typical size of a spatial object. In this case, the grid is 100 by 100 in size as defined by a universe MBR of 0,0 to 100,100 and the number of grid cells in both the x and y direction is defined to be 100.
- In the first SELECT statement, a row at a time is selected from P500000. For each row, the tessellate table function is called to return a table of cell ids that contain the spatial object. This produces a table (S1) of the spatial objects and the cells that contain them. For example, if a row from P500000 is processed and the spatial object is in four cells, four rows are added to S1, each with the same spatial object and a cell id. This continues for all rows in P500000.
- The second SELECT statement is processed on table R5000 in the same way as the first select statement with the results going into S2.
- Now there are two tables, S1 and S2. Next, the final WHERE clause does a join between S1 and S2 on the cell id and the overlaps computation, which is simple for an MBR shape. This produces a row if the two shapes overlap. If we assume that the overlaps computation can be expensive, the performance gain comes from the fact that only spatial objects that are in the same cell are compared via the overlaps computation. The overlaps computation is never executed for objects that are not physically close to one another.