- Changed the NSMframe design so that there are interior and leaf frames
- Created test file for RTree operators
- Code refactoring and cleaning
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_indexes@508 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
index 0014a2c..efe762c 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
@@ -19,9 +19,9 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.common.api.IntArrayList;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
public final class BTreeOpContext implements IndexOpContext {
public final IndexOp op;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IntArrayList.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IntArrayList.java
deleted file mode 100644
index c232ba8..0000000
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IntArrayList.java
+++ /dev/null
@@ -1,64 +0,0 @@
-/*
- * Copyright 2009-2010 by The Regents of the University of California
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * you may obtain a copy of the License from
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package edu.uci.ics.hyracks.storage.am.common.api;
-
-public class IntArrayList {
- private int[] data;
- private int size;
- private final int growth;
-
- public IntArrayList(int initialCapacity, int growth) {
- data = new int[initialCapacity];
- size = 0;
- this.growth = growth;
- }
-
- public int size() {
- return size;
- }
-
- public void add(int i) {
- if (size == data.length) {
- int[] newData = new int[data.length + growth];
- System.arraycopy(data, 0, newData, 0, data.length);
- data = newData;
- }
-
- data[size++] = i;
- }
-
- public void removeLast() {
- if (size > 0)
- size--;
- }
-
- // WARNING: caller is responsible for checking size > 0
- public int getLast() {
- return data[size - 1];
- }
-
- public int get(int i) {
- return data[i];
- }
-
- public void clear() {
- size = 0;
- }
-
- public boolean isEmpty() {
- return size == 0;
- }
-}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IntArrayList.java
similarity index 96%
rename from hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java
rename to hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IntArrayList.java
index 4be3b38..8902713 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/IntArrayList.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/IntArrayList.java
@@ -13,7 +13,7 @@
* limitations under the License.
*/
-package edu.uci.ics.hyracks.storage.am.rtree.impls;
+package edu.uci.ics.hyracks.storage.am.common.ophelpers;
public class IntArrayList {
private int[] data;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
index 4b3445e..6524eb7 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/ophelpers/MultiComparator.java
@@ -92,10 +92,6 @@
this.cmps = cmps;
}
- public int size() {
- return cmps.length;
- }
-
public int getFieldCount() {
return typeTraits.length;
}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
index 8fe9db4..3e7fed9 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/utility/TreeIndexBufferCacheWarmup.java
@@ -7,7 +7,7 @@
import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
-import edu.uci.ics.hyracks.storage.am.common.api.IntArrayList;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
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;
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
index 49adc87..45ae3a1 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
@@ -6,26 +6,20 @@
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.am.rtree.impls.Rectangle;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.TraverseList;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.TupleEntryArrayList;
public interface IRTreeFrame extends ITreeIndexFrame {
public ITreeIndexTupleReference createTupleReference();
- public boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+ public void generateDist(ITupleReference tuple, TupleEntryArrayList entries, Rectangle rec, int start, int end);
public void computeMBR(ISplitKey splitKey, MultiComparator cmp);
+ public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception;
+
public void delete(int tupleIndex, MultiComparator cmp) throws Exception;
- public int findTupleByPointer(int pageId, MultiComparator cmp);
-
- public int findTupleByPointer(ITupleReference tuple, TraverseList traverseList, int parentId, MultiComparator cmp);
-
- public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp);
-
- public int findTupleIndex(ITupleReference tuple, MultiComparator cmp);
-
public int getPageNsn();
public void setPageNsn(int pageNsn);
@@ -34,19 +28,6 @@
public void setRightPage(int rightPage);
- public int getBestChildPageId(MultiComparator cmp);
-
- public boolean findBestChild(ITupleReference tuple, MultiComparator cmp);
-
public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp);
- public void adjustKey(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
-
- public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
-
- public Rectangle checkIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
-
- public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
-
- public void enlarge(ITupleReference tuple, MultiComparator cmp);
}
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
new file mode 100644
index 0000000..a59e411
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeInteriorFrame.java
@@ -0,0 +1,24 @@
+package edu.uci.ics.hyracks.storage.am.rtree.api;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.TraverseList;
+
+public interface IRTreeInteriorFrame extends IRTreeFrame {
+
+ public boolean findBestChild(ITupleReference tuple, MultiComparator cmp);
+
+ public int getBestChildPageId(MultiComparator cmp);
+
+ public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+
+ public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp);
+
+ public int findTupleByPointer(ITupleReference tuple, TraverseList traverseList, int parentId, MultiComparator cmp);
+
+ public void adjustKey(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+
+ public boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+
+ public void enlarge(ITupleReference tuple, MultiComparator cmp);
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeLeafFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeLeafFrame.java
new file mode 100644
index 0000000..7d66ade
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeLeafFrame.java
@@ -0,0 +1,11 @@
+package edu.uci.ics.hyracks.storage.am.rtree.api;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+
+public interface IRTreeLeafFrame extends IRTreeFrame {
+
+ public int findTupleIndex(ITupleReference tuple, MultiComparator cmp);
+
+ public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelper.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelper.java
index 61091cc..bb5d9cd 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelper.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeOpHelper.java
@@ -1,27 +1,20 @@
package edu.uci.ics.hyracks.storage.am.rtree.dataflow;
import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
-import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
-import edu.uci.ics.hyracks.api.io.FileReference;
-import edu.uci.ics.hyracks.dataflow.std.file.IFileSplitProvider;
import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
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.ITreeIndexFrame;
-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.dataflow.ITreeIndexOperatorDescriptorHelper;
import edu.uci.ics.hyracks.storage.am.common.dataflow.IndexHelperOpenMode;
-import edu.uci.ics.hyracks.storage.am.common.dataflow.IndexRegistry;
import edu.uci.ics.hyracks.storage.am.common.dataflow.TreeIndexOpHelper;
import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
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 RTreeOpHelper extends TreeIndexOpHelper {
@@ -32,91 +25,6 @@
super(opDesc, ctx, partition, mode);
}
- public void init() throws HyracksDataException {
- IBufferCache bufferCache = opDesc.getStorageManager().getBufferCache(ctx);
- IFileMapProvider fileMapProvider = opDesc.getStorageManager().getFileMapProvider(ctx);
- IFileSplitProvider fileSplitProvider = opDesc.getTreeIndexFileSplitProvider();
-
- FileReference f = fileSplitProvider.getFileSplits()[partition].getLocalFile();
- boolean fileIsMapped = fileMapProvider.isMapped(f);
-
- switch (mode) {
-
- case OPEN: {
- if (!fileIsMapped) {
- throw new HyracksDataException("Trying to open rtree from unmapped file " + f.toString());
- }
- }
- break;
-
- case CREATE:
- case ENLIST: {
- if (!fileIsMapped) {
- bufferCache.createFile(f);
- }
- }
- break;
-
- }
-
- int fileId = fileMapProvider.lookupFileId(f);
- try {
- bufferCache.openFile(fileId);
- } catch (HyracksDataException e) {
- // revert state of buffer cache since file failed to open
- if (!fileIsMapped) {
- bufferCache.deleteFile(fileId);
- }
- throw e;
- }
-
- // only set indexFileId member when openFile() succeeds,
- // otherwise deinit() will try to close the file that failed to open
- indexFileId = fileId;
-
- interiorFrame = opDesc.getTreeIndexInteriorFactory().createFrame();
- leafFrame = opDesc.getTreeIndexLeafFactory().createFrame();
-
- IndexRegistry<ITreeIndex> treeIndexRegistry = opDesc.getTreeIndexRegistryProvider().getRegistry(ctx);
- treeIndex = treeIndexRegistry.get(indexFileId);
- if (treeIndex == null) {
-
- // create new tree and register it
- treeIndexRegistry.lock();
- try {
- // check if tree has already been registered by another thread
- treeIndex = treeIndexRegistry.get(indexFileId);
- if (treeIndex == null) {
- // this thread should create and register the tree
-
- IBinaryComparator[] comparators = new IBinaryComparator[opDesc.getTreeIndexComparatorFactories().length];
- for (int i = 0; i < opDesc.getTreeIndexComparatorFactories().length; i++) {
- comparators[i] = opDesc.getTreeIndexComparatorFactories()[i].createBinaryComparator();
- }
-
- cmp = new MultiComparator(opDesc.getTreeIndexTypeTraits(), comparators);
- InteriorFrameSchema interiorFrameSchema = new InteriorFrameSchema(cmp);
- interiorCmp = interiorFrameSchema.getInteriorCmp();
-
- treeIndex = createTreeIndex();
- if (mode == IndexHelperOpenMode.CREATE) {
- ITreeIndexMetaDataFrame metaFrame = treeIndex.getFreePageManager().getMetaDataFrameFactory()
- .createFrame();
- try {
- treeIndex.create(indexFileId, leafFrame, metaFrame);
- } catch (Exception e) {
- throw new HyracksDataException(e);
- }
- }
- treeIndex.open(indexFileId);
- treeIndexRegistry.register(indexFileId, treeIndex);
- }
- } finally {
- treeIndexRegistry.unlock();
- }
- }
- }
-
public ITreeIndex createTreeIndex() throws HyracksDataException {
IBufferCache bufferCache = opDesc.getStorageManager().getBufferCache(ctx);
ITreeIndexMetaDataFrameFactory metaDataFrameFactory = new LIFOMetaDataFrameFactory();
@@ -124,7 +32,7 @@
metaDataFrameFactory);
return new RTree(bufferCache, freePageManager, opDesc.getTreeIndexInteriorFactory(),
- opDesc.getTreeIndexLeafFactory(), interiorCmp, cmp);
+ opDesc.getTreeIndexLeafFactory(), cmp);
}
public ITreeIndexCursor createDiskOrderScanCursor(ITreeIndexFrame leafFrame) throws HyracksDataException {
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorDescriptor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorDescriptor.java
index 1da8730..5bb0056 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorDescriptor.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorDescriptor.java
@@ -25,10 +25,10 @@
public RTreeSearchOperatorDescriptor(JobSpecification spec, RecordDescriptor recDesc,
IStorageManagerInterface storageManager, IIndexRegistryProvider<ITreeIndex> treeIndexRegistryProvider,
IFileSplitProvider fileSplitProvider, ITreeIndexFrameFactory interiorFrameFactory,
- ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] leafTypeTraits,
+ ITreeIndexFrameFactory leafFrameFactory, ITypeTrait[] typeTraits,
IBinaryComparatorFactory[] comparatorFactories, int[] keyFields, ITreeIndexOpHelperFactory opHelperFactory) {
super(spec, 1, 1, recDesc, storageManager, treeIndexRegistryProvider, fileSplitProvider, interiorFrameFactory,
- leafFrameFactory, leafTypeTraits, comparatorFactories, opHelperFactory);
+ leafFrameFactory, typeTraits, comparatorFactories, opHelperFactory);
this.keyFields = keyFields;
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java
index c1b6df3..a98157e 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/dataflow/RTreeSearchOperatorNodePushable.java
@@ -22,7 +22,8 @@
import edu.uci.ics.hyracks.storage.am.common.dataflow.TreeIndexOpHelper;
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.rtree.api.IRTreeFrame;
+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;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
@@ -40,8 +41,7 @@
private RTree rtree;
private PermutingFrameTupleReference searchKey;
private SearchPredicate searchPred;
- private MultiComparator interiorCmp;
- private MultiComparator leafCmp;
+ private MultiComparator cmp;
private ITreeIndexCursor cursor;
private ITreeIndexFrame interiorFrame;
private ITreeIndexFrame leafFrame;
@@ -69,27 +69,26 @@
interiorFrame = opDesc.getTreeIndexInteriorFactory().createFrame();
leafFrame = opDesc.getTreeIndexLeafFactory().createFrame();
- cursor = new RTreeSearchCursor((IRTreeFrame) interiorFrame, (IRTreeFrame) leafFrame);
+ cursor = new RTreeSearchCursor((IRTreeInteriorFrame) interiorFrame, (IRTreeLeafFrame) leafFrame);
try {
treeIndexOpHelper.init();
rtree = (RTree) treeIndexOpHelper.getTreeIndex();
- int keySearchFields = rtree.getLeafCmp().getComparators().length;
+ int keySearchFields = rtree.getCmp().getComparators().length;
IBinaryComparator[] keySearchComparators = new IBinaryComparator[keySearchFields];
for (int i = 0; i < keySearchFields; i++) {
- keySearchComparators[i] = rtree.getLeafCmp().getComparators()[i];
+ keySearchComparators[i] = rtree.getCmp().getComparators()[i];
}
- interiorCmp = new MultiComparator(rtree.getInteriorCmp().getTypeTraits(), keySearchComparators);
- leafCmp = new MultiComparator(rtree.getLeafCmp().getTypeTraits(), keySearchComparators);
+ cmp = new MultiComparator(rtree.getCmp().getTypeTraits(), keySearchComparators);
- searchPred = new SearchPredicate(searchKey, interiorCmp, leafCmp);
+ searchPred = new SearchPredicate(searchKey, cmp);
accessor = new FrameTupleAccessor(treeIndexOpHelper.getHyracksStageletContext().getFrameSize(), recDesc);
writeBuffer = treeIndexOpHelper.getHyracksStageletContext().allocateFrame();
- tb = new ArrayTupleBuilder(rtree.getLeafCmp().getFieldCount());
+ tb = new ArrayTupleBuilder(rtree.getCmp().getFieldCount());
dos = tb.getDataOutput();
appender = new FrameTupleAppender(treeIndexOpHelper.getHyracksStageletContext().getFrameSize());
appender.reset(writeBuffer, true);
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrame.java
index 6387264..9edb815 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrame.java
@@ -4,37 +4,34 @@
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.DoubleSerializerDeserializer;
import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
-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.api.ITreeIndexTupleWriter;
import edu.uci.ics.hyracks.storage.am.common.frames.TreeIndexNSMFrame;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.EntriesOrder;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSplitKey;
import edu.uci.ics.hyracks.storage.am.rtree.impls.Rectangle;
import edu.uci.ics.hyracks.storage.am.rtree.impls.SpatialUtils;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.TraverseList;
import edu.uci.ics.hyracks.storage.am.rtree.impls.TupleEntryArrayList;
import edu.uci.ics.hyracks.storage.am.rtree.impls.UnorderedSlotManager;
import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriter;
-public class NSMFrame extends TreeIndexNSMFrame implements IRTreeFrame {
+public abstract class NSMFrame extends TreeIndexNSMFrame implements IRTreeFrame {
protected static final int pageNsnOff = smFlagOff + 1;
protected static final int rightPageOff = pageNsnOff + 4;
- private ITreeIndexTupleReference[] tuples;
- private ITreeIndexTupleReference cmpFrameTuple;
- public final SpatialUtils spatialUtils;
- public TupleEntryArrayList tupleEntries1; // used for split and checking enlargement
- public TupleEntryArrayList tupleEntries2; // used for split
- public Rectangle[] rec;
+ protected ITreeIndexTupleReference[] tuples;
+ protected ITreeIndexTupleReference cmpFrameTuple;
+ protected final SpatialUtils spatialUtils;
+ protected TupleEntryArrayList tupleEntries1; // used for split and checking
+ // enlargement
+ protected TupleEntryArrayList tupleEntries2; // used for split
+ protected Rectangle[] rec;
- private static final double splitFactor = 0.4;
- private static final int nearMinimumOverlapFactor = 32;
+ protected static final double splitFactor = 0.4;
+ protected static final int nearMinimumOverlapFactor = 32;
public NSMFrame(ITreeIndexTupleWriter tupleWriter, int keyFieldCount) {
super(tupleWriter, new UnorderedSlotManager());
@@ -90,7 +87,7 @@
buf.putInt(rightPageOff, rightPage);
}
- private ITreeIndexTupleReference[] getTuples() {
+ protected ITreeIndexTupleReference[] getTuples() {
return tuples;
}
@@ -112,167 +109,7 @@
return ret;
}
- @Override
- public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey) throws Exception {
-
- RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
- RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
- RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
- rightFrame.setPageTupleFieldCount(cmp.getFieldCount());
- frameTuple.setFieldCount(cmp.getFieldCount());
-
- // calculations are based on the R*-tree paper
- int m = (int) Math.floor((getTupleCount() + 1) * splitFactor);
- int splitDistribution = getTupleCount() - (2 * m) + 2;
-
- // to calculate the minimum margin in order to pick the split axis
- double minMargin = Double.MAX_VALUE;
- int splitAxis = 0, sortOrder = 0;
-
- int maxFieldPos = cmp.getKeyFieldCount() / 2;
- for (int i = 0; i < maxFieldPos; i++) {
- int j = maxFieldPos + i;
- for (int k = 0; k < getTupleCount(); ++k) {
-
- frameTuple.resetByTupleIndex(this, k);
-
- double LowerKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(i),
- frameTuple.getFieldStart(i));
- double UpperKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(j),
- frameTuple.getFieldStart(j));
-
- tupleEntries1.add(k, LowerKey);
- tupleEntries2.add(k, UpperKey);
- }
- double LowerKey = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
- double UpperKey = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j));
-
- tupleEntries1.add(-1, LowerKey);
- tupleEntries2.add(-1, UpperKey);
-
- tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
- tupleEntries2.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
-
- double lowerMargin = 0.0, upperMargin = 0.0;
- // generate distribution
- for (int k = 1; k <= splitDistribution; ++k) {
- int d = m - 1 + k;
-
- generateDist(tuple, tupleEntries1, rec[0], 0, d);
- generateDist(tuple, tupleEntries2, rec[1], 0, d);
- generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
- generateDist(tuple, tupleEntries2, rec[3], d, getTupleCount() + 1);
-
- // calculate the margin of the distributions
- lowerMargin += rec[0].margin() + rec[2].margin();
- upperMargin += rec[1].margin() + rec[3].margin();
- }
- double margin = Math.min(lowerMargin, upperMargin);
-
- // store minimum margin as split axis
- if (margin < minMargin) {
- minMargin = margin;
- splitAxis = i;
- sortOrder = (lowerMargin < upperMargin) ? 0 : 2;
- }
-
- tupleEntries1.clear();
- tupleEntries2.clear();
- }
-
- for (int i = 0; i < getTupleCount(); ++i) {
- frameTuple.resetByTupleIndex(this, i);
- double key = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(splitAxis + sortOrder),
- frameTuple.getFieldStart(splitAxis + sortOrder));
- tupleEntries1.add(i, key);
- }
- double key = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(splitAxis + sortOrder),
- tuple.getFieldStart(splitAxis + sortOrder));
- tupleEntries1.add(-1, key);
- tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
-
- double minArea = Double.MAX_VALUE;
- double minOverlap = Double.MAX_VALUE;
- int splitPoint = 0;
- for (int i = 1; i <= splitDistribution; ++i) {
- int d = m - 1 + i;
-
- generateDist(tuple, tupleEntries1, rec[0], 0, d);
- generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
-
- double overlap = rec[0].overlappedArea(rec[2]);
- if (overlap < minOverlap) {
- splitPoint = d;
- minOverlap = overlap;
- minArea = rec[0].area() + rec[2].area();
- } else if (overlap == minOverlap) {
- double area = rec[0].area() + rec[2].area();
- if (area < minArea) {
- splitPoint = d;
- minArea = area;
- }
- }
- }
- int startIndex, endIndex;
- if (splitPoint < (getTupleCount() + 1) / 2) {
- startIndex = 0;
- endIndex = splitPoint;
- } else {
- startIndex = splitPoint;
- endIndex = (getTupleCount() + 1);
- }
- boolean tupleInserted = false;
- int totalBytes = 0, numOfDeletedTuples = 0;
- for (int i = startIndex; i < endIndex; i++) { // TODO: is there a better
- // way
- // to split the entries?
- if (tupleEntries1.get(i).getTupleIndex() != -1) {
- frameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
- rightFrame.insert(frameTuple, cmp, -1);
- ((UnorderedSlotManager) slotManager).modifySlot(
- slotManager.getSlotOff(tupleEntries1.get(i).getTupleIndex()), -1);
- totalBytes += tupleWriter.bytesRequired(frameTuple);
- numOfDeletedTuples++;
- } else {
- rightFrame.insert(tuple, cmp, -1);
- tupleInserted = true;
- }
- }
-
- ((UnorderedSlotManager) slotManager).deleteEmptySlots();
-
- // maintain space information
- buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + totalBytes
- + (slotManager.getSlotSize() * numOfDeletedTuples));
-
- // compact both pages
- rightFrame.compact(cmp);
- compact(cmp);
-
- if (!tupleInserted) {
- insert(tuple, cmp, -1);
- }
-
- int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
- frameTuple.resetByTupleOffset(buf, tupleOff);
- int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
-
- splitKey.initData(splitKeySize);
- this.adjustMBR(tuples, cmp);
- rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
- rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
-
- ((IRTreeFrame) rightFrame).adjustMBR(((NSMFrame) rightFrame).getTuples(), cmp);
- rTreeTupleWriterRightFrame.writeTupleFields(((NSMFrame) rightFrame).getTuples(), 0,
- rTreeSplitKey.getRightPageBuffer(), 0);
- rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
-
- tupleEntries1.clear();
- tupleEntries2.clear();
- return 0;
- }
-
- private void generateDist(ITupleReference tuple, TupleEntryArrayList entries, Rectangle rec, int start, int end) {
+ public void generateDist(ITupleReference tuple, TupleEntryArrayList entries, Rectangle rec, int start, int end) {
int j = 0;
while (entries.get(j).getTupleIndex() == -1) {
j++;
@@ -304,333 +141,8 @@
public ITreeIndexTupleReference createTupleReference() {
return tupleWriter.createTupleReference();
}
-
- @Override
- public int getBestChildPageId(MultiComparator cmp) {
- return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
- }
- @Override
- public boolean findBestChild(ITupleReference tuple, MultiComparator cmp) {
- cmpFrameTuple.setFieldCount(cmp.getFieldCount());
- frameTuple.setFieldCount(cmp.getFieldCount());
-
- int bestChild = 0;
- double minEnlargedArea = Double.MAX_VALUE;
-
- // the children pointers in the node point to leaves
- if (getLevel() == 1) {
- // find least overlap enlargement, use minimum enlarged area to
- // break tie, if tie still exists use minimum area to break it
- for (int i = 0; i < getTupleCount(); ++i) {
- frameTuple.resetByTupleIndex(this, i);
- double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
- tupleEntries1.add(i, enlargedArea);
- if (enlargedArea < minEnlargedArea) {
- minEnlargedArea = enlargedArea;
- bestChild = i;
- }
- }
- if (minEnlargedArea < tupleEntries1.getDoubleEpsilon() || minEnlargedArea > tupleEntries1.getDoubleEpsilon()) {
- minEnlargedArea = Double.MAX_VALUE;
- int k;
- if (getTupleCount() > nearMinimumOverlapFactor) {
- // sort the entries based on their area enlargement needed
- // to include the object
- tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount());
- k = nearMinimumOverlapFactor;
- } else {
- k = getTupleCount();
- }
-
- double minOverlap = Double.MAX_VALUE;
- int id = 0;
- for (int i = 0; i < k; ++i) {
- double difference = 0.0;
- for (int j = 0; j < getTupleCount(); ++j) {
- frameTuple.resetByTupleIndex(this, j);
- cmpFrameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
-
- int c = cmp.getIntCmp().compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
- frameTuple.getFieldStart(cmp.getKeyFieldCount()),
- frameTuple.getFieldLength(cmp.getKeyFieldCount()),
- cmpFrameTuple.getFieldData(cmp.getKeyFieldCount()),
- cmpFrameTuple.getFieldStart(cmp.getKeyFieldCount()),
- cmpFrameTuple.getFieldLength(cmp.getKeyFieldCount()));
- if (c != 0) {
- double intersection = overlappedArea(frameTuple, tuple, cmpFrameTuple, cmp);
- if (intersection != 0.0) {
- difference += intersection - overlappedArea(frameTuple, null, cmpFrameTuple, cmp);
- }
- } else {
- id = j;
- }
- }
-
- double enlargedArea = enlargedArea(cmpFrameTuple, tuple, cmp);
- if (difference < minOverlap) {
- minOverlap = difference;
- minEnlargedArea = enlargedArea;
- bestChild = id;
- } else if (difference == minOverlap) {
- if (enlargedArea < minEnlargedArea) {
- minEnlargedArea = enlargedArea;
- bestChild = id;
- } else if (enlargedArea == minEnlargedArea) {
- double area = area(cmpFrameTuple, cmp);
- frameTuple.resetByTupleIndex(this, bestChild);
- double minArea = area(frameTuple, cmp);
- if (area < minArea) {
- bestChild = id;
- }
- }
- }
- }
- }
- } else { // find minimum enlarged area, use minimum area to break tie
- for (int i = 0; i < getTupleCount(); i++) {
- frameTuple.resetByTupleIndex(this, i);
- double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
- if (enlargedArea < minEnlargedArea) {
- minEnlargedArea = enlargedArea;
- bestChild = i;
- } else if (enlargedArea == minEnlargedArea) {
- double area = area(frameTuple, cmp);
- frameTuple.resetByTupleIndex(this, bestChild);
- double minArea = area(frameTuple, cmp);
- if (area < minArea) {
- bestChild = i;
- }
- }
- }
- }
- tupleEntries1.clear();
-
- frameTuple.resetByTupleIndex(this, bestChild);
- if (minEnlargedArea > 0.0) {
- return true;
- } else {
- return false;
- }
- }
-
- private double area(ITupleReference tuple, MultiComparator cmp) {
- double area = 1.0;
- int maxFieldPos = cmp.getKeyFieldCount() / 2;
- for (int i = 0; i < maxFieldPos; i++) {
- int j = maxFieldPos + i;
- area *= DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j))
- - DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
- }
- return area;
- }
-
- private double overlappedArea(ITupleReference tuple1, ITupleReference tupleToBeInserted, ITupleReference tuple2,
- MultiComparator cmp) {
- double area = 1.0;
- double f1, f2;
-
- int maxFieldPos = cmp.getKeyFieldCount() / 2;
- for (int i = 0; i < maxFieldPos; i++) {
- int j = maxFieldPos + i;
- double pHigh1, pLow1;
- if (tupleToBeInserted != null) {
- int c = cmp.getComparators()[i].compare(tuple1.getFieldData(i), tuple1.getFieldStart(i),
- tuple1.getFieldLength(i), tupleToBeInserted.getFieldData(i),
- tupleToBeInserted.getFieldStart(i), tupleToBeInserted.getFieldLength(i));
- if (c < 0) {
- pLow1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(i), tuple1.getFieldStart(i));
- } else {
- pLow1 = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(i),
- tupleToBeInserted.getFieldStart(i));
- }
-
- c = cmp.getComparators()[j].compare(tuple1.getFieldData(j), tuple1.getFieldStart(j),
- tuple1.getFieldLength(j), tupleToBeInserted.getFieldData(j),
- tupleToBeInserted.getFieldStart(j), tupleToBeInserted.getFieldLength(j));
- if (c > 0) {
- pHigh1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(j), tuple1.getFieldStart(j));
- } else {
- pHigh1 = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(j),
- tupleToBeInserted.getFieldStart(j));
- }
- } else {
- pLow1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(i), tuple1.getFieldStart(i));
- pHigh1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(j), tuple1.getFieldStart(j));
- }
-
- double pLow2 = DoubleSerializerDeserializer.getDouble(tuple2.getFieldData(i), tuple2.getFieldStart(i));
- double pHigh2 = DoubleSerializerDeserializer.getDouble(tuple2.getFieldData(j), tuple2.getFieldStart(j));
-
- if (pLow1 > pHigh2 || pHigh1 < pLow2) {
- return 0.0;
- }
-
- f1 = Math.max(pLow1, pLow2);
- f2 = Math.min(pHigh1, pHigh2);
- area *= f2 - f1;
- }
- return area;
- }
-
- private double enlargedArea(ITupleReference tuple, ITupleReference tupleToBeInserted, MultiComparator cmp) {
- double areaBeforeEnlarge = area(tuple, cmp);
- double areaAfterEnlarge = 1.0;
-
- int maxFieldPos = cmp.getKeyFieldCount() / 2;
- for (int i = 0; i < maxFieldPos; i++) {
- int j = maxFieldPos + i;
- double pHigh, pLow;
- int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
- tuple.getFieldLength(i), tupleToBeInserted.getFieldData(i), tupleToBeInserted.getFieldStart(i),
- tupleToBeInserted.getFieldLength(i));
- if (c < 0) {
- pLow = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
- } else {
- pLow = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(i),
- tupleToBeInserted.getFieldStart(i));
- }
-
- c = cmp.getComparators()[j].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
- tupleToBeInserted.getFieldData(j), tupleToBeInserted.getFieldStart(j),
- tupleToBeInserted.getFieldLength(j));
- if (c > 0) {
- pHigh = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j));
- } else {
- pHigh = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(j),
- tupleToBeInserted.getFieldStart(j));
- }
- areaAfterEnlarge *= pHigh - pLow;
- }
- return areaAfterEnlarge - areaBeforeEnlarge;
- }
-
- @Override
- public void enlarge(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) {
- System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), frameTuple.getFieldData(i),
- frameTuple.getFieldStart(i), tuple.getFieldLength(i));
- }
- 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) {
- System.arraycopy(tuple.getFieldData(j), tuple.getFieldStart(j), frameTuple.getFieldData(j),
- frameTuple.getFieldStart(j), tuple.getFieldLength(j));
- }
- }
- }
-
- @Override
- public void adjustKey(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
- frameTuple.setFieldCount(cmp.getFieldCount());
- if (tupleIndex == -1) {
- tupleIndex = findTupleByPointer(tuple, cmp);
- }
- if (tupleIndex != -1) {
- tupleWriter.writeTuple(tuple, buf, getTupleOffset(tupleIndex));
- }
- }
-
- @Override
- public int findTupleIndex(ITupleReference tuple, MultiComparator cmp) {
- frameTuple.setFieldCount(cmp.getFieldCount());
- return slotManager.findTupleIndex(tuple, frameTuple, cmp, null, null);
- }
-
- @Override
- public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception {
- frameTuple.setFieldCount(cmp.getFieldCount());
- slotManager.insertSlot(-1, buf.getInt(freeSpaceOff));
- int bytesWritten = tupleWriter.writeTuple(tuple, buf, buf.getInt(freeSpaceOff));
-
- buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
- buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + bytesWritten);
- buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - bytesWritten - slotManager.getSlotSize());
- }
-
- @Override
- public void delete(int tupleIndex, MultiComparator cmp) throws Exception {
- frameTuple.setFieldCount(cmp.getFieldCount());
- int slotOff = slotManager.getSlotOff(tupleIndex);
-
- int tupleOff = slotManager.getTupleOff(slotOff);
- frameTuple.resetByTupleOffset(buf, tupleOff);
- int tupleSize = tupleWriter.bytesRequired(frameTuple);
-
- // perform deletion (we just do a memcpy to overwrite the slot)
- int slotStartOff = slotManager.getSlotEndOff();
- int length = slotOff - slotStartOff;
- System.arraycopy(buf.array(), slotStartOff, buf.array(), slotStartOff + slotManager.getSlotSize(), length);
-
- // maintain space information
- buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
- buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + tupleSize + slotManager.getSlotSize());
- }
-
- @Override
- public int findTupleByPointer(int pageId, MultiComparator cmp) {
- frameTuple.setFieldCount(cmp.getFieldCount());
- for (int i = 0; i < getTupleCount(); i++) {
- frameTuple.resetByTupleIndex(this, i);
- int id = IntegerSerializerDeserializer.getInt(frameTuple.getFieldData(cmp.getKeyFieldCount()),
- frameTuple.getFieldStart(cmp.getKeyFieldCount()));
- if (id == pageId) {
- return i;
- }
- }
- return -1;
- }
-
- @Override
- public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp) {
- frameTuple.setFieldCount(cmp.getFieldCount());
- for (int i = 0; i < getTupleCount(); i++) {
- frameTuple.resetByTupleIndex(this, i);
- int c = cmp.getIntCmp().compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
- frameTuple.getFieldStart(cmp.getKeyFieldCount()),
- frameTuple.getFieldLength(cmp.getKeyFieldCount()), tuple.getFieldData(cmp.getKeyFieldCount()),
- tuple.getFieldStart(cmp.getKeyFieldCount()), tuple.getFieldLength(cmp.getKeyFieldCount()));
- if (c == 0) {
- return i;
- }
- }
- return -1;
- }
-
- @Override
- public int findTupleByPointer(ITupleReference tuple, TraverseList traverseList, int parentIndex, MultiComparator cmp) {
- frameTuple.setFieldCount(cmp.getFieldCount());
- for (int i = 0; i < getTupleCount(); i++) {
- frameTuple.resetByTupleIndex(this, i);
- int c = cmp.getIntCmp().compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
- frameTuple.getFieldStart(cmp.getKeyFieldCount()),
- frameTuple.getFieldLength(cmp.getKeyFieldCount()), tuple.getFieldData(cmp.getKeyFieldCount()),
- tuple.getFieldStart(cmp.getKeyFieldCount()), tuple.getFieldLength(cmp.getKeyFieldCount()));
- if (c == 0) {
- return i;
- } else {
- int pageId = IntegerSerializerDeserializer.getInt(frameTuple.getFieldData(cmp.getKeyFieldCount()),
- frameTuple.getFieldStart(cmp.getKeyFieldCount()));
- traverseList.add(pageId, -1, parentIndex);
- }
- }
- return -1;
- }
-
- @Override
- public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
- for (int i = 0; i < tuples.length; i++) {
- tuples[i].setFieldCount(cmp.getKeyFieldCount());
- tuples[i].resetByTupleIndex(this, 0);
- }
-
+ public void adjustMBRImpl(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
int maxFieldPos = cmp.getKeyFieldCount() / 2;
for (int i = 1; i < getTupleCount(); i++) {
frameTuple.resetByTupleIndex(this, i);
@@ -653,77 +165,6 @@
}
@Override
- public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
- frameTuple.setFieldCount(cmp.getFieldCount());
- frameTuple.resetByTupleIndex(this, tupleIndex);
- int maxFieldPos = cmp.getKeyFieldCount() / 2;
- for (int i = 0; i < maxFieldPos; i++) {
- int j = maxFieldPos + i;
- int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
- tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
- frameTuple.getFieldLength(j));
- if (c > 0) {
- return -1;
- }
- c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
- frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
-
- if (c < 0) {
- return -1;
- }
- }
- return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
- }
-
- @Override
- public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
- frameTuple.setFieldCount(cmp.getFieldCount());
- frameTuple.resetByTupleIndex(this, tupleIndex);
- int maxFieldPos = cmp.getKeyFieldCount() / 2;
- for (int i = 0; i < maxFieldPos; i++) {
- int j = maxFieldPos + i;
- int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
- tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
- frameTuple.getFieldLength(j));
- if (c > 0) {
- return false;
- }
- c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
- frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
-
- if (c < 0) {
- return false;
- }
- }
- return true;
- }
-
- @Override
- public Rectangle checkIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
- frameTuple.setFieldCount(cmp.getFieldCount());
- frameTuple.resetByTupleIndex(this, tupleIndex);
- int maxFieldPos = cmp.getKeyFieldCount() / 2;
- for (int i = 0; i < maxFieldPos; i++) {
- int j = maxFieldPos + i;
- int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
- tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
- frameTuple.getFieldLength(j));
- if (c > 0) {
- return null;
- }
- c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
- frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
-
- if (c < 0) {
- return null;
- }
- }
- Rectangle rec = new Rectangle(maxFieldPos);
- rec.set(frameTuple);
- return rec;
- }
-
- @Override
public void computeMBR(ISplitKey splitKey, MultiComparator cmp) {
RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
@@ -740,31 +181,6 @@
}
@Override
- public boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
- frameTuple.setFieldCount(cmp.getFieldCount());
- frameTuple.resetByTupleIndex(this, tupleIndex);
-
- 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 int getPageHeaderSize() {
return rightPageOff;
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrameFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrameFactory.java
deleted file mode 100644
index 0b84a77..0000000
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMFrameFactory.java
+++ /dev/null
@@ -1,22 +0,0 @@
-package edu.uci.ics.hyracks.storage.am.rtree.frames;
-
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
-
-public class NSMFrameFactory implements ITreeIndexFrameFactory {
-
- private static final long serialVersionUID = 1L;
- private ITreeIndexTupleWriterFactory tupleWriterFactory;
- private int keyFieldCount;
-
- public NSMFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory, int keyFieldCount) {
- this.tupleWriterFactory = tupleWriterFactory;
- this.keyFieldCount = keyFieldCount;
- }
-
- @Override
- public IRTreeFrame createFrame() {
- return new NSMFrame(tupleWriterFactory.createTupleWriter(), keyFieldCount);
- }
-}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMInteriorFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMInteriorFrame.java
new file mode 100644
index 0000000..7cd8bc3
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMInteriorFrame.java
@@ -0,0 +1,633 @@
+package edu.uci.ics.hyracks.storage.am.rtree.frames;
+
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.util.ArrayList;
+import java.util.Collections;
+
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+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.DoubleSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
+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.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.frames.FrameOpSpaceStatus;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.SlotOffTupleOff;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.EntriesOrder;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSplitKey;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.TraverseList;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.UnorderedSlotManager;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriter;
+
+public class NSMInteriorFrame extends NSMFrame implements IRTreeInteriorFrame {
+
+ private static final int childPtrSize = 4;
+
+ public NSMInteriorFrame(ITreeIndexTupleWriter tupleWriter, int keyFieldCount) {
+ super(tupleWriter, keyFieldCount);
+ }
+
+ @Override
+ public String printKeys(MultiComparator cmp, ISerializerDeserializer[] fields) throws HyracksDataException {
+ StringBuilder strBuilder = new StringBuilder();
+ int tupleCount = buf.getInt(tupleCountOff);
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+ for (int i = 0; i < tupleCount; i++) {
+ frameTuple.resetByTupleIndex(this, i);
+ for (int j = 0; j < cmp.getKeyFieldCount(); j++) {
+ ByteArrayInputStream inStream = new ByteArrayInputStream(frameTuple.getFieldData(j),
+ frameTuple.getFieldStart(j), frameTuple.getFieldLength(j));
+ DataInput dataIn = new DataInputStream(inStream);
+ Object o = fields[j].deserialize(dataIn);
+ strBuilder.append(o.toString() + " ");
+ }
+ strBuilder.append(" | ");
+ }
+ strBuilder.append("\n");
+ return strBuilder.toString();
+ }
+
+ @Override
+ public boolean findBestChild(ITupleReference tuple, MultiComparator cmp) {
+ cmpFrameTuple.setFieldCount(cmp.getKeyFieldCount());
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+
+ int bestChild = 0;
+ double minEnlargedArea = Double.MAX_VALUE;
+
+ // the children pointers in the node point to leaves
+ if (getLevel() == 1) {
+ // find least overlap enlargement, use minimum enlarged area to
+ // break tie, if tie still exists use minimum area to break it
+ for (int i = 0; i < getTupleCount(); ++i) {
+ frameTuple.resetByTupleIndex(this, i);
+ double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
+ tupleEntries1.add(i, enlargedArea);
+ if (enlargedArea < minEnlargedArea) {
+ minEnlargedArea = enlargedArea;
+ bestChild = i;
+ }
+ }
+ if (minEnlargedArea < tupleEntries1.getDoubleEpsilon()
+ || minEnlargedArea > tupleEntries1.getDoubleEpsilon()) {
+ minEnlargedArea = Double.MAX_VALUE;
+ int k;
+ if (getTupleCount() > nearMinimumOverlapFactor) {
+ // sort the entries based on their area enlargement needed
+ // to include the object
+ tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount());
+ k = nearMinimumOverlapFactor;
+ } else {
+ k = getTupleCount();
+ }
+
+ double minOverlap = Double.MAX_VALUE;
+ int id = 0;
+ for (int i = 0; i < k; ++i) {
+ double difference = 0.0;
+ for (int j = 0; j < getTupleCount(); ++j) {
+ frameTuple.resetByTupleIndex(this, j);
+ cmpFrameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
+
+ int c = pointerCmp(frameTuple, cmpFrameTuple, cmp);
+ if (c != 0) {
+ double intersection = overlappedArea(frameTuple, tuple, cmpFrameTuple, cmp);
+ if (intersection != 0.0) {
+ difference += intersection - overlappedArea(frameTuple, null, cmpFrameTuple, cmp);
+ }
+ } else {
+ id = j;
+ }
+ }
+
+ double enlargedArea = enlargedArea(cmpFrameTuple, tuple, cmp);
+ if (difference < minOverlap) {
+ minOverlap = difference;
+ minEnlargedArea = enlargedArea;
+ bestChild = id;
+ } else if (difference == minOverlap) {
+ if (enlargedArea < minEnlargedArea) {
+ minEnlargedArea = enlargedArea;
+ bestChild = id;
+ } else if (enlargedArea == minEnlargedArea) {
+ double area = area(cmpFrameTuple, cmp);
+ frameTuple.resetByTupleIndex(this, bestChild);
+ double minArea = area(frameTuple, cmp);
+ if (area < minArea) {
+ bestChild = id;
+ }
+ }
+ }
+ }
+ }
+ } else { // find minimum enlarged area, use minimum area to break tie
+ for (int i = 0; i < getTupleCount(); i++) {
+ frameTuple.resetByTupleIndex(this, i);
+ double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
+ if (enlargedArea < minEnlargedArea) {
+ minEnlargedArea = enlargedArea;
+ bestChild = i;
+ } else if (enlargedArea == minEnlargedArea) {
+ double area = area(frameTuple, cmp);
+ frameTuple.resetByTupleIndex(this, bestChild);
+ double minArea = area(frameTuple, cmp);
+ if (area < minArea) {
+ bestChild = i;
+ }
+ }
+ }
+ }
+ tupleEntries1.clear();
+
+ frameTuple.resetByTupleIndex(this, bestChild);
+ if (minEnlargedArea > 0.0) {
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ @Override
+ public int getBestChildPageId(MultiComparator cmp) {
+ return buf.getInt(getChildPointerOff(frameTuple, cmp));
+ }
+
+ @Override
+ public int findTupleByPointer(ITupleReference tuple, MultiComparator cmp) {
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+ for (int i = 0; i < getTupleCount(); i++) {
+ frameTuple.resetByTupleIndex(this, i);
+ int c = pointerCmp(frameTuple, tuple, cmp);
+ if (c == 0) {
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ @Override
+ public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+ frameTuple.resetByTupleIndex(this, tupleIndex);
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+ frameTuple.getFieldLength(j));
+ if (c > 0) {
+ return -1;
+ }
+ c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
+ frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
+ if (c < 0) {
+ return -1;
+ }
+ }
+ // return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
+ return buf.getInt(getChildPointerOff(frameTuple, cmp));
+ }
+
+ @Override
+ public int findTupleByPointer(ITupleReference tuple, TraverseList traverseList, int parentIndex, MultiComparator cmp) {
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+ for (int i = 0; i < getTupleCount(); i++) {
+ frameTuple.resetByTupleIndex(this, i);
+
+ int c = pointerCmp(frameTuple, tuple, cmp);
+ if (c == 0) {
+ return i;
+ } else {
+ int pageId = IntegerSerializerDeserializer.getInt(frameTuple.getFieldData(cmp.getKeyFieldCount() - 1),
+ getChildPointerOff(frameTuple, cmp));
+ traverseList.add(pageId, -1, parentIndex);
+ }
+ }
+ return -1;
+ }
+
+ @Override
+ public boolean compact(MultiComparator cmp) {
+ resetSpaceParams();
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+
+ int tupleCount = buf.getInt(tupleCountOff);
+ int freeSpace = buf.getInt(freeSpaceOff);
+
+ ArrayList<SlotOffTupleOff> sortedTupleOffs = new ArrayList<SlotOffTupleOff>();
+ sortedTupleOffs.ensureCapacity(tupleCount);
+ for (int i = 0; i < tupleCount; i++) {
+ int slotOff = slotManager.getSlotOff(i);
+ int tupleOff = slotManager.getTupleOff(slotOff);
+ sortedTupleOffs.add(new SlotOffTupleOff(i, slotOff, tupleOff));
+ }
+ Collections.sort(sortedTupleOffs);
+
+ for (int i = 0; i < sortedTupleOffs.size(); i++) {
+ int tupleOff = sortedTupleOffs.get(i).tupleOff;
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+
+ int tupleEndOff = frameTuple.getFieldStart(frameTuple.getFieldCount() - 1)
+ + frameTuple.getFieldLength(frameTuple.getFieldCount() - 1);
+ int tupleLength = tupleEndOff - tupleOff + childPtrSize;
+ System.arraycopy(buf.array(), tupleOff, buf.array(), freeSpace, tupleLength);
+
+ slotManager.setSlot(sortedTupleOffs.get(i).slotOff, freeSpace);
+ freeSpace += tupleLength;
+ }
+
+ buf.putInt(freeSpaceOff, freeSpace);
+ buf.putInt(totalFreeSpaceOff, buf.capacity() - freeSpace - tupleCount * slotManager.getSlotSize());
+
+ return false;
+ }
+
+ @Override
+ public FrameOpSpaceStatus hasSpaceInsert(ITupleReference tuple, MultiComparator cmp) {
+ int bytesRequired = tupleWriter.bytesRequired(tuple) + childPtrSize; // for
+ // the
+ // child
+ // pointer
+ if (bytesRequired + slotManager.getSlotSize() <= buf.capacity() - buf.getInt(freeSpaceOff)
+ - (buf.getInt(tupleCountOff) * slotManager.getSlotSize()))
+ return FrameOpSpaceStatus.SUFFICIENT_CONTIGUOUS_SPACE;
+ else if (bytesRequired + slotManager.getSlotSize() <= buf.getInt(totalFreeSpaceOff))
+ return FrameOpSpaceStatus.SUFFICIENT_SPACE;
+ else
+ return FrameOpSpaceStatus.INSUFFICIENT_SPACE;
+ }
+
+
+
+ @Override
+ public void adjustKey(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+ if (tupleIndex == -1) {
+ tupleIndex = findTupleByPointer(tuple, cmp);
+ }
+ if (tupleIndex != -1) {
+ tupleWriter.writeTuple(tuple, buf, getTupleOffset(tupleIndex));
+ }
+ }
+
+ private int pointerCmp(ITupleReference tupleA, ITupleReference tupleB, MultiComparator cmp) {
+ return cmp.getIntCmp().compare(tupleA.getFieldData(cmp.getKeyFieldCount() - 1),
+ getChildPointerOff(tupleA, cmp), childPtrSize, tupleB.getFieldData(cmp.getKeyFieldCount() - 1),
+ getChildPointerOff(tupleB, cmp), childPtrSize);
+ }
+
+ @Override
+ public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey)
+ throws Exception {
+
+ rightFrame.setPageTupleFieldCount(cmp.getKeyFieldCount());
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+
+ RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
+ RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
+ RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
+
+ // calculations are based on the R*-tree paper
+ int m = (int) Math.floor((getTupleCount() + 1) * splitFactor);
+ int splitDistribution = getTupleCount() - (2 * m) + 2;
+
+ // to calculate the minimum margin in order to pick the split axis
+ double minMargin = Double.MAX_VALUE;
+ int splitAxis = 0, sortOrder = 0;
+
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ for (int k = 0; k < getTupleCount(); ++k) {
+
+ frameTuple.resetByTupleIndex(this, k);
+
+ double LowerKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(i),
+ frameTuple.getFieldStart(i));
+ double UpperKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(j),
+ frameTuple.getFieldStart(j));
+
+ tupleEntries1.add(k, LowerKey);
+ tupleEntries2.add(k, UpperKey);
+ }
+ double LowerKey = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
+ double UpperKey = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j));
+
+ tupleEntries1.add(-1, LowerKey);
+ tupleEntries2.add(-1, UpperKey);
+
+ tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+ tupleEntries2.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+
+ double lowerMargin = 0.0, upperMargin = 0.0;
+ // generate distribution
+ for (int k = 1; k <= splitDistribution; ++k) {
+ int d = m - 1 + k;
+
+ generateDist(tuple, tupleEntries1, rec[0], 0, d);
+ generateDist(tuple, tupleEntries2, rec[1], 0, d);
+ generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
+ generateDist(tuple, tupleEntries2, rec[3], d, getTupleCount() + 1);
+
+ // calculate the margin of the distributions
+ lowerMargin += rec[0].margin() + rec[2].margin();
+ upperMargin += rec[1].margin() + rec[3].margin();
+ }
+ double margin = Math.min(lowerMargin, upperMargin);
+
+ // store minimum margin as split axis
+ if (margin < minMargin) {
+ minMargin = margin;
+ splitAxis = i;
+ sortOrder = (lowerMargin < upperMargin) ? 0 : 2;
+ }
+
+ tupleEntries1.clear();
+ tupleEntries2.clear();
+ }
+
+ for (int i = 0; i < getTupleCount(); ++i) {
+ frameTuple.resetByTupleIndex(this, i);
+ double key = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(splitAxis + sortOrder),
+ frameTuple.getFieldStart(splitAxis + sortOrder));
+ tupleEntries1.add(i, key);
+ }
+ double key = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(splitAxis + sortOrder),
+ tuple.getFieldStart(splitAxis + sortOrder));
+ tupleEntries1.add(-1, key);
+ tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+
+ double minArea = Double.MAX_VALUE;
+ double minOverlap = Double.MAX_VALUE;
+ int splitPoint = 0;
+ for (int i = 1; i <= splitDistribution; ++i) {
+ int d = m - 1 + i;
+
+ generateDist(tuple, tupleEntries1, rec[0], 0, d);
+ generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
+
+ double overlap = rec[0].overlappedArea(rec[2]);
+ if (overlap < minOverlap) {
+ splitPoint = d;
+ minOverlap = overlap;
+ minArea = rec[0].area() + rec[2].area();
+ } else if (overlap == minOverlap) {
+ double area = rec[0].area() + rec[2].area();
+ if (area < minArea) {
+ splitPoint = d;
+ minArea = area;
+ }
+ }
+ }
+ int startIndex, endIndex;
+ if (splitPoint < (getTupleCount() + 1) / 2) {
+ startIndex = 0;
+ endIndex = splitPoint;
+ } else {
+ startIndex = splitPoint;
+ endIndex = (getTupleCount() + 1);
+ }
+ boolean tupleInserted = false;
+ int totalBytes = 0, numOfDeletedTuples = 0;
+ for (int i = startIndex; i < endIndex; i++) {
+ if (tupleEntries1.get(i).getTupleIndex() != -1) {
+ frameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
+ rightFrame.insert(frameTuple, cmp, -1);
+ ((UnorderedSlotManager) slotManager).modifySlot(
+ slotManager.getSlotOff(tupleEntries1.get(i).getTupleIndex()), -1);
+ totalBytes += tupleWriter.bytesRequired(frameTuple) + childPtrSize;
+ numOfDeletedTuples++;
+ } else {
+ rightFrame.insert(tuple, cmp, -1);
+ tupleInserted = true;
+ }
+ }
+
+ ((UnorderedSlotManager) slotManager).deleteEmptySlots();
+
+ // maintain space information
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + totalBytes
+ + (slotManager.getSlotSize() * numOfDeletedTuples));
+
+ // compact both pages
+ rightFrame.compact(cmp);
+ compact(cmp);
+
+ if (!tupleInserted) {
+ insert(tuple, cmp, -1);
+ }
+
+ int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+ int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
+
+ splitKey.initData(splitKeySize);
+ this.adjustMBR(tuples, cmp);
+ rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
+ rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
+
+ ((IRTreeFrame) rightFrame).adjustMBR(((NSMFrame) rightFrame).getTuples(), cmp);
+ rTreeTupleWriterRightFrame.writeTupleFields(((NSMFrame) rightFrame).getTuples(), 0,
+ rTreeSplitKey.getRightPageBuffer(), 0);
+ rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
+
+ tupleEntries1.clear();
+ tupleEntries2.clear();
+ return 0;
+ }
+
+ private int getChildPointerOff(ITupleReference tuple, MultiComparator cmp) {
+ return tuple.getFieldStart(cmp.getKeyFieldCount() - 1) + tuple.getFieldLength(cmp.getKeyFieldCount() - 1);
+ }
+
+ @Override
+ public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception {
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+ slotManager.insertSlot(-1, buf.getInt(freeSpaceOff));
+ int freeSpace = buf.getInt(freeSpaceOff);
+ int bytesWritten = tupleWriter.writeTupleFields(tuple, 0, cmp.getKeyFieldCount(), buf, freeSpace);
+ System.arraycopy(tuple.getFieldData(cmp.getKeyFieldCount() - 1), getChildPointerOff(tuple, cmp), buf.array(),
+ freeSpace + bytesWritten, childPtrSize);
+ int tupleSize = bytesWritten + childPtrSize;
+
+ buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
+ buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + tupleSize);
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - tupleSize - slotManager.getSlotSize());
+
+ }
+
+ @Override
+ public void delete(int tupleIndex, MultiComparator cmp) throws Exception {
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+ int slotOff = slotManager.getSlotOff(tupleIndex);
+
+ int tupleOff = slotManager.getTupleOff(slotOff);
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+ int tupleSize = tupleWriter.bytesRequired(frameTuple);
+
+ // perform deletion (we just do a memcpy to overwrite the slot)
+ int slotStartOff = slotManager.getSlotEndOff();
+ int length = slotOff - slotStartOff;
+ System.arraycopy(buf.array(), slotStartOff, buf.array(), slotStartOff + slotManager.getSlotSize(), length);
+
+ // maintain space information
+ buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
+ buf.putInt(totalFreeSpaceOff,
+ buf.getInt(totalFreeSpaceOff) + tupleSize + childPtrSize + slotManager.getSlotSize());
+ }
+
+ @Override
+ public boolean recomputeMBR(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+ frameTuple.setFieldCount(cmp.getKeyFieldCount());
+ frameTuple.resetByTupleIndex(this, tupleIndex);
+
+ 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;
+ }
+
+ private double overlappedArea(ITupleReference tuple1, ITupleReference tupleToBeInserted, ITupleReference tuple2,
+ MultiComparator cmp) {
+ double area = 1.0;
+ double f1, f2;
+
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ double pHigh1, pLow1;
+ if (tupleToBeInserted != null) {
+ int c = cmp.getComparators()[i].compare(tuple1.getFieldData(i), tuple1.getFieldStart(i),
+ tuple1.getFieldLength(i), tupleToBeInserted.getFieldData(i),
+ tupleToBeInserted.getFieldStart(i), tupleToBeInserted.getFieldLength(i));
+ if (c < 0) {
+ pLow1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(i), tuple1.getFieldStart(i));
+ } else {
+ pLow1 = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(i),
+ tupleToBeInserted.getFieldStart(i));
+ }
+
+ c = cmp.getComparators()[j].compare(tuple1.getFieldData(j), tuple1.getFieldStart(j),
+ tuple1.getFieldLength(j), tupleToBeInserted.getFieldData(j),
+ tupleToBeInserted.getFieldStart(j), tupleToBeInserted.getFieldLength(j));
+ if (c > 0) {
+ pHigh1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(j), tuple1.getFieldStart(j));
+ } else {
+ pHigh1 = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(j),
+ tupleToBeInserted.getFieldStart(j));
+ }
+ } else {
+ pLow1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(i), tuple1.getFieldStart(i));
+ pHigh1 = DoubleSerializerDeserializer.getDouble(tuple1.getFieldData(j), tuple1.getFieldStart(j));
+ }
+
+ double pLow2 = DoubleSerializerDeserializer.getDouble(tuple2.getFieldData(i), tuple2.getFieldStart(i));
+ double pHigh2 = DoubleSerializerDeserializer.getDouble(tuple2.getFieldData(j), tuple2.getFieldStart(j));
+
+ if (pLow1 > pHigh2 || pHigh1 < pLow2) {
+ return 0.0;
+ }
+
+ f1 = Math.max(pLow1, pLow2);
+ f2 = Math.min(pHigh1, pHigh2);
+ area *= f2 - f1;
+ }
+ return area;
+ }
+
+ private double enlargedArea(ITupleReference tuple, ITupleReference tupleToBeInserted, MultiComparator cmp) {
+ double areaBeforeEnlarge = area(tuple, cmp);
+ double areaAfterEnlarge = 1.0;
+
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ double pHigh, pLow;
+ int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i), tupleToBeInserted.getFieldData(i), tupleToBeInserted.getFieldStart(i),
+ tupleToBeInserted.getFieldLength(i));
+ if (c < 0) {
+ pLow = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
+ } else {
+ pLow = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(i),
+ tupleToBeInserted.getFieldStart(i));
+ }
+
+ c = cmp.getComparators()[j].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
+ tupleToBeInserted.getFieldData(j), tupleToBeInserted.getFieldStart(j),
+ tupleToBeInserted.getFieldLength(j));
+ if (c > 0) {
+ pHigh = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j));
+ } else {
+ pHigh = DoubleSerializerDeserializer.getDouble(tupleToBeInserted.getFieldData(j),
+ tupleToBeInserted.getFieldStart(j));
+ }
+ areaAfterEnlarge *= pHigh - pLow;
+ }
+ return areaAfterEnlarge - areaBeforeEnlarge;
+ }
+
+ private double area(ITupleReference tuple, MultiComparator cmp) {
+ double area = 1.0;
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ area *= DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j))
+ - DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
+ }
+ return area;
+ }
+
+ @Override
+ public void enlarge(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) {
+ System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), frameTuple.getFieldData(i),
+ frameTuple.getFieldStart(i), tuple.getFieldLength(i));
+ }
+ 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) {
+ System.arraycopy(tuple.getFieldData(j), tuple.getFieldStart(j), frameTuple.getFieldData(j),
+ frameTuple.getFieldStart(j), tuple.getFieldLength(j));
+ }
+ }
+ }
+
+ @Override
+ public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
+ for (int i = 0; i < tuples.length; i++) {
+ tuples[i].setFieldCount(cmp.getKeyFieldCount());
+ tuples[i].resetByTupleIndex(this, 0);
+ }
+
+ adjustMBRImpl(tuples, cmp);
+ }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMInteriorFrameFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMInteriorFrameFactory.java
new file mode 100644
index 0000000..690592f
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMInteriorFrameFactory.java
@@ -0,0 +1,22 @@
+package edu.uci.ics.hyracks.storage.am.rtree.frames;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+
+public class NSMInteriorFrameFactory implements ITreeIndexFrameFactory {
+
+ private static final long serialVersionUID = 1L;
+ private ITreeIndexTupleWriterFactory tupleWriterFactory;
+ private int keyFieldCount;
+
+ public NSMInteriorFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory, int keyFieldCount) {
+ this.tupleWriterFactory = tupleWriterFactory;
+ this.keyFieldCount = keyFieldCount;
+ }
+
+ @Override
+ public IRTreeInteriorFrame createFrame() {
+ return new NSMInteriorFrame(tupleWriterFactory.createTupleWriter(), keyFieldCount);
+ }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMLeafFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMLeafFrame.java
new file mode 100644
index 0000000..14938b3
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMLeafFrame.java
@@ -0,0 +1,251 @@
+package edu.uci.ics.hyracks.storage.am.rtree.frames;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.ISplitKey;
+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.api.ITreeIndexTupleWriter;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.EntriesOrder;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSplitKey;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.UnorderedSlotManager;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriter;
+
+public class NSMLeafFrame extends NSMFrame implements IRTreeLeafFrame {
+
+ public NSMLeafFrame(ITreeIndexTupleWriter tupleWriter, int keyFieldCount) {
+ super(tupleWriter, keyFieldCount);
+ }
+
+ @Override
+ public int findTupleIndex(ITupleReference tuple, MultiComparator cmp) {
+ frameTuple.setFieldCount(cmp.getFieldCount());
+ return slotManager.findTupleIndex(tuple, frameTuple, cmp, null, null);
+ }
+
+ @Override
+ public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
+ frameTuple.setFieldCount(cmp.getFieldCount());
+ frameTuple.resetByTupleIndex(this, tupleIndex);
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
+ tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+ frameTuple.getFieldLength(j));
+ if (c > 0) {
+ return false;
+ }
+ c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
+ frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
+
+ if (c < 0) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ @Override
+ public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey)
+ throws Exception {
+
+ rightFrame.setPageTupleFieldCount(cmp.getFieldCount());
+ frameTuple.setFieldCount(cmp.getFieldCount());
+
+ RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
+ RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
+ RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
+
+ // calculations are based on the R*-tree paper
+ int m = (int) Math.floor((getTupleCount() + 1) * splitFactor);
+ int splitDistribution = getTupleCount() - (2 * m) + 2;
+
+ // to calculate the minimum margin in order to pick the split axis
+ double minMargin = Double.MAX_VALUE;
+ int splitAxis = 0, sortOrder = 0;
+
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ for (int k = 0; k < getTupleCount(); ++k) {
+
+ frameTuple.resetByTupleIndex(this, k);
+
+ double LowerKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(i),
+ frameTuple.getFieldStart(i));
+ double UpperKey = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(j),
+ frameTuple.getFieldStart(j));
+
+ tupleEntries1.add(k, LowerKey);
+ tupleEntries2.add(k, UpperKey);
+ }
+ double LowerKey = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(i), tuple.getFieldStart(i));
+ double UpperKey = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(j), tuple.getFieldStart(j));
+
+ tupleEntries1.add(-1, LowerKey);
+ tupleEntries2.add(-1, UpperKey);
+
+ tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+ tupleEntries2.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+
+ double lowerMargin = 0.0, upperMargin = 0.0;
+ // generate distribution
+ for (int k = 1; k <= splitDistribution; ++k) {
+ int d = m - 1 + k;
+
+ generateDist(tuple, tupleEntries1, rec[0], 0, d);
+ generateDist(tuple, tupleEntries2, rec[1], 0, d);
+ generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
+ generateDist(tuple, tupleEntries2, rec[3], d, getTupleCount() + 1);
+
+ // calculate the margin of the distributions
+ lowerMargin += rec[0].margin() + rec[2].margin();
+ upperMargin += rec[1].margin() + rec[3].margin();
+ }
+ double margin = Math.min(lowerMargin, upperMargin);
+
+ // store minimum margin as split axis
+ if (margin < minMargin) {
+ minMargin = margin;
+ splitAxis = i;
+ sortOrder = (lowerMargin < upperMargin) ? 0 : 2;
+ }
+
+ tupleEntries1.clear();
+ tupleEntries2.clear();
+ }
+
+ for (int i = 0; i < getTupleCount(); ++i) {
+ frameTuple.resetByTupleIndex(this, i);
+ double key = DoubleSerializerDeserializer.getDouble(frameTuple.getFieldData(splitAxis + sortOrder),
+ frameTuple.getFieldStart(splitAxis + sortOrder));
+ tupleEntries1.add(i, key);
+ }
+ double key = DoubleSerializerDeserializer.getDouble(tuple.getFieldData(splitAxis + sortOrder),
+ tuple.getFieldStart(splitAxis + sortOrder));
+ tupleEntries1.add(-1, key);
+ tupleEntries1.sort(EntriesOrder.ASCENDING, getTupleCount() + 1);
+
+ double minArea = Double.MAX_VALUE;
+ double minOverlap = Double.MAX_VALUE;
+ int splitPoint = 0;
+ for (int i = 1; i <= splitDistribution; ++i) {
+ int d = m - 1 + i;
+
+ generateDist(tuple, tupleEntries1, rec[0], 0, d);
+ generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
+
+ double overlap = rec[0].overlappedArea(rec[2]);
+ if (overlap < minOverlap) {
+ splitPoint = d;
+ minOverlap = overlap;
+ minArea = rec[0].area() + rec[2].area();
+ } else if (overlap == minOverlap) {
+ double area = rec[0].area() + rec[2].area();
+ if (area < minArea) {
+ splitPoint = d;
+ minArea = area;
+ }
+ }
+ }
+ int startIndex, endIndex;
+ if (splitPoint < (getTupleCount() + 1) / 2) {
+ startIndex = 0;
+ endIndex = splitPoint;
+ } else {
+ startIndex = splitPoint;
+ endIndex = (getTupleCount() + 1);
+ }
+ boolean tupleInserted = false;
+ int totalBytes = 0, numOfDeletedTuples = 0;
+ for (int i = startIndex; i < endIndex; i++) {
+ if (tupleEntries1.get(i).getTupleIndex() != -1) {
+ frameTuple.resetByTupleIndex(this, tupleEntries1.get(i).getTupleIndex());
+ rightFrame.insert(frameTuple, cmp, -1);
+ ((UnorderedSlotManager) slotManager).modifySlot(
+ slotManager.getSlotOff(tupleEntries1.get(i).getTupleIndex()), -1);
+ totalBytes += tupleWriter.bytesRequired(frameTuple);
+ numOfDeletedTuples++;
+ } else {
+ rightFrame.insert(tuple, cmp, -1);
+ tupleInserted = true;
+ }
+ }
+
+ ((UnorderedSlotManager) slotManager).deleteEmptySlots();
+
+ // maintain space information
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + totalBytes
+ + (slotManager.getSlotSize() * numOfDeletedTuples));
+
+ // compact both pages
+ rightFrame.compact(cmp);
+ compact(cmp);
+
+ if (!tupleInserted) {
+ insert(tuple, cmp, -1);
+ }
+
+ int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+ int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
+
+ splitKey.initData(splitKeySize);
+ this.adjustMBR(tuples, cmp);
+ rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
+ rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
+
+ ((IRTreeFrame) rightFrame).adjustMBR(((NSMFrame) rightFrame).getTuples(), cmp);
+ rTreeTupleWriterRightFrame.writeTupleFields(((NSMFrame) rightFrame).getTuples(), 0,
+ rTreeSplitKey.getRightPageBuffer(), 0);
+ rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
+
+ tupleEntries1.clear();
+ tupleEntries2.clear();
+ return 0;
+ }
+
+ @Override
+ public void insert(ITupleReference tuple, MultiComparator cmp, int tupleIndex) throws Exception {
+ frameTuple.setFieldCount(cmp.getFieldCount());
+ slotManager.insertSlot(-1, buf.getInt(freeSpaceOff));
+ int bytesWritten = tupleWriter.writeTuple(tuple, buf, buf.getInt(freeSpaceOff));
+
+ buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) + 1);
+ buf.putInt(freeSpaceOff, buf.getInt(freeSpaceOff) + bytesWritten);
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) - bytesWritten - slotManager.getSlotSize());
+ }
+
+ @Override
+ public void delete(int tupleIndex, MultiComparator cmp) throws Exception {
+ frameTuple.setFieldCount(cmp.getFieldCount());
+ int slotOff = slotManager.getSlotOff(tupleIndex);
+
+ int tupleOff = slotManager.getTupleOff(slotOff);
+ frameTuple.resetByTupleOffset(buf, tupleOff);
+ int tupleSize = tupleWriter.bytesRequired(frameTuple);
+
+ // perform deletion (we just do a memcpy to overwrite the slot)
+ int slotStartOff = slotManager.getSlotEndOff();
+ int length = slotOff - slotStartOff;
+ System.arraycopy(buf.array(), slotStartOff, buf.array(), slotStartOff + slotManager.getSlotSize(), length);
+
+ // maintain space information
+ buf.putInt(tupleCountOff, buf.getInt(tupleCountOff) - 1);
+ buf.putInt(totalFreeSpaceOff, buf.getInt(totalFreeSpaceOff) + tupleSize + slotManager.getSlotSize());
+ }
+
+ @Override
+ public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
+ for (int i = 0; i < tuples.length; i++) {
+ tuples[i].setFieldCount(cmp.getFieldCount());
+ tuples[i].resetByTupleIndex(this, 0);
+ }
+
+ adjustMBRImpl(tuples, cmp);
+ }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMLeafFrameFactory.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMLeafFrameFactory.java
new file mode 100644
index 0000000..01811d2
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMLeafFrameFactory.java
@@ -0,0 +1,22 @@
+package edu.uci.ics.hyracks.storage.am.rtree.frames;
+
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
+
+public class NSMLeafFrameFactory implements ITreeIndexFrameFactory {
+
+ private static final long serialVersionUID = 1L;
+ private ITreeIndexTupleWriterFactory tupleWriterFactory;
+ private int keyFieldCount;
+
+ public NSMLeafFrameFactory(ITreeIndexTupleWriterFactory tupleWriterFactory, int keyFieldCount) {
+ this.tupleWriterFactory = tupleWriterFactory;
+ this.keyFieldCount = keyFieldCount;
+ }
+
+ @Override
+ public IRTreeLeafFrame createFrame() {
+ return new NSMLeafFrame(tupleWriterFactory.createTupleWriter(), keyFieldCount);
+ }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/ByteArrayList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/ByteArrayList.java
deleted file mode 100644
index c6aebea..0000000
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/ByteArrayList.java
+++ /dev/null
@@ -1,53 +0,0 @@
-package edu.uci.ics.hyracks.storage.am.rtree.impls;
-
-public class ByteArrayList {
- private byte[] data;
- private int size;
- private final int growth;
-
- public ByteArrayList(int initialCapacity, int growth) {
- data = new byte[initialCapacity];
- size = 0;
- this.growth = growth;
- }
-
- public int size() {
- return size;
- }
-
- public void add(byte i) {
- if (size == data.length) {
- byte[] newData = new byte[data.length + growth];
- System.arraycopy(data, 0, newData, 0, data.length);
- data = newData;
- }
-
- data[size++] = i;
- }
-
- public void removeLast() {
- if (size > 0)
- size--;
- }
-
- // WARNING: caller is responsible for checking size > 0
- public byte getLast() {
- return data[size - 1];
- }
-
- public byte get(int i) {
- return data[i];
- }
-
- public void set(int i, byte b) {
- data[i] = b;
- }
-
- public void clear() {
- size = 0;
- }
-
- public boolean isEmpty() {
- return size == 0;
- }
-}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/InteriorFrameSchema.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/InteriorFrameSchema.java
deleted file mode 100644
index d8801a7..0000000
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/InteriorFrameSchema.java
+++ /dev/null
@@ -1,26 +0,0 @@
-package edu.uci.ics.hyracks.storage.am.rtree.impls;
-
-import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
-import edu.uci.ics.hyracks.api.dataflow.value.TypeTrait;
-import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-
-public class InteriorFrameSchema {
-
- private MultiComparator interiorCmp;
-
- public InteriorFrameSchema(MultiComparator leafCmp) {
- // 1 for node's pointer
- ITypeTrait[] interiorTypeTraits = new ITypeTrait[leafCmp.getKeyFieldCount() + 1];
- for (int i = 0; i < leafCmp.getKeyFieldCount(); i++) {
- interiorTypeTraits[i] = new TypeTrait(leafCmp.getTypeTraits()[i].getStaticallyKnownDataLength());
- }
-
- // the pointer is of type int (size: 4 bytes)
- interiorTypeTraits[leafCmp.getKeyFieldCount()] = new TypeTrait(4);
- interiorCmp = new MultiComparator(interiorTypeTraits, leafCmp.getComparators());
- }
-
- public MultiComparator getInteriorCmp() {
- return interiorCmp;
- }
-}
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/PathList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/PathList.java
index 093bc8c..80ddfab 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/PathList.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/PathList.java
@@ -15,6 +15,8 @@
package edu.uci.ics.hyracks.storage.am.rtree.impls;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
+
public class PathList {
private IntArrayList pageIds;
private IntArrayList pageLsns;
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 f7cbef9..5494217 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
@@ -23,6 +23,8 @@
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOpContext;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMFrame;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
@@ -31,6 +33,7 @@
public class RTree implements ITreeIndex {
private boolean created = false;
+ private boolean loaded = false;
private final int rootPage = 1; // the root page never changes
private final AtomicInteger globalNsn; // Global node sequence number
@@ -44,8 +47,7 @@
private final SearchPredicate diskOrderScanPredicate;
private final ITreeIndexFrameFactory interiorFrameFactory;
private final ITreeIndexFrameFactory leafFrameFactory;
- private final MultiComparator interiorCmp;
- private final MultiComparator leafCmp;
+ private final MultiComparator cmp;
public int rootSplits = 0;
public int[] splitsByLevel = new int[500];
@@ -58,17 +60,15 @@
public byte currentLevel = 0;
public RTree(IBufferCache bufferCache, IFreePageManager freePageManager,
- ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory,
- MultiComparator interiorCmp, MultiComparator leafCmp) {
+ ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory leafFrameFactory, MultiComparator cmp) {
this.bufferCache = bufferCache;
this.freePageManager = freePageManager;
this.interiorFrameFactory = interiorFrameFactory;
this.leafFrameFactory = leafFrameFactory;
- this.interiorCmp = interiorCmp;
- this.leafCmp = leafCmp;
+ this.cmp = cmp;
globalNsn = new AtomicInteger();
this.treeLatch = new ReentrantReadWriteLock(true);
- this.diskOrderScanPredicate = new SearchPredicate(null, interiorCmp, leafCmp);
+ this.diskOrderScanPredicate = new SearchPredicate(null, cmp);
}
public void incrementGlobalNsn() {
@@ -154,14 +154,14 @@
String keyString;
if (interiorFrame.isLeaf()) {
leafFrame.setPage(node);
- keyString = leafFrame.printKeys(leafCmp, fields);
+ keyString = leafFrame.printKeys(cmp, fields);
} else {
- keyString = interiorFrame.printKeys(interiorCmp, fields);
+ keyString = interiorFrame.printKeys(cmp, fields);
}
System.out.format(keyString);
if (!interiorFrame.isLeaf()) {
- ArrayList<Integer> children = ((NSMFrame) (interiorFrame)).getChildren(interiorCmp);
+ ArrayList<Integer> children = ((NSMFrame) (interiorFrame)).getChildren(cmp);
for (int i = 0; i < children.size(); i++) {
printTree(children.get(i), node, i == children.size() - 1, leafFrame, interiorFrame, fields);
}
@@ -227,7 +227,7 @@
@Override
public RTreeOpContext createOpContext(IndexOp op, ITreeIndexFrame leafFrame, ITreeIndexFrame interiorFrame,
ITreeIndexMetaDataFrame metaFrame) {
- return new RTreeOpContext(op, (IRTreeFrame) leafFrame, (IRTreeFrame) interiorFrame, metaFrame, 8);
+ return new RTreeOpContext(op, (IRTreeLeafFrame) leafFrame, (IRTreeInteriorFrame) interiorFrame, metaFrame, 8);
}
@Override
@@ -236,10 +236,10 @@
ctx.reset();
ctx.setTuple(tuple);
ctx.splitKey.reset();
- ctx.splitKey.getLeftTuple().setFieldCount(interiorCmp.getFieldCount());
- ctx.splitKey.getRightTuple().setFieldCount(interiorCmp.getFieldCount());
- ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
- ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
+ ctx.splitKey.getLeftTuple().setFieldCount(cmp.getKeyFieldCount());
+ ctx.splitKey.getRightTuple().setFieldCount(cmp.getKeyFieldCount());
+ ctx.interiorFrame.setPageTupleFieldCount(cmp.getKeyFieldCount());
+ ctx.leafFrame.setPageTupleFieldCount(cmp.getFieldCount());
ICachedPage leafNode = findLeaf(ctx);
@@ -259,7 +259,6 @@
incrementWriteLatchesReleased();
bufferCache.unpin(leafNode);
incrementUnpins();
-
}
public ICachedPage findLeaf(RTreeOpContext ctx) throws Exception {
@@ -325,57 +324,43 @@
ctx.pathList.add(pageId, pageLsn, -1);
if (!isLeaf) {
- // checkEnlargement must be called *before* getBestChildPageId
- boolean needsEnlargement = ctx.interiorFrame.findBestChild(ctx.getTuple(), interiorCmp);
- int childPageId = ctx.interiorFrame.getBestChildPageId(interiorCmp);
+ // findBestChild must be called *before* getBestChildPageId
+ ctx.interiorFrame.findBestChild(ctx.getTuple(), cmp);
+ int childPageId = ctx.interiorFrame.getBestChildPageId(cmp);
- if (needsEnlargement) {
- if (!writeLatched) {
- node.releaseReadLatch();
- 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();
- incrementWriteLatchesAcquired();
- ctx.interiorFrame.setPage(node);
- writeLatched = true;
-
- if (ctx.interiorFrame.getPageLsn() != pageLsn) {
- // The page was changed while we unlocked it; thus,
- // retry (re-choose best child)
-
- ctx.pathList.removeLast();
- continue;
- }
- }
-
- // We don't need to reset the frameTuple because it is
- // already pointing to the best child
- ctx.interiorFrame.enlarge(ctx.getTuple(), interiorCmp);
-
- node.releaseWriteLatch();
- incrementWriteLatchesReleased();
+ if (!writeLatched) {
+ node.releaseReadLatch();
+ incrementReadLatchesReleased();
+ // TODO: do we need to un-pin and pin again?
bufferCache.unpin(node);
incrementUnpins();
- writeLatched = false;
- } else {
- if (writeLatched) {
- node.releaseWriteLatch();
- incrementWriteLatchesReleased();
- bufferCache.unpin(node);
- incrementUnpins();
- writeLatched = false;
- } else {
- node.releaseReadLatch();
- incrementReadLatchesReleased();
- bufferCache.unpin(node);
- incrementUnpins();
+
+ node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ incrementPins();
+ node.acquireWriteLatch();
+ incrementWriteLatchesAcquired();
+ ctx.interiorFrame.setPage(node);
+ writeLatched = true;
+
+ if (ctx.interiorFrame.getPageLsn() != pageLsn) {
+ // The page was changed while we unlocked it; thus,
+ // retry (re-choose best child)
+
+ ctx.pathList.removeLast();
+ 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();
+ incrementWriteLatchesReleased();
+ bufferCache.unpin(node);
+ incrementUnpins();
+ writeLatched = false;
+
pageId = childPageId;
parentLsn = pageLsn;
} else {
@@ -389,19 +374,19 @@
throws Exception {
FrameOpSpaceStatus spaceStatus;
if (!isLeaf) {
- spaceStatus = ctx.interiorFrame.hasSpaceInsert(tuple, interiorCmp);
+ spaceStatus = ctx.interiorFrame.hasSpaceInsert(tuple, cmp);
} else {
- spaceStatus = ctx.leafFrame.hasSpaceInsert(tuple, leafCmp);
+ spaceStatus = ctx.leafFrame.hasSpaceInsert(tuple, cmp);
}
switch (spaceStatus) {
case SUFFICIENT_CONTIGUOUS_SPACE: {
if (!isLeaf) {
- ctx.interiorFrame.insert(tuple, interiorCmp, -1);
+ ctx.interiorFrame.insert(tuple, cmp, -1);
incrementGlobalNsn();
ctx.interiorFrame.setPageLsn(getGlobalNsn());
} else {
- ctx.leafFrame.insert(tuple, leafCmp, -1);
+ ctx.leafFrame.insert(tuple, cmp, -1);
incrementGlobalNsn();
ctx.leafFrame.setPageLsn(getGlobalNsn());
}
@@ -411,13 +396,13 @@
case SUFFICIENT_SPACE: {
if (!isLeaf) {
- ctx.interiorFrame.compact(interiorCmp);
- ctx.interiorFrame.insert(tuple, interiorCmp, -1);
+ ctx.interiorFrame.compact(cmp);
+ ctx.interiorFrame.insert(tuple, cmp, -1);
incrementGlobalNsn();
ctx.interiorFrame.setPageLsn(getGlobalNsn());
} else {
- ctx.leafFrame.compact(leafCmp);
- ctx.leafFrame.insert(tuple, leafCmp, -1);
+ ctx.leafFrame.compact(cmp);
+ ctx.leafFrame.insert(tuple, cmp, -1);
incrementGlobalNsn();
ctx.leafFrame.setPageLsn(getGlobalNsn());
}
@@ -441,8 +426,8 @@
rightFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
rightFrame.setPage(rightNode);
rightFrame.initBuffer((byte) ctx.interiorFrame.getLevel());
- rightFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
- ret = ctx.interiorFrame.split(rightFrame, tuple, interiorCmp, ctx.splitKey);
+ rightFrame.setPageTupleFieldCount(cmp.getKeyFieldCount());
+ ret = ctx.interiorFrame.split(rightFrame, tuple, cmp, ctx.splitKey);
ctx.interiorFrame.setRightPage(rightPageId);
rightFrame.setPageNsn(ctx.interiorFrame.getPageNsn());
incrementGlobalNsn();
@@ -455,8 +440,8 @@
rightFrame = (IRTreeFrame) leafFrameFactory.createFrame();
rightFrame.setPage(rightNode);
rightFrame.initBuffer((byte) 0);
- rightFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
- ret = ctx.leafFrame.split(rightFrame, tuple, leafCmp, ctx.splitKey);
+ rightFrame.setPageTupleFieldCount(cmp.getFieldCount());
+ ret = ctx.leafFrame.split(rightFrame, tuple, cmp, ctx.splitKey);
ctx.leafFrame.setRightPage(rightPageId);
rightFrame.setPageNsn(ctx.leafFrame.getPageNsn());
incrementGlobalNsn();
@@ -494,8 +479,8 @@
ctx.splitKey.setLeftPage(newLeftId);
- ctx.interiorFrame.insert(ctx.splitKey.getLeftTuple(), interiorCmp, -1);
- ctx.interiorFrame.insert(ctx.splitKey.getRightTuple(), interiorCmp, -1);
+ ctx.interiorFrame.insert(ctx.splitKey.getLeftTuple(), cmp, -1);
+ ctx.interiorFrame.insert(ctx.splitKey.getRightTuple(), cmp, -1);
incrementGlobalNsn();
int newNsn = getGlobalNsn();
@@ -532,7 +517,7 @@
if (ctx.interiorFrame.getPageLsn() != ctx.pathList.getLastPageLsn()) {
foundParent = false;
while (true) {
- if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), interiorCmp) != -1) {
+ if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), cmp) != -1) {
// found the parent
foundParent = true;
break;
@@ -556,7 +541,7 @@
}
}
if (foundParent) {
- ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), -1, interiorCmp);
+ ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), -1, cmp);
insertTuple(parentNode, parentId, ctx.splitKey.getRightTuple(), ctx, ctx.interiorFrame.isLeaf());
ctx.pathList.removeLast();
@@ -605,8 +590,7 @@
}
parentLsn = pageLsn;
- if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), ctx.traverseList, pageIndex,
- interiorCmp) != -1) {
+ if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), ctx.traverseList, pageIndex, cmp) != -1) {
fillPath(ctx, pageIndex);
node.releaseReadLatch();
@@ -635,9 +619,9 @@
ctx.reset();
ctx.setTuple(tuple);
ctx.splitKey.reset();
- ctx.splitKey.getLeftTuple().setFieldCount(interiorCmp.getFieldCount());
- ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
- ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
+ ctx.splitKey.getLeftTuple().setFieldCount(cmp.getKeyFieldCount());
+ ctx.interiorFrame.setPageTupleFieldCount(cmp.getKeyFieldCount());
+ ctx.leafFrame.setPageTupleFieldCount(cmp.getFieldCount());
int tupleIndex = findTupleToDelete(ctx);
@@ -674,7 +658,7 @@
if (ctx.interiorFrame.getPageLsn() != ctx.pathList.getLastPageLsn()) {
foundParent = false;
while (true) {
- tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), interiorCmp);
+ tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), cmp);
if (tupleIndex != -1) {
// found the parent
foundParent = true;
@@ -700,12 +684,12 @@
}
if (foundParent) {
if (tupleIndex == -1) {
- tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), interiorCmp);
+ tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), cmp);
}
- boolean recomputeMBR = ctx.interiorFrame.recomputeMBR(ctx.splitKey.getLeftTuple(), tupleIndex, interiorCmp);
+ boolean recomputeMBR = ctx.interiorFrame.recomputeMBR(ctx.splitKey.getLeftTuple(), tupleIndex, cmp);
if (recomputeMBR) {
- ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), tupleIndex, interiorCmp);
+ ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), tupleIndex, cmp);
ctx.pathList.removeLast();
incrementGlobalNsn();
@@ -713,7 +697,7 @@
ctx.splitKey.reset();
if (!ctx.pathList.isEmpty()) {
- ctx.interiorFrame.computeMBR(ctx.splitKey, interiorCmp);
+ ctx.interiorFrame.computeMBR(ctx.splitKey, cmp);
ctx.splitKey.setLeftPage(parentId);
}
} else {
@@ -768,7 +752,7 @@
if (!isLeaf) {
for (int i = 0; i < ctx.interiorFrame.getTupleCount(); i++) {
- int childPageId = ctx.interiorFrame.getChildPageIdIfIntersect(ctx.tuple, i, interiorCmp);
+ int childPageId = ctx.interiorFrame.getChildPageIdIfIntersect(ctx.tuple, i, cmp);
if (childPageId != -1) {
ctx.traverseList.add(childPageId, -1, pageIndex);
ctx.pathList.add(childPageId, pageLsn, ctx.traverseList.size() - 1);
@@ -776,7 +760,7 @@
}
} else {
ctx.leafFrame.setPage(node);
- int tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, leafCmp);
+ int tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, cmp);
if (tupleIndex != -1) {
node.releaseReadLatch();
@@ -793,7 +777,7 @@
if (ctx.leafFrame.getPageLsn() != pageLsn) {
// The page was changed while we unlocked it
- tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, leafCmp);
+ tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, cmp);
if (tupleIndex == -1) {
ctx.traverseList.add(pageId, -1, parentIndex);
ctx.pathList.add(pageId, parentLsn, ctx.traverseList.size() - 1);
@@ -818,13 +802,13 @@
}
public void deleteTuple(int pageId, int tupleIndex, RTreeOpContext ctx) throws Exception {
- ctx.leafFrame.delete(tupleIndex, leafCmp);
+ ctx.leafFrame.delete(tupleIndex, cmp);
incrementGlobalNsn();
ctx.leafFrame.setPageLsn(getGlobalNsn());
// if the page is empty, just leave it there for future inserts
if (pageId != rootPage && ctx.leafFrame.getTupleCount() > 0) {
- ctx.leafFrame.computeMBR(ctx.splitKey, leafCmp);
+ ctx.leafFrame.computeMBR(ctx.splitKey, cmp);
ctx.splitKey.setLeftPage(pageId);
}
}
@@ -839,60 +823,6 @@
ctx.cursor.open(ctx.cursorInitialState, pred);
}
- public void search(Stack<Integer> s, ITupleReference tuple, RTreeOpContext ctx, ArrayList<Rectangle> results)
- throws Exception {
- ctx.reset();
- ctx.setTuple(tuple);
- ctx.interiorFrame.setPageTupleFieldCount(interiorCmp.getFieldCount());
- ctx.leafFrame.setPageTupleFieldCount(leafCmp.getFieldCount());
- s.push(rootPage);
- while (!s.isEmpty()) {
- int pageId = s.pop();
- ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
- incrementPins();
- node.acquireReadLatch();
- incrementReadLatchesAcquired();
-
- try {
-
- ctx.interiorFrame.setPage(node);
- boolean isLeaf = ctx.interiorFrame.isLeaf();
- int tupleCount = ctx.interiorFrame.getTupleCount();
-
- if (!isLeaf) {
- for (int i = 0; i < tupleCount; i++) {
- // check intersection, if intersect, call search
- int childPageId = ctx.interiorFrame.getChildPageIdIfIntersect(ctx.tuple, i, interiorCmp);
- if (childPageId != -1) {
- s.push(childPageId);
- }
- }
-
- } else {
- for (int i = 0; i < tupleCount; i++) {
- ctx.leafFrame.setPage(node);
-
- // check intersection, if intersect, add the tuple to
- // the
- // result set
- Rectangle rec = ctx.leafFrame.checkIntersect(ctx.tuple, i, leafCmp);
- if (rec != null) {
- // add the tuple to the result set
- results.add(rec);
- }
- }
-
- }
-
- } finally {
- node.releaseReadLatch();
- incrementReadLatchesReleased();
- bufferCache.unpin(node);
- incrementUnpins();
- }
- }
- }
-
public ITreeIndexFrameFactory getInteriorFrameFactory() {
return interiorFrameFactory;
}
@@ -901,12 +831,8 @@
return leafFrameFactory;
}
- public MultiComparator getInteriorCmp() {
- return interiorCmp;
- }
-
- public MultiComparator getLeafCmp() {
- return leafCmp;
+ public MultiComparator getCmp() {
+ return cmp;
}
public IFreePageManager getFreePageManager() {
@@ -918,35 +844,60 @@
throw new Exception("RTree Update not implemented.");
}
+ public final class BulkLoadContext implements IIndexBulkLoadContext {
+
+ public RTreeOpContext insertOpCtx;
+
+ public BulkLoadContext(float fillFactor, IRTreeFrame leafFrame, IRTreeFrame interiorFrame,
+ ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
+
+ insertOpCtx = createOpContext(IndexOp.INSERT, leafFrame, interiorFrame, metaFrame);
+ }
+ }
+
@Override
public IIndexBulkLoadContext beginBulkLoad(float fillFactor, ITreeIndexFrame leafFrame,
ITreeIndexFrame interiorFrame, ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException {
- throw new HyracksDataException("RTree Bulkload not implemented.");
+ // throw new HyracksDataException("RTree Bulkload not implemented.");
+
+ if (loaded)
+ throw new HyracksDataException("Trying to bulk-load RTree but has RTree already been loaded.");
+
+ BulkLoadContext ctx = new BulkLoadContext(fillFactor, (IRTreeFrame) leafFrame, (IRTreeFrame) interiorFrame,
+ metaFrame);
+ return ctx;
}
@Override
public void bulkLoadAddTuple(IIndexBulkLoadContext ictx, ITupleReference tuple) throws HyracksDataException {
- throw new HyracksDataException("RTree Bulkload not implemented.");
+ // throw new HyracksDataException("RTree Bulkload not implemented.");
+
+ try {
+ insert(tuple, ((BulkLoadContext) ictx).insertOpCtx);
+ } catch (Exception e) {
+ // TODO Auto-generated catch block
+ e.printStackTrace();
+ }
}
@Override
public void endBulkLoad(IIndexBulkLoadContext ictx) throws HyracksDataException {
- throw new HyracksDataException("RTree Bulkload not implemented.");
+ // throw new HyracksDataException("RTree Bulkload not implemented.");
+
+ loaded = true;
}
@Override
- public void diskOrderScan(ITreeIndexCursor icursor,
- ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame, IndexOpContext ictx)
- throws HyracksDataException {
- RTreeDiskOrderScanCursor cursor = (RTreeDiskOrderScanCursor)icursor;
+ public void diskOrderScan(ITreeIndexCursor icursor, ITreeIndexFrame leafFrame, ITreeIndexMetaDataFrame metaFrame,
+ IndexOpContext ictx) throws HyracksDataException {
+ RTreeDiskOrderScanCursor cursor = (RTreeDiskOrderScanCursor) icursor;
RTreeOpContext ctx = (RTreeOpContext) ictx;
ctx.reset();
-
+
int currentPageId = rootPage + 1;
int maxPageId = freePageManager.getMaxPage(metaFrame);
- ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(
- fileId, currentPageId), false);
+ ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false);
page.acquireReadLatch();
cursor.setBufferCache(bufferCache);
cursor.setFileId(fileId);
@@ -956,7 +907,6 @@
cursor.open(ctx.cursorInitialState, diskOrderScanPredicate);
}
-
@Override
public int getRootPageId() {
return rootPage;
@@ -964,7 +914,7 @@
@Override
public int getFieldCount() {
- return leafCmp.getFieldCount();
+ return cmp.getFieldCount();
}
@Override
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeDiskOrderScanCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeDiskOrderScanCursor.java
index de66e77..f852905 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeDiskOrderScanCursor.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeDiskOrderScanCursor.java
@@ -118,8 +118,8 @@
tupleIndex = 0;
frame.setPage(page);
SearchPredicate pred = (SearchPredicate) searchPred;
- MultiComparator leafCmp = pred.getLeafCmp();
- frameTuple.setFieldCount(leafCmp.getFieldCount());
+ MultiComparator cmp = pred.getCmp();
+ frameTuple.setFieldCount(cmp.getFieldCount());
boolean leafExists = positionToNextLeaf(false);
if (!leafExists) {
throw new HyracksDataException(
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 f377bba..5ad9965 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
@@ -5,12 +5,13 @@
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.IndexOpContext;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+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 IndexOpContext {
public final IndexOp op;
- public final IRTreeFrame interiorFrame;
- public final IRTreeFrame leafFrame;
+ public final IRTreeInteriorFrame interiorFrame;
+ public final IRTreeLeafFrame leafFrame;
public ITreeIndexCursor cursor;
public CursorInitialState cursorInitialState;
public final ITreeIndexMetaDataFrame metaFrame;
@@ -20,7 +21,7 @@
// of the visited pages
public final TraverseList traverseList; // used for traversing the tree
- public RTreeOpContext(IndexOp op, IRTreeFrame leafFrame, IRTreeFrame interiorFrame,
+ public RTreeOpContext(IndexOp op, IRTreeLeafFrame leafFrame, IRTreeInteriorFrame interiorFrame,
ITreeIndexMetaDataFrame metaFrame, int treeHeightHint) {
this.op = op;
this.interiorFrame = interiorFrame;
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 478acb2..481c034 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
@@ -2,12 +2,14 @@
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.DoubleSerializerDeserializer;
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.ITreeIndexTupleReference;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+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.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
import edu.uci.ics.hyracks.storage.common.file.BufferedFileHandle;
@@ -16,8 +18,8 @@
private int fileId = -1;
private ICachedPage page = null;
- private IRTreeFrame interiorFrame = null;
- private IRTreeFrame leafFrame = null;
+ private IRTreeInteriorFrame interiorFrame = null;
+ private IRTreeLeafFrame leafFrame = null;
private IBufferCache bufferCache = null;
private SearchPredicate pred;
@@ -28,15 +30,14 @@
private int tupleIndex = 0;
private int tupleIndexInc = 0;
- private MultiComparator leafCmp;
- private MultiComparator interiorCmp;
+ private MultiComparator cmp;
private ITreeIndexTupleReference frameTuple;
private int pin = 0;
private int unpin = 0;
- public RTreeSearchCursor(IRTreeFrame interiorFrame, IRTreeFrame leafFrame) {
+ public RTreeSearchCursor(IRTreeInteriorFrame interiorFrame, IRTreeLeafFrame leafFrame) {
this.interiorFrame = interiorFrame;
this.leafFrame = leafFrame;
this.frameTuple = leafFrame.createTupleReference();
@@ -51,7 +52,7 @@
tupleIndex = 0;
tupleIndexInc = 0;
page = null;
- pathList.clear();
+ pathList = null;
}
public ITupleReference getTuple() {
@@ -85,7 +86,7 @@
if (!isLeaf) {
for (int i = 0; i < interiorFrame.getTupleCount(); i++) {
- int childPageId = interiorFrame.getChildPageIdIfIntersect(searchKey, i, interiorCmp);
+ int childPageId = interiorFrame.getChildPageIdIfIntersect(searchKey, i, cmp);
if (childPageId != -1) {
pathList.add(childPageId, pageLsn, -1);
}
@@ -110,6 +111,10 @@
@Override
public boolean hasNext() throws Exception {
+ if (page == null) {
+ return false;
+ }
+
if (tupleIndex == leafFrame.getTupleCount()) {
if (!fetchNextLeafPage()) {
return false;
@@ -118,7 +123,7 @@
do {
for (int i = tupleIndex; i < leafFrame.getTupleCount(); i++) {
- if (leafFrame.intersect(searchKey, i, leafCmp)) {
+ if (leafFrame.intersect(searchKey, i, cmp)) {
frameTuple.resetByTupleIndex(leafFrame, i);
tupleIndexInc = i + 1;
return true;
@@ -146,12 +151,11 @@
rootPage = ((CursorInitialState) initialState).getRootPage();
pred = (SearchPredicate) searchPred;
- interiorCmp = pred.getInteriorCmp();
- leafCmp = pred.getLeafCmp();
+ cmp = pred.getCmp();
searchKey = pred.getSearchKey();
-
+
pathList.add(this.rootPage, -1, -1);
- frameTuple.setFieldCount(leafCmp.getFieldCount());
+ frameTuple.setFieldCount(cmp.getFieldCount());
tupleIndex = 0;
fetchNextLeafPage();
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchPredicate.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchPredicate.java
index c83f0e2..4ad6223 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchPredicate.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/SearchPredicate.java
@@ -9,13 +9,11 @@
private static final long serialVersionUID = 1L;
protected ITupleReference searchKey;
- protected MultiComparator interiorCmp;
- protected MultiComparator leafCmp;
+ protected MultiComparator cmp;
- public SearchPredicate(ITupleReference searchKey, MultiComparator interiorCmp, MultiComparator leafCmp) {
+ public SearchPredicate(ITupleReference searchKey, MultiComparator cmp) {
this.searchKey = searchKey;
- this.interiorCmp = interiorCmp;
- this.leafCmp = leafCmp;
+ this.cmp = cmp;
}
public ITupleReference getSearchKey() {
@@ -26,11 +24,7 @@
this.searchKey = searchKey;
}
- public MultiComparator getInteriorCmp() {
- return interiorCmp;
- }
-
- public MultiComparator getLeafCmp() {
- return leafCmp;
+ public MultiComparator getCmp() {
+ return cmp;
}
}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/TraverseList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/TraverseList.java
index c09971d..6a4d45c 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/TraverseList.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/TraverseList.java
@@ -15,6 +15,8 @@
package edu.uci.ics.hyracks.storage.am.rtree.impls;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IntArrayList;
+
public class TraverseList {
private IntArrayList pageIds;
private IntArrayList pageLsns;
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 e90cc0d..8cffd4d 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
@@ -1,13 +1,9 @@
package edu.uci.ics.hyracks.storage.am.rtree;
-import java.io.BufferedReader;
import java.io.DataOutput;
import java.io.File;
-import java.io.FileReader;
import java.nio.ByteBuffer;
-import java.util.ArrayList;
import java.util.Random;
-import java.util.Stack;
import org.junit.Test;
@@ -27,7 +23,6 @@
import edu.uci.ics.hyracks.dataflow.common.data.comparators.DoubleBinaryComparatorFactory;
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.impls.BTreeOpContext;
import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
@@ -37,13 +32,14 @@
import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.utility.TreeIndexStats;
+import edu.uci.ics.hyracks.storage.am.common.utility.TreeIndexStatsGatherer;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
-import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMFrameFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMLeafFrameFactory;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeDiskOrderScanCursor;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.Rectangle;
import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
@@ -52,9 +48,9 @@
public class RTreeTest extends AbstractRTreeTest {
- private static final int PAGE_SIZE = 1024;
- private static final int NUM_PAGES = 10000;
- private static final int MAX_OPEN_FILES = 10;
+ private static final int PAGE_SIZE = 8192;
+ private static final int NUM_PAGES = 20;
+ private static final int MAX_OPEN_FILES = 20;
private static final int HYRACKS_FRAME_SIZE = 128;
private IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
@@ -77,26 +73,23 @@
cmps[2] = cmps[0];
cmps[3] = cmps[0];
- // declare leaf-frame-tuple fields
- int leafFieldCount = 7;
- ITypeTrait[] leafTypeTraits = new ITypeTrait[leafFieldCount];
- leafTypeTraits[0] = new TypeTrait(8);
- leafTypeTraits[1] = new TypeTrait(8);
- leafTypeTraits[2] = new TypeTrait(8);
- leafTypeTraits[3] = new TypeTrait(8);
- leafTypeTraits[4] = new TypeTrait(8);
- leafTypeTraits[5] = new TypeTrait(4);
- leafTypeTraits[6] = new TypeTrait(8);
+ // declare tuple fields
+ int fieldCount = 7;
+ ITypeTrait[] typeTraits = new ITypeTrait[fieldCount];
+ typeTraits[0] = new TypeTrait(8);
+ typeTraits[1] = new TypeTrait(8);
+ typeTraits[2] = new TypeTrait(8);
+ typeTraits[3] = new TypeTrait(8);
+ typeTraits[4] = new TypeTrait(8);
+ typeTraits[5] = new TypeTrait(4);
+ typeTraits[6] = new TypeTrait(8);
- MultiComparator leafCmp = new MultiComparator(leafTypeTraits, cmps);
- InteriorFrameSchema interiorFrameSchema = new InteriorFrameSchema(leafCmp);
+ MultiComparator cmp = new MultiComparator(typeTraits, cmps);
- RTreeTypeAwareTupleWriterFactory interiorTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(
- interiorFrameSchema.getInteriorCmp().getTypeTraits());
- RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
+ RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
- ITreeIndexFrameFactory interiorFrameFactory = new NSMFrameFactory(interiorTupleWriterFactory, keyFieldCount);
- ITreeIndexFrameFactory leafFrameFactory = new NSMFrameFactory(leafTupleWriterFactory, keyFieldCount);
+ ITreeIndexFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(tupleWriterFactory, keyFieldCount);
+ ITreeIndexFrameFactory leafFrameFactory = new NSMLeafFrameFactory(tupleWriterFactory, keyFieldCount);
ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
@@ -104,14 +97,13 @@
IRTreeFrame leafFrame = (IRTreeFrame) leafFrameFactory.createFrame();
IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
- RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory,
- interiorFrameSchema.getInteriorCmp(), leafCmp);
+ RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, cmp);
rtree.create(fileId, leafFrame, metaFrame);
rtree.open(fileId);
ByteBuffer hyracksFrame = ctx.allocateFrame();
FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
- ArrayTupleBuilder tb = new ArrayTupleBuilder(leafCmp.getFieldCount());
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(cmp.getFieldCount());
DataOutput dos = tb.getDataOutput();
@SuppressWarnings("rawtypes")
@@ -131,7 +123,6 @@
Random rnd2 = new Random();
rnd2.setSeed(50);
- Stack<Integer> s = new Stack<Integer>();
for (int i = 0; i < 10000; i++) {
double p1x = rnd.nextDouble();
@@ -164,7 +155,6 @@
tuple.reset(accessor, 0);
- long end = System.currentTimeMillis();
print("INSERTING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x)
+ " " + Math.max(p1y, p2y) + "\n");
@@ -179,34 +169,19 @@
// rtree.printTree(leafFrame, interiorFrame, recDescSers);
// System.out.println();
- RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame);
- ArrayList<Rectangle> results = new ArrayList<Rectangle>();
- rtree.search(s, tuple, searchOpCtx, results);
+ String rtreeStats = rtree.printStats();
+ print(rtreeStats);
- // for (int i = 0; i < results.size(); i++) {
- // for (int j = 0; j < dim; j++) {
- // System.out.print(results.get(i).getLow(j) + " " +
- // results.get(i).getHigh(j));
- // }
- // System.out.println();
- // }
- System.out.println("Number of Results: " + results.size());
-
- String stats = rtree.printStats();
- print(stats);
-
-
// disk-order scan
print("DISK-ORDER SCAN:\n");
RTreeDiskOrderScanCursor diskOrderCursor = new RTreeDiskOrderScanCursor(leafFrame);
- RTreeOpContext diskOrderScanOpCtx = rtree.createOpContext(IndexOp.DISKORDERSCAN,
- leafFrame, null, null);
+ RTreeOpContext diskOrderScanOpCtx = rtree.createOpContext(IndexOp.DISKORDERSCAN, leafFrame, null, null);
rtree.diskOrderScan(diskOrderCursor, leafFrame, metaFrame, diskOrderScanOpCtx);
try {
while (diskOrderCursor.hasNext()) {
diskOrderCursor.next();
ITupleReference frameTuple = diskOrderCursor.getTuple();
- String rec = leafCmp.printTuple(frameTuple, recDescSers);
+ String rec = cmp.printTuple(frameTuple, recDescSers);
print(rec + "\n");
}
} catch (Exception e) {
@@ -214,356 +189,12 @@
} finally {
diskOrderCursor.close();
}
-
- // TreeIndexStatsGatherer statsGatherer = new
- // TreeIndexStatsGatherer(bufferCache, freePageManager, fileId, rtree.getRootPageId());
- // TreeIndexStats stats = statsGatherer.gatherStats(leafFrame,
- // interiorFrame, metaFrame);
- // String string = stats.toString();
- // System.out.println(string);
- rtree.close();
- bufferCache.closeFile(fileId);
- bufferCache.close();
-
- }
-
- // @Test
- public void test02() throws Exception {
-
- TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
- IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
- IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
- FileReference file = new FileReference(new File(fileName));
- bufferCache.createFile(file);
- int fileId = fmp.lookupFileId(file);
- bufferCache.openFile(fileId);
-
- // declare interior-frame-tuple fields
- int interiorFieldCount = 5;
- ITypeTrait[] interiorTypeTraits = new ITypeTrait[interiorFieldCount];
- interiorTypeTraits[0] = new TypeTrait(8);
- interiorTypeTraits[1] = new TypeTrait(8);
- interiorTypeTraits[2] = new TypeTrait(8);
- interiorTypeTraits[3] = new TypeTrait(8);
- interiorTypeTraits[4] = new TypeTrait(4);
-
- // declare keys
- int keyFieldCount = 4;
- IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
- cmps[0] = DoubleBinaryComparatorFactory.INSTANCE.createBinaryComparator();
- cmps[1] = cmps[0];
- cmps[2] = cmps[0];
- cmps[3] = cmps[0];
-
- // declare leaf-frame-tuple fields
- int leafFieldCount = 5;
- ITypeTrait[] leafTypeTraits = new ITypeTrait[leafFieldCount];
- leafTypeTraits[0] = new TypeTrait(8);
- leafTypeTraits[1] = new TypeTrait(8);
- leafTypeTraits[2] = new TypeTrait(8);
- leafTypeTraits[3] = new TypeTrait(8);
- leafTypeTraits[4] = new TypeTrait(4);
-
- MultiComparator interiorCmp = new MultiComparator(interiorTypeTraits, cmps);
- MultiComparator leafCmp = new MultiComparator(leafTypeTraits, cmps);
-
- RTreeTypeAwareTupleWriterFactory interiorTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(
- interiorTypeTraits);
- RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
-
- ITreeIndexFrameFactory interiorFrameFactory = new NSMFrameFactory(interiorTupleWriterFactory, keyFieldCount);
- ITreeIndexFrameFactory leafFrameFactory = new NSMFrameFactory(leafTupleWriterFactory, keyFieldCount);
- ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
- ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
-
- IRTreeFrame interiorFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
- IRTreeFrame leafFrame = (IRTreeFrame) leafFrameFactory.createFrame();
- IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
-
- RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, interiorCmp,
- leafCmp);
- rtree.create(fileId, leafFrame, metaFrame);
- rtree.open(fileId);
-
- ByteBuffer hyracksFrame = ctx.allocateFrame();
- FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
- ArrayTupleBuilder tb = new ArrayTupleBuilder(leafCmp.getFieldCount());
- DataOutput dos = tb.getDataOutput();
-
- @SuppressWarnings("rawtypes")
- ISerializerDeserializer[] recDescSers = { DoubleSerializerDeserializer.INSTANCE,
- DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
- DoubleSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
- RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
- IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
- accessor.reset(hyracksFrame);
- FrameTupleReference tuple = new FrameTupleReference();
-
- RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, leafFrame, interiorFrame, metaFrame);
-
- File datasetFile = new File("/home/salsubaiee/dataset.txt");
- BufferedReader reader = new BufferedReader(new FileReader(datasetFile));
-
- Random rnd = new Random();
- rnd.setSeed(50);
- String inputLine = reader.readLine();
- int index = 0;
-
- while (inputLine != null) {
-
- String[] splittedLine1 = inputLine.split(",");
- String[] splittedLine2 = splittedLine1[0].split("\\s");
-
- double p1x = 0;
- double p1y = 0;
-
- try {
- p1x = Double.valueOf(splittedLine2[1].trim()).doubleValue();
- p1y = Double.valueOf(splittedLine2[2].trim()).doubleValue();
- } catch (Exception e) {
- inputLine = reader.readLine();
- continue;
- }
- double p2x = p1x;
- double p2y = p1y;
-
- int pk = rnd.nextInt();
-
- tb.reset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p1x, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p1y, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p2x, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p2y, dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
- tb.addFieldEndOffset();
-
- appender.reset(hyracksFrame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
-
- tuple.reset(accessor, 0);
-
- long end = System.currentTimeMillis();
- print("INSERTING " + index + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x)
- + " " + Math.max(p1y, p2y) + "\n");
-
- try {
- rtree.insert(tuple, insertOpCtx);
- } catch (TreeIndexException e) {
- } catch (Exception e) {
- e.printStackTrace();
- }
-
- if (index == 1000) {
- break;
- }
- inputLine = reader.readLine();
- index++;
-
- // rtree.printTree(leafFrame, interiorFrame, recDescSers);
- // System.out.println();
- }
-
- // rtree.printTree(leafFrame, interiorFrame, recDescSers);
- // System.out.println();
-
- RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame);
-
- File querysetFile = new File("/home/salsubaiee/queryset.txt");
- BufferedReader reader2 = new BufferedReader(new FileReader(querysetFile));
-
- inputLine = reader2.readLine();
- int totalResults = 0;
- index = 0;
- Stack<Integer> s = new Stack<Integer>();
- while (inputLine != null) {
-
- String[] splittedLine1 = inputLine.split(",");
- String[] splittedLine2 = splittedLine1[0].split("\\s");
-
- double p1x;
- double p1y;
- double p2x;
- double p2y;
-
- try {
- p1x = Double.valueOf(splittedLine2[1].trim()).doubleValue();
- p1y = Double.valueOf(splittedLine2[2].trim()).doubleValue();
- p2x = Double.valueOf(splittedLine2[3].trim()).doubleValue();
- p2y = Double.valueOf(splittedLine2[4].trim()).doubleValue();
- } catch (Exception e) {
- inputLine = reader2.readLine();
- continue;
- }
-
- int pk = rnd.nextInt();
-
- tb.reset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p1x, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p1y, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p2x, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p2y, dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
- tb.addFieldEndOffset();
-
- appender.reset(hyracksFrame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
-
- tuple.reset(accessor, 0);
-
- long end = System.currentTimeMillis();
- print("SEARCHING " + index + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x)
- + " " + Math.max(p1y, p2y) + "\n");
-
- try {
- ArrayList<Rectangle> results = new ArrayList<Rectangle>();
- rtree.search(s, tuple, searchOpCtx, results);
- totalResults += results.size();
- } catch (TreeIndexException e) {
- } catch (Exception e) {
- e.printStackTrace();
- }
-
- inputLine = reader2.readLine();
- index++;
-
- }
-
- System.out.println("Number of Results: " + totalResults);
-
- // String stats = rtree.printStats();
- // print(stats);
-
- RTreeOpContext deleteOpCtx = rtree.createOpContext(IndexOp.DELETE, leafFrame, interiorFrame, metaFrame);
-
- BufferedReader reader3 = new BufferedReader(new FileReader(datasetFile));
- inputLine = reader3.readLine();
- index = 0;
- rnd.setSeed(50);
- while (inputLine != null) {
-
- String[] splittedLine1 = inputLine.split(",");
- String[] splittedLine2 = splittedLine1[0].split("\\s");
-
- double p1x = 0;
- double p1y = 0;
-
- try {
- p1x = Double.valueOf(splittedLine2[1].trim()).doubleValue();
- p1y = Double.valueOf(splittedLine2[2].trim()).doubleValue();
- } catch (Exception e) {
- inputLine = reader3.readLine();
- continue;
- }
- double p2x = p1x;
- double p2y = p1y;
-
- int pk = rnd.nextInt();
-
- tb.reset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p1x, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p1y, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p2x, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p2y, dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
- tb.addFieldEndOffset();
-
- appender.reset(hyracksFrame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
-
- tuple.reset(accessor, 0);
-
- print("Deleteing " + index + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x)
- + " " + Math.max(p1y, p2y) + "\n");
-
- try {
- rtree.delete(tuple, deleteOpCtx);
- } catch (TreeIndexException e) {
- } catch (Exception e) {
- e.printStackTrace();
- }
-
- if (index == 1000) {
- break;
- }
- inputLine = reader3.readLine();
- index++;
-
- // rtree.printTree(leafFrame, interiorFrame, recDescSers);
- // System.out.println();
- }
-
- BufferedReader reader4 = new BufferedReader(new FileReader(querysetFile));
-
- inputLine = reader4.readLine();
- totalResults = 0;
- index = 0;
- Stack<Integer> s2 = new Stack<Integer>();
- while (inputLine != null) {
-
- String[] splittedLine1 = inputLine.split(",");
- String[] splittedLine2 = splittedLine1[0].split("\\s");
-
- double p1x = Double.valueOf(splittedLine2[1].trim()).doubleValue();
- double p1y = Double.valueOf(splittedLine2[2].trim()).doubleValue();
- double p2x = Double.valueOf(splittedLine2[3].trim()).doubleValue();
- double p2y = Double.valueOf(splittedLine2[4].trim()).doubleValue();
-
- int pk = rnd.nextInt();
-
- tb.reset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p1x, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p1y, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p2x, dos);
- tb.addFieldEndOffset();
- DoubleSerializerDeserializer.INSTANCE.serialize(p2y, dos);
- tb.addFieldEndOffset();
- IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
- tb.addFieldEndOffset();
-
- appender.reset(hyracksFrame, true);
- appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
-
- tuple.reset(accessor, 0);
-
- print("SEARCHING " + index + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x)
- + " " + Math.max(p1y, p2y) + "\n");
-
- try {
- ArrayList<Rectangle> results = new ArrayList<Rectangle>();
- rtree.search(s2, tuple, searchOpCtx, results);
- totalResults += results.size();
- } catch (TreeIndexException e) {
- } catch (Exception e) {
- e.printStackTrace();
- }
-
- inputLine = reader4.readLine();
- index++;
-
- }
-
- System.out.println("Number of Results: " + totalResults);
-
- // stats = rtree.printStats();
- // print(stats);
-
- rtree.printTree(leafFrame, interiorFrame, recDescSers);
- System.out.println();
+ TreeIndexStatsGatherer statsGatherer = new TreeIndexStatsGatherer(bufferCache, freePageManager, fileId,
+ rtree.getRootPageId());
+ TreeIndexStats stats = statsGatherer.gatherStats(leafFrame, interiorFrame, metaFrame);
+ String string = stats.toString();
+ System.out.println(string);
rtree.close();
bufferCache.closeFile(fileId);
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
index f750edc..f8d0383 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
@@ -37,9 +37,10 @@
import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
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.rtree.api.IRTreeFrame;
-import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMFrameFactory;
-import edu.uci.ics.hyracks.storage.am.rtree.impls.InteriorFrameSchema;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.NSMLeafFrameFactory;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
@@ -76,39 +77,35 @@
cmps[2] = cmps[0];
cmps[3] = cmps[0];
- // declare leaf-frame-tuple fields
- int leafFieldCount = 5;
- ITypeTrait[] leafTypeTraits = new ITypeTrait[leafFieldCount];
- leafTypeTraits[0] = new TypeTrait(8);
- leafTypeTraits[1] = new TypeTrait(8);
- leafTypeTraits[2] = new TypeTrait(8);
- leafTypeTraits[3] = new TypeTrait(8);
- leafTypeTraits[4] = new TypeTrait(4);
+ // declare tuple fields
+ int fieldCount = 5;
+ ITypeTrait[] typeTraits = new ITypeTrait[fieldCount];
+ typeTraits[0] = new TypeTrait(8);
+ typeTraits[1] = new TypeTrait(8);
+ typeTraits[2] = new TypeTrait(8);
+ typeTraits[3] = new TypeTrait(8);
+ typeTraits[4] = new TypeTrait(4);
- MultiComparator leafCmp = new MultiComparator(leafTypeTraits, cmps);
- InteriorFrameSchema interiorFrameSchema = new InteriorFrameSchema(leafCmp);
+ MultiComparator cmp = new MultiComparator(typeTraits, cmps);
- RTreeTypeAwareTupleWriterFactory interiorTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(
- interiorFrameSchema.getInteriorCmp().getTypeTraits());
- RTreeTypeAwareTupleWriterFactory leafTupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(leafTypeTraits);
+ RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
- ITreeIndexFrameFactory interiorFrameFactory = new NSMFrameFactory(interiorTupleWriterFactory, keyFieldCount);
- ITreeIndexFrameFactory leafFrameFactory = new NSMFrameFactory(leafTupleWriterFactory, keyFieldCount);
+ ITreeIndexFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(tupleWriterFactory, keyFieldCount);
+ ITreeIndexFrameFactory leafFrameFactory = new NSMLeafFrameFactory(tupleWriterFactory, keyFieldCount);
ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
- IRTreeFrame interiorFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
- IRTreeFrame leafFrame = (IRTreeFrame) leafFrameFactory.createFrame();
+ IRTreeInteriorFrame interiorFrame = (IRTreeInteriorFrame) interiorFrameFactory.createFrame();
+ IRTreeLeafFrame leafFrame = (IRTreeLeafFrame) leafFrameFactory.createFrame();
IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
- RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory,
- interiorFrameSchema.getInteriorCmp(), leafCmp);
+ RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, cmp);
rtree.create(fileId, leafFrame, metaFrame);
rtree.open(fileId);
ByteBuffer hyracksFrame = ctx.allocateFrame();
FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
- ArrayTupleBuilder tb = new ArrayTupleBuilder(leafCmp.getFieldCount());
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(cmp.getFieldCount());
DataOutput dos = tb.getDataOutput();
@SuppressWarnings("rawtypes")
@@ -163,8 +160,7 @@
}
ITreeIndexCursor searchCursor = new RTreeSearchCursor(interiorFrame, leafFrame);
- SearchPredicate searchPredicate = new SearchPredicate(tuple, interiorFrameSchema.getInteriorCmp(), leafCmp);
-
+ SearchPredicate searchPredicate = new SearchPredicate(tuple, cmp);
RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame);
rtree.search(searchCursor, searchPredicate, searchOpCtx);