souffle::ram::analysis::MinIndexSelection Class Reference

#include <Index.h>

Inheritance diagram for souffle::ram::analysis::MinIndexSelection:

Collaboration diagram for souffle::ram::analysis::MinIndexSelection:

Data Structures
class	SearchComparator

Public Types
using	AttributeIndex = uint32_t
using	AttributeSet = std::unordered_set< AttributeIndex >
using	Chain = std::vector< SearchSignature >
using	ChainOrderMap = std::list< Chain >
using	DischargeMap = std::unordered_map< SearchSignature, AttributeSet, SearchSignature::Hasher >
using	IndexSignatureMap = std::unordered_map< AttributeIndex, SearchSignature >
using	LexOrder = std::vector< AttributeIndex >
using	OrderCollection = std::vector< LexOrder >
using	SearchSet = std::set< SearchSignature, SearchComparator >
using	SignatureIndexMap = std::unordered_map< SearchSignature, AttributeIndex, SearchSignature::Hasher >
using	SignatureMap = std::unordered_map< SearchSignature, SearchSignature, SearchSignature::Hasher >

Public Member Functions
void	addSearch (SearchSignature cols)
	@Brief Add new key to an Index Set More...
const ChainOrderMap	getAllChains () const
	@Brief Get all chains More...
const OrderCollection	getAllOrders () const
	@Brief Get all indexes More...
AttributeSet	getAttributesToDischarge (const SearchSignature &s, const Relation &rel)
	Return the attribute position for each indexed operation that should be discharged. More...
const LexOrder &	getLexOrder (SearchSignature cols) const
	@Brief Get index for a search More...
int	getLexOrderNum (SearchSignature cols) const
	@Brief Get index for a search More...
const SearchSet &	getSearches () const
	@Brief Get searches More...
void	insertDefaultTotalIndex (size_t arity)
	@Brief insert a total order index More...
bool	isSubset (SearchSignature cols) const
	Check whether number of constraints in k is not equal to number of columns in lexicographical order. More...
	MinIndexSelection ()=default
void	print (std::ostream &os)
void	solve ()
	@Brief map the keys in the key set to lexicographical order More...
	~MinIndexSelection ()=default

Protected Member Functions
Chain	getChain (const SearchSignature umn, const MaxMatching::Matchings &match)
	@Brief get a chain from a matching More...
const ChainOrderMap	getChainsFromMatching (const MaxMatching::Matchings &match, const SearchSet &nodes)
	@Brief get all chains from the matching More...
const SearchSet	getUnmatchedKeys (const MaxMatching::Matchings &match, const SearchSet &nodes)
	@Brief get all nodes which are unmatched from A-> B More...
void	insertIndex (LexOrder &ids, SearchSignature delta)
	@Brief insert an index based on the delta More...
int	map (SearchSignature cols) const
	@Brief maps search columns to an lexicographical order (labeled by a number) More...
void	removeExtraInequalities ()
	@Brief remove arbitrary extra inequalities More...
void	updateSearch (SearchSignature oldSearch, SearchSignature newSearch)

Static Protected Member Functions
static size_t	card (SearchSignature cols)
	@Brief count the number of constraints in key More...

Protected Attributes
ChainOrderMap	chainToOrder
DischargeMap	dischargedMap
IndexSignatureMap	indexToSignature
MaxMatching	matching
OrderCollection	orders
SearchSet	searches
SignatureIndexMap	signatureToIndexA
SignatureIndexMap	signatureToIndexB

Detailed Description

@Brief computes the minimal index cover for a relation in a RAM Program.

If the indexes of a relation can cover several searches, the minimal set of indexes is computed by Dilworth's problem. See

"Automatic Index Selection for Large-Scale Datalog Computation" http://www.vldb.org/pvldb/vol12/p141-subotic.pdf

Definition at line 208 of file Index.h.

Member Typedef Documentation

AttributeIndex

using souffle::ram::analysis::MinIndexSelection::AttributeIndex = uint32_t

Definition at line 210 of file Index.h.

AttributeSet

using souffle::ram::analysis::MinIndexSelection::AttributeSet = std::unordered_set<AttributeIndex>

Definition at line 211 of file Index.h.

Chain

using souffle::ram::analysis::MinIndexSelection::Chain = std::vector<SearchSignature>

Definition at line 218 of file Index.h.

ChainOrderMap

using souffle::ram::analysis::MinIndexSelection::ChainOrderMap = std::list<Chain>

Definition at line 221 of file Index.h.

DischargeMap

using souffle::ram::analysis::MinIndexSelection::DischargeMap = std::unordered_map<SearchSignature, AttributeSet, SearchSignature::Hasher>

Definition at line 215 of file Index.h.

IndexSignatureMap

using souffle::ram::analysis::MinIndexSelection::IndexSignatureMap = std::unordered_map<AttributeIndex, SearchSignature>

Definition at line 214 of file Index.h.

LexOrder

using souffle::ram::analysis::MinIndexSelection::LexOrder = std::vector<AttributeIndex>

Definition at line 216 of file Index.h.

OrderCollection

using souffle::ram::analysis::MinIndexSelection::OrderCollection = std::vector<LexOrder>

Definition at line 217 of file Index.h.

SearchSet

using souffle::ram::analysis::MinIndexSelection::SearchSet = std::set<SearchSignature, SearchComparator>

Definition at line 231 of file Index.h.

SignatureIndexMap

using souffle::ram::analysis::MinIndexSelection::SignatureIndexMap = std::unordered_map<SearchSignature, AttributeIndex, SearchSignature::Hasher>

Definition at line 213 of file Index.h.

SignatureMap

using souffle::ram::analysis::MinIndexSelection::SignatureMap = std::unordered_map<SearchSignature, SearchSignature, SearchSignature::Hasher>

Definition at line 212 of file Index.h.

Constructor & Destructor Documentation

MinIndexSelection()

souffle::ram::analysis::MinIndexSelection::MinIndexSelection ( )

default

~MinIndexSelection()

souffle::ram::analysis::MinIndexSelection::~MinIndexSelection ( )

default

Member Function Documentation

addSearch()

void souffle::ram::analysis::MinIndexSelection::addSearch ( SearchSignature  cols )

inline

@Brief Add new key to an Index Set

Definition at line 237 of file Index.h.

                                                {
        if (!cols.empty()) {
            searches.insert(cols);
        }
    }

References souffle::ram::analysis::SearchSignature::empty(), and searches.

Referenced by souffle::ram::analysis::IndexAnalysis::run().

Here is the call graph for this function:

card()

static size_t souffle::ram::analysis::MinIndexSelection::card ( SearchSignature  cols )

inlinestaticprotected

@Brief count the number of constraints in key

Definition at line 338 of file Index.h.

                                             {
        size_t sz = 0;
        for (size_t i = 0; i < cols.arity(); i++) {
            if (cols[i] != AttributeConstraint::None) {
                sz++;
            }
        }
        return sz;
    }

References souffle::ram::analysis::SearchSignature::arity(), i, and souffle::ram::analysis::None.

Referenced by isSubset().

Here is the call graph for this function:

getAllChains()

const ChainOrderMap souffle::ram::analysis::MinIndexSelection::getAllChains ( ) const

inline

@Brief Get all chains

Definition at line 268 of file Index.h.

                                             {
        return chainToOrder;
    }

References chainToOrder.

Referenced by print().

getAllOrders()

const OrderCollection souffle::ram::analysis::MinIndexSelection::getAllOrders ( ) const

inline

@Brief Get all indexes

Definition at line 263 of file Index.h.

                                               {
        return orders;
    }

References orders.

Referenced by souffle::interpreter::Relation< 2, Eqrel >::castView(), and print().

getAttributesToDischarge()

MinIndexSelection::AttributeSet souffle::ram::analysis::MinIndexSelection::getAttributesToDischarge	(	const SearchSignature &	s,
		const Relation &	rel
	)

Return the attribute position for each indexed operation that should be discharged.

Definition at line 443 of file Index.cpp.

                                                                      {
        return allInequalities;
    }
 
    // do not support indexed inequalities with provenance
    if (Global::config().has("provenance")) {
        return allInequalities;
    }
 
    // if we are in the interpreter then we only permit signed inequalities
    // remembering to discharge any excess signed inequalities!
    AttributeSet interpreterAttributesToDischarge(dischargedMap[s]);
    for (size_t i = 0; i < s.arity(); ++i) {
        if (s[i] == AttributeConstraint::Inequal && rel.getAttributeTypes()[i][0] != 'i') {
            interpreterAttributesToDischarge.insert(i);
        }
    }
    if (!Global::config().has("compile") && !Global::config().has("dl-program") &&
            !Global::config().has("generate") && !Global::config().has("swig")) {
        return interpreterAttributesToDischarge;
    }
 
    return dischargedMap[s];
}
 
void IndexAnalysis::run(const TranslationUnit& translationUnit) {
    relAnalysis = translationUnit.getAnalysis<RelationAnalysis>();
 
    // After complete:
    // 1. All relations should have at least one index (for full-order search).

getChain()

MinIndexSelection::Chain souffle::ram::analysis::MinIndexSelection::getChain ( const SearchSignature  umn, const MaxMatching::Matchings &  match  )

protected

@Brief get a chain from a matching

Parameters

Starting	node of a chain
Matching

Returns

A minimal chain given an unmapped node from set A we follow it from set B until it cannot be matched from B if not matched from B then umn is a chain.

Definition at line 348 of file Index.cpp.

                 {
        auto mit = match.find(signatureToIndexB[start]);  // we start from B side
        // on each iteration we swap sides when collecting the chain so we use the corresponding index map
        if (std::find(chain.begin(), chain.end(), start) == chain.end()) {
            chain.push_back(start);
        }
 
        if (mit == match.end()) {
            std::reverse(chain.begin(), chain.end());
            return chain;
        }
 
        SearchSignature a = indexToSignature.at(mit->second);
        if (std::find(chain.begin(), chain.end(), a) == chain.end()) {
            chain.push_back(a);
        }
        start = a;
    }
}
 
const MinIndexSelection::ChainOrderMap MinIndexSelection::getChainsFromMatching(
        const MaxMatching::Matchings& match, const SearchSet& nodes) {
    assert(!nodes.empty());
 
    // Get all unmatched nodes from A

References indexToSignature, and signatureToIndexB.

getChainsFromMatching()

const MinIndexSelection::ChainOrderMap souffle::ram::analysis::MinIndexSelection::getChainsFromMatching ( const MaxMatching::Matchings &  match, const SearchSet &  nodes  )

protected

@Brief get all chains from the matching

Definition at line 377 of file Index.cpp.

                        {
        for (auto node : nodes) {
            Chain a;
            a.push_back(node);
            chainToOrder.push_back(a);
            return chainToOrder;
        }
    }
 
    assert(!umKeys.empty());
 
    // A worklist of used nodes
    SearchSet usedKeys;
 
    // Case: nodes < umKeys or if nodes == umKeys then anti chain - this is handled by this loop
    for (auto umKey : umKeys) {
        Chain c = getChain(umKey, match);
        assert(!c.empty());
        chainToOrder.push_back(c);
    }
 
    assert(!chainToOrder.empty());
    return chainToOrder;
}
 
void MinIndexSelection::updateSearch(SearchSignature oldSearch, SearchSignature newSearch) {
    auto delta = SearchSignature::getDelta(oldSearch, newSearch);
    for (size_t i = 0; i < delta.arity(); ++i) {
        if (delta[i] == AttributeConstraint::Inequal) {
            dischargedMap[oldSearch].insert(i);

References chainToOrder.

getLexOrder()

const LexOrder& souffle::ram::analysis::MinIndexSelection::getLexOrder ( SearchSignature  cols ) const

inline

@Brief Get index for a search

Definition at line 252 of file Index.h.

                                                            {
        int idx = map(cols);
        return orders[idx];
    }

References map(), and orders.

Here is the call graph for this function:

getLexOrderNum()

int souffle::ram::analysis::MinIndexSelection::getLexOrderNum ( SearchSignature  cols ) const

inline

@Brief Get index for a search

Definition at line 258 of file Index.h.

                                                   {
        return map(cols);
    }

References map().

Here is the call graph for this function:

getSearches()

const SearchSet& souffle::ram::analysis::MinIndexSelection::getSearches ( ) const

inline

@Brief Get searches

Definition at line 247 of file Index.h.

                                         {
        return searches;
    }

References searches.

Referenced by print().

getUnmatchedKeys()

const SearchSet souffle::ram::analysis::MinIndexSelection::getUnmatchedKeys ( const MaxMatching::Matchings &  match, const SearchSet &  nodes  )

inlineprotected

@Brief get all nodes which are unmatched from A-> B

Definition at line 396 of file Index.h.

                                                                                                {
        SearchSet unmatched;
 
        // For all nodes n such that n is not in match
        for (auto node : nodes) {
            if (match.find(signatureToIndexA[node]) == match.end()) {
                unmatched.insert(node);
            }
        }
        return unmatched;
    }

References signatureToIndexA.

insertDefaultTotalIndex()

void souffle::ram::analysis::MinIndexSelection::insertDefaultTotalIndex ( size_t  arity )

inline

@Brief insert a total order index

Parameters

size	of the index

Definition at line 287 of file Index.h.

                                               {
        Chain chain = std::vector<SearchSignature>();
        SearchSignature fullIndexKey = SearchSignature::getFullSearchSignature(arity);
        chain.push_back(fullIndexKey);
        chainToOrder.push_back(std::move(chain));
        LexOrder totalOrder;
        for (size_t i = 0; i < arity; ++i) {
            totalOrder.push_back(i);
        }
        orders.push_back(std::move(totalOrder));
    }

References chainToOrder, souffle::ram::analysis::SearchSignature::getFullSearchSignature(), i, and orders.

Here is the call graph for this function:

insertIndex()

void souffle::ram::analysis::MinIndexSelection::insertIndex ( LexOrder &  ids, SearchSignature  delta  )

inlineprotected

@Brief insert an index based on the delta

Definition at line 362 of file Index.h.

                                                           {
        LexOrder backlog;  // add inequalities at the end
        for (size_t pos = 0; pos < delta.arity(); pos++) {
            if (delta[pos] == AttributeConstraint::Equal) {
                ids.push_back(pos);
            } else if (delta[pos] == AttributeConstraint::Inequal) {
                backlog.push_back(pos);
            }
        }
        ids.insert(ids.end(), backlog.begin(), backlog.end());
    }

References souffle::ram::analysis::SearchSignature::arity(), souffle::ram::analysis::Equal, and souffle::ram::analysis::Inequal.

Here is the call graph for this function:

isSubset()

bool souffle::ram::analysis::MinIndexSelection::isSubset ( SearchSignature  cols ) const

inline

Check whether number of constraints in k is not equal to number of columns in lexicographical order.

Definition at line 276 of file Index.h.

                                              {
        int idx = map(cols);
        return card(cols) < orders[idx].size();
    }

References card(), map(), and orders.

Here is the call graph for this function:

map()

int souffle::ram::analysis::MinIndexSelection::map ( SearchSignature  cols ) const

inlineprotected

@Brief maps search columns to an lexicographical order (labeled by a number)

Definition at line 349 of file Index.h.

                                        {
        assert(orders.size() == chainToOrder.size() && "Order and Chain Sizes do not match!!");
        int i = 0;
        for (auto it = chainToOrder.begin(); it != chainToOrder.end(); ++it, ++i) {
            if (std::find(it->begin(), it->end(), cols) != it->end()) {
                assert((size_t)i < orders.size());
                return i;
            }
        }
        fatal("cannot find matching lexicographical order");
    }

References chainToOrder, souffle::fatal(), i, and orders.

Referenced by getLexOrder(), getLexOrderNum(), and isSubset().

Here is the call graph for this function:

print()

void souffle::ram::analysis::MinIndexSelection::print ( std::ostream &  os )

inline

Definition at line 302 of file Index.h.

                               {
        /* Print searches */
        os << "\tNumber of Searches: " << getSearches().size() << "\n";
 
        /* print searches */
        for (auto& search : getSearches()) {
            os << "\t\t";
            os << search;
            os << "\n";
        }
 
        /* print chains */
        for (auto& chain : getAllChains()) {
            os << join(chain, "-->") << "\n";
        }
        os << "\n";
 
        os << "\tNumber of Indexes: " << getAllOrders().size() << "\n";
        for (auto& order : getAllOrders()) {
            os << "\t\t";
            os << join(order, "<") << "\n";
            os << "\n";
        }
    }

References getAllChains(), getAllOrders(), getSearches(), and souffle::join().

Here is the call graph for this function:

removeExtraInequalities()

void souffle::ram::analysis::MinIndexSelection::removeExtraInequalities ( )

protected

@Brief remove arbitrary extra inequalities

Definition at line 426 of file Index.cpp.

                                    {
                    newSearch[i] = AttributeConstraint::None;
                } else {
                    seenInequality = true;
                }
            }
        }
        updateSearch(oldSearch, newSearch);
    }
}
 
MinIndexSelection::AttributeSet MinIndexSelection::getAttributesToDischarge(
        const SearchSignature& s, const Relation& rel) {
    // by default we have all attributes w/inequalities discharged
    AttributeSet allInequalities;
    for (size_t i = 0; i < s.arity(); ++i) {

References i, and souffle::ram::analysis::None.

solve()

void souffle::ram::analysis::MinIndexSelection::solve

(

)

@Brief map the keys in the key set to lexicographical order

Definition at line 263 of file Index.cpp.

                           : searches) {
        if (s.empty()) {
            continue;
        }
        // map the signature to its unique index in each set
        signatureToIndexA.insert({s, currentIndex});
        signatureToIndexB.insert({s, currentIndex + 1});
        // map each index back to the search signature
        indexToSignature.insert({currentIndex, s});
        indexToSignature.insert({currentIndex + 1, s});
        currentIndex += 2;
    }
 
    // Construct the matching poblem
    for (auto search : searches) {
        for (auto itt : searches) {
            if (search == itt) {
                continue;
            }
 
            if (search < itt) {
                matching.addEdge(signatureToIndexA[search], signatureToIndexB[itt]);
            }
        }
    }
 
    // Perform the Hopcroft-Karp on the graph and receive matchings (mapped A->B and B->A)
    // Assume: alg.calculate is not called on an empty graph
    assert(!searches.empty());
    const MaxMatching::Matchings& matchings = matching.solve();
 
    // Extract the chains given the nodes and matchings
    ChainOrderMap chains = getChainsFromMatching(matchings, searches);
 
    // Should never get no chains back as we never call calculate on an empty graph
    assert(!chains.empty());
    for (const auto& chain : chains) {
        std::vector<uint32_t> ids;
 
        SearchSignature initDelta = *(chain.begin());
        insertIndex(ids, initDelta);
 
        // build the lex-order
        for (auto iit = chain.begin(); next(iit) != chain.end(); ++iit) {
            SearchSignature delta = SearchSignature::getDelta(*next(iit), *iit);
            insertIndex(ids, delta);
        }
 
        assert(!ids.empty());
        orders.push_back(ids);
    }
 
    // Validate the lex-order
    for (auto chain : chains) {
        for (auto search : chain) {
            int idx = map(search);
            size_t l = card(search);
 
            SearchSignature k(search.arity());
            for (size_t i = 0; i < l; i++) {
                k[orders[idx][i]] = AttributeConstraint::Equal;
            }
            for (size_t i = 0; i < search.arity(); ++i) {
                if (k[i] == AttributeConstraint::None && search[i] != AttributeConstraint::None) {
                    assert("incorrect lexicographical order");
                }
                if (k[i] != AttributeConstraint::None && search[i] == AttributeConstraint::None) {
                    assert("incorrect lexicographical order");
                }
            }
        }
    }
}
 
MinIndexSelection::Chain MinIndexSelection::getChain(
        const SearchSignature umn, const MaxMatching::Matchings& match) {
    SearchSignature start = umn;  // start at an unmatched node
    Chain chain;
    // given an unmapped node from set A we follow it from set B until it cannot be matched from B

updateSearch()

void souffle::ram::analysis::MinIndexSelection::updateSearch ( SearchSignature  oldSearch, SearchSignature  newSearch  )

protected

Parameters

OldSearch	to be updated
NewSearch	to replace the OldSearch

Definition at line 409 of file Index.cpp.

                     : chainToOrder) {
        for (auto& search : chain) {
            if (search == oldSearch) {
                search = newSearch;
            }
        }
    }
}
 
void MinIndexSelection::removeExtraInequalities() {
    for (auto oldSearch : searches) {
        auto newSearch = oldSearch;
        bool seenInequality = false;
        for (size_t i = 0; i < oldSearch.arity(); ++i) {

Field Documentation

chainToOrder

ChainOrderMap souffle::ram::analysis::MinIndexSelection::chainToOrder

protected

Definition at line 334 of file Index.h.

Referenced by getAllChains(), getChainsFromMatching(), insertDefaultTotalIndex(), and map().

dischargedMap

DischargeMap souffle::ram::analysis::MinIndexSelection::dischargedMap

protected

Definition at line 330 of file Index.h.

indexToSignature

IndexSignatureMap souffle::ram::analysis::MinIndexSelection::indexToSignature

protected

Definition at line 331 of file Index.h.

Referenced by getChain().

matching

MaxMatching souffle::ram::analysis::MinIndexSelection::matching

protected

Definition at line 335 of file Index.h.

orders

OrderCollection souffle::ram::analysis::MinIndexSelection::orders

protected

Definition at line 333 of file Index.h.

Referenced by getAllOrders(), getLexOrder(), insertDefaultTotalIndex(), isSubset(), and map().

searches

SearchSet souffle::ram::analysis::MinIndexSelection::searches

protected

Definition at line 332 of file Index.h.

Referenced by addSearch(), and getSearches().

signatureToIndexA

SignatureIndexMap souffle::ram::analysis::MinIndexSelection::signatureToIndexA

protected

Definition at line 328 of file Index.h.

Referenced by getUnmatchedKeys().

signatureToIndexB

SignatureIndexMap souffle::ram::analysis::MinIndexSelection::signatureToIndexB

protected

Definition at line 329 of file Index.h.

Referenced by getChain().

---

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

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