Fixed the following bug:
1) Insert to the tree tuple A.
2) Flushed tuple A.
3) Delete tuple A (still in the in-memory btree).
4) Insert tuple A, which will cause the tuple A in the in-memory btree to be deleted.
5) Tuple A will be inserted in the in-memory tree.
Thus, searchers will see 2 copies of tuple A.
The bug is fixed now by skipping the second insertion.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_rtree_bulkload@1442 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
index 9e932f9..4b30092 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
@@ -88,7 +88,7 @@
}
private final LSMHarness lsmHarness;
-
+
private final ILinearizeComparatorFactory linearizer;
// In-memory components.
@@ -234,9 +234,9 @@
return diskTree;
}
- @Deprecated
- private ITreeIndexBulkLoader bulkloader;
-
+ @Deprecated
+ private ITreeIndexBulkLoader bulkloader;
+
@Override
public IIndexBulkLoadContext beginBulkLoad(float fillFactor) throws TreeIndexException, HyracksDataException {
bulkloader = createBulkLoader(fillFactor);
@@ -323,9 +323,10 @@
// index and a tuple shouldn't be deleted twice without
// insert between them.
}
+ } else {
+ ctx.memRTreeAccessor.insert(tuple);
+ memRTreeTuples++;
}
- ctx.memRTreeAccessor.insert(tuple);
- memRTreeTuples++;
} else {
// For each delete operation, we make sure that we run a true
@@ -398,32 +399,33 @@
ITreeIndexBulkLoader rTreeBulkloader;
ITreeIndexCursor cursor;
- if(!(linearizer instanceof NullLinearizeComparatorFactory)) {
- IBinaryComparatorFactory[] linearizerArray = {linearizer};
-
- if (rTreeTupleSorter == null) {
- rTreeTupleSorter = new RTreeTupleSorter(memRTreeTuples, MEM_RTREE_FILE_ID, linearizerArray,
- rtreeLeafFrameFactory.createFrame(), rtreeLeafFrameFactory.createFrame(), memComponent.getRTree()
- .getBufferCache());
- } else {
- rTreeTupleSorter.reset();
- }
- // BulkLoad the tuples from the in-memory tree into the new disk RTree.
-
- try {
- while (rtreeScanCursor.hasNext()) {
- rtreeScanCursor.next();
- rTreeTupleSorter.insertTupleEntry(rtreeScanCursor.getPageId(), rtreeScanCursor.getTupleOffset());
- }
- } finally {
- rtreeScanCursor.close();
- }
- rTreeTupleSorter.sort();
- rTreeBulkloader = diskRTree.createBulkLoader(1.0f);
- cursor = rTreeTupleSorter;
+ if (!(linearizer instanceof NullLinearizeComparatorFactory)) {
+ IBinaryComparatorFactory[] linearizerArray = { linearizer };
+
+ if (rTreeTupleSorter == null) {
+ rTreeTupleSorter = new RTreeTupleSorter(memRTreeTuples, MEM_RTREE_FILE_ID, linearizerArray,
+ rtreeLeafFrameFactory.createFrame(), rtreeLeafFrameFactory.createFrame(), memComponent
+ .getRTree().getBufferCache());
+ } else {
+ rTreeTupleSorter.reset();
+ }
+ // BulkLoad the tuples from the in-memory tree into the new disk
+ // RTree.
+
+ try {
+ while (rtreeScanCursor.hasNext()) {
+ rtreeScanCursor.next();
+ rTreeTupleSorter.insertTupleEntry(rtreeScanCursor.getPageId(), rtreeScanCursor.getTupleOffset());
+ }
+ } finally {
+ rtreeScanCursor.close();
+ }
+ rTreeTupleSorter.sort();
+ rTreeBulkloader = diskRTree.createBulkLoader(1.0f);
+ cursor = rTreeTupleSorter;
} else {
- rTreeBulkloader = diskRTree.createInsertBulkLoader();
- cursor = rtreeScanCursor;
+ rTreeBulkloader = diskRTree.createInsertBulkLoader();
+ cursor = rtreeScanCursor;
}
try {
@@ -436,7 +438,7 @@
cursor.close();
}
rTreeBulkloader.end();
-
+
// scan the memory BTree
ITreeIndexAccessor memBTreeAccessor = memComponent.getBTree().createAccessor();
IIndexCursor btreeScanCursor = memBTreeAccessor.createSearchCursor();
@@ -468,7 +470,7 @@
IIndexOpContext ctx = createOpContext();
ITreeIndexCursor cursor;
- cursor = new LSMRTreeSortedCursor(linearizer);
+ cursor = new LSMRTreeSortedCursor(linearizer);
ISearchPredicate rtreeSearchPred = new SearchPredicate(null, null);
// Scan the RTrees, ignoring the in-memory RTree.
List<Object> mergingComponents = lsmHarness.search(cursor, rtreeSearchPred, ctx, false);
@@ -487,8 +489,8 @@
RTree mergedRTree = (RTree) createDiskTree(diskRTreeFactory, rtreeFile, true);
BTree mergedBTree = (BTree) createDiskTree(diskBTreeFactory, btreeFile, true);
- ITreeIndexBulkLoader bulkloader = (!(linearizer instanceof NullLinearizeComparatorFactory) ?
- mergedRTree.createBulkLoader(1.0f) : mergedRTree.createInsertBulkLoader());
+ ITreeIndexBulkLoader bulkloader = (!(linearizer instanceof NullLinearizeComparatorFactory) ? mergedRTree
+ .createBulkLoader(1.0f) : mergedRTree.createInsertBulkLoader());
try {
while (cursor.hasNext()) {
cursor.next();
@@ -599,48 +601,48 @@
public ILSMComponentFinalizer getComponentFinalizer() {
return componentFinalizer;
}
-
- @Override
- public ITreeIndexBulkLoader createBulkLoader(float fillLevel)
- throws TreeIndexException {
- return new LSMRTreeBulkLoader(fillLevel);
- }
-
- public class LSMRTreeBulkLoader implements ITreeIndexBulkLoader {
- private final RTree diskRTree;
- private final BTree diskBTree;
- private final RTreeBulkLoader bulkLoader;
- public LSMRTreeBulkLoader(float fillFactor) throws TreeIndexException {
- // Note that by using a flush target file name, we state that the new
- // bulk loaded tree is "newer" than any other merged tree.
- try {
- LSMRTreeFileNameComponent fileNames = (LSMRTreeFileNameComponent) fileManager.getRelFlushFileName();
- FileReference rtreeFile = fileManager.createFlushFile(fileNames.getRTreeFileName());
- diskRTree = (RTree) createDiskTree(diskRTreeFactory, rtreeFile, true);
- // For each RTree, we require to have a buddy BTree. thus, we create an
- // empty BTree.
- FileReference btreeFile = fileManager.createFlushFile(fileNames.getBTreeFileName());
- diskBTree = (BTree) createDiskTree(diskBTreeFactory, btreeFile, true);
- } catch (HyracksDataException e) {
- throw new TreeIndexException(e);
- }
-
-
- bulkLoader = (RTreeBulkLoader) diskRTree.createBulkLoader(fillFactor);
- }
+ @Override
+ public ITreeIndexBulkLoader createBulkLoader(float fillLevel) throws TreeIndexException {
+ return new LSMRTreeBulkLoader(fillLevel);
+ }
- @Override
- public void add(ITupleReference tuple) throws HyracksDataException {
- bulkLoader.add(tuple);
- }
+ public class LSMRTreeBulkLoader implements ITreeIndexBulkLoader {
+ private final RTree diskRTree;
+ private final BTree diskBTree;
+ private final RTreeBulkLoader bulkLoader;
- @Override
- public void end() throws HyracksDataException {
- bulkLoader.end();
- LSMRTreeComponent diskComponent = new LSMRTreeComponent(diskRTree, diskBTree);
- lsmHarness.addBulkLoadedComponent(diskComponent);
- }
-
- }
+ public LSMRTreeBulkLoader(float fillFactor) throws TreeIndexException {
+ // Note that by using a flush target file name, we state that the
+ // new
+ // bulk loaded tree is "newer" than any other merged tree.
+ try {
+ LSMRTreeFileNameComponent fileNames = (LSMRTreeFileNameComponent) fileManager.getRelFlushFileName();
+ FileReference rtreeFile = fileManager.createFlushFile(fileNames.getRTreeFileName());
+ diskRTree = (RTree) createDiskTree(diskRTreeFactory, rtreeFile, true);
+ // For each RTree, we require to have a buddy BTree. thus, we
+ // create an
+ // empty BTree.
+ FileReference btreeFile = fileManager.createFlushFile(fileNames.getBTreeFileName());
+ diskBTree = (BTree) createDiskTree(diskBTreeFactory, btreeFile, true);
+ } catch (HyracksDataException e) {
+ throw new TreeIndexException(e);
+ }
+
+ bulkLoader = (RTreeBulkLoader) diskRTree.createBulkLoader(fillFactor);
+ }
+
+ @Override
+ public void add(ITupleReference tuple) throws HyracksDataException {
+ bulkLoader.add(tuple);
+ }
+
+ @Override
+ public void end() throws HyracksDataException {
+ bulkLoader.end();
+ LSMRTreeComponent diskComponent = new LSMRTreeComponent(diskRTree, diskBTree);
+ lsmHarness.addBulkLoadedComponent(diskComponent);
+ }
+
+ }
}
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java
index 7c549d7..5a5b2c3 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java
@@ -29,7 +29,6 @@
import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
-import edu.uci.ics.hyracks.storage.am.linearize.HilbertDoubleComparatorFactory;
import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileManager;
import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryBufferCache;
import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryFreePageManager;
@@ -40,6 +39,7 @@
import edu.uci.ics.hyracks.storage.am.lsm.rtree.tuples.LSMTypeAwareTupleWriterFactory;
import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.linearize.HilbertDoubleComparatorFactory;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java
index 6efa620..f2f52e1 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java
@@ -23,21 +23,9 @@
import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeInsertTest;
-import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeTestContext;
import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestContext;
import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
-/**
- * Tests the BTree insert operation with strings and integer fields using
- * various numbers of key and payload fields.
- *
- * Each tests first fills a BTree with randomly generated tuples. We compare the
- * following operations against expected results: 1. Point searches for all
- * tuples. 2. Ordered scan. 3. Disk-order scan. 4. Range search (and prefix
- * search for composite keys).
- *
- */
@SuppressWarnings("rawtypes")
public class RTreeInsertTest extends AbstractRTreeInsertTest {