US 10,706,055 B2Granted

Partition aware evaluation of top-N queries

AssigneeOracle International Corporation

InventorsGong Zhang, Sam Idicula, Michael Duller, Nitin Kunal

Life of this patent

Estimating the term…

Loading patent…

Abstract

Techniques are described for executing an analytical query with a top-N clause. In an embodiment, a stream of tuples are received by each of the processing units from a data source identified in the query. The processing unit uses a portion of a received tuple to identify the partition that the tuple is assigned to. For each partition, the processing unit maintains a top-N data store that stores an N number of received tuples that match the criteria of top N tuples according to the query. The received tuple is compared to the N number of tuples to determine whether to store the received tuple and discard an already stored tuple, or to discard the received tuple. After all the tuples have been similarly processed by the processing units, all the top-N data stores for each partition are merged, yielding the top N number of tuples for each partition to return as a result of the query.

Claims24

Dependent claims

A computer-implemented method comprising:

receiving a query with a request to select a particular number of rows in each of a plurality of data partitions of a data set of tuples, the request specifying:
a partition key of the data set by which values to partition the data set into the plurality of data partitions, and
a sort key of the data set by which values to sort rows for said each of the plurality of data partitions and a particular order in which to sort;
executing the query by a plurality of processing units, the executing comprising:
a processing unit of the plurality of processing units maintaining a respective set of tuple data stores, wherein each tuple data store in the respective set of tuple data stores corresponds to a different partition key value of the partition key;
said processing unit maintaining a respective set of sort key data stores that corresponds to the respective set of tuple data stores, wherein each sort key data store in the respective set of sort key data stores corresponds to a different partition key value of the partition key;
based on values for the partition key of tuples of the data set, said processing unit partitioning tuples from the data set into said respective set of tuple data stores corresponding to a plurality of unique values of the partition key;
said processing unit storing sort key values of the tuples of the data set in said respective set of sort key data stores;
wherein each sort key value in said each sort key data store, of said respective set of sort key data stores, is associated with a corresponding tuple in said each tuple data store of said respective set of tuple data stores;
wherein the respective set of sort key data stores is stored in respective memory of said processing unit, said respective memory having an affinity with said processing unit;
and
generating a respective result set for a unique partitioning key value of the partition key by merging a particular tuple data store from the respective set of tuple data stores that corresponds to the unique partitioning key value and that is maintained by the processing unit with one or more other tuple data stores that correspond to the same unique partitioning key value and that are maintained by one or more other processing units of the plurality of processing units thereby generating a merged tuple data store that corresponds to the unique partition key value and comprises the particular number of tuples.

9 more elements

One or more non-transitory storage media storing instructions, which, when executed by one or more hardware processors, cause:

receiving a query with a request to select a particular number of rows in each of a plurality of data partitions of a data set of tuples, the request specifying:
a partition key of the data set by which values to partition the data set into the plurality of data partitions, and
a sort key of the data set by which values to sort rows for said each of the plurality of data partitions and a particular order in which to sort;
executing the query by a plurality of processing units, the executing comprising:
a processing unit of the plurality of processing units maintaining a respective set of tuple data stores, wherein each tuple data store in the respective set of tuple data stores corresponds to a different partition key value of the partition key;
said processing unit maintaining a respective set of sort key data stores that corresponds to the respective set of tuple data stores, wherein each sort key data store in the respective set of sort key data stores corresponds to a different partition key value of the partition key;
based on values for the partition key of tuples of the data set, said processing unit partitioning tuples from the data set into said respective set of tuple data stores corresponding to a plurality of unique values of the partition key;
said processing unit storing sort key values of the tuples of the data set in said respective set of sort key data stores;
wherein each sort key value in said each sort key data store, of said respective set of sort key data stores, is associated with a corresponding tuple in said each tuple data store of said respective set of tuple data stores;
wherein the respective set of sort key data stores is stored in respective memory of said processing unit, said respective memory having an affinity with said processing unit;
and
generating a respective result set for a unique partitioning key value of the partition key by merging a particular tuple data store from the respective set of tuple data stores that corresponds to the unique partitioning key value and that is maintained by the processing unit with one or more other tuple data stores that correspond to the same unique partitioning key value and that are maintained by one or more other processing units of the plurality of processing units thereby generating a merged tuple data store that corresponds to the unique partition key value and comprises the particular number of tuples.

9 more elements

Dependencies are inferred from the claim text.