Package org.apache.derby.impl.store.access.btree

Class ControlRow

  • All Implemented Interfaces:
    TypedFormat, AuxObject
    Direct Known Subclasses:
    BranchControlRow, LeafControlRow
    public abstract class ControlRow
extends java.lang.Object
implements AuxObject, TypedFormat
    Base class for leaf and branch control rows.

    Concurrency Notes

    All access through control rows is serialized by an exclusive latch on the page the control row is for. The page is latched when the control row is "gotten" (ControlRow#Get), and unlatched when the control row is released (ControlRow#release).

    To Do List

    • [NOTE1] The code is arranged to fault in fields from the row as necessary. many of the fields of a control row are rarely used (left sibling, parent). The accessors fault in the underlying column only when requested by allocating the appropriate object and calling fetchFromSlot and only fetching the requested field.
    • [NOTE2] Currently, all the fields of the control row are stored as StorableU8s for simplicity. This is too few bits to hold the long page numbers, and too many to hold the version, level, and isRoot flag. Some consideration will have to be given to the appropriate storage format for these values.
    • [NOTE3] The implementation relies on the existance of page "auxiliary" pointers which keep Object versions of the control row.

    See Also:
    get(org.apache.derby.impl.store.access.btree.OpenBTree, long), release()

    • Field Detail

      • version

        private StorableFormatId version
        Version indentifier of the control row within the page.

        This is the format id of the control row. The format id is currently one of either StoredFormatIds.ACCESS_BTREE_LEAFCONTROLROW_ID or StoredFormatIds.ACCESS_BTREE_BRANCHCONTROLROW_ID.

      • leftSiblingPageNumber

        private SQLLongint leftSiblingPageNumber
        Pointer to page which is "left" at the current level.

        Currently all pages at a level are doubly linked. The leftmost page in a level has a leftSiblingPageNumber == ContainerHandle.INVALID_PAGE_NUMBER. All key values on the page which is left must precede the first key value on the current page.

      • rightSiblingPageNumber

        private SQLLongint rightSiblingPageNumber
        Pointer to page which is "right" at the current level.

        Currently all pages at a level are doubly linked. The rightmost page in a level has a rightSiblingPageNumber == ContainerHandle.INVALID_PAGE_NUMBER. All key values on the page which is right of the current page must follow the last key value on the current page.

      • parentPageNumber

        private SQLLongint parentPageNumber
        The parent page of the current page.

        For consistency checking it is useful to maintain the parentPageNumber field of the current page. The root page has a value of ContainerHandle.INVALID_PAGE_NUMBER in it's parentPageNumber field.

        RESOLVE (mikem) - we need to come up with some way to not maintain these, maybe by providing a property on secondary index or a different 2nd index.

      • level

        private SQLLongint level
        The level of the btree.

        The leaf level of the btree is 0. The first branch level (parent level of the leaf), is level 1. The height of the btree is (level + 1).

        The smallest btree is a one page btree with only a leaf, and no branch pages.

      • isRoot

        private SQLLongint isRoot
        Is this page the root of the btree?

        Currently "1" if the page is the root page, else "0".

        RESOLVE (mikem) When real datatype come about, this value should probably be just a bit in some status word.

      • btree

        private BTree btree
        A copy of the Conglomerate that describes the owning conglom.

        This information is used during logical undo to get the type information so that rows can be compared and searched for. We may be able to get away with a subset of the information stored in the conglomerate.

        RESOLVE (mikem) - change this to only store the info on the root page.

      • page

        protected Page page
        The page that this control row describes.

      • scratch_row

        protected DataValueDescriptor[] scratch_row
        row used to replace fetchFieldFromSlot() calls.

      • fetchDesc

        protected FetchDescriptor fetchDesc
        FetchDescriptor used to replace fetchFieldFromSlot() calls.

      • use_last_search_result_hint

        protected transient boolean use_last_search_result_hint
        In memory hint about whether to use the last_search_result hint during search.

      • last_search_result

        protected transient int last_search_result
        In memory hint about where to begin the binary search to find a key on the the current control page.

      • CR_COLID_FIRST

        protected static final int CR_COLID_FIRST
        Column number assignments for columns of the control row.

        The control row is stored as the first row in a btree page. The row is an array of columns. The Control row columns are the columns numbered from ControlRow.CR_COLID_FIRST through ControlRow.CR_COLID_LAST. The classes which implement the concrete derived classes of ControlRow may add columns to the control row, but they must be added after the ControlRow columns.

        See Also:
        Constant Field Values

      • CR_VERSION_BITSET

        protected static final FormatableBitSet CR_VERSION_BITSET
        bit sets used to fetch single columns at a time.

      • CR_RIGHTSIB_BITSET

        protected static final FormatableBitSet CR_RIGHTSIB_BITSET

      • SPLIT_FLAG_LAST_ON_PAGE

        public static final int SPLIT_FLAG_LAST_ON_PAGE
        Values passed in the flag argument to splitFor.
        See Also:
        Constant Field Values

      • SPLIT_FLAG_LAST_IN_TABLE

        public static final int SPLIT_FLAG_LAST_IN_TABLE
        See Also:
        Constant Field Values

      • SPLIT_FLAG_FIRST_ON_PAGE

        public static final int SPLIT_FLAG_FIRST_ON_PAGE
        See Also:
        Constant Field Values

      • SPLIT_FLAG_FIRST_IN_TABLE

        public static final int SPLIT_FLAG_FIRST_IN_TABLE
        See Also:
        Constant Field Values

      • CR_SLOT

        protected static final int CR_SLOT
        The slot at which all control rows reside.
        See Also:
        Constant Field Values

    • Constructor Detail

      • ControlRow

        protected ControlRow()
        No arg constructor.

        GetControlRowForPage() will call this constructor when it uses the monitor to create a control row dynamically given a given format id.

      • ControlRow

        protected ControlRow​(OpenBTree btree,
                     Page page,
                     int level,
                     ControlRow parent,
                     boolean isRoot)
              throws StandardException
        Constructor for making a new control row as part of allocating a new page. Fills in all the fields but does not write them anywhere.

        Changes to this constructor will probably require changes to the corresponding accessor(s).

        Parameters:
        btree - Static information about the btree.
        page - The page described by this control row.
        parent - The parent page of this page, "null" if this page is root or if not maintaining parent links.
        isRoot - Is this page the root of the tree?
        Throws:
        StandardException - Standard exception policy.

      • ControlRow

        protected ControlRow​(ContainerHandle container,
                     Page page)
              throws StandardException
        Constructor for making a control row for an existing page.

        Not all the fields are filled in; their values will get faulted in from the page as necessary.

        Classes which extend ControlRow must delegate to this constructor and may want to override it as well. Changes to this constructor will probably require changes to the corresponding accessor(s).

        Parameters:
        container - Open container
        page - The page described by this control row.
        Throws:
        StandardException - Standard exception policy.

    • Method Detail

      • getVersion

        protected int getVersion()
                  throws StandardException
        Get version of the control row.

        Returns the version of the control row, faulting it in from the page if necessary.

        Returns:
        version of the control row.
        Throws:
        StandardException - Standard exception policy.

      • setVersion

        protected void setVersion​(int version)
                   throws StandardException
        Set version of the control row.

        Sets the version of the control row. Updates both the in-memory control row and the disk copy.

        Throws:
        StandardException - Standard exception policy.

      • getLeftSibling

        public ControlRow getLeftSibling​(OpenBTree btree)
                          throws StandardException,
                                 WaitError
        Get the control row for this page's left sibling, or null if there is no left sibling (which probably means it's the leftmost page at its level). Since right-to-left traversal of an index level is deadlock-prone, this method will only get get the left sibling if it can latch it without waiting.
        Throws:
        WaitError - if the latch request would have had to wait.
        StandardException - Standard exception policy.

      • getRightSibling

        protected ControlRow getRightSibling​(OpenBTree open_btree)
                              throws StandardException
        Return the control row for this page's right sibling. Unlike getting the left sibling, it's ok to wait for the right sibling latch since left-to-right is the deadlock-free ordering.
        Throws:
        StandardException - Standard exception policy.

      • getleftSiblingPageNumber

        public long getleftSiblingPageNumber()
                              throws StandardException
        Get the page number of the left sibling. Fault it's value in if it hasn't been yet.
        Throws:
        StandardException - Standard exception policy.

      • getrightSiblingPageNumber

        protected long getrightSiblingPageNumber()
                                  throws StandardException
        Get the page number of the right sibling. Fault it's value in if it hasn't been yet.
        Throws:
        StandardException - Standard exception policy.

      • getParentPageNumber

        protected long getParentPageNumber()
                            throws StandardException
        Get the page number of the parent, if it's being maintained. Note that there is intentionally no way to get the control row for the parent page - the b-tree code NEVER traverses up the tree, even in consistency checks.
        Throws:
        StandardException - Standard exception policy.

      • getConglom

        public BTree getConglom​(int format_id)
                 throws StandardException
        Get format id information for row on page.

        Returns the format id information for a row on the page. faulting it in from the page if necessary.

        Returns:
        format id of a row on the page.
        Throws:
        StandardException - Standard exception policy.

      • get

        public static ControlRow get​(OpenBTree open_btree,
                             long pageNumber)
                      throws StandardException
        Get the control row from the given page in the b-tree. The returned control row will be of the correct type for the page (i.e., either a LeafControlRow or a BranchControlRow).
        Throws:
        StandardException - Standard exception policy.

      • getNoWait

        public static ControlRow getNoWait​(OpenBTree open_btree,
                                   long pageNumber)
                            throws StandardException
        Get the control row for the given page if the latch on the page can be obtained without waiting, else return null.
        Throws:
        StandardException - Standard exception policy.

      • release

        public void release()
        Release this control row's resources.

      • searchForEntry

        protected void searchForEntry​(SearchParameters params)
                       throws StandardException
        Search this index page.

        This method is very performance sensitive. It is the intention that no object allocations occur during the execution of this method.

        This method performs a binary search on the page and finds the entry i on the page such that entry[i] <= key < entry[i+1]. The result of the search is filled into the passed in params structure.

        Parameters:
        params - the parameters of the search
        Throws:
        StandardException - could be thrown by underlying raw store operations.
        See Also:
        SearchParameters

      • compareIndexRowFromPageToKey

        public static int compareIndexRowFromPageToKey​(ControlRow indexpage,
                                               int slot,
                                               DataValueDescriptor[] indexrow,
                                               DataValueDescriptor[] key,
                                               int nCompareCols,
                                               int partialKeyOrder,
                                               boolean[] ascOrDesc)
                                        throws StandardException
        Compare two orderable rows, considering nCompareCols, and return -1, 0, or 1 depending on whether the first row (indexrow) is less than, equal to, or greater than the second (key). The key may have fewer columns present than nCompareCols. In such a case, if all the columns of the partial key match all of the corresponding columns in the index row, then the value passed in in partialKeyOrder is returned. The caller should pass in partialKeyOrder=1 if the index rows which match a partial key should be considered to be greater than the partial key, and -1 if they should be considered to be less. This routine only reads objects off the page if it needs them, so if a multi-part key differs in the first column the subsequent columns are not read.
        Parameters:
        indexpage - Controlrow of page to get target row from.
        slot - Slot to get control row from.
        indexrow - template of the target row (the row in the index).
        key - the (possibly partial) search key.
        nCompareCols - the number of columns to compare.
        partialKeyOrder - what to return on a partial key match.
        ascOrDesc - column sort order information
        Throws:
        StandardException - if lower levels have a problem.

      • checkGeneric

        protected void checkGeneric​(OpenBTree btree,
                            ControlRow parent,
                            boolean check_other_pages)
                     throws StandardException
        Perform consistency checks which are common to all pages that derive from ControlRow (both leaf and branch pages). The checks are:
      • This page thinks the parent argument is actually its parent.
      • The level of this page is 1 less than the level of the parent.
      • All the rows on the page are in order.
      • Both left and right siblings, if they exist, are at the same level of this page.
      • This page is the left sibling of its right sibling, and it's the right sibling of its left sibling.
      • The last row on the left sibling is < the first row on this page.
      • The first row on the right sibling is > than the the last row on this page.
        • Note that these last two are really only true if there are never duplicate keys.
        Throws:
        StandardException - Standard exception policy.

      • checkRowOrder

        protected boolean checkRowOrder​(OpenBTree btree,
                                ControlRow parent)
                         throws StandardException
        Check that all rows on the page are in order. This means that each key is > than the previous key.
        Throws:
        StandardException - Standard exception policy.

      • checkSiblings

        protected void checkSiblings​(OpenBTree btree)
                      throws StandardException
        Perform checks on the siblings of this page: make sure that they're at the same level as this page, that they're mutually linked together, and that the first/last keys on sibling pages are in order.
        Throws:
        StandardException - Standard exception policy.

      • linkRight

        void linkRight​(OpenBTree btree,
               ControlRow target)
        throws StandardException
        Link this page to the right of the target page.

        Upon entry, this page and the target must be latched. Upon exit, this page and the target remain latched.

        This method carefully acquires pages from left to right in order to avoid deadlocks.

        Throws:
        StandardException - Standard exception policy.

      • unlink

        boolean unlink​(OpenBTree btree)
        throws StandardException
        Unlink this page from its siblings. This method will give up and return false rather than run the risk of a deadlock.

        On entry this page must be latched. The siblings are latched and unlatched during the operation. Upon exit, this page will remain latched, but unlinked from its siblings and deallocated from the container.

        The seemingly odd situation that this page will be returned latched but deallocated is intentional. The container will not be able to reuse this page until the latch is released, and the caller may still need to read information out of it.

        Throws:
        StandardException - Standard exception policy.

      • getPage

        public Page getPage()

      • getRow

        protected final DataValueDescriptor[] getRow()
        Get the row.

        Return the object array that represents the control row for use in raw store fetch, insert, and/or update.

        Returns:
        The row.

      • checkConsistency

        protected abstract int checkConsistency​(OpenBTree btree,
                                        ControlRow parent,
                                        boolean check_other_pages)
                                 throws StandardException
        Check consistency of the page and its children, returning the number of pages seen, and throwing errors if inconsistencies are found.

        Parameters:
        btree - The open btree to associate latches/locks with.
        parent - The parent page of this page, "null" if this page is root or if not maintaining parent links.
        check_other_pages - Should the consistency check go to other pages (this option breaks the latch protocol).
        Returns:
        The identifier to be used to open the conglomerate later.
        Throws:
        StandardException - Standard exception policy.

      • getLeftChild

        protected abstract ControlRow getLeftChild​(OpenBTree btree)
                                    throws StandardException
        Return the left child pointer for the page.

        Leaf pages don't have children, so they override this and return null.

        Parameters:
        btree - The open btree to associate latches/locks with.
        Returns:
        The page which is the leftmost child of this page.
        Throws:
        StandardException - Standard exception policy.

      • getRightChild

        protected abstract ControlRow getRightChild​(OpenBTree btree)
                                     throws StandardException
        Return the right child pointer for the page.

        Leaf pages don't have children, so they override this and return null.

        Parameters:
        btree - The open btree to associate latches/locks with.
        Returns:
        The page which is the rightmost child of this page.
        Throws:
        StandardException - Standard exception policy.

      • controlRowInit

        protected abstract void controlRowInit()
        Perform page specific initialization.

      • isLeftmostLeaf

        public abstract boolean isLeftmostLeaf()
                                throws StandardException
        Is the current page the leftmost leaf of tree?

        Returns:
        true if the current page is the leftmost leaf of the tree, else return false.
        Throws:
        StandardException - Standard exception policy.

      • isRightmostLeaf

        public abstract boolean isRightmostLeaf()
                                 throws StandardException
        Is the current page the rightmost leaf of tree?

        Returns:
        true if the current page is the rightmost leaf of the tree, else return false.
        Throws:
        StandardException - Standard exception policy.

      • search

        public abstract ControlRow search​(SearchParameters search_params)
                           throws StandardException
        Perform a recursive search, ultimately returning the latched leaf page and row slot after which the given key belongs. The slot is returned in the result structure. If the key exists on the page, the resultExact field will be true. Otherwise, resultExact field will be false, and the row slot returned will be the one immediately preceding the position at which the key belongs.
        Throws:
        StandardException - Standard exception policy.

      • getNumberOfControlRowColumns

        protected abstract int getNumberOfControlRowColumns()
        Get the number of columns in the control row.

        Control rows all share the first columns as defined by this class and then add columns to the end of the control row. For instance a branch control row add a child page pointer field.

        Returns:
        The total number of columns in the control row.

      • searchLeft

        protected abstract ControlRow searchLeft​(OpenBTree btree)
                                  throws StandardException
        Search and return the left most leaf page.

        Perform a recursive search, ultimately returning the leftmost leaf page which is the first leaf page in the leaf sibling chain. (This method might better be called getFirstLeafPage()).

        Parameters:
        btree - The open btree to associate latches/locks with.
        Returns:
        The leftmost leaf page.
        Throws:
        StandardException - Standard exception policy.

      • searchRight

        protected abstract ControlRow searchRight​(OpenBTree btree)
                                   throws StandardException
        Search and return the right most leaf page.

        Perform a recursive search, ultimately returning the rightmost leaf page which is the last leaf page in the leaf sibling chain. (This method might better be called getLastLeafPage()).

        Parameters:
        btree - The open btree to associate latches/locks with.
        Returns:
        The rightmost leaf page.
        Throws:
        StandardException - Standard exception policy.

      • shrinkFor

        protected abstract boolean shrinkFor​(OpenBTree btree,
                                     DataValueDescriptor[] key)
                              throws StandardException
        Perform a recursive shrink operation for the key. If this method returns true, the caller should remove the corresponding entry for the page. This routine is not guaranteed to successfully shrink anything. The page lead to by the key might turn out not to be empty by the time shrink gets there, and shrinks will give up if there is a deadlock.

        As currently implemented shrinkFor must be executed while holding an exclusive container lock on the entire table. It is expected that this call is made within an internal transaction which has been called by a post commit thread. Latches are released by the code. The raw store guarantees that deallocated pages are not seen by other xacts until the transaction has been committed.

        Note that a non-table level lock implementation must hold latches on pages affected until end transaction.

        On entry, the current page is latched. On exit, all pages will have been unlatched.

        Throws:
        StandardException - Standard exception policy.

      • splitFor

        protected abstract long splitFor​(OpenBTree open_btree,
                                 DataValueDescriptor[] template,
                                 BranchControlRow parentpage,
                                 DataValueDescriptor[] row,
                                 int flag)
                          throws StandardException
        Perform a top down split pass making room for the the key in "row".

        Perform a split such that a subsequent call to insert given the argument index row will likely find room for it. Since latches are released the client must code for the case where another user has grabbed the space made available by the split pass and be ready to do another split.

        Parameters:
        open_btree - The open btree to associate latches with.
        template - A scratch area to use while searching for split pass.
        parentpage - The parent page of the current page in the split pass. starts at null for root.
        row - The key to make room for during the split pass.
        flag - A flag used to direct where point of split should be chosen.
        Returns:
        page number of the newly allocated leaf page created by split.
        Throws:
        StandardException - Standard exception policy.

      • auxObjectInvalidated

        public void auxObjectInvalidated()
        Called when the page is being evicted from cache or when a rollback happened on the page and may possibly have changed the control row's value
        Specified by:
        auxObjectInvalidated in interface AuxObject
        See Also:
        AuxObject.auxObjectInvalidated()

      • getRowTemplate

        public DataValueDescriptor[] getRowTemplate​(OpenBTree open_btree)
                                     throws StandardException
        Return a new template for reading a data row from the current page.

        Default implementation for rows which are the same as the conglomerates template, sub-classes can alter if underlying template is different (for instance branch rows add an extra field at the end).

        Returns:
        Newly allocated template.
        Throws:
        StandardException - Standard exception policy.

      • debugPage

        public java.lang.String debugPage​(OpenBTree open_btree)
                           throws StandardException
        Dump complete information about control row and rows on the page.

        Returns:
        string with all info.
        Throws:
        StandardException - Standard exception policy.

      • toString

        public java.lang.String toString()
        The standard toString().

        This is a concise print out of the info in the control row, does not include anything the page.

        Overrides:
        toString in class java.lang.Object