ibis::index Class Reference
[FastBit IBIS key implementation objects.]

The base index class. More...

#include <index.h>

Inheritance diagram for ibis::index:

List of all members.

Public Types

typedef std::map< double,
uint32_t > histogram

enum INDEX_TYPE {
  BINNING = 0, RANGE, MESA, AMBIT,
  PALE, PACK, ZONE, RELIC,
  ROSTER, SLICE, FADE, SBIAD,
  SAPID, EGALE, MOINS, ENTRE,
  BAK, BAK2, KEYWORDS, MESH,
  BAND, DIREKTE, GENERIC, BYLT,
  FUZZ, ZONA, FUGE, EXTERN
}

The integer values of this enum type are used in the index files to differentiate the indexes. More...

typedef std::map< double,
ibis::bitvector * > VMap

Public Member Functions

virtual long append (const char *dt, const char *df, uint32_t nnew)

Extend the index.

virtual void binBoundaries (std::vector< double > &) const

The function binBoundaries and binWeights return bin boundaries and counts of each bin respectively.

virtual void binWeights (std::vector< uint32_t > &) const

virtual int contractRange (ibis::qContinuousRange &rng) const

virtual int64_t estimate (const ibis::rangeJoin &expr, const ibis::bitvector &mask, const ibis::qRange *const range1, const ibis::qRange *const range2) const

virtual void estimate (const ibis::rangeJoin &expr, const ibis::bitvector &mask, const ibis::qRange *const range1, const ibis::qRange *const range2, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const

Evaluating a join condition with one (likely composite) index.

virtual int64_t estimate (const ibis::index &idx2, const ibis::rangeJoin &expr, const ibis::bitvector &mask, const ibis::qRange *const range1, const ibis::qRange *const range2) const

virtual int64_t estimate (const ibis::index &idx2, const ibis::rangeJoin &expr, const ibis::bitvector &mask) const

Estimate an upper bound for the number of pairs produced from marked records.

virtual int64_t estimate (const ibis::index &idx2, const ibis::rangeJoin &expr) const

Estimate an upper bound for the number of pairs.

virtual void estimate (const ibis::index &idx2, const ibis::rangeJoin &expr, const ibis::bitvector &mask, const ibis::qRange *const range1, const ibis::qRange *const range2, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const

virtual void estimate (const ibis::index &idx2, const ibis::rangeJoin &expr, const ibis::bitvector &mask, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const

Estimate the pairs for the range join operator.

virtual void estimate (const ibis::index &idx2, const ibis::rangeJoin &expr, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const

Estimate the pairs for the range join operator.

virtual uint32_t estimate (const ibis::qDiscreteRange &expr) const

virtual void estimate (const ibis::qDiscreteRange &expr, ibis::bitvector &lower, ibis::bitvector &upper) const

Estimate the hits for discrete ranges, i.e., those translated from 'a IN (x, y, .

virtual uint32_t estimate (const ibis::qContinuousRange &expr) const

Returns an upper bound on the number of hits.

virtual void estimate (const ibis::qContinuousRange &expr, ibis::bitvector &lower, ibis::bitvector &upper) const

Computes an approximation of hits as a pair of lower and upper bounds.

virtual double estimateCost (const ibis::qDiscreteRange &expr) const

virtual double estimateCost (const ibis::qContinuousRange &expr) const

Estimate the code of evaluate a range condition.

virtual long evaluate (const ibis::qDiscreteRange &, ibis::bitvector &) const

To evaluate the exact hits.

virtual long evaluate (const ibis::qContinuousRange &expr, ibis::bitvector &hits) const =0

To evaluate the exact hits.

virtual int expandRange (ibis::qContinuousRange &rng) const

The functions expandRange and contractRange expands or contracts the boundaries of a range condition so that the new range will have exact answers using the function estimate.

virtual const ibis::bitvector * getBitvector (uint32_t i) const

Return a pointer to the ith bitvector used in the index (may be 0).

virtual long getCumulativeDistribution (std::vector< double > &bds, std::vector< uint32_t > &cts) const

Cumulative distribution of the data.

virtual long getDistribution (std::vector< double > &bbs, std::vector< uint32_t > &cts) const

Binned distribution of the data.

virtual double getMax () const

The maximum value recorded in the index.

virtual double getMin () const

The minimum value recorded in the index.

virtual uint32_t getNRows () const

virtual double getSum () const

Compute the approximate sum of all the values indexed.

virtual const char * name () const =0

Returns the name of the index, similar to the function type, but returns a string instead.

virtual uint32_t numBitvectors () const

Returns the number of bit vectors used by the index.

virtual void print (std::ostream &out) const =0

Prints human readable information.

virtual int read (ibis::fileManager::storage *st)=0

Reconstructs an index from an array of bytes.

virtual int read (const char *name)=0

Reconstructs an index from the named file.

virtual void speedTest (std::ostream &out) const

Time some logical operations and print out their speed.

virtual INDEX_TYPE type () const =0

Returns an index type identifier.

virtual float undecidable (const ibis::qDiscreteRange &expr, ibis::bitvector &iffy) const

virtual float undecidable (const ibis::qContinuousRange &expr, ibis::bitvector &iffy) const

Mark the position of the rows that can not be decided with this index.

virtual int write (const char *name) const =0

Save index to a file.

virtual ~index ()

The destructor.

Static Public Member Functions

static index * create (const column *c, const char *name=0, const char *spec=0)

Index factory.

static void divideCounts (array_t< uint32_t > &bounds, const array_t< uint32_t > &cnt)

Determine how to split the array cnt, so that each group has roughly the same total value.

static bool isIndex (const char *f, INDEX_TYPE t)

Read the header of the named file to determine if it contains an index of the specified type.

template<typename E1, typename E2>

static void mapValues (const array_t< E1 > &val1, const array_t< E2 > &val2, array_t< E1 > &bnd1, array_t< E2 > &bnd2, std::vector< uint32_t > &cnts)

Compute a two-dimensional histogram.

template<typename E>

static void mapValues (const array_t< E > &val, array_t< E > &bounds, std::vector< uint32_t > &cnts)

template<typename E>

static void mapValues (const array_t< E > &val, histogram &hist, uint32_t count=0)

template<typename E>

static void mapValues (const array_t< E > &val, VMap &bmap)

Protected Member Functions

virtual void activate (uint32_t i, uint32_t j) const

Regenerate bitvectors i (inclusive) through j (exclusive) from the underlying storage.

virtual void activate (uint32_t i) const

Regenerate the ith bitvector from the underlying storage.

virtual void activate () const

Regenerate all bitvectors from the underlying storage.

void addBits (uint32_t ib, uint32_t ie, ibis::bitvector &res, const ibis::bitvector &tot) const

Compute the sum of bit vectors [ib, ie).

void addBits (uint32_t ib, uint32_t ie, ibis::bitvector &res) const

Add the sum of bits[ib] through bits[ie-1] to res.

virtual void clear ()

Clear the existing content.

void computeMinMax (const char *f, double &min, double &max) const

void dataFileName (const char *f, std::string &name) const

Generate data file name from "f".

index (const ibis::column *c=0, ibis::fileManager::storage *s=0)

Protect the constructor so that ibis::index can not be instantiated directly.

void indexFileName (const char *f, std::string &name) const

Generate index file name from "f".

void mapValues (const char *f, histogram &hist, uint32_t count=0) const

Generate a histogram.

void mapValues (const char *f, VMap &bmap) const

Map the positions of each individual value.

void optionalUnpack (std::vector< ibis::bitvector * > &bits, const char *opt)

A function to decide whether to uncompress the bitvectors.

void sumBits (uint32_t ib, uint32_t ie, ibis::bitvector &res, uint32_t ib0, uint32_t ie0) const

Compute a new sum for bit vectors [ib, ie) by taking advantage of the old sum for bitvectors [ib0, ie0).

void sumBits (uint32_t ib, uint32_t ie, ibis::bitvector &res) const

Compute the bitwise OR of all bitvectors (in bits) from ib to ie.

Static Protected Member Functions

static void addBins (const std::vector< ibis::bitvector * > &bits, uint32_t ib, uint32_t ie, ibis::bitvector &res)

Add the bts[ib:ie-1] to res.

static void indexFileName (std::string &name, const ibis::column *col1, const ibis::column *col2, const char *f=0)

Generate the index file name for the composite index fromed on two columns.

static void setBases (array_t< uint32_t > &bases, uint32_t card, uint32_t nbase=2)

Fill the array bases with the values that cover the range [0, card).

static void sumBins (const std::vector< ibis::bitvector * > &bits, const ibis::bitvector &tot, uint32_t ib, uint32_t ie, ibis::bitvector &res)

Sum up bts[ib:ie-1] and add the result to res.

static void sumBins (const std::vector< ibis::bitvector * > &bits, uint32_t ib, uint32_t ie, ibis::bitvector &res)

Sum up bts[ib:ie-1] and place the result in res.

Protected Attributes

std::vector< ibis::bitvector * > bits

A list of bitvectors.

const ibis::column * col

Pointer to the column this index is for.

const char * fname

The name of the file containing the index.

uint32_t nrows

The number of rows represented by the index.

array_t< int32_t > offsets

Starting positions of the bitvectors.

ibis::fileManager::storage * str

The underlying storage.

Classes

class barrel

A specialization that adds function setValue. More...

Detailed Description

The base index class.

Class ibis::index contains the common definitions and virtual functions of the class hierarchy. It is assumed that an ibis::index is for only one column. The user is to create an new index through the function ibis::index::create and only use the functions defined in this class.

Member Enumeration Documentation

enum ibis::index::INDEX_TYPE

The integer values of this enum type are used in the index files to differentiate the indexes.

Reordering the list will make some index files invalid ****

Enumerator:

BINNING	ibis::bin.
RANGE	ibis::range.
MESA	ibis::interval.
AMBIT	ibis::ambit, range-range two level encoding on bins.
PALE	ibis::pale, equality-range encoding on bins.
PACK	ibis::pack, range-equality encoding on bins.
ZONE	ibis::zone, equality-equality encoding on bins.
RELIC	ibis::relic, the basic bitmap index.
ROSTER	ibis::roster, RID list.
SLICE	ibis::slice, bit-sliced index.
FADE	ibis::fade, multicomponent range encoding (unbinned).
SBIAD	ibis::sbiad, multicomponent interval encoding (unbinned).
SAPID	ibis::sapid, multicomponent equality encoding (unbinned).
EGALE	ibis::egale, multicomponent equality encoding on bins.
MOINS	ibis::moins, multicomponent range encoding on bins.
ENTRE	ibis::entre, multicomponent interval encoding on bins.
BAK	ibis::bak, reduced precision mapping, equality code.
BAK2	ibis::bak2, splits each BAK bin in two, one less than the mapped value, one greater and equal to the mapped value.
KEYWORDS	ibis::keywords, boolean term-document matrix.
MESH	not used.
BAND	not used.
DIREKTE	ibis::direkte, hash value to bitmaps.
GENERIC	not used.
BYLT	ibis::bylt, unbinned range-equality encoding.
FUZZ	ibis::fuzz, unbinned interval-equality encoding.
ZONA	ibis::zona, unbinned equality-equality encoding.
FUGE	ibis::fuge, binned interval-equality encoding.
EXTERN	externally defined index

Constructor & Destructor Documentation

ibis::index::index	(	const ibis::column *	c = `0`,
		ibis::fileManager::storage *	s = `0`
	)			`[inline, protected]`

Protect the constructor so that ibis::index can not be instantiated directly.

It can not be instantiated because some functions are pure virtual, but this also reduces the size of public interface.

Member Function Documentation

void ibis::index::activate	(	uint32_t	i,
		uint32_t	j
	)			const `[protected, virtual]`

Regenerate bitvectors i (inclusive) through j (exclusive) from the underlying storage.

References bits, col, fname, ibis::gVerbose, ibis::column::logWarning(), ibis::column::name(), nrows, offsets, array_t< T >::size(), and str.

void ibis::index::addBins	(	const std::vector< ibis::bitvector * > &	bts,
		uint32_t	ib,
		uint32_t	ie,
		ibis::bitvector &	res
	)			`[static, protected]`

Add the bts[ib:ie-1] to res.

Since the set of bit vectors are explicitly given, there is no need to perform activation. To minimize the burden of deciding which bit vectors to activate, this function always use the bts[ib] through bts[ie-1].

Note:: The caller need to activate the bit vectors!
This function still has to check whether a particular bts[i] is a null pointer before using the bit vector.

References ibis::bitvector::bytes(), ibis::bitvector::cnt(), ibis::bitvector::compress(), ibis::bitvector::copy(), ibis::horometer::CPUTime(), ibis::bitvector::decompress(), ibis::gVerbose, ibis::horometer::realTime(), ibis::bitvector::set(), ibis::bitvector::size(), ibis::horometer::start(), and ibis::horometer::stop().

Referenced by ibis::zona::evaluate().

void ibis::index::addBits	(	uint32_t	ib,
		uint32_t	ie,
		ibis::bitvector &	res,
		const ibis::bitvector &	tot
	)			const `[protected]`

Compute the sum of bit vectors [ib, ie).

This is basically a copy of the function sumBits (without the 4th arguments).

If computing a complement is faster, assume all bit vectors add up to tot.

There are two changes: (1) if res has the same number of bits as tot, the new sum is added to the existing bitvector, and (2) when it computes the sum through complements, it performs a subtraction from tot.

References activate(), ibis::bitvector::adjustSize(), bits, ibis::bitvector::bitsPerLiteral(), ibis::bitvector::bytes(), array_t< T >::clear(), ibis::bitvector::cnt(), col, ibis::bitvector::copy(), ibis::horometer::CPUTime(), ibis::bitvector::decompress(), array_t< T >::empty(), fname, ibis::gVerbose, ibis::column::name(), nrows, offsets, ibis::horometer::realTime(), array_t< T >::resize(), ibis::bitvector::set(), array_t< T >::size(), ibis::bitvector::size(), ibis::horometer::start(), ibis::horometer::stop(), str, and ibis::bitvector::swap().

void ibis::index::addBits	(	uint32_t	ib,
		uint32_t	ie,
		ibis::bitvector &	res
	)			const `[protected]`

Add the sum of bits[ib] through bits[ie-1] to res.

The most important difference between this function and sumBits is that this function always use bits[ib] through bits[ie-1].

Always explicitly use bits[ib] through bits[ie-1].

This is similar to the function addBins.

References activate(), ibis::bitvector::adjustSize(), bits, ibis::bitvector::bitsPerLiteral(), ibis::bitvector::bytes(), ibis::bitvector::cnt(), col, ibis::bitvector::copy(), ibis::horometer::CPUTime(), ibis::bitvector::decompress(), ibis::gVerbose, ibis::column::name(), nrows, ibis::horometer::realTime(), ibis::bitvector::set(), ibis::bitvector::size(), ibis::horometer::start(), and ibis::horometer::stop().

Referenced by ibis::fuge::estimate(), ibis::zona::evaluate(), ibis::fuzz::evaluate(), and ibis::bylt::evaluate().

virtual void ibis::index::binBoundaries ( std::vector< double > & ) const [inline, virtual]

The function binBoundaries and binWeights return bin boundaries and counts of each bin respectively.

Reimplemented in ibis::bin, ibis::range, ibis::mesa, ibis::ambit, ibis::pale, ibis::pack, ibis::zone, ibis::egale, ibis::bak, ibis::bak2, ibis::direkte, ibis::keywords, and ibis::relic.

Referenced by ibis::part::coarsenBins(), ibis::part::get2DDistributionI(), and ibis::column::preferredBounds().

void ibis::index::clear ( ) [protected, virtual]

Clear the existing content.

Free the objectes pointed to by the pointers.

Reimplemented in ibis::bin, ibis::ambit, ibis::pale, ibis::pack, ibis::zone, ibis::fuge, ibis::egale, ibis::keywords, ibis::relic, ibis::slice, ibis::fade, ibis::fuzz, ibis::bylt, and ibis::zona.

References bits, array_t< T >::clear(), fname, nrows, offsets, and str.

Referenced by ibis::bin::binning(), ibis::bin::binningT(), ibis::relic::clear(), ibis::keywords::clear(), ibis::bin::clear(), ibis::relic::read(), ibis::keywords::read(), ibis::direkte::read(), and ~index().

ibis::index * ibis::index::create	(	const column *	c,
		const char *	name = `0`,
		const char *	spec = `0`
	)			`[static]`

Index factory.

It creates a specific concrete index object. If this function failed to read a specified index file, it will attempt to create a new index based on the current data file and index specification. The new index will be written under the old name.

This function returns nil if it fails to create an index.

Parameters:

	c	a pointer to a ibis::column object. This argument must be present.
	name	a name, it can be the name of the index file, the data file, or the directory containing the data file. If the name ends with '.idx' is treated as an index file and the content of the file is read. If the name does not end with '.idx', it is assumed to be the data file name unless it is determined to be directory name. If it is a directory name, the data file is assumed to be in the directory with the file name same as the column name. Once a data file is found, the content of the data file is read to construct a new index according to the return value of function indexSpec. The argument name can be nil, in which case, the data file name is constructed by concatenate the return of partition()->currentDataDir() and the column name.

Note:: Set name to null to build a brand new index and discard the existing index.

Parameters:

spec

the index specification. This string contains the parameters for how to create an index. The most general form is

        <binning .../> <encoding .../> <compression .../>.

Here is one example (it is the default for some integer columns)

        <binning none /> <encoding equality />

FastBit always compresses every bitmap it ever generates. The compression option is to instruct it to uncompress some bitmaps or not compress indices at all. The compress option is usually not used.

If the argument spec is not specified, this function checks the specification in the following order.

use the index specification for the column being indexed;
use the index specification for the table containing the column being indexed;
use the most specific index specification relates to the column be indexed in the global resources (gParameters).

It stops looking as soon as it finds the first non-empty string. To override any general index specification, one must provide a complete index specification string.

References AMBIT, BAK, BAK2, ibis::fileManager::storage::begin(), BINNING, ibis::util::logger::buffer(), BYLT, ibis::BYTE, ibis::CATEGORY, col, ibis::column::computeMinMax(), ibis::horometer::CPUTime(), ibis::part::currentDataDir(), DIREKTE, ibis::DOUBLE, EGALE, ENTRE, FADE, ibis::FLOAT, FUGE, FUZZ, getNRows(), ibis::gParameters(), ibis::gVerbose, ibis::part::indexSpec(), ibis::column::indexSpec(), ibis::fileManager::instance(), ibis::INT, ibis::resource::isTrue(), KEYWORDS, ibis::column::logMessage(), ibis::column::logWarning(), ibis::LONG, ibis::column::lowerBound(), MESA, MOINS, name(), ibis::column::name(), ibis::part::name(), ibis::part::nRows(), PACK, PALE, ibis::column::partition(), print(), RANGE, read(), ibis::horometer::realTime(), RELIC, SAPID, SBIAD, ibis::SHORT, SLICE, ibis::horometer::start(), ibis::horometer::stop(), str, ibis::TEXT, ibis::fileManager::tryGetFile(), ibis::column::type(), ibis::UBYTE, ibis::UINT, ibis::ULONG, ibis::column::upperBound(), ibis::USHORT, ibis::bad_alloc::what(), write(), ZONA, and ZONE.

Referenced by ibis::column::append(), ibis::mensa::buildIndex(), ibis::part::loadIndex(), and ibis::column::loadIndex().

void ibis::index::divideCounts	(	array_t< uint32_t > &	bdry,
		const array_t< uint32_t > &	cnt
	)			`[static]`

Determine how to split the array cnt, so that each group has roughly the same total value.

Note:: The array bdry stores the dividers. The first group is [0, bdry[0]), the second group is [bdry[0], bdry[1]), and so on. Ths function uses the size of array bdry to determine the number of groups to use.

References array_t< T >::back(), array_t< T >::begin(), ibis::util::logger::buffer(), array_t< T >::clear(), array_t< T >::empty(), array_t< T >::end(), ibis::gVerbose, array_t< T >::push_back(), array_t< T >::resize(), and array_t< T >::size().

Referenced by ibis::part::adaptive2DBins(), ibis::part::adaptiveFloats(), ibis::part::adaptiveInts(), ibis::part::coarsenBins(), ibis::part::equalWeightBins(), ibis::part::get2DDistributionI(), ibis::part::getCumulativeDistribution(), ibis::part::getDistribution(), and ibis::bin::scanAndPartition().

int64_t ibis::index::estimate	(	const ibis::index &	idx2,
		const ibis::rangeJoin &	expr,
		const ibis::bitvector &	mask
	)			const `[virtual]`

Estimate an upper bound for the number of pairs produced from marked records.

References ibis::bitvector::cnt(), col, ibis::gVerbose, ibis::part::nRows(), and ibis::column::partition().

void ibis::index::estimate	(	const ibis::index &	idx2,
		const ibis::rangeJoin &	expr,
		const ibis::bitvector &	mask,
		ibis::bitvector64 &	lower,
		ibis::bitvector64 &	upper
	)			const `[virtual]`

Estimate the pairs for the range join operator.

Only records that are masked are evaluated.

References ibis::bitvector64::clear(), col, ibis::gVerbose, ibis::part::nRows(), ibis::outerProduct(), ibis::column::partition(), and ibis::bitvector64::set().

void ibis::index::estimate	(	const ibis::qDiscreteRange &	expr,
		ibis::bitvector &	lower,
		ibis::bitvector &	upper
	)			const `[virtual]`

Estimate the hits for discrete ranges, i.e., those translated from 'a IN (x, y, .

A trivial implementation to indicate the index can not determine any row.

.)'.

Reimplemented in ibis::direkte, and ibis::relic.

References col, ibis::qDiscreteRange::colName(), ibis::gVerbose, ibis::part::nRows(), ibis::column::partition(), and ibis::bitvector::set().

virtual void ibis::index::estimate	(	const ibis::qContinuousRange &	expr,
		ibis::bitvector &	lower,
		ibis::bitvector &	upper
	)			const `[inline, virtual]`

Computes an approximation of hits as a pair of lower and upper bounds.

Parameters:

	expr	the query expression to be evaluated.
	lower	a bitvector marking a subset of the hits. All rows marked with one (1) are definitely hits.
	upper	a bitvector marking a superset of the hits. All hits are marked with one, but some of the rows marked one may not be hits. If the variable upper is empty, the variable lower is assumed to contain the exact answer.

Reimplemented in ibis::bin, ibis::range, ibis::mesa, ibis::ambit, ibis::pale, ibis::pack, ibis::zone, ibis::fuge, ibis::egale, ibis::moins, ibis::entre, ibis::direkte, ibis::keywords, ibis::relic, and ibis::slice.

References nrows, and ibis::bitvector::set().

Referenced by ibis::column::estimateRange(), ibis::column::evaluateRange(), and ibis::category::search().

virtual long ibis::index::evaluate	(	const ibis::qDiscreteRange &	,
		ibis::bitvector &
	)			const `[inline, virtual]`

To evaluate the exact hits.

On success, return the number of hits, otherwise a negative value is returned.

Reimplemented in ibis::direkte, ibis::relic, ibis::slice, ibis::fade, ibis::sbiad, and ibis::sapid.

virtual long ibis::index::evaluate	(	const ibis::qContinuousRange &	expr,
		ibis::bitvector &	hits
	)			const `[pure virtual]`

To evaluate the exact hits.

On success, return the number of hits, otherwise a negative value is returned.

Implemented in ibis::bin, ibis::range, ibis::mesa, ibis::ambit, ibis::pale, ibis::pack, ibis::zone, ibis::fuge, ibis::egale, ibis::moins, ibis::entre, ibis::direkte, ibis::keywords, ibis::relic, ibis::slice, ibis::fade, ibis::sbiad, ibis::sapid, ibis::fuzz, ibis::bylt, and ibis::zona.

Referenced by ibis::part::coarsenBins(), and ibis::part::get2DDistributionI().

virtual int ibis::index::expandRange ( ibis::qContinuousRange & rng ) const [inline, virtual]

The functions expandRange and contractRange expands or contracts the boundaries of a range condition so that the new range will have exact answers using the function estimate.

The default implementation provided does nothing since this is only meaningful for indices based on bins.

Reimplemented in ibis::bin, ibis::range, ibis::bak, and ibis::bak2.

Referenced by ibis::column::expandRange().

long ibis::index::getCumulativeDistribution	(	std::vector< double > &	bds,
		std::vector< uint32_t > &	cts
	)			const `[virtual]`

Cumulative distribution of the data.

A brute-force approach to get an accurate cumulative distribution.

Reimplemented in ibis::bin, ibis::direkte, and ibis::relic.

long ibis::index::getDistribution	(	std::vector< double > &	bbs,
		std::vector< uint32_t > &	cts
	)			const `[virtual]`

Binned distribution of the data.

A brute-force approach to get an accurate distribution.

Reimplemented in ibis::bin, ibis::direkte, and ibis::relic.

virtual double ibis::index::getSum ( ) const [inline, virtual]

Compute the approximate sum of all the values indexed.

If it decides that computing the sum directly from the vertical partition is more efficient, it will return NaN immediately.

Reimplemented in ibis::bin, ibis::range, ibis::mesa, ibis::ambit, ibis::pack, ibis::egale, ibis::moins, ibis::entre, ibis::direkte, ibis::keywords, ibis::relic, ibis::slice, and ibis::fade.

void ibis::index::indexFileName	(	std::string &	iname,
		const ibis::column *	col1,
		const ibis::column *	col2,
		const char *	dir = `0`
	)			`[static, protected]`

Generate the index file name for the composite index fromed on two columns.

May use argument "dir" if it is not null.

References ibis::part::currentDataDir(), ibis::column::name(), and ibis::column::partition().

bool ibis::index::isIndex	(	const char *	f,
		INDEX_TYPE	t
	)			`[static]`

Read the header of the named file to determine if it contains an index of the specified type.

Returns true if the correct header is found, else return false.

Referenced by ibis::bak2::read(), and ibis::bak::read().

void ibis::index::mapValues	(	const char *	f,
		histogram &	hist,
		uint32_t	count = `0`
	)			const `[protected]`

Generate a histogram.

Compute a histogram of a column.

Given a property file containing the values of a


Public Types
typedef std::map< double, uint32_t >	histogram
enum	INDEX_TYPE { BINNING = 0, RANGE, MESA, AMBIT, PALE, PACK, ZONE, RELIC, ROSTER, SLICE, FADE, SBIAD, SAPID, EGALE, MOINS, ENTRE, BAK, BAK2, KEYWORDS, MESH, BAND, DIREKTE, GENERIC, BYLT, FUZZ, ZONA, FUGE, EXTERN }
	The integer values of this enum type are used in the index files to differentiate the indexes. More...
typedef std::map< double, ibis::bitvector * >	VMap
Public Member Functions
virtual long	append (const char dt, const char df, uint32_t nnew)
	Extend the index.
virtual void	binBoundaries (std::vector< double > &) const
	The function binBoundaries and binWeights return bin boundaries and counts of each bin respectively.
virtual void	binWeights (std::vector< uint32_t > &) const
virtual int	contractRange (ibis::qContinuousRange &rng) const
virtual int64_t	estimate (const ibis::rangeJoin &expr, const ibis::bitvector &mask, const ibis::qRange const range1, const ibis::qRange const range2) const
virtual void	estimate (const ibis::rangeJoin &expr, const ibis::bitvector &mask, const ibis::qRange const range1, const ibis::qRange const range2, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const
	Evaluating a join condition with one (likely composite) index.
virtual int64_t	estimate (const ibis::index &idx2, const ibis::rangeJoin &expr, const ibis::bitvector &mask, const ibis::qRange const range1, const ibis::qRange const range2) const
virtual int64_t	estimate (const ibis::index &idx2, const ibis::rangeJoin &expr, const ibis::bitvector &mask) const
	Estimate an upper bound for the number of pairs produced from marked records.
virtual int64_t	estimate (const ibis::index &idx2, const ibis::rangeJoin &expr) const
	Estimate an upper bound for the number of pairs.
virtual void	estimate (const ibis::index &idx2, const ibis::rangeJoin &expr, const ibis::bitvector &mask, const ibis::qRange const range1, const ibis::qRange const range2, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const
virtual void	estimate (const ibis::index &idx2, const ibis::rangeJoin &expr, const ibis::bitvector &mask, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const
	Estimate the pairs for the range join operator.
virtual void	estimate (const ibis::index &idx2, const ibis::rangeJoin &expr, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const
	Estimate the pairs for the range join operator.
virtual uint32_t	estimate (const ibis::qDiscreteRange &expr) const
virtual void	estimate (const ibis::qDiscreteRange &expr, ibis::bitvector &lower, ibis::bitvector &upper) const
	Estimate the hits for discrete ranges, i.e., those translated from 'a IN (x, y, .
virtual uint32_t	estimate (const ibis::qContinuousRange &expr) const
	Returns an upper bound on the number of hits.
virtual void	estimate (const ibis::qContinuousRange &expr, ibis::bitvector &lower, ibis::bitvector &upper) const
	Computes an approximation of hits as a pair of lower and upper bounds.
virtual double	estimateCost (const ibis::qDiscreteRange &expr) const
virtual double	estimateCost (const ibis::qContinuousRange &expr) const
	Estimate the code of evaluate a range condition.
virtual long	evaluate (const ibis::qDiscreteRange &, ibis::bitvector &) const
	To evaluate the exact hits.
virtual long	evaluate (const ibis::qContinuousRange &expr, ibis::bitvector &hits) const =0
	To evaluate the exact hits.
virtual int	expandRange (ibis::qContinuousRange &rng) const
	The functions expandRange and contractRange expands or contracts the boundaries of a range condition so that the new range will have exact answers using the function estimate.
virtual const ibis::bitvector *	getBitvector (uint32_t i) const
	Return a pointer to the ith bitvector used in the index (may be 0).
virtual long	getCumulativeDistribution (std::vector< double > &bds, std::vector< uint32_t > &cts) const
	Cumulative distribution of the data.
virtual long	getDistribution (std::vector< double > &bbs, std::vector< uint32_t > &cts) const
	Binned distribution of the data.
virtual double	getMax () const
	The maximum value recorded in the index.
virtual double	getMin () const
	The minimum value recorded in the index.
virtual uint32_t	getNRows () const
virtual double	getSum () const
	Compute the approximate sum of all the values indexed.
virtual const char *	name () const =0
	Returns the name of the index, similar to the function `type`, but returns a string instead.
virtual uint32_t	numBitvectors () const
	Returns the number of bit vectors used by the index.
virtual void	print (std::ostream &out) const =0
	Prints human readable information.
virtual int	read (ibis::fileManager::storage *st)=0
	Reconstructs an index from an array of bytes.
virtual int	read (const char *name)=0
	Reconstructs an index from the named file.
virtual void	speedTest (std::ostream &out) const
	Time some logical operations and print out their speed.
virtual INDEX_TYPE	type () const =0
	Returns an index type identifier.
virtual float	undecidable (const ibis::qDiscreteRange &expr, ibis::bitvector &iffy) const
virtual float	undecidable (const ibis::qContinuousRange &expr, ibis::bitvector &iffy) const
	Mark the position of the rows that can not be decided with this index.
virtual int	write (const char *name) const =0
	Save index to a file.
virtual	~index ()
	The destructor.
Static Public Member Functions
static index *	create (const column c, const char name=0, const char *spec=0)
	Index factory.
static void	divideCounts (array_t< uint32_t > &bounds, const array_t< uint32_t > &cnt)
	Determine how to split the array `cnt`, so that each group has roughly the same total value.
static bool	isIndex (const char *f, INDEX_TYPE t)
	Read the header of the named file to determine if it contains an index of the specified type.
template<typename E1, typename E2>
static void	mapValues (const array_t< E1 > &val1, const array_t< E2 > &val2, array_t< E1 > &bnd1, array_t< E2 > &bnd2, std::vector< uint32_t > &cnts)
	Compute a two-dimensional histogram.
template<typename E>
static void	mapValues (const array_t< E > &val, array_t< E > &bounds, std::vector< uint32_t > &cnts)
template<typename E>
static void	mapValues (const array_t< E > &val, histogram &hist, uint32_t count=0)
template<typename E>
static void	mapValues (const array_t< E > &val, VMap &bmap)
Protected Member Functions
virtual void	activate (uint32_t i, uint32_t j) const
	Regenerate bitvectors i (inclusive) through j (exclusive) from the underlying storage.
virtual void	activate (uint32_t i) const
	Regenerate the ith bitvector from the underlying storage.
virtual void	activate () const
	Regenerate all bitvectors from the underlying storage.
void	addBits (uint32_t ib, uint32_t ie, ibis::bitvector &res, const ibis::bitvector &tot) const
	Compute the sum of bit vectors [`ib`, `ie`).
void	addBits (uint32_t ib, uint32_t ie, ibis::bitvector &res) const
	Add the sum of `bits`[ib] through `bits`[ie-1] to `res`.
virtual void	clear ()
	Clear the existing content.
void	computeMinMax (const char *f, double &min, double &max) const
void	dataFileName (const char *f, std::string &name) const
	Generate data file name from "f".
	index (const ibis::column c=0, ibis::fileManager::storage s=0)
	Protect the constructor so that ibis::index can not be instantiated directly.
void	indexFileName (const char *f, std::string &name) const
	Generate index file name from "f".
void	mapValues (const char *f, histogram &hist, uint32_t count=0) const
	Generate a histogram.
void	mapValues (const char *f, VMap &bmap) const
	Map the positions of each individual value.
void	optionalUnpack (std::vector< ibis::bitvector * > &bits, const char *opt)
	A function to decide whether to uncompress the bitvectors.
void	sumBits (uint32_t ib, uint32_t ie, ibis::bitvector &res, uint32_t ib0, uint32_t ie0) const
	Compute a new sum for bit vectors [ib, ie) by taking advantage of the old sum for bitvectors [ib0, ie0).
void	sumBits (uint32_t ib, uint32_t ie, ibis::bitvector &res) const
	Compute the bitwise OR of all bitvectors (in bits) from ib to ie.
Static Protected Member Functions
static void	addBins (const std::vector< ibis::bitvector * > &bits, uint32_t ib, uint32_t ie, ibis::bitvector &res)
	Add the `bts`[ib:ie-1] to `res`.
static void	indexFileName (std::string &name, const ibis::column col1, const ibis::column col2, const char *f=0)
	Generate the index file name for the composite index fromed on two columns.
static void	setBases (array_t< uint32_t > &bases, uint32_t card, uint32_t nbase=2)
	Fill the array bases with the values that cover the range [0, card).
static void	sumBins (const std::vector< ibis::bitvector * > &bits, const ibis::bitvector &tot, uint32_t ib, uint32_t ie, ibis::bitvector &res)
	Sum up `bts`[ib:ie-1] and add the result to `res`.
static void	sumBins (const std::vector< ibis::bitvector * > &bits, uint32_t ib, uint32_t ie, ibis::bitvector &res)
	Sum up `bts`[ib:ie-1] and place the result in `res`.
Protected Attributes
std::vector< ibis::bitvector * >	bits
	A list of bitvectors.
const ibis::column *	col
	Pointer to the column this index is for.
const char *	fname
	The name of the file containing the index.
uint32_t	nrows
	The number of rows represented by the index.
array_t< int32_t >	offsets
	Starting positions of the bitvectors.
ibis::fileManager::storage *	str
	The underlying storage.
Classes
class	barrel
	A specialization that adds function `setValue`. More...

ibis::index Class Reference [FastBit IBIS key implementation objects.]

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Classes

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

ibis::index Class Reference
[FastBit IBIS key implementation objects.]