souffle  2.0.2-371-g6315b36
IndexedInequality.cpp
Go to the documentation of this file.
1 /*
2  * Souffle - A Datalog Compiler
3  * Copyright (c) 2018, The Souffle Developers. All rights reserved
4  * Licensed under the Universal Permissive License v 1.0 as shown at:
5  * - https://opensource.org/licenses/UPL
6  * - <souffle root>/licenses/SOUFFLE-UPL.txt
7  */
8 
9 /************************************************************************
10  *
11  * @file IndexedInequality.cpp
12  *
13  ***********************************************************************/
14 
16 #include "ram/Condition.h"
17 #include "ram/Expression.h"
18 #include "ram/Node.h"
19 #include "ram/Operation.h"
20 #include "ram/Program.h"
21 #include "ram/Relation.h"
22 #include "ram/Statement.h"
23 #include "ram/utility/Utils.h"
24 #include "ram/utility/Visitor.h"
27 #include <algorithm>
28 #include <cstddef>
29 #include <functional>
30 #include <memory>
31 #include <unordered_set>
32 #include <utility>
33 #include <vector>
34 
35 namespace souffle::ram::transform {
36 
38  bool changed = false;
39 
40  // helper for collecting conditions from filter operations
41  auto addCondition = [](Own<Condition> condition, Own<Condition> c) -> Own<Condition> {
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
souffle::ram::transform
Definition: ChoiceConversion.cpp:30
souffle::ram::IndexOperation
Definition: IndexOperation.h:48
BinaryConstraintOps.h
souffle::ram::Query
A relational algebra query.
Definition: Query.h:50
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::Own
std::unique_ptr< A > Own
Definition: ContainerUtil.h:42
MiscUtil.h
souffle::getLessEqualConstraint
BinaryConstraintOp getLessEqualConstraint(const std::string &type)
Definition: BinaryConstraintOps.h:84
Program.h
souffle::Relation
Object-oriented wrapper class for Souffle's templatized relations.
Definition: SouffleInterface.h:49
Visitor.h
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::Relation
An abstract class for performing indexed operations.
Definition: Relation.h:40
Relation.h
Condition.h
Utils.h
IndexedInequality.h
Node.h
Operation.h
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
Statement.h
souffle::fatal
void fatal(const char *format, const Args &... args)
Definition: MiscUtil.h:198
souffle::ram::transform::IndexedInequalityTransformer::transformIndexToFilter
bool transformIndexToFilter(Program &program)
Converts a box query into a corresponding partial box query operation.
Definition: IndexedInequality.cpp:41
Expression.h
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
souffle::ram::Expression
Abstract class for describing scalar values in RAM.
Definition: Expression.h:33
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