US 10,762,071 B2Granted

Value-ID-based sorting in column-store databases

AssigneeSap SE

InventorsRobert Schulze, Thomas Peh

Life of this patent

Estimating the term…

Loading patent…

Abstract

Innovations in performing sort operations for dictionary-compressed values of columns in a column-store database using value identifiers (“IDs”) are described. For example, a database system includes a data store and an execution engine. The data store stores values at positions of a column A dictionary maps distinct values to corresponding value IDs. An inverted index stores, for each of the corresponding value IDs, a list of those of the positions that contain the associated distinct value. The execution engine processes a request to sort values at an input set of the positions and identify an output set of the positions for sorted values. In particular, the execution engine iterates through positions stored in the lists of the inverted index. For a given position, the execution engine checks if the given position is one of the input set and, if so, adds the given position to the output set.

Claims30

Dependent claims

A computer system comprising one or more processing units and a memory, wherein the computer system implements a database system comprising:

a data store configured to store values at positions of a column using structures that comprise:
a sorted dictionary structure configured to map distinct values, among the values at the positions of the column, to corresponding value IDs, the distinct values being sorted in the sorted dictionary structure according to a first sort criteria;
and
a sorted inverted index structure, sorted according to the first sort criteria, comprising a plurality of sequential elements, each sequential element of the plurality of sequential elements representing a value ID, each sequential element of the plurality of sequential elements configured to store, for each of the corresponding value IDs mapped to the distinct values in the sorted dictionary structure, a list of those of the positions of the column that contain that distinct value for the value ID, at least one of the lists comprising a plurality of column positions, wherein a number of sequential elements in the sorted inverted index structure is equal to a number of value IDs in the sorted dictionary structure;
and
an execution engine configured to process a request to sort, using the first sort criteria, values for an input set of the positions of the column and identify an output set of the positions of the column for at least some of the sorted values, by performing operations that include, as part of sorting the values at the input set of the positions of the column, iterating through at least some positions stored in the lists of the inverted index structure, the iterating comprising, for a first sequential element of the sorted inverted index structure:
determining a first column position specified in the list for the first sequential element;
determining that the first column position specified in the list is a member of the input set of the positions of the column by checking whether the positions of the columns, respectively, are in the input set;
adding the first column position to the output set;
and
analyzing a second column position specified in the list for the first sequential element to determine whether the second column position specified in the list for the first sequential element is a member of the input set of the positions of the column.

8 more elements

One or more non-transitory computer-readable media storing computer-executable instructions for causing a computer system, when programmed thereby, to perform sorting, for a data store configured to store values at positions of a column using structures that comprise:

(i) a sorted dictionary structure configured to map distinct values, among the values at the positions of the column, to corresponding value IDs, the distinct values being sorted in the sorted dictionary structure according to a first sort criteria;
and
(ii) a sorted inverted index structure, sorted according to the first sort criteria, comprising a plurality of sequential elements, each sequential element of the plurality of sequential elements representing a value ID, each sequential element of the plurality of sequential elements configured to store, for each of the corresponding value IDs mapped to the distinct values in the dictionary structure, a list of those of the positions of the column that contain the distinct value for the value ID, at least one of the lists comprising a plurality of column positions, wherein a number of sequential elements in the sorted inverted index structure is equal to a number of value IDs in the sorted dictionary structure;
wherein the sorting comprises:
receiving a request to sort values for an input set of the positions of the column and identify an output set of the positions of the column for at least some of the sorted values;
and
processing the request by performing operations that include, as part of sorting the values at the input set of the positions of the column, iterating through at least some positions stored in the lists of the inverted index structure, the iterating comprising, for a first sequential element of the sorted inverted index structure:
determining a first column position specified in the list for the first sequential element;
determining that the first column position specified in the list is a member of the input set of the positions of the column by checking whether the positions of the columns, respectively, are in the input set;
adding the first column position to the output set;
and
analyzing a second column position specified in the list for the first sequential element to determine whether the second column position specified in the list for the first sequential element is a member of the input set of the positions of the column.

9 more elements

A method, implemented in a computer system that includes a data store configured to store values at positions of a column using structures that comprise:

(i) a sorted dictionary structure configured to map distinct values, among the values at the positions of the column, to corresponding value IDs, the distinct values being sorted in the sorted dictionary structure according to a first sort criteria;
and
(ii) a sorted inverted index structure, sorted according to the first sort criteria, comprising a plurality of sequential elements, each sequential element of the plurality of sequential elements representing a value ID, each sequential element of the plurality of sequential elements configured to store, for each of the corresponding value IDs mapped to the distinct values in the dictionary structure, a list of those of the positions of the column that contain the distinct value for the value ID, at least one of the lists comprising a plurality of column positions, wherein a number of sequential elements in the sorted inverted index is equal to a number of value IDs in the sorted dictionary structure;
the method comprising:
receiving a request to sort values for an input set of the positions of the column and identify an output set of the positions of the column for at least some of the sorted values;
and
processing the request by performing operations that include, as part of sorting the values at the input set of the positions of the column, iterating through at least some positions stored in the lists of the inverted index structure, the iterating comprising, for a first sequential element of the sorted inverted index structure:
determining a first column position specified in the list for the first sequential element;
determining that the first column position specified in the list is a member of the input set of the positions of the column by checking whether the positions of the columns, respectively, are in the input set;
adding the first column position to the output set;
and
analyzing a second column position specified in the list for the first sequential element to determine whether the second column position specified in the list for the first sequential element is a member of the input set of the positions of the column.

9 more elements

Dependencies are inferred from the claim text.