SERVER-37417 Plans using $** wildcard indices can return duplicate results

12 files changed, 24 insertions, 21 deletions

diff --git a/src/mongo/db/exec/geo_near.cpp b/src/mongo/db/exec/geo_near.cpp
index 80923c4f55e..88b1c4a8e32 100644
--- a/src/mongo/db/exec/geo_near.cpp
+++ b/src/mongo/db/exec/geo_near.cpp
@@ -318,7 +318,6 @@ void GeoNear2DStage::DensityEstimator::buildIndexScan(OperationContext* opCtx,
     // This is handled in query planning.
     IndexScanParams scanParams(opCtx, *_twoDIndex);
     scanParams.bounds = _nearParams->baseBounds;
-    scanParams.doNotDedup = true;
 
     // The "2d" field is always the first in the index
     const string twoDFieldName = _nearParams->nearQuery->field;
@@ -691,7 +690,6 @@ StatusWith<NearStage::CoveredInterval*>  //
 
     // This does force us to do our own deduping of results.
     scanParams.bounds = _nearParams.baseBounds;
-    scanParams.doNotDedup = true;
 
     // The "2d" field is always the first in the index
     const string twoDFieldName = _nearParams.nearQuery->field;
@@ -882,7 +880,6 @@ void GeoNear2DSphereStage::DensityEstimator::buildIndexScan(OperationContext* op
                                                             Collection* collection) {
     IndexScanParams scanParams(opCtx, *_s2Index);
     scanParams.bounds = _nearParams->baseBounds;
-    scanParams.doNotDedup = true;
 
     // Because the planner doesn't yet set up 2D index bounds, do it ourselves here
     const string s2Field = _nearParams->nearQuery->field;
@@ -1057,7 +1054,6 @@ StatusWith<NearStage::CoveredInterval*>  //
 
     // This does force us to do our own deduping of results.
     scanParams.bounds = _nearParams.baseBounds;
-    scanParams.doNotDedup = true;
 
     // Because the planner doesn't yet set up 2D index bounds, do it ourselves here
     const string s2Field = _nearParams.nearQuery->field;
diff --git a/src/mongo/db/exec/index_scan.cpp b/src/mongo/db/exec/index_scan.cpp
index a4836e6e5a2..b17ca54c8a7 100644
--- a/src/mongo/db/exec/index_scan.cpp
+++ b/src/mongo/db/exec/index_scan.cpp
@@ -69,7 +69,6 @@ IndexScan::IndexScan(OperationContext* opCtx,
       _keyPattern(params.keyPattern.getOwned()),
       _scanState(INITIALIZING),
       _filter(filter),
-      _shouldDedup(true),
       _forward(params.direction == 1),
       _params(std::move(params)),
       _startKeyInclusive(IndexBounds::isStartIncludedInBound(_params.bounds.boundInclusion)),
@@ -86,12 +85,6 @@ IndexScan::IndexScan(OperationContext* opCtx,
 }
 
 boost::optional<IndexKeyEntry> IndexScan::initIndexScan() {
-    if (_params.doNotDedup) {
-        _shouldDedup = false;
-    } else {
-        _shouldDedup = _params.isMultiKey;
-    }
-
     // Perform the possibly heavy-duty initialization of the underlying index cursor.
     _indexCursor = _iam->newCursor(getOpCtx(), _forward);
 
@@ -193,7 +186,7 @@ PlanStage::StageState IndexScan::doWork(WorkingSetID* out) {
 
     _scanState = GETTING_NEXT;
 
-    if (_shouldDedup) {
+    if (_params.shouldDedup) {
         ++_specificStats.dupsTested;
         if (!_returned.insert(kv->loc).second) {
             // We've seen this RecordId before. Skip it this time.
diff --git a/src/mongo/db/exec/index_scan.h b/src/mongo/db/exec/index_scan.h
index 583acb52881..2ee3f7b1553 100644
--- a/src/mongo/db/exec/index_scan.h
+++ b/src/mongo/db/exec/index_scan.h
@@ -89,7 +89,7 @@ struct IndexScanParams {
 
     int direction{1};
 
-    bool doNotDedup{false};
+    bool shouldDedup{false};
 
     // Do we want to add the key as metadata?
     bool addKeyMetadata{false};
@@ -166,7 +166,6 @@ private:
     const MatchExpression* const _filter;
 
     // Could our index have duplicates?  If so, we use _returned to dedup.
-    bool _shouldDedup;
     stdx::unordered_set<RecordId, RecordId::Hasher> _returned;
 
     const bool _forward;
diff --git a/src/mongo/db/exec/stagedebug_cmd.cpp b/src/mongo/db/exec/stagedebug_cmd.cpp
index bc01089c83b..6d6acd38bde 100644
--- a/src/mongo/db/exec/stagedebug_cmd.cpp
+++ b/src/mongo/db/exec/stagedebug_cmd.cpp
@@ -307,6 +307,7 @@ public:
             params.bounds.boundInclusion = IndexBounds::makeBoundInclusionFromBoundBools(
                 nodeArgs["startKeyInclusive"].Bool(), nodeArgs["endKeyInclusive"].Bool());
             params.direction = nodeArgs["direction"].numberInt();
+            params.shouldDedup = desc->isMultikey(opCtx);
 
             return new IndexScan(opCtx, params, workingSet, matcher);
         } else if ("andHash" == nodeName) {
diff --git a/src/mongo/db/exec/text.cpp b/src/mongo/db/exec/text.cpp
index 2c9e0f4ba81..89a937eddbc 100644
--- a/src/mongo/db/exec/text.cpp
+++ b/src/mongo/db/exec/text.cpp
@@ -109,6 +109,7 @@ unique_ptr<PlanStage> TextStage::buildTextTree(OperationContext* opCtx,
         ixparams.bounds.boundInclusion = BoundInclusion::kIncludeBothStartAndEndKeys;
         ixparams.bounds.isSimpleRange = true;
         ixparams.direction = -1;
+        ixparams.shouldDedup = _params.index->isMultikey(opCtx);
 
         indexScanList.push_back(stdx::make_unique<IndexScan>(opCtx, ixparams, ws, nullptr));
     }
diff --git a/src/mongo/db/query/internal_plans.cpp b/src/mongo/db/query/internal_plans.cpp
index 03ee028def0..b8e96f5b338 100644
--- a/src/mongo/db/query/internal_plans.cpp
+++ b/src/mongo/db/query/internal_plans.cpp
@@ -209,6 +209,7 @@ std::unique_ptr<PlanStage> InternalPlanner::_indexScan(OperationContext* opCtx,
     params.bounds.startKey = startKey;
     params.bounds.endKey = endKey;
     params.bounds.boundInclusion = boundInclusion;
+    params.shouldDedup = descriptor->isMultikey(opCtx);
 
     std::unique_ptr<PlanStage> root =
         stdx::make_unique<IndexScan>(opCtx, std::move(params), ws, nullptr);
diff --git a/src/mongo/db/query/planner_access.cpp b/src/mongo/db/query/planner_access.cpp
index 7bcb08f0832..7a07d878ccf 100644
--- a/src/mongo/db/query/planner_access.cpp
+++ b/src/mongo/db/query/planner_access.cpp
@@ -598,11 +598,11 @@ void QueryPlannerAccess::finishLeafNode(QuerySolutionNode* node, const IndexEntr
         IndexScanNode* scan = static_cast<IndexScanNode*>(node);
         nodeIndex = &scan->index;
         bounds = &scan->bounds;
-    }
 
-    // If this is a $** index, update and populate the keyPattern, bounds, and multikeyPaths.
-    if (index.type == IndexType::INDEX_WILDCARD) {
-        wcp::finalizeWildcardIndexScanConfiguration(nodeIndex, bounds);
+        // If this is a $** index, update and populate the keyPattern, bounds, and multikeyPaths.
+        if (index.type == IndexType::INDEX_WILDCARD) {
+            wcp::finalizeWildcardIndexScanConfiguration(scan);
+        }
     }
 
     // Find the first field in the scan's bounds that was not filled out.
diff --git a/src/mongo/db/query/planner_wildcard_helpers.cpp b/src/mongo/db/query/planner_wildcard_helpers.cpp
index 1c0610823be..f44bce0563b 100644
--- a/src/mongo/db/query/planner_wildcard_helpers.cpp
+++ b/src/mongo/db/query/planner_wildcard_helpers.cpp
@@ -389,7 +389,10 @@ BoundsTightness translateWildcardIndexBoundsAndTightness(const IndexEntry& index
     return (arrayIndicesTraversedByQuery.empty() ? tightnessIn : BoundsTightness::INEXACT_FETCH);
 }
 
-void finalizeWildcardIndexScanConfiguration(IndexEntry* index, IndexBounds* bounds) {
+void finalizeWildcardIndexScanConfiguration(IndexScanNode* scan) {
+    IndexEntry* index = &scan->index;
+    IndexBounds* bounds = &scan->bounds;
+
     // We should only ever reach this point when processing a $** index. Sanity check the arguments.
     invariant(index && index->type == IndexType::INDEX_WILDCARD);
     invariant(index->keyPattern.nFields() == 1);
@@ -448,6 +451,11 @@ void finalizeWildcardIndexScanConfiguration(IndexEntry* index, IndexBounds* boun
         if (requiresSubpathBounds) {
             pathIntervals.push_back(IndexBoundsBuilder::makeRangeInterval(
                 path + subPathStart, path + subPathEnd, BoundInclusion::kIncludeStartKeyOnly));
+
+            // Queries which scan subpaths for a single wildcard index should be deduped. The index
+            // bounds may include multiple keys associated with the same document. Therefore, we
+            // instruct the IXSCAN to dedup keys which point to the same object.
+            scan->shouldDedup = true;
         }
     }
     // Ensure that the bounds' intervals are correctly aligned.
diff --git a/src/mongo/db/query/planner_wildcard_helpers.h b/src/mongo/db/query/planner_wildcard_helpers.h
index f05c475295f..0ac9f4810b1 100644
--- a/src/mongo/db/query/planner_wildcard_helpers.h
+++ b/src/mongo/db/query/planner_wildcard_helpers.h
@@ -73,8 +73,9 @@ BoundsTightness translateWildcardIndexBoundsAndTightness(const IndexEntry& index
  * - Converts the keyPattern to the {$_path: 1, "path": 1} format expected by the $** index.
  * - Adds a new entry '$_path' to the bounds vector, and computes the necessary intervals on it.
  * - Adds a new, empty entry to 'multikeyPaths' for '$_path'.
+ * - Updates shouldDedup for index scan node.
  */
-void finalizeWildcardIndexScanConfiguration(IndexEntry* index, IndexBounds* bounds);
+void finalizeWildcardIndexScanConfiguration(IndexScanNode* scan);
 
 /**
  * Returns true if the given IndexScanNode is a $** scan whose bounds overlap the object type
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index 6ba95a37232..b31be410a4d 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -519,6 +519,7 @@ IndexScanNode::IndexScanNode(IndexEntry index)
       index(std::move(index)),
       direction(1),
       addKeyMetadata(false),
+      shouldDedup(index.multikey),
       queryCollator(nullptr) {}
 
 void IndexScanNode::appendToString(mongoutils::str::stream* ss, int indent) const {
diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h
index ffd0985a679..a896b700c95 100644
--- a/src/mongo/db/query/query_solution.h
+++ b/src/mongo/db/query/query_solution.h
@@ -505,6 +505,8 @@ struct IndexScanNode : public QuerySolutionNode {
     // If there's a 'returnKey' projection we add key metadata.
     bool addKeyMetadata;
 
+    bool shouldDedup = false;
+
     IndexBounds bounds;
 
     const CollatorInterface* queryCollator;
diff --git a/src/mongo/db/query/stage_builder.cpp b/src/mongo/db/query/stage_builder.cpp
index f368a4699f8..dfc38384e43 100644
--- a/src/mongo/db/query/stage_builder.cpp
+++ b/src/mongo/db/query/stage_builder.cpp
@@ -105,6 +105,7 @@ PlanStage* buildStages(OperationContext* opCtx,
             params.bounds = ixn->bounds;
             params.direction = ixn->direction;
             params.addKeyMetadata = ixn->addKeyMetadata;
+            params.shouldDedup = ixn->shouldDedup;
             return new IndexScan(opCtx, std::move(params), ws, ixn->filter.get());
         }
         case STAGE_FETCH: {
@@ -352,7 +353,6 @@ PlanStage* buildStages(OperationContext* opCtx,
             params.startKeyInclusive = csn->startKeyInclusive;
             params.endKey = csn->endKey;
             params.endKeyInclusive = csn->endKeyInclusive;
-
             return new CountScan(opCtx, std::move(params), ws);
         }
         case STAGE_ENSURE_SORTED: {