souffle  2.0.2-371-g6315b36
IndexOperation.h
Go to the documentation of this file.
1 /*
2  * Souffle - A Datalog Compiler
3  * Copyright (c) 2013, 2014, Oracle and/or its affiliates. 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 IndexOperation.h
12  *
13  ***********************************************************************/
14 
15 #pragma once
16 
17 #include "ram/Expression.h"
18 #include "ram/Node.h"
19 #include "ram/Operation.h"
20 #include "ram/Relation.h"
21 #include "ram/RelationOperation.h"
22 #include "ram/utility/NodeMapper.h"
23 #include "ram/utility/Utils.h"
26 #include <cassert>
27 #include <iosfwd>
28 #include <memory>
29 #include <ostream>
30 #include <string>
31 #include <utility>
32 #include <vector>
33 
34 namespace souffle::ram {
35 
36 /** Pattern type for lower/upper bound */
37 using RamBound = VecOwn<Expression>;
38 using RamPattern = std::pair<RamBound, RamBound>;
39 
40 /**
41  * @class Relation Scan with Index
42  * @brief An abstract class for performing indexed operations
43  */
44 class IndexOperation : public RelationOperation {
45 public:
46  IndexOperation(std::string rel, int ident, RamPattern queryPattern, Own<Operation> nested,
47  std::string profileText = "")
48  : RelationOperation(rel, ident, std::move(nested), std::move(profileText)),
49  queryPattern(std::move(queryPattern)) {
50  assert(getRangePattern().first.size() == getRangePattern().second.size() && "Arity mismatch");
51  for (const auto& pattern : queryPattern.first) {
52  assert(pattern != nullptr && "pattern is a null-pointer");
53  }
54  for (const auto& pattern : queryPattern.second) {
55  assert(pattern != nullptr && "pattern is a null-pointer");
56  }
57  }
58 
59  /**
60  * @brief Get range pattern
61  * @return A pair of std::vector of pointers to Expression objects
62  * These vectors represent the lower and upper bounds for each attribute in the tuple
63  * <expr1> <= Tuple[level, element] <= <expr2>
64  * We have that at an index for an attribute, its bounds are <expr1> and <expr2> respectively
65  * */
66  std::pair<std::vector<Expression*>, std::vector<Expression*>> getRangePattern() const {
67  return std::make_pair(toPtrVector(queryPattern.first), toPtrVector(queryPattern.second));
68  }
69 
70  std::vector<const Node*> getChildNodes() const override {
72  for (auto& pattern : queryPattern.first) {
73  res.push_back(pattern.get());
74  }
75  for (auto& pattern : queryPattern.second) {
76  res.push_back(pattern.get());
77  }
78  return res;
79  }
80 
81  void apply(const NodeMapper& map) override {
83  for (auto& pattern : queryPattern.first) {
84  pattern = map(std::move(pattern));
85  }
86  for (auto& pattern : queryPattern.second) {
87  pattern = map(std::move(pattern));
88  }
89  }
90 
91  IndexOperation* clone() const override {
92  RamPattern resQueryPattern;
93  for (const auto& i : queryPattern.first) {
94  resQueryPattern.first.emplace_back(i->clone());
95  }
96  for (const auto& i : queryPattern.second) {
97  resQueryPattern.second.emplace_back(i->clone());
98  }
99  return new IndexOperation(relation, getTupleId(), std::move(resQueryPattern),
101  }
102 
103  /** @brief Helper method for printing */
104  void printIndex(std::ostream& os) const {
105  // const auto& attrib = getRelation().getAttributeNames();
106  bool first = true;
107  for (unsigned int i = 0; i < queryPattern.first.size(); ++i) {
108  // early exit if no upper/lower bounds are defined
109  if (isUndefValue(queryPattern.first[i].get()) && isUndefValue(queryPattern.second[i].get())) {
110  continue;
111  }
112 
113  if (first) {
114  os << " ON INDEX ";
115  first = false;
116  } else {
117  os << " AND ";
118  }
119 
120  // both bounds defined and equal => equality
121  if (!isUndefValue(queryPattern.first[i].get()) && !isUndefValue(queryPattern.second[i].get())) {
122  // print equality when lower bound = upper bound
123  if (*(queryPattern.first[i]) == *(queryPattern.second[i])) {
124  os << "t" << getTupleId() << ".";
125  os << i << " = ";
126  os << *(queryPattern.first[i]);
127  continue;
128  }
129  }
130  // at least one bound defined => inequality
131  if (!isUndefValue(queryPattern.first[i].get()) || !isUndefValue(queryPattern.second[i].get())) {
132  if (!isUndefValue(queryPattern.first[i].get())) {
133  os << *(queryPattern.first[i]) << " <= ";
134  }
135 
136  os << "t" << getTupleId() << ".";
137  os << i;
138 
139  if (!isUndefValue(queryPattern.second[i].get())) {
140  os << " <= " << *(queryPattern.second[i]);
141  }
142 
143  continue;
144  }
145  }
146  }
147 
148 protected:
149  bool equal(const Node& node) const override {
150  const auto& other = static_cast<const IndexOperation&>(node);
151  return RelationOperation::equal(other) &&
152  equal_targets(queryPattern.first, other.queryPattern.first) &&
153  equal_targets(queryPattern.second, other.queryPattern.second);
154  }
155 
156  /** Values of index per column of table (if indexable) */
158 };
159 
160 } // namespace souffle::ram
souffle::ram::NestedOperation::profileText
const std::string profileText
Text used by the profiler.
Definition: NestedOperation.h:93
souffle::ram::IndexOperation
Definition: IndexOperation.h:48
souffle::ram::RamBound
VecOwn< Expression > RamBound
Pattern type for lower/upper bound.
Definition: IndexOperation.h:41
souffle::ram::isUndefValue
bool isUndefValue(const Expression *expr)
Determines if an expression represents an undefined value.
Definition: Utils.h:40
souffle::ram::TupleOperation::getChildNodes
std::vector< const Node * > getChildNodes() const override
Obtain list of all embedded child nodes.
Definition: TupleOperation.h:52
souffle::ram::IndexOperation::getRangePattern
std::pair< std::vector< Expression * >, std::vector< Expression * > > getRangePattern() const
Get range pattern.
Definition: IndexOperation.h:70
souffle::ram::IndexOperation::getChildNodes
std::vector< const Node * > getChildNodes() const override
Obtain list of all embedded child nodes.
Definition: IndexOperation.h:74
souffle::ram::NestedOperation::apply
void apply(const NodeMapper &map) override
Apply the mapper to all child nodes.
Definition: NestedOperation.h:75
souffle::ram::NestedOperation::getOperation
Operation & getOperation() const
Get nested operation.
Definition: NestedOperation.h:62
souffle::Own
std::unique_ptr< A > Own
Definition: ContainerUtil.h:42
souffle::map
auto map(const std::vector< A > &xs, F &&f)
Applies a function to each element of a vector and returns the results.
Definition: ContainerUtil.h:158
MiscUtil.h
RelationOperation.h
souffle::ram
Definition: AstToRamTranslator.h:54
souffle::ram::RelationOperation::relation
const std::string relation
Search relation.
Definition: RelationOperation.h:60
souffle::ram::IndexOperation::apply
void apply(const NodeMapper &map) override
Apply the mapper to all child nodes.
Definition: IndexOperation.h:85
souffle::clone
auto clone(const std::vector< A * > &xs)
Definition: ContainerUtil.h:172
NodeMapper.h
i
size_t i
Definition: json11.h:663
ContainerUtil.h
souffle::ram::IndexOperation::clone
IndexOperation * clone() const override
Create a clone (i.e.
Definition: IndexOperation.h:95
souffle::ram::NestedOperation::getProfileText
const std::string & getProfileText() const
Get profile text.
Definition: NestedOperation.h:67
souffle::ram::IndexOperation::equal
bool equal(const Node &node) const override
Equality check for two RAM nodes.
Definition: IndexOperation.h:153
Relation.h
souffle::equal_targets
bool equal_targets(const Container &a, const Container &b, const Comparator &comp)
A function testing whether two containers are equal with the given Comparator.
Definition: ContainerUtil.h:433
souffle::ram::RelationOperation::equal
bool equal(const Node &node) const override
Equality check for two RAM nodes.
Definition: RelationOperation.h:54
souffle::ram::RelationOperation
Abstract class for operations on relations.
Definition: RelationOperation.h:41
souffle::ram::TupleOperation::getTupleId
int getTupleId() const
Get identifier.
Definition: TupleOperation.h:43
Utils.h
souffle::ram::IndexOperation::printIndex
void printIndex(std::ostream &os) const
Helper method for printing.
Definition: IndexOperation.h:108
Node.h
std
Definition: Brie.h:3053
Operation.h
souffle::ram::IndexOperation::queryPattern
RamPattern queryPattern
Values of index per column of table (if indexable)
Definition: IndexOperation.h:161
souffle::ram::RamPattern
std::pair< RamBound, RamBound > RamPattern
Definition: IndexOperation.h:42
Expression.h
rel
void rel(size_t limit, bool showLimit=true)
Definition: Tui.h:1086
souffle::toPtrVector
std::vector< T * > toPtrVector(const std::vector< std::unique_ptr< T >> &v)
A utility function enabling the creation of a vector of pointers.
Definition: ContainerUtil.h:146
souffle::ram::IndexOperation::IndexOperation
IndexOperation(std::string rel, int ident, RamPattern queryPattern, Own< Operation > nested, std::string profileText="")
Definition: IndexOperation.h:50