org.apache.derby.impl.store.access.btree
Class BTreeMaxScan

java.lang.Object
  extended by org.apache.derby.impl.store.access.btree.OpenBTree
      extended by org.apache.derby.impl.store.access.btree.BTreeScan
          extended by org.apache.derby.impl.store.access.btree.BTreeMaxScan
All Implemented Interfaces:
ScanManager, GenericScanController, GroupFetchScanController, RowCountable, ScanController
Direct Known Subclasses:
B2IMaxScan

public class BTreeMaxScan
extends BTreeScan

A BTreeScan implementation that provides the 90% solution to the max on btree problem. If the row is the last row in the btree it works very efficiently. This implementation will be removed once backward scan is fully functional. The current implementation only exports to the user the ability to call fetchMax() and get back one row, none of the generic scan ablities are exported. To return the maximum row this implementation does the following: 1) calls positionAtStartPosition() which returns with the a latch on the rightmost leaf page and a lock on the rightmost leaf row on that page. It will loop until it can get the lock without waiting while holding the latch. At this point the slot position is just right of the locked row. 2) in fetchMax() it loops backward on the last leaf page, locking rows as it does so, until it either finds the first non-deleted and locks that row without having to wait and thus did not give up the latch on the page. If successful it returns that row. 3) If it is not successful in this last page search it faults over to the original implementation of max scan, which is simply a search from left to right at the leaf level for the last row in the table.


Field Summary
 
Fields inherited from class org.apache.derby.impl.store.access.btree.BTreeScan
fetchNext_one_slot_array, init_fetchDesc, init_forUpdate, init_hold, init_lock_fetch_desc, init_qualifier, init_rawtran, init_scanColumnList, init_startKeyValue, init_startSearchOperator, init_stopKeyValue, init_stopSearchOperator, init_template, init_useUpdateLocks, lock_operation, SCAN_DONE, SCAN_HOLD_INIT, SCAN_HOLD_INPROGRESS, SCAN_INIT, SCAN_INPROGRESS, scan_position, scan_state, stat_numdeleted_rows_visited, stat_numpages_visited, stat_numrows_qualified, stat_numrows_visited
 
Fields inherited from class org.apache.derby.impl.store.access.btree.OpenBTree
btree_undo, container, err_containerid, init_lock_level, init_open_user_scans, runtime_mem
 
Fields inherited from interface org.apache.derby.iapi.store.access.ScanController
GE, GT, NA
 
Constructor Summary
BTreeMaxScan()
           
 
Method Summary
 boolean fetchMax(DataValueDescriptor[] fetch_row)
          Fetch the maximum row in the table.
private  boolean fetchMaxRowFromBeginning(DataValueDescriptor[] fetch_row)
          Fetch the maximum non-deleted row from the table.
protected  int fetchRows(BTreeRowPosition pos, DataValueDescriptor[][] row_array, RowLocation[] rowloc_array, BackingStoreHashtable hash_table, long max_rowcnt, int[] key_column_numbers)
          disallow fetchRows on this scan type, caller should only be able to call fetchMax().
protected  void positionAtStartPosition(BTreeRowPosition pos)
          Position scan at "start" position of the MAX scan.
 
Methods inherited from class org.apache.derby.impl.store.access.btree.BTreeScan
close, closeForEndTransaction, delete, didNotQualify, doesCurrentPositionQualify, fetch, fetchLocation, fetchNext, fetchNextGroup, fetchNextGroup, fetchSet, fetchWithoutQualify, getCurrentRecordHandleForDebugging, getScanInfo, init, isCurrentPositionDeleted, isHeldAfterCommit, isKeyed, newRowLocationTemplate, next, positionAtDoneScan, positionAtDoneScanFromClose, positionAtNextPage, positionAtRowLocation, positionAtStartForForwardScan, process_qualifier, reopenScan, reopenScanByRowLocation, replace, reposition, savePositionAndReleasePage, savePositionAndReleasePage, toString
 
Methods inherited from class org.apache.derby.impl.store.access.btree.OpenBTree
checkConsistency, debugConglomerate, getColumnSortOrderInfo, getConglomerate, getContainer, getContainerHandle, getEstimatedRowCount, getHeight, getHold, getLockingPolicy, getLockLevel, getOpenMode, getRawTran, getRuntimeMem, getSpaceInfo, getXactMgr, init, isClosed, isIndexableRowConsistent, isTableLocked, reopen, setEstimatedRowCount, setLockingPolicy, test_errors
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface org.apache.derby.iapi.store.access.GenericScanController
isTableLocked
 
Methods inherited from interface org.apache.derby.iapi.store.access.RowCountable
getEstimatedRowCount, setEstimatedRowCount
 

Constructor Detail

BTreeMaxScan

public BTreeMaxScan()
Method Detail

fetchMaxRowFromBeginning

private boolean fetchMaxRowFromBeginning(DataValueDescriptor[] fetch_row)
                                  throws StandardException
Fetch the maximum non-deleted row from the table. Scan from left to right at the leaf level searching for the rightmost non deleted row in the index.

Throws:
StandardException - Standard exception policy.

fetchRows

protected int fetchRows(BTreeRowPosition pos,
                        DataValueDescriptor[][] row_array,
                        RowLocation[] rowloc_array,
                        BackingStoreHashtable hash_table,
                        long max_rowcnt,
                        int[] key_column_numbers)
                 throws StandardException
disallow fetchRows on this scan type, caller should only be able to call fetchMax().

Specified by:
fetchRows in class BTreeScan
Throws:
StandardException - Standard exception policy.

positionAtStartPosition

protected void positionAtStartPosition(BTreeRowPosition pos)
                                throws StandardException
Position scan at "start" position of the MAX scan.

Positions the scan to the slot just after the last record on the rightmost leaf of the index. Returns the rightmost leaf page latched, the rightmost row on the page locked and sets "current_slot" to the slot number just right of the last row on the page.

Specified by:
positionAtStartPosition in class BTreeScan
Throws:
StandardException - Standard exception policy.

fetchMax

public boolean fetchMax(DataValueDescriptor[] fetch_row)
                 throws StandardException
Fetch the maximum row in the table. Call positionAtStartPosition() to quickly position on rightmost row of rightmost leaf of tree. Search last page for last non deleted row, and if one is found return it as max. If no row found on last page, or could not find row withou losing latch then call fetchMaxRowFromBeginning() to search from left to right for maximum value in index.

Throws:
StandardException - Standard exception policy.

Built on Thu 2011-03-10 11:54:14+0000, from revision ???

Apache Derby V10.6 Internals - Copyright © 2004,2007 The Apache Software Foundation. All Rights Reserved.