Cut filtered dataset search from 30+ minutes to sub-second at 25–50M records

Client and system names are omitted for confidentiality. The architecture, mechanisms and numbers are real.

Context

An enterprise data platform stores datasets as MongoDB collections that range from a few thousand to tens of millions of documents and keep growing. Users browse them through a data grid (Angular / PrimeNG) that filters, sorts, paginates and runs “contains” searches on arbitrary columns. The platform is self-hosted, often air-gapped, and deployed per customer on Kubernetes. Schemas are user-defined, so no one knows in advance which fields a collection will have or how large it will get.

The problem and its cost

On a collection of roughly 25 million documents, a filtered, sorted grid request was reported to take 30+ minutes. The request thread was blocked for the whole time, and the grid was effectively unusable on exactly the collections users cared about most.

The size of the collection was not the cause. A correctly indexed query on 25M documents answers in single-digit milliseconds and stays flat as data grows. The latency came from four separate design problems stacked on top of each other.

Constraints

• No new infrastructure by default. Every added service means another deployment per customer site, including air-gapped ones.
• No new third-party license.
• Unknown, user-defined schemas. Indexes can’t be designed once, by hand, for a fixed model.
• No breaking changes for grid users.

Diagnosis: four stacked problems

#	Problem	Effect
1	Indexes were shaped for ingestion (insertion date), not for the grid’s query shapes	Every filter and sort was a collection scan plus an in-memory sort
2	Offset pagination (skip/limit)	Page N re-scans every preceding match; deep pages get linearly slower
3	A total count on every request, whether or not the UI displayed it	A second full scan per page
4	Unanchored substring search (contains)	No index can serve it; 60–80 s in the no-match and sorted cases, the ones partial input triggers most

Method: measure before touching production

A throwaway collection of 25,000,000 realistically shaped documents was built, and every candidate change was measured with MongoDB’s query planner (explain("executionStats")): documents examined, keys examined, in-memory sort or not, wall time. Every decision below rests on those before/after numbers rather than on intuition.

Stage 1: the free fixes

Query-shaped compound indexes (ESR order). Indexes built in the order the grid actually queries: Equality fields first, then the Sort field, then Range fields. The sort is served by the index, and in-memory sorts disappear.

// simplified, illustrative
db.records.createIndex({ status: 1, title: 1, createdAt: 1 })
//                       equality ─┘   sort ─┘   range ─┘

Keyset pagination instead of offset. The client passes the sort key and _id of the last row it saw, and the next page starts exactly there. Every page costs the same as page one.

// simplified, illustrative
db.records.find({ status: "active",
                  $or: [ { title: { $gt: lastTitle } },
                         { title: lastTitle, _id: { $gt: lastId } } ] })
          .sort({ title: 1, _id: 1 }).limit(pageSize)

Counts on demand. The total is computed only when the UI actually needs it, not on every page request.

Together, these took the reported 30-minute case to sub-second for every query type except unanchored substring search.

Stage 2: substring search, three options measured

Measured side by side at 25M documents:

Option	Result	Verdict
Do nothing (collection scan)	Fast when matches are common; 60–80 s for no-match or sorted queries	Rejected
Vendor-native n-gram index	Plain contains acceptable; ~49 s once combined with sorting, which is the combination the grid needs	Rejected
Self-provisioned n-gram index on the existing MongoDB	Worst case ~80 s → ~1 ms	Chosen

How it works. At write time, searchable string fields are split into overlapping 4-character grams (drag, rago, agon for “dragon”). The grams are stored in an indexed array. A contains query becomes an index lookup on the query’s grams, which returns a small candidate set. Only those candidates are then verified with the exact substring match.

Prefix and suffix need no n-grams. A normal index serves “starts with”. A second index on a reversed copy of the field turns “ends with” into the same kind of prefix lookup. Three of the grid’s most common operators stop scanning documents.

The index provisions itself. It is built only for collections that are large enough to need it, because below a few hundred thousand documents a scan is already fast. It is also pruned based on which fields users actually search.

Linked-value fields. Some fields hold references to other records, and users search those too. A second benchmark on 8.4M documents found a no-match search against such a field took ~2.7 s, projected to ~16 s at 50M. Folding those values into the same n-gram index brought the no-match case from ~2.7 s to ~2 ms, and a dense match (hundreds of thousands of hits) from ~900 ms to ~10 ms.

Rejected: a dedicated search engine

OpenSearch was evaluated. It is the standard answer once fuzzy, faceted, relevance-ranked search becomes the actual product requirement. Here it would have meant an extra service plus a change-data-capture pipeline to keep it in sync, per customer and per site, including air-gapped ones. That is a lot of operational weight for a problem the existing database could solve. It stays documented as the next step if that requirement ever appears.

Sizing: keeping the index in cache

The n-gram index is not free. At tens of millions of documents, the real question is whether it fits in the WiredTiger cache or falls back to disk. The mitigation ladder, in order of effort:

1. Index compression: a configuration change that cuts index size by 40–50%.
2. Scope to searchable fields only: roughly halves coverage.
3. Skip small collections: below a few hundred thousand documents, don’t build it at all.
4. Selective per-field provisioning, guided by the database’s own index-usage statistics.
5. Move inline version history out of the documents: stored history padded documents several-fold, so moving it to its own collection multiplies how much of the working set fits in the same RAM.

What this does not fix

“Contains X, sorted by Y” still has to collect every match before it can sort. That is the offset problem again, one layer down. The fix is the same one, keyset pagination at that layer, but it requires the grid to request “the page after this key” rather than “page 500”. That is documented as the remaining work.

License check

This MongoDB deployment is self-hosted and embedded behind the application, not offered as a database service to third parties. The server license only becomes restrictive when the database itself is offered as a service. This was verified against the actual license text before committing to the approach, not assumed. The solution adds zero new third-party licenses.

Result

• Filtered search: 30+ minutes → sub-second, flat from small collections to 50M documents.
• Worst-case contains: ~80 s → ~1 ms. Linked-value no-match: ~2.7 s → ~2 ms.
• No new infrastructure, no new license, no change for grid users.
• Shipped in stages: free index and pagination fixes first, then the self-provisioning index, then n-grams. Users got faster search at each step instead of waiting for the full design.