CardinalityEstimator.hpp

Go to the documentation of this file.

#pragma once
 
#include <fstream>
#include <iostream>
#include <mutable/mutable-config.hpp>
#include <mutable/util/ADT.hpp>
#include <mutable/util/crtp.hpp>
#include <mutable/util/Pool.hpp>
#include <sstream>
#include <unordered_map>
#include <vector>
 
 
namespace m {
 
namespace ast {
 
struct Expr;
 
}
 
namespace cnf { struct CNF; }
struct Diagnostic;
struct GroupingOperator;
struct LimitOperator;
struct Operator;
struct PlanTableLargeAndSparse;
struct PlanTableSmallOrDense;
struct QueryGraph;
struct SpnWrapper;
 
using Subproblem = SmallBitset;
 
 
struct M_EXPORT DataModel
{
    virtual ~DataModel() = 0;
 
    virtual void assign_to(Subproblem s) = 0;
};
 
 
struct M_EXPORT estimate_join_all_tag : const_virtual_crtp_helper<estimate_join_all_tag>::
    returns<std::unique_ptr<DataModel>>::
    crtp_args<const PlanTableSmallOrDense&, const PlanTableLargeAndSparse&>::
    args<const QueryGraph&, Subproblem, const cnf::CNF&> { };
 
struct M_EXPORT CardinalityEstimator : estimate_join_all_tag::base_type
{
    using estimate_join_all_tag::base_type::operator();
    using group_type = std::pair<std::reference_wrapper<const ast::Expr>, ThreadSafePooledOptionalString>;
 
    struct data_model_exception : m::exception
    {
        explicit data_model_exception(std::string message) : m::exception(std::move(message)) { }
    };
 
    virtual ~CardinalityEstimator() = 0;
 
 
    /*==================================================================================================================
     * Model calculation
     *================================================================================================================*/
 
    virtual std::unique_ptr<DataModel> empty_model() const = 0;
 
    virtual std::unique_ptr<DataModel> estimate_scan(const QueryGraph &G, Subproblem P) const = 0;
 
    virtual std::unique_ptr<DataModel> estimate_filter(const QueryGraph &G, const DataModel &data,
                                                       const cnf::CNF &filter) const = 0;
 
    virtual std::unique_ptr<DataModel>
    estimate_limit(const QueryGraph &G, const DataModel &data, const std::size_t limit,
                   const std::size_t offset) const = 0;
 
    virtual std::unique_ptr<DataModel>
    estimate_grouping(const QueryGraph &G, const DataModel &data, const std::vector<group_type> &groups) const = 0;
 
    virtual std::unique_ptr<DataModel>
    estimate_join(const QueryGraph &G, const DataModel &left, const DataModel &right,
                  const cnf::CNF &condition) const = 0;
 
    template<typename PlanTable>
    std::unique_ptr<DataModel>
    estimate_join_all(const QueryGraph &G, const PlanTable &PT, Subproblem to_join, const cnf::CNF &condition) const
    {
        return operator()(estimate_join_all_tag{}, PT, G, to_join, condition);
    }
 
 
    /*==================================================================================================================
     * Prediction via model use
     *================================================================================================================*/
 
    virtual std::size_t predict_cardinality(const DataModel &data) const = 0;
 
    virtual double predict_number_distinct_values(const DataModel &data) const;
 
    /*==================================================================================================================
     * other methods
     *================================================================================================================*/
 
M_LCOV_EXCL_START
    friend std::ostream & operator<<(std::ostream &out, const CardinalityEstimator &CE) {
        CE.print(out);
        return out;
    }
M_LCOV_EXCL_STOP
 
    void dump(std::ostream &out) const;
 
    void dump() const;
 
    protected:
    virtual void print(std::ostream &out) const = 0;
};
 
namespace {
 
template<typename Actual>
struct CardinalityEstimatorCRTP : CardinalityEstimator
                                , estimate_join_all_tag::derived_type<Actual>
{ };
 
}
 
struct M_EXPORT CartesianProductEstimator : CardinalityEstimatorCRTP<CartesianProductEstimator>
{
    struct CartesianProductDataModel : DataModel
    {
        std::size_t size;
 
        CartesianProductDataModel() = default;
        CartesianProductDataModel(std::size_t size) : size(size) { }
 
        void assign_to(Subproblem) override { /* nothing to be done */ }
    };
 
    CartesianProductEstimator() { }
    CartesianProductEstimator(ThreadSafePooledString) { }
 
 
    /*==================================================================================================================
     * Model calculation
     *================================================================================================================*/
 
    std::unique_ptr<DataModel> empty_model() const override;
    std::unique_ptr<DataModel> estimate_scan(const QueryGraph &G, Subproblem P) const override;
    std::unique_ptr<DataModel>
    estimate_filter(const QueryGraph &G, const DataModel &data, const cnf::CNF &filter) const override;
    std::unique_ptr<DataModel>
    estimate_limit(const QueryGraph &G, const DataModel &data, std::size_t limit, std::size_t offset) const override;
    std::unique_ptr<DataModel>
    estimate_grouping(const QueryGraph &G, const DataModel &data, const std::vector<group_type> &groups) const override;
    std::unique_ptr<DataModel>
    estimate_join(const QueryGraph &G, const DataModel &left, const DataModel &right,
                  const cnf::CNF &condition) const override;
 
    template<typename PlanTable>
    std::unique_ptr<DataModel>
    operator()(estimate_join_all_tag, PlanTable &&PT, const QueryGraph &G, Subproblem to_join,
               const cnf::CNF &condition) const;
 
 
    /*==================================================================================================================
     * Prediction via model use
     *================================================================================================================*/
 
    std::size_t predict_cardinality(const DataModel &data) const override;
 
    private:
    void print(std::ostream &out) const override;
};
 
struct M_EXPORT InjectionCardinalityEstimator : CardinalityEstimatorCRTP<InjectionCardinalityEstimator>
{
    using Subproblem = SmallBitset;
 
    struct InjectionCardinalityDataModel : DataModel
    {
        friend struct InjectionCardinalityEstimator;
 
        private:
        Subproblem subproblem_;
        std::size_t size_;
 
        public:
        InjectionCardinalityDataModel(Subproblem S, std::size_t size) : subproblem_(S), size_(size) { }
        InjectionCardinalityDataModel(const InjectionCardinalityDataModel&) = default;
        InjectionCardinalityDataModel(InjectionCardinalityDataModel&&) = default;
        InjectionCardinalityDataModel & operator=(InjectionCardinalityDataModel &&other) = default;
        InjectionCardinalityDataModel & operator=(const InjectionCardinalityDataModel &other) = default;
 
        void assign_to(Subproblem s) override { subproblem_ = s; }
    };
 
    private:
    mutable std::vector<char> buf_;
    mutable std::ostringstream oss_;
 
    std::unordered_map<ThreadSafePooledString, std::size_t> cardinality_table_;
    CartesianProductEstimator fallback_;
 
    public:
    InjectionCardinalityEstimator(ThreadSafePooledString name_of_database);
 
    InjectionCardinalityEstimator(Diagnostic &diag, ThreadSafePooledString name_of_database, std::istream &in);
 
    ~InjectionCardinalityEstimator() = default;
 
    InjectionCardinalityEstimator(const InjectionCardinalityEstimator&) = delete;
    InjectionCardinalityEstimator(InjectionCardinalityEstimator&&) = default;
 
    InjectionCardinalityEstimator & operator=(InjectionCardinalityEstimator&&) = default;
 
 
    /*==================================================================================================================
     * Model calculation
     *================================================================================================================*/
 
    std::unique_ptr<DataModel> empty_model() const override;
    std::unique_ptr<DataModel> estimate_scan(const QueryGraph &G, Subproblem P) const override;
    std::unique_ptr<DataModel>
    estimate_filter(const QueryGraph &G, const DataModel &data, const cnf::CNF &filter) const override;
    std::unique_ptr<DataModel>
    estimate_limit(const QueryGraph &G, const DataModel &data, std::size_t limit, std::size_t offset) const override;
    std::unique_ptr<DataModel>
    estimate_grouping(const QueryGraph &G, const DataModel &data, const std::vector<group_type> &groups) const override;
    std::unique_ptr<DataModel>
    estimate_join(const QueryGraph &G, const DataModel &left, const DataModel &right,
                  const cnf::CNF &condition) const override;
 
    template<typename PlanTable>
    std::unique_ptr<DataModel>
    operator()(estimate_join_all_tag, PlanTable &&PT, const QueryGraph &G, Subproblem to_join,
               const cnf::CNF &condition) const;
 
    /*==================================================================================================================
     * Prediction via model use
     *================================================================================================================*/
 
    std::size_t predict_cardinality(const DataModel &data) const override;
 
    private:
    void read_json(Diagnostic &diag, std::istream &in, const ThreadSafePooledString &name_of_database);
    void print(std::ostream &out) const override;
    void buf_append(const char *s) const { while (*s) buf_.emplace_back(*s++); }
    void buf_append(const std::string &s) const {
        buf_.reserve(buf_.size() + s.size());
        buf_append(s.c_str());
    }
    const char * buf_view() const { return buf_.data(); }
    ThreadSafePooledString make_identifier(const QueryGraph &G, const Subproblem S) const;
};
 
struct M_EXPORT SpnEstimator : CardinalityEstimatorCRTP<SpnEstimator>
{
    using SpnIdentifier = std::pair<ThreadSafePooledString, ThreadSafePooledString>;
    using SpnJoin = std::pair<SpnIdentifier, SpnIdentifier>;
    using table_spn_map = std::unordered_map<ThreadSafePooledString, std::reference_wrapper<const SpnWrapper>>;
 
    struct SpnDataModel : DataModel
    {
        friend struct SpnEstimator;
 
        private:
        table_spn_map spns_; 
        std::vector<std::size_t> max_frequencies_; 
        std::size_t num_rows_;
 
        public:
        SpnDataModel() = default;
        SpnDataModel(table_spn_map spns, std::size_t num_rows)
            : spns_(std::move(spns))
            , num_rows_(num_rows)
        { }
 
        void assign_to(Subproblem) override { /* nothing to be done */ }
    };
 
    private:
    std::unordered_map<ThreadSafePooledString, SpnWrapper*> table_to_spn_;
    ThreadSafePooledString name_of_database_;
 
    public:
    explicit SpnEstimator(ThreadSafePooledString name_of_database) : name_of_database_(std::move(name_of_database)) { }
 
    ~SpnEstimator();
 
    void learn_spns();
 
    void learn_new_spn(const ThreadSafePooledString &name_of_table);
 
    private:
    static std::pair<unsigned, bool> find_spn_id(const SpnDataModel &data, SpnJoin &join);
 
    static std::size_t max_frequency(const SpnDataModel &data, SpnJoin &join);
 
    static std::size_t max_frequency(const SpnDataModel &data, const ThreadSafePooledString &attribute);
 
    /*==================================================================================================================
     * Model calculation
     *================================================================================================================*/
 
    public:
    std::unique_ptr<DataModel> empty_model() const override;
    std::unique_ptr<DataModel> estimate_scan(const QueryGraph &G, Subproblem P) const override;
    std::unique_ptr<DataModel>
    estimate_filter(const QueryGraph &G, const DataModel &data, const cnf::CNF &filter) const override;
    std::unique_ptr<DataModel>
    estimate_limit(const QueryGraph &G, const DataModel &data, std::size_t limit, std::size_t offset) const override;
    std::unique_ptr<DataModel>
    estimate_grouping(const QueryGraph &G, const DataModel &data, const std::vector<group_type> &groups) const override;
    std::unique_ptr<DataModel>
    estimate_join(const QueryGraph &G, const DataModel &left, const DataModel &right,
                  const cnf::CNF &condition) const override;
 
    template<typename PlanTable>
    std::unique_ptr<DataModel>
    operator()(estimate_join_all_tag, PlanTable &&PT, const QueryGraph &G, Subproblem to_join,
               const cnf::CNF &condition) const;
 
 
    /*==================================================================================================================
     * Prediction via model use
     *================================================================================================================*/
 
    std::size_t predict_cardinality(const DataModel &data) const override;
 
    private:
    void print(std::ostream &out) const override;
};
 
}