merged hyracks_lsm_tree and fullstack_asterix_stabilization
git-svn-id: https://hyracks.googlecode.com/svn/branches/fullstack_lsm_staging@3026 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/pom.xml b/hyracks/hyracks-storage-am-lsm-rtree/pom.xml
new file mode 100644
index 0000000..4b2ce55
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/pom.xml
@@ -0,0 +1,47 @@
+<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>
+ <artifactId>hyracks-storage-am-lsm-rtree</artifactId>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks</artifactId>
+ <version>0.2.3-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.7</source>
+ <target>1.7</target>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+ <dependencies>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-lsm-common</artifactId>
+ <version>0.2.3-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-btree</artifactId>
+ <version>0.2.3-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-rtree</artifactId>
+ <version>0.2.3-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ </dependencies>
+</project>
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/AbstractLSMRTreeDataflowHelper.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/AbstractLSMRTreeDataflowHelper.java
new file mode 100644
index 0000000..c363c99
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/AbstractLSMRTreeDataflowHelper.java
@@ -0,0 +1,98 @@
+/*
+ * 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.lsm.rtree.dataflow;
+
+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.ILinearizeComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.api.io.IIOManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IInMemoryFreePageManager;
+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.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.AbstractTreeIndexOperatorDescriptor;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.IIndexOperatorDescriptor;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.IInMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallbackProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationScheduler;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMMergePolicy;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMOperationTrackerFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.dataflow.AbstractLSMIndexDataflowHelper;
+import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.DualIndexInMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.DualIndexInMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreePolicyType;
+import edu.uci.ics.hyracks.storage.common.buffercache.HeapBufferAllocator;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public abstract class AbstractLSMRTreeDataflowHelper extends AbstractLSMIndexDataflowHelper {
+
+ protected final IBinaryComparatorFactory[] btreeComparatorFactories;
+ protected final IPrimitiveValueProviderFactory[] valueProviderFactories;
+ protected final RTreePolicyType rtreePolicyType;
+ protected final ILinearizeComparatorFactory linearizeCmpFactory;
+
+ public AbstractLSMRTreeDataflowHelper(IIndexOperatorDescriptor opDesc, IHyracksTaskContext ctx, int partition,
+ IBinaryComparatorFactory[] btreeComparatorFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILSMMergePolicy mergePolicy, ILSMOperationTrackerFactory opTrackerFactory,
+ ILSMIOOperationScheduler ioScheduler, ILSMIOOperationCallbackProvider ioOpCallbackProvider,
+ ILinearizeComparatorFactory linearizeCmpFactory) {
+ this(opDesc, ctx, partition, DEFAULT_MEM_PAGE_SIZE, DEFAULT_MEM_NUM_PAGES, btreeComparatorFactories,
+ valueProviderFactories, rtreePolicyType, mergePolicy, opTrackerFactory, ioScheduler,
+ ioOpCallbackProvider, linearizeCmpFactory);
+ }
+
+ public AbstractLSMRTreeDataflowHelper(IIndexOperatorDescriptor opDesc, IHyracksTaskContext ctx, int partition,
+ int memPageSize, int memNumPages, IBinaryComparatorFactory[] btreeComparatorFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILSMMergePolicy mergePolicy, ILSMOperationTrackerFactory opTrackerFactory,
+ ILSMIOOperationScheduler ioScheduler, ILSMIOOperationCallbackProvider ioOpCallbackProvider,
+ ILinearizeComparatorFactory linearizeCmpFactory) {
+ super(opDesc, ctx, partition, memPageSize, memNumPages, mergePolicy, opTrackerFactory, ioScheduler,
+ ioOpCallbackProvider);
+ this.btreeComparatorFactories = btreeComparatorFactories;
+ this.valueProviderFactories = valueProviderFactories;
+ this.rtreePolicyType = rtreePolicyType;
+ this.linearizeCmpFactory = linearizeCmpFactory;
+ }
+
+ @Override
+ public ITreeIndex createIndexInstance() throws HyracksDataException {
+ AbstractTreeIndexOperatorDescriptor treeOpDesc = (AbstractTreeIndexOperatorDescriptor) opDesc;
+ ITreeIndexMetaDataFrameFactory metaDataFrameFactory = new LIFOMetaDataFrameFactory();
+ IInMemoryBufferCache memBufferCache = new DualIndexInMemoryBufferCache(new HeapBufferAllocator(), memPageSize,
+ memNumPages);
+ IInMemoryFreePageManager memFreePageManager = new DualIndexInMemoryFreePageManager(memNumPages,
+ metaDataFrameFactory);
+ return createLSMTree(memBufferCache, memFreePageManager, ctx.getIOManager(), file, opDesc.getStorageManager()
+ .getBufferCache(ctx), opDesc.getStorageManager().getFileMapProvider(ctx),
+ treeOpDesc.getTreeIndexTypeTraits(), treeOpDesc.getTreeIndexComparatorFactories(),
+ btreeComparatorFactories, valueProviderFactories, rtreePolicyType, linearizeCmpFactory, partition);
+
+ }
+
+ protected abstract ITreeIndex createLSMTree(IInMemoryBufferCache memBufferCache,
+ IInMemoryFreePageManager memFreePageManager, IIOManager ioManager, FileReference file,
+ IBufferCache diskBufferCache, IFileMapProvider diskFileMapProvider, ITypeTraits[] typeTraits,
+ IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILinearizeComparatorFactory linearizeCmpFactory, int startIODeviceIndex) throws HyracksDataException;
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/LSMRTreeDataflowHelper.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/LSMRTreeDataflowHelper.java
new file mode 100644
index 0000000..1df914e
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/LSMRTreeDataflowHelper.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright 2009-2012 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.lsm.rtree.dataflow;
+
+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.ILinearizeComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.api.io.IIOManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IInMemoryFreePageManager;
+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.common.dataflow.IIndexOperatorDescriptor;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.IInMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallbackProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationScheduler;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMMergePolicy;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMOperationTrackerFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.utils.LSMRTreeUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreePolicyType;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public class LSMRTreeDataflowHelper extends AbstractLSMRTreeDataflowHelper {
+
+ public LSMRTreeDataflowHelper(IIndexOperatorDescriptor opDesc, IHyracksTaskContext ctx, int partition,
+ IBinaryComparatorFactory[] btreeComparatorFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILSMMergePolicy mergePolicy, ILSMOperationTrackerFactory opTrackerFactory,
+ ILSMIOOperationScheduler ioScheduler, ILSMIOOperationCallbackProvider ioOpCallbackProvider,
+ ILinearizeComparatorFactory linearizeCmpFactory) {
+ super(opDesc, ctx, partition, btreeComparatorFactories, valueProviderFactories, rtreePolicyType, mergePolicy,
+ opTrackerFactory, ioScheduler, ioOpCallbackProvider, linearizeCmpFactory);
+ }
+
+ public LSMRTreeDataflowHelper(IIndexOperatorDescriptor opDesc, IHyracksTaskContext ctx, int partition,
+ int memPageSize, int memNumPages, IBinaryComparatorFactory[] btreeComparatorFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILSMMergePolicy mergePolicy, ILSMOperationTrackerFactory opTrackerFactory,
+ ILSMIOOperationScheduler ioScheduler, ILSMIOOperationCallbackProvider ioOpCallbackProvider,
+ ILinearizeComparatorFactory linearizeCmpFactory) {
+ super(opDesc, ctx, partition, memPageSize, memNumPages, btreeComparatorFactories, valueProviderFactories,
+ rtreePolicyType, mergePolicy, opTrackerFactory, ioScheduler, ioOpCallbackProvider, linearizeCmpFactory);
+ }
+
+ @Override
+ protected ITreeIndex createLSMTree(IInMemoryBufferCache memBufferCache,
+ IInMemoryFreePageManager memFreePageManager, IIOManager ioManager, FileReference file,
+ IBufferCache diskBufferCache, IFileMapProvider diskFileMapProvider, ITypeTraits[] typeTraits,
+ IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILinearizeComparatorFactory linearizeCmpFactory, int startIODeviceIndex) throws HyracksDataException {
+ try {
+ return LSMRTreeUtils.createLSMTree(memBufferCache, memFreePageManager, ioManager, file, diskBufferCache,
+ diskFileMapProvider, typeTraits, rtreeCmpFactories, btreeCmpFactories, valueProviderFactories,
+ rtreePolicyType, mergePolicy, opTrackerFactory, ioScheduler, ioOpCallbackProvider,
+ linearizeCmpFactory, startIODeviceIndex);
+ } catch (TreeIndexException e) {
+ throw new HyracksDataException(e);
+ }
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/LSMRTreeDataflowHelperFactory.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/LSMRTreeDataflowHelperFactory.java
new file mode 100644
index 0000000..a730895
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/LSMRTreeDataflowHelperFactory.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.lsm.rtree.dataflow;
+
+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.ILinearizeComparatorFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.IIndexOperatorDescriptor;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.IndexDataflowHelper;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallbackProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationSchedulerProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMMergePolicyProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMOperationTrackerFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.dataflow.AbstractLSMIndexDataflowHelperFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreePolicyType;
+
+public class LSMRTreeDataflowHelperFactory extends AbstractLSMIndexDataflowHelperFactory {
+
+ private static final long serialVersionUID = 1L;
+
+ private final IBinaryComparatorFactory[] btreeComparatorFactories;
+ private final IPrimitiveValueProviderFactory[] valueProviderFactories;
+ private final RTreePolicyType rtreePolicyType;
+ private final ILinearizeComparatorFactory linearizeCmpFactory;
+
+ public LSMRTreeDataflowHelperFactory(IPrimitiveValueProviderFactory[] valueProviderFactories,
+ RTreePolicyType rtreePolicyType, IBinaryComparatorFactory[] btreeComparatorFactories,
+ ILSMMergePolicyProvider mergePolicyProvider, ILSMOperationTrackerFactory opTrackerFactory,
+ ILSMIOOperationSchedulerProvider ioSchedulerProvider, ILSMIOOperationCallbackProvider ioOpCallbackProvider,
+ ILinearizeComparatorFactory linearizeCmpFactory, int memPageSize, int memNumPages) {
+ super(mergePolicyProvider, opTrackerFactory, ioSchedulerProvider, ioOpCallbackProvider, memPageSize,
+ memNumPages);
+ this.btreeComparatorFactories = btreeComparatorFactories;
+ this.valueProviderFactories = valueProviderFactories;
+ this.rtreePolicyType = rtreePolicyType;
+ this.linearizeCmpFactory = linearizeCmpFactory;
+ }
+
+ @Override
+ public IndexDataflowHelper createIndexDataflowHelper(IIndexOperatorDescriptor opDesc, IHyracksTaskContext ctx,
+ int partition) {
+ return new LSMRTreeDataflowHelper(opDesc, ctx, partition, memPageSize, memNumPages, btreeComparatorFactories, valueProviderFactories,
+ rtreePolicyType, mergePolicyProvider.getMergePolicy(ctx), opTrackerFactory,
+ ioSchedulerProvider.getIOScheduler(ctx), ioOpCallbackProvider, linearizeCmpFactory);
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/LSMRTreeWithAntiMatterTuplesDataflowHelper.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/LSMRTreeWithAntiMatterTuplesDataflowHelper.java
new file mode 100644
index 0000000..6f5ecb1
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/LSMRTreeWithAntiMatterTuplesDataflowHelper.java
@@ -0,0 +1,77 @@
+/*
+ * 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.lsm.rtree.dataflow;
+
+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.ILinearizeComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.api.io.IIOManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IInMemoryFreePageManager;
+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.common.dataflow.IIndexOperatorDescriptor;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.IInMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallbackProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationScheduler;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMMergePolicy;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMOperationTrackerFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.utils.LSMRTreeUtils;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreePolicyType;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public class LSMRTreeWithAntiMatterTuplesDataflowHelper extends AbstractLSMRTreeDataflowHelper {
+ public LSMRTreeWithAntiMatterTuplesDataflowHelper(IIndexOperatorDescriptor opDesc, IHyracksTaskContext ctx,
+ int partition, IBinaryComparatorFactory[] btreeComparatorFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILSMMergePolicy mergePolicy, ILSMOperationTrackerFactory opTrackerFactory,
+ ILSMIOOperationScheduler ioScheduler, ILSMIOOperationCallbackProvider ioOpCallbackProvider,
+ ILinearizeComparatorFactory linearizeCmpFactory) {
+ super(opDesc, ctx, partition, btreeComparatorFactories, valueProviderFactories, rtreePolicyType, mergePolicy,
+ opTrackerFactory, ioScheduler, ioOpCallbackProvider, linearizeCmpFactory);
+ }
+
+ public LSMRTreeWithAntiMatterTuplesDataflowHelper(IIndexOperatorDescriptor opDesc, IHyracksTaskContext ctx,
+ int partition, int memPageSize, int memNumPages, IBinaryComparatorFactory[] btreeComparatorFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILSMMergePolicy mergePolicy, ILSMOperationTrackerFactory opTrackerFactory,
+ ILSMIOOperationScheduler ioScheduler, ILSMIOOperationCallbackProvider ioOpCallbackProvider,
+ ILinearizeComparatorFactory linearizeCmpFactory) {
+ super(opDesc, ctx, partition, memPageSize, memNumPages, btreeComparatorFactories, valueProviderFactories,
+ rtreePolicyType, mergePolicy, opTrackerFactory, ioScheduler, ioOpCallbackProvider, linearizeCmpFactory);
+ }
+
+ @Override
+ protected ITreeIndex createLSMTree(IInMemoryBufferCache memBufferCache,
+ IInMemoryFreePageManager memFreePageManager, IIOManager ioManager, FileReference file,
+ IBufferCache diskBufferCache, IFileMapProvider diskFileMapProvider, ITypeTraits[] typeTraits,
+ IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILinearizeComparatorFactory linearizeCmpFactory, int startIODeviceIndex) throws HyracksDataException {
+ try {
+ return LSMRTreeUtils.createLSMTreeWithAntiMatterTuples(memBufferCache, memFreePageManager, ioManager, file,
+ diskBufferCache, diskFileMapProvider, typeTraits, rtreeCmpFactories, btreeCmpFactories,
+ valueProviderFactories, rtreePolicyType, mergePolicy, opTrackerFactory, ioScheduler,
+ ioOpCallbackProvider, linearizeCmpFactory, startIODeviceIndex);
+ } catch (TreeIndexException e) {
+ throw new HyracksDataException(e);
+ }
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/LSMRTreeWithAntiMatterTuplesDataflowHelperFactory.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/LSMRTreeWithAntiMatterTuplesDataflowHelperFactory.java
new file mode 100644
index 0000000..b27e84f
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/dataflow/LSMRTreeWithAntiMatterTuplesDataflowHelperFactory.java
@@ -0,0 +1,66 @@
+/*
+ * 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.lsm.rtree.dataflow;
+
+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.ILinearizeComparatorFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.IIndexDataflowHelperFactory;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.IIndexOperatorDescriptor;
+import edu.uci.ics.hyracks.storage.am.common.dataflow.IndexDataflowHelper;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallbackProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationSchedulerProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMMergePolicyProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMOperationTrackerFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreePolicyType;
+
+public class LSMRTreeWithAntiMatterTuplesDataflowHelperFactory implements IIndexDataflowHelperFactory {
+
+ private static final long serialVersionUID = 1L;
+
+ private final IBinaryComparatorFactory[] btreeComparatorFactories;
+ private final IPrimitiveValueProviderFactory[] valueProviderFactories;
+ private final RTreePolicyType rtreePolicyType;
+ private final ILSMMergePolicyProvider mergePolicyProvider;
+ private final ILSMOperationTrackerFactory opTrackerProvider;
+ private final ILSMIOOperationSchedulerProvider ioSchedulerProvider;
+ private final ILSMIOOperationCallbackProvider ioOpCallbackProvider;
+ private final ILinearizeComparatorFactory linearizeCmpFactory;
+
+ public LSMRTreeWithAntiMatterTuplesDataflowHelperFactory(IPrimitiveValueProviderFactory[] valueProviderFactories,
+ RTreePolicyType rtreePolicyType, IBinaryComparatorFactory[] btreeComparatorFactories,
+ ILSMMergePolicyProvider mergePolicyProvider, ILSMOperationTrackerFactory opTrackerProvider,
+ ILSMIOOperationSchedulerProvider ioSchedulerProvider, ILSMIOOperationCallbackProvider ioOpCallbackProvider,
+ ILinearizeComparatorFactory linearizeCmpFactory) {
+ this.btreeComparatorFactories = btreeComparatorFactories;
+ this.valueProviderFactories = valueProviderFactories;
+ this.rtreePolicyType = rtreePolicyType;
+ this.mergePolicyProvider = mergePolicyProvider;
+ this.ioSchedulerProvider = ioSchedulerProvider;
+ this.opTrackerProvider = opTrackerProvider;
+ this.ioOpCallbackProvider = ioOpCallbackProvider;
+ this.linearizeCmpFactory = linearizeCmpFactory;
+ }
+
+ @Override
+ public IndexDataflowHelper createIndexDataflowHelper(IIndexOperatorDescriptor opDesc, IHyracksTaskContext ctx,
+ int partition) {
+ return new LSMRTreeWithAntiMatterTuplesDataflowHelper(opDesc, ctx, partition, btreeComparatorFactories,
+ valueProviderFactories, rtreePolicyType, mergePolicyProvider.getMergePolicy(ctx), opTrackerProvider,
+ ioSchedulerProvider.getIOScheduler(ctx), ioOpCallbackProvider, linearizeCmpFactory);
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/AbstractLSMRTree.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/AbstractLSMRTree.java
new file mode 100644
index 0000000..23137ab
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/AbstractLSMRTree.java
@@ -0,0 +1,357 @@
+/*
+ * 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.lsm.rtree.impls;
+
+import java.io.File;
+import java.util.List;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparatorFactory;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+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.impls.BTree;
+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.IInMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexOperationContext;
+import edu.uci.ics.hyracks.storage.am.common.api.IModificationOperationCallback;
+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.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOperation;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.IInMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponent;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponentFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallbackProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationScheduler;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexFileManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMMergePolicy;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMOperationTrackerFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.AbstractLSMIndex;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.BlockingIOOperationCallbackWrapper;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMComponentFileReferences;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
+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.impls.RTree;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public abstract class AbstractLSMRTree extends AbstractLSMIndex implements ITreeIndex {
+
+ protected final ILinearizeComparatorFactory linearizer;
+ protected final int[] comparatorFields;
+ protected final IBinaryComparatorFactory[] linearizerArray;
+
+ // In-memory components.
+ protected final LSMRTreeMutableComponent mutableComponent;
+ protected final IInMemoryBufferCache memBufferCache;
+
+ protected TreeTupleSorter rTreeTupleSorter;
+
+ // On-disk components.
+ // For creating RTree's used in flush and merge.
+ protected final ILSMComponentFactory componentFactory;
+
+ private IBinaryComparatorFactory[] btreeCmpFactories;
+ private IBinaryComparatorFactory[] rtreeCmpFactories;
+
+ // Common for in-memory and on-disk components.
+ protected final ITreeIndexFrameFactory rtreeInteriorFrameFactory;
+ protected final ITreeIndexFrameFactory btreeInteriorFrameFactory;
+ protected final ITreeIndexFrameFactory rtreeLeafFrameFactory;
+ protected final ITreeIndexFrameFactory btreeLeafFrameFactory;
+
+ public AbstractLSMRTree(IInMemoryBufferCache memBufferCache, IInMemoryFreePageManager memFreePageManager,
+ ITreeIndexFrameFactory rtreeInteriorFrameFactory, ITreeIndexFrameFactory rtreeLeafFrameFactory,
+ ITreeIndexFrameFactory btreeInteriorFrameFactory, ITreeIndexFrameFactory btreeLeafFrameFactory,
+ ILSMIndexFileManager fileManager, TreeIndexFactory<RTree> diskRTreeFactory,
+ ILSMComponentFactory componentFactory, IFileMapProvider diskFileMapProvider, int fieldCount,
+ IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories,
+ ILinearizeComparatorFactory linearizer, int[] comparatorFields, IBinaryComparatorFactory[] linearizerArray,
+ ILSMMergePolicy mergePolicy, ILSMOperationTrackerFactory opTrackerFactory,
+ ILSMIOOperationScheduler ioScheduler, ILSMIOOperationCallbackProvider ioOpCallbackProvider) {
+ super(memFreePageManager, diskRTreeFactory.getBufferCache(), fileManager, diskFileMapProvider, mergePolicy,
+ opTrackerFactory, ioScheduler, ioOpCallbackProvider);
+ RTree memRTree = new RTree(memBufferCache, ((InMemoryBufferCache) memBufferCache).getFileMapProvider(),
+ memFreePageManager, rtreeInteriorFrameFactory, rtreeLeafFrameFactory, rtreeCmpFactories, fieldCount,
+ new FileReference(new File("memrtree")));
+ BTree memBTree = new BTree(memBufferCache, ((InMemoryBufferCache) memBufferCache).getFileMapProvider(),
+ memFreePageManager, btreeInteriorFrameFactory, btreeLeafFrameFactory, btreeCmpFactories, fieldCount,
+ new FileReference(new File("membtree")));
+ mutableComponent = new LSMRTreeMutableComponent(memRTree, memBTree, memFreePageManager);
+ this.memBufferCache = memBufferCache;
+ this.rtreeInteriorFrameFactory = rtreeInteriorFrameFactory;
+ this.rtreeLeafFrameFactory = rtreeLeafFrameFactory;
+ this.btreeInteriorFrameFactory = btreeInteriorFrameFactory;
+ this.btreeLeafFrameFactory = btreeLeafFrameFactory;
+ this.componentFactory = componentFactory;
+ this.btreeCmpFactories = btreeCmpFactories;
+ this.rtreeCmpFactories = rtreeCmpFactories;
+ this.linearizer = linearizer;
+ this.comparatorFields = comparatorFields;
+ this.linearizerArray = linearizerArray;
+ rTreeTupleSorter = null;
+ }
+
+ @Override
+ public synchronized void create() throws HyracksDataException {
+ if (isActivated) {
+ throw new HyracksDataException("Failed to create the index since it is activated.");
+ }
+
+ fileManager.deleteDirs();
+ fileManager.createDirs();
+ componentsRef.get().clear();
+ }
+
+ @Override
+ public synchronized void activate() throws HyracksDataException {
+ if (isActivated) {
+ return;
+ }
+
+ ((InMemoryBufferCache) mutableComponent.getRTree().getBufferCache()).open();
+ mutableComponent.getRTree().create();
+ mutableComponent.getBTree().create();
+ mutableComponent.getRTree().activate();
+ mutableComponent.getBTree().activate();
+ }
+
+ @Override
+ public synchronized void deactivate(boolean flushOnExit) throws HyracksDataException {
+ if (!isActivated) {
+ return;
+ }
+
+ if (flushOnExit) {
+ BlockingIOOperationCallbackWrapper cb = new BlockingIOOperationCallbackWrapper(
+ ioOpCallbackProvider.getIOOperationCallback(this));
+ ILSMIndexAccessor accessor = (ILSMIndexAccessor) createAccessor(NoOpOperationCallback.INSTANCE,
+ NoOpOperationCallback.INSTANCE);
+ accessor.scheduleFlush(cb);
+ try {
+ cb.waitForIO();
+ } catch (InterruptedException e) {
+ throw new HyracksDataException(e);
+ }
+ }
+
+ mutableComponent.getRTree().deactivate();
+ mutableComponent.getBTree().deactivate();
+ mutableComponent.getRTree().destroy();
+ mutableComponent.getBTree().destroy();
+ ((InMemoryBufferCache) mutableComponent.getRTree().getBufferCache()).close();
+ }
+
+ @Override
+ public synchronized void destroy() throws HyracksDataException {
+ if (isActivated) {
+ throw new HyracksDataException("Failed to destroy the index since it is activated.");
+ }
+
+ mutableComponent.getRTree().deactivate();
+ mutableComponent.getBTree().deactivate();
+ }
+
+ @Override
+ public synchronized void clear() throws HyracksDataException {
+ if (!isActivated) {
+ throw new HyracksDataException("Failed to clear the index since it is not activated.");
+ }
+
+ mutableComponent.getRTree().clear();
+ mutableComponent.getBTree().clear();
+ }
+
+ @Override
+ public void getOperationalComponents(ILSMIndexOperationContext ctx) {
+ List<ILSMComponent> operationalComponents = ctx.getComponentHolder();
+ operationalComponents.clear();
+ List<ILSMComponent> immutableComponents = componentsRef.get();
+ switch (ctx.getOperation()) {
+ case INSERT:
+ case DELETE:
+ case FLUSH:
+ operationalComponents.add(mutableComponent);
+ break;
+ case SEARCH:
+ operationalComponents.add(mutableComponent);
+ operationalComponents.addAll(immutableComponents);
+ break;
+ case MERGE:
+ operationalComponents.addAll(immutableComponents);
+ break;
+ default:
+ throw new UnsupportedOperationException("Operation " + ctx.getOperation() + " not supported.");
+ }
+ }
+
+ protected LSMComponentFileReferences getMergeTargetFileName(List<ILSMComponent> mergingDiskComponents)
+ throws HyracksDataException {
+ RTree firstTree = ((LSMRTreeImmutableComponent) mergingDiskComponents.get(0)).getRTree();
+ RTree lastTree = ((LSMRTreeImmutableComponent) mergingDiskComponents.get(mergingDiskComponents.size() - 1))
+ .getRTree();
+ FileReference firstFile = diskFileMapProvider.lookupFileName(firstTree.getFileId());
+ FileReference lastFile = diskFileMapProvider.lookupFileName(lastTree.getFileId());
+ LSMComponentFileReferences fileRefs = fileManager.getRelMergeFileReference(firstFile.getFile().getName(),
+ lastFile.getFile().getName());
+ return fileRefs;
+ }
+
+ protected LSMRTreeImmutableComponent createDiskComponent(ILSMComponentFactory factory, FileReference insertFileRef,
+ FileReference deleteFileRef, FileReference bloomFilterFileRef, boolean createComponent)
+ throws HyracksDataException, IndexException {
+ // Create new tree instance.
+ LSMRTreeImmutableComponent component = (LSMRTreeImmutableComponent) factory
+ .createLSMComponentInstance(new LSMComponentFileReferences(insertFileRef, deleteFileRef,
+ bloomFilterFileRef));
+ if (createComponent) {
+ component.getRTree().create();
+ if (component.getBTree() != null) {
+ component.getBTree().create();
+ component.getBloomFilter().create();
+ }
+ }
+ // Tree will be closed during cleanup of merge().
+ component.getRTree().activate();
+ if (component.getBTree() != null) {
+ component.getBTree().activate();
+ component.getBloomFilter().activate();
+ }
+ return component;
+ }
+
+ @Override
+ public ITreeIndexFrameFactory getLeafFrameFactory() {
+ return mutableComponent.getRTree().getLeafFrameFactory();
+ }
+
+ @Override
+ public ITreeIndexFrameFactory getInteriorFrameFactory() {
+ return mutableComponent.getRTree().getInteriorFrameFactory();
+ }
+
+ @Override
+ public IFreePageManager getFreePageManager() {
+ return mutableComponent.getRTree().getFreePageManager();
+ }
+
+ @Override
+ public int getFieldCount() {
+ return mutableComponent.getRTree().getFieldCount();
+ }
+
+ @Override
+ public int getRootPageId() {
+ return mutableComponent.getRTree().getRootPageId();
+ }
+
+ @Override
+ public int getFileId() {
+ return mutableComponent.getRTree().getFileId();
+ }
+
+ @Override
+ public void modify(IIndexOperationContext ictx, ITupleReference tuple) throws HyracksDataException, IndexException {
+ LSMRTreeOpContext ctx = (LSMRTreeOpContext) ictx;
+ if (ctx.getOperation() == IndexOperation.PHYSICALDELETE) {
+ throw new UnsupportedOperationException("Physical delete not supported in the LSM-RTree");
+ }
+
+ if (ctx.getOperation() == IndexOperation.INSERT) {
+ // Before each insert, we must check whether there exist a killer
+ // tuple in the memBTree. If we find a killer tuple, we must truly
+ // delete the existing tuple from the BTree, and then insert it to
+ // memRTree. Otherwise, the old killer tuple will kill the newly
+ // added RTree tuple.
+ RangePredicate btreeRangePredicate = new RangePredicate(tuple, tuple, true, true,
+ ctx.getBTreeMultiComparator(), ctx.getBTreeMultiComparator());
+ ITreeIndexCursor cursor = ctx.memBTreeAccessor.createSearchCursor();
+ ctx.memBTreeAccessor.search(cursor, btreeRangePredicate);
+ boolean foundTupleInMemoryBTree = false;
+ try {
+ if (cursor.hasNext()) {
+ foundTupleInMemoryBTree = true;
+ }
+ } finally {
+ cursor.close();
+ }
+ if (foundTupleInMemoryBTree) {
+ try {
+ ctx.memBTreeAccessor.delete(tuple);
+ } catch (BTreeNonExistentKeyException e) {
+ // Tuple has been deleted in the meantime. Do nothing.
+ // This normally shouldn't happen if we are dealing with
+ // good citizens since LSMRTree is used as a secondary
+ // index and a tuple shouldn't be deleted twice without
+ // insert between them.
+ }
+ } else {
+ ctx.memRTreeAccessor.insert(tuple);
+ }
+
+ } else {
+ try {
+ ctx.memBTreeAccessor.insert(tuple);
+ } catch (BTreeDuplicateKeyException e) {
+ // Do nothing, because one delete tuple is enough to indicate
+ // that all the corresponding insert tuples are deleted
+ }
+ }
+ }
+
+ protected LSMRTreeOpContext createOpContext(IModificationOperationCallback modCallback) {
+ return new LSMRTreeOpContext((RTree.RTreeAccessor) mutableComponent.getRTree().createAccessor(modCallback,
+ NoOpOperationCallback.INSTANCE), (IRTreeLeafFrame) rtreeLeafFrameFactory.createFrame(),
+ (IRTreeInteriorFrame) rtreeInteriorFrameFactory.createFrame(), memFreePageManager
+ .getMetaDataFrameFactory().createFrame(), 4, (BTree.BTreeAccessor) mutableComponent.getBTree()
+ .createAccessor(modCallback, NoOpOperationCallback.INSTANCE), btreeLeafFrameFactory,
+ btreeInteriorFrameFactory, memFreePageManager.getMetaDataFrameFactory().createFrame(),
+ rtreeCmpFactories, btreeCmpFactories, null, null);
+ }
+
+ @Override
+ public IBinaryComparatorFactory[] getComparatorFactories() {
+ return rtreeCmpFactories;
+ }
+
+ public boolean isEmptyIndex() throws HyracksDataException {
+ return componentsRef.get().isEmpty()
+ && mutableComponent.getBTree().isEmptyTree(
+ mutableComponent.getBTree().getInteriorFrameFactory().createFrame())
+ && mutableComponent.getRTree().isEmptyTree(
+ mutableComponent.getRTree().getInteriorFrameFactory().createFrame());
+ }
+
+ @Override
+ public void validate() throws HyracksDataException {
+ throw new UnsupportedOperationException("Validation not implemented for LSM R-Trees.");
+ }
+
+ @Override
+ public long getMemoryAllocationSize() {
+ InMemoryBufferCache memBufferCache = (InMemoryBufferCache) mutableComponent.getRTree().getBufferCache();
+ return memBufferCache.getNumPages() * memBufferCache.getPageSize();
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
new file mode 100644
index 0000000..3bffb43
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
@@ -0,0 +1,474 @@
+/*
+ * Copyright 2009-2012 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.lsm.rtree.impls;
+
+import java.util.List;
+import java.util.ListIterator;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparatorFactory;
+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.storage.am.bloomfilter.impls.BloomCalculations;
+import edu.uci.ics.hyracks.storage.am.bloomfilter.impls.BloomFilter;
+import edu.uci.ics.hyracks.storage.am.bloomfilter.impls.BloomFilterFactory;
+import edu.uci.ics.hyracks.storage.am.bloomfilter.impls.BloomFilterSpecification;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree.BTreeAccessor;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.IInMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoader;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.IModificationOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+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.IndexException;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOperation;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.IInMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponent;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMHarness;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperation;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallback;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallbackProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationScheduler;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexAccessorInternal;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexFileManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMMergePolicy;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMOperationTrackerFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMComponentFileReferences;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
+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.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public class LSMRTree extends AbstractLSMRTree {
+
+ public LSMRTree(IInMemoryBufferCache memBufferCache, IInMemoryFreePageManager memFreePageManager,
+ ITreeIndexFrameFactory rtreeInteriorFrameFactory, ITreeIndexFrameFactory rtreeLeafFrameFactory,
+ ITreeIndexFrameFactory btreeInteriorFrameFactory, ITreeIndexFrameFactory btreeLeafFrameFactory,
+ ILSMIndexFileManager fileNameManager, TreeIndexFactory<RTree> diskRTreeFactory,
+ TreeIndexFactory<BTree> diskBTreeFactory, BloomFilterFactory bloomFilterFactory,
+ IFileMapProvider diskFileMapProvider, int fieldCount, IBinaryComparatorFactory[] rtreeCmpFactories,
+ IBinaryComparatorFactory[] btreeCmpFactories, ILinearizeComparatorFactory linearizer,
+ int[] comparatorFields, IBinaryComparatorFactory[] linearizerArray, ILSMMergePolicy mergePolicy,
+ ILSMOperationTrackerFactory opTrackerFactory, ILSMIOOperationScheduler ioScheduler,
+ ILSMIOOperationCallbackProvider ioOpCallbackProvider) {
+ super(memBufferCache, memFreePageManager, rtreeInteriorFrameFactory, rtreeLeafFrameFactory,
+ btreeInteriorFrameFactory, btreeLeafFrameFactory, fileNameManager, diskRTreeFactory,
+ new LSMRTreeComponentFactory(diskRTreeFactory, diskBTreeFactory, bloomFilterFactory),
+ diskFileMapProvider, fieldCount, rtreeCmpFactories, btreeCmpFactories, linearizer, comparatorFields,
+ linearizerArray, mergePolicy, opTrackerFactory, ioScheduler, ioOpCallbackProvider);
+ }
+
+ /**
+ * Opens LSMRTree, cleaning up invalid files from base dir, and registering
+ * all valid files as on-disk RTrees and BTrees.
+ *
+ * @param fileReference
+ * Dummy file id.
+ * @throws HyracksDataException
+ */
+ @Override
+ public synchronized void activate() throws HyracksDataException {
+ super.activate();
+ List<ILSMComponent> immutableComponents = componentsRef.get();
+ List<LSMComponentFileReferences> validFileReferences;
+ try {
+ validFileReferences = fileManager.cleanupAndGetValidFiles();
+ } catch (IndexException e) {
+ throw new HyracksDataException(e);
+ }
+ immutableComponents.clear();
+ for (LSMComponentFileReferences lsmComonentFileReference : validFileReferences) {
+ LSMRTreeImmutableComponent component;
+ try {
+ component = createDiskComponent(componentFactory,
+ lsmComonentFileReference.getInsertIndexFileReference(),
+ lsmComonentFileReference.getDeleteIndexFileReference(),
+ lsmComonentFileReference.getBloomFilterFileReference(), false);
+ } catch (IndexException e) {
+ throw new HyracksDataException(e);
+ }
+ immutableComponents.add(component);
+ }
+ isActivated = true;
+ }
+
+ @Override
+ public synchronized void deactivate(boolean flushOnExit) throws HyracksDataException {
+ super.deactivate(flushOnExit);
+ List<ILSMComponent> immutableComponents = componentsRef.get();
+ for (ILSMComponent c : immutableComponents) {
+ LSMRTreeImmutableComponent component = (LSMRTreeImmutableComponent) c;
+ RTree rtree = component.getRTree();
+ BTree btree = component.getBTree();
+ BloomFilter bloomFilter = component.getBloomFilter();
+ rtree.deactivate();
+ btree.deactivate();
+ bloomFilter.deactivate();
+ }
+ isActivated = false;
+ }
+
+ @Override
+ public synchronized void deactivate() throws HyracksDataException {
+ deactivate(true);
+ }
+
+ @Override
+ public synchronized void destroy() throws HyracksDataException {
+ super.destroy();
+ List<ILSMComponent> immutableComponents = componentsRef.get();
+ for (ILSMComponent c : immutableComponents) {
+ LSMRTreeImmutableComponent component = (LSMRTreeImmutableComponent) c;
+ component.getBTree().destroy();
+ component.getBloomFilter().destroy();
+ component.getRTree().destroy();
+ }
+ fileManager.deleteDirs();
+ }
+
+ @Override
+ public synchronized void clear() throws HyracksDataException {
+ super.clear();
+ List<ILSMComponent> immutableComponents = componentsRef.get();
+ for (ILSMComponent c : immutableComponents) {
+ LSMRTreeImmutableComponent component = (LSMRTreeImmutableComponent) c;
+ component.getBTree().deactivate();
+ component.getBloomFilter().deactivate();
+ component.getRTree().deactivate();
+ component.getBTree().destroy();
+ component.getBloomFilter().destroy();
+ component.getRTree().destroy();
+ }
+ immutableComponents.clear();
+ }
+
+ @Override
+ public void search(ILSMIndexOperationContext ictx, IIndexCursor cursor, ISearchPredicate pred)
+ throws HyracksDataException, IndexException {
+ LSMRTreeOpContext ctx = (LSMRTreeOpContext) ictx;
+ List<ILSMComponent> operationalComponents = ctx.getComponentHolder();
+ boolean includeMutableComponent = operationalComponents.get(0) == mutableComponent;
+ int numTrees = operationalComponents.size();
+
+ ListIterator<ILSMComponent> diskComponentIter = operationalComponents.listIterator();
+ ITreeIndexAccessor[] rTreeAccessors = new ITreeIndexAccessor[numTrees];
+ ITreeIndexAccessor[] bTreeAccessors = new ITreeIndexAccessor[numTrees];
+ int diskComponentIx = 0;
+ if (includeMutableComponent) {
+ rTreeAccessors[0] = ctx.memRTreeAccessor;
+ bTreeAccessors[0] = ctx.memBTreeAccessor;
+ diskComponentIx++;
+ diskComponentIter.next();
+ }
+
+ while (diskComponentIter.hasNext()) {
+ LSMRTreeImmutableComponent component = (LSMRTreeImmutableComponent) diskComponentIter.next();
+ RTree diskRTree = component.getRTree();
+ BTree diskBTree = component.getBTree();
+ rTreeAccessors[diskComponentIx] = diskRTree.createAccessor(NoOpOperationCallback.INSTANCE,
+ NoOpOperationCallback.INSTANCE);
+ bTreeAccessors[diskComponentIx] = diskBTree.createAccessor(NoOpOperationCallback.INSTANCE,
+ NoOpOperationCallback.INSTANCE);
+ diskComponentIx++;
+ }
+
+ LSMRTreeCursorInitialState initialState = new LSMRTreeCursorInitialState(numTrees, rtreeLeafFrameFactory,
+ rtreeInteriorFrameFactory, btreeLeafFrameFactory, ctx.getBTreeMultiComparator(), rTreeAccessors,
+ bTreeAccessors, includeMutableComponent, lsmHarness, comparatorFields, linearizerArray,
+ ctx.searchCallback, operationalComponents);
+ cursor.open(initialState, pred);
+ }
+
+ @Override
+ public void scheduleFlush(ILSMIndexOperationContext ctx, ILSMIOOperationCallback callback)
+ throws HyracksDataException {
+ LSMComponentFileReferences componentFileRefs = fileManager.getRelFlushFileReference();
+ ILSMIndexOperationContext rctx = createOpContext(NoOpOperationCallback.INSTANCE);
+ LSMRTreeMutableComponent flushingComponent = (LSMRTreeMutableComponent) ctx.getComponentHolder().get(0);
+ rctx.setOperation(IndexOperation.FLUSH);
+ rctx.getComponentHolder().addAll(ctx.getComponentHolder());
+ LSMRTreeAccessor accessor = new LSMRTreeAccessor(lsmHarness, rctx);
+ ioScheduler.scheduleOperation(new LSMRTreeFlushOperation(accessor, flushingComponent, componentFileRefs
+ .getInsertIndexFileReference(), componentFileRefs.getDeleteIndexFileReference(), componentFileRefs
+ .getBloomFilterFileReference(), callback));
+ }
+
+ @Override
+ public ILSMComponent flush(ILSMIOOperation operation) throws HyracksDataException, IndexException {
+ LSMRTreeFlushOperation flushOp = (LSMRTreeFlushOperation) operation;
+ LSMRTreeMutableComponent flushingComponent = (LSMRTreeMutableComponent) flushOp.getFlushingComponent();
+ // Renaming order is critical because we use assume ordering when we
+ // read the file names when we open the tree.
+ // The RTree should be renamed before the BTree.
+
+ // scan the memory RTree
+ ITreeIndexAccessor memRTreeAccessor = flushingComponent.getRTree().createAccessor(
+ NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE);
+ RTreeSearchCursor rtreeScanCursor = (RTreeSearchCursor) memRTreeAccessor.createSearchCursor();
+ SearchPredicate rtreeNullPredicate = new SearchPredicate(null, null);
+ memRTreeAccessor.search(rtreeScanCursor, rtreeNullPredicate);
+ LSMRTreeImmutableComponent component = createDiskComponent(componentFactory, flushOp.getRTreeFlushTarget(),
+ flushOp.getBTreeFlushTarget(), flushOp.getBloomFilterFlushTarget(), true);
+ RTree diskRTree = component.getRTree();
+ IIndexBulkLoader rTreeBulkloader;
+ ITreeIndexCursor cursor;
+
+ IBinaryComparatorFactory[] linearizerArray = { linearizer };
+
+ if (rTreeTupleSorter == null) {
+ rTreeTupleSorter = new TreeTupleSorter(flushingComponent.getRTree().getFileId(), linearizerArray,
+ rtreeLeafFrameFactory.createFrame(), rtreeLeafFrameFactory.createFrame(), flushingComponent
+ .getRTree().getBufferCache(), comparatorFields);
+ } else {
+ rTreeTupleSorter.reset();
+ }
+ // BulkLoad the tuples from the in-memory tree into the new disk
+ // RTree.
+
+ boolean isEmpty = true;
+ try {
+ while (rtreeScanCursor.hasNext()) {
+ isEmpty = false;
+ rtreeScanCursor.next();
+ rTreeTupleSorter.insertTupleEntry(rtreeScanCursor.getPageId(), rtreeScanCursor.getTupleOffset());
+ }
+ } finally {
+ rtreeScanCursor.close();
+ }
+ if (!isEmpty) {
+ rTreeTupleSorter.sort();
+
+ rTreeBulkloader = diskRTree.createBulkLoader(1.0f, false, 0L);
+ cursor = rTreeTupleSorter;
+
+ try {
+ while (cursor.hasNext()) {
+ cursor.next();
+ ITupleReference frameTuple = cursor.getTuple();
+ rTreeBulkloader.add(frameTuple);
+ }
+ } finally {
+ cursor.close();
+ }
+ rTreeBulkloader.end();
+ }
+
+ ITreeIndexAccessor memBTreeAccessor = flushingComponent.getBTree().createAccessor(
+ NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE);
+ RangePredicate btreeNullPredicate = new RangePredicate(null, null, true, true, null, null);
+ IIndexCursor btreeCountingCursor = ((BTreeAccessor) memBTreeAccessor).createCountingSearchCursor();
+ memBTreeAccessor.search(btreeCountingCursor, btreeNullPredicate);
+ long numBTreeTuples = 0L;
+ try {
+ while (btreeCountingCursor.hasNext()) {
+ btreeCountingCursor.next();
+ ITupleReference countTuple = btreeCountingCursor.getTuple();
+ numBTreeTuples = IntegerSerializerDeserializer.getInt(countTuple.getFieldData(0),
+ countTuple.getFieldStart(0));
+ }
+ } finally {
+ btreeCountingCursor.close();
+ }
+
+ if (numBTreeTuples > 0) {
+ int maxBucketsPerElement = BloomCalculations.maxBucketsPerElement(numBTreeTuples);
+ BloomFilterSpecification bloomFilterSpec = BloomCalculations.computeBloomSpec(maxBucketsPerElement,
+ MAX_BLOOM_FILTER_ACCEPTABLE_FALSE_POSITIVE_RATE);
+
+ IIndexCursor btreeScanCursor = memBTreeAccessor.createSearchCursor();
+ memBTreeAccessor.search(btreeScanCursor, btreeNullPredicate);
+ BTree diskBTree = component.getBTree();
+
+ // BulkLoad the tuples from the in-memory tree into the new disk BTree.
+ IIndexBulkLoader bTreeBulkloader = diskBTree.createBulkLoader(1.0f, false, numBTreeTuples);
+ IIndexBulkLoader builder = component.getBloomFilter().createBuilder(numBTreeTuples,
+ bloomFilterSpec.getNumHashes(), bloomFilterSpec.getNumBucketsPerElements());
+ // scan the memory BTree
+ try {
+ while (btreeScanCursor.hasNext()) {
+ btreeScanCursor.next();
+ ITupleReference frameTuple = btreeScanCursor.getTuple();
+ bTreeBulkloader.add(frameTuple);
+ builder.add(frameTuple);
+ }
+ } finally {
+ btreeScanCursor.close();
+ builder.end();
+ }
+ bTreeBulkloader.end();
+ }
+
+ return component;
+ }
+
+ @Override
+ public void scheduleMerge(ILSMIndexOperationContext ctx, ILSMIOOperationCallback callback)
+ throws HyracksDataException, IndexException {
+ // Renaming order is critical because we use assume ordering when we
+ // read the file names when we open the tree.
+ // The RTree should be renamed before the BTree.
+ List<ILSMComponent> mergingComponents = ctx.getComponentHolder();
+ ILSMIndexOperationContext rctx = createOpContext(NoOpOperationCallback.INSTANCE);
+ rctx.getComponentHolder().addAll(mergingComponents);
+ ITreeIndexCursor cursor = new LSMRTreeSortedCursor(rctx, linearizer);
+ ISearchPredicate rtreeSearchPred = new SearchPredicate(null, null);
+ search(rctx, cursor, rtreeSearchPred);
+
+ rctx.setOperation(IndexOperation.MERGE);
+ LSMComponentFileReferences relMergeFileRefs = getMergeTargetFileName(mergingComponents);
+ ILSMIndexAccessorInternal accessor = new LSMRTreeAccessor(lsmHarness, rctx);
+ ioScheduler.scheduleOperation(new LSMRTreeMergeOperation((ILSMIndexAccessorInternal) accessor,
+ mergingComponents, cursor, relMergeFileRefs.getInsertIndexFileReference(), relMergeFileRefs
+ .getDeleteIndexFileReference(), relMergeFileRefs.getBloomFilterFileReference(), callback));
+ }
+
+ @Override
+ public ILSMComponent merge(List<ILSMComponent> mergedComponents, ILSMIOOperation operation)
+ throws HyracksDataException, IndexException {
+ LSMRTreeMergeOperation mergeOp = (LSMRTreeMergeOperation) operation;
+ ITreeIndexCursor cursor = mergeOp.getCursor();
+ mergedComponents.addAll(mergeOp.getMergingComponents());
+
+ LSMRTreeImmutableComponent mergedComponent = createDiskComponent(componentFactory,
+ mergeOp.getRTreeMergeTarget(), mergeOp.getBTreeMergeTarget(), mergeOp.getBloomFilterMergeTarget(), true);
+ IIndexBulkLoader bulkLoader = mergedComponent.getRTree().createBulkLoader(1.0f, false, 0L);
+
+ try {
+ while (cursor.hasNext()) {
+ cursor.next();
+ ITupleReference frameTuple = cursor.getTuple();
+ bulkLoader.add(frameTuple);
+ }
+ } finally {
+ cursor.close();
+ }
+ bulkLoader.end();
+ return mergedComponent;
+ }
+
+ @Override
+ public ILSMIndexAccessorInternal createAccessor(IModificationOperationCallback modificationCallback,
+ ISearchOperationCallback searchCallback) {
+ return new LSMRTreeAccessor(lsmHarness, createOpContext(modificationCallback));
+ }
+
+ public class LSMRTreeAccessor extends LSMTreeIndexAccessor {
+ public LSMRTreeAccessor(ILSMHarness lsmHarness, ILSMIndexOperationContext ctx) {
+ super(lsmHarness, ctx);
+ }
+
+ @Override
+ public ITreeIndexCursor createSearchCursor() {
+ return new LSMRTreeSearchCursor(ctx);
+ }
+
+ public MultiComparator getMultiComparator() {
+ LSMRTreeOpContext concreteCtx = (LSMRTreeOpContext) ctx;
+ return concreteCtx.rtreeOpContext.cmp;
+ }
+ }
+
+ private ILSMComponent createBulkLoadTarget() throws HyracksDataException, IndexException {
+ LSMComponentFileReferences componentFileRefs = fileManager.getRelFlushFileReference();
+ return createDiskComponent(componentFactory, componentFileRefs.getInsertIndexFileReference(),
+ componentFileRefs.getDeleteIndexFileReference(), componentFileRefs.getBloomFilterFileReference(), true);
+ }
+
+ @Override
+ public IIndexBulkLoader createBulkLoader(float fillLevel, boolean verifyInput, long numElementsHint)
+ throws TreeIndexException {
+ return new LSMRTreeBulkLoader(fillLevel, verifyInput, numElementsHint);
+ }
+
+ public class LSMRTreeBulkLoader implements IIndexBulkLoader {
+ private final ILSMComponent component;
+ private final IIndexBulkLoader bulkLoader;
+
+ public LSMRTreeBulkLoader(float fillFactor, boolean verifyInput, long numElementsHint)
+ throws TreeIndexException {
+ // Note that by using a flush target file name, we state that the
+ // new bulk loaded tree is "newer" than any other merged tree.
+ try {
+ component = createBulkLoadTarget();
+ } catch (HyracksDataException e) {
+ throw new TreeIndexException(e);
+ } catch (IndexException e) {
+ throw new TreeIndexException(e);
+ }
+ bulkLoader = ((LSMRTreeImmutableComponent) component).getRTree().createBulkLoader(fillFactor, verifyInput,
+ numElementsHint);
+ }
+
+ @Override
+ public void add(ITupleReference tuple) throws HyracksDataException, IndexException {
+ try {
+ bulkLoader.add(tuple);
+ } catch (IndexException e) {
+ handleException();
+ throw e;
+ } catch (HyracksDataException e) {
+ handleException();
+ throw e;
+ } catch (RuntimeException e) {
+ handleException();
+ throw e;
+ }
+ }
+
+ @Override
+ public void end() throws HyracksDataException, IndexException {
+ bulkLoader.end();
+ lsmHarness.addBulkLoadedComponent(component);
+ }
+
+ protected void handleException() throws HyracksDataException {
+ ((LSMRTreeImmutableComponent) component).getRTree().deactivate();
+ ((LSMRTreeImmutableComponent) component).getRTree().destroy();
+ ((LSMRTreeImmutableComponent) component).getBTree().deactivate();
+ ((LSMRTreeImmutableComponent) component).getBTree().destroy();
+ ((LSMRTreeImmutableComponent) component).getBloomFilter().deactivate();
+ ((LSMRTreeImmutableComponent) component).getBloomFilter().destroy();
+ }
+ }
+
+ @Override
+ public void markAsValid(ILSMComponent lsmComponent) throws HyracksDataException {
+ LSMRTreeImmutableComponent component = (LSMRTreeImmutableComponent) lsmComponent;
+ // Flush the bloom filter first.
+ int fileId = component.getBloomFilter().getFileId();
+ IBufferCache bufferCache = component.getBTree().getBufferCache();
+ int startPage = 0;
+ int maxPage = component.getBloomFilter().getNumPages();
+ forceFlushDirtyPages(bufferCache, fileId, startPage, maxPage);
+ forceFlushDirtyPages(component.getRTree());
+ markAsValidInternal(component.getRTree());
+ forceFlushDirtyPages(component.getBTree());
+ markAsValidInternal(component.getBTree());
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeAbstractCursor.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeAbstractCursor.java
new file mode 100644
index 0000000..5a72f29
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeAbstractCursor.java
@@ -0,0 +1,143 @@
+package edu.uci.ics.hyracks.storage.am.lsm.rtree.impls;
+
+import java.util.List;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponent;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMHarness;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.BloomFilterAwareBTreePointSearchCursor;
+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.impls.RTreeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public abstract class LSMRTreeAbstractCursor implements ITreeIndexCursor {
+
+ protected RTreeSearchCursor[] rtreeCursors;
+ protected boolean open = false;
+ protected ITreeIndexCursor[] btreeCursors;
+ protected ITreeIndexAccessor[] rTreeAccessors;
+ protected ITreeIndexAccessor[] bTreeAccessors;
+ private MultiComparator btreeCmp;
+ protected int numberOfTrees;
+ protected SearchPredicate rtreeSearchPredicate;
+ protected RangePredicate btreeRangePredicate;
+ protected ITupleReference frameTuple;
+ protected boolean includeMemRTree;
+ protected ILSMHarness lsmHarness;
+ protected boolean foundNext;
+ protected final ILSMIndexOperationContext opCtx;
+
+ protected List<ILSMComponent> operationalComponents;
+
+ public LSMRTreeAbstractCursor(ILSMIndexOperationContext opCtx) {
+ super();
+ this.opCtx = opCtx;
+ }
+
+ public RTreeSearchCursor getCursor(int cursorIndex) {
+ return rtreeCursors[cursorIndex];
+ }
+
+ @Override
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+ LSMRTreeCursorInitialState lsmInitialState = (LSMRTreeCursorInitialState) initialState;
+ btreeCmp = lsmInitialState.getBTreeCmp();
+ includeMemRTree = lsmInitialState.getIncludeMemComponent();
+ operationalComponents = lsmInitialState.getOperationalComponents();
+ lsmHarness = lsmInitialState.getLSMHarness();
+ numberOfTrees = lsmInitialState.getNumberOfTrees();
+ rTreeAccessors = lsmInitialState.getRTreeAccessors();
+ bTreeAccessors = lsmInitialState.getBTreeAccessors();
+
+ rtreeCursors = new RTreeSearchCursor[numberOfTrees];
+ btreeCursors = new ITreeIndexCursor[numberOfTrees];
+
+ int i = 0;
+ if (includeMemRTree) {
+ rtreeCursors[i] = new RTreeSearchCursor((IRTreeInteriorFrame) lsmInitialState
+ .getRTreeInteriorFrameFactory().createFrame(), (IRTreeLeafFrame) lsmInitialState
+ .getRTreeLeafFrameFactory().createFrame());
+
+ // No need for a bloom filter for the in-memory BTree.
+ btreeCursors[i] = new BTreeRangeSearchCursor((IBTreeLeafFrame) lsmInitialState.getBTreeLeafFrameFactory()
+ .createFrame(), false);
+ ++i;
+ }
+ for (; i < numberOfTrees; i++) {
+ rtreeCursors[i] = new RTreeSearchCursor((IRTreeInteriorFrame) lsmInitialState
+ .getRTreeInteriorFrameFactory().createFrame(), (IRTreeLeafFrame) lsmInitialState
+ .getRTreeLeafFrameFactory().createFrame());
+
+ btreeCursors[i] = new BloomFilterAwareBTreePointSearchCursor((IBTreeLeafFrame) lsmInitialState
+ .getBTreeLeafFrameFactory().createFrame(), false,
+ ((LSMRTreeImmutableComponent) operationalComponents.get(i)).getBloomFilter());
+ }
+
+ rtreeSearchPredicate = (SearchPredicate) searchPred;
+ btreeRangePredicate = new RangePredicate(null, null, true, true, btreeCmp, btreeCmp);
+
+ open = true;
+ }
+
+ @Override
+ public ICachedPage getPage() {
+ // do nothing
+ return null;
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ if (!open) {
+ return;
+ }
+
+ try {
+ if (rtreeCursors != null && btreeCursors != null) {
+ for (int i = 0; i < numberOfTrees; i++) {
+ rtreeCursors[i].close();
+ btreeCursors[i].close();
+ }
+ }
+ rtreeCursors = null;
+ btreeCursors = null;
+ } finally {
+ lsmHarness.endSearch(opCtx);
+ }
+
+ open = false;
+ }
+
+ @Override
+ public void setBufferCache(IBufferCache bufferCache) {
+ // do nothing
+ }
+
+ @Override
+ public void setFileId(int fileId) {
+ // do nothing
+ }
+
+ @Override
+ public ITupleReference getTuple() {
+ return frameTuple;
+ }
+
+ @Override
+ public boolean exclusiveLatchNodes() {
+ return false;
+ }
+
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeComponentFactory.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeComponentFactory.java
new file mode 100644
index 0000000..56e3d28
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeComponentFactory.java
@@ -0,0 +1,53 @@
+/*
+ * Copyright 2009-2012 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.lsm.rtree.impls;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.bloomfilter.impls.BloomFilterFactory;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponent;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponentFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMComponentFileReferences;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+public class LSMRTreeComponentFactory implements ILSMComponentFactory {
+ private final TreeIndexFactory<RTree> rtreeFactory;
+ private final TreeIndexFactory<BTree> btreeFactory;
+ private final BloomFilterFactory bloomFilterFactory;
+
+ public LSMRTreeComponentFactory(TreeIndexFactory<RTree> rtreeFactory, TreeIndexFactory<BTree> btreeFactory,
+ BloomFilterFactory bloomFilterFactory) {
+ this.rtreeFactory = rtreeFactory;
+ this.btreeFactory = btreeFactory;
+ this.bloomFilterFactory = bloomFilterFactory;
+ }
+
+ @Override
+ public ILSMComponent createLSMComponentInstance(LSMComponentFileReferences cfr) throws IndexException,
+ HyracksDataException {
+ return new LSMRTreeImmutableComponent(rtreeFactory.createIndexInstance(cfr.getInsertIndexFileReference()),
+ btreeFactory.createIndexInstance(cfr.getDeleteIndexFileReference()),
+ bloomFilterFactory.createBloomFiltertInstance(cfr.getBloomFilterFileReference()));
+ }
+
+ @Override
+ public IBufferCache getBufferCache() {
+ return rtreeFactory.getBufferCache();
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeCursorInitialState.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeCursorInitialState.java
new file mode 100644
index 0000000..590d5d8
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeCursorInitialState.java
@@ -0,0 +1,144 @@
+/*
+ * 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.lsm.rtree.impls;
+
+import java.util.List;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
+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.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponent;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMHarness;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public class LSMRTreeCursorInitialState implements ICursorInitialState {
+
+ private final int numberOfTrees;
+ private final ITreeIndexFrameFactory rtreeInteriorFrameFactory;
+ private final ITreeIndexFrameFactory rtreeLeafFrameFactory;
+ private final ITreeIndexFrameFactory btreeLeafFrameFactory;
+ private final MultiComparator btreeCmp;
+ private final MultiComparator hilbertCmp;
+ private final ITreeIndexAccessor[] rTreeAccessors;
+ private final ITreeIndexAccessor[] bTreeAccessors;
+ private final boolean includeMemRTree;
+ private final ILSMHarness lsmHarness;
+ private final int[] comparatorFields;
+
+ private ISearchOperationCallback searchCallback;
+ private final List<ILSMComponent> operationalComponents;
+
+ public LSMRTreeCursorInitialState(int numberOfTrees, ITreeIndexFrameFactory rtreeLeafFrameFactory,
+ ITreeIndexFrameFactory rtreeInteriorFrameFactory, ITreeIndexFrameFactory btreeLeafFrameFactory,
+ MultiComparator btreeCmp, ITreeIndexAccessor[] rTreeAccessors, ITreeIndexAccessor[] bTreeAccessors,
+ boolean includeMemRTree, ILSMHarness lsmHarness, int[] comparatorFields,
+ IBinaryComparatorFactory[] linearizerArray, ISearchOperationCallback searchCallback,
+ List<ILSMComponent> operationalComponents) {
+ this.numberOfTrees = numberOfTrees;
+ this.rtreeLeafFrameFactory = rtreeLeafFrameFactory;
+ this.rtreeInteriorFrameFactory = rtreeInteriorFrameFactory;
+ this.btreeLeafFrameFactory = btreeLeafFrameFactory;
+ this.btreeCmp = btreeCmp;
+ this.rTreeAccessors = rTreeAccessors;
+ this.bTreeAccessors = bTreeAccessors;
+ this.includeMemRTree = includeMemRTree;
+ this.lsmHarness = lsmHarness;
+ this.comparatorFields = comparatorFields;
+ this.hilbertCmp = MultiComparator.create(linearizerArray);
+ this.searchCallback = searchCallback;
+ this.operationalComponents = operationalComponents;
+ }
+
+ public MultiComparator getHilbertCmp() {
+ return hilbertCmp;
+ }
+
+ public int[] getComparatorFields() {
+ return comparatorFields;
+ }
+
+ public int getNumberOfTrees() {
+ return numberOfTrees;
+ }
+
+ public ITreeIndexFrameFactory getRTreeInteriorFrameFactory() {
+ return rtreeInteriorFrameFactory;
+ }
+
+ public ITreeIndexFrameFactory getRTreeLeafFrameFactory() {
+ return rtreeLeafFrameFactory;
+ }
+
+ public ITreeIndexFrameFactory getBTreeLeafFrameFactory() {
+ return btreeLeafFrameFactory;
+ }
+
+ public MultiComparator getBTreeCmp() {
+ return btreeCmp;
+ }
+
+ @Override
+ public ICachedPage getPage() {
+ return null;
+ }
+
+ @Override
+ public void setPage(ICachedPage page) {
+ }
+
+ public List<ILSMComponent> getOperationalComponents() {
+ return operationalComponents;
+ }
+
+ public ITreeIndexAccessor[] getRTreeAccessors() {
+ return rTreeAccessors;
+ }
+
+ public ITreeIndexAccessor[] getBTreeAccessors() {
+ return bTreeAccessors;
+ }
+
+ public boolean getIncludeMemComponent() {
+ return includeMemRTree;
+ }
+
+ public ILSMHarness getLSMHarness() {
+ return lsmHarness;
+ }
+
+ @Override
+ public ISearchOperationCallback getSearchOperationCallback() {
+ return searchCallback;
+ }
+
+ @Override
+ public void setSearchOperationCallback(ISearchOperationCallback searchCallback) {
+ this.searchCallback = searchCallback;
+ }
+
+ @Override
+ public MultiComparator getOriginalKeyComparator() {
+ return null;
+ }
+
+ @Override
+ public void setOriginialKeyComparator(MultiComparator originalCmp) {
+ }
+
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeFileManager.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeFileManager.java
new file mode 100644
index 0000000..e698990
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeFileManager.java
@@ -0,0 +1,229 @@
+/*
+ * 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.lsm.rtree.impls;
+
+import java.io.File;
+import java.io.FilenameFilter;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Date;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.api.io.IIOManager;
+import edu.uci.ics.hyracks.api.io.IODeviceHandle;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.AbstractLSMIndexFileManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMComponentFileReferences;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public class LSMRTreeFileManager extends AbstractLSMIndexFileManager {
+ private static final String RTREE_STRING = "r";
+ private static final String BTREE_STRING = "b";
+
+ private final TreeIndexFactory<? extends ITreeIndex> rtreeFactory;
+ private final TreeIndexFactory<? extends ITreeIndex> btreeFactory;
+
+ private static FilenameFilter btreeFilter = new FilenameFilter() {
+ public boolean accept(File dir, String name) {
+ return !name.startsWith(".") && name.endsWith(BTREE_STRING);
+ }
+ };
+
+ private static FilenameFilter rtreeFilter = new FilenameFilter() {
+ public boolean accept(File dir, String name) {
+ return !name.startsWith(".") && name.endsWith(RTREE_STRING);
+ }
+ };
+
+ public LSMRTreeFileManager(IIOManager ioManager, IFileMapProvider fileMapProvider, FileReference file,
+ TreeIndexFactory<? extends ITreeIndex> rtreeFactory, TreeIndexFactory<? extends ITreeIndex> btreeFactory,
+ int startIODeviceIndex) {
+ super(ioManager, fileMapProvider, file, null, startIODeviceIndex);
+ this.rtreeFactory = rtreeFactory;
+ this.btreeFactory = btreeFactory;
+ }
+
+ @Override
+ public LSMComponentFileReferences getRelFlushFileReference() {
+ Date date = new Date();
+ String ts = formatter.format(date);
+ String baseName = baseDir + ts + SPLIT_STRING + ts;
+ // Begin timestamp and end timestamp are identical since it is a flush
+ return new LSMComponentFileReferences(createFlushFile(baseName + SPLIT_STRING + RTREE_STRING),
+ createFlushFile(baseName + SPLIT_STRING + BTREE_STRING), createFlushFile(baseName + SPLIT_STRING
+ + BLOOM_FILTER_STRING));
+ }
+
+ @Override
+ public LSMComponentFileReferences getRelMergeFileReference(String firstFileName, String lastFileName)
+ throws HyracksDataException {
+ String[] firstTimestampRange = firstFileName.split(SPLIT_STRING);
+ String[] lastTimestampRange = lastFileName.split(SPLIT_STRING);
+
+ String baseName = baseDir + firstTimestampRange[0] + SPLIT_STRING + lastTimestampRange[1];
+ // Get the range of timestamps by taking the earliest and the latest timestamps
+ return new LSMComponentFileReferences(createMergeFile(baseName + SPLIT_STRING + RTREE_STRING),
+ createMergeFile(baseName + SPLIT_STRING + BTREE_STRING), createMergeFile(baseName + SPLIT_STRING
+ + BLOOM_FILTER_STRING));
+ }
+
+ @Override
+ public List<LSMComponentFileReferences> cleanupAndGetValidFiles() throws HyracksDataException, IndexException {
+ List<LSMComponentFileReferences> validFiles = new ArrayList<LSMComponentFileReferences>();
+ ArrayList<ComparableFileName> allRTreeFiles = new ArrayList<ComparableFileName>();
+ ArrayList<ComparableFileName> allBTreeFiles = new ArrayList<ComparableFileName>();
+ ArrayList<ComparableFileName> allBloomFilterFiles = new ArrayList<ComparableFileName>();
+
+ // Gather files from all IODeviceHandles.
+ for (IODeviceHandle dev : ioManager.getIODevices()) {
+ cleanupAndGetValidFilesInternal(dev, bloomFilterFilter, null, allBloomFilterFiles);
+ HashSet<String> bloomFilterFilesSet = new HashSet<String>();
+ for (ComparableFileName cmpFileName : allBloomFilterFiles) {
+ int index = cmpFileName.fileName.lastIndexOf(SPLIT_STRING);
+ bloomFilterFilesSet.add(cmpFileName.fileName.substring(0, index));
+ }
+
+ // List of valid BTree files that may or may not have a bloom filter buddy. Will check for buddies below.
+ ArrayList<ComparableFileName> tmpAllBTreeFiles = new ArrayList<ComparableFileName>();
+ cleanupAndGetValidFilesInternal(dev, btreeFilter, btreeFactory, tmpAllBTreeFiles);
+ // Look for buddy bloom filters for all valid BTrees.
+ // If no buddy is found, delete the file, otherwise add the BTree to allBTreeFiles.
+ HashSet<String> btreeFilesSet = new HashSet<String>();
+ for (ComparableFileName cmpFileName : tmpAllBTreeFiles) {
+ int index = cmpFileName.fileName.lastIndexOf(SPLIT_STRING);
+ String file = cmpFileName.fileName.substring(0, index);
+ if (bloomFilterFilesSet.contains(file)) {
+ allBTreeFiles.add(cmpFileName);
+ btreeFilesSet.add(cmpFileName.fileName.substring(0, index));
+ } else {
+ // Couldn't find the corresponding bloom filter file; thus, delete
+ // the BTree file.
+ File invalidBTreeFile = new File(cmpFileName.fullPath);
+ invalidBTreeFile.delete();
+ }
+ }
+
+ // List of valid RTree files that may or may not have a BTree buddy. Will check for buddies below.
+ ArrayList<ComparableFileName> tmpAllRTreeFiles = new ArrayList<ComparableFileName>();
+ cleanupAndGetValidFilesInternal(dev, rtreeFilter, rtreeFactory, tmpAllRTreeFiles);
+ // Look for buddy BTrees for all valid RTrees.
+ // If no buddy is found, delete the file, otherwise add the RTree to allRTreeFiles.
+ for (ComparableFileName cmpFileName : tmpAllRTreeFiles) {
+ int index = cmpFileName.fileName.lastIndexOf(SPLIT_STRING);
+ String file = cmpFileName.fileName.substring(0, index);
+ if (btreeFilesSet.contains(file)) {
+ allRTreeFiles.add(cmpFileName);
+ } else {
+ // Couldn't find the corresponding BTree file; thus, delete
+ // the RTree file.
+ File invalidRTreeFile = new File(cmpFileName.fullPath);
+ invalidRTreeFile.delete();
+ }
+ }
+ }
+ // Sanity check.
+ if (allRTreeFiles.size() != allBTreeFiles.size() || allBTreeFiles.size() != allBloomFilterFiles.size()) {
+ throw new HyracksDataException(
+ "Unequal number of valid RTree, BTree, and Bloom Filter files found. Aborting cleanup.");
+ }
+
+ // Trivial cases.
+ if (allRTreeFiles.isEmpty() || allBTreeFiles.isEmpty() || allBloomFilterFiles.isEmpty()) {
+ return validFiles;
+ }
+
+ if (allRTreeFiles.size() == 1 && allBTreeFiles.size() == 1 && allBloomFilterFiles.size() == 1) {
+ validFiles.add(new LSMComponentFileReferences(allRTreeFiles.get(0).fileRef, allBTreeFiles.get(0).fileRef,
+ allBloomFilterFiles.get(0).fileRef));
+ return validFiles;
+ }
+
+ // Sorts files names from earliest to latest timestamp.
+ Collections.sort(allRTreeFiles);
+ Collections.sort(allBTreeFiles);
+ Collections.sort(allBloomFilterFiles);
+
+ List<ComparableFileName> validComparableRTreeFiles = new ArrayList<ComparableFileName>();
+ ComparableFileName lastRTree = allRTreeFiles.get(0);
+ validComparableRTreeFiles.add(lastRTree);
+
+ List<ComparableFileName> validComparableBTreeFiles = new ArrayList<ComparableFileName>();
+ ComparableFileName lastBTree = allBTreeFiles.get(0);
+ validComparableBTreeFiles.add(lastBTree);
+
+ List<ComparableFileName> validComparableBloomFilterFiles = new ArrayList<ComparableFileName>();
+ ComparableFileName lastBloomFilter = allBloomFilterFiles.get(0);
+ validComparableBloomFilterFiles.add(lastBloomFilter);
+
+ for (int i = 1; i < allRTreeFiles.size(); i++) {
+ ComparableFileName currentRTree = allRTreeFiles.get(i);
+ ComparableFileName currentBTree = allBTreeFiles.get(i);
+ ComparableFileName currentBloomFilter = allBloomFilterFiles.get(i);
+ // Current start timestamp is greater than last stop timestamp.
+ if (currentRTree.interval[0].compareTo(lastRTree.interval[1]) > 0
+ && currentBTree.interval[0].compareTo(lastBTree.interval[1]) > 0
+ && currentBloomFilter.interval[0].compareTo(lastBloomFilter.interval[1]) > 0) {
+ validComparableRTreeFiles.add(currentRTree);
+ validComparableBTreeFiles.add(currentBTree);
+ validComparableBloomFilterFiles.add(currentBloomFilter);
+ lastRTree = currentRTree;
+ lastBTree = currentBTree;
+ lastBloomFilter = currentBloomFilter;
+ } else if (currentRTree.interval[0].compareTo(lastRTree.interval[0]) >= 0
+ && currentRTree.interval[1].compareTo(lastRTree.interval[1]) <= 0
+ && currentBTree.interval[0].compareTo(lastBTree.interval[0]) >= 0
+ && currentBTree.interval[1].compareTo(lastBTree.interval[1]) <= 0
+ && currentBloomFilter.interval[0].compareTo(lastBloomFilter.interval[0]) >= 0
+ && currentBloomFilter.interval[1].compareTo(lastBloomFilter.interval[1]) <= 0) {
+ // Invalid files are completely contained in last interval.
+ File invalidRTreeFile = new File(currentRTree.fullPath);
+ invalidRTreeFile.delete();
+ File invalidBTreeFile = new File(currentBTree.fullPath);
+ invalidBTreeFile.delete();
+ File invalidBloomFilterFile = new File(currentBloomFilter.fullPath);
+ invalidBloomFilterFile.delete();
+ } else {
+ // This scenario should not be possible.
+ throw new HyracksDataException("Found LSM files with overlapping but not contained timetamp intervals.");
+ }
+ }
+
+ // Sort valid files in reverse lexicographical order, such that newer
+ // files come first.
+ Collections.sort(validComparableRTreeFiles, recencyCmp);
+ Collections.sort(validComparableBTreeFiles, recencyCmp);
+ Collections.sort(validComparableBloomFilterFiles, recencyCmp);
+
+ Iterator<ComparableFileName> rtreeFileIter = validComparableRTreeFiles.iterator();
+ Iterator<ComparableFileName> btreeFileIter = validComparableBTreeFiles.iterator();
+ Iterator<ComparableFileName> bloomFilterFileIter = validComparableBloomFilterFiles.iterator();
+ while (rtreeFileIter.hasNext() && btreeFileIter.hasNext()) {
+ ComparableFileName cmpRTreeFileName = rtreeFileIter.next();
+ ComparableFileName cmpBTreeFileName = btreeFileIter.next();
+ ComparableFileName cmpBloomFilterFileName = bloomFilterFileIter.next();
+ validFiles.add(new LSMComponentFileReferences(cmpRTreeFileName.fileRef, cmpBTreeFileName.fileRef,
+ cmpBloomFilterFileName.fileRef));
+ }
+
+ return validFiles;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeFlushOperation.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeFlushOperation.java
new file mode 100644
index 0000000..7b7f2bc
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeFlushOperation.java
@@ -0,0 +1,77 @@
+package edu.uci.ics.hyracks.storage.am.lsm.rtree.impls;
+
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Set;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.api.io.IODeviceHandle;
+import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponent;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperation;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallback;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexAccessorInternal;
+
+public class LSMRTreeFlushOperation implements ILSMIOOperation {
+
+ private final ILSMIndexAccessorInternal accessor;
+ private final ILSMComponent flushingComponent;
+ private final FileReference rtreeFlushTarget;
+ private final FileReference btreeFlushTarget;
+ private final FileReference bloomFilterFlushTarget;
+ private final ILSMIOOperationCallback callback;
+
+ public LSMRTreeFlushOperation(ILSMIndexAccessorInternal accessor, ILSMComponent flushingComponent,
+ FileReference rtreeFlushTarget, FileReference btreeFlushTarget, FileReference bloomFilterFlushTarget,
+ ILSMIOOperationCallback callback) {
+ this.accessor = accessor;
+ this.flushingComponent = flushingComponent;
+ this.rtreeFlushTarget = rtreeFlushTarget;
+ this.btreeFlushTarget = btreeFlushTarget;
+ this.bloomFilterFlushTarget = bloomFilterFlushTarget;
+ this.callback = callback;
+ }
+
+ @Override
+ public Set<IODeviceHandle> getReadDevices() {
+ return Collections.emptySet();
+ }
+
+ @Override
+ public Set<IODeviceHandle> getWriteDevices() {
+ Set<IODeviceHandle> devs = new HashSet<IODeviceHandle>();
+ devs.add(rtreeFlushTarget.getDeviceHandle());
+ if (btreeFlushTarget != null) {
+ devs.add(btreeFlushTarget.getDeviceHandle());
+ devs.add(bloomFilterFlushTarget.getDeviceHandle());
+ }
+ return devs;
+ }
+
+ @Override
+ public void perform() throws HyracksDataException, IndexException {
+ accessor.flush(this);
+ }
+
+ @Override
+ public ILSMIOOperationCallback getCallback() {
+ return callback;
+ }
+
+ public FileReference getRTreeFlushTarget() {
+ return rtreeFlushTarget;
+ }
+
+ public FileReference getBTreeFlushTarget() {
+ return btreeFlushTarget;
+ }
+
+ public FileReference getBloomFilterFlushTarget() {
+ return bloomFilterFlushTarget;
+ }
+
+ public ILSMComponent getFlushingComponent() {
+ return flushingComponent;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeImmutableComponent.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeImmutableComponent.java
new file mode 100644
index 0000000..8d20c14
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeImmutableComponent.java
@@ -0,0 +1,43 @@
+package edu.uci.ics.hyracks.storage.am.lsm.rtree.impls;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.bloomfilter.impls.BloomFilter;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.AbstractImmutableLSMComponent;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+
+public class LSMRTreeImmutableComponent extends AbstractImmutableLSMComponent {
+ private final RTree rtree;
+ private final BTree btree;
+ private final BloomFilter bloomFilter;
+
+ public LSMRTreeImmutableComponent(RTree rtree, BTree btree, BloomFilter bloomFilter) {
+ this.rtree = rtree;
+ this.btree = btree;
+ this.bloomFilter = bloomFilter;
+ }
+
+ @Override
+ public void destroy() throws HyracksDataException {
+ rtree.deactivate();
+ rtree.destroy();
+ if (btree != null) {
+ btree.deactivate();
+ btree.destroy();
+ bloomFilter.deactivate();
+ bloomFilter.destroy();
+ }
+ }
+
+ public RTree getRTree() {
+ return rtree;
+ }
+
+ public BTree getBTree() {
+ return btree;
+ }
+
+ public BloomFilter getBloomFilter() {
+ return bloomFilter;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeMergeOperation.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeMergeOperation.java
new file mode 100644
index 0000000..0e05a93
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeMergeOperation.java
@@ -0,0 +1,92 @@
+package edu.uci.ics.hyracks.storage.am.lsm.rtree.impls;
+
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.api.io.IODeviceHandle;
+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.lsm.common.api.ILSMComponent;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperation;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallback;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexAccessorInternal;
+
+public class LSMRTreeMergeOperation implements ILSMIOOperation {
+ private final ILSMIndexAccessorInternal accessor;
+ private final List<ILSMComponent> mergingComponents;
+ private final ITreeIndexCursor cursor;
+ private final FileReference rtreeMergeTarget;
+ private final FileReference btreeMergeTarget;
+ private final FileReference bloomFilterMergeTarget;
+ private final ILSMIOOperationCallback callback;
+
+ public LSMRTreeMergeOperation(ILSMIndexAccessorInternal accessor, List<ILSMComponent> mergingComponents,
+ ITreeIndexCursor cursor, FileReference rtreeMergeTarget, FileReference btreeMergeTarget,
+ FileReference bloomFilterMergeTarget, ILSMIOOperationCallback callback) {
+ this.accessor = accessor;
+ this.mergingComponents = mergingComponents;
+ this.cursor = cursor;
+ this.rtreeMergeTarget = rtreeMergeTarget;
+ this.btreeMergeTarget = btreeMergeTarget;
+ this.bloomFilterMergeTarget = bloomFilterMergeTarget;
+ this.callback = callback;
+ }
+
+ @Override
+ public Set<IODeviceHandle> getReadDevices() {
+ Set<IODeviceHandle> devs = new HashSet<IODeviceHandle>();
+ for (ILSMComponent o : mergingComponents) {
+ LSMRTreeImmutableComponent component = (LSMRTreeImmutableComponent) o;
+ devs.add(component.getRTree().getFileReference().getDeviceHandle());
+ if (component.getBTree() != null) {
+ devs.add(component.getBTree().getFileReference().getDeviceHandle());
+ devs.add(component.getBloomFilter().getFileReference().getDeviceHandle());
+ }
+ }
+ return devs;
+ }
+
+ @Override
+ public Set<IODeviceHandle> getWriteDevices() {
+ Set<IODeviceHandle> devs = new HashSet<IODeviceHandle>();
+ devs.add(rtreeMergeTarget.getDeviceHandle());
+ if (btreeMergeTarget != null) {
+ devs.add(btreeMergeTarget.getDeviceHandle());
+ devs.add(bloomFilterMergeTarget.getDeviceHandle());
+ }
+ return devs;
+ }
+
+ @Override
+ public void perform() throws HyracksDataException, IndexException {
+ accessor.merge(this);
+ }
+
+ @Override
+ public ILSMIOOperationCallback getCallback() {
+ return callback;
+ }
+
+ public FileReference getRTreeMergeTarget() {
+ return rtreeMergeTarget;
+ }
+
+ public FileReference getBTreeMergeTarget() {
+ return btreeMergeTarget;
+ }
+
+ public FileReference getBloomFilterMergeTarget() {
+ return bloomFilterMergeTarget;
+ }
+
+ public ITreeIndexCursor getCursor() {
+ return cursor;
+ }
+
+ public List<ILSMComponent> getMergingComponents() {
+ return mergingComponents;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeMutableComponent.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeMutableComponent.java
new file mode 100644
index 0000000..80f76a1
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeMutableComponent.java
@@ -0,0 +1,56 @@
+/*
+ * Copyright 2009-2012 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.lsm.rtree.impls;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.common.api.IInMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.AbstractMutableLSMComponent;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+
+public class LSMRTreeMutableComponent extends AbstractMutableLSMComponent {
+
+ private final RTree rtree;
+ private final BTree btree;
+ private final IInMemoryFreePageManager mfpm;
+
+ public LSMRTreeMutableComponent(RTree rtree, BTree btree, IInMemoryFreePageManager mfpm) {
+ this.rtree = rtree;
+ this.btree = btree;
+ this.mfpm = mfpm;
+ }
+
+ public RTree getRTree() {
+ return rtree;
+ }
+
+ public BTree getBTree() {
+ return btree;
+ }
+
+ @Override
+ protected boolean isFull() {
+ return mfpm.isFull();
+ }
+
+ @Override
+ protected void reset() throws HyracksDataException {
+ rtree.clear();
+ if (btree != null) {
+ btree.clear();
+ }
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeOpContext.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeOpContext.java
new file mode 100644
index 0000000..b8805d1
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeOpContext.java
@@ -0,0 +1,104 @@
+/*
+ * 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.lsm.rtree.impls;
+
+import java.util.LinkedList;
+import java.util.List;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
+import edu.uci.ics.hyracks.storage.am.common.api.IModificationOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
+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.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOperation;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponent;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext;
+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.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
+
+public final class LSMRTreeOpContext implements ILSMIndexOperationContext {
+
+ public RTreeOpContext rtreeOpContext;
+ public BTreeOpContext btreeOpContext;
+ public final RTree.RTreeAccessor memRTreeAccessor;
+ public final BTree.BTreeAccessor memBTreeAccessor;
+ private IndexOperation op;
+ public final List<ILSMComponent> componentHolder;
+ public final IModificationOperationCallback modificationCallback;
+ public final ISearchOperationCallback searchCallback;
+
+ public LSMRTreeOpContext(RTree.RTreeAccessor memRtreeAccessor, IRTreeLeafFrame rtreeLeafFrame,
+ IRTreeInteriorFrame rtreeInteriorFrame, ITreeIndexMetaDataFrame rtreeMetaFrame, int rTreeHeightHint,
+ BTree.BTreeAccessor memBtreeAccessor, ITreeIndexFrameFactory btreeLeafFrameFactory,
+ ITreeIndexFrameFactory btreeInteriorFrameFactory, ITreeIndexMetaDataFrame btreeMetaFrame,
+ IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories,
+ IModificationOperationCallback modificationCallback, ISearchOperationCallback searchCallback) {
+ this.memRTreeAccessor = memRtreeAccessor;
+ this.memBTreeAccessor = memBtreeAccessor;
+ this.componentHolder = new LinkedList<ILSMComponent>();
+ this.modificationCallback = modificationCallback;
+ this.searchCallback = searchCallback;
+ this.rtreeOpContext = new RTreeOpContext(rtreeLeafFrame, rtreeInteriorFrame, rtreeMetaFrame, rtreeCmpFactories,
+ rTreeHeightHint, NoOpOperationCallback.INSTANCE);
+ this.btreeOpContext = new BTreeOpContext(memBtreeAccessor, btreeLeafFrameFactory, btreeInteriorFrameFactory,
+ btreeMetaFrame, btreeCmpFactories, NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE);
+ }
+
+ public void setOperation(IndexOperation newOp) {
+ reset();
+ if (newOp == IndexOperation.INSERT) {
+ rtreeOpContext.setOperation(newOp);
+ } else if (newOp == IndexOperation.DELETE) {
+ btreeOpContext.setOperation(IndexOperation.INSERT);
+ }
+ this.op = newOp;
+ }
+
+ @Override
+ public void reset() {
+ componentHolder.clear();
+ }
+
+ @Override
+ public IndexOperation getOperation() {
+ return op;
+ }
+
+ public MultiComparator getBTreeMultiComparator() {
+ return btreeOpContext.cmp;
+ }
+
+ @Override
+ public List<ILSMComponent> getComponentHolder() {
+ return componentHolder;
+ }
+
+ @Override
+ public ISearchOperationCallback getSearchOperationCallback() {
+ return searchCallback;
+ }
+
+ @Override
+ public IModificationOperationCallback getModificationCallback() {
+ return modificationCallback;
+ }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
new file mode 100644
index 0000000..966ed8d
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
@@ -0,0 +1,124 @@
+/*
+ * 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.lsm.rtree.impls;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext;
+
+public class LSMRTreeSearchCursor extends LSMRTreeAbstractCursor {
+
+ private int currentCursor;
+
+ public LSMRTreeSearchCursor(ILSMIndexOperationContext opCtx) {
+ super(opCtx);
+ currentCursor = 0;
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ super.close();
+ currentCursor = 0;
+ }
+
+ @Override
+ public void reset() throws HyracksDataException {
+ if (!open) {
+ return;
+ }
+
+ currentCursor = 0;
+ foundNext = false;
+ try {
+ for (int i = 0; i < numberOfTrees; i++) {
+ rtreeCursors[i].close();
+ btreeCursors[i].close();
+ }
+ rtreeCursors = null;
+ btreeCursors = null;
+ } finally {
+ lsmHarness.endSearch(opCtx);
+ }
+ }
+
+ private void searchNextCursor() throws HyracksDataException {
+ if (currentCursor < numberOfTrees) {
+ rtreeCursors[currentCursor].reset();
+ try {
+ rTreeAccessors[currentCursor].search(rtreeCursors[currentCursor], rtreeSearchPredicate);
+ } catch (IndexException e) {
+ throw new HyracksDataException(e);
+ }
+ }
+ }
+
+ @Override
+ public boolean hasNext() throws HyracksDataException, IndexException {
+ if (foundNext) {
+ return true;
+ }
+ while (currentCursor < numberOfTrees) {
+ while (rtreeCursors[currentCursor].hasNext()) {
+ rtreeCursors[currentCursor].next();
+ ITupleReference currentTuple = rtreeCursors[currentCursor].getTuple();
+
+ boolean killerTupleFound = false;
+ for (int i = 0; i <= currentCursor; i++) {
+ try {
+ btreeCursors[i].reset();
+ btreeRangePredicate.setHighKey(currentTuple, true);
+ btreeRangePredicate.setLowKey(currentTuple, true);
+ bTreeAccessors[i].search(btreeCursors[i], btreeRangePredicate);
+ } catch (IndexException e) {
+ throw new HyracksDataException(e);
+ }
+ try {
+ if (btreeCursors[i].hasNext()) {
+ killerTupleFound = true;
+ break;
+ }
+ } finally {
+ btreeCursors[i].close();
+ }
+ }
+ if (!killerTupleFound) {
+ frameTuple = currentTuple;
+ foundNext = true;
+ return true;
+ }
+ }
+ rtreeCursors[currentCursor].close();
+ currentCursor++;
+ searchNextCursor();
+ }
+ return false;
+ }
+
+ @Override
+ public void next() throws HyracksDataException {
+ foundNext = false;
+ }
+
+ @Override
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+ super.open(initialState, searchPred);
+ searchNextCursor();
+ }
+
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSortedCursor.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSortedCursor.java
new file mode 100644
index 0000000..02a1876
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSortedCursor.java
@@ -0,0 +1,152 @@
+/*
+ * 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.lsm.rtree.impls;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparatorFactory;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext;
+
+public class LSMRTreeSortedCursor extends LSMRTreeAbstractCursor {
+
+ private ILinearizeComparator linearizeCmp;
+ private boolean[] depletedRtreeCursors;
+ private int foundIn = -1;
+
+ public LSMRTreeSortedCursor(ILSMIndexOperationContext opCtx, ILinearizeComparatorFactory linearizer)
+ throws HyracksDataException {
+ super(opCtx);
+ this.linearizeCmp = linearizer.createBinaryComparator();
+ reset();
+ }
+
+ @Override
+ public void reset() throws HyracksDataException {
+ depletedRtreeCursors = new boolean[numberOfTrees];
+ foundNext = false;
+ try {
+ for (int i = 0; i < numberOfTrees; i++) {
+ rtreeCursors[i].reset();
+ try {
+ rTreeAccessors[i].search(rtreeCursors[i], rtreeSearchPredicate);
+ } catch (IndexException e) {
+ throw new HyracksDataException(e);
+ }
+ if (rtreeCursors[i].hasNext()) {
+ rtreeCursors[i].next();
+ } else {
+ depletedRtreeCursors[i] = true;
+ }
+ }
+ } finally {
+ if (open) {
+ lsmHarness.endSearch(opCtx);
+ }
+ }
+ }
+
+ @Override
+ public boolean hasNext() throws HyracksDataException, IndexException {
+ while (!foundNext) {
+ frameTuple = null;
+
+ if (foundIn != -1) {
+ if (rtreeCursors[foundIn].hasNext()) {
+ rtreeCursors[foundIn].next();
+ } else {
+ depletedRtreeCursors[foundIn] = true;
+ }
+ }
+
+ foundIn = -1;
+ for (int i = 0; i < numberOfTrees; i++) {
+ if (depletedRtreeCursors[i])
+ continue;
+
+ if (frameTuple == null) {
+ frameTuple = rtreeCursors[i].getTuple();
+ foundIn = i;
+ continue;
+ }
+
+ if (linearizeCmp.compare(frameTuple.getFieldData(0), frameTuple.getFieldStart(0),
+ frameTuple.getFieldLength(0) * linearizeCmp.getDimensions(), rtreeCursors[i].getTuple()
+ .getFieldData(0), rtreeCursors[i].getTuple().getFieldStart(0), rtreeCursors[i]
+ .getTuple().getFieldLength(0) * linearizeCmp.getDimensions()) <= 0) {
+ frameTuple = rtreeCursors[i].getTuple();
+ foundIn = i;
+ }
+ }
+
+ if (foundIn == -1)
+ return false;
+
+ boolean killed = false;
+ for (int i = 0; i < foundIn; i++) {
+ try {
+ btreeCursors[i].reset();
+ btreeRangePredicate.setHighKey(frameTuple, true);
+ btreeRangePredicate.setLowKey(frameTuple, true);
+ bTreeAccessors[i].search(btreeCursors[i], btreeRangePredicate);
+ } catch (IndexException e) {
+ throw new HyracksDataException(e);
+ }
+ try {
+ if (btreeCursors[i].hasNext()) {
+ killed = true;
+ break;
+ }
+ } finally {
+ btreeCursors[i].close();
+ }
+ }
+ if (!killed) {
+ foundNext = true;
+ }
+ }
+
+ return true;
+ }
+
+ @Override
+ public void next() throws HyracksDataException {
+ foundNext = false;
+ }
+
+ @Override
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+ super.open(initialState, searchPred);
+
+ depletedRtreeCursors = new boolean[numberOfTrees];
+ foundNext = false;
+ for (int i = 0; i < numberOfTrees; i++) {
+ rtreeCursors[i].reset();
+ try {
+ rTreeAccessors[i].search(rtreeCursors[i], rtreeSearchPredicate);
+ } catch (IndexException e) {
+ throw new HyracksDataException(e);
+ }
+ if (rtreeCursors[i].hasNext()) {
+ rtreeCursors[i].next();
+ } else {
+ depletedRtreeCursors[i] = true;
+ }
+ }
+ }
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuples.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuples.java
new file mode 100644
index 0000000..478d076
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuples.java
@@ -0,0 +1,434 @@
+/*
+ * Copyright 2009-2012 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.lsm.rtree.impls;
+
+import java.util.List;
+import java.util.ListIterator;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparatorFactory;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.IInMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoader;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.IModificationOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+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.IndexException;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOperation;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.IInMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponent;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponentFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMHarness;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperation;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallback;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallbackProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationScheduler;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexAccessorInternal;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexFileManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMMergePolicy;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMOperationTrackerFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMComponentFileReferences;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
+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.common.file.IFileMapProvider;
+
+public class LSMRTreeWithAntiMatterTuples extends AbstractLSMRTree {
+
+ private TreeTupleSorter bTreeTupleSorter;
+
+ // On-disk components.
+ // For creating RTree's used in bulk load. Different from diskRTreeFactory
+ // because it should have a different tuple writer in it's leaf frames.
+ private final ILSMComponentFactory bulkLoaComponentFactory;
+
+ public LSMRTreeWithAntiMatterTuples(IInMemoryBufferCache memBufferCache,
+ IInMemoryFreePageManager memFreePageManager, ITreeIndexFrameFactory rtreeInteriorFrameFactory,
+ ITreeIndexFrameFactory rtreeLeafFrameFactory, ITreeIndexFrameFactory btreeInteriorFrameFactory,
+ ITreeIndexFrameFactory btreeLeafFrameFactory, ILSMIndexFileManager fileManager,
+ TreeIndexFactory<RTree> diskRTreeFactory, TreeIndexFactory<RTree> bulkLoadRTreeFactory,
+ IFileMapProvider diskFileMapProvider, int fieldCount, IBinaryComparatorFactory[] rtreeCmpFactories,
+ IBinaryComparatorFactory[] btreeCmpFactories, ILinearizeComparatorFactory linearizer,
+ int[] comparatorFields, IBinaryComparatorFactory[] linearizerArray, ILSMMergePolicy mergePolicy,
+ ILSMOperationTrackerFactory opTrackerFactory, ILSMIOOperationScheduler ioScheduler,
+ ILSMIOOperationCallbackProvider ioOpCallbackProvider) {
+ super(memBufferCache, memFreePageManager, rtreeInteriorFrameFactory, rtreeLeafFrameFactory,
+ btreeInteriorFrameFactory, btreeLeafFrameFactory, fileManager, diskRTreeFactory,
+ new LSMRTreeWithAntiMatterTuplesComponentFactory(diskRTreeFactory), diskFileMapProvider, fieldCount,
+ rtreeCmpFactories, btreeCmpFactories, linearizer, comparatorFields, linearizerArray, mergePolicy,
+ opTrackerFactory, ioScheduler, ioOpCallbackProvider);
+ bulkLoaComponentFactory = new LSMRTreeWithAntiMatterTuplesComponentFactory(bulkLoadRTreeFactory);
+ this.bTreeTupleSorter = null;
+ }
+
+ @Override
+ public synchronized void activate() throws HyracksDataException {
+ super.activate();
+ List<ILSMComponent> immutableComponents = componentsRef.get();
+ immutableComponents.clear();
+ List<LSMComponentFileReferences> validFileReferences;
+ try {
+ validFileReferences = fileManager.cleanupAndGetValidFiles();
+ } catch (IndexException e) {
+ throw new HyracksDataException(e);
+ }
+ for (LSMComponentFileReferences lsmComonentFileReference : validFileReferences) {
+ LSMRTreeImmutableComponent component;
+ try {
+ component = createDiskComponent(componentFactory,
+ lsmComonentFileReference.getInsertIndexFileReference(), null, null, false);
+ } catch (IndexException e) {
+ throw new HyracksDataException(e);
+ }
+ immutableComponents.add(component);
+ }
+ isActivated = true;
+ }
+
+ @Override
+ public synchronized void deactivate(boolean flushOnExit) throws HyracksDataException {
+ super.deactivate(flushOnExit);
+ List<ILSMComponent> immutableComponents = componentsRef.get();
+ for (ILSMComponent c : immutableComponents) {
+ RTree rtree = (RTree) ((LSMRTreeImmutableComponent) c).getRTree();
+ rtree.deactivate();
+ }
+ isActivated = false;
+ }
+
+ @Override
+ public synchronized void deactivate() throws HyracksDataException {
+ deactivate(true);
+ }
+
+ @Override
+ public synchronized void destroy() throws HyracksDataException {
+ super.destroy();
+ List<ILSMComponent> immutableComponents = componentsRef.get();
+ for (ILSMComponent c : immutableComponents) {
+ RTree rtree = (RTree) ((LSMRTreeImmutableComponent) c).getRTree();
+ rtree.destroy();
+ }
+ fileManager.deleteDirs();
+ }
+
+ @Override
+ public synchronized void clear() throws HyracksDataException {
+ super.clear();
+ List<ILSMComponent> immutableComponents = componentsRef.get();
+ for (ILSMComponent c : immutableComponents) {
+ RTree rtree = (RTree) ((LSMRTreeImmutableComponent) c).getRTree();
+ rtree.deactivate();
+ rtree.destroy();
+ }
+ immutableComponents.clear();
+ }
+
+ @Override
+ public void search(ILSMIndexOperationContext ictx, IIndexCursor cursor, ISearchPredicate pred)
+ throws HyracksDataException, IndexException {
+ LSMRTreeOpContext ctx = (LSMRTreeOpContext) ictx;
+ List<ILSMComponent> operationalComponents = ictx.getComponentHolder();
+ boolean includeMutableComponent = operationalComponents.get(0) == mutableComponent;
+ LSMRTreeWithAntiMatterTuplesSearchCursor lsmTreeCursor = (LSMRTreeWithAntiMatterTuplesSearchCursor) cursor;
+ int numDiskRComponents = operationalComponents.size();
+
+ LSMRTreeCursorInitialState initialState;
+ ITreeIndexAccessor[] bTreeAccessors = null;
+ if (includeMutableComponent) {
+ // Only in-memory BTree
+ bTreeAccessors = new ITreeIndexAccessor[1];
+ bTreeAccessors[0] = ctx.memBTreeAccessor;
+ }
+
+ initialState = new LSMRTreeCursorInitialState(numDiskRComponents, rtreeLeafFrameFactory,
+ rtreeInteriorFrameFactory, btreeLeafFrameFactory, ctx.getBTreeMultiComparator(), null, bTreeAccessors,
+ includeMutableComponent, lsmHarness, comparatorFields, linearizerArray, ctx.searchCallback,
+ operationalComponents);
+
+ lsmTreeCursor.open(initialState, pred);
+
+ ListIterator<ILSMComponent> diskComponentsIter = operationalComponents.listIterator();
+ int diskComponentIx = 0;
+ if (includeMutableComponent) {
+ // Open cursor of in-memory RTree
+ ctx.memRTreeAccessor.search(lsmTreeCursor.getMemRTreeCursor(), pred);
+ diskComponentIx++;
+ diskComponentsIter.next();
+ }
+
+ // Open cursors of on-disk RTrees.
+ ITreeIndexAccessor[] diskRTreeAccessors = new ITreeIndexAccessor[numDiskRComponents];
+ while (diskComponentsIter.hasNext()) {
+ RTree diskRTree = (RTree) ((LSMRTreeImmutableComponent) diskComponentsIter.next()).getRTree();
+ diskRTreeAccessors[diskComponentIx] = diskRTree.createAccessor(NoOpOperationCallback.INSTANCE,
+ NoOpOperationCallback.INSTANCE);
+ diskRTreeAccessors[diskComponentIx].search(lsmTreeCursor.getCursor(diskComponentIx), pred);
+ diskComponentIx++;
+ }
+ lsmTreeCursor.initPriorityQueue();
+ }
+
+ @Override
+ public void scheduleFlush(ILSMIndexOperationContext ctx, ILSMIOOperationCallback callback)
+ throws HyracksDataException {
+ LSMRTreeOpContext opCtx = createOpContext(NoOpOperationCallback.INSTANCE);
+ LSMComponentFileReferences relFlushFileRefs = fileManager.getRelFlushFileReference();
+ ILSMComponent flushingComponent = ctx.getComponentHolder().get(0);
+ opCtx.setOperation(IndexOperation.FLUSH);
+ opCtx.getComponentHolder().add(flushingComponent);
+ ILSMIndexAccessorInternal accessor = new LSMRTreeWithAntiMatterTuplesAccessor(lsmHarness, opCtx);
+ ioScheduler.scheduleOperation(new LSMRTreeFlushOperation(accessor, flushingComponent, relFlushFileRefs
+ .getInsertIndexFileReference(), null, null, callback));
+ }
+
+ @Override
+ public ILSMComponent flush(ILSMIOOperation operation) throws HyracksDataException, IndexException {
+ LSMRTreeFlushOperation flushOp = (LSMRTreeFlushOperation) operation;
+ // Renaming order is critical because we use assume ordering when we
+ // read the file names when we open the tree.
+ // The RTree should be renamed before the BTree.
+ LSMRTreeMutableComponent flushingComponent = (LSMRTreeMutableComponent) flushOp.getFlushingComponent();
+ ITreeIndexAccessor memRTreeAccessor = flushingComponent.getRTree().createAccessor(
+ NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE);
+ RTreeSearchCursor rtreeScanCursor = (RTreeSearchCursor) memRTreeAccessor.createSearchCursor();
+ SearchPredicate rtreeNullPredicate = new SearchPredicate(null, null);
+ memRTreeAccessor.search(rtreeScanCursor, rtreeNullPredicate);
+ LSMRTreeImmutableComponent component = createDiskComponent(componentFactory, flushOp.getRTreeFlushTarget(),
+ null, null, true);
+ RTree diskRTree = component.getRTree();
+
+ // scan the memory BTree
+ ITreeIndexAccessor memBTreeAccessor = flushingComponent.getBTree().createAccessor(
+ NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE);
+ BTreeRangeSearchCursor btreeScanCursor = (BTreeRangeSearchCursor) memBTreeAccessor.createSearchCursor();
+ RangePredicate btreeNullPredicate = new RangePredicate(null, null, true, true, null, null);
+ memBTreeAccessor.search(btreeScanCursor, btreeNullPredicate);
+
+ // Since the LSM-RTree is used as a secondary assumption, the
+ // primary key will be the last comparator in the BTree comparators
+ if (rTreeTupleSorter == null) {
+ rTreeTupleSorter = new TreeTupleSorter(flushingComponent.getRTree().getFileId(), linearizerArray,
+ rtreeLeafFrameFactory.createFrame(), rtreeLeafFrameFactory.createFrame(), flushingComponent
+ .getRTree().getBufferCache(), comparatorFields);
+
+ bTreeTupleSorter = new TreeTupleSorter(flushingComponent.getBTree().getFileId(), linearizerArray,
+ btreeLeafFrameFactory.createFrame(), btreeLeafFrameFactory.createFrame(), flushingComponent
+ .getBTree().getBufferCache(), comparatorFields);
+ } else {
+ rTreeTupleSorter.reset();
+ bTreeTupleSorter.reset();
+ }
+ // BulkLoad the tuples from the in-memory tree into the new disk
+ // RTree.
+
+ boolean isEmpty = true;
+ try {
+ while (rtreeScanCursor.hasNext()) {
+ isEmpty = false;
+ rtreeScanCursor.next();
+ rTreeTupleSorter.insertTupleEntry(rtreeScanCursor.getPageId(), rtreeScanCursor.getTupleOffset());
+ }
+ } finally {
+ rtreeScanCursor.close();
+ }
+ if (!isEmpty) {
+ rTreeTupleSorter.sort();
+ }
+
+ isEmpty = true;
+ try {
+ while (btreeScanCursor.hasNext()) {
+ isEmpty = false;
+ btreeScanCursor.next();
+ bTreeTupleSorter.insertTupleEntry(btreeScanCursor.getPageId(), btreeScanCursor.getTupleOffset());
+ }
+ } finally {
+ btreeScanCursor.close();
+ }
+ if (!isEmpty) {
+ bTreeTupleSorter.sort();
+ }
+
+ IIndexBulkLoader rTreeBulkloader = diskRTree.createBulkLoader(1.0f, false, 0L);
+ LSMRTreeWithAntiMatterTuplesFlushCursor cursor = new LSMRTreeWithAntiMatterTuplesFlushCursor(rTreeTupleSorter,
+ bTreeTupleSorter, comparatorFields, linearizerArray);
+ cursor.open(null, null);
+
+ try {
+ while (cursor.hasNext()) {
+ cursor.next();
+ ITupleReference frameTuple = cursor.getTuple();
+
+ rTreeBulkloader.add(frameTuple);
+ }
+ } finally {
+ cursor.close();
+ }
+
+ rTreeBulkloader.end();
+ return component;
+ }
+
+ @Override
+ public void scheduleMerge(ILSMIndexOperationContext ctx, ILSMIOOperationCallback callback)
+ throws HyracksDataException, IndexException {
+ List<ILSMComponent> mergingComponents = ctx.getComponentHolder();
+ LSMRTreeOpContext rctx = createOpContext(NoOpOperationCallback.INSTANCE);
+ rctx.getComponentHolder().addAll(mergingComponents);
+ ITreeIndexCursor cursor = new LSMRTreeWithAntiMatterTuplesSearchCursor(ctx);
+ ISearchPredicate rtreeSearchPred = new SearchPredicate(null, null);
+ search(rctx, cursor, (SearchPredicate) rtreeSearchPred);
+ rctx.setOperation(IndexOperation.MERGE);
+ LSMComponentFileReferences relMergeFileRefs = getMergeTargetFileName(mergingComponents);
+ ILSMIndexAccessorInternal accessor = new LSMRTreeWithAntiMatterTuplesAccessor(lsmHarness, rctx);
+ ioScheduler.scheduleOperation(new LSMRTreeMergeOperation(accessor, mergingComponents, cursor, relMergeFileRefs
+ .getInsertIndexFileReference(), null, null, callback));
+ }
+
+ @Override
+ public ILSMComponent merge(List<ILSMComponent> mergedComponents, ILSMIOOperation operation)
+ throws HyracksDataException, IndexException {
+ LSMRTreeMergeOperation mergeOp = (LSMRTreeMergeOperation) operation;
+ ITreeIndexCursor cursor = mergeOp.getCursor();
+ mergedComponents.addAll(mergeOp.getMergingComponents());
+
+ // Nothing to merge.
+ if (mergedComponents.size() <= 1) {
+ cursor.close();
+ return null;
+ }
+
+ // Bulk load the tuples from all on-disk RTrees into the new RTree.
+ LSMRTreeImmutableComponent component = createDiskComponent(componentFactory, mergeOp.getRTreeMergeTarget(),
+ null, null, true);
+ RTree mergedRTree = component.getRTree();
+ IIndexBulkLoader bulkloader = mergedRTree.createBulkLoader(1.0f, false, 0L);
+ try {
+ while (cursor.hasNext()) {
+ cursor.next();
+ ITupleReference frameTuple = cursor.getTuple();
+ bulkloader.add(frameTuple);
+ }
+ } finally {
+ cursor.close();
+ }
+ bulkloader.end();
+ return component;
+ }
+
+ @Override
+ public ILSMIndexAccessorInternal createAccessor(IModificationOperationCallback modificationCallback,
+ ISearchOperationCallback searchCallback) {
+ return new LSMRTreeWithAntiMatterTuplesAccessor(lsmHarness, createOpContext(modificationCallback));
+ }
+
+ public class LSMRTreeWithAntiMatterTuplesAccessor extends LSMTreeIndexAccessor {
+ public LSMRTreeWithAntiMatterTuplesAccessor(ILSMHarness lsmHarness, ILSMIndexOperationContext ctx) {
+ super(lsmHarness, ctx);
+ }
+
+ @Override
+ public ITreeIndexCursor createSearchCursor() {
+ return new LSMRTreeWithAntiMatterTuplesSearchCursor(ctx);
+ }
+
+ public MultiComparator getMultiComparator() {
+ LSMRTreeOpContext concreteCtx = (LSMRTreeOpContext) ctx;
+ return concreteCtx.rtreeOpContext.cmp;
+ }
+ }
+
+ @Override
+ public IIndexBulkLoader createBulkLoader(float fillLevel, boolean verifyInput, long numElementsHint)
+ throws TreeIndexException {
+ return new LSMRTreeWithAntiMatterTuplesBulkLoader(fillLevel, verifyInput, numElementsHint);
+ }
+
+ private ILSMComponent createBulkLoadTarget() throws HyracksDataException, IndexException {
+ LSMComponentFileReferences relFlushFileRefs = fileManager.getRelFlushFileReference();
+ return createDiskComponent(bulkLoaComponentFactory, relFlushFileRefs.getInsertIndexFileReference(), null, null,
+ true);
+ }
+
+ public class LSMRTreeWithAntiMatterTuplesBulkLoader implements IIndexBulkLoader {
+ private final ILSMComponent component;
+ private final IIndexBulkLoader bulkLoader;
+
+ public LSMRTreeWithAntiMatterTuplesBulkLoader(float fillFactor, boolean verifyInput, long numElementsHint)
+ throws TreeIndexException {
+ // Note that by using a flush target file name, we state that the
+ // new bulk loaded tree is "newer" than any other merged tree.
+ try {
+ component = createBulkLoadTarget();
+ } catch (HyracksDataException e) {
+ throw new TreeIndexException(e);
+ } catch (IndexException e) {
+ throw new TreeIndexException(e);
+ }
+ bulkLoader = ((LSMRTreeImmutableComponent) component).getRTree().createBulkLoader(fillFactor, verifyInput,
+ numElementsHint);
+ }
+
+ @Override
+ public void add(ITupleReference tuple) throws HyracksDataException, IndexException {
+ try {
+ bulkLoader.add(tuple);
+ } catch (IndexException e) {
+ handleException();
+ throw e;
+ } catch (HyracksDataException e) {
+ handleException();
+ throw e;
+ } catch (RuntimeException e) {
+ handleException();
+ throw e;
+ }
+ }
+
+ @Override
+ public void end() throws HyracksDataException, IndexException {
+ bulkLoader.end();
+ lsmHarness.addBulkLoadedComponent(component);
+ }
+
+ protected void handleException() throws HyracksDataException {
+ ((LSMRTreeImmutableComponent) component).getRTree().deactivate();
+ ((LSMRTreeImmutableComponent) component).getRTree().destroy();
+ }
+
+ }
+
+ @Override
+ public void markAsValid(ILSMComponent lsmComponent) throws HyracksDataException {
+ RTree rtree = ((LSMRTreeImmutableComponent) lsmComponent).getRTree();
+ forceFlushDirtyPages(rtree);
+ markAsValidInternal(rtree);
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesComponentFactory.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesComponentFactory.java
new file mode 100644
index 0000000..0149800
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesComponentFactory.java
@@ -0,0 +1,43 @@
+/*
+ * Copyright 2009-2012 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.lsm.rtree.impls;
+
+import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponent;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponentFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMComponentFileReferences;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+public class LSMRTreeWithAntiMatterTuplesComponentFactory implements ILSMComponentFactory {
+ private final TreeIndexFactory<RTree> rtreeFactory;
+
+ public LSMRTreeWithAntiMatterTuplesComponentFactory(TreeIndexFactory<RTree> rtreeFactory) {
+ this.rtreeFactory = rtreeFactory;
+ }
+
+ @Override
+ public ILSMComponent createLSMComponentInstance(LSMComponentFileReferences cfr) throws IndexException {
+ return new LSMRTreeImmutableComponent(rtreeFactory.createIndexInstance(cfr.getInsertIndexFileReference()),
+ null, null);
+ }
+
+ @Override
+ public IBufferCache getBufferCache() {
+ return rtreeFactory.getBufferCache();
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesFileManager.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesFileManager.java
new file mode 100644
index 0000000..10b982f
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesFileManager.java
@@ -0,0 +1,126 @@
+/*
+ * Copyright 2009-2012 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.lsm.rtree.impls;
+
+import java.io.File;
+import java.io.FilenameFilter;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Date;
+import java.util.List;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.api.io.IIOManager;
+import edu.uci.ics.hyracks.api.io.IODeviceHandle;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.AbstractLSMIndexFileManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMComponentFileReferences;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public class LSMRTreeWithAntiMatterTuplesFileManager extends AbstractLSMIndexFileManager {
+
+ private final TreeIndexFactory<? extends ITreeIndex> rtreeFactory;
+
+ public LSMRTreeWithAntiMatterTuplesFileManager(IIOManager ioManager, IFileMapProvider fileMapProvider,
+ FileReference file, TreeIndexFactory<? extends ITreeIndex> rtreeFactory, int startIODeviceIndex) {
+ super(ioManager, fileMapProvider, file, null, startIODeviceIndex);
+ this.rtreeFactory = rtreeFactory;
+ }
+
+ @Override
+ public LSMComponentFileReferences getRelFlushFileReference() {
+ Date date = new Date();
+ String ts = formatter.format(date);
+ // Begin timestamp and end timestamp are identical since it is a flush
+ return new LSMComponentFileReferences(createFlushFile(baseDir + ts + SPLIT_STRING + ts), null, null);
+ }
+
+ @Override
+ public LSMComponentFileReferences getRelMergeFileReference(String firstFileName, String lastFileName)
+ throws HyracksDataException {
+ String[] firstTimestampRange = firstFileName.split(SPLIT_STRING);
+ String[] lastTimestampRange = lastFileName.split(SPLIT_STRING);
+ // Get the range of timestamps by taking the earliest and the latest timestamps
+ return new LSMComponentFileReferences(createMergeFile(baseDir + firstTimestampRange[0] + SPLIT_STRING
+ + lastTimestampRange[1]), null, null);
+ }
+
+ private static FilenameFilter fileNameFilter = new FilenameFilter() {
+ public boolean accept(File dir, String name) {
+ return !name.startsWith(".");
+ }
+ };
+
+ @Override
+ public List<LSMComponentFileReferences> cleanupAndGetValidFiles() throws HyracksDataException, IndexException {
+ List<LSMComponentFileReferences> validFiles = new ArrayList<LSMComponentFileReferences>();
+ ArrayList<ComparableFileName> allFiles = new ArrayList<ComparableFileName>();
+
+ // Gather files from all IODeviceHandles and delete invalid files
+ // There are two types of invalid files:
+ // (1) The isValid flag is not set
+ // (2) The file's interval is contained by some other file
+ // Here, we only filter out (1).
+ for (IODeviceHandle dev : ioManager.getIODevices()) {
+ cleanupAndGetValidFilesInternal(dev, fileNameFilter, rtreeFactory, allFiles);
+ }
+
+ if (allFiles.isEmpty()) {
+ return validFiles;
+ }
+
+ if (allFiles.size() == 1) {
+ validFiles.add(new LSMComponentFileReferences(allFiles.get(0).fileRef, null, null));
+ return validFiles;
+ }
+
+ // Sorts files names from earliest to latest timestamp.
+ Collections.sort(allFiles);
+
+ List<ComparableFileName> validComparableFiles = new ArrayList<ComparableFileName>();
+ ComparableFileName last = allFiles.get(0);
+ validComparableFiles.add(last);
+ for (int i = 1; i < allFiles.size(); i++) {
+ ComparableFileName current = allFiles.get(i);
+ // The current start timestamp is greater than last stop timestamp so current is valid.
+ if (current.interval[0].compareTo(last.interval[1]) > 0) {
+ validComparableFiles.add(current);
+ last = current;
+ } else if (current.interval[0].compareTo(last.interval[0]) >= 0
+ && current.interval[1].compareTo(last.interval[1]) <= 0) {
+ // The current file is completely contained in the interval of the
+ // last file. Thus the last file must contain at least as much information
+ // as the current file, so delete the current file.
+ current.fileRef.delete();
+ } else {
+ // This scenario should not be possible since timestamps are monotonically increasing.
+ throw new HyracksDataException("Found LSM files with overlapping timestamp intervals, "
+ + "but the intervals were not contained by another file.");
+ }
+ }
+
+ // Sort valid files in reverse lexicographical order, such that newer files come first.
+ Collections.sort(validComparableFiles, recencyCmp);
+ for (ComparableFileName cmpFileName : validComparableFiles) {
+ validFiles.add(new LSMComponentFileReferences(cmpFileName.fileRef, null, null));
+ }
+
+ return validFiles;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesFlushCursor.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesFlushCursor.java
new file mode 100644
index 0000000..22e6929
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesFlushCursor.java
@@ -0,0 +1,164 @@
+/*
+ * 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.lsm.rtree.impls;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public class LSMRTreeWithAntiMatterTuplesFlushCursor implements ITreeIndexCursor {
+ private final TreeTupleSorter rTreeTupleSorter;
+ private final TreeTupleSorter bTreeTupleSorter;
+ private final int[] comparatorFields;
+ private final MultiComparator cmp;
+ private ITupleReference frameTuple;
+ private ITupleReference leftOverTuple;
+ private ITupleReference rtreeTuple;
+ private ITupleReference btreeTuple;
+ private boolean foundNext = false;
+
+ public LSMRTreeWithAntiMatterTuplesFlushCursor(TreeTupleSorter rTreeTupleSorter, TreeTupleSorter bTreeTupleSorter,
+ int[] comparatorFields, IBinaryComparatorFactory[] comparatorFactories) {
+ this.rTreeTupleSorter = rTreeTupleSorter;
+ this.bTreeTupleSorter = bTreeTupleSorter;
+ this.comparatorFields = comparatorFields;
+ cmp = MultiComparator.create(comparatorFactories);
+ }
+
+ @Override
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+
+ }
+
+ @Override
+ public boolean hasNext() throws HyracksDataException {
+ if (foundNext) {
+ return true;
+ }
+ while (true) {
+ if (leftOverTuple != null && leftOverTuple == rtreeTuple) {
+ if (bTreeTupleSorter.hasNext()) {
+ bTreeTupleSorter.next();
+ btreeTuple = bTreeTupleSorter.getTuple();
+ } else {
+ frameTuple = rtreeTuple;
+ foundNext = true;
+ leftOverTuple = null;
+ return true;
+ }
+ } else if (leftOverTuple != null && leftOverTuple == btreeTuple) {
+ if (rTreeTupleSorter.hasNext()) {
+ rTreeTupleSorter.next();
+ rtreeTuple = rTreeTupleSorter.getTuple();
+ } else {
+ frameTuple = btreeTuple;
+ foundNext = true;
+ leftOverTuple = null;
+ return true;
+ }
+ } else {
+ if (rTreeTupleSorter.hasNext() && bTreeTupleSorter.hasNext()) {
+ rTreeTupleSorter.next();
+ bTreeTupleSorter.next();
+ rtreeTuple = rTreeTupleSorter.getTuple();
+ btreeTuple = bTreeTupleSorter.getTuple();
+ } else if (rTreeTupleSorter.hasNext()) {
+ rTreeTupleSorter.next();
+ rtreeTuple = rTreeTupleSorter.getTuple();
+ frameTuple = rtreeTuple;
+ leftOverTuple = null;
+ foundNext = true;
+ return true;
+ } else if (bTreeTupleSorter.hasNext()) {
+ bTreeTupleSorter.next();
+ btreeTuple = bTreeTupleSorter.getTuple();
+ frameTuple = btreeTuple;
+ leftOverTuple = null;
+ foundNext = true;
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ int c = cmp.selectiveFieldCompare(rtreeTuple, btreeTuple, comparatorFields);
+ if (c == 0) {
+ leftOverTuple = null;
+ continue;
+ } else if (c < 0) {
+ frameTuple = rtreeTuple;
+ leftOverTuple = btreeTuple;
+ foundNext = true;
+ return true;
+ } else {
+ frameTuple = btreeTuple;
+ leftOverTuple = rtreeTuple;
+ foundNext = true;
+ return true;
+ }
+ }
+ }
+
+ @Override
+ public void next() throws HyracksDataException {
+ foundNext = false;
+
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ }
+
+ @Override
+ public void reset() throws HyracksDataException {
+
+ }
+
+ @Override
+ public ITupleReference getTuple() {
+ return frameTuple;
+ }
+
+ @Override
+ public ICachedPage getPage() {
+ return null;
+ }
+
+ @Override
+ public void setBufferCache(IBufferCache bufferCache) {
+ // TODO Auto-generated method stub
+
+ }
+
+ @Override
+ public void setFileId(int fileId) {
+ // TODO Auto-generated method stub
+
+ }
+
+ @Override
+ public boolean exclusiveLatchNodes() {
+ // TODO Auto-generated method stub
+ return false;
+ }
+
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesSearchCursor.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesSearchCursor.java
new file mode 100644
index 0000000..47d00c0
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeWithAntiMatterTuplesSearchCursor.java
@@ -0,0 +1,249 @@
+/*
+ * 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.lsm.rtree.impls;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+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.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMIndexSearchCursor;
+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.impls.RTreeSearchCursor;
+
+public class LSMRTreeWithAntiMatterTuplesSearchCursor extends LSMIndexSearchCursor {
+
+ private RTreeSearchCursor memRTreeCursor;
+ private BTreeRangeSearchCursor memBTreeCursor;
+ private RangePredicate btreeRangePredicate;
+ private ITreeIndexAccessor memBTreeAccessor;
+ private boolean foundNext;
+ private ITupleReference frameTuple;
+ private int[] comparatorFields;
+ private MultiComparator btreeCmp;
+
+ public LSMRTreeWithAntiMatterTuplesSearchCursor(ILSMIndexOperationContext opCtx) {
+ super(opCtx);
+ }
+
+ @Override
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+ LSMRTreeCursorInitialState lsmInitialState = (LSMRTreeCursorInitialState) initialState;
+ cmp = lsmInitialState.getHilbertCmp();
+ btreeCmp = lsmInitialState.getBTreeCmp();
+ int numDiskRTrees = lsmInitialState.getNumberOfTrees();
+ rangeCursors = new RTreeSearchCursor[numDiskRTrees];
+ for (int i = 0; i < numDiskRTrees; i++) {
+ rangeCursors[i] = new RTreeSearchCursor((IRTreeInteriorFrame) lsmInitialState
+ .getRTreeInteriorFrameFactory().createFrame(), (IRTreeLeafFrame) lsmInitialState
+ .getRTreeLeafFrameFactory().createFrame());
+ }
+ includeMemComponent = lsmInitialState.getIncludeMemComponent();
+ operationalComponents = lsmInitialState.getOperationalComponents();
+ if (includeMemComponent) {
+ memRTreeCursor = new RTreeSearchCursor((IRTreeInteriorFrame) lsmInitialState.getRTreeInteriorFrameFactory()
+ .createFrame(), (IRTreeLeafFrame) lsmInitialState.getRTreeLeafFrameFactory().createFrame());
+ memBTreeCursor = new BTreeRangeSearchCursor((IBTreeLeafFrame) lsmInitialState.getBTreeLeafFrameFactory()
+ .createFrame(), false);
+ memBTreeAccessor = lsmInitialState.getBTreeAccessors()[0];
+ btreeRangePredicate = new RangePredicate(null, null, true, true, btreeCmp, btreeCmp);
+ }
+ lsmHarness = lsmInitialState.getLSMHarness();
+ comparatorFields = lsmInitialState.getComparatorFields();
+ setPriorityQueueComparator();
+ }
+
+ @Override
+ public boolean hasNext() throws HyracksDataException, IndexException {
+ if (includeMemComponent) {
+ if (foundNext) {
+ return true;
+ }
+ while (memRTreeCursor.hasNext()) {
+ memRTreeCursor.next();
+ ITupleReference memRTreeTuple = memRTreeCursor.getTuple();
+ if (searchMemBTree(memRTreeTuple)) {
+ foundNext = true;
+ frameTuple = memRTreeTuple;
+ return true;
+ }
+ }
+ while (super.hasNext()) {
+ super.next();
+ ITupleReference diskRTreeTuple = super.getTuple();
+ if (searchMemBTree(diskRTreeTuple)) {
+ foundNext = true;
+ frameTuple = diskRTreeTuple;
+ return true;
+ }
+ }
+ } else {
+ return super.hasNext();
+ }
+
+ return false;
+ }
+
+ @Override
+ public void next() throws HyracksDataException {
+ if (includeMemComponent) {
+ foundNext = false;
+ } else {
+ super.next();
+ }
+
+ }
+
+ @Override
+ public ITupleReference getTuple() {
+ if (includeMemComponent) {
+ return frameTuple;
+ } else {
+ return super.getTuple();
+ }
+
+ }
+
+ @Override
+ public void reset() throws HyracksDataException, IndexException {
+ if (includeMemComponent) {
+ memRTreeCursor.reset();
+ memBTreeCursor.reset();
+ }
+ super.reset();
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ if (includeMemComponent) {
+ memRTreeCursor.close();
+ memBTreeCursor.close();
+ }
+ super.close();
+ }
+
+ public ITreeIndexCursor getMemRTreeCursor() {
+ return memRTreeCursor;
+ }
+
+ @Override
+ protected int compare(MultiComparator cmp, ITupleReference tupleA, ITupleReference tupleB) {
+ return cmp.selectiveFieldCompare(tupleA, tupleB, comparatorFields);
+ }
+
+ private boolean searchMemBTree(ITupleReference tuple) throws HyracksDataException {
+ try {
+ btreeRangePredicate.setHighKey(tuple, true);
+ btreeRangePredicate.setLowKey(tuple, true);
+ memBTreeAccessor.search(memBTreeCursor, btreeRangePredicate);
+ } catch (IndexException e) {
+ throw new HyracksDataException(e);
+ }
+ try {
+ if (memBTreeCursor.hasNext()) {
+ return false;
+ } else {
+ return true;
+ }
+ } finally {
+ memBTreeCursor.close();
+ }
+ }
+
+ @Override
+ protected void setPriorityQueueComparator() {
+ if (pqCmp == null || cmp != pqCmp.getMultiComparator()) {
+ pqCmp = new PriorityQueueHilbertComparator(cmp, comparatorFields);
+ }
+ }
+
+ public class PriorityQueueHilbertComparator extends PriorityQueueComparator {
+
+ private final int[] comparatorFields;
+
+ public PriorityQueueHilbertComparator(MultiComparator cmp, int[] comparatorFields) {
+ super(cmp);
+ this.comparatorFields = comparatorFields;
+ }
+
+ @Override
+ public int compare(PriorityQueueElement elementA, PriorityQueueElement elementB) {
+ int result = cmp.selectiveFieldCompare(elementA.getTuple(), elementB.getTuple(), comparatorFields);
+ if (result != 0) {
+ return result;
+ }
+ if (elementA.getCursorIndex() > elementB.getCursorIndex()) {
+ return 1;
+ } else {
+ return -1;
+ }
+ }
+ }
+
+ @Override
+ protected void checkPriorityQueue() throws HyracksDataException, IndexException {
+ while (!outputPriorityQueue.isEmpty() || needPush == true) {
+ if (!outputPriorityQueue.isEmpty()) {
+ PriorityQueueElement checkElement = outputPriorityQueue.peek();
+ // If there is no previous tuple or the previous tuple can be ignored
+ if (outputElement == null) {
+ if (isDeleted(checkElement)) {
+ // If the key has been deleted then pop it and set needPush to true.
+ // We cannot push immediately because the tuple may be
+ // modified if hasNext() is called
+ outputElement = outputPriorityQueue.poll();
+ needPush = true;
+ } else {
+ break;
+ }
+ } else {
+ // Compare the previous tuple and the head tuple in the PQ
+ if (compare(cmp, outputElement.getTuple(), checkElement.getTuple()) == 0) {
+ // If the previous tuple and the head tuple are
+ // identical
+ // then pop the head tuple and push the next tuple from
+ // the tree of head tuple
+
+ // the head element of PQ is useless now
+ PriorityQueueElement e = outputPriorityQueue.poll();
+ pushIntoPriorityQueue(e);
+ } else {
+ // If the previous tuple and the head tuple are different
+ // the info of previous tuple is useless
+ if (needPush == true) {
+ pushIntoPriorityQueue(outputElement);
+ needPush = false;
+ }
+ outputElement = null;
+ }
+ }
+ } else {
+ // the priority queue is empty and needPush
+ pushIntoPriorityQueue(outputElement);
+ needPush = false;
+ outputElement = null;
+ }
+ }
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/RTreeFactory.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/RTreeFactory.java
new file mode 100644
index 0000000..71e228b
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/RTreeFactory.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.lsm.rtree.impls;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManagerFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public class RTreeFactory extends TreeIndexFactory<RTree> {
+
+ public RTreeFactory(IBufferCache bufferCache, IFileMapProvider fileMapProvider,
+ IFreePageManagerFactory freePageManagerFactory, ITreeIndexFrameFactory interiorFrameFactory,
+ ITreeIndexFrameFactory leafFrameFactory, IBinaryComparatorFactory[] cmpFactories, int fieldCount) {
+ super(bufferCache, fileMapProvider, freePageManagerFactory, interiorFrameFactory, leafFrameFactory,
+ cmpFactories, fieldCount);
+ }
+
+ @Override
+ public RTree createIndexInstance(FileReference file) throws IndexException {
+ return new RTree(bufferCache, fileMapProvider, freePageManagerFactory.createFreePageManager(),
+ interiorFrameFactory, leafFrameFactory, cmpFactories, fieldCount, file);
+ }
+
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/TreeTupleSorter.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/TreeTupleSorter.java
new file mode 100644
index 0000000..294c2b8
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/TreeTupleSorter.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.lsm.rtree.impls;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+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;
+
+public class TreeTupleSorter implements ITreeIndexCursor {
+ private final static int INITIAL_SIZE = 1000000;
+ private int numTuples;
+ private int currentTupleIndex;
+ private int[] tPointers;
+ private IBufferCache bufferCache;
+ private final ITreeIndexFrame leafFrame1;
+ private final ITreeIndexFrame leafFrame2;
+ private ITreeIndexTupleReference frameTuple1;
+ private ITreeIndexTupleReference frameTuple2;
+ private final int fileId;
+ private final static int ARRAY_GROWTH = 1000000; // Must be at least of size 2
+ private final int[] comparatorFields;
+ private final MultiComparator cmp;
+
+ public TreeTupleSorter(int fileId, IBinaryComparatorFactory[] comparatorFactories, ITreeIndexFrame leafFrame1,
+ ITreeIndexFrame leafFrame2, IBufferCache bufferCache, int[] comparatorFields) {
+ this.fileId = fileId;
+ this.leafFrame1 = leafFrame1;
+ this.leafFrame2 = leafFrame2;
+ this.bufferCache = bufferCache;
+ this.comparatorFields = comparatorFields;
+ tPointers = new int[INITIAL_SIZE * 2];
+ frameTuple1 = leafFrame1.createTupleReference();
+ frameTuple2 = leafFrame2.createTupleReference();
+ currentTupleIndex = 0;
+ cmp = MultiComparator.create(comparatorFactories);
+ }
+
+ public void reset() {
+ numTuples = 0;
+ currentTupleIndex = 0;
+ }
+
+ public boolean hasNext() throws HyracksDataException {
+ if (numTuples <= currentTupleIndex) {
+ return false;
+ }
+ // We don't latch pages since this code is only used by flush () before
+ // bulk-loading the r-tree to disk and flush is not concurrent.
+ //
+ ICachedPage node1 = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, tPointers[currentTupleIndex * 2]),
+ false);
+ try {
+ leafFrame1.setPage(node1);
+ frameTuple1.resetByTupleOffset(leafFrame1.getBuffer(), tPointers[currentTupleIndex * 2 + 1]);
+ } finally {
+ bufferCache.unpin(node1);
+ }
+ return true;
+ }
+
+ public void next() {
+ currentTupleIndex++;
+ }
+
+ public ITupleReference getTuple() {
+ return frameTuple1;
+ }
+
+ public void insertTupleEntry(int pageId, int tupleOffset) {
+ if (numTuples * 2 == tPointers.length) {
+ int[] newData = new int[tPointers.length + ARRAY_GROWTH];
+ System.arraycopy(tPointers, 0, newData, 0, tPointers.length);
+ tPointers = newData;
+ }
+
+ tPointers[numTuples * 2] = pageId;
+ tPointers[numTuples * 2 + 1] = tupleOffset;
+ numTuples++;
+ }
+
+ public void sort() throws HyracksDataException {
+ sort(tPointers, 0, numTuples);
+ }
+
+ private void sort(int[] tPointers, int offset, int length) throws HyracksDataException {
+ int m = offset + (length >> 1);
+ int mi = tPointers[m * 2];
+ int mj = tPointers[m * 2 + 1];
+
+ int a = offset;
+ int b = a;
+ int c = offset + length - 1;
+ int d = c;
+ while (true) {
+ while (b <= c) {
+ int cmp = compare(tPointers, b, mi, mj);
+ if (cmp > 0) {
+ break;
+ }
+ if (cmp == 0) {
+ swap(tPointers, a++, b);
+ }
+ ++b;
+ }
+ while (c >= b) {
+ int cmp = compare(tPointers, c, mi, mj);
+ if (cmp < 0) {
+ break;
+ }
+ if (cmp == 0) {
+ swap(tPointers, c, d--);
+ }
+ --c;
+ }
+ if (b > c)
+ break;
+ swap(tPointers, b++, c--);
+ }
+
+ int s;
+ int n = offset + length;
+ s = Math.min(a - offset, b - a);
+ vecswap(tPointers, offset, b - s, s);
+ s = Math.min(d - c, n - d - 1);
+ vecswap(tPointers, b, n - s, s);
+
+ if ((s = b - a) > 1) {
+ sort(tPointers, offset, s);
+ }
+ if ((s = d - c) > 1) {
+ sort(tPointers, n - s, s);
+ }
+ }
+
+ private void swap(int x[], int a, int b) {
+ for (int i = 0; i < 2; ++i) {
+ int t = x[a * 2 + i];
+ x[a * 2 + i] = x[b * 2 + i];
+ x[b * 2 + i] = t;
+ }
+ }
+
+ private void vecswap(int x[], int a, int b, int n) {
+ for (int i = 0; i < n; i++, a++, b++) {
+ swap(x, a, b);
+ }
+ }
+
+ private int compare(int[] tPointers, int tp1, int tp2i, int tp2j) throws HyracksDataException {
+ int i1 = tPointers[tp1 * 2];
+ int j1 = tPointers[tp1 * 2 + 1];
+
+ int i2 = tp2i;
+ int j2 = tp2j;
+
+ ICachedPage node1 = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, i1), false);
+ leafFrame1.setPage(node1);
+ ICachedPage node2 = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, i2), false);
+ leafFrame2.setPage(node2);
+
+ try {
+ frameTuple1.resetByTupleOffset(leafFrame1.getBuffer(), j1);
+ frameTuple2.resetByTupleOffset(leafFrame2.getBuffer(), j2);
+
+ return cmp.selectiveFieldCompare(frameTuple1, frameTuple2, comparatorFields);
+
+ } finally {
+ bufferCache.unpin(node1);
+ bufferCache.unpin(node2);
+ }
+ }
+
+ @Override
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+ // do nothing
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ // do nothing
+ }
+
+ @Override
+ public ICachedPage getPage() {
+ return null;
+ }
+
+ @Override
+ public void setBufferCache(IBufferCache bufferCache) {
+ // do nothing
+ }
+
+ @Override
+ public void setFileId(int fileId) {
+ // do nothing
+ }
+
+ @Override
+ public boolean exclusiveLatchNodes() {
+ return false;
+ }
+
+}
\ No newline at end of file
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeCopyTupleWriter.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeCopyTupleWriter.java
new file mode 100644
index 0000000..1852b51
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeCopyTupleWriter.java
@@ -0,0 +1,35 @@
+/*
+ * 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.lsm.rtree.tuples;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+
+public class LSMRTreeCopyTupleWriter extends LSMRTreeTupleWriter {
+ public LSMRTreeCopyTupleWriter(ITypeTraits[] typeTraits) {
+ // Third parameter is never used locally, just give false.
+ super(typeTraits, false);
+ }
+
+ @Override
+ public int writeTuple(ITupleReference tuple, byte[] targetBuf, int targetOff) {
+ int tupleSize = bytesRequired(tuple);
+ byte[] buf = tuple.getFieldData(0);
+ int tupleStartOff = ((LSMRTreeTupleReference) tuple).getTupleStart();
+ System.arraycopy(buf, tupleStartOff, targetBuf, targetOff, tupleSize);
+ return tupleSize;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeCopyTupleWriterFactory.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeCopyTupleWriterFactory.java
new file mode 100644
index 0000000..39a8e4d
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeCopyTupleWriterFactory.java
@@ -0,0 +1,35 @@
+/*
+ * 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.lsm.rtree.tuples;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+
+public class LSMRTreeCopyTupleWriterFactory extends TypeAwareTupleWriterFactory {
+ private static final long serialVersionUID = 1L;
+ private final ITypeTraits[] typeTraits;
+
+ public LSMRTreeCopyTupleWriterFactory(ITypeTraits[] typeTraits) {
+ super(typeTraits);
+ this.typeTraits = typeTraits;
+ }
+
+ @Override
+ public ITreeIndexTupleWriter createTupleWriter() {
+ return new LSMRTreeCopyTupleWriter(typeTraits);
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeTupleReference.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeTupleReference.java
new file mode 100644
index 0000000..70072e1
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeTupleReference.java
@@ -0,0 +1,47 @@
+/*
+ * 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.lsm.rtree.tuples;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleReference;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMTreeTupleReference;
+
+public class LSMRTreeTupleReference extends TypeAwareTupleReference implements ILSMTreeTupleReference {
+
+ public LSMRTreeTupleReference(ITypeTraits[] typeTraits) {
+ super(typeTraits);
+ }
+
+ @Override
+ protected int getNullFlagsBytes() {
+ // +1.0 is for matter/antimatter bit.
+ return (int) Math.ceil((fieldCount + 1.0) / 8.0);
+ }
+
+ @Override
+ public boolean isAntimatter() {
+ // Check if the leftmost bit is 0 or 1.
+ final byte mask = (byte) (1 << 7);
+ if ((buf.array()[tupleStartOff] & mask) != 0) {
+ return true;
+ }
+ return false;
+ }
+
+ public int getTupleStart() {
+ return tupleStartOff;
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeTupleWriter.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeTupleWriter.java
new file mode 100644
index 0000000..932a307
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeTupleWriter.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.lsm.rtree.tuples;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriter;
+
+public class LSMRTreeTupleWriter extends RTreeTypeAwareTupleWriter {
+ private final boolean isAntimatter;
+
+ public LSMRTreeTupleWriter(ITypeTraits[] typeTraits, boolean isAntimatter) {
+ super(typeTraits);
+ this.isAntimatter = isAntimatter;
+ }
+
+ @Override
+ public ITreeIndexTupleReference createTupleReference() {
+ return new LSMRTreeTupleReference(typeTraits);
+ }
+
+ @Override
+ public int bytesRequired(ITupleReference tuple) {
+ return super.bytesRequired(tuple);
+ }
+
+ @Override
+ public int writeTuple(ITupleReference tuple, byte[] targetBuf, int targetOff) {
+ int bytesWritten = super.writeTuple(tuple, targetBuf, targetOff);
+ if (isAntimatter) {
+ setAntimatterBit(targetBuf, targetOff);
+ }
+ return bytesWritten;
+ }
+
+ @Override
+ protected int getNullFlagsBytes(int numFields) {
+ // +1.0 is for matter/antimatter bit.
+ return (int) Math.ceil(((double) numFields + 1.0) / 8.0);
+ }
+
+ @Override
+ protected int getNullFlagsBytes(ITupleReference tuple) {
+ // +1.0 is for matter/antimatter bit.
+ return (int) Math.ceil(((double) tuple.getFieldCount() + 1.0) / 8.0);
+ }
+
+ protected void setAntimatterBit(byte[] targetBuf, int targetOff) {
+ // Set leftmost bit to 1.
+ targetBuf[targetOff] = (byte) (targetBuf[targetOff] | (1 << 7));
+ }
+
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeTupleWriterFactory.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeTupleWriterFactory.java
new file mode 100644
index 0000000..493d368
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMRTreeTupleWriterFactory.java
@@ -0,0 +1,38 @@
+/*
+ * 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.lsm.rtree.tuples;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+
+public class LSMRTreeTupleWriterFactory extends TypeAwareTupleWriterFactory {
+
+ private static final long serialVersionUID = 1L;
+ private final ITypeTraits[] typeTraits;
+ private final boolean isDelete;
+
+ public LSMRTreeTupleWriterFactory(ITypeTraits[] typeTraits, boolean isDelete) {
+ super(typeTraits);
+ this.typeTraits = typeTraits;
+ this.isDelete = isDelete;
+ }
+
+ @Override
+ public ITreeIndexTupleWriter createTupleWriter() {
+ return new LSMRTreeTupleWriter(typeTraits, isDelete);
+ }
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMTypeAwareTupleWriterFactory.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMTypeAwareTupleWriterFactory.java
new file mode 100644
index 0000000..876df56
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/tuples/LSMTypeAwareTupleWriterFactory.java
@@ -0,0 +1,30 @@
+package edu.uci.ics.hyracks.storage.am.lsm.rtree.tuples;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriter;
+
+public class LSMTypeAwareTupleWriterFactory extends TypeAwareTupleWriterFactory {
+
+ private static final long serialVersionUID = 1L;
+ private ITypeTraits[] typeTraits;
+ private final boolean isDelete;
+
+ public LSMTypeAwareTupleWriterFactory(ITypeTraits[] typeTraits, boolean isDelete) {
+ super(typeTraits);
+ this.typeTraits = typeTraits;
+ this.isDelete = isDelete;
+ }
+
+ @Override
+ public ITreeIndexTupleWriter createTupleWriter() {
+ if (isDelete) {
+ return new TypeAwareTupleWriter(typeTraits);
+ } else {
+ return new RTreeTypeAwareTupleWriter(typeTraits);
+ }
+ }
+
+}
diff --git a/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java
new file mode 100644
index 0000000..6c9fce6
--- /dev/null
+++ b/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java
@@ -0,0 +1,211 @@
+/*
+ * Copyright 2009-2012 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.lsm.rtree.utils;
+
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ILinearizeComparatorFactory;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.api.io.IIOManager;
+import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.storage.am.bloomfilter.impls.BloomFilterFactory;
+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.IInMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+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.LinkedListFreePageManagerFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.IInMemoryBufferCache;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationCallbackProvider;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperationScheduler;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexFileManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMMergePolicy;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMOperationTrackerFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.BTreeFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTree;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTreeFileManager;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTreeWithAntiMatterTuples;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTreeWithAntiMatterTuplesFileManager;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.RTreeFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.tuples.LSMRTreeCopyTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.tuples.LSMRTreeTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.rtree.tuples.LSMTypeAwareTupleWriterFactory;
+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.frames.RTreePolicyType;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.linearize.HilbertDoubleComparatorFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.linearize.ZCurveDoubleComparatorFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.linearize.ZCurveIntComparatorFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+
+public class LSMRTreeUtils {
+ public static LSMRTree createLSMTree(IInMemoryBufferCache memBufferCache,
+ IInMemoryFreePageManager memFreePageManager, IIOManager ioManager, FileReference file,
+ IBufferCache diskBufferCache, IFileMapProvider diskFileMapProvider, ITypeTraits[] typeTraits,
+ IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILSMMergePolicy mergePolicy, ILSMOperationTrackerFactory opTrackerFactory,
+ ILSMIOOperationScheduler ioScheduler, ILSMIOOperationCallbackProvider ioOpCallbackProvider,
+ ILinearizeComparatorFactory linearizeCmpFactory) throws TreeIndexException {
+ return createLSMTree(memBufferCache, memFreePageManager, ioManager, file, diskBufferCache, diskFileMapProvider,
+ typeTraits, rtreeCmpFactories, btreeCmpFactories, valueProviderFactories, rtreePolicyType, mergePolicy,
+ opTrackerFactory, ioScheduler, ioOpCallbackProvider, linearizeCmpFactory, 0);
+ }
+
+ public static LSMRTree createLSMTree(IInMemoryBufferCache memBufferCache,
+ IInMemoryFreePageManager memFreePageManager, IIOManager ioManager, FileReference file,
+ IBufferCache diskBufferCache, IFileMapProvider diskFileMapProvider, ITypeTraits[] typeTraits,
+ IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILSMMergePolicy mergePolicy, ILSMOperationTrackerFactory opTrackerFactory,
+ ILSMIOOperationScheduler ioScheduler, ILSMIOOperationCallbackProvider ioOpCallbackProvider,
+ ILinearizeComparatorFactory linearizeCmpFactory, int startIODeviceIndex) throws TreeIndexException {
+ LSMTypeAwareTupleWriterFactory rtreeTupleWriterFactory = new LSMTypeAwareTupleWriterFactory(typeTraits, false);
+ LSMTypeAwareTupleWriterFactory btreeTupleWriterFactory = new LSMTypeAwareTupleWriterFactory(typeTraits, true);
+
+ ITreeIndexFrameFactory rtreeInteriorFrameFactory = new RTreeNSMInteriorFrameFactory(rtreeTupleWriterFactory,
+ valueProviderFactories, rtreePolicyType);
+ ITreeIndexFrameFactory rtreeLeafFrameFactory = new RTreeNSMLeafFrameFactory(rtreeTupleWriterFactory,
+ valueProviderFactories, rtreePolicyType);
+
+ ITreeIndexFrameFactory btreeInteriorFrameFactory = new BTreeNSMInteriorFrameFactory(btreeTupleWriterFactory);
+ ITreeIndexFrameFactory btreeLeafFrameFactory = new BTreeNSMLeafFrameFactory(btreeTupleWriterFactory);
+
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+ LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(diskBufferCache,
+ metaFrameFactory);
+
+ TreeIndexFactory<RTree> diskRTreeFactory = new RTreeFactory(diskBufferCache, diskFileMapProvider,
+ freePageManagerFactory, rtreeInteriorFrameFactory, rtreeLeafFrameFactory, rtreeCmpFactories,
+ typeTraits.length);
+ TreeIndexFactory<BTree> diskBTreeFactory = new BTreeFactory(diskBufferCache, diskFileMapProvider,
+ freePageManagerFactory, btreeInteriorFrameFactory, btreeLeafFrameFactory, btreeCmpFactories,
+ typeTraits.length);
+
+ int[] comparatorFields = { 0 };
+ IBinaryComparatorFactory[] linearizerArray = { linearizeCmpFactory };
+
+ int[] bloomFilterKeyFields = new int[btreeCmpFactories.length];
+ for (int i = 0; i < btreeCmpFactories.length; i++) {
+ bloomFilterKeyFields[i] = i;
+ }
+ BloomFilterFactory bloomFilterFactory = new BloomFilterFactory(diskBufferCache, diskFileMapProvider,
+ bloomFilterKeyFields);
+
+ ILSMIndexFileManager fileNameManager = new LSMRTreeFileManager(ioManager, diskFileMapProvider, file,
+ diskRTreeFactory, diskBTreeFactory, startIODeviceIndex);
+ LSMRTree lsmTree = new LSMRTree(memBufferCache, memFreePageManager, rtreeInteriorFrameFactory,
+ rtreeLeafFrameFactory, btreeInteriorFrameFactory, btreeLeafFrameFactory, fileNameManager,
+ diskRTreeFactory, diskBTreeFactory, bloomFilterFactory, diskFileMapProvider, typeTraits.length,
+ rtreeCmpFactories, btreeCmpFactories, linearizeCmpFactory, comparatorFields, linearizerArray,
+ mergePolicy, opTrackerFactory, ioScheduler, ioOpCallbackProvider);
+ return lsmTree;
+ }
+
+ public static LSMRTreeWithAntiMatterTuples createLSMTreeWithAntiMatterTuples(IInMemoryBufferCache memBufferCache,
+ IInMemoryFreePageManager memFreePageManager, IIOManager ioManager, FileReference file,
+ IBufferCache diskBufferCache, IFileMapProvider diskFileMapProvider, ITypeTraits[] typeTraits,
+ IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILSMMergePolicy mergePolicy, ILSMOperationTrackerFactory opTrackerFactory,
+ ILSMIOOperationScheduler ioScheduler, ILSMIOOperationCallbackProvider ioOpCallbackProvider,
+ ILinearizeComparatorFactory linearizerCmpFactory) throws TreeIndexException {
+ return createLSMTreeWithAntiMatterTuples(memBufferCache, memFreePageManager, ioManager, file, diskBufferCache,
+ diskFileMapProvider, typeTraits, rtreeCmpFactories, btreeCmpFactories, valueProviderFactories,
+ rtreePolicyType, mergePolicy, opTrackerFactory, ioScheduler, ioOpCallbackProvider,
+ linearizerCmpFactory, 0);
+ }
+
+ public static LSMRTreeWithAntiMatterTuples createLSMTreeWithAntiMatterTuples(IInMemoryBufferCache memBufferCache,
+ IInMemoryFreePageManager memFreePageManager, IIOManager ioManager, FileReference file,
+ IBufferCache diskBufferCache, IFileMapProvider diskFileMapProvider, ITypeTraits[] typeTraits,
+ IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories,
+ IPrimitiveValueProviderFactory[] valueProviderFactories, RTreePolicyType rtreePolicyType,
+ ILSMMergePolicy mergePolicy, ILSMOperationTrackerFactory opTrackerFactory,
+ ILSMIOOperationScheduler ioScheduler, ILSMIOOperationCallbackProvider ioOpCallbackProvider,
+ ILinearizeComparatorFactory linearizerCmpFactory, int startIODeviceIndex) throws TreeIndexException {
+
+ LSMRTreeTupleWriterFactory rtreeTupleWriterFactory = new LSMRTreeTupleWriterFactory(typeTraits, false);
+ LSMRTreeTupleWriterFactory btreeTupleWriterFactory = new LSMRTreeTupleWriterFactory(typeTraits, true);
+
+ LSMRTreeCopyTupleWriterFactory copyTupleWriterFactory = new LSMRTreeCopyTupleWriterFactory(typeTraits);
+
+ ITreeIndexFrameFactory rtreeInteriorFrameFactory = new RTreeNSMInteriorFrameFactory(rtreeTupleWriterFactory,
+ valueProviderFactories, rtreePolicyType);
+ ITreeIndexFrameFactory rtreeLeafFrameFactory = new RTreeNSMLeafFrameFactory(rtreeTupleWriterFactory,
+ valueProviderFactories, rtreePolicyType);
+
+ ITreeIndexFrameFactory btreeInteriorFrameFactory = new BTreeNSMInteriorFrameFactory(btreeTupleWriterFactory);
+ ITreeIndexFrameFactory btreeLeafFrameFactory = new BTreeNSMLeafFrameFactory(btreeTupleWriterFactory);
+
+ ITreeIndexFrameFactory copyTupleLeafFrameFactory = new RTreeNSMLeafFrameFactory(copyTupleWriterFactory,
+ valueProviderFactories, rtreePolicyType);
+
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+ LinkedListFreePageManagerFactory freePageManagerFactory = new LinkedListFreePageManagerFactory(diskBufferCache,
+ metaFrameFactory);
+
+ TreeIndexFactory<RTree> diskRTreeFactory = new RTreeFactory(diskBufferCache, diskFileMapProvider,
+ freePageManagerFactory, rtreeInteriorFrameFactory, copyTupleLeafFrameFactory, rtreeCmpFactories,
+ typeTraits.length);
+
+ TreeIndexFactory<RTree> bulkLoadRTreeFactory = new RTreeFactory(diskBufferCache, diskFileMapProvider,
+ freePageManagerFactory, rtreeInteriorFrameFactory, rtreeLeafFrameFactory, rtreeCmpFactories,
+ typeTraits.length);
+
+ // The first field is for the sorted curve (e.g. Hilbert curve), and the
+ // second field is for the primary key.
+ int[] comparatorFields = { 0, btreeCmpFactories.length - 1 };
+ IBinaryComparatorFactory[] linearizerArray = { linearizerCmpFactory,
+ btreeCmpFactories[btreeCmpFactories.length - 1] };
+
+ ILSMIndexFileManager fileNameManager = new LSMRTreeWithAntiMatterTuplesFileManager(ioManager,
+ diskFileMapProvider, file, diskRTreeFactory, startIODeviceIndex);
+ LSMRTreeWithAntiMatterTuples lsmTree = new LSMRTreeWithAntiMatterTuples(memBufferCache, memFreePageManager,
+ rtreeInteriorFrameFactory, rtreeLeafFrameFactory, btreeInteriorFrameFactory, btreeLeafFrameFactory,
+ fileNameManager, diskRTreeFactory, bulkLoadRTreeFactory, diskFileMapProvider, typeTraits.length,
+ rtreeCmpFactories, btreeCmpFactories, linearizerCmpFactory, comparatorFields, linearizerArray,
+ mergePolicy, opTrackerFactory, ioScheduler, ioOpCallbackProvider);
+ return lsmTree;
+ }
+
+ public static ILinearizeComparatorFactory proposeBestLinearizer(ITypeTraits[] typeTraits, int numKeyFields)
+ throws TreeIndexException {
+ for (int i = 0; i < numKeyFields; i++) {
+ if (!(typeTraits[i].getClass().equals(typeTraits[0].getClass()))) {
+ throw new TreeIndexException("Cannot propose linearizer if dimensions have different types");
+ }
+ }
+
+ if (numKeyFields / 2 == 2 && (typeTraits[0].getClass() == DoublePointable.TYPE_TRAITS.getClass())) {
+ return new HilbertDoubleComparatorFactory(2);
+ } else if (typeTraits[0].getClass() == DoublePointable.TYPE_TRAITS.getClass()) {
+ return new ZCurveDoubleComparatorFactory(numKeyFields / 2);
+ } else if (typeTraits[0].getClass() == IntegerPointable.TYPE_TRAITS.getClass()) {
+ return new ZCurveIntComparatorFactory(numKeyFields / 2);
+ }
+
+ throw new TreeIndexException("Cannot propose linearizer");
+ }
+}