1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
|
/**
* Copyright (C) 2018-present MongoDB, Inc.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the Server Side Public License, version 1,
* as published by MongoDB, Inc.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* Server Side Public License for more details.
*
* You should have received a copy of the Server Side Public License
* along with this program. If not, see
* <http://www.mongodb.com/licensing/server-side-public-license>.
*
* As a special exception, the copyright holders give permission to link the
* code of portions of this program with the OpenSSL library under certain
* conditions as described in each individual source file and distribute
* linked combinations including the program with the OpenSSL library. You
* must comply with the Server Side Public License in all respects for
* all of the code used other than as permitted herein. If you modify file(s)
* with this exception, you may extend this exception to your version of the
* file(s), but you are not obligated to do so. If you do not wish to do so,
* delete this exception statement from your version. If you delete this
* exception statement from all source files in the program, then also delete
* it in the license file.
*/
#pragma once
#include <deque>
#include <vector>
#include "mongo/bson/util/builder.h"
#include "mongo/db/matcher/expression.h"
namespace mongo {
// output from enumerator to query planner
class IndexTag : public MatchExpression::TagData {
public:
static const size_t kNoIndex;
/**
* Assigns a leaf expression to the leading field of index 'i' where combining bounds with other
* leaf expressions is known to be safe.
*/
IndexTag(size_t i) : index(i) {}
/**
* Assigns a leaf expresssion to position 'p' of index 'i' where whether it is safe to combine
* bounds with other leaf expressions is defined by 'canCombineBounds_'.
*/
IndexTag(size_t i, size_t p, bool canCombineBounds_)
: index(i), pos(p), canCombineBounds(canCombineBounds_) {}
virtual ~IndexTag() {}
virtual void debugString(StringBuilder* builder) const {
*builder << " || Selected Index #" << index << " pos " << pos << " combine "
<< canCombineBounds;
}
virtual MatchExpression::TagData* clone() const {
return new IndexTag(index, pos, canCombineBounds);
}
virtual Type getType() const {
return Type::IndexTag;
}
// What index should we try to use for this leaf?
size_t index = kNoIndex;
// What position are we in the index? (Compound.)
size_t pos = 0U;
// The plan enumerator can assign multiple predicates to the same position of a multikey index
// when generating a self-intersection index assignment in enumerateAndIntersect().
// 'canCombineBounds' gives the access planner enough information to know when it is safe to
// intersect the bounds for multiple leaf expressions on the 'pos' field of 'index' and when it
// isn't. The plan enumerator should never generate an index assignment where it isn't safe to
// compound the bounds for multiple leaf expressions on the index.
bool canCombineBounds = true;
};
// used internally
class RelevantTag : public MatchExpression::TagData {
public:
RelevantTag() : elemMatchExpr(NULL), pathPrefix("") {}
std::vector<size_t> first;
std::vector<size_t> notFirst;
// We don't know the full path from a node unless we keep notes as we traverse from the
// root. We do this once and store it.
// TODO: Do a FieldRef / StringData pass.
// TODO: We might want this inside of the MatchExpression.
std::string path;
// Points to the innermost containing $elemMatch. If this tag is
// attached to an expression not contained in an $elemMatch, then
// 'elemMatchExpr' is NULL. Not owned here.
MatchExpression* elemMatchExpr;
// If not contained inside an elemMatch, 'pathPrefix' contains the
// part of 'path' prior to the first dot. For example, if 'path' is
// "a.b.c", then 'pathPrefix' is "a". If 'path' is just "a", then
// 'pathPrefix' is also "a".
//
// If tagging a predicate contained in an $elemMatch, 'pathPrefix'
// holds the prefix of the path *inside* the $elemMatch. If this
// tags predicate {a: {$elemMatch: {"b.c": {$gt: 1}}}}, then
// 'pathPrefix' is "b".
//
// Used by the plan enumerator to make sure that we never
// compound two predicates sharing a path prefix.
std::string pathPrefix;
virtual void debugString(StringBuilder* builder) const {
*builder << " || First: ";
for (size_t i = 0; i < first.size(); ++i) {
*builder << first[i] << " ";
}
*builder << "notFirst: ";
for (size_t i = 0; i < notFirst.size(); ++i) {
*builder << notFirst[i] << " ";
}
*builder << "full path: " << path;
}
virtual MatchExpression::TagData* clone() const {
RelevantTag* ret = new RelevantTag();
ret->first = first;
ret->notFirst = notFirst;
return ret;
}
virtual Type getType() const {
return Type::RelevantTag;
}
};
/**
* An OrPushdownTag indicates that this node is a predicate that can be used inside of a sibling
* indexed OR.
*/
class OrPushdownTag final : public MatchExpression::TagData {
public:
/**
* A destination to which this predicate should be pushed down, consisting of a route through
* the sibling indexed OR, and the tag the predicate should receive after it is pushed down.
*/
struct Destination {
Destination clone() const {
Destination clone;
clone.route = route;
clone.tagData.reset(tagData->clone());
return clone;
}
void debugString(StringBuilder* builder) const {
*builder << " || Move to ";
bool firstPosition = true;
for (auto position : route) {
if (!firstPosition) {
*builder << ",";
}
firstPosition = false;
*builder << position;
}
tagData->debugString(builder);
}
/**
* The route along which the predicate should be pushed down. This starts at the
* indexed OR sibling of the predicate. Each value in 'route' is the index of a child in
* an indexed OR.
* For example, if the MatchExpression tree is:
* AND
* / \
* {a: 5} OR
* / \
* AND {e: 9}
* / \
* {b: 6} OR
* / \
* {c: 7} {d: 8}
* and the predicate is {a: 5}, then the path {0, 1} means {a: 5} should be
* AND-combined with {d: 8}.
*/
std::deque<size_t> route;
// The TagData that the predicate should be tagged with after it is pushed down.
std::unique_ptr<MatchExpression::TagData> tagData;
};
void debugString(StringBuilder* builder) const override {
if (_indexTag) {
_indexTag->debugString(builder);
}
for (const auto& dest : _destinations) {
dest.debugString(builder);
}
}
MatchExpression::TagData* clone() const override {
std::unique_ptr<OrPushdownTag> clone = stdx::make_unique<OrPushdownTag>();
for (const auto& dest : _destinations) {
clone->addDestination(dest.clone());
}
if (_indexTag) {
clone->setIndexTag(_indexTag->clone());
}
return clone.release();
}
Type getType() const override {
return Type::OrPushdownTag;
}
void addDestination(Destination dest) {
_destinations.push_back(std::move(dest));
}
const std::vector<Destination>& getDestinations() const {
return _destinations;
}
/**
* Releases ownership of the destinations.
*/
std::vector<Destination> releaseDestinations() {
std::vector<Destination> destinations;
destinations.swap(_destinations);
return destinations;
}
void setIndexTag(MatchExpression::TagData* indexTag) {
_indexTag.reset(indexTag);
}
const MatchExpression::TagData* getIndexTag() const {
return _indexTag.get();
}
std::unique_ptr<MatchExpression::TagData> releaseIndexTag() {
return std::move(_indexTag);
}
private:
std::vector<Destination> _destinations;
// The index tag the predicate should receive at its current position in the tree.
std::unique_ptr<MatchExpression::TagData> _indexTag;
};
/*
* Reorders the nodes according to their tags as needed for access planning. 'tree' should be a
* tagged MatchExpression tree in canonical order.
*/
void prepareForAccessPlanning(MatchExpression* tree);
} // namespace mongo
|