[SERVER-371] optimize compound index multiple ranges Created: 19/Oct/09 Updated: 12/Jul/16 Resolved: 08/Jul/10 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | Querying |
| Affects Version/s: | None |
| Fix Version/s: | 1.5.5 |
| Type: | Improvement | Priority: | Major - P3 |
| Reporter: | Eliot Horowitz (Inactive) | Assignee: | Aaron Staple |
| Resolution: | Done | Votes: | 8 |
| Labels: | None | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Issue Links: |
|
||||||||
| Participants: | |||||||||
| Description |
|
test in jstests/index_check6.js |
| Comments |
| Comment by auto [ 08/Jul/10 ] |
|
Author: {'login': 'astaple', 'name': 'Aaron', 'email': 'aaron@10gen.com'}Message: |
| Comment by auto [ 07/Jul/10 ] |
|
Author: {'login': 'astaple', 'name': 'Aaron', 'email': 'aaron@10gen.com'}Message: |
| Comment by auto [ 07/Jul/10 ] |
|
Author: {'login': 'astaple', 'name': 'Aaron', 'email': 'aaron@10gen.com'}Message: |
| Comment by Eliot Horowitz (Inactive) [ 22/Jun/10 ] |
|
Yeah - at some point we may want to add a new index type to make these really fast - but i think just optimizing the ranges scanning is good enough for now |
| Comment by Aaron Staple [ 22/Jun/10 ] |
|
@eliot - Apparently it's also possible to do a space filling mapping from multi dimensional data to a single dimension and do a multidimensional query on a 1d index that way (similar to our geo queries). The indexes would have to be created specially for this, the same as with our geo indexes. Here is a rough description <http://www.scholarpedia.org/article/B-tree_and_UB-tree#UB-trees_for_Multidimensional_Applications>. I imagine we don't want to do this right now, but just thought I'd throw it out there and check. |
| Comment by Eliot Horowitz (Inactive) [ 21/Jun/10 ] |
|
@aaron - that sounds correct |
| Comment by Aaron Staple [ 14/Jun/10 ] |
|
So since basically all of our data types are continuous the best way I know of to implement this is as follows. Say our constraints are 0 <= x <= 5, 10 <= y <= 15 and we have an index on {x:1,y:1}. We first scan from x=0,y=10 to x=0,y=15. Then as efficiently as possible we traverse the btree from x=0,y=15 to x=a where a is the smallest existing value of x which is > 0. Then we look for x=a,y=b where b is the smallest value of y between 10 and 15. If there is a b, we scan from x=a,y=b to x=a,y=15. Then we find the next lowest value of x, set that to a, and repeat. Eliot, do you want me to implement this? |
| Comment by Benno Rice [ 01/Mar/10 ] |
|
Similar. We have a number of values that we want to index and we want to constrain our results to a given range for some or all of the values. So imagine having n axes and you want to find the values that fall inside a given "box". |
| Comment by Eliot Horowitz (Inactive) [ 01/Mar/10 ] |
|
does your example follow exactly the example in index_check6? |
| Comment by Benno Rice [ 01/Mar/10 ] |
|
It's a pressing need for something we have here though. I'd happily work on something short term that can be replaced later. Alternatively I can index things outside mongodb but if I can use mongo itself I'd far prefer that. |
| Comment by Eliot Horowitz (Inactive) [ 01/Mar/10 ] |
|
probably FieldRange... This code may change a bit soon though, and is a bit involved - so a touch place to start |
| Comment by Benno Rice [ 01/Mar/10 ] |
|
If I wanted to have a go at fixing this, where should I start? I've been having a look through the query optimizer code among other things but it'd help to have a few pointers. |