4 ms·

Writing a document database from scratch in Go: Lucene-like filters and indexes

168 points by eatonphil 5y ago

jll29 5y ago
This implementation uses set semantics with "and" as the only Boolean operator (Boolean retrieval model) - the dominant paradigm of the 1960s library catalog search systems. The Lucene library and engines on top (Elastic, Solr) use ranked retrieval, so resuls are scored and returned in order from most to least relevant. For example, the Vector Space Model (VSM) computes the cosine of the vector that represents the query (vector of all query term frequencies, other components 0) with the document vectors (vector of all document term frequencies, other components 0), and there are other models such as the Probabilistic Model (also known as BM25 or Okapi, after the version of the ranking formula used or the name of the software system implementing it, respectively) or DfR (Divergence from Randomness), another Information Retrieval (IR) model type. Since 1972 terms are weighted with the popular TDIDF weighting scheme (Term Frequency times Inverse Document collection Frequency, Spärck Jones (1972) J. Doc.) and often apply length normalization. I'd argue that these are important ingredients in a minimal implementation (and actually the first Lucene version had them). Without ranked retrieval there is no guarantee that the most relevant result in a list of 10,000 documents is not returned last.
- eatonphil 5y ago
  Good catch! But I don't think it matters because I didn't implement full text search so there is no question that all documents returned are equally relevant.
samber 5y ago
I wonder what is the motivation? Did you identify a limit to ES ? Did you need a simple query builder for advanced cockroachdb search queries? Whatever your initial needs (production or experimentations), please add a short explanation in the article! ;)
- eatonphil 5y ago
  I've implemented a SQL database from scratch before (that one was only in-memory) so I wanted to try my hand at a document database and this time have it support real storage. In general, posts on my personal blog are purely for fun and education. :)
kreeben 5y ago
Go folk might get a kick out of this but >> I said this project is "from scratch" but I'm going to bring in a storage engine Oh, so... not from scratch, then?
- metadat 5y ago
  That's kind of a nasty bait and switch, definitely not from scratch if you pick the indexer core up from GitHub on the way home after work. Phil, I'm a bit disappointed in you. This hasn't been the sort of thing I've observed from your (excellent) prior writings.
  - eatonphil 5y ago
    You people are harsh! :) I'll put it this way: I only write about stuff that I think is interesting. And I don't believe my title is clickbait. If you read the article and still think it's not interesting or not my normal level of educational, well then I'll be surprised.
    - bogomipz 5y ago
      I thoroughly enjoyed this post! I also didn't perceive the title as any kind of attempt at "clickbait." Thanks for sharing. I would like interested in seeing more installments of developing this Elasticsearch style API too :)
    - metadat 5y ago
      It is interesting. If the indexer is being imported, it's also not "from scratch", at all. The two are not mutually exclusive. Your piece will stand on it's own, perhaps call it something like: Implementing The Elasticsearch Backend Myself in Go Phil, your editorial honesty, integrity, and accuracy will be appreciated by me and others. <3
  - kungfufrog 5y ago
    Did you read the article? He addresses your point directly. Your criticism sounds a little petty, but, perhaps you're being flippant and it's lost on me..
AtlasBarfed 5y ago
What are you using to scale the document storage across nodes? Is it the usual master-slave stuff?
- eatonphil 5y ago
  Just an educational proof-of-concept. Scaling not being part of that concept.
  - AtlasBarfed 5y ago
    In my off time I was writing a document layer atop cassandra. Then if you add a basic relation capability between documents, then all of a sudden a document database becomes a poor man's property-graph database. It also was just a bit of an side project without any real production use.

168 points by eatonphil 5y ago

This implementation uses set semantics with "and" as the only Boolean operator (Boolean retrieval model) - the dominant paradigm of the 1960s library catalog search systems. The Lucene library and engines on top (Elastic, Solr) use ranked retrieval, so resuls are scored and returned in order from most to least relevant. For example, the Vector Space Model (VSM) computes the cosine of the vector that represents the query (vector of all query term frequencies, other components 0) with the document vectors (vector of all document term frequencies, other components 0), and there are other models such as the Probabilistic Model (also known as BM25 or Okapi, after the version of the ranking formula used or the name of the software system implementing it, respectively) or DfR (Divergence from Randomness), another Information Retrieval (IR) model type. Since 1972 terms are weighted with the popular TDIDF weighting scheme (Term Frequency times Inverse Document collection Frequency, Spärck Jones (1972) J. Doc.) and often apply length normalization. I'd argue that these are important ingredients in a minimal implementation (and actually the first Lucene version had them). Without ranked retrieval there is no guarantee that the most relevant result in a list of 10,000 documents is not returned last.

eatonphil 5y ago
Good catch! But I don't think it matters because I didn't implement full text search so there is no question that all documents returned are equally relevant.

samber 5y ago

I wonder what is the motivation? Did you identify a limit to ES ? Did you need a simple query builder for advanced cockroachdb search queries? Whatever your initial needs (production or experimentations), please add a short explanation in the article! ;)

eatonphil 5y ago
I've implemented a SQL database from scratch before (that one was only in-memory) so I wanted to try my hand at a document database and this time have it support real storage. In general, posts on my personal blog are purely for fun and education. :)

kreeben 5y ago

Go folk might get a kick out of this but >> I said this project is "from scratch" but I'm going to bring in a storage engine Oh, so... not from scratch, then?

metadat 5y ago
That's kind of a nasty bait and switch, definitely not from scratch if you pick the indexer core up from GitHub on the way home after work. Phil, I'm a bit disappointed in you. This hasn't been the sort of thing I've observed from your (excellent) prior writings.
- eatonphil 5y ago
  You people are harsh! :) I'll put it this way: I only write about stuff that I think is interesting. And I don't believe my title is clickbait. If you read the article and still think it's not interesting or not my normal level of educational, well then I'll be surprised.
  - bogomipz 5y ago
    I thoroughly enjoyed this post! I also didn't perceive the title as any kind of attempt at "clickbait." Thanks for sharing. I would like interested in seeing more installments of developing this Elasticsearch style API too :)
  - metadat 5y ago
    It is interesting. If the indexer is being imported, it's also not "from scratch", at all. The two are not mutually exclusive. Your piece will stand on it's own, perhaps call it something like: Implementing The Elasticsearch Backend Myself in Go Phil, your editorial honesty, integrity, and accuracy will be appreciated by me and others. <3
- kungfufrog 5y ago
  Did you read the article? He addresses your point directly. Your criticism sounds a little petty, but, perhaps you're being flippant and it's lost on me..

AtlasBarfed 5y ago

What are you using to scale the document storage across nodes? Is it the usual master-slave stuff?

eatonphil 5y ago
Just an educational proof-of-concept. Scaling not being part of that concept.
- AtlasBarfed 5y ago
  In my off time I was writing a document layer atop cassandra. Then if you add a basic relation capability between documents, then all of a sudden a document database becomes a poor man's property-graph database. It also was just a bit of an side project without any real production use.