Luo Chen has submitted this change and it was merged. 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 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]> --- 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/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-common/src/main/java/org/apache/hyracks/storage/am/common/api/ITreeIndexFrame.java M hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java M hyracks-fullstack/hyracks/hyracks-storage-am-common/src/main/java/org/apache/hyracks/storage/am/common/impls/TreeIndexDiskOrderScanCursor.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/LSMBTreeDiskComponentScanCursor.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/LSMBTreeRangeSearchCursor.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 22 files changed, 943 insertions(+), 232 deletions(-) Approvals: Anon. E. Moose #1000171: abdullah alamoudi: Looks good to me, approved Jenkins: Verified; ; Verified Objections: Jenkins: Violations found 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/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 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 @@ 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; @@ -83,12 +83,7 @@ @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 @@ 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 @@ 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 @@ tupleIndex++; } - private int getLowKeyIndex() throws HyracksDataException { + protected int getLowKeyIndex() throws HyracksDataException { if (lowKey == null) { return 0; } @@ -227,7 +208,7 @@ return index; } - private int getHighKeyIndex() throws HyracksDataException { + protected int getHighKeyIndex() throws HyracksDataException { if (highKey == null) { return frame.getTupleCount() - 1; } @@ -248,12 +229,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 +267,10 @@ stopTupleIndex = getHighKeyIndex(); } + protected void resetBeforeOpen() throws HyracksDataException { + releasePage(); + } + @Override public void close() throws HyracksDataException { destroy(); @@ -310,4 +290,23 @@ 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; + } } 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; + } + + } + +} 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..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(); + } +} 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-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 ITreeIndexTupleReference createTupleReference(); public void setMultiComparator(MultiComparator cmp); + + public ITupleReference getLeftmostTuple() throws HyracksDataException; + + public ITupleReference getRightmostTuple() throws HyracksDataException; } 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 @@ 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; + } + } } 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 @@ 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 @@ @Override public void destroy() throws HyracksDataException { - page.releaseReadLatch(); - bufferCache.unpin(page); + releasePage(); page = null; } @@ -75,12 +74,9 @@ break; } - page.releaseReadLatch(); - bufferCache.unpin(page); + releasePage(); - ICachedPage nextPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false); - nextPage.acquireReadLatch(); - + ICachedPage nextPage = acquireNextPage(); page = nextPage; frame.setPage(page); tupleIndex = 0; @@ -120,8 +116,7 @@ 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 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; + } } 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/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.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 @@ 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); } 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 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 @@ 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 @@ 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 @@ } 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 @@ } } 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 @@ return true; } } else { - rangeCursors[i].destroy(); + btreeCursors[i].destroy(); } } return false; @@ -140,9 +139,9 @@ @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 @@ 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 @@ 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 @@ if (lsmHarness != null) { try { closeCursors(); - rangeCursors = null; + btreeCursors = null; } finally { lsmHarness.endSearch(opCtx); } @@ -253,10 +236,10 @@ } 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(); } } } 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.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 @@ 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; 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 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.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 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.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.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.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 @@ 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 @@ 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 @@ 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 @@ } 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 @@ 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 @@ } 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 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 @@ 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 @@ 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); + } + } } 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..c7f0425 --- /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,203 @@ +/* + * 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.List; +import java.util.TreeSet; + +import org.apache.hyracks.api.dataflow.value.IBinaryComparatorFactory; +import org.apache.hyracks.api.exceptions.HyracksDataException; +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.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.isInfoEnabled()) { + 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.isInfoEnabled()) { + 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.isInfoEnabled()) { + 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(); + + 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); + } + + insertBTree(keys, btree); + + // forward searches + Assert.assertTrue(performBatchLookups(keys, btree, leafFrame, interiorFrame, minSearchKey, maxSearchKey)); + + btree.deactivate(); + btree.destroy(); + } + + private 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.isInfoEnabled()) { + LOGGER.info("DIFFERENT RESULTS AT: i=" + i + " k=" + k); + LOGGER.info(results.get(k) + " " + expectedResults.get(k)); + } + return false; + } + } + } else { + if (LOGGER.isInfoEnabled()) { + 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; + } + + @Override + protected void insertBTree(List<Integer> keys, BTree btree) throws HyracksDataException { + ArrayTupleBuilder tupleBuilder = new ArrayTupleBuilder(fieldCount); + ArrayTupleReference tuple = new ArrayTupleReference(); + + IIndexBulkLoader bulkloader = btree.createBulkLoader(1, true, 0, true); + // 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()); + + bulkloader.add(tuple); + } + bulkloader.end(); + } + +} 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: merged Gerrit-Change-Id: I8f2a9281478c4b8665589dc695769d0497af9961 Gerrit-PatchSet: 18 Gerrit-Project: asterixdb Gerrit-Branch: master Gerrit-Owner: Luo Chen <[email protected]> Gerrit-Reviewer: Anon. E. Moose #1000171 Gerrit-Reviewer: Ian Maxon <[email protected]> Gerrit-Reviewer: Jenkins <[email protected]> Gerrit-Reviewer: Luo Chen <[email protected]> Gerrit-Reviewer: Taewoo Kim <[email protected]> Gerrit-Reviewer: abdullah alamoudi <[email protected]>
