com.sleepycat.je.dbi
Class SortedLSNTreeWalker

java.lang.Object
  extended by com.sleepycat.je.dbi.SortedLSNTreeWalker

public class SortedLSNTreeWalker
extends Object

SortedLSNTreeWalker uses ordered disk access rather than random access to iterate over a database tree. Faulting in data records by on-disk order can provide much improved performance over faulting in by key order, since the latter may require random access. SortedLSN walking does not obey cursor and locking constraints, and therefore can only be guaranteed consistent for a quiescent tree which is not being modified by user or daemon threads. The class walks over the tree using sorted LSN fetching for parts of the tree that are not in memory. It returns LSNs for each node in the tree, except the root IN, in an arbitrary order (i.e. not key order). The caller is responsible for getting the root IN's LSN explicitly.

A callback function specified in the constructor is executed for each LSN found.

The walker works in two phases. The first phase is to gather and return all the resident INs using the roots that were specified when the SLTW was constructed. For each child of each root, if the child is resident it is passed to the callback method (processLSN). If the child was not in memory, it is added to a list of LSNs to read. When all of the in-memory INs have been passed to the callback for all LSNs collected, phase 1 is complete.

In phase 2, for each of the sorted LSNs, the target is fetched, the type determined, and the LSN and type passed to the callback method for processing. LSNs of the children of those nodes are retrieved and the process repeated until there are no more nodes to be fetched for this database's tree. LSNs are accumlated in batches in this phase so that memory consumption is not excessive. For instance, if batches were not used then the LSNs of all of the BINs would need to be held in memory.


Nested Class Summary
static class SortedLSNTreeWalker.DeltaINEntry
          Supplements INEntry with BINDelta information.
static interface SortedLSNTreeWalker.ExceptionPredicate
           
static class SortedLSNTreeWalker.INEntry
           
static interface SortedLSNTreeWalker.TreeNodeProcessor
           
 
Field Summary
protected  boolean accumulateDupLNs
           
protected  boolean accumulateLNs
           
protected  DatabaseImpl[] dbImpls
           
protected  EnvironmentImpl envImpl
           
 
Constructor Summary
SortedLSNTreeWalker(DatabaseImpl[] dbImpls, boolean setDbState, long[] rootLsns, SortedLSNTreeWalker.TreeNodeProcessor callback, List<DatabaseException> savedExceptions, SortedLSNTreeWalker.ExceptionPredicate excPredicate)
           
 
Method Summary
protected  void accumulateLSNs(IN in, LSNAccumulator pendingLSNs)
           
protected  void callProcessLSNHandleExceptions(long childLSN, LogEntryType childType, Node theNode, byte[] lnKey)
           
protected  boolean fetchAndInsertIntoTree()
           
protected  Node fetchLSN(long lsn, DatabaseEntry lnKeyEntry, LSNAccumulator pendingLSNs)
           
protected  IN getOrFetchRootIN(DatabaseImpl dbImpl, long rootLsn)
          Returns the root IN, latched shared.
protected  IN getResidentRootIN(DatabaseImpl dbImpl)
          The default behavior returns (and latches shared) the IN if it is resident in the Btree, or null otherwise.
protected  IN getRootIN(DatabaseImpl dbImpl, long rootLsn)
          The default behavior fetches the rootIN from the log and latches it shared.
 List<DatabaseException> getSavedExceptions()
           
(package private)  void incInternalMemoryUsage(long increment)
           
protected  void processAccumulatedLSNs(LSNAccumulator pendingLSNs)
           
protected  void processResidentChild(long lsn, Node node, byte[] lnKey, LSNAccumulator pendingLSNs)
           
protected  void releaseRootIN(IN root)
          Release the latch.
(package private)  void setInternalMemoryLimit(long internalMemoryLimit)
           
(package private)  void setLSNBatchSize(long lsnBatchSize)
           
 void walk()
          Find all non-resident nodes, and execute the callback.
protected  void walkInternal()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

dbImpls

protected final DatabaseImpl[] dbImpls

envImpl

protected final EnvironmentImpl envImpl

accumulateLNs

protected boolean accumulateLNs

accumulateDupLNs

protected boolean accumulateDupLNs
Constructor Detail

SortedLSNTreeWalker

public SortedLSNTreeWalker(DatabaseImpl[] dbImpls,
                           boolean setDbState,
                           long[] rootLsns,
                           SortedLSNTreeWalker.TreeNodeProcessor callback,
                           List<DatabaseException> savedExceptions,
                           SortedLSNTreeWalker.ExceptionPredicate excPredicate)
                    throws DatabaseException
Throws:
DatabaseException
Method Detail

setLSNBatchSize

void setLSNBatchSize(long lsnBatchSize)

setInternalMemoryLimit

void setInternalMemoryLimit(long internalMemoryLimit)

incInternalMemoryUsage

void incInternalMemoryUsage(long increment)

walk

public void walk()
          throws DatabaseException
Find all non-resident nodes, and execute the callback. The root IN's LSN is not returned to the callback.

Throws:
DatabaseException

walkInternal

protected void walkInternal()
                     throws DatabaseException
Throws:
DatabaseException

processAccumulatedLSNs

protected void processAccumulatedLSNs(LSNAccumulator pendingLSNs)

accumulateLSNs

protected void accumulateLSNs(IN in,
                              LSNAccumulator pendingLSNs)
                       throws DatabaseException
Throws:
DatabaseException

processResidentChild

protected void processResidentChild(long lsn,
                                    Node node,
                                    byte[] lnKey,
                                    LSNAccumulator pendingLSNs)

callProcessLSNHandleExceptions

protected void callProcessLSNHandleExceptions(long childLSN,
                                              LogEntryType childType,
                                              Node theNode,
                                              byte[] lnKey)

getOrFetchRootIN

protected IN getOrFetchRootIN(DatabaseImpl dbImpl,
                              long rootLsn)
Returns the root IN, latched shared. Allows subclasses to override getResidentRootIN and/or getRootIN to modify behavior. getResidentRootIN is called first,


getRootIN

protected IN getRootIN(DatabaseImpl dbImpl,
                       long rootLsn)
The default behavior fetches the rootIN from the log and latches it shared. Classes extending this may fetch (and latch) the root from the tree.


getResidentRootIN

protected IN getResidentRootIN(DatabaseImpl dbImpl)
The default behavior returns (and latches shared) the IN if it is resident in the Btree, or null otherwise. Classes extending this may return (and latch) a known IN object.


releaseRootIN

protected void releaseRootIN(IN root)
Release the latch. Overriding this method should not be necessary.


fetchLSN

protected Node fetchLSN(long lsn,
                        DatabaseEntry lnKeyEntry,
                        LSNAccumulator pendingLSNs)
                 throws FileNotFoundException,
                        DatabaseException
Throws:
FileNotFoundException
DatabaseException

fetchAndInsertIntoTree

protected boolean fetchAndInsertIntoTree()

getSavedExceptions

public List<DatabaseException> getSavedExceptions()


Copyright (c) 2004-2012 Oracle. All rights reserved.