Merged fullstack_staging branch into trunk
git-svn-id: https://hyracks.googlecode.com/svn/trunk@2372 123451ca-8445-de46-9d55-352943316053
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/pom.xml b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/pom.xml
new file mode 100644
index 0000000..fc22c77
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/pom.xml
@@ -0,0 +1,50 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-btree-test</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <name>hyracks-storage-am-btree-test</name>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-tests</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ </parent>
+
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-compiler-plugin</artifactId>
+ <version>2.0.2</version>
+ <configuration>
+ <source>1.6</source>
+ <target>1.6</target>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+ <dependencies>
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <version>4.8.1</version>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-btree</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-test-support</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
+ </dependencies>
+</project>
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeBulkLoadTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeBulkLoadTest.java
new file mode 100644
index 0000000..11c47c7
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeBulkLoadTest.java
@@ -0,0 +1,61 @@
+/*
+ * 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 java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexBulkLoadTest;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+
+@SuppressWarnings("rawtypes")
+public class BTreeBulkLoadTest extends OrderedIndexBulkLoadTest {
+
+ public BTreeBulkLoadTest() {
+ super(BTreeTestHarness.LEAF_FRAMES_TO_TEST, 1);
+ }
+
+ private final BTreeTestHarness harness = new BTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+ BTreeLeafFrameType leafType) throws Exception {
+ return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+ leafType);
+ }
+
+ @Override
+ protected Random getRandom() {
+ return harness.getRandom();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java b/fullstack/hyracks/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..0205540
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeDeleteTest.java
@@ -0,0 +1,61 @@
+/*
+ * 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 java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexDeleteTest;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+
+@SuppressWarnings("rawtypes")
+public class BTreeDeleteTest extends OrderedIndexDeleteTest {
+
+ public BTreeDeleteTest() {
+ super(BTreeTestHarness.LEAF_FRAMES_TO_TEST);
+ }
+
+ private final BTreeTestHarness harness = new BTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+ BTreeLeafFrameType leafType) throws Exception {
+ return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+ leafType);
+ }
+
+ @Override
+ protected Random getRandom() {
+ return harness.getRandom();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeExamplesTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeExamplesTest.java
new file mode 100644
index 0000000..f4f8b12
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeExamplesTest.java
@@ -0,0 +1,52 @@
+/*
+ * 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.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexExamplesTest;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+
+public class BTreeExamplesTest extends OrderedIndexExamplesTest {
+ private final BTreeTestHarness harness = new BTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] cmpFactories) throws TreeIndexException {
+ return BTreeUtils.createBTree(harness.getBufferCache(), harness.getOpCallback(), typeTraits, cmpFactories,
+ BTreeLeafFrameType.REGULAR_NSM);
+ }
+
+ protected int getIndexFileId() {
+ return harness.getBTreeFileId();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java b/fullstack/hyracks/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..0b6cf4d
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeInsertTest.java
@@ -0,0 +1,71 @@
+/*
+ * 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 java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexInsertTest;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+
+/**
+ * Tests the BTree insert operation with strings and integer fields using
+ * various numbers of key and payload fields.
+ *
+ * Each tests first fills a BTree with randomly generated tuples. We compare the
+ * following operations against expected results: 1. Point searches for all
+ * tuples. 2. Ordered scan. 3. Disk-order scan. 4. Range search (and prefix
+ * search for composite keys).
+ *
+ */
+@SuppressWarnings("rawtypes")
+public class BTreeInsertTest extends OrderedIndexInsertTest {
+
+ public BTreeInsertTest() {
+ super(BTreeTestHarness.LEAF_FRAMES_TO_TEST);
+ }
+
+ private final BTreeTestHarness harness = new BTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+ BTreeLeafFrameType leafType) throws Exception {
+ return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+ leafType);
+ }
+
+ @Override
+ protected Random getRandom() {
+ return harness.getRandom();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeSearchCursorTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeSearchCursorTest.java
new file mode 100644
index 0000000..4003cf1
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeSearchCursorTest.java
@@ -0,0 +1,421 @@
+/*
+ * 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 java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Random;
+import java.util.TreeSet;
+import java.util.logging.Level;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.frames.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.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.ITreeIndexAccessor;
+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.NoOpOperationCallback;
+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 BTreeSearchCursorTest extends AbstractBTreeTest {
+ // Declare fields
+ int fieldCount = 2;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+
+ TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(typeTraits);
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
+
+ Random rnd = new Random(50);
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ super.setUp();
+ typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+ }
+
+ @Test
+ public void uniqueIndexTest() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("TESTING RANGE SEARCH CURSOR ON UNIQUE INDEX");
+ }
+
+ IBufferCache bufferCache = harness.getBufferCache();
+ int btreeFileId = harness.getBTreeFileId();
+
+ // declare keys
+ int keyFieldCount = 1;
+ IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+ ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
+ IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame) interiorFrameFactory.createFrame();
+
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+ BTree btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
+ btree.create(btreeFileId);
+ btree.open(btreeFileId);
+
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+
+ ITreeIndexAccessor indexAccessor = btree.createAccessor();
+
+ // generate keys
+ int numKeys = 50;
+ int maxKey = 1000;
+ TreeSet<Integer> uniqueKeys = new TreeSet<Integer>();
+ ArrayList<Integer> keys = new ArrayList<Integer>();
+ while (uniqueKeys.size() < numKeys) {
+ int key = rnd.nextInt() % maxKey;
+ uniqueKeys.add(key);
+ }
+ for (Integer i : uniqueKeys) {
+ keys.add(i);
+ }
+
+ // insert keys into btree
+ for (int i = 0; i < keys.size(); i++) {
+
+ TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+ tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+
+ try {
+ indexAccessor.insert(tuple);
+ } catch (BTreeException e) {
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ // btree.printTree(leafFrame, interiorFrame, recDescSers);
+
+ int minSearchKey = -100;
+ int maxSearchKey = 100;
+
+ // forward searches
+ performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, true, false);
+ performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, false, true, false);
+ performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, false, false);
+ performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, true, false);
+
+ btree.close();
+ }
+
+ @Test
+ public void nonUniqueIndexTest() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("TESTING RANGE SEARCH CURSOR ON NONUNIQUE INDEX");
+ }
+
+ IBufferCache bufferCache = harness.getBufferCache();
+ int btreeFileId = harness.getBTreeFileId();
+
+ // declare keys
+ int keyFieldCount = 2;
+ IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+ ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
+ IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame) interiorFrameFactory.createFrame();
+
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+ BTree btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
+ btree.create(btreeFileId);
+ btree.open(btreeFileId);
+
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+
+ ITreeIndexAccessor indexAccessor = btree.createAccessor();
+
+ // generate keys
+ int numKeys = 50;
+ int maxKey = 10;
+ ArrayList<Integer> keys = new ArrayList<Integer>();
+ for (int i = 0; i < numKeys; i++) {
+ int k = rnd.nextInt() % maxKey;
+ keys.add(k);
+ }
+ Collections.sort(keys);
+
+ // insert keys into btree
+ for (int i = 0; i < keys.size(); i++) {
+
+ TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+ tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+
+ try {
+ indexAccessor.insert(tuple);
+ } catch (BTreeException e) {
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ // btree.printTree(leafFrame, interiorFrame, recDescSers);
+
+ int minSearchKey = -100;
+ int maxSearchKey = 100;
+
+ // forward searches
+ performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, true, false);
+ performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, false, true, false);
+ performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, false, false);
+ performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, true, false);
+
+ btree.close();
+ }
+
+ @Test
+ public void nonUniqueFieldPrefixIndexTest() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("TESTING RANGE SEARCH CURSOR ON NONUNIQUE FIELD-PREFIX COMPRESSED INDEX");
+ }
+
+ IBufferCache bufferCache = harness.getBufferCache();
+ int btreeFileId = harness.getBTreeFileId();
+
+ // declare keys
+ int keyFieldCount = 2;
+ IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+ ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
+ IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame) interiorFrameFactory.createFrame();
+
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+ BTree btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
+ btree.create(btreeFileId);
+ btree.open(btreeFileId);
+
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+
+ ITreeIndexAccessor indexAccessor = btree.createAccessor();
+
+ // generate keys
+ int numKeys = 50;
+ int maxKey = 10;
+ ArrayList<Integer> keys = new ArrayList<Integer>();
+ for (int i = 0; i < numKeys; i++) {
+ int k = rnd.nextInt() % maxKey;
+ keys.add(k);
+ }
+ Collections.sort(keys);
+
+ // insert keys into btree
+ for (int i = 0; i < keys.size(); i++) {
+
+ TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+ tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+
+ try {
+ indexAccessor.insert(tuple);
+ } catch (BTreeException e) {
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ // btree.printTree(leafFrame, interiorFrame, recDescSers);
+
+ int minSearchKey = -100;
+ int maxSearchKey = 100;
+
+ // forward searches
+ performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, true, false);
+ performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, false, true, false);
+ performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, false, false);
+ performSearches(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey, true, true, false);
+
+ btree.close();
+ }
+
+ public RangePredicate createRangePredicate(int lk, int hk, boolean lowKeyInclusive,
+ boolean highKeyInclusive) throws HyracksDataException {
+
+ // create tuplereferences for search keys
+ ITupleReference lowKey = TupleUtils.createIntegerTuple(lk);
+ ITupleReference highKey = TupleUtils.createIntegerTuple(hk);
+
+ IBinaryComparator[] searchCmps = new IBinaryComparator[1];
+ searchCmps[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
+ MultiComparator searchCmp = new MultiComparator(searchCmps);
+
+ RangePredicate rangePred = new RangePredicate(lowKey, highKey, lowKeyInclusive, highKeyInclusive,
+ searchCmp, searchCmp);
+ return rangePred;
+ }
+
+ public void getExpectedResults(ArrayList<Integer> expectedResults, ArrayList<Integer> keys, int lk, int hk,
+ boolean lowKeyInclusive, boolean highKeyInclusive) {
+
+ // special cases
+ if (lk == hk && (!lowKeyInclusive || !highKeyInclusive))
+ return;
+ if (lk > hk)
+ return;
+
+ for (int i = 0; i < keys.size(); i++) {
+ if ((lk == keys.get(i) && lowKeyInclusive) || (hk == keys.get(i) && highKeyInclusive)) {
+ expectedResults.add(keys.get(i));
+ continue;
+ }
+
+ if (lk < keys.get(i) && hk > keys.get(i)) {
+ expectedResults.add(keys.get(i));
+ continue;
+ }
+ }
+ }
+
+ public boolean performSearches(ArrayList<Integer> keys, BTree btree, IBTreeLeafFrame leafFrame,
+ IBTreeInteriorFrame interiorFrame, int minKey, int maxKey, boolean lowKeyInclusive,
+ boolean highKeyInclusive, boolean printExpectedResults) throws Exception {
+
+ ArrayList<Integer> results = new ArrayList<Integer>();
+ ArrayList<Integer> expectedResults = new ArrayList<Integer>();
+
+ for (int i = minKey; i < maxKey; i++) {
+ for (int j = minKey; j < maxKey; j++) {
+
+ results.clear();
+ expectedResults.clear();
+
+ int lowKey = i;
+ int highKey = j;
+
+ ITreeIndexCursor rangeCursor = new BTreeRangeSearchCursor(leafFrame, false);
+ RangePredicate rangePred = createRangePredicate(lowKey, highKey, lowKeyInclusive,
+ highKeyInclusive);
+ ITreeIndexAccessor indexAccessor = btree.createAccessor();
+ indexAccessor.search(rangeCursor, rangePred);
+
+ try {
+ while (rangeCursor.hasNext()) {
+ rangeCursor.next();
+ ITupleReference frameTuple = rangeCursor.getTuple();
+ ByteArrayInputStream inStream = new ByteArrayInputStream(frameTuple.getFieldData(0),
+ frameTuple.getFieldStart(0), frameTuple.getFieldLength(0));
+ DataInput dataIn = new DataInputStream(inStream);
+ Integer res = IntegerSerializerDeserializer.INSTANCE.deserialize(dataIn);
+ results.add(res);
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ rangeCursor.close();
+ }
+
+ getExpectedResults(expectedResults, keys, lowKey, highKey, lowKeyInclusive, highKeyInclusive);
+
+ if (printExpectedResults) {
+ if (expectedResults.size() > 0) {
+ char l, u;
+
+ if (lowKeyInclusive)
+ l = '[';
+ else
+ l = '(';
+
+ if (highKeyInclusive)
+ u = ']';
+ else
+ u = ')';
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("RANGE: " + l + " " + lowKey + " , " + highKey + " " + u);
+ }
+ StringBuilder strBuilder = new StringBuilder();
+ for (Integer r : expectedResults) {
+ strBuilder.append(r + " ");
+ }
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(strBuilder.toString());
+ }
+ }
+ }
+
+ if (results.size() == expectedResults.size()) {
+ for (int k = 0; k < results.size(); k++) {
+ if (!results.get(k).equals(expectedResults.get(k))) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("DIFFERENT RESULTS AT: i=" + i + " j=" + j + " k=" + k);
+ LOGGER.info(results.get(k) + " " + expectedResults.get(k));
+ }
+ return false;
+ }
+ }
+ } else {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("UNEQUAL NUMBER OF RESULTS AT: i=" + i + " j=" + j);
+ LOGGER.info("RESULTS: " + results.size());
+ LOGGER.info("EXPECTED RESULTS: " + expectedResults.size());
+ }
+ return false;
+ }
+ }
+ }
+
+ return true;
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
new file mode 100644
index 0000000..c33b4e9
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
@@ -0,0 +1,163 @@
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import java.io.DataOutput;
+import java.io.File;
+import java.nio.ByteBuffer;
+import java.util.Random;
+import java.util.logging.Level;
+
+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.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+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.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.frames.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.util.AbstractBTreeTest;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+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.api.TreeIndexException;
+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.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexBufferCacheWarmup;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStats;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexStatsGatherer;
+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;
+
+@SuppressWarnings("rawtypes")
+public class BTreeStatsTest extends AbstractBTreeTest {
+ private static final int PAGE_SIZE = 4096;
+ private static final int NUM_PAGES = 1000;
+ private static final int MAX_OPEN_FILES = 10;
+ private static final int HYRACKS_FRAME_SIZE = 128;
+ private IHyracksTaskContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+ @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(harness.getFileName()));
+ bufferCache.createFile(file);
+ int fileId = fmp.lookupFileId(file);
+ bufferCache.openFile(fileId);
+
+ // declare fields
+ int fieldCount = 2;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+
+ // declare keys
+ int keyFieldCount = 1;
+ IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(typeTraits);
+ ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+ ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
+ IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame) interiorFrameFactory.createFrame();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
+
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+ BTree btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
+ btree.create(fileId);
+ btree.open(fileId);
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ long start = System.currentTimeMillis();
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("INSERTING INTO TREE");
+ }
+
+ ByteBuffer frame = ctx.allocateFrame();
+ FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+ DataOutput dos = tb.getDataOutput();
+
+ ISerializerDeserializer[] recDescSers = { IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE };
+ RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
+ IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
+ accessor.reset(frame);
+ FrameTupleReference tuple = new FrameTupleReference();
+
+ ITreeIndexAccessor indexAccessor = btree.createAccessor();
+ // 10000
+ for (int i = 0; i < 100000; i++) {
+
+ int f0 = rnd.nextInt() % 100000;
+ int f1 = 5;
+
+ tb.reset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(f0, dos);
+ tb.addFieldEndOffset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(f1, dos);
+ tb.addFieldEndOffset();
+
+ appender.reset(frame, true);
+ appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+ tuple.reset(accessor, 0);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if (i % 10000 == 0) {
+ long end = System.currentTimeMillis();
+ LOGGER.info("INSERTING " + i + " : " + f0 + " " + f1 + " " + (end - start));
+ }
+ }
+
+ try {
+ indexAccessor.insert(tuple);
+ } catch (TreeIndexException e) {
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ TreeIndexStatsGatherer statsGatherer = new TreeIndexStatsGatherer(bufferCache, freePageManager, fileId,
+ btree.getRootPageId());
+ TreeIndexStats stats = statsGatherer.gatherStats(leafFrame, interiorFrame, metaFrame);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("\n" + stats.toString());
+ }
+
+ TreeIndexBufferCacheWarmup bufferCacheWarmup = new TreeIndexBufferCacheWarmup(bufferCache, freePageManager,
+ fileId);
+ bufferCacheWarmup.warmup(leafFrame, metaFrame, new int[] { 1, 2 }, new int[] { 2, 5 });
+
+ btree.close();
+ bufferCache.closeFile(fileId);
+ bufferCache.close();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateSearchTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateSearchTest.java
new file mode 100644
index 0000000..2b03a6a
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateSearchTest.java
@@ -0,0 +1,154 @@
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+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.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.ITreeIndexAccessor;
+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.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+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.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+@SuppressWarnings("rawtypes")
+public class BTreeUpdateSearchTest extends AbstractBTreeTest {
+
+ // Update scan test on fixed-length tuples.
+ @Test
+ public void test01() throws Exception {
+ IBufferCache bufferCache = harness.getBufferCache();
+ int btreeFileId = harness.getBTreeFileId();
+
+ // declare fields
+ int fieldCount = 2;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+
+ // declare keys
+ int keyFieldCount = 1;
+ IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ ISerializerDeserializer[] recDescSers = { IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE };
+
+ TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(typeTraits);
+ ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+ ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
+
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+ BTree btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, fieldCount, cmpFactories, freePageManager, interiorFrameFactory, leafFrameFactory);
+ btree.create(btreeFileId);
+ btree.open(btreeFileId);
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ long start = System.currentTimeMillis();
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("INSERTING INTO TREE");
+ }
+
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference insertTuple = new ArrayTupleReference();
+ ITreeIndexAccessor indexAccessor = btree.createAccessor();
+
+ int numInserts = 10000;
+ for (int i = 0; i < numInserts; i++) {
+ int f0 = rnd.nextInt() % 10000;
+ int f1 = 5;
+ TupleUtils.createIntegerTuple(tb, insertTuple, f0, f1);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if (i % 10000 == 0) {
+ long end = System.currentTimeMillis();
+ LOGGER.info("INSERTING " + i + " : " + f0 + " " + f1 + " " + (end - start));
+ }
+ }
+
+ try {
+ indexAccessor.insert(insertTuple);
+ } catch (TreeIndexException e) {
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+ long end = System.currentTimeMillis();
+ long duration = end - start;
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("DURATION: " + duration);
+ }
+
+ // Update scan.
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("UPDATE SCAN:");
+ }
+ // Set the cursor to X latch nodes.
+ ITreeIndexCursor updateScanCursor = new BTreeRangeSearchCursor(leafFrame, true);
+ RangePredicate nullPred = new RangePredicate(null, null, true, true, null, null);
+ indexAccessor.search(updateScanCursor, nullPred);
+ try {
+ while (updateScanCursor.hasNext()) {
+ updateScanCursor.next();
+ ITupleReference tuple = updateScanCursor.getTuple();
+ // Change the value field.
+ IntegerSerializerDeserializer.putInt(10, tuple.getFieldData(1), tuple.getFieldStart(1));
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ updateScanCursor.close();
+ }
+
+ // Ordered scan to verify the values.
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("ORDERED SCAN:");
+ }
+ // Set the cursor to X latch nodes.
+ ITreeIndexCursor scanCursor = new BTreeRangeSearchCursor(leafFrame, true);
+ indexAccessor.search(scanCursor, nullPred);
+ try {
+ while (scanCursor.hasNext()) {
+ scanCursor.next();
+ ITupleReference tuple = scanCursor.getTuple();
+ String rec = TupleUtils.printTuple(tuple, recDescSers);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(rec);
+ }
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ scanCursor.close();
+ }
+ btree.close();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateTest.java
new file mode 100644
index 0000000..c3b56d5
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpdateTest.java
@@ -0,0 +1,61 @@
+/*
+ * 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 java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexUpdateTest;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+
+@SuppressWarnings("rawtypes")
+public class BTreeUpdateTest extends OrderedIndexUpdateTest {
+
+ public BTreeUpdateTest() {
+ super(BTreeTestHarness.LEAF_FRAMES_TO_TEST);
+ }
+
+ private final BTreeTestHarness harness = new BTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+ BTreeLeafFrameType leafType) throws Exception {
+ return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+ leafType);
+ }
+
+ @Override
+ protected Random getRandom() {
+ return harness.getRandom();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpsertTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpsertTest.java
new file mode 100644
index 0000000..6e14607
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeUpsertTest.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;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+
+/**
+ * Tests the BTree insert operation with strings and integer fields using
+ * various numbers of key and payload fields.
+ *
+ * Each tests first fills a BTree with randomly generated tuples. We compare the
+ * following operations against expected results: 1. Point searches for all
+ * tuples. 2. Ordered scan. 3. Disk-order scan. 4. Range search (and prefix
+ * search for composite keys).
+ *
+ */
+@SuppressWarnings("rawtypes")
+public class BTreeUpsertTest extends OrderedIndexUpsertTest {
+
+ public BTreeUpsertTest() {
+ super(BTreeTestHarness.LEAF_FRAMES_TO_TEST);
+ }
+
+ private final BTreeTestHarness harness = new BTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected OrderedIndexTestContext createTestContext(ISerializerDeserializer[] fieldSerdes, int numKeys,
+ BTreeLeafFrameType leafType) throws Exception {
+ return BTreeTestContext.create(harness.getBufferCache(), harness.getBTreeFileId(), fieldSerdes, numKeys,
+ leafType);
+ }
+
+ @Override
+ protected Random getRandom() {
+ return harness.getRandom();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/FieldPrefixNSMTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/FieldPrefixNSMTest.java
new file mode 100644
index 0000000..d61d16a
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/FieldPrefixNSMTest.java
@@ -0,0 +1,225 @@
+/*
+ * 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 java.io.DataOutput;
+import java.nio.ByteBuffer;
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Assert;
+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.ITypeTraits;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+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.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeFieldPrefixNSMLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.util.AbstractBTreeTest;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.util.TreeIndexUtils;
+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;
+
+@SuppressWarnings("rawtypes")
+public class FieldPrefixNSMTest extends AbstractBTreeTest {
+
+ private static final int PAGE_SIZE = 32768; // 32K
+ private static final int NUM_PAGES = 40;
+ private static final int MAX_OPEN_FILES = 10;
+ private static final int HYRACKS_FRAME_SIZE = 128;
+
+ public FieldPrefixNSMTest() {
+ super(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES, HYRACKS_FRAME_SIZE);
+ }
+
+ private ITupleReference createTuple(IHyracksTaskContext ctx, int f0, int f1, int f2, boolean print)
+ throws HyracksDataException {
+ if (print) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("CREATING: " + f0 + " " + f1 + " " + f2);
+ }
+ }
+
+ ByteBuffer buf = ctx.allocateFrame();
+ FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(3);
+ DataOutput dos = tb.getDataOutput();
+
+ ISerializerDeserializer[] recDescSers = { IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+ RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
+ IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
+ accessor.reset(buf);
+ FrameTupleReference tuple = new FrameTupleReference();
+
+ tb.reset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(f0, dos);
+ tb.addFieldEndOffset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(f1, dos);
+ tb.addFieldEndOffset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(f2, dos);
+ tb.addFieldEndOffset();
+
+ appender.reset(buf, true);
+ appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+ tuple.reset(accessor, 0);
+
+ return tuple;
+ }
+
+ @Test
+ public void test01() throws Exception {
+
+ // declare fields
+ int fieldCount = 3;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[2] = IntegerPointable.TYPE_TRAITS;
+
+ // declare keys
+ int keyFieldCount = 3;
+ IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
+ cmps[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
+ cmps[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
+ cmps[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY).createBinaryComparator();
+ MultiComparator cmp = new MultiComparator(cmps);
+
+ // just for printing
+ ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ IBufferCache bufferCache = harness.getBufferCache();
+ int btreeFileId = harness.getBTreeFileId();
+ IHyracksTaskContext ctx = harness.getHyracksTaskContext();
+ ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(btreeFileId, 0), false);
+ try {
+
+ ITreeIndexTupleWriter tupleWriter = new TypeAwareTupleWriter(typeTraits);
+ BTreeFieldPrefixNSMLeafFrame frame = new BTreeFieldPrefixNSMLeafFrame(tupleWriter);
+ frame.setPage(page);
+ frame.initBuffer((byte) 0);
+ frame.setMultiComparator(cmp);
+ frame.setPrefixTupleCount(0);
+
+ String before = new String();
+ String after = new String();
+
+ int compactFreq = 5;
+ int compressFreq = 5;
+ int smallMax = 10;
+ int numRecords = 1000;
+
+ int[][] savedFields = new int[numRecords][3];
+
+ // insert records with random calls to compact and compress
+ for (int i = 0; i < numRecords; i++) {
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if ((i + 1) % 100 == 0) {
+ LOGGER.info("INSERTING " + (i + 1) + " / " + numRecords);
+ }
+ }
+
+ int a = rnd.nextInt() % smallMax;
+ int b = rnd.nextInt() % smallMax;
+ int c = i;
+
+ ITupleReference tuple = createTuple(ctx, a, b, c, false);
+ try {
+ int targetTupleIndex = frame.findInsertTupleIndex(tuple);
+ frame.insert(tuple, targetTupleIndex);
+ } catch (BTreeException e) {
+ e.printStackTrace();
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+
+ savedFields[i][0] = a;
+ savedFields[i][1] = b;
+ savedFields[i][2] = c;
+
+ if (rnd.nextInt() % compactFreq == 0) {
+ before = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+ frame.compact();
+ after = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+ Assert.assertEquals(before, after);
+ }
+
+ if (rnd.nextInt() % compressFreq == 0) {
+ before = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+ frame.compress();
+ after = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+ Assert.assertEquals(before, after);
+ }
+
+ }
+
+ // delete records with random calls to compact and compress
+ for (int i = 0; i < numRecords; i++) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ if ((i + 1) % 100 == 0) {
+ LOGGER.info("DELETING " + (i + 1) + " / " + numRecords);
+ }
+ }
+
+ ITupleReference tuple = createTuple(ctx, savedFields[i][0], savedFields[i][1], savedFields[i][2], false);
+ try {
+ int tupleIndex = frame.findDeleteTupleIndex(tuple);
+ frame.delete(tuple, tupleIndex);
+ } catch (Exception e) {
+ }
+
+ if (rnd.nextInt() % compactFreq == 0) {
+ before = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+ frame.compact();
+ after = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+ Assert.assertEquals(before, after);
+ }
+
+ if (rnd.nextInt() % compressFreq == 0) {
+ before = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+ frame.compress();
+ after = TreeIndexUtils.printFrameTuples(frame, fieldSerdes);
+ Assert.assertEquals(before, after);
+ }
+ }
+
+ } finally {
+ bufferCache.unpin(page);
+ }
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/StorageManagerTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/StorageManagerTest.java
new file mode 100644
index 0000000..9ec64b5
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/StorageManagerTest.java
@@ -0,0 +1,259 @@
+/*
+ * 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 java.util.LinkedList;
+import java.util.List;
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+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.sync.LatchType;
+
+public class StorageManagerTest extends AbstractBTreeTest {
+ public class PinnedLatchedPage {
+ public final ICachedPage page;
+ public final LatchType latch;
+ public final int pageId;
+
+ public PinnedLatchedPage(ICachedPage page, int pageId, LatchType latch) {
+ this.page = page;
+ this.pageId = pageId;
+ this.latch = latch;
+ }
+ }
+
+ public enum FileAccessType {
+ FTA_READONLY, FTA_WRITEONLY, FTA_MIXED, FTA_UNLATCHED
+ }
+
+ public class FileAccessWorker implements Runnable {
+ private int workerId;
+ private final IBufferCache bufferCache;
+ private final int maxPages;
+ private final int fileId;
+ private final long thinkTime;
+ private final int maxLoopCount;
+ private final int maxPinnedPages;
+ private final int closeFileChance;
+ private final FileAccessType fta;
+ private int loopCount = 0;
+ private boolean fileIsOpen = false;
+ private Random rnd = new Random(50);
+ private List<PinnedLatchedPage> pinnedPages = new LinkedList<PinnedLatchedPage>();
+
+ public FileAccessWorker(int workerId, IBufferCache bufferCache, FileAccessType fta, int fileId, int maxPages,
+ int maxPinnedPages, int maxLoopCount, int closeFileChance, long thinkTime) {
+ this.bufferCache = bufferCache;
+ this.fileId = fileId;
+ this.maxPages = maxPages;
+ this.maxLoopCount = maxLoopCount;
+ this.maxPinnedPages = maxPinnedPages;
+ this.thinkTime = thinkTime;
+ this.closeFileChance = closeFileChance;
+ this.workerId = workerId;
+ this.fta = fta;
+ }
+
+ private void pinRandomPage() {
+ int pageId = Math.abs(rnd.nextInt() % maxPages);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(workerId + " PINNING PAGE: " + pageId);
+ }
+
+ try {
+ ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ LatchType latch = null;
+
+ switch (fta) {
+
+ case FTA_UNLATCHED: {
+ latch = null;
+ }
+ break;
+
+ case FTA_READONLY: {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(workerId + " S LATCHING: " + pageId);
+ }
+ page.acquireReadLatch();
+ latch = LatchType.LATCH_S;
+ }
+ break;
+
+ case FTA_WRITEONLY: {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(workerId + " X LATCHING: " + pageId);
+ }
+ page.acquireWriteLatch();
+ latch = LatchType.LATCH_X;
+ }
+ break;
+
+ case FTA_MIXED: {
+ if (rnd.nextInt() % 2 == 0) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(workerId + " S LATCHING: " + pageId);
+ }
+ page.acquireReadLatch();
+ latch = LatchType.LATCH_S;
+ } else {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(workerId + " X LATCHING: " + pageId);
+ }
+ page.acquireWriteLatch();
+ latch = LatchType.LATCH_X;
+ }
+ }
+ break;
+
+ }
+
+ PinnedLatchedPage plPage = new PinnedLatchedPage(page, pageId, latch);
+ pinnedPages.add(plPage);
+ } catch (HyracksDataException e) {
+ e.printStackTrace();
+ }
+ }
+
+ private void unpinRandomPage() {
+ int index = Math.abs(rnd.nextInt() % pinnedPages.size());
+ try {
+ PinnedLatchedPage plPage = pinnedPages.get(index);
+
+ if (plPage.latch != null) {
+ if (plPage.latch == LatchType.LATCH_S) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(workerId + " S UNLATCHING: " + plPage.pageId);
+ }
+ plPage.page.releaseReadLatch();
+ } else {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(workerId + " X UNLATCHING: " + plPage.pageId);
+ }
+ plPage.page.releaseWriteLatch();
+ }
+ }
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(workerId + " UNPINNING PAGE: " + plPage.pageId);
+ }
+
+ bufferCache.unpin(plPage.page);
+ pinnedPages.remove(index);
+ } catch (HyracksDataException e) {
+ e.printStackTrace();
+ }
+ }
+
+ private void openFile() {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(workerId + " OPENING FILE: " + fileId);
+ }
+ try {
+ bufferCache.openFile(fileId);
+ fileIsOpen = true;
+ } catch (HyracksDataException e) {
+ e.printStackTrace();
+ }
+ }
+
+ private void closeFile() {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(workerId + " CLOSING FILE: " + fileId);
+ }
+ try {
+ bufferCache.closeFile(fileId);
+ fileIsOpen = false;
+ } catch (HyracksDataException e) {
+ e.printStackTrace();
+ }
+ }
+
+ @Override
+ public void run() {
+
+ openFile();
+
+ while (loopCount < maxLoopCount) {
+ loopCount++;
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(workerId + " LOOP: " + loopCount + "/" + maxLoopCount);
+ }
+
+ if (fileIsOpen) {
+
+ // pin some pages
+ int pagesToPin = Math.abs(rnd.nextInt()) % (maxPinnedPages - pinnedPages.size());
+ for (int i = 0; i < pagesToPin; i++) {
+ pinRandomPage();
+ }
+
+ // do some thinking
+ try {
+ Thread.sleep(thinkTime);
+ } catch (InterruptedException e) {
+ e.printStackTrace();
+ }
+
+ // unpin some pages
+ if (!pinnedPages.isEmpty()) {
+ int pagesToUnpin = Math.abs(rnd.nextInt()) % pinnedPages.size();
+ for (int i = 0; i < pagesToUnpin; i++) {
+ unpinRandomPage();
+ }
+ }
+
+ // possibly close file
+ int closeFileCheck = Math.abs(rnd.nextInt()) % closeFileChance;
+ if (pinnedPages.isEmpty() || closeFileCheck == 0) {
+ int numPinnedPages = pinnedPages.size();
+ for (int i = 0; i < numPinnedPages; i++) {
+ unpinRandomPage();
+ }
+ closeFile();
+ }
+ } else {
+ openFile();
+ }
+ }
+
+ if (fileIsOpen) {
+ int numPinnedPages = pinnedPages.size();
+ for (int i = 0; i < numPinnedPages; i++) {
+ unpinRandomPage();
+ }
+ closeFile();
+ }
+ }
+ }
+
+ @Test
+ public void oneThreadOneFileTest() throws Exception {
+ Thread worker = new Thread(new FileAccessWorker(0,
+ harness.getBufferCache(), FileAccessType.FTA_UNLATCHED,
+ harness.getBTreeFileId(), 10, 10, 100, 10, 0));
+ worker.start();
+ worker.join();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeMultiThreadTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeMultiThreadTest.java
new file mode 100644
index 0000000..596fa31
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeMultiThreadTest.java
@@ -0,0 +1,91 @@
+/*
+ * 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.multithread;
+
+import java.util.ArrayList;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexMultiThreadTest;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeTestHarness;
+import edu.uci.ics.hyracks.storage.am.btree.util.BTreeUtils;
+import edu.uci.ics.hyracks.storage.am.common.ITreeIndexTestWorkerFactory;
+import edu.uci.ics.hyracks.storage.am.common.TestWorkloadConf;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector.TestOperation;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+
+public class BTreeMultiThreadTest extends OrderedIndexMultiThreadTest {
+
+ private BTreeTestHarness harness = new BTreeTestHarness();
+
+ private BTreeTestWorkerFactory workerFactory = new BTreeTestWorkerFactory();
+
+ @Override
+ protected void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @Override
+ protected void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] cmpFactories) throws TreeIndexException {
+ return BTreeUtils.createBTree(harness.getBufferCache(), harness.getOpCallback(), typeTraits, cmpFactories, BTreeLeafFrameType.REGULAR_NSM);
+ }
+
+ @Override
+ protected ITreeIndexTestWorkerFactory getWorkerFactory() {
+ return workerFactory;
+ }
+
+ @Override
+ protected ArrayList<TestWorkloadConf> getTestWorkloadConf() {
+ ArrayList<TestWorkloadConf> workloadConfs = new ArrayList<TestWorkloadConf>();
+
+ // Insert only workload.
+ TestOperation[] insertOnlyOps = new TestOperation[] { TestOperation.INSERT };
+ workloadConfs.add(new TestWorkloadConf(insertOnlyOps, getUniformOpProbs(insertOnlyOps)));
+
+ // Inserts mixed with point searches and scans.
+ TestOperation[] insertSearchOnlyOps = new TestOperation[] { TestOperation.INSERT, TestOperation.POINT_SEARCH, TestOperation.SCAN, TestOperation.DISKORDER_SCAN };
+ workloadConfs.add(new TestWorkloadConf(insertSearchOnlyOps, getUniformOpProbs(insertSearchOnlyOps)));
+
+ // Inserts, updates, deletes, and upserts.
+ TestOperation[] insertDeleteUpdateUpsertOps = new TestOperation[] { TestOperation.INSERT, TestOperation.DELETE, TestOperation.UPDATE, TestOperation.UPSERT };
+ workloadConfs.add(new TestWorkloadConf(insertDeleteUpdateUpsertOps, getUniformOpProbs(insertDeleteUpdateUpsertOps)));
+
+ // All operations mixed.
+ TestOperation[] allOps = new TestOperation[] { TestOperation.INSERT, TestOperation.DELETE, TestOperation.UPDATE, TestOperation.UPSERT, TestOperation.POINT_SEARCH, TestOperation.SCAN, TestOperation.DISKORDER_SCAN };
+ workloadConfs.add(new TestWorkloadConf(allOps, getUniformOpProbs(allOps)));
+
+ return workloadConfs;
+ }
+
+ @Override
+ protected int getFileId() {
+ return harness.getBTreeFileId();
+ }
+
+ @Override
+ protected String getIndexTypeName() {
+ return "BTree";
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeTestWorker.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeTestWorker.java
new file mode 100644
index 0000000..7d8de7d
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeTestWorker.java
@@ -0,0 +1,133 @@
+/*
+ * 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.multithread;
+
+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.storage.am.btree.exceptions.BTreeDuplicateKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNonExistentKeyException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNotUpdateableException;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.AbstractTreeIndexTestWorker;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector.TestOperation;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.datagen.DataGenThread;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public class BTreeTestWorker extends AbstractTreeIndexTestWorker {
+
+ private final BTree btree;
+ private final int numKeyFields;
+ private final ArrayTupleBuilder deleteTb;
+ private final ArrayTupleReference deleteTuple = new ArrayTupleReference();
+
+ public BTreeTestWorker(DataGenThread dataGen, TestOperationSelector opSelector, ITreeIndex index, int numBatches) {
+ super(dataGen, opSelector, index, numBatches);
+ btree = (BTree) index;
+ numKeyFields = btree.getComparatorFactories().length;
+ deleteTb = new ArrayTupleBuilder(numKeyFields);
+ }
+
+ @Override
+ public void performOp(ITupleReference tuple, TestOperation op) throws HyracksDataException, TreeIndexException {
+ BTree.BTreeAccessor accessor = (BTree.BTreeAccessor) indexAccessor;
+ ITreeIndexCursor searchCursor = accessor.createSearchCursor();
+ ITreeIndexCursor diskOrderScanCursor = accessor.createDiskOrderScanCursor();
+ MultiComparator cmp = accessor.getOpContext().cmp;
+ RangePredicate rangePred = new RangePredicate(tuple, tuple, true, true, cmp, cmp);
+
+ switch (op) {
+ case INSERT:
+ try {
+ accessor.insert(tuple);
+ } catch (BTreeDuplicateKeyException e) {
+ // Ignore duplicate keys, since we get random tuples.
+ }
+ break;
+
+ case DELETE:
+ // Create a tuple reference with only key fields.
+ deleteTb.reset();
+ for (int i = 0; i < numKeyFields; i++) {
+ deleteTb.addField(tuple.getFieldData(i), tuple.getFieldStart(i), tuple.getFieldLength(i));
+ }
+ deleteTuple.reset(deleteTb.getFieldEndOffsets(), deleteTb.getByteArray());
+ try {
+ accessor.delete(deleteTuple);
+ } catch (BTreeNonExistentKeyException e) {
+ // Ignore non-existant keys, since we get random tuples.
+ }
+ break;
+
+ case UPDATE:
+ try {
+ accessor.update(tuple);
+ } catch (BTreeNonExistentKeyException e) {
+ // Ignore non-existant keys, since we get random tuples.
+ } catch (BTreeNotUpdateableException e) {
+ // Ignore not updateable exception due to numKeys == numFields.
+ }
+ break;
+
+ case UPSERT:
+ accessor.upsert(tuple);
+ // Upsert should not throw. If it does, there's
+ // a bigger problem and the test should fail.
+ break;
+
+ case POINT_SEARCH:
+ searchCursor.reset();
+ rangePred.setLowKey(tuple, true);
+ rangePred.setHighKey(tuple, true);
+ accessor.search(searchCursor, rangePred);
+ consumeCursorTuples(searchCursor);
+ break;
+
+ case SCAN:
+ searchCursor.reset();
+ rangePred.setLowKey(null, true);
+ rangePred.setHighKey(null, true);
+ accessor.search(searchCursor, rangePred);
+ consumeCursorTuples(searchCursor);
+ break;
+
+ case DISKORDER_SCAN:
+ diskOrderScanCursor.reset();
+ accessor.diskOrderScan(diskOrderScanCursor);
+ consumeCursorTuples(diskOrderScanCursor);
+ break;
+
+ default:
+ throw new HyracksDataException("Op " + op.toString() + " not supported.");
+ }
+ }
+
+ private void consumeCursorTuples(ITreeIndexCursor cursor) throws HyracksDataException {
+ try {
+ while(cursor.hasNext()) {
+ cursor.next();
+ }
+ } finally {
+ cursor.close();
+ }
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeTestWorkerFactory.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeTestWorkerFactory.java
new file mode 100644
index 0000000..dc4d883
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/multithread/BTreeTestWorkerFactory.java
@@ -0,0 +1,30 @@
+/*
+ * 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.multithread;
+
+import edu.uci.ics.hyracks.storage.am.common.AbstractTreeIndexTestWorker;
+import edu.uci.ics.hyracks.storage.am.common.ITreeIndexTestWorkerFactory;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.datagen.DataGenThread;
+
+public class BTreeTestWorkerFactory implements ITreeIndexTestWorkerFactory {
+ @Override
+ public AbstractTreeIndexTestWorker create(DataGenThread dataGen, TestOperationSelector opSelector,
+ ITreeIndex index, int numBatches) {
+ return new BTreeTestWorker(dataGen, opSelector, index, numBatches);
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
new file mode 100644
index 0000000..f4eca1b
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/AbstractBTreeTest.java
@@ -0,0 +1,46 @@
+/*
+ * 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.logging.Logger;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+
+public abstract class AbstractBTreeTest {
+ protected final Logger LOGGER = Logger.getLogger(BTreeTestHarness.class.getName());
+ protected final BTreeTestHarness harness;
+
+ public AbstractBTreeTest() {
+ harness = new BTreeTestHarness();
+ }
+
+ public AbstractBTreeTest(int pageSize, int numPages, int maxOpenFiles, int hyracksFrameSize) {
+ harness = new BTreeTestHarness(pageSize, numPages, maxOpenFiles, hyracksFrameSize);
+ }
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestContext.java b/fullstack/hyracks/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..b820f93
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestContext.java
@@ -0,0 +1,57 @@
+/*
+ * 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 edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.dataflow.common.util.SerdeUtils;
+import edu.uci.ics.hyracks.storage.am.btree.OrderedIndexTestContext;
+import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+@SuppressWarnings("rawtypes")
+public class BTreeTestContext extends OrderedIndexTestContext {
+
+ public BTreeTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
+ super(fieldSerdes, treeIndex);
+ }
+
+ @Override
+ public int getKeyFieldCount() {
+ BTree btree = (BTree) treeIndex;
+ return btree.getComparatorFactories().length;
+ }
+
+ @Override
+ public IBinaryComparatorFactory[] getComparatorFactories() {
+ BTree btree = (BTree) treeIndex;
+ return btree.getComparatorFactories();
+ }
+
+ public static BTreeTestContext create(IBufferCache bufferCache, int btreeFileId, ISerializerDeserializer[] fieldSerdes, int numKeyFields, BTreeLeafFrameType leafType) throws Exception {
+ ITypeTraits[] typeTraits = SerdeUtils.serdesToTypeTraits(fieldSerdes);
+ IBinaryComparatorFactory[] cmpFactories = SerdeUtils.serdesToComparatorFactories(fieldSerdes, numKeyFields);
+ BTree btree = BTreeUtils.createBTree(bufferCache, NoOpOperationCallback.INSTANCE, typeTraits, cmpFactories, leafType);
+ btree.create(btreeFileId);
+ btree.open(btreeFileId);
+ BTreeTestContext testCtx = new BTreeTestContext(fieldSerdes, btree);
+ return testCtx;
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestHarness.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestHarness.java
new file mode 100644
index 0000000..1b450d8
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/util/BTreeTestHarness.java
@@ -0,0 +1,132 @@
+/*
+ * 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.io.File;
+import java.text.SimpleDateFormat;
+import java.util.Date;
+import java.util.Random;
+
+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.frames.BTreeLeafFrameType;
+import edu.uci.ics.hyracks.storage.am.common.api.IOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+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 BTreeTestHarness {
+ public static final BTreeLeafFrameType[] LEAF_FRAMES_TO_TEST = new BTreeLeafFrameType[] {
+ BTreeLeafFrameType.REGULAR_NSM, BTreeLeafFrameType.FIELD_PREFIX_COMPRESSED_NSM };
+
+ private static final long RANDOM_SEED = 50;
+ private static final int DEFAULT_PAGE_SIZE = 256;
+ private static final int DEFAULT_NUM_PAGES = 100;
+ private static final int DEFAULT_MAX_OPEN_FILES = 10;
+ private static final int DEFAULT_HYRACKS_FRAME_SIZE = 128;
+
+ protected final int pageSize;
+ protected final int numPages;
+ protected final int maxOpenFiles;
+ protected final int hyracksFrameSize;
+
+ protected IHyracksTaskContext ctx;
+ protected IBufferCache bufferCache;
+ protected int btreeFileId;
+
+ protected final Random rnd = new Random();
+ protected final SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
+ protected final String tmpDir = System.getProperty("java.io.tmpdir");
+ protected final String sep = System.getProperty("file.separator");
+ protected String fileName;
+
+ public BTreeTestHarness() {
+ this.pageSize = DEFAULT_PAGE_SIZE;
+ this.numPages = DEFAULT_NUM_PAGES;
+ this.maxOpenFiles = DEFAULT_MAX_OPEN_FILES;
+ this.hyracksFrameSize = DEFAULT_HYRACKS_FRAME_SIZE;
+ }
+
+ public BTreeTestHarness(int pageSize, int numPages, int maxOpenFiles, int hyracksFrameSize) {
+ this.pageSize = pageSize;
+ this.numPages = numPages;
+ this.maxOpenFiles = maxOpenFiles;
+ this.hyracksFrameSize = hyracksFrameSize;
+ }
+
+ public void setUp() throws HyracksDataException {
+ fileName = tmpDir + sep + simpleDateFormat.format(new Date());
+ ctx = TestUtils.create(getHyracksFrameSize());
+ TestStorageManagerComponentHolder.init(pageSize, numPages, maxOpenFiles);
+ bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ btreeFileId = fmp.lookupFileId(file);
+ bufferCache.openFile(btreeFileId);
+ rnd.setSeed(RANDOM_SEED);
+ }
+
+ public void tearDown() throws HyracksDataException {
+ bufferCache.closeFile(btreeFileId);
+ bufferCache.close();
+ File f = new File(fileName);
+ f.deleteOnExit();
+ }
+
+ public IHyracksTaskContext getHyracksTaskContext() {
+ return ctx;
+ }
+
+ public IBufferCache getBufferCache() {
+ return bufferCache;
+ }
+
+ public int getBTreeFileId() {
+ return btreeFileId;
+ }
+
+ public String getFileName() {
+ return fileName;
+ }
+
+ public Random getRandom() {
+ return rnd;
+ }
+
+ public int getPageSize() {
+ return pageSize;
+ }
+
+ public int getNumPages() {
+ return numPages;
+ }
+
+ public int getHyracksFrameSize() {
+ return hyracksFrameSize;
+ }
+
+ public int getMaxOpenFiles() {
+ return maxOpenFiles;
+ }
+
+ public IOperationCallback getOpCallback() {
+ return NoOpOperationCallback.INSTANCE;
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/pom.xml b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/pom.xml
new file mode 100644
index 0000000..5d66b81
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/pom.xml
@@ -0,0 +1,51 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-invertedindex-test</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <name>hyracks-storage-am-invertedindex-test</name>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-tests</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ </parent>
+
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-compiler-plugin</artifactId>
+ <version>2.0.2</version>
+ <configuration>
+ <source>1.6</source>
+ <target>1.6</target>
+ <encoding>UTF-8</encoding>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+ <dependencies>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-invertedindex</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-test-support</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>test</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/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/AbstractInvIndexSearchTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/AbstractInvIndexSearchTest.java
new file mode 100644
index 0000000..e086af6
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/AbstractInvIndexSearchTest.java
@@ -0,0 +1,193 @@
+/*
+ * 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.invertedindex;
+
+import java.io.File;
+import java.util.ArrayList;
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.data.std.primitive.UTF8StringPointable;
+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.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.IIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+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.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.invertedindex.api.IInvertedListBuilder;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.FixedSizeElementInvertedListBuilder;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.InvertedIndex;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.IBinaryTokenizer;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.ITokenFactory;
+import edu.uci.ics.hyracks.storage.am.invertedindex.util.InvertedIndexUtils;
+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 abstract class AbstractInvIndexSearchTest extends AbstractInvIndexTest {
+ protected final int PAGE_SIZE = 32768;
+ protected final int NUM_PAGES = 100;
+ protected final int MAX_OPEN_FILES = 10;
+ protected final int HYRACKS_FRAME_SIZE = 32768;
+ protected IHyracksTaskContext taskCtx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+ protected IBufferCache bufferCache;
+ protected IFileMapProvider fmp;
+
+ // --- BTREE ---
+
+ // create file refs
+ protected FileReference btreeFile = new FileReference(new File(btreeFileName));
+ protected int btreeFileId;
+
+ // declare token type traits
+ protected ITypeTraits[] tokenTypeTraits = new ITypeTraits[] { UTF8StringPointable.TYPE_TRAITS };
+ protected ITypeTraits[] btreeTypeTraits = InvertedIndexUtils.getBTreeTypeTraits(tokenTypeTraits);
+
+ // declare btree keys
+ protected int btreeKeyFieldCount = 1;
+ protected IBinaryComparatorFactory[] btreeCmpFactories = new IBinaryComparatorFactory[btreeKeyFieldCount];
+
+ // btree frame factories
+ protected TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(btreeTypeTraits);
+ protected ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+ protected ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+ protected ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+ // btree frames
+ protected ITreeIndexFrame leafFrame = leafFrameFactory.createFrame();
+ protected ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
+
+ protected IFreePageManager freePageManager;
+
+ protected BTree btree;
+
+ // --- INVERTED INDEX ---
+
+ protected FileReference invListsFile = new FileReference(new File(invListsFileName));
+ protected int invListsFileId;
+
+ protected int invListFields = 1;
+ protected ITypeTraits[] invListTypeTraits = new ITypeTraits[invListFields];
+
+ protected int invListKeys = 1;
+ protected IBinaryComparatorFactory[] invListCmpFactories = new IBinaryComparatorFactory[invListKeys];
+
+ protected InvertedIndex invIndex;
+
+ protected Random rnd = new Random();
+
+ protected ArrayTupleBuilder tb = new ArrayTupleBuilder(2);
+ protected ArrayTupleReference tuple = new ArrayTupleReference();
+
+ protected ISerializerDeserializer[] insertSerde = { UTF8StringSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE };
+ protected RecordDescriptor insertRecDesc = new RecordDescriptor(insertSerde);
+
+ protected ArrayList<ArrayList<Integer>> checkInvLists = new ArrayList<ArrayList<Integer>>();
+
+ protected int maxId = 1000000;
+ protected int[] scanCountArray = new int[maxId];
+ protected ArrayList<Integer> expectedResults = new ArrayList<Integer>();
+
+ protected ISerializerDeserializer[] querySerde = { UTF8StringSerializerDeserializer.INSTANCE };
+ protected RecordDescriptor queryRecDesc = new RecordDescriptor(querySerde);
+
+ protected ArrayTupleBuilder queryTb = new ArrayTupleBuilder(querySerde.length);
+ protected ArrayTupleReference queryTuple = new ArrayTupleReference();
+
+ protected ITokenFactory tokenFactory;
+ protected IBinaryTokenizer tokenizer;
+
+ protected IIndexCursor resultCursor;
+
+ protected abstract void setTokenizer();
+
+ /**
+ * Initialize members, generate data, and bulk load the inverted index.
+ */
+ @Before
+ public void start() throws Exception {
+ TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+ bufferCache = TestStorageManagerComponentHolder.getBufferCache(taskCtx);
+ fmp = TestStorageManagerComponentHolder.getFileMapProvider(taskCtx);
+
+ // --- BTREE ---
+
+ bufferCache.createFile(btreeFile);
+ btreeFileId = fmp.lookupFileId(btreeFile);
+ bufferCache.openFile(btreeFileId);
+
+ btreeCmpFactories[0] = PointableBinaryComparatorFactory.of(UTF8StringPointable.FACTORY);
+
+ freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+ btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, btreeTypeTraits.length, btreeCmpFactories,
+ freePageManager, interiorFrameFactory, leafFrameFactory);
+ btree.create(btreeFileId);
+ btree.open(btreeFileId);
+
+ // --- INVERTED INDEX ---
+
+ setTokenizer();
+
+ bufferCache.createFile(invListsFile);
+ invListsFileId = fmp.lookupFileId(invListsFile);
+ bufferCache.openFile(invListsFileId);
+
+ invListTypeTraits[0] = IntegerPointable.TYPE_TRAITS;
+ invListCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ IInvertedListBuilder invListBuilder = new FixedSizeElementInvertedListBuilder(invListTypeTraits);
+ invIndex = new InvertedIndex(bufferCache, btree, invListTypeTraits, invListCmpFactories, invListBuilder);
+ invIndex.open(invListsFileId);
+
+ rnd.setSeed(50);
+ }
+
+ @After
+ public void deinit() throws HyracksDataException {
+ AbstractInvIndexTest.tearDown();
+ btree.close();
+ invIndex.close();
+ bufferCache.closeFile(btreeFileId);
+ bufferCache.closeFile(invListsFileId);
+ bufferCache.close();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/AbstractInvIndexTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/AbstractInvIndexTest.java
new file mode 100644
index 0000000..cc8ab15
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/AbstractInvIndexTest.java
@@ -0,0 +1,43 @@
+/*
+ * 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.invertedindex;
+
+import java.io.File;
+import java.text.SimpleDateFormat;
+import java.util.Date;
+import java.util.logging.Logger;
+
+public abstract class AbstractInvIndexTest {
+
+ protected static final Logger LOGGER = Logger
+ .getLogger(AbstractInvIndexTest.class.getName());
+
+ protected final static SimpleDateFormat simpleDateFormat = new SimpleDateFormat(
+ "ddMMyy-hhmmssSS");
+ protected final static String tmpDir = System.getProperty("java.io.tmpdir");
+ protected final static String sep = System.getProperty("file.separator");
+ protected final static String baseFileName = tmpDir + sep
+ + simpleDateFormat.format(new Date());
+ protected final static String btreeFileName = baseFileName + "btree";
+ protected final static String invListsFileName = baseFileName + "invlists";
+
+ public static void tearDown() {
+ File btreeFile = new File(btreeFileName);
+ btreeFile.deleteOnExit();
+ File invListsFile = new File(invListsFileName);
+ invListsFile.deleteOnExit();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/BulkLoadTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/BulkLoadTest.java
new file mode 100644
index 0000000..9fdc1c4
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/BulkLoadTest.java
@@ -0,0 +1,294 @@
+/*
+ * 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.invertedindex;
+
+import java.io.DataOutput;
+import java.io.File;
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+
+import junit.framework.Assert;
+
+import org.junit.AfterClass;
+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.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.data.std.primitive.UTF8StringPointable;
+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.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.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.BTreeRangeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+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.impls.NoOpOperationCallback;
+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.am.invertedindex.api.IInvertedListBuilder;
+import edu.uci.ics.hyracks.storage.am.invertedindex.api.IInvertedListCursor;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.FixedSizeElementInvertedListBuilder;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.FixedSizeElementInvertedListCursor;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.InvertedIndex;
+import edu.uci.ics.hyracks.storage.am.invertedindex.util.InvertedIndexUtils;
+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 BulkLoadTest extends AbstractInvIndexTest {
+
+ private static final int PAGE_SIZE = 32768;
+ private static final int NUM_PAGES = 100;
+ private static final int MAX_OPEN_FILES = 10;
+ private static final int HYRACKS_FRAME_SIZE = 32768;
+ private IHyracksTaskContext stageletCtx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+ /**
+ * This test generates a list of <word-token, id> pairs which are pre-sorted
+ * on the token. Those pairs for the input to an inverted-index bulk load.
+ * The contents of the inverted lists are verified against the generated
+ * data.
+ */
+ @Test
+ public void singleFieldPayloadTest() throws Exception {
+
+ TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+ IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(stageletCtx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(stageletCtx);
+
+ // create file refs
+ FileReference btreeFile = new FileReference(new File(btreeFileName));
+ bufferCache.createFile(btreeFile);
+ int btreeFileId = fmp.lookupFileId(btreeFile);
+ bufferCache.openFile(btreeFileId);
+
+ FileReference invListsFile = new FileReference(new File(invListsFileName));
+ bufferCache.createFile(invListsFile);
+ int invListsFileId = fmp.lookupFileId(invListsFile);
+ bufferCache.openFile(invListsFileId);
+
+ // Declare token type traits, and compute BTree type traits.
+ ITypeTraits[] tokenTypeTraits = new ITypeTraits[] { UTF8StringPointable.TYPE_TRAITS };
+ ITypeTraits[] btreeTypeTraits = InvertedIndexUtils.getBTreeTypeTraits(tokenTypeTraits);
+
+ // declare btree keys
+ int keyFieldCount = 1;
+ IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] = PointableBinaryComparatorFactory.of(UTF8StringPointable.FACTORY);
+
+ TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(btreeTypeTraits);
+ ITreeIndexFrameFactory leafFrameFactory = new BTreeNSMLeafFrameFactory(tupleWriterFactory);
+ ITreeIndexFrameFactory interiorFrameFactory = new BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+ ITreeIndexFrame leafFrame = leafFrameFactory.createFrame();
+
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+ BTree btree = new BTree(bufferCache, NoOpOperationCallback.INSTANCE, btreeTypeTraits.length, cmpFactories,
+ freePageManager, interiorFrameFactory, leafFrameFactory);
+ btree.create(btreeFileId);
+ btree.open(btreeFileId);
+
+ int invListFields = 1;
+ ITypeTraits[] invListTypeTraits = new ITypeTraits[invListFields];
+ invListTypeTraits[0] = IntegerPointable.TYPE_TRAITS;
+
+ int invListKeys = 1;
+ IBinaryComparatorFactory[] invListCmpFactories = new IBinaryComparatorFactory[invListKeys];
+ invListCmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ IInvertedListBuilder invListBuilder = new FixedSizeElementInvertedListBuilder(invListTypeTraits);
+ InvertedIndex invIndex = new InvertedIndex(bufferCache, btree, invListTypeTraits, invListCmpFactories, invListBuilder);
+ invIndex.open(invListsFileId);
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ ByteBuffer frame = stageletCtx.allocateFrame();
+ FrameTupleAppender appender = new FrameTupleAppender(stageletCtx.getFrameSize());
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(2);
+ DataOutput dos = tb.getDataOutput();
+
+ ISerializerDeserializer[] insertSerde = { UTF8StringSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE };
+ RecordDescriptor insertRecDesc = new RecordDescriptor(insertSerde);
+ IFrameTupleAccessor accessor = new FrameTupleAccessor(stageletCtx.getFrameSize(), insertRecDesc);
+ accessor.reset(frame);
+ FrameTupleReference tuple = new FrameTupleReference();
+
+ List<String> tokens = new ArrayList<String>();
+ tokens.add("compilers");
+ tokens.add("computer");
+ tokens.add("databases");
+ tokens.add("fast");
+ tokens.add("hyracks");
+ tokens.add("major");
+ tokens.add("science");
+ tokens.add("systems");
+ tokens.add("university");
+
+ ArrayList<ArrayList<Integer>> checkListElements = new ArrayList<ArrayList<Integer>>();
+ for (int i = 0; i < tokens.size(); i++) {
+ checkListElements.add(new ArrayList<Integer>());
+ }
+
+ int maxId = 1000000;
+ int addProb = 0;
+ int addProbStep = 10;
+
+ IIndexBulkLoadContext ctx = invIndex.beginBulkLoad(BTree.DEFAULT_FILL_FACTOR);
+
+ for (int i = 0; i < tokens.size(); i++) {
+
+ addProb += addProbStep * (i + 1);
+ for (int j = 0; j < maxId; j++) {
+ if ((Math.abs(rnd.nextInt()) % addProb) == 0) {
+
+ tb.reset();
+ UTF8StringSerializerDeserializer.INSTANCE.serialize(tokens.get(i), dos);
+ tb.addFieldEndOffset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(j, dos);
+ tb.addFieldEndOffset();
+
+ checkListElements.get(i).add(j);
+
+ appender.reset(frame, true);
+ appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+ tuple.reset(accessor, 0);
+
+ try {
+ invIndex.bulkLoadAddTuple(tuple, ctx);
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+ }
+ }
+ invIndex.endBulkLoad(ctx);
+
+ // ------- START VERIFICATION -----------
+
+ ITreeIndexCursor btreeCursor = new BTreeRangeSearchCursor((IBTreeLeafFrame) leafFrame, false);
+ FrameTupleReference searchKey = new FrameTupleReference();
+ MultiComparator btreeCmp = MultiComparator.create(cmpFactories);
+ RangePredicate btreePred = new RangePredicate(searchKey, searchKey, true, true, btreeCmp, btreeCmp);
+
+ IInvertedListCursor invListCursor = new FixedSizeElementInvertedListCursor(bufferCache, invListsFileId,
+ invListTypeTraits);
+
+ ISerializerDeserializer[] tokenSerde = { UTF8StringSerializerDeserializer.INSTANCE };
+ RecordDescriptor tokenRecDesc = new RecordDescriptor(tokenSerde);
+ FrameTupleAppender tokenAppender = new FrameTupleAppender(stageletCtx.getFrameSize());
+ ArrayTupleBuilder tokenTupleBuilder = new ArrayTupleBuilder(1);
+ DataOutput tokenDos = tokenTupleBuilder.getDataOutput();
+ IFrameTupleAccessor tokenAccessor = new FrameTupleAccessor(stageletCtx.getFrameSize(), tokenRecDesc);
+ tokenAccessor.reset(frame);
+
+ ITreeIndexAccessor btreeAccessor = invIndex.getBTree().createAccessor();
+
+ // verify created inverted lists one-by-one
+ for (int i = 0; i < tokens.size(); i++) {
+
+ tokenTupleBuilder.reset();
+ UTF8StringSerializerDeserializer.INSTANCE.serialize(tokens.get(i), tokenDos);
+ tokenTupleBuilder.addFieldEndOffset();
+
+ tokenAppender.reset(frame, true);
+ tokenAppender.append(tokenTupleBuilder.getFieldEndOffsets(), tokenTupleBuilder.getByteArray(), 0,
+ tokenTupleBuilder.getSize());
+
+ searchKey.reset(tokenAccessor, 0);
+
+ invIndex.openCursor(btreeCursor, btreePred, btreeAccessor, invListCursor);
+
+ invListCursor.pinPagesSync();
+ int checkIndex = 0;
+ while (invListCursor.hasNext()) {
+ invListCursor.next();
+ ITupleReference invListTuple = invListCursor.getTuple();
+ int invListElement = IntegerSerializerDeserializer.getInt(invListTuple.getFieldData(0),
+ invListTuple.getFieldStart(0));
+ int checkInvListElement = checkListElements.get(i).get(checkIndex).intValue();
+ Assert.assertEquals(invListElement, checkInvListElement);
+ checkIndex++;
+ }
+ invListCursor.unpinPages();
+ Assert.assertEquals(checkIndex, checkListElements.get(i).size());
+ }
+
+ // check that non-existing tokens have an empty inverted list
+ List<String> nonExistingTokens = new ArrayList<String>();
+ nonExistingTokens.add("watermelon");
+ nonExistingTokens.add("avocado");
+ nonExistingTokens.add("lemon");
+
+ for (int i = 0; i < nonExistingTokens.size(); i++) {
+
+ tokenTupleBuilder.reset();
+ UTF8StringSerializerDeserializer.INSTANCE.serialize(nonExistingTokens.get(i), tokenDos);
+ tokenTupleBuilder.addFieldEndOffset();
+
+ tokenAppender.reset(frame, true);
+ tokenAppender.append(tokenTupleBuilder.getFieldEndOffsets(), tokenTupleBuilder.getByteArray(), 0,
+ tokenTupleBuilder.getSize());
+
+ searchKey.reset(tokenAccessor, 0);
+
+ invIndex.openCursor(btreeCursor, btreePred, btreeAccessor, invListCursor);
+
+ invListCursor.pinPagesSync();
+ Assert.assertEquals(invListCursor.hasNext(), false);
+ invListCursor.unpinPages();
+ }
+
+ btree.close();
+ bufferCache.closeFile(btreeFileId);
+ bufferCache.closeFile(invListsFileId);
+ bufferCache.close();
+ }
+
+ @AfterClass
+ public static void deinit() {
+ AbstractInvIndexTest.tearDown();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/FixedSizeFrameTupleTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/FixedSizeFrameTupleTest.java
new file mode 100644
index 0000000..9c7ec09
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/FixedSizeFrameTupleTest.java
@@ -0,0 +1,75 @@
+/*
+ * 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.invertedindex;
+
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Random;
+
+import junit.framework.Assert;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.FixedSizeFrameTupleAccessor;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.FixedSizeFrameTupleAppender;
+
+public class FixedSizeFrameTupleTest {
+
+ private static int FRAME_SIZE = 4096;
+
+ private Random rnd = new Random(50);
+
+ /**
+ * This test verifies the correct behavior of the FixedSizeFrameTuple class.
+ * Frames containing FixedSizeFrameTuple's require neither tuple slots nor
+ * field slots. The tests inserts generated data into a frame until the
+ * frame is full, and then verifies the frame's contents.
+ *
+ */
+ @Test
+ public void singleFieldTest() throws Exception {
+ ByteBuffer buffer = ByteBuffer.allocate(FRAME_SIZE);
+
+ ITypeTraits[] fields = new ITypeTraits[1];
+ fields[0] = IntegerPointable.TYPE_TRAITS;
+
+ FixedSizeFrameTupleAppender ftapp = new FixedSizeFrameTupleAppender(FRAME_SIZE, fields);
+ FixedSizeFrameTupleAccessor ftacc = new FixedSizeFrameTupleAccessor(FRAME_SIZE, fields);
+
+ boolean frameHasSpace = true;
+
+ ArrayList<Integer> check = new ArrayList<Integer>();
+
+ ftapp.reset(buffer, true);
+ while (frameHasSpace) {
+ int val = rnd.nextInt();
+ frameHasSpace = ftapp.append(val);
+ if (frameHasSpace) {
+ check.add(val);
+ ftapp.incrementTupleCount(1);
+ }
+ }
+
+ ftacc.reset(buffer);
+ for (int i = 0; i < ftacc.getTupleCount(); i++) {
+ int val = IntegerSerializerDeserializer.getInt(ftacc.getBuffer().array(), ftacc.getTupleStartOffset(i));
+ Assert.assertEquals(check.get(i).intValue(), val);
+ }
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/NGramTokenizerTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/NGramTokenizerTest.java
new file mode 100644
index 0000000..5f15a91
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/NGramTokenizerTest.java
@@ -0,0 +1,247 @@
+/**
+ * Copyright 2010-2011 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 at
+ *
+ * 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.
+ *
+ * Author: Alexander Behm <abehm (at) ics.uci.edu>
+ */
+
+package edu.uci.ics.hyracks.storage.am.invertedindex;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.io.DataOutput;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.AbstractUTF8Token;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.HashedUTF8NGramTokenFactory;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.IToken;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.NGramUTF8StringBinaryTokenizer;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.UTF8NGramTokenFactory;
+
+public class NGramTokenizerTest {
+
+ private char PRECHAR = '#';
+ private char POSTCHAR = '$';
+
+ private String str = "Jürgen S. Generic's Car";
+ private byte[] inputBuffer;
+
+ private int gramLength = 3;
+
+ private void getExpectedGrams(String s, int gramLength,
+ ArrayList<String> grams, boolean prePost) {
+
+ String tmp = s.toLowerCase();
+ if (prePost) {
+ StringBuilder preBuilder = new StringBuilder();
+ for (int i = 0; i < gramLength - 1; i++) {
+ preBuilder.append(PRECHAR);
+ }
+ String pre = preBuilder.toString();
+
+ StringBuilder postBuilder = new StringBuilder();
+ for (int i = 0; i < gramLength - 1; i++) {
+ postBuilder.append(POSTCHAR);
+ }
+ String post = postBuilder.toString();
+
+ tmp = pre + s.toLowerCase() + post;
+ }
+
+ for (int i = 0; i < tmp.length() - gramLength + 1; i++) {
+ String gram = tmp.substring(i, i + gramLength);
+ grams.add(gram);
+ }
+ }
+
+ @Before
+ public void init() throws Exception {
+ // serialize string into bytes
+ ByteArrayOutputStream baos = new ByteArrayOutputStream();
+ DataOutput dos = new DataOutputStream(baos);
+ dos.writeUTF(str);
+ inputBuffer = baos.toByteArray();
+ }
+
+ void runTestNGramTokenizerWithCountedHashedUTF8Tokens(boolean prePost)
+ throws IOException {
+ HashedUTF8NGramTokenFactory tokenFactory = new HashedUTF8NGramTokenFactory();
+ NGramUTF8StringBinaryTokenizer tokenizer = new NGramUTF8StringBinaryTokenizer(
+ gramLength, prePost, false, false, tokenFactory);
+ tokenizer.reset(inputBuffer, 0, inputBuffer.length);
+
+ ArrayList<String> expectedGrams = new ArrayList<String>();
+ getExpectedGrams(str, gramLength, expectedGrams, prePost);
+ ArrayList<Integer> expectedHashedGrams = new ArrayList<Integer>();
+ HashMap<String, Integer> gramCounts = new HashMap<String, Integer>();
+ for (String s : expectedGrams) {
+ Integer count = gramCounts.get(s);
+ if (count == null) {
+ count = 1;
+ gramCounts.put(s, count);
+ } else {
+ count++;
+ }
+
+ int hash = tokenHash(s, count);
+ expectedHashedGrams.add(hash);
+ }
+
+ int tokenCount = 0;
+
+ while (tokenizer.hasNext()) {
+ tokenizer.next();
+
+ // serialize hashed token
+ ByteArrayOutputStream tokenBaos = new ByteArrayOutputStream();
+ DataOutput tokenDos = new DataOutputStream(tokenBaos);
+
+ IToken token = tokenizer.getToken();
+ token.serializeToken(tokenDos);
+
+ // deserialize token
+ ByteArrayInputStream bais = new ByteArrayInputStream(
+ tokenBaos.toByteArray());
+ DataInput in = new DataInputStream(bais);
+
+ Integer hashedGram = in.readInt();
+
+ // System.out.println(hashedGram);
+
+ Assert.assertEquals(expectedHashedGrams.get(tokenCount), hashedGram);
+
+ tokenCount++;
+ }
+ // System.out.println("---------");
+ }
+
+ void runTestNGramTokenizerWithHashedUTF8Tokens(boolean prePost)
+ throws IOException {
+ HashedUTF8NGramTokenFactory tokenFactory = new HashedUTF8NGramTokenFactory();
+ NGramUTF8StringBinaryTokenizer tokenizer = new NGramUTF8StringBinaryTokenizer(
+ gramLength, prePost, true, false, tokenFactory);
+ tokenizer.reset(inputBuffer, 0, inputBuffer.length);
+
+ ArrayList<String> expectedGrams = new ArrayList<String>();
+ getExpectedGrams(str, gramLength, expectedGrams, prePost);
+ ArrayList<Integer> expectedHashedGrams = new ArrayList<Integer>();
+ for (String s : expectedGrams) {
+ int hash = tokenHash(s, 1);
+ expectedHashedGrams.add(hash);
+ }
+
+ int tokenCount = 0;
+
+ while (tokenizer.hasNext()) {
+ tokenizer.next();
+
+ // serialize hashed token
+ ByteArrayOutputStream tokenBaos = new ByteArrayOutputStream();
+ DataOutput tokenDos = new DataOutputStream(tokenBaos);
+
+ IToken token = tokenizer.getToken();
+ token.serializeToken(tokenDos);
+
+ // deserialize token
+ ByteArrayInputStream bais = new ByteArrayInputStream(
+ tokenBaos.toByteArray());
+ DataInput in = new DataInputStream(bais);
+
+ Integer hashedGram = in.readInt();
+
+ // System.out.println(hashedGram);
+
+ Assert.assertEquals(expectedHashedGrams.get(tokenCount), hashedGram);
+
+ tokenCount++;
+ }
+ // System.out.println("---------");
+ }
+
+ void runTestNGramTokenizerWithUTF8Tokens(boolean prePost)
+ throws IOException {
+ UTF8NGramTokenFactory tokenFactory = new UTF8NGramTokenFactory();
+ NGramUTF8StringBinaryTokenizer tokenizer = new NGramUTF8StringBinaryTokenizer(
+ gramLength, prePost, true, false, tokenFactory);
+ tokenizer.reset(inputBuffer, 0, inputBuffer.length);
+
+ ArrayList<String> expectedGrams = new ArrayList<String>();
+ getExpectedGrams(str, gramLength, expectedGrams, prePost);
+
+ int tokenCount = 0;
+
+ while (tokenizer.hasNext()) {
+ tokenizer.next();
+
+ // serialize hashed token
+ ByteArrayOutputStream tokenBaos = new ByteArrayOutputStream();
+ DataOutput tokenDos = new DataOutputStream(tokenBaos);
+
+ IToken token = tokenizer.getToken();
+ token.serializeToken(tokenDos);
+
+ // deserialize token
+ ByteArrayInputStream bais = new ByteArrayInputStream(
+ tokenBaos.toByteArray());
+ DataInput in = new DataInputStream(bais);
+
+ String strGram = in.readUTF();
+
+ // System.out.println("\"" + strGram + "\"");
+
+ Assert.assertEquals(expectedGrams.get(tokenCount), strGram);
+
+ tokenCount++;
+ }
+ // System.out.println("---------");
+ }
+
+ @Test
+ public void testNGramTokenizerWithCountedHashedUTF8Tokens()
+ throws Exception {
+ runTestNGramTokenizerWithCountedHashedUTF8Tokens(false);
+ runTestNGramTokenizerWithCountedHashedUTF8Tokens(true);
+ }
+
+ @Test
+ public void testNGramTokenizerWithHashedUTF8Tokens() throws Exception {
+ runTestNGramTokenizerWithHashedUTF8Tokens(false);
+ runTestNGramTokenizerWithHashedUTF8Tokens(true);
+ }
+
+ @Test
+ public void testNGramTokenizerWithUTF8Tokens() throws IOException {
+ runTestNGramTokenizerWithUTF8Tokens(false);
+ runTestNGramTokenizerWithUTF8Tokens(true);
+ }
+
+ public int tokenHash(String token, int tokenCount) {
+ int h = AbstractUTF8Token.GOLDEN_RATIO_32;
+ for (int i = 0; i < token.length(); i++) {
+ h ^= token.charAt(i);
+ h *= AbstractUTF8Token.GOLDEN_RATIO_32;
+ }
+ return h + tokenCount;
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/SearchPerfTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/SearchPerfTest.java
new file mode 100644
index 0000000..33bf0c5
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/SearchPerfTest.java
@@ -0,0 +1,303 @@
+/*
+ * 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.invertedindex;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.logging.Level;
+
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+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.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.invertedindex.api.IInvertedIndexSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.InvertedIndex.InvertedIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.InvertedIndexSearchPredicate;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.OccurrenceThresholdPanicException;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.TOccurrenceSearcher;
+import edu.uci.ics.hyracks.storage.am.invertedindex.searchmodifiers.ConjunctiveSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.searchmodifiers.JaccardSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.DelimitedUTF8StringBinaryTokenizer;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.UTF8WordTokenFactory;
+
+/**
+ * The purpose of this test is to evaluate the performance of searches against
+ * an inverted index. First, we generate random <token, id> pairs sorted on
+ * token, which are bulk loaded into an inverted index. Next, we build random
+ * queries from a list of predefined tokens in the index, and measure the
+ * performance of executing them with different search modifiers. We test the
+ * ConjunctiveSearchModifier and the JaccardSearchModifier.
+ *
+ */
+public class SearchPerfTest extends AbstractInvIndexSearchTest {
+
+ protected List<String> tokens = new ArrayList<String>();
+
+ @Override
+ protected void setTokenizer() {
+ tokenFactory = new UTF8WordTokenFactory();
+ tokenizer = new DelimitedUTF8StringBinaryTokenizer(true, false,
+ tokenFactory);
+ }
+
+ @Before
+ public void start() throws Exception {
+ super.start();
+ loadData();
+ }
+
+ public void loadData() throws HyracksDataException, TreeIndexException {
+ tokens.add("compilers");
+ tokens.add("computer");
+ tokens.add("databases");
+ tokens.add("fast");
+ tokens.add("hyracks");
+ tokens.add("major");
+ tokens.add("science");
+ tokens.add("systems");
+ tokens.add("university");
+
+ for (int i = 0; i < tokens.size(); i++) {
+ checkInvLists.add(new ArrayList<Integer>());
+ }
+
+ // for generating length-skewed inverted lists
+ int addProb = 0;
+ int addProbStep = 10;
+
+ IIndexBulkLoadContext ctx = invIndex.beginBulkLoad(BTree.DEFAULT_FILL_FACTOR);
+
+ for (int i = 0; i < tokens.size(); i++) {
+
+ addProb += addProbStep * (i + 1);
+ for (int j = 0; j < maxId; j++) {
+ if ((Math.abs(rnd.nextInt()) % addProb) == 0) {
+ tb.reset();
+ UTF8StringSerializerDeserializer.INSTANCE.serialize(
+ tokens.get(i), tb.getDataOutput());
+ tb.addFieldEndOffset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(j, tb.getDataOutput());
+ tb.addFieldEndOffset();
+ tuple.reset(tb.getFieldEndOffsets(), tb.getByteArray());
+ checkInvLists.get(i).add(j);
+ try {
+ invIndex.bulkLoadAddTuple(tuple, ctx);
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+ }
+ }
+ invIndex.endBulkLoad(ctx);
+ }
+
+ /**
+ * Determine the expected results with the ScanCount algorithm. The
+ * ScanCount algorithm is very simple, so we can be confident the results
+ * are correct.
+ *
+ */
+ protected void fillExpectedResults(int[] queryTokenIndexes,
+ int numQueryTokens, int occurrenceThreshold) {
+ // reset scan count array
+ for (int i = 0; i < maxId; i++) {
+ scanCountArray[i] = 0;
+ }
+
+ // count occurrences
+ for (int i = 0; i < numQueryTokens; i++) {
+ ArrayList<Integer> list = checkInvLists.get(queryTokenIndexes[i]);
+ for (int j = 0; j < list.size(); j++) {
+ scanCountArray[list.get(j)]++;
+ }
+ }
+
+ // check threshold
+ expectedResults.clear();
+ for (int i = 0; i < maxId; i++) {
+ if (scanCountArray[i] >= occurrenceThreshold) {
+ expectedResults.add(i);
+ }
+ }
+ }
+
+ /**
+ * Generates a specified number of queries. Each query consists of a set of
+ * randomly chosen tokens that are picked from the pre-defined set of
+ * tokens. We run each query, measure it's time, and verify it's results
+ * against the results produced by ScanCount, implemented in
+ * fillExpectedResults().
+ *
+ */
+ private void runQueries(IInvertedIndexSearchModifier searchModifier,
+ int numQueries) throws Exception {
+
+ rnd.setSeed(50);
+
+ InvertedIndexAccessor accessor = (InvertedIndexAccessor) invIndex.createAccessor();
+ InvertedIndexSearchPredicate searchPred = new InvertedIndexSearchPredicate(tokenizer, searchModifier);
+
+ // generate random queries
+ int[] queryTokenIndexes = new int[tokens.size()];
+ for (int i = 0; i < numQueries; i++) {
+
+ int numQueryTokens = Math.abs(rnd.nextInt() % tokens.size()) + 1;
+ for (int j = 0; j < numQueryTokens; j++) {
+ queryTokenIndexes[j] = Math.abs(rnd.nextInt() % tokens.size());
+ }
+
+ StringBuilder strBuilder = new StringBuilder();
+ for (int j = 0; j < numQueryTokens; j++) {
+ strBuilder.append(tokens.get(queryTokenIndexes[j]));
+ if (j + 1 != numQueryTokens) {
+ strBuilder.append(" ");
+ }
+ }
+
+ String queryString = strBuilder.toString();
+
+ // Serialize query.
+ queryTb.reset();
+ UTF8StringSerializerDeserializer.INSTANCE.serialize(queryString,
+ queryTb.getDataOutput());
+ queryTb.addFieldEndOffset();
+ queryTuple.reset(queryTb.getFieldEndOffsets(), queryTb.getByteArray());
+
+ // Set query tuple in search predicate.
+ searchPred.setQueryTuple(queryTuple);
+ searchPred.setQueryFieldIndex(0);
+
+ boolean panic = false;
+
+ resultCursor = accessor.createSearchCursor();
+ int repeats = 1;
+ double totalTime = 0;
+ for (int j = 0; j < repeats; j++) {
+ long timeStart = System.currentTimeMillis();
+ try {
+ resultCursor.reset();
+ accessor.search(resultCursor, searchPred);
+ } catch (OccurrenceThresholdPanicException e) {
+ panic = true;
+ }
+ long timeEnd = System.currentTimeMillis();
+ totalTime += timeEnd - timeStart;
+ }
+ double avgTime = totalTime / (double) repeats;
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(i + ": " + "\"" + queryString + "\": " + avgTime
+ + "ms");
+ }
+
+ if (!panic) {
+ TOccurrenceSearcher searcher = (TOccurrenceSearcher) accessor.getSearcher();
+ fillExpectedResults(queryTokenIndexes, numQueryTokens,
+ searcher.getOccurrenceThreshold());
+ // verify results
+ int checkIndex = 0;
+ while (resultCursor.hasNext()) {
+ resultCursor.next();
+ ITupleReference resultTuple = resultCursor.getTuple();
+ int id = IntegerSerializerDeserializer.getInt(
+ resultTuple.getFieldData(0),
+ resultTuple.getFieldStart(0));
+ Assert.assertEquals(expectedResults.get(checkIndex)
+ .intValue(), id);
+ checkIndex++;
+ }
+
+ if (expectedResults.size() != checkIndex) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("CHECKING");
+ }
+ StringBuilder expectedStrBuilder = new StringBuilder();
+ for (Integer x : expectedResults) {
+ expectedStrBuilder.append(x + " ");
+ }
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(expectedStrBuilder.toString());
+ }
+ }
+
+ Assert.assertEquals(expectedResults.size(), checkIndex);
+ }
+ }
+ }
+
+ /**
+ * Runs 50 random conjunctive search queries to test the
+ * ConjunctiveSearchModifier.
+ *
+ */
+ @Test
+ public void conjunctiveKeywordQueryTest() throws Exception {
+ IInvertedIndexSearchModifier searchModifier = new ConjunctiveSearchModifier();
+ runQueries(searchModifier, 50);
+ }
+
+ /**
+ * Runs 50 random jaccard-based search queries with thresholds 1.0, 0.9,
+ * 0.8, 0.7, 0.6, 0.5. Tests the JaccardSearchModifier.
+ *
+ */
+ @Test
+ public void jaccardKeywordQueryTest() throws Exception {
+ JaccardSearchModifier searchModifier = new JaccardSearchModifier(1.0f);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("JACCARD: " + 1.0f);
+ }
+ searchModifier.setJaccThresh(1.0f);
+ runQueries(searchModifier, 50);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("JACCARD: " + 0.9f);
+ }
+ searchModifier.setJaccThresh(0.9f);
+ runQueries(searchModifier, 50);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("JACCARD: " + 0.8f);
+ }
+ searchModifier.setJaccThresh(0.8f);
+ runQueries(searchModifier, 50);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("JACCARD: " + 0.7f);
+ }
+ searchModifier.setJaccThresh(0.7f);
+ runQueries(searchModifier, 50);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("JACCARD: " + 0.6f);
+ }
+ searchModifier.setJaccThresh(0.6f);
+ runQueries(searchModifier, 50);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("JACCARD: " + 0.5f);
+ }
+ searchModifier.setJaccThresh(0.5f);
+ runQueries(searchModifier, 50);
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/SearchTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/SearchTest.java
new file mode 100644
index 0000000..c3c9b99
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/SearchTest.java
@@ -0,0 +1,308 @@
+/*
+ * 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.invertedindex;
+
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.logging.Level;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.data.std.util.ByteArrayAccessibleOutputStream;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.invertedindex.api.IInvertedIndexSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.InvertedIndex.InvertedIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.InvertedIndexSearchPredicate;
+import edu.uci.ics.hyracks.storage.am.invertedindex.impls.OccurrenceThresholdPanicException;
+import edu.uci.ics.hyracks.storage.am.invertedindex.searchmodifiers.ConjunctiveSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.searchmodifiers.EditDistanceSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.searchmodifiers.JaccardSearchModifier;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.IToken;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.NGramUTF8StringBinaryTokenizer;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.UTF8NGramTokenFactory;
+
+public class SearchTest extends AbstractInvIndexSearchTest {
+
+ protected List<String> dataStrings = new ArrayList<String>();
+ protected List<String> firstNames = new ArrayList<String>();
+ protected List<String> lastNames = new ArrayList<String>();
+
+ protected IBinaryComparator[] btreeBinCmps;
+
+ @Override
+ protected void setTokenizer() {
+ tokenFactory = new UTF8NGramTokenFactory();
+ tokenizer = new NGramUTF8StringBinaryTokenizer(3, false, true, false,
+ tokenFactory);
+ }
+
+ @Before
+ public void start() throws Exception {
+ super.start();
+ btreeBinCmps = new IBinaryComparator[btreeCmpFactories.length];
+ for (int i = 0; i < btreeCmpFactories.length; i++) {
+ btreeBinCmps[i] = btreeCmpFactories[i].createBinaryComparator();
+ }
+ generateDataStrings();
+ loadData();
+ }
+
+ public void generateDataStrings() {
+ firstNames.add("Kathrin");
+ firstNames.add("Cathrin");
+ firstNames.add("Kathryn");
+ firstNames.add("Cathryn");
+ firstNames.add("Kathrine");
+ firstNames.add("Cathrine");
+ firstNames.add("Kathryne");
+ firstNames.add("Cathryne");
+ firstNames.add("Katherin");
+ firstNames.add("Catherin");
+ firstNames.add("Katheryn");
+ firstNames.add("Catheryn");
+ firstNames.add("Katherine");
+ firstNames.add("Catherine");
+ firstNames.add("Katheryne");
+ firstNames.add("Catheryne");
+ firstNames.add("John");
+ firstNames.add("Jack");
+ firstNames.add("Jonathan");
+ firstNames.add("Nathan");
+
+ lastNames.add("Miller");
+ lastNames.add("Myller");
+ lastNames.add("Keller");
+ lastNames.add("Ketler");
+ lastNames.add("Muller");
+ lastNames.add("Fuller");
+ lastNames.add("Smith");
+ lastNames.add("Smyth");
+ lastNames.add("Smithe");
+ lastNames.add("Smythe");
+
+ // Generate all 'firstName lastName' combinations as data strings
+ for (String f : firstNames) {
+ for (String l : lastNames) {
+ dataStrings.add(f + " " + l);
+ }
+ }
+ }
+
+ private class TokenIdPair implements Comparable<TokenIdPair> {
+ public ByteArrayAccessibleOutputStream baaos = new ByteArrayAccessibleOutputStream();
+ public DataOutputStream dos = new DataOutputStream(baaos);
+ public int id;
+
+ TokenIdPair(IToken token, int id) throws IOException {
+ token.serializeToken(dos);
+ this.id = id;
+ }
+
+ @Override
+ public int compareTo(TokenIdPair o) {
+ int cmp = btreeBinCmps[0].compare(baaos.getByteArray(), 0,
+ baaos.getByteArray().length, o.baaos.getByteArray(), 0,
+ o.baaos.getByteArray().length);
+ if (cmp == 0) {
+ return id - o.id;
+ } else {
+ return cmp;
+ }
+ }
+ }
+
+ public void loadData() throws IOException, TreeIndexException {
+ List<TokenIdPair> pairs = new ArrayList<TokenIdPair>();
+ // generate pairs for subsequent sorting and bulk-loading
+ int id = 0;
+ for (String s : dataStrings) {
+ ByteArrayAccessibleOutputStream baaos = new ByteArrayAccessibleOutputStream();
+ DataOutputStream dos = new DataOutputStream(baaos);
+ UTF8StringSerializerDeserializer.INSTANCE.serialize(s, dos);
+ tokenizer.reset(baaos.getByteArray(), 0, baaos.size());
+ while (tokenizer.hasNext()) {
+ tokenizer.next();
+ IToken token = tokenizer.getToken();
+ pairs.add(new TokenIdPair(token, id));
+ }
+ ++id;
+ }
+ Collections.sort(pairs);
+
+ // bulk load index
+ IIndexBulkLoadContext ctx = invIndex.beginBulkLoad(BTree.DEFAULT_FILL_FACTOR);
+
+ for (TokenIdPair t : pairs) {
+ tb.reset();
+ tb.addField(t.baaos.getByteArray(), 0,
+ t.baaos.getByteArray().length);
+ IntegerSerializerDeserializer.INSTANCE.serialize(t.id, tb.getDataOutput());
+ tb.addFieldEndOffset();
+ tuple.reset(tb.getFieldEndOffsets(), tb.getByteArray());
+
+ try {
+ invIndex.bulkLoadAddTuple(tuple, ctx);
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+ invIndex.endBulkLoad(ctx);
+ }
+
+ /**
+ * Runs a specified number of randomly picked strings from dataStrings as
+ * queries. We run each query, measure it's time, and print it's results.
+ *
+ */
+ private void runQueries(IInvertedIndexSearchModifier searchModifier,
+ int numQueries) throws Exception {
+
+ rnd.setSeed(50);
+
+ InvertedIndexAccessor accessor = (InvertedIndexAccessor) invIndex.createAccessor();
+ InvertedIndexSearchPredicate searchPred = new InvertedIndexSearchPredicate(tokenizer, searchModifier);
+
+ for (int i = 0; i < numQueries; i++) {
+
+ int queryIndex = Math.abs(rnd.nextInt() % dataStrings.size());
+ String queryString = dataStrings.get(queryIndex);
+
+ // Serialize query.
+ queryTb.reset();
+ UTF8StringSerializerDeserializer.INSTANCE.serialize(queryString,
+ queryTb.getDataOutput());
+ queryTb.addFieldEndOffset();
+ queryTuple.reset(queryTb.getFieldEndOffsets(), queryTb.getByteArray());
+
+ // Set query tuple in search predicate.
+ searchPred.setQueryTuple(queryTuple);
+ searchPred.setQueryFieldIndex(0);
+
+ resultCursor = accessor.createSearchCursor();
+
+ int repeats = 1;
+ double totalTime = 0;
+ for (int j = 0; j < repeats; j++) {
+ long timeStart = System.currentTimeMillis();
+ try {
+ resultCursor.reset();
+ accessor.search(resultCursor, searchPred);
+ } catch (OccurrenceThresholdPanicException e) {
+ // ignore panic queries
+ }
+ long timeEnd = System.currentTimeMillis();
+ totalTime += timeEnd - timeStart;
+ }
+ double avgTime = totalTime / (double) repeats;
+ StringBuilder strBuilder = new StringBuilder();
+ strBuilder.append(i + ": " + "\"" + queryString + "\": " + avgTime
+ + "ms" + "\n");
+ strBuilder.append("CANDIDATE RESULTS:\n");
+ while (resultCursor.hasNext()) {
+ resultCursor.next();
+ ITupleReference resultTuple = resultCursor.getTuple();
+ int id = IntegerSerializerDeserializer.getInt(
+ resultTuple.getFieldData(0),
+ resultTuple.getFieldStart(0));
+ strBuilder.append(id + " " + dataStrings.get(id));
+ strBuilder.append('\n');
+ }
+ // remove trailing newline
+ strBuilder.deleteCharAt(strBuilder.length() - 1);
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info(strBuilder.toString());
+ }
+ }
+ }
+
+ /**
+ * Runs 5 random conjunctive search queries to test the
+ * ConjunctiveSearchModifier.
+ *
+ */
+ @Test
+ public void conjunctiveQueryTest() throws Exception {
+ IInvertedIndexSearchModifier searchModifier = new ConjunctiveSearchModifier();
+ runQueries(searchModifier, 5);
+ }
+
+ /**
+ * Runs 5 random jaccard-based search queries with thresholds 0.9, 0.8, 0.7.
+ * Tests the JaccardSearchModifier.
+ *
+ */
+ @Test
+ public void jaccardQueryTest() throws Exception {
+ JaccardSearchModifier searchModifier = new JaccardSearchModifier(1.0f);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("JACCARD: " + 0.9f);
+ }
+ searchModifier.setJaccThresh(0.9f);
+ runQueries(searchModifier, 5);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("JACCARD: " + 0.8f);
+ }
+ searchModifier.setJaccThresh(0.8f);
+ runQueries(searchModifier, 5);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("JACCARD: " + 0.7f);
+ }
+ searchModifier.setJaccThresh(0.7f);
+ runQueries(searchModifier, 5);
+ }
+
+ /**
+ * Runs 5 random edit-distance based search queries with thresholds 1, 2, 3.
+ * Tests the EditDistanceSearchModifier.
+ *
+ */
+ @Test
+ public void editDistanceQueryTest() throws Exception {
+ EditDistanceSearchModifier searchModifier = new EditDistanceSearchModifier(
+ 3, 0);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("EDIT DISTANCE: " + 1);
+ }
+ searchModifier.setEdThresh(1);
+ runQueries(searchModifier, 5);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("EDIT DISTANCE: " + 2);
+ }
+ searchModifier.setEdThresh(2);
+ runQueries(searchModifier, 5);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("EDIT DISTANCE: " + 3);
+ }
+ searchModifier.setEdThresh(3);
+ runQueries(searchModifier, 5);
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/WordTokenizerTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/WordTokenizerTest.java
new file mode 100644
index 0000000..53fb96d
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-invertedindex-test/src/test/java/edu/uci/ics/hyracks/storage/am/invertedindex/WordTokenizerTest.java
@@ -0,0 +1,221 @@
+/**
+ * Copyright 2010-2011 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 at
+ *
+ * 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.
+ *
+ * Author: Alexander Behm <abehm (at) ics.uci.edu>
+ */
+
+package edu.uci.ics.hyracks.storage.am.invertedindex;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.io.DataOutput;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+
+import junit.framework.Assert;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.AbstractUTF8Token;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.DelimitedUTF8StringBinaryTokenizer;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.HashedUTF8WordTokenFactory;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.IToken;
+import edu.uci.ics.hyracks.storage.am.invertedindex.tokenizers.UTF8WordTokenFactory;
+
+public class WordTokenizerTest {
+
+ private String text = "Hello World, I would like to inform you of the importance of Foo Bar. Yes, Foo Bar. Jürgen.";
+ private byte[] inputBuffer;
+
+ private ArrayList<String> expectedUTF8Tokens = new ArrayList<String>();
+ private ArrayList<Integer> expectedHashedUTF8Tokens = new ArrayList<Integer>();
+ private ArrayList<Integer> expectedCountedHashedUTF8Tokens = new ArrayList<Integer>();
+
+ private boolean isSeparator(char c) {
+ return !(Character.isLetterOrDigit(c) || Character.getType(c) == Character.OTHER_LETTER || Character.getType(c) == Character.OTHER_NUMBER);
+ }
+
+ private void tokenize(String text, ArrayList<String> tokens) {
+ String lowerCaseText = text.toLowerCase();
+ int startIx = 0;
+
+ // Skip separators at beginning of string.
+ while(isSeparator(lowerCaseText.charAt(startIx))) {
+ startIx++;
+ }
+ while(startIx < lowerCaseText.length()) {
+ while(startIx < lowerCaseText.length() && isSeparator(lowerCaseText.charAt(startIx))) {
+ startIx++;
+ }
+ int tokenStart = startIx;
+
+ while(startIx < lowerCaseText.length() && !isSeparator(lowerCaseText.charAt(startIx))) {
+ startIx++;
+ }
+ int tokenEnd = startIx;
+
+ // Emit token.
+ String token = lowerCaseText.substring(tokenStart, tokenEnd);
+
+ tokens.add(token);
+ }
+ }
+
+ @Before
+ public void init() throws IOException {
+ // serialize text into bytes
+ ByteArrayOutputStream baos = new ByteArrayOutputStream();
+ DataOutput dos = new DataOutputStream(baos);
+ dos.writeUTF(text);
+ inputBuffer = baos.toByteArray();
+
+ // init expected string tokens
+ tokenize(text, expectedUTF8Tokens);
+
+ // hashed tokens ignoring token count
+ for (int i = 0; i < expectedUTF8Tokens.size(); i++) {
+ int hash = tokenHash(expectedUTF8Tokens.get(i), 1);
+ expectedHashedUTF8Tokens.add(hash);
+ }
+
+ // hashed tokens using token count
+ HashMap<String, Integer> tokenCounts = new HashMap<String, Integer>();
+ for (int i = 0; i < expectedUTF8Tokens.size(); i++) {
+ Integer count = tokenCounts.get(expectedUTF8Tokens.get(i));
+ if (count == null) {
+ count = 1;
+ tokenCounts.put(expectedUTF8Tokens.get(i), count);
+ } else {
+ count++;
+ }
+
+ int hash = tokenHash(expectedUTF8Tokens.get(i), count);
+ expectedCountedHashedUTF8Tokens.add(hash);
+ }
+ }
+
+ @Test
+ public void testWordTokenizerWithCountedHashedUTF8Tokens() throws IOException {
+
+ HashedUTF8WordTokenFactory tokenFactory = new HashedUTF8WordTokenFactory();
+ DelimitedUTF8StringBinaryTokenizer tokenizer = new DelimitedUTF8StringBinaryTokenizer(false, false,
+ tokenFactory);
+
+ tokenizer.reset(inputBuffer, 0, inputBuffer.length);
+
+ int tokenCount = 0;
+
+ while (tokenizer.hasNext()) {
+ tokenizer.next();
+
+ // serialize token
+ ByteArrayOutputStream tokenBaos = new ByteArrayOutputStream();
+ DataOutput tokenDos = new DataOutputStream(tokenBaos);
+
+ IToken token = tokenizer.getToken();
+ token.serializeToken(tokenDos);
+
+ // deserialize token
+ ByteArrayInputStream bais = new ByteArrayInputStream(tokenBaos.toByteArray());
+ DataInput in = new DataInputStream(bais);
+
+ Integer hashedToken = in.readInt();
+
+ Assert.assertEquals(hashedToken, expectedCountedHashedUTF8Tokens.get(tokenCount));
+
+ tokenCount++;
+ }
+ }
+
+ @Test
+ public void testWordTokenizerWithHashedUTF8Tokens() throws IOException {
+
+ HashedUTF8WordTokenFactory tokenFactory = new HashedUTF8WordTokenFactory();
+ DelimitedUTF8StringBinaryTokenizer tokenizer = new DelimitedUTF8StringBinaryTokenizer(true, false, tokenFactory);
+
+ tokenizer.reset(inputBuffer, 0, inputBuffer.length);
+
+ int tokenCount = 0;
+
+ while (tokenizer.hasNext()) {
+ tokenizer.next();
+
+ // serialize token
+ ByteArrayOutputStream tokenBaos = new ByteArrayOutputStream();
+ DataOutput tokenDos = new DataOutputStream(tokenBaos);
+
+ IToken token = tokenizer.getToken();
+ token.serializeToken(tokenDos);
+
+ // deserialize token
+ ByteArrayInputStream bais = new ByteArrayInputStream(tokenBaos.toByteArray());
+ DataInput in = new DataInputStream(bais);
+
+ Integer hashedToken = in.readInt();
+
+ Assert.assertEquals(expectedHashedUTF8Tokens.get(tokenCount), hashedToken);
+
+ tokenCount++;
+ }
+ }
+
+ @Test
+ public void testWordTokenizerWithUTF8Tokens() throws IOException {
+
+ UTF8WordTokenFactory tokenFactory = new UTF8WordTokenFactory();
+ DelimitedUTF8StringBinaryTokenizer tokenizer = new DelimitedUTF8StringBinaryTokenizer(true, false, tokenFactory);
+
+ tokenizer.reset(inputBuffer, 0, inputBuffer.length);
+
+ int tokenCount = 0;
+
+ while (tokenizer.hasNext()) {
+ tokenizer.next();
+
+ // serialize hashed token
+ ByteArrayOutputStream tokenBaos = new ByteArrayOutputStream();
+ DataOutput tokenDos = new DataOutputStream(tokenBaos);
+
+ IToken token = tokenizer.getToken();
+ token.serializeToken(tokenDos);
+
+ // deserialize token
+ ByteArrayInputStream bais = new ByteArrayInputStream(tokenBaos.toByteArray());
+ DataInput in = new DataInputStream(bais);
+
+ String strToken = in.readUTF();
+
+ Assert.assertEquals(expectedUTF8Tokens.get(tokenCount), strToken);
+
+ tokenCount++;
+ }
+ }
+
+ // JAQL Hash
+ public int tokenHash(String token, int tokenCount) {
+ int h = AbstractUTF8Token.GOLDEN_RATIO_32;
+ for (int i = 0; i < token.length(); i++) {
+ h ^= token.charAt(i);
+ h *= AbstractUTF8Token.GOLDEN_RATIO_32;
+ }
+ return h + tokenCount;
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
new file mode 100644
index 0000000..247969e
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/pom.xml
@@ -0,0 +1,50 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-rtree-test</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <name>hyracks-storage-am-rtree-test</name>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-tests</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ </parent>
+
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-compiler-plugin</artifactId>
+ <version>2.0.2</version>
+ <configuration>
+ <source>1.6</source>
+ <target>1.6</target>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+ <dependencies>
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <version>4.8.1</version>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-rtree</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-test-support</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
+ </dependencies>
+</project>
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeBulkLoadTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeBulkLoadTest.java
new file mode 100644
index 0000000..58bca10
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeBulkLoadTest.java
@@ -0,0 +1,61 @@
+/*
+ * 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.rtree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeBulkLoadTest;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+@SuppressWarnings("rawtypes")
+public class RTreeBulkLoadTest extends AbstractRTreeBulkLoadTest {
+
+ public RTreeBulkLoadTest() {
+ super(1);
+ }
+
+ private final RTreeTestHarness harness = new RTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+ return RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(), fieldSerdes,
+ valueProviderFactories, numKeys);
+ }
+
+ @Override
+ protected Random getRandom() {
+ return harness.getRandom();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java
new file mode 100644
index 0000000..42e933e
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeDeleteTest.java
@@ -0,0 +1,57 @@
+/*
+ * 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.rtree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeDeleteTest;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+@SuppressWarnings("rawtypes")
+public class RTreeDeleteTest extends AbstractRTreeDeleteTest {
+
+ private final RTreeTestHarness harness = new RTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+ return RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(), fieldSerdes,
+ valueProviderFactories, numKeys);
+ }
+
+ @Override
+ protected Random getRandom() {
+ return harness.getRandom();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.java
new file mode 100644
index 0000000..c72338e
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeExamplesTest.java
@@ -0,0 +1,56 @@
+/*
+ * 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.rtree;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeExamplesTest;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+public class RTreeExamplesTest extends AbstractRTreeExamplesTest {
+ private final RTreeTestHarness harness = new RTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] rtreeCmpFactories,
+ IBinaryComparatorFactory[] btreeCmpFactories, IPrimitiveValueProviderFactory[] valueProviderFactories)
+ throws TreeIndexException {
+ return RTreeUtils.createRTree(harness.getBufferCache(), typeTraits,
+ valueProviderFactories, rtreeCmpFactories);
+ }
+
+ @Override
+ protected int getIndexFileId() {
+ return harness.getTreeFileId();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java
new file mode 100644
index 0000000..6efa620
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeInsertTest.java
@@ -0,0 +1,67 @@
+/*
+ * 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.rtree;
+
+import java.util.Random;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeInsertTest;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+/**
+ * Tests the BTree insert operation with strings and integer fields using
+ * various numbers of key and payload fields.
+ *
+ * Each tests first fills a BTree with randomly generated tuples. We compare the
+ * following operations against expected results: 1. Point searches for all
+ * tuples. 2. Ordered scan. 3. Disk-order scan. 4. Range search (and prefix
+ * search for composite keys).
+ *
+ */
+@SuppressWarnings("rawtypes")
+public class RTreeInsertTest extends AbstractRTreeInsertTest {
+
+ private final RTreeTestHarness harness = new RTreeTestHarness();
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected AbstractRTreeTestContext createTestContext(ISerializerDeserializer[] fieldSerdes,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, int numKeys) throws Exception {
+ return RTreeTestContext.create(harness.getBufferCache(), harness.getTreeFileId(), fieldSerdes,
+ valueProviderFactories, numKeys);
+ }
+
+ @Override
+ protected Random getRandom() {
+ return harness.getRandom();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
new file mode 100644
index 0000000..8332c11
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
@@ -0,0 +1,175 @@
+/*
+ * 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.rtree;
+
+import java.util.ArrayList;
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+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.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+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.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+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.rtree.RTreeCheckTuple;
+import edu.uci.ics.hyracks.storage.am.rtree.RTreeTestUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.AbstractRTreeTest;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+public class RTreeSearchCursorTest extends AbstractRTreeTest {
+
+ private final RTreeTestUtils rTreeTestUtils;
+ private Random rnd = new Random(50);
+
+ public RTreeSearchCursorTest() {
+ this.rTreeTestUtils = new RTreeTestUtils();
+ }
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ super.setUp();
+ }
+
+ @SuppressWarnings({ "unchecked", "rawtypes" })
+ @Test
+ public void rangeSearchTest() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("TESTING RANGE SEARCH CURSOR FOR RTREE");
+ }
+
+ IBufferCache bufferCache = harness.getBufferCache();
+ int rtreeFileId = harness.getTreeFileId();
+
+ // Declare fields.
+ int fieldCount = 5;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ typeTraits[0] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[1] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[2] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[3] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[4] = IntegerPointable.TYPE_TRAITS;
+ // Declare field serdes.
+ ISerializerDeserializer[] fieldSerdes = { IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+
+ // Declare keys.
+ int keyFieldCount = 4;
+ IBinaryComparatorFactory[] cmpFactories = new IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[1] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[2] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[3] = PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ // create value providers
+ IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+ cmpFactories.length, IntegerPointable.FACTORY);
+
+ RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+ ITreeIndexFrameFactory interiorFrameFactory = new RTreeNSMInteriorFrameFactory(tupleWriterFactory,
+ valueProviderFactories);
+ ITreeIndexFrameFactory leafFrameFactory = new RTreeNSMLeafFrameFactory(tupleWriterFactory,
+ valueProviderFactories);
+
+ IRTreeInteriorFrame interiorFrame = (IRTreeInteriorFrame) interiorFrameFactory.createFrame();
+ IRTreeLeafFrame leafFrame = (IRTreeLeafFrame) leafFrameFactory.createFrame();
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, 0, metaFrameFactory);
+
+ RTree rtree = new RTree(bufferCache, fieldCount, cmpFactories, freePageManager, interiorFrameFactory,
+ leafFrameFactory);
+ rtree.create(rtreeFileId);
+ rtree.open(rtreeFileId);
+
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ ITreeIndexAccessor indexAccessor = rtree.createAccessor();
+ int numInserts = 10000;
+ ArrayList<RTreeCheckTuple> checkTuples = new ArrayList<RTreeCheckTuple>();
+ for (int i = 0; i < numInserts; i++) {
+ int p1x = rnd.nextInt();
+ int p1y = rnd.nextInt();
+ int p2x = rnd.nextInt();
+ int p2y = rnd.nextInt();
+
+ int pk = rnd.nextInt();;
+
+ TupleUtils.createIntegerTuple(tb, tuple, Math.min(p1x, p2x), Math.min(p1y, p2y), Math.max(p1x, p2x),
+ Math.max(p1y, p2y), pk);
+ try {
+ indexAccessor.insert(tuple);
+ } catch (TreeIndexException e) {
+ }
+ RTreeCheckTuple checkTuple = new RTreeCheckTuple(fieldCount, keyFieldCount);
+ checkTuple.add(Math.min(p1x, p2x));
+ checkTuple.add(Math.min(p1y, p2y));
+ checkTuple.add(Math.max(p1x, p2x));
+ checkTuple.add(Math.max(p1y, p2y));
+ checkTuple.add(pk);
+
+ checkTuples.add(checkTuple);
+ }
+
+ // Build key.
+ ArrayTupleBuilder keyTb = new ArrayTupleBuilder(keyFieldCount);
+ ArrayTupleReference key = new ArrayTupleReference();
+ TupleUtils.createIntegerTuple(keyTb, key, -1000, -1000, 1000, 1000);
+
+ MultiComparator cmp = MultiComparator.create(cmpFactories);
+ ITreeIndexCursor searchCursor = new RTreeSearchCursor(interiorFrame, leafFrame);
+ SearchPredicate searchPredicate = new SearchPredicate(key, cmp);
+
+ RTreeCheckTuple keyCheck = (RTreeCheckTuple) rTreeTestUtils.createCheckTupleFromTuple(key, fieldSerdes,
+ keyFieldCount);
+ ArrayList<RTreeCheckTuple> expectedResult = rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
+
+ rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
+ indexAccessor.search(searchCursor, searchPredicate);
+
+ rTreeTestUtils.checkExpectedResults(searchCursor, expectedResult, fieldSerdes, keyFieldCount, null);
+
+ rtree.close();
+ }
+
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeMultiThreadTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeMultiThreadTest.java
new file mode 100644
index 0000000..7520793
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeMultiThreadTest.java
@@ -0,0 +1,97 @@
+/*
+ * 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.rtree.multithread;
+
+import java.util.ArrayList;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.ITreeIndexTestWorkerFactory;
+import edu.uci.ics.hyracks.storage.am.common.TestWorkloadConf;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector.TestOperation;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeMultiThreadTest;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.utils.RTreeTestHarness;
+
+public class RTreeMultiThreadTest extends AbstractRTreeMultiThreadTest {
+
+ private RTreeTestHarness harness = new RTreeTestHarness();
+
+ private RTreeTestWorkerFactory workerFactory = new RTreeTestWorkerFactory();
+
+ @Override
+ protected void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @Override
+ protected void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+
+ @Override
+ protected ITreeIndex createTreeIndex(ITypeTraits[] typeTraits, IBinaryComparatorFactory[] rtreeCmpFactories,
+ IBinaryComparatorFactory[] btreeCmpFactories, IPrimitiveValueProviderFactory[] valueProviderFactories)
+ throws TreeIndexException {
+ return RTreeUtils.createRTree(harness.getBufferCache(), typeTraits,
+ valueProviderFactories, rtreeCmpFactories);
+
+ }
+
+ @Override
+ protected ITreeIndexTestWorkerFactory getWorkerFactory() {
+ return workerFactory;
+ }
+
+ @Override
+ protected ArrayList<TestWorkloadConf> getTestWorkloadConf() {
+ ArrayList<TestWorkloadConf> workloadConfs = new ArrayList<TestWorkloadConf>();
+
+ // Insert only workload.
+ TestOperation[] insertOnlyOps = new TestOperation[] { TestOperation.INSERT };
+ workloadConfs.add(new TestWorkloadConf(insertOnlyOps, getUniformOpProbs(insertOnlyOps)));
+
+ // Inserts mixed with scans.
+ TestOperation[] insertSearchOnlyOps = new TestOperation[] { TestOperation.INSERT, TestOperation.SCAN,
+ TestOperation.DISKORDER_SCAN };
+ workloadConfs.add(new TestWorkloadConf(insertSearchOnlyOps, getUniformOpProbs(insertSearchOnlyOps)));
+
+ // Inserts and deletes.
+ TestOperation[] insertDeleteOps = new TestOperation[] { TestOperation.INSERT, TestOperation.DELETE };
+ workloadConfs.add(new TestWorkloadConf(insertDeleteOps, getUniformOpProbs(insertDeleteOps)));
+
+ // All operations mixed.
+ TestOperation[] allOps = new TestOperation[] { TestOperation.INSERT, TestOperation.DELETE, TestOperation.SCAN,
+ TestOperation.DISKORDER_SCAN };
+ workloadConfs.add(new TestWorkloadConf(allOps, getUniformOpProbs(allOps)));
+
+ return workloadConfs;
+ }
+
+ @Override
+ protected int getFileId() {
+ return harness.getTreeFileId();
+ }
+
+ @Override
+ protected String getIndexTypeName() {
+ return "RTree";
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeTestWorker.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeTestWorker.java
new file mode 100644
index 0000000..f5867e6
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeTestWorker.java
@@ -0,0 +1,115 @@
+/*
+ * 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.rtree.multithread;
+
+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.storage.am.common.AbstractTreeIndexTestWorker;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector.TestOperation;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.common.datagen.DataGenThread;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
+
+public class RTreeTestWorker extends AbstractTreeIndexTestWorker {
+
+ private final RTree rtree;
+ private final int numFields;
+ private final ArrayTupleReference rearrangedTuple = new ArrayTupleReference();
+ private final ArrayTupleBuilder rearrangedTb;
+
+ public RTreeTestWorker(DataGenThread dataGen, TestOperationSelector opSelector, ITreeIndex index, int numBatches) {
+ super(dataGen, opSelector, index, numBatches);
+ rtree = (RTree) index;
+ numFields = rtree.getFieldCount();
+ rearrangedTb = new ArrayTupleBuilder(numFields);
+ }
+
+ @Override
+ public void performOp(ITupleReference tuple, TestOperation op) throws HyracksDataException, IndexException {
+ RTree.RTreeAccessor accessor = (RTree.RTreeAccessor) indexAccessor;
+ IIndexCursor searchCursor = accessor.createSearchCursor();
+ ITreeIndexCursor diskOrderScanCursor = accessor.createDiskOrderScanCursor();
+ MultiComparator cmp = accessor.getOpContext().cmp;
+ SearchPredicate rangePred = new SearchPredicate(tuple, cmp);
+
+ switch (op) {
+ case INSERT:
+ rearrangeTuple(tuple, cmp);
+ accessor.insert(rearrangedTuple);
+ break;
+
+ case DELETE:
+ rearrangeTuple(tuple, cmp);
+ accessor.delete(rearrangedTuple);
+ break;
+
+ case SCAN:
+ searchCursor.reset();
+ rangePred.setSearchKey(null);
+ accessor.search(searchCursor, rangePred);
+ consumeCursorTuples(searchCursor);
+ break;
+
+ case DISKORDER_SCAN:
+ diskOrderScanCursor.reset();
+ accessor.diskOrderScan(diskOrderScanCursor);
+ consumeCursorTuples(diskOrderScanCursor);
+ break;
+
+ default:
+ throw new HyracksDataException("Op " + op.toString() + " not supported.");
+ }
+ }
+
+ private void rearrangeTuple(ITupleReference tuple, MultiComparator cmp) throws HyracksDataException {
+ // Create a tuple with rearranged key values to make sure lower points
+ // have larger coordinates than high points.
+ rearrangedTb.reset();
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i), tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j));
+ if (c > 0) {
+ rearrangedTb.addField(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j));
+ } else {
+ rearrangedTb.addField(tuple.getFieldData(i), tuple.getFieldStart(i), tuple.getFieldLength(i));
+ }
+ }
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i), tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j));
+ if (c > 0) {
+ rearrangedTb.addField(tuple.getFieldData(i), tuple.getFieldStart(i), tuple.getFieldLength(i));
+ } else {
+ rearrangedTb.addField(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j));
+ }
+ }
+ for (int i = cmp.getKeyFieldCount(); i < numFields; i++) {
+ rearrangedTb.addField(tuple.getFieldData(i), tuple.getFieldStart(i), tuple.getFieldLength(i));
+ }
+ rearrangedTuple.reset(rearrangedTb.getFieldEndOffsets(), rearrangedTb.getByteArray());
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeTestWorkerFactory.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeTestWorkerFactory.java
new file mode 100644
index 0000000..d4f14ca
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/multithread/RTreeTestWorkerFactory.java
@@ -0,0 +1,30 @@
+/*
+ * 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.rtree.multithread;
+
+import edu.uci.ics.hyracks.storage.am.common.AbstractTreeIndexTestWorker;
+import edu.uci.ics.hyracks.storage.am.common.ITreeIndexTestWorkerFactory;
+import edu.uci.ics.hyracks.storage.am.common.TestOperationSelector;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.datagen.DataGenThread;
+
+public class RTreeTestWorkerFactory implements ITreeIndexTestWorkerFactory {
+ @Override
+ public AbstractTreeIndexTestWorker create(DataGenThread dataGen, TestOperationSelector opSelector,
+ ITreeIndex index, int numBatches) {
+ return new RTreeTestWorker(dataGen, opSelector, index, numBatches);
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/AbstractRTreeTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/AbstractRTreeTest.java
new file mode 100644
index 0000000..fccb29c
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/AbstractRTreeTest.java
@@ -0,0 +1,46 @@
+/*
+ * 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.rtree.utils;
+
+import java.util.logging.Logger;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+
+public abstract class AbstractRTreeTest {
+ protected final Logger LOGGER = Logger.getLogger(RTreeTestHarness.class.getName());
+ protected final RTreeTestHarness harness;
+
+ public AbstractRTreeTest() {
+ harness = new RTreeTestHarness();
+ }
+
+ public AbstractRTreeTest(int pageSize, int numPages, int maxOpenFiles, int hyracksFrameSize) {
+ harness = new RTreeTestHarness(pageSize, numPages, maxOpenFiles, hyracksFrameSize);
+ }
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ harness.setUp();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ harness.tearDown();
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestContext.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestContext.java
new file mode 100644
index 0000000..039fb0b
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestContext.java
@@ -0,0 +1,60 @@
+/*
+ * 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.rtree.utils;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.dataflow.common.util.SerdeUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.rtree.AbstractRTreeTestContext;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+@SuppressWarnings("rawtypes")
+public class RTreeTestContext extends AbstractRTreeTestContext {
+
+ public RTreeTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
+ super(fieldSerdes, treeIndex);
+ }
+
+ @Override
+ public int getKeyFieldCount() {
+ RTree rtree = (RTree) treeIndex;
+ return rtree.getComparatorFactories().length;
+ }
+
+ @Override
+ public IBinaryComparatorFactory[] getComparatorFactories() {
+ RTree rtree = (RTree) treeIndex;
+ return rtree.getComparatorFactories();
+ }
+
+ public static RTreeTestContext create(IBufferCache bufferCache, int rtreeFileId,
+ ISerializerDeserializer[] fieldSerdes, IPrimitiveValueProviderFactory[] valueProviderFactories,
+ int numKeyFields) throws Exception {
+ ITypeTraits[] typeTraits = SerdeUtils.serdesToTypeTraits(fieldSerdes);
+ IBinaryComparatorFactory[] cmpFactories = SerdeUtils.serdesToComparatorFactories(fieldSerdes, numKeyFields);
+ RTree rtree = RTreeUtils
+ .createRTree(bufferCache, typeTraits, valueProviderFactories, cmpFactories);
+ rtree.create(rtreeFileId);
+ rtree.open(rtreeFileId);
+ RTreeTestContext testCtx = new RTreeTestContext(fieldSerdes, rtree);
+ return testCtx;
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestHarness.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestHarness.java
new file mode 100644
index 0000000..c0cec35
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/utils/RTreeTestHarness.java
@@ -0,0 +1,123 @@
+/*
+ * 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.rtree.utils;
+
+import java.io.File;
+import java.text.SimpleDateFormat;
+import java.util.Date;
+import java.util.Random;
+
+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.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 RTreeTestHarness {
+
+ private static final long RANDOM_SEED = 50;
+ private static final int DEFAULT_PAGE_SIZE = 256;
+ private static final int DEFAULT_NUM_PAGES = 1000;
+ private static final int DEFAULT_MAX_OPEN_FILES = 10;
+ private static final int DEFAULT_HYRACKS_FRAME_SIZE = 128;
+
+ protected final int pageSize;
+ protected final int numPages;
+ protected final int maxOpenFiles;
+ protected final int hyracksFrameSize;
+
+ protected IHyracksTaskContext ctx;
+ protected IBufferCache bufferCache;
+ protected int treeFileId;
+
+ protected final Random rnd = new Random();
+ protected final SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
+ protected final String tmpDir = System.getProperty("java.io.tmpdir");
+ protected final String sep = System.getProperty("file.separator");
+ protected String fileName;
+
+ public RTreeTestHarness() {
+ this.pageSize = DEFAULT_PAGE_SIZE;
+ this.numPages = DEFAULT_NUM_PAGES;
+ this.maxOpenFiles = DEFAULT_MAX_OPEN_FILES;
+ this.hyracksFrameSize = DEFAULT_HYRACKS_FRAME_SIZE;
+ }
+
+ public RTreeTestHarness(int pageSize, int numPages, int maxOpenFiles, int hyracksFrameSize) {
+ this.pageSize = pageSize;
+ this.numPages = numPages;
+ this.maxOpenFiles = maxOpenFiles;
+ this.hyracksFrameSize = hyracksFrameSize;
+ }
+
+ public void setUp() throws HyracksDataException {
+ fileName = tmpDir + sep + simpleDateFormat.format(new Date());
+ ctx = TestUtils.create(getHyracksFrameSize());
+ TestStorageManagerComponentHolder.init(pageSize, numPages, maxOpenFiles);
+ bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ treeFileId = fmp.lookupFileId(file);
+ bufferCache.openFile(treeFileId);
+ rnd.setSeed(RANDOM_SEED);
+ }
+
+ public void tearDown() throws HyracksDataException {
+ bufferCache.closeFile(treeFileId);
+ bufferCache.close();
+ File f = new File(fileName);
+ f.deleteOnExit();
+ }
+
+ public IHyracksTaskContext getHyracksTaskContext() {
+ return ctx;
+ }
+
+ public IBufferCache getBufferCache() {
+ return bufferCache;
+ }
+
+ public int getTreeFileId() {
+ return treeFileId;
+ }
+
+ public String getFileName() {
+ return fileName;
+ }
+
+ public Random getRandom() {
+ return rnd;
+ }
+
+ public int getPageSize() {
+ return pageSize;
+ }
+
+ public int getNumPages() {
+ return numPages;
+ }
+
+ public int getHyracksFrameSize() {
+ return hyracksFrameSize;
+ }
+
+ public int getMaxOpenFiles() {
+ return maxOpenFiles;
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/pom.xml b/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/pom.xml
new file mode 100644
index 0000000..b01f2a7
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/pom.xml
@@ -0,0 +1,49 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-common-test</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <name>hyracks-storage-common-test</name>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-tests</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ </parent>
+
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-compiler-plugin</artifactId>
+ <version>2.0.2</version>
+ <configuration>
+ <source>1.6</source>
+ <target>1.6</target>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+ <dependencies>
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <version>4.8.1</version>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-common</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-test-support</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ </dependencies>
+</project>
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/src/test/java/edu/uci/ics/hyracks/storage/common/BufferCacheRegressionTests.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/src/test/java/edu/uci/ics/hyracks/storage/common/BufferCacheRegressionTests.java
new file mode 100644
index 0000000..a649aa7
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/src/test/java/edu/uci/ics/hyracks/storage/common/BufferCacheRegressionTests.java
@@ -0,0 +1,171 @@
+package edu.uci.ics.hyracks.storage.common;
+
+import static org.junit.Assert.fail;
+
+import java.io.File;
+import java.io.IOException;
+import java.nio.ByteBuffer;
+
+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.api.io.IFileHandle;
+import edu.uci.ics.hyracks.api.io.IIOManager;
+import edu.uci.ics.hyracks.api.io.IIOManager.FileReadWriteMode;
+import edu.uci.ics.hyracks.api.io.IIOManager.FileSyncMode;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class BufferCacheRegressionTests {
+ protected static final String tmpDir = System.getProperty("java.io.tmpdir");
+ protected static final String sep = System.getProperty("file.separator");
+
+ protected String fileName = tmpDir + sep + "flushTestFile";
+
+ private static final int PAGE_SIZE = 256;
+ private static final int HYRACKS_FRAME_SIZE = PAGE_SIZE;
+ private IHyracksTaskContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+ // We want to test the following behavior when reclaiming a file slot in the
+ // buffer cache:
+ // 1. If the file being evicted was deleted, then its dirty pages should be
+ // invalidated, but most not be flushed.
+ // 2. If the file was not deleted, then we must flush its dirty pages.
+ @Test
+ public void testFlushBehaviorOnFileEviction() throws IOException {
+ File f = new File(fileName);
+ if (f.exists()) {
+ f.delete();
+ }
+ flushBehaviorTest(true);
+ flushBehaviorTest(false);
+ }
+
+ private void flushBehaviorTest(boolean deleteFile) throws IOException {
+ TestStorageManagerComponentHolder.init(PAGE_SIZE, 10, 1);
+
+ IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+
+ FileReference firstFileRef = new FileReference(new File(fileName));
+ bufferCache.createFile(firstFileRef);
+ int firstFileId = fmp.lookupFileId(firstFileRef);
+ bufferCache.openFile(firstFileId);
+
+ // Fill the first page with known data and make it dirty by write
+ // latching it.
+ ICachedPage writePage = bufferCache.pin(BufferedFileHandle.getDiskPageId(firstFileId, 0), true);
+ writePage.acquireWriteLatch();
+ try {
+ ByteBuffer buf = writePage.getBuffer();
+ for (int i = 0; i < buf.capacity(); i++) {
+ buf.put(Byte.MAX_VALUE);
+ }
+ } finally {
+ writePage.releaseWriteLatch();
+ bufferCache.unpin(writePage);
+ }
+ bufferCache.closeFile(firstFileId);
+ if (deleteFile) {
+ bufferCache.deleteFile(firstFileId, false);
+ }
+
+ // Create a file with the same name.
+ FileReference secondFileRef = new FileReference(new File(fileName));
+ bufferCache.createFile(secondFileRef);
+ int secondFileId = fmp.lookupFileId(secondFileRef);
+
+ // This open will replace the firstFileRef's slot in the BufferCache,
+ // causing it's pages to be cleaned up. We want to make sure that those
+ // dirty pages are not flushed to the disk, because the file was
+ // declared as deleted, and
+ // somebody might be already using the same filename again (having been
+ // assigned a different fileId).
+ bufferCache.openFile(secondFileId);
+
+ // Manually open the file and inspect it's contents. We cannot simply
+ // ask the BufferCache to pin the page, because it would return the same
+ // physical memory again, and for performance reasons pages are never
+ // reset with 0's.
+ IIOManager ioManager = ctx.getIOManager();
+ FileReference testFileRef = new FileReference(new File(fileName));
+ IFileHandle testFileHandle = ioManager.open(testFileRef, FileReadWriteMode.READ_ONLY,
+ FileSyncMode.METADATA_SYNC_DATA_SYNC);
+ ByteBuffer testBuffer = ByteBuffer.allocate(PAGE_SIZE);
+ ioManager.syncRead(testFileHandle, 0, testBuffer);
+ for (int i = 0; i < testBuffer.capacity(); i++) {
+ if (deleteFile) {
+ // We deleted the file. We expect to see a clean buffer.
+ if (testBuffer.get(i) == Byte.MAX_VALUE) {
+ fail("Page 0 of deleted file was fazily flushed in openFile(), "
+ + "corrupting the data of a newly created file with the same name.");
+ }
+ } else {
+ // We didn't delete the file. We expect to see a buffer full of
+ // Byte.MAX_VALUE.
+ if (testBuffer.get(i) != Byte.MAX_VALUE) {
+ fail("Page 0 of closed file was not flushed when properly, when reclaiming the file slot of fileId 0 in the BufferCache.");
+ }
+ }
+ }
+ ioManager.close(testFileHandle);
+ bufferCache.closeFile(secondFileId);
+ if (deleteFile) {
+ bufferCache.deleteFile(secondFileId, false);
+ }
+ bufferCache.close();
+ }
+
+ // Tests the behavior of the BufferCache when more than all pages are
+ // pinned. We expect an exception.
+ @Test
+ public void testPinningAllPages() throws HyracksDataException {
+ int numPages = 10;
+ TestStorageManagerComponentHolder.init(PAGE_SIZE, numPages, 1);
+
+ IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+
+ FileReference firstFileRef = new FileReference(new File(fileName));
+ bufferCache.createFile(firstFileRef);
+ int fileId = fmp.lookupFileId(firstFileRef);
+ bufferCache.openFile(fileId);
+
+ // Pin all pages.
+ ICachedPage[] pages = new ICachedPage[numPages];
+ for (int i = 0; i < numPages; ++i) {
+ pages[i] = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, i), true);
+ }
+
+ // Try to pin another page. We expect a HyracksDataException.
+ ICachedPage errorPage = null;
+ try {
+ errorPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, numPages), true);
+ } catch (HyracksDataException e) {
+ // This is the expected outcome.
+ // The BufferCache should still be able to function properly.
+ // Try unpinning all pages.
+ for (int i = 0; i < numPages; ++i) {
+ bufferCache.unpin(pages[i]);
+ }
+ // Now try pinning the page that failed above again.
+ errorPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, numPages), true);
+ // Unpin it.
+ bufferCache.unpin(errorPage);
+ // Cleanup.
+ bufferCache.closeFile(fileId);
+ bufferCache.close();
+ return;
+ } catch (Exception e) {
+ fail("Expected a HyracksDataException when pinning more pages than available but got another exception: "
+ + e.getMessage());
+ }
+ fail("Expected a HyracksDataException when pinning more pages than available.");
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/src/test/java/edu/uci/ics/hyracks/storage/common/BufferCacheTest.java b/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/src/test/java/edu/uci/ics/hyracks/storage/common/BufferCacheTest.java
new file mode 100644
index 0000000..80502eb
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/hyracks-storage-common-test/src/test/java/edu/uci/ics/hyracks/storage/common/BufferCacheTest.java
@@ -0,0 +1,310 @@
+package edu.uci.ics.hyracks.storage.common;
+
+import java.io.File;
+import java.text.SimpleDateFormat;
+import java.util.ArrayList;
+import java.util.Date;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Random;
+
+import org.junit.AfterClass;
+import org.junit.Assert;
+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.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class BufferCacheTest {
+ protected static final List<String> openedFiles = new ArrayList<String>();
+ protected static final SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
+ protected static final String tmpDir = System.getProperty("java.io.tmpdir");
+ protected static final String sep = System.getProperty("file.separator");
+
+ private static final int PAGE_SIZE = 256;
+ private static final int NUM_PAGES = 10;
+ private static final int MAX_OPEN_FILES = 20;
+ private static final int HYRACKS_FRAME_SIZE = PAGE_SIZE;
+ private IHyracksTaskContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+ private static final Random rnd = new Random(50);
+
+ private String getFileName() {
+ String fileName = tmpDir + sep + simpleDateFormat.format(new Date()) + openedFiles.size();
+ openedFiles.add(fileName);
+ return fileName;
+ }
+
+ @Test
+ public void simpleOpenPinCloseTest() throws HyracksDataException {
+ TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+ IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+ String fileName = getFileName();
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ int fileId = fmp.lookupFileId(file);
+ int num = 10;
+ int testPageId = 0;
+
+ bufferCache.openFile(fileId);
+
+ ICachedPage page = null;
+
+ // tryPin should fail
+ page = bufferCache.tryPin(BufferedFileHandle.getDiskPageId(fileId, testPageId));
+ Assert.assertNull(page);
+
+ // pin page should succeed
+ page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, testPageId), true);
+ page.acquireWriteLatch();
+ try {
+ for (int i = 0; i < num; i++) {
+ page.getBuffer().putInt(i * 4, i);
+ }
+
+ // try pin should succeed
+ ICachedPage page2 = bufferCache.tryPin(BufferedFileHandle.getDiskPageId(fileId, testPageId));
+ Assert.assertNotNull(page2);
+ bufferCache.unpin(page2);
+
+ } finally {
+ page.releaseWriteLatch();
+ bufferCache.unpin(page);
+ }
+
+ bufferCache.closeFile(fileId);
+
+ boolean exceptionThrown = false;
+
+ // tryPin should fail since file is not open
+ try {
+ page = bufferCache.tryPin(BufferedFileHandle.getDiskPageId(fileId, testPageId));
+ } catch (HyracksDataException e) {
+ exceptionThrown = true;
+ }
+ Assert.assertTrue(exceptionThrown);
+
+ // pin should fail since file is not open
+ exceptionThrown = false;
+ try {
+ page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, testPageId), false);
+ } catch (HyracksDataException e) {
+ exceptionThrown = true;
+ }
+ Assert.assertTrue(exceptionThrown);
+
+ // open file again
+ bufferCache.openFile(fileId);
+
+ // tryPin should succeed because page should still be cached
+ page = bufferCache.tryPin(BufferedFileHandle.getDiskPageId(fileId, testPageId));
+ Assert.assertNotNull(page);
+ page.acquireReadLatch();
+ try {
+ // verify contents of page
+ for (int i = 0; i < num; i++) {
+ Assert.assertEquals(page.getBuffer().getInt(i * 4), i);
+ }
+ } finally {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ }
+
+ bufferCache.closeFile(fileId);
+ bufferCache.close();
+ }
+
+ @Test
+ public void simpleMaxOpenFilesTest() throws HyracksDataException {
+ TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+ IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+
+ List<Integer> fileIds = new ArrayList<Integer>();
+
+ for (int i = 0; i < MAX_OPEN_FILES; i++) {
+ String fileName = getFileName();
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ int fileId = fmp.lookupFileId(file);
+ bufferCache.openFile(fileId);
+ fileIds.add(fileId);
+ }
+
+ boolean exceptionThrown = false;
+
+ // since all files are open, next open should fail
+ try {
+ String fileName = getFileName();
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ int fileId = fmp.lookupFileId(file);
+ bufferCache.openFile(fileId);
+ } catch (HyracksDataException e) {
+ exceptionThrown = true;
+ }
+ Assert.assertTrue(exceptionThrown);
+
+ // close a random file
+ int ix = Math.abs(rnd.nextInt()) % fileIds.size();
+ bufferCache.closeFile(fileIds.get(ix));
+ fileIds.remove(ix);
+
+ // now open should succeed again
+ exceptionThrown = false;
+ try {
+ String fileName = getFileName();
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ int fileId = fmp.lookupFileId(file);
+ bufferCache.openFile(fileId);
+ fileIds.add(fileId);
+
+ } catch (HyracksDataException e) {
+ exceptionThrown = true;
+ }
+ Assert.assertFalse(exceptionThrown);
+
+ for (Integer i : fileIds) {
+ bufferCache.closeFile(i.intValue());
+ }
+
+ bufferCache.close();
+ }
+
+ @Test
+ public void contentCheckingMaxOpenFilesTest() throws HyracksDataException {
+ TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+ IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+
+ List<Integer> fileIds = new ArrayList<Integer>();
+ Map<Integer, ArrayList<Integer>> pageContents = new HashMap<Integer, ArrayList<Integer>>();
+ int num = 10;
+ int testPageId = 0;
+
+ // open max number of files and write some stuff into their first page
+ for (int i = 0; i < MAX_OPEN_FILES; i++) {
+ String fileName = getFileName();
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ int fileId = fmp.lookupFileId(file);
+ bufferCache.openFile(fileId);
+ fileIds.add(fileId);
+
+ ICachedPage page = null;
+ page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, testPageId), true);
+ page.acquireWriteLatch();
+ try {
+ ArrayList<Integer> values = new ArrayList<Integer>();
+ for (int j = 0; j < num; j++) {
+ int x = Math.abs(rnd.nextInt());
+ page.getBuffer().putInt(j * 4, x);
+ values.add(x);
+ }
+ pageContents.put(fileId, values);
+ } finally {
+ page.releaseWriteLatch();
+ bufferCache.unpin(page);
+ }
+ }
+
+ boolean exceptionThrown = false;
+
+ // since all files are open, next open should fail
+ try {
+ String fileName = getFileName();
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ int fileId = fmp.lookupFileId(file);
+ bufferCache.openFile(fileId);
+ } catch (HyracksDataException e) {
+ exceptionThrown = true;
+ }
+ Assert.assertTrue(exceptionThrown);
+
+ // close a few random files
+ ArrayList<Integer> closedFileIds = new ArrayList<Integer>();
+ int filesToClose = 5;
+ for (int i = 0; i < filesToClose; i++) {
+ int ix = Math.abs(rnd.nextInt()) % fileIds.size();
+ bufferCache.closeFile(fileIds.get(ix));
+ closedFileIds.add(fileIds.get(ix));
+ fileIds.remove(ix);
+ }
+
+ // now open a few new files
+ for (int i = 0; i < filesToClose; i++) {
+ String fileName = getFileName();
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ int fileId = fmp.lookupFileId(file);
+ bufferCache.openFile(fileId);
+ fileIds.add(fileId);
+ }
+
+ // since all files are open, next open should fail
+ try {
+ String fileName = getFileName();
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ int fileId = fmp.lookupFileId(file);
+ bufferCache.openFile(fileId);
+ } catch (HyracksDataException e) {
+ exceptionThrown = true;
+ }
+ Assert.assertTrue(exceptionThrown);
+
+ // close a few random files again
+ for (int i = 0; i < filesToClose; i++) {
+ int ix = Math.abs(rnd.nextInt()) % fileIds.size();
+ bufferCache.closeFile(fileIds.get(ix));
+ closedFileIds.add(fileIds.get(ix));
+ fileIds.remove(ix);
+ }
+
+ // now open those closed files again and verify their contents
+ for (int i = 0; i < filesToClose; i++) {
+ int closedFileId = closedFileIds.get(i);
+ bufferCache.openFile(closedFileId);
+ fileIds.add(closedFileId);
+
+ // pin first page and verify contents
+ ICachedPage page = null;
+ page = bufferCache.pin(BufferedFileHandle.getDiskPageId(closedFileId, testPageId), false);
+ page.acquireReadLatch();
+ try {
+ ArrayList<Integer> values = pageContents.get(closedFileId);
+ for (int j = 0; j < values.size(); j++) {
+ Assert.assertEquals(values.get(j).intValue(), page.getBuffer().getInt(j * 4));
+ }
+ } finally {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ }
+ }
+
+ for (Integer i : fileIds) {
+ bufferCache.closeFile(i.intValue());
+ }
+
+ bufferCache.close();
+ }
+
+ @AfterClass
+ public static void cleanup() throws Exception {
+ for (String s : openedFiles) {
+ File f = new File(s);
+ f.deleteOnExit();
+ }
+ }
+}
diff --git a/fullstack/hyracks/hyracks-tests/pom.xml b/fullstack/hyracks/hyracks-tests/pom.xml
new file mode 100644
index 0000000..cc5d7bc
--- /dev/null
+++ b/fullstack/hyracks/hyracks-tests/pom.xml
@@ -0,0 +1,21 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-tests</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <packaging>pom</packaging>
+ <name>hyracks-tests</name>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ </parent>
+
+ <modules>
+ <module>hyracks-storage-common-test</module>
+ <module>hyracks-storage-am-btree-test</module>
+ <module>hyracks-storage-am-invertedindex-test</module>
+ <module>hyracks-storage-am-rtree-test</module>
+ </modules>
+</project>