[SERVER-14311] skipping of index keys is not accounted for in plan ranking by the index scan stage Created: 19/Jun/14  Updated: 11/Jul/16  Resolved: 11/Jul/14

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 2.6.2, 2.6.3
Fix Version/s: 2.6.4, 2.7.4

Type: Bug Priority: Critical - P2
Reporter: Asya Kamsky Assignee: David Storch
Resolution: Done Votes: 1
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
Related
related to SERVER-14423 Plans which fetch different numbers o... Closed
is related to SERVER-13675 Plans with differing performance can ... Closed
is related to SERVER-14961 Plan ranker favors intersection plans... Closed
is related to SERVER-15152 When evaluating plans, some index can... Closed
Tested
Operating System: ALL
Backport Completed:
Participants:

 Description   
Issue Status as of Jun 20, 2014

ISSUE SUMMARY
The plan ranker does not account for work spent skipping index keys when ranking plans against each other. For example, if the following indexes are present:

{a:1, b:1}
{a:1, x:1, b:1}

It is cheaper to use index {a:1, b:1} for queries with predicates over fields a and b, because for index {a:1, x:1, b:1} it may be necessary to skip many keys due to the interceding x field.

Another example where this issue appears is the following:

Indexes: {a:1}, {b:1, c:1}
Data: {a: i, b: i, c: i} for increasing values of i
Query: {a: 9, b: {$ne: 10}, c: 9}

Plans using the two indices tie in this case. This can cause the plan ranker to use index {b: 1, c: 1} rather than the obviously better {a: 1} index.

USER IMPACT
An inferior plan may be chosen, which may have a negative performance impact. See also related issues SERVER-13675 and SERVER-14525 for cases where plans tie.

WORKAROUNDS
Hinting on a different index may avert the performance impact.

AFFECTED VERSIONS
MongoDB 2.6 production releases up to 2.6.3 are affected by this issue.

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

RESOLUTION DETAILS
The bug arises from not counting a btree key skip as a unit of work. The resolution is therefore to properly account for the work done skipping keys in order to break the plan ranking tie.

Original description

Possible a missed variant of SERVER-13675 the inferior plan is picked out of two raced plans.



 Comments   
Comment by Githook User [ 21/Jul/14 ]

Author:

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

Message: SERVER-14311 account for key skips in plan ranking by returning NEED_TIME in the index scan stage
Branch: v2.6
https://github.com/mongodb/mongo/commit/270880374ec6a117235eefbcfc9ccdbd505acfe2

Comment by Atul Kachru [ 16/Jul/14 ]

Setting CAP Verification : Needed.

Comment by Githook User [ 11/Jul/14 ]

Author:

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

Message: SERVER-14311 fix plan ranking dbtest
Branch: master
https://github.com/mongodb/mongo/commit/f6a6dec8f14ef75980d1512bb6d5e30fab6b73db

Comment by Githook User [ 11/Jul/14 ]

Author:

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

Message: SERVER-14311 account for key skips in plan ranking by returning NEED_TIME in the index scan stage
Branch: master
https://github.com/mongodb/mongo/commit/f3ba3590ce1ca1bf8f7fbb13ad8311a52df9c176

Comment by Wei Kong [ 27/Jun/14 ]

Which release will this fix be available?

Comment by Ian Daniel [ 20/Jun/14 ]

Hi Wei,

I have raised the priority of this ticket to P2.

Regards,
Ian

Comment by Wei Kong [ 19/Jun/14 ]

Any reason this ticket is p3 while SERVER-13675 is p2? The impact is the same.

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