The multicomponent interval encoded index. More...
#include <irelic.h>
Inheritance diagram for ibis::sbiad:
Public Member Functions | |
| virtual long | append (const char *dt, const char *df, uint32_t nnew) |
| Create an index based on data in df and append the result to the index in dt. More... | |
| virtual long | evaluate (const ibis::qContinuousRange &expr, ibis::bitvector &hits) const |
Compute the hits as a bitvector. | |
| virtual long | evaluate (const ibis::qDiscreteRange &expr, ibis::bitvector &hits) const |
| Resolve a discrete range condition. More... | |
| virtual const char * | name () const |
Returns the name of the index, similar to the function type, but returns a string instead. More... | |
| virtual void | print (std::ostream &out) const |
| The printing function. | |
| sbiad (const ibis::column *c=0, const char *f=0, const uint32_t nbase=2) | |
| Constructor. More... | |
| sbiad (const ibis::column *c, ibis::fileManager::storage *st, size_t start=8) | |
| Reconstruct an index from a storage object. More... | |
| virtual void | speedTest (std::ostream &out) const |
| A simple function to test the speed of the bitvector operations. | |
| virtual INDEX_TYPE | type () const |
| Returns an index type identifier. | |
| virtual int | write (const char *dt) const |
| Write the content of this index to a file. More... | |
 Public Member Functions inherited from ibis::fade | |
| virtual void | binWeights (std::vector< uint32_t > &b) const |
| Return the exact count for each distinct value. | |
| virtual uint32_t | estimate (const ibis::qContinuousRange &expr) const |
| Return the number of hits satisfying the given continuous range expression. More... | |
| virtual double | estimateCost (const ibis::qContinuousRange &expr) const |
| Estimate the cost of resolving the continuous range expression. More... | |
| fade (const ibis::column *c=0, const char *f=0, const uint32_t nbase=2) | |
| Construct a bitmap index from current data. | |
| fade (const ibis::column *c, ibis::fileManager::storage *st, size_t start=8) | |
| Reconstruct from content of fileManager::storage. More... | |
| virtual double | getSum () const |
| Compute the sum of all values of the column indexed. | |
| virtual int | read (const char *idxfile) |
Read the index contained in the file named f. | |
| virtual int | read (ibis::fileManager::storage *st) |
| Reconstruct an index from a piece of consecutive memory. | |
| virtual long | select (const ibis::qContinuousRange &, void *) const |
| Evaluate the range condition and select values. | |
| virtual long | select (const ibis::qContinuousRange &, void *, ibis::bitvector &) const |
| Evaluate the range condition, select values, and record the positions. | |
| Public Member Functions inherited from ibis::relic | |
| long | append (const ibis::relic &tail) |
| Append tail to this index. More... | |
| long | append (const array_t< uint32_t > &ind) |
| Append a list of integers. More... | |
| virtual void | binBoundaries (std::vector< double > &b) const |
| Return all distinct values as the bin boundaries. | |
| void | construct (const char *f=0) |
| Construct a new index in memory. More... | |
| template<typename E > | |
| void | construct (const array_t< E > &arr) |
| Construct an index from in-memory values. More... | |
| 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. More... | |
| 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, ..)'. More... | |
| virtual uint32_t | estimate (const ibis::qDiscreteRange &) const |
| Compute the number of hits satisfying the discrete range expression. | |
| virtual void | estimate (const ibis::relic &idx2, const ibis::deprecatedJoin &expr, const ibis::bitvector &mask, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const |
| Estimate the pairs for the range join operator. More... | |
| virtual void | estimate (const ibis::relic &idx2, const ibis::deprecatedJoin &expr, const ibis::bitvector &mask, const ibis::qRange *const range1, const ibis::qRange *const range2, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const |
| virtual int64_t | estimate (const ibis::relic &idx2, const ibis::deprecatedJoin &expr, const ibis::bitvector &mask) const |
| Estimate an upper bound for the number of pairs produced from marked records. More... | |
| virtual int64_t | estimate (const ibis::relic &idx2, const ibis::deprecatedJoin &expr, const ibis::bitvector &mask, const ibis::qRange *const range1, const ibis::qRange *const range2) const |
| virtual double | estimateCost (const ibis::qDiscreteRange &expr) const |
| Estimate the cost of resolving the discrete range expression. More... | |
| virtual long | getCumulativeDistribution (std::vector< double > &bds, std::vector< uint32_t > &cts) const |
| Compute a cumulative distribition. | |
| virtual long | getDistribution (std::vector< double > &bds, std::vector< uint32_t > &cts) const |
| Compute a histogram. | |
| virtual double | getMax () const |
| The maximum value recorded in the index. | |
| virtual double | getMin () const |
| The minimum value recorded in the index. | |
| array_t< uint32_t > * | keys (const ibis::bitvector &mask) const |
| Convert the bitvector mask into bin numbers. | |
| template<typename T > | |
| long | mergeValuesT (const array_t< T > &vs, const array_t< const bitvector * > &ps, array_t< T > &res) |
| A template function to merge list of values and a list of positions. More... | |
| relic (const ibis::column *c, const char *f=0) | |
| Construct a basic bitmap index. More... | |
| relic (const ibis::column *c, uint32_t popu, uint32_t ntpl=0) | |
| Construct a dummy index. More... | |
| 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, ibis::fileManager::storage *st, size_t start=8) | |
| Reconstruct from content of fileManager::storage. More... | |
| virtual float | undecidable (const ibis::qContinuousRange &, ibis::bitvector &iffy) const |
| This class and its derived classes should produce exact answers, therefore no undecidable rows. More... | |
| virtual float | undecidable (const ibis::qDiscreteRange &, ibis::bitvector &iffy) const |
| Public Member Functions inherited from ibis::index | |
| void | addBins (uint32_t ib, uint32_t ie, ibis::bitvector &res) const |
Add the sum of bits[ib] through bits[ie-1] to res. More... | |
| void | addBins (uint32_t ib, uint32_t ie, ibis::bitvector &res, const ibis::bitvector &tot) const |
Compute the sum of bit vectors [ib, ie). More... | |
| virtual int | contractRange (ibis::qContinuousRange &) const |
| virtual void | estimate (const ibis::index &idx2, const ibis::deprecatedJoin &expr, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const |
| Estimate the pairs for the range join operator. | |
| virtual void | estimate (const ibis::index &idx2, const ibis::deprecatedJoin &expr, const ibis::bitvector &mask, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const |
| Estimate the pairs for the range join operator. More... | |
| virtual void | estimate (const ibis::index &idx2, const ibis::deprecatedJoin &expr, const ibis::bitvector &mask, const ibis::qRange *const range1, const ibis::qRange *const range2, ibis::bitvector64 &lower, ibis::bitvector64 &upper) const |
| virtual int64_t | estimate (const ibis::index &idx2, const ibis::deprecatedJoin &expr) const |
| Estimate an upper bound for the number of pairs. | |
| virtual int64_t | estimate (const ibis::index &idx2, const ibis::deprecatedJoin &expr, const ibis::bitvector &mask) const |
| Estimate an upper bound for the number of pairs produced from marked records. More... | |
| virtual int64_t | estimate (const ibis::index &idx2, const ibis::deprecatedJoin &expr, const ibis::bitvector &mask, const ibis::qRange *const range1, const ibis::qRange *const range2) const |
| virtual void | estimate (const ibis::deprecatedJoin &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::deprecatedJoin &expr, const ibis::bitvector &mask, const ibis::qRange *const range1, const ibis::qRange *const range2) const |
| virtual int | expandRange (ibis::qContinuousRange &) 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. More... | |
| virtual const ibis::bitvector * | getBitvector (uint32_t i) const |
| Return a pointer to the ith bitvector used in the index (may be 0). | |
| uint32_t | getNRows () const |
| Return the number of rows represented by this object. | |
| template<typename E > | |
| void | mapValues (const array_t< E > &val, VMap &bmap) |
| template<typename E > | |
| void | mapValues (const array_t< E > &val, histogram &hist, uint32_t count) |
| template<typename E > | |
| void | mapValues (const array_t< E > &val, array_t< E > &bounds, std::vector< uint32_t > &cnts) |
| template<typename E1 , typename E2 > | |
| 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. More... | |
| virtual uint32_t | numBitvectors () const |
| Returns the number of bit vectors used by the index. | |
| float | sizeInBytes () const |
| Estiamte the size of this index object measured in bytes. More... | |
| void | sumBins (uint32_t ib, uint32_t ie, ibis::bitvector &res) const |
Sum up bits[ib:ie-1] and place the result in res. More... | |
| void | sumBins (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). More... | |
| void | sumBins (const ibis::array_t< uint32_t > &, ibis::bitvector &) const |
| Sum up the bits in in the specified bins. | |
| virtual | ~index () |
| The destructor. | |
Additional Inherited Members | |
| Public Types inherited from ibis::index | |
|
typedef std::map< double, uint32_t > | histogram |
| enum | INDEX_TYPE { BINNING =0, RANGE, MESA, AMBIT, PALE, PACK, ZONE, RELIC, ROSTER, SKIVE, FADE, SBIAD, SAPID, EGALE, MOINS, ENTRE, BAK, BAK2, KEYWORDS, MESH, BAND, DIREKTE, GENERIC, BYLT, FUZZ, ZONA, FUGE, SLICE, 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 |
| Static Public Member Functions inherited from ibis::index | |
| static void | addBits (const array_t< bitvector * > &bits, uint32_t ib, uint32_t ie, ibis::bitvector &res) |
Add the pile[ib:ie-1] to res. More... | |
| static index * | create (const column *c, const char *name=0, const char *spec=0, int inEntirety=0) |
| Index factory. More... | |
| 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. More... | |
| static bool | isIndex (const char *f, INDEX_TYPE t) |
| Is the named file an index file? Read the header of the named file to determine if it contains an index of the specified type. More... | |
| template<typename E > | |
| static void | mapValues (const array_t< E > &val, VMap &bmap) |
| 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, array_t< E > &bounds, std::vector< uint32_t > &cnts) |
| 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) |
| 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). More... | |
| static void | sumBits (const array_t< bitvector * > &bits, uint32_t ib, uint32_t ie, ibis::bitvector &res) |
Sum up pile[ib:ie-1] and place the result in res. More... | |
| static void | sumBits (const array_t< bitvector * > &bits, const ibis::bitvector &tot, uint32_t ib, uint32_t ie, ibis::bitvector &res) |
Sum up pile[ib:ie-1] and add the result to res. More... | |
| Protected Member Functions inherited from ibis::fade | |
| virtual void | clear () |
| Clear the existing content. More... | |
| virtual size_t | getSerialSize () const throw () |
| Estiamte the size of the index in a file. | |
| int | write32 (int fdes) const |
| Write the content to a file already opened. | |
| int | write64 (int fdes) const |
| Write the content to a file already opened. | |
| Static Protected Member Functions inherited from ibis::relic | |
| template<typename T > | |
| static long | mergeValuesT (const array_t< T > &vs, const array_t< const bitvector * > &ps, array_t< T > &res) |
| Protected Attributes inherited from ibis::fade | |
| array_t< uint32_t > | bases |
| array_t< uint32_t > | cnts |
Detailed Description
The multicomponent interval encoded index.
Defined by Chan and Ioannidis (SIGMOD 99).
Constructor & Destructor Documentation
| ibis::sbiad::sbiad | ( | const ibis::column * | c = 0, |
| const char * | f = 0, |
||
| const uint32_t | nbase = 2 |
||
| ) |
Constructor.
If an index exists in the specified location, it will be read, otherwise a new bitmap index will be created from current data.
References ibis::index::bits, ibis::fade::clear(), ibis::index::col, ibis::gVerbose, ibis::column::name(), ibis::part::name(), ibis::part::nRows(), ibis::index::nrows, print(), and ibis::array_t< T >::size().
| ibis::sbiad::sbiad | ( | const ibis::column * | c, |
| ibis::fileManager::storage * | st, | ||
| size_t | start = 8 |
||
| ) |
Reconstruct an index from a storage object.
The content of the file (following the 8-byte header) is as follows:
nobs (uint32_t) -- the 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 distinct values as doubles
offset([nobs+1]) -- the starting positions of the bit sequences
(as bit vectors)
nbases(uint32_t) -- the number of components (bases) used
cnts (uint32_t[card]) -- the counts for each distinct value
bases(uint32_t[nbases]) -- the bases sizes
bitvectors -- the bitvectors one after another
References ibis::index::bits, ibis::index::col, ibis::gVerbose, ibis::column::name(), ibis::part::name(), ibis::index::nrows, print(), and ibis::array_t< T >::size().
Member Function Documentation
|
virtual |
Create an index based on data in df and append the result to the index in dt.
Reimplemented from ibis::fade.
References ibis::util::clear().
|
virtual |
Resolve a discrete range condition.
The answer is a bitvector marking the rows satisfying the range conditions.
Reimplemented from ibis::fade.
References ibis::bitvector::cnt(), ibis::qDiscreteRange::getValues(), ibis::bitvector::set(), ibis::array_t< T >::size(), and ibis::bitvector::size().
|
inlinevirtual |
Returns the name of the index, similar to the function type, but returns a string instead.
Reimplemented from ibis::fade.
|
virtual |
Write the content of this index to a file.
The argument is the name of the directory or the index file name.
Reimplemented from ibis::fade.
References ibis::fileManager::flushFile(), ibis::gVerbose, ibis::fileManager::instance(), ibis::index::SBIAD, UnixOpen, ibis::fade::write32(), and ibis::fade::write64().
The documentation for this class was generated from the following files:
- irelic.h
- isbiad.cpp
