diff options
author | Samantha Ritter <samantha.ritter@10gen.com> | 2014-02-27 16:29:46 -0500 |
---|---|---|
committer | Matt Kangas <matt.kangas@mongodb.com> | 2014-02-28 16:14:50 -0500 |
commit | cd62080dcb036e83f8fca6d68d9bcab67bf7a21c (patch) | |
tree | 9ce907222e4b0e618f30eae65aac7477e3bc2fb9 | |
parent | d43eb9202ff065364e0eac9a6b601186afd37fa5 (diff) | |
download | mongo-cd62080dcb036e83f8fca6d68d9bcab67bf7a21c.tar.gz |
SERVER-12557 allow exists queries to use an index
Signed-off-by: Matt Kangas <matt.kangas@mongodb.com>
-rw-r--r-- | jstests/covered_index_simple_3.js | 65 | ||||
-rw-r--r-- | jstests/exists2.js | 2 | ||||
-rw-r--r-- | jstests/exists6.js | 120 | ||||
-rw-r--r-- | jstests/exists9.js | 3 | ||||
-rw-r--r-- | jstests/existsa.js | 28 | ||||
-rw-r--r-- | jstests/existsb.js | 76 | ||||
-rw-r--r-- | src/mongo/db/query/index_bounds_builder.cpp | 54 | ||||
-rw-r--r-- | src/mongo/db/query/index_bounds_builder_test.cpp | 53 | ||||
-rw-r--r-- | src/mongo/db/query/indexability.h | 1 | ||||
-rw-r--r-- | src/mongo/db/query/query_planner_test.cpp | 45 |
10 files changed, 327 insertions, 120 deletions
diff --git a/jstests/covered_index_simple_3.js b/jstests/covered_index_simple_3.js index dfb11003a74..ee586540ea4 100644 --- a/jstests/covered_index_simple_3.js +++ b/jstests/covered_index_simple_3.js @@ -1,55 +1,52 @@ // Simple covered index query test with a unique sparse index -var coll = db.getCollection("covered_simple_3") -coll.drop() +var coll = db.getCollection("covered_simple_3"); +coll.drop(); for (i=0;i<10;i++) { - coll.insert({foo:i}) + coll.insert({foo:i}); } for (i=0;i<5;i++) { - coll.insert({bar:i}) + coll.insert({bar:i}); } -coll.insert({foo:"string"}) -coll.insert({foo:{bar:1}}) -coll.insert({foo:null}) -coll.ensureIndex({foo:1}, {sparse:true, unique:true}) +coll.insert({foo:"string"}); +coll.insert({foo:{bar:1}}); +coll.insert({foo:null}); +coll.ensureIndex({foo:1}, {sparse:true, unique:true}); // Test equality with int value -var plan = coll.find({foo:1}, {foo:1, _id:0}).hint({foo:1}).explain() -assert.eq(true, plan.indexOnly, "simple.3.1 - indexOnly should be true on covered query") -assert.eq(0, plan.nscannedObjects, "simple.3.1 - nscannedObjects should be 0 for covered query") +var plan = coll.find({foo:1}, {foo:1, _id:0}).hint({foo:1}).explain(); +assert.eq(true, plan.indexOnly, "simple.3.1 - indexOnly should be true on covered query"); +assert.eq(0, plan.nscannedObjects, "simple.3.1 - nscannedObjects should be 0 for covered query"); // Test equality with string value -var plan = coll.find({foo:"string"}, {foo:1, _id:0}).hint({foo:1}).explain() -assert.eq(true, plan.indexOnly, "simple.3.2 - indexOnly should be true on covered query") -assert.eq(0, plan.nscannedObjects, "simple.3.2 - nscannedObjects should be 0 for covered query") +var plan = coll.find({foo:"string"}, {foo:1, _id:0}).hint({foo:1}).explain(); +assert.eq(true, plan.indexOnly, "simple.3.2 - indexOnly should be true on covered query"); +assert.eq(0, plan.nscannedObjects, "simple.3.2 - nscannedObjects should be 0 for covered query"); // Test equality with int value on a dotted field -var plan = coll.find({foo:{bar:1}}, {foo:1, _id:0}).hint({foo:1}).explain() -assert.eq(true, plan.indexOnly, "simple.3.3 - indexOnly should be true on covered query") -assert.eq(0, plan.nscannedObjects, "simple.3.3 - nscannedObjects should be 0 for covered query") +var plan = coll.find({foo:{bar:1}}, {foo:1, _id:0}).hint({foo:1}).explain(); +assert.eq(true, plan.indexOnly, "simple.3.3 - indexOnly should be true on covered query"); +assert.eq(0, plan.nscannedObjects, "simple.3.3 - nscannedObjects should be 0 for covered query"); // Test no query -var plan = coll.find({}, {foo:1, _id:0}).hint({foo:1}).explain() -assert.eq(true, plan.indexOnly, "simple.3.4 - indexOnly should be true on covered query") -assert.eq(0, plan.nscannedObjects, "simple.3.4 - nscannedObjects should be 0 for covered query") +var plan = coll.find({}, {foo:1, _id:0}).hint({foo:1}).explain(); +assert.eq(true, plan.indexOnly, "simple.3.4 - indexOnly should be true on covered query"); +assert.eq(0, plan.nscannedObjects, "simple.3.4 - nscannedObjects should be 0 for covered query"); // Test range query -var plan = coll.find({foo:{$gt:2,$lt:6}}, {foo:1, _id:0}).hint({foo:1}).explain() -assert.eq(true, plan.indexOnly, "simple.3.5 - indexOnly should be true on covered query") -assert.eq(0, plan.nscannedObjects, "simple.3.5 - nscannedObjects should be 0 for covered query") +var plan = coll.find({foo:{$gt:2,$lt:6}}, {foo:1, _id:0}).hint({foo:1}).explain(); +assert.eq(true, plan.indexOnly, "simple.3.5 - indexOnly should be true on covered query"); +assert.eq(0, plan.nscannedObjects, "simple.3.5 - nscannedObjects should be 0 for covered query"); // Test in query -var plan = coll.find({foo:{$in:[5,8]}}, {foo:1, _id:0}).hint({foo:1}).explain() -assert.eq(true, plan.indexOnly, "simple.3.6 - indexOnly should be true on covered query") -assert.eq(0, plan.nscannedObjects, "simple.3.6 - nscannedObjects should be 0 for covered query") - -// SERVER-12262: currently $exists will always use a collection scan. We do -// not use a full index scan as a proxy for a collection scan, and hence the -// query is not covered / indexOnly. -//var plan = coll.find({foo:{$exists:true}}, {foo:1, _id:0}).hint({foo:1}).explain() -//assert.eq(true, plan.indexOnly, "simple.3.7 - indexOnly should be true on covered query") -// this should be 0 but is not due to bug https://jira.mongodb.org/browse/SERVER-3187 -//assert.eq(13, plan.nscannedObjects, "simple.3.7 - nscannedObjects should be 0 for covered query") +var plan = coll.find({foo:{$in:[5,8]}}, {foo:1, _id:0}).hint({foo:1}).explain(); +assert.eq(true, plan.indexOnly, "simple.3.6 - indexOnly should be true on covered query"); +assert.eq(0, plan.nscannedObjects, "simple.3.6 - nscannedObjects should be 0 for covered query"); + +// Test $exists true +var plan = coll.find({foo:{$exists:true}}, {foo:1, _id:0}).hint({foo:1}).explain(); +assert.eq(true, plan.indexOnly, "simple.3.7 - indexOnly should be true on covered query"); +assert.eq(0, plan.nscannedObjects, "simple.3.7 - nscannedObjects should be 0 for covered query"); // SERVER-12262: currently $nin will always use a collection scan //var plan = coll.find({foo:{$nin:[5,8]}}, {foo:1, _id:0}).hint({foo:1}).explain() diff --git a/jstests/exists2.js b/jstests/exists2.js index a9b4d1ed7b3..e925c168f50 100644 --- a/jstests/exists2.js +++ b/jstests/exists2.js @@ -8,7 +8,9 @@ t.save( { a : 1 , b : 1 , c : 1 } ) assert.eq( 2 , t.find().itcount() , "A1" ); assert.eq( 2 , t.find( { a : 1 , b : 1 } ).itcount() , "A2" ); assert.eq( 1 , t.find( { a : 1 , b : 1 , c : { "$exists" : true } } ).itcount() , "A3" ); +assert.eq( 1 , t.find( { a : 1 , b : 1 , c : { "$exists" : false } } ).itcount() , "A4" ); t.ensureIndex( { a : 1 , b : 1 , c : 1 } ) assert.eq( 1 , t.find( { a : 1 , b : 1 , c : { "$exists" : true } } ).itcount() , "B1" ); +assert.eq( 1 , t.find( { a : 1 , b : 1 , c : { "$exists" : false } } ).itcount() , "B2" ); diff --git a/jstests/exists6.js b/jstests/exists6.js index ea0f0ac64df..2fa4ba85d49 100644 --- a/jstests/exists6.js +++ b/jstests/exists6.js @@ -8,45 +8,64 @@ t.save( {} ); t.save( {b:1} ); t.save( {b:null} ); -checkExists = function( query ) { - // Index range constraint on 'b' is universal, so a BasicCursor is the default cursor type. +//--------------------------------- + +function checkIndexUse( query, usesIndex, index, bounds ) { var x = t.find( query ).explain() - assert.eq( 'BasicCursor', x.cursor , tojson(x) ); - // Index bounds include all elements. + if ( usesIndex ) { + assert.eq( x.cursor.indexOf(index), 0 , tojson(x) ); + if ( ! x.indexBounds ) x.indexBounds = {} + assert.eq( bounds, x.indexBounds.b , tojson(x) ); + } + else { + assert.eq( 'BasicCursor', x.cursor, tojson(x) ); + } +} - var x = t.find( query ).hint( {b:1} ).explain() - if ( ! x.indexBounds ) x.indexBounds = {} - // SERVER-12262: currently we never use an index for $exists queries. - // Tests which rely on an indexed solution being chosen are unsafe - // and should be moved into unit tests. - /* - assert.eq( [ [ { $minElement:1 }, { $maxElement:1 } ] ], x.indexBounds.b , tojson(x) ); - // All keys must be scanned. - assert.eq( 3, t.find( query ).hint( {b:1} ).explain().nscanned ); +function checkExists( query, usesIndex, bounds ) { + checkIndexUse( query, usesIndex, 'BtreeCursor b_1', bounds ); + // Whether we use an index or not, we will always scan all docs. + assert.eq( 3, t.find( query ).explain().nscanned ); // 2 docs will match. - */ - assert.eq( 2, t.find( query ).hint( {b:1} ).itcount() ); + assert.eq( 2, t.find( query ).itcount() ); +} + +function checkMissing( query, usesIndex, bounds ) { + checkIndexUse( query, usesIndex, 'BtreeCursor b_1', bounds ); + // Nscanned changes based on index usage. + if ( usesIndex ) assert.eq( 2, t.find( query ).explain().nscanned ); + else assert.eq( 3, t.find( query ).explain().nscanned ); + // 1 doc is missing 'b'. + assert.eq( 1, t.find( query ).itcount() ); +} + +function checkExistsCompound( query, usesIndex, bounds ) { + checkIndexUse( query, usesIndex, 'BtreeCursor', bounds ); + if ( usesIndex ) assert.eq( 3, t.find( query ).explain().nscanned ); + else assert.eq( 3, t.find( query ).explain().nscanned ); + // 2 docs have a:1 and b:exists. + assert.eq( 2, t.find( query ).itcount() ); } -checkExists( {b:{$exists:true}} ); -checkExists( {b:{$not:{$exists:false}}} ); -checkMissing = function( query ) { - // SERVER-12262: currently we never use an index for $exists queries. - // Tests which rely on an indexed solution being chosen are unsafe - // and should be moved into unit tests. - /* - // Index range constraint on 'b' is not universal, so a BtreeCursor is the default cursor type. - assert.eq( 'BtreeCursor b_1', t.find( query ).explain().cursor ); - // Scan null index keys. - assert.eq( [ [ null, null ] ], t.find( query ).explain().indexBounds.b ); - // Two existing null keys will be scanned. - assert.eq( 2, t.find( query ).explain().nscanned ); - */ - // One doc is missing 'b'. - assert.eq( 1, t.find( query ).hint( {b:1} ).itcount() ); +function checkMissingCompound( query, usesIndex, bounds ) { + checkIndexUse( query, usesIndex, 'BtreeCursor', bounds ); + // two possible indexes to use + // 1 doc should match + assert.eq( 1, t.find( query ).itcount() ); } -checkMissing( {b:{$exists:false}} ); -checkMissing( {b:{$not:{$exists:true}}} ); + +//--------------------------------- + +var allValues = [ [ { $minElement:1 }, { $maxElement:1 } ] ]; +var nullNull = [ [ null, null ] ]; + +// Basic cases +checkExists( {b:{$exists:true}}, true, allValues ); +// We change this to not -> not -> exists:true, and get allValue for bounds +// but we use a BasicCursor? +checkExists( {b:{$not:{$exists:false}}}, false, allValues ); +checkMissing( {b:{$exists:false}}, true, nullNull ); +checkMissing( {b:{$not:{$exists:true}}}, true, nullNull ); // Now check existence of second compound field. t.ensureIndex( {a:1,b:1} ); @@ -54,34 +73,7 @@ t.save( {a:1} ); t.save( {a:1,b:1} ); t.save( {a:1,b:null} ); -checkExists = function( query ) { - // SERVER-12262: currently we never use an index for $exists queries. - // Tests which rely on an indexed solution being chosen are unsafe - // and should be moved into unit tests. - /* - // Index bounds include all elements. - assert.eq( [ [ { $minElement:1 }, { $maxElement:1 } ] ], t.find( query ).explain().indexBounds.b ); - // All keys must be scanned. - assert.eq( 3, t.find( query ).explain().nscanned ); - */ - // 2 docs will match. - assert.eq( 2, t.find( query ).hint( {a:1,b:1} ).itcount() ); -} -checkExists( {a:1,b:{$exists:true}} ); -checkExists( {a:1,b:{$not:{$exists:false}}} ); - -checkMissing = function( query ) { - // SERVER-12262: currently we never use an index for $exists queries. - // Tests which rely on an indexed solution being chosen are unsafe - // and should be moved into unit tests. - /* - // Scan null index keys. - assert.eq( [ [ null, null ] ], t.find( query ).explain().indexBounds.b ); - // Two existing null keys will be scanned. - assert.eq( 2, t.find( query ).explain().nscanned ); - */ - // One doc is missing 'b'. - assert.eq( 1, t.find( query ).hint( {a:1,b:1} ).itcount() ); -} -checkMissing( {a:1,b:{$exists:false}} ); -checkMissing( {a:1,b:{$not:{$exists:true}}} ); +checkExistsCompound( {a:1,b:{$exists:true}}, true, allValues ); +checkExistsCompound( {a:1,b:{$not:{$exists:false}}}, true, allValues ); +checkMissingCompound( {a:1,b:{$exists:false}}, true, nullNull ); +checkMissingCompound( {a:1,b:{$not:{$exists:true}}}, true, nullNull ); diff --git a/jstests/exists9.js b/jstests/exists9.js index 9336bcaaa8b..66378d1b424 100644 --- a/jstests/exists9.js +++ b/jstests/exists9.js @@ -25,8 +25,7 @@ assert.eq( 1, t.count( {a:{$exists:false}} ) ); t.ensureIndex( {a:1} ); assert.eq( 1, t.find( {a:{$exists:true}} ).hint( {a:1} ).itcount() ); assert.eq( 1, t.find( {a:{$exists:false}} ).hint( {a:1} ).itcount() ); -// An {$exists: false} requires a collection scan. -assert.eq( 2, t.find( {a:{$exists:false}} ).hint( {a:1} ).explain().nscanned ); +assert.eq( 1, t.find( {a:{$exists:false}} ).hint( {a:1} ).explain().nscanned ); t.drop(); diff --git a/jstests/existsa.js b/jstests/existsa.js index c3ca98f4ae8..9ef7e9f374c 100644 --- a/jstests/existsa.js +++ b/jstests/existsa.js @@ -24,8 +24,7 @@ function assertPrefix( prefix, str ) { /** @return count when hinting the index to use. */ function hintedCount( query ) { - // SERVER-12262: $exists currently will never use an index. - //assertPrefix( indexCursorName, t.find( query ).hint( indexKeySpec ).explain().cursor ); + assertPrefix( indexCursorName, t.find( query ).hint( indexKeySpec ).explain().cursor ); return t.find( query ).hint( indexKeySpec ).itcount(); } @@ -35,25 +34,23 @@ function assertMissing( query, expectedMissing, expectedIndexedMissing ) { expectedIndexedMissing = expectedIndexedMissing || 0; assert.eq( expectedMissing, t.count( query ) ); assert.eq( 'BasicCursor', t.find( query ).explain().cursor ); - // SERVER-12262: $exists currently will never use an index. // We also shouldn't get a different count depending on whether // an index is used or not. - // assert.eq( expectedIndexedMissing, hintedCount( query ) ); + assert.eq( expectedIndexedMissing, hintedCount( query ) ); } /** The query field exists and the sparse index is used without a hint. */ function assertExists( query, expectedExists ) { expectedExists = expectedExists || 2; assert.eq( expectedExists, t.count( query ) ); - assert.eq( 'BasicCursor', t.find( query ).explain().cursor ); + assert.eq( 0, t.find( query ).explain().cursor.indexOf('BtreeCursor') ); // An $exists:true predicate generates no index filters. Add another predicate on the index key // to trigger use of the index. andClause = {} andClause[ indexKeyField ] = { $ne:null }; Object.extend( query, { $and:[ andClause ] } ); assert.eq( expectedExists, t.count( query ) ); - // SERVER-12262: $exists currently will never use an index. - // assertPrefix( indexCursorName, t.find( query ).explain().cursor ); + assertPrefix( indexCursorName, t.find( query ).explain().cursor ); assert.eq( expectedExists, hintedCount( query ) ); } @@ -82,21 +79,21 @@ assertMissing( { 'a.x':{ $exists:false } }, 2, 1 ); // Currently a sparse index is disallowed even if the $exists:false query is on a different field. assertMissing( { b:{ $exists:false } }, 2, 1 ); assertMissing( { b:{ $exists:false }, a:{ $ne:6 } }, 2, 1 ); +assertMissing( { b:{ $not:{ $exists:true } } }, 2, 1 ); -// Top level $exists:true queries match the proper number of documents and allow the sparse index. +// Top level $exists:true queries match the proper number of documents +// and use the sparse index on { a : 1 }. assertExists( { a:{ $exists:true } } ); -assertExists( { 'a.x':{ $exists:true } }, 1 ); -assertExists( { b:{ $exists:true } }, 1 ); -assertExists( { a:{ $not:{ $exists:false } } } ); // Nested $exists queries match the proper number of documents and disallow the sparse index. assertExistsUnindexed( { $nor:[ { a:{ $exists:false } } ] } ); assertExistsUnindexed( { $nor:[ { 'a.x':{ $exists:false } } ] }, 1 ); +assertExistsUnindexed( { a:{ $not:{ $exists:false } } } ); // Nested $exists queries disallow the sparse index in some cases where it is not strictly // necessary to do so. (Descriptive tests.) assertExistsUnindexed( { $nor:[ { b:{ $exists:false } } ] }, 1 ); // Unindexed field. -assertExistsUnindexed( { $or:[ { a:{ $exists:true } } ] } ); // $exists:true not $exists:false. +assertExists( { $or:[ { a:{ $exists:true } } ] } ); // $exists:true not $exists:false. // Behavior is similar with $elemMatch. t.drop(); @@ -106,13 +103,12 @@ t.save( { a:[ { b:1 } ] } ); setIndex( 'a.b' ); assertMissing( { a:{ $elemMatch:{ b:{ $exists:false } } } } ); -// A $elemMatch predicate is treated as nested, and the index is disallowed even for $exists:true. -assertExistsUnindexed( { a:{ $elemMatch:{ b:{ $exists:true } } } } ); +// A $elemMatch predicate is treated as nested, and the index should be used for $exists:true. +assertExists( { a:{ $elemMatch:{ b:{ $exists:true } } } } ); // A non sparse index will not be disallowed. t.drop(); t.save( {} ); t.ensureIndex( { a:1 } ); assert.eq( 1, t.find( { a:{ $exists:false } } ).itcount() ); -// SERVER-12262: $exists currently will never use an index. -//assert.eq( 'BtreeCursor a_1', t.find( { a:{ $exists:false } } ).explain().cursor ); +assert.eq( 'BtreeCursor a_1', t.find( { a:{ $exists:false } } ).explain().cursor ); diff --git a/jstests/existsb.js b/jstests/existsb.js new file mode 100644 index 00000000000..a212be145c0 --- /dev/null +++ b/jstests/existsb.js @@ -0,0 +1,76 @@ +// Tests for $exists against documents that store a null value +// +// A document with a missing value for an indexed field +// is indexed *as if* it had the value 'null' explicitly. +// Therefore: +// { b : 1 } +// { a : null, b : 1 } +// look identical based on a standard index on { a : 1 }. +// +// -- HOWEVER!! -- +// A sparse index on { a : 1 } would include { a : null, b : 1 }, +// but would not include { b : 1 }. In this case, the two documents +// are treated equally. +// +// Also, super special edge case around sparse, compound indexes +// from Mathias: +// If we have a sparse index on { a : 1, b : 1 } +// And we insert docs {}, { a : 1 }, +// { b : 1 }, and { a : 1, b : 1 } +// everything but {} will have an index entry. +// Let's make sure we handle this properly! + +t = db.jstests_existsb; +t.drop(); + +t.save( {} ); +t.save( { a: 1 } ); +t.save( { b: 1 } ); +t.save( { a: 1, b: null } ); +t.save( { a: 1, b: 1 } ); + +/** run a series of checks, just on the number of docs found */ +function checkExistsNull() { + // Basic cases + assert.eq( 3, t.count({ a:{ $exists: true }}) ); + assert.eq( 2, t.count({ a:{ $exists: false }}) ); + assert.eq( 3, t.count({ b:{ $exists: true }}) ); + assert.eq( 2, t.count({ b:{ $exists: false }}) ); + // With negations + assert.eq( 3, t.count({ a:{ $not:{ $exists: false }}}) ); + assert.eq( 2, t.count({ a:{ $not:{ $exists: true }}}) ); + assert.eq( 3, t.count({ b:{ $not:{ $exists: false }}}) ); + assert.eq( 2, t.count({ b:{ $not:{ $exists: true }}}) ); + // Both fields + assert.eq( 2, t.count({ a:1, b: { $exists: true }}) ); + assert.eq( 1, t.count({ a:1, b: { $exists: false }}) ); + assert.eq( 1, t.count({ a:{ $exists: true }, b:1}) ); + assert.eq( 1, t.count({ a:{ $exists: false }, b:1}) ); + // Both fields, both $exists + assert.eq( 2, t.count({ a:{ $exists: true }, b:{ $exists: true }}) ); + assert.eq( 1, t.count({ a:{ $exists: true }, b:{ $exists: false }}) ); + assert.eq( 1, t.count({ a:{ $exists: false }, b:{ $exists: true }}) ); + assert.eq( 1, t.count({ a:{ $exists: false }, b:{ $exists: false }}) ); +} + +// with no index, make sure we get correct results +checkExistsNull(); + +// try with a standard index +t.ensureIndex({ a : 1 }); +checkExistsNull(); + +// try with a sparse index +t.dropIndexes(); +t.ensureIndex({ a : 1 }, { sparse:true }); +checkExistsNull(); + +// try with a compound index +t.dropIndexes(); +t.ensureIndex({ a : 1, b : 1 }); +checkExistsNull(); + +// try with sparse compound index +t.dropIndexes(); +t.ensureIndex({ a : 1, b : 1 }, { sparse:true }); +checkExistsNull(); diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp index eefaf2a44e7..59df9828b53 100644 --- a/src/mongo/db/query/index_bounds_builder.cpp +++ b/src/mongo/db/query/index_bounds_builder.cpp @@ -254,7 +254,22 @@ namespace mongo { *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH; } else if (MatchExpression::NOT == expr->matchType()) { - if (Indexability::nodeCanUseIndexOnOwnField(expr->getChild(0))) { + MatchExpression* child = expr->getChild(0); + + // If we have a NOT -> EXISTS, we must handle separately. + if (MatchExpression::EXISTS == child->matchType()) { + // We should never try to use a sparse index for $exists:false. + invariant(!index.sparse); + BSONObjBuilder bob; + bob.appendNull(""); + bob.appendNull(""); + BSONObj dataObj = bob.obj(); + oilOut->intervals.push_back(makeRangeInterval(dataObj, true, true)); + + *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH; + return; + } + else if (Indexability::nodeCanUseIndexOnOwnField(child)) { // We have a NOT of a bounds-generating expression. Get the // bounds of the NOT's child and then complement them. translate(expr->getChild(0), elt, index, oilOut, tightnessOut); @@ -270,6 +285,43 @@ namespace mongo { *tightnessOut = INEXACT_FETCH; } } + else if (MatchExpression::EXISTS == expr->matchType()) { + // We only handle the {$exists:true} case, as {$exists:false} + // will have been translated to {$not:{ $exists:true }}. + // + // Documents with a missing value are stored *as if* they were + // explicitly given the value 'null'. Given: + // X = { b : 1 } + // Y = { a : null, b : 1 } + // X and Y look identical from within a standard index on { a : 1 }. + // HOWEVER a sparse index on { a : 1 } will treat X and Y differently, + // storing Y and not storing X. + // + // We can safely use an index in the following cases: + // {a:{ $exists:true }} - normal index helps, but we must still fetch + // {a:{ $exists:true }} - sparse index is exact + // {a:{ $exists:false }} - normal index requires a fetch + // {a:{ $exists:false }} - sparse indexes cannot be used at all. + // + // Noted in SERVER-12869, in case this ever changes some day. + if (index.sparse) { + oilOut->intervals.push_back(allValues()); + // A sparse, compound index on { a:1, b:1 } will include entries + // for all of the following documents: + // { a:1 }, { b:1 }, { a:1, b:1 } + // So we must use INEXACT bounds in this case. + if ( 1 < index.keyPattern.nFields() ) { + *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH; + } + else { + *tightnessOut = IndexBoundsBuilder::EXACT; + } + } + else { + oilOut->intervals.push_back(allValues()); + *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH; + } + } else if (MatchExpression::EQ == expr->matchType()) { const EqualityMatchExpression* node = static_cast<const EqualityMatchExpression*>(expr); translateEquality(node->getData(), isHashed, oilOut, tightnessOut); diff --git a/src/mongo/db/query/index_bounds_builder_test.cpp b/src/mongo/db/query/index_bounds_builder_test.cpp index 4be2f4dea22..1420e48b69c 100644 --- a/src/mongo/db/query/index_bounds_builder_test.cpp +++ b/src/mongo/db/query/index_bounds_builder_test.cpp @@ -457,6 +457,59 @@ namespace { } // + // $exists tests + // + + TEST(IndexBoundsBuilderTest, ExistsTrue) { + IndexEntry testIndex = IndexEntry(BSONObj()); + BSONObj obj = fromjson("{a: {$exists: true}}"); + auto_ptr<MatchExpression> expr(parseMatchExpression(obj)); + BSONElement elt = obj.firstElement(); + OrderedIntervalList oil; + IndexBoundsBuilder::BoundsTightness tightness; + IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness); + ASSERT_EQUALS(oil.name, "a"); + ASSERT_EQUALS(oil.intervals.size(), 1U); + ASSERT_EQUALS(Interval::INTERVAL_EQUALS, + oil.intervals[0].compare(IndexBoundsBuilder::allValues())); + ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH); + } + + TEST(IndexBoundsBuilderTest, ExistsFalse) { + IndexEntry testIndex = IndexEntry(BSONObj()); + BSONObj obj = fromjson("{a: {$exists: false}}"); + auto_ptr<MatchExpression> expr(parseMatchExpression(obj)); + BSONElement elt = obj.firstElement(); + OrderedIntervalList oil; + IndexBoundsBuilder::BoundsTightness tightness; + IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness); + ASSERT_EQUALS(oil.name, "a"); + ASSERT_EQUALS(oil.intervals.size(), 1U); + ASSERT_EQUALS(Interval::INTERVAL_EQUALS, oil.intervals[0].compare( + Interval(fromjson("{'': null, '': null}"), true, true))); + ASSERT_EQUALS(tightness, IndexBoundsBuilder::INEXACT_FETCH); + } + + TEST(IndexBoundsBuilderTest, ExistsTrueSparse) { + IndexEntry testIndex = IndexEntry(BSONObj(), + false, + true, + "exists_true_sparse", + BSONObj()); + BSONObj obj = fromjson("{a: {$exists: true}}"); + auto_ptr<MatchExpression> expr(parseMatchExpression(obj)); + BSONElement elt = obj.firstElement(); + OrderedIntervalList oil; + IndexBoundsBuilder::BoundsTightness tightness; + IndexBoundsBuilder::translate(expr.get(), elt, testIndex, &oil, &tightness); + ASSERT_EQUALS(oil.name, "a"); + ASSERT_EQUALS(oil.intervals.size(), 1U); + ASSERT_EQUALS(Interval::INTERVAL_EQUALS, + oil.intervals[0].compare(IndexBoundsBuilder::allValues())); + ASSERT_EQUALS(tightness, IndexBoundsBuilder::EXACT); + } + + // // Union tests // diff --git a/src/mongo/db/query/indexability.h b/src/mongo/db/query/indexability.h index 6f25bda0469..0085e05e5a2 100644 --- a/src/mongo/db/query/indexability.h +++ b/src/mongo/db/query/indexability.h @@ -61,6 +61,7 @@ namespace mongo { || me->matchType() == MatchExpression::TYPE_OPERATOR || me->matchType() == MatchExpression::GEO || me->matchType() == MatchExpression::GEO_NEAR + || me->matchType() == MatchExpression::EXISTS || me->matchType() == MatchExpression::TEXT; } diff --git a/src/mongo/db/query/query_planner_test.cpp b/src/mongo/db/query/query_planner_test.cpp index 6ad01f502bd..705428a53e4 100644 --- a/src/mongo/db/query/query_planner_test.cpp +++ b/src/mongo/db/query/query_planner_test.cpp @@ -451,7 +451,7 @@ namespace { TEST_F(QueryPlannerTest, ExistsTrue) { addIndex(BSON("x" << 1)); - runQuery(fromjson("{x: 1, y: {$exists: true}}")); + runQuery(fromjson("{x: {$exists: true}}")); assertNumSolutions(2U); assertSolutionExists("{cscan: {dir: 1}}"); @@ -461,7 +461,7 @@ namespace { TEST_F(QueryPlannerTest, ExistsFalse) { addIndex(BSON("x" << 1)); - runQuery(fromjson("{x: 1, y: {$exists: false}}")); + runQuery(fromjson("{x: {$exists: false}}")); assertNumSolutions(2U); assertSolutionExists("{cscan: {dir: 1}}"); @@ -471,7 +471,7 @@ namespace { TEST_F(QueryPlannerTest, ExistsTrueSparseIndex) { addIndex(BSON("x" << 1), false, true); - runQuery(fromjson("{x: 1, y: {$exists: true}}")); + runQuery(fromjson("{x: {$exists: true}}")); assertNumSolutions(2U); assertSolutionExists("{cscan: {dir: 1}}"); @@ -481,6 +481,45 @@ namespace { TEST_F(QueryPlannerTest, ExistsFalseSparseIndex) { addIndex(BSON("x" << 1), false, true); + runQuery(fromjson("{x: {$exists: false}}")); + + assertNumSolutions(1U); + assertSolutionExists("{cscan: {dir: 1}}"); + } + + TEST_F(QueryPlannerTest, ExistsTrueOnUnindexedField) { + addIndex(BSON("x" << 1)); + + runQuery(fromjson("{x: 1, y: {$exists: true}}")); + + assertNumSolutions(2U); + assertSolutionExists("{cscan: {dir: 1}}"); + assertSolutionExists("{fetch: {node: {ixscan: {pattern: {x: 1}}}}}"); + } + + TEST_F(QueryPlannerTest, ExistsFalseOnUnindexedField) { + addIndex(BSON("x" << 1)); + + runQuery(fromjson("{x: 1, y: {$exists: false}}")); + + assertNumSolutions(2U); + assertSolutionExists("{cscan: {dir: 1}}"); + assertSolutionExists("{fetch: {node: {ixscan: {pattern: {x: 1}}}}}"); + } + + TEST_F(QueryPlannerTest, ExistsTrueSparseIndexOnOtherField) { + addIndex(BSON("x" << 1), false, true); + + runQuery(fromjson("{x: 1, y: {$exists: true}}")); + + assertNumSolutions(2U); + assertSolutionExists("{cscan: {dir: 1}}"); + assertSolutionExists("{fetch: {node: {ixscan: {pattern: {x: 1}}}}}"); + } + + TEST_F(QueryPlannerTest, ExistsFalseSparseIndexOnOtherField) { + addIndex(BSON("x" << 1), false, true); + runQuery(fromjson("{x: 1, y: {$exists: false}}")); assertNumSolutions(2U); |