SERVER-64830 Simplify exclusivity tracking in IndexSeekPoint

7 files changed, 391 insertions, 102 deletions

diff --git a/src/mongo/db/exec/distinct_scan.cpp b/src/mongo/db/exec/distinct_scan.cpp
index 82c0805eb43..7be30af453a 100644
--- a/src/mongo/db/exec/distinct_scan.cpp
+++ b/src/mongo/db/exec/distinct_scan.cpp
@@ -119,7 +119,7 @@ PlanStage::StageState DistinctScan::doWork(WorkingSetID* out) {
                 kv->key = kv->key.getOwned();
             _seekPoint.keyPrefix = kv->key;
             _seekPoint.prefixLen = _fieldNo + 1;
-            _seekPoint.prefixExclusive = true;
+            _seekPoint.firstExclusive = _fieldNo;
 
             // Package up the result for the caller.
             WorkingSetID id = _workingSet->allocate();
diff --git a/src/mongo/db/exec/sbe/size_estimator.cpp b/src/mongo/db/exec/sbe/size_estimator.cpp
index 0a11248287f..0395142bce9 100644
--- a/src/mongo/db/exec/sbe/size_estimator.cpp
+++ b/src/mongo/db/exec/sbe/size_estimator.cpp
@@ -54,7 +54,6 @@ size_t estimate(const Interval& interval) {
 size_t estimate(const IndexSeekPoint& indexSeekPoint) {
     size_t size = estimate(indexSeekPoint.keyPrefix);
     size += estimate(indexSeekPoint.keySuffix);
-    size += estimate(indexSeekPoint.suffixInclusive);
     return size;
 }
 
diff --git a/src/mongo/db/query/index_bounds.cpp b/src/mongo/db/query/index_bounds.cpp
index d5f3e90733f..39bf4f67737 100644
--- a/src/mongo/db/query/index_bounds.cpp
+++ b/src/mongo/db/query/index_bounds.cpp
@@ -501,16 +501,17 @@ IndexBoundsChecker::IndexBoundsChecker(const IndexBounds* bounds,
 
 bool IndexBoundsChecker::getStartSeekPoint(IndexSeekPoint* out) {
     out->prefixLen = 0;
-    out->prefixExclusive = false;
+    out->firstExclusive = -1;
     out->keySuffix.resize(_bounds->fields.size());
-    out->suffixInclusive.resize(_bounds->fields.size());
 
-    for (size_t i = 0; i < _bounds->fields.size(); ++i) {
+    for (int i = _bounds->fields.size() - 1; i >= out->prefixLen; --i) {
         if (0 == _bounds->fields[i].intervals.size()) {
             return false;
         }
         out->keySuffix[i] = &_bounds->fields[i].intervals[0].start;
-        out->suffixInclusive[i] = _bounds->fields[i].intervals[0].startInclusive;
+        if (!_bounds->fields[i].intervals[0].startInclusive) {
+            out->firstExclusive = i;
+        }
     }
 
     return true;
@@ -586,7 +587,6 @@ bool IndexBoundsChecker::isValidKey(const BSONObj& key) {
 IndexBoundsChecker::KeyState IndexBoundsChecker::checkKey(const BSONObj& key, IndexSeekPoint* out) {
     verify(_curInterval.size() > 0);
     out->keySuffix.resize(_curInterval.size());
-    out->suffixInclusive.resize(_curInterval.size());
 
     // It's useful later to go from a field number to the value for that field.  Store these.
     size_t i = 0;
@@ -628,12 +628,14 @@ IndexBoundsChecker::KeyState IndexBoundsChecker::checkKey(const BSONObj& key, In
         // Tell the caller to move forward to the start of the current interval.
         out->keyPrefix = key.getOwned();
         out->prefixLen = firstNonContainedField;
-        out->prefixExclusive = false;
+        out->firstExclusive = -1;
 
-        for (size_t j = firstNonContainedField; j < _curInterval.size(); ++j) {
+        for (int j = _curInterval.size() - 1; j >= out->prefixLen; --j) {
             const OrderedIntervalList& oil = _bounds->fields[j];
             out->keySuffix[j] = &oil.intervals[_curInterval[j]].start;
-            out->suffixInclusive[j] = oil.intervals[_curInterval[j]].startInclusive;
+            if (!oil.intervals[_curInterval[j]].startInclusive) {
+                out->firstExclusive = j;
+            }
         }
 
         return MUST_ADVANCE;
@@ -672,11 +674,13 @@ IndexBoundsChecker::KeyState IndexBoundsChecker::checkKey(const BSONObj& key, In
 
             out->keyPrefix = key.getOwned();
             out->prefixLen = firstNonContainedField;
-            out->prefixExclusive = false;
-            for (size_t i = firstNonContainedField; i < _curInterval.size(); ++i) {
+            out->firstExclusive = -1;
+            for (int i = _curInterval.size() - 1; i >= out->prefixLen; --i) {
                 const OrderedIntervalList& oil = _bounds->fields[i];
                 out->keySuffix[i] = &oil.intervals[_curInterval[i]].start;
-                out->suffixInclusive[i] = oil.intervals[_curInterval[i]].startInclusive;
+                if (!oil.intervals[_curInterval[i]].startInclusive) {
+                    out->firstExclusive = i;
+                }
             }
 
             return MUST_ADVANCE;
@@ -694,7 +698,7 @@ IndexBoundsChecker::KeyState IndexBoundsChecker::checkKey(const BSONObj& key, In
 
             out->keyPrefix = key.getOwned();
             out->prefixLen = firstNonContainedField;
-            out->prefixExclusive = true;
+            out->firstExclusive = firstNonContainedField - 1;
 
             for (size_t i = firstNonContainedField; i < _curInterval.size(); ++i) {
                 _curInterval[i] = 0;
diff --git a/src/mongo/db/query/index_bounds_test.cpp b/src/mongo/db/query/index_bounds_test.cpp
index 45cabc3cc6e..895d9cd8eb8 100644
--- a/src/mongo/db/query/index_bounds_test.cpp
+++ b/src/mongo/db/query/index_bounds_test.cpp
@@ -673,9 +673,8 @@ TEST(IndexBoundsCheckerTest, StartKey) {
     it.getStartSeekPoint(&seekPoint);
 
     ASSERT_EQUALS(seekPoint.keySuffix[0]->numberInt(), 7);
-    ASSERT_EQUALS(seekPoint.suffixInclusive[0], true);
     ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 0);
-    ASSERT_EQUALS(seekPoint.suffixInclusive[1], false);
+    ASSERT_EQUALS(seekPoint.firstExclusive, 1);
 }
 
 TEST(IndexBoundsCheckerTest, CheckEnd) {
@@ -703,7 +702,7 @@ TEST(IndexBoundsCheckerTest, CheckEnd) {
     state = it.checkKey(BSON("" << 20 << "" << 5), &seekPoint);
     ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE);
     ASSERT_EQUALS(seekPoint.prefixLen, 1);
-    ASSERT(seekPoint.prefixExclusive);
+    ASSERT_EQUALS(seekPoint.firstExclusive, 0);
 
     // The next index key is in the second interval for 'foo' and there is a valid interval for
     // 'bar'.
@@ -716,7 +715,7 @@ TEST(IndexBoundsCheckerTest, CheckEnd) {
     state = it.checkKey(BSON("" << 29.9 << "" << 5), &seekPoint);
     ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE);
     ASSERT_EQUALS(seekPoint.prefixLen, 1);
-    ASSERT(seekPoint.prefixExclusive);
+    ASSERT_EQUALS(seekPoint.firstExclusive, 0);
 }
 
 TEST(IndexBoundsCheckerTest, MoveIntervalForwardToNextInterval) {
@@ -744,11 +743,9 @@ TEST(IndexBoundsCheckerTest, MoveIntervalForwardToNextInterval) {
     ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE);
     ASSERT_EQUALS(seekPoint.prefixLen, 0);
     // Should be told to move exactly to the next interval's beginning.
-    ASSERT_EQUALS(seekPoint.prefixExclusive, false);
     ASSERT_EQUALS(seekPoint.keySuffix[0]->numberInt(), 21);
-    ASSERT_EQUALS(seekPoint.suffixInclusive[0], true);
     ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 0);
-    ASSERT_EQUALS(seekPoint.suffixInclusive[1], false);
+    ASSERT_EQUALS(seekPoint.firstExclusive, 1);
 }
 
 TEST(IndexBoundsCheckerTest, MoveIntervalForwardManyIntervals) {
@@ -798,15 +795,14 @@ TEST(IndexBoundsCheckerTest, SimpleCheckKey) {
     state = it.checkKey(BSON("" << 7 << "" << 5.00001), &seekPoint);
     ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE);
     ASSERT_EQUALS(seekPoint.prefixLen, 1);
-    ASSERT_EQUALS(seekPoint.prefixExclusive, true);
+    ASSERT_EQUALS(seekPoint.firstExclusive, 0);
 
     // Move a little forward, but note that the rightmost key isn't in the interval yet.
     state = it.checkKey(BSON("" << 7.2 << "" << 0), &seekPoint);
     ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE);
     ASSERT_EQUALS(seekPoint.prefixLen, 1);
-    ASSERT_EQUALS(seekPoint.prefixExclusive, false);
     ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 0);
-    ASSERT_EQUALS(seekPoint.suffixInclusive[1], false);
+    ASSERT_EQUALS(seekPoint.firstExclusive, 1);
 
     // Move to the edge of both intervals, 20,5
     state = it.checkKey(BSON("" << 20 << "" << 5), &seekPoint);
@@ -841,9 +837,8 @@ TEST(IndexBoundsCheckerTest, FirstKeyMovedIsOKSecondKeyMustMove) {
     state = it.checkKey(BSON("" << 10 << "" << -1), &seekPoint);
     ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE);
     ASSERT_EQUALS(seekPoint.prefixLen, 1);
-    ASSERT_EQUALS(seekPoint.prefixExclusive, false);
     ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 0);
-    ASSERT_EQUALS(seekPoint.suffixInclusive[1], false);
+    ASSERT_EQUALS(seekPoint.firstExclusive, 1);
 }
 
 TEST(IndexBoundsCheckerTest, SecondIntervalMustRewind) {
@@ -871,9 +866,8 @@ TEST(IndexBoundsCheckerTest, SecondIntervalMustRewind) {
     state = it.checkKey(BSON("" << 25 << "" << 1), &seekPoint);
     ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE);
     ASSERT_EQUALS(seekPoint.prefixLen, 1);
-    ASSERT_EQUALS(seekPoint.prefixExclusive, false);
     ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 9);
-    ASSERT_EQUALS(seekPoint.suffixInclusive[1], true);
+    ASSERT_EQUALS(seekPoint.firstExclusive, -1);
 
     state = it.checkKey(BSON("" << 25 << "" << 9), &seekPoint);
     ASSERT_EQUALS(state, IndexBoundsChecker::VALID);
@@ -911,15 +905,14 @@ TEST(IndexBoundsCheckerTest, SimpleCheckKeyBackwards) {
     state = it.checkKey(BSON("" << 20 << "" << 0), &seekPoint);
     ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE);
     ASSERT_EQUALS(seekPoint.prefixLen, 1);
-    ASSERT_EQUALS(seekPoint.prefixExclusive, true);
+    ASSERT_EQUALS(seekPoint.firstExclusive, 0);
 
     // Move a little forward, but note that the rightmost key isn't in the interval yet.
     state = it.checkKey(BSON("" << 19 << "" << 6), &seekPoint);
     ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE);
     ASSERT_EQUALS(seekPoint.prefixLen, 1);
-    ASSERT_EQUALS(seekPoint.prefixExclusive, false);
     ASSERT_EQUALS(seekPoint.keySuffix[1]->numberInt(), 5);
-    ASSERT_EQUALS(seekPoint.suffixInclusive[1], true);
+    ASSERT_EQUALS(seekPoint.firstExclusive, -1);
 
     // Move to the edge of both intervals
     state = it.checkKey(BSON("" << 7 << "" << 0.01), &seekPoint);
@@ -958,7 +951,7 @@ TEST(IndexBoundsCheckerTest, CheckEndBackwards) {
     state = it.checkKey(BSON("" << 30 << "" << 5), &seekPoint);
     ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE);
     ASSERT_EQUALS(seekPoint.prefixLen, 1);
-    ASSERT(seekPoint.prefixExclusive);
+    ASSERT_EQUALS(seekPoint.firstExclusive, 0);
 
     // The next index key is in the second interval for 'foo' and there is a valid interval for
     // 'bar'.
@@ -971,7 +964,7 @@ TEST(IndexBoundsCheckerTest, CheckEndBackwards) {
     state = it.checkKey(BSON("" << 7.001 << "" << 5), &seekPoint);
     ASSERT_EQUALS(state, IndexBoundsChecker::MUST_ADVANCE);
     ASSERT_EQUALS(seekPoint.prefixLen, 1);
-    ASSERT(seekPoint.prefixExclusive);
+    ASSERT_EQUALS(seekPoint.firstExclusive, 0);
 }
 
 //
diff --git a/src/mongo/db/storage/index_entry_comparison.cpp b/src/mongo/db/storage/index_entry_comparison.cpp
index feceb088a38..50ef5509367 100644
--- a/src/mongo/db/storage/index_entry_comparison.cpp
+++ b/src/mongo/db/storage/index_entry_comparison.cpp
@@ -114,16 +114,7 @@ int IndexEntryComparison::compare(const IndexKeyEntry& lhs, const IndexKeyEntry&
 
 KeyString::Value IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
     const IndexSeekPoint& seekPoint, KeyString::Version version, Ordering ord, bool isForward) {
-
-    // Determines the discriminator used to build the KeyString.
-    auto suffixExclusive = [&]() {
-        for (size_t i = seekPoint.prefixLen; i < seekPoint.keySuffix.size(); i++) {
-            if (!seekPoint.suffixInclusive[i])
-                return true;
-        }
-        return false;
-    };
-    bool inclusive = !seekPoint.prefixExclusive && !suffixExclusive();
+    const bool inclusive = seekPoint.firstExclusive < 0;
     const auto discriminator = isForward == inclusive ? KeyString::Discriminator::kExclusiveBefore
                                                       : KeyString::Discriminator::kExclusiveAfter;
 
@@ -139,24 +130,13 @@ KeyString::Value IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
         }
     }
 
-    // If the prefix is exclusive then the suffix does not matter as it will never be used.
-    if (seekPoint.prefixExclusive) {
-        invariant(seekPoint.prefixLen > 0);
-        return builder.getValueCopy();
-    }
-
     // Handles the suffix. Note that the useful parts of the suffix start at index prefixLen rather
     // than at 0.
-    invariant(seekPoint.keySuffix.size() == seekPoint.suffixInclusive.size());
-    for (size_t i = seekPoint.prefixLen; i < seekPoint.keySuffix.size(); i++) {
+    size_t end = seekPoint.firstExclusive >= 0 ? static_cast<size_t>(seekPoint.firstExclusive + 1)
+                                               : seekPoint.keySuffix.size();
+    for (size_t i = seekPoint.prefixLen; i < end; i++) {
         invariant(seekPoint.keySuffix[i]);
         builder.appendBSONElement(*seekPoint.keySuffix[i]);
-
-        // If an exclusive field exists then no fields after this will matter, since an
-        // exclusive field never evaluates as equal.
-        if (!seekPoint.suffixInclusive[i]) {
-            return builder.getValueCopy();
-        }
     }
     return builder.getValueCopy();
 }
diff --git a/src/mongo/db/storage/index_entry_comparison.h b/src/mongo/db/storage/index_entry_comparison.h
index a6291c3f91b..2f6232459dc 100644
--- a/src/mongo/db/storage/index_entry_comparison.h
+++ b/src/mongo/db/storage/index_entry_comparison.h
@@ -115,14 +115,12 @@ struct KeyStringEntry {
  * expressing exclusiveness on a prefix of the key. This is mostly used to express a location to
  * seek to in an index that may not be representable as a valid key.
  *
- * The "key" used for comparison is the concatenation of the first 'prefixLen' elements of
- * 'keyPrefix' followed by the last 'keySuffix.size() - prefixLen' elements of
- * 'keySuffix'.
+ * If 'firstExclusive' is negative, the "key" used for comparison is the concatenation of the first
+ * 'prefixLen' elements of 'keyPrefix' followed by the last 'keySuffix.size() - prefixLen' elements
+ * of 'keySuffix'.
  *
- * The comparison is exclusive if either 'prefixExclusive' is true or if there are any false
- * values in 'suffixInclusive' that are false at index >= 'prefixLen'.
- *
- * Portions of the key following the first exclusive part may be ignored.
+ * The comparison is exclusive if 'firstExclusive' is non-negative, and any portion of the key after
+ * that index will be omitted. The value of 'firstExclusive' must be at least 'prefixLen' - 1.
  *
  * e.g.
  *
@@ -130,9 +128,8 @@ struct KeyStringEntry {
  *
  *      keyPrefix = { "" : 1, "" : 2 }
  *      prefixLen = 1
- *      prefixExclusive = false
- *      keySuffix = [ IGNORED, { "" : 5 } ]
- *      suffixInclusive = [ IGNORED, false ]
+ *      keySuffix = [ IGNORED, { "" : 5 }, { "" : 9 } ]
+ *      firstExclusive = 1
  *
  *      ==> key is { "" : 1, "" : 5 }
  *          with the comparison being done exclusively
@@ -141,14 +138,21 @@ struct KeyStringEntry {
  *
  *      keyPrefix = { "" : 1, "" : 2 }
  *      prefixLen = 1
- *      prefixExclusive = true
  *      keySuffix = IGNORED
- *      suffixInclusive = IGNORED
+ *      firstExclusive = 0
  *
  *      ==> represented key is { "" : 1 }
  *          with the comparison being done exclusively
  *
- * 'prefixLen = 0' and 'prefixExclusive = true' are mutually incompatible.
+ *  Suppose that
+ *
+ *      keyPrefix = { "" : 1, "" : 2 }
+ *      prefixLen = 1
+ *      keySuffix = [ IGNORED, { "" : 5 }, { "" : 9 } ]
+ *      firstExclusive = -1
+ *
+ *      ==> key is { "" : 1, "" : 5, "" : 9 }
+ *          with the comparison being done inclusively
  */
 struct IndexSeekPoint {
     BSONObj keyPrefix;
@@ -159,24 +163,17 @@ struct IndexSeekPoint {
     int prefixLen = 0;
 
     /**
-     * If true, compare exclusively on just the fields on keyPrefix and ignore the suffix.
-     */
-    bool prefixExclusive = false;
-
-    /**
      * Elements starting at index 'prefixLen' are logically appended to the prefix.
      * The elements before index 'prefixLen' should be ignored.
      */
     std::vector<const BSONElement*> keySuffix;
 
     /**
-     * If the ith element is false, ignore indexes > i in keySuffix and treat the
-     * concatenated key as exclusive.
-     * The elements before index 'prefixLen' should be ignored.
-     *
-     * Must have identical size as keySuffix.
+     * If non-negative, then the comparison will be exclusive and any elements after index
+     * 'firstExclusive' are ignored. Otherwise all elements are considered and the comparison will
+     * be inclusive.
      */
-    std::vector<bool> suffixInclusive;
+    int firstExclusive = -1;
 };
 
 /**
@@ -211,11 +208,9 @@ public:
      * isForward.
      *
      * If a field is marked as exclusive, then comparisons stop after that field and return
-     * either higher or lower, even if that field compares equal. If prefixExclusive is true and
-     * prefixLen is greater than 0, then the last field in the prefix is marked as exclusive. It
-     * is illegal to specify prefixExclusive as true with a prefixLen of 0. Each bool in
-     * suffixInclusive, starting at index prefixLen, indicates whether the corresponding element
-     * in keySuffix is inclusive or exclusive.
+     * either higher or lower, even if that field compares equal. If firstExclusive is non-negative,
+     * then the field at the corresponding index is marked as exclusive and any subsequent fields
+     * are ignored.
      *
      * Returned objects are for use in lookups only and should never be inserted into the
      * database, as their format may change. The only reason this is the same type as the
diff --git a/src/mongo/db/storage/sorted_data_interface_test_cursor_advanceto.cpp b/src/mongo/db/storage/sorted_data_interface_test_cursor_advanceto.cpp
index be6870c6c37..83f9f599d2c 100644
--- a/src/mongo/db/storage/sorted_data_interface_test_cursor_advanceto.cpp
+++ b/src/mongo/db/storage/sorted_data_interface_test_cursor_advanceto.cpp
@@ -82,7 +82,7 @@ TEST(SortedDataInterface, AdvanceTo) {
         IndexSeekPoint seekPoint;
         seekPoint.keyPrefix = key1;
         seekPoint.prefixLen = 1;
-        seekPoint.prefixExclusive = false;
+        seekPoint.firstExclusive = -1;
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
                       seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
                   IndexKeyEntry(key1, loc1));
@@ -151,7 +151,7 @@ TEST(SortedDataInterface, AdvanceToReversed) {
         IndexSeekPoint seekPoint;
         seekPoint.keyPrefix = key3;
         seekPoint.prefixLen = 1;
-        seekPoint.prefixExclusive = false;
+        seekPoint.firstExclusive = -1;
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
                       seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), isForward)),
                   IndexKeyEntry(key3, loc5));
@@ -211,12 +211,12 @@ TEST(SortedDataInterface, AdvanceToKeyBeforeCursorPosition) {
         IndexSeekPoint seekPoint;
         seekPoint.keyPrefix = key0;
         seekPoint.prefixLen = 1;
-        seekPoint.prefixExclusive = false;
+        seekPoint.firstExclusive = -1;
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
                       seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
                   IndexKeyEntry(key1, loc1));
 
-        seekPoint.prefixExclusive = true;
+        seekPoint.firstExclusive = 0;
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
                       seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
                   IndexKeyEntry(key1, loc1));
@@ -263,12 +263,12 @@ TEST(SortedDataInterface, AdvanceToKeyAfterCursorPositionReversed) {
         IndexSeekPoint seekPoint;
         seekPoint.keyPrefix = key3;
         seekPoint.prefixLen = 1;
-        seekPoint.prefixExclusive = false;
+        seekPoint.firstExclusive = -1;
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
                       seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), isForward)),
                   IndexKeyEntry(key2, loc2));
 
-        seekPoint.prefixExclusive = true;
+        seekPoint.firstExclusive = 0;
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
                       seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), isForward)),
                   IndexKeyEntry(key2, loc2));
@@ -314,12 +314,12 @@ TEST(SortedDataInterface, AdvanceToKeyAtCursorPosition) {
         IndexSeekPoint seekPoint;
         seekPoint.keyPrefix = key1;
         seekPoint.prefixLen = 1;
-        seekPoint.prefixExclusive = false;
+        seekPoint.firstExclusive = -1;
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
                       seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
                   IndexKeyEntry(key1, loc1));
 
-        seekPoint.prefixExclusive = true;
+        seekPoint.firstExclusive = 0;
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
                       seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
                   boost::none);
@@ -367,12 +367,12 @@ TEST(SortedDataInterface, AdvanceToKeyAtCursorPositionReversed) {
         IndexSeekPoint seekPoint;
         seekPoint.keyPrefix = key1;
         seekPoint.prefixLen = 1;
-        seekPoint.prefixExclusive = false;
+        seekPoint.firstExclusive = -1;
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
                       seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), isForward)),
                   IndexKeyEntry(key1, loc1));
 
-        seekPoint.prefixExclusive = true;
+        seekPoint.firstExclusive = 0;
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
                       seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), isForward)),
                   boost::none);
@@ -423,7 +423,7 @@ TEST(SortedDataInterface, AdvanceToExclusive) {
         IndexSeekPoint seekPoint;
         seekPoint.keyPrefix = key1;
         seekPoint.prefixLen = 1;
-        seekPoint.prefixExclusive = true;
+        seekPoint.firstExclusive = 0;
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
                       seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
                   IndexKeyEntry(key2, loc4));
@@ -491,7 +491,7 @@ TEST(SortedDataInterface, AdvanceToExclusiveReversed) {
         IndexSeekPoint seekPoint;
         seekPoint.keyPrefix = key3;
         seekPoint.prefixLen = 1;
-        seekPoint.prefixExclusive = true;
+        seekPoint.firstExclusive = 0;
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
                       seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), isForward)),
                   IndexKeyEntry(key2, loc2));
@@ -555,7 +555,7 @@ TEST(SortedDataInterface, AdvanceToIndirect) {
         seekPoint.prefixLen = 0;
         BSONElement suffix0;
         seekPoint.keySuffix = {&suffix0};
-        seekPoint.suffixInclusive = {true};
+        seekPoint.firstExclusive = -1;
 
         suffix0 = key2.firstElement();
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
@@ -612,7 +612,7 @@ TEST(SortedDataInterface, AdvanceToIndirectReversed) {
         seekPoint.prefixLen = 0;
         BSONElement suffix0;
         seekPoint.keySuffix = {&suffix0};
-        seekPoint.suffixInclusive = {true};
+        seekPoint.firstExclusive = -1;
 
         suffix0 = key4.firstElement();
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
@@ -670,7 +670,7 @@ TEST(SortedDataInterface, AdvanceToIndirectExclusive) {
         seekPoint.prefixLen = 0;
         BSONElement suffix0;
         seekPoint.keySuffix = {&suffix0};
-        seekPoint.suffixInclusive = {false};
+        seekPoint.firstExclusive = 0;
 
         suffix0 = key2.firstElement();
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
@@ -738,7 +738,7 @@ TEST(SortedDataInterface, AdvanceToIndirectExclusiveReversed) {
         seekPoint.prefixLen = 0;
         BSONElement suffix0;
         seekPoint.keySuffix = {&suffix0};
-        seekPoint.suffixInclusive = {false};
+        seekPoint.firstExclusive = 0;
 
         suffix0 = key4.firstElement();
         ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
@@ -760,5 +760,323 @@ TEST(SortedDataInterface, AdvanceToIndirectExclusiveReversed) {
     }
 }
 
+// Insert multiple two-field keys and advance to each of them using a forward cursor by specifying
+// their exact key. When advanceTo() is called on a duplicate key, the cursor is positioned at the
+// first occurrence of that key in ascending order by RecordId.
+TEST(SortedDataInterface, AdvanceToCompoundWithPrefixAndSuffixInclusive) {
+    const auto harnessHelper(newSortedDataInterfaceHarnessHelper());
+    const std::unique_ptr<SortedDataInterface> sorted(
+        harnessHelper->newSortedDataInterface(/*unique=*/false, /*partial=*/false));
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        ASSERT(sorted->isEmpty(opCtx.get()));
+    }
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        {
+            WriteUnitOfWork uow(opCtx.get());
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey1a, loc1), true));
+            ASSERT_OK(sorted->insert(opCtx.get(),
+                                     makeKeyString(sorted.get(), compoundKey1a, loc2),
+                                     true /* allow duplicates */));
+            ASSERT_OK(sorted->insert(opCtx.get(),
+                                     makeKeyString(sorted.get(), compoundKey1a, loc3),
+                                     true /* allow duplicates */));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey2b, loc4), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey3b, loc5), true));
+            uow.commit();
+        }
+    }
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        ASSERT_EQUALS(5, sorted->numEntries(opCtx.get()));
+    }
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        const std::unique_ptr<SortedDataInterface::Cursor> cursor(sorted->newCursor(opCtx.get()));
+
+        ASSERT_EQ(cursor->seek(makeKeyStringForSeek(sorted.get(), compoundKey1a, true, true)),
+                  IndexKeyEntry(compoundKey1a, loc1));
+
+        IndexSeekPoint seekPoint;
+        seekPoint.keyPrefix = compoundKey1a;
+        seekPoint.prefixLen = 1;  // Get first field from the prefix
+        std::vector<BSONElement> suffix;
+        compoundKey1a.elems(suffix);
+        seekPoint.keySuffix = {&suffix[0], &suffix[1]};
+        seekPoint.firstExclusive = -1;  // Get second field from the suffix, no exclusive fields
+
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  IndexKeyEntry(compoundKey1a, loc1));
+
+        seekPoint.keyPrefix = compoundKey2b;
+        suffix.clear();
+        compoundKey2b.elems(suffix);
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  IndexKeyEntry(compoundKey2b, loc4));
+
+
+        seekPoint.keyPrefix = compoundKey3b;
+        suffix.clear();
+        compoundKey3b.elems(suffix);
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  IndexKeyEntry(compoundKey3b, loc5));
+
+        seekPoint.keyPrefix = compoundKey3c;
+        suffix.clear();
+        compoundKey3c.elems(suffix);
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  boost::none);
+    }
+}
+
+// Insert multiple two-field keys and advance to each of them using a forward cursor by specifying a
+// key that comes before. When advanceTo() is called in non-inclusive mode, the cursor is positioned
+// at the key that comes after the one specified. When dealing with prefixes, that means that any
+// keys that match on the prefix are skipped.
+TEST(SortedDataInterface, AdvanceToCompoundWithPrefixExclusive) {
+    const auto harnessHelper(newSortedDataInterfaceHarnessHelper());
+    const std::unique_ptr<SortedDataInterface> sorted(
+        harnessHelper->newSortedDataInterface(/*unique=*/false, /*partial=*/false));
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        ASSERT(sorted->isEmpty(opCtx.get()));
+    }
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        {
+            WriteUnitOfWork uow(opCtx.get());
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey1a, loc1), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey1b, loc2), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey1c, loc3), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey2b, loc4), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey3b, loc5), true));
+            uow.commit();
+        }
+    }
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        ASSERT_EQUALS(5, sorted->numEntries(opCtx.get()));
+    }
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        const std::unique_ptr<SortedDataInterface::Cursor> cursor(sorted->newCursor(opCtx.get()));
+
+        ASSERT_EQ(cursor->seek(makeKeyStringForSeek(sorted.get(), compoundKey1a, true, true)),
+                  IndexKeyEntry(compoundKey1a, loc1));
+
+        IndexSeekPoint seekPoint;
+        seekPoint.keyPrefix = compoundKey1a;
+        seekPoint.prefixLen = 1;  // Get first field from prefix
+        std::vector<BSONElement> suffix;
+        compoundKey1a.elems(suffix);
+        seekPoint.keySuffix = {&suffix[0], &suffix[1]};
+        seekPoint.firstExclusive = 0;  // Ignore the suffix, make prefix exclusive
+
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  IndexKeyEntry(compoundKey2b, loc4));
+
+        seekPoint.keyPrefix = compoundKey2b;
+        suffix.clear();
+        compoundKey2b.elems(suffix);
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  IndexKeyEntry(compoundKey3b, loc5));
+
+
+        seekPoint.keyPrefix = compoundKey3b;
+        suffix.clear();
+        compoundKey3b.elems(suffix);
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  boost::none);
+
+        seekPoint.keyPrefix = compoundKey3c;
+        suffix.clear();
+        compoundKey3c.elems(suffix);
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  boost::none);
+    }
+}
+
+// Insert multiple two-field keys and advance to each of them using a forward cursor by specifying a
+// key that comes before. When advanceTo() is called in non-inclusive mode, the cursor is positioned
+// at the key that comes after the one specified.
+TEST(SortedDataInterface, AdvanceToCompoundWithPrefixAndSuffixExclusive) {
+    const auto harnessHelper(newSortedDataInterfaceHarnessHelper());
+    const std::unique_ptr<SortedDataInterface> sorted(
+        harnessHelper->newSortedDataInterface(/*unique=*/false, /*partial=*/false));
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        ASSERT(sorted->isEmpty(opCtx.get()));
+    }
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        {
+            WriteUnitOfWork uow(opCtx.get());
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey1a, loc1), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey1b, loc2), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey1c, loc3), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey2b, loc4), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey3b, loc5), true));
+            uow.commit();
+        }
+    }
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        ASSERT_EQUALS(5, sorted->numEntries(opCtx.get()));
+    }
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        const std::unique_ptr<SortedDataInterface::Cursor> cursor(sorted->newCursor(opCtx.get()));
+
+        ASSERT_EQ(cursor->seek(makeKeyStringForSeek(sorted.get(), compoundKey1a, true, true)),
+                  IndexKeyEntry(compoundKey1a, loc1));
+
+        IndexSeekPoint seekPoint;
+        seekPoint.keyPrefix = compoundKey1a;
+        seekPoint.prefixLen = 1;  // Get first field from the prefix
+        std::vector<BSONElement> suffix;
+        compoundKey1a.elems(suffix);
+        seekPoint.keySuffix = {&suffix[0], &suffix[1]};
+        seekPoint.firstExclusive = 1;  // Get second field from suffix, make it exclusive
+
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  IndexKeyEntry(compoundKey1b, loc2));
+
+        seekPoint.keyPrefix = compoundKey2b;
+        suffix.clear();
+        compoundKey2b.elems(suffix);
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  IndexKeyEntry(compoundKey3b, loc5));
+
+
+        seekPoint.keyPrefix = compoundKey3b;
+        suffix.clear();
+        compoundKey3b.elems(suffix);
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  boost::none);
+
+        seekPoint.keyPrefix = compoundKey3c;
+        suffix.clear();
+        compoundKey3c.elems(suffix);
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  boost::none);
+    }
+}
+
+// Insert multiple two-field keys and advance to each of them using a forward cursor by specifying a
+// key that comes before. When advanceTo() is called in non-inclusive mode, the cursor is positioned
+// at the key that comes after the one specified.
+TEST(SortedDataInterface, AdvanceToCompoundWithSuffixExclusive) {
+    const auto harnessHelper(newSortedDataInterfaceHarnessHelper());
+    const std::unique_ptr<SortedDataInterface> sorted(
+        harnessHelper->newSortedDataInterface(/*unique=*/false, /*partial=*/false));
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        ASSERT(sorted->isEmpty(opCtx.get()));
+    }
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        {
+            WriteUnitOfWork uow(opCtx.get());
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey1a, loc1), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey1b, loc2), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey1c, loc3), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey2b, loc4), true));
+            ASSERT_OK(sorted->insert(
+                opCtx.get(), makeKeyString(sorted.get(), compoundKey3b, loc5), true));
+            uow.commit();
+        }
+    }
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        ASSERT_EQUALS(5, sorted->numEntries(opCtx.get()));
+    }
+
+    {
+        const ServiceContext::UniqueOperationContext opCtx(harnessHelper->newOperationContext());
+        const std::unique_ptr<SortedDataInterface::Cursor> cursor(sorted->newCursor(opCtx.get()));
+
+        ASSERT_EQ(cursor->seek(makeKeyStringForSeek(sorted.get(), compoundKey1a, true, true)),
+                  IndexKeyEntry(compoundKey1a, loc1));
+
+        IndexSeekPoint seekPoint;
+        seekPoint.keyPrefix = compoundKey1a;
+        seekPoint.prefixLen = 0;  // Ignore the prefix
+        std::vector<BSONElement> suffix;
+        compoundKey1a.elems(suffix);
+        seekPoint.keySuffix = {&suffix[0], &suffix[1]};
+        seekPoint.firstExclusive = 1;  // Get both fields from the suffix, make the second exclusive
+
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  IndexKeyEntry(compoundKey1b, loc2));
+
+        seekPoint.keyPrefix = compoundKey2b;
+        suffix.clear();
+        compoundKey2b.elems(suffix);
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  IndexKeyEntry(compoundKey3b, loc5));
+
+
+        seekPoint.keyPrefix = compoundKey3b;
+        suffix.clear();
+        compoundKey3b.elems(suffix);
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  boost::none);
+
+        seekPoint.keyPrefix = compoundKey3c;
+        suffix.clear();
+        compoundKey3c.elems(suffix);
+        ASSERT_EQ(cursor->seek(IndexEntryComparison::makeKeyStringFromSeekPointForSeek(
+                      seekPoint, sorted->getKeyStringVersion(), sorted->getOrdering(), true)),
+                  boost::none);
+    }
+}
 }  // namespace
 }  // namespace mongo