Background:

When mongo runs a query (or count, update, etc...) the query optimizer will iterate over all indexes in the collection and check each to see if a query plan using that index should be considered to evaluate the query. There are two steps in the process:

1) The index's IndexSpec is checked for its "suitability." If suitability() is USELESS, the index will be ignored, otherwise the implementation proceeds to step #2. For non btree indexes, IndexSpec::suitability() will delegate to IndexType::suitability(). This allows non btree index types to implement their own suitability behaviors (there is a different IndexType implementation per type of index). For example, 2d indexes and hashed indexes implement custom suitability methods.

2) The query optimizer creates a QueryPlan based on the query and index. This QueryPlan has a "utility" which currently implements more precise checks than IndexSpec::suiitability(). Depending on the "utility" values for the different candidate QueryPlans, one or more of these QueryPlans will be put in a QueryPlanSet and used to execute the query.

Functional Overview:

This ticket represents changing the suitability() interface function from:

virtual IndexSuitability suitability( const BSONObj& query , const BSONObj& order ) const ;

to

virtual IndexSuitability suitability( const FieldRangeSet& queryConstraints, const BSONObj& order ) const;

A FieldRangeSet is a representation of a parsed query that describes the bounds on all query fields suitable for indexing. Passing this representation to suitability() allows the different suitability() implementations to access this index bound information without re-parsing the query. A FieldRangeSet also normalizes the information about a query that is pertinent in this context, for example

and { $and:[

] } produce the same FieldRangeSet.

The primary functional change is that passing a FieldRangeSet instead of a bson query allows the hash index implementation to utilize queries consisting of a set of equality values (for example, { a:

}) which was not possible previously. (Previously, the 'query' parameter passed to suitability() was a simplified form of the original query and not precise enough for the hashed index implementation to identify such cases.)

Aside from this primary functional change, the different IndexType::suitability() implementations have been updated. In addition the IndexSpec::_suitability() implementation (for btree indexes) has been updated and its behavior changed slightly as described in the comment preceding the new code. Also, the code that passes arguments to suitability() has been updated slightly. It may be worth testing the updated suitability() implementations as part of the qa effort.

Aaron

-----------------------------

The IndexType suitability() method should takes an already parsed query, instead of a raw query. This will save the cost of re-parsing complicated queries for every candidate index. For our purposes, a parsed query is represented as a "FieldRangeSetPair," so the input to suitability() should be one of these instead of a BSONObj.

This will also fix a problem with hashed indexes not being used for certain queries (like $in queries) due to the suitability method being passed an oversimplified query.