Starting to Add BTree utilities like stats gathering.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_indexes@443 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/FieldPrefixNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/FieldPrefixNSMLeafFrame.java
index 21ded44..05d7e2c 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/FieldPrefixNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/FieldPrefixNSMLeafFrame.java
@@ -382,6 +382,11 @@
public boolean isLeaf() {
return buf.get(levelOff) == 0;
}
+
+ @Override
+ public boolean isInterior() {
+ return buf.get(levelOff) > 0;
+ }
@Override
public byte getLevel() {
@@ -658,4 +663,8 @@
return tupleIndex;
}
+ @Override
+ public int getPageHeaderSize() {
+ return nextLeafOff;
+ }
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrame.java
index fdb7337..8498958 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMInteriorFrame.java
@@ -448,4 +448,9 @@
strBuilder.append("\n");
return strBuilder.toString();
}
+
+ @Override
+ public int getPageHeaderSize() {
+ return rightLeafOff;
+ }
}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrame.java
index 49fe895..2acaba6 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/NSMLeafFrame.java
@@ -187,4 +187,9 @@
FindTupleMode ftm, FindTupleNoExactMatchPolicy ftp) {
return slotManager.findTupleIndex(searchKey, pageTuple, cmp, ftm, ftp);
}
+
+ @Override
+ public int getPageHeaderSize() {
+ return nextLeafOff;
+ }
}
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 920b3b3..fa3024d 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
@@ -439,7 +439,7 @@
uselessCompressionTime += (end - start);
uselessCompression++;
-
+
// perform split
splitsByLevel[0]++; // debug
int rightSiblingPageId = ctx.leafFrame.getNextLeaf();
@@ -677,7 +677,7 @@
treeLatchesAcquired++;
try {
- ctx.leafFrame.delete(tuple, cmp, true);
+ ctx.leafFrame.delete(tuple, cmp, true);
// to propagate the deletion we only need to make the
// splitKey != null
// we can reuse data to identify which key to delete in
@@ -695,9 +695,10 @@
// together
// with
// logging
+ ctx.leafFrame.setLevel(freePageManager.getFreePageLevelIndicator());
ctx.smPages.add(pageId);
- ctx.leafFrame.setSmFlag(true);
+ ctx.leafFrame.setSmFlag(true);
node.releaseWriteLatch();
writeLatchesReleased++;
@@ -771,7 +772,8 @@
// tie
// together
// with
- // logging
+ // logging
+ ctx.leafFrame.setLevel(freePageManager.getFreePageLevelIndicator());
ctx.smPages.add(pageId);
ctx.interiorFrame.setSmFlag(true);
ctx.interiorFrame.setRightmostChildPageId(-1); // this node is
@@ -1198,7 +1200,43 @@
loaded = true;
}
-
+
+ public void getBTreeStats(IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
+ ITreeIndexMetaDataFrame metaFrame, BTreeStats btreeStats) throws HyracksDataException {
+
+ btreeStats.begin();
+
+ int maxPageId = freePageManager.getMaxPage(metaFrame);
+ for(int pageId = 0; pageId < maxPageId; pageId++) {
+ ICachedPage page = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+ page.acquireReadLatch();
+ try {
+ metaFrame.setPage(page);
+ leafFrame.setPage(page);
+ interiorFrame.setPage(page);
+
+ if(pageId == rootPage) {
+ btreeStats.addRoot(leafFrame, interiorFrame);
+ } else if(leafFrame.isLeaf()) {
+ double fillFactor = (double)(leafFrame.getBuffer().capacity() - leafFrame.getTotalFreeSpace()) / (double)leafFrame.getBuffer().capacity();
+ System.out.println("FILLFACTOR: " + pageId + " " + fillFactor + " " + leafFrame.getTupleCount());
+ btreeStats.add(leafFrame);
+ } else if(interiorFrame.isInterior()) {
+ btreeStats.add(interiorFrame);
+ } else {
+ System.out.println("META: " + metaFrame.getLevel());
+ btreeStats.add(metaFrame, freePageManager);
+ }
+
+ } finally {
+ page.releaseReadLatch();
+ bufferCache.unpin(page);
+ }
+ }
+
+ btreeStats.end();
+ }
+
public BTreeOpContext createOpContext(TreeIndexOp op, IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame,
ITreeIndexMetaDataFrame metaFrame) {
// TODO: figure out better tree-height hint
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeStats.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeStats.java
new file mode 100644
index 0000000..6f6ba52
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeStats.java
@@ -0,0 +1,143 @@
+package edu.uci.ics.hyracks.storage.am.btree.impls;
+
+import java.text.DecimalFormat;
+
+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.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+
+public class BTreeStats {
+
+ private TreeIndexNodeTypeStats rootStats = new TreeIndexNodeTypeStats();
+ private TreeIndexNodeTypeStats interiorStats = new TreeIndexNodeTypeStats();
+ private TreeIndexNodeTypeStats leafStats = new TreeIndexNodeTypeStats();
+
+ private int freePages = 0;
+ private int metaPages = 0;
+ private int treeLevels = 0;
+
+ public void begin() {
+ rootStats.clear();
+ interiorStats.clear();
+ leafStats.clear();
+ freePages = 0;
+ metaPages = 0;
+ treeLevels = 0;
+ }
+
+ public void addRoot(IBTreeLeafFrame leafFrame, IBTreeInteriorFrame interiorFrame) {
+ treeLevels = leafFrame.getLevel();
+ if(leafFrame.isLeaf()) {
+ rootStats.add(leafFrame);
+ }
+ else {
+ rootStats.add(interiorFrame);
+ }
+ }
+
+ public void add(IBTreeLeafFrame leafFrame) {
+ leafStats.add(leafFrame);
+ }
+
+ public void add(IBTreeInteriorFrame interiorFrame) {
+ interiorStats.add(interiorFrame);
+ }
+
+ public void add(ITreeIndexMetaDataFrame metaFrame, IFreePageManager freePageManager) {
+ if(freePageManager.isFreePage(metaFrame)) {
+ freePages++;
+ } else if(freePageManager.isMetaPage(metaFrame)) {
+ metaPages++;
+ }
+ }
+
+ public void end() {
+ // nothing here currently
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder strBuilder = new StringBuilder();
+ DecimalFormat df = new DecimalFormat("#####.##");
+
+ strBuilder.append("TREE LEVELS: " + treeLevels + "\n");
+ strBuilder.append("FREE PAGES : " + freePages + "\n");
+ strBuilder.append("META PAGES : " + metaPages + "\n");
+ long totalPages = interiorStats.getNumPages() + leafStats.getNumPages() + freePages + metaPages;
+ strBuilder.append("TOTAL PAGES : " + totalPages + "\n");
+
+ strBuilder.append("\n");
+ strBuilder.append("ROOT STATS" + "\n");
+ strBuilder.append("NUM TUPLES: " + rootStats.getNumTuples() + "\n");
+ strBuilder.append("FILL FACTOR : " + df.format(rootStats.getAvgFillFactor()) + "\n");
+
+ if(interiorStats.getNumPages() > 0) {
+ strBuilder.append("\n");
+ strBuilder.append("INTERIOR STATS" + "\n");
+ strBuilder.append("NUM PAGES: " + interiorStats.getNumPages() + "\n");
+ strBuilder.append("NUM TUPLES: " + interiorStats.getNumTuples() + "\n");
+ strBuilder.append("AVG TUPLES/PAGE: " + df.format(interiorStats.getAvgNumTuples()) + "\n");
+ strBuilder.append("AVG FILL FACTOR: " + df.format(interiorStats.getAvgFillFactor()) + "\n");
+ }
+
+ if(leafStats.getNumPages() > 0) {
+ strBuilder.append("\n");
+ strBuilder.append("LEAF STATS" + "\n");
+ strBuilder.append("NUM PAGES: " + df.format(leafStats.getNumPages()) + "\n");
+ strBuilder.append("NUM TUPLES: " + df.format(leafStats.getNumTuples()) + "\n");
+ strBuilder.append("AVG TUPLES/PAGE: " + df.format(leafStats.getAvgNumTuples()) + "\n");
+ strBuilder.append("AVG FILL FACTOR: " + df.format(leafStats.getAvgFillFactor()) + "\n");
+ }
+
+ return strBuilder.toString();
+ }
+
+ public class TreeIndexNodeTypeStats {
+ private long numTuples;
+ private long sumTuplesSizes;
+ private long numPages;
+ private double sumFillFactors;
+
+ public void clear() {
+ numTuples = 0;
+ sumTuplesSizes = 0;
+ numPages = 0;
+ }
+
+ public void add(ITreeIndexFrame frame) {
+ numPages++;
+ numTuples += frame.getTupleCount();
+ sumFillFactors += (double)(frame.getBuffer().capacity() - frame.getTotalFreeSpace()) / (double)frame.getBuffer().capacity();
+ double fillFactor = (double)(frame.getBuffer().capacity() - frame.getTotalFreeSpace()) / (double)frame.getBuffer().capacity();
+ //System.out.println("BLUBBI: " + frame.getBuffer().capacity() + " " + frame.getTotalFreeSpace() + " " + frame.getBuffer().capacity());
+ //System.out.println("INDIVIDUAL FILL FACTOR: " + fillFactor);
+ //if(fillFactor < 0.5) System.out.println("LOW FILL FACTOR: " + frame.getTupleCount());
+ }
+
+ public long getNumTuples() {
+ return numTuples;
+ }
+
+ public long getSumTupleSizes() {
+ return sumTuplesSizes;
+ }
+
+ public long getNumPages() {
+ return numPages;
+ }
+
+ public double getAvgNumTuples() {
+ return (double)numTuples / (double)numPages;
+ }
+
+ public double getAvgTupleSize() {
+ return (double)sumTuplesSizes / (double)numTuples;
+ }
+
+ public double getAvgFillFactor() {
+ return sumFillFactors / numPages;
+ }
+ }
+}
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangeSearchCursor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangeSearchCursor.java
index 1518581..b18d5e5 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangeSearchCursor.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/RangeSearchCursor.java
@@ -87,6 +87,8 @@
page = nextLeaf;
frame.setPage(page);
+
+ System.out.println("NEXT LEAF: " + nextLeafPage + " " + frame.getTupleCount());
}
@Override
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java
index d8989d6..c404a5f 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/IFreePageManager.java
@@ -8,4 +8,11 @@
public int getMaxPage(ITreeIndexMetaDataFrame metaFrame) throws HyracksDataException;
public void init(ITreeIndexMetaDataFrame metaFrame, int currentMaxPage) throws HyracksDataException;
public ITreeIndexMetaDataFrameFactory getMetaDataFrameFactory();
+
+ // required to return negative values
+ public byte getMetaPageLevelIndicator();
+ public byte getFreePageLevelIndicator();
+ // determined by examining level indicator
+ public boolean isMetaPage(ITreeIndexMetaDataFrame metaFrame);
+ public boolean isFreePage(ITreeIndexMetaDataFrame metaFrame);
}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
index 3356846..425821c 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ITreeIndexFrame.java
@@ -74,7 +74,8 @@
// a compatible interior and leaf implementation MUST return identical
// values when given the same ByteBuffer for the functions below
public boolean isLeaf();
-
+ public boolean isInterior();
+
public byte getLevel();
public void setLevel(byte level);
@@ -97,4 +98,5 @@
public ITreeIndexTupleWriter getTupleWriter();
+ public int getPageHeaderSize();
}
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
index fcefc4a..1e02d61 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/frames/TreeIndexNSMFrame.java
@@ -72,6 +72,11 @@
public boolean isLeaf() {
return buf.get(levelOff) == 0;
}
+
+ @Override
+ public boolean isInterior() {
+ return buf.get(levelOff) > 0;
+ }
@Override
public byte getLevel() {
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java
index c09199a..15cc943 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/freepage/LinkedListFreePageManager.java
@@ -10,6 +10,8 @@
public class LinkedListFreePageManager implements IFreePageManager {
+ private static final byte META_PAGE_LEVEL_INDICATOR = -1;
+ private static final byte FREE_PAGE_LEVEL_INDICATOR = -2;
private final IBufferCache bufferCache;
private final int fileId;
private final int headPage;
@@ -55,7 +57,7 @@
.getBuffer().array(), 0, metaNode.getBuffer()
.capacity());
- metaFrame.initBuffer(-1);
+ metaFrame.initBuffer(META_PAGE_LEVEL_INDICATOR);
metaFrame.setNextPage(newPage);
metaFrame.setMaxPage(metaMaxPage);
metaFrame.addFreePage(freePage);
@@ -131,7 +133,7 @@
metaNode.releaseWriteLatch();
bufferCache.unpin(metaNode);
}
-
+
return freePage;
}
@@ -162,7 +164,7 @@
metaNode.acquireWriteLatch();
try {
metaFrame.setPage(metaNode);
- metaFrame.initBuffer((byte) -1);
+ metaFrame.initBuffer(META_PAGE_LEVEL_INDICATOR);
metaFrame.setMaxPage(currentMaxPage);
} finally {
metaNode.releaseWriteLatch();
@@ -174,4 +176,24 @@
public ITreeIndexMetaDataFrameFactory getMetaDataFrameFactory() {
return metaDataFrameFactory;
}
+
+ @Override
+ public byte getFreePageLevelIndicator() {
+ return FREE_PAGE_LEVEL_INDICATOR;
+ }
+
+ @Override
+ public byte getMetaPageLevelIndicator() {
+ return META_PAGE_LEVEL_INDICATOR;
+ }
+
+ @Override
+ public boolean isFreePage(ITreeIndexMetaDataFrame metaFrame) {
+ return metaFrame.getLevel() == FREE_PAGE_LEVEL_INDICATOR;
+ }
+
+ @Override
+ public boolean isMetaPage(ITreeIndexMetaDataFrame metaFrame) {
+ return metaFrame.getLevel() == META_PAGE_LEVEL_INDICATOR;
+ }
}
diff --git a/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/TOccurrenceSearcher.java b/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/TOccurrenceSearcher.java
index 03fd3bc..fe67635 100644
--- a/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/TOccurrenceSearcher.java
+++ b/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/TOccurrenceSearcher.java
@@ -73,8 +73,8 @@
protected int occurrenceThreshold;
protected final int cursorCacheSize = 10;
- protected ArrayList<IInvertedListCursor> invListCursorCache = new ArrayList<IInvertedListCursor>(cursorCacheSize);
- protected ArrayList<IInvertedListCursor> invListCursors = new ArrayList<IInvertedListCursor>(cursorCacheSize);
+ protected List<IInvertedListCursor> invListCursorCache = new ArrayList<IInvertedListCursor>(cursorCacheSize);
+ protected List<IInvertedListCursor> invListCursors = new ArrayList<IInvertedListCursor>(cursorCacheSize);
public TOccurrenceSearcher(IHyracksStageletContext ctx, InvertedIndex invIndex, IBinaryTokenizer queryTokenizer) {
this.ctx = ctx;
@@ -126,11 +126,9 @@
}
currentNumResults = 0;
}
-
-
+
public void search(ITupleReference queryTuple, int queryFieldIndex) throws Exception {
-
- // parse query, TODO: this parsing is too simple
+
RecordDescriptor queryTokenRecDesc = new RecordDescriptor(
new ISerializerDeserializer[] { UTF8StringSerializerDeserializer.INSTANCE });
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
index 36f384d..ddf5042 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
@@ -805,4 +805,10 @@
}
return false;
}
+
+ @Override
+ public int getPageHeaderSize() {
+ // TODO Auto-generated method stub
+ return 0;
+ }
}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
new file mode 100644
index 0000000..90243f5
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeStatsTest.java
@@ -0,0 +1,203 @@
+package edu.uci.ics.hyracks.storage.am.btree;
+
+import java.io.DataOutput;
+import java.io.File;
+import java.nio.ByteBuffer;
+import java.util.Random;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.dataflow.value.TypeTrait;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.comparators.IntegerBinaryComparatorFactory;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeCursor;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.frames.NSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.frames.NSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
+import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeStats;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
+import edu.uci.ics.hyracks.storage.am.btree.impls.RangeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.TreeIndexOp;
+import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class BTreeStatsTest extends AbstractBTreeTest {
+
+ private static final int PAGE_SIZE = 32768;
+ private static final int NUM_PAGES = 1000;
+ private static final int HYRACKS_FRAME_SIZE = 128;
+ private IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+ // FIXED-LENGTH KEY TEST
+ // create a B-tree with one fixed-length "key" field and one fixed-length
+ // "value" field
+ // fill B-tree with random values using insertions (not bulk load)
+ // perform ordered scan and range search
+ @Test
+ public void test01() throws Exception {
+
+ print("FIXED-LENGTH KEY TEST\n");
+
+ TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES);
+ IBufferCache bufferCache = TestStorageManagerComponentHolder
+ .getBufferCache(ctx);
+ IFileMapProvider fmp = TestStorageManagerComponentHolder
+ .getFileMapProvider(ctx);
+ FileReference file = new FileReference(new File(fileName));
+ bufferCache.createFile(file);
+ int fileId = fmp.lookupFileId(file);
+ bufferCache.openFile(fileId);
+
+ // declare fields
+ int fieldCount = 2;
+ ITypeTrait[] typeTraits = new ITypeTrait[fieldCount];
+ typeTraits[0] = new TypeTrait(4);
+ typeTraits[1] = new TypeTrait(4);
+
+ // declare keys
+ int keyFieldCount = 1;
+ IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
+ cmps[0] = IntegerBinaryComparatorFactory.INSTANCE
+ .createBinaryComparator();
+
+ MultiComparator cmp = new MultiComparator(typeTraits, cmps);
+
+ TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(
+ typeTraits);
+ IBTreeLeafFrameFactory leafFrameFactory = new NSMLeafFrameFactory(
+ tupleWriterFactory);
+ IBTreeInteriorFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(
+ tupleWriterFactory);
+ ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+
+ IBTreeLeafFrame leafFrame = leafFrameFactory.getFrame();
+ IBTreeInteriorFrame interiorFrame = interiorFrameFactory.getFrame();
+ ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.getFrame();
+
+ IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
+
+ BTree btree = new BTree(bufferCache, freePageManager, interiorFrameFactory,
+ leafFrameFactory, cmp);
+ btree.create(fileId, leafFrame, metaFrame);
+ btree.open(fileId);
+
+ Random rnd = new Random();
+ rnd.setSeed(50);
+
+ long start = System.currentTimeMillis();
+
+ print("INSERTING INTO TREE\n");
+
+ ByteBuffer frame = ctx.allocateFrame();
+ FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
+ ArrayTupleBuilder tb = new ArrayTupleBuilder(cmp.getFieldCount());
+ DataOutput dos = tb.getDataOutput();
+
+ ISerializerDeserializer[] recDescSers = {
+ IntegerSerializerDeserializer.INSTANCE,
+ IntegerSerializerDeserializer.INSTANCE };
+ RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
+ IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx
+ .getFrameSize(), recDesc);
+ accessor.reset(frame);
+ FrameTupleReference tuple = new FrameTupleReference();
+
+ BTreeOpContext insertOpCtx = btree.createOpContext(TreeIndexOp.TI_INSERT,
+ leafFrame, interiorFrame, metaFrame);
+
+ // 10000
+ for (int i = 0; i < 100000; i++) {
+
+ int f0 = rnd.nextInt() % 100000;
+ int f1 = 5;
+
+ tb.reset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(f0, dos);
+ tb.addFieldEndOffset();
+ IntegerSerializerDeserializer.INSTANCE.serialize(f1, dos);
+ tb.addFieldEndOffset();
+
+ appender.reset(frame, true);
+ appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb
+ .getSize());
+
+ tuple.reset(accessor, 0);
+
+ // System.out.println(tuple.getFieldCount() + " " +
+ // tuple.getFieldLength(0) + " " + tuple.getFieldLength(1));
+
+ if (i % 10000 == 0) {
+ long end = System.currentTimeMillis();
+ print("INSERTING " + i + " : " + f0 + " " + f1 + " "
+ + (end - start) + "\n");
+ }
+
+ try {
+ btree.insert(tuple, insertOpCtx);
+ } catch (TreeIndexException e) {
+ } catch (Exception e) {
+ e.printStackTrace();
+ }
+
+ // btree.printTree(leafFrame, interiorFrame);
+ // System.out.println();
+ }
+ // btree.printTree(leafFrame, interiorFrame);
+ // System.out.println();
+
+ print("ORDERED SCAN:\n");
+ IBTreeCursor scanCursor = new RangeSearchCursor(leafFrame);
+ RangePredicate nullPred = new RangePredicate(true, null, null, true,
+ true, null, null);
+ BTreeOpContext searchOpCtx = btree.createOpContext(TreeIndexOp.TI_SEARCH,
+ leafFrame, interiorFrame, null);
+ btree.search(scanCursor, nullPred, searchOpCtx);
+ try {
+ while (scanCursor.hasNext()) {
+ scanCursor.next();
+ }
+ } catch (Exception e) {
+ e.printStackTrace();
+ } finally {
+ scanCursor.close();
+ }
+
+ BTreeStats btreeStats = new BTreeStats();
+ btree.getBTreeStats(leafFrame, interiorFrame, metaFrame, btreeStats);
+ String s = btreeStats.toString();
+ System.out.println(s);
+
+ btree.close();
+ bufferCache.closeFile(fileId);
+ bufferCache.close();
+
+ print("\n");
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
index 505521c..7a00914 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeTest.java
@@ -36,9 +36,7 @@
import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
import edu.uci.ics.hyracks.dataflow.common.data.comparators.IntegerBinaryComparatorFactory;
-import edu.uci.ics.hyracks.dataflow.common.data.comparators.UTF8StringBinaryComparatorFactory;
import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
-import edu.uci.ics.hyracks.dataflow.common.data.marshalling.UTF8StringSerializerDeserializer;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeCursor;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrameFactory;
@@ -59,7 +57,6 @@
import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.TreeIndexOp;
-import edu.uci.ics.hyracks.storage.am.common.tuples.SimpleTupleWriterFactory;
import edu.uci.ics.hyracks.storage.am.common.tuples.TypeAwareTupleWriterFactory;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.buffercache.ICacheMemoryAllocator;
@@ -69,8 +66,8 @@
public class BTreeTest extends AbstractBTreeTest {
- private static final int PAGE_SIZE = 256;
- private static final int NUM_PAGES = 10;
+ private static final int PAGE_SIZE = 256;
+ private static final int NUM_PAGES = 10;
private static final int HYRACKS_FRAME_SIZE = 128;
private IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
@@ -120,9 +117,7 @@
MultiComparator cmp = new MultiComparator(typeTraits, cmps);
TypeAwareTupleWriterFactory tupleWriterFactory = new TypeAwareTupleWriterFactory(
- typeTraits);
- // SimpleTupleWriterFactory tupleWriterFactory = new
- // SimpleTupleWriterFactory();
+ typeTraits);
IBTreeLeafFrameFactory leafFrameFactory = new NSMLeafFrameFactory(
tupleWriterFactory);
IBTreeInteriorFrameFactory interiorFrameFactory = new NSMInteriorFrameFactory(
@@ -203,7 +198,7 @@
}
// btree.printTree(leafFrame, interiorFrame);
// System.out.println();
-
+
int maxPage = btree.getFreePageManager().getMaxPage(metaFrame);
System.out.println("MAXPAGE: " + maxPage);
@@ -317,9 +312,11 @@
bufferCache.closeFile(fileId);
bufferCache.close();
- print("\n");
+ print("\n");
}
+ /*
+
// COMPOSITE KEY TEST (NON-UNIQUE B-TREE)
// create a B-tree with one two fixed-length "key" fields and one
// fixed-length "value" field
@@ -1350,4 +1347,5 @@
}
return strBuilder.toString();
}
+ */
}
\ No newline at end of file