Writing a text indexer, tips?

<p>I&#39;m in need of writing a text indexer which operates similar to a basic SQL database. Ie, rows/objects of data, and the ability to perform basic queries against that data like <code>columnA==5 &amp;&amp; columnB == 6</code>. The rows will be schemaless as well.</p> <p>With that said, i&#39;ve never implemented this sort of project before, and am curious if anyone has any good writeups that might help me get started on this.</p> <p>Ignorantly if you were going to implement this you could iterate over a set of objects, such as might be stored in boltdb, and hit them one by one ignoring the ones that don&#39;t match and returning the ones that do match. However this seems naive at best haha.</p> <p>Anyway, i realize this is a very open ended question, quite in the nature of &#34;do my homework for me&#34;, but i don&#39;t mean it like that at all. Just looking for any pointers from anyone who has experience in dealing with fairly large datasets and query operations like this. A couple notes:</p> <ol> <li>I&#39;m not doing this because i want to, but because all other solutions i&#39;ve found are either not pure-Go, or are unable to index the type of data i have <em>(schema-less maps. Eg, Storm is out, but with some work i could use something like QL)</em>.</li> <li>I realize the performance of something ignorantly coded is not likely to be up to snuff. However if i can match through one or two million objects in a sane timeframe i&#39;ll consider that &#34;good enough&#34;. Beyond that i would need something non-Go, like SQLite or a proper DB.</li> </ol> <p>Thanks to any replies!</p> <hr/>**评论：**<br/><br/>lobster_johnson: <pre><p>Your question is odd, since the first and only example in your post is not about text, but some basic integer matching, and you don&#39;t even mention text (which is a separate can of worms to just matching by equality — tokenization, ranking, etc.) other than in your first sentence. Are you really indexing text?</p> <p>If so, have you looked at <a href="https://github.com/blevesearch/bleve" rel="nofollow">Bleve</a>? It&#39;s a text-indexing library.</p> <p>If your data doesn&#39;t need to be on disk, consider a column-store-type approach stored in RAM. The cache efficiency potentially allows you to race through huge amounts of data in a short time without having to use complicated indexes such as B-trees.</p></pre>PhoRaptor: <pre><blockquote> <p>Your question is odd, since the first and only example in your post is not about text, but some basic integer matching, and you don&#39;t even mention text (which is a separate can of worms to just matching by equality — tokenization, ranking, etc.) other than in your first sentence. Are you really indexing text?</p> </blockquote> <p>Apologies. I&#39;m &#34;indexing&#34; text, integers, bools, time, and possibly a couple other data formats i&#39;m not thinking of at the moment.</p> <p>Keep in mind i&#39;m not concerned about full text indexing, because i planned on using Bleve for that. However using Bleve alone doesn&#39;t quite have the set of SQL-like features. I&#39;ve actually already used Bleve in the past for this task, and wasn&#39;t able to implement the querying requirements i needed. Eg, iirc Bleve made some SQL-like queries difficult, but i can&#39;t remember which specific operator is missing offhand. With that said, i should probably whip up a quick implementation in Bleve as to know what is lacking. Perhaps i could augment Bleve more easily than writing my own.</p> <blockquote> <p>If your data doesn&#39;t need to be on disk, consider a column-store-type approach stored in RAM. The cache efficiency potentially allows you to race through huge amounts of data in a short time without having to use complicated indexes such as B-trees.</p> </blockquote> <p>I&#39;m likely going to leave the storage up to something else, ie BoltDB - So in-memory may or may not be on the table. Granted, i would like to plan for not in memory, since the indexed datasets might be a bit too large.</p> <p>Your BTree example is good though, that would have been a far better question to ask. Which Compsci data structures lend themselves to searching and filtering large datasets? Seems like that is really what i&#39;m asking.</p> <p>Appreciate your reply!</p></pre>lobster_johnson: <pre><p>All right, I think I have a better understanding now.</p> <p>Re BoltDB, keep in mind that it&#39;s just a key/value store. It&#39;s good for storing data, but not for querying on anything except for a value&#39;s key.</p> <p>It&#39;s hard to use a key/value store as a general-purpose index on collections of data. For example, let&#39;s say you wanted to index data on an integer column called <code>age</code>. You could use the key <code>age:&lt;value&gt;</code>. So for a record with <code>age=42</code>, you&#39;d store it as <code>age:42</code>. Each BoltDB value would be a list of record IDs that matched the value.</p> <p>But that presents several problems. One is that in order to update the index (add or remove records), you&#39;ll have to write the entire <code>age:42</code> key every time. If there are 1 million records with <code>age=42</code>, that&#39;s a huge value to write. Secondly, the lookup becomes extremely slow; there&#39;s no way to stream the lookup.</p> <p>You could partition it into buckets (e.g. <code>age:&lt;bucket-ID&gt;:42</code>, but then you need to keep track of the sizes of the buckets so you know where to insert. It&#39;s a can of worms, and probably not the path to good performance.</p> <p>A system like this would couple tightly to BoltDB&#39;s key lookup mechanism. The efficiency of this approach depends on your ability to map values to keys. Of course, for a long time Lucene did pretty well by indexing integers as strings.</p> <hr/> <p>A better way, in my opinion, would be to use BoltDB as a transactional page management system, and implement your own indexing on top of this. This is roughly how modern databases work. </p> <p>In this system, your data structures would be serialized to disk in the form of &#34;pages&#34;. A single page contains index nodes in some efficient structure, limited by size (e.g. 4K). When saved to BoltDB, they&#39;d be serialized in a compact binary format, and deserialized when read back. (The size limit should be set according to how expensive it is to modify just one entry in the page, which is the worst case. You don&#39;t it to be large.)</p> <p>If you give each page an ID, the index nodes can then refer to each other by page ID.</p> <p>You can implement a B-tree structure — or any other indexing data structure — on top of a page system like this. The stupidest algorithm you can do is probably a plain, unbalanced binary tree, for example. Each node has a left/right pointer, which is a <code>[page_id, node_index]</code> tuple. Leaf nodes then have values. Binary trees will eventually get too unbalanced, and aren&#39;t efficiently packed. B-trees are pretty much ideal for page-oriented systems because they can pack many leaf nodes together in a single node.</p> <p>The benefit of using BoltDB here, and not inventing your own disk storage, is that you get transactions for free. Last I checked, BoltDB implemented an MVCC-type transactional system, which means it&#39;s got great concurrency and is crash-proof.</p> <hr/> <p>But the reason I mentioned indexing in RAM is that if you use a columnar approach, you can zip through the columns extremely fast — RAM is so fast that you don&#39;t necessarily even need &#34;fancy&#34; structures like B-trees, which are complex to implement, especially if you can parallelize queires.</p> <p>You can even <code>mmap</code> the index as a disk file. This is how kdb, which is one of the world&#39;s fastest column databases, works. I believe BoltDB also uses <code>mmap</code> on Unix to put its data files into RAM.</p> <p>The downside, of course, is that if you don&#39;t do something mmap, you need to reindex every time your program starts. There are some projects that do this, and rely on clustering (redundant nodes) to reduce the chance of a restart incurring any downtime.</p> <p>(But if you do choose to use disk, don&#39;t invent your own storage mechanism.)</p> <hr/> <p>Lastly: This is a big topic, and I only lightly brushed the surface of it in the above.</p> <p>I recommend getting some proper books on this, because there are so many solved problems that have clever solutions that you don&#39;t want to reinvent, poorly. I&#39;ll see if I can come up with titles for you. I remember <a href="https://www.amazon.com/exec/obidos/ISBN=0321197844/portlandpatternrA/" rel="nofollow">An Introduction to Database Systems</a> as being decent, but it doesn&#39;t go into much detail about the physical storage of databases. There&#39;s a lot of information online, too, of course; but some older works, still in paper book form, are a lot better.</p> <p>You&#39;ll also something that goes into relational algebra. Modern systems use relational algebra to split query execution into several phases, creating a logical execution plan that can be optimized into a physical plan. For example, imagine someone queries on <code>age &gt; 42 and name = &#34;bob&#34;</code>. If there&#39;s only one person named &#34;bob&#34; which can be found using a single index lookup, it would be a bad idea to also run <code>age &gt; 42</code>, because all other predicates can be executed directly on the fetched row.</p></pre>xiegeo: <pre><p>You can use SQLite in Go too. Such as <a href="https://github.com/mattn/go-sqlite3" rel="nofollow">https://github.com/mattn/go-sqlite3</a></p></pre>PhoRaptor: <pre><p>In Go yes, but not as pure Go unfortunately. Eg, cross compiling is troublesome, unfortunately. Oddly enough, there is a pure Go SQLite in the works. :)</p></pre>xiegeo: <pre><p>Only if easy cross compiling is that important to you. There has been a pure Go version in the works for years, so I wouldn&#39;t wait for that.</p> <p>I had too looked for pure Go solutions in the beginning, but i don&#39;t think there is enough benefit for anyone to rewrite SQLite in Go, and make it production quality. Personally I don&#39;t find cross compiling critical, if I need to support a platform, then I need have access to an instance of that platform for debugging anyway.</p></pre>