Column store optimization using telescope columns

Patent metadata

Field	Value
Publication number	US-9740719-B2
Application number	US-201414325262-A
Country	US
Kind code	B2
Filing date	Jul 7, 2014
Priority date	Jul 7, 2014
Publication date	Aug 22, 2017
Grant date	Aug 22, 2017

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.

First claim

What is claimed is:

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

Assignees

• Kazmaier Gerrit Simon
• Gildhoff Hinnerk
• Volker Lars
• Grouisborn Tim
• Sap Se

Inventors

• Kazmaier Gerrit Simon
• Gildhoff Hinnerk
• Volker Lars
• Grouisborn Tim

Classifications

• G06F16/221 Primary

  Column-oriented storage; Management thereof · CPC title

• G06F17/30315 Primary

  Physics · mapped topic