Querying spatial data in column stores using grid-order scans

• US 9,720,931 B2
• Filed: 05/09/2014
• Issued: 08/01/2017
• Est. Priority Date: 05/09/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Kazmaier, Gerrit Simon, Tyercha, Edward-Robert, Gildhoff, Hinnerk, Volker, Lars, Grouisborn, Tim, Pekel, Isil
• Primary Examiner(s): Uddin, Md. I
• Application Number:
  US14/274,548
• Publication Number:
  US 20150324373A1
• Time in Patent Office: 1,180 Days
• Field of Search: 707714, 707722, 707792
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

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 grid order scanning technique. The spatial data set corresponding to the received query is then mapped to physical storage in the database using the identified minimal bounding rectangle so that the spatial data set can be 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 grid ordering comprising;

dividing a bounded space containing the spatial point objects into a grid having fixed boundaries and comprising rectangular cells,

indexing the cells of the grid, wherein the indexing comprises defining a minimum bounding box for each spatial point object of the plurality of spatial point objects, the minimum bounding box enclosing the spatial point object, storing a grid-identifier to at least one cell of the grid for each minimum bounding box, and creating index vectors to represent the cells of the grid and the grid identifiers of the minimum bounding boxes, and

assigning any minimum bounding boxes having a size above a certain level to an overflow cell;

identifying a target minimum bounding box based on a received query of the spatial data, the identifying comprising scanning the cells of the grid and the exclusive ordering values using the index vectors;

determining, based on the mapping and the identified target 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, the determining further comprising checking the overflow cell for the received query; and

retrieving the spatial data set from the physical storage location based on the determining.

2. A method as in claim 1, wherein the grid ordering comprises the grid of cells being of uniform length along each axis of a plurality of axes.

3. A method as in claim 2, wherein the indexing of the cells of the grid comprises indexing the cells with a space-filling curve.

4. A method as in claim 3, wherein the space-filling curve comprises a Hilbert space-filling curve.

5. A method as in claim 2, further comprising redundantly storing a reference to each minimum bounding box for every cell the minimum bounding box intersects.

6. A method as in claim 2, further comprising storing a reference to each minimum bounding box only for a cell at which a corner of the minimum bounding box is inside.

7. A method as in claim 6, wherein a parameter defines a number of adjacent cells per dimension extending from the corner.

8. A method as in claim 1, wherein the size is based on a number of adjacent cells per dimension that the minimum bounding box can intersect.

9. A method as in claim 1, wherein the grid ordering comprises the grid of cells having non-uniform dimensions.

10. A non-transitory computer program product 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 grid ordering comprising;

dividing a bounded space containing the spatial point objects into a grid having fixed boundaries and comprising rectangular cells,

indexing the cells of the grid, wherein the indexing comprises defining a minimum bounding box for each spatial point object of the plurality of spatial point objects, the minimum bounding box enclosing the spatial point object, storing a grid-identifier to at least one cell of the grid for each minimum bounding box, and creating index vectors to represent the cells of the grid and the grid identifiers of the minimum bounding boxes, and

assigning any minimum bounding boxes having a size above a certain level to an overflow cell;

identifying a target minimum bounding box based on a received query of the spatial data, the identifying comprising scanning the cells of the grid and the exclusive ordering values using the index vectors;

determining, based on the mapping and the identified target 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, the determining further comprising checking the overflow cell for the received query; and

retrieving the spatial data set from the physical storage location based on the determining.

11. A computer program product as in claim 10, wherein the grid ordering comprises the grid of cells being of uniform length along each axis of a plurality of axes.

12. A computer program product as in claim 11, wherein the indexing of the cells of the grid comprises indexing the cells with a space-filling curve.

13. A computer program product as in claim 12, wherein the space-filling curve comprises a Hilbert space-filling curve.

14. A computer program product as in claim 11, wherein the operations further comprise redundantly storing a reference to each minimum bounding box for every cell the minimum bounding box intersects.

15. A computer program product as in claim 11, wherein the operations further comprise a reference to each minimum bounding box only for a cell at which a corner of the minimum bounding box is inside.

16. A computer program product as in claim 15, wherein a parameter defines a number of adjacent cells per dimension extending from the corner.

17. A computer program product as in claim 15, wherein the operations further comprise any minimum bounding boxes having a size above a certain level to an overflow cell.

18. 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 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 grid ordering comprising;

dividing a bounded space containing the spatial point objects into a grid having fixed boundaries and comprising rectangular cells,

indexing the cells of the grid, wherein the indexing comprises defining a minimum bounding box for each spatial point object of the plurality of spatial point objects, the minimum bounding box enclosing the spatial point object, storing a grid-identifier to at least one cell of the grid for each minimum bounding box, and creating index vectors to represent the cells of the grid and the grid identifiers of the minimum bounding boxes, and

assigning any minimum bounding boxes having a size above a certain level to an overflow cell;

identifying a target minimum bounding box based on a received query of the spatial data, the identifying comprising scanning the cells of the grid and the exclusive ordering values using the index vectors;

determining, based on the mapping and the identified target 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, the determining further comprising checking the overflow cell for the received query; and

retrieving the spatial data set from the physical storage location based on the determining.