Searches
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.
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.