Refactoring in preparation of performance improvements for BTree searches.
git-svn-id: https://hyracks.googlecode.com/svn/trunk/hyracks@235 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ISlotManager.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ISlotManager.java
index a9a7999..14cf579 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ISlotManager.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ISlotManager.java
@@ -22,8 +22,8 @@
public interface ISlotManager {
public void setFrame(IBTreeFrame frame);
- public int findSlot(ITupleReference tuple, IBTreeTupleReference pageTuple, MultiComparator multiCmp, FindSlotMode mode);
- public int insertSlot(int slotOff, int tupleOff);
+ public int findTupleIndex(ITupleReference tuple, IBTreeTupleReference pageTuple, MultiComparator multiCmp, FindSlotMode mode);
+ public int insertSlot(int tupleIndex, int tupleOff);
public int getSlotStartOff();
public int getSlotEndOff();
@@ -31,7 +31,7 @@
public int getTupleOff(int slotOff);
public void setSlot(int slotOff, int value);
- public int getSlotOff(int slotNum);
+ public int getSlotOff(int tupleIndex);
public int getSlotSize();
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMFrame.java
index a613cfc..ec578b8 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMFrame.java
@@ -157,8 +157,9 @@
@Override
public void delete(ITupleReference tuple, MultiComparator cmp, boolean exactDelete) throws Exception {
frameTuple.setFieldCount(cmp.getFieldCount());
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_EXACT);
- if(slotOff < 0) {
+ int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindSlotMode.FSM_EXACT);
+ int slotOff = slotManager.getSlotOff(tupleIndex);
+ if(tupleIndex < 0) {
throw new BTreeException("Key to be deleted does not exist.");
}
else {
@@ -210,8 +211,8 @@
@Override
public void insert(ITupleReference tuple, MultiComparator cmp) throws Exception {
frameTuple.setFieldCount(cmp.getFieldCount());
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_INCLUSIVE);
- slotOff = slotManager.insertSlot(slotOff, buf.getInt(freeSpaceOff));
+ int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindSlotMode.FSM_INCLUSIVE);
+ slotManager.insertSlot(tupleIndex, buf.getInt(freeSpaceOff));
int bytesWritten = tupleWriter.writeTuple(tuple, buf, buf.getInt(freeSpaceOff));
buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrame.java
index c0c5340..6d50461 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrame.java
@@ -72,11 +72,12 @@
@Override
public void insert(ITupleReference tuple, MultiComparator cmp) throws Exception {
- frameTuple.setFieldCount(cmp.getKeyFieldCount());
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_INCLUSIVE);
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+ int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindSlotMode.FSM_INCLUSIVE);
+ int slotOff = slotManager.getSlotOff(tupleIndex);
boolean isDuplicate = true;
- if(slotOff < 0) isDuplicate = false; // greater than all existing keys
+ if(tupleIndex < 0) isDuplicate = false; // greater than all existing keys
else {
frameTuple.resetByOffset(buf, slotManager.getTupleOff(slotOff));
if(cmp.compare(tuple, frameTuple) != 0) isDuplicate = false;
@@ -86,7 +87,7 @@
throw new BTreeException("Trying to insert duplicate value into interior node.");
}
else {
- slotOff = slotManager.insertSlot(slotOff, buf.getInt(freeSpaceOff));
+ slotOff = slotManager.insertSlot(tupleIndex, buf.getInt(freeSpaceOff));
int freeSpace = buf.getInt(freeSpaceOff);
int bytesWritten = tupleWriter.writeTupleFields(tuple, 0, cmp.getKeyFieldCount(), buf, freeSpace);
@@ -131,8 +132,9 @@
public int split(IBTreeFrame rightFrame, ITupleReference tuple, MultiComparator cmp, SplitKey splitKey) throws Exception {
// before doing anything check if key already exists
frameTuple.setFieldCount(cmp.getKeyFieldCount());
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_EXACT);
- if(slotOff >= 0) {
+ int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindSlotMode.FSM_EXACT);
+ int slotOff = slotManager.getSlotOff(tupleIndex);
+ if(tupleIndex >= 0) {
frameTuple.resetByOffset(buf, slotManager.getTupleOff(slotOff));
if(cmp.compare(tuple, frameTuple) == 0) {
throw new BTreeException("Inserting duplicate key in interior node during split");
@@ -256,8 +258,9 @@
}
MultiComparator targetCmp = pred.getComparator();
- int slotOff = slotManager.findSlot(tuple, frameTuple, targetCmp, fsm);
- if(slotOff < 0) {
+ int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, targetCmp, fsm);
+ int slotOff = slotManager.getSlotOff(tupleIndex);
+ if(tupleIndex < 0) {
return buf.getInt(rightLeafOff);
}
else {
@@ -296,11 +299,12 @@
@Override
public void delete(ITupleReference tuple, MultiComparator cmp, boolean exactDelete) throws Exception {
frameTuple.setFieldCount(cmp.getKeyFieldCount());
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_INCLUSIVE);
+ int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindSlotMode.FSM_INCLUSIVE);
+ int slotOff = slotManager.getSlotOff(tupleIndex);
int tupleOff;
int keySize;
- if(slotOff < 0) {
+ if(tupleIndex < 0) {
tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
frameTuple.resetByOffset(buf, tupleOff);
keySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrame.java
index 0fa8c2d..bcf6ef8 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrame.java
@@ -65,10 +65,11 @@
@Override
public void insert(ITupleReference tuple, MultiComparator cmp) throws Exception {
frameTuple.setFieldCount(cmp.getFieldCount());
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_INCLUSIVE);
+ int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindSlotMode.FSM_INCLUSIVE);
+ int slotOff = slotManager.getSlotOff(tupleIndex);
boolean isDuplicate = true;
-
- if (slotOff < 0) isDuplicate = false; // greater than all existing keys
+
+ if (tupleIndex < 0) isDuplicate = false; // greater than all existing keys
else {
frameTuple.resetByOffset(buf, slotManager.getTupleOff(slotOff));
if (cmp.compare(tuple, frameTuple) != 0) isDuplicate = false;
@@ -78,7 +79,7 @@
throw new BTreeException("Trying to insert duplicate value into leaf of unique index");
}
else {
- slotOff = slotManager.insertSlot(slotOff, buf.getInt(freeSpaceOff));
+ slotOff = slotManager.insertSlot(tupleIndex, buf.getInt(freeSpaceOff));
int freeSpace = buf.getInt(freeSpaceOff);
int bytesWritten = tupleWriter.writeTuple(tuple, buf, freeSpace);
@@ -105,9 +106,9 @@
frameTuple.setFieldCount(cmp.getFieldCount());
// before doing anything check if key already exists
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_EXACT);
- if (slotOff >= 0) {
- frameTuple.resetByOffset(buf, slotManager.getTupleOff(slotOff));
+ int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindSlotMode.FSM_EXACT);
+ if (tupleIndex >= 0) {
+ frameTuple.resetByTupleIndex(this, tupleIndex);
if (cmp.compare(tuple, frameTuple) == 0) {
throw new BTreeException("Inserting duplicate key into unique index");
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/OrderedSlotManager.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/OrderedSlotManager.java
index a1d6089..bbbd965 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/OrderedSlotManager.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/OrderedSlotManager.java
@@ -26,7 +26,7 @@
private IBTreeFrame frame;
@Override
- public int findSlot(ITupleReference tuple, IBTreeTupleReference pageTuple, MultiComparator multiCmp, FindSlotMode mode) {
+ public int findTupleIndex(ITupleReference tuple, IBTreeTupleReference pageTuple, MultiComparator multiCmp, FindSlotMode mode) {
if(frame.getTupleCount() <= 0) return -1;
int mid;
@@ -34,10 +34,8 @@
int end = frame.getTupleCount() - 1;
while(begin <= end) {
- mid = (begin + end) / 2;
- int slotOff = getSlotOff(mid);
- int tupleOff = getTupleOff(slotOff);
- pageTuple.resetByOffset(frame.getBuffer(), tupleOff);
+ mid = (begin + end) / 2;
+ pageTuple.resetByTupleIndex(frame, mid);
int cmp = multiCmp.compare(tuple, pageTuple);
if(cmp < 0) {
@@ -51,19 +49,17 @@
begin = mid + 1;
}
else {
- return slotOff;
+ return mid;
}
}
}
if(mode == FindSlotMode.FSM_EXACT) return -1;
if(begin > frame.getTupleCount() - 1) return -1;
-
- int slotOff = getSlotOff(begin);
- int tupleOff = getTupleOff(slotOff);
- pageTuple.resetByOffset(frame.getBuffer(), tupleOff);
+
+ pageTuple.resetByTupleIndex(frame, begin);
if(multiCmp.compare(tuple, pageTuple) < 0)
- return slotOff;
+ return begin;
else
return -1;
}
@@ -94,8 +90,9 @@
}
@Override
- public int insertSlot(int slotOff, int tupleOff) {
- if(slotOff < 0) {
+ public int insertSlot(int tupleIndex, int tupleOff) {
+ int slotOff = getSlotOff(tupleIndex);
+ if(tupleIndex < 0) {
slotOff = getSlotEndOff() - slotSize;
setSlot(slotOff, tupleOff);
return slotOff;
@@ -115,7 +112,7 @@
}
@Override
- public int getSlotOff(int slotNum) {
- return getSlotStartOff() - slotNum * slotSize;
+ public int getSlotOff(int tupleIndex) {
+ return getSlotStartOff() - tupleIndex * slotSize;
}
}
