fixed rare case bug with update in btree and cleaned up an interface
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@1570 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
index fb2e833..5d3dd65 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
@@ -69,7 +69,7 @@
private final ITreeIndexTupleWriter tupleWriter;
private MultiComparator cmp;
-
+
private final FieldPrefixTupleReference frameTuple;
private final FieldPrefixPrefixTupleReference framePrefixTuple;
@@ -257,36 +257,36 @@
buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + bytesWritten);
buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - bytesWritten - slotManager.getSlotSize());
}
-
+
@Override
public FrameOpSpaceStatus hasSpaceUpdate(ITupleReference newTuple, int oldTupleIndex) {
int tupleIndex = slotManager.decodeSecondSlotField(oldTupleIndex);
frameTuple.resetByTupleIndex(this, tupleIndex);
-
+
int oldTupleBytes = 0;
int newTupleBytes = 0;
-
+
int numPrefixFields = frameTuple.getNumPrefixFields();
int fieldCount = frameTuple.getFieldCount();
if (numPrefixFields != 0) {
// Check the space requirements for updating the suffix of the original tuple.
oldTupleBytes = frameTuple.getSuffixTupleSize();
- newTupleBytes = tupleWriter.bytesRequired(newTuple, numPrefixFields, fieldCount - numPrefixFields);
+ newTupleBytes = tupleWriter.bytesRequired(newTuple, numPrefixFields, fieldCount - numPrefixFields);
} else {
// The original tuple is uncompressed.
oldTupleBytes = frameTuple.getTupleSize();
newTupleBytes = tupleWriter.bytesRequired(newTuple);
}
-
+
int additionalBytesRequired = newTupleBytes - oldTupleBytes;
// Enough space for an in-place update?
if (additionalBytesRequired <= 0) {
return FrameOpSpaceStatus.SUFFICIENT_INPLACE_SPACE;
}
-
+
int freeContiguous = buf.capacity() - buf.getInt(freeSpaceOff)
- ((buf.getInt(tupleCountOff) + buf.getInt(prefixTupleCountOff)) * slotManager.getSlotSize());
-
+
// Enough space if we delete the old tuple and insert the new one without compaction?
if (newTupleBytes <= freeContiguous) {
return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
@@ -304,21 +304,23 @@
int tupleSlotOff = slotManager.getTupleSlotOff(tupleIndex);
int tupleSlot = buf.getInt(tupleSlotOff);
int prefixSlotNum = slotManager.decodeFirstSlotField(tupleSlot);
- int suffixTupleStartOff = slotManager.decodeSecondSlotField(tupleSlot);
-
+ int suffixTupleStartOff = slotManager.decodeSecondSlotField(tupleSlot);
+
frameTuple.resetByTupleIndex(this, tupleIndex);
int fieldCount = frameTuple.getFieldCount();
int numPrefixFields = frameTuple.getNumPrefixFields();
int oldTupleBytes = frameTuple.getSuffixTupleSize();
- int bytesWritten = 0;
-
+ int bytesWritten = 0;
+
if (inPlace) {
// Overwrite the old tuple suffix in place.
- bytesWritten = tupleWriter.writeTupleFields(newTuple, numPrefixFields, fieldCount - numPrefixFields, buf.array(), suffixTupleStartOff);
+ bytesWritten = tupleWriter.writeTupleFields(newTuple, numPrefixFields, fieldCount - numPrefixFields,
+ buf.array(), suffixTupleStartOff);
} else {
// Insert the new tuple suffix at the end of the free space, and change the slot value (effectively "deleting" the old tuple).
int newSuffixTupleStartOff = buf.getInt(freeSpaceOff);
- bytesWritten = tupleWriter.writeTupleFields(newTuple, numPrefixFields, fieldCount - numPrefixFields, buf.array(), newSuffixTupleStartOff);
+ bytesWritten = tupleWriter.writeTupleFields(newTuple, numPrefixFields, fieldCount - numPrefixFields,
+ buf.array(), newSuffixTupleStartOff);
// Update slot value using the same prefix slot num.
slotManager.setSlot(tupleSlotOff, slotManager.encodeSlotFields(prefixSlotNum, newSuffixTupleStartOff));
// Update contiguous free space pointer.
@@ -326,7 +328,7 @@
}
buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + oldTupleBytes - bytesWritten);
}
-
+
protected void resetSpaceParams() {
buf.putInt(freeSpaceOff, getOrigFreeSpaceOff());
buf.putInt(totalFreeSpaceOff, getOrigTotalFreeSpace());
@@ -355,8 +357,8 @@
@Override
public int findInsertTupleIndex(ITupleReference tuple) throws TreeIndexException {
- int slot = slotManager.findSlot(tuple, frameTuple, framePrefixTuple, cmp, FindTupleMode.EXCLUSIVE_ERROR_IF_EXISTS,
- FindTupleNoExactMatchPolicy.HIGHER_KEY);
+ int slot = slotManager.findSlot(tuple, frameTuple, framePrefixTuple, cmp,
+ FindTupleMode.EXCLUSIVE_ERROR_IF_EXISTS, FindTupleNoExactMatchPolicy.HIGHER_KEY);
int tupleIndex = slotManager.decodeSecondSlotField(slot);
// Error indicator is set if there is an exact match.
if (tupleIndex == slotManager.getErrorIndicator()) {
@@ -364,7 +366,7 @@
}
return slot;
}
-
+
@Override
public int findUpsertTupleIndex(ITupleReference tuple) throws TreeIndexException {
int slot = slotManager.findSlot(tuple, frameTuple, framePrefixTuple, cmp, FindTupleMode.INCLUSIVE,
@@ -376,7 +378,7 @@
}
return slot;
}
-
+
@Override
public ITupleReference getUpsertBeforeTuple(ITupleReference tuple, int targetTupleIndex) throws TreeIndexException {
int tupleIndex = slotManager.decodeSecondSlotField(targetTupleIndex);
@@ -393,7 +395,7 @@
// In those cases, we are definitely dealing with an insert.
return null;
}
-
+
@Override
public int findUpdateTupleIndex(ITupleReference tuple) throws TreeIndexException {
int slot = slotManager.findSlot(tuple, frameTuple, framePrefixTuple, cmp, FindTupleMode.EXACT,
@@ -402,10 +404,10 @@
// Error indicator is set if there is no exact match.
if (tupleIndex == slotManager.getErrorIndicator()) {
throw new BTreeNonExistentKeyException("Trying to update a tuple with a nonexistent key in leaf node.");
- }
+ }
return slot;
}
-
+
@Override
public int findDeleteTupleIndex(ITupleReference tuple) throws TreeIndexException {
int slot = slotManager.findSlot(tuple, frameTuple, framePrefixTuple, cmp, FindTupleMode.EXACT,
@@ -414,10 +416,10 @@
// Error indicator is set if there is no exact match.
if (tupleIndex == slotManager.getErrorIndicator()) {
throw new BTreeNonExistentKeyException("Trying to delete a tuple with a nonexistent key in leaf node.");
- }
+ }
return slot;
}
-
+
@Override
public String printHeader() {
StringBuilder strBuilder = new StringBuilder();
@@ -537,10 +539,9 @@
}
@Override
- public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey)
- throws TreeIndexException {
+ public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) {
- BTreeFieldPrefixNSMLeafFrame rf = (BTreeFieldPrefixNSMLeafFrame)rightFrame;
+ BTreeFieldPrefixNSMLeafFrame rf = (BTreeFieldPrefixNSMLeafFrame) rightFrame;
ByteBuffer right = rf.getBuffer();
int tupleCount = getTupleCount();
@@ -652,7 +653,13 @@
rightFrame.compact();
// insert last key
- int targetTupleIndex = ((IBTreeLeafFrame)targetFrame).findInsertTupleIndex(tuple);
+ int targetTupleIndex;
+ // it's safe to catch this exception since it will have been caught before reaching here
+ try {
+ targetTupleIndex = ((IBTreeLeafFrame) targetFrame).findInsertTupleIndex(tuple);
+ } catch (TreeIndexException e) {
+ throw new IllegalStateException(e);
+ }
targetFrame.insert(tuple, targetTupleIndex);
// set split key to be highest value in left page
@@ -716,7 +723,8 @@
int slot = slotManager.findSlot(searchKey, pageTuple, framePrefixTuple, cmp, ftm, ftp);
int tupleIndex = slotManager.decodeSecondSlotField(slot);
// TODO: Revisit this one. Maybe there is a cleaner way to solve this in the RangeSearchCursor.
- if (tupleIndex == FieldPrefixSlotManager.GREATEST_KEY_INDICATOR || tupleIndex == FieldPrefixSlotManager.ERROR_INDICATOR)
+ if (tupleIndex == FieldPrefixSlotManager.GREATEST_KEY_INDICATOR
+ || tupleIndex == FieldPrefixSlotManager.ERROR_INDICATOR)
return -1;
else
return tupleIndex;
@@ -727,9 +735,9 @@
return nextLeafOff;
}
- @Override
- public void setMultiComparator(MultiComparator cmp) {
- this.cmp = cmp;
- this.slotManager.setMultiComparator(cmp);
- }
+ @Override
+ public void setMultiComparator(MultiComparator cmp) {
+ this.cmp = cmp;
+ this.slotManager.setMultiComparator(cmp);
+ }
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
index d2cb2c6..7208da6 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
@@ -59,7 +59,7 @@
return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
FindTupleNoExactMatchPolicy.HIGHER_KEY);
}
-
+
@Override
public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple) {
// Tuple bytes + child pointer + slot.
@@ -103,7 +103,7 @@
}
}
}
-
+
@Override
public int findDeleteTupleIndex(ITupleReference tuple) throws TreeIndexException {
return slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
@@ -135,7 +135,7 @@
buf.putInt(totalFreeSpaceOff,
buf.getInt(totalFreeSpaceOff) + keySize + childPtrSize + slotManager.getSlotSize());
}
-
+
@Override
public void deleteGreatest() {
int slotOff = slotManager.getSlotEndOff();
@@ -152,12 +152,12 @@
buf.putInt(freeSpace, freeSpace - (keySize + childPtrSize));
}
}
-
+
@Override
public FrameOpSpaceStatus hasSpaceUpdate(ITupleReference tuple, int oldTupleIndex) {
throw new UnsupportedOperationException("Cannot update tuples in interior node.");
}
-
+
@Override
public int findUpdateTupleIndex(ITupleReference tuple) throws TreeIndexException {
throw new UnsupportedOperationException("Cannot update tuples in interior node.");
@@ -179,10 +179,10 @@
}
@Override
- public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) throws TreeIndexException {
+ public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) {
ByteBuffer right = rightFrame.getBuffer();
int tupleCount = getTupleCount();
-
+
// Find split point, and determine into which frame the new tuple should be inserted into.
int tuplesToLeft = (tupleCount / 2) + (tupleCount % 2);
ITreeIndexFrame targetFrame = null;
@@ -232,8 +232,13 @@
compact();
// Insert the saved split key.
- int targetTupleIndex = ((BTreeNSMInteriorFrame) targetFrame)
- .findInsertTupleIndex(savedSplitKey.getTuple());
+ int targetTupleIndex;
+ // it's safe to catch this exception since it will have been caught before reaching here
+ try {
+ targetTupleIndex = ((BTreeNSMInteriorFrame) targetFrame).findInsertTupleIndex(savedSplitKey.getTuple());
+ } catch (TreeIndexException e) {
+ throw new IllegalStateException(e);
+ }
targetFrame.insert(savedSplitKey.getTuple(), targetTupleIndex);
}
@@ -378,14 +383,14 @@
cmpFrameTuple.setFieldCount(cmp.getKeyFieldCount());
frameTuple.setFieldCount(cmp.getKeyFieldCount());
}
-
+
@Override
public ITreeIndexTupleReference createTupleReference() {
ITreeIndexTupleReference tuple = tupleWriter.createTupleReference();
tuple.setFieldCount(cmp.getKeyFieldCount());
return tuple;
}
-
+
// For debugging.
public ArrayList<Integer> getChildren(MultiComparator cmp) {
ArrayList<Integer> ret = new ArrayList<Integer>();
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
index 4b7f44b..0437a5d 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
@@ -34,7 +34,7 @@
public class BTreeNSMLeafFrame extends TreeIndexNSMFrame implements IBTreeLeafFrame {
protected static final int nextLeafOff = smFlagOff + 1;
private MultiComparator cmp;
-
+
public BTreeNSMLeafFrame(ITreeIndexTupleWriter tupleWriter) {
super(tupleWriter, new OrderedSlotManager());
}
@@ -65,7 +65,7 @@
}
return tupleIndex;
}
-
+
@Override
public int findUpdateTupleIndex(ITupleReference tuple) throws TreeIndexException {
int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.EXACT,
@@ -73,10 +73,10 @@
// Error indicator is set if there is no exact match.
if (tupleIndex == slotManager.getErrorIndicator() || tupleIndex == slotManager.getGreatestKeyIndicator()) {
throw new BTreeNonExistentKeyException("Trying to update a tuple with a nonexistent key in leaf node.");
- }
+ }
return tupleIndex;
}
-
+
@Override
public int findUpsertTupleIndex(ITupleReference tuple) throws TreeIndexException {
int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.INCLUSIVE,
@@ -84,7 +84,7 @@
// Just return the found tupleIndex. The caller will make the final decision whether to insert or update.
return tupleIndex;
}
-
+
@Override
public ITupleReference getUpsertBeforeTuple(ITupleReference tuple, int targetTupleIndex) throws TreeIndexException {
// Examine the tuple index to determine whether it is valid or not.
@@ -100,7 +100,7 @@
// In those cases, we are definitely dealing with an insert.
return null;
}
-
+
@Override
public int findDeleteTupleIndex(ITupleReference tuple) throws TreeIndexException {
int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.EXACT,
@@ -108,7 +108,7 @@
// Error indicator is set if there is no exact match.
if (tupleIndex == slotManager.getErrorIndicator() || tupleIndex == slotManager.getGreatestKeyIndicator()) {
throw new BTreeNonExistentKeyException("Trying to delete a tuple with a nonexistent key in leaf node.");
- }
+ }
return tupleIndex;
}
@@ -128,10 +128,10 @@
}
@Override
- public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) throws TreeIndexException {
- ByteBuffer right = rightFrame.getBuffer();
- int tupleCount = getTupleCount();
-
+ public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) {
+ ByteBuffer right = rightFrame.getBuffer();
+ int tupleCount = getTupleCount();
+
// Find split point, and determine into which frame the new tuple should be inserted into.
int tuplesToLeft;
int mid = tupleCount / 2;
@@ -166,7 +166,13 @@
compact();
// Insert the new tuple.
- int targetTupleIndex = ((BTreeNSMLeafFrame)targetFrame).findInsertTupleIndex(tuple);
+ int targetTupleIndex;
+ // it's safe to catch this exception since it will have been caught before reaching here
+ try {
+ targetTupleIndex = ((BTreeNSMLeafFrame) targetFrame).findInsertTupleIndex(tuple);
+ } catch (TreeIndexException e) {
+ throw new IllegalStateException(e);
+ }
targetFrame.insert(tuple, targetTupleIndex);
// Set the split key to be highest key in the left page.
@@ -213,9 +219,9 @@
buf.put(smFlagOff, (byte) 0);
}
}
-
- @Override
- public void setMultiComparator(MultiComparator cmp) {
- this.cmp = cmp;
- }
+
+ @Override
+ public void setMultiComparator(MultiComparator cmp) {
+ this.cmp = cmp;
+ }
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
index 682ada7..397d95a 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
@@ -60,9 +60,9 @@
private final static long RESTART_OP = Long.MIN_VALUE;
private final static int MAX_RESTARTS = 10;
private final static int rootPage = 1;
-
+
private final IFreePageManager freePageManager;
- private final IBufferCache bufferCache;
+ private final IBufferCache bufferCache;
private final IOperationCallback opCallback;
private final ITreeIndexFrameFactory interiorFrameFactory;
private final ITreeIndexFrameFactory leafFrameFactory;
@@ -71,14 +71,15 @@
private final ReadWriteLock treeLatch;
private int fileId;
- public BTree(IBufferCache bufferCache, IOperationCallback opCallback, int fieldCount, IBinaryComparatorFactory[] cmpFactories, IFreePageManager freePageManager,
+ public BTree(IBufferCache bufferCache, IOperationCallback opCallback, int fieldCount,
+ IBinaryComparatorFactory[] cmpFactories, IFreePageManager freePageManager,
ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory) {
this.bufferCache = bufferCache;
this.opCallback = opCallback;
this.fieldCount = fieldCount;
this.cmpFactories = cmpFactories;
this.interiorFrameFactory = interiorFrameFactory;
- this.leafFrameFactory = leafFrameFactory;
+ this.leafFrameFactory = leafFrameFactory;
this.freePageManager = freePageManager;
this.treeLatch = new ReentrantReadWriteLock(true);
}
@@ -99,9 +100,9 @@
}
@Override
- public void open(int fileId) {
- this.fileId = fileId;
- freePageManager.open(fileId);
+ public void open(int fileId) {
+ this.fileId = fileId;
+ freePageManager.open(fileId);
}
@Override
@@ -193,7 +194,7 @@
bufferCache.unpin(rootNode);
}
}
-
+
private void createNewRoot(BTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
// Make sure the root is always in the same page.
ICachedPage leftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, ctx.splitKey.getLeftPage()),
@@ -226,8 +227,9 @@
bufferCache.unpin(leftNode);
}
}
-
- private void insertUpdateOrDelete(ITupleReference tuple, BTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
+
+ private void insertUpdateOrDelete(ITupleReference tuple, BTreeOpContext ctx) throws HyracksDataException,
+ TreeIndexException {
ctx.reset();
ctx.pred.setLowKeyComparator(ctx.cmp);
ctx.pred.setHighKeyComparator(ctx.cmp);
@@ -254,11 +256,11 @@
repeatOp = false;
}
}
-
+
private void insert(ITupleReference tuple, BTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
insertUpdateOrDelete(tuple, ctx);
}
-
+
private void upsert(ITupleReference tuple, BTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
insertUpdateOrDelete(tuple, ctx);
}
@@ -272,12 +274,13 @@
}
insertUpdateOrDelete(tuple, ctx);
}
-
+
private void delete(ITupleReference tuple, BTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
insertUpdateOrDelete(tuple, ctx);
}
-
- private boolean insertLeaf(ITupleReference tuple, int targetTupleIndex, int pageId, BTreeOpContext ctx) throws Exception {
+
+ private boolean insertLeaf(ITupleReference tuple, int targetTupleIndex, int pageId, BTreeOpContext ctx)
+ throws Exception {
boolean restartOp = false;
FrameOpSpaceStatus spaceStatus = ctx.leafFrame.hasSpaceInsert(tuple);
switch (spaceStatus) {
@@ -295,7 +298,7 @@
ctx.splitKey.reset();
break;
}
- case INSUFFICIENT_SPACE: {
+ case INSUFFICIENT_SPACE: {
// Try compressing the page first and see if there is space available.
boolean reCompressed = ctx.leafFrame.compress();
if (reCompressed) {
@@ -307,15 +310,16 @@
ctx.leafFrame.insert(tuple, targetTupleIndex);
ctx.splitKey.reset();
} else {
- restartOp = performLeafSplit(pageId, tuple, ctx);
+ restartOp = performLeafSplit(pageId, tuple, ctx, -1);
}
break;
}
- }
+ }
return restartOp;
}
-
- private boolean performLeafSplit(int pageId, ITupleReference tuple, BTreeOpContext ctx) throws Exception {
+
+ private boolean performLeafSplit(int pageId, ITupleReference tuple, BTreeOpContext ctx, int updateTupleIndex)
+ throws Exception {
// We must never hold a latch on a page while waiting to obtain the tree
// latch, because it this could lead to a latch-deadlock.
// If we can't get the tree latch, we return, release our page latches,
@@ -325,14 +329,18 @@
return true;
}
int rightPageId = freePageManager.getFreePage(ctx.metaFrame);
- ICachedPage rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightPageId),
- true);
+ ICachedPage rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightPageId), true);
rightNode.acquireWriteLatch();
try {
IBTreeLeafFrame rightFrame = ctx.createLeafFrame();
rightFrame.setPage(rightNode);
rightFrame.initBuffer((byte) 0);
rightFrame.setMultiComparator(ctx.cmp);
+
+ // Perform an update (delete + insert) if the updateTupleIndex != -1
+ if (updateTupleIndex != -1) {
+ ctx.leafFrame.delete(tuple, updateTupleIndex);
+ }
ctx.leafFrame.split(rightFrame, tuple, ctx.splitKey);
ctx.smPages.add(pageId);
@@ -360,8 +368,9 @@
}
return false;
}
-
- private boolean updateLeaf(ITupleReference tuple, int oldTupleIndex, int pageId, BTreeOpContext ctx) throws Exception {
+
+ private boolean updateLeaf(ITupleReference tuple, int oldTupleIndex, int pageId, BTreeOpContext ctx)
+ throws Exception {
FrameOpSpaceStatus spaceStatus = ctx.leafFrame.hasSpaceUpdate(tuple, oldTupleIndex);
boolean restartOp = false;
switch (spaceStatus) {
@@ -374,7 +383,7 @@
ctx.leafFrame.update(tuple, oldTupleIndex, false);
ctx.splitKey.reset();
break;
- }
+ }
case SUFFICIENT_SPACE: {
// Delete the old tuple, compact the frame, and insert the new tuple.
ctx.leafFrame.delete(tuple, oldTupleIndex);
@@ -383,27 +392,17 @@
ctx.leafFrame.insert(tuple, targetTupleIndex);
ctx.splitKey.reset();
break;
- }
+ }
case INSUFFICIENT_SPACE: {
- // Delete the old tuple, and try compressing the page to make space available.
- ctx.leafFrame.delete(tuple, oldTupleIndex);
- ctx.leafFrame.compress();
- // We need to insert the new tuple, so check if there is space.
- spaceStatus = ctx.leafFrame.hasSpaceInsert(tuple);
- if (spaceStatus == FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE) {
- int targetTupleIndex = ctx.leafFrame.findInsertTupleIndex(tuple);
- ctx.leafFrame.insert(tuple, targetTupleIndex);
- ctx.splitKey.reset();
- } else {
- restartOp = performLeafSplit(pageId, tuple, ctx);
- }
+ restartOp = performLeafSplit(pageId, tuple, ctx, oldTupleIndex);
break;
}
}
return restartOp;
}
- private boolean upsertLeaf(ITupleReference tuple, int targetTupleIndex, int pageId, BTreeOpContext ctx) throws Exception {
+ private boolean upsertLeaf(ITupleReference tuple, int targetTupleIndex, int pageId, BTreeOpContext ctx)
+ throws Exception {
boolean restartOp = false;
ITupleReference beforeTuple = ctx.leafFrame.getUpsertBeforeTuple(tuple, targetTupleIndex);
if (beforeTuple == null) {
@@ -416,7 +415,7 @@
opCallback.post(tuple);
return restartOp;
}
-
+
private void insertInterior(ICachedPage node, int pageId, ITupleReference tuple, BTreeOpContext ctx)
throws Exception {
ctx.interiorFrame.setPage(node);
@@ -451,7 +450,7 @@
bufferCache.unpin(rightNode);
}
break;
- }
+ }
case SUFFICIENT_CONTIGUOUS_SPACE: {
ctx.interiorFrame.insert(tuple, targetTupleIndex);
@@ -471,7 +470,8 @@
}
}
- private boolean deleteLeaf(ICachedPage node, int pageId, ITupleReference tuple, BTreeOpContext ctx) throws Exception {
+ private boolean deleteLeaf(ICachedPage node, int pageId, ITupleReference tuple, BTreeOpContext ctx)
+ throws Exception {
// Simply delete the tuple, and don't do any rebalancing.
// This means that there could be underflow, even an empty page that is
// pointed to by an interior node.
@@ -507,10 +507,11 @@
return isConsistent;
}
- private void performOp(int pageId, ICachedPage parent, boolean parentIsReadLatched, BTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
+ private void performOp(int pageId, ICachedPage parent, boolean parentIsReadLatched, BTreeOpContext ctx)
+ throws HyracksDataException, TreeIndexException {
ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
ctx.interiorFrame.setPage(node);
-
+
// this check performs an unprotected read in the page
// the following could happen: TODO fill out
boolean unsafeIsLeaf = ctx.interiorFrame.isLeaf();
@@ -526,9 +527,9 @@
// Latch coupling: unlatch parent.
if (parent != null) {
if (parentIsReadLatched) {
- parent.releaseReadLatch();
+ parent.releaseReadLatch();
} else {
- parent.releaseWriteLatch();
+ parent.releaseWriteLatch();
}
bufferCache.unpin(parent);
}
@@ -544,7 +545,7 @@
if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.getLast() == RESTART_OP) {
// Pop the restart op indicator.
- ctx.pageLsns.removeLast();
+ ctx.pageLsns.removeLast();
if (isConsistent(pageId, ctx)) {
// Pin and latch page again, since it was unpinned and unlatched in call to performOp (passed as parent).
node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
@@ -555,26 +556,27 @@
continue;
} else {
// Pop pageLsn of this page (version seen by this op during descent).
- ctx.pageLsns.removeLast();
+ ctx.pageLsns.removeLast();
// This node is not consistent set the restart indicator for upper level.
ctx.pageLsns.add(RESTART_OP);
break;
}
}
-
+
switch (ctx.op) {
case INSERT:
case UPSERT:
case UPDATE: {
// Is there a propagated split key?
if (ctx.splitKey.getBuffer() != null) {
- ICachedPage interiorNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ ICachedPage interiorNode = bufferCache.pin(
+ BufferedFileHandle.getDiskPageId(fileId, pageId), false);
interiorNode.acquireWriteLatch();
try {
// Insert or update op. Both can cause split keys to propagate upwards.
insertInterior(interiorNode, pageId, ctx.splitKey.getTuple(), ctx);
} finally {
- interiorNode.releaseWriteLatch();
+ interiorNode.releaseWriteLatch();
bufferCache.unpin(interiorNode);
}
} else {
@@ -582,14 +584,15 @@
}
break;
}
-
+
case DELETE: {
if (ctx.splitKey.getBuffer() != null) {
- throw new BTreeException("Split key was propagated during delete. Delete allows empty leaf pages.");
+ throw new BTreeException(
+ "Split key was propagated during delete. Delete allows empty leaf pages.");
}
break;
}
-
+
default: {
// Do nothing for Search and DiskOrderScan.
break;
@@ -601,9 +604,9 @@
} else { // smFlag
ctx.opRestarts++;
if (isReadLatched) {
- node.releaseReadLatch();
+ node.releaseReadLatch();
} else {
- node.releaseWriteLatch();
+ node.releaseWriteLatch();
}
bufferCache.unpin(node);
@@ -614,7 +617,7 @@
// latch-deadlock
treeLatch.writeLock().lock();
treeLatch.writeLock().unlock();
-
+
// unwind recursion and restart operation, find lowest page
// with a pageLsn as seen by this operation during descent
ctx.pageLsns.removeLast(); // pop current page lsn
@@ -624,10 +627,10 @@
}
} else { // isLeaf and !smFlag
// We may have to restart an op to avoid latch deadlock.
- boolean restartOp = false;
- ctx.leafFrame.setPage(node);
- switch (ctx.op) {
- case INSERT: {
+ boolean restartOp = false;
+ ctx.leafFrame.setPage(node);
+ switch (ctx.op) {
+ case INSERT: {
int targetTupleIndex = ctx.leafFrame.findInsertTupleIndex(ctx.pred.getLowKey());
restartOp = insertLeaf(ctx.pred.getLowKey(), targetTupleIndex, pageId, ctx);
break;
@@ -639,11 +642,11 @@
}
case UPDATE: {
int oldTupleIndex = ctx.leafFrame.findUpdateTupleIndex(ctx.pred.getLowKey());
- restartOp = updateLeaf(ctx.pred.getLowKey(), oldTupleIndex, pageId, ctx);
+ restartOp = updateLeaf(ctx.pred.getLowKey(), oldTupleIndex, pageId, ctx);
break;
}
case DELETE: {
- restartOp = deleteLeaf(node, pageId, ctx.pred.getLowKey(), ctx);
+ restartOp = deleteLeaf(node, pageId, ctx.pred.getLowKey(), ctx);
break;
}
case SEARCH: {
@@ -652,38 +655,38 @@
break;
}
}
- if (ctx.op != IndexOp.SEARCH) {
- node.releaseWriteLatch();
+ if (ctx.op != IndexOp.SEARCH) {
+ node.releaseWriteLatch();
bufferCache.unpin(node);
- }
- if (restartOp) {
- ctx.pageLsns.removeLast();
+ }
+ if (restartOp) {
+ ctx.pageLsns.removeLast();
ctx.pageLsns.add(RESTART_OP);
- }
+ }
}
} catch (TreeIndexException e) {
- if (!ctx.exceptionHandled) {
- if (node != null) {
- if (isReadLatched) {
- node.releaseReadLatch();
- } else {
- node.releaseWriteLatch();
- }
- bufferCache.unpin(node);
- ctx.exceptionHandled = true;
- }
+ if (!ctx.exceptionHandled) {
+ if (node != null) {
+ if (isReadLatched) {
+ node.releaseReadLatch();
+ } else {
+ node.releaseWriteLatch();
+ }
+ bufferCache.unpin(node);
+ ctx.exceptionHandled = true;
+ }
}
throw e;
} catch (Exception e) {
- e.printStackTrace();
- if (node != null) {
- if (isReadLatched) {
- node.releaseReadLatch();
- } else {
- node.releaseWriteLatch();
- }
- bufferCache.unpin(node);
- }
+ e.printStackTrace();
+ if (node != null) {
+ if (isReadLatched) {
+ node.releaseReadLatch();
+ } else {
+ node.releaseWriteLatch();
+ }
+ bufferCache.unpin(node);
+ }
BTreeException wrappedException = new BTreeException(e);
ctx.exceptionHandled = true;
throw wrappedException;
@@ -701,22 +704,21 @@
private final IBTreeLeafFrame leafFrame;
private final IBTreeInteriorFrame interiorFrame;
private final ITreeIndexMetaDataFrame metaFrame;
- private final ITreeIndexTupleWriter tupleWriter;
-
+ private final ITreeIndexTupleWriter tupleWriter;
+
public BulkLoadContext(float fillFactor, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
ITreeIndexMetaDataFrame metaFrame, IBinaryComparatorFactory[] cmpFactories) throws HyracksDataException {
this.cmp = MultiComparator.create(cmpFactories);
-
- leafFrame.setMultiComparator(cmp);
- interiorFrame.setMultiComparator(cmp);
-
+
+ leafFrame.setMultiComparator(cmp);
+ interiorFrame.setMultiComparator(cmp);
+
splitKey = new BTreeSplitKey(leafFrame.getTupleWriter().createTupleReference());
tupleWriter = leafFrame.getTupleWriter();
NodeFrontier leafFrontier = new NodeFrontier(leafFrame.createTupleReference());
leafFrontier.pageId = freePageManager.getFreePage(metaFrame);
- leafFrontier.page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, leafFrontier.pageId),
- true);
+ leafFrontier.page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, leafFrontier.pageId), true);
leafFrontier.page.acquireWriteLatch();
interiorFrame.setPage(leafFrontier.page);
@@ -770,8 +772,8 @@
frontier.lastTuple.resetByTupleIndex(ctx.interiorFrame, ctx.interiorFrame.getTupleCount() - 1);
int splitKeySize = ctx.tupleWriter.bytesRequired(frontier.lastTuple, 0, ctx.cmp.getKeyFieldCount());
ctx.splitKey.initData(splitKeySize);
- ctx.tupleWriter
- .writeTupleFields(frontier.lastTuple, 0, ctx.cmp.getKeyFieldCount(), ctx.splitKey.getBuffer().array(), 0);
+ ctx.tupleWriter.writeTupleFields(frontier.lastTuple, 0, ctx.cmp.getKeyFieldCount(), ctx.splitKey
+ .getBuffer().array(), 0);
ctx.splitKey.getTuple().resetByTupleOffset(ctx.splitKey.getBuffer(), 0);
ctx.splitKey.setLeftPage(frontier.pageId);
@@ -795,13 +797,14 @@
// assumes btree has been created and opened
@Override
public IIndexBulkLoadContext beginBulkLoad(float fillFactor) throws TreeIndexException, HyracksDataException {
- IBTreeLeafFrame leafFrame = (IBTreeLeafFrame)leafFrameFactory.createFrame();
- if (!isEmptyTree(leafFrame)) {
- throw new BTreeException("Trying to Bulk-load a non-empty BTree.");
- }
-
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
+ if (!isEmptyTree(leafFrame)) {
+ throw new BTreeException("Trying to Bulk-load a non-empty BTree.");
+ }
+
BulkLoadContext ctx = new BulkLoadContext(fillFactor, leafFrame,
- (IBTreeInteriorFrame)interiorFrameFactory.createFrame(), freePageManager.getMetaDataFrameFactory().createFrame(), cmpFactories);
+ (IBTreeInteriorFrame) interiorFrameFactory.createFrame(), freePageManager.getMetaDataFrameFactory()
+ .createFrame(), cmpFactories);
ctx.splitKey.getTuple().setFieldCount(ctx.cmp.getKeyFieldCount());
return ctx;
}
@@ -825,8 +828,8 @@
leafFrontier.lastTuple.resetByTupleIndex(leafFrame, leafFrame.getTupleCount() - 1);
int splitKeySize = ctx.tupleWriter.bytesRequired(leafFrontier.lastTuple, 0, ctx.cmp.getKeyFieldCount());
ctx.splitKey.initData(splitKeySize);
- ctx.tupleWriter.writeTupleFields(leafFrontier.lastTuple, 0, ctx.cmp.getKeyFieldCount(),
- ctx.splitKey.getBuffer().array(), 0);
+ ctx.tupleWriter.writeTupleFields(leafFrontier.lastTuple, 0, ctx.cmp.getKeyFieldCount(), ctx.splitKey
+ .getBuffer().array(), 0);
ctx.splitKey.getTuple().resetByTupleOffset(ctx.splitKey.getBuffer(), 0);
ctx.splitKey.setLeftPage(leafFrontier.pageId);
leafFrontier.pageId = freePageManager.getFreePage(ctx.metaFrame);
@@ -838,8 +841,7 @@
ctx.splitKey.setRightPage(leafFrontier.pageId);
propagateBulk(ctx, 1);
- leafFrontier.page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, leafFrontier.pageId),
- true);
+ leafFrontier.page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, leafFrontier.pageId), true);
leafFrontier.page.acquireWriteLatch();
leafFrame.setPage(leafFrontier.page);
leafFrame.initBuffer((byte) 0);
@@ -884,7 +886,7 @@
return new BTreeOpContext(leafFrameFactory, interiorFrameFactory, freePageManager.getMetaDataFrameFactory()
.createFrame(), cmpFactories);
}
-
+
public ITreeIndexFrameFactory getInteriorFrameFactory() {
return interiorFrameFactory;
}
@@ -903,7 +905,7 @@
public int getRootPageId() {
return rootPage;
- }
+ }
@Override
public int getFieldCount() {
@@ -914,17 +916,17 @@
public IndexType getIndexType() {
return IndexType.BTREE;
}
-
+
@Override
public int getFileId() {
- return fileId;
+ return fileId;
}
-
+
@Override
public IBufferCache getBufferCache() {
return bufferCache;
}
-
+
public byte getTreeHeight(IBTreeLeafFrame leafFrame) throws HyracksDataException {
ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), false);
rootNode.acquireReadLatch();
@@ -936,26 +938,26 @@
bufferCache.unpin(rootNode);
}
}
-
+
public boolean isEmptyTree(IBTreeLeafFrame leafFrame) throws HyracksDataException {
- ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), false);
+ ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), false);
rootNode.acquireReadLatch();
try {
leafFrame.setPage(rootNode);
if (leafFrame.getLevel() == 0 && leafFrame.getTupleCount() == 0) {
- return true;
+ return true;
} else {
- return false;
+ return false;
}
} finally {
rootNode.releaseReadLatch();
bufferCache.unpin(rootNode);
}
}
-
- @SuppressWarnings("rawtypes")
- public String printTree(IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame, ISerializerDeserializer[] keySerdes)
- throws Exception {
+
+ @SuppressWarnings("rawtypes")
+ public String printTree(IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
+ ISerializerDeserializer[] keySerdes) throws Exception {
MultiComparator cmp = MultiComparator.create(cmpFactories);
byte treeHeight = getTreeHeight(leafFrame);
StringBuilder strBuilder = new StringBuilder();
@@ -963,9 +965,10 @@
return strBuilder.toString();
}
- @SuppressWarnings("rawtypes")
+ @SuppressWarnings("rawtypes")
public void printTree(int pageId, ICachedPage parent, boolean unpin, IBTreeLeafFrame leafFrame,
- IBTreeInteriorFrame interiorFrame, byte treeHeight, ISerializerDeserializer[] keySerdes, StringBuilder strBuilder, MultiComparator cmp) throws Exception {
+ IBTreeInteriorFrame interiorFrame, byte treeHeight, ISerializerDeserializer[] keySerdes,
+ StringBuilder strBuilder, MultiComparator cmp) throws Exception {
ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
node.acquireReadLatch();
try {
@@ -993,7 +996,8 @@
if (!interiorFrame.isLeaf()) {
ArrayList<Integer> children = ((BTreeNSMInteriorFrame) (interiorFrame)).getChildren(cmp);
for (int i = 0; i < children.size(); i++) {
- printTree(children.get(i), node, i == children.size() - 1, leafFrame, interiorFrame, treeHeight, keySerdes, strBuilder, cmp);
+ printTree(children.get(i), node, i == children.size() - 1, leafFrame, interiorFrame, treeHeight,
+ keySerdes, strBuilder, cmp);
}
} else {
node.releaseReadLatch();
@@ -1010,18 +1014,18 @@
public ITreeIndexAccessor createAccessor() {
return new BTreeAccessor(this);
}
-
- // TODO: Class should be private. But currently we need to expose the
- // setOpContext() API to the LSM Tree for it to work correctly.
+
+ // TODO: Class should be private. But currently we need to expose the
+ // setOpContext() API to the LSM Tree for it to work correctly.
public class BTreeAccessor implements ITreeIndexAccessor {
private BTree btree;
private BTreeOpContext ctx;
-
+
public BTreeAccessor(BTree btree) {
this.btree = btree;
this.ctx = btree.createOpContext();
}
-
+
@Override
public void insert(ITupleReference tuple) throws HyracksDataException, TreeIndexException {
ctx.reset(IndexOp.INSERT);
@@ -1039,19 +1043,19 @@
ctx.reset(IndexOp.DELETE);
btree.delete(tuple, ctx);
}
-
+
@Override
public void upsert(ITupleReference tuple) throws HyracksDataException, TreeIndexException {
ctx.reset(IndexOp.UPSERT);
btree.upsert(tuple, ctx);
}
-
+
@Override
- public ITreeIndexCursor createSearchCursor() {
- IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
- return new BTreeRangeSearchCursor(leafFrame, false);
- }
-
+ public ITreeIndexCursor createSearchCursor() {
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
+ return new BTreeRangeSearchCursor(leafFrame, false);
+ }
+
@Override
public void search(IIndexCursor cursor, ISearchPredicate searchPred) throws HyracksDataException,
TreeIndexException {
@@ -1060,22 +1064,22 @@
}
@Override
- public ITreeIndexCursor createDiskOrderScanCursor() {
- IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
- return new TreeDiskOrderScanCursor(leafFrame);
- }
-
+ public ITreeIndexCursor createDiskOrderScanCursor() {
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
+ return new TreeDiskOrderScanCursor(leafFrame);
+ }
+
@Override
public void diskOrderScan(ITreeIndexCursor cursor) throws HyracksDataException {
ctx.reset(IndexOp.DISKORDERSCAN);
btree.diskOrderScan(cursor, ctx);
}
-
- // TODO: Ideally, this method should not exist. But we need it for
- // the changing the leafFrame and leafFrameFactory of the op context for
- // the LSM-BTree to work correctly.
- public BTreeOpContext getOpContext() {
- return ctx;
- }
+
+ // TODO: Ideally, this method should not exist. But we need it for
+ // the changing the leafFrame and leafFrameFactory of the op context for
+ // the LSM-BTree to work correctly.
+ public BTreeOpContext getOpContext() {
+ return ctx;
+ }
}
}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
index c33a8d8..f11ee82 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
@@ -24,16 +24,16 @@
public interface ITreeIndexFrame {
- public void initBuffer(byte level);
-
+ public void initBuffer(byte level);
+
public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple);
-
- public void insert(ITupleReference tuple, int tupleIndex);
-
- public FrameOpSpaceStatus hasSpaceUpdate(ITupleReference newTuple, int oldTupleIndex);
-
- public void update(ITupleReference newTuple, int oldTupleIndex, boolean inPlace);
-
+
+ public void insert(ITupleReference tuple, int tupleIndex);
+
+ public FrameOpSpaceStatus hasSpaceUpdate(ITupleReference newTuple, int oldTupleIndex);
+
+ public void update(ITupleReference newTuple, int oldTupleIndex, boolean inPlace);
+
public void delete(ITupleReference tuple, int tupleIndex);
// returns true if slots were modified, false otherwise
@@ -57,11 +57,11 @@
public ICachedPage getPage();
public ByteBuffer getBuffer();
-
+
// for debugging
public String printHeader();
- public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) throws TreeIndexException;
+ public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey);
public ISlotManager getSlotManager();
@@ -87,6 +87,6 @@
public ITreeIndexTupleWriter getTupleWriter();
public int getPageHeaderSize();
-
+
public ITreeIndexTupleReference createTupleReference();
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
index 84e66ef..6943199 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
@@ -21,7 +21,6 @@
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.rtree.api.IRTreeFrame;
import edu.uci.ics.hyracks.storage.am.rtree.impls.EntriesOrder;
@@ -121,7 +120,7 @@
}
@Override
- public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) throws TreeIndexException {
+ public void split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) {
RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());