Re: Adjacent Key Locking/"Twin Problem"

OK,OK,OK. Fifty replies asking for the twin document tells me that it should be posted here. Thanks to INFORMIX (Mary Schulte) for finding this for me. ************************************************************************** TechInfo # 3873 Short Description: The Twin Problem, Adjacent Key Locking, & Key Value Locking Long Description: Adjacent Key Locking vs. Key Value Locking in OnLine ____________________________________________________ *What is the "Twin Problem"? The "Twin Problem" is a situation that can arise when inserting and deleting rows in databases with logging. Suppose that two processes, Px and Py, are updating a table that has a unique index. Px deletes a row with key value 8; then Py inserts a row with key value 8. Later, Px decides to roll back its transaction. If we allow Px to roll back, there will now be two rows with key value 8, violating the uniqueness constraint on the index. Py therefore must not be allowed to insert its row until Px completes its transaction. But if only row locks are used, there is no way to prevent Py from inserting the row. Once Px deletes the row, the lock is gone; a row that is not there cannot be locked. A similar problem can occur when Isolation Mode is set to Repeatable Read. Suppose Px, using Repeatable Read, locks the set of rows with key value 5. These rows now cannot be deleted or updated. However, new rows can still be added. Py can insert a row with key value 5, or update a row with key value 2 to key value 5. This would violate the Repeatable Read. If the Repeatable Read selection criteria did not include a filter on an indexed column, the only solution is to place a shared lock on the entire table. This prevents any other process from altering the table while the repeatable read is in progress. However, when the selection makes use of an indexed column, OnLine makes use of adjacent key locking to prevent both this and the "Twin Problem". *What is "Adjacent Key Locking"? In databases with logging, when a row is deleted from a table with an index, the current key is tested for the existence of a lock, and an exclusive lock is placed on the next key in the index. If the index is unique, this is the next higher key value. If the index is non-unique, this is the next higher rowid with the same key value, if any, or the next higher key value. If there is no next value, the "infinity" value is locked, which locks all higher values. If either lock step fails, a lock error is returned (or the process waits, if LOCK MODE is set to WAIT), and does not complete the deletion. When a row is inserted, the next key in the index is tested to see if an exclusive lock can be placed on it (but the lock is not actually placed on it), and an exclusive lock is placed on the new (inserted) key. If either step fails, a lock error is returned (or the process waits), and does not complete the insertion. Updates to an indexed value are treated as an insert of the new value and a delete of the old value. ^ | |****Note from Joe Lumbley....it covers updates as well as deletes!!! *How does this work and what are the ramifications? What is the effect on the "Twin Problem"? When Px deletes the row with key value 8, it first tests value 8 to make sure it is not already locked, then it places a lock on key value 9, and deletes value 8. When Py attempts to insert a row with key value 8, it first has to test value 9 to see if it is locked. Since Px has locked value 9, Py cannot insert value 8. Note that if there is no value 9, Px will lock value 10, which not only prevents Py from inserting a value 8, but also prevents Py from inserting a value 9. If 8 was the highest value, the "infinity" value is locked, preventing Py from inserting any value higher than 8. This also protects reads with Isolation Mode of Committed Read or greater, by alerting the reading process to uncommitted insertions or deletions from the selected set. If Py selects all rows "WHERE key_val < 10", and Px has deleted key value 8, Py will encounter the lock on key value 9, alerting it to the fact that there is an uncommitted insertion or deletion of a row. If there is no value 9, 10, or 11, Px will lock key value 12; however, Py will still encounter the lock, because the way in which OnLine determines that it has found all required rows is to read the index values until it reaches the first one which does NOT fit the criteria, which in this case would be 12. Note that Py would also receive a locking error if Py selected all rows "WHERE key_val > 10", even though the row actually deleted was 8. These examples have dealt with issues on unique indexes. However, adjacent key locking also applies to non-unique indexes, as in the Repeatable Read problem. When Px, in Repeatable Read, selects all rows "WHERE value = 5" on a non-unique indexed value, it locks each row with value 5 as it is read. When it passes the last rowid with indexed value 5, it reads the first indexed value 6, which alerts it that it has completed its search, and locks it as well. If Py now attempts to insert a row with value 5, it will first test the adjacent key. If the rowid of the new row is less than that of any one of the existing rows with value 5, it will test the key of the first existing row with rowid greater than itself, and find it locked, as the Repeatable Read locked all the keys for value 5. If the new rowid is greater than any of the existing rows, it will test the key value 6, and find it locked as well. Thus Py is prevented from inserting any new rows with value 5 until the Repeatable Read is completed. Another side-effect of adjacent key locking is reduced concurrency of insertions. If Px inserts the key value 9 into a unique index, Py will now receive a locking error if it attempts to insert the value 8. *Changes in OnLine 4.10 & 5.01 Modifications have been made to current versions of OnLine to increase concurrency of insertions into indexed values. Instead of placing exclusive locks on the inserted value and adjacent value, an "Intent-Exclusive" lock will be used. Intent-Exclusive locks, currently used on tables and databases, are incompatible with Shared or Exclusive locks, but are compatible with other Intent-Exclusive locks, i.e. more than one Intent-Exclusive lock can exist on the same item, but an Intent-Exclusive lock cannot co-exist with a Shared lock. With this modification, Px will obtain an "IX" lock when inserting key value 9, and when Py attempts to insert key value 8, it will test placing an "IX" lock on key value 9, which will succeed, and Py will successfully insert value 8. However, Px deleting value 9 would still lock Py from inserting value 8. This modification has been made in Releases 4.10.UG1, 4.11, and 5.01 of OnLine. *Key Value Locking in OnLine 6.0 Release 6.0 of OnLine features a completely re-designed locking mechanism to avoid the "Twin Problem" and ensure Repeatable Read. Rowid entries in the b-tree will have an additional byte for a "deleted" flag. D