SERVER-64830 Simplify exclusivity tracking in IndexSeekPoint

3 files changed, 362 insertions, 69 deletions

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