Luo Chen has uploaded a new change for review.
https://asterix-gerrit.ics.uci.edu/2193
Change subject: [ASTERIXDB-2184] Add Immutable DiskBTree
......................................................................
[ASTERIXDB-2184] Add Immutable DiskBTree
- user model changes: no
- storage format changes: no
- interface changes: no
Details:
- Add a immutable DiskBTree to for LSM disk components. This DiskBTree
only supports two operations, i.e., search and bulkload. No concurrency
control is performed at all, since it's immutable.
- Change LSMBTree/InvertedIndex to use this DiskBTree
- Add a DiskBTree point search cursor to optimize point lookups
Change-Id: I8f2a9281478c4b8665589dc695769d0497af9961
---
M
hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/api/IBTreeFrame.java
M
hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
M
hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
M
hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
M
hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTree.java
M
hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
A
hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTree.java
A
hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreePointSearchCursor.java
A
hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreeRangeSearchCursor.java
M
hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/util/BTreeUtils.java
M
hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponent.java
M
hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponentFactory.java
M
hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java
M
hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBloomFilterDiskComponentFactory.java
M
hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/utils/LSMBTreeUtil.java
A
hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/DiskBTreeFactory.java
M
hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/OnDiskInvertedIndex.java
M
hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/org/apache/hyracks/storage/am/btree/BTreeSearchCursorTest.java
A
hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/org/apache/hyracks/storage/am/btree/DiskBTreeSearchCursorTest.java
M
hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/org/apache/hyracks/storage/am/lsm/btree/impl/TestLsmBtreeUtil.java
20 files changed, 1,134 insertions(+), 131 deletions(-)
git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb
refs/changes/93/2193/1
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/api/IBTreeFrame.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/api/IBTreeFrame.java
index 2383192..629a866 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/api/IBTreeFrame.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/api/IBTreeFrame.java
@@ -40,4 +40,8 @@
public boolean getLargeFlag();
public void validate(PageValidationInfo pvi) throws HyracksDataException;
+
+ public ITupleReference getLeftmostTuple() throws HyracksDataException;
+
+ public ITupleReference getRightmostTuple() throws HyracksDataException;
}
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
index 9624158..eb87c57 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
@@ -790,4 +790,14 @@
throw new IllegalStateException("nyi");
}
+ @Override
+ public ITupleReference getLeftmostTuple() throws HyracksDataException {
+ throw new UnsupportedOperationException("Not implemented");
+ }
+
+ @Override
+ public ITupleReference getRightmostTuple() throws HyracksDataException {
+ throw new UnsupportedOperationException("Not implemented");
+ }
+
}
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
index 8c67cfe..cc41393 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeNSMInteriorFrame.java
@@ -441,4 +441,26 @@
}
}
}
+
+ @Override
+ public ITupleReference getLeftmostTuple() {
+ int tupleCount = getTupleCount();
+ if (tupleCount == 0) {
+ return null;
+ } else {
+ frameTuple.resetByTupleIndex(this, 0);
+ return frameTuple;
+ }
+ }
+
+ @Override
+ public ITupleReference getRightmostTuple() {
+ int tupleCount = getTupleCount();
+ if (tupleCount == 0) {
+ return null;
+ } else {
+ frameTuple.resetByTupleIndex(this, tupleCount - 1);
+ return frameTuple;
+ }
+ }
}
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
index 09a4db4..2dc9f67 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
@@ -343,4 +343,26 @@
strBuilder.append("nextLeafOff: " + NEXT_LEAF_OFFSET + "\n");
return strBuilder.toString();
}
+
+ @Override
+ public ITupleReference getLeftmostTuple() {
+ int tupleCount = getTupleCount();
+ if (tupleCount == 0) {
+ return null;
+ } else {
+ frameTuple.resetByTupleIndex(this, 0);
+ return frameTuple;
+ }
+ }
+
+ @Override
+ public ITupleReference getRightmostTuple() {
+ int tupleCount = getTupleCount();
+ if (tupleCount == 0) {
+ return null;
+ } else {
+ frameTuple.resetByTupleIndex(this, tupleCount - 1);
+ return frameTuple;
+ }
+ }
}
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTree.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTree.java
index 63c54c3..26564e0 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTree.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTree.java
@@ -838,8 +838,8 @@
* for now, we are reusing it while it is an inner class !!!!
*/
public class BTreeAccessor implements ITreeIndexAccessor {
- private BTree btree;
- private BTreeOpContext ctx;
+ protected BTree btree;
+ protected BTreeOpContext ctx;
public BTreeAccessor(BTree btree, IModificationOperationCallback
modificationCalback,
ISearchOperationCallback searchCallback) {
@@ -896,6 +896,10 @@
return new BTreeRangeSearchCursor(leafFrame, exclusive);
}
+ public BTreeRangeSearchCursor createPointCursor(boolean exclusive) {
+ return createSearchCursor(exclusive);
+ }
+
@Override
public void search(IIndexCursor cursor, ISearchPredicate searchPred)
throws HyracksDataException {
ctx.setOperation(IndexOperation.SEARCH);
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
index 13cb57a..4dc72e5 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
@@ -40,37 +40,37 @@
public class BTreeRangeSearchCursor implements ITreeIndexCursor {
- private final IBTreeLeafFrame frame;
- private final ITreeIndexTupleReference frameTuple;
- private final boolean exclusiveLatchNodes;
- private boolean isPageDirty;
+ protected final IBTreeLeafFrame frame;
+ protected final ITreeIndexTupleReference frameTuple;
+ protected final boolean exclusiveLatchNodes;
+ protected boolean isPageDirty;
- private IBufferCache bufferCache = null;
- private int fileId = -1;
+ protected IBufferCache bufferCache = null;
+ protected int fileId = -1;
- private ICachedPage page = null;
- private int pageId = -1; // This is used by the LSMRTree flush operation
+ protected ICachedPage page = null;
+ protected int pageId = -1; // This is used by the LSMRTree flush operation
- private int tupleIndex = 0;
- private int stopTupleIndex;
+ protected int tupleIndex = 0;
+ protected int stopTupleIndex;
- private final RangePredicate reusablePredicate;
- private final ArrayTupleReference reconciliationTuple;
- private IIndexAccessor accessor;
- private ISearchOperationCallback searchCb;
- private MultiComparator originalKeyCmp;
- private ArrayTupleBuilder tupleBuilder;
+ protected final RangePredicate reusablePredicate;
+ protected final ArrayTupleReference reconciliationTuple;
+ protected IIndexAccessor accessor;
+ protected ISearchOperationCallback searchCb;
+ protected MultiComparator originalKeyCmp;
+ protected ArrayTupleBuilder tupleBuilder;
- private FindTupleMode lowKeyFtm;
- private FindTupleMode highKeyFtm;
- private FindTupleNoExactMatchPolicy lowKeyFtp;
- private FindTupleNoExactMatchPolicy highKeyFtp;
+ protected FindTupleMode lowKeyFtm;
+ protected FindTupleMode highKeyFtm;
+ protected FindTupleNoExactMatchPolicy lowKeyFtp;
+ protected FindTupleNoExactMatchPolicy highKeyFtp;
- private RangePredicate pred;
- private MultiComparator lowKeyCmp;
- private MultiComparator highKeyCmp;
+ protected RangePredicate pred;
+ protected MultiComparator lowKeyCmp;
+ protected MultiComparator highKeyCmp;
protected ITupleReference lowKey;
- private ITupleReference highKey;
+ protected ITupleReference highKey;
public BTreeRangeSearchCursor(IBTreeLeafFrame frame, boolean
exclusiveLatchNodes) {
this.frame = frame;
@@ -100,16 +100,6 @@
@Override
public ITupleReference getTuple() {
return frameTuple;
- }
-
- @Override
- public ITupleReference getFilterMinTuple() {
- return null;
- }
-
- @Override
- public ITupleReference getFilterMaxTuple() {
- return null;
}
public int getTupleOffset() {
@@ -210,7 +200,7 @@
tupleIndex++;
}
- private int getLowKeyIndex() throws HyracksDataException {
+ protected int getLowKeyIndex() throws HyracksDataException {
if (lowKey == null) {
return 0;
}
@@ -227,7 +217,7 @@
return index;
}
- private int getHighKeyIndex() throws HyracksDataException {
+ protected int getHighKeyIndex() throws HyracksDataException {
if (highKey == null) {
return frame.getTupleCount() - 1;
}
@@ -248,12 +238,7 @@
public void open(ICursorInitialState initialState, ISearchPredicate
searchPred) throws HyracksDataException {
// in case open is called multiple times without closing
if (page != null) {
- if (exclusiveLatchNodes) {
- page.releaseWriteLatch(isPageDirty);
- } else {
- page.releaseReadLatch();
- }
- bufferCache.unpin(page);
+ resetBeforeOpen();
}
accessor = ((BTreeCursorInitialState) initialState).getAccessor();
searchCb = initialState.getSearchOperationCallback();
@@ -291,6 +276,10 @@
stopTupleIndex = getHighKeyIndex();
}
+ protected void resetBeforeOpen() throws HyracksDataException {
+ close();
+ }
+
@Override
public void reset() throws HyracksDataException {
close();
@@ -310,4 +299,14 @@
public boolean isExclusiveLatchNodes() {
return exclusiveLatchNodes;
}
+
+ @Override
+ public ITupleReference getFilterMinTuple() {
+ return null;
+ }
+
+ @Override
+ public ITupleReference getFilterMaxTuple() {
+ return null;
+ }
}
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTree.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTree.java
new file mode 100644
index 0000000..7ae2964
--- /dev/null
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTree.java
@@ -0,0 +1,269 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.btree.impls;
+
+import org.apache.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.api.io.FileReference;
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+import org.apache.hyracks.storage.am.btree.api.IBTreeFrame;
+import org.apache.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import org.apache.hyracks.storage.am.common.api.IPageManager;
+import org.apache.hyracks.storage.am.common.api.ITreeIndexCursor;
+import org.apache.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import org.apache.hyracks.storage.am.common.impls.TreeIndexDiskOrderScanCursor;
+import org.apache.hyracks.storage.am.common.ophelpers.IndexOperation;
+import org.apache.hyracks.storage.common.IIndexAccessParameters;
+import org.apache.hyracks.storage.common.IIndexCursor;
+import org.apache.hyracks.storage.common.IModificationOperationCallback;
+import org.apache.hyracks.storage.common.ISearchOperationCallback;
+import org.apache.hyracks.storage.common.ISearchPredicate;
+import org.apache.hyracks.storage.common.MultiComparator;
+import org.apache.hyracks.storage.common.buffercache.IBufferCache;
+import org.apache.hyracks.storage.common.buffercache.ICachedPage;
+import org.apache.hyracks.storage.common.file.BufferedFileHandle;
+
+public class DiskBTree extends BTree {
+
+ public DiskBTree(IBufferCache bufferCache, IPageManager freePageManager,
+ ITreeIndexFrameFactory interiorFrameFactory,
ITreeIndexFrameFactory leafFrameFactory,
+ IBinaryComparatorFactory[] cmpFactories, int fieldCount,
FileReference file) {
+ super(bufferCache, freePageManager, interiorFrameFactory,
leafFrameFactory, cmpFactories, fieldCount, file);
+ }
+
+ private void diskOrderScan(ITreeIndexCursor icursor, BTreeOpContext ctx)
throws HyracksDataException {
+ TreeIndexDiskOrderScanCursor cursor = (TreeIndexDiskOrderScanCursor)
icursor;
+ ctx.reset();
+ RangePredicate diskOrderScanPred = new RangePredicate(null, null,
true, true, ctx.getCmp(), ctx.getCmp());
+ int maxPageId = freePageManager.getMaxPageId(ctx.getMetaFrame());
+ int currentPageId = bulkloadLeafStart;
+ ICachedPage page =
bufferCache.pin(BufferedFileHandle.getDiskPageId(getFileId(), currentPageId),
false);
+ try {
+ cursor.setBufferCache(bufferCache);
+ cursor.setFileId(getFileId());
+ cursor.setCurrentPageId(currentPageId);
+ cursor.setMaxPageId(maxPageId);
+ ctx.getCursorInitialState().setPage(page);
+
ctx.getCursorInitialState().setSearchOperationCallback(ctx.getSearchCallback());
+
ctx.getCursorInitialState().setOriginialKeyComparator(ctx.getCmp());
+ cursor.open(ctx.getCursorInitialState(), diskOrderScanPred);
+ } catch (Exception e) {
+ bufferCache.unpin(page);
+ throw HyracksDataException.create(e);
+ }
+ }
+
+ private void search(ITreeIndexCursor cursor, ISearchPredicate searchPred,
BTreeOpContext ctx)
+ throws HyracksDataException {
+ ctx.reset();
+ ctx.setPred((RangePredicate) searchPred);
+ ctx.setCursor(cursor);
+ // simple index scan
+ if (ctx.getPred().getLowKeyComparator() == null) {
+ ctx.getPred().setLowKeyComparator(ctx.getCmp());
+ }
+ if (ctx.getPred().getHighKeyComparator() == null) {
+ ctx.getPred().setHighKeyComparator(ctx.getCmp());
+ }
+ cursor.setBufferCache(bufferCache);
+ cursor.setFileId(getFileId());
+
+ DiskBTreeRangeSearchCursor diskCursor = (DiskBTreeRangeSearchCursor)
cursor;
+
+ if (diskCursor.numSearchPages() == 0) {
+ // we have to search from root to leaf
+ ICachedPage rootNode =
bufferCache.pin(BufferedFileHandle.getDiskPageId(getFileId(), rootPage), false);
+ diskCursor.addSearchPage(rootPage);
+ searchDown(rootNode, rootPage, ctx, diskCursor);
+ } else {
+ // we first check whether the leaf page matches because page may
be shifted during cursor.hasNext
+ if (ctx.getLeafFrame().getPage() != diskCursor.getPage()) {
+ ctx.getLeafFrame().setPage(diskCursor.getPage());
+ ctx.getCursorInitialState().setPage(diskCursor.getPage());
+ ctx.getCursorInitialState().setPageId(diskCursor.getPageId());
+ }
+
+ if (fitInPage(ctx.getPred().getLowKey(),
ctx.getPred().getLowKeyComparator(), ctx.getLeafFrame())) {
+ // the input still falls into the previous search leaf
+ diskCursor.open(ctx.getCursorInitialState(), searchPred);
+ } else {
+ // unpin the previous leaf page
+ bufferCache.unpin(ctx.getLeafFrame().getPage());
+ diskCursor.removeLastSearchPage();
+
+ ICachedPage page = searchUp(ctx, diskCursor);
+ int pageId = diskCursor.getLastSearchPage();
+
+ searchDown(page, pageId, ctx, diskCursor);
+ }
+ }
+ }
+
+ private ICachedPage searchUp(BTreeOpContext ctx,
DiskBTreeRangeSearchCursor cursor) throws HyracksDataException {
+ int index = cursor.numSearchPages() - 1;
+ // no need to check root page
+ for (; index >= 0; index--) {
+ int pageId = cursor.getLastSearchPage();
+ ICachedPage page =
bufferCache.pin(BufferedFileHandle.getDiskPageId(getFileId(), pageId), false);
+ ctx.getInteriorFrame().setPage(page);
+ if (index == 0 || fitInPage(ctx.getPred().getLowKey(),
ctx.getPred().getLowKeyComparator(),
+ ctx.getInteriorFrame())) {
+ // we've found the right page
+ return page;
+ } else {
+ // unpin the current page
+ bufferCache.unpin(page);
+ cursor.removeLastSearchPage();
+ }
+ }
+
+ // if no page is available (which is the case for single-level BTree)
+ // we simply return the root page
+ ICachedPage page =
bufferCache.pin(BufferedFileHandle.getDiskPageId(getFileId(), rootPage), false);
+ cursor.addSearchPage(rootPage);
+ return page;
+ }
+
+ private boolean fitInPage(ITupleReference key, MultiComparator comparator,
IBTreeFrame frame)
+ throws HyracksDataException {
+ ITupleReference rightmostTuple = frame.getRightmostTuple();
+ int cmp = comparator.compare(key, rightmostTuple);
+ if (cmp > 0) {
+ return false;
+ }
+ ITupleReference leftmostTuple = frame.getLeftmostTuple();
+ return comparator.compare(key, leftmostTuple) >= 0;
+ }
+
+ private void searchDown(ICachedPage page, int pageId, BTreeOpContext ctx,
DiskBTreeRangeSearchCursor cursor)
+ throws HyracksDataException {
+ ctx.getInteriorFrame().setPage(page);
+ try {
+ int childPageId = pageId;
+ while (!ctx.getInteriorFrame().isLeaf()) {
+ // walk down the tree until we find the leaf
+ childPageId =
ctx.getInteriorFrame().getChildPageId(ctx.getPred());
+
+ // save the child page tuple index
+ cursor.addSearchPage(childPageId);
+ bufferCache.unpin(page);
+ page =
bufferCache.pin(BufferedFileHandle.getDiskPageId(getFileId(), childPageId),
false);
+ ctx.getInteriorFrame().setPage(page);
+ }
+
+
ctx.getCursorInitialState().setSearchOperationCallback(ctx.getSearchCallback());
+
ctx.getCursorInitialState().setOriginialKeyComparator(ctx.getCmp());
+ ctx.getCursorInitialState().setPage(page);
+ ctx.getCursorInitialState().setPageId(childPageId);
+ ctx.getLeafFrame().setPage(page);
+ cursor.open(ctx.getCursorInitialState(), ctx.getPred());
+ } catch (HyracksDataException e) {
+ if (!ctx.isExceptionHandled()) {
+ if (page != null) {
+ bufferCache.unpin(page);
+ ctx.setExceptionHandled(true);
+ }
+ }
+ throw e;
+ } catch (Exception e) {
+ if (page != null) {
+ bufferCache.unpin(page);
+ }
+ HyracksDataException wrappedException =
HyracksDataException.create(e);
+ ctx.setExceptionHandled(true);
+ throw wrappedException;
+ }
+ }
+
+ @Override
+ public BTreeAccessor createAccessor(IIndexAccessParameters iap) {
+ return new DiskBTreeAccessor(this, iap.getModificationCallback(),
iap.getSearchOperationCallback());
+ }
+
+ @Override
+ public DiskBTreeAccessor createAccessor(IModificationOperationCallback
modificationCallback,
+ ISearchOperationCallback searchCallback, int[] logTupleFields) {
+ return new DiskBTreeAccessor(this, modificationCallback,
searchCallback, logTupleFields);
+ }
+
+ public class DiskBTreeAccessor extends BTreeAccessor {
+
+ public DiskBTreeAccessor(DiskBTree btree,
IModificationOperationCallback modificationCalback,
+ ISearchOperationCallback searchCallback) {
+ super(btree, modificationCalback, searchCallback);
+ }
+
+ public DiskBTreeAccessor(DiskBTree btree,
IModificationOperationCallback modificationCalback,
+ ISearchOperationCallback searchCallback, int[] logTupleFields)
{
+ super(btree, modificationCalback, searchCallback, logTupleFields);
+ }
+
+ @Override
+ public void insert(ITupleReference tuple) throws HyracksDataException {
+ throw new UnsupportedOperationException("Insert is not supported
by DiskBTree. ");
+ }
+
+ @Override
+ public void update(ITupleReference tuple) throws HyracksDataException {
+ throw new UnsupportedOperationException("Update is not supported
by DiskBTree. ");
+ }
+
+ @Override
+ public void delete(ITupleReference tuple) throws HyracksDataException {
+ throw new UnsupportedOperationException("Delete is not supported
by DiskBTree. ");
+ }
+
+ @Override
+ public void upsert(ITupleReference tuple) throws HyracksDataException {
+ throw new UnsupportedOperationException("Upsert is not supported
by DiskBTree. ");
+ }
+
+ @Override
+ public DiskBTreeRangeSearchCursor createSearchCursor(boolean
exclusive) {
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame)
btree.getLeafFrameFactory().createFrame();
+ return new DiskBTreeRangeSearchCursor(leafFrame, exclusive);
+ }
+
+ @Override
+ public BTreeRangeSearchCursor createPointCursor(boolean exclusive) {
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame)
btree.getLeafFrameFactory().createFrame();
+ return new DiskBTreePointSearchCursor(leafFrame, exclusive);
+ }
+
+ @Override
+ public void search(IIndexCursor cursor, ISearchPredicate searchPred)
throws HyracksDataException {
+ ctx.setOperation(IndexOperation.SEARCH);
+ ((DiskBTree) btree).search((ITreeIndexCursor) cursor, searchPred,
ctx);
+ }
+
+ @Override
+ public ITreeIndexCursor createDiskOrderScanCursor() {
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame)
btree.getLeafFrameFactory().createFrame();
+ return new TreeIndexDiskOrderScanCursor(leafFrame);
+ }
+
+ @Override
+ public void diskOrderScan(ITreeIndexCursor cursor) throws
HyracksDataException {
+ ctx.setOperation(IndexOperation.DISKORDERSCAN);
+ ((DiskBTree) btree).diskOrderScan(cursor, ctx);
+ }
+ }
+
+}
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreePointSearchCursor.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreePointSearchCursor.java
new file mode 100644
index 0000000..5839d0e
--- /dev/null
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreePointSearchCursor.java
@@ -0,0 +1,76 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.btree.impls;
+
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import org.apache.hyracks.storage.am.common.ophelpers.FindTupleMode;
+import
org.apache.hyracks.storage.am.common.ophelpers.FindTupleNoExactMatchPolicy;
+import org.apache.hyracks.storage.common.ICursorInitialState;
+import org.apache.hyracks.storage.common.ISearchPredicate;
+
+public class DiskBTreePointSearchCursor extends DiskBTreeRangeSearchCursor {
+
+ private boolean nextHasBeenCalled;
+
+ public DiskBTreePointSearchCursor(IBTreeLeafFrame frame, boolean
exclusiveLatchNodes) {
+ super(frame, exclusiveLatchNodes);
+ }
+
+ @Override
+ public boolean hasNext() throws HyracksDataException {
+ return tupleIndex >= 0 && !nextHasBeenCalled;
+ }
+
+ @Override
+ public void next() throws HyracksDataException {
+ nextHasBeenCalled = true;
+ }
+
+ @Override
+ public void open(ICursorInitialState initialState, ISearchPredicate
searchPred) throws HyracksDataException {
+ // in case open is called multiple times without closing
+ if (page != null) {
+ resetBeforeOpen();
+ }
+ accessor = ((BTreeCursorInitialState) initialState).getAccessor();
+ searchCb = initialState.getSearchOperationCallback();
+ originalKeyCmp = initialState.getOriginalKeyComparator();
+ pageId = ((BTreeCursorInitialState) initialState).getPageId();
+ page = initialState.getPage();
+ isPageDirty = false;
+ frame.setPage(page);
+
+ pred = (RangePredicate) searchPred;
+ lowKeyCmp = pred.getLowKeyComparator();
+ lowKey = pred.getLowKey();
+
+ reusablePredicate.setLowKeyComparator(originalKeyCmp);
+
+ lowKeyFtm = FindTupleMode.EXACT;
+ lowKeyFtp = FindTupleNoExactMatchPolicy.NONE;
+
+ nextHasBeenCalled = false;
+
+ // only get the low key position
+ tupleIndex = getLowKeyIndex();
+ }
+
+}
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreeRangeSearchCursor.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreeRangeSearchCursor.java
new file mode 100644
index 0000000..2e0afb4
--- /dev/null
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreeRangeSearchCursor.java
@@ -0,0 +1,113 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.btree.impls;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import org.apache.hyracks.storage.common.buffercache.ICachedPage;
+import org.apache.hyracks.storage.common.file.BufferedFileHandle;
+
+public class DiskBTreeRangeSearchCursor extends BTreeRangeSearchCursor {
+
+ // keep track of the pages (root -> leaf) we've searched
+ protected final List<Integer> searchPages = new ArrayList<>(5);
+
+ public DiskBTreeRangeSearchCursor(IBTreeLeafFrame frame, boolean
exclusiveLatchNodes) {
+ super(frame, exclusiveLatchNodes);
+ }
+
+ protected void fetchNextLeafPage(int nextLeafPage) throws
HyracksDataException {
+ do {
+ ICachedPage nextLeaf =
bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, nextLeafPage), false);
+ bufferCache.unpin(page);
+ page = nextLeaf;
+ frame.setPage(page);
+ pageId = nextLeafPage;
+ nextLeafPage = frame.getNextLeaf();
+ } while (frame.getTupleCount() == 0 && nextLeafPage > 0);
+ }
+
+ @Override
+ public boolean hasNext() throws HyracksDataException {
+ int nextLeafPage;
+ if (tupleIndex >= frame.getTupleCount()) {
+ nextLeafPage = frame.getNextLeaf();
+ if (nextLeafPage >= 0) {
+ fetchNextLeafPage(nextLeafPage);
+ tupleIndex = 0;
+ // update page ids and positions
+ searchPages.set(searchPages.size() - 1, nextLeafPage);
+ stopTupleIndex = getHighKeyIndex();
+ if (stopTupleIndex < 0) {
+ return false;
+ }
+ } else {
+ return false;
+ }
+ }
+ if (tupleIndex > stopTupleIndex) {
+ return false;
+ }
+
+ frameTuple.resetByTupleIndex(frame, tupleIndex);
+ return true;
+ }
+
+ @Override
+ protected void resetBeforeOpen() throws HyracksDataException {
+ // do nothing
+ // we allow a disk btree range cursor be stateful, that is, the next
search can be based on the previous search
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ if (page != null) {
+ bufferCache.unpin(page);
+ }
+ tupleIndex = 0;
+ page = null;
+ isPageDirty = false;
+ pred = null;
+ searchPages.clear();
+ }
+
+ public int numSearchPages() {
+ return searchPages.size();
+ }
+
+ public void addSearchPage(int page) {
+ searchPages.add(page);
+ }
+
+ public int getLastSearchPage() {
+ return searchPages.get(searchPages.size() - 1);
+ }
+
+ public int removeLastSearchPage() {
+ return searchPages.remove(searchPages.size() - 1);
+ }
+
+ public ICachedPage getPage() {
+ return page;
+ }
+}
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/util/BTreeUtils.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/util/BTreeUtils.java
index 7f992f9..0c06bc3 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/util/BTreeUtils.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/util/BTreeUtils.java
@@ -29,6 +29,7 @@
import org.apache.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
import org.apache.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
import org.apache.hyracks.storage.am.btree.impls.BTree;
+import org.apache.hyracks.storage.am.btree.impls.DiskBTree;
import
org.apache.hyracks.storage.am.btree.tuples.BTreeTypeAwareTupleWriterFactory;
import org.apache.hyracks.storage.am.common.api.IPageManager;
import org.apache.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
@@ -51,6 +52,17 @@
typeTraits.length, file);
}
+ public static DiskBTree createDiskBTree(IBufferCache bufferCache,
ITypeTraits[] typeTraits,
+ IBinaryComparatorFactory[] cmpFactories, BTreeLeafFrameType
leafType, FileReference file,
+ IPageManager freePageManager, boolean updateAware) throws
HyracksDataException {
+ BTreeTypeAwareTupleWriterFactory tupleWriterFactory =
+ new BTreeTypeAwareTupleWriterFactory(typeTraits, updateAware);
+ ITreeIndexFrameFactory leafFrameFactory =
getLeafFrameFactory(tupleWriterFactory, leafType);
+ ITreeIndexFrameFactory interiorFrameFactory = new
BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+ return new DiskBTree(bufferCache, freePageManager,
interiorFrameFactory, leafFrameFactory, cmpFactories,
+ typeTraits.length, file);
+ }
+
public static BTree createBTree(IBufferCache bufferCache, IPageManager
freePageManager, ITypeTraits[] typeTraits,
IBinaryComparatorFactory[] cmpFactories, BTreeLeafFrameType
leafType, FileReference file,
boolean updateAware) throws HyracksDataException {
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponent.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponent.java
index d759167..0fc79eb 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponent.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponent.java
@@ -22,26 +22,27 @@
import java.util.Set;
import org.apache.hyracks.storage.am.btree.impls.BTree;
+import org.apache.hyracks.storage.am.btree.impls.DiskBTree;
import org.apache.hyracks.storage.am.common.api.IMetadataPageManager;
import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponentFilter;
import org.apache.hyracks.storage.am.lsm.common.impls.AbstractLSMDiskComponent;
import org.apache.hyracks.storage.am.lsm.common.impls.AbstractLSMIndex;
public class LSMBTreeDiskComponent extends AbstractLSMDiskComponent {
- protected final BTree btree;
+ protected final DiskBTree btree;
- public LSMBTreeDiskComponent(AbstractLSMIndex lsmIndex, BTree btree,
ILSMComponentFilter filter) {
+ public LSMBTreeDiskComponent(AbstractLSMIndex lsmIndex, DiskBTree btree,
ILSMComponentFilter filter) {
super(lsmIndex, getMetadataPageManager(btree), filter);
this.btree = btree;
}
@Override
- public BTree getIndex() {
+ public DiskBTree getIndex() {
return btree;
}
@Override
- public BTree getMetadataHolder() {
+ public DiskBTree getMetadataHolder() {
return btree;
}
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponentFactory.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponentFactory.java
index 0e54f53..3b332cd 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponentFactory.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponentFactory.java
@@ -20,7 +20,7 @@
package org.apache.hyracks.storage.am.lsm.btree.impls;
import org.apache.hyracks.api.exceptions.HyracksDataException;
-import org.apache.hyracks.storage.am.btree.impls.BTree;
+import org.apache.hyracks.storage.am.btree.impls.DiskBTree;
import org.apache.hyracks.storage.am.lsm.common.api.IComponentFilterHelper;
import org.apache.hyracks.storage.am.lsm.common.api.ILSMDiskComponentFactory;
import org.apache.hyracks.storage.am.lsm.common.impls.AbstractLSMIndex;
@@ -28,10 +28,10 @@
import org.apache.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
public class LSMBTreeDiskComponentFactory implements ILSMDiskComponentFactory {
- protected final TreeIndexFactory<BTree> btreeFactory;
+ protected final TreeIndexFactory<DiskBTree> btreeFactory;
protected final IComponentFilterHelper filterHelper;
- public LSMBTreeDiskComponentFactory(TreeIndexFactory<BTree> btreeFactory,
IComponentFilterHelper filterHelper) {
+ public LSMBTreeDiskComponentFactory(TreeIndexFactory<DiskBTree>
btreeFactory, IComponentFilterHelper filterHelper) {
this.btreeFactory = btreeFactory;
this.filterHelper = filterHelper;
}
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java
index b84a172..fb5951a 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java
@@ -24,10 +24,8 @@
import org.apache.hyracks.api.exceptions.HyracksDataException;
import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
import org.apache.hyracks.storage.am.bloomfilter.impls.BloomFilter;
-import org.apache.hyracks.storage.am.btree.api.IBTreeLeafFrame;
import org.apache.hyracks.storage.am.btree.impls.BTree;
import org.apache.hyracks.storage.am.btree.impls.BTree.BTreeAccessor;
-import org.apache.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
import org.apache.hyracks.storage.am.btree.impls.RangePredicate;
import org.apache.hyracks.storage.am.common.api.ITreeIndexCursor;
import org.apache.hyracks.storage.am.common.impls.NoOpIndexAccessParameters;
@@ -45,7 +43,7 @@
public class LSMBTreePointSearchCursor implements ITreeIndexCursor {
- private BTreeRangeSearchCursor[] rangeCursors;
+ private ITreeIndexCursor[] btreeCursors;
private final ILSMIndexOperationContext opCtx;
private ISearchOperationCallback searchCallback;
private RangePredicate predicate;
@@ -78,21 +76,21 @@
if (bloomFilters[i] != null &&
!bloomFilters[i].contains(predicate.getLowKey(), hashes)) {
continue;
}
- btreeAccessors[i].search(rangeCursors[i], predicate);
- if (rangeCursors[i].hasNext()) {
- rangeCursors[i].next();
+ btreeAccessors[i].search(btreeCursors[i], predicate);
+ if (btreeCursors[i].hasNext()) {
+ btreeCursors[i].next();
// We use the predicate's to lock the key instead of the tuple
that we get from cursor
// to avoid copying the tuple when we do the "unlatch dance".
if (reconciled ||
searchCallback.proceed(predicate.getLowKey())) {
// if proceed is successful, then there's no need for
doing the "unlatch dance"
- if (((ILSMTreeTupleReference)
rangeCursors[i].getTuple()).isAntimatter()) {
+ if (((ILSMTreeTupleReference)
btreeCursors[i].getTuple()).isAntimatter()) {
if (reconciled) {
searchCallback.cancel(predicate.getLowKey());
}
- rangeCursors[i].close();
+ btreeCursors[i].close();
return false;
} else {
- frameTuple = rangeCursors[i].getTuple();
+ frameTuple = btreeCursors[i].getTuple();
foundTuple = true;
foundIn = i;
return true;
@@ -100,20 +98,20 @@
}
if (i == 0 && includeMutableComponent) {
// unlatch/unpin
- rangeCursors[i].reset();
+ btreeCursors[i].reset();
searchCallback.reconcile(predicate.getLowKey());
reconciled = true;
// retraverse
- btreeAccessors[0].search(rangeCursors[i], predicate);
- if (rangeCursors[i].hasNext()) {
- rangeCursors[i].next();
- if (((ILSMTreeTupleReference)
rangeCursors[i].getTuple()).isAntimatter()) {
+ btreeAccessors[0].search(btreeCursors[i], predicate);
+ if (btreeCursors[i].hasNext()) {
+ btreeCursors[i].next();
+ if (((ILSMTreeTupleReference)
btreeCursors[i].getTuple()).isAntimatter()) {
searchCallback.cancel(predicate.getLowKey());
- rangeCursors[i].close();
+ btreeCursors[i].close();
return false;
} else {
- frameTuple = rangeCursors[i].getTuple();
+ frameTuple = btreeCursors[i].getTuple();
foundTuple = true;
searchCallback.complete(predicate.getLowKey());
foundIn = i;
@@ -121,10 +119,10 @@
}
} else {
searchCallback.cancel(predicate.getLowKey());
- rangeCursors[i].close();
+ btreeCursors[i].close();
}
} else {
- frameTuple = rangeCursors[i].getTuple();
+ frameTuple = btreeCursors[i].getTuple();
searchCallback.reconcile(frameTuple);
searchCallback.complete(frameTuple);
foundTuple = true;
@@ -132,7 +130,7 @@
return true;
}
} else {
- rangeCursors[i].close();
+ btreeCursors[i].close();
}
}
return false;
@@ -141,9 +139,9 @@
@Override
public void reset() throws HyracksDataException {
try {
- if (rangeCursors != null) {
- for (int i = 0; i < rangeCursors.length; ++i) {
- rangeCursors[i].reset();
+ if (btreeCursors != null) {
+ for (int i = 0; i < numBTrees; ++i) {
+ btreeCursors[i].reset();
}
}
nextHasBeenCalled = false;
@@ -163,9 +161,9 @@
searchCallback = lsmInitialState.getSearchOperationCallback();
predicate = (RangePredicate) lsmInitialState.getSearchPredicate();
numBTrees = operationalComponents.size();
- if (rangeCursors == null || rangeCursors.length != numBTrees) {
+ if (btreeCursors == null || btreeCursors.length != numBTrees) {
// object creation: should be relatively low
- rangeCursors = new BTreeRangeSearchCursor[numBTrees];
+ btreeCursors = new ITreeIndexCursor[numBTrees];
btreeAccessors = new BTreeAccessor[numBTrees];
bloomFilters = new BloomFilter[numBTrees];
}
@@ -173,37 +171,22 @@
for (int i = 0; i < numBTrees; i++) {
ILSMComponent component = operationalComponents.get(i);
- BTree btree;
+ BTree btree = (BTree) component.getIndex();
if (component.getType() == LSMComponentType.MEMORY) {
includeMutableComponent = true;
- if (rangeCursors[i] == null) {
- // create a new one
- IBTreeLeafFrame leafFrame = (IBTreeLeafFrame)
lsmInitialState.getLeafFrameFactory().createFrame();
- rangeCursors[i] = new BTreeRangeSearchCursor(leafFrame,
false);
- } else {
- // reset
- rangeCursors[i].reset();
- }
- btree = ((LSMBTreeMemoryComponent) component).getIndex();
// no bloom filter for in-memory BTree
bloomFilters[i] = null;
} else {
- if (rangeCursors[i] != null) {
- // can re-use cursor
- rangeCursors[i].reset();
- } else {
- // create new cursor <should be relatively rare>
- IBTreeLeafFrame leafFrame = (IBTreeLeafFrame)
lsmInitialState.getLeafFrameFactory().createFrame();
- rangeCursors[i] = new BTreeRangeSearchCursor(leafFrame,
false);
- }
- btree = ((LSMBTreeWithBloomFilterDiskComponent)
component).getIndex();
bloomFilters[i] = ((LSMBTreeWithBloomFilterDiskComponent)
component).getBloomFilter();
}
+
if (btreeAccessors[i] == null) {
btreeAccessors[i] =
btree.createAccessor(NoOpIndexAccessParameters.INSTANCE);
+ btreeCursors[i] = btreeAccessors[i].createPointCursor(false);
} else {
// re-use
btreeAccessors[i].reset(btree, NoOpOperationCallback.INSTANCE,
NoOpOperationCallback.INSTANCE);
+ btreeCursors[i].reset();
}
}
nextHasBeenCalled = false;
@@ -220,7 +203,7 @@
if (lsmHarness != null) {
try {
closeCursors();
- rangeCursors = null;
+ btreeCursors = null;
} finally {
lsmHarness.endSearch(opCtx);
}
@@ -269,10 +252,10 @@
}
private void closeCursors() throws HyracksDataException {
- if (rangeCursors != null) {
- for (int i = 0; i < rangeCursors.length; ++i) {
- if (rangeCursors[i] != null) {
- rangeCursors[i].close();
+ if (btreeCursors != null) {
+ for (int i = 0; i < btreeCursors.length; ++i) {
+ if (btreeCursors[i] != null) {
+ btreeCursors[i].close();
}
}
}
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBloomFilterDiskComponentFactory.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBloomFilterDiskComponentFactory.java
index 09e83cc..eaf9cd5 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBloomFilterDiskComponentFactory.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBloomFilterDiskComponentFactory.java
@@ -20,7 +20,7 @@
import org.apache.hyracks.api.exceptions.HyracksDataException;
import org.apache.hyracks.storage.am.bloomfilter.impls.BloomFilterFactory;
-import org.apache.hyracks.storage.am.btree.impls.BTree;
+import org.apache.hyracks.storage.am.btree.impls.DiskBTree;
import org.apache.hyracks.storage.am.lsm.common.api.IComponentFilterHelper;
import org.apache.hyracks.storage.am.lsm.common.api.ILSMDiskComponentFactory;
import org.apache.hyracks.storage.am.lsm.common.impls.AbstractLSMIndex;
@@ -28,11 +28,11 @@
import org.apache.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
public class LSMBTreeWithBloomFilterDiskComponentFactory implements
ILSMDiskComponentFactory {
- protected final TreeIndexFactory<BTree> btreeFactory;
+ protected final TreeIndexFactory<DiskBTree> btreeFactory;
protected final IComponentFilterHelper filterHelper;
protected final BloomFilterFactory bloomFilterFactory;
- public LSMBTreeWithBloomFilterDiskComponentFactory(TreeIndexFactory<BTree>
btreeFactory,
+ public
LSMBTreeWithBloomFilterDiskComponentFactory(TreeIndexFactory<DiskBTree>
btreeFactory,
BloomFilterFactory bloomFilterFactory, IComponentFilterHelper
filterHelper) {
this.btreeFactory = btreeFactory;
this.filterHelper = filterHelper;
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/utils/LSMBTreeUtil.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/utils/LSMBTreeUtil.java
index 08e5af0..4706faa 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/utils/LSMBTreeUtil.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/utils/LSMBTreeUtil.java
@@ -30,6 +30,7 @@
import org.apache.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
import org.apache.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
import org.apache.hyracks.storage.am.btree.impls.BTree;
+import org.apache.hyracks.storage.am.btree.impls.DiskBTree;
import
org.apache.hyracks.storage.am.btree.tuples.BTreeTypeAwareTupleWriterFactory;
import org.apache.hyracks.storage.am.common.api.IMetadataPageManagerFactory;
import org.apache.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
@@ -54,6 +55,7 @@
import
org.apache.hyracks.storage.am.lsm.common.frames.LSMComponentFilterFrameFactory;
import org.apache.hyracks.storage.am.lsm.common.impls.BTreeFactory;
import org.apache.hyracks.storage.am.lsm.common.impls.ComponentFilterHelper;
+import org.apache.hyracks.storage.am.lsm.common.impls.DiskBTreeFactory;
import
org.apache.hyracks.storage.am.lsm.common.impls.LSMComponentFilterManager;
import org.apache.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
import org.apache.hyracks.storage.common.buffercache.IBufferCache;
@@ -87,10 +89,11 @@
ITreeIndexFrameFactory interiorFrameFactory = new
BTreeNSMInteriorFrameFactory(insertTupleWriterFactory);
ITreeIndexFrameFactory bulkLoadLeafFrameFactory = new
BTreeNSMLeafFrameFactory(bulkLoadTupleWriterFactory);
- TreeIndexFactory<BTree> diskBTreeFactory = new BTreeFactory(ioManager,
diskBufferCache, freePageManagerFactory,
- interiorFrameFactory, copyTupleLeafFrameFactory, cmpFactories,
typeTraits.length);
- TreeIndexFactory<BTree> bulkLoadBTreeFactory =
- new BTreeFactory(ioManager, diskBufferCache,
freePageManagerFactory, interiorFrameFactory,
+ TreeIndexFactory<DiskBTree> diskBTreeFactory =
+ new DiskBTreeFactory(ioManager, diskBufferCache,
freePageManagerFactory, interiorFrameFactory,
+ copyTupleLeafFrameFactory, cmpFactories,
typeTraits.length);
+ TreeIndexFactory<DiskBTree> bulkLoadBTreeFactory =
+ new DiskBTreeFactory(ioManager, diskBufferCache,
freePageManagerFactory, interiorFrameFactory,
bulkLoadLeafFrameFactory, cmpFactories,
typeTraits.length);
ComponentFilterHelper filterHelper = null;
@@ -151,16 +154,17 @@
ITreeIndexFrameFactory transactionLeafFrameFactory =
new BTreeNSMLeafFrameFactory(transactionTupleWriterFactory);
- TreeIndexFactory<BTree> diskBTreeFactory = new BTreeFactory(ioManager,
diskBufferCache, freePageManagerFactory,
- interiorFrameFactory, copyTupleLeafFrameFactory, cmpFactories,
typeTraits.length);
- TreeIndexFactory<BTree> bulkLoadBTreeFactory = new
BTreeFactory(ioManager, diskBufferCache,
+ TreeIndexFactory<DiskBTree> diskBTreeFactory =
+ new DiskBTreeFactory(ioManager, diskBufferCache,
freePageManagerFactory, interiorFrameFactory,
+ copyTupleLeafFrameFactory, cmpFactories,
typeTraits.length);
+ TreeIndexFactory<DiskBTree> bulkLoadBTreeFactory = new
DiskBTreeFactory(ioManager, diskBufferCache,
freePageManagerFactory, interiorFrameFactory,
insertLeafFrameFactory, cmpFactories, typeTraits.length);
BloomFilterFactory bloomFilterFactory = new
BloomFilterFactory(diskBufferCache, bloomFilterKeyFields);
// This is the component factory for transactions
- TreeIndexFactory<BTree> transactionBTreeFactory =
- new BTreeFactory(ioManager, diskBufferCache,
freePageManagerFactory, interiorFrameFactory,
+ TreeIndexFactory<DiskBTree> transactionBTreeFactory =
+ new DiskBTreeFactory(ioManager, diskBufferCache,
freePageManagerFactory, interiorFrameFactory,
transactionLeafFrameFactory, cmpFactories,
typeTraits.length);
//TODO remove BloomFilter from external dataset's secondary LSMBTree
index
ILSMIndexFileManager fileNameManager = new
LSMBTreeFileManager(ioManager, file, diskBTreeFactory, true);
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/DiskBTreeFactory.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/DiskBTreeFactory.java
new file mode 100644
index 0000000..ba863ac
--- /dev/null
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/DiskBTreeFactory.java
@@ -0,0 +1,45 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.lsm.common.impls;
+
+import org.apache.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import org.apache.hyracks.api.io.FileReference;
+import org.apache.hyracks.api.io.IIOManager;
+import org.apache.hyracks.storage.am.btree.impls.DiskBTree;
+import org.apache.hyracks.storage.am.common.api.IPageManagerFactory;
+import org.apache.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import org.apache.hyracks.storage.common.buffercache.IBufferCache;
+
+public class DiskBTreeFactory extends TreeIndexFactory<DiskBTree> {
+
+ public DiskBTreeFactory(IIOManager ioManager, IBufferCache bufferCache,
IPageManagerFactory freePageManagerFactory,
+ ITreeIndexFrameFactory interiorFrameFactory,
ITreeIndexFrameFactory leafFrameFactory,
+ IBinaryComparatorFactory[] cmpFactories, int fieldCount) {
+ super(ioManager, bufferCache, freePageManagerFactory,
interiorFrameFactory, leafFrameFactory, cmpFactories,
+ fieldCount);
+ }
+
+ @Override
+ public DiskBTree createIndexInstance(FileReference file) {
+ return new DiskBTree(bufferCache,
freePageManagerFactory.createPageManager(bufferCache), interiorFrameFactory,
+ leafFrameFactory, cmpFactories, fieldCount, file);
+ }
+
+}
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/OnDiskInvertedIndex.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/OnDiskInvertedIndex.java
index 5301fa1..df60104 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/OnDiskInvertedIndex.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/OnDiskInvertedIndex.java
@@ -37,6 +37,7 @@
import org.apache.hyracks.dataflow.common.utils.TupleUtils;
import org.apache.hyracks.storage.am.btree.frames.BTreeLeafFrameType;
import org.apache.hyracks.storage.am.btree.impls.BTree;
+import org.apache.hyracks.storage.am.btree.impls.DiskBTree;
import org.apache.hyracks.storage.am.btree.impls.RangePredicate;
import org.apache.hyracks.storage.am.btree.util.BTreeUtils;
import org.apache.hyracks.storage.am.common.api.IIndexOperationContext;
@@ -90,7 +91,7 @@
btreeValueTypeTraits[3] = IntegerPointable.TYPE_TRAITS;
}
- protected BTree btree;
+ protected DiskBTree btree;
protected int rootPageId = 0;
protected IBufferCache bufferCache;
protected int fileId = -1;
@@ -117,7 +118,7 @@
this.invListCmpFactories = invListCmpFactories;
this.tokenTypeTraits = tokenTypeTraits;
this.tokenCmpFactories = tokenCmpFactories;
- this.btree = BTreeUtils.createBTree(bufferCache,
getBTreeTypeTraits(tokenTypeTraits), tokenCmpFactories,
+ this.btree = BTreeUtils.createDiskBTree(bufferCache,
getBTreeTypeTraits(tokenTypeTraits), tokenCmpFactories,
BTreeLeafFrameType.REGULAR_NSM, btreeFile,
pageManagerFactory.createPageManager(bufferCache), false);
this.numTokenFields = btree.getComparatorFactories().length;
this.numInvListKeys = invListCmpFactories.length;
@@ -240,7 +241,7 @@
private final boolean verifyInput;
private final MultiComparator allCmp;
- private IFIFOPageQueue queue;
+ private final IFIFOPageQueue queue;
public OnDiskInvertedIndexBulkLoader(float btreeFillFactor, boolean
verifyInput, long numElementsHint,
boolean checkIfEmptyIndex, int startPageId) throws
HyracksDataException {
diff --git
a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/org/apache/hyracks/storage/am/btree/BTreeSearchCursorTest.java
b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/org/apache/hyracks/storage/am/btree/BTreeSearchCursorTest.java
index 0a714cf..dfcba2d 100644
---
a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/org/apache/hyracks/storage/am/btree/BTreeSearchCursorTest.java
+++
b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/org/apache/hyracks/storage/am/btree/BTreeSearchCursorTest.java
@@ -44,19 +44,19 @@
import org.apache.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
import org.apache.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
import org.apache.hyracks.storage.am.btree.impls.BTree;
-import org.apache.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
import org.apache.hyracks.storage.am.btree.impls.RangePredicate;
import
org.apache.hyracks.storage.am.btree.tuples.BTreeTypeAwareTupleWriterFactory;
import org.apache.hyracks.storage.am.btree.util.AbstractBTreeTest;
import org.apache.hyracks.storage.am.common.TestOperationCallback;
import org.apache.hyracks.storage.am.common.api.IMetadataPageManager;
import org.apache.hyracks.storage.am.common.api.ITreeIndexAccessor;
-import org.apache.hyracks.storage.am.common.api.ITreeIndexCursor;
import org.apache.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
import org.apache.hyracks.storage.am.common.api.ITreeIndexMetadataFrameFactory;
import org.apache.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
import org.apache.hyracks.storage.am.common.freepage.LinkedMetaDataPageManager;
import org.apache.hyracks.storage.am.common.impls.IndexAccessParameters;
+import org.apache.hyracks.storage.common.IIndexBulkLoader;
+import org.apache.hyracks.storage.common.IIndexCursor;
import org.apache.hyracks.storage.common.MultiComparator;
import org.apache.hyracks.storage.common.buffercache.IBufferCache;
import org.junit.Assert;
@@ -64,12 +64,12 @@
import org.junit.Test;
public class BTreeSearchCursorTest extends AbstractBTreeTest {
- private final int fieldCount = 2;
- private final ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
- private final BTreeTypeAwareTupleWriterFactory tupleWriterFactory =
+ protected final int fieldCount = 2;
+ protected final ITypeTraits[] typeTraits = new ITypeTraits[fieldCount];
+ protected final BTreeTypeAwareTupleWriterFactory tupleWriterFactory =
new BTreeTypeAwareTupleWriterFactory(typeTraits, false);
- private final ITreeIndexMetadataFrameFactory metaFrameFactory = new
LIFOMetaDataFrameFactory();
- private final Random rnd = new Random(50);
+ protected final ITreeIndexMetadataFrameFactory metaFrameFactory = new
LIFOMetaDataFrameFactory();
+ protected final Random rnd = new Random(50);
@Override
@Before
@@ -104,7 +104,7 @@
fieldCount, harness.getFileReference());
btree.create();
btree.activate();
-
+ IIndexBulkLoader bulkloader = btree.createBulkLoader(1.0f, true, 0,
true);
ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
ArrayTupleReference tuple = new ArrayTupleReference();
@@ -132,11 +132,12 @@
tuple.reset(tupleBuilder.getFieldEndOffsets(),
tupleBuilder.getByteArray());
try {
- indexAccessor.insert(tuple);
+ bulkloader.add(tuple);
} catch (Exception e) {
e.printStackTrace();
}
}
+ bulkloader.end();
int minSearchKey = -100;
int maxSearchKey = 100;
@@ -305,7 +306,6 @@
public RangePredicate createRangePredicate(int lk, int hk, boolean
lowKeyInclusive, boolean highKeyInclusive)
throws HyracksDataException {
-
// create tuplereferences for search keys
ITupleReference lowKey = TupleUtils.createIntegerTuple(false, lk);
ITupleReference highKey = TupleUtils.createIntegerTuple(false, hk);
@@ -352,18 +352,17 @@
for (int i = minKey; i < maxKey; i++) {
for (int j = minKey; j < maxKey; j++) {
-
results.clear();
expectedResults.clear();
int lowKey = i;
int highKey = j;
- ITreeIndexCursor rangeCursor = new
BTreeRangeSearchCursor(leafFrame, false);
RangePredicate rangePred = createRangePredicate(lowKey,
highKey, lowKeyInclusive, highKeyInclusive);
IndexAccessParameters actx =
new
IndexAccessParameters(TestOperationCallback.INSTANCE,
TestOperationCallback.INSTANCE);
ITreeIndexAccessor indexAccessor = btree.createAccessor(actx);
+ IIndexCursor rangeCursor =
indexAccessor.createSearchCursor(false);
indexAccessor.search(rangeCursor, rangePred);
try {
diff --git
a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/org/apache/hyracks/storage/am/btree/DiskBTreeSearchCursorTest.java
b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/org/apache/hyracks/storage/am/btree/DiskBTreeSearchCursorTest.java
new file mode 100644
index 0000000..abe6ed4
--- /dev/null
+++
b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/org/apache/hyracks/storage/am/btree/DiskBTreeSearchCursorTest.java
@@ -0,0 +1,438 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hyracks.storage.am.btree;
+
+import java.io.ByteArrayInputStream;
+import java.io.DataInput;
+import java.io.DataInputStream;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.TreeSet;
+import java.util.logging.Level;
+
+import org.apache.hyracks.api.dataflow.value.IBinaryComparatorFactory;
+import org.apache.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import org.apache.hyracks.data.std.primitive.IntegerPointable;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleReference;
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+import
org.apache.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import org.apache.hyracks.dataflow.common.utils.TupleUtils;
+import org.apache.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
+import org.apache.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import org.apache.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
+import org.apache.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
+import org.apache.hyracks.storage.am.btree.impls.BTree;
+import org.apache.hyracks.storage.am.btree.impls.BTree.BTreeAccessor;
+import org.apache.hyracks.storage.am.btree.impls.DiskBTree;
+import org.apache.hyracks.storage.am.btree.impls.RangePredicate;
+import org.apache.hyracks.storage.am.common.TestOperationCallback;
+import org.apache.hyracks.storage.am.common.api.IMetadataPageManager;
+import org.apache.hyracks.storage.am.common.api.ITreeIndexAccessor;
+import org.apache.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import org.apache.hyracks.storage.am.common.freepage.LinkedMetaDataPageManager;
+import org.apache.hyracks.storage.am.common.impls.IndexAccessParameters;
+import org.apache.hyracks.storage.common.IIndexBulkLoader;
+import org.apache.hyracks.storage.common.IIndexCursor;
+import org.apache.hyracks.storage.common.buffercache.IBufferCache;
+import org.junit.Assert;
+import org.junit.FixMethodOrder;
+import org.junit.Test;
+import org.junit.runners.MethodSorters;
+
+@FixMethodOrder(MethodSorters.NAME_ASCENDING)
+public class DiskBTreeSearchCursorTest extends BTreeSearchCursorTest {
+
+ @Test
+ public void batchPointLookupSingleLevelTest() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("TESTING POINT LOOKUP CURSOR ON UNIQUE 1 LEVEL INDEX");
+ }
+ // only 4 keys
+ batchPointLookupTest(4, 4, -8, 8);
+ }
+
+ @Test
+ public void batchPointLookupMultiLevelTest() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("TESTING POINT LOOKUP CURSOR ON UNIQUE MULTI-LEVEL
INDEX");
+ }
+ // only 10000 keys
+ batchPointLookupTest(10000, 20000, -1000, 1000);
+ }
+
+ @Test
+ public void batchPointLookupMultiLevelOutRangeTest() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("TESTING POINT LOOKUP CURSOR ON UNIQUE 1 LEVEL INDEX");
+ }
+ // only 100 keys
+ batchPointLookupTest(100, 200, -1000, 1000);
+ }
+
+ private void batchPointLookupTest(int numKeys, int maxKey, int
minSearchKey, int maxSearchKey) throws Exception {
+
+ IBufferCache bufferCache = harness.getBufferCache();
+
+ // declare keys
+ int keyFieldCount = 1;
+ IBinaryComparatorFactory[] cmpFactories = new
IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] =
PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ ITreeIndexFrameFactory leafFrameFactory = new
BTreeNSMLeafFrameFactory(tupleWriterFactory);
+ ITreeIndexFrameFactory interiorFrameFactory = new
BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame)
leafFrameFactory.createFrame();
+ IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame)
interiorFrameFactory.createFrame();
+
+ IMetadataPageManager freePageManager = new
LinkedMetaDataPageManager(bufferCache, metaFrameFactory);
+
+ DiskBTree btree = new DiskBTree(bufferCache, freePageManager,
interiorFrameFactory, leafFrameFactory,
+ cmpFactories, fieldCount, harness.getFileReference());
+ btree.create();
+ btree.activate();
+
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+
+ IIndexBulkLoader bulkloader = btree.createBulkLoader(1, true, 0, true);
+
+ TreeSet<Integer> uniqueKeys = new TreeSet<>();
+ ArrayList<Integer> keys = new ArrayList<>();
+ while (uniqueKeys.size() < numKeys) {
+ int key = rnd.nextInt() % maxKey;
+ uniqueKeys.add(key);
+ }
+ for (Integer i : uniqueKeys) {
+ keys.add(i);
+ }
+
+ // insert keys into btree
+ for (int i = 0; i < keys.size(); i++) {
+
+ TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+ tuple.reset(tupleBuilder.getFieldEndOffsets(),
tupleBuilder.getByteArray());
+
+ try {
+ bulkloader.add(tuple);
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ bulkloader.end();
+
+ // forward searches
+ Assert.assertTrue(performBatchLookups(keys, btree, leafFrame,
interiorFrame, minSearchKey, maxSearchKey));
+
+ btree.deactivate();
+ btree.destroy();
+ }
+
+ @Override
+ @Test
+ public void uniqueIndexTest() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("TESTING RANGE SEARCH CURSOR ON UNIQUE INDEX");
+ }
+
+ IBufferCache bufferCache = harness.getBufferCache();
+
+ // declare keys
+ int keyFieldCount = 1;
+ IBinaryComparatorFactory[] cmpFactories = new
IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] =
PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ ITreeIndexFrameFactory leafFrameFactory = new
BTreeNSMLeafFrameFactory(tupleWriterFactory);
+ ITreeIndexFrameFactory interiorFrameFactory = new
BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame)
leafFrameFactory.createFrame();
+ IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame)
interiorFrameFactory.createFrame();
+
+ IMetadataPageManager freePageManager = new
LinkedMetaDataPageManager(bufferCache, metaFrameFactory);
+
+ DiskBTree btree = new DiskBTree(bufferCache, freePageManager,
interiorFrameFactory, leafFrameFactory,
+ cmpFactories, fieldCount, harness.getFileReference());
+ btree.create();
+ btree.activate();
+
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+
+ ITreeIndexAccessor indexAccessor = btree.createAccessor(
+ new IndexAccessParameters(TestOperationCallback.INSTANCE,
TestOperationCallback.INSTANCE));
+ IIndexBulkLoader bulkloader = btree.createBulkLoader(1, true, 0, true);
+
+ // generate keys
+ int numKeys = 50;
+ int maxKey = 1000;
+ TreeSet<Integer> uniqueKeys = new TreeSet<>();
+ ArrayList<Integer> keys = new ArrayList<>();
+ while (uniqueKeys.size() < numKeys) {
+ int key = rnd.nextInt() % maxKey;
+ uniqueKeys.add(key);
+ }
+ for (Integer i : uniqueKeys) {
+ keys.add(i);
+ }
+
+ // insert keys into btree
+ for (int i = 0; i < keys.size(); i++) {
+
+ TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+ tuple.reset(tupleBuilder.getFieldEndOffsets(),
tupleBuilder.getByteArray());
+
+ try {
+ bulkloader.add(tuple);
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ bulkloader.end();
+
+ int minSearchKey = -100;
+ int maxSearchKey = 100;
+
+ // forward searches
+ Assert.assertTrue(
+ performSearches(keys, btree, leafFrame, interiorFrame,
minSearchKey, maxSearchKey, true, true, false));
+ Assert.assertTrue(
+ performSearches(keys, btree, leafFrame, interiorFrame,
minSearchKey, maxSearchKey, false, true, false));
+ Assert.assertTrue(
+ performSearches(keys, btree, leafFrame, interiorFrame,
minSearchKey, maxSearchKey, true, false, false));
+ Assert.assertTrue(
+ performSearches(keys, btree, leafFrame, interiorFrame,
minSearchKey, maxSearchKey, true, true, false));
+
+ btree.deactivate();
+ btree.destroy();
+ }
+
+ @Override
+ @Test
+ public void nonUniqueIndexTest() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("TESTING RANGE SEARCH CURSOR ON NONUNIQUE INDEX");
+ }
+
+ IBufferCache bufferCache = harness.getBufferCache();
+
+ // declare keys
+ int keyFieldCount = 2;
+ IBinaryComparatorFactory[] cmpFactories = new
IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] =
PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[1] =
PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ ITreeIndexFrameFactory leafFrameFactory = new
BTreeNSMLeafFrameFactory(tupleWriterFactory);
+ ITreeIndexFrameFactory interiorFrameFactory = new
BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame)
leafFrameFactory.createFrame();
+ IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame)
interiorFrameFactory.createFrame();
+
+ IMetadataPageManager freePageManager = new
LinkedMetaDataPageManager(bufferCache, metaFrameFactory);
+
+ DiskBTree btree = new DiskBTree(bufferCache, freePageManager,
interiorFrameFactory, leafFrameFactory,
+ cmpFactories, fieldCount, harness.getFileReference());
+ btree.create();
+ btree.activate();
+
+ IIndexBulkLoader bulkloader = btree.createBulkLoader(1.0f, true, 0,
true);
+
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+ ITreeIndexAccessor indexAccessor = btree.createAccessor(
+ new IndexAccessParameters(TestOperationCallback.INSTANCE,
TestOperationCallback.INSTANCE));
+
+ // generate keys
+ int numKeys = 50;
+ int maxKey = 10;
+ ArrayList<Integer> keys = new ArrayList<>();
+ for (int i = 0; i < numKeys; i++) {
+ int k = rnd.nextInt() % maxKey;
+ keys.add(k);
+ }
+ Collections.sort(keys);
+
+ // insert keys into btree
+ for (int i = 0; i < keys.size(); i++) {
+
+ TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+ tuple.reset(tupleBuilder.getFieldEndOffsets(),
tupleBuilder.getByteArray());
+
+ try {
+ bulkloader.add(tuple);
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+ bulkloader.end();
+
+ int minSearchKey = -100;
+ int maxSearchKey = 100;
+
+ // forward searches
+ Assert.assertTrue(
+ performSearches(keys, btree, leafFrame, interiorFrame,
minSearchKey, maxSearchKey, true, true, false));
+ Assert.assertTrue(
+ performSearches(keys, btree, leafFrame, interiorFrame,
minSearchKey, maxSearchKey, false, true, false));
+ Assert.assertTrue(
+ performSearches(keys, btree, leafFrame, interiorFrame,
minSearchKey, maxSearchKey, true, false, false));
+ Assert.assertTrue(
+ performSearches(keys, btree, leafFrame, interiorFrame,
minSearchKey, maxSearchKey, true, true, false));
+
+ btree.deactivate();
+ btree.destroy();
+ }
+
+ @Override
+ @Test
+ public void nonUniqueFieldPrefixIndexTest() throws Exception {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("TESTING RANGE SEARCH CURSOR ON NONUNIQUE FIELD-PREFIX
COMPRESSED INDEX");
+ }
+
+ IBufferCache bufferCache = harness.getBufferCache();
+
+ // declare keys
+ int keyFieldCount = 2;
+ IBinaryComparatorFactory[] cmpFactories = new
IBinaryComparatorFactory[keyFieldCount];
+ cmpFactories[0] =
PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+ cmpFactories[1] =
PointableBinaryComparatorFactory.of(IntegerPointable.FACTORY);
+
+ ITreeIndexFrameFactory leafFrameFactory = new
BTreeNSMLeafFrameFactory(tupleWriterFactory);
+ ITreeIndexFrameFactory interiorFrameFactory = new
BTreeNSMInteriorFrameFactory(tupleWriterFactory);
+
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame)
leafFrameFactory.createFrame();
+ IBTreeInteriorFrame interiorFrame = (IBTreeInteriorFrame)
interiorFrameFactory.createFrame();
+
+ IMetadataPageManager freePageManager = new
LinkedMetaDataPageManager(bufferCache, metaFrameFactory);
+
+ DiskBTree btree = new DiskBTree(bufferCache, freePageManager,
interiorFrameFactory, leafFrameFactory,
+ cmpFactories, fieldCount, harness.getFileReference());
+ btree.create();
+ btree.activate();
+ IIndexBulkLoader bulkloader = btree.createBulkLoader(1.0f, true, 0L,
true);
+
+ ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount);
+ ArrayTupleReference tuple = new ArrayTupleReference();
+
+ ITreeIndexAccessor indexAccessor = btree.createAccessor(
+ new IndexAccessParameters(TestOperationCallback.INSTANCE,
TestOperationCallback.INSTANCE));
+
+ // generate keys
+ int numKeys = 50;
+ int maxKey = 10;
+ ArrayList<Integer> keys = new ArrayList<>();
+ for (int i = 0; i < numKeys; i++) {
+ int k = rnd.nextInt() % maxKey;
+ keys.add(k);
+ }
+ Collections.sort(keys);
+
+ // insert keys into btree
+ for (int i = 0; i < keys.size(); i++) {
+
+ TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i);
+ tuple.reset(tupleBuilder.getFieldEndOffsets(),
tupleBuilder.getByteArray());
+
+ try {
+ bulkloader.add(tuple);
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ bulkloader.end();
+
+ int minSearchKey = -100;
+ int maxSearchKey = 100;
+
+ // forward searches
+ Assert.assertTrue(
+ performSearches(keys, btree, leafFrame, interiorFrame,
minSearchKey, maxSearchKey, true, true, false));
+ Assert.assertTrue(
+ performSearches(keys, btree, leafFrame, interiorFrame,
minSearchKey, maxSearchKey, false, true, false));
+ Assert.assertTrue(
+ performSearches(keys, btree, leafFrame, interiorFrame,
minSearchKey, maxSearchKey, true, false, false));
+ Assert.assertTrue(
+ performSearches(keys, btree, leafFrame, interiorFrame,
minSearchKey, maxSearchKey, true, true, false));
+
+ btree.deactivate();
+ btree.destroy();
+ }
+
+ public boolean performBatchLookups(ArrayList<Integer> keys, BTree btree,
IBTreeLeafFrame leafFrame,
+ IBTreeInteriorFrame interiorFrame, int minKey, int maxKey) throws
Exception {
+
+ ArrayList<Integer> results = new ArrayList<>();
+ ArrayList<Integer> expectedResults = new ArrayList<>();
+ BTreeAccessor indexAccessor = btree.createAccessor(
+ new IndexAccessParameters(TestOperationCallback.INSTANCE,
TestOperationCallback.INSTANCE));
+ IIndexCursor pointCursor = indexAccessor.createPointCursor(false);
+ for (int i = minKey; i < maxKey; i++) {
+ results.clear();
+ expectedResults.clear();
+
+ int lowKey = i;
+ int highKey = i;
+ RangePredicate rangePred = createRangePredicate(lowKey, highKey,
true, true);
+ indexAccessor.search(pointCursor, rangePred);
+ try {
+ while (pointCursor.hasNext()) {
+ pointCursor.next();
+ ITupleReference frameTuple = pointCursor.getTuple();
+ ByteArrayInputStream inStream = new
ByteArrayInputStream(frameTuple.getFieldData(0),
+ frameTuple.getFieldStart(0),
frameTuple.getFieldLength(0));
+ DataInput dataIn = new DataInputStream(inStream);
+ Integer res =
IntegerSerializerDeserializer.INSTANCE.deserialize(dataIn);
+ results.add(res);
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+
+ getExpectedResults(expectedResults, keys, lowKey, highKey, true,
true);
+
+ if (results.size() == expectedResults.size()) {
+ for (int k = 0; k < results.size(); k++) {
+ if (!results.get(k).equals(expectedResults.get(k))) {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("DIFFERENT RESULTS AT: i=" + i + " k="
+ k);
+ LOGGER.info(results.get(k) + " " +
expectedResults.get(k));
+ }
+ return false;
+ }
+ }
+ } else {
+ if (LOGGER.isLoggable(Level.INFO)) {
+ LOGGER.info("UNEQUAL NUMBER OF RESULTS AT: i=" + i);
+ LOGGER.info("RESULTS: " + results.size());
+ LOGGER.info("EXPECTED RESULTS: " + expectedResults.size());
+ }
+ return false;
+ }
+ }
+
+ pointCursor.close();
+
+ return true;
+ }
+
+}
diff --git
a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/org/apache/hyracks/storage/am/lsm/btree/impl/TestLsmBtreeUtil.java
b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/org/apache/hyracks/storage/am/lsm/btree/impl/TestLsmBtreeUtil.java
index 4000c1d..d614aff 100644
---
a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/org/apache/hyracks/storage/am/lsm/btree/impl/TestLsmBtreeUtil.java
+++
b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/org/apache/hyracks/storage/am/lsm/btree/impl/TestLsmBtreeUtil.java
@@ -28,7 +28,7 @@
import org.apache.hyracks.storage.am.bloomfilter.impls.BloomFilterFactory;
import org.apache.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrameFactory;
import org.apache.hyracks.storage.am.btree.frames.BTreeNSMLeafFrameFactory;
-import org.apache.hyracks.storage.am.btree.impls.BTree;
+import org.apache.hyracks.storage.am.btree.impls.DiskBTree;
import org.apache.hyracks.storage.am.common.api.IMetadataPageManagerFactory;
import org.apache.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
import org.apache.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
@@ -46,8 +46,8 @@
import org.apache.hyracks.storage.am.lsm.common.api.ILSMOperationTracker;
import org.apache.hyracks.storage.am.lsm.common.api.IVirtualBufferCache;
import
org.apache.hyracks.storage.am.lsm.common.frames.LSMComponentFilterFrameFactory;
-import org.apache.hyracks.storage.am.lsm.common.impls.BTreeFactory;
import org.apache.hyracks.storage.am.lsm.common.impls.ComponentFilterHelper;
+import org.apache.hyracks.storage.am.lsm.common.impls.DiskBTreeFactory;
import
org.apache.hyracks.storage.am.lsm.common.impls.LSMComponentFilterManager;
import org.apache.hyracks.storage.am.lsm.common.impls.TreeIndexFactory;
import org.apache.hyracks.storage.common.buffercache.IBufferCache;
@@ -77,9 +77,10 @@
ITreeIndexFrameFactory deleteLeafFrameFactory = new
BTreeNSMLeafFrameFactory(deleteTupleWriterFactory);
ITreeIndexFrameFactory interiorFrameFactory = new
BTreeNSMInteriorFrameFactory(insertTupleWriterFactory);
- TreeIndexFactory<BTree> diskBTreeFactory = new BTreeFactory(ioManager,
diskBufferCache, freePageManagerFactory,
- interiorFrameFactory, copyTupleLeafFrameFactory, cmpFactories,
typeTraits.length);
- TreeIndexFactory<BTree> bulkLoadBTreeFactory = new
BTreeFactory(ioManager, diskBufferCache,
+ TreeIndexFactory<DiskBTree> diskBTreeFactory =
+ new DiskBTreeFactory(ioManager, diskBufferCache,
freePageManagerFactory, interiorFrameFactory,
+ copyTupleLeafFrameFactory, cmpFactories,
typeTraits.length);
+ TreeIndexFactory<DiskBTree> bulkLoadBTreeFactory = new
DiskBTreeFactory(ioManager, diskBufferCache,
freePageManagerFactory, interiorFrameFactory,
insertLeafFrameFactory, cmpFactories, typeTraits.length);
ComponentFilterHelper filterHelper = null;
--
To view, visit https://asterix-gerrit.ics.uci.edu/2193
To unsubscribe, visit https://asterix-gerrit.ics.uci.edu/settings
Gerrit-MessageType: newchange
Gerrit-Change-Id: I8f2a9281478c4b8665589dc695769d0497af9961
Gerrit-PatchSet: 1
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Owner: Luo Chen <[email protected]>
