Neighborhood locking technique for increasing concurrency among transactions

• US 7,269,588 B1
• Filed: 09/24/2003
• Issued: 09/11/2007
• Est. Priority Date: 09/24/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Listgarten, Sherry, Haldar, Sibsankar, Verma, Sanjay, Hoang, Chi-Kim
• Primary Examiner(s): Kimm; Chong H.
• Assistant Examiner(s): Vautrot; Dennis L.
• Application Number:
  US10/671,297
• Time in Patent Office: 1,448 Days
• Field of Search: 707 1- 10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

New lock modes are based on the concept of neighborhoods and are applied to spaces in indexes. The new lock modes include a Read, or shared, neighborhood (Snei) lock mode and a Write neighborhood (Xnei) that enhance concurrency among non-serializable transactions.

Claims

1. A database management system, comprising:

a processor providing a neighborhood locking scheme for a neighborhood of free space adjacent to and associated with a data item and extending to an adjacent data item, the neighborhood locking scheme concurrently creating both a first locking mode for the data item, while at the same time creating a second locking mode for the neighborhood associated with the data item;

where the first locking mode when first held on the data item determines an associated set of predetermined access restrictions for the data item and determines an associated different set of predetermined access restrictions for the neighborhood associated with the data item;

where the second locking mode when first held on the neighborhood determines the associated set of predetermined access restrictions for the neighborhood and determines the associated different set of predetermined access restrictions for the data item;

wherein the neighborhood locking scheme includes a neighborhood lock mode that grants a first transaction an exclusive lock on a first tuple and a weak lock on the neighborhood associated with the first tuple; and

wherein the neighborhood lock mode grants a second concurrent transaction an exclusive lock on a second tuple located in the neighborhood of the first tuple.

4. A database management system according to claim 1 wherein the neighborhood corresponds to free space between tuples in a table.

5. A database management system according to claim 4 wherein the tuples in the table are identified through an index.

20. A database management system according to claim 1 wherein the first tuple is a first row in a table and the second tuple is a second row in the table and the first transaction can delete the first row and the second transaction can delete the second row simultaneously.

2. A database management system, comprising:

a processor providing a neighborhood locking scheme for a neighborhood of free space adjacent to and associated with a data item and extending to an adjacent data item, the neighborhood locking scheme concurrently creating both a first locking mode for the data item, while at the same time creating a second locking mode for the neighborhood associated with the data item;

where the first locking mode when first held on the data item determines an associated set of predetermined access restrictions for the data item and determines an associated different set of predetermined access restrictions for the neighborhood associated with the data item;

where the second locking mode when first held on the neighborhood determines the associated set of predetermined access restrictions for the neighborhood and determines the associated different set of predetermined access restrictions for the data item;

wherein the neighborhood locking scheme;

allows a non-serializable scan of the data item with a first transaction while allowing a concurrent non-serializable lock on the neighborhood with a second transaction;

allows a serializable scan of the data item with the first transaction while preventing a concurrent non-serializable lock on the neighborhood with the second transaction;

allows a non-serializable lock on the neighborhood with the first transaction while allowing a concurrent non-serializable scan on the data item with the second transaction; and

allows a non-serializable lock on the neighborhood with the first transaction while preventing a concurrent serializable scan on the data item with the second transaction.

3. A database management system, comprising:

a processor providing a neighborhood locking scheme for a neighborhood of free space adjacent to and associated with a data item and extending to an adjacent data item, the neighborhood locking scheme concurrently creating both a first locking mode for the data item, while at the same time creating a second locking mode for the neighborhood associated with the data item;

where the first locking mode when first held on the data item determines an associated set of predetermined access restrictions for the data item and determines and associated different set of predetermined access restrictions for the neighborhood associated with the data item;

where the second locking mode when first held on the neighborhood determines the associated set of predetermined access restrictions for the neighborhood and determines the associated different set of predetermined access restrictions for the data item; and

wherein the neighborhood locking scheme;

allows a first non-serializable lock of the data item with a first transaction while concurrently allowing a second non-serializable lock on the neighborhood with a second transaction;

allows a first serializable lock on the data item with the first transaction while concurrently preventing a second non-serializable lock on the neighborhood with a second transaction;

allows a first non-serializable lock on the neighborhood with the first transaction while concurrently allowing a second non-serializable lock on the data item with the second transaction; and

allows a first non-serializable lock on the neighborhood with the first transaction while concurrently preventing a second serializable lock on the data item with the second transaction.

6. A database management system, comprising:

a processor providing a neighborhood locking scheme for a neighborhood of free space adjacent to and associated with a data item and extending to an adjacent data item, the neighborhood locking scheme concurrently creating both a first locking mode for the data item, while at the same time creating a second locking mode for the neighborhood associated with the data item;

where the first locking mode when first held on the data item determines an associated set of predetermined access restrictions for the data item and determines and associated different set of predetermined access restrictions for the neighborhood associated with the data item;

where the second locking mode when first held on the neighborhood determines the associated set of predetermined access restrictions for the neighborhood and determines the associated different set of predetermined access restrictions for the data item; and

wherein the neighborhood locking scheme includes a neighborhood lock (Xnei) mode that enables a first transaction to lock the neighborhood for inserting a new tuple but prevents the first transaction from locking a tuple associated with the neighborhood.

7. A database management system according to claim 6 wherein the Xnei mode enables a second concurrent transaction to modify the tuple while preventing the second concurrent transaction from having exclusive rights on the neighborhood.

8. A database management system, comprising:

a processor providing a neighborhood locking scheme for a neighborhood of free space adjacent to and associated with a data item and extending to an adjacent data item, the neighborhood locking scheme concurrently creating both a first locking mode for the data item, while at the same time creating a second locking mode for the neighborhood associated with the data item;

where the first locking mode when first held on the data item determines an associated set of predetermined access restrictions for the data item and determines and associated different set of predetermined access restrictions for the neighborhood associated with the data item;

where the second locking mode when first held on the neighborhood determines the associated set of predetermined access restrictions for the neighborhood and determines the associated different set of predetermined access restrictions for the data item; and

wherein the neighborhood locking scheme includes a non-serializable end of scan (Snei) lock mode that allows a first transaction to only read the neighborhood while preventing the first transaction from reading or writing a tuple associated with the neighborhood.

9. A database management system according to claim 8 wherein the Snei lock mode enables a second concurrent transaction to read and write the tuple and modify the data neighborhood.

10. A method for controlling access to data items in a database, comprising:

identifying a neighborhood of free space adjacent to a data item in the database;

providing a first set of access privileges to a first transaction accessing the data item and holding a lock mode on the data item corresponding with the first transaction;

providing a second set of access privileges to a second transaction operating independently of the first transaction and accessing the neighborhood associated with the data item, the second set of access privileges determined by the lock mode already held on the data item by the first transaction;

granting a non-serializable shared lock for reading the data item with the first set of access privileges; and

granting a weak exclusive neighborhood lock on the data item with the second set of access privileges so that a first transaction can read the data item while a second transaction concurrently performs an insert operation into the neighborhood associated with the data item.

11. A method according to claim 10 including:

using a lock mode first held on the data item for determining the first set of access privileges for the data item and the second set of access privileges for the neighborhood; and

using the lock mode first held on the neighborhood for determining the first set of access privileges for the data item and the second set of access privileges for the neighborhood.

12. A method according to claim 11 including preventing the first transaction from locking the data item when the second transaction already holds a lock on the neighborhood.

14. A method according to claim 10 including using entries in an index to identify the neighborhood.

13. A method for controlling access to data items in a database, comprising:

identifying a neighborhood of free space adjacent to a data item in the database;

providing a first set of access privileges to a first transaction accessing the data item and holding a lock mode on the data item corresponding with the first transaction; and

providing a second set of access privileges to a second transaction operating independently of the first transaction and accessing the neighborhood associated with the data item, the second set of access privileges determined by the lock mode already held on the data item by the first transaction;

using a lock mode first held on the data item for determining the first set of access privileges for the data item and the second set of access privileges for the neighborhood; and

using the lock mode first held on the neighborhood for determining the first set of access privileges for the data item and the second set of access privileges for the neighborhood; and

gaining access for modifying the neighborhood by asserting a neighborhood lock (Xnei) on the data item and then restricting access to the data item according to a predetermined set of lock modes associated with the Xnei.

15. A system for controlling access to data items in a database, comprising:

a processor executing;

means for identifying a neighborhood of free space associated with a data item in the database;

means for providing a first set of access privileges for the data item according to a lock mode held on the data item

means for providing a second set of access privileges for the neighborhood associated with the data item and determined by the lock mode held on the data item;

means for using a lock mode first held on the data item for determining the first set of access privileges for the data item and the second set of access privileges for the neighborhood;

means for using the lock mode first held on the neighborhood for determining the first set of access privileges for the data item and the second set of access privileges for the neighborhood; and

means for gaining access for modifying the neighborhood by asserting a neighborhood lock (Xnei) on the data item and then restricting to the data item according to a predetermined set of lock modes associated with the Xnei.

16. The system according to claim 15 including means for preventing a first transaction from locking the data item when a second independent transaction already holds a lock on the neighborhood.

17. A computer readable medium containing instructions that are executing on a computer comprising:

providing a neighborhood locking scheme for a neighborhood of free space adjacent to and associated with a data item and extending to an adjacent data item, the neighborhood locking scheme concurrently creating both a first locking mode for the data item, while at the same time creating a second locking mode for the neighborhood associated with the data item;

causing the first locking mode when first held on the data item to determine an associated set of predetermined access restrictions for the data item and determine an associated different set of predetermined access restrictions for the neighborhood associated with the data item;

causing the second locking mode when first held on the neighborhood to determine the associated set of predetermined access restrictions for the neighborhood and determine the associated different set of predetermined access restrictions for the data item;

causing a non-serializable scan of the data item with a first transaction while allowing a concurrent non-serializable lock on the neighborhood with a second transaction;

causing a serializable scan of the data item with the first transaction while preventing a concurrent non-serializable lock on the neighborhood with the second transaction;

causing a non-serializable lock on the neighborhood with the first transaction while allowing a concurrent non-serializable scan on the data item with the second transaction; and

causing a non-serializable lock on the neighborhood with the first transaction while preventing a concurrent serializable scan on the data item with the second transaction.

18. A computer readable medium containing instructions that are executing on a computer comprising:

providing a neighborhood locking scheme for a neighborhood of free space adjacent to and associated with a data item and extending to an adjacent data item, the neighborhood locking scheme concurrently creating both a first locking mode for the data item, while at the same time creating a second locking mode for the neighborhood associated with the data item;

causing the first locking mode when first held on the data item to determine an associated set of predetermined access restrictions for the data item and determine an associated different set of predetermined access restrictions for the neighborhood associated with the data item;

causing the second locking mode when first held on the neighborhood to determine the associated set of predetermined access restrictions for the neighborhood and determine the associated different set of predetermined access restrictions for the data item;

causing a first non-serializable lock of the data item with a first transaction while concurrently allowing a second non-serializable lock on the neighborhood with a second transaction;

causing a first serializable lock on the data item with the first transaction while concurrently preventing a second non-serializable lock on the neighborhood with a second transaction;

causing a first non-serializable lock on the neighborhood with the first transaction while concurrently allowing a second non-serializable lock on the data item with the second transaction; and

causing a first non-serializable lock on the neighborhood with the first transaction while concurrently preventing a second serializable lock on the data item with the second transaction.

19. A computer readable medium containing instructions that are executing on a computer comprising:

providing a neighborhood locking scheme for a neighborhood of free space adjacent to and associated with a data item and extending to an adjacent data item, the neighborhood locking scheme concurrently creating both a first locking mode for the data item, while at the same time creating a second locking mode for the neighborhood associated with the data item;

causing the first locking mode when first held on the data item to determine an associated set of predetermined access restrictions for the data item and determine an associated different set of predetermined access restrictions for the neighborhood associated with the data item;

causing the second locking mode when first held on the neighborhood to determine the associated set of predetermined access restrictions for the neighborhood and determine the associated different set of predetermined access restrictions for the data item; and

enabling a first transaction to lock the neighborhood for inserting a new tuple but preventing the transaction from locking a tuple associated with the neighborhood.