Planned change for default tokenizer in logs adapter

[fthevenet]

Hi!

I'm considering a change in the way lines of log files are tokenized when added as documents in the lucene index backend.
We're currently using the built-in StandardAnalizer, which has the following notable properties:

• Periods (dots) that are not followed by whitespace are kept as part of the token

This is an interesting property as it allows to search for IP addresses or URL as single tokens, but if makes looking for things in lines of codes difficult.
For instance:

Something a.foo.bar.randomStuff something
Somtehing b.foo.bar.randomStuff something
Something c.foo.bar.interestingBits something
Somtehing x.foo.bar.random Stuff something
Something y.foo.bar.interestingBits something
Somtehing z.foo.bar.randomStuff something*

It is not possible to easily filter all lines containing interestingBits, since this string is part of tokens that start with something that varies (a, b, c, x, y, z). And wildcards will not help here, because lucene does not allow a query to start with one (i.e. *foo is illegal).

[Arkanosis]

Hi!

That could for sure lead to a better search experience. I've already wished on some occasions that I could search for a logger using only its class name and not its fully qualified classified class name.

On the other hand, I'm pretty sure I'd like to keep the ability to search for a fully qualified class name. If that helps, I'm not sure preserving the dot itself if mandatory, though: I guess as long as searching for "foo.bar.baz.someMethod" works (rather that having to search for "foo bar baz someMethod" instead), that's fine. This probably only requires that the tokenization is the same for the logs and the query.

[fthevenet]

Also, sorry I was still editing my question and got sidetracked and so it was already changed when I saw your answer... 😅

[fthevenet]

I've protoyped a change like that in the tokeninzer config in the latest dev branch: https://github.com/binjr/binjr/tree/v3.12.0-dev
It basically behaves pretty much as you describe in your comment above.

I've spent a little bit of time and so far I like much better than the previous behaviour. That said, I made that change specifically to help me with what I've been working on at the moment, so of course my own feedback is quite biased, so I'd really like to get you opinion on this.

I'm just worried I'm going to hate it if I have to deal with a lot of IP addresses at some point...

[fthevenet]

NB: you can re-instate the old tokenizer by checking the doNotTokenizeOnDots property in the debug console, but you need to restart the application for that to take effect.

[fthevenet]

Last night I upgraded my system, and noticed plocate, a newer, faster version of mlocate, which was a newer, faster version of locate, which in turn was a newer, faster replacement for find. :-) It'd be interesting to harness (harvest? steal?) the algorithm it's using. I'm not saying that Lucene is bad, but when searching for a substring, it's not the right tool.

It's not really Lucene per se that makes it hard to look for exact substrings, but rather the way field tokenization is generally configured; so for instance to match everything that contains "Feb 20 19:3", you could use its regex syntax, something like /.*" "Feb 20 19:3".*/. Except that in our case, that's no going to give you anything because currently each line is tokenized in such a way that "Feb" "20" "19" etc... are split across as many tokens, and none of these will individually satisfy the expression.

Changing the default tokenization to satisfy that particular need would be detrimental to the more common case of looking for a single word. But that gave me an idea, though: we could add an extra field that index the whole line as single token to perform regex (or any other sub query that would benefit from that).
Say that we call that new field "regex", then you could type regex:/.*"Feb 20 19:3".*/ should have the expected effect.

@Arkanosis w.d.y.t? If find how to do a prefix handler in lucene, we could even take out the ceremonial /.* and .*/

Originally posted by @fthevenet in #123 (comment)

[fthevenet]

I'd suspect that putting the whole line into a token would slow things down a lot. Lucene would index the regex field, which on the plus side would make searching for a prefix of the field fast, but on the minus side, the index would be of no use for regular expression searching.

It'd be better to break the search string (possibly regular expressions, if they aren't too complicated) into tokens, find matching records, and then search for the literal string or regex in the matched lines. If some joker like me has entered a partial token, maybe ignore tokens that don't match anything (e.g. 3) or match too many things (e.g. Feb). Actually, this sorta-kinda sounds like what happens already, doesn't it?

The locate family of commands break input lines into three-character 'trigrams', and index those. They support regular expressions, but I'm not sure how they make it so fast. At one point, I wanted to index an arbitrary file, so I took the updatedb command and replaced find / with cat $inputfile, and voila, I could use locate on that file. Of course, that was back when updatedb was a shell script. 😄 🧓🏻

Originally posted by @PenelopeFudd in #123 (comment)

[fthevenet]

A regex search would be slower, but this would be a new, additional search mode that one would have to explicitly invoke from the query prompt; it would be up to the user to trade speed for functionality. Since the existing mode would still be there (and the default) I think this is perfectly reasonable.

It would be an issue if it slows down the indexing speed or increase the on-disk size too much, however. That would have to be benchmarked to see if it is reasonable to enable by default.

[fthevenet]

Also, we could indeed try and experiment with using n-grams in a similar way plocate works. Will need to dig into Lucene's doc to find out how to do that.
We'd probably loose some capabilities, like operators that relies on token position? But maybe that's not so much of a big deal?
These can only be apply within a single line of log anyway (as each line is indexed as a separate document), so that probably reduce there usefulness.

[PenelopeFudd]

I've had experience with Atlassian's Confluence (which uses Lucene), and tokenization drives me bonkers. :-/

Basically, when I want to search for an ip address or hostname, it finds pages that don't have the desired string, but do have some of the tokens. E.g. If I look for "jenkins.example.com", it finds pages with "jenkins.example.com" (good), but also pages with just "example" or "com" or "example.com" (bad). Since Example.com is my company's domain, there's a very high number of pages that have "example.com" on them, and even more with just "com", making the search results just about worthless.

So my advice there is to have a secondary search: Do the Lucene search first, and then filter the results it gives you using a slower but more precise string search. I do this with grep and awk: if I process a large logfile with awk, it'll take minutes, but if I filter it with grep first and feed that much-smaller result to awk, it takes seconds and gives the same results. The difference is that grep is highly optimized for searching strings, whereas awk has to be good at being a generalized language.

[fthevenet]

Hello!

So I have finally come up with a prototype for indexing log files using ngrams instead of word-based tokens in binjr (it took a while because as I suspected it took me some time to figure out how to do it but mostly because it made an existing bug in Lucene a lot more visible and I had to fix that first).

But first a quick word to maybe recap the discussion so far; when indexing log files, binjr currently split the text for each line in the log file trying to identify what looks like words and uses these so-called tokens as entries in the index for the line in question.
This is what most search engine do by default for natural language (at least for languages written using the roman alphabet) as it works pretty well and proves rather efficient in terms of both processing time and index size.
An index like that will only be able to find results when you query it using whole words, however. The search syntax provides features like fuzzy search and wildcards to allow searching for partial or approximate terms but this doesn't really help when you're searching for patterns that spread across several tokens.
An other approach then is to instead split the raw text into contiguous sequence of n characters - called n-grams - and uses those sequences as index entries for documents. At search time, you can then decompose the user entered terms into a sequence to n-grams in the same way and query the index for documents matching such sequence:

Indexing the word foobar using bigrams (ngrams where n=2) will result in the following tokens fo oo ob ba ar and searching for term ooba will search for the token sequence oo ob ba and match the doc.

This indexing strategy could possibly make for more convenient and intuitive way to filter out log file content and so it is available as an option in binjr and can be tried out right now in a preview for the next version available here: https://github.com/binjr/binjr/releases/tag/v3.12.0-SNAPSHOT

To activate the feature, go to the settings panel, in the "Logs" section and selecting "Index using N-Grams"

You will need to close and reopen any log file sources already open to re-index the files for the change to become effective.

There is an extra settings where you can choose the size of the ngrams (i.e. the value for n); it is set by default to 2 and I have found it a good compromise so far, but you're welcome to experiment with different values.

[fthevenet]

Using n-grams indexing in binjr is not necessarily a silver bullet, however, and it comes with a few trade-offs.
First of all in terms of impact over the generation of the index itself; I have conducted some preliminary benchmarks using a large-ish log file (586 MiB for ~4 Millions lines) and below are the results comparing the indexing speed (with and without an active Anti-virus on Windows) and index size for word-indexing (binjr's default) and bigrams indexing (n=2) and trigrams (n=3):

Corpus:

• Single file
• 586 MiB
• 3,991,795 lines
• 3,991,789 parsed events

	Words	bigrams	trigrams
Indexing time A/V off (1)	45,334 ms	41,288 ms	44,934 ms
Indexing time A/V off (3)	37,926 ms	34,934 ms	36,856 ms
Indexing time A/V off (3)	35,048 ms	36,487 ms	39,327 ms
Indexing time A/V off (avg)	35,048 ms	37,569 ms	40,372 ms
Indexing time A/V on (1)	44,213 ms	50,676 ms	66,680 ms
Indexing time A/V on (2)	39,209 ms	44,254 ms	48,664 ms
Indexing time A/V on (3)	40,168 ms	45,160 ms	48,678 ms
Indexing time A/V on (avg)	41,196 ms	46,696 ms	54,674 ms

	Words	bigrams	trigrams
ndex size	251 Mib	1,015 MiB	989 Mib

While indexing times are largely similar without the anti-virus (and slightly longer for n-grams with the A/V on) the impact on the index size is very significant: ~4x bigger when indexing with n-grams vs indexing words (notably, index size is half the size of raw text input in word mode, while it is twice as large in ngrams mode).
These results can be explained by two factors, the first one being that as part of ngram tokenization we keep all non-letters and number characters while we prune those during standard tokenization.
The second one is that by increasing the numbers of tokens for a given corpus, we end up paying for the cumulated overheads for those.

All in all this is not a show stopper but definitely something users need to be aware of when using binjr on large log files, as they are more likely to run of temp space using ngrams.

[fthevenet]

Hello!

Has anyone had the chance to try the new indexing mode?
Lucene 9.6 (which contain the fix that will make this feature viable) is poised to be released in the next couple of weeks, meaning that in turn, a release of binjr 3.12.0 will be possible.
I would really like to to get broader feedback on that feature before then.

Thanks!

[Arkanosis]

Hopefully, I'll have some time to try this week-end. I'm lucky enough to have a painful GPU driver / kernel issue to investigate for the occasion 😀

[fthevenet]

Lucky indeed! 🤣
Thanks!

[Arkanosis]

Let's start with the easy part, numbers:

Computer:

• Intel Core i5-6500
• 32 GiB RAM
• Linux 6.0.11

Corpus:

• Single file on a RAMdisk (journalctl --output=short-iso-precise with custom parsing rules)
• 363 MiB
• 2,357,123 lines
• 3,354,741 parsed events

	Words	bigrams	trigrams
Indexing time (1)	20,300 ms	28,457 ms	31,969 ms
Indexing time (3)	18,473 ms	27,927 ms	31,831ms
Indexing time (3)	18,452 ms	27,557 ms	31,100 ms
Indexing time (avg)	19,075 ms	27,980 ms	31,633 ms

	Words	bigrams	trigrams
Index size	195 Mib	617 MiB	592 Mib

That's pretty consistent with your results, and definitely a price I'm willing to pay for the additional capabilities.

Now, let's move to the hard part, UX :)

Before anything else, I have to say that once enabled, it's a real pleasure to use! Well done! Also, even though I haven't found the root cause for my driver issue yet (definitely not binjr's fault!), the n-gram mode has been superior to the word mode to sift the highly inconsistent output of journalctl.

I have a few questions / ideas:

• Would there be some benefits to let the user enable n-grams right in the path / file extension / parsing profile selection dialog? I feel like I might want to change the mode rather than set it once and forget it (see below for a more difficult change that would make this mostly irrelevant).
• In some cases, search doesn't seem to work for some reason when I use wildcards and n-grams together. For example, if I search for “ACP*“ it doesn't find “ACPI” with 2-grams, but it does with 3-grams. I initially thought it was because the literal was longer than the n-gram, but I've no problem finding “SMBIOS” with “SMBI*” with 3-grams, so… I'm confused :) Could it be the bug in Lucene you were writing about? In all fairness, the usefulness of widcards with n-grams as they are used is pretty low.

I certainly see possible improvements for a future version, but a release as-is would already be the best release ever™! :)

Possible improvements:

• Regular expressions (obviously :p) — especially “\b” and “\s”.
• Maybe difficult, but do you think the user experience could be unified between words and n-grams indexing? For example by reproducing the behavior of words with n-grams by default (eg. by adding implicits “\b”) and only unlocking the full potential of n-grams with explicit widcards (prefix, suffix…). This means that world would match hello world but not hello worlds; "hello w" wouldn't either, but "hello w*" would. This would make the choice between words and n-grams a matter of indexing time / index size only, and I'd see myself more likely to stick with n-grams always enabled than enabling / disabling them on a case-by-case basis.

[fthevenet]

Thanks for taking the time to try it out! 🙏

In some cases, search doesn't seem to work for some reason when I use wildcards and n-grams together. [...] Could it be the bug in Lucene you were writing about?

I'll start with that one as it is the most concerning to me. First thing to do is to make sure that you were using the 9.6-SNAPSHOT build for Lucene, as this is the one that supposedly fixes the bug. If you're using one of the pre-built package available here: https://github.com/binjr/binjr/releases/tag/v3.12.0-SNAPSHOT, that should be the case. If you built it yourself... it should also be the case, but you might want to double check there isn't a copy of a previous version accessible on the classpath.

Once you're confident you're using the right version, if the issue still happens it would be simpler if you can send me the elements for a reproducer. There's a pretty big chance the the problem lies in my own code, as I'm doing some custom query rewriting so that is is possible to generate the ngrams for the user submitted terms while still leveraging the standard query parser to support things like boolean operators.

And of course the probability that this is another, unrelated Lucene bug is non-zero 🤷

[Arkanosis]

Just to be extra sure: does your actual query contain the double quotes or not?

No, just ACP or ACP*.

[fthevenet]

OK, so that was indeed a stupid bug in my query rewriting code (and not something buried deep in the abyss of Lucene's codebase, so that's a relief 😅 ).
That should be fixed soon.

[fthevenet]

And thanks for spotting it!

[Arkanosis]

Awesome, thanks! :-)

[fthevenet]

As a matter of fact, wildcards are not only kinda useless in that context, they actually are downright problematic...

In a nutshell, to make the search accurate with ngram tokens, it is important that all tokens are passed within a "phrase query", i.e. delimited by ", to ensure that the position of said token are taken into account.
For instance, to match exclusively foobar you need the query "fo oo ob ba ar" and not fo AND oo AND ob AND ba AND ar, as this also match oofobar for instance (NB: the implicit boolean operator is "OR", so fo oo ob ba ar matches anything with just one of the token, so that's even less accurate).

This works great, but Lucene's query parser does not support wildcard in phrases, only within single terms, so that means It is up to us to implement that behaviour, and what I attempted in the buggy code that you spot an issue with.

For the simplest case where wc are used to search for a prefix (e.g. foo* or foo?), the solution is trivial enough; simply get rid on the wildcard and do the search as is. That also works for prefix search, although those are not allowed by default by Lucene's parser.
As simple as it is, this also have strictly no values over omitting the wildcard, though: it only helps by providing a compatible syntax.

That leaves us with the more useful cases of fo*ar and foo?ar, which indeed would offer a benefit. The problem is that I cannot really think of a good and efficient implementation for it...
The best I could come up with was to turn foo*bar into "fo oo" AND "ba ar", which does match "foobar" or "foo baz bar" but also "bar foo" and all sort of things like that, which is not what is expected. Re-implementing the behaviour of the ? wildcard is even more difficult, of course.

I haven't found a way to build composite queries that respects the notion of positions of terms in Lucene (other than the aforementioned phrase queries) and failing that I don't think we can come up with a satisfactory implementation for wildcards.

I'll keep looking for a bit, but maybe the best thing to do is just advertised wildcards are just not supported in this mode.

[fthevenet]

Would there be some benefits to let the user enable n-grams right in the path / file extension / parsing profile selection dialog? I feel like I might want to change the mode rather than set it once and forget it

Right now, it isn't possible to implement in binjr, as the type of tokenizer is set once and for all when the IndexWriter instance is built, and it is assumed that an index is only built and updated by a single IndexWriter. That is not to say it would be impossible to ever implement it, but that is certainly more work than it looks.

[Arkanosis]

That makes sense. Let's wait and see if people like me actually switch between modes all the time or completely forget about one of them :)

[fthevenet]

Possible improvements:
- Regular expressions (obviously :p) — especially “\b” and “\s”.
- Maybe difficult, but do you think the user experience could be unified between words and n-grams indexing? For example by reproducing the behavior of words with n-grams by default (eg. by adding implicits “\b”) and only unlocking the full potential of n-grams with explicit widcards (prefix, suffix…). This means that world would match hello world but not hello worlds; "hello w" wouldn't either, but "hello w" would. This would make the choice between words and n-grams a matter of indexing time / index size only, and I'd see myself more likely to stick with n-grams always enabled than enabling / disabling them on a case-by-case basis.*

Well, you can't implement regular expressions on top of a field whose content has been split into n-grams, or at least I don't see how. What can be done is to also index each line in a separate field without any tokenization of any sorted, and apply regexs on that: I've done that in a POC and that works. The drawback is that this would further incread the index size (by about the raw text size mitigated by compression used) and it is unclear how well that would scale a across large-ish index. At any rate, this would not used the ngram field at all.

With regard to your second point, what I gather is that you really want, is to be able to make a query with the term foo that surfaces baz foo bar but not bas foobar, is that correct? In other words, regain the ability to have an exact match for a term.

The bad news is that you cannot do that with n-grams (unless there's something that eludes me). The good news is, however, that you could search for foo (with a trailing space) instead of foo to achieve that. Right now, I keep all white space when building the ngrams so that means the index itself should be capable of serving such query.
However as mentioned before, I used the standard query parser (so that it handles the rest of the query language) and this will eat away all trailing spaces in terms not enclosed in double quotes, but at the moment my rewriting query logic does some possibly questionable things to Phrase queries (terms in double quotes) that would prevent it.

I'm really not sure about that said logic though and I've considered changing it before; it might be time to do so!

[fthevenet]

OK, so I've change the query re-rewriting so that it preserves anything that's enclosed in double quotes (including spaces), and turns that into a into sequence of bi or trigrams to search for, retaining the order.

What that means is that given the following corpus:

1: foo bar baz
2: bar foo baz
3: foobar baz
4: foobarbaz
5: baz bar foo
6: foo baz

• foo and "foo" matches everything
• "foo " matches 1, 2 and 6
• " foo " matches 2
• foobar matches 3 and 4
• foo bar and bar foo matches 1, 2, 3, 4, 5
• "foo bar" matches 1
• "foo ba" matches 1, 2, 6
• "bar foo" matches 2 and 5
• foo baz bar matches everything
• "foo baz bar" matches nothing
• foo AND baz AND bar matches 1, 2, 3, 4, 5

[fthevenet]

Note that * or ? won't be treated as wildcards when found in terms enclosed in double quotes (i.e. in the example above, "foo*" won't match anything. But foo* will be like foo).

[fthevenet]

All in all, I'm pretty tempted to make this new mode the default, especially with the latest change in behaviour for quoted terms.

Also, I'm considering removing the ngram size option from the settings panel: I don't see much point in using anything other than bi-gram, as the increase in index size is minimal and it allows for a smaller minimum term size.
Having this option in the UI is only likely to confuse people. It will still be accessible as a property from the debug console, just in case.

It might have an impact at search time as it increases the number of terms produced in the end query for larger user-supplied words, but I'm doubtful this would ever really be noticeable (I haven't noticed it, at least), given the fact that even very large logs files only make for rather small search corpora, and we're only ever serve a single user at a time.

WDYT?

[fthevenet]

(also, I think we should rename the "Index using N-grams [yes | no]" option to "Optimize search for [partial terms | whole words]" or something like that, so that it might be understandable to more people than just search engine and NLP nerds 🤓)

[fthevenet]

Yeah, I think it makes a lot more sense like that:

[fthevenet]

The n-gram size parameter is still accessible via the debug console, btw