- Started to add support for delete operation
- Bug fixes
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_indexes@409 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 9d60464..5e766c5 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
@@ -5,14 +5,24 @@
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.FindPathList;
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 boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
- public int findTuple(ITupleReference tuple, FindPathList findPathList, int parentId, 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 findTuple(ITupleReference tuple, MultiComparator cmp);
public int getPageNsn();
@@ -25,19 +35,15 @@
public int getBestChildPageId(MultiComparator cmp);
- public boolean checkEnlargement(ITupleReference tuple, TupleEntryArrayList entries,
- ITreeIndexTupleReference[] nodesMBRs, MultiComparator cmp);
+ public boolean findBestChild(ITupleReference tuple, TupleEntryArrayList entries, MultiComparator cmp);
- public void adjustNodeMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp);
+ public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp);
- public void adjustKey(ITupleReference tuple, 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 void reinsert(ITupleReference tuple, ITreeIndexTupleReference nodeMBR, TupleEntryArrayList entries,
- ISplitKey splitKey, MultiComparator cmp) throws Exception;
-
public Rectangle intersect(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 7d0e886..d414073 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
@@ -10,13 +10,16 @@
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
import edu.uci.ics.hyracks.storage.am.common.frames.TreeIndexNSMFrame;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleMode;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.FindTupleNoExactMatchPolicy;
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.impls.EntriesOrder;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.FindPathList;
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.TraverseList;
import edu.uci.ics.hyracks.storage.am.rtree.impls.TupleEntryArrayList;
import edu.uci.ics.hyracks.storage.am.rtree.impls.UnorderedSlotManager;
import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriter;
@@ -29,7 +32,6 @@
private ITreeIndexTupleReference cmpFrameTuple;
- private static final double reinsertFactor = 0.3;
private static final double splitFactor = 0.4;
private static final int nearMinimumOverlapFactor = 32;
@@ -102,82 +104,6 @@
return ret;
}
- // @Override
- // public int split(ITreeIndexFrame rightFrame, ITupleReference tuple,
- // MultiComparator cmp, ISplitKey splitKey)
- // throws Exception {
- //
- // RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
- // RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame =
- // ((RTreeTypeAwareTupleWriter) tupleWriter);
- // RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame =
- // ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
- // frameTuple.setFieldCount(cmp.getFieldCount());
- // rightFrame.setPageTupleFieldCount(cmp.getFieldCount());
- //
- // ByteBuffer right = rightFrame.getBuffer();
- // int tupleCount = getTupleCount();
- //
- // int tuplesToLeft;
- // int mid = tupleCount / 2;
- // ITreeIndexFrame targetFrame = null;
- // int tupleOff = slotManager.getTupleOff(slotManager.getSlotOff(mid));
- // frameTuple.resetByTupleOffset(buf, tupleOff);
- // if (cmp.compare(tuple, frameTuple) >= 0) {
- // tuplesToLeft = mid + (tupleCount % 2);
- // targetFrame = rightFrame;
- // } else {
- // tuplesToLeft = mid;
- // targetFrame = this;
- // }
- // int tuplesToRight = tupleCount - tuplesToLeft;
- //
- // // copy entire page
- // System.arraycopy(buf.array(), 0, right.array(), 0, buf.capacity());
- //
- // // on right page we need to copy rightmost slots to left
- // int src = rightFrame.getSlotManager().getSlotEndOff();
- // int dest = rightFrame.getSlotManager().getSlotEndOff() + tuplesToLeft
- // * rightFrame.getSlotManager().getSlotSize();
- // int length = rightFrame.getSlotManager().getSlotSize() * tuplesToRight;
- // System.arraycopy(right.array(), src, right.array(), dest, length);
- // right.putInt(tupleCountOff, tuplesToRight);
- //
- // // on left page only change the tupleCount indicator
- // buf.putInt(tupleCountOff, tuplesToLeft);
- //
- // // compact both pages
- // rightFrame.compact(cmp);
- // compact(cmp);
- //
- // // insert last key
- // targetFrame.insert(tuple, cmp);
- //
- // // set split key to be highest value in left page
- // // TODO: find a better way to find the key size
- // tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
- // frameTuple.resetByTupleOffset(buf, tupleOff);
- //
- // int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0,
- // cmp.getKeyFieldCount());
- // splitKey.initData(splitKeySize);
- // this.adjustNodeMBR(tuples, cmp);
- // rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0,
- // rTreeSplitKey.getLeftPageBuffer(), 0);
- // rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(),
- // 0);
- //
- // ((IRTreeFrame) rightFrame).adjustNodeMBR(((NSMRTreeFrame)
- // rightFrame).getTuples(), cmp);
- // rTreeTupleWriterRightFrame.writeTupleFields(((NSMRTreeFrame)
- // rightFrame).getTuples(), 0,
- // rTreeSplitKey.getRightPageBuffer(), 0);
- // rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(),
- // 0);
- //
- // return 0;
- // }
-
@Override
public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception {
@@ -237,13 +163,13 @@
// int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0,
// cmp.getKeyFieldCount());
// splitKey.initData(splitKeySize);
- // this.adjustNodeMBR(tuples, cmp);
+ // this.adjustMBR(tuples, cmp);
// rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0,
// rTreeSplitKey.getLeftPageBuffer(), 0);
// rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(),
// 0);
//
- // ((IRTreeFrame) rightFrame).adjustNodeMBR(((NSMRTreeFrame)
+ // ((IRTreeFrame) rightFrame).adjustMBR(((NSMRTreeFrame)
// rightFrame).getTuples(), cmp);
// rTreeTupleWriterRightFrame.writeTupleFields(((NSMRTreeFrame)
// rightFrame).getTuples(), 0,
@@ -258,7 +184,6 @@
RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
rightFrame.setPageTupleFieldCount(cmp.getFieldCount());
frameTuple.setFieldCount(cmp.getFieldCount());
- cmpFrameTuple.setFieldCount(cmp.getFieldCount());
// calculations are based on the R*-tree paper
int m = (int) Math.floor((getTupleCount() + 1) * splitFactor);
@@ -397,11 +322,11 @@
int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
splitKey.initData(splitKeySize);
- this.adjustNodeMBR(tuples, cmp);
+ this.adjustMBR(tuples, cmp);
rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
- ((IRTreeFrame) rightFrame).adjustNodeMBR(((NSMRTreeFrame) rightFrame).getTuples(), cmp);
+ ((IRTreeFrame) rightFrame).adjustMBR(((NSMRTreeFrame) rightFrame).getTuples(), cmp);
rTreeTupleWriterRightFrame.writeTupleFields(((NSMRTreeFrame) rightFrame).getTuples(), 0,
rTreeSplitKey.getRightPageBuffer(), 0);
rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
@@ -444,9 +369,7 @@
}
@Override
- public boolean checkEnlargement(ITupleReference tuple, TupleEntryArrayList entries,
- ITreeIndexTupleReference[] nodesMBRs, MultiComparator cmp) {
-
+ public boolean findBestChild(ITupleReference tuple, TupleEntryArrayList entries, MultiComparator cmp) {
cmpFrameTuple.setFieldCount(cmp.getFieldCount());
frameTuple.setFieldCount(cmp.getFieldCount());
@@ -544,195 +467,9 @@
frameTuple.resetByTupleIndex(this, bestChild);
if (minEnlargedArea > 0.0) {
return true;
- // enlarge(frameTuple, tuple, cmp);
} else {
return false;
}
-
- // nodesMBRs[(int) getLevel() - 1].resetByTupleIndex(this, bestChild);
-
- // return the page id of the bestChild tuple
- // return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
- }
-
- // @Override
- // public int getChildPageId(ITupleReference tuple, TupleEntryArrayList
- // entries, ITreeIndexTupleReference[] nodesMBRs,
- // MultiComparator cmp) {
- //
- // cmpFrameTuple.setFieldCount(cmp.getFieldCount());
- // frameTuple.setFieldCount(cmp.getFieldCount());
- //
- // int bestChild = 0;
- // double minEnlargedArea = Double.MAX_VALUE;
- //
- // // the children pointers in the node point to leaves
- // if (getLevel() == 1) {
- // // find least overlap enlargement, use minimum enlarged area to
- // // break tie, if tie still exists use minimum area to break it
- // for (int i = 0; i < getTupleCount(); ++i) {
- // frameTuple.resetByTupleIndex(this, i);
- // double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
- // entries.add(i, enlargedArea);
- // if (enlargedArea < minEnlargedArea) {
- // minEnlargedArea = enlargedArea;
- // bestChild = i;
- // }
- // }
- // if (minEnlargedArea < entries.getDoubleEpsilon() || minEnlargedArea >
- // entries.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());
- // k = nearMinimumOverlapFactor;
- // } else {
- // k = getTupleCount();
- // }
- //
- // double minOverlap = Double.MAX_VALUE;
- // int id = 0;
- // for (int i = 0; i < k; ++i) {
- // double difference = 0.0;
- // for (int j = 0; j < getTupleCount(); ++j) {
- // frameTuple.resetByTupleIndex(this, j);
- // cmpFrameTuple.resetByTupleIndex(this, entries.get(i).getTupleIndex());
- //
- // int c =
- // cmp.getIntCmp().compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
- // frameTuple.getFieldStart(cmp.getKeyFieldCount()),
- // frameTuple.getFieldLength(cmp.getKeyFieldCount()),
- // cmpFrameTuple.getFieldData(cmp.getKeyFieldCount()),
- // cmpFrameTuple.getFieldStart(cmp.getKeyFieldCount()),
- // cmpFrameTuple.getFieldLength(cmp.getKeyFieldCount()));
- // if (c != 0) {
- // double intersection = overlappedArea(frameTuple, tuple, cmpFrameTuple,
- // cmp);
- // if (intersection != 0.0) {
- // difference += intersection - overlappedArea(frameTuple, null,
- // cmpFrameTuple, cmp);
- // }
- // } else {
- // id = j;
- // }
- // }
- //
- // double enlargedArea = enlargedArea(cmpFrameTuple, tuple, cmp);
- // if (difference < minOverlap) {
- // minOverlap = difference;
- // minEnlargedArea = enlargedArea;
- // bestChild = id;
- // } else if (difference == minOverlap) {
- // if (enlargedArea < minEnlargedArea) {
- // minEnlargedArea = enlargedArea;
- // bestChild = id;
- // } else if (enlargedArea == minEnlargedArea) {
- // double area = area(cmpFrameTuple, cmp);
- // frameTuple.resetByTupleIndex(this, bestChild);
- // double minArea = area(frameTuple, cmp);
- // if (area < minArea) {
- // bestChild = id;
- // }
- // }
- // }
- // }
- // }
- // } else { // find minimum enlarged area, use minimum area to break tie
- // for (int i = 0; i < getTupleCount(); i++) {
- // frameTuple.resetByTupleIndex(this, i);
- // double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
- // if (enlargedArea < minEnlargedArea) {
- // minEnlargedArea = enlargedArea;
- // bestChild = i;
- // } else if (enlargedArea == minEnlargedArea) {
- // double area = area(frameTuple, cmp);
- // frameTuple.resetByTupleIndex(this, bestChild);
- // double minArea = area(frameTuple, cmp);
- // if (area < minArea) {
- // bestChild = i;
- // }
- // }
- // }
- // }
- // frameTuple.resetByTupleIndex(this, bestChild);
- // nodesMBRs[(int) getLevel() - 1].resetByTupleIndex(this, bestChild);
- //
- // entries.clear();
- //
- // // return the page id of the bestChild tuple
- // return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
- // }
-
- @Override
- public void reinsert(ITupleReference tuple, ITreeIndexTupleReference nodeMBR, TupleEntryArrayList entries,
- ISplitKey splitKey, MultiComparator cmp) throws Exception {
-
- nodeMBR.setFieldCount(cmp.getFieldCount());
- int maxFieldPos = cmp.getKeyFieldCount() / 2;
- for (int i = 0; i < getTupleCount() + 1; ++i) {
- if (i < getTupleCount()) {
- frameTuple.resetByTupleIndex(this, i);
- }
- double centerDistance = 0.0;
- for (int j = 0; j < maxFieldPos; j++) {
- int k = maxFieldPos + j;
-
- // TODO: an optimization can be done here, compute nodeCenter
- // only once and reuse it
- double nodeCenter = (DoubleSerializerDeserializer.getDouble(nodeMBR.getFieldData(j),
- nodeMBR.getFieldStart(j)) + DoubleSerializerDeserializer.getDouble(nodeMBR.getFieldData(k),
- nodeMBR.getFieldStart(k))) / 2.0;
-
- double childCenter;
- if (i < getTupleCount()) {
- childCenter = (DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(j),
- frameTuple.getFieldStart(j)) + DoubleSerializerDeserializer.getDouble(
- frameTuple.getFieldData(k), frameTuple.getFieldStart(k))) / 2.0;
- } else { // special case to deal with the new tuple to be
- // inserted
- childCenter = (DoubleSerializerDeserializer
- .getDouble(tuple.getFieldData(j), tuple.getFieldStart(j)) + DoubleSerializerDeserializer
- .getDouble(tuple.getFieldData(k), tuple.getFieldStart(k))) / 2.0;
- }
-
- double d = childCenter - nodeCenter;
- centerDistance += d * d;
- }
- if (i < getTupleCount()) {
- entries.add(i, centerDistance);
- } else { // special case to deal with the new tuple to be inserted
- entries.add(-1, centerDistance);
- }
-
- }
- entries.sort(EntriesOrder.DESCENDING, getTupleCount() + 1);
-
- int j = (int) Math.floor((getTupleCount() + 1) * reinsertFactor);
- for (int i = 0; i < j; i++) {
- if (entries.get(i).getTupleIndex() != -1) {
- frameTuple.resetByTupleIndex(this, i);
- delete(frameTuple, cmp, false);
- } else {
- delete(tuple, cmp, false);
- }
-
- }
-
- // rebuild the node's MBR
- RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
- RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
- this.adjustNodeMBR(tuples, cmp);
-
- int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
- frameTuple.resetByTupleOffset(buf, tupleOff);
- int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
- rTreeSplitKey.initData(splitKeySize);
-
- rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
-
- entries.clear();
}
private double area(ITupleReference tuple, MultiComparator cmp) {
@@ -849,9 +586,11 @@
}
@Override
- public void adjustKey(ITupleReference tuple, MultiComparator cmp) {
+ public void adjustKey(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
frameTuple.setFieldCount(cmp.getFieldCount());
- int tupleIndex = findTuple(tuple, cmp);
+ if (tupleIndex == -1) {
+ tupleIndex = findTupleByPointer(tuple, cmp);
+ }
if (tupleIndex != -1) {
tupleWriter.writeTuple(tuple, buf, getTupleOffset(tupleIndex));
}
@@ -860,6 +599,63 @@
@Override
public int findTuple(ITupleReference tuple, MultiComparator cmp) {
frameTuple.setFieldCount(cmp.getFieldCount());
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < getTupleCount(); i++) {
+ frameTuple.resetByTupleIndex(this, i);
+
+ for (int j = 0; j < maxFieldPos; j++) {
+ int k = maxFieldPos + j;
+ int c1 = cmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+ frameTuple.getFieldLength(j), tuple.getFieldData(j), tuple.getFieldStart(j),
+ tuple.getFieldLength(j));
+
+ int c2 = cmp.getComparators()[k].compare(frameTuple.getFieldData(k), frameTuple.getFieldStart(k),
+ frameTuple.getFieldLength(k), tuple.getFieldData(k), tuple.getFieldStart(k),
+ tuple.getFieldLength(k));
+ if (c1 == 0 && c2 == 0) {
+ return i;
+ }
+ }
+ }
+ return -1;
+ }
+
+ @Override
+ public void delete(int tupleIndex, MultiComparator cmp) throws Exception {
+ frameTuple.setFieldCount(cmp.getFieldCount());
+ int slotOff = slotManager.getSlotOff(tupleIndex);
+
+ int tupleOff = slotManager.getTupleOff(slotOff);
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+ int tupleSize = tupleWriter.bytesRequired(frameTuple);
+
+ // perform deletion (we just do a memcpy to overwrite the slot)
+ int slotStartOff = slotManager.getSlotEndOff();
+ int length = slotOff - slotStartOff;
+ System.arraycopy(buf.array(), slotStartOff, buf.array(), slotStartOff + slotManager.getSlotSize(), length);
+
+ // maintain space information
+ buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + tupleSize + slotManager.getSlotSize());
+ }
+
+ @Override
+ public int findTupleByPointer(int pageId, MultiComparator cmp) {
+ frameTuple.setFieldCount(cmp.getFieldCount());
+ for (int i = 0; i < getTupleCount(); i++) {
+ frameTuple.resetByTupleIndex(this, i);
+ int id = IntegerSerializerDeserializer.getInt(frameTuple.getFieldData(cmp.getKeyFieldCount()),
+ frameTuple.getFieldStart(cmp.getKeyFieldCount()));
+ if (id == pageId) {
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ @Override
+ public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp) {
+ frameTuple.setFieldCount(cmp.getFieldCount());
for (int i = 0; i < getTupleCount(); i++) {
frameTuple.resetByTupleIndex(this, i);
int c = cmp.getIntCmp().compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
@@ -874,7 +670,7 @@
}
@Override
- public int findTuple(ITupleReference tuple, FindPathList findPathList, int parentIndex, MultiComparator cmp) {
+ public int findTupleByPointer(ITupleReference tuple, TraverseList traverseList, int parentIndex, MultiComparator cmp) {
frameTuple.setFieldCount(cmp.getFieldCount());
for (int i = 0; i < getTupleCount(); i++) {
frameTuple.resetByTupleIndex(this, i);
@@ -887,14 +683,14 @@
} else {
int pageId = IntegerSerializerDeserializer.getInt(frameTuple.getFieldData(cmp.getKeyFieldCount()),
frameTuple.getFieldStart(cmp.getKeyFieldCount()));
- findPathList.add(pageId, parentIndex);
+ traverseList.add(pageId, -1, parentIndex);
}
}
return -1;
}
@Override
- public void adjustNodeMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
+ public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
for (int i = 0; i < tuples.length; i++) {
tuples[i].setFieldCount(cmp.getKeyFieldCount());
tuples[i].resetByTupleIndex(this, 0);
@@ -975,4 +771,45 @@
// TODO Auto-generated method stub
return 0;
}
+
+ @Override
+ public void computeMBR(ISplitKey splitKey, MultiComparator cmp) {
+ RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
+ RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
+ frameTuple.setFieldCount(cmp.getFieldCount());
+
+ int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+ int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
+
+ splitKey.initData(splitKeySize);
+ this.adjustMBR(tuples, cmp);
+ rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
+ rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
+ }
+
+ @Override
+ public boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+ frameTuple.setFieldCount(cmp.getFieldCount());
+ frameTuple.resetByTupleIndex(this, tupleIndex);
+
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ int c = cmp.getComparators()[i].compare(frameTuple.getFieldData(i), frameTuple.getFieldStart(i),
+ frameTuple.getFieldLength(i), tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i));
+ if (c != 0) {
+ return true;
+ }
+ c = cmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+ frameTuple.getFieldLength(j), tuple.getFieldData(j), tuple.getFieldStart(j),
+ tuple.getFieldLength(j));
+
+ if (c != 0) {
+ return true;
+ }
+ }
+ return false;
+ }
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/FindPathList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/FindPathList.java
index 2522e17..83289e4 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/FindPathList.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/FindPathList.java
@@ -36,7 +36,7 @@
return size;
}
- public void add(int pageId, int parentId) {
+ public void add(int pageId, int parentIndex) {
if (size == pageIds.length) {
int[] newPageIds = new int[pageIds.length + growth];
System.arraycopy(pageIds, 0, newPageIds, 0, pageIds.length);
@@ -52,7 +52,7 @@
}
pageIds[size] = pageId;
- parentIndexes[size] = parentId;
+ parentIndexes[size] = parentIndex;
size++;
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java
index 1cc95d1..4be3b38 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java
@@ -18,17 +18,23 @@
public class IntArrayList {
private int[] data;
private int size;
+ private int first;
private final int growth;
public IntArrayList(int initialCapacity, int growth) {
data = new int[initialCapacity];
size = 0;
+ first = 0;
this.growth = growth;
}
public int size() {
return size;
}
+
+ public int first() {
+ return first;
+ }
public void add(int i) {
if (size == data.length) {
@@ -54,10 +60,29 @@
return data[i];
}
- public void clear() {
- size = 0;
+ // WARNING: caller is responsible for checking i < size
+ public void set(int i, int value) {
+ data[i] = value;
+
}
+ public int getFirst() {
+ return data[first];
+ }
+
+ public void moveFirst() {
+ first++;
+ }
+
+ public void clear() {
+ size = 0;
+ first = 0;
+ }
+
+ public boolean isLast() {
+ return size == first;
+ }
+
public boolean isEmpty() {
return size == 0;
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/PathList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/PathList.java
new file mode 100644
index 0000000..093bc8c
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/PathList.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+public class PathList {
+ private IntArrayList pageIds;
+ private IntArrayList pageLsns;
+ private IntArrayList pageIndexes;
+
+ public PathList(int initialCapacity, int growth) {
+ pageIds = new IntArrayList(initialCapacity, growth);
+ pageLsns = new IntArrayList(initialCapacity, growth);
+ pageIndexes = new IntArrayList(initialCapacity, growth);
+ }
+
+ public int size() {
+ return pageIds.size();
+ }
+
+ public void add(int pageId, int pageLsn, int pageIndex) {
+ pageIds.add(pageId);
+ pageLsns.add(pageLsn);
+ pageIndexes.add(pageIndex);
+ }
+
+ public int getLastPageId() {
+ return pageIds.getLast();
+ }
+
+ public int getLastPageLsn() {
+ return pageLsns.getLast();
+ }
+
+ public int getLastPageIndex() {
+ return pageIndexes.getLast();
+ }
+
+ public int getPageId(int i) {
+ return pageIds.get(i);
+ }
+
+ public int getPageLsn(int i) {
+ return pageLsns.get(i);
+ }
+
+ public int getPageIndex(int i) {
+ return pageIndexes.get(i);
+ }
+
+ public void removeLast() {
+ pageIds.removeLast();
+ pageLsns.removeLast();
+ pageIndexes.removeLast();
+ }
+
+ public void clear() {
+ pageIds.clear();
+ pageLsns.clear();
+ pageIndexes.clear();
+ }
+
+ public boolean isEmpty() {
+ return pageIds.isEmpty();
+ }
+}
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 534ca50..2815e48 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
@@ -3,6 +3,8 @@
import java.util.ArrayList;
import java.util.Stack;
import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
@@ -25,6 +27,7 @@
private final AtomicInteger globalNsn; // Global node sequence number
private int numOfPages = 1;
+ private final ReadWriteLock treeLatch;
private final IFreePageManager freePageManager;
private final IBufferCache bufferCache;
@@ -57,6 +60,7 @@
this.leafCmp = leafCmp;
this.dim = dim;
globalNsn = new AtomicInteger();
+ this.treeLatch = new ReentrantReadWriteLock(true);
}
public synchronized void incrementGlobalNsn() {
@@ -150,30 +154,35 @@
if (created)
return;
- // check if another thread beat us to it
- if (created)
- return;
-
- freePageManager.init(metaFrame, rootPage);
-
- // initialize root page
- ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), true);
- pins++;
-
- rootNode.acquireWriteLatch();
- writeLatchesAcquired++;
+ treeLatch.writeLock().lock();
try {
- leafFrame.setPage(rootNode);
- leafFrame.initBuffer((byte) 0);
- } finally {
- rootNode.releaseWriteLatch();
- writeLatchesReleased++;
- bufferCache.unpin(rootNode);
- unpins++;
- }
- currentLevel = 0;
+ // check if another thread beat us to it
+ if (created)
+ return;
- created = true;
+ freePageManager.init(metaFrame, rootPage);
+
+ // initialize root page
+ ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), true);
+ pins++;
+
+ rootNode.acquireWriteLatch();
+ writeLatchesAcquired++;
+ try {
+ leafFrame.setPage(rootNode);
+ leafFrame.initBuffer((byte) 0);
+ } finally {
+ rootNode.releaseWriteLatch();
+ writeLatchesReleased++;
+ bufferCache.unpin(rootNode);
+ unpins++;
+ }
+ currentLevel = 0;
+
+ created = true;
+ } finally {
+ treeLatch.writeLock().unlock();
+ }
}
public void open(int fileId) {
@@ -190,150 +199,6 @@
return new RTreeOpContext(op, interiorFrame, leafFrame, metaFrame, 8, dim);
}
- private void createNewRoot(RTreeOpContext ctx) throws Exception {
- rootSplits++; // debug
- splitsByLevel[currentLevel]++;
- currentLevel++;
-
- // make sure the root is always at the same level
- ICachedPage leftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, ctx.splitKey.getLeftPage()),
- false);
- pins++;
- leftNode.acquireWriteLatch(); // TODO: think about whether latching is
- // really required
- writeLatchesAcquired++;
- try {
- ICachedPage rightNode = bufferCache.pin(
- BufferedFileHandle.getDiskPageId(fileId, ctx.splitKey.getRightPage()), false);
- pins++;
- rightNode.acquireWriteLatch(); // TODO: think about whether latching
- // is really required
- writeLatchesAcquired++;
- try {
- int newLeftId = freePageManager.getFreePage(ctx.metaFrame);
- ICachedPage newLeftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, newLeftId), true);
- pins++;
- newLeftNode.acquireWriteLatch(); // TODO: think about whether
- // latching is really required
- writeLatchesAcquired++;
- try {
- // copy left child to new left child
- System.arraycopy(leftNode.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0, newLeftNode
- .getBuffer().capacity());
-
- // initialize new root (leftNode becomes new root)
- ctx.interiorFrame.setPage(leftNode);
- ctx.interiorFrame.initBuffer((byte) (ctx.interiorFrame.getLevel() + 1));
-
- ctx.splitKey.setLeftPage(newLeftId);
-
- ctx.interiorFrame.insert(ctx.splitKey.getLeftTuple(), interiorCmp);
- ctx.interiorFrame.insert(ctx.splitKey.getRightTuple(), interiorCmp);
- } finally {
- newLeftNode.releaseWriteLatch();
- writeLatchesReleased++;
- bufferCache.unpin(newLeftNode);
- unpins++;
- }
- } finally {
- rightNode.releaseWriteLatch();
- writeLatchesReleased++;
- bufferCache.unpin(rightNode);
- unpins++;
- }
- } finally {
- leftNode.releaseWriteLatch();
- writeLatchesReleased++;
- bufferCache.unpin(leftNode);
- unpins++;
- }
- }
-
- private final void acquireLatch(ICachedPage node, TreeIndexOp op, boolean isLeaf) {
- if (isLeaf && (op.equals(TreeIndexOp.TI_INSERT) || op.equals(TreeIndexOp.TI_DELETE))) {
- node.acquireWriteLatch();
- writeLatchesAcquired++;
- } else {
- node.acquireReadLatch();
- readLatchesAcquired++;
- }
- }
-
- // public void insert(ITupleReference tuple, RTreeOpContext ctx) throws
- // Exception {
- // ctx.reset();
- // ctx.setTuple(tuple);
- // ctx.splitKey.reset();
- // ctx.splitKey.getLeftTuple().setFieldCount(interiorCmp.getFieldCount());
- // ctx.splitKey.getRightTuple().setFieldCount(interiorCmp.getFieldCount());
- // ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
- // for (int i = 0; i < currentLevel; i++) {
- // ctx.overflowArray.add((byte) 0);
- // }
- // insertImpl(rootPage, null, (byte) 0, ctx);
- //
- // // we split the root, here is the key for a new root
- // if (ctx.splitKey.getLeftPageBuffer() != null) {
- // createNewRoot(ctx);
- // }
- // }
-
- // public void insertImpl(int pageId, ICachedPage parent, byte desiredLevel,
- // RTreeOpContext ctx) throws Exception {
- // ICachedPage node =
- // bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
- // pins++;
- // ctx.interiorFrame.setPage(node);
- // boolean isLeaf = ctx.interiorFrame.isLeaf();
- // acquireLatch(node, ctx.op, isLeaf);
- //
- // // latch coupling TODO: check the correctness of this
- // if (parent != null) {
- // parent.releaseReadLatch();
- // readLatchesReleased++;
- // bufferCache.unpin(parent);
- // unpins++;
- // }
- //
- // if (ctx.interiorFrame.getLevel() > desiredLevel) {
- // int childPageId = ctx.interiorFrame.checkEnlargement(ctx.getTuple(),
- // ctx.tupleEntries1, ctx.nodesMBRs,
- // interiorCmp);
- //
- // insertImpl(childPageId, node, desiredLevel, ctx);
- // if (ctx.splitKey.getLeftPageBuffer() != null) {
- // node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId),
- // false);
- // pins++;
- // node.acquireWriteLatch();
- // writeLatchesAcquired++;
- // try {
- // ctx.interiorFrame.setPage(node);
- // ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), interiorCmp);
- // insertTuple(pageId, ctx.splitKey.getRightTuple(), ctx, isLeaf);
- // } finally {
- // node.releaseWriteLatch();
- // writeLatchesReleased++;
- // bufferCache.unpin(node);
- // unpins++;
- // }
- // }
- // } else {
- // try {
- // if (isLeaf) {
- // ctx.leafFrame.setPage(node);
- // ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
- // }
- // insertTuple(pageId, ctx.getTuple(), ctx, isLeaf);
- // } finally {
- // node.releaseWriteLatch();
- // writeLatchesReleased++;
- // bufferCache.unpin(node);
- // unpins++;
- // }
- // }
- // }
-
public void insert(ITupleReference tuple, RTreeOpContext ctx) throws Exception {
ctx.reset();
ctx.setTuple(tuple);
@@ -341,20 +206,17 @@
ctx.splitKey.getLeftTuple().setFieldCount(interiorCmp.getFieldCount());
ctx.splitKey.getRightTuple().setFieldCount(interiorCmp.getFieldCount());
ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
- for (int i = 0; i < currentLevel; i++) {
- ctx.overflowArray.add((byte) 0);
- }
+ ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
ICachedPage leafNode = findLeaf(ctx);
- int pageId = ctx.path.getLast();
- ctx.path.removeLast();
- ctx.pageLsns.removeLast();
- insertTuple(leafNode, pageId, ctx.getTuple(), ctx, ctx.leafFrame.isLeaf());
+ int pageId = ctx.pathList.getLastPageId();
+ ctx.pathList.removeLast();
+ insertTuple(leafNode, pageId, ctx.getTuple(), ctx, true);
while (true) {
if (ctx.splitKey.getLeftPageBuffer() != null) {
- updateParent(ctx);
+ updateParentForInsert(ctx);
} else {
break;
}
@@ -366,113 +228,6 @@
unpins++;
}
- public void updateParent(RTreeOpContext ctx) throws Exception {
- int parentId = ctx.path.getLast();
- ICachedPage parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
- pins++;
- parentNode.acquireWriteLatch();
- writeLatchesAcquired++;
- ctx.interiorFrame.setPage(parentNode);
- boolean foundParent = true;
-
- if (ctx.interiorFrame.getPageLsn() != ctx.pageLsns.getLast()) {
- foundParent = false;
- while (true) {
- if (ctx.interiorFrame.findTuple(ctx.splitKey.getLeftTuple(), interiorCmp) != -1) {
- // found the parent
- foundParent = true;
- break;
- }
- int rightPage = ctx.interiorFrame.getRightPage();
- parentNode.releaseWriteLatch();
- writeLatchesReleased++;
- bufferCache.unpin(parentNode);
- unpins++;
-
- if (rightPage == -1) {
- break;
- }
-
- parentId = rightPage;
- parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
- pins++;
- parentNode.acquireWriteLatch();
- writeLatchesAcquired++;
- ctx.interiorFrame.setPage(parentNode);
- }
- }
- if (foundParent) {
- ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), interiorCmp);
- insertTuple(parentNode, parentId, ctx.splitKey.getRightTuple(), ctx, ctx.interiorFrame.isLeaf());
- ctx.path.removeLast();
- ctx.pageLsns.removeLast();
-
- parentNode.releaseWriteLatch();
- writeLatchesReleased++;
- bufferCache.unpin(parentNode);
- unpins++;
- return;
- }
-
- // very rare situation when the there is a root split, do an exhaustive
- // breadth-first traversal looking for the parent tuple
-
- ctx.path.clear();
- ctx.pageLsns.clear();
- ctx.findPathList.clear();
- findPath(ctx);
- updateParent(ctx);
- }
-
- public void findPath(RTreeOpContext ctx) throws Exception {
- int pageId = rootPage;
- int parentIndex = -1;
- int parentLsn = 0;
- int pageLsn, pageIndex;
- ctx.findPathList.add(pageId, parentIndex);
-
- while (!ctx.findPathList.isLast()) {
- pageId = ctx.findPathList.getFirstPageId();
- parentIndex = ctx.findPathList.getFirstParentIndex();
- ctx.findPathList.moveFirst();
- ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
- pins++;
- node.acquireReadLatch();
- readLatchesAcquired++;
- ctx.interiorFrame.setPage(node);
- pageLsn = ctx.interiorFrame.getPageLsn();
- pageIndex = ctx.findPathList.size() - 1;
- ctx.findPathList.setPageLsn(pageIndex, pageLsn);
-
- if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
- ctx.findPathList.add(ctx.interiorFrame.getRightPage(), parentIndex);
- }
- parentLsn = pageLsn;
-
- if (ctx.interiorFrame.findTuple(ctx.splitKey.getLeftTuple(), ctx.findPathList, pageIndex, interiorCmp) != -1) {
- fillPath(ctx, pageIndex);
-
- node.releaseReadLatch();
- readLatchesReleased++;
- bufferCache.unpin(node);
- unpins++;
- return;
- }
- node.releaseReadLatch();
- readLatchesReleased++;
- bufferCache.unpin(node);
- unpins++;
- }
- }
-
- public void fillPath(RTreeOpContext ctx, int pageIndex) throws Exception {
- if (pageIndex != -1) {
- fillPath(ctx, ctx.findPathList.getParentIndex(pageIndex));
- ctx.path.add(ctx.findPathList.getPageId(pageIndex));
- ctx.pageLsns.add(ctx.findPathList.getPageLsn(pageIndex));
- }
- }
-
public ICachedPage findLeaf(RTreeOpContext ctx) throws Exception {
int pageId = rootPage;
boolean writeLatched = false;
@@ -498,9 +253,8 @@
readLatchesAcquired++;
}
}
- ctx.path.add(pageId);
pageLsn = ctx.interiorFrame.getPageLsn();
- ctx.pageLsns.add(pageLsn);
+ ctx.pathList.add(pageId, pageLsn, -1);
if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
// Concurrent split detected, go back to parent and re-choose
@@ -517,17 +271,21 @@
unpins++;
}
- ctx.path.removeLast();
- ctx.pageLsns.removeLast();
+ ctx.pathList.removeLast();
+
+ pageId = ctx.pathList.getLastPageId();
+ if (pageId != rootPage) {
+ parentLsn = ctx.pathList.getPageLsn(ctx.pathList.size() - 2);
+ }
+
writeLatched = false;
continue;
}
- parentLsn = pageLsn;
if (!isLeaf) {
// checkEnlargement must be called *before* getBestChildPageId
- boolean needsEnlargement = ctx.interiorFrame.checkEnlargement(ctx.getTuple(), ctx.tupleEntries1,
- ctx.nodesMBRs, interiorCmp);
+ boolean needsEnlargement = ctx.interiorFrame.findBestChild(ctx.getTuple(), ctx.tupleEntries1,
+ interiorCmp);
int childPageId = ctx.interiorFrame.getBestChildPageId(interiorCmp);
if (needsEnlargement) {
@@ -547,7 +305,8 @@
if (ctx.interiorFrame.getPageLsn() != pageLsn) {
// The page was changed while we unlocked it; thus,
- // retry
+ // retry (re-choose best child)
+ ctx.pathList.removeLast();
continue;
}
}
@@ -568,16 +327,15 @@
unpins++;
}
pageId = childPageId;
+ parentLsn = pageLsn;
} else {
ctx.leafFrame.setPage(node);
- ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
return node;
}
}
-
}
- private void insertTuple(ICachedPage leafNode, int pageId, ITupleReference tuple, RTreeOpContext ctx, boolean isLeaf)
+ private void insertTuple(ICachedPage node, int pageId, ITupleReference tuple, RTreeOpContext ctx, boolean isLeaf)
throws Exception {
FrameOpSpaceStatus spaceStatus;
if (!isLeaf) {
@@ -618,21 +376,6 @@
writeLatchesAcquired++;
try {
- // if the level is not the root level and this is the
- // first overflow treatment in the given level during the
- // insertion of one data rectangle
- /*
- * if (ctx.overflowArray.get((int)
- * ctx.interiorFrame.getLevel()) == 0 && pageId != rootPage)
- * { if (!isLeaf) { ctx.overflowArray.set((int)
- * ctx.interiorFrame.getLevel(), (byte) 1);
- * ctx.interiorFrame.reinsert(tuple,
- * ctx.nodesMBRs[ctx.interiorFrame.getLevel()], ctx.entries,
- * ctx.splitKey, interiorCmp); } else {
- * ctx.overflowArray.set(0, (byte) 1);
- * ctx.leafFrame.reinsert(tuple, ctx.nodesMBRs[0],
- * ctx.entries, ctx.splitKey, leafCmp); } } else {
- */
IRTreeFrame rightFrame;
int ret;
numOfPages++; // debug
@@ -681,11 +424,11 @@
writeLatchesAcquired++;
try {
// copy left child to new left child
- System.arraycopy(leafNode.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0,
+ System.arraycopy(node.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0,
newLeftNode.getBuffer().capacity());
// initialize new root (leftNode becomes new root)
- ctx.interiorFrame.setPage(leafNode);
+ ctx.interiorFrame.setPage(node);
ctx.interiorFrame.initBuffer((byte) (ctx.interiorFrame.getLevel() + 1));
ctx.splitKey.setLeftPage(newLeftId);
@@ -714,6 +457,308 @@
}
}
+ public void updateParentForInsert(RTreeOpContext ctx) throws Exception {
+ int parentId = ctx.pathList.getLastPageId();
+ ICachedPage parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
+ pins++;
+ parentNode.acquireWriteLatch();
+ writeLatchesAcquired++;
+ ctx.interiorFrame.setPage(parentNode);
+ boolean foundParent = true;
+
+ if (ctx.interiorFrame.getPageLsn() != ctx.pathList.getLastPageLsn()) {
+ foundParent = false;
+ while (true) {
+ if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), interiorCmp) != -1) {
+ // found the parent
+ foundParent = true;
+ break;
+ }
+ int rightPage = ctx.interiorFrame.getRightPage();
+ parentNode.releaseWriteLatch();
+ writeLatchesReleased++;
+ bufferCache.unpin(parentNode);
+ unpins++;
+
+ if (rightPage == -1) {
+ break;
+ }
+
+ parentId = rightPage;
+ parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
+ pins++;
+ parentNode.acquireWriteLatch();
+ writeLatchesAcquired++;
+ ctx.interiorFrame.setPage(parentNode);
+ }
+ }
+ if (foundParent) {
+ ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), -1, interiorCmp);
+ insertTuple(parentNode, parentId, ctx.splitKey.getRightTuple(), ctx, ctx.interiorFrame.isLeaf());
+ ctx.pathList.removeLast();
+
+ parentNode.releaseWriteLatch();
+ writeLatchesReleased++;
+ bufferCache.unpin(parentNode);
+ unpins++;
+ return;
+ }
+
+ // very rare situation when the there is a root split, do an exhaustive
+ // breadth-first traversal looking for the parent tuple
+
+ ctx.pathList.clear();
+ ctx.traverseList.clear();
+ findPath(ctx);
+ updateParentForInsert(ctx);
+ }
+
+ public void findPath(RTreeOpContext ctx) throws Exception {
+ int pageId = rootPage;
+ int parentIndex = -1;
+ int parentLsn = 0;
+ int pageLsn, pageIndex;
+ ctx.traverseList.add(pageId, -1, parentIndex);
+ while (!ctx.traverseList.isLast()) {
+ pageId = ctx.traverseList.getFirstPageId();
+ parentIndex = ctx.traverseList.getFirstParentIndex();
+
+ ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ pins++;
+ node.acquireReadLatch();
+ readLatchesAcquired++;
+ ctx.interiorFrame.setPage(node);
+ pageLsn = ctx.interiorFrame.getPageLsn();
+ pageIndex = ctx.traverseList.first();
+ ctx.traverseList.setPageLsn(pageIndex, pageLsn);
+
+ ctx.traverseList.moveFirst();
+
+ if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
+ int rightPage = ctx.interiorFrame.getRightPage();
+ if (rightPage != -1) {
+ ctx.traverseList.add(rightPage, -1, parentIndex);
+ }
+ }
+ parentLsn = pageLsn;
+
+ if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), ctx.traverseList, pageIndex,
+ interiorCmp) != -1) {
+ fillPath(ctx, pageIndex);
+
+ node.releaseReadLatch();
+ readLatchesReleased++;
+ bufferCache.unpin(node);
+ unpins++;
+ return;
+ }
+ node.releaseReadLatch();
+ readLatchesReleased++;
+ bufferCache.unpin(node);
+ unpins++;
+ }
+ }
+
+ public void fillPath(RTreeOpContext ctx, int pageIndex) throws Exception {
+ if (pageIndex != -1) {
+ fillPath(ctx, ctx.traverseList.getParentIndex(pageIndex));
+ ctx.pathList.add(ctx.traverseList.getPageId(pageIndex), ctx.traverseList.getPageLsn(pageIndex), -1);
+ }
+ }
+
+ public void delete(ITupleReference tuple, RTreeOpContext ctx) throws Exception {
+ ctx.reset();
+ ctx.setTuple(tuple);
+ ctx.splitKey.reset();
+ ctx.splitKey.getLeftTuple().setFieldCount(interiorCmp.getFieldCount());
+ ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
+ ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
+
+ int tupleIndex = findTupleToDelete(ctx);
+
+ if (tupleIndex != -1) {
+ int pageId = ctx.pathList.getLastPageId();
+ ctx.pathList.removeLast();
+ deleteTuple(pageId, tupleIndex, ctx);
+
+ while (true) {
+ if (ctx.splitKey.getLeftPageBuffer() != null) {
+ updateParentForDelete(ctx);
+ } else {
+ break;
+ }
+ }
+
+ ctx.leafFrame.getPage().releaseWriteLatch();
+ writeLatchesReleased++;
+ bufferCache.unpin(ctx.leafFrame.getPage());
+ unpins++;
+ }
+ }
+
+ public void updateParentForDelete(RTreeOpContext ctx) throws Exception {
+ int parentId = ctx.pathList.getLastPageId();
+ ICachedPage parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
+ pins++;
+ parentNode.acquireWriteLatch();
+ writeLatchesAcquired++;
+ ctx.interiorFrame.setPage(parentNode);
+ boolean foundParent = true;
+ int tupleIndex = -1;
+
+ if (ctx.interiorFrame.getPageLsn() != ctx.pathList.getLastPageLsn()) {
+ foundParent = false;
+ while (true) {
+ tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), interiorCmp);
+ if (tupleIndex != -1) {
+ // found the parent
+ foundParent = true;
+ break;
+ }
+ int rightPage = ctx.interiorFrame.getRightPage();
+ parentNode.releaseWriteLatch();
+ writeLatchesReleased++;
+ bufferCache.unpin(parentNode);
+ unpins++;
+
+ if (rightPage == -1) {
+ break;
+ }
+
+ parentId = rightPage;
+ parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
+ pins++;
+ parentNode.acquireWriteLatch();
+ writeLatchesAcquired++;
+ ctx.interiorFrame.setPage(parentNode);
+ }
+ }
+ if (foundParent) {
+ if (tupleIndex == -1) {
+ tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), interiorCmp);
+ }
+ boolean recomputeMBR = ctx.interiorFrame.recomputeMBR(ctx.splitKey.getLeftTuple(), tupleIndex, interiorCmp);
+
+
+ if (recomputeMBR) {
+ ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), tupleIndex, interiorCmp);
+ ctx.pathList.removeLast();
+
+ ctx.splitKey.reset();
+ if (!ctx.pathList.isEmpty()) {
+ ctx.interiorFrame.computeMBR(ctx.splitKey, interiorCmp);
+ ctx.splitKey.setLeftPage(parentId);
+ }
+ } else {
+ ctx.pathList.removeLast();
+ ctx.splitKey.reset();
+ }
+
+ parentNode.releaseWriteLatch();
+ writeLatchesReleased++;
+ bufferCache.unpin(parentNode);
+ unpins++;
+ return;
+ }
+
+ // very rare situation when the there is a root split, do an exhaustive
+ // breadth-first traversal looking for the parent tuple
+
+ ctx.pathList.clear();
+ ctx.traverseList.clear();
+ findPath(ctx);
+ updateParentForDelete(ctx);
+ }
+
+ public int findTupleToDelete(RTreeOpContext ctx) throws Exception {
+
+ ctx.traverseList.add(rootPage, -1, -1);
+ ctx.pathList.add(rootPage, -1, ctx.traverseList.size() - 1);
+
+ while (!ctx.pathList.isEmpty()) {
+ int pageId = ctx.pathList.getLastPageId();
+ int parentLsn = ctx.pathList.getLastPageLsn();
+ int pageIndex = ctx.pathList.getLastPageIndex();
+ ctx.pathList.removeLast();
+ ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ pins++;
+ node.acquireReadLatch();
+ readLatchesAcquired++;
+ ctx.interiorFrame.setPage(node);
+ boolean isLeaf = ctx.interiorFrame.isLeaf();
+ int pageLsn = ctx.interiorFrame.getPageLsn();
+ int parentIndex = ctx.traverseList.getParentIndex(pageIndex);
+
+ if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
+ // Concurrent split detected, we need to visit the right page
+ int rightPage = ctx.interiorFrame.getRightPage();
+ if (rightPage != -1) {
+ ctx.traverseList.add(rightPage, parentLsn, parentIndex);
+ ctx.pathList.add(rightPage, parentLsn, ctx.traverseList.size() - 1);
+ }
+ }
+
+ if (!isLeaf) {
+ parentLsn = pageLsn;
+ for (int i = 0; i < ctx.interiorFrame.getTupleCount(); i++) {
+ int childPageId = ctx.interiorFrame.getChildPageIdIfIntersect(ctx.tuple, i, interiorCmp);
+ if (childPageId != -1) {
+ ctx.traverseList.add(childPageId, parentLsn, pageIndex);
+ ctx.pathList.add(childPageId, parentLsn, ctx.traverseList.size() - 1);
+ }
+ }
+ } else {
+ ctx.leafFrame.setPage(node);
+ int tupleIndex = ctx.leafFrame.findTuple(ctx.tuple, leafCmp);
+ if (tupleIndex != -1) {
+
+ node.releaseReadLatch();
+ readLatchesReleased++;
+ bufferCache.unpin(node);
+ unpins++;
+
+ node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ pins++;
+ node.acquireWriteLatch();
+ writeLatchesAcquired++;
+ ctx.leafFrame.setPage(node);
+
+ if (ctx.leafFrame.getPageLsn() != pageLsn) {
+ // The page was changed while we unlocked it
+
+ tupleIndex = ctx.leafFrame.findTuple(ctx.tuple, leafCmp);
+ if (tupleIndex == -1) {
+ ctx.traverseList.add(pageId, parentLsn, parentIndex);
+ ctx.pathList.add(pageId, parentLsn, ctx.traverseList.size() - 1);
+ }
+ } else {
+ ctx.pathList.clear();
+ fillPath(ctx, pageIndex);
+ return tupleIndex;
+ }
+ }
+ }
+ node.releaseReadLatch();
+ readLatchesReleased++;
+ bufferCache.unpin(node);
+ unpins++;
+ }
+ return -1;
+ }
+
+ public void deleteTuple(int pageId, int tupleIndex, RTreeOpContext ctx) throws Exception {
+
+ if (ctx.leafFrame.getTupleCount() == 1) {
+
+ } else {
+
+ ctx.leafFrame.delete(tupleIndex, leafCmp);
+ ctx.leafFrame.computeMBR(ctx.splitKey, leafCmp);
+ ctx.splitKey.setLeftPage(pageId);
+
+ }
+ }
+
public void search(Stack<Integer> s, ITupleReference tuple, RTreeOpContext ctx, ArrayList<Rectangle> results)
throws Exception {
ctx.reset();
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 6a07c93..4c8f198 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
@@ -2,7 +2,6 @@
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.TreeIndexOp;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
@@ -11,16 +10,13 @@
public final IRTreeFrame interiorFrame;
public final IRTreeFrame leafFrame;
public final ITreeIndexMetaDataFrame metaFrame;
- public final ByteArrayList overflowArray;
public final RTreeSplitKey splitKey;
public final SpatialUtils spatialUtils;
public ITupleReference tuple;
- public TupleEntryArrayList tupleEntries1;
- public TupleEntryArrayList tupleEntries2;
- public ITreeIndexTupleReference[] nodesMBRs;
- public final IntArrayList path;
- public final IntArrayList pageLsns;
- public final FindPathList findPathList; // works as a queue
+ 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 TraverseList traverseList; // used for traversing the tree
public Rectangle[] rec;
public RTreeOpContext(TreeIndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
@@ -31,19 +27,12 @@
this.metaFrame = metaFrame;
splitKey = new RTreeSplitKey(interiorFrame.getTupleWriter().createTupleReference(), interiorFrame
.getTupleWriter().createTupleReference());
- overflowArray = new ByteArrayList(treeHeightHint, treeHeightHint);
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);
- nodesMBRs = new ITreeIndexTupleReference[treeHeightHint];
- path = new IntArrayList(treeHeightHint, treeHeightHint);
- pageLsns = new IntArrayList(treeHeightHint, treeHeightHint);
- findPathList = new FindPathList(100, 100);
- for (int i = 0; i < treeHeightHint; i++) {
- nodesMBRs[i] = interiorFrame.getTupleWriter().createTupleReference();
- nodesMBRs[i].setFieldCount(nodesMBRs[i].getFieldCount());
- }
+ 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);
@@ -59,23 +48,17 @@
}
public void reset() {
- if (overflowArray != null) {
- overflowArray.clear();
- }
if (tupleEntries1 != null) {
tupleEntries1.clear();
}
if (tupleEntries2 != null) {
tupleEntries2.clear();
}
- if (path != null) {
- path.clear();
+ if (pathList != null) {
+ pathList.clear();
}
- if (pageLsns != null) {
- pageLsns.clear();
- }
- if (findPathList != null) {
- pageLsns.clear();
+ if (traverseList != null) {
+ traverseList.clear();
}
}
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/TraverseList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/TraverseList.java
new file mode 100644
index 0000000..c09971d
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/TraverseList.java
@@ -0,0 +1,108 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree.impls;
+
+public class TraverseList {
+ private IntArrayList pageIds;
+ private IntArrayList pageLsns;
+ private IntArrayList parentIndexes;
+
+ public TraverseList(int initialCapacity, int growth) {
+ pageIds = new IntArrayList(initialCapacity, growth);
+ pageLsns = new IntArrayList(initialCapacity, growth);
+ parentIndexes = new IntArrayList(initialCapacity, growth);
+ }
+
+ public int size() {
+ return pageIds.size();
+ }
+
+ public int first() {
+ return pageIds.first();
+ }
+
+ public void add(int pageId, int pageLsn, int parentIndex) {
+ pageIds.add(pageId);
+ pageLsns.add(pageLsn);
+ parentIndexes.add(parentIndex);
+ }
+
+ public int getFirstPageId() {
+ return pageIds.getFirst();
+ }
+
+ public int getFirstPageLsn() {
+ return pageLsns.getFirst();
+ }
+
+ public int getFirstParentIndex() {
+ return parentIndexes.getFirst();
+ }
+
+ public int getLastPageId() {
+ return pageIds.getLast();
+ }
+
+ public int getLastPageLsn() {
+ return pageLsns.getLast();
+ }
+
+ public int getLastParentIndex() {
+ return parentIndexes.getLast();
+ }
+
+ public int getPageId(int i) {
+ return pageIds.get(i);
+ }
+
+ public int getPageLsn(int i) {
+ return pageLsns.get(i);
+ }
+
+ public int getParentIndex(int i) {
+ return parentIndexes.get(i);
+ }
+
+ public void setPageLsn(int i, int pageLsn) {
+ pageLsns.set(i, pageLsn);
+ }
+
+ public void moveFirst() {
+ pageIds.moveFirst();
+ pageLsns.moveFirst();
+ parentIndexes.moveFirst();
+ }
+
+ public void moveLast() {
+ pageIds.removeLast();
+ pageLsns.removeLast();
+ parentIndexes.removeLast();
+ }
+
+ public boolean isLast() {
+ return pageIds.isLast();
+ }
+
+ public void clear() {
+ pageIds.clear();
+ pageLsns.clear();
+ parentIndexes.clear();
+ }
+
+ public boolean isEmpty() {
+ return pageIds.isEmpty();
+ }
+}