Support case insensitive search on new wildcard field and keyword

[markharwood]

Currently the wildcard field only supports case sensitive search but it is vital that we find a way to offer case insensitive search too. A recent blog post highlighted general string-matching problems and how users have resorted to ugly regex expressions like this one to overcome issues with case sensitivity:

/[Cc]:\\[Ww][Ii][Nn][Dd][Oo][Ww][Ss]\\[Ss][Yy][Ss][Tt][Ee][Mm]32\\.*/

The example above is a search for a string from a case-insensitive operating system where hackers may have used mixed case commands deliberately to try avoid simpler rule detection.

Solution 1: Index-time case choices

We could make the wildcard field accept an optional normalizer to lower-case the content at index time (much like the keyword field). However, in a centralised logging system we may be storing content from both Windows and Unix machines which are case insensitive and case sensitive file systems respectively. The importance of case may vary from one document to the next. This would typically mean that we would be forced to index with multi-fields (one case sensitive, the other not) which would double the storage costs.

Solution 2: query-time choices

The wildcard field already has 2 representations of the original content - an ngram index for approximate matching and a binary doc value of the original bytes for verification of approximate matches. If the ngram index is changed to always use lower-case then the decision to have case-sensitive matching or not becomes a query-time option when verifying candidate matches. There would be a (likely small) increase in the number of false-positives from the approximate matching but the big advantage is no increase in today's storage costs (actually a decrease if we normalise ngrams).

In either solution the searcher has to make a conscious decision - either to search a case-insensitive field or to declare the query clause as case-insensitive.

Solution 2 looks preferable to me from the back end but is a break with existing approaches where case-sensitivity is an index-time mapping decision not a property of a query clause. This means that the wildcard query clause would have a case-sensitive parameter that is relevant if you target a wildcard field but not on a text or keyword field (although we could amend keyword field logic to support this too).

Thoughts @jimczi @jpountz ?

[elasticmachine]

Pinging @elastic/es-search (:Search/Mapping)

[markharwood]

Maybe there's a third solution.
Solution 1 indexes content twice.
Solution 2 changes the query syntax.
Maybe a wildcard field can automatically have a pseudo multi-field which is defined as being case insensitive. As an example - a field called foo can be assumed by users to have a foo._nocase field which isn't anything physical -it's really just used as a signal that the verification query should make the pattern-matching it does case insensitive. There's no extra storage costs or extra flags required on query clauses with this approach.

[markharwood]

I opened a PR for this third option. #53814

[webmat]

From ECS' POV it's important to preserve the ability to query case sensitively, as well as offer the ability to query case insensitively. Both are important, but my understanding is that case insensitivity is the most important one of the two, especially on a fuzzy kind of search like wildcard.

Currently in ECS, most fields are keyword only. Some fields that require flexibility in how users search, whether because their content is messy (e.g. user agent) or because they're places where users do threat hunting (e.g. file paths & names, command lines) now also have a text multi-field. So the canonical string fields (e.g. myfield) are always keyword, and in some places we have myfield.text for full text search.

I think in most cases, the same fields that have text multi-fields will be candidates for wildcard as well.

If we add wildcard fields to the mix, they would likely be as another multi-field (e.g. myfield.wildcard). Here I'm making the assumption that wildcard could not replace keyword as the canonical type, since keyword and wildcard are not similar enough. Is this assumption correct?

If the above is correct, then when adding wildcard as a multi-field at myfield.wildcard, my understanding of your example would be that we also have myfield.wildcard._nocase as a way to query case insensitively?

If this is the case, I would like to suggest we flip the behaviours around instead. By default, I think most people would want case insensitive search on a wildcard field. Wildcards are already a fuzzy search. Then only when case sensitivity is needed (and keyword doesn't solve the need), they would resort to a virtual subfield to get wildcard + case sensitivity.

In other words, can we do:

• myfield.wildcard: supports wildcards case insensitively
• myfield.wildcard._cs: supports wildcards case sensitively (suggestions welcome on the ._cs naming 🙂)

@rw-access was telling me Endgame only supports case insensitive search, and then additional filtering or analysis is done, if case is important.

And actually, based on what Ross was telling me, perhaps we could even consider having wildcard only do case insensitive, and not even have a virtual sub-field?

@neu5ron ping

[markharwood]

Here I'm making the assumption that wildcard could not replace keyword as the canonical type, since keyword and wildcard are not similar enough. Is this assumption correct?

I think the differences come down to:

Feature	keyword	wildcard
Sort by speeds	Fast	Not quite as fast (*caveat 1)
Aggregate speeds	Fast	Not quite as fast (*caveat 1)
Prefix query speeds (foo*)	Fast	Not quite as fast (*caveat 2)
Leading wildcard query speeds on high-cardinality fields (*foo)	Terrible	Much faster
Term query. full value match (foo)	Fast	Not quite as fast (*caveat 2)
Fuzzy query.	Y (if allow expensive queries enabled)	N
Regex query.	Y (if allow expensive queries enabled)	N
Range query.	Y (if allow expensive queries enabled)	N
Disk costs for mostly unique values	high	lower
Disk costs for mostly identical values	low	medium
Max character size for a field value	256 for default JSON string mappings, 32,766 Lucene max	unlimited

Caveat 1: somewhat slower as doc values retrieved from compressed blocks of 32
Caveat 2: somewhat slower because approximate matches with ngrams need verification

perhaps we could even consider having wildcard only do case insensitive, and not even have a virtual sub-field?

That would be faster to search. There's an overhead in my option 3 converting stored mixed-case values to lower-case at query-time. While it minimises disk storage costs required to support CS and non-CS the better trade-off might be to just make the field fast for the primary use case (non-CS).

[jimczi]

And actually, based on what Ross was telling me, perhaps we could even consider having wildcard only do case insensitive, and not even have a virtual sub-field?

I like the fact that the wildcard is just a keyword field optimized for wildcard queries. For this reason I think it would be easier to simply allow a normalizer like we have for the keyword field. This would force users to choose whether they want to normalize upfront but I don't think we should eagerly normalize or create a virtual sub-field.

[markharwood]

I opened #53851 to add the normalizer support.

There's no normalisation by default but I would like to make it easier for the simple case of users wanting case-insensitive. Having to declare an analysis section just to define and register lower-case token filters is a pain. Can we ship elasticsearch with a named normalizer e.g. lowercase? That would make adding case insensitivity for a field a single-liner rather than complex JSON to define the analysis settings for lowercasing. I opened #53872 to discuss adding a pre-declared named normalizer.

[neu5ron]

Hey all, co-author of the ugly regex blog here 🙃
Great discussion!

I like the proposed solution of keyword and wildcard case insensitive.
I want to stress however, that if its made a choice then the community will run into similar issues that are occurring elsewhere - which one entity having something different than another. This is not something that certain people need - this is something that all security/logging use cases need.

Regarding storage - I believe solving a visibility gap is critical and the side affect of increasing storage is an acceptable con/negative. Also:

• For all of elasticsearch history (until recently) everything was a multi field
• People can and should use roll ups
• People can and should use enhanced compressions after certain amount of days.

There should still be a good analyzed field similar to the text analyzer - maybe even an improved one for security use case. Because if we dont have an analyzed field then we miss out on a lot of the additional powers of lucene like fuzzy query and the newer terms query.
However, I can live without an analyzed field if we have a case insensitive ability. Because not many were using those advanced queries of lucene - and for those who were they can add it if need be.

[webmat]

Here I'm making the assumption that wildcard could not replace keyword as the canonical type, since keyword and wildcard are not similar enough. Is this assumption correct?

Let me phrase that as a more direct question :-)

If index-1 has field myfield as keyword and index-2 has the same field as wildcard, would a query across myfield-* raise an error such as "aggregation_execution_exception"?

Also, can we do aggregations on wildcard fields?

Understanding whether we can replace keyword fields transparently with the wildcard data type where appropriate will inform our strategy here.

[neu5ron]

i think the gist is we need to have keyword and have to wildcard lowercase. if the standard is set, implemented in beats or what not, and communicated then we should not have to worry about such overlap of fields - right @webmat

[markharwood]

Understanding whether we can replace keyword fields transparently with the wildcard data type where appropriate will inform our strategy here.

All field types are expected to respond to requests for the same set of query types prefix/term/wildcard/range/fuzzy etc.
Some field types outright reject some query types (eg wildcard currently doesn't do fuzzy) while others will attempt to perform a query type but not nearly as fast as other field types because their data structures aren't optimised for that case. For this reason it's not always a yes/no supported-features matrix for field types - there are variable performance characteristics. Perhaps the main reason for creating the wildcard field is not that keyword fields couldn't run wildcard queries but because they did so very slowly.

See my feature comparison table here

I'm also working on a blog for the 7.7 release to help expand on choosing between field types now that we have wildcard in the mix.