[SERVER-18653] Answering "equality to null" predicates with an index requires a FETCH stage Created: 26/May/15  Updated: 06/Dec/22  Resolved: 03/Jun/15

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: 3.0.3
Fix Version/s: None

Type: Improvement Priority: Major - P3
Reporter: Andrey Hohutkin Assignee: Backlog - Query Optimization
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
is duplicated by SERVER-20155 Query for null filters before index scan Closed
Related
is related to SERVER-18861 Queries matching null value should be... Backlog
Assigned Teams:
Query Optimization
Participants:

 Description   

I have a primary collection users:

{ _id: ObjectId, follow: [ObjectId], primary: ObjectId }

primary field is optional in document
I have a non-sparse index:

{ follow: 1, primary: 1 }

When I try to query all followers without primary:
db.users.count(

{ follow: ObjectId, primary: null }

)
it uses only follow field, fetches all these documents and then filters out documents where primary is null.

Here is a result from explain:
"winningPlan" : {
"stage" : "COUNT",
"inputStage" : {
"stage" : "FETCH",
"filter" : {
"primary" :

{ "$eq" : null }

},
"inputStage" : {
"stage" : "IXSCAN",
"keyPattern" :

{ "follow" : NumberInt(1), "primary" : NumberInt(1) }

,
"indexName" : "follow_1_primary_1",
"isMultiKey" : true,
"direction" : "forward",
"indexBounds" :

{ "follow" : [ "[ObjectId('5382f987832983fb3a5ae9d4'), ObjectId('5382f987832983fb3a5ae9d4')]" ], "primary" : [ "[null, null]" ] }

}
}
}

It shows 'filter' stage that absolutely not needed.
It drastically drops down a performance of an application.

I checked that if I put primary as 0 - it works fine.
The problem is query with null value.



 Comments   
Comment by mils [ 13/Nov/17 ]

Hi,
For the last few weeks I have faced some serious performance issues as a result of null semantics in Mongodb, and this jira ticket currently appears to be the best source of information on mongo null semantics on the internet. Thus I apologise for flogging a dead horse, but I genuinely cannot find a better source of info.

So firstly thank you both to andrey and @rassi for the super-useful information. It has been vital to my db performance.

Simply put, I looked through the 2.6 changelist and this is the only documentation on why the null-semantic change was made:

> null equality conditions on array elements (e.g. "a.b": null) no longer match document missing the nested field a.b (e.g. a: [ 2, 3 ])

@rassi can you please provide any more info on why this used to be indexed, and is no longer indexed? I think a lot of mongodb users out there would gain confidence in the engine if they had a better understanding of why the change was made.

Thanks again,

Comment by Andrey Hohutkin [ 08/Jun/15 ]

Because nobody replied to my comment I will create a ticket with a feature request.

Comment by Andrey Hohutkin [ 05/Jun/15 ]

I want to show you that this issue has "bad design" and I will argue that.

"null" is not reserved word or value for mongodb. It is value that used in documents as well as a lot of others like Number, String or ObjectId. So I can freely to use "null" value in db and expect that I can use full power of engine.

Basing on this fact, I give you example that contains contradiction in it.
Let's create documents that have property "primary" and some of them can be null, others ObjectId or without property.
Let's create an index on this field only.
Now try to get count of documents with null value.
You will see that index is assumed to be used but not used.
You will get the same performance as you run it without index.
Do you agree that it is an absurd situation and should be resolved?

Now I want to explain my opinion about your explanation how it works now.
You describe very special case that a document hypothetically can have an array. For this case and only for this case the whole engine should have a great performance slowdown? Without ability to query simple null value?

I think, If a collection already has an index on specified field it should be ready for "any" case of data. Otherwise it is just takes a resources and does nothing.

What is your opinion and what others think of it?
I will continue to investigate the issue. First part of it is easy with my patch. It uses index for any further operation.
After that, behavior of index should be changed and take a respect of array type to be sure that documents with array wont included into result.

Thanks for attention.

Comment by J Rassi [ 04/Jun/15 ]

I will attempt to clearly spell out my previous explanation:

  1. The document {} generates the index key {"": null} for the index with key pattern {"a.b": 1}.
  2. The document {a: []} also generates the index key {"": null} for the index with key pattern {"a.b": 1}.
  3. The document {} matches the query {"a.b": null}.
  4. The document {a: []} does not match the query {"a.b": null}.
  5. Therefore, a query {"a.b": null} that is answered by an index with key pattern {"a.b": 1} must fetch the document and re-check the predicate, in order to ensure that the document {} is included in the result set and that the document {a: []} is not included in the result set.

You say that
"this document {a: []} generates the index key {"": null}."
It is a bug.
The key in index should be {"a.b": null}

Index keys don't have the field name attached, so the key is indeed {"": null}.

By documentation:
"null equality queries (i.e. field: null ) now match fields with values undefined."

I was referring to the second bullet in this list, not the third bullet. The second bullet reads as follows: "null equality conditions on array elements (e.g. 'a.b': null) no longer match document missing the nested field a.b (e.g. a: [ 2, 3 ])."

And finally the main issue - why it doesn't use an index?!!

As I mentioned above, this query is using an index, however the query cannot be covered by this index.

Comment by Andrey Hohutkin [ 04/Jun/15 ]

Hi Jason!

I do not agree with you that it "Works as Designed".
"primary" field in DB is not mandatory, and more than that it should not to be in document because I build on it unique "sparse" index.
I dont want to increase index size by filling value with 0 or false or what ever.
In my case primary field (if it exists in document) should be ObjectId. So it is not logic to put "false" value in that case.

Now I want to know how your explanation is related to my issue.
By documentation:
"null equality queries (i.e. field: null ) now match fields with values undefined."
It is exactly my case.

According to spec "undefined" is deprecated.
And finally the main issue - why it doesn't use an index?!! Who cares "null" value on predication? If an index exists - give it to index to decide. If not - use fetch.

IMHO, this is ridiculous, that a simple and clear issue not assumed as a bug.
If it "works as designed" it is bug by design.

Please, reopen the issue or let someone else to say his opinion.

P.S.
You say that
"this document

{a: []}

generates the index key

{"": null}

."
It is a bug.
The key in index should be

{"a.b": null}
Comment by J Rassi [ 03/Jun/15 ]

Hi Andrey,

I've investigated further, and determined that this was in fact not a regression introduced in the 2.6 query engine rewrite, but instead was an intentional behavior change.

Version 2.6.0 of the server changed the semantics of a null equality match predicate, such that the document {a: []} was no longer considered a match for the query predicate {"a.b": null} (in prior versions of the server, this document was considered a match for this predicate). This is documented in the 2.6 compatibility notes, under the "null comparison" section.

For an index with key pattern {"a.b": 1}, this document {a: []} generates the index key {"": null}. Other documents like {a: null} and the empty document {} also generate the index key {"": null}. As a result, if a query with predicate {"a.b": null} uses this index, the query system cannot tell just from the index key {"": null} whether or not the associated document matches the predicate. As a result, INEXACT_FETCH bounds are assigned instead of EXACT bounds, and hence a FETCH stage is added to the query execution tree.

As such, the existing code is correct, and I will close this ticket with resolution "Works as Designed". If you require an index-only count for this operation, you must implement a workaround in your application (for example, you could change your schema such that followers without a primary are represented by "primary: false" instead of "primary: null").

~ Jason Rassi

Comment by Andrey Hohutkin [ 30/May/15 ]

I think I found a place with a bug.
Checking for null - is the main problem. No need to check for null at all.
Use full index even with null values (that legitimate).
Checked with sparse index and without. Working fine.
With sparse index it adds filter with primary field.

diff -r 491e0354a29f src/mongo/db/query/index_bounds_builder.cpp
--- a/src/mongo/db/query/index_bounds_builder.cpp	Sat May 30 06:54:02 2015 +1000
+++ b/src/mongo/db/query/index_bounds_builder.cpp	Sun May 31 02:30:36 2015 +0300
@@ -825,7 +825,7 @@
             verify(dataObj.isOwned());
             oil->intervals.push_back(makePointInterval(dataObj));
 
-            if (dataObj.firstElement().isNull() || isHashed) {
+            if (isHashed) {
                 *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH;
             }
             else {

Comment by J Rassi [ 26/May/15 ]

Hi,

Thanks for the report. I can confirm that this count operation should be able to use a covered scan on this index, but it does not.

This appears to be a regression introduced by the query engine rewrite for the 2.6 release. I can see that predicates of the form {a: null} (or {a: {$eq: null}}, equivalently) generate "inexact bounds" in cases where "exact bounds" could be generated. This means that query plans in which these predicates are indexed will unnecessarily cause the document to be fetched and re-checked against the predicate (note that the index is indeed being used, but the query is not being covered by the index scan).

I'm updating the summary and moving this ticket to the "Needs Triage" state; please continue to watch this ticket for updates on when a fix may be scheduled.

~ Jason Rassi

Generated at Thu Feb 08 03:48:21 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.