Public Member Functions | List of all members
ibis::sbiad Class Reference

The multicomponent interval encoded index. More...

#include <irelic.h>

Inheritance diagram for ibis::sbiad:
ibis::fade ibis::relic ibis::index

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 indexdup () const
 Duplicate the content of an index object.
 
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.
 
void locate (const ibis::qContinuousRange &expr, uint32_t &hit0, uint32_t &hit1) const
 Locate the bitmaps covered by the range expression. More...
 
 relic (const relic &)
 Copy constructor.
 
 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. More...
 
 relic (const ibis::column *c, ibis::fileManager::storage *st, size_t start=8)
 Reconstruct from content of fileManager::storage. More...
 
 relic (const ibis::column *c, uint32_t nb, double *keys, int64_t *offs)
 Reconstruct index from keys and offsets.
 
 relic (const ibis::column *c, uint32_t nb, double *keys, int64_t *offs, uint32_t *bms)
 Reconstruct index from keys and offsets.
 
 relic (const ibis::column *c, uint32_t nb, double *keys, int64_t *offs, void *bms, FastBitReadBitmaps rd)
 Reconstruct index from keys and offsets.
 
virtual void serialSizes (uint64_t &, uint64_t &, uint64_t &) const
 Compute the size of arrays that would be generated by the serializatioin function (write). 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
 
virtual int write (ibis::array_t< double > &, ibis::array_t< int64_t > &, ibis::array_t< uint32_t > &) const
 Save index to three arrays. Serialize the index in memory.
 
- 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
 
bool empty () const
 The index object is considered empty if there is no bitmap or getNRows returns 0. More...
 
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::bitvectorgetBitvector (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.
 
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 (uint32_t ib, uint32_t ie, ibis::bitvector &res, uint32_t *buf) const
 Sum up bits[ib:ie-1] and place the result in res. 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 indexcreate (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)
 Compute a two-dimensional histogram. More...
 
static void printHeader (std::ostream &, const char *)
 
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.
 
- Protected Member Functions inherited from ibis::relic
virtual double computeSum () const
 Compute the sum of all values of the column indexed.
 
uint32_t locate (const double &val) const
 Find the smallest i such that vals[i] > val.
 
long mergeValues (uint32_t, uint32_t, void *) const
 Merge the values in different bitmaps into a single list. More...
 
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.
 
- Protected Member Functions inherited from ibis::index
virtual void activate () const
 Regenerate all bitvectors from the underlying storage. More...
 
virtual void activate (uint32_t i) const
 Regenerate the ith bitvector from the underlying storage.
 
virtual void activate (uint32_t i, uint32_t j) const
 Regenerate bitvectors i (inclusive) through j (exclusive) from the underlying storage. More...
 
void computeMinMax (const char *f, double &min, double &max) const
 
void dataFileName (std::string &name, const char *f=0) const
 Generate data file name from "f". More...
 
 index (const ibis::column *c=0)
 Default constructor. More...
 
 index (const ibis::column *c, ibis::fileManager::storage *s)
 Constructor with a storage object. More...
 
 index (const index &)
 Copy constructor.
 
void indexFileName (std::string &name, const char *f=0) const
 Generates index file name from "f". More...
 
void initBitmaps (int fdes)
 Prepare the bitmaps using the given file descriptor. More...
 
void initBitmaps (ibis::fileManager::storage *st)
 Prepare bitmaps from the given storage object. More...
 
void initBitmaps (uint32_t *st)
 Prepare bitmaps from the given raw pointer. More...
 
void initBitmaps (void *ctx, FastBitReadBitmaps rd)
 Prepare bitmaps from the user provided function pointer and context. More...
 
int initOffsets (int64_t *, size_t)
 Initialize the offsets from the given data array. More...
 
int initOffsets (int fdes, const char offsize, size_t start, uint32_t nobs)
 Read in the offset array. More...
 
int initOffsets (ibis::fileManager::storage *st, size_t start, uint32_t nobs)
 Regenerate the offsets array from the given storage object. More...
 
void mapValues (const char *f, VMap &bmap) const
 Map the positions of each individual value. More...
 
void mapValues (const char *f, histogram &hist, uint32_t count=0) const
 Generate a histogram. More...
 
indexoperator= (const index &)
 Assignment operator.
 
void optionalUnpack (array_t< ibis::bitvector * > &bits, const char *opt)
 A function to decide whether to uncompress the bitvectors. More...
 
- 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)
 A template function to merge list of values and a list of positions. More...
 
- Static Protected Member Functions inherited from ibis::index
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. More...
 
- Protected Attributes inherited from ibis::fade
array_t< uint32_t > bases
 
array_t< uint32_t > cnts
 
- Protected Attributes inherited from ibis::relic
array_t< double > vals
 
- Protected Attributes inherited from ibis::index
array_t< ibis::bitvector * > bits
 A list of bitvectors.
 
bitmapReaderbreader
 The functor to read serialized bitmaps from a more complex source.
 
const ibis::columncol
 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. More...
 
array_t< int32_t > offset32
 Starting positions of the bitvectors.
 
array_t< int64_t > offset64
 Starting positions of the bitvectors. More...
 
ibis::fileManager::storagestr
 The underlying storage. More...
 

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::part::name(), ibis::column::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:

nrows(uint32_t) -- the number of bits in a bit sequence
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::part::name(), ibis::column::name(), ibis::index::nrows, print(), and ibis::array_t< T >::size().

Member Function Documentation

long ibis::sbiad::append ( const char *  dt,
const char *  df,
uint32_t  nnew 
)
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().

long ibis::sbiad::evaluate ( const ibis::qDiscreteRange expr,
ibis::bitvector answer 
) const
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().

virtual const char* ibis::sbiad::name ( ) const
inlinevirtual

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

Reimplemented from ibis::fade.

int ibis::sbiad::write ( const char *  dt) const
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::fileManager::instance(), ibis::util::flock::isLocked(), ibis::index::SBIAD, UnixOpen, ibis::fade::write32(), and ibis::fade::write64().


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

Make It A Bit Faster
Contact us
Disclaimers
FastBit source code
FastBit mailing list archive