Column Store Optimization Using Telescope Columns

• US 20160004735A1
• Filed: 07/07/2014
• Published: 01/07/2016
• Est. Priority Date: 07/07/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Kazmaier, Gerrit Simon, Gildhoff, Hinnerk, Volker, Lars, Grouisborn, Tim
• Granted Patent: US 9,740,719 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof

Abstract

A data set of spatial data having a plurality of dimensions and including linestrings can be processing by decomposing each linestring of the plurality of linestrings into a plurality of line segments. Each coordinate dimension appears in at least one line segment of the plurality of line segments can be listed in one of a plurality of dimensional dictionaries that each correspond to a dimension of the plurality of dimensions. A linestring of the plurality of linestrings can be represented as a set of the line segments using the plurality of dimensional dictionaries.

Claims

1. A computer program product comprising a machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:

processing a data set of spatial data having a plurality of dimensions and comprising a plurality of linestrings, the processing comprising decomposing each linestring of the plurality of linestrings into a plurality of line segments;

listing each coordinate dimension appearing in at least one line segment of the plurality of line segments in one of a plurality of dimensional dictionaries, each dimensional dictionary of the plurality of dimensional dictionaries corresponding to a dimension of the plurality of dimensions;

representing a linestring of the plurality of linestrings as a set of the line segments using the plurality of dimensional dictionaries; and

performing a data set operation on the data set using the plurality of dimensional dictionaries.

2. The computer program product of claim 1, wherein the data set operation comprises a dictionary compression operation.

3. The computer program product of claim 1, wherein the data set operation comprises a bounding box test operation.

4. The computer program product of claim 1, wherein the data set operation comprises a polygon clipping operation

5. The computer program product of claim 1, wherein the data set operation comprises projecting the line segments of the linestring to a grid using a grid join operation.

6. The computer program product of claim 1, wherein the data set operation comprises a join of linestrings, the join comprising finding all line segments of the joined linestrings that intersect using the plurality of dimensional dictionaries.

7. A system comprising:

computer hardware configured to perform operations comprising;

processing a data set of spatial data having a plurality of dimensions and comprising a plurality of linestrings, the processing comprising decomposing each linestring of the plurality of linestrings into a plurality of line segments;

listing each coordinate dimension appearing in at least one line segment of the plurality of line segments in one of a plurality of dimensional dictionaries, each dimensional dictionary of the plurality of dimensional dictionaries corresponding to a dimension of the plurality of dimensions;

representing a linestring of the plurality of linestrings as a set of the line segments using the plurality of dimensional dictionaries; and

performing a data set operation on the data set using the plurality of dimensional dictionaries.

8. The system of claim 7, wherein the data set operation comprises a dictionary compression operation.

9. The system of claim 7, wherein the data set operation comprises a bounding box test operation.

10. The system of claim 7, wherein the data set operation comprises a polygon clipping operation

11. The system of claim 7, wherein the data set operation comprises projecting the line segments of the linestring to a grid using a grid join operation.

12. The system of claim 7, wherein the data set operation comprises a join of linestrings, the join comprising finding all line segments of the joined linestrings that intersect using the plurality of dimensional dictionaries.

13. The system of claim 7, wherein the computer hardware comprises:

a programmable processor; and

a machine-readable medium comprising instructions that, when executed by the programmable processor, cause the programmable processor to perform at least some of the operations.

14. A computer-implemented method comprising:

processing a data set of spatial data having a plurality of dimensions and comprising a plurality of linestrings, the processing comprising decomposing each linestring of the plurality of linestrings into a plurality of line segments;

listing each coordinate dimension appearing in at least one line segment of the plurality of line segments in one of a plurality of dimensional dictionaries, each dimensional dictionary of the plurality of dimensional dictionaries corresponding to a dimension of the plurality of dimensions;

representing a linestring of the plurality of linestrings as a set of the line segments using the plurality of dimensional dictionaries; and

performing a data set operation on the data set using the plurality of dimensional dictionaries.

15. The computer-implemented method of claim 14, wherein the data set operation comprises a dictionary compression operation.

16. The computer-implemented method of claim 14, wherein the data set operation comprises a bounding box test operation.

17. The computer-implemented method of claim 14, wherein the data set operation comprises a polygon clipping operation

18. The computer-implemented method of claim 14, wherein the data set operation comprises projecting the line segments of the linestring to a grid using a grid join operation.

19. The computer-implemented method of claim 14, wherein the data set operation comprises a join of linestrings, the join comprising finding all line segments of the joined linestrings that intersect using the plurality of dimensional dictionaries.

20. The computer-implemented method of claim 14, wherein at least one of the processing, the listing, the representing, and the performing is performed by at least one system comprising computer hardware.