Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-37132

Negation of $in with regex can incorrectly plan from the cache, leading to missing query results

    • Type: Icon: Bug Bug
    • Resolution: Fixed
    • Priority: Icon: Critical - P2 Critical - P2
    • 3.4.19, 3.6.9, 4.0.4, 4.1.4
    • Affects Version/s: 3.2.21, 3.4.17, 3.6.7, 4.0.2, 4.1.2
    • Component/s: Querying
    • Fully Compatible
    • ALL
    • v4.0, v3.6, v3.4, v3.2
    • Hide
      (function() {
          "use strict";
      
          const coll = db.c;
          coll.drop();
          assert.commandWorked(coll.createIndex({a: 1}));
          assert.commandWorked(coll.createIndex({a: 1, b: 1}));
          assert.commandWorked(coll.insert({a: "foo"}));
      
          assert.eq(1, coll.find({a: {$not: {$in: [32, 33]}}}).itcount());
          assert.eq(1, coll.find({a: {$not: {$in: [32, 33]}}}).itcount());
          assert.eq(1, coll.find({a: {$not: {$in: [34, /bar/]}}}).itcount());
      })();
      
      Show
      (function() { "use strict"; const coll = db.c; coll.drop(); assert.commandWorked(coll.createIndex({a: 1})); assert.commandWorked(coll.createIndex({a: 1, b: 1})); assert.commandWorked(coll.insert({a: "foo"})); assert.eq(1, coll.find({a: {$not: {$in: [32, 33]}}}).itcount()); assert.eq(1, coll.find({a: {$not: {$in: [32, 33]}}}).itcount()); assert.eq(1, coll.find({a: {$not: {$in: [34, /bar/]}}}).itcount()); })();
    • Query 2018-10-08
    • 11

      A negation of a $in with a regex cannot be indexed. This is enforced by the query planner's index selection phase here:

      https://github.com/mongodb/mongo/blob/bd38c69f5e6dc3136d20505d49f034c0927bf3e2/src/mongo/db/query/planner_ixselect.cpp#L467-L473

      However, a negated $in with a regex, and one without a regex, are considered the same shape. This can be seen by verifying that they have the same queryHash, which was added to explain output in SERVER-36527:

      MongoDB Enterprise > var hash1 = db.c.find({a: {$not: {$in: [32, 33]}}}).explain().queryPlanner.queryHash
      MongoDB Enterprise > var hash2 = db.c.find({a: {$not: {$in: [34, /bar/]}}}).explain().queryPlanner.queryHash
      MongoDB Enterprise > assert.eq(hash1, hash2)
      

      As a result, the latter query can incorrectly use a plan cache entry created by the former query. The resulting plan has incorrect bounds which can erroneously exclude matching documents. A likely fix would be to add a discriminator to the plan cache key so that $not-$in predicates with regexes are encoded differently from $not-$in predicates without regexes.

            Assignee:
            bernard.gorman@mongodb.com Bernard Gorman
            Reporter:
            david.storch@mongodb.com David Storch
            Votes:
            0 Vote for this issue
            Watchers:
            10 Start watching this issue

              Created:
              Updated:
              Resolved: