title: MongoDB extremely slow at counting null values (or {$exists: false})
body: <p>I have a Mongo server running on an VPS with 16GB of memory (although probably with slow IO using magnetic disks).</p>
  
  <p>I have a collection of around 35 million records which doesn't fit into main memory (<code>db.stats()</code> reports a <code>size</code> of 35GB and a <code>storageSize</code> of 14GB), however the 1.7GB reported for <code>totalIndexSize</code> should comfortably fit there.</p>
  
  <p>There is particular field <code>bg</code> I'm querying over which can be present with value <code>true</code> or absent entirely (please no discussions about whether this is the best data representation – I still think Mongo is behaving weirdly). This field is indexed with a non-sparse index with a reported size of 146MB.</p>
  
  <p>I'm using the WiredTiger storage engine with a default cache size (so it should be around 8GB).</p>
  
  <p>I'm trying to count the number of records missing the <code>bg</code> field.</p>
  
  <p>Counting <code>true</code> values is tolerably fast (a few seconds):</p>
  
  <pre><code>&gt; db.entities.find({bg: true}).count()
  8300677
  </code></pre>
  
  <p>However the query for missing values is extremely slow (around 5 minutes):</p>
  
  <pre><code>&gt; db.entities.find({bg: null}).count()
  27497706
  </code></pre>
  
  <p>To my eyes, <code>explain()</code> looks ok:</p>
  
  <pre><code>&gt; db.entities.find({bg: null}).explain()
  {
      "queryPlanner" : {
          "plannerVersion" : 1,
          "namespace" : "testdb.entities",
          "indexFilterSet" : false,
          "parsedQuery" : {
              "bg" : {
                  "$eq" : null
              }
          },
          "winningPlan" : {
              "stage" : "FETCH",
              "filter" : {
                  "bg" : {
                      "$eq" : null
                  }
              },
              "inputStage" : {
                  "stage" : "IXSCAN",
                  "keyPattern" : {
                      "bg" : 1
                  },
                  "indexName" : "bg_1",
                  "isMultiKey" : false,
                  "direction" : "forward",
                  "indexBounds" : {
                      "bg" : [
                          "[null, null]"
                      ]
                  }
              }
          },
          "rejectedPlans" : [ ]
      },
      "serverInfo" : {
          "host" : "mongo01",
          "port" : 27017,
          "version" : "3.0.3",
          "gitVersion" : "b40106b36eecd1b4407eb1ad1af6bc60593c6105"
      },
      "ok" : 1
  }
  </code></pre>
  
  <p>However the query remains stubbornly slow, even after repeated calls. Other count queries for different values are fast:</p>
  
  <pre><code>&gt; db.entities.find({bg: "foo"}).count()
  0
  &gt; db.entities.find({}).count()
  35798383
  </code></pre>
  
  <p>I find this kind of strange, since my understanding is that missing fields in non-sparse indexes are simply stored as <code>null</code>, so the count query with <code>null</code> should be similar to counting an actual value (or maybe up to three times for three times as many positive values, if it has to count more index entries or something). Indeed, <a href="https://stackoverflow.com/a/22683751/1711188">this answer</a> reports vast speed improvements over similar queries involving <code>null</code> values and <code>.count()</code>. The only point of differentiation I can think of is WiredTiger.</p>
  
  <p>Can anyone explain why is my query to count null values so slow or what I can do to fix it (apart from doing the obvious subtraction of the <code>true</code> counts from the total, which would work fine but wouldn't satisfy my curiosity)?</p>