Columnwise Storage of Point Data

• US 20140222828A1
• Filed: 04/08/2014
• Published: 08/07/2014
• Est. Priority Date: 06/04/2012
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Weyerhaeuser, Christoph, Baeumges, Daniel, Kazmaier, Gerrit Simon, Mindnich, Tobias
• Granted Patent: US 9,128,969 B2
• Time in Patent Office: Days
• US Class Current: 707/743
• 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-20. -20. (canceled)

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

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

23. A method as in claim 22, wherein the database is an in-memory database.

24. A method as in claim 21 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.

25. A method as in claim 21, wherein the point data characterizes geometric attributes of data.

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

27. A method as in claim 21, wherein the point data characterizes topology attributes of data.

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

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

30. 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, the dictionary provide dictionary-based compression;

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.

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

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

33. A computer program product as in claim 30, 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.

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

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

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

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

38. 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 with a shared dictionary;

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

39. A system as in claim 38, 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.

40. A system as in claim 38, 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.