Loose bounding box calculations

In an R-tree index, bounding boxes are used to identify all data that might qualify during a search. A more accurate check is always applied as a second step. For this reason, one might think that the bounding box of an object could be loose, or not an exact fit, without causing anything worse than a few initial false hits. It is often difficult to calculate an exact bounding box for some objects, such as great circle arcs on the surface of the earth, so there is a compelling reason to use an approximation.

However, there is a possibility you might get inaccurate results when you use loose bounding boxes. For example, assume the bounding box for data object A is looser than the bounding box for data object B. Even if data object A is within data object B, A's bounding box might extend beyond B's, due to its looseness. The Within strategy function, if written to rely on a preliminary bounding box check, might return FALSE when it should return TRUE. As a result, the R-tree access method code that called the Within function might miss some qualifying data.

There are two solutions to this problem:
  • Calculate exact bounding boxes for all data objects.
  • Add a compensating factor, the maximum looseness, to the size of one of the arguments before comparing bounding boxes. You program this compensating factor in the bounding box portion of the strategy function code.

    In the example in the preceding paragraph, add X to the size of B's bounding box, where X is the maximum looseness of A's bounding box, before comparing A and B's bounding boxes.

The R-tree access method code might call a different strategy function when it processes internal pages. For example, the access method uses the Contains strategy function for internal pages when it processes a query that specifies the Equal function. The bounding box logic must be correct in all cases.