souffle::synthesiser::DirectRelation Class Reference

#include <Relation.h>

Inheritance diagram for souffle::synthesiser::DirectRelation:

Collaboration diagram for souffle::synthesiser::DirectRelation:

Public Member Functions
void	computeIndices () override
	Generate index set for a direct indexed relation. More...
	DirectRelation (const ram::Relation &ramRel, const MinIndexSelection &indexSet, bool isProvenance)
void	generateTypeStruct (std::ostream &out) override
	Generate type struct of a direct indexed relation. More...
std::string	getTypeName () override
	Generate type name of a direct indexed relation. More...
Public Member Functions inherited from souffle::ram::Relation
Relation *	clone () const override
	Create a clone (i.e. More...
unsigned	getArity () const
	Get arity of relation. More...
const std::vector< std::string > &	getAttributeNames () const
	Get attribute names. More...
const std::vector< std::string > &	getAttributeTypes () const
	Get attribute types. More...
unsigned	getAuxiliaryArity () const
	Get number of auxiliary attributes. More...
const std::string &	getName () const
	Get name. More...
RelationRepresentation	getRepresentation () const
	Relation representation type. More...
bool	isNullary () const
	Is nullary relation. More...
bool	isTemp () const
	Is temporary relation (for semi-naive evaluation) More...
bool	operator< (const Relation &other) const
	Compare two relations via their name. More...
	Relation (std::string name, size_t arity, size_t auxiliaryArity, std::vector< std::string > attributeNames, std::vector< std::string > attributeTypes, RelationRepresentation representation)
Public Member Functions inherited from souffle::ram::Node
virtual void	apply (const NodeMapper &)
	Apply the mapper to all child nodes. More...
virtual std::vector< const Node * >	getChildNodes () const
	Obtain list of all embedded child nodes. More...
bool	operator!= (const Node &other) const
	Inequality check for two RAM nodes. More...
bool	operator== (const Node &other) const
	Equivalence check for two RAM nodes. More...
virtual void	rewrite (const Node *oldNode, Own< Node > newNode)
	Rewrite a child node. More...
virtual	~Node ()=default

Additional Inherited Members
Protected Member Functions inherited from souffle::ram::Relation
bool	equal (const Node &node) const override
	Equality check for two RAM nodes. More...
void	print (std::ostream &out) const override
	Print RAM node. More...
Protected Attributes inherited from souffle::ram::Relation
const size_t	arity
	Arity, i.e., number of attributes. More...
const std::vector< std::string >	attributeNames
	Name of attributes. More...
const std::vector< std::string >	attributeTypes
	Type of attributes. More...
const size_t	auxiliaryArity
	Number of auxiliary attributes (e.g. More...
const std::string	name
	Name of relation. More...
const RelationRepresentation	representation
	Data-structure representation. More...

Detailed Description

Definition at line 124 of file Relation.h.

Constructor & Destructor Documentation

DirectRelation()

souffle::synthesiser::DirectRelation::DirectRelation ( const ram::Relation &  ramRel, const MinIndexSelection &  indexSet, bool  isProvenance  )

inline

Definition at line 126 of file Relation.h.

            : Relation(ramRel, indexSet, isProvenance) {}

Member Function Documentation

computeIndices()

void souffle::synthesiser::DirectRelation::computeIndices ( )

override

Generate index set for a direct indexed relation.

Definition at line 117 of file Relation.cpp.

                                    {
    // Generate and set indices
    MinIndexSelection::OrderCollection inds = indices.getAllOrders();
 
    // generate a full index if no indices exist
    assert(!inds.empty() && "no full index in relation");
 
    size_t index_nr = 0;
    // expand all search orders to be full
    for (auto& ind : inds) {
        // use a set as a cache for fast lookup
        std::set<int> curIndexElems(ind.begin(), ind.end());
 
        // If this relation is used with provenance,
        // we must expand all search orders to be full indices,
        // since weak/strong comparators and updaters need this,
        // and also add provenance annotations to the indices
        if (isProvenance) {
            // expand index to be full
            for (size_t i = 0; i < getArity() - relation.getAuxiliaryArity(); i++) {
                if (curIndexElems.find(i) == curIndexElems.end()) {
                    ind.push_back(i);
                }
            }
            // remove any provenance annotations already in the index order
            if (curIndexElems.find(getArity() - relation.getAuxiliaryArity() + 1) != curIndexElems.end()) {
                ind.erase(std::find(ind.begin(), ind.end(), getArity() - relation.getAuxiliaryArity() + 1));
            }
 
            if (curIndexElems.find(getArity() - relation.getAuxiliaryArity()) != curIndexElems.end()) {
                ind.erase(std::find(ind.begin(), ind.end(), getArity() - relation.getAuxiliaryArity()));
            }
 
            // add provenance annotations to the index, but in reverse order
            ind.push_back(getArity() - relation.getAuxiliaryArity() + 1);
            ind.push_back(getArity() - relation.getAuxiliaryArity());
            masterIndex = 0;
        } else if (ind.size() == getArity()) {
            masterIndex = index_nr;
        }
        index_nr++;
    }
    assert(masterIndex < inds.size() && "no full index in relation");
    computedIndices = inds;
}

References i, and relation.

generateTypeStruct()

void souffle::synthesiser::DirectRelation::generateTypeStruct ( std::ostream &  out )

override

Generate type struct of a direct indexed relation.

Definition at line 188 of file Relation.cpp.

                                                       {
    size_t arity = getArity();
    size_t auxiliaryArity = relation.getAuxiliaryArity();
    auto types = relation.getAttributeTypes();
    const auto& inds = getIndices();
    size_t numIndexes = inds.size();
    std::map<MinIndexSelection::LexOrder, int> indexToNumMap;
 
    // struct definition
    out << "struct " << getTypeName() << " {\n";
    out << "static constexpr Relation::arity_type Arity = " << arity << ";\n";
 
    // stored tuple type
    out << "using t_tuple = Tuple<RamDomain, " << arity << ">;\n";
 
    // generate an updater class for provenance
    if (isProvenance) {
        out << "struct updater_" << getTypeName() << " {\n";
        out << "void update(t_tuple& old_t, const t_tuple& new_t) {\n";
 
        for (size_t i = arity - auxiliaryArity; i < arity; i++) {
            out << "old_t[" << i << "] = new_t[" << i << "];\n";
        }
 
        out << "}\n";
        out << "};\n";
    }
 
    // generate the btree type for each relation
    for (size_t i = 0; i < inds.size(); i++) {
        auto& ind = inds[i];
 
        if (i < getMinIndexSelection().getAllOrders().size()) {
            indexToNumMap[getMinIndexSelection().getAllOrders()[i]] = i;
        }
 
        std::vector<std::string> typecasts;
        typecasts.reserve(types.size());
 
        for (auto type : types) {
            switch (type[0]) {
                case 'f': typecasts.push_back("ramBitCast<RamFloat>"); break;
                case 'u': typecasts.push_back("ramBitCast<RamUnsigned>"); break;
                default: typecasts.push_back("ramBitCast<RamSigned>");
            }
        }
 
        auto genstruct = [&](std::string name, size_t bound) {
            out << "struct " << name << "{\n";
            out << " int operator()(const t_tuple& a, const t_tuple& b) const {\n";
            out << "  return ";
            std::function<void(size_t)> gencmp = [&](size_t i) {
                size_t attrib = ind[i];
                const auto& typecast = typecasts[attrib];
 
                out << "(" << typecast << "(a[" << attrib << "]) < " << typecast << "(b[" << attrib
                    << "])) ? -1 : (" << typecast << "(a[" << attrib << "]) > " << typecast << "(b[" << attrib
                    << "])) ? 1 :(";
                if (i + 1 < bound) {
                    gencmp(i + 1);
                } else {
                    out << "0";
                }
                out << ")";
            };
            gencmp(0);
            out << ";\n }\n";
            out << "bool less(const t_tuple& a, const t_tuple& b) const {\n";
            out << "  return ";
            std::function<void(size_t)> genless = [&](size_t i) {
                size_t attrib = ind[i];
                const auto& typecast = typecasts[attrib];
 
                out << "(" << typecast << "(a[" << attrib << "]) < " << typecast << "(b[" << attrib << "]))";
                if (i + 1 < bound) {
                    out << "|| (" << typecast << "(a[" << attrib << "]) == " << typecast << "(b[" << attrib
                        << "])) && (";
                    genless(i + 1);
                    out << ")";
                }
            };
            genless(0);
            out << ";\n }\n";
            out << "bool equal(const t_tuple& a, const t_tuple& b) const {\n";
            out << "return ";
            std::function<void(size_t)> geneq = [&](size_t i) {
                size_t attrib = ind[i];
                const auto& typecast = typecasts[attrib];
 
                out << "(" << typecast << "(a[" << attrib << "]) == " << typecast << "(b[" << attrib << "]))";
                if (i + 1 < bound) {
                    out << "&&";
                    geneq(i + 1);
                }
            };
            geneq(0);
            out << ";\n }\n";
            out << "};\n";
        };
 
        std::string comparator = "t_comparator_" + std::to_string(i);
        genstruct(comparator, ind.size());
 
        // for provenance, all indices must be full so we use btree_set
        // also strong/weak comparators and updater methods
 
        if (isProvenance) {
            std::string comparator_aux;
            if (provenanceIndexNumbers.find(i) == provenanceIndexNumbers.end()) {
                // index for bottom up phase
                comparator_aux = "t_comparator_" + std::to_string(i) + "_aux";
                genstruct(comparator_aux, ind.size() - auxiliaryArity);
            } else {
                // index for top down phase
                comparator_aux = comparator;
            }
            out << "using t_ind_" << i << " = btree_set<t_tuple," << comparator
                << ",std::allocator<t_tuple>,256,typename "
                   "souffle::detail::default_strategy<t_tuple>::type,"
                << comparator_aux << ",updater_" << getTypeName() << ">;\n";
        } else {
            if (ind.size() == arity) {
                out << "using t_ind_" << i << " = btree_set<t_tuple," << comparator << ">;\n";
            } else {
                // without provenance, some indices may be not full, so we use btree_multiset for those
                out << "using t_ind_" << i << " = btree_multiset<t_tuple," << comparator << ">;\n";
            }
        }
        out << "t_ind_" << i << " ind_" << i << ";\n";
    }
 
    // typedef master index iterator to be struct iterator
    out << "using iterator = t_ind_" << masterIndex << "::iterator;\n";
 
    // create a struct storing hints for each btree
    out << "struct context {\n";
    for (size_t i = 0; i < numIndexes; i++) {
        out << "t_ind_" << i << "::operation_hints hints_" << i << "_lower"
            << ";\n";
        out << "t_ind_" << i << "::operation_hints hints_" << i << "_upper"
            << ";\n";
    }
    out << "};\n";
    out << "context createContext() { return context(); }\n";
 
    // insert methods
    out << "bool insert(const t_tuple& t) {\n";
    out << "context h;\n";
    out << "return insert(t, h);\n";
    out << "}\n";  // end of insert(t_tuple&)
 
    out << "bool insert(const t_tuple& t, context& h) {\n";
    out << "if (ind_" << masterIndex << ".insert(t, h.hints_" << masterIndex << "_lower"
        << ")) {\n";
    for (size_t i = 0; i < numIndexes; i++) {
        if (i != masterIndex && provenanceIndexNumbers.find(i) == provenanceIndexNumbers.end()) {
            out << "ind_" << i << ".insert(t, h.hints_" << i << "_lower"
                << ");\n";
        }
    }
    out << "return true;\n";
    out << "} else return false;\n";
    out << "}\n";  // end of insert(t_tuple&, context&)
 
    out << "bool insert(const RamDomain* ramDomain) {\n";
    out << "RamDomain data[" << arity << "];\n";
    out << "std::copy(ramDomain, ramDomain + " << arity << ", data);\n";
    out << "const t_tuple& tuple = reinterpret_cast<const t_tuple&>(data);\n";
    out << "context h;\n";
    out << "return insert(tuple, h);\n";
    out << "}\n";  // end of insert(RamDomain*)
 
    std::vector<std::string> decls;
    std::vector<std::string> params;
    for (size_t i = 0; i < arity; i++) {
        decls.push_back("RamDomain a" + std::to_string(i));
        params.push_back("a" + std::to_string(i));
    }
    out << "bool insert(" << join(decls, ",") << ") {\n";
    out << "RamDomain data[" << arity << "] = {" << join(params, ",") << "};\n";
    out << "return insert(data);\n";
    out << "}\n";  // end of insert(RamDomain x1, RamDomain x2, ...)
 
    // contains methods
    out << "bool contains(const t_tuple& t, context& h) const {\n";
    out << "return ind_" << masterIndex << ".contains(t, h.hints_" << masterIndex << "_lower"
        << ");\n";
    out << "}\n";
 
    out << "bool contains(const t_tuple& t) const {\n";
    out << "context h;\n";
    out << "return contains(t, h);\n";
    out << "}\n";
 
    // size method
    out << "std::size_t size() const {\n";
    out << "return ind_" << masterIndex << ".size();\n";
    out << "}\n";
 
    // find methods
    out << "iterator find(const t_tuple& t, context& h) const {\n";
    out << "return ind_" << masterIndex << ".find(t, h.hints_" << masterIndex << "_lower"
        << ");\n";
    out << "}\n";
 
    out << "iterator find(const t_tuple& t) const {\n";
    out << "context h;\n";
    out << "return find(t, h);\n";
    out << "}\n";
 
    // empty lowerUpperRange method
    out << "range<iterator> lowerUpperRange_" << SearchSignature(arity)
        << "(const t_tuple& /* lower */, const t_tuple& /* upper */, context& /* h */) const "
           "{\n";
 
    out << "return range<iterator>(ind_" << masterIndex << ".begin(),ind_" << masterIndex << ".end());\n";
    out << "}\n";
 
    out << "range<iterator> lowerUpperRange_" << SearchSignature(arity)
        << "(const t_tuple& /* lower */, const t_tuple& /* upper */) const {\n";
 
    out << "return range<iterator>(ind_" << masterIndex << ".begin(),ind_" << masterIndex << ".end());\n";
    out << "}\n";
 
    // lowerUpperRange methods for each pattern which is used to search this relation
    for (auto search : getMinIndexSelection().getSearches()) {
        auto& lexOrder = getMinIndexSelection().getLexOrder(search);
        size_t indNum = indexToNumMap[lexOrder];
 
        out << "range<t_ind_" << indNum << "::iterator> lowerUpperRange_" << search;
        out << "(const t_tuple& lower, const t_tuple& upper, context& h) const {\n";
 
        // count size of search pattern
        size_t eqSize = 0;
        for (size_t column = 0; column < arity; column++) {
            if (search[column] == analysis::AttributeConstraint::Equal) {
                eqSize++;
            }
        }
 
        out << "t_comparator_" << indNum << " comparator;\n";
        out << "int cmp = comparator(lower, upper);\n";
 
        // if search signature is full we can apply this specialization
        if (eqSize == arity) {
            // use the more efficient find() method if lower == upper
            out << "if (cmp == 0) {\n";
            out << "    auto pos = ind_" << indNum << ".find(lower, h.hints_" << indNum << "_lower);\n";
            out << "    auto fin = ind_" << indNum << ".end();\n";
            out << "    if (pos != fin) {fin = pos; ++fin;}\n";
            out << "    return make_range(pos, fin);\n";
            out << "}\n";
        }
        // if lower_bound > upper_bound then we return an empty range
        out << "if (cmp > 0) {\n";
        out << "    return make_range(ind_" << indNum << ".end(), ind_" << indNum << ".end());\n";
        out << "}\n";
        // otherwise use the general method
        out << "return make_range(ind_" << indNum << ".lower_bound(lower, h.hints_" << indNum << "_lower"
            << "), ind_" << indNum << ".upper_bound(upper, h.hints_" << indNum << "_upper"
            << "));\n";
 
        out << "}\n";
 
        out << "range<t_ind_" << indNum << "::iterator> lowerUpperRange_" << search;
        out << "(const t_tuple& lower, const t_tuple& upper) const {\n";
 
        out << "context h;\n";
        out << "return lowerUpperRange_" << search << "(lower,upper,h);\n";
        out << "}\n";
    }
 
    // empty method
    out << "bool empty() const {\n";
    out << "return ind_" << masterIndex << ".empty();\n";
    out << "}\n";
 
    // partition method for parallelism
    out << "std::vector<range<iterator>> partition() const {\n";
    out << "return ind_" << masterIndex << ".getChunks(400);\n";
    out << "}\n";
 
    // purge method
    out << "void purge() {\n";
    for (size_t i = 0; i < numIndexes; i++) {
        out << "ind_" << i << ".clear();\n";
    }
    out << "}\n";
 
    // begin and end iterators
    out << "iterator begin() const {\n";
    out << "return ind_" << masterIndex << ".begin();\n";
    out << "}\n";
 
    out << "iterator end() const {\n";
    out << "return ind_" << masterIndex << ".end();\n";
    out << "}\n";
 
    // copyIndex method
    if (!provenanceIndexNumbers.empty()) {
        out << "void copyIndex() {\n";
        out << "for (auto const &cur : ind_" << masterIndex << ") {\n";
        for (auto const i : provenanceIndexNumbers) {
            out << "ind_" << i << ".insert(cur);\n";
        }
        out << "}\n";
        out << "}\n";
    }
 
    // printStatistics method
    out << "void printStatistics(std::ostream& o) const {\n";
    for (size_t i = 0; i < numIndexes; i++) {
        out << "o << \" arity " << arity << " direct b-tree index " << i << " lex-order " << inds[i]
            << "\\n\";\n";
        out << "ind_" << i << ".printStats(o);\n";
    }
    out << "}\n";
 
    // end struct
    out << "};\n";
}  // namespace souffle

References i, souffle::join(), relation, TCB_SPAN_NAMESPACE_NAME::detail::size(), and types.

Here is the call graph for this function:

getTypeName()

std::string souffle::synthesiser::DirectRelation::getTypeName ( )

override

Generate type name of a direct indexed relation.

Definition at line 164 of file Relation.cpp.

                                      {
    // collect all attributes used in the lex-order
    std::unordered_set<uint32_t> attributesUsed;
    for (auto& ind : getIndices()) {
        for (auto& attr : ind) {
            attributesUsed.insert(attr);
        }
    }
 
    std::stringstream res;
    res << "t_btree_" << getTypeAttributeString(relation.getAttributeTypes(), attributesUsed);
 
    for (auto& ind : getIndices()) {
        res << "__" << join(ind, "_");
    }
 
    for (auto& search : getMinIndexSelection().getSearches()) {
        res << "__" << search;
    }
 
    return res.str();
}

References souffle::join(), and relation.

Here is the call graph for this function:

---

The documentation for this class was generated from the following files:

• synthesiser/Relation.h
• synthesiser/Relation.cpp