Indexing spatial data with a quadtree index having cost-based query decomposition

摘要

Approaches for indexing and retrieving spatial data with a quadtree index in database management systems are described. In an embodiment, data objects are stored without decomposition within a linearized quadtree stored within a B-tree index. In another embodiment, a method determines an optimal execution plan for a spatial query by parsing it to determine a query type and geometry object associated with the query. The method tessellates the query object by recursively decomposing the quadtree blocks that cover it. Cost-based decomposition decisions are made by consulting a cost model furnished by the database management system to minimize the cost of the resulting index range plan on the B-tree storage. Thus, data-directed query decomposition enacted by the method results in the optimal cost index range plan for the current data distribution and system context. In another embodiment, a system identifies and displays an optimal index range plan in a user interface.

主权项

1. A method for determining an optimal execution plan for a spatial data query in a database management system, comprising:
receiving a query for data related to a spatial data object; parsing the query to determine a query type and a key for the data object; determining quadtree blocks assigned to a block of the data object; recursively partitioning the quadtree blocks to derive keys for the quadtree blocks; performing data-directed range decomposition of the query; identifying an optimal index range plan for the query, wherein the identifying comprises: recursively traversing a logical quadtree depth-first, and assembling, incrementally at each recursive traversal, the index range plan for the query; pruning a search space for the query while retaining optimality of a search associated with the query, wherein the pruning is branch-and-bound pruning; and creating a spatial quadtree index based on the identifying.