Querying spatial data in column stores using tree-order scans

Patent metadata

Field	Value
Publication number	US-9613055-B2
Application number	US-201414274572-A
Country	US
Kind code	B2
Filing date	May 9, 2014
Priority date	May 9, 2014
Publication date	Apr 4, 2017
Grant date	Apr 4, 2017

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.

First claim

What is claimed is:

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 st

Assignees

• Tyercha Edward-Robert
• Kazmaier Gerrit Simon
• Gildhoff Hinnerk
• Pekel Isil
• Volker Lars
• Grouisborn Tim
• Sap Se

Inventors

• Tyercha Edward-Robert
• Kazmaier Gerrit Simon
• Gildhoff Hinnerk
• Pekel Isil
• Volker Lars
• Grouisborn Tim

Classifications

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/221

  Column-oriented storage; Management thereof · CPC title

• Y10S707/921

  Spatial · CPC title

• G06F16/29 Primary

  Geographical information databases · CPC title

• G06F17/30241 Primary

  Physics · mapped topic