summaryrefslogtreecommitdiff
path: root/src/mongo/db/pipeline/abt
diff options
context:
space:
mode:
Diffstat (limited to 'src/mongo/db/pipeline/abt')
-rw-r--r--src/mongo/db/pipeline/abt/abt_translate_bm_fixture.cpp211
-rw-r--r--src/mongo/db/pipeline/abt/abt_translate_bm_fixture.h137
-rw-r--r--src/mongo/db/pipeline/abt/abt_translate_cq_bm.cpp88
-rw-r--r--src/mongo/db/pipeline/abt/abt_translate_pipeline_bm.cpp90
-rw-r--r--src/mongo/db/pipeline/abt/expr_algebrizer_context.h34
-rw-r--r--src/mongo/db/pipeline/abt/match_expression_visitor.cpp80
-rw-r--r--src/mongo/db/pipeline/abt/utils.cpp35
-rw-r--r--src/mongo/db/pipeline/abt/utils.h10
8 files changed, 632 insertions, 53 deletions
diff --git a/src/mongo/db/pipeline/abt/abt_translate_bm_fixture.cpp b/src/mongo/db/pipeline/abt/abt_translate_bm_fixture.cpp
new file mode 100644
index 00000000000..6b00208dbbd
--- /dev/null
+++ b/src/mongo/db/pipeline/abt/abt_translate_bm_fixture.cpp
@@ -0,0 +1,211 @@
+/**
+ * Copyright (C) 2022-present MongoDB, Inc.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the Server Side Public License, version 1,
+ * as published by MongoDB, Inc.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * Server Side Public License for more details.
+ *
+ * You should have received a copy of the Server Side Public License
+ * along with this program. If not, see
+ * <http://www.mongodb.com/licensing/server-side-public-license>.
+ *
+ * As a special exception, the copyright holders give permission to link the
+ * code of portions of this program with the OpenSSL library under certain
+ * conditions as described in each individual source file and distribute
+ * linked combinations including the program with the OpenSSL library. You
+ * must comply with the Server Side Public License in all respects for
+ * all of the code used other than as permitted herein. If you modify file(s)
+ * with this exception, you may extend this exception to your version of the
+ * file(s), but you are not obligated to do so. If you do not wish to do so,
+ * delete this exception statement from your version. If you delete this
+ * exception statement from all source files in the program, then also delete
+ * it in the license file.
+ */
+
+#include "mongo/db/pipeline/abt/abt_translate_bm_fixture.h"
+
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/db/json.h"
+
+namespace mongo {
+namespace {
+BSONArray buildArray(int size) {
+ BSONArrayBuilder builder;
+ for (int i = 0; i < size; i++) {
+ builder.append(i);
+ }
+ return builder.arr();
+}
+
+std::string getField(int index) {
+ static constexpr StringData kViableChars = "abcdefghijklmnopqrstuvwxyz"_sd;
+ invariant(size_t(index) < kViableChars.size());
+ return std::string(1, kViableChars[index]);
+}
+
+BSONObj buildSimpleBSONSpec(int nFields, bool isMatch, bool isExclusion = false) {
+ BSONObjBuilder spec;
+ for (auto i = 0; i < nFields; i++) {
+ int val = isMatch ? i : (isExclusion ? 0 : 1);
+ spec.append(getField(i), val);
+ }
+ return spec.obj();
+}
+
+/**
+ * Builds a filter BSON with 'nFields' simple equality predicates.
+ */
+BSONObj buildSimpleMatchSpec(int nFields) {
+ return buildSimpleBSONSpec(nFields, true /*isMatch*/);
+}
+
+/**
+ * Builds a projection BSON with 'nFields' simple inclusions or exclusions, depending on the
+ * 'isExclusion' parameter.
+ */
+BSONObj buildSimpleProjectSpec(int nFields, bool isExclusion) {
+ return buildSimpleBSONSpec(nFields, false /*isMatch*/, isExclusion);
+}
+
+BSONObj buildNestedBSONSpec(int depth, bool isExclusion, int offset) {
+ std::string field;
+ for (auto i = 0; i < depth - 1; i++) {
+ field += getField(offset + i) += ".";
+ }
+ field += getField(offset + depth);
+
+ return BSON(field << (isExclusion ? 0 : 1));
+}
+
+/**
+ * Builds a BSON representing a predicate on one dotted path, where the field has depth 'depth'.
+ */
+BSONObj buildNestedMatchSpec(int depth, int offset = 0) {
+ return buildNestedBSONSpec(depth, false /*isExclusion*/, offset);
+}
+
+/**
+ * Builds a BSON representing a projection on one dotted path, where the field has depth 'depth'.
+ */
+BSONObj buildNestedProjectSpec(int depth, bool isExclusion, int offset = 0) {
+ return buildNestedBSONSpec(depth, isExclusion, offset);
+}
+} // namespace
+
+void ABTTranslateBenchmarkFixture::benchmarkMatch(benchmark::State& state) {
+ auto match = buildSimpleMatchSpec(1);
+ benchmarkABTTranslate(state, match, BSONObj());
+}
+void ABTTranslateBenchmarkFixture::benchmarkMatchTwoFields(benchmark::State& state) {
+ auto match = buildSimpleMatchSpec(2);
+ benchmarkABTTranslate(state, match, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkMatchTwentyFields(benchmark::State& state) {
+ auto match = buildSimpleMatchSpec(20);
+ benchmarkABTTranslate(state, match, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkMatchDepthTwo(benchmark::State& state) {
+ auto match = buildNestedMatchSpec(2);
+ benchmarkABTTranslate(state, match, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkMatchDepthTwenty(benchmark::State& state) {
+ auto match = buildNestedMatchSpec(20);
+ benchmarkABTTranslate(state, match, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkMatchGtLt(benchmark::State& state) {
+ auto match = fromjson("{a: {$gt: -12, $lt: 5}}");
+ benchmarkABTTranslate(state, match, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkMatchIn(benchmark::State& state) {
+ auto match = BSON("a" << BSON("$in" << buildArray(10)));
+ benchmarkABTTranslate(state, match, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkMatchInLarge(benchmark::State& state) {
+ auto match = BSON("a" << BSON("$in" << buildArray(1000)));
+ benchmarkABTTranslate(state, match, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkMatchElemMatch(benchmark::State& state) {
+ auto match = fromjson("{a: {$elemMatch: {b: {$eq: 2}, c: {$lt: 3}}}}");
+ benchmarkABTTranslate(state, match, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkMatchComplex(benchmark::State& state) {
+ auto match = fromjson(
+ "{$and: ["
+ "{'a.b': {$not: {$eq: 2}}},"
+ "{'b.c': {$lte: {$eq: 'str'}}},"
+ "{$or: [{'c.d' : {$eq: 3}}, {'d.e': {$eq: 4}}]},"
+ "{$or: ["
+ "{'e.f': {$gt: 4}},"
+ "{$and: ["
+ "{'f.g': {$not: {$eq: 1}}},"
+ "{'g.h': {$eq: 3}}"
+ "]}"
+ "]}"
+ "]}}");
+ benchmarkABTTranslate(state, match, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkProjectExclude(benchmark::State& state) {
+ auto project = buildSimpleProjectSpec(1, true /*isExclusion*/);
+ benchmarkABTTranslate(state, project, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkProjectInclude(benchmark::State& state) {
+ auto project = buildSimpleProjectSpec(1, false /*isExclusion*/);
+ benchmarkABTTranslate(state, project, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkProjectIncludeTwoFields(benchmark::State& state) {
+ auto project = buildSimpleProjectSpec(2, false /*isExclusion*/);
+ benchmarkABTTranslate(state, project, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkProjectIncludeTwentyFields(benchmark::State& state) {
+ auto project = buildSimpleProjectSpec(20, false /*isExclusion*/);
+ benchmarkABTTranslate(state, project, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkProjectIncludeDepthTwo(benchmark::State& state) {
+ auto project = buildNestedProjectSpec(2, false /*isExclusion*/);
+ benchmarkABTTranslate(state, project, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkProjectIncludeDepthTwenty(benchmark::State& state) {
+ auto project = buildNestedProjectSpec(20, false /*isExclusion*/);
+ benchmarkABTTranslate(state, project, BSONObj());
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkTwoStages(benchmark::State& state) {
+ // Builds a match on a nested field and then excludes that nested field.
+ std::vector<BSONObj> pipeline;
+ pipeline.push_back(BSON("$match" << buildNestedMatchSpec(3)));
+ pipeline.push_back(BSON("$project" << buildNestedProjectSpec(3, true /*isExclusion*/)));
+ benchmarkABTTranslate(state, pipeline);
+}
+
+void ABTTranslateBenchmarkFixture::benchmarkTwentyStages(benchmark::State& state) {
+ // Builds a sequence of alternating $match and $project stages which match on a nested field and
+ // then exclude that field.
+ std::vector<BSONObj> pipeline;
+ for (int i = 0; i < 10; i++) {
+ pipeline.push_back(BSON("$match" << buildNestedMatchSpec(3, i)));
+ pipeline.push_back(BSON("$project" << buildNestedProjectSpec(3, true /*exclusion*/, i)));
+ }
+ benchmarkABTTranslate(state, pipeline);
+}
+
+
+} // namespace mongo
diff --git a/src/mongo/db/pipeline/abt/abt_translate_bm_fixture.h b/src/mongo/db/pipeline/abt/abt_translate_bm_fixture.h
new file mode 100644
index 00000000000..0ab40ed52fe
--- /dev/null
+++ b/src/mongo/db/pipeline/abt/abt_translate_bm_fixture.h
@@ -0,0 +1,137 @@
+/**
+ * Copyright (C) 2022-present MongoDB, Inc.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the Server Side Public License, version 1,
+ * as published by MongoDB, Inc.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * Server Side Public License for more details.
+ *
+ * You should have received a copy of the Server Side Public License
+ * along with this program. If not, see
+ * <http://www.mongodb.com/licensing/server-side-public-license>.
+ *
+ * As a special exception, the copyright holders give permission to link the
+ * code of portions of this program with the OpenSSL library under certain
+ * conditions as described in each individual source file and distribute
+ * linked combinations including the program with the OpenSSL library. You
+ * must comply with the Server Side Public License in all respects for
+ * all of the code used other than as permitted herein. If you modify file(s)
+ * with this exception, you may extend this exception to your version of the
+ * file(s), but you are not obligated to do so. If you do not wish to do so,
+ * delete this exception statement from your version. If you delete this
+ * exception statement from all source files in the program, then also delete
+ * it in the license file.
+ */
+
+#pragma once
+
+#include "mongo/platform/basic.h"
+
+#include <benchmark/benchmark.h>
+
+#include "mongo/bson/bsonobj.h"
+
+namespace mongo {
+
+class ABTTranslateBenchmarkFixture : public benchmark::Fixture {
+public:
+ virtual void benchmarkABTTranslate(benchmark::State& state,
+ BSONObj matchSpec,
+ BSONObj projectSpec) = 0;
+ virtual void benchmarkABTTranslate(benchmark::State& state,
+ const std::vector<BSONObj>& pipeline) = 0;
+
+ void benchmarkMatch(benchmark::State& state);
+ void benchmarkMatchTwoFields(benchmark::State& state);
+ void benchmarkMatchTwentyFields(benchmark::State& state);
+
+ void benchmarkMatchDepthTwo(benchmark::State& state);
+ void benchmarkMatchDepthTwenty(benchmark::State& state);
+
+ void benchmarkMatchGtLt(benchmark::State& state);
+ void benchmarkMatchIn(benchmark::State& state);
+ void benchmarkMatchInLarge(benchmark::State& state);
+ void benchmarkMatchElemMatch(benchmark::State& state);
+ void benchmarkMatchComplex(benchmark::State& state);
+
+ void benchmarkProjectExclude(benchmark::State& state);
+ void benchmarkProjectInclude(benchmark::State& state);
+ void benchmarkProjectIncludeTwoFields(benchmark::State& state);
+ void benchmarkProjectIncludeTwentyFields(benchmark::State& state);
+
+ void benchmarkProjectIncludeDepthTwo(benchmark::State& state);
+ void benchmarkProjectIncludeDepthTwenty(benchmark::State& state);
+
+ void benchmarkTwoStages(benchmark::State& state);
+ void benchmarkTwentyStages(benchmark::State& state);
+};
+
+// These benchmarks cover some simple queries which are currently CQF-eligible. As more support
+// is added to CQF, more benchmarks may be added here as needed.
+#define BENCHMARK_MQL_TRANSLATION(Fixture) \
+ \
+ BENCHMARK_F(Fixture, Match)(benchmark::State & state) { \
+ benchmarkMatch(state); \
+ } \
+ BENCHMARK_F(Fixture, MatchTwoFields)(benchmark::State & state) { \
+ benchmarkMatchTwoFields(state); \
+ } \
+ BENCHMARK_F(Fixture, MatchTwentyFields)(benchmark::State & state) { \
+ benchmarkMatchTwentyFields(state); \
+ } \
+ BENCHMARK_F(Fixture, MatchDepthTwo)(benchmark::State & state) { \
+ benchmarkMatchDepthTwo(state); \
+ } \
+ BENCHMARK_F(Fixture, MatchDepthTwenty)(benchmark::State & state) { \
+ benchmarkMatchDepthTwenty(state); \
+ } \
+ BENCHMARK_F(Fixture, MatchGtLt)(benchmark::State & state) { \
+ benchmarkMatchGtLt(state); \
+ } \
+ BENCHMARK_F(Fixture, MatchIn)(benchmark::State & state) { \
+ benchmarkMatchIn(state); \
+ } \
+ BENCHMARK_F(Fixture, MatchInLarge)(benchmark::State & state) { \
+ benchmarkMatchInLarge(state); \
+ } \
+ BENCHMARK_F(Fixture, MatchElemMatch)(benchmark::State & state) { \
+ benchmarkMatchElemMatch(state); \
+ } \
+ BENCHMARK_F(Fixture, MatchComplex)(benchmark::State & state) { \
+ benchmarkMatchComplex(state); \
+ } \
+ BENCHMARK_F(Fixture, ProjectExclude)(benchmark::State & state) { \
+ benchmarkProjectExclude(state); \
+ } \
+ BENCHMARK_F(Fixture, ProjectInclude)(benchmark::State & state) { \
+ benchmarkProjectInclude(state); \
+ } \
+ BENCHMARK_F(Fixture, ProjectIncludeTwoFields)(benchmark::State & state) { \
+ benchmarkProjectIncludeTwoFields(state); \
+ } \
+ BENCHMARK_F(Fixture, ProjectIncludeTwentyFields)(benchmark::State & state) { \
+ benchmarkProjectIncludeTwentyFields(state); \
+ } \
+ BENCHMARK_F(Fixture, ProjectIncludeDepthTwo)(benchmark::State & state) { \
+ benchmarkProjectIncludeDepthTwo(state); \
+ } \
+ BENCHMARK_F(Fixture, ProjectIncludeDepthTwenty)(benchmark::State & state) { \
+ benchmarkProjectIncludeDepthTwenty(state); \
+ }
+
+// Queries which are expressed as pipelines should be added here because they cannot go through
+// find translation.
+#define BENCHMARK_MQL_PIPELINE_TRANSLATION(Fixture) \
+ \
+ BENCHMARK_F(Fixture, TwoStages)(benchmark::State & state) { \
+ benchmarkTwoStages(state); \
+ } \
+ BENCHMARK_F(Fixture, TwentyStages)(benchmark::State & state) { \
+ benchmarkTwentyStages(state); \
+ }
+
+} // namespace mongo
diff --git a/src/mongo/db/pipeline/abt/abt_translate_cq_bm.cpp b/src/mongo/db/pipeline/abt/abt_translate_cq_bm.cpp
new file mode 100644
index 00000000000..8603ea2d7c0
--- /dev/null
+++ b/src/mongo/db/pipeline/abt/abt_translate_cq_bm.cpp
@@ -0,0 +1,88 @@
+/**
+ * Copyright (C) 2022-present MongoDB, Inc.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the Server Side Public License, version 1,
+ * as published by MongoDB, Inc.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * Server Side Public License for more details.
+ *
+ * You should have received a copy of the Server Side Public License
+ * along with this program. If not, see
+ * <http://www.mongodb.com/licensing/server-side-public-license>.
+ *
+ * As a special exception, the copyright holders give permission to link the
+ * code of portions of this program with the OpenSSL library under certain
+ * conditions as described in each individual source file and distribute
+ * linked combinations including the program with the OpenSSL library. You
+ * must comply with the Server Side Public License in all respects for
+ * all of the code used other than as permitted herein. If you modify file(s)
+ * with this exception, you may extend this exception to your version of the
+ * file(s), but you are not obligated to do so. If you do not wish to do so,
+ * delete this exception statement from your version. If you delete this
+ * exception statement from all source files in the program, then also delete
+ * it in the license file.
+ */
+
+#include <benchmark/benchmark.h>
+
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/db/pipeline/abt/abt_translate_bm_fixture.h"
+#include "mongo/db/pipeline/abt/canonical_query_translation.h"
+#include "mongo/db/query/canonical_query.h"
+#include "mongo/db/query/query_test_service_context.h"
+
+namespace mongo::optimizer {
+namespace {
+/**
+ * Benchmarks translation from CanonicalQuery to ABT.
+ */
+class CanonicalQueryABTTranslate : public ABTTranslateBenchmarkFixture {
+public:
+ CanonicalQueryABTTranslate() {}
+
+ void benchmarkABTTranslate(benchmark::State& state,
+ const std::vector<BSONObj>& pipeline) override final {
+ state.SkipWithError("Find translation fixture cannot translate a pieline");
+ return;
+ }
+
+ void benchmarkABTTranslate(benchmark::State& state,
+ BSONObj matchSpec,
+ BSONObj projectSpec) override final {
+ QueryTestServiceContext testServiceContext;
+ auto opCtx = testServiceContext.makeOperationContext();
+ auto nss = NamespaceString("test.bm");
+
+ Metadata metadata{{}};
+ PrefixId prefixId;
+ std::string scanProjName = prefixId.getNextId("scan");
+
+ auto findCommand = std::make_unique<FindCommandRequest>(nss);
+ findCommand->setFilter(matchSpec);
+ findCommand->setProjection(projectSpec);
+ auto cq = CanonicalQuery::canonicalize(opCtx.get(), std::move(findCommand));
+ if (!cq.isOK()) {
+ state.SkipWithError("Canonical query could not be created");
+ return;
+ }
+
+ // This is where recording starts.
+ for (auto keepRunning : state) {
+ benchmark::DoNotOptimize(
+ translateCanonicalQueryToABT(metadata,
+ *cq.getValue(),
+ scanProjName,
+ make<ScanNode>(scanProjName, "collection"),
+ prefixId));
+ benchmark::ClobberMemory();
+ }
+ }
+};
+
+BENCHMARK_MQL_TRANSLATION(CanonicalQueryABTTranslate)
+} // namespace
+} // namespace mongo::optimizer
diff --git a/src/mongo/db/pipeline/abt/abt_translate_pipeline_bm.cpp b/src/mongo/db/pipeline/abt/abt_translate_pipeline_bm.cpp
new file mode 100644
index 00000000000..f878c494c13
--- /dev/null
+++ b/src/mongo/db/pipeline/abt/abt_translate_pipeline_bm.cpp
@@ -0,0 +1,90 @@
+/**
+ * Copyright (C) 2022-present MongoDB, Inc.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the Server Side Public License, version 1,
+ * as published by MongoDB, Inc.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * Server Side Public License for more details.
+ *
+ * You should have received a copy of the Server Side Public License
+ * along with this program. If not, see
+ * <http://www.mongodb.com/licensing/server-side-public-license>.
+ *
+ * As a special exception, the copyright holders give permission to link the
+ * code of portions of this program with the OpenSSL library under certain
+ * conditions as described in each individual source file and distribute
+ * linked combinations including the program with the OpenSSL library. You
+ * must comply with the Server Side Public License in all respects for
+ * all of the code used other than as permitted herein. If you modify file(s)
+ * with this exception, you may extend this exception to your version of the
+ * file(s), but you are not obligated to do so. If you do not wish to do so,
+ * delete this exception statement from your version. If you delete this
+ * exception statement from all source files in the program, then also delete
+ * it in the license file.
+ */
+
+#include <benchmark/benchmark.h>
+
+#include "mongo/bson/bsonobjbuilder.h"
+#include "mongo/db/pipeline/abt/abt_translate_bm_fixture.h"
+#include "mongo/db/pipeline/abt/document_source_visitor.h"
+#include "mongo/db/pipeline/expression_context_for_test.h"
+#include "mongo/db/query/query_test_service_context.h"
+
+namespace mongo::optimizer {
+namespace {
+/**
+ * Benchmarks translation from optimized Pipeline to ABT.
+ */
+class PipelineABTTranslateBenchmark : public ABTTranslateBenchmarkFixture {
+public:
+ PipelineABTTranslateBenchmark() {}
+
+ void benchmarkABTTranslate(benchmark::State& state,
+ BSONObj matchSpec,
+ BSONObj projectSpec) override final {
+ std::vector<BSONObj> pipeline;
+ if (!matchSpec.isEmpty()) {
+ pipeline.push_back(BSON("$match" << matchSpec));
+ }
+ if (!projectSpec.isEmpty()) {
+ pipeline.push_back(BSON("$project" << projectSpec));
+ }
+ benchmarkABTTranslate(state, pipeline);
+ }
+
+ void benchmarkABTTranslate(benchmark::State& state,
+ const std::vector<BSONObj>& pipeline) override final {
+ QueryTestServiceContext testServiceContext;
+ auto opCtx = testServiceContext.makeOperationContext();
+ auto expCtx = new ExpressionContextForTest(opCtx.get(), NamespaceString("test.bm"));
+
+ Metadata metadata{{}};
+ PrefixId prefixId;
+ std::string scanProjName = prefixId.getNextId("scan");
+
+ std::unique_ptr<Pipeline, PipelineDeleter> parsedPipeline =
+ Pipeline::parse(pipeline, expCtx);
+ parsedPipeline->optimizePipeline();
+
+ // This is where recording starts.
+ for (auto keepRunning : state) {
+ benchmark::DoNotOptimize(
+ translatePipelineToABT(metadata,
+ *parsedPipeline,
+ scanProjName,
+ make<ScanNode>(scanProjName, "collection"),
+ prefixId));
+ benchmark::ClobberMemory();
+ }
+ }
+};
+
+BENCHMARK_MQL_TRANSLATION(PipelineABTTranslateBenchmark)
+BENCHMARK_MQL_PIPELINE_TRANSLATION(PipelineABTTranslateBenchmark)
+} // namespace
+} // namespace mongo::optimizer
diff --git a/src/mongo/db/pipeline/abt/expr_algebrizer_context.h b/src/mongo/db/pipeline/abt/expr_algebrizer_context.h
index 7cbf740c2e2..7c852281078 100644
--- a/src/mongo/db/pipeline/abt/expr_algebrizer_context.h
+++ b/src/mongo/db/pipeline/abt/expr_algebrizer_context.h
@@ -31,6 +31,7 @@
#include <stack>
+#include "mongo/db/matcher/expression_path.h"
#include "mongo/db/query/optimizer/node.h"
#include "mongo/db/query/optimizer/utils/utils.h"
@@ -73,17 +74,37 @@ public:
*/
std::string getNextId(const std::string& key);
- void enterElemMatch() {
- _elemMatchCount++;
+ void enterElemMatch(const MatchExpression::MatchType matchType) {
+ _elemMatchStack.push_back(matchType);
}
void exitElemMatch() {
tassert(6809501, "Attempting to exit out of elemMatch that was not entered", inElemMatch());
- _elemMatchCount--;
+ _elemMatchStack.pop_back();
}
bool inElemMatch() {
- return _elemMatchCount > 0;
+ return !_elemMatchStack.empty();
+ }
+
+ /**
+ * Returns whether the current $elemMatch should consider its path for translation. This
+ * function assumes that 'enterElemMatch' has been called before visiting the current
+ * expression.
+ */
+ bool shouldGeneratePathForElemMatch() const {
+ return _elemMatchStack.size() == 1 ||
+ _elemMatchStack[_elemMatchStack.size() - 2] ==
+ MatchExpression::MatchType::ELEM_MATCH_OBJECT;
+ }
+
+ /**
+ * Returns true if the current expression should consider its path for translation based on
+ * whether it's contained within an ElemMatchObjectExpression.
+ */
+ bool shouldGeneratePath() const {
+ return _elemMatchStack.empty() ||
+ _elemMatchStack.back() == MatchExpression::MatchType::ELEM_MATCH_OBJECT;
}
private:
@@ -103,8 +124,9 @@ private:
// child expressions.
std::stack<ABT> _stack;
- // Track whether the vistor is currently under an $elemMatch node.
- int _elemMatchCount{0};
+ // Used to track expressions contained under an $elemMatch. Each entry is either an
+ // ELEM_MATCH_OBJECT or ELEM_MATCH_VALUE.
+ std::vector<MatchExpression::MatchType> _elemMatchStack;
};
} // namespace mongo::optimizer
diff --git a/src/mongo/db/pipeline/abt/match_expression_visitor.cpp b/src/mongo/db/pipeline/abt/match_expression_visitor.cpp
index e422dc24d63..70be6fd3651 100644
--- a/src/mongo/db/pipeline/abt/match_expression_visitor.cpp
+++ b/src/mongo/db/pipeline/abt/match_expression_visitor.cpp
@@ -73,11 +73,11 @@ public:
ABTMatchExpressionPreVisitor(ExpressionAlgebrizerContext& ctx) : _ctx(ctx) {}
void visit(const ElemMatchObjectMatchExpression* expr) override {
- _ctx.enterElemMatch();
+ _ctx.enterElemMatch(expr->matchType());
}
void visit(const ElemMatchValueMatchExpression* expr) override {
- _ctx.enterElemMatch();
+ _ctx.enterElemMatch(expr->matchType());
}
private:
@@ -135,8 +135,8 @@ public:
assertSupportedPathExpression(expr);
ABT result = make<PathDefault>(Constant::boolean(false));
- if (!expr->path().empty()) {
- result = generateFieldPath(FieldPath(expr->path().toString()), std::move(result));
+ if (shouldGeneratePath(expr)) {
+ result = translateFieldRef(*(expr->fieldRef()), std::move(result));
}
_ctx.push(std::move(result));
}
@@ -227,9 +227,9 @@ public:
maybeComposePath<PathComposeA>(result, make<PathDefault>(Constant::boolean(true)));
}
- // The path can be empty if we are within an $elemMatch. In this case elemMatch would
- // insert a traverse.
- if (!expr->path().empty()) {
+ // Do not insert a traverse if within an $elemMatch; traversal will be handled by the
+ // $elemMatch expression itself.
+ if (shouldGeneratePath(expr)) {
// When the path we are comparing is a path to an array, the comparison is
// considered true if it evaluates to true for the array itself or for any of the
// array’s elements. 'result' evaluates comparison on the array elements, and
@@ -249,7 +249,7 @@ public:
make<Constant>(tagArraysOnly, valArraysOnly)));
arrOnlyGuard.reset();
}
- result = generateFieldPath(FieldPath(expr->path().toString()), std::move(result));
+ result = translateFieldRef(*(expr->fieldRef()), std::move(result));
}
_ctx.push(std::move(result));
}
@@ -426,14 +426,8 @@ public:
make<FunctionCall>("getArraySize", makeSeq(make<Variable>(lambdaProjName))),
Constant::int64(expr->getData()))));
- if (!expr->path().empty()) {
- // No traverse.
- result = translateFieldPath(
- FieldPath(expr->path().toString()),
- std::move(result),
- [](const std::string& fieldName, const bool /*isLastElement*/, ABT input) {
- return make<PathGet>(fieldName, std::move(input));
- });
+ if (shouldGeneratePath(expr)) {
+ result = translateFieldRef(*(expr->fieldRef()), std::move(result));
}
_ctx.push(std::move(result));
}
@@ -460,9 +454,7 @@ public:
makeSeq(make<Variable>(lambdaProjName),
Constant::int32(expr->typeSet().getBSONTypeMask())))));
- // The path can be empty if we are within an $elemMatch. In this case elemMatch would insert
- // a traverse.
- if (!expr->path().empty()) {
+ if (shouldGeneratePath(expr)) {
result = make<PathTraverse>(std::move(result), PathTraverse::kSingleLevel);
if (expr->typeSet().hasType(BSONType::Array)) {
// If we are testing against array type, insert a comparison against the
@@ -470,7 +462,7 @@ public:
result = make<PathComposeA>(make<PathArr>(), std::move(result));
}
- result = generateFieldPath(FieldPath(expr->path().toString()), std::move(result));
+ result = translateFieldRef(*(expr->fieldRef()), std::move(result));
}
_ctx.push(std::move(result));
}
@@ -517,33 +509,13 @@ private:
// Make sure we consider only arrays fields on the path.
maybeComposePath(result, make<PathArr>());
- if (!expr->path().empty()) {
- result = translateFieldPath(
- FieldPath{expr->path().toString()},
- std::move(result),
- [&](const std::string& fieldName, const bool isLastElement, ABT input) {
- if (!isLastElement) {
- input = make<PathTraverse>(std::move(input), PathTraverse::kSingleLevel);
- }
- return make<PathGet>(fieldName, std::move(input));
- });
+ if (shouldGeneratePath(expr)) {
+ result = translateFieldRef(*(expr->fieldRef()), std::move(result));
}
_ctx.push(std::move(result));
}
- ABT generateFieldPath(const FieldPath& fieldPath, ABT initial) {
- return translateFieldPath(
- fieldPath,
- std::move(initial),
- [&](const std::string& fieldName, const bool isLastElement, ABT input) {
- if (!isLastElement) {
- input = make<PathTraverse>(std::move(input), PathTraverse::kSingleLevel);
- }
- return make<PathGet>(fieldName, std::move(input));
- });
- }
-
void assertSupportedPathExpression(const PathMatchExpression* expr) {
uassert(ErrorCodes::InternalErrorNotSupported,
"Expression contains a numeric path component",
@@ -610,9 +582,7 @@ private:
break;
}
- // The path can be empty if we are within an $elemMatch. In this case elemMatch would
- // insert a traverse.
- if (!expr->path().empty()) {
+ if (shouldGeneratePath(expr)) {
if (tag == sbe::value::TypeTags::Array || tag == sbe::value::TypeTags::MinKey ||
tag == sbe::value::TypeTags::MaxKey) {
// The behavior of PathTraverse when it encounters an array is to apply its subpath
@@ -628,8 +598,9 @@ private:
result = make<PathTraverse>(std::move(result), PathTraverse::kSingleLevel);
}
- result = generateFieldPath(FieldPath(expr->path().toString()), std::move(result));
+ result = translateFieldRef(*(expr->fieldRef()), std::move(result));
}
+
_ctx.push(std::move(result));
}
@@ -659,6 +630,23 @@ private:
str::stream() << "Match expression is not supported: " << expr->matchType());
}
+ /**
+ * Returns whether the currently visiting expression should consider the path it's operating on
+ * and build the appropriate ABT. This can return false for expressions within an $elemMatch
+ * that operate against each value in an array (aka "elemMatch value").
+ */
+ bool shouldGeneratePath(const PathMatchExpression* expr) const {
+ // The only case where any expression, including $elemMatch, should ignore it's path is if
+ // it's directly under a value $elemMatch. The 'elemMatchStack' includes 'expr' if it's an
+ // $elemMatch, so we need to look back an extra element.
+ if (expr->matchType() == MatchExpression::MatchType::ELEM_MATCH_OBJECT ||
+ expr->matchType() == MatchExpression::MatchType::ELEM_MATCH_VALUE) {
+ return _ctx.shouldGeneratePathForElemMatch();
+ }
+
+ return _ctx.shouldGeneratePath();
+ }
+
// If we are parsing a partial index filter, we don't allow agg expressions.
const bool _allowAggExpressions;
diff --git a/src/mongo/db/pipeline/abt/utils.cpp b/src/mongo/db/pipeline/abt/utils.cpp
index c4d6093cc1b..9911e090305 100644
--- a/src/mongo/db/pipeline/abt/utils.cpp
+++ b/src/mongo/db/pipeline/abt/utils.cpp
@@ -30,7 +30,7 @@
#include "mongo/db/pipeline/abt/utils.h"
#include "mongo/db/exec/sbe/values/bson.h"
-
+#include "mongo/db/query/optimizer/utils/utils.h"
namespace mongo::optimizer {
@@ -81,6 +81,39 @@ ABT translateFieldPath(const FieldPath& fieldPath,
return result;
}
+ABT translateFieldRef(const FieldRef& fieldRef, ABT initial) {
+ ABT result = std::move(initial);
+
+ const size_t fieldPathLength = fieldRef.numParts();
+
+ // Handle empty field paths separately.
+ if (fieldPathLength == 0) {
+ return make<PathGet>("", std::move(result));
+ }
+
+ for (size_t i = fieldPathLength; i-- > 0;) {
+ // A single empty field path will parse to a FieldRef with 0 parts but should
+ // logically be considered a single part with an empty string.
+ if (i != fieldPathLength - 1) {
+ // For field paths with empty elements such as 'x.', we should traverse the
+ // array 'x' but not reach into any sub-objects. So a predicate such as {'x.':
+ // {$eq: 5}} should match {x: [5]} and {x: {"": 5}} but not {x: [{"": 5}]}.
+ const bool trailingEmptyPath =
+ (fieldPathLength >= 2u && i == fieldPathLength - 2u) && (fieldRef[i + 1] == ""_sd);
+ if (trailingEmptyPath) {
+ auto arrCase = make<PathArr>();
+ maybeComposePath(arrCase, result.cast<PathGet>()->getPath());
+ maybeComposePath<PathComposeA>(result, arrCase);
+ } else {
+ result = make<PathTraverse>(std::move(result), PathTraverse::kSingleLevel);
+ }
+ }
+ result = make<PathGet>(fieldRef[i].toString(), std::move(result));
+ }
+
+ return result;
+}
+
std::pair<boost::optional<ABT>, bool> getMinMaxBoundForType(const bool isMin,
const sbe::value::TypeTags& tag) {
switch (tag) {
diff --git a/src/mongo/db/pipeline/abt/utils.h b/src/mongo/db/pipeline/abt/utils.h
index 3d7c2906979..54a255adff7 100644
--- a/src/mongo/db/pipeline/abt/utils.h
+++ b/src/mongo/db/pipeline/abt/utils.h
@@ -40,12 +40,22 @@ std::pair<sbe::value::TypeTags, sbe::value::Value> convertFrom(Value val);
using ABTFieldNameFn =
std::function<ABT(const std::string& fieldName, const bool isLastElement, ABT input)>;
+
+/**
+ * Translates an aggregation FieldPath by invoking the `fieldNameFn` for each path component.
+ */
ABT translateFieldPath(const FieldPath& fieldPath,
ABT initial,
const ABTFieldNameFn& fieldNameFn,
size_t skipFromStart = 0);
/**
+ * Translates a given FieldRef (typically used in a MatchExpression) with 'initial' as the input
+ * ABT.
+ */
+ABT translateFieldRef(const FieldRef& fieldRef, ABT initial);
+
+/**
* Return the minimum or maximum value for the "class" of values represented by the input
* constant. Used to support type bracketing.
* Return format is <min/max value, bool inclusive>
View Lorry Controller Status