- Fixed the r-tree usch that latches are released in case of failures.
- Fixed an offset bug in the r-tree frame.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_btree_updates_next@692 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
index 0486496..e23bbc2 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
@@ -35,7 +35,7 @@
public abstract class RTreeNSMFrame extends TreeIndexNSMFrame implements
IRTreeFrame {
protected static final int pageNsnOff = smFlagOff + 1;
- protected static final int rightPageOff = pageNsnOff + 4;
+ protected static final int rightPageOff = pageNsnOff + 8;
protected ITreeIndexTupleReference[] tuples;
protected ITreeIndexTupleReference cmpFrameTuple;
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
index cb553f7..46baae2 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -84,7 +84,7 @@
this.cmp = cmp;
this.freePageManager = freePageManager;
this.interiorFrameFactory = interiorFrameFactory;
- this.leafFrameFactory = leafFrameFactory;
+ this.leafFrameFactory = leafFrameFactory;
globalNsn = new AtomicLong();
this.treeLatch = new ReentrantReadWriteLock(true);
this.diskOrderScanPredicate = new SearchPredicate(null, cmp);
@@ -242,13 +242,12 @@
fileId = -1;
}
- @Override
- public RTreeOpContext createOpContext(IndexOp op) {
- return new RTreeOpContext(op,
- (IRTreeLeafFrame) leafFrameFactory.createFrame(),
- (IRTreeInteriorFrame) interiorFrameFactory.createFrame(),
- freePageManager.getMetaDataFrameFactory().createFrame(), 8);
- }
+ @Override
+ public RTreeOpContext createOpContext(IndexOp op) {
+ return new RTreeOpContext(op, (IRTreeLeafFrame) leafFrameFactory.createFrame(),
+ (IRTreeInteriorFrame) interiorFrameFactory.createFrame(), freePageManager.getMetaDataFrameFactory()
+ .createFrame(), 8);
+ }
@Override
public void insert(ITupleReference tuple, IIndexOpContext ictx) throws HyracksDataException, TreeIndexException {
@@ -292,115 +291,142 @@
public ICachedPage findLeaf(RTreeOpContext ctx) throws HyracksDataException {
int pageId = rootPage;
boolean writeLatched = false;
+ boolean readLatched = false;
+ boolean succeed = false;
ICachedPage node = null;
boolean isLeaf = false;
long pageLsn = 0, parentLsn = 0;
- while (true) {
- if (!writeLatched) {
- node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
- incrementPins();
- ctx.interiorFrame.setPage(node);
- isLeaf = ctx.interiorFrame.isLeaf();
- if (isLeaf) {
- node.acquireWriteLatch();
- incrementWriteLatchesAcquired();
- writeLatched = true;
+ try {
- if (!ctx.interiorFrame.isLeaf()) {
+ while (true) {
+ if (!writeLatched) {
+ node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ incrementPins();
+ ctx.interiorFrame.setPage(node);
+ isLeaf = ctx.interiorFrame.isLeaf();
+ if (isLeaf) {
+ node.acquireWriteLatch();
+ writeLatched = true;
+ incrementWriteLatchesAcquired();
+
+ if (!ctx.interiorFrame.isLeaf()) {
+ node.releaseWriteLatch();
+ writeLatched = false;
+ incrementWriteLatchesReleased();
+ bufferCache.unpin(node);
+ incrementUnpins();
+ continue;
+ }
+ } else {
+ // Be optimistic and grab read latch first. We will swap
+ // it
+ // to write latch if we need to enlarge the best child
+ // tuple.
+ node.acquireReadLatch();
+ readLatched = true;
+ incrementReadLatchesAcquired();
+ }
+ }
+
+ if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
+ // Concurrent split detected, go back to parent and
+ // re-choose
+ // the best child
+ if (writeLatched) {
node.releaseWriteLatch();
+ writeLatched = false;
incrementWriteLatchesReleased();
bufferCache.unpin(node);
incrementUnpins();
- writeLatched = false;
- continue;
+ } else {
+ node.releaseReadLatch();
+ readLatched = false;
+ incrementReadLatchesReleased();
+ bufferCache.unpin(node);
+ incrementUnpins();
}
- } else {
- // Be optimistic and grab read latch first. We will swap it
- // to write latch if we need to enlarge the best child
- // tuple.
- node.acquireReadLatch();
- incrementReadLatchesAcquired();
- }
- }
- if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
- // Concurrent split detected, go back to parent and re-choose
- // the best child
- if (writeLatched) {
+ pageId = ctx.pathList.getLastPageId();
+ if (pageId != rootPage) {
+ parentLsn = ctx.pathList.getPageLsn(ctx.pathList.size() - 2);
+ }
+ ctx.pathList.moveLast();
+ continue;
+ }
+
+ pageLsn = ctx.interiorFrame.getPageLsn();
+ ctx.pathList.add(pageId, pageLsn, -1);
+
+ if (!isLeaf) {
+ // findBestChild must be called *before* getBestChildPageId
+ ctx.interiorFrame.findBestChild(ctx.getTuple(), cmp);
+ int childPageId = ctx.interiorFrame.getBestChildPageId();
+
+ if (!writeLatched) {
+ node.releaseReadLatch();
+ readLatched = false;
+ incrementReadLatchesReleased();
+ // TODO: do we need to un-pin and pin again?
+ bufferCache.unpin(node);
+ incrementUnpins();
+
+ node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ incrementPins();
+ node.acquireWriteLatch();
+ writeLatched = true;
+ incrementWriteLatchesAcquired();
+ ctx.interiorFrame.setPage(node);
+
+ if (ctx.interiorFrame.getPageLsn() != pageLsn) {
+ // The page was changed while we unlocked it; thus,
+ // retry (re-choose best child)
+
+ ctx.pathList.moveLast();
+ continue;
+ }
+ }
+
+ // We don't need to reset the frameTuple because it is
+ // already pointing to the best child
+ ctx.interiorFrame.enlarge(ctx.getTuple(), cmp);
+
node.releaseWriteLatch();
+ writeLatched = false;
incrementWriteLatchesReleased();
bufferCache.unpin(node);
incrementUnpins();
- writeLatched = false;
+
+ pageId = childPageId;
+ parentLsn = pageLsn;
} else {
- node.releaseReadLatch();
- incrementReadLatchesReleased();
- bufferCache.unpin(node);
- incrementUnpins();
+ ctx.leafFrame.setPage(node);
+ succeed = true;
+ return node;
}
-
- pageId = ctx.pathList.getLastPageId();
- if (pageId != rootPage) {
- parentLsn = ctx.pathList.getPageLsn(ctx.pathList.size() - 2);
- }
- ctx.pathList.moveLast();
- continue;
}
-
- pageLsn = ctx.interiorFrame.getPageLsn();
- ctx.pathList.add(pageId, pageLsn, -1);
-
- if (!isLeaf) {
- // findBestChild must be called *before* getBestChildPageId
- ctx.interiorFrame.findBestChild(ctx.getTuple(), cmp);
- int childPageId = ctx.interiorFrame.getBestChildPageId();
-
- if (!writeLatched) {
+ } finally {
+ if (!succeed) {
+ if (readLatched) {
node.releaseReadLatch();
+ readLatched = false;
incrementReadLatchesReleased();
- // TODO: do we need to un-pin and pin again?
bufferCache.unpin(node);
incrementUnpins();
-
- node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
- incrementPins();
- node.acquireWriteLatch();
- incrementWriteLatchesAcquired();
- ctx.interiorFrame.setPage(node);
- writeLatched = true;
-
- if (ctx.interiorFrame.getPageLsn() != pageLsn) {
- // The page was changed while we unlocked it; thus,
- // retry (re-choose best child)
-
- ctx.pathList.moveLast();
- continue;
- }
+ } else if (writeLatched) {
+ node.releaseWriteLatch();
+ writeLatched = false;
+ incrementWriteLatchesReleased();
+ bufferCache.unpin(node);
+ incrementUnpins();
}
-
- // We don't need to reset the frameTuple because it is
- // already pointing to the best child
- ctx.interiorFrame.enlarge(ctx.getTuple(), cmp);
-
- node.releaseWriteLatch();
- incrementWriteLatchesReleased();
- bufferCache.unpin(node);
- incrementUnpins();
- writeLatched = false;
-
- pageId = childPageId;
- parentLsn = pageLsn;
- } else {
- ctx.leafFrame.setPage(node);
- return node;
}
}
}
private void insertTuple(ICachedPage node, int pageId, ITupleReference tuple, RTreeOpContext ctx, boolean isLeaf)
throws HyracksDataException, TreeIndexException {
- FrameOpSpaceStatus spaceStatus;
+ FrameOpSpaceStatus spaceStatus;
if (!isLeaf) {
spaceStatus = ctx.interiorFrame.hasSpaceInsert(tuple);
} else {
@@ -526,53 +552,70 @@
}
public void updateParentForInsert(RTreeOpContext ctx) throws HyracksDataException, TreeIndexException {
+ boolean writeLatched = false;
int parentId = ctx.pathList.getLastPageId();
ICachedPage parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
incrementPins();
parentNode.acquireWriteLatch();
+ writeLatched = true;
incrementWriteLatchesAcquired();
ctx.interiorFrame.setPage(parentNode);
boolean foundParent = true;
- if (ctx.interiorFrame.getPageLsn() != ctx.pathList.getLastPageLsn()) {
- foundParent = false;
- while (true) {
- if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), cmp) != -1) {
- // found the parent
- foundParent = true;
- break;
+ try {
+
+ if (ctx.interiorFrame.getPageLsn() != ctx.pathList.getLastPageLsn()) {
+ foundParent = false;
+ while (true) {
+ if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), cmp) != -1) {
+ // found the parent
+ foundParent = true;
+ break;
+ }
+ int rightPage = ctx.interiorFrame.getRightPage();
+ parentNode.releaseWriteLatch();
+ writeLatched = false;
+ incrementWriteLatchesReleased();
+ bufferCache.unpin(parentNode);
+ incrementUnpins();
+
+ if (rightPage == -1) {
+ break;
+ }
+
+ parentId = rightPage;
+ parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
+ incrementPins();
+ parentNode.acquireWriteLatch();
+ writeLatched = true;
+ incrementWriteLatchesAcquired();
+ ctx.interiorFrame.setPage(parentNode);
}
- int rightPage = ctx.interiorFrame.getRightPage();
+ }
+ if (foundParent) {
+ ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), -1, cmp);
+ insertTuple(parentNode, parentId, ctx.splitKey.getRightTuple(), ctx, ctx.interiorFrame.isLeaf());
+ ctx.pathList.moveLast();
+
parentNode.releaseWriteLatch();
+ writeLatched = false;
incrementWriteLatchesReleased();
bufferCache.unpin(parentNode);
incrementUnpins();
+ return;
+ }
- if (rightPage == -1) {
- break;
- }
-
- parentId = rightPage;
- parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
- incrementPins();
- parentNode.acquireWriteLatch();
- incrementWriteLatchesAcquired();
- ctx.interiorFrame.setPage(parentNode);
+ } finally {
+ if (writeLatched) {
+ parentNode.releaseWriteLatch();
+ writeLatched = false;
+ incrementWriteLatchesReleased();
+ bufferCache.unpin(parentNode);
+ incrementUnpins();
}
}
- if (foundParent) {
- ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), -1, cmp);
- insertTuple(parentNode, parentId, ctx.splitKey.getRightTuple(), ctx, ctx.interiorFrame.isLeaf());
- ctx.pathList.moveLast();
-
- parentNode.releaseWriteLatch();
- incrementWriteLatchesReleased();
- bufferCache.unpin(parentNode);
- incrementUnpins();
- return;
- }
-
- // very rare situation when the there is a root split, do an exhaustive
+ // very rare situation when the there is a root split, do an
+ // exhaustive
// breadth-first traversal looking for the parent tuple
ctx.pathList.clear();
@@ -582,48 +625,57 @@
}
public void findPath(RTreeOpContext ctx) throws HyracksDataException {
+ boolean readLatched = false;
int pageId = rootPage;
int parentIndex = -1;
long parentLsn = 0;
long pageLsn;
int pageIndex;
+ ICachedPage node = null;
ctx.traverseList.add(pageId, -1, parentIndex);
- while (!ctx.traverseList.isLast()) {
- pageId = ctx.traverseList.getFirstPageId();
- parentIndex = ctx.traverseList.getFirstPageIndex();
+ try {
+ while (!ctx.traverseList.isLast()) {
+ pageId = ctx.traverseList.getFirstPageId();
+ parentIndex = ctx.traverseList.getFirstPageIndex();
- ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
- incrementPins();
- node.acquireReadLatch();
- incrementReadLatchesAcquired();
- ctx.interiorFrame.setPage(node);
- pageLsn = ctx.interiorFrame.getPageLsn();
- pageIndex = ctx.traverseList.first();
- ctx.traverseList.setPageLsn(pageIndex, pageLsn);
+ node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ incrementPins();
+ node.acquireReadLatch();
+ readLatched = true;
+ incrementReadLatchesAcquired();
+ ctx.interiorFrame.setPage(node);
+ pageLsn = ctx.interiorFrame.getPageLsn();
+ pageIndex = ctx.traverseList.first();
+ ctx.traverseList.setPageLsn(pageIndex, pageLsn);
- ctx.traverseList.moveFirst();
+ ctx.traverseList.moveFirst();
- if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
- int rightPage = ctx.interiorFrame.getRightPage();
- if (rightPage != -1) {
- ctx.traverseList.add(rightPage, -1, parentIndex);
+ if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
+ int rightPage = ctx.interiorFrame.getRightPage();
+ if (rightPage != -1) {
+ ctx.traverseList.add(rightPage, -1, parentIndex);
+ }
}
- }
- parentLsn = pageLsn;
+ parentLsn = pageLsn;
- if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), ctx.traverseList, pageIndex, cmp) != -1) {
- fillPath(ctx, pageIndex);
-
+ if (ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), ctx.traverseList, pageIndex, cmp) != -1) {
+ fillPath(ctx, pageIndex);
+ return;
+ }
node.releaseReadLatch();
+ readLatched = false;
incrementReadLatchesReleased();
bufferCache.unpin(node);
incrementUnpins();
- return;
}
- node.releaseReadLatch();
- incrementReadLatchesReleased();
- bufferCache.unpin(node);
- incrementUnpins();
+ } finally {
+ if (readLatched) {
+ node.releaseReadLatch();
+ readLatched = false;
+ incrementReadLatchesReleased();
+ bufferCache.unpin(node);
+ incrementUnpins();
+ }
}
}
@@ -665,70 +717,85 @@
}
public void updateParentForDelete(RTreeOpContext ctx) throws HyracksDataException {
+ boolean writeLatched = false;
int parentId = ctx.pathList.getLastPageId();
ICachedPage parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
incrementPins();
parentNode.acquireWriteLatch();
+ writeLatched = true;
incrementWriteLatchesAcquired();
ctx.interiorFrame.setPage(parentNode);
boolean foundParent = true;
int tupleIndex = -1;
- if (ctx.interiorFrame.getPageLsn() != ctx.pathList.getLastPageLsn()) {
- foundParent = false;
- while (true) {
- tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), cmp);
- if (tupleIndex != -1) {
- // found the parent
- foundParent = true;
- break;
+ try {
+ if (ctx.interiorFrame.getPageLsn() != ctx.pathList.getLastPageLsn()) {
+ foundParent = false;
+ while (true) {
+ tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), cmp);
+ if (tupleIndex != -1) {
+ // found the parent
+ foundParent = true;
+ break;
+ }
+ int rightPage = ctx.interiorFrame.getRightPage();
+ parentNode.releaseWriteLatch();
+ writeLatched = false;
+ incrementWriteLatchesReleased();
+ bufferCache.unpin(parentNode);
+ incrementUnpins();
+
+ if (rightPage == -1) {
+ break;
+ }
+
+ parentId = rightPage;
+ parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
+ incrementPins();
+ parentNode.acquireWriteLatch();
+ writeLatched = true;
+ incrementWriteLatchesAcquired();
+ ctx.interiorFrame.setPage(parentNode);
}
- int rightPage = ctx.interiorFrame.getRightPage();
+ }
+ if (foundParent) {
+ if (tupleIndex == -1) {
+ tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), cmp);
+ }
+ boolean recomputeMBR = ctx.interiorFrame.recomputeMBR(ctx.splitKey.getLeftTuple(), tupleIndex, cmp);
+
+ if (recomputeMBR) {
+ ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), tupleIndex, cmp);
+ ctx.pathList.moveLast();
+
+ incrementGlobalNsn();
+ ctx.interiorFrame.setPageLsn(getGlobalNsn());
+
+ ctx.splitKey.reset();
+ if (!ctx.pathList.isEmpty()) {
+ ctx.interiorFrame.computeMBR(ctx.splitKey);
+ ctx.splitKey.setLeftPage(parentId);
+ }
+ } else {
+ ctx.pathList.moveLast();
+ ctx.splitKey.reset();
+ }
+
parentNode.releaseWriteLatch();
+ writeLatched = false;
incrementWriteLatchesReleased();
bufferCache.unpin(parentNode);
incrementUnpins();
-
- if (rightPage == -1) {
- break;
- }
-
- parentId = rightPage;
- parentNode = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, parentId), false);
- incrementPins();
- parentNode.acquireWriteLatch();
- incrementWriteLatchesAcquired();
- ctx.interiorFrame.setPage(parentNode);
+ return;
}
- }
- if (foundParent) {
- if (tupleIndex == -1) {
- tupleIndex = ctx.interiorFrame.findTupleByPointer(ctx.splitKey.getLeftTuple(), cmp);
+ } finally {
+ if (writeLatched) {
+ parentNode.releaseWriteLatch();
+ writeLatched = false;
+ incrementWriteLatchesReleased();
+ bufferCache.unpin(parentNode);
+ incrementUnpins();
}
- boolean recomputeMBR = ctx.interiorFrame.recomputeMBR(ctx.splitKey.getLeftTuple(), tupleIndex, cmp);
-
- if (recomputeMBR) {
- ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), tupleIndex, cmp);
- ctx.pathList.moveLast();
-
- incrementGlobalNsn();
- ctx.interiorFrame.setPageLsn(getGlobalNsn());
-
- ctx.splitKey.reset();
- if (!ctx.pathList.isEmpty()) {
- ctx.interiorFrame.computeMBR(ctx.splitKey);
- ctx.splitKey.setLeftPage(parentId);
- }
- } else {
- ctx.pathList.moveLast();
- ctx.splitKey.reset();
- }
-
- parentNode.releaseWriteLatch();
- incrementWriteLatchesReleased();
- bufferCache.unpin(parentNode);
- incrementUnpins();
- return;
}
// very rare situation when the there is a root split, do an exhaustive
@@ -741,87 +808,116 @@
}
public int findTupleToDelete(RTreeOpContext ctx) throws HyracksDataException {
-
+ boolean writeLatched = false;
+ boolean readLatched = false;
+ boolean succeed = false;
+ ICachedPage node = null;
ctx.traverseList.add(rootPage, -1, -1);
ctx.pathList.add(rootPage, -1, ctx.traverseList.size() - 1);
- while (!ctx.pathList.isEmpty()) {
- int pageId = ctx.pathList.getLastPageId();
- long parentLsn = ctx.pathList.getLastPageLsn();
- int pageIndex = ctx.pathList.getLastPageIndex();
- ctx.pathList.moveLast();
- ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
- incrementPins();
- node.acquireReadLatch();
- incrementReadLatchesAcquired();
- ctx.interiorFrame.setPage(node);
- boolean isLeaf = ctx.interiorFrame.isLeaf();
- long pageLsn = ctx.interiorFrame.getPageLsn();
- int parentIndex = ctx.traverseList.getPageIndex(pageIndex);
- ctx.traverseList.setPageLsn(pageIndex, pageLsn);
+ try {
+ while (!ctx.pathList.isEmpty()) {
+ int pageId = ctx.pathList.getLastPageId();
+ long parentLsn = ctx.pathList.getLastPageLsn();
+ int pageIndex = ctx.pathList.getLastPageIndex();
+ ctx.pathList.moveLast();
+ node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ incrementPins();
+ node.acquireReadLatch();
+ readLatched = true;
+ incrementReadLatchesAcquired();
+ ctx.interiorFrame.setPage(node);
+ boolean isLeaf = ctx.interiorFrame.isLeaf();
+ long pageLsn = ctx.interiorFrame.getPageLsn();
+ int parentIndex = ctx.traverseList.getPageIndex(pageIndex);
+ ctx.traverseList.setPageLsn(pageIndex, pageLsn);
- if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
- // Concurrent split detected, we need to visit the right page
- int rightPage = ctx.interiorFrame.getRightPage();
- if (rightPage != -1) {
- ctx.traverseList.add(rightPage, -1, parentIndex);
- ctx.pathList.add(rightPage, parentLsn, ctx.traverseList.size() - 1);
- }
- }
-
- if (!isLeaf) {
- for (int i = 0; i < ctx.interiorFrame.getTupleCount(); i++) {
- int childPageId = ctx.interiorFrame.getChildPageIdIfIntersect(ctx.tuple, i, cmp);
- if (childPageId != -1) {
- ctx.traverseList.add(childPageId, -1, pageIndex);
- ctx.pathList.add(childPageId, pageLsn, ctx.traverseList.size() - 1);
+ if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
+ // Concurrent split detected, we need to visit the right
+ // page
+ int rightPage = ctx.interiorFrame.getRightPage();
+ if (rightPage != -1) {
+ ctx.traverseList.add(rightPage, -1, parentIndex);
+ ctx.pathList.add(rightPage, parentLsn, ctx.traverseList.size() - 1);
}
}
- } else {
- ctx.leafFrame.setPage(node);
- int tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, cmp);
- if (tupleIndex != -1) {
- node.releaseReadLatch();
- incrementReadLatchesReleased();
- bufferCache.unpin(node);
- incrementUnpins();
-
- node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
- incrementPins();
- node.acquireWriteLatch();
- incrementWriteLatchesAcquired();
+ if (!isLeaf) {
+ for (int i = 0; i < ctx.interiorFrame.getTupleCount(); i++) {
+ int childPageId = ctx.interiorFrame.getChildPageIdIfIntersect(ctx.tuple, i, cmp);
+ if (childPageId != -1) {
+ ctx.traverseList.add(childPageId, -1, pageIndex);
+ ctx.pathList.add(childPageId, pageLsn, ctx.traverseList.size() - 1);
+ }
+ }
+ } else {
ctx.leafFrame.setPage(node);
+ int tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, cmp);
+ if (tupleIndex != -1) {
- if (ctx.leafFrame.getPageLsn() != pageLsn) {
- // The page was changed while we unlocked it
+ node.releaseReadLatch();
+ readLatched = false;
+ incrementReadLatchesReleased();
+ bufferCache.unpin(node);
+ incrementUnpins();
- tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, cmp);
- if (tupleIndex == -1) {
- ctx.traverseList.add(pageId, -1, parentIndex);
- ctx.pathList.add(pageId, parentLsn, ctx.traverseList.size() - 1);
+ node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ incrementPins();
+ node.acquireWriteLatch();
+ writeLatched = true;
+ incrementWriteLatchesAcquired();
+ ctx.leafFrame.setPage(node);
- node.releaseWriteLatch();
- incrementWriteLatchesReleased();
- bufferCache.unpin(node);
- incrementUnpins();
- continue;
+ if (ctx.leafFrame.getPageLsn() != pageLsn) {
+ // The page was changed while we unlocked it
+
+ tupleIndex = ctx.leafFrame.findTupleIndex(ctx.tuple, cmp);
+ if (tupleIndex == -1) {
+ ctx.traverseList.add(pageId, -1, parentIndex);
+ ctx.pathList.add(pageId, parentLsn, ctx.traverseList.size() - 1);
+
+ node.releaseWriteLatch();
+ writeLatched = false;
+ incrementWriteLatchesReleased();
+ bufferCache.unpin(node);
+ incrementUnpins();
+ continue;
+ } else {
+ ctx.pathList.clear();
+ fillPath(ctx, pageIndex);
+ succeed = true;
+ return tupleIndex;
+ }
} else {
ctx.pathList.clear();
fillPath(ctx, pageIndex);
+ succeed = true;
return tupleIndex;
}
- } else {
- ctx.pathList.clear();
- fillPath(ctx, pageIndex);
- return tupleIndex;
}
}
+ node.releaseReadLatch();
+ readLatched = false;
+ incrementReadLatchesReleased();
+ bufferCache.unpin(node);
+ incrementUnpins();
}
- node.releaseReadLatch();
- incrementReadLatchesReleased();
- bufferCache.unpin(node);
- incrementUnpins();
+ } finally {
+ if (!succeed) {
+ if (readLatched) {
+ node.releaseReadLatch();
+ readLatched = false;
+ incrementReadLatchesReleased();
+ bufferCache.unpin(node);
+ incrementUnpins();
+ } else if (writeLatched) {
+ node.releaseWriteLatch();
+ writeLatched = false;
+ incrementWriteLatchesReleased();
+ bufferCache.unpin(node);
+ incrementUnpins();
+ }
+ }
}
return -1;
}
@@ -885,8 +981,9 @@
throw new HyracksDataException("Trying to bulk-load RTree but RTree has already been loaded.");
}
- BulkLoadContext ctx = new BulkLoadContext(fillFactor, (IRTreeFrame) leafFrameFactory.createFrame(), (IRTreeFrame) interiorFrameFactory.createFrame(),
- freePageManager.getMetaDataFrameFactory().createFrame());
+ BulkLoadContext ctx = new BulkLoadContext(fillFactor, (IRTreeFrame) leafFrameFactory.createFrame(),
+ (IRTreeFrame) interiorFrameFactory.createFrame(), freePageManager.getMetaDataFrameFactory()
+ .createFrame());
return ctx;
}
@@ -915,12 +1012,18 @@
ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false);
page.acquireReadLatch();
- cursor.setBufferCache(bufferCache);
- cursor.setFileId(fileId);
- cursor.setCurrentPageId(currentPageId);
- cursor.setMaxPageId(maxPageId);
- ctx.cursorInitialState.setPage(page);
- cursor.open(ctx.cursorInitialState, diskOrderScanPredicate);
+ try {
+ cursor.setBufferCache(bufferCache);
+ cursor.setFileId(fileId);
+ cursor.setCurrentPageId(currentPageId);
+ cursor.setMaxPageId(maxPageId);
+ ctx.cursorInitialState.setPage(page);
+ cursor.open(ctx.cursorInitialState, diskOrderScanPredicate);
+ } catch (Exception e) {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ throw new HyracksDataException(e);
+ }
}
@Override
@@ -937,4 +1040,4 @@
public IndexType getIndexType() {
return IndexType.RTREE;
}
-}
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
index a138212..16b96b2 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
@@ -30,188 +30,193 @@
public class RTreeSearchCursor implements ITreeIndexCursor {
- private int fileId = -1;
- private ICachedPage page = null;
- private IRTreeInteriorFrame interiorFrame = null;
- private IRTreeLeafFrame leafFrame = null;
- private IBufferCache bufferCache = null;
+ private int fileId = -1;
+ private ICachedPage page = null;
+ private IRTreeInteriorFrame interiorFrame = null;
+ private IRTreeLeafFrame leafFrame = null;
+ private IBufferCache bufferCache = null;
- private SearchPredicate pred;
- private PathList pathList;
- private int rootPage;
- ITupleReference searchKey;
+ private SearchPredicate pred;
+ private PathList pathList;
+ private int rootPage;
+ ITupleReference searchKey;
- private int tupleIndex = 0;
- private int tupleIndexInc = 0;
+ private int tupleIndex = 0;
+ private int tupleIndexInc = 0;
- private MultiComparator cmp;
+ private MultiComparator cmp;
- private ITreeIndexTupleReference frameTuple;
- private boolean readLatched = false;
+ private ITreeIndexTupleReference frameTuple;
+ private boolean readLatched = false;
- private int pin = 0;
- private int unpin = 0;
+ private int pin = 0;
+ private int unpin = 0;
- public RTreeSearchCursor(IRTreeInteriorFrame interiorFrame,
- IRTreeLeafFrame leafFrame) {
- this.interiorFrame = interiorFrame;
- this.leafFrame = leafFrame;
- this.frameTuple = leafFrame.createTupleReference();
- }
+ public RTreeSearchCursor(IRTreeInteriorFrame interiorFrame, IRTreeLeafFrame leafFrame) {
+ this.interiorFrame = interiorFrame;
+ this.leafFrame = leafFrame;
+ this.frameTuple = leafFrame.createTupleReference();
+ }
- @Override
- public void close() throws Exception {
- if (readLatched) {
- page.releaseReadLatch();
- bufferCache.unpin(page);
- readLatched = false;
- }
- tupleIndex = 0;
- tupleIndexInc = 0;
- page = null;
- pathList = null;
- }
+ @Override
+ public void close() throws Exception {
+ if (readLatched) {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ readLatched = false;
+ }
+ tupleIndex = 0;
+ tupleIndexInc = 0;
+ page = null;
+ pathList = null;
+ }
- public ITupleReference getTuple() {
- return frameTuple;
- }
+ public ITupleReference getTuple() {
+ return frameTuple;
+ }
- @Override
- public ICachedPage getPage() {
- return page;
- }
+ @Override
+ public ICachedPage getPage() {
+ return page;
+ }
- public boolean fetchNextLeafPage() throws HyracksDataException {
- if (readLatched) {
- page.releaseReadLatch();
- bufferCache.unpin(page);
- unpin++;
- readLatched = false;
- }
- while (!pathList.isEmpty()) {
- int pageId = pathList.getLastPageId();
- long parentLsn = pathList.getLastPageLsn();
- pathList.moveLast();
- ICachedPage node = bufferCache.pin(
- BufferedFileHandle.getDiskPageId(fileId, pageId), false);
- pin++;
- node.acquireReadLatch();
- readLatched = true;
- interiorFrame.setPage(node);
- boolean isLeaf = interiorFrame.isLeaf();
- long pageLsn = interiorFrame.getPageLsn();
+ public boolean fetchNextLeafPage() throws HyracksDataException {
+ boolean succeed = false;
+ if (readLatched) {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ unpin++;
+ readLatched = false;
+ }
- if (pageId != rootPage && parentLsn < interiorFrame.getPageNsn()) {
- // Concurrent split detected, we need to visit the right page
- int rightPage = interiorFrame.getRightPage();
- if (rightPage != -1) {
- pathList.add(rightPage, parentLsn, -1);
- }
- }
+ while (!pathList.isEmpty()) {
+ int pageId = pathList.getLastPageId();
+ long parentLsn = pathList.getLastPageLsn();
+ pathList.moveLast();
+ ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ pin++;
+ node.acquireReadLatch();
+ readLatched = true;
+ try {
+ interiorFrame.setPage(node);
+ boolean isLeaf = interiorFrame.isLeaf();
+ long pageLsn = interiorFrame.getPageLsn();
- if (!isLeaf) {
- for (int i = 0; i < interiorFrame.getTupleCount(); i++) {
- int childPageId = interiorFrame.getChildPageIdIfIntersect(
- searchKey, i, cmp);
- if (childPageId != -1) {
- pathList.add(childPageId, pageLsn, -1);
- }
- }
- } else {
- page = node;
- leafFrame.setPage(page);
- tupleIndex = 0;
- return true;
- }
- node.releaseReadLatch();
- readLatched = false;
- bufferCache.unpin(node);
- unpin++;
- }
- return false;
- }
+ if (pageId != rootPage && parentLsn < interiorFrame.getPageNsn()) {
+ // Concurrent split detected, we need to visit the right
+ // page
+ int rightPage = interiorFrame.getRightPage();
+ if (rightPage != -1) {
+ pathList.add(rightPage, parentLsn, -1);
+ }
+ }
- @Override
- public boolean hasNext() throws Exception {
- if (page == null) {
- return false;
- }
+ if (!isLeaf) {
+ for (int i = 0; i < interiorFrame.getTupleCount(); i++) {
+ int childPageId = interiorFrame.getChildPageIdIfIntersect(searchKey, i, cmp);
+ if (childPageId != -1) {
+ pathList.add(childPageId, pageLsn, -1);
+ }
+ }
+ } else {
+ page = node;
+ leafFrame.setPage(page);
+ tupleIndex = 0;
+ succeed = true;
+ return true;
+ }
+ } finally {
+ if (!succeed) {
+ if (readLatched) {
+ node.releaseReadLatch();
+ readLatched = false;
+ bufferCache.unpin(node);
+ unpin++;
+ }
+ }
+ }
+ }
+ return false;
+ }
- if (tupleIndex == leafFrame.getTupleCount()) {
- if (!fetchNextLeafPage()) {
- return false;
- }
- }
+ @Override
+ public boolean hasNext() throws Exception {
+ if (page == null) {
+ return false;
+ }
- do {
- for (int i = tupleIndex; i < leafFrame.getTupleCount(); i++) {
- if (leafFrame.intersect(searchKey, i, cmp)) {
- frameTuple.resetByTupleIndex(leafFrame, i);
- tupleIndexInc = i + 1;
- return true;
- }
- }
- } while (fetchNextLeafPage());
- return false;
- }
+ if (tupleIndex == leafFrame.getTupleCount()) {
+ if (!fetchNextLeafPage()) {
+ return false;
+ }
+ }
- @Override
- public void next() throws Exception {
- tupleIndex = tupleIndexInc;
- }
+ do {
+ for (int i = tupleIndex; i < leafFrame.getTupleCount(); i++) {
+ if (leafFrame.intersect(searchKey, i, cmp)) {
+ frameTuple.resetByTupleIndex(leafFrame, i);
+ tupleIndexInc = i + 1;
+ return true;
+ }
+ }
+ } while (fetchNextLeafPage());
+ return false;
+ }
- @Override
- public void open(ICursorInitialState initialState,
- ISearchPredicate searchPred) throws Exception {
- // in case open is called multiple times without closing
- if (this.page != null) {
- this.page.releaseReadLatch();
- readLatched = false;
- bufferCache.unpin(this.page);
- pathList.clear();
- }
+ @Override
+ public void next() throws Exception {
+ tupleIndex = tupleIndexInc;
+ }
- pathList = ((RTreeCursorInitialState) initialState).getPathList();
- rootPage = ((RTreeCursorInitialState) initialState).getRootPage();
+ @Override
+ public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws Exception {
+ // in case open is called multiple times without closing
+ if (this.page != null) {
+ this.page.releaseReadLatch();
+ readLatched = false;
+ bufferCache.unpin(this.page);
+ pathList.clear();
+ }
- pred = (SearchPredicate) searchPred;
- cmp = pred.getLowKeyComparator();
- searchKey = pred.getSearchKey();
+ pathList = ((RTreeCursorInitialState) initialState).getPathList();
+ rootPage = ((RTreeCursorInitialState) initialState).getRootPage();
- int maxFieldPos = cmp.getKeyFieldCount() / 2;
- for (int i = 0; i < maxFieldPos; i++) {
- int j = maxFieldPos + i;
- int c = cmp.getComparators()[i].compare(searchKey.getFieldData(i),
- searchKey.getFieldStart(i), searchKey.getFieldLength(i),
- searchKey.getFieldData(j), searchKey.getFieldStart(j),
- searchKey.getFieldLength(j));
- if (c > 0) {
- throw new IllegalArgumentException(
- "The low key point has larger coordinates than the high key point.");
- }
- }
+ pred = (SearchPredicate) searchPred;
+ cmp = pred.getLowKeyComparator();
+ searchKey = pred.getSearchKey();
- pathList.add(this.rootPage, -1, -1);
- tupleIndex = 0;
- fetchNextLeafPage();
- }
+ int maxFieldPos = cmp.getKeyFieldCount() / 2;
+ for (int i = 0; i < maxFieldPos; i++) {
+ int j = maxFieldPos + i;
+ int c = cmp.getComparators()[i].compare(searchKey.getFieldData(i), searchKey.getFieldStart(i),
+ searchKey.getFieldLength(i), searchKey.getFieldData(j), searchKey.getFieldStart(j),
+ searchKey.getFieldLength(j));
+ if (c > 0) {
+ throw new IllegalArgumentException("The low key point has larger coordinates than the high key point.");
+ }
+ }
- @Override
- public void reset() {
- try {
- close();
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
+ pathList.add(this.rootPage, -1, -1);
+ tupleIndex = 0;
+ fetchNextLeafPage();
+ }
- @Override
- public void setBufferCache(IBufferCache bufferCache) {
- this.bufferCache = bufferCache;
- }
+ @Override
+ public void reset() {
+ try {
+ close();
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
- @Override
- public void setFileId(int fileId) {
- this.fileId = fileId;
- }
+ @Override
+ public void setBufferCache(IBufferCache bufferCache) {
+ this.bufferCache = bufferCache;
+ }
+
+ @Override
+ public void setFileId(int fileId) {
+ this.fileId = fileId;
+ }
}
\ No newline at end of file