SERVER-18115 Avoid unnecessary in-memory sort stage for .min()/.max() queries

(cherry picked from commit ecfac2be1f855c19ef6b50eef712fd3b6b9631f7)

4 files changed, 311 insertions, 0 deletions

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 <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.
+ */
+
+#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