toObject({getters:true}) on projected documents: applyGetters iterates all schema paths and each unselected path triggers an O(projectionKeys) isSelected scan — O(paths x projection) per doc

toObject({getters:true}) on projected documents: applyGetters iterates all schema paths and each unselected path triggers an O(projectionKeys) isSelected scan — O(paths x projection) per doc

Repo: Automattic/mongoose Location: lib/document.js:4394 (applyGetters per-path $__isSelected call) x lib/document.js:2572 (isSelected projection-key scan) Severity: medium · Confidence: 0.75 Type: complexity-at-a-distance

Description

applyGetters in lib/document.js (line ~4371) loops over every key of schema.paths and calls self.$__isSelected(path) for each. Document.prototype.isSelected (line ~2525) is O(S) for any path not literally present in the projection: after the O(1) path in this.$__.selected check fails, it loops all projection keys doing startsWith comparisons (lines ~2572-2584). So serializing one projected document with getters enabled (a very common toJSON config) costs O(P x S) where P = schema paths and S = projection keys — per document, per serialization. The chain crosses three modules: lib/query.js _completeMany builds projected docs (fields propagated into the Document constructor, $__.selected set at lib/document.js:158), then user/toJSON triggers $toObject -> applyGetters -> isSelected. Each function looks fine locally; the product only appears across the boundary.

Benchmark

With schema width 2N and an inclusive projection of N keys, toObject({getters:true}) time should grow superlinearly, tracking the O(N^2) prediction (N=500 hundreds-to-thousands of times slower per pass than N=10) because each of the ~N unselected paths scans the N projection keys.

Observed complexity: O(N·M)

| Input | median_ms | ratio | note |
|-------|-----------|-------|------|
| N=10 | 2.75 | 1.00 | — |
| N=50 | 17.59 | 6.40 | — |
| N=100 | 68.20 | 24.79 | — |
| N=500 | 2199.44 | 799.43 | — |

benchmark confirmed