souffle::ram::transform::MakeIndexTransformer Class Reference

Make indexable operations to indexed operations. More...

#include <MakeIndex.h>

Inheritance diagram for souffle::ram::transform::MakeIndexTransformer:

Collaboration diagram for souffle::ram::transform::MakeIndexTransformer:

Public Types
using	ExpressionPair = std::pair< Own< Expression >, Own< Expression > >
	Get expression of RAM element access. More...

Public Member Functions
Own< Condition >	constructPattern (const std::vector< std::string > &attributeTypes, RamPattern &queryPattern, bool &indexable, VecOwn< Condition > conditionList, int identifier)
ExpressionPair	getExpressionPair (const Constraint *binRelOp, size_t &element, int identifier)
ExpressionPair	getLowerUpperExpression (Condition *c, size_t &element, int level)
std::string	getName () const override
	@Brief get name of the transformer More...
bool	makeIndex (Program &program)
	Make indexable RAM operation indexed. More...
Own< Operation >	rewriteAggregate (const Aggregate *agg)
	Rewrite an aggregate operation to an indexed aggregate operation. More...
Own< Operation >	rewriteIndexScan (const IndexScan *iscan)
	Rewrite an index scan operation to an amended index scan operation. More...
Own< Operation >	rewriteScan (const Scan *scan)
	Rewrite a scan operation to an indexed scan operation. More...
Public Member Functions inherited from souffle::ram::transform::Transformer
bool	apply (TranslationUnit &translationUnit)
	@Brief apply the transformer to a translation unit @Param translationUnit that will be transformed. More...
virtual	~Transformer ()=default

Protected Member Functions
bool	transform (TranslationUnit &translationUnit) override
	@Brief transform the translation unit / used by apply @Param translationUnit that will be transformed. More...

Protected Attributes
analysis::RelationAnalysis *	relAnalysis {nullptr}
analysis::LevelAnalysis *	rla {nullptr}

Detailed Description

Make indexable operations to indexed operations.

The transformer assumes that the RAM has been levelled before. The conditions that could be used for an index must be located immediately after the scan or aggregate operation.

QUERY
 ...
 FOR t1 IN A
  IF t1.x = 10 /\ t1.y = 20 /\ C
   ...

will be rewritten to

QUERY
 ...
  SEARCH t1 IN A INDEX t1.x=10 AND t1.y = 20
   IF C
    ...

Definition at line 68 of file MakeIndex.h.

Member Typedef Documentation

ExpressionPair

using souffle::ram::transform::MakeIndexTransformer::ExpressionPair = std::pair<Own<Expression>, Own<Expression> >

Get expression of RAM element access.

Parameters

Equivalence	constraints of the format t1.x = <expression> or <expression> = t1.x
Element	that was accessed, e.g., for t1.x this would be the index of attribute x.
Tuple	identifier

The method retrieves expression the expression of an equivalence constraint of the format t1.x = <expr> or <expr> = t1.x

Definition at line 84 of file MakeIndex.h.

Member Function Documentation

constructPattern()

Own< Condition > souffle::ram::transform::MakeIndexTransformer::constructPattern	(	const std::vector< std::string > &	attributeTypes,
		RamPattern &	queryPattern,
		bool &	indexable,
		VecOwn< Condition >	conditionList,
		int	identifier
	)

Parameters

AttributeTypes	to indicate type of each attribute in the relation
Query	pattern that is to be constructed
Flag	to indicate whether operation is indexable
A	list of conditions that will be transformed to query patterns
Tuple	identifier of the indexable operation

Returns

Remaining conditions that could not be transformed to an index

Definition at line 121 of file MakeIndex.cpp.

                                              {
        if (condition != nullptr) {
            condition = mk<Conjunction>(std::move(condition), std::move(c));
        } else {
            condition = std::move(c);
        }
    };
 
    // transform condition list so that every strict inequality becomes a weak inequality + filter
    // e.g. Tuple[level, element] < <expr> --> Tuple[level, element] <= <expr> and Tuple[level, element] !=
    // <expr>
    std::vector<std::unique_ptr<Condition>> toAppend;
    auto it = conditionList.begin();
    while (it != conditionList.end()) {
        auto* binRelOp = dynamic_cast<Constraint*>(it->get());
        if (binRelOp == nullptr) {
            ++it;
            continue;
        }
 
        bool transformable = false;
 
        if (isStrictIneqConstraint(binRelOp->getOperator())) {
            if (const auto* lhs = dynamic_cast<const TupleElement*>(&binRelOp->getLHS())) {
                const Expression* rhs = &binRelOp->getRHS();
                if (lhs->getTupleId() == identifier && rla->getLevel(rhs) < identifier) {
                    transformable = true;
                }
            }
            if (const auto* rhs = dynamic_cast<const TupleElement*>(&binRelOp->getRHS())) {
                const Expression* lhs = &binRelOp->getLHS();
                if (rhs->getTupleId() == identifier && rla->getLevel(lhs) < identifier) {
                    transformable = true;
                }
            }
        }
 
        if (transformable) {
            // append the weak version of inequality
            toAppend.emplace_back(
                    std::make_unique<Constraint>(convertStrictToWeakIneqConstraint(binRelOp->getOperator()),
                            clone(&binRelOp->getLHS()), clone(&binRelOp->getRHS())));
            // append the != constraint
            toAppend.emplace_back(
                    std::make_unique<Constraint>(convertStrictToNotEqualConstraint(binRelOp->getOperator()),
                            clone(&binRelOp->getLHS()), clone(&binRelOp->getRHS())));
 
            // remove the strict version of inequality
            it = conditionList.erase(it);
        } else {
            ++it;
        }
    }
 
    std::transform(toAppend.begin(), toAppend.end(), std::back_inserter(conditionList),
            [](const std::unique_ptr<Condition>& cond) { return clone(cond); });
 
    // Build query pattern and remaining condition
    for (auto& cond : conditionList) {
        size_t element = 0;
        Own<Expression> lowerExpression;
        Own<Expression> upperExpression;
        std::tie(lowerExpression, upperExpression) = getLowerUpperExpression(cond.get(), element, identifier);
 
        // we have new bounds if at least one is defined
        if (!isUndefValue(lowerExpression.get()) || !isUndefValue(upperExpression.get())) {
            // if no previous bounds are set then just assign them, consider both bounds to be set (but not
            // necessarily defined) in all remaining cases
            auto type = attributeTypes[element];
            indexable = true;
            if (isUndefValue(queryPattern.first[element].get()) &&
                    isUndefValue(queryPattern.second[element].get())) {
                queryPattern.first[element] = std::move(lowerExpression);
                queryPattern.second[element] = std::move(upperExpression);
                // if lower bound is undefined and we have a new lower bound then assign it
            } else if (isUndefValue(queryPattern.first[element].get()) &&
                       !isUndefValue(lowerExpression.get()) && isUndefValue(upperExpression.get())) {
                queryPattern.first[element] = std::move(lowerExpression);
                // if upper bound is undefined and we have a new upper bound then assign it
            } else if (isUndefValue(queryPattern.second[element].get()) &&
                       isUndefValue(lowerExpression.get()) && !isUndefValue(upperExpression.get())) {
                queryPattern.second[element] = std::move(upperExpression);
                // if both bounds are defined ...
                // and equal then we have a previous equality constraint i.e. Tuple[level, element] = <expr1>
            } else if (!isUndefValue(queryPattern.first[element].get()) &&
                       !isUndefValue(queryPattern.second[element].get()) &&
                       (*(queryPattern.first[element]) == *(queryPattern.second[element]))) {
                // new equality constraint i.e. Tuple[level, element] = <expr2>
                // simply hoist <expr1> = <expr2> to the outer loop
                if (!isUndefValue(lowerExpression.get()) && !isUndefValue(upperExpression.get())) {
                    // FIXME: `FEQ` handling; need to know if the expr is a float exp or not
                    addCondition(mk<Constraint>(getEqConstraint(type),
                            souffle::clone(queryPattern.first[element]), std::move(lowerExpression)));
                }
                // new lower bound i.e. Tuple[level, element] >= <expr2>
                // we need to hoist <expr1> >= <expr2> to the outer loop
                else if (!isUndefValue(lowerExpression.get()) && isUndefValue(upperExpression.get())) {
                    addCondition(mk<Constraint>(getGreaterEqualConstraint(type),
                            souffle::clone(queryPattern.first[element]), std::move(lowerExpression)));
                }
                // new upper bound i.e. Tuple[level, element] <= <expr2>
                // we need to hoist <expr1> <= <expr2> to the outer loop
                else if (isUndefValue(lowerExpression.get()) && !isUndefValue(upperExpression.get())) {
                    addCondition(mk<Constraint>(getLessEqualConstraint(type),
                            souffle::clone(queryPattern.first[element]), std::move(upperExpression)));
                }
                // if either bound is defined but they aren't equal we must consider the cases for updating
                // them note that at this point we know that if we have a lower/upper bound it can't be the
                // first one
            } else if (!isUndefValue(queryPattern.first[element].get()) ||
                       !isUndefValue(queryPattern.second[element].get())) {
                // if we have a new equality constraint and previous inequality constraints
                if (!isUndefValue(lowerExpression.get()) && !isUndefValue(upperExpression.get()) &&
                        *lowerExpression == *upperExpression) {
                    // if Tuple[level, element] >= <expr1> and we see Tuple[level, element] = <expr2>
                    // need to hoist <expr2> >= <expr1> to the outer loop
                    if (!isUndefValue(queryPattern.first[element].get())) {
                        addCondition(mk<Constraint>(getGreaterEqualConstraint(type),
                                souffle::clone(lowerExpression), std::move(queryPattern.first[element])));
                    }
                    // if Tuple[level, element] <= <expr1> and we see Tuple[level, element] = <expr2>
                    // need to hoist <expr2> <= <expr1> to the outer loop
                    if (!isUndefValue(queryPattern.second[element].get())) {
                        addCondition(mk<Constraint>(getLessEqualConstraint(type),
                                souffle::clone(upperExpression), std::move(queryPattern.second[element])));
                    }
                    // finally replace bounds with equality constraint
                    queryPattern.first[element] = std::move(lowerExpression);
                    queryPattern.second[element] = std::move(upperExpression);
                    // if we have a new lower bound
                } else if (!isUndefValue(lowerExpression.get())) {
                    // we want the tightest lower bound so we take the max
                    VecOwn<Expression> maxArguments;
                    maxArguments.push_back(std::move(queryPattern.first[element]));
                    maxArguments.push_back(std::move(lowerExpression));
 
                    queryPattern.first[element] =
                            mk<IntrinsicOperator>(getMaxOp(type), std::move(maxArguments));
                    // if we have a new upper bound
                } else if (!isUndefValue(upperExpression.get())) {
                    // we want the tightest upper bound so we take the min
                    VecOwn<Expression> minArguments;
                    minArguments.push_back(std::move(queryPattern.second[element]));
                    minArguments.push_back(std::move(upperExpression));
 
                    queryPattern.second[element] =
                            mk<IntrinsicOperator>(getMinOp(type), std::move(minArguments));
                }
            }
        } else {
            addCondition(std::move(cond));
        }
    }
 
    // Avoid null-pointers for condition and query pattern
    if (condition == nullptr) {
        condition = mk<True>();
    }
    return condition;
}
 
Own<Operation> MakeIndexTransformer::rewriteAggregate(const Aggregate* agg) {
    if (dynamic_cast<const True*>(&agg->getCondition()) == nullptr) {
        const Relation& rel = relAnalysis->lookup(agg->getRelation());

getExpressionPair()

ExpressionPair souffle::ram::transform::MakeIndexTransformer::getExpressionPair	(	const Constraint *	binRelOp,
		size_t &	element,
		int	identifier
	)

Definition at line 48 of file MakeIndex.cpp.

                                                                                      {
            const Expression* rhs = &binRelOp->getRHS();
            if (lhs->getTupleId() == identifier && rla->getLevel(rhs) < identifier) {
                element = lhs->getElement();
                return {mk<UndefValue>(), clone(rhs)};
            }
        }
        // <expr> <= Tuple[level, element]
        if (const auto* rhs = dynamic_cast<const TupleElement*>(&binRelOp->getRHS())) {
            const Expression* lhs = &binRelOp->getLHS();
            if (rhs->getTupleId() == identifier && rla->getLevel(lhs) < identifier) {
                element = rhs->getElement();
                return {clone(lhs), mk<UndefValue>()};
            }
        }
    }
 
    if (isGreaterEqual(binRelOp->getOperator())) {
        // Tuple[level, element] >= <expr>
        if (const auto* lhs = dynamic_cast<const TupleElement*>(&binRelOp->getLHS())) {
            const Expression* rhs = &binRelOp->getRHS();
            if (lhs->getTupleId() == identifier && rla->getLevel(rhs) < identifier) {
                element = lhs->getElement();
                return {clone(rhs), mk<UndefValue>()};
            }
        }
        // <expr> >= Tuple[level, element]
        if (const auto* rhs = dynamic_cast<const TupleElement*>(&binRelOp->getRHS())) {
            const Expression* lhs = &binRelOp->getLHS();
            if (rhs->getTupleId() == identifier && rla->getLevel(lhs) < identifier) {
                element = rhs->getElement();
                return {mk<UndefValue>(), clone(lhs)};
            }
        }
    }
    return {mk<UndefValue>(), mk<UndefValue>()};
}
 
// Retrieves the <expr1> <= Tuple[level, element] <= <expr2> part of the constraint as a pair { <expr1>,
// <expr2> }
ExpressionPair MakeIndexTransformer::getLowerUpperExpression(Condition* c, size_t& element, int identifier) {

References souffle::clone(), souffle::ram::analysis::LevelAnalysis::getLevel(), souffle::identifier(), lhs, rhs, and rla.

Here is the call graph for this function:

getLowerUpperExpression()

ExpressionPair souffle::ram::transform::MakeIndexTransformer::getLowerUpperExpression	(	Condition *	c,
		size_t &	element,
		int	level
	)

Definition at line 92 of file MakeIndex.cpp.

                                                                             {
            return {mk<UndefValue>(), mk<UndefValue>()};
        } else if (isEqConstraint(binRelOp->getOperator())) {
            if (const auto* lhs = dynamic_cast<const TupleElement*>(&binRelOp->getLHS())) {
                const Expression* rhs = &binRelOp->getRHS();
                if (lhs->getTupleId() == identifier && rla->getLevel(rhs) < identifier) {
                    element = lhs->getElement();
                    return {clone(rhs), clone(rhs)};
                }
            }
            if (const auto* rhs = dynamic_cast<const TupleElement*>(&binRelOp->getRHS())) {
                const Expression* lhs = &binRelOp->getLHS();
                if (rhs->getTupleId() == identifier && rla->getLevel(lhs) < identifier) {
                    element = rhs->getElement();
                    return {clone(lhs), clone(lhs)};
                }
            }
        } else if (isWeakIneqConstraint(binRelOp->getOperator())) {
            return getExpressionPair(binRelOp, element, identifier);
        }
    }
    return {mk<UndefValue>(), mk<UndefValue>()};
}
 
Own<Condition> MakeIndexTransformer::constructPattern(const std::vector<std::string>& attributeTypes,
        RamPattern& queryPattern, bool& indexable, VecOwn<Condition> conditionList, int identifier) {
    // Remaining conditions which cannot be handled by an index

getName()

std::string souffle::ram::transform::MakeIndexTransformer::getName ( ) const

inlineoverridevirtual

@Brief get name of the transformer

Implements souffle::ram::transform::Transformer.

Definition at line 70 of file MakeIndex.h.

makeIndex()

bool souffle::ram::transform::MakeIndexTransformer::makeIndex

(

Program &

program

)

Make indexable RAM operation indexed.

Parameters

RAM	program that is transformed

Returns

Flag that indicates whether the input program has changed

Definition at line 361 of file MakeIndex.cpp.

                                                                    {
                const Relation& rel = relAnalysis->lookup(scan->getRelation());
                if (rel.getRepresentation() != RelationRepresentation::INFO) {
                    if (Own<Operation> op = rewriteScan(scan)) {
                        changed = true;
                        node = std::move(op);
                    }
                }
            } else if (const IndexScan* iscan = dynamic_cast<IndexScan*>(node.get())) {
                if (Own<Operation> op = rewriteIndexScan(iscan)) {
                    changed = true;
                    node = std::move(op);
                }
            } else if (const Aggregate* agg = dynamic_cast<Aggregate*>(node.get())) {
                if (Own<Operation> op = rewriteAggregate(agg)) {
                    changed = true;
                    node = std::move(op);
                }
            }
            node->apply(makeLambdaRamMapper(scanRewriter));
            return node;
        };
        const_cast<Query*>(&query)->apply(makeLambdaRamMapper(scanRewriter));
    });
    return changed;
}
 
}  // namespace souffle::ram::transform

References souffle::INFO, souffle::ram::analysis::RelationAnalysis::lookup(), rel(), relAnalysis, and rewriteScan().

Here is the call graph for this function:

rewriteAggregate()

Own< Operation > souffle::ram::transform::MakeIndexTransformer::rewriteAggregate

(

const Aggregate *

agg

)

Rewrite an aggregate operation to an indexed aggregate operation.

Parameters

Aggregate

operation that is potentially rewritten to an indexed version

Returns

The result is null if the aggregate could not be rewritten to an indexed version; otherwise the new indexed version of the aggregate is returned.

Definition at line 286 of file MakeIndex.cpp.

                                                          {
            queryPattern.first.push_back(mk<UndefValue>());
            queryPattern.second.push_back(mk<UndefValue>());
        }
 
        bool indexable = false;
        Own<Condition> condition = constructPattern(rel.getAttributeTypes(), queryPattern, indexable,
                toConjunctionList(&agg->getCondition()), identifier);
        if (indexable) {
            return mk<IndexAggregate>(souffle::clone(&agg->getOperation()), agg->getFunction(),
                    agg->getRelation(), souffle::clone(&agg->getExpression()), std::move(condition),
                    std::move(queryPattern), agg->getTupleId());
        }
    }
    return nullptr;
}
 
Own<Operation> MakeIndexTransformer::rewriteScan(const Scan* scan) {
    if (const auto* filter = dynamic_cast<const Filter*>(&scan->getOperation())) {
        const Relation& rel = relAnalysis->lookup(scan->getRelation());

rewriteIndexScan()

Own< Operation > souffle::ram::transform::MakeIndexTransformer::rewriteIndexScan

(

const IndexScan *

iscan

)

Rewrite an index scan operation to an amended index scan operation.

Parameters

An	IndexScan that can be amended with new index values

Returns

The result is null if the index scan cannot be amended; otherwise the new IndexScan operation is returned.

Definition at line 333 of file MakeIndex.cpp.

                       {
            // Merge Index Pattern here
 
            Own<Operation> op = souffle::clone(&filter->getOperation());
            if (!isTrue(condition.get())) {
                op = mk<Filter>(std::move(condition), std::move(op));
            }
            return mk<IndexScan>(iscan->getRelation(), identifier, std::move(strengthenedPattern),
                    std::move(op), iscan->getProfileText());
        }
    }
    return nullptr;
}
 
bool MakeIndexTransformer::makeIndex(Program& program) {
    bool changed = false;
    visitDepthFirst(program, [&](const Query& query) {

rewriteScan()

Own< Operation > souffle::ram::transform::MakeIndexTransformer::rewriteScan

(

const Scan *

scan

)

Rewrite a scan operation to an indexed scan operation.

Parameters

Scan	operation that is potentially rewritten to an IndexScan

Returns

The result is null if the scan could not be rewritten to an IndexScan; otherwise the new IndexScan operation is returned.

Definition at line 308 of file MakeIndex.cpp.

                                                          {
            queryPattern.first.push_back(mk<UndefValue>());
            queryPattern.second.push_back(mk<UndefValue>());
        }
 
        bool indexable = false;
        Own<Condition> condition = constructPattern(rel.getAttributeTypes(), queryPattern, indexable,
                toConjunctionList(&filter->getCondition()), identifier);
        if (indexable) {
            Own<Operation> op = souffle::clone(&filter->getOperation());
            if (!isTrue(condition.get())) {
                op = mk<Filter>(std::move(condition), std::move(op));
            }
            return mk<IndexScan>(scan->getRelation(), identifier, std::move(queryPattern), std::move(op),
                    scan->getProfileText());
        }
    }
    return nullptr;
}
 
Own<Operation> MakeIndexTransformer::rewriteIndexScan(const IndexScan* iscan) {
    if (const auto* filter = dynamic_cast<const Filter*>(&iscan->getOperation())) {
        const Relation& rel = relAnalysis->lookup(iscan->getRelation());

Referenced by makeIndex().

transform()

bool souffle::ram::transform::MakeIndexTransformer::transform ( TranslationUnit &  translationUnit )

inlineoverrideprotectedvirtual

@Brief transform the translation unit / used by apply @Param translationUnit that will be transformed.

@Return flag reporting whether the RAM program has changed

Implements souffle::ram::transform::Transformer.

Definition at line 134 of file MakeIndex.h.

                                         {nullptr};
};
 

Field Documentation

relAnalysis

analysis::RelationAnalysis* souffle::ram::transform::MakeIndexTransformer::relAnalysis {nullptr}

protected

Definition at line 140 of file MakeIndex.h.

Referenced by makeIndex().

rla

analysis::LevelAnalysis* souffle::ram::transform::MakeIndexTransformer::rla {nullptr}

protected

Definition at line 132 of file MakeIndex.h.

Referenced by getExpressionPair().

---

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

• ram/transform/MakeIndex.h
• ram/transform/MakeIndex.cpp