db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Dibyendu Majumdar" <dibye...@mazumdar.demon.co.uk>
Subject Re: Derby architecture/design documents
Date Sat, 22 Jan 2005 01:13:54 GMT

My initial comments/questions follow, more to come ...

> Btree's are based on ARIES.

Do you mean that BTree implementation uses ARIES style logging and
recovery, or does it implement the concurrency and recovery logic of
ARIES/IM? Or both?

Reading the code, I cannot see that ARIES/IM is used apart from the
data row locking.

> Structure modifications are all
> isolated from other operations through the use of latches.

I am trying to understand the splitting logic which requires structural
change. It seems to me that it works as follows:

If a key cannot be inserted in a page, then check if parent has enough space
to insert the split key.
If not, go to root and split the tree top-down along the path that leads to
the page that the new key is being inserted at.
Retry inserting the key.

The logic repeats until the key is inserted.

The basic idea seems to be that the split is deferred until it is ensured
that space is available in the parent page.
The exact mechanism is not clear to me as I am unable to follow the logic
which uses recursion, and seems quite complex.

The split seems to be managed as an "internal transaction" which is
described as follows:

"Start an internal transaction.  An internal transaction is a completely
separate transaction from the current user transaction.  All work done
in the internal transaction must be physical (ie. it can be undone
 physically by the rawstore at the page level, rather than logically
 undone like btree insert/delete operations).  The rawstore guarantee's
that in the case of a system failure all open Internal transactions are
first undone in reverse order, and then other transactions are undone
in reverse order.
Internal transactions are meant to implement operations which, if
 interupted before completion will cause logical operations like tree
searches to fail.  This special undo order insures that the state of
the tree is restored to a consistent state before any logical undo
operation which may need to search the tree is performed."

FYI, I am looking at the following methods:


> In both the btree and the heap, delete are first executed by marking
> a "deleted" bit.  This is to insure space on the page for abort, since
> row level locking will allow other rows on the page to be modified
> conncurrently with transaction executing the delete.  The system uses
> a background daemon to schedule work after commit to reclaim the space
> of the deleted rows.  A row marked deleted can be "purged" if one can
> obtain a lock on it (if it was an uncommitted delete then the
> transaction doing the commit would still have an exclusive lock on the
> row).

I assume you are referring to:


The comment in the code says:

"The current space reclamation algorithm requires a table level
lock on the btree - this is mostly because the shrink algorithm
is not multi-user.  This lock is requested NOWAIT as it does
not want to impedede normal operation on the table.  If the lock
were to wait then the current lock manager livelock algorithm
would block all subsequent lock requests on this btree even if
they are compatible with the current holder of the lock."

But I also find that deleted rows are also reclaimed during normal insert
operations. For example, in:


The comment for this method says:

"Attempt to reclaim committed deleted rows from the page.
Get exclusive latch on page, and then loop backward through
page searching for deleted rows which are committed.  The routine
assumes that it is called from a transaction which cannot have
deleted any rows on the page.  For each deleted row on the page
it attempts to get an exclusive lock on the deleted row, NOWAIT.
If it succeeds, and since this row did not delete the row then the
row must have been deleted by a transaction which has committed, so
it is safe to purge the row.  It then purges the row from the page.
Note that this routine may remove all rows from the page, it will not
attempt a merge in this situation.  This is because this routine is
called from split which is attempting an insert on the given page, so
it would be a waste to merge the page only to split it again to allow
the insert of the row causing the split."



View raw message