Querying spatial data in column stores using grid-order scans

• US 10,380,130 B2
• Filed: 06/27/2017
• Issued: 08/13/2019
• 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): Uddin, Md I
• Application Number:
  US15/635,004
• Publication Number:
  US 20170293662A1
• Time in Patent Office: 777 Days
• Field of Search: 707714, 707722, 707792, 707999002, 707999003
• 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 plurality of spatial point objects into a grid having fixed boundaries and comprising rectangular cells, and

indexing the cells of the grid, wherein the indexing comprises assigning each spatial point object of the plurality of spatial point objects to a particular cell of the grid, assigning one or more bounding boxes to one or more of the cells, maintaining a record of the assignment of the one or more bounding boxes to the one or more of the cells, and creating index vectors to represent the cells of the grid,

wherein assigning one or more bounding boxes to one or more of the cells comprises assigning a bounding box to a cell if the bounding box intersects a predefined number of adjacent cells with respect to a single characteristic point of the bounding box, and assigning the bounding box to an overflow cell if the intersection of the bounding box exceeds the predefined cellsize;

receiving a query of the spatial data and checking overflow cell for every received query;

identifying a target bounding box based on the received query of the spatial data, the identifying comprising scanning the cells of the grid using the index vectors and return bit vector to check valid entries;

determining, based on the mapping and the identified target 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;

retrieving the spatial data set from the physical storage location based on the determining and in response to the received query of the spatial data; and

providing the retrieved spatial data set in response to the received query of the spatial data.

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

3. The method of claim 1, wherein indexing the cells further comprises adding a separate vector that stores, for each replicated entry, an object identifier.

4. The method of claim 3, wherein the one or more bounding boxes have a sequentially increasing integer object identifier.

5. The method of claim 4, further comprising, upon retrieving the spatial data set for the received query, applying the mapping to identify the plurality of spatial point objects.

6. The method of claim 1, wherein the grid ordering comprises the grid of cells having non-uniform dimensions.

7. 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 plurality of spatial point objects into a grid having fixed boundaries and comprising rectangular cells, and

indexing the cells of the grid, wherein the indexing comprises assigning each spatial point object of the plurality of spatial point objects to a particular cell of the grid, assigning one or more bounding boxes to one or more of the cells, maintaining a record of the assignment of the one or more bounding boxes to the one or more of the cells, and creating index vectors to represent the cells of the grid,

wherein assigning one or more bounding boxes to one or more of the cells comprises assigning a bounding box to a cell if the bounding box intersects a predefined number of adjacent cells with respect to a single characteristic point of the bounding box, and assigning the bounding box to an overflow cell if the intersection of the bounding box exceeds the predefined cellsize;

receiving a query of the spatial data and checking overflow cell for every received query;

identifying a target bounding box based on the received query of the spatial data, the identifying comprising scanning the cells of the grid using the index vectors and return bit vector to check valid entries;

determining, based on the mapping and the identified target 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;

retrieving the spatial data set from the physical storage location based on the determining and in response to the received query of the spatial data; and

providing the retrieved spatial data set in response to the received query of the spatial data.

8. The computer program product of claim 7, wherein the grid ordering comprises the grid of cells being of uniform length along each axis of a plurality of axes.

9. The computer program product of claim 7, wherein indexing the cells further comprises adding a separate vector that stores, for each replicated entry, an object identifier.

10. The computer program product of claim 9, wherein the one or more bounding boxes have a sequentially increasing integer object identifier.

11. The computer program product of claim 10, wherein the operations further comprise, upon retrieving the spatial data set for the received query, applying the mapping to identify the plurality of spatial point objects.

12. The computer program product of claim 7, wherein the grid ordering comprises the grid of cells having non-uniform dimensions.

13. 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 plurality of spatial point objects into a grid having fixed boundaries and comprising rectangular cells, and

indexing the cells of the grid, wherein the indexing comprises assigning each spatial point object of the plurality of spatial point objects to a particular cell of the grid, assigning one or more bounding boxes to one or more of the cells, maintaining a record of the assignment of the one or more bounding boxes to the one or more of the cells, and creating index vectors to represent the cells of the grid,

wherein assigning one or more bounding boxes to one or more of the cells comprises assigning a bounding box to a cell if the bounding box intersects a predefined number of adjacent cells with respect to a single characteristic point of the bounding box, and assigning the bounding box to an overflow cell if the intersection of the bounding box exceeds the predefined cellsize;

receiving a query of the spatial data and checking overflow cell for every received query;

identifying a target bounding box based on the received query of the spatial data, the identifying comprising scanning the cells of the grid using the index vectors and return bit vector to check valid entries;

determining, based on the mapping and the identified target 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;

retrieving the spatial data set from the physical storage location based on the determining and in response to the received query of the spatial data; and

providing the retrieved spatial data set in response to the received query of the spatial data.

14. The system of claim 13, wherein the grid ordering comprises the grid of cells being of uniform length along each axis of a plurality of axes.

15. The system of claim 13, wherein indexing the cells further comprises adding a separate vector that stores, for each replicated entry, an object identifier.

16. The system of claim 15, wherein the one or more bounding boxes have a sequentially increasing integer object identifier.

17. The system of claim 16, wherein the operations further comprise, upon retrieving the spatial data set for the received query, applying the mapping to identify the plurality of spatial point objects.

18. The system of claim 13, wherein the grid ordering comprises the grid of cells having non-uniform dimensions.