Method for concurrency control for a secondary index
View Patent ↗The present invention relates to a method and a computer program for concurrency control for a secondary index ( 13 ) wherein many deadlocks are avoided by means of a selective locking strategy and by means of allowing index records ( 14 ) of the secondary index to contain some keys to many but never too few. When keys are read from the secondary index ( 13 ) it is thus possible to read some keys that may be irrelevant. However, such irrelevant keys are sorted out by means of checking against the corresponding records ( 12 ) in the table ( 11 ) to which the secondary index ( 13 ) is associated. The selective locking strategy allows for increased concurrency.
1. A computer implemented method for concurrency control for a secondary index associated with a database table, which secondary index includes index records, wherein each index record contains a list of entries, which are unique keys each identifying a table record of the database table, which method involves performing index operations on the index records according to a locking strategy for locking the index records, wherein the method comprises:
allowing the index operation of type Delete Index Entry to operate on an index record concurrently with any other index operation of type Add Index Entry, Write Index Entry, Delete Index Entry, or Read Index Entry even when the other index operation holds a lock on the index record, and
performing the index operation of type Delete Index Entry such that an entry to be deleted from the index record is not removed from the index record until the index operation of type Delete Index Entry is committed.
2. The method for concurrency control for a secondary index according to claim 1 , wherein any index operation is allowed to operate on an index record while an index operation of type Delete Index Entry is operating on the index record.
3. The method for concurrency control for a secondary index according to claim 1 , wherein the index operation of type Delete Index Entry is performed such that an entry to be deleted from the index record is marked, which marked entry is readable by an index operation of type Read Index Entry.
4. The method for concurrency control for a secondary index according to claim 3 , wherein the index operation of type Read Index Entry is performed according to the steps of:
reading all entries listed in an index record that relate to a first search condition,
checking the table records identified by the read entries to see which table records fulfill the first search condition, and
returning the entries that identify the table records that still fulfill the first search condition.
5. The method for concurrency control for a secondary index according to claim 1 , wherein any index operation is allowed to operate on an index record while an index operation of type Add Index Entry is operating on the index record.
6. The method for concurrency control for a secondary index according to claim 5 , wherein the index operation of type Add Index Entry is performed according to the steps of:
adding an entry to an index record when the index operation of type Add Index Entry is started, and
removing the added entry if the index operation of type Add Index Entry is aborted.
7. The method for concurrency control for a secondary index according to claim 1 , wherein any index operation is allowed to operate on an index record while an index operation of type Write Index Entry is operating on the index record.
8. The method for concurrency control for a secondary index according to claim 7 , wherein the index operation of type Write Index Entry is performed according to the steps of:
reading all entries listed in an index record that relate to a first search condition,
checking the table records identified by the read entries to see which table records fulfill the first search condition,
updating the table records that still fulfill the first search condition, and
updating the secondary index to be consistent with the updated database table.
9. The method for concurrency control for a secondary index according to claim 1 , wherein the locking strategy is arranged to allow concurrency between an incoming index operation of type Add Index Entry and another ongoing index operation of type Add Index Entry or Delete Index Entry and to forbid concurrency between an incoming index operation of type Add Index Entry and another ongoing index operation of type Write Index Entry or Read Index Entry.
10. The method for concurrency control for a secondary index according to claim 1 , wherein the locking strategy is arranged to allow concurrency between an incoming index operation of type Write Index Entry and another ongoing index operation of type Delete Index Entry or Add Index Entry, and to forbid concurrency between an incoming index operation of type Write Index Entry and another ongoing index operation of type Write Index Entry or Read Index Entry.
11. The method for concurrency control for a secondary index according to claim 1 , wherein the locking strategy is arranged to allow concurrency between an incoming index operation of type Read Index Entry and another ongoing index operation of type Add Index Entry, Delete Index Entry or Read Index Entry, and to forbid concurrency between an incoming index operation of type Read Index Entry and another ongoing index operation of type Write Index Entry.
12. A computer program product for a database management system, which computer program product comprises code means residing on a computer readable medium, wherein said code means are arranged to perform a method for concurrency control for a secondary index associated with a database table, which secondary index includes index records, wherein each index record contains a list of entries, which are unique keys each identifying a table record of the database table, which method involves performing index operations on the index records according to a locking strategy for locking the index records, when said computer program is executed by a computer of the database management system, wherein the method comprises:
allowing the index operation of type Delete Index Entry to operate on an index record concurrently with any other index operation of type Add Index Entry, Write Index Entry, Delete Index Entry, or Read Index Entry even when the other index operation holds a lock on the index record, and
performing the index operation of type Delete Index Entry such that an entry to be deleted from the index record is not removed from the index record until the index operation of type Delete Index Entry is committed.
13. The computer program product for a database management system according to claim 12 , wherein any index operation is allowed to operate on an index record while an index operation of type Delete Index Entry is operating on the index record.
14. The computer program product for a database management system according to claim 12 , wherein the index operation of type Delete Index Entry is performed such that an entry to be deleted from the index record is marked, which marked entry is readable by an index operation of type Read Index Entry.
15. The computer program product for a database management system according to claim 14 , wherein the index operation of type Read Index Entry is performed according to the steps of:
reading all entries listed in an index record that relate to a first search condition,
checking the table records identified by the read entries to see which table records fulfill the first search condition, and
returning the entries that identify the table records that still fulfill the first search condition.
16. The computer program product for a database management system according to claim 12 , wherein any index operation is allowed to operate on an index record while an index operation of type Add Index Entry is operating on the index record.
17. The computer program product for a database management system according to claim 16 , wherein the index operation of type Add Index Entry is performed according to the steps of:
adding an entry to an index record when the index operation of type Add Index Entry is started, and
removing the added entry if the index operation of type Add Index Entry is aborted.
18. The computer program product for a database management system according to claim 12 , wherein any index operation is allowed to operate on an index record while an index operation of type Write Index Entry is operating on the index record.
19. The computer program product for a database management system according to claim 18 , wherein the index operation of type Write Index Entry is performed according to the steps of:
reading all entries listed in an index record that relate to a first search condition,
checking the table records identified by the read entries to see which table records fulfill the first search condition,
updating the table records that still fulfill the first search condition, and
updating the secondary index to be consistent with the updated database table.
20. The computer program product for a database management system according to claim 12 , wherein the locking strategy is arranged to allow concurrency between an incoming index operation of type Add Index Entry and another ongoing index operation of type Add Index Entry or Delete Index Entry and to forbid concurrency between an incoming index operation of type Add Index Entry and another ongoing index operation of type Write Index Entry or Read Index Entry.
21. The computer program product for a database management system according to claim 12 , wherein the locking strategy is arranged to allow concurrency between an incoming index operation of type Write Index Entry and another ongoing index operation of type Delete Index Entry or Add Index Entry, and to forbid concurrency between an incoming index operation of type Write Index Entry and another ongoing index operation of type Write Index Entry or Read Index Entry.
22. The computer program product for a database management system according to claim 12 , wherein the locking strategy is arranged to allow concurrency between an incoming index operation of type Read Index Entry and another ongoing index operation of type Add Index Entry, Delete Index Entry or Read Index Entry, and to forbid concurrency between an incoming index operation of type Read Index Entry and another ongoing index operation of type Write Index Entry.