btreecostcontroller.java

derby database source code.good for you.

     *                            set then each scan will be costed independant
     *                            of any other predicted scan access.
     *
	 * @return The cost of the fetch.
     *
	 * @exception  StandardException  Standard exception policy.
     *
	 * @see RowUtil
     **/
    public double getFetchFromFullKeyCost(
    FormatableBitSet      validColumns,
    int         access_type)
		throws StandardException
    {
        double ret_cost;

        if ((access_type & StoreCostController.STORECOST_CLUSTERED) == 0)
        {
            // uncached fetch
            ret_cost = BTREE_UNCACHED_FETCH_BY_KEY_PER_LEVEL;
        }
        else
        {
            ret_cost = BTREE_SORTMERGE_FETCH_BY_KEY_PER_LEVEL;
        }
        ret_cost *= tree_height;

        return(ret_cost);
    }


    /**
     * Calculate the cost of a scan.
     * <p>
     * Cause this object to calculate the cost of performing the described
     * scan.  The interface is setup such that first a call is made to
     * calcualteScanCost(), and then subsequent calls to accessor routines
     * are made to get various pieces of information about the cost of
     * the scan.
     * <p>
     * For the purposes of costing this routine is going to assume that 
     * a page will remain in cache between the time one next()/fetchNext()
     * call and a subsequent next()/fetchNext() call is made within a scan.
     * <p>
     * The result of costing the scan is placed in the "cost_result".  
     * The cost of the scan is stored by calling 
     * cost_result.setEstimatedCost(cost).
     * The estimated row count is stored by calling 
     * cost_result.setEstimatedRowCount(row_count).
     * <p>
     * The estimated cost of the scan assumes the caller will 
     * execute a fetchNext() loop for every row that qualifies between
     * start and stop position.  Note that this cost is different than
     * execution a next(),fetch() loop; or if the scan is going to be
     * terminated by client prior to reaching the stop condition.
     * <p>
     * The estimated number of rows returned from the scan 
     * assumes the caller will execute a fetchNext() loop for every 
     * row that qualifies between start and stop position.
     * <p>
     *
     *
     * @param scan_type       The type of scan that will be executed.  There
     *                        are currently 2 types:
     *                        STORECOST_SCAN_NORMAL - scans will be executed
     *                        using the standard next/fetch, where each fetch
     *                        can retrieve 1 or many rows (if fetchNextGroup()
     *                        interface is used).
     *
     *                        STORECOST_SCAN_SET - The entire result set will
     *                        be retrieved using the the fetchSet() interface.
     *
     * @param row_count       Estimated total row count of the table.  The 
     *                        current system tracks row counts in heaps better
     *                        than btree's (btree's have "rows" which are not
     *                        user rows - branch rows, control rows), so 
     *                        if available the client should
     *                        pass in the base table's row count into this
     *                        routine to be used as the index's row count.
     *                        If the caller has no idea, pass in -1.
     *
     * @param group_size      The number of rows to be returned by a single
     *                        fetch call for STORECOST_SCAN_NORMAL scans.
     *
	 * @param forUpdate       Should be true if the caller intends to update 
     *                        through the scan.
     * 
	 * @param scanColumnList  A description of which columns to return from 
     *                        every fetch in the scan.  template, 
     *                        and scanColumnList work together
     *                        to describe the row to be returned by the scan - 
     *                        see RowUtil for description of how these three 
     *                        parameters work together to describe a "row".
     * 
     * @param template        A prototypical row which the scan may use to
	 *                        maintain its position in the conglomerate.  Not 
     *                        all access method scan types will require this, 
     *                        if they don't it's ok to pass in null.
     *                        In order to scan a conglomerate one must 
     *                        allocate 2 separate "row" templates.  The "row" 
     *                        template passed into openScan is for the private
     *                        use of the scan itself, and no access to it
     *                        should be made by the caller while the scan is 
     *                        still open.  Because of this the scanner must 
     *                        allocate another "row" template to hold the 
     *                        values returned from fetch().  Note that this 
     *                        template must be for the full row, whether a 
     *                        partial row scan is being executed or not.
     *
	 * @param startKeyValue   An indexable row which holds a (partial) key 
     *                        value which, in combination with the 
     *                        startSearchOperator, defines the starting 
     *                        position of the scan.  If null, the starting
     *                        position of the scan is the first row of the 
     *                        conglomerate.  The startKeyValue must only
     *                        reference columns included in the scanColumnList.
     *
	 * @param startSearchOperator 
     *                        an operator which defines how the startKeyValue
     *                        is to be searched for.  If startSearchOperation 
     *                        is ScanController.GE, the scan starts on the 
     *                        first row which is greater than or equal to the 
	 *                        startKeyValue.  If startSearchOperation is 
     *                        ScanController.GT, the scan starts on the first
     *                        row whose key is greater than startKeyValue.  The
     *                        startSearchOperation parameter is ignored if the
     *                        startKeyValue parameter is null.
     *
	 * @param stopKeyValue    An indexable row which holds a (partial) key 
     *                        value which, in combination with the 
     *                        stopSearchOperator, defines the ending position
     *                        of the scan.  If null, the ending position of the
     *                        scan is the last row of the conglomerate.  The
     *                        stopKeyValue must only reference columns included
     *                        in the scanColumnList.
     *
	 * @param stopSearchOperator
     *                        an operator which defines how the stopKeyValue
     *                        is used to determine the scan stopping position. 
     *                        If stopSearchOperation is ScanController.GE, the
     *                        scan stops just before the first row which is
     *                        greater than or equal to the stopKeyValue.  If 
     *                        stopSearchOperation is ScanController.GT, the 
     *                        scan stops just before the first row whose key 
     *                        is greater than startKeyValue.  The
     *                        stopSearchOperation parameter is ignored if the
     *                        stopKeyValue parameter is null.
     *
     *                        
     * @param access_type     Describe the type of access the query will be
     *                        performing to the ScanController.  
     *
     *                        STORECOST_CLUSTERED - The location of one scan
     *                            is likely clustered "close" to the previous 
     *                            scan.  For instance if the query plan were
     *                            to used repeated "reopenScan()'s" to probe
     *                            for the next key in an index, then this flag
     *                            should be be specified.  If this flag is not 
     *                            set then each scan will be costed independant
     *                            of any other predicted scan access.
     *
     *
	 * @exception  StandardException  Standard exception policy.
     *
	 * @see RowUtil
     **/
	public void getScanCost(
    int                     scan_type,
    long                    row_count,
    int                     group_size,
    boolean                 forUpdate,
    FormatableBitSet                 scanColumnList,
    DataValueDescriptor[]   template,
    DataValueDescriptor[]   startKeyValue,
    int                     startSearchOperator,
    DataValueDescriptor[]   stopKeyValue,
    int                     stopSearchOperator,
    boolean                 reopen_scan,
    int                     access_type,
    StoreCostResult         cost_result)
        throws StandardException
    {
        float       left_of_start;
        float       left_of_stop;
        ControlRow  control_row = null;
        long        input_row_count = (row_count < 0 ? num_rows : row_count);

        try
        {
            // Find the starting page and row slot.
            if (startKeyValue == null)
            {
                left_of_start = 0;
            }
            else
            {
                // Search for the starting row.

                SearchParameters sp = new SearchParameters(
                    startKeyValue, 
                    ((startSearchOperator == ScanController.GE) ? 
                        SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH : 
                        SearchParameters.POSITION_RIGHT_OF_PARTIAL_KEY_MATCH),
                    template, this, true);

                control_row =
                    ControlRow.Get(this, BTree.ROOTPAGEID).search(sp);

                control_row.release();
                control_row = null;

                left_of_start = sp.left_fraction;
            }

            if (stopKeyValue == null)
            {
                left_of_stop = 1;
            }
            else
            {
                // Search for the stopping row.

                SearchParameters sp = 
                    new SearchParameters(
                        stopKeyValue, 
                        ((stopSearchOperator == ScanController.GE) ? 
                          SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH : 
                          SearchParameters.POSITION_RIGHT_OF_PARTIAL_KEY_MATCH),
                        template, this, true);

                control_row =
                    ControlRow.Get(this, BTree.ROOTPAGEID).search(sp);

                control_row.release();
                control_row = null;

                left_of_stop = sp.left_fraction;
            }

            // System.out.println(
              //   "\n\tleft_of_start = " + left_of_start +
                // "\n\tleft_of_stop  = " + left_of_stop);

            // what percentage of rows are between start and stop?

            float ret_fraction = left_of_stop - left_of_start;

            // If for some reason the stop position comes before the start
            // position, assume 0 rows will return from query.
            if (ret_fraction < 0)
                ret_fraction = 0;

            // Never return estimate of more rows than exist, sometimes 
            // the recursive estimation through the btree may return a number
            // like 1.00001.
            if (ret_fraction > 1)
                ret_fraction = 1;

            float estimated_row_count = input_row_count * ret_fraction;

            // first the base cost of positioning on the first row in the scan.
            double cost = 
                getFetchFromFullKeyCost(scanColumnList, access_type);

            // add the base cost of bringing each page for the first time into
            // the cache.  This is basically the cost of bringing each leaf
            // uncached into the cache and reading the control row off of it.:
            cost += 
                (num_pages * ret_fraction) * BASE_UNCACHED_ROW_FETCH_COST;

            // Now some magic to try and figure out the cost of doing a
            // scan along the leaf level of the tree.  Mostly just assume
            // the costs are the same as the heap, and ignore qualifier
            // processing and stop row comparisons for now.

            // the base cost of getting each of the rows from a page assumed
            // to already be cached (by the scan fetch) - this is only for all
            // rows after the initial row on the page has been accounted for
            // under the BASE_UNCACHED_ROW_FETCH_COST cost.:
            long cached_row_count = ((long) estimated_row_count) - num_pages;
            if (cached_row_count < 0)
                cached_row_count = 0;

            if (scan_type == StoreCostController.STORECOST_SCAN_NORMAL)
                cost += cached_row_count * BASE_GROUPSCAN_ROW_COST;
            else
                cost += cached_row_count * BASE_HASHSCAN_ROW_FETCH_COST;

            // finally add the cost associated with the number of bytes in row:
            long row_size = 
                (input_row_count == 0) ? 
                    4 : (num_pages * page_size) / input_row_count;

            cost += 
                (estimated_row_count * row_size) * BASE_ROW_PER_BYTECOST;

            if (SanityManager.DEBUG)
            {
                if (cost < 0)
                    SanityManager.THROWASSERT("cost " + cost);

                if (estimated_row_count < 0)
                    SanityManager.THROWASSERT(
                        "estimated_row_count = " + estimated_row_count);
            }

            // return the cost
            cost_result.setEstimatedCost(cost);

            // RESOLVE - should we make sure this number is > 0?
            cost_result.setEstimatedRowCount(Math.round(estimated_row_count));
        }
        finally
        {
            if (control_row != null)
                control_row.release();
        }

        // System.out.println("BTreeCostController.getScanCost():" + 
          //   "\n\t cost = " + cost_result.getEstimatedCost() +
            // "\n\t rows = " + cost_result.getEstimatedRowCount());

        return;
    }

    /**
     * Return an "empty" row location object of the correct type.
     * <p>
     *
	 * @return The empty Rowlocation.
     *
	 * @exception  StandardException  Standard exception policy.
     **/
	public RowLocation newRowLocationTemplate()
		throws StandardException
	{
        throw StandardException.newException(
                SQLState.BTREE_UNIMPLEMENTED_FEATURE);
	}
}