SERVER-58587 Improve performance of $setIsSubset by replacing std::set with an unordered set

(cherry picked from commit f0defdba5d5839e4cbfd3b0fa69fb8369419ded4)

1 files changed, 13 insertions, 6 deletions

diff --git a/src/mongo/db/pipeline/expression.cpp b/src/mongo/db/pipeline/expression.cpp
index de1434b0fcc..2cc52c45bdc 100644
--- a/src/mongo/db/pipeline/expression.cpp
+++ b/src/mongo/db/pipeline/expression.cpp
@@ -4090,6 +4090,13 @@ ValueSet arrayToSet(const Value& val, const ValueComparator& valueComparator) {
     valueSet.insert(array.begin(), array.end());
     return valueSet;
 }
+
+ValueUnorderedSet arrayToUnorderedSet(const Value& val, const ValueComparator& valueComparator) {
+    const vector<Value>& array = val.getArray();
+    ValueUnorderedSet valueSet = valueComparator.makeUnorderedValueSet();
+    valueSet.insert(array.begin(), array.end());
+    return valueSet;
+}
 }  // namespace
 
 /* ----------------------- ExpressionSetDifference ---------------------------- */
@@ -4219,7 +4226,7 @@ const char* ExpressionSetIntersection::getOpName() const {
 /* ----------------------- ExpressionSetIsSubset ---------------------------- */
 
 namespace {
-Value setIsSubsetHelper(const vector<Value>& lhs, const ValueSet& rhs) {
+Value setIsSubsetHelper(const vector<Value>& lhs, const ValueUnorderedSet& rhs) {
     // do not shortcircuit when lhs.size() > rhs.size()
     // because lhs can have redundant entries
     for (vector<Value>::const_iterator it = lhs.begin(); it != lhs.end(); ++it) {
@@ -4244,8 +4251,8 @@ Value ExpressionSetIsSubset::evaluate(const Document& root, Variables* variables
                           << "argument is of type: " << typeName(rhs.getType()),
             rhs.isArray());
 
-    return setIsSubsetHelper(lhs.getArray(),
-                             arrayToSet(rhs, getExpressionContext()->getValueComparator()));
+    return setIsSubsetHelper(
+        lhs.getArray(), arrayToUnorderedSet(rhs, getExpressionContext()->getValueComparator()));
 }
 
 /**
@@ -4258,7 +4265,7 @@ Value ExpressionSetIsSubset::evaluate(const Document& root, Variables* variables
 class ExpressionSetIsSubset::Optimized : public ExpressionSetIsSubset {
 public:
     Optimized(const boost::intrusive_ptr<ExpressionContext>& expCtx,
-              const ValueSet& cachedRhsSet,
+              const ValueUnorderedSet& cachedRhsSet,
               const ExpressionVector& operands)
         : ExpressionSetIsSubset(expCtx), _cachedRhsSet(cachedRhsSet) {
         _children = operands;
@@ -4276,7 +4283,7 @@ public:
     }
 
 private:
-    const ValueSet _cachedRhsSet;
+    const ValueUnorderedSet _cachedRhsSet;
 };
 
 intrusive_ptr<Expression> ExpressionSetIsSubset::optimize() {
@@ -4296,7 +4303,7 @@ intrusive_ptr<Expression> ExpressionSetIsSubset::optimize() {
 
         intrusive_ptr<Expression> optimizedWithConstant(
             new Optimized(this->getExpressionContext(),
-                          arrayToSet(rhs, getExpressionContext()->getValueComparator()),
+                          arrayToUnorderedSet(rhs, getExpressionContext()->getValueComparator()),
                           _children));
         return optimizedWithConstant;
     }