SERVER-7343 turn within on in queryoptimizer, add jstests

10 files changed, 219 insertions, 67 deletions

diff --git a/jstests/geo_box1_noindex.js b/jstests/geo_box1_noindex.js
new file mode 100644
index 00000000000..a32740401d4
--- /dev/null
+++ b/jstests/geo_box1_noindex.js
@@ -0,0 +1,33 @@
+// SERVER-7343: allow $within without a geo index.
+t = db.geo_box1_noindex;
+t.drop();
+
+num = 0;
+for ( x=0; x<=20; x++ ){
+    for ( y=0; y<=20; y++ ){
+        o = { _id : num++ , loc : [ x , y ] } 
+        t.save( o )
+    }
+}
+
+searches = [
+    [ [ 1 , 2 ] , [ 4 , 5 ] ] ,
+    [ [ 1 , 1 ] , [ 2 , 2 ] ] ,
+    [ [ 0 , 2 ] , [ 4 , 5 ] ] ,
+    [ [ 1 , 1 ] , [ 2 , 8 ] ] ,
+];
+
+for ( i=0; i<searches.length; i++ ){
+    b = searches[i];
+    
+    q = { loc : { $within : { $box : b } } }
+    numWanted = ( 1 + b[1][0] - b[0][0] ) * ( 1 + b[1][1] - b[0][1] );
+    assert.eq( numWanted  , t.find(q).itcount() , "itcount: " + tojson( q ) );
+    printjson( t.find(q).explain() )
+}
+
+assert.eq( 0 , t.find( { loc : { $within : { $box : [ [100 , 100 ] , [ 110 , 110 ] ] } } } ).itcount() , "E1" )
+assert.eq( 0 , t.find( { loc : { $within : { $box : [ [100 , 100 ] , [ 110 , 110 ] ] } } } ).count() , "E2" )
+assert.eq( num , t.find( { loc : { $within : { $box : [ [ 0 , 0 ] , [ 110 , 110 ] ] } } } ).count() , "E3" )
+assert.eq( num , t.find( { loc : { $within : { $box : [ [ 0 , 0 ] , [ 110 , 110 ] ] } } } ).itcount() , "E4" )
+assert.eq( 57 , t.find( { loc : { $within : { $box : [ [ 0 , 0 ] , [ 110 , 110 ] ] } } } ).limit(57).itcount() , "E5" )
diff --git a/jstests/geo_circle1_noindex.js b/jstests/geo_circle1_noindex.js
new file mode 100644
index 00000000000..02e82914c54
--- /dev/null
+++ b/jstests/geo_circle1_noindex.js
@@ -0,0 +1,29 @@
+// SERVER-7343: allow $within without a geo index.
+t = db.geo_circle1_noindex;
+t.drop();
+
+searches = [ 
+    [ [ 5 , 5 ] , 3 ] ,
+    [ [ 5 , 5 ] , 1 ] ,
+    [ [ 5 , 5 ] , 5 ] ,
+    [ [ 0 , 5 ] , 5 ] ,
+];
+correct = searches.map( function(z){ return []; } );
+
+num = 0;
+
+for ( x=0; x<=20; x++ ){
+    for ( y=0; y<=20; y++ ){
+        o = { _id : num++ , loc : [ x , y ] } 
+        t.save( o )
+        for ( i=0; i<searches.length; i++ )
+            if ( Geo.distance( [ x , y ] , searches[i][0] ) <= searches[i][1] )
+                correct[i].push( o );
+    }
+}
+
+for ( i=0; i<searches.length; i++ ){
+    q = { loc : { $within : { $center : searches[i] } } }
+    assert.eq( correct[i].length , t.find( q ).itcount() , "itcount : " + tojson( searches[i] ) );
+    assert.eq( correct[i].length , t.find( q ).count() , "count : " + tojson( searches[i] ) );
+}
diff --git a/jstests/geo_polygon1_noindex.js b/jstests/geo_polygon1_noindex.js
new file mode 100644
index 00000000000..f5b8f4eae7b
--- /dev/null
+++ b/jstests/geo_polygon1_noindex.js
@@ -0,0 +1,47 @@
+// SERVER-7343: allow $within without a geo index.
+
+t = db.geo_polygon1_noindex;
+t.drop();
+
+num = 0;
+for ( x=1; x < 9; x++ ){
+    for ( y= 1; y < 9; y++ ){
+        o = { _id : num++ , loc : [ x , y ] };
+        t.save( o );
+    }
+}
+
+triangle = [[0,0], [1,1], [0,2]];
+
+// Look at only a small slice of the data within a triangle
+assert.eq( 1 , t.find( { loc: { "$within": { "$polygon" : triangle }}} ).count() , "Triangle Test" );
+
+boxBounds = [ [0,0], [0,10], [10,10], [10,0] ];
+
+assert.eq( num , t.find( { loc : { "$within" : { "$polygon" : boxBounds } } } ).count() , "Bounding Box Test" );
+
+//Make sure we can add object-based polygons
+assert.eq( num, t.find( { loc : { $within : { $polygon : { a : [-10, -10], b : [-10, 10], c : [10, 10], d : [10, -10] } } } } ).count() )
+
+// Look in a box much bigger than the one we have data in
+boxBounds = [[-100,-100], [-100, 100], [100,100], [100,-100]];
+assert.eq( num , t.find( { loc : { "$within" : { "$polygon" : boxBounds } } } ).count() , "Big Bounding Box Test" );
+
+t.drop();
+
+pacman = [
+           [0,2], [0,4], [2,6], [4,6], // Head
+           [6,4], [4,3], [6,2], // Mouth
+           [4,0], [2,0] // Bottom
+         ];
+
+t.save({loc: [1,3] }); // Add a point that's in
+assert.isnull( db.getLastError() )
+
+assert.eq( 1 , t.find({loc : { $within : { $polygon : pacman }}} ).count() , "Pacman single point" );
+
+t.save({ loc : [5, 3] })  // Add a point that's out right in the mouth opening
+t.save({ loc : [3, 7] })  // Add a point above the center of the head
+t.save({ loc : [3,-1] })  // Add a point below the center of the bottom
+
+assert.eq( 1 , t.find({loc : { $within : { $polygon : pacman }}} ).count() , "Pacman double point" );
diff --git a/jstests/geo_withinquery.js b/jstests/geo_withinquery.js
new file mode 100644
index 00000000000..10bd90edca7
--- /dev/null
+++ b/jstests/geo_withinquery.js
@@ -0,0 +1,15 @@
+// SERVER-7343: allow $within without a geo index.
+t = db.geo_withinquery;
+t.drop();
+
+num = 0;
+for ( x=0; x<=20; x++ ){
+    for ( y=0; y<=20; y++ ){
+        o = { _id : num++ , loc : [ x , y ] } 
+        t.save( o )
+    }
+}
+
+assert.eq(21 * 21 - 1, t.find({ $and: [ {loc: {$ne:[0,0]}},
+                                        {loc: {$within: {$box: [[0,0], [100,100]]}}},
+                                      ]}).itcount(), "UHOH!")
diff --git a/src/mongo/db/geo/2d.cpp b/src/mongo/db/geo/2d.cpp
index a53ec58494b..38cc36e4a96 100644
--- a/src/mongo/db/geo/2d.cpp
+++ b/src/mongo/db/geo/2d.cpp
@@ -2441,6 +2441,9 @@ namespace mongo {
         else if ( numWanted == 0 )
             numWanted = 100;
 
+        // false means we want to filter OUT geoFieldsToNuke, not filter to include only that.
+        BSONObj filteredQuery = query.filterFieldsUndotted(BSON(_geo << ""), false);
+
         BSONObjIterator i(query);
         while ( i.more() ) {
             BSONElement e = i.next();
@@ -2450,14 +2453,10 @@ namespace mongo {
 
             if ( e.type() == Array ) {
                 // If we get an array query, assume it is a location, and do a $within { $center : [[x, y], 0] } search
-                shared_ptr<Cursor> c( new GeoCircleBrowse( this , BSON( "0" << e.embeddedObjectUserCheck() << "1" << 0 ), query.filterFieldsUndotted( BSON( _geo << "" ), false ), "$center", true ) );
+                shared_ptr<Cursor> c( new GeoCircleBrowse( this , BSON( "0" << e.embeddedObjectUserCheck() << "1" << 0 ), filteredQuery, "$center", true ) );
                 return c;
             }
             else if ( e.type() == Object ) {
-
-                // TODO:  Filter out _geo : { $special... } field so it doesn't get matched accidentally,
-                // if matcher changes
-
                 switch ( e.embeddedObject().firstElement().getGtLtOp() ) {
                 case BSONObj::opNEAR: {
                     BSONObj n = e.embeddedObject();
@@ -2494,7 +2493,8 @@ namespace mongo {
                     bool uniqueDocs = false;
                     if( ! n["$uniqueDocs"].eoo() ) uniqueDocs = n["$uniqueDocs"].trueValue();
 
-                    shared_ptr<GeoSearch> s( new GeoSearch( this , Point( e ) , numWanted , query , maxDistance, type, uniqueDocs ) );
+                    shared_ptr<GeoSearch> s( new GeoSearch( this , Point( e ) , numWanted ,
+                                                            filteredQuery , maxDistance, type, uniqueDocs ) );
                     s->exec();
                     shared_ptr<Cursor> c;
                     c.reset( new GeoSearchCursor( s ) );
@@ -2514,24 +2514,27 @@ namespace mongo {
 
                     if ( startsWith(type,  "$center") ) {
                         uassert( 13059 , "$center has to take an object or array" , e.isABSONObj() );
-                        shared_ptr<Cursor> c( new GeoCircleBrowse( this , e.embeddedObjectUserCheck() , query , type, uniqueDocs ) );
+                        shared_ptr<Cursor> c(new GeoCircleBrowse(this, e.embeddedObjectUserCheck(),
+                                                                 filteredQuery, type, uniqueDocs));
                         return c;
                     }
                     else if ( type == "$box" ) {
                         uassert( 13065 , "$box has to take an object or array" , e.isABSONObj() );
-                        shared_ptr<Cursor> c( new GeoBoxBrowse( this , e.embeddedObjectUserCheck() , query, uniqueDocs ) );
+                        shared_ptr<Cursor> c(new GeoBoxBrowse(this, e.embeddedObjectUserCheck(),
+                                                              filteredQuery, uniqueDocs));
                         return c;
                     }
                     else if ( startsWith( type, "$poly" ) ) {
                         uassert( 14029 , "$polygon has to take an object or array" , e.isABSONObj() );
-                        shared_ptr<Cursor> c( new GeoPolygonBrowse( this , e.embeddedObjectUserCheck() , query, uniqueDocs ) );
+                        shared_ptr<Cursor> c(new GeoPolygonBrowse(this, e.embeddedObjectUserCheck(),
+                                                                  filteredQuery, uniqueDocs));
                         return c;
                     }
                     throw UserException( 13058 , str::stream() << "unknown $within information : " << context << ", a shape must be specified." );
                 }
                 default:
                     // Otherwise... assume the object defines a point, and we want to do a zero-radius $within $center
-                    shared_ptr<Cursor> c( new GeoCircleBrowse( this , BSON( "0" << e.embeddedObjectUserCheck() << "1" << 0 ), query.filterFieldsUndotted( BSON( _geo << "" ), false ) ) );
+                    shared_ptr<Cursor> c( new GeoCircleBrowse( this , BSON( "0" << e.embeddedObjectUserCheck() << "1" << 0 ), filteredQuery));
                     return c;
                 }
             }
diff --git a/src/mongo/db/matcher.cpp b/src/mongo/db/matcher.cpp
index 766113a67c3..eda29b48163 100755..100644
--- a/src/mongo/db/matcher.cpp
+++ b/src/mongo/db/matcher.cpp
@@ -366,44 +366,45 @@ namespace mongo {
         case BSONObj::opWITHIN: {
             BSONObj shapeObj = fe.embeddedObject();
             BSONObjIterator argIt(shapeObj);
-
-            while (argIt.more()) {
-                BSONElement elt = argIt.next();
-                if (!elt.isABSONObj()) { break; }
-
-                if (!strcmp(elt.fieldName(), "$box")) {
-                    BSONObjIterator coordIt(elt.Obj());
-                    BSONElement minE = coordIt.next();
-                    if (!minE.isABSONObj()) { break; }
-                    if (!coordIt.more()) { break; }
-                    BSONElement maxE = coordIt.next();
-                    if (!maxE.isABSONObj()) { break; }
-                    _geo.push_back(GeoMatcher::makeBox(e.fieldName(), minE.Obj(), maxE.Obj()));
-                } else if (!strcmp(elt.fieldName(), "$center")) {
-                    BSONObjIterator coordIt(elt.Obj());
-                    BSONElement center = coordIt.next();
-                    if (!center.isABSONObj()) { break; }
-                    if (!coordIt.more()) { break; }
-                    BSONElement radius = coordIt.next();
-                    if (!radius.isNumber()) { break; }
-                    _geo.push_back(
+            uassert(16481, "Empty obj for $within: " + shapeObj.toString(), argIt.more());
+
+            BSONElement elt = argIt.next();
+            uassert(16466, "Within must be provided a BSONObj: " + elt.toString(),
+                    elt.isABSONObj());
+            BSONObj obj = elt.Obj();
+            BSONObjIterator coordIt(elt.Obj());
+            uassert(16482, "Malformed $within: ", coordIt.more());
+
+            if (str::equals(elt.fieldName(), "$box")) {
+                BSONElement minE = coordIt.next();
+                uassert(16467, "Malformed $box: " + obj.toString(), minE.isABSONObj());
+                uassert(16468, "Malformed $box: " + obj.toString(), coordIt.more());
+                BSONElement maxE = coordIt.next();
+                uassert(16469, "Malformed $box: " + obj.toString(), minE.isABSONObj());
+                _geo.push_back(GeoMatcher::makeBox(e.fieldName(), minE.Obj(), maxE.Obj()));
+            } else if (str::equals(elt.fieldName(), "$center")) {
+                BSONElement center = coordIt.next();
+                uassert(16473, "Malformed $center: " + obj.toString(), center.isABSONObj());
+                uassert(16474, "Malformed $center: " + obj.toString(), coordIt.more());
+                BSONElement radius = coordIt.next();
+                uassert(16475, "Malformed $center: " + obj.toString(), radius.isNumber());
+                _geo.push_back(
                         GeoMatcher::makeCircle(e.fieldName(), center.Obj(), radius.number()));
-                } else if (!strcmp(elt.fieldName(), "$polygon")) {
-                    BSONObjIterator coordIt(elt.Obj());
-                    bool valid = true;
-                    while (coordIt.more()) {
-                        BSONElement coord = coordIt.next();
-                        if (!coord.isABSONObj()) { valid = false; break; }
-                        BSONObjIterator numIt(coord.Obj());
-                        if (!numIt.more()) { valid = false; break; }
-                        BSONElement x = numIt.next();
-                        if (!x.isNumber()) { valid = false; break; }
-                        BSONElement y = numIt.next();
-                        if (!y.isNumber()) { valid = false; break; }
-                    }
-                    if (!valid) { break; }
-                    _geo.push_back(GeoMatcher::makePolygon(e.fieldName(), elt.Obj()));
+            } else if (str::equals(elt.fieldName(), "$polygon")) {
+                while (coordIt.more()) {
+                    BSONElement coord = coordIt.next();
+                    uassert(16476, "Malformed $polygon: " + obj.toString(), coord.isABSONObj());
+                    BSONObjIterator numIt(coord.Obj());
+                    uassert(16477, "Malformed $polygon: " + obj.toString(), numIt.more());
+                    BSONElement x = numIt.next();
+                    uassert(16478, "Malformed $polygon: " + obj.toString(), x.isNumber());
+                    uassert(16484, "Malformed $polygon: " + obj.toString(), numIt.more());
+                    BSONElement y = numIt.next();
+                    uassert(16479, "Malformed $polygon: " + obj.toString(), y.isNumber());
                 }
+                _geo.push_back(GeoMatcher::makePolygon(e.fieldName(), elt.Obj()));
+            } else {
+                uasserted(16483, "Couldn't pull any geometry out of $within query: " + obj.toString());
             }
             break;
         }
@@ -980,25 +981,15 @@ namespace mongo {
         }
 
         for (vector<GeoMatcher>::const_iterator it = _geo.begin(); it != _geo.end(); ++it) {
+            verify(_constrainIndexKey.isEmpty());
             BSONElementSet s;
-            // XXX: when do we do this and why?
-            if (!_constrainIndexKey.isEmpty()) {
-                BSONElement e = jsobj.getFieldUsingIndexNames(it->getFieldName().c_str(), _constrainIndexKey);
-                if (Array == e.type()) {
-                    BSONObjIterator i(e.Obj());
-                    while (i.more()) { s.insert(i.next()); }
-                } else if (!e.eoo()) {
-                    s.insert(e);
-                }
-            } else {
-                jsobj.getFieldsDotted(it->getFieldName().c_str(), s, false);
-            }
+            jsobj.getFieldsDotted(it->getFieldName().c_str(), s, false);
             int matches = 0;
             for (BSONElementSet::const_iterator i = s.begin(); i != s.end(); ++i) {
                 if (!i->isABSONObj()) { continue; }
                 Point p;
                 if (!GeoMatcher::pointFrom(i->Obj(), &p)) { continue; }
-                if (it->containsPoint(p)) { ++matches; }
+                if (it->containsPoint(p)) { ++matches; break; }
             }
             if (0 == matches) { return false; }
         }
@@ -1244,6 +1235,9 @@ namespace mongo {
         if ( !( _basics.size() == docMatcher._basics.size() && _regexs.size() == docMatcher._regexs.size() && !docMatcher._where ) ) {
             return false;
         }
+        if (_geo.size() != docMatcher._geo.size()) {
+            return false;
+        }
         if ( _andMatchers.size() != docMatcher._andMatchers.size() ) {
             return false;
         }
diff --git a/src/mongo/db/matcher.h b/src/mongo/db/matcher.h
index 2b878f97362..e217667fa81 100644
--- a/src/mongo/db/matcher.h
+++ b/src/mongo/db/matcher.h
@@ -45,7 +45,8 @@ namespace mongo {
 
     class GeoMatcher {
     private:
-        GeoMatcher(const string& field) : _isBox(false), _isCircle(false), _fieldName(field) {}
+        GeoMatcher(const string& field) : _isBox(false), _isCircle(false), _isPolygon(false),
+                                          _fieldName(field) {}
         bool _isBox;
         Box _box;
 
@@ -63,15 +64,15 @@ namespace mongo {
         static GeoMatcher makeBox(const string& field, const BSONObj &min, const BSONObj &max) {
             GeoMatcher m(field);
             m._isBox = true;
-            pointFrom(min, &m._box._min);
-            pointFrom(max, &m._box._max);
+            uassert(16470, "Malformed coord: " + min.toString(), pointFrom(min, &m._box._min));
+            uassert(16471, "Malformed coord: " + max.toString(), pointFrom(max, &m._box._max));
             return m;
         }
 
         static GeoMatcher makeCircle(const string& field, const BSONObj &center, double rad) {
             GeoMatcher m(field);
             m._isCircle = true;
-            pointFrom(center, &m._center);
+            uassert(16472, "Malformed coord: " + center.toString(), pointFrom(center, &m._center));
             m._radius = rad;
             return m;
         }
@@ -84,8 +85,9 @@ namespace mongo {
             BSONObjIterator coordIt(poly);
             while (coordIt.more()) {
                 BSONElement coord = coordIt.next();
+                const BSONObj& obj = coord.Obj();
                 Point p;
-                pointFrom(coord.Obj(), &p);
+                uassert(16480, "Malformed coord: " + obj.toString(), pointFrom(obj, &p));
                 points.push_back(p);
             }
             m._polygon = Polygon(points);
diff --git a/src/mongo/db/queryoptimizer.cpp b/src/mongo/db/queryoptimizer.cpp
index 849c8064c85..40af04ce450 100644
--- a/src/mongo/db/queryoptimizer.cpp
+++ b/src/mongo/db/queryoptimizer.cpp
@@ -642,6 +642,7 @@ doneCheckOrder:
     
     bool QueryPlanGenerator::addSpecialPlan( NamespaceDetails *d ) {
         DEBUGQO( "\t special : " << _qps.frsp().getSpecial() );
+        // If an index exists for the special query component, use it.
         if ( _qps.frsp().getSpecial().size() ) {
             string special = _qps.frsp().getSpecial();
             NamespaceDetails::IndexIterator i = d->ii();
@@ -656,6 +657,12 @@ doneCheckOrder:
                     return true;
                 }
             }
+
+            // If no index exists but the index is not mandatory (Matcher has functionality to
+            // support it), have the caller fall through to using a normal query plan.
+            if (!_qps.frsp().hasSpecialThatNeedsIndex()) { return false; }
+
+            // Otherwise, error.
             uassert( 13038, (string)"can't find special index: " + special +
                     " for: " + _qps.originalQuery().toString(), false );
         }
diff --git a/src/mongo/db/queryutil.cpp b/src/mongo/db/queryutil.cpp
index 26d7dfba1b0..ca8d4197892 100644
--- a/src/mongo/db/queryutil.cpp
+++ b/src/mongo/db/queryutil.cpp
@@ -163,7 +163,7 @@ namespace mongo {
 
 
     FieldRange::FieldRange( const BSONElement &e, bool isNot, bool optimize ) :
-    _exactMatchRepresentation() {
+        _specialNeedsIndex(true), _exactMatchRepresentation() {
         int op = e.getGtLtOp();
 
         // NOTE with $not, we could potentially form a complementary set of intervals.
@@ -428,8 +428,12 @@ namespace mongo {
             log() << "warning: shouldn't get here?" << endl;
             break;
         }
-        case BSONObj::opNEAR:
         case BSONObj::opWITHIN:
+            _specialNeedsIndex = false;
+            _special = "2d";
+            break;
+        case BSONObj::opNEAR:
+            _specialNeedsIndex = true;
             _special = "2d";
             break;
         case BSONObj::opEXISTS: {
@@ -465,8 +469,10 @@ namespace mongo {
         _intervals = newIntervals;
         for( vector<BSONObj>::const_iterator i = other._objData.begin(); i != other._objData.end(); ++i )
             _objData.push_back( *i );
-        if ( _special.size() == 0 && other._special.size() )
+        if ( _special.size() == 0 && other._special.size() ) {
             _special = other._special;
+            _specialNeedsIndex = other._specialNeedsIndex;
+        }
         _exactMatchRepresentation = exactMatchRepresentation;
     }
 
@@ -767,6 +773,17 @@ namespace mongo {
         return s;
     }
 
+    bool FieldRangeSet::hasSpecialThatNeedsIndex() const {
+        for ( map<string,FieldRange>::const_iterator i=_ranges.begin(); i!=_ranges.end(); i++ ) {
+            if ( i->second.getSpecial().size() == 0 )
+                continue;
+            if ( i->second.hasSpecialThatNeedsIndex() )
+                return true;
+        }
+        return false;
+    }
+
+
     /**
      * Btree scanning for a multidimentional key range will yield a
      * multidimensional box.  The idea here is that if an 'other'
diff --git a/src/mongo/db/queryutil.h b/src/mongo/db/queryutil.h
index 79097b4af68..f29404b33a0 100644
--- a/src/mongo/db/queryutil.h
+++ b/src/mongo/db/queryutil.h
@@ -359,6 +359,8 @@ namespace mongo {
          */
         void reverse( FieldRange &ret ) const;
 
+        bool hasSpecialThatNeedsIndex() const { verify( _special.size() ); return _specialNeedsIndex; }
+
         string toString() const;
     private:
         BSONObj addObj( const BSONObj &o );
@@ -368,6 +370,7 @@ namespace mongo {
         // Owns memory for our BSONElements.
         vector<BSONObj> _objData;
         string _special;
+        bool _specialNeedsIndex;
         bool _exactMatchRepresentation;
     };
     
@@ -457,6 +460,7 @@ namespace mongo {
         
         QueryPattern pattern( const BSONObj &sort = BSONObj() ) const;
         string getSpecial() const;
+        bool hasSpecialThatNeedsIndex() const;
 
         /**
          * @return a FieldRangeSet approximation of the documents in 'this' but
@@ -578,6 +582,7 @@ namespace mongo {
         const char *ns() const { return _singleKey.ns(); }
 
         string getSpecial() const { return _singleKey.getSpecial(); }
+        bool hasSpecialThatNeedsIndex() const { return _singleKey.hasSpecialThatNeedsIndex(); }
 
         /** Intersect with another FieldRangeSetPair. */
         FieldRangeSetPair &operator&=( const FieldRangeSetPair &other );