## Deadlock in Index (where index is B+ tree) Locking with Intention Locks

### Deadlock in Index (where index is B+ tree) Locking with Intention Locks

In class I was told that any locking protocol can result in deadlock
when there is concurrency.

Also in class, the professor gave us a simple example of deadlock
occurring in the tree, if bi-directional traversal (traversing both up
and down the tree) is allowed.  This is very easy to understand how
deadlock can occur in this case.

But I can't come up with an example of deadlock occuring in a tree
based structure when you don't allow this bi-directional traversal.

For example, in the following tree:
http://www.cs.queensu.ca/~cassidy/media/images/tree.jpg

let's say that there are two transactions:
T1 and T2

And they all want to delete database objects - you'll notice in some
cases that an X (exclusive lock) is obtained on the inner nodes of the
tree and not in others.  This is because in some cases the B+ tree's
index will change if one of it's node's order falls beneath its
predefined number and this change could perculate up the tree.

And let's imagine the following scenario:
T1 - IX(root) IX(B) IX(D) IX(H) X(P) X(H) X(D) X(B) U(P) U(H) U(D)
U(B) U(root)
T2 - IX(root) IX(B) IX(D) IX(H) X(O) X(H) X(D) X(B) U(O) U(H) U(D)
U(B) U(root)
T3 - IX(root) IX(B) IX(D) IX(G) X(N) X(G) X(D) X(B) U(N) U(G) U(D)
U(B) U(root)

There is no permutation I could find of the above that would result in

If you can think of a more simple set of transactions that would
result in deadlock I would also be interested in that.

Thanks for any suggestions,
Tim

### Deadlock in Index (where index is B+ tree) Locking with Intention Locks

Quote:> And let's imagine the following scenario:
> T1 - IX(root) IX(B) IX(D) IX(H) X(P) X(H) X(D) X(B) U(P) U(H) U(D)
> U(B) U(root)
> T2 - IX(root) IX(B) IX(D) IX(H) X(O) X(H) X(D) X(B) U(O) U(H) U(D)
> U(B) U(root)
> T3 - IX(root) IX(B) IX(D) IX(G) X(N) X(G) X(D) X(B) U(N) U(G) U(D)
> U(B) U(root)

> There is no permutation I could find of the above that would result in

> If you can think of a more simple set of transactions that would
> result in deadlock I would also be interested in that.

Is your protocol deadlock safe? Maybe. But it's not very interesting, since
all your transactions are serialized on the root node. You need to unlock
root node early, and then watch problem to happen!

### Deadlock in Index (where index is B+ tree) Locking with Intention Locks

Actually it isn't serialized at the root node.

Perhaps your misunderstanding is due to the concept of the lock IX
(Intentional Exclusive Lock).  This lock allows other Intentional
Exclusive locks to be obtained (or such is my understanding).

For instance the following ordering is allowed:
T1 - IX(root)
T2 - IX(root)
T1 - IX(B)
T2 - IX(B)
T1 - IX(D) IX(H) X(P) X(H) X(D) X(B) U(P) U(H) U(D) U(B) U(root)
T2 - IX(D) IX(H) X(O) X(H) X(D) X(B) U(O) U(H) U(D) U(B) U(root)
T3 - IX(root) IX(B) IX(D) IX(G) X(N) X(G) X(D) X(B) U(N) U(G) U(D)
U(B) U(root)

And of course will not result in deadlock.  Basically, I'm trying to
confirm or deny the theory that "all locking protocols that allow

The index locking (with a tree) appears to me to be an exception to
this rule.

Thanks for your suggestion though... I don't mean to sound

Thanks,
Tim

> > And let's imagine the following scenario:
> > T1 - IX(root) IX(B) IX(D) IX(H) X(P) X(H) X(D) X(B) U(P) U(H) U(D)
> > U(B) U(root)
> > T2 - IX(root) IX(B) IX(D) IX(H) X(O) X(H) X(D) X(B) U(O) U(H) U(D)
> > U(B) U(root)
> > T3 - IX(root) IX(B) IX(D) IX(G) X(N) X(G) X(D) X(B) U(N) U(G) U(D)
> > U(B) U(root)

> > There is no permutation I could find of the above that would result in

> > If you can think of a more simple set of transactions that would
> > result in deadlock I would also be interested in that.

> Is your protocol deadlock safe? Maybe. But it's not very interesting, since
> all your transactions are serialized on the root node. You need to unlock
> root node early, and then watch problem to happen!

### Deadlock in Index (where index is B+ tree) Locking with Intention Locks

> > And let's imagine the following scenario:
> > T1 - IX(root) IX(B) IX(D) IX(H) X(P) X(H) X(D) X(B) U(P) U(H) U(D)
> > U(B) U(root)
> > T2 - IX(root) IX(B) IX(D) IX(H) X(O) X(H) X(D) X(B) U(O) U(H) U(D)
> > U(B) U(root)
> > T3 - IX(root) IX(B) IX(D) IX(G) X(N) X(G) X(D) X(B) U(N) U(G) U(D)
> > U(B) U(root)

> > There is no permutation I could find of the above that would result in

> > If you can think of a more simple set of transactions that would
> > result in deadlock I would also be interested in that.

> Is your protocol deadlock safe? Maybe. But it's not very interesting,
since
> all your transactions are serialized on the root node. You need to unlock
> root node early, and then watch problem to happen!

Unlocking the root node early would certainly provide problems if block/page
splits propogated up the hierarchy to the root...doesn't seem like a viable
alternative.

### Deadlock in Index (where index is B+ tree) Locking with Intention Locks

Quote:> In class I was told that any locking protocol can result in deadlock
> when there is concurrency.

> Also in class, the professor gave us a simple example of deadlock
> occurring in the tree, if bi-directional traversal (traversing both up
> and down the tree) is allowed.  This is very easy to understand how
> deadlock can occur in this case.

> But I can't come up with an example of deadlock occuring in a tree
> based structure when you don't allow this bi-directional traversal.

> For example, in the following tree:
> http://www.cs.queensu.ca/~cassidy/media/images/tree.jpg

> let's say that there are two transactions:
> T1 and T2

> And they all want to delete database objects - you'll notice in some
> cases that an X (exclusive lock) is obtained on the inner nodes of the
> tree and not in others.  This is because in some cases the B+ tree's
> index will change if one of it's node's order falls beneath its
> predefined number and this change could perculate up the tree.

> And let's imagine the following scenario:
> T1 - IX(root) IX(B) IX(D) IX(H) X(P) X(H) X(D) X(B) U(P) U(H) U(D)
> U(B) U(root)
> T2 - IX(root) IX(B) IX(D) IX(H) X(O) X(H) X(D) X(B) U(O) U(H) U(D)
> U(B) U(root)
> T3 - IX(root) IX(B) IX(D) IX(G) X(N) X(G) X(D) X(B) U(N) U(G) U(D)
> U(B) U(root)

> There is no permutation I could find of the above that would result in

Assuming the multiple granularity locking protocol with 2PL, would the
following schedule achieve the effect you are looking for?

Time | T1           | T2           | T3
-----|--------------|--------------|------------------
T1   | IX(root)     |              |
T2   | IX(B)        |              |
T3   | IX(D)        |              |
T4   | IX(H)        |              |
T5   |              |              | IX(root)
T6   |              |              | IX(B)
T7   |              |              | IX(D)
T8   |              |              | IX(G)
T9   | X(P)         |              |
T10  |              | IX(root)     |
T11  |              | IX(B)        |
T12  |              | IX(D)        |
T13  |              | IX(H)        |
T14  |              | IX(O)        |
T15  |              | waiting X(H) |
T16  | waiting X(H) | waiting X(H) |
T17  | waiting X(H) | waiting X(H) | X(N)
T17  | waiting X(H) | waiting X(H) | X(G)
T18  | waiting X(H) | waiting X(H) | waiting X(O)
T19  | waiting X(H) | waiting X(H) | waiting X(O)

I am also assuming that alternative locking protocols such as B-link trees
are not considered in the question you pose.

Dan

- Show quoted text -

Quote:> If you can think of a more simple set of transactions that would
> result in deadlock I would also be interested in that.

> Thanks for any suggestions,
> Tim

### Deadlock in Index (where index is B+ tree) Locking with Intention Locks

>>In class I was told that any locking protocol can result in deadlock
>>when there is concurrency.

>>Also in class, the professor gave us a simple example of deadlock
>>occurring in the tree, if bi-directional traversal (traversing both up
>>and down the tree) is allowed.  This is very easy to understand how
>>deadlock can occur in this case.

>>But I can't come up with an example of deadlock occuring in a tree
>>based structure when you don't allow this bi-directional traversal.

>>For example, in the following tree:
>>http://www.cs.queensu.ca/~cassidy/media/images/tree.jpg

>>let's say that there are two transactions:
>>T1 and T2

>>And they all want to delete database objects - you'll notice in some
>>cases that an X (exclusive lock) is obtained on the inner nodes of the
>>tree and not in others.  This is because in some cases the B+ tree's
>>index will change if one of it's node's order falls beneath its
>>predefined number and this change could perculate up the tree.

>>And let's imagine the following scenario:
>>T1 - IX(root) IX(B) IX(D) IX(H) X(P) X(H) X(D) X(B) U(P) U(H) U(D)
>>U(B) U(root)
>>T2 - IX(root) IX(B) IX(D) IX(H) X(O) X(H) X(D) X(B) U(O) U(H) U(D)
>>U(B) U(root)
>>T3 - IX(root) IX(B) IX(D) IX(G) X(N) X(G) X(D) X(B) U(N) U(G) U(D)
>>U(B) U(root)

>>There is no permutation I could find of the above that would result in

> Assuming the multiple granularity locking protocol with 2PL, would the
> following schedule achieve the effect you are looking for?

> Time | T1           | T2           | T3
> -----|--------------|--------------|------------------
> T1   | IX(root)     |              |
> T2   | IX(B)        |              |
> T3   | IX(D)        |              |
> T4   | IX(H)        |              |
> T5   |              |              | IX(root)
> T6   |              |              | IX(B)
> T7   |              |              | IX(D)
> T8   |              |              | IX(G)
> T9   | X(P)         |              |
> T10  |              | IX(root)     |
> T11  |              | IX(B)        |
> T12  |              | IX(D)        |
> T13  |              | IX(H)        |
> T14  |              | IX(O)        |
> T15  |              | waiting X(H) |
> T16  | waiting X(H) | waiting X(H) |
> T17  | waiting X(H) | waiting X(H) | X(N)
> T17  | waiting X(H) | waiting X(H) | X(G)
> T18  | waiting X(H) | waiting X(H) | waiting X(O)
> T19  | waiting X(H) | waiting X(H) | waiting X(O)

> I am also assuming that alternative locking protocols such as B-link trees
> are not considered in the question you pose.

> Dan

>>If you can think of a more simple set of transactions that would
>>result in deadlock I would also be interested in that.

>>Thanks for any suggestions,

Try:

http://www.informatik.uni-trier.de/~ley/db/conf/vldb/Mohan90.html

paper :-() which showed how you could manage locking in B+trees w/o
locking the root node automatically.

I'm not sure it's the one cited above -- maybe a visit to citeseer
would help too.  Or even google?

--
Jonathan Leffler                   #include <disclaimer.h>

Guardian of DBD::Informix 1.04.PC1 -- http://dbi.perl.org/

### Deadlock in Index (where index is B+ tree) Locking with Intention Locks

>In class I was told that any locking protocol can result in deadlock
>when there is concurrency.

Actually, that is not completely true. It is well known that the socalled
"tree locking protocol" which basically outlaws bi-directional traversal

For references see:

SILBERSCHATZ, A. and KEDEM, Z. Consistency in hierarchical database
systems. J. of the ACM 27,1 (January 1980) 72-80

or

Lanin, V. and Shasha, D. 1990. Tree Locking on Changing Trees. Technical
Report 503, New York University. http://citeseer.nj.nec.com/lanin90tree.html

If you stick to 2PL then a transaction excludes all other operations of
other transactions because it will lock the root, but the beauty of the tree
locking protocol is that you don't have to stick to 2PL to guarantee
serializability.

-- Jan Hidders

Hi,

I'm doing a project for a DB class I'm taking.
I've been looking into disk-based index methods
for mulit-dimensional data.  I've heard that
Informix's recent DBMSs ship with R-tree as
one of the access methods.  Other versions of
the R-tree are apparently implemented in various