Column store optimization using telescope columns

• US 9,740,719 B2
• Filed: 07/07/2014
• Issued: 08/22/2017
• 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
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): HOANG, HAU HAI
• Application Number:
  US14/325,262
• Publication Number:
  US 20160004735A1
• Time in Patent Office: 1,142 Days
• Field of Search: None
• 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 non-transitory 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 column containing a plurality of linestrings, the processing comprising decomposing each linestring of the plurality of linestrings into a plurality of line segments, each line segment of the plurality of line segment having a first vertex and a second vertex;

listing each coordinate dimension value 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 the column containing the plurality of linestring as a set of index vectors, the set of index vectors comprising an index vector for each dimension of the plurality of dimensions for each of the first and second vertices of the plurality of line segments, each index vector of the set of index vectors comprising value identifiers that reference the coordinate dimension values in the dimensional dictionary of the plurality of dimensional dictionaries corresponding to the dimension represented by the index vector; and

performing a data set operation on the data set using the plurality of dimensional dictionaries, the data set operation comprising a join of linestrings, the join comprising finding all line segments of the joined linestrings that intersect using the plurality of dimensional dictionaries, the finding comprising;

defining an index cluster that comprises an interval within a dimensional dictionary of the plurality of dimensional dictionaries, the interval including a coordinate value of one of the vertices of a line segment of the plurality of line segments, and

identifying possibly intersecting other line segments of the plurality of line segments as those line segments for which a comparison of the index cluster with another index vector of the set of index vectors return a true value.

2. The computer program product of claim 1, wherein the data set operation further 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 further comprises a polygon clipping operation.

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

6. 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 column containing a plurality of linestrings, the processing comprising decomposing each linestring of the plurality of linestrings into a plurality of line segments, each line segment of the plurality of line segments having a first vertex and a second vertex;

listing each coordinate dimension value 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 the column containing the plurality of linestrings as a set of index vectors, the set of index vectors comprising an index vector for each dimension of the plurality of dimensions for each of the first and second vertices of the plurality of line segments, each index vector of the set of index vectors comprising value identifiers that reference the coordinate dimension values in the dimensional dictionary of the plurality of dimensional dictionaries corresponding to the dimension represented by the index vector; and

performing a data set operation on the data set using the plurality of dimensional dictionaries, the data set operation comprising a join of linestring, the join comprising finding all line segments of the joined linestrings that intersect using the plurality of dimensional dictionaries, the finding comprising;

defining an index cluster that comprises an interval within a dimensional dictionary of the plurality of dimensional dictionaries, the interval including a coordinate value of one of the vertices of a line segments of the plurality of line segments, and

identifying possibly intersecting other line segments of the plurality of line segments as those line segments for which a comparison of the index cluster with anther index vector of the set of index vectors returns a true value.

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

8. The system of claim 6, wherein the data set operation further comprises a bounding box test operation.

9. The system of claim 6, wherein the data set operation further comprises a polygon clipping operation.

10. The system of claim 6, wherein the data set operation further comprises projecting the line segments of the linestring to a grid using a grid-join operation.

11. The system of claim 6, 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.

12. A computer-implemented method comprising:

processing a data set of spatial data having a plurality of dimensions and comprising a column containing a plurality of linestrings, the processing comprising decomposing each linestring of the plurality of linestring into a plurality of line segments, each line segment of the plurality of line segments having a first vertex and a second vertex;

listing each coordinate dimension value 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 the column containing the plurality of linestrings as a set of index vectors, the set of index vectors comprising an index vector for each dimension of the plurality of dimensions for each of the first and second vertices of the plurality of line segments, each index vector of the set of index vectors comprising value identifiers that reference the coordinate dimension values in the dimensional dictionary of the plurality of dimensional dictionaries corresponding to the dimension represented by the index vector; and

performing a data set operation on the data set using the plurality of dimensional dictionaries, the data set operation comprising a join of linestring, the join comprising finding all line segments of the joined linestrings that intersect using the plurality of dimensional dictionaries, the finding comprising;

defining an index cluster that comprises an interval within a dimensional dictionary of the plurality of dimensional dictionaries, the interval including a coordinate value of one of the vertices of a line segment of the plurality of line segments, and

identifying possibly intersecting other line segments of the plurality of line segment as those line segment for which a comparison of the index cluster with another index vector of the set of index vectors returns a true value.

13. The computer-implemented method of claim 12, wherein the data set operation further comprises a dictionary compression operation.

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

15. The computer-implemented method of claim 12, wherein the data set operation further comprises a polygon clipping operation.

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

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