Merge lp:~pbeaman/akiban-persistit/tree-visitor-prototype into lp:akiban-persistit

[Peter Beaman]

Adds new Exchange#traverse methods and a new interface Exchange.TraverseVisitor. JavaDoc for these describes the functionality and restrictions.

A simple benchmark loop showed that the TraverseVisitor produces key-value pairs almost twice as fast as a regular traverse operations.

Fortunately, the implementation turned out to be extremely simple so very little delicate Exchange code needed to be disturbed.

This is a proposal is intended to help review the design. Probably the best way to evaluate it is to look at the diff and experiment with it as a prototype. I expect we'll go back and forth on things a bit before final approval into trunk.

[Peter Beaman (pbeaman)]

Comments from email by Yuval:

On Tue, Dec 18, 2012 at 4:58 PM, Peter Beaman <email address hidden> wrote:
Must not modify the state of the Exchange instance. The visit method may use any accessor method on the Exchange, including Exchange.getKey() and Exchange.getValue(). However, the key value itself should not be modified.

It would be nice if we could get at this via the type system. Specifically, we could create interfaces for Exchange, Key and Values which contain only the read-only methods for each of those classes, and have TraverseVisitor.visit take a ReadExchange instead of an Exchange

Must not perform update operations affecting the Tree on which this Exchange operates.

What happens if the visitor breaks this constraint (or the one above, if we don't do the interface idea -- or if we do, but don't use a delegate pattern so that the visitor can just downcast its ReadExchange to Exchange)? It'd be nice if we could put some fail-fast check in there. Since the javadoc implies that there's some sort of Tree-grained (or larger?) lock taken during the visit, it'd be easy to add a "boolean visitHappening" and check this during all modification operations. It wouldn't even need to be volatile, since the lock will provide the HB edge.

[Peter Beaman (pbeaman)]

Thanks for the suggestion. I have modified the merge proposal to include a new ReadOnlyExchange interface that supplied only "safe" methods. The instance passed to visit is the original Exchange, so a perverse program could cast it. But the documentation and intent are clear, I believe.

I also added tests to prove that the methods provided by ReadOnlyExchange are indeed safe. It turns out that the visitor can indeed modify the key without causing an unwanted side-effects, so that restriction is removed. This may actually be a desirable operation for a visitor. For example, it might be useful to do a deep traversal of a group, but to skip over unwanted branches. A TraverseVisitor could detect that an unwanted branch has been entered and modify the key to skip past it.

There's no really good way to add safety checks to prevent code using this method from deadlocking, so I think we continue to need a warning The issue is that any call to modify any Tree from any Exchange is susceptible to the problem. We already spend a fair amount of CPU cycles checking for incorrect code patterns; in this case I think a warning is sufficient.

[Nathan Williams (nwilliams)]

Sorry for the review slowness.

There is extremely little to actually do the visitor -- nice!

However, I'm not so sure that all the methods on ReadOnlyExchange are "safe". They are truly read only, but they do modify internal state. A nested traverse, due to calling one of the has* methods, would bork the _spareKey1, I think.

My only other nit is that the ReadOnlyExchange is an interface so the abstract clauses on each method are superfluous. Persistit has interface styles with both, but my 'druthers would be new ones without.

review: Needs Information

[Peter Beaman (pbeaman)]

Good catch on the calls to traverse. I removed the hasXXX methods from ReadOnlyExchange. I had to do something ugly to the unit test that actually used them, and would gladly accept a suggestion for something better.

Re the "abstract" clauses, my 'druthers too. They came from the Eclipse refactor operation I did to create the class in the the first place and I didn't notice them. Overall, using refactoring to create this interface resulted in more problems them it solved - it was an educational experience.

[Nathan Williams (nwilliams)]

I think isValueDefined() is also a hidden traverse, as it is actually isKeyDefined().

The unit test doesn't bother me much. It's simple and easy to change if ever needed.

Looks good otherwise.

[Peter Beaman (pbeaman)]

Yes, you're right. Removed.

[Peter Beaman (pbeaman)]

A-pproving, per discussion with Tim and Nathan.

[Akiban Build User (build-akiban)]

There were 2 failures during build/test:

* job server-packages failed at build number 2960: http://172.16.20.104:8080/job/server-packages/2960/

* view must-pass failed: server-packages is red

review: Needs Fixing

[Peter Beaman (pbeaman)]

Packaging error. Will re A-pprove this.

=== modified file 'src/main/java/com/persistit/Exchange.java'
--- src/main/java/com/persistit/Exchange.java	2012-11-28 19:07:46 +0000
+++ src/main/java/com/persistit/Exchange.java	2013-01-07 23:12:21 +0000
@@ -132,7 +132,7 @@
  * 
  * @version 1.0
  */
-public class Exchange {
+public class Exchange implements ReadOnlyExchange {
 
     public enum Sequence {
         NONE, FORWARD, REVERSE
@@ -639,6 +639,44 @@
     }
 
     /**
+     * A visitor used with the
+     * {@link Exchange#traverse(Key.Direction, boolean, int, TraverseVisitor)}
+     * The {@link #visit(ReadOnlyExchange)} method is called once for each
+     * <code>Key</code> traversed by the <code>traverse</code> method.
+     */
+    public interface TraverseVisitor {
+        /**
+         * Receive an Exchange having <code>Key</code> and <code>Value</code>
+         * values set by
+         * {@link Exchange#traverse(Key.Direction, boolean, int, TraverseVisitor)}
+         * . This method will be called once for each key encountered in the
+         * traversal. This method may return <code>false</code> to stop
+         * traversing additional keys. </p>
+         * <p>
+         * The implementation of this method:
+         * <ul>
+         * <li>Must return quickly, especially in a multi-threaded environment,
+         * to avoid blocking other threads that may attempt to update records in
+         * the same <code>Buffer</code>,
+         * <li>Must not perform update operations on any <codeExchange</code>,
+         * especially in a multi-threaded environment, to prevent deadlocks,
+         * <li>May read and modify the <code>Key</code> and <code>Value</code>
+         * fields of the supplied <code>ReadOnlyExchange</code>. Note, however,
+         * that modifying the <code>Key</code> affects the results of subsequent
+         * traversal operations.
+         * </ul>
+         * 
+         * @param ex
+         *            a {@link ReadOnlyExchange} from which the current
+         *            <code>Key</code> and <code>Value</code> may be read
+         * @return <code>true</code> to continue traversing keys, or
+         *         <code>false</code> to stop
+         * @throws PersistitException
+         */
+        public boolean visit(final ReadOnlyExchange ex) throws PersistitException;
+    }
+
+    /**
      * Delegate to {@link Key#reset} on the associated <code>Key</code> object.
      * 
      * @return This <code>Exchange</code> to permit method call chaining.
@@ -893,6 +931,7 @@
      * 
      * @return This <code>Key</code>.
      */
+    @Override
     public Key getKey() {
         assertCorrectThread(true);
         return _key;
@@ -903,6 +942,7 @@
      * 
      * @return The <code>Value</code>.
      */
+    @Override
     public Value getValue() {
         assertCorrectThread(true);
         return _value;
@@ -918,6 +958,7 @@
      * 
      * @return The <code>Volume</code>.
      */
+    @Override
     public Volume getVolume() {
         assertCorrectThread(true);
         return _volume;
@@ -928,6 +969,7 @@
      * 
      * @return The <code>Tree</code>
      */
+    @Override
     public Tree getTree() {
         assertCorrectThread(true);
         return _tree;
@@ -938,6 +980,7 @@
      * 
      * @return The <code>Persistit</code> instance.
      */
+    @Override
     public Persistit getPersistitInstance() {
         assertCorrectThread(true);
         return _persistit;
@@ -952,6 +995,7 @@
      * 
      * @return The change count
      */
+    @Override
     public long getChangeCount() {
         assertCorrectThread(true);
         return _tree.getChangeCount();
@@ -2010,7 +2054,7 @@
      */
     public boolean traverse(final Direction direction, final boolean deep, final int minimumBytes)
             throws PersistitException {
-        return traverse(direction, deep, minimumBytes, 0, 0);
+        return traverse(direction, deep, minimumBytes, 0, 0, null);
     }
 
     /**
@@ -2027,10 +2071,9 @@
      *            visibility</i>, <code>false</code> is immediately returned.
      */
     private boolean traverse(final Direction direction, final boolean deep, final int minimumBytes,
-            final int minKeyDepth, final int matchUpToIndex) throws PersistitException {
+            final int minKeyDepth, final int matchUpToIndex, final TraverseVisitor visitor) throws PersistitException {
         assertCorrectThread(true);
         _persistit.checkClosed();
-
         final Key spareKey = _spareKey1;
         final boolean doFetch = minimumBytes > 0;
         final boolean doModify = minimumBytes >= 0;
@@ -2038,8 +2081,9 @@
         final Value outValue = doFetch ? _value : _spareValue;
         outValue.clear();
 
+        Direction dir = direction;
         Buffer buffer = null;
-        boolean edge = direction == EQ || direction == GTEQ || direction == LTEQ;
+        boolean edge = dir == EQ || dir == GTEQ || dir == LTEQ;
         boolean nudged = false;
 
         if (_key.getEncodedSize() == 0) {
@@ -2121,11 +2165,11 @@
                     matches = true;
                 } else if (edge && !deep && Buffer.decodeDepth(foundAt) == index) {
                     matches = true;
-                } else if (direction == EQ) {
+                } else if (dir == EQ) {
                     matches = false;
                 } else {
                     edge = false;
-                    foundAt = buffer.traverse(_key, direction, foundAt);
+                    foundAt = buffer.traverse(_key, dir, foundAt);
                     if (buffer.isAfterRightEdge(foundAt)) {
                         final long rightSiblingPage = buffer.getRightSibling();
 
@@ -2139,7 +2183,7 @@
                             //
                             buffer = rightSibling;
                             checkPageType(buffer, PAGE_TYPE_DATA, false);
-                            foundAt = buffer.traverse(_key, direction, buffer.toKeyBlock(0));
+                            foundAt = buffer.traverse(_key, dir, buffer.toKeyBlock(0));
                             matches = !buffer.isAfterRightEdge(foundAt);
                         } else {
                             matches = false;
@@ -2189,14 +2233,14 @@
                     matches = false;
                 } else {
                     if (deep) {
-                        matches |= direction != EQ;
+                        matches |= dir != EQ;
                         index = _key.getEncodedSize();
 
                         if (matches) {
                             matches = fetchFromBufferInternal(buffer, outValue, foundAt, minimumBytes);
-                            if (!matches && direction != EQ) {
+                            if (!matches && dir != EQ) {
                                 nudged = false;
-                                nudgeForMVCC = (direction == GTEQ || direction == LTEQ);
+                                nudgeForMVCC = (dir == GTEQ || dir == LTEQ);
                                 buffer.release();
                                 buffer = null;
                                 continue;
@@ -2225,10 +2269,10 @@
                                     nudged = false;
                                     buffer.release();
                                     buffer = null;
-                                    if (direction == EQ) {
+                                    if (dir == EQ) {
                                         matches = false;
                                     } else {
-                                        nudgeForMVCC = (direction == GTEQ || direction == LTEQ);
+                                        nudgeForMVCC = (dir == GTEQ || dir == LTEQ);
                                         continue;
                                     }
                                 }
@@ -2284,6 +2328,18 @@
                 // Done
                 _volume.getStatistics().bumpTraverseCounter();
                 _tree.getStatistics().bumpTraverseCounter();
+                if (matches && visitor != null && visitor.visit(this)) {
+                    nudged = false;
+                    edge = false;
+                    if (dir == GTEQ) {
+                        dir = GT;
+                    } else if (dir == LTEQ) {
+                        dir = LT;
+                    } else if (dir == EQ) {
+                        return false;
+                    }
+                    continue;
+                }
                 return matches;
             }
         } finally {
@@ -2296,6 +2352,91 @@
 
     /**
      * <p>
+     * Performs generalized tree traversal using a {@link TraverseVisitor}. The
+     * direction value indicates whether to traverse forward or backward in
+     * collation sequence and whether the key being sought must be strictly
+     * greater than or less than the supplied key.
+     * </p>
+     * <p>
+     * Unlike {@link #traverse(Key.Direction, boolean, int)}, this method does
+     * not return each time a new key is encountered in the traversal. Instead,
+     * the {@link TraverseVisitor#visit(ReadOnlyExchange)} method is called once
+     * for each key. This method avoids performing initial verification of the
+     * key value and usually avoids locking a <code>Buffer</code> for every
+     * record returned. It may offer better performance in circumstances where a
+     * long sequence of keys is being examined. Note that
+     * <code>ReadOnlyExchange</code> is an interface implemented by this class
+     * which supplies the subset of methods that may be used safely within the
+     * visitor.
+     * </p>
+     * <p>
+     * During the call the {@link Buffer} containing the key is locked with a
+     * non-exclusive claim, and any thread attempting to update records in the
+     * same <code>Buffer</code> will block. Therefore the <code>visit</code>
+     * method must be written carefully. See
+     * {@link TraverseVisitor#visit(ReadOnlyExchange)} for guidelines.
+     * </p>
+     * <p>
+     * This method normally modifies both the <code>Key</code> and
+     * <code>Value</code> fields of this <code>Exchange</code>: the
+     * <code>Key</code> is modified to reflect the key found through traversal,
+     * and the <code>Value</code> field is modified to contain the value
+     * associated with that key. However, this behavior can be modified by the
+     * <code>minimumBytes</code> parameter. If <code>minimumBytes</code> is less
+     * than or equal to zero then only the <code>Key</code> is modified. If it
+     * is greater than zero, then the traverse method may choose to populate
+     * only the specified number of bytes of the <code>Value</code>.
+     * </p>
+     * <p>
+     * The <code>direction</code> value must be one of:
+     * <dl>
+     * <dt>Key.GT:</dt>
+     * <dd>Find the next key that is strictly greater than the supplied key. If
+     * there is none, return false.</dd>
+     * <dt>Key.GTEQ:</dt>
+     * <dd>If the supplied key exists in the database, return that key;
+     * otherwise find the next greater key and return it.</dd>
+     * <dt>Key.EQ:</dt>
+     * <dd>Return <code>true</code> iff the specified key exists in the
+     * database. Does not update the Key.</dd>
+     * <dt>Key.LT:</dt>
+     * <dd>Find the next key that is strictly less than the supplied key. If
+     * there is none, return false.</dd>
+     * <dt>Key.LTEQ:</dt>
+     * <dd>If the supplied key exists in the database, return that key;
+     * otherwise find the next smaller key and return it.</dd>
+     * </dl>
+     * </p>
+     * 
+     * @param direction
+     *            One of Key.GT, Key.GTEQ, Key.EQ, Key.LT or Key.LTEQ.
+     * 
+     * @param deep
+     *            Determines whether the result should represent the next (or
+     *            previous) physical key in the <code>Tree</code> or should be
+     *            restricted to just the logical siblings of the current key.
+     *            (See <a href="Key.html#_keyChildren">Logical Key Children and
+     *            Siblings</a>).
+     * 
+     * @param minimumBytes
+     *            The minimum number of bytes to fetch. See {@link #fetch(int)}.
+     * 
+     * @param visitor
+     *            The application-supplied <code>TraverseVisitor</code>.
+     * 
+     * @return <code>true</code> if additional keys remaining in the traversal
+     *         set, or <code>false</code> to indicate that keys are exhausted.
+     * 
+     * @throws PersistitException
+     */
+
+    public boolean traverse(final Direction direction, final boolean deep, final int minimumBytes,
+            final TraverseVisitor visitor) throws PersistitException {
+        return traverse(direction, deep, Math.max(0, minimumBytes), 0, 0, visitor);
+    }
+
+    /**
+     * <p>
      * Performs generalized tree traversal constrained by a supplied
      * {@link KeyFilter}. The direction value indicates whether to traverse
      * forward or backward in collation sequence, and whether the key being
@@ -2370,7 +2511,7 @@
             }
             if (keyFilter.isKeyPrefixFilter()) {
                 return traverse(direction, true, minBytes, keyFilter.getMinimumDepth(),
-                        keyFilter.getKeyPrefixByteCount());
+                        keyFilter.getKeyPrefixByteCount(), null);
             }
             final boolean matched = traverse(direction, true, minBytes);
             totalVisited += _keysVisitedDuringTraverse;
@@ -2929,7 +3070,7 @@
         assertCorrectThread(true);
         _key.copyTo(_spareKey2);
         final int size = _key.getEncodedSize();
-        final boolean result = traverse(GT, true, 0, _key.getDepth() + 1, size);
+        final boolean result = traverse(GT, true, 0, _key.getDepth() + 1, size, null);
         _spareKey2.copyTo(_key);
         return result;
     }
@@ -3834,7 +3975,7 @@
             _value.setPointerPageType(buffer.getPageType());
             buffer.release();
             buffer = null;
-            storeInternal(_spareKey2, _value, level + 1, Exchange.StoreOptions.NONE);
+            storeInternal(_spareKey2, _value, level + 1, StoreOptions.NONE);
             return true;
         } finally {
             _treeHolder.release();
@@ -3887,6 +4028,7 @@
      * 
      * @return The <code>Transaction</code> context for this thread.
      */
+    @Override
     public Transaction getTransaction() {
         assertCorrectThread(true);
         return _transaction;

=== added file 'src/main/java/com/persistit/ReadOnlyExchange.java'
--- src/main/java/com/persistit/ReadOnlyExchange.java	1970-01-01 00:00:00 +0000
+++ src/main/java/com/persistit/ReadOnlyExchange.java	2013-01-07 23:12:21 +0000
@@ -0,0 +1,82 @@
+/**
+ * Copyright © 2012 Akiban Technologies, Inc.  All rights reserved.
+ * 
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ * 
+ * This program may also be available under different license terms.
+ * For more information, see www.akiban.com or contact [e-mail].
+ * 
+ * Contributors:
+ * Akiban Technologies, Inc.
+ */
+
+package com.persistit;
+
+/**
+ * Methods of the {@link Exchange} class that are safe to use within a
+ * {@link Exchange.TraverseVisitor}.
+ * 
+ * @author peter
+ */
+public interface ReadOnlyExchange {
+
+    /**
+     * Return the {@link Key} associated with this <code>Exchange</code>.
+     * 
+     * @return This <code>Key</code>.
+     */
+    public Key getKey();
+
+    /**
+     * Return the {@link Value} associated with this <code>Exchange</code>.
+     * 
+     * @return The <code>Value</code>.
+     */
+    public Value getValue();
+
+    /**
+     * Return the {@link Volume} containing the data accessed by this
+     * <code>Exchange</code>.
+     * 
+     * @return The <code>Volume</code>.
+     */
+    public Volume getVolume();
+
+    /**
+     * Return the {@link Tree} on which this <code>Exchange</code> operates.
+     * 
+     * @return The <code>Tree</code>
+     */
+    public Tree getTree();
+
+    /**
+     * Return the Persistit instance from which this Exchange was created.
+     * 
+     * @return The <code>Persistit</code> instance.
+     */
+    public Persistit getPersistitInstance();
+
+    /**
+     * Return the count of structural changes committed to the {@link Tree} on
+     * which this <code>Exchange</code> operates. This count includes changes
+     * committed by all Threads, including the current one. A structural change
+     * is one in which at least one key is inserted or deleted. Replacement of
+     * an existing value is not counted.
+     * 
+     * @return The change count
+     */
+    public long getChangeCount();
+
+    /**
+     * The transaction context for this Exchange. By default, this is the
+     * transaction context of the current thread, and by default, all
+     * <code>Exchange</code>s created by a thread share the same transaction
+     * context.
+     * 
+     * @return The <code>Transaction</code> context for this thread.
+     */
+    public Transaction getTransaction();
+}

=== modified file 'src/test/java/com/persistit/unit/ExchangeTest.java'
--- src/test/java/com/persistit/unit/ExchangeTest.java	2012-10-15 18:08:24 +0000
+++ src/test/java/com/persistit/unit/ExchangeTest.java	2013-01-07 23:12:21 +0000
@@ -216,6 +216,7 @@
         assertEquals(false, ex.traverse(Key.GTEQ, kf, 4));
         assertEquals(false, ex.traverse(Key.LT, kf, 4));
         assertEquals(false, ex.traverse(Key.LTEQ, kf, 4));
+
     }
 
     @Test
@@ -489,7 +490,6 @@
         keyCheck(ex, deep ? "{1,2}" : "{1}");
         assertEquals("Should be true", true, ex.traverse(Key.EQ, deep, 0));
         keyCheck(ex, deep ? "{1,2}" : "{1}");
-
     }
 
     private void keyCheck(final Exchange ex, final String expected) {

=== added file 'src/test/java/com/persistit/unit/TraverseVisitorTest.java'
--- src/test/java/com/persistit/unit/TraverseVisitorTest.java	1970-01-01 00:00:00 +0000
+++ src/test/java/com/persistit/unit/TraverseVisitorTest.java	2013-01-07 23:12:21 +0000
@@ -0,0 +1,166 @@
+/**
+ * Copyright © 2011-2012 Akiban Technologies, Inc.  All rights reserved.
+ * 
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ * 
+ * This program may also be available under different license terms.
+ * For more information, see www.akiban.com or contact [e-mail].
+ * 
+ * Contributors:
+ * Akiban Technologies, Inc.
+ */
+
+package com.persistit.unit;
+
+import static org.junit.Assert.assertEquals;
+
+import java.util.concurrent.atomic.AtomicBoolean;
+import java.util.concurrent.atomic.AtomicInteger;
+
+import org.junit.Test;
+
+import com.persistit.Exchange;
+import com.persistit.Exchange.TraverseVisitor;
+import com.persistit.Key;
+import com.persistit.PersistitUnitTestCase;
+import com.persistit.ReadOnlyExchange;
+import com.persistit.exception.PersistitException;
+
+public class TraverseVisitorTest extends PersistitUnitTestCase {
+
+    private final AtomicInteger visited = new AtomicInteger();
+    private final AtomicInteger visitLimit = new AtomicInteger(Integer.MAX_VALUE);
+    private final AtomicBoolean reverse = new AtomicBoolean();
+
+    @Test
+    public void simpleTraverseVisitor() throws PersistitException {
+        final TraverseVisitor tv = new Exchange.TraverseVisitor() {
+
+            @Override
+            public boolean visit(final ReadOnlyExchange ex) {
+                visited.incrementAndGet();
+                return visited.get() < visitLimit.get();
+            }
+        };
+        doCombo(tv);
+
+    }
+
+    @Test
+    public void traverseVisitorNonMutatingTraverseMethods() throws Exception {
+
+        final TraverseVisitor tv = new Exchange.TraverseVisitor() {
+
+            @Override
+            public boolean visit(final ReadOnlyExchange ex) throws PersistitException {
+                visited.incrementAndGet();
+                final int v = visited.get();
+                return v < visitLimit.get();
+            }
+        };
+
+        doCombo(tv);
+    }
+
+    /**
+     * Demonstrates that a TraverseVisitor can (carefully) modify the Key of a
+     * supplied ReadOnlyExchange.
+     * 
+     * @throws Exception
+     */
+    @Test
+    public void testMutateKey() throws Exception {
+        final TraverseVisitor tv = new Exchange.TraverseVisitor() {
+
+            @Override
+            public boolean visit(final ReadOnlyExchange ex) throws PersistitException {
+                visited.incrementAndGet();
+                final int v = visited.get();
+                if (reverse.get()) {
+                    final int k = ex.getKey().reset().decodeInt();
+                    ex.getKey().clear().append(k - 1).append(0);
+                } else {
+                    ex.getKey().append("a");
+                }
+                return v < visitLimit.get();
+            }
+        };
+
+        doCombo(tv);
+
+    }
+
+    private void doCombo(final TraverseVisitor tv) throws PersistitException {
+        final Exchange ex = _persistit.getExchange("persistit", "gogo", true);
+        final String mockValue = createString(64);
+        for (int i = 0; i < 1000; i++) {
+            ex.clear().append(i);
+            ex.getValue().put(mockValue);
+            ex.store();
+        }
+        final int max = Integer.MAX_VALUE;
+        doTraverse(ex, tv, false, Key.GT, max, 1000);
+        doTraverse(ex, tv, false, Key.GT, max, 1000);
+        doTraverse(ex, tv, false, Key.LT, max, 1000);
+        doTraverse(ex, tv, false, Key.LT, max, 1000);
+        doTraverse(ex, tv, false, Key.GT, 1, 1);
+        doTraverse(ex, tv, false, Key.GT, 1, 1);
+        doTraverse(ex, tv, false, Key.GT, 10, 10);
+        doTraverse(ex, tv, false, Key.GT, 10, 10);
+        doTraverse(ex, tv, false, Key.LT, 1, 1);
+        doTraverse(ex, tv, false, Key.LT, 1, 1);
+        doTraverse(ex, tv, false, Key.LT, 10, 10);
+        doTraverse(ex, tv, false, Key.LT, 10, 10);
+
+        doTraverse(ex, tv, true, Key.GT, max, 1000);
+        doTraverse(ex, tv, true, Key.GT, max, 1000);
+        doTraverse(ex, tv, true, Key.LT, max, 1000);
+        doTraverse(ex, tv, true, Key.LT, max, 1000);
+        doTraverse(ex, tv, true, Key.GT, 1, 1);
+        doTraverse(ex, tv, true, Key.GT, 1, 1);
+        doTraverse(ex, tv, true, Key.GT, 10, 10);
+        doTraverse(ex, tv, true, Key.GT, 10, 10);
+        doTraverse(ex, tv, true, Key.LT, 1, 1);
+        doTraverse(ex, tv, true, Key.LT, 1, 1);
+        doTraverse(ex, tv, true, Key.LT, 10, 10);
+        doTraverse(ex, tv, true, Key.LT, 10, 10);
+
+        doTraverse(ex, tv, false, Key.GTEQ, max, 1000);
+        doTraverse(ex, tv, false, Key.GTEQ, max, 1000);
+        doTraverse(ex, tv, false, Key.LTEQ, max, 1000);
+        doTraverse(ex, tv, false, Key.LTEQ, max, 1000);
+
+        doTraverseFrom(1, ex, tv, false, Key.GT, max, 998);
+        doTraverseFrom(1, ex, tv, false, Key.GTEQ, max, 999);
+        doTraverseFrom(998, ex, tv, false, Key.LT, max, 998);
+        doTraverseFrom(998, ex, tv, false, Key.LTEQ, max, 999);
+
+        doTraverseFrom(500, ex, tv, false, Key.EQ, max, 1);
+        doTraverseFrom(1001, ex, tv, false, Key.EQ, max, 0);
+    }
+
+    private void doTraverse(final Exchange ex, final TraverseVisitor tv, final boolean deep,
+            final Key.Direction direction, final int limit, final int expected) throws PersistitException {
+        ex.clear().append(direction == Key.LT || direction == Key.LTEQ ? Key.AFTER : Key.BEFORE);
+        doTraverse0(ex, tv, deep, direction, limit, expected);
+    }
+
+    private void doTraverseFrom(final int from, final Exchange ex, final TraverseVisitor tv, final boolean deep,
+            final Key.Direction direction, final int limit, final int expected) throws PersistitException {
+        ex.clear().append(from);
+        doTraverse0(ex, tv, deep, direction, limit, expected);
+    }
+
+    private void doTraverse0(final Exchange ex, final TraverseVisitor tv, final boolean deep,
+            final Key.Direction direction, final int limit, final int expected) throws PersistitException {
+        reverse.set(direction == Key.LT || direction == Key.LTEQ);
+        visited.set(0);
+        visitLimit.set(limit);
+        assertEquals(limit < 1000, ex.traverse(direction, deep, Integer.MAX_VALUE, tv));
+        assertEquals(expected, visited.get());
+    }
+
+}