irelic.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_IRELIC_H
#define IBIS_IRELIC_H







#if defined(_WIN32) && defined(_MSC_VER)
#pragma warning(disable:4786)   // some identifier longer than 256 characters
#endif
#include "index.h"

class ibis::relic : public ibis::index {
public:
    virtual ~relic() {clear();};
    relic(const ibis::column* c, const char* f = 0);
    relic(const ibis::column* c, uint32_t popu, uint32_t ntpl=0);
    relic(const ibis::column* c, uint32_t card, array_t<uint32_t>& ints);
    relic(const ibis::column* c, ibis::fileManager::storage* st,
          size_t start = 8);

    virtual void print(std::ostream& out) const;
    virtual int  write(const char* dt) const;
    virtual int  read(const char* idxfile);
    virtual int  read(ibis::fileManager::storage* st);
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long select(const ibis::qContinuousRange&, void*) const;
    virtual long select(const ibis::qContinuousRange&, void*,
                        ibis::bitvector&) const;

    using ibis::index::estimate;
    using ibis::index::estimateCost;
    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const;

    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const {
        (void) evaluate(expr, lower);
        upper.clear();
    }
    virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
    virtual float undecidable(const ibis::qContinuousRange&,
                              ibis::bitvector& iffy) const {
        iffy.clear();
        return 0.0;
    }
    virtual void estimate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const {
        evaluate(expr, lower);
        upper.clear();
    }
    virtual uint32_t estimate(const ibis::qDiscreteRange&) const;
    virtual float undecidable(const ibis::qDiscreteRange&,
                              ibis::bitvector& iffy) const {
        iffy.clear();
        return 0.0;
    }

    virtual double estimateCost(const ibis::qContinuousRange& expr) const;
    virtual double estimateCost(const ibis::qDiscreteRange& expr) const;

    virtual void estimate(const ibis::relic& idx2,
                          const ibis::deprecatedJoin& expr,
                          const ibis::bitvector& mask,
                          ibis::bitvector64& lower,
                          ibis::bitvector64& upper) const;
    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;
    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 INDEX_TYPE type() const {return RELIC;}
    virtual const char* name() const {return "basic";}
    // bin boundaries and counts of each bin
    virtual void binBoundaries(std::vector<double>& b) const;
    virtual void binWeights(std::vector<uint32_t>& b) const;

    virtual long getCumulativeDistribution(std::vector<double>& bds,
                                           std::vector<uint32_t>& cts) const;
    virtual long getDistribution(std::vector<double>& bds,
                                 std::vector<uint32_t>& cts) const;
    virtual double getMin() const {return (vals.empty()?DBL_MAX:vals[0]);}
    virtual double getMax() const {return (vals.empty()?-DBL_MAX:vals.back());}
    virtual double getSum() const;

    virtual void speedTest(std::ostream& out) const;
    long append(const ibis::relic& tail);
    long append(const array_t<uint32_t>& ind);
    array_t<uint32_t>* keys(const ibis::bitvector& mask) const;

    template <typename T>
    struct valpos {
        T val;
        bitvector::indexSet ind;
        bitvector::word_t j;

        valpos<T>() : val(0), j(0) {}
        valpos<T>(const T v, const bitvector& b)
        : val(v), ind(b.firstIndexSet()), j(0) {
            if (ind.nIndices() > 0 && ind.isRange())
                j = *(ind.indices());
        }

        bitvector::word_t position() const {
            if (ind.isRange())
                return j;
            else
                return ind.indices()[j];
        }

        void next() {
            ++ j;
            if (ind.isRange()) {
                if (j >= ind.indices()[1]) {
                    ++ ind;
                    if (ind.nIndices() > 0 && ind.isRange())
                        j = ind.indices()[0];
                    else
                        j = 0;
                }
            }
            else if (j >= ind.nIndices()) {
                ++ ind;
                if (ind.nIndices() > 0 && ind.isRange())
                    j = ind.indices()[0];
                else
                    j = 0;
            }
        }
    }; // valpos

    template<typename T>
    struct comparevalpos {
        bool operator()(const valpos<T>* x, const valpos<T>* y) {
            return (x->position() > y->position());
        }
    }; // comparevalpos

protected:
    // protected member variables
    array_t<double> vals;

    int write32(int fdes) const;
    int write64(int fdes) const;
    // protected member functions
    uint32_t locate(const double& val) const;
    void     locate(const ibis::qContinuousRange& expr,
                    uint32_t& hit0, uint32_t& hit1) const;

    // a dummy constructor
    relic() : ibis::index() {}
    // free current resources, re-initialized all member variables
    virtual void clear();
    virtual double computeSum() const;
    virtual size_t getSerialSize() const throw();

    template <typename E>
    void construct(const array_t<E>& arr);
    void construct(const char* f = 0);

    long mergeValues(uint32_t, uint32_t, void*) const;
    template <typename T> static long
    mergeValuesT(const array_t<T>& vs,
                 const array_t<const bitvector*>& ps,
                 array_t<T>& res);

    template <typename T> struct mappedValues;

private:
    // private member functions
    int64_t equiJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
                     ibis::bitvector64& hits) const;
    int64_t deprecatedJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
                      const double& delta, ibis::bitvector64& hits) const;
    int64_t compJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
                     const ibis::math::term& delta,
                     ibis::bitvector64& hits) const;

    int64_t equiJoin(const ibis::relic& idx2,
                     const ibis::bitvector& mask) const;
    int64_t deprecatedJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
                      const double& delta) const;
    int64_t compJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
                     const ibis::math::term& delta) const;

    int64_t equiJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
                     const ibis::qRange* const range1,
                     const ibis::qRange* const range2,
                     ibis::bitvector64& hits) const;
    int64_t deprecatedJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
                      const ibis::qRange* const range1,
                      const ibis::qRange* const range2,
                      const double& delta, ibis::bitvector64& hits) const;
    int64_t compJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
                     const ibis::qRange* const range1,
                     const ibis::qRange* const range2,
                     const ibis::math::term& delta,
                     ibis::bitvector64& hits) const {
        return compJoin(idx2, mask, delta, hits);
    }

    int64_t equiJoin(const ibis::relic& idx2,
                     const ibis::bitvector& mask,
                     const ibis::qRange* const range1,
                     const ibis::qRange* const range2) const;
    int64_t deprecatedJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
                      const ibis::qRange* const range1,
                      const ibis::qRange* const range2,
                      const double& delta) const;
    int64_t compJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
                     const ibis::qRange* const range1,
                     const ibis::qRange* const range2,
                     const ibis::math::term& delta) const {
        return compJoin(idx2, mask, delta);
    }

    relic(const relic&);
    relic& operator=(const relic&);
}; // ibis::relic

class ibis::slice : public ibis::relic {
public:
    virtual ~slice() {clear();};
    slice(const ibis::column* c = 0, const char* f = 0);
    slice(const ibis::column* c, ibis::fileManager::storage* st,
          size_t start = 8);

    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);

    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long select(const ibis::qContinuousRange&, void*) const {
        return -1;}
    virtual long select(const ibis::qContinuousRange&, void*,
                        ibis::bitvector&) const {
        return -1;}

    using ibis::relic::estimate;
    using ibis::relic::estimateCost;
    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const;

    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;
    virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
    virtual INDEX_TYPE type() const {return SLICE;}
    virtual const char* name() const {return "bit-sliced";}
    // number of records in each bin
    virtual void binWeights(std::vector<uint32_t>& b) const;
    virtual double getSum() const;

    virtual void speedTest(std::ostream& out) const;
    virtual double estimateCost(const ibis::qContinuousRange&) const {
        double ret;
        if (offset64.size() > bits.size())
            ret = offset64.back();
        else if (offset32.size() > bits.size())
            ret = offset32.back();
        else
            ret = 0.0;
        return ret;
    }
    virtual double estimateCost(const ibis::qDiscreteRange& expr) const {
        double ret;
        if (offset64.size() > bits.size())
            ret = offset64.back();
        else if (offset32.size() > bits.size())
            ret = offset32.back();
        else
            ret = 0.0;
        return ret;
    }

protected:
    virtual void clear();
    virtual size_t getSerialSize() const throw();

private:
    // private member variables
    array_t<uint32_t> cnts; // the counts for each distinct value

    // private member functions
    void construct1(const char* f = 0); // uses more temporary storage
    void construct2(const char* f = 0); // passes through data twice
    void setBit(const uint32_t i, const double val);

    int write32(int fdes) const;
    int write64(int fdes) const;
    void evalGE(ibis::bitvector& res, uint32_t b) const;
    void evalEQ(ibis::bitvector& res, uint32_t b) const;

    slice(const slice&);
    slice& operator=(const slice&);
}; // ibis::slice

class ibis::fade : public ibis::relic {
public:
    virtual ~fade() {clear();};
    fade(const ibis::column* c = 0, const char* f = 0,
         const uint32_t nbase = 2);
    fade(const ibis::column* c, ibis::fileManager::storage* st,
         size_t start = 8);

    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);

    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long select(const ibis::qContinuousRange&, void*) const {
        return -1;}
    virtual long select(const ibis::qContinuousRange&, void*,
                        ibis::bitvector&) const {
        return -1;}

    using ibis::relic::estimate;
    using ibis::relic::estimateCost;
    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const;

    virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
    virtual INDEX_TYPE type() const {return FADE;}
    virtual const char* name() const {return "multi-level range";}

    virtual void speedTest(std::ostream& out) const;
    // number of records in each bin
    virtual void binWeights(std::vector<uint32_t>& b) const;
    virtual double getSum() const;
    virtual double estimateCost(const ibis::qContinuousRange& expr) const;
    //virtual double estimateCost(const ibis::qDiscreteRange& expr) const;

protected:
    // protected member variables
    array_t<uint32_t> cnts; // the counts for each distinct value
    array_t<uint32_t> bases;// the values of the bases used

    // protected member functions to be used by derived classes
    int write32(int fdes) const;
    int write64(int fdes) const;
    virtual void clear();
    virtual size_t getSerialSize() const throw();

private:
    // private member functions
    void setBit(const uint32_t i, const double val);
    void construct1(const char* f = 0, const uint32_t nbase = 2);
    void construct2(const char* f = 0, const uint32_t nbase = 2);

    void evalEQ(ibis::bitvector& res, uint32_t b) const;
    void evalLE(ibis::bitvector& res, uint32_t b) const;
    void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;

    fade(const fade&);
    fade& operator=(const fade&);
}; // ibis::fade

class ibis::sbiad : public ibis::fade {
public:
    virtual ~sbiad() {clear();};
    sbiad(const ibis::column* c = 0, const char* f = 0,
          const uint32_t nbase = 2);
    sbiad(const ibis::column* c, ibis::fileManager::storage* st,
          size_t start = 8);

    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const;

    virtual INDEX_TYPE type() const {return SBIAD;}
    virtual const char* name() const {return "multi-level interval";}

    virtual void speedTest(std::ostream& out) const;
    //virtual double estimateCost(const ibis::qContinuousRange& expr) const;
    //virtual double estimateCost(const ibis::qDiscreteRange& expr) const;

private:
    // private member functions
    void setBit(const uint32_t i, const double val);
    void construct1(const char* f = 0, const uint32_t nbase = 2);
    void construct2(const char* f = 0, const uint32_t nbase = 2);

    void evalEQ(ibis::bitvector& res, uint32_t b) const;
    void evalLE(ibis::bitvector& res, uint32_t b) const;
    void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;

    sbiad(const sbiad&);
    sbiad& operator=(const sbiad&);
}; // ibis::sbiad

class ibis::sapid : public ibis::fade {
public:
    virtual ~sapid() {clear();};
    sapid(const ibis::column* c = 0, const char* f = 0,
          const uint32_t nbase = 2);
    sapid(const ibis::column* c, ibis::fileManager::storage* st,
          size_t start = 8);

    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const;

    virtual INDEX_TYPE type() const {return SAPID;}
    virtual const char* name() const {return "multi-level equality";}

    virtual void speedTest(std::ostream& out) const;
    //virtual double estimateCost(const ibis::qContinuousRange& expr) const;
    //virtual double estimateCost(const ibis::qDiscreteRange& expr) const;

private:
    // private member functions
    void setBit(const uint32_t i, const double val);
    void construct1(const char* f = 0, const uint32_t nbase = 2);
    void construct2(const char* f = 0, const uint32_t nbase = 2);

    void addBits_(uint32_t ib, uint32_t ie, ibis::bitvector& res) const;
    void evalEQ(ibis::bitvector& res, uint32_t b) const;
    void evalLE(ibis::bitvector& res, uint32_t b) const;
    void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;

    sapid(const sapid&);
    sapid& operator=(const sapid&);
}; // ibis::sapid

class ibis::fuzz : public ibis::relic {
public:
    virtual ~fuzz() {clear();};
    fuzz(const ibis::column* c = 0, const char* f = 0);
    fuzz(const ibis::column* c, ibis::fileManager::storage* st,
         size_t start = 8);

    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);

    virtual long append(const char* dt, const char* df, uint32_t nnew);

    using ibis::relic::evaluate;
    using ibis::relic::estimate;
    using ibis::relic::estimateCost;
    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
    virtual double estimateCost(const ibis::qContinuousRange& expr) const;

    virtual INDEX_TYPE type() const {return FUZZ;}
    virtual const char* name() const {return "interval-equality";}

protected:
    virtual void clear();
    virtual size_t getSerialSize() const throw();

private:
    mutable array_t<bitvector*> cbits;
    array_t<uint32_t> cbounds;
    mutable array_t<int32_t> coffset32;
    mutable array_t<int64_t> coffset64;

    void coarsen(); // given fine level, add coarse level
    void activateCoarse() const; // activate all coarse level bitmaps
    void activateCoarse(uint32_t i) const; // activate one bitmap
    void activateCoarse(uint32_t i, uint32_t j) const;

    int writeCoarse32(int fdes) const;
    int writeCoarse64(int fdes) const;
    int readCoarse(const char *fn);
    void clearCoarse();

    long coarseEstimate(uint32_t lo, uint32_t hi) const;
    long coarseEvaluate(uint32_t lo, uint32_t hi, ibis::bitvector& res) const;

    fuzz(const fuzz&);
    fuzz& operator=(const fuzz&);
}; // ibis::fuzz

class ibis::bylt : public ibis::relic {
public:
    virtual ~bylt() {clear();};
    bylt(const ibis::column* c = 0, const char* f = 0);
    bylt(const ibis::column* c, ibis::fileManager::storage* st,
         size_t start = 8);

    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);

    virtual long append(const char* dt, const char* df, uint32_t nnew);

    using ibis::relic::evaluate;
    using ibis::relic::estimate;
    using ibis::relic::estimateCost;
    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
    virtual double estimateCost(const ibis::qContinuousRange& expr) const;

    virtual INDEX_TYPE type() const {return BYLT;}
    virtual const char* name() const {return "range-equality";}

protected:
    virtual void clear();
    virtual size_t getSerialSize() const throw();

private:
    // the fine level is stored in ibis::relic, the parent class, only the
    // coarse bins are stored here.  The coarse bins use integer bin
    // boundaries; these integers are indices to the array vals and bits.
    mutable array_t<bitvector*> cbits;
    array_t<uint32_t> cbounds;
    mutable array_t<int32_t> coffset32;
    mutable array_t<int64_t> coffset64;

    void coarsen(); // given fine level, add coarse level
    void activateCoarse() const; // activate all coarse level bitmaps
    void activateCoarse(uint32_t i) const; // activate one bitmap
    void activateCoarse(uint32_t i, uint32_t j) const;

    int writeCoarse32(int fdes) const;
    int writeCoarse64(int fdes) const;
    int readCoarse(const char *fn);

    bylt(const bylt&);
    bylt& operator=(const bylt&);
}; // ibis::bylt

class ibis::zona : public ibis::relic {
public:
    virtual ~zona() {clear();};
    zona(const ibis::column* c = 0, const char* f = 0);
    zona(const ibis::column* c, ibis::fileManager::storage* st,
         size_t start = 8);

    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);

    virtual long append(const char* dt, const char* df, uint32_t nnew);

    using ibis::relic::evaluate;
    using ibis::relic::estimate;
    using ibis::relic::estimateCost;
    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
    virtual double estimateCost(const ibis::qContinuousRange& expr) const;

    virtual INDEX_TYPE type() const {return ZONA;}
    virtual const char* name() const {return "equality-equality";}

protected:
    virtual void clear();
    virtual size_t getSerialSize() const throw();

private:
    // the fine level is stored in ibis::relic, the parent class, only the
    // coarse bins are stored here.  The coarse bins use integer bin
    // boundaries; these integers are indices to the array vals and bits.
    mutable array_t<bitvector*> cbits;
    array_t<uint32_t> cbounds;
    mutable array_t<int32_t> coffset32;
    mutable array_t<int64_t> coffset64;

    void coarsen(); // given fine level, add coarse level
    void activateCoarse() const; // activate all coarse level bitmaps
    void activateCoarse(uint32_t i) const; // activate one bitmap
    void activateCoarse(uint32_t i, uint32_t j) const;

    int writeCoarse32(int fdes) const;
    int writeCoarse64(int fdes) const;
    int readCoarse(const char *fn);

    zona(const zona&);
    zona& operator=(const zona&);
}; // ibis::zona

template <typename T>
struct ibis::relic::mappedValues {
}; // ibis::relic::mappedValues
#endif // IBIS_IRELIC_H