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.
2. The method of claim 1 , wherein the database management system stores two dimensional (2D) data and wherein the spatial data object is a 2D planar object.
3. The method of claim 1 , wherein the database management system supports data types representing one or more of:
a point,
a curve,
a line (linestring),
a surface,
a polygon,
a multi-surface polygon; or
multi-curve linestrings.
4. The method of claim 1 , wherein the database management system stores three dimensional (3D) data and wherein the spatial data object is a 3D object.
5. The method of claim 1 , wherein the query type is one of:
an intersection query;
a containment query; or
a within query.
6. The method of claim 5 , wherein the query is expressed in structured query language (SQL) and wherein the query includes one of the following operators:
INTERSECTS;
CONTAINS; or
WITHIN.
7. The method of claim 1 , wherein the creating comprises executing a structured query language (SQL) CREATE INDEX command.
8. The method of claim 1 , wherein the retrieving comprises quadtree block retrieval of ancestors of the block and descendants of the block.
9. The method of claim 1 , wherein the keys for the quadtree blocks are Morton keys and the quadtree blocks are Morton blocks.
10. The method of claim 9 , wherein the identifying comprises: enumerating object decompositions when recursively traversing the logical quadtree depth-first; and
wherein the assembling further comprises using knowledge of a Morton key ordering to merge adjacent Morton key ranges; and
pruning a search space for the query while retaining optimality of a search associated with the query.
11. The method of claim 10 , further comprising:
evaluating, at each recursive traversal, a cost of a current, partially constructed index range plan to determine if the cost exceeds the cost of a previously constructed index range plan that spanned an entire ancestor Morton block; and
in response to determining that the cost exceeds the cost of the previously constructed index range plan, backtracking out of a current traversal of the logical quadtree.
12. The method of claim 11 , wherein the evaluating determines if the cost of the current, partially constructed index range plan exceeds a predetermined upper bound.
13. The method of claim 12 , wherein the upper bound is a tunable parameter.
14. The method of claim 1 , wherein the data-directed range decomposition is cost-based.
15. The method of claim 1 , wherein the quadtree index is a linear quadtree index.
16. The method of claim 1 , wherein the identifying further comprises recursively searching for a least-cost index range plan.
17. A non-transitory computer readable storage medium having instructions stored thereon that, in response to execution by a computing device, cause the computing device to perform operations comprising:
receiving a query for data related to a spatial data object;
parsing the query to determine a query type and a quadtree block of the data object;
initializing a whole index range plan for the quadtree block, wherein the whole index range plan comprises a single index range to retrieve all objects assigned to the quadtree block or any child quadtree blocks of the quadtree block;
appending an index key range of the quadtree block to the whole index range plan;
recursively partitioning the quadtree block to identify:
child quadtree blocks assigned to the quadtree block; and
child keys for the identified child quadtree blocks;
identifying a decomposition index range plan for the quadtree block, wherein the decomposition index range plan comprises optimal plans computed for the child quadtree blocks, the optimal plans computed by recursively traversing a logical quadtree depth-first, 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 assembling, incrementally at each recursive traversal, the optimal plan for the query;
determining a cost of using the whole index range plan and a cost of using the decomposition range plan;
designating, based on the determining, the least costly index range plan as an optimal index range plan for the received query.
18. A system for creating a spatial quadtree index comprising:
a database server comprising:
database storage storing a database comprising an initial spatial index and a plurality of tables comprising rows of spatial data;
a query parser to receive a query for spatial data, wherein the query parser determines a spatial data object and query type associated with the query;
a filter to determine a plurality of candidates for the query, wherein the candidates are determined using the initial spatial index to reduce the size of the plurality of candidates;
an execution unit configured to retrieve, from the database, quadtree blocks assigned to a block of the data object;
a partitioning module configured to recursively partition the quadtree blocks to derive keys for the quadtree blocks;
a query decomposition module configured to perform data-directed range decomposition of the query;
optimizer configured to identify an optimal index range plan for the query, recursively traverse a logical quadtree depth-first, prune a search space for the query while retaining optimality of a search associated with the query, wherein the prune is a branch-and-bound prune, and assemble, incrementally at each recursive traversal, the index range plan for the query;
an indexer configured to create a spatial quadtree index based on the optimal index range plan; and
a display device configured to display representations of the optimal index range plan and the spatial quadtree index in an interactive user interface.
19. The system of claim 18 , wherein the query decomposition module is further configured to perform the data-directed range decomposition when the query executes (at run time).
20. The system of claim 19 , wherein the query decomposition module is further configured to perform the data-directed range decomposition using storage statistics for plurality of tables.
21. The system of claim 20 , wherein the storage statistics are represented as one or more histograms.