Efficient computation of order by, order by with limit, min, and max in column-oriented databases

Patent metadata

Field	Value
Publication number	US-11914589-B2
Application number	US-202016805624-A
Country	US
Kind code	B2
Filing date	Feb 28, 2020
Priority date	Feb 28, 2020
Publication date	Feb 27, 2024
Grant date	Feb 27, 2024

Abstract

In some example embodiments, there may be provided a method including detecting a query operator of a predetermined type requiring a sorting or a scanning responsive to the query operator at a column-oriented database; determining a sorted dictionary at the column-oriented database is eligible for direct access by at least checking that the column-oriented database provides sorted dictionary access and that dictionary collation and a collation of the query operator are the same; when the sorted dictionary is eligible, reading directly from the sorted dictionary a batch of sorted values; and processing, based on the batch sorted values read from the sorted dictionary, the query operator.

First claim

What is claimed:

1. A computer-implemented method comprising:
detecting, by one or more processors, at a column-oriented database comprising a main fragment and a delta fragment, a query operator of a predetermined type requiring a sorting of a column of the column-oriented database and a scanning of the column of the column-oriented database in order to determine a response to the query operator, wherein the predetermined type of query operator comprises at least one of an order by, an order by with limit, an order by with top k smallest, an order by with top k largest, a minimum, and a maximum, wherein the main fragment comprises a search tree, and wherein the delta fragment comprises newly-written data optimized for writing and an auxiliary search tree associated with an unsorted dictionary of the delta fragment that provides a sort order over the unsorted dictionary;
determining, by the one or more processors, using an eligibility verification, that a sorted dictionary at the column-oriented database is eligible for sorted direct access, wherein the eligibility verification comprises at least checking that the column-oriented database provides sorted access to the sorted dictionary and identifying that a first sort collation of the sorted dictionary matches a sorting type of a second sort collation of the query operator, the main fragment and the delta fragment being domain-coded to the sorted dictionary;
reading, by the one or more processors, directly from the sorted dictionary a batch of sorted values comprising first values with respect to the sorted access to the sorted dictionary and skipping reading of remaining values, to avoid expensive operations comprising fully scanning the search tree and the auxiliary search tree and unpacking of a fragment at the column-oriented database, the first values comprising value identifiers in a vector result according to the sorting required in the query operator; and
processing, by the one or more processors, based on the batch of sorted values read from the sorted dictionary, the query operator in order to provide a response to the query operator.

2. The computer-implemented method of claim 1 , wherein the batch of sorted values from the sorted dictionary provides a response by a direct read from the sorted dictionary rather than determine the response using the sorting of the column of the column-oriented database and/or the scanning of the column of the column-oriented database, wherein the column is comprised in a main fragment of the column-oriented database.

3. The computer-implemented method of claim 2 , wherein the column-oriented database comprises the main fragment storing the column of data values as a data vector, the sorted dictionary encoding the data values, and an inverted index.

4. The computer-implemented method of claim 3 , wherein the column-oriented database comprises the delta fragment domain-coded to the sorted dictionary and a delta fragment inverted index.

5. The computer-implemented method of claim 1 , wherein the query operator is detected as part of query optimization.

6. The computer-implemented method of claim 1 , wherein checking that the column-oriented database provides access to the sorted dictionary and that a first sort collation of the sorted dictionary and a second sort collation of the query operator match comprises a call to a main fragment of the column-oriented database and a response to the call indicating the column-oriented database is eligible.

7. The computer-implemented method of claim 1 , wherein reading from the sorted dictionary the batch of sorted values comprises storing a last, or a next, value read from the sorted dictionary to enable a second batch read of the sorted dictionary.

8. The computer-implemented method of claim 1 , wherein reading directly from the sorted dictionary enables to avoid, in response to the query operator, a sort or a scan of a fragment at the column-oriented database.

9. A system comprising:
at least one processor; and
at least one memory comprising a program code which when executed by the at least one processor causes operations comprising:
detecting at a column-oriented database comprising a main fragment and a delta fragment, a query operator of a predetermined type requiring a sorting of a column of the column-oriented database and a scanning of the column of the column-oriented database in order to determine a response to the query operator, wherein the predetermined type of query operator comprises at least one of an order by, an order by with limit, an order by with top k smallest, an order by with top k largest, a minimum, and a maximum, wherein the main fragment comprises a search tree, and wherein the delta fragment comprises newly-written data optimized for writing and an auxiliary search tree associated with an unsorted dictionary of the delta fragment that provides a sort order over the unsorted dictionary;
determining using an eligibility verification, that a sorted dictionary at the column-oriented database is eligible for sorted direct access, wherein the eligibility verification comprises at least checking that the column-oriented database provides sorted access to the sorted dictionary and identifying that a first sort collation of the sorted dictionary matches a sorting type of a second sort collation of the query operator, the main fragment and the delta fragment being domain-coded to the sorted dictionary;
reading directly from the sorted dictionary a batch of sorted values comprising first values with respect to the sorted access to the sorted dictionary and skipping reading of remaining values, to avoid expensive operations comprising fully scanning the search tree and the auxiliary search tree and unpacking of a fragment at the column-oriented database, the first values comprising value identifiers in a vector result according to the sorting required in the query operator; and
processing, based on the batch of sorted values read from the sorted dictionary, the query operator in order to provide a response to the query operator.

10. The system of claim 9 , wherein the batch of sorted values from the sorted dictionary provides a response by a direct read from the sorted dictionary rather than determine the response using the sorting of the column of the column-oriented database and/or the scanning of the column of the column-oriented database, wherein the column is comprised in a main fragment of the column-oriented database.

11. The system of claim 10 , wherein the column-oriented database comprises the main fragment storing the column of data values as a data vector, the sorted dictionary encoding the data values, and an inverted index.

12. The system of claim 11 , wherein the column-oriented database comprises the delta fragment domain-coded to the sorted dictionary and a delta fragment inverted index.

13. The system of claim 9 , wherein the query operator is detected as part of query optimization.

14. The system of claim 9 , wherein checking that the column-oriented database provides access to the sorted dictionary and that a first sort collation of the sorted dictionary and a second sort collation of the query operator match comprises a call to a main fragment of the column-oriented database and a response to the call indicating the column-oriented database is eligible.

15. The system of claim 9 , wherein reading from the sorted dictionary the batch of sorted values comprises storing a last, or a next, value read from the sorted dictionary to enable a second batch read of the sorted dictionary.

16. The system of claim 9 , wherein reading directly from

Assignees

• Sap Se

Inventors

• Horn Oliver
• Legler Thomas
• Schulze Robert

Classifications

• G06F16/24537 Primary

  of operators · CPC title

• G06F16/221

  Column-oriented storage; Management thereof · CPC title

• G06F16/24556

  Aggregation; Duplicate elimination · CPC title

• G06F16/24557

  Efficient disk access during query execution · CPC title

• G06F7/24

  Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence) · CPC title