com.bigdata.bop.cost

Class BTreeCostModel

java.lang.Object

com.bigdata.bop.cost.BTreeCostModel

All Implemented Interfaces:

Serializable

public class BTreeCostModel
extends Object
implements Serializable

A cost model for a range scan on a BTree backed by a Journal. The on disk representation of the BTree does not reflect the index order so a range scan on the BTree is basically turned into one random seek per node or leaf visited.

Version:

$Id$

Author:

Bryan Thompson

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
BTreeCostModel(DiskCostModel diskCostModel)

Method Summary

Methods

Modifier and Type	Method and Description
static int	estimateHeight(int entryCount, int branchingFactor) Compute the height of the B+Tree from its entry count and branching factor (this can also be used to find the minimum height at which there could exist a given range count).
static void	main(String[] args) Prints out some tables based on different disk cost models, branching factors, and range scans.
double	rangeScan(long rangeCount, int m, int h, int leafUtilization) Return the estimated cost of a range scan of the index.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BTreeCostModel

public BTreeCostModel(DiskCostModel diskCostModel)

Parameters:

diskCostModel - The cost model for the disk on which the Journal backing the BTree is located.

Method Detail

estimateHeight

public static int estimateHeight(int entryCount,
                 int branchingFactor)

Compute the height of the B+Tree from its entry count and branching factor (this can also be used to find the minimum height at which there could exist a given range count).

rangeScan

public double rangeScan(long rangeCount,
               int m,
               int h,
               int leafUtilization)

Return the estimated cost of a range scan of the index.

Parameters:

rangeCount - The range count for the scan.

m - The B+Tree branching factor.

h - The B+Tree height.

leafUtilization - The leaf utilization percentage [0:100].

Returns:

The estimated cost (milliseconds).

main

public static void main(String[] args)

Prints out some tables based on different disk cost models, branching factors, and range scans. To validate this, you can do a scatter plot of the rangeCount and cost columns and observe the log linear curve of the B+Tree.

Parameters:

args - ignored.

See Also:

query-cost-model.xls