diff options
author | Hari Khalsa <hkhalsa@10gen.com> | 2013-12-10 13:15:29 -0500 |
---|---|---|
committer | Hari Khalsa <hkhalsa@10gen.com> | 2013-12-11 14:19:22 -0500 |
commit | 76e5458c48460de585bbde25c87bd4046c67198b (patch) | |
tree | 2f69fdd7463ee698646b06e37b3887974a166c9c /src/mongo/db | |
parent | be7c5f961bd163cb315c561ebd5a47a3b54dcfe8 (diff) | |
download | mongo-76e5458c48460de585bbde25c87bd4046c67198b.tar.gz |
SERVER-10026 migrate geoNear to new exec via rewrite
Diffstat (limited to 'src/mongo/db')
34 files changed, 588 insertions, 3592 deletions
diff --git a/src/mongo/db/commands/geonear.cpp b/src/mongo/db/commands/geonear.cpp new file mode 100644 index 00000000000..44a445a6b4a --- /dev/null +++ b/src/mongo/db/commands/geonear.cpp @@ -0,0 +1,295 @@ +/** +* Copyright (C) 2012 10gen Inc. +* +* This program is free software: you can redistribute it and/or modify +* it under the terms of the GNU Affero General Public License, version 3, +* as published by the Free Software Foundation. +* +* This program is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU Affero General Public License for more details. +* +* You should have received a copy of the GNU Affero General Public License +* along with this program. If not, see <http://www.gnu.org/licenses/>. +* +* 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 <vector> + +#include "mongo/db/auth/action_set.h" +#include "mongo/db/auth/action_type.h" +#include "mongo/db/auth/privilege.h" +#include "mongo/db/commands.h" +#include "mongo/db/curop.h" +#include "mongo/db/geo/geoconstants.h" +#include "mongo/db/geo/geoquery.h" +#include "mongo/db/geo/s2common.h" +#include "mongo/db/index_names.h" +#include "mongo/db/index/index_descriptor.h" +#include "mongo/db/jsobj.h" +#include "mongo/db/namespace_details.h" +#include "mongo/db/pdfile.h" +#include "mongo/db/query/get_runner.h" +#include "mongo/db/query/type_explain.h" +#include "mongo/db/structure/collection.h" +#include "mongo/platform/unordered_map.h" + +namespace mongo { + + class Geo2dFindNearCmd : public Command { + public: + Geo2dFindNearCmd() : Command("geoNear") {} + + virtual LockType locktype() const { return READ; } + bool slaveOk() const { return true; } + bool slaveOverrideOk() const { return true; } + + void help(stringstream& h) const { + h << "http://dochub.mongodb.org/core/geo#GeospatialIndexing-geoNearCommand"; + } + + virtual void addRequiredPrivileges(const std::string& dbname, + const BSONObj& cmdObj, + std::vector<Privilege>* out) { + ActionSet actions; + actions.addAction(ActionType::find); + out->push_back(Privilege(parseResourcePattern(dbname, cmdObj), actions)); + } + + bool run(const string& dbname, BSONObj& cmdObj, int, string& errmsg, BSONObjBuilder& result, bool fromRepl) { + string ns = dbname + "." + cmdObj.firstElement().valuestr(); + + if (!cmdObj["start"].eoo()) { + errmsg = "using deprecated 'start' argument to geoNear"; + return false; + } + + Database* db = cc().database(); + if ( !db ) { + errmsg = "can't find ns"; + return false; + } + + Collection* collection = db->getCollection( ns ); + if ( !collection ) { + errmsg = "can't find ns"; + return false; + } + + IndexCatalog* indexCatalog = collection->getIndexCatalog(); + + // cout << "raw cmd " << cmdObj.toString() << endl; + + // We seek to populate this. + string nearFieldName; + bool using2DIndex = false; + if (!getFieldName(collection, indexCatalog, &nearFieldName, &errmsg, &using2DIndex)) { + return false; + } + + uassert(17304, "'near' field must be point", + !cmdObj["near"].eoo() && cmdObj["near"].isABSONObj() + && GeoParser::isPoint(cmdObj["near"].Obj())); + + bool isSpherical = cmdObj["spherical"].trueValue(); + if (!using2DIndex) { + uassert(17301, "2dsphere index must have spherical: true", isSpherical); + } + + // Build the $near expression for the query. + BSONObjBuilder nearBob; + if (isSpherical) { + nearBob.append("$nearSphere", cmdObj["near"].Obj()); + } + else { + nearBob.append("$near", cmdObj["near"].Obj()); + } + + if (!cmdObj["maxDistance"].eoo()) { + uassert(17299, "maxDistance must be a number",cmdObj["maxDistance"].isNumber()); + nearBob.append("$maxDistance", cmdObj["maxDistance"].number()); + } + + if (!cmdObj["minDistance"].eoo()) { + uassert(17298, "minDistance doesn't work on 2d index", !using2DIndex); + uassert(17300, "minDistance must be a number",cmdObj["minDistance"].isNumber()); + nearBob.append("$minDistance", cmdObj["minDistance"].number()); + } + + if (!cmdObj["uniqueDocs"].eoo()) { + nearBob.append("$uniqueDocs", cmdObj["uniqueDocs"].trueValue()); + } + + // And, build the full query expression. + BSONObjBuilder queryBob; + queryBob.append(nearFieldName, nearBob.obj()); + if (!cmdObj["query"].eoo() && cmdObj["query"].isABSONObj()) { + queryBob.appendElements(cmdObj["query"].Obj()); + } + BSONObj rewritten = queryBob.obj(); + + // cout << "rewritten query: " << rewritten.toString() << endl; + + int numWanted = 100; + const char* limitName = !cmdObj["num"].eoo() ? "num" : "limit"; + BSONElement eNumWanted = cmdObj[limitName]; + if (!eNumWanted.eoo()) { + uassert(17303, "limit must be number", eNumWanted.isNumber()); + numWanted = eNumWanted.numberInt(); + uassert(17302, "limit must be >=0", numWanted >= 0); + } + + bool includeLocs = false; + if (!cmdObj["includeLocs"].eoo()) { + includeLocs = cmdObj["includeLocs"].trueValue(); + } + + double distanceMultiplier = 1.0; + BSONElement eDistanceMultiplier = cmdObj["distanceMultiplier"]; + if (!eDistanceMultiplier.eoo()) { + uassert(17296, "distanceMultiplier must be a number", eDistanceMultiplier.isNumber()); + distanceMultiplier = eDistanceMultiplier.number(); + uassert(17297, "distanceMultiplier must be non-negative", distanceMultiplier >= 0); + } + + BSONObj projObj = BSON("$pt" << BSON("$meta" << "geoNearPoint") << + "$dis" << BSON("$meta" << "geoNearDistance")); + + CanonicalQuery* cq; + if (!CanonicalQuery::canonicalize(ns, rewritten, BSONObj(), projObj, 0, numWanted, BSONObj(), &cq).isOK()) { + errmsg = "Can't parse filter / create query"; + return false; + } + + Runner* rawRunner; + if (!getRunner(cq, &rawRunner, 0).isOK()) { + errmsg = "can't get query runner"; + return false; + } + + auto_ptr<Runner> runner(rawRunner); + + double totalDistance = 0; + BSONObjBuilder resultBuilder(result.subarrayStart("results")); + double farthestDist = 0; + + BSONObj currObj; + int results = 0; + while ((results < numWanted) && Runner::RUNNER_ADVANCED == runner->getNext(&currObj, NULL)) { + // cout << "result is " << currObj.toString() << endl; + + double dist = currObj["$dis"].number() * distanceMultiplier; + // cout << std::setprecision(10) << "HK GEON mul'd dist is " << dist << " raw dist is " << currObj["$dis"].number() << endl; + totalDistance += dist; + if (dist > farthestDist) { farthestDist = dist; } + + BSONObjBuilder oneResultBuilder( + resultBuilder.subobjStart(BSONObjBuilder::numStr(results))); + oneResultBuilder.append("dis", dist); + if (includeLocs) { + oneResultBuilder.appendAs(currObj["$pt"], "loc"); + } + + // strip out '$dis' and '$pt' and the rest gets added as 'obj'. + BSONObjIterator resIt(currObj); + BSONObjBuilder resBob; + while (resIt.more()) { + BSONElement elt = resIt.next(); + if (!mongoutils::str::equals("$pt", elt.fieldName()) + && !mongoutils::str::equals("$dis", elt.fieldName())) { + resBob.append(elt); + } + } + oneResultBuilder.append("obj", resBob.obj()); + oneResultBuilder.done(); + ++results; + } + + resultBuilder.done(); + + // Fill out the stats subobj. + BSONObjBuilder stats(result.subobjStart("stats")); + + // Fill in nscanned from the explain. + TypeExplain* bareExplain; + Status res = runner->getExplainPlan(&bareExplain); + if (res.isOK()) { + auto_ptr<TypeExplain> explain(bareExplain); + stats.append("nscanned", explain->getNScanned()); + stats.append("objectsLoaded", explain->getNScannedObjects()); + } + + stats.append("avgDistance", totalDistance / results); + stats.append("maxDistance", farthestDist); + stats.append("time", cc().curop()->elapsedMillis()); + stats.done(); + + return true; + } + + private: + bool getFieldName(Collection* collection, IndexCatalog* indexCatalog, string* fieldOut, + string* errOut, bool *isFrom2D) { + vector<int> idxs; + + // First, try 2d. + collection->details()->findIndexByType(IndexNames::GEO_2D, idxs); + if (idxs.size() > 1) { + *errOut = "more than one 2d index, not sure which to run geoNear on"; + return false; + } + + if (1 == idxs.size()) { + BSONObj indexKp = indexCatalog->getDescriptor(idxs[0])->keyPattern(); + BSONObjIterator kpIt(indexKp); + while (kpIt.more()) { + BSONElement elt = kpIt.next(); + if (String == elt.type() && IndexNames::GEO_2D == elt.valuestr()) { + *fieldOut = elt.fieldName(); + *isFrom2D = true; + return true; + } + } + } + + // Next, 2dsphere. + idxs.clear(); + collection->details()->findIndexByType(IndexNames::GEO_2DSPHERE, idxs); + if (0 == idxs.size()) { + *errOut = "no geo indices for geoNear"; + return false; + } + + if (idxs.size() > 1) { + *errOut = "more than one 2dsphere index, not sure which to run geoNear on"; + return false; + } + + // 1 == idx.size() + BSONObj indexKp = indexCatalog->getDescriptor(idxs[0])->keyPattern(); + BSONObjIterator kpIt(indexKp); + while (kpIt.more()) { + BSONElement elt = kpIt.next(); + if (String == elt.type() && IndexNames::GEO_2DSPHERE == elt.valuestr()) { + *fieldOut = elt.fieldName(); + *isFrom2D = false; + return true; + } + } + + return false; + } + } geo2dFindNearCmd; +} // namespace mongo diff --git a/src/mongo/db/exec/2dcommon.cpp b/src/mongo/db/exec/2dcommon.cpp index 9c9ca3ea005..2f09e060916 100644 --- a/src/mongo/db/exec/2dcommon.cpp +++ b/src/mongo/db/exec/2dcommon.cpp @@ -27,12 +27,73 @@ */ #include "mongo/db/exec/2dcommon.h" + +#include "mongo/db/matcher/matchable.h" #include "mongo/db/query/index_bounds_builder.h" namespace mongo { namespace twod_exec { // + // A MatchableDocument that will load the doc if need be but records if it does. + // + + class GeoMatchableDocument : public MatchableDocument { + public: + GeoMatchableDocument(const BSONObj& keyPattern, const BSONObj& key, DiskLoc loc, bool *fetched) + : _keyPattern(keyPattern), + _key(key), + _loc(loc), + _fetched(fetched) { } + + BSONObj toBSON() const { + *_fetched = true; + return _loc.obj(); + } + + virtual ElementIterator* allocateIterator(const ElementPath* path) const { + BSONObjIterator keyPatternIt(_keyPattern); + BSONObjIterator keyDataIt(_key); + + // Skip the "2d"-indexed stuff. We might have a diff. predicate over that field + // and those can't be covered. + keyPatternIt.next(); + keyDataIt.next(); + + // Look in the key. + while (keyPatternIt.more()) { + BSONElement keyPatternElt = keyPatternIt.next(); + verify(keyDataIt.more()); + BSONElement keyDataElt = keyDataIt.next(); + + if (path->fieldRef().equalsDottedField(keyPatternElt.fieldName())) { + if (Array == keyDataElt.type()) { + return new SimpleArrayElementIterator(keyDataElt, true); + } + else { + return new SingleElementElementIterator(keyDataElt); + } + } + } + + // All else fails, fetch. + *_fetched = true; + return new BSONElementIterator(path, _loc.obj()); + } + + virtual void releaseIterator( ElementIterator* iterator ) const { + delete iterator; + } + + private: + BSONObj _keyPattern; + BSONObj _key; + DiskLoc _loc; + bool* _fetched; + }; + + + // // GeoAccumulator // @@ -65,22 +126,30 @@ namespace twod_exec { //cout << "newDoc: " << newDoc << endl; if(newDoc) { + bool fetched = false; + if (NULL != _filter) { - // XXX: use key information to match...shove in WSM, try loc_and_idx, then fetch obj - // and try that. - BSONObj obj = node.recordLoc.obj(); - bool good = _filter->matchesBSON(obj, NULL); + GeoMatchableDocument md(_accessMethod->getDescriptor()->keyPattern(), + node._key, + node.recordLoc, + &fetched); + bool good = _filter->matches(&md); + _matchesPerfd++; - //if (details.hasLoadedRecord()) - //_objectsLoaded++; + if (fetched) { + _objectsLoaded++; + } if (! good) { _matched[ node.recordLoc ] = false; return; } } - _matched[ node.recordLoc ] = true; + // Don't double-count. + if (!fetched) { + _objectsLoaded++; + } } else if(!((*match).second)) { return; } diff --git a/src/mongo/db/exec/2dcommon.h b/src/mongo/db/exec/2dcommon.h index b11ff70438e..b475aa3adae 100644 --- a/src/mongo/db/exec/2dcommon.h +++ b/src/mongo/db/exec/2dcommon.h @@ -28,7 +28,6 @@ #include "mongo/db/exec/index_scan.h" #include "mongo/db/geo/core.h" -#include "mongo/db/geo/geonear.h" #include "mongo/db/geo/hash.h" #include "mongo/db/geo/shapes.h" #include "mongo/db/pdfile.h" diff --git a/src/mongo/db/exec/2dnear.cpp b/src/mongo/db/exec/2dnear.cpp index 5b1776d00ea..33093a8572d 100644 --- a/src/mongo/db/exec/2dnear.cpp +++ b/src/mongo/db/exec/2dnear.cpp @@ -29,6 +29,7 @@ #include "mongo/db/exec/2dnear.h" #include "mongo/db/exec/working_set_common.h" +#include "mongo/db/exec/working_set_computed_data.h" #include "mongo/db/jsobj.h" #include "mongo/db/structure/collection.h" @@ -73,11 +74,13 @@ namespace mongo { _params.nearQuery.maxDistance, _params.nearQuery.isNearSphere ? twod_exec::GEO_SPHERE : twod_exec::GEO_PLANE, - _params.uniqueDocs, + _params.nearQuery.uniqueDocs, false)); // This is where all the work is done. :( search->exec(); + _specificStats.objectsLoaded = search->_objectsLoaded; + _specificStats.nscanned = search->_nscanned; for (twod_exec::GeoHopper::Holder::iterator it = search->_points.begin(); it != search->_points.end(); it++) { @@ -86,8 +89,13 @@ namespace mongo { WorkingSetMember* member = _workingSet->get(id); member->loc = it->_loc; member->obj = member->loc.obj(); - //cout << "points: " << member->obj.toString() << endl; member->state = WorkingSetMember::LOC_AND_UNOWNED_OBJ; + if (_params.addDistMeta) { + member->addComputed(new GeoDistanceComputedData(it->_distance)); + } + if (_params.addPointMeta) { + member->addComputed(new GeoNearPointComputedData(it->_pt)); + } _results.push(Result(id, it->_distance)); _invalidationMap.insert(pair<DiskLoc, WorkingSetID>(it->_loc, id)); } @@ -140,7 +148,9 @@ namespace mongo { PlanStageStats* TwoDNear::getStats() { _commonStats.isEOF = isEOF(); - return new PlanStageStats(_commonStats, STAGE_GEO_NEAR_2D); + auto_ptr<PlanStageStats> ret(new PlanStageStats(_commonStats, STAGE_GEO_NEAR_2D)); + ret->specific.reset(new TwoDNearStats(_specificStats)); + return ret.release(); } } // namespace mongo diff --git a/src/mongo/db/exec/2dnear.h b/src/mongo/db/exec/2dnear.h index c92ec044e69..d7a2c271d1c 100644 --- a/src/mongo/db/exec/2dnear.h +++ b/src/mongo/db/exec/2dnear.h @@ -45,7 +45,8 @@ namespace mongo { BSONObj indexKeyPattern; MatchExpression* filter; int numWanted; - bool uniqueDocs; + bool addPointMeta; + bool addDistMeta; }; struct Result { @@ -57,6 +58,7 @@ namespace mongo { } WorkingSetID id; + double distance; }; @@ -77,10 +79,9 @@ namespace mongo { private: WorkingSet* _workingSet; - MatchExpression* _filter; - // Stats CommonStats _commonStats; + TwoDNearStats _specificStats; // We compute an annulus of results and cache it here. priority_queue<Result> _results; diff --git a/src/mongo/db/exec/plan_stats.h b/src/mongo/db/exec/plan_stats.h index f125b4e8a83..633045d050b 100644 --- a/src/mongo/db/exec/plan_stats.h +++ b/src/mongo/db/exec/plan_stats.h @@ -265,4 +265,14 @@ namespace mongo { uint64_t chunkSkips; }; + struct TwoDNearStats : public SpecificStats { + TwoDNearStats() : objectsLoaded(0), nscanned(0) { } + + uint64_t objectsLoaded; + + // Since 2d's near does all its work in one go we can't divine the real nscanned from + // anything else. + uint64_t nscanned; + }; + } // namespace mongo diff --git a/src/mongo/db/exec/projection_exec.cpp b/src/mongo/db/exec/projection_exec.cpp index 862c6461184..ae28683d377 100644 --- a/src/mongo/db/exec/projection_exec.cpp +++ b/src/mongo/db/exec/projection_exec.cpp @@ -127,6 +127,12 @@ namespace mongo { else if (mongoutils::str::equals(e2.valuestr(), "diskloc")) { _meta[e.fieldName()] = META_DISKLOC; } + else if (mongoutils::str::equals(e2.valuestr(), "geoNearPoint")) { + _meta[e.fieldName()] = META_GEONEAR_POINT; + } + else if (mongoutils::str::equals(e2.valuestr(), "geoNearDistance")) { + _meta[e.fieldName()] = META_GEONEAR_DIST; + } else if (mongoutils::str::equals(e2.valuestr(), "indexKey")) { _hasReturnKey = true; // The index key clobbers everything so just stop parsing here. @@ -287,7 +293,37 @@ namespace mongo { } for (MetaMap::const_iterator it = _meta.begin(); it != _meta.end(); ++it) { - if (META_TEXT == it->second) { + if (META_GEONEAR_DIST == it->second) { + if (member->hasComputed(WSM_COMPUTED_GEO_DISTANCE)) { + const GeoDistanceComputedData* dist + = static_cast<const GeoDistanceComputedData*>( + member->getComputed(WSM_COMPUTED_GEO_DISTANCE)); + bob.append(it->first, dist->getDist()); + } + else { + return Status(ErrorCodes::InternalError, + "near loc dist requested but no data available"); + } + } + else if (META_GEONEAR_POINT == it->second) { + if (member->hasComputed(WSM_GEO_NEAR_POINT)) { + const GeoNearPointComputedData* point + = static_cast<const GeoNearPointComputedData*>( + member->getComputed(WSM_GEO_NEAR_POINT)); + BSONObj ptObj = point->getPoint(); + if (ptObj.couldBeArray()) { + bob.appendArray(it->first, ptObj); + } + else { + bob.append(it->first, ptObj); + } + } + else { + return Status(ErrorCodes::InternalError, + "near loc proj requested but no data available"); + } + } + else if (META_TEXT == it->second) { if (member->hasComputed(WSM_COMPUTED_TEXT_SCORE)) { const TextScoreComputedData* score = static_cast<const TextScoreComputedData*>( diff --git a/src/mongo/db/exec/projection_exec.h b/src/mongo/db/exec/projection_exec.h index 8b6efb26003..95b4396aecb 100644 --- a/src/mongo/db/exec/projection_exec.h +++ b/src/mongo/db/exec/projection_exec.h @@ -53,7 +53,8 @@ namespace mongo { */ enum MetaProjection { META_TEXT, - META_GEO, + META_GEONEAR_DIST, + META_GEONEAR_POINT, META_DISKLOC, META_IX_KEY, }; diff --git a/src/mongo/db/exec/s2near.cpp b/src/mongo/db/exec/s2near.cpp index cfb383cf766..f21c589c7dc 100644 --- a/src/mongo/db/exec/s2near.cpp +++ b/src/mongo/db/exec/s2near.cpp @@ -31,6 +31,7 @@ #include "mongo/db/exec/fetch.h" #include "mongo/db/exec/index_scan.h" #include "mongo/db/exec/working_set_common.h" +#include "mongo/db/exec/working_set_computed_data.h" #include "mongo/db/geo/geoconstants.h" #include "mongo/db/index/catalog_hack.h" #include "mongo/db/index/expression_index.h" @@ -38,40 +39,34 @@ namespace mongo { - S2NearStage::S2NearStage(const string& ns, const BSONObj& indexKeyPattern, - const NearQuery& nearQuery, const IndexBounds& baseBounds, - MatchExpression* filter, WorkingSet* ws) { - _ns = ns; + S2NearStage::S2NearStage(const S2NearParams& params, WorkingSet* ws) { + _params = params; _ws = ws; - _indexKeyPattern = indexKeyPattern; - _nearQuery = nearQuery; - _baseBounds = baseBounds; - _filter = filter; _worked = false; _failed = false; // The field we're near-ing from is the n-th field. Figure out what that 'n' is. We // put the cover for the search annulus in this spot in the bounds. _nearFieldIndex = 0; - BSONObjIterator specIt(_indexKeyPattern); + BSONObjIterator specIt(_params.indexKeyPattern); while (specIt.more()) { - if (specIt.next().fieldName() == _nearQuery.field) { + if (specIt.next().fieldName() == _params.nearQuery.field) { break; } ++_nearFieldIndex; } - verify(_nearFieldIndex < _indexKeyPattern.nFields()); + verify(_nearFieldIndex < _params.indexKeyPattern.nFields()); // FLAT implies the distances are in radians. Convert to meters. - if (FLAT == _nearQuery.centroid.crs) { - _nearQuery.minDistance *= kRadiusOfEarthInMeters; - _nearQuery.maxDistance *= kRadiusOfEarthInMeters; + if (FLAT == _params.nearQuery.centroid.crs) { + _params.nearQuery.minDistance *= kRadiusOfEarthInMeters; + _params.nearQuery.maxDistance *= kRadiusOfEarthInMeters; } // Make sure distances are sane. Possibly redundant given the checking during parsing. - _minDistance = max(0.0, _nearQuery.minDistance); - _maxDistance = min(M_PI * kRadiusOfEarthInMeters, _nearQuery.maxDistance); + _minDistance = max(0.0, _params.nearQuery.minDistance); + _maxDistance = min(M_PI * kRadiusOfEarthInMeters, _params.nearQuery.maxDistance); _minDistance = min(_minDistance, _maxDistance); // We grow _outerRadius in nextAnnulus() below. @@ -152,9 +147,9 @@ namespace mongo { if (isEOF()) { return; } // Step 2: Fill out bounds for the ixscan we use. - _innerCap = S2Cap::FromAxisAngle(_nearQuery.centroid.point, + _innerCap = S2Cap::FromAxisAngle(_params.nearQuery.centroid.point, S1Angle::Radians(_innerRadius / kRadiusOfEarthInMeters)); - _outerCap = S2Cap::FromAxisAngle(_nearQuery.centroid.point, + _outerCap = S2Cap::FromAxisAngle(_params.nearQuery.centroid.point, S1Angle::Radians(_outerRadius / kRadiusOfEarthInMeters)); _innerCap = _innerCap.Complement(); @@ -165,8 +160,8 @@ namespace mongo { _annulus.Release(NULL); _annulus.Init(®ions); - _baseBounds.fields[_nearFieldIndex].intervals.clear(); - ExpressionMapping::cover2dsphere(_annulus, &_baseBounds.fields[_nearFieldIndex]); + _params.baseBounds.fields[_nearFieldIndex].intervals.clear(); + ExpressionMapping::cover2dsphere(_annulus, &_params.baseBounds.fields[_nearFieldIndex]); // Step 3: Actually create the ixscan. // TODO: Cache params. @@ -177,24 +172,26 @@ namespace mongo { return; } - Collection* collection = db->getCollection( _ns ); + Collection* collection = db->getCollection( _params.ns ); if ( !collection ) { _failed = true; return; } IndexScanParams params; - params.descriptor = collection->getIndexCatalog()->findIndexByKeyPattern( _indexKeyPattern ); + params.descriptor = + collection->getIndexCatalog()->findIndexByKeyPattern(_params.indexKeyPattern ); + if ( !params.descriptor ) { _failed = true; return; } - params.bounds = _baseBounds; + params.bounds = _params.baseBounds; params.direction = 1; IndexScan* scan = new IndexScan(params, _ws, NULL); // Owns 'scan'. - _child.reset(new FetchStage(_ws, scan, _filter)); + _child.reset(new FetchStage(_ws, scan, _params.filter)); } PlanStage::StageState S2NearStage::addResultToQueue(WorkingSetID* out) { @@ -234,28 +231,39 @@ namespace mongo { // Get all the fields with that name from the document. BSONElementSet geom; - member->obj.getFieldsDotted(_nearQuery.field, geom, false); + member->obj.getFieldsDotted(_params.nearQuery.field, geom, false); if (geom.empty()) {return PlanStage::NEED_TIME; } // Some value that any distance we can calculate will be less than. double minDistance = numeric_limits<double>::max(); + BSONObj minDistanceObj; for (BSONElementSet::iterator git = geom.begin(); git != geom.end(); ++git) { if (!git->isABSONObj()) { return PlanStage::FAILURE; } BSONObj obj = git->Obj(); double distToObj; - if (S2SearchUtil::distanceBetween(_nearQuery.centroid.point, obj, &distToObj)) { - minDistance = min(distToObj, minDistance); + if (S2SearchUtil::distanceBetween(_params.nearQuery.centroid.point, obj, &distToObj)) { + if (distToObj < minDistance) { + minDistance = distToObj; + minDistanceObj = obj; + } } else { warning() << "unknown geometry: " << obj.toString(); } } - // If the distance to the doc satisfies our distance criteria, + // If the distance to the doc satisfies our distance criteria, add it to our buffered + // results. if (minDistance >= _innerRadius && (_outerRadiusInclusive ? minDistance <= _outerRadius : minDistance < _outerRadius)) { _results.push(Result(*out, minDistance)); + if (_params.addDistMeta) { + member->addComputed(new GeoDistanceComputedData(minDistance)); + } + if (_params.addPointMeta) { + member->addComputed(new GeoNearPointComputedData(minDistanceObj)); + } if (member->hasLoc()) { _invalidationMap[member->loc] = *out; } diff --git a/src/mongo/db/exec/s2near.h b/src/mongo/db/exec/s2near.h index aa08e8c20fb..9f1513d3235 100644 --- a/src/mongo/db/exec/s2near.h +++ b/src/mongo/db/exec/s2near.h @@ -42,6 +42,16 @@ namespace mongo { + struct S2NearParams { + string ns; + BSONObj indexKeyPattern; + NearQuery nearQuery; + IndexBounds baseBounds; + MatchExpression* filter; + bool addPointMeta; + bool addDistMeta; + }; + /** * Executes a geoNear search. Is a leaf node. Output type is LOC_AND_UNOWNED_OBJ. */ @@ -51,9 +61,7 @@ namespace mongo { * Takes: index to scan over, MatchExpression with near point, other MatchExpressions for * covered data, */ - S2NearStage(const string& ns, const BSONObj& indexKeyPattern, - const NearQuery& nearQuery, const IndexBounds& baseBounds, - MatchExpression* filter, WorkingSet* ws); + S2NearStage(const S2NearParams& params, WorkingSet* ws); virtual ~S2NearStage(); @@ -72,26 +80,17 @@ namespace mongo { bool _worked; - WorkingSet* _ws; - - string _ns; + S2NearParams _params; - BSONObj _indexKeyPattern; + WorkingSet* _ws; // This is the "array index" of the key field that is the near field. We use this to do // cheap is-this-doc-in-the-annulus testing. We also need to know where to stuff the index // bounds for the various annuluses/annuli. int _nearFieldIndex; - NearQuery _nearQuery; - - IndexBounds _baseBounds; - scoped_ptr<PlanStage> _child; - // We don't check this ourselves; we let the sub-fetch deal w/it. - MatchExpression* _filter; - // The S2 machinery that represents the search annulus. We keep this around after bounds // generation to check for intersection. S2Cap _innerCap; diff --git a/src/mongo/db/exec/working_set.h b/src/mongo/db/exec/working_set.h index c32cf8be121..9b47e4a5540 100644 --- a/src/mongo/db/exec/working_set.h +++ b/src/mongo/db/exec/working_set.h @@ -145,9 +145,20 @@ namespace mongo { * What types of computed data can we have? */ enum WorkingSetComputedDataType { + // What's the score of the document retrieved from a $text query? WSM_COMPUTED_TEXT_SCORE = 0, + + // What's the distance from a geoNear query point to the document? WSM_COMPUTED_GEO_DISTANCE = 1, + + // The index key used to retrieve the document, for $returnKey query option. WSM_INDEX_KEY = 2, + + // What point (of several possible points) was used to compute the distance to the document + // via geoNear? + WSM_GEO_NEAR_POINT = 3, + + // Must be last. WSM_COMPUTED_NUM_TYPES, }; diff --git a/src/mongo/db/exec/working_set_computed_data.h b/src/mongo/db/exec/working_set_computed_data.h index 221b7804664..53a74633764 100644 --- a/src/mongo/db/exec/working_set_computed_data.h +++ b/src/mongo/db/exec/working_set_computed_data.h @@ -50,18 +50,18 @@ namespace mongo { class GeoDistanceComputedData : public WorkingSetComputedData { public: - GeoDistanceComputedData(double score) + GeoDistanceComputedData(double dist) : WorkingSetComputedData(WSM_COMPUTED_GEO_DISTANCE), - _score(score) { } + _dist(dist) { } - double getScore() const { return _score; } + double getDist() const { return _dist; } virtual GeoDistanceComputedData* clone() const { - return new GeoDistanceComputedData(_score); + return new GeoDistanceComputedData(_dist); } private: - double _score; + double _dist; }; class IndexKeyComputedData : public WorkingSetComputedData { @@ -80,4 +80,20 @@ namespace mongo { BSONObj _key; }; + class GeoNearPointComputedData : public WorkingSetComputedData { + public: + GeoNearPointComputedData(BSONObj point) + : WorkingSetComputedData(WSM_GEO_NEAR_POINT), + _point(point.getOwned()) { } + + BSONObj getPoint() const { return _point; } + + virtual GeoNearPointComputedData* clone() const { + return new GeoNearPointComputedData(_point); + } + + private: + BSONObj _point; + }; + } // namespace mongo diff --git a/src/mongo/db/geo/geonear.cpp b/src/mongo/db/geo/geonear.cpp deleted file mode 100644 index a407989b29d..00000000000 --- a/src/mongo/db/geo/geonear.cpp +++ /dev/null @@ -1,274 +0,0 @@ -/** -* Copyright (C) 2012 10gen Inc. -* -* This program is free software: you can redistribute it and/or modify -* it under the terms of the GNU Affero General Public License, version 3, -* as published by the Free Software Foundation. -* -* This program is distributed in the hope that it will be useful, -* but WITHOUT ANY WARRANTY; without even the implied warranty of -* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -* GNU Affero General Public License for more details. -* -* You should have received a copy of the GNU Affero General Public License -* along with this program. If not, see <http://www.gnu.org/licenses/>. -* -* 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 <vector> - -#include "mongo/db/geo/geonear.h" - -#include "mongo/db/auth/action_set.h" -#include "mongo/db/auth/action_type.h" -#include "mongo/db/auth/privilege.h" -#include "mongo/db/commands.h" -#include "mongo/db/curop.h" -#include "mongo/db/geo/geoconstants.h" -#include "mongo/db/geo/s2common.h" -#include "mongo/db/index_names.h" -#include "mongo/db/index/2d_index_cursor.h" -#include "mongo/db/index/index_descriptor.h" -#include "mongo/db/index/index_access_method.h" -#include "mongo/db/index/s2_near_cursor.h" -#include "mongo/db/index/s2_access_method.h" -#include "mongo/db/jsobj.h" -#include "mongo/db/namespace_details.h" -#include "mongo/db/pdfile.h" -#include "mongo/db/structure/collection.h" -#include "mongo/platform/unordered_map.h" - -namespace mongo { - - GeoNearArguments::GeoNearArguments(const BSONObj &cmdObj) { - // If 'num' is passed, use it and ignore 'limit'. Otherwise use 'limit'. - const char* limitName = !cmdObj["num"].eoo() ? "num" : "limit"; - BSONElement eNumWanted = cmdObj[limitName]; - if (!eNumWanted.eoo()) { - uassert(17032, str::stream() << limitName << " must be a number", - eNumWanted.isNumber()); - numWanted = eNumWanted.numberInt(); - } else { - numWanted = 100; - } - - if (!cmdObj["uniqueDocs"].eoo()) { - uniqueDocs = cmdObj["uniqueDocs"].trueValue(); - } else { - uniqueDocs = false; - } - - if (!cmdObj["includeLocs"].eoo()) { - includeLocs = cmdObj["includeLocs"].trueValue(); - } else { - includeLocs = false; - } - - if (cmdObj["query"].isABSONObj()) { - query = cmdObj["query"].embeddedObject(); - } - - BSONElement eDistanceMultiplier = cmdObj["distanceMultiplier"]; - if (!eDistanceMultiplier.eoo()) { - uassert(17033, "distanceMultiplier must be a number", eDistanceMultiplier.isNumber()); - distanceMultiplier = eDistanceMultiplier.number(); - uassert(17034, "distanceMultiplier must be non-negative", distanceMultiplier >= 0); - } else { - distanceMultiplier = 1.0; - } - - isSpherical = cmdObj["spherical"].trueValue(); - } - - class Geo2dFindNearCmd : public Command { - public: - Geo2dFindNearCmd() : Command("geoNear") {} - - virtual LockType locktype() const { return READ; } - bool slaveOk() const { return true; } - bool slaveOverrideOk() const { return true; } - - void help(stringstream& h) const { - h << "http://dochub.mongodb.org/core/geo#GeospatialIndexing-geoNearCommand"; - } - - virtual void addRequiredPrivileges(const std::string& dbname, - const BSONObj& cmdObj, - std::vector<Privilege>* out) { - ActionSet actions; - actions.addAction(ActionType::find); - out->push_back(Privilege(parseResourcePattern(dbname, cmdObj), actions)); - } - - bool run(const string& dbname, BSONObj& cmdObj, int, string& errmsg, BSONObjBuilder& result, bool fromRepl) { - string ns = dbname + "." + cmdObj.firstElement().valuestr(); - - Database* db = cc().database(); - if ( !db ) { - errmsg = "can't find ns"; - return false; - } - - Collection* collection = db->getCollection( ns ); - if ( !collection ) { - errmsg = "can't find ns"; - return false; - } - - IndexCatalog* indexCatalog = collection->getIndexCatalog(); - - GeoNearArguments commonArgs(cmdObj); - if (commonArgs.numWanted < 0) { - errmsg = "numWanted must be >= 0"; - return false; - } - - vector<int> idxs; - - collection->details()->findIndexByType(IndexNames::GEO_2D, idxs); - if (idxs.size() > 1) { - errmsg = "more than one 2d index, not sure which to run geoNear on"; - return false; - } - - unordered_map<string, double> statsMap; - - if (1 == idxs.size()) { - result.append("ns", ns); - twod_internal::TwoDGeoNearRunner::run2DGeoNear(indexCatalog, - indexCatalog->getDescriptor( idxs[0] ), - cmdObj, commonArgs, - errmsg, result, &statsMap); - BSONObjBuilder stats(result.subobjStart("stats")); - for (unordered_map<string, double>::const_iterator it = statsMap.begin(); - it != statsMap.end(); ++it) { - stats.append(it->first, it->second); - } - stats.append("time", cc().curop()->elapsedMillis()); - stats.done(); - return true; - } - - collection->details()->findIndexByType(IndexNames::GEO_2DSPHERE, idxs); - if (idxs.size() > 1) { - errmsg = "more than one 2dsphere index, not sure which to run geoNear on"; - return false; - } - - if (1 == idxs.size()) { - result.append("ns", ns); - run2DSphereGeoNear(indexCatalog,indexCatalog->getDescriptor(idxs[0]), - cmdObj, commonArgs, errmsg, result); - return true; - } - - errmsg = "no geo indices for geoNear"; - return false; - } - - private: - - static bool run2DSphereGeoNear(IndexCatalog* catalog, IndexDescriptor* descriptor, - BSONObj& cmdObj, const GeoNearArguments &parsedArgs, - string& errmsg, BSONObjBuilder& result) { - S2AccessMethod* sam = static_cast<S2AccessMethod*>( catalog->getIndex(descriptor) ); - const S2IndexingParams& params = sam->getParams(); - scoped_ptr<S2NearIndexCursor> nic(new S2NearIndexCursor(descriptor, params)); - - vector<string> geoFieldNames; - BSONObjIterator i(descriptor->keyPattern()); - while (i.more()) { - BSONElement e = i.next(); - if (e.type() == String && IndexNames::GEO_2DSPHERE == e.valuestr()) { - geoFieldNames.push_back(e.fieldName()); - } - } - - // NOTE(hk): If we add a new argument to geoNear, we could have a - // 2dsphere index with multiple indexed geo fields, and the geoNear - // could pick the one to run over. Right now, we just require one. - uassert(16552, "geoNear requires exactly one indexed geo field", 1 == geoFieldNames.size()); - NearQuery nearQuery(geoFieldNames[0]); - uassert(16679, "Invalid geometry given as arguments to geoNear: " + cmdObj.toString(), - nearQuery.parseFromGeoNear(cmdObj, params.radius)); - uassert(16683, "geoNear on 2dsphere index requires spherical", - parsedArgs.isSpherical); - - // NOTE(hk): For a speedup, we could look through the query to see if - // we've geo-indexed any of the fields in it. - vector<GeoQuery> regions; - - if (FLAT == nearQuery.centroid.crs) { - nearQuery.maxDistance *= kRadiusOfEarthInMeters; - nearQuery.minDistance *= kRadiusOfEarthInMeters; - } - - nic->seek(parsedArgs.query, nearQuery, regions); - - // We do pass in the query above, but it's just so we can possibly use it in our index - // scan. We have to do our own matching. - auto_ptr<Matcher> matcher(new Matcher(parsedArgs.query)); - - double totalDistance = 0; - BSONObjBuilder resultBuilder(result.subarrayStart("results")); - double farthestDist = 0; - - int results; - for (results = 0; results < parsedArgs.numWanted && !nic->isEOF(); ++results) { - BSONObj currObj = nic->getValue().obj(); - if (!matcher->matches(currObj)) { - --results; - nic->next(); - continue; - } - - double dist = nic->currentDistance(); - // If we got the distance in radians, output it in radians too. - if (FLAT == nearQuery.centroid.crs) { dist /= params.radius; } - dist *= parsedArgs.distanceMultiplier; - totalDistance += dist; - if (dist > farthestDist) { farthestDist = dist; } - - BSONObjBuilder oneResultBuilder( - resultBuilder.subobjStart(BSONObjBuilder::numStr(results))); - oneResultBuilder.append("dis", dist); - if (parsedArgs.includeLocs) { - BSONElementSet geoFieldElements; - currObj.getFieldsDotted(geoFieldNames[0], geoFieldElements, false); - for (BSONElementSet::iterator oi = geoFieldElements.begin(); - oi != geoFieldElements.end(); ++oi) { - if (oi->isABSONObj()) { - oneResultBuilder.appendAs(*oi, "loc"); - } - } - } - - oneResultBuilder.append("obj", currObj); - oneResultBuilder.done(); - nic->next(); - } - - resultBuilder.done(); - - BSONObjBuilder stats(result.subobjStart("stats")); - stats.appendNumber("nscanned", nic->nscanned()); - stats.append("avgDistance", totalDistance / results); - stats.append("maxDistance", farthestDist); - stats.append("time", cc().curop()->elapsedMillis()); - stats.done(); - - return true; - } - } geo2dFindNearCmd; -} // namespace mongo diff --git a/src/mongo/db/geo/geonear.h b/src/mongo/db/geo/geonear.h deleted file mode 100644 index de74da84610..00000000000 --- a/src/mongo/db/geo/geonear.h +++ /dev/null @@ -1,47 +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. -*/ - -#pragma once - -#include "mongo/db/jsobj.h" - -namespace mongo { - // Arguments in common between 2d and 2dsphere geoNear. - class GeoNearArguments { - public: - GeoNearArguments(const BSONObj& cmdObj); - int numWanted; - bool uniqueDocs; - bool includeLocs; - BSONObj query; - double distanceMultiplier; - bool isSpherical; - private: - GeoNearArguments() { } - }; -} // namespace mongo diff --git a/src/mongo/db/geo/geoquery.cpp b/src/mongo/db/geo/geoquery.cpp index f45c813ee85..6d870464e99 100644 --- a/src/mongo/db/geo/geoquery.cpp +++ b/src/mongo/db/geo/geoquery.cpp @@ -34,31 +34,6 @@ namespace mongo { using mongoutils::str::equals; - bool NearQuery::parseFromGeoNear(const BSONObj &obj, double radius) { - if (obj["near"].eoo()) { return false; } - BSONObj nearObj = obj["near"].embeddedObject(); - - if (!GeoParser::isPoint(nearObj) || !GeoParser::parsePoint(nearObj, ¢roid)) { - return false; - } - - if (!obj["minDistance"].eoo()) { - uassert(17035, "minDistance must be a number", obj["minDistance"].isNumber()); - double distArg = obj["minDistance"].number(); - uassert(16901, "minDistance must be non-negative", distArg >= 0.0); - minDistance = distArg; - } - - if (!obj["maxDistance"].eoo()) { - uassert(17036, "maxDistance must be a number", obj["maxDistance"].isNumber()); - double distArg = obj["maxDistance"].number(); - uassert(16902, "maxDistance must be non-negative", distArg >= 0.0); - maxDistance = distArg; - } - - return true; - } - bool NearQuery::parseLegacyQuery(const BSONObj &obj) { bool hasGeometry = false; @@ -88,6 +63,8 @@ namespace mongo { uassert(16895, "$maxDistance must be a number", e.isNumber()); maxDistance = e.Number(); uassert(16896, "$maxDistance must be non-negative", maxDistance >= 0.0); + } else if (equals(e.fieldName(), "$uniqueDocs")) { + uniqueDocs = e.trueValue(); } } diff --git a/src/mongo/db/geo/geoquery.h b/src/mongo/db/geo/geoquery.h index 9ee1c363732..fc051482b3f 100644 --- a/src/mongo/db/geo/geoquery.h +++ b/src/mongo/db/geo/geoquery.h @@ -105,16 +105,17 @@ namespace mongo { NearQuery() : minDistance(0), maxDistance(std::numeric_limits<double>::max()), - isNearSphere(false) { } + isNearSphere(false), + uniqueDocs(false) { } NearQuery(const string& f) : field(f), minDistance(0), maxDistance(std::numeric_limits<double>::max()), - isNearSphere(false) { } + isNearSphere(false), + uniqueDocs(false) { } bool parseFrom(const BSONObj &obj); - bool parseFromGeoNear(const BSONObj &obj, double radius); // The name of the field that contains the geometry. string field; @@ -132,6 +133,8 @@ namespace mongo { // It's either $near or $nearSphere. bool isNearSphere; + bool uniqueDocs; + string toString() const { stringstream ss; ss << " field=" << field; diff --git a/src/mongo/db/index/2d_access_method.cpp b/src/mongo/db/index/2d_access_method.cpp index fcefdb633be..c9fe4b8bab2 100644 --- a/src/mongo/db/index/2d_access_method.cpp +++ b/src/mongo/db/index/2d_access_method.cpp @@ -34,7 +34,6 @@ #include "mongo/db/geo/core.h" #include "mongo/db/index_names.h" #include "mongo/db/index/2d_common.h" -#include "mongo/db/index/2d_index_cursor.h" #include "mongo/db/jsobj.h" #include "mongo/db/pdfile.h" @@ -191,8 +190,7 @@ namespace mongo { } Status TwoDAccessMethod::newCursor(IndexCursor** out) { - *out = new TwoDIndexCursor(this); - return Status::OK(); + return Status(ErrorCodes::IllegalOperation, "Unimplemented seek called on S2"); } } // namespace mongo diff --git a/src/mongo/db/index/2d_index_cursor.cpp b/src/mongo/db/index/2d_index_cursor.cpp deleted file mode 100644 index 0cdd707fbf2..00000000000 --- a/src/mongo/db/index/2d_index_cursor.cpp +++ /dev/null @@ -1,2013 +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/index/2d_index_cursor.h" - -#ifdef _WIN32 -#include <float.h> -#define nextafter _nextafter -#else -#include <cmath> // nextafter -#endif - -#include "mongo/db/btreecursor.h" -#include "mongo/db/index/2d_access_method.h" -#include "mongo/db/index/btree_interface.h" -#include "mongo/db/jsobj.h" -#include "mongo/db/geo/core.h" -#include "mongo/db/geo/geonear.h" -#include "mongo/db/geo/hash.h" -#include "mongo/db/geo/shapes.h" -#include "mongo/db/pdfile.h" -#include "mongo/db/queryutil.h" -#include "mongo/db/structure/collection.h" - -namespace mongo { - -# define CDEBUG 10 -# define GEODEBUG(x) -# define GEODEBUGPRINT(x) -# define PREFIXDEBUG(x, y) - - // All these internal classes exist in namespace mongo until we kill the 2d index type. - // For now, put them into their own namespace to avoid scary "which symbol are we using" issues. - namespace twod_internal { - - enum GeoDistType { - GEO_PLANE, - GEO_SPHERE - }; - - class GeoKeyNode { - public: - GeoKeyNode(DiskLoc bucket, int keyOfs, DiskLoc r, BSONObj k) - : _bucket(bucket), _keyOfs(keyOfs), recordLoc(r), _key(k) { } - const DiskLoc _bucket; - const int _keyOfs; - const DiskLoc recordLoc; - const BSONObj _key; - private: - GeoKeyNode(); - }; - - inline double computeXScanDistance(double y, double maxDistDegrees) { - // TODO: this overestimates for large maxDistDegrees far from the equator - return maxDistDegrees / min(cos(deg2rad(min(+89.0, y + maxDistDegrees))), - cos(deg2rad(max(-89.0, y - maxDistDegrees)))); - } - - class GeoPoint { - public: - GeoPoint() : _distance(-1), _exact(false), _dirty(false) { } - - //// Distance not used //// - - GeoPoint(const GeoKeyNode& node) - : _key(node._key), _loc(node.recordLoc), _o(node.recordLoc.obj()), - _distance(-1), _exact(false), _dirty(false), _bucket(node._bucket), - _pos(node._keyOfs) { } - - //// Immediate initialization of distance //// - - GeoPoint(const GeoKeyNode& node, double distance, bool exact) - : _key(node._key), _loc(node.recordLoc), _o(node.recordLoc.obj()), - _distance(distance), _exact(exact), _dirty(false) { } - - GeoPoint(const GeoPoint& pt, double distance, bool exact) - : _key(pt.key()), _loc(pt.loc()), _o(pt.obj()), _distance(distance), _exact(exact), - _dirty(false) { } - - bool operator<(const GeoPoint& other) const { - if (_distance != other._distance) return _distance < other._distance; - if (_exact != other._exact) return _exact < other._exact; - return _loc < other._loc; - } - - double distance() const { return _distance; } - bool isExact() const { return _exact; } - BSONObj key() const { return _key; } - bool hasLoc() const { return _loc.isNull(); } - BSONObj obj() const { return _o; } - BSONObj pt() const { return _pt; } - bool isEmpty() { return _o.isEmpty(); } - bool isCleanAndEmpty() { return isEmpty() && !isDirty(); } - bool isDirty(){ return _dirty; } - - DiskLoc loc() const { - verify(!_dirty); - return _loc; - } - - string toString() const { - return str::stream() << "Point from " << _key << " - " << _o - << " dist : " << _distance << (_exact ? " (ex)" : " (app)"); - } - - // Recover from yield by finding all the changed disk locs here, modifying the _seenPts - // array. Not sure yet the correct thing to do about _seen. Definitely need to re-find our - // current max/min locations too - bool unDirty(const BtreeInterface* btreeInterface, IndexDescriptor* descriptor, - DiskLoc& oldLoc) { - verify(_dirty); - verify(! _id.isEmpty()); - - oldLoc = _loc; - _loc = DiskLoc(); - - // Check this position and the one immediately preceding - for(int i = 0; i < 2; i++){ - if (_pos - i < 0) continue; - - BSONObj key; - DiskLoc loc; - btreeInterface->keyAndRecordAt(_bucket, _pos - i, &key, &loc); - - if (loc.isNull()) continue; - - if (key.binaryEqual(_key) && loc.obj()["_id"].wrap("").binaryEqual(_id)) { - _pos = _pos - i; - _loc = loc; - _dirty = false; - _o = loc.obj(); - return true; - } - } - - // Slow undirty - scoped_ptr<BtreeCursor> cursor(BtreeCursor::make(nsdetails(descriptor->parentNS()), - descriptor->getOnDisk(), _key, _key, true, 1)); - - int count = 0; - while(cursor->ok()){ - count++; - if(cursor->current()["_id"].wrap("").binaryEqual(_id)){ - _bucket = cursor->getBucket(); - _pos = cursor->getKeyOfs(); - _loc = cursor->currLoc(); - _o = _loc.obj(); - break; - } else{ - LOG(CDEBUG + 1) << "Key doesn't match : " << cursor->current()["_id"] - << " saved : " << _id << endl; - } - cursor->advance(); - } - - if(! count) { LOG(CDEBUG) << "No key found for " << _key << endl; } - _dirty = false; - return _loc == oldLoc; - } - - bool makeDirty(){ - if(! _dirty){ - verify(! obj()["_id"].eoo()); - verify(! _bucket.isNull()); - verify(_pos >= 0); - - if(_id.isEmpty()){ - _id = obj()["_id"].wrap("").getOwned(); - } - _o = BSONObj(); - _key = _key.getOwned(); - _pt = _pt.getOwned(); - _dirty = true; - - return true; - } - - return false; - } - - BSONObj _key; - DiskLoc _loc; - BSONObj _o; - BSONObj _pt; - - double _distance; - bool _exact; - - BSONObj _id; - bool _dirty; - DiskLoc _bucket; - int _pos; - }; - - // GeoBrowse subclasses this - class GeoAccumulator { - public: - GeoAccumulator(TwoDAccessMethod* accessMethod, const BSONObj& filter, bool uniqueDocs, - bool needDistance) - : _accessMethod(accessMethod), _converter(accessMethod->getParams().geoHashConverter), - _lookedAt(0), _matchesPerfd(0), _objectsLoaded(0), _pointsLoaded(0), _found(0), - _uniqueDocs(uniqueDocs), _needDistance(needDistance) { - - if (! filter.isEmpty()) { - _matcher.reset(new CoveredIndexMatcher(filter, - accessMethod->getDescriptor()->keyPattern())); - GEODEBUG("Matcher is now " << _matcher->docMatcher().toString()); - } - } - - virtual ~GeoAccumulator() { } - enum KeyResult { BAD, BORDER, GOOD }; - - virtual void add(const GeoKeyNode& node) { - GEODEBUG("\t\t\t\t checking key " << node._key.toString()) - - _lookedAt++; - - // Approximate distance check using key data - double keyD = 0; - Point keyP(_converter->unhashToPoint(node._key.firstElement())); - KeyResult keyOk = approxKeyCheck(keyP, keyD); - if (keyOk == BAD) { - GEODEBUG("\t\t\t\t bad distance : " << node.recordLoc.obj() << "\t" << keyD); - return; - } - GEODEBUG("\t\t\t\t good distance : " << node.recordLoc.obj() << "\t" << keyD); - - // Check for match using other key (and potentially doc) criteria - // Remember match results for each object - map<DiskLoc, bool>::iterator match = _matched.find(node.recordLoc); - bool newDoc = match == _matched.end(); - if(newDoc) { - GEODEBUG("\t\t\t\t matching new doc with " - << (_matcher ? _matcher->docMatcher().toString() : "(empty)")); - - // matcher - MatchDetails details; - if (_matcher.get()) { - bool good = _matcher->matchesWithSingleKeyIndex(node._key, node.recordLoc, - &details); - _matchesPerfd++; - - if (details.hasLoadedRecord()) - _objectsLoaded++; - - if (! good) { - GEODEBUG("\t\t\t\t didn't match : " << node.recordLoc.obj()["_id"]); - _matched[ node.recordLoc ] = false; - return; - } - } - - _matched[ node.recordLoc ] = true; - - if (! details.hasLoadedRecord()) // don't double count - _objectsLoaded++; - - } else if(!((*match).second)) { - GEODEBUG("\t\t\t\t previously didn't match : " << node.recordLoc.obj()["_id"]); - return; - } - - // Exact check with particular data fields - // Can add multiple points - int diff = addSpecific(node, keyP, keyOk == BORDER, keyD, newDoc); - //int diff = addSpecific(node, keyP, keyOk == BORDER, keyD); - if(diff > 0) _found += diff; - else _found -= -diff; - } - - virtual void getPointsFor(const BSONObj& key, const BSONObj& obj, - vector<BSONObj> &locsForNode, bool allPoints = false) { - // Find all the location objects from the keys - vector<BSONObj> locs; - _accessMethod->getKeys(obj, allPoints ? locsForNode : locs); - ++_pointsLoaded; - - if (allPoints) return; - if (locs.size() == 1){ - locsForNode.push_back(locs[0]); - return; - } - - // Find the particular location we want - GeoHash keyHash(key.firstElement(), _converter->getBits()); - - for(vector< BSONObj >::iterator i = locs.begin(); i != locs.end(); ++i) { - // Ignore all locations not hashed to the key's hash, since we may see - // those later - if(_converter->hash(*i) != keyHash) continue; - locsForNode.push_back(*i); - } - } - - virtual int addSpecific(const GeoKeyNode& node, const Point& p, bool inBounds, double d, - bool newDoc) = 0; - virtual KeyResult approxKeyCheck(const Point& p, double& keyD) = 0; - virtual bool exactDocCheck(const Point& p, double& d) = 0; - virtual bool expensiveExactCheck(){ return false; } - - long long found() const { return _found; } - - TwoDAccessMethod* _accessMethod; - shared_ptr<GeoHashConverter> _converter; - map<DiskLoc, bool> _matched; - shared_ptr<CoveredIndexMatcher> _matcher; - - long long _lookedAt; - long long _matchesPerfd; - long long _objectsLoaded; - long long _pointsLoaded; - long long _found; - - bool _uniqueDocs; - bool _needDistance; - }; - - struct BtreeLocation { - BtreeLocation() { } - - scoped_ptr<BtreeCursor> _cursor; - scoped_ptr<FieldRangeSet> _frs; - // TODO: Turn into a KeyPattern object when FieldRangeVector takes one. - BSONObj _keyPattern; - - BSONObj key() { return _cursor->currKey(); } - - bool hasPrefix(const GeoHash& hash) { - BSONObj k = key(); - BSONElement e = k.firstElement(); - if (e.eoo()) - return false; - return GeoHash(e).hasPrefix(hash); - } - - bool checkAndAdvance(const GeoHash& hash, int& totalFound, GeoAccumulator* all){ - if(! _cursor->ok() || ! hasPrefix(hash)) return false; - - if(all){ - totalFound++; - GeoKeyNode n(_cursor->getBucket(), _cursor->getKeyOfs(), _cursor->currLoc(), - _cursor->currKey()); - all->add(n); - } - _cursor->advance(); - - return true; - } - - void save(){ _cursor->noteLocation(); } - void restore(){ _cursor->checkLocation(); } - - string toString() { - stringstream ss; - ss << "bucket: " << _cursor->getBucket().toString() << " pos: " << _cursor->getKeyOfs() - << (_cursor->ok() ? (str::stream() << " k: " << _cursor->currKey() - << " o : " << _cursor->current()["_id"]) - : (string)"[none]") << endl; - return ss.str(); - } - - // Returns the min and max keys which bound a particular location. - // The only time these may be equal is when we actually equal the location - // itself, otherwise our expanding algorithm will fail. - static bool initial(IndexDescriptor* descriptor, const TwoDIndexingParams& params, - BtreeLocation& min, BtreeLocation& max, - GeoHash start, int& found, GeoAccumulator* hopper) { - verify(descriptor); - verify(hopper); - // Would be nice to build this directly, but bug in max/min queries SERVER-3766 and lack - // of interface makes this easiest for now. - - BSONObj minQuery = BSON(params.geo << BSON("$gt" << MINKEY - << start.wrap("$lte").firstElement())); - BSONObj maxQuery = BSON(params.geo << BSON("$lt" << MAXKEY - << start.wrap("$gt").firstElement())); - - min._frs.reset(new FieldRangeSet(descriptor->parentNS().c_str(), - minQuery, true, false)); - - max._frs.reset(new FieldRangeSet(descriptor->parentNS().c_str(), - maxQuery, true, false)); - - BSONObjBuilder bob; - bob.append(params.geo, 1); - for(vector<pair<string, int> >::const_iterator i = params.other.begin(); - i != params.other.end(); i++){ - bob.append(i->first, i->second); - } - BSONObj iSpec = bob.obj(); - - min._keyPattern = iSpec; - max._keyPattern = iSpec; - - shared_ptr<FieldRangeVector> frvMin(new FieldRangeVector(*min._frs, min._keyPattern, -1)); - shared_ptr<FieldRangeVector> frvMax(new FieldRangeVector(*max._frs, max._keyPattern, 1)); - - min._cursor.reset(BtreeCursor::make(nsdetails(descriptor->parentNS()), - descriptor->getOnDisk(), frvMin, 0, -1)); - - max._cursor.reset(BtreeCursor::make(nsdetails(descriptor->parentNS()), - descriptor->getOnDisk(), frvMax, 0, 1)); - - return min._cursor->ok() || max._cursor->ok(); - } - }; - - class GeoCursorBase { - public: - virtual ~GeoCursorBase() { } - virtual void explainDetails(BSONObjBuilder& b) { } - virtual bool ok() = 0; - bool eof() { return !ok(); } - virtual BSONObj current() = 0; - virtual DiskLoc currLoc() = 0; - virtual bool advance() = 0; /*true=ok*/ - virtual BSONObj currKey() const = 0; - static const shared_ptr<CoveredIndexMatcher> otherEmptyMatcher; - virtual void noteLocation() { } - virtual void checkLocation() { } - virtual bool supportGetMore() { return false; } - virtual string toString() = 0; - }; - - const shared_ptr<CoveredIndexMatcher> GeoCursorBase::otherEmptyMatcher( - new CoveredIndexMatcher(BSONObj(), BSONObj())); - - // TODO: Pull out the cursor bit from the browse, have GeoBrowse as field of cursor to clean up - // this hierarchy a bit. Also probably useful to look at whether GeoAccumulator can be a member - // instead of a superclass. - class GeoBrowse : public GeoCursorBase, public GeoAccumulator { - public: - // The max points which should be added to an expanding box at one time - static const int maxPointsHeuristic = 50; - - // Expand states - enum State { - START, - DOING_EXPAND, - DONE_NEIGHBOR, - DONE - } _state; - - GeoBrowse(TwoDAccessMethod* accessMethod, string type, BSONObj filter = BSONObj(), - bool uniqueDocs = true, bool needDistance = false) - : GeoCursorBase(), - GeoAccumulator(accessMethod, filter, uniqueDocs, needDistance), - _type(type), _filter(filter), _firstCall(true), _noted(false), _nscanned(), - _nDirtied(0), _nChangedOnYield(0), _nRemovedOnYield(0), _centerPrefix(0, 0, 0), - _btreeInterface(accessMethod->getInterface()), - _descriptor(accessMethod->getDescriptor()), - _converter(accessMethod->getParams().geoHashConverter), - _params(accessMethod->getParams()) { - - // Set up the initial expand state - _state = START; - _neighbor = -1; - _foundInExp = 0; - - } - - virtual string toString() { return (string)"GeoBrowse-" + _type; } - - virtual bool ok() { - bool filled = false; - LOG(CDEBUG) << "Checking cursor, in state " << (int) _state << ", first call " - << _firstCall << ", empty : " << _cur.isEmpty() << ", dirty : " - << _cur.isDirty() << ", stack : " << _stack.size() << endl; - - bool first = _firstCall; - if (_firstCall) { - fillStack(maxPointsHeuristic); - filled = true; - _firstCall = false; - } - if (! _cur.isCleanAndEmpty() || _stack.size()) { - if (first) { ++_nscanned; } - if(_noted && filled) noteLocation(); - return true; - } - - while (moreToDo()) { - LOG(CDEBUG) << "Refilling stack..." << endl; - fillStack(maxPointsHeuristic); - filled = true; - if (! _cur.isCleanAndEmpty()) { - if (first) { ++_nscanned; } - if(_noted && filled) noteLocation(); - return true; - } - } - - if(_noted && filled) noteLocation(); - return false; - } - - virtual bool advance() { - _cur._o = BSONObj(); - - if (_stack.size()) { - _cur = _stack.front(); - _stack.pop_front(); - ++_nscanned; - return true; - } - - if (! moreToDo()) return false; - - bool filled = false; - while (_cur.isCleanAndEmpty() && moreToDo()){ - fillStack(maxPointsHeuristic); - filled = true; - } - - if(_noted && filled) noteLocation(); - return ! _cur.isCleanAndEmpty() && ++_nscanned; - } - - virtual void noteLocation() { - _noted = true; - LOG(CDEBUG) << "Noting location with " << _stack.size() - << (_cur.isEmpty() ? "" : " + 1 ") << " points " << endl; - - // Make sure we advance past the point we're at now, - // since the current location may move on an update/delete - // if(_state == DOING_EXPAND){ - // if(_min.hasPrefix(_prefix)){ _min.advance(-1, _foundInExp, this); } - // if(_max.hasPrefix(_prefix)){ _max.advance( 1, _foundInExp, this); } - // } - - // Remember where our _max, _min are - _min.save(); - _max.save(); - - LOG(CDEBUG) << "Min " << _min.toString() << endl; - LOG(CDEBUG) << "Max " << _max.toString() << endl; - - // Dirty all our queued stuff - for(list<GeoPoint>::iterator i = _stack.begin(); i != _stack.end(); i++){ - LOG(CDEBUG) << "Undirtying stack point with id " << i->_id << endl; - if(i->makeDirty()) _nDirtied++; - verify(i->isDirty()); - } - - // Check current item - if(! _cur.isEmpty()){ - if(_cur.makeDirty()) _nDirtied++; - } - - // Our cached matches become invalid now - //_matched.clear(); - } - - /* - void fixMatches(DiskLoc oldLoc, DiskLoc newLoc){ - map<DiskLoc, bool>::iterator match = _matched.find(oldLoc); - if(match != _matched.end()){ - bool val = match->second; - _matched.erase(oldLoc); - _matched[ newLoc ] = val; - } - }*/ - - /* called before query getmore block is iterated */ - virtual void checkLocation() { - LOG(CDEBUG) << "Restoring location with " << _stack.size() - << (! _cur.isDirty() ? "" : " + 1 ") << " points " << endl; - // We can assume an error was thrown earlier if this database somehow disappears - // Recall our _max, _min - _min.restore(); - _max.restore(); - - LOG(CDEBUG) << "Min " << _min.toString() << endl; - LOG(CDEBUG) << "Max " << _max.toString() << endl; - - // If the current key moved, we may have been advanced past the current point - // - need to check this - // if(_state == DOING_EXPAND){ - // if(_min.hasPrefix(_prefix)){ _min.advance(-1, _foundInExp, this); } - // if(_max.hasPrefix(_prefix)){ _max.advance( 1, _foundInExp, this); } - //} - - // Undirty all the queued stuff - // Dirty all our queued stuff - list<GeoPoint>::iterator i = _stack.begin(); - while(i != _stack.end()){ - LOG(CDEBUG) << "Undirtying stack point with id " << i->_id << endl; - - DiskLoc oldLoc; - if(i->unDirty(_btreeInterface, _descriptor, oldLoc)){ - // Document is in same location - LOG(CDEBUG) << "Undirtied " << oldLoc << endl; - i++; - } else if(! i->loc().isNull()){ - // Re-found document somewhere else - LOG(CDEBUG) << "Changed location of " << i->_id << " : " - << i->loc() << " vs " << oldLoc << endl; - _nChangedOnYield++; - //fixMatches(oldLoc, i->loc()); - i++; - } else { - // Can't re-find document - LOG(CDEBUG) << "Removing document " << i->_id << endl; - _nRemovedOnYield++; - _found--; - verify(_found >= 0); - // Can't find our key again, remove - i = _stack.erase(i); - } - } - - if(_cur.isDirty()){ - LOG(CDEBUG) << "Undirtying cur point with id : " << _cur._id << endl; - } - - // Check current item - DiskLoc oldLoc; - if(_cur.isDirty() && ! _cur.unDirty(_btreeInterface, _descriptor, oldLoc)){ - if(_cur.loc().isNull()){ - // Document disappeared! - LOG(CDEBUG) << "Removing cur point " << _cur._id << endl; - _nRemovedOnYield++; - advance(); - } else{ - // Document moved - LOG(CDEBUG) << "Changed location of cur point " << _cur._id << " : " - << _cur.loc() << " vs " << oldLoc << endl; - _nChangedOnYield++; - //fixMatches(oldLoc, _cur.loc()); - } - } - - _noted = false; - } - - virtual Record* _current() { verify(ok()); LOG(CDEBUG + 1) << "_current " << _cur._loc.obj()["_id"] << endl; return _cur._loc.rec(); } - virtual BSONObj current() { verify(ok()); LOG(CDEBUG + 1) << "current " << _cur._o << endl; return _cur._o; } - virtual DiskLoc currLoc() { verify(ok()); LOG(CDEBUG + 1) << "currLoc " << _cur._loc << endl; return _cur._loc; } - virtual BSONObj currKey() const { return _cur._key; } - - virtual CoveredIndexMatcher* matcher() const { - if(_matcher.get()) return _matcher.get(); - else return GeoCursorBase::otherEmptyMatcher.get(); - } - - // Are we finished getting points? - virtual bool moreToDo() { return _state != DONE; } - virtual bool supportGetMore() { return true; } - - Box makeBox(const GeoHash &hash) const { - double sizeEdge = _converter->sizeEdge(hash); - Point min(_converter->unhashToPoint(hash)); - Point max(min.x + sizeEdge, min.y + sizeEdge); - return Box(min, max); - } - - // Fills the stack, but only checks a maximum number of maxToCheck points at a time. - // Further calls to this function will continue the expand/check neighbors algorithm. - virtual void fillStack(int maxToCheck, int maxToAdd = -1, bool onlyExpand = false) { -#ifdef GEODEBUGGING - log() << "Filling stack with maximum of " << maxToCheck - << ", state : " << (int) _state << endl; -#endif - if(maxToAdd < 0) maxToAdd = maxToCheck; - int maxFound = _foundInExp + maxToCheck; - verify(maxToCheck > 0); - verify(maxFound > 0); - verify(_found <= 0x7fffffff); // conversion to int - int maxAdded = static_cast<int>(_found) + maxToAdd; - verify(maxAdded >= 0); // overflow check - - bool isNeighbor = _centerPrefix.constrains(); - - // Starting a box expansion - if (_state == START) { - // Get the very first hash point, if required - if(! isNeighbor) - _prefix = expandStartHash(); - GEODEBUG("initializing btree"); - -#ifdef GEODEBUGGING - log() << "Initializing from b-tree with hash of " << _prefix << " @ " - << Box(_g, _prefix) << endl; -#endif - - if (!BtreeLocation::initial(_descriptor, _params, _min, _max, _prefix, - _foundInExp, this)) { - _state = isNeighbor ? DONE_NEIGHBOR : DONE; - } else { - _state = DOING_EXPAND; - _lastPrefix.reset(); - } - - GEODEBUG((_state == DONE_NEIGHBOR || _state == DONE ? "not initialized" - : "initializedFig")); - } - - // Doing the actual box expansion - if (_state == DOING_EXPAND) { - while (true) { - GEODEBUG("box prefix [" << _prefix << "]"); -#ifdef GEODEBUGGING - if(_prefix.constrains()) { - log() << "current expand box : " << Box(_g, _prefix).toString() << endl; - } - else { - log() << "max expand box." << endl; - } -#endif - GEODEBUG("expanding box points... "); - - // Record the prefix we're actively exploring... - _expPrefix.reset(new GeoHash(_prefix)); - - // Find points inside this prefix - while (_min.checkAndAdvance(_prefix, _foundInExp, this) - && _foundInExp < maxFound && _found < maxAdded) {} - while (_max.checkAndAdvance(_prefix, _foundInExp, this) - && _foundInExp < maxFound && _found < maxAdded) {} - -#ifdef GEODEBUGGING - log() << "finished expand, checked : " - << (maxToCheck - (maxFound - _foundInExp)) - << " found : " << (maxToAdd - (maxAdded - _found)) - << " max : " << maxToCheck << " / " << maxToAdd << endl; -#endif - GEODEBUG("finished expand, found : " << (maxToAdd - (maxAdded - _found))); - if(_foundInExp >= maxFound || _found >= maxAdded) return; - - // We've searched this prefix fully, remember - _lastPrefix.reset(new GeoHash(_prefix)); - - // If we've searched the entire space, we're finished. - if (! _prefix.constrains()) { - GEODEBUG("box exhausted"); - _state = DONE; - notePrefix(); - return; - } - - // If we won't fit in the box, and we're not doing a sub-scan, increase the size - if (! fitsInBox(_converter->sizeEdge(_prefix)) && _fringe.size() == 0) { - // If we're still not expanded bigger than the box size, expand again - _prefix = _prefix.up(); - continue; - } - - // We're done and our size is large enough - _state = DONE_NEIGHBOR; - - // Go to the next sub-box, if applicable - if(_fringe.size() > 0) _fringe.pop_back(); - // Go to the next neighbor if this was the last sub-search - if(_fringe.size() == 0) _neighbor++; - break; - } - notePrefix(); - } - - // If we doeighbors - if(onlyExpand) return; - - // If we're done expanding the current box... - if(_state == DONE_NEIGHBOR) { - // Iterate to the next neighbor - // Loop is useful for cases where we want to skip over boxes entirely, - // otherwise recursion increments the neighbors. - for (; _neighbor < 9; _neighbor++) { - // If we have no fringe for the neighbor, make sure we have the default fringe - if(_fringe.size() == 0) _fringe.push_back(""); - - if(! isNeighbor) { - _centerPrefix = _prefix; - _centerBox = makeBox(_centerPrefix); - isNeighbor = true; - } - - int i = (_neighbor / 3) - 1; - int j = (_neighbor % 3) - 1; - - if ((i == 0 && j == 0) || - (i < 0 && _centerPrefix.atMinX()) || - (i > 0 && _centerPrefix.atMaxX()) || - (j < 0 && _centerPrefix.atMinY()) || - (j > 0 && _centerPrefix.atMaxY())) { - - continue; // main box or wrapped edge - // TODO: We may want to enable wrapping in future, probably best as layer - // on top of this search. - } - - // Make sure we've got a reasonable center - verify(_centerPrefix.constrains()); - - GeoHash _neighborPrefix = _centerPrefix; - _neighborPrefix.move(i, j); - - GEODEBUG("moving to neighbor " << _neighbor << " @ " << i << ", " << j - << " fringe : " << _fringe.size()); - PREFIXDEBUG(_centerPrefix, _g); - PREFIXDEBUG(_neighborPrefix, _g); - - while(_fringe.size() > 0) { - _prefix = _neighborPrefix + _fringe.back(); - Box cur(makeBox(_prefix)); - - PREFIXDEBUG(_prefix, _g); - - double intAmt = intersectsBox(cur); - - // No intersection - if(intAmt <= 0) { - GEODEBUG("skipping box" << cur.toString()); - _fringe.pop_back(); - continue; - } else if(intAmt < 0.5 && _prefix.canRefine() - && _fringe.back().size() < 4 /* two bits */) { - // Small intersection, refine search - string lastSuffix = _fringe.back(); - _fringe.pop_back(); - _fringe.push_back(lastSuffix + "00"); - _fringe.push_back(lastSuffix + "01"); - _fringe.push_back(lastSuffix + "11"); - _fringe.push_back(lastSuffix + "10"); - continue; - } - - // Restart our search from a diff box. - _state = START; - verify(! onlyExpand); - verify(_found <= 0x7fffffff); - fillStack(maxFound - _foundInExp, maxAdded - static_cast<int>(_found)); - // When we return from the recursive fillStack call, we'll either have - // checked enough points or be entirely done. Max recurse depth is < 8 * - // 16. - // If we're maxed out on points, return - if(_foundInExp >= maxFound || _found >= maxAdded) { - // Make sure we'll come back to add more points - verify(_state == DOING_EXPAND); - return; - } - - // Otherwise we must be finished to return - verify(_state == DONE); - return; - } - } - // Finished with neighbors - _state = DONE; - } - } - - // The initial geo hash box for our first expansion - virtual GeoHash expandStartHash() = 0; - - // Whether the current box width is big enough for our search area - virtual bool fitsInBox(double width) = 0; - - // The amount the current box overlaps our search area - virtual double intersectsBox(Box& cur) = 0; - - bool remembered(BSONObj o){ - BSONObj seenId = o["_id"].wrap("").getOwned(); - if(_seenIds.find(seenId) != _seenIds.end()){ - LOG(CDEBUG + 1) << "Object " << o["_id"] << " already seen." << endl; - return true; - } else{ - _seenIds.insert(seenId); - LOG(CDEBUG + 1) << "Object " << o["_id"] << " remembered." << endl; - return false; - } - } - - virtual int addSpecific(const GeoKeyNode& node, const Point& keyP, bool onBounds, - double keyD, bool potentiallyNewDoc) { - int found = 0; - // We need to handle every possible point in this method, even those not in the key - // value, to avoid us tracking which hashes we've already seen. - if(! potentiallyNewDoc){ return 0; } - - // Final check for new doc - // OK to touch, since we're probably returning this object now - if(remembered(node.recordLoc.obj())) return 0; - - if(_uniqueDocs && ! onBounds) { - //log() << "Added ind to " << _type << endl; - _stack.push_front(GeoPoint(node)); - found++; - } else { - // We now handle every possible point in the document, even those not in the key - // value, since we're iterating through them anyway - prevents us from having to - // save the hashes we've seen per-doc - // If we're filtering by hash, get the original - bool expensiveExact = expensiveExactCheck(); - - vector< BSONObj > locs; - getPointsFor(node._key, node.recordLoc.obj(), locs, true); - for(vector< BSONObj >::iterator i = locs.begin(); i != locs.end(); ++i){ - double d = -1; - Point p(*i); - // We can avoid exact document checks by redoing approx checks, - // if the exact checks are more expensive. - bool needExact = true; - if(expensiveExact){ - verify(false); - KeyResult result = approxKeyCheck(p, d); - if(result == BAD) continue; - else if(result == GOOD) needExact = false; - } - - if(! needExact || exactDocCheck(p, d)){ - //log() << "Added mult to " << _type << endl; - _stack.push_front(GeoPoint(node)); - found++; - // If returning unique, just exit after first point is added - if(_uniqueDocs) break; - } - } - } - - while(_cur.isCleanAndEmpty() && _stack.size() > 0){ - _cur = _stack.front(); - _stack.pop_front(); - } - - return found; - } - - virtual long long nscanned() { - if (_firstCall) { ok(); } - return _nscanned; - } - - virtual void explainDetails(BSONObjBuilder& b){ - b << "lookedAt" << _lookedAt; - b << "matchesPerfd" << _matchesPerfd; - b << "objectsLoaded" << _objectsLoaded; - b << "pointsLoaded" << _pointsLoaded; - b << "pointsSavedForYield" << _nDirtied; - b << "pointsChangedOnYield" << _nChangedOnYield; - b << "pointsRemovedOnYield" << _nRemovedOnYield; - } - - virtual BSONObj prettyIndexBounds() const { - vector<GeoHash>::const_iterator i = _expPrefixes.end(); - if(_expPrefixes.size() > 0 && *(--i) != *(_expPrefix.get())) - _expPrefixes.push_back(*(_expPrefix.get())); - - BSONObjBuilder bob; - BSONArrayBuilder bab; - for(i = _expPrefixes.begin(); i != _expPrefixes.end(); ++i){ - bab << makeBox(*i).toBSON(); - } - bob << _params.geo << bab.arr(); - return bob.obj(); - } - - void notePrefix() { _expPrefixes.push_back(_prefix); } - - string _type; - BSONObj _filter; - list<GeoPoint> _stack; - set<BSONObj> _seenIds; - - GeoPoint _cur; - bool _firstCall; - bool _noted; - - long long _nscanned; - long long _nDirtied; - long long _nChangedOnYield; - long long _nRemovedOnYield; - - // The current box we're expanding (-1 is first/center box) - int _neighbor; - - // The points we've found so far - int _foundInExp; - - // The current hash prefix we're expanding and the center-box hash prefix - GeoHash _prefix; - shared_ptr<GeoHash> _lastPrefix; - GeoHash _centerPrefix; - list<string> _fringe; - int recurseDepth; - Box _centerBox; - - // Start and end of our search range in the current box - BtreeLocation _min; - BtreeLocation _max; - - shared_ptr<GeoHash> _expPrefix; - mutable vector<GeoHash> _expPrefixes; - BtreeInterface* _btreeInterface; - IndexDescriptor* _descriptor; - shared_ptr<GeoHashConverter> _converter; - TwoDIndexingParams _params; - }; - - class GeoHopper : public GeoBrowse { - public: - typedef multiset<GeoPoint> Holder; - - GeoHopper(TwoDAccessMethod* accessMethod, - unsigned max, - const Point& n, - const BSONObj& filter = BSONObj(), - double maxDistance = numeric_limits<double>::max(), - GeoDistType type = GEO_PLANE, - bool uniqueDocs = false, - bool needDistance = true) - : GeoBrowse(accessMethod, "search", filter, uniqueDocs, needDistance), - _max(max), - _near(n), - _maxDistance(maxDistance), - _type(type), - _distError(type == GEO_PLANE - ? accessMethod->getParams().geoHashConverter->getError() - : accessMethod->getParams().geoHashConverter->getErrorSphere()), - _farthest(0) { } - - virtual KeyResult approxKeyCheck(const Point& p, double& d) { - // Always check approximate distance, since it lets us avoid doing - // checks of the rest of the object if it succeeds - switch (_type) { - case GEO_PLANE: - d = distance(_near, p); - break; - case GEO_SPHERE: - checkEarthBounds(p); - d = spheredist_deg(_near, p); - break; - default: verify(false); - } - verify(d >= 0); - - GEODEBUG("\t\t\t\t\t\t\t checkDistance " << _near.toString() - << "\t" << p.toString() << "\t" << d - << " farthest: " << farthest()); - - // If we need more points - double borderDist = (_points.size() < _max ? _maxDistance : farthest()); - - if (d >= borderDist - 2 * _distError && d <= borderDist + 2 * _distError) return BORDER; - else return d < borderDist ? GOOD : BAD; - } - - virtual bool exactDocCheck(const Point& p, double& d){ - bool within = false; - - // Get the appropriate distance for the type - switch (_type) { - case GEO_PLANE: - d = distance(_near, p); - within = distanceWithin(_near, p, _maxDistance); - break; - case GEO_SPHERE: - checkEarthBounds(p); - d = spheredist_deg(_near, p); - within = (d <= _maxDistance); - break; - default: verify(false); - } - - return within; - } - - // Always in distance units, whether radians or normal - double farthest() const { return _farthest; } - - virtual int addSpecific(const GeoKeyNode& node, const Point& keyP, bool onBounds, - double keyD, bool potentiallyNewDoc) { - // Unique documents - GeoPoint newPoint(node, keyD, false); - int prevSize = _points.size(); - - // STEP 1 : Remove old duplicate points from the set if needed - if(_uniqueDocs){ - // Lookup old point with same doc - map<DiskLoc, Holder::iterator>::iterator oldPointIt = _seenPts.find(newPoint.loc()); - - if(oldPointIt != _seenPts.end()){ - const GeoPoint& oldPoint = *(oldPointIt->second); - // We don't need to care if we've already seen this same approx pt or better, - // or we've already gone to disk once for the point - if(oldPoint < newPoint){ - GEODEBUG("\t\tOld point closer than new point"); - return 0; - } - GEODEBUG("\t\tErasing old point " << oldPointIt->first.obj()); - _points.erase(oldPointIt->second); - } - } - - Holder::iterator newIt = _points.insert(newPoint); - if(_uniqueDocs) _seenPts[ newPoint.loc() ] = newIt; - - GEODEBUG("\t\tInserted new point " << newPoint.toString() << " approx : " << keyD); - - verify(_max > 0); - - Holder::iterator lastPtIt = _points.end(); - lastPtIt--; - _farthest = lastPtIt->distance() + 2 * _distError; - return _points.size() - prevSize; - } - - // Removes extra points from end of _points set. - // Check can be a bit costly if we have lots of exact points near borders, - // so we'll do this every once and awhile. - void processExtraPoints(){ - if(_points.size() == 0) return; - int prevSize = _points.size(); - - // Erase all points from the set with a position >= _max *and* - // whose distance isn't close to the _max - 1 position distance - int numToErase = _points.size() - _max; - if(numToErase < 0) numToErase = 0; - - // Get the first point definitely in the _points array - Holder::iterator startErase = _points.end(); - for(int i = 0; i < numToErase + 1; i++) startErase--; - _farthest = startErase->distance() + 2 * _distError; - - startErase++; - while(numToErase > 0 && startErase->distance() <= _farthest){ - GEODEBUG("\t\tNot erasing point " << startErase->toString()); - numToErase--; - startErase++; - verify(startErase != _points.end() || numToErase == 0); - } - - if(_uniqueDocs){ - for(Holder::iterator i = startErase; i != _points.end(); ++i) - _seenPts.erase(i->loc()); - } - - _points.erase(startErase, _points.end()); - - int diff = _points.size() - prevSize; - if(diff > 0) _found += diff; - else _found -= -diff; - } - - unsigned _max; - Point _near; - Holder _points; - double _maxDistance; - GeoDistType _type; - double _distError; - double _farthest; - - // Safe to use currently since we don't yield in $near searches. If we do start to yield, - // we may need to replace dirtied disklocs in our holder / ensure our logic is correct. - map<DiskLoc, Holder::iterator> _seenPts; - }; - - class GeoSearch : public GeoHopper { - public: - GeoSearch(TwoDAccessMethod* accessMethod, - const Point& startPt, - int numWanted = 100, - BSONObj filter = BSONObj(), - double maxDistance = numeric_limits<double>::max(), - GeoDistType type = GEO_PLANE, - bool uniqueDocs = false, - bool needDistance = false) - : GeoHopper(accessMethod, numWanted, startPt, filter, maxDistance, type, - uniqueDocs, needDistance), - _start(accessMethod->getParams().geoHashConverter->hash(startPt.x, startPt.y)), - _numWanted(numWanted), - _type(type), - _params(accessMethod->getParams()) { - - _nscanned = 0; - _found = 0; - - if(_maxDistance < 0){ - _scanDistance = numeric_limits<double>::max(); - } else if (type == GEO_PLANE) { - _scanDistance = maxDistance + _params.geoHashConverter->getError(); - } else if (type == GEO_SPHERE) { - checkEarthBounds(startPt); - // TODO: consider splitting into x and y scan distances - _scanDistance = computeXScanDistance(startPt.y, - rad2deg(_maxDistance) + _params.geoHashConverter->getError()); - } - - verify(_scanDistance > 0); - } - - - /** Check if we've already looked at a key. ALSO marks as seen, anticipating a follow-up - * call to add(). This is broken out to avoid some work extracting the key bson if it's an - * already seen point. - */ - private: - set< pair<DiskLoc,int> > _seen; - public: - void exec() { - if(_numWanted == 0) return; - - /* - * Search algorithm - * 1) use geohash prefix to find X items - * 2) compute max distance from want to an item - * 3) find optimal set of boxes that complete circle - * 4) use regular btree cursors to scan those boxes - */ - - // Part 1 - { - do { - long long f = found(); - verify(f <= 0x7fffffff); - fillStack(maxPointsHeuristic, _numWanted - static_cast<int>(f), true); - processExtraPoints(); - } while(_state != DONE && _state != DONE_NEIGHBOR && - found() < _numWanted && - (!_prefix.constrains() || - _params.geoHashConverter->sizeEdge(_prefix) <= _scanDistance)); - - // If we couldn't scan or scanned everything, we're done - if(_state == DONE){ - expandEndPoints(); - return; - } - } - -#ifdef GEODEBUGGING - log() << "part 1 of near search completed, found " << found() - << " points (out of " << _foundInExp << " scanned)" - << " in expanded region " << _prefix << " @ " << Box(_g, _prefix) - << " with furthest distance " << farthest() << endl; -#endif - - // Part 2 - { - // Find farthest distance for completion scan - double farDist = farthest(); - if(found() < _numWanted) { - // Not enough found in Phase 1 - farDist = _scanDistance; - } - else if (_type == GEO_PLANE) { - // Enough found, but need to search neighbor boxes - farDist += _params.geoHashConverter->getError(); - } - else if (_type == GEO_SPHERE) { - // Enough found, but need to search neighbor boxes - farDist = std::min(_scanDistance, - computeXScanDistance(_near.y, - rad2deg(farDist)) - + 2 * _params.geoHashConverter->getError()); - } - verify(farDist >= 0); - GEODEBUGPRINT(farDist); - - // Find the box that includes all the points we need to return - _want = Box(_near.x - farDist, _near.y - farDist, farDist * 2); - GEODEBUGPRINT(_want.toString()); - - // Remember the far distance for further scans - _scanDistance = farDist; - - // Reset the search, our distances have probably changed - if(_state == DONE_NEIGHBOR){ - _state = DOING_EXPAND; - _neighbor = -1; - } - - // Do regular search in the full region - do { - fillStack(maxPointsHeuristic); - processExtraPoints(); - } - while(_state != DONE); - } - - GEODEBUG("done near search with " << _points.size() << " points "); - expandEndPoints(); - } - - void addExactPoints(const GeoPoint& pt, Holder& points, bool force){ - int before, after; - addExactPoints(pt, points, before, after, force); - } - - void addExactPoints(const GeoPoint& pt, Holder& points, int& before, int& after, - bool force){ - before = 0; - after = 0; - - GEODEBUG("Adding exact points for " << pt.toString()); - - if(pt.isExact()){ - if(force) points.insert(pt); - return; - } - - vector<BSONObj> locs; - getPointsFor(pt.key(), pt.obj(), locs, _uniqueDocs); - - GeoPoint nearestPt(pt, -1, true); - - for(vector<BSONObj>::iterator i = locs.begin(); i != locs.end(); i++){ - Point loc(*i); - double d; - if(! exactDocCheck(loc, d)) continue; - - if(_uniqueDocs && (nearestPt.distance() < 0 || d < nearestPt.distance())){ - nearestPt._distance = d; - nearestPt._pt = *i; - continue; - } else if(! _uniqueDocs){ - GeoPoint exactPt(pt, d, true); - exactPt._pt = *i; - points.insert(exactPt); - exactPt < pt ? before++ : after++; - } - } - - if(_uniqueDocs && nearestPt.distance() >= 0){ - points.insert(nearestPt); - if(nearestPt < pt) before++; - else after++; - } - } - - // TODO: Refactor this back into holder class, allow to run periodically when we are seeing - // a lot of pts - void expandEndPoints(bool finish = true){ - processExtraPoints(); - // All points in array *could* be in maxDistance - - // Step 1 : Trim points to max size TODO: This check will do little for now, but is - // skeleton for future work in incremental $near - // searches - if(_max > 0){ - int numToErase = _points.size() - _max; - if(numToErase > 0){ - Holder tested; - // Work backward through all points we're not sure belong in the set - Holder::iterator maybePointIt = _points.end(); - maybePointIt--; - double approxMin = maybePointIt->distance() - 2 * _distError; - - // Insert all - int erased = 0; - while(_points.size() > 0 - && (maybePointIt->distance() >= approxMin || erased < numToErase)){ - - Holder::iterator current = maybePointIt; - if (current != _points.begin()) - --maybePointIt; - - addExactPoints(*current, tested, true); - _points.erase(current); - erased++; - - if(tested.size()) - approxMin = tested.begin()->distance() - 2 * _distError; - } - - int numToAddBack = erased - numToErase; - verify(numToAddBack >= 0); - - Holder::iterator testedIt = tested.begin(); - for(int i = 0; i < numToAddBack && testedIt != tested.end(); i++){ - _points.insert(*testedIt); - testedIt++; - } - } - } - - // We've now trimmed first set of unneeded points - - GEODEBUG("\t\t Start expanding, num points : " << _points.size() << " max : " << _max); - - // Step 2: iterate through all points and add as needed - unsigned expandedPoints = 0; - Holder::iterator it = _points.begin(); - double expandWindowEnd = -1; - - while(it != _points.end()){ - const GeoPoint& currPt = *it; - // TODO: If one point is exact, maybe not 2 * _distError - - // See if we're in an expand window - bool inWindow = currPt.distance() <= expandWindowEnd; - // If we're not, and we're done with points, break - if(! inWindow && expandedPoints >= _max) break; - - bool expandApprox = !currPt.isExact() && - (!_uniqueDocs || (finish && _needDistance) || inWindow); - - if (expandApprox) { - // Add new point(s). These will only be added in a radius of 2 * _distError - // around the current point, so should not affect previously valid points. - int before, after; - addExactPoints(currPt, _points, before, after, false); - expandedPoints += before; - - if(_max > 0 && expandedPoints < _max) - expandWindowEnd = currPt.distance() + 2 * _distError; - - // Iterate to the next point - Holder::iterator current = it++; - // Erase the current point - _points.erase(current); - } else{ - expandedPoints++; - it++; - } - } - - GEODEBUG("\t\tFinished expanding, num points : " << _points.size() - << " max : " << _max); - - // Finish - // TODO: Don't really need to trim? - for(; expandedPoints > _max; expandedPoints--) it--; - _points.erase(it, _points.end()); - } - - virtual GeoHash expandStartHash(){ return _start; } - - // Whether the current box width is big enough for our search area - 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); } - - GeoHash _start; - int _numWanted; - double _scanDistance; - long long _nscanned; - int _found; - GeoDistType _type; - Box _want; - TwoDIndexingParams& _params; - }; - - class GeoSearchCursor : public GeoCursorBase { - public: - GeoSearchCursor(shared_ptr<GeoSearch> s) - : GeoCursorBase(), _s(s), _cur(s->_points.begin()), _end(s->_points.end()), - _nscanned() { - if (_cur != _end) { - ++_nscanned; - } - } - - virtual ~GeoSearchCursor() {} - - virtual bool ok() { return _cur != _end; } - virtual Record* _current() { verify(ok()); return _cur->_loc.rec(); } - virtual BSONObj current() { verify(ok()); return _cur->_o; } - virtual DiskLoc currLoc() { verify(ok()); return _cur->_loc; } - virtual BSONObj currKey() const { return _cur->_key; } - virtual string toString() { return "GeoSearchCursor"; } - virtual long long nscanned() { return _nscanned; } - - virtual bool advance() { - if(ok()){ - _cur++; - incNscanned(); - return ok(); - } - return false; - } - - virtual BSONObj prettyStartKey() const { - return BSON(_s->_params.geo << _s->_prefix.toString()); - } - virtual BSONObj prettyEndKey() const { - GeoHash temp = _s->_prefix; - temp.move(1, 1); - return BSON(_s->_params.geo << temp.toString()); - } - - virtual CoveredIndexMatcher* matcher() const { - if(_s->_matcher.get()) return _s->_matcher.get(); - else return otherEmptyMatcher.get(); - } - - shared_ptr<GeoSearch> _s; - GeoHopper::Holder::iterator _cur; - GeoHopper::Holder::iterator _end; - - void incNscanned() { if (ok()) { ++_nscanned; } } - long long _nscanned; - }; - - class GeoCircleBrowse : public GeoBrowse { - public: - GeoCircleBrowse(TwoDAccessMethod* accessMethod, const BSONObj& circle, - BSONObj filter = BSONObj(), const string& type = "$center", - bool uniqueDocs = true) - : GeoBrowse(accessMethod, "circle", filter, uniqueDocs) { - - uassert(16783, "$center needs 2 fields (middle,max distance)", circle.nFields() == 2); - - BSONObjIterator i(circle); - BSONElement center = i.next(); - - uassert(16784, "the first field of $center object must be a location object", - center.isABSONObj()); - - _converter = accessMethod->getParams().geoHashConverter; - - // Get geohash and exact center point - // TODO: For wrapping search, may be useful to allow center points outside-of-bounds - // here. Calculating the nearest point as a hash start inside the region would then be - // required. - _start = _converter->hash(center); - _startPt = Point(center); - - _maxDistance = i.next().numberDouble(); - uassert(16785, "need a max distance >= 0 ", _maxDistance >= 0); - - if (type == "$center") { - // Look in box with bounds of maxDistance in either direction - _type = GEO_PLANE; - xScanDistance = _maxDistance + _converter->getError(); - yScanDistance = _maxDistance + _converter->getError(); - } else if (type == "$centerSphere") { - // Same, but compute maxDistance using spherical transform - uassert(16786, "Spherical MaxDistance > PI. Are you sure you are using radians?", - _maxDistance < M_PI); - checkEarthBounds(_startPt); - - _type = GEO_SPHERE; - // should this be sphere error? - yScanDistance = rad2deg(_maxDistance) + _converter->getError(); - xScanDistance = computeXScanDistance(_startPt.y, yScanDistance); - - uassert(16787, "Spherical distance would require (unimplemented) wrapping", - (_startPt.x + xScanDistance < 180) && - (_startPt.x - xScanDistance > -180) && - (_startPt.y + yScanDistance < 90) && - (_startPt.y - yScanDistance > -90)); - } else { - uassert(16788, "invalid $center query type: " + type, false); - } - - // 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); - - GEODEBUG("Bounding box for circle query : " << _bBox.toString() - << " (max distance : " << _maxDistance << ")" - << " starting from " << _startPt.toString()); - ok(); - } - - 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) { - // 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; - } - - virtual bool 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; - } - - 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(TwoDAccessMethod* accessMethod, const BSONObj& box, BSONObj filter = BSONObj(), - bool uniqueDocs = true) - : GeoBrowse(accessMethod, "box", filter, uniqueDocs) { - - _converter = accessMethod->getParams().geoHashConverter; - - uassert(16789, "$box needs 2 fields (bottomLeft,topRight)", box.nFields() == 2); - - // Initialize an *exact* box from the given obj. - BSONObjIterator i(box); - _want._min = Point(i.next()); - _want._max = Point(i.next()); - - _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); - - uassert(16790, "need an area > 0 ", _want.area() > 0); - - 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 fixBox(Box& box) { - if(box._min.x > box._max.x) - swap(box._min.x, box._max.x); - if(box._min.y > box._max.y) - 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; - } - - void swap(double& a, double& b) { - double swap = a; - a = b; - b = swap; - } - - 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(TwoDAccessMethod* accessMethod, const BSONObj& polyPoints, - BSONObj filter = BSONObj(), bool uniqueDocs = true) - : GeoBrowse(accessMethod, "polygon", filter, uniqueDocs) { - - BSONObjIterator i(polyPoints); - BSONElement first = i.next(); - _poly.add(Point(first)); - - while (i.more()) { - _poly.add(Point(i.next())); - } - - uassert(16791, "polygon must be defined by three points or more", _poly.size() >= 3); - _converter = accessMethod->getParams().geoHashConverter; - - _bounds = _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(); - } - - // 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; - }; - - bool TwoDGeoNearRunner::run2DGeoNear(IndexCatalog* catalog, - IndexDescriptor* descriptor, const BSONObj& cmdObj, - const GeoNearArguments &parsedArgs, string& errmsg, - BSONObjBuilder& result, - unordered_map<string, double>* stats) { - - TwoDAccessMethod* sam = static_cast<TwoDAccessMethod*>( catalog->getIndex( descriptor ) ); - const TwoDIndexingParams& params = sam->getParams(); - - uassert(13046, "'near' param missing/invalid", !cmdObj["near"].eoo()); - const Point n(cmdObj["near"]); - result.append("near", params.geoHashConverter->hash(cmdObj["near"]).toString()); - - uassert(16903, "'minDistance' param not supported for 2d index, requires 2dsphere index", - cmdObj["minDistance"].eoo()); - - double maxDistance = numeric_limits<double>::max(); - BSONElement eMaxDistance = cmdObj["maxDistance"]; - - if (!eMaxDistance.eoo()) { - uassert(17085, "maxDistance must be a number", eMaxDistance.isNumber()); - maxDistance = cmdObj["maxDistance"].number(); - uassert(17086, "maxDistance must be non-negative", maxDistance >= 0); - } - - GeoDistType type = parsedArgs.isSpherical ? GEO_SPHERE : GEO_PLANE; - - GeoSearch gs(sam, n, parsedArgs.numWanted, parsedArgs.query, maxDistance, type, - parsedArgs.uniqueDocs, true); - - if (cmdObj["start"].type() == String) { - GeoHash start ((string) cmdObj["start"].valuestr()); - gs._start = start; - } - - gs.exec(); - - double totalDistance = 0; - - BSONObjBuilder arr(result.subarrayStart("results")); - int x = 0; - for (GeoHopper::Holder::iterator i=gs._points.begin(); i!=gs._points.end(); i++) { - - const GeoPoint& p = *i; - double dis = parsedArgs.distanceMultiplier * p.distance(); - totalDistance += dis; - - BSONObjBuilder bb(arr.subobjStart(BSONObjBuilder::numStr(x++))); - bb.append("dis", dis); - if (parsedArgs.includeLocs) { - if(p._pt.couldBeArray()) bb.append("loc", BSONArray(p._pt)); - else bb.append("loc", p._pt); - } - bb.append("obj", p._o); - bb.done(); - - if (arr.len() > BSONObjMaxUserSize) { - warning() << "Too many results to fit in single document. Truncating..." << endl; - break; - } - } - arr.done(); - - (*stats)["btreelocs"] = gs._nscanned; - (*stats)["nscanned"] = gs._lookedAt; - (*stats)["objectsLoaded"] = gs._objectsLoaded; - (*stats)["avgDistance"] = totalDistance / x; - (*stats)["maxDistance"] = gs.farthest(); - - return true; - } - - } // namespace twod_internal - - // - // IndexCursor below. - // - - TwoDIndexCursor::TwoDIndexCursor(TwoDAccessMethod* accessMethod) - : _accessMethod(accessMethod), _numWanted(100) { } - - Status TwoDIndexCursor::setOptions(const CursorOptions& options) { - _numWanted = options.numWanted; - - if (_numWanted < 0) { - _numWanted = _numWanted * -1; - } else if (0 == _numWanted) { - _numWanted = 100; - } - - return Status::OK(); - } - - Status TwoDIndexCursor::seek(const BSONObj& position) { - // false means we want to filter OUT geoFieldsToNuke, not filter to include only that. - BSONObj filteredQuery = position.filterFieldsUndotted( - BSON(_accessMethod->getParams().geo << ""), false); - - BSONObjIterator i(position); - while (i.more()) { - BSONElement e = i.next(); - - if (_accessMethod->getParams().geo != e.fieldName()) - continue; - - if (e.type() == Array) { - // If we get an array query, assume it is a location, and do a $within { $center : - // [[x, y], 0] } search - BSONObj circle = BSON("0" << e.embeddedObjectUserCheck() << "1" << 0); - _underlyingCursor.reset(new twod_internal::GeoCircleBrowse(_accessMethod, circle, filteredQuery, "$center", true)); - } else if (e.type() == Object) { - switch (e.embeddedObject().firstElement().getGtLtOp()) { - case BSONObj::opNEAR: { - BSONObj n = e.embeddedObject(); - e = n.firstElement(); - twod_internal::GeoDistType type; - if (strcmp(e.fieldName(), "$nearSphere") == 0) { - type = twod_internal::GEO_SPHERE; - } else if ( (strcmp(e.fieldName(), "$near") == 0) || (strcmp(e.fieldName(), "$geoNear") == 0) ) { - type = twod_internal::GEO_PLANE; - } else { - uassert(16792, string("invalid $near search type: ") + e.fieldName(), false); - type = twod_internal::GEO_PLANE; // prevents uninitialized warning - } - - uassert(16904, - "'$minDistance' param not supported for 2d index, requires 2dsphere index", - n["$minDistance"].eoo()); - - double maxDistance = numeric_limits<double>::max(); - if (e.isABSONObj() && e.embeddedObject().nFields() > 2) { - BSONObjIterator i(e.embeddedObject()); - i.next(); - i.next(); - BSONElement e = i.next(); - if (e.isNumber()) - maxDistance = e.numberDouble(); - } - { - BSONElement e = n["$maxDistance"]; - if (!e.eoo()) { - uassert(17087, "$maxDistance must be a number", e.isNumber()); - maxDistance = e.numberDouble(); - uassert(16989, "$maxDistance must be non-negative", maxDistance >= 0); - if (twod_internal::GEO_SPHERE == type) { - uassert(17088, "$maxDistance too large", - maxDistance <= nextafter(M_PI, DBL_MAX)); - } - } - } - - bool uniqueDocs = false; - if(! n["$uniqueDocs"].eoo()) uniqueDocs = n["$uniqueDocs"].trueValue(); - - shared_ptr<twod_internal::GeoSearch> s( - new twod_internal::GeoSearch(_accessMethod, Point(e), _numWanted, - filteredQuery, maxDistance, type, uniqueDocs)); - s->exec(); - _underlyingCursor.reset(new twod_internal::GeoSearchCursor(s)); - } break; - case BSONObj::opWITHIN: { - e = e.embeddedObject().firstElement(); - uassert(16793, "$within has to take an object or array", e.isABSONObj()); - - BSONObj context = e.embeddedObject(); - e = e.embeddedObject().firstElement(); - string type = e.fieldName(); - - bool uniqueDocs = true; - if (!context["$uniqueDocs"].eoo()) - uniqueDocs = context["$uniqueDocs"].trueValue(); - - if (startsWith(type, "$center")) { - uassert(16794, "$center has to take an object or array", e.isABSONObj()); - _underlyingCursor.reset(new twod_internal::GeoCircleBrowse(_accessMethod, e.embeddedObjectUserCheck(), - filteredQuery, type, uniqueDocs)); - } else if (type == "$box") { - uassert(16795, "$box has to take an object or array", e.isABSONObj()); - _underlyingCursor.reset(new twod_internal::GeoBoxBrowse(_accessMethod, e.embeddedObjectUserCheck(), - filteredQuery, uniqueDocs)); - } else if (startsWith(type, "$poly")) { - uassert(16796, "$polygon has to take an object or array", e.isABSONObj()); - _underlyingCursor.reset(new twod_internal::GeoPolygonBrowse(_accessMethod, e.embeddedObjectUserCheck(), - filteredQuery, uniqueDocs)); - } else { - throw UserException(16797, str::stream() << "unknown $within information : " - << context - << ", a shape must be specified."); - } - } break; - default: - // Otherwise... assume the object defines a point, and we want to do a - // zero-radius $within $center - - _underlyingCursor.reset(new twod_internal::GeoCircleBrowse(_accessMethod, - BSON("0" << e.embeddedObjectUserCheck() << "1" << 0), filteredQuery)); - break; - } - } - } - - if (NULL == _underlyingCursor.get()) { - throw UserException(16798, (string)"missing geo field (" - + _accessMethod->getParams().geo + ") in : " + position.toString()); - } - return Status::OK(); - } - - bool TwoDIndexCursor::isEOF() const { return _underlyingCursor->eof(); } - BSONObj TwoDIndexCursor::getKey() const { return _underlyingCursor->currKey(); } - DiskLoc TwoDIndexCursor::getValue() const { return _underlyingCursor->currLoc(); }; - void TwoDIndexCursor::next() { _underlyingCursor->advance(); } - string TwoDIndexCursor::toString() { return _underlyingCursor->toString(); } - Status TwoDIndexCursor::savePosition() { - _underlyingCursor->noteLocation(); - return Status::OK(); - } - Status TwoDIndexCursor::restorePosition() { - _underlyingCursor->checkLocation(); - return Status::OK(); - } - void TwoDIndexCursor::explainDetails(BSONObjBuilder* b) { - _underlyingCursor->explainDetails(*b); - } - -} // namespace mongo diff --git a/src/mongo/db/index/2d_index_cursor.h b/src/mongo/db/index/2d_index_cursor.h deleted file mode 100644 index cfef73ae187..00000000000 --- a/src/mongo/db/index/2d_index_cursor.h +++ /dev/null @@ -1,93 +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. -*/ - -#pragma once - -#include <vector> - -#include "mongo/base/status.h" -#include "mongo/db/geo/geoquery.h" -#include "mongo/db/index/2d_common.h" -#include "mongo/db/index/index_cursor.h" -#include "mongo/db/jsobj.h" -#include "mongo/db/pdfile.h" -#include "mongo/platform/unordered_map.h" - -namespace mongo { - - class TwoDAccessMethod; - class GeoNearArguments; - class IndexDescriptor; - - namespace twod_internal { - class GeoCursorBase; - - class TwoDGeoNearRunner { - public: - static bool run2DGeoNear(IndexCatalog* catalog, - IndexDescriptor* descriptor, const BSONObj& cmdObj, - const GeoNearArguments &parsedArgs, string& errmsg, - BSONObjBuilder& result, unordered_map<string, double>* stats); - }; - } - - class TwoDIndexCursor : public IndexCursor { - public: - TwoDIndexCursor(TwoDAccessMethod* accessMethod); - - /** - * Parse the query, figure out if it's a near or a non-near predicate, and create the - * appropriate sub-cursor. - */ - virtual Status seek(const BSONObj& position); - - /** - * We pay attention to the numWanted option. - */ - virtual Status setOptions(const CursorOptions& options); - - // Implemented: - virtual bool isEOF() const; - virtual BSONObj getKey() const; - virtual DiskLoc getValue() const; - virtual void next(); - - virtual string toString(); - - virtual Status savePosition(); - virtual Status restorePosition(); - - virtual void explainDetails(BSONObjBuilder* b); - - private: - TwoDAccessMethod* _accessMethod; - int _numWanted; - - scoped_ptr<twod_internal::GeoCursorBase> _underlyingCursor; - }; -} // namespace mongo diff --git a/src/mongo/db/index/s2_access_method.cpp b/src/mongo/db/index/s2_access_method.cpp index 64cfd4cef55..1a638c5f792 100644 --- a/src/mongo/db/index/s2_access_method.cpp +++ b/src/mongo/db/index/s2_access_method.cpp @@ -35,7 +35,6 @@ #include "mongo/db/geo/geoconstants.h" #include "mongo/db/geo/s2common.h" #include "mongo/db/index_names.h" -#include "mongo/db/index/s2_index_cursor.h" #include "mongo/db/jsobj.h" namespace mongo { @@ -85,8 +84,7 @@ namespace mongo { } Status S2AccessMethod::newCursor(IndexCursor** out) { - *out = new S2IndexCursor(_params, _descriptor); - return Status::OK(); + return Status(ErrorCodes::IllegalOperation, "Unimplemented seek called on S2"); } void S2AccessMethod::getKeys(const BSONObj& obj, BSONObjSet* keys) { diff --git a/src/mongo/db/index/s2_index_cursor.cpp b/src/mongo/db/index/s2_index_cursor.cpp deleted file mode 100644 index ca6496ad163..00000000000 --- a/src/mongo/db/index/s2_index_cursor.cpp +++ /dev/null @@ -1,145 +0,0 @@ -// DEPRECATED -/** -* 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/index/s2_index_cursor.h" - -#include "mongo/db/btreecursor.h" -#include "mongo/db/index_names.h" -#include "mongo/db/index/index_cursor.h" -#include "mongo/db/index/index_descriptor.h" -#include "mongo/db/index/s2_near_cursor.h" -#include "mongo/db/index/s2_simple_cursor.h" -#include "mongo/db/pdfile.h" -#include "mongo/db/queryutil.h" -#include "third_party/s2/s2regionintersection.h" - -namespace mongo { - - S2IndexCursor::S2IndexCursor(const S2IndexingParams& params, IndexDescriptor* descriptor) - : _params(params), _descriptor(descriptor) { } - - Status S2IndexCursor::seek(const BSONObj &position) { - vector<GeoQuery> regions; - bool isNearQuery = false; - NearQuery nearQuery; - - // Go through the fields that we index, and for each geo one, make - // a GeoQuery object for the S2*Cursor class to do intersection - // testing/cover generating with. - BSONObjIterator keyIt(_descriptor->keyPattern()); - while (keyIt.more()) { - BSONElement keyElt = keyIt.next(); - - if (keyElt.type() != String || IndexNames::GEO_2DSPHERE != keyElt.valuestr()) { - continue; - } - - BSONElement e = position.getFieldDotted(keyElt.fieldName()); - if (e.eoo()) { continue; } - if (!e.isABSONObj()) { continue; } - BSONObj obj = e.Obj(); - - if (nearQuery.parseFrom(obj)) { - if (nearQuery.centroid.crs == FLAT && !nearQuery.isNearSphere) { - return Status(ErrorCodes::BadValue, "flat near query on spherical index"); - } - if (isNearQuery) { - return Status(ErrorCodes::BadValue, "Only one $near clause allowed: " + - position.toString(), 16685); - } - isNearQuery = true; - - // FLAT implies the distances are in radians. Convert to meters. - if (FLAT == nearQuery.centroid.crs) { - nearQuery.minDistance *= _params.radius; - nearQuery.maxDistance *= _params.radius; - } - - nearQuery.field = keyElt.fieldName(); - continue; - } - - GeoQuery geoQueryField(keyElt.fieldName()); - if (!geoQueryField.parseFrom(obj)) { - return Status(ErrorCodes::BadValue, "can't parse query (2dsphere): " - + obj.toString(), 16535); - } - if (!geoQueryField.hasS2Region()) { - return Status(ErrorCodes::BadValue, "Geometry unsupported: " + obj.toString(), - 16684); - } - regions.push_back(geoQueryField); - } - - if (!isNearQuery && regions.size() == 0) { - return Status(ErrorCodes::BadValue, "None of index's fields present in seek " + position.toString()); - } - - // Remove all the indexed geo regions from the query. The s2*cursor will - // instead create a covering for that key to speed up the search. - // - // One thing to note is that we create coverings for indexed geo keys during - // a near search to speed it up further. - BSONObjBuilder geoFieldsToNuke; - - if (isNearQuery) { - geoFieldsToNuke.append(nearQuery.field, ""); - } - - for (size_t i = 0; i < regions.size(); ++i) { - geoFieldsToNuke.append(regions[i].getField(), ""); - } - - // false means we want to filter OUT geoFieldsToNuke, not filter to include only that. - BSONObj filteredQuery = position.filterFieldsUndotted(geoFieldsToNuke.obj(), false); - - if (isNearQuery) { - S2NearIndexCursor* nearCursor = new S2NearIndexCursor(_descriptor, _params); - _underlyingCursor.reset(nearCursor); - nearCursor->seek(filteredQuery, nearQuery, regions); - } else { - S2SimpleCursor* simpleCursor = new S2SimpleCursor(_descriptor, _params); - _underlyingCursor.reset(simpleCursor); - simpleCursor->seek(filteredQuery, regions); - } - - return Status::OK(); - } - - Status S2IndexCursor::setOptions(const CursorOptions& options) { return Status::OK(); } - - bool S2IndexCursor::isEOF() const { return _underlyingCursor->isEOF(); } - BSONObj S2IndexCursor::getKey() const { return _underlyingCursor->getKey(); } - DiskLoc S2IndexCursor::getValue() const { return _underlyingCursor->getValue(); } - void S2IndexCursor::next() { _underlyingCursor->next(); } - string S2IndexCursor::toString() { return _underlyingCursor->toString(); } - Status S2IndexCursor::savePosition() { return _underlyingCursor->savePosition(); } - Status S2IndexCursor::restorePosition() { return _underlyingCursor->restorePosition(); } - -} // namespace mongo diff --git a/src/mongo/db/index/s2_index_cursor.h b/src/mongo/db/index/s2_index_cursor.h deleted file mode 100644 index 2bcccdc3640..00000000000 --- a/src/mongo/db/index/s2_index_cursor.h +++ /dev/null @@ -1,80 +0,0 @@ -// DEPRECATED -/** -* 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. -*/ - -#pragma once - -#include <vector> - -#include "mongo/db/btreecursor.h" -#include "mongo/db/geo/geoquery.h" -#include "mongo/db/geo/s2common.h" -#include "mongo/db/index/index_cursor.h" -#include "mongo/db/index/index_descriptor.h" -#include "mongo/db/jsobj.h" -#include "mongo/db/pdfile.h" -#include "mongo/platform/unordered_set.h" -#include "third_party/s2/s2cap.h" -#include "third_party/s2/s2regionintersection.h" - -namespace mongo { - - /** - * This is the cursor that the caller of S2AccessMethod::newCursor actually gets. When you call - * seek on a S2IndexCursor, it creates another cursor depending on the predicate in the query. - * The behavior for $near is so different than the behavior for the other geo predicates that - * it's best to separate the cursors. - */ - class S2IndexCursor : public IndexCursor { - public: - S2IndexCursor(const S2IndexingParams& params, IndexDescriptor* descriptor); - virtual ~S2IndexCursor() { } - - // Parse the query, figure out if it's a near or a non-near predicate, and create the - // appropriate sub-cursor. - virtual Status seek(const BSONObj& position); - - virtual Status setOptions(const CursorOptions& options); - - // Implemented: - virtual bool isEOF() const; - virtual BSONObj getKey() const; - virtual DiskLoc getValue() const; - virtual void next(); - - virtual string toString(); - - virtual Status savePosition(); - virtual Status restorePosition(); - - private: - S2IndexingParams _params; - IndexDescriptor *_descriptor; - scoped_ptr<IndexCursor> _underlyingCursor; - }; -} // namespace mongo diff --git a/src/mongo/db/index/s2_near_cursor.cpp b/src/mongo/db/index/s2_near_cursor.cpp deleted file mode 100644 index 5512ba7a790..00000000000 --- a/src/mongo/db/index/s2_near_cursor.cpp +++ /dev/null @@ -1,368 +0,0 @@ -// DEPRECATED -/** -* 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/index/s2_near_cursor.h" - -#include "mongo/db/btreecursor.h" -#include "mongo/db/index/index_cursor.h" -#include "mongo/db/index/index_descriptor.h" -#include "mongo/db/pdfile.h" -#include "mongo/db/queryutil.h" -#include "third_party/s2/s2regionintersection.h" - -namespace mongo { - - S2NearIndexCursor::S2NearIndexCursor(IndexDescriptor* descriptor, - const S2IndexingParams& params) - : _descriptor(descriptor), _params(params) { } - - void S2NearIndexCursor::seek(const BSONObj& query, const NearQuery& nearQuery, - const vector<GeoQuery>& regions) { - _indexedGeoFields = regions; - _nearQuery = nearQuery; - _returnedDistance = 0; - _nearFieldIndex = 0; - _stats = Stats(); - _returned = unordered_set<DiskLoc, DiskLoc::Hasher>(); - _results = priority_queue<Result>(); - - BSONObjBuilder geoFieldsToNuke; - for (size_t i = 0; i < _indexedGeoFields.size(); ++i) { - geoFieldsToNuke.append(_indexedGeoFields[i].getField(), ""); - } - // false means we want to filter OUT geoFieldsToNuke, not filter to include only that. - _filteredQuery = query.filterFieldsUndotted(geoFieldsToNuke.obj(), false); - - // More indexing machinery. - BSONObjBuilder specBuilder; - BSONObjIterator specIt(_descriptor->keyPattern()); - while (specIt.more()) { - BSONElement e = specIt.next(); - // Checked in AccessMethod already, so we know this spec has only numbers and 2dsphere - if ( e.type() == String ) { - specBuilder.append( e.fieldName(), 1 ); - } - else { - specBuilder.append( e.fieldName(), e.numberInt() ); - } - } - _specForFRV = specBuilder.obj(); - - specIt = BSONObjIterator(_descriptor->keyPattern()); - while (specIt.more()) { - if (specIt.next().fieldName() == _nearQuery.field) { break; } - ++_nearFieldIndex; - } - - _minDistance = max(0.0, _nearQuery.minDistance); - - // _outerRadius can't be greater than (pi * r) or we wrap around the opposite - // side of the world. - _maxDistance = min(M_PI * _params.radius, _nearQuery.maxDistance); - uassert(16892, "$minDistance too large", _minDistance < _maxDistance); - - // Start with a conservative _radiusIncrement. - _radiusIncrement = 5 * S2::kAvgEdge.GetValue(_params.finestIndexedLevel) * _params.radius; - _innerRadius = _outerRadius = _minDistance; - // We might want to adjust the sizes of our coverings if our search - // isn't local to the start point. - // Set up _outerRadius with proper checks (maybe maxDistance is really small?) - nextAnnulus(); - fillResults(); - } - - S2NearIndexCursor::~S2NearIndexCursor() { _annulus.Release(NULL); } - - Status S2NearIndexCursor::seek(const BSONObj& position) { - return Status::OK(); - } - - Status S2NearIndexCursor::setOptions(const CursorOptions& options) { - return Status::OK(); - } - - bool S2NearIndexCursor::isEOF() const { - if (_innerRadius > _maxDistance) { - return true; - } - - return _results.empty(); - } - - BSONObj S2NearIndexCursor::getKey() const { return _results.top().key; } - DiskLoc S2NearIndexCursor::getValue() const { return _results.top().loc; } - string S2NearIndexCursor::toString() { return "S2NearCursor"; } - - void S2NearIndexCursor::next() { - if (_innerRadius > _maxDistance) { - LOG(2) << "advancing but exhausted search distance" << endl; - } - - if (!_results.empty()) { - _returnedDistance = _results.top().distance; - _returned.insert(_results.top().loc); - _results.pop(); - ++_stats._numReturned; - // Safe to grow the radius as we've returned everything in our shell. We don't do this - // check outside of !_results.empty() because we could have results, yield, dump them - // (_results would be empty), then need to recreate them w/the same radii. In that case - // we'd grow when we shouldn't. - if (_results.empty()) { nextAnnulus(); } - } - - if (_results.empty()) { fillResults(); } - } - - Status S2NearIndexCursor::savePosition() { - _results = priority_queue<Result>(); - return Status::OK(); - } - - Status S2NearIndexCursor::restorePosition() { - if (_results.empty()) { - fillResults(); - } - return Status::OK(); - } - - // Make the object that describes all keys that are within our current search annulus. - BSONObj S2NearIndexCursor::makeFRSObject() { - BSONObjBuilder frsObjBuilder; - frsObjBuilder.appendElements(_filteredQuery); - - S2RegionCoverer coverer; - // Step 1: Make the BSON'd covering for our search annulus. - BSONObj inExpr; - // Caps are inclusive and inverting a cap includes the border. This means that our - // initial _innerRadius of 0 is OK -- we'll still find a point that is exactly at - // the start of our search. - _innerCap = S2Cap::FromAxisAngle(_nearQuery.centroid.point, - S1Angle::Radians(_innerRadius / _params.radius)); - _outerCap = S2Cap::FromAxisAngle(_nearQuery.centroid.point, - S1Angle::Radians(_outerRadius / _params.radius)); - double area = _outerCap.area() - _innerCap.area(); - _innerCap = _innerCap.Complement(); - vector<S2Region*> regions; - regions.push_back(&_innerCap); - regions.push_back(&_outerCap); - _annulus.Release(NULL); - _annulus.Init(®ions); - vector<S2CellId> cover; - S2SearchUtil::setCoverLimitsBasedOnArea(area, &coverer, _params.coarsestIndexedLevel); - coverer.GetCovering(_annulus, &cover); - LOG(2) << "annulus cover size is " << cover.size() - << ", params (" << coverer.min_level() << ", " << coverer.max_level() << ")" - << endl; - inExpr = S2SearchUtil::coverAsBSON(cover, _nearQuery.field, - _params.coarsestIndexedLevel); - frsObjBuilder.appendElements(inExpr); - - _params.configureCoverer(&coverer); - // Cover the indexed geo components of the query. - for (size_t i = 0; i < _indexedGeoFields.size(); ++i) { - vector<S2CellId> cover; - coverer.GetCovering(_indexedGeoFields[i].getRegion(), &cover); - uassert(16761, "Couldn't generate index keys for geo field " - + _indexedGeoFields[i].getField(), - cover.size() > 0); - BSONObj fieldRange = S2SearchUtil::coverAsBSON(cover, _indexedGeoFields[i].getField(), - _params.coarsestIndexedLevel); - frsObjBuilder.appendElements(fieldRange); - } - - return frsObjBuilder.obj(); - } - - // Fill _results with all of the results in the annulus defined by _innerRadius and - // _outerRadius. If no results are found, grow the annulus and repeat until success (or - // until the edge of the world). - void S2NearIndexCursor::fillResults() { - verify(_results.empty()); - if (_innerRadius >= _outerRadius) { return; } - if (_innerRadius > _maxDistance) { return; } - - // We iterate until 1. our search radius is too big or 2. we find results. - do { - // Some of these arguments are opaque, look at the definitions of the involved classes. - FieldRangeSet frs(_descriptor->parentNS().c_str(), makeFRSObject(), false, false); - shared_ptr<FieldRangeVector> frv(new FieldRangeVector(frs, _specForFRV, 1)); - scoped_ptr<BtreeCursor> cursor(BtreeCursor::make(nsdetails(_descriptor->parentNS()), - _descriptor->getOnDisk(), frv, 0, 1)); - - // The cursor may return the same obj more than once for a given - // FRS, so we make sure to only consider it once in any given annulus. - // - // We don't want this outside of the 'do' loop because the covering - // for an annulus may return an object whose distance to the query - // point is actually contained in a subsequent annulus. If we - // didn't consider every object in a given annulus we might miss - // the point. - // - // We don't use a global 'seen' because we get that by requiring - // the distance from the query point to the indexed geo to be - // within our 'current' annulus, and I want to dodge all yield - // issues if possible. - unordered_set<DiskLoc, DiskLoc::Hasher> seen; - - LOG(1) << "looking at annulus from " << _innerRadius << " to " << _outerRadius << endl; - LOG(1) << "Total # returned: " << _stats._numReturned << endl; - // Do the actual search through this annulus. - for (; cursor->ok(); cursor->advance()) { - // Don't bother to look at anything we've returned. - if (_returned.end() != _returned.find(cursor->currLoc())) { - ++_stats._returnSkip; - continue; - } - - ++_stats._nscanned; - if (seen.end() != seen.find(cursor->currLoc())) { - ++_stats._btreeDups; - continue; - } - - // Get distance interval from our query point to the cell. - // If it doesn't overlap with our current shell, toss. - BSONObj currKey(cursor->currKey()); - BSONObjIterator it(currKey); - BSONElement geoKey; - for (int i = 0; i <= _nearFieldIndex; ++i) { - geoKey = it.next(); - } - - S2Cell keyCell = S2Cell(S2CellId::FromString(geoKey.String())); - if (!_annulus.MayIntersect(keyCell)) { - ++_stats._keyGeoSkip; - continue; - } - - // We have to add this document to seen *AFTER* the key intersection test. - // A geometry may have several keys, one of which may be in our search shell and one - // of which may be outside of it. We don't want to ignore a document just because - // one of its covers isn't inside this annulus. - seen.insert(cursor->currLoc()); - - // At this point forward, we will not examine the document again in this annulus. - - const BSONObj& indexedObj = cursor->currLoc().obj(); - - // Match against indexed geo fields. - ++_stats._geoMatchTested; - size_t geoFieldsMatched = 0; - // See if the object actually overlaps w/the geo query fields. - for (size_t i = 0; i < _indexedGeoFields.size(); ++i) { - BSONElementSet geoFieldElements; - indexedObj.getFieldsDotted(_indexedGeoFields[i].getField(), geoFieldElements, - false); - if (geoFieldElements.empty()) { continue; } - - bool match = false; - - for (BSONElementSet::iterator oi = geoFieldElements.begin(); - !match && (oi != geoFieldElements.end()); ++oi) { - if (!oi->isABSONObj()) { continue; } - const BSONObj &geoObj = oi->Obj(); - GeometryContainer geoContainer; - uassert(16762, "ill-formed geometry: " + geoObj.toString(), - geoContainer.parseFrom(geoObj)); - match = _indexedGeoFields[i].satisfiesPredicate(geoContainer); - } - - if (match) { ++geoFieldsMatched; } - } - - if (geoFieldsMatched != _indexedGeoFields.size()) { - continue; - } - - // Get all the fields with that name from the document. - BSONElementSet geoFieldElements; - indexedObj.getFieldsDotted(_nearQuery.field, geoFieldElements, false); - if (geoFieldElements.empty()) { continue; } - - ++_stats._inAnnulusTested; - double minDistance = 1e20; - // Look at each field in the document and take the min. distance. - for (BSONElementSet::iterator oi = geoFieldElements.begin(); - oi != geoFieldElements.end(); ++oi) { - if (!oi->isABSONObj()) { continue; } - BSONObj obj = oi->Obj(); - double dist; - bool ret = S2SearchUtil::distanceBetween(_nearQuery.centroid.point, - obj, &dist); - if (!ret) { - warning() << "unknown geometry: " << obj.toString(); - dist = numeric_limits<double>::max(); - } - - minDistance = min(dist, minDistance); - } - - // We could be in an annulus, yield, add new points closer to - // query point than the last point we returned, then unyield. - // This would return points out of order. - if (minDistance < _returnedDistance) { continue; } - - // If the min. distance satisfies our distance criteria - if (minDistance >= _innerRadius && minDistance <= _outerRadius) { - // The result is valid. We have to de-dup ourselves here. - if (_returned.end() == _returned.find(cursor->currLoc())) { - _results.push(Result(cursor->currLoc(), cursor->currKey(), - minDistance)); - } - } - } - - if (_results.empty()) { - LOG(1) << "results empty!\n"; - _radiusIncrement *= 2; - nextAnnulus(); - } else if (_results.size() < 300) { - _radiusIncrement *= 2; - } else if (_results.size() > 600) { - _radiusIncrement /= 2; - } - } while (_results.empty() - && _innerRadius < _maxDistance - && _innerRadius < _outerRadius); - LOG(1) << "Filled shell with " << _results.size() << " results" << endl; - } - - // Grow _innerRadius and _outerRadius by _radiusIncrement, capping _outerRadius at halfway - // around the world (pi * _params.radius). - void S2NearIndexCursor::nextAnnulus() { - LOG(1) << "growing annulus from (" << _innerRadius << ", " << _outerRadius; - _innerRadius = _outerRadius; - _outerRadius += _radiusIncrement; - _outerRadius = min(_outerRadius, _maxDistance); - verify(_innerRadius <= _outerRadius); - LOG(1) << ") to (" << _innerRadius << ", " << _outerRadius << ")" << endl; - ++_stats._numShells; - } - -} // namespace mongo diff --git a/src/mongo/db/index/s2_near_cursor.h b/src/mongo/db/index/s2_near_cursor.h deleted file mode 100644 index e6534237c2f..00000000000 --- a/src/mongo/db/index/s2_near_cursor.h +++ /dev/null @@ -1,188 +0,0 @@ -// DEPRECATED -/** -* 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. -*/ - -#pragma once - -#include <queue> - -#include "mongo/db/btreecursor.h" -#include "mongo/db/geo/geoquery.h" -#include "mongo/db/geo/s2common.h" -#include "mongo/db/index/index_cursor.h" -#include "mongo/db/index/index_descriptor.h" -#include "mongo/db/jsobj.h" -#include "mongo/db/pdfile.h" -#include "mongo/platform/unordered_set.h" -#include "third_party/s2/s2cap.h" -#include "third_party/s2/s2regionintersection.h" - -namespace mongo { - - class S2NearIndexCursor : public IndexCursor { - public: - S2NearIndexCursor(IndexDescriptor* descriptor, const S2IndexingParams& params); - - virtual ~S2NearIndexCursor(); - - // Not implemented. - virtual Status seek(const BSONObj &position); - Status setOptions(const CursorOptions& options); - - // Implemented: - // This is our very specific seek function. Not part of IndexCursor. - void seek(const BSONObj& query, const NearQuery& nearQuery, - const vector<GeoQuery>& regions); - virtual bool isEOF() const; - virtual BSONObj getKey() const; - virtual DiskLoc getValue() const; - virtual void next(); - virtual string toString(); - virtual Status savePosition(); - virtual Status restorePosition(); - - // The geoNear command wants these. - long long nscanned() { return _stats._nscanned; } - double currentDistance() { return _results.top().distance; } - - private: - // We use this to cache results of the search. Results are sorted to have decreasing - // distance, and callers are interested in loc and key. - struct Result { - Result(const DiskLoc& dl, const BSONObj& ck, double dist) : loc(dl), key(ck), - distance(dist) { } - bool operator<(const Result& other) const { - // We want increasing distance, not decreasing, so we reverse the <. - return distance > other.distance; - } - - DiskLoc loc; - BSONObj key; - double distance; - }; - - /** - * Make the object that describes all keys that are within our current search annulus. - */ - BSONObj makeFRSObject(); - - /** - * Fill _results with all of the results in the annulus defined by _innerRadius and - * _outerRadius. If no results are found, grow the annulus and repeat until success (or - * until the edge of the world). - */ - void fillResults(); - - /** - * Grow _innerRadius and _outerRadius by _radiusIncrement, capping _outerRadius at halfway - * around the world (pi * _params.radius). - */ - void nextAnnulus(); - - double distanceTo(const BSONObj &obj); - - IndexDescriptor* _descriptor; - - // How we need/use the query: - // Matcher: Can have geo fields in it, but only with $within. - // This only really happens (right now) from geoNear command. - // We assume the caller takes care of this in the right way. - // FRS: No geo fields allowed! - // So, on that note: the query with the geo stuff taken out, used by makeFRSObject(). - BSONObj _filteredQuery; - - // The GeoQuery for the point we're doing near searching from. - NearQuery _nearQuery; - - // What geo regions are we looking for? - vector<GeoQuery> _indexedGeoFields; - - // How were the keys created? We need this to search for the right stuff. - S2IndexingParams _params; - - // We also pass this to the FieldRangeVector ctor. - BSONObj _specForFRV; - - // Geo-related variables. - // At what min distance (arc length) do we start looking for results? - double _minDistance; - // What's the max distance (arc length) we're willing to look for results? - double _maxDistance; - - // We compute an annulus of results and cache it here. - priority_queue<Result> _results; - - // These radii define the annulus we're currently looking at. - double _innerRadius; - double _outerRadius; - - // When we search the next annulus, what to adjust our radius by? Grows when we search an - // annulus and find no results. - - double _radiusIncrement; - - // What have we returned already? - unordered_set<DiskLoc, DiskLoc::Hasher> _returned; - - struct Stats { - Stats() : _nscanned(0), _matchTested(0), _geoMatchTested(0), _numShells(0), - _keyGeoSkip(0), _returnSkip(0), _btreeDups(0), _inAnnulusTested(0), - _numReturned(0) {} - // Stat counters/debug information goes below. - // How many items did we look at in the btree? - long long _nscanned; - // How many did we try to match? - long long _matchTested; - // How many did we geo-test? - long long _geoMatchTested; - // How many search shells did we use? - long long _numShells; - // How many did we skip due to key-geo check? - long long _keyGeoSkip; - long long _returnSkip; - long long _btreeDups; - long long _inAnnulusTested; - long long _numReturned; - }; - - Stats _stats; - - // The S2 machinery that represents the search annulus - S2Cap _innerCap; - S2Cap _outerCap; - S2RegionIntersection _annulus; - - // This is the "array index" of the key field that is the near field. We use this to do - // cheap is-this-doc-in-the-annulus testing. - int _nearFieldIndex; - - // The max distance we've returned so far. - double _returnedDistance; - }; - -} // namespace mongo diff --git a/src/mongo/db/index/s2_simple_cursor.cpp b/src/mongo/db/index/s2_simple_cursor.cpp deleted file mode 100644 index fff4e216188..00000000000 --- a/src/mongo/db/index/s2_simple_cursor.cpp +++ /dev/null @@ -1,172 +0,0 @@ -// DEPRECATED -/** -* 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/index/s2_simple_cursor.h" - -#include "mongo/db/btreecursor.h" -#include "mongo/db/index/index_cursor.h" -#include "mongo/db/index/index_descriptor.h" -#include "mongo/db/pdfile.h" -#include "mongo/db/queryutil.h" -#include "third_party/s2/s2regionintersection.h" - -namespace mongo { - - S2SimpleCursor::S2SimpleCursor(IndexDescriptor* descriptor, const S2IndexingParams& params) - : _descriptor(descriptor), _params(params) { } - - void S2SimpleCursor::seek(const BSONObj& query, const vector<GeoQuery>& regions) { - _nscanned = 0; - _matchTested = 0; - _geoTested = 0; - _fields = regions; - _seen = unordered_set<DiskLoc, DiskLoc::Hasher>(); - - BSONObjBuilder geoFieldsToNuke; - for (size_t i = 0; i < _fields.size(); ++i) { - geoFieldsToNuke.append(_fields[i].getField(), ""); - } - // false means we want to filter OUT geoFieldsToNuke, not filter to include only that. - _filteredQuery = query.filterFieldsUndotted(geoFieldsToNuke.obj(), false); - - BSONObjBuilder specBuilder; - BSONObjIterator i(_descriptor->keyPattern()); - while (i.more()) { - BSONElement e = i.next(); - // Checked in AccessMethod already, so we know this spec has only numbers and 2dsphere - if ( e.type() == String ) { - specBuilder.append( e.fieldName(), 1 ); - } - else { - specBuilder.append( e.fieldName(), e.numberInt() ); - } - } - BSONObj spec = specBuilder.obj(); - - BSONObj frsObj; - - BSONObjBuilder frsObjBuilder; - frsObjBuilder.appendElements(_filteredQuery); - - S2RegionCoverer coverer; - - for (size_t i = 0; i < _fields.size(); ++i) { - vector<S2CellId> cover; - double area = _fields[i].getRegion().GetRectBound().Area(); - S2SearchUtil::setCoverLimitsBasedOnArea(area, &coverer, _params.coarsestIndexedLevel); - coverer.GetCovering(_fields[i].getRegion(), &cover); - uassert(16759, "No cover ARGH?!", cover.size() > 0); - _cellsInCover = cover.size(); - BSONObj fieldRange = S2SearchUtil::coverAsBSON(cover, _fields[i].getField(), - _params.coarsestIndexedLevel); - frsObjBuilder.appendElements(fieldRange); - } - - frsObj = frsObjBuilder.obj(); - - FieldRangeSet frs(_descriptor->parentNS().c_str(), frsObj, false, false); - shared_ptr<FieldRangeVector> frv(new FieldRangeVector(frs, spec, 1)); - _btreeCursor.reset(BtreeCursor::make(nsdetails(_descriptor->parentNS()), - _descriptor->getOnDisk(), frv, 0, 1)); - next(); - } - - Status S2SimpleCursor::seek(const BSONObj& position) { - return Status::OK(); - } - - Status S2SimpleCursor::setOptions(const CursorOptions& options) { - return Status::OK(); - } - - bool S2SimpleCursor::isEOF() const { return !_btreeCursor->ok(); } - BSONObj S2SimpleCursor::getKey() const { return _btreeCursor->currKey(); } - DiskLoc S2SimpleCursor::getValue() const { return _btreeCursor->currLoc(); } - - void S2SimpleCursor::next() { - for (; _btreeCursor->ok(); _btreeCursor->advance()) { - ++_nscanned; - if (_seen.end() != _seen.find(_btreeCursor->currLoc())) { continue; } - _seen.insert(_btreeCursor->currLoc()); - - const BSONObj &indexedObj = _btreeCursor->currLoc().obj(); - - ++_geoTested; - size_t geoFieldsMatched = 0; - // OK, cool, non-geo match satisfied. See if the object actually overlaps w/the geo - // query fields. - for (size_t i = 0; i < _fields.size(); ++i) { - BSONElementSet geoFieldElements; - indexedObj.getFieldsDotted(_fields[i].getField(), geoFieldElements, false); - if (geoFieldElements.empty()) { continue; } - - bool match = false; - - for (BSONElementSet::iterator oi = geoFieldElements.begin(); - !match && (oi != geoFieldElements.end()); ++oi) { - if (!oi->isABSONObj()) { continue; } - const BSONObj &geoObj = oi->Obj(); - GeometryContainer geoContainer; - uassert(16760, "malformed geometry: " + geoObj.toString(), - geoContainer.parseFrom(geoObj)); - match = _fields[i].satisfiesPredicate(geoContainer); - } - - if (match) { ++geoFieldsMatched; } - } - - if (geoFieldsMatched == _fields.size()) { - // We have a winner! And we point at it. - return; - } - } - } - - string S2SimpleCursor::toString() { return "S2Cursor: " + _btreeCursor->toString(); } - - Status S2SimpleCursor::savePosition() { - _btreeCursor->noteLocation(); - _seen.clear(); - return Status::OK(); - } - - Status S2SimpleCursor::restorePosition() { - _btreeCursor->checkLocation(); - // We are pointing at a valid btree location now, but it may not be a valid result. - // This ensures that we're pointing at a valid result that satisfies the query. - - // There is something subtle here: Say we point at something valid, and note the location - // (yield), then checkLocation (unyield), when we call advance, we don't go past the object - // that we were/are pointing at since we only do that if we've seen it before (that is, it's - // in _seen, which we clear when we yield). - next(); - return Status::OK(); - } - -} // namespace mongo diff --git a/src/mongo/db/index/s2_simple_cursor.h b/src/mongo/db/index/s2_simple_cursor.h deleted file mode 100644 index cb7d570cd8f..00000000000 --- a/src/mongo/db/index/s2_simple_cursor.h +++ /dev/null @@ -1,103 +0,0 @@ -// DEPRECATED -/** -* 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. -*/ - -#pragma once - -#include <vector> - -#include "mongo/db/btreecursor.h" -#include "mongo/db/geo/geoquery.h" -#include "mongo/db/geo/s2common.h" -#include "mongo/db/index/index_cursor.h" -#include "mongo/db/index/index_descriptor.h" -#include "mongo/db/jsobj.h" -#include "mongo/db/pdfile.h" -#include "mongo/platform/unordered_set.h" -#include "third_party/s2/s2cap.h" -#include "third_party/s2/s2regionintersection.h" - -namespace mongo { - - class S2SimpleCursor : public IndexCursor { - public: - S2SimpleCursor(IndexDescriptor* descriptor, const S2IndexingParams& params); - - virtual ~S2SimpleCursor() { } - - // Not implemented - virtual Status seek(const BSONObj& position); - Status setOptions(const CursorOptions& options); - - // Implemented: - // Not part of the IndexCursor spec. - void seek(const BSONObj& query, const vector<GeoQuery>& regions); - - bool isEOF() const; - BSONObj getKey() const; - DiskLoc getValue() const; - void next(); - - virtual string toString(); - - virtual Status savePosition(); - virtual Status restorePosition(); - - private: - IndexDescriptor* _descriptor; - - // The query with the geo stuff taken out. We use this with a matcher. - BSONObj _filteredQuery; - - // What geo regions are we looking for? - vector<GeoQuery> _fields; - - // How were the keys created? We need this to search for the right stuff. - S2IndexingParams _params; - - // What have we checked so we don't repeat it and waste time? - unordered_set<DiskLoc, DiskLoc::Hasher> _seen; - - // This really does all the work/points into the btree. - scoped_ptr<BtreeCursor> _btreeCursor; - - // Stat counters/debug information goes below: - // How many items did we look at in the btree? - long long _nscanned; - - // How many did we try to match? - long long _matchTested; - - // How many did we geo-test? - long long _geoTested; - - // How many cells were in our cover? - long long _cellsInCover; - }; - -} // namespace mongo diff --git a/src/mongo/db/matcher/expression_geo.h b/src/mongo/db/matcher/expression_geo.h index c6044cf6f08..d67edc91919 100644 --- a/src/mongo/db/matcher/expression_geo.h +++ b/src/mongo/db/matcher/expression_geo.h @@ -31,7 +31,6 @@ #pragma once -#include "mongo/db/geo/geonear.h" #include "mongo/db/geo/geoquery.h" #include "mongo/db/matcher/expression.h" #include "mongo/db/matcher/expression_leaf.h" diff --git a/src/mongo/db/query/explain_plan.cpp b/src/mongo/db/query/explain_plan.cpp index e34ccd50388..0899b13d031 100644 --- a/src/mongo/db/query/explain_plan.cpp +++ b/src/mongo/db/query/explain_plan.cpp @@ -159,11 +159,11 @@ namespace mongo { res->setIndexOnly(false); } else if (leaf->stageType == STAGE_GEO_NEAR_2D) { - // TODO: This is kind of a lie. + TwoDNearStats* nStats = static_cast<TwoDNearStats*>(leaf->specific.get()); res->setCursor("GeoSearchCursor"); // The first work() is an init. Every subsequent work examines a document. - res->setNScanned(leaf->common.works); - res->setNScannedObjects(leaf->common.works); + res->setNScanned(nStats->nscanned); + res->setNScannedObjects(nStats->objectsLoaded); // TODO: Could be multikey. res->setIsMultiKey(false); res->setIndexOnly(false); diff --git a/src/mongo/db/query/parsed_projection.cpp b/src/mongo/db/query/parsed_projection.cpp index 0d5da2fe02d..b972ca34f9e 100644 --- a/src/mongo/db/query/parsed_projection.cpp +++ b/src/mongo/db/query/parsed_projection.cpp @@ -57,6 +57,9 @@ namespace mongo { bool hasIndexKeyProjection = false; + bool wantGeoNearPoint = false; + bool wantGeoNearDistance = false; + // Until we see a positional or elemMatch operator we're normal. ArrayOpType arrayOpType = ARRAY_OP_NORMAL; @@ -142,14 +145,23 @@ namespace mongo { if (!mongoutils::str::equals(e2.valuestr(), "text") && !mongoutils::str::equals(e2.valuestr(), "diskloc") - && !mongoutils::str::equals(e2.valuestr(), "indexKey")) { + && !mongoutils::str::equals(e2.valuestr(), "indexKey") + && !mongoutils::str::equals(e2.valuestr(), "geoNearDistance") + && !mongoutils::str::equals(e2.valuestr(), "geoNearPoint")) { return Status(ErrorCodes::BadValue, "unsupported $meta operator: " + e2.str()); } + // This clobbers everything else. if (mongoutils::str::equals(e2.valuestr(), "indexKey")) { hasIndexKeyProjection = true; } + else if (mongoutils::str::equals(e2.valuestr(), "geoNearDistance")) { + wantGeoNearDistance = true; + } + else if (mongoutils::str::equals(e2.valuestr(), "geoNearPoint")) { + wantGeoNearPoint = true; + } } else { return Status(ErrorCodes::BadValue, @@ -235,6 +247,10 @@ namespace mongo { // missing." pp->_requiresDocument = include || hasNonSimple || hasDottedField; + // Add geoNear projections. + pp->_wantGeoNearPoint = wantGeoNearPoint; + pp->_wantGeoNearDistance = wantGeoNearDistance; + // If it's possible to compute the projection in a covered fashion, populate _requiredFields // so the planner can perform projection analysis. if (!pp->_requiresDocument) { diff --git a/src/mongo/db/query/parsed_projection.h b/src/mongo/db/query/parsed_projection.h index aa46a32caa2..0b02c16eb40 100644 --- a/src/mongo/db/query/parsed_projection.h +++ b/src/mongo/db/query/parsed_projection.h @@ -72,6 +72,17 @@ namespace mongo { return _source; } + /** + * Does the projection want geoNear metadata? If so any geoNear stage should include them. + */ + bool wantGeoNearDistance() const { + return _wantGeoNearDistance; + } + + bool wantGeoNearPoint() const { + return _wantGeoNearPoint; + } + private: /** * Must go through ::make @@ -96,6 +107,10 @@ namespace mongo { bool _requiresDocument; BSONObj _source; + + bool _wantGeoNearDistance; + + bool _wantGeoNearPoint; }; } // namespace mongo diff --git a/src/mongo/db/query/planner_access.cpp b/src/mongo/db/query/planner_access.cpp index 744f17be890..4af988fcfb4 100644 --- a/src/mongo/db/query/planner_access.cpp +++ b/src/mongo/db/query/planner_access.cpp @@ -103,6 +103,10 @@ namespace mongo { ret->indexKeyPattern = index.keyPattern; ret->nq = nearExpr->getData(); ret->baseBounds.fields.resize(index.keyPattern.nFields()); + if (NULL != query.getProj()) { + ret->addPointMeta = query.getProj()->wantGeoNearPoint(); + ret->addDistMeta = query.getProj()->wantGeoNearDistance(); + } return ret; } else if (indexIs2D) { diff --git a/src/mongo/db/query/query_planner.cpp b/src/mongo/db/query/query_planner.cpp index 54de06435a5..f04cc434fa8 100644 --- a/src/mongo/db/query/query_planner.cpp +++ b/src/mongo/db/query/query_planner.cpp @@ -402,6 +402,10 @@ namespace mongo { GeoNear2DNode* solnRoot = new GeoNear2DNode(); solnRoot->nq = gnme->getData(); + if (NULL != query.getProj()) { + solnRoot->addPointMeta = query.getProj()->wantGeoNearPoint(); + solnRoot->addDistMeta = query.getProj()->wantGeoNearDistance(); + } if (MatchExpression::GEO_NEAR != query.root()->matchType()) { // root is an AND, clone and delete the GEO_NEAR child. diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h index eac941b12d5..ad3dc7e9818 100644 --- a/src/mongo/db/query/query_solution.h +++ b/src/mongo/db/query/query_solution.h @@ -501,7 +501,7 @@ namespace mongo { // This is a standalone stage. struct GeoNear2DNode : public QuerySolutionNode { - GeoNear2DNode() : numWanted(100) { } + GeoNear2DNode() : numWanted(100), addPointMeta(false), addDistMeta(false) { } virtual ~GeoNear2DNode() { } virtual StageType getType() const { return STAGE_GEO_NEAR_2D; } @@ -516,11 +516,13 @@ namespace mongo { NearQuery nq; int numWanted; BSONObj indexKeyPattern; + bool addPointMeta; + bool addDistMeta; }; // This is actually its own standalone stage. struct GeoNear2DSphereNode : public QuerySolutionNode { - GeoNear2DSphereNode() { } + GeoNear2DSphereNode() : addPointMeta(false), addDistMeta(false) { } virtual ~GeoNear2DSphereNode() { } virtual StageType getType() const { return STAGE_GEO_NEAR_2DSPHERE; } @@ -537,6 +539,8 @@ namespace mongo { IndexBounds baseBounds; BSONObj indexKeyPattern; + bool addPointMeta; + bool addDistMeta; }; // diff --git a/src/mongo/db/query/stage_builder.cpp b/src/mongo/db/query/stage_builder.cpp index 22b4c8c4dae..d7d376d797f 100644 --- a/src/mongo/db/query/stage_builder.cpp +++ b/src/mongo/db/query/stage_builder.cpp @@ -186,15 +186,21 @@ namespace mongo { params.indexKeyPattern = node->indexKeyPattern; params.filter = node->filter.get(); params.numWanted = node->numWanted; - // XXX XXX where do we grab this from?? the near query...modify geo parser... :( - params.uniqueDocs = false; - // XXX XXX where do we grab this from?? the near query...modify geo parser... :( + params.addPointMeta = node->addPointMeta; + params.addDistMeta = node->addDistMeta; return new TwoDNear(params, ws); } else if (STAGE_GEO_NEAR_2DSPHERE == root->getType()) { const GeoNear2DSphereNode* node = static_cast<const GeoNear2DSphereNode*>(root); - return new S2NearStage(ns, node->indexKeyPattern, node->nq, node->baseBounds, - node->filter.get(), ws); + S2NearParams params; + params.ns = ns; + params.indexKeyPattern = node->indexKeyPattern; + params.nearQuery = node->nq; + params.baseBounds = node->baseBounds; + params.filter = node->filter.get(); + params.addPointMeta = node->addPointMeta; + params.addDistMeta = node->addDistMeta; + return new S2NearStage(params, ws); } else if (STAGE_TEXT == root->getType()) { const TextNode* node = static_cast<const TextNode*>(root); |