Class BTreeController

java.lang.Object
org.apache.derby.impl.store.access.btree.OpenBTree
org.apache.derby.impl.store.access.btree.BTreeController
All Implemented Interfaces:
ConglomerateController, ConglomPropertyQueryable
Direct Known Subclasses:
B2IController

public class BTreeController extends OpenBTree implements ConglomerateController
A b-tree controller corresponds to an instance of an open b-tree conglomerate.

Concurrency Notes

The concurrency rules are derived from OpenBTree.

See Also:
  • Field Details

    • scratch_template

      transient DataValueDescriptor[] scratch_template
    • get_insert_row_lock

      boolean get_insert_row_lock
      Whether to get lock on the row being inserted, usually this lock has already been gotten when the row was inserted into the base table.
    • NO_MATCH

      private static final int NO_MATCH
      See Also:
    • MATCH_FOUND

      private static final int MATCH_FOUND
      See Also:
    • RESCAN_REQUIRED

      private static final int RESCAN_REQUIRED
      See Also:
  • Constructor Details

    • BTreeController

      public BTreeController()
  • Method Details

    • reclaim_deleted_rows

      private boolean reclaim_deleted_rows(OpenBTree open_btree, long pageno) throws StandardException
      Attempt to reclaim committed deleted rows from the page.

      Get exclusive latch on page, and then loop backward through page searching for deleted rows which are committed. The routine assumes that it is called from a transaction which cannot have deleted any rows on the page. For each deleted row on the page it attempts to get an exclusive lock on the deleted row, NOWAIT. If it succeeds, and since this row did not delete the row then the row must have been deleted by a transaction which has committed, so it is safe to purge the row. It then purges the row from the page.

      Note that this routine may remove all rows from the page, it will not attempt a merge in this situation. This is because this routine is called from split which is attempting an insert on the given page, so it would be a waste to merge the page only to split it again to allow the insert of the row causing the split.

      Parameters:
      open_btree - The already open btree to use to get latch on page.
      pageno - The page number of the leaf to attempt the reclaim on.
      Returns:
      true if at least one row was purged. If true, then the routine will leave the page latched, and the caller will release the latch by committing or aborting the transaction. The latch must be held to end transaction to insure space on the page remains available for a undo of the purge.
      Throws:
      StandardException - Standard exception policy.
    • start_xact_and_dosplit

      private long start_xact_and_dosplit(boolean attempt_to_reclaim_deleted_rows, long leaf_pageno, DataValueDescriptor[] scratch_template, DataValueDescriptor[] rowToInsert, int flag) throws StandardException
      Start an internal transaction and do the split.

      This routine starts a new transaction, and handles any errors that may come during the transaction. This transation must not obtain any locks as they are likely to conflict with the current user transaction.

      If attempt_to_reclaim_deleted_rows is true this routine will attempt to reclaim space on the leaf page input, by purging committed deleted rows from the leaf. If it succeeds in purging at least one row, then it will commit the internal transaction and return without actually performing a split.

      Parameters:
      scratch_template - A scratch template used to search a page.
      rowToInsert - The row to insert, make sure during split to make room for this row.
      Throws:
      StandardException - Standard exception policy.
    • comparePreviousRecord

      private int comparePreviousRecord(int slot, LeafControlRow leaf, DataValueDescriptor[] rows, DataValueDescriptor[] oldRows) throws StandardException
      Compares the oldrow with the one at 'slot' or the one left to it. If the slot is first slot it will move to the left sibiling of the 'leaf' and will compare with the record from the last slot.
      Parameters:
      slot - slot number to start with
      leaf - LeafControlRow of the current page
      rows - DataValueDescriptot array to fill it with fetched values
      Returns:
      0 if no duplicate 1 if duplicate 2 if rescan required
      Throws:
      StandardException
    • compareNextRecord

      private int compareNextRecord(int slot, LeafControlRow leaf, DataValueDescriptor[] rows, DataValueDescriptor[] oldRows) throws StandardException
      Compares the new record with the one at slot or the one right to it. If the slot is last slot in the page it will move to the right to sibling of the leaf and will compare with the record from the last slot.
      Parameters:
      slot - slot number to start with
      leaf - LeafControlRow of the current page
      rows - DataValueDescriptot array to fill it with fetched values
      Returns:
      0 if no duplicate 1 if duplicate 2 if rescan required
      Throws:
      StandardException
    • compareRowsForInsert

      private int compareRowsForInsert(DataValueDescriptor[] originalRow, DataValueDescriptor[] newRow, LeafControlRow leaf, int slot) throws StandardException
      Compares two rows for insert. If the two rows are not equal, NO_MATCH is returned. Otherwise, it tries to get a lock on the row in the tree. If the lock is obtained without waiting, MATCH_FOUND is returned (even if the row has been deleted). Otherwise, RESCAN_REQUIRED is returned to indicate that the latches have been released and the B-tree must be rescanned. If MATCH_FOUND is returned, the caller should check whether the row has been deleted. If so, it may have to move to check the adjacent rows to be sure that there is no non-deleted duplicate row. If MATCH_FOUND or RESCAN_REQUIRED is returned, the transaction will hold an update lock on the specified record when the method returns. Note! This method should only be called when the index is almost unique (that is, a non-unique index backing a unique constraint).
      Parameters:
      originalRow - row from the tree
      newRow - row to be inserted
      leaf - leaf where originalRow resides
      slot - slot where originalRow
      Returns:
      NO_MATCH if no duplicate is found, MATCH_FOUND if a duplicate is found, or RESCAN_REQUIRED if the B-tree must be rescanned
      Throws:
      StandardException
    • compareLeftAndRightSiblings

      private int compareLeftAndRightSiblings(DataValueDescriptor[] rowToInsert, int insert_slot, LeafControlRow targetleaf) throws StandardException
      Compares immidiate left and right records to check for duplicates. This methods compares new record (being inserted) with the record in immidate left and right postion to see if its duplicate (only for almost unique index and for non null keys)
      Parameters:
      rowToInsert - row being inserted
      insert_slot - slot where rowToInsert is being inserted
      targetleaf - page where rowToInsert
      Returns:
      0 if no duplicate 1 if duplicate 2 if rescan required
      Throws:
      StandardException
    • doIns

      private int doIns(DataValueDescriptor[] rowToInsert) throws StandardException
      Insert a row into the conglomerate.
      Parameters:
      rowToInsert - The row to insert into the conglomerate. The stored representations of the row's columns are copied into a new row somewhere in the conglomerate.
      Returns:
      Returns 0 if insert succeeded. Returns ConglomerateController.ROWISDUPLICATE if conglomerate supports uniqueness checks and has been created to disallow duplicates, and the row inserted had key columns which were duplicate of a row already in the table. Other insert failures will raise StandardException's.
      Throws:
      StandardException - Standard exception policy.
    • do_load_insert

      private boolean do_load_insert(DataValueDescriptor[] rowToInsert, LeafControlRow leaf, int insert_slot) throws StandardException
      Just insert the row on the current page/slot if it fits.

      Throws:
      StandardException - Standard exception policy.
    • do_load_split

      private LeafControlRow do_load_split(DataValueDescriptor[] rowToInsert, LeafControlRow leaf) throws StandardException
      Create room to insert a row to the right of the largest key in table.

      Perform a split pass on the tree which will move the largest key in leaf right to a new leaf, splitting parent branch pages as necessary.

      Throws:
      StandardException - Standard exception policy.
    • init

      public void init(TransactionManager xact_manager, boolean hold, ContainerHandle container, Transaction rawtran, int open_mode, int lock_level, BTreeLockingPolicy btree_locking_policy, BTree conglomerate, LogicalUndo undo, StaticCompiledOpenConglomInfo static_info, DynamicCompiledOpenConglomInfo dynamic_info) throws StandardException
      Initialize the controller for use.

      Any changes to this method will probably have to be reflected in close as well.

      Currently delegates to OpenBTree. If the btree controller ends up not having any state of its own, we can remove this method (the VM will dispatch to OpenBTree), gaining some small efficiency. For now, this method remains for clarity.

      Throws:
      StandardException - Standard exception policy.
    • close

      public void close() throws StandardException
      Close the conglomerate controller.

      Any changes to this method will probably have to be reflected in close as well.

      Currently delegates to OpenBTree. If the btree controller ends up not having any state of its own, we can remove this method (the VM will dispatch to OpenBTree), gaining some small efficiency. For now, this method remains for clarity.

      Specified by:
      close in interface ConglomerateController
      Overrides:
      close in class OpenBTree
      Throws:
      StandardException - Standard exception policy.
      See Also:
    • closeForEndTransaction

      public boolean closeForEndTransaction(boolean closeHeldScan) throws StandardException
      Close conglomerate controller as part of terminating a transaction.

      Use this call to close the conglomerate controller resources as part of committing or aborting a transaction. The normal close() routine may do some cleanup that is either unnecessary, or not correct due to the unknown condition of the controller following a transaction ending error. Use this call when closing all controllers as part of an abort of a transaction.

      This call is meant to only be used internally by the Storage system, clients of the storage system should use the simple close() interface.

      RESOLVE (mikem) - move this call to ConglomerateManager so it is obvious that non-access clients should not call this.

      Specified by:
      closeForEndTransaction in interface ConglomerateController
      Parameters:
      closeHeldScan - If true, means to close controller even if it has been opened to be kept opened across commit. This is used to close these controllers on abort.
      Returns:
      boolean indicating that the close has resulted in a real close of the controller. A held scan will return false if called by closeForEndTransaction(false), otherwise it will return true. A non-held scan will always return true.
      Throws:
      StandardException - Standard exception policy.
    • insert

      public int insert(DataValueDescriptor[] row) throws StandardException
      Insert a row into the conglomerate.
      Specified by:
      insert in interface ConglomerateController
      Parameters:
      row - The row to insert into the conglomerate. The stored representations of the row's columns are copied into a new row somewhere in the conglomerate.
      Returns:
      Returns 0 if insert succeeded. Returns ConglomerateController.ROWISDUPLICATE if conglomerate supports uniqueness checks and has been created to disallow duplicates, and the row inserted had key columns which were duplicate of a row already in the table. Other insert failures will raise StandardException's.
      Throws:
      StandardException - Standard exception policy.
      See Also:
    • isKeyed

      public boolean isKeyed()
      Return whether this is a keyed conglomerate.

      All b-trees are keyed.

      Specified by:
      isKeyed in interface ConglomerateController
      See Also:
    • getTableProperties

      public void getTableProperties(Properties prop) throws StandardException
      Request the system properties associated with a table.

      Request the value of properties that are associated with a table. The following properties can be requested: derby.storage.pageSize derby.storage.pageReservedSpace derby.storage.minimumRecordSize derby.storage.initialPages

      To get the value of a particular property add it to the property list, and on return the value of the property will be set to it's current value. For example: get_prop(ConglomerateController cc) { Properties prop = new Properties(); prop.put("derby.storage.pageSize", ""); cc.getTableProperties(prop); System.out.println( "table's page size = " + prop.getProperty("derby.storage.pageSize"); }

      Specified by:
      getTableProperties in interface ConglomPropertyQueryable
      Parameters:
      prop - Property list to fill in.
      Throws:
      StandardException - Standard exception policy.
    • getInternalTablePropertySet

      public Properties getInternalTablePropertySet(Properties prop) throws StandardException
      Request set of properties associated with a table.

      Returns a property object containing all properties that the store knows about, which are stored persistently by the store. This set of properties may vary from implementation to implementation of the store.

      This call is meant to be used only for internal query of the properties by jbms, for instance by language during bulk insert so that it can create a new conglomerate which exactly matches the properties that the original container was created with. This call should not be used by the user interface to present properties to users as it may contain properties that are meant to be internal to jbms. Some properties are meant only to be specified by jbms code and not by users on the command line.

      Note that not all properties passed into createConglomerate() are stored persistently, and that set may vary by store implementation.

      Specified by:
      getInternalTablePropertySet in interface ConglomPropertyQueryable
      Parameters:
      prop - Property list to add properties to. If null, routine will create a new Properties object, fill it in and return it.
      Throws:
      StandardException - Standard exception policy.
    • load

      public long load(TransactionManager xact_manager, boolean createConglom, RowLocationRetRowSource rowSource) throws StandardException
      Load rows from rowSource into the opened btree.

      Efficiently load rows into the already opened btree. The btree must be table locked, as no row locks will be requested by this routine. On exit from this routine the conglomerate will be closed (on both error or success).

      This routine does an almost bottom up build of a btree. It assumes all rows arrive in sorted order, and inserts them directly into the next (to the right) spot in the current leaf until there is no space. Then it calls the generic split code to add the next leaf (RESOLVE - in the future we could optimize this to split bottom up rather than top down for create index).

      Throws:
      StandardException - Standard exception policy. If conglomerate supports uniqueness checks and has been created to disallow duplicates, and one of the rows being loaded had key columns which were duplicate of a row already in the conglomerate, then raise SQLState.STORE_CONGLOMERATE_DUPLICATE_KEY_EXCEPTION.
      See Also:
    • delete

      public boolean delete(RowLocation loc) throws StandardException
      Delete a row from the conglomerate.
      Specified by:
      delete in interface ConglomerateController
      Returns:
      Returns true if delete was successful, false if the record pointed at no longer represents a valid record.
      Throws:
      StandardException - Standard exception policy.
      See Also:
    • fetch

      public boolean fetch(RowLocation loc, DataValueDescriptor[] row, FormatableBitSet validColumns) throws StandardException
      Fetch the row at the given location.
      Specified by:
      fetch in interface ConglomerateController
      Parameters:
      loc - The "RowLocation" which describes the exact row to fetch from the table.
      row - The row to read the data into.
      validColumns - A description of which columns to return from row on the page into "destRow." destRow and validColumns work together to describe the row to be returned by the fetch - see RowUtil for description of how these three parameters work together to describe a fetched "row".
      Returns:
      Returns true if fetch was successful, false if the record pointed at no longer represents a valid record.
      Throws:
      StandardException - Standard exception policy.
      See Also:
    • fetch

      public boolean fetch(RowLocation loc, DataValueDescriptor[] row, FormatableBitSet validColumns, boolean waitForLock) throws StandardException
      Fetch the row at the given location.
      Specified by:
      fetch in interface ConglomerateController
      Parameters:
      loc - The "RowLocation" which describes the exact row to fetch from the table.
      row - The row to read the data into.
      validColumns - A description of which columns to return from row on the page into "destRow." destRow and validColumns work together to describe the row to be returned by the fetch - see RowUtil for description of how these three parameters work together to describe a fetched "row".
      waitForLock - If false, then the call will throw a lock timeout exception immediately, if the lock can not be granted without waiting. If true call will act exactly as fetch() interface with no waitForLock parameter.
      Returns:
      Returns true if fetch was successful, false if the record pointed at no longer represents a valid record.
      Throws:
      StandardException - Standard exception policy.
      See Also:
    • insertAndFetchLocation

      public void insertAndFetchLocation(DataValueDescriptor[] row, RowLocation templateRowLocation) throws StandardException
      Insert a row into the conglomerate, and store its location in the provided template row location. Unimplemented by btree.
      Specified by:
      insertAndFetchLocation in interface ConglomerateController
      Parameters:
      row - The row to insert into the conglomerate. The stored representations of the row's columns are copied into a new row somewhere in the conglomerate.
      templateRowLocation - The rowlocation to read the inserted row location into.
      Throws:
      StandardException - Standard exception policy.
      See Also:
    • newRowLocationTemplate

      public RowLocation newRowLocationTemplate() throws StandardException
      Return a row location object of the correct type to be used in calls to insertAndFetchLocation.
      Specified by:
      newRowLocationTemplate in interface ConglomerateController
      Throws:
      StandardException - Standard exception policy.
      See Also:
    • lockRow

      public boolean lockRow(RowLocation loc, int lock_operation, boolean wait, int lock_duration) throws StandardException
      Lock the given row location.

      Should only be called by access.

      This call can be made on a ConglomerateController that was opened for locking only.

      RESOLVE (mikem) - move this call to ConglomerateManager so it is obvious that non-access clients should not call this.

      Specified by:
      lockRow in interface ConglomerateController
      Parameters:
      loc - The "RowLocation" which describes the exact row to lock.
      lock_operation - For what operation are we requesting the lock, this should be one of the following 4 options: LOCK_READ [read lock], (LOCK_INS | LOCK_UPD) [ lock for insert], (LOCK_INSERT_PREVKEY | LOCK_UPD) [lock for previous key to insert], (LOCK_UPD) [lock for delete or replace] (LOCK_UPD | LOCK_UPDATE_LOCKS) [lock scan for update, will upgrade lock later if actual update is take place]
      wait - Should the lock call wait to be granted?
      lock_duration - If set to TransactionManager.LOCK_INSTANT_DURATION, then lock will be released immediately after being granted.
      Returns:
      true if lock was granted, only can be false if wait was false.
      Throws:
      StandardException - Standard exception policy.
    • lockRow

      public boolean lockRow(long page_num, int record_id, int lock_operation, boolean wait, int lock_duration) throws StandardException
      Description copied from interface: ConglomerateController
      Lock the given record id/page num pair.

      Should only be called by access, to lock "special" locks formed from the Recordhandle.* reserved constants for page specific locks.

      This call can be made on a ConglomerateController that was opened for locking only.

      RESOLVE (mikem) - move this call to ConglomerateManager so it is obvious that non-access clients should not call this.

      Specified by:
      lockRow in interface ConglomerateController
      Parameters:
      page_num - page number of record to lock.
      record_id - record id of record to lock.
      lock_operation - For what operation are we requesting the lock, this should be one of the following 4 options: LOCK_READ [read lock], (LOCK_INS | LOCK_UPD) [ lock for insert], (LOCK_INSERT_PREVKEY | LOCK_UPD) [lock for previous key to insert], (LOCK_UPD) [lock for delete or replace] (LOCK_UPD | LOCK_UPDATE_LOCKS) [lock scan for update, will upgrade lock later if actual update is take place]
      wait - Should the lock call wait to be granted?
      lock_duration - If set to TransactionManager.LOCK_INSTANT_DURATION, then lock will be released immediately after being granted.
      Returns:
      true if lock was granted, only can be false if wait was false.
      Throws:
      StandardException - Standard exception policy.
    • unlockRowAfterRead

      public void unlockRowAfterRead(RowLocation loc, boolean forUpdate, boolean row_qualifies) throws StandardException
      Description copied from interface: ConglomerateController
      UnLock the given row location.

      Should only be called by access.

      This call can be made on a ConglomerateController that was opened for locking only.

      RESOLVE (mikem) - move this call to ConglomerateManager so it is obvious that non-access clients should not call this.

      Specified by:
      unlockRowAfterRead in interface ConglomerateController
      Parameters:
      loc - The "RowLocation" which describes the row to unlock.
      forUpdate - Row was locked for read or update.
      row_qualifies - Row was qualified and returned to the user.
      Throws:
      StandardException - Standard exception policy.
    • replace

      public boolean replace(RowLocation loc, DataValueDescriptor[] row, FormatableBitSet validColumns) throws StandardException
      Replace the entire row at the given location.
      Specified by:
      replace in interface ConglomerateController
      Returns:
      true if update was successful, returns false if the update fails because the record pointed at no longer represents a valid record.
      Throws:
      StandardException - Standard exception policy.
      See Also: