souffle::synthesiser::IndirectRelation Class Reference

#include <Relation.h>

Inheritance diagram for souffle::synthesiser::IndirectRelation:

Collaboration diagram for souffle::synthesiser::IndirectRelation:

Public Member Functions
void	computeIndices () override
	Generate index set for a indirect indexed relation. More...
void	generateTypeStruct (std::ostream &out) override
	Generate type struct of a indirect indexed relation. More...
std::string	getTypeName () override
	Generate type name of a indirect indexed relation. More...
	IndirectRelation (const ram::Relation &ramRel, const MinIndexSelection &indexSet, bool isProvenance)
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 134 of file Relation.h.

Constructor & Destructor Documentation

IndirectRelation()

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

inline

Definition at line 136 of file Relation.h.

            : Relation(ramRel, indexSet, isProvenance) {}

Member Function Documentation

computeIndices()

void souffle::synthesiser::IndirectRelation::computeIndices ( )

override

Generate index set for a indirect indexed relation.

Definition at line 513 of file Relation.cpp.

                                      {
    assert(!isProvenance && "indirect indexes cannot used for provenance");
 
    // 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");
 
    // check for full index
    for (size_t i = 0; i < inds.size(); i++) {
        auto& ind = inds[i];
        if (ind.size() == getArity()) {
            masterIndex = i;
            break;
        }
    }
    assert(masterIndex < inds.size() && "no full index in relation");
    computedIndices = inds;
}

References i.

generateTypeStruct()

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

override

Generate type struct of a indirect indexed relation.

Definition at line 559 of file Relation.cpp.

                                                         {
    size_t arity = getArity();
    const auto& inds = getIndices();
    auto types = relation.getAttributeTypes();
    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";
 
    // table and lock required for storing actual data for indirect indices
    out << "Table<t_tuple> dataTable;\n";
    out << "Lock insert_lock;\n";
 
    // btree types
    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>");
            }
        }
 
        std::string comparator = "t_comparator_" + std::to_string(i);
 
        out << "struct " << comparator << "{\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 < ind.size()) {
                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 < ind.size()) {
                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 < ind.size()) {
                out << "&&";
                geneq(i + 1);
            }
        };
        geneq(0);
        out << ";\n }\n";
        out << "};\n";
 
        if (ind.size() == arity) {
            out << "using t_ind_" << i << " = btree_set<const t_tuple*," << comparator << ">;\n";
        } else {
            out << "using t_ind_" << i << " = btree_multiset<const t_tuple*," << comparator << ">;\n";
        }
 
        out << "t_ind_" << i << " ind_" << i << ";\n";
    }
 
    // typedef deref iterators
    for (size_t i = 0; i < numIndexes; i++) {
        out << "using iterator_" << i << " = IterDerefWrapper<typename t_ind_" << i << "::iterator>;\n";
    }
    out << "using iterator = iterator_" << masterIndex << ";\n";
 
    // Create a struct storing the context hints for each index
    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";
 
    out << "bool insert(const t_tuple& t, context& h) {\n";
    out << "const t_tuple* masterCopy = nullptr;\n";
    out << "{\n";
    out << "auto lease = insert_lock.acquire();\n";
    out << "if (contains(t, h)) return false;\n";
    out << "masterCopy = &dataTable.insert(t);\n";
    out << "ind_" << masterIndex << ".insert(masterCopy, h.hints_" << masterIndex << "_lower);\n";
    out << "}\n";
    for (size_t i = 0; i < numIndexes; i++) {
        if (i != masterIndex) {
            out << "ind_" << i << ".insert(masterCopy, h.hints_" << i << "_lower"
                << ");\n";
        }
    }
    out << "return true;\n";
    out << "}\n";
 
    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_0(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_0(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<iterator_" << indNum << "> 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";
 
        // use the more efficient find() method if the search pattern is full
        if (eqSize == arity) {
            // if lower == upper we can just do a find
            out << "if (cmp == 0) {\n";
            out << "    auto pos = find(lower, h);\n";
            out << "    auto fin = end();\n";
            out << "    if (pos != fin) {fin = pos; ++fin;}\n";
            out << "    return make_range(pos, fin);\n";
            out << "}\n";
        }
        // if lower > upper then we have an empty range
        out << "if (cmp > 0) {\n";
        out << "    return range<iterator_" << indNum << ">(ind_" << indNum << ".end(), ind_" << indNum
            << ".end());\n";
        out << "}\n";
 
        // otherwise do the default method
        out << "return range<iterator_" << indNum << ">(ind_" << indNum << ".lower_bound(&lower, h.hints_"
            << indNum << "_lower"
            << "), ind_" << indNum << ".upper_bound(&upper, h.hints_" << indNum << "_upper"
            << "));\n";
 
        out << "}\n";
 
        out << "range<iterator_" << indNum << "> 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
    out << "std::vector<range<iterator>> partition() const {\n";
    out << "std::vector<range<iterator>> res;\n";
    out << "for (const auto& cur : ind_" << masterIndex << ".getChunks(400)) {\n";
    out << "    res.push_back(make_range(derefIter(cur.begin()), derefIter(cur.end())));\n";
    out << "}\n";
    out << "return res;\n";
    out << "}\n";
 
    // purge method
    out << "void purge() {\n";
    for (size_t i = 0; i < numIndexes; i++) {
        out << "ind_" << i << ".clear();\n";
    }
    out << "dataTable.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";
 
    // printStatistics method
    out << "void printStatistics(std::ostream& o) const {\n";
    for (size_t i = 0; i < numIndexes; i++) {
        out << "o << \" arity " << arity << " indirect b-tree index " << i << " lex-order " << inds[i]
            << "\\n\";\n";
        out << "ind_" << i << ".printStats(o);\n";
    }
    out << "}\n";
 
    // end struct
    out << "};\n";
}

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::IndirectRelation::getTypeName ( )

override

Generate type name of a indirect indexed relation.

Definition at line 535 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