diff options
-rw-r--r-- | src/mongo/db/query/SConscript | 1 | ||||
-rw-r--r-- | src/mongo/db/query/optimizer/SConscript | 26 | ||||
-rw-r--r-- | src/mongo/db/query/optimizer/defs.cpp | 40 | ||||
-rw-r--r-- | src/mongo/db/query/optimizer/defs.h | 53 | ||||
-rw-r--r-- | src/mongo/db/query/optimizer/filter.h | 38 | ||||
-rw-r--r-- | src/mongo/db/query/optimizer/node.cpp | 129 | ||||
-rw-r--r-- | src/mongo/db/query/optimizer/node.h | 163 | ||||
-rw-r--r-- | src/mongo/db/query/optimizer/optimizer_test.cpp | 43 | ||||
-rw-r--r-- | src/mongo/db/query/optimizer/projection.h | 38 | ||||
-rw-r--r-- | src/mongo/db/query/optimizer/props.h | 38 |
10 files changed, 569 insertions, 0 deletions
diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript index eada898eafb..a82d443d5bf 100644 --- a/src/mongo/db/query/SConscript +++ b/src/mongo/db/query/SConscript @@ -8,6 +8,7 @@ env.SConscript( dirs=[ "collation", "datetime", + 'optimizer', ], exports=[ 'env' diff --git a/src/mongo/db/query/optimizer/SConscript b/src/mongo/db/query/optimizer/SConscript new file mode 100644 index 00000000000..175b109625d --- /dev/null +++ b/src/mongo/db/query/optimizer/SConscript @@ -0,0 +1,26 @@ +# -*- mode: python -*- + +Import("env") + +env = env.Clone() + +env.Library( + target="optimizer", + source=[ + "defs.cpp", + "node.cpp", + ], + LIBDEPS=[ +# "$BUILD_DIR/mongo/base", + ], +) + +env.CppUnitTest( + target='optimizer_test', + source=[ + 'optimizer_test.cpp', + ], + LIBDEPS=[ + 'optimizer', + ] +) diff --git a/src/mongo/db/query/optimizer/defs.cpp b/src/mongo/db/query/optimizer/defs.cpp new file mode 100644 index 00000000000..07eb9c8b85c --- /dev/null +++ b/src/mongo/db/query/optimizer/defs.cpp @@ -0,0 +1,40 @@ +/** + * Copyright (C) 2020-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/query/optimizer/defs.h" + +namespace mongo::optimizer { + +Context::Context() : _currentNodeId(0) {} + +NodeIdType Context::nextNodeId() { + return _currentNodeId++; +} + +} // namespace mongo::optimizer diff --git a/src/mongo/db/query/optimizer/defs.h b/src/mongo/db/query/optimizer/defs.h new file mode 100644 index 00000000000..84f8e1ff783 --- /dev/null +++ b/src/mongo/db/query/optimizer/defs.h @@ -0,0 +1,53 @@ +/** + * Copyright (C) 2020-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 <string> + +namespace mongo::optimizer { + +using FieldNameType = std::string; +using CollectionNameType = std::string; +using ProjectionName = std::string; + +using NodeIdType = uint64_t; + +class Context +{ +public: + Context();; + + NodeIdType nextNodeId(); + +private: + NodeIdType _currentNodeId; +}; + +} // namespace mongo::optimizer diff --git a/src/mongo/db/query/optimizer/filter.h b/src/mongo/db/query/optimizer/filter.h new file mode 100644 index 00000000000..1e62d7c020b --- /dev/null +++ b/src/mongo/db/query/optimizer/filter.h @@ -0,0 +1,38 @@ +/** + * Copyright (C) 2020-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 <string> + +namespace mongo::optimizer { + +using FilterType = std::string; + +} // namespace mongo::optimizer diff --git a/src/mongo/db/query/optimizer/node.cpp b/src/mongo/db/query/optimizer/node.cpp new file mode 100644 index 00000000000..46a5fcc3859 --- /dev/null +++ b/src/mongo/db/query/optimizer/node.cpp @@ -0,0 +1,129 @@ +/** + * Copyright (C) 2020-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/query/optimizer/node.h" + +namespace mongo::optimizer { + +Node::Node(NodePtr child) { + _children.push_back(std::move(child)); +} + +Node::Node(std::vector<NodePtr> children) : _children(std::move(children)) {} + +std::string Node::generateMemo() { + std::ostringstream os; + generateMemoInternal(os); + return os.str(); +} + +NodePtr ScanNode::create(CollectionNameType collectionName) { + return NodePtr(new ScanNode(std::move(collectionName))); +} + +ScanNode::ScanNode(CollectionNameType collectionName) + : Node(), _collectionName(std::move(collectionName)) {} + +void ScanNode::generateMemoInternal(std::ostringstream& os) { + os << "Scan"; +} + +NodePtr MultiJoinNode::create(FilterSet filterSet, + ProjectionMap projectionMap, + std::vector<NodePtr> children) { + return NodePtr( + new MultiJoinNode(std::move(filterSet), std::move(projectionMap), std::move(children))); +} + +MultiJoinNode::MultiJoinNode(FilterSet filterSet, + ProjectionMap projectionMap, + std::vector<NodePtr> children) + : Node(std::move(children)), + _filterSet(std::move(filterSet)), + _projectionMap(std::move(projectionMap)) {} + +void MultiJoinNode::generateMemoInternal(std::ostringstream& os) { + os << "MultiJoin"; +} + +NodePtr UnionNode::create(std::vector<NodePtr> children) { + return NodePtr(new UnionNode(std::move(children))); +} + +UnionNode::UnionNode(std::vector<NodePtr> children) : Node(std::move(children)) {} + +void UnionNode::generateMemoInternal(std::ostringstream& os) { + os << "Union"; +} + +NodePtr GroupByNode::create(GroupByNode::GroupByVector groupByVector, + GroupByNode::ProjectionMap projectionMap, + NodePtr child) { + return NodePtr( + new GroupByNode(std::move(groupByVector), std::move(projectionMap), std::move(child))); +} + +GroupByNode::GroupByNode(GroupByNode::GroupByVector groupByVector, + GroupByNode::ProjectionMap projectionMap, + NodePtr child) + : Node(std::move(child)), + _groupByVector(std::move(groupByVector)), + _projectionMap(std::move(projectionMap)) {} + +void GroupByNode::generateMemoInternal(std::ostringstream& os) { + os << "GroupBy"; +} + +NodePtr UnwindNode::create(ProjectionName projectionName, + const bool retainNonArrays, + NodePtr child) { + return NodePtr(new UnwindNode(std::move(projectionName), retainNonArrays, std::move(child))); +} + +UnwindNode::UnwindNode(ProjectionName projectionName, const bool retainNonArrays, NodePtr child) + : Node(std::move(child)), + _projectionName(std::move(projectionName)), + _retainNonArrays(retainNonArrays) {} + +void UnwindNode::generateMemoInternal(std::ostringstream& os) { + os << "Unwind"; +} + +NodePtr WindNode::create(ProjectionName projectionName, NodePtr child) { + return NodePtr(new WindNode(std::move(projectionName), std::move(child))); +} + +WindNode::WindNode(ProjectionName projectionName, NodePtr child) + : Node(std::move(child)), _projectionName(std::move(projectionName)) {} + +void WindNode::generateMemoInternal(std::ostringstream& os) { + os << "Wind"; +} + +} // namespace mongo::optimizer diff --git a/src/mongo/db/query/optimizer/node.h b/src/mongo/db/query/optimizer/node.h new file mode 100644 index 00000000000..b2aba1adc3e --- /dev/null +++ b/src/mongo/db/query/optimizer/node.h @@ -0,0 +1,163 @@ +/** + * Copyright (C) 2020-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 <memory> +#include <sstream> +#include <string> +#include <unordered_map> +#include <unordered_set> +#include <utility> +#include <vector> + +#include "mongo/db/query/optimizer/defs.h" +#include "mongo/db/query/optimizer/filter.h" +#include "mongo/db/query/optimizer/projection.h" +#include "mongo/db/query/optimizer/props.h" + + +namespace mongo::optimizer { + +class Node; +using NodePtr = std::unique_ptr<Node>; + + +class Node { +protected: + Node() : _children() {} + + // pass context + explicit Node(NodePtr child); + + explicit Node(std::vector<NodePtr> children); + + virtual void generateMemoInternal(std::ostringstream& os) = 0; + + // clone +public: + virtual std::string generateMemo() final; + +private: + // id + // properties + std::vector<NodePtr> _children; +}; + +class ScanNode : public Node { +public: + static NodePtr create(CollectionNameType collectionName); + +protected: + void generateMemoInternal(std::ostringstream& os) override; + +private: + explicit ScanNode(CollectionNameType collectionName); + + const CollectionNameType _collectionName; +}; + +class MultiJoinNode : public Node { +public: + using FilterSet = std::unordered_set<FilterType>; + using ProjectionMap = std::unordered_map<ProjectionName, ProjectionType>; + + static NodePtr create(FilterSet filterSet, + ProjectionMap projectionMap, + std::vector<NodePtr> children); + +protected: + void generateMemoInternal(std::ostringstream& os) override; + +private: + explicit MultiJoinNode(FilterSet filterSet, + ProjectionMap projectionMap, + std::vector<NodePtr> children); + + FilterSet _filterSet; + ProjectionMap _projectionMap; +}; + +class UnionNode : public Node { +public: + static NodePtr create(std::vector<NodePtr> children); + +protected: + void generateMemoInternal(std::ostringstream& os) override; + +private: + explicit UnionNode(std::vector<NodePtr> children); +}; + +class GroupByNode : public Node { +public: + using GroupByVector = std::vector<ProjectionName>; + using ProjectionMap = std::unordered_map<ProjectionName, ProjectionType>; + + static NodePtr create(GroupByVector groupByVector, ProjectionMap projectionMap, NodePtr child); + +protected: + void generateMemoInternal(std::ostringstream& os) override; + +private: + explicit GroupByNode(GroupByVector groupByVector, ProjectionMap projectionMap, NodePtr child); + + GroupByVector _groupByVector; + ProjectionMap _projectionMap; +}; + +class UnwindNode : public Node { +public: + static NodePtr create(ProjectionName projectionName, bool retainNonArrays, NodePtr child); + +protected: + void generateMemoInternal(std::ostringstream& os) override; + +private: + UnwindNode(ProjectionName projectionName, bool retainNonArrays, NodePtr child); + + const ProjectionName _projectionName; + const bool _retainNonArrays; +}; + +class WindNode : public Node { +public: + static NodePtr create(ProjectionName projectionName, NodePtr child); + +protected: + void generateMemoInternal(std::ostringstream& os) override; + +private: + WindNode(ProjectionName projectionName, NodePtr child); + + const ProjectionName _projectionName; +}; + + +} // namespace mongo::optimizer diff --git a/src/mongo/db/query/optimizer/optimizer_test.cpp b/src/mongo/db/query/optimizer/optimizer_test.cpp new file mode 100644 index 00000000000..1f244624f7b --- /dev/null +++ b/src/mongo/db/query/optimizer/optimizer_test.cpp @@ -0,0 +1,43 @@ +/** + * Copyright (C) 2020-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/query/optimizer/node.h" +#include "mongo/unittest/unittest.h" + +namespace mongo::optimizer { +namespace { + +TEST(Optimizer, Basic) { + NodePtr ptr = ScanNode::create("test"); + const std::string s = ptr->generateMemo(); + NodePtr ptr1 = ScanNode::create("test"); +} + +} // namespace +} // namespace mongo::optimizer diff --git a/src/mongo/db/query/optimizer/projection.h b/src/mongo/db/query/optimizer/projection.h new file mode 100644 index 00000000000..78be4907a9e --- /dev/null +++ b/src/mongo/db/query/optimizer/projection.h @@ -0,0 +1,38 @@ +/** + * Copyright (C) 2020-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 <string> + +namespace mongo::optimizer { + +using ProjectionType = std::string; + +} // namespace mongo::optimizer diff --git a/src/mongo/db/query/optimizer/props.h b/src/mongo/db/query/optimizer/props.h new file mode 100644 index 00000000000..cd366152493 --- /dev/null +++ b/src/mongo/db/query/optimizer/props.h @@ -0,0 +1,38 @@ +/** + * Copyright (C) 2020-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 <string> + +namespace mongo::optimizer { + +using LogicalProperties = std::string; + +} // namespace mongo::optimizer |