Caponia - an in memory, full text search system in clojure | Hacker News Reader

Caponia - an in memory, full text search system in clojure

github.com

25 pointsbrehaut11 comments

Why not just wrap Lucene? It's in Java, provenly awesome over the course of a decade and supports in-memory, file-backed, whatever. Probably a lot easier than writing your own tokenizers and indexing algorithms.

Fair question. I'm running couchdb for a new project, and Lucene is the 'blessed' search backend for that.

However, (at least via couchdb) Lucene needs a whole JVM of its own, and I'm planning to run this on a VPS with pretty tight resources. A couple of MB in the same JVM as my site is a whole lot more appealing, and has the additional advantage of using native data-structures directly.

Lucene's just a toolkit, it'll run in the same JVM that you're running clojure in, and while it can be memory-intensive if you're running a lot of searches over a big index, it's probably not any more memory intensive than what you're doing -- they've done a bunch of iterations already.

Maybe you were thinking of Solr? That's the REST service that wraps Lucene but you can use the Lucene API from within your app just as easily if that fits your use case.

couchdb-lucene, which is what I was looking at, does require its own JVM. I didn't think to look at using Lucene directly.

On the other hand, I'm quite happy with how this turned out, it's one less dependency, and it's been fun to write.

Yeah, kudos for writing it, it's always good to write something like that and learn. If you find further needs, I'd really recommend looking at the "thin wrapper around lucene" approach, they've been banging on this problem for a decade and have a lot of lessons learned in their codebase.

That would also be my recommendation. BTW, I just wrapped up Lucene, Sesame (RDF data store), and Java DB in one package (I wanted RDF+geolocation+search of text in RDF triples), and also put Clojure and Scala wrappers around my Java wrapper.

If you are using Clojure, Scala, JRuby, etc., might as well take advantage of great Java libraries.

I am impressed at how little source code is there.

Is that all that's needed to implement the full text search?

And it's fast?

I'm only using on a pretty small scale – around 500-600 blog posts. It takes about 10 seconds to build the index from scratch (including tokenising and stemming everything), and queries are effectively instantaneous.

So it basically isn't using B-trees or whatever fancy data structures Lucene and company would use?

The top level index is a clojure map (a persistent hash-map by default i believe) of strings (stems) to another map of key to weighting. The hash-map is implemented as a Bagwell Trie under the hood. Check out http://blog.higher-order.net/2009/09/08/understanding-clojur... for a lot of detail on the implementation, and http://en.wikipedia.org/wiki/Trie for a general overview of how Tries differ from Trees.

For some additional information about the performance of caponia, heres some details about the pain points:

The particular pathological case for this system is query where the search stems occur in the majority of documents (there is a small exclusion list that helps, but its not a panacea) because the merging of stem results is at best a linear operation (:or queries are currently much simpler than :and queries)

The other difficult case for this system is updating or removing a document from the index; removal is fairly easy: generate the stems for the current state and update those stems in the index.

To update (an existing document in the index) efficiently you need the set of stems in both old and new versions of the document; For the stems that are in new set you can just add them to the index as normal. For the difference of the old set and the new set (ie, those stems only in the old set - clojure's difference function is not symmetric i believe) you then need to remove the document id from those stems in the index.

edit: clarified meaning of update.

Reply on news.ycombinator.com