db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From j..@apache.org
Subject svn commit: r278667 - in /db/derby/site/trunk: build/site/papers/btree_package.html src/documentation/content/xdocs/papers/btree_package.html
Date Mon, 05 Sep 2005 02:47:15 GMT
Author: jta
Date: Sun Sep  4 19:47:13 2005
New Revision: 278667

URL: http://svn.apache.org/viewcvs?rev=278667&view=rev
Log:
Expanded @link references in btree_package.html to javadoc pages.

Modified:
    db/derby/site/trunk/build/site/papers/btree_package.html
    db/derby/site/trunk/src/documentation/content/xdocs/papers/btree_package.html

Modified: db/derby/site/trunk/build/site/papers/btree_package.html
URL: http://svn.apache.org/viewcvs/db/derby/site/trunk/build/site/papers/btree_package.html?rev=278667&r1=278666&r2=278667&view=diff
==============================================================================
--- db/derby/site/trunk/build/site/papers/btree_package.html (original)
+++ db/derby/site/trunk/build/site/papers/btree_package.html Sun Sep  4 19:47:13 2005
@@ -199,6 +199,14 @@
 </li>
 <li>
 <a href="#Garbage+Collection+of+deleted+keys">Garbage Collection of deleted keys</a>
+<ul class="minitoc">
+<li>
+<a href="#Online+during+BTREE+split">Online during BTREE split</a>
+</li>
+<li>
+<a href="#BTREE+post+commit+work">BTREE post commit work</a>
+</li>
+</ul>
 </li>
 <li>
 <a href="#Logging+and+Recovery">Logging and Recovery</a>
@@ -221,23 +229,23 @@
 <h2 class="boxed">High level structure of the B+Tree</h2>
 <div class="section">
 <ul>
-<li>The first row in all pages, branch or leaf, is a control row. In branch pages,
this is a {@link org.apache.derby.impl.store.access.btree.BranchControlRow BranchControlRow}
and in leaf pages, it is a {@link org.apache.derby.impl.store.access.btree.LeafControlRow
LeafControlRow}.</li>
-<li>In addition to the BranchControlRow, branch level pages contain {@link org.apache.derby.impl.store.access.btree.BranchRow
BranchRows}.</li>
+<li>The first row in all pages, branch or leaf, is a control row. In branch pages,
this is a <a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/impl/store/access/btree/BranchControlRow.html">BranchControlRow</a>
and in leaf pages, it is a <a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/impl/store/access/btree/LeafControlRow.html">LeafControlRow</a>.</li>
+<li>In addition to the BranchControlRow, branch level pages contain <a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/impl/store/access/btree/BranchRow.html">BranchRows</a>.</li>
 <li>At branch level, a page is linked to is left and right siblings, parent, as well
as children. The number of child pages is 1 greater than the number of BranchRows in the page.
The leftmost child pointer is stored in the BranchControlRow itself. Each BranchRow contains
a child pointer as its last column.</li>
-<li>At leaf level also, a page is linked to its left and right siblings, and the parent.
In addition to the LeafControlRow, leaf level pages contain {@link org.apache.derby.impl.sql.execute.IndexRow
IndexRows}. The last column in an IndexRow is a {@link org.apache.derby.iapi.types.RowLocation
RowLocation}.</li>
-<li>IndexRows are generated by the {@link org.apache.derby.iapi.sql.dictionary.IndexRowGenerator
IndexRowGenerator}.</li>
+<li>At leaf level also, a page is linked to its left and right siblings, and the parent.
In addition to the LeafControlRow, leaf level pages contain <a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/impl/sql/execute/IndexRow.html">IndexRows</a>.
The last column in an IndexRow is a <a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/iapi/types/RowLocation.html">RowLocation</a>.</li>
+<li>IndexRows are generated by the <a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/iapi/sql/dictionary/IndexRowGenerator.html">IndexRowGenerator</a>.</li>
 </ul>
 </div>
-<a name="N1003E"></a><a name="Latching+implementation"></a>
+<a name="N10056"></a><a name="Latching+implementation"></a>
 <h2 class="boxed">Latching implementation</h2>
 <div class="section">
 <p>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 modifications are all isolated from
other operations through the use of latches.</p>
 </div>
-<a name="N10044"></a><a name="Locking+and+Isolation+Levels"></a>
+<a name="N1005C"></a><a name="Locking+and+Isolation+Levels"></a>
 <h2 class="boxed">Locking and Isolation Levels</h2>
 <div class="section">
 <p>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).</p>
-<p>In data only locking the key for all locks whether obtained in the BTree or in the
base table is the address of the base table row. In the BTree case the address of the base
table row ({@link org.apache.derby.iapi.types.RowLocation RowLocation}) is always the last
column of the leaf index entry ({@link org.apache.derby.impl.sql.execute.IndexRow IndexRows}).</p>
+<p>In data only locking the key for all locks whether obtained in the BTree or in the
base table is the address of the base table row. In the BTree case the address of the base
table row (<a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/iapi/types/RowLocation.html">RowLocation</a>)
is always the last column of the leaf index entry (<a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/impl/sql/execute/IndexRow.html">IndexRows</a>).</p>
 <dl>
 <dt>Serializable</dt>
 <dd>Derby uses "previous key" locking to prevent phantoms from being inserted into
a range being accessed by a scan. A scan always locks the index row just "previous" to the
first entry that satisfies the scan condition and then all index entries going forward until
the end of the scan. All row locks are held until end of transaction. Inserts also get previous
key locks, which will block if the existing row is locked.</dd>
@@ -249,7 +257,7 @@
 <dd>No row locks are acquired. The code still gets table level intent locks to prevent
concurrent DDL during the query.</dd>
 </dl>
 </div>
-<a name="N1005D"></a><a name="BTree+Structure+Modifications"></a>
+<a name="N1007D"></a><a name="BTree+Structure+Modifications"></a>
 <h2 class="boxed">BTree Structure Modifications</h2>
 <div class="section">
 <p>In Derby, SMOs (structure modification operations - ie. page splits), only happen
top down. This is not as concurrent as bottom up in <a class="external" href="http://www.almaden.ibm.com/u/mohan/RJ6846.pdf">ARIES/IM</a>,
but is simpler. As in ARIES/IM <q>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.</q>
@@ -258,17 +266,24 @@
 <p>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.</p>
 <p>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.</p>
 </div>
-<a name="N1006F"></a><a name="Logical+Key+Deletes"></a>
+<a name="N1008F"></a><a name="Logical+Key+Deletes"></a>
 <h2 class="boxed">Logical Key Deletes</h2>
 <div class="section">
 <p>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).</p>
 </div>
-<a name="N10075"></a><a name="Garbage+Collection+of+deleted+keys"></a>
+<a name="N10095"></a><a name="Garbage+Collection+of+deleted+keys"></a>
 <h2 class="boxed">Garbage Collection of deleted keys</h2>
 <div class="section">
 <p>Since rows are only marked as "deleted", and not physically removed, it is necessary
to perform space reclamation on deleted rows.</p>
+<a name="N1009B"></a><a name="Online+during+BTREE+split"></a>
+<h3 class="boxed">Online during BTREE split</h3>
+<p>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}.</p>
+<a name="N100A1"></a><a name="BTREE+post+commit+work"></a>
+<h3 class="boxed">BTREE post commit work</h3>
+<p>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.</p>
+<p>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</p>
 </div>
-<a name="N1007B"></a><a name="Logging+and+Recovery"></a>
+<a name="N100A9"></a><a name="Logging+and+Recovery"></a>
 <h2 class="boxed">Logging and Recovery</h2>
 <div class="section">
 <p>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.</p>

Modified: db/derby/site/trunk/src/documentation/content/xdocs/papers/btree_package.html
URL: http://svn.apache.org/viewcvs/db/derby/site/trunk/src/documentation/content/xdocs/papers/btree_package.html?rev=278667&r1=278666&r2=278667&view=diff
==============================================================================
--- db/derby/site/trunk/src/documentation/content/xdocs/papers/btree_package.html (original)
+++ db/derby/site/trunk/src/documentation/content/xdocs/papers/btree_package.html Sun Sep
 4 19:47:13 2005
@@ -29,13 +29,12 @@
 <h1>High level structure of the B+Tree</h1>
 <ul>
 	<li>The first row in all pages, branch or leaf, is a control row. In
-	branch pages, this is a {@link
-	org.apache.derby.impl.store.access.btree.BranchControlRow
-	BranchControlRow} and in leaf pages, it is a {@link
-	org.apache.derby.impl.store.access.btree.LeafControlRow
-	LeafControlRow}.</li>
+	branch pages, this is a 
+        <a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/impl/store/access/btree/BranchControlRow.html">BranchControlRow</a>
+         and in leaf pages, it is a
+        <a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/impl/store/access/btree/LeafControlRow.html">LeafControlRow</a>.</li>
 	<li>In addition to the BranchControlRow, branch level pages contain
-	{@link org.apache.derby.impl.store.access.btree.BranchRow BranchRows}.
+<a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/impl/store/access/btree/BranchRow.html">BranchRows</a>.
 	</li>
 	<li>At branch level, a page is linked to is left and right siblings,
 	parent, as well as children. The number of child pages is 1 greater
@@ -44,12 +43,11 @@
 	child pointer as its last column.</li>
 	<li>At leaf level also, a page is linked to its left and right
 	siblings, and the parent. In addition to the LeafControlRow, leaf level
-	pages contain {@link org.apache.derby.impl.sql.execute.IndexRow
-	IndexRows}. The last column in an IndexRow is a {@link
-	org.apache.derby.iapi.types.RowLocation RowLocation}.</li>
-	<li>IndexRows are generated by the {@link
-	org.apache.derby.iapi.sql.dictionary.IndexRowGenerator
-	IndexRowGenerator}.</li>
+	pages contain 
+        <a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/impl/sql/execute/IndexRow.html">IndexRows</a>.
The last column in an IndexRow is a 
+        <a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/iapi/types/RowLocation.html">RowLocation</a>.</li>
+	<li>IndexRows are generated by the 
+        <a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/iapi/sql/dictionary/IndexRowGenerator.html">IndexRowGenerator</a>.</li>
 </ul>
 <h1>Latching implementation</h1>
 <p>Derby uses latches on pages to get exclusive access to the page while
@@ -74,10 +72,8 @@
 not support non-locking isolation such as multi-versioning).</p>
 <p>In data only locking the key for all locks whether obtained in the
 BTree or in the base table is the address of the base table row. In the
-BTree case the address of the base table row ({@link
-org.apache.derby.iapi.types.RowLocation RowLocation}) is always the last
-column of the leaf index entry ({@link
-org.apache.derby.impl.sql.execute.IndexRow IndexRows}).</p>
+BTree case the address of the base table row (<a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/iapi/types/RowLocation.html">RowLocation</a>)
is always the last
+column of the leaf index entry (<a href="http://db.apache.org/derby/javadoc/engine/org/apache/derby/impl/sql/execute/IndexRow.html">IndexRows</a>).</p>
 <dl>
 	<dt>Serializable</dt>
 	<dd>Derby uses "previous key" locking to prevent phantoms from being
@@ -136,15 +132,16 @@
 <p>Since rows are only marked as "deleted", and not physically removed,
 it is necessary to perform space reclamation on deleted rows.</p>
 <p></p>
-<h3>Online during BTREE split</h3>
+<h2>Online during BTREE split</h2>
 <p>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}.</p>
-<h3>BTREE post commit work</h3>
+org.apache.derby.impl.store.access.btree.BTreeController.reclaim_deleted_rows}.
+</p>
+<h2>BTREE post commit work</h2>
 <p>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



Mime
View raw message