Mailing-List: contact derby-dev-help@db.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Derby Development" <derby-dev@db.apache.org>
Received-SPF: neutral (hermes.apache.org: local policy)
Message-ID: <42A5EEE5.2000803@sbcglobal.net>
Date: Tue, 07 Jun 2005 12:00:53 -0700
From: Mike Matrigali <mikem_app@sbcglobal.net>
User-Agent: Mozilla Thunderbird 0.7.2 (Windows/20040707)
MIME-Version: 1.0
To: Derby Development <derby-dev@db.apache.org>
Subject: restarting work on documenting the btree module ...
References: <54ac72d705051719171a779686@mail.gmail.com> <42935A7F.400@sun.com>
 <54ac72d705052415473ee5eb7f@mail.gmail.com> <4293B070.90006@sbcglobal.net>
 <002901c5610c$4ecd33e0$0200000a@lan> <4294AC84.2080706@sbcglobal.net>
In-Reply-To: <4294AC84.2080706@sbcglobal.net>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

ok, should have time now to get back to this.

First here is a start at info about files in the index directory.
Is this a good start.  I would actually like to check this information
into the source code, and am looking for some opinions about how best
to do it.  Currently it is just text, but ideally I would like to hook
it up to html and the javadoc system some how.  Worst case I am just
going to check it into a readme.txt in the appropriate directory unless
there is some better suggestion.  Unfortunately I don't have much
html or javadoc expertise.

Next I will look at the btree directory, probably tommorow.

And then eventually would like
to get back to the compare/contrast paper with Aries work this btree
is based on.


Text of a suggested readme.txt in the
java/engine/org/apache/derby/impl/store/access/btree/index

This directory implements the code used by the language layer to implement
SQL secondary indexes.  The files here extend and use the classes in
the java/engine/org/apache/derby/impl/store/access/btree/index
directory to implement a locked btree index.

The key to understanding the class layout is to understand the public
store interfaces in
java/engine/org/apache/derby/iapi/store/access/conglomerate,
see the javadoc there.  Basically it defines a shared interface used by
all access method interfaces.  Currently derby implements a heap and a
btree index implementation.  Every access method must implement all the
interfaces in that directory.  Users of access methods use the same
interface
no matter what the underlying type or particular implementation of the
access method.  Derby could support multiple types of btree index
implementation,  which if done right should require no changes to actual
users
of the access methods.

In reality I would expect the interfaces to have to change some to support
a radically different kind of access method - like gist.  But the
implementor
should enhance the interfaces in the conglomerate directory so that it can
then support all existing access methods.

Below is a quick description of what the files do, see javadoc in the
individual files for more explanation of each.

B2I.java
    Implements the Conglomerate interface which has 2 rolls:
    1) Is the object which is stored on disk which holds the store specific
       information needed to access/describe the conglomerate.  This
includes
       information like the format id's of the columns, the conglomerate id
       of the base table, the location of row location column.
    2) Access to all the interface's start by making a call off the
       Conglomerate interface.  So for instance to get a scan on the
       conglomerate you call B2I.openScan().

B2IController.java
    Implements the ConglomerateController interface for the secondary index
    implementation.  The primary use of this interface is to insert rows
into
    the tree.

B2ICostController.java
    Implements the StoreCostController interface for the secondary index
    implementation.  The primary use of this interface is to provide costs
    used by the query optimizer to use when choosing query plans.  Provides
    costs of things like fetch one row, how many rows in conglomerate, how
    many rows between these 2 keys.

B2IFactory.java
    Implments the ConglomerateFactory interface for the secondary index
    implementation.  This class makes this access method implementation
    a module, and available through the ModuleControl system.  Used to
    create a new conglomerate and to bootstrap an existing B2I from disk
using
    metadata stored to disk in a B2I.

B2IForwardScan.java
    Implments the ScanManager interface.  This supports setting up and
    iterating through a set of rows while providing a start key, stop key,
    and a set of AND and OR qualifiers to skip unwanted rows.  Currently
    derby only supports forward scans (but individual columns can have
    descending order).  This interface is also used to delete rows from
    the conglomerate.  Note that update is not supported, it must be
    implemented as a delete, followed by an insert.

B2IMaxScan.java
    This class implements an optimized interface to find the maximum row,
    for a set of rows between an input start and stop key.

Isolation level implementation in the secondary index is done with data
only locking, ie. locks on secondary index rows are actually locks on the
data rows that they point to.  The specifics of particular isolation levels
are hidden in various implementations of the BTreeLockingPolicy class.  The
classes which do scans, deletes, and inserts don't have isolation specific
code, instead they make lock calls using BTreeLockingPolicy interfaces, and
then depending on the isolation level one of the following 4 classes does
the actual locking:

B2INoLocking.java
    Basically does no locking.  This is used when we know that logical locks
    are already obtained so need not be requested again.

B2IRowLocking1.java
    Implements the jdbc read uncommitted isolation level, using row locks.
    No read locks are requested.
    Holds write locks until end of transaction.
    Extends B2IRowLocking2.
    No previous key read locks are obtained.

B2IRowLocking2.java
    Implements the jdbc read committed isolation level using row locks.
    Releases read locks after obtaining them, in some cases uses optimized
        locking interface to wait for lock grant and to instantaneously
        release lock.
    Holds write locks until end of transaction.
    Extends B2IRowLockingRR.

B2IRowLockingRR.java
    Implements the jdbc repeatable read isolation level using row locks.
    Holds read and write locks until end of transaction.
    No previous key read locks are obtained.
    Extends B2IRowLocking3.

B2IRowLocking3.java
    Implements the jdbc serializable isolation level using row locks.
    Holds read and write locks until end of transaction.
    Previous key locks are obtained to protect from phantom reads.

B2ITableLocking3.java
    If table locking implements all isolation levels.

B2IStaticCompiledInfo.java
    Information about the table that does not vary from one execution to
    the next, can be compiled into a query plan and then sent back into
    store to save lookup costs per execution of a query.  See
    openCompiledScan() for usage.

B2IUndo.java
    Used to implement logical undo of btree insert and delete operations.

D_B2IController.java
    Debugging class used to print debug information about B2I.  Code here
    can be used in SANE development builds but the class is not necessary
    for a release so does not add footprint to a customer release.
    See the DiagnosticableGeneric interface for more information.


Mike Matrigali wrote:

> I can help out with this, but probably will not get to it until next
> week, is that ok?  Also let's move the discussion to some other
> subject.
> 
> /mikem
> 
> Dibyendu Majumdar wrote:
> 
>> From: "Mike Matrigali" <mikem_app@sbcglobal.net>
>>
>>> 3) some extra functionality on btree side (not necessarily show
>>> stopper).
>>
>>
>>
>> Mike, I'd like to restart the work on documenting the Btree module.
>> Would you have time to add to any of your previous comments?
>> If you could provide a brief note on the various Classes and which one
>> does
>> what, I can this further by reading up the code/comments.
>>
>> Regards
>>
>>
>>
>>
> 
>