Searches

The R-tree access method uses the four required strategy functions in a variety of combinations when searching in an R-tree index, as the following table shows.


Slot Number	Strategy function	Commutator function	Function called on an index key in a nonleaf page
1	Overlap	Overlap	Overlap
2	Equal	Equal	Contains
3	Contains	Within	Contains
4	Within	Contains	Overlap
5	Available for use	Same function	Same function
...	...	...	...
64	Available for use	Same function	Same function
			You can use the RtreeInfo function to redefine these switching semantics.

The first column of the table refers to the position in the CREATE OPCLASS statement of the strategy function. The four required strategy functions must be listed first, in the order shown in the second column.

The third column specifies the function that the R-tree access method uses as the commutator of a particular strategy function. The Within and Contains functions are commutators of each other. Other functions, including those numbered 5 and up, are assumed to be their own commutators. This means that the R-tree access method assumes that when it calls the function, the access method can reverse the order of the arguments without changing the results of the function. Strategy functions should be implemented with these commutator substitutions in mind.

In certain cases, the query optimizer uses the commutator functions as substitute functions. For example, suppose a query has the predicate Within(A, B) in its WHERE clause, where A is a constant search object and B is a table column with an R-tree index defined on it. Predicate functions in WHERE clauses are written to work with an index on the first argument, so the Within function cannot be used in this case, because the R-tree index is on the second argument. The commutator information allows the optimizer to substitute Contains(B, A), which allows the R-tree index on B to be used in the execution of the query.

The strategy functions in slots 5 through 64 can have commutator functions specified by the COMMUTATOR = FUNCTION modifier of the CREATE FUNCTION statements used to register the functions in SQL. If you do not specify a commutator function, the query optimizer does not attempt to change the order of the arguments in order to get an indexed column as the first argument. The following example registers the Contains strategy function and specifies that the Within function is its commutator:

CREATE FUNCTION Contains (MyShape, MyShape)
RETURNS BOOLEAN
WITH
(
    COMMUTATOR = Within,
    NOT VARIANT
)
EXTERNAL NAME "$INFORMIXDIR/extend/shapes.3.0/shapes.bld (MyShapeContains)"
LANGUAGE C;

The strategy functions in slots 5 through 64 can also have negator functions specified by the NEGATOR = FUNCTION modifier of the CREATE FUNCTION statements used to register the functions in SQL. The R-tree access method cannot process queries with a negated strategy function, such as NOT Separated(A,B). However, if the Separated strategy function declares the Overlap function as its negator, the query optimizer is able to substitute the predicate Overlap(A,B) for the NOT Separated(A,B), which allows the use of an R-tree index on column A.

The fourth column specifies the function that the R-tree access method uses when searching for an index key in a nonleaf page. The following paragraph explains why the entry for Within is Overlap, and the entry for Equal is Contains.

Suppose a query has the predicate Within(A, B) in its WHERE clause, where B is a constant search object and A is a table column with an R-tree index defined on it. When a leaf page of the index is searched, the index entries are true candidates to match the query, so the Within function is used directly for each index entry. The search of a branch page tests to see if there exists an entry in the subtree below the branch page that is within the search object B. In this case, the search does not test whether the bounding box of the subtree is within B, but whether the bounding box of the subtree overlaps B. This is because a small entry within the subtree, in the overlapping portion of the bounding box, could be completely within B. Therefore, an index search that uses the Within function must substitute the Overlap function for nonleaf (branch) index pages.

Similarly, an index search that uses the Contains function must substitute the Equal function for nonleaf index pages because a qualifying index entry could be in any subtree whose bounding box contains the search object.

Tip: The RtreeInfo function allows you to specify which function you want the R-tree access method to call for nonleaf data.