← Back to branch summary

~ubuntu-branches/ubuntu/trusty/mongodb/trusty-proposed

« back to all changes in this revision

Viewing changes to dbtests/queryoptimizertests.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Antonin Kral
  • Date: 2010-01-29 19:48:45 UTC
  • Revision ID: james.westby@ubuntu.com-20100129194845-8wbmkf626fwcavc9
Tags: upstream-1.3.1
Import upstream version 1.3.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
dbtests/queryoptimizertests.cpp
 
1
// queryoptimizertests.cpp : query optimizer unit tests
 
2
//
 
3
 
 
4
/**
 
5
 *    Copyright (C) 2009 10gen Inc.
 
6
 *
 
7
 *    This program is free software: you can redistribute it and/or  modify
 
8
 *    it under the terms of the GNU Affero General Public License, version 3,
 
9
 *    as published by the Free Software Foundation.
 
10
 *
 
11
 *    This program is distributed in the hope that it will be useful,
 
12
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
14
 *    GNU Affero General Public License for more details.
 
15
 *
 
16
 *    You should have received a copy of the GNU Affero General Public License
 
17
 *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
18
 */
 
19
 
 
20
#include "stdafx.h"
 
21
#include "../db/queryoptimizer.h"
 
22
 
 
23
#include "../db/db.h"
 
24
#include "../db/dbhelpers.h"
 
25
#include "../db/instance.h"
 
26
#include "../db/query.h"
 
27
 
 
28
#include "dbtests.h"
 
29
 
 
30
namespace mongo {
 
31
    extern BSONObj id_obj;
 
32
    auto_ptr< QueryResult > runQuery(Message& m, QueryMessage& q ){
 
33
        CurOp op;
 
34
        return runQuery( m , q , op );
 
35
    }
 
36
} // namespace mongo
 
37
 
 
38
namespace QueryOptimizerTests {
 
39
 
 
40
    namespace FieldRangeTests {
 
41
        class Base {
 
42
        public:
 
43
            virtual ~Base() {}
 
44
            void run() {
 
45
                FieldRangeSet s( "ns", query() );
 
46
                checkElt( lower(), s.range( "a" ).min() );
 
47
                checkElt( upper(), s.range( "a" ).max() );
 
48
                ASSERT_EQUALS( lowerInclusive(), s.range( "a" ).minInclusive() );
 
49
                ASSERT_EQUALS( upperInclusive(), s.range( "a" ).maxInclusive() );
 
50
            }
 
51
        protected:
 
52
            virtual BSONObj query() = 0;
 
53
            virtual BSONElement lower() { return minKey.firstElement(); }
 
54
            virtual bool lowerInclusive() { return true; }
 
55
            virtual BSONElement upper() { return maxKey.firstElement(); }
 
56
            virtual bool upperInclusive() { return true; }
 
57
        private:
 
58
            static void checkElt( BSONElement expected, BSONElement actual ) {
 
59
                if ( expected.woCompare( actual, false ) ) {
 
60
                    stringstream ss;
 
61
                    ss << "expected: " << expected << ", got: " << actual;
 
62
                    FAIL( ss.str() );
 
63
                }
 
64
            }
 
65
        };
 
66
        
 
67
 
 
68
        class NumericBase : public Base {
 
69
        public:
 
70
            NumericBase(){
 
71
                o = BSON( "min" << -numeric_limits<double>::max() << "max" << numeric_limits<double>::max() );
 
72
            }
 
73
            
 
74
            virtual BSONElement lower() { return o["min"]; }
 
75
            virtual BSONElement upper() { return o["max"]; }
 
76
        private:
 
77
            BSONObj o;
 
78
        };
 
79
 
 
80
        class Empty : public Base {
 
81
            virtual BSONObj query() { return BSONObj(); }
 
82
        };
 
83
        
 
84
        class Eq : public Base {
 
85
        public:
 
86
            Eq() : o_( BSON( "a" << 1 ) ) {}
 
87
            virtual BSONObj query() { return o_; }
 
88
            virtual BSONElement lower() { return o_.firstElement(); }
 
89
            virtual BSONElement upper() { return o_.firstElement(); }
 
90
            BSONObj o_;
 
91
        };
 
92
 
 
93
        class DupEq : public Eq {
 
94
        public:
 
95
            virtual BSONObj query() { return BSON( "a" << 1 << "b" << 2 << "a" << 1 ); }
 
96
        };        
 
97
 
 
98
        class Lt : public NumericBase {
 
99
        public:
 
100
            Lt() : o_( BSON( "-" << 1 ) ) {}
 
101
            virtual BSONObj query() { return BSON( "a" << LT << 1 ); }
 
102
            virtual BSONElement upper() { return o_.firstElement(); }
 
103
            virtual bool upperInclusive() { return false; }
 
104
            BSONObj o_;
 
105
        };        
 
106
 
 
107
        class Lte : public Lt {
 
108
            virtual BSONObj query() { return BSON( "a" << LTE << 1 ); }            
 
109
            virtual bool upperInclusive() { return true; }
 
110
        };
 
111
        
 
112
        class Gt : public NumericBase {
 
113
        public:
 
114
            Gt() : o_( BSON( "-" << 1 ) ) {}
 
115
            virtual BSONObj query() { return BSON( "a" << GT << 1 ); }
 
116
            virtual BSONElement lower() { return o_.firstElement(); }
 
117
            virtual bool lowerInclusive() { return false; }
 
118
            BSONObj o_;
 
119
        };        
 
120
        
 
121
        class Gte : public Gt {
 
122
            virtual BSONObj query() { return BSON( "a" << GTE << 1 ); }            
 
123
            virtual bool lowerInclusive() { return true; }
 
124
        };
 
125
        
 
126
        class TwoLt : public Lt {
 
127
            virtual BSONObj query() { return BSON( "a" << LT << 1 << LT << 5 ); }                        
 
128
        };
 
129
 
 
130
        class TwoGt : public Gt {
 
131
            virtual BSONObj query() { return BSON( "a" << GT << 0 << GT << 1 ); }                        
 
132
        };        
 
133
        
 
134
        class EqGte : public Eq {
 
135
            virtual BSONObj query() { return BSON( "a" << 1 << "a" << GTE << 1 ); }            
 
136
        };
 
137
 
 
138
        class EqGteInvalid {
 
139
        public:
 
140
            void run() {
 
141
                FieldRangeSet fbs( "ns", BSON( "a" << 1 << "a" << GTE << 2 ) );
 
142
                ASSERT( !fbs.matchPossible() );
 
143
            }
 
144
        };        
 
145
 
 
146
        class Regex : public Base {
 
147
        public:
 
148
            Regex() : o1_( BSON( "" << "abc" ) ), o2_( BSON( "" << "abd" ) ) {}
 
149
            virtual BSONObj query() {
 
150
                BSONObjBuilder b;
 
151
                b.appendRegex( "a", "^abc" );
 
152
                return b.obj();
 
153
            }
 
154
            virtual BSONElement lower() { return o1_.firstElement(); }
 
155
            virtual BSONElement upper() { return o2_.firstElement(); }
 
156
            virtual bool upperInclusive() { return false; }
 
157
            BSONObj o1_, o2_;
 
158
        };        
 
159
 
 
160
        class RegexObj : public Base {
 
161
        public:
 
162
            RegexObj() : o1_( BSON( "" << "abc" ) ), o2_( BSON( "" << "abd" ) ) {}
 
163
            virtual BSONObj query() { return BSON("a" << BSON("$regex" << "^abc")); }
 
164
            virtual BSONElement lower() { return o1_.firstElement(); }
 
165
            virtual BSONElement upper() { return o2_.firstElement(); }
 
166
            virtual bool upperInclusive() { return false; }
 
167
            BSONObj o1_, o2_;
 
168
        };
 
169
        
 
170
        class UnhelpfulRegex : public Base {
 
171
            virtual BSONObj query() {
 
172
                BSONObjBuilder b;
 
173
                b.appendRegex( "a", "abc" );
 
174
                return b.obj();
 
175
            }            
 
176
        };
 
177
        
 
178
        class In : public Base {
 
179
        public:
 
180
            In() : o1_( BSON( "-" << -3 ) ), o2_( BSON( "-" << 44 ) ) {}
 
181
            virtual BSONObj query() {
 
182
                vector< int > vals;
 
183
                vals.push_back( 4 );
 
184
                vals.push_back( 8 );
 
185
                vals.push_back( 44 );
 
186
                vals.push_back( -1 );
 
187
                vals.push_back( -3 );
 
188
                vals.push_back( 0 );
 
189
                BSONObjBuilder bb;
 
190
                bb.append( "$in", vals );
 
191
                BSONObjBuilder b;
 
192
                b.append( "a", bb.done() );
 
193
                return b.obj();
 
194
            }
 
195
            virtual BSONElement lower() { return o1_.firstElement(); }
 
196
            virtual BSONElement upper() { return o2_.firstElement(); }
 
197
            BSONObj o1_, o2_;
 
198
        };
 
199
        
 
200
        class Equality {
 
201
        public:
 
202
            void run() {
 
203
                FieldRangeSet s( "ns", BSON( "a" << 1 ) );
 
204
                ASSERT( s.range( "a" ).equality() );
 
205
                FieldRangeSet s2( "ns", BSON( "a" << GTE << 1 << LTE << 1 ) );
 
206
                ASSERT( s2.range( "a" ).equality() );
 
207
                FieldRangeSet s3( "ns", BSON( "a" << GT << 1 << LTE << 1 ) );
 
208
                ASSERT( !s3.range( "a" ).equality() );
 
209
                FieldRangeSet s4( "ns", BSON( "a" << GTE << 1 << LT << 1 ) );
 
210
                ASSERT( !s4.range( "a" ).equality() );
 
211
                FieldRangeSet s5( "ns", BSON( "a" << GTE << 1 << LTE << 1 << GT << 1 ) );
 
212
                ASSERT( !s5.range( "a" ).equality() );
 
213
                FieldRangeSet s6( "ns", BSON( "a" << GTE << 1 << LTE << 1 << LT << 1 ) );
 
214
                ASSERT( !s6.range( "a" ).equality() );
 
215
            }
 
216
        };
 
217
        
 
218
        class SimplifiedQuery {
 
219
        public:
 
220
            void run() {
 
221
                FieldRangeSet fbs( "ns", BSON( "a" << GT << 1 << GT << 5 << LT << 10 << "b" << 4 << "c" << LT << 4 << LT << 6 << "d" << GTE << 0 << GT << 0 << "e" << GTE << 0 << LTE << 10 ) );
 
222
                BSONObj simple = fbs.simplifiedQuery();
 
223
                cout << "simple: " << simple << endl;
 
224
                ASSERT( !simple.getObjectField( "a" ).woCompare( fromjson( "{$gt:5,$lt:10}" ) ) );
 
225
                ASSERT_EQUALS( 4, simple.getIntField( "b" ) );
 
226
                ASSERT( !simple.getObjectField( "c" ).woCompare( BSON("$gte" << -numeric_limits<double>::max() << "$lt" << 4 ) ) );
 
227
                ASSERT( !simple.getObjectField( "d" ).woCompare( BSON("$gt" << 0 << "$lte" << numeric_limits<double>::max() ) ) );
 
228
                ASSERT( !simple.getObjectField( "e" ).woCompare( fromjson( "{$gte:0,$lte:10}" ) ) );
 
229
            }
 
230
        };
 
231
        
 
232
        class QueryPatternTest {
 
233
        public:
 
234
            void run() {
 
235
                ASSERT( p( BSON( "a" << 1 ) ) == p( BSON( "a" << 1 ) ) );
 
236
                ASSERT( p( BSON( "a" << 1 ) ) == p( BSON( "a" << 5 ) ) );
 
237
                ASSERT( p( BSON( "a" << 1 ) ) != p( BSON( "b" << 1 ) ) );
 
238
                ASSERT( p( BSON( "a" << 1 ) ) != p( BSON( "a" << LTE << 1 ) ) );
 
239
                ASSERT( p( BSON( "a" << 1 ) ) != p( BSON( "a" << 1 << "b" << 2 ) ) );
 
240
                ASSERT( p( BSON( "a" << 1 << "b" << 3 ) ) != p( BSON( "a" << 1 ) ) );
 
241
                ASSERT( p( BSON( "a" << LT << 1 ) ) == p( BSON( "a" << LTE << 5 ) ) );
 
242
                ASSERT( p( BSON( "a" << LT << 1 << GTE << 0 ) ) == p( BSON( "a" << LTE << 5 << GTE << 0 ) ) );
 
243
                ASSERT( p( BSON( "a" << 1 ) ) < p( BSON( "a" << 1 << "b" << 1 ) ) );
 
244
                ASSERT( !( p( BSON( "a" << 1 << "b" << 1 ) ) < p( BSON( "a" << 1 ) ) ) );
 
245
                ASSERT( p( BSON( "a" << 1 ), BSON( "b" << 1 ) ) == p( BSON( "a" << 4 ), BSON( "b" << "a" ) ) );
 
246
                ASSERT( p( BSON( "a" << 1 ), BSON( "b" << 1 ) ) == p( BSON( "a" << 4 ), BSON( "b" << -1 ) ) );
 
247
                ASSERT( p( BSON( "a" << 1 ), BSON( "b" << 1 ) ) != p( BSON( "a" << 4 ), BSON( "c" << 1 ) ) );
 
248
                ASSERT( p( BSON( "a" << 1 ), BSON( "b" << 1 << "c" << -1 ) ) == p( BSON( "a" << 4 ), BSON( "b" << -1 << "c" << 1 ) ) );
 
249
                ASSERT( p( BSON( "a" << 1 ), BSON( "b" << 1 << "c" << 1 ) ) != p( BSON( "a" << 4 ), BSON( "b" << 1 ) ) );
 
250
                ASSERT( p( BSON( "a" << 1 ), BSON( "b" << 1 ) ) != p( BSON( "a" << 4 ), BSON( "b" << 1 << "c" << 1 ) ) );
 
251
            }
 
252
        private:
 
253
            static QueryPattern p( const BSONObj &query, const BSONObj &sort = BSONObj() ) {
 
254
                return FieldRangeSet( "", query ).pattern( sort );
 
255
            }
 
256
        };
 
257
        
 
258
        class NoWhere {
 
259
        public:
 
260
            void run() {
 
261
                ASSERT_EQUALS( 0, FieldRangeSet( "ns", BSON( "$where" << 1 ) ).nNontrivialRanges() );
 
262
            }
 
263
        };
 
264
        
 
265
        class Numeric {
 
266
        public:
 
267
            void run() {
 
268
                FieldRangeSet f( "", BSON( "a" << 1 ) );
 
269
                ASSERT( f.range( "a" ).min().woCompare( BSON( "a" << 2.0 ).firstElement() ) < 0 );
 
270
                ASSERT( f.range( "a" ).min().woCompare( BSON( "a" << 0.0 ).firstElement() ) > 0 );
 
271
            }
 
272
        };
 
273
 
 
274
        class InLowerBound {
 
275
        public:
 
276
            void run() {
 
277
                FieldRangeSet f( "", fromjson( "{a:{$gt:4,$in:[1,2,3,4,5,6]}}" ) );
 
278
                ASSERT( f.range( "a" ).min().woCompare( BSON( "a" << 5.0 ).firstElement(), false ) == 0 );
 
279
                ASSERT( f.range( "a" ).max().woCompare( BSON( "a" << 6.0 ).firstElement(), false ) == 0 );
 
280
            }
 
281
        };
 
282
 
 
283
        class InUpperBound {
 
284
        public:
 
285
            void run() {
 
286
                FieldRangeSet f( "", fromjson( "{a:{$lt:4,$in:[1,2,3,4,5,6]}}" ) );
 
287
                ASSERT( f.range( "a" ).min().woCompare( BSON( "a" << 1.0 ).firstElement(), false ) == 0 );
 
288
                ASSERT( f.range( "a" ).max().woCompare( BSON( "a" << 3.0 ).firstElement(), false ) == 0 );
 
289
            }
 
290
        };
 
291
                
 
292
                class MultiBound {
 
293
                public:
 
294
                        void run() {
 
295
                FieldRangeSet frs1( "", fromjson( "{a:{$in:[1,3,5,7,9]}}" ) );
 
296
                FieldRangeSet frs2( "", fromjson( "{a:{$in:[2,3,5,8,9]}}" ) );
 
297
                                FieldRange fr1 = frs1.range( "a" );
 
298
                                FieldRange fr2 = frs2.range( "a" );
 
299
                                fr1 &= fr2;
 
300
                ASSERT( fr1.min().woCompare( BSON( "a" << 3.0 ).firstElement(), false ) == 0 );
 
301
                ASSERT( fr1.max().woCompare( BSON( "a" << 9.0 ).firstElement(), false ) == 0 );
 
302
                                vector< FieldInterval > intervals = fr1.intervals();
 
303
                                vector< FieldInterval >::const_iterator j = intervals.begin();
 
304
                                double expected[] = { 3, 5, 9 };
 
305
                                for( int i = 0; i < 3; ++i, ++j ) {
 
306
                                        ASSERT_EQUALS( expected[ i ], j->lower_.bound_.number() );
 
307
                                        ASSERT( j->lower_.inclusive_ );
 
308
                                        ASSERT( j->lower_ == j->upper_ );
 
309
                                }
 
310
                                ASSERT( j == intervals.end() );
 
311
                        }
 
312
                };
 
313
        
 
314
    } // namespace FieldRangeTests
 
315
    
 
316
    namespace QueryPlanTests {
 
317
        class Base {
 
318
        public:
 
319
            Base() : indexNum_( 0 ) {
 
320
                setClient( ns() );
 
321
                string err;
 
322
                userCreateNS( ns(), BSONObj(), err, false );
 
323
            }
 
324
            ~Base() {
 
325
                if ( !nsd() )
 
326
                    return;
 
327
                string s( ns() );
 
328
                dropNS( s );
 
329
            }
 
330
        protected:
 
331
            static const char *ns() { return "unittests.QueryPlanTests"; }
 
332
            static NamespaceDetails *nsd() { return nsdetails( ns() ); }
 
333
            IndexDetails *index( const BSONObj &key ) {
 
334
                stringstream ss;
 
335
                ss << indexNum_++;
 
336
                string name = ss.str();
 
337
                client_.resetIndexCache();
 
338
                client_.ensureIndex( ns(), key, false, name.c_str() );
 
339
                NamespaceDetails *d = nsd();
 
340
                for( int i = 0; i < d->nIndexes; ++i ) {
 
341
                    if ( d->idx(i).keyPattern() == key /*indexName() == name*/ || ( d->idx(i).isIdIndex() && IndexDetails::isIdIndexPattern( key ) ) )
 
342
                        return &d->idx(i);
 
343
                }
 
344
                assert( false );
 
345
                return 0;
 
346
            }
 
347
            int indexno( const BSONObj &key ) {
 
348
                return nsd()->idxNo( *index(key) );
 
349
            }
 
350
            BSONObj startKey( const QueryPlan &p ) const {
 
351
                BoundList bl = p.indexBounds();
 
352
                return bl[ 0 ].first.getOwned();
 
353
            }
 
354
            BSONObj endKey( const QueryPlan &p ) const {
 
355
                BoundList bl = p.indexBounds();
 
356
                return bl[ bl.size() - 1 ].second.getOwned();
 
357
            }
 
358
        private:
 
359
            dblock lk_;
 
360
            int indexNum_;
 
361
            static DBDirectClient client_;
 
362
        };
 
363
        DBDirectClient Base::client_;
 
364
        
 
365
        // There's a limit of 10 indexes total, make sure not to exceed this in a given test.
 
366
#define INDEXNO(x) nsd()->idxNo( *this->index( BSON(x) ) )
 
367
#define INDEX(x) this->index( BSON(x) )
 
368
        auto_ptr< FieldRangeSet > FieldRangeSet_GLOBAL;
 
369
#define FBS(x) ( FieldRangeSet_GLOBAL.reset( new FieldRangeSet( ns(), x ) ), *FieldRangeSet_GLOBAL )
 
370
        
 
371
        class NoIndex : public Base {
 
372
        public:
 
373
            void run() {
 
374
                QueryPlan p( nsd(), -1, FBS( BSONObj() ), BSONObj() );
 
375
                ASSERT( !p.optimal() );
 
376
                ASSERT( !p.scanAndOrderRequired() );
 
377
                ASSERT( !p.exactKeyMatch() );
 
378
            }
 
379
        };
 
380
        
 
381
        class SimpleOrder : public Base {
 
382
        public:
 
383
            void run() {
 
384
                BSONObjBuilder b;
 
385
                b.appendMinKey( "" );
 
386
                BSONObj start = b.obj();
 
387
                BSONObjBuilder b2;
 
388
                b2.appendMaxKey( "" );
 
389
                BSONObj end = b2.obj();
 
390
                
 
391
                QueryPlan p( nsd(), INDEXNO( "a" << 1 ), FBS( BSONObj() ), BSON( "a" << 1 ) );
 
392
                ASSERT( !p.scanAndOrderRequired() );
 
393
                ASSERT( !startKey( p ).woCompare( start ) );
 
394
                ASSERT( !endKey( p ).woCompare( end ) );
 
395
                QueryPlan p2( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSONObj() ), BSON( "a" << 1 << "b" << 1 ) );
 
396
                ASSERT( !p2.scanAndOrderRequired() );
 
397
                QueryPlan p3( nsd(), INDEXNO( "a" << 1 ), FBS( BSONObj() ), BSON( "b" << 1 ) );
 
398
                ASSERT( p3.scanAndOrderRequired() );
 
399
                ASSERT( !startKey( p3 ).woCompare( start ) );
 
400
                ASSERT( !endKey( p3 ).woCompare( end ) );
 
401
            }
 
402
        };
 
403
        
 
404
        class MoreIndexThanNeeded : public Base {
 
405
        public:
 
406
            void run() {
 
407
                QueryPlan p( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSONObj() ), BSON( "a" << 1 ) );
 
408
                ASSERT( !p.scanAndOrderRequired() );                
 
409
            }
 
410
        };
 
411
        
 
412
        class IndexSigns : public Base {
 
413
        public:
 
414
            void run() {
 
415
                QueryPlan p( nsd(), INDEXNO( "a" << 1 << "b" << -1 ) , FBS( BSONObj() ), BSON( "a" << 1 << "b" << -1 ) );
 
416
                ASSERT( !p.scanAndOrderRequired() );                
 
417
                ASSERT_EQUALS( 1, p.direction() );
 
418
                QueryPlan p2( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSONObj() ), BSON( "a" << 1 << "b" << -1 ) );
 
419
                ASSERT( p2.scanAndOrderRequired() );                
 
420
                ASSERT_EQUALS( 0, p2.direction() );
 
421
                QueryPlan p3( nsd(), indexno( id_obj ), FBS( BSONObj() ), BSON( "_id" << 1 ) );
 
422
                ASSERT( !p3.scanAndOrderRequired() );
 
423
                ASSERT_EQUALS( 1, p3.direction() );
 
424
            }            
 
425
        };
 
426
        
 
427
        class IndexReverse : public Base {
 
428
        public:
 
429
            void run() {
 
430
                BSONObjBuilder b;
 
431
                b.appendMinKey( "" );
 
432
                b.appendMaxKey( "" );
 
433
                BSONObj start = b.obj();
 
434
                BSONObjBuilder b2;
 
435
                b2.appendMaxKey( "" );
 
436
                b2.appendMinKey( "" );
 
437
                BSONObj end = b2.obj();
 
438
                QueryPlan p( nsd(),  INDEXNO( "a" << -1 << "b" << 1 ),FBS( BSONObj() ), BSON( "a" << 1 << "b" << -1 ) );
 
439
                ASSERT( !p.scanAndOrderRequired() );                
 
440
                ASSERT_EQUALS( -1, p.direction() );
 
441
                ASSERT( !startKey( p ).woCompare( start ) );
 
442
                ASSERT( !endKey( p ).woCompare( end ) );
 
443
                QueryPlan p2( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSONObj() ), BSON( "a" << -1 << "b" << -1 ) );
 
444
                ASSERT( !p2.scanAndOrderRequired() );                
 
445
                ASSERT_EQUALS( -1, p2.direction() );
 
446
                QueryPlan p3( nsd(), INDEXNO( "a" << 1 << "b" << -1 ), FBS( BSONObj() ), BSON( "a" << -1 << "b" << -1 ) );
 
447
                ASSERT( p3.scanAndOrderRequired() );                
 
448
                ASSERT_EQUALS( 0, p3.direction() );
 
449
            }                        
 
450
        };
 
451
 
 
452
        class NoOrder : public Base {
 
453
        public:
 
454
            void run() {
 
455
                BSONObjBuilder b;
 
456
                b.append( "", 3 );
 
457
                b.appendMinKey( "" );
 
458
                BSONObj start = b.obj();
 
459
                BSONObjBuilder b2;
 
460
                b2.append( "", 3 );
 
461
                b2.appendMaxKey( "" );
 
462
                BSONObj end = b2.obj();
 
463
                QueryPlan p( nsd(), INDEXNO( "a" << -1 << "b" << 1 ), FBS( BSON( "a" << 3 ) ), BSONObj() );
 
464
                ASSERT( !p.scanAndOrderRequired() );                
 
465
                ASSERT( !startKey( p ).woCompare( start ) );
 
466
                ASSERT( !endKey( p ).woCompare( end ) );
 
467
                QueryPlan p2( nsd(), INDEXNO( "a" << -1 << "b" << 1 ), FBS( BSON( "a" << 3 ) ), BSONObj() );
 
468
                ASSERT( !p2.scanAndOrderRequired() );                
 
469
                ASSERT( !startKey( p ).woCompare( start ) );
 
470
                ASSERT( !endKey( p ).woCompare( end ) );
 
471
            }            
 
472
        };
 
473
        
 
474
        class EqualWithOrder : public Base {
 
475
        public:
 
476
            void run() {
 
477
                QueryPlan p( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "a" << 4 ) ), BSON( "b" << 1 ) );
 
478
                ASSERT( !p.scanAndOrderRequired() );                
 
479
                QueryPlan p2( nsd(), INDEXNO( "a" << 1 << "b" << 1 << "c" << 1 ), FBS( BSON( "b" << 4 ) ), BSON( "a" << 1 << "c" << 1 ) );
 
480
                ASSERT( !p2.scanAndOrderRequired() );                
 
481
                QueryPlan p3( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "b" << 4 ) ), BSON( "a" << 1 << "c" << 1 ) );
 
482
                ASSERT( p3.scanAndOrderRequired() );                
 
483
            }
 
484
        };
 
485
        
 
486
        class Optimal : public Base {
 
487
        public:
 
488
            void run() {
 
489
                QueryPlan p( nsd(), INDEXNO( "a" << 1 ), FBS( BSONObj() ), BSON( "a" << 1 ) );
 
490
                ASSERT( p.optimal() );
 
491
                QueryPlan p2( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSONObj() ), BSON( "a" << 1 ) );
 
492
                ASSERT( p2.optimal() );
 
493
                QueryPlan p3( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "a" << 1 ) ), BSON( "a" << 1 ) );
 
494
                ASSERT( p3.optimal() );
 
495
                QueryPlan p4( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "b" << 1 ) ), BSON( "a" << 1 ) );
 
496
                ASSERT( !p4.optimal() );
 
497
                QueryPlan p5( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "a" << 1 ) ), BSON( "b" << 1 ) );
 
498
                ASSERT( p5.optimal() );
 
499
                QueryPlan p6( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "b" << 1 ) ), BSON( "b" << 1 ) );
 
500
                ASSERT( !p6.optimal() );
 
501
                QueryPlan p7( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "a" << 1 << "b" << 1 ) ), BSON( "a" << 1 ) );
 
502
                ASSERT( p7.optimal() );
 
503
                QueryPlan p8( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "a" << 1 << "b" << LT << 1 ) ), BSON( "a" << 1 )  );
 
504
                ASSERT( p8.optimal() );
 
505
                QueryPlan p9( nsd(), INDEXNO( "a" << 1 << "b" << 1 << "c" << 1 ), FBS( BSON( "a" << 1 << "b" << LT << 1 ) ), BSON( "a" << 1 ) );
 
506
                ASSERT( p9.optimal() );
 
507
            }
 
508
        };
 
509
        
 
510
        class MoreOptimal : public Base {
 
511
        public:
 
512
            void run() {
 
513
                 QueryPlan p10( nsd(), INDEXNO( "a" << 1 << "b" << 1 << "c" << 1 ), FBS( BSON( "a" << 1 ) ), BSONObj() );
 
514
                 ASSERT( p10.optimal() );
 
515
                 QueryPlan p11( nsd(), INDEXNO( "a" << 1 << "b" << 1 << "c" << 1 ), FBS( BSON( "a" << 1 << "b" << LT << 1 ) ), BSONObj() );
 
516
                 ASSERT( p11.optimal() );
 
517
                 QueryPlan p12( nsd(), INDEXNO( "a" << 1 << "b" << 1 << "c" << 1 ), FBS( BSON( "a" << LT << 1 ) ), BSONObj() );
 
518
                 ASSERT( p12.optimal() );
 
519
                 QueryPlan p13( nsd(), INDEXNO( "a" << 1 << "b" << 1 << "c" << 1 ), FBS( BSON( "a" << LT << 1 ) ), BSON( "a" << 1 ) );
 
520
                 ASSERT( p13.optimal() );
 
521
            }
 
522
        };
 
523
        
 
524
        class KeyMatch : public Base {
 
525
        public:
 
526
            void run() {
 
527
                QueryPlan p( nsd(), INDEXNO( "a" << 1 ), FBS( BSONObj() ), BSON( "a" << 1 ) );
 
528
                ASSERT( !p.exactKeyMatch() );
 
529
                QueryPlan p2( nsd(), INDEXNO( "b" << 1 << "a" << 1 ), FBS( BSONObj() ), BSON( "a" << 1 ) );
 
530
                ASSERT( !p2.exactKeyMatch() );
 
531
                QueryPlan p3( nsd(), INDEXNO( "b" << 1 << "a" << 1 ), FBS( BSON( "b" << "z" ) ), BSON( "a" << 1 ) );
 
532
                ASSERT( !p3.exactKeyMatch() );
 
533
                QueryPlan p4( nsd(), INDEXNO( "b" << 1 << "a" << 1 << "c" << 1 ), FBS( BSON( "c" << "y" << "b" << "z" ) ), BSON( "a" << 1 ) );
 
534
                ASSERT( !p4.exactKeyMatch() );
 
535
                QueryPlan p5( nsd(), INDEXNO( "b" << 1 << "a" << 1 << "c" << 1 ), FBS( BSON( "c" << "y" << "b" << "z" ) ), BSONObj() );
 
536
                ASSERT( !p5.exactKeyMatch() );
 
537
                QueryPlan p6( nsd(), INDEXNO( "b" << 1 << "a" << 1 << "c" << 1 ), FBS( BSON( "c" << LT << "y" << "b" << GT << "z" ) ), BSONObj() );
 
538
                ASSERT( !p6.exactKeyMatch() );
 
539
                QueryPlan p7( nsd(), INDEXNO( "b" << 1 ), FBS( BSONObj() ), BSON( "a" << 1 ) );
 
540
                ASSERT( !p7.exactKeyMatch() );
 
541
                QueryPlan p8( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "b" << "y" << "a" << "z" ) ), BSONObj() );
 
542
                ASSERT( p8.exactKeyMatch() );
 
543
                QueryPlan p9( nsd(), INDEXNO( "a" << 1 ), FBS( BSON( "a" << "z" ) ), BSON( "a" << 1 ) );
 
544
                ASSERT( p9.exactKeyMatch() );
 
545
            }
 
546
        };
 
547
        
 
548
        class MoreKeyMatch : public Base {
 
549
        public:
 
550
            void run() {
 
551
                QueryPlan p( nsd(), INDEXNO( "a" << 1 ), FBS( BSON( "a" << "r" << "b" << NE << "q" ) ), BSON( "a" << 1 ) );
 
552
                ASSERT( !p.exactKeyMatch() );                
 
553
            }
 
554
        };
 
555
        
 
556
        class ExactKeyQueryTypes : public Base {
 
557
        public:
 
558
            void run() {
 
559
                QueryPlan p( nsd(), INDEXNO( "a" << 1 ), FBS( BSON( "a" << "b" ) ), BSONObj() );
 
560
                ASSERT( p.exactKeyMatch() );
 
561
                QueryPlan p2( nsd(), INDEXNO( "a" << 1 ), FBS( BSON( "a" << 4 ) ), BSONObj() );
 
562
                ASSERT( !p2.exactKeyMatch() );
 
563
                QueryPlan p3( nsd(), INDEXNO( "a" << 1 ), FBS( BSON( "a" << BSON( "c" << "d" ) ) ), BSONObj() );
 
564
                ASSERT( !p3.exactKeyMatch() );
 
565
                BSONObjBuilder b;
 
566
                b.appendRegex( "a", "^ddd" );
 
567
                QueryPlan p4( nsd(), INDEXNO( "a" << 1 ), FBS( b.obj() ), BSONObj() );
 
568
                ASSERT( !p4.exactKeyMatch() );
 
569
                QueryPlan p5( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "a" << "z" << "b" << 4 ) ), BSONObj() );
 
570
                ASSERT( !p5.exactKeyMatch() );
 
571
            }
 
572
        };
 
573
        
 
574
        class Unhelpful : public Base {
 
575
        public:
 
576
            void run() {
 
577
                QueryPlan p( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "b" << 1 ) ), BSONObj() );
 
578
                ASSERT( !p.range( "a" ).nontrivial() );
 
579
                ASSERT( p.unhelpful() );
 
580
                QueryPlan p2( nsd(), INDEXNO( "a" << 1 << "b" << 1 ), FBS( BSON( "b" << 1 << "c" << 1 ) ), BSON( "a" << 1 ) );
 
581
                ASSERT( !p2.scanAndOrderRequired() );
 
582
                ASSERT( !p2.range( "a" ).nontrivial() );
 
583
                ASSERT( !p2.unhelpful() );
 
584
                QueryPlan p3( nsd(), INDEXNO( "b" << 1 ), FBS( BSON( "b" << 1 << "c" << 1 ) ), BSONObj() );
 
585
                ASSERT( p3.range( "b" ).nontrivial() );
 
586
                ASSERT( !p3.unhelpful() );
 
587
                QueryPlan p4( nsd(), INDEXNO( "b" << 1 << "c" << 1 ), FBS( BSON( "c" << 1 << "d" << 1 ) ), BSONObj() );
 
588
                ASSERT( !p4.range( "b" ).nontrivial() );
 
589
                ASSERT( p4.unhelpful() );
 
590
            }
 
591
        };
 
592
        
 
593
    } // namespace QueryPlanTests
 
594
 
 
595
    namespace QueryPlanSetTests {
 
596
        class Base {
 
597
        public:
 
598
            Base() {
 
599
                setClient( ns() );
 
600
                string err;
 
601
                userCreateNS( ns(), BSONObj(), err, false );
 
602
            }
 
603
            ~Base() {
 
604
                if ( !nsd() )
 
605
                    return;
 
606
                NamespaceDetailsTransient::_get( ns() ).clearQueryCache();
 
607
                string s( ns() );
 
608
                dropNS( s );
 
609
            }
 
610
            static void assembleRequest( const string &ns, BSONObj query, int nToReturn, int nToSkip, BSONObj *fieldsToReturn, int queryOptions, Message &toSend ) {
 
611
                // see query.h for the protocol we are using here.
 
612
                BufBuilder b;
 
613
                int opts = queryOptions;
 
614
                b.append(opts);
 
615
                b.append(ns.c_str());
 
616
                b.append(nToSkip);
 
617
                b.append(nToReturn);
 
618
                query.appendSelfToBufBuilder(b);
 
619
                if ( fieldsToReturn )
 
620
                    fieldsToReturn->appendSelfToBufBuilder(b);
 
621
                toSend.setData(dbQuery, b.buf(), b.len());
 
622
            }            
 
623
        protected:
 
624
            static const char *ns() { return "unittests.QueryPlanSetTests"; }
 
625
            static NamespaceDetails *nsd() { return nsdetails( ns() ); }
 
626
        private:
 
627
            dblock lk_;
 
628
        };
 
629
        
 
630
        class NoIndexes : public Base {
 
631
        public:
 
632
            void run() {
 
633
                QueryPlanSet s( ns(), BSON( "a" << 4 ), BSON( "b" << 1 ) );
 
634
                ASSERT_EQUALS( 1, s.nPlans() );
 
635
            }
 
636
        };
 
637
        
 
638
        class Optimal : public Base {
 
639
        public:
 
640
            void run() {
 
641
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
642
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "b_2" );
 
643
                QueryPlanSet s( ns(), BSON( "a" << 4 ), BSONObj() );
 
644
                ASSERT_EQUALS( 1, s.nPlans() );                
 
645
            }
 
646
        };
 
647
 
 
648
        class NoOptimal : public Base {
 
649
        public:
 
650
            void run() {
 
651
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
652
                Helpers::ensureIndex( ns(), BSON( "b" << 1 ), false, "b_1" );
 
653
                QueryPlanSet s( ns(), BSON( "a" << 4 ), BSON( "b" << 1 ) );
 
654
                ASSERT_EQUALS( 3, s.nPlans() );
 
655
            }
 
656
        };
 
657
 
 
658
        class NoSpec : public Base {
 
659
        public:
 
660
            void run() {
 
661
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
662
                Helpers::ensureIndex( ns(), BSON( "b" << 1 ), false, "b_1" );
 
663
                QueryPlanSet s( ns(), BSONObj(), BSONObj() );
 
664
                ASSERT_EQUALS( 1, s.nPlans() );
 
665
            }
 
666
        };
 
667
        
 
668
        class HintSpec : public Base {
 
669
        public:
 
670
            void run() {
 
671
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
672
                Helpers::ensureIndex( ns(), BSON( "b" << 1 ), false, "b_1" );
 
673
                BSONObj b = BSON( "hint" << BSON( "a" << 1 ) );
 
674
                BSONElement e = b.firstElement();
 
675
                QueryPlanSet s( ns(), BSON( "a" << 1 ), BSON( "b" << 1 ), &e );
 
676
                ASSERT_EQUALS( 1, s.nPlans() );                
 
677
            }
 
678
        };
 
679
 
 
680
        class HintName : public Base {
 
681
        public:
 
682
            void run() {
 
683
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
684
                Helpers::ensureIndex( ns(), BSON( "b" << 1 ), false, "b_1" );
 
685
                BSONObj b = BSON( "hint" << "a_1" );
 
686
                BSONElement e = b.firstElement();
 
687
                QueryPlanSet s( ns(), BSON( "a" << 1 ), BSON( "b" << 1 ), &e );
 
688
                ASSERT_EQUALS( 1, s.nPlans() );                
 
689
            }
 
690
        };
 
691
        
 
692
        class NaturalHint : public Base {
 
693
        public:
 
694
            void run() {
 
695
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
696
                Helpers::ensureIndex( ns(), BSON( "b" << 1 ), false, "b_1" );
 
697
                BSONObj b = BSON( "hint" << BSON( "$natural" << 1 ) );
 
698
                BSONElement e = b.firstElement();
 
699
                QueryPlanSet s( ns(), BSON( "a" << 1 ), BSON( "b" << 1 ), &e );
 
700
                ASSERT_EQUALS( 1, s.nPlans() );                
 
701
            }
 
702
        };
 
703
 
 
704
        class NaturalSort : public Base {
 
705
        public:
 
706
            void run() {
 
707
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
708
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "b_2" );
 
709
                QueryPlanSet s( ns(), BSON( "a" << 1 ), BSON( "$natural" << 1 ) );
 
710
                ASSERT_EQUALS( 1, s.nPlans() );
 
711
            }
 
712
        };
 
713
 
 
714
        class BadHint : public Base {
 
715
        public:
 
716
            void run() {
 
717
                BSONObj b = BSON( "hint" << "a_1" );
 
718
                BSONElement e = b.firstElement();
 
719
                ASSERT_EXCEPTION( QueryPlanSet s( ns(), BSON( "a" << 1 ), BSON( "b" << 1 ), &e ),
 
720
                                 AssertionException );
 
721
            }
 
722
        };
 
723
        
 
724
        class Count : public Base {
 
725
        public:
 
726
            void run() {
 
727
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
728
                Helpers::ensureIndex( ns(), BSON( "b" << 1 ), false, "b_1" );
 
729
                string err;
 
730
                ASSERT_EQUALS( 0, runCount( ns(), BSON( "query" << BSON( "a" << 4 ) ), err ) );
 
731
                BSONObj one = BSON( "a" << 1 );
 
732
                BSONObj fourA = BSON( "a" << 4 );
 
733
                BSONObj fourB = BSON( "a" << 4 );
 
734
                theDataFileMgr.insert( ns(), one );
 
735
                ASSERT_EQUALS( 0, runCount( ns(), BSON( "query" << BSON( "a" << 4 ) ), err ) );
 
736
                theDataFileMgr.insert( ns(), fourA );
 
737
                ASSERT_EQUALS( 1, runCount( ns(), BSON( "query" << BSON( "a" << 4 ) ), err ) );
 
738
                theDataFileMgr.insert( ns(), fourB );
 
739
                ASSERT_EQUALS( 2, runCount( ns(), BSON( "query" << BSON( "a" << 4 ) ), err ) );
 
740
                ASSERT_EQUALS( 3, runCount( ns(), BSON( "query" << BSONObj() ), err ) );
 
741
                ASSERT_EQUALS( 3, runCount( ns(), BSON( "query" << BSON( "a" << GT << 0 ) ), err ) );
 
742
                // missing ns
 
743
                ASSERT_EQUALS( -1, runCount( "unittests.missingNS", BSONObj(), err ) );
 
744
                // impossible match
 
745
                ASSERT_EQUALS( 0, runCount( ns(), BSON( "query" << BSON( "a" << GT << 0 << LT << -1 ) ), err ) );
 
746
            }
 
747
        };
 
748
        
 
749
        class QueryMissingNs : public Base {
 
750
        public:
 
751
            void run() {
 
752
                Message m;
 
753
                assembleRequest( "unittests.missingNS", BSONObj(), 0, 0, 0, 0, m );
 
754
                stringstream ss;
 
755
 
 
756
                DbMessage d(m);
 
757
                QueryMessage q(d);
 
758
                ASSERT_EQUALS( 0, runQuery( m, q)->nReturned );
 
759
            }
 
760
        };
 
761
        
 
762
        class UnhelpfulIndex : public Base {
 
763
        public:
 
764
            void run() {
 
765
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
766
                Helpers::ensureIndex( ns(), BSON( "b" << 1 ), false, "b_1" );
 
767
                QueryPlanSet s( ns(), BSON( "a" << 1 << "c" << 2 ), BSONObj() );
 
768
                ASSERT_EQUALS( 2, s.nPlans() );                
 
769
            }
 
770
        };        
 
771
        
 
772
        class SingleException : public Base {
 
773
        public:
 
774
            void run() {
 
775
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
776
                Helpers::ensureIndex( ns(), BSON( "b" << 1 ), false, "b_1" );
 
777
                QueryPlanSet s( ns(), BSON( "a" << 4 ), BSON( "b" << 1 ) );
 
778
                ASSERT_EQUALS( 3, s.nPlans() );
 
779
                bool threw = false;
 
780
                auto_ptr< TestOp > t( new TestOp( true, threw ) );
 
781
                boost::shared_ptr< TestOp > done = s.runOp( *t );
 
782
                ASSERT( threw );
 
783
                ASSERT( done->complete() );
 
784
                ASSERT( done->exceptionMessage().empty() );
 
785
                ASSERT( !done->error() );
 
786
            }
 
787
        private:
 
788
            class TestOp : public QueryOp {
 
789
            public:
 
790
                TestOp( bool iThrow, bool &threw ) : iThrow_( iThrow ), threw_( threw ), i_(), youThrow_( false ) {}
 
791
                virtual void init() {}
 
792
                virtual void next() {
 
793
                    if ( iThrow_ )
 
794
                        threw_ = true;
 
795
                    massert( 10408 ,  "throw", !iThrow_ );
 
796
                    if ( ++i_ > 10 )
 
797
                        setComplete();
 
798
                }
 
799
                virtual QueryOp *clone() const {
 
800
                    QueryOp *op = new TestOp( youThrow_, threw_ );
 
801
                    youThrow_ = !youThrow_;
 
802
                    return op;
 
803
                }
 
804
                virtual bool mayRecordPlan() const { return true; }
 
805
            private:
 
806
                bool iThrow_;
 
807
                bool &threw_;
 
808
                int i_;
 
809
                mutable bool youThrow_;
 
810
            };
 
811
        };
 
812
        
 
813
        class AllException : public Base {
 
814
        public:
 
815
            void run() {
 
816
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
817
                Helpers::ensureIndex( ns(), BSON( "b" << 1 ), false, "b_1" );
 
818
                QueryPlanSet s( ns(), BSON( "a" << 4 ), BSON( "b" << 1 ) );
 
819
                ASSERT_EQUALS( 3, s.nPlans() );
 
820
                auto_ptr< TestOp > t( new TestOp() );
 
821
                boost::shared_ptr< TestOp > done = s.runOp( *t );
 
822
                ASSERT( !done->complete() );
 
823
                ASSERT_EQUALS( "throw", done->exceptionMessage() );
 
824
                ASSERT( done->error() );
 
825
            }
 
826
        private:
 
827
            class TestOp : public QueryOp {
 
828
            public:
 
829
                virtual void init() {}
 
830
                virtual void next() {
 
831
                    massert( 10409 ,  "throw", false );
 
832
                }
 
833
                virtual QueryOp *clone() const {
 
834
                    return new TestOp();
 
835
                }
 
836
                virtual bool mayRecordPlan() const { return true; }
 
837
            };
 
838
        };
 
839
        
 
840
        class SaveGoodIndex : public Base {
 
841
        public:
 
842
            void run() {
 
843
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
844
                Helpers::ensureIndex( ns(), BSON( "b" << 1 ), false, "b_1" );
 
845
                nPlans( 3 );
 
846
                runQuery();
 
847
                nPlans( 1 );
 
848
                nPlans( 1 );
 
849
                Helpers::ensureIndex( ns(), BSON( "c" << 1 ), false, "c_1" );
 
850
                nPlans( 3 );
 
851
                runQuery();
 
852
                nPlans( 1 );
 
853
                
 
854
                {
 
855
                    DBDirectClient client;
 
856
                    for( int i = 0; i < 34; ++i ) {
 
857
                        client.insert( ns(), BSON( "i" << i ) );
 
858
                        client.update( ns(), QUERY( "i" << i ), BSON( "i" << i + 1 ) );
 
859
                        client.remove( ns(), BSON( "i" << i + 1 ) );
 
860
                    }
 
861
                }
 
862
                nPlans( 3 );
 
863
                
 
864
                QueryPlanSet s( ns(), BSON( "a" << 4 ), BSON( "b" << 1 ) );
 
865
                NoRecordTestOp original;
 
866
                s.runOp( original );
 
867
                nPlans( 3 );
 
868
 
 
869
                BSONObj hint = fromjson( "{hint:{$natural:1}}" );
 
870
                BSONElement hintElt = hint.firstElement();
 
871
                QueryPlanSet s2( ns(), BSON( "a" << 4 ), BSON( "b" << 1 ), &hintElt );
 
872
                TestOp newOriginal;
 
873
                s2.runOp( newOriginal );
 
874
                nPlans( 3 );
 
875
 
 
876
                QueryPlanSet s3( ns(), BSON( "a" << 4 ), BSON( "b" << 1 << "c" << 1 ) );
 
877
                TestOp newerOriginal;
 
878
                s3.runOp( newerOriginal );
 
879
                nPlans( 3 );                
 
880
                
 
881
                runQuery();
 
882
                nPlans( 1 );
 
883
            }
 
884
        private:
 
885
            void nPlans( int n ) {
 
886
                QueryPlanSet s( ns(), BSON( "a" << 4 ), BSON( "b" << 1 ) );
 
887
                ASSERT_EQUALS( n, s.nPlans() );                
 
888
            }
 
889
            void runQuery() {
 
890
                QueryPlanSet s( ns(), BSON( "a" << 4 ), BSON( "b" << 1 ) );
 
891
                TestOp original;
 
892
                s.runOp( original );
 
893
            }
 
894
            class TestOp : public QueryOp {
 
895
            public:
 
896
                virtual void init() {}
 
897
                virtual void next() {
 
898
                    setComplete();
 
899
                }
 
900
                virtual QueryOp *clone() const {
 
901
                    return new TestOp();
 
902
                }
 
903
                virtual bool mayRecordPlan() const { return true; }
 
904
            };
 
905
            class NoRecordTestOp : public TestOp {
 
906
                virtual bool mayRecordPlan() const { return false; }
 
907
                virtual QueryOp *clone() const { return new NoRecordTestOp(); }
 
908
            };
 
909
        };        
 
910
        
 
911
        class TryAllPlansOnErr : public Base {
 
912
        public:
 
913
            void run() {
 
914
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
915
 
 
916
                QueryPlanSet s( ns(), BSON( "a" << 4 ), BSON( "b" << 1 ) );
 
917
                ScanOnlyTestOp op;
 
918
                s.runOp( op );
 
919
                ASSERT( fromjson( "{$natural:1}" ).woCompare( NamespaceDetailsTransient::_get( ns() ).indexForPattern( s.fbs().pattern( BSON( "b" << 1 ) ) ) ) == 0 );
 
920
                ASSERT_EQUALS( 1, NamespaceDetailsTransient::_get( ns() ).nScannedForPattern( s.fbs().pattern( BSON( "b" << 1 ) ) ) );
 
921
                
 
922
                QueryPlanSet s2( ns(), BSON( "a" << 4 ), BSON( "b" << 1 ) );
 
923
                TestOp op2;
 
924
                ASSERT( s2.runOp( op2 )->complete() );
 
925
            }
 
926
        private:
 
927
            class TestOp : public QueryOp {
 
928
            public:
 
929
                virtual void init() {}
 
930
                virtual void next() {
 
931
                    if ( qp().indexKey().firstElement().fieldName() == string( "$natural" ) )
 
932
                        massert( 10410 ,  "throw", false );
 
933
                    setComplete();
 
934
                }
 
935
                virtual QueryOp *clone() const {
 
936
                    return new TestOp();
 
937
                }
 
938
                virtual bool mayRecordPlan() const { return true; }
 
939
            };
 
940
            class ScanOnlyTestOp : public TestOp {
 
941
                virtual void next() {
 
942
                    if ( qp().indexKey().firstElement().fieldName() == string( "$natural" ) )
 
943
                        setComplete();
 
944
                    massert( 10411 ,  "throw", false );
 
945
                }
 
946
                virtual QueryOp *clone() const {
 
947
                    return new ScanOnlyTestOp();
 
948
                }
 
949
            };
 
950
        };
 
951
        
 
952
        class FindOne : public Base {
 
953
        public:
 
954
            void run() {
 
955
                BSONObj one = BSON( "a" << 1 );
 
956
                theDataFileMgr.insert( ns(), one );
 
957
                BSONObj result;
 
958
                ASSERT( Helpers::findOne( ns(), BSON( "a" << 1 ), result ) );
 
959
                ASSERT_EXCEPTION( Helpers::findOne( ns(), BSON( "a" << 1 ), result, true ), AssertionException );                
 
960
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
961
                ASSERT( Helpers::findOne( ns(), BSON( "a" << 1 ), result, true ) );                
 
962
            }
 
963
        };
 
964
        
 
965
        class Delete : public Base {
 
966
        public:
 
967
            void run() {
 
968
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
969
                for( int i = 0; i < 200; ++i ) {
 
970
                    BSONObj two = BSON( "a" << 2 );
 
971
                    theDataFileMgr.insert( ns(), two );
 
972
                }
 
973
                BSONObj one = BSON( "a" << 1 );
 
974
                theDataFileMgr.insert( ns(), one );
 
975
                deleteObjects( ns(), BSON( "a" << 1 ), false );
 
976
                ASSERT( BSON( "a" << 1 ).woCompare( NamespaceDetailsTransient::_get( ns() ).indexForPattern( FieldRangeSet( ns(), BSON( "a" << 1 ) ).pattern() ) ) == 0 );
 
977
                ASSERT_EQUALS( 2, NamespaceDetailsTransient::_get( ns() ).nScannedForPattern( FieldRangeSet( ns(), BSON( "a" << 1 ) ).pattern() ) );
 
978
            }
 
979
        };
 
980
        
 
981
        class DeleteOneScan : public Base {
 
982
        public:
 
983
            void run() {
 
984
                Helpers::ensureIndex( ns(), BSON( "_id" << 1 ), false, "_id_1" );
 
985
                BSONObj one = BSON( "_id" << 3 << "a" << 1 );
 
986
                BSONObj two = BSON( "_id" << 2 << "a" << 1 );
 
987
                BSONObj three = BSON( "_id" << 1 << "a" << -1 );
 
988
                theDataFileMgr.insert( ns(), one );
 
989
                theDataFileMgr.insert( ns(), two );
 
990
                theDataFileMgr.insert( ns(), three );
 
991
                deleteObjects( ns(), BSON( "_id" << GT << 0 << "a" << GT << 0 ), true );
 
992
                for( auto_ptr< Cursor > c = theDataFileMgr.findAll( ns() ); c->ok(); c->advance() )
 
993
                    ASSERT( 3 != c->current().getIntField( "_id" ) );
 
994
            }
 
995
        };
 
996
 
 
997
        class DeleteOneIndex : public Base {
 
998
        public:
 
999
            void run() {
 
1000
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a" );
 
1001
                BSONObj one = BSON( "a" << 2 << "_id" << 0 );
 
1002
                BSONObj two = BSON( "a" << 1 << "_id" << 1 );
 
1003
                BSONObj three = BSON( "a" << 0 << "_id" << 2 );
 
1004
                theDataFileMgr.insert( ns(), one );
 
1005
                theDataFileMgr.insert( ns(), two );
 
1006
                theDataFileMgr.insert( ns(), three );
 
1007
                deleteObjects( ns(), BSON( "a" << GTE << 0 << "_id" << GT << 0 ), true );
 
1008
                for( auto_ptr< Cursor > c = theDataFileMgr.findAll( ns() ); c->ok(); c->advance() )
 
1009
                    ASSERT( 2 != c->current().getIntField( "_id" ) );
 
1010
            }
 
1011
        };
 
1012
 
 
1013
        class TryOtherPlansBeforeFinish : public Base {
 
1014
        public:
 
1015
            void run() {
 
1016
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
1017
                for( int i = 0; i < 100; ++i ) {
 
1018
                    for( int j = 0; j < 2; ++j ) {
 
1019
                        BSONObj temp = BSON( "a" << 100 - i - 1 << "b" << i );
 
1020
                        theDataFileMgr.insert( ns(), temp );
 
1021
                    }
 
1022
                }
 
1023
                Message m;
 
1024
                // Need to return at least 2 records to cause plan to be recorded.
 
1025
                assembleRequest( ns(), QUERY( "b" << 0 << "a" << GTE << 0 ).obj, 2, 0, 0, 0, m );
 
1026
                stringstream ss;
 
1027
                {
 
1028
                    DbMessage d(m);
 
1029
                    QueryMessage q(d);
 
1030
                    runQuery( m, q);
 
1031
                }
 
1032
                ASSERT( BSON( "$natural" << 1 ).woCompare( NamespaceDetailsTransient::_get( ns() ).indexForPattern( FieldRangeSet( ns(), BSON( "b" << 0 << "a" << GTE << 0 ) ).pattern() ) ) == 0 );
 
1033
                
 
1034
                Message m2;
 
1035
                assembleRequest( ns(), QUERY( "b" << 99 << "a" << GTE << 0 ).obj, 2, 0, 0, 0, m2 );
 
1036
                {
 
1037
                    DbMessage d(m2);
 
1038
                    QueryMessage q(d);
 
1039
                    runQuery( m2, q);
 
1040
                }
 
1041
                ASSERT( BSON( "a" << 1 ).woCompare( NamespaceDetailsTransient::_get( ns() ).indexForPattern( FieldRangeSet( ns(), BSON( "b" << 0 << "a" << GTE << 0 ) ).pattern() ) ) == 0 );                
 
1042
                ASSERT_EQUALS( 2, NamespaceDetailsTransient::_get( ns() ).nScannedForPattern( FieldRangeSet( ns(), BSON( "b" << 0 << "a" << GTE << 0 ) ).pattern() ) );
 
1043
            }
 
1044
        };
 
1045
        
 
1046
        class InQueryIntervals : public Base {
 
1047
        public:
 
1048
            void run() {
 
1049
                Helpers::ensureIndex( ns(), BSON( "a" << 1 ), false, "a_1" );
 
1050
                for( int i = 0; i < 10; ++i ) {
 
1051
                    BSONObj temp = BSON( "a" << i );
 
1052
                    theDataFileMgr.insert( ns(), temp );
 
1053
                }
 
1054
                BSONObj hint = fromjson( "{$hint:{a:1}}" );
 
1055
                BSONElement hintElt = hint.firstElement();
 
1056
                QueryPlanSet s( ns(), fromjson( "{a:{$in:[2,3,6,9,11]}}" ), BSONObj(), &hintElt );
 
1057
                QueryPlan qp( nsd(), 1, s.fbs(), BSONObj() );
 
1058
                auto_ptr< Cursor > c = qp.newCursor();
 
1059
                double expected[] = { 2, 3, 6, 9 };
 
1060
                for( int i = 0; i < 4; ++i, c->advance() ) {
 
1061
                    ASSERT_EQUALS( expected[ i ], c->current().getField( "a" ).number() );
 
1062
                }
 
1063
                ASSERT( !c->ok() );
 
1064
                
 
1065
                // now check reverse
 
1066
                {
 
1067
                    QueryPlanSet s( ns(), fromjson( "{a:{$in:[2,3,6,9,11]}}" ), BSON( "a" << -1 ), &hintElt );
 
1068
                    QueryPlan qp( nsd(), 1, s.fbs(), BSON( "a" << -1 ) );
 
1069
                    auto_ptr< Cursor > c = qp.newCursor();
 
1070
                    double expected[] = { 9, 6, 3, 2 };
 
1071
                    for( int i = 0; i < 4; ++i, c->advance() ) {
 
1072
                        ASSERT_EQUALS( expected[ i ], c->current().getField( "a" ).number() );
 
1073
                    }
 
1074
                    ASSERT( !c->ok() );                    
 
1075
                }
 
1076
            }
 
1077
        };
 
1078
        
 
1079
        class EqualityThenIn : public Base {
 
1080
        public:
 
1081
            void run() {
 
1082
                Helpers::ensureIndex( ns(), BSON( "a" << 1 << "b" << 1 ), false, "a_1_b_1" );
 
1083
                for( int i = 0; i < 10; ++i ) {
 
1084
                    BSONObj temp = BSON( "a" << 5 << "b" << i );
 
1085
                    theDataFileMgr.insert( ns(), temp );
 
1086
                }
 
1087
                BSONObj hint = fromjson( "{$hint:{a:1,b:1}}" );
 
1088
                BSONElement hintElt = hint.firstElement();
 
1089
                QueryPlanSet s( ns(), fromjson( "{a:5,b:{$in:[2,3,6,9,11]}}" ), BSONObj(), &hintElt );
 
1090
                QueryPlan qp( nsd(), 1, s.fbs(), BSONObj() );
 
1091
                auto_ptr< Cursor > c = qp.newCursor();
 
1092
                double expected[] = { 2, 3, 6, 9 };
 
1093
                for( int i = 0; i < 4; ++i, c->advance() ) {
 
1094
                    ASSERT_EQUALS( expected[ i ], c->current().getField( "b" ).number() );
 
1095
                }
 
1096
                ASSERT( !c->ok() );
 
1097
            }
 
1098
        };
 
1099
        
 
1100
        class NotEqualityThenIn : public Base {
 
1101
        public:
 
1102
            void run() {
 
1103
                Helpers::ensureIndex( ns(), BSON( "a" << 1 << "b" << 1 ), false, "a_1_b_1" );
 
1104
                for( int i = 0; i < 10; ++i ) {
 
1105
                    BSONObj temp = BSON( "a" << 5 << "b" << i );
 
1106
                    theDataFileMgr.insert( ns(), temp );
 
1107
                }
 
1108
                BSONObj hint = fromjson( "{$hint:{a:1,b:1}}" );
 
1109
                BSONElement hintElt = hint.firstElement();
 
1110
                QueryPlanSet s( ns(), fromjson( "{a:{$gte:5},b:{$in:[2,3,6,9,11]}}" ), BSONObj(), &hintElt );
 
1111
                QueryPlan qp( nsd(), 1, s.fbs(), BSONObj() );
 
1112
                auto_ptr< Cursor > c = qp.newCursor();
 
1113
                for( int i = 2; i < 10; ++i, c->advance() ) {
 
1114
                    ASSERT_EQUALS( i, c->current().getField( "b" ).number() );
 
1115
                }
 
1116
                ASSERT( !c->ok() );
 
1117
            }
 
1118
        };
 
1119
 
 
1120
    } // namespace QueryPlanSetTests
 
1121
    
 
1122
    class All : public Suite {
 
1123
    public:
 
1124
        All() : Suite( "queryoptimizer" ){}
 
1125
        
 
1126
        void setupTests(){
 
1127
            add< FieldRangeTests::Empty >();
 
1128
            add< FieldRangeTests::Eq >();
 
1129
            add< FieldRangeTests::DupEq >();
 
1130
            add< FieldRangeTests::Lt >();
 
1131
            add< FieldRangeTests::Lte >();
 
1132
            add< FieldRangeTests::Gt >();
 
1133
            add< FieldRangeTests::Gte >();
 
1134
            add< FieldRangeTests::TwoLt >();
 
1135
            add< FieldRangeTests::TwoGt >();
 
1136
            add< FieldRangeTests::EqGte >();
 
1137
            add< FieldRangeTests::EqGteInvalid >();
 
1138
            add< FieldRangeTests::Regex >();
 
1139
            add< FieldRangeTests::RegexObj >();
 
1140
            add< FieldRangeTests::UnhelpfulRegex >();
 
1141
            add< FieldRangeTests::In >();
 
1142
            add< FieldRangeTests::Equality >();
 
1143
            add< FieldRangeTests::SimplifiedQuery >();
 
1144
            add< FieldRangeTests::QueryPatternTest >();
 
1145
            add< FieldRangeTests::NoWhere >();
 
1146
            add< FieldRangeTests::Numeric >();
 
1147
            add< FieldRangeTests::InLowerBound >();
 
1148
            add< FieldRangeTests::InUpperBound >();
 
1149
            add< FieldRangeTests::MultiBound >();
 
1150
            add< QueryPlanTests::NoIndex >();
 
1151
            add< QueryPlanTests::SimpleOrder >();
 
1152
            add< QueryPlanTests::MoreIndexThanNeeded >();
 
1153
            add< QueryPlanTests::IndexSigns >();
 
1154
            add< QueryPlanTests::IndexReverse >();
 
1155
            add< QueryPlanTests::NoOrder >();
 
1156
            add< QueryPlanTests::EqualWithOrder >();
 
1157
            add< QueryPlanTests::Optimal >();
 
1158
            add< QueryPlanTests::MoreOptimal >();
 
1159
            add< QueryPlanTests::KeyMatch >();
 
1160
            add< QueryPlanTests::MoreKeyMatch >();
 
1161
            add< QueryPlanTests::ExactKeyQueryTypes >();
 
1162
            add< QueryPlanTests::Unhelpful >();
 
1163
            add< QueryPlanSetTests::NoIndexes >();
 
1164
            add< QueryPlanSetTests::Optimal >();
 
1165
            add< QueryPlanSetTests::NoOptimal >();
 
1166
            add< QueryPlanSetTests::NoSpec >();
 
1167
            add< QueryPlanSetTests::HintSpec >();
 
1168
            add< QueryPlanSetTests::HintName >();
 
1169
            add< QueryPlanSetTests::NaturalHint >();
 
1170
            add< QueryPlanSetTests::NaturalSort >();
 
1171
            add< QueryPlanSetTests::BadHint >();
 
1172
            add< QueryPlanSetTests::Count >();
 
1173
            add< QueryPlanSetTests::QueryMissingNs >();
 
1174
            add< QueryPlanSetTests::UnhelpfulIndex >();
 
1175
            add< QueryPlanSetTests::SingleException >();
 
1176
            add< QueryPlanSetTests::AllException >();
 
1177
            add< QueryPlanSetTests::SaveGoodIndex >();
 
1178
            add< QueryPlanSetTests::TryAllPlansOnErr >();
 
1179
            add< QueryPlanSetTests::FindOne >();
 
1180
            add< QueryPlanSetTests::Delete >();
 
1181
            add< QueryPlanSetTests::DeleteOneScan >();
 
1182
            add< QueryPlanSetTests::DeleteOneIndex >();
 
1183
            add< QueryPlanSetTests::TryOtherPlansBeforeFinish >();
 
1184
            add< QueryPlanSetTests::InQueryIntervals >();
 
1185
            add< QueryPlanSetTests::EqualityThenIn >();
 
1186
            add< QueryPlanSetTests::NotEqualityThenIn >();
 
1187
        }
 
1188
    } myall;
 
1189
    
 
1190
} // namespace QueryOptimizerTests
 
1191