Unwanted limit stage in querying data

naman · January 25, 2021, 7:49pm

I am using Mongo 4.2 (stuck with this) and have a collection say “product_data” with documents with the following schema:

_id:“2lgys2yxouhug5xj3ms45mluxw5hsweu_itmep53vy”
uIdHash:“2lgys2yxouhug5xj3ms45mluxw5hsweu”
userTS:1494055844000
systemTS:1582138336379

Case 1:
With this, I have the following indexes for the collection:

_id: Regular and Unique (default)
uIdHash: Hashed

I tried to execute

db.product_data.find( {"uIdHash":"2lgys2yxouhug5xj3ms45mluxw5hsweu"}).sort({"userTS":-1}).explain()

and these are the stages in result:

Ofcourse, I could realize that it would make sense to have an additional compound index to avoid the mongo in-memory ‘Sort’ stage. So here is another case.

Case 2:
Now I have attempted to add another index with those which were existing
3. {uIdHash:1 , userTS:-1}: Regular and Compound

Up to my expectation, the result of execution here was able to optimize on the sorting stage:

<>

All good so far, now that I am looking to build for pagination on top of this query. I would need to limit the data queried. Hence the query further translates to

db.product_data.find( {"uIdHash":"2lgys2yxouhug5xj3ms45mluxw5hsweu"}).sort({"userTS":-1}).limit(10).explain()

The result for each Case now are as follows:

Case 1 Limit Result:

The in-memory sorting does less work (36 instead of 50) and returns the expected number of documents.
Fair enough, a good underlying optimization within the stage.

Case 2 Limit Result:

Surprisingly, with the compound index in use and the data queried, there is an additional Limit stage added to processing!

The doubts now I have are as follows:

Why do we need an additional stage for LIMIT, when we already have 10 documents returned from the FETCH stage?
What would be the impact of this additional stage? Given that I need pagination, shall I stick with Case 1 indexes and not use the last compound index?

Pavel_Duchovny · January 26, 2021, 7:00am

Hi @naman,

Welcome to MongoDB community and thanks for the detailed post!!

I believe the fetch stage is required in both scenarios as the documents found by the indexed searches have to be fetched in batches to the client.

Now the sort stage when happening in memory can skip a limit stage in the plan. However, the limit plan is very fast compared to in-memory blocking sort.

Therefore in almost all cases the second index to avoid the sort will be the optimal for this query.

Thanks
Pavel

naman · January 26, 2021, 9:04am

Hey @Pavel_Duchovny, thanks for your response. While the sort stage is quite understood, II was curious to know why is it that the FETCH stage couldn’t skip the LIMIT in the plan based on the indexes used to query the data within. e.g. in the limit based query, the IXSCAN and FETCH both made use of the same index and returned exactly the same amount of documents as asked to limit for, then why add another stage (even if it is quicker)?

PS: It took quite some time to get this post live here on the community and in the meanwhile I had posted it on SO#65889806. But because of answers made there, I can’t really pull it down. Maybe once we reach a conclusion to the discussion here, someone can answer the thread and help me close it a well. Just learning how this works and would take a note of avoiding that going forward.

Pavel_Duchovny · January 26, 2021, 9:39am

Hi @naman

Please note that the limit operation is done on the cursor level and not on the query.

So does in memory sort. Therefore the fetch stage inly fills the server side cursor. As the in memory sort already operate on a cursor there is no need to add a limit. However, an index sort happens before cursor is filled therefore it has to do fetch and limit.

If that doesn’t answer your questions please provide full explain (“executionStats”) to us.

Thanks
Pavel

naman · January 26, 2021, 2:14pm

The executionStats for the limit with the compound index are as follows:

{
  "executionSuccess": true,
  "nReturned": 10,
  "executionTimeMillis": 0,
  "totalKeysExamined": 10,
  "totalDocsExamined": 10,
  "executionStages": {
    "stage": "LIMIT",
    "nReturned": 10,
    "executionTimeMillisEstimate": 0,
    "works": 11,
    "advanced": 10,
    "needTime": 0,
    "needYield": 0,
    "saveState": 0,
    "restoreState": 0,
    "isEOF": 1,
    "limitAmount": 10,
    "inputStage": {
      "stage": "FETCH",
      "nReturned": 10,
      "executionTimeMillisEstimate": 0,
      "works": 10,
      "advanced": 10,
      "needTime": 0,
      "needYield": 0,
      "saveState": 0,
      "restoreState": 0,
      "isEOF": 0,
      "docsExamined": 10,
      "alreadyHasObj": 0,
      "inputStage": {
        "stage": "IXSCAN",
        "nReturned": 10,
        "executionTimeMillisEstimate": 0,
        "works": 10,
        "advanced": 10,
        "needTime": 0,
        "needYield": 0,
        "saveState": 0,
        "restoreState": 0,
        "isEOF": 0,
        "keyPattern": {
          "uIdHash": 1,
          "userTS": -1
        },
        "indexName": "uIdHash_1_userTS_-1",
        "isMultiKey": false,
        "multiKeyPaths": {
          "uIdHash": [],
          "userTS": []
        },
        "isUnique": false,
        "isSparse": false,
        "isPartial": false,
        "indexVersion": 2,
        "direction": "forward",
        "indexBounds": {
          "uIdHash": [
            "[\"2lgys2yxouhug5xj3ms45mluxw5hsweu\", \"2lgys2yxouhug5xj3ms45mluxw5hsweu\"]"
          ],
          "userTS": [
            "[MaxKey, MinKey]"
          ]
        },
        "keysExamined": 10,
        "seeks": 1,
        "dupsTested": 0,
        "dupsDropped": 0
      }
    }
  }
}

and to further relate what I am trying to convey if you notice the scan and fetch looks sufficient to provide the exact 10 documents that shall be the result effectively. Hope that helps explain better. The complete output with winningPlan and rejectedPlans is accessible here as a gist

naman · January 27, 2021, 1:01pm

@Pavel_Duchovny not sure if I was able to tag you with the stats in the previous response.

Pavel_Duchovny · January 27, 2021, 1:14pm

Hi @naman,

The stats show the same as the screen shots and I still have the same explanation.

Limit stage is needed as there is no other method performed in memory. As opposed to in memory sort.

Thanks pavel

Pavel_Duchovny · January 27, 2021, 1:15pm

I don’t see a reason to dove any dipper as clearly the addition of that stage has no impact on timing

naman · January 27, 2021, 1:46pm

Can I infer from this, that the cursor has to be processed(must) in memory before returning the result and LIMIT here is idempotent in nature(might be specifically for this case)?

Stennie_X · January 28, 2021, 1:40pm

Hi @naman,

The difference you are observing in explain output is expected based on the documented sort behaviour.

The extra query planning stage may seem counter-intuitive at first, but consider the following excerpts:

If MongoDB cannot use an index or indexes to obtain the sort order, MongoDB must perform a blocking sort operation on the data. A blocking sort indicates that MongoDB must consume and process all input documents to the sort before returning results. See: cursor.sort() Behaviors: Sort and Index Use.
If MongoDB cannot obtain the sort order via an index scan, then MongoDB uses a top-k sort algorithm. This algorithm buffers the first k results (or last, depending on the sort order) seen so far by the underlying index or collection access. See: cursor.sort() Behaviors: Limit Results.
In a non-blocking, or indexed sort, the sort step scans the index to produce results in the requested order. See: Use Indexes to Sort Query Results.

With an in-memory (blocking sort), output is buffered until the sort completes using a top-k sort algorithm. The top-k sort only keeps as many results as are needed for query processing, which in your example would be the limit of 10 documents. Per your Case 1 Limit Result, 24 index key comparisons were needed and 24 documents had to be fetched as input for the in-memory SORT stage which returned 10 documents.

With an indexed (non-blocking) sort, results are streamed to subsequent query processing stages and a LIMIT stage is used to stop execution once the limit of 10 documents has been reached. Per your Case 2 Limit Result, only 10 index keys were examined leading to 10 documents fetched and returned. As @Pavel_Duchovny noted, this is a more optimal query.

The stages in the query plan are required for correctness. The count of stages is not as important as the amount of work that has to be done when the same pipeline runs against a much larger data set.

An indexed sort will effectively have a constant amount of work to do even if there are many more potential matching documents. An in-memory sort will have to iterate all matching documents to produce the sorted result set, so there will be more processing overhead as the number of matching documents (before sorting and limiting) grows.

The comparative performance impact may not be very evident for a small number of documents in a test environment, but the indexed sort will be a much more scalable approach for future data growth.

In-memory sorts can also be fragile if query limits (or your average document size) change significantly from your test data or original assumptions. There is a memory limit for blocking sort operations (100MB in MongoDB 4.4; 32MB in prior versions). In-memory sorts exceeding this limit will fail with an exception like “Sort operation used more than the maximum 33554432 bytes of RAM. Add an index, or specify a smaller limit”.

You can include an allowDiskUse query option for find() queries in MongoDB 4.4 (or aggregate() queries in prior server versions) to support buffering in-memory sorts to disk if needed, but that I/O overhead is not going be ideal for performance.

Regards,
Stennie

naman · February 1, 2021, 7:15am

Thank you for the detailed answer @Stennie_X, I was really looking for this and yeah could agree with Pavel that the latter looked more optimal anyway by the work done under explanation. The additional details are really useful too.

system · February 6, 2021, 7:15am

This topic was automatically closed 5 days after the last reply. New replies are no longer allowed.