Back to results
US 12,762,121 B2Granted
Multi-stage parallelization model for scalable execution of partitioned row limiting
AssigneeOracle International Corporation
InventorsRithvik Chandan, Srikanth Bellamkonda
Life of this patent
Estimating the term…
Abstract
A database command includes an order-by-key, a hierarchy of partition keys, a top number of partitions to return for each partitioning key level, and a number of rows to return for each partition key value combination. Communications are performed between the worker processes and a query coordinator for initial sorts of the partition keys until all of the worker processes can be used to perform the remaining sorts while avoiding duplicate rows. The results of the initial sorts are distributed to the worker processes in a manner that maintains rows of unique partition key combinations on respective individual worker processes. Each worker process constructs the remaining sorts locally using the rows it receives.
Claims20
A method comprising:
- a plurality of processes executing a database command, wherein said plurality of processes includes a coordinator process, a plurality of producer processes, and a plurality of consumer processes, wherein said database command specifies:
- an order-by key specifying an order to sort a plurality of rows;
- a hierarchy of partition keys by which to partition said plurality of rows, said hierarchy of partition keys comprising L partitioning key levels, each partitioning key level having a respective partition key;
- a respective top P number for respective key level partitions to return for each L partitioning key level;
- an R number of rows to return for each partition key value combination identified for said database command;
- each producer process of said plurality of producer processes generating a respective main sort list ordered by said order-by key;
- in an iteration, of a plurality of iterations, the iteration performed for a current partitioning key level of said hierarchy of partitioning key levels, said plurality of iterations performed beginning with a highest partitioning key level and performed until a criterion is satisfied, each producer process of said plurality of producer processes:
- determining a top P combinations of partition key values of partitions from said respective main sort list as further partitioned by a combination of partition key values of said current partitioning key level and global top P combinations of partition key values previously determined for a most previously performed iteration, if any;
- sending a top R rows for said top P combinations of partition key values to said coordinator process;
- said coordinator process determining global top P combinations of partition key values for said current partitioning key level based on a consolidation of top R rows sent by said plurality of producer processes for said current partitioning key level;
- said coordinator process sending said global top P combinations of partition key values for said current partitioning key level to said plurality of producer processes;
- in response to determining that said criterion is satisfied, each producer process of said plurality of producer processes distributing rows for said top P combinations of partition key values for said current partitioning key level based on hashing top P combinations of partition key values that have been determined in said plurality of iterations for said database command;
- wherein said criterion is based on a cardinality of said top R rows for said top P combinations of partition key values for said current partitioning key level;
- and
- said plurality of consumer processes generating top R rows for said top P combinations of partition key values for any partitioning key level for which top P combinations of partition key values have not been determined in said plurality of iterations for said database command.
12 more elements
One or more non-transitory storage media storing one or more sequences of instructions which, when executed by one or more computing devices, cause:
- a plurality of processes executing a database command, wherein said plurality of processes includes a coordinator process, a plurality of producer processes, and a plurality of consumer processes, wherein said database command specifies:
- an order-by key specifying an order to sort a plurality of rows;
- a hierarchy of partition keys by which to partition said plurality of rows, said hierarchy of partition keys comprising L partitioning key levels, each partitioning key level having a respective partition key;
- a respective top P number for respective key level partitions to return for each L partitioning key level;
- an R number of rows to return for each partition key value combination identified for said database command;
- each producer process of said plurality of producer processes generating a respective main sort list ordered by said order-by key;
- in an iteration, of a plurality of iterations, the iteration performed for a current partitioning key level of said hierarchy of partitioning key levels, said plurality of iterations performed beginning with a highest partitioning key level and performed until a criterion is satisfied, each producer process of said plurality of producer processes:
- determining a top P combinations of partition key values of partitions from said respective main sort list as further partitioned by a combination of partition key values of said current partitioning key level and global top P combinations of partition key values previously determined for a most previously performed iteration, if any;
- sending a top R rows for said top P combinations of partition key values to said coordinator process;
- said coordinator process determining global top P combinations of partition key values for said current partitioning key level based on a consolidation of top R rows sent by said plurality of producer processes for said current partitioning key level;
- said coordinator process sending said global top P combinations of partition key values for said current partitioning key level to said plurality of producer processes;
- in response to determining that said criterion is satisfied, each producer process of said plurality of producer processes distributing rows for said top P combinations of partition key values for said current partitioning key level based on hashing top P combinations of partition key values that have been determined in said plurality of iterations for said database command;
- wherein said criterion is based on a cardinality of said top R rows for said top P combinations of partition key values for said current partitioning key level;
- and
- said plurality of consumer processes generating top R rows for said top P combinations of partition key values for any partitioning key level for which top P combinations of partition key values have not been determined in said plurality of iterations for said database command.
12 more elements
Dependencies are inferred from the claim text.