Utilized bloom filters in LSM-BTree point search.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree_bloom_filter@2764 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-bloomfilter/src/main/java/edu/uci/ics/hyracks/storage/am/bloomfilter/impls/BloomFilterFactory.java b/hyracks-storage-am-bloomfilter/src/main/java/edu/uci/ics/hyracks/storage/am/bloomfilter/impls/BloomFilterFactory.java
index 8bd419a..645c8bd 100644
--- a/hyracks-storage-am-bloomfilter/src/main/java/edu/uci/ics/hyracks/storage/am/bloomfilter/impls/BloomFilterFactory.java
+++ b/hyracks-storage-am-bloomfilter/src/main/java/edu/uci/ics/hyracks/storage/am/bloomfilter/impls/BloomFilterFactory.java
@@ -34,4 +34,8 @@
public BloomFilter createBloomFiltertInstance(FileReference file) throws HyracksDataException {
return new BloomFilter(bufferCache, fileMapProvider, file, keyFields);
}
+
+ public int[] getKeyFields() {
+ return keyFields;
+ }
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
index 2f2eb43..607e00a 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
@@ -65,7 +65,7 @@
private RangePredicate pred;
private MultiComparator lowKeyCmp;
private MultiComparator highKeyCmp;
- private ITupleReference lowKey;
+ protected ITupleReference lowKey;
private ITupleReference highKey;
public BTreeRangeSearchCursor(IBTreeLeafFrame frame, boolean exclusiveLatchNodes) {
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java
index b557125..b81bbe9 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java
@@ -316,10 +316,24 @@
int numBTrees = operationalComponents.size();
assert numBTrees > 0;
+ boolean isPointSearch = false;
+ RangePredicate btreePred = (RangePredicate) pred;
+ if (btreePred.getLowKey() != null && btreePred.getHighKey() != null) {
+ if (btreePred.isLowKeyInclusive() && btreePred.isHighKeyInclusive()) {
+ if (btreePred.getLowKeyComparator().getKeyFieldCount() == btreePred.getHighKeyComparator()
+ .getKeyFieldCount()) {
+ if (btreePred.getLowKeyComparator().getKeyFieldCount() == componentFactory.getKeyFields().length) {
+ if (ctx.cmp.compare(btreePred.getLowKey(), btreePred.getHighKey()) == 0) {
+ isPointSearch = true;
+ }
+ }
+ }
+ }
+ }
boolean includeMutableComponent = operationalComponents.get(0) == mutableComponent;
LSMBTreeCursorInitialState initialState = new LSMBTreeCursorInitialState(numBTrees, insertLeafFrameFactory,
- ctx.cmp, includeMutableComponent, lsmHarness, ctx.memBTreeAccessor, pred, ctx.searchCallback,
- operationalComponents);
+ ctx.cmp, includeMutableComponent, isPointSearch, lsmHarness, ctx.memBTreeAccessor, pred,
+ ctx.searchCallback, operationalComponents);
lsmTreeCursor.open(initialState, pred);
int cursorIx;
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeCursorInitialState.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeCursorInitialState.java
index 84f1c64..d59e0d7 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeCursorInitialState.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeCursorInitialState.java
@@ -33,6 +33,7 @@
private final ITreeIndexFrameFactory leafFrameFactory;
private MultiComparator cmp;
private final boolean includeMemComponent;
+ private final boolean pointSearch;
private final ILSMHarness lsmHarness;
private final IIndexAccessor memBtreeAccessor;
@@ -42,7 +43,7 @@
private final List<ILSMComponent> operationalComponents;
public LSMBTreeCursorInitialState(int numBTrees, ITreeIndexFrameFactory leafFrameFactory, MultiComparator cmp,
- boolean includeMemComponent, ILSMHarness lsmHarness, IIndexAccessor memBtreeAccessor,
+ boolean includeMemComponent, boolean pointSearch, ILSMHarness lsmHarness, IIndexAccessor memBtreeAccessor,
ISearchPredicate predicate, ISearchOperationCallback searchCallback,
List<ILSMComponent> operationalComponents) {
this.numBTrees = numBTrees;
@@ -54,6 +55,7 @@
this.memBtreeAccessor = memBtreeAccessor;
this.predicate = predicate;
this.operationalComponents = operationalComponents;
+ this.pointSearch = pointSearch;
}
public int getNumBTrees() {
@@ -77,6 +79,10 @@
return includeMemComponent;
}
+ public boolean isPointSearch() {
+ return pointSearch;
+ }
+
public ILSMHarness getLSMHarness() {
return lsmHarness;
}
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeImmutableComponentFactory.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeImmutableComponentFactory.java
index 998072f..fcae42c 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeImmutableComponentFactory.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeImmutableComponentFactory.java
@@ -45,4 +45,8 @@
public IBufferCache getBufferCache() {
return btreeFactory.getBufferCache();
}
+
+ public int[] getKeyFields() {
+ return bloomFilterFactory.getKeyFields();
+ }
}
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
index a96ac81..e1ad93a 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
@@ -30,6 +30,7 @@
import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.BloomFilterAwareBTreePointSearchCursor;
import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMIndexSearchCursor;
public class LSMBTreeRangeSearchCursor extends LSMIndexSearchCursor {
@@ -39,10 +40,10 @@
private ISearchOperationCallback searchCallback;
private RangePredicate predicate;
private IIndexAccessor memBTreeAccessor;
- private ArrayTupleBuilder tupleBuilder;
-
+ private ArrayTupleBuilder tupleBuilder;
+
public LSMBTreeRangeSearchCursor(ILSMIndexOperationContext opCtx) {
- super(opCtx);
+ super(opCtx);
this.copyTuple = new ArrayTupleReference();
this.reusablePred = new RangePredicate(null, null, true, true, null, null);
}
@@ -130,12 +131,6 @@
public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
LSMBTreeCursorInitialState lsmInitialState = (LSMBTreeCursorInitialState) initialState;
cmp = lsmInitialState.getOriginalKeyComparator();
- int numBTrees = lsmInitialState.getNumBTrees();
- rangeCursors = new BTreeRangeSearchCursor[numBTrees];
- for (int i = 0; i < numBTrees; i++) {
- IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) lsmInitialState.getLeafFrameFactory().createFrame();
- rangeCursors[i] = new BTreeRangeSearchCursor(leafFrame, false);
- }
includeMemComponent = lsmInitialState.getIncludeMemComponent();
operationalComponents = lsmInitialState.getOperationalComponents();
lsmHarness = lsmInitialState.getLSMHarness();
@@ -145,6 +140,29 @@
reusablePred.setLowKeyComparator(cmp);
reusablePred.setHighKey(predicate.getHighKey(), predicate.isHighKeyInclusive());
reusablePred.setHighKeyComparator(predicate.getHighKeyComparator());
+
+ int numBTrees = lsmInitialState.getNumBTrees();
+ rangeCursors = new BTreeRangeSearchCursor[numBTrees];
+ if (lsmInitialState.isPointSearch()) {
+ int i = 0;
+ if (includeMemComponent) {
+ // No need for a bloom filter for the in-memory BTree.
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) lsmInitialState.getLeafFrameFactory().createFrame();
+ rangeCursors[i] = new BTreeRangeSearchCursor(leafFrame, false);
+ ++i;
+ }
+ for (; i < numBTrees; i++) {
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) lsmInitialState.getLeafFrameFactory().createFrame();
+ rangeCursors[i] = new BloomFilterAwareBTreePointSearchCursor(leafFrame, false,
+ ((LSMBTreeImmutableComponent) operationalComponents.get(i)).getBloomFilter());
+ }
+ } else {
+ for (int i = 0; i < numBTrees; i++) {
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) lsmInitialState.getLeafFrameFactory().createFrame();
+ rangeCursors[i] = new BTreeRangeSearchCursor(leafFrame, false);
+ }
+ }
+
setPriorityQueueComparator();
}
}
\ No newline at end of file
diff --git a/hyracks-storage-am-lsm-common/pom.xml b/hyracks-storage-am-lsm-common/pom.xml
index 6402d63..94ed2f4 100644
--- a/hyracks-storage-am-lsm-common/pom.xml
+++ b/hyracks-storage-am-lsm-common/pom.xml
@@ -33,6 +33,13 @@
</dependency>
<dependency>
<groupId>edu.uci.ics.hyracks</groupId>
+ <artifactId>hyracks-storage-am-bloomfilter</artifactId>
+ <version>0.2.2-SNAPSHOT</version>
+ <type>jar</type>
+ <scope>compile</scope>
+ </dependency>
+ <dependency>
+ <groupId>edu.uci.ics.hyracks</groupId>
<artifactId>hyracks-storage-am-btree</artifactId>
<version>0.2.2-SNAPSHOT</version>
<type>jar</type>
diff --git a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/BloomFilterAwareBTreePointSearchCursor.java b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/BloomFilterAwareBTreePointSearchCursor.java
new file mode 100644
index 0000000..af08bdb
--- /dev/null
+++ b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/BloomFilterAwareBTreePointSearchCursor.java
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed 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 from
+ *
+ * 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 edu.uci.ics.hyracks.storage.am.lsm.common.impls;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.bloomfilter.impls.BloomFilter;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
+
+public class BloomFilterAwareBTreePointSearchCursor extends BTreeRangeSearchCursor {
+ private final 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;
+ }
+}
\ No newline at end of file