/**
* Copyright (C) 2013 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 .
*
* 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 GNU Affero General 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
#include
#include "mongo/db/jsobj.h"
#include "mongo/db/query/interval.h"
#include "mongo/db/storage/index_entry_comparison.h"
namespace mongo {
/**
* An ordered list of intervals for one field.
*/
struct OrderedIntervalList {
OrderedIntervalList() {}
OrderedIntervalList(const std::string& n) : name(n) {}
// Must be ordered according to the index order.
std::vector intervals;
// TODO: We could drop this. Only used in IndexBounds::isValidFor.
std::string name;
bool isValidFor(int expectedOrientation) const;
std::string toString() const;
/**
* Complements the OIL. Used by the index bounds builder in order
* to create index bounds for $not predicates.
*
* Assumes the OIL is increasing, and therefore must be called prior to
* alignBounds(...).
*
* Example:
* The complement of [3, 6), [8, 10] is [MinKey, 3), [6, 8), (20, MaxKey],
* where this OIL has direction==1.
*/
void complement();
};
/**
* Tied to an index. Permissible values for all fields in the index. Requires the index to
* interpret. Previously known as FieldRangeVector.
*/
struct IndexBounds {
IndexBounds() : isSimpleRange(false), endKeyInclusive(false) {}
// For each indexed field, the values that the field is allowed to take on.
std::vector fields;
// Debugging check.
// We must have as many fields the key pattern does.
// The fields must be oriented in the direction we'd encounter them given the indexing
// direction (the value of the field in keyPattern) and index traversal direction provided
// by 'direction'.
//
// An example: [7, 20]
// We can traverse this forward if indexed ascending
// We can traverse this backwards if indexed descending.
bool isValidFor(const BSONObj& keyPattern, int direction);
// Methods below used for debugging purpose only. Do not use outside testing code.
size_t size() const;
std::string getFieldName(size_t i) const;
size_t getNumIntervals(size_t i) const;
Interval getInterval(size_t i, size_t j) const;
std::string toString() const;
/**
* BSON format for explain. The format is an array of strings for each field.
* Each string represents an interval. The strings use "[" and "]" if the interval
* bounds are inclusive, and "(" / ")" if exclusive.
*
* Ex.
* {a: ["[1, 1]", "(3, 10)"], b: ["[Infinity, 10)"] }
*/
BSONObj toBSON() const;
// TODO: we use this for max/min scan. Consider migrating that.
bool isSimpleRange;
BSONObj startKey;
BSONObj endKey;
bool endKeyInclusive;
};
/**
* A helper used by IndexScan to navigate an index.
*/
class IndexBoundsChecker {
public:
/**
* keyPattern is the index that we're iterating over.
* bounds are the bounds we're allowed to iterate over.
* direction is the direction we're moving over the index, 1 or -1.
*
* Bounds not owned by us.
*/
IndexBoundsChecker(const IndexBounds* bounds, const BSONObj& keyPattern, int direction);
/**
* Get the IndexSeekPoint that we should with.
*
* Returns false if there are no possible index entries that match the bounds. In this case
* there is no valid start point to seek to so out will not be filled out and the caller
* should emit no results.
*/
bool getStartSeekPoint(IndexSeekPoint* out);
/**
* The states of a key from an index scan. See checkKey below.
*/
enum KeyState {
VALID,
MUST_ADVANCE,
DONE,
};
/**
* Is 'key' a valid key? Note that this differs from checkKey, which assumes that it
* receives keys in sorted order.
*/
bool isValidKey(const BSONObj& key);
/**
* This function checks if the key is within the bounds we're iterating over and updates any
* internal state required to efficiently determine if the key is within our bounds.
*
* Possible outcomes:
*
* 1. The key is in our bounds. Returns VALID. Caller can use the data associated with the
* key.
*
* 2. The key is not in our bounds but has not exceeded the maximum value in our bounds.
* Returns MUST_ADVANCE. Caller must advance to the query provided in the out parameters
* and call checkKey again.
*
* 3. The key is past our bounds. Returns DONE. No further keys will satisfy the bounds
* and the caller should stop.
*
* keyEltsToUse, movePastKeyElts, out, and incOut must all be non-NULL.
* out and incOut must already be resized to have as many elements as the key has fields.
*
* In parameters:
* currentKey is the index key.
*
* Out parameter only valid if we return MUST_ADVANCE.
*/
KeyState checkKey(const BSONObj& currentKey, IndexSeekPoint* query);
/**
* Relative position of a key to an interval.
* Exposed for testing only.
*/
enum Location {
BEHIND = -1,
WITHIN = 0,
AHEAD = 1,
};
/**
* If 'elt' is in any interval, return WITHIN and set 'newIntervalIndex' to the index of the
* interval in the ordered interval list.
*
* If 'elt' is not in any interval but could be advanced to be in one, return BEHIND and set
* 'newIntervalIndex' to the index of the interval that 'elt' could be advanced to.
*
* If 'elt' cannot be advanced to any interval, return AHEAD.
*
* Exposed for testing only.
*
* TODO(efficiency): Start search from a given index.
*/
static Location findIntervalForField(const BSONElement& elt,
const OrderedIntervalList& oil,
const int expectedDirection,
size_t* newIntervalIndex);
private:
/**
* Find the first field in the key that isn't within the interval we think it is. Returns
* false if every field is in the interval we think it is. Returns true and populates out
* parameters if a field isn't in the interval we think it is.
*
* Out parameters set if we return true:
* 'where' is the leftmost field that isn't in the interval we think it is.
* 'what' is the orientation of the field with respect to that interval.
*/
bool findLeftmostProblem(const std::vector& keyValues,
size_t* where,
Location* what);
/**
* Returns true if it's possible to advance any of the first 'fieldsToCheck' fields of the
* index key and still be within valid index bounds.
*
* keyValues are the elements of the index key in order.
*/
bool spaceLeftToAdvance(size_t fieldsToCheck, const std::vector& keyValues);
// The actual bounds. Must outlive this object. Not owned by us.
const IndexBounds* _bounds;
// For each field, which interval are we currently in?
std::vector _curInterval;
// Direction of scan * direction of indexing.
std::vector _expectedDirection;
};
} // namespace mongo