[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:
Depends
is depended on by SERVER-802 Query optimization is doing a big sca... Closed
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: SERVER-371 mix skip types to scan fewer unused keys
http://github.com/mongodb/mongo/commit/a84e4a13eb4e9ce2cce7a9509dea60337676db37

Comment by auto [ 07/Jul/10 ]

Author:

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

Message: SERVER-371 don't skip when spec
http://github.com/mongodb/mongo/commit/e3a60f43b336a4d16b8f86fa5aa8a159f773951f

Comment by auto [ 07/Jul/10 ]

Author:

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

Message: SERVER-371 btree skipping
http://github.com/mongodb/mongo/commit/3e788cf58882dd173daee339444678ea963c8978

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.

Generated at Thu Feb 08 02:53:52 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.