TQ distribution that increases parallism by distributing one slave to a particular data block

• US 7,293,011 B1
• Filed: 11/27/2002
• Issued: 11/06/2007
• Est. Priority Date: 11/27/2002
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Thusoo, Ashish, Cruanes, Thierry, Bedi, Harmeek
• Primary Examiner(s): Pham; Hung Q
• Application Number:
  US10/305,744
• Time in Patent Office: 1,805 Days
• Field of Search: 707/2, 707/8, 707/10, 718/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

Provided herein are techniques that may be used to dramatically increase parallism for distributed DML operations. The work of distributed DML operations are distributed in a way that avoids self-dead locks, by ensuring that, for a given data block, no more than one slave is assigned to modify a row that is wholly contained by the data block or whose head row piece is contained by the data block. Assigning slaves in this way not only allows more slaves to be assigned to modify a partition, but allows for greater flexibility in load balancing.

Claims

1. A method, the method comprising the computer-implemented steps of:

assigning a first plurality of slaves and a second plurality of slaves to participate in execution of a distributed operation, wherein the distributed operation involves accessing base rows that are contained in at least one table and that are stored in a plurality of data blocks;

wherein said first plurality of slaves generates output rows for processing by said second plurality of slaves;

wherein said generated output rows contain data from said accessed base rows;

generating a data structure that indicates associations of said second plurality of slaves with said plurality of data blocks;

distributing said generated output rows to said second plurality of slaves based on;

particular data blocks that contain the accessed base rows of the generated output rows; and

the associations of said second plurality of slaves with said plurality of data blocks;

wherein a first slave of said first plurality of slaves produces a first output row having a first base row from a certain data block of said plurality of data blocks;

wherein a second slave of said first plurality of slaves produces a second output row having a second base row from said certain data block of said plurality of data blocks; and

wherein distributing said output rows includes;

assigning, based on the generated data structure and said certain data block containing said first base row, said first output row to a certain slave of said second plurality of slaves that is associated with said certain data block; and

assigning, based on the generated data structure and said certain data block containing said second base row, said second output row to said certain slave of said second plurality of slaves that is associated with said certain data block.

2. The method of claim 1, wherein:

each base row contained in said certain data block is associated with a row-id containing data identifying said certain data block; and

the step of assigning said first output row includes assigning said first output row to said certain slave based on the row-id associated with the first base row of said first output row.

3. The method of claim 1, wherein:

the first output row is associated with a first row-id and the second output row is associated with a second row-id, wherein said first row-id and said second row-id contain data identifying said certain data block;

the generated data structure comprises a hash table that includes entries, wherein each entry in said hash table is associated with a hash value from a set of hash values and a slave from said second plurality of slaves; and

wherein the step of assigning includes;

applying a hash function to the data identifying said certain data block from the first row-id to generate a particular hash value,

applying said hash function to the data identifying said certain data block from the second row-id to generate said particular hash value,

assigning said first output row to said certain slave associated with the entry in said hash table associated with the particular hash value, and

assigning said second output row to said certain slave associated with the entry in said hash table associated with the particular hash value.

4. The method of claim 1, wherein the steps further include another slave from said second plurality of slaves modifying a data in said certain data block, wherein said association does not associate said another slave with the certain data block.

5. The method of claim 4, wherein said another slave is assigned a particular row to modify that is stored in another data block other than said certain data block.

6. The method of claim 5, wherein said particular row is comprised of a row piece stored in said certain data block and said another data block.

7. The method of claim 1, wherein:

said distributed operation is a distributed transaction involving DML operations,

wherein said distributed transaction includes subtransactions for each slave of said second plurality of slaves; and

the steps further include committing said distributed transaction and each subtransaction of said subtransactions.

8. The method of claim 7, wherein:

said distributed transaction is executed by a database system;

the steps further include said database system limiting the quantity of uncommitted transactions that concurrently modify data in said certain data block to a threshold number; and

the number of slaves in said second plurality of slaves is greater than said threshold number.

9. The method of claim 8, wherein:

said at least one table is comprised of one or more table partitions;

said certain data block stores rows that belong to a partition; and

the steps further include assigning a subset of said second plurality of slaves to modify data in said partition, wherein the number of slaves in said subset is greater than said threshold number.

10. The method of claim 8, wherein:

said certain data block contains a plurality of locks, wherein the number of locks in said plurality of locks is said threshold number; and

the steps further include said database system causing a process executing a transaction that includes modifications to at least a portion of a row stored in the certain data block to acquire a lock from said plurality of locks for the transaction.

11. A computer-readable storage medium storing one or more sequences of instructions for executing distributed operations, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

assigning a first plurality of slaves and a second plurality of slaves to participate in execution of a distributed operation, wherein the distributed operation involves accessing base rows that are contained in at least one table and that are stored in a plurality of data blocks;

wherein said first plurality of slaves generates output rows for processing by said second plurality of slaves;

wherein said generated output rows contain data from said base rows;

generating a data structure that indicates associations of said second plurality of slaves with said plurality of data blocks;

distributing said generated output rows to said second plurality of slaves based on;

particular data blocks that contain the accessed base rows of the generated output rows; and

the associations of said second plurality of slaves with said plurality of data blocks;

wherein a first slave of said first plurality of slaves produces a first output row having a first base row from a certain data block of said plurality of data blocks;

wherein a second slave of said first plurality of slaves produces a second output row having a second base row from said certain data block of said plurality of data blocks; and

wherein distributing said output rows includes;

assigning, based on the generated data structure and said certain data block containing said first base row, said first output row to a certain slave of said second plurality of slaves that is associated with said certain data block; and

assigning, based on the generated data structure and said certain data block containing said second base row, said second output row to said certain slave of said second plurality of slaves that is associated with said certain data block.

12. The computer-readable storage medium of claim 11, wherein:

each base row contained in said certain data block is associated with a row-id containing data identifying said certain data block; and

the step of assigning said first output row includes assigning said first output row to said certain slave based on the row-id associated with the first base row of said first output row.

13. The computer-readable storage medium of claim 11, wherein:

the first output row is associated with a first row-id and the second output row is associated with a second row-id, wherein said first row-id and said second row-id contain data identifying said certain data block;

the generated data structure comprises a hash table that includes entries, wherein each entry in said hash table is associated with a hash value from a set of hash values and a slave from said second plurality of slaves; and

wherein the step of assigning includes;

applying a hash function to the data identifying said certain data block from the first row-id to generate a particular hash value,

applying said hash function to the data identifying said certain data block from the second row-id to generate said particular hash value,

assigning said first output row to said certain slave associated with the entry in said hash table associated with the particular hash value, and

assigning said second output row to said certain slave associated with the entry in said hash table associated with the particular hash value.

14. The computer-readable storage medium of claim 11, wherein the steps further include another slave from said second plurality of slaves modifying a data in said certain data block, wherein said association does not associate said another slave with the certain data block.

15. The computer-readable storage medium of claim 14, wherein said another slave is assigned a particular row to modify that is stored in another data block other than said certain data block.

16. The computer-readable storage medium of claim 15, wherein said particular row is comprised of a row piece stored in said certain data block and said another data block.

17. The computer-readable storage medium of claim 11, wherein:

said distributed operation is a distributed transaction involving DML operations,

wherein said distributed transaction includes subtransactions for each slave of said second plurality of slaves; and

the steps further include committing said distributed transaction and each subtransaction of said subtransactions.

18. The computer-readable storage medium of claim 17, wherein:

said distributed transaction is executed by a database system;

the steps further include said database system limiting the quantity of uncommitted transactions that concurrently modify data in said certain data block to a threshold number; and

the number of slaves in said second plurality of slaves is greater than said threshold number.

19. The computer-readable storage medium of claim 18,

wherein:

said at least one table is comprised of one or more table partitions;

said certain data block stores rows that belong to a partition; and

the steps further include assigning a subset of said second plurality of slaves to modify data in said partition, wherein the number of slaves in said subset is greater than said threshold number.

20. The computer-readable storage medium of claim 18, wherein:

said certain data block contains a plurality of locks, wherein the number of locks in said plurality of locks is said threshold number; and

the steps further include said database system causing a process executing a transaction that includes modifications to at least a portion of a row stored in the certain data block to acquire a lock from said plurality of locks for the transaction.