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

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Critical - P2
    • Resolution: Fixed
    • Affects Version/s: 3.2.21, 3.4.17, 3.6.7, 4.0.2, 4.1.2
    • Fix Version/s: 3.4.19, 3.6.9, 4.0.4, 4.1.4
    • Component/s: Querying
    • Labels:
    • Backwards Compatibility:
      Fully Compatible
    • Operating System:
      ALL
    • Backport Requested:
      v4.0, v3.6, v3.4, v3.2
    • Steps To Reproduce:
      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()); })();
    • Sprint:
      Query 2018-10-08
    • Linked BF Score:
      11

      Description

      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.

        Attachments

          Activity

            People

            • Votes:
              0 Vote for this issue
              Watchers:
              11 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: