Proposal: Substring Filtering

[myronmarston]

Context

Current ElasticGraph API

ElasticGraph currently offers two filter inputs for String fields:

input StringFilterInput {
  allOf: [StringFilterInput!]
  anyOf: [StringFilterInput!]
  equalToAnyOf: [String]
  not: StringFilterInput
}

input TextFilterInput {
  allOf: [TextFilterInput!]
  anyOf: [TextFilterInput!]
  matchesPhrase: MatchesPhraseFilterInput
  matchesQuery: MatchesQueryFilterInput
  not: TextFilterInput
}

TextFilterInput is used for String fields defined with f.mapping type: "text"; StringFilterInput is used for the rest.

At Block, we have some internal ElasticGraph clients that need case-insensitive substring filtering. The full text search predicates (matchesQuery and matchesPhrase) can provide substring filtering in some cases, but it doesn't provide general purpose substring filtering. For example, if you filter on "script" it'll match a text value like "A bash script" but it won't match a string value like "subscription", at least with default field settings. Furthermore, we'd like to use this on fields that have not been indexed as text.

Therefore, we're interested in expanding the ElasticGraph filtering API to offer substring filtering.

Elasticsearch/OpenSearch Offerings

Elasticsearch and OpenSearch have a few features that could be used here:

• Regexp query (ES, OS)
• Wildcard query (ES, OS)
• N-gram token filter (ES, OS)

For our purposes, I believe the wildcard query will work best, for a few reasons:

• N-gram token filter is likely to be quite performant, but is complex to configure and requires careful up-front planning to know which fields would need to use the ngram token filter. We want to offer substring filtering as a general feature from StringFilterInput on all String fields, so this isn't suitable for our general implementation. However, it can remain an option for a potential future optimization for specific fields.
• A wildcard query maps very closely to the substring semantics we want using an expression like "*script*".
• A regexp query can easily provide substring semantics using an expression like ".*script.*". However, Regexp is strictly more flexible/powerful than wildcard, and we consequently expect wildcard queries to perform equivalently or better.
• The wildcard field type (ES, OS), when used, can make both Regexp and Wildcard queries much more performant.

While we plan to use a wildcard query to implement this, we do not plan to expose direct access to the wildcard query operator, instead offering a more limited substring filter that internally translates into a wildcard query. This is in keeping with ElasticGraph's current level of abstraction and retains some nice flexibility: since substring filtering can be implemented in multiple ways, we can change that implementation in the future if there is need! ElasticGraph is designed to expose a curated subset of Elasticsearch/OpenSearch functionality to clients while offering excellent performance. This approach aligns with that.

Prefix Filtering

Elasticseach and OpenSearch also offer a dedicated prefix query. Prefix queries should be more performant than substring queries, and the Elasticsearch/OpenSearch Wildcard docs highlight the fact that * should be avoided at the beginning of a wildcard query.

Given that, I plan to offer a prefix filtering predicate alongside the substring filtering predicate, allowing clients who want the more strict semantics of a prefix search to opt-in to a more performant query.

Future Plans: Unify StringFilterInput and TextFilterInput

While StringFilterInput and TextFilterInput are currently distinct, in the future I'd like to unify them using the multi-fields feature. This feature would allow a single field to be indexed in multiple ways--as both text and keyword, for example, enabling a single filter input containing all of the string/text filtering predicates.

While the design of a multi-fields feature is out of scope for this proposal, it's worth bearing in mind because the API changes proposed here should ideally be compatible with this future direction.

API Options

Option 1: contains: String/startsWith: String

The simplest option is just to add contains and startsWith predicates:

input StringFilterInput {
  allOf: [StringFilterInput!]
  anyOf: [StringFilterInput!]
  contains: String
  equalToAnyOf: [String]
  not: StringFilterInput
  startsWith: String
}

However, it feels inconsistent that equalToAnyOf accepts a list of values while contains and startsWith only accept a single value. If a client wants to express a filter like name contains "foo" OR name contains "bar" than they'd have to wrap it with an anyOf:

filter: {
  name: {
    anyOf: [
      {contains: "foo"}
      {contains: "bar"}
    ]
  }
}

That's a bit annoying to work with.

Option 2: containsAnyOf: [String!]/startsWithAnyOf: [String!]

With this option, StringFilterInput would be updated like so:

input StringFilterInput {
  allOf: [StringFilterInput!]
  anyOf: [StringFilterInput!]
  containsAnyOf: [String!]
  equalToAnyOf: [String]
  not: StringFilterInput
  startsWithAnyOf: [String!]
}

This is simpler to use for the case discussed above:

filter: {
  name: {
    containsAnyOf: ["foo", "bar"]
  }
}

However, it doesn't provide a clear place to specify whether it should be case sensitive or not. There are a couple ways we can offer that functionality.

Option 2a: ignoreCase argument

For this option, we'd add an ignoreCase argument alongside the other predicates:

input StringFilterInput {
  allOf: [StringFilterInput!]
  anyOf: [StringFilterInput!]
  containsAnyOf: [String!]
  equalToAnyOf: [String]
  ignoreCase: Boolean = false
  not: StringFilterInput
  startsWithAnyOf: [String!]
}

By default, a query would be case-sensitive, but a client could choose to ignore case:

filter: {
  name: {
    ignoreCase: true
    containsAnyOf: ["foo", "bar"]
  }
}

However, this API allows ignoreCase: true to be specified along with any of the StringFilterInput subfields. It's not clear what these expressions would mean:

filter: {
  name: {
    ignoreCase: true
    allOf: [
      # ...
    ]
  }
}

filter: {
  name: {
    ignoreCase: true
    anyOf: [
      # ...
    ]
  }
}

filter: {
  name: {
    ignoreCase: true
    not: {
      # ...
    }
  }
}

In addition, equalToAnyOf is always case sensitive. And matchesQuery/matchesPhrase are case-insensitive, which could matter when we unify StringFilterInput and TextFilterInput. As far as I know, there's no way to make matchesQuery/matchesPhrase case-sensitive.

We don't want to offer an input argument that is easy to misuse/misunderstand, so this doesn't seem like an ideal option.

Option 2b: separate caseSensitivelyContainsAnyOf/caseInsensitivelyContainsAnyOf predicates

Here's how this option would look:

input StringFilterInput {
  allOf: [StringFilterInput!]
  anyOf: [StringFilterInput!]
  caseInsensitivelyContainsAnyOf: [String!]
  caseInsensitivelyStartsWithAnyOf: [String!]
  caseSensitivelyContainsAnyOf: [String!]
  caseSensitivelyStartsWithAnyOf: [String!]
  equalToAnyOf: [String]
  not: StringFilterInput
}

This avoids the issues presented by ignoreCase with the above option. However, caseInsensitivelyContainsAnyOf is quite the mouthful. This doesn't feel like a great API to me.

Option 3: contains: StringContainsFilterInput/startsWith: StringStartsWithFilterInput

Here's the schema for this option:

input StringContainsFilterInput {
  allSubstringsOf: [String!]
  anySubstringOf: [String!]
  ignoreCase: Boolean = false
}

input StringStartsWithFilterInput {
  anyPrefixOf: [String!]
  ignoreCase: Boolean = false
}

input StringFilterInput {
  allOf: [StringFilterInput!]
  anyOf: [StringFilterInput!]
  contains: StringContainsFilterInput
  equalToAnyOf: [String]
  not: StringFilterInput
  startsWith: StringStartsWithFilterInput
}

And here are some examples of how it would be used:

filter: {
  name: {
    contains: {
      anySubstringOf: ["foo", "bar"]
      ignoreCase: true
    }
  }
}

filter: {
  name: {
    contains: {
      allSubstringsOf: ["foo", "bar"]
    }
  }
}

filter: {
  name: {
    startsWith: {
      anyPrefixOf: ["foo", "bar"]
    }
  }
}

This allows ignoreCase to be specified just under contains: {...} and startsWith: {...}, scoping it appropriately. In addition, it opens the door to offering both contains: {allSubstringsOf: ...} and contains: {anySubstringOf: ...}, which is a nice bit of added flexibility.

Note

We don't offer an all field under startsWith because I don't believe it's useful. A string can easily contain multiple substrings, but it can only start with one prefix.

Proposal

I propose we implement Option 3--contains: {anySubstringOf: [...], allSubstringsOf: [...]} and startsWith: {anyPrefixOf: [...]}. This option provides maximal flexibility and (in my opinion, at least) reads nicely. contains will translate to a wildcard query, and startsWith will translate to a prefix query. In the future, when we offer a first-class multi-fields feature, these predicates can be enhanced to use a wildcard field if the field has a wildcard variant in the index mapping.

Consequences

• Clients will be be able to perform substring and prefix searches.
• Clients will not be offered the full power of wildcard or regexp queries; however, the door remains open to offering those in the future when a need arises.
• These new filter predicates are not expected to perform as well as equalToAnyOf, matchesQuery, or matchesPhrase. However, a number of optimization avenues are open to us, including the use of wildcard fields.

[myronmarston]

This has been implemented in #557, #559, and #560.