index.h

Go to the documentation of this file.

//File: $Id$
// Author: John Wu <John.Wu at ACM.org>
//         Lawrence Berkeley National Laboratory
// Copyright (c) 2000-2016 the Regents of the University of California
#ifndef IBIS_INDEX_H
#define IBIS_INDEX_H
#if defined(_WIN32) && defined(_MSC_VER)
#pragma warning(disable:4786)   // some identifier longer than 256 characters
#endif
#include "qExpr.h"
#include "bitvector.h"

#include <string>
#include <limits>       // std::numeric_limits

namespace ibis { // the concrete classes of index hierarchy
    class bin;   // equal size bins (equality encoded bitmap index)
    class range; // one-sided range encoded (cumulative) index
    class mesa;  // interval encoded index (two-sided ranges)
    class ambit; // two-level, cumulative index (cumulate on all levels)
    class pale;  // two-level, cumulative on the fine level only
    class pack;  // two-level, cumulative on the coarse level only
    class zone;  // two-level, do not cumulate on either levels
    class relic; // the basic bitmap index (one bitmap per distinct value)
    class skive; // a binary encoded index with repacking of keyvalues
    class slice; // the bit slice index (binary encoding of ibis::relic)
    class fade;  // a more controlled slice (multicomponent range code)
    class sbiad; // Italian translation of fade (multicomponent interval code)
    class sapid; // closest word to sbiad in English (multicomponent equality
                 // code)
    class egale; // French word for "equal" (multicomponent equality code on
                 // bins)
    class moins; // French word for "less" (multicomponent range code on bins)
    class entre; // French word for "in between" (multicomponent interval code
                 // on bins)
    class bak;   // Dutch word for "bin" (simple equality encoding for
                 // values mapped to reduced precision floating-point
                 // values)
    class bak2;  // a variation of bak that splits each bak bin in two
//     class waaier;// Dutch word for "range" (simple range encoding for values
//               // mapped to reduced precision floating-point values)
//     class tussen;// Dutch word for "in between" (simple interval encoding
//               // for values mapped to reduce precision floating-point
//               // values)
//     class uguale;// Italian word for "equal" (multicomponent version of bak)
//     class meno;  // Italian word for "less" (multicomponent version of waaier)
//     class fra;   // Italian word for "in between" (multicomponent version of
//               // tussen)
    class keywords;// A boolean version of term-document matrix.
    class mesh;  // Composite index on 2-D regular mesh
    class band;  // Composite index on 2-D bands.
    class direkte;// Directly use the integer values as bin numbers.
    class bylt;  // Unbinned version of pack.
    class zona;  // Unbinned version of zone.
    class fuzz;  // Unbinned version of interval-equality encoding.
    class fuge;  // Binned version of interval-equality encoding.
} // namespace ibis

class ibis::index {
public:
    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
    };

    static index* create(const column* c, const char* name=0,
                         const char* spec=0, int inEntirety=0);
    static bool isIndex(const char* f, INDEX_TYPE t);

    virtual ~index () {clear();};

    virtual INDEX_TYPE type() const = 0;
    virtual const char* name() const = 0;

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const = 0;
    virtual long select(const ibis::qContinuousRange&, void*) const =0;
    virtual long select(const ibis::qContinuousRange&, void*,
                        ibis::bitvector&) const =0;
    virtual long evaluate(const ibis::qDiscreteRange&,
                          ibis::bitvector&) const {
        return -1;}

    virtual void estimate(const ibis::qContinuousRange&,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const {
        lower.set(0, nrows); upper.set(1, nrows);}
    virtual uint32_t estimate(const ibis::qContinuousRange&) const {
        return nrows;}
    virtual float undecidable(const ibis::qContinuousRange &expr,
                              ibis::bitvector &iffy) const {return 0.5;}

    virtual void estimate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;
    virtual uint32_t estimate(const ibis::qDiscreteRange& expr) const;
    virtual float undecidable(const ibis::qDiscreteRange& expr,
                              ibis::bitvector& iffy) const;

    virtual void estimate(const ibis::index& idx2,
                          const ibis::deprecatedJoin& expr,
                          ibis::bitvector64& lower,
                          ibis::bitvector64& upper) const;
    virtual void estimate(const ibis::index& idx2,
                          const ibis::deprecatedJoin& expr,
                          const ibis::bitvector& mask,
                          ibis::bitvector64& lower,
                          ibis::bitvector64& upper) const;
    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;
    virtual int64_t estimate(const ibis::index& idx2,
                             const ibis::deprecatedJoin& expr,
                             const ibis::bitvector& mask) const;
    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;
    virtual int64_t estimate(const ibis::deprecatedJoin& expr,
                             const ibis::bitvector& mask,
                             const ibis::qRange* const range1,
                             const ibis::qRange* const range2) const;

    virtual double estimateCost(const ibis::qContinuousRange&) const {
        return (offset32.empty() ? (nrows<<3) : offset32.back());}
    virtual double estimateCost(const ibis::qDiscreteRange&) const {
        return (offset32.empty() ? (nrows<<3) : offset32.back());}

    virtual void print(std::ostream& out) const = 0;
    virtual int write(const char* name) const = 0;
    virtual int write(ibis::array_t<double> &,
                      ibis::array_t<int64_t> &,
                      ibis::array_t<uint32_t> &) const =0;
    virtual void serialSizes(uint64_t&, uint64_t&, uint64_t&) const =0;
    virtual int read(const char* name) = 0;
    virtual int read(ibis::fileManager::storage* st) = 0;

    virtual long append(const char*, const char*, uint32_t) {return -1;}
    virtual index* dup() const = 0;

    float sizeInBytes() const;
    virtual void speedTest(std::ostream&) const {};
    virtual uint32_t numBitvectors() const {return bits.size();}
    virtual const ibis::bitvector* getBitvector(uint32_t i) const {
        if (i < bits.size()) {
            if (bits[i] == 0)
                activate(i);
            return bits[i];
        }
        else {
            return 0;
        }
    }

    virtual void binBoundaries(std::vector<double>&) const {return;}
    virtual void binWeights(std::vector<uint32_t>&) const {return;}

    virtual long getCumulativeDistribution
    (std::vector<double>& bds, std::vector<uint32_t>& cts) const;
    virtual long getDistribution
    (std::vector<double>& bbs, std::vector<uint32_t>& cts) const;
    virtual double getMin() const {
        return std::numeric_limits<double>::quiet_NaN();}
    virtual double getMax() const {
        return std::numeric_limits<double>::quiet_NaN();}
    virtual double getSum() const {
        return std::numeric_limits<double>::quiet_NaN();}
    uint32_t getNRows() const {return nrows;}

    bool empty() const {return (bits.empty() || nrows == 0);}

    void addBins(uint32_t ib, uint32_t ie, ibis::bitvector& res) const;
    void addBins(uint32_t ib, uint32_t ie, ibis::bitvector& res,
                 const ibis::bitvector& tot) const;
    void sumBins(uint32_t ib, uint32_t ie, ibis::bitvector& res) const;
    void sumBins(uint32_t ib, uint32_t ie, ibis::bitvector& res,
                 uint32_t ib0, uint32_t ie0) const;
    void sumBins(uint32_t ib, uint32_t ie, ibis::bitvector& res,
                 uint32_t *buf) const;
    void sumBins(const ibis::array_t<uint32_t> &, ibis::bitvector&) const;

    virtual int expandRange(ibis::qContinuousRange&) const {return 0;}
    virtual int contractRange(ibis::qContinuousRange&) const {return 0;}

    typedef std::map< double, ibis::bitvector* > VMap;
    typedef std::map< double, uint32_t > histogram;
    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 divideCounts(array_t<uint32_t>& bounds,
                             const array_t<uint32_t>& cnt);

    // three static functions to perform the task of summing up bit sequences
    static void addBits(const array_t<bitvector*>& bits,
                        uint32_t ib, uint32_t ie, ibis::bitvector& res);
    static void sumBits(const array_t<bitvector*>& bits,
                        uint32_t ib, uint32_t ie, ibis::bitvector& res);
    static void sumBits(const array_t<bitvector*>& bits,
                        const ibis::bitvector& tot, uint32_t ib, uint32_t ie,
                        ibis::bitvector& res);

    static void setBases(array_t<uint32_t>& bases, uint32_t card,
                         uint32_t nbase = 2);
    static void printHeader(std::ostream&, const char*);

protected:
    // forward declarations.
    class barrel;
    class bitmapReader;

    // shared members for all indexes
    const ibis::column* col;
    mutable ibis::fileManager::storage* str;
    mutable const char* fname;
    mutable bitmapReader *breader;
    mutable array_t<int32_t> offset32;
    mutable array_t<int64_t> offset64;
    mutable array_t<ibis::bitvector*> bits;
    uint32_t nrows;

    index(const ibis::column* c=0)
        : col(c), str(0), fname(0), breader(0), nrows(0) {}
    index(const ibis::column* c, ibis::fileManager::storage* s);
    index(const index&);
    index& operator=(const index&);

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

    virtual void activate() const;
    virtual void activate(uint32_t i) const;
    virtual void activate(uint32_t i, uint32_t j) const;
    virtual void clear();
    virtual size_t getSerialSize() const throw();

    // both VMap and histogram assume that all supported data types can be
    // safely stored in double
    void mapValues(const char* f, VMap& bmap) const;
    void mapValues(const char* f, histogram& hist, uint32_t count=0) const;

    void computeMinMax(const char* f, double& min, double& max) const;
    void optionalUnpack(array_t<ibis::bitvector*>& bits,
                        const char* opt);

    int initOffsets(int64_t *, size_t);
    int initOffsets(int fdes, const char offsize, size_t start,
                    uint32_t nobs);
    int initOffsets(ibis::fileManager::storage *st, size_t start,
                    uint32_t nobs);
    void initBitmaps(int fdes);
    void initBitmaps(ibis::fileManager::storage *st);
    void initBitmaps(uint32_t *st);
    void initBitmaps(void *ctx, FastBitReadBitmaps rd);

private:

    static index* readOld(const column*, const char*,
                          fileManager::storage*, INDEX_TYPE);
    static index* buildNew(const column*, const char*, const char*);
}; // ibis::index


class ibis::index::barrel : public ibis::math::barrel {
public:
    barrel(const ibis::math::term* t) : ibis::math::barrel(t) {}

    void setValue(uint32_t i, double v) {varvalues[i] = v;}
}; // ibis::index::barrel

class ibis::index::bitmapReader {
public:
    bitmapReader(void *ctx, FastBitReadBitmaps rd)
        : _context(ctx), _reader(rd) {}

    int read(uint64_t b, uint64_t c, ibis::fileManager::buffer<uint32_t> &buf) {
        if (c == 0) return 0; // nothing to read
        if (buf.size() < c) {
            buf.resize(c);
            if (buf.size() < c) {
                LOGGER(ibis::gVerbose > 1)
                    << "Warning -- bitmapReader(" << _context << ", "
                    << reinterpret_cast<void*>(_reader) << ") failed to "
                    "allocate enough space to read " << c << " elements "
                    "from the given context";
                return -1;
            }
        }

        return _reader(_context, b, c, buf.address());
    }

    int read(uint64_t b, uint64_t c, ibis::array_t<uint32_t> &buf) {
        if (c == 0) return 0; // nothing to read
        if (buf.size() < c) {
            buf.resize(c);
            if (buf.size() < c) {
                LOGGER(ibis::gVerbose > 1)
                    << "Warning -- bitmapReader(" << _context << ", "
                    << reinterpret_cast<void*>(_reader) << ") failed to "
                    "allocate enough space to read " << c << " elements "
                    "from the given context";
                return -1;
            }
        }

        return _reader(_context, b, c, buf.begin());
    }

private:
    void *_context;
    FastBitReadBitmaps _reader;

    // Default constructor.  Declared, but not defined.
    bitmapReader();
}; // ibis::index::bitmapReader
#endif // IBIS_INDEX_H