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
|
/**
* 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/db/btreeposition.h"
#include "mongo/db/cursor.h"
#include "mongo/db/namespace_details.h"
#include "mongo/platform/cstdint.h"
#include "mongo/platform/unordered_set.h"
namespace mongo {
/**
* An optimized btree cursor that iterates through all btree keys between a lower bound and an
* upper bound. The contents of the individual keys are not examined by the implementation,
* which simply advances through the tree until reaching a predetermined end location. The goal
* is to optimize count operations where the keys must only be counted, not tested for matching.
*
* Limitations compared to a standard BtreeCursor (partial list):
* - Only supports index constraints consisting of a single interval within an index.
* - Only supports forward direction iteration.
* - Does not support covered index projections.
* - Does not support get more.
* - Only supports V1 indexes (not V0).
*/
class IntervalBtreeCursor : public Cursor {
public:
/**
* @return a cursor, or NULL if no cursor can be created.
* @param namespaceDetails - Collection metadata that will not be modified.
* @param indexDetails - Index metadata, if not a v1 index then make() will return NULL.
* @param lowerBound - Lower bound of the key range to iterate, according to the index's
* native ordering.
* @param lowerBoundInclusive - If true, the lower bound includes the endpoint.
* @param upperBound - Upper bound of the key range to iterate.
* @param upperBoundInclusive - If true, the upper bound includes the endpoint.
*/
static IntervalBtreeCursor* make( /* const */ NamespaceDetails* namespaceDetails,
const IndexDetails& indexDetails,
const BSONObj& lowerBound,
bool lowerBoundInclusive,
const BSONObj& upperBound,
bool upperBoundInclusive );
/** Virtuals from Cursor. */
virtual bool ok();
virtual Record* _current() { return currLoc().rec(); }
virtual BSONObj current() { return currLoc().obj(); }
virtual DiskLoc currLoc();
virtual bool advance();
virtual BSONObj currKey() const;
virtual DiskLoc refLoc() { return currLoc(); }
static void aboutToDeleteBucket( const DiskLoc& b );
virtual BSONObj indexKeyPattern() { return _indexDetails.keyPattern(); }
virtual bool supportGetMore() { return false; }
virtual void noteLocation();
virtual void checkLocation();
virtual bool supportYields() { return true; }
virtual string toString() { return "IntervalBtreeCursor"; }
virtual bool getsetdup( DiskLoc loc );
virtual bool isMultiKey() const { return _multikeyFlag; }
virtual bool modifiedKeys() const { return _multikeyFlag; }
virtual BSONObj prettyIndexBounds() const;
virtual long long nscanned() { return _nscanned; }
virtual CoveredIndexMatcher* matcher() const { return _matcher.get(); }
virtual void setMatcher( shared_ptr<CoveredIndexMatcher> matcher ) { _matcher = matcher; }
virtual ~IntervalBtreeCursor();
private:
IntervalBtreeCursor( NamespaceDetails* namespaceDetails,
const IndexDetails& indexDetails,
const BSONObj& lowerBound,
bool lowerBoundInclusive,
const BSONObj& upperBound,
bool upperBoundInclusive );
// For handling bucket deletion.
static unordered_set<IntervalBtreeCursor*> _activeCursors;
static SimpleMutex _activeCursorsMutex;
void init();
/**
* @return a location in the btree, determined by the parameters specified.
* @param key - The key to search for.
* @param afterKey - If true, return the first btree key greater than the supplied 'key'.
* If false, return the first key equal to the supplied 'key'.
*/
BtreeKeyLocation locateKey( const BSONObj& key, bool afterKey );
/** Find the iteration end location and set _end to it. */
void relocateEnd();
const NamespaceDetails& _namespaceDetails;
const int32_t _indexNo;
const IndexDetails& _indexDetails;
const Ordering _ordering;
const BSONObj _lowerBound;
const bool _lowerBoundInclusive;
const BSONObj _upperBound;
const bool _upperBoundInclusive;
BtreeKeyLocation _curr; // Current position in the btree.
LogicalBtreePosition _currRecoverable; // Helper to track the position of _curr if the
// btree is modified during a mutex yield.
BtreeKeyLocation _end; // Exclusive end location in the btree.
int64_t _nscanned;
shared_ptr<CoveredIndexMatcher> _matcher;
bool _multikeyFlag;
unordered_set<DiskLoc,DiskLoc::Hasher> _dups;
};
} // namespace mongo
|
