Fennel: BTreeLeafReader Class Reference (original) (raw)

BTreeLeafReader extends BTreeReader by only doing reads of leaf pages in a btree. More...

#include <[BTreeLeafReader.h](BTreeLeafReader%5F8h-source.html)>

Inheritance diagram for BTreeLeafReader:

Public Member Functions
	BTreeLeafReader (BTreeDescriptor const &descriptor)
virtual bool	searchForKey (TupleData const &key, DuplicateSeek dupSeek, bool leastUpper=true)
	Searches for a tuple in the current leaf page based on the given key.
virtual bool	searchNext ()
	Searches for the next tuple in the current leaf page.
virtual void	endSearch ()
	Resets the search such that there no longer is a current leaf page.
void	setCurrentPageId (PageId pageId)
	Sets the current leaf page that will later be searched/read.
TupleAccessor const &	getTupleAccessorForRead () const
	Gets a read-only accessor for leaf tuples.
TupleData &	getSearchKeyForWrite ()
	Gets writable TupleData which can be used to prepare a key to be used in searchForKey.
bool	searchFirst ()
	Searches for the first tuple in the tree.
bool	searchLast ()
	Searches for the last tuple in the tree.
bool	isPositioned () const
	Returns:true if a search method has been called without a subsequent endSearch yet
bool	isSingular () const
	Returns:true if reader is either unpositioned or past last entry in tree
SharedSegment	getSegment () const
	Returns:the segment storing the BTree being accessed
SharedCacheAccessor	getCacheAccessor () const
	Returns:the CacheAccessor used to access the BTree's pages
PageId	getRootPageId () const
	Returns:the BTree's root PageId
void	setRootPageId (PageId rootPageId)
	Updates the BTree's root PageId.
SegmentId	getSegmentId () const
	Returns:SegmentId of segment storing the BTree
PageOwnerId	getPageOwnerId () const
	Returns:PageOwnerId used to mark pages of the BTree
TupleDescriptor const &	getTupleDescriptor () const
	Returns:TupleDescriptor for tuples stored by this BTree
TupleDescriptor const &	getKeyDescriptor () const
	Returns:TupleDescriptor for keys indexed by this BTree
TupleProjection const &	getKeyProjection () const
	Returns:TupleProjection from getTupleDescriptor() to getKeyDescriptor()
void	validateTupleSize (TupleAccessor const &tupleAccessor)
	Validates that a particular tuple can fit in this BTree, throwing a TupleOverflowExcn if not.
Protected Types
enum	ReadMode { READ_ALL, READ_NONLEAF_ONLY, READ_LEAF_ONLY }
	Enumeration of which node types the reader should be reading. More...
Protected Member Functions
void	accessLeafTuple ()
uint	binarySearch (BTreeNode const &node, DuplicateSeek dupSeek, bool leastUpper, bool &found)
	Searches a node for the current search key.
TupleData const &	getSearchKey ()
	Returns:the key being sought
int	compareFirstKey (BTreeNode const &node)
	Compares the first key on a node to the current search key.
void	accessTupleInline (BTreeNode const &node, uint iEntry)
	Sets tuple accessor to provided node entry.
template<bool leafLockCoupling, class PageStack>
bool	searchForKeyTemplate (TupleData const &key, DuplicateSeek dupSeek, bool leastUpper, PageStack &pageStack, PageId startPageId, LockMode initialLockMode, ReadMode readMode)
	Implements the workhorse algorithm for performing the actual search through the tree; templated to efficiently allow for certain variations needed when the search is used in preparation for an insertion by BTreeWriter.
bool	searchForKeyInternal (TupleData const &key, DuplicateSeek dupSeek, bool leastUpper, PageId startPageId, LockMode initialLockMode, ReadMode readMode)
	See also:searchForKeyTemplate()
bool	searchExtremeInternal (bool first, ReadMode readMode)
	Searches for the first or last tuple in the tree.
bool	searchNextInternal ()
	Searches for next tuple.
BTreeNodeAccessor &	getLeafNodeAccessor (BTreeNode const &node)
	Gets the node accessor for a leaf node, asserting that the node really is a leaf.
BTreeNodeAccessor &	getNonLeafNodeAccessor (BTreeNode const &node)
	Gets the node accessor for a non-leaf node, asserting that the node really is a non-leaf.
BTreeNodeAccessor &	getNodeAccessor (BTreeNode const &node)
	Gets the node accessor for any node, using the node height to determine whether it's a leaf or not.
PageId	getChildForCurrent ()
	Gets the child PageId corresponding to the current key in a non-leaf node.
PageId	getChild (BTreeNode const &node, uint iChild)
	Accesses a non-leaf tuple and gets its child PageId.
PageId	getRightSibling (PageId pageId)
	Gets the right sibling of a node by consulting the containing segment's successor information.
void	setRightSibling (BTreeNode &leftNode, PageId leftPageId, PageId rightPageId)
	Sets the right sibling of a node.
PageId	getFirstChild (PageId pageId)
	Gets the first child of a non-leaf node.
Protected Attributes
BTreePageLock	pageLock
	Lock on node being searched.
PageId	pageId
	PageId of node being searched.
uint	iTupleOnLowestLevel
	0-based position on lowest level searched by the reader.
bool	singular
	See also:isSingular()
LockMode	rootLockMode
	LockMode to use when acquiring lock on root node.
LockMode	nonLeafLockMode
	LockMode to use when acquiring lock on non-leaf nodes other than the root.
LockMode	leafLockMode
	LockMode to use when acquiring lock on leaf nodes.
TupleData	comparisonKeyData
	TupleData used as a temp variable for comparisons while searching.
TupleData const *	pSearchKey
	Key being sought.
TupleData	searchKeyData
	TupleData for key used in searches.
BTreeDescriptor	treeDescriptor
	Descriptor for tree being accessed.
TupleDescriptor	keyDescriptor
	Descriptor for pure keys (common across leaf and non-leaf tuples).
AttributeAccessor const *	pChildAccessor
	Accessor for the attribute of non-leaf tuples which stores the child PageId.
TupleProjectionAccessor	leafKeyAccessor
	Accessor for keys of tuples stored in leaves.
boost::scoped_ptr< BTreeNodeAccessor >	pNonLeafNodeAccessor
	Accessor for non-leaf nodes.
boost::scoped_ptr< BTreeNodeAccessor >	pLeafNodeAccessor
	Accessor for leaf nodes.
uint	cbTupleMax
	Maximum size for a leaf-level tuple.
Private Member Functions
bool	adjustRootLockMode (LockMode &lockMode)
	Deals with the fact that when we lock the root, we don't know whether it happens to be a leaf as well.
virtual bool	searchExtreme (bool first)
	Searches for the first or last tuple in the current leaf node.
Private Attributes
PageId	currLeafPageId
	The current leaf page to be searched/read.

Detailed Description

BTreeLeafReader extends BTreeReader by only doing reads of leaf pages in a btree.

Definition at line 35 of file BTreeLeafReader.h.

Member Enumeration Documentation

Enumeration of which node types the reader should be reading.

Enumerator:

READ_ALL	Read both non-leaf and leaf nodes.
READ_NONLEAF_ONLY	Read only non-leaf nodes.
READ_LEAF_ONLY	Read only leaf nodes.

Definition at line 43 of file BTreeReader.h.

Constructor & Destructor Documentation

BTreeLeafReader::BTreeLeafReader	(	BTreeDescriptor const &	descriptor	)	[explicit]

Member Function Documentation

bool BTreeLeafReader::adjustRootLockMode	(	LockMode &	lockMode	)	[private]

Deals with the fact that when we lock the root, we don't know whether it happens to be a leaf as well.

This method is a no-op for this class. The lockMode passed in should always be the same as the current lock mode since this class only reads leaf pages.

Parameters:

lockMode	the lock mode used to lock a leaf

Returns:

always returns true

Reimplemented from BTreeReader.

Definition at line 37 of file BTreeLeafReader.cpp.

References BTreeReader::leafLockMode.

00038 { 00039 assert(lockMode == leafLockMode); 00040 return true; 00041 }

bool BTreeLeafReader::searchExtreme	(	bool	first	)	[private, virtual]

bool BTreeLeafReader::searchForKey	(	TupleData const &	key,
DuplicateSeek	dupSeek,
bool	leastUpper = true
)	[virtual]

| bool BTreeLeafReader::searchNext | ( | | ) | [virtual] | | -------------------------------- | - | | - | ----------- |

| void BTreeLeafReader::endSearch | ( | | ) | [virtual] | | ------------------------------- | - | | - | ----------- |

void BTreeLeafReader::setCurrentPageId	(	PageId	pageId	)

| void BTreeReader::accessLeafTuple | ( | | ) | [inline, protected, inherited] | | --------------------------------- | - | | - | -------------------------------- |

uint BTreeReader::binarySearch	(	BTreeNode const &	node,
DuplicateSeek	dupSeek,
bool	leastUpper,
bool &	found
)	[inline, protected, inherited]

| FENNEL_BEGIN_NAMESPACE TupleData const & BTreeReader::getSearchKey | ( | | ) | [inline, protected, inherited] | | ------------------------------------------------------------------------------------------- | - | | - | -------------------------------- |

int BTreeReader::compareFirstKey	(	BTreeNode const &	node	)	[inline, protected, inherited]

void BTreeReader::accessTupleInline	(	BTreeNode const &	node,
uint	iEntry
)	[inline, protected, inherited]

template<bool leafLockCoupling, class PageStack>

bool BTreeReader::searchForKeyTemplate	(	TupleData const &	key,
DuplicateSeek	dupSeek,
bool	leastUpper,
PageStack &	pageStack,
PageId	startPageId,
LockMode	initialLockMode,
ReadMode	readMode
)	[inline, protected, inherited]

Implements the workhorse algorithm for performing the actual search through the tree; templated to efficiently allow for certain variations needed when the search is used in preparation for an insertion by BTreeWriter.

leafLockCoupling controls whether lock coupling is enforced while moving rightward at the leaf level.

Parameters:

key	the key being searched for
dupSeek	how to handle duplicates
leastUpper	whether to position on least upper bound or greatest lower bound
pageStack	receives a path of rightmost PageId's encountered from root to the level above the leaf (PageStack must support the push_back method)
startPageId	the pageId at which the search should start
initialLockMode	the initial lockmode to use when searching the tree
readMode	which node types should be searched

Definition at line 96 of file BTreeReaderImpl.h.

References BTreeReader::accessTupleInline(), BTreeReader::adjustRootLockMode(), BTreeReader::binarySearch(), BTreeReader::compareFirstKey(), DUP_SEEK_END, BTreeAccessBase::getChild(), BTreeAccessBase::getChildForCurrent(), BTreeAccessBase::getFirstChild(), SegNodeLock< Node >::getNodeForRead(), BTreeNode::height, BTreeReader::iTupleOnLowestLevel, BTreeAccessBase::keyDescriptor, BTreeReader::leafLockMode, SegPageLock::lockPage(), SegPageLock::lockPageWithCoupling(), BTreeNode::nEntries, NULL_PAGE_ID, BTreeReader::pageId, BTreeReader::pageLock, BTreeReader::pSearchKey, BTreeReader::READ_LEAF_ONLY, BTreeReader::READ_NONLEAF_ONLY, BTreeNode::rightSibling, BTreeReader::singular, and SegPageLock::unlock().

00100 { 00101 pSearchKey = &key; 00102 00103
00104
00105
00106
00107 PageId rightSearchTerminator = NULL_PAGE_ID; 00108 pageId = startPageId; 00109 LockMode lockMode = initialLockMode; 00110 bool lockCoupling = false; 00111 bool foundKeyAndMovedRight = false; 00112 for (;;) { 00113 if (leafLockCoupling && lockCoupling) { 00114 pageLock.lockPageWithCoupling(pageId,lockMode); 00115 } else { 00116 pageLock.lockPage(pageId,lockMode); 00117 } 00118 00119 BTreeNode const *pNode = &(pageLock.getNodeForRead()); 00120 00121
00122 if (!pNode->height && adjustRootLockMode (lockMode)) { 00123
00124 continue; 00125 } 00126 00127 bool found; 00128 uint iKeyBound = binarySearch(*pNode,dupSeek,leastUpper,found); 00129 if (foundKeyAndMovedRight && !found) { 00130
00131
00132
00133
00134
00135 assert(iKeyBound == 0); 00136 found = true; 00137 } 00138 00139
00140
00141
00142
00143 if (!leastUpper && !found && iKeyBound == pNode->nEntries - 1 && 00144 pNode->rightSibling != NULL_PAGE_ID) 00145 { 00146
00147
00148 assert(leafLockCoupling == false); 00149 00150 PageId siblingPageId = pNode->rightSibling; 00151 pageLock.unlock(); 00152 pageLock.lockPage(siblingPageId, lockMode); 00153 BTreeNode const &rightNode = pageLock.getNodeForRead(); 00154 int res = compareFirstKey(rightNode); 00155 00156 pageLock.unlock(); 00157 if (res < 0) { 00158
00159
00160
00161
00162
00163
00164
00165
00166
00167
00168 pageLock.lockPage(pageId, lockMode); 00169 pNode = &(pageLock.getNodeForRead()); 00170 accessTupleInline(*pNode, iKeyBound); 00171 } else { 00172
00173
00174 if (readMode == READ_LEAF_ONLY) { 00175 assert(rightNode.height == 0); 00176
00177
00178 pageLock.lockPage(pageId, lockMode); 00179 iTupleOnLowestLevel = iKeyBound; 00180 return false; 00181 } 00182 pageId = siblingPageId; 00183 foundKeyAndMovedRight = false; 00184 continue; 00185 } 00186 } 00187 00188 if (iKeyBound == pNode->nEntries) { 00189 assert(!found || (dupSeek == DUP_SEEK_END)); 00190
00191
00192 if (pNode->rightSibling == rightSearchTerminator) { 00193
00194
00195
00196
00197 assert(!pNode->height); 00198 if (rightSearchTerminator == NULL_PAGE_ID) { 00199 singular = true; 00200 } 00201 } else { 00202
00203 foundKeyAndMovedRight = found; 00204 pageId = pNode->rightSibling; 00205 if (leafLockCoupling && !pNode->height) { 00206 lockCoupling = true; 00207 } 00208 continue; 00209 } 00210 } 00211 00212 switch (pNode->height) { 00213 case 0: 00214
00215 iTupleOnLowestLevel = iKeyBound; 00216 return found; 00217 00218 case 1: 00219 if (readMode == READ_NONLEAF_ONLY) { 00220 iTupleOnLowestLevel = iKeyBound; 00221 return found; 00222 } 00223
00224 lockMode = leafLockMode; 00225 break; 00226 } 00227 00228
00229 pageStack.push_back(pageId); 00230 00231
00232 pageId = getChildForCurrent(); 00233 foundKeyAndMovedRight = false; 00234 00235
00236
00237
00238
00239
00240
00241
00242
00243 if ((*pSearchKey).size() == keyDescriptor.size() && 00244 dupSeek != DUP_SEEK_END) 00245 { 00246 if (iKeyBound < (pNode->nEntries - 1)) { 00247 rightSearchTerminator = getChild(*pNode,iKeyBound + 1); 00248 } else { 00249
00250
00251
00252 PageId rightSiblingPageId = pNode->rightSibling; 00253 pageLock.unlock(); 00254 rightSearchTerminator = getFirstChild(rightSiblingPageId); 00255 } 00256 } 00257 } 00258 }

bool BTreeReader::searchForKeyInternal	(	TupleData const &	key,
DuplicateSeek	dupSeek,
bool	leastUpper,
PageId	startPageId,
LockMode	initialLockMode,
ReadMode	readMode
)	[protected, inherited]

See also:

searchForKeyTemplate()

Definition at line 153 of file BTreeReader.cpp.

References BTreeReader::pSearchKey, and BTreeReader::singular.

Referenced by BTreeReader::searchForKey(), BTreeNonLeafReader::searchForKey(), and searchForKey().

00156 { 00157 singular = false; 00158 NullPageStack nullPageStack; 00159 bool found = searchForKeyTemplate<false,NullPageStack>( 00160 key,dupSeek,leastUpper,nullPageStack,startPageId,initialLockMode, 00161 readMode); 00162 pSearchKey = NULL; 00163 return found; 00164 }

bool BTreeReader::searchExtremeInternal	(	bool	first,
ReadMode	readMode
)	[protected, inherited]

Searches for the first or last tuple in the tree.

Parameters:

first	true for first; false for last
readMode	which types of nodes should be searched

Returns:

true if tuple found; false if tree is empty

Definition at line 54 of file BTreeReader.cpp.

References BTreeReader::accessLeafTuple(), BTreeReader::accessTupleInline(), BTreeReader::adjustRootLockMode(), BTreeAccessBase::getChild(), SegNodeLock< Node >::getNodeForRead(), BTreeAccessBase::getRootPageId(), BTreeNode::height, BTreeReader::iTupleOnLowestLevel, BTreeReader::leafLockMode, SegPageLock::lockPage(), BTreeNode::nEntries, BTreeReader::nonLeafLockMode, NULL_PAGE_ID, BTreeReader::pageId, BTreeReader::pageLock, BTreeReader::READ_NONLEAF_ONLY, BTreeNode::rightSibling, BTreeReader::rootLockMode, and BTreeReader::singular.

Referenced by BTreeReader::searchExtreme(), and BTreeNonLeafReader::searchExtreme().

| bool BTreeReader::searchNextInternal | ( | | ) | [protected, inherited] | | ------------------------------------ | - | | - | ------------------------ |

| TupleAccessor const & BTreeReader::getTupleAccessorForRead | ( | | ) | const [inherited] | | ------------------------------------------------------------------------------------- | - | | - | ------------------- |

| TupleData & BTreeReader::getSearchKeyForWrite | ( | | ) | [inline, inherited] | | -------------------------------------------------------------------- | - | | - | --------------------- |

| bool BTreeReader::searchFirst | ( | | ) | [inline, inherited] | | ----------------------------- | - | | - | --------------------- |

| bool BTreeReader::searchLast | ( | | ) | [inline, inherited] | | ---------------------------- | - | | - | --------------------- |

Searches for the last tuple in the tree.

FIXME jvs 11-Nov-2005: This method isn't currently guaranteed to work after deletions on a tree. The problem is that deletions may leave the last page of the tree empty, so when we hit leaf level, we may not find anything, even though a predecessor page is non-empty. We only have right-sibling links, not left-siblings, so the fix requires keeping a breadcrumb trail on the way down and backtracking when we hit an empty leaf.

Returns:

true if tuple found; false if tree is empty

Definition at line 362 of file BTreeReader.h.

References BTreeReader::searchExtreme().

Referenced by BTreeTest::testScan(), BTreeReadersTest::testScan(), and BTreeTest::testSearchLast().

| bool BTreeReader::isPositioned | ( | | ) | const [inline, inherited] | | ------------------------------ | - | | - | --------------------------- |

| bool BTreeReader::isSingular | ( | | ) | const [inline, inherited] | | ---------------------------- | - | | - | --------------------------- |

FENNEL_BEGIN_NAMESPACE BTreeNodeAccessor & BTreeAccessBase::getLeafNodeAccessor	(	BTreeNode const &	node	)	[inline, protected, inherited]

Gets the node accessor for any node, using the node height to determine whether it's a leaf or not.

If you already know this from the context, call getLeafNodeAccessor or getNonLeafNodeAccessor instead.

Parameters:

Returns:

node accessor

Definition at line 46 of file BTreeAccessBaseImpl.h.

References BTreeNode::height, BTreeAccessBase::pLeafNodeAccessor, and BTreeAccessBase::pNonLeafNodeAccessor.

Referenced by BTreeReader::accessTupleInline(), BTreeWriter::attemptInsertWithoutSplit(), BTreeReader::binarySearch(), BTreeWriter::compactNode(), BTreeReader::compareFirstKey(), BTreeWriter::grow(), BTreeWriter::lockParentPage(), BTreeWriter::splitCurrentNode(), BTreeVerifier::verifyChildren(), and BTreeVerifier::verifyNode().

| PageId BTreeAccessBase::getChildForCurrent | ( | | ) | [inline, protected, inherited] | | ------------------------------------------ | - | | - | -------------------------------- |

PageId BTreeAccessBase::getChild	(	BTreeNode const &	node,
uint	iChild
)	[inline, protected, inherited]

PageId BTreeAccessBase::getRightSibling	(	PageId	pageId	)	[inline, protected, inherited]

void BTreeAccessBase::setRightSibling	(	BTreeNode &	leftNode,
PageId	leftPageId,
PageId	rightPageId
)	[inline, protected, inherited]

PageId BTreeAccessBase::getFirstChild	(	PageId	pageId	)	[protected, inherited]

| SharedSegment BTreeAccessBase::getSegment | ( | | ) | const [inline, inherited] | | --------------------------------------------------------------------------------------------------- | - | | - | --------------------------- |

Returns:

the segment storing the BTree being accessed

Definition at line 234 of file BTreeAccessBase.h.

References SegmentAccessor::pSegment, BTreeDescriptor::segmentAccessor, and BTreeAccessBase::treeDescriptor.

Referenced by BTreeBuildLevel::allocatePage(), BTreeAccessBase::BTreeAccessBase(), BTreeBuilder::buildBalanced(), BTreeBuilder::buildTwoPass(), BTreeBuilder::buildUnbalanced(), BTreeWriter::compactNode(), BTreeBuilder::createEmptyRoot(), BTreeAccessBase::getRightSibling(), BTreeWriter::grow(), BTreeAccessBase::setRightSibling(), BTreeWriter::splitCurrentNode(), and BTreeBuilder::truncate().

| PageId BTreeAccessBase::getRootPageId | ( | | ) | const [inline, inherited] | | ------------------------------------- | - | | - | --------------------------- |

Returns:

the BTree's root PageId

Definition at line 244 of file BTreeAccessBase.h.

References BTreeDescriptor::rootPageId, and BTreeAccessBase::treeDescriptor.

Referenced by BTreeVerifier::BTreeVerifier(), BTreeBuilder::buildBalanced(), BTreeInsertExecStream::buildTree(), LbmSplicerExecStreamTest::createBTree(), BTreeBuilder::createEmptyRoot(), BTreeWriter::describeParticipant(), LcsClusterReplaceExecStream::getTupleForLoad(), LbmSplicerExecStream::getValidatedTuple(), BTreeNonLeafReader::isRootOnly(), LcsClusterReplaceExecStreamTest::loadCluster(), LcsMultiClusterAppendTest::loadClusters(), LcsRowScanExecStreamTest::loadOneCluster(), LbmSearchTest::loadTableAndIndex(), BTreeWriter::lockParentPage(), BTreeWriter::optimizeRootLockMode(), BTreeWriter::positionSearchKey(), BTreeReader::searchExtremeInternal(), BTreeReader::searchForKey(), BTreeNonLeafReader::searchForKey(), BTreeBuilder::swapRoot(), ExecStreamTestSuite::testBTreeInsertExecStream(), BTreeTest::testBulkLoad(), BTreeTest::testInserts(), LbmLoadBitmapTest::testLoad(), LcsClusterAppendExecStreamTest::testLoadMultiCol(), LcsClusterAppendExecStreamTest::testLoadSingleCol(), BTreeTest::testMultiKeySearches(), BTreeReadersTest::testReaders(), BTreeReadersTest::testScan(), LcsRowScanExecStreamTest::testScanOnEmptyCluster(), BTreeReadersTest::testSearch(), BTreeBuilder::truncate(), BTreeVerifier::verify(), and CmdInterpreter::visit().

void BTreeAccessBase::setRootPageId	(	PageId	rootPageId	)	[inherited]

| SegmentId BTreeAccessBase::getSegmentId | ( | | ) | const [inline, inherited] | | --------------------------------------- | - | | - | --------------------------- |

| PageOwnerId BTreeAccessBase::getPageOwnerId | ( | | ) | const [inline, inherited] | | ------------------------------------------- | - | | - | --------------------------- |

| TupleDescriptor const & BTreeAccessBase::getTupleDescriptor | ( | | ) | const [inline, inherited] | | ---------------------------------------------------------------------------------------- | - | | - | --------------------------- |

| TupleDescriptor const & BTreeAccessBase::getKeyDescriptor | ( | | ) | const [inline, inherited] | | -------------------------------------------------------------------------------------- | - | | - | --------------------------- |

| TupleProjection const & BTreeAccessBase::getKeyProjection | ( | | ) | const [inline, inherited] | | -------------------------------------------------------------------------------------- | - | | - | --------------------------- |