Repository: asterixdb Updated Branches: refs/heads/master 9473e0327 -> 9782f8a29
[ASTERIXDB-2128] Fix bloomfilter during index search - user model changes: no - storage format changes: no - interface changes: no Details: - The current use of bloomfilter during search is completely wrong (including primary index point lookups, secondary index search with deleted btrees). We call BTree.search before bloomfilter check, which renders bloomfilter completely useless. This patch fixes this serious problem. Change-Id: I90ab0d0b2da0028e0ec3cfa94d21881318293ff7 Reviewed-on: https://asterix-gerrit.ics.uci.edu/2069 Reviewed-by: abdullah alamoudi <[email protected]> Sonar-Qube: Jenkins <[email protected]> Tested-by: Jenkins <[email protected]> Contrib: Jenkins <[email protected]> Integration-Tests: Jenkins <[email protected]> Project: http://git-wip-us.apache.org/repos/asf/asterixdb/repo Commit: http://git-wip-us.apache.org/repos/asf/asterixdb/commit/9782f8a2 Tree: http://git-wip-us.apache.org/repos/asf/asterixdb/tree/9782f8a2 Diff: http://git-wip-us.apache.org/repos/asf/asterixdb/diff/9782f8a2 Branch: refs/heads/master Commit: 9782f8a295595efad74fd494960cd2680f3e7c42 Parents: 9473e03 Author: luochen01 <[email protected]> Authored: Fri Oct 20 16:16:57 2017 -0700 Committer: Luo Chen <[email protected]> Committed: Fri Oct 20 19:33:40 2017 -0700 ---------------------------------------------------------------------- .../am/bloomfilter/impls/BloomFilter.java | 10 ++-- .../am/btree/impls/BTreeRangeSearchCursor.java | 4 -- .../btree/impls/LSMBTreePointSearchCursor.java | 25 +++++---- .../impls/LSMBTreeWithBuddyAbstractCursor.java | 22 ++++---- .../impls/LSMBTreeWithBuddySearchCursor.java | 13 +++-- .../BloomFilterAwareBTreePointSearchCursor.java | 53 -------------------- .../LSMInvertedIndexRangeSearchCursor.java | 18 ++++--- .../impls/LSMInvertedIndexSearchCursor.java | 18 ++++--- .../lsm/rtree/impls/LSMRTreeAbstractCursor.java | 19 +++---- .../lsm/rtree/impls/LSMRTreeSearchCursor.java | 9 ++-- .../storage/am/bloomfilter/BloomFilterTest.java | 4 +- 11 files changed, 82 insertions(+), 113 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/asterixdb/blob/9782f8a2/hyracks-fullstack/hyracks/hyracks-storage-am-bloomfilter/src/main/java/org/apache/hyracks/storage/am/bloomfilter/impls/BloomFilter.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-bloomfilter/src/main/java/org/apache/hyracks/storage/am/bloomfilter/impls/BloomFilter.java b/hyracks-fullstack/hyracks/hyracks-storage-am-bloomfilter/src/main/java/org/apache/hyracks/storage/am/bloomfilter/impls/BloomFilter.java index 47a9734..68b96a3 100644 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-bloomfilter/src/main/java/org/apache/hyracks/storage/am/bloomfilter/impls/BloomFilter.java +++ b/hyracks-fullstack/hyracks/hyracks-storage-am-bloomfilter/src/main/java/org/apache/hyracks/storage/am/bloomfilter/impls/BloomFilter.java @@ -170,6 +170,10 @@ public class BloomFilter { fileId = -1; } + public static long[] createHashArray() { + return new long[2]; + } + public synchronized void destroy() throws HyracksDataException { if (isActivated) { throw HyracksDataException.create(ErrorCode.CANNOT_DESTROY_ACTIVE_BLOOM_FILTER); @@ -183,13 +187,13 @@ public class BloomFilter { } public class BloomFilterBuilder implements IIndexBulkLoader { - private final long[] hashes = new long[2]; + private final long[] hashes = BloomFilter.createHashArray(); private final long numElements; private final int numHashes; private final long numBits; private final int numPages; - private IFIFOPageQueue queue; - private ICachedPage[] pages; + private final IFIFOPageQueue queue; + private final ICachedPage[] pages; private ICachedPage metaDataPage = null; public BloomFilterBuilder(long numElements, int numHashes, int numBitsPerElement) throws HyracksDataException { http://git-wip-us.apache.org/repos/asf/asterixdb/blob/9782f8a2/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 32cc7ee..13cb57a 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 @@ -310,8 +310,4 @@ public class BTreeRangeSearchCursor implements ITreeIndexCursor { public boolean isExclusiveLatchNodes() { return exclusiveLatchNodes; } - - public boolean isBloomFilterAware() { - return false; - } } http://git-wip-us.apache.org/repos/asf/asterixdb/blob/9782f8a2/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 0f7aa38..24a78a6 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 @@ -23,6 +23,7 @@ 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; @@ -36,7 +37,6 @@ import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponentFilter; import org.apache.hyracks.storage.am.lsm.common.api.ILSMHarness; import org.apache.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext; import org.apache.hyracks.storage.am.lsm.common.api.ILSMTreeTupleReference; -import org.apache.hyracks.storage.am.lsm.common.impls.BloomFilterAwareBTreePointSearchCursor; import org.apache.hyracks.storage.common.ICursorInitialState; import org.apache.hyracks.storage.common.ISearchOperationCallback; import org.apache.hyracks.storage.common.ISearchPredicate; @@ -51,6 +51,7 @@ public class LSMBTreePointSearchCursor implements ITreeIndexCursor { private boolean includeMutableComponent; private int numBTrees; private BTreeAccessor[] btreeAccessors; + private BloomFilter[] bloomFilters; private ILSMHarness lsmHarness; private boolean nextHasBeenCalled; private boolean foundTuple; @@ -58,6 +59,8 @@ public class LSMBTreePointSearchCursor implements ITreeIndexCursor { private ITupleReference frameTuple; private List<ILSMComponent> operationalComponents; + private final long[] hashes = BloomFilter.createHashArray(); + public LSMBTreePointSearchCursor(ILSMIndexOperationContext opCtx) { this.opCtx = opCtx; } @@ -71,6 +74,9 @@ public class LSMBTreePointSearchCursor implements ITreeIndexCursor { } boolean reconciled = false; for (int i = 0; i < numBTrees; ++i) { + if (bloomFilters[i] != null && !bloomFilters[i].contains(predicate.getLowKey(), hashes)) { + continue; + } btreeAccessors[i].search(rangeCursors[i], predicate); if (rangeCursors[i].hasNext()) { rangeCursors[i].next(); @@ -139,7 +145,6 @@ public class LSMBTreePointSearchCursor implements ITreeIndexCursor { rangeCursors[i].reset(); } } - rangeCursors = null; nextHasBeenCalled = false; foundTuple = false; } finally { @@ -161,6 +166,7 @@ public class LSMBTreePointSearchCursor implements ITreeIndexCursor { // object creation: should be relatively low rangeCursors = new BTreeRangeSearchCursor[numBTrees]; btreeAccessors = new BTreeAccessor[numBTrees]; + bloomFilters = new BloomFilter[numBTrees]; } includeMutableComponent = false; @@ -169,8 +175,7 @@ public class LSMBTreePointSearchCursor implements ITreeIndexCursor { BTree btree; if (component.getType() == LSMComponentType.MEMORY) { includeMutableComponent = true; - // No need for a bloom filter for the in-memory BTree. - if (rangeCursors[i] == null || rangeCursors[i].isBloomFilterAware()) { + if (rangeCursors[i] == null) { // create a new one IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) lsmInitialState.getLeafFrameFactory().createFrame(); rangeCursors[i] = new BTreeRangeSearchCursor(leafFrame, false); @@ -179,19 +184,19 @@ public class LSMBTreePointSearchCursor implements ITreeIndexCursor { rangeCursors[i].reset(); } btree = ((LSMBTreeMemoryComponent) component).getIndex(); + // no bloom filter for in-memory BTree + bloomFilters[i] = null; } else { - if (rangeCursors[i] != null && rangeCursors[i].isBloomFilterAware()) { + if (rangeCursors[i] != null) { // can re-use cursor - ((BloomFilterAwareBTreePointSearchCursor) rangeCursors[i]) - .resetBloomFilter(((LSMBTreeWithBloomFilterDiskComponent) component).getBloomFilter()); rangeCursors[i].reset(); } else { // create new cursor <should be relatively rare> IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) lsmInitialState.getLeafFrameFactory().createFrame(); - rangeCursors[i] = new BloomFilterAwareBTreePointSearchCursor(leafFrame, false, - ((LSMBTreeWithBloomFilterDiskComponent) component).getBloomFilter()); + rangeCursors[i] = new BTreeRangeSearchCursor(leafFrame, false); } - btree = (BTree) component.getIndex(); + btree = ((LSMBTreeWithBloomFilterDiskComponent) component).getIndex(); + bloomFilters[i] = ((LSMBTreeWithBloomFilterDiskComponent) component).getBloomFilter(); } if (btreeAccessors[i] == null) { btreeAccessors[i] = http://git-wip-us.apache.org/repos/asf/asterixdb/blob/9782f8a2/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBuddyAbstractCursor.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBuddyAbstractCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBuddyAbstractCursor.java index 5122e43..2d2d184 100644 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBuddyAbstractCursor.java +++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBuddyAbstractCursor.java @@ -22,6 +22,7 @@ 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; @@ -33,8 +34,6 @@ import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponent; import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponent.LSMComponentType; import org.apache.hyracks.storage.am.lsm.common.api.ILSMHarness; import org.apache.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext; -import org.apache.hyracks.storage.am.lsm.common.api.AbstractLSMWithBuddyDiskComponent; -import org.apache.hyracks.storage.am.lsm.common.impls.BloomFilterAwareBTreePointSearchCursor; import org.apache.hyracks.storage.common.ICursorInitialState; import org.apache.hyracks.storage.common.ISearchPredicate; import org.apache.hyracks.storage.common.MultiComparator; @@ -47,6 +46,7 @@ public abstract class LSMBTreeWithBuddyAbstractCursor implements ITreeIndexCurso protected BTreeRangeSearchCursor[] buddyBtreeCursors; protected BTreeAccessor[] btreeAccessors; protected BTreeAccessor[] buddyBtreeAccessors; + protected BloomFilter[] buddyBtreeBloomFilters; protected MultiComparator btreeCmp; protected MultiComparator buddyBtreeCmp; protected int numberOfTrees; @@ -58,6 +58,8 @@ public abstract class LSMBTreeWithBuddyAbstractCursor implements ITreeIndexCurso protected boolean foundNext; protected final ILSMIndexOperationContext opCtx; + protected final long[] hashes = BloomFilter.createHashArray(); + protected List<ILSMComponent> operationalComponents; public LSMBTreeWithBuddyAbstractCursor(ILSMIndexOperationContext opCtx) { @@ -87,6 +89,7 @@ public abstract class LSMBTreeWithBuddyAbstractCursor implements ITreeIndexCurso buddyBtreeCursors = new BTreeRangeSearchCursor[numberOfTrees]; btreeAccessors = new BTreeAccessor[numberOfTrees]; buddyBtreeAccessors = new BTreeAccessor[numberOfTrees]; + buddyBtreeBloomFilters = new BloomFilter[numberOfTrees]; } includeMutableComponent = false; @@ -99,7 +102,7 @@ public abstract class LSMBTreeWithBuddyAbstractCursor implements ITreeIndexCurso // This is not needed at the moment but is implemented anyway includeMutableComponent = true; // No need for a bloom filter for the in-memory BTree. - if (buddyBtreeCursors[i] == null || buddyBtreeCursors[i].isBloomFilterAware()) { + if (buddyBtreeCursors[i] == null) { buddyBtreeCursors[i] = new BTreeRangeSearchCursor( (IBTreeLeafFrame) lsmInitialState.getBuddyBTreeLeafFrameFactory().createFrame(), false); } else { @@ -107,16 +110,17 @@ public abstract class LSMBTreeWithBuddyAbstractCursor implements ITreeIndexCurso } btree = ((LSMBTreeWithBuddyMemoryComponent) component).getIndex(); buddyBtree = ((LSMBTreeWithBuddyMemoryComponent) component).getBuddyIndex(); + buddyBtreeBloomFilters[i] = null; } else { - if (buddyBtreeCursors[i] == null || !buddyBtreeCursors[i].isBloomFilterAware()) { - buddyBtreeCursors[i] = new BloomFilterAwareBTreePointSearchCursor( - (IBTreeLeafFrame) lsmInitialState.getBuddyBTreeLeafFrameFactory().createFrame(), false, - ((AbstractLSMWithBuddyDiskComponent) operationalComponents.get(i)).getBloomFilter()); + if (buddyBtreeCursors[i] == null) { + buddyBtreeCursors[i] = new BTreeRangeSearchCursor( + (IBTreeLeafFrame) lsmInitialState.getBuddyBTreeLeafFrameFactory().createFrame(), false); } else { buddyBtreeCursors[i].reset(); } - btree = (BTree) component.getIndex(); - buddyBtree = (BTree) ((AbstractLSMWithBuddyDiskComponent) component).getBuddyIndex(); + btree = ((LSMBTreeWithBuddyDiskComponent) component).getIndex(); + buddyBtree = ((LSMBTreeWithBuddyDiskComponent) component).getBuddyIndex(); + buddyBtreeBloomFilters[i] = ((LSMBTreeWithBuddyDiskComponent) component).getBloomFilter(); } IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) lsmInitialState.getBTreeLeafFrameFactory().createFrame(); if (btreeAccessors[i] == null) { http://git-wip-us.apache.org/repos/asf/asterixdb/blob/9782f8a2/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBuddySearchCursor.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBuddySearchCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBuddySearchCursor.java index d6aa0c6..503182a 100644 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBuddySearchCursor.java +++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeWithBuddySearchCursor.java @@ -28,7 +28,7 @@ import org.apache.hyracks.storage.common.ISearchPredicate; public class LSMBTreeWithBuddySearchCursor extends LSMBTreeWithBuddyAbstractCursor { private int currentCursor; - private PermutingTupleReference buddyBTreeTuple; + private final PermutingTupleReference buddyBTreeTuple; public LSMBTreeWithBuddySearchCursor(ILSMIndexOperationContext opCtx, int[] buddyBTreeFields) { super(opCtx); @@ -80,7 +80,11 @@ public class LSMBTreeWithBuddySearchCursor extends LSMBTreeWithBuddyAbstractCurs ITupleReference currentTuple = btreeCursors[currentCursor].getTuple(); buddyBTreeTuple.reset(btreeCursors[currentCursor].getTuple()); boolean killerTupleFound = false; - for (int i = 0; i < currentCursor; i++) { + for (int i = 0; i < currentCursor && !killerTupleFound; i++) { + if (buddyBtreeBloomFilters[i] != null + && !buddyBtreeBloomFilters[i].contains(buddyBTreeTuple, hashes)) { + continue; + } buddyBtreeCursors[i].reset(); buddyBtreeRangePredicate.setHighKey(buddyBTreeTuple, true); buddyBtreeRangePredicate.setLowKey(buddyBTreeTuple, true); @@ -88,7 +92,6 @@ public class LSMBTreeWithBuddySearchCursor extends LSMBTreeWithBuddyAbstractCurs try { if (buddyBtreeCursors[i].hasNext()) { killerTupleFound = true; - break; } } finally { buddyBtreeCursors[i].close(); @@ -115,13 +118,13 @@ public class LSMBTreeWithBuddySearchCursor extends LSMBTreeWithBuddyAbstractCurs @Override public ITupleReference getFilterMinTuple() { ILSMComponentFilter filter = getFilter(); - return filter == null ? null : filter.getMinTuple(); + return filter == null ? null : filter.getMinTuple(); } @Override public ITupleReference getFilterMaxTuple() { ILSMComponentFilter filter = getFilter(); - return filter == null ? null : filter.getMaxTuple(); + return filter == null ? null : filter.getMaxTuple(); } private ILSMComponentFilter getFilter() { http://git-wip-us.apache.org/repos/asf/asterixdb/blob/9782f8a2/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/BloomFilterAwareBTreePointSearchCursor.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/BloomFilterAwareBTreePointSearchCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/BloomFilterAwareBTreePointSearchCursor.java deleted file mode 100644 index f84aeb5..0000000 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-common/src/main/java/org/apache/hyracks/storage/am/lsm/common/impls/BloomFilterAwareBTreePointSearchCursor.java +++ /dev/null @@ -1,53 +0,0 @@ -/* - * 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.exceptions.HyracksDataException; -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.BTreeRangeSearchCursor; - -public class BloomFilterAwareBTreePointSearchCursor extends BTreeRangeSearchCursor { - private BloomFilter bloomFilter; - private long[] hashes = new long[2]; - - public BloomFilterAwareBTreePointSearchCursor(IBTreeLeafFrame frame, boolean exclusiveLatchNodes, - BloomFilter bloomFilter) { - super(frame, exclusiveLatchNodes); - this.bloomFilter = bloomFilter; - } - - @Override - public boolean hasNext() throws HyracksDataException { - if (bloomFilter.contains(lowKey, hashes)) { - return super.hasNext(); - } - return false; - } - - @Override - public boolean isBloomFilterAware() { - return true; - } - - public void resetBloomFilter(BloomFilter bloomFilter) { - this.bloomFilter = bloomFilter; - } -} http://git-wip-us.apache.org/repos/asf/asterixdb/blob/9782f8a2/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursor.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursor.java index ec1fe68..d565b9a 100644 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursor.java +++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursor.java @@ -22,13 +22,12 @@ package org.apache.hyracks.storage.am.lsm.invertedindex.impls; import java.util.ArrayList; import org.apache.hyracks.api.exceptions.HyracksDataException; -import org.apache.hyracks.storage.am.btree.api.IBTreeLeafFrame; +import org.apache.hyracks.storage.am.bloomfilter.impls.BloomFilter; import org.apache.hyracks.storage.am.btree.impls.RangePredicate; import org.apache.hyracks.storage.am.common.tuples.PermutingTupleReference; import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponent; import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponent.LSMComponentType; import org.apache.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext; -import org.apache.hyracks.storage.am.lsm.common.impls.BloomFilterAwareBTreePointSearchCursor; import org.apache.hyracks.storage.am.lsm.common.impls.LSMIndexSearchCursor; import org.apache.hyracks.storage.am.lsm.invertedindex.api.IInvertedIndexAccessor; import org.apache.hyracks.storage.common.ICursorInitialState; @@ -41,6 +40,8 @@ public class LSMInvertedIndexRangeSearchCursor extends LSMIndexSearchCursor { // Assuming the cursor for all deleted-keys indexes are of the same type. private IIndexCursor[] deletedKeysBTreeCursors; + protected BloomFilter[] bloomFilters; + protected final long[] hashes = BloomFilter.createHashArray(); protected ArrayList<IIndexAccessor> deletedKeysBTreeAccessors; protected PermutingTupleReference keysOnlyTuple; protected RangePredicate keySearchPred; @@ -73,18 +74,17 @@ public class LSMInvertedIndexRangeSearchCursor extends LSMIndexSearchCursor { // For searching the deleted-keys BTrees. this.keysOnlyTuple = lsmInitState.getKeysOnlyTuple(); deletedKeysBTreeAccessors = lsmInitState.getDeletedKeysBTreeAccessors(); - + bloomFilters = new BloomFilter[deletedKeysBTreeAccessors.size()]; if (!deletedKeysBTreeAccessors.isEmpty()) { deletedKeysBTreeCursors = new IIndexCursor[deletedKeysBTreeAccessors.size()]; for (int i = 0; i < operationalComponents.size(); i++) { ILSMComponent component = operationalComponents.get(i); + deletedKeysBTreeCursors[i] = deletedKeysBTreeAccessors.get(i).createSearchCursor(false); if (component.getType() == LSMComponentType.MEMORY) { // No need for a bloom filter for the in-memory BTree. - deletedKeysBTreeCursors[i] = deletedKeysBTreeAccessors.get(i).createSearchCursor(false); + bloomFilters[i] = null; } else { - deletedKeysBTreeCursors[i] = new BloomFilterAwareBTreePointSearchCursor( - (IBTreeLeafFrame) lsmInitState.getgetDeletedKeysBTreeLeafFrameFactory().createFrame(), - false, ((LSMInvertedIndexDiskComponent) operationalComponents.get(i)).getBloomFilter()); + bloomFilters[i] = ((LSMInvertedIndexDiskComponent) component).getBloomFilter(); } } } @@ -103,6 +103,9 @@ public class LSMInvertedIndexRangeSearchCursor extends LSMIndexSearchCursor { keysOnlyTuple.reset(checkElement.getTuple()); int end = checkElement.getCursorIndex(); for (int i = 0; i < end; i++) { + if (bloomFilters[i] != null && bloomFilters[i].contains(keysOnlyTuple, hashes)) { + continue; + } deletedKeysBTreeCursors[i].reset(); try { deletedKeysBTreeAccessors.get(i).search(deletedKeysBTreeCursors[i], keySearchPred); @@ -115,4 +118,5 @@ public class LSMInvertedIndexRangeSearchCursor extends LSMIndexSearchCursor { } return false; } + } http://git-wip-us.apache.org/repos/asf/asterixdb/blob/9782f8a2/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexSearchCursor.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexSearchCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexSearchCursor.java index b07b4b0..c214a2c 100644 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexSearchCursor.java +++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-invertedindex/src/main/java/org/apache/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexSearchCursor.java @@ -22,14 +22,13 @@ 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.btree.api.IBTreeLeafFrame; +import org.apache.hyracks.storage.am.bloomfilter.impls.BloomFilter; import org.apache.hyracks.storage.am.btree.impls.RangePredicate; import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponent; import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponent.LSMComponentType; import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponentFilter; import org.apache.hyracks.storage.am.lsm.common.api.ILSMHarness; import org.apache.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext; -import org.apache.hyracks.storage.am.lsm.common.impls.BloomFilterAwareBTreePointSearchCursor; import org.apache.hyracks.storage.common.ICursorInitialState; import org.apache.hyracks.storage.common.IIndexAccessor; import org.apache.hyracks.storage.common.IIndexCursor; @@ -54,6 +53,7 @@ public class LSMInvertedIndexSearchCursor implements IIndexCursor { // Assuming the cursor for all deleted-keys indexes are of the same type. private IIndexCursor[] deletedKeysBTreeCursors; + private BloomFilter[] deletedKeysBTreeBloomFilters; private List<IIndexAccessor> deletedKeysBTreeAccessors; private RangePredicate keySearchPred; private ILSMIndexOperationContext opCtx; @@ -62,6 +62,8 @@ public class LSMInvertedIndexSearchCursor implements IIndexCursor { private ITupleReference currentTuple = null; private boolean resultOfSearchCallBackProceed = false; + private final long[] hashes = BloomFilter.createHashArray(); + @Override public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException { LSMInvertedIndexSearchCursorInitialState lsmInitState = (LSMInvertedIndexSearchCursorInitialState) initialState; @@ -76,16 +78,15 @@ public class LSMInvertedIndexSearchCursor implements IIndexCursor { // For searching the deleted-keys BTrees. deletedKeysBTreeAccessors = lsmInitState.getDeletedKeysBTreeAccessors(); deletedKeysBTreeCursors = new IIndexCursor[deletedKeysBTreeAccessors.size()]; - + deletedKeysBTreeBloomFilters = new BloomFilter[deletedKeysBTreeAccessors.size()]; for (int i = 0; i < operationalComponents.size(); i++) { ILSMComponent component = operationalComponents.get(i); + deletedKeysBTreeCursors[i] = deletedKeysBTreeAccessors.get(i).createSearchCursor(false); if (component.getType() == LSMComponentType.MEMORY) { // No need for a bloom filter for the in-memory BTree. - deletedKeysBTreeCursors[i] = deletedKeysBTreeAccessors.get(i).createSearchCursor(false); + deletedKeysBTreeBloomFilters[i] = null; } else { - deletedKeysBTreeCursors[i] = new BloomFilterAwareBTreePointSearchCursor( - (IBTreeLeafFrame) lsmInitState.getgetDeletedKeysBTreeLeafFrameFactory().createFrame(), false, - ((LSMInvertedIndexDiskComponent) operationalComponents.get(i)).getBloomFilter()); + deletedKeysBTreeBloomFilters[i] = ((LSMInvertedIndexDiskComponent) component).getBloomFilter(); } } @@ -98,6 +99,9 @@ public class LSMInvertedIndexSearchCursor implements IIndexCursor { keySearchPred.setHighKey(key, true); for (int i = 0; i < accessorIndex; i++) { deletedKeysBTreeCursors[i].reset(); + if (deletedKeysBTreeBloomFilters[i] != null && !deletedKeysBTreeBloomFilters[i].contains(key, hashes)) { + continue; + } try { deletedKeysBTreeAccessors.get(i).search(deletedKeysBTreeCursors[i], keySearchPred); if (deletedKeysBTreeCursors[i].hasNext()) { http://git-wip-us.apache.org/repos/asf/asterixdb/blob/9782f8a2/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/org/apache/hyracks/storage/am/lsm/rtree/impls/LSMRTreeAbstractCursor.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/org/apache/hyracks/storage/am/lsm/rtree/impls/LSMRTreeAbstractCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/org/apache/hyracks/storage/am/lsm/rtree/impls/LSMRTreeAbstractCursor.java index 7cc38f9..77219a2 100644 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/org/apache/hyracks/storage/am/lsm/rtree/impls/LSMRTreeAbstractCursor.java +++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/org/apache/hyracks/storage/am/lsm/rtree/impls/LSMRTreeAbstractCursor.java @@ -22,6 +22,7 @@ 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; @@ -33,7 +34,6 @@ import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponent; import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponent.LSMComponentType; import org.apache.hyracks.storage.am.lsm.common.api.ILSMHarness; import org.apache.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext; -import org.apache.hyracks.storage.am.lsm.common.impls.BloomFilterAwareBTreePointSearchCursor; import org.apache.hyracks.storage.am.rtree.api.IRTreeInteriorFrame; import org.apache.hyracks.storage.am.rtree.api.IRTreeLeafFrame; import org.apache.hyracks.storage.am.rtree.impls.RTree; @@ -52,6 +52,7 @@ public abstract class LSMRTreeAbstractCursor implements ITreeIndexCursor { protected BTreeRangeSearchCursor[] btreeCursors; protected RTreeAccessor[] rtreeAccessors; protected BTreeAccessor[] btreeAccessors; + protected BloomFilter[] bloomFilters; private MultiComparator btreeCmp; protected int numberOfTrees; protected SearchPredicate rtreeSearchPredicate; @@ -61,8 +62,8 @@ public abstract class LSMRTreeAbstractCursor implements ITreeIndexCursor { protected ILSMHarness lsmHarness; protected boolean foundNext; protected final ILSMIndexOperationContext opCtx; - protected List<ILSMComponent> operationalComponents; + protected long[] hashes = BloomFilter.createHashArray(); public LSMRTreeAbstractCursor(ILSMIndexOperationContext opCtx) { this.opCtx = opCtx; @@ -92,6 +93,7 @@ public abstract class LSMRTreeAbstractCursor implements ITreeIndexCursor { btreeCursors = new BTreeRangeSearchCursor[numberOfTrees]; rtreeAccessors = new RTreeAccessor[numberOfTrees]; btreeAccessors = new BTreeAccessor[numberOfTrees]; + bloomFilters = new BloomFilter[numberOfTrees]; } includeMutableComponent = false; @@ -102,7 +104,7 @@ public abstract class LSMRTreeAbstractCursor implements ITreeIndexCursor { if (component.getType() == LSMComponentType.MEMORY) { includeMutableComponent = true; // No need for a bloom filter for the in-memory BTree. - if (btreeCursors[i] == null || btreeCursors[i].isBloomFilterAware()) { + if (btreeCursors[i] == null) { //create btreeCursors[i] = new BTreeRangeSearchCursor( (IBTreeLeafFrame) lsmInitialState.getBTreeLeafFrameFactory().createFrame(), false); @@ -112,20 +114,19 @@ public abstract class LSMRTreeAbstractCursor implements ITreeIndexCursor { } rtree = ((LSMRTreeMemoryComponent) component).getIndex(); btree = ((LSMRTreeMemoryComponent) component).getBuddyIndex(); + bloomFilters[i] = null; } else { - if (btreeCursors[i] == null || !btreeCursors[i].isBloomFilterAware()) { + if (btreeCursors[i] == null) { // need to create a new one - btreeCursors[i] = new BloomFilterAwareBTreePointSearchCursor( - (IBTreeLeafFrame) lsmInitialState.getBTreeLeafFrameFactory().createFrame(), false, - ((LSMRTreeDiskComponent) operationalComponents.get(i)).getBloomFilter()); + btreeCursors[i] = new BTreeRangeSearchCursor( + (IBTreeLeafFrame) lsmInitialState.getBTreeLeafFrameFactory().createFrame(), false); } else { // reset - ((BloomFilterAwareBTreePointSearchCursor) btreeCursors[i]) - .resetBloomFilter(((LSMRTreeDiskComponent) operationalComponents.get(i)).getBloomFilter()); btreeCursors[i].reset(); } rtree = ((LSMRTreeDiskComponent) component).getIndex(); btree = ((LSMRTreeDiskComponent) component).getBuddyIndex(); + bloomFilters[i] = ((LSMRTreeDiskComponent) component).getBloomFilter(); } if (rtreeCursors[i] == null) { rtreeCursors[i] = new RTreeSearchCursor( http://git-wip-us.apache.org/repos/asf/asterixdb/blob/9782f8a2/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/org/apache/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/org/apache/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/org/apache/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java index ec85127..06c39db 100644 --- a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/org/apache/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java +++ b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-rtree/src/main/java/org/apache/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java @@ -22,7 +22,6 @@ package org.apache.hyracks.storage.am.lsm.rtree.impls; import org.apache.hyracks.api.exceptions.HyracksDataException; import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference; import org.apache.hyracks.storage.am.common.tuples.PermutingTupleReference; -import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponent; import org.apache.hyracks.storage.am.lsm.common.api.ILSMComponentFilter; import org.apache.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext; import org.apache.hyracks.storage.common.ICursorInitialState; @@ -31,7 +30,7 @@ import org.apache.hyracks.storage.common.ISearchPredicate; public class LSMRTreeSearchCursor extends LSMRTreeAbstractCursor { private int currentCursor; - private PermutingTupleReference btreeTuple; + private final PermutingTupleReference btreeTuple; public LSMRTreeSearchCursor(ILSMIndexOperationContext opCtx, int[] buddyBTreeFields) { super(opCtx); @@ -99,7 +98,10 @@ public class LSMRTreeSearchCursor extends LSMRTreeAbstractCursor { ITupleReference currentTuple = rtreeCursors[currentCursor].getTuple(); btreeTuple.reset(rtreeCursors[currentCursor].getTuple()); boolean killerTupleFound = false; - for (int i = 0; i < currentCursor; i++) { + for (int i = 0; i < currentCursor && !killerTupleFound; i++) { + if (bloomFilters[i] != null && bloomFilters[i].contains(btreeTuple, hashes)) { + continue; + } btreeCursors[i].reset(); btreeRangePredicate.setHighKey(btreeTuple, true); btreeRangePredicate.setLowKey(btreeTuple, true); @@ -107,7 +109,6 @@ public class LSMRTreeSearchCursor extends LSMRTreeAbstractCursor { try { if (btreeCursors[i].hasNext()) { killerTupleFound = true; - break; } } finally { btreeCursors[i].close(); http://git-wip-us.apache.org/repos/asf/asterixdb/blob/9782f8a2/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-bloomfilter-test/src/test/java/org/apache/hyracks/storage/am/bloomfilter/BloomFilterTest.java ---------------------------------------------------------------------- diff --git a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-bloomfilter-test/src/test/java/org/apache/hyracks/storage/am/bloomfilter/BloomFilterTest.java b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-bloomfilter-test/src/test/java/org/apache/hyracks/storage/am/bloomfilter/BloomFilterTest.java index 35779ac..24b1122 100644 --- a/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-bloomfilter-test/src/test/java/org/apache/hyracks/storage/am/bloomfilter/BloomFilterTest.java +++ b/hyracks-fullstack/hyracks/hyracks-tests/hyracks-storage-am-bloomfilter-test/src/test/java/org/apache/hyracks/storage/am/bloomfilter/BloomFilterTest.java @@ -99,7 +99,7 @@ public class BloomFilterTest extends AbstractBloomFilterTest { // Check all the inserted tuples can be found. - long[] hashes = new long[2]; + long[] hashes = BloomFilter.createHashArray(); for (int i = 0; i < keys.size(); ++i) { TupleUtils.createIntegerTuple(tupleBuilder, tuple, keys.get(i), i); Assert.assertTrue(bf.contains(tuple, hashes)); @@ -157,7 +157,7 @@ public class BloomFilterTest extends AbstractBloomFilterTest { } builder.end(); - long[] hashes = new long[2]; + long[] hashes = BloomFilter.createHashArray(); for (int i = 0; i < numElements; ++i) { TupleUtils.createTuple(tupleBuilder, tuple, fieldSerdes, s1.get(i), s2.get(i), i, s3.get(i), s4.get(i)); Assert.assertTrue(bf.contains(tuple, hashes));
