path: root/jstests/core/wildcard_index_multikey.js

/**
 * Tests that queries using a multikey $** index, return correct results.
 * @tags: [assumes_balancer_off]
 */
(function() {
    "use strict";

    load("jstests/aggregation/extras/utils.js");  // For arrayEq.
    load("jstests/libs/analyze_plan.js");         // For getPlanStages.

    const assertArrayEq = (l, r) => assert(arrayEq(l, r), tojson(l) + " != " + tojson(r));

    const coll = db.wildcard_multikey_index;
    coll.drop();

    // Template document which defines the 'schema' of the documents in the test collection.
    const templateDoc = {a: [], b: {c: [], d: [{e: 0}]}};
    const pathList = ["a", "b.c", "b.d.e"];

    // Insert a set of documents into the collection, based on the template document and populated
    // with an increasing sequence of values. This is to ensure that the range of values present for
    // each field in the dataset is not entirely homogeneous.
    for (let i = 0; i < 50; i++) {
        (function populateDoc(doc, value) {
            for (let key in doc) {
                if (typeof doc[key] === "object") {
                    if (Array.isArray(doc[key])) {
                        if (typeof doc[key][0] === "object") {
                            value = populateDoc(doc[key][0], value);
                        } else {
                            doc[key] = [++value, ++value];
                        }
                    } else {
                        value = populateDoc(doc[key], value);
                    }
                } else {
                    doc[key] = ++value;
                }
            }
            return value;
        })(templateDoc, i);
        assert.commandWorked(coll.insert(templateDoc));
    }

    // Set of operations which will be applied to each field in the index in turn.
    const operationList = [
        {expression: {$gte: 10}},
        {expression: {$gt: 10}},
        {expression: {$lt: 40}},
        {expression: {$lte: 40}},
        {expression: {$gt: 10, $lt: 40}},
        {expression: {$eq: 25}},
        {expression: {$in: [5, 15, 35, 40]}},
        {expression: {$elemMatch: {$gte: 10, $lte: 40}}},
    ];

    // Given a keyPattern and (optional) pathProjection, this function builds a $** index on the
    // collection and then tests each of the match expression in the 'operationList' on each indexed
    // field in turn. The 'expectedPaths' argument lists the set of paths which we expect to have
    // been indexed based on the spec; this function will confirm that only the appropriate paths
    // are present in the $** index.
    function runWildcardIndexTest(keyPattern, pathProjection, expectedPaths) {
        assert.commandWorked(coll.dropIndexes());
        assert.commandWorked(coll.createIndex(
            keyPattern, pathProjection ? {wildcardProjection: pathProjection} : {}));
        assert(expectedPaths);
        // Verify the expected behaviour for every combination of path and operator.
        for (let op of operationList) {
            for (let path of pathList) {
                const query = {[path]: op.expression};
                assertWildcardQuery(query, expectedPaths.includes(path) ? path : null);
            }
        }
    }

    // Runs a single wildcard query test. If 'expectedPath' is non-null, verifies that there is an
    // indexed solution that uses the $** index with the given path string. If 'expectedPath' is
    // null, verifies that no indexed solution was found. If 'explainStats' is non-empty, verifies
    // that the query's explain output reflects the given stats.
    function assertWildcardQuery(query, expectedPath, explainStats = {}) {
        // Explain the query, and determine whether an indexed solution is available.
        const explainOutput = coll.find(query).explain("executionStats");
        // If we expect the current path to have been excluded based on the $** keyPattern
        // or projection, confirm that no indexed solution was found.
        if (!expectedPath) {
            assert.gt(getPlanStages(explainOutput.queryPlanner.winningPlan, "COLLSCAN").length, 0);
            return;
        }
        // Verify that the winning plan uses the $** index with the expected path.
        const ixScans = getPlanStages(explainOutput.queryPlanner.winningPlan, "IXSCAN");
        assert.eq(ixScans.length, FixtureHelpers.numberOfShardsForCollection(coll));
        assert.docEq(ixScans[0].keyPattern, {"$_path": 1, [expectedPath]: 1});
        // Verify that the results obtained from the $** index are identical to a COLLSCAN.
        assertArrayEq(coll.find(query).toArray(), coll.find(query).hint({$natural: 1}).toArray());
        // Verify that the explain output reflects the given 'explainStats'.
        for (let stat in explainStats) {
            assert.eq(explainStats[stat],
                      stat.split('.').reduce((obj, i) => obj[i], explainOutput),
                      explainOutput);
        }
    }

    // Test a $** index that indexes the entire document.
    runWildcardIndexTest({'$**': 1}, null, ['a', 'b.c', 'b.d.e']);
    // Test a $** index on a single subtree.
    runWildcardIndexTest({'a.$**': 1}, null, ['a']);
    runWildcardIndexTest({'b.$**': 1}, null, ['b.c', 'b.d.e']);
    runWildcardIndexTest({'b.c.$**': 1}, null, ['b.c']);
    runWildcardIndexTest({'b.d.$**': 1}, null, ['b.d.e']);
    // Test a $** index which includes a subset of paths.
    runWildcardIndexTest({'$**': 1}, {a: 1}, ['a']);
    runWildcardIndexTest({'$**': 1}, {b: 1}, ['b.c', 'b.d.e']);
    runWildcardIndexTest({'$**': 1}, {'b.d': 1}, ['b.d.e']);
    runWildcardIndexTest({'$**': 1}, {a: 1, 'b.d': 1}, ['a', 'b.d.e']);
    // Test a $** index which excludes a subset of paths.
    runWildcardIndexTest({'$**': 1}, {a: 0}, ['b.c', 'b.d.e']);
    runWildcardIndexTest({'$**': 1}, {b: 0}, ['a']);
    runWildcardIndexTest({'$**': 1}, {'b.c': 0}, ['a', 'b.d.e']);
    runWildcardIndexTest({'$**': 1}, {a: 0, 'b.c': 0}, ['b.d.e']);

    // Sanity check that a few queries which need to be planned specially in the multikey case
    // return the correct results.
    coll.drop();
    assert.commandWorked(coll.createIndex({"$**": 1}));
    assert.commandWorked(coll.insert({a: [-5, 15]}));
    assert.eq(1, coll.find({a: {$gt: 0, $lt: 9}}).itcount());
    assert.eq(1, coll.find({a: {$gt: 0, $lt: 9}}).hint({$natural: 1}).itcount());
    assert.eq(0, coll.find({a: {$elemMatch: {$gt: 0, $lt: 9}}}).itcount());
    assert.eq(0, coll.find({a: {$elemMatch: {$gt: 0, $lt: 9}}}).hint({$natural: 1}).itcount());

    assert.commandWorked(coll.insert({b: {c: {d: [{e: {f: -5}}, {e: {f: 15}}]}}}));
    assert.eq(1, coll.find({"b.c.d.e.f": {$gt: 0, $lt: 9}}).itcount());
    assert.eq(1, coll.find({"b.c.d.e.f": {$gt: 0, $lt: 9}}).hint({$natural: 1}).itcount());
    assert.eq(0, coll.find({"b.c.d": {$elemMatch: {"e.f": {$gt: 0, $lt: 9}}}}).itcount());
    assert.eq(0,
              coll.find({"b.c.d": {$elemMatch: {"e.f": {$gt: 0, $lt: 9}}}})
                  .hint({$natural: 1})
                  .itcount());

    // Fieldname-or-array-index query tests.
    assert(coll.drop());
    assert.commandWorked(coll.createIndex({"$**": 1}));

    // Insert some documents that exhibit a mix of numeric fieldnames and array indices.
    assert.commandWorked(coll.insert({_id: 1, a: [{b: [{c: 1}]}]}));
    assert.commandWorked(coll.insert({_id: 2, a: [{b: [{c: 0}, {c: 1}]}]}));
    assert.commandWorked(coll.insert({_id: 3, a: {'0': [{b: {'1': {c: 1}}}, {d: 1}]}}));
    assert.commandWorked(coll.insert({_id: 4, a: [{b: [{1: {c: 1}}]}]}));
    assert.commandWorked(
        coll.insert({_id: 5, a: [{b: [{'1': {c: {'2': {d: [0, 1, 2, 3, {e: 1}]}}}}]}]}));

    /*
     * Multikey Metadata Keys:
     * {'': 1, '': 'a'}
     * {'': 1, '': 'a.0'}
     * {'': 1, '': 'a.b'}
     * {'': 1, '': 'a.b.1.c.2.d'}
     * Keys:
     * {'': 'a.b.c', '': 1}         // _id: 1, a,b multikey
     * {'': 'a.b.c', '': 0}         // _id: 2, a,b multikey
     * {'': 'a.b.c', '': 1}         // _id: 2, a,b multikey
     * {'': 'a.0.b.1.c', '': 1}     // _id: 3, '0, 1' are fieldnames, a.0 multikey
     * {'': 'a.0.d', '': 1}         // _id: 3, '0' is fieldname, a.0 multikey
     * {'': 'a.b.1.c', '': 1}       // _id: 4, '1' is fieldname, a,b multikey
     * {'': 'a.b.1.c.2.d', '': 0}   // _id: 5, a,b,a.b.1.c.2.d multikey, '1' is fieldname
     * {'': 'a.b.1.c.2.d', '': 1}   // _id: 5
     * {'': 'a.b.1.c.2.d', '': 2}   // _id: 5
     * {'': 'a.b.1.c.2.d', '': 3}   // _id: 5
     * {'': 'a.b.1.c.2.d.e', '': 1} // _id: 5
     */

    // Test that a query with multiple numeric path components returns all relevant documents,
    // whether the numeric path component refers to a fieldname or array index in each doc:
    //
    // _id:1 will be captured by the special fieldname-or-array-index bounds 'a.b.c', but will be
    // filtered out by the INEXACT_FETCH since it has no array index or fieldname 'b.1'.
    // _id:2 will match both 'a.0' and 'b.1' by array index.
    // _id:3 will match both 'a.0' and 'b.1' by fieldname.
    // _id:4 will match 'a.0' by array index and 'b.1' by fieldname.
    // _id:5 is not captured by the special fieldname-or-array-index bounds.
    //
    // We examine the solution's 'nReturned' versus 'totalDocsExamined' to confirm this.
    // totalDocsExamined: [_id:1, _id:2, _id:3, _id:4], nReturned: [_id:2, _id:3, _id:4]
    assertWildcardQuery({'a.0.b.1.c': 1},
                        'a.0.b.1.c',
                        {'executionStats.nReturned': 3, 'executionStats.totalDocsExamined': 4});

    // Test that we can query a specific field of an array whose fieldname is itself numeric.
    assertWildcardQuery({'a.0.1.d': 1},
                        'a.0.1.d',
                        {'executionStats.nReturned': 1, 'executionStats.totalDocsExamined': 1});

    // Test that we can query a primitive value at a specific array index.
    assertWildcardQuery({'a.0.b.1.c.2.d.3': 3},
                        'a.0.b.1.c.2.d.3',
                        {'executionStats.nReturned': 1, 'executionStats.totalDocsExamined': 1});

    // Test that a $** index can't be used for a query through more than 8 nested array indices.
    assert.commandWorked(
        coll.insert({_id: 6, a: [{b: [{c: [{d: [{e: [{f: [{g: [{h: [{i: [1]}]}]}]}]}]}]}]}]}));
    // We can query up to a depth of 8 arrays via specific indices, but not through 9 or more.
    assertWildcardQuery({'a.0.b.0.c.0.d.0.e.0.f.0.g.0.h.0.i': 1},
                        'a.0.b.0.c.0.d.0.e.0.f.0.g.0.h.0.i');
    assertWildcardQuery({'a.0.b.0.c.0.d.0.e.0.f.0.g.0.h.0.i.0': 1}, null);

    // Test that fieldname-or-array-index queries do not inappropriately trim predicates; that is,
    // all predicates on the field are added to a FETCH filter above the IXSCAN.
    assert(coll.drop());
    assert.commandWorked(coll.createIndex({"$**": 1}));

    assert.commandWorked(coll.insert({_id: 1, a: [0, 1, 2]}));
    assert.commandWorked(coll.insert({_id: 2, a: [1, 2, 3]}));
    assert.commandWorked(coll.insert({_id: 3, a: [2, 3, 4], b: [5, 6, 7]}));
    assert.commandWorked(coll.insert({_id: 4, a: [3, 4, 5], b: [6, 7, 8], c: {'0': 9}}));
    assert.commandWorked(coll.insert({_id: 5, a: [4, 5, 6], b: [7, 8, 9], c: {'0': 10}}));
    assert.commandWorked(coll.insert({_id: 6, a: [5, 6, 7], b: [8, 9, 10], c: {'0': 11}}));

    assertWildcardQuery({"a.0": {$gt: 1, $lt: 4}}, 'a.0', {'executionStats.nReturned': 2});
    assertWildcardQuery({"a.1": {$gte: 1, $lte: 4}}, 'a.1', {'executionStats.nReturned': 4});
    assertWildcardQuery({"b.2": {$in: [5, 9]}}, 'b.2', {'executionStats.nReturned': 1});
    assertWildcardQuery({"c.0": {$in: [10, 11]}}, 'c.0', {'executionStats.nReturned': 2});

    // Test that the $** index doesn't trim predicates when planning across multiple nested $and/$or
    // expressions on various fieldname-or-array-index paths.
    const trimTestQuery = {
        $or: [
            {"a.0": {$gte: 0, $lt: 3}, "a.1": {$in: [2, 3, 4]}},
            {"b.1": {$gt: 6, $lte: 9}, "c.0": {$gt: 9, $lt: 12}}
        ]
    };
    const trimTestExplain = coll.find(trimTestQuery).explain("executionStats");
    // Verify that the expected number of documents were matched, and the $** index was used.
    // Matched documents: [_id:2, _id:3, _id:5, _id:6]
    assert.eq(trimTestExplain.executionStats.nReturned, 4);
    const trimTestIxScans = getPlanStages(trimTestExplain.queryPlanner.winningPlan, "IXSCAN");
    for (let ixScan of trimTestIxScans) {
        assert.eq(ixScan.keyPattern["$_path"], 1);
    }
    // Finally, confirm that a collection scan produces the same results.
    assertArrayEq(coll.find(trimTestQuery).toArray(),
                  coll.find(trimTestQuery).hint({$natural: 1}).toArray());
})();