Fixed a bug (reported by Zack) in the r-tree insert method. The issue turned out to occur when all the objects residing inside an MBR are points that are aligned exactly on the same line causing the area of that MBR to be exactly zero which makes the r-tree think that it does not need to enlarge the MBR if a new object (to be inserted into this node) is also aligned with the MBR line but it does not fall on it.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@2679 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeInteriorFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeInteriorFrame.java
index 9e40208..59c047c 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeInteriorFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeInteriorFrame.java
@@ -22,9 +22,9 @@
public interface IRTreeInteriorFrame extends IRTreeFrame {
- public boolean findBestChild(ITupleReference tuple, MultiComparator cmp);
+ public int findBestChild(ITupleReference tuple, MultiComparator cmp);
- public int getBestChildPageId();
+ public boolean checkIfEnlarementIsNeeded(ITupleReference tuple, MultiComparator cmp);
public int getChildPageId(int tupleIndex);
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreePolicy.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreePolicy.java
index b1d026a..a0cc5e8 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreePolicy.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreePolicy.java
@@ -28,6 +28,6 @@
public void split(ITreeIndexFrame leftFrame, ByteBuffer buf, ITreeIndexFrame rightFrame, ISlotManager slotManager,
ITreeIndexTupleReference frameTuple, ITupleReference tuple, ISplitKey splitKey);
- public boolean findBestChild(ITreeIndexFrame frame, ITupleReference tuple, ITreeIndexTupleReference frameTuple,
+ public int findBestChildPosition(ITreeIndexFrame frame, ITupleReference tuple, ITreeIndexTupleReference frameTuple,
MultiComparator cmp);
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RStarTreePolicy.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RStarTreePolicy.java
index 3341ace..aafecd5 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RStarTreePolicy.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RStarTreePolicy.java
@@ -64,6 +64,7 @@
}
}
+ @Override
public void split(ITreeIndexFrame leftFrame, ByteBuffer buf, ITreeIndexFrame rightFrame, ISlotManager slotManager,
ITreeIndexTupleReference frameTuple, ITupleReference tuple, ISplitKey splitKey) {
RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
@@ -252,7 +253,8 @@
}
}
- public boolean findBestChild(ITreeIndexFrame frame, ITupleReference tuple, ITreeIndexTupleReference frameTuple,
+ @Override
+ public int findBestChildPosition(ITreeIndexFrame frame, ITupleReference tuple, ITreeIndexTupleReference frameTuple,
MultiComparator cmp) {
cmpFrameTuple.setFieldCount(cmp.getKeyFieldCount());
frameTuple.setFieldCount(cmp.getKeyFieldCount());
@@ -347,11 +349,6 @@
}
tupleEntries1.clear();
- frameTuple.resetByTupleIndex(frame, bestChild);
- if (minEnlargedArea > 0.0) {
- return true;
- } else {
- return false;
- }
+ return bestChild;
}
}
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeComputationUtils.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeComputationUtils.java
index 475dc6f..f0122b3 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeComputationUtils.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeComputationUtils.java
@@ -113,4 +113,25 @@
return area;
}
+ public static boolean containsRegion(ITupleReference tuple1, ITupleReference tuple2, MultiComparator cmp,
+ IPrimitiveValueProvider[] keyValueProviders) {
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ int c = cmp.getComparators()[i]
+ .compare(tuple1.getFieldData(i), tuple1.getFieldStart(i), tuple1.getFieldLength(i),
+ tuple2.getFieldData(i), tuple2.getFieldStart(i), tuple2.getFieldLength(i));
+ if (c > 0) {
+ return false;
+ }
+
+ c = cmp.getComparators()[j]
+ .compare(tuple1.getFieldData(j), tuple1.getFieldStart(j), tuple1.getFieldLength(j),
+ tuple2.getFieldData(j), tuple2.getFieldStart(j), tuple2.getFieldLength(j));
+ if (c < 0) {
+ return false;
+ }
+ }
+ return true;
+ }
}
\ 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 954a3bb..5ab9632 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
@@ -48,8 +48,16 @@
}
@Override
- public boolean findBestChild(ITupleReference tuple, MultiComparator cmp) {
- return rtreePolicy.findBestChild(this, tuple, frameTuple, cmp);
+ public int findBestChild(ITupleReference tuple, MultiComparator cmp) {
+ int bestChild = rtreePolicy.findBestChildPosition(this, tuple, frameTuple, cmp);
+ frameTuple.resetByTupleIndex(this, bestChild);
+ return buf.getInt(getChildPointerOff(frameTuple));
+ }
+
+ // frameTuple is assumed to have the tuple to be tested against.
+ @Override
+ public boolean checkIfEnlarementIsNeeded(ITupleReference tuple, MultiComparator cmp) {
+ return !RTreeComputationUtils.containsRegion(frameTuple, tuple, cmp, keyValueProviders);
}
@Override
@@ -60,11 +68,6 @@
}
@Override
- public int getBestChildPageId() {
- return buf.getInt(getChildPointerOff(frameTuple));
- }
-
- @Override
public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp) {
frameTuple.setFieldCount(cmp.getKeyFieldCount());
for (int i = 0; i < getTupleCount(); i++) {
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreePolicy.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreePolicy.java
index 1d76b0e..9d94794 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreePolicy.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreePolicy.java
@@ -55,6 +55,7 @@
}
}
+ @Override
public void split(ITreeIndexFrame leftFrame, ByteBuffer buf, ITreeIndexFrame rightFrame, ISlotManager slotManager,
ITreeIndexTupleReference frameTuple, ITupleReference tuple, ISplitKey splitKey) {
RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
@@ -199,7 +200,8 @@
rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
}
- public boolean findBestChild(ITreeIndexFrame frame, ITupleReference tuple, ITreeIndexTupleReference frameTuple,
+ @Override
+ public int findBestChildPosition(ITreeIndexFrame frame, ITupleReference tuple, ITreeIndexTupleReference frameTuple,
MultiComparator cmp) {
cmpFrameTuple.setFieldCount(cmp.getKeyFieldCount());
frameTuple.setFieldCount(cmp.getKeyFieldCount());
@@ -224,12 +226,7 @@
}
}
- frameTuple.resetByTupleIndex(frame, bestChild);
- if (minEnlargedArea > 0.0) {
- return true;
- } else {
- return false;
- }
+ return bestChild;
}
}
\ 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 e39ab50..773d593 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
@@ -255,9 +255,9 @@
ctx.pathList.add(pageId, pageLsn, -1);
if (!isLeaf) {
- // findBestChild must be called *before* getBestChildPageId
- boolean enlarementIsNeeded = ctx.interiorFrame.findBestChild(ctx.getTuple(), ctx.cmp);
- int childPageId = ctx.interiorFrame.getBestChildPageId();
+ // findBestChild must be called *before* checkIfEnlarementIsNeeded
+ int childPageId = ctx.interiorFrame.findBestChild(ctx.getTuple(), ctx.cmp);
+ boolean enlarementIsNeeded = ctx.interiorFrame.checkIfEnlarementIsNeeded(ctx.getTuple(), ctx.cmp);
if (enlarementIsNeeded) {
if (!writeLatched) {