asterixdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From luoc...@apache.org
Subject asterixdb git commit: [ASTERIXDB-2128] Fix bloomfilter during index search
Date Sat, 21 Oct 2017 02:33:52 GMT
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 <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>


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 <cluo8@uci.edu>
Authored: Fri Oct 20 16:16:57 2017 -0700
Committer: Luo Chen <cluo8@uci.edu>
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));


Mime
View raw message