Improved BTree ops to generate less objects. For example, BTreeOpContext can now be reused for multiple operations.
git-svn-id: https://hyracks.googlecode.com/svn/trunk/hyracks@228 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 7269a01..d10d622 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
@@ -66,6 +66,7 @@
import edu.uci.ics.hyracks.storage.am.btree.frames.NSMLeafFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
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.RangeSearchCursor;
@@ -160,7 +161,8 @@
BTree btree = btreeRegistryProvider.getBTreeRegistry().get(btreeFileId);
IBTreeCursor scanCursor = new RangeSearchCursor(leafFrameFactory.getFrame());
RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null);
- btree.search(scanCursor, nullPred, leafFrameFactory.getFrame(), interiorFrameFactory.getFrame());
+ BTreeOpContext opCtx = btree.createOpContext(BTreeOp.BTO_SEARCH, leafFrameFactory.getFrame(), interiorFrameFactory.getFrame(), null);
+ btree.search(scanCursor, nullPred, opCtx);
try {
while (scanCursor.hasNext()) {
scanCursor.next();
@@ -422,7 +424,8 @@
System.out.println("PRINTING PRIMARY INDEX");
IBTreeCursor scanCursorA = new RangeSearchCursor(primaryLeafFrameFactory.getFrame());
RangePredicate nullPredA = new RangePredicate(true, null, null, true, true, null);
- btreeA.search(scanCursorA, nullPredA, primaryLeafFrameFactory.getFrame(), primaryInteriorFrameFactory.getFrame());
+ BTreeOpContext opCtxA = btreeA.createOpContext(BTreeOp.BTO_SEARCH, primaryLeafFrameFactory.getFrame(), primaryInteriorFrameFactory.getFrame(), null);
+ btreeA.search(scanCursorA, nullPredA, opCtxA);
try {
while (scanCursorA.hasNext()) {
scanCursorA.next();
@@ -441,7 +444,8 @@
System.out.println("PRINTING FIRST SECONDARY INDEX");
IBTreeCursor scanCursorB = new RangeSearchCursor(secondaryLeafFrameFactory.getFrame());
RangePredicate nullPredB = new RangePredicate(true, null, null, true, true, null);
- btreeB.search(scanCursorB, nullPredB, secondaryLeafFrameFactory.getFrame(), secondaryInteriorFrameFactory.getFrame());
+ BTreeOpContext opCtxB = btreeB.createOpContext(BTreeOp.BTO_SEARCH, secondaryLeafFrameFactory.getFrame(), secondaryInteriorFrameFactory.getFrame(), null);
+ btreeB.search(scanCursorB, nullPredB, opCtxB);
try {
while (scanCursorB.hasNext()) {
scanCursorB.next();
@@ -460,7 +464,8 @@
System.out.println("PRINTING SECOND SECONDARY INDEX");
IBTreeCursor scanCursorC = new RangeSearchCursor(secondaryLeafFrameFactory.getFrame());
RangePredicate nullPredC = new RangePredicate(true, null, null, true, true, null);
- btreeC.search(scanCursorC, nullPredC, secondaryLeafFrameFactory.getFrame(), secondaryInteriorFrameFactory.getFrame());
+ BTreeOpContext opCtxC = btreeC.createOpContext(BTreeOp.BTO_SEARCH, secondaryLeafFrameFactory.getFrame(), secondaryInteriorFrameFactory.getFrame(), null);
+ btreeC.search(scanCursorC, nullPredC, opCtxC);
try {
while (scanCursorC.hasNext()) {
scanCursorC.next();
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 dc02c2e..44d26da 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
@@ -23,27 +23,19 @@
import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
import edu.uci.ics.hyracks.dataflow.common.comm.util.FrameUtils;
import edu.uci.ics.hyracks.dataflow.std.base.AbstractUnaryInputUnaryOutputOperatorNodePushable;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
import edu.uci.ics.hyracks.storage.am.btree.frames.MetaDataFrame;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
public class BTreeInsertUpdateDeleteOperatorNodePushable extends AbstractUnaryInputUnaryOutputOperatorNodePushable {
private final BTreeOpHelper btreeOpHelper;
-
private FrameTupleAccessor accessor;
-
- private IRecordDescriptorProvider recordDescProvider;
-
- private IBTreeMetaDataFrame metaFrame;
-
- private BTreeOp op;
-
- private PermutingFrameTupleReference tuple = new PermutingFrameTupleReference();
-
+ private final IRecordDescriptorProvider recordDescProvider;
+ private final BTreeOp op;
+ private final PermutingFrameTupleReference tuple = new PermutingFrameTupleReference();
private ByteBuffer writeBuffer;
+ private BTreeOpContext opCtx;
public BTreeInsertUpdateDeleteOperatorNodePushable(AbstractBTreeOperatorDescriptor opDesc, IHyracksContext ctx,
int partition, int[] fieldPermutation, IRecordDescriptorProvider recordDescProvider, BTreeOp op) {
@@ -60,10 +52,7 @@
@Override
public void nextFrame(ByteBuffer buffer) throws HyracksDataException {
- final BTree btree = btreeOpHelper.getBTree();
- final IBTreeLeafFrame leafFrame = btreeOpHelper.getLeafFrame();
- final IBTreeInteriorFrame interiorFrame = btreeOpHelper.getInteriorFrame();
-
+ final BTree btree = btreeOpHelper.getBTree();
accessor.reset(buffer);
int tupleCount = accessor.getTupleCount();
@@ -74,12 +63,12 @@
switch (op) {
case BTO_INSERT: {
- btree.insert(tuple, leafFrame, interiorFrame, metaFrame);
+ btree.insert(tuple, opCtx);
}
break;
case BTO_DELETE: {
- btree.delete(tuple, leafFrame, interiorFrame, metaFrame);
+ btree.delete(tuple, opCtx);
}
break;
@@ -104,14 +93,14 @@
AbstractBTreeOperatorDescriptor opDesc = btreeOpHelper.getOperatorDescriptor();
RecordDescriptor inputRecDesc = recordDescProvider.getInputRecordDescriptor(opDesc.getOperatorId(), 0);
accessor = new FrameTupleAccessor(btreeOpHelper.getHyracksContext(), inputRecDesc);
- writeBuffer = btreeOpHelper.getHyracksContext().getResourceManager().allocateFrame();
+ writeBuffer = btreeOpHelper.getHyracksContext().getResourceManager().allocateFrame();
try {
btreeOpHelper.init();
btreeOpHelper.getBTree().open(btreeOpHelper.getBTreeFileId());
- metaFrame = new MetaDataFrame();
} catch (Exception e) {
e.printStackTrace();
}
+ opCtx = btreeOpHelper.getBTree().createOpContext(op, btreeOpHelper.getLeafFrame(), btreeOpHelper.getInteriorFrame(), new MetaDataFrame());
}
@Override
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 2b69d9d..e97ae7d 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
@@ -29,9 +29,10 @@
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
import edu.uci.ics.hyracks.dataflow.std.base.AbstractUnaryInputUnaryOutputOperatorNodePushable;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeCursor;
-import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
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.RangeSearchCursor;
@@ -53,10 +54,9 @@
private boolean highKeyInclusive;
private RangePredicate rangePred;
private MultiComparator searchCmp;
- private IBTreeCursor cursor;
- private IBTreeLeafFrame leafFrame;
- private IBTreeLeafFrame cursorFrame;
- private IBTreeInteriorFrame interiorFrame;
+ private IBTreeCursor cursor;
+ private IBTreeLeafFrame cursorFrame;
+ private BTreeOpContext opCtx;
private RecordDescriptor recDesc;
@@ -90,9 +90,6 @@
throw new HyracksDataException(e);
}
btree = btreeOpHelper.getBTree();
-
- leafFrame = btreeOpHelper.getLeafFrame();
- interiorFrame = btreeOpHelper.getInteriorFrame();
// construct range predicate
@@ -113,6 +110,8 @@
dos = tb.getDataOutput();
appender = new FrameTupleAppender(btreeOpHelper.getHyracksContext());
appender.reset(writeBuffer, true);
+
+ opCtx = btree.createOpContext(BTreeOp.BTO_SEARCH, btreeOpHelper.getLeafFrame(), btreeOpHelper.getInteriorFrame(), null);
}
private void writeSearchResults() throws Exception {
@@ -149,7 +148,7 @@
rangePred.setHighKey(highKey, highKeyInclusive);
cursor.reset();
- btree.search(cursor, rangePred, leafFrame, interiorFrame);
+ btree.search(cursor, rangePred, opCtx);
writeSearchResults();
}
} catch (Exception e) {
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 7a74bf8..a4effb7 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
@@ -16,7 +16,6 @@
package edu.uci.ics.hyracks.storage.am.btree.impls;
import java.util.ArrayList;
-import java.util.Stack;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
@@ -226,8 +225,8 @@
}
private void addFreePages(BTreeOpContext ctx) throws Exception {
- for (Integer i : ctx.freePages) {
- addFreePage(ctx.metaFrame, i);
+ for(int i = 0; i < ctx.freePages.size(); i++) {
+ addFreePage(ctx.metaFrame, ctx.freePages.get(i));
}
ctx.freePages.clear();
}
@@ -403,16 +402,10 @@
cursor.open(page, diskOrderScanPredicate);
}
- public void search(IBTreeCursor cursor, RangePredicate pred, IBTreeLeafFrame leafFrame,
- IBTreeInteriorFrame interiorFrame) throws Exception {
- BTreeOpContext ctx = new BTreeOpContext();
- ctx.op = BTreeOp.BTO_SEARCH;
- ctx.leafFrame = leafFrame;
- ctx.interiorFrame = interiorFrame;
- ctx.metaFrame = null;
- ctx.pred = pred;
- ctx.cursor = cursor;
- ctx.pageLsns = new Stack<Integer>();
+ public void search(IBTreeCursor cursor, RangePredicate pred, BTreeOpContext ctx) throws Exception {
+ ctx.reset();
+ ctx.pred = pred;
+ ctx.cursor = cursor;
if (ctx.pred.getComparator() == null)
ctx.pred.setComparator(cmp); // simple index scan
@@ -424,8 +417,8 @@
// if we reach this stage then we need to restart from the (possibly
// new) root
- if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.peek().equals(RESTART_OP)) {
- ctx.pageLsns.pop(); // pop the restart op indicator
+ if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.getLast() == RESTART_OP) {
+ ctx.pageLsns.removeLast(); // pop the restart op indicator
continue;
}
@@ -438,8 +431,9 @@
private void unsetSmPages(BTreeOpContext ctx) throws Exception {
ICachedPage originalPage = ctx.interiorFrame.getPage();
- for (Integer i : ctx.smPages) {
- ICachedPage smPage = bufferCache.pin(FileInfo.getDiskPageId(fileId, i), false);
+ for(int i = 0; i < ctx.smPages.size(); i++) {
+ int pageId = ctx.smPages.get(i);
+ ICachedPage smPage = bufferCache.pin(FileInfo.getDiskPageId(fileId, pageId), false);
pins++;
smPage.acquireWriteLatch(); // TODO: would like to set page dirty without latching
writeLatchesAcquired++;
@@ -522,19 +516,14 @@
}
}
- public void insert(ITupleReference tuple, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
- IBTreeMetaDataFrame metaFrame) throws Exception {
- BTreeOpContext ctx = new BTreeOpContext();
- ctx.op = BTreeOp.BTO_INSERT;
- ctx.leafFrame = leafFrame;
- ctx.interiorFrame = interiorFrame;
- ctx.metaFrame = metaFrame;
- ctx.pred = new RangePredicate(true, tuple, tuple, true, true, cmp);
- ctx.splitKey = new SplitKey(leafFrame.getTupleWriter().createTupleReference());
+ public void insert(ITupleReference tuple, BTreeOpContext ctx) throws Exception {
+ ctx.reset();
+ ctx.pred.setComparator(cmp);
+ ctx.pred.setLowKey(tuple, true);
+ ctx.pred.setHighKey(tuple, true);
+ ctx.splitKey.reset();
ctx.splitKey.getTuple().setFieldCount(cmp.getKeyFieldCount());
- ctx.smPages = new ArrayList<Integer>();
- ctx.pageLsns = new Stack<Integer>();
-
+
boolean repeatOp = true;
// we use this loop to deal with possibly multiple operation restarts
// due to ongoing structure modifications during the descent
@@ -543,8 +532,8 @@
// if we reach this stage then we need to restart from the (possibly
// new) root
- if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.peek().equals(RESTART_OP)) {
- ctx.pageLsns.pop(); // pop the restart op indicator
+ if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.getLast() == RESTART_OP) {
+ ctx.pageLsns.removeLast(); // pop the restart op indicator
continue;
}
@@ -759,19 +748,13 @@
}
}
- public void delete(ITupleReference tuple, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
- IBTreeMetaDataFrame metaFrame) throws Exception {
- BTreeOpContext ctx = new BTreeOpContext();
- ctx.op = BTreeOp.BTO_DELETE;
- ctx.leafFrame = leafFrame;
- ctx.interiorFrame = interiorFrame;
- ctx.metaFrame = metaFrame;
- 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>();
+ public void delete(ITupleReference tuple, BTreeOpContext ctx) throws Exception {
+ ctx.reset();
+ ctx.pred.setComparator(cmp);
+ ctx.pred.setLowKey(tuple, true);
+ ctx.pred.setHighKey(tuple, true);
+ ctx.splitKey.reset();
+ ctx.splitKey.getTuple().setFieldCount(cmp.getKeyFieldCount());
boolean repeatOp = true;
// we use this loop to deal with possibly multiple operation restarts
@@ -781,8 +764,8 @@
// if we reach this stage then we need to restart from the (possibly
// new) root
- if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.peek().equals(RESTART_OP)) {
- ctx.pageLsns.pop(); // pop the restart op indicator
+ if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.getLast() == RESTART_OP) {
+ ctx.pageLsns.removeLast(); // pop the restart op indicator
continue;
}
@@ -793,8 +776,8 @@
rootNode.acquireWriteLatch();
writeLatchesAcquired++;
try {
- leafFrame.setPage(rootNode);
- leafFrame.initBuffer((byte) 0);
+ ctx.leafFrame.setPage(rootNode);
+ ctx.leafFrame.initBuffer((byte) 0);
currentLevel = 0; // debug
} finally {
rootNode.releaseWriteLatch();
@@ -978,7 +961,7 @@
ctx.interiorFrame.setPage(node);
boolean isConsistent = false;
try {
- isConsistent = ctx.pageLsns.peek().equals(ctx.interiorFrame.getPageLsn());
+ isConsistent = ctx.pageLsns.getLast() == ctx.interiorFrame.getPageLsn();
} finally {
node.releaseReadLatch();
readLatchesReleased++;
@@ -999,8 +982,8 @@
// remember trail of pageLsns, to unwind recursion in case of an ongoing
// structure modification
- ctx.pageLsns.push(ctx.interiorFrame.getPageLsn());
-
+ ctx.pageLsns.add(ctx.interiorFrame.getPageLsn());
+
try {
// latch coupling, note: parent should never be write latched,
@@ -1022,18 +1005,18 @@
int childPageId = ctx.interiorFrame.getChildPageId(ctx.pred, cmp);
performOp(childPageId, node, ctx);
- if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.peek().equals(RESTART_OP)) {
- ctx.pageLsns.pop(); // pop the restart op indicator
+ if (!ctx.pageLsns.isEmpty() && ctx.pageLsns.getLast() == RESTART_OP) {
+ ctx.pageLsns.removeLast(); // pop the restart op indicator
if (isConsistent(pageId, ctx)) {
node = null; // to avoid unpinning and
// unlatching node again in
// recursive call
continue; // descend the tree again
} else {
- ctx.pageLsns.pop(); // pop pageLsn of this page
+ ctx.pageLsns.removeLast(); // pop pageLsn of this page
// (version seen by this op
// during descent)
- ctx.pageLsns.push(RESTART_OP); // this node is
+ ctx.pageLsns.add(RESTART_OP); // this node is
// not
// consistent,
// set the
@@ -1113,10 +1096,10 @@
// unwind recursion and restart operation, find lowest page
// with a pageLsn as seen by this operation during descent
- ctx.pageLsns.pop(); // pop current page lsn
+ ctx.pageLsns.removeLast(); // pop current page lsn
// put special value on the stack to inform caller of
// restart
- ctx.pageLsns.push(RESTART_OP);
+ ctx.pageLsns.add(RESTART_OP);
}
} else { // isLeaf and !smFlag
switch (ctx.op) {
@@ -1334,6 +1317,12 @@
loaded = true;
}
+ public BTreeOpContext createOpContext(BTreeOp op, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
+ IBTreeMetaDataFrame metaFrame) {
+ // TODO: figure out better tree-height hint
+ return new BTreeOpContext(op, leafFrame, interiorFrame, metaFrame, 6);
+ }
+
public IBTreeInteriorFrameFactory getInteriorFrameFactory() {
return interiorFrameFactory;
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
index 9a81c96..390831d 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
@@ -15,24 +15,49 @@
package edu.uci.ics.hyracks.storage.am.btree.impls;
-import java.util.ArrayList;
-import java.util.Stack;
-
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeCursor;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeMetaDataFrame;
public final class BTreeOpContext {
- public BTreeOp op;
- public IBTreeLeafFrame leafFrame;
- public IBTreeInteriorFrame interiorFrame;
- public IBTreeMetaDataFrame metaFrame;
+ public final BTreeOp op;
+ public final IBTreeLeafFrame leafFrame;
+ public final IBTreeInteriorFrame interiorFrame;
+ public final IBTreeMetaDataFrame metaFrame;
public IBTreeCursor cursor;
public RangePredicate pred;
- public SplitKey splitKey;
+ public final SplitKey splitKey;
public int opRestarts = 0;
- public ArrayList<Integer> smPages;
- public Stack<Integer> pageLsns;
- public ArrayList<Integer> freePages;
+ public final IntArrayList pageLsns; // used like a stack
+ public final IntArrayList smPages;
+ public final IntArrayList freePages;
+
+ public BTreeOpContext(BTreeOp op, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
+ IBTreeMetaDataFrame metaFrame, int treeHeightHint) {
+ this.op = op;
+ this.leafFrame = leafFrame;
+ this.interiorFrame = interiorFrame;
+ this.metaFrame = metaFrame;
+
+ pageLsns = new IntArrayList(treeHeightHint, treeHeightHint);
+ if(op != BTreeOp.BTO_SEARCH) {
+ smPages = new IntArrayList(treeHeightHint, treeHeightHint);
+ freePages = new IntArrayList(treeHeightHint, treeHeightHint);
+ pred = new RangePredicate(true, null, null, true, true, null);
+ splitKey = new SplitKey(leafFrame.getTupleWriter().createTupleReference());
+ }
+ else {
+ smPages = null;
+ freePages = null;
+ splitKey = null;
+ }
+ }
+
+ public void reset() {
+ if(pageLsns != null) pageLsns.clear();
+ if(freePages != null) freePages.clear();
+ if(smPages != null) smPages.clear();
+ opRestarts = 0;
+ }
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/IntArrayList.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/IntArrayList.java
new file mode 100644
index 0000000..124cccd
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/IntArrayList.java
@@ -0,0 +1,48 @@
+package edu.uci.ics.hyracks.storage.am.btree.impls;
+
+public class IntArrayList {
+ private int[] data;
+ private int size;
+ private final int growth;
+
+ public IntArrayList(int initialCapacity, int growth) {
+ data = new int[initialCapacity];
+ size = 0;
+ this.growth = growth;
+ }
+
+ public int size() {
+ return size;
+ }
+
+ public void add(int i) {
+ if(size == data.length) {
+ int[] newData = new int[data.length + growth];
+ System.arraycopy(data, 0, newData, 0, data.length);
+ data = newData;
+ }
+
+ data[size++] = i;
+ }
+
+ public void removeLast() {
+ if(size > 0) size--;
+ }
+
+ // WARNING: caller is responsible for checking size > 0
+ public int getLast() {
+ return data[size-1];
+ }
+
+ public int get(int i) {
+ return data[i];
+ }
+
+ public void clear() {
+ size = 0;
+ }
+
+ public boolean isEmpty() {
+ return size == 0;
+ }
+}
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 a4c488b..78b6d4d78 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
@@ -52,6 +52,8 @@
import edu.uci.ics.hyracks.storage.am.btree.frames.NSMLeafFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
import edu.uci.ics.hyracks.storage.am.btree.impls.DiskOrderScanCursor;
import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
@@ -164,6 +166,8 @@
accessor.reset(frame);
FrameTupleReference tuple = new FrameTupleReference();
+ BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT, leafFrame, interiorFrame, metaFrame);
+
// 10000
for (int i = 0; i < 10000; i++) {
@@ -189,7 +193,7 @@
}
try {
- btree.insert(tuple, leafFrame, interiorFrame, metaFrame);
+ btree.insert(tuple, insertOpCtx);
} catch (BTreeException e) {
} catch (Exception e) {
e.printStackTrace();
@@ -216,7 +220,8 @@
print("ORDERED SCAN:\n");
IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null);
- btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
+ BTreeOpContext searchOpCtx = btree.createOpContext(BTreeOp.BTO_SEARCH, leafFrame, interiorFrame, null);
+ btree.search(scanCursor, nullPred, searchOpCtx);
try {
while (scanCursor.hasNext()) {
scanCursor.next();
@@ -290,8 +295,8 @@
MultiComparator searchCmp = new MultiComparator(typeTraits, searchCmps);
RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, searchCmp);
- btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
-
+ btree.search(rangeCursor, rangePred, searchOpCtx);
+
try {
while (rangeCursor.hasNext()) {
rangeCursor.next();
@@ -382,6 +387,8 @@
accessor.reset(frame);
FrameTupleReference tuple = new FrameTupleReference();
+ BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT, leafFrame, interiorFrame, metaFrame);
+
for (int i = 0; i < 10000; i++) {
int f0 = rnd.nextInt() % 2000;
int f1 = rnd.nextInt() % 1000;
@@ -405,7 +412,7 @@
}
try {
- btree.insert(tuple, leafFrame, interiorFrame, metaFrame);
+ btree.insert(tuple, insertOpCtx);
} catch (Exception e) {
}
}
@@ -419,7 +426,8 @@
print("ORDERED SCAN:\n");
IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null);
- btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
+ BTreeOpContext searchOpCtx = btree.createOpContext(BTreeOp.BTO_SEARCH, leafFrame, interiorFrame, null);
+ btree.search(scanCursor, nullPred, searchOpCtx);
try {
while (scanCursor.hasNext()) {
@@ -475,7 +483,7 @@
MultiComparator searchCmp = new MultiComparator(typeTraits, searchCmps); // use only a single comparator for searching
RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, searchCmp);
- btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
+ btree.search(rangeCursor, rangePred, searchOpCtx);
try {
while (rangeCursor.hasNext()) {
@@ -560,6 +568,7 @@
accessor.reset(frame);
FrameTupleReference tuple = new FrameTupleReference();
+ BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT, leafFrame, interiorFrame, metaFrame);
int maxLength = 10; // max string length to be generated
for (int i = 0; i < 10000; i++) {
@@ -583,7 +592,7 @@
}
try {
- btree.insert(tuple, leafFrame, interiorFrame, metaFrame);
+ btree.insert(tuple, insertOpCtx);
} catch (Exception e) {
//e.printStackTrace();
}
@@ -596,7 +605,8 @@
print("ORDERED SCAN:\n");
IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null);
- btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
+ BTreeOpContext searchOpCtx = btree.createOpContext(BTreeOp.BTO_SEARCH, leafFrame, interiorFrame, null);
+ btree.search(scanCursor, nullPred, searchOpCtx);
try {
while (scanCursor.hasNext()) {
@@ -652,7 +662,7 @@
MultiComparator searchCmp = new MultiComparator(typeTraits, searchCmps);
RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, searchCmp);
- btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
+ btree.search(rangeCursor, rangePred, searchOpCtx);
try {
while (rangeCursor.hasNext()) {
@@ -738,6 +748,9 @@
accessor.reset(frame);
FrameTupleReference tuple = new FrameTupleReference();
+ BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT, leafFrame, interiorFrame, metaFrame);
+ BTreeOpContext deleteOpCtx = btree.createOpContext(BTreeOp.BTO_DELETE, leafFrame, interiorFrame, metaFrame);
+
int runs = 3;
for (int run = 0; run < runs; run++) {
@@ -772,11 +785,12 @@
print("INSERTING " + i + "\n");
//print("INSERTING " + i + ": " + cmp.printRecord(record, 0) + "\n");
}
-
+
try {
- btree.insert(tuple, leafFrame, interiorFrame, metaFrame);
+ btree.insert(tuple, insertOpCtx);
insDone++;
- } catch (BTreeException e) {
+ } catch (BTreeException e) {
+ //e.printStackTrace();
} catch (Exception e) {
e.printStackTrace();
}
@@ -807,13 +821,14 @@
}
try {
- btree.delete(tuple, leafFrame, interiorFrame, metaFrame);
+ btree.delete(tuple, deleteOpCtx);
delDone++;
- } catch (BTreeException e) {
+ } catch (BTreeException e) {
+ //e.printStackTrace();
} catch (Exception e) {
e.printStackTrace();
}
-
+
if (insDoneCmp[i] != delDone) {
print("INCONSISTENT STATE, ERROR IN DELETION TEST\n");
print("INSDONECMP: " + insDoneCmp[i] + " " + delDone + "\n");
@@ -974,7 +989,8 @@
// TODO: check when searching backwards
RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, searchCmp);
- btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
+ BTreeOpContext searchOpCtx = btree.createOpContext(BTreeOp.BTO_SEARCH, leafFrame, interiorFrame, null);
+ btree.search(rangeCursor, rangePred, searchOpCtx);
try {
while (rangeCursor.hasNext()) {
@@ -1093,6 +1109,8 @@
intervals[9][0] = 20;
intervals[9][1] = 35;
+ BTreeOpContext insertOpCtx = btree.createOpContext(BTreeOp.BTO_INSERT, leafFrame, interiorFrame, metaFrame);
+
// int exceptionCount = 0;
for (int i = 0; i < intervalCount; i++) {
int f0 = intervals[i][0];
@@ -1116,7 +1134,7 @@
print("INSERTING " + i + "\n");
try {
- btree.insert(tuple, leafFrame, interiorFrame, metaFrame);
+ btree.insert(tuple, insertOpCtx);
} catch (Exception e) {
// e.printStackTrace();
}
@@ -1133,7 +1151,8 @@
print("ORDERED SCAN:\n");
IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null);
- btree.search(scanCursor, nullPred, leafFrame, interiorFrame);
+ BTreeOpContext searchOpCtx = btree.createOpContext(BTreeOp.BTO_SEARCH, leafFrame, interiorFrame, null);
+ btree.search(scanCursor, nullPred, searchOpCtx);
try {
while (scanCursor.hasNext()) {
@@ -1195,7 +1214,7 @@
//print("INDEX RANGE SEARCH ON: " + cmp.printKey(lowKey, 0) + " " + cmp.printKey(highKey, 0) + "\n");
RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, searchCmp);
- btree.search(rangeCursor, rangePred, leafFrame, interiorFrame);
+ btree.search(rangeCursor, rangePred, searchOpCtx);
try {
while (rangeCursor.hasNext()) {
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 72f57f4..e3067a3 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
@@ -21,6 +21,8 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
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.RangeSearchCursor;
@@ -130,11 +132,13 @@
maxResultBufIdx = 0;
+ BTreeOpContext opCtx = btree.createOpContext(BTreeOp.BTO_SEARCH, leafFrame, interiorFrame, null);
+
resultTupleAppender.reset(newResultBuffers.get(0), true);
try {
// append first inverted list to temporary results
searchKey.reset(queryTokenAccessor, 0);
- btree.search(btreeCursor, pred, leafFrame, interiorFrame);
+ btree.search(btreeCursor, pred, opCtx);
while(btreeCursor.hasNext()) {
btreeCursor.next();
maxResultBufIdx = appendTupleToNewResults(btreeCursor, maxResultBufIdx);
@@ -153,7 +157,7 @@
newResultBuffers = swap;
try {
searchKey.reset(queryTokenAccessor, i);
- btree.search(btreeCursor, pred, leafFrame, interiorFrame);
+ btree.search(btreeCursor, pred, opCtx);
maxResultBufIdx = intersectList(btreeCursor, prevResultBuffers, maxResultBufIdx, newResultBuffers);
} catch (Exception e) {
throw new HyracksDataException(e);
diff --git a/hyracks-storage-am-invertedindex/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/searchers/SimpleConjunctiveSearcherTest.java b/hyracks-storage-am-invertedindex/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/searchers/SimpleConjunctiveSearcherTest.java
index 3f00e4c..fa5ec4c 100644
--- a/hyracks-storage-am-invertedindex/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/searchers/SimpleConjunctiveSearcherTest.java
+++ b/hyracks-storage-am-invertedindex/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/searchers/SimpleConjunctiveSearcherTest.java
@@ -39,8 +39,10 @@
import edu.uci.ics.hyracks.storage.am.btree.frames.NSMInteriorFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.frames.NSMLeafFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOp;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
import edu.uci.ics.hyracks.storage.am.btree.impls.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.btree.tuples.SimpleTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.btree.tuples.TypeAwareTupleWriterFactory;
import edu.uci.ics.hyracks.storage.am.invertedindex.api.IBinaryTokenizer;
import edu.uci.ics.hyracks.storage.am.invertedindex.api.IInvertedIndexResultCursor;
import edu.uci.ics.hyracks.storage.am.invertedindex.impls.SimpleConjunctiveSearcher;
@@ -62,7 +64,7 @@
// realistic params
//private static final int PAGE_SIZE = 32768;
- //private static final int NUM_PAGES = 1000;
+ //private static final int NUM_PAGES = 100;
//private static final int HYRACKS_FRAME_SIZE = 32768;
private String tmpDir = System.getProperty("java.io.tmpdir");
@@ -106,9 +108,10 @@
MultiComparator cmp = new MultiComparator(typeTraits, cmps);
- //TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(typeTraits);
- SimpleTupleWriterFactory tupleWriterFactory = new SimpleTupleWriterFactory();
+ TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(typeTraits);
+ //SimpleTupleWriterFactory tupleWriterFactory = new SimpleTupleWriterFactory();
IBTreeLeafFrameFactory leafFrameFactory = new NSMLeafFrameFactory(tupleWriterFactory);
+ //IBTreeLeafFrameFactory leafFrameFactory = new FieldPrefixNSMLeafFrameFactory(tupleWriterFactory);
IBTreeInteriorFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(tupleWriterFactory);
IBTreeMetaDataFrameFactory metaFrameFactory = new MetaDataFrameFactory();
@@ -147,6 +150,8 @@
int addProb = 0;
int addProbStep = 2;
+ BTreeOpContext opCtx = btree.createOpContext(BTreeOp.BTO_INSERT, leafFrame, interiorFrame, metaFrame);
+
for (int i = 0; i < tokens.size(); i++) {
addProb += addProbStep;
@@ -164,7 +169,7 @@
tuple.reset(accessor, 0);
try {
- btree.insert(tuple, leafFrame, interiorFrame, metaFrame);
+ btree.insert(tuple, opCtx);
} catch (Exception e) {
e.printStackTrace();
}