db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kahat...@apache.org
Subject svn commit: r1071171 - in /db/derby/code/trunk/java: engine/org/apache/derby/impl/store/access/btree/ testing/org/apache/derbyTesting/functionTests/tests/store/
Date Wed, 16 Feb 2011 08:45:55 GMT
Author: kahatlen
Date: Wed Feb 16 08:45:55 2011
New Revision: 1071171

URL: http://svn.apache.org/viewvc?rev=1071171&view=rev
Log:
DERBY-642: SELECT MAX doesn't use indices optimally

First attempt on a B-tree max scan that walks backwards. Includes some
test cases that test latch conflicts.

Added:
    db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/store/BTreeMaxScanTest.java
  (with props)
Modified:
    db/derby/code/trunk/java/engine/org/apache/derby/impl/store/access/btree/BTreeMaxScan.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/store/access/btree/BTreeScan.java
    db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/store/_Suite.java

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/store/access/btree/BTreeMaxScan.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/store/access/btree/BTreeMaxScan.java?rev=1071171&r1=1071170&r2=1071171&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/store/access/btree/BTreeMaxScan.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/store/access/btree/BTreeMaxScan.java
Wed Feb 16 08:45:55 2011
@@ -27,11 +27,6 @@ import org.apache.derby.iapi.services.sa
 
 import org.apache.derby.iapi.error.StandardException; 
 
-import org.apache.derby.iapi.store.access.RowUtil;
-import org.apache.derby.iapi.store.access.Qualifier;
-import org.apache.derby.iapi.store.access.ScanController;
-
-import org.apache.derby.iapi.store.raw.FetchDescriptor;
 import org.apache.derby.iapi.store.raw.Page;
 import org.apache.derby.iapi.store.raw.RecordHandle;
 
@@ -56,7 +51,7 @@ import org.apache.derby.iapi.store.acces
 
 /**
 
-A BTreeScan implementation that provides the 90% solution to the max on
+A BTreeScan implementation that provides the 95% solution to the max on
 btree problem.  If the row is the last row in the btree it works very
 efficiently.  This implementation will be removed once backward scan is
 fully functional.
@@ -72,13 +67,13 @@ To return the maximum row this implement
    the latch.  At this point the slot position is just right of the
    locked row.
 2) in fetchMax() it loops backward on the last leaf page, locking rows
-   as it does so, until it either finds the first non-deleted and locks
-   that row without having to wait and thus did not give up the latch on the 
-   page.  If successful it returns that row.
-3) If it is not successful in this last page search it faults over to 
-   the original implementation of max scan, which is simply a search from 
-   left to right at the leaf level for the last row in the table.
-
+   as it does so, until it finds the first non-deleted, non-NULL row.
+3) If it is not successful in this last page search it attempts to latch
+   the left sibling page, without waiting to avoid deadlocks with forward
+   scans, and continue the search on that page.
+4) If the sibling page couldn't be latched without waiting, save the
+   current position, release all latches, and restart the scan from the
+   saved position.
 
 **/
 
@@ -91,191 +86,41 @@ public class BTreeMaxScan extends BTreeS
      */
 
     /**
-     * Fetch the maximum non-deleted row from the table.
-     *
-     * Scan from left to right at the leaf level searching for the 
-     * rightmost non deleted row in the index.
+     * Move the current position to the page to the left of the current page,
+     * right after the last slot on that page. If we have to wait for a latch,
+     * give up the latch on the current leaf and give up. The caller will have
+     * to reposition and retry.
      *
-	 * @exception  StandardException  Standard exception policy.
-     **/
-    private boolean fetchMaxRowFromBeginning(
-    DataValueDescriptor[]   fetch_row)
-        throws StandardException
-	{
-        int                 ret_row_count     = 0;
-        RecordHandle        max_rh            = null;
-
-        // we need to scan until we hit the end of the table or until we
-        // run into a null.  Use this template to probe the "next" row so
-        // that if we need to finish, fetch_row will have the right value.
-        DataValueDescriptor[] check_row_template = new DataValueDescriptor[1];
-        check_row_template[0] = fetch_row[0].cloneValue(false);
-        FetchDescriptor check_row_desc = RowUtil.getFetchDescriptorConstant(1);
-
-        // reopen the scan for reading from the beginning of the table.
-        reopenScan(
-            (DataValueDescriptor[]) null,
-            ScanController.NA,
-            (Qualifier[][]) null,
-            (DataValueDescriptor[]) null,
-            ScanController.NA);
-
-        BTreeRowPosition pos = scan_position;
-
-        positionAtStartForForwardScan(pos);
-
-        // At this point:
-        // current_page is latched.  current_slot is the slot on current_page
-        // just before the "next" record this routine should process.
-
-        // loop through successive leaf pages and successive slots on those
-        // leaf pages.  Stop when either the last leaf is reached. At any
-        // time in the scan fetch_row will contain "last" non-deleted row
-        // seen.
-
-        boolean nulls_not_reached = true;
-        leaf_loop:
-		while ((pos.current_leaf != null) && nulls_not_reached)
-		{
-            slot_loop:
-			while ((pos.current_slot + 1) < pos.current_leaf.page.recordCount())
-			{
-                // unlock the previous row if doing read.
-                if (pos.current_rh != null)
-                {
-                    this.getLockingPolicy().unlockScanRecordAfterRead(
-                        pos, init_forUpdate);
-
-                    // current_rh is used to track which row we need to unlock,
-                    // at this point no row needs to be unlocked.
-                    pos.current_rh = null;
-                }
-
-                // move scan current position forward.
-                pos.current_slot++;
-                this.stat_numrows_visited++;
-
-                // get current record handle for positioning but don't read
-                // data until we verify it is not deleted.  rh is needed
-                // for repositioning if we lose the latch.
-                RecordHandle rh = 
-                    pos.current_leaf.page.fetchFromSlot(
-                        (RecordHandle) null,
-                        pos.current_slot, 
-                        check_row_template,
-                        null,
-                        true);
-
-                // lock the row.
-                boolean latch_released =
-                    !this.getLockingPolicy().lockScanRow(
-                        this, this.getConglomerate(), pos,
-                        init_lock_fetch_desc,
-                        pos.current_lock_template,
-                        pos.current_lock_row_loc,
-                        false, init_forUpdate, lock_operation);
-
-                // special test to see if latch release code works
-                if (SanityManager.DEBUG)
-                {
-                    latch_released = 
-                        test_errors(
-                            this,
-                            "BTreeMaxScan_fetchNextGroup", pos,
-                            this.getLockingPolicy(),
-                            pos.current_leaf, latch_released);
-                }
-
-                // At this point we have successfully locked this record, so
-                // remember the record handle so that it can be unlocked if
-                // necessary.  If the above lock deadlocks, we will not try
-                // to unlock a lock we never got in close(), because current_rh
-                // is null until after the lock is granted.
-                pos.current_rh = rh;
-
-                if (latch_released)
-                {
-                    // lost latch on page in order to wait for row lock.
-                    // Call reposition() which will use the saved record
-                    // handle to reposition to the same spot on the page.
-                    // If the row is no longer on the page, reposition()
-                    // will take care of searching the tree and position
-                    // on the correct page.
-                    if (!reposition(pos, false))
-                    {
-                        // Could not position on the exact same row that was
-                        // saved, which means that it has been purged.
-                        // Reposition on the row immediately to the left of
-                        // the purged row instead.
-                        if (!reposition(pos, true))
-                        {
-                            if (SanityManager.DEBUG)
-                            {
-                                SanityManager.THROWASSERT(
-                                        "Cannot fail with 2nd param true");
-                            }
-                            // reposition will set pos.current_leaf to null if
-                            // it returns false, so if this ever does fail in
-                            // delivered code, expect a NullPointerException at
-                            // the top of this loop when we call recordCount().
-                        }
-
-                        // Now we're positioned to the left of our saved
-                        // position. Go to the top of the loop so that we move
-                        // the scan to the next row and release the lock on
-                        // the purged row.
-                        continue slot_loop;
-                    }
-                }
-
-
-                if (pos.current_leaf.page.isDeletedAtSlot(pos.current_slot))
-                {
-                    this.stat_numdeleted_rows_visited++;
-
-                    if (check_row_template[0].isNull())
-                    {
-                        // nulls sort at high end and are not to be returned
-                        // by max scan, so search is over, return whatever is
-                        // in fetch_row.
-                        nulls_not_reached = false;
-                        break;
-                    }
-                }
-                else if (check_row_template[0].isNull())
-                {
-                    nulls_not_reached = false;
-                    break;
-                }
-                else 
-                {
-
-                    pos.current_leaf.page.fetchFromSlot(
-                        pos.current_rh,
-                        pos.current_slot, fetch_row, init_fetchDesc,
-                        true);
-
-                    stat_numrows_qualified++;
-                    max_rh = pos.current_rh;
-                }
-			}
-
-            // Move position of the scan to slot 0 of the next page.  If there
-            // is no next page current_page will be null.
-            positionAtNextPage(pos);
-
-            this.stat_numpages_visited++;
-		}
-
-
-        // Reached last leaf of tree.
-        positionAtDoneScan(pos);
+     * @return true if the position was successfully moved, false if we had
+     * to wait for a latch
+     */
+    private boolean moveToLeftSibling() throws StandardException {
+        try {
+            positionAtPreviousPage();
+            return true;
+        } catch (WaitError we) {
+            // We couldn't get the latch without waiting. Let's save the
+            // position and let the caller retry.
+            //
+            // If the page is empty, there is no position to save. Since
+            // positionAtPreviousPage() skips empty pages mid-scan, we know
+            // that an empty page seen here must be the rightmost leaf. In
+            // that case, the caller can simply restart the scan, so there's
+            // no need to save the position.
+            if (isEmpty(scan_position.current_leaf.getPage())) {
+                scan_position.current_leaf.release();
+                scan_position.init();
+            } else {
+                // Save the leftmost record on the page. That's the record in
+                // slot 1, since slot 0 is the control row.
+                scan_position.current_slot = 1;
+                savePositionAndReleasePage();
+            }
 
-        // we need to decrement when we stop scan at the end of the table.
-        this.stat_numpages_visited--;
+            return false;
+        }
+    }
 
-        return(max_rh != null);
-	}
 
     /**************************************************************************
      * Protected implementation of abstract methods of BTreeScan class:
@@ -419,7 +264,7 @@ public class BTreeMaxScan extends BTreeS
      * Search last page for last non deleted row, and if one is found return
      * it as max.
      *
-     * If no row found on last page, or could not find row withou losing latch
+     * If no row found on last page, or could not find row without losing latch
      * then call fetchMaxRowFromBeginning() to search from left to right
      * for maximum value in index.
      *
@@ -478,7 +323,7 @@ public class BTreeMaxScan extends BTreeS
         // At this point:
         // current_page is latched.  current_slot is the slot on current_page
         // just "right" of the "next" record this routine should process.
-        // In this case teh "next" record is the last row on the rightmost
+        // In this case the "next" record is the last row on the rightmost
         // leaf page.
 
 
@@ -487,8 +332,98 @@ public class BTreeMaxScan extends BTreeS
         // Code is positioned on the rightmost leaf of the index, the rightmost
         // non-deleted row on this page is the maximum row to return.
 
-        if ((pos.current_slot - 1) > 0)
+        leaf_loop:
+        while (!max_found && pos.current_leaf != null)
         {
+            if (pos.current_slot <= 1)
+            {
+                // Reached beginning of this leaf page without finding a
+                // value, so move position to the end of the left sibling and
+                // resume the scan.
+                boolean latch_released = !moveToLeftSibling();
+
+                if (latch_released)
+                {
+                    // The previous page was latched by someone else, so we
+                    // gave up the latch on this page to avoid running into a
+                    // deadlock with someone scanning the leaves in the
+                    // opposite direction.
+
+                    if (SanityManager.DEBUG)
+                    {
+                        SanityManager.DEBUG(
+                                "BTreeMaxScan.latchConflict",
+                                "Couldn't get latch nowait, will retry");
+                    }
+
+                    if (pos.current_positionKey == null)
+                    {
+                        // We haven't seen any rows yet, so no position has
+                        // been saved. See comment in moveToLeftSibling().
+                        // Restart the scan from the rightmost leaf.
+                        if (SanityManager.DEBUG)
+                        {
+                            SanityManager.DEBUG(
+                                    "BTreeMaxScan.latchConflict",
+                                    "Restart scan from rightmost leaf");
+                        }
+                        scan_state = SCAN_INIT;
+                        positionAtStartPosition(pos);
+                    }
+                    else if (!reposition(pos, false))
+                    {
+                        if (SanityManager.DEBUG)
+                        {
+                            SanityManager.DEBUG(
+                                    "BTreeMaxScan.latchConflict",
+                                    "Saved position is gone");
+                        }
+
+                        // The row on the saved position doesn't exist anymore,
+                        // so it must have been purged. Move to the position
+                        // immediately to the left of where the row should
+                        // have been.
+                        if (!reposition(pos, true))
+                        {
+                            if (SanityManager.DEBUG)
+                            {
+                                SanityManager.THROWASSERT(
+                                        "Cannot fail with 2nd param true");
+                            }
+                        }
+
+                        // reposition() will position to the left of the purged
+                        // row, whereas we want to be on the right side of it
+                        // since we're moving backwards.
+                        pos.current_slot++;
+                    }
+                }
+
+                // We now have one of the following scenarios:
+                //
+                // 1) Current position is right after the last row on the left
+                //    sibling page if we could move to the sibling page without
+                //    waiting for a latch.
+                // 2) Current position is on the same row as the last one we
+                //    looked at if we had to wait for a latch on the sibling
+                //    page and the row hadn't been purged before we
+                //    repositioned.
+                // 3) Current position is right after the position where we
+                //    should have found the last row we looked at if we had
+                //    to wait for a latch on the sibling page and the row was
+                //    purged before we repositioned.
+                // 4) There is no current position if we already were at the
+                //    leftmost leaf page.
+                //
+                // For scenarios 1-3, we're positioned immediately to the right
+                // of the next row we want to look at, so going to the top of
+                // the loop will make us move to the next interesting row. For
+                // scenario 4, we want to break out of the loop, which also
+                // is handled by going to the top of the loop and reevaluating
+                // the loop condition.
+                continue;
+            }
+
             // move scan backward in search of last non-deleted row on page.
             pos.current_slot--;
 
@@ -524,10 +459,33 @@ public class BTreeMaxScan extends BTreeS
 
                 if (latch_released)
                 {
-                    // had to wait on lock while lost latch, now last page of
-                    // index may have changed, give up on "easy/fast" max scan.
-                    pos.current_leaf = null;
-                    break;
+                    // Had to wait on lock while not holding the latch, so now
+                    // the current row may have been moved to another page and
+                    // we need to reposition.
+                    if (!reposition(pos, false))
+                    {
+                        // Could not position on the exact same row that was
+                        // saved, which means that it has been purged.
+                        // Reposition on the row immediately to the left of
+                        // where the purged row should have been.
+                        if (!reposition(pos, true))
+                        {
+                            if (SanityManager.DEBUG)
+                            {
+                                SanityManager.THROWASSERT(
+                                        "Cannot fail with 2nd param true");
+                            }
+                        }
+
+                        // Now we're positioned immediately to the left of our
+                        // previous position. We want to be positioned to the
+                        // right of that position so that we can restart the
+                        // scan from where we were before we came to the row
+                        // that disappeared for us. Adjust position one step
+                        // to the right and continue from the top of the loop.
+                        pos.current_slot++;
+                        continue leaf_loop;
+                    }
                 }
 
                 if (pos.current_leaf.page.isDeletedAtSlot(pos.current_slot))
@@ -573,12 +531,6 @@ public class BTreeMaxScan extends BTreeS
         // Clean up the scan based on searching through rightmost leaf of btree
         positionAtDoneScan(scan_position);
 
-        if (!max_found)
-        {
-            // max row in table was not last row in table
-            max_found = fetchMaxRowFromBeginning(fetch_row);
-        }
-
         return(max_found);
 	}
 }

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/store/access/btree/BTreeScan.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/store/access/btree/BTreeScan.java?rev=1071171&r1=1071170&r2=1071171&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/store/access/btree/BTreeScan.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/store/access/btree/BTreeScan.java
Wed Feb 16 08:45:55 2011
@@ -511,6 +511,91 @@ public abstract class BTreeScan extends 
     }
 
     /**
+     * <p>
+     * Position the scan after the last row on the previous page. Hold the
+     * latch on the current page until the previous page has been latched. If
+     * the immediate left sibling is empty, move further until a non-empty page
+     * is found or there are no more leaves to be found. The latch on the
+     * current page will be held until a non-empty left sibling page is found.
+     * </p>
+     *
+     * <p>
+     * This method never waits for a latch, as waiting for latches while
+     * holding another latch is only allowed when moving forward in the B-tree.
+     * Waiting while moving backward may result in deadlocks with scanners
+     * going forward. A {@code WaitError} is thrown if the previous page cannot
+     * be latched without waiting. {@code scan_position.current_leaf} will
+     * point to the same page as before the method was called in the case where
+     * a {@code WaitError} is thrown, and the page will still be latched.
+     * </p>
+     *
+     * @throws StandardException standard exception policy
+     * @throws WaitError if the previous page cannot be latched immediately
+     */
+    protected void positionAtPreviousPage()
+            throws StandardException, WaitError {
+        BTreeRowPosition pos = scan_position;
+
+        LeafControlRow leaf =
+                (LeafControlRow) pos.current_leaf.getLeftSibling(this);
+
+        // Skip empty leaves. We don't want to stop on empty pages while
+        // moving backwards, since pages with no rows have no keys and we will
+        // need to save the current position by key if we cannot latch a page
+        // immediately.
+        while (leaf != null && isEmpty(leaf.page))
+        {
+            final LeafControlRow next;
+            try {
+                next = (LeafControlRow) leaf.getLeftSibling(this);
+            } finally {
+                leaf.release();
+            }
+
+            // Successfully managed to latch the leaf to the left of the empty
+            // sibling page. Use that leaf instead.
+            leaf = next;
+        }
+
+        // Now that we either have the latch on the first non-empty leaf to
+        // the left of the current leaf, or we have passed the leftmost leaf,
+        // we can release the latch on the current page.
+
+        // Unlock the previous row if doing read.
+        if (pos.current_rh != null)
+        {
+            this.getLockingPolicy().unlockScanRecordAfterRead(
+                pos, init_forUpdate);
+        }
+
+        pos.current_leaf.release();
+        pos.current_leaf = leaf;
+
+        // Set up for scan to continue at the end of the page.
+        pos.current_slot = (pos.current_leaf == null) ?
+            Page.INVALID_SLOT_NUMBER : pos.current_leaf.page.recordCount();
+        pos.current_rh = null;
+    }
+
+    /**
+     * Check if a B-tree page is empty. The control row, which is always
+     * present, is not counted.
+     *
+     * @param page the B-tree page to check
+     * @return true if the page is empty, false otherwise
+     * @throws StandardException standard exception policy
+     */
+    static boolean isEmpty(Page page) throws StandardException {
+        // Because of the control row, the page should always have at least
+        // one record. It's empty if that's the only record on the page.
+        if (SanityManager.DEBUG) {
+            SanityManager.ASSERT(
+                    page.recordCount() > 0, "Page without control row?");
+        }
+        return page.recordCount() <= 1;
+    }
+
+    /**
     Position scan at "start" position.
     <p>
     Positions the scan to the slot just before the first record to be returned

Added: db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/store/BTreeMaxScanTest.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/store/BTreeMaxScanTest.java?rev=1071171&view=auto
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/store/BTreeMaxScanTest.java
(added)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/store/BTreeMaxScanTest.java
Wed Feb 16 08:45:55 2011
@@ -0,0 +1,471 @@
+/*
+ * Derby - Class org.apache.derbyTesting.functionTests.tests.store.BTreeMaxScanTest
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND,
+ * either express or implied. See the License for the specific
+ * language governing permissions and limitations under the License.
+ */
+
+package org.apache.derbyTesting.functionTests.tests.store;
+
+import java.sql.Connection;
+import java.sql.PreparedStatement;
+import java.sql.ResultSet;
+import java.sql.Statement;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import junit.framework.Test;
+import org.apache.derby.iapi.services.sanity.SanityManager;
+import org.apache.derbyTesting.junit.BaseJDBCTestCase;
+import org.apache.derbyTesting.junit.CleanDatabaseTestSetup;
+import org.apache.derbyTesting.junit.JDBC;
+import org.apache.derbyTesting.junit.TestConfiguration;
+
+/**
+ * Test cases for max queries that scan a B-tree index backwards (DERBY-642).
+ */
+public class BTreeMaxScanTest extends BaseJDBCTestCase {
+    /** List of SanityManager debug flags to reset on teardown. */
+    private List traceFlags = new ArrayList();
+
+    public BTreeMaxScanTest(String name) {
+        super(name);
+    }
+
+    /**
+     * Create a test suite with all the test cases in this class.
+     */
+    public static Test suite() {
+        // This is a test for engine functionality, so skip client/server.
+        return new CleanDatabaseTestSetup(
+                TestConfiguration.embeddedSuite(BTreeMaxScanTest.class));
+    }
+
+    /**
+     * Tear down the test environment.
+     */
+    protected void tearDown() throws Exception {
+        super.tearDown();
+        if (SanityManager.DEBUG) {
+            // If we've enabled tracing for the test case, disable it now.
+            Iterator it = traceFlags.iterator();
+            while (it.hasNext()) {
+                String flag = (String) it.next();
+                SanityManager.DEBUG_PRINT(
+                        flag, "Disable tracing for " + getName());
+                SanityManager.DEBUG_CLEAR(flag);
+            }
+        }
+    }
+
+    // TESTS
+
+    /**
+     * Test that a max scan which cannot immediately lock the rightmost row
+     * in the index, restarts the scan when it wakes up to see if the row it
+     * waited for is still the maximum row. Tests
+     * BTreeMaxScan#positionAtStartPosition.
+     */
+    public void testRestartScanAfterWaitOnMaxRow() throws Exception {
+        setAutoCommit(false);
+
+        // Populate a table with test data
+        Statement s = createStatement();
+        s.execute("create table t(x int, y int)");
+
+        PreparedStatement ins = prepareStatement("insert into t(x) values ?");
+        for (int i = 1; i <= 800; i++) {
+            ins.setInt(1, i);
+            ins.executeUpdate();
+        }
+
+        s.execute("create index i on t(x)");
+
+        commit();
+
+        // Make sure the rightmost row in the index is locked
+        s.execute("update t set y = 0 where x = 800");
+
+        Connection c2 = openDefaultConnection();
+        try {
+            c2.setAutoCommit(false);
+            Statement s2 = c2.createStatement();
+
+            // In a different thread, in a different transaction, start a max
+            // scan that will be blocked trying to lock the rightmost row.
+            Result r = asyncGetSingleResult(s2,
+                    "select max(x) from t --derby-properties index=i");
+
+            // Give the other thread two seconds to start executing and hit
+            // the lock.
+            Thread.sleep(2000L);
+
+            // Now insert a row with a higher value, so that the row the other
+            // thread is waiting for is no longer the maximum row.
+            ins.setInt(1, 801);
+            ins.executeUpdate();
+
+            // Commit, release locks, and allow the other thread to continue.
+            commit();
+
+            // Now we expect the other thread to be able to continue. It should
+            // restart the scan because it couldn't lock the rightmost row, and
+            // it should therefore see the newly inserted value 801.
+            assertEquals("801", r.get());
+
+        } finally {
+            c2.rollback();
+            c2.close();
+        }
+
+        dropTable("T");
+        commit();
+    }
+
+    /**
+     * Test that scanners that work in opposite directions don't deadlock. The
+     * test case has two threads running B-tree forward scans in parallel with
+     * two threads running B-tree (backward) max scans.
+     */
+    public void testOppositeScanDirections() throws Exception {
+        // Trace latch conflicts to see which parts of the repositioning code
+        // we exercise. This test case is supposed to test simple latch
+        // conflicts between forward scanners and backward scanners, and should
+        // result in "Couldn't get latch nowait, will retry" being written to
+        // derby.log when latch conflicts occur.
+        setTraceFlag("BTreeMaxScan.latchConflict");
+
+        setAutoCommit(false);
+
+        Statement s = createStatement();
+        s.execute("create table t(x int)");
+
+        // Insert a couple pages worth of rows, only the first 100 of them
+        // being non-null. The null values makes the max scan need to scan
+        // backwards across page boundaries to find a qualifying row.
+        PreparedStatement ins = prepareStatement("insert into t values ?");
+        final String[][] tableContents = new String[800][];
+        for (int i = 1; i <= tableContents.length; i++) {
+            String value = (i <= 100) ? Integer.toString(i) : null;
+            ins.setString(1, value);
+            ins.executeUpdate();
+            tableContents[i - 1] = new String[] { value };
+        }
+
+        s.execute("create index i on t(x)");
+
+        commit();
+
+        // Now start four threads. Two scanning the B-tree in the forward
+        // direction, and two scanning in the backward direction (max scans).
+        // These threads should not interfere with each other.
+        String forwardSQL = "select x from t --derby-properties index=i";
+        String backwardSQL = "select max(x) from t --derby-properties index=i";
+
+        final PreparedStatement[] pss = {
+            openDefaultConnection().prepareStatement(forwardSQL),
+            openDefaultConnection().prepareStatement(forwardSQL),
+            openDefaultConnection().prepareStatement(backwardSQL),
+            openDefaultConnection().prepareStatement(backwardSQL),
+        };
+
+        final Exception[] exceptions = new Exception[pss.length];
+
+        final Thread[] threads = new Thread[pss.length];
+
+        for (int i = 0; i < pss.length; i++) {
+            final int threadNo = i;
+            threads[i] = new Thread() {
+                public void run() {
+                    // The forward scan is expected to return all rows in
+                    // the table, the backward (max) scan only the highest
+                    // non-null row.
+                    String[][] expected = (threadNo < 2) ?
+                            tableContents : new String[][] {{"100"}};
+                    try {
+                        for (int j = 0; j < 1000; j++) {
+                            ResultSet rs = pss[threadNo].executeQuery();
+                            JDBC.assertFullResultSet(rs, expected);
+                        }
+                    } catch (Exception e) {
+                        exceptions[threadNo] = e;
+                    }
+                }
+            };
+            threads[i].start();
+        }
+
+        for (int i = 0; i < pss.length; i++) {
+            threads[i].join();
+            pss[i].getConnection().close();
+        }
+
+        for (int i = 0; i < exceptions.length; i++) {
+            if (exceptions[i] != null) {
+                throw exceptions[i];
+            }
+        }
+
+        dropTable("T");
+        commit();
+    }
+
+    /**
+     * <p>
+     * Test that latch conflicts between forward scans and backward (max) scans
+     * are resolved without deadlocking or other errors when the rightmost
+     * leaf page of the B-tree is empty. In that case, the backward scan must
+     * restart, since it doesn't have any saved position to return to.
+     * </p>
+     *
+     * <p>
+     * The test is performed by running two threads that scan the leaves of
+     * the B-tree in the forward direction, while at the same time two threads
+     * do a backward max scan on the same B-tree. In parallel with the threads
+     * that scan the index, the main thread will repeatedly delete the rows
+     * with the highest values in order to create a window where the scans may
+     * see an empty page, sleep a little, and then re-insert the deleted rows.
+     * </p>
+     */
+    public void testEmptyRightmostLeaf() throws Exception {
+        // Trace latch conflicts to see that we exercise the code path that
+        // handles repositioning after waiting for a latch when moving away
+        // from an empty leaf at the far-right end of the B-tree. When this
+        // code is exercised, we'll see "Restart scan from rightmost leaf"
+        // printed to derby.log.
+        setTraceFlag("BTreeMaxScan.latchConflict");
+
+        setAutoCommit(false);
+
+        Statement s = createStatement();
+        s.execute("create table t(x int)");
+
+        // Insert a couple pages worth of rows.
+        PreparedStatement ins = prepareStatement("insert into t values ?");
+        for (int i = 1; i <= 800; i++) {
+            ins.setInt(1, i);
+            ins.executeUpdate();
+        }
+
+        s.execute("create index i on t(x)");
+
+        commit();
+
+        // Now start four threads. Two scanning the B-tree in the forward
+        // direction, and two scanning in the backward direction (max scans).
+        // These threads should not interfere with each other.
+        String forwardSQL = "select x from t --derby-properties index=i";
+        String backwardSQL = "select max(x) from t --derby-properties index=i";
+
+        final PreparedStatement[] pss = {
+            openDefaultConnection().prepareStatement(forwardSQL),
+            openDefaultConnection().prepareStatement(forwardSQL),
+            openDefaultConnection().prepareStatement(backwardSQL),
+            openDefaultConnection().prepareStatement(backwardSQL),
+        };
+
+        final Exception[] exceptions = new Exception[pss.length];
+
+        final Thread[] threads = new Thread[pss.length];
+
+        final AtomicInt threadCount = new AtomicInt();
+
+        for (int i = 0; i < pss.length; i++) {
+            final int threadNo = i;
+            // Set the isolation level to read uncommitted so that the scans
+            // don't take any locks. We do this because we want to test latch
+            // conflicts, and if the scans take read locks, they'll spend most
+            // of the time waiting for the write thread to release its locks.
+            pss[i].getConnection().setTransactionIsolation(
+                    Connection.TRANSACTION_READ_UNCOMMITTED);
+            threads[i] = new Thread() {
+                public void run() {
+                    try {
+                        for (int j = 0; j < 1000; j++) {
+                            ResultSet rs = pss[threadNo].executeQuery();
+                            if (threadNo < 2) {
+                                // This is a full forward scan (SELECT *) of
+                                // the B-tree, so expect it to see between 400
+                                // and 800 rows.
+                                int rowCount = JDBC.assertDrainResults(rs);
+                                if (rowCount < 400 || rowCount > 800) {
+                                    fail("Unexpected row count: " + rowCount);
+                                }
+                            } else {
+                                // This is a max scan, so expect a single
+                                // row that contains a value between 400 and
+                                // 800.
+                                assertTrue(rs.next());
+                                int max = rs.getInt(1);
+                                if (max < 400 || max > 800) {
+                                    fail("Unexpected max value: " + max);
+                                }
+                                assertFalse(rs.next());
+                                rs.close();
+                            }
+                        }
+                    } catch (Exception e) {
+                        exceptions[threadNo] = e;
+                    } finally {
+                        threadCount.decrement();
+                    }
+                }
+            };
+            threads[i].start();
+            threadCount.increment();
+        }
+
+        // As long as the scanner threads are running, periodically delete
+        // and re-insert the last 400 rows. This empties the rightmost leaf
+        // page(s) and makes it possible for the scanners to encounter the
+        // situation where they need to reposition after a latch conflict
+        // while being positioned on an empty page with no saved position. The
+        // post-commit worker will eventually remove the pointers to the empty
+        // leaf, so we need to do this repeatedly and hope that the timing
+        // will be right at least once so that we exercise the desired path.
+        PreparedStatement deleteRows =
+                prepareStatement("delete from t where x > 400");
+        PreparedStatement insertRows =
+                prepareStatement("insert into t select x+400 from t");
+        while (threadCount.get() > 0) {
+            // Delete rows in range [401, 800].
+            assertEquals("deleted rows", 400, deleteRows.executeUpdate());
+            commit();
+
+            // Sleep a little while so that we don't fill the empty page
+            // before the scanners have seen it.
+            Thread.sleep(100L);
+
+            // Re-insert rows in range [401, 800].
+            assertEquals("inserted rows", 400, insertRows.executeUpdate());
+            commit();
+        }
+
+        for (int i = 0; i < pss.length; i++) {
+            threads[i].join();
+            pss[i].getConnection().close();
+        }
+
+        for (int i = 0; i < exceptions.length; i++) {
+            if (exceptions[i] != null) {
+                throw exceptions[i];
+            }
+        }
+
+        dropTable("T");
+        commit();
+    }
+
+    // HELPER METHODS
+
+    /**
+     * This class represents a result from an asynchronous operation.
+     */
+    private static class Result {
+        private boolean complete;
+        private Exception ex;
+        private String value;
+
+        synchronized void error(Exception ex) {
+            this.ex = ex;
+            this.complete = true;
+            notifyAll();
+        }
+
+        synchronized void set(String value) {
+            this.value = value;
+            this.complete = true;
+            notifyAll();
+        }
+
+        synchronized String get() throws Exception {
+            while (!complete) {
+                wait();
+            }
+            if (ex != null) {
+                throw ex;
+            } else {
+                return value;
+            }
+        }
+    }
+
+    /**
+     * Execute a statement asynchronously and return an object that can be
+     * used to retrieve the result once the statement is complete. The
+     * statement should return a single value.
+     *
+     * @param s the statement object to use for execution
+     * @param sql the SQL to execute
+     * @return a {@code Result} object that allows retrieval of the result
+     * once it's available
+     */
+    private static Result asyncGetSingleResult(
+            final Statement s, final String sql) {
+        final Result result = new Result();
+
+        Thread t = new Thread() {
+            public void run() {
+                try {
+                    ResultSet rs = s.executeQuery(sql);
+                    assertEquals("expected single value",
+                            1, rs.getMetaData().getColumnCount());
+                    assertTrue("empty result", rs.next());
+                    String val = rs.getString(1);
+                    assertFalse("multiple rows", rs.next());
+                    rs.close();
+                    result.set(val);
+                } catch (Exception e) {
+                    result.error(e);
+                }
+            }
+        };
+
+        t.start();
+
+        return result;
+    }
+
+    /**
+     * If running with a debug build and derby.tests.trace is true, enable
+     * tracing for messages with the specified flag.
+     *
+     * @param flag the debug flag to enable
+     */
+    private void setTraceFlag(String flag) {
+        if (SanityManager.DEBUG && TestConfiguration.getCurrent().doTrace()) {
+            SanityManager.DEBUG_PRINT(flag, "Enable tracing for " + getName());
+            SanityManager.DEBUG_SET(flag);
+            traceFlags.add(flag);
+        }
+    }
+
+    /**
+     * Poor man's replacement for java.util.concurrent.atomic.AtomicInteger
+     * that runs on platforms where java.util.concurrent isn't available.
+     */
+    private static class AtomicInt {
+        private int i;
+        synchronized void increment() {
+            i++;
+        }
+        synchronized void decrement() {
+            i--;
+        }
+        synchronized int get() {
+            return i;
+        }
+    }
+}

Propchange: db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/store/BTreeMaxScanTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/store/_Suite.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/store/_Suite.java?rev=1071171&r1=1071170&r2=1071171&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/store/_Suite.java
(original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/tests/store/_Suite.java
Wed Feb 16 08:45:55 2011
@@ -71,6 +71,7 @@ public class _Suite extends BaseTestCase
         suite.addTest(AccessTest.suite());
         suite.addTest(AutomaticIndexStatisticsTest.suite());
         suite.addTest(AutomaticIndexStatisticsMultiTest.suite());
+        suite.addTest(BTreeMaxScanTest.suite());
         
         /* Tests that only run in sane builds */
         if (SanityManager.DEBUG) {



Mime
View raw message