US 8,751,526 B1Granted

Efficient range unions in SQL

AssigneeBentley Systems, Incorporated

InventorsKeith A. Bentley, Raymond B. Bentley

Life of this patent

Estimating the term…

Loading patent…

Abstract

In one embodiment, a union of the bounding boxes is computed of entities in a relational database indexed by a spatial index, filtered according to some criteria. For each of a set of targets to be considered, a bounding box of the target is tested against a current range union result. If the bounding box is completely contained in the current range union result, the target is excluded from further consideration. Otherwise, the target is processed. When the target is an entity, it is determined whether the entity meets the entity filtering criteria. If so a union is computed and the current range union result updated. When each of the targets to be considered in the spatial index has been subject to test or excluded, the current range union result is returned as a final range union result.

Claims19

Dependent claims

A method for computing a union of bounding boxes of entities in a relational database indexed by a spatial index, filtered according to an entity filtering criteria, the method comprising:

receiving, by a relational database system executing on an electronic device, a query statement requesting the union of the bounding boxes of entities in the relational database filtered according to the entity filtering criteria;
for each of a set of targets to be considered in the spatial index, testing a bounding box of the target against a current range union result, and
if the bounding box of the target subject to test is completely contained in the current range union result, excluding the target subject to test from further consideration and when the target subject to test is an internal node excluding any lower level nodes or entities in the spatial index pointed to from the internal node from further consideration, and
if the bounding box of the target subject to test is not completely contained in the current range union result, when the target subject to test is an entity, determining if the entity meets the entity filtering criteria, and if so, computing a union of a bounding box of the entity and the current range union result, and storing the union as the current range union result;
and
when each of the targets to be considered in the spatial index has been subject to test or excluded, returning the current range union result as a final range union result.

3 more elements

A non-transitory computer-readable medium containing executable instructions, the executable instructions, when executed by one or more processors, operable to:

process a query statement requesting a union of bounding boxes of entities in a relational database that includes spatial data filtered according to an entity filtering criteria, wherein the entities in the relational database are indexed by a spatial index;
for each of a set of targets to be considered in the spatial index, test a bounding box of the target against a current range union result, and
if the bounding box of the target subject to test is completely contained in the current range union result, exclude the target subject to test from further consideration and when the target subject to test is an internal node exclude any lower level nodes or entities in the spatial index pointed to from the internal node from further consideration, and
if the bounding box of the target subject to test is not completely contained in the current range union result, when the target subject to test is an entity, determine if the entity meets the entity filtering criteria, and if so, compute a union of a bounding box of the entity and the current range union result, and store the union as the current range union result;
and
when each of the targets to be considered in the spatial index has been subject to test or excluded, return the current range union result as a final range union result.

3 more elements

Dependencies are inferred from the claim text.