PolarDB:An analysis of the full-text search feature in IMCI

IMCI uses the RBM (Roaring Bitmaps) algorithm to compress and compute posting lists (that is, sets of document IDs).

The RBM implementation is based on the CRoaring library and dynamically selects a storage strategy based on data density:

• If the number of document IDs in the posting list is smaller than a preset threshold, std::array is used for storage.

• If the number exceeds the threshold, the storage switches to the roaring::Roaring64Map type to handle large-scale sparse or dense data while maintaining a high compression ratio.

Performance characteristics:

• Supports lookups with O(logN) complexity during index building.

• Supports SIMD instruction acceleration for set operations such as intersection and union.

• Supports space reorganization when data is written to disk to reduce fragmentation.

• Supports using minimum/maximum values for fast filtering and iterator optimization during queries.

IMCI uses the FST (Finite State Transducer) algorithm to build the term dictionary to balance time efficiency and space efficiency.

• Space efficiency: By sharing the common prefixes and suffixes of terms, the storage space is effectively compressed.

• Time efficiency: The time complexity of a term lookup is O(L), where L is the length of the term.

For example, assume that the terms China, Chinese, and love are inserted in order and that their posting list address offsets are 5, 10, and 15. The dictionary that is built is shown in the following figure. The figure shows that the FST not only shares common prefixes and suffixes to save space, but also guarantees that each transition has a unique associated value. A query starts from initial state 0 and checks each character of the term for an outgoing edge of that character. If the edge exists, the query accumulates the associated value. Otherwise, the query checks whether the current state is a final state. For example, Chinese accumulates an associated value of 15 and its last character is a final state, which means that the term exists in the dictionary. In addition, FST prefix calculation is byte-based rather than character-based, so it also supports encodings such as UTF-8.

When the PolarDB IMCI full-text index is built with SPIMI, IMCI continuously reads the columnstore data of the target column, tokenizes each row to obtain a set of terms, and then adds each term and its corresponding row number to a hash table while accumulating a memory usage value. When the memory usage exceeds the segment size threshold, IMCI builds a dictionary from the terms and posting lists in the hash table, resets the memory, and continues with the next row until all columnstore data is processed. The main process for building a dictionary (FST) from the hash table (std::unordered_map) is as follows: first sort the hash table by term (key); then serialize all posting lists in the hash table to disk in order and record their relative offset addresses on disk; then add each term and the posting list offset address of that term to the FST algorithm in order to build the dictionary; finally compress the dictionary, write it to disk, and record the current segment information (including the dictionary size, the dictionary start address, the posting list start address, and the row number range) in the metadata. PolarDB does not build a global dictionary in order to avoid external sorting (a global dictionary would also have to be split by prefix so that a term index could be built on it). Instead, because columnstore storage uses an append-only write model, PolarDB uses a lightweight build method that produces multiple local dictionaries based on the memory threshold, as shown in the following figure. When memory is sufficient, increase the memory threshold as much as possible. More instances of the same term then fall into the same inverted segment, which saves space and improves query performance.

In addition to the normal inverted index building described above, the PolarDB IMCI full-text index also supports asynchronous merging of inverted indexes when the system is idle in the background. The PolarDB IMCI columnstore index is a secondary index of a regular table. On INSERT, data is always appended to the columnstore storage engine by column in insertion order. DELETE uses mark-for-deletion, and UPDATE is converted to DELETE plus INSERT. IMCI uses array InsertMask to mark the insert version of each row in the columnstore data for visibility checks, and uses lsm DeleteMask to mark an existing row as deleted. At the same time, background operations such as asynchronous Compaction and Recycle reorganize data and reclaim space. As part of the columnstore engine, the PolarDB IMCI full-text index also uses a background asynchronous inverted index Compaction task to periodically clean up data that is marked as deleted, which saves space and improves query performance. Inverted index merging uses the inverted segment as its unit: multiple inverted segments are merged into a new inverted segment, and the original inverted segments are not modified. This prevents the inverted index snapshot objects that queries use from becoming invalid. When the merge finishes, a new inverted index snapshot is generated, and new queries use the new snapshot. Thanks to the local build method and the mark-for-deletion design, a bulk insert does not trigger a global rebuild in the PolarDB IMCI full-text index and only the incremental part is built. The update cost is also very low because only a deletion mark is required, so write performance is not affected even in frequent update scenarios. In addition, periodic background asynchronous merging produces more compact inverted indexes to improve query performance. Combined with the concurrent query capability of the column store, this meets millisecond-level response requirements even in massive data scenarios.

The PolarDB IMCI full-text index supports the official MySQL MATCH function and the LIKE operator.

• MATCH function

  PolarDB IMCI supports using the MATCH function for full-text search regardless of whether a full-text index exists in the row store. If no row store index exists, the query is routed directly to the column store node. If a row store index exists, the query is intelligently distributed based on cost evaluation. To keep the time-consuming operations that a native MySQL full-text index triggers during the optimization phase, such as auxiliary table synchronization and cache loading, from affecting column store performance, PolarDB skips these operations at the start of query distribution.

  During the execution phase, IMCI provides two retrieval methods: the FtsTableScan operator and the MATCH expression. The former obtains matching rows directly from the inverted index and suits scenarios with a high filter ratio. The latter looks up the index by row number and suits scenarios in which preceding conditions have already filtered out most of the data. The execution efficiency of both methods depends on how well other predicates filter data. The column store optimizer therefore estimates the filter ratio from statistics and dynamically selects the optimal strategy. When the operator method is selected, the system automatically rewrites the MATCH function into FtsTableScan + Filter operators.

  The full-text index is built asynchronously, which can briefly delay the visibility of new data. By default, the column store executor completes the query results with a full table scan over unindexed data to ensure the completeness of query results. A parameter controls whether to skip that step, so you can flexibly balance performance and consistency in scenarios with high concurrency and large data volumes. You can also adjust index building parameters to increase the data synchronization frequency and narrow the scope of the full table scan, which further improves query efficiency.

• LIKE acceleration

  Under specific conditions, PolarDB IMCI supports mutual conversion between LIKE and MATCH. Converting LIKE to MATCH is mainly used for query acceleration to reduce the overhead of row-by-row comparison of large amounts of strings in full table scans.

  Currently, this conversion takes effect only when the columnstore full-text index uses the ngram tokenizer and the ngram token length is less than or equal to the length of the LIKE pattern string. Under this condition, the optimizer can rewrite a predicate such as LIKE '%abc%' into FtsTableScan + Filter operators, using the inverted index to quickly filter candidate rows.

  However, because the matching mechanism of ngram tokenization differs from the semantics of LIKE (for example, "abbc" tokenizes to ab, bb, and bc, which overlap with "abc"'s ab and bc and may be falsely judged as a match), the original LIKE expression is retained as a subsequent filter condition for exact verification to ensure result correctness.

  This mechanism significantly improves query performance while effectively balancing semantic accuracy and execution efficiency.

The PolarDB IMCI inverted index consists of multiple inverted segments. Each inverted segment contains its own metadata, one term dictionary, and a series of posting lists, where each term uniquely corresponds to one posting list. The metadata records information such as the start addresses of the dictionary and the posting lists. The metadata is small and resides in memory by default to accelerate index access.

Inverted index retrieval is performed per inverted segment. The main process includes reading the dictionary data, building the FST (Finite State Transducer) dictionary object, looking up the target term in the dictionary, and reading the corresponding posting list to build the RBM (Roaring Bitmap) posting list object.

Specifically, queries are divided into two modes:

1. Operator query: Traverses the metadata of all inverted segments, obtains the dictionary start address, loads the dictionary data, builds the dictionary object, and looks up the target term. If the term is found, it combines the posting list offset address of the term with the start address in the segment to read the complete posting list object.

2. Expression query: Determines the set of inverted segments based on the row number, further filters by the row number range in the metadata, and then performs a dictionary lookup and posting list read similar to the operator query on the matching inverted segments.

To improve performance, IMCI supports term dictionary caching. It uses an independent LRU (Least Recently Used) caching mechanism, and the scheduling module dynamically adjusts the memory quota of that cache. A single posting list is usually small (most require only one 4 KB I/O), and posting lists are also numerous, so the cache hit ratio and the benefit of caching them are limited. Posting list caching is therefore disabled by default to avoid wasting memory resources.

This design balances memory usage and I/O overhead while ensuring query efficiency.