Classic plan cache key does not take into account whether the regex has a prefix match.

Given query {b:{$regex:/^fun/}}, we can use an index on "b", eg:

// key=reb|||f<11>

------IXSCAN
---------indexName = b_1
---------keyPattern = { b: 1.0 }
---------direction = 1
---------bounds = field #0['b']: ["fun", "fuo"), [/^fun/, /^fun/]
---------iets = (iets { b: 1.0 } (b: 1.0 (eval $regex #0)))

If we execute the above query first, we'll cache a plan using the index. If we then execute the query {b:{$regex:/fun/}} (no fixed prefix), we'll reuse the index plan and build the following bounds, including a residual filter:

---------filter = b regex /fun/ || Selected Index #5 pos 0 combine 1
---------direction = 1
---------bounds = field #0['b']: ["", {}), [/fun/, /fun/]
---------iets = (iets { b: 1.0 } (b: 1.0 (eval $regex #0)))

If we execute the "no fixed prefix" query first, then we'll cache a COLLSCAN plan and reuse it even when a prefix is present.