7 ms·

Author of the referenced blog (and library) here. This is great! The full text search engine in SQLite is sadly not really good for this - one reason is that i

Author of the referenced blog (and library) here. This is great! The full text search engine in SQLite is sadly not really good for this - one reason is that it uses standard B-Trees, another is that it forces storing all token positions if you want BM25 sorting, which is a huge overhead for articles as long as Wikipedia's. But that doesn't mean full text search isn't possible in a very efficient manner with statically hosted data! I wrote a proof of concept of making the Rust-based tantivy library work in the same way, which has a lot of internal things that can make the index much smaller and more efficient than SQLite's. It's also >10x faster in creating the search index. Here's the demo also for Wikipedia: https://demo.phiresky.xyz/tmp-ytccrzsovkcjoylr/dist/index.html https://demo.phiresky.xyz/tmp-ytccrzsovkcjoylr/dist/index.ht... I'm not sure if it's more efficient than the SQlite version in this form, but it definitely has more upward potential and is more fun to work with. And the corresponding draft PR: https://github.com/tantivy-search/tantivy/pull/1067 https://github.com/tantivy-search/tantivy/pull/1067 I sadly haven't gotten around to working on it more and writing an article about it. Other people are also working on using this stuff to make Sci-hub and LibGen more available by using this in combination with IPFS for distributed and "uncensorable" hosting which is pretty awesome. Edit: Just realized that the OP demo only searches in article titles, while mine searches in full article contents by default. You can search in only the titles in my demo by querying `title:harry title:potter`

segfall 5y ago
Thank you, Phiresky. My little side project only exists because of your work.
- ignoramous 5y ago
  Congrats on your side project! This wonderful discussion exists because of your work.
tored 5y ago
I have been thinking of using FTS5 with SQLite to search emails. Not close of 43 GB ofc, so I would probably not have any major performance problems, but still is FTS5 any good? Or should I look into other solutions?
- OJFord 5y ago
  Have you seen 'notmuch'? I was honestly shocked how good/fast it is. It uses a C (++?) lib called 'xapian' to provide the actual index/search capability.
- psanford 5y ago
  The nice thing about FTS5 is you can have full text search up and running on a dataset in a couple of minutes. So give it try and see if it is sufficient for your use case. If it is, great! If not, you've not wasted much time.
- phiresky 5y ago
  If you're talking about a normal local SQlite DB and your dataset is less than maybe 100GB of plaintext then SQLite FTS will work fine regarding performance.
walrus01 5y ago
How does it do for performance if you throw the whole 43GB into RAM? Plenty of very affordable workstation systems out there today gently used with 128GB in them.
- londons_explore 5y ago
  You still have to download it all... Which is a barrier for most...
  - tjoff 5y ago
    For English it states 90 GB uncompressed, doesn't say compressed size but that doesn't sound much larger than a large game. In the context I don't see it as a barrier.
  - tw04 5y ago
    As someone who was very recently on about as bad of a dsl connection you could get... What? Outside of metered cellular connections this is available to basically everyone. Even the remotest parts of Africa have at least a handful of unmetered connections within a days drive and a USB drive.
  - unknownOrigin 5y ago
    That's only a size of regular modern video game... the downloads of which are pretty mainstream these days. Saying that a 50 gig download is a barrier "for most" is definitely not true.
  - exdsq 5y ago
    Gears of War 5 on the Xbox is 133GB with all its updates. I think we're at the point where 100GB is a high but reasonable request for people nowadays, at least in cities in the West.
- shp0ngle 5y ago
  what? the point of this is that it seeks just parts of the files through http ranges… not all 43 GB… just try the page? or am I missing something?
peterhunt 5y ago
You can also get efficient FTS with this method if you implement indexing in user space and avoid BM25. The Lucene practical scoring function works well with this method in my experience: https://www.elastic.co/guide/en/elasticsearch/guide/current/practical-scoring-function.html#coord https://www.elastic.co/guide/en/elasticsearch/guide/current/...
- piyh 5y ago
  Is there a dumbed down version of this indexing conversation for someone who understands b-trees, but BM25 or user space indexing?
  - peterhunt 5y ago
    Well, this post is in the context of an e2e encrypted DB, but it's subject to the same constraints: https://medium.com/@ZeroDB_/scalable-full-text-search-over-encrypted-data-cb2b5dd5bce2 https://medium.com/@ZeroDB_/scalable-full-text-search-over-e... If you understand btrees you understand the hardest part already :) Basically, you need to design a search index that examines the fewest DB pages in order to find the result. The Lucene scoring method stores a mapping of term -> document[] sorted in relevance order. The main idea is that you can examine only the first n documents for each term in the search query in order to find the most relevant search results. Picking n is sort of tricky, but if your index is stored in this way it's possible to fulfill a large % of queries efficiently without downloading the whole index. Here's a little Python implementation of what I mean by a "user space implementation". Note that it's a toy but it performs pretty well on some demo sklearn data sets: https://gist.github.com/petehunt/724eeb77189332db101ad7b0db8de3ef https://gist.github.com/petehunt/724eeb77189332db101ad7b0db8...
dheera 5y ago
Yeah I was just thinking that. Why not just a static filesystem? Just mount a ext4 image full of .html files and browse away. It would be remarkably efficient, likely much more efficient than SQLite.
neocodesoftware 5y ago
how are the xml dumps generated?

segfall 5y ago

Thank you, Phiresky. My little side project only exists because of your work.

ignoramous 5y ago
Congrats on your side project! This wonderful discussion exists because of your work.

tored 5y ago

I have been thinking of using FTS5 with SQLite to search emails. Not close of 43 GB ofc, so I would probably not have any major performance problems, but still is FTS5 any good? Or should I look into other solutions?

OJFord 5y ago
Have you seen 'notmuch'? I was honestly shocked how good/fast it is. It uses a C (++?) lib called 'xapian' to provide the actual index/search capability.
psanford 5y ago
The nice thing about FTS5 is you can have full text search up and running on a dataset in a couple of minutes. So give it try and see if it is sufficient for your use case. If it is, great! If not, you've not wasted much time.
phiresky 5y ago
If you're talking about a normal local SQlite DB and your dataset is less than maybe 100GB of plaintext then SQLite FTS will work fine regarding performance.

walrus01 5y ago

How does it do for performance if you throw the whole 43GB into RAM? Plenty of very affordable workstation systems out there today gently used with 128GB in them.

londons_explore 5y ago
You still have to download it all... Which is a barrier for most...
- tjoff 5y ago
  For English it states 90 GB uncompressed, doesn't say compressed size but that doesn't sound much larger than a large game. In the context I don't see it as a barrier.
- tw04 5y ago
  As someone who was very recently on about as bad of a dsl connection you could get... What? Outside of metered cellular connections this is available to basically everyone. Even the remotest parts of Africa have at least a handful of unmetered connections within a days drive and a USB drive.
- unknownOrigin 5y ago
  That's only a size of regular modern video game... the downloads of which are pretty mainstream these days. Saying that a 50 gig download is a barrier "for most" is definitely not true.
- exdsq 5y ago
  Gears of War 5 on the Xbox is 133GB with all its updates. I think we're at the point where 100GB is a high but reasonable request for people nowadays, at least in cities in the West.
shp0ngle 5y ago
what? the point of this is that it seeks just parts of the files through http ranges… not all 43 GB… just try the page? or am I missing something?

peterhunt 5y ago

You can also get efficient FTS with this method if you implement indexing in user space and avoid BM25. The Lucene practical scoring function works well with this method in my experience: https://www.elastic.co/guide/en/elasticsearch/guide/current/practical-scoring-function.html#coord https://www.elastic.co/guide/en/elasticsearch/guide/current/...

piyh 5y ago
Is there a dumbed down version of this indexing conversation for someone who understands b-trees, but BM25 or user space indexing?
- peterhunt 5y ago
  Well, this post is in the context of an e2e encrypted DB, but it's subject to the same constraints: https://medium.com/@ZeroDB_/scalable-full-text-search-over-encrypted-data-cb2b5dd5bce2 https://medium.com/@ZeroDB_/scalable-full-text-search-over-e... If you understand btrees you understand the hardest part already :) Basically, you need to design a search index that examines the fewest DB pages in order to find the result. The Lucene scoring method stores a mapping of term -> document[] sorted in relevance order. The main idea is that you can examine only the first n documents for each term in the search query in order to find the most relevant search results. Picking n is sort of tricky, but if your index is stored in this way it's possible to fulfill a large % of queries efficiently without downloading the whole index. Here's a little Python implementation of what I mean by a "user space implementation". Note that it's a toy but it performs pretty well on some demo sklearn data sets: https://gist.github.com/petehunt/724eeb77189332db101ad7b0db8de3ef https://gist.github.com/petehunt/724eeb77189332db101ad7b0db8...

dheera 5y ago

Yeah I was just thinking that. Why not just a static filesystem? Just mount a ext4 image full of .html files and browse away. It would be remarkably efficient, likely much more efficient than SQLite.

neocodesoftware 5y ago

how are the xml dumps generated?