Querying spatial data in column stores using tree-order scans

摘要

A query of spatial data is received by a database comprising a columnar data store storing data in a column-oriented structure. Thereafter, a minimal bounding rectangle associated with the query is identified using a tree-order scanning technique. A spatial data set that corresponds to the received query is then mapped to the physical storage in the database using the identified minimal bounding rectangle. Next, the spatial data set is then retrieved. Related apparatus, systems, techniques and articles are also described.

主权项

1. A method implemented on one or more systems comprising one or more programmable processors, the method comprising:
mapping spatial data stored in a database comprising a columnar data store storing the spatial data in a column-oriented structure, the mapping comprising preserving spatial proximity of a plurality of spatial point objects when the spatial data are physically stored using a tree-order hierarchy, the mapping further comprising:
recursively subdividing a bounded space into a grid containing the spatial point objects in the tree-order hierarchy, the tree-order hierarchy having a plurality of levels such that cells in the grid at a lower level of the tree-order hierarchy have a finer scale than cells in the grid at a higher level of the tree-order hierarchy,assigning a bounding rectangle for each spatial point object of the plurality of spatial point objects to a single cell of the grid at a level of the plurality of levels in which the single cell fits all of the spatial point object,indexing the cells of the grid, the indexing comprising enumerating nodes of the tree-order hierarchy such that the tree-order hierarchy is not stored explicitly, andstoring an enumeration order for the bounding box in an index vector, the enumeration order being determined from the indexing; identifying a minimum bounding box based on a received query of the spatial data, the identifying comprising scanning the cells of the grid using a tree-order scanning technique; determining, based on the mapping and using the identified minimum bounding box, a spatial data set corresponding to the received query and a physical storage location in the database from which to retrieve the spatial data set; and retrieving the spatial data set from the physical storage location based on the determining.