[SERVER-17815] Plan ranking tie breaker is computed incorrectly Created: 31/Mar/15  Updated: 19/Sep/15  Resolved: 29/Jun/15

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.10, 3.0.4
Fix Version/s: 2.6.11, 3.0.5, 3.1.6

Type: Bug Priority: Major - P3
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:
Depends
Related
Backwards Compatibility: Fully Compatible
Operating System: ALL
Backport Completed:
Sprint: Quint Iteration 3.1.2, Quint Iteration 6
Participants:

 Description   

The epsilon value used to break a tie is computed as 1 over the query knob constant for the max number of works to perform during plan ranking:

https://github.com/mongodb/mongo/blob/r3.1.0/src/mongo/db/query/plan_ranker.cpp#L209-L211

// Just enough to break a tie.
static const double epsilon = 1.0 /
     static_cast<double>(internalQueryPlanEvaluationWorks);

During plan ranking, however, the actual number of works is the max of internalQueryPlanEvaluationWorks and some fixed fraction of the collection size:

https://github.com/mongodb/mongo/blob/r3.1.0/src/mongo/db/exec/multi_plan.cpp#L199-L200

numWorks = std::max(size_t(internalQueryPlanEvaluationWorks),
       size_t(fraction * _collection->numRecords(_txn)));

The consequence is that the tie breaker can be too large. Instead of breaking a tie, it can cause an inferior plan's score to exceed a superior plan's score.



 Comments   
Comment by Githook User [ 29/Jun/15 ]

Author:

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

Message: SERVER-17815 tie breaker value should not be static in PlanRanker::scoreTree

(cherry picked from commit dcc38a627d3e4f92d9df0eaeb97739dfa0280907)
Branch: v2.6
https://github.com/mongodb/mongo/commit/0fbe8f851b1aa8b9a63e5c7e904139654134294b

Comment by Githook User [ 29/Jun/15 ]

Author:

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

Message: SERVER-17815 tie breaker value should not be static in PlanRanker::scoreTree

(cherry picked from commit dcc38a627d3e4f92d9df0eaeb97739dfa0280907)
Branch: v3.0
https://github.com/mongodb/mongo/commit/965e3b062530c2834f584d115063fd54b4329d52

Comment by Githook User [ 29/Jun/15 ]

Author:

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

Message: SERVER-17815 tie breaker value should not be static in PlanRanker::scoreTree
Branch: master
https://github.com/mongodb/mongo/commit/dcc38a627d3e4f92d9df0eaeb97739dfa0280907

Comment by David Storch [ 29/Jun/15 ]

The original fix for this problem, released with 2.6.10 and 3.0.3, was discovered to be incorrect. The user impact is that the plan ranking problem can still occur on all stable versions of the server. Re-opening pending an additional fix.

Comment by Githook User [ 10/Apr/15 ]

Author:

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

Message: SERVER-17815 ensure plan ranking tie breaker does not cause an inferior plan to win

(cherry picked from commit 122ceeaf9caca8ac1a93e1bed1a7286315aee0ab)
Branch: v2.6
https://github.com/mongodb/mongo/commit/cc61da0890124c5fd5943b38d051b1bd4a96b961

Comment by Githook User [ 10/Apr/15 ]

Author:

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

Message: SERVER-17815 ensure plan ranking tie breaker does not cause an inferior plan to win

(cherry picked from commit 122ceeaf9caca8ac1a93e1bed1a7286315aee0ab)
Branch: v3.0
https://github.com/mongodb/mongo/commit/4afd401c40072f36a5639162163c58989deb1fa0

Comment by Githook User [ 07/Apr/15 ]

Author:

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

Message: SERVER-17815 ensure plan ranking tie breaker does not cause an inferior plan to win
Branch: master
https://github.com/mongodb/mongo/commit/122ceeaf9caca8ac1a93e1bed1a7286315aee0ab

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