The bit-sliced index. More...
#include <irelic.h>
Inheritance diagram for ibis::slice:
Public Member Functions | |
| virtual long | append (const char *dt, const char *df, uint32_t nnew) |
| Create index based data in dt. Have to start from data directly. | |
| 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. | |
| slice (const ibis::column *c=0, const char *f=0) | |
| Construct a bitmap index from current data. | |
| slice (const ibis::column *c, ibis::fileManager::storage *st, size_t start=8) | |
| Reconstruct from content of a storage object. More... | |
| virtual INDEX_TYPE | type () const |
| Returns an index type identifier. | |
| virtual int | write (const char *dt) const |
| Write the content of the index to the specified location. More... | |
 Public Member Functions inherited from ibis::skive | |
| virtual void | binWeights (std::vector< uint32_t > &b) const |
| Return the exact count for each distinct value. | |
| 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 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 &) const |
| Estimate the cost of resolving the continuous range expression. More... | |
| virtual double | estimateCost (const ibis::qDiscreteRange &expr) const |
| Estimate the cost of resolving the discrete range expression. 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 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 f. More... | |
| virtual int | read (ibis::fileManager::storage *st) |
| Reconstruct an index from a piece of consecutive memory. More... | |
| 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. | |
| skive (const ibis::column *c=0, const char *f=0) | |
| Construct a bitmap index from current data. | |
| skive (const ibis::column *c, ibis::fileManager::storage *st, size_t start=8) | |
| Reconstruct from content of a storage object. More... | |
| virtual void | speedTest (std::ostream &out) const |
| Time some logical operations and print out their speed. | |
| 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 index * | dup () const |
| Duplicate the content of an index object. | |
| 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 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::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. | |
| 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. | |
Static Public Member Functions | |
| static bool | isSuitable (const column &, const char *) |
| Are values of the given column suitable for a bit-sliced index? Returns true for yes. More... | |
| 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) |
| 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... | |
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 |
| Protected Member Functions inherited from ibis::skive | |
| virtual void | clear () |
| Free the memory hold by this object. | |
| void | evalEQ (ibis::bitvector &res, uint32_t b) const |
| Compute the bitvector that is the answer for the query x = b. | |
| void | evalGE (ibis::bitvector &res, uint32_t b) const |
| Compute the bitvector that is the answer for the query x >= b. | |
| virtual size_t | getSerialSize () const throw () |
| Estimate the size of the index in a file. | |
| int | write32 (int fdes) const |
| Write the content to a file opened by the caller. More... | |
| int | write64 (int fdes) const |
| Write the content to a file opened by the caller. More... | |
| 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... | |
| index & | operator= (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::skive | |
| 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. | |
| bitmapReader * | breader |
| The functor to read serialized bitmaps from a more complex source. | |
| 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. More... | |
| array_t< int32_t > | offset32 |
| Starting positions of the bitvectors. | |
| array_t< int64_t > | offset64 |
| Starting positions of the bitvectors. More... | |
| ibis::fileManager::storage * | str |
| The underlying storage. More... | |
Detailed Description
The bit-sliced index.
This version strictly slices the binary bits of the incoming values. It also supports operations on bit slices.
Constructor & Destructor Documentation
| ibis::slice::slice | ( | const ibis::column * | c, |
| ibis::fileManager::storage * | st, | ||
| size_t | start = 8 |
||
| ) |
Reconstruct from content of a storage object.
The content of the file (following the 8-byte header) is
nobs (uint32_t) -- the number of bit sequences
card (uint32_t) -- the number of possible values, i.e., cardinality
(padding to ensure the next data element is on 8-byte boundary)
values (double[card]) -- the possible values as doubles
offset ([nobs+1]) -- the starting positions of the bit sequences (as
bit vectors)
cnts (uint32_t[card]) -- the counts for each possible value
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
|
static |
Are values of the given column suitable for a bit-sliced index? Returns true for yes.
The bit-sliced index can only be used for unsigned integers. This function will return false if the column type is not integer or the integer values are not all non-negative.
References ibis::column::isSignedInteger(), ibis::column::isUnsignedInteger(), ibis::column::lowerBound(), and ibis::column::upperBound().
Referenced by slice().
|
inlinevirtual |
Returns the name of the index, similar to the function type, but returns a string instead.
Reimplemented from ibis::skive.
|
virtual |
Write the content of the index to the specified location.
The actual index file name is determined by the function indexFileName.
Reimplemented from ibis::skive.
References ibis::fileManager::flushFile(), ibis::fileManager::instance(), ibis::util::flock::isLocked(), ibis::index::SLICE, and UnixOpen.
The documentation for this class was generated from the following files:
- irelic.h
- islice.cpp
