Summary

For a left-anchored $regex, the planner derives a string prefix and scans only [prefix, prefix+1) in an ascending index. analyze_regex::getRegexPrefixMatch() handles {} and ? correctly by dropping the preceding character from the prefix. It treats } like {{+ instead, ending the prefix but *keeping the preceding character. {0,n}, {0} and {0,} all make that character optional, so documents that match with zero repetitions fall outside the index bounds. Results are silently short, with no error. The same bounds are used by find, $match, countDocuments, distinct, $in: [/re/], updateMany and deleteMany.

Observed on master (9.1.0 nightly, gitVersion e5ad5e50d389), identical on 9.0.2 and 8.0.32

Collection with one ascending index {s: 1} and s values "", "a", "aa", "aaa", "b", "ab", "abb", "abc", ".", "..", "é", "éé", "x", "1", "12345", "ABC1", "1" (_id = position). "scan" is hint({$natural: 1}) and "default" is the planner's choice (IXSCAN in every row):

pattern              scan              default         lost by index   indexBounds (prefix part)
^a\{0,2}$             [0,1,2]           [1,2]           ""              ["a", "b")
^a\{0}$               [0]               []              ""              ["a", "b")
^a\{0,}$              [0,1,2,3]         [1,2,3]         ""              ["a", "b")
^ab\{0,2}$            [1,5,6]           [5,6]           "a"             ["ab", "ac")
^a\{0,2}b$            [4,5]             [5]             "b"             ["a", "b")
^\.\{0,2}$            [0,8,9]           [8,9]           ""              [".", "/")
^\Qab\E\{0,2}$        [1,5,6]           [5,6]           "a"             ["ab", "ac")
^é\{0,2}$             [0,10,11]         [10,11]         ""              ["é", "ê")
^a \{0,2}$   (opt x)  [0,1,2]           [1,2]           ""              ["a", "b")
\Aa\{0,2}$   (opt m)  [0,1,2]           [1,2]           ""              ["a", "b")
^a\{0,2}$ lazy/poss.  ^a\{0,2}?$ and ^a\{0,2}+$ both lose "" as well
^a\{0,2}     (no $)   all 17            [1,2,3,5,6,7]   11 documents    ["a", "b")   (the regex matches every string)

-- controls, all correct --
^a\{1,2}$             [1,2]             [1,2]           -               ["a", "b")
^a\{2}$               [2]               [2]             -               ["a", "b")
^a+$                 [1,2,3]           [1,2,3]         -               ["a", "b")
^a*$                 [0,1,2,3]         [0,1,2,3]       -               ["", {})
^a?$                 [0,1]             [0,1]           -               ["", {})
^[a]\{0,2}$           [0,1,2]           [0,1,2]         -               ["", {})
^(?:a)\{0,2}$         [0,1,2]           [0,1,2]         -               ["", {})
^\d\{0,5}$            correct                                           ["", {})
^[A-Z]\{0,3}[0-9]+$   correct                                           ["", {})

Writes use the same bounds:

// fresh collection: "", "a", "aa", "aaa", index \{s:1}
db.r.updateMany(\{s: {$regex: "^a{0,2}$"}}, \{$set: {hit: true}})   // matchedCount: 2   (3 match)
db.r.deleteMany(\{s: {$regex: "^a{0,2}$"}})                         // deletedCount: 2   ("" is left behind)
db.r.find(\{s: {$in: [/^a{0,2}$/]}})                                // _id 1, 2          (scan: 0, 1, 2)

So the defect is gated exactly on a {min,...} quantifier with min == 0 applied directly to a literal character that is part of the derived prefix: a plain character, an escaped literal such as \., the last character of \Q...\E, or a literal followed by whitespace in x mode. Character classes, groups and escapes such as \d end the prefix earlier, so they are not affected.

Root cause

src/mongo/db/query/analyze_regex.cpp, getRegexPrefixMatch() (called from IndexBoundsBuilder::simpleRegex(), index_bounds_builder.cpp:219-235):

 90        if (c == '*' || c == '?') {
 91            // These are the only two symbols that make the last char optional.
 92            r = ss;
 93            r = r.substr(0, r.size() - 1);
 ...
 97            return \{r, false};
 ...
120        } else if (strchr("^$.[()+{", c)) {
121            // List of "metacharacters" from man pcrepattern.
 ...
132            r = ss;          // <-- keeps the character before '{'
133            break;

The comment on line 91 is wrong: {0,n}, {0} and {0,} also make the last character optional. '{' is grouped with '+', which needs at least one repetition, so the prefix ss keeps the optional character. For {n,m} with n >= 1 that is correct, which is why ^a{1,2}$ works and the bug only shows at min == 0.

Same function: multi-byte character before ? or * (related)

Line 93 drops one byte, not one character. When the optional character is multi-byte UTF-8, the "prefix" keeps a dangling lead byte. The scan then misses every document without that lead byte, and explain() emits an invalid UTF-8 string that the shell cannot decode:

^é?$     scan [0,10]       default [10]       loses ""      explain(): "BSONError: Invalid UTF-8 string in BSON document"
^é*$     scan [0,10,11]    default [10,11]    loses ""      explain(): same error

"é" is C3 A9. substr(0, size-1) leaves "\xC3", so the bounds become ["\xC3", "\xC4"). Whatever fix is applied to {0,...} should remove the whole last code point (and, for \Q...\E, the last quoted character).

Suggested fix

In getRegexPrefixMatch(), when c == '{', parse the brace. If it is a valid PCRE quantifier ({n}, {n,}, {n,m}) with n == 0, handle it exactly like {}/?: drop the preceding character from the prefix and return a non-exact prefix. Otherwise keep the current behaviour. In both the {}/? and {0,...} paths, remove the last UTF-8 code point rather than the last byte. Unit tests can extend index_bounds_builder_regex_test.cpp (or the analyze_regex tests) with ^a{0,2}$, ^a{0}$, ^a{0,}$, ^ab{0,2}$ and ^é?$, and a jstest can assert find(q) equals find(q).hint({$natural:1}).

Why it matters

{0,n} on a literal is an ordinary way to write "up to n of these", for example an optional repeated padding character (^0{0,3}[1-9]) or an optional separator ({0,1}\d). Both are affected. With s in "7", "07", "5", "-5" and an index on s, ^0{0,3}[1-9] returns only "07" (scan: "7", "07", "5"), and {0,1}\d returns only "-5" (scan: all four). The defect only appears when the field is indexed, which is when such queries run at scale. Nothing errors and the planner picks the index by itself, so the count is just short. The same bounds drive updateMany/deleteMany, so writes silently skip the zero-repetition documents too.