Confirm
574
edits
Changes
Created page with "trilite, the trigram index which powers DXR searches, is extremely powerful and was ahead of its time, but I wouldn't mind getting off it, now that the rest of the world h..."
trilite, the trigram index which powers [[DXR]] searches, is extremely powerful and was ahead of its time, but I wouldn't mind getting off it, now that the rest of the world has started to catch up. Motivations:
* We have to maintain it.
* It's bound to SQLite, which imposes scalability challenges. It requires the webhead to be the one to execute the expensive queries. It can't parallelize beyond a single machine (or processor?).
* Contributors have trouble building it and messing with <code>LD_LIBRARY_PATH</code>.
Here are some alternatives. Let's go shopping.
__TOC__
== Elasticsearch ==
Pros:
* Parallelization of even single queries
* Redundancy
* Already-implemented update and delete support (which trilite is missing and which we'd need for incremental indexing)
* Caching of intermediate filter results. (It will transparently store the set of, say, all *.cpp files as a bitmap for quick set operations later. This means that common compound queries will likely be much faster than in any RDBMS.)
* Suggesters for "did you mean" and autocomplete
* Sparse attribute storage, which could come in handy for supporting new languages
* Scoring
=== Challenge: Fast Regex Matching ===
ES lacks out-of-the-box support for trigram-accelerated regex searches. It does offer [https://lucene.apache.org/core/4_3_0/core/index.html?org%2Fapache%2Flucene%2Futil%2Fautomaton%2FRegExp.html some regexp query support] which uses term indices and [https://lucene.apache.org/core/4_3_0/core/index.html?org%2Fapache%2Flucene%2Futil%2Fautomaton%2FRegExp.html some clever enumeration] to deliver non-naive performance, but I wonder if it would be enough. I don't see how you can use a term index to accelerate a regex that may span terms. I suppose you could index each line as a single term and then start every non-anchored regex search with <code>.*</code>, but that seems like a great way to have an enormous number of unique terms and be super slow.
Here's how we could get ES up to trilite speeds without too much trouble. If we're willing to extract trigrams ourselves, we can easily tell ES to filter down to the docs containing those, then run a regex prosaically across them. And it just so happens that Python's stdlib regex machinery is written in Python. (I couldn't believe it either.) Take a look at sre_compile.py and sre_parse.py. They literally build a Python list of instructions, like <code>['charset', 'groupref_ignore', ...]</code>, and then pass that to <code>_sre.compile()</code>, which is the only C speedup I see. Presumably, that returns a fast matcher of some kind, with guts in machine language. So, we harness that existing regex parser, extract trigrams, and go to town. This actually gives us flexibility beyond what trilite provides, in that we have the option of running non-accelerated regex queries, foolish though that may be. And we have full control over the complexity of regexes that we allow, since that isn't buried in <code>re2</code> any longer. At any rate, it's something to consider.
== PostgreSQL ==
Postgres is the other contender. As of 9.3 it supports trigram-accelerated regex searches, but, sadly, they hard-coded a limitation to word-like chars. We'd probably have to hack the source to circumvent that.
Pros:
* An easy port from our existing relational-based storage
* Update and delete support
* We have to maintain it.
* It's bound to SQLite, which imposes scalability challenges. It requires the webhead to be the one to execute the expensive queries. It can't parallelize beyond a single machine (or processor?).
* Contributors have trouble building it and messing with <code>LD_LIBRARY_PATH</code>.
Here are some alternatives. Let's go shopping.
__TOC__
== Elasticsearch ==
Pros:
* Parallelization of even single queries
* Redundancy
* Already-implemented update and delete support (which trilite is missing and which we'd need for incremental indexing)
* Caching of intermediate filter results. (It will transparently store the set of, say, all *.cpp files as a bitmap for quick set operations later. This means that common compound queries will likely be much faster than in any RDBMS.)
* Suggesters for "did you mean" and autocomplete
* Sparse attribute storage, which could come in handy for supporting new languages
* Scoring
=== Challenge: Fast Regex Matching ===
ES lacks out-of-the-box support for trigram-accelerated regex searches. It does offer [https://lucene.apache.org/core/4_3_0/core/index.html?org%2Fapache%2Flucene%2Futil%2Fautomaton%2FRegExp.html some regexp query support] which uses term indices and [https://lucene.apache.org/core/4_3_0/core/index.html?org%2Fapache%2Flucene%2Futil%2Fautomaton%2FRegExp.html some clever enumeration] to deliver non-naive performance, but I wonder if it would be enough. I don't see how you can use a term index to accelerate a regex that may span terms. I suppose you could index each line as a single term and then start every non-anchored regex search with <code>.*</code>, but that seems like a great way to have an enormous number of unique terms and be super slow.
Here's how we could get ES up to trilite speeds without too much trouble. If we're willing to extract trigrams ourselves, we can easily tell ES to filter down to the docs containing those, then run a regex prosaically across them. And it just so happens that Python's stdlib regex machinery is written in Python. (I couldn't believe it either.) Take a look at sre_compile.py and sre_parse.py. They literally build a Python list of instructions, like <code>['charset', 'groupref_ignore', ...]</code>, and then pass that to <code>_sre.compile()</code>, which is the only C speedup I see. Presumably, that returns a fast matcher of some kind, with guts in machine language. So, we harness that existing regex parser, extract trigrams, and go to town. This actually gives us flexibility beyond what trilite provides, in that we have the option of running non-accelerated regex queries, foolish though that may be. And we have full control over the complexity of regexes that we allow, since that isn't buried in <code>re2</code> any longer. At any rate, it's something to consider.
== PostgreSQL ==
Postgres is the other contender. As of 9.3 it supports trigram-accelerated regex searches, but, sadly, they hard-coded a limitation to word-like chars. We'd probably have to hack the source to circumvent that.
Pros:
* An easy port from our existing relational-based storage
* Update and delete support
