- Fixed a bug in the way we check for free space in a page before we insert a tuple
- Minor refactoring
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_indexes@490 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
index 75a74ca..49adc87 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
@@ -7,24 +7,23 @@
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.rtree.impls.Rectangle;
import edu.uci.ics.hyracks.storage.am.rtree.impls.TraverseList;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.TupleEntryArrayList;
public interface IRTreeFrame extends ITreeIndexFrame {
-
+
public ITreeIndexTupleReference createTupleReference();
-
+
public boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
public void computeMBR(ISplitKey splitKey, MultiComparator cmp);
-
+
public void delete(int tupleIndex, MultiComparator cmp) throws Exception;
-
+
public int findTupleByPointer(int pageId, MultiComparator cmp);
-
+
public int findTupleByPointer(ITupleReference tuple, TraverseList traverseList, int parentId, MultiComparator cmp);
public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp);
-
+
public int findTupleIndex(ITupleReference tuple, MultiComparator cmp);
public int getPageNsn();
@@ -37,17 +36,14 @@
public int getBestChildPageId(MultiComparator cmp);
- public boolean findBestChild(ITupleReference tuple, TupleEntryArrayList entries, MultiComparator cmp);
+ public boolean findBestChild(ITupleReference tuple, MultiComparator cmp);
public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp);
public void adjustKey(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
- public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
- TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception;
-
public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
-
+
public Rectangle checkIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
index e4bdf93..805c084 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
@@ -16,6 +16,7 @@
import edu.uci.ics.hyracks.storage.am.rtree.impls.EntriesOrder;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSplitKey;
import edu.uci.ics.hyracks.storage.am.rtree.impls.Rectangle;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SpatialUtils;
import edu.uci.ics.hyracks.storage.am.rtree.impls.TraverseList;
import edu.uci.ics.hyracks.storage.am.rtree.impls.TupleEntryArrayList;
import edu.uci.ics.hyracks.storage.am.rtree.impls.UnorderedSlotManager;
@@ -26,8 +27,11 @@
protected static final int rightPageOff = pageNsnOff + 4;
private ITreeIndexTupleReference[] tuples;
-
private ITreeIndexTupleReference cmpFrameTuple;
+ public final SpatialUtils spatialUtils;
+ public TupleEntryArrayList tupleEntries1; // used for split and checking enlargement
+ public TupleEntryArrayList tupleEntries2; // used for split
+ public Rectangle[] rec;
private static final double splitFactor = 0.4;
private static final int nearMinimumOverlapFactor = 32;
@@ -39,6 +43,14 @@
this.tuples[i] = tupleWriter.createTupleReference();
}
cmpFrameTuple = tupleWriter.createTupleReference();
+ spatialUtils = new SpatialUtils();
+ // TODO: find a better way to know number of entries per node
+ tupleEntries1 = new TupleEntryArrayList(100, 100, spatialUtils);
+ tupleEntries2 = new TupleEntryArrayList(100, 100, spatialUtils);
+ rec = new Rectangle[4];
+ for (int i = 0; i < 4; i++) {
+ rec[i] = new Rectangle(keyFieldCount / 2);
+ }
}
@Override
@@ -101,8 +113,7 @@
}
@Override
- public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
- TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception {
+ public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey) throws Exception {
RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
@@ -130,27 +141,27 @@
double UpperKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(j),
frameTuple.getFieldStart(j));
- entries1.add(k, LowerKey);
- entries2.add(k, UpperKey);
+ tupleEntries1.add(k, LowerKey);
+ tupleEntries2.add(k, UpperKey);
}
double LowerKey = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
double UpperKey = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j));
- entries1.add(-1, LowerKey);
- entries2.add(-1, UpperKey);
+ tupleEntries1.add(-1, LowerKey);
+ tupleEntries2.add(-1, UpperKey);
- entries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
- entries2.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+ tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+ tupleEntries2.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
double lowerMargin = 0.0, upperMargin = 0.0;
// generate distribution
for (int k = 1; k <= splitDistribution; ++k) {
int d = m - 1 + k;
- generateDist(tuple, entries1, rec[0], 0, d);
- generateDist(tuple, entries2, rec[1], 0, d);
- generateDist(tuple, entries1, rec[2], d, getTupleCount() + 1);
- generateDist(tuple, entries2, rec[3], d, getTupleCount() + 1);
+ generateDist(tuple, tupleEntries1, rec[0], 0, d);
+ generateDist(tuple, tupleEntries2, rec[1], 0, d);
+ generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
+ generateDist(tuple, tupleEntries2, rec[3], d, getTupleCount() + 1);
// calculate the margin of the distributions
lowerMargin += rec[0].margin() + rec[2].margin();
@@ -165,20 +176,20 @@
sortOrder = (lowerMargin < upperMargin) ? 0 : 2;
}
- entries1.clear();
- entries2.clear();
+ tupleEntries1.clear();
+ tupleEntries2.clear();
}
for (int i = 0; i < getTupleCount(); ++i) {
frameTuple.resetByTupleIndex(this, i);
double key = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(splitAxis + sortOrder),
frameTuple.getFieldStart(splitAxis + sortOrder));
- entries1.add(i, key);
+ tupleEntries1.add(i, key);
}
double key = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(splitAxis + sortOrder),
tuple.getFieldStart(splitAxis + sortOrder));
- entries1.add(-1, key);
- entries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+ tupleEntries1.add(-1, key);
+ tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
double minArea = Double.MAX_VALUE;
double minOverlap = Double.MAX_VALUE;
@@ -186,8 +197,8 @@
for (int i = 1; i <= splitDistribution; ++i) {
int d = m - 1 + i;
- generateDist(tuple, entries1, rec[0], 0, d);
- generateDist(tuple, entries1, rec[2], d, getTupleCount() + 1);
+ generateDist(tuple, tupleEntries1, rec[0], 0, d);
+ generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
double overlap = rec[0].overlappedArea(rec[2]);
if (overlap < minOverlap) {
@@ -215,11 +226,11 @@
for (int i = startIndex; i < endIndex; i++) { // TODO: is there a better
// way
// to split the entries?
- if (entries1.get(i).getTupleIndex() != -1) {
- frameTuple.resetByTupleIndex(this, entries1.get(i).getTupleIndex());
+ if (tupleEntries1.get(i).getTupleIndex() != -1) {
+ frameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
rightFrame.insert(frameTuple, cmp, -1);
((UnorderedSlotManager) slotManager).modifySlot(
- slotManager.getSlotOff(entries1.get(i).getTupleIndex()), -1);
+ slotManager.getSlotOff(tupleEntries1.get(i).getTupleIndex()), -1);
totalBytes += tupleWriter.bytesRequired(frameTuple);
numOfDeletedTuples++;
} else {
@@ -256,7 +267,8 @@
rTreeSplitKey.getRightPageBuffer(), 0);
rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
- entries1.clear();
+ tupleEntries1.clear();
+ tupleEntries2.clear();
return 0;
}
@@ -299,7 +311,7 @@
}
@Override
- public boolean findBestChild(ITupleReference tuple, TupleEntryArrayList entries, MultiComparator cmp) {
+ public boolean findBestChild(ITupleReference tuple, MultiComparator cmp) {
cmpFrameTuple.setFieldCount(cmp.getFieldCount());
frameTuple.setFieldCount(cmp.getFieldCount());
@@ -313,19 +325,19 @@
for (int i = 0; i < getTupleCount(); ++i) {
frameTuple.resetByTupleIndex(this, i);
double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
- entries.add(i, enlargedArea);
+ tupleEntries1.add(i, enlargedArea);
if (enlargedArea < minEnlargedArea) {
minEnlargedArea = enlargedArea;
bestChild = i;
}
}
- if (minEnlargedArea < entries.getDoubleEpsilon() || minEnlargedArea > entries.getDoubleEpsilon()) {
+ if (minEnlargedArea < tupleEntries1.getDoubleEpsilon() || minEnlargedArea > tupleEntries1.getDoubleEpsilon()) {
minEnlargedArea = Double.MAX_VALUE;
int k;
if (getTupleCount() > nearMinimumOverlapFactor) {
// sort the entries based on their area enlargement needed
// to include the object
- entries.sort(EntriesOrder.ASCENDING, getTupleCount());
+ tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount());
k = nearMinimumOverlapFactor;
} else {
k = getTupleCount();
@@ -337,7 +349,7 @@
double difference = 0.0;
for (int j = 0; j < getTupleCount(); ++j) {
frameTuple.resetByTupleIndex(this, j);
- cmpFrameTuple.resetByTupleIndex(this, entries.get(i).getTupleIndex());
+ cmpFrameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
int c = cmp.getIntCmp().compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
frameTuple.getFieldStart(cmp.getKeyFieldCount()),
@@ -392,7 +404,7 @@
}
}
}
- entries.clear();
+ tupleEntries1.clear();
frameTuple.resetByTupleIndex(this, bestChild);
if (minEnlargedArea > 0.0) {
@@ -712,13 +724,6 @@
}
@Override
- public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey)
- throws Exception {
- // TODO Auto-generated method stub
- return 0;
- }
-
- @Override
public void computeMBR(ISplitKey splitKey, MultiComparator cmp) {
RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/InteriorFrameSchema.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/InteriorFrameSchema.java
new file mode 100644
index 0000000..d8801a7
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/InteriorFrameSchema.java
@@ -0,0 +1,26 @@
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.TypeTrait;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public class InteriorFrameSchema {
+
+ private MultiComparator interiorCmp;
+
+ public InteriorFrameSchema(MultiComparator leafCmp) {
+ // 1 for node's pointer
+ ITypeTrait[] interiorTypeTraits = new ITypeTrait[leafCmp.getKeyFieldCount() + 1];
+ for (int i = 0; i < leafCmp.getKeyFieldCount(); i++) {
+ interiorTypeTraits[i] = new TypeTrait(leafCmp.getTypeTraits()[i].getStaticallyKnownDataLength());
+ }
+
+ // the pointer is of type int (size: 4 bytes)
+ interiorTypeTraits[leafCmp.getKeyFieldCount()] = new TypeTrait(4);
+ interiorCmp = new MultiComparator(interiorTypeTraits, leafCmp.getComparators());
+ }
+
+ public MultiComparator getInteriorCmp() {
+ return interiorCmp;
+ }
+}
\ No newline at end of file
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 ed70d1b..612ef85 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
@@ -12,8 +12,8 @@
import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
import edu.uci.ics.hyracks.storage.am.common.frames.FrameOpSpaceStatus;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeCursor;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrameFactory;
@@ -215,11 +215,10 @@
fileId = -1;
}
- public RTreeOpContext createOpContext(IndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
+ public RTreeOpContext createOpContext(IndexOp op, IRTreeFrame leafFrame, IRTreeFrame interiorFrame,
ITreeIndexMetaDataFrame metaFrame, String threadName) {
// TODO: figure out better tree-height hint
- return new RTreeOpContext(op, interiorFrame, leafFrame, metaFrame, 8, interiorCmp.getKeyFieldCount() / 2,
- threadName);
+ return new RTreeOpContext(op, leafFrame, interiorFrame, metaFrame, 8, threadName);
}
public void insert(ITupleReference tuple, RTreeOpContext ctx) throws Exception {
@@ -316,8 +315,7 @@
if (!isLeaf) {
// checkEnlargement must be called *before* getBestChildPageId
- boolean needsEnlargement = ctx.interiorFrame.findBestChild(ctx.getTuple(), ctx.tupleEntries1,
- interiorCmp);
+ boolean needsEnlargement = ctx.interiorFrame.findBestChild(ctx.getTuple(), interiorCmp);
int childPageId = ctx.interiorFrame.getBestChildPageId(interiorCmp);
if (needsEnlargement) {
@@ -380,9 +378,9 @@
throws Exception {
FrameOpSpaceStatus spaceStatus;
if (!isLeaf) {
- spaceStatus = ctx.interiorFrame.hasSpaceInsert(ctx.getTuple(), interiorCmp);
+ spaceStatus = ctx.interiorFrame.hasSpaceInsert(tuple, interiorCmp);
} else {
- spaceStatus = ctx.leafFrame.hasSpaceInsert(ctx.getTuple(), leafCmp);
+ spaceStatus = ctx.leafFrame.hasSpaceInsert(tuple, leafCmp);
}
switch (spaceStatus) {
@@ -433,8 +431,7 @@
rightFrame.setPage(rightNode);
rightFrame.initBuffer((byte) ctx.interiorFrame.getLevel());
rightFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
- ret = ctx.interiorFrame.split(rightFrame, tuple, interiorCmp, ctx.splitKey, ctx.tupleEntries1,
- ctx.tupleEntries2, ctx.rec);
+ ret = ctx.interiorFrame.split(rightFrame, tuple, interiorCmp, ctx.splitKey);
ctx.interiorFrame.setRightPage(rightPageId);
rightFrame.setPageNsn(ctx.interiorFrame.getPageNsn());
incrementGlobalNsn();
@@ -448,8 +445,7 @@
rightFrame.setPage(rightNode);
rightFrame.initBuffer((byte) 0);
rightFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
- ret = ctx.leafFrame.split(rightFrame, tuple, leafCmp, ctx.splitKey, ctx.tupleEntries1,
- ctx.tupleEntries2, ctx.rec);
+ ret = ctx.leafFrame.split(rightFrame, tuple, leafCmp, ctx.splitKey);
ctx.leafFrame.setRightPage(rightPageId);
rightFrame.setPageNsn(ctx.leafFrame.getPageNsn());
incrementGlobalNsn();
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
index 976c45e..91c6e26 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
@@ -13,33 +13,23 @@
public IRTreeCursor cursor;
public final ITreeIndexMetaDataFrame metaFrame;
public final RTreeSplitKey splitKey;
- public final SpatialUtils spatialUtils;
public ITupleReference tuple;
- public TupleEntryArrayList tupleEntries1; // used for split and checking enlargement
- public TupleEntryArrayList tupleEntries2; // used for split
- public final PathList pathList; // used to record the pageIds and pageLsns of the visited pages
+ public final PathList pathList; // used to record the pageIds and pageLsns
+ // of the visited pages
public final TraverseList traverseList; // used for traversing the tree
- public Rectangle[] rec;
public String threadName; // for debugging
- public RTreeOpContext(IndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
- ITreeIndexMetaDataFrame metaFrame, int treeHeightHint, int dim, String threadName) {
+ public RTreeOpContext(IndexOp op, IRTreeFrame leafFrame, IRTreeFrame interiorFrame,
+ ITreeIndexMetaDataFrame metaFrame, int treeHeightHint, String threadName) {
this.op = op;
this.interiorFrame = interiorFrame;
this.leafFrame = leafFrame;
this.metaFrame = metaFrame;
splitKey = new RTreeSplitKey(interiorFrame.getTupleWriter().createTupleReference(), interiorFrame
.getTupleWriter().createTupleReference());
- spatialUtils = new SpatialUtils();
- // TODO: find a better way to know number of entries per node
- tupleEntries1 = new TupleEntryArrayList(100, 100, spatialUtils);
- tupleEntries2 = new TupleEntryArrayList(100, 100, spatialUtils);
+
pathList = new PathList(treeHeightHint, treeHeightHint);
traverseList = new TraverseList(100, 100);
- rec = new Rectangle[4];
- for (int i = 0; i < 4; i++) {
- rec[i] = new Rectangle(dim);
- }
this.threadName = threadName;
}
@@ -52,12 +42,6 @@
}
public void reset() {
- if (tupleEntries1 != null) {
- tupleEntries1.clear();
- }
- if (tupleEntries2 != null) {
- tupleEntries2.clear();
- }
if (pathList != null) {
pathList.clear();
}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml b/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
index 2090bb2..5e76687 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
@@ -34,7 +34,7 @@
<dependency>
<groupId>edu.uci.ics.hyracks</groupId>
<artifactId>hyracks-control-nc</artifactId>
- <version>0.1.4</version>
+ <version>0.1.5</version>
<scope>compile</scope>
</dependency>
<dependency>
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
index 6ed84f2..ad123bb 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
@@ -32,11 +32,12 @@
import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrameFactory;
import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMRTreeFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
import edu.uci.ics.hyracks.storage.am.rtree.impls.Rectangle;
@@ -65,15 +66,6 @@
int fileId = fmp.lookupFileId(file);
bufferCache.openFile(fileId);
- // declare interior-frame-tuple fields
- int interiorFieldCount = 5;
- ITypeTrait[] interiorTypeTraits = new ITypeTrait[interiorFieldCount];
- interiorTypeTraits[0] = new TypeTrait(8);
- interiorTypeTraits[1] = new TypeTrait(8);
- interiorTypeTraits[2] = new TypeTrait(8);
- interiorTypeTraits[3] = new TypeTrait(8);
- interiorTypeTraits[4] = new TypeTrait(4);
-
// declare keys
int keyFieldCount = 4;
IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
@@ -83,19 +75,21 @@
cmps[3] = cmps[0];
// declare leaf-frame-tuple fields
- int leafFieldCount = 5;
+ int leafFieldCount = 7;
ITypeTrait[] leafTypeTraits = new ITypeTrait[leafFieldCount];
leafTypeTraits[0] = new TypeTrait(8);
leafTypeTraits[1] = new TypeTrait(8);
leafTypeTraits[2] = new TypeTrait(8);
leafTypeTraits[3] = new TypeTrait(8);
- leafTypeTraits[4] = new TypeTrait(4);
+ leafTypeTraits[4] = new TypeTrait(8);
+ leafTypeTraits[5] = new TypeTrait(4);
+ leafTypeTraits[6] = new TypeTrait(8);
- MultiComparator interiorCmp = new MultiComparator(interiorTypeTraits, cmps);
MultiComparator leafCmp = new MultiComparator(leafTypeTraits, cmps);
+ InteriorFrameSchema interiorFrameSchema = new InteriorFrameSchema(leafCmp);
RTreeTypeAwareTupleWriterFactory interiorTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(
- interiorTypeTraits);
+ interiorFrameSchema.getInteriorCmp().getTypeTraits());
RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory, keyFieldCount);
@@ -107,8 +101,8 @@
IRTreeFrame leafFrame = leafFrameFactory.getFrame();
IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
- RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, interiorCmp,
- leafCmp);
+ RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory,
+ interiorFrameSchema.getInteriorCmp(), leafCmp);
rtree.create(fileId, leafFrame, metaFrame);
rtree.open(fileId);
@@ -120,17 +114,21 @@
@SuppressWarnings("rawtypes")
ISerializerDeserializer[] recDescSers = { DoubleSerializerDeserializer.INSTANCE,
DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- DoubleSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+ DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE };
RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
accessor.reset(hyracksFrame);
FrameTupleReference tuple = new FrameTupleReference();
- RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, interiorFrame, leafFrame, metaFrame,
+ RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, leafFrame, interiorFrame, metaFrame,
"unittest");
Random rnd = new Random();
rnd.setSeed(50);
+
+ Random rnd2 = new Random();
+ rnd2.setSeed(50);
Stack<Integer> s = new Stack<Integer>();
for (int i = 0; i < 10000; i++) {
@@ -139,7 +137,9 @@
double p2x = rnd.nextDouble();
double p2y = rnd.nextDouble();
- int pk = rnd.nextInt();
+ double pk1 = rnd2.nextDouble();
+ int pk2 = rnd2.nextInt();
+ double pk3 = rnd2.nextDouble();
tb.reset();
DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
@@ -150,7 +150,11 @@
tb.addFieldEndOffset();
DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
+ DoubleSerializerDeserializer.INSTANCE.serialize(pk1, dos);
+ tb.addFieldEndOffset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(pk2, dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(pk3, dos);
tb.addFieldEndOffset();
appender.reset(hyracksFrame, true);
@@ -173,7 +177,7 @@
// rtree.printTree(leafFrame, interiorFrame, recDescSers);
// System.out.println();
- RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, interiorFrame, leafFrame, metaFrame,
+ RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame,
"unittest");
ArrayList<Rectangle> results = new ArrayList<Rectangle>();
rtree.search(s, tuple, searchOpCtx, results);
@@ -190,6 +194,13 @@
String stats = rtree.printStats();
print(stats);
+ // TreeIndexStatsGatherer statsGatherer = new
+ // TreeIndexStatsGatherer(bufferCache, freePageManager, fileId, 1);
+ // TreeIndexStats stats = statsGatherer.gatherStats(leafFrame,
+ // interiorFrame, metaFrame);
+ // String string = stats.toString();
+ // System.out.println(string);
+
rtree.close();
bufferCache.closeFile(fileId);
bufferCache.close();
@@ -268,7 +279,7 @@
accessor.reset(hyracksFrame);
FrameTupleReference tuple = new FrameTupleReference();
- RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, interiorFrame, leafFrame, metaFrame,
+ RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, leafFrame, interiorFrame, metaFrame,
"unittest");
File datasetFile = new File("/home/salsubaiee/dataset.txt");
@@ -340,7 +351,7 @@
// rtree.printTree(leafFrame, interiorFrame, recDescSers);
// System.out.println();
- RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, interiorFrame, leafFrame, metaFrame,
+ RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame,
"unittest");
File querysetFile = new File("/home/salsubaiee/queryset.txt");
@@ -412,7 +423,7 @@
// String stats = rtree.printStats();
// print(stats);
- RTreeOpContext deleteOpCtx = rtree.createOpContext(IndexOp.DELETE, interiorFrame, leafFrame, metaFrame,
+ RTreeOpContext deleteOpCtx = rtree.createOpContext(IndexOp.DELETE, leafFrame, interiorFrame, metaFrame,
"unittest");
BufferedReader reader3 = new BufferedReader(new FileReader(datasetFile));
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
index e3d8aa4..d0d988fb 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
@@ -33,12 +33,13 @@
import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeCursor;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrameFactory;
import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMRTreeFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchCursor;
@@ -66,15 +67,6 @@
int fileId = fmp.lookupFileId(file);
bufferCache.openFile(fileId);
- // declare interior-frame-tuple fields
- int interiorFieldCount = 5;
- ITypeTrait[] interiorTypeTraits = new ITypeTrait[interiorFieldCount];
- interiorTypeTraits[0] = new TypeTrait(8);
- interiorTypeTraits[1] = new TypeTrait(8);
- interiorTypeTraits[2] = new TypeTrait(8);
- interiorTypeTraits[3] = new TypeTrait(8);
- interiorTypeTraits[4] = new TypeTrait(4);
-
// declare keys
int keyFieldCount = 4;
IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
@@ -92,11 +84,11 @@
leafTypeTraits[3] = new TypeTrait(8);
leafTypeTraits[4] = new TypeTrait(4);
- MultiComparator interiorCmp = new MultiComparator(interiorTypeTraits, cmps);
MultiComparator leafCmp = new MultiComparator(leafTypeTraits, cmps);
+ InteriorFrameSchema interiorFrameSchema = new InteriorFrameSchema(leafCmp);
RTreeTypeAwareTupleWriterFactory interiorTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(
- interiorTypeTraits);
+ interiorFrameSchema.getInteriorCmp().getTypeTraits());
RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
IRTreeFrameFactory interiorFrameFactory = new NSMRTreeFrameFactory(interiorTupleWriterFactory, keyFieldCount);
@@ -108,8 +100,8 @@
IRTreeFrame leafFrame = leafFrameFactory.getFrame();
IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
- RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, interiorCmp,
- leafCmp);
+ RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory,
+ interiorFrameSchema.getInteriorCmp(), leafCmp);
rtree.create(fileId, leafFrame, metaFrame);
rtree.open(fileId);
@@ -127,7 +119,7 @@
accessor.reset(hyracksFrame);
FrameTupleReference tuple = new FrameTupleReference();
- RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, interiorFrame, leafFrame, metaFrame,
+ RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, leafFrame, interiorFrame, metaFrame,
"unittest");
Random rnd = new Random();
@@ -171,7 +163,7 @@
}
IRTreeCursor searchCursor = new SearchCursor(interiorFrame, leafFrame);
- RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, interiorFrame, leafFrame, metaFrame,
+ RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame,
"cursortest");
rtree.search(searchCursor, tuple, searchOpCtx);