/usr/include/mongo/db/keypattern.h is in mongodb-dev 1:2.4.9-1ubuntu2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 | // @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() );
}
/* 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
|