[SERVER-13104] Plan enumerator doesn't enumerate all possibilities for a nested $or Created: 07/Mar/14  Updated: 11/Jul/16  Resolved: 03/Sep/14

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.0-rc1, 2.6.4, 2.7.5
Fix Version/s: 2.6.5, 2.7.6

Type: Bug Priority: Minor - P4
Reporter: David Storch Assignee: David Storch
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-13184 2.6 should explore same number of one... Closed
is related to SERVER-13732 Predicates in top-level implicit AND ... Closed
Operating System: ALL
Backport Completed:
Participants:

 Description   

Say you have indices {a: 1} and {b: 1} and the following query:

db.coll.find({c: 1, $or: [{$and: [{a: 1}, {b: 1}]}, {a: 1}]});

Only one plan is generated for this query:

KEEP_MUTATIONS
---filter:
        $and
            $or
                $and
                    a == 1.0
                    b == 1.0
                a == 1.0
            c == 1.0
---fetched = 1
---sortedByDiskLoc = 0
---getSort = []
---Child:
------FETCH
---------filter:
                c == 1.0
---------fetched = 1
---------sortedByDiskLoc = 0
---------getSort = []
---------Child:
------------OR
---------------fetched = 0
---------------sortedByDiskLoc = 0
---------------getSort = []
---------------Child 0:
------------------FETCH
---------------------filter:
                                b == 1.0
---------------------fetched = 1
---------------------sortedByDiskLoc = 1
---------------------getSort = [{ a: 1 }, ]
---------------------Child:
------------------------IXSCAN
---------------------------keyPattern = { a: 1.0 }
---------------------------direction = 1
---------------------------bounds = field #0['a']: [1.0, 1.0]
---------------------------fetched = 0
---------------------------sortedByDiskLoc = 1
---------------------------getSort = [{ a: 1 }, ]
 
---------------Child 1:
------------------IXSCAN
---------------------keyPattern = { a: 1.0 }
---------------------direction = 1
---------------------bounds = field #0['a']: [1.0, 1.0]
---------------------fetched = 0
---------------------sortedByDiskLoc = 1
---------------------getSort = [{ a: 1 }, ]

However, there are additional plans that have not been enumerated. For example, the first child of the OR stage above could use index {b: 1}. It does not get enumerated because of how we step through the memo (see https://github.com/mongodb/mongo/blob/20a22bdf907a0e2cd60b79f242a7375d84a3ab6a/src/mongo/db/query/plan_enumerator.cpp#L1033). The outer $and only has one "top-level" choice, and we don't consider that there are multiple enumeration choices for the nested $and.



 Comments   
Comment by Githook User [ 22/Sep/14 ]

Author:

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

Message: SERVER-13104 enumerate all possibilties for $or below an $and

(cherry picked from commit aac8ba84d8fac7dc531a03c63224fdfc8cd3baa3)
Branch: v2.6
https://github.com/mongodb/mongo/commit/eed6fc90e26f7606a4cd14705ca8c873f34fed83

Comment by Githook User [ 03/Sep/14 ]

Author:

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

Message: SERVER-13104 enumerate all possibilties for $or below an $and
Branch: master
https://github.com/mongodb/mongo/commit/aac8ba84d8fac7dc531a03c63224fdfc8cd3baa3

Comment by Asya Kamsky [ 10/Mar/14 ]

Index on b doesn't help though, since a has to be checked regardless....

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