SERVER-48721 Support for $returnKey in SBE

5 files changed, 142 insertions, 26 deletions

diff --git a/src/mongo/db/exec/sbe/parser/parser.cpp b/src/mongo/db/exec/sbe/parser/parser.cpp
index 546d26c8c5f..1e410bbb176 100644
--- a/src/mongo/db/exec/sbe/parser/parser.cpp
+++ b/src/mongo/db/exec/sbe/parser/parser.cpp
@@ -86,7 +86,7 @@ static constexpr auto kSyntax = R"(
 
                 IXSCAN <- 'ixscan' IDENT? # optional variable name of the root object (record) delivered by the scan
                                    IDENT? # optional variable name of the record id delivered by the scan
-                                   IDENT_LIST_WITH_RENAMES  # list of projected fields (may be empty)
+                                   IX_KEY_LIST_WITH_RENAMES  # list of projected fields (may be empty)
                                    IDENT # collection name
                                    IDENT # index name to scan
                                    FORWARD_FLAG # forward scan or not
@@ -95,7 +95,7 @@ static constexpr auto kSyntax = R"(
                                    IDENT # variable name of the high key
                                    IDENT? # optional variable name of the root object (record) delivered by the scan
                                    IDENT? # optional variable name of the record id delivered by the scan
-                                   IDENT_LIST_WITH_RENAMES  # list of projected fields (may be empty)
+                                   IX_KEY_LIST_WITH_RENAMES  # list of projected fields (may be empty)
                                    IDENT # collection name
                                    IDENT # index name to scan
                                    FORWARD_FLAG # forward scan or not
@@ -207,6 +207,9 @@ static constexpr auto kSyntax = R"(
                 IDENT_LIST_WITH_RENAMES <- '[' (IDENT_WITH_RENAME (',' IDENT_WITH_RENAME)*)? ']'
                 IDENT_WITH_RENAME <- IDENT ('=' IDENT)?
 
+                IX_KEY_LIST_WITH_RENAMES <- '[' (IX_KEY_WITH_RENAME (',' IX_KEY_WITH_RENAME)*)? ']'
+                IX_KEY_WITH_RENAME <- IDENT '=' NUMBER
+
                 IDENT_LIST <- '[' (IDENT (',' IDENT)*)? ']'
                 IDENT <- RAW_IDENT/ESC_IDENT
 
@@ -223,6 +226,30 @@ static constexpr auto kSyntax = R"(
                 %word        <-  [a-z]+
         )";
 
+std::pair<IndexKeysInclusionSet, sbe::value::SlotVector> Parser::lookupIndexKeyRenames(
+    const std::vector<std::string>& renames, const std::vector<size_t>& indexKeys) {
+    IndexKeysInclusionSet indexKeysInclusion;
+
+    // Each indexKey is associated with the parallel remap from the 'renames' vector. This
+    // map explicitly binds each indexKey with its remap and sorts them by 'indexKey' order.
+    stdx::unordered_map<int, sbe::value::SlotId> slotsByKeyIndex;
+    invariant(renames.size() == indexKeys.size());
+    for (size_t idx = 0; idx < renames.size(); idx++) {
+        uassert(4872100,
+                str::stream() << "Cannot project index key at position " << indexKeys[idx],
+                indexKeys[idx] < indexKeysInclusion.size());
+        slotsByKeyIndex[indexKeys[idx]] = lookupSlotStrict(renames[idx]);
+    }
+
+    sbe::value::SlotVector slots;
+    for (auto&& [indexKey, slot] : slotsByKeyIndex) {
+        indexKeysInclusion.set(indexKey);
+        slots.push_back(slot);
+    }
+
+    return {indexKeysInclusion, std::move(slots)};
+}
+
 void Parser::walkChildren(AstQuery& ast) {
     for (const auto& node : ast.nodes) {
         walk(*node);
@@ -271,6 +298,24 @@ void Parser::walkIdentListWithRename(AstQuery& ast) {
     }
 }
 
+void Parser::walkIxKeyWithRename(AstQuery& ast) {
+    walkChildren(ast);
+
+    ast.rename = ast.nodes[0]->identifier;
+
+    // This token cannot be negative, because the parser does not accept a "-" prefix.
+    ast.indexKey = static_cast<size_t>(std::stoi(ast.nodes[1]->token));
+}
+
+void Parser::walkIxKeyListWithRename(AstQuery& ast) {
+    walkChildren(ast);
+
+    for (auto& node : ast.nodes) {
+        ast.indexKeys.emplace_back(std::move(node->indexKey));
+        ast.renames.emplace_back(std::move(node->rename));
+    }
+}
+
 void Parser::walkProjectList(AstQuery& ast) {
     walkChildren(ast);
 
@@ -625,13 +670,16 @@ void Parser::walkIndexScan(AstQuery& ast) {
         collection ? NamespaceStringOrUUID{dbName, collection->uuid()} : nssColl;
     const auto forward = (ast.nodes[forwardPos]->token == "true") ? true : false;
 
+    auto [indexKeysInclusion, vars] =
+        lookupIndexKeyRenames(ast.nodes[projectsPos]->renames, ast.nodes[projectsPos]->indexKeys);
+
     ast.stage = makeS<IndexScanStage>(name,
                                       indexName,
                                       forward,
                                       lookupSlot(recordName),
                                       lookupSlot(recordIdName),
-                                      ast.nodes[projectsPos]->identifiers,
-                                      lookupSlots(ast.nodes[projectsPos]->renames),
+                                      indexKeysInclusion,
+                                      vars,
                                       boost::none,
                                       boost::none,
                                       nullptr,
@@ -678,13 +726,16 @@ void Parser::walkIndexSeek(AstQuery& ast) {
         collection ? NamespaceStringOrUUID{dbName, collection->uuid()} : nssColl;
     const auto forward = (ast.nodes[forwardPos]->token == "true") ? true : false;
 
+    auto [indexKeysInclusion, vars] =
+        lookupIndexKeyRenames(ast.nodes[projectsPos]->renames, ast.nodes[projectsPos]->indexKeys);
+
     ast.stage = makeS<IndexScanStage>(name,
                                       indexName,
                                       forward,
                                       lookupSlot(recordName),
                                       lookupSlot(recordIdName),
-                                      ast.nodes[projectsPos]->identifiers,
-                                      lookupSlots(ast.nodes[projectsPos]->renames),
+                                      indexKeysInclusion,
+                                      vars,
                                       lookupSlot(ast.nodes[0]->identifier),
                                       lookupSlot(ast.nodes[1]->identifier),
                                       nullptr,
@@ -1339,6 +1390,12 @@ void Parser::walk(AstQuery& ast) {
         case "IDENT_LIST_WITH_RENAMES"_:
             walkIdentListWithRename(ast);
             break;
+        case "IX_KEY_WITH_RENAME"_:
+            walkIxKeyWithRename(ast);
+            break;
+        case "IX_KEY_LIST_WITH_RENAMES"_:
+            walkIxKeyListWithRename(ast);
+            break;
         case "PROJECT_LIST"_:
             walkProjectList(ast);
             break;
diff --git a/src/mongo/db/exec/sbe/parser/parser.h b/src/mongo/db/exec/sbe/parser/parser.h
index 9d17c7deb17..87e5b04be7f 100644
--- a/src/mongo/db/exec/sbe/parser/parser.h
+++ b/src/mongo/db/exec/sbe/parser/parser.h
@@ -33,6 +33,7 @@
 #include <third_party/peglib/peglib.h>
 
 #include "mongo/db/exec/sbe/expressions/expression.h"
+#include "mongo/db/exec/sbe/stages/ix_scan.h"
 #include "mongo/db/exec/sbe/stages/spool.h"
 #include "mongo/db/exec/sbe/stages/stages.h"
 #include "mongo/db/exec/sbe/values/id_generators.h"
@@ -42,8 +43,10 @@ namespace mongo {
 namespace sbe {
 struct ParsedQueryTree {
     std::string identifier;
+    size_t indexKey;
     std::string rename;
     std::vector<std::string> identifiers;
+    std::vector<size_t> indexKeys;
     std::vector<std::string> renames;
 
     std::unique_ptr<PlanStage> stage;
@@ -153,6 +156,9 @@ private:
         return result;
     }
 
+    std::pair<IndexKeysInclusionSet, sbe::value::SlotVector> lookupIndexKeyRenames(
+        const std::vector<std::string>& renames, const std::vector<size_t>& indexKeys);
+
     SpoolId lookupSpoolBuffer(const std::string& name) {
         if (_spoolBuffersLookupTable.find(name) == _spoolBuffersLookupTable.end()) {
             _spoolBuffersLookupTable[name] = _spoolIdGenerator.generate();
@@ -165,6 +171,8 @@ private:
     void walkIdentList(AstQuery& ast);
     void walkIdentWithRename(AstQuery& ast);
     void walkIdentListWithRename(AstQuery& ast);
+    void walkIxKeyWithRename(AstQuery& ast);
+    void walkIxKeyListWithRename(AstQuery& ast);
 
     void walkProjectList(AstQuery& ast);
     void walkAssign(AstQuery& ast);
diff --git a/src/mongo/db/exec/sbe/stages/ix_scan.cpp b/src/mongo/db/exec/sbe/stages/ix_scan.cpp
index 9e3cdb21d44..f26dd1dbadb 100644
--- a/src/mongo/db/exec/sbe/stages/ix_scan.cpp
+++ b/src/mongo/db/exec/sbe/stages/ix_scan.cpp
@@ -33,6 +33,7 @@
 
 #include "mongo/db/catalog/index_catalog.h"
 #include "mongo/db/exec/sbe/expressions/expression.h"
+#include "mongo/db/exec/sbe/values/bson.h"
 #include "mongo/db/index/index_access_method.h"
 
 namespace mongo::sbe {
@@ -41,7 +42,7 @@ IndexScanStage::IndexScanStage(const NamespaceStringOrUUID& name,
                                bool forward,
                                boost::optional<value::SlotId> recordSlot,
                                boost::optional<value::SlotId> recordIdSlot,
-                               std::vector<std::string> fields,
+                               IndexKeysInclusionSet indexKeysToInclude,
                                value::SlotVector vars,
                                boost::optional<value::SlotId> seekKeySlotLow,
                                boost::optional<value::SlotId> seekKeySlotHi,
@@ -53,15 +54,16 @@ IndexScanStage::IndexScanStage(const NamespaceStringOrUUID& name,
       _forward(forward),
       _recordSlot(recordSlot),
       _recordIdSlot(recordIdSlot),
-      _fields(std::move(fields)),
+      _indexKeysToInclude(indexKeysToInclude),
       _vars(std::move(vars)),
       _seekKeySlotLow(seekKeySlotLow),
       _seekKeySlotHi(seekKeySlotHi),
       _tracker(tracker) {
-    invariant(_fields.size() == _vars.size());
     // The valid state is when both boundaries, or none is set, or only low key is set.
     invariant((_seekKeySlotLow && _seekKeySlotHi) || (!_seekKeySlotLow && !_seekKeySlotHi) ||
               (_seekKeySlotLow && !_seekKeySlotHi));
+
+    invariant(_indexKeysToInclude.count() == _vars.size());
 }
 
 std::unique_ptr<PlanStage> IndexScanStage::clone() const {
@@ -70,7 +72,7 @@ std::unique_ptr<PlanStage> IndexScanStage::clone() const {
                                             _forward,
                                             _recordSlot,
                                             _recordIdSlot,
-                                            _fields,
+                                            _indexKeysToInclude,
                                             _vars,
                                             _seekKeySlotLow,
                                             _seekKeySlotHi,
@@ -87,12 +89,10 @@ void IndexScanStage::prepare(CompileCtx& ctx) {
         _recordIdAccessor = std::make_unique<value::ViewOfValueAccessor>();
     }
 
-    for (size_t idx = 0; idx < _fields.size(); ++idx) {
-        auto [it, inserted] =
-            _fieldAccessors.emplace(_fields[idx], std::make_unique<value::ViewOfValueAccessor>());
-        uassert(4822821, str::stream() << "duplicate field: " << _fields[idx], inserted);
-        auto [itRename, insertedRename] = _varAccessors.emplace(_vars[idx], it->second.get());
-        uassert(4822822, str::stream() << "duplicate field: " << _vars[idx], insertedRename);
+    _accessors.resize(_vars.size());
+    for (size_t idx = 0; idx < _accessors.size(); ++idx) {
+        auto [it, inserted] = _accessorMap.emplace(_vars[idx], &_accessors[idx]);
+        uassert(4822821, str::stream() << "duplicate slot: " << _vars[idx], inserted);
     }
 
     if (_seekKeySlotLow) {
@@ -112,7 +112,7 @@ value::SlotAccessor* IndexScanStage::getAccessor(CompileCtx& ctx, value::SlotId
         return _recordIdAccessor.get();
     }
 
-    if (auto it = _varAccessors.find(slot); it != _varAccessors.end()) {
+    if (auto it = _accessorMap.find(slot); it != _accessorMap.end()) {
         return it->second;
     }
 
@@ -206,6 +206,10 @@ void IndexScanStage::open(bool reOpen) {
                 _seekKeyLow = &_startPoint;
                 _seekKeyHi = nullptr;
             }
+
+            // TODO SERVER-49385: When the 'prepare()' phase takes the collection lock, it will be
+            // possible to intialize '_ordering' there instead of here.
+            _ordering = entry->ordering();
         } else {
             _cursor.reset();
         }
@@ -256,6 +260,12 @@ PlanState IndexScanStage::getNext() {
                                  value::bitcastFrom<int64_t>(_nextRecord->loc.repr()));
     }
 
+    if (_accessors.size()) {
+        _valuesBuffer.reset();
+        readKeyStringValueIntoAccessors(
+            _nextRecord->keyString, *_ordering, &_valuesBuffer, &_accessors, _indexKeysToInclude);
+    }
+
     if (_tracker && _tracker->trackProgress<TrialRunProgressTracker::kNumReads>(1)) {
         // If we're collecting execution stats during multi-planning and reached the end of the
         // trial period (trackProgress() will return 'true' in this case), then we can reset the
@@ -308,14 +318,18 @@ std::vector<DebugPrinter::Block> IndexScanStage::debugPrint() const {
     }
 
     ret.emplace_back(DebugPrinter::Block("[`"));
-    for (size_t idx = 0; idx < _fields.size(); ++idx) {
-        if (idx) {
+    size_t varIndex = 0;
+    for (size_t keyIndex = 0; keyIndex < _indexKeysToInclude.size(); ++keyIndex) {
+        if (!_indexKeysToInclude[keyIndex]) {
+            continue;
+        }
+        if (varIndex) {
             ret.emplace_back(DebugPrinter::Block("`,"));
         }
-
-        DebugPrinter::addIdentifier(ret, _vars[idx]);
+        invariant(varIndex < _vars.size());
+        DebugPrinter::addIdentifier(ret, _vars[varIndex++]);
         ret.emplace_back("=");
-        DebugPrinter::addIdentifier(ret, _fields[idx]);
+        ret.emplace_back(std::to_string(keyIndex));
     }
     ret.emplace_back(DebugPrinter::Block("`]"));
 
diff --git a/src/mongo/db/exec/sbe/stages/ix_scan.h b/src/mongo/db/exec/sbe/stages/ix_scan.h
index a3d23b2bb82..fcecc127ddd 100644
--- a/src/mongo/db/exec/sbe/stages/ix_scan.h
+++ b/src/mongo/db/exec/sbe/stages/ix_scan.h
@@ -29,6 +29,7 @@
 
 #pragma once
 
+#include "mongo/bson/ordering.h"
 #include "mongo/db/db_raii.h"
 #include "mongo/db/exec/sbe/stages/stages.h"
 #include "mongo/db/exec/trial_run_progress_tracker.h"
@@ -36,6 +37,27 @@
 #include "mongo/db/storage/sorted_data_interface.h"
 
 namespace mongo::sbe {
+
+/**
+ * A stage that iterates the entries of a collection index, starting from a bound specified by the
+ * value in 'seekKeySlotLow' and ending (via IS_EOF) with the 'seekKeySlotHi' bound. (An unspecified
+ * 'seekKeySlowHi' scans to the end of the index. Leaving both bounds unspecified scans the index
+ * from beginning to end.)
+ *
+ * The input 'seekKeySlotLow' and 'seekKeySlotHi' slots get read as part of the open (or re-open)
+ * call. A common use case for an IndexScanStage is to place it as the inner child of LoopJoinStage.
+ * The outer side of the LoopJoinStage determines the bounds, and the inner IndexScanStage iterates
+ * through all the entries within those bounds.
+ *
+ * The "output" slots are
+ *   - 'recordSlot': the "KeyString" representing the index entry,
+ *   - 'recordIdSlot': a reference that can be used to fetch the entire document, and
+ *   - 'vars': one slot for each value in the index key that should be "projected" out of the entry.
+ *
+ * The 'indexKeysToInclude' bitset determines which values are included in the projection based
+ * on their order in the index pattern. The number of bits set in 'indexKeysToInclude' must be
+ * the same as the number of slots in the 'vars' SlotVector.
+ */
 class IndexScanStage final : public PlanStage {
 public:
     IndexScanStage(const NamespaceStringOrUUID& name,
@@ -43,7 +65,7 @@ public:
                    bool forward,
                    boost::optional<value::SlotId> recordSlot,
                    boost::optional<value::SlotId> recordIdSlot,
-                   std::vector<std::string> fields,
+                   IndexKeysInclusionSet indexKeysToInclude,
                    value::SlotVector vars,
                    boost::optional<value::SlotId> seekKeySlotLow,
                    boost::optional<value::SlotId> seekKeySlotHi,
@@ -74,7 +96,7 @@ private:
     const bool _forward;
     const boost::optional<value::SlotId> _recordSlot;
     const boost::optional<value::SlotId> _recordIdSlot;
-    const std::vector<std::string> _fields;
+    const IndexKeysInclusionSet _indexKeysToInclude;
     const value::SlotVector _vars;
     const boost::optional<value::SlotId> _seekKeySlotLow;
     const boost::optional<value::SlotId> _seekKeySlotHi;
@@ -82,8 +104,10 @@ private:
     std::unique_ptr<value::ViewOfValueAccessor> _recordAccessor;
     std::unique_ptr<value::ViewOfValueAccessor> _recordIdAccessor;
 
-    value::FieldAccessorMap _fieldAccessors;
-    value::SlotAccessorMap _varAccessors;
+    // One accessor and slot for each key component that this stage will bind from an index entry's
+    // KeyString. The accessors are in the same order as the key components they bind to.
+    std::vector<value::ViewOfValueAccessor> _accessors;
+    value::SlotAccessorMap _accessorMap;
 
     value::SlotAccessor* _seekKeyLowAccessor{nullptr};
     value::SlotAccessor* _seekKeyHiAccessor{nullptr};
@@ -94,9 +118,14 @@ private:
 
     std::unique_ptr<SortedDataInterface::Cursor> _cursor;
     std::weak_ptr<const IndexCatalogEntry> _weakIndexCatalogEntry;
+    boost::optional<Ordering> _ordering{boost::none};
     boost::optional<AutoGetCollectionForRead> _coll;
     boost::optional<KeyStringEntry> _nextRecord;
 
+    // This buffer stores values that are projected out of the index entry. Values in the
+    // '_accessors' list that are pointers point to data in this buffer.
+    BufBuilder _valuesBuffer;
+
     bool _open{false};
     bool _firstGetNext{true};
     IndexScanStats _specificStats;
diff --git a/src/mongo/db/exec/sbe/values/id_generators.h b/src/mongo/db/exec/sbe/values/id_generators.h
index fc7fa93f840..4b3fae32cca 100644
--- a/src/mongo/db/exec/sbe/values/id_generators.h
+++ b/src/mongo/db/exec/sbe/values/id_generators.h
@@ -67,6 +67,14 @@ public:
     T generate() {
         return this->generateByIncrementing();
     }
+
+    auto generateMultiple(size_t num) {
+        std::vector<T> idVector(num);
+        for (T& id : idVector) {
+            id = generate();
+        }
+        return idVector;
+    }
 };
 
 using SlotIdGenerator = IdGenerator<value::SlotId>;