Thread: [Bigdata-commit] SF.net SVN: bigdata:[3356] trunk/bigdata/src

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Revision: 3356
          http://bigdata.svn.sourceforge.net/bigdata/?rev=3356&view=rev
Author:   thompsonbry
Date:     2010-07-29 18:58:37 +0000 (Thu, 29 Jul 2010)

Log Message:
-----------
Bug fix for https://sourceforge.net/apps/trac/bigdata/ticket/128 (IndexSegmentMultiBlockIterator has fence post resulting in thrown exception).

Modified Paths:
--------------
    trunk/bigdata/src/java/com/bigdata/btree/IndexSegment.java
    trunk/bigdata/src/java/com/bigdata/btree/IndexSegmentMultiBlockIterator.java
    trunk/bigdata/src/test/com/bigdata/btree/TestIndexSegmentMultiBlockIterators.java

Modified: trunk/bigdata/src/java/com/bigdata/btree/IndexSegment.java
===================================================================

--- trunk/bigdata/src/java/com/bigdata/btree/IndexSegment.java	2010-07-29 18:48:18 UTC (rev 3355)
+++ trunk/bigdata/src/java/com/bigdata/btree/IndexSegment.java	2010-07-29 18:58:37 UTC (rev 3356)
@@ -623,7 +623,7 @@
      * 
      * @throws IllegalArgumentException
      *             if the <i>key</i> is <code>null</code>.
-     * @throws RUntimeException
+     * @throws RuntimeException
      *             if the key does not lie within the optional key-range
      *             constraints for an index partition.
      */

Modified: trunk/bigdata/src/java/com/bigdata/btree/IndexSegmentMultiBlockIterator.java
===================================================================
--- trunk/bigdata/src/java/com/bigdata/btree/IndexSegmentMultiBlockIterator.java	2010-07-29 18:48:18 UTC (rev 3355)
+++ trunk/bigdata/src/java/com/bigdata/btree/IndexSegmentMultiBlockIterator.java	2010-07-29 18:58:37 UTC (rev 3356)
@@ -151,6 +151,16 @@
      */
     private int blockLength = 0;
 
+    /*
+     * Counters
+     */
+
+    /** The #of leaves read so far. */
+    private long leafReadCount = 0;
+
+    /** The #of blocks read so far. */
+    private long blockReadCount = 0;
+    
     /**
      * 
      * @param seg
@@ -209,11 +219,25 @@
                 : seg.findLeafAddr(toKey));
 
         if (pool.getBufferCapacity() < store.getCheckpoint().maxNodeOrLeafLength) {
+
             /*
-             * Leaves are invariably larger than nodes. If the buffers in the
-             * pool are too small to hold the largest record in the index
-             * segment then you can not use this iterator.
+             * If the buffers in the pool are too small to hold the largest
+             * record in the index segment then you can not use this iterator.
+             * 
+             * Note: We presume that the largest record is therefore a leaf. In
+             * practice this will nearly always be true as nodes have relatively
+             * little metadata per tuple while leaves store the value associated
+             * with the tuple.
+             * 
+             * Note: AbstractBTree checks for this condition before choosing
+             * this iterator.
              */
+            
+            throw new UnsupportedOperationException(
+                    "Record is larger than buffer: maxNodeOrLeafLength="
+                            + store.getCheckpoint().maxNodeOrLeafLength
+                            + ", bufferCapacity=" + pool.getBufferCapacity());
+
         }
         
         if (firstLeafAddr == 0L) {
@@ -345,7 +369,7 @@
             throw new IllegalStateException();
         if (currentLeaf == null) {
             if (log.isTraceEnabled())
-                log.trace("Reading first leaf");
+                log.trace("Reading initial leaf");
             // acquire the buffer from the pool.
             acquireBuffer();
             // Read the first block.
@@ -355,6 +379,12 @@
             // Return the first leaf.
             return leaf;
         }
+        if (currentLeaf.identity == lastLeafAddr) {
+            // No more leaves.
+            if (log.isTraceEnabled())
+                log.trace("No more leaves (end of key range)");
+            return null;
+        }
         /*
          * We need to return the next leaf. We get the address of the next leaf
          * from the nextAddr field of the current leaf.
@@ -363,7 +393,7 @@
         if (nextLeafAddr == 0L) {
             // No more leaves.
             if (log.isTraceEnabled())
-                log.trace("No more leaves");
+                log.trace("No more leaves (end of segment)");
             return null;
         }
         /*
@@ -411,20 +441,25 @@
             throw new IllegalArgumentException();
         
         // offset into the buffer.
-        final int toff = (int)(offset - blockOffset);
+        final int offsetWithinBuffer = (int)(offset - blockOffset);
 
-        if (log.isTraceEnabled())
-            log.trace("addr=" + addr + "(" + store.toString(addr)
-                    + "), blockOffset=" + blockOffset+" toff="+toff);
-        
         // read only view of the leaf in the buffer.
         final ByteBuffer tmp = buffer.asReadOnlyBuffer();
-        tmp.limit(toff + nbytes);
-        tmp.position(toff);
+        tmp.limit(offsetWithinBuffer + nbytes);
+        tmp.position(offsetWithinBuffer);
 
         // decode byte[] as ILeafData.
         final ILeafData data = (ILeafData) seg.nodeSer.decode(tmp);
-        
+
+        leafReadCount++;
+
+        if (log.isTraceEnabled())
+            log
+                    .trace("read leaf: leafReadCount=" + leafReadCount
+                            + ", addr=" + addr + "(" + store.toString(addr)
+                            + "), blockOffset=" + blockOffset
+                            + " offsetWithinBuffer=" + offsetWithinBuffer);
+
         // return as Leaf.
         return new ImmutableLeaf(seg, addr, data);
         
@@ -470,6 +505,14 @@
         // the #of bytes that we will actually read.
         final int nbytes = (int) Math.min(lastOffset - startOffset, b
                 .capacity());
+        if(log.isTraceEnabled())
+            log.trace("leafAddr=" + store.toString(leafAddr) + ", startOffset="
+                    + startOffset + ", lastOffset=" + lastOffset + ", nbytes="
+                    + nbytes);
+        if (nbytes == 0) {
+            throw new AssertionError("nbytes=0 : leafAddr"
+                    + store.toString(leafAddr) + " : " + this);
+        }
         // set the position to zero.
         b.position(0);
         // set the limit to the #of bytes to be read.
@@ -483,9 +526,29 @@
         // update the offset/length in the store for the in memory block
         blockOffset = startOffset;
         blockLength = nbytes;
+        blockReadCount++;
         if (log.isTraceEnabled())
-            log.trace("leafAddr=" + leafAddr + ", blockOffset=" + blockOffset
-                    + ", blockLength=" + blockLength);
+            log.trace("read block: blockReadCount=" + blockReadCount
+                    + ", leafAddr=" + store.toString(leafAddr)
+                    + ", blockOffset=" + blockOffset + ", blockLength="
+                    + blockLength);
     }
 
+    public String toString() {
+        return super.toString() + //
+                "{file=" + store.getFile() + //
+                ",checkpoint="+store.getCheckpoint()+//
+                ",fromKey="+BytesUtil.toString(fromKey)+//
+                ",toKey="+BytesUtil.toString(toKey)+//
+                ",firstLeafAddr=" + store.toString(firstLeafAddr) + //
+                ",lastLeafAddr=" + store.toString(lastLeafAddr) + //
+                ",currentLeaf=" + (currentLeaf!=null?store.toString(currentLeaf.identity):"N/A") + //
+                ",blockOffset="+blockOffset+//
+                ",blockLength="+blockLength+//
+                ",bufferCapacity="+pool.getBufferCapacity()+//
+                ",leafReadCount="+leafReadCount+//
+                ",blockReadCount="+blockReadCount+//
+                "}";
+        }
+
 }

Modified: trunk/bigdata/src/test/com/bigdata/btree/TestIndexSegmentMultiBlockIterators.java
===================================================================
--- trunk/bigdata/src/test/com/bigdata/btree/TestIndexSegmentMultiBlockIterators.java	2010-07-29 18:48:18 UTC (rev 3355)
+++ trunk/bigdata/src/test/com/bigdata/btree/TestIndexSegmentMultiBlockIterators.java	2010-07-29 18:58:37 UTC (rev 3356)
@@ -28,6 +28,7 @@
 package com.bigdata.btree;
 
 import java.io.File;
+import java.util.Random;
 import java.util.UUID;
 
 import com.bigdata.btree.IndexSegmentBuilder.BuildEnum;
@@ -271,6 +272,8 @@
             // verify that the iterator is exhausted.
             assertFalse(itr.hasNext());
             
+            doRandomScanTest(btree, seg, 10/* ntests */);
+            
         } finally {
 
             seg.getStore().destroy();
@@ -280,6 +283,43 @@
     }
 
     /**
+     * Unit test builds an empty index segment and then verifies the behavior of
+     * the {@link IndexSegmentMultiBlockIterator}.
+     * 
+     * @throws Exception 
+     */
+    public void test_emptyIndexSegment() throws Exception {
+
+        final BTree btree = BTree.createTransient(new IndexMetadata(UUID
+                .randomUUID()));
+
+        final IndexSegmentBuilder builder = TestIndexSegmentBuilderWithLargeTrees
+                .doBuildIndexSegment(getName(), btree, 32/* m */,
+                        BuildEnum.TwoPass, bufferNodes);
+
+        final IndexSegment seg = new IndexSegmentStore(builder.outFile)
+                .loadIndexSegment();
+
+        try {
+
+            final IndexSegmentMultiBlockIterator<?> itr = new IndexSegmentMultiBlockIterator(
+                    seg, DirectBufferPool.INSTANCE_10M, null/* fromKey */,
+                    null/* toKey */, IRangeQuery.DEFAULT);
+
+            assertFalse(itr.hasNext());
+            
+            // verify the data.
+            testMultiBlockIterator(btree, seg);
+            
+        } finally {
+
+            seg.getStore().destroy();
+
+        }
+
+    }
+    
+    /**
      * Test build around an {@link IndexSegment} having a default branching
      * factor and a bunch of leaves totally more than 1M in size on the disk.
      */
@@ -288,8 +328,13 @@
         final BTree btree = BTree.createTransient(new IndexMetadata(UUID
                 .randomUUID()));
 
-        for (int i = 0; i < 1000000; i++) {
+        final int LIMIT = 1000000;
+
+        // populate the index.
+        for (int i = 0; i < LIMIT; i++) {
+
             btree.insert(i, i);
+            
         }
 
         final IndexSegmentBuilder builder = TestIndexSegmentBuilderWithLargeTrees
@@ -336,6 +381,9 @@
 
             // verify the data.
             testMultiBlockIterator(btree, seg);
+
+            // random iterator scan tests.
+            doRandomScanTest(btree, seg, 1000/* ntests */);
             
         } finally {
 
@@ -345,4 +393,112 @@
 
     }
 
+    /**
+     * Do a bunch of random iterator scans. Each scan will start at a random key
+     * and run to a random key.
+     * 
+     * @param groundTruth
+     *            The ground truth B+Tree.
+     * @param actual
+     *            The index segment built from that B+Tree.
+     * @param ntests
+     *            The #of scans to run.
+     */
+    private void doRandomScanTest(final BTree groundTruth,
+            final IndexSegment actual, final int ntests) {
+
+        final Random r = new Random();
+        
+        final int n = groundTruth.getEntryCount();
+
+        // point query beyond the last tuple in the index segment.
+        {
+            
+            final int fromIndex = n - 1;
+
+            final byte[] fromKey = groundTruth.keyAt(fromIndex);
+
+            final byte[] toKey = BytesUtil.successor(fromKey.clone());
+
+            final ITupleIterator<?> expectedItr = groundTruth
+                    .rangeIterator(fromKey, toKey, 0/* capacity */,
+                            IRangeQuery.DEFAULT, null/* filter */);
+
+            final IndexSegmentMultiBlockIterator<?> actualItr = new IndexSegmentMultiBlockIterator(
+                    actual, DirectBufferPool.INSTANCE_10M, fromKey, toKey,
+                    IRangeQuery.DEFAULT);
+            
+            assertSameEntryIterator(expectedItr, actualItr);
+
+        }
+        
+        // random point queries.
+        for (int i = 0; i < ntests; i++) {
+
+            final int fromIndex = r.nextInt(n);
+
+            final byte[] fromKey = groundTruth.keyAt(fromIndex);
+
+            final byte[] toKey = BytesUtil.successor(fromKey.clone());
+
+            final ITupleIterator<?> expectedItr = groundTruth
+                    .rangeIterator(fromKey, toKey, 0/* capacity */,
+                            IRangeQuery.DEFAULT, null/* filter */);
+
+            final IndexSegmentMultiBlockIterator<?> actualItr = new IndexSegmentMultiBlockIterator(
+                    actual, DirectBufferPool.INSTANCE_10M, fromKey, toKey,
+                    IRangeQuery.DEFAULT);
+            
+            assertSameEntryIterator(expectedItr, actualItr);
+
+        }
+        
+        // random range queries with small range of spanned keys (0 to 10).
+        for (int i = 0; i < ntests; i++) {
+
+            final int fromIndex = r.nextInt(n);
+
+            final byte[] fromKey = groundTruth.keyAt(fromIndex);
+
+            final byte[] toKey = groundTruth.keyAt(Math.min(fromIndex
+                    + r.nextInt(10), n - 1));
+
+            final ITupleIterator<?> expectedItr = groundTruth
+                    .rangeIterator(fromKey, toKey, 0/* capacity */,
+                            IRangeQuery.DEFAULT, null/* filter */);
+
+            final IndexSegmentMultiBlockIterator<?> actualItr = new IndexSegmentMultiBlockIterator(
+                    actual, DirectBufferPool.INSTANCE_10M, fromKey, toKey,
+                    IRangeQuery.DEFAULT);
+
+            assertSameEntryIterator(expectedItr, actualItr);
+
+        }
+
+        // random range queries with random #of spanned keys.
+        for (int i = 0; i < ntests; i++) {
+
+            final int fromIndex = r.nextInt(n);
+
+            final int toIndex = fromIndex + r.nextInt(n - fromIndex + 1);
+
+            final byte[] fromKey = groundTruth.keyAt(fromIndex);
+
+            final byte[] toKey = toIndex >= n ? null : groundTruth
+                    .keyAt(toIndex);
+
+            final ITupleIterator<?> expectedItr = groundTruth
+                    .rangeIterator(fromKey, toKey, 0/* capacity */,
+                            IRangeQuery.DEFAULT, null/* filter */);
+
+            final IndexSegmentMultiBlockIterator<?> actualItr = new IndexSegmentMultiBlockIterator(
+                    actual, DirectBufferPool.INSTANCE_10M, fromKey, toKey,
+                    IRangeQuery.DEFAULT);
+
+            assertSameEntryIterator(expectedItr, actualItr);
+
+        }
+
+    }
+
 }


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.




Thread: [Bigdata-commit] SF.net SVN: bigdata:[3356] trunk/bigdata/src

Fast, scalable, robust graph database platform

bigdata-commit