Added support for open intervals in BTree searches.
git-svn-id: https://hyracks.googlecode.com/svn/trunk/hyracks@210 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-examples/hyracks-integration-tests/src/test/java/edu/uci/ics/hyracks/tests/btree/BTreeOperatorsTest.java b/hyracks-examples/hyracks-integration-tests/src/test/java/edu/uci/ics/hyracks/tests/btree/BTreeOperatorsTest.java
index 37027f7..7269a01 100644
--- a/hyracks-examples/hyracks-integration-tests/src/test/java/edu/uci/ics/hyracks/tests/btree/BTreeOperatorsTest.java
+++ b/hyracks-examples/hyracks-integration-tests/src/test/java/edu/uci/ics/hyracks/tests/btree/BTreeOperatorsTest.java
@@ -159,7 +159,7 @@
int btreeFileId = 0; // TODO: this relies on the way FileMappingProvider assigns ids (in sequence starting from 0)
BTree btree = btreeRegistryProvider.getBTreeRegistry().get(btreeFileId);
IBTreeCursor scanCursor = new RangeSearchCursor(leafFrameFactory.getFrame());
- RangePredicate nullPred = new RangePredicate(true, null, null, null);
+ RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null);
btree.search(scanCursor, nullPred, leafFrameFactory.getFrame(), interiorFrameFactory.getFrame());
try {
while (scanCursor.hasNext()) {
@@ -235,7 +235,7 @@
IFileSplitProvider btreeSplitProvider = new ConstantFileSplitProvider(
new FileSplit[] { new FileSplit(NC1_ID, new File(nc1FileName)) } );
- BTreeSearchOperatorDescriptor btreeSearchOp = new BTreeSearchOperatorDescriptor(spec, recDesc, bufferCacheProvider, btreeRegistryProvider, btreeSplitProvider, fileMappingProviderProvider, interiorFrameFactory, leafFrameFactory, typeTraits, comparatorFactories, true, new int[]{0}, new int[]{1});
+ BTreeSearchOperatorDescriptor btreeSearchOp = new BTreeSearchOperatorDescriptor(spec, recDesc, bufferCacheProvider, btreeRegistryProvider, btreeSplitProvider, fileMappingProviderProvider, interiorFrameFactory, leafFrameFactory, typeTraits, comparatorFactories, true, new int[]{0}, new int[]{1}, true, true);
//BTreeDiskOrderScanOperatorDescriptor btreeSearchOp = new BTreeDiskOrderScanOperatorDescriptor(spec, splitProvider, recDesc, bufferCacheProvider, btreeRegistryProvider, 0, "btreetest.bin", interiorFrameFactory, leafFrameFactory, cmp);
PartitionConstraint btreePartitionConstraint = new ExplicitPartitionConstraint(new LocationConstraint[] { new AbsoluteLocationConstraint(NC1_ID) });
@@ -421,7 +421,7 @@
// scan primary index
System.out.println("PRINTING PRIMARY INDEX");
IBTreeCursor scanCursorA = new RangeSearchCursor(primaryLeafFrameFactory.getFrame());
- RangePredicate nullPredA = new RangePredicate(true, null, null, null);
+ RangePredicate nullPredA = new RangePredicate(true, null, null, true, true, null);
btreeA.search(scanCursorA, nullPredA, primaryLeafFrameFactory.getFrame(), primaryInteriorFrameFactory.getFrame());
try {
while (scanCursorA.hasNext()) {
@@ -440,7 +440,7 @@
// scan first secondary index
System.out.println("PRINTING FIRST SECONDARY INDEX");
IBTreeCursor scanCursorB = new RangeSearchCursor(secondaryLeafFrameFactory.getFrame());
- RangePredicate nullPredB = new RangePredicate(true, null, null, null);
+ RangePredicate nullPredB = new RangePredicate(true, null, null, true, true, null);
btreeB.search(scanCursorB, nullPredB, secondaryLeafFrameFactory.getFrame(), secondaryInteriorFrameFactory.getFrame());
try {
while (scanCursorB.hasNext()) {
@@ -459,7 +459,7 @@
// scan second secondary index
System.out.println("PRINTING SECOND SECONDARY INDEX");
IBTreeCursor scanCursorC = new RangeSearchCursor(secondaryLeafFrameFactory.getFrame());
- RangePredicate nullPredC = new RangePredicate(true, null, null, null);
+ RangePredicate nullPredC = new RangePredicate(true, null, null, true, true, null);
btreeC.search(scanCursorC, nullPredC, secondaryLeafFrameFactory.getFrame(), secondaryInteriorFrameFactory.getFrame());
try {
while (scanCursorC.hasNext()) {
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 e289c73..a9a7999 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
@@ -16,12 +16,13 @@
package edu.uci.ics.hyracks.storage.am.btree.api;
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.impls.FindSlotMode;
import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
public interface ISlotManager {
public void setFrame(IBTreeFrame frame);
- public int findSlot(ITupleReference tuple, IBTreeTupleReference pageTuple, MultiComparator multiCmp, boolean exact);
+ public int findSlot(ITupleReference tuple, IBTreeTupleReference pageTuple, MultiComparator multiCmp, FindSlotMode mode);
public int insertSlot(int slotOff, int tupleOff);
public int getSlotStartOff();
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorNodePushable.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorNodePushable.java
index 0690dbf..dc02c2e 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorNodePushable.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeInsertUpdateDeleteOperatorNodePushable.java
@@ -102,8 +102,8 @@
@Override
public void open() throws HyracksDataException {
AbstractBTreeOperatorDescriptor opDesc = btreeOpHelper.getOperatorDescriptor();
- RecordDescriptor recDesc = recordDescProvider.getInputRecordDescriptor(opDesc.getOperatorId(), 0);
- accessor = new FrameTupleAccessor(btreeOpHelper.getHyracksContext(), recDesc);
+ RecordDescriptor inputRecDesc = recordDescProvider.getInputRecordDescriptor(opDesc.getOperatorId(), 0);
+ accessor = new FrameTupleAccessor(btreeOpHelper.getHyracksContext(), inputRecDesc);
writeBuffer = btreeOpHelper.getHyracksContext().getResourceManager().allocateFrame();
try {
btreeOpHelper.init();
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorDescriptor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorDescriptor.java
index d31766d..de842fd 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorDescriptor.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorDescriptor.java
@@ -31,11 +31,13 @@
private static final long serialVersionUID = 1L;
- private boolean isForward;
+ private boolean isForward;
private int[] lowKeyFields; // fields in input tuple to be used as low keys
private int[] highKeyFields; // fields in input tuple to be used as high keys
+ private boolean lowKeyInclusive;
+ private boolean highKeyInclusive;
- public BTreeSearchOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc, IBufferCacheProvider bufferCacheProvider, IBTreeRegistryProvider btreeRegistryProvider, IFileSplitProvider fileSplitProvider, IFileMappingProviderProvider fileMappingProviderProvider, IBTreeInteriorFrameFactory interiorFactory, IBTreeLeafFrameFactory leafFactory, ITypeTrait[] typeTraits, IBinaryComparatorFactory[] comparatorFactories, boolean isForward, int[] lowKeyFields, int[] highKeyFields) {
+ public BTreeSearchOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc, IBufferCacheProvider bufferCacheProvider, IBTreeRegistryProvider btreeRegistryProvider, IFileSplitProvider fileSplitProvider, IFileMappingProviderProvider fileMappingProviderProvider, IBTreeInteriorFrameFactory interiorFactory, IBTreeLeafFrameFactory leafFactory, ITypeTrait[] typeTraits, IBinaryComparatorFactory[] comparatorFactories, boolean isForward, int[] lowKeyFields, int[] highKeyFields, boolean lowKeyInclusive, boolean highKeyInclusive) {
super(spec, 1, 1, recDesc, bufferCacheProvider, btreeRegistryProvider, fileSplitProvider, fileMappingProviderProvider, interiorFactory, leafFactory, typeTraits, comparatorFactories);
this.isForward = isForward;
this.lowKeyFields = lowKeyFields;
@@ -45,6 +47,6 @@
@Override
public IOperatorNodePushable createPushRuntime(final IHyracksContext ctx, final IOperatorEnvironment env,
IRecordDescriptorProvider recordDescProvider, int partition, int nPartitions) {
- return new BTreeSearchOperatorNodePushable(this, ctx, partition, recordDescProvider, isForward, lowKeyFields, highKeyFields);
+ return new BTreeSearchOperatorNodePushable(this, ctx, partition, recordDescProvider, isForward, lowKeyFields, highKeyFields, lowKeyInclusive, highKeyInclusive);
}
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorNodePushable.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorNodePushable.java
index 7d23ba3..2b69d9d 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorNodePushable.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/dataflow/BTreeSearchOperatorNodePushable.java
@@ -37,8 +37,7 @@
import edu.uci.ics.hyracks.storage.am.btree.impls.RangeSearchCursor;
public class BTreeSearchOperatorNodePushable extends AbstractUnaryInputUnaryOutputOperatorNodePushable {
- private BTreeOpHelper btreeOpHelper;
- private boolean isForward;
+ private BTreeOpHelper btreeOpHelper;
private FrameTupleAccessor accessor;
private ByteBuffer writeBuffer;
@@ -47,20 +46,25 @@
private DataOutput dos;
private BTree btree;
+ private boolean isForward;
private PermutingFrameTupleReference lowKey;
- private PermutingFrameTupleReference highKey;
+ private PermutingFrameTupleReference highKey;
+ private boolean lowKeyInclusive;
+ private boolean highKeyInclusive;
private RangePredicate rangePred;
private MultiComparator searchCmp;
private IBTreeCursor cursor;
private IBTreeLeafFrame leafFrame;
private IBTreeLeafFrame cursorFrame;
- private IBTreeInteriorFrame interiorFrame;
+ private IBTreeInteriorFrame interiorFrame;
private RecordDescriptor recDesc;
- public BTreeSearchOperatorNodePushable(AbstractBTreeOperatorDescriptor opDesc, IHyracksContext ctx, int partition, IRecordDescriptorProvider recordDescProvider, boolean isForward, int[] lowKeyFields, int[] highKeyFields) {
+ public BTreeSearchOperatorNodePushable(AbstractBTreeOperatorDescriptor opDesc, IHyracksContext ctx, int partition, IRecordDescriptorProvider recordDescProvider, boolean isForward, int[] lowKeyFields, int[] highKeyFields, boolean lowKeyInclusive, boolean highKeyInclusive) {
btreeOpHelper = new BTreeOpHelper(opDesc, ctx, partition, BTreeOpHelper.BTreeMode.OPEN_BTREE);
- this.isForward = isForward;
+ this.isForward = isForward;
+ this.lowKeyInclusive = lowKeyInclusive;
+ this.highKeyInclusive = highKeyInclusive;
this.recDesc = recordDescProvider.getInputRecordDescriptor(opDesc.getOperatorId(), 0);
if(lowKeyFields != null && lowKeyFields.length > 0) {
lowKey = new PermutingFrameTupleReference();
@@ -100,7 +104,7 @@
}
searchCmp = new MultiComparator(btree.getMultiComparator().getTypeTraits(), searchComparators);
- rangePred = new RangePredicate(isForward, null, null, searchCmp);
+ rangePred = new RangePredicate(isForward, null, null, lowKeyInclusive, highKeyInclusive, searchCmp);
accessor = new FrameTupleAccessor(btreeOpHelper.getHyracksContext(), recDesc);
@@ -141,8 +145,8 @@
for (int i = 0; i < tupleCount; i++) {
if(lowKey != null) lowKey.reset(accessor, i);
if(highKey != null) highKey.reset(accessor, i);
- rangePred.setLowKey(lowKey);
- rangePred.setHighKey(highKey);
+ rangePred.setLowKey(lowKey, lowKeyInclusive);
+ rangePred.setHighKey(highKey, highKeyInclusive);
cursor.reset();
btree.search(cursor, rangePred, leafFrame, interiorFrame);
@@ -151,14 +155,13 @@
} catch (Exception e) {
throw new HyracksDataException(e);
}
- }
+ }
@Override
public void close() throws HyracksDataException {
if (appender.getTupleCount() > 0) {
FrameUtils.flushFrame(writeBuffer, writer);
- }
-
+ }
writer.close();
try {
cursor.close();
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 dc856ce..a613cfc 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
@@ -30,6 +30,7 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
import edu.uci.ics.hyracks.storage.am.btree.api.ISlotManager;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.impls.FindSlotMode;
import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
import edu.uci.ics.hyracks.storage.am.btree.impls.OrderedSlotManager;
import edu.uci.ics.hyracks.storage.am.btree.impls.SlotOffTupleOff;
@@ -156,7 +157,7 @@
@Override
public void delete(ITupleReference tuple, MultiComparator cmp, boolean exactDelete) throws Exception {
frameTuple.setFieldCount(cmp.getFieldCount());
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, true);
+ int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_EXACT);
if(slotOff < 0) {
throw new BTreeException("Key to be deleted does not exist.");
}
@@ -209,7 +210,7 @@
@Override
public void insert(ITupleReference tuple, MultiComparator cmp) throws Exception {
frameTuple.setFieldCount(cmp.getFieldCount());
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, false);
+ int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_INCLUSIVE);
slotOff = slotManager.insertSlot(slotOff, buf.getInt(freeSpaceOff));
int bytesWritten = tupleWriter.writeTuple(tuple, buf, buf.getInt(freeSpaceOff));
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 fc4659a..c0c5340 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
@@ -30,6 +30,7 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleReference;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.impls.FindSlotMode;
import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
import edu.uci.ics.hyracks.storage.am.btree.impls.SlotOffTupleOff;
@@ -72,7 +73,7 @@
@Override
public void insert(ITupleReference tuple, MultiComparator cmp) throws Exception {
frameTuple.setFieldCount(cmp.getKeyFieldCount());
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, false);
+ int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_INCLUSIVE);
boolean isDuplicate = true;
if(slotOff < 0) isDuplicate = false; // greater than all existing keys
@@ -130,7 +131,7 @@
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, true);
+ int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_EXACT);
if(slotOff >= 0) {
frameTuple.resetByOffset(buf, slotManager.getTupleOff(slotOff));
if(cmp.compare(tuple, frameTuple) == 0) {
@@ -237,22 +238,26 @@
// check for trivial cases where no low key or high key exists (e.g. during an index scan)
ITupleReference tuple = null;
+ FindSlotMode fsm = null;
if(pred.isForward()) {
tuple = pred.getLowKey();
if(tuple == null) {
return getLeftmostChildPageId(srcCmp);
- }
+ }
+ if(pred.isLowKeyInclusive()) fsm = FindSlotMode.FSM_INCLUSIVE;
+ else fsm = FindSlotMode.FSM_EXCLUSIVE;
}
else {
tuple = pred.getHighKey();
if(tuple == null) {
return getRightmostChildPageId(srcCmp);
- }
+ }
+ fsm = FindSlotMode.FSM_INCLUSIVE;
}
MultiComparator targetCmp = pred.getComparator();
- int slotOff = slotManager.findSlot(tuple, frameTuple, targetCmp, false);
- if(slotOff < 0) {
+ int slotOff = slotManager.findSlot(tuple, frameTuple, targetCmp, fsm);
+ if(slotOff < 0) {
return buf.getInt(rightLeafOff);
}
else {
@@ -291,7 +296,7 @@
@Override
public void delete(ITupleReference tuple, MultiComparator cmp, boolean exactDelete) throws Exception {
frameTuple.setFieldCount(cmp.getKeyFieldCount());
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, false);
+ int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_INCLUSIVE);
int tupleOff;
int keySize;
@@ -344,9 +349,7 @@
}
// for debugging
- public ArrayList<Integer> getChildren(MultiComparator cmp) {
- System.out.println(page);
-
+ public ArrayList<Integer> getChildren(MultiComparator cmp) {
ArrayList<Integer> ret = new ArrayList<Integer>();
frameTuple.setFieldCount(cmp.getKeyFieldCount());
int tupleCount = buf.getInt(tupleCountOff);
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 0f5c1fa..363ab23 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
@@ -22,6 +22,7 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeTupleWriter;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.impls.FindSlotMode;
import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
import edu.uci.ics.hyracks.storage.am.btree.impls.SplitKey;
@@ -63,7 +64,7 @@
@Override
public void insert(ITupleReference tuple, MultiComparator cmp) throws Exception {
frameTuple.setFieldCount(cmp.getFieldCount());
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, false);
+ int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_INCLUSIVE);
boolean isDuplicate = true;
if (slotOff < 0) isDuplicate = false; // greater than all existing keys
@@ -103,7 +104,7 @@
frameTuple.setFieldCount(cmp.getFieldCount());
// before doing anything check if key already exists
- int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, true);
+ int slotOff = slotManager.findSlot(tuple, frameTuple, cmp, FindSlotMode.FSM_EXACT);
if (slotOff >= 0) {
frameTuple.resetByOffset(buf, slotManager.getTupleOff(slotOff));
if (cmp.compare(tuple, frameTuple) == 0) {
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 e48123c..7a74bf8 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
@@ -44,7 +44,7 @@
private final int metaDataPage = 0; // page containing meta data, e.g., maxPage
private final int rootPage = 1; // the root page never changes
- private boolean created = false;
+ private boolean created = false;
private boolean loaded = false;
private final IBufferCache bufferCache;
@@ -98,7 +98,7 @@
this.leafFrameFactory = leafFrameFactory;
this.cmp = cmp;
this.treeLatch = new ReentrantReadWriteLock(true);
- this.diskOrderScanPredicate = new RangePredicate(true, null, null, cmp);
+ this.diskOrderScanPredicate = new RangePredicate(true, null, null, true, true, cmp);
}
public void create(int fileId, IBTreeLeafFrame leafFrame, IBTreeMetaDataFrame metaFrame) throws Exception {
@@ -529,7 +529,7 @@
ctx.leafFrame = leafFrame;
ctx.interiorFrame = interiorFrame;
ctx.metaFrame = metaFrame;
- ctx.pred = new RangePredicate(true, tuple, tuple, cmp);
+ ctx.pred = new RangePredicate(true, tuple, tuple, true, true, cmp);
ctx.splitKey = new SplitKey(leafFrame.getTupleWriter().createTupleReference());
ctx.splitKey.getTuple().setFieldCount(cmp.getKeyFieldCount());
ctx.smPages = new ArrayList<Integer>();
@@ -766,13 +766,13 @@
ctx.leafFrame = leafFrame;
ctx.interiorFrame = interiorFrame;
ctx.metaFrame = metaFrame;
- ctx.pred = new RangePredicate(true, tuple, tuple, cmp);
+ ctx.pred = new RangePredicate(true, tuple, tuple, true, true, cmp);
ctx.splitKey = new SplitKey(leafFrame.getTupleWriter().createTupleReference());
ctx.splitKey.getTuple().setFieldCount(cmp.getKeyFieldCount());
ctx.smPages = new ArrayList<Integer>();
ctx.pageLsns = new Stack<Integer>();
ctx.freePages = new ArrayList<Integer>();
-
+
boolean repeatOp = true;
// we use this loop to deal with possibly multiple operation restarts
// due to ongoing structure modifications during the descent
@@ -1145,8 +1145,7 @@
}
throw e;
} catch (Exception e) { // this could be caused, e.g. by a
- // failure to pin a new node during a
- // split
+ // failure to pin a new node during a split
System.out.println("ASTERIX EXCEPTION");
e.printStackTrace();
releaseLatch(node, ctx.op, isLeaf);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FindSlotMode.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FindSlotMode.java
new file mode 100644
index 0000000..c1d878f
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FindSlotMode.java
@@ -0,0 +1,7 @@
+package edu.uci.ics.hyracks.storage.am.btree.impls;
+
+public enum FindSlotMode {
+ FSM_INCLUSIVE,
+ FSM_EXCLUSIVE,
+ FSM_EXACT
+}
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 db9ee0e..a1d6089 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
@@ -25,15 +25,14 @@
private static final int slotSize = 4;
private IBTreeFrame frame;
- // TODO: mix in interpolation search
@Override
- public int findSlot(ITupleReference tuple, IBTreeTupleReference pageTuple, MultiComparator multiCmp, boolean exact) {
+ public int findSlot(ITupleReference tuple, IBTreeTupleReference pageTuple, MultiComparator multiCmp, FindSlotMode mode) {
if(frame.getTupleCount() <= 0) return -1;
int mid;
int begin = 0;
int end = frame.getTupleCount() - 1;
-
+
while(begin <= end) {
mid = (begin + end) / 2;
int slotOff = getSlotOff(mid);
@@ -41,16 +40,24 @@
pageTuple.resetByOffset(frame.getBuffer(), tupleOff);
int cmp = multiCmp.compare(tuple, pageTuple);
- if(cmp < 0)
+ if(cmp < 0) {
end = mid - 1;
- else if(cmp > 0)
+ }
+ else if(cmp > 0) {
begin = mid + 1;
- else
- return slotOff;
+ }
+ else {
+ if(mode == FindSlotMode.FSM_EXCLUSIVE) {
+ begin = mid + 1;
+ }
+ else {
+ return slotOff;
+ }
+ }
}
- if(exact) return -1;
- if(begin > frame.getTupleCount() - 1) return -1;
+ if(mode == FindSlotMode.FSM_EXACT) return -1;
+ if(begin > frame.getTupleCount() - 1) return -1;
int slotOff = getSlotOff(begin);
int tupleOff = getTupleOff(slotOff);
@@ -58,7 +65,7 @@
if(multiCmp.compare(tuple, pageTuple) < 0)
return slotOff;
else
- return -1;
+ return -1;
}
@Override
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangePredicate.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangePredicate.java
index 02928be..f2419e0 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangePredicate.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangePredicate.java
@@ -25,18 +25,20 @@
protected boolean isForward = true;
protected ITupleReference lowKey = null;
protected ITupleReference highKey = null;
+ protected boolean lowKeyInclusive = true;
+ protected boolean highKeyInclusive = true;
protected MultiComparator cmp;
public RangePredicate() {
}
- // TODO: for now range is [lowKey, highKey] but depending on user predicate the range could be exclusive on any end
- // need to model this somehow
- // for point queries just use same value for low and high key
- public RangePredicate(boolean isForward, ITupleReference lowKey, ITupleReference highKey, MultiComparator cmp) {
+ public RangePredicate(boolean isForward, ITupleReference lowKey, ITupleReference highKey,
+ boolean lowKeyInclusive, boolean highKeyInclusive, MultiComparator cmp) {
this.isForward = isForward;
this.lowKey = lowKey;
this.highKey = highKey;
+ this.lowKeyInclusive = lowKeyInclusive;
+ this.highKeyInclusive = highKeyInclusive;
this.cmp = cmp;
}
@@ -60,11 +62,23 @@
return highKey;
}
- public void setLowKey(ITupleReference lowKey) {
+ public void setLowKey(ITupleReference lowKey, boolean lowKeyInclusive) {
this.lowKey = lowKey;
+ this.lowKeyInclusive = lowKeyInclusive;
}
- public void setHighKey(ITupleReference highKey) {
+ public void setHighKey(ITupleReference highKey, boolean highKeyInclusive) {
this.highKey = highKey;
+ this.highKeyInclusive = highKeyInclusive;
+ }
+
+ public boolean isLowKeyInclusive() {
+ return lowKeyInclusive;
+ }
+
+ public boolean isHighKeyInclusive() {
+ return highKeyInclusive;
}
}
+
+
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangeSearchCursor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangeSearchCursor.java
index fd8a906..e0bd016 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangeSearchCursor.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangeSearchCursor.java
@@ -92,24 +92,35 @@
frameTuple.resetByTupleIndex(frame, tupleIndex);
if(highKey == null) return true;
- if(cmp.compare(highKey, frameTuple) < 0) {
- return false;
+
+ if(pred.isHighKeyInclusive()) {
+ if(cmp.compare(highKey, frameTuple) < 0) {
+ return false;
+ }
}
else {
- return true;
+ if(cmp.compare(highKey, frameTuple) <= 0) {
+ return false;
+ }
}
+ return true;
}
else {
ITupleReference lowKey = pred.getLowKey();
frameTuple.resetByTupleIndex(frame, frame.getTupleCount() - tupleIndex - 1);
if(lowKey == null) return true;
- if(cmp.compare(lowKey, frameTuple) > 0) {
- return false;
+ if(pred.isLowKeyInclusive()) {
+ if(cmp.compare(lowKey, frameTuple) > 0) {
+ return false;
+ }
}
else {
- return true;
- }
+ if(cmp.compare(lowKey, frameTuple) >= 0) {
+ return false;
+ }
+ }
+ return true;
}
}
@@ -136,15 +147,25 @@
MultiComparator cmp = pred.getComparator();
frameTuple.setFieldCount(cmp.getFieldCount());
if(searchPred.isForward()) {
- ITupleReference lowKey = pred.getLowKey();
+ ITupleReference lowKey = pred.getLowKey();
frameTuple.resetByTupleIndex(frame, tupleIndex);
if(lowKey == null) return; // null means -infinity
-
- while(cmp.compare(lowKey, frameTuple) > 0 && tupleIndex < frame.getTupleCount()) {
- tupleIndex++;
- frameTuple.resetByTupleIndex(frame, tupleIndex);
- }
+
+ if(pred.isLowKeyInclusive()) {
+ while(cmp.compare(lowKey, frameTuple) > 0) {
+ tupleIndex++;
+ if(tupleIndex >= frame.getTupleCount()) break;
+ frameTuple.resetByTupleIndex(frame, tupleIndex);
+ }
+ }
+ else {
+ while(cmp.compare(lowKey, frameTuple) >= 0) {
+ tupleIndex++;
+ if(tupleIndex >= frame.getTupleCount()) break;
+ frameTuple.resetByTupleIndex(frame, tupleIndex);
+ }
+ }
}
else {
ITupleReference highKey = pred.getHighKey();
@@ -152,10 +173,20 @@
frameTuple.resetByTupleIndex(frame, frame.getTupleCount() - tupleIndex - 1);
if(highKey == null) return; // null means +infinity
- while(cmp.compare(highKey, frameTuple) < 0 && tupleIndex < frame.getTupleCount()) {
- tupleIndex++;
- frameTuple.resetByTupleIndex(frame, frame.getTupleCount() - tupleIndex - 1);
- }
+ if(pred.isHighKeyInclusive()) {
+ while(cmp.compare(highKey, frameTuple) < 0) {
+ tupleIndex++;
+ if(tupleIndex >= frame.getTupleCount()) break;
+ frameTuple.resetByTupleIndex(frame, frame.getTupleCount() - tupleIndex - 1);
+ }
+ }
+ else {
+ while(cmp.compare(highKey, frameTuple) <= 0) {
+ tupleIndex++;
+ if(tupleIndex >= frame.getTupleCount()) break;
+ frameTuple.resetByTupleIndex(frame, frame.getTupleCount() - tupleIndex - 1);
+ }
+ }
}
}
diff --git a/hyracks-storage-am-btree/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java b/hyracks-storage-am-btree/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
index 0d2b256..a4c488b 100644
--- a/hyracks-storage-am-btree/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
+++ b/hyracks-storage-am-btree/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
@@ -215,7 +215,7 @@
print("ORDERED SCAN:\n");
IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
- RangePredicate nullPred = new RangePredicate(true, null, null, null);
+ RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null);
btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
try {
while (scanCursor.hasNext()) {
@@ -289,7 +289,7 @@
searchCmps[0] = IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
MultiComparator searchCmp = new MultiComparator(typeTraits, searchCmps);
- RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
+ RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, searchCmp);
btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
try {
@@ -418,7 +418,7 @@
// try a simple index scan
print("ORDERED SCAN:\n");
IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
- RangePredicate nullPred = new RangePredicate(true, null, null, null);
+ RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null);
btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
try {
@@ -474,7 +474,7 @@
searchCmps[0] = IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
MultiComparator searchCmp = new MultiComparator(typeTraits, searchCmps); // use only a single comparator for searching
- RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
+ RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, searchCmp);
btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
try {
@@ -595,7 +595,7 @@
// ordered scan
print("ORDERED SCAN:\n");
IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
- RangePredicate nullPred = new RangePredicate(true, null, null, null);
+ RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null);
btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
try {
@@ -651,7 +651,7 @@
searchCmps[0] = UTF8StringBinaryComparatorFactory.INSTANCE.createBinaryComparator();
MultiComparator searchCmp = new MultiComparator(typeTraits, searchCmps);
- RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
+ RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, searchCmp);
btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
try {
@@ -973,7 +973,7 @@
MultiComparator searchCmp = new MultiComparator(typeTraits, searchCmps);
// TODO: check when searching backwards
- RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
+ RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, searchCmp);
btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
try {
@@ -1132,7 +1132,7 @@
print("ORDERED SCAN:\n");
IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
- RangePredicate nullPred = new RangePredicate(true, null, null, null);
+ RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null);
btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
try {
@@ -1194,7 +1194,7 @@
//print("INDEX RANGE SEARCH ON: " + cmp.printKey(lowKey, 0) + " " + cmp.printKey(highKey, 0) + "\n");
- RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, searchCmp);
+ RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, searchCmp);
btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
try {
diff --git a/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/SimpleConjunctiveSearcher.java b/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/SimpleConjunctiveSearcher.java
index ec45deb..72f57f4 100644
--- a/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/SimpleConjunctiveSearcher.java
+++ b/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/SimpleConjunctiveSearcher.java
@@ -52,7 +52,7 @@
private final IBTreeInteriorFrame interiorFrame;
private final IBTreeCursor btreeCursor;
private final FrameTupleReference searchKey = new FrameTupleReference();
- private final RangePredicate pred = new RangePredicate(true, null, null, null);
+ private final RangePredicate pred = new RangePredicate(true, null, null, true, true, null);
private final IBinaryTokenizer queryTokenizer;
@@ -85,8 +85,8 @@
MultiComparator searchCmp = new MultiComparator(btreeCmp.getTypeTraits(), keyCmps);
pred.setComparator(searchCmp);
- pred.setLowKey(searchKey);
- pred.setHighKey(searchKey);
+ pred.setLowKey(searchKey, true);
+ pred.setHighKey(searchKey, true);
ISerializerDeserializer[] valueSerde = new ISerializerDeserializer[numValueFields];
for(int i = 0; i < numValueFields; i++) {