4
Querying Spatial Data

This chapter describes how the structures of a Spatial layer in the object-relational model are used to resolve spatial queries and spatial joins. For the sake of clarity, the examples all use fixed-size tiling, but hybrid indexing is actually recommended for the object-relational model.

4.1 Query Model

Spatial uses a two-tier query model to resolve spatial queries and spatial joins. The term two-tier is used to indicate that two distinct operations are performed in order to resolve queries. If both operations are performed, the exact result set is returned.

The two operations are referred to as primary filter and secondary filter operations.

• The primary filter permits fast selection of candidate records to pass along to the secondary filter. The primary filter uses geometry approximations (or index tiles) to reduce computational complexity and is considered a lower-cost filter.

• The secondary filter applies exact computational geometry to the result set of the primary filter. These exact computations yield the exact answer to a query. The secondary filter operations are computationally more expensive, but they are applied only to the relatively small result set returned from the primary filter.

4.2 Spatial Query

An important concept in the spatial data model is that each geometry is represented by a set of exclusive and exhaustive tiles. This means that no tiles overlap each other (exclusive), and the tiles fully cover the object (exhaustive).

Consider the following layer containing several objects in Figure 4-1. Each object is labeled with its SDO_GID. The relevant tiles are labeled with `Tn'.

Figure 4-1 Tessellated Layer with Multiple Objects

A typical spatial query is to request all objects that lie within a defined fence or window. A query window is shown in Figure 4-2 by the dotted-line box. A dynamic query window refers to a fence that is not defined in the database, but that must be defined before it is used.

Figure 4-2 Tessellated Layer with a Query Window

4.2.1 Primary Filter

Spatial provides an operator named SDO_FILTER. This implements the primary filter portion of the two-step process involved in the product's query processing model. The primary filter uses the index data only to determine a set of candidate object pairs that may interact. The syntax is as follows:

SDO_FILTER(geometry1 MDSYS.SDO_GEOMETRY, geometry2 MDSYS.SDO_GEOMETRY, 

  params VARCHAR2)

Where:

• geometry1 is a column of type MDSYS.SDO_GEOMETRY in a table. geometry1 must be spatially indexed.

• geometry2 is an object of type MDSYS.SDO_GEOMETRY. geometry2 may or may not come from a table. If it comes from a table, it may or may not be spatially indexed.

• params is a quoted string of keyword value pairs that determine the behavior of the operator. See the SDO_FILTER operator in Chapter 6 for a list of parameters.

The following examples perform a primary filter operation only. They will return all the geometries shown in Figure 4-2 that have an index tile in common with one of the index tiles that approximates the query window: tiles T1, T2, T3, and T4. The result of the following examples are geometries with IDs 1013, 1243, 12, and 501.

Example 4-1 performs a primary filter operation without inserting the query window into a table. The window will be indexed in memory and performance will be very good.

Example 4-1 Primary Filter with a Temporary Query Window

SELECT A.Feature_ID FROM TARGET A

 WHERE sdo_filter(A.shape, mdsys.sdo_geometry(2003,NULL,NULL,
                                       mdsys.sdo_elem_info_array(1,1003,3),
                                       mdsys.sdo_ordinate_array(x1,y1, x2,y2)),
                        'querytype=window') = 'TRUE';	

Note that (x1,y1) and (x2,y2) are the lower-left and upper-right corners of the query window.

In Example 4-2, a transient instance of type SDO_GEOMETRY was constructed for the query window instead of specifying the window parameters in the query itself.

Example 4-2 Primary Filter with a Transient Instance of the Query Window

SELECT A.Feature_ID FROM TARGET A

 WHERE sdo_filter(A.shape, :theWindow,'querytype=window') = 'TRUE';	

Example 4-3 assumes the query window was inserted into a table called WINDOWS, with an ID of WINS_1.

Example 4-3 Primary Filter with a Stored Query Window

SELECT A.Feature_ID FROM TARGET A, WINDOWS B

 WHERE B.ID = 'WINS_1' AND 

  sdo_filter(A.shape, B.shape,'querytype=window') = 'TRUE';	

If the B.SHAPE column is not spatially indexed, the SDO_FILTER operator indexes the query window in memory and performance is very good.

If the B.SHAPE column is spatially indexed with the same SDO_LEVEL value as the A.SHAPE column, the SDO_FILTER operator reuses the existing index, and performance is very good or better.

If the B.SHAPE column is spatially indexed with a different SDO_LEVEL value than the A.SHAPE column, the SDO_FILTER operator reindexes B.SHAPE in the same way as if there were no index on the column originally, and then performance is very good.

4.2.2 Primary and Secondary Filters

The SDO_RELATE operator performs both the primary and secondary filter stages when processing a query. The syntax of the operator is as follows:

 SDO_RELATE(geometry1  MDSYS.SDO_GEOMETRY,
            geometry2  MDSYS.SDO_GEOMETRY,
            params     VARCHAR2)

Where:

• geometry1 is a column of type MDSYS.SDO_GEOMETRY in a table. geometry1 must be spatially indexed.

• geometry2 is an object of type MDSYS.SDO_GEOMETRY. geometry2 may or may not come from a table. If it comes from a table, it may or may not be spatially indexed.

• params is a quoted string of keyword value pairs that determine the behavior of the operator. See the SDO_RELATE operator in Chapter 6 for a list of parameters.

The following examples perform both primary and secondary filter operations. They return all the geometries in Figure 4-2 that lie within or overlap the query window. The result of these examples is objects 1243 and 1013.

Example 4-4 performs both primary and secondary filter operations without inserting the query window into a table. The window will be indexed in memory and performance will be very good.

Example 4-4 Secondary Filter Using a Temporary Query Window

SELECT A.Feature_ID FROM TARGET A
   WHERE sdo_relate(A.shape, mdsys.sdo_geometry(2003,NULL,NULL,
                                       mdsys.sdo_elem_info_array(1,1003,3),
                                      mdsys.sdo_ordinate_array(x1,y1, x2,y2)),

                        'mask=anyinteract querytype=window') = 'TRUE';

Note that (x1,y1) and (x2,y2) are the lower-left and upper-right corners of the query window.

Example 4-5 assumes the query window was inserted into a table called WINDOWS, with an ID of WINS_1.

Example 4-5 Secondary Filter Using a Stored Query Window

SELECT A.Feature_ID FROM TARGET A, WINDOWS B

 WHERE B.ID= 'WINS_1' AND 

        sdo_relate(A.shape, B.shape,
          'mask=anyinteract querytype=window') = 'TRUE';	

If the B.SHAPE column is not spatially indexed, the SDO_RELATE operator indexes the query window in memory and performance is very good.

If the B.SHAPE column is spatially indexed with the same SDO_LEVEL value as the A.SHAPE column, the SDO_RELATE operator reuses the existing index, and performance is very good or better.

If the B.SHAPE column is spatially indexed with a different SDO_LEVEL value than the A.SHAPE column, the SDO_FILTER operator reindexes B.SHAPE in the same way as if there were no index on the column originally, and then performance is very good.

4.2.3 Within-Distance Operator

The SDO_WITHIN_DISTANCE operator is used to determine the set of objects in a table that are within n Euclidean distance units from a reference object aRefGeom. The reference object may be a transient or persistent instance of MDSYS.SDO_GEOMETRY (such as a temporary query window or a permanent geometry stored in the database). The syntax is as follows:

SDO_WITHIN_DISTANCE(geometry1  MDSYS.SDO_GEOMETRY, 
                    aRefGeom   MDSYS.SDO_GEOMETRY,
                    params     VARCHAR2)

Where:

• geometry1 is a column of type MDSYS.SDO_GEOMETRY in a table. geometry1 must be spatially indexed.

• aRefGeom is an instance of type MDSYS.SDO_GEOMETRY.

• params is a quoted string of keyword value pairs that determines the behavior of the operator. See the SDO_WITHIN_DISTANCE operator in Chapter 6 for a list of parameters.

The following example selects any objects within 1.35 distance units from the query window:

SELECT A.Feature_ID
  FROM TARGET A
  WHERE SDO_WITHIN_DISTANCE( A.shape, :theWindow, 'distance=1.35') = 'TRUE';

The distance units are based on the geometry coordinate system in use. Spatial treats the coordinate space as Cartesian. If your data consists of latitude and longitude pairs, then you cannot use the SDO_WITHIN_DISTANCE operator to provide correct results unless all your data is near the equator. If all the data is not near the equator, you must project the latitude/longitude data into a locally-conformal Cartesian plane before using the SDO_WITHIN_DISTANCE operator.

The SDO_WITHIN_DISTANCE operator is not suitable for performing spatial joins. That is, a query such as Find all parks that are within 10 distance units from coastlines will not be processed as an index-based spatial join of the COASTLINES and PARKS tables. Instead, it will be processed as a nested loop query in which each COASTLINES instance is in turn a reference object that is buffered, indexed, and evaluated against the PARKS table. Thus, the SDO_WITHIN_DISTANCE operation is performed n times if there are n rows in the COASTLINES table.

There is an efficient way to accomplish a spatial join that involves buffering all the geometries of a layer. This method does not use the SDO_WITHIN_DISTANCE operator. First, create a new table COSINE_BUFS as follows:

CREATE TABLE cosine_bufs UNRECOVERABLE AS
   SELECT SDO_BUFFER (A.SHAPE, B.DIMINFO, 1.35)
     FROM COSINE A, USER_SDO_GEOM_METADATA B
     WHERE TABLE_NAME='COSINES' AND COLUMN_NAME='SHAPE';

Next, create a spatial index on the SHAPE column of COSINE_BUFS. Then you can perform the following query:

SELECT a.gif, b.gid FROM parks A cosine_bufs B
  WHERE SDO_Relate(A.shape, B.shape, 'mask=ANYINTERACT querytype=JOIN') ='TRUE';

4.2.4 Nearest Neighbor Operator

The SDO_NN operator is used to identify the nearest neighbors for a geometry. The syntax is as follows:

SDO_NN(geometry1  MDSYS.SDO_GEOMETRY, 
       geometry2  MDSYS.SDO_GEOMETRY,
       param      VARCHAR2)

Where:

• geometry1 is a column of type MDSYS.SDO_GEOMETRY in a table. geometry1 must be spatially indexed.

• geometry2 is an instance of type MDSYS.SDO_GEOMETRY.

• param is a quoted string of a keyword value pair that determines how many nearest neighbor geometries are returned by the operator. See the SDO_NN operator in Chapter 6 for information about this parameter.

The following example finds the two objects from the SHAPE column in the COLA_MARKETS table that are closest to a specified point (10,7). (Note the use of the optimizer hint in the SELECT statement, as explained in the Usage Notes for the SDO_NN operator in Chapter 6.)

SELECT /*+ INDEX(cola_markets cola_spatial_idx) */
 c.mkt_id, c.name  FROM cola_markets c  WHERE SDO_NN(c.shape,
   mdsys.sdo_geometry(2001, NULL, mdsys.sdo_point_type(10,7,NULL), NULL,
   NULL),  'sdo_num_res=2') = 'TRUE'; 

4.3 Spatial Join

A spatial join is the same as a regular join except that the predicate involves a spatial operator. In Spatial, a spatial join takes place when you compare all the geometries of one layer to all the geometries of another layer. This is unlike a query window that only compares a single geometry to all geometries of a layer.

In a spatial join, all tables must have the same type of spatial index (that is, R-tree or quadtree) defined on the geometry column; and if they have quadtree indexes, the SDO_LEVEL value must be the same for all the indexes.

Spatial joins can be used to answer questions such as, Which highways cross national parks?

The following table structures illustrate how the join would be accomplished for this example:

PARKS(    GID VARCHAR2(32), SHAPE MDSYS.SDO_GEOMETRY)
HIGHWAYS( GID VARCHAR2(32), SHAPE MDSYS.SDO_GEOMETRY) 

The primary filter would identify pairs of GID values from the PARKS and HIGHWAYS tables that interact in their index entries. The query that performs the primary filter join is:

SELECT A.GID, B.GID 

  FROM PARKS A, HIGHWAYS B 

  WHERE sdo_filter(A.shape, B.shape, 'querytype=join') = 'TRUE';

The original question, asking about highways that cross national parks, requires the secondary filter operator to find the exact relationship between highways and parks.

The query that performs this join using both primary and secondary filters is:

SELECT A.GID, B.GID 
  FROM parks A, highways B
  WHERE sdo_relate(A.shape, B.shape, 

           'mask=ANYINTERACT querytype=join');

4.4 Cross-Schema Operator Invocation

You can invoke spatial operators on an indexed table that is not in your schema. Assume that user A has a spatial table T1 (with index table IDX_TAB1) with a spatial index defined, that user B has a spatial table T2 (with index table IDX_TAB2) with a spatial index defined, and that user C wants to invoke operators on tables in one or both of the other schemas.

If user C wants to invoke an operator only on T1, user C must perform the following steps:

1. Connect as user A and execute the following statements:

   GRANT select on T1 to C;
   GRANT select on idx_tab1 to C;
   
   

2. Connect as user C and execute a statement such as the following:

   SELECT a.gid 
     FROM T1 a
     WHERE sdo_filter(a.geometry, :theGeometry, 'querytype=WINDOW') = 'TRUE';
   
   

If user C wants to invoke an operator on both T1 and T2, user C must perform the following steps:

1. Connect as user A and execute the following statements:

   GRANT select on T1 to C;
   GRANT select on idx_tab1 to C;
   
   

2. Connect as user B and execute the following statements:

   GRANT select on T2 to C;
   GRANT select on idx_tab2 to C;
   
   

3. Connect as user C and execute a statement such as the following:

   SELECT a.gid
     FROM T1 a, T2 b
     WHERE b.gid = 5 AND 
           sdo_filter(a.geometry, b.geometry, 'querytype=WINDOW') = 'TRUE';