Modified: db/derby/site/trunk/build/site/papers/btree_package.html URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/btree_package.html?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== --- db/derby/site/trunk/build/site/papers/btree_package.html (original) +++ db/derby/site/trunk/build/site/papers/btree_package.html Fri Dec 21 14:30:38 2007 @@ -1,9 +1,9 @@ - + - + @@ -18,49 +18,88 @@
+
apache > db
+
+ + +
Apache DB Project
+ + +
+
+
+
- +  
+ +
+ +
+
+ +
-
-Font size: +
Font size:       @@ -298,7 +351,8 @@
- +

Implements BTree access method, which is the basis for SQL indexes.

+

Overview

Derby implements secondary SQL indexes as BTrees. The high level features of the BTree implementation are:

@@ -310,7 +364,7 @@
  • Derby uses logical key deletes. This enables it to perform undos during rollbacks and restart recovery as single page operations.
  • - +

    High level structure of the B+Tree

    - +

    Latching implementation

    Derby uses latches on pages to get exclusive access to the page while reading or writing the page (Derby only uses exclusive latches, no shared latches are used). In order to prevent deadlocks latches requested while holding other latches are always requested top/down and left to right. Btree splits are always left to right. If for any reason the code needs to break this protocol then it will first request the latch NOWAIT and if it can't get the latch it will release all current latches and wait for the latch it is trying to get, and then after obtaining it go about getting the other latches it needs for the particular operation. While traversing down the tree Derby may hold 2 latches: one on parent and one on child. It then continues doing "ladder" latching down the tree releasing the highest node when it has successfully got a new lower node latch. Latches are short term, only held while reading/modifying the page, never held while an I/O is happening. Structure modifi cations are all isolated from other operations through the use of latches.

    - +

    Locking and Isolation Levels

    Derby uses data only locking for its logical row level locking. All isolation level implementation is done using logical locks (Derby does not support non-locking isolation such as multi-versioning).

    @@ -342,7 +396,7 @@
    No row locks are acquired. The code still gets table level intent locks to prevent concurrent DDL during the query.
    - +

    BTree Structure Modifications

    In Derby, SMOs (structure modification operations - ie. page splits), only happen top down. This is not as concurrent as bottom up in ARIES/IM, but is simpler. As in ARIES/IM Not more than 2 index pages are held latched simultaneously at anytime. In order to improve concurrency and to avoid deadlocks involving latches, even those latches are not held while waiting for a lock wich is not immediately grantable. No data page latch is held or acquired during an index access. Latch coupling is used while traversing the tree - ie. the latch on a parent page is held while requesting a latch on a child page. @@ -351,45 +405,54 @@

    The hard case is when P does not have room for descriminator key. In this case all latches are released, and Derby does a split pass from top to bottom, and will split the internal nodes that do not have room for the decrimator key. Note this may result in more splits than necessary for this particular insert, but the assumption is that the splits will have to happen eventually anyway. After this split pass is done, the search for the insert starts again from top down, but it must once again check for space because it has given up all its latches and some other transaction may have acquired the space in the meantime.

    Optimization is possible to remember C and see if it is right location, and/or use sideway pointers to search right rather than do research of tree.

    - +

    Logical Key Deletes

    In both the BTree and the Heap, deletes 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 the 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).

    - +

    Garbage Collection of deleted keys

    Since rows are only marked as "deleted", and not physically removed, it is necessary to perform space reclamation on deleted rows.

    - +

    Online during BTREE split

    Whenever there is not enough room on a leaf to do an insert the code attempts to find space on the leaf, by checking if it can reclaim any committed deletes on that leaf. That work only requires the latch on the leaf and NOWAIT row write locks. It is expected that most of the space reclaim done in the BTree goes through this path. Most of this work is done in {@link org.apache.derby.impl.store.access.btree.BTreeController.reclaim_deleted_rows}.

    - +

    BTREE post commit work

    Whenever a delete operation deletes the last row from a leaf page then a BtreePostCommit job is queued to be executed after the transaction which did the delete commits. This work currently requires a table level lock as page merges have not been implemented to be allowed concurrent with other operations. Many DBMSes don't even try to do page merges except when called from some sort of reorg utility. If all rows on page are purged, then the page will move to the free list and perform a merge to the tree.

    It is expected that the normal space reclamation happens with row locks during btree split, which is why not much work has been done to optimize btree post commit path

    - +

    Logging and Recovery

    Derby uses physical redo and logical undo for BTree inserts and deletes. Logical undo is simplified as a result of using logical key deletes. If keys were physically removed during deletes, then the undo of a key delete would have required an insert operation which can potentially lead to page splits at various levels within the tree. Since the key is not physically removed, but only marked as "deleted", undoing a key delete is accomplished easily. However, since the page where the insert or delete should take place may have moved, it may be necessary to search for the page.

    Structure modification operations (SMOs) are handled as independent internal transactions and commit separately from the transaction that initiated the SMO. Once an SMO has been completed successfully, it is not undone, even if the transaction that caused it decides to abort. During restart recovery undo phase, incomplete internal transactions are undone BEFORE any regular transactions. This ensures that the BTrees are structurally consistent before normal undo begins.

    +
     
    Send feedback about the website to: derby-user@db.apache.org
    + Modified: db/derby/site/trunk/build/site/papers/container-format.png URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/container-format.png?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== Binary files - no diff available. Modified: db/derby/site/trunk/build/site/papers/derby_arch.html URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/derby_arch.html?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== --- db/derby/site/trunk/build/site/papers/derby_arch.html (original) +++ db/derby/site/trunk/build/site/papers/derby_arch.html Fri Dec 21 14:30:38 2007 @@ -1,9 +1,9 @@ - + - + Derby Engine Architecture Overview @@ -16,49 +16,88 @@
    +
    apache > db
    +
    + + +
    Apache DB Project
    + + +
    +
    +
    +
    - +  
    + +
    + +
    +
    + +
    -
    -Font size: +
    Font size:       @@ -479,21 +532,30 @@
    +
     
    Send feedback about the website to: derby-user@db.apache.org
    +
    Modified: db/derby/site/trunk/build/site/papers/derby_htw.html URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/derby_htw.html?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== --- db/derby/site/trunk/build/site/papers/derby_htw.html (original) +++ db/derby/site/trunk/build/site/papers/derby_htw.html Fri Dec 21 14:30:38 2007 @@ -1,9 +1,9 @@ - + - + How Things Work @@ -16,49 +16,88 @@
    +
    apache > db
    +
    + + +
    Apache DB Project
    + + +
    +
    +
    +
    - +  
    + +
    + +
    +
    + +
    -
    -Font size: +
    Font size:       @@ -262,7 +315,7 @@

    How Things Work

    -
    +
    Warning
    This page is ancient, predating the creating of the @@ -477,21 +530,30 @@
    +
     
    Send feedback about the website to: derby-user@db.apache.org
    +
    Modified: db/derby/site/trunk/build/site/papers/derby_web.html URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/derby_web.html?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== --- db/derby/site/trunk/build/site/papers/derby_web.html (original) +++ db/derby/site/trunk/build/site/papers/derby_web.html Fri Dec 21 14:30:38 2007 @@ -1,9 +1,9 @@ - + - + Apache Derby Web Site @@ -16,49 +16,88 @@
    +
    +
    +
    - +  
    + + + +
    +
    + +
    -
    -Font size: +
    Font size:       @@ -110,6 +163,9 @@ Web Site Change Notes
    • +21-Dec-2007: Web site upgraded to Forrest 0.8 +
    • +
    • 12-Aug-2005: Web site upgraded to Forrest 0.7
    • @@ -200,14 +256,18 @@

      Web Site Change Notes

      - + +

      21-Dec-2007: Web site upgraded to Forrest 0.8

      +

      The web site was upgraded to build with the latest +release of Forrest, Forrest 0.8.

      +

      12-Aug-2005: Web site upgraded to Forrest 0.7

      The web site was recently upgraded to build with the latest release of Forrest, Forrest 0.7.

      If you receive OutOfMemoryErrors while trying to build the site, try increasing the amount of memory available to forrest by setting the ANT_OPTS environment variable to -mx512M.

      - +

      31-Jul-2005: Web site moved from Incubator to Apache DB

      Derby graduated from the Incubator to the Apache DB project, @@ -230,7 +290,7 @@

    - +

    15-May-2005: Version 10.0 manuals moved

    The files that comprise the 10.0 manuals are numerous (about 750), static, @@ -238,7 +298,7 @@ In May they were moved to a separate "mini" forrest site, which is now at http://db.apache.org/derby/docs/10.0/index.html.

    - +

    27-Jan-2005: Web site upgraded to Forrest 0.6

    The Derby web site was initialized in August 2004 with Forrest 0.5.1. @@ -277,7 +337,7 @@

    - +

    Forrest in a Nutshell

    @@ -303,17 +363,17 @@ The 'forrest run' command starts up the Jetty web server that is included in the Forrest distribution on port 8888.

    -
    +
    Warning
    -The Derby web site uses Forrest 0.7 and must be built using Forrest 0.7. +The Derby web site uses Forrest 0.8 and must be built using Forrest 0.8.
    - +

    Testing New Pages for the Derby Site

    @@ -323,7 +383,7 @@ It is much easier to integrate new pages by first testing them outside the Derby web site source tree.

    - +

    Create a Forrest seed site

    The @@ -336,7 +396,7 @@

  • Download - Forrest 0.7.
  • + Forrest 0.8.
  • Install Forrest and set up your environment.
  • @@ -355,7 +415,7 @@
  • Look at the sample pages that are included in the seed site.
  • - +

    Add your new page to the seed site

    If you don't need to add a new page, skip this step. @@ -445,7 +505,7 @@ source file. - +

    What editor can you use for Forrest XML?

    The Forrest web site mentions jEdit, oXygen, xmlspy, @@ -476,7 +536,7 @@ by posting to derby-dev@db.apache.org.

    - +

    Resolve Forrest DTDs locally

    Many source files in the Derby web site repository are in Forrest XML format. @@ -509,7 +569,7 @@ - +

    Updating the Apache Derby web site

    @@ -519,14 +579,14 @@ Step 7 tells contributors how to create a patch. Steps 8-10 tell committers how to commit and publish changes.

    - +

    1. Install Forrest on your machine

    If you haven't installed Forrest yet, -install Forrest 0.7 +install Forrest 0.8 on your local system.

    - +

    2. Check out the Derby web site pages

    Check the Derby web site files out of the subversion repository: @@ -534,7 +594,7 @@

     svn co https://svn.apache.org/repos/asf/db/derby/site/trunk
     
    - +

    3. Modify files in the src tree

    After checking the site out of subversion, @@ -691,7 +751,7 @@ - +

    4. Build the site

    After modifying files, rebuild the site with the @@ -713,7 +773,7 @@ try setting the ANT_OPTS environment variable to -mx512M.

    - +

    5. Test the changes

    There are a couple ways (at least) to review changes. @@ -750,7 +810,7 @@ won't be added when the site is viewed locally.

    - +

    6. Adjust the site build - odd diffs

    Derby developers build the site on a variety of platforms, including Windows, Mac, and Linux. The @@ -776,7 +836,7 @@

    svn revert build\site\skin\*

    If you are using TortoiseSVN, you can use Windows Explorer to revert the changes.

    - +

    7. Create a patch

    Create a patch at the trunk level and only include the @@ -786,7 +846,7 @@

    Upload the patch to a Jira issue to make it available to a Derby committer.

    - +

    8. Commit changes to the src and build/site directories

    Apply any patch, if one was provided, then build and test the web site @@ -831,7 +891,7 @@

     svn commit --message "here is my commit message" src build/site 
     
    - +

    9. Make web site changes visible

    A Derby committer can make web site changes visible as follows: @@ -845,7 +905,7 @@ www.apache.org automatically syncs up with people.apache.org every couple hours (the specific schedule could change).

    - +

    10. Considering a quick fix to the build tree?

    If you modify a file in the build/site tree, @@ -854,27 +914,36 @@ will likely overwrite your changes to the build tree.

    -Last updated Oct 18, 2006 +Last updated Dec 21, 2007

    +
     
    Send feedback about the website to: derby-user@db.apache.org
    +
    Modified: db/derby/site/trunk/build/site/papers/field-header-non-overflow.png URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/field-header-non-overflow.png?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== Binary files - no diff available. Modified: db/derby/site/trunk/build/site/papers/field-header-overflow.png URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/field-header-overflow.png?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== Binary files - no diff available. Modified: db/derby/site/trunk/build/site/papers/fortune_tut.html URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/fortune_tut.html?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== --- db/derby/site/trunk/build/site/papers/fortune_tut.html (original) +++ db/derby/site/trunk/build/site/papers/fortune_tut.html Fri Dec 21 14:30:38 2007 @@ -1,9 +1,9 @@ - + - + Apache Derby Fortune Server Tutorial @@ -16,49 +16,88 @@
    +
    +
    +
    - +  
    + +
    + +
    +
    + +
    -
    -Font size: +
    Font size:       @@ -499,21 +552,30 @@
    +
     
    Send feedback about the website to: derby-user@db.apache.org
    +
    Modified: db/derby/site/trunk/build/site/papers/index.html URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/index.html?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== --- db/derby/site/trunk/build/site/papers/index.html (original) +++ db/derby/site/trunk/build/site/papers/index.html Fri Dec 21 14:30:38 2007 @@ -1,9 +1,9 @@ - + - + Apache Derby Papers @@ -16,49 +16,88 @@
    +
    +
    +
    - +  
    + +
    + +

    Built with Apache Forrest - logo
    +
    + +
    -
    -Font size: +
    Font size:       @@ -532,17 +585,23 @@

    +
     
    Valid HTML 4.01!Valid CSS!
    @@ -550,6 +609,9 @@ Send feedback about the website to: derby-user@db.apache.org
    +
    Modified: db/derby/site/trunk/build/site/papers/logformats.html URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/logformats.html?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== --- db/derby/site/trunk/build/site/papers/logformats.html (original) +++ db/derby/site/trunk/build/site/papers/logformats.html Fri Dec 21 14:30:38 2007 @@ -1,9 +1,9 @@ - + - + Derby Write Ahead Log Format @@ -16,49 +16,88 @@
    + +
    +
    +
    +
    - +  
    + +
    + +
    +
    + +
    -
    -Font size: +
    Font size:       @@ -770,7 +823,7 @@

    Pointers to relevant classes

    -
    +
    Fixme (DM)
    This section should link to appropriate Javadoc documentation
    @@ -900,21 +953,30 @@
    +
     
    Send feedback about the website to: derby-user@db.apache.org
    +
    Modified: db/derby/site/trunk/build/site/papers/optimizer.html URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/optimizer.html?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== --- db/derby/site/trunk/build/site/papers/optimizer.html (original) +++ db/derby/site/trunk/build/site/papers/optimizer.html Fri Dec 21 14:30:38 2007 @@ -1,9 +1,9 @@ - + - + Derby Optimizer Design @@ -16,49 +16,88 @@
    + +
    +
    +
    +
    - +  
    + +
    + +
    +
    + +
    -
    -Font size: +
    Font size:       @@ -281,7 +334,7 @@

    Overview

    -
    +
    Note
    Jeffrey Lichtman wrote the original implementation of the optimizer. What follows below is a description of the optimizer he posted to the @@ -564,21 +617,30 @@
    +
     
    Send feedback about the website to: derby-user@db.apache.org
    +
    Modified: db/derby/site/trunk/build/site/papers/page-format.png URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/page-format.png?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== Binary files - no diff available. Modified: db/derby/site/trunk/build/site/papers/pageformats.html URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/pageformats.html?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== --- db/derby/site/trunk/build/site/papers/pageformats.html (original) +++ db/derby/site/trunk/build/site/papers/pageformats.html Fri Dec 21 14:30:38 2007 @@ -1,9 +1,9 @@ - + - + Derby On Disk Page Format @@ -16,49 +16,88 @@
    +
    +
    +
    - +  
    + +
    + +
    +
    + +
    -
    -Font size: +
    Font size:       @@ -550,7 +603,7 @@ -
    +
    Note
    Spare space is guaranteed to be writen with "0", so that future @@ -676,7 +729,7 @@ -
    +
    Long Rows
    A row is long if all of it's columns can't fit on a single page. @@ -837,7 +890,7 @@ -
    +
    Long Columns
    A column is long if it can't fit on a single page. A long column @@ -1388,21 +1441,30 @@
    +
     
    Send feedback about the website to: derby-user@db.apache.org
    +
    Modified: db/derby/site/trunk/build/site/papers/recovery.html URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/recovery.html?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== --- db/derby/site/trunk/build/site/papers/recovery.html (original) +++ db/derby/site/trunk/build/site/papers/recovery.html Fri Dec 21 14:30:38 2007 @@ -1,9 +1,9 @@ - + - + Derby Logging and Recovery @@ -16,49 +16,88 @@
    +
    +
    +
    - +  
    + +
    + +
    +
    + +
    -
    -Font size: +
    Font size:       @@ -625,7 +678,7 @@

    Transactions can be at the following states w/r to a checkpoint - consider the log as a continous stream and not as series of log files for the sake of clarity:
    - +

    @@ -851,21 +904,30 @@
     
    +
     
    Send feedback about the website to: derby-user@db.apache.org
    +
    Modified: db/derby/site/trunk/build/site/papers/versionupgrade.html URL: http://svn.apache.org/viewvc/db/derby/site/trunk/build/site/papers/versionupgrade.html?rev=606336&r1=606335&r2=606336&view=diff ============================================================================== --- db/derby/site/trunk/build/site/papers/versionupgrade.html (original) +++ db/derby/site/trunk/build/site/papers/versionupgrade.html Fri Dec 21 14:30:38 2007 @@ -1,9 +1,9 @@ - + - + Derby Versioning Scheme @@ -16,49 +16,88 @@
    +
    +
    +
    - +  
    + +
    + +
    +
    + +
    -
    -Font size: +
    Font size:       @@ -284,7 +337,7 @@

    Basic Numbering Scheme

    -
    +
    Note
    This is an overview of how the version scheme is set up in the Derby code and was intended to work for Cloudscape. It was described by Dan @@ -389,7 +442,7 @@

    Version Upgrade Mechanism

    -
    +
    Note
    This is a description of how the mechanics of the code is set up to handle upgrade and how it was intended to work for Cloudscape.
    @@ -458,7 +511,7 @@

    Upgrading System Catalogs

    -
    +
    Note
    This was described by Dan Debrunner on 16 March 2005
    @@ -571,21 +624,30 @@
    +
     
    Send feedback about the website to: derby-user@db.apache.org
    +