Rescheduling transactions in a database system

• US 6,990,503 B1
• Filed: 04/12/2002
• Issued: 01/24/2006
• Est. Priority Date: 04/12/2002
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Luo, Gang, Ellmann, Curt J., Watzke, Michael W., Naughton, Jeffrey F.
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US10/121,190
• Time in Patent Office: 1,383 Days
• Field of Search: 707 1- 10, 707200-205, 710/113, 711/154, 705/26
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity

Abstract

A database system includes a transaction rescheduling mechanism that reorders pending transactions based on whether one or more of the pending transactions conflict with any transactions that have been scheduled for execution. In one arrangement, the received pending transactions are stored in a first queue. The transactions that are scheduled for execution are stored in a second queue. The transactions are moved from the first queue to the second queue based on the reordering by the transaction rescheduling mechanism.

Claims

1. An article comprising at least one storage medium containing instructions that when executed cause a computer-implemented database system to:

receive a plurality of pending transactions; and

reorder the received pending transactions based on determining conflicts between the received pending transactions and other transactions scheduled for execution.

2. The article of claim 1, wherein the instructions when executed cause the database system to:

store the other transactions scheduled for execution in a first queue; and

move the received pending transactions to the first queue in an order according to the reordering.

3. The article of claim 2, wherein the instructions when executed cause the database system to store the received pending transactions in a second queue,

wherein moving the received pending transactions comprises moving the pending transactions from the second queue to the first queue.

4. The article of claim 1, wherein the instructions when executed cause the database system to determine conflicts between the received pending transactions and other transactions based on checking locks requested by the received pending transactions and by the other transactions.

5. The article of claim 4, wherein the instructions when executed cause the database system to receive the plurality of pending transactions by receiving execution plans from an optimizer in the database system, the execution plans generated by the optimizer in response to received queries.

6. The article of claim 5, wherein the instructions when executed cause the database system to invoke a re-scheduler to reorder the received pending transactions,

the re-scheduler sending the reordered transactions to a scheduler in the database system.

7. The article of claim 4, wherein the instructions when executed cause the database system to:

store a view that is based on plural base relations;

define a relationship between the base relations, the relationship indicating conflicts between base relations due to their association with the view;

wherein determining conflicts between the received pending transactions and other transactions is based on the defined relationship of base relations.

8. The article of claim 7, wherein the instructions when executed cause the database system to define the relationship by defining a conflict graph, the conflict graph having plural components representing respective plural base relations,

wherein an edge is defined between every pair of components representing the base relations of the view.

9. The article of claim 8, wherein the instructions when executed cause the database system to:

store other base relations,

wherein each of the components of the conflict graph representing the other base relations are not connected by an edge to the components representing the base relations of the view.

10. The article of claim 9, wherein the instructions when executed cause the database system to:

for a first received pending transaction that updates a first base relation, identify the first transaction as a transaction that can be scheduled for execution if the first transaction does not conflict with the other transactions scheduled for execution.

11. The article of claim 10, wherein the instructions when executed cause the database system to identify the first transaction as not conflicting if the following is satisfied:

for certain of the other transactions that update a first set of one or more base relations, there is no edge in the conflict graph between the first base relation and any of the first set of one or more base relations; and

none of the other transactions read any view defined on the first base relation.

12. The article of claim 11, wherein the instructions when executed cause the database system to:

for a second received pending transaction that reads the first base relation, identify the second transaction as a transaction that can be scheduled for execution if the following condition is satisfied;

either (a) the second transaction reads the first base relation using a table-level shared lock on the first base relation and none of the other transactions updates the first base relation, or (b) the second transaction reads the first base relation using a shared value lock on the first base relation and none of the other transactions updates the first base relation by a table-level exclusive lock.

13. The article of claim 12, wherein the instructions when executed cause the database system to:

for a third received pending transaction that reads the view, identify the third transaction as a transaction that can be scheduled for execution if none of the other transactions update any base relation of the view.

14. The article of claim 1, wherein the instructions when executed cause the database system to:

store a data structure to indicate the types of locks placed on each of plural base relations; and

access the data structure to determine conflict.

15. The article of claim 14, wherein the instructions when executed cause the database system to:

store the data structure containing indicators to indicate placement of a table-level exclusive lock, an exclusive value lock, a table-level shared lock, and a shared value lock.

16. The article of claim 15, wherein the instructions when executed cause the database system to increment the indicators depending on a number of locks placed by transactions on each base relation.

17. The article of claim 1, wherein the database system includes plural nodes, each node having a re-scheduler, and

wherein reordering the received pending transactions is performed by one or more of the re-schedulers.

18. The article of claim 17, wherein the instructions when executed cause the database system to:

assign a first node to perform reordering of transactions on a first set of base relations, and assign a second node to perform reordering of transactions on a second set of base relations.

19. A method of scheduling transactions in a computer-implemented database system, comprising:

receiving pending transactions in a first order;

determining any conflicts between the received pending transactions and transactions scheduled for execution; and

in response to determining conflicts, reordering the received pending transactions so that the received pending transactions are provided for execution scheduling in a second order different from the first order.

20. The method of claim 19, further comprising storing transactions scheduled for execution in a queue,

the method further comprising moving the received pending transactions into the queue in the second order.

21. The method of claim 19, wherein the database system has plural nodes, each node having a re-scheduler,

wherein the reordering is performed by the plural re-schedulers.

22. The method of claim 21, further comprising:

determining that a first received pending transaction operates on a first base relation; and

sending the first received pending transaction to a first re-scheduler to reorder based on the determining.

23. The method of claim 22, further comprising:

determining that a second received pending transaction operates on a second base relation; and

sending the second received pending transaction to a second re-scheduler different from the first re-scheduler to reorder based on determining that the second received pending transaction operates on the second base relation.

24. The method of claim 19, further comprising:

defining a relationship having plural components, each component representing a corresponding base relation,

wherein the relationship indicates conflicts between base relations due to their associations with views;

defining one or more conflicts between or among a first set of base relations of a first view; and

defining one or more conflicts between or among a second set of base relations of a second view.

25. The method of claim 24, further comprising sending a given received pending transaction to a selected one of the re-schedulers based on whether a first base relation operated on by the given received pending transaction belongs to the first set or second set.

26. The method of claim 25, further comprising sending a second received pending transaction that operates on a second base relation to another selected re-scheduler based on determining that the second base relation belongs to a different set than the first base relation.

27. The method of claim 24, further comprising defining conflicts between or among base relations of one or more further sets.

28. A database system, comprising:

one or more processors, the one or more processors to execute a re-scheduler to receive pending transactions; and

the one or more processors to execute a scheduler to process a set of transactions,

the re-scheduler to reorder the pending transactions based on whether the pending transactions request locks that conflict with locks of the set of transactions processed by the scheduler.

29. The database system of claim 28, further comprising a storage to store a first queue and a second queue, the first queue to store the pending transactions, and the second queue to store the set of transactions processed by the scheduler.

30. The database system of claim 29, the re-scheduler to select one of the received pending transactions from the first queue to move to the second queue in performing the reordering.

31. The database system of claim 30, the re-scheduler to receive the pending transactions in a first order, and the re-scheduler to move the pending transactions from the first queue to the second queue in a second, different order.

32. The database system of claim 31, wherein the first queue includes a first segment implemented as a round-robin queue, the re-scheduler to scan through the round-robin queue to find a pending transaction that does not conflict with any transaction in the set.

33. The database system of claim 32, wherein the first queue has a length, the first segment having a length shorter than the length of the first queue.

34. The database system of claim 33, the re-scheduler to scan the first segment at an element that follows the last element scanned in a prior scan.

35. The database system of claim 31, the re-scheduler to modify its processing in response to detecting that a given pending transaction has remained in the first queue for more than a predefined number of scan cycles.

36. The database system of claim 28, further comprising plural nodes, each node having a re-scheduler, different re-schedulers to perform reordering of different groups of transactions.

37. An article comprising at least one storage medium containing instructions that when executed cause a computer-implemented database system to:

receive, in a first order, pending transactions in a first queue;

store transactions to be scheduled for execution in a second queue;

scan the pending transactions in the first queue to determine any lock conflicts between the pending transactions in the first queue and the transactions in the second queue;

move pending transactions from the first queue to the second queue if the pending transactions do not have a lock conflict with the transactions in the second queue,

wherein the pending transactions are moved to the second queue in an order different than the first order;

remove transactions from the second queue as they are completed; and

move further pending transactions to the second queue as transactions are removed from the first queue.