[SERVER-4180] Allow multiple constraints (on same field) within a $elemMatch clause to be used with a multikey index Created: 31/Oct/11  Updated: 11/Jul/16  Resolved: 13/Jun/12

Status: Closed
Project: Core Server
Component/s: Index Maintenance, Querying
Affects Version/s: 2.0.1
Fix Version/s: 2.1.2

Type: Improvement Priority: Major - P3
Reporter: Mathieu Poumeyrol Assignee: Aaron Staple
Resolution: Done Votes: 2
Labels: regression
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified
Environment:

linux ubuntu


Attachments: File testcase.date_broken_range.tgz    
Issue Links:
Depends
is depended on by SERVER-3104 index bound improvements for elemMatc... Closed
Duplicate
is duplicated by SERVER-6002 Query on same field with $gt/$gte and... Closed
is duplicated by SERVER-6720 Range query with compound multikey in... Closed
is duplicated by SERVER-8135 Unused index-boundaries on multikey Closed
Related
related to SERVER-4184 date max index bound value looks mess... Closed
Backwards Compatibility: Fully Compatible
Participants:

 Description   

While bumping from 1.8 to mongo 2.0.1, we noticed some query optimization seemed not to work anymore. After some laborious digging in our data, we found out a single document showing the issue.

Please open the attached .tgz. The tc.sh script will restore the document in a core.picture_set_pictures collection on a localhost:27017 mongo, setup an index, and explain a range query on a date embedded in a array of objects. The relevant section of the output shows.

"indexBounds" :

{ "votes.created_at" : [ [ ISODate("2010-10-31T13:37:20Z"), ISODate("292278995-01--2147483647T07:12:56.808Z") ] ] }

The upper bound is completely aberrant, and as far as I can tell, nothing in the document justifies such a value. As a consequence, on the real database, this will scan half of the table for every request. On the contrary, 1.8.3 was showing the right upper bound. Please also note that as far as we can tell, our collections have other instances of documents raising the problem (that is, a collection with just this document will exhibit the issue, but just removing the doc from the collection is not enough for the issue to disappear).



 Comments   
Comment by Mathieu Poumeyrol [ 13/Jun/12 ]

This collection is big, and there are actually several ones impacted.

I asked formally what was going to happen. Once I understood what was happenning, I gave you a testable case, and I POCed a patch. You guys told me there would be a fix for 2.2.

Now, height months later, I'm stuck with a choice between a "maybe" and a huge and complicated data migration on several collections, including the biggest and most critical of my dataset.

Please schedule 6050 for 2.2.

I understand the rush for a 2.2 release... but come on. In the current state, seeing this qualified as "fixed" feels like a very bad joke on me.

Comment by Aaron Staple [ 13/Jun/12 ]

Hi Mathieu - I suggest you change your schema slightly and add an elemMatch to your original query, per the following example. If SERVER-6050 is implemented you will not have to change the schema from your original. Feel free to comment on that issue.

c = db.c;
c.drop();
c.save(
       {
           "_id" : "--ITkd13HZw:c9o5i05059t3t-Xw-EIPkVE90",
               "votes" : [
                          {
                              "browser_id" : "fwAAAU5IAJajhSIyVZiGAg==",
                                  "kind" : "nominate",
                                  "pending" : {
                                  "review" : true
                                      },
                                  "created_at" : [ISODate("2011-10-29T15:49:46.592Z")],
                                      "sql_id" : 3285089,
                                      "_id" : 3285089,
                                      "user_ip" : "189.82.222.127",
                                      "user" : "c9o5i05059t3t",
                                      "score" : 1
                                      },
                          {
                              "browser_id" : "fwAAAU6r166/BhUvNXcCAg==",
                                  "comment" : "",
                                  "kind" : "score",
                                  "created_at" : [ISODate("2011-10-29T16:31:30.014Z")],
                                  "sql_id" : 3285177,
                                  "_id" : 3285177,
                                  "relevance" : 1,
                                  "origin" : "albums/fotopedia-en-Chaise_longue",
                                  "user_ip" : "93.16.21.63",
                                  "user" : "oGrgsfdBDZM",
                                  "score" : 2,
                                  "quality" : 1
                                  }
                          ]
               }
       );
c.ensureIndex( { 'votes.created_at':1 } );
printjson( c.find( { 'votes.created_at':{ $elemMatch:{ "$gte" : ISODate("2010-10-31T13:37:20Z"), "$lte" : ISODate("2010-10-31T13:37:35") } } } ).hint("votes.created_at_1").explain() );

Comment by Mathieu Poumeyrol [ 13/Jun/12 ]

I'm sorry to be a pain here, but this fix is completely irrelevant to the issue.

Worse, the implementation of the support for scalar values in $elemMatch being the root cause of the apparition of the regression in the first time, I fear these changes have brought us even farther from an actual resolution.

I insist: this is a sneaky but major regression (a few other people have mentioned difficulties with the same problem on the irc channel) from 1.8. I sincerely hope we can have it fixed for 2.2. In any case, we definitely need to reopen it.

Comment by Aaron Staple [ 13/Jun/12 ]

We've implemented an optimization allowing the $elemMatch operator to utilize multiple bounds on a multikey index. So if you do a query { a:{ $elemMatch:

{ $gte:0, $lte:10 }

} } on index

{ a:1 }

, only the a-values 0 through 10 will be scanned.

This optimization doesn't apply to nested $elemMatch queries, for example { a:{ $elemMatch:{ b:

{ $gte:0, $lte:10 }

} } on index

{ 'a.b':1 }

. Since the $elemMatch operator is applied to a and not 'a.b', only one bound constraint can be applied to the values of 'a.b', and in this case all 'a.b' values >= 0 would be scanned.

In the above situation you might consider a query like { 'a.b':{ $elemMatch:

{ $gte:0, $lte:10 }

} } instead. Keep in mind though that (pending SERVER-6050) $elemMatch can only be applied to arrays. So the query { 'a.b':{ $elemMatch:

{ $gte:0, $lte:10 }

} } would match the documents { _id:0, a:

{ b:[ 5 ] }

} and { _id:1, a:[

{ b:[ 5 ] }

] } but not { _id:2, a:[

{ b:5 }

] }.

Comment by auto [ 09/Jun/12 ]

Author:

{u'login': u'astaple', u'name': u'Aaron', u'email': u'aaron@10gen.com'}

Message: SERVER-4180 Document FieldRange and FieldRangeSet constructors.
Branch: master
https://github.com/mongodb/mongo/commit/af775374ea8b2184cd4c311468c2f86338876d9c

Comment by auto [ 09/Jun/12 ]

Author:

{u'login': u'astaple', u'name': u'Aaron', u'email': u'aaron@10gen.com'}

Message: SERVER-4180 Generate single key index bounds for $elemMatch expressions of the SERVER-1264 style (where matching is applied to the $elemMatch field itself, not subfields).
Branch: master
https://github.com/mongodb/mongo/commit/bb0fd337ac9498a5642986bba162880fa3030ce0

Comment by auto [ 09/Jun/12 ]

Author:

{u'login': u'astaple', u'name': u'Aaron', u'email': u'aaron@10gen.com'}

Message: SERVER-4180 Remove optional arguments to FieldRange and FieldRangeSet constructors.
Branch: master
https://github.com/mongodb/mongo/commit/ab0bfed139f35ab5a3e1de7241ebfb5922faf2ee

Comment by auto [ 09/Jun/12 ]

Author:

{u'login': u'astaple', u'name': u'Aaron', u'email': u'aaron@10gen.com'}

Message: SERVER-4180 Fixes and cleanups for $elemMatch index range calculation, in particular to clean up incorrect bound generation for SERVER-1264 style $elemMatch queries. Includes fixes for SERVER-5740 and SERVER-5741.
Branch: master
https://github.com/mongodb/mongo/commit/2b572b9c07d8d3feda949153e20b9eee8706ff7d

Comment by auto [ 09/Jun/12 ]

Author:

{u'login': u'astaple', u'name': u'Aaron', u'email': u'aaron@10gen.com'}

Message: SERVER-4180 Fixes and cleanups for $elemMatch matching, including fix for SERVER-6001.
Branch: master
https://github.com/mongodb/mongo/commit/68775795d16f6a3854341f16d4cab32d1bc76830

Comment by Eliot Horowitz (Inactive) [ 28/Mar/12 ]

This is scheduled for 2.1.2, so we'll be working on it a couple of weeks.

Comment by Mathieu Poumeyrol [ 11/Nov/11 ]

Anybody listening here ?

Comment by Mathieu Poumeyrol [ 03/Nov/11 ]

In the end, I went for strategy #3. The results are https://github.com/kali/mongo/commit/a559b7132ae5d595e0d63bb7a89231ab9bacb2d8 . It is a bigger patch than I expected, and it will be a pain to rebase to other versions, but if I'm pretty sure I'll get it to work on 2.0 and get us out of trouble for now.

Eliot, guys, I would like to know if something of the sort has a remote chance to be integrated. I would assume not before 2.1 anyway, but in that case I would spend a few more hours tidying every loose end I can see or sensible changes you want made. I do think there is value in making the hint system extensible, but the way I chose may not be of your liking.

If you don't like the idea at all, please let me know what are the plans (or even lack of plan) to get a fix (or a won't fix) for the range vs multivalued optimization issue. A rough idea of the version it may land would be of great help. Apologies for being a pain, but there is a huge performance regression here, and for us at least, a definite show-stopper for features that have taken already months to implement based on assumptions made on 1.8 behavior.

Comment by Mathieu Poumeyrol [ 02/Nov/11 ]

giving a shot at a patch for strategy #2.

Comment by Mathieu Poumeyrol [ 02/Nov/11 ]

My understanding of the issue is the optimizer refuses to consider the query a range query because it can not know that the inner key, "a", in the previous example, is never multivalued. So I was looking for ways to convey this information to the optimizer:
1/ extend the "multiKey" index property semantics: store the indexes of multivalued tokens in the path instead of just the boolean. That would be the most elegant, as no user intervention would be required to hint the optimizer. But the way the multiKey is stored (as a single bit in a namespace-wide bitmap) make it a very heavy change. The IndexDetails might be another place, but as far as I can tell the "info" doc is read-only.
2/ a variant: manual hint the index at index creation and store the hint in the IndexDetails.info doc (something in the form 'multiValued : ["v"]').
3/ provide the same information to the optimizer extending the index "hint"
4/ make the fact we mean "range" explicit in the query syntax: '{ "v" : { $elemMatch : { "a" : { $range :

{ $gte : 3, $lte : 5 }

}}}}'

Comment by Mathieu Poumeyrol [ 01/Nov/11 ]

So, with the JS display of the maximum date value set aside, a much simpler testcase is:

db.test.drop()
db.test.save({ v: [

{ a: 1}

,

{ a: 4}

,

{ a:8}

] })
db.test.ensureIndex(

{"v.a" : 1}

)
plan = db.test.find({ "v" : { $elemMatch : { "a" : { "$gte" : 3, "$lte" : 5}}}}).explain()
assert.eq(5, plan.indexBounds["v.a"][0][1])

It was passing in 1.8.2 (haven't test 1.8.3) and is breaking in 2.0.1.

Comment by Mathieu Poumeyrol [ 31/Oct/11 ]

OK, I understand the possible semantic ambiguity with multivalued field. But are you sure 2.0 choice is better than the 1.8 ?

As a matter of fact, what my query means is "some actual value in the range" not "any absurd combination of unrelated values managing to somehow match the range as a side effect"...

The actual query I started investigating with was using $elemMatch (as a third filtering criteria was applied to the a potential matching "vote"). In that case, the ambiguity of the query $lt/$gt over a subdocument was gone.

If I understand correctly, the 1.8 behavior is not reproducible with 2.0. That is a big regression as far as we are concerned. Optimization of these queries are a critical issue for us, meaning we will be stuck with 1.8 as long as these range semantics are not somehow restored. Our application can't afford the supplementary data scan the new semantics implies.

Comment by Aaron Staple [ 31/Oct/11 ]

Because your field is multikey we can only use one index bound for the index on this field, not both an upper and lower bound.

Please see SERVER-4155.

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