Slow query when searching for non-existing values

I created ~500,000 documents with fake data. This is how one document looks:

{
    "_id" : ObjectId("63f8a22ae22b80196a09d688"),
    "workspace_id" : NumberInt(1),
    "data" : [
        {
            "k" : "first_name",
            "v" : "Berneice",
            "t" : NumberInt(1)
        },
        {
            "k" : "last_name",
            "v" : "Adams",
            "t" : NumberInt(1)
        },
        {
            "k" : "email",
            "v" : "xjaskolski@hotmail.com",
            "t" : NumberInt(1)
        },
        {
            "k" : "phone",
            "v" : "(201) 205-4629",
            "t" : NumberInt(1)
        },
        {
            "k" : "address",
            "v" : "1627 General Center Apt. 481\nNaderberg, OH 73926-4376",
            "t" : NumberInt(1)
        },
        {
            "k" : "city",
            "v" : "Millertown",
            "t" : NumberInt(1)
        },
        {
            "k" : "state",
            "v" : "Wisconsin",
            "t" : NumberInt(1)
        },
        {
            "k" : "zip",
            "v" : "32184",
            "t" : NumberInt(1)
        },
        {
            "k" : "country",
            "v" : "India",
            "t" : NumberInt(1)
        },
        {
            "k" : "company",
            "v" : "Jakubowski-Prosacco",
            "t" : NumberInt(1)
        },
        {
            "k" : "remove_from_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "consequatur"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "add_to_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "http://www.ondricka.com/voluptas-voluptatem-accusamus-nisi"
                },
                {
                    "k" : "price",
                    "v" : 56.07
                },
                {
                    "k" : "quantity",
                    "v" : NumberInt(47)
                },
                {
                    "k" : "size",
                    "v" : "atque"
                },
                {
                    "k" : "color",
                    "v" : "quos"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "viewed_page",
            "v" : [
                {
                    "k" : "url",
                    "v" : "http://www.wiza.org/"
                },
                {
                    "k" : "page_title",
                    "v" : "excepturi"
                },
                {
                    "k" : "page_type",
                    "v" : "quisquam"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "add_to_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "http://www.wiza.net/dicta-corrupti-est-atque-quia-sit"
                },
                {
                    "k" : "price",
                    "v" : 94.77
                },
                {
                    "k" : "quantity",
                    "v" : NumberInt(88)
                },
                {
                    "k" : "size",
                    "v" : "nisi"
                },
                {
                    "k" : "color",
                    "v" : "deserunt"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "purchase",
            "v" : [
                {
                    "k" : "category",
                    "v" : "optio"
                },
                {
                    "k" : "revenue",
                    "v" : NumberInt(788)
                },
                {
                    "k" : "product",
                    "v" : "sint"
                },
                {
                    "k" : "size",
                    "v" : "quo"
                },
                {
                    "k" : "color",
                    "v" : ""
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "purchase",
            "v" : [
                {
                    "k" : "category",
                    "v" : "earum"
                },
                {
                    "k" : "revenue",
                    "v" : NumberInt(102)
                },
                {
                    "k" : "product",
                    "v" : "eaque"
                },
                {
                    "k" : "size",
                    "v" : "provident"
                },
                {
                    "k" : "color",
                    "v" : ""
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "viewed_page",
            "v" : [
                {
                    "k" : "url",
                    "v" : "http://murray.biz/quisquam-et-ea-similique-consequatur-laboriosam-ab-vel"
                },
                {
                    "k" : "page_title",
                    "v" : "ea"
                },
                {
                    "k" : "page_type",
                    "v" : "qui"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "purchase",
            "v" : [
                {
                    "k" : "category",
                    "v" : "ad"
                },
                {
                    "k" : "revenue",
                    "v" : NumberInt(152)
                },
                {
                    "k" : "product",
                    "v" : "ab"
                },
                {
                    "k" : "size",
                    "v" : "ut"
                },
                {
                    "k" : "color",
                    "v" : ""
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "purchase",
            "v" : [
                {
                    "k" : "category",
                    "v" : "aliquam"
                },
                {
                    "k" : "revenue",
                    "v" : NumberInt(326)
                },
                {
                    "k" : "product",
                    "v" : "aperiam"
                },
                {
                    "k" : "size",
                    "v" : "ipsa"
                },
                {
                    "k" : "color",
                    "v" : ""
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "purchase",
            "v" : [
                {
                    "k" : "category",
                    "v" : "voluptatem"
                },
                {
                    "k" : "revenue",
                    "v" : NumberInt(209)
                },
                {
                    "k" : "product",
                    "v" : "eum"
                },
                {
                    "k" : "size",
                    "v" : "eius"
                },
                {
                    "k" : "color",
                    "v" : ""
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "remove_from_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "eos"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "remove_from_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "neque"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "viewed_page",
            "v" : [
                {
                    "k" : "url",
                    "v" : "http://kunde.com/unde-et-deleniti-veniam-dolore-aliquam-possimus-amet-dolores.html"
                },
                {
                    "k" : "page_title",
                    "v" : "illo"
                },
                {
                    "k" : "page_type",
                    "v" : "nesciunt"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "add_to_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "http://kiehn.com/"
                },
                {
                    "k" : "price",
                    "v" : 19.43
                },
                {
                    "k" : "quantity",
                    "v" : NumberInt(75)
                },
                {
                    "k" : "size",
                    "v" : "aperiam"
                },
                {
                    "k" : "color",
                    "v" : "quam"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "search",
            "v" : [
                {
                    "k" : "query",
                    "v" : "in"
                },
                {
                    "k" : "results_count",
                    "v" : NumberInt(17)
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "viewed_page",
            "v" : [
                {
                    "k" : "url",
                    "v" : "http://beahan.com/autem-commodi-facilis-quia.html"
                },
                {
                    "k" : "page_title",
                    "v" : "libero"
                },
                {
                    "k" : "page_type",
                    "v" : "sequi"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "add_to_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "http://www.prohaska.info/vitae-fuga-voluptatem-mollitia-natus-ea-consectetur-et-est"
                },
                {
                    "k" : "price",
                    "v" : 97.38
                },
                {
                    "k" : "quantity",
                    "v" : NumberInt(57)
                },
                {
                    "k" : "size",
                    "v" : "occaecati"
                },
                {
                    "k" : "color",
                    "v" : "temporibus"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "remove_from_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "sapiente"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "remove_from_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "quo"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "remove_from_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "officiis"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "search",
            "v" : [
                {
                    "k" : "query",
                    "v" : "qui"
                },
                {
                    "k" : "results_count",
                    "v" : NumberInt(27)
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "add_to_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "https://www.cartwright.biz/aut-eos-blanditiis-est-voluptas-eius"
                },
                {
                    "k" : "price",
                    "v" : 93.39
                },
                {
                    "k" : "quantity",
                    "v" : NumberInt(51)
                },
                {
                    "k" : "size",
                    "v" : "nihil"
                },
                {
                    "k" : "color",
                    "v" : "rerum"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "search",
            "v" : [
                {
                    "k" : "query",
                    "v" : "deleniti"
                },
                {
                    "k" : "results_count",
                    "v" : NumberInt(94)
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "add_to_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "http://www.baumbach.org/est-illo-similique-nostrum-perspiciatis-sint-itaque-facere.html"
                },
                {
                    "k" : "price",
                    "v" : 4.78
                },
                {
                    "k" : "quantity",
                    "v" : NumberInt(19)
                },
                {
                    "k" : "size",
                    "v" : "ratione"
                },
                {
                    "k" : "color",
                    "v" : "esse"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "add_to_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "http://batz.com/qui-ab-eaque-aut-neque-ad"
                },
                {
                    "k" : "price",
                    "v" : 66.02
                },
                {
                    "k" : "quantity",
                    "v" : NumberInt(8)
                },
                {
                    "k" : "size",
                    "v" : "nobis"
                },
                {
                    "k" : "color",
                    "v" : "dolores"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "viewed_page",
            "v" : [
                {
                    "k" : "url",
                    "v" : "http://schowalter.com/"
                },
                {
                    "k" : "page_title",
                    "v" : "assumenda"
                },
                {
                    "k" : "page_type",
                    "v" : "debitis"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "search",
            "v" : [
                {
                    "k" : "query",
                    "v" : "quas"
                },
                {
                    "k" : "results_count",
                    "v" : NumberInt(48)
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "viewed_page",
            "v" : [
                {
                    "k" : "url",
                    "v" : "http://www.kautzer.com/consectetur-repellat-sit-doloremque-possimus-dolorum.html"
                },
                {
                    "k" : "page_title",
                    "v" : "et"
                },
                {
                    "k" : "page_type",
                    "v" : "necessitatibus"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "viewed_page",
            "v" : [
                {
                    "k" : "url",
                    "v" : "http://www.renner.com/consequatur-labore-ducimus-minus"
                },
                {
                    "k" : "page_title",
                    "v" : "recusandae"
                },
                {
                    "k" : "page_type",
                    "v" : "harum"
                }
            ],
            "t" : NumberInt(2)
        },
        {
            "k" : "add_to_cart",
            "v" : [
                {
                    "k" : "product",
                    "v" : "http://zulauf.net/delectus-qui-nihil-quia-officia-reprehenderit"
                },
                {
                    "k" : "price",
                    "v" : 76.76
                },
                {
                    "k" : "quantity",
                    "v" : NumberInt(16)
                },
                {
                    "k" : "size",
                    "v" : "aut"
                },
                {
                    "k" : "color",
                    "v" : "quaerat"
                }
            ],
            "t" : NumberInt(2)
        }
    ]
}

After that, I created the following index:

db.contats.createIndex({ "workspace_id": 1, "data.v": 1, "created_at": -1 )

It is really fast when searching something like this:

db.getCollection("contactst").find({
    "workspace_id": 1,
    "data": {
        $elemMatch: {
            "k": "viewed_page", "v": { $elemMatch: { "k": "page_title", "v": "excepturi" } }, "t": 2
        }
    }
}).limit(25)

But, this is ONLY fast when there is page_title with value of excepturi.

If I search this for example:

db.getCollection("contacts").find({
    "workspace_id": 1,
    "data": {
        $elemMatch: {
            "k": "viewed_page", "v": { $elemMatch: { "k": "page_title", "v": "SOME-NON-EXISTING RECORD-HERE" } }, "t": 2
        }
    }
}).limit(25)

then it takes ~2 minutes to query.

This is explain:

{
    "explainVersion" : "1",
    "queryPlanner" : {
        "namespace" : "test.contacts",
        "indexFilterSet" : false,
        "parsedQuery" : {
            "$and" : [
                {
                    "data" : {
                        "$elemMatch" : {
                            "$and" : [
                                {
                                    "v" : {
                                        "$elemMatch" : {
                                            "$and" : [
                                                {
                                                    "k" : {
                                                        "$eq" : "page_title"
                                                    }
                                                },
                                                {
                                                    "v" : {
                                                        "$eq" : "NON-EXISTING"
                                                    }
                                                }
                                            ]
                                        }
                                    }
                                },
                                {
                                    "k" : {
                                        "$eq" : "viewed_page"
                                    }
                                },
                                {
                                    "t" : {
                                        "$eq" : 2.0
                                    }
                                }
                            ]
                        }
                    }
                },
                {
                    "workspace_id" : {
                        "$eq" : 1.0
                    }
                }
            ]
        },
        "queryHash" : "8A0FD575",
        "planCacheKey" : "0D8E423A",
        "maxIndexedOrSolutionsReached" : false,
        "maxIndexedAndSolutionsReached" : false,
        "maxScansToExplodeReached" : false,
        "winningPlan" : {
            "stage" : "LIMIT",
            "limitAmount" : 25.0,
            "inputStage" : {
                "stage" : "FETCH",
                "filter" : {
                    "data" : {
                        "$elemMatch" : {
                            "$and" : [
                                {
                                    "k" : {
                                        "$eq" : "viewed_page"
                                    }
                                },
                                {
                                    "t" : {
                                        "$eq" : 2.0
                                    }
                                },
                                {
                                    "v" : {
                                        "$elemMatch" : {
                                            "$and" : [
                                                {
                                                    "k" : {
                                                        "$eq" : "page_title"
                                                    }
                                                },
                                                {
                                                    "v" : {
                                                        "$eq" : "NON-EXISTING"
                                                    }
                                                }
                                            ]
                                        }
                                    }
                                }
                            ]
                        }
                    }
                },
                "inputStage" : {
                    "stage" : "IXSCAN",
                    "keyPattern" : {
                        "workspace_id" : 1.0,
                        "data.v" : 1.0,
                        "created_at" : -1.0
                    },
                    "indexName" : "workspace_id_1_data.v_1_created_at_-1",
                    "isMultiKey" : true,
                    "multiKeyPaths" : {
                        "workspace_id" : [

                        ],
                        "data.v" : [
                            "data",
                            "data.v"
                        ],
                        "created_at" : [

                        ]
                    },
                    "isUnique" : false,
                    "isSparse" : false,
                    "isPartial" : false,
                    "indexVersion" : 2.0,
                    "direction" : "forward",
                    "indexBounds" : {
                        "workspace_id" : [
                            "[1, 1]"
                        ],
                        "data.v" : [
                            "[MinKey, MaxKey]"
                        ],
                        "created_at" : [
                            "[MaxKey, MinKey]"
                        ]
                    }
                }
            }
        },
        "rejectedPlans" : [

        ]
    },
    "command" : {
        "find" : "contact_tests",
        "filter" : {
            "workspace_id" : 1.0,
            "data" : {
                "$elemMatch" : {
                    "k" : "viewed_page",
                    "v" : {
                        "$elemMatch" : {
                            "k" : "page_title",
                            "v" : "NON-EXISTING"
                        }
                    },
                    "t" : 2.0
                }
            }
        },
        "limit" : 25.0,
        "$db" : "jellyreach_backup"
    },
    "serverInfo" : {
        "host" : "MacBook-Pro.local",
        "port" : 27017.0,
        "version" : "6.0.1",
        "gitVersion" : "32f0f9c88dc44a2c8073a5bd47cf779d4bfdee6b"
    },
    "serverParameters" : {
        "internalQueryFacetBufferSizeBytes" : 104857600.0,
        "internalQueryFacetMaxOutputDocSizeBytes" : 104857600.0,
        "internalLookupStageIntermediateDocumentMaxSizeBytes" : 104857600.0,
        "internalDocumentSourceGroupMaxMemoryBytes" : 104857600.0,
        "internalQueryMaxBlockingSortMemoryUsageBytes" : 104857600.0,
        "internalQueryProhibitBlockingMergeOnMongoS" : 0.0,
        "internalQueryMaxAddToSetBytes" : 104857600.0,
        "internalDocumentSourceSetWindowFieldsMaxMemoryBytes" : 104857600.0
    },
    "ok" : 1.0
}

Why? It looks like event when searching for non-existing fields is using index, but it is still so much slow. Our data is pretty dynamic so I’ve selected this structure.

Bumping this.

I created one simple collection array and tested. Happens there too.

When array element does not exist, it is slow.

Adding wildcard index to data seems to be working.

However, I’m curious why didn’t work compound index on workspace_id and data (multikey index)?

Hey @jellyx,

The reason why your index on workspace_id_1_data.v_1_created_at_-1 is not performing well when searching for a non-existing value is that queryPlanner has to search through all the index keys to perform the operation. You can check this by reading the explain output of your queries. To confirm this, I created a collection of 2100 documents from the sample document you provided. I created an index workspace_id_1_data.v_1_created_at_-1.
Then I used your first query:

db.testing.find({
    "workspace_id": 1,
    "data": {
        $elemMatch: {
            "k": "viewed_page", "v": { $elemMatch: { "k": "page_title", "v": "excepturi" } }, "t": 2
        }
    }
}).limit(25).explain('executionStats')

The execution stats were

{
  executionStats: {
    executionSuccess: true,
    nReturned: 25,
    executionTimeMillis: 0,
    totalKeysExamined: 53,
    totalDocsExamined: 5,

}

Notice in the executionStats, executionTimeMillis is 0, and totalKeysExamined is 53 while documents returned is 25 (query targeting ratio is about 0.47: 0.47 document returned for each index key examined.

Now running this for the second query:

db.testing.find({
    "workspace_id": 1,
    "data": {
        $elemMatch: {
            "k": "viewed_page", "v": { $elemMatch: { "k": "page_title", "v": "something" } }, "t": 2
        }
    }
}).limit(25).explain('executionStats')

we got:


  executionStats: {
    executionSuccess: true,
    nReturned: 0,
    executionTimeMillis: 85,
    totalKeysExamined: 101611,
    totalDocsExamined: 1104


As you can see, executionTimeMillis becomes 85, and the totalKeysExamined is 101611 with totalDocsExamined being 1104 while the query returns nothing. This shows when a value does not exist, the queryPlanner has to search through a big part of the indexes and hence the time.

Additionally, why are you using index workspace_id_1_data.v_1_created_at_-1, instead of workspace_id_1_data.k_1_created_at_-1 ie, instead of data.v, use data.k in our index. This should give a better performance based on the two queries you provided. I tested this on my end as well. Changed the index to workspace_id_1_data.k_1_created_at_-1. For the first query, the explain output was:


executionStats: {
      executionSuccess: true,
      nReturned: 25,
      executionTimeMillis: 0,
      totalKeysExamined: 37,
      totalDocsExamined: 37

Notice in the executionStats, only 37 keys had to be examined against 53 originally, while returning 25 documents (query targeting a ratio of 0.67, which is already much better than the earlier 0.47).
For the second query, the explain output was:

{
  executionStats: {
    executionSuccess: true,
    nReturned: 0,
    executionTimeMillis: 10,
    totalKeysExamined: 1055,
    totalDocsExamined: 1055

}

Here too, the totalKeysExamined reduces to 1055 instead of 101611 with the original key. The executionTimeMillis also comes down to 10 from 85.

In conclusion, I believe by modifying your index, you can achieve better query-targeting ratio by allowing the server to zoom in to the relevant part of the collection quickly, eliminating a lot of unnecessary work. I would note that in the best case above, the query targeting ratio is still not close to 1 (where 1 index key scan returns 1 document). The server is doing the work at maximum efficiency when this ratio is 1.

Please let us know if there are any doubts about this. Feel free to reach out for anything else as well.

Regards,
Satyam

1 Like