Columnwise storage of point data

• US 9,128,969 B2
• Filed: 04/08/2014
• Issued: 09/08/2015
• Est. Priority Date: 06/04/2012
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Weyerhaeuser, Christoph, Mindnich, Tobias, Baeumges, Daniel, Kazmaier, Gerrit Simon
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): ALLEN, NICHOLAS E
• Application Number:
  US14/248,099
• Publication Number:
  US 20140222828A1
• Time in Patent Office: 518 Days
• Field of Search: 707/743
• US Class Current: 1/1
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A database query of point data among two or more axes of a database is received. The database stores point data in distinct integer vectors with a shared dictionary. Thereafter, the dictionary is scanned to determine boundaries for each axis specified by the query. In response, results characterizing data responsive to the query within the determined boundaries for each axis are returned. Related apparatus, systems, techniques and articles are also described.

Claims

1. A computer-implemented method comprising:

receiving a database query of point data among two or more axes of a database, the database storing point data in distinct integer vectors for each axis with a shared dictionary;

scanning the dictionary to determine boundaries for each axis specified by the query, wherein at least a portion of the scanning for each axis is performed in parallel; and

returning results characterizing data responsive to the query within the determined boundaries for each axis.

2. A method as in claim 1, wherein the database is a column oriented database storing data in a columnwise manner.

3. A method as in claim 2, wherein the database is an in-memory database.

4. A method as in claim 1 further comprising:

generating, for each axis, a bit vector identifying all points within the corresponding boundaries; and

merging all of the bit vectors to generate a query window, the query window being used to identify results responsive to the query.

5. A method as in claim 1, wherein the point data characterizes geometric attributes of data.

6. A method as in claim 5, wherein the geometric attributes comprise one or more of location when data was acquired or shape of acquired data.

7. A method as in claim 1, wherein the point data characterizes topology attributes of data.

8. A method as in claim 7, wherein the topology attributes characterize spatial adjacency in relation to other data points.

9. A method as in claim 1, wherein the receiving, scanning, and returning are performed by at least one data processor forming part of at least one computing system.

10. A non-transitory computer program product storing instructions, which when executed by at least one data processor of at least one computing system, result in operations comprising:

receiving a database query of point data among two or more axes of a database, the database storing point data in distinct integer vectors with a shared dictionary, wherein the dictionary provides dictionary-based compression by representing values in at least one table stored in the database with identifiers for corresponding values;

scanning the dictionary to determine boundaries for each axis specified by the query, wherein at least a portion of the scanning for each axis is performed in parallel; and

returning results characterizing data responsive to the query within the determined boundaries for each axis.

11. A computer program product as in claim 10, wherein the database is a column oriented database storing data in a columnwise manner.

12. A computer program product as in claim 11, wherein the database is an in-memory database.

13. A computer program product as in claim 10, wherein the operations further comprise:

generating, for each axis, a bit vector identifying all points within the corresponding boundaries; and

merging all of the bit vectors to generate a query window, the query window being used to identify results responsive to the query.

14. A computer program product as in claim 10, wherein the point data characterizes geometric attributes of data.

15. A computer program product as in claim 14, wherein the geometric attributes comprise one or more of location when data was acquired or shape of acquired data.

16. A computer program product as in claim 10, wherein the point data characterizes topology attributes of data.

17. A computer program product as in claim 16, wherein the topology attributes characterize spatial adjacency in relation to other data points.

18. A system comprising:

a column-oriented in-memory database storing data columnwise;

one or more data processors;

memory storing instructions, which when executed, cause at least one data processor to perform operations comprising;

receiving a database query of point data among two or more axes, the database storing point data in distinct integer vectors for each axis with a shared dictionary;

scanning, for each axis in parallel, the dictionary to determine boundaries for each axis specified by the query; and

returning results characterizing data responsive to the query within the determined boundaries for each axis.

19. A system as in claim 18, wherein the operations further comprise:

generating, for each axis, a bit vector identifying all points within the corresponding boundaries; and

merging all of the bit vectors to generate a query window, the query window being used to identify results responsive to the query.

20. A system as in claim 18, wherein the point data characterizes geometric attributes of data that comprise one or more of location when data was acquired or shape of acquired data.