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
|
// @file keypattern.h - Utilities for manipulating index/shard key patterns.
/**
* Copyright (C) 2012 10gen Inc.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License, version 3,
* as published by the Free Software Foundation.
*
* 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
* GNU Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#pragma once
#include "mongo/base/string_data.h"
#include "mongo/db/jsobj.h"
#include "mongo/platform/unordered_set.h"
#include "mongo/util/mongoutils/str.h"
namespace mongo {
struct FieldInterval;
class FieldRangeSet;
/**
* A BoundList contains intervals specified by inclusive start
* and end bounds. The intervals should be nonoverlapping and occur in
* the specified direction of traversal. For example, given a simple index {i:1}
* and direction +1, one valid BoundList is: (1, 2); (4, 6). The same BoundList
* would be valid for index {i:-1} with direction -1.
*/
typedef vector<pair<BSONObj,BSONObj> > BoundList;
/** A KeyPattern is an expression describing a transformation of a document into a
* document key. Document keys are used to store documents in indices and to target
* sharded queries.
*
* Examples:
* { a : 1 }
* { a : 1 , b : -1 }
* { a : "hashed" }
*/
class KeyPattern {
public:
/*
* We are allowing implicit conversion from BSON
*/
KeyPattern( const BSONObj& pattern );
/*
* Returns a BSON representation of this KeyPattern.
*/
BSONObj toBSON() const { return _pattern; }
/*
* Returns true if the given fieldname is the (dotted prefix of the) name of one
* element of the (potentially) compound key described by this KeyPattern.
*/
bool hasField( const StringData& fieldname ) const {
return _prefixes.find( fieldname ) != _prefixes.end();
}
/*
* Gets the element of this pattern corresponding to the given fieldname.
* Returns eoo if none exists.
*/
BSONElement getField( const char* fieldname ) const { return _pattern[ fieldname ]; }
/*
* Returns true if the key described by this KeyPattern is a prefix of
* the (potentially) compound key described by 'other'
*/
bool isPrefixOf( const KeyPattern& other ) const {
return _pattern.isPrefixOf( other.toBSON() );
}
/**
* Is the provided key pattern the index over the ID field?
* The always required ID index is always {_id: 1} or {_id: -1}.
*/
static bool isIdKeyPattern(const BSONObj& pattern);
/* Takes a BSONObj whose field names are a prefix of the fields in this keyPattern, and
* outputs a new bound with MinKey values appended to match the fields in this keyPattern
* (or MaxKey values for descending -1 fields). This is useful in sharding for
* calculating chunk boundaries when tag ranges are specified on a prefix of the actual
* shard key, or for calculating index bounds when the shard key is a prefix of the actual
* index used.
*
* @param makeUpperInclusive If true, then MaxKeys instead of MinKeys will be appended, so
* that the output bound will compare *greater* than the bound being extended (note that
* -1's in the keyPattern will swap MinKey/MaxKey vals. See examples).
*
* Examples:
* If this keyPattern is {a : 1}
* extendRangeBound( {a : 55}, false) --> {a : 55}
*
* If this keyPattern is {a : 1, b : 1}
* extendRangeBound( {a : 55}, false) --> {a : 55, b : MinKey}
* extendRangeBound( {a : 55}, true ) --> {a : 55, b : MaxKey}
*
* If this keyPattern is {a : 1, b : -1}
* extendRangeBound( {a : 55}, false) --> {a : 55, b : MaxKey}
* extendRangeBound( {a : 55}, true ) --> {a : 55, b : MinKey}
*/
BSONObj extendRangeBound( const BSONObj& bound , bool makeUpperInclusive ) const;
/**
* Returns true if this KeyPattern contains any computed values, (e.g. {a : "hashed"}),
* and false if this KeyPattern consists of only ascending/descending fields
* (e.g. {a : 1, b : -1}). With our current index expression language, "special" patterns
* are any patterns that are not a simple list of field names and 1/-1 values.
*/
bool isSpecial() const;
/**
* Returns true if the quantities stored in this KeyPattern can be used to compute all the
* quantities in "other". Useful for determining whether an index based on one KeyPattern
* can be used as a covered index for a query based on another.
*/
bool isCoveredBy( const KeyPattern& other ) const;
string toString() const{ return toBSON().toString(); }
/* Given a document, extracts the index key corresponding to this KeyPattern
* Warning: assumes that there is a *single* key to be extracted!
*
* Examples:
* If 'this' KeyPattern is { a : 1 }
* { a: "hi" , b : 4} --> returns { a : "hi" }
* { c : 4 , a : 2 } --> returns { a : 2 }
* { b : 2 } (bad input, don't call with this)
* { a : [1,2] } (bad input, don't call with this)
*
* If 'this' KeyPattern is { a : "hashed" }
* { a: 1 } --> returns { a : NumberLong("5902408780260971510") }
*/
BSONObj extractSingleKey( const BSONObj& doc ) const;
/**@param queryConstraints a FieldRangeSet, usually formed from parsing a query
* @return an ordered list of bounds generated using this KeyPattern and the
* constraints from the FieldRangeSet. This function is used in sharding to
* determine where to route queries according to the shard key pattern.
*
* Examples:
* If this KeyPattern is { a : 1 }
* FieldRangeSet( {a : 5 } ) --> returns [{a : 5}, {a : 5 } ]
* FieldRangeSet( {a : {$gt : 3}} ) --> returns [({a : 3} , { a : MaxInt})]
*
* If this KeyPattern is { a : "hashed }
* FieldRangeSet( {a : 5 } --> returns [ ({ a : hash(5) }, {a : hash(5) }) ]
*
* The bounds returned by this function may be a superset of those defined
* by the constraints. For instance, if this KeyPattern is {a : 1}
* FieldRanget( { a : {$in : [1,2]} , b : {$in : [3,4,5]} } )
* --> returns [({a : 1 , b : 3} , {a : 1 , b : 5}]),
* [({a : 2 , b : 3} , {a : 2 , b : 5}])
*
* The queryConstraints should be defined for all the fields in this keypattern
* (i.e. the value of frsp->matchPossibleForSingleKeyFRS(_pattern) should be true,
* otherwise this function could throw).
*
*/
BoundList keyBounds( const FieldRangeSet& queryConstraints ) const;
private:
BSONObj _pattern;
// Each field in the '_pattern' may be itself a dotted field. We store all the prefixes
// of each field here. For instance, if a pattern is { 'a.b.c': 1, x: 1 }, we'll store
// here 'a', 'a.b', 'a.b.c', and 'x'.
//
// Since we're indexing into '_pattern's field names, it must stay constant after
// constructed.
struct PrefixHasher {
size_t operator()( const StringData& strData ) const {
size_t result = 0;
const char* p = strData.rawData();
for (size_t len = strData.size(); len > 0; len-- ) {
result = ( result * 131 ) + *p++;
}
return result;
}
};
unordered_set<StringData, PrefixHasher> _prefixes;
bool isAscending( const BSONElement& fieldExpression ) const {
return ( fieldExpression.isNumber() && fieldExpression.numberInt() == 1 );
}
bool isDescending( const BSONElement& fieldExpression ) const {
return ( fieldExpression.isNumber() && fieldExpression.numberInt() == -1 );
}
bool isHashed( const BSONElement& fieldExpression ) const {
return mongoutils::str::equals( fieldExpression.valuestrsafe() , "hashed" );
}
/* Takes a list of intervals corresponding to constraints on a given field
* in this keypattern, and transforms them into a list of bounds
* based on the expression for 'field'
*/
BoundList _transformFieldBounds( const vector<FieldInterval>& oldIntervals ,
const BSONElement& field ) const;
};
} // namespace mongo
|
