Patent ID: 8892569
Filing Date: 2014-11-18
Classification: G06F

Abstract:
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.