souffle::ram::analysis::IndexAnalysis Class Reference

#include <Index.h>

Inheritance diagram for souffle::ram::analysis::IndexAnalysis:

Collaboration diagram for souffle::ram::analysis::IndexAnalysis:

Public Member Functions
MinIndexSelection &	getIndexes (const std::string &relName)
	@Brief get the minimal index cover for a relation More...
SearchSignature	getSearchSignature (const ExistenceCheck *existCheck) const
	@Brief Get the index signature for an existence check More...
SearchSignature	getSearchSignature (const IndexOperation *search) const
	@Brief Get index signature for an Ram IndexOperation operation More...
SearchSignature	getSearchSignature (const ProvenanceExistenceCheck *existCheck) const
	@Brief Get the index signature for a provenance existence check More...
SearchSignature	getSearchSignature (const Relation *ramRel) const
	@Brief Get the default index signature for a relation (the total-order index) More...
	IndexAnalysis (const char *id)
bool	isTotalSignature (const AbstractExistenceCheck *existCheck) const
	@Brief index signature of existence check resembles a total index More...
void	print (std::ostream &os) const override
	Print the analysis result in HTML format. More...
void	run (const TranslationUnit &translationUnit) override
	Run analysis for a RAM translation unit. More...
Public Member Functions inherited from souffle::ram::analysis::Analysis
	Analysis (const char *id)
virtual const std::string &	getName () const
	get name of the analysis More...
virtual	~Analysis ()=default

Static Public Attributes
static constexpr const char *	name = "index-analysis"

Private Attributes
std::map< std::string, MinIndexSelection >	minIndexCover
	minimal index cover for relations, i.e., maps a relation to a set of indexes More...
RelationAnalysis *	relAnalysis
	relation analysis for looking up relations by name More...

Additional Inherited Members
Protected Attributes inherited from souffle::ram::analysis::Analysis
std::string	identifier
	name of analysis instance More...

Detailed Description

Definition at line 413 of file Index.h.

Constructor & Destructor Documentation

IndexAnalysis()

souffle::ram::analysis::IndexAnalysis::IndexAnalysis ( const char *  id )

inline

Definition at line 415 of file Index.h.

: Analysis(id), relAnalysis(nullptr) {}

Member Function Documentation

getIndexes()

MinIndexSelection & souffle::ram::analysis::IndexAnalysis::getIndexes

(

const std::string &

relName

)

@Brief get the minimal index cover for a relation

Parameters

relation

name

Returns

set of indexes of the minimal index cover

Definition at line 549 of file Index.cpp.

                                              {
    for (auto& cur : minIndexCover) {
        const std::string& relName = cur.first;
        const MinIndexSelection& indexes = cur.second;
 

Referenced by run().

getSearchSignature() [1/4]

SearchSignature souffle::ram::analysis::IndexAnalysis::getSearchSignature

(

const ExistenceCheck *

existCheck

)

const

@Brief Get the index signature for an existence check

Parameters

Existence

check

Returns

index signature of existence check

Definition at line 655 of file Index.cpp.

                                                                                   {

getSearchSignature() [2/4]

SearchSignature souffle::ram::analysis::IndexAnalysis::getSearchSignature

(

const IndexOperation *

search

)

const

@Brief Get index signature for an Ram IndexOperation operation

Parameters

Index-relation-search

operation

Returns

Index signature of operation

Definition at line 612 of file Index.cpp.

                                       {
        // if both bounds are undefined
        if (isUndefValue(lower[i]) && isUndefValue(upper[i])) {
            keys[i] = AttributeConstraint::None;
            // if bounds are equal we have an equality
        } else if (*lower[i] == *upper[i]) {
            keys[i] = AttributeConstraint::Equal;
        } else {
            keys[i] = AttributeConstraint::Inequal;
        }
    }
    return keys;
}
 
SearchSignature IndexAnalysis::getSearchSignature(const ProvenanceExistenceCheck* provExistCheck) const {
    const auto values = provExistCheck->getValues();
    const Relation* rel = &relAnalysis->lookup(provExistCheck->getRelation());
    auto auxiliaryArity = rel->getAuxiliaryArity();
 

Referenced by run().

getSearchSignature() [3/4]

SearchSignature souffle::ram::analysis::IndexAnalysis::getSearchSignature

(

const ProvenanceExistenceCheck *

existCheck

)

const

@Brief Get the index signature for a provenance existence check

Parameters

Provenance-existence

check

Returns

index signature of provenance-existence check

Definition at line 633 of file Index.cpp.

                                                                {
        if (!isUndefValue(values[i])) {
            keys[i] = AttributeConstraint::Equal;
        }
    }
 
    // all auxiliary attributes should be free
    for (size_t i = values.size() - auxiliaryArity; i < values.size(); i++) {
        keys[i] = AttributeConstraint::None;
    }
 
    return keys;
}
 
SearchSignature IndexAnalysis::getSearchSignature(const ExistenceCheck* existCheck) const {
    const Relation* rel = &relAnalysis->lookup(existCheck->getRelation());
    return searchSignature(rel->getArity(), existCheck->getValues());
}
 

References souffle::ram::analysis::Equal, i, and souffle::ram::isUndefValue().

Here is the call graph for this function:

getSearchSignature() [4/4]

SearchSignature souffle::ram::analysis::IndexAnalysis::getSearchSignature

(

const Relation *

ramRel

)

const

@Brief Get the default index signature for a relation (the total-order index)

Parameters

ramRel

RAM-relation

Returns

total full-signature of the relation

Definition at line 660 of file Index.cpp.

                               {
            return false;
        }

isTotalSignature()

bool souffle::ram::analysis::IndexAnalysis::isTotalSignature

(

const AbstractExistenceCheck *

existCheck

)

const

@Brief index signature of existence check resembles a total index

Parameters

(provenance)

existence check

isTotalSignature returns true if all elements of a tuple are used for the the existence check.

Definition at line 664 of file Index.cpp.

print()

void souffle::ram::analysis::IndexAnalysis::print ( std::ostream &  ) const

overridevirtual

Print the analysis result in HTML format.

Reimplemented from souffle::ram::analysis::Analysis.

Definition at line 560 of file Index.cpp.

                                   : " << indexes.getSearches().size() << "\n";
 
        /* print searches */
        for (auto& search : indexes.getSearches()) {
            os << "\t\t";
            os << search;
            os << "\n";
        }
 
        /* print chains */
        for (auto& chain : indexes.getAllChains()) {
            os << join(chain, "-->") << "\n";
        }
        os << "\n";
 
        os << "\tNumber of Indexes: " << indexes.getAllOrders().size() << "\n";
        for (auto& order : indexes.getAllOrders()) {
            os << "\t\t";
            os << join(order, "<") << "\n";
            os << "\n";
        }
    }
}
 
namespace {
// handles equality constraints
template <typename Iter>
SearchSignature searchSignature(size_t arity, Iter const& bgn, Iter const& end) {
    SearchSignature keys(arity);

run()

void souffle::ram::analysis::IndexAnalysis::run ( const TranslationUnit &  translationUnit )

overridevirtual

Run analysis for a RAM translation unit.

Implements souffle::ram::analysis::Analysis.

Definition at line 480 of file Index.cpp.

                                                                        {
        if (const auto* indexSearch = dynamic_cast<const IndexOperation*>(&node)) {
            MinIndexSelection& indexes = getIndexes(indexSearch->getRelation());
            indexes.addSearch(getSearchSignature(indexSearch));
        } else if (const auto* exists = dynamic_cast<const ExistenceCheck*>(&node)) {
            MinIndexSelection& indexes = getIndexes(exists->getRelation());
            indexes.addSearch(getSearchSignature(exists));
        } else if (const auto* provExists = dynamic_cast<const ProvenanceExistenceCheck*>(&node)) {
            MinIndexSelection& indexes = getIndexes(provExists->getRelation());
            indexes.addSearch(getSearchSignature(provExists));
        } else if (const auto* ramRel = dynamic_cast<const Relation*>(&node)) {
            MinIndexSelection& indexes = getIndexes(ramRel->getName());
            indexes.addSearch(getSearchSignature(ramRel));
        }
    });
 
    // A swap happen between rel A and rel B indicates A should include all indices of B, vice versa.
    visitDepthFirst(translationUnit.getProgram(), [&](const Swap& swap) {
        // Note: this naive approach will not work if there exists chain or cyclic swapping.
        // e.g.  swap(relA, relB) swap(relB, relC) swap(relC, relA)
        // One need to keep merging the search set until a fixed point where no more index is introduced
        // in any of the relation in a complete iteration.
        //
        // Currently RAM does not have such situation.
        const std::string& relA = swap.getFirstRelation();
        const std::string& relB = swap.getSecondRelation();
        MinIndexSelection& indexesA = getIndexes(relA);
        MinIndexSelection& indexesB = getIndexes(relB);
        // Add all searchSignature of A into B
        for (const auto& signature : indexesA.getSearches()) {
            indexesB.addSearch(signature);
        }
 
        // Add all searchSignature of B into A
        for (const auto& signature : indexesB.getSearches()) {
            indexesA.addSearch(signature);
        }
    });
 
    // find optimal indexes for relations
    for (auto& cur : minIndexCover) {
        MinIndexSelection& indexes = cur.second;
        indexes.solve();
    }
 
    // Only case where indexSet is still empty is when relation has arity == 0
    for (auto& cur : minIndexCover) {
        MinIndexSelection& indexes = cur.second;
        if (indexes.getAllOrders().empty()) {
            indexes.insertDefaultTotalIndex(0);
        }
    }
}
 
MinIndexSelection& IndexAnalysis::getIndexes(const std::string& relName) {
    auto pos = minIndexCover.find(relName);
    if (pos != minIndexCover.end()) {
        return pos->second;
    } else {

References souffle::ram::analysis::MinIndexSelection::addSearch(), getIndexes(), and getSearchSignature().

Here is the call graph for this function:

Field Documentation

minIndexCover

std::map<std::string, MinIndexSelection> souffle::ram::analysis::IndexAnalysis::minIndexCover

private

minimal index cover for relations, i.e., maps a relation to a set of indexes

Definition at line 474 of file Index.h.

name

constexpr const char* souffle::ram::analysis::IndexAnalysis::name = "index-analysis"

staticconstexpr

Definition at line 417 of file Index.h.

relAnalysis

RelationAnalysis* souffle::ram::analysis::IndexAnalysis::relAnalysis

private

relation analysis for looking up relations by name

Definition at line 469 of file Index.h.

---

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

• ram/analysis/Index.h
• ram/analysis/Index.cpp