Removed left-sibling link from BTree leaves.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@1094 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
index a079527..3c5bce8 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
@@ -27,10 +27,6 @@
public int getNextLeaf();
- public void setPrevLeaf(int prevPage);
-
- public int getPrevLeaf();
-
public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference pageTuple, MultiComparator cmp,
FindTupleMode ftm, FindTupleNoExactMatchPolicy ftp) throws HyracksDataException;
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
index 6e9ad81..a82203f 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
@@ -58,8 +58,7 @@
protected static final int uncompressedTupleCountOff = smFlagOff + 1; // 22
protected static final int prefixTupleCountOff = uncompressedTupleCountOff + 4; // 26
- protected static final int prevLeafOff = prefixTupleCountOff + 4; // 30
- protected static final int nextLeafOff = prevLeafOff + 4; // 34
+ protected static final int nextLeafOff = prefixTupleCountOff + 4; // 30
protected ICachedPage page = null;
protected ByteBuffer buf = null;
@@ -343,7 +342,6 @@
buf.putInt(prefixTupleCountOff, 0);
buf.put(levelOff, level);
buf.put(smFlagOff, (byte) 0);
- buf.putInt(prevLeafOff, -1);
buf.putInt(nextLeafOff, -1);
}
@@ -402,7 +400,6 @@
strBuilder.append("smFlagOff: " + smFlagOff + "\n");
strBuilder.append("uncompressedTupleCountOff: " + uncompressedTupleCountOff + "\n");
strBuilder.append("prefixTupleCountOff: " + prefixTupleCountOff + "\n");
- strBuilder.append("prevLeafOff: " + prevLeafOff + "\n");
strBuilder.append("nextLeafOff: " + nextLeafOff + "\n");
return strBuilder.toString();
}
@@ -658,20 +655,10 @@
}
@Override
- public void setPrevLeaf(int page) {
- buf.putInt(prevLeafOff, page);
- }
-
- @Override
public int getNextLeaf() {
return buf.getInt(nextLeafOff);
}
- @Override
- public int getPrevLeaf() {
- return buf.getInt(prevLeafOff);
- }
-
public int getUncompressedTupleCount() {
return buf.getInt(uncompressedTupleCountOff);
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
index 40a7670..4770307 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
@@ -32,8 +32,7 @@
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
public class BTreeNSMLeafFrame extends TreeIndexNSMFrame implements IBTreeLeafFrame {
- protected static final int prevLeafOff = smFlagOff + 1;
- protected static final int nextLeafOff = prevLeafOff + 4;
+ protected static final int nextLeafOff = smFlagOff + 1;
private MultiComparator cmp;
public BTreeNSMLeafFrame(ITreeIndexTupleWriter tupleWriter) {
@@ -43,7 +42,6 @@
@Override
public void initBuffer(byte level) {
super.initBuffer(level);
- buf.putInt(prevLeafOff, -1);
buf.putInt(nextLeafOff, -1);
}
@@ -53,21 +51,11 @@
}
@Override
- public void setPrevLeaf(int page) {
- buf.putInt(prevLeafOff, page);
- }
-
- @Override
public int getNextLeaf() {
return buf.getInt(nextLeafOff);
}
@Override
- public int getPrevLeaf() {
- return buf.getInt(prevLeafOff);
- }
-
- @Override
public int findInsertTupleIndex(ITupleReference tuple) throws TreeIndexException {
int tupleIndex = slotManager.findTupleIndex(tuple, frameTuple, cmp, FindTupleMode.EXCLUSIVE_ERROR_IF_EXISTS,
FindTupleNoExactMatchPolicy.HIGHER_KEY);
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
index 3e155a0..b90a89a 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
@@ -26,6 +26,7 @@
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
+import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNonExistentKeyException;
import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNotUpdateableException;
import edu.uci.ics.hyracks.storage.am.btree.frames.BTreeNSMInteriorFrame;
import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
@@ -103,16 +104,6 @@
fileId = -1;
}
- private void addFreePages(BTreeOpContext ctx) throws HyracksDataException {
- for (int i = 0; i < ctx.freePages.size(); i++) {
- // Root page is special, never add it to free pages.
- if (ctx.freePages.get(i) != rootPage) {
- freePageManager.addFreePage(ctx.metaFrame, ctx.freePages.get(i));
- }
- }
- ctx.freePages.clear();
- }
-
private void diskOrderScan(ITreeIndexCursor icursor, BTreeOpContext ctx) throws HyracksDataException {
TreeDiskOrderScanCursor cursor = (TreeDiskOrderScanCursor) icursor;
ctx.reset();
@@ -204,39 +195,26 @@
false);
leftNode.acquireWriteLatch();
try {
- ICachedPage rightNode = bufferCache.pin(
- BufferedFileHandle.getDiskPageId(fileId, ctx.splitKey.getRightPage()), false);
- rightNode.acquireWriteLatch();
+ int newLeftId = freePageManager.getFreePage(ctx.metaFrame);
+ ICachedPage newLeftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, newLeftId), true);
+ newLeftNode.acquireWriteLatch();
try {
- int newLeftId = freePageManager.getFreePage(ctx.metaFrame);
- ICachedPage newLeftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, newLeftId), true);
- newLeftNode.acquireWriteLatch();
- try {
- // Copy left child to new left child.
- System.arraycopy(leftNode.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0, newLeftNode
- .getBuffer().capacity());
- ctx.interiorFrame.setPage(newLeftNode);
- ctx.interiorFrame.setSmFlag(false);
- // Change sibling pointer if children are leaves.
- ctx.leafFrame.setPage(rightNode);
- if (ctx.leafFrame.isLeaf()) {
- ctx.leafFrame.setPrevLeaf(newLeftId);
- }
- // Initialize new root (leftNode becomes new root).
- ctx.interiorFrame.setPage(leftNode);
- ctx.interiorFrame.initBuffer((byte) (ctx.leafFrame.getLevel() + 1));
- // Will be cleared later in unsetSmPages.
- ctx.interiorFrame.setSmFlag(true);
- ctx.splitKey.setLeftPage(newLeftId);
- int targetTupleIndex = ctx.interiorFrame.findInsertTupleIndex(ctx.splitKey.getTuple());
- ctx.interiorFrame.insert(ctx.splitKey.getTuple(), targetTupleIndex);
- } finally {
- newLeftNode.releaseWriteLatch();
- bufferCache.unpin(newLeftNode);
- }
+ // Copy left child to new left child.
+ System.arraycopy(leftNode.getBuffer().array(), 0, newLeftNode.getBuffer().array(), 0, newLeftNode
+ .getBuffer().capacity());
+ ctx.interiorFrame.setPage(newLeftNode);
+ ctx.interiorFrame.setSmFlag(false);
+ // Initialize new root (leftNode becomes new root).
+ ctx.interiorFrame.setPage(leftNode);
+ ctx.interiorFrame.initBuffer((byte) (ctx.leafFrame.getLevel() + 1));
+ // Will be cleared later in unsetSmPages.
+ ctx.interiorFrame.setSmFlag(true);
+ ctx.splitKey.setLeftPage(newLeftId);
+ int targetTupleIndex = ctx.interiorFrame.findInsertTupleIndex(ctx.splitKey.getTuple());
+ ctx.interiorFrame.insert(ctx.splitKey.getTuple(), targetTupleIndex);
} finally {
- rightNode.releaseWriteLatch();
- bufferCache.unpin(rightNode);
+ newLeftNode.releaseWriteLatch();
+ bufferCache.unpin(newLeftNode);
}
} finally {
leftNode.releaseWriteLatch();
@@ -264,18 +242,10 @@
}
// Split key propagated?
if (ctx.splitKey.getBuffer() != null) {
- if (ctx.op == IndexOp.DELETE) {
- // Reset level of root to zero.
- initRoot(ctx.leafFrame, false);
- } else {
- // Insert or update op. Create a new root.
- createNewRoot(ctx);
- }
+ // Insert or update op. Create a new root.
+ createNewRoot(ctx);
}
unsetSmPages(ctx);
- if (ctx.op == IndexOp.DELETE) {
- addFreePages(ctx);
- }
repeatOp = false;
}
}
@@ -341,67 +311,43 @@
}
private boolean performLeafSplit(int pageId, ITupleReference tuple, BTreeOpContext ctx) throws Exception {
- // Lock is released in unsetSmPages(), after sm has fully completed.
+ // Lock is released in unsetSmPages(), after sm has fully completed.
if (!treeLatch.writeLock().tryLock()) {
- return true;
+ return true;
}
- int rightSiblingPageId = ctx.leafFrame.getNextLeaf();
- ICachedPage rightSibling = null;
- if (rightSiblingPageId > 0) {
- rightSibling = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightSiblingPageId),
- false);
- }
+ int rightPageId = freePageManager.getFreePage(ctx.metaFrame);
+ ICachedPage rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightPageId),
+ true);
+ rightNode.acquireWriteLatch();
try {
- int rightPageId = freePageManager.getFreePage(ctx.metaFrame);
- ICachedPage rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, rightPageId),
- true);
- rightNode.acquireWriteLatch();
- try {
- IBTreeLeafFrame rightFrame = ctx.createLeafFrame();
- rightFrame.setPage(rightNode);
- rightFrame.initBuffer((byte) 0);
- rightFrame.setMultiComparator(cmp);
- ctx.leafFrame.split(rightFrame, tuple, ctx.splitKey);
+ IBTreeLeafFrame rightFrame = ctx.createLeafFrame();
+ rightFrame.setPage(rightNode);
+ rightFrame.initBuffer((byte) 0);
+ rightFrame.setMultiComparator(cmp);
+ ctx.leafFrame.split(rightFrame, tuple, ctx.splitKey);
- ctx.smPages.add(pageId);
- ctx.smPages.add(rightPageId);
- ctx.leafFrame.setSmFlag(true);
- rightFrame.setSmFlag(true);
+ ctx.smPages.add(pageId);
+ ctx.smPages.add(rightPageId);
+ ctx.leafFrame.setSmFlag(true);
+ rightFrame.setSmFlag(true);
- rightFrame.setNextLeaf(ctx.leafFrame.getNextLeaf());
- rightFrame.setPrevLeaf(pageId);
- ctx.leafFrame.setNextLeaf(rightPageId);
+ rightFrame.setNextLeaf(ctx.leafFrame.getNextLeaf());
+ ctx.leafFrame.setNextLeaf(rightPageId);
- // TODO: we just use increasing numbers as pageLsn,
- // we
- // should tie this together with the LogManager and
- // TransactionManager
- rightFrame.setPageLsn(rightFrame.getPageLsn() + 1);
- ctx.leafFrame.setPageLsn(ctx.leafFrame.getPageLsn() + 1);
+ // TODO: we just use increasing numbers as pageLsn,
+ // we
+ // should tie this together with the LogManager and
+ // TransactionManager
+ rightFrame.setPageLsn(rightFrame.getPageLsn() + 1);
+ ctx.leafFrame.setPageLsn(ctx.leafFrame.getPageLsn() + 1);
- ctx.splitKey.setPages(pageId, rightPageId);
-
- if (rightSibling != null) {
- rightSibling.acquireWriteLatch();
- try {
- // Reuse rightFrame for modification.
- rightFrame.setPage(rightSibling);
- rightFrame.setPrevLeaf(rightPageId);
- } finally {
- rightSibling.releaseWriteLatch();
- }
- }
- } finally {
- rightNode.releaseWriteLatch();
- bufferCache.unpin(rightNode);
- }
+ ctx.splitKey.setPages(pageId, rightPageId);
} catch (Exception e) {
treeLatch.writeLock().unlock();
throw e;
} finally {
- if (rightSibling != null) {
- bufferCache.unpin(rightSibling);
- }
+ rightNode.releaseWriteLatch();
+ bufferCache.unpin(rightNode);
}
return false;
}
@@ -507,134 +453,20 @@
}
private boolean deleteLeaf(ICachedPage node, int pageId, ITupleReference tuple, BTreeOpContext ctx) throws Exception {
+ // Simply delete the tuple, and don't do any rebalancing.
+ // This means that there could be underflow, even an empty page that is
+ // pointed to by an interior node.
ctx.leafFrame.setPage(node);
+ if (ctx.leafFrame.getTupleCount() == 0) {
+ throw new BTreeNonExistentKeyException("Trying to delete a tuple with a nonexistent key in leaf node.");
+ }
int tupleIndex = ctx.leafFrame.findDeleteTupleIndex(tuple);
-
- // Will this leaf become empty?
- if (ctx.leafFrame.getTupleCount() > 1) {
- // Leaf will not become empty.
- ctx.leafFrame.delete(tuple, tupleIndex);
- node.releaseWriteLatch();
- bufferCache.unpin(node);
- return false;
- }
-
- // Leaf will become empty.
- IBTreeLeafFrame siblingFrame = (IBTreeLeafFrame) leafFrameFactory.createFrame();
- siblingFrame.setMultiComparator(cmp);
- ICachedPage leftNode = null;
- ICachedPage rightNode = null;
- int nextLeaf = ctx.leafFrame.getNextLeaf();
- int prevLeaf = ctx.leafFrame.getPrevLeaf();
- // Try to get the tree latch, if it's already taken, then restart this operation
- // to avoid latch deadlock.
- if (!treeLatch.writeLock().tryLock()) {
- return true;
- }
- try {
- if (prevLeaf > 0) {
- leftNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, prevLeaf), false);
- }
- try {
- if (nextLeaf > 0) {
- rightNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, nextLeaf), false);
- }
- try {
- try {
- ctx.leafFrame.delete(tuple, tupleIndex);
- // To propagate the deletion we only need to make the
- // splitKey != null.
- // Reuse data to identify which key to delete in the parent.
- ctx.splitKey.initData(1);
- } catch (Exception e) {
- // Don't propagate deletion.
- ctx.splitKey.reset();
- throw e;
- }
-
- // TODO: Tie together with logging.
- ctx.leafFrame.setPageLsn(ctx.leafFrame.getPageLsn() + 1);
- ctx.leafFrame.setLevel(freePageManager.getFreePageLevelIndicator());
-
- ctx.smPages.add(pageId);
- ctx.leafFrame.setSmFlag(true);
-
- node.releaseWriteLatch();
- bufferCache.unpin(node);
-
- if (leftNode != null) {
- leftNode.acquireWriteLatch();
- try {
- siblingFrame.setPage(leftNode);
- siblingFrame.setNextLeaf(nextLeaf);
- // TODO: Tie together with logging.
- siblingFrame.setPageLsn(siblingFrame.getPageLsn() + 1);
- } finally {
- leftNode.releaseWriteLatch();
- }
- }
-
- if (rightNode != null) {
- rightNode.acquireWriteLatch();
- try {
- siblingFrame.setPage(rightNode);
- siblingFrame.setPrevLeaf(prevLeaf);
- // TODO: Tie together with logging.
- siblingFrame.setPageLsn(siblingFrame.getPageLsn() + 1);
- } finally {
- rightNode.releaseWriteLatch();
- }
- }
- // Register pageId as a free.
- ctx.freePages.add(pageId);
- } finally {
- if (rightNode != null) {
- bufferCache.unpin(rightNode);
- }
- }
- } finally {
- if (leftNode != null) {
- bufferCache.unpin(leftNode);
- }
- }
- } catch (Exception e) {
- treeLatch.writeLock().unlock();
- throw e;
- }
+ ctx.leafFrame.delete(tuple, tupleIndex);
+ node.releaseWriteLatch();
+ bufferCache.unpin(node);
return false;
}
- private void deleteInterior(ICachedPage node, int pageId, ITupleReference tuple, BTreeOpContext ctx)
- throws Exception {
- ctx.interiorFrame.setPage(node);
-
- int tupleIndex = ctx.interiorFrame.findDeleteTupleIndex(tuple);
-
- // this means there is only a child pointer but no key, this case
- // propagates the split
- if (ctx.interiorFrame.getTupleCount() == 0) {
- ctx.interiorFrame.setPageLsn(ctx.interiorFrame.getPageLsn() + 1); // TODO:
- // tie
- // together
- // with
- // logging
- ctx.leafFrame.setLevel(freePageManager.getFreePageLevelIndicator());
- ctx.smPages.add(pageId);
- ctx.interiorFrame.setSmFlag(true);
- ctx.interiorFrame.setRightmostChildPageId(-1); // this node is
- // completely empty
- // register this pageId as a free page
- ctx.freePages.add(pageId);
-
- } else {
- ctx.interiorFrame.delete(tuple, tupleIndex);
- // TODO: Tie together with logging.
- ctx.interiorFrame.setPageLsn(ctx.interiorFrame.getPageLsn() + 1);
- // Don't propagate deletion.
- ctx.splitKey.reset();
- }
- }
-
private final void acquireLatch(ICachedPage node, BTreeOpContext ctx, boolean isLeaf) {
if (!isLeaf || (ctx.op == IndexOp.SEARCH && !ctx.cursor.exclusiveLatchNodes())) {
node.acquireReadLatch();
@@ -716,19 +548,14 @@
switch (ctx.op) {
case INSERT:
- case UPDATE:
- case DELETE: {
+ case UPDATE: {
// Is there a propagated split key?
if (ctx.splitKey.getBuffer() != null) {
node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
node.acquireWriteLatch();
try {
- if (ctx.op == IndexOp.DELETE) {
- deleteInterior(node, pageId, ctx.pred.getLowKey(), ctx);
- } else {
- // Insert or update op. Both can cause split keys to propagate upwards.
- insertInterior(node, pageId, ctx.splitKey.getTuple(), ctx);
- }
+ // Insert or update op. Both can cause split keys to propagate upwards.
+ insertInterior(node, pageId, ctx.splitKey.getTuple(), ctx);
} finally {
node.releaseWriteLatch();
bufferCache.unpin(node);
@@ -738,6 +565,14 @@
}
break;
}
+
+ case DELETE: {
+ if (ctx.splitKey.getBuffer() != null) {
+ throw new BTreeException("Split key was propagated during delete. Delete allows empty leaf pages.");
+ }
+ break;
+ }
+
default: {
// Do nothing for Search and DiskOrderScan.
break;
@@ -947,7 +782,6 @@
ctx.splitKey.getBuffer().array(), 0);
ctx.splitKey.getTuple().resetByTupleOffset(ctx.splitKey.getBuffer(), 0);
ctx.splitKey.setLeftPage(leafFrontier.pageId);
- int prevPageId = leafFrontier.pageId;
leafFrontier.pageId = freePageManager.getFreePage(ctx.metaFrame);
leafFrame.setNextLeaf(leafFrontier.pageId);
@@ -962,7 +796,6 @@
leafFrontier.page.acquireWriteLatch();
leafFrame.setPage(leafFrontier.page);
leafFrame.initBuffer((byte) 0);
- leafFrame.setPrevLeaf(prevPageId);
}
leafFrame.setPage(leafFrontier.page);
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 5946594..8bf4db3 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
@@ -86,17 +86,20 @@
}
private void fetchNextLeafPage(int nextLeafPage) throws HyracksDataException {
- ICachedPage nextLeaf = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, nextLeafPage), false);
- if (exclusiveLatchNodes) {
- nextLeaf.acquireWriteLatch();
- page.releaseWriteLatch();
- } else {
- nextLeaf.acquireReadLatch();
- page.releaseReadLatch();
- }
- bufferCache.unpin(page);
- page = nextLeaf;
- frame.setPage(page);
+ do {
+ ICachedPage nextLeaf = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, nextLeafPage), false);
+ if (exclusiveLatchNodes) {
+ nextLeaf.acquireWriteLatch();
+ page.releaseWriteLatch();
+ } else {
+ nextLeaf.acquireReadLatch();
+ page.releaseReadLatch();
+ }
+ bufferCache.unpin(page);
+ page = nextLeaf;
+ frame.setPage(page);
+ nextLeafPage = frame.getNextLeaf();
+ } while (frame.getTupleCount() == 0 && nextLeafPage > 0);
}
@Override
@@ -106,7 +109,6 @@
if (nextLeafPage >= 0) {
fetchNextLeafPage(nextLeafPage);
tupleIndex = 0;
-
stopTupleIndex = getHighKeyIndex();
if (stopTupleIndex < 0) {
return false;
@@ -196,7 +198,7 @@
} else {
highKeyFtp = FindTupleNoExactMatchPolicy.LOWER_KEY;
}
-
+
tupleIndex = getLowKeyIndex();
stopTupleIndex = getHighKeyIndex();
tupleIndexInc = 1;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
index 15b63ec..533b5b7 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
@@ -61,7 +61,7 @@
private boolean positionToNextLeaf(boolean skipCurrent)
throws HyracksDataException {
- while ((frame.getLevel() != 0 || skipCurrent) && (currentPageId <= maxPageId)) {
+ while ((frame.getLevel() != 0 || skipCurrent || frame.getTupleCount() == 0) && (currentPageId <= maxPageId)) {
currentPageId++;
ICachedPage nextPage = bufferCache.pin(
@@ -77,10 +77,11 @@
tupleIndex = 0;
skipCurrent = false;
}
- if (currentPageId <= maxPageId)
+ if (currentPageId <= maxPageId) {
return true;
- else
+ } else {
return false;
+ }
}
@Override