[SERVER-5848] Refactor IndexType suitability() method to take a FieldRangeSetPair Created: 15/May/12  Updated: 11/Jul/16  Resolved: 20/Dec/12

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

Type: Improvement Priority: Minor - P4
Reporter: Kevin Matulef Assignee: Kevin Matulef
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
is related to SERVER-5858 Special index types including hashed ... Closed
Participants:

 Description   

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

{ a:1 }

and { $and:[

{ a:1 }

] } 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:

{ $in:[ 1, 2 ] }

}) 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.



 Comments   
Comment by auto [ 15/Mar/13 ]

Author:

{u'date': u'2013-03-15T15:19:59Z', u'name': u'aaron', u'email': u'aaron@10gen.com'}

Message: SERVER-5848 Additional tests.
Branch: master
https://github.com/mongodb/mongo/commit/4c75c66c34bae94e61e805403ceca4e132856064

Comment by auto [ 20/Dec/12 ]

Author:

{u'date': u'2012-12-20T21:25:57Z', u'email': u'matulef@10gen.com', u'name': u'Kevin Matulef'}

Message: SERVER-5848 further simplifications to default suitability() method
Branch: master
https://github.com/mongodb/mongo/commit/429d1a8f670a6f29975f16a1465044f677656bd5

Comment by auto [ 18/Dec/12 ]

Author:

{u'date': u'2012-12-18T18:17:34Z', u'email': u'matulef@10gen.com', u'name': u'Kevin Matulef'}

Message: SERVER-5848 ammend c++ unit tests for new suitability method
Branch: master
https://github.com/mongodb/mongo/commit/0133fa6fe09720333bc0cd49fea6dba4f284edd5

Comment by auto [ 18/Dec/12 ]

Author:

{u'date': u'2012-12-18T16:35:36Z', u'name': u'Alberto Lerner', u'email': u'alerner@10gen.com'}

Message: SERVER-5848 Disable tests temporarily (fix compile).
Branch: master
https://github.com/mongodb/mongo/commit/95aec02bdeb20e4529c140464996b8b47d9dd7e8

Comment by auto [ 18/Dec/12 ]

Author:

{u'date': u'2012-12-18T15:54:41Z', u'name': u'Kevin Matulef', u'email': u'matulef@10gen.com'}

Message: SERVER-5848 determine index suitability using a FieldRangeSet

Previously each special index type would determine the suitability
of the index by analyzing the original query. To avoid re-parsing
the query for each index, we now pass in a FieldRangeSet, which is
a better representation of all the constraints implied by the query.
Branch: master
https://github.com/mongodb/mongo/commit/6b46f885aba062ffcddbd6f7cfb2a36e23bbce1d

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