[SERVER-24320] Planner can attempt to use invalid index when using plan cache due to plan cache key / MatchExpression sorting inconsistency Created: 31/May/16  Updated: 20/Nov/16  Resolved: 26/Jul/16

Status: Closed
Project: Core Server
Component/s: Geo, Querying
Affects Version/s: 3.2.6, 3.3.6
Fix Version/s: 3.2.10, 3.3.11

Type: Bug Priority: Major - P3
Reporter: David Storch Assignee: Tess Avitabile (Inactive)
Resolution: Done Votes: 0
Labels: code-and-test
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
is related to SERVER-17659 Query plan cache support for partial ... Closed
Backwards Compatibility: Fully Compatible
Operating System: ALL
Backport Completed:
Steps To Reproduce:

(function() {
    "use strict";
 
    db.c.drop();
    db.c.createIndex({a: "2dsphere", b: 1});
    db.c.createIndex({b: 1});
 
    db.c.insert({a: {type: "Point", coordinates: [-79.88635540008511, 32.76497530165182]}, b: 10});
    db.c.insert({a: [-79.88635540008511, 32.76497530165182], b: 12});
 
    var geoPredicate = {
        $and: [
            {b: {$gte: 6}},
            {
              a: {
                  $within: {
                      $polygon: [
                          [-79.97488975524868, 32.76497530165182],
                          [-79.88635540008511, 32.76497530165182],
                          [-79.88635540008511, 32.72617288558777],
                          [-79.97488975524868, 32.72617288558777]
                      ]
                  }
              }
            },
            {
              a: {
                  $within: {
                      $centerSphere:
                          [[-79.86978928637699, 32.75469246872076], 0.000757002271006813]
                  }
              }
            }
        ]
    };
 
   // First invocation should succeed and generate a plan cache entry.
   assert.eq(2, db.c.find(geoPredicate).itcount());
 
   // Second invocation is pulled from the cache and trips the verify()!
   assert.eq(2, db.c.find(geoPredicate).itcount());
})();

Sprint: Query 16 (06/24/16)
Participants:

 Description   

The 2dsphere geo query in the repro steps trips the following verify():

https://github.com/mongodb/mongo/blob/r3.3.6/src/mongo/db/query/index_bounds_builder.cpp#L596

This affects the 3.2 branch as well as 3.3.x development versions. 3.0.x versions are not affected.



 Comments   
Comment by Githook User [ 18/Aug/16 ]

Author:

{u'username': u'tessavitabile', u'name': u'Tess Avitabile', u'email': u'tess.avitabile@mongodb.com'}

Message: SERVER-24320 PlanCacheIndexTree should have same sort order as MatchExpression used to generate plan cache key
Branch: v3.2
https://github.com/mongodb/mongo/commit/cb380a1911e5f3ad1b9e8203f866adcf239e8be1

Comment by Githook User [ 26/Jul/16 ]

Author:

{u'username': u'tessavitabile', u'name': u'Tess Avitabile', u'email': u'tess.avitabile@mongodb.com'}

Message: SERVER-24320 PlanCacheIndexTree should have same sort order as MatchExpression used to generate plan cache key
Branch: master
https://github.com/mongodb/mongo/commit/8f6e2270bb10ea77728eae881c552ce23c7e87f9

Comment by David Storch [ 09/Jun/16 ]

Another update: I believe this was first broken in the 3.1.3 development release as part of the plan cache work done in support of partial indexes. Specifically, this problem was introduced by https://github.com/mongodb/mongo/commit/88f6f4733bca7c615dd6fedcfc93a24cfa68372a under SERVER-17659. This work separated how we generate the plan cache key from how we sort the MatchExpression AST (which is required in order to correctly restore plans from the plan cache). However, the discrimination between geo expression types and their different coordinate reference systems done during plan cache key generation was not correctly implemented in the new MatchExpression sorting logic here:

https://github.com/mongodb/mongo/blob/r3.3.8/src/mongo/db/query/canonical_query.cpp#L64

In addition to fixing the problem reproduced here, we should audit to ensure that there are no other discrepancies between plan cache key generation and MatchExpression sorting.

Comment by David Storch [ 09/Jun/16 ]

I've done some initial investigation and have some results to report. Read on for some of the technical details.

The $within-$polygon predicate used in the problem query is only compatible to be indexed by a "2d" index; it is intended for use with a flat geometry rather than a spherical one. This is documented here:

Only the 2d geospatial index supports the $polygon operator.

and is enforced in the query planner's index selection process here:

https://github.com/mongodb/mongo/blob/r3.3.8/src/mongo/db/query/planner_ixselect.cpp#L307-L312

A $within $polygon query always has a flat coordinate reference system, which will cause hasS2Region() to return false, thus indicating that the predicate is not compatible with the "2dsphere" index.

In the reproducing script above, the first run of the problem query indexes only the $within $centerSphere predicate and the $gte—the $within $polygon predicate is correctly left unindexed and instead is affixed as a filter to be performed after the index scan. An entry is then inserted to the plan cache with some information that should allow us to reconstitute the original plan. The problem occurs when, on execution of the second query, we attempt to construct the plan using the plan cache entry. The plan cache code is mistakenly attempting to index the $within $polygon predicate rather than the $within $centerSphere predicate. In turn, the downstream invariant check that the geo predicate being answering with a 2dsphere index has a spherical coordinate reference system is tripped!

Some more investigation will be required to determine a strategy for fixing the issue, as well as identifying the scope of the bug and possibly the original breaking commit. Please continue to watch for updates.

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