simpledb

Class IntHistogram

java.lang.Object

simpledb.IntHistogram

public class IntHistogram
extends java.lang.Object

A class to represent a fixed-width histogram over a single integer-based field.

Field Summary

Fields

Modifier and Type	Field and Description
private int[]	hist
private boolean	isSumComputed
private int	max
private int	min
private int	nBuckets
private int	nBucketSize
private int	nTups
private int[]	sum

Constructor Summary

Constructors

Constructor and Description
IntHistogram(int buckets, int min, int max) Create a new IntHistogram.

Method Summary

Modifier and Type	Method and Description
void	addValue(int v) Add a value to the set of values that you are keeping a histogram of.
double	avgSelectivity()
double	estimateSelectivity(Predicate.Op op, int v) Estimate the selectivity of a particular predicate and operand on this table.
private int	getSum(int i, int j) Returns Sum( hist[i..j] )
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

nBuckets

private int nBuckets

nBucketSize

private int nBucketSize

min

private int min

max

private int max

hist

private int[] hist

sum

private int[] sum

isSumComputed

private boolean isSumComputed

nTups

private int nTups

Constructor Detail

IntHistogram

public IntHistogram(int buckets,
                    int min,
                    int max)

Create a new IntHistogram. This IntHistogram should maintain a histogram of integer values that it receives. It should split the histogram into "buckets" buckets. The values that are being histogrammed will be provided one-at-a-time through the "addValue()" function. Your implementation should use space and have execution time that are both constant with respect to the number of values being histogrammed. For example, you shouldn't simply store every value that you see in a sorted list.

Parameters:

buckets - The number of buckets to split the input value into.

min - The minimum integer value that will ever be passed to this class for histogramming

max - The maximum integer value that will ever be passed to this class for histogramming

Method Detail

addValue

public void addValue(int v)

Add a value to the set of values that you are keeping a histogram of.

Parameters:

v - Value to add to the histogram

getSum

private int getSum(int i,
                   int j)

Returns Sum( hist[i..j] )

Parameters:

i -

j -

Returns:

The sum hist[i..j]

estimateSelectivity

public double estimateSelectivity(Predicate.Op op,
                                  int v)

Estimate the selectivity of a particular predicate and operand on this table. For example, if "op" is "GREATER_THAN" and "v" is 5, return your estimate of the fraction of elements that are greater than 5.

Parameters:

op - Operator

v - Value

Returns:

Predicted selectivity of this particular operator and value

avgSelectivity

public double avgSelectivity()

Returns:

the average selectivity of this histogram. This is not an indispensable method to implement the basic join optimization. It may be needed if you want to implement a more efficient optimization

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

Returns:

A string describing this histogram, for debugging purposes