index.h

Go to the documentation of this file.

//File: $Id$
// Author: John Wu <John.Wu at ACM.org>
//         Lawrence Berkeley National Laboratory
// Copyright 2000-2012 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 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, 
        SLICE,  
        FADE,   
        SBIAD,  
        SAPID,  
        EGALE,  
        MOINS,  
        ENTRE,  
        BAK,    
        BAK2,   


        KEYWORDS,       
        MESH,   
        BAND,   
        DIREKTE,
        GENERIC,
        BYLT,   
        FUZZ,   
        ZONA,   
        FUGE,   
        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&,
                              ibis::bitvector&) 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 read(const char* name) = 0;
    virtual int read(ibis::fileManager::storage* st) = 0;

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

    inline 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;}

    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(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);
    // a static function to assign bases for multicomponent schemes
    static void setBases(array_t<uint32_t>& bases, uint32_t card,
                         uint32_t nbase = 2);

protected:
    // shared members for all indexes
    const ibis::column* col;
    mutable ibis::fileManager::storage* str;
    mutable const char* fname;
    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), nrows(0) {}
    index(const ibis::column* c, ibis::fileManager::storage* s);

    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();

    // 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(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);

    class barrel;

private:
    index(const index&); // no copy constructor
    index& operator=(const index&); // no assignment operator
}; // 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


inline float ibis::index::sizeInBytes() const {
    if (offset64.size() > bits.size()) {
        return (float)offset64[bits.size()];
    }
    else if (offset32.size() > bits.size()) {
        return (float)offset32[bits.size()];
    }
    else if (str != 0) {
        return (float)str->size();
    }
    else if (*fname != 0) {
        return (float)ibis::util::getFileSize(fname);
    }
    else {
        return FLT_MAX;
    }
} // ibis::index::sizeInBytes

#endif // IBIS_INDEX_H