Index.hpp

Go to the documentation of this file.

#pragma once
 
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <mutable/util/concepts.hpp>
#include <mutable/util/exception.hpp>
#include <mutable/util/macro.hpp>
#include <mutable/util/memory.hpp>
#include <utility>
#include <vector>
 
 
namespace m {
 
// Forward declarations
struct Table;
struct Schema;
 
namespace idx {
 
enum class IndexMethod { Array, Rmi };
 
struct IndexBase
{
    protected:
    IndexBase() = default;
 
    public:
    IndexBase(IndexBase&&) = default;
    virtual ~IndexBase() { }
 
    virtual void bulkload(const Table &table, const Schema &key_schema) = 0;
    /* Returns the number of entries in the index. */
    virtual std::size_t num_entries() const = 0;
    virtual IndexMethod method() const = 0;
    virtual const memory::Memory & memory() const = 0;
    /* Returns the size of the index in bytes. */
    virtual std::size_t size_in_bytes() const = 0;
 
    virtual void dump(std::ostream &out) const = 0;
    virtual void dump() const = 0;
 
    protected:
    static std::string build_query(const Table &table, const Schema &schema);
};
 
template<typename Key>
struct ArrayIndex : IndexBase
{
#ifndef NDEBUG
    static constexpr std::size_t ALLOCATION_SIZE = 1UL << 30; 
#else
    static constexpr std::size_t ALLOCATION_SIZE = 1UL << 37; 
#endif
 
    using key_type = Key;
    using value_type = std::size_t;
    using entry_type = std::pair<key_type, value_type>;
    using iterator = entry_type*;
    using const_iterator = const entry_type*;
 
    protected:
    memory::Memory memory_;
    std::size_t num_entries_; 
    bool finalized_; 
 
    struct
    {
        template<typename T, typename U>
        requires (std::same_as<T, key_type> or std::same_as<T, entry_type>) and
                 (std::same_as<U, key_type> or std::same_as<U, entry_type>)
        bool operator()(const T &_lhs, const U &_rhs) const {
            key_type lhs = M_CONSTEXPR_COND((std::same_as<T, key_type>), _lhs, _lhs.first);
            key_type rhs = M_CONSTEXPR_COND((std::same_as<U, key_type>), _rhs, _rhs.first);
            if constexpr(std::same_as<key_type, const char*>)
                return std::strcmp(lhs, rhs) < 0;
            else
                return lhs < rhs;
        }
    } cmp;
 
    public:
    ArrayIndex();
 
    void bulkload(const Table &table, const Schema &key_schema) override;
 
    std::size_t num_entries() const override { return num_entries_; }
 
    IndexMethod method() const override { return IndexMethod::Array; }
 
    const memory::Memory & memory() const override { return memory_; }
 
    /* Returns the size of the index in bytes. */
    std::size_t size_in_bytes() const override { return num_entries_ * sizeof(entry_type); }
 
    public:
    void add(const key_type key, const value_type value);
 
    virtual void finalize() {
        std::sort(begin(), end(), cmp);
        finalized_ = true;
    }
 
    bool finalized() const { return finalized_; }
 
    virtual const_iterator lower_bound(const key_type key) const {
        if (not finalized_) throw m::exception("Index is not finalized.");
        return std::lower_bound(begin(), end(), entry_type{key, value_type()}, cmp);
    }
 
    virtual const_iterator upper_bound(const key_type key) const {
        if (not finalized_) throw m::exception("Index is not finalized.");
        return std::upper_bound(begin(), end(), entry_type{key, value_type()}, cmp);
    }
 
    protected:
    iterator       begin()        { return static_cast<entry_type*>(memory_.addr()); }
    public:
    const_iterator begin()  const { return static_cast<const entry_type*>(memory_.addr()); }
    const_iterator cbegin() const { return begin(); }
    protected:
    iterator       end()        { return static_cast<entry_type*>(memory_.addr()) + num_entries_; }
    public:
    const_iterator end()  const { return static_cast<const entry_type*>(memory_.addr()) + num_entries_; }
    const_iterator cend() const { return end(); }
 
    void dump(std::ostream &out) const override { out << "ArrayIndex<" << typeid(key_type).name() << '>' << std::endl; }
    void dump() const override { dump(std::cerr); }
};
 
template<arithmetic Key>
struct RecursiveModelIndex : ArrayIndex<Key>
{
    using base_type = ArrayIndex<Key>;
    using key_type = base_type::key_type;
    using value_type = base_type::value_type;
    using entry_type = base_type::entry_type;
    using const_iterator = base_type::const_iterator;
 
    struct LinearModel
    {
        double slope;
        double intercept;
 
        LinearModel(double slope, double intercept) : slope(slope), intercept(intercept) { }
 
        double operator()(const key_type x) const { return std::fma(slope, static_cast<double>(x), intercept); }
 
        static LinearModel train_linear_spline(const_iterator first, const_iterator last,
                                               const std::size_t offset = 0, const double compression_factor = 1.0)
        {
            std::size_t n = std::distance(first, last);
            if (n == 0) return { 0.0, 0.0 };
            if (n == 1) return { 0.0, static_cast<double>(offset) * compression_factor };
            double numerator = static_cast<double>(n); // (offset + n) - offset
            double denominator = static_cast<double>((*(last - 1)).first - (*first).first);
            double slope = denominator != 0 ? numerator/denominator * compression_factor : 0.0;
            double intercept = offset * compression_factor - slope * (*first).first;
            return { slope, intercept };
        }
 
        static LinearModel train_linear_regression(const_iterator first, const_iterator last,
                                                   const std::size_t offset = 0, const double compression_factor = 1.0)
        {
            std::size_t n = std::distance(first, last);
            if (n == 0) return { 0.0, 0.0 };
            if (n == 1) return { 0.0, static_cast<double>(offset) * compression_factor };
 
            double mean_x = 0.0;
            double mean_y = 0.0;
            double c = 0.0;
            double m2 = 0.0;
 
            for (std::size_t i = 0; i != n; ++i) {
                auto x = (*(first + i)).first;
                std::size_t y = offset + i;
 
                double dx = x - mean_x;
                mean_x += dx /  (i + 1);
                mean_y += (y - mean_y) / (i + 1);
                c += dx * (y - mean_y);
 
                double dx2 = x - mean_x;
                m2 += dx * dx2;
            }
 
            double cov = c / (n - 1);
            double var = m2 / (n - 1);
 
            if (var == 0.f) return { 0.0, mean_y };
 
            double slope = cov / var * compression_factor;
            double intercept = mean_y * compression_factor - slope * mean_x;
            return { slope, intercept };
        }
    };
 
    protected:
    std::vector<LinearModel> models_; 
 
    public:
    RecursiveModelIndex() : base_type() { }
 
    IndexMethod method() const override { return IndexMethod::Rmi; }
 
    const memory::Memory & memory() const override { throw m::runtime_error("not yet implemented"); }
 
    /* Returns the size of the index in bytes. */
    std::size_t size_in_bytes() const override { throw m::runtime_error("not yet implemented"); }
 
    void finalize() override;
 
    const_iterator lower_bound(const key_type key) const override {
        if (not base_type::finalized()) throw m::exception("Index is not finalized.");
        return lower_bound_exponential_search(base_type::begin() + predict(key), key);
    }
 
    const_iterator upper_bound(const key_type key) const override {
        if (not base_type::finalized()) throw m::exception("Index is not finalized.");
        return upper_bound_exponential_search(base_type::begin() + predict(key), key);
    }
 
    void dump(std::ostream &out) const override { out << "RecursiveModelIndex<" << typeid(key_type).name() << '>' << std::endl; }
    void dump() const override { dump(std::cerr); }
 
    private:
    std::size_t predict(const key_type key) const {
        auto segment_id = std::clamp<double>(models_[0](key), 0, models_.size() - 2);
        auto pred = std::clamp<double>(models_[segment_id + 1](key), 0, base_type::num_entries());
        return static_cast<std::size_t>(pred);
    }
    const_iterator lower_bound_exponential_search(const_iterator pred, const key_type value) const {
        auto begin = base_type::begin();
        auto end = base_type::end();
        std::size_t bound = 1;
        if (base_type::cmp(*pred, value)) { // search right side
            auto prev = pred;
            auto curr = prev + bound;
            while (curr < end and base_type::cmp(*curr, value)) {
                bound *= 2;
                prev = curr;
                curr += bound;
            }
            return std::lower_bound(prev, std::min(curr + 1, end), value, base_type::cmp);
        } else { // search left side
            auto prev = pred;
            auto curr = prev - bound;
            while (curr > begin and not base_type::cmp(*curr, value)) {
                bound *= 2;
                prev = curr;
                curr -= bound;
            }
            return std::lower_bound(std::max(begin, curr), prev, value, base_type::cmp);
        }
    }
    const_iterator upper_bound_exponential_search(const_iterator pred, const key_type value) const {
        auto begin = base_type::begin();
        auto end = base_type::end();
        std::size_t bound = 1;
        if (not base_type::cmp(value, *pred)) { // search right side
            auto prev = pred;
            auto curr = prev + bound;
            while (curr < end and not base_type::cmp(value, *curr)) {
                bound *= 2;
                prev = curr;
                curr += bound;
            }
            return std::upper_bound(prev, std::min(curr + 1, end), value, base_type::cmp);
        } else { // search left side
            auto prev = pred;
            auto curr = prev - bound;
            while (curr > begin and base_type::cmp(value, *curr)) {
                bound *= 2;
                prev = curr;
                curr -= bound;
            }
            return std::upper_bound(std::max(begin, curr), prev, value, base_type::cmp);
        }
    }
};
 
#define M_INDEX_LIST_TEMPLATED(X) \
    X(m::idx::ArrayIndex<bool>) \
    X(m::idx::ArrayIndex<int8_t>) \
    X(m::idx::ArrayIndex<int16_t>) \
    X(m::idx::ArrayIndex<int32_t>) \
    X(m::idx::ArrayIndex<int64_t>) \
    X(m::idx::ArrayIndex<float>) \
    X(m::idx::ArrayIndex<double>) \
    X(m::idx::ArrayIndex<const char*>) \
    X(m::idx::RecursiveModelIndex<int8_t>) \
    X(m::idx::RecursiveModelIndex<int16_t>) \
    X(m::idx::RecursiveModelIndex<int32_t>) \
    X(m::idx::RecursiveModelIndex<int64_t>) \
    X(m::idx::RecursiveModelIndex<float>) \
    X(m::idx::RecursiveModelIndex<double>)
 
}
 
}
 
// explicit instantiation declarations
#define DECLARE(CLASS) \
    extern template struct CLASS;
M_INDEX_LIST_TEMPLATED(DECLARE)
#undef DECLARE