SERVER-13675 do not cache plans if there is a tie

(backport of 7dcbdc440a56fef19a561f513d8eddd1c2a2b27f)

10 files changed, 499 insertions, 443 deletions

diff --git a/jstests/core/index_filter_commands.js b/jstests/core/index_filter_commands.js
index c10fd3da0ca..4fa1e533a8a 100644
--- a/jstests/core/index_filter_commands.js
+++ b/jstests/core/index_filter_commands.js
@@ -26,7 +26,12 @@ var t = db.jstests_index_filter_commands;
 
 t.drop();
 
+// Setup the data so that plans will not tie given the indices and query
+// below. Tying plans will not be cached, and we need cached shapes in
+// order to test the filter functionality.
 t.save({a: 1});
+t.save({a: 1});
+t.save({a: 1, b: 1});
 
 // Add 2 indexes.
 // 1st index is more efficient.
@@ -38,7 +43,7 @@ t.ensureIndex(indexA1);
 t.ensureIndex(indexA1B1);
 t.ensureIndex(indexA1C1);
 
-var queryA1 = {a: 1};
+var queryA1 = {a: 1, b: 1};
 var projectionA1 = {_id: 0, a: 1};
 var sortA1 = {a: -1};
 
diff --git a/jstests/core/plan_cache_clear.js b/jstests/core/plan_cache_clear.js
new file mode 100644
index 00000000000..5923fdbd238
--- /dev/null
+++ b/jstests/core/plan_cache_clear.js
@@ -0,0 +1,95 @@
+// Test clearing of the plan cache, either manually through the planCacheClear command,
+// or due to system events such as an index build.
+
+var t = db.jstests_plan_cache_clear;
+t.drop();
+
+// Utility function to list query shapes in cache.
+function getShapes(collection) {
+    if (collection == undefined) {
+        collection = t;
+    }
+    var res = collection.runCommand('planCacheListQueryShapes');
+    print('planCacheListQueryShapes() = ' + tojson(res));
+    assert.commandWorked(res, 'planCacheListQueryShapes failed');
+    assert(res.hasOwnProperty('shapes'), 'shapes missing from planCacheListQueryShapes result');
+    return res.shapes;
+}
+
+t.save({a: 1, b: 1});
+t.save({a: 1, b: 2});
+t.save({a: 1, b: 2});
+t.save({a: 2, b: 2});
+
+// We need two indices so that the MultiPlanRunner is executed.
+t.ensureIndex({a: 1});
+t.ensureIndex({a: 1, b:1});
+
+// Run a query so that an entry is inserted into the cache.
+assert.eq(1, t.find({a: 1, b: 1}).itcount(), 'unexpected document count');
+
+// Invalid key should be a no-op.
+t.runCommand('planCacheClear', {query: {unknownfield: 1}});
+assert.eq(1, getShapes().length, 'removing unknown query should not affecting exisiting entries');
+
+// Run a new query shape and drop it from the cache
+assert.eq(1, getShapes().length, 'unexpected cache size after running 2nd query');
+assert.commandWorked(t.runCommand('planCacheClear', {query: {a: 1, b: 1}}));
+assert.eq(0, getShapes().length, 'unexpected cache size after dropping 2nd query from cache');
+
+// Insert two more shapes into the cache.
+assert.eq(1, t.find({a: 1, b: 1}).itcount(), 'unexpected document count');
+assert.eq(1, t.find({a: 1, b: 1}, {_id: 0, a: 1}).itcount(), 'unexpected document count');
+
+// Drop query cache. This clears all cached queries in the collection.
+res = t.runCommand('planCacheClear');
+print('planCacheClear() = ' + tojson(res));
+assert.commandWorked(res, 'planCacheClear failed');
+assert.eq(0, getShapes().length, 'plan cache should be empty after successful planCacheClear()');
+
+//
+// Query Plan Revision
+// http://docs.mongodb.org/manual/core/query-plans/#query-plan-revision
+// As collections change over time, the query optimizer deletes the query plan and re-evaluates
+// after any of the following events:
+// - The collection receives 1,000 write operations.
+// - The reIndex rebuilds the index.
+// - You add or drop an index.
+// - The mongod process restarts.
+//
+
+// Case 1: The collection receives 1,000 write operations.
+// Steps:
+//     Populate cache. Cache should contain 1 key after running query.
+//     Insert 1000 documents.
+//     Cache should be cleared.
+assert.eq(1, t.find({a: 1, b: 1}).itcount(), 'unexpected document count');
+assert.eq(1, getShapes().length, 'plan cache should not be empty after query');
+for (var i = 0; i < 1000; i++) {
+    t.save({b: i});
+}
+assert.eq(0, getShapes().length, 'plan cache should be empty after adding 1000 documents.');
+
+// Case 2: The reIndex rebuilds the index.
+// Steps:
+//     Populate the cache with 1 entry.
+//     Run reIndex on the collection.
+//     Confirm that cache is empty.
+assert.eq(1, t.find({a: 1, b: 1}).itcount(), 'unexpected document count');
+assert.eq(1, getShapes().length, 'plan cache should not be empty after query');
+res = t.reIndex();
+print('reIndex result = ' + tojson(res));
+assert.eq(0, getShapes().length, 'plan cache should be empty after reIndex operation');
+
+// Case 3: You add or drop an index.
+// Steps:
+//     Populate the cache with 1 entry.
+//     Add an index.
+//     Confirm that cache is empty.
+assert.eq(1, t.find({a: 1, b: 1}).itcount(), 'unexpected document count');
+assert.eq(1, getShapes().length, 'plan cache should not be empty after query');
+t.ensureIndex({b: 1});
+assert.eq(0, getShapes().length, 'plan cache should be empty after adding index');
+
+// Case 4: The mongod process restarts
+// Not applicable.
diff --git a/jstests/core/plan_cache_commands.js b/jstests/core/plan_cache_commands.js
deleted file mode 100644
index 613d436aa15..00000000000
--- a/jstests/core/plan_cache_commands.js
+++ /dev/null
@@ -1,433 +0,0 @@
-/**
- * Plan cache commands
- * 
- * Cache-wide Commands
- * - planCacheListQueryShapes
- * - planCacheClear
- *       Removes plans for one or all query shapes.
- * - planCacheListPlans
- */ 
-
-var t = db.jstests_plan_cache_commands;
-t.drop();
-
-// Insert some data so we don't go to EOF.
-t.save({a: 1, b: 1});
-t.save({a: 2, b: 2});
-
-// We need two indices so that the MultiPlanRunner is executed.
-t.ensureIndex({a: 1});
-t.ensureIndex({a: 1, b:1});
-
-// Run the query.
-var queryA1 = {a: 1, b:1};
-var projectionA1 = {_id: 0, a: 1};
-var sortA1 = {a: -1};
-assert.eq(1, t.find(queryA1, projectionA1).sort(sortA1).itcount(), 'unexpected document count');
-// We now expect the two indices to be compared and a cache entry to exist.
-
-
-//
-// tests for planCacheListQueryShapes
-// Returns a list of query shapes for the queries currently cached in the collection.
-//
-
-// Utility function to list query shapes in cache.
-function getShapes(collection) {
-    if (collection == undefined) {
-        
-        collection = t;
-    }
-    var res = collection.runCommand('planCacheListQueryShapes');
-    print('planCacheListQueryShapes() = ' + tojson(res));
-    assert.commandWorked(res, 'planCacheListQueryShapes failed');
-    assert(res.hasOwnProperty('shapes'), 'shapes missing from planCacheListQueryShapes result');
-    return res.shapes;
-    
-}
-
-// Attempting to retrieve cache information on non-existent collection is not an error
-// and should return an empty array of query shapes.
-var missingCollection = db.jstests_query_cache_missing;
-missingCollection.drop();
-assert.eq(0, getShapes(missingCollection).length,
-          'planCacheListQueryShapes should return empty array on non-existent collection');
-
-// Retrieve query shapes from the test collection
-// Number of shapes should match queries executed by multi-plan runner.
-var shapes = getShapes();
-assert.eq(1, shapes.length, 'unexpected number of shapes in planCacheListQueryShapes result');
-assert.eq({query: queryA1, sort: sortA1, projection: projectionA1}, shapes[0],
-          'unexpected query shape returned from planCacheListQueryShapes');
-
-
-
-//
-// Tests for planCacheClear (one query shape)
-//
-
-// Invalid key should be a no-op.
-t.runCommand('planCacheClear', {query: {unknownfield: 1}});
-assert.eq(1, getShapes().length, 'removing unknown query should not affecting exisiting entries');
-
-// Run a new query shape and drop it from the cache
-assert.eq(1, t.find({a: 2, b: 2}).itcount(), 'unexpected document count');
-assert.eq(2, getShapes().length, 'unexpected cache size after running 2nd query');
-assert.commandWorked(t.runCommand('planCacheClear', {query: {a: 1, b: 1}}));
-assert.eq(1, getShapes().length, 'unexpected cache size after dropping 2nd query from cache');
-
-
-
-//
-// Tests for planCacheListPlans
-//
-
-// Utility function to list plans for a query.
-function getPlans(query, sort, projection) {
-    var key = {query: query, sort: sort, projection: projection};
-    var res = t.runCommand('planCacheListPlans', key);
-    assert.commandWorked(res, 'planCacheListPlans(' + tojson(key, '', true) + ' failed');
-    assert(res.hasOwnProperty('plans'), 'plans missing from planCacheListPlans(' +
-           tojson(key, '', true) + ') result');
-    return res.plans;
-}
-
-// Invalid key should be an error.
-assert.eq(0, getPlans({unknownfield: 1}, {}, {}),
-          'planCacheListPlans should return empty results on unknown query shape');
-
-// Retrieve plans for valid cache entry.
-var plans = getPlans(queryA1, sortA1, projectionA1);
-assert.eq(2, plans.length, 'unexpected number of plans cached for query');
-
-// Print every plan
-// Plan details/feedback verified separately in section after Query Plan Revision tests.
-print('planCacheListPlans result:');
-for (var i = 0; i < plans.length; i++) {
-    print('plan ' + i + ': ' + tojson(plans[i]));
-}
-
-
-
-//
-// Tests for planCacheClear
-//
-
-// Drop query cache. This clears all cached queries in the collection.
-res = t.runCommand('planCacheClear');
-print('planCacheClear() = ' + tojson(res));
-assert.commandWorked(res, 'planCacheClear failed');
-assert.eq(0, getShapes().length, 'plan cache should be empty after successful planCacheClear()');
-
-
-
-//
-// Query Plan Revision
-// http://docs.mongodb.org/manual/core/query-plans/#query-plan-revision
-// As collections change over time, the query optimizer deletes the query plan and re-evaluates
-// after any of the following events:
-// - The collection receives 1,000 write operations.
-// - The reIndex rebuilds the index.
-// - You add or drop an index.
-// - The mongod process restarts.
-//
-
-// Case 1: The collection receives 1,000 write operations.
-// Steps:
-//     Populate cache. Cache should contain 1 key after running query.
-//     Insert 1000 documents.
-//     Cache should be cleared.
-assert.eq(1, t.find(queryA1, projectionA1).sort(sortA1).itcount(), 'unexpected document count');
-assert.eq(1, getShapes().length, 'plan cache should not be empty after query');
-for (var i = 0; i < 1000; i++) {
-    t.save({b: i});
-}
-assert.eq(0, getShapes().length, 'plan cache should be empty after adding 1000 documents.');
-
-// Case 2: The reIndex rebuilds the index.
-// Steps:
-//     Populate the cache with 1 entry.
-//     Run reIndex on the collection.
-//     Confirm that cache is empty.
-assert.eq(1, t.find(queryA1, projectionA1).sort(sortA1).itcount(), 'unexpected document count');
-assert.eq(1, getShapes().length, 'plan cache should not be empty after query');
-res = t.reIndex();
-print('reIndex result = ' + tojson(res));
-assert.eq(0, getShapes().length, 'plan cache should be empty after reIndex operation');
-
-// Case 3: You add or drop an index.
-// Steps:
-//     Populate the cache with 1 entry.
-//     Add an index.
-//     Confirm that cache is empty.
-assert.eq(1, t.find(queryA1, projectionA1).sort(sortA1).itcount(), 'unexpected document count');
-assert.eq(1, getShapes().length, 'plan cache should not be empty after query');
-t.ensureIndex({b: 1});
-assert.eq(0, getShapes().length, 'plan cache should be empty after adding index');
-
-// Case 4: The mongod process restarts
-// Not applicable.
-
-
-
-//
-// Tests for plan reason and feedback in planCacheListPlans
-//
-
-// Generate more plans for test query by adding indexes (compound and sparse).
-// This will also clear the plan cache.
-t.ensureIndex({a: -1}, {sparse: true});
-t.ensureIndex({a: 1, b: 1});
-
-// Implementation note: feedback stats is calculated after 20 executions.
-// See PlanCacheEntry::kMaxFeedback.
-var numExecutions = 100;
-var queryA3B3 = {a: 3, b: 3};
-for (var i = 0; i < numExecutions; i++) {
-    assert.eq(0, t.find(queryA3B3, projectionA1).sort(sortA1).itcount(), 'query failed');
-}
-
-plans = getPlans(queryA3B3, sortA1, projectionA1);
-
-// This should be obvious but feedback is available only for the first (winning) plan.
-print('planCacheListPlans result (after adding indexes and completing 20 executions):');
-for (var i = 0; i < plans.length; i++) {
-    print('plan ' + i + ': ' + tojson(plans[i]));
-    assert.gt(plans[i].reason.score, 0, 'plan ' + i + ' score is invalid');
-    if (i > 0) {
-        assert.lte(plans[i].reason.score, plans[i-1].reason.score,
-                   'plans not sorted by score in descending order. ' +
-                   'plan ' + i + ' has a score that is greater than that of the previous plan');
-    }
-    assert(plans[i].reason.stats.hasOwnProperty('type'), 'no stats inserted for plan ' + i);
-}
-
-// feedback meaningful only for plan 0
-// feedback is capped at 20
-//
-// This assertion relies on the condition that the plan cache feedback mechanism
-// has not evicted the cache entry. In order for this to be reliable, we must be
-// sure that the plan scores the same each time it is run. We can be sure of this
-// because:
-//   1) The plan will produce zero results. This means that the productivity will
-//   always be zero, and in turn the score will always be the same.
-//   2) The plan hits EOF quickly. This means that it will be cached despite
-//   returning zero results.
-assert.eq(20, plans[0].feedback.nfeedback, 'incorrect nfeedback');
-assert.gt(plans[0].feedback.averageScore, 0, 'invalid average score');
-
-
-
-//
-// Tests for shell helpers
-//
-
-// Reset collection data and indexes.
-t.drop();
-var n = 200;
-for (var i = 0; i < n; i++) {
-    t.save({a:i, b: i});
-}
-t.ensureIndex({a: 1});
-t.ensureIndex({b: 1});
-t.ensureIndex({a: 1, b: 1});
-
-// Repopulate plan cache with 3 query shapes.
-var queryB = {a: {$gte: 0}, b: {$gte: 0}};
-var projectionB = {_id: 0, b: 1};
-var sortB = {b: -1};
-assert.eq(n, t.find(queryB, projectionB).sort(sortB).itcount(), 'unexpected document count');
-assert.eq(n, t.find(queryB, projectionB).itcount(), 'unexpected document count');
-assert.eq(n, t.find(queryB).sort(sortB).itcount(), 'unexpected document count');
-assert.eq(n, t.find(queryB).itcount(), 'unexpected document count');
-assert.eq(4, getShapes().length, 'unexpected number of query shapes in plan cache');
-
-//
-// PlanCache.getName
-//
-
-var planCache = t.getPlanCache();
-assert.eq(t.getName(), planCache.getName(), 'name of plan cache should match collection');
-
-//
-// PlanCache.help
-//
-planCache.help();
-
-//
-// shellPrint
-//
-
-print('plan cache:');
-print(planCache);
-
-//
-// collection.getPlanCache().listQueryShapes
-//
-
-missingCollection.drop();
-// should return empty array on non-existent collection.
-assert.eq(0, missingCollection.getPlanCache().listQueryShapes().length,
-          'collection.getPlanCache().listQueryShapes() should return empty results ' +
-          'on non-existent collection');
-assert.eq(getShapes(), planCache.listQueryShapes(),
-          'unexpected collection.getPlanCache().listQueryShapes() shell helper result');
-
-//
-// collection.getPlanCache().getPlansByQuery
-//
-
-// should return empty array on non-existent query shape.
-assert.eq(0, planCache.getPlansByQuery({unknownfield: 1}).length,
-          'collection.getPlanCache().getPlansByQuery() should return empty results ' +
-          'on non-existent collection');
-// should error on missing required field query.
-assert.throws(function() { planCache.getPlansByQuery() });
-
-// Invoke with various permutations of required (query) and optional (projection, sort) arguments.
-assert.eq(getPlans(queryB, sortB, projectionB), planCache.getPlansByQuery(queryB, projectionB,
-                                                                          sortB),
-          'plans from collection.getPlanCache().getPlansByQuery() different from command result');
-assert.eq(getPlans(queryB, {}, projectionB), planCache.getPlansByQuery(queryB, projectionB),
-          'plans from collection.getPlanCache().getPlansByQuery() different from command result');
-assert.eq(getPlans(queryB, sortB, {}), planCache.getPlansByQuery(queryB, undefined, sortB),
-          'plans from collection.getPlanCache().getPlansByQuery() different from command result');
-assert.eq(getPlans(queryB, {}, {}), planCache.getPlansByQuery(queryB),
-          'plans from collection.getPlanCache().getPlansByQuery() different from command result');
-
-// getPlansByQuery() will also accept a single argument with the query shape object
-// as an alternative to specifying the query, sort and projection parameters separately.
-// Format of query shape object:
-// {
-//     query: <query>,
-//     projection: <projection>,
-//     sort: <sort>
-// }
-var shapeB = {query: queryB, projection: projectionB, sort: sortB};
-assert.eq(getPlans(queryB, sortB, projectionB),
-          planCache.getPlansByQuery(shapeB),
-          'collection.getPlanCache().getPlansByQuery() did not accept query shape object');
-
-// Should return empty array on missing or extra fields in query shape object.
-// The entire invalid query shape object will be passed to the command
-// as the 'query' component which will result in the server returning an empty
-// array of plans.
-assert.eq(0, planCache.getPlansByQuery({query: queryB}).length,
-          'collection.getPlanCache.getPlansByQuery should return empty results on ' +
-          'incomplete query shape');
-assert.eq(0, planCache.getPlansByQuery({query: queryB, sort: sortB,
-                                        projection: projectionB,
-                                        unknown_field: 1}).length,
-          'collection.getPlanCache.getPlansByQuery should return empty results on ' +
-          'invalid query shape');
-
-
-
-//
-// collection.getPlanCache().clearPlansByQuery
-//
-
-// should not error on non-existent query shape.
-planCache.clearPlansByQuery({unknownfield: 1});
-// should error on missing required field query.
-assert.throws(function() { planCache.clearPlansByQuery() });
-
-// Invoke with various permutations of required (query) and optional (projection, sort) arguments.
-planCache.clearPlansByQuery(queryB, projectionB, sortB);
-assert.eq(3, getShapes().length,
-          'query shape not dropped after running collection.getPlanCache().clearPlansByQuery()');
-
-planCache.clearPlansByQuery(queryB, projectionB);
-assert.eq(2, getShapes().length,
-          'query shape not dropped after running collection.getPlanCache().clearPlansByQuery()');
-
-planCache.clearPlansByQuery(queryB, undefined, sortB);
-assert.eq(1, getShapes().length,
-          'query shape not dropped after running collection.getPlanCache().clearPlansByQuery()');
-
-planCache.clearPlansByQuery(queryB);
-assert.eq(0, getShapes().length,
-          'query shape not dropped after running collection.getPlanCache().clearPlansByQuery()');
-
-// clearPlansByQuery() will also accept a single argument with the query shape object
-// as an alternative to specifying the query, sort and projection parameters separately.
-// Format of query shape object:
-// {
-//     query: <query>,
-//     projection: <projection>,
-//     sort: <sort>
-// }
-
-// Repopulate cache
-assert.eq(n, t.find(queryB, projectionB).sort(sortB).itcount(), 'unexpected document count');
-
-// Clear using query shape object.
-planCache.clearPlansByQuery(shapeB);
-assert.eq(0, getShapes().length,
-          'collection.getPlanCache().clearPlansByQuery() did not accept query shape object');
-
-// Should not error on missing or extra fields in query shape object.
-planCache.clearPlansByQuery({query: queryB});
-planCache.clearPlansByQuery({query: queryB, sort: sortB, projection: projectionB,
-                             unknown_field: 1});
-
-
-
-//
-// collection.getPlanCache().clear
-//
-
-// Should not error on non-existent collection.
-missingCollection.getPlanCache().clear();
-// Re-populate plan cache with 1 query shape.
-assert.eq(n, t.find(queryB, projectionB).sort(sortB).itcount(), 'unexpected document count');
-assert.eq(1, getShapes().length, 'plan cache should not be empty after running cacheable query');
-// Clear cache.
-planCache.clear();
-assert.eq(0, getShapes().length, 'plan cache not empty after clearing');
-
-
-
-//
-// explain and plan cache
-// Running explain should not mutate the plan cache.
-//
-
-planCache.clear();
-
-// MultiPlanRunner explain
-var multiPlanRunnerExplain = t.find(queryB, projectionB).sort(sortB).explain(true);
-
-print('multi plan runner explain = ' + tojson(multiPlanRunnerExplain));
-
-assert.eq(0, getShapes().length, 'explain should not mutate plan cache');
-
-
-
-
-//
-// SERVER-12796: Plans for queries that return zero
-// results should not be cached.
-//
-
-t.drop();
-
-t.ensureIndex({a: 1});
-t.ensureIndex({b: 1});
-
-for (var i = 0; i < 200; i++) {
-    t.save({a: 1, b: 1});
-}
-t.save({a: 2, b: 2});
-
-// A query with zero results that does not hit EOF should not be cached...
-assert.eq(0, t.find({c: 0}).itcount(), 'unexpected count');
-assert.eq(0, getShapes().length, 'unexpected number of query shapes in plan cache');
-
-// ...but a query with zero results that hits EOF will be cached.
-assert.eq(0, t.find({a: 3, b: 3}).itcount(), 'unexpected count');
-assert.eq(1, getShapes().length, 'unexpected number of query shapes in plan cache');
-
-// A query that returns results but does not hit EOF will also be cached.
-assert.eq(200, t.find({a: {$gte: 0}, b:1}).itcount(), 'unexpected count');
-assert.eq(2, getShapes().length, 'unexpected number of query shapes in plan cache');
diff --git a/jstests/core/plan_cache_list_plans.js b/jstests/core/plan_cache_list_plans.js
new file mode 100644
index 00000000000..4e90531da25
--- /dev/null
+++ b/jstests/core/plan_cache_list_plans.js
@@ -0,0 +1,74 @@
+// Test the planCacheListPlans command.
+
+var t = db.jstests_plan_cache_list_plans;
+t.drop();
+
+// Utility function to list plans for a query.
+function getPlans(query, sort, projection) {
+    var key = {query: query, sort: sort, projection: projection};
+    var res = t.runCommand('planCacheListPlans', key);
+    assert.commandWorked(res, 'planCacheListPlans(' + tojson(key, '', true) + ' failed');
+    assert(res.hasOwnProperty('plans'), 'plans missing from planCacheListPlans(' +
+           tojson(key, '', true) + ') result');
+    return res.plans;
+}
+
+t.save({a: 1, b: 1});
+t.save({a: 1, b: 2});
+t.save({a: 1, b: 2});
+t.save({a: 2, b: 2});
+
+// We need two indices so that the MultiPlanRunner is executed.
+t.ensureIndex({a: 1});
+t.ensureIndex({a: 1, b:1});
+
+// Invalid key should be an error.
+assert.eq(0, getPlans({unknownfield: 1}, {}, {}),
+          'planCacheListPlans should return empty results on unknown query shape');
+
+// Create a cache entry.
+assert.eq(1, t.find({a: 1, b: 1}, {_id: 0, a: 1}).sort({a: -1}).itcount(),
+          'unexpected document count');
+
+// Retrieve plans for valid cache entry.
+var plans = getPlans({a: 1, b: 1}, {a: -1}, {_id: 0, a: 1});
+assert.eq(2, plans.length, 'unexpected number of plans cached for query');
+
+// Print every plan
+// Plan details/feedback verified separately in section after Query Plan Revision tests.
+print('planCacheListPlans result:');
+for (var i = 0; i < plans.length; i++) {
+    print('plan ' + i + ': ' + tojson(plans[i]));
+}
+
+//
+// Tests for plan reason and feedback in planCacheListPlans
+//
+
+// Generate more plans for test query by adding indexes (compound and sparse).
+// This will also clear the plan cache.
+t.ensureIndex({a: -1}, {sparse: true});
+t.ensureIndex({a: 1, b: 1});
+
+// Implementation note: feedback stats is calculated after 20 executions.
+// See PlanCacheEntry::kMaxFeedback.
+var numExecutions = 100;
+for (var i = 0; i < numExecutions; i++) {
+    assert.eq(0, t.find({a: 3, b: 3}, {_id: 0, a: 1}).sort({a: -1}).itcount(), 'query failed');
+}
+
+plans = getPlans({a: 3, b: 3}, {a: -1}, {_id: 0, a: 1});
+
+// This should be obvious but feedback is available only for the first (winning) plan.
+print('planCacheListPlans result (after adding indexes and completing 20 executions):');
+for (var i = 0; i < plans.length; i++) {
+    print('plan ' + i + ': ' + tojson(plans[i]));
+    assert.gt(plans[i].reason.score, 0, 'plan ' + i + ' score is invalid');
+    if (i > 0) {
+        assert.lte(plans[i].reason.score, plans[i-1].reason.score,
+                   'plans not sorted by score in descending order. ' +
+                   'plan ' + i + ' has a score that is greater than that of the previous plan');
+    }
+    assert(plans[i].reason.stats.hasOwnProperty('type'), 'no stats inserted for plan ' + i);
+}
+
diff --git a/jstests/core/plan_cache_list_shapes.js b/jstests/core/plan_cache_list_shapes.js
new file mode 100644
index 00000000000..c22d7caa2e4
--- /dev/null
+++ b/jstests/core/plan_cache_list_shapes.js
@@ -0,0 +1,50 @@
+// Test the planCacheListQueryShapes command, which returns a list of query shapes
+// for the queries currently cached in the collection.
+
+var t = db.jstests_plan_cache_list_shapes;
+t.drop();
+
+// Utility function to list query shapes in cache.
+function getShapes(collection) {
+    if (collection == undefined) {
+        collection = t;
+    }
+    var res = collection.runCommand('planCacheListQueryShapes');
+    print('planCacheListQueryShapes() = ' + tojson(res));
+    assert.commandWorked(res, 'planCacheListQueryShapes failed');
+    assert(res.hasOwnProperty('shapes'), 'shapes missing from planCacheListQueryShapes result');
+    return res.shapes;
+}
+
+// Attempting to retrieve cache information on non-existent collection is not an error
+// and should return an empty array of query shapes.
+var missingCollection = db.jstests_query_cache_missing;
+missingCollection.drop();
+assert.eq(0, getShapes(missingCollection).length,
+          'planCacheListQueryShapes should return empty array on non-existent collection');
+
+t.save({a: 1, b: 1});
+t.save({a: 1, b: 2});
+t.save({a: 1, b: 2});
+t.save({a: 2, b: 2});
+
+// We need two indices so that the MultiPlanRunner is executed.
+t.ensureIndex({a: 1});
+t.ensureIndex({a: 1, b: 1});
+
+// Run a query.
+assert.eq(1, t.find({a: 1, b: 1}, {_id: 1, a: 1}).sort({a: -1}).itcount(),
+          'unexpected document count');
+
+// We now expect the two indices to be compared and a cache entry to exist.
+// Retrieve query shapes from the test collection
+// Number of shapes should match queries executed by multi-plan runner.
+var shapes = getShapes();
+assert.eq(1, shapes.length, 'unexpected number of shapes in planCacheListQueryShapes result');
+assert.eq({query: {a: 1, b: 1}, sort: {a: -1}, projection: {_id: 1, a: 1}}, shapes[0],
+          'unexpected query shape returned from planCacheListQueryShapes');
+
+// Running a different query shape should cause another entry to be cached.
+assert.eq(1, t.find({a: 1, b: 1}).itcount(), 'unexpected document count');
+shapes = getShapes();
+assert.eq(2, shapes.length, 'unexpected number of shapes in planCacheListQueryShapes result');
diff --git a/jstests/core/plan_cache_shell_helpers.js b/jstests/core/plan_cache_shell_helpers.js
new file mode 100644
index 00000000000..9ac9554ef00
--- /dev/null
+++ b/jstests/core/plan_cache_shell_helpers.js
@@ -0,0 +1,201 @@
+// Test the shell helpers which wrap the plan cache commands.
+
+var t = db.jstests_plan_cache_shell_helpers;
+t.drop();
+
+// Utility function to list query shapes in cache.
+function getShapes(collection) {
+    if (collection == undefined) {
+        collection = t;
+    }
+    var res = collection.runCommand('planCacheListQueryShapes');
+    print('planCacheListQueryShapes() = ' + tojson(res));
+    assert.commandWorked(res, 'planCacheListQueryShapes failed');
+    assert(res.hasOwnProperty('shapes'), 'shapes missing from planCacheListQueryShapes result');
+    return res.shapes;
+}
+// Utility function to list plans for a query.
+function getPlans(query, sort, projection) {
+    var key = {query: query, sort: sort, projection: projection};
+    var res = t.runCommand('planCacheListPlans', key);
+    assert.commandWorked(res, 'planCacheListPlans(' + tojson(key, '', true) + ' failed');
+    assert(res.hasOwnProperty('plans'), 'plans missing from planCacheListPlans(' +
+           tojson(key, '', true) + ') result');
+    return res.plans;
+}
+
+// Add data an indices.
+var n = 200;
+for (var i = 0; i < n; i++) {
+    t.save({a:i, b: -1, c: 1});
+}
+t.ensureIndex({a: 1});
+t.ensureIndex({b: 1});
+
+// Populate plan cache.
+var queryB = {a: {$gte: 199}, b: -1};
+var projectionB = {_id: 0, b: 1};
+var sortC = {c: -1};
+assert.eq(1, t.find(queryB, projectionB).sort(sortC).itcount(), 'unexpected document count');
+assert.eq(1, t.find(queryB, projectionB).itcount(), 'unexpected document count');
+assert.eq(1, t.find(queryB).sort(sortC).itcount(), 'unexpected document count');
+assert.eq(1, t.find(queryB).itcount(), 'unexpected document count');
+assert.eq(4, getShapes().length, 'unexpected number of query shapes in plan cache');
+
+//
+// PlanCache.getName
+//
+
+var planCache = t.getPlanCache();
+assert.eq(t.getName(), planCache.getName(), 'name of plan cache should match collection');
+
+//
+// PlanCache.help
+//
+planCache.help();
+
+//
+// shellPrint
+//
+
+print('plan cache:');
+print(planCache);
+
+//
+// collection.getPlanCache().listQueryShapes
+//
+
+var missingCollection = db.jstests_plan_cache_missing;
+missingCollection.drop();
+// should return empty array on non-existent collection.
+assert.eq(0, missingCollection.getPlanCache().listQueryShapes().length,
+          'collection.getPlanCache().listQueryShapes() should return empty results ' +
+          'on non-existent collection');
+assert.eq(getShapes(), planCache.listQueryShapes(),
+          'unexpected collection.getPlanCache().listQueryShapes() shell helper result');
+
+//
+// collection.getPlanCache().getPlansByQuery
+//
+
+// should return empty array on non-existent query shape.
+assert.eq(0, planCache.getPlansByQuery({unknownfield: 1}).length,
+          'collection.getPlanCache().getPlansByQuery() should return empty results ' +
+          'on non-existent collection');
+// should error on missing required field query.
+assert.throws(function() { planCache.getPlansByQuery() });
+
+// Invoke with various permutations of required (query) and optional (projection, sort) arguments.
+assert.eq(getPlans(queryB, sortC, projectionB), planCache.getPlansByQuery(queryB, projectionB,
+                                                                          sortC),
+          'plans from collection.getPlanCache().getPlansByQuery() different from command result');
+assert.eq(getPlans(queryB, {}, projectionB), planCache.getPlansByQuery(queryB, projectionB),
+          'plans from collection.getPlanCache().getPlansByQuery() different from command result');
+assert.eq(getPlans(queryB, sortC, {}), planCache.getPlansByQuery(queryB, undefined, sortC),
+          'plans from collection.getPlanCache().getPlansByQuery() different from command result');
+assert.eq(getPlans(queryB, {}, {}), planCache.getPlansByQuery(queryB),
+          'plans from collection.getPlanCache().getPlansByQuery() different from command result');
+
+// getPlansByQuery() will also accept a single argument with the query shape object
+// as an alternative to specifying the query, sort and projection parameters separately.
+// Format of query shape object:
+// {
+//     query: <query>,
+//     projection: <projection>,
+//     sort: <sort>
+// }
+var shapeB = {query: queryB, projection: projectionB, sort: sortC};
+assert.eq(getPlans(queryB, sortC, projectionB),
+          planCache.getPlansByQuery(shapeB),
+          'collection.getPlanCache().getPlansByQuery() did not accept query shape object');
+
+// Should return empty array on missing or extra fields in query shape object.
+// The entire invalid query shape object will be passed to the command
+// as the 'query' component which will result in the server returning an empty
+// array of plans.
+assert.eq(0, planCache.getPlansByQuery({query: queryB}).length,
+          'collection.getPlanCache.getPlansByQuery should return empty results on ' +
+          'incomplete query shape');
+assert.eq(0, planCache.getPlansByQuery({query: queryB, sort: sortC,
+                                        projection: projectionB,
+                                        unknown_field: 1}).length,
+          'collection.getPlanCache.getPlansByQuery should return empty results on ' +
+          'invalid query shape');
+
+
+
+//
+// collection.getPlanCache().clearPlansByQuery
+//
+
+// should not error on non-existent query shape.
+planCache.clearPlansByQuery({unknownfield: 1});
+// should error on missing required field query.
+assert.throws(function() { planCache.clearPlansByQuery() });
+
+// Invoke with various permutations of required (query) and optional (projection, sort) arguments.
+planCache.clearPlansByQuery(queryB, projectionB);
+assert.eq(3, getShapes().length,
+          'query shape not dropped after running collection.getPlanCache().clearPlansByQuery()');
+
+planCache.clearPlansByQuery(queryB, undefined, sortC);
+assert.eq(2, getShapes().length,
+          'query shape not dropped after running collection.getPlanCache().clearPlansByQuery()');
+
+planCache.clearPlansByQuery(queryB);
+assert.eq(1, getShapes().length,
+          'query shape not dropped after running collection.getPlanCache().clearPlansByQuery()');
+
+planCache.clear();
+assert.eq(0, getShapes().length, 'plan cache not empty');
+
+// clearPlansByQuery() will also accept a single argument with the query shape object
+// as an alternative to specifying the query, sort and projection parameters separately.
+// Format of query shape object:
+// {
+//     query: <query>,
+//     projection: <projection>,
+//     sort: <sort>
+// }
+
+// Repopulate cache
+assert.eq(1, t.find(queryB).sort(sortC).itcount(), 'unexpected document count');
+
+// Clear using query shape object.
+planCache.clearPlansByQuery({query: queryB, projection: {}, sort: sortC});
+assert.eq(0, getShapes().length,
+          'collection.getPlanCache().clearPlansByQuery() did not accept query shape object');
+
+// Should not error on missing or extra fields in query shape object.
+planCache.clearPlansByQuery({query: queryB});
+planCache.clearPlansByQuery({query: queryB, sort: sortC, projection: projectionB,
+                             unknown_field: 1});
+
+
+
+//
+// collection.getPlanCache().clear
+//
+
+// Should not error on non-existent collection.
+missingCollection.getPlanCache().clear();
+// Re-populate plan cache with 1 query shape.
+assert.eq(1, t.find(queryB, projectionB).sort(sortC).itcount(), 'unexpected document count');
+assert.eq(1, getShapes().length, 'plan cache should not be empty after running cacheable query');
+// Clear cache.
+planCache.clear();
+assert.eq(0, getShapes().length, 'plan cache not empty after clearing');
+
+//
+// explain and plan cache
+// Running explain should not mutate the plan cache.
+//
+
+planCache.clear();
+
+// MultiPlanRunner explain
+var multiPlanRunnerExplain = t.find(queryB, projectionB).sort(sortC).explain(true);
+
+print('multi plan runner explain = ' + tojson(multiPlanRunnerExplain));
+
+assert.eq(0, getShapes().length, 'explain should not mutate plan cache');
diff --git a/jstests/core/plan_cache_ties.js b/jstests/core/plan_cache_ties.js
new file mode 100644
index 00000000000..edb16c0b18b
--- /dev/null
+++ b/jstests/core/plan_cache_ties.js
@@ -0,0 +1,47 @@
+// SERVER-13675: Plans that tie should not be cached.
+
+var t = db.jstests_plan_cache_ties;
+t.drop();
+
+// Utility function to list query shapes in cache.
+function getShapes(collection) {
+    if (collection == undefined) {
+        collection = t;
+    }
+    var res = collection.runCommand('planCacheListQueryShapes');
+    print('planCacheListQueryShapes() = ' + tojson(res));
+    assert.commandWorked(res, 'planCacheListQueryShapes failed');
+    assert(res.hasOwnProperty('shapes'), 'shapes missing from planCacheListQueryShapes result');
+    return res.shapes;
+}
+
+t.ensureIndex({a: 1});
+t.ensureIndex({b: 1});
+
+for (var i = 0; i < 200; i++) {
+    t.save({a: 1, b: 1});
+}
+t.save({a: 2, b: 2});
+
+// A query with zero results that does not hit EOF should not be cached.
+assert.eq(0, t.find({c: 0}).itcount(), 'unexpected count');
+assert.eq(0, getShapes().length, 'unexpected number of query shapes in plan cache');
+
+// A query that hits EOF but still results in a tie should not be cached.
+assert.eq(0, t.find({a: 3, b: 3}).itcount(), 'unexpected count');
+assert.eq(0, getShapes().length, 'unexpected number of query shapes in plan cache');
+
+// A query that returns results but leads to a tie should not be cached.
+assert.eq(1, t.find({a: 2, b: 2}).itcount(), 'unexpected count');
+assert.eq(0, getShapes().length, 'unexpected number of query shapes in plan cache');
+
+// With a new index and tweaked data, we deliver a new query that should not tie. Check that
+// this one gets cached.
+t.ensureIndex({a: 1, b: 1});
+for (var i = 0; i < 3; i++) {
+    t.save({a: 2, b: 1});
+    t.save({a: 1, b: 2});
+}
+
+assert.eq(1, t.find({a: 2, b: 2}).itcount(), 'unexpected count');
+assert.eq(1, getShapes().length, 'unexpected number of query shapes in plan cache');
diff --git a/src/mongo/db/query/multi_plan_runner.cpp b/src/mongo/db/query/multi_plan_runner.cpp
index 4547b92e3e2..709e08d8414 100644
--- a/src/mongo/db/query/multi_plan_runner.cpp
+++ b/src/mongo/db/query/multi_plan_runner.cpp
@@ -388,15 +388,12 @@ namespace mongo {
             }
         }
 
-        // Store the choice we just made in the cache. We do
-        // not cache the query if:
-        //   1) The query is of a type that is not safe to cache, or
-        //   2) the winning plan did not actually produce any results,
-        //   without hitting EOF. In this case, we have no information to
-        //   suggest that this plan is good.
-        const PlanStageStats* bestStats = _ranking->stats.vector()[0];
-        if (PlanCache::shouldCacheQuery(*_query)
-            && (!_alreadyProduced.empty() || bestStats->common.isEOF)) {
+        // Store the choice we just made in the cache. In order to do so,
+        //  1) the query must be of a type that is safe to cache, and
+        //  2) two or more plans cannot have tied for the win. Caching in the
+        //  case of ties can cause successive queries of the same shape to use
+        //  a bad index.
+        if (PlanCache::shouldCacheQuery(*_query) && !_ranking->tieForBest) {
             Database* db = cc().database();
             verify(NULL != db);
             Collection* collection = db->getCollection(_query->ns());
diff --git a/src/mongo/db/query/plan_ranker.cpp b/src/mongo/db/query/plan_ranker.cpp
index e2ac018a67e..01dc6d3cd90 100644
--- a/src/mongo/db/query/plan_ranker.cpp
+++ b/src/mongo/db/query/plan_ranker.cpp
@@ -27,6 +27,7 @@
  */
 
 #include <algorithm>
+#include <math.h>
 #include <vector>
 #include <utility>
 
@@ -107,6 +108,14 @@ namespace mongo {
         std::stable_sort(scoresAndCandidateindices.begin(), scoresAndCandidateindices.end(),
                          scoreComparator);
 
+        // Determine whether plans tied for the win.
+        if (scoresAndCandidateindices.size() > 1) {
+            double bestScore = scoresAndCandidateindices[0].first;
+            double runnerUpScore = scoresAndCandidateindices[1].first;
+            static const double epsilon = 1e-10;
+            why->tieForBest = fabs(bestScore - runnerUpScore) < epsilon;
+        }
+
         // Update results in 'why'
         // Stats and scores in 'why' are sorted in descending order by score.
         why->stats.clear();
diff --git a/src/mongo/db/query/plan_ranker.h b/src/mongo/db/query/plan_ranker.h
index 1f0f1779b19..973429c0609 100644
--- a/src/mongo/db/query/plan_ranker.h
+++ b/src/mongo/db/query/plan_ranker.h
@@ -86,6 +86,9 @@ namespace mongo {
      * and used by the CachedPlanRunner to compare expected performance with actual.
      */
     struct PlanRankingDecision {
+
+        PlanRankingDecision() : tieForBest(false) { }
+
         /**
          * Make a deep copy.
          */
@@ -98,6 +101,7 @@ namespace mongo {
             }
             decision->scores = scores;
             decision->candidateOrder = candidateOrder;
+            decision->tieForBest = tieForBest;
             return decision;
         }
 
@@ -116,6 +120,13 @@ namespace mongo {
         // candidates[candidateOrder[1]] followed by
         // candidates[candidateOrder[2]], ...
         std::vector<size_t> candidateOrder;
+
+        // Did two plans tie for best?
+        //
+        // NOTE: Reading this is the only reliable way to determine if there was a tie,
+        // because the scores kept inside the PlanRankingDecision do not incorporate
+        // the EOF bonus.
+        bool tieForBest;
     };
 
 }  // namespace mongo