souffle  2.0.2-371-g6315b36
Public Member Functions | Protected Member Functions | Protected Attributes
souffle::ram::transform::IndexedInequalityTransformer Class Reference

Removes Inequalities from Indexed Operations and replaces them with a Filter Operation and empty Indexed Operations are coverted to their Non-Indexed semantic equivalent. More...

#include <IndexedInequality.h>

Inheritance diagram for souffle::ram::transform::IndexedInequalityTransformer:
Inheritance graph
Collaboration diagram for souffle::ram::transform::IndexedInequalityTransformer:
Collaboration graph

Public Member Functions

std::string getName () const override
 @Brief get name of the transformer More...
 
bool transformIndexToFilter (Program &program)
 Converts a box query into a corresponding partial box query 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::IndexAnalysis * idxAnalysis
 
analysis::RelationAnalysis * relAnalysis
 

Detailed Description

Removes Inequalities from Indexed Operations and replaces them with a Filter Operation and empty Indexed Operations are coverted to their Non-Indexed semantic equivalent.

If there exists inequality constraints in an Indexed Operation, these constraints will be replaced with a semantically equivalent nested Filter Operation.

Furthermore, if after removing all of these inequality constraints from the Indexed Operation we may find that the Indexed Operation is empty (no constraints). This occurs in the case where an Indexed Operation is composed entirely of inequality constraints. In this situation, the Indexed Operation is empty and replaced with a semantically equivalent Operation. i.e. IndexScan -> Scan

For example,

QUERY
...
FOR t1 IN X ON INDEX t1.x < 10 AND t1.y > 20
... // t1 only has inequality constraints placed on it

will be rewritten to

QUERY
...
FOR t1 in X ON INDEX // empty index since all inequalities have been removed
IF t1.x < 10 AND t1.y > 20
// replaced with a semantically equivalent filter
...

will be rewritten to

QUERY
...
FOR t1 in X // Scan instead of IndexScan
IF t1.x < 10 AND t1.y > 20
// replaced with a semantically equivalent filter
...

Definition at line 76 of file IndexedInequality.h.

Member Function Documentation

◆ getName()

std::string souffle::ram::transform::IndexedInequalityTransformer::getName ( ) const
inlineoverridevirtual

@Brief get name of the transformer

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

Definition at line 78 of file IndexedInequality.h.

83  :
84  bool transform(TranslationUnit& translationUnit) override {

◆ transform()

bool souffle::ram::transform::IndexedInequalityTransformer::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 88 of file IndexedInequality.h.

◆ transformIndexToFilter()

bool souffle::ram::transform::IndexedInequalityTransformer::transformIndexToFilter ( Program &  program)

Converts a box query into a corresponding partial box query operation.

This will turn every box query into a filter operation.

Definition at line 41 of file IndexedInequality.cpp.

41  {
42  if (condition == nullptr) {
43  return c;
44  } else {
45  return mk<Conjunction>(std::move(condition), std::move(c));
46  }
47  };
48 
49  visitDepthFirst(program, [&](const Query& query) {
50  std::function<Own<Node>(Own<Node>)> indexToFilterRewriter = [&](Own<Node> node) -> Own<Node> {
51  // find a IndexOperation
52  if (const IndexOperation* indexOperation = dynamic_cast<IndexOperation*>(node.get())) {
53  const Relation& rel = relAnalysis->lookup(indexOperation->getRelation());
54  auto indexSelection = idxAnalysis->getIndexes(indexOperation->getRelation());
55  auto attributesToDischarge = indexSelection.getAttributesToDischarge(
56  idxAnalysis->getSearchSignature(indexOperation), rel);
57  auto pattern = indexOperation->getRangePattern();
58  Own<Condition> condition;
59  RamPattern updatedPattern;
60 
61  for (Expression* p : indexOperation->getRangePattern().first) {
62  updatedPattern.first.emplace_back(p->clone());
63  }
64  for (Expression* p : indexOperation->getRangePattern().second) {
65  updatedPattern.second.emplace_back(p->clone());
66  }
67  for (auto i : attributesToDischarge) {
68  // move constraints out of the indexed inequality and into a conjuction
69  Own<Constraint> lowerBound;
70  Own<Constraint> upperBound;
71  changed = true;
72 
73  if (!isUndefValue(pattern.first[i])) {
74  const Relation& rel = relAnalysis->lookup(indexOperation->getRelation());
75  lowerBound = mk<Constraint>(getGreaterEqualConstraint(rel.getAttributeTypes()[i]),
76  mk<TupleElement>(indexOperation->getTupleId(), i),
77  souffle::clone(pattern.first[i]));
78  condition = addCondition(std::move(condition), souffle::clone(lowerBound));
79  }
80 
81  if (!isUndefValue(pattern.second[i])) {
82  const Relation& rel = relAnalysis->lookup(indexOperation->getRelation());
83  upperBound = mk<Constraint>(getLessEqualConstraint(rel.getAttributeTypes()[i]),
84  mk<TupleElement>(indexOperation->getTupleId(), i),
85  souffle::clone(pattern.second[i]));
86  condition = addCondition(std::move(condition), souffle::clone(upperBound));
87  }
88 
89  // reset the bounds
90  updatedPattern.first[i] = mk<UndefValue>();
91  updatedPattern.second[i] = mk<UndefValue>();
92  }
93 
94  if (condition) {
95  auto nestedOp = souffle::clone(&indexOperation->getOperation());
96  auto filter = mk<Filter>(souffle::clone(condition), souffle::clone(nestedOp));
97 
98  // need to rewrite the node with the same index operation
99  if (const IndexScan* iscan = dynamic_cast<IndexScan*>(node.get())) {
100  node = mk<IndexScan>(iscan->getRelation(), iscan->getTupleId(),
101  std::move(updatedPattern), std::move(filter), iscan->getProfileText());
102  } else if (const ParallelIndexScan* pscan =
103  dynamic_cast<ParallelIndexScan*>(node.get())) {
104  node = mk<ParallelIndexScan>(pscan->getRelation(), pscan->getTupleId(),
105  std::move(updatedPattern), std::move(filter), pscan->getProfileText());
106  } else if (const IndexChoice* ichoice = dynamic_cast<IndexChoice*>(node.get())) {
107  node = mk<IndexChoice>(ichoice->getRelation(), ichoice->getTupleId(),
108  souffle::clone(&ichoice->getCondition()), std::move(updatedPattern),
109  std::move(filter), ichoice->getProfileText());
110  } else if (const IndexAggregate* iagg = dynamic_cast<IndexAggregate*>(node.get())) {
111  // in the case of an aggregate we must strengthen the condition of the aggregate
112  // it doesn't make sense to nest a filter operation because the aggregate needs the
113  // condition in its scope
114  auto strengthenedCondition = addCondition(
115  Own<Condition>(souffle::clone(&iagg->getCondition())), std::move(condition));
116 
117  node = mk<IndexAggregate>(std::move(nestedOp), iagg->getFunction(),
118  iagg->getRelation(), souffle::clone(&iagg->getExpression()),
119  std::move(strengthenedCondition), std::move(updatedPattern),
120  iagg->getTupleId());
121  } else {
122  fatal("New IndexOperation subclass found but not supported while making index.");
123  }
124  }
125  }
126  node->apply(makeLambdaRamMapper(indexToFilterRewriter));
127  return node;
128  };
129  const_cast<Query*>(&query)->apply(makeLambdaRamMapper(indexToFilterRewriter));
130  });
131 
132  visitDepthFirst(program, [&](const Query& query) {
133  std::function<Own<Node>(Own<Node>)> removeEmptyIndexRewriter = [&](Own<Node> node) -> Own<Node> {
134  // find an IndexOperation
135  if (const IndexOperation* indexOperation = dynamic_cast<IndexOperation*>(node.get())) {
136  auto pattern = indexOperation->getRangePattern();
137  size_t length = pattern.first.size();
138  bool foundRealIndexableOperation = false;
139 
140  for (size_t i = 0; i < length; ++i) {
141  // if both bounds are undefined we don't have a box query
142  if (isUndefValue(pattern.first[i]) && isUndefValue(pattern.second[i])) {
143  continue;
144  }
145  // if lower and upper bounds are equal its also not a box query
146  foundRealIndexableOperation = true;
147  break;
148  }
149  if (!foundRealIndexableOperation) {
150  // need to rewrite the node with a semantically equivalent operation to get rid of the
151  // index operation i.e. IndexScan with no indexable attributes -> Scan
152  if (const IndexScan* iscan = dynamic_cast<IndexScan*>(node.get())) {
153  node = mk<Scan>(iscan->getRelation(), iscan->getTupleId(),
154  souffle::clone(&iscan->getOperation()), iscan->getProfileText());
155  } else if (const ParallelIndexScan* pscan =
156  dynamic_cast<ParallelIndexScan*>(node.get())) {
157  node = mk<ParallelScan>(pscan->getRelation(), pscan->getTupleId(),
158  souffle::clone(&pscan->getOperation()), pscan->getProfileText());
159  } else if (const IndexChoice* ichoice = dynamic_cast<IndexChoice*>(node.get())) {
160  node = mk<Choice>(ichoice->getRelation(), ichoice->getTupleId(),
161  souffle::clone(&ichoice->getCondition()),
162  souffle::clone(&ichoice->getOperation()), ichoice->getProfileText());
163  } else if (const IndexAggregate* iagg = dynamic_cast<IndexAggregate*>(node.get())) {
164  node = mk<Aggregate>(souffle::clone(&iagg->getOperation()), iagg->getFunction(),
165  iagg->getRelation(), souffle::clone(&iagg->getExpression()),
166  souffle::clone(&iagg->getCondition()), iagg->getTupleId());
167  } else {
168  fatal("New IndexOperation subclass found but not supported while transforming "
169  "index.");
170  }
171  }
172  }
173  node->apply(makeLambdaRamMapper(removeEmptyIndexRewriter));
174  return node;
175  };
176  const_cast<Query*>(&query)->apply(makeLambdaRamMapper(removeEmptyIndexRewriter));
177  });
178  return changed;
179 }
180 
181 } // namespace souffle::ram::transform

Field Documentation

◆ idxAnalysis

analysis::IndexAnalysis* souffle::ram::transform::IndexedInequalityTransformer::idxAnalysis
protected

Definition at line 94 of file IndexedInequality.h.

◆ relAnalysis

analysis::RelationAnalysis* souffle::ram::transform::IndexedInequalityTransformer::relAnalysis
protected

Definition at line 95 of file IndexedInequality.h.

The documentation for this class was generated from the following files:
souffle::ram::transform::IndexedInequalityTransformer::transform
bool transform(TranslationUnit &translationUnit) override
@Brief transform the translation unit / used by apply @Param translationUnit that will be transformed...
Definition: IndexedInequality.h:88
souffle::ram::isUndefValue
bool isUndefValue(const Expression *expr)
Determines if an expression represents an undefined value.
Definition: Utils.h:40
souffle::ram::transform::IndexedInequalityTransformer::idxAnalysis
analysis::IndexAnalysis * idxAnalysis
Definition: IndexedInequality.h:94
souffle::ram::transform::Transformer::apply
bool apply(TranslationUnit &translationUnit)
@Brief apply the transformer to a translation unit @Param translationUnit that will be transformed.
Definition: Transformer.cpp:39
souffle::getGreaterEqualConstraint
BinaryConstraintOp getGreaterEqualConstraint(const std::string &type)
Definition: BinaryConstraintOps.h:94
souffle::ram::transform::IndexedInequalityTransformer::relAnalysis
analysis::RelationAnalysis * relAnalysis
Definition: IndexedInequality.h:95
souffle::getLessEqualConstraint
BinaryConstraintOp getLessEqualConstraint(const std::string &type)
Definition: BinaryConstraintOps.h:84
souffle::clone
auto clone(const std::vector< A * > &xs)
Definition: ContainerUtil.h:172
i
size_t i
Definition: json11.h:663
souffle::filter
std::vector< A > filter(std::vector< A > xs, F &&f)
Filter a vector to include certain elements.
Definition: FunctionalUtil.h:155
souffle::ram::analysis::MinIndexSelection::getAttributesToDischarge
AttributeSet getAttributesToDischarge(const SearchSignature &s, const Relation &rel)
Return the attribute position for each indexed operation that should be discharged.
Definition: Index.cpp:443
souffle::ram::RamPattern
std::pair< RamBound, RamBound > RamPattern
Definition: IndexOperation.h:42
souffle::fatal
void fatal(const char *format, const Args &... args)
Definition: MiscUtil.h:198
souffle::ram::analysis::RelationAnalysis::lookup
const ram::Relation & lookup(const std::string &name) const
Definition: Relation.cpp:33
souffle::ram::analysis::IndexAnalysis::getIndexes
MinIndexSelection & getIndexes(const std::string &relName)
@Brief get the minimal index cover for a relation
Definition: Index.cpp:549
souffle::ram::analysis::IndexAnalysis::getSearchSignature
SearchSignature getSearchSignature(const IndexOperation *search) const
@Brief Get index signature for an Ram IndexOperation operation
Definition: Index.cpp:612
souffle::ram::visitDepthFirst
void visitDepthFirst(const Node &root, Visitor< R, Ps... > &visitor, Args &... args)
A utility function visiting all nodes within the RAM fragments rooted by the given node recursively i...
Definition: Visitor.h:357
rel
void rel(size_t limit, bool showLimit=true)
Definition: Tui.h:1086
p
a horizontalBars(j=m=void 0===a.axisX.type?new c.AutoScaleAxis(c.Axis.units.x, b.normalized.series, o, c.extend({}, a.axisX,{highLow:d, referenceValue:0})):a.axisX.type.call(c, c.Axis.units.x, b.normalized.series, o, c.extend({}, a.axisX,{highLow:d, referenceValue:0})), l=n=void 0===a.axisY.type?new c.StepAxis(c.Axis.units.y, b.normalized.series, o,{ticks:k}):a.axisY.type.call(c, c.Axis.units.y, b.normalized.series, o, a.axisY)) var p
Definition: htmlJsChartistMin.h:15
souffle::ram::makeLambdaRamMapper
LambdaNodeMapper< Lambda > makeLambdaRamMapper(const Lambda &lambda)
Creates a node mapper based on a corresponding lambda expression.
Definition: LambdaNodeMapper.h:67
Generated by   doxygen 1.8.17