[SERVER-13236] Consider not enumerating index intersection solutions unless the AND is top-level Created: 17/Mar/14  Updated: 21/Oct/15  Resolved: 21/Oct/15

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.0-rc1
Fix Version/s: None

Type: Improvement Priority: Major - P3
Reporter: David Storch Assignee: David Storch
Resolution: Won't Fix 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
Participants:

 Description   

Suppose we have indices on 'a', 'b', and we receive the following query:

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

We could end up enumerating 9 possible solutions, as there are three possibilities for each branch (use 'a', use 'b', and use index intersection). If all combinations are considered than 3 * 3 = 9. This is the search space explosion problem for $or that is currently being tracked in SERVER-13184.

Regardless of the approach taken for SERVER-13184, we can mitigate the problem by not enumerating index intersection solutions if the AND is not top-level. For the example above, this would reduce the number of possibilities to 2 * 2 = 4.


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