SERVER-5580 track paths containing empty or single-element arrays as multikey

This is required in order for the planner to enforce correct
covering behavior.

1 files changed, 78 insertions, 27 deletions

diff --git a/src/mongo/db/index/btree_key_generator_test.cpp b/src/mongo/db/index/btree_key_generator_test.cpp
index d8bb9e64024..a884b5ce619 100644
--- a/src/mongo/db/index/btree_key_generator_test.cpp
+++ b/src/mongo/db/index/btree_key_generator_test.cpp
@@ -345,8 +345,8 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromArraySubelementComplex) {
     BSONObj genKeysFrom = fromjson("{a:[{b:[2]}]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': 2}"));
-    // Both the 'a' and 'a.b' arrays contain a single element.
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    // Both the 'a' and 'a.b' arrays contain a single element, so they are considered multikey.
+    MultikeyPaths expectedMultikeyPaths{{0U, 1U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -414,17 +414,17 @@ TEST(BtreeKeyGeneratorTest, GetKeysArrayEmpty) {
     genKeysFrom = fromjson("{a: [1]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1}"));
-    expectedMultikeyPaths[0].clear();
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
-    genKeysFrom = fromjson("{a: null}");
+    genKeysFrom = fromjson("{a: []}");
     expectedKeys.clear();
-    expectedKeys.insert(fromjson("{'': null}"));
+    expectedKeys.insert(fromjson("{'': undefined}"));
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
-    genKeysFrom = fromjson("{a: []}");
+    genKeysFrom = fromjson("{a: null}");
     expectedKeys.clear();
-    expectedKeys.insert(fromjson("{'': undefined}"));
+    expectedKeys.insert(fromjson("{'': null}"));
+    expectedMultikeyPaths[0].clear();
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -443,7 +443,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleEmptyArray) {
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': undefined, '': undefined}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}, {0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -459,7 +459,6 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromMultiEmptyArray) {
     genKeysFrom = fromjson("{a: 1, b: [1]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1, '': 1}"));
-    expectedMultikeyPaths[1].clear();
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a: 1, b: []}");
@@ -473,7 +472,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromNestedEmptyArray) {
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': null}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -482,7 +481,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromMultiNestedEmptyArray) {
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': null, '': null}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}, {0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -491,7 +490,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromUnevenNestedEmptyArray) {
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': undefined, '': null}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}, {0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[{b: 1}]}");
@@ -502,6 +501,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromUnevenNestedEmptyArray) {
     genKeysFrom = fromjson("{a:[{b: []}]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': {b:[]}, '': undefined}"));
+    expectedMultikeyPaths[1].insert(1U);
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -510,7 +510,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromReverseUnevenNestedEmptyArray) {
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': null, '': undefined}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}, {0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -520,7 +520,7 @@ TEST(BtreeKeyGeneratorTest, SparseReverseUnevenNestedEmptyArray) {
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': null, '': undefined}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}, std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}, {0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 }
 
@@ -533,6 +533,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromSparseEmptyArray) {
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 
     genKeysFrom = fromjson("{a:[]}");
+    expectedMultikeyPaths[0].insert(0U);
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 
     genKeysFrom = fromjson("{a:[{c:1}]}");
@@ -548,6 +549,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromSparseEmptyArraySecond) {
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 
     genKeysFrom = fromjson("{a:[]}");
+    expectedMultikeyPaths[1].insert(0U);
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 
     genKeysFrom = fromjson("{a:[{c:1}]}");
@@ -559,7 +561,7 @@ TEST(BtreeKeyGeneratorTest, SparseNonObjectMissingNestedField) {
     BSONObj keyPattern = fromjson("{'a.b': 1}");
     BSONObj genKeysFrom = fromjson("{a:[]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 
     genKeysFrom = fromjson("{a:[1]}");
@@ -568,7 +570,6 @@ TEST(BtreeKeyGeneratorTest, SparseNonObjectMissingNestedField) {
     genKeysFrom = fromjson("{a:[1,{b:1}]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1}"));
-    expectedMultikeyPaths = {{0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths, sparse));
 }
 
@@ -626,11 +627,16 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromDoubleIndexedArrayIndex) {
     genKeysFrom = fromjson("{a:[]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': null}"));
+    // Here the first "0" path component acts like a regular field name rather than a positional
+    // path element, since the 0th array index does not exist. Therefore, path component "a" is
+    // considered multikey.
+    expectedMultikeyPaths = {{0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[[]]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': undefined}"));
+    expectedMultikeyPaths = {std::set<size_t>{}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -645,31 +651,76 @@ TEST(BtreeKeyGeneratorTest, GetKeysFromObjectWithinArray) {
     genKeysFrom = fromjson("{a:[{b:[1]}]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1}"));
+    expectedMultikeyPaths = {{2U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[{b:[[1]]}]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': [1]}"));
+    expectedMultikeyPaths = {{2U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[{b:1}]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1}"));
+    // Path component "0" refers to an array which is subsequently expanded, so it is considered
+    // multikey.
+    expectedMultikeyPaths = {{1U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[{b:[1]}]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': 1}"));
+    expectedMultikeyPaths = {{1U, 2U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[{b:[[1]]}]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': [1]}"));
+    expectedMultikeyPaths = {{1U, 2U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 
     genKeysFrom = fromjson("{a:[[{b:[]}]]}");
     expectedKeys.clear();
     expectedKeys.insert(fromjson("{'': undefined}"));
+    expectedMultikeyPaths = {{1U, 2U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysPositionalElementIsExpandedArray) {
+    BSONObj keyPattern = fromjson("{'a.0.b': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[[{b:1}, {b:2}]]}");
+    BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
+    expectedKeys.insert(fromjson("{'': 1}"));
+    expectedKeys.insert(fromjson("{'': 2}"));
+    MultikeyPaths expectedMultikeyPaths{{1U}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysTrailingPositionalElementIsSingletonArray) {
+    BSONObj keyPattern = fromjson("{'a.b.c.3': 1}");
+    BSONObj genKeysFrom = fromjson("{a:{b:{c:[0,1,2,[3]]}}}");
+    BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
+    expectedKeys.insert(fromjson("{'': [3]}"));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysTrailingPositionalElementIsEmptyArray) {
+    BSONObj keyPattern = fromjson("{'a.b.c.3': 1}");
+    BSONObj genKeysFrom = fromjson("{a:{b:{c:[0,1,2,[]]}}}");
+    BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
+    expectedKeys.insert(fromjson("{'': undefined}"));
+    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
+}
+
+TEST(BtreeKeyGeneratorTest, GetKeysManyPositionalElementsComplex) {
+    BSONObj keyPattern = fromjson("{'a.0.1.2.b.0': 1}");
+    BSONObj genKeysFrom = fromjson("{a:[[1, [1, 2, [{b: [[], 2]}]]], 1]}");
+    BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
+    expectedKeys.insert(fromjson("{'': undefined}"));
+    MultikeyPaths expectedMultikeyPaths{{3U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -741,7 +792,7 @@ TEST(BtreeKeyGeneratorTest, GetKeys2DArray) {
     BSONObj genKeysFrom = fromjson("{a: [[2]]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': [2]}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -780,7 +831,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternMissingElement) {
     BSONObj genKeysFrom = fromjson("{a: [{'2': 5}]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': 5}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -790,7 +841,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray) {
     BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5]]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': null}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -810,7 +861,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray3) {
     BSONObj genKeysFrom = fromjson("{a: [{'0': 1, '1': 2, '2': 5}]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': 5}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -820,7 +871,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysPositionalKeyPatternNestedArray4) {
     BSONObj genKeysFrom = fromjson("{a: [{b: [[1, 2, 5]]}]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': null}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U, 1U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -840,7 +891,7 @@ TEST(BtreeKeyGeneratorTest, GetNullKeyNestedArray) {
     BSONObj genKeysFrom = fromjson("{a: [[1, 2, 5]]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': null}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -912,7 +963,7 @@ TEST(BtreeKeyGeneratorTest, GetKeysFirstPathPieceEmpty2) {
     expectedKeys.insert(fromjson("{'': 1}"));
     expectedKeys.insert(fromjson("{'': 2}"));
     expectedKeys.insert(fromjson("{'': 3}"));
-    MultikeyPaths expectedMultikeyPaths{{1U}};
+    MultikeyPaths expectedMultikeyPaths{{0U, 1U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -930,7 +981,7 @@ TEST(BtreeKeyGeneratorTest, KeyPattern_a_0_b_Extracts_b_ElementInsideSingleton2D
     BSONObj genKeysFrom = fromjson("{a: [[{b: 1}]]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': 1}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{1U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -960,7 +1011,7 @@ TEST(BtreeKeyGeneratorTest, KeyPattern_a_0_0_b_Extracts_b_ElementInsideSingleton
     BSONObj genKeysFrom = fromjson("{a: [[[ {b: 1} ]]]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': 1}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{2U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -980,7 +1031,7 @@ TEST(BtreeKeyGeneratorTest, KeyPattern_a_0_0_b_ExtractsNullFrom4DArray) {
     BSONObj genKeysFrom = fromjson("{a: [[[[ {b: 1} ]]]]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': null}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{2U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }
 
@@ -989,7 +1040,7 @@ TEST(BtreeKeyGeneratorTest, PositionalKeyPatternNestedArrays5) {
     BSONObj genKeysFrom = fromjson("{a: [{b: [1, 2]}]}");
     BSONObjSet expectedKeys = SimpleBSONObjComparator::kInstance.makeBSONObjSet();
     expectedKeys.insert(fromjson("{'': 2}"));
-    MultikeyPaths expectedMultikeyPaths{std::set<size_t>{}};
+    MultikeyPaths expectedMultikeyPaths{{0U}};
     ASSERT(testKeygen(keyPattern, genKeysFrom, expectedKeys, expectedMultikeyPaths));
 }