- Fixed a bug in the LSMRTree search cursor which caused returning corrputed tuples.
- Fixed a rare bug in the unordered slot manager when a page has not tuples.
- Fixed a bug that caused the printTree method to not work properly.
- Minor bug fixes and code cleaning.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@1109 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 68a8da4..930fc80 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
@@ -55,29 +55,29 @@
import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
public class LSMRTree implements ILSMTree {
-
- public class LSMRTreeComponent {
- private final RTree rtree;
- private final BTree btree;
-
- LSMRTreeComponent (RTree rtree, BTree btree) {
- this.rtree = rtree;
- this.btree = btree;
- }
-
- public RTree getRTree() {
- return rtree;
- }
-
- public BTree getBTree() {
- return btree;
- }
- }
-
- private final LSMHarness lsmHarness;
-
+
+ public class LSMRTreeComponent {
+ private final RTree rtree;
+ private final BTree btree;
+
+ LSMRTreeComponent(RTree rtree, BTree btree) {
+ this.rtree = rtree;
+ this.btree = btree;
+ }
+
+ public RTree getRTree() {
+ return rtree;
+ }
+
+ public BTree getBTree() {
+ return btree;
+ }
+ }
+
+ private final LSMHarness lsmHarness;
+
// In-memory components.
- private final LSMRTreeComponent memComponent;
+ private final LSMRTreeComponent memComponent;
protected final InMemoryFreePageManager memFreePageManager;
private final static int MEM_RTREE_FILE_ID = 0;
private final static int MEM_BTREE_FILE_ID = 1;
@@ -90,12 +90,13 @@
private final RTreeFactory diskRTreeFactory;
// For creating BTree's used in flush and merge.
private final BTreeFactory diskBTreeFactory;
- // List of LSMRTreeComponent instances. Using Object for better sharing via ILSMTree + LSMHarness.
+ // List of LSMRTreeComponent instances. Using Object for better sharing via
+ // ILSMTree + LSMHarness.
private final LinkedList<Object> diskComponents = new LinkedList<Object>();
private IBinaryComparatorFactory[] btreeCmpFactories;
private IBinaryComparatorFactory[] rtreeCmpFactories;
-
+
// Common for in-memory and on-disk components.
private final ITreeIndexFrameFactory rtreeInteriorFrameFactory;
private final ITreeIndexFrameFactory btreeInteriorFrameFactory;
@@ -106,11 +107,12 @@
ITreeIndexFrameFactory rtreeInteriorFrameFactory, ITreeIndexFrameFactory rtreeLeafFrameFactory,
ITreeIndexFrameFactory btreeInteriorFrameFactory, ITreeIndexFrameFactory btreeLeafFrameFactory,
ILSMFileNameManager fileNameManager, RTreeFactory diskRTreeFactory, BTreeFactory diskBTreeFactory,
- IFileMapProvider diskFileMapProvider, int fieldCount, IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories) {
- RTree memRTree = new RTree(memBufferCache, fieldCount, rtreeCmpFactories, memFreePageManager, rtreeInteriorFrameFactory,
- rtreeLeafFrameFactory);
- BTree memBTree = new BTree(memBufferCache, fieldCount, btreeCmpFactories, memFreePageManager, btreeInteriorFrameFactory,
- btreeLeafFrameFactory);
+ IFileMapProvider diskFileMapProvider, int fieldCount, IBinaryComparatorFactory[] rtreeCmpFactories,
+ IBinaryComparatorFactory[] btreeCmpFactories) {
+ RTree memRTree = new RTree(memBufferCache, fieldCount, rtreeCmpFactories, memFreePageManager,
+ rtreeInteriorFrameFactory, rtreeLeafFrameFactory);
+ BTree memBTree = new BTree(memBufferCache, fieldCount, btreeCmpFactories, memFreePageManager,
+ btreeInteriorFrameFactory, btreeLeafFrameFactory);
memComponent = new LSMRTreeComponent(memRTree, memBTree);
this.memFreePageManager = memFreePageManager;
this.diskBufferCache = diskBTreeFactory.getBufferCache();
@@ -129,8 +131,8 @@
@Override
public void create(int indexFileId) throws HyracksDataException {
- memComponent.getRTree().create(MEM_RTREE_FILE_ID);
- memComponent.getBTree().create(MEM_BTREE_FILE_ID);
+ memComponent.getRTree().create(MEM_RTREE_FILE_ID);
+ memComponent.getBTree().create(MEM_BTREE_FILE_ID);
}
/**
@@ -151,8 +153,8 @@
*/
@Override
public void open(int indexFileId) throws HyracksDataException {
- memComponent.getRTree().open(MEM_RTREE_FILE_ID);
- memComponent.getBTree().open(MEM_BTREE_FILE_ID);
+ memComponent.getRTree().open(MEM_RTREE_FILE_ID);
+ memComponent.getBTree().open(MEM_BTREE_FILE_ID);
File dir = new File(fileNameManager.getBaseDir());
FilenameFilter rtreeFilter = new FilenameFilter() {
public boolean accept(File dir, String name) {
@@ -175,12 +177,12 @@
Comparator<String> fileNameCmp = fileNameManager.getFileNameComparator();
Arrays.sort(rtreeFiles, fileNameCmp);
Arrays.sort(btreeFiles, fileNameCmp);
- // Assert rtreeFiles.size() == btreeFiles.size()
+ // Assert rtreeFiles.size() == btreeFiles.size()
for (int i = 0; i < rtreeFiles.length; i++) {
- RTree rtree = (RTree) createDiskTree(diskRTreeFactory, rtreeFiles[i], false);
- BTree btree = (BTree) createDiskTree(diskBTreeFactory, btreeFiles[i], false);
- LSMRTreeComponent diskComponent = new LSMRTreeComponent(rtree, btree);
- diskComponents.add(diskComponent);
+ RTree rtree = (RTree) createDiskTree(diskRTreeFactory, rtreeFiles[i], false);
+ BTree btree = (BTree) createDiskTree(diskBTreeFactory, btreeFiles[i], false);
+ LSMRTreeComponent diskComponent = new LSMRTreeComponent(rtree, btree);
+ diskComponents.add(diskComponent);
}
}
@@ -219,7 +221,7 @@
diskTree.open(diskTreeFileId);
return diskTree;
}
-
+
@Override
public IIndexBulkLoadContext beginBulkLoad(float fillFactor) throws TreeIndexException, HyracksDataException {
// Note that by using a flush target file name, we state that the new
@@ -300,14 +302,12 @@
IIndexOpContext ictx, boolean includeMemComponent) throws HyracksDataException, TreeIndexException {
LSMRTreeOpContext ctx = (LSMRTreeOpContext) ictx;
int numDiskTrees = diskComponents.size();
- ITreeIndexAccessor[] bTreeAccessors;
+ int numTrees = (includeMemComponent) ? numDiskTrees + 1 : numDiskTrees;
+ ITreeIndexAccessor[] bTreeAccessors = new ITreeIndexAccessor[numTrees];
int diskBTreeIx = 0;
if (includeMemComponent) {
- bTreeAccessors = new ITreeIndexAccessor[numDiskTrees + 1];
bTreeAccessors[0] = ctx.memBTreeAccessor;
diskBTreeIx++;
- } else {
- bTreeAccessors = new ITreeIndexAccessor[numDiskTrees];
}
ListIterator<Object> diskBTreesIter = diskComponents.listIterator();
@@ -319,12 +319,12 @@
}
LSMRTreeSearchCursor lsmRTreeCursor = (LSMRTreeSearchCursor) cursor;
- LSMRTreeCursorInitialState initialState = new LSMRTreeCursorInitialState(numDiskTrees + 1,
- rtreeLeafFrameFactory, rtreeInteriorFrameFactory, btreeLeafFrameFactory, ctx.getBTreeMultiComparator(), bTreeAccessors,
+ LSMRTreeCursorInitialState initialState = new LSMRTreeCursorInitialState(numTrees, rtreeLeafFrameFactory,
+ rtreeInteriorFrameFactory, btreeLeafFrameFactory, ctx.getBTreeMultiComparator(), bTreeAccessors,
includeMemComponent, lsmHarness);
lsmRTreeCursor.open(initialState, pred);
- int cursorIx = 1;
+ int cursorIx;
if (includeMemComponent) {
ctx.memRTreeAccessor.search(((LSMRTreeSearchCursor) lsmRTreeCursor).getCursor(0), pred);
cursorIx = 1;
@@ -430,10 +430,10 @@
}
@Override
- public void cleanUpAfterMerge(List<Object> mergedComponents) throws HyracksDataException {
+ public void cleanUpAfterMerge(List<Object> mergedComponents) throws HyracksDataException {
for (Object o : mergedComponents) {
LSMRTreeComponent component = (LSMRTreeComponent) o;
- BTree oldBTree = component.getBTree();
+ BTree oldBTree = component.getBTree();
FileReference btreeFileRef = diskFileMapProvider.lookupFileName(oldBTree.getFileId());
diskBufferCache.closeFile(oldBTree.getFileId());
oldBTree.close();
@@ -458,7 +458,7 @@
@Override
public void resetInMemoryComponent() throws HyracksDataException {
- memComponent.getRTree().create(MEM_RTREE_FILE_ID);
+ memComponent.getRTree().create(MEM_RTREE_FILE_ID);
memComponent.getBTree().create(MEM_BTREE_FILE_ID);
memFreePageManager.reset();
}
@@ -467,21 +467,21 @@
public List<Object> getDiskComponents() {
return diskComponents;
}
-
+
protected LSMRTreeOpContext createOpContext() {
return new LSMRTreeOpContext((RTree.RTreeAccessor) memComponent.getRTree().createAccessor(),
(IRTreeLeafFrame) rtreeLeafFrameFactory.createFrame(),
(IRTreeInteriorFrame) rtreeInteriorFrameFactory.createFrame(), memFreePageManager
- .getMetaDataFrameFactory().createFrame(), 8, (BTree.BTreeAccessor) memComponent.getBTree().createAccessor(),
- btreeLeafFrameFactory, btreeInteriorFrameFactory, memFreePageManager.getMetaDataFrameFactory()
- .createFrame(), rtreeCmpFactories, btreeCmpFactories);
+ .getMetaDataFrameFactory().createFrame(), 8, (BTree.BTreeAccessor) memComponent.getBTree()
+ .createAccessor(), btreeLeafFrameFactory, btreeInteriorFrameFactory, memFreePageManager
+ .getMetaDataFrameFactory().createFrame(), rtreeCmpFactories, btreeCmpFactories);
}
-
+
@Override
public ITreeIndexAccessor createAccessor() {
return new LSMRTreeAccessor(lsmHarness, createOpContext());
}
-
+
private class LSMRTreeAccessor extends LSMTreeIndexAccessor {
public LSMRTreeAccessor(LSMHarness lsmHarness, IIndexOpContext ctx) {
super(lsmHarness, ctx);
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
index 9fd47e9..9804f0c 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
@@ -45,6 +45,7 @@
private ITupleReference frameTuple;
private boolean includeMemRTree;
private LSMHarness lsmHarness;
+ private boolean foundNext = false;
public LSMRTreeSearchCursor() {
currentCursror = 0;
@@ -61,44 +62,44 @@
@Override
public boolean hasNext() throws HyracksDataException {
- for (int i = currentCursror; i < numberOfTrees; i++) {
- while (rtreeCursors[i].hasNext()) {
- rtreeCursors[i].next();
- ITupleReference currentTuple = rtreeCursors[i].getTuple();
+ if (foundNext) {
+ return true;
+ }
+ while (currentCursror < numberOfTrees) {
+ while (rtreeCursors[currentCursror].hasNext()) {
+ rtreeCursors[currentCursror].next();
+ ITupleReference currentTuple = rtreeCursors[currentCursror].getTuple();
+
boolean killerTupleFound = false;
- for (int j = 0; j <= i; j++) {
+ for (int i = 0; i <= currentCursror; i++) {
btreeRangePredicate.setHighKey(currentTuple, true);
btreeRangePredicate.setLowKey(currentTuple, true);
try {
- diskBTreeAccessors[j].search(btreeCursors[j], btreeRangePredicate);
+ diskBTreeAccessors[i].search(btreeCursors[i], btreeRangePredicate);
} catch (TreeIndexException e) {
throw new HyracksDataException(e);
}
- if (btreeCursors[j].hasNext()) {
+ if (btreeCursors[i].hasNext()) {
killerTupleFound = true;
break;
}
}
if (!killerTupleFound) {
frameTuple = currentTuple;
+ foundNext = true;
return true;
}
}
+ currentCursror++;
}
return false;
}
@Override
public void next() throws HyracksDataException {
- while (true) {
- if (currentCursror < numberOfTrees || rtreeCursors[currentCursror].hasNext()) {
- break;
- } else {
- currentCursror++;
- }
- }
+ foundNext = false;
}
@Override
@@ -133,14 +134,14 @@
@Override
public void close() throws HyracksDataException {
try {
- for (int i = 0; i < numberOfTrees; i++) {
- rtreeCursors[i].close();
- btreeCursors[i].close();
- }
- rtreeCursors = null;
- btreeCursors = null;
+ for (int i = 0; i < numberOfTrees; i++) {
+ rtreeCursors[i].close();
+ btreeCursors[i].close();
+ }
+ rtreeCursors = null;
+ btreeCursors = null;
} finally {
- lsmHarness.closeSearchCursor(includeMemRTree);
+ lsmHarness.closeSearchCursor(includeMemRTree);
}
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
index ea2ecb1..ea597ec 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
@@ -15,10 +15,7 @@
package edu.uci.ics.hyracks.storage.am.rtree.frames;
-import java.util.ArrayList;
-
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProvider;
import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
@@ -31,183 +28,151 @@
import edu.uci.ics.hyracks.storage.am.rtree.impls.UnorderedSlotManager;
import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriter;
-public abstract class RTreeNSMFrame extends TreeIndexNSMFrame implements
- IRTreeFrame {
- protected static final int pageNsnOff = smFlagOff + 1;
- protected static final int rightPageOff = pageNsnOff + 8;
+public abstract class RTreeNSMFrame extends TreeIndexNSMFrame implements IRTreeFrame {
+ protected static final int pageNsnOff = smFlagOff + 1;
+ protected static final int rightPageOff = pageNsnOff + 8;
- protected ITreeIndexTupleReference[] tuples;
- protected ITreeIndexTupleReference cmpFrameTuple;
- protected TupleEntryArrayList tupleEntries1; // used for split and checking
- // enlargement
- protected TupleEntryArrayList tupleEntries2; // used for split
+ protected ITreeIndexTupleReference[] tuples;
+ protected ITreeIndexTupleReference cmpFrameTuple;
+ protected TupleEntryArrayList tupleEntries1; // used for split and checking
+ // enlargement
+ protected TupleEntryArrayList tupleEntries2; // used for split
- protected Rectangle[] rec;
+ protected Rectangle[] rec;
- protected static final double splitFactor = 0.4;
- protected static final int nearMinimumOverlapFactor = 32;
- private static final double doubleEpsilon = computeDoubleEpsilon();
- private static final int numTuplesEntries = 100;
- protected final IPrimitiveValueProvider[] keyValueProviders;
-
- public RTreeNSMFrame(ITreeIndexTupleWriter tupleWriter, IPrimitiveValueProvider[] keyValueProviders) {
- super(tupleWriter, new UnorderedSlotManager());
- this.tuples = new ITreeIndexTupleReference[keyValueProviders.length];
- for (int i = 0; i < keyValueProviders.length; i++) {
- this.tuples[i] = tupleWriter.createTupleReference();
- }
- cmpFrameTuple = tupleWriter.createTupleReference();
+ protected static final double splitFactor = 0.4;
+ protected static final int nearMinimumOverlapFactor = 32;
+ private static final double doubleEpsilon = computeDoubleEpsilon();
+ private static final int numTuplesEntries = 100;
+ protected final IPrimitiveValueProvider[] keyValueProviders;
- tupleEntries1 = new TupleEntryArrayList(numTuplesEntries,
- numTuplesEntries);
- tupleEntries2 = new TupleEntryArrayList(numTuplesEntries,
- numTuplesEntries);
- rec = new Rectangle[4];
- for (int i = 0; i < 4; i++) {
- rec[i] = new Rectangle(keyValueProviders.length / 2);
- }
- this.keyValueProviders = keyValueProviders;
- }
+ public RTreeNSMFrame(ITreeIndexTupleWriter tupleWriter, IPrimitiveValueProvider[] keyValueProviders) {
+ super(tupleWriter, new UnorderedSlotManager());
+ this.tuples = new ITreeIndexTupleReference[keyValueProviders.length];
+ for (int i = 0; i < keyValueProviders.length; i++) {
+ this.tuples[i] = tupleWriter.createTupleReference();
+ }
+ cmpFrameTuple = tupleWriter.createTupleReference();
- private static double computeDoubleEpsilon() {
- double doubleEpsilon = 1.0;
+ tupleEntries1 = new TupleEntryArrayList(numTuplesEntries, numTuplesEntries);
+ tupleEntries2 = new TupleEntryArrayList(numTuplesEntries, numTuplesEntries);
+ rec = new Rectangle[4];
+ for (int i = 0; i < 4; i++) {
+ rec[i] = new Rectangle(keyValueProviders.length / 2);
+ }
+ this.keyValueProviders = keyValueProviders;
+ }
- do {
- doubleEpsilon /= 2.0;
- } while (1.0 + (doubleEpsilon / 2.0) != 1.0);
- return doubleEpsilon;
- }
+ private static double computeDoubleEpsilon() {
+ double doubleEpsilon = 1.0;
- public static double doubleEpsilon() {
- return doubleEpsilon;
- }
+ do {
+ doubleEpsilon /= 2.0;
+ } while (1.0 + (doubleEpsilon / 2.0) != 1.0);
+ return doubleEpsilon;
+ }
- @Override
- public void initBuffer(byte level) {
- super.initBuffer(level);
- buf.putLong(pageNsnOff, 0);
- buf.putInt(rightPageOff, -1);
- }
+ public static double doubleEpsilon() {
+ return doubleEpsilon;
+ }
- public void setTupleCount(int tupleCount) {
- buf.putInt(tupleCountOff, tupleCount);
- }
+ @Override
+ public void initBuffer(byte level) {
+ super.initBuffer(level);
+ buf.putLong(pageNsnOff, 0);
+ buf.putInt(rightPageOff, -1);
+ }
- @Override
- public void setPageNsn(long pageNsn) {
- buf.putLong(pageNsnOff, pageNsn);
- }
+ public void setTupleCount(int tupleCount) {
+ buf.putInt(tupleCountOff, tupleCount);
+ }
- @Override
- public long getPageNsn() {
- return buf.getLong(pageNsnOff);
- }
+ @Override
+ public void setPageNsn(long pageNsn) {
+ buf.putLong(pageNsnOff, pageNsn);
+ }
- @Override
- protected void resetSpaceParams() {
- buf.putInt(freeSpaceOff, rightPageOff + 4);
- buf.putInt(totalFreeSpaceOff, buf.capacity() - (rightPageOff + 4));
- }
+ @Override
+ public long getPageNsn() {
+ return buf.getLong(pageNsnOff);
+ }
- @Override
- public int getRightPage() {
- return buf.getInt(rightPageOff);
- }
+ @Override
+ protected void resetSpaceParams() {
+ buf.putInt(freeSpaceOff, rightPageOff + 4);
+ buf.putInt(totalFreeSpaceOff, buf.capacity() - (rightPageOff + 4));
+ }
- @Override
- public void setRightPage(int rightPage) {
- buf.putInt(rightPageOff, rightPage);
- }
+ @Override
+ public int getRightPage() {
+ return buf.getInt(rightPageOff);
+ }
- protected ITreeIndexTupleReference[] getTuples() {
- return tuples;
- }
+ @Override
+ public void setRightPage(int rightPage) {
+ buf.putInt(rightPageOff, rightPage);
+ }
- // for debugging
- public ArrayList<Integer> getChildren(int numKeyFields) {
- ArrayList<Integer> ret = new ArrayList<Integer>();
- frameTuple.setFieldCount(numKeyFields);
- int tupleCount = buf.getInt(tupleCountOff);
- for (int i = 0; i < tupleCount; i++) {
- int tupleOff = slotManager.getTupleOff(slotManager.getSlotOff(i));
- frameTuple.resetByTupleOffset(buf, tupleOff);
+ protected ITreeIndexTupleReference[] getTuples() {
+ return tuples;
+ }
- int intVal = IntegerSerializerDeserializer.getInt(
- buf.array(),
- frameTuple.getFieldStart(frameTuple.getFieldCount() - 1)
- + frameTuple.getFieldLength(frameTuple
- .getFieldCount() - 1));
- ret.add(intVal);
- }
- return ret;
- }
+ public void generateDist(ITupleReference tuple, TupleEntryArrayList entries, Rectangle rec, int start, int end) {
+ int j = 0;
+ while (entries.get(j).getTupleIndex() == -1) {
+ j++;
+ }
+ frameTuple.resetByTupleIndex(this, entries.get(j).getTupleIndex());
+ rec.set(frameTuple, keyValueProviders);
+ for (int i = start; i < end; ++i) {
+ if (i != j) {
+ if (entries.get(i).getTupleIndex() != -1) {
+ frameTuple.resetByTupleIndex(this, entries.get(i).getTupleIndex());
+ rec.enlarge(frameTuple, keyValueProviders);
+ } else {
+ rec.enlarge(tuple, keyValueProviders);
+ }
+ }
+ }
+ }
- public void generateDist(ITupleReference tuple,
- TupleEntryArrayList entries, Rectangle rec, int start, int end) {
- int j = 0;
- while (entries.get(j).getTupleIndex() == -1) {
- j++;
- }
- frameTuple.resetByTupleIndex(this, entries.get(j).getTupleIndex());
- rec.set(frameTuple, keyValueProviders);
- for (int i = start; i < end; ++i) {
- if (i != j) {
- if (entries.get(i).getTupleIndex() != -1) {
- frameTuple.resetByTupleIndex(this, entries.get(i)
- .getTupleIndex());
- rec.enlarge(frameTuple, keyValueProviders);
- } else {
- rec.enlarge(tuple, keyValueProviders);
- }
- }
- }
- }
+ public void adjustMBRImpl(ITreeIndexTupleReference[] tuples) {
+ int maxFieldPos = keyValueProviders.length / 2;
+ for (int i = 1; i < getTupleCount(); i++) {
+ frameTuple.resetByTupleIndex(this, i);
+ for (int j = 0; j < maxFieldPos; j++) {
+ int k = maxFieldPos + j;
+ double valA = keyValueProviders[j].getValue(frameTuple.getFieldData(j), frameTuple.getFieldStart(j));
+ double valB = keyValueProviders[j].getValue(tuples[j].getFieldData(j), tuples[j].getFieldStart(j));
+ if (valA < valB) {
+ tuples[j].resetByTupleIndex(this, i);
+ }
+ valA = keyValueProviders[k].getValue(frameTuple.getFieldData(k), frameTuple.getFieldStart(k));
+ valB = keyValueProviders[k].getValue(tuples[k].getFieldData(k), tuples[k].getFieldStart(k));
+ if (valA > valB) {
+ tuples[k].resetByTupleIndex(this, i);
+ }
+ }
+ }
+ }
- @Override
- public ITreeIndexTupleReference createTupleReference() {
- return tupleWriter.createTupleReference();
- }
+ @Override
+ public void computeMBR(ISplitKey splitKey) {
+ RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
+ RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
- public void adjustMBRImpl(ITreeIndexTupleReference[] tuples) {
- int maxFieldPos = keyValueProviders.length / 2;
- for (int i = 1; i < getTupleCount(); i++) {
- frameTuple.resetByTupleIndex(this, i);
- for (int j = 0; j < maxFieldPos; j++) {
- int k = maxFieldPos + j;
- double valA = keyValueProviders[j].getValue(frameTuple.getFieldData(j), frameTuple.getFieldStart(j));
- double valB = keyValueProviders[j].getValue(tuples[j].getFieldData(j), tuples[j].getFieldStart(j));
- if (valA < valB) {
- tuples[j].resetByTupleIndex(this, i);
- }
- valA = keyValueProviders[k].getValue(frameTuple.getFieldData(k), frameTuple.getFieldStart(k));
- valB = keyValueProviders[k].getValue(tuples[k].getFieldData(k), tuples[k].getFieldStart(k));
- if (valA > valB) {
- tuples[k].resetByTupleIndex(this, i);
- }
- }
- }
- }
+ int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+ int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, keyValueProviders.length);
- @Override
- public void computeMBR(ISplitKey splitKey) {
- RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
- RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
+ splitKey.initData(splitKeySize);
+ this.adjustMBR(tuples);
+ rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
+ rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
+ }
- int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
- frameTuple.resetByTupleOffset(buf, tupleOff);
- int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0,
- keyValueProviders.length);
-
- splitKey.initData(splitKeySize);
- this.adjustMBR(tuples);
- rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0,
- rTreeSplitKey.getLeftPageBuffer(), 0);
- rTreeSplitKey.getLeftTuple().resetByTupleOffset(
- rTreeSplitKey.getLeftPageBuffer(), 0);
- }
-
- @Override
- public int getPageHeaderSize() {
- return rightPageOff;
- }
+ @Override
+ public int getPageHeaderSize() {
+ return rightPageOff;
+ }
}
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMInteriorFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMInteriorFrame.java
index 696443b..99a51a4 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMInteriorFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMInteriorFrame.java
@@ -45,10 +45,12 @@
private static final int childPtrSize = 4;
private static IBinaryComparator childPtrCmp = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY)
.createBinaryComparator();
+ private final int keyFieldCount;
public RTreeNSMInteriorFrame(ITreeIndexTupleWriter tupleWriter, IPrimitiveValueProvider[] keyValueProviders) {
super(tupleWriter, keyValueProviders);
- frameTuple.setFieldCount(keyValueProviders.length);
+ keyFieldCount = keyValueProviders.length;
+ frameTuple.setFieldCount(keyFieldCount);
}
@Override
@@ -151,6 +153,13 @@
}
@Override
+ public ITreeIndexTupleReference createTupleReference() {
+ ITreeIndexTupleReference tuple = tupleWriter.createTupleReference();
+ tuple.setFieldCount(keyFieldCount);
+ return tuple;
+ }
+
+ @Override
public int getBestChildPageId() {
return buf.getInt(getChildPointerOff(frameTuple));
}
@@ -642,4 +651,21 @@
adjustMBRImpl(tuples);
}
+
+ // For debugging.
+ public ArrayList<Integer> getChildren(MultiComparator cmp) {
+ ArrayList<Integer> ret = new ArrayList<Integer>();
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+ int tupleCount = buf.getInt(tupleCountOff);
+ for (int i = 0; i < tupleCount; i++) {
+ int tupleOff = slotManager.getTupleOff(slotManager.getSlotOff(i));
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+ int intVal = IntegerSerializerDeserializer.getInt(
+ buf.array(),
+ frameTuple.getFieldStart(frameTuple.getFieldCount() - 1)
+ + frameTuple.getFieldLength(frameTuple.getFieldCount() - 1));
+ ret.add(intVal);
+ }
+ return ret;
+ }
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMLeafFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMLeafFrame.java
index b2ae5fc..858b1d5 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMLeafFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMLeafFrame.java
@@ -37,6 +37,11 @@
}
@Override
+ public ITreeIndexTupleReference createTupleReference() {
+ return tupleWriter.createTupleReference();
+ }
+
+ @Override
public int findTupleIndex(ITupleReference tuple, MultiComparator cmp) {
return slotManager.findTupleIndex(tuple, frameTuple, cmp, null, null);
}
@@ -85,10 +90,10 @@
frameTuple.resetByTupleIndex(this, k);
- double LowerKey = keyValueProviders[i].getValue(frameTuple.getFieldData(i),
- frameTuple.getFieldStart(i));
- double UpperKey = keyValueProviders[j].getValue(frameTuple.getFieldData(j),
- frameTuple.getFieldStart(j));
+ double LowerKey = keyValueProviders[i]
+ .getValue(frameTuple.getFieldData(i), frameTuple.getFieldStart(i));
+ double UpperKey = keyValueProviders[j]
+ .getValue(frameTuple.getFieldData(j), frameTuple.getFieldStart(j));
tupleEntries1.add(k, LowerKey);
tupleEntries2.add(k, UpperKey);
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
index bfbb63b..5b48b8d 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -44,7 +44,7 @@
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
-import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrame;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
@@ -78,8 +78,9 @@
public byte currentLevel = 0;
// TODO: is MultiComparator needed at all?
- public RTree(IBufferCache bufferCache, int fieldCount, IBinaryComparatorFactory[] cmpFactories, IFreePageManager freePageManager,
- ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory) {
+ public RTree(IBufferCache bufferCache, int fieldCount, IBinaryComparatorFactory[] cmpFactories,
+ IFreePageManager freePageManager, ITreeIndexFrameFactory interiorFrameFactory,
+ ITreeIndexFrameFactory leafFrameFactory) {
this.bufferCache = bufferCache;
this.fieldCount = fieldCount;
this.cmpFactories = cmpFactories;
@@ -87,7 +88,7 @@
this.interiorFrameFactory = interiorFrameFactory;
this.leafFrameFactory = leafFrameFactory;
globalNsn = new AtomicLong();
- this.treeLatch = new ReentrantReadWriteLock(true);
+ this.treeLatch = new ReentrantReadWriteLock(true);
}
public void incrementGlobalNsn() {
@@ -141,34 +142,46 @@
return strBuilder.toString();
}
- public void printTree(IRTreeFrame leafFrame, IRTreeFrame interiorFrame, ISerializerDeserializer[] keySerdes)
- throws Exception {
- printTree(rootPage, null, false, leafFrame, interiorFrame, keySerdes);
+ public byte getTreeHeight(IRTreeLeafFrame leafFrame) throws HyracksDataException {
+ ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), false);
+ rootNode.acquireReadLatch();
+ try {
+ leafFrame.setPage(rootNode);
+ return leafFrame.getLevel();
+ } finally {
+ rootNode.releaseReadLatch();
+ bufferCache.unpin(rootNode);
+ }
}
- public void printTree(int pageId, ICachedPage parent, boolean unpin, IRTreeFrame leafFrame,
- IRTreeFrame interiorFrame, ISerializerDeserializer[] keySerdes) throws Exception {
+ @SuppressWarnings("rawtypes")
+ public String printTree(IRTreeLeafFrame leafFrame, IRTreeInteriorFrame interiorFrame,
+ ISerializerDeserializer[] keySerdes) throws Exception {
+ MultiComparator cmp = MultiComparator.create(cmpFactories);
+ byte treeHeight = getTreeHeight(leafFrame);
+ StringBuilder strBuilder = new StringBuilder();
+ printTree(rootPage, null, false, leafFrame, interiorFrame, treeHeight, keySerdes, strBuilder, cmp);
+ return strBuilder.toString();
+ }
+ @SuppressWarnings("rawtypes")
+ public void printTree(int pageId, ICachedPage parent, boolean unpin, IRTreeLeafFrame leafFrame,
+ IRTreeInteriorFrame interiorFrame, byte treeHeight, ISerializerDeserializer[] keySerdes,
+ StringBuilder strBuilder, MultiComparator cmp) throws Exception {
ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
- incrementPins();
node.acquireReadLatch();
- incrementReadLatchesAcquired();
-
try {
if (parent != null && unpin == true) {
parent.releaseReadLatch();
- incrementReadLatchesReleased();
bufferCache.unpin(parent);
- incrementUnpins();
}
-
interiorFrame.setPage(node);
int level = interiorFrame.getLevel();
-
- System.out.format("%1d ", level);
- System.out.format("%3d ", pageId);
- for (int i = 0; i < currentLevel - level; i++)
- System.out.format(" ");
+ strBuilder.append(String.format("%1d ", level));
+ strBuilder.append(String.format("%3d ", pageId) + ": ");
+ for (int i = 0; i < treeHeight - level; i++) {
+ strBuilder.append(" ");
+ }
String keyString;
if (interiorFrame.isLeaf()) {
@@ -178,24 +191,21 @@
keyString = TreeIndexUtils.printFrameTuples(interiorFrame, keySerdes);
}
- System.out.format(keyString);
+ strBuilder.append(keyString + "\n");
if (!interiorFrame.isLeaf()) {
- ArrayList<Integer> children = ((RTreeNSMFrame) (interiorFrame)).getChildren(cmpFactories.length);
+ ArrayList<Integer> children = ((RTreeNSMInteriorFrame) (interiorFrame)).getChildren(cmp);
for (int i = 0; i < children.size(); i++) {
- printTree(children.get(i), node, i == children.size() - 1, leafFrame, interiorFrame, keySerdes);
+ printTree(children.get(i), node, i == children.size() - 1, leafFrame, interiorFrame, treeHeight,
+ keySerdes, strBuilder, cmp);
}
} else {
node.releaseReadLatch();
- incrementReadLatchesReleased();
bufferCache.unpin(node);
- incrementUnpins();
}
} catch (Exception e) {
node.releaseReadLatch();
- incrementReadLatchesReleased();
bufferCache.unpin(node);
- incrementUnpins();
- throw e;
+ e.printStackTrace();
}
}
@@ -675,7 +685,8 @@
}
parentLsn = pageLsn;
- if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), ctx.traverseList, pageIndex, ctx.cmp) != -1) {
+ if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), ctx.traverseList, pageIndex,
+ ctx.cmp) != -1) {
fillPath(ctx, pageIndex);
return;
}
@@ -1025,7 +1036,7 @@
MultiComparator cmp = MultiComparator.create(cmpFactories);
SearchPredicate searchPred = new SearchPredicate(null, cmp);
-
+
int currentPageId = rootPage + 1;
int maxPageId = freePageManager.getMaxPage(ctx.metaFrame);
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
index 260cdea..103cd45 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
@@ -24,105 +24,95 @@
import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMFrame;
public class UnorderedSlotManager extends AbstractSlotManager {
-
- @Override
- public int findTupleIndex(ITupleReference searchKey,
- ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
- FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy) {
- int maxFieldPos = multiCmp.getKeyFieldCount() / 2;
- for (int i = 0; i < frame.getTupleCount(); i++) {
- frameTuple.resetByTupleIndex(frame, i);
+ @Override
+ public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
+ FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy) {
- boolean foundTuple = true;
- for (int j = 0; j < maxFieldPos; j++) {
- int k = maxFieldPos + j;
- int c1 = multiCmp.getComparators()[j].compare(
- frameTuple.getFieldData(j),
- frameTuple.getFieldStart(j),
- frameTuple.getFieldLength(j),
- searchKey.getFieldData(j), searchKey.getFieldStart(j),
- searchKey.getFieldLength(j));
+ int maxFieldPos = multiCmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < frame.getTupleCount(); i++) {
+ frameTuple.resetByTupleIndex(frame, i);
- if (c1 != 0) {
- foundTuple = false;
- break;
- }
- int c2 = multiCmp.getComparators()[k].compare(
- frameTuple.getFieldData(k),
- frameTuple.getFieldStart(k),
- frameTuple.getFieldLength(k),
- searchKey.getFieldData(k), searchKey.getFieldStart(k),
- searchKey.getFieldLength(k));
- if (c2 != 0) {
- foundTuple = false;
- break;
- }
- }
- int remainingFieldCount = frameTuple.getFieldCount()
- - multiCmp.getKeyFieldCount();
- for (int j = multiCmp.getKeyFieldCount(); j < multiCmp
- .getKeyFieldCount() + remainingFieldCount; j++) {
- if (!compareField(searchKey, frameTuple, j)) {
- foundTuple = false;
- break;
- }
- }
- if (foundTuple) {
- return i;
- }
- }
- return -1;
- }
+ boolean foundTuple = true;
+ for (int j = 0; j < maxFieldPos; j++) {
+ int k = maxFieldPos + j;
+ int c1 = multiCmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+ frameTuple.getFieldLength(j), searchKey.getFieldData(j), searchKey.getFieldStart(j),
+ searchKey.getFieldLength(j));
- public boolean compareField(ITupleReference searchKey,
- ITreeIndexTupleReference frameTuple, int fIdx) {
- int searchKeyFieldLength = searchKey.getFieldLength(fIdx);
- int frameTupleFieldLength = frameTuple.getFieldLength(fIdx);
+ if (c1 != 0) {
+ foundTuple = false;
+ break;
+ }
+ int c2 = multiCmp.getComparators()[k].compare(frameTuple.getFieldData(k), frameTuple.getFieldStart(k),
+ frameTuple.getFieldLength(k), searchKey.getFieldData(k), searchKey.getFieldStart(k),
+ searchKey.getFieldLength(k));
+ if (c2 != 0) {
+ foundTuple = false;
+ break;
+ }
+ }
+ int remainingFieldCount = frameTuple.getFieldCount() - multiCmp.getKeyFieldCount();
+ for (int j = multiCmp.getKeyFieldCount(); j < multiCmp.getKeyFieldCount() + remainingFieldCount; j++) {
+ if (!compareField(searchKey, frameTuple, j)) {
+ foundTuple = false;
+ break;
+ }
+ }
+ if (foundTuple) {
+ return i;
+ }
+ }
+ return -1;
+ }
- if (searchKeyFieldLength != frameTupleFieldLength) {
- return false;
- }
+ public boolean compareField(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, int fIdx) {
+ int searchKeyFieldLength = searchKey.getFieldLength(fIdx);
+ int frameTupleFieldLength = frameTuple.getFieldLength(fIdx);
- for (int i = 0; i < searchKeyFieldLength; i++) {
- if (searchKey.getFieldData(fIdx)[i + searchKey.getFieldStart(fIdx)] != frameTuple
- .getFieldData(fIdx)[i + frameTuple.getFieldStart(fIdx)]) {
- return false;
- }
- }
- return true;
- }
+ if (searchKeyFieldLength != frameTupleFieldLength) {
+ return false;
+ }
- @Override
- public int insertSlot(int tupleIndex, int tupleOff) {
- int slotOff = getSlotEndOff() - slotSize;
- setSlot(slotOff, tupleOff);
- return slotOff;
- }
+ for (int i = 0; i < searchKeyFieldLength; i++) {
+ if (searchKey.getFieldData(fIdx)[i + searchKey.getFieldStart(fIdx)] != frameTuple.getFieldData(fIdx)[i
+ + frameTuple.getFieldStart(fIdx)]) {
+ return false;
+ }
+ }
+ return true;
+ }
- public void modifySlot(int slotOff, int tupleOff) {
- setSlot(slotOff, tupleOff);
- }
+ @Override
+ public int insertSlot(int tupleIndex, int tupleOff) {
+ int slotOff = getSlotEndOff() - slotSize;
+ setSlot(slotOff, tupleOff);
+ return slotOff;
+ }
- public void deleteEmptySlots() {
- int slotOff = getSlotStartOff();
- while (slotOff >= getSlotEndOff()) {
- if (frame.getBuffer().getInt(slotOff) == -1) {
- while (frame.getBuffer().getInt(getSlotEndOff()) == -1) {
- ((RTreeNSMFrame) frame)
- .setTupleCount(frame.getTupleCount() - 1);
- }
- if (slotOff > getSlotEndOff()) {
- System.arraycopy(frame.getBuffer().array(),
- getSlotEndOff(), frame.getBuffer().array(),
- slotOff, slotSize);
- ((RTreeNSMFrame) frame)
- .setTupleCount(frame.getTupleCount() - 1);
- } else {
- break;
- }
- }
- slotOff -= slotSize;
- }
- }
+ public void modifySlot(int slotOff, int tupleOff) {
+ setSlot(slotOff, tupleOff);
+ }
+
+ public void deleteEmptySlots() {
+ int slotOff = getSlotStartOff();
+ while (slotOff >= getSlotEndOff()) {
+ if (frame.getBuffer().getInt(slotOff) == -1) {
+ while (frame.getBuffer().getInt(getSlotEndOff()) == -1) {
+ ((RTreeNSMFrame) frame).setTupleCount(frame.getTupleCount() - 1);
+ if (getSlotEndOff() > getSlotStartOff()) {
+ break;
+ }
+ }
+ if (slotOff > getSlotEndOff()) {
+ System.arraycopy(frame.getBuffer().array(), getSlotEndOff(), frame.getBuffer().array(), slotOff,
+ slotSize);
+ ((RTreeNSMFrame) frame).setTupleCount(frame.getTupleCount() - 1);
+ } else {
+ break;
+ }
+ }
+ slotOff -= slotSize;
+ }
+ }
}