Optimized point search queries in LSM-BTree to open cursors sequentially (if they get the green light from their corresponding bloom filters). This optimization can also improve secondary-to-primary index lookup.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@2895 123451ca-8445-de46-9d55-352943316053
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 677b467..3596466 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
@@ -17,7 +17,6 @@
import java.io.File;
import java.util.List;
-import java.util.ListIterator;
import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
@@ -44,7 +43,6 @@
import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
-import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
@@ -270,7 +268,7 @@
private boolean insert(ITupleReference tuple, LSMBTreeOpContext ctx) throws HyracksDataException, IndexException {
MultiComparator comparator = MultiComparator.createIgnoreFieldLength(mutableComponent.getBTree()
.getComparatorFactories());
- LSMBTreeRangeSearchCursor searchCursor = new LSMBTreeRangeSearchCursor(ctx);
+ LSMBTreePointSearchCursor searchCursor = new LSMBTreePointSearchCursor(ctx);
IIndexCursor memCursor = new BTreeRangeSearchCursor(ctx.memBTreeOpCtx.leafFrame, false);
RangePredicate predicate = new RangePredicate(tuple, tuple, true, true, comparator, comparator);
@@ -311,57 +309,15 @@
public void search(ILSMIndexOperationContext ictx, IIndexCursor cursor, ISearchPredicate pred)
throws HyracksDataException, IndexException {
LSMBTreeOpContext ctx = (LSMBTreeOpContext) ictx;
- LSMBTreeRangeSearchCursor lsmTreeCursor = (LSMBTreeRangeSearchCursor) cursor;
List<ILSMComponent> operationalComponents = ctx.getComponentHolder();
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
- .getBloomFilterKeyFields().length) {
- if (ctx.bloomFilterCmps.compare(btreePred.getLowKey(), btreePred.getHighKey()) == 0) {
- isPointSearch = true;
- }
- }
- }
- }
- }
boolean includeMutableComponent = operationalComponents.get(0) == mutableComponent;
LSMBTreeCursorInitialState initialState = new LSMBTreeCursorInitialState(numBTrees, insertLeafFrameFactory,
- ctx.cmp, includeMutableComponent, isPointSearch, lsmHarness, ctx.memBTreeAccessor, pred,
+ ctx.cmp, ctx.bloomFilterCmp, includeMutableComponent, lsmHarness, ctx.memBTreeAccessor, pred,
ctx.searchCallback, operationalComponents);
- lsmTreeCursor.open(initialState, pred);
-
- int cursorIx;
- ListIterator<ILSMComponent> diskBTreesIter = operationalComponents.listIterator();
- if (includeMutableComponent) {
- // Open cursor of in-memory BTree at index 0.
- ctx.memBTreeAccessor.search(lsmTreeCursor.getCursor(0), pred);
- // Skip 0 because it is the in-memory BTree.
- cursorIx = 1;
- diskBTreesIter.next();
- } else {
- cursorIx = 0;
- }
-
- // Open cursors of on-disk BTrees.
- int numDiskComponents = includeMutableComponent ? numBTrees - 1 : numBTrees;
- ITreeIndexAccessor[] diskBTreeAccessors = new ITreeIndexAccessor[numDiskComponents];
- int diskBTreeIx = 0;
- while (diskBTreesIter.hasNext()) {
- BTree diskBTree = (BTree) ((LSMBTreeImmutableComponent) diskBTreesIter.next()).getBTree();
- diskBTreeAccessors[diskBTreeIx] = diskBTree.createAccessor(NoOpOperationCallback.INSTANCE,
- NoOpOperationCallback.INSTANCE);
- diskBTreeAccessors[diskBTreeIx].search(lsmTreeCursor.getCursor(cursorIx), pred);
- cursorIx++;
- diskBTreeIx++;
- }
- lsmTreeCursor.initPriorityQueue();
+ cursor.open(initialState, pred);
}
@Override
@@ -611,7 +567,7 @@
@Override
public IIndexCursor createSearchCursor() {
- return new LSMBTreeRangeSearchCursor(ctx);
+ return new LSMBTreeSearchCursor(ctx);
}
public MultiComparator getMultiComparator() {
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 d59e0d7..2b7029b 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
@@ -32,8 +32,8 @@
private final int numBTrees;
private final ITreeIndexFrameFactory leafFrameFactory;
private MultiComparator cmp;
+ private final MultiComparator bloomFilterCmp;
private final boolean includeMemComponent;
- private final boolean pointSearch;
private final ILSMHarness lsmHarness;
private final IIndexAccessor memBtreeAccessor;
@@ -43,19 +43,19 @@
private final List<ILSMComponent> operationalComponents;
public LSMBTreeCursorInitialState(int numBTrees, ITreeIndexFrameFactory leafFrameFactory, MultiComparator cmp,
- boolean includeMemComponent, boolean pointSearch, ILSMHarness lsmHarness, IIndexAccessor memBtreeAccessor,
- ISearchPredicate predicate, ISearchOperationCallback searchCallback,
+ MultiComparator bloomFilterCmp, boolean includeMemComponent, ILSMHarness lsmHarness,
+ IIndexAccessor memBtreeAccessor, ISearchPredicate predicate, ISearchOperationCallback searchCallback,
List<ILSMComponent> operationalComponents) {
this.numBTrees = numBTrees;
this.leafFrameFactory = leafFrameFactory;
this.cmp = cmp;
+ this.bloomFilterCmp = bloomFilterCmp;
this.includeMemComponent = includeMemComponent;
this.lsmHarness = lsmHarness;
this.searchCallback = searchCallback;
this.memBtreeAccessor = memBtreeAccessor;
this.predicate = predicate;
this.operationalComponents = operationalComponents;
- this.pointSearch = pointSearch;
}
public int getNumBTrees() {
@@ -79,10 +79,6 @@
return includeMemComponent;
}
- public boolean isPointSearch() {
- return pointSearch;
- }
-
public ILSMHarness getLSMHarness() {
return lsmHarness;
}
@@ -109,6 +105,10 @@
return predicate;
}
+ public MultiComparator getBloomFilterComparator() {
+ return bloomFilterCmp;
+ }
+
@Override
public MultiComparator getOriginalKeyComparator() {
return cmp;
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeOpContext.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeOpContext.java
index 8edd9b9..9400d2d 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeOpContext.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeOpContext.java
@@ -42,7 +42,7 @@
public BTreeOpContext memBTreeOpCtx;
public IndexOperation op;
public final MultiComparator cmp;
- public final MultiComparator bloomFilterCmps;
+ public final MultiComparator bloomFilterCmp;
public final IModificationOperationCallback modificationCallback;
public final ISearchOperationCallback searchCallback;
private final List<ILSMComponent> componentHolder;
@@ -57,7 +57,7 @@
this.cmp = null;
}
- bloomFilterCmps = MultiComparator.createIgnoreFieldLength(memBTree.getComparatorFactories(), 0,
+ bloomFilterCmp = MultiComparator.createIgnoreFieldLength(memBTree.getComparatorFactories(), 0,
numBloomFilterKeyFields);
this.memBTree = memBTree;
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java
new file mode 100644
index 0000000..d1aa6a8
--- /dev/null
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java
@@ -0,0 +1,224 @@
+/*
+ * Copyright 2009-2010 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.btree.impls;
+
+import java.util.ListIterator;
+import java.util.concurrent.atomic.AtomicInteger;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponent;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMHarness;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIndexOperationContext;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMTreeTupleReference;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.BloomFilterAwareBTreePointSearchCursor;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public class LSMBTreePointSearchCursor implements ITreeIndexCursor {
+
+ private IIndexCursor[] rangeCursors;
+ private final ILSMIndexOperationContext opCtx;
+ private ISearchOperationCallback searchCallback;
+ private RangePredicate predicate;
+ private IIndexAccessor memBTreeAccessor;
+ private boolean includeMemComponent;
+ private int numBTrees;
+ private IIndexAccessor[] bTreeAccessors;
+ private AtomicInteger searcherRefCount;
+ private ILSMHarness lsmHarness;
+ private boolean nextHasBeenCalled;
+ private boolean foundTuple;
+ private ITupleReference frameTuple;
+
+ public LSMBTreePointSearchCursor(ILSMIndexOperationContext opCtx) {
+ this.opCtx = opCtx;
+ }
+
+ @Override
+ public boolean hasNext() throws HyracksDataException, IndexException {
+ if (nextHasBeenCalled) {
+ return false;
+ } else if (foundTuple) {
+ return true;
+ }
+ boolean reconciled = false;
+ for (int i = 0; i < numBTrees; ++i) {
+ bTreeAccessors[i].search(rangeCursors[i], predicate);
+ if (rangeCursors[i].hasNext()) {
+ rangeCursors[i].next();
+ if (reconciled || searchCallback.proceed(predicate.getLowKey())) {
+ // if proceed is successful, then there's no need for doing the "unlatch dance"
+ if (((ILSMTreeTupleReference) rangeCursors[i].getTuple()).isAntimatter()) {
+ return false;
+ } else {
+ frameTuple = rangeCursors[i].getTuple();
+ foundTuple = true;
+ return true;
+ }
+ }
+ if (i == 0 && includeMemComponent) {
+ // unlatch/unpin
+ rangeCursors[i].reset();
+ searchCallback.reconcile(predicate.getLowKey());
+ reconciled = true;
+
+ // retraverse
+ try {
+ memBTreeAccessor.search(rangeCursors[i], predicate);
+ } catch (IndexException e) {
+ throw new HyracksDataException(e);
+ }
+ if (rangeCursors[i].hasNext()) {
+ rangeCursors[i].next();
+ if (((ILSMTreeTupleReference) rangeCursors[i].getTuple()).isAntimatter()) {
+ return false;
+ } else {
+ frameTuple = rangeCursors[i].getTuple();
+ foundTuple = true;
+ return true;
+ }
+ }
+ } else {
+ frameTuple = rangeCursors[i].getTuple();
+ searchCallback.reconcile(frameTuple);
+ foundTuple = true;
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ @Override
+ public void reset() throws HyracksDataException, IndexException {
+ if (rangeCursors != null) {
+ for (int i = 0; i < rangeCursors.length; ++i) {
+ rangeCursors[i].reset();
+ }
+ }
+ rangeCursors = null;
+ nextHasBeenCalled = false;
+ foundTuple = false;
+ if (searcherRefCount != null) {
+ lsmHarness.endSearch(opCtx);
+ }
+ }
+
+ @Override
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+ LSMBTreeCursorInitialState lsmInitialState = (LSMBTreeCursorInitialState) initialState;
+ includeMemComponent = lsmInitialState.getIncludeMemComponent();
+ lsmHarness = lsmInitialState.getLSMHarness();
+ searchCallback = lsmInitialState.getSearchOperationCallback();
+ memBTreeAccessor = lsmInitialState.getMemBTreeAccessor();
+ predicate = (RangePredicate) lsmInitialState.getSearchPredicate();
+
+ numBTrees = lsmInitialState.getNumBTrees();
+ rangeCursors = new IIndexCursor[numBTrees];
+ 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) lsmInitialState.getOperationalComponents().get(i)).getBloomFilter());
+ }
+
+ bTreeAccessors = new IIndexAccessor[numBTrees];
+ int cursorIx = 0;
+ ListIterator<ILSMComponent> btreesIter = lsmInitialState.getOperationalComponents().listIterator();
+ if (includeMemComponent) {
+ bTreeAccessors[cursorIx] = memBTreeAccessor;
+ ++cursorIx;
+ btreesIter.next();
+ }
+
+ while (btreesIter.hasNext()) {
+ BTree diskBTree = ((LSMBTreeImmutableComponent) btreesIter.next()).getBTree();
+ bTreeAccessors[cursorIx] = diskBTree.createAccessor(NoOpOperationCallback.INSTANCE,
+ NoOpOperationCallback.INSTANCE);
+ cursorIx++;
+ }
+ nextHasBeenCalled = false;
+ foundTuple = false;
+ }
+
+ @Override
+ public void next() throws HyracksDataException {
+ nextHasBeenCalled = true;
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ if (lsmHarness != null) {
+ try {
+ for (int i = 0; i < rangeCursors.length; i++) {
+ rangeCursors[i].close();
+ }
+ rangeCursors = null;
+ } finally {
+ lsmHarness.endSearch(opCtx);
+ }
+ }
+ nextHasBeenCalled = false;
+ foundTuple = false;
+ }
+
+ @Override
+ public ITupleReference getTuple() {
+ return frameTuple;
+ }
+
+ @Override
+ public ICachedPage getPage() {
+ // do nothing
+ return null;
+ }
+
+ @Override
+ public void setBufferCache(IBufferCache bufferCache) {
+ // do nothing
+
+ }
+
+ @Override
+ public void setFileId(int fileId) {
+ // do nothing
+
+ }
+
+ @Override
+ public boolean exclusiveLatchNodes() {
+ return false;
+ }
+}
\ No newline at end of file
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 e1ad93a..ff01ce8 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
@@ -16,21 +16,26 @@
package edu.uci.ics.hyracks.storage.am.lsm.btree.impls;
import java.util.Iterator;
+import java.util.ListIterator;
import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
import edu.uci.ics.hyracks.storage.am.common.api.IIndexAccessor;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexCursor;
import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponent;
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 {
@@ -128,7 +133,8 @@
}
@Override
- public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException,
+ IndexException {
LSMBTreeCursorInitialState lsmInitialState = (LSMBTreeCursorInitialState) initialState;
cmp = lsmInitialState.getOriginalKeyComparator();
includeMemComponent = lsmInitialState.getIncludeMemComponent();
@@ -142,27 +148,35 @@
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);
- }
+ rangeCursors = new IIndexCursor[numBTrees];
+ for (int i = 0; i < numBTrees; i++) {
+ IBTreeLeafFrame leafFrame = (IBTreeLeafFrame) lsmInitialState.getLeafFrameFactory().createFrame();
+ rangeCursors[i] = new BTreeRangeSearchCursor(leafFrame, false);
+ }
+ setPriorityQueueComparator();
+
+ int cursorIx = 0;
+ ListIterator<ILSMComponent> btreesIter = operationalComponents.listIterator();
+ if (includeMemComponent) {
+ // Open cursor of in-memory BTree at index 0.
+ memBTreeAccessor.search(rangeCursors[cursorIx], searchPred);
+ // Skip 0 because it is the in-memory BTree.
+ ++cursorIx;
+ btreesIter.next();
}
- setPriorityQueueComparator();
+ // Open cursors of on-disk BTrees.
+ int numDiskComponents = includeMemComponent ? numBTrees - 1 : numBTrees;
+ ITreeIndexAccessor[] diskBTreeAccessors = new ITreeIndexAccessor[numDiskComponents];
+ int diskBTreeIx = 0;
+ while (btreesIter.hasNext()) {
+ BTree diskBTree = (BTree) ((LSMBTreeImmutableComponent) btreesIter.next()).getBTree();
+ diskBTreeAccessors[diskBTreeIx] = diskBTree.createAccessor(NoOpOperationCallback.INSTANCE,
+ NoOpOperationCallback.INSTANCE);
+ diskBTreeAccessors[diskBTreeIx].search(rangeCursors[cursorIx], searchPred);
+ cursorIx++;
+ diskBTreeIx++;
+ }
+ initPriorityQueue();
}
}
\ No newline at end of file
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeSearchCursor.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeSearchCursor.java
new file mode 100644
index 0000000..b15b88c
--- /dev/null
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeSearchCursor.java
@@ -0,0 +1,128 @@
+/*
+ * Copyright 2009-2010 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.btree.impls;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
+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.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
+
+public class LSMBTreeSearchCursor implements ITreeIndexCursor {
+
+ public enum LSMBTreeSearchType {
+ POINT,
+ RANGE
+ }
+
+ private final LSMBTreePointSearchCursor pointCursor;
+ private final LSMBTreeRangeSearchCursor rangeCursor;
+ private ITreeIndexCursor currentCursor;
+
+ public LSMBTreeSearchCursor(ILSMIndexOperationContext opCtx) {
+ pointCursor = new LSMBTreePointSearchCursor(opCtx);
+ rangeCursor = new LSMBTreeRangeSearchCursor(opCtx);
+ }
+
+ @Override
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws IndexException,
+ HyracksDataException {
+
+ LSMBTreeCursorInitialState lsmInitialState = (LSMBTreeCursorInitialState) initialState;
+
+ LSMBTreeSearchType searchType = LSMBTreeSearchType.RANGE;
+ RangePredicate btreePred = (RangePredicate) searchPred;
+ if (btreePred.getLowKey() != null && btreePred.getHighKey() != null) {
+ if (btreePred.isLowKeyInclusive() && btreePred.isHighKeyInclusive()) {
+ if (btreePred.getLowKeyComparator().getKeyFieldCount() == btreePred.getHighKeyComparator()
+ .getKeyFieldCount()) {
+ if (btreePred.getLowKeyComparator().getKeyFieldCount() == lsmInitialState
+ .getBloomFilterComparator().getKeyFieldCount()) {
+ if (lsmInitialState.getBloomFilterComparator().compare(btreePred.getLowKey(),
+ btreePred.getHighKey()) == 0) {
+ searchType = LSMBTreeSearchType.POINT;
+ }
+ }
+ }
+ }
+ }
+ switch (searchType) {
+ case POINT:
+ currentCursor = pointCursor;
+ break;
+ case RANGE:
+ currentCursor = rangeCursor;
+ break;
+ default:
+ throw new HyracksDataException("Wrong search type");
+ }
+ currentCursor.open(lsmInitialState, searchPred);
+ }
+
+ @Override
+ public boolean hasNext() throws HyracksDataException, IndexException {
+ return currentCursor.hasNext();
+ }
+
+ @Override
+ public void next() throws HyracksDataException {
+ currentCursor.next();
+ }
+
+ @Override
+ public void close() throws HyracksDataException {
+ currentCursor.close();
+ }
+
+ @Override
+ public void reset() throws HyracksDataException, IndexException {
+ if (currentCursor != null) {
+ currentCursor.reset();
+ }
+ }
+
+ @Override
+ public ITupleReference getTuple() {
+ return currentCursor.getTuple();
+ }
+
+ @Override
+ public ICachedPage getPage() {
+ return currentCursor.getPage();
+ }
+
+ @Override
+ public void setBufferCache(IBufferCache bufferCache) {
+ currentCursor.setBufferCache(bufferCache);
+ }
+
+ @Override
+ public void setFileId(int fileId) {
+ currentCursor.setFileId(fileId);
+
+ }
+
+ @Override
+ public boolean exclusiveLatchNodes() {
+ return currentCursor.exclusiveLatchNodes();
+ }
+
+}
\ No newline at end of file