[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 Reviewed-on: https://asterix-gerrit.ics.uci.edu/2193 Tested-by: Jenkins <[email protected]> Contrib: Jenkins <[email protected]> Integration-Tests: Jenkins <[email protected]> Reviewed-by: abdullah alamoudi <[email protected]> Project: http://git-wip-us.apache.org/repos/asf/asterixdb/repo Commit: http://git-wip-us.apache.org/repos/asf/asterixdb/commit/73d9acaf Tree: http://git-wip-us.apache.org/repos/asf/asterixdb/tree/73d9acaf Diff: http://git-wip-us.apache.org/repos/asf/asterixdb/diff/73d9acaf Branch: refs/heads/master Commit: 73d9acaf764b4a6a18875b7a0ebe7f816cafdb15 Parents: 6a58866 Author: luochen01 <[email protected]> Authored: Fri Jan 12 17:19:07 2018 -0800 Committer: Luo Chen <[email protected]> Committed: Sat Jan 13 15:01:28 2018 -0800 ---------------------------------------------------------------------- .../frames/BTreeFieldPrefixNSMLeafFrame.java | 10 + .../hyracks/storage/am/btree/impls/BTree.java | 8 +- .../am/btree/impls/BTreeRangeSearchCursor.java | 123 ++++---- .../storage/am/btree/impls/DiskBTree.java | 289 +++++++++++++++++++ .../btree/impls/DiskBTreePointSearchCursor.java | 76 +++++ .../btree/impls/DiskBTreeRangeSearchCursor.java | 106 +++++++ .../storage/am/btree/util/BTreeUtils.java | 12 + .../storage/am/common/api/ITreeIndexFrame.java | 4 + .../am/common/frames/TreeIndexNSMFrame.java | 19 ++ .../impls/TreeIndexDiskOrderScanCursor.java | 36 ++- .../lsm/btree/impls/LSMBTreeDiskComponent.java | 9 +- .../impls/LSMBTreeDiskComponentFactory.java | 6 +- .../impls/LSMBTreeDiskComponentScanCursor.java | 6 +- .../btree/impls/LSMBTreePointSearchCursor.java | 79 ++--- .../btree/impls/LSMBTreeRangeSearchCursor.java | 15 +- ...TreeWithBloomFilterDiskComponentFactory.java | 6 +- .../am/lsm/btree/utils/LSMBTreeUtil.java | 22 +- .../am/lsm/common/impls/DiskBTreeFactory.java | 45 +++ .../ondisk/OnDiskInvertedIndex.java | 7 +- .../storage/am/btree/BTreeSearchCursorTest.java | 95 ++---- .../am/btree/DiskBTreeSearchCursorTest.java | 203 +++++++++++++ .../am/lsm/btree/impl/TestLsmBtreeUtil.java | 11 +- 22 files changed, 949 insertions(+), 238 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java ---------------------------------------------------------------------- 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 @@ public class BTreeFieldPrefixNSMLeafFrame implements IBTreeLeafFrame { 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"); + } + } http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTree.java ---------------------------------------------------------------------- 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 @@ public class BTree extends AbstractTreeIndex { * 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 @@ public class BTree extends AbstractTreeIndex { 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); http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java ---------------------------------------------------------------------- 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 5ce9e1a..a75c9f7 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 @@ import org.apache.hyracks.storage.common.file.BufferedFileHandle; public class BTreeRangeSearchCursor implements ITreeIndexCursor { - private final IBTreeLeafFrame frame; - private final ITreeIndexTupleReference frameTuple; - private final boolean exclusiveLatchNodes; - private boolean isPageDirty; - - private IBufferCache bufferCache = null; - private int fileId = -1; - - private ICachedPage page = null; - private int pageId = -1; // This is used by the LSMRTree flush operation - - private int tupleIndex = 0; - private int stopTupleIndex; - - private final RangePredicate reusablePredicate; - private final ArrayTupleReference reconciliationTuple; - private IIndexAccessor accessor; - private ISearchOperationCallback searchCb; - private MultiComparator originalKeyCmp; - private ArrayTupleBuilder tupleBuilder; - - private FindTupleMode lowKeyFtm; - private FindTupleMode highKeyFtm; - private FindTupleNoExactMatchPolicy lowKeyFtp; - private FindTupleNoExactMatchPolicy highKeyFtp; - - private RangePredicate pred; - private MultiComparator lowKeyCmp; - private MultiComparator highKeyCmp; + protected final IBTreeLeafFrame frame; + protected final ITreeIndexTupleReference frameTuple; + protected final boolean exclusiveLatchNodes; + protected boolean isPageDirty; + + protected IBufferCache bufferCache = null; + protected int fileId = -1; + + protected ICachedPage page = null; + protected int pageId = -1; // This is used by the LSMRTree flush operation + + protected int tupleIndex = 0; + protected int stopTupleIndex; + + protected final RangePredicate reusablePredicate; + protected final ArrayTupleReference reconciliationTuple; + protected IIndexAccessor accessor; + protected ISearchOperationCallback searchCb; + protected MultiComparator originalKeyCmp; + protected ArrayTupleBuilder tupleBuilder; + + protected FindTupleMode lowKeyFtm; + protected FindTupleMode highKeyFtm; + protected FindTupleNoExactMatchPolicy lowKeyFtp; + protected FindTupleNoExactMatchPolicy highKeyFtp; + + 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; @@ -83,12 +83,7 @@ public class BTreeRangeSearchCursor implements ITreeIndexCursor { @Override public void destroy() throws HyracksDataException { if (page != null) { - if (exclusiveLatchNodes) { - page.releaseWriteLatch(isPageDirty); - } else { - page.releaseReadLatch(); - } - bufferCache.unpin(page); + releasePage(); } tupleIndex = 0; @@ -120,18 +115,10 @@ public class BTreeRangeSearchCursor implements ITreeIndexCursor { return pageId; } - private void fetchNextLeafPage(int nextLeafPage) throws HyracksDataException { + protected void fetchNextLeafPage(int nextLeafPage) throws HyracksDataException { do { - ICachedPage nextLeaf = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, nextLeafPage), false); - if (exclusiveLatchNodes) { - nextLeaf.acquireWriteLatch(); - page.releaseWriteLatch(isPageDirty); - } else { - nextLeaf.acquireReadLatch(); - page.releaseReadLatch(); - } - bufferCache.unpin(page); - + ICachedPage nextLeaf = acquirePage(nextLeafPage); + releasePage(); page = nextLeaf; isPageDirty = false; frame.setPage(page); @@ -173,13 +160,7 @@ public class BTreeRangeSearchCursor implements ITreeIndexCursor { TupleUtils.copyTuple(tupleBuilder, frameTuple, originalKeyCmp.getKeyFieldCount()); reconciliationTuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray()); - // unlatch/unpin - if (exclusiveLatchNodes) { - page.releaseWriteLatch(isPageDirty); - } else { - page.releaseReadLatch(); - } - bufferCache.unpin(page); + releasePage(); page = null; isPageDirty = false; @@ -210,7 +191,7 @@ public class BTreeRangeSearchCursor implements ITreeIndexCursor { tupleIndex++; } - private int getLowKeyIndex() throws HyracksDataException { + protected int getLowKeyIndex() throws HyracksDataException { if (lowKey == null) { return 0; } @@ -227,7 +208,7 @@ public class BTreeRangeSearchCursor implements ITreeIndexCursor { return index; } - private int getHighKeyIndex() throws HyracksDataException { + protected int getHighKeyIndex() throws HyracksDataException { if (highKey == null) { return frame.getTupleCount() - 1; } @@ -248,12 +229,7 @@ public class BTreeRangeSearchCursor implements ITreeIndexCursor { 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 +267,10 @@ public class BTreeRangeSearchCursor implements ITreeIndexCursor { stopTupleIndex = getHighKeyIndex(); } + protected void resetBeforeOpen() throws HyracksDataException { + releasePage(); + } + @Override public void close() throws HyracksDataException { destroy(); @@ -310,4 +290,23 @@ public class BTreeRangeSearchCursor implements ITreeIndexCursor { public boolean isExclusiveLatchNodes() { return exclusiveLatchNodes; } + + protected void releasePage() throws HyracksDataException { + if (exclusiveLatchNodes) { + page.releaseWriteLatch(isPageDirty); + } else { + page.releaseReadLatch(); + } + bufferCache.unpin(page); + } + + protected ICachedPage acquirePage(int pageId) throws HyracksDataException { + ICachedPage nextPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false); + if (exclusiveLatchNodes) { + nextPage.acquireWriteLatch(); + } else { + nextPage.acquireReadLatch(); + } + return nextPage; + } } http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTree.java ---------------------------------------------------------------------- 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..32fa9df --- /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,289 @@ +/* + * 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.ITreeIndexFrame; +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 { + ICachedPage currentPage = page; + ctx.getInteriorFrame().setPage(currentPage); + + 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(currentPage); + currentPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(getFileId(), childPageId), false); + ctx.getInteriorFrame().setPage(currentPage); + } + + ctx.getCursorInitialState().setSearchOperationCallback(ctx.getSearchCallback()); + ctx.getCursorInitialState().setOriginialKeyComparator(ctx.getCmp()); + ctx.getCursorInitialState().setPage(currentPage); + ctx.getCursorInitialState().setPageId(childPageId); + ctx.getLeafFrame().setPage(currentPage); + cursor.open(ctx.getCursorInitialState(), ctx.getPred()); + } catch (HyracksDataException e) { + if (!ctx.isExceptionHandled() && currentPage != null) { + bufferCache.unpin(currentPage); + ctx.setExceptionHandled(true); + } + throw e; + } catch (Exception e) { + if (currentPage != null) { + bufferCache.unpin(currentPage); + } + 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 DiskBTreeDiskScanCursor(leafFrame); + } + + @Override + public void diskOrderScan(ITreeIndexCursor cursor) throws HyracksDataException { + ctx.setOperation(IndexOperation.DISKORDERSCAN); + ((DiskBTree) btree).diskOrderScan(cursor, ctx); + } + } + + private class DiskBTreeDiskScanCursor extends TreeIndexDiskOrderScanCursor { + + public DiskBTreeDiskScanCursor(ITreeIndexFrame frame) { + super(frame); + } + + @Override + protected void releasePage() throws HyracksDataException { + bufferCache.unpin(page); + } + + @Override + protected ICachedPage acquireNextPage() throws HyracksDataException { + ICachedPage nextPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false); + return nextPage; + } + + } + +} http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreePointSearchCursor.java ---------------------------------------------------------------------- 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(); + } + +} http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/DiskBTreeRangeSearchCursor.java ---------------------------------------------------------------------- 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..7d4ee0d --- /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,106 @@ +/* + * 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); + } + + @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 + } + + 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; + } + + @Override + protected void releasePage() throws HyracksDataException { + bufferCache.unpin(page); + } + + @Override + protected ICachedPage acquirePage(int pageId) throws HyracksDataException { + return bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false); + } + + @Override + public void close() throws HyracksDataException { + super.close(); + searchPages.clear(); + } +} http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/util/BTreeUtils.java ---------------------------------------------------------------------- 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.BTreeLeafFrameType; 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 @@ public class BTreeUtils { 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 { http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/api/ITreeIndexFrame.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/api/ITreeIndexFrame.java b/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/api/ITreeIndexFrame.java index 8dc30c8..7ac49c6 100644 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/api/ITreeIndexFrame.java +++ b/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/api/ITreeIndexFrame.java @@ -118,4 +118,8 @@ public interface ITreeIndexFrame { public ITreeIndexTupleReference createTupleReference(); public void setMultiComparator(MultiComparator cmp); + + public ITupleReference getLeftmostTuple() throws HyracksDataException; + + public ITupleReference getRightmostTuple() throws HyracksDataException; } http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java b/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java index 5f001e0..6106358 100644 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java +++ b/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java @@ -335,4 +335,23 @@ public abstract class TreeIndexNSMFrame implements ITreeIndexFrame { return buf.capacity() - getFreeSpaceOff() - (getTupleCount() * slotManager.getSlotSize()); } + public ITupleReference getLeftmostTuple() { + int tupleCount = getTupleCount(); + if (tupleCount == 0) { + return null; + } else { + frameTuple.resetByTupleIndex(this, 0); + return frameTuple; + } + } + + public ITupleReference getRightmostTuple() { + int tupleCount = getTupleCount(); + if (tupleCount == 0) { + return null; + } else { + frameTuple.resetByTupleIndex(this, tupleCount - 1); + return frameTuple; + } + } } http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/impls/TreeIndexDiskOrderScanCursor.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/impls/TreeIndexDiskOrderScanCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/impls/TreeIndexDiskOrderScanCursor.java index 6bc5be2..3cbcf70 100644 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/impls/TreeIndexDiskOrderScanCursor.java +++ b/hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/impls/TreeIndexDiskOrderScanCursor.java @@ -32,12 +32,12 @@ import org.apache.hyracks.storage.common.file.BufferedFileHandle; public class TreeIndexDiskOrderScanCursor implements ITreeIndexCursor { - private int tupleIndex = 0; - private int fileId = -1; - private int currentPageId = -1; - private int maxPageId = -1; - private ICachedPage page = null; - private IBufferCache bufferCache = null; + protected int tupleIndex = 0; + protected int fileId = -1; + protected int currentPageId = -1; + protected int maxPageId = -1; + protected ICachedPage page = null; + protected IBufferCache bufferCache = null; private final ITreeIndexFrame frame; private final ITreeIndexTupleReference frameTuple; @@ -49,8 +49,7 @@ public class TreeIndexDiskOrderScanCursor implements ITreeIndexCursor { @Override public void destroy() throws HyracksDataException { - page.releaseReadLatch(); - bufferCache.unpin(page); + releasePage(); page = null; } @@ -75,12 +74,9 @@ public class TreeIndexDiskOrderScanCursor implements ITreeIndexCursor { break; } - page.releaseReadLatch(); - bufferCache.unpin(page); - - ICachedPage nextPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false); - nextPage.acquireReadLatch(); + releasePage(); + ICachedPage nextPage = acquireNextPage(); page = nextPage; frame.setPage(page); tupleIndex = 0; @@ -120,8 +116,7 @@ public class TreeIndexDiskOrderScanCursor implements ITreeIndexCursor { public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException { // in case open is called multiple times without closing if (page != null) { - page.releaseReadLatch(); - bufferCache.unpin(page); + releasePage(); } page = initialState.getPage(); tupleIndex = 0; @@ -159,4 +154,15 @@ public class TreeIndexDiskOrderScanCursor implements ITreeIndexCursor { public boolean isExclusiveLatchNodes() { return false; } + + protected void releasePage() throws HyracksDataException { + page.releaseReadLatch(); + bufferCache.unpin(page); + } + + protected ICachedPage acquireNextPage() throws HyracksDataException { + ICachedPage nextPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false); + nextPage.acquireReadLatch(); + return nextPage; + } } http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponent.java ---------------------------------------------------------------------- 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.HashSet; 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; } http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponentFactory.java ---------------------------------------------------------------------- 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.LSMComponentFileReferences 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; } http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponentScanCursor.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponentScanCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponentScanCursor.java index efaf555..a789ddd 100644 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponentScanCursor.java +++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeDiskComponentScanCursor.java @@ -26,10 +26,8 @@ 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.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.common.impls.NoOpIndexAccessParameters; import org.apache.hyracks.storage.am.common.tuples.PermutingTupleReference; import org.apache.hyracks.storage.am.lsm.btree.tuples.LSMBTreeTupleReference; @@ -74,11 +72,9 @@ public class LSMBTreeDiskComponentScanCursor extends LSMIndexSearchCursor { btreeAccessors = new BTreeAccessor[numBTrees]; for (int i = 0; i < numBTrees; i++) { ILSMComponent component = operationalComponents.get(i); - IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) lsmInitialState.getLeafFrameFactory().createFrame(); - rangeCursors[i] = new BTreeRangeSearchCursor(leafFrame, false); BTree btree = (BTree) component.getIndex(); - btreeAccessors[i] = btree.createAccessor(NoOpIndexAccessParameters.INSTANCE); + rangeCursors[i] = btreeAccessors[i].createSearchCursor(false); btreeAccessors[i].search(rangeCursors[i], searchPred); } http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java ---------------------------------------------------------------------- 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 0284ee1..31e0356 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,11 +24,10 @@ import java.util.List; 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; import org.apache.hyracks.storage.am.common.impls.NoOpOperationCallback; import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponent; @@ -44,7 +43,7 @@ import org.apache.hyracks.storage.common.ISearchPredicate; public class LSMBTreePointSearchCursor implements IIndexCursor { - private BTreeRangeSearchCursor[] rangeCursors; + private ITreeIndexCursor[] btreeCursors; private final ILSMIndexOperationContext opCtx; private ISearchOperationCallback searchCallback; private RangePredicate predicate; @@ -77,21 +76,21 @@ public class LSMBTreePointSearchCursor implements IIndexCursor { 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].destroy(); + btreeCursors[i].destroy(); return false; } else { - frameTuple = rangeCursors[i].getTuple(); + frameTuple = btreeCursors[i].getTuple(); foundTuple = true; foundIn = i; return true; @@ -99,20 +98,20 @@ public class LSMBTreePointSearchCursor implements IIndexCursor { } if (i == 0 && includeMutableComponent) { // unlatch/unpin - rangeCursors[i].close(); + btreeCursors[i].close(); 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].destroy(); + btreeCursors[i].destroy(); return false; } else { - frameTuple = rangeCursors[i].getTuple(); + frameTuple = btreeCursors[i].getTuple(); foundTuple = true; searchCallback.complete(predicate.getLowKey()); foundIn = i; @@ -120,10 +119,10 @@ public class LSMBTreePointSearchCursor implements IIndexCursor { } } else { searchCallback.cancel(predicate.getLowKey()); - rangeCursors[i].destroy(); + btreeCursors[i].destroy(); } } else { - frameTuple = rangeCursors[i].getTuple(); + frameTuple = btreeCursors[i].getTuple(); searchCallback.reconcile(frameTuple); searchCallback.complete(frameTuple); foundTuple = true; @@ -131,7 +130,7 @@ public class LSMBTreePointSearchCursor implements IIndexCursor { return true; } } else { - rangeCursors[i].destroy(); + btreeCursors[i].destroy(); } } return false; @@ -140,9 +139,9 @@ public class LSMBTreePointSearchCursor implements IIndexCursor { @Override public void close() throws HyracksDataException { try { - if (rangeCursors != null) { - for (int i = 0; i < rangeCursors.length; ++i) { - rangeCursors[i].close(); + if (btreeCursors != null) { + for (int i = 0; i < numBTrees; ++i) { + btreeCursors[i].close(); } } nextHasBeenCalled = false; @@ -162,9 +161,9 @@ public class LSMBTreePointSearchCursor implements IIndexCursor { 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]; } @@ -172,37 +171,21 @@ public class LSMBTreePointSearchCursor implements IIndexCursor { 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].close(); - } - 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].close(); - } 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].close(); } } nextHasBeenCalled = false; @@ -219,7 +202,7 @@ public class LSMBTreePointSearchCursor implements IIndexCursor { if (lsmHarness != null) { try { closeCursors(); - rangeCursors = null; + btreeCursors = null; } finally { lsmHarness.endSearch(opCtx); } @@ -253,10 +236,10 @@ public class LSMBTreePointSearchCursor implements IIndexCursor { } private void closeCursors() throws HyracksDataException { - if (rangeCursors != null) { + if (btreeCursors != null) { for (int i = 0; i < numBTrees; ++i) { - if (rangeCursors[i] != null) { - rangeCursors[i].destroy(); + if (btreeCursors[i] != null) { + btreeCursors[i].destroy(); } } } http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java index 36ca87f..1e401a2 100644 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java +++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java @@ -26,10 +26,8 @@ import org.apache.hyracks.api.exceptions.HyracksDataException; import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder; import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleReference; import org.apache.hyracks.dataflow.common.utils.TupleUtils; -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.impls.NoOpIndexAccessParameters; import org.apache.hyracks.storage.am.common.impls.NoOpOperationCallback; @@ -338,30 +336,25 @@ public class LSMBTreeRangeSearchCursor extends LSMIndexSearchCursor { rangeCursors = new IIndexCursor[numBTrees]; btreeAccessors = new BTreeAccessor[numBTrees]; } + for (int i = 0; i < numBTrees; i++) { ILSMComponent component = operationalComponents.get(i); BTree btree; - if (rangeCursors[i] == null) { - // create, should be relatively rare - IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) lsmInitialState.getLeafFrameFactory().createFrame(); - rangeCursors[i] = new BTreeRangeSearchCursor(leafFrame, false); - } else { - // re-use - rangeCursors[i].close(); - } - if (component.getType() == LSMComponentType.MEMORY) { includeMutableComponent = true; } btree = (BTree) component.getIndex(); if (btreeAccessors[i] == null) { btreeAccessors[i] = btree.createAccessor(NoOpIndexAccessParameters.INSTANCE); + rangeCursors[i] = btreeAccessors[i].createSearchCursor(false); } else { // re-use btreeAccessors[i].reset(btree, NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE); + rangeCursors[i].close(); } btreeAccessors[i].search(rangeCursors[i], searchPred); } + setPriorityQueueComparator(); initPriorityQueue(); canCallProceed = true; http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBloomFilterDiskComponentFactory.java ---------------------------------------------------------------------- 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 @@ package org.apache.hyracks.storage.am.lsm.btree.impls; 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.LSMComponentFileReferences 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; http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/utils/LSMBTreeUtil.java ---------------------------------------------------------------------- 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.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.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.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; @@ -87,10 +89,11 @@ public class LSMBTreeUtil { 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 @@ public class LSMBTreeUtil { 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); http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/DiskBTreeFactory.java ---------------------------------------------------------------------- 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); + } + +} http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/ondisk/OnDiskInvertedIndex.java ---------------------------------------------------------------------- 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 8db298d..4942eda 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.data.accessors.ITupleReference; 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 @@ public class OnDiskInvertedIndex implements IInPlaceInvertedIndex { 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 @@ public class OnDiskInvertedIndex implements IInPlaceInvertedIndex { 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 @@ public class OnDiskInvertedIndex implements IInPlaceInvertedIndex { 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 { http://git-wip-us.apache.org/repos/asf/asterixdb/blob/73d9acaf/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/org/apache/hyracks/storage/am/btree/BTreeSearchCursorTest.java ---------------------------------------------------------------------- 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 6c234b7..68a3984 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 @@ -24,6 +24,7 @@ import java.io.DataInput; import java.io.DataInputStream; import java.util.ArrayList; import java.util.Collections; +import java.util.List; import java.util.Random; import java.util.TreeSet; @@ -43,19 +44,19 @@ 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.BTreeRangeSearchCursor; +import org.apache.hyracks.storage.am.btree.impls.BTree.BTreeAccessor; 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.IIndexCursor; import org.apache.hyracks.storage.common.MultiComparator; import org.apache.hyracks.storage.common.buffercache.IBufferCache; import org.junit.Assert; @@ -63,12 +64,12 @@ import org.junit.Before; 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,13 +105,6 @@ public class BTreeSearchCursorTest extends AbstractBTreeTest { btree.create(); btree.activate(); - ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount); - ArrayTupleReference tuple = new ArrayTupleReference(); - - IndexAccessParameters actx = - new IndexAccessParameters(TestOperationCallback.INSTANCE, TestOperationCallback.INSTANCE); - ITreeIndexAccessor indexAccessor = btree.createAccessor(actx); - // generate keys int numKeys = 50; int maxKey = 1000; @@ -124,18 +118,7 @@ public class BTreeSearchCursorTest extends AbstractBTreeTest { keys.add(i); } - // insert keys into btree - for (int i = 0; i < keys.size(); i++) { - - TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i); - tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray()); - - try { - indexAccessor.insert(tuple); - } catch (Exception e) { - e.printStackTrace(); - } - } + insertBTree(keys, btree); int minSearchKey = -100; int maxSearchKey = 100; @@ -181,13 +164,6 @@ public class BTreeSearchCursorTest extends AbstractBTreeTest { btree.create(); btree.activate(); - ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount); - ArrayTupleReference tuple = new ArrayTupleReference(); - - IndexAccessParameters actx = - new IndexAccessParameters(TestOperationCallback.INSTANCE, TestOperationCallback.INSTANCE); - ITreeIndexAccessor indexAccessor = btree.createAccessor(actx); - // generate keys int numKeys = 50; int maxKey = 10; @@ -198,18 +174,7 @@ public class BTreeSearchCursorTest extends AbstractBTreeTest { } Collections.sort(keys); - // insert keys into btree - for (int i = 0; i < keys.size(); i++) { - - TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i); - tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray()); - - try { - indexAccessor.insert(tuple); - } catch (Exception e) { - e.printStackTrace(); - } - } + insertBTree(keys, btree); int minSearchKey = -100; int maxSearchKey = 100; @@ -254,14 +219,6 @@ public class BTreeSearchCursorTest extends AbstractBTreeTest { fieldCount, harness.getFileReference()); btree.create(); btree.activate(); - - ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount); - ArrayTupleReference tuple = new ArrayTupleReference(); - - IndexAccessParameters actx = - new IndexAccessParameters(TestOperationCallback.INSTANCE, TestOperationCallback.INSTANCE); - ITreeIndexAccessor indexAccessor = btree.createAccessor(actx); - // generate keys int numKeys = 50; int maxKey = 10; @@ -272,18 +229,7 @@ public class BTreeSearchCursorTest extends AbstractBTreeTest { } Collections.sort(keys); - // insert keys into btree - for (int i = 0; i < keys.size(); i++) { - - TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i); - tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray()); - - try { - indexAccessor.insert(tuple); - } catch (Exception e) { - e.printStackTrace(); - } - } + insertBTree(keys, btree); int minSearchKey = -100; int maxSearchKey = 100; @@ -304,7 +250,6 @@ public class BTreeSearchCursorTest extends AbstractBTreeTest { 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); @@ -351,18 +296,17 @@ public class BTreeSearchCursorTest extends AbstractBTreeTest { 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 { @@ -435,4 +379,19 @@ public class BTreeSearchCursorTest extends AbstractBTreeTest { return true; } + + protected void insertBTree(List<Integer> keys, BTree btree) throws HyracksDataException { + IndexAccessParameters actx = + new IndexAccessParameters(TestOperationCallback.INSTANCE, TestOperationCallback.INSTANCE); + BTreeAccessor accessor = btree.createAccessor(actx); + ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount); + ArrayTupleReference tuple = new ArrayTupleReference(); + + // 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()); + accessor.insert(tuple); + } + } }
