diff options
author | James Wahlin <james@mongodb.com> | 2018-10-01 16:05:08 -0400 |
---|---|---|
committer | James Wahlin <james@mongodb.com> | 2018-10-02 09:56:37 -0400 |
commit | f7ddb89c8caf438781de9191d690d03f711b63fe (patch) | |
tree | 9244266869d8c17de23d5e0c817a2fddc2bc849a /src/mongo/db/query/planner_wildcard_helpers.h | |
parent | 5a6ee566f608c46654133de17a4e8bb3464d680d (diff) | |
download | mongo-f7ddb89c8caf438781de9191d690d03f711b63fe.tar.gz |
SERVER-37188 Rename "All Paths" index to "Wildcard" index
Diffstat (limited to 'src/mongo/db/query/planner_wildcard_helpers.h')
-rw-r--r-- | src/mongo/db/query/planner_wildcard_helpers.h | 101 |
1 files changed, 101 insertions, 0 deletions
diff --git a/src/mongo/db/query/planner_wildcard_helpers.h b/src/mongo/db/query/planner_wildcard_helpers.h new file mode 100644 index 00000000000..7e56adb1ba0 --- /dev/null +++ b/src/mongo/db/query/planner_wildcard_helpers.h @@ -0,0 +1,101 @@ +/** + * Copyright (C) 2018 MongoDB Inc. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU Affero General Public License, version 3, + * as published by the Free Software Foundation. + * + * 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 + * GNU Affero General Public License for more details. + * + * You should have received a copy of the GNU Affero General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + * + * 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 GNU Affero General 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 <set> + +#include "mongo/db/field_ref.h" +#include "mongo/db/index/multikey_paths.h" +#include "mongo/db/query/index_bounds_builder.h" +#include "mongo/db/query/query_solution.h" + +namespace mongo { +namespace wildcard_planning { + +using BoundsTightness = IndexBoundsBuilder::BoundsTightness; + +/** + * Specifies the maximum depth of nested array indices through which a query may traverse before a + * $** declines to answer it, due to the exponential complexity of the bounds required. + */ +static constexpr size_t kWildcardMaxArrayIndexTraversalDepth = 8u; + +/** + * Returns a MultikeyPaths which indicates which components of 'indexedPath' are multikey, by + * looking up multikeyness in 'multikeyPathSet'. + */ +MultikeyPaths buildMultiKeyPathsForExpandedWildcardIndexEntry( + const FieldRef& indexedPath, const std::set<FieldRef>& multikeyPathSet); + +/** + * Given a query path and the set of known multikey path components, this function outputs the power + * set of paths generated by considering each relevant numerical path component first as a literal + * fieldname, and then as an array index. In other words, for each numerical path component that + * immediately follows a multikey field, we will output one path with the numerical component and + * one path without. If both 'a' and 'b' are multikey, then the queryPath 'a.0.b.1.c' will produce + * ['a.0.b.1.c', 'a.0.b.c', 'a.b.1.c', 'a.b.c']. + */ +std::set<FieldRef> generateFieldNameOrArrayIndexPathSet(const std::set<std::size_t>& multikeyPaths, + const FieldRef& queryPath); + +/** + * In certain circumstances, it is necessary to adjust the tightness of the bounds generated by the + * planner for $** indexes. For instance, if the query traverses through one or more arrays via + * specific indices, then we must enforce INEXACT_FETCH to ensure correctness, regardless of the + * predicate. Given an IndexEntry representing an expanded $** index, we apply any necessary changes + * to the tightness here. + */ +BoundsTightness applyWildcardIndexScanBoundsTightness(const IndexEntry& index, + BoundsTightness tightnessIn); + +/** + * Returns false if 'queryPath' includes any numerical path components which render it unanswerable + * by the $** index, true otherwise. Specifically, the $** index cannot answer the query if either + * of the following scenarios occur: + * + * - The query path traverses through more than 'kWildcardMaxArrayIndexTraversalDepth' nested arrays + * via explicit array indices. + * - The query path lies along a $** projection through an array index. + * + * For an example of the latter case, say that our query path is 'a.0.b', our projection includes + * {'a.0': 1}, and 'a' is multikey. The query semantics will match 'a.0.b' by either field name or + * array index against the documents, but because the $** index always projects numeric path + * components strictly as field names, the projection {'a.0': 1} cannot correctly support this + * query. + * + * To see why, consider the document {a: [1, 2, 3]}. Query {'a.0': 1} will match this document, but + * the projection {'a.0': 1} will produce output document {a: []}, and so we will not index any of + * the values [1, 2, 3] for 'a'. + */ +bool validateNumericPathComponents(const MultikeyPaths& multikeyPaths, + const std::set<FieldRef>& includedPaths, + const FieldRef& queryPath); + +} // namespace wildcard_planning +} // namespace mongo |