From 44f0661a7a770bad193582935d001b4754389b34 Mon Sep 17 00:00:00 2001 From: Tess Avitabile Date: Fri, 29 Jan 2016 13:55:48 -0500 Subject: SERVER-18115 Avoid unnecessary in-memory sort stage for .min()/.max() queries (cherry picked from commit ecfac2be1f855c19ef6b50eef712fd3b6b9631f7) --- src/mongo/db/query/SConscript | 10 ++ src/mongo/db/query/query_planner_test.cpp | 39 +++++ src/mongo/db/query/query_solution.cpp | 10 ++ src/mongo/db/query/query_solution_test.cpp | 252 +++++++++++++++++++++++++++++ 4 files changed, 311 insertions(+) create mode 100644 src/mongo/db/query/query_solution_test.cpp diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript index ce2f45085a6..9f1dd85bc14 100644 --- a/src/mongo/db/query/SConscript +++ b/src/mongo/db/query/SConscript @@ -340,6 +340,16 @@ env.CppUnitTest( ], ) +env.CppUnitTest( + target="query_solution_test", + source=[ + "query_solution_test.cpp", + ], + LIBDEPS=[ + "query_planner", + ], +) + # $text pulls in a lot of stuff so we test it here. env.CppUnitTest( target="query_planner_text_test", diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp index 0504fc410b8..30fa95eb58c 100644 --- a/src/mongo/db/query/query_planner_test.cpp +++ b/src/mongo/db/query/query_planner_test.cpp @@ -1088,6 +1088,45 @@ TEST_F(QueryPlannerTest, MaxMinSort) { assertSolutionExists("{fetch: {node: {ixscan: {filter: null, pattern: {a: 1}}}}}"); } +TEST_F(QueryPlannerTest, MaxMinSortEqualityFirstSortSecond) { + addIndex(BSON("a" << 1 << "b" << 1)); + + // Run an empty query, sort {b: 1}, max/min arguments. + runQueryFull(BSONObj(), + fromjson("{b: 1}"), + BSONObj(), + 0, + 0, + BSONObj(), + fromjson("{a: 1, b: 1}"), + fromjson("{a: 1, b: 2}"), + false); + + assertNumSolutions(1); + assertSolutionExists("{fetch: {node: {ixscan: {filter: null, pattern: {a: 1, b: 1}}}}}"); +} + +TEST_F(QueryPlannerTest, MaxMinSortInequalityFirstSortSecond) { + addIndex(BSON("a" << 1 << "b" << 1)); + + // Run an empty query, sort {b: 1}, max/min arguments. + runQueryFull(BSONObj(), + fromjson("{b: 1}"), + BSONObj(), + 0, + 0, + BSONObj(), + fromjson("{a: 1, b: 1}"), + fromjson("{a: 2, b: 2}"), + false); + + assertNumSolutions(1); + assertSolutionExists( + "{sort: {pattern: {b: 1}, limit: 0, node: {sortKeyGen: {node: " + "{fetch: {node: " + "{ixscan: {filter: null, pattern: {a: 1, b: 1}}}}}}}}}"); +} + TEST_F(QueryPlannerTest, MaxMinReverseSort) { addIndex(BSON("a" << 1)); diff --git a/src/mongo/db/query/query_solution.cpp b/src/mongo/db/query/query_solution.cpp index da1fa79c034..e2168669187 100644 --- a/src/mongo/db/query/query_solution.cpp +++ b/src/mongo/db/query/query_solution.cpp @@ -501,6 +501,16 @@ void IndexScanNode::computeProperties() { } equalityFields.insert(oil.name); } + } else { + BSONObjIterator keyIter(indexKeyPattern); + BSONObjIterator startIter(bounds.startKey); + BSONObjIterator endIter(bounds.endKey); + while (keyIter.more() && startIter.more() && endIter.more()) { + BSONElement key = keyIter.next(); + if (startIter.next() == endIter.next()) { + equalityFields.insert(key.fieldName()); + } + } } if (equalityFields.empty()) { diff --git a/src/mongo/db/query/query_solution_test.cpp b/src/mongo/db/query/query_solution_test.cpp new file mode 100644 index 00000000000..ffb90d2fa6e --- /dev/null +++ b/src/mongo/db/query/query_solution_test.cpp @@ -0,0 +1,252 @@ +/** + * Copyright (C) 2016 10gen 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 . + * + * 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. + */ + +#include "mongo/platform/basic.h" + +#include "mongo/db/query/index_bounds_builder.h" +#include "mongo/db/query/query_solution.h" +#include "mongo/unittest/unittest.h" + +namespace { + +using namespace mongo; + +// Index: {a: 1, b: 1, c: 1, d: 1, e: 1} +// Min: {a: 1, b: 1, c: 1, d: 1, e: 1} +// Max: {a: 1, b: 1, c: 1, d: 1, e: 1} +TEST(QuerySolutionTest, SimpleRangeAllEqual) { + IndexScanNode node{}; + node.indexKeyPattern = BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1); + node.bounds.isSimpleRange = true; + node.bounds.startKey = BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1); + node.bounds.endKey = BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1); + node.computeProperties(); + + // Expected sort orders + ASSERT_EQUALS(node.getSort().size(), 10U); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1))); + ASSERT(node.getSort().count(BSON("b" << 1 << "c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("e" << 1))); + ASSERT(node.getSort().count(BSONObj{})); +} + +// Index: {a: 1, b: 1, c: 1, d: 1, e: 1} +// Min: {a: 1, b: 1, c: 1, d: 1, e: 1} +// Max: {a: 2, b: 2, c: 2, d: 2, e: 2} +TEST(QuerySolutionTest, SimpleRangeNoneEqual) { + IndexScanNode node{}; + node.indexKeyPattern = BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1); + node.bounds.isSimpleRange = true; + node.bounds.startKey = BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1); + node.bounds.endKey = BSON("a" << 2 << "b" << 2 << "c" << 2 << "d" << 2 << "e" << 2); + node.computeProperties(); + + // Expected sort orders + ASSERT_EQUALS(node.getSort().size(), 5U); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1))); +} + +// Index: {a: 1, b: 1, c: 1, d: 1, e: 1} +// Min: {a: 1, b: 1, c: 1, d: 1, e: 1} +// Max: {a: 1, b: 1, c: 2, d: 2, e: 2} +TEST(QuerySolutionTest, SimpleRangeSomeEqual) { + IndexScanNode node{}; + node.indexKeyPattern = BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1); + node.bounds.isSimpleRange = true; + node.bounds.startKey = BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1); + node.bounds.endKey = BSON("a" << 1 << "b" << 1 << "c" << 2 << "d" << 2 << "e" << 2); + node.computeProperties(); + + // Expected sort orders + ASSERT_EQUALS(node.getSort().size(), 9U); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1))); + ASSERT(node.getSort().count(BSON("b" << 1 << "c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("c" << 1 << "d" << 1))); + ASSERT(node.getSort().count(BSON("c" << 1))); +} + +// Index: {a: 1, b: 1, c: 1, d: 1, e: 1} +// Intervals: a: [1,1], b: [1,1], c: [1,1], d: [1,1], e: [1,1] +TEST(QuerySolutionTest, IntervalListAllPoints) { + IndexScanNode node{}; + node.indexKeyPattern = BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1); + + OrderedIntervalList a{}; + a.name = "a"; + a.intervals.push_back(IndexBoundsBuilder::makePointInterval(BSON("" << 1))); + node.bounds.fields.push_back(a); + + OrderedIntervalList b{}; + b.name = "b"; + b.intervals.push_back(IndexBoundsBuilder::makePointInterval(BSON("" << 1))); + node.bounds.fields.push_back(b); + + OrderedIntervalList c{}; + c.name = "c"; + c.intervals.push_back(IndexBoundsBuilder::makePointInterval(BSON("" << 1))); + node.bounds.fields.push_back(c); + + OrderedIntervalList d{}; + d.name = "d"; + d.intervals.push_back(IndexBoundsBuilder::makePointInterval(BSON("" << 1))); + node.bounds.fields.push_back(d); + + OrderedIntervalList e{}; + e.name = "e"; + e.intervals.push_back(IndexBoundsBuilder::makePointInterval(BSON("" << 1))); + node.bounds.fields.push_back(e); + + node.computeProperties(); + + // Expected sort orders + ASSERT_EQUALS(node.getSort().size(), 10U); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1))); + ASSERT(node.getSort().count(BSON("b" << 1 << "c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("e" << 1))); + ASSERT(node.getSort().count(BSONObj{})); +} + + +// Index: {a: 1, b: 1, c: 1, d: 1, e: 1} +// Intervals: a: [1,2], b: [1,2], c: [1,2], d: [1,2], e: [1,2] +TEST(QuerySolutionTest, IntervalListNoPoints) { + IndexScanNode node{}; + node.indexKeyPattern = BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1); + + OrderedIntervalList a{}; + a.name = "a"; + a.intervals.push_back( + IndexBoundsBuilder::makeRangeInterval(BSON("" << 1 << "" << 2), true, true)); + node.bounds.fields.push_back(a); + + OrderedIntervalList b{}; + b.name = "b"; + b.intervals.push_back( + IndexBoundsBuilder::makeRangeInterval(BSON("" << 1 << "" << 2), true, true)); + node.bounds.fields.push_back(b); + + OrderedIntervalList c{}; + c.name = "c"; + c.intervals.push_back( + IndexBoundsBuilder::makeRangeInterval(BSON("" << 1 << "" << 2), true, true)); + node.bounds.fields.push_back(c); + + OrderedIntervalList d{}; + d.name = "d"; + d.intervals.push_back( + IndexBoundsBuilder::makeRangeInterval(BSON("" << 1 << "" << 2), true, true)); + node.bounds.fields.push_back(d); + + OrderedIntervalList e{}; + e.name = "e"; + e.intervals.push_back( + IndexBoundsBuilder::makeRangeInterval(BSON("" << 1 << "" << 2), true, true)); + node.bounds.fields.push_back(e); + + node.computeProperties(); + + // Expected sort orders + ASSERT_EQUALS(node.getSort().size(), 5U); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1))); +} + +// Index: {a: 1, b: 1, c: 1, d: 1, e: 1} +// Intervals: a: [1,1], b: [1,1], c: [1,2], d: [1,2], e: [1,2] +TEST(QuerySolutionTest, IntervalListSomePoints) { + IndexScanNode node{}; + node.indexKeyPattern = BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1); + + OrderedIntervalList a{}; + a.name = "a"; + a.intervals.push_back(IndexBoundsBuilder::makePointInterval(BSON("" << 1))); + node.bounds.fields.push_back(a); + + OrderedIntervalList b{}; + b.name = "b"; + b.intervals.push_back(IndexBoundsBuilder::makePointInterval(BSON("" << 1))); + node.bounds.fields.push_back(b); + + OrderedIntervalList c{}; + c.name = "c"; + c.intervals.push_back( + IndexBoundsBuilder::makeRangeInterval(BSON("" << 1 << "" << 2), true, true)); + node.bounds.fields.push_back(c); + + OrderedIntervalList d{}; + d.name = "d"; + d.intervals.push_back( + IndexBoundsBuilder::makeRangeInterval(BSON("" << 1 << "" << 2), true, true)); + node.bounds.fields.push_back(d); + + OrderedIntervalList e{}; + e.name = "e"; + e.intervals.push_back( + IndexBoundsBuilder::makeRangeInterval(BSON("" << 1 << "" << 2), true, true)); + node.bounds.fields.push_back(e); + + node.computeProperties(); + + // Expected sort orders + ASSERT_EQUALS(node.getSort().size(), 9U); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1 << "d" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1 << "c" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1 << "b" << 1))); + ASSERT(node.getSort().count(BSON("a" << 1))); + ASSERT(node.getSort().count(BSON("b" << 1 << "c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("c" << 1 << "d" << 1 << "e" << 1))); + ASSERT(node.getSort().count(BSON("c" << 1 << "d" << 1))); + ASSERT(node.getSort().count(BSON("c" << 1))); +} + +} // namespace -- cgit v1.2.1