ibis::relic Class Reference

The basic bitmap index. More...

#include <irelic.h>

Inheritance diagram for ibis::relic:

List of all members.

Public Member Functions
long	append (const array_t< uint32_t > &ind)
	Append a list of integers.
long	append (const ibis::relic &tail)
virtual long	append (const char *dt, const char *df, uint32_t nnew)
	Extend the index.
virtual void	binBoundaries (std::vector< double > &b) const
	The function binBoundaries and binWeights return bin boundaries and counts of each bin respectively.
virtual void	binWeights (std::vector< uint32_t > &b) const
virtual int64_t	estimate (const ibis::relic &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::relic &idx2, const ibis::rangeJoin &expr, const ibis::bitvector &mask) const
	Estimate an upper bound for the number of pairs produced from marked records.
virtual void	estimate (const ibis::relic &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::relic &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 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 &expr, ibis::bitvector &hits) const
	To evaluate the exact hits.
virtual long	evaluate (const ibis::qContinuousRange &expr, ibis::bitvector &hits) const
	To evaluate the exact hits.
virtual long	getCumulativeDistribution (std::vector< double > &bds, std::vector< uint32_t > &cts) const
	Cumulative distribution of the data.
virtual long	getDistribution (std::vector< double > &bds, 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 double	getSum () const
	Compute the approximate sum of all the values indexed.
array_t< uint32_t > *	keys (const ibis::bitvector &mask) const
virtual const char *	name () const
	Returns the name of the index, similar to the function type, but returns a string instead.
virtual void	print (std::ostream &out) const
	Prints human readable information.
virtual int	read (ibis::fileManager::storage *st)
	Reconstructs an index from an array of bytes.
virtual int	read (const char *idxfile)
	Reconstructs an index from the named file.
	relic (const ibis::column *c, ibis::fileManager::storage *st, uint32_t offset=8)
	Reconstruct from content of fileManager::storage.
	relic (const ibis::column *c, uint32_t card, array_t< uint32_t > &ints)
	Construct an index from an integer array.
	relic (const ibis::column *c, uint32_t popu, uint32_t ntpl=0)
	Construct a dummy index.
	relic (const ibis::column *c, const char *f=0)
virtual void	speedTest (std::ostream &out) const
	Time some logical operations and print out their speed.
virtual INDEX_TYPE	type () const
	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
	This class and its derived classes should produce exact answers, therefore no undecidable rows.
virtual int	write (const char *dt) const
	Save index to a file.
Protected Member Functions
virtual void	clear ()
	Clear the existing content.
virtual double	computeSum () const
template<typename E>
void	construct (const array_t< E > &arr)
	Construct an index from in-memory values.
void	locate (const ibis::qContinuousRange &expr, uint32_t &hit0, uint32_t &hit1) const
	Locate the bitmaps covered by the range expression.
uint32_t	locate (const double &val) const
	Find the smallest i such that vals[i] > val.
int	write (int fdes) const
Protected Attributes
array_t< double >	vals

---

Detailed Description

The basic bitmap index.

It generates one bitmap for each distinct value.

---

Constructor & Destructor Documentation

ibis::relic::relic	(	const ibis::column *	c,
		uint32_t	popu,
		uint32_t	ntpl = 0
	)

Construct a dummy index.

All entries have the same value popu. This is used to generate index for meta tags from STAR data.

References ibis::index::bits, ibis::util::logger::buffer(), clear(), ibis::index::col, ibis::gVerbose, ibis::column::name(), ibis::index::nrows, ibis::part::nRows(), ibis::column::partition(), print(), and array_t< T >::resize().

ibis::relic::relic	(	const ibis::column *	c,
		ibis::fileManager::storage *	st,
		uint32_t	start = 8
	)

Reconstruct from content of fileManager::storage.

The content of the file (following the 8-byte header) is nrows(uint32_t) -- number of bits in each bit sequences nobs (uint32_t) -- number of bit sequences card (uint32_t) -- the number of distinct values, i.e., cardinality (padding to ensure the next data element is on 8-byte boundary) values (double[card]) -- the values as doubles offset (uint32_t[nobs+1]) -- the starting positions of the bit sequences (as bit vectors) bitvectors -- the bitvectors one after another

References ibis::fileManager::storage::begin(), ibis::index::bits, ibis::util::logger::buffer(), clear(), ibis::index::col, array_t< T >::copy(), ibis::fileManager::storage::filename(), ibis::gVerbose, ibis::fileManager::storage::isFileMap(), ibis::column::logWarning(), ibis::column::name(), ibis::index::nrows, ibis::index::offsets, print(), ibis::index::RELIC, ibis::bitvector::setSize(), and ibis::index::str.

---

Member Function Documentation

long ibis::relic::append

(

const array_t< uint32_t > &

ind

)

Append a list of integers.

The integers are treated as bin numbers. This function is primarily used by ibis::category::append().

References ibis::index::activate(), ibis::index::bits, ibis::index::col, array_t< T >::empty(), ibis::column::logMessage(), ibis::index::nrows, array_t< T >::push_back(), and array_t< T >::size().

void ibis::relic::binBoundaries

(

std::vector< double > &

)

const [virtual]

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

Reimplemented from ibis::index.

References array_t< T >::size().

Referenced by getCumulativeDistribution(), and getDistribution().

void ibis::relic::clear

(

)

[protected, virtual]

Clear the existing content.

Free the objectes pointed to by the pointers.

Reimplemented from ibis::index.

Reimplemented in ibis::slice, ibis::fade, ibis::fuzz, ibis::bylt, and ibis::zona.

References ibis::index::clear(), and array_t< T >::clear().

Referenced by ibis::zona::clear(), ibis::fuzz::clear(), ibis::bylt::clear(), ibis::slice::clear(), ibis::fade::clear(), read(), and relic().

template<typename E>

void ibis::relic::construct

(

const array_t< E > &

arr

)

[inline, protected]

Construct an index from in-memory values.

The type E is intended to be element types supported in column.h.

References ibis::index::bits, ibis::util::logger::buffer(), ibis::index::col, ibis::gVerbose, ibis::column::indexSpec(), ibis::fileManager::instance(), ibis::index::nrows, ibis::index::optionalUnpack(), print(), array_t< T >::resize(), ibis::fileManager::signalMemoryAvailable(), and array_t< T >::size().

int64_t ibis::relic::estimate	(	const ibis::relic &	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(), ibis::index::col, ibis::horometer::CPUTime(), ibis::compRange::term::eval(), ibis::part::evaluateJoin(), ibis::rangeJoin::getRange(), ibis::gVerbose, ibis::column::partition(), ibis::horometer::realTime(), ibis::horometer::start(), ibis::horometer::stop(), and ibis::compRange::term::termType().

void ibis::relic::estimate	(	const ibis::relic &	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]

Note:

It is assumed that range1 is for column 1 in the join expression and range2 is for column 2 in the join expression. No name matching is performed.

References ibis::bitvector64::bytes(), ibis::bitvector64::clear(), ibis::bitvector::cnt(), ibis::index::col, ibis::horometer::CPUTime(), estimate(), ibis::compRange::term::eval(), ibis::part::evaluateJoin(), ibis::rangeJoin::getRange(), ibis::gVerbose, ibis::column::partition(), ibis::horometer::realTime(), ibis::horometer::start(), ibis::horometer::stop(), and ibis::compRange::term::termType().

void ibis::relic::estimate	(	const ibis::relic &	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::bytes(), ibis::bitvector64::clear(), ibis::bitvector::cnt(), ibis::index::col, ibis::horometer::CPUTime(), ibis::compRange::term::eval(), ibis::part::evaluateJoin(), ibis::rangeJoin::getRange(), ibis::gVerbose, ibis::column::partition(), ibis::horometer::realTime(), ibis::horometer::start(), ibis::horometer::stop(), and ibis::compRange::term::termType().

virtual void ibis::relic::estimate	(	const ibis::qDiscreteRange &	expr,
		ibis::bitvector &	lower,
		ibis::bitvector &	upper
	)			const [inline, 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 from ibis::index.

References ibis::bitvector::clear(), and evaluate().

virtual void ibis::relic::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 from ibis::index.

Reimplemented in ibis::slice.

References ibis::bitvector::clear(), and evaluate().

Referenced by estimate().

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

To evaluate the exact hits.

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

Reimplemented from ibis::index.

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

References ibis::index::activate(), ibis::index::bits, ibis::bitvector::cnt(), ibis::qDiscreteRange::getValues(), locate(), ibis::index::nrows, and ibis::bitvector::set().

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

To evaluate the exact hits.

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

Implements ibis::index.

Reimplemented in ibis::slice, ibis::fade, ibis::sbiad, ibis::sapid, ibis::fuzz, ibis::bylt, and ibis::zona.

References ibis::index::bits, ibis::bitvector::cnt(), locate(), ibis::index::nrows, ibis::bitvector::set(), and ibis::index::sumBits().

Referenced by estimate().

long ibis::relic::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 from ibis::index.

References binBoundaries(), ibis::util::logger::buffer(), ibis::index::col, ibis::column::logMessage(), and ibis::bitvector::size().

long ibis::relic::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 from ibis::index.

References binBoundaries(), ibis::util::logger::buffer(), ibis::index::col, and ibis::column::logMessage().

double ibis::relic::getSum

(

)

const [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 from ibis::index.

Reimplemented in ibis::slice, and ibis::fade.

References ibis::index::bits, ibis::fileManager::storage::bytes(), ibis::index::col, ibis::column::elementSize(), ibis::part::nRows(), ibis::index::offsets, ibis::column::partition(), array_t< T >::size(), and ibis::index::str.

void ibis::relic::locate	(	const ibis::qContinuousRange &	expr,
		uint32_t &	hit0,
		uint32_t &	hit1
	)			const [protected]

Locate the bitmaps covered by the range expression.

Bitmaps hit0 (inclusive) through hit1 (execlusive) correspond to values satisfy the range expression expr.

References ibis::index::col, ibis::gVerbose, ibis::qContinuousRange::leftBound(), ibis::qContinuousRange::leftOperator(), locate(), ibis::column::logMessage(), ibis::column::logWarning(), ibis::qContinuousRange::rightBound(), ibis::qContinuousRange::rightOperator(), and array_t< T >::size().

virtual const char* ibis::relic::name

(

)

const [inline, virtual]

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

Implements ibis::index.

Reimplemented in ibis::slice, ibis::fade, ibis::sbiad, ibis::sapid, ibis::fuzz, ibis::bylt, and ibis::zona.

Referenced by read().

void ibis::relic::print

(

std::ostream &

out

)

const [virtual]

Prints human readable information.

Outputs information about the index as text to the specified output stream.

Implements ibis::index.

Reimplemented in ibis::slice, ibis::fade, ibis::sbiad, ibis::sapid, ibis::fuzz, ibis::bylt, and ibis::zona.

References ibis::index::bits, ibis::index::col, ibis::gVerbose, ibis::column::name(), ibis::part::name(), ibis::index::nrows, ibis::column::partition(), and array_t< T >::size().

Referenced by ibis::category::append(), construct(), and relic().

int ibis::relic::read

(

ibis::fileManager::storage *

st

)

[virtual]

Reconstructs an index from an array of bytes.

Intended for internal use only!

Implements ibis::index.

Reimplemented in ibis::slice, ibis::fade, ibis::fuzz, ibis::bylt, and ibis::zona.

References ibis::fileManager::storage::begin(), ibis::index::bits, ibis::index::clear(), ibis::index::col, ibis::gVerbose, ibis::fileManager::storage::isFileMap(), ibis::column::logWarning(), ibis::index::nrows, ibis::index::offsets, ibis::bitvector::setSize(), ibis::index::str, and array_t< T >::swap().

int ibis::relic::read

(

const char *

name

)

[virtual]

Reconstructs an index from the named file.

The name can be the directory containing an index file. In this case, the name of the index file must be the name of the column followed by ".idx" suffix.

Implements ibis::index.

Reimplemented in ibis::slice, ibis::fade, ibis::fuzz, ibis::bylt, and ibis::zona.

References ibis::index::bits, ibis::util::logger::buffer(), clear(), ibis::index::col, ibis::index::fname, ibis::gVerbose, ibis::index::indexFileName(), ibis::fileManager::instance(), ibis::column::logMessage(), ibis::column::logWarning(), name(), ibis::index::nrows, ibis::index::offsets, ibis::fileManager::pageSize(), ibis::fileManager::recordPages(), ibis::index::str, and array_t< T >::swap().

virtual float ibis::relic::undecidable	(	const ibis::qContinuousRange &	expr,
		ibis::bitvector &	iffy
	)			const [inline, virtual]

This class and its derived classes should produce exact answers, therefore no undecidable rows.

Reimplemented from ibis::index.

References ibis::bitvector::clear().

int ibis::relic::write

(

const char *

name

)

const [virtual]

Save index to a file.

Outputs the index in a compact binary format to the named file or directory. The index file contains a header that can be identified by the function isIndex.

Implements ibis::index.

Reimplemented in ibis::slice, ibis::fade, ibis::sbiad, ibis::sapid, ibis::fuzz, ibis::bylt, and ibis::zona.

References ibis::index::activate(), ibis::index::bits, ibis::index::col, array_t< T >::empty(), ibis::index::fname, ibis::gVerbose, ibis::index::indexFileName(), ibis::column::logMessage(), ibis::column::logWarning(), ibis::column::name(), ibis::part::name(), ibis::index::nrows, ibis::column::partition(), ibis::index::RELIC, array_t< T >::size(), and ibis::index::str.

Referenced by append(), ibis::category::append(), ibis::zona::write(), ibis::fuzz::write(), and ibis::bylt::write().

---

The documentation for this class was generated from the following files:

• irelic.h
• irelic.cpp