Finished BTree update. Improved BTree tests.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_btree_updates_next@602 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/data/accessors/FrameTupleReference.java b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/data/accessors/FrameTupleReference.java
index ff45eba..a21d5e9 100644
--- a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/data/accessors/FrameTupleReference.java
+++ b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/data/accessors/FrameTupleReference.java
@@ -1,3 +1,18 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
package edu.uci.ics.hyracks.dataflow.common.data.accessors;
import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
diff --git a/hyracks-examples/hyracks-integration-tests/src/test/java/edu/uci/ics/hyracks/tests/btree/BTreeSecondaryIndexSearchOperatorTest.java b/hyracks-examples/hyracks-integration-tests/src/test/java/edu/uci/ics/hyracks/tests/btree/BTreeSecondaryIndexSearchOperatorTest.java
index 60c3b13..57fef2e 100644
--- a/hyracks-examples/hyracks-integration-tests/src/test/java/edu/uci/ics/hyracks/tests/btree/BTreeSecondaryIndexSearchOperatorTest.java
+++ b/hyracks-examples/hyracks-integration-tests/src/test/java/edu/uci/ics/hyracks/tests/btree/BTreeSecondaryIndexSearchOperatorTest.java
@@ -361,7 +361,6 @@
public static void cleanup() throws Exception {
File primary = new File(primaryFileName);
primary.deleteOnExit();
-
File secondary = new File(secondaryFileName);
secondary.deleteOnExit();
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeDuplicateKeyException.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeDuplicateKeyException.java
similarity index 83%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeDuplicateKeyException.java
rename to hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeDuplicateKeyException.java
index 1aa7fff..7105670 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeDuplicateKeyException.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeDuplicateKeyException.java
@@ -1,4 +1,4 @@
-package edu.uci.ics.hyracks.storage.am.btree.impls;
+package edu.uci.ics.hyracks.storage.am.btree.exceptions;
public class BTreeDuplicateKeyException extends BTreeException {
private static final long serialVersionUID = 1L;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeException.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeException.java
similarity index 95%
rename from hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeException.java
rename to hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeException.java
index 1658989..1e09658 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeException.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeException.java
@@ -13,7 +13,7 @@
* limitations under the License.
*/
-package edu.uci.ics.hyracks.storage.am.btree.impls;
+package edu.uci.ics.hyracks.storage.am.btree.exceptions;
import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeNotUpdateableException.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeNotUpdateableException.java
new file mode 100644
index 0000000..fb2e4a4
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/exceptions/BTreeNotUpdateableException.java
@@ -0,0 +1,13 @@
+package edu.uci.ics.hyracks.storage.am.btree.exceptions;
+
+public class BTreeNotUpdateableException extends BTreeException {
+ private static final long serialVersionUID = 1L;
+
+ public BTreeNotUpdateableException(Exception e) {
+ super(e);
+ }
+
+ public BTreeNotUpdateableException(String message) {
+ super(message);
+ }
+}
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 f74e2ee..b662c4e 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
@@ -30,8 +30,8 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IFrameCompressor;
import edu.uci.ics.hyracks.storage.am.btree.api.IPrefixSlotManager;
import edu.uci.ics.hyracks.storage.am.btree.compressors.FieldPrefixCompressor;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeDuplicateKeyException;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixPrefixTupleReference;
import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixSlotManager;
import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixTupleReference;
@@ -67,8 +67,8 @@
protected ICachedPage page = null;
protected ByteBuffer buf = null;
public IFrameCompressor compressor;
- public IPrefixSlotManager slotManager; // TODO: should be protected, but
- // will trigger some refactoring
+ // TODO: Should be protected, but will trigger some refactoring.
+ public IPrefixSlotManager slotManager;
private ITreeIndexTupleWriter tupleWriter;
@@ -258,11 +258,98 @@
}
@Override
- public FrameOpSpaceStatus hasSpaceUpdate(ITupleReference tuple, int oldTupleIndex, MultiComparator cmp) {
- // TODO Auto-generated method stub
+ public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception {
+ int slot = slotManager.insertSlot(tupleIndex, buf.getInt(freeSpaceOff));
+ int prefixSlotNum = slotManager.decodeFirstSlotField(slot);
+ int numPrefixFields = 0;
+ if (prefixSlotNum != FieldPrefixSlotManager.TUPLE_UNCOMPRESSED) {
+ int prefixSlotOff = slotManager.getPrefixSlotOff(prefixSlotNum);
+ int prefixSlot = buf.getInt(prefixSlotOff);
+ numPrefixFields = slotManager.decodeFirstSlotField(prefixSlot);
+ } else {
+ buf.putInt(uncompressedTupleCountOff, buf.getInt(uncompressedTupleCountOff) + 1);
+ }
+
+ int freeSpace = buf.getInt(freeSpaceOff);
+ int bytesWritten = tupleWriter.writeTupleFields(tuple, numPrefixFields,
+ tuple.getFieldCount() - numPrefixFields, buf, freeSpace);
+
+ buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
+ buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + bytesWritten);
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - bytesWritten - slotManager.getSlotSize());
+ }
+
+ @Override
+ public FrameOpSpaceStatus hasSpaceUpdate(ITupleReference newTuple, int oldTupleIndex, MultiComparator cmp) {
+ int tupleIndex = slotManager.decodeSecondSlotField(oldTupleIndex);
+ frameTuple.resetByTupleIndex(this, tupleIndex);
+ // TODO: Do we need to set the field count here?
+ //frameTuple.setFieldCount(cmp.getFieldCount());
+
+ int oldTupleBytes = 0;
+ int newTupleBytes = 0;
+
+ int numPrefixFields = frameTuple.getNumPrefixFields();
+ int numFields = frameTuple.getFieldCount();
+ if (numPrefixFields != 0) {
+ // Check the space requirements for updating the suffix of the original tuple.
+ oldTupleBytes = frameTuple.getSuffixTupleSize();
+ newTupleBytes = tupleWriter.bytesRequired(newTuple, numPrefixFields, numFields - numPrefixFields);
+ } else {
+ // The original tuple is uncompressed.
+ oldTupleBytes = frameTuple.getTupleSize();
+ newTupleBytes = tupleWriter.bytesRequired(newTuple);
+ }
+
+ int additionalBytesRequired = newTupleBytes - oldTupleBytes;
+ // Enough space for an in-place update?
+ if (additionalBytesRequired <= 0) {
+ return FrameOpSpaceStatus.SUFFICIENT_INPLACE_SPACE;
+ }
+
+ int freeContiguous = buf.capacity() - buf.getInt(freeSpaceOff)
+ - ((buf.getInt(tupleCountOff) + buf.getInt(prefixTupleCountOff)) * slotManager.getSlotSize());
+
+ // Enough space if we delete the old tuple and insert the new one without compaction?
+ if (newTupleBytes <= freeContiguous) {
+ return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
+ }
+ // Enough space if we delete the old tuple and compact?
+ if (additionalBytesRequired <= buf.getInt(totalFreeSpaceOff)) {
+ return FrameOpSpaceStatus.SUFFICIENT_SPACE;
+ }
return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
}
+ @Override
+ public void update(ITupleReference newTuple, int oldTupleIndex, boolean inPlace) throws Exception {
+ int tupleIndex = slotManager.decodeSecondSlotField(oldTupleIndex);
+ int tupleSlotOff = slotManager.getTupleSlotOff(tupleIndex);
+ int tupleSlot = buf.getInt(tupleSlotOff);
+ int prefixSlotNum = slotManager.decodeFirstSlotField(tupleSlot);
+ int suffixTupleStartOff = slotManager.decodeSecondSlotField(tupleSlot);
+
+ frameTuple.resetByTupleIndex(this, tupleIndex);
+ int numFields = frameTuple.getFieldCount();
+ int numPrefixFields = frameTuple.getNumPrefixFields();
+ int oldTupleBytes = frameTuple.getSuffixTupleSize();
+ int bytesWritten = 0;
+
+ if (inPlace) {
+ // Overwrite the old tuple suffix in place.
+ bytesWritten = tupleWriter.writeTupleFields(newTuple, numPrefixFields, numFields - numPrefixFields, buf, suffixTupleStartOff);
+ } else {
+ // Insert the new tuple suffix at the end of the free space, and change the slot value (effectively "deleting" the old tuple).
+ int newSuffixTupleStartOff = buf.getInt(freeSpaceOff);
+ bytesWritten = tupleWriter.writeTupleFields(newTuple, numPrefixFields, numFields - numPrefixFields, buf, newSuffixTupleStartOff);
+ // Update slot value using the same prefix slot num.
+ slotManager.setSlot(tupleSlotOff, slotManager.encodeSlotFields(prefixSlotNum, newSuffixTupleStartOff));
+ // Update contiguous free space pointer.
+ buf.putInt(freeSpaceOff, newSuffixTupleStartOff + bytesWritten);
+ }
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + oldTupleBytes - bytesWritten);
+ }
+
protected void resetSpaceParams() {
buf.putInt(freeSpaceOff, getOrigFreeSpaceOff());
buf.putInt(totalFreeSpaceOff, getOrigTotalFreeSpace());
@@ -310,34 +397,6 @@
}
@Override
- public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception {
- int slot = slotManager.insertSlot(tupleIndex, buf.getInt(freeSpaceOff));
- int prefixSlotNum = slotManager.decodeFirstSlotField(slot);
- int numPrefixFields = 0;
- if (prefixSlotNum != FieldPrefixSlotManager.TUPLE_UNCOMPRESSED) {
- int prefixSlotOff = slotManager.getPrefixSlotOff(prefixSlotNum);
- int prefixSlot = buf.getInt(prefixSlotOff);
- numPrefixFields = slotManager.decodeFirstSlotField(prefixSlot);
- } else {
- buf.putInt(uncompressedTupleCountOff, buf.getInt(uncompressedTupleCountOff) + 1);
- }
-
- int freeSpace = buf.getInt(freeSpaceOff);
- int bytesWritten = tupleWriter.writeTupleFields(tuple, numPrefixFields,
- tuple.getFieldCount() - numPrefixFields, buf, freeSpace);
-
- buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
- buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + bytesWritten);
- buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - bytesWritten - slotManager.getSlotSize());
- }
-
- @Override
- public void update(ITupleReference newTuple, int oldTupleIndex, boolean inPlace) throws Exception {
- // TODO Auto-generated method stub
-
- }
-
- @Override
public void printHeader() {
// TODO Auto-generated method stub
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeLeafFrameType.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeLeafFrameType.java
new file mode 100644
index 0000000..6ff44be
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeLeafFrameType.java
@@ -0,0 +1,6 @@
+package edu.uci.ics.hyracks.storage.am.btree.frames;
+
+public enum BTreeLeafFrameType {
+ REGULAR_NSM,
+ FIELD_PREFIX_COMPRESSED_NSM
+}
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 0d56cb0..3ccd039 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
@@ -26,7 +26,7 @@
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeDuplicateKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
index 0ffc400..aa01ccb 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
@@ -20,7 +20,7 @@
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeDuplicateKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
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 d1ba794..335630a 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.Collections;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
@@ -26,7 +25,8 @@
import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
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.frames.BTreeFieldPrefixNSMLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNotUpdateableException;
import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrame;
import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
@@ -44,7 +44,6 @@
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.SlotOffTupleOff;
import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriter;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
@@ -121,36 +120,13 @@
@Override
public void create(int fileId, ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame) throws Exception {
-
- if (created)
- return;
-
treeLatch.writeLock().lock();
try {
-
- // check if another thread beat us to it
- if (created)
+ if (created) {
return;
-
- freePageManager.init(metaFrame, rootPage);
-
- // initialize root page
- ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), true);
- pins++;
-
- rootNode.acquireWriteLatch();
- writeLatchesAcquired++;
- try {
- leafFrame.setPage(rootNode);
- leafFrame.initBuffer((byte) 0);
- } finally {
- rootNode.releaseWriteLatch();
- writeLatchesReleased++;
- bufferCache.unpin(rootNode);
- unpins++;
}
- currentLevel = 0;
-
+ freePageManager.init(metaFrame, rootPage);
+ initRoot(leafFrame, true);
created = true;
} finally {
treeLatch.writeLock().unlock();
@@ -381,14 +357,14 @@
ctx.interiorFrame.setPage(originalPage);
}
- private void reinitRoot(BTreeOpContext ctx) throws HyracksDataException {
- ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), false);
+ private void initRoot(ITreeIndexFrame leafFrame, boolean firstInit) throws HyracksDataException {
+ ICachedPage rootNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rootPage), firstInit);
pins++;
rootNode.acquireWriteLatch();
writeLatchesAcquired++;
try {
- ctx.leafFrame.setPage(rootNode);
- ctx.leafFrame.initBuffer((byte) 0);
+ leafFrame.setPage(rootNode);
+ leafFrame.initBuffer((byte) 0);
currentLevel = 0; // debug
} finally {
rootNode.releaseWriteLatch();
@@ -489,7 +465,7 @@
if (ctx.splitKey.getBuffer() != null) {
if (ctx.op == IndexOp.DELETE) {
// Reset level of root to zero.
- reinitRoot(ctx);
+ initRoot(ctx.leafFrame, false);
} else {
// Insert or update op. Create a new root.
createNewRoot(ctx);
@@ -510,6 +486,12 @@
@Override
public void update(ITupleReference tuple, IndexOpContext ictx) throws Exception {
+ // Updating a tuple's key necessitates deleting the old entry, and inserting the new entry.
+ // This call only allows updating of non-key fields.
+ // The user of the BTree is responsible for dealing with non-key updates (i.e., doing a delete + insert).
+ if (cmp.getFieldCount() == cmp.getKeyFieldCount()) {
+ throw new BTreeNotUpdateableException("Cannot perform updates when the entire tuple forms the key.");
+ }
insertUpdateOrDelete(tuple, ictx);
}
@@ -806,7 +788,7 @@
treeLatchesAcquired++;
try {
- ctx.leafFrame.delete(tuple, cmp, true);
+ ctx.leafFrame.delete(tuple, cmp, false);
// to propagate the deletion we only need to make the
// splitKey != null
// we can reuse data to identify which key to delete in
@@ -879,7 +861,7 @@
}
}
} else { // leaf will not become empty
- ctx.leafFrame.delete(tuple, cmp, true);
+ ctx.leafFrame.delete(tuple, cmp, false);
node.releaseWriteLatch();
writeLatchesReleased++;
bufferCache.unpin(node);
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 bacd16c..3929433 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
@@ -24,7 +24,7 @@
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
public final class BTreeOpContext implements IndexOpContext {
- public final IndexOp op;
+ public IndexOp op;
public final IBTreeLeafFrame leafFrame;
public final IBTreeInteriorFrame interiorFrame;
public final ITreeIndexMetaDataFrame metaFrame;
@@ -67,4 +67,8 @@
smPages.clear();
opRestarts = 0;
}
+
+ public void setIndexOp(IndexOp op) {
+ this.op = op;
+ }
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixTupleReference.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixTupleReference.java
index 27c63f0..09be0bb 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixTupleReference.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/FieldPrefixTupleReference.java
@@ -46,7 +46,7 @@
@Override
public void setFieldCount(int fieldStartIndex, int fieldCount) {
- // not implemented
+ throw new UnsupportedOperationException("Not supported.");
}
@Override
@@ -88,13 +88,25 @@
// unsupported operation
@Override
public void resetByTupleOffset(ByteBuffer buf, int tupleStartOffset) {
- frame = null;
+ throw new UnsupportedOperationException("Resetting this type of frame by offset is not supported.");
}
@Override
public int getTupleSize() {
- // TODO Auto-generated method stub
- return 0;
+ return getSuffixTupleSize() + getPrefixTupleSize();
+ }
+
+ public int getSuffixTupleSize() {
+ helperTuple.setFieldCount(numPrefixFields, fieldCount - numPrefixFields);
+ helperTuple.resetByTupleOffset(frame.getBuffer(), suffixTupleStartOff);
+ return helperTuple.getTupleSize();
+ }
+
+ public int getPrefixTupleSize() {
+ if (numPrefixFields == 0) return 0;
+ helperTuple.setFieldCount(numPrefixFields);
+ helperTuple.resetByTupleOffset(frame.getBuffer(), prefixTupleStartOff);
+ return helperTuple.getTupleSize();
}
public int getNumPrefixFields() {
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeUtils.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeUtils.java
new file mode 100644
index 0000000..39a3e20
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeUtils.java
@@ -0,0 +1,58 @@
+package edu.uci.ics.hyracks.storage.am.btree.util;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeFieldPrefixNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+public class BTreeUtils {
+ public static BTree createBTree(IBufferCache bufferCache, int btreeFileId, ITypeTrait[] typeTraits, IBinaryComparator[] cmps, BTreeLeafFrameType leafType) throws BTreeException {
+ MultiComparator cmp = new MultiComparator(typeTraits, cmps);
+ TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(typeTraits);
+ ITreeIndexFrameFactory leafFrameFactory = getLeafFrameFactory(tupleWriterFactory, leafType);
+ ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, btreeFileId, 0, metaFrameFactory);
+ BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, cmp);
+ return btree;
+ }
+
+ public static MultiComparator getSearchMultiComparator(MultiComparator btreeCmp, ITupleReference searchKey) {
+ if (btreeCmp.getKeyFieldCount() == searchKey.getFieldCount()) {
+ return btreeCmp;
+ }
+ IBinaryComparator[] cmps = new IBinaryComparator[searchKey.getFieldCount()];
+ for (int i = 0; i < searchKey.getFieldCount(); i++) {
+ cmps[i] = btreeCmp.getComparators()[i];
+ }
+ return new MultiComparator(btreeCmp.getTypeTraits(), cmps);
+ }
+
+ public static ITreeIndexFrameFactory getLeafFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory, BTreeLeafFrameType leafType) throws BTreeException {
+ switch(leafType) {
+ case REGULAR_NSM: {
+ return new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+ }
+ case FIELD_PREFIX_COMPRESSED_NSM: {
+ return new BTreeFieldPrefixNSMLeafFrameFactory(tupleWriterFactory);
+ }
+ default: {
+ throw new BTreeException("Unknown BTreeLeafFrameType: " + leafType.toString());
+ }
+ }
+ }
+}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
index 7c576e0..e1a0dd6 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
@@ -15,7 +15,9 @@
package edu.uci.ics.hyracks.storage.am.common.impls;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
@@ -30,17 +32,18 @@
private int tupleIndex = 0;
private int fileId = -1;
- int currentPageId = -1;
- int maxPageId = -1;
+ private int currentPageId = -1;
+ private int maxPageId = -1;
private ICachedPage page = null;
private ITreeIndexFrame frame = null;
private IBufferCache bufferCache = null;
-
+ private int fieldCount;
+
private ITreeIndexTupleReference frameTuple;
public TreeDiskOrderScanCursor(ITreeIndexFrame frame) {
- this.frame = frame;
- this.frameTuple = frame.getTupleWriter().createTupleReference();
+ this.frame = frame;
+ this.frameTuple = frame.createTupleReference();
}
@Override
@@ -62,8 +65,7 @@
private boolean positionToNextLeaf(boolean skipCurrent)
throws HyracksDataException {
- while ((frame.getLevel() != 0 || skipCurrent)
- && (currentPageId <= maxPageId) || (frame.getTupleCount() == 0)) {
+ while ((frame.getLevel() != 0 || skipCurrent) && (currentPageId <= maxPageId)) {
currentPageId++;
ICachedPage nextPage = bufferCache.pin(
@@ -86,18 +88,20 @@
}
@Override
- public boolean hasNext() throws Exception {
+ public boolean hasNext() throws Exception {
+ if (currentPageId > maxPageId) {
+ return false;
+ }
if (tupleIndex >= frame.getTupleCount()) {
boolean nextLeafExists = positionToNextLeaf(true);
if (nextLeafExists) {
- frameTuple.resetByTupleIndex(frame, tupleIndex);
+ frameTuple.resetByTupleIndex(frame, tupleIndex);
return true;
} else {
return false;
}
- }
-
- frameTuple.resetByTupleIndex(frame, tupleIndex);
+ }
+ frameTuple.resetByTupleIndex(frame, tupleIndex);
return true;
}
@@ -115,15 +119,12 @@
bufferCache.unpin(page);
}
page = initialState.getPage();
- tupleIndex = 0;
+ tupleIndex = 0;
frame.setPage(page);
MultiComparator lowKeyCmp = searchPred.getLowKeyComparator();
- frameTuple.setFieldCount(lowKeyCmp.getFieldCount());
- boolean leafExists = positionToNextLeaf(false);
- if (!leafExists) {
- throw new HyracksDataException(
- "Failed to open disk-order scan cursor for tree index. Traget tree index has no leaves.");
- }
+ fieldCount = lowKeyCmp.getFieldCount();
+ frameTuple.setFieldCount(fieldCount);
+ positionToNextLeaf(false);
}
@Override
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java
deleted file mode 100644
index a189953..0000000
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java
+++ /dev/null
@@ -1,13 +0,0 @@
-package edu.uci.ics.hyracks.storage.am.btree;
-
-import org.junit.Test;
-
-import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
-
-public class BTreeDeleteTest extends AbstractBTreeTest {
-
- @Test
- public void blubb() {
-
- }
-}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java
index 7ef38b6..10d96d2 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java
@@ -16,7 +16,6 @@
package edu.uci.ics.hyracks.storage.am.btree;
import java.io.DataOutput;
-import java.io.File;
import java.nio.ByteBuffer;
import java.util.Random;
@@ -31,7 +30,6 @@
import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
import edu.uci.ics.hyracks.api.dataflow.value.TypeTrait;
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
-import edu.uci.ics.hyracks.api.io.FileReference;
import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
@@ -40,19 +38,15 @@
import edu.uci.ics.hyracks.dataflow.common.data.comparators.IntegerBinaryComparatorFactory;
import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
import edu.uci.ics.hyracks.storage.am.btree.api.IPrefixSlotManager;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeFieldPrefixNSMLeafFrame;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeException;
import edu.uci.ics.hyracks.storage.am.btree.impls.FieldPrefixSlotManager;
import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriter;
-import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
-import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
-import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
-import edu.uci.ics.hyracks.test.support.TestUtils;
public class BTreeFieldPrefixNSMTest extends AbstractBTreeTest {
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java
deleted file mode 100644
index 973385a..0000000
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java
+++ /dev/null
@@ -1,183 +0,0 @@
-/*
- * Copyright 2009-2010 by The Regents of the University of California
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * you may obtain a copy of the License from
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package edu.uci.ics.hyracks.storage.am.btree;
-
-import org.junit.Test;
-
-import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
-import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
-import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
-import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
-import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
-import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestUtils;
-
-/**
- * Tests the BTree insert operation in the following scenarios:
- * 1. Integer fields:
- * 1.1. One key, one value
- * 1.2. Two keys, no value
- * 1.3. Two keys, two values
- * 2. String fields:
- * 2.1. One key, one value
- * 2.2. Two keys, no value
- * 2.3. Two keys, two values
- *
- * Each tests consists of the following steps:
- * 1. Insert randomly generated tuples.
- * 2. Perform ordered scan and print results.
- * 3. Perform disk-order scan and print results.
- * 4. Perform range search and print results.
- *
- */
-@SuppressWarnings("rawtypes")
-public class BTreeInsertTest extends AbstractBTreeTest {
-
- @Test
- public void oneIntKeyAndValue() throws Exception {
- LOGGER.info("BTree Test With One Int Key And Value.");
-
- ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
- BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, 1);
- BTreeTestUtils.fillIntBTree(testCtx, 10000);
-
- BTreeTestUtils.checkOrderedScan(testCtx);
- BTreeTestUtils.checkDiskOrderScan(testCtx);
-
- // Range search in [-1000, 1000];
- ITupleReference lowKey = TupleUtils.createIntegerTuple(-1000);
- ITupleReference highKey = TupleUtils.createIntegerTuple(1000);
- BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
-
- testCtx.btree.close();
- }
-
- @Test
- public void twoIntKeys() throws Exception {
- LOGGER.info("BTree Test With Two Int Keys.");
-
- ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
- BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, 2);
- BTreeTestUtils.fillIntBTree(testCtx, 10000);
-
- BTreeTestUtils.checkOrderedScan(testCtx);
- BTreeTestUtils.checkDiskOrderScan(testCtx);
-
- // Range search in [50 0, 50 500];
- ITupleReference lowKey = TupleUtils.createIntegerTuple(50, 0);
- ITupleReference highKey = TupleUtils.createIntegerTuple(50, 500);
- BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
-
- // Prefix range search in [50, 50]
- ITupleReference prefixLowKey = TupleUtils.createIntegerTuple(50);
- ITupleReference prefixHighKey = TupleUtils.createIntegerTuple(50);
- BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
-
- testCtx.btree.close();
- }
-
- @Test
- public void twoIntKeysAndValues() throws Exception {
- LOGGER.info("BTree Test With Two Int Keys And Values.");
-
- ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
- BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, 2);
- BTreeTestUtils.fillIntBTree(testCtx, 10000);
-
- BTreeTestUtils.checkOrderedScan(testCtx);
- BTreeTestUtils.checkDiskOrderScan(testCtx);
-
- // Range search in [50 100, 100 100];
- ITupleReference lowKey = TupleUtils.createIntegerTuple(-100, -100);
- ITupleReference highKey = TupleUtils.createIntegerTuple(100, 100);
- BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
-
- // Prefix range search in [50, 50]
- ITupleReference prefixLowKey = TupleUtils.createIntegerTuple(50);
- ITupleReference prefixHighKey = TupleUtils.createIntegerTuple(50);
- BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
-
- testCtx.btree.close();
- }
-
- @Test
- public void oneStringKeyAndValue() throws Exception {
- LOGGER.info("BTree Test With One String Key And Value.");
-
- ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
- BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, 1);
- BTreeTestUtils.fillStringBTree(testCtx, 10000);
-
- BTreeTestUtils.checkOrderedScan(testCtx);
- BTreeTestUtils.checkDiskOrderScan(testCtx);
-
- // Range search in ["cbf", cc7"]
- ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
- ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7");
- BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
-
- testCtx.btree.close();
- }
-
- @Test
- public void twoStringKeys() throws Exception {
- LOGGER.info("BTree Test With Two String Keys.");
-
- ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
- BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, 2);
- BTreeTestUtils.fillStringBTree(testCtx, 10000);
-
- BTreeTestUtils.checkOrderedScan(testCtx);
- BTreeTestUtils.checkDiskOrderScan(testCtx);
-
- // Range search in ["cbf", "ddd", cc7", "eee"]
- ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf", "ddd");
- ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7", "eee");
- BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
-
- // Prefix range search in ["cbf", cc7"]
- ITupleReference prefixLowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
- ITupleReference prefixHighKey = TupleUtils.createTuple(fieldSerdes, "cc7");
- BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
-
- testCtx.btree.close();
- }
-
- @Test
- public void twoStringKeysAndValues() throws Exception {
- LOGGER.info("BTree Test With Two String Keys And Values.");
-
- ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
- BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, 2);
- BTreeTestUtils.fillStringBTree(testCtx, 10000);
-
- BTreeTestUtils.checkOrderedScan(testCtx);
- BTreeTestUtils.checkDiskOrderScan(testCtx);
-
- // Range search in ["cbf", "ddd", cc7", "eee"]
- ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf", "ddd");
- ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7", "eee");
- BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
-
- // Prefix range search in ["cbf", cc7"]
- ITupleReference prefixLowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
- ITupleReference prefixHighKey = TupleUtils.createTuple(fieldSerdes, "cc7");
- BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
-
- testCtx.btree.close();
- }
-}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
index 09eb7ea..1253c6f 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
@@ -150,7 +150,7 @@
TreeIndexStatsGatherer statsGatherer = new TreeIndexStatsGatherer(bufferCache, freePageManager, fileId,
btree.getRootPageId());
TreeIndexStats stats = statsGatherer.gatherStats(leafFrame, interiorFrame, metaFrame);
- LOGGER.info(stats.toString());
+ LOGGER.info("\n" + stats.toString());
TreeIndexBufferCacheWarmup bufferCacheWarmup = new TreeIndexBufferCacheWarmup(bufferCache, freePageManager,
fileId);
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
index 05e8941..f1469f1 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
@@ -293,7 +293,7 @@
// fixed-length "value" field
// fill B-tree with random values using insertions (not bulk load)
// perform ordered scan and range search
- //@Test
+ @Test
public void test02() throws Exception {
LOGGER.info("COMPOSITE KEY TEST");
@@ -391,7 +391,6 @@
//System.out.println("---------------------------------");
}
- /*
long end = System.currentTimeMillis();
long duration = end - start;
LOGGER.info("DURATION: " + duration);
@@ -468,7 +467,7 @@
rangeCursor.next();
ITupleReference frameTuple = rangeCursor.getTuple();
String rec = cmp.printTuple(frameTuple, recDescSers);
- print(rec + "\n");
+ LOGGER.info(rec);
}
} catch (Exception e) {
e.printStackTrace();
@@ -476,7 +475,6 @@
rangeCursor.close();
}
- */
btree.close();
bufferCache.closeFile(fileId);
@@ -488,7 +486,7 @@
// variable-length "value" field
// fill B-tree with random values using insertions (not bulk load)
// perform ordered scan and range search
- //@Test
+ @Test
public void test03() throws Exception {
LOGGER.info("VARIABLE-LENGTH KEY TEST");
@@ -661,7 +659,7 @@
// fill B-tree with random values using insertions, then delete entries
// one-by-one
// repeat procedure a few times on same B-tree
- //@Test
+ @Test
public void test04() throws Exception {
LOGGER.info("DELETION TEST");
@@ -1028,7 +1026,7 @@
// insert 100,000 records in bulk
// B-tree has a composite key to "simulate" non-unique index creation
// do range search
- //@Test
+ @Test
public void test06() throws Exception {
LOGGER.info("BULK LOAD TEST");
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTestDriver.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTestDriver.java
new file mode 100644
index 0000000..ef1e5e3
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTestDriver.java
@@ -0,0 +1,119 @@
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
+
+@SuppressWarnings("rawtypes")
+public abstract class BTreeTestDriver extends AbstractBTreeTest {
+
+ protected static final int numTuplesToInsert = 10000;
+
+ protected abstract void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType, ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey) throws Exception;
+ protected abstract String getTestOpName();
+
+ @Test
+ public void oneIntKeyAndValue() throws Exception {
+ LOGGER.info("BTree " + getTestOpName() + " Test With One Int Key And Value.");
+
+ ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+ // Range search in [-1000, 1000]
+ ITupleReference lowKey = TupleUtils.createIntegerTuple(-1000);
+ ITupleReference highKey = TupleUtils.createIntegerTuple(1000);
+
+ runTest(fieldSerdes, 1, BTreeLeafFrameType.REGULAR_NSM, lowKey, highKey, null, null);
+ runTest(fieldSerdes, 1, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM, lowKey, highKey, null, null);
+ }
+
+ @Test
+ public void twoIntKeys() throws Exception {
+ LOGGER.info("BTree " + getTestOpName() + " Test With Two Int Keys.");
+
+ ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+
+ // Range search in [50 0, 50 500]
+ ITupleReference lowKey = TupleUtils.createIntegerTuple(50, 0);
+ ITupleReference highKey = TupleUtils.createIntegerTuple(50, 500);
+
+ // Prefix range search in [50, 50]
+ ITupleReference prefixLowKey = TupleUtils.createIntegerTuple(50);
+ ITupleReference prefixHighKey = TupleUtils.createIntegerTuple(50);
+
+ runTest(fieldSerdes, 2, BTreeLeafFrameType.REGULAR_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+ runTest(fieldSerdes, 2, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+ }
+
+ @Test
+ public void twoIntKeysAndValues() throws Exception {
+ LOGGER.info("BTree " + getTestOpName() + " Test With Two Int Keys And Values.");
+
+ ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+
+ // Range search in [50 100, 100 100]
+ ITupleReference lowKey = TupleUtils.createIntegerTuple(-100, -100);
+ ITupleReference highKey = TupleUtils.createIntegerTuple(100, 100);
+
+ // Prefix range search in [50, 50]
+ ITupleReference prefixLowKey = TupleUtils.createIntegerTuple(50);
+ ITupleReference prefixHighKey = TupleUtils.createIntegerTuple(50);
+
+ runTest(fieldSerdes, 2, BTreeLeafFrameType.REGULAR_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+ runTest(fieldSerdes, 2, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+ }
+
+ @Test
+ public void oneStringKeyAndValue() throws Exception {
+ LOGGER.info("BTree " + getTestOpName() + " Test With One String Key And Value.");
+
+ ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
+
+ // Range search in ["cbf", cc7"]
+ ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
+ ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7");
+
+ runTest(fieldSerdes, 1, BTreeLeafFrameType.REGULAR_NSM, lowKey, highKey, null, null);
+ runTest(fieldSerdes, 1, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM, lowKey, highKey, null, null);
+ }
+
+ @Test
+ public void twoStringKeys() throws Exception {
+ LOGGER.info("BTree " + getTestOpName() + " Test With Two String Keys.");
+
+ ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
+
+ // Range search in ["cbf", "ddd", cc7", "eee"]
+ ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf", "ddd");
+ ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7", "eee");
+
+ // Prefix range search in ["cbf", cc7"]
+ ITupleReference prefixLowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
+ ITupleReference prefixHighKey = TupleUtils.createTuple(fieldSerdes, "cc7");
+
+ runTest(fieldSerdes, 2, BTreeLeafFrameType.REGULAR_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+ runTest(fieldSerdes, 2, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+ }
+
+ @Test
+ public void twoStringKeysAndValues() throws Exception {
+ LOGGER.info("BTree " + getTestOpName() + " Test With Two String Keys And Values.");
+
+ ISerializerDeserializer[] fieldSerdes = { UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE, UTF8StringSerializerDeserializer.INSTANCE };
+
+ // Range search in ["cbf", "ddd", cc7", "eee"]
+ ITupleReference lowKey = TupleUtils.createTuple(fieldSerdes, "cbf", "ddd");
+ ITupleReference highKey = TupleUtils.createTuple(fieldSerdes, "cc7", "eee");
+
+ // Prefix range search in ["cbf", cc7"]
+ ITupleReference prefixLowKey = TupleUtils.createTuple(fieldSerdes, "cbf");
+ ITupleReference prefixHighKey = TupleUtils.createTuple(fieldSerdes, "cc7");
+
+ runTest(fieldSerdes, 2, BTreeLeafFrameType.REGULAR_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+ runTest(fieldSerdes, 2, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM, lowKey, highKey, prefixLowKey, prefixHighKey);
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BulkLoadTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BulkLoadTest.java
new file mode 100644
index 0000000..49d08a3
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BulkLoadTest.java
@@ -0,0 +1,53 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestUtils;
+
+@SuppressWarnings("rawtypes")
+public class BulkLoadTest extends BTreeTestDriver {
+
+ @Override
+ protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType, ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey) throws Exception {
+ BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, numKeys, leafType);
+
+ // We assume all fieldSerdes are of the same type. Check the first one to determine which field types to generate.
+ if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
+ BTreeTestUtils.bulkLoadIntTuples(testCtx, numTuplesToInsert, rnd);
+ } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
+ BTreeTestUtils.bulkLoadStringTuples(testCtx, numTuplesToInsert, rnd);
+ }
+
+ BTreeTestUtils.checkPointSearches(testCtx);
+ BTreeTestUtils.checkOrderedScan(testCtx);
+ BTreeTestUtils.checkDiskOrderScan(testCtx);
+ BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
+ if (prefixLowKey != null && prefixHighKey != null) {
+ BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
+ }
+ }
+
+ @Override
+ protected String getTestOpName() {
+ return "BulkLoad";
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/DeleteTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/DeleteTest.java
new file mode 100644
index 0000000..2157adb
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/DeleteTest.java
@@ -0,0 +1,63 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestUtils;
+
+@SuppressWarnings("rawtypes")
+public class DeleteTest extends BTreeTestDriver {
+
+ private static final int numInsertRounds = 3;
+ private static final int numDeleteRounds = 3;
+
+ @Override
+ protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType, ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey) throws Exception {
+ BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, numKeys, leafType);
+ for (int i = 0; i < numInsertRounds; i++) {
+
+ // We assume all fieldSerdes are of the same type. Check the first one to determine which field types to generate.
+ if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
+ BTreeTestUtils.insertIntTuples(testCtx, numTuplesToInsert, rnd);
+ } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
+ BTreeTestUtils.insertStringTuples(testCtx, numTuplesToInsert, rnd);
+ }
+
+ int numTuplesPerDeleteRound = (int)Math.ceil((float)testCtx.checkTuples.size() / (float)numDeleteRounds);
+ for(int j = 0; j < numDeleteRounds; j++) {
+ BTreeTestUtils.deleteTuples(testCtx, numTuplesPerDeleteRound, rnd);
+
+ BTreeTestUtils.checkPointSearches(testCtx);
+ BTreeTestUtils.checkOrderedScan(testCtx);
+ BTreeTestUtils.checkDiskOrderScan(testCtx);
+ BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
+ if (prefixLowKey != null && prefixHighKey != null) {
+ BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
+ }
+ }
+ }
+ }
+
+ @Override
+ protected String getTestOpName() {
+ return "Delete";
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/InsertTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/InsertTest.java
new file mode 100644
index 0000000..fa3f895
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/InsertTest.java
@@ -0,0 +1,65 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestUtils;
+
+/**
+ * Tests the BTree insert operation with strings and integer fields using
+ * various numbers of key and payload fields.
+ *
+ * Each tests first fills a BTree with randomly generated tuples.
+ * We compare the following operations against expected results:
+ * 1. Point searches for all tuples.
+ * 2. Ordered scan.
+ * 3. Disk-order scan.
+ * 4. Range search (and prefix search for composite keys).
+ *
+ */
+@SuppressWarnings("rawtypes")
+public class InsertTest extends BTreeTestDriver {
+ @Override
+ protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType, ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey) throws Exception {
+ BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, numKeys, leafType);
+ // We assume all fieldSerdes are of the same type. Check the first one to determine which field types to generate.
+ if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
+ BTreeTestUtils.insertIntTuples(testCtx, numTuplesToInsert, rnd);
+ } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
+ BTreeTestUtils.insertStringTuples(testCtx, numTuplesToInsert, rnd);
+ }
+
+ BTreeTestUtils.checkPointSearches(testCtx);
+ BTreeTestUtils.checkOrderedScan(testCtx);
+ BTreeTestUtils.checkDiskOrderScan(testCtx);
+
+ BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
+ if (prefixLowKey != null && prefixHighKey != null) {
+ BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
+ }
+ testCtx.btree.close();
+ }
+
+ @Override
+ protected String getTestOpName() {
+ return "Insert";
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java
index 82adfde..9e8a7cd 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/RangeSearchCursorTest.java
@@ -38,11 +38,11 @@
import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
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.exceptions.BTreeException;
import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeFieldPrefixNSMLeafFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
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.BTreeOpContext;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/UpdateTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/UpdateTest.java
new file mode 100644
index 0000000..b40539f
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/UpdateTest.java
@@ -0,0 +1,64 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestUtils;
+
+@SuppressWarnings("rawtypes")
+public class UpdateTest extends BTreeTestDriver {
+ private static final int numUpdateRounds = 3;
+
+ @Override
+ protected void runTest(ISerializerDeserializer[] fieldSerdes, int numKeys, BTreeLeafFrameType leafType, ITupleReference lowKey, ITupleReference highKey, ITupleReference prefixLowKey, ITupleReference prefixHighKey) throws Exception {
+ // This is a noop because we can only update non-key fields.
+ if (fieldSerdes.length == numKeys) {
+ return;
+ }
+
+ BTreeTestContext testCtx = BTreeTestUtils.createBTreeTestContext(bufferCache, btreeFileId, fieldSerdes, numKeys, leafType);
+
+ // We assume all fieldSerdes are of the same type. Check the first one to determine which field types to generate.
+ if (fieldSerdes[0] instanceof IntegerSerializerDeserializer) {
+ BTreeTestUtils.insertIntTuples(testCtx, numTuplesToInsert, rnd);
+ } else if (fieldSerdes[0] instanceof UTF8StringSerializerDeserializer) {
+ BTreeTestUtils.insertStringTuples(testCtx, numTuplesToInsert, rnd);
+ }
+
+ int numTuplesPerDeleteRound = (int)Math.ceil((float)testCtx.checkTuples.size() / (float)numUpdateRounds);
+ for(int j = 0; j < numUpdateRounds; j++) {
+ BTreeTestUtils.updateTuples(testCtx, numTuplesPerDeleteRound, rnd);
+
+ BTreeTestUtils.checkPointSearches(testCtx);
+ BTreeTestUtils.checkOrderedScan(testCtx);
+ BTreeTestUtils.checkDiskOrderScan(testCtx);
+ BTreeTestUtils.checkRangeSearch(testCtx, lowKey, highKey, true, true);
+ if (prefixLowKey != null && prefixHighKey != null) {
+ BTreeTestUtils.checkRangeSearch(testCtx, prefixLowKey, prefixHighKey, true, true);
+ }
+ }
+ }
+
+ @Override
+ protected String getTestOpName() {
+ return "Update";
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
index 19ae81a..dff1e9c 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
@@ -3,6 +3,7 @@
import java.io.File;
import java.text.SimpleDateFormat;
import java.util.Date;
+import java.util.Random;
import java.util.logging.Logger;
import org.junit.After;
@@ -18,20 +19,22 @@
public abstract class AbstractBTreeTest {
protected static final Logger LOGGER = Logger.getLogger(AbstractBTreeTest.class.getName());
-
+ public static final long RANDOM_SEED = 50;
+
private static final int PAGE_SIZE = 256;
private static final int NUM_PAGES = 10;
private static final int MAX_OPEN_FILES = 10;
private static final int HYRACKS_FRAME_SIZE = 128;
-
+
protected IHyracksTaskContext ctx;
protected IBufferCache bufferCache;
protected int btreeFileId;
+ protected final Random rnd = new Random();
protected final static SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
protected final static String tmpDir = System.getProperty("java.io.tmpdir");
protected final static String sep = System.getProperty("file.separator");
- protected String fileName;
+ protected String fileName;
@Before
public void setUp() throws HyracksDataException {
@@ -44,6 +47,7 @@
bufferCache.createFile(file);
btreeFileId = fmp.lookupFileId(file);
bufferCache.openFile(btreeFileId);
+ rnd.setSeed(RANDOM_SEED);
}
@After
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestUtils.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestUtils.java
index 52bebe6..f73d1a1 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestUtils.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestUtils.java
@@ -5,6 +5,7 @@
import java.io.ByteArrayInputStream;
import java.io.DataInput;
import java.io.DataInputStream;
+import java.io.DataOutput;
import java.util.Iterator;
import java.util.NavigableSet;
import java.util.Random;
@@ -15,52 +16,38 @@
import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
import edu.uci.ics.hyracks.dataflow.common.util.SerdeUtils;
import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
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.frames.BTreeNSMInteriorFrameFactory;
-import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeDuplicateKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
-import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeDuplicateKeyException;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
-import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
-import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
-import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
import edu.uci.ics.hyracks.storage.am.common.impls.TreeDiskOrderScanCursor;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
@SuppressWarnings("rawtypes")
public class BTreeTestUtils {
- private static final Logger LOGGER = Logger.getLogger(BTreeTestUtils.class.getName());
- private static final long RANDOM_SEED = 50;
+ private static final Logger LOGGER = Logger.getLogger(BTreeTestUtils.class.getName());
- public static BTree createBTree(IBufferCache bufferCache, int btreeFileId, ITypeTrait[] typeTraits, IBinaryComparator[] cmps) {
- MultiComparator cmp = new MultiComparator(typeTraits, cmps);
- TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(typeTraits);
- ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
- ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
- ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
- IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, btreeFileId, 0, metaFrameFactory);
- BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, cmp);
- return btree;
- }
-
- public static BTreeTestContext createBTreeTestContext(IBufferCache bufferCache, int btreeFileId, ISerializerDeserializer[] fieldSerdes, int numKeyFields) throws Exception {
+ public static BTreeTestContext createBTreeTestContext(IBufferCache bufferCache, int btreeFileId, ISerializerDeserializer[] fieldSerdes, int numKeyFields, BTreeLeafFrameType leafType) throws Exception {
ITypeTrait[] typeTraits = SerdeUtils.serdesToTypeTraits(fieldSerdes, fieldSerdes.length);
IBinaryComparator[] cmps = SerdeUtils.serdesToComparators(fieldSerdes, numKeyFields);
- BTree btree = BTreeTestUtils.createBTree(bufferCache, btreeFileId, typeTraits, cmps);
+ BTree btree = BTreeUtils.createBTree(bufferCache, btreeFileId, typeTraits, cmps, leafType);
IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame) btree.getInteriorFrameFactory().createFrame();
@@ -87,7 +74,7 @@
}
@SuppressWarnings("unchecked")
- private static CheckTuple createCheckTupleFromTuple(ITupleReference tuple, int numKeys, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
+ private static CheckTuple createCheckTupleFromTuple(ITupleReference tuple, ISerializerDeserializer[] fieldSerdes, int numKeys) throws HyracksDataException {
CheckTuple checkTuple = new CheckTuple(fieldSerdes.length, numKeys);
int numFields = Math.min(fieldSerdes.length, tuple.getFieldCount());
for (int i = 0; i < numFields; i++) {
@@ -101,6 +88,18 @@
return checkTuple;
}
+ @SuppressWarnings("unchecked")
+ private static void createTupleFromCheckTuple(CheckTuple checkTuple, ArrayTupleBuilder tupleBuilder, ArrayTupleReference tuple, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
+ int fieldCount = tupleBuilder.getFieldEndOffsets().length;
+ DataOutput dos = tupleBuilder.getDataOutput();
+ tupleBuilder.reset();
+ for (int i = 0; i < fieldCount; i++) {
+ fieldSerdes[i].serialize(checkTuple.get(i), dos);
+ tupleBuilder.addFieldEndOffset();
+ }
+ tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+ }
+
public static void checkOrderedScan(BTreeTestContext testCtx) throws Exception {
LOGGER.info("Testing Ordered Scan:");
ITreeIndexCursor scanCursor = new BTreeRangeSearchCursor(testCtx.leafFrame);
@@ -138,7 +137,7 @@
while (diskOrderCursor.hasNext()) {
diskOrderCursor.next();
ITupleReference tuple = diskOrderCursor.getTuple();
- CheckTuple checkTuple = createCheckTupleFromTuple(tuple, testCtx.btree.getMultiComparator().getKeyFieldCount(), testCtx.fieldSerdes);
+ CheckTuple checkTuple = createCheckTupleFromTuple(tuple, testCtx.fieldSerdes, testCtx.btree.getMultiComparator().getKeyFieldCount());
if (!testCtx.checkTuples.contains(checkTuple)) {
fail("Disk-order scan returned unexpected answer: " + checkTuple.toString());
}
@@ -157,19 +156,19 @@
public static void checkRangeSearch(BTreeTestContext testCtx, ITupleReference lowKey, ITupleReference highKey, boolean lowKeyInclusive, boolean highKeyInclusive) throws Exception {
LOGGER.info("Testing Range Search:");
- MultiComparator lowKeyCmp = getSearchMultiComparator(testCtx.btree.getMultiComparator(), lowKey);
- MultiComparator highKeyCmp = getSearchMultiComparator(testCtx.btree.getMultiComparator(), highKey);
+ MultiComparator lowKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator(), lowKey);
+ MultiComparator highKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator(), highKey);
ITreeIndexCursor searchCursor = new BTreeRangeSearchCursor(testCtx.leafFrame);
RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, lowKeyInclusive, highKeyInclusive, lowKeyCmp, highKeyCmp);
BTreeOpContext searchOpCtx = testCtx.btree.createOpContext(IndexOp.SEARCH, testCtx.leafFrame, testCtx.interiorFrame, null);
testCtx.btree.search(searchCursor, rangePred, searchOpCtx);
// Get the subset of elements from the expected set within given key range.
- CheckTuple lowKeyCheck = createCheckTupleFromTuple(lowKey, lowKeyCmp.getKeyFieldCount(), testCtx.fieldSerdes);
- CheckTuple highKeyCheck = createCheckTupleFromTuple(highKey, highKeyCmp.getKeyFieldCount(), testCtx.fieldSerdes);
+ CheckTuple lowKeyCheck = createCheckTupleFromTuple(lowKey, testCtx.fieldSerdes, lowKeyCmp.getKeyFieldCount());
+ CheckTuple highKeyCheck = createCheckTupleFromTuple(highKey, testCtx.fieldSerdes, highKeyCmp.getKeyFieldCount());
NavigableSet<CheckTuple> expectedSubset = null;
if (lowKeyCmp.getKeyFieldCount() < testCtx.btree.getMultiComparator().getKeyFieldCount() ||
highKeyCmp.getKeyFieldCount() < testCtx.btree.getMultiComparator().getKeyFieldCount()) {
- // Searching on a key prefix (on low key or high key or both).
+ // Searching on a key prefix (low key or high key or both).
expectedSubset = getPrefixExpectedSubset(testCtx.checkTuples, lowKeyCheck, highKeyCheck);
} else {
// Searching on all key fields.
@@ -196,6 +195,48 @@
}
}
+ public static void checkPointSearches(BTreeTestContext testCtx) throws Exception {
+ LOGGER.info("Testing Point Searches On All Expected Keys:");
+ ITreeIndexCursor searchCursor = new BTreeRangeSearchCursor(testCtx.leafFrame);
+
+ ArrayTupleBuilder lowKeyBuilder = new ArrayTupleBuilder(testCtx.btree.getMultiComparator().getKeyFieldCount());
+ ArrayTupleReference lowKey = new ArrayTupleReference();
+ ArrayTupleBuilder highKeyBuilder = new ArrayTupleBuilder(testCtx.btree.getMultiComparator().getKeyFieldCount());
+ ArrayTupleReference highKey = new ArrayTupleReference();
+
+ BTreeOpContext searchOpCtx = testCtx.btree.createOpContext(IndexOp.SEARCH, testCtx.leafFrame, testCtx.interiorFrame, null);
+ RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, null, null);
+
+ // Iterate through expected tuples, and perform a point search in the BTree to verify the tuple can be reached.
+ for (CheckTuple checkTuple : testCtx.checkTuples) {
+ createTupleFromCheckTuple(checkTuple, lowKeyBuilder, lowKey, testCtx.fieldSerdes);
+ createTupleFromCheckTuple(checkTuple, highKeyBuilder, highKey, testCtx.fieldSerdes);
+ MultiComparator lowKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator(), lowKey);
+ MultiComparator highKeyCmp = BTreeUtils.getSearchMultiComparator(testCtx.btree.getMultiComparator(), highKey);
+
+ rangePred.setLowKey(lowKey, true);
+ rangePred.setHighKey(highKey, true);
+ rangePred.setLowKeyComparator(lowKeyCmp);
+ rangePred.setHighKeyComparator(highKeyCmp);
+
+ testCtx.btree.search(searchCursor, rangePred, searchOpCtx);
+
+ try {
+ // We expect exactly one answer.
+ if (searchCursor.hasNext()) {
+ searchCursor.next();
+ ITupleReference tuple = searchCursor.getTuple();
+ compareActualAndExpected(tuple, checkTuple, testCtx.fieldSerdes);
+ }
+ if (searchCursor.hasNext()) {
+ fail("Point search returned more than one answer.");
+ }
+ } finally {
+ searchCursor.close();
+ }
+ }
+ }
+
@SuppressWarnings("unchecked")
// Create a new TreeSet containing the elements satisfying the prefix search.
// Implementing prefix search by changing compareTo() in CheckTuple does not work.
@@ -225,17 +266,6 @@
return expectedSubset;
}
- public static MultiComparator getSearchMultiComparator(MultiComparator btreeCmp, ITupleReference searchKey) {
- if (btreeCmp.getKeyFieldCount() == searchKey.getFieldCount()) {
- return btreeCmp;
- }
- IBinaryComparator[] cmps = new IBinaryComparator[searchKey.getFieldCount()];
- for (int i = 0; i < searchKey.getFieldCount(); i++) {
- cmps[i] = btreeCmp.getComparators()[i];
- }
- return new MultiComparator(btreeCmp.getTypeTraits(), cmps);
- }
-
private static String printCursorResults(BTree btree, ITreeIndexCursor cursor, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException, Exception {
StringBuilder strBuilder = new StringBuilder();
strBuilder.append("\n");
@@ -248,13 +278,10 @@
return strBuilder.toString();
}
- public static void fillIntBTree(BTreeTestContext testCtx, int numTuples) throws Exception {
+ public static void insertIntTuples(BTreeTestContext testCtx, int numTuples, Random rnd) throws Exception {
int numFields = testCtx.getFieldCount();
int numKeyFields = testCtx.getKeyFieldCount();
- Random rnd = new Random();
- rnd.setSeed(RANDOM_SEED);
-
BTreeOpContext insertOpCtx = testCtx.btree.createOpContext(IndexOp.INSERT, testCtx.leafFrame, testCtx.interiorFrame, testCtx.metaFrame);
int[] tupleValues = new int[testCtx.getFieldCount()];
@@ -288,13 +315,11 @@
}
}
- public static void fillStringBTree(BTreeTestContext testCtx, int numTuples) throws Exception {
+ public static void insertStringTuples(BTreeTestContext testCtx, int numTuples, Random rnd) throws Exception {
int numFields = testCtx.getFieldCount();
int numKeyFields = testCtx.getKeyFieldCount();
BTreeOpContext insertOpCtx = testCtx.btree.createOpContext(IndexOp.INSERT, testCtx.leafFrame, testCtx.interiorFrame, testCtx.metaFrame);
- Random rnd = new Random();
- rnd.setSeed(RANDOM_SEED);
Object[] tupleValues = new Object[numFields];
for (int i = 0; i < numTuples; i++) {
if ((i + 1) % (numTuples / 10) == 0) {
@@ -324,6 +349,156 @@
}
}
+ public static void bulkLoadIntTuples(BTreeTestContext testCtx, int numTuples, Random rnd) throws Exception {
+ int numFields = testCtx.getFieldCount();
+ int numKeyFields = testCtx.getKeyFieldCount();
+ int[] tupleValues = new int[testCtx.getFieldCount()];
+ int maxValue = (int)Math.ceil(Math.pow(numTuples, 1.0/(double)numKeyFields));
+ for (int i = 0; i < numTuples; i++) {
+ // Set keys.
+ for (int j = 0; j < numKeyFields; j++) {
+ tupleValues[j] = rnd.nextInt() % maxValue;
+ }
+ // Set values.
+ for (int j = numKeyFields; j < numFields; j++) {
+ tupleValues[j] = j;
+ }
+
+ // Set expected values. We also use these as the pre-sorted stream for bulk loading.
+ CheckTuple<Integer> checkTuple = new CheckTuple<Integer>(numFields, numKeyFields);
+ for(int v : tupleValues) {
+ checkTuple.add(v);
+ }
+ testCtx.checkTuples.add(checkTuple);
+ }
+
+ bulkLoadCheckTuples(testCtx, numTuples);
+ }
+
+ public static void bulkLoadStringTuples(BTreeTestContext testCtx, int numTuples, Random rnd) throws Exception {
+ int numFields = testCtx.getFieldCount();
+ int numKeyFields = testCtx.getKeyFieldCount();
+ String[] tupleValues = new String[numFields];
+ for (int i = 0; i < numTuples; i++) {
+ // Set keys.
+ for (int j = 0; j < numKeyFields; j++) {
+ int length = (Math.abs(rnd.nextInt()) % 10) + 1;
+ tupleValues[j] = getRandomString(length, rnd);
+ }
+ // Set values.
+ for (int j = numKeyFields; j < numFields; j++) {
+ tupleValues[j] = getRandomString(5, rnd);
+ }
+ // Set expected values. We also use these as the pre-sorted stream for bulk loading.
+ CheckTuple<String> checkTuple = new CheckTuple<String>(numFields, numKeyFields);
+ for(String v : tupleValues) {
+ checkTuple.add(v);
+ }
+ testCtx.checkTuples.add(checkTuple);
+ }
+
+ bulkLoadCheckTuples(testCtx, numTuples);
+ }
+
+ private static void bulkLoadCheckTuples(BTreeTestContext testCtx, int numTuples) throws HyracksDataException {
+ int numFields = testCtx.getFieldCount();
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(numFields);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ // Perform bulk load.
+ IIndexBulkLoadContext bulkLoadCtx = testCtx.btree.beginBulkLoad(0.7f, testCtx.leafFrame, testCtx.interiorFrame, testCtx.metaFrame);
+ int c = 1;
+ for (CheckTuple checkTuple : testCtx.checkTuples) {
+ if (c % (numTuples / 10) == 0) {
+ LOGGER.info("Bulk Loading Tuple " + c + "/" + numTuples);
+ }
+ createTupleFromCheckTuple(checkTuple, tupleBuilder, tuple, testCtx.fieldSerdes);
+ testCtx.btree.bulkLoadAddTuple(bulkLoadCtx, tuple);
+ c++;
+ }
+ testCtx.btree.endBulkLoad(bulkLoadCtx);
+ }
+
+ public static void deleteTuples(BTreeTestContext testCtx, int numTuples, Random rnd) throws Exception {
+ ArrayTupleBuilder deleteTupleBuilder = new ArrayTupleBuilder(testCtx.btree.getMultiComparator().getKeyFieldCount());
+ ArrayTupleReference deleteTuple = new ArrayTupleReference();
+ int numCheckTuples = testCtx.checkTuples.size();
+ BTreeOpContext deleteOpCtx = testCtx.btree.createOpContext(IndexOp.DELETE, testCtx.leafFrame, testCtx.interiorFrame, testCtx.metaFrame);
+ // Copy CheckTuple references into array, so we can randomly pick from there.
+ CheckTuple[] checkTuples = new CheckTuple[numCheckTuples];
+ int idx = 0;
+ for (CheckTuple checkTuple : testCtx.checkTuples) {
+ checkTuples[idx++] = checkTuple;
+ }
+ for (int i = 0; i < numTuples && numCheckTuples > 0; i++) {
+ if ((i + 1) % (numTuples / 10) == 0) {
+ LOGGER.info("Deleting Tuple " + (i + 1) + "/" + numTuples);
+ }
+ int checkTupleIdx = Math.abs(rnd.nextInt() % numCheckTuples);
+ CheckTuple checkTuple = checkTuples[checkTupleIdx];
+ createTupleFromCheckTuple(checkTuple, deleteTupleBuilder, deleteTuple, testCtx.fieldSerdes);
+ testCtx.btree.delete(deleteTuple, deleteOpCtx);
+
+ // Remove check tuple from expected results.
+ testCtx.checkTuples.remove(checkTuple);
+
+ // Swap with last "valid" CheckTuple.
+ CheckTuple tmp = checkTuples[numCheckTuples - 1];
+ checkTuples[numCheckTuples - 1] = checkTuple;
+ checkTuples[checkTupleIdx] = tmp;
+ numCheckTuples--;
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ public static void updateTuples(BTreeTestContext testCtx, int numTuples, Random rnd) throws Exception {
+ int fieldCount = testCtx.btree.getMultiComparator().getFieldCount();
+ int keyFieldCount = testCtx.btree.getMultiComparator().getKeyFieldCount();
+ // This is a noop because we can only update non-key fields.
+ if (fieldCount == keyFieldCount) {
+ return;
+ }
+ ArrayTupleBuilder updateTupleBuilder = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference updateTuple = new ArrayTupleReference();
+ int numCheckTuples = testCtx.checkTuples.size();
+ BTreeOpContext updateOpCtx = testCtx.btree.createOpContext(IndexOp.UPDATE, testCtx.leafFrame, testCtx.interiorFrame, testCtx.metaFrame);
+ // Copy CheckTuple references into array, so we can randomly pick from there.
+ CheckTuple[] checkTuples = new CheckTuple[numCheckTuples];
+ int idx = 0;
+ for (CheckTuple checkTuple : testCtx.checkTuples) {
+ checkTuples[idx++] = checkTuple;
+ }
+ for (int i = 0; i < numTuples && numCheckTuples > 0; i++) {
+ if ((i + 1) % (numTuples / 10) == 0) {
+ LOGGER.info("Updating Tuple " + (i + 1) + "/" + numTuples);
+ }
+ int checkTupleIdx = Math.abs(rnd.nextInt() % numCheckTuples);
+ CheckTuple checkTuple = checkTuples[checkTupleIdx];
+ // Update check tuple's non-key fields.
+ for (int j = keyFieldCount; j < fieldCount; j++) {
+ Comparable newValue = getRandomUpdateValue(testCtx.fieldSerdes[j], rnd);
+ checkTuple.set(j, newValue);
+ }
+
+ createTupleFromCheckTuple(checkTuple, updateTupleBuilder, updateTuple, testCtx.fieldSerdes);
+ testCtx.btree.update(updateTuple, updateOpCtx);
+
+ // Swap with last "valid" CheckTuple.
+ CheckTuple tmp = checkTuples[numCheckTuples - 1];
+ checkTuples[numCheckTuples - 1] = checkTuple;
+ checkTuples[checkTupleIdx] = tmp;
+ numCheckTuples--;
+ }
+ }
+
+ private static Comparable getRandomUpdateValue(ISerializerDeserializer serde, Random rnd) {
+ if (serde instanceof IntegerSerializerDeserializer) {
+ return Integer.valueOf(rnd.nextInt());
+ } else if (serde instanceof UTF8StringSerializerDeserializer) {
+ return getRandomString(10, rnd);
+ }
+ return null;
+ }
+
public static String getRandomString(int length, Random rnd) {
String s = Long.toHexString(Double.doubleToLongBits(rnd.nextDouble()));
StringBuilder strBuilder = new StringBuilder();
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/CheckTuple.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/CheckTuple.java
index 97874be..f945ab9 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/CheckTuple.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/CheckTuple.java
@@ -47,6 +47,10 @@
return (T)tuple[idx];
}
+ public void set(int idx, T e) {
+ tuple[idx] = e;
+ }
+
public int size() {
return tuple.length;
}