SERVER-67416 Always sort fieldpath string sets using custom comparator

57 files changed, 215 insertions, 201 deletions

diff --git a/src/mongo/db/exec/add_fields_projection_executor.cpp b/src/mongo/db/exec/add_fields_projection_executor.cpp
index a0fd7f08580..067059167f5 100644
--- a/src/mongo/db/exec/add_fields_projection_executor.cpp
+++ b/src/mongo/db/exec/add_fields_projection_executor.cpp
@@ -93,7 +93,7 @@ private:
     const BSONObj& _rawObj;
 
     // Tracks which paths we've seen to ensure no two paths conflict with each other.
-    std::set<std::string, PathPrefixComparator> _seenPaths;
+    OrderedPathSet _seenPaths;
 };
 
 void ProjectionSpecValidator::uassertValid(const BSONObj& spec) {
diff --git a/src/mongo/db/exec/add_fields_projection_executor.h b/src/mongo/db/exec/add_fields_projection_executor.h
index c2c8e8481e3..12f7bbfe19b 100644
--- a/src/mongo/db/exec/add_fields_projection_executor.h
+++ b/src/mongo/db/exec/add_fields_projection_executor.h
@@ -112,7 +112,7 @@ public:
     }
 
     DocumentSource::GetModPathsReturn getModifiedPaths() const final {
-        std::set<std::string> computedPaths;
+        OrderedPathSet computedPaths;
         StringMap<std::string> renamedPaths;
         _root->reportComputedPaths(&computedPaths, &renamedPaths);
         return {DocumentSource::GetModPathsReturn::Type::kFiniteSet,
diff --git a/src/mongo/db/exec/exclusion_projection_executor.h b/src/mongo/db/exec/exclusion_projection_executor.h
index a9c1fade72d..eb75f86fa20 100644
--- a/src/mongo/db/exec/exclusion_projection_executor.h
+++ b/src/mongo/db/exec/exclusion_projection_executor.h
@@ -149,7 +149,7 @@ public:
             return {DocumentSource::GetModPathsReturn::Type::kAllPaths, {}, {}};
         }
 
-        std::set<std::string> modifiedPaths;
+        OrderedPathSet modifiedPaths;
         _root->reportProjectedPaths(&modifiedPaths);
         return {DocumentSource::GetModPathsReturn::Type::kFiniteSet, std::move(modifiedPaths), {}};
     }
diff --git a/src/mongo/db/exec/inclusion_projection_executor.h b/src/mongo/db/exec/inclusion_projection_executor.h
index a0429ff924f..f0dd72aae80 100644
--- a/src/mongo/db/exec/inclusion_projection_executor.h
+++ b/src/mongo/db/exec/inclusion_projection_executor.h
@@ -237,10 +237,10 @@ public:
             return {DocumentSource::GetModPathsReturn::Type::kAllPaths, {}, {}};
         }
 
-        std::set<std::string> preservedPaths;
+        OrderedPathSet preservedPaths;
         _root->reportProjectedPaths(&preservedPaths);
 
-        std::set<std::string> computedPaths;
+        OrderedPathSet computedPaths;
         StringMap<std::string> renamedPaths;
         _root->reportComputedPaths(&computedPaths, &renamedPaths);
 
diff --git a/src/mongo/db/exec/projection_executor_wildcard_access_test.cpp b/src/mongo/db/exec/projection_executor_wildcard_access_test.cpp
index bdf5dea8241..fc1e74a0c2e 100644
--- a/src/mongo/db/exec/projection_executor_wildcard_access_test.cpp
+++ b/src/mongo/db/exec/projection_executor_wildcard_access_test.cpp
@@ -74,7 +74,7 @@ std::unique_ptr<ProjectionExecutor> makeProjectionWithDefaultIdExclusionAndNeste
     return createProjectionExecutor(projSpec, policies);
 }
 
-std::set<FieldRef> toFieldRefs(const std::set<std::string>& stringPaths) {
+std::set<FieldRef> toFieldRefs(const OrderedPathSet& stringPaths) {
     std::set<FieldRef> fieldRefs;
     std::transform(stringPaths.begin(),
                    stringPaths.end(),
diff --git a/src/mongo/db/exec/projection_node.cpp b/src/mongo/db/exec/projection_node.cpp
index 1ef569ecd75..00fcf70946f 100644
--- a/src/mongo/db/exec/projection_node.cpp
+++ b/src/mongo/db/exec/projection_node.cpp
@@ -229,7 +229,7 @@ Value ProjectionNode::applyExpressionsToValue(const Document& root, Value inputV
     }
 }
 
-void ProjectionNode::reportProjectedPaths(std::set<std::string>* projectedPaths) const {
+void ProjectionNode::reportProjectedPaths(OrderedPathSet* projectedPaths) const {
     for (auto&& projectedField : _projectedFields) {
         projectedPaths->insert(FieldPath::getFullyQualifiedPath(_pathToNode, projectedField));
     }
@@ -239,7 +239,7 @@ void ProjectionNode::reportProjectedPaths(std::set<std::string>* projectedPaths)
     }
 }
 
-void ProjectionNode::reportComputedPaths(std::set<std::string>* computedPaths,
+void ProjectionNode::reportComputedPaths(OrderedPathSet* computedPaths,
                                          StringMap<std::string>* renamedPaths) const {
     for (auto&& computedPair : _expressions) {
         // The expression's path is the concatenation of the path to this node, plus the field name
diff --git a/src/mongo/db/exec/projection_node.h b/src/mongo/db/exec/projection_node.h
index 2a587580330..cf79c26719c 100644
--- a/src/mongo/db/exec/projection_node.h
+++ b/src/mongo/db/exec/projection_node.h
@@ -102,7 +102,7 @@ public:
     /**
      * Recursively report all paths that are referenced by this projection.
      */
-    void reportProjectedPaths(std::set<std::string>* preservedPaths) const;
+    void reportProjectedPaths(OrderedPathSet* preservedPaths) const;
 
     /**
      * Return an optional number, x, which indicates that it is safe to stop reading the document
@@ -119,7 +119,7 @@ public:
      * 'renamedPaths'. Each entry in 'renamedPaths' maps from the path's new name to its old name
      * prior to application of this projection.
      */
-    void reportComputedPaths(std::set<std::string>* computedPaths,
+    void reportComputedPaths(OrderedPathSet* computedPaths,
                              StringMap<std::string>* renamedPaths) const;
 
     const std::string& getPath() const {
diff --git a/src/mongo/db/matcher/expression_algo.cpp b/src/mongo/db/matcher/expression_algo.cpp
index 8fc98dac37e..0e67713864a 100644
--- a/src/mongo/db/matcher/expression_algo.cpp
+++ b/src/mongo/db/matcher/expression_algo.cpp
@@ -31,6 +31,7 @@
 #include "mongo/platform/basic.h"
 
 #include "mongo/base/checked_cast.h"
+#include "mongo/bson/unordered_fields_bsonobj_comparator.h"
 #include "mongo/db/matcher/expression.h"
 #include "mongo/db/matcher/expression_algo.h"
 #include "mongo/db/matcher/expression_array.h"
@@ -374,7 +375,7 @@ unique_ptr<MatchExpression> createNorOfNodes(std::vector<unique_ptr<MatchExpress
  */
 std::pair<unique_ptr<MatchExpression>, unique_ptr<MatchExpression>> splitMatchExpressionByFunction(
     unique_ptr<MatchExpression> expr,
-    const std::set<std::string>& fields,
+    const OrderedPathSet& fields,
     expression::ShouldSplitExprFunc shouldSplitOut) {
     if (shouldSplitOut(*expr, fields)) {
         // 'expr' satisfies our split condition and can be completely split out.
@@ -440,7 +441,7 @@ std::pair<unique_ptr<MatchExpression>, unique_ptr<MatchExpression>> splitMatchEx
 bool pathDependenciesAreExact(StringData key, const MatchExpression* expr) {
     DepsTracker columnDeps;
     expr->addDependencies(&columnDeps);
-    return !columnDeps.needWholeDocument && columnDeps.fields == std::set{key.toString()};
+    return !columnDeps.needWholeDocument && columnDeps.fields == OrderedPathSet{key.toString()};
 }
 
 bool tryAddExprHelper(StringData path,
@@ -786,7 +787,33 @@ bool hasOnlyRenameableMatchExpressionChildren(const MatchExpression& expr) {
     return true;
 }
 
-bool isIndependentOf(const MatchExpression& expr, const std::set<std::string>& pathSet) {
+bool containsDependency(const OrderedPathSet& testSet, const OrderedPathSet& prefixCandidates) {
+    if (testSet.empty()) {
+        return false;
+    }
+
+    PathComparator pathComparator;
+    auto i2 = testSet.begin();
+    for (auto p1 : prefixCandidates) {
+        while (pathComparator(*i2, p1)) {
+            ++i2;
+            if (i2 == testSet.end()) {
+                return false;
+            }
+        }
+        // At this point we know that p1 <= *i2, so it may be identical or a path prefix.
+        if (p1 == *i2 || isPathPrefixOf(p1, *i2)) {
+            return true;
+        }
+    }
+    return false;
+}
+
+bool areIndependent(const OrderedPathSet& pathSet1, const OrderedPathSet& pathSet2) {
+    return !containsDependency(pathSet1, pathSet2) && !containsDependency(pathSet2, pathSet1);
+}
+
+bool isIndependentOf(const MatchExpression& expr, const OrderedPathSet& pathSet) {
     // Any expression types that do not have renaming implemented cannot have their independence
     // evaluated here. See applyRenamesToExpression().
     if (!hasOnlyRenameableMatchExpressionChildren(expr)) {
@@ -796,38 +823,42 @@ bool isIndependentOf(const MatchExpression& expr, const std::set<std::string>& p
     auto depsTracker = DepsTracker{};
     expr.addDependencies(&depsTracker);
     // Match expressions that generate random numbers can't be safely split out and pushed down.
-    return !depsTracker.needRandomGenerator &&
-        std::none_of(
-            depsTracker.fields.begin(), depsTracker.fields.end(), [&pathSet](auto&& field) {
-                return pathSet.find(field) != pathSet.end() ||
-                    std::any_of(pathSet.begin(), pathSet.end(), [&field](auto&& path) {
-                           return expression::isPathPrefixOf(field, path) ||
-                               expression::isPathPrefixOf(path, field);
-                       });
-            });
+    if (depsTracker.needRandomGenerator || depsTracker.needWholeDocument) {
+        return false;
+    }
+    return areIndependent(pathSet, depsTracker.fields);
 }
 
-bool isOnlyDependentOn(const MatchExpression& expr, const std::set<std::string>& pathSet) {
+bool isOnlyDependentOn(const MatchExpression& expr, const OrderedPathSet& pathSet) {
     // Any expression types that do not have renaming implemented cannot have their independence
     // evaluated here. See applyRenamesToExpression().
     if (!hasOnlyRenameableMatchExpressionChildren(expr)) {
         return false;
     }
 
-    auto depsTracker = DepsTracker{};
-    expr.addDependencies(&depsTracker);
+    // The approach below takes only O(n log n) time.
+
+    // Find the unique dependencies of pathSet.
+    auto pathsDeps =
+        DepsTracker::simplifyDependencies(pathSet, DepsTracker::TruncateToRootLevel::no);
+    auto pathsDepsCopy = OrderedPathSet(pathsDeps.begin(), pathsDeps.end());
+
+    // Now add the match expression's paths and see if the dependencies are the same.
+    auto exprDepsTracker = DepsTracker{};
+    expr.addDependencies(&exprDepsTracker);
     // Match expressions that generate random numbers can't be safely split out and pushed down.
-    return !depsTracker.needRandomGenerator &&
-        std::all_of(depsTracker.fields.begin(), depsTracker.fields.end(), [&](auto&& field) {
-            return std::any_of(pathSet.begin(), pathSet.end(), [&](auto&& path) {
-                return path == field || isPathPrefixOf(path, field);
-            });
-        });
+    if (exprDepsTracker.needRandomGenerator) {
+        return false;
+    }
+    pathsDepsCopy.insert(exprDepsTracker.fields.begin(), exprDepsTracker.fields.end());
+
+    return pathsDeps ==
+        DepsTracker::simplifyDependencies(pathsDepsCopy, DepsTracker::TruncateToRootLevel::no);
 }
 
 std::pair<unique_ptr<MatchExpression>, unique_ptr<MatchExpression>> splitMatchExpressionBy(
     unique_ptr<MatchExpression> expr,
-    const std::set<std::string>& fields,
+    const OrderedPathSet& fields,
     const StringMap<std::string>& renames,
     ShouldSplitExprFunc func /*= isIndependentOf */) {
     auto splitExpr = splitMatchExpressionByFunction(std::move(expr), fields, func);
diff --git a/src/mongo/db/matcher/expression_algo.h b/src/mongo/db/matcher/expression_algo.h
index 0fdbac756a0..70c7e0adcc6 100644
--- a/src/mongo/db/matcher/expression_algo.h
+++ b/src/mongo/db/matcher/expression_algo.h
@@ -34,6 +34,7 @@
 #include <set>
 
 #include "mongo/base/string_data.h"
+#include "mongo/db/pipeline/dependencies.h"
 #include "mongo/util/string_map.h"
 
 namespace mongo {
@@ -85,17 +86,32 @@ bool isSubsetOf(const MatchExpression* lhs, const MatchExpression* rhs);
  * For example, {a: "foo", b: "bar"} is splittable by "b", while
  * {$or: [{a: {$eq: "foo"}}, {b: {$eq: "bar"}}]} is not splittable by "b", due to the $or.
  */
-bool isSplittableBy(const MatchExpression& expr, const std::set<std::string>& pathSet);
+bool isSplittableBy(const MatchExpression& expr, const OrderedPathSet& pathSet);
+
+/**
+ * True if no path in either set is contained by a path in the other.  Does not check for
+ * dependencies within each of the sets, just across sets.  Runs in 0(n) time.
+ *
+ * areIndependent([a.b, b, a], [c]) --> true
+ * areIndependent([a.b, b, a], [a.b.f]) --> false
+ */
+bool areIndependent(const OrderedPathSet& pathSet1, const OrderedPathSet& pathSet2);
+
+/**
+ * Return true if any of the fieldPaths in prefixCandidates are identical to or an ancestor of any
+ * of the fieldpaths in testSet.  The order of the parameters matters -- it's not commutative.
+ */
+bool containsDependency(const OrderedPathSet& testSet, const OrderedPathSet& prefixCandidates);
 
 /**
  * Determine if 'expr' is reliant upon any path from 'pathSet'.
  */
-bool isIndependentOf(const MatchExpression& expr, const std::set<std::string>& pathSet);
+bool isIndependentOf(const MatchExpression& expr, const OrderedPathSet& pathSet);
 
 /**
  * Determine if 'expr' is reliant only upon paths from 'pathSet'.
  */
-bool isOnlyDependentOn(const MatchExpression& expr, const std::set<std::string>& pathSet);
+bool isOnlyDependentOn(const MatchExpression& expr, const OrderedPathSet& pathSet);
 
 /**
  * Returns whether the path represented by 'first' is an prefix of the path represented by 'second'.
@@ -122,8 +138,7 @@ bool bidirectionalPathPrefixOf(StringData first, StringData second);
  */
 void mapOver(MatchExpression* expr, NodeTraversalFunc func, std::string path = "");
 
-using ShouldSplitExprFunc =
-    std::function<bool(const MatchExpression&, const std::set<std::string>&)>;
+using ShouldSplitExprFunc = std::function<bool(const MatchExpression&, const OrderedPathSet&)>;
 
 /**
  * Attempt to split 'expr' into two MatchExpressions according to 'func'. 'func' describes the
@@ -146,7 +161,7 @@ using ShouldSplitExprFunc =
  */
 std::pair<std::unique_ptr<MatchExpression>, std::unique_ptr<MatchExpression>>
 splitMatchExpressionBy(std::unique_ptr<MatchExpression> expr,
-                       const std::set<std::string>& fields,
+                       const OrderedPathSet& fields,
                        const StringMap<std::string>& renames,
                        ShouldSplitExprFunc func = isIndependentOf);
 
diff --git a/src/mongo/db/matcher/expression_algo_test.cpp b/src/mongo/db/matcher/expression_algo_test.cpp
index 7bb074e3cbc..f2ebefbb76d 100644
--- a/src/mongo/db/matcher/expression_algo_test.cpp
+++ b/src/mongo/db/matcher/expression_algo_test.cpp
@@ -931,6 +931,15 @@ TEST(IsIndependent, NonRenameableExpressionIsNotIndependent) {
     }
 }
 
+TEST(IsIndependent, EmptyDependencySetsPassIsOnlyDependentOn) {
+    BSONObj matchPredicate = fromjson("{}");
+    boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest());
+    auto swMatchExpression = MatchExpressionParser::parse(matchPredicate, std::move(expCtx));
+    ASSERT_OK(swMatchExpression.getStatus());
+    auto matchExpression = std::move(swMatchExpression.getValue());
+    ASSERT_TRUE(expression::isOnlyDependentOn(*matchExpression.get(), {}));
+}
+
 TEST(SplitMatchExpression, AndWithSplittableChildrenIsSplittable) {
     BSONObj matchPredicate = fromjson("{$and: [{a: 1}, {b: 1}]}");
     boost::intrusive_ptr<ExpressionContextForTest> expCtx(new ExpressionContextForTest());
diff --git a/src/mongo/db/pipeline/abt/abt_document_source_visitor.cpp b/src/mongo/db/pipeline/abt/abt_document_source_visitor.cpp
index 582f3263bfb..1d136a098ce 100644
--- a/src/mongo/db/pipeline/abt/abt_document_source_visitor.cpp
+++ b/src/mongo/db/pipeline/abt/abt_document_source_visitor.cpp
@@ -179,7 +179,7 @@ private:
     }
 
     void processProjectedPaths(const projection_executor::InclusionNode& node) {
-        std::set<std::string> preservedPaths;
+        OrderedPathSet preservedPaths;
         node.reportProjectedPaths(&preservedPaths);
 
         for (const std::string& preservedPathStr : preservedPaths) {
@@ -194,7 +194,7 @@ private:
     void processComputedPaths(const projection_executor::InclusionNode& node,
                               const std::string& rootProjection,
                               const bool isAddingFields) {
-        std::set<std::string> computedPaths;
+        OrderedPathSet computedPaths;
         StringMap<std::string> renamedPaths;
         node.reportComputedPaths(&computedPaths, &renamedPaths);
 
@@ -268,7 +268,7 @@ private:
     }
 
     void visitExclusionNode(const projection_executor::ExclusionNode& node) {
-        std::set<std::string> preservedPaths;
+        OrderedPathSet preservedPaths;
         node.reportProjectedPaths(&preservedPaths);
 
         for (const std::string& preservedPathStr : preservedPaths) {
diff --git a/src/mongo/db/pipeline/abt/field_map_builder.h b/src/mongo/db/pipeline/abt/field_map_builder.h
index af593d38cd3..4eedf150644 100644
--- a/src/mongo/db/pipeline/abt/field_map_builder.h
+++ b/src/mongo/db/pipeline/abt/field_map_builder.h
@@ -57,7 +57,7 @@ struct FieldMapEntry {
     bool _hasDrop = false;
     std::string _constVarName;
 
-    std::set<std::string> _childPaths;
+    OrderedPathSet _childPaths;
 };
 
 class FieldMapBuilder {
diff --git a/src/mongo/db/pipeline/dependencies.cpp b/src/mongo/db/pipeline/dependencies.cpp
index 479c1876471..4480ec8cf6b 100644
--- a/src/mongo/db/pipeline/dependencies.cpp
+++ b/src/mongo/db/pipeline/dependencies.cpp
@@ -65,13 +65,6 @@ OrderedPathSet DepsTracker::simplifyDependencies(OrderedPathSet dependencies,
     return returnSet;
 }
 
-std::list<std::string> DepsTracker::sortedFields() const {
-    // Use a special comparator to put parent fieldpaths before their children.
-    std::list<std::string> sortedFields(fields.begin(), fields.end());
-    sortedFields.sort(PathPrefixComparator());
-    return sortedFields;
-}
-
 BSONObj DepsTracker::toProjectionWithoutMetadata(
     TruncateToRootLevel truncationBehavior /*= TruncateToRootLevel::no*/) const {
     BSONObjBuilder bb;
@@ -87,35 +80,16 @@ BSONObj DepsTracker::toProjectionWithoutMetadata(
         return bb.obj();
     }
 
-    // Go through dependency fieldpaths to find the minimal set of projections that cover the
-    // dependencies. For example, the dependencies ["a.b", "a.b.c.g", "c", "c.d", "f"] would be
-    // minimally covered by the projection {"a.b": 1, "c": 1, "f": 1}. The key operation here is
-    // folding dependencies into ancestor dependencies, wherever possible. This is assisted by a
-    // special sort in DepsTracker::sortedFields that treats '.' as the first char and thus places
-    // parent paths directly before their children.
+    // Create a projection from the simplified dependencies (absorbing descendants into parents).
+    // For example, the dependencies ["a.b", "a.b.c.g", "c", "c.d", "f"] would be
+    // minimally covered by the projection {"a.b": 1, "c": 1, "f": 1}.
     bool idSpecified = false;
-    std::string last;
-    for (const auto& field : sortedFields()) {
-        if (str::startsWith(field, "_id") && (field.size() == 3 || field[3] == '.')) {
+    for (auto path : simplifyDependencies(fields, truncationBehavior)) {
+        // Remember if _id was specified.  If not, we'll later explicitly add {_id: 0}
+        if (str::startsWith(path, "_id") && (path.size() == 3 || path[3] == '.')) {
             idSpecified = true;
         }
-
-        if (!last.empty() && str::startsWith(field, last)) {
-            // We are including a parent of this field, so we can skip this field.
-            continue;
-        }
-
-        // Check that the field requested is a valid field name in the agg language. This
-        // constructor will throw if it isn't.
-        FieldPath fp(field);
-
-        if (truncationBehavior == TruncateToRootLevel::yes) {
-            last = fp.front().toString() + '.';
-            bb.append(fp.front(), 1);
-        } else {
-            last = field + '.';
-            bb.append(field, 1);
-        }
+        bb.append(path, 1);
     }
 
     if (!idSpecified) {
@@ -137,7 +111,7 @@ void DepsTracker::setNeedsMetadata(DocumentMetadataFields::MetaType type, bool r
 }
 
 // Returns true if the lhs value should sort before the rhs, false otherwise.
-bool PathPrefixComparator::operator()(const std::string& lhs, const std::string& rhs) const {
+bool PathComparator::operator()(const std::string& lhs, const std::string& rhs) const {
     constexpr char dot = '.';
 
     for (size_t pos = 0, len = std::min(lhs.size(), rhs.size()); pos < len; ++pos) {
diff --git a/src/mongo/db/pipeline/dependencies.h b/src/mongo/db/pipeline/dependencies.h
index 94f4489b71f..963584ba148 100644
--- a/src/mongo/db/pipeline/dependencies.h
+++ b/src/mongo/db/pipeline/dependencies.h
@@ -38,18 +38,20 @@
 
 namespace mongo {
 
-/** Custom comparator that orders fieldpath strings by path prefix first, then by field.
+/**
+ * Custom comparator that orders fieldpath strings by path prefix first, then by field.
  * This ensures that a parent field is ordered directly before its children.
  */
-struct PathPrefixComparator {
+struct PathComparator {
     /* Returns true if the lhs value should sort before the rhs, false otherwise. */
     bool operator()(const std::string& lhs, const std::string& rhs) const;
 };
+
 /**
  * Set of field paths strings.  When iterated over, a parent path is seen directly before its
  * children (or descendants, more generally).  Eg., "a", "a.a", "a.b", "a-plus", "b".
  */
-typedef std::set<std::string, PathPrefixComparator> OrderedPathSet;
+typedef std::set<std::string, PathComparator> OrderedPathSet;
 
 /**
  * This struct allows components in an agg pipeline to report what they need from their input.
@@ -208,11 +210,11 @@ struct DepsTracker {
     }
 
     /**
-     * Return fieldpaths ordered such that a parent is immediately before its children.
+     * Return names of needed fields in dotted notation.  A custom comparator orders the fields
+     * such that a parent is immediately before its children.
      */
-    std::list<std::string> sortedFields() const;
+    OrderedPathSet fields;
 
-    std::set<std::string> fields;    // Names of needed fields in dotted notation.
     std::set<Variables::Id> vars;    // IDs of referenced variables.
     bool needWholeDocument = false;  // If true, ignore 'fields'; the whole document is needed.
 
diff --git a/src/mongo/db/pipeline/dependencies_test.cpp b/src/mongo/db/pipeline/dependencies_test.cpp
index 938130b91bd..75451b258b8 100644
--- a/src/mongo/db/pipeline/dependencies_test.cpp
+++ b/src/mongo/db/pipeline/dependencies_test.cpp
@@ -45,8 +45,8 @@ using std::set;
 using std::string;
 
 template <size_t ArrayLen>
-set<string> arrayToSet(const char* (&array)[ArrayLen]) {
-    set<string> out;
+OrderedPathSet arrayToSet(const char* (&array)[ArrayLen]) {
+    OrderedPathSet out;
     for (size_t i = 0; i < ArrayLen; i++)
         out.insert(array[i]);
     return out;
@@ -306,19 +306,17 @@ TEST(DependenciesToProjectionTest, SortFieldPaths) {
                            "b.a"
                            "b.aa"
                            "b.🌲d"};
-    DepsTracker deps;
-    deps.fields = arrayToSet(array);
+    auto fields = arrayToSet(array);
     // our custom sort will restore the ordering above
-    std::list<std::string> fieldPathSorted = deps.sortedFields();
-    auto itr = fieldPathSorted.begin();
-    for (unsigned long i = 0; i < fieldPathSorted.size(); i++) {
+    auto itr = fields.begin();
+    for (unsigned long i = 0; i < fields.size(); i++) {
         ASSERT_EQ(*itr, array[i]);
         ++itr;
     }
 }
 
 TEST(DependenciesToProjectionTest, PathLessThan) {
-    auto lessThan = PathPrefixComparator();
+    auto lessThan = PathComparator();
     ASSERT_FALSE(lessThan("a", "a"));
     ASSERT_TRUE(lessThan("a", "aa"));
     ASSERT_TRUE(lessThan("a", "b"));
diff --git a/src/mongo/db/pipeline/document_path_support.cpp b/src/mongo/db/pipeline/document_path_support.cpp
index a57d0496a1d..03113191623 100644
--- a/src/mongo/db/pipeline/document_path_support.cpp
+++ b/src/mongo/db/pipeline/document_path_support.cpp
@@ -136,7 +136,7 @@ StatusWith<Value> extractElementAlongNonArrayPath(const Document& doc, const Fie
     return curValue;
 }
 
-BSONObj documentToBsonWithPaths(const Document& input, const std::set<std::string>& paths) {
+BSONObj documentToBsonWithPaths(const Document& input, const OrderedPathSet& paths) {
     BSONObjBuilder outputBuilder;
     for (auto&& path : paths) {
         // getNestedField does not handle dotted paths correctly, so instead of retrieving the
diff --git a/src/mongo/db/pipeline/document_path_support.h b/src/mongo/db/pipeline/document_path_support.h
index 5d9f0a1cb6b..cba263bb836 100644
--- a/src/mongo/db/pipeline/document_path_support.h
+++ b/src/mongo/db/pipeline/document_path_support.h
@@ -63,7 +63,7 @@ StatusWith<Value> extractElementAlongNonArrayPath(const Document& doc, const Fie
 /**
  * Extracts 'paths' from the input document and returns a BSON object containing only those paths.
  */
-BSONObj documentToBsonWithPaths(const Document&, const std::set<std::string>& paths);
+BSONObj documentToBsonWithPaths(const Document&, const OrderedPathSet& paths);
 
 /**
  * Extracts 'paths' from the input document to a flat document.
diff --git a/src/mongo/db/pipeline/document_path_support_test.cpp b/src/mongo/db/pipeline/document_path_support_test.cpp
index 5e966e08a75..1cdfa179d0b 100644
--- a/src/mongo/db/pipeline/document_path_support_test.cpp
+++ b/src/mongo/db/pipeline/document_path_support_test.cpp
@@ -351,8 +351,8 @@ TEST(DocumentToBsonWithPathsTest, MissingFieldShouldNotAppearInResult) {
 TEST(DocumentToBsonWithPathsTest, ShouldSerializeNothingIfNothingIsNeeded) {
     Document input(fromjson("{a: 1, b: {c: 1}}"));
     BSONObj expected;
-    ASSERT_BSONOBJ_EQ(
-        expected, document_path_support::documentToBsonWithPaths(input, std::set<std::string>{}));
+    ASSERT_BSONOBJ_EQ(expected,
+                      document_path_support::documentToBsonWithPaths(input, OrderedPathSet{}));
 }
 
 TEST(DocumentToBsonWithPathsTest, ShouldExtractEntireArrayFromPrefixOfDottedField) {
diff --git a/src/mongo/db/pipeline/document_source.h b/src/mongo/db/pipeline/document_source.h
index f527cb1ef64..453d27cddb8 100644
--- a/src/mongo/db/pipeline/document_source.h
+++ b/src/mongo/db/pipeline/document_source.h
@@ -601,9 +601,7 @@ public:
             kAllExcept,
         };
 
-        GetModPathsReturn(Type type,
-                          std::set<std::string>&& paths,
-                          StringMap<std::string>&& renames)
+        GetModPathsReturn(Type type, OrderedPathSet&& paths, StringMap<std::string>&& renames)
             : type(type), paths(std::move(paths)), renames(std::move(renames)) {}
 
         std::set<std::string> getNewNames() {
@@ -653,7 +651,7 @@ public:
         }
 
         Type type;
-        std::set<std::string> paths;
+        OrderedPathSet paths;
 
         // Stages may fill out 'renames' to contain information about path renames. Each entry in
         // 'renames' maps from the new name of the path (valid in documents flowing *out* of this
@@ -676,7 +674,7 @@ public:
      * See GetModPathsReturn above for the possible return values and what they mean.
      */
     virtual GetModPathsReturn getModifiedPaths() const {
-        return {GetModPathsReturn::Type::kNotSupported, std::set<std::string>{}, {}};
+        return {GetModPathsReturn::Type::kNotSupported, OrderedPathSet{}, {}};
     }
 
     /**
@@ -714,7 +712,7 @@ public:
      * parallel since it will preserve the shard key.
      */
     virtual bool canRunInParallelBeforeWriteStage(
-        const std::set<std::string>& nameOfShardKeyFieldsUponEntryToStage) const {
+        const OrderedPathSet& nameOfShardKeyFieldsUponEntryToStage) const {
         return false;
     }
 
diff --git a/src/mongo/db/pipeline/document_source_change_stream_ensure_resume_token_present.h b/src/mongo/db/pipeline/document_source_change_stream_ensure_resume_token_present.h
index 3f24ed446ea..6fcabf4c0b6 100644
--- a/src/mongo/db/pipeline/document_source_change_stream_ensure_resume_token_present.h
+++ b/src/mongo/db/pipeline/document_source_change_stream_ensure_resume_token_present.h
@@ -47,7 +47,7 @@ public:
 
     GetModPathsReturn getModifiedPaths() const final {
         // This stage neither modifies nor renames any field.
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{}, {}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{}, {}};
     }
 
     static boost::intrusive_ptr<DocumentSourceChangeStreamEnsureResumeTokenPresent> create(
diff --git a/src/mongo/db/pipeline/document_source_change_stream_handle_topology_change.h b/src/mongo/db/pipeline/document_source_change_stream_handle_topology_change.h
index c5d5a16fd93..4c07368aff9 100644
--- a/src/mongo/db/pipeline/document_source_change_stream_handle_topology_change.h
+++ b/src/mongo/db/pipeline/document_source_change_stream_handle_topology_change.h
@@ -67,7 +67,7 @@ public:
 
     GetModPathsReturn getModifiedPaths() const final {
         // This stage neither modifies nor renames any field.
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{}, {}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{}, {}};
     }
 
     boost::optional<DistributedPlanLogic> distributedPlanLogic() final {
diff --git a/src/mongo/db/pipeline/document_source_change_stream_transform.cpp b/src/mongo/db/pipeline/document_source_change_stream_transform.cpp
index 766150a6e54..975afe09ba2 100644
--- a/src/mongo/db/pipeline/document_source_change_stream_transform.cpp
+++ b/src/mongo/db/pipeline/document_source_change_stream_transform.cpp
@@ -118,7 +118,7 @@ DepsTracker::State DocumentSourceChangeStreamTransform::getDependencies(DepsTrac
 
 DocumentSource::GetModPathsReturn DocumentSourceChangeStreamTransform::getModifiedPaths() const {
     // All paths are modified.
-    return {DocumentSource::GetModPathsReturn::Type::kAllPaths, std::set<std::string>{}, {}};
+    return {DocumentSource::GetModPathsReturn::Type::kAllPaths, OrderedPathSet{}, {}};
 }
 
 DocumentSource::GetNextResult DocumentSourceChangeStreamTransform::doGetNext() {
diff --git a/src/mongo/db/pipeline/document_source_change_stream_unwind_transaction.cpp b/src/mongo/db/pipeline/document_source_change_stream_unwind_transaction.cpp
index 05bfcff4df7..ae65c696d65 100644
--- a/src/mongo/db/pipeline/document_source_change_stream_unwind_transaction.cpp
+++ b/src/mongo/db/pipeline/document_source_change_stream_unwind_transaction.cpp
@@ -157,7 +157,7 @@ DepsTracker::State DocumentSourceChangeStreamUnwindTransaction::getDependencies(
 
 DocumentSource::GetModPathsReturn DocumentSourceChangeStreamUnwindTransaction::getModifiedPaths()
     const {
-    return {DocumentSource::GetModPathsReturn::Type::kAllPaths, std::set<std::string>{}, {}};
+    return {DocumentSource::GetModPathsReturn::Type::kAllPaths, OrderedPathSet{}, {}};
 }
 
 DocumentSource::GetNextResult DocumentSourceChangeStreamUnwindTransaction::doGetNext() {
diff --git a/src/mongo/db/pipeline/document_source_find_and_modify_image_lookup.cpp b/src/mongo/db/pipeline/document_source_find_and_modify_image_lookup.cpp
index 2fc1208e2b9..13229ba6d3e 100644
--- a/src/mongo/db/pipeline/document_source_find_and_modify_image_lookup.cpp
+++ b/src/mongo/db/pipeline/document_source_find_and_modify_image_lookup.cpp
@@ -199,7 +199,7 @@ DepsTracker::State DocumentSourceFindAndModifyImageLookup::getDependencies(
 }
 
 DocumentSource::GetModPathsReturn DocumentSourceFindAndModifyImageLookup::getModifiedPaths() const {
-    return {DocumentSource::GetModPathsReturn::Type::kAllPaths, std::set<std::string>{}, {}};
+    return {DocumentSource::GetModPathsReturn::Type::kAllPaths, OrderedPathSet{}, {}};
 }
 
 DocumentSource::GetNextResult DocumentSourceFindAndModifyImageLookup::doGetNext() {
diff --git a/src/mongo/db/pipeline/document_source_graph_lookup.cpp b/src/mongo/db/pipeline/document_source_graph_lookup.cpp
index a39c8ba5a0f..8c1076d3d76 100644
--- a/src/mongo/db/pipeline/document_source_graph_lookup.cpp
+++ b/src/mongo/db/pipeline/document_source_graph_lookup.cpp
@@ -507,7 +507,7 @@ void DocumentSourceGraphLookUp::performSearch() {
 }
 
 DocumentSource::GetModPathsReturn DocumentSourceGraphLookUp::getModifiedPaths() const {
-    std::set<std::string> modifiedPaths{_as.fullPath()};
+    OrderedPathSet modifiedPaths{_as.fullPath()};
     if (_unwind) {
         auto pathsModifiedByUnwind = _unwind.get()->getModifiedPaths();
         invariant(pathsModifiedByUnwind.type == GetModPathsReturn::Type::kFiniteSet);
diff --git a/src/mongo/db/pipeline/document_source_group.cpp b/src/mongo/db/pipeline/document_source_group.cpp
index 3f718360838..7831dfb3196 100644
--- a/src/mongo/db/pipeline/document_source_group.cpp
+++ b/src/mongo/db/pipeline/document_source_group.cpp
@@ -110,7 +110,7 @@ DepsTracker::State GroupFromFirstDocumentTransformation::addDependencies(DepsTra
 
 DocumentSource::GetModPathsReturn GroupFromFirstDocumentTransformation::getModifiedPaths() const {
     // Replaces the entire root, so all paths are modified.
-    return {DocumentSource::GetModPathsReturn::Type::kAllPaths, std::set<std::string>{}, {}};
+    return {DocumentSource::GetModPathsReturn::Type::kAllPaths, OrderedPathSet{}, {}};
 }
 
 std::unique_ptr<GroupFromFirstDocumentTransformation> GroupFromFirstDocumentTransformation::create(
@@ -368,7 +368,7 @@ DocumentSource::GetModPathsReturn DocumentSourceGroup::getModifiedPaths() const
     }
 
     return {DocumentSource::GetModPathsReturn::Type::kAllExcept,
-            std::set<std::string>{},  // No fields are preserved.
+            OrderedPathSet{},  // No fields are preserved.
             std::move(renames)};
 }
 
@@ -832,7 +832,7 @@ bool DocumentSourceGroup::pathIncludedInGroupKeys(const std::string& dottedPath)
 }
 
 bool DocumentSourceGroup::canRunInParallelBeforeWriteStage(
-    const std::set<std::string>& nameOfShardKeyFieldsUponEntryToStage) const {
+    const OrderedPathSet& nameOfShardKeyFieldsUponEntryToStage) const {
     if (_doingMerge) {
         return true;  // This is fine.
     }
diff --git a/src/mongo/db/pipeline/document_source_group.h b/src/mongo/db/pipeline/document_source_group.h
index edffed6758b..3196695d6d1 100644
--- a/src/mongo/db/pipeline/document_source_group.h
+++ b/src/mongo/db/pipeline/document_source_group.h
@@ -175,7 +175,7 @@ public:
 
     boost::optional<DistributedPlanLogic> distributedPlanLogic() final;
     bool canRunInParallelBeforeWriteStage(
-        const std::set<std::string>& nameOfShardKeyFieldsUponEntryToStage) const final;
+        const OrderedPathSet& nameOfShardKeyFieldsUponEntryToStage) const final;
 
     /**
      * When possible, creates a document transformer that transforms the first document in a group
diff --git a/src/mongo/db/pipeline/document_source_internal_compute_geo_near_distance.h b/src/mongo/db/pipeline/document_source_internal_compute_geo_near_distance.h
index 1083d58bb7f..b1a24787224 100644
--- a/src/mongo/db/pipeline/document_source_internal_compute_geo_near_distance.h
+++ b/src/mongo/db/pipeline/document_source_internal_compute_geo_near_distance.h
@@ -76,9 +76,7 @@ public:
     }
 
     DocumentSource::GetModPathsReturn getModifiedPaths() const final {
-        return {GetModPathsReturn::Type::kFiniteSet,
-                std::set<std::string>{_distanceField.fullPath()},
-                {}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{_distanceField.fullPath()}, {}};
     }
 
     boost::optional<DistributedPlanLogic> distributedPlanLogic() override {
diff --git a/src/mongo/db/pipeline/document_source_internal_unpack_bucket.cpp b/src/mongo/db/pipeline/document_source_internal_unpack_bucket.cpp
index 742dd4f5229..e49a2e3e9d4 100644
--- a/src/mongo/db/pipeline/document_source_internal_unpack_bucket.cpp
+++ b/src/mongo/db/pipeline/document_source_internal_unpack_bucket.cpp
@@ -1208,8 +1208,8 @@ DocumentSource::GetModPathsReturn DocumentSourceInternalUnpackBucket::getModifie
         StringMap<std::string> renames;
         renames.emplace(*_bucketUnpacker.bucketSpec().metaField(),
                         timeseries::kBucketMetaFieldName);
-        return {GetModPathsReturn::Type::kAllExcept, std::set<std::string>{}, std::move(renames)};
+        return {GetModPathsReturn::Type::kAllExcept, OrderedPathSet{}, std::move(renames)};
     }
-    return {GetModPathsReturn::Type::kAllPaths, std::set<std::string>{}, {}};
+    return {GetModPathsReturn::Type::kAllPaths, OrderedPathSet{}, {}};
 }
 }  // namespace mongo
diff --git a/src/mongo/db/pipeline/document_source_lookup.cpp b/src/mongo/db/pipeline/document_source_lookup.cpp
index 1a3d971dfac..0b4585de2bc 100644
--- a/src/mongo/db/pipeline/document_source_lookup.cpp
+++ b/src/mongo/db/pipeline/document_source_lookup.cpp
@@ -668,7 +668,7 @@ void DocumentSourceLookUp::addCacheStageAndOptimize(Pipeline& pipeline) {
 }
 
 DocumentSource::GetModPathsReturn DocumentSourceLookUp::getModifiedPaths() const {
-    std::set<std::string> modifiedPaths{_as.fullPath()};
+    OrderedPathSet modifiedPaths{_as.fullPath()};
     if (_unwindSrc) {
         auto pathsModifiedByUnwind = _unwindSrc->getModifiedPaths();
         invariant(pathsModifiedByUnwind.type == GetModPathsReturn::Type::kFiniteSet);
diff --git a/src/mongo/db/pipeline/document_source_match.cpp b/src/mongo/db/pipeline/document_source_match.cpp
index 10346eb6a46..038b38100c4 100644
--- a/src/mongo/db/pipeline/document_source_match.cpp
+++ b/src/mongo/db/pipeline/document_source_match.cpp
@@ -410,13 +410,13 @@ void DocumentSourceMatch::joinMatchWith(intrusive_ptr<DocumentSourceMatch> other
 }
 
 pair<intrusive_ptr<DocumentSourceMatch>, intrusive_ptr<DocumentSourceMatch>>
-DocumentSourceMatch::splitSourceBy(const std::set<std::string>& fields,
+DocumentSourceMatch::splitSourceBy(const OrderedPathSet& fields,
                                    const StringMap<std::string>& renames) && {
     return std::move(*this).splitSourceByFunc(fields, renames, expression::isIndependentOf);
 }
 
 pair<intrusive_ptr<DocumentSourceMatch>, intrusive_ptr<DocumentSourceMatch>>
-DocumentSourceMatch::splitSourceByFunc(const std::set<std::string>& fields,
+DocumentSourceMatch::splitSourceByFunc(const OrderedPathSet& fields,
                                        const StringMap<std::string>& renames,
                                        expression::ShouldSplitExprFunc func) && {
     pair<unique_ptr<MatchExpression>, unique_ptr<MatchExpression>> newExpr(
@@ -499,7 +499,7 @@ DocumentSourceMatch::splitMatchByModifiedFields(
     const boost::intrusive_ptr<DocumentSourceMatch>& match,
     const DocumentSource::GetModPathsReturn& modifiedPathsRet) {
     // Attempt to move some or all of this $match before this stage.
-    std::set<std::string> modifiedPaths;
+    OrderedPathSet modifiedPaths;
     switch (modifiedPathsRet.type) {
         case DocumentSource::GetModPathsReturn::Type::kNotSupported:
             // We don't know what paths this stage might modify, so refrain from swapping.
diff --git a/src/mongo/db/pipeline/document_source_match.h b/src/mongo/db/pipeline/document_source_match.h
index 5bf27ddfe5c..f01c655771d 100644
--- a/src/mongo/db/pipeline/document_source_match.h
+++ b/src/mongo/db/pipeline/document_source_match.h
@@ -140,7 +140,7 @@ public:
 
     GetModPathsReturn getModifiedPaths() const final {
         // This stage does not modify or rename any paths.
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{}, {}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{}, {}};
     }
 
     /**
@@ -199,7 +199,7 @@ public:
      * z: "baz"}} and {$match: {a: "foo"}}.
      */
     std::pair<boost::intrusive_ptr<DocumentSourceMatch>, boost::intrusive_ptr<DocumentSourceMatch>>
-    splitSourceBy(const std::set<std::string>& fields, const StringMap<std::string>& renames) &&;
+    splitSourceBy(const OrderedPathSet& fields, const StringMap<std::string>& renames) &&;
 
     boost::optional<DistributedPlanLogic> distributedPlanLogic() final {
         return boost::none;
@@ -220,7 +220,7 @@ protected:
 
 private:
     std::pair<boost::intrusive_ptr<DocumentSourceMatch>, boost::intrusive_ptr<DocumentSourceMatch>>
-    splitSourceByFunc(const std::set<std::string>& fields,
+    splitSourceByFunc(const OrderedPathSet& fields,
                       const StringMap<std::string>& renames,
                       expression::ShouldSplitExprFunc func) &&;
 
diff --git a/src/mongo/db/pipeline/document_source_mock.h b/src/mongo/db/pipeline/document_source_mock.h
index a6be10cbb84..39b3e17a265 100644
--- a/src/mongo/db/pipeline/document_source_mock.h
+++ b/src/mongo/db/pipeline/document_source_mock.h
@@ -106,7 +106,7 @@ public:
      * This stage does not modify anything.
      */
     GetModPathsReturn getModifiedPaths() const override {
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{}, {}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{}, {}};
     }
 
     boost::optional<DistributedPlanLogic> distributedPlanLogic() override {
diff --git a/src/mongo/db/pipeline/document_source_queue.h b/src/mongo/db/pipeline/document_source_queue.h
index 31dc128f6cb..e7eb6452d06 100644
--- a/src/mongo/db/pipeline/document_source_queue.h
+++ b/src/mongo/db/pipeline/document_source_queue.h
@@ -75,7 +75,7 @@ public:
      * This stage does not modify anything.
      */
     GetModPathsReturn getModifiedPaths() const override {
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{}, {}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{}, {}};
     }
 
     /**
diff --git a/src/mongo/db/pipeline/document_source_replace_root.h b/src/mongo/db/pipeline/document_source_replace_root.h
index e302ce5d88c..f288aa10321 100644
--- a/src/mongo/db/pipeline/document_source_replace_root.h
+++ b/src/mongo/db/pipeline/document_source_replace_root.h
@@ -74,7 +74,7 @@ public:
 
     DocumentSource::GetModPathsReturn getModifiedPaths() const final {
         // Replaces the entire root, so all paths are modified.
-        return {DocumentSource::GetModPathsReturn::Type::kAllPaths, std::set<std::string>{}, {}};
+        return {DocumentSource::GetModPathsReturn::Type::kAllPaths, OrderedPathSet{}, {}};
     }
 
     const boost::intrusive_ptr<Expression>& getExpression() const {
diff --git a/src/mongo/db/pipeline/document_source_set_window_fields.h b/src/mongo/db/pipeline/document_source_set_window_fields.h
index 652d1206ec9..f0f9b0742ce 100644
--- a/src/mongo/db/pipeline/document_source_set_window_fields.h
+++ b/src/mongo/db/pipeline/document_source_set_window_fields.h
@@ -117,7 +117,7 @@ public:
           _iterator(expCtx.get(), pSource, &_memoryTracker, std::move(partitionBy), _sortBy){};
 
     GetModPathsReturn getModifiedPaths() const final {
-        std::set<std::string> outputPaths;
+        OrderedPathSet outputPaths;
         for (auto&& outputField : _outputFields) {
             outputPaths.insert(outputField.fieldName);
         }
diff --git a/src/mongo/db/pipeline/document_source_sort.cpp b/src/mongo/db/pipeline/document_source_sort.cpp
index 711641c8cd6..e1ee0f3e6f3 100644
--- a/src/mongo/db/pipeline/document_source_sort.cpp
+++ b/src/mongo/db/pipeline/document_source_sort.cpp
@@ -656,7 +656,7 @@ boost::optional<DocumentSource::DistributedPlanLogic> DocumentSourceSort::distri
 }
 
 bool DocumentSourceSort::canRunInParallelBeforeWriteStage(
-    const std::set<std::string>& nameOfShardKeyFieldsUponEntryToStage) const {
+    const OrderedPathSet& nameOfShardKeyFieldsUponEntryToStage) const {
     // This is an interesting special case. If there are no further stages which require merging the
     // streams into one, a $sort should not require it. This is only the case because the sort order
     // doesn't matter for a pipeline ending with a write stage. We may encounter it here as an
diff --git a/src/mongo/db/pipeline/document_source_sort.h b/src/mongo/db/pipeline/document_source_sort.h
index f0ab0c28a3c..ba087ee4a3f 100644
--- a/src/mongo/db/pipeline/document_source_sort.h
+++ b/src/mongo/db/pipeline/document_source_sort.h
@@ -79,7 +79,7 @@ public:
 
     GetModPathsReturn getModifiedPaths() const final {
         // A $sort does not modify any paths.
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{}, {}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{}, {}};
     }
 
     StageConstraints constraints(Pipeline::SplitState) const final {
@@ -102,7 +102,7 @@ public:
 
     boost::optional<DistributedPlanLogic> distributedPlanLogic() final;
     bool canRunInParallelBeforeWriteStage(
-        const std::set<std::string>& nameOfShardKeyFieldsUponEntryToStage) const final;
+        const OrderedPathSet& nameOfShardKeyFieldsUponEntryToStage) const final;
 
     /**
      * Returns the sort key pattern.
diff --git a/src/mongo/db/pipeline/document_source_unwind.cpp b/src/mongo/db/pipeline/document_source_unwind.cpp
index daf7adcd5ed..2161b0b9bbb 100644
--- a/src/mongo/db/pipeline/document_source_unwind.cpp
+++ b/src/mongo/db/pipeline/document_source_unwind.cpp
@@ -220,7 +220,7 @@ DocumentSource::GetNextResult DocumentSourceUnwind::doGetNext() {
 }
 
 DocumentSource::GetModPathsReturn DocumentSourceUnwind::getModifiedPaths() const {
-    std::set<std::string> modifiedFields{_unwindPath.fullPath()};
+    OrderedPathSet modifiedFields{_unwindPath.fullPath()};
     if (_indexPath) {
         modifiedFields.insert(_indexPath->fullPath());
     }
diff --git a/src/mongo/db/pipeline/document_source_writer.h b/src/mongo/db/pipeline/document_source_writer.h
index 98c8590d650..284699deb30 100644
--- a/src/mongo/db/pipeline/document_source_writer.h
+++ b/src/mongo/db/pipeline/document_source_writer.h
@@ -116,7 +116,7 @@ public:
     GetModPathsReturn getModifiedPaths() const override {
         // For purposes of tracking which fields come from where, the writer stage does not modify
         // any fields by default.
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{}, {}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{}, {}};
     }
 
     boost::optional<DistributedPlanLogic> distributedPlanLogic() override {
@@ -124,7 +124,7 @@ public:
     }
 
     bool canRunInParallelBeforeWriteStage(
-        const std::set<std::string>& nameOfShardKeyFieldsUponEntryToStage) const override {
+        const OrderedPathSet& nameOfShardKeyFieldsUponEntryToStage) const override {
         return true;
     }
 
diff --git a/src/mongo/db/pipeline/expression.h b/src/mongo/db/pipeline/expression.h
index 474f79ceb1f..29cfd9d509f 100644
--- a/src/mongo/db/pipeline/expression.h
+++ b/src/mongo/db/pipeline/expression.h
@@ -170,7 +170,7 @@ public:
      */
     struct ComputedPaths {
         // Non-rename computed paths.
-        std::set<std::string> paths;
+        OrderedPathSet paths;
 
         // Mappings from the old name of a path before applying this expression, to the new one
         // after applying this expression.
diff --git a/src/mongo/db/pipeline/expression_date_test.cpp b/src/mongo/db/pipeline/expression_date_test.cpp
index efe0a577ef6..9205ea29633 100644
--- a/src/mongo/db/pipeline/expression_date_test.cpp
+++ b/src/mongo/db/pipeline/expression_date_test.cpp
@@ -1771,7 +1771,7 @@ TEST_F(ExpressionDateDiffTest, AddsDependencies) {
     auto depsTracker = dateDiffExpression->getDependencies();
     ASSERT_TRUE(
         (depsTracker.fields ==
-         std::set<std::string>{
+         OrderedPathSet{
              "startDateField", "endDateField", "unitField", "timezoneField", "startOfWeekField"}));
 }
 }  // namespace ExpressionDateDiffTest
@@ -1869,7 +1869,7 @@ TEST_F(ExpressionDateTruncTest, AddsDependencies) {
     const auto depsTracker = dateTruncExpression->getDependencies();
     ASSERT_TRUE(
         (depsTracker.fields ==
-         std::set<std::string>{
+         OrderedPathSet{
              "dateField", "unitField", "binSizeField", "timezoneField", "startOfWeekField"}));
 }
 }  // namespace
diff --git a/src/mongo/db/pipeline/pipeline_test.cpp b/src/mongo/db/pipeline/pipeline_test.cpp
index ae84c241c7d..cd1b99870bc 100644
--- a/src/mongo/db/pipeline/pipeline_test.cpp
+++ b/src/mongo/db/pipeline/pipeline_test.cpp
@@ -4666,7 +4666,7 @@ public:
      * Returns a description which communicate that this stage modifies nothing.
      */
     GetModPathsReturn getModifiedPaths() const final {
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>(), {}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet(), {}};
     }
 };
 
@@ -4743,7 +4743,7 @@ public:
      * Returns a description which communicate that this stage modifies nothing.
      */
     GetModPathsReturn getModifiedPaths() const final {
-        return {GetModPathsReturn::Type::kNotSupported, std::set<std::string>(), {}};
+        return {GetModPathsReturn::Type::kNotSupported, OrderedPathSet(), {}};
     }
 };
 
@@ -4779,7 +4779,7 @@ public:
         return new RenamesAToB(expCtx);
     }
     GetModPathsReturn getModifiedPaths() const final {
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{}, {{"b", "a"}}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{}, {{"b", "a"}}};
     }
 };
 
@@ -4903,7 +4903,7 @@ public:
         return new RenamesBToC(expCtx);
     }
     GetModPathsReturn getModifiedPaths() const final {
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{}, {{"c", "b"}}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{}, {{"c", "b"}}};
     }
 };
 
@@ -4946,7 +4946,7 @@ public:
         return new RenamesBToA(expCtx);
     }
     GetModPathsReturn getModifiedPaths() const final {
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{}, {{"a", "b"}}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{}, {{"a", "b"}}};
     }
 };
 
diff --git a/src/mongo/db/pipeline/semantic_analysis.cpp b/src/mongo/db/pipeline/semantic_analysis.cpp
index c1613a6a85f..04aa2de4541 100644
--- a/src/mongo/db/pipeline/semantic_analysis.cpp
+++ b/src/mongo/db/pipeline/semantic_analysis.cpp
@@ -79,7 +79,7 @@ boost::optional<std::string> findRename(const StringMap<std::string>& renamedPat
  * maps the path to itself.
  */
 StringMap<std::string> computeNamesAssumingAnyPathsNotRenamedAreUnmodified(
-    const StringMap<std::string>& renamedPaths, const std::set<std::string>& pathsOfInterest) {
+    const StringMap<std::string>& renamedPaths, const OrderedPathSet& pathsOfInterest) {
     StringMap<std::string> renameOut;
     for (auto&& ofInterest : pathsOfInterest) {
         if (auto name = findRename(renamedPaths, ofInterest)) {
@@ -163,7 +163,7 @@ template <class Iterator>
 boost::optional<Iterator> lookForNestUnnestPattern(
     Iterator start,
     Iterator end,
-    std::set<std::string> pathsOfInterest,
+    OrderedPathSet pathsOfInterest,
     const Direction& traversalDir,
     boost::optional<std::function<bool(DocumentSource*)>> additionalStageValidatorCallback) {
     auto replaceRootTransform = isReplaceRoot((*start).get());
@@ -252,7 +252,7 @@ template <class Iterator>
 std::pair<Iterator, StringMap<std::string>> multiStageRenamedPaths(
     Iterator start,
     Iterator end,
-    std::set<std::string> pathsOfInterest,
+    OrderedPathSet pathsOfInterest,
     const Direction& traversalDir,
     boost::optional<std::function<bool(DocumentSource*)>> additionalStageValidatorCallback =
         boost::none) {
@@ -300,7 +300,7 @@ template <class Iterator>
 boost::optional<StringMap<std::string>> renamedPathsFullPipeline(
     Iterator start,
     Iterator end,
-    std::set<std::string> pathsOfInterest,
+    OrderedPathSet pathsOfInterest,
     const Direction& traversalDir,
     boost::optional<std::function<bool(DocumentSource*)>> additionalStageValidatorCallback) {
     auto [itr, renameMap] = multiStageRenamedPaths(
@@ -313,9 +313,9 @@ boost::optional<StringMap<std::string>> renamedPathsFullPipeline(
 
 }  // namespace
 
-std::set<std::string> extractModifiedDependencies(const std::set<std::string>& dependencies,
-                                                  const std::set<std::string>& preservedPaths) {
-    std::set<std::string> modifiedDependencies;
+OrderedPathSet extractModifiedDependencies(const OrderedPathSet& dependencies,
+                                           const OrderedPathSet& preservedPaths) {
+    OrderedPathSet modifiedDependencies;
 
     // The modified dependencies is *almost* the set difference 'dependencies' - 'preservedPaths',
     // except that if p in 'preservedPaths' is a "path prefix" of d in 'dependencies', then 'd'
@@ -342,7 +342,7 @@ std::set<std::string> extractModifiedDependencies(const std::set<std::string>& d
     return modifiedDependencies;
 }
 
-boost::optional<StringMap<std::string>> renamedPaths(const std::set<std::string>& pathsOfInterest,
+boost::optional<StringMap<std::string>> renamedPaths(const OrderedPathSet& pathsOfInterest,
                                                      const DocumentSource& stage,
                                                      const Direction& traversalDir) {
     auto modifiedPathsRet = stage.getModifiedPaths();
@@ -351,19 +351,11 @@ boost::optional<StringMap<std::string>> renamedPaths(const std::set<std::string>
         case DocumentSource::GetModPathsReturn::Type::kAllPaths:
             return boost::none;
         case DocumentSource::GetModPathsReturn::Type::kFiniteSet: {
-            for (auto&& modified : modifiedPathsRet.paths) {
-                for (auto&& ofInterest : pathsOfInterest) {
-                    // Any overlap of the path means the path of interest is not preserved. For
-                    // example, if the path of interest is "a.b", then a modified path of "a",
-                    // "a.b", or "a.b.c" would all signal that "a.b" is not preserved.
-                    if (ofInterest == modified ||
-                        expression::isPathPrefixOf(ofInterest, modified) ||
-                        expression::isPathPrefixOf(modified, ofInterest)) {
-                        // This stage modifies at least one of the fields which the caller is
-                        // interested in, bail out.
-                        return boost::none;
-                    }
-                }
+            // Any overlap of the path means the path of interest is not preserved. For
+            // example, if the path of interest is "a.b", then a modified path of "a",
+            // "a.b", or "a.b.c" would all signal that "a.b" is not preserved.
+            if (!expression::areIndependent(modifiedPathsRet.paths, pathsOfInterest)) {
+                return boost::none;
             }
 
             // None of the paths of interest were modified, construct the result map, mapping
@@ -401,7 +393,7 @@ boost::optional<StringMap<std::string>> renamedPaths(const std::set<std::string>
 boost::optional<StringMap<std::string>> renamedPaths(
     const Pipeline::SourceContainer::const_iterator start,
     const Pipeline::SourceContainer::const_iterator end,
-    const std::set<std::string>& pathsOfInterest,
+    const OrderedPathSet& pathsOfInterest,
     boost::optional<std::function<bool(DocumentSource*)>> additionalStageValidatorCallback) {
     return renamedPathsFullPipeline(
         start, end, pathsOfInterest, Direction::kForward, additionalStageValidatorCallback);
@@ -410,7 +402,7 @@ boost::optional<StringMap<std::string>> renamedPaths(
 boost::optional<StringMap<std::string>> renamedPaths(
     const Pipeline::SourceContainer::const_reverse_iterator start,
     const Pipeline::SourceContainer::const_reverse_iterator end,
-    const std::set<std::string>& pathsOfInterest,
+    const OrderedPathSet& pathsOfInterest,
     boost::optional<std::function<bool(DocumentSource*)>> additionalStageValidatorCallback) {
     return renamedPathsFullPipeline(
         start, end, pathsOfInterest, Direction::kBackward, additionalStageValidatorCallback);
@@ -420,7 +412,7 @@ std::pair<Pipeline::SourceContainer::const_iterator, StringMap<std::string>>
 findLongestViablePrefixPreservingPaths(
     const Pipeline::SourceContainer::const_iterator start,
     const Pipeline::SourceContainer::const_iterator end,
-    const std::set<std::string>& pathsOfInterest,
+    const OrderedPathSet& pathsOfInterest,
     boost::optional<std::function<bool(DocumentSource*)>> additionalStageValidatorCallback) {
     return multiStageRenamedPaths(
         start, end, pathsOfInterest, Direction::kForward, additionalStageValidatorCallback);
diff --git a/src/mongo/db/pipeline/semantic_analysis.h b/src/mongo/db/pipeline/semantic_analysis.h
index 1931800b9df..befbddac923 100644
--- a/src/mongo/db/pipeline/semantic_analysis.h
+++ b/src/mongo/db/pipeline/semantic_analysis.h
@@ -57,7 +57,7 @@ enum class Direction { kForward, kBackward };
  * the pipeline, and direction is backward. Say nextStage preserves all the paths but renamed "a" to
  * "b"; we would return a mapping b-->a.
  */
-boost::optional<StringMap<std::string>> renamedPaths(const std::set<std::string>& pathsOfInterest,
+boost::optional<StringMap<std::string>> renamedPaths(const OrderedPathSet& pathsOfInterest,
                                                      const DocumentSource& stage,
                                                      const Direction& traversalDir);
 /**
@@ -72,7 +72,7 @@ boost::optional<StringMap<std::string>> renamedPaths(const std::set<std::string>
 boost::optional<StringMap<std::string>> renamedPaths(
     Pipeline::SourceContainer::const_iterator start,
     Pipeline::SourceContainer::const_iterator end,
-    const std::set<std::string>& pathsOfInterest,
+    const OrderedPathSet& pathsOfInterest,
     boost::optional<std::function<bool(DocumentSource*)>> additionalStageValidatorCallback =
         boost::none);
 
@@ -89,7 +89,7 @@ boost::optional<StringMap<std::string>> renamedPaths(
 boost::optional<StringMap<std::string>> renamedPaths(
     Pipeline::SourceContainer::const_reverse_iterator start,
     Pipeline::SourceContainer::const_reverse_iterator end,
-    const std::set<std::string>& pathsOfInterest,
+    const OrderedPathSet& pathsOfInterest,
     boost::optional<std::function<bool(DocumentSource*)>> additionalStageValidatorCallback =
         boost::none);
 
@@ -104,7 +104,7 @@ boost::optional<StringMap<std::string>> renamedPaths(
 std::pair<Pipeline::SourceContainer::const_iterator, StringMap<std::string>>
 findLongestViablePrefixPreservingPaths(Pipeline::SourceContainer::const_iterator start,
                                        Pipeline::SourceContainer::const_iterator end,
-                                       const std::set<std::string>& pathsOfInterest,
+                                       const OrderedPathSet& pathsOfInterest,
                                        boost::optional<std::function<bool(DocumentSource*)>>
                                            additionalStageValidatorCallback = boost::none);
 
@@ -115,10 +115,9 @@ findLongestViablePrefixPreservingPaths(Pipeline::SourceContainer::const_iterator
  * For example, extractModifiedDependencies({'a', 'b', 'c.d', 'e'}, {'a', 'b.c', c'}) returns
  * {'b', 'e'}, since 'b' and 'e' are not preserved (only 'b.c' is preserved).
  */
-std::set<std::string> extractModifiedDependencies(const std::set<std::string>& dependencies,
-                                                  const std::set<std::string>& preservedPaths);
+OrderedPathSet extractModifiedDependencies(const OrderedPathSet& dependencies,
+                                           const OrderedPathSet& preservedPaths);
 
-bool pathSetContainsOverlappingPath(const std::set<std::string>& paths,
-                                    const std::string& targetPath);
+bool pathSetContainsOverlappingPath(const OrderedPathSet& paths, const std::string& targetPath);
 
 }  // namespace mongo::semantic_analysis
diff --git a/src/mongo/db/pipeline/semantic_analysis_test.cpp b/src/mongo/db/pipeline/semantic_analysis_test.cpp
index ca95d9098a2..0b6e4d224bf 100644
--- a/src/mongo/db/pipeline/semantic_analysis_test.cpp
+++ b/src/mongo/db/pipeline/semantic_analysis_test.cpp
@@ -54,7 +54,7 @@ public:
     GetModPathsReturn getModifiedPaths() const final {
         // Pretend this stage simply renames the "a" field to be "b", leaving the value of "a" the
         // same. This would be the equivalent of an {$addFields: {b: "$a"}}.
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{}, {{"b", "a"}}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{}, {{"b", "a"}}};
     }
 };
 
@@ -132,9 +132,7 @@ public:
         : DocumentSourceTestOptimizations(expCtx) {}
 
     GetModPathsReturn getModifiedPaths() const final {
-        return {GetModPathsReturn::Type::kAllExcept,
-                std::set<std::string>{"e", "f", "g"},
-                {{"d", "c"}}};
+        return {GetModPathsReturn::Type::kAllExcept, OrderedPathSet{"e", "f", "g"}, {{"d", "c"}}};
     }
 };
 
@@ -196,7 +194,7 @@ public:
         : DocumentSourceTestOptimizations(expCtx) {}
 
     GetModPathsReturn getModifiedPaths() const final {
-        return {GetModPathsReturn::Type::kAllExcept, std::set<std::string>{"f.g"}, {{"e", "c.d"}}};
+        return {GetModPathsReturn::Type::kAllExcept, OrderedPathSet{"f.g"}, {{"e", "c.d"}}};
     }
 };
 
@@ -295,7 +293,7 @@ public:
         : DocumentSourceTestOptimizations(expCtx) {}
 
     GetModPathsReturn getModifiedPaths() const final {
-        return {GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{"c.d"}, {{"x.y", "a"}}};
+        return {GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{"c.d"}, {{"x.y", "a"}}};
     }
 };
 
@@ -386,7 +384,7 @@ public:
     ModifiesAllPaths(const boost::intrusive_ptr<ExpressionContext>& expCtx)
         : DocumentSourceTestOptimizations(expCtx) {}
     GetModPathsReturn getModifiedPaths() const final {
-        return {GetModPathsReturn::Type::kAllPaths, std::set<std::string>{}, {}};
+        return {GetModPathsReturn::Type::kAllPaths, OrderedPathSet{}, {}};
     }
 };
 
@@ -415,7 +413,7 @@ public:
     ModificationsUnknown(const boost::intrusive_ptr<ExpressionContext>& expCtx)
         : DocumentSourceTestOptimizations(expCtx) {}
     GetModPathsReturn getModifiedPaths() const final {
-        return {GetModPathsReturn::Type::kNotSupported, std::set<std::string>{}, {}};
+        return {GetModPathsReturn::Type::kNotSupported, OrderedPathSet{}, {}};
     }
 };
 
diff --git a/src/mongo/db/pipeline/sharded_agg_helpers.cpp b/src/mongo/db/pipeline/sharded_agg_helpers.cpp
index 7940fc0b97b..ca48387afdc 100644
--- a/src/mongo/db/pipeline/sharded_agg_helpers.cpp
+++ b/src/mongo/db/pipeline/sharded_agg_helpers.cpp
@@ -414,7 +414,7 @@ void moveEligibleStreamingStagesBeforeSortOnShards(Pipeline* shardPipe,
         // Expected last stage on the shards to be a $sort.
         return;
     }
-    auto sortPaths = sortPattern.getFieldNames<std::set<std::string>>();
+    auto sortPaths = sortPattern.getFieldNames<OrderedPathSet>();
     auto firstMergeStage = mergePipe->getSources().cbegin();
     std::function<bool(DocumentSource*)> distributedPlanLogicCallback = [](DocumentSource* stage) {
         return !static_cast<bool>(stage->distributedPlanLogic());
@@ -561,7 +561,7 @@ void limitFieldsSentFromShardsToMerger(Pipeline* shardPipe, Pipeline* mergePipe)
 }
 
 bool stageCanRunInParallel(const boost::intrusive_ptr<DocumentSource>& stage,
-                           const std::set<std::string>& nameOfShardKeyFieldsUponEntryToStage) {
+                           const OrderedPathSet& nameOfShardKeyFieldsUponEntryToStage) {
     if (stage->distributedPlanLogic()) {
         return stage->canRunInParallelBeforeWriteStage(nameOfShardKeyFieldsUponEntryToStage);
     } else {
@@ -598,7 +598,7 @@ BSONObj buildNewKeyPattern(const ShardKeyPattern& shardKey, StringMap<std::strin
 }
 
 StringMap<std::string> computeShardKeyRenameMap(const Pipeline* mergePipeline,
-                                                std::set<std::string>&& pathsOfShardKey) {
+                                                OrderedPathSet&& pathsOfShardKey) {
     auto traversalStart = mergePipeline->getSources().crbegin();
     auto traversalEnd = mergePipeline->getSources().crend();
     const auto leadingGroup =
@@ -626,7 +626,7 @@ StringMap<std::string> computeShardKeyRenameMap(const Pipeline* mergePipeline,
  *
  * Purposefully takes 'shardKeyPaths' by value so that it can be modified throughout.
  */
-bool anyStageModifiesShardKeyOrNeedsMerge(std::set<std::string> shardKeyPaths,
+bool anyStageModifiesShardKeyOrNeedsMerge(OrderedPathSet shardKeyPaths,
                                           const Pipeline* mergePipeline) {
     const auto& stages = mergePipeline->getSources();
     for (auto it = stages.crbegin(); it != stages.crend(); ++it) {
@@ -653,7 +653,7 @@ boost::optional<ShardedExchangePolicy> walkPipelineBackwardsTrackingShardKey(
     OperationContext* opCtx, const Pipeline* mergePipeline, const ChunkManager& chunkManager) {
 
     const ShardKeyPattern& shardKey = chunkManager.getShardKeyPattern();
-    std::set<std::string> shardKeyPaths;
+    OrderedPathSet shardKeyPaths;
     for (auto&& path : shardKey.getKeyPatternFields()) {
         shardKeyPaths.emplace(path->dottedField().toString());
     }
diff --git a/src/mongo/db/query/canonical_query_encoder.cpp b/src/mongo/db/query/canonical_query_encoder.cpp
index ccbcce36635..6a6938ef4b1 100644
--- a/src/mongo/db/query/canonical_query_encoder.cpp
+++ b/src/mongo/db/query/canonical_query_encoder.cpp
@@ -584,7 +584,7 @@ void encodeKeyForProj(const projection_ast::Projection* proj, StringBuilder* key
         return;
     }
 
-    std::set<std::string> requiredFields = proj->getRequiredFields();
+    auto requiredFields = proj->getRequiredFields();
 
     // If the only requirement is that $sortKey be included with some value, we just act as if the
     // entire document is needed.
diff --git a/src/mongo/db/query/planner_analysis.cpp b/src/mongo/db/query/planner_analysis.cpp
index 40d8d7b0d0d..2436ce5c29b 100644
--- a/src/mongo/db/query/planner_analysis.cpp
+++ b/src/mongo/db/query/planner_analysis.cpp
@@ -337,7 +337,7 @@ void geoSkipValidationOn(const std::set<StringData>& twoDSphereFields,
 /**
  * If any field is missing from the list of fields the projection wants, we are not covered.
  */
-auto providesAllFields(const std::set<std::string>& fields, const QuerySolutionNode& solnRoot) {
+auto providesAllFields(const OrderedPathSet& fields, const QuerySolutionNode& solnRoot) {
     for (auto&& field : fields) {
         if (!solnRoot.hasField(field))
             return false;
diff --git a/src/mongo/db/query/projection.cpp b/src/mongo/db/query/projection.cpp
index af5fedfe780..b55fc03602a 100644
--- a/src/mongo/db/query/projection.cpp
+++ b/src/mongo/db/query/projection.cpp
@@ -49,7 +49,7 @@ struct DepsAnalysisData {
         fieldDependencyTracker.fields.insert(fieldName);
     }
 
-    std::set<std::string> requiredFields() const {
+    OrderedPathSet requiredFields() const {
         return fieldDependencyTracker.fields;
     }
 };
diff --git a/src/mongo/db/query/projection.h b/src/mongo/db/query/projection.h
index 914567e87ed..97b8d1e0d30 100644
--- a/src/mongo/db/query/projection.h
+++ b/src/mongo/db/query/projection.h
@@ -49,7 +49,7 @@ struct ProjectionDependencies {
     bool containsElemMatch = false;
 
     // Which fields are necessary to perform the projection, or boost::none if all are required.
-    boost::optional<std::set<std::string>> requiredFields;
+    boost::optional<OrderedPathSet> requiredFields;
 
     bool hasDottedPath = false;
 
@@ -95,7 +95,7 @@ public:
      * Return which fields are required to compute the projection, assuming the entire document is
      * not needed.
      */
-    const std::set<std::string>& getRequiredFields() const {
+    const OrderedPathSet& getRequiredFields() const {
         invariant(_type == ProjectType::kInclusion);
         return *_deps.requiredFields;
     }
diff --git a/src/mongo/db/query/query_planner_wildcard_index_test.cpp b/src/mongo/db/query/query_planner_wildcard_index_test.cpp
index cd943126a17..b344e71d3c0 100644
--- a/src/mongo/db/query/query_planner_wildcard_index_test.cpp
+++ b/src/mongo/db/query/query_planner_wildcard_index_test.cpp
@@ -56,7 +56,7 @@ protected:
     }
 
     void addWildcardIndex(BSONObj keyPattern,
-                          const std::set<std::string>& multikeyPathSet = {},
+                          const OrderedPathSet& multikeyPathSet = {},
                           BSONObj wildcardProjection = BSONObj{},
                           MatchExpression* partialFilterExpr = nullptr,
                           CollatorInterface* collator = nullptr,
diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp
index dc24bc3653a..7b24c1c08a3 100644
--- a/src/mongo/db/query/query_solution.cpp
+++ b/src/mongo/db/query/query_solution.cpp
@@ -1083,8 +1083,8 @@ bool IndexScanNode::operator==(const IndexScanNode& other) const {
 // ColumnIndexScanNode
 //
 ColumnIndexScanNode::ColumnIndexScanNode(ColumnIndexEntry indexEntry,
-                                         std::set<std::string> outputFieldsIn,
-                                         std::set<std::string> matchFieldsIn,
+                                         OrderedPathSet outputFieldsIn,
+                                         OrderedPathSet matchFieldsIn,
                                          StringMap<std::unique_ptr<MatchExpression>> filtersByPath,
                                          std::unique_ptr<MatchExpression> postAssemblyFilter)
     : indexEntry(std::move(indexEntry)),
diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h
index f318884280b..235d59f37be 100644
--- a/src/mongo/db/query/query_solution.h
+++ b/src/mongo/db/query/query_solution.h
@@ -515,8 +515,8 @@ struct CollectionScanNode : public QuerySolutionNodeWithSortSet {
 
 struct ColumnIndexScanNode : public QuerySolutionNode {
     ColumnIndexScanNode(ColumnIndexEntry,
-                        std::set<std::string> outputFields,
-                        std::set<std::string> matchFields,
+                        OrderedPathSet outputFields,
+                        OrderedPathSet matchFields,
                         StringMap<std::unique_ptr<MatchExpression>> filtersByPath,
                         std::unique_ptr<MatchExpression> postAssemblyFilter);
 
@@ -556,11 +556,11 @@ struct ColumnIndexScanNode : public QuerySolutionNode {
     ColumnIndexEntry indexEntry;
 
     // The fields we need to output. Dot separated path names.
-    std::set<std::string> outputFields;
+    OrderedPathSet outputFields;
 
     // The fields which are referenced by any and all filters - either in 'filtersByPath' or
     // 'postAssemblyFilter'.
-    std::set<std::string> matchFields;
+    OrderedPathSet matchFields;
 
     // A column scan can apply a filter to the columns directly while scanning, or to a document
     // assembled from the scanned columns.
@@ -575,7 +575,7 @@ struct ColumnIndexScanNode : public QuerySolutionNode {
 
     // A cached copy of the union of the above two field sets which we expect to be frequently asked
     // for.
-    std::set<std::string> allFields;
+    OrderedPathSet allFields;
 };
 
 /**
diff --git a/src/mongo/db/query/sort_pattern.h b/src/mongo/db/query/sort_pattern.h
index 9c74208ac43..b659ed0124e 100644
--- a/src/mongo/db/query/sort_pattern.h
+++ b/src/mongo/db/query/sort_pattern.h
@@ -147,6 +147,6 @@ private:
     std::vector<SortPatternPart> _sortPattern;
 
     // The set of paths on which we're sorting.
-    std::set<std::string> _paths;
+    OrderedPathSet _paths;
 };
 }  // namespace mongo
diff --git a/src/mongo/db/s/resharding/document_source_resharding_iterate_transaction.cpp b/src/mongo/db/s/resharding/document_source_resharding_iterate_transaction.cpp
index 9d412147b7f..8075111e3af 100644
--- a/src/mongo/db/s/resharding/document_source_resharding_iterate_transaction.cpp
+++ b/src/mongo/db/s/resharding/document_source_resharding_iterate_transaction.cpp
@@ -134,7 +134,7 @@ DepsTracker::State DocumentSourceReshardingIterateTransaction::getDependencies(
 
 DocumentSource::GetModPathsReturn DocumentSourceReshardingIterateTransaction::getModifiedPaths()
     const {
-    return {DocumentSource::GetModPathsReturn::Type::kAllPaths, std::set<std::string>{}, {}};
+    return {DocumentSource::GetModPathsReturn::Type::kAllPaths, OrderedPathSet{}, {}};
 }
 
 DocumentSource::GetNextResult DocumentSourceReshardingIterateTransaction::doGetNext() {
diff --git a/src/mongo/db/s/resharding/document_source_resharding_ownership_match.cpp b/src/mongo/db/s/resharding/document_source_resharding_ownership_match.cpp
index f8a186e3bcd..3144723bf2d 100644
--- a/src/mongo/db/s/resharding/document_source_resharding_ownership_match.cpp
+++ b/src/mongo/db/s/resharding/document_source_resharding_ownership_match.cpp
@@ -109,7 +109,7 @@ DepsTracker::State DocumentSourceReshardingOwnershipMatch::getDependencies(
 
 DocumentSource::GetModPathsReturn DocumentSourceReshardingOwnershipMatch::getModifiedPaths() const {
     // This stage does not modify or rename any paths.
-    return {DocumentSource::GetModPathsReturn::Type::kFiniteSet, std::set<std::string>{}, {}};
+    return {DocumentSource::GetModPathsReturn::Type::kFiniteSet, OrderedPathSet{}, {}};
 }
 
 DocumentSource::GetNextResult DocumentSourceReshardingOwnershipMatch::doGetNext() {