[SERVER-13960] Queries containing $or may miss results if multiple clauses use the same index Created: 15/May/14  Updated: 11/Jul/16  Resolved: 30/May/14

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.1, 2.7.0
Fix Version/s: 2.6.2, 2.7.2

Type: Bug Priority: Major - P3
Reporter: J Rassi Assignee: David Storch
Resolution: Done Votes: 2
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
Duplicate
is duplicated by SERVER-14030 Indexes causes incorrect queries on 2... Closed
is duplicated by SERVER-14084 Adding compound index changes result ... Closed
Operating System: ALL
Backport Completed:
Participants:

 Description   
Issue Status as of June 2, 2014

ISSUE SUMMARY
Given a query with an $or operator where:

  1. one of the $or clauses includes a regex, $mod, $type, $elemMatch, $exists, geo, or range predicate with a non-simple type (like {a: {$gt: {b: 3}}}), and
  2. that predicate has an index which it can use,

then the query may miss results from one of the $or clauses. For example:

db.foo.ensureIndex({name : 1})
db.foo.insert({_id : 1, name : "Alice"})
db.foo.insert({_id : 2, name : "Bob"})
db.foo.find({$or : [{name : /^(B|C)/}, {name : "Alice"}]})
{ "_id" : 2, "name" : "Bob" }

USER IMPACT
Significant user impact: query results may be incomplete.

WORKAROUNDS
One workaround is to use the $natural operator to force a collection scan, which may have a significant performance impact:

db.foo.find({$or : [{name : /^(B|^C)/}, {name : "Alice"}]}).hint({$natural : 1})
{ "_id" : 1, "name" : "Alice" }
{ "_id" : 2, "name" : "Bob" }

If query rewrite is possible, using the $in operator provides another workaround:

db.foo.find({name : {$in : [/^(B|^C)/, "Alice"]}})
{ "_id" : 1, "name" : "Alice" }
{ "_id" : 2, "name" : "Bob" }

AFFECTED VERSIONS
MongoDB production releases 2.6.0 and 2.6.1 are affected by this issue.

FIX VERSION
The fix is included in the 2.6.2 production release.

RESOLUTION DETAILS
The issue stems from an incorrect filter being affixed to FETCH and IXSCAN query solution nodes, which would filter the result set too narrowly. When an $or clause has inexact bounds, we must filter the results after performing the index scan. The filter should be an $or of all the predicates assigned to the corresponding index. The fix was to ensure that the filter includes all necessary predicates.

Original description

For certain types of query predicates that include the $or operator, the query planner can output a plan with a semantically incorrect query execution tree. Results may be omitted if this query plan is selected.

Specifically, if an OR expression contains at least one clause that generates "exact" bounds on an index and at least one clause that generates "inexact" bounds on the same index, then the resulting filter constructed for the index scan may only include the "inexact" predicates. In this case, results unique to the "exact" clauses will not be returned.

To reproduce:

> db.foo.ensureIndex({name:1})
{
	"createdCollectionAutomatically" : true,
	"numIndexesBefore" : 1,
	"numIndexesAfter" : 2,
	"ok" : 1
}
> db.foo.insert({_id:0, name:"thomas"})
WriteResult({ "nInserted" : 1 })
> db.foo.insert({_id:1, name:"alexandra"})
WriteResult({ "nInserted" : 1 })
> db.foo.find({$or:[{name:"thomas"}, {name:/^alexand(er|ra)/}]})
{ "_id" : 1, "name" : "alexandra" } // INCORRECT (results missing)
> db.foo.find({$or:[{name:"thomas"}, {name:/^alexand(er|ra)/}]}).hint({$natural:1})
{ "_id" : 0, "name" : "thomas" }    // CORRECT
{ "_id" : 1, "name" : "alexandra" }

Original report from mongodb-user: <https://groups.google.com/forum/#!topic/mongodb-user/psQan0UKWDc>.



 Comments   
Comment by Githook User [ 01/Jun/14 ]

Author:

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

Message: SERVER-13960 bug fixes for OR with inexact predicates

(cherry picked from commit 3242afb803a5cc523f16c2c63c3ee1dfc10a5671)
Branch: v2.6
https://github.com/mongodb/mongo/commit/5900e7a03183f052bf5f2f17f177c65062ac75aa

Comment by Githook User [ 01/Jun/14 ]

Author:

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

Message: SERVER-13960 fix access planning for OR with inexact child predicates

Includes a refactor of QueryPlannerAccess::processIndexScans(...) which makes this
change saner.

(cherry picked from commit bee249ac8907cc9de6b19ba87c3fcb074d84b1a3)
Branch: v2.6
https://github.com/mongodb/mongo/commit/3f02f1a6a157eda94f8d10edbeb4148a11a4bdc1

Comment by Githook User [ 30/May/14 ]

Author:

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

Message: SERVER-13960 bug fixes for OR with inexact predicates
Branch: master
https://github.com/mongodb/mongo/commit/3242afb803a5cc523f16c2c63c3ee1dfc10a5671

Comment by Githook User [ 30/May/14 ]

Author:

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

Message: SERVER-13960 fix access planning for OR with inexact child predicates

Includes a refactor of QueryPlannerAccess::processIndexScans(...) which makes this
change saner.
Branch: master
https://github.com/mongodb/mongo/commit/bee249ac8907cc9de6b19ba87c3fcb074d84b1a3

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