[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 <bamousaa@gmail.com>
Sonar-Qube: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Tested-by: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Contrib: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Integration-Tests: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
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 @@
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 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 {
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 boolean isExclusiveLatchNodes() {
return exclusiveLatchNodes;
}
-
- public boolean isBloomFilterAware() {
- return false;
- }
}
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 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.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 @@
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 @@
private ITupleReference frameTuple;
private List<ILSMComponent> operationalComponents;
+ private final long[] hashes = BloomFilter.createHashArray();
+
public LSMBTreePointSearchCursor(ILSMIndexOperationContext opCtx) {
this.opCtx = opCtx;
}
@@ -71,6 +74,9 @@
}
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 @@
rangeCursors[i].reset();
}
}
- rangeCursors = null;
nextHasBeenCalled = false;
foundTuple = false;
} finally {
@@ -161,6 +166,7 @@
// object creation: should be relatively low
rangeCursors = new BTreeRangeSearchCursor[numBTrees];
btreeAccessors = new BTreeAccessor[numBTrees];
+ bloomFilters = new BloomFilter[numBTrees];
}
includeMutableComponent = false;
@@ -169,8 +175,7 @@
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 @@
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] =
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 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.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 @@
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 @@
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 @@
buddyBtreeCursors = new BTreeRangeSearchCursor[numberOfTrees];
btreeAccessors = new BTreeAccessor[numberOfTrees];
buddyBtreeAccessors = new BTreeAccessor[numberOfTrees];
+ buddyBtreeBloomFilters = new BloomFilter[numberOfTrees];
}
includeMutableComponent = false;
@@ -99,7 +102,7 @@
// 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 @@
}
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) {
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 @@
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 @@
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 @@
try {
if (buddyBtreeCursors[i].hasNext()) {
killerTupleFound = true;
- break;
}
} finally {
buddyBtreeCursors[i].close();
@@ -115,13 +118,13 @@
@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() {
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;
- }
-}
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 @@
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 @@
// 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 @@
// 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 @@
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 @@
}
return false;
}
+
}
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 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 @@
// 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 @@
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 @@
// 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 @@
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()) {
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 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.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 @@
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 @@
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 @@
btreeCursors = new BTreeRangeSearchCursor[numberOfTrees];
rtreeAccessors = new RTreeAccessor[numberOfTrees];
btreeAccessors = new BTreeAccessor[numberOfTrees];
+ bloomFilters = new BloomFilter[numberOfTrees];
}
includeMutableComponent = false;
@@ -102,7 +104,7 @@
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 @@
}
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(
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 @@
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 @@
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 @@
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 @@
try {
if (btreeCursors[i].hasNext()) {
killerTupleFound = true;
- break;
}
} finally {
btreeCursors[i].close();
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 @@
// 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 @@
}
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));