Querying spatial data in column stores using tree-order scans

• US 9,613,055 B2
• Filed: 05/09/2014
• Issued: 04/04/2017
• Est. Priority Date: 05/09/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Tyercha, Edward-Robert, Kazmaier, Gerrit Simon, Gildhoff, Hinnerk, Pekel, Isil, Volker, Lars, Grouisborn, Tim
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Weinrich, Brian E.
• Application Number:
  US14/274,572
• Publication Number:
  US 20150324399A1
• Time in Patent Office: 1,061 Days
• Field of Search: 707792, 707791
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/921 Spatial

Abstract

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.

Claims

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, and

storing 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.

2. A method as in claim 1, wherein a boundary of the grid is the same for each level of the tree-order hierarchy.

3. A method as in claim 1, wherein the bounding box is assigned to a single node of the tree-order hierarchy.

4. A method as in claim 1, wherein each node of the tree-order hierarchy corresponds to a single cell at a specified level of the plurality of levels.

5. A method as in claim 4, wherein the tree:

order hierarchy comprises a plurality of nodes.

6. A method as in claim 5, wherein a number of children per node is variable but consistent for the tree-order hierarchy.

7. A method as in claim 6, wherein the number of children is limited by a number of sub-divisions per cell of the tree-order hierarchy.

8. A method as in claim 1, wherein the cells of the tree-order hierarchy are further indexed by a space-filling curve.

9. A method as in claim 8, wherein the space-filling curve is a Z-order space filling curve.

10. A method as in claim 8, wherein another enumeration of the space-filling curve applied to each level of the plurality of levels separately.

11. A method as in claim 8, wherein every cell of the tree-order hierarchy is assigned an enumerated number.

12. A method as in claim 11, wherein every number of a child node is smaller than a number of its corresponding parent node.

13. A method as in claim 1, wherein a depth of the tree-order hierarchy is fixed.

14. A non-transitory computer program product comprising a non-transitory machine-readable medium storing instructions which, when executed by at least one data processor forming part of at least one computing system, result in operations 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, and

storing 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.

15. A computer program product as in claim 14, wherein the cells of the tree-order hierarchy are further indexed by a space-filling curve.

16. A computer program product as in claim 15, wherein the space-filling curve is a Z-order space filling curve and the further indexing comprises another enumeration of the space-filling curve applied to each level of the plurality of levels separately.

17. A system comprising:

a database comprising a columnar data store storing data in a column-oriented structure;

at least one data processor; and

memory storing instructions which, when executed by the at least one data processor, result in operations comprising;

mapping spatial data stored in the database, 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, and

storing 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;

mapping, using the identified minimal bounding rectangle, a spatial data set corresponding to the received query to physical storage in the database; and

retrieving the spatial data set.