Text and Other Large Indexes

A text index can speed up document text searching by many orders of magnitude, and InfinityDB can do it well. InfinityDB has a built-in general-purpose index called ‘IncrementalMergingItemSpace’ that can be used for text and many similar large-index applications, but often a custom index is built on top of the basic ItemSpace data model by application code. It is not strictly necessary to have a special text index data structure at all, so application code can simply store one word per Item, as shown in the ‘WordSorter.java’ example code, with extremely high performance. However, for indexes that do not fit in the memory cache, a special word index can greatly speed word addition and overall index construction, as shown in the ‘FileIndexer.java’ example code.

The 4.0 Map-based Access can be Used

This code all uses the basic low-level ‘ItemSpace’ data model, but it is completely compatible with the new version 4 standard extended ConcurrentNavigableMap access technique. For Map-based access, one can simply create one of these indexes and then wrap it with an InfinityDBMap: such wrapping is shown in MapHelloWorld.java. All uses of InfinityDB can use either technique.

The Principle is Like On-Disk Merge Sorting

The principles of text indexing are closely related to on-disk merge sorting. A merge sort takes a batch of input data to sort and outputs the result on one operation. A text index uses the same structure but also allows the on-disk data to be searchable even while the sorting is in an intermediate state. Thus words may be added quickly and the effects can be seen immediately. In fact, all kinds of indexes can be built,  maintained, and accessed this way, but it is slower to retrieve or delete data from such an index while it is in the intermediate state. The intermediate state may be long-lived if necessary or by design.

Basic Layered Structure

The basic structure of text indexes is usually the same: there is an expandable array of one to perhaps five ‘layers’, each layer being a set of zero to say about 10 ‘segment files’, each segment containing a sorted set of words and their associated data. The segments at each layer are about 10 times larger than those at the layer below, the number of layers increases logarithmically base 10, and the number of segment files at each level varies from 0 to 10 as words are added. There is a sorted memory buffer for the most recently added words. To add to the index, the new word and its associated data is added to the buffer, and if the buffer fills, it is written to disk as a new segment file at layer 0 (the ‘lowest’ layer). After writing a buffer, the invariant of the index is re-established, so if layer 0 has 11 segments, then those segments are merged – which is fast because they are sorted – and the result is written as a new segment at layer 1. Then all the segment files at layer 0 are removed. This of course is recursive.

The two InfinityDB Sort Engines – the MergeSorterItemOutput Subclasses

This basic layered structure is used for many kinds of on-disk batch sorting, not just for word indexes. In other DBMS, B-Tree or other indexes are built quickly by sorting the values before index construction this way. For simple sorting, the segments do not need to be searchable. InfinityDB provides two such complete sort engines based on a ‘MergeSorterItemOutput’ which allow Items to be written out and read-back in sorted. The API for these sorters is extremely simple. Performance and scalability are very good. One uses external files for speed, and the other operates inside the single InfinityDB file. See the ‘InfinityDBSortingBulkLoadTest.java’ example code. They are single-threaded. If desired, a text index can be created in a batch using one of these, by sorting all of the words and then sequentially inserting them into the InfinityDB in ‘plain’ form, i.e. without any final layered structure. The final insertion is fast because the blocks being inserted into are in the cache, and disk writes may be all at the file’s end. This results in an extremely fast word index.

The InfinityDB Text Indexes

The text indexes used with InfinityDB use segments that are also individually efficiently searchable at any size. InfinityDB segments are actually just separate portions of the single InfinityDB file each identified by a prefix, so there are no special outside directories or files. This is in contrast to most other text indexes. In order to look up a word, all of the segments are individually searched, and if any segment contains the word, its data is returned. If a word is added multiple times, there may be multiple matches. Any amount of data may be associated with a word. (A while ago, another text indexing system also used individually searchable segments, but they are external files, not B-Trees, and they have to use limited additional per-segment files to accelerate search somewhat for small segments by trading much memory for speed.)

Word Deletion

In text indexes other than in InfinityDB, words either cannot be removed, or they require setting a deleted bit, but continue to take space. Since each segment in the InfinityDB word indexes use the native underlying single B-Tree, deletion reclaims all freed space for the rest of the database to use. Deletion is performed by removing the word or selected associated data from all segments. This is much slower than insertion, possibly requiring random (logarithmic) access in each segment, but that is inherent in the layered structure. Any of the data associated with a word can be inserted, deleted, or updated later. That is not generally true in other word index implementations.

IncrementalMergingItemSpace is the Text Index

Now, we have to admit that InfinityDB actually provides no specific Text Index out of the box, but instead provides a more general-purpose index implementation that can be used in that capacity. The IncrementalMergingItemSpace acts exactly like an isolated InfinityDB database itself – it can insert, delete, update, and search using the same standard API that the rest of the database uses, except that modifications are synchronized and single-threaded. Searches are concurrent. This could hardly be more general. (All access can optionally restrict itself to the new version 4.0 Map-based model transparently of course without referring to the lower-level  ‘ItemSpace’ concept.) To use it as a text index, one simply stores Items in it that are each a word concatenated with any data. Multiple Items can be used per word, so the amount and structure of fully-modifiable data efficiently associated with each word is unlimited. Each entire index can be maintained under a given identifying prefix within the containing file, so there is no limit to the number of indexes sharing a file. Each index is in fact a fully-functional DBMS with different performance characteristics than the containing file.

The IncrementalMergingItemSpace is fast for inserting any amount of random input data, even when the stream of data exceeds the memory cache size. Slow disk seeks are dramatically reduced for inserts, but retrievals, deletions, and updates still require many seeks – which are about 6ms each. Each retrieval, deletion or update requires searching about five segments per layer, on average, and each segment requires searching the InfinityDB internal B-Tree, which takes a number of seeks logarithmic in the segment size. Note however, that sequential or localized retrievals are much more efficient, because the cache holds the most recently accessed blocks from all of the segments and there are few seeks. Sequential or localized retrievals are still not as fast as straight in-cache retrievals.

No Long Interruptions

IncrementalMergingItemSpace has an important advantage in that each insertion does some incremental work in merging the segments. This means that the flushing of the cache to a new layer-0 segment does not sometimes result in the recursive re-establishment of the index invariant, which occasionally takes an amount of time essentially proportional to the index size. Such interruptions may be unacceptable for  cases where latency is to be bounded or indexes grow large. Sometimes data flows continuously into an InfinityDB from outside – data like a stock price stream or sensor data stream. It may be necessary to provide low-latency access to input data in real-time, and the IncrementalMergingItemSpace is perfect for this. Retrievals are much slower, but never bog down, and input is much faster. (Other techniques appropriate to extremely high-speed sources like sensor data where historical data can be dynamically archived and pruned are possible – one use is in a time-series database.)

Background Incremental Merging

IncrementalMergingItemSpace can be gradually optimized by invoking advance() by a single background thread (which may not overlap foreground modifying threads). Each advance() invocation makes gradual progress merging all segments together, finally producing a single top-level segment, which will have maximum speed. All other operations are still concurrent. Other text indexing systems occasionally halt everything while potentially huge merges happen, limiting practical index size.

Space Efficiency

InfinityDB always compresses data in memory and on-disk. The results depend on the inherent compressibility of the data, but since ZLib (deflate) is one of the layers, text is compressed very well. There is also prefix compression, branch-cell suffix compression, UTF-8 compression, variable-length Items and components of Items, variable-length blocks, and optimized block allocation within the file when space is re-used. An InfinityDB file never shrinks, but internal free space is bounded at 50% resulting from transactions that touch all blocks. If transactions are kept small, internal free space is small. It is easy for application code to minimize the file by opening a second file and transferring all Items with a few lines of code.t w

File Consistency and Integrity

In a complex text index, sudden application failure must not leave the segment files disorganized or the data will be inaccessible or wrong or cause strange failures. InfinityDB has a global commit that guarantees file integrity and consistency. File structure never is corrupted, and all changes written to the file before the commit will be persisted, and no changes after the commit returns will be persisted. Given this, it might be possible to create a very large text index having a separate InfinityDB file for each segment, but the possible improvement is unknown.