* Created new projects for the LSM-Rtree.
* Added test files.
* Refactored some code.
* Fixed couple of bugs in the r-tree code.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@969 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-lsmtree-common/pom.xml b/hyracks-storage-am-lsmtree-common/pom.xml
new file mode 100644
index 0000000..3a02f53
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-common/pom.xml
@@ -0,0 +1,42 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-lsmtree-common</artifactId>
+ <version>0.2.0-SNAPSHOT</version>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks</artifactId>
+ <version>0.2.0-SNAPSHOT</version>
+ </parent>
+
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-compiler-plugin</artifactId>
+ <version>2.0.2</version>
+ <configuration>
+ <source>1.6</source>
+ <target>1.6</target>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+ <dependencies>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-common</artifactId>
+ <version>0.2.0-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <version>4.8.1</version>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
+ </dependencies>
+</project>
diff --git a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/api/ILSMTree.java b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/api/ILSMTree.java
new file mode 100644
index 0000000..46cdc2e
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/api/ILSMTree.java
@@ -0,0 +1,9 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.common.api;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+
+public interface ILSMTree extends ITreeIndex {
+ public void merge() throws Exception;
+
+ public void flush() throws Exception;
+}
diff --git a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/FreePageManagerFactory.java b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/FreePageManagerFactory.java
new file mode 100644
index 0000000..a0591a6
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/FreePageManagerFactory.java
@@ -0,0 +1,23 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.common.impls;
+
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+
+public class FreePageManagerFactory {
+
+ private final ITreeIndexMetaDataFrameFactory metaDataFrameFactory;
+ private final IBufferCache bufferCache;
+
+ public FreePageManagerFactory(IBufferCache bufferCache, ITreeIndexMetaDataFrameFactory metaDataFrameFactory) {
+ this.metaDataFrameFactory = metaDataFrameFactory;
+ this.bufferCache = bufferCache;
+ }
+
+ public IFreePageManager createFreePageManager(int fileId) {
+ return new LinkedListFreePageManager(bufferCache, fileId, 0, metaDataFrameFactory);
+ }
+
+}
diff --git a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/InMemoryBufferCache.java b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/InMemoryBufferCache.java
new file mode 100644
index 0000000..72ab9c4
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/InMemoryBufferCache.java
@@ -0,0 +1,146 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.common.impls;
+
+import java.nio.ByteBuffer;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCacheInternal;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICacheMemoryAllocator;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPageInternal;
+import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
+
+public class InMemoryBufferCache implements IBufferCacheInternal {
+
+ private final int pageSize;
+ private final int numPages;
+ private final CachedPage[] cachedPages;
+
+ //Constructor
+ public InMemoryBufferCache(ICacheMemoryAllocator allocator, int pageSize, int numPages){
+
+ this.pageSize = pageSize;
+ this.numPages = numPages;
+ ByteBuffer[] buffers = allocator.allocate(this.pageSize, this.numPages);
+ cachedPages = new CachedPage[buffers.length];
+ for (int i = 0; i < buffers.length; ++i) {
+ cachedPages[i] = new CachedPage(i, buffers[i]);
+ }
+ }
+
+ @Override
+ public void createFile(FileReference fileRef) throws HyracksDataException {
+ // Do nothing
+ }
+
+ @Override
+ public void openFile(int fileId) throws HyracksDataException {
+ // Do nothing
+ }
+
+ @Override
+ public void closeFile(int fileId) throws HyracksDataException {
+ // Do nothing
+ }
+
+ @Override
+ public void deleteFile(int fileId) throws HyracksDataException {
+ // Do nothing
+ }
+
+ @Override
+ public ICachedPage tryPin(long dpid) throws HyracksDataException {
+ // Just call pin!
+ return null;
+ }
+
+ @Override
+ public ICachedPage pin(long dpid, boolean newPage){
+ return cachedPages[BufferedFileHandle.getPageId(dpid)];
+ }
+
+ @Override
+ public void unpin(ICachedPage page) throws HyracksDataException {
+ //Do Nothing
+ }
+
+ @Override
+ public int getPageSize() {
+ return pageSize;
+ }
+
+ @Override
+ public int getNumPages() {
+ return numPages;
+ }
+
+ @Override
+ public void close() {
+ // Do nothing
+ }
+
+ @Override
+ public ICachedPageInternal getPage(int cpid) {
+ return cachedPages[cpid];
+ }
+
+ private class CachedPage implements ICachedPageInternal {
+ private final int cpid;
+ private final ByteBuffer buffer;
+ private final ReadWriteLock latch;
+
+ public CachedPage(int cpid, ByteBuffer buffer) {
+ this.cpid = cpid;
+ this.buffer = buffer;
+ latch = new ReentrantReadWriteLock(true);
+ }
+
+ @Override
+ public ByteBuffer getBuffer() {
+ return buffer;
+ }
+
+ @Override
+ public Object getReplacementStrategyObject() {
+ //Do nothing
+ return null;
+ }
+
+ @Override
+ public boolean pinIfGoodVictim() {
+ //Do nothing
+ return false;
+ }
+
+ @Override
+ public int getCachedPageId() {
+ return cpid;
+ }
+
+ @Override
+ public void acquireReadLatch() {
+ latch.readLock().lock();
+ }
+
+ private void acquireWriteLatch(boolean markDirty) {
+ latch.writeLock().lock();
+ }
+
+ @Override
+ public void acquireWriteLatch() {
+ acquireWriteLatch(true);
+ }
+
+ @Override
+ public void releaseReadLatch() {
+ latch.readLock().unlock();
+ }
+
+ @Override
+ public void releaseWriteLatch() {
+ latch.writeLock().unlock();
+ }
+ }
+}
diff --git a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/InMemoryBufferCacheFactory.java b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/InMemoryBufferCacheFactory.java
new file mode 100644
index 0000000..fca8dc4
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/InMemoryBufferCacheFactory.java
@@ -0,0 +1,26 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.common.impls;
+
+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.buffercache.ICacheMemoryAllocator;
+
+public class InMemoryBufferCacheFactory {
+
+ private IBufferCache bufferCache;
+ private final int pageSize;
+ private final int numPages;
+
+ public InMemoryBufferCacheFactory(int pageSize, int numPages) {
+ this.pageSize = pageSize;
+ this.numPages = numPages;
+ bufferCache = null;
+ }
+
+ public synchronized IBufferCache createInMemoryBufferCache() {
+ if (bufferCache == null) {
+ ICacheMemoryAllocator allocator = new HeapBufferAllocator();
+ bufferCache = new InMemoryBufferCache(allocator, pageSize, numPages);
+ }
+ return bufferCache;
+ }
+}
diff --git a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/InMemoryFreePageManager.java b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/InMemoryFreePageManager.java
new file mode 100644
index 0000000..1f43bc8
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/InMemoryFreePageManager.java
@@ -0,0 +1,86 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.common.impls;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.PageAllocationException;
+
+public class InMemoryFreePageManager implements IFreePageManager{
+ private final int maxCapacity;
+ private int currentCapacity;
+ private final ITreeIndexMetaDataFrameFactory metaDataFrameFactory;
+
+ public InMemoryFreePageManager(int maxCapacity, ITreeIndexMetaDataFrameFactory metaDataFrameFactory) {
+ this.maxCapacity = maxCapacity-1; // Since the range of CacheArray in InMemoryBufferCache is 0 ~ maxCapacity-1
+ currentCapacity = 1;
+ this.metaDataFrameFactory = metaDataFrameFactory;
+ }
+
+ public int getCurrentCapacity() {
+ return currentCapacity;
+ }
+
+ @Override
+ public synchronized int getFreePage(ITreeIndexMetaDataFrame metaFrame)
+ throws HyracksDataException, PageAllocationException {
+
+ if(currentCapacity == maxCapacity) {
+ throw new PageAllocationException("In-mem tree capacity reaches max capacity");
+ }
+ currentCapacity++;
+ return currentCapacity;
+ }
+
+
+ @Override
+ public void addFreePage(ITreeIndexMetaDataFrame metaFrame, int freePage)
+ throws HyracksDataException {
+ System.out.println("InMemoryFreePageManager.addFreePage()");
+ }
+
+ @Override
+ public int getMaxPage(ITreeIndexMetaDataFrame metaFrame)
+ throws HyracksDataException {
+ return currentCapacity;
+ }
+
+ @Override
+ public void init(ITreeIndexMetaDataFrame metaFrame, int currentMaxPage)
+ throws HyracksDataException {
+ currentCapacity = 1;
+ }
+
+ @Override
+ public ITreeIndexMetaDataFrameFactory getMetaDataFrameFactory() {
+ return metaDataFrameFactory;
+ }
+
+ @Override
+ public byte getMetaPageLevelIndicator() {
+ System.out.println("InMemoryFreePageManager.getMetaPageLevelIndicator()");
+ return 0;
+ }
+
+ @Override
+ public byte getFreePageLevelIndicator() {
+ System.out.println("InMemoryFreePageManager.getFreePageLevelIndicator()");
+ return 0;
+ }
+
+ @Override
+ public boolean isMetaPage(ITreeIndexMetaDataFrame metaFrame) {
+ System.out.println("InMemoryFreePageManager.isMetaPage()");
+ return false;
+ }
+
+ @Override
+ public boolean isFreePage(ITreeIndexMetaDataFrame metaFrame) {
+ System.out.println("InMemoryFreePageManager.isFreePage()");
+ return false;
+ }
+
+ public void reset(){
+ currentCapacity = 1;
+ }
+}
diff --git a/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/TreeFactory.java b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/TreeFactory.java
new file mode 100644
index 0000000..7903d18
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/common/impls/TreeFactory.java
@@ -0,0 +1,29 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.common.impls;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+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.common.buffercache.IBufferCache;
+
+public abstract class TreeFactory {
+
+ protected IBufferCache bufferCache;
+ protected int fieldCount;
+ protected MultiComparator cmp;
+ protected ITreeIndexFrameFactory interiorFrameFactory;
+ protected ITreeIndexFrameFactory leafFrameFactory;
+ protected FreePageManagerFactory freePageManagerFactory;
+
+ public TreeFactory(IBufferCache bufferCache, FreePageManagerFactory freePageManagerFactory, MultiComparator cmp,
+ int fieldCount, ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory) {
+ this.bufferCache = bufferCache;
+ this.fieldCount = fieldCount;
+ this.cmp = cmp;
+ this.interiorFrameFactory = interiorFrameFactory;
+ this.leafFrameFactory = leafFrameFactory;
+ this.freePageManagerFactory = freePageManagerFactory;
+ }
+
+ public abstract ITreeIndex createIndexInstance(int fileId);
+
+}
diff --git a/hyracks-storage-am-lsmtree-rtree/pom.xml b/hyracks-storage-am-lsmtree-rtree/pom.xml
new file mode 100644
index 0000000..2c9b94c
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-rtree/pom.xml
@@ -0,0 +1,56 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-lsmtree-rtree</artifactId>
+ <version>0.2.0-SNAPSHOT</version>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks</artifactId>
+ <version>0.2.0-SNAPSHOT</version>
+ </parent>
+
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-compiler-plugin</artifactId>
+ <version>2.0.2</version>
+ <configuration>
+ <source>1.6</source>
+ <target>1.6</target>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+ <dependencies>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-lsmtree-common</artifactId>
+ <version>0.2.0-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.0-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.0-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <version>4.8.1</version>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
+ </dependencies>
+</project>
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/BTreeFactory.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/BTreeFactory.java
new file mode 100644
index 0000000..a60cc60
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/BTreeFactory.java
@@ -0,0 +1,24 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls;
+
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.lsmtree.common.impls.FreePageManagerFactory;
+import edu.uci.ics.hyracks.storage.am.lsmtree.common.impls.TreeFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+public class BTreeFactory extends TreeFactory {
+
+ public BTreeFactory(IBufferCache bufferCache, FreePageManagerFactory freePageManagerFactory, MultiComparator cmp,
+ int fieldCount, ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory) {
+ super(bufferCache, freePageManagerFactory, cmp, fieldCount, interiorFrameFactory, leafFrameFactory);
+ }
+
+ @Override
+ public ITreeIndex createIndexInstance(int fileId) {
+ return new BTree(bufferCache, fieldCount, cmp, freePageManagerFactory.createFreePageManager(fileId),
+ interiorFrameFactory, leafFrameFactory);
+ }
+
+}
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMBTreeOpContext.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMBTreeOpContext.java
new file mode 100644
index 0000000..f35ee34
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMBTreeOpContext.java
@@ -0,0 +1,30 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls;
+
+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.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public final class LSMBTreeOpContext extends BTreeOpContext {
+
+ public final BTree.BTreeAccessor memBtreeAccessor;
+
+ public LSMBTreeOpContext(BTree.BTreeAccessor memBtreeAccessor, ITreeIndexFrameFactory leafFrameFactory,
+ ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexMetaDataFrame metaFrame, MultiComparator cmp) {
+ super(leafFrameFactory, interiorFrameFactory, metaFrame, cmp);
+
+ this.memBtreeAccessor = memBtreeAccessor;
+ // Overwrite the BTree accessor's op context with our LSMBTreeOpContext.
+ this.memBtreeAccessor.setOpContext(this);
+
+ reset(op);
+ }
+
+ @Override
+ public void reset(IndexOp newOp) {
+ super.reset(newOp);
+ }
+
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTree.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTree.java
new file mode 100644
index 0000000..4583bdc
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTree.java
@@ -0,0 +1,516 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls;
+
+import java.io.File;
+import java.util.LinkedList;
+
+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.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoadContext;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+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.IndexType;
+import edu.uci.ics.hyracks.storage.am.common.api.PageAllocationException;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.lsmtree.common.api.ILSMTree;
+import edu.uci.ics.hyracks.storage.am.lsmtree.common.impls.InMemoryFreePageManager;
+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.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.IFileMapManager;
+
+public class LSMRTree implements ILSMTree {
+
+ private final IBufferCache bufferCache;
+ private RTree memRTree;
+ private BTree memBTree;
+ private String rtreeFileName;
+ private String btreeFileName;
+ private int rtreeFileId;
+ private int btreeFileId;
+ private boolean created;
+
+ private final IFreePageManager rtreeMemFreePageManager;
+ private final IFreePageManager btreeMemFreePageManager;
+ private final ITreeIndexFrameFactory rtreeInteriorFrameFactory;
+ private final ITreeIndexFrameFactory btreeInteriorFrameFactory;
+ private final ITreeIndexFrameFactory rtreeLeafFrameFactory;
+ private final ITreeIndexFrameFactory btreeLeafFrameFactory;
+ private final MultiComparator cmp;
+
+ // TODO: change to private, it's public only for LSMTreeSearchTest
+ public LinkedList<ITreeIndex> inDiskRTreeList;
+ public LinkedList<ITreeIndex> inDiskBTreeList;
+ private LinkedList<ITreeIndex> mergedInDiskRTreeList;
+ private LinkedList<ITreeIndex> mergedInDiskBTreeList;
+ private int inDiskTreeCounter;
+ private final RTreeFactory rTreeFactory;
+ private final BTreeFactory bTreeFactory;
+ private final IFileMapManager fileMapManager;
+ private int threadReferenceCounter;
+ private boolean flushFlag;
+
+ public LSMRTree(IBufferCache rtreeMemCache, IBufferCache btreeMemCache, IBufferCache bufferCache, int fieldCount, MultiComparator cmp,
+ IFreePageManager rtreeMemFreePageManager, IFreePageManager btreeMemFreePageManager, ITreeIndexFrameFactory rtreeInteriorFrameFactory,
+ ITreeIndexFrameFactory btreeInteriorFrameFactory, ITreeIndexFrameFactory rtreeLeafFrameFactory,
+ ITreeIndexFrameFactory btreeLeafFrameFactory, RTreeFactory rTreeFactory, BTreeFactory bTreeFactory,
+ IFileMapManager fileMapManager) {
+ this.bufferCache = bufferCache;
+ this.cmp = cmp;
+ this.rtreeInteriorFrameFactory = rtreeInteriorFrameFactory;
+ this.btreeInteriorFrameFactory = btreeInteriorFrameFactory;
+ this.rtreeLeafFrameFactory = rtreeLeafFrameFactory;
+ this.btreeLeafFrameFactory = btreeLeafFrameFactory;
+ this.rtreeMemFreePageManager = rtreeMemFreePageManager;
+ this.btreeMemFreePageManager = btreeMemFreePageManager;
+ this.rTreeFactory = rTreeFactory;
+ this.bTreeFactory = bTreeFactory;
+ this.inDiskRTreeList = new LinkedList<ITreeIndex>();
+ this.inDiskBTreeList = new LinkedList<ITreeIndex>();
+ this.inDiskTreeCounter = 0;
+ this.fileMapManager = fileMapManager;
+ this.threadReferenceCounter = 0;
+ this.created = false;
+ this.flushFlag = false;
+
+ try {
+ this.rtreeFileName = this.fileMapManager.lookupFileName(this.rtreeFileId).toString();
+
+ this.btreeFileName = this.rtreeFileName + "-btree";
+ FileReference file = new FileReference(new File(this.btreeFileName));
+ this.bufferCache.createFile(file);
+ this.btreeFileId = fileMapManager.lookupFileId(file);
+ bufferCache.openFile(btreeFileId);
+
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+
+ memRTree = new RTree(rtreeMemCache, fieldCount, cmp, rtreeMemFreePageManager, rtreeInteriorFrameFactory,
+ rtreeLeafFrameFactory);
+ memBTree = new BTree(btreeMemCache, fieldCount, cmp, btreeMemFreePageManager, btreeInteriorFrameFactory,
+ btreeLeafFrameFactory);
+ }
+
+ @Override
+ public ITreeIndexAccessor createAccessor() {
+ return new LSMRTreeAccessor(this);
+ }
+
+ @Override
+ public IIndexBulkLoadContext beginBulkLoad(float fillFactor) throws TreeIndexException, HyracksDataException,
+ PageAllocationException {
+ // TODO Auto-generated method stub
+ return null;
+ }
+
+ @Override
+ public void bulkLoadAddTuple(ITupleReference tuple, IIndexBulkLoadContext ictx) throws HyracksDataException,
+ PageAllocationException {
+ // TODO Auto-generated method stub
+
+ }
+
+ @Override
+ public void endBulkLoad(IIndexBulkLoadContext ictx) throws HyracksDataException, PageAllocationException {
+ // TODO Auto-generated method stub
+
+ }
+
+ @Override
+ public ITreeIndexFrameFactory getLeafFrameFactory() {
+ // TODO Auto-generated method stub
+ return null;
+ }
+
+ @Override
+ public ITreeIndexFrameFactory getInteriorFrameFactory() {
+ // TODO Auto-generated method stub
+ return null;
+ }
+
+ @Override
+ public IFreePageManager getFreePageManager() {
+ // TODO Auto-generated method stub
+ return null;
+ }
+
+ @Override
+ public int getFieldCount() {
+ // TODO Auto-generated method stub
+ return 0;
+ }
+
+ @Override
+ public int getRootPageId() {
+ // TODO Auto-generated method stub
+ return 0;
+ }
+
+ @Override
+ public IndexType getIndexType() {
+ // TODO Auto-generated method stub
+ return null;
+ }
+
+ @Override
+ public void create(int indexFileId) throws HyracksDataException {
+ if (created) {
+ return;
+ } else {
+ rtreeFileId = indexFileId;
+ memRTree.create(rtreeFileId);
+ memBTree.create(btreeFileId);
+ created = true;
+ }
+ }
+
+ @Override
+ public void open(int indexFileId) {
+ memRTree.open(rtreeFileId);
+ memBTree.open(btreeFileId);
+ }
+
+ @Override
+ public void close() {
+ memRTree.close();
+ memBTree.close();
+ this.rtreeFileId = -1;
+
+ }
+
+ @Override
+ public void merge() throws Exception {
+ // TODO Auto-generated method stub
+
+ }
+
+ @Override
+ public void flush() throws Exception {
+ inDiskTreeCounter++;
+
+ // scan the RTree
+ ITreeIndexCursor rtreeScanCursor = new RTreeSearchCursor(
+ (IRTreeInteriorFrame) rtreeInteriorFrameFactory.createFrame(),
+ (IRTreeLeafFrame) rtreeLeafFrameFactory.createFrame());
+ SearchPredicate searchPredicate = new SearchPredicate(null, null);
+
+ ITreeIndexAccessor memRTreeAccessor = memRTree.createAccessor();
+ memRTreeAccessor.search(rtreeScanCursor, searchPredicate);
+
+ // Create a new in-Disk RTree
+
+ // Register the RTree information into system.
+ FileReference rtreeFile = new FileReference(new File(getNextFileName(rtreeFileName, inDiskTreeCounter)));
+ // TODO: Delete the file during cleanup.
+ bufferCache.createFile(rtreeFile);
+ int newDiskRTreeId = fileMapManager.lookupFileId(rtreeFile);
+ // TODO: Close the file during cleanup.
+ bufferCache.openFile(newDiskRTreeId);
+
+ // Create new in-Disk RTree.
+ RTree inDiskRTree = (RTree) rTreeFactory.createIndexInstance(newDiskRTreeId);
+ inDiskRTree.create(newDiskRTreeId);
+ // TODO: Close the RTree during cleanup.
+ inDiskRTree.open(newDiskRTreeId);
+
+ // // BulkLoad the tuples from the in-memory tree into the new disk RTree.
+ IIndexBulkLoadContext rtreeBulkLoadCtx = inDiskRTree.beginBulkLoad(1.0f);
+
+ int i = 0;
+ try {
+ while (rtreeScanCursor.hasNext()) {
+ rtreeScanCursor.next();
+ ITupleReference frameTuple = rtreeScanCursor.getTuple();
+ inDiskRTree.bulkLoadAddTuple(frameTuple, rtreeBulkLoadCtx);
+ i++;
+ }
+ } finally {
+ rtreeScanCursor.close();
+ }
+ inDiskRTree.endBulkLoad(rtreeBulkLoadCtx);
+
+ // scan the BTree
+ ITreeIndexCursor btreeScanCursor = new BTreeRangeSearchCursor((IBTreeLeafFrame) btreeLeafFrameFactory.createFrame(),
+ false);
+ RangePredicate nullPred = new RangePredicate(true, null, null, true, true, null, null);
+ ITreeIndexAccessor memBTreeAccessor = memBTree.createAccessor();
+ memBTreeAccessor.search(btreeScanCursor, nullPred);
+
+ // Create a new in-Disk BTree, which have full fillfactor.
+
+ // Register the BTree information into system.
+ FileReference btreeFile = new FileReference(new File(getNextFileName(btreeFileName, inDiskTreeCounter)));
+ // TODO: Delete the file during cleanup.
+ bufferCache.createFile(btreeFile);
+ int newDiskBTreeId = fileMapManager.lookupFileId(btreeFile);
+ // TODO: Close the file during cleanup.
+ bufferCache.openFile(newDiskBTreeId);
+
+ // Create new in-Disk BTree.
+ BTree inDiskBTree = (BTree) bTreeFactory.createIndexInstance(newDiskBTreeId);
+ inDiskBTree.create(newDiskBTreeId);
+ // TODO: Close the BTree during cleanup.
+ inDiskBTree.open(newDiskBTreeId);
+
+ // BulkLoad the tuples from the in-memory tree into the new disk BTree.
+ IIndexBulkLoadContext btreeBulkLoadCtx = inDiskBTree.beginBulkLoad(1.0f);
+ try {
+ while (btreeScanCursor.hasNext()) {
+ btreeScanCursor.next();
+ ITupleReference frameTuple = btreeScanCursor.getTuple();
+ inDiskBTree.bulkLoadAddTuple(frameTuple, btreeBulkLoadCtx);
+ }
+ } finally {
+ btreeScanCursor.close();
+ }
+ inDiskBTree.endBulkLoad(btreeBulkLoadCtx);
+
+ // After BulkLoading, Clear the in-memTrees
+ resetInMemoryTrees();
+
+ synchronized (inDiskRTreeList) {
+ inDiskRTreeList.addFirst(inDiskRTree);
+ }
+ synchronized (inDiskBTreeList) {
+ inDiskBTreeList.addFirst(inDiskBTree);
+ }
+ }
+
+ private static final String getNextFileName(String fileName, int inDiskTreeCounter) {
+ return fileName + "-" + Integer.toString(inDiskTreeCounter);
+ }
+
+ public void resetInMemoryTrees() throws HyracksDataException {
+ ((InMemoryFreePageManager) rtreeMemFreePageManager).reset();
+ ((InMemoryFreePageManager) btreeMemFreePageManager).reset();
+ memRTree.create(rtreeFileId);
+ memBTree.create(btreeFileId);
+ }
+
+ private void decreaseThreadReferenceCounter() throws Exception {
+ synchronized (this) {
+ threadReferenceCounter--;
+ if (flushFlag == true) {
+ if (threadReferenceCounter == 0) {
+ flush();
+ flushFlag = false;
+ return;
+ } else if (threadReferenceCounter < 0) {
+ throw new Error("Thread reference counter is below zero. This indicates a programming error!");
+ }
+ }
+ }
+ }
+
+ private void insert(ITupleReference tuple, LSMTreeOpContext ctx) throws HyracksDataException, TreeIndexException,
+ PageAllocationException {
+ try {
+ boolean continuePerformOp = false;
+ try {
+ while (continuePerformOp == false) {
+ synchronized (this) {
+ if (!flushFlag) {
+ threadReferenceCounter++;
+ continuePerformOp = true;
+ }
+ }
+ }
+ ctx.LSMRTreeOpContext.memRtreeAccessor.insert(tuple);
+ decreaseThreadReferenceCounter();
+ } catch (PageAllocationException e) {
+ synchronized (this) {
+ // If flushFlag is false it means we are the first inserter
+ // to
+ // trigger the flush. If flushFlag is already set to true,
+ // there's no harm in setting it to true again.
+ flushFlag = true;
+ threadReferenceCounter--;
+ if (threadReferenceCounter == 0) {
+ flush();
+ ctx.LSMRTreeOpContext.reset(IndexOp.INSERT);
+ ctx.LSMRTreeOpContext.memRtreeAccessor.insert(tuple);
+ flushFlag = false;
+ return;
+ } else if (threadReferenceCounter < 0) {
+ throw new Error("Thread reference counter is below zero. This indicates a programming error!");
+ }
+ }
+ insert(tuple, ctx);
+ return;
+ }
+
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ private void delete(ITupleReference tuple, LSMTreeOpContext ctx) throws HyracksDataException, TreeIndexException,
+ PageAllocationException {
+ try {
+ boolean continuePerformOp = false;
+ try {
+ while (continuePerformOp == false) {
+ synchronized (this) {
+ if (!flushFlag) {
+ threadReferenceCounter++;
+ continuePerformOp = true;
+ }
+ }
+ }
+ ctx.LSMBTreeOpContext.memBtreeAccessor.insert(tuple);
+ decreaseThreadReferenceCounter();
+ } catch (PageAllocationException e) {
+ synchronized (this) {
+ // If flushFlag is false it means we are the first inserter
+ // to
+ // trigger the flush. If flushFlag is already set to true,
+ // there's no harm in setting it to true again.
+ flushFlag = true;
+ threadReferenceCounter--;
+ if (threadReferenceCounter == 0) {
+ flush();
+ ctx.LSMBTreeOpContext.reset(IndexOp.INSERT);
+ ctx.LSMBTreeOpContext.memBtreeAccessor.insert(tuple);
+ flushFlag = false;
+ return;
+ } else if (threadReferenceCounter < 0) {
+ throw new Error("Thread reference counter is below zero. This indicates a programming error!");
+ }
+ }
+ delete(tuple, ctx);
+ return;
+ }
+
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ private void search(ITreeIndexCursor cursor, ISearchPredicate searchPred, LSMTreeOpContext ctx) throws Exception {
+ // int numberOfInDiskTrees;
+ // ListIterator<InDiskTreeInfo> inDiskTreeInfoListIterator;
+ // boolean continuePerformOp = false;
+ //
+ // ctx.reset(IndexOp.SEARCH);
+ //
+ // while (continuePerformOp == false) {
+ // synchronized (this) {
+ // if (!flushFlag) {
+ // threadReferenceCounter++;
+ // continuePerformOp = true;
+ // }
+ // }
+ // }
+ //
+ // // in-disk
+ // synchronized (inDiskTreeInfoList) {
+ // numberOfInDiskTrees = inDiskTreeInfoList.size();
+ // inDiskTreeInfoListIterator = inDiskTreeInfoList.listIterator();
+ // }
+ //
+ // LSMTreeCursorInitialState initialState = new
+ // LSMTreeCursorInitialState(numberOfInDiskTrees + 1,
+ // insertLeafFrameFactory, cmp, this);
+ // cursor.open(initialState, pred);
+ //
+ // BTree[] onDiskBtrees = new BTree[numberOfInDiskTrees];
+ // ITreeIndexAccessor[] onDiskBtreeAccessors = new
+ // ITreeIndexAccessor[numberOfInDiskTrees];
+ //
+ // for (int i = 0; i < numberOfInDiskTrees; i++) {
+ // // get btree instances for in-disk trees
+ // if (inDiskTreeInfoListIterator.hasNext()) {
+ // onDiskBtrees[i] = ((InDiskTreeInfo)
+ // inDiskTreeInfoListIterator.next()).getBTree();
+ // } else {
+ // throw new HyracksDataException("Cannot find in-disk tree instance");
+ // }
+ // onDiskBtreeAccessors[i] = onDiskBtrees[i].createAccessor();
+ // onDiskBtreeAccessors[i].search(((LSMTreeRangeSearchCursor)
+ // cursor).getCursor(i + 1), pred);
+ // }
+ //
+ // // in-memory
+ // ctx.memBtreeAccessor.search(((LSMTreeRangeSearchCursor)
+ // cursor).getCursor(0), pred);
+ //
+ // LSMPriorityQueueComparator LSMPriorityQueueCmp = new
+ // LSMPriorityQueueComparator(cmp);
+ // ((LSMTreeRangeSearchCursor)
+ // cursor).initPriorityQueue(numberOfInDiskTrees + 1,
+ // LSMPriorityQueueCmp);
+ }
+
+ private LSMTreeOpContext createOpContext() {
+
+ return new LSMTreeOpContext(new LSMRTreeOpContext((RTree.RTreeAccessor) memRTree.createAccessor(),
+ (IRTreeLeafFrame) rtreeLeafFrameFactory.createFrame(),
+ (IRTreeInteriorFrame) rtreeInteriorFrameFactory.createFrame(), rtreeMemFreePageManager
+ .getMetaDataFrameFactory().createFrame(), 8), new LSMBTreeOpContext(
+ (BTree.BTreeAccessor) memBTree.createAccessor(), btreeLeafFrameFactory, btreeInteriorFrameFactory,
+ btreeMemFreePageManager.getMetaDataFrameFactory().createFrame(), cmp));
+ }
+
+ private class LSMRTreeAccessor implements ITreeIndexAccessor {
+ private LSMRTree lsmRTree;
+ private LSMTreeOpContext ctx;
+
+ public LSMRTreeAccessor(LSMRTree lsmRTree) {
+ this.lsmRTree = lsmRTree;
+ this.ctx = lsmRTree.createOpContext();
+
+ }
+
+ @Override
+ public void insert(ITupleReference tuple) throws HyracksDataException, TreeIndexException,
+ PageAllocationException {
+ ctx.LSMRTreeOpContext.reset(IndexOp.INSERT);
+ lsmRTree.insert(tuple, ctx);
+ }
+
+ @Override
+ public void update(ITupleReference tuple) throws HyracksDataException, TreeIndexException,
+ PageAllocationException {
+ throw new UnsupportedOperationException("Update not supported by LSMRTree");
+ }
+
+ @Override
+ public void delete(ITupleReference tuple) throws HyracksDataException, TreeIndexException,
+ PageAllocationException {
+ ctx.LSMBTreeOpContext.reset(IndexOp.INSERT);
+ lsmRTree.delete(tuple, ctx);
+ }
+
+ @Override
+ public void search(ITreeIndexCursor cursor, ISearchPredicate searchPred) throws HyracksDataException,
+ TreeIndexException, PageAllocationException {
+ ctx.reset(IndexOp.SEARCH);
+ // TODO: fix exception handling throughout LSM tree.
+ try {
+ lsmRTree.search(cursor, searchPred, ctx);
+ } catch (Exception e) {
+ throw new HyracksDataException(e);
+ }
+ }
+
+ @Override
+ public void diskOrderScan(ITreeIndexCursor cursor) throws HyracksDataException {
+ throw new UnsupportedOperationException("DiskOrderScan not supported by LSMRTree");
+ }
+ }
+
+}
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeOpContext.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeOpContext.java
new file mode 100644
index 0000000..a3df90f
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMRTreeOpContext.java
@@ -0,0 +1,31 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+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 extends RTreeOpContext {
+
+ public final RTree.RTreeAccessor memRtreeAccessor;
+
+ public LSMRTreeOpContext(RTree.RTreeAccessor memRtreeAccessor, IRTreeLeafFrame leafFrame,
+ IRTreeInteriorFrame interiorFrame, ITreeIndexMetaDataFrame metaFrame, int treeHeightHint) {
+
+ super(leafFrame, interiorFrame, metaFrame, treeHeightHint);
+
+ this.memRtreeAccessor = memRtreeAccessor;
+ // Overwrite the RTree accessor's op context with our LSMRTreeOpContext.
+ this.memRtreeAccessor.setOpContext(this);
+
+ reset(op);
+ }
+
+ @Override
+ public void reset(IndexOp newOp) {
+ super.reset(newOp);
+ }
+
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMTreeOpContext.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMTreeOpContext.java
new file mode 100644
index 0000000..dcf5247
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMTreeOpContext.java
@@ -0,0 +1,20 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls;
+
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+
+public final class LSMTreeOpContext {
+
+ public LSMRTreeOpContext LSMRTreeOpContext;
+ public LSMBTreeOpContext LSMBTreeOpContext;
+
+ public LSMTreeOpContext(LSMRTreeOpContext LSMRTreeOpContext, LSMBTreeOpContext LSMBTreeOpContext) {
+ this.LSMRTreeOpContext = LSMRTreeOpContext;
+ this.LSMBTreeOpContext = LSMBTreeOpContext;
+ }
+
+ public void reset(IndexOp newOp) {
+ LSMRTreeOpContext.reset(newOp);
+ LSMBTreeOpContext.reset(newOp);
+ }
+
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMTypeAwareTupleWriterFactory.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMTypeAwareTupleWriterFactory.java
new file mode 100644
index 0000000..a55248b
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/LSMTypeAwareTupleWriterFactory.java
@@ -0,0 +1,30 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls;
+
+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-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/RTreeFactory.java b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/RTreeFactory.java
new file mode 100644
index 0000000..d5558d7
--- /dev/null
+++ b/hyracks-storage-am-lsmtree-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/impls/RTreeFactory.java
@@ -0,0 +1,24 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+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.lsmtree.common.impls.FreePageManagerFactory;
+import edu.uci.ics.hyracks.storage.am.lsmtree.common.impls.TreeFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+
+public class RTreeFactory extends TreeFactory {
+
+ public RTreeFactory(IBufferCache bufferCache, FreePageManagerFactory freePageManagerFactory, MultiComparator cmp,
+ int fieldCount, ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory) {
+ super(bufferCache, freePageManagerFactory, cmp, fieldCount, interiorFrameFactory, leafFrameFactory);
+ }
+
+ @Override
+ public ITreeIndex createIndexInstance(int fileId) {
+ return new RTree(bufferCache, fieldCount, cmp, freePageManagerFactory.createFreePageManager(fileId),
+ interiorFrameFactory, leafFrameFactory);
+ }
+
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeInteriorFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeInteriorFrame.java
index 2b3065d..242adad 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeInteriorFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeInteriorFrame.java
@@ -25,6 +25,8 @@
public int getBestChildPageId();
+ public int getChildPageId(int tupleIndex);
+
public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex,
MultiComparator cmp);
@@ -40,4 +42,6 @@
MultiComparator cmp);
public void enlarge(ITupleReference tuple, MultiComparator cmp);
+
+ boolean checkEnlargement(ITupleReference tuple, MultiComparator cmp);
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMInteriorFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMInteriorFrame.java
index f3e6be2..202ae18 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMInteriorFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMInteriorFrame.java
@@ -169,6 +169,12 @@
}
@Override
+ public int getChildPageId(int tupleIndex) {
+ frameTuple.resetByTupleIndex(this, tupleIndex);
+ return buf.getInt(getChildPointerOff(frameTuple));
+ }
+
+ @Override
public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
frameTuple.setFieldCount(cmp.getKeyFieldCount());
frameTuple.resetByTupleIndex(this, tupleIndex);
@@ -585,6 +591,27 @@
}
@Override
+ public boolean checkEnlargement(ITupleReference tuple, MultiComparator cmp) {
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ int c = cmp.getComparators()[i].compare(frameTuple.getFieldData(i), frameTuple.getFieldStart(i),
+ frameTuple.getFieldLength(i), tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i));
+ if (c > 0) {
+ return true;
+ }
+ c = cmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+ frameTuple.getFieldLength(j), tuple.getFieldData(j), tuple.getFieldStart(j),
+ tuple.getFieldLength(j));
+ if (c < 0) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ @Override
public void enlarge(ITupleReference tuple, MultiComparator cmp) {
int maxFieldPos = cmp.getKeyFieldCount() / 2;
for (int i = 0; i < maxFieldPos; i++) {
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
index 5f78dcc..7f06e16 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -51,7 +51,6 @@
public class RTree implements ITreeIndex {
- private boolean created = false;
private boolean loaded = false;
private final int rootPage = 1; // the root page never changes
@@ -206,10 +205,6 @@
public void create(int fileId) throws HyracksDataException {
treeLatch.writeLock().lock();
try {
- if (created) {
- return;
- }
-
ITreeIndexFrame leafFrame = leafFrameFactory.createFrame();
ITreeIndexMetaDataFrame metaFrame = freePageManager.getMetaDataFrameFactory().createFrame();
freePageManager.init(metaFrame, rootPage);
@@ -230,8 +225,6 @@
incrementUnpins();
}
currentLevel = 0;
-
- created = true;
} finally {
treeLatch.writeLock().unlock();
}
@@ -251,7 +244,8 @@
.createFrame(), 8);
}
- private void insert(ITupleReference tuple, IIndexOpContext ictx) throws HyracksDataException, TreeIndexException, PageAllocationException {
+ private void insert(ITupleReference tuple, IIndexOpContext ictx) throws HyracksDataException, TreeIndexException,
+ PageAllocationException {
RTreeOpContext ctx = (RTreeOpContext) ictx;
ctx.reset();
ctx.setTuple(tuple);
@@ -289,7 +283,7 @@
incrementUnpins();
}
- public ICachedPage findLeaf(RTreeOpContext ctx) throws HyracksDataException {
+ private ICachedPage findLeaf(RTreeOpContext ctx) throws HyracksDataException {
int pageId = rootPage;
boolean writeLatched = false;
boolean readLatched = false;
@@ -329,7 +323,7 @@
incrementReadLatchesAcquired();
}
}
-
+
if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
// Concurrent split detected, go back to parent and
// re-choose
@@ -364,40 +358,58 @@
ctx.interiorFrame.findBestChild(ctx.getTuple(), cmp);
int childPageId = ctx.interiorFrame.getBestChildPageId();
- if (!writeLatched) {
- node.releaseReadLatch();
- readLatched = false;
- incrementReadLatchesReleased();
- // TODO: do we need to un-pin and pin again?
+ // check if enlargement is needed
+ boolean enlarementIsNeeded = ctx.interiorFrame.checkEnlargement(ctx.getTuple(), cmp);
+ if (enlarementIsNeeded) {
+ if (!writeLatched) {
+ node.releaseReadLatch();
+ readLatched = false;
+ incrementReadLatchesReleased();
+ // TODO: do we need to un-pin and pin again?
+ bufferCache.unpin(node);
+ incrementUnpins();
+
+ node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ incrementPins();
+ node.acquireWriteLatch();
+ writeLatched = true;
+ incrementWriteLatchesAcquired();
+ ctx.interiorFrame.setPage(node);
+
+ if (ctx.interiorFrame.getPageLsn() != pageLsn) {
+ // The page was changed while we unlocked it;
+ // thus,
+ // retry (re-choose best child)
+
+ ctx.pathList.moveLast();
+ continue;
+ }
+ }
+ // We don't need to reset the frameTuple because it is
+ // already pointing to the best child
+ ctx.interiorFrame.enlarge(ctx.getTuple(), cmp);
+
+ node.releaseWriteLatch();
+ writeLatched = false;
+ incrementWriteLatchesReleased();
bufferCache.unpin(node);
incrementUnpins();
-
- node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
- incrementPins();
- node.acquireWriteLatch();
- writeLatched = true;
- incrementWriteLatchesAcquired();
- ctx.interiorFrame.setPage(node);
-
- if (ctx.interiorFrame.getPageLsn() != pageLsn) {
- // The page was changed while we unlocked it; thus,
- // retry (re-choose best child)
-
- ctx.pathList.moveLast();
- continue;
+ } else {
+ if (readLatched) {
+ node.releaseReadLatch();
+ readLatched = false;
+ incrementReadLatchesReleased();
+ bufferCache.unpin(node);
+ incrementUnpins();
+ } else if (writeLatched) {
+ node.releaseWriteLatch();
+ writeLatched = false;
+ incrementWriteLatchesReleased();
+ bufferCache.unpin(node);
+ incrementUnpins();
}
}
- // We don't need to reset the frameTuple because it is
- // already pointing to the best child
- ctx.interiorFrame.enlarge(ctx.getTuple(), cmp);
-
- node.releaseWriteLatch();
- writeLatched = false;
- incrementWriteLatchesReleased();
- bufferCache.unpin(node);
- incrementUnpins();
-
pageId = childPageId;
parentLsn = pageLsn;
} else {
@@ -552,7 +564,8 @@
}
}
- public void updateParentForInsert(RTreeOpContext ctx) throws HyracksDataException, TreeIndexException, PageAllocationException {
+ private void updateParentForInsert(RTreeOpContext ctx) throws HyracksDataException, TreeIndexException,
+ PageAllocationException {
boolean writeLatched = false;
int parentId = ctx.pathList.getLastPageId();
ICachedPage parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
@@ -625,7 +638,7 @@
updateParentForInsert(ctx);
}
- public void findPath(RTreeOpContext ctx) throws HyracksDataException {
+ private void findPath(RTreeOpContext ctx) throws HyracksDataException {
boolean readLatched = false;
int pageId = rootPage;
int parentIndex = -1;
@@ -680,14 +693,14 @@
}
}
- public void fillPath(RTreeOpContext ctx, int pageIndex) {
+ private void fillPath(RTreeOpContext ctx, int pageIndex) {
if (pageIndex != -1) {
fillPath(ctx, ctx.traverseList.getPageIndex(pageIndex));
ctx.pathList.add(ctx.traverseList.getPageId(pageIndex), ctx.traverseList.getPageLsn(pageIndex), -1);
}
}
- public void delete(ITupleReference tuple, RTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
+ private void delete(ITupleReference tuple, RTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
ctx.reset();
ctx.setTuple(tuple);
ctx.splitKey.reset();
@@ -715,7 +728,7 @@
}
}
- public void updateParentForDelete(RTreeOpContext ctx) throws HyracksDataException {
+ private void updateParentForDelete(RTreeOpContext ctx) throws HyracksDataException {
boolean writeLatched = false;
int parentId = ctx.pathList.getLastPageId();
ICachedPage parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
@@ -806,7 +819,7 @@
updateParentForDelete(ctx);
}
- public int findTupleToDelete(RTreeOpContext ctx) throws HyracksDataException {
+ private int findTupleToDelete(RTreeOpContext ctx) throws HyracksDataException {
boolean writeLatched = false;
boolean readLatched = false;
boolean succeed = false;
@@ -921,7 +934,7 @@
return -1;
}
- public void deleteTuple(int pageId, int tupleIndex, RTreeOpContext ctx) throws HyracksDataException {
+ private void deleteTuple(int pageId, int tupleIndex, RTreeOpContext ctx) throws HyracksDataException {
ctx.leafFrame.delete(tupleIndex, cmp);
incrementGlobalNsn();
ctx.leafFrame.setPageLsn(getGlobalNsn());
@@ -933,14 +946,15 @@
}
}
- private void search(ITreeIndexCursor cursor, ISearchPredicate searchPred, RTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
- ctx.reset();
+ private void search(ITreeIndexCursor cursor, ISearchPredicate searchPred, RTreeOpContext ctx)
+ throws HyracksDataException, TreeIndexException {
+ ctx.reset();
ctx.cursor = cursor;
cursor.setBufferCache(bufferCache);
cursor.setFileId(fileId);
ctx.cursorInitialState.setRootPage(rootPage);
- ctx.cursor.open(ctx.cursorInitialState, (SearchPredicate)searchPred);
+ ctx.cursor.open(ctx.cursorInitialState, (SearchPredicate) searchPred);
}
public ITreeIndexFrameFactory getInteriorFrameFactory() {
@@ -969,7 +983,7 @@
public BulkLoadContext(float fillFactor, IRTreeFrame leafFrame, IRTreeFrame interiorFrame,
ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
- indexAccessor = createAccessor();
+ indexAccessor = createAccessor();
}
}
@@ -988,7 +1002,7 @@
@Override
public void bulkLoadAddTuple(ITupleReference tuple, IIndexBulkLoadContext ictx) throws HyracksDataException {
try {
- ((BulkLoadContext) ictx).indexAccessor.insert(tuple);
+ ((BulkLoadContext) ictx).indexAccessor.insert(tuple);
} catch (Exception e) {
throw new HyracksDataException("BulkLoad Error");
}
@@ -1036,23 +1050,24 @@
public IndexType getIndexType() {
return IndexType.RTREE;
}
-
+
@Override
- public ITreeIndexAccessor createAccessor() {
- return new RTreeAccessor(this);
- }
-
- private class RTreeAccessor implements ITreeIndexAccessor {
+ public ITreeIndexAccessor createAccessor() {
+ return new RTreeAccessor(this);
+ }
+
+ public class RTreeAccessor implements ITreeIndexAccessor {
private RTree rtree;
private RTreeOpContext ctx;
-
+
public RTreeAccessor(RTree rtree) {
this.rtree = rtree;
this.ctx = rtree.createOpContext();
}
-
+
@Override
- public void insert(ITupleReference tuple) throws HyracksDataException, TreeIndexException, PageAllocationException {
+ public void insert(ITupleReference tuple) throws HyracksDataException, TreeIndexException,
+ PageAllocationException {
ctx.reset(IndexOp.INSERT);
rtree.insert(tuple, ctx);
}
@@ -1081,5 +1096,13 @@
ctx.reset(IndexOp.DISKORDERSCAN);
rtree.diskOrderScan(cursor, ctx);
}
+
+ // TODO: Ideally, this method should not exist. But we need it for
+ // the LSM tree to work correctly, so we can use the LSMOpContext inside
+ // a BTreeAccessor.
+ // Making the appropriate change will involve changing lots of code.
+ public void setOpContext(RTreeOpContext ctx) {
+ this.ctx = ctx;
+ }
}
}
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
index c258377..9c60492 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
@@ -23,7 +23,7 @@
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
-public final class RTreeOpContext implements IIndexOpContext {
+public class RTreeOpContext implements IIndexOpContext {
public final IRTreeInteriorFrame interiorFrame;
public final IRTreeLeafFrame leafFrame;
public IndexOp op;
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
index e65f1d4..ee0cb20 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
@@ -49,9 +49,6 @@
private ITreeIndexTupleReference frameTuple;
private boolean readLatched = false;
- private int pin = 0;
- private int unpin = 0;
-
public RTreeSearchCursor(IRTreeInteriorFrame interiorFrame, IRTreeLeafFrame leafFrame) {
this.interiorFrame = interiorFrame;
this.leafFrame = leafFrame;
@@ -80,12 +77,11 @@
return page;
}
- public boolean fetchNextLeafPage() throws HyracksDataException {
+ private boolean fetchNextLeafPage() throws HyracksDataException {
boolean succeed = false;
if (readLatched) {
page.releaseReadLatch();
bufferCache.unpin(page);
- unpin++;
readLatched = false;
}
@@ -94,7 +90,6 @@
long parentLsn = pathList.getLastPageLsn();
pathList.moveLast();
ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
- pin++;
node.acquireReadLatch();
readLatched = true;
try {
@@ -112,12 +107,20 @@
}
if (!isLeaf) {
- for (int i = 0; i < interiorFrame.getTupleCount(); i++) {
- int childPageId = interiorFrame.getChildPageIdIfIntersect(searchKey, i, cmp);
- if (childPageId != -1) {
+ if (searchKey != null) {
+ for (int i = 0; i < interiorFrame.getTupleCount(); i++) {
+ int childPageId = interiorFrame.getChildPageIdIfIntersect(searchKey, i, cmp);
+ if (childPageId != -1) {
+ pathList.add(childPageId, pageLsn, -1);
+ }
+ }
+ } else {
+ for (int i = 0; i < interiorFrame.getTupleCount(); i++) {
+ int childPageId = interiorFrame.getChildPageId(i);
pathList.add(childPageId, pageLsn, -1);
}
}
+
} else {
page = node;
leafFrame.setPage(page);
@@ -131,7 +134,6 @@
node.releaseReadLatch();
readLatched = false;
bufferCache.unpin(node);
- unpin++;
}
}
}
@@ -153,7 +155,13 @@
do {
for (int i = tupleIndex; i < leafFrame.getTupleCount(); i++) {
- if (leafFrame.intersect(searchKey, i, cmp)) {
+ if (searchKey != null) {
+ if (leafFrame.intersect(searchKey, i, cmp)) {
+ frameTuple.resetByTupleIndex(leafFrame, i);
+ tupleIndexInc = i + 1;
+ return true;
+ }
+ } else {
frameTuple.resetByTupleIndex(leafFrame, i);
tupleIndexInc = i + 1;
return true;
@@ -185,17 +193,19 @@
cmp = pred.getLowKeyComparator();
searchKey = pred.getSearchKey();
- int maxFieldPos = cmp.getKeyFieldCount() / 2;
- for (int i = 0; i < maxFieldPos; i++) {
- int j = maxFieldPos + i;
- int c = cmp.getComparators()[i].compare(searchKey.getFieldData(i), searchKey.getFieldStart(i),
- searchKey.getFieldLength(i), searchKey.getFieldData(j), searchKey.getFieldStart(j),
- searchKey.getFieldLength(j));
- if (c > 0) {
- throw new IllegalArgumentException("The low key point has larger coordinates than the high key point.");
+ if (searchKey != null) {
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ int c = cmp.getComparators()[i].compare(searchKey.getFieldData(i), searchKey.getFieldStart(i),
+ searchKey.getFieldLength(i), searchKey.getFieldData(j), searchKey.getFieldStart(j),
+ searchKey.getFieldLength(j));
+ if (c > 0) {
+ throw new IllegalArgumentException("The low key point has larger coordinates than the high key point.");
+ }
}
}
-
+
pathList.add(this.rootPage, -1, -1);
tupleIndex = 0;
fetchNextLeafPage();
diff --git a/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/pom.xml b/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/pom.xml
new file mode 100644
index 0000000..737e975
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/pom.xml
@@ -0,0 +1,55 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-lsmtree-rtree-test</artifactId>
+ <version>0.2.0-SNAPSHOT</version>
+
+ <parent>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-tests</artifactId>
+ <version>0.2.0-SNAPSHOT</version>
+ </parent>
+
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-compiler-plugin</artifactId>
+ <version>2.0.2</version>
+ <configuration>
+ <source>1.6</source>
+ <target>1.6</target>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+ <dependencies>
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <version>4.8.1</version>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-control-nc</artifactId>
+ <version>0.2.0-SNAPSHOT</version>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-lsmtree-rtree</artifactId>
+ <version>0.2.0-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-test-support</artifactId>
+ <version>0.2.0-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>test</scope>
+ </dependency>
+ </dependencies>
+</project>
diff --git a/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/AbstractLSMTreeTest.java b/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/AbstractLSMTreeTest.java
new file mode 100644
index 0000000..58b08ec
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/AbstractLSMTreeTest.java
@@ -0,0 +1,76 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.rtree;
+
+import java.io.File;
+import java.text.SimpleDateFormat;
+import java.util.Date;
+import java.util.Random;
+import java.util.logging.Logger;
+
+import org.junit.After;
+import org.junit.Before;
+
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public abstract class AbstractLSMTreeTest {
+ protected static final Logger LOGGER = Logger.getLogger(AbstractLSMTreeTest.class.getName());
+ public static final long RANDOM_SEED = 50;
+
+ private static final int PAGE_SIZE = 256;
+ private static final int NUM_PAGES = 10;
+ private static final int MAX_OPEN_FILES = 10;
+ private static final int HYRACKS_FRAME_SIZE = 128;
+
+ protected IHyracksTaskContext ctx;
+ protected IBufferCache bufferCache;
+ protected int btreeFileId;
+
+ protected final Random rnd = new Random();
+ protected final static SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
+ protected final static String tmpDir = System.getProperty("java.io.tmpdir");
+ protected final static String sep = System.getProperty("file.separator");
+ protected String fileName;
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ fileName = tmpDir + sep + simpleDateFormat.format(new Date());
+ ctx = TestUtils.create(getHyracksFrameSize());
+ TestStorageManagerComponentHolder.init(getPageSize(), getNumPages(), getMaxOpenFiles());
+ bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ btreeFileId = fmp.lookupFileId(file);
+ bufferCache.openFile(btreeFileId);
+ rnd.setSeed(RANDOM_SEED);
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ bufferCache.closeFile(btreeFileId);
+ bufferCache.close();
+ File f = new File(fileName);
+ f.deleteOnExit();
+ }
+
+ public int getPageSize() {
+ return PAGE_SIZE;
+ }
+
+ public int getNumPages() {
+ return NUM_PAGES;
+ }
+
+ public int getHyracksFrameSize() {
+ return HYRACKS_FRAME_SIZE;
+ }
+
+ public int getMaxOpenFiles() {
+ return MAX_OPEN_FILES;
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/LSMRTreeTest.java b/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/LSMRTreeTest.java
new file mode 100644
index 0000000..33349e0
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsmtree-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsmtree/rtree/LSMRTreeTest.java
@@ -0,0 +1,263 @@
+package edu.uci.ics.hyracks.storage.am.lsmtree.rtree;
+
+import java.io.DataOutput;
+import java.io.File;
+import java.nio.ByteBuffer;
+import java.util.Random;
+import java.util.logging.Level;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
+import edu.uci.ics.hyracks.api.context.IHyracksTaskContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTraits;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.DoublePointable;
+import edu.uci.ics.hyracks.data.std.primitive.IntegerPointable;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+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.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.IPrimitiveValueProviderFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.lsmtree.common.impls.FreePageManagerFactory;
+import edu.uci.ics.hyracks.storage.am.lsmtree.common.impls.InMemoryBufferCacheFactory;
+import edu.uci.ics.hyracks.storage.am.lsmtree.common.impls.InMemoryFreePageManager;
+import edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls.BTreeFactory;
+import edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls.LSMRTree;
+import edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls.LSMTypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.lsmtree.rtree.impls.RTreeFactory;
+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.util.RTreeUtils;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapManager;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class LSMRTreeTest extends AbstractLSMTreeTest {
+
+ private static final int PAGE_SIZE = 256;
+ private static final int NUM_PAGES = 10000;
+ private static final int MAX_OPEN_FILES = 100;
+ private static final int HYRACKS_FRAME_SIZE = 128;
+ private IHyracksTaskContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+ // INSERT-DELETE TEST
+ @Test
+ public void Test1() throws Exception {
+ // in disk
+ TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+ IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ int fileId = fmp.lookupFileId(file);
+ bufferCache.openFile(fileId);
+
+ // in memory
+ InMemoryBufferCacheFactory rtreeInMemBufferCacheFactory = new InMemoryBufferCacheFactory(PAGE_SIZE, NUM_PAGES);
+ IBufferCache rtreeMemBufferCache = rtreeInMemBufferCacheFactory.createInMemoryBufferCache();
+
+ // in memory
+ InMemoryBufferCacheFactory btreeInMemBufferCacheFactory = new InMemoryBufferCacheFactory(PAGE_SIZE, NUM_PAGES);
+ IBufferCache btreeMemBufferCache = btreeInMemBufferCacheFactory.createInMemoryBufferCache();
+
+ // declare keys
+ int keyFieldCount = 4;
+ IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
+ cmps[0] = PointableBinaryComparatorFactory.of(DoublePointable.FACTORY).createBinaryComparator();
+ cmps[1] = cmps[0];
+ cmps[2] = cmps[0];
+ cmps[3] = cmps[0];
+
+ // declare tuple fields
+ int fieldCount = 7;
+ ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ typeTraits[0] = DoublePointable.TYPE_TRAITS;
+ typeTraits[1] = DoublePointable.TYPE_TRAITS;
+ typeTraits[2] = DoublePointable.TYPE_TRAITS;
+ typeTraits[3] = DoublePointable.TYPE_TRAITS;
+ typeTraits[4] = DoublePointable.TYPE_TRAITS;
+ typeTraits[5] = IntegerPointable.TYPE_TRAITS;
+ typeTraits[6] = DoublePointable.TYPE_TRAITS;
+
+ MultiComparator cmp = new MultiComparator(cmps);
+
+ // create value providers
+ IPrimitiveValueProviderFactory[] valueProviderFactories = RTreeUtils.createPrimitiveValueProviderFactories(
+ cmps.length, DoublePointable.FACTORY);
+
+ LSMTypeAwareTupleWriterFactory rtreeTupleWriterFactory = new LSMTypeAwareTupleWriterFactory(typeTraits, false);
+ LSMTypeAwareTupleWriterFactory btreeTupleWriterFactory = new LSMTypeAwareTupleWriterFactory(typeTraits, true);
+
+ ITreeIndexFrameFactory rtreeInteriorFrameFactory = new RTreeNSMInteriorFrameFactory(rtreeTupleWriterFactory,
+ valueProviderFactories);
+ ITreeIndexFrameFactory rtreeLeafFrameFactory = new RTreeNSMLeafFrameFactory(rtreeTupleWriterFactory,
+ valueProviderFactories);
+
+ ITreeIndexFrameFactory btreeInteriorFrameFactory = new BTreeNSMInteriorFrameFactory(btreeTupleWriterFactory);
+ ITreeIndexFrameFactory btreeLeafFrameFactory = new BTreeNSMLeafFrameFactory(btreeTupleWriterFactory);
+
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+ IFreePageManager rtreeMemFreePageManager = new InMemoryFreePageManager(100, metaFrameFactory);
+ IFreePageManager btreeMemFreePageManager = new InMemoryFreePageManager(100, metaFrameFactory);
+
+ FreePageManagerFactory freePageManagerFactory = new FreePageManagerFactory(bufferCache, metaFrameFactory);
+
+ RTreeFactory rTreeFactory = new RTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
+ rtreeInteriorFrameFactory, rtreeLeafFrameFactory);
+ BTreeFactory bTreeFactory = new BTreeFactory(bufferCache, freePageManagerFactory, cmp, fieldCount,
+ btreeInteriorFrameFactory, btreeLeafFrameFactory);
+
+ LSMRTree lsmrtree = new LSMRTree(rtreeMemBufferCache, btreeMemBufferCache, bufferCache, fieldCount, cmp,
+ rtreeMemFreePageManager, btreeMemFreePageManager, rtreeInteriorFrameFactory, btreeInteriorFrameFactory,
+ rtreeLeafFrameFactory, btreeLeafFrameFactory, rTreeFactory, bTreeFactory, (IFileMapManager) fmp);
+
+ lsmrtree.create(fileId);
+ lsmrtree.open(fileId);
+
+ ByteBuffer frame = ctx.allocateFrame();
+ FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
+
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(fieldCount);
+ DataOutput dos = tb.getDataOutput();
+
+ @SuppressWarnings("rawtypes")
+ ISerializerDeserializer[] recDescSers = { DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+ DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE };
+ RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
+
+ IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
+ accessor.reset(frame);
+
+ FrameTupleReference tuple = new FrameTupleReference();
+
+ ITreeIndexAccessor lsmTreeAccessor = lsmrtree.createAccessor();
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ Random rnd2 = new Random();
+ rnd2.setSeed(50);
+ for (int i = 0; i < 5000; i++) {
+
+ double p1x = rnd.nextDouble();
+ double p1y = rnd.nextDouble();
+ double p2x = rnd.nextDouble();
+ double p2y = rnd.nextDouble();
+
+ double pk1 = rnd2.nextDouble();
+ int pk2 = rnd2.nextInt();
+ double pk3 = rnd2.nextDouble();
+
+ tb.reset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1y, p2y), dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1x, p2x), dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(pk1, dos);
+ tb.addFieldEndOffset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(pk2, dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(pk3, dos);
+ tb.addFieldEndOffset();
+
+ appender.reset(frame, true);
+ appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+ tuple.reset(accessor, 0);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ // if (i % 1000 == 0) {
+ LOGGER.info("INSERTING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " "
+ + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y));
+ // }
+ }
+
+ try {
+ lsmTreeAccessor.insert(tuple);
+ } catch (TreeIndexException e) {
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ rnd.setSeed(50);
+ for (int i = 0; i < 5000; i++) {
+
+ double p1x = rnd.nextDouble();
+ double p1y = rnd.nextDouble();
+ double p2x = rnd.nextDouble();
+ double p2y = rnd.nextDouble();
+
+ double pk1 = rnd.nextDouble();
+ int pk2 = rnd.nextInt();
+ double pk3 = rnd.nextDouble();
+
+ tb.reset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1y, p2y), dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1x, p2x), dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(pk1, dos);
+ tb.addFieldEndOffset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(pk2, dos);
+ tb.addFieldEndOffset();
+ DoubleSerializerDeserializer.INSTANCE.serialize(pk3, dos);
+ tb.addFieldEndOffset();
+
+ appender.reset(frame, true);
+ appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+ tuple.reset(accessor, 0);
+
+ if (LOGGER.isLoggable(Level.INFO)) {
+ //if (i % 1000 == 0) {
+ LOGGER.info("DELETING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " "
+ + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y));
+ //}
+ }
+
+ try {
+ lsmTreeAccessor.delete(tuple);
+ } catch (TreeIndexException e) {
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ lsmrtree.close();
+ bufferCache.closeFile(fileId);
+ rtreeMemBufferCache.close();
+ btreeMemBufferCache.close();
+ }
+
+}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
index 9fe2c94..e24a086 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
@@ -267,7 +267,7 @@
typeTraits[2] = DoublePointable.TYPE_TRAITS;
typeTraits[3] = DoublePointable.TYPE_TRAITS;
typeTraits[4] = DoublePointable.TYPE_TRAITS;
- typeTraits[5] = DoublePointable.TYPE_TRAITS;
+ typeTraits[5] = IntegerPointable.TYPE_TRAITS;
typeTraits[6] = DoublePointable.TYPE_TRAITS;
// create value providers
diff --git a/hyracks-tests/pom.xml b/hyracks-tests/pom.xml
index b120ba82..1169172 100644
--- a/hyracks-tests/pom.xml
+++ b/hyracks-tests/pom.xml
@@ -16,5 +16,6 @@
<module>hyracks-storage-am-btree-test</module>
<module>hyracks-storage-am-invertedindex-test</module>
<module>hyracks-storage-am-rtree-test</module>
+ <module>hyracks-storage-am-lsmtree-rtree-test</module>
</modules>
</project>
diff --git a/pom.xml b/pom.xml
index 68e8097..5b9121e 100644
--- a/pom.xml
+++ b/pom.xml
@@ -93,6 +93,8 @@
<module>hyracks-storage-am-btree</module>
<module>hyracks-storage-am-invertedindex</module>
<module>hyracks-storage-am-lsmtree</module>
+ <module>hyracks-storage-am-lsmtree-common</module>
+ <module>hyracks-storage-am-lsmtree-rtree</module>
<module>hyracks-storage-am-rtree</module>
<module>hyracks-test-support</module>
<module>hyracks-tests</module>