Created a test framework for the RTree and added the corresponding tests.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@1119 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-common/pom.xml b/hyracks-storage-am-common/pom.xml
index 9f0e53a..2a9b89d 100644
--- a/hyracks-storage-am-common/pom.xml
+++ b/hyracks-storage-am-common/pom.xml
@@ -52,5 +52,12 @@
<type>jar</type>
<scope>compile</scope>
</dependency>
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <version>4.8.1</version>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
</dependencies>
</project>
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/CheckTuple.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/CheckTuple.java
new file mode 100644
index 0000000..22cd5df
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/CheckTuple.java
@@ -0,0 +1,73 @@
+/*
+ * 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.common.test;
+
+@SuppressWarnings({"rawtypes", "unchecked"})
+public class CheckTuple<T extends Comparable<T>> implements Comparable<T> {
+ protected final int numKeys;
+ protected final Comparable[] tuple;
+ protected 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 void set(int idx, T e) {
+ tuple[idx] = e;
+ }
+
+ 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
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/ITreeIndexTestContext.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/ITreeIndexTestContext.java
new file mode 100644
index 0000000..cf9ca2e
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/ITreeIndexTestContext.java
@@ -0,0 +1,49 @@
+/*
+ * 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.common.test;
+
+import java.util.Collection;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+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.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+
+@SuppressWarnings("rawtypes")
+public interface ITreeIndexTestContext <T extends CheckTuple>{
+ public int getFieldCount();
+
+ public int getKeyFieldCount();
+
+ public ISerializerDeserializer[] getFieldSerdes();
+
+ public IBinaryComparatorFactory[] getComparatorFactories();
+
+ public ITreeIndexAccessor getIndexAccessor();
+
+ public ITreeIndex getIndex();
+
+ public ArrayTupleReference getTuple();
+
+ public ArrayTupleBuilder getTupleBuilder();
+
+ public void insertCheckTuple(T checkTuple, Collection<T> checkTuples);
+
+ public Collection<T> getCheckTuples();
+
+}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestContext.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestContext.java
new file mode 100644
index 0000000..4b0129c
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestContext.java
@@ -0,0 +1,68 @@
+/*
+ * 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.common.test;
+
+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.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+
+@SuppressWarnings("rawtypes")
+public abstract class TreeIndexTestContext<T extends CheckTuple> implements ITreeIndexTestContext<T> {
+ protected final ISerializerDeserializer[] fieldSerdes;
+ protected final ITreeIndex treeIndex;
+ protected final ArrayTupleBuilder tupleBuilder;
+ protected final ArrayTupleReference tuple = new ArrayTupleReference();
+ protected final ITreeIndexAccessor indexAccessor;
+
+ public TreeIndexTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
+ this.fieldSerdes = fieldSerdes;
+ this.treeIndex = treeIndex;
+ this.indexAccessor = treeIndex.createAccessor();
+ this.tupleBuilder = new ArrayTupleBuilder(fieldSerdes.length);
+ }
+
+ @Override
+ public int getFieldCount() {
+ return fieldSerdes.length;
+ }
+
+ @Override
+ public ITreeIndexAccessor getIndexAccessor() {
+ return indexAccessor;
+ }
+
+ @Override
+ public ArrayTupleReference getTuple() {
+ return tuple;
+ }
+
+ @Override
+ public ArrayTupleBuilder getTupleBuilder() {
+ return tupleBuilder;
+ }
+
+ @Override
+ public ISerializerDeserializer[] getFieldSerdes() {
+ return fieldSerdes;
+ }
+
+ @Override
+ public ITreeIndex getIndex() {
+ return treeIndex;
+ }
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestUtils.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestUtils.java
new file mode 100644
index 0000000..5b21485
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/test/TreeIndexTestUtils.java
@@ -0,0 +1,237 @@
+package edu.uci.ics.hyracks.storage.am.common.test;
+
+import static org.junit.Assert.fail;
+
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.io.DataOutput;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Random;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+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.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+
+@SuppressWarnings("rawtypes")
+public abstract class TreeIndexTestUtils {
+ private static final Logger LOGGER = Logger.getLogger(TreeIndexTestUtils.class.getName());
+
+ protected abstract CheckTuple createCheckTuple(int numfields, int numKeyFields);
+
+ protected abstract ISearchPredicate createNullSearchPredicate();
+
+ public abstract void checkExpectedResults(ITreeIndexCursor cursor, Collection checkTuples,
+ ISerializerDeserializer[] fieldSerdes, int keyFieldCount) throws Exception;
+
+ protected abstract CheckTuple createIntCheckTuple(int[] fieldValues, int numKeyFields);
+
+ protected abstract void setIntKeyFields(int[] fieldValues, int numKeyFields, int maxValue, Random rnd);
+
+ protected abstract boolean insertTuple(ITreeIndexTestContext ctx) throws Exception;
+
+ protected abstract Collection createCheckTuplesCollection();
+
+ @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());
+ }
+
+ @SuppressWarnings("unchecked")
+ public CheckTuple createCheckTupleFromTuple(ITupleReference tuple, ISerializerDeserializer[] fieldSerdes,
+ int numKeys) throws HyracksDataException {
+ CheckTuple checkTuple = createCheckTuple(fieldSerdes.length, numKeys);
+ int fieldCount = Math.min(fieldSerdes.length, tuple.getFieldCount());
+ for (int i = 0; i < fieldCount; 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 void checkScan(ITreeIndexTestContext ctx) throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Testing Scan.");
+ }
+ ITreeIndexCursor scanCursor = ctx.getIndexAccessor().createSearchCursor();
+ ISearchPredicate nullPred = createNullSearchPredicate();
+ ctx.getIndexAccessor().search(scanCursor, nullPred);
+ checkExpectedResults(scanCursor, ctx.getCheckTuples(), ctx.getFieldSerdes(), ctx.getKeyFieldCount());
+ }
+
+ public void checkDiskOrderScan(ITreeIndexTestContext ctx) throws Exception {
+ try {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Testing Disk-Order Scan.");
+ }
+ ITreeIndexCursor diskOrderCursor = ctx.getIndexAccessor().createDiskOrderScanCursor();
+ ctx.getIndexAccessor().diskOrderScan(diskOrderCursor);
+ int actualCount = 0;
+ try {
+ while (diskOrderCursor.hasNext()) {
+ diskOrderCursor.next();
+ ITupleReference tuple = diskOrderCursor.getTuple();
+ CheckTuple checkTuple = createCheckTupleFromTuple(tuple, ctx.getFieldSerdes(),
+ ctx.getKeyFieldCount());
+ if (!ctx.getCheckTuples().contains(checkTuple)) {
+ fail("Disk-order scan returned unexpected answer: " + checkTuple.toString());
+ }
+ actualCount++;
+ }
+ if (actualCount < ctx.getCheckTuples().size()) {
+ fail("Disk-order scan returned fewer answers than expected.\nExpected: "
+ + ctx.getCheckTuples().size() + "\nActual : " + actualCount);
+ }
+ if (actualCount > ctx.getCheckTuples().size()) {
+ fail("Disk-order scan returned more answers than expected.\nExpected: "
+ + ctx.getCheckTuples().size() + "\nActual : " + actualCount);
+ }
+ } finally {
+ diskOrderCursor.close();
+ }
+ } catch (UnsupportedOperationException e) {
+ // Ignore exception because some indexes, e.g. the LSMTrees, don't
+ // support disk-order scan.
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("Ignoring disk-order scan since it's not supported.");
+ }
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ public void insertIntTuples(ITreeIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
+ int fieldCount = ctx.getFieldCount();
+ int numKeyFields = ctx.getKeyFieldCount();
+ int[] fieldValues = new int[ctx.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.
+ setIntKeyFields(fieldValues, numKeyFields, maxValue, rnd);
+ // Set values.
+ for (int j = numKeyFields; j < fieldCount; j++) {
+ fieldValues[j] = j;
+ }
+ TupleUtils.createIntegerTuple(ctx.getTupleBuilder(), ctx.getTuple(), fieldValues);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if ((i + 1) % (numTuples / Math.min(10, numTuples)) == 0) {
+ LOGGER.info("Inserting Tuple " + (i + 1) + "/" + numTuples);
+ }
+ }
+ boolean succeeded = insertTuple(ctx);
+ if (succeeded) {
+ ctx.insertCheckTuple(createIntCheckTuple(fieldValues, ctx.getKeyFieldCount()), ctx.getCheckTuples());
+ }
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ public void bulkLoadIntTuples(ITreeIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
+ int fieldCount = ctx.getFieldCount();
+ int numKeyFields = ctx.getKeyFieldCount();
+ int[] fieldValues = new int[ctx.getFieldCount()];
+ int maxValue = (int) Math.ceil(Math.pow(numTuples, 1.0 / (double) numKeyFields));
+ Collection<CheckTuple> tmpCheckTuples = createCheckTuplesCollection();
+ for (int i = 0; i < numTuples; i++) {
+ // Set keys.
+ setIntKeyFields(fieldValues, numKeyFields, maxValue, rnd);
+ // Set values.
+ for (int j = numKeyFields; j < fieldCount; j++) {
+ fieldValues[j] = j;
+ }
+
+ // Set expected values. (We also use these as the pre-sorted stream
+ // for ordered indexes bulk loading).
+ ctx.insertCheckTuple(createIntCheckTuple(fieldValues, ctx.getKeyFieldCount()), tmpCheckTuples);
+ }
+ bulkLoadCheckTuples(ctx, tmpCheckTuples);
+
+ // Add tmpCheckTuples to ctx check tuples for comparing searches.
+ for (CheckTuple checkTuple : tmpCheckTuples) {
+ ctx.insertCheckTuple(checkTuple, ctx.getCheckTuples());
+ }
+ }
+
+ public static void bulkLoadCheckTuples(ITreeIndexTestContext ctx, Collection<CheckTuple> checkTuples)
+ throws HyracksDataException, TreeIndexException {
+ int fieldCount = ctx.getFieldCount();
+ int numTuples = checkTuples.size();
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ // Perform bulk load.
+ IIndexBulkLoadContext bulkLoadCtx = ctx.getIndex().beginBulkLoad(0.7f);
+ int c = 1;
+ for (CheckTuple checkTuple : checkTuples) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if (c % (numTuples / 10) == 0) {
+ LOGGER.info("Bulk Loading Tuple " + c + "/" + numTuples);
+ }
+ }
+ createTupleFromCheckTuple(checkTuple, tupleBuilder, tuple, ctx.getFieldSerdes());
+ ctx.getIndex().bulkLoadAddTuple(tuple, bulkLoadCtx);
+ c++;
+ }
+ ctx.getIndex().endBulkLoad(bulkLoadCtx);
+ }
+
+ @SuppressWarnings("unchecked")
+ public void deleteTuples(ITreeIndexTestContext ctx, int numTuples, Random rnd) throws Exception {
+ ArrayTupleBuilder deleteTupleBuilder = new ArrayTupleBuilder(ctx.getKeyFieldCount());
+ ArrayTupleReference deleteTuple = new ArrayTupleReference();
+ int numCheckTuples = ctx.getCheckTuples().size();
+ // Copy CheckTuple references into array, so we can randomly pick from
+ // there.
+ CheckTuple[] checkTuples = new CheckTuple[numCheckTuples];
+ int idx = 0;
+ Iterator<CheckTuple> iter = ctx.getCheckTuples().iterator();
+ while (iter.hasNext()) {
+ CheckTuple checkTuple = iter.next();
+ checkTuples[idx++] = checkTuple;
+ }
+
+ for (int i = 0; i < numTuples && numCheckTuples > 0; i++) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if ((i + 1) % (numTuples / Math.min(10, numTuples)) == 0) {
+ LOGGER.info("Deleting Tuple " + (i + 1) + "/" + numTuples);
+ }
+ }
+ int checkTupleIdx = Math.abs(rnd.nextInt() % numCheckTuples);
+ CheckTuple checkTuple = checkTuples[checkTupleIdx];
+ createTupleFromCheckTuple(checkTuple, deleteTupleBuilder, deleteTuple, ctx.getFieldSerdes());
+ ctx.getIndexAccessor().delete(deleteTuple);
+
+ // Remove check tuple from expected results.
+ ctx.getCheckTuples().remove(checkTuple);
+
+ // Swap with last "valid" CheckTuple.
+ CheckTuple tmp = checkTuples[numCheckTuples - 1];
+ checkTuples[numCheckTuples - 1] = checkTuple;
+ checkTuples[checkTupleIdx] = tmp;
+ numCheckTuples--;
+ }
+ }
+
+}