[SERVER-19999] $all with $elemMatch indexes first element regardless of predicate cardinality (regression) Created: 18/Aug/15  Updated: 07/Oct/15  Resolved: 30/Sep/15

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.10, 3.0.0
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Andrew Ryder (Inactive) Assignee: David Storch
Resolution: Duplicate Votes: 2
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
duplicates SERVER-16042 Optimise $all/$and to select smallest... Closed
Related
is related to SERVER-16256 $all clause with elemMatch uses wider... Closed
Operating System: ALL
Steps To Reproduce:
  1. Generate a database with documents containing a key/value array form, eg.

    { attr: [ { k: "low", v: 1 }, { k: "high", v: 1000 } ] }
    

    • Make sure there are two key/values, one with a high cardinality and one with a very low cardinality - in my example I use simply "high" and "low" to denote these conditions of the value ranges.
    • In my examples below there were 50,000 documents, "low" has a range of 10 (~5000 docs per bucket), while high has a range of 10000 (~5 docs per bucket).
  2. Build an index to be able to efficiently search for specific pairs, something like:

    { "attr.k":1, "attr.v":1 }
    

  3. Run a query that would be much faster if the second predicate was used:

    db.kv.find({attr:{$all:[{$elemMatch: {k: "low", v: 1}}, {$elemMatch: {k: "high", v: 1}}]}})
    

  4. Compare runtimes and explain outputs for server versions 2.6.0 (up to 2.6.9) versus 2.6.10 onwards (including 3.0).
Sprint: QuInt A (10/12/15)
Participants:

 Description   

The pattern of using key/value attributes and querying using $all and $elemMatch used to work really efficiently even when the cardinality of values for specific keys was not known. Since 2.6.10 and 3.0.* this pattern now only uses the first predicate regardless.

SERVER-16256 appears to have introduced this new behavior, essentially returning it to 2.4.* status.

Shown below are two explain(true) outputs, the first is what is seen when run on 2.6.0 -> 2.6.9... notice there are 2 possible plans in the allPlans list:

>db.kv.find({attr:{$all:[{$elemMatch: {k: "low", v: 1}}, {$elemMatch: {k: "high", v: 1024}}]}}).explain(true);
{
        "cursor" : "BtreeCursor attr.k_1_attr.v_1",
        "isMultiKey" : true,
        "n" : 2,
        "nscannedObjects" : 6,
        "nscanned" : 6,
        "nscannedObjectsAllPlans" : 17,
        "nscannedAllPlans" : 17,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 8,
        "nChunkSkips" : 0,
        "millis" : 0,
        "indexBounds" : {
                "attr.k" : [
                        [
                                "high",
                                "high"
                        ]
                ],
                "attr.v" : [
                        [
                                1024,
                                1024
                        ]
                ]
        },
        "allPlans" : [
                {
                        "cursor" : "BtreeCursor attr.k_1_attr.v_1",
                        "isMultiKey" : true,
                        "n" : 2,
                        "nscannedObjects" : 6,
                        "nscanned" : 6,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "attr.k" : [
                                        [
                                                "high",
                                                "high"
                                        ]
                                ],
                                "attr.v" : [
                                        [
                                                1024,
                                                1024
                                        ]
                                ]
                        }
                },
                {
                        "cursor" : "BtreeCursor attr.k_1_attr.v_1",
                        "isMultiKey" : true,
                        "n" : 0,
                        "nscannedObjects" : 11,
                        "nscanned" : 11,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "attr.k" : [
                                        [
                                                "low",
                                                "low"
                                        ]
                                ],
                                "attr.v" : [
                                        [
                                                1,
                                                1
                                        ]
                                ]
                        }
                }
        ],
        "server" : "Boomtime:27017",
        "filterSet" : false,
        "stats" : {
                "type" : "KEEP_MUTATIONS",
                "works" : 14,
                "yields" : 8,
                "unyields" : 8,
                "invalidates" : 0,
                "advanced" : 2,
                "needTime" : 4,
                "needFetch" : 6,
                "isEOF" : 1,
                "children" : [
                        {
                                "type" : "FETCH",
                                "works" : 13,
                                "yields" : 8,
                                "unyields" : 8,
                                "invalidates" : 0,
                                "advanced" : 2,
                                "needTime" : 4,
                                "needFetch" : 6,
                                "isEOF" : 1,
                                "alreadyHasObj" : 0,
                                "forcedFetches" : 0,
                                "matchTested" : 2,
                                "children" : [
                                        {
                                                "type" : "IXSCAN",
                                                "works" : 7,
                                                "yields" : 8,
                                                "unyields" : 8,
                                                "invalidates" : 0,
                                                "advanced" : 6,
                                                "needTime" : 0,
                                                "needFetch" : 0,
                                                "isEOF" : 1,
                                                "keyPattern" : "{ attr.k: 1.0, attr.v: 1.0 }",
                                                "isMultiKey" : 1,
                                                "boundsVerbose" : "field #0['attr.k']: [\"high\", \"high\"], field #1['attr.v']: [1024.0, 1024.0]",
                                                "yieldMovedCursor" : 0,
                                                "dupsTested" : 6,
                                                "dupsDropped" : 0,
                                                "seenInvalidated" : 0,
                                                "matchTested" : 0,
                                                "keysExamined" : 6,
                                                "children" : [ ]
                                        }
                                ]
                        }
                ]
        }
}

The second explain is what is seen for the same query on 2.6.10+ (including all of 3.0). Notice that there is now only 1 plan considered, based exclusively on the first item in the $all array:

17:46:50@test>db.kv.find({attr:{$all:[{$elemMatch: {k: "low", v: 1}}, {$elemMatch: {k: "high", v: 1024}}]}}).explain(true);
{
        "cursor" : "BtreeCursor attr.k_1_attr.v_1",
        "isMultiKey" : true,
        "n" : 2,
        "nscannedObjects" : 5138,
        "nscanned" : 5138,
        "nscannedObjectsAllPlans" : 5138,
        "nscannedAllPlans" : 5138,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 174,
        "nChunkSkips" : 0,
        "millis" : 26,
        "indexBounds" : {
                "attr.k" : [
                        [
                                "low",
                                "low"
                        ]
                ],
                "attr.v" : [
                        [
                                1,
                                1
                        ]
                ]
        },
        "allPlans" : [
                {
                        "cursor" : "BtreeCursor attr.k_1_attr.v_1",
                        "isMultiKey" : true,
                        "n" : 2,
                        "nscannedObjects" : 5138,
                        "nscanned" : 5138,
                        "scanAndOrder" : false,
                        "indexOnly" : false,
                        "nChunkSkips" : 0,
                        "indexBounds" : {
                                "attr.k" : [
                                        [
                                                "low",
                                                "low"
                                        ]
                                ],
                                "attr.v" : [
                                        [
                                                1,
                                                1
                                        ]
                                ]
                        }
                }
        ],
        "server" : "Boomtime:27017",
        "filterSet" : false,
        "stats" : {
                "type" : "KEEP_MUTATIONS",
                "works" : 5313,
                "yields" : 174,
                "unyields" : 174,
                "invalidates" : 0,
                "advanced" : 2,
                "needTime" : 5136,
                "needFetch" : 174,
                "isEOF" : 1,
                "children" : [
                        {
                                "type" : "FETCH",
                                "works" : 5313,
                                "yields" : 174,
                                "unyields" : 174,
                                "invalidates" : 0,
                                "advanced" : 2,
                                "needTime" : 5136,
                                "needFetch" : 174,
                                "isEOF" : 1,
                                "alreadyHasObj" : 0,
                                "forcedFetches" : 0,
                                "matchTested" : 2,
                                "children" : [
                                        {
                                                "type" : "IXSCAN",
                                                "works" : 5139,
                                                "yields" : 174,
                                                "unyields" : 174,
                                                "invalidates" : 0,
                                                "advanced" : 5138,
                                                "needTime" : 0,
                                                "needFetch" : 0,
                                                "isEOF" : 1,
                                                "keyPattern" : "{ attr.k: 1.0, attr.v: 1.0 }",
                                                "isMultiKey" : 1,
                                                "boundsVerbose" : "field #0['attr.k']: [\"low\", \"low\"], field #1['attr.v']: [1.0, 1.0]",
                                                "yieldMovedCursor" : 0,
                                                "dupsTested" : 5138,
                                                "dupsDropped" : 0,
                                                "seenInvalidated" : 0,
                                                "matchTested" : 0,
                                                "keysExamined" : 5138,
                                                "children" : [ ]
                                        }
                                ]
                        }
                ]
        }
}



 Comments   
Comment by David Storch [ 30/Sep/15 ]

evan@dnanexus.com, we will evaluate the risk associated with backport to the 2.6 branch, but for the moment this is only scheduled as part of the 3.0.7 patch release.

Comment by Evan Worley [ 30/Sep/15 ]

So this will not be back ported to 2.6?

Comment by David Storch [ 30/Sep/15 ]

We are currently planning on moving forward with the following option (excerpted from my previous comment):

Resolve this ticket as a dup of SERVER-16042 and then fix SERVER-16042. This is the ideal solution because it fixes the problem in all of its manifestations. However, it might be technically tricky and runs the risk of causing a regression for other unrelated queries because the plan ranker will need to evaluate a greater number of plans for $and queries. This approach may also be difficult to backport to the 3.0 or 2.6 branches.

After investigation, this approach should be relatively easy to implement, and is not too "technically tricky", It should also be backportable, at least to the 3.0 branch. Note that the planned fix will apply not only to $all-$elemMatch queries, but to any $all or $and query (including implicit $and). I am closing this ticket as a duplicate of SERVER-16042, so please watch that ticket for further updates.

Comment by Evan Worley [ 31/Aug/15 ]

Wonderful, thanks David.

Comment by David Storch [ 31/Aug/15 ]

evan@dnanexus.com, understood. We are looking to make a targeted fix that will be suitable for backport to 3.0 and 2.6. Please keep in mind, however, that we can only evaluate backport once the fix is tested and pushed to the development branch.

Comment by Evan Worley [ 31/Aug/15 ]

Thanks for all the info. I'm concerned that these fixes will not be back-ported. All of the mongo upgrades that we've done so far have required involved testing to ensure there are no major performance or functionality regressions. Given that we are on 2.6.9 now, 3.1 is probably many months away. If at all possible I would really like to see these fixes back ported at least to the 2.6 series.

Comment by David Storch [ 31/Aug/15 ]

Some more context on this ticket: When working on SERVER-16256, I discovered that we had special handling for the $all-$elemMatch construction, even through $all-$elemMatch is logically identical to a regular $and with $elemMatch children. Furthermore, this special handling was flawed in that it built the incorrect bounds. I also consider it a flawed design in that two semantically equivalent queries with different syntaxes were handled with different codepaths. The system's behavior was dependent on how the application author happened to type the query.

I see three options for how we could handle this ticket:

  1. Resolve this ticket as a dup of SERVER-16042 and then fix SERVER-16042. This is the ideal solution because it fixes the problem in all of its manifestations. However, it might be technically tricky and runs the risk of causing a regression for other unrelated queries because the plan ranker will need to evaluate a greater number of plans for $and queries. This approach may also be difficult to backport to the 3.0 or 2.6 branches.
  2. Revert the patch from SERVER-16256 in order to undo this regression. Then provide a different fix for the original bounds problem from SERVER-16256 that does not involve eliminating the special $all-$elemMatch handling. This is not preferable because 1) it means that $and is still affected by the problem and 2) we reintroduce complexity in the query engine that was cleaned up under SERVER-16256. I'll have to look into the feasibility of this option.
  3. Do nothing.

I think #1 is feasible and backportable. Some queries will be slower, but this cost should be amortized due to plan caching.

Generated at Thu Feb 08 03:52:49 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.