diff options
author | Dan Larkin-York <dan.larkin-york@mongodb.com> | 2022-04-01 13:08:35 +0000 |
---|---|---|
committer | Evergreen Agent <no-reply@evergreen.mongodb.com> | 2022-04-01 14:14:24 +0000 |
commit | 211be39f5e722bc7ccb9660fa622e33d44d0b30a (patch) | |
tree | 3e686402f84a73a7c542c3eb035527c2e07a981c /src/mongo/db/storage | |
parent | 4c7f60204736dea74792bcd85f4da816a2fa94cc (diff) | |
download | mongo-211be39f5e722bc7ccb9660fa622e33d44d0b30a.tar.gz |
SERVER-64830 Simplify exclusivity tracking in IndexSeekPoint
Diffstat (limited to 'src/mongo/db/storage')
-rw-r--r-- | src/mongo/db/storage/index_entry_comparison.cpp | 28 | ||||
-rw-r--r-- | src/mongo/db/storage/index_entry_comparison.h | 53 | ||||
-rw-r--r-- | src/mongo/db/storage/sorted_data_interface_test_cursor_advanceto.cpp | 350 |
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 |