Added a bunch of utility functions and classes related to serdes, comparators and tuples. Finished new BTree insert test while laying the groundwork for the other new tests.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_btree_updates_next@597 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/SerdeUtils.java b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/SerdeUtils.java
new file mode 100644
index 0000000..cc35a13
--- /dev/null
+++ b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/SerdeUtils.java
@@ -0,0 +1,90 @@
+/*
+ * 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.util;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.dataflow.common.data.comparators.DoubleBinaryComparatorFactory;
+import edu.uci.ics.hyracks.dataflow.common.data.comparators.FloatBinaryComparatorFactory;
+import edu.uci.ics.hyracks.dataflow.common.data.comparators.IntegerBinaryComparatorFactory;
+import edu.uci.ics.hyracks.dataflow.common.data.comparators.UTF8StringBinaryComparatorFactory;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.BooleanSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.FloatSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.Integer64SerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+
+@SuppressWarnings("rawtypes")
+public class SerdeUtils {
+ public static ITypeTrait[] serdesToTypeTraits(ISerializerDeserializer[] serdes, int numSerdes) {
+ ITypeTrait[] typeTraits = new ITypeTrait[numSerdes];
+ for (int i = 0; i < numSerdes; i++) {
+ typeTraits[i] = serdeToTypeTrait(serdes[i]);
+ }
+ return typeTraits;
+ }
+
+ public static ITypeTrait serdeToTypeTrait(ISerializerDeserializer serde) {
+ if (serde instanceof IntegerSerializerDeserializer) {
+ return ITypeTrait.INTEGER_TYPE_TRAIT;
+ }
+ if (serde instanceof Integer64SerializerDeserializer) {
+ return ITypeTrait.INTEGER64_TYPE_TRAIT;
+ }
+ if (serde instanceof FloatSerializerDeserializer) {
+ return ITypeTrait.FLOAT_TYPE_TRAIT;
+ }
+ if (serde instanceof DoubleSerializerDeserializer) {
+ return ITypeTrait.DOUBLE_TYPE_TRAIT;
+ }
+ if (serde instanceof BooleanSerializerDeserializer) {
+ return ITypeTrait.BOOLEAN_TYPE_TRAIT;
+ }
+ return ITypeTrait.VARLEN_TYPE_TRAIT;
+ }
+
+ public static IBinaryComparator[] serdesToComparators(ISerializerDeserializer[] serdes, int numSerdes) {
+ IBinaryComparator[] comparators = new IBinaryComparator[numSerdes];
+ for (int i = 0; i < numSerdes; i++) {
+ comparators[i] = serdeToComparator(serdes[i]);
+ }
+ return comparators;
+ }
+
+ public static IBinaryComparator serdeToComparator(ISerializerDeserializer serde) {
+ if (serde instanceof IntegerSerializerDeserializer) {
+ return IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+ }
+ if (serde instanceof Integer64SerializerDeserializer) {
+ throw new UnsupportedOperationException("Binary comparator for Integer64 not implemented.");
+ }
+ if (serde instanceof FloatSerializerDeserializer) {
+ return FloatBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+ }
+ if (serde instanceof DoubleSerializerDeserializer) {
+ return DoubleBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+ }
+ if (serde instanceof BooleanSerializerDeserializer) {
+ throw new UnsupportedOperationException("Binary comparator for Boolean not implemented.");
+ }
+ if (serde instanceof UTF8StringSerializerDeserializer) {
+ return UTF8StringBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+ }
+ throw new UnsupportedOperationException("Binary comparator for + " + serde.toString() + " not implemented.");
+ }
+}
diff --git a/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.java
new file mode 100644
index 0000000..801206b
--- /dev/null
+++ b/hyracks-dataflow-common/src/main/java/edu/uci/ics/hyracks/dataflow/common/util/TupleUtils.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.dataflow.common.util;
+
+import java.io.DataOutput;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+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;
+
+@SuppressWarnings("rawtypes")
+public class TupleUtils {
+ @SuppressWarnings("unchecked")
+ public static void createTuple(ArrayTupleBuilder tupleBuilder, ArrayTupleReference tuple, ISerializerDeserializer[] fieldSerdes, final Object... fields) throws HyracksDataException {
+ DataOutput dos = tupleBuilder.getDataOutput();
+ tupleBuilder.reset();
+ for (int i = 0; i < fields.length; i++) {
+ fieldSerdes[i].serialize(fields[i], dos);
+ tupleBuilder.addFieldEndOffset();
+ }
+ tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+ }
+
+ public static ITupleReference createTuple(ISerializerDeserializer[] fieldSerdes, final Object... fields) throws HyracksDataException {
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fields.length);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ createTuple(tupleBuilder, tuple, fieldSerdes, fields);
+ return tuple;
+ }
+
+ public static void createIntegerTuple(ArrayTupleBuilder tupleBuilder, ArrayTupleReference tuple,
+ final int... fields) throws HyracksDataException {
+ DataOutput dos = tupleBuilder.getDataOutput();
+ tupleBuilder.reset();
+ for (final int i : fields) {
+ IntegerSerializerDeserializer.INSTANCE.serialize(i, dos);
+ tupleBuilder.addFieldEndOffset();
+ }
+ tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+ }
+
+ public static ITupleReference createIntegerTuple(final int... fields) throws HyracksDataException {
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fields.length);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ createIntegerTuple(tupleBuilder, tuple, fields);
+ return tuple;
+ }
+}
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 01b91b1..7c576e0 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
@@ -114,7 +114,6 @@
page.releaseReadLatch();
bufferCache.unpin(page);
}
-
page = initialState.getPage();
tupleIndex = 0;
frame.setPage(page);
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
index 2989404..81da948 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
@@ -92,7 +92,10 @@
tuple.getFieldLength(i));
DataInput dataIn = new DataInputStream(inStream);
Object o = fields[i].deserialize(dataIn);
- strBuilder.append(o.toString() + " ");
+ strBuilder.append(o.toString());
+ if (i != fields.length - 1) {
+ strBuilder.append(" ");
+ }
}
return strBuilder.toString();
}
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
new file mode 100644
index 0000000..a189953
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java
@@ -0,0 +1,13 @@
+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 ab3d9d9..7ef38b6 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
@@ -43,6 +43,7 @@
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;
@@ -59,7 +60,6 @@
private static final int NUM_PAGES = 40;
private static final int MAX_OPEN_FILES = 10;
private static final int HYRACKS_FRAME_SIZE = 128;
- private IHyracksTaskContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
private ITupleReference createTuple(IHyracksTaskContext ctx, int f0, int f1, int f2, boolean print)
throws HyracksDataException {
@@ -97,14 +97,6 @@
@Test
public void test01() throws Exception {
- TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
- IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
- IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
- FileReference file = new FileReference(new File(fileName));
- bufferCache.createFile(file);
- int fileId = fmp.lookupFileId(file);
- bufferCache.openFile(fileId);
-
// declare fields
int fieldCount = 3;
ITypeTrait[] typeTraits = new ITypeTrait[fieldCount];
@@ -127,7 +119,7 @@
Random rnd = new Random();
rnd.setSeed(50);
- ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, 0), false);
+ ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(btreeFileId, 0), false);
try {
IPrefixSlotManager slotManager = new FieldPrefixSlotManager();
@@ -218,8 +210,21 @@
} finally {
bufferCache.unpin(page);
}
-
- bufferCache.closeFile(fileId);
- bufferCache.close();
+ }
+
+ public int getPageSize() {
+ return PAGE_SIZE;
+ }
+
+ public int getNumPages() {
+ return NUM_PAGES;
+ }
+
+ public int getHyracksFrameSize() {
+ return HYRACKS_FRAME_SIZE;
+ }
+
+ public int getMaxOpenFiles() {
+ return MAX_OPEN_FILES;
}
}
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
new file mode 100644
index 0000000..973385a
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java
@@ -0,0 +1,183 @@
+/*
+ * 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 3ef0cc2..09eb7ea 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
@@ -27,6 +27,7 @@
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.BTreeOpContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
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.ITreeIndexMetaDataFrame;
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 23eb0b2..05e8941 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
@@ -53,6 +53,7 @@
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.btree.util.AbstractBTreeTest;
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;
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTestUtils.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTestUtils.java
deleted file mode 100644
index 2e33eaf..0000000
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTestUtils.java
+++ /dev/null
@@ -1,92 +0,0 @@
-package edu.uci.ics.hyracks.storage.am.btree;
-
-import java.io.DataOutput;
-
-import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
-import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
-import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
-import edu.uci.ics.hyracks.api.dataflow.value.TypeTrait;
-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.marshalling.BooleanSerializerDeserializer;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.FloatSerializerDeserializer;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.Integer64SerializerDeserializer;
-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.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.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 BTreeTestUtils {
- public static void createIntTuple(ArrayTupleBuilder tupleBuilder, ArrayTupleReference tuple, final int... fields)
- throws HyracksDataException {
- DataOutput dos = tupleBuilder.getDataOutput();
- tupleBuilder.reset();
- for (final int i : fields) {
- IntegerSerializerDeserializer.INSTANCE.serialize(i, dos);
- tupleBuilder.addFieldEndOffset();
- }
- tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
- }
- public static void createStringTuple(ArrayTupleBuilder tupleBuilder, ArrayTupleReference tuple, final String... fields)
- throws HyracksDataException {
- DataOutput dos = tupleBuilder.getDataOutput();
- tupleBuilder.reset();
- for (final String s : fields) {
- UTF8StringSerializerDeserializer.INSTANCE.serialize(s, dos);
- tupleBuilder.addFieldEndOffset();
- }
- tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
- }
-
- 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;
- }
-
- @SuppressWarnings("rawtypes")
- public static ITypeTrait[] serdesToTypeTraits(ISerializerDeserializer[] serdes) {
- ITypeTrait[] typeTraits = new ITypeTrait[serdes.length];
- for (int i = 0; i < serdes.length; i++) {
- ISerializerDeserializer serde = serdes[i];
- if (serde instanceof IntegerSerializerDeserializer) {
- typeTraits[i] = ITypeTrait.INTEGER_TYPE_TRAIT;
- continue;
- }
- if (serde instanceof Integer64SerializerDeserializer) {
- typeTraits[i] = ITypeTrait.INTEGER64_TYPE_TRAIT;
- continue;
- }
- if (serde instanceof FloatSerializerDeserializer) {
- typeTraits[i] = ITypeTrait.FLOAT_TYPE_TRAIT;
- continue;
- }
- if (serde instanceof DoubleSerializerDeserializer) {
- typeTraits[i] = ITypeTrait.DOUBLE_TYPE_TRAIT;
- continue;
- }
- if (serde instanceof BooleanSerializerDeserializer) {
- typeTraits[i] = ITypeTrait.BOOLEAN_TYPE_TRAIT;
- continue;
- }
- typeTraits[i] = ITypeTrait.VARLEN_TYPE_TRAIT;
- }
- return typeTraits;
- }
-}
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
deleted file mode 100644
index 205527e..0000000
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/InsertTest.java
+++ /dev/null
@@ -1,199 +0,0 @@
-package edu.uci.ics.hyracks.storage.am.btree;
-
-import java.util.Random;
-
-import org.junit.Test;
-
-import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
-import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
-import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
-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.comparators.IntegerBinaryComparatorFactory;
-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.impls.BTree;
-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.ITreeIndexCursor;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
-import edu.uci.ics.hyracks.storage.am.common.impls.TreeDiskOrderScanCursor;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
-
-public class InsertTest extends AbstractBTreeTest {
-
- @Test
- public void test() throws Exception {
- LOGGER.info("FIXED-LENGTH KEY TEST");
-
- // declare fields
- ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
- int fieldCount = fieldSerdes.length;
- ITypeTrait[] typeTraits = BTreeTestUtils.serdesToTypeTraits(fieldSerdes);
-
- // declare keys
- int keyFieldCount = 1;
- IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
- cmps[0] = IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
-
- BTree btree = BTreeTestUtils.createBTree(bufferCache, btreeFileId, typeTraits, cmps);
-
- IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
- IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame) btree.getInteriorFrameFactory().createFrame();
- ITreeIndexMetaDataFrame metaFrame = btree.getFreePageManager().getMetaDataFrameFactory().createFrame();
-
- btree.create(btreeFileId, leafFrame, metaFrame);
- btree.open(btreeFileId);
-
- Random rnd = new Random();
- rnd.setSeed(50);
-
- long start = System.currentTimeMillis();
-
- LOGGER.info("INSERTING INTO TREE");
-
- ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
- ArrayTupleReference tuple = new ArrayTupleReference();
-
- BTreeOpContext insertOpCtx = btree.createOpContext(IndexOp.INSERT, leafFrame, interiorFrame, metaFrame);
-
- // 10000
- for (int i = 0; i < 10000; i++) {
- int f0 = rnd.nextInt() % 10000;
- int f1 = 5;
-
- BTreeTestUtils.createIntTuple(tupleBuilder, tuple, f0, f1);
-
- if (i % 1000 == 0) {
- long end = System.currentTimeMillis();
- LOGGER.info("INSERTING " + i + " : " + f0 + " " + f1 + " " + (end - start));
- }
-
- try {
- btree.insert(tuple, insertOpCtx);
- } catch (TreeIndexException e) {
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
- // btree.printTree(leafFrame, interiorFrame);
-
- int maxPage = btree.getFreePageManager().getMaxPage(metaFrame);
- LOGGER.info("MAXPAGE: " + maxPage);
- LOGGER.info(btree.printStats());
-
- long end = System.currentTimeMillis();
- long duration = end - start;
- LOGGER.info("DURATION: " + duration);
-
- // ordered scan
-
- LOGGER.info("ORDERED SCAN:");
- ITreeIndexCursor scanCursor = new BTreeRangeSearchCursor(leafFrame);
- RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null, null);
- BTreeOpContext searchOpCtx = btree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, null);
- btree.search(scanCursor, nullPred, searchOpCtx);
- try {
- while (scanCursor.hasNext()) {
- scanCursor.next();
- ITupleReference frameTuple = scanCursor.getTuple();
- String rec = btree.getMultiComparator().printTuple(frameTuple, fieldSerdes);
- LOGGER.info(rec);
- }
- } catch (Exception e) {
- e.printStackTrace();
- } finally {
- scanCursor.close();
- }
-
- // disk-order scan
- LOGGER.info("DISK-ORDER SCAN:");
- TreeDiskOrderScanCursor diskOrderCursor = new TreeDiskOrderScanCursor(leafFrame);
- BTreeOpContext diskOrderScanOpCtx = btree.createOpContext(IndexOp.DISKORDERSCAN, leafFrame, null, null);
- btree.diskOrderScan(diskOrderCursor, leafFrame, metaFrame, diskOrderScanOpCtx);
- try {
- while (diskOrderCursor.hasNext()) {
- diskOrderCursor.next();
- ITupleReference frameTuple = diskOrderCursor.getTuple();
- String rec = btree.getMultiComparator().printTuple(frameTuple, fieldSerdes);
- LOGGER.info(rec);
- }
- } catch (Exception e) {
- e.printStackTrace();
- } finally {
- diskOrderCursor.close();
- }
-
- /*
- // range search in [-1000, 1000]
- LOGGER.info("RANGE SEARCH:");
-
- ITreeIndexCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame);
-
- // build low and high keys
- ArrayTupleBuilder ktb = new ArrayTupleBuilder(cmp.getKeyFieldCount());
- DataOutput kdos = ktb.getDataOutput();
-
- ISerializerDeserializer[] keyDescSers = { IntegerSerializerDeserializer.INSTANCE };
- RecordDescriptor keyDesc = new RecordDescriptor(keyDescSers);
- IFrameTupleAccessor keyAccessor = new FrameTupleAccessor(ctx.getFrameSize(), keyDesc);
- keyAccessor.reset(frame);
-
- appender.reset(frame, true);
-
- // build and append low key
- ktb.reset();
- IntegerSerializerDeserializer.INSTANCE.serialize(-1000, kdos);
- ktb.addFieldEndOffset();
- appender.append(ktb.getFieldEndOffsets(), ktb.getByteArray(), 0, ktb.getSize());
-
- // build and append high key
- ktb.reset();
- IntegerSerializerDeserializer.INSTANCE.serialize(1000, kdos);
- ktb.addFieldEndOffset();
- appender.append(ktb.getFieldEndOffsets(), ktb.getByteArray(), 0, ktb.getSize());
-
- // create tuplereferences for search keys
- FrameTupleReference lowKey = new FrameTupleReference();
- lowKey.reset(keyAccessor, 0);
-
- FrameTupleReference highKey = new FrameTupleReference();
- highKey.reset(keyAccessor, 1);
-
- IBinaryComparator[] searchCmps = new IBinaryComparator[1];
- searchCmps[0] = IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
- MultiComparator searchCmp = new MultiComparator(typeTraits, searchCmps);
-
- RangePredicate rangePred = new RangePredicate(true, lowKey, highKey, true, true, searchCmp, searchCmp);
- btree.search(rangeCursor, rangePred, searchOpCtx);
-
- try {
- while (rangeCursor.hasNext()) {
- rangeCursor.next();
- ITupleReference frameTuple = rangeCursor.getTuple();
- String rec = cmp.printTuple(frameTuple, recDescSers);
- LOGGER.info(rec);
- }
- } catch (Exception e) {
- e.printStackTrace();
- } finally {
- rangeCursor.close();
- }
-
- btree.close();
- bufferCache.closeFile(fileId);
- bufferCache.close();
- */
-
- btree.close();
- }
-
- @Test
- public void test2() {
- System.out.println("Test 2");
- }
-}
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 7dada06..82adfde 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
@@ -18,9 +18,6 @@
import java.io.ByteArrayInputStream;
import java.io.DataInput;
import java.io.DataInputStream;
-import java.io.DataOutput;
-import java.io.File;
-import java.nio.ByteBuffer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
@@ -29,22 +26,16 @@
import org.junit.Before;
import org.junit.Test;
-import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
-import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
-import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
-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;
-import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
+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.comparators.IntegerBinaryComparatorFactory;
import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+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.BTreeFieldPrefixNSMLeafFrameFactory;
@@ -53,8 +44,9 @@
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.RangePredicate;
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.btree.util.AbstractBTreeTest;
import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
@@ -65,18 +57,9 @@
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;
-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 RangeSearchCursorTest extends AbstractBTreeTest {
- 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;
-
- // declare fields
+ // Declare fields
int fieldCount = 2;
ITypeTrait[] typeTraits = new ITypeTrait[fieldCount];
@@ -92,59 +75,35 @@
IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame)interiorFrameFactory.createFrame();
ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
- IHyracksTaskContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
- ByteBuffer frame = ctx.allocateFrame();
- FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
-
- ISerializerDeserializer[] recDescSers = {
- IntegerSerializerDeserializer.INSTANCE,
- IntegerSerializerDeserializer.INSTANCE };
- RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
- IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(),
- recDesc);
- FrameTupleReference tuple = new FrameTupleReference();
-
Random rnd = new Random(50);
@Before
- public void setUp() {
- typeTraits[0] = new TypeTrait(4);
+ public void setUp() throws HyracksDataException {
+ super.setUp();
+ typeTraits[0] = new TypeTrait(4);
typeTraits[1] = new TypeTrait(4);
- accessor.reset(frame);
}
@Test
public void uniqueIndexTest() throws Exception {
-
LOGGER.info("TESTING RANGE SEARCH CURSOR ON UNIQUE INDEX");
- TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
- IBufferCache bufferCache = TestStorageManagerComponentHolder
- .getBufferCache(ctx);
- IFileMapProvider fmp = TestStorageManagerComponentHolder
- .getFileMapProvider(ctx);
- FileReference file = new FileReference(new File(fileName));
- bufferCache.createFile(file);
- int fileId = fmp.lookupFileId(file);
- bufferCache.openFile(fileId);
-
// declare keys
int keyFieldCount = 1;
IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
- cmps[0] = IntegerBinaryComparatorFactory.INSTANCE
- .createBinaryComparator();
+ cmps[0] = IntegerBinaryComparatorFactory.INSTANCE.createBinaryComparator();
MultiComparator cmp = new MultiComparator(typeTraits, cmps);
- IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, btreeFileId, 0, metaFrameFactory);
BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmp);
- btree.create(fileId, leafFrame, metaFrame);
- btree.open(fileId);
+ btree.create(btreeFileId, leafFrame, metaFrame);
+ btree.open(btreeFileId);
- ArrayTupleBuilder tb = new ArrayTupleBuilder(cmp.getFieldCount());
- DataOutput dos = tb.getDataOutput();
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(cmp.getFieldCount());
+ ArrayTupleReference tuple = new ArrayTupleReference();
BTreeOpContext insertOpCtx = btree.createOpContext(IndexOp.INSERT,
leafFrame, interiorFrame, metaFrame);
@@ -165,18 +124,8 @@
// insert keys into btree
for (int i = 0; i < keys.size(); i++) {
- tb.reset();
- IntegerSerializerDeserializer.INSTANCE.serialize(keys.get(i)
- .intValue(), dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(i, dos);
- tb.addFieldEndOffset();
-
- appender.reset(frame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb
- .getSize());
-
- tuple.reset(accessor, 0);
+ TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+ tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
try {
btree.insert(tuple, insertOpCtx);
@@ -212,25 +161,12 @@
maxSearchKey, false, true, true, false);
btree.close();
- bufferCache.closeFile(fileId);
- bufferCache.close();
}
@Test
public void nonUniqueIndexTest() throws Exception {
-
LOGGER.info("TESTING RANGE SEARCH CURSOR ON NONUNIQUE INDEX");
- TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
- IBufferCache bufferCache = TestStorageManagerComponentHolder
- .getBufferCache(ctx);
- IFileMapProvider fmp = TestStorageManagerComponentHolder
- .getFileMapProvider(ctx);
- FileReference file = new FileReference(new File(fileName));
- bufferCache.createFile(file);
- int fileId = fmp.lookupFileId(file);
- bufferCache.openFile(fileId);
-
// declare keys
int keyFieldCount = 2;
IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
@@ -241,15 +177,15 @@
MultiComparator cmp = new MultiComparator(typeTraits, cmps);
- IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, btreeFileId, 0, metaFrameFactory);
BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmp);
- btree.create(fileId, leafFrame, metaFrame);
- btree.open(fileId);
+ btree.create(btreeFileId, leafFrame, metaFrame);
+ btree.open(btreeFileId);
- ArrayTupleBuilder tb = new ArrayTupleBuilder(cmp.getFieldCount());
- DataOutput dos = tb.getDataOutput();
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(cmp.getFieldCount());
+ ArrayTupleReference tuple = new ArrayTupleReference();
BTreeOpContext insertOpCtx = btree.createOpContext(IndexOp.INSERT,
leafFrame, interiorFrame, metaFrame);
@@ -267,18 +203,8 @@
// insert keys into btree
for (int i = 0; i < keys.size(); i++) {
- tb.reset();
- IntegerSerializerDeserializer.INSTANCE.serialize(keys.get(i)
- .intValue(), dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(i, dos);
- tb.addFieldEndOffset();
-
- appender.reset(frame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb
- .getSize());
-
- tuple.reset(accessor, 0);
+ TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+ tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
try {
btree.insert(tuple, insertOpCtx);
@@ -314,29 +240,16 @@
maxSearchKey, false, true, true, false);
btree.close();
- bufferCache.closeFile(fileId);
- bufferCache.close();
}
@Test
public void nonUniqueFieldPrefixIndexTest() throws Exception {
-
LOGGER.info("TESTING RANGE SEARCH CURSOR ON NONUNIQUE FIELD-PREFIX COMPRESSED INDEX");
ITreeIndexFrameFactory leafFrameFactory = new BTreeFieldPrefixNSMLeafFrameFactory(
tupleWriterFactory);
IBTreeLeafFrame leafFrame = (IBTreeLeafFrame)leafFrameFactory.createFrame();
- TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
- IBufferCache bufferCache = TestStorageManagerComponentHolder
- .getBufferCache(ctx);
- IFileMapProvider fmp = TestStorageManagerComponentHolder
- .getFileMapProvider(ctx);
- FileReference file = new FileReference(new File(fileName));
- bufferCache.createFile(file);
- int fileId = fmp.lookupFileId(file);
- bufferCache.openFile(fileId);
-
// declare keys
int keyFieldCount = 2;
IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
@@ -347,15 +260,15 @@
MultiComparator cmp = new MultiComparator(typeTraits, cmps);
- IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, btreeFileId, 0, metaFrameFactory);
BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmp);
- btree.create(fileId, leafFrame, metaFrame);
- btree.open(fileId);
+ btree.create(btreeFileId, leafFrame, metaFrame);
+ btree.open(btreeFileId);
- ArrayTupleBuilder tb = new ArrayTupleBuilder(cmp.getFieldCount());
- DataOutput dos = tb.getDataOutput();
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(cmp.getFieldCount());
+ ArrayTupleReference tuple = new ArrayTupleReference();
BTreeOpContext insertOpCtx = btree.createOpContext(IndexOp.INSERT,
leafFrame, interiorFrame, metaFrame);
@@ -373,18 +286,8 @@
// insert keys into btree
for (int i = 0; i < keys.size(); i++) {
- tb.reset();
- IntegerSerializerDeserializer.INSTANCE.serialize(keys.get(i)
- .intValue(), dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(i, dos);
- tb.addFieldEndOffset();
-
- appender.reset(frame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb
- .getSize());
-
- tuple.reset(accessor, 0);
+ TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+ tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
try {
btree.insert(tuple, insertOpCtx);
@@ -420,46 +323,16 @@
maxSearchKey, false, true, true, false);
btree.close();
- bufferCache.closeFile(fileId);
- bufferCache.close();
}
public RangePredicate createRangePredicate(int lk, int hk,
boolean isForward, boolean lowKeyInclusive,
boolean highKeyInclusive, MultiComparator cmp,
ITypeTrait[] typeTraits) throws HyracksDataException {
- // build low and high keys
- ArrayTupleBuilder ktb = new ArrayTupleBuilder(1);
- DataOutput kdos = ktb.getDataOutput();
-
- ISerializerDeserializer[] keyDescSers = { IntegerSerializerDeserializer.INSTANCE };
- RecordDescriptor keyDesc = new RecordDescriptor(keyDescSers);
- IFrameTupleAccessor keyAccessor = new FrameTupleAccessor(ctx
- .getFrameSize(), keyDesc);
- keyAccessor.reset(frame);
-
- appender.reset(frame, true);
-
- // build and append low key
- ktb.reset();
- IntegerSerializerDeserializer.INSTANCE.serialize(lk, kdos);
- ktb.addFieldEndOffset();
- appender.append(ktb.getFieldEndOffsets(), ktb.getByteArray(), 0, ktb
- .getSize());
-
- // build and append high key
- ktb.reset();
- IntegerSerializerDeserializer.INSTANCE.serialize(hk, kdos);
- ktb.addFieldEndOffset();
- appender.append(ktb.getFieldEndOffsets(), ktb.getByteArray(), 0, ktb
- .getSize());
// create tuplereferences for search keys
- FrameTupleReference lowKey = new FrameTupleReference();
- lowKey.reset(keyAccessor, 0);
-
- FrameTupleReference highKey = new FrameTupleReference();
- highKey.reset(keyAccessor, 1);
+ ITupleReference lowKey = TupleUtils.createIntegerTuple(lk);
+ ITupleReference highKey = TupleUtils.createIntegerTuple(hk);
IBinaryComparator[] searchCmps = new IBinaryComparator[1];
searchCmps[0] = IntegerBinaryComparatorFactory.INSTANCE
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/StorageManagerTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/StorageManagerTest.java
index 39bedac..7e4b2e3 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/StorageManagerTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/StorageManagerTest.java
@@ -22,23 +22,21 @@
import org.junit.Test;
-import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
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.storage.common.sync.LatchType;
import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
-import edu.uci.ics.hyracks.test.support.TestUtils;
public class StorageManagerTest extends AbstractBTreeTest {
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;
- private IHyracksTaskContext ctx = TestUtils.create(32768);
+ private static final int HYRACKS_FRAME_SIZE = 32768;
public class PinnedLatchedPage {
public final ICachedPage page;
@@ -255,4 +253,20 @@
bufferCache.close();
}
+
+ public int getPageSize() {
+ return PAGE_SIZE;
+ }
+
+ public int getNumPages() {
+ return NUM_PAGES;
+ }
+
+ public int getHyracksFrameSize() {
+ return HYRACKS_FRAME_SIZE;
+ }
+
+ public int getMaxOpenFiles() {
+ return MAX_OPEN_FILES;
+ }
}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/AbstractBTreeTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
similarity index 91%
rename from hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/AbstractBTreeTest.java
rename to hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
index c54a830..19ae81a 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/AbstractBTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
@@ -1,4 +1,4 @@
-package edu.uci.ics.hyracks.storage.am.btree;
+package edu.uci.ics.hyracks.storage.am.btree.util;
import java.io.File;
import java.text.SimpleDateFormat;
@@ -36,8 +36,8 @@
@Before
public void setUp() throws HyracksDataException {
fileName = tmpDir + sep + simpleDateFormat.format(new Date());
- ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
- TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+ ctx = TestUtils.create(getHyracksFrameSize());
+ TestStorageManagerComponentHolder.init(getPageSize(), getNumPages(), getMaxOpenFiles());
bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
FileReference file = new FileReference(new File(fileName));
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestContext.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestContext.java
new file mode 100644
index 0000000..a517b1f
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestContext.java
@@ -0,0 +1,59 @@
+/*
+ * 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.util;
+
+import java.util.TreeSet;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+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.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.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+@SuppressWarnings("rawtypes")
+public final class BTreeTestContext {
+ public final ISerializerDeserializer[] fieldSerdes;
+ public final IBufferCache bufferCache;
+ public final BTree btree;
+ public final IBTreeLeafFrame leafFrame;
+ public final IBTreeInteriorFrame interiorFrame;
+ public final ITreeIndexMetaDataFrame metaFrame;
+ public final ArrayTupleBuilder tupleBuilder;
+ public final ArrayTupleReference tuple = new ArrayTupleReference();
+ public final TreeSet<CheckTuple> checkTuples = new TreeSet<CheckTuple>();
+
+ public BTreeTestContext(IBufferCache bufferCache, ISerializerDeserializer[] fieldSerdes, BTree btree, IBTreeLeafFrame leafFrame,
+ IBTreeInteriorFrame interiorFrame, ITreeIndexMetaDataFrame metaFrame) {
+ this.bufferCache = bufferCache;
+ this.fieldSerdes = fieldSerdes;
+ this.btree = btree;
+ this.leafFrame = leafFrame;
+ this.interiorFrame = interiorFrame;
+ this.metaFrame = metaFrame;
+ this.tupleBuilder = new ArrayTupleBuilder(fieldSerdes.length);
+ }
+
+ public int getFieldCount() {
+ return fieldSerdes.length;
+ }
+
+ public int getKeyFieldCount() {
+ return btree.getMultiComparator().getKeyFieldCount();
+ }
+}
\ No newline at end of file
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
new file mode 100644
index 0000000..52bebe6
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestUtils.java
@@ -0,0 +1,335 @@
+package edu.uci.ics.hyracks.storage.am.btree.util;
+
+import static org.junit.Assert.fail;
+
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.util.Iterator;
+import java.util.NavigableSet;
+import java.util.Random;
+import java.util.TreeSet;
+import java.util.logging.Logger;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+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.data.accessors.ITupleReference;
+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.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.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;
+
+ 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 {
+ ITypeTrait[] typeTraits = SerdeUtils.serdesToTypeTraits(fieldSerdes, fieldSerdes.length);
+ IBinaryComparator[] cmps = SerdeUtils.serdesToComparators(fieldSerdes, numKeyFields);
+
+ BTree btree = BTreeTestUtils.createBTree(bufferCache, btreeFileId, typeTraits, cmps);
+
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) btree.getLeafFrameFactory().createFrame();
+ IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame) btree.getInteriorFrameFactory().createFrame();
+ ITreeIndexMetaDataFrame metaFrame = btree.getFreePageManager().getMetaDataFrameFactory().createFrame();
+
+ btree.create(btreeFileId, leafFrame, metaFrame);
+ btree.open(btreeFileId);
+
+ BTreeTestContext testCtx = new BTreeTestContext(bufferCache, fieldSerdes, btree, leafFrame, interiorFrame, metaFrame);
+ return testCtx;
+ }
+
+ private static void compareActualAndExpected(ITupleReference actual, CheckTuple expected, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
+ for (int i = 0; i < fieldSerdes.length; i++) {
+ ByteArrayInputStream inStream = new ByteArrayInputStream(
+ actual.getFieldData(i), actual.getFieldStart(i),
+ actual.getFieldLength(i));
+ DataInput dataIn = new DataInputStream(inStream);
+ Object actualObj = fieldSerdes[i].deserialize(dataIn);
+ if (!actualObj.equals(expected.get(i))) {
+ fail("Actual and expected fields do not match.\nExpected: " + expected.get(i) + "\nActual : " + actualObj);
+ }
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ private static CheckTuple createCheckTupleFromTuple(ITupleReference tuple, int numKeys, ISerializerDeserializer[] fieldSerdes) throws HyracksDataException {
+ CheckTuple checkTuple = new CheckTuple(fieldSerdes.length, numKeys);
+ int numFields = Math.min(fieldSerdes.length, tuple.getFieldCount());
+ for (int i = 0; i < numFields; i++) {
+ ByteArrayInputStream inStream = new ByteArrayInputStream(
+ tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i));
+ DataInput dataIn = new DataInputStream(inStream);
+ Comparable fieldObj = (Comparable)fieldSerdes[i].deserialize(dataIn);
+ checkTuple.add(fieldObj);
+ }
+ return checkTuple;
+ }
+
+ public static void checkOrderedScan(BTreeTestContext testCtx) throws Exception {
+ LOGGER.info("Testing Ordered Scan:");
+ ITreeIndexCursor scanCursor = new BTreeRangeSearchCursor(testCtx.leafFrame);
+ RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null, null);
+ BTreeOpContext searchOpCtx = testCtx.btree.createOpContext(IndexOp.SEARCH, testCtx.leafFrame, testCtx.interiorFrame, null);
+ testCtx.btree.search(scanCursor, nullPred, searchOpCtx);
+ Iterator<CheckTuple> checkIter = testCtx.checkTuples.iterator();
+ int actualCount = 0;
+ try {
+ while (scanCursor.hasNext()) {
+ if (!checkIter.hasNext()) {
+ fail("Ordered scan returned more answers than expected.\nExpected: " + testCtx.checkTuples.size());
+ }
+ scanCursor.next();
+ CheckTuple expectedTuple = checkIter.next();
+ ITupleReference tuple = scanCursor.getTuple();
+ compareActualAndExpected(tuple, expectedTuple, testCtx.fieldSerdes);
+ actualCount++;
+ }
+ if (actualCount < testCtx.checkTuples.size()) {
+ fail("Ordered scan returned fewer answers than expected.\nExpected: " + testCtx.checkTuples.size() + "\nActual : " + actualCount);
+ }
+ } finally {
+ scanCursor.close();
+ }
+ }
+
+ public static void checkDiskOrderScan(BTreeTestContext testCtx) throws Exception {
+ LOGGER.info("Testing Disk-Order Scan:");
+ ITreeIndexCursor diskOrderCursor = new TreeDiskOrderScanCursor(testCtx.leafFrame);
+ BTreeOpContext diskOrderScanOpCtx = testCtx.btree.createOpContext(IndexOp.DISKORDERSCAN, testCtx.leafFrame, null, null);
+ testCtx.btree.diskOrderScan(diskOrderCursor, testCtx.leafFrame, testCtx.metaFrame, diskOrderScanOpCtx);
+ int actualCount = 0;
+ try {
+ while (diskOrderCursor.hasNext()) {
+ diskOrderCursor.next();
+ ITupleReference tuple = diskOrderCursor.getTuple();
+ CheckTuple checkTuple = createCheckTupleFromTuple(tuple, testCtx.btree.getMultiComparator().getKeyFieldCount(), testCtx.fieldSerdes);
+ if (!testCtx.checkTuples.contains(checkTuple)) {
+ fail("Disk-order scan returned unexpected answer: " + checkTuple.toString());
+ }
+ actualCount++;
+ }
+ if (actualCount < testCtx.checkTuples.size()) {
+ fail("Disk-order scan returned fewer answers than expected.\nExpected: " + testCtx.checkTuples.size() + "\nActual : " + actualCount);
+ }
+ if (actualCount > testCtx.checkTuples.size()) {
+ fail("Disk-order scan returned more answers than expected.\nExpected: " + testCtx.checkTuples.size() + "\nActual : " + actualCount);
+ }
+ } finally {
+ diskOrderCursor.close();
+ }
+ }
+
+ 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);
+ 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);
+ 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).
+ expectedSubset = getPrefixExpectedSubset(testCtx.checkTuples, lowKeyCheck, highKeyCheck);
+ } else {
+ // Searching on all key fields.
+ expectedSubset = testCtx.checkTuples.subSet(lowKeyCheck, lowKeyInclusive, highKeyCheck, highKeyInclusive);
+ }
+ Iterator<CheckTuple> checkIter = expectedSubset.iterator();
+ int actualCount = 0;
+ try {
+ while (searchCursor.hasNext()) {
+ if (!checkIter.hasNext()) {
+ fail("Range search returned more answers than expected.\nExpected: " + expectedSubset.size());
+ }
+ searchCursor.next();
+ CheckTuple expectedTuple = checkIter.next();
+ ITupleReference tuple = searchCursor.getTuple();
+ compareActualAndExpected(tuple, expectedTuple, testCtx.fieldSerdes);
+ actualCount++;
+ }
+ if (actualCount < expectedSubset.size()) {
+ fail("Range search returned fewer answers than expected.\nExpected: " + expectedSubset.size() + "\nActual : " + actualCount);
+ }
+ } 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.
+ public static TreeSet<CheckTuple> getPrefixExpectedSubset(TreeSet<CheckTuple> checkTuples, CheckTuple lowKey, CheckTuple highKey) {
+ TreeSet<CheckTuple> expectedSubset = new TreeSet<CheckTuple>();
+ Iterator<CheckTuple> iter = checkTuples.iterator();
+ while(iter.hasNext()) {
+ CheckTuple t = iter.next();
+ boolean geLowKey = true;
+ boolean leHighKey = true;
+ for (int i = 0; i < lowKey.getNumKeys(); i++) {
+ if (t.get(i).compareTo(lowKey.get(i)) < 0) {
+ geLowKey = false;
+ break;
+ }
+ }
+ for (int i = 0; i < highKey.getNumKeys(); i++) {
+ if (t.get(i).compareTo(highKey.get(i)) > 0) {
+ leHighKey = false;
+ break;
+ }
+ }
+ if (geLowKey && leHighKey) {
+ expectedSubset.add(t);
+ }
+ }
+ 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");
+ while (cursor.hasNext()) {
+ cursor.next();
+ ITupleReference frameTuple = cursor.getTuple();
+ String tupleString = btree.getMultiComparator().printTuple(frameTuple, fieldSerdes);
+ strBuilder.append(tupleString + "\n");
+ }
+ return strBuilder.toString();
+ }
+
+ public static void fillIntBTree(BTreeTestContext testCtx, int numTuples) 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()];
+ // Scale range of values according to number of keys.
+ // For example, for 2 keys we want the square root of numTuples, for 3 keys the cube root of numTuples, etc.
+ 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;
+ }
+ TupleUtils.createIntegerTuple(testCtx.tupleBuilder, testCtx.tuple, tupleValues);
+ if ((i + 1) % (numTuples / 10) == 0) {
+ LOGGER.info("Inserting Tuple " + (i + 1) + "/" + numTuples);
+ }
+ try {
+ testCtx.btree.insert(testCtx.tuple, insertOpCtx);
+ // Set expected values. Do this only after insertion succeeds because we ignore duplicate keys.
+ CheckTuple<Integer> checkTuple = new CheckTuple<Integer>(numFields, numKeyFields);
+ for(int v : tupleValues) {
+ checkTuple.add(v);
+ }
+ testCtx.checkTuples.add(checkTuple);
+ } catch (BTreeDuplicateKeyException e) {
+ // Ignore duplicate key insertions.
+ }
+ }
+ }
+
+ public static void fillStringBTree(BTreeTestContext testCtx, int numTuples) 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) {
+ LOGGER.info("Inserting Tuple " + (i + 1) + "/" + numTuples);
+ }
+ // 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);
+ }
+ TupleUtils.createTuple(testCtx.tupleBuilder, testCtx.tuple, testCtx.fieldSerdes, tupleValues);
+ try {
+ testCtx.btree.insert(testCtx.tuple, insertOpCtx);
+ // Set expected values. Do this only after insertion succeeds because we ignore duplicate keys.
+ CheckTuple<String> checkTuple = new CheckTuple<String>(numFields, numKeyFields);
+ for(Object v : tupleValues) {
+ checkTuple.add((String)v);
+ }
+ testCtx.checkTuples.add(checkTuple);
+ } catch (BTreeDuplicateKeyException e) {
+ // Ignore duplicate key insertions.
+ }
+ }
+ }
+
+ public static String getRandomString(int length, Random rnd) {
+ String s = Long.toHexString(Double.doubleToLongBits(rnd.nextDouble()));
+ StringBuilder strBuilder = new StringBuilder();
+ for (int i = 0; i < s.length() && i < length; i++) {
+ strBuilder.append(s.charAt(Math.abs(rnd.nextInt()) % s.length()));
+ }
+ return strBuilder.toString();
+ }
+}
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
new file mode 100644
index 0000000..97874be
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/CheckTuple.java
@@ -0,0 +1,69 @@
+/*
+ * 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.util;
+
+@SuppressWarnings({"rawtypes", "unchecked"})
+public class CheckTuple<T extends Comparable<T>> implements Comparable<T> {
+ private final int numKeys;
+ private final Comparable[] tuple;
+ private int pos;
+
+ public CheckTuple(int numFields, int numKeys) {
+ this.numKeys = numKeys;
+ this.tuple = new Comparable[numFields];
+ pos = 0;
+ }
+
+ public void add(T e) {
+ tuple[pos++] = e;
+ }
+
+ @Override
+ public int compareTo(T o) {
+ CheckTuple<T> other = (CheckTuple<T>)o;
+ for (int i = 0; i < numKeys; i++) {
+ int cmp = tuple[i].compareTo(other.get(i));
+ if (cmp != 0) {
+ return cmp;
+ }
+ }
+ return 0;
+ }
+
+ public T get(int idx) {
+ return (T)tuple[idx];
+ }
+
+ public int size() {
+ return tuple.length;
+ }
+
+ public int getNumKeys() {
+ return numKeys;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder strBuilder = new StringBuilder();
+ for (int i = 0; i < tuple.length; i++) {
+ strBuilder.append(tuple[i].toString());
+ if (i != tuple.length-1) {
+ strBuilder.append(" ");
+ }
+ }
+ return strBuilder.toString();
+ }
+}
\ No newline at end of file