0

schema:

{
  time_utc: "milliseconds",
  city: "string",
  age: "integer"
}

index:

{
  time_utc: 1,
  city: 1,
  age: 1
}

sample query:

col.aggregate([
  {
    $match: { time_utc: { $exists: true }  city: "new york", age: { $gt: 18 } }
  },
  {
    $sort: { time_utc: -1 }
  }
])

I am certain that the compound index will be used in this query, so that the sort will be efficient.

However, the $match / filtering of documents stage does not seem efficient because we can assume that time_utc is unique across the collection.

Let's suppose that there are 1 million documents in the collection and only 10 will be returned. Let's further suppose that the 10 documents are located at bottom of the time_utc sort.

In this scenario, the query must scan the entire 1 million value of the index in order to discover the 10 documents. This is equivalent to a full collection scan.

Let's suppose the opposite, that there are only 2 unique values in time_utc. In this scenario, it seems that the index for the city and age fields can in fact be effective.

Is my reasoning correct?

2 Answers 2

2

I would say that some of your reasoning is correct, and thinking through the consequences of the structure of the index is indeed hugely important. As usual, @Wernfried Domscheit makes some salient points in his answer. But I think there is more to unpack here, so let's dive in. We'll start by responding to some of the statements directly.

I am certain that the compound index will be used in this query, so that the sort will be efficient.

The index can be used, yes. But, as I've mentioned before, that does not mean that it will be used. This is particularly true in the presence of other viable indexes which we will talk about later on.

...we can assume that time_utc is unique across the collection.

Let's suppose that there are 1 million documents in the collection and only 10 will be returned. Let's further suppose that the 10 documents are located at bottom of the time_utc sort.

In this scenario, the query must scan the entire 1 million value of the index in order to discover the 10 documents.

Right. The behavior/problem that you have described is not isolated to where the results are located while scanning the index though.

In the scenario you have described, the index scan that is required is very 'wide'. This makes it rather inefficient at servicing the query. The placement of the results in that index is irrelevant to the behavior and performance of the query in general though. Your query would take the same amount of time and do the same amount of work if those 10 documents were the first 10 in the index scan as well.

We can see that by viewing the execution stats from the explain plan when issuing the sort in the two directions since the index can be scanned in forward or reverse direction. Using the descending sorting provided in the question:

> db.foo.aggregate([ { $match: { time_utc: { $exists: true }, city: "new york", age: { $gt: 18 } } }, { $sort: { time_utc: -1 } }]).explain("executionStats").executionStats
{
  nReturned: 10,
  totalKeysExamined: 1000000,
  totalDocsExamined: 10,
  ...
      keyPattern: { time_utc: 1, city: 1, age: 1 },
      direction: 'backward',

And using the opposite (ascending):

> db.foo.aggregate([ { $match: { time_utc: { $exists: true }, city: "new york", age: { $gt: 18 } } }, { $sort: { time_utc: 1 } }]).explain("executionStats").executionStats
{
  nReturned: 10,
  totalKeysExamined: 1000000,
  totalDocsExamined: 10,
  ...
      keyPattern: { time_utc: 1, city: 1, age: 1 },
      direction: 'forward',

Let's suppose the opposite, that there are only 2 unique values in time_utc. In this scenario, it seems that the index for the city and age fields can in fact be effective.

Yes. As you've implied here, this is a consequence of the distribution of the data as opposed to some different behavior of the database in this situation.

Using the terminology above, the boundaries for the index scan are still just as "wide" as they were before. The difference here is that the 'width' of the index is much smaller. In this situation where there are 2 unique values I would expect the explain output to (likely) report just a few seeks which would reflect the logical structure of the index being 'narrower' in this regard.

Let's explore that a little futher.

'Wide' Scan

In general, when the index definition leads with the sort field(s) then the index scan on that field will not be bounded. In your case you do happen to have a predicate condition on that same field (time_utc), but it does not actually result in narrowing the scan. We can see that in the explain output:

> db.foo.aggregate([ { $match: { time_utc: { $exists: true }, city: "new york", age: { $gt: 18 } } }, { $sort: { time_utc: -1 } }]).explain().queryPlanner.winningPlan.inputStage.indexBounds
{
  time_utc: [ '[MaxKey, MinKey]' ],
  city: [ '["new york", "new york"]' ],
  age: [ '[inf.0, 18)' ]
}

These boundaries are the same regardless of the data in the collection.

Now if we look at the execution stats from the IXSCAN with the original data set (1 million unique values) we can see that the database needs to jump around through the index to find the relevant section and ends up looking at the whole thing:

> db.foo.aggregate([{$group:{_id:'$time_utc'}},{$count:'uniqueTimes'}])
[ { uniqueTimes: 1000000 } ]
> db.foo.aggregate([ { $match: { time_utc: { $exists: true }, city: "new york", age: { $gt: 18 } } }, { $sort: { time_utc: -1 } }]).explain("executionStats").executionStats.executionStages.inputStage
{
  keyPattern: { time_utc: 1, city: 1, age: 1 },
  keysExamined: 1000000,
  seeks: 999991,
  ...

But when there are only 2 distinct values for the leading key defined by the index, the database gets to skip over most of it:

> db.foo.aggregate([{$group:{_id:'$time_utc'}},{$count:'uniqueTimes'}])
[ { uniqueTimes: 2 } ]
> db.foo.aggregate([ { $match: { time_utc: { $exists: true }, city: "new york", age: { $gt: 18 } } }, { $sort: { time_utc: -1 } }]).explain("executionStats").executionStats.executionStages.inputStage
{
  keyPattern: { time_utc: 1, city: 1, age: 1 },
  keysExamined: 12,
  seeks: 3,
  ...

Recommendations (ESR Guidance)

As the other answer mentions, if the result sets are small then the cost of the sort is not particularly high.

In general though, MongoDB suggests that the starting place for indexing is what they refer to as The ESR Rule. Using this approach, the predicate on city is an equality condition so should be placed first in the index. The time_utc predicate, however, is a range condition as it basically means "any value except for missing". Because that field is used in both regards (sort and range), the index that the guidelines would suggest that you try is:

{
  city: 1,
  time_utc: 1,
  age: 1
}

Now going back to the point about result set size, it is definitely possible that you could actually see better performance by swapping the second and third keys and incurring the blocking sort:

{
  city: 1,
  age: 1,
  time_utc: 1
}

This entirely depends on data selectivity and it may be the case that some predicate values work better with one index than the other. You'd have to test and evaluate in your own environment.

0

First, date/time values should be better stored properly as Date object, not as numbers or - even worse - as strings. Date objects are always UTC times, so it should fulfill your requirements.

If the condition on city and age returns only 10 documents, then you don't need an index on time_utc. For sorting of 10 documents it does not matter whether it uses an index or not, regardless if time_utc has 10 million distinct values or just two distinct values.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.