Fixed a space calculation bug in the the btree interior frame split. Formatted the code.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@2411 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 c21fa79..354aa1e 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
@@ -118,8 +118,7 @@
int tupleCount = buf.getInt(tupleCountOff);
- // determine start of target free space (depends on assumptions stated
- // above)
+ // determine start of target free space (depends on assumptions stated above)
int freeSpace = buf.getInt(freeSpaceOff);
int prefixTupleCount = buf.getInt(prefixTupleCountOff);
if (prefixTupleCount > 0) {
@@ -184,8 +183,7 @@
int length = tupleSlotOff - slotEndOff;
System.arraycopy(buf.array(), slotEndOff, buf.array(), slotEndOff + slotManager.getSlotSize(), length);
- // maintain space information, get size of tuple suffix (suffix could be
- // entire tuple)
+ // maintain space information, get size of tuple suffix (suffix could be entire tuple)
int tupleSize = 0;
int suffixFieldStart = 0;
if (prefixSlotNum == FieldPrefixSlotManager.TUPLE_UNCOMPRESSED) {
@@ -219,8 +217,7 @@
if (bytesRequired + slotManager.getSlotSize() <= buf.getInt(totalFreeSpaceOff))
return FrameOpSpaceStatus.SUFFICIENT_SPACE;
- // See if the tuple matches a prefix and will fit after truncating the
- // prefix.
+ // See if the tuple matches a prefix and will fit after truncating the prefix.
int prefixSlotNum = slotManager.findPrefix(tuple, framePrefixTuple);
if (prefixSlotNum != FieldPrefixSlotManager.TUPLE_UNCOMPRESSED) {
int prefixSlotOff = slotManager.getPrefixSlotOff(prefixSlotNum);
@@ -269,8 +266,7 @@
int numPrefixFields = frameTuple.getNumPrefixFields();
int fieldCount = frameTuple.getFieldCount();
if (numPrefixFields != 0) {
- // Check the space requirements for updating the suffix of the
- // original tuple.
+ // Check the space requirements for updating the suffix of the original tuple.
oldTupleBytes = frameTuple.getSuffixTupleSize();
newTupleBytes = tupleWriter.bytesRequired(newTuple, numPrefixFields, fieldCount - numPrefixFields);
} else {
@@ -288,8 +284,7 @@
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?
+ // Enough space if we delete the old tuple and insert the new one without compaction?
if (newTupleBytes <= freeContiguous) {
return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
}
@@ -319,8 +314,7 @@
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
+ // 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,
@@ -388,16 +382,14 @@
int tupleIndex = slotManager.decodeSecondSlotField(targetTupleIndex);
// Examine the tuple index to determine whether it is valid or not.
if (tupleIndex != slotManager.getGreatestKeyIndicator()) {
- // We need to check the key to determine whether it's an insert or
- // an update.
+ // We need to check the key to determine whether it's an insert or an update.
frameTuple.resetByTupleIndex(this, tupleIndex);
if (cmp.compare(searchTuple, frameTuple) == 0) {
// The keys match, it's an update.
return frameTuple;
}
}
- // Either the tuple index is a special indicator, or the keys don't
- // match.
+ // Either the tuple index is a special indicator, or the keys don't match.
// In those cases, we are definitely dealing with an insert.
return null;
}
@@ -584,8 +576,7 @@
}
}
- // if we are splitting in the middle of a prefix both pages need to have
- // the prefix slot and tuple
+ // if we are splitting in the middle of a prefix both pages need to have the prefix slot and tuple
int boundaryTupleSlotOff = rf.slotManager.getTupleSlotOff(tuplesToLeft - 1);
int boundaryTupleSlot = buf.getInt(boundaryTupleSlotOff);
int boundaryPrefixSlotNum = rf.slotManager.decodeFirstSlotField(boundaryTupleSlot);
@@ -595,8 +586,7 @@
prefixesToLeft++; // tuples on both pages share one prefix
}
- // move prefix tuples on right page to beginning of page and adjust
- // prefix slots
+ // move prefix tuples on right page to beginning of page and adjust prefix slots
if (prefixesToRight > 0 && prefixesToLeft > 0 && prefixTupleCount > 1) {
int freeSpace = rf.getOrigFreeSpaceOff();
@@ -661,8 +651,7 @@
// insert last key
int targetTupleIndex;
- // it's safe to catch this exception since it will have been caught
- // before reaching here
+ // 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) {
@@ -730,8 +719,7 @@
FindTupleMode ftm, FindTupleNoExactMatchPolicy ftp) {
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.
+ // 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)
return -1;
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 f6c3963..90b167f 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
@@ -94,12 +94,9 @@
System.arraycopy(tuple.getFieldData(tuple.getFieldCount() - 1), getLeftChildPageOff(tuple) + childPtrSize,
buf.array(), rightLeafOff, childPtrSize);
} else {
- // If slotOff has a right (slot-)neighbor then update its child
- // pointer.
- // The only time when this is NOT the case, is when this is the very
- // first tuple
- // (or when the splitkey goes into the rightmost slot but that case
- // is handled in the if above).
+ // If slotOff has a right (slot-)neighbor then update its child pointer.
+ // The only time when this is NOT the case, is when this is the very first tuple
+ // (or when the splitkey goes into the rightmost slot but that case is handled in the if above).
if (buf.getInt(tupleCountOff) > 1) {
int rightNeighborOff = slotOff - slotManager.getSlotSize();
frameTuple.resetByTupleOffset(buf, slotManager.getTupleOff(rightNeighborOff));
@@ -183,8 +180,7 @@
ByteBuffer right = rightFrame.getBuffer();
int tupleCount = getTupleCount();
- // Find split point, and determine into which frame the new tuple should
- // be inserted into.
+ // Find split point, and determine into which frame the new tuple should be inserted into.
int tuplesToLeft;
ITreeIndexFrame targetFrame = null;
@@ -193,7 +189,7 @@
int i;
for (i = 0; i < tupleCount; ++i) {
frameTuple.resetByTupleIndex(this, i);
- totalSize += tupleWriter.bytesRequired(frameTuple) + slotManager.getSlotSize();
+ totalSize += tupleWriter.bytesRequired(frameTuple) + childPtrSize + slotManager.getSlotSize();
if (totalSize >= halfPageSize) {
break;
}
@@ -225,8 +221,7 @@
// Copy the split key to be inserted.
// We must do so because setting the new split key will overwrite the
- // old split key, and we cannot insert the existing split key at this
- // point.
+ // old split key, and we cannot insert the existing split key at this point.
ISplitKey savedSplitKey = splitKey.duplicate(tupleWriter.createTupleReference());
// Set split key to be highest value in left page.
@@ -248,8 +243,7 @@
// Insert the saved split key.
int targetTupleIndex;
- // it's safe to catch this exception since it will have been caught
- // before reaching here
+ // 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) {
@@ -302,7 +296,6 @@
FindTupleMode fsm = null;
// The target comparator may be on a prefix of the BTree key fields.
MultiComparator targetCmp = pred.getLowKeyComparator();
- ;
tuple = pred.getLowKey();
if (tuple == null) {
return getLeftmostChildPageId();
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriter.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriter.java
index 069ede8..43991f1 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriter.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexTupleWriter.java
@@ -21,24 +21,22 @@
public interface ITreeIndexTupleWriter {
public int writeTuple(ITupleReference tuple, ByteBuffer targetBuf, int targetOff);
-
+
public int writeTuple(ITupleReference tuple, byte[] targetBuf, int targetOff);
public int bytesRequired(ITupleReference tuple);
- public int writeTupleFields(ITupleReference tuple, int startField, int numFields, byte[] targetBuf,
- int targetOff);
+ public int writeTupleFields(ITupleReference tuple, int startField, int numFields, byte[] targetBuf, int targetOff);
public int bytesRequired(ITupleReference tuple, int startField, int numFields);
// return a tuplereference instance that can read the tuple written by this
- // writer
- // the main idea is that the format of the written tuple may not be the same
+ // writer the main idea is that the format of the written tuple may not be the same
// as the format written by this writer
public ITreeIndexTupleReference createTupleReference();
-
+
// This method is only used by the BTree leaf frame split method since tuples
- // in the LSM-BTree can be either matter or anti-matter tuple and we want to
+ // in the LSM-BTree can be either matter or anti-matter tuples and we want
// to calculate the size of all tuples in the frame.
public int getCopySpaceRequired(ITupleReference tuple);
}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriter.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriter.java
index 8cd8d98..8c41dd3 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriter.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/SimpleTupleWriter.java
@@ -114,6 +114,7 @@
return numFields * 2;
}
+ @Override
public int getCopySpaceRequired(ITupleReference tuple) {
return bytesRequired(tuple);
}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriter.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriter.java
index ab14441..1e12bea 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriter.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/tuples/TypeAwareTupleWriter.java
@@ -148,6 +148,7 @@
this.typeTraits = typeTraits;
}
+ @Override
public int getCopySpaceRequired(ITupleReference tuple) {
return bytesRequired(tuple);
}
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/tuples/LSMBTreeTupleWriter.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/tuples/LSMBTreeTupleWriter.java
index 5943a82..12aca6f 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/tuples/LSMBTreeTupleWriter.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/tuples/LSMBTreeTupleWriter.java
@@ -21,61 +21,61 @@
import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriter;
public class LSMBTreeTupleWriter extends TypeAwareTupleWriter {
- private final boolean isAntimatter;
- private final int numKeyFields;
-
- public LSMBTreeTupleWriter(ITypeTraits[] typeTraits, int numKeyFields, boolean isAntimatter) {
- super(typeTraits);
- this.numKeyFields = numKeyFields;
- this.isAntimatter = isAntimatter;
- }
+ private final boolean isAntimatter;
+ private final int numKeyFields;
- @Override
- public int bytesRequired(ITupleReference tuple) {
- if (isAntimatter) {
- // Only requires space for the key fields.
- return super.bytesRequired(tuple, 0, numKeyFields);
- } else {
- return super.bytesRequired(tuple);
- }
+ public LSMBTreeTupleWriter(ITypeTraits[] typeTraits, int numKeyFields, boolean isAntimatter) {
+ super(typeTraits);
+ this.numKeyFields = numKeyFields;
+ this.isAntimatter = isAntimatter;
}
-
- @Override
- public int getCopySpaceRequired(ITupleReference tuple) {
+
+ @Override
+ public int bytesRequired(ITupleReference tuple) {
+ if (isAntimatter) {
+ // Only requires space for the key fields.
+ return super.bytesRequired(tuple, 0, numKeyFields);
+ } else {
+ return super.bytesRequired(tuple);
+ }
+ }
+
+ @Override
+ public int getCopySpaceRequired(ITupleReference tuple) {
return super.bytesRequired(tuple);
}
-
- @Override
+
+ @Override
public ITreeIndexTupleReference createTupleReference() {
return new LSMBTreeTupleReference(typeTraits, numKeyFields);
}
-
- @Override
- protected int getNullFlagsBytes(int numFields) {
- // +1.0 is for matter/antimatter bit.
- return (int) Math.ceil(((double) numFields + 1.0) / 8.0);
+
+ @Override
+ protected int getNullFlagsBytes(int numFields) {
+ // +1.0 is for matter/antimatter bit.
+ return (int) Math.ceil(((double) numFields + 1.0) / 8.0);
}
-
- @Override
+
+ @Override
protected int getNullFlagsBytes(ITupleReference tuple) {
- // +1.0 is for matter/antimatter bit.
+ // +1.0 is for matter/antimatter bit.
return (int) Math.ceil(((double) tuple.getFieldCount() + 1.0) / 8.0);
}
-
- @Override
- public int writeTuple(ITupleReference tuple, byte[] targetBuf, int targetOff) {
- int bytesWritten = -1;
- if (isAntimatter) {
- bytesWritten = super.writeTupleFields(tuple, 0, numKeyFields, targetBuf, targetOff);
- setAntimatterBit(targetBuf, targetOff);
- } else {
- bytesWritten = super.writeTuple(tuple, targetBuf, targetOff);
- }
- return bytesWritten;
+
+ @Override
+ public int writeTuple(ITupleReference tuple, byte[] targetBuf, int targetOff) {
+ int bytesWritten = -1;
+ if (isAntimatter) {
+ bytesWritten = super.writeTupleFields(tuple, 0, numKeyFields, targetBuf, targetOff);
+ setAntimatterBit(targetBuf, targetOff);
+ } else {
+ bytesWritten = super.writeTuple(tuple, targetBuf, targetOff);
+ }
+ return bytesWritten;
}
-
- private void setAntimatterBit(byte[] targetBuf, int targetOff) {
- // Set leftmost bit to 1.
- targetBuf[targetOff] = (byte) (targetBuf[targetOff] | (1 << 7));
- }
+
+ private void setAntimatterBit(byte[] targetBuf, int targetOff) {
+ // Set leftmost bit to 1.
+ targetBuf[targetOff] = (byte) (targetBuf[targetOff] | (1 << 7));
+ }
}
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexExamplesTest.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexExamplesTest.java
index 759a292..770a2ad 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexExamplesTest.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexExamplesTest.java
@@ -136,8 +136,11 @@
/**
* This test the btree page split. Originally this test didn't pass since
- * the btree was spliting by cardinality and not size. Now, it split page by
- * size.
+ * the btree was spliting by cardinality and not size. Thus, we might end
+ * up with a situation where there is not enough space to insert the new
+ * tuple after the split which will throw an error and the split won't be
+ * propagated to upper level; thus, the tree is corrupted. Now, it split
+ * page by size. The correct behavior on abnormally large keys/values.
*/
@Test
public void pageSplitTestExample() throws Exception {