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 | |
parent | 4c7f60204736dea74792bcd85f4da816a2fa94cc (diff) | |
download | mongo-211be39f5e722bc7ccb9660fa622e33d44d0b30a.tar.gz |
SERVER-64830 Simplify exclusivity tracking in IndexSeekPoint
Diffstat (limited to 'src')
-rw-r--r-- | src/mongo/db/exec/distinct_scan.cpp | 2 | ||||
-rw-r--r-- | src/mongo/db/exec/sbe/size_estimator.cpp | 1 | ||||
-rw-r--r-- | src/mongo/db/query/index_bounds.cpp | 28 | ||||
-rw-r--r-- | src/mongo/db/query/index_bounds_test.cpp | 31 | ||||
-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 |
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 |