Concurrency Control B-Tree between Hash

Question

I am new to transaction. When I read the book "Transactional Information Systems", it is mentioned that B-tree uses key-range locking to guarantee serializability. Is that true all accesses to the relation must be conducted via the same B-tree to guarantee serializability?

If I understand correctly, there is no way to guarantee serializability if accesses are via different indexes. See the following example.

Suppose there are two indexes on the same relation, namely, a B-tree and a hash index, and there are two transactions.

First, one transaction reads the relation using the hash index, e.g., fetchkey(16) to fetch the (currently absent) record with key 16 and find no match. Since hash does not have key-range locking, it cannot lock the next key. Then, the other transaction inserts a record with key '16' via the B-tree. The insertion will be successful, leading to a phantom.

Answer 1

Locking and the storage mechanisms are independent.

Because locks are independent of the storage it does not matter how storage is accessed. One query may access data through a B-Tree. A second may use a separate B-Tree, a hash index, the base table or any other structure. Data pages can be swapped out to disk. It doesn't matter, locks will still be respected.

If your DBMS happens to have BTrees already then key range locking is a convenient implementation detail.

In the absence of BTrees a different implementation could be predicate locking. In this the WHERE clauses of running queries are compared. If a new query's where clause conflicts with an existing query's the new query queues.

As an example let's say we have rows with IDs 10, 20, 50, 100. Query 1's predicate is ..WHERE ID between 15 and 75. The range lock has to cover the next-lowest and next highest existing keys. So the lock is taken on 10..100. Now if query 2 tries to write ..WHERE ID = 88 it will block because 88 falls within the locked range of 10..100.

With predicate locking, however, the system would recognise that query 2's predicate (88) lies outside the range of query 1's (15..75) so query 2 can proceed. There is no risk of phantoms so the result is serializable.

Predicates can be arbitrarily complex so matching every new query to every already-running query is not trivial. Likely the additional throughput would not pay for the cost on a busy system.

For hash indexes, there are such things as order-preserving hashes. For our example that would mean that hash(100) is greater than hash(75) and range locking can still be applied.

Answer 2

There are multiple types and levels of locking. A higher level of locking is a lock on the entire table object itself. This would include all indexes on that table. Generally this happens when a certain threshold of rows are being modified relative to the total number in the table, and is known as lock escalation.

Please see the DBA.StackExchange question titled What is lock escalation? for further information.