diff options
Diffstat (limited to 'src/mongo')
34 files changed, 444 insertions, 760 deletions
diff --git a/src/mongo/SConscript b/src/mongo/SConscript index 7022341d3b8..4c7ec89a688 100644 --- a/src/mongo/SConscript +++ b/src/mongo/SConscript @@ -844,9 +844,12 @@ env.Library("geoquery", [ "db/geo/geoquery.cpp", "db/geo/r2_region_coverer.cpp", "geoparser", '$BUILD_DIR/third_party/s2/s2' ]) -env.CppUnitTest("hash_test", [ "db/geo/hash_test.cpp" ], LIBDEPS = ["geometry" ]) -env.CppUnitTest("geoparser_test", [ "db/geo/geoparser_test.cpp" ], LIBDEPS = ["geoparser"]) -env.CppUnitTest("r2_region_coverer_test",[ "db/geo/r2_region_coverer_test.cpp" ], LIBDEPS = ["geoquery"]) +env.CppUnitTest("hash_test", [ "db/geo/hash_test.cpp" ], + LIBDEPS = ["geometry", "db/common" ]) # db/common needed for field parsing +env.CppUnitTest("geoparser_test", [ "db/geo/geoparser_test.cpp" ], + LIBDEPS = ["geoparser", "db/common" ]) # db/common needed for field parsing +env.CppUnitTest("r2_region_coverer_test", [ "db/geo/r2_region_coverer_test.cpp" ], + LIBDEPS = [ "geoquery", "db/common" ]) # db/common needed for field parsing env.CppUnitTest( target="index_filter_commands_test", diff --git a/src/mongo/db/exec/2d.cpp b/src/mongo/db/exec/2d.cpp deleted file mode 100644 index dd2d7dc1eef..00000000000 --- a/src/mongo/db/exec/2d.cpp +++ /dev/null @@ -1,293 +0,0 @@ -/** - * 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 <http://www.gnu.org/licenses/>. - * - * 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. - */ - -#include "mongo/db/exec/2d.h" - -#include "mongo/db/catalog/database.h" -#include "mongo/db/client.h" -#include "mongo/db/exec/working_set_common.h" -#include "mongo/db/jsobj.h" -#include "mongo/db/catalog/collection.h" - -namespace mongo { - - TwoD::TwoD(const TwoDParams& params, WorkingSet* ws) - : _params(params), _workingSet(ws), _initted(false), - _descriptor(NULL), _am(NULL) { - } - - TwoD::~TwoD() { } - - bool TwoD::isEOF() { - return _initted && (NULL == _browse.get()); - } - - PlanStage::StageState TwoD::work(WorkingSetID* out) { - if (isEOF()) { return PlanStage::IS_EOF; } - - if (!_initted) { - _initted = true; - - if ( !_params.collection ) - return PlanStage::IS_EOF; - - IndexCatalog* indexCatalog = _params.collection->getIndexCatalog(); - - _descriptor = indexCatalog->findIndexByKeyPattern(_params.indexKeyPattern); - if ( _descriptor == NULL ) - return PlanStage::IS_EOF; - - _am = static_cast<TwoDAccessMethod*>( indexCatalog->getIndex( _descriptor ) ); - verify( _am ); - - if (NULL != _params.gq.getGeometry().getCapGeometryHack()) { - _browse.reset(new twod_exec::GeoCircleBrowse(_params, _am)); - } - else if (NULL != _params.gq.getGeometry().getPolygonGeometryHack()) { - _browse.reset(new twod_exec::GeoPolygonBrowse(_params, _am)); - } - else { - verify(NULL != _params.gq.getGeometry().getBoxGeometryHack()); - _browse.reset(new twod_exec::GeoBoxBrowse(_params, _am)); - } - - // Fill out static portion of plan stats. - // We will retrieve the geo hashes used by the geo browser - // when the search is complete. - _specificStats.type = _browse->_type; - _specificStats.field = _params.gq.getField(); - _specificStats.converterParams = _browse->_converter->getParams(); - - return PlanStage::NEED_TIME; - } - - verify(NULL != _browse.get()); - - if (!_browse->ok()) { - // Grab geo hashes before disposing geo browser. - _specificStats.expPrefixes.swap(_browse->_expPrefixes); - _browse.reset(); - return PlanStage::IS_EOF; - } - - WorkingSetID id = _workingSet->allocate(); - WorkingSetMember* member = _workingSet->get(id); - member->loc = _browse->currLoc(); - member->obj = _params.collection->docFor(member->loc); - member->state = WorkingSetMember::LOC_AND_UNOWNED_OBJ; - - _browse->advance(); - - *out = id; - _commonStats.advanced++; - _commonStats.works++; - return PlanStage::ADVANCED; - } - - void TwoD::prepareToYield() { - if (NULL != _browse) { - _browse->noteLocation(); - } - } - - void TwoD::recoverFromYield() { - if (NULL != _browse) { - _browse->checkLocation(); - } - } - - void TwoD::invalidate(const DiskLoc& dl, InvalidationType type) { - if (NULL != _browse) { - // If the invalidation actually tossed out a result... - if (_browse->invalidate(dl)) { - // Create a new WSM - WorkingSetID id = _workingSet->allocate(); - WorkingSetMember* member = _workingSet->get(id); - member->loc = dl; - member->obj = _params.collection->docFor(member->loc); - member->state = WorkingSetMember::LOC_AND_UNOWNED_OBJ; - - // And flag it for later. - WorkingSetCommon::fetchAndInvalidateLoc(member, _params.collection); - _workingSet->flagForReview(id); - } - } - } - - PlanStageStats* TwoD::getStats() { - _commonStats.isEOF = isEOF(); - auto_ptr<PlanStageStats> ret(new PlanStageStats(_commonStats, STAGE_GEO_2D)); - ret->specific.reset(new TwoDStats(_specificStats)); - return ret.release(); - } -} - -namespace mongo { -namespace twod_exec { - - - // - // Impls of browse below - // - - // - // GeoCircleBrowse - // - - GeoCircleBrowse::GeoCircleBrowse(const TwoDParams& params, TwoDAccessMethod* accessMethod) - : GeoBrowse(params.collection, accessMethod, "circle", params.filter) { - - _converter = accessMethod->getParams().geoHashConverter; - - const CapWithCRS& cap = *params.gq.getGeometry().getCapGeometryHack(); - - _startPt = cap.circle.center; - _start = _converter->hash(_startPt); - _maxDistance = cap.circle.radius; - - if (FLAT == cap.crs) { - _type = GEO_PLANE; - xScanDistance = _maxDistance + _converter->getError(); - yScanDistance = _maxDistance + _converter->getError(); - } else { - _type = GEO_SPHERE; - yScanDistance = rad2deg(_maxDistance) + _converter->getError(); - xScanDistance = computeXScanDistance(_startPt.y, yScanDistance); - } - - // Bounding box includes fudge factor. - // TODO: Is this correct, since fudge factor may be spherically transformed? - _bBox._min = Point(_startPt.x - xScanDistance, _startPt.y - yScanDistance); - _bBox._max = Point(_startPt.x + xScanDistance, _startPt.y + yScanDistance); - - ok(); - } - - GeoAccumulator::KeyResult GeoCircleBrowse::approxKeyCheck(const Point& p, double& d) { - // Inexact hash distance checks. - double error = 0; - switch (_type) { - case GEO_PLANE: - d = distance(_startPt, p); - error = _converter->getError(); - break; - case GEO_SPHERE: { - checkEarthBounds(p); - d = spheredist_deg(_startPt, p); - error = _converter->getErrorSphere(); - break; - } - default: verify(false); - } - - // If our distance is in the error bounds... - if(d >= _maxDistance - error && d <= _maxDistance + error) return BORDER; - return d > _maxDistance ? BAD : GOOD; - } - - bool GeoCircleBrowse::exactDocCheck(const Point& p, double& d){ - switch (_type) { - case GEO_PLANE: { - if(distanceWithin(_startPt, p, _maxDistance)) return true; - break; - } - case GEO_SPHERE: - checkEarthBounds(p); - if(spheredist_deg(_startPt, p) <= _maxDistance) return true; - break; - default: verify(false); - } - - return false; - } - - // - // GeoBoxBrowse - // - - GeoBoxBrowse::GeoBoxBrowse(const TwoDParams& params, TwoDAccessMethod* accessMethod) - : GeoBrowse(params.collection, accessMethod, "box", params.filter) { - - _converter = accessMethod->getParams().geoHashConverter; - - _want = params.gq.getGeometry().getBoxGeometryHack()->box; - _wantRegion = _want; - // Need to make sure we're checking regions within error bounds of where we want - _wantRegion.fudge(_converter->getError()); - fixBox(_wantRegion); - fixBox(_want); - - Point center = _want.center(); - _start = _converter->hash(center.x, center.y); - - _fudge = _converter->getError(); - _wantLen = _fudge + - std::max((_want._max.x - _want._min.x), - (_want._max.y - _want._min.y)) / 2; - - ok(); - } - - void GeoBoxBrowse::fixBox(Box& box) { - if(box._min.x > box._max.x) - std::swap(box._min.x, box._max.x); - if(box._min.y > box._max.y) - std::swap(box._min.y, box._max.y); - - double gMin = _converter->getMin(); - double gMax = _converter->getMax(); - - if(box._min.x < gMin) box._min.x = gMin; - if(box._min.y < gMin) box._min.y = gMin; - if(box._max.x > gMax) box._max.x = gMax; - if(box._max.y > gMax) box._max.y = gMax; - } - - // - // GeoPolygonBrowse - // - - GeoPolygonBrowse::GeoPolygonBrowse(const TwoDParams& params, TwoDAccessMethod* accessMethod) - : GeoBrowse(params.collection, accessMethod, "polygon", params.filter) { - - _converter = accessMethod->getParams().geoHashConverter; - - _poly.init(params.gq.getGeometry().getPolygonGeometryHack()->oldPolygon); - _bounds.init(_poly.bounds()); - - // We need to check regions within the error bounds of these bounds - _bounds.fudge(_converter->getError()); - // We don't need to look anywhere outside the space - _bounds.truncate(_converter->getMin(), _converter->getMax()); - _maxDim = _converter->getError() + _bounds.maxDim() / 2; - - ok(); - } - -} // namespace twod_exec -} // namespace mongo diff --git a/src/mongo/db/exec/2d.h b/src/mongo/db/exec/2d.h deleted file mode 100644 index 0f0cdd111de..00000000000 --- a/src/mongo/db/exec/2d.h +++ /dev/null @@ -1,179 +0,0 @@ -/** - * 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 <http://www.gnu.org/licenses/>. - * - * 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. - */ - -#include "mongo/db/exec/2dcommon.h" -#include "mongo/db/exec/plan_stage.h" -#include "mongo/db/geo/geoquery.h" - -#pragma once - -namespace mongo { - - struct TwoDParams { - TwoDParams() : filter(NULL), collection(NULL) { } - GeoQuery gq; - MatchExpression* filter; - BSONObj indexKeyPattern; - Collection* collection; // not owned - }; - - class TwoD : public PlanStage { - public: - TwoD(const TwoDParams& params, WorkingSet* ws); - virtual ~TwoD(); - - virtual bool isEOF(); - virtual StageState work(WorkingSetID* out); - - virtual void prepareToYield(); - virtual void recoverFromYield(); - virtual void invalidate(const DiskLoc& dl, InvalidationType type); - - virtual PlanStageStats* getStats(); - private: - scoped_ptr<mongo::twod_exec::GeoBrowse> _browse; - TwoDParams _params; - WorkingSet* _workingSet; - bool _initted; - IndexDescriptor* _descriptor; - TwoDAccessMethod* _am; - CommonStats _commonStats; - TwoDStats _specificStats; - }; -} - -namespace mongo { -namespace twod_exec { - - // - // Impls of browse below - // - - class GeoCircleBrowse : public GeoBrowse { - public: - GeoCircleBrowse(const TwoDParams& params, TwoDAccessMethod* accessMethod); - - virtual GeoHash expandStartHash() { return _start; } - - virtual bool fitsInBox(double width) { - return width >= std::max(xScanDistance, yScanDistance); - } - - virtual double intersectsBox(Box& cur) { - return cur.intersects(_bBox); - } - - virtual KeyResult approxKeyCheck(const Point& p, double& d); - - virtual bool exactDocCheck(const Point& p, double& d); - - GeoDistType _type; - GeoHash _start; - Point _startPt; - double _maxDistance; // user input - double xScanDistance; // effected by GeoDistType - double yScanDistance; // effected by GeoDistType - Box _bBox; - - shared_ptr<GeoHashConverter> _converter; - }; - - class GeoBoxBrowse : public GeoBrowse { - public: - GeoBoxBrowse(const TwoDParams& params, TwoDAccessMethod* accessMethod); - - void fixBox(Box& box); - - virtual GeoHash expandStartHash() { - return _start; - } - - virtual bool fitsInBox(double width) { - return width >= _wantLen; - } - - virtual double intersectsBox(Box& cur) { - return cur.intersects(_wantRegion); - } - - virtual KeyResult approxKeyCheck(const Point& p, double& d) { - if(_want.onBoundary(p, _fudge)) return BORDER; - else return _want.inside(p, _fudge) ? GOOD : BAD; - - } - - virtual bool exactDocCheck(const Point& p, double& d){ - return _want.inside(p); - } - - Box _want; - Box _wantRegion; - double _wantLen; - double _fudge; - GeoHash _start; - shared_ptr<GeoHashConverter> _converter; - }; - - class GeoPolygonBrowse : public GeoBrowse { - public: - GeoPolygonBrowse(const TwoDParams& params, TwoDAccessMethod* accessMethod); - - // The initial geo hash box for our first expansion - virtual GeoHash expandStartHash() { - return _converter->hash(_bounds.center()); - } - - // Whether the current box width is big enough for our search area - virtual bool fitsInBox(double width) { - return _maxDim <= width; - } - - // Whether the current box overlaps our search area - virtual double intersectsBox(Box& cur) { - return cur.intersects(_bounds); - } - - virtual KeyResult approxKeyCheck(const Point& p, double& d) { - int in = _poly.contains(p, _converter->getError()); - if(in == 0) return BORDER; - else return in > 0 ? GOOD : BAD; - } - - virtual bool exactDocCheck(const Point& p, double& d){ - return _poly.contains(p); - } - - private: - Polygon _poly; - Box _bounds; - double _maxDim; - GeoHash _start; - shared_ptr<GeoHashConverter> _converter; - }; -} // namespace twod_exec -} // namespace mongo diff --git a/src/mongo/db/exec/2dcommon.cpp b/src/mongo/db/exec/2dcommon.cpp index fc2529258f7..7ffc110d8f6 100644 --- a/src/mongo/db/exec/2dcommon.cpp +++ b/src/mongo/db/exec/2dcommon.cpp @@ -249,7 +249,7 @@ namespace twod_exec { // First field of start key goes (MINKEY, start] (in reverse) BSONObjBuilder firstBob; firstBob.appendMinKey(""); - start.appendToBuilder(&firstBob, ""); + start.appendHashMin(&firstBob, ""); minParams.bounds.fields[0].intervals.push_back(Interval(firstBob.obj(), false, true)); IndexScanParams maxParams; @@ -260,7 +260,7 @@ namespace twod_exec { maxParams.doNotDedup = true; // First field of end key goes (start, MAXKEY) BSONObjBuilder secondBob; - start.appendToBuilder(&secondBob, ""); + start.appendHashMin(&secondBob, ""); secondBob.appendMaxKey(""); maxParams.bounds.fields[0].intervals.push_back(Interval(secondBob.obj(), false, false)); diff --git a/src/mongo/db/exec/2dnear.h b/src/mongo/db/exec/2dnear.h index 6d3ac4254d8..65d07908a73 100644 --- a/src/mongo/db/exec/2dnear.h +++ b/src/mongo/db/exec/2dnear.h @@ -172,7 +172,7 @@ namespace twod_exec { virtual bool fitsInBox(double width) { return width >= _scanDistance; } // Whether the current box overlaps our search area - virtual double intersectsBox(Box& cur) { return cur.intersects(_want); } + virtual double intersectsBox(Box& cur) { return cur.legacyIntersectFraction(_want); } std::set< std::pair<DiskLoc,int> > _seen; GeoHash _start; diff --git a/src/mongo/db/exec/SConscript b/src/mongo/db/exec/SConscript index 037fe773e7c..3c85bfb8602 100644 --- a/src/mongo/db/exec/SConscript +++ b/src/mongo/db/exec/SConscript @@ -35,7 +35,6 @@ env.Library( env.Library( target = 'exec', source = [ - "2d.cpp", "2dcommon.cpp", "2dnear.cpp", "and_hash.cpp", diff --git a/src/mongo/db/field_parser.cpp b/src/mongo/db/field_parser.cpp index 80f04ab4e6e..40c8c9664eb 100644 --- a/src/mongo/db/field_parser.cpp +++ b/src/mongo/db/field_parser.cpp @@ -378,6 +378,67 @@ namespace mongo { return FIELD_INVALID; } + FieldParser::FieldState FieldParser::extract( BSONObj doc, + const BSONField<double>& field, + double* out, + string* errMsg ) { + return extract( doc[field.name()], field, out, errMsg ); + } + + FieldParser::FieldState FieldParser::extract( BSONElement elem, + const BSONField<double>& field, + double* out, + string* errMsg ) + { + if (elem.eoo()) { + if (field.hasDefault()) { + *out = field.getDefault(); + return FIELD_DEFAULT; + } + else { + return FIELD_NONE; + } + } + + if (elem.type() == NumberDouble) { + *out = elem.numberDouble(); + return FIELD_SET; + } + + _genFieldErrMsg(elem, field, "double", errMsg); + return FIELD_INVALID; + } + + FieldParser::FieldState FieldParser::extractNumber( BSONObj doc, + const BSONField<double>& field, + double* out, + string* errMsg ) { + return extractNumber( doc[field.name()], field, out, errMsg ); + } + + FieldParser::FieldState FieldParser::extractNumber( BSONElement elem, + const BSONField<double>& field, + double* out, + string* errMsg ) { + if (elem.eoo()) { + if (field.hasDefault()) { + *out = field.getDefault(); + return FIELD_DEFAULT; + } + else { + return FIELD_NONE; + } + } + + if (elem.isNumber()) { + *out = elem.numberDouble(); + return FIELD_SET; + } + + _genFieldErrMsg(elem, field, "number", errMsg); + return FIELD_INVALID; + } + FieldParser::FieldState FieldParser::extractID( BSONObj doc, const BSONField<BSONObj>& field, BSONObj* out, diff --git a/src/mongo/db/field_parser.h b/src/mongo/db/field_parser.h index a0897c16fdd..bd6d852e71f 100644 --- a/src/mongo/db/field_parser.h +++ b/src/mongo/db/field_parser.h @@ -156,6 +156,16 @@ namespace mongo { long long* out, std::string* errMsg = NULL ); + static FieldState extract( BSONElement elem, + const BSONField<double>& field, + double* out, + std::string* errMsg = NULL ); + + static FieldState extract( BSONObj doc, + const BSONField<double>& field, + double* out, + std::string* errMsg = NULL ); + /** * The following extractNumber methods do implicit conversion between any numeric type and * the BSONField type. This can be useful when an exact numeric type is not needed, for @@ -181,6 +191,16 @@ namespace mongo { long long* out, std::string* errMsg = NULL ); + static FieldState extractNumber( BSONObj doc, + const BSONField<double>& field, + double* out, + std::string* errMsg = NULL ); + + static FieldState extractNumber( BSONElement elem, + const BSONField<double>& field, + double* out, + std::string* errMsg = NULL ); + /** * Extracts a document id from a particular field name, which may be of any type but Array. * Wraps the extracted id value in a BSONObj with one element and empty field name. diff --git a/src/mongo/db/geo/geoquery.cpp b/src/mongo/db/geo/geoquery.cpp index f4f3fbff351..b0c1f86e105 100644 --- a/src/mongo/db/geo/geoquery.cpp +++ b/src/mongo/db/geo/geoquery.cpp @@ -246,6 +246,9 @@ namespace mongo { return parseLegacyQuery(obj) || parseNewQuery(obj); } + GeometryContainer::GeometryContainer() { + } + bool GeometryContainer::isSimpleContainer() const { return NULL != _point || NULL != _line || NULL != _polygon; } @@ -338,16 +341,12 @@ namespace mongo { bool GeometryContainer::R2BoxRegion::fastContains(const Box& other) const { // TODO: Add more cases here to make coverings better + if (_geometry->_box && FLAT == _geometry->_box->crs) { const Box& box = _geometry->_box->box; - if (box.inside(other._min) && box.inside(other._max)) { - return true; - } + return box.contains(other); } - // Fast bounds check - if (!_bounds.contains(other)) return false; - if ( _geometry->_cap && FLAT == _geometry->_cap->crs ) { const Circle& circle = _geometry->_cap->circle; const Point& a = other._min; @@ -369,6 +368,7 @@ namespace mongo { } bool GeometryContainer::R2BoxRegion::fastDisjoint(const Box& other) const { + if (!_bounds.intersects(other)) return true; @@ -1023,7 +1023,6 @@ namespace mongo { } bool GeometryContainer::parseFrom(const BSONObj& obj) { - *this = GeometryContainer(); if (GeoParser::isPolygon(obj)) { // We can't really pass these things around willy-nilly except by ptr. @@ -1146,12 +1145,4 @@ namespace mongo { return _cap.get(); } - const BoxWithCRS* GeometryContainer::getBoxGeometryHack() const { - return _box.get(); - } - - const PolygonWithCRS* GeometryContainer::getPolygonGeometryHack() const { - return _polygon.get(); - } - } // namespace mongo diff --git a/src/mongo/db/geo/geoquery.h b/src/mongo/db/geo/geoquery.h index f39d0430692..16ed8da11b2 100644 --- a/src/mongo/db/geo/geoquery.h +++ b/src/mongo/db/geo/geoquery.h @@ -28,6 +28,7 @@ #pragma once +#include "mongo/base/disallow_copying.h" #include "mongo/db/geo/geoparser.h" #include "mongo/db/geo/shapes.h" #include "mongo/util/mongoutils/str.h" @@ -36,8 +37,14 @@ namespace mongo { class GeometryContainer { + MONGO_DISALLOW_COPYING(GeometryContainer); public: + /** + * Creates an empty geometry container which may then only be loaded via parseFrom(). + */ + GeometryContainer(); + bool parseFrom(const BSONObj &obj); /** @@ -79,11 +86,9 @@ namespace mongo { // Returns a string related to the type of the geometry (for debugging queries) std::string getDebugType() const; - // Needed for 2D wrapping check and 2d stage (for now) + // Needed for 2D wrapping check (for now) // TODO: Remove these hacks const CapWithCRS* getCapGeometryHack() const; - const BoxWithCRS* getBoxGeometryHack() const; - const PolygonWithCRS* getPolygonGeometryHack() const; private: @@ -107,21 +112,20 @@ namespace mongo { // Only one of these shared_ptrs should be non-NULL. S2Region is a // superclass but it only supports testing against S2Cells. We need // the most specific class we can get. - // TODO: Make this non-copyable and change all these shared ptrs to scoped - shared_ptr<PointWithCRS> _point; - shared_ptr<LineWithCRS> _line; - shared_ptr<BoxWithCRS> _box; - shared_ptr<PolygonWithCRS> _polygon; - shared_ptr<CapWithCRS> _cap; - shared_ptr<MultiPointWithCRS> _multiPoint; - shared_ptr<MultiLineWithCRS> _multiLine; - shared_ptr<MultiPolygonWithCRS> _multiPolygon; - shared_ptr<GeometryCollection> _geometryCollection; + scoped_ptr<PointWithCRS> _point; + scoped_ptr<LineWithCRS> _line; + scoped_ptr<BoxWithCRS> _box; + scoped_ptr<PolygonWithCRS> _polygon; + scoped_ptr<CapWithCRS> _cap; + scoped_ptr<MultiPointWithCRS> _multiPoint; + scoped_ptr<MultiLineWithCRS> _multiLine; + scoped_ptr<MultiPolygonWithCRS> _multiPolygon; + scoped_ptr<GeometryCollection> _geometryCollection; // Cached for use during covering calculations // TODO: _s2Region is currently generated immediately - don't necessarily need to do this - shared_ptr<S2RegionUnion> _s2Region; - shared_ptr<R2Region> _r2Region; + scoped_ptr<S2RegionUnion> _s2Region; + scoped_ptr<R2Region> _r2Region; }; // TODO: Make a struct, turn parse stuff into something like diff --git a/src/mongo/db/geo/hash.cpp b/src/mongo/db/geo/hash.cpp index 5f922ba4c73..5715c2b5eca 100644 --- a/src/mongo/db/geo/hash.cpp +++ b/src/mongo/db/geo/hash.cpp @@ -26,7 +26,7 @@ * it in the license file. */ -#include "mongo/pch.h" +#include "mongo/db/field_parser.h" #include "mongo/db/jsobj.h" #include "mongo/db/geo/core.h" #include "mongo/db/geo/hash.h" @@ -59,9 +59,13 @@ namespace mongo { hashedToNormal[fixed] = i; } + // Generate all 32 + 1 all-on bit patterns by repeatedly shifting the next bit to the + // correct position + long long currAllX = 0, currAllY = 0; - for (int i = 0; i < 64; i++){ - long long thisBit = 1LL << (63 - i); + for (int i = 0; i < 64 + 2; i++){ + + long long thisBit = 1LL << (63 >= i ? 63 - i : 0); if (i % 2 == 0) { allX[i / 2] = currAllX; @@ -79,12 +83,13 @@ namespace mongo { // allX[1] = 8000000000000000 // allX[2] = a000000000000000 // allX[3] = a800000000000000 - long long allX[32]; + // Note that 32 + 1 entries are needed, since 0 and 32 are both valid numbers of bits. + long long allX[33]; // Same alternating bits but starting with one from the MSB: // allY[1] = 4000000000000000 // allY[2] = 5000000000000000 // allY[3] = 5400000000000000 - long long allY[32]; + long long allY[33]; unsigned hashedToNormal[256]; }; @@ -105,6 +110,13 @@ namespace mongo { return 1LL << (63 - i); } + // Binary data is stored in some particular byte ordering that requires this. + static void copyAndReverse(char *dst, const char *src) { + for (unsigned a = 0; a < 8; a++) { + dst[a] = src[7 - a]; + } + } + // Definition unsigned int const GeoHash::kMaxBits = 32; @@ -139,7 +151,7 @@ namespace mongo { _bits = bits; if (e.type() == BinData) { int len = 0; - _copyAndReverse((char*)&_hash, e.binData(len)); + copyAndReverse((char*)&_hash, e.binData(len)); verify(len == 8); } else { cout << "GeoHash bad element: " << e << endl; @@ -258,7 +270,7 @@ namespace mongo { // TODO(hk): Comment this. BSONObj GeoHash::wrap(const char* name) const { BSONObjBuilder b(20); - appendToBuilder(&b, name); + appendHashMin(&b, name); BSONObj o = b.obj(); if ('\0' == name[0]) verify(o.objsize() == 20); return o; @@ -365,7 +377,12 @@ namespace mongo { } bool GeoHash::operator<(const GeoHash& h) const { - if (_hash != h._hash) return _hash < h._hash; + + if (_hash != h._hash) { + return static_cast<unsigned long long>(_hash) < + static_cast<unsigned long long>(h._hash); + } + return _bits < h._bits; } @@ -410,11 +427,25 @@ namespace mongo { _hash &= mask; } - // Append the hash to the builder provided. - void GeoHash::appendToBuilder(BSONObjBuilder* b, const char * name) const { + static void appendHashToBuilder(long long hash, + BSONObjBuilder* builder, + const char* fieldName) { char buf[8]; - _copyAndReverse(buf, (char*)&_hash); - b->appendBinData(name, 8, bdtCustom, buf); + copyAndReverse(buf, (char*) &hash); + builder->appendBinData(fieldName, 8, bdtCustom, buf); + } + + void GeoHash::appendHashMin(BSONObjBuilder* builder, const char* fieldName) const { + // The min bound of a GeoHash region has all the unused suffix bits set to 0 + appendHashToBuilder(_hash, builder, fieldName); + } + + void GeoHash::appendHashMax(BSONObjBuilder* builder, const char* fieldName) const { + // The max bound of a GeoHash region has all the unused suffix bits set to 1 + long long suffixMax = ~(geoBitSets.allX[_bits] | geoBitSets.allY[_bits]); + long long hashMax = _hash | suffixMax; + + appendHashToBuilder(hashMax, builder, fieldName); } long long GeoHash::getHash() const { @@ -464,14 +495,54 @@ namespace mongo { return GeoHash(_hash, _bits - 1); } - // Binary data is stored in some particular byte ordering that requires this. - void GeoHash::_copyAndReverse(char *dst, const char *src) { - for (unsigned a = 0; a < 8; a++) { - dst[a] = src[7 - a]; + static BSONField<int> bitsField("bits", 26); + static BSONField<double> maxField("max", 180.0); + static BSONField<double> minField("min", -180.0); + + Status GeoHashConverter::parseParameters(const BSONObj& paramDoc, + GeoHashConverter::Parameters* params) { + + string errMsg; + + if (FieldParser::FIELD_INVALID + == FieldParser::extractNumber(paramDoc, bitsField, ¶ms->bits, &errMsg)) { + return Status(ErrorCodes::InvalidOptions, errMsg); + } + + if (FieldParser::FIELD_INVALID + == FieldParser::extractNumber(paramDoc, maxField, ¶ms->max, &errMsg)) { + return Status(ErrorCodes::InvalidOptions, errMsg); + } + + if (FieldParser::FIELD_INVALID + == FieldParser::extractNumber(paramDoc, minField, ¶ms->min, &errMsg)) { + return Status(ErrorCodes::InvalidOptions, errMsg); } + + if (params->bits < 1 || params->bits > 32) { + return Status(ErrorCodes::InvalidOptions, + str::stream() << "bits for hash must be > 0 and <= 32, " + << "but " << params->bits << " bits were specified"); + } + + if (params->min >= params->max) { + return Status(ErrorCodes::InvalidOptions, + str::stream() << "region for hash must be valid and have positive area, " + << "but [" << params->min << ", " << params->max << "]" + << "was specified"); + } + + double numBuckets = (1024 * 1024 * 1024 * 4.0); + params->scaling = numBuckets / (params->max - params->min); + + return Status::OK(); + } + + GeoHashConverter::GeoHashConverter(const Parameters& params) : _params(params) { + init(); } - GeoHashConverter::GeoHashConverter(const Parameters ¶ms) : _params(params) { + void GeoHashConverter::init() { // TODO(hk): What do we require of the values in params? // Compute how much error there is so it can be used as a fudge factor. diff --git a/src/mongo/db/geo/hash.h b/src/mongo/db/geo/hash.h index 32a3f8aa0cc..95dbbf37d86 100644 --- a/src/mongo/db/geo/hash.h +++ b/src/mongo/db/geo/hash.h @@ -109,8 +109,11 @@ namespace mongo { GeoHash operator+(const char *s) const; GeoHash operator+(const std::string& s) const; - // Append the hash to the builder provided. - void appendToBuilder(BSONObjBuilder* b, const char * name) const; + // Append the minimum range of the hash to the builder provided (inclusive) + void appendHashMin(BSONObjBuilder* builder, const char* fieldName) const; + // Append the maximum range of the hash to the builder provided (inclusive) + void appendHashMax(BSONObjBuilder* builder, const char* fieldName) const; + long long getHash() const; unsigned getBits() const; @@ -126,9 +129,7 @@ namespace mongo { GeoHash parent() const; private: - // XXX not sure why this is done exactly. Why does binary - // data need to be reversed? byte ordering of some sort? - static void _copyAndReverse(char *dst, const char *src); + // Create a hash from the provided string. Used by the std::string and char* cons. void initFromString(const char *s); /* Keep the upper _bits*2 bits of _hash, clear the lower bits. @@ -167,6 +168,11 @@ namespace mongo { GeoHashConverter(const Parameters ¶ms); /** + * Returns hashing parameters parsed from a BSONObj + */ + static Status parseParameters(const BSONObj& paramDoc, Parameters* params); + + /** * Return converter parameterss which can be used to * construct an copy of this converter. */ @@ -220,6 +226,9 @@ namespace mongo { // XXX: understand/clean this. double sizeEdge(const GeoHash& a) const; private: + + void init(); + // Convert from an unsigned in [0, (max-min)*scaling] to [min, max] double convertFromHashScale(unsigned in) const; diff --git a/src/mongo/db/geo/r2_region_coverer_test.cpp b/src/mongo/db/geo/r2_region_coverer_test.cpp index 87a87edbd4e..07bd6aa5285 100644 --- a/src/mongo/db/geo/r2_region_coverer_test.cpp +++ b/src/mongo/db/geo/r2_region_coverer_test.cpp @@ -116,12 +116,35 @@ namespace { return params; } - class BoxRegion : public R2Region { + /** + * Test region which mimics the region of a geohash cell. + * NOTE: Technically this is not 100% correct, since geohash cells are inclusive on lower and + * exclusive on upper edges. For now, this region is just exclusive on all edges. + * TODO: Create an explicit HashCell which correctly encapsulates this behavior, push to the + * R2Region interface. + */ + class HashBoxRegion : public R2Region { public: - BoxRegion(Box box) : _box(box) { } + + HashBoxRegion(Box box) : _box(box) {} Box getR2Bounds() const { return _box; } - bool fastContains(const Box& other) const { return _box.contains(other); } - bool fastDisjoint(const Box& other) const { return !_box.intersects(other); } + + bool fastContains(const Box& other) const { + return _box.contains(other); + } + + bool fastDisjoint(const Box& other) const { + if (!_box.intersects(other)) + return true; + + // Make outer edges exclusive + if (_box._max.x == other._min.x || _box._min.x == other._max.x + || _box._max.y == other._min.y || _box._min.y == other._max.y) + return true; + + return false; + } + private: Box _box; }; @@ -135,7 +158,7 @@ namespace { GeoHash id( (long long) rand.nextInt64(), (unsigned) rand.nextInt32( GeoHash::kMaxBits + 1 ) ); vector<GeoHash> covering; - BoxRegion region(converter.unhashToBox(id)); + HashBoxRegion region(converter.unhashToBox(id)); coverer.getCovering(region, &covering); ASSERT_EQUALS( covering.size(), (size_t)1 ); ASSERT_EQUALS( covering[0], id ); @@ -213,12 +236,12 @@ namespace { } // Generate a circle within [0, MAXBOUND] - GeometryContainer getRandomCircle(double radius) { + GeometryContainer* getRandomCircle(double radius) { ASSERT_LESS_THAN(radius, MAXBOUND / 2); // Format: { $center : [ [-74, 40.74], 10 ] } - GeometryContainer container; - container.parseFrom(BSON("$center" + GeometryContainer* container = new GeometryContainer(); + container->parseFrom(BSON("$center" << BSON_ARRAY( BSON_ARRAY(randDouble(radius, MAXBOUND - radius) << randDouble(radius, MAXBOUND - radius)) @@ -240,8 +263,8 @@ namespace { coverer.setMaxLevel( coverer.minLevel() + 4 ); double radius = randDouble(0.0, MAXBOUND / 2); - GeometryContainer geometry = getRandomCircle(radius); - const R2Region& region = geometry.getR2Region(); + auto_ptr<GeometryContainer> geometry(getRandomCircle(radius)); + const R2Region& region = geometry->getR2Region(); vector<GeoHash> covering; coverer.getCovering(region, &covering); @@ -263,8 +286,8 @@ namespace { // 100 * 2 ^ -32 ~= 2.3E-8 (cell edge length) double radius = randDouble(1E-15, ldexp(100.0, -32) * 10); - GeometryContainer geometry = getRandomCircle(radius); - const R2Region& region = geometry.getR2Region(); + auto_ptr<GeometryContainer> geometry(getRandomCircle(radius)); + const R2Region& region = geometry->getR2Region(); vector<GeoHash> covering; coverer.getCovering(region, &covering); diff --git a/src/mongo/db/geo/shapes.cpp b/src/mongo/db/geo/shapes.cpp index b0562077fee..edcd338d966 100644 --- a/src/mongo/db/geo/shapes.cpp +++ b/src/mongo/db/geo/shapes.cpp @@ -125,7 +125,21 @@ namespace mongo { return true; } - double Box::intersects(const Box& other) const { + bool Box::intersects(const Box& other) const { + + bool intersectX = between(_min.x, _max.x, other._min.x) // contain part of other range + || between(_min.x, _max.x, other._max.x) // contain part of other range + || between(other._min.x, other._max.x, _min.x); // other range contains us + + bool intersectY = between(_min.y, _max.y, other._min.y) + || between(_min.y, _max.y, other._max.y) + || between(other._min.y, other._max.y, _min.y); + + return intersectX && intersectY; + } + + double Box::legacyIntersectFraction(const Box& other) const { + Point boundMin(0,0); Point boundMax(0,0); @@ -384,6 +398,41 @@ namespace mongo { return *_bounds; } + R2Annulus::R2Annulus() : + _inner(0.0), _outer(0.0) { + } + + R2Annulus::R2Annulus(const Point& center, double inner, double outer) : + _center(center), _inner(inner), _outer(outer) { + } + + const Point& R2Annulus::center() const { + return _center; + } + + double R2Annulus::getInner() const { + return _inner; + } + + double R2Annulus::getOuter() const { + return _outer; + } + + bool R2Annulus::contains(const Point& point, double maxError) const { + + // See if we're inside the inner radius + if (distanceWithin(point, _center, getInner() - maxError)) { + return false; + } + + // See if we're outside the outer radius + if (!distanceWithin(point, _center, getOuter() + maxError)) { + return false; + } + + return true; + } + /////// Other methods /** diff --git a/src/mongo/db/geo/shapes.h b/src/mongo/db/geo/shapes.h index 99594520a1d..2281a189fa8 100644 --- a/src/mongo/db/geo/shapes.h +++ b/src/mongo/db/geo/shapes.h @@ -94,21 +94,25 @@ namespace mongo { bool onBoundary(double bound, double val, double fudge = 0) const; bool mid(double amin, double amax, double bmin, double bmax, bool min, double* res) const; - double intersects(const Box& other) const; double area() const; double maxDim() const; Point center() const; + // NOTE: Box boundaries are *inclusive* bool onBoundary(Point p, double fudge = 0) const; bool inside(Point p, double fudge = 0) const; bool inside(double x, double y, double fudge = 0) const; bool contains(const Box& other, double fudge = 0) const; + bool intersects(const Box& other) const; // Box modifications void truncate(double min, double max); void fudge(double error); void expandToInclude(const Point& pt); + // TODO: Remove after 2D near dependency goes away + double legacyIntersectFraction(const Box& other) const; + Point _min; Point _max; }; @@ -183,6 +187,26 @@ namespace mongo { SPHERE }; + class R2Annulus { + public: + + R2Annulus(); + R2Annulus(const Point& center, double inner, double outer); + + const Point& center() const; + + double getInner() const; + double getOuter() const; + + bool contains(const Point& point, double maxError) const; + + private: + + Point _center; + double _inner; + double _outer; + }; + struct PointWithCRS { PointWithCRS() : crs(UNSET), flatUpgradedToSphere(false) {} diff --git a/src/mongo/db/index/expression_index.h b/src/mongo/db/index/expression_index.h index 4860c0e50c8..8dd5a7db569 100644 --- a/src/mongo/db/index/expression_index.h +++ b/src/mongo/db/index/expression_index.h @@ -29,7 +29,9 @@ #pragma once #include "mongo/db/jsobj.h" +#include "mongo/db/geo/hash.h" #include "mongo/db/geo/geoquery.h" +#include "mongo/db/geo/r2_region_coverer.h" #include "mongo/db/hasher.h" #include "mongo/db/query/index_bounds_builder.h" @@ -52,13 +54,31 @@ namespace mongo { const BSONObj& indexInfoObj, OrderedIntervalList* oil) { - BSONObjBuilder builder; - builder << "" << MINKEY; - builder << "" << MAXKEY; + GeoHashConverter::Parameters hashParams; + Status paramStatus = GeoHashConverter::parseParameters(indexInfoObj, &hashParams); + verify(paramStatus.isOK()); // We validated the parameters when creating the index - oil->intervals.push_back(IndexBoundsBuilder::makeRangeInterval(builder.obj(), - true, - true)); + GeoHashConverter hashConverter(hashParams); + R2RegionCoverer coverer(&hashConverter); + coverer.setMaxLevel(hashConverter.getBits()); + + // TODO: Maybe slightly optimize by returning results in order + vector<GeoHash> unorderedCovering; + coverer.getCovering(region, &unorderedCovering); + set<GeoHash> covering(unorderedCovering.begin(), unorderedCovering.end()); + + for (set<GeoHash>::const_iterator it = covering.begin(); it != covering.end(); + ++it) { + + const GeoHash& geoHash = *it; + BSONObjBuilder builder; + geoHash.appendHashMin(&builder, ""); + geoHash.appendHashMax(&builder, ""); + + oil->intervals.push_back(IndexBoundsBuilder::makeRangeInterval(builder.obj(), + true, + true)); + } } // TODO: what should we really pass in for indexInfoObj? diff --git a/src/mongo/db/index/expression_keys_private.cpp b/src/mongo/db/index/expression_keys_private.cpp index e12f4c8dd8d..b42d3949a34 100644 --- a/src/mongo/db/index/expression_keys_private.cpp +++ b/src/mongo/db/index/expression_keys_private.cpp @@ -269,7 +269,7 @@ namespace mongo { else continue; } - params.geoHashConverter->hash(locObj, &obj).appendToBuilder(&b, ""); + params.geoHashConverter->hash(locObj, &obj).appendHashMin(&b, ""); // Go through all the other index keys for (vector<pair<string, int> >::const_iterator i = params.other.begin(); diff --git a/src/mongo/db/index/expression_params.h b/src/mongo/db/index/expression_params.h index 83e23f2778a..f8fdf818755 100644 --- a/src/mongo/db/index/expression_params.h +++ b/src/mongo/db/index/expression_params.h @@ -56,15 +56,9 @@ namespace mongo { uassert(16802, "no geo field specified", out->geo.size()); - double bits = configValueWithDefaultDouble(infoObj, "bits", 26); // for lat/long, ~ 1ft - uassert(16803, "bits in geo index must be between 1 and 32", bits > 0 && bits <= 32); - GeoHashConverter::Parameters hashParams; - hashParams.bits = static_cast<unsigned>(bits); - hashParams.max = configValueWithDefaultDouble(infoObj, "max", 180.0); - hashParams.min = configValueWithDefaultDouble(infoObj, "min", -180.0); - double numBuckets = (1024 * 1024 * 1024 * 4.0); - hashParams.scaling = numBuckets / (hashParams.max - hashParams.min); + Status paramStatus = GeoHashConverter::parseParameters(infoObj, &hashParams); + uassertStatusOK(paramStatus); out->geoHashConverter.reset(new GeoHashConverter(hashParams)); } diff --git a/src/mongo/db/matcher/expression_geo.cpp b/src/mongo/db/matcher/expression_geo.cpp index 2289fb19c56..c701d0916dc 100644 --- a/src/mongo/db/matcher/expression_geo.cpp +++ b/src/mongo/db/matcher/expression_geo.cpp @@ -37,9 +37,9 @@ namespace mongo { // Geo queries we don't need an index to answer: geoWithin and geoIntersects // - Status GeoMatchExpression::init( const StringData& path, const GeoQuery& query, + Status GeoMatchExpression::init( const StringData& path, const GeoQuery* query, const BSONObj& rawObj ) { - _query = query; + _query.reset(query); _rawObj = rawObj; return initPath( path ); } @@ -52,12 +52,12 @@ namespace mongo { if ( !geometry.parseFrom( e.Obj() ) ) return false; - if (GeoQuery::WITHIN == _query.getPred()) { - return _query.getGeometry().contains(geometry); + if (GeoQuery::WITHIN == _query->getPred()) { + return _query->getGeometry().contains(geometry); } else { - verify(GeoQuery::INTERSECT == _query.getPred()); - return _query.getGeometry().intersects(geometry); + verify(GeoQuery::INTERSECT == _query->getPred()); + return _query->getGeometry().intersects(geometry); } } @@ -88,7 +88,8 @@ namespace mongo { LeafMatchExpression* GeoMatchExpression::shallowClone() const { GeoMatchExpression* next = new GeoMatchExpression(); - next->init( path(), _query, _rawObj); + next->init( path(), NULL, _rawObj); + next->_query = _query; if (getTag()) { next->setTag(getTag()->clone()); } diff --git a/src/mongo/db/matcher/expression_geo.h b/src/mongo/db/matcher/expression_geo.h index d67edc91919..3a3121a728a 100644 --- a/src/mongo/db/matcher/expression_geo.h +++ b/src/mongo/db/matcher/expression_geo.h @@ -42,7 +42,10 @@ namespace mongo { GeoMatchExpression() : LeafMatchExpression( GEO ){} virtual ~GeoMatchExpression(){} - Status init( const StringData& path, const GeoQuery& query, const BSONObj& rawObj ); + /** + * Takes ownership of the passed-in GeoQuery. + */ + Status init( const StringData& path, const GeoQuery* query, const BSONObj& rawObj ); virtual bool matchesSingleElement( const BSONElement& e ) const; @@ -52,12 +55,13 @@ namespace mongo { virtual LeafMatchExpression* shallowClone() const; - const GeoQuery& getGeoQuery() const { return _query; } + const GeoQuery& getGeoQuery() const { return *_query; } const BSONObj getRawObj() const { return _rawObj; } private: BSONObj _rawObj; - GeoQuery _query; + // Share ownership of our query with all of our clones + shared_ptr<const GeoQuery> _query; }; class GeoNearMatchExpression : public LeafMatchExpression { diff --git a/src/mongo/db/matcher/expression_geo_test.cpp b/src/mongo/db/matcher/expression_geo_test.cpp index 6f22f47c20f..7fe244d555a 100644 --- a/src/mongo/db/matcher/expression_geo_test.cpp +++ b/src/mongo/db/matcher/expression_geo_test.cpp @@ -43,11 +43,11 @@ namespace mongo { TEST( ExpressionGeoTest, Geo1 ) { BSONObj query = fromjson("{loc:{$within:{$box:[{x: 4, y:4},[6,6]]}}}"); - GeoQuery gq; - ASSERT( gq.parseFrom( query["loc"].Obj() ) ); + auto_ptr<GeoQuery> gq(new GeoQuery); + ASSERT( gq->parseFrom( query["loc"].Obj() ) ); GeoMatchExpression ge; - ASSERT( ge.init("a", gq, query ).isOK() ); + ASSERT( ge.init("a", gq.release(), query ).isOK() ); ASSERT(!ge.matchesBSON(fromjson("{a: [3,4]}"))); ASSERT(ge.matchesBSON(fromjson("{a: [4,4]}"))); diff --git a/src/mongo/db/matcher/expression_parser_geo.cpp b/src/mongo/db/matcher/expression_parser_geo.cpp index ae238b500ff..ccbfa10dd22 100644 --- a/src/mongo/db/matcher/expression_parser_geo.cpp +++ b/src/mongo/db/matcher/expression_parser_geo.cpp @@ -42,8 +42,8 @@ namespace mongo { int type, const BSONObj& section ) { if (BSONObj::opWITHIN == type || BSONObj::opGEO_INTERSECTS == type) { - GeoQuery gq(name); - if ( !gq.parseFrom( section ) ) + auto_ptr<GeoQuery> gq(new GeoQuery(name)); + if ( !gq->parseFrom( section ) ) return StatusWithMatchExpression( ErrorCodes::BadValue, "bad geo query" ); auto_ptr<GeoMatchExpression> e( new GeoMatchExpression() ); @@ -53,7 +53,7 @@ namespace mongo { // layer. BSONObjBuilder bob; bob.append(name, section); - Status s = e->init( name, gq, bob.obj() ); + Status s = e->init( name, gq.release(), bob.obj() ); if ( !s.isOK() ) return StatusWithMatchExpression( s ); return StatusWithMatchExpression( e.release() ); diff --git a/src/mongo/db/query/explain_plan.cpp b/src/mongo/db/query/explain_plan.cpp index 3a29a6f8502..1e15efd37f1 100644 --- a/src/mongo/db/query/explain_plan.cpp +++ b/src/mongo/db/query/explain_plan.cpp @@ -235,30 +235,6 @@ namespace mongo { res->setIndexOnly(false); res->setIsMultiKey(false); } - else if (leaf->stageType == STAGE_GEO_2D) { - // Cursor name depends on type of GeoBrowse. - // TODO: We could omit the shape from the cursor name. - TwoDStats* nStats = static_cast<TwoDStats*>(leaf->specific.get()); - res->setCursor("GeoBrowse-" + nStats->type); - res->setNScanned(leaf->common.works); - res->setNScannedObjects(leaf->common.works); - - // Generate index bounds from prefixes. - GeoHashConverter converter(nStats->converterParams); - BSONObjBuilder bob; - BSONArrayBuilder arrayBob(bob.subarrayStart(nStats->field)); - for (size_t i = 0; i < nStats->expPrefixes.size(); ++i) { - const GeoHash& prefix = nStats->expPrefixes[i]; - Box box = converter.unhashToBox(prefix); - arrayBob.append(box.toBSON()); - } - arrayBob.doneFast(); - res->setIndexBounds(bob.obj()); - - // TODO: Could be multikey. - res->setIsMultiKey(false); - res->setIndexOnly(false); - } else if (leaf->stageType == STAGE_GEO_NEAR_2DSPHERE) { // TODO: This is kind of a lie for STAGE_GEO_NEAR_2DSPHERE. res->setCursor("S2NearCursor"); @@ -422,8 +398,6 @@ namespace mongo { return "DISTINCT"; case STAGE_FETCH: return "FETCH"; - case STAGE_GEO_2D: - return "GEO_2D"; case STAGE_GEO_NEAR_2D: return "GEO_NEAR_2D"; case STAGE_GEO_NEAR_2DSPHERE: @@ -507,20 +481,6 @@ namespace mongo { bob->appendNumber("forcedFetches", spec->forcedFetches); bob->appendNumber("matchTested", spec->matchTested); } - else if (STAGE_GEO_2D == stats.stageType) { - TwoDStats* spec = static_cast<TwoDStats*>(stats.specific.get()); - bob->append("geometryType", spec->type); - bob->append("field", spec->field); - - // Generate verbose index bounds from prefixes - GeoHashConverter converter(spec->converterParams); - BSONArrayBuilder arrayBob(bob->subarrayStart("boundsVerbose")); - for (size_t i = 0; i < spec->expPrefixes.size(); ++i) { - const GeoHash& prefix = spec->expPrefixes[i]; - Box box = converter.unhashToBox(prefix); - arrayBob.append(box.toString()); - } - } else if (STAGE_GEO_NEAR_2D == stats.stageType) { TwoDNearStats* spec = static_cast<TwoDNearStats*>(stats.specific.get()); bob->appendNumber("objectsLoaded", spec->objectsLoaded); @@ -615,10 +575,6 @@ namespace mongo { const DistinctNode* dn = static_cast<const DistinctNode*>(node); leafInfo << " " << dn->indexKeyPattern; } - else if (STAGE_GEO_2D == node->getType()) { - const Geo2DNode* g2d = static_cast<const Geo2DNode*>(node); - leafInfo << " " << g2d->indexKeyPattern; - } else if (STAGE_GEO_NEAR_2D == node->getType()) { const GeoNear2DNode* g2dnear = static_cast<const GeoNear2DNode*>(node); leafInfo << " " << g2dnear->indexKeyPattern; diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp index 3ec41de9806..63e1f7571a5 100644 --- a/src/mongo/db/query/index_bounds_builder.cpp +++ b/src/mongo/db/query/index_bounds_builder.cpp @@ -572,17 +572,26 @@ namespace mongo { unionize(oilOut); } else if (MatchExpression::GEO == expr->matchType()) { + const GeoMatchExpression* gme = static_cast<const GeoMatchExpression*>(expr); - // Can only do this for 2dsphere. - if (!mongoutils::str::equals("2dsphere", elt.valuestrsafe())) { - warning() << "Planner error, trying to build geo bounds for non-2dsphere" - << " index element: " << elt.toString() << endl; + + if (mongoutils::str::equals("2dsphere", elt.valuestrsafe())) { + verify(gme->getGeoQuery().getGeometry().hasS2Region()); + const S2Region& region = gme->getGeoQuery().getGeometry().getS2Region(); + ExpressionMapping::cover2dsphere(region, index.infoObj, oilOut); + *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH; + } + else if (mongoutils::str::equals("2d", elt.valuestrsafe())) { + verify(gme->getGeoQuery().getGeometry().hasR2Region()); + const R2Region& region = gme->getGeoQuery().getGeometry().getR2Region(); + ExpressionMapping::cover2d(region, index.infoObj, oilOut); + *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH; + } + else { + warning() << "Planner error trying to build geo bounds for " << elt.toString() + << " index element."; verify(0); } - - const S2Region& region = gme->getGeoQuery().getGeometry().getS2Region(); - ExpressionMapping::cover2dsphere(region, index.infoObj, oilOut); - *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH; } else { warning() << "Planner error, trying to build bounds for expression: " @@ -891,7 +900,7 @@ namespace mongo { } if (!bounds->isValidFor(kp, scanDir)) { - QLOG() << "INVALID BOUNDS: " << bounds->toString() << endl + log() << "INVALID BOUNDS: " << bounds->toString() << endl << "kp = " << kp.toString() << endl << "scanDir = " << scanDir << endl; verify(0); diff --git a/src/mongo/db/query/plan_cache_test.cpp b/src/mongo/db/query/plan_cache_test.cpp index 8a25e9b00e3..7a1d1cd03af 100644 --- a/src/mongo/db/query/plan_cache_test.cpp +++ b/src/mongo/db/query/plan_cache_test.cpp @@ -1003,22 +1003,22 @@ namespace { // Polygon query = fromjson("{a : { $within: { $polygon : [[0,0], [2,0], [4,0]] } }}"); runQuery(query); - assertNotCached("{fetch: {node: {geo2d: {a: '2d'}}}}"); + assertNotCached("{fetch: {node: {ixscan: {pattern: {a: '2d'}}}}}"); // Center query = fromjson("{a : { $within : { $center : [[ 5, 5 ], 7 ] } }}"); runQuery(query); - assertNotCached("{fetch: {node: {geo2d: {a: '2d'}}}}"); + assertNotCached("{fetch: {node: {ixscan: {pattern: {a: '2d'}}}}}"); // Centersphere query = fromjson("{a : { $within : { $centerSphere : [[ 10, 20 ], 0.01 ] } }}"); runQuery(query); - assertNotCached("{fetch: {node: {geo2d: {a: '2d'}}}}"); + assertNotCached("{fetch: {node: {ixscan: {pattern: {a: '2d'}}}}}"); // Within box. query = fromjson("{a : {$within: {$box : [[0,0],[9,9]]}}}"); runQuery(query); - assertNotCached("{fetch: {node: {geo2d: {a: '2d'}}}}"); + assertNotCached("{fetch: {node: {ixscan: {pattern: {a: '2d'}}}}}"); } TEST_F(CachePlanSelectionTest, Or2DNonNearNotCached) { @@ -1028,7 +1028,8 @@ namespace { " {b : { $within : { $center : [[ 5, 5 ], 7 ] } }} ]}"); runQuery(query); - assertNotCached("{fetch: {node: {or: {nodes: [{geo2d: {a: '2d'}}, {geo2d: {b: '2d'}}]}}}}"); + assertNotCached("{or: {nodes: [{fetch: {node: {ixscan: {pattern: {a: '2d'}}}}}," + "{fetch: {node: {ixscan: {pattern: {b: '2d'}}}}}]}}"); } } // namespace diff --git a/src/mongo/db/query/planner_access.cpp b/src/mongo/db/query/planner_access.cpp index 705f25d6aad..5e59b6e34e0 100644 --- a/src/mongo/db/query/planner_access.cpp +++ b/src/mongo/db/query/planner_access.cpp @@ -105,16 +105,18 @@ namespace mongo { // This should gracefully deal with the case where we have a pred over foo but no geo clause // over bar. In that case there is no GEO_NEAR to appear first and it's treated like a // straight ixscan. - BSONElement elt = index.keyPattern.firstElement(); - bool indexIs2D = (String == elt.type() && "2d" == elt.String()); if (MatchExpression::GEO_NEAR == expr->matchType()) { // We must not keep the expression node around. *tightnessOut = IndexBoundsBuilder::EXACT; GeoNearMatchExpression* nearExpr = static_cast<GeoNearMatchExpression*>(expr); + // 2d geoNear requires a hard limit and as such we take it out before it gets here. If // this happens it's a bug. + BSONElement elt = index.keyPattern.firstElement(); + bool indexIs2D = (String == elt.type() && "2d" == elt.String()); verify(!indexIs2D); + GeoNear2DSphereNode* ret = new GeoNear2DSphereNode(); ret->indexKeyPattern = index.keyPattern; ret->nq = nearExpr->getData(); @@ -125,17 +127,6 @@ namespace mongo { } return ret; } - else if (indexIs2D) { - // We must not keep the expression node around. - *tightnessOut = IndexBoundsBuilder::EXACT; - verify(MatchExpression::GEO == expr->matchType()); - GeoMatchExpression* nearExpr = static_cast<GeoMatchExpression*>(expr); - verify(indexIs2D); - Geo2DNode* ret = new Geo2DNode(); - ret->indexKeyPattern = index.keyPattern; - ret->gq = nearExpr->getGeoQuery(); - return ret; - } else if (MatchExpression::TEXT == expr->matchType()) { // We must not keep the expression node around. *tightnessOut = IndexBoundsBuilder::EXACT; @@ -206,13 +197,6 @@ namespace mongo { // by adding a filter to the special leaf type. // - if (STAGE_GEO_2D == type) { - // Don't merge GEO with a geo leaf. Instead, we will generate an AND_HASH solution - // with two separate leaves. - return MatchExpression::AND == mergeType - && MatchExpression::GEO != exprType; - } - if (STAGE_TEXT == type) { // Currently only one text predicate is allowed, but to be safe, make sure that we // do not try to merge two text predicates. @@ -268,11 +252,6 @@ namespace mongo { const StageType type = node->getType(); verify(STAGE_GEO_NEAR_2D != type); - if (STAGE_GEO_2D == type) { - scanState->tightness = IndexBoundsBuilder::INEXACT_FETCH; - return; - } - // Text data is covered, but not exactly. Text covering is unlike any other covering // so we deal with it in addFilterToSolutionNode. if (STAGE_TEXT == type) { @@ -289,6 +268,14 @@ namespace mongo { else { verify(type == STAGE_IXSCAN); IndexScanNode* scan = static_cast<IndexScanNode*>(node); + + // 2D indexes can only support additional non-geometric criteria by filtering after the + // initial element - don't generate bounds if this is not the first field + if (INDEX_2D == index.type && pos > 0) { + scanState->tightness = IndexBoundsBuilder::INEXACT_COVERED; + return; + } + boundsToFillOut = &scan->bounds; } @@ -478,10 +465,6 @@ namespace mongo { const StageType type = node->getType(); verify(STAGE_GEO_NEAR_2D != type); - if (STAGE_GEO_2D == type) { - return; - } - if (STAGE_TEXT == type) { finishTextNode(node, index); return; diff --git a/src/mongo/db/query/planner_analysis.cpp b/src/mongo/db/query/planner_analysis.cpp index c5607b3bfa8..68767dd1cb9 100644 --- a/src/mongo/db/query/planner_analysis.cpp +++ b/src/mongo/db/query/planner_analysis.cpp @@ -546,8 +546,7 @@ namespace mongo { // Only these stages can produce flagged results. A stage has to hold state past one call // to work(...) in order to possibly flag a result. - bool couldProduceFlagged = hasNode(solnRoot, STAGE_GEO_2D) - || hasAndHashStage + bool couldProduceFlagged = hasAndHashStage || hasNode(solnRoot, STAGE_AND_SORTED) || hasNode(solnRoot, STAGE_FETCH); diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp index e8d900851b6..464bffce401 100644 --- a/src/mongo/db/query/planner_ixselect.cpp +++ b/src/mongo/db/query/planner_ixselect.cpp @@ -53,14 +53,12 @@ namespace mongo { * 2d indices don't handle wrapping so we can't use them for queries that wrap. */ static bool twoDWontWrap(const Circle& circle, const IndexEntry& index) { - GeoHashConverter::Parameters params; - params.bits = static_cast<unsigned>(fieldWithDefault(index.infoObj, "bits", 26)); - params.max = fieldWithDefault(index.infoObj, "max", 180.0); - params.min = fieldWithDefault(index.infoObj, "min", -180.0); - double numBuckets = (1024 * 1024 * 1024 * 4.0); - params.scaling = numBuckets / (params.max - params.min); - - GeoHashConverter conv(params); + + GeoHashConverter::Parameters hashParams; + Status paramStatus = GeoHashConverter::parseParameters(index.infoObj, &hashParams); + verify(paramStatus.isOK()); // we validated the params on index creation + + GeoHashConverter conv(hashParams); // FYI: old code used flat not spherical error. double yscandist = rad2deg(circle.radius) + conv.getErrorSphere(); diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp index 29648c77598..eaec8ea0399 100644 --- a/src/mongo/db/query/query_planner_test.cpp +++ b/src/mongo/db/query/query_planner_test.cpp @@ -1737,25 +1737,25 @@ namespace { runQuery(fromjson("{a : { $within: { $polygon : [[0,0], [2,0], [4,0]] } }}")); assertNumSolutions(2U); assertSolutionExists("{cscan: {dir: 1}}"); - assertSolutionExists("{fetch: {node: {geo2d: {a: '2d'}}}}"); + assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: '2d'}}}}}"); // Center runQuery(fromjson("{a : { $within : { $center : [[ 5, 5 ], 7 ] } }}")); assertNumSolutions(2U); assertSolutionExists("{cscan: {dir: 1}}"); - assertSolutionExists("{fetch: {node: {geo2d: {a: '2d'}}}}"); + assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: '2d'}}}}}"); // Centersphere runQuery(fromjson("{a : { $within : { $centerSphere : [[ 10, 20 ], 0.01 ] } }}")); assertNumSolutions(2U); assertSolutionExists("{cscan: {dir: 1}}"); - assertSolutionExists("{fetch: {node: {geo2d: {a: '2d'}}}}"); + assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: '2d'}}}}}"); // Within box. runQuery(fromjson("{a : {$within: {$box : [[0,0],[9,9]]}}}")); assertNumSolutions(2U); assertSolutionExists("{cscan: {dir: 1}}"); - assertSolutionExists("{fetch: {node: {geo2d: {a: '2d'}}}}"); + assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: '2d'}}}}}"); // TODO: test that we *don't* annotate for things we shouldn't. } @@ -1771,6 +1771,20 @@ namespace { assertSolutionExists("{fetch: {node: {geoNear2dsphere: {loc: '2dsphere'}}}}"); } + TEST_F(QueryPlannerTest, Basic2DCompound) { + addIndex(BSON("loc" << "2d" << "a" << 1)); + + runQuery(fromjson("{ loc: { $geoWithin: { $box : [[0, 0],[10, 10]] } }," + "a: 'mouse' }")); + assertNumSolutions(2U); + assertSolutionExists("{cscan: {dir: 1}}"); + assertSolutionExists("{fetch: {node: {ixscan: {pattern: {loc : '2d', a: 1}," + "filter: {a: 'mouse'}," + "bounds: {loc: []," // Ignored since complex + " a: [['MinKey','MaxKey',true,true]]}" + "}}}}"); + } + TEST_F(QueryPlannerTest, Multikey2DSphereCompound) { // true means multikey addIndex(BSON("a" << 1 << "b" << 1), true); @@ -1907,7 +1921,8 @@ namespace { assertNumSolutions(2U); assertSolutionExists("{cscan: {dir: 1}}"); - assertSolutionExists("{fetch: {node: {or: {nodes: [{geo2d: {a: '2d'}}, {geo2d: {b: '2d'}}]}}}}"); + assertSolutionExists("{or: {nodes: [{fetch: {node: {ixscan: {pattern: {a: '2d'}}}}}," + "{fetch: {node: {ixscan: {pattern: {b: '2d'}}}}}]}}"); } // SERVER-3984, $or 2d index @@ -1918,7 +1933,7 @@ namespace { assertNumSolutions(2U); assertSolutionExists("{cscan: {dir: 1}}"); - assertSolutionExists("{fetch: {node: {or: {nodes: [{geo2d: {a: '2d'}}, {geo2d: {a: '2d'}}]}}}}"); + assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: '2d'}}}}}"); } // SERVER-3984, $or 2dsphere index @@ -1957,8 +1972,9 @@ namespace { assertNumSolutions(2U); assertSolutionExists("{cscan: {dir: 1}}"); - assertSolutionExists("{fetch: {node: {andHash: {nodes: [" - "{geo2d: {a: '2d'}}, {geo2d: {a: '2d'}}]}}}}"); + // Bounds of the two 2d geo predicates are combined into + // a single index scan. + assertSolutionExists("{fetch: {node: {ixscan: {pattern: {a: '2d'}}}}}"); } TEST_F(QueryPlannerTest, And2DWith2DNearSameField) { diff --git a/src/mongo/db/query/query_planner_test_lib.cpp b/src/mongo/db/query/query_planner_test_lib.cpp index 2fe75527574..134392e34d9 100644 --- a/src/mongo/db/query/query_planner_test_lib.cpp +++ b/src/mongo/db/query/query_planner_test_lib.cpp @@ -248,13 +248,6 @@ namespace mongo { } return filterMatches(filter.Obj(), trueSoln); } - else if (STAGE_GEO_2D == trueSoln->getType()) { - const Geo2DNode* node = static_cast<const Geo2DNode*>(trueSoln); - BSONElement el = testSoln["geo2d"]; - if (el.eoo() || !el.isABSONObj()) { return false; } - BSONObj geoObj = el.Obj(); - return geoObj == node->indexKeyPattern; - } else if (STAGE_GEO_NEAR_2D == trueSoln->getType()) { const GeoNear2DNode* node = static_cast<const GeoNear2DNode*>(trueSoln); BSONElement el = testSoln["geoNear2d"]; diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp index 9192760d51c..e3fef1dead7 100644 --- a/src/mongo/db/query/query_solution.cpp +++ b/src/mongo/db/query/query_solution.cpp @@ -750,39 +750,6 @@ namespace mongo { } // - // Geo2DNode - // - - void Geo2DNode::appendToString(mongoutils::str::stream* ss, int indent) const { - addIndent(ss, indent); - *ss << "GEO_2D\n"; - addIndent(ss, indent + 1); - *ss << "keyPattern = " << indexKeyPattern.toString() << '\n'; - addCommon(ss, indent); - } - - bool Geo2DNode::hasField(const string& field) const { - BSONObjIterator it(indexKeyPattern); - while (it.more()) { - if (field == it.next().fieldName()) { - return true; - } - } - return false; - } - - QuerySolutionNode* Geo2DNode::clone() const { - Geo2DNode* copy = new Geo2DNode(); - cloneBaseData(copy); - - copy->_sorts = this->_sorts; - copy->indexKeyPattern = this->indexKeyPattern; - copy->gq = this->gq; - - return copy; - } - - // // ShardingFilterNode // diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h index 6000c823528..096b35473d8 100644 --- a/src/mongo/db/query/query_solution.h +++ b/src/mongo/db/query/query_solution.h @@ -562,31 +562,6 @@ namespace mongo { int skip; }; - // - // Geo nodes. A thin wrapper above an IXSCAN until we can yank functionality out of - // the IXSCAN layer into the stage layer. - // - - // TODO: This is probably an expression index. - struct Geo2DNode : public QuerySolutionNode { - Geo2DNode() { } - virtual ~Geo2DNode() { } - - virtual StageType getType() const { return STAGE_GEO_2D; } - virtual void appendToString(mongoutils::str::stream* ss, int indent) const; - - bool fetched() const { return false; } - bool hasField(const std::string& field) const; - bool sortedByDiskLoc() const { return false; } - const BSONObjSet& getSort() const { return _sorts; } - BSONObjSet _sorts; - - QuerySolutionNode* clone() const; - - BSONObj indexKeyPattern; - GeoQuery gq; - }; - // This is a standalone stage. struct GeoNear2DNode : public QuerySolutionNode { GeoNear2DNode() : numWanted(100), addPointMeta(false), addDistMeta(false) { } diff --git a/src/mongo/db/query/stage_builder.cpp b/src/mongo/db/query/stage_builder.cpp index 0640590f063..a332088c1b2 100644 --- a/src/mongo/db/query/stage_builder.cpp +++ b/src/mongo/db/query/stage_builder.cpp @@ -29,7 +29,6 @@ #include "mongo/db/query/stage_builder.h" #include "mongo/db/client.h" -#include "mongo/db/exec/2d.h" #include "mongo/db/exec/2dnear.h" #include "mongo/db/exec/and_hash.h" #include "mongo/db/exec/and_sorted.h" @@ -189,15 +188,6 @@ namespace mongo { } return ret.release(); } - else if (STAGE_GEO_2D == root->getType()) { - const Geo2DNode* node = static_cast<const Geo2DNode*>(root); - TwoDParams params; - params.gq = node->gq; - params.filter = node->filter.get(); - params.indexKeyPattern = node->indexKeyPattern; - params.collection = collection; - return new TwoD(params, ws); - } else if (STAGE_GEO_NEAR_2D == root->getType()) { const GeoNear2DNode* node = static_cast<const GeoNear2DNode*>(root); TwoDNearParams params; diff --git a/src/mongo/db/query/stage_types.h b/src/mongo/db/query/stage_types.h index 901f804190f..62729bd7990 100644 --- a/src/mongo/db/query/stage_types.h +++ b/src/mongo/db/query/stage_types.h @@ -54,10 +54,6 @@ namespace mongo { STAGE_FETCH, - // TODO: This is secretly an expression index but we need geometry -> covering for our - // geohash. - STAGE_GEO_2D, - // The two $geoNear impls imply a fetch+sort and must be stages. STAGE_GEO_NEAR_2D, STAGE_GEO_NEAR_2DSPHERE, |