[SERVER-13066] Negations over multikey fields do not use index Created: 05/Mar/14  Updated: 11/Jul/16  Resolved: 04/Apr/14

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.0-rc0
Fix Version/s: 2.6.1, 2.7.0

Type: Improvement Priority: Major - P3
Reporter: Michael Kennedy Assignee: David Storch
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
Backwards Compatibility: Major Change
Backport Completed:
Participants:

 Description   
Issue Status as of April 15, 2014

ISSUE SUMMARY
Negation predicates like $ne or $not did not make use of an index if the index was a "multikey" index (where the indexed fields contained arrays).

USER IMPACT
Queries with negation predicates were scanning the entire collection, which is inefficient and can cause disruption in the working set.

WORKAROUNDS
In some cases, the query can be rewritten (for example with $gt and $lt predicates) to eliminate the negation predicate.

RESOLUTION
Multikey index usage has been enabled for negation predicates.

AFFECTED VERSIONS
All recent production releases up to and including 2.6.0 are affected.

PATCHES
The patch is included in the 2.6.1 production release.

Original description

This query does not seem to use an index at all even when it exists:

db.Book.find({ "Ratings" : { "$ne" : null, "$not" : { "$size" : 0 } } } )

Notice the DB (referenced below), has an index:

       {
               "v" : 1,
               "key" : {
                       "Ratings" : 1
               },
               "name" : "Ratings_1",
               "ns" : "BookStore.Book"
       }

Yet, when you explain the query, you see basic cursor:

> db.Book.find({ "Ratings" : { "$ne" : null, "$not" : { "$size" : 0 } } } ).expl
ain()
{
        "cursor" : "BasicCursor",
        "isMultiKey" : false,
        "n" : 270171,
        "nscannedObjects" : 271380,
        "nscanned" : 271380,
        "nscannedObjectsAllPlans" : 271380,
        "nscannedAllPlans" : 271380,
        "scanAndOrder" : false,
        "indexOnly" : false,
        "nYields" : 2120,
        "nChunkSkips" : 0,
        "millis" : 559,
        "server" : "WIN-7S2IMPQ2TOE:27017",
        "filterSet" : false
}

To see this in action, open the BookStore.zip file from this issue:
https://jira.mongodb.org/browse/SERVER-13065



 Comments   
Comment by Githook User [ 09/Apr/14 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-13066 allow negations to use multikey indices

(cherry picked from commit 7aa932a23fd1c429d7b3d8cbd96d865526c149c9)
Branch: v2.6
https://github.com/mongodb/mongo/commit/423ebc231ab8234ac3b2c8d11ca3759b0e99d19f

Comment by David Storch [ 03/Apr/14 ]

This issue is now resolved in master and will be backported to the 2.6 branch after 2.6.0 ships.

Comment by Githook User [ 03/Apr/14 ]

Author:

{u'username': u'dstorch', u'name': u'David Storch', u'email': u'david.storch@10gen.com'}

Message: SERVER-13066 allow negations to use multikey indices
Branch: master
https://github.com/mongodb/mongo/commit/7aa932a23fd1c429d7b3d8cbd96d865526c149c9

Comment by Michael Kennedy [ 07/Mar/14 ]

Thank you for addressing this.

Comment by David Storch [ 07/Mar/14 ]

Hi Michael,

Thanks for the detailed bug report! It looks like the problem is that the negation predicates are not using the index because the index is multikey. I'm going to move the "fixVersion" to "Needs Triage" so that our engineering team can decide on a schedule for working on this.

Best,
Dave

Comment by Michael Kennedy [ 05/Mar/14 ]

Sorry I forgot to add this when I submitted:

I tested this both on 2.4.9 and 2.6.0_rc0.

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