Full-text search with text indexes

#### Header cache settings[​](#caching-header "Direct link to Header cache settings")

|  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Setting Description|  |  |  |  |  |  |  |  | | --- | --- | --- | --- | --- | --- | --- | --- | | [text\_index\_header\_cache\_policy](/docs/operations/server-configuration-parameters/settings#text_index_header_cache_policy) Text index header cache policy name.|  |  |  |  |  |  | | --- | --- | --- | --- | --- | --- | | [text\_index\_header\_cache\_size](/docs/operations/server-configuration-parameters/settings#text_index_header_cache_size) Maximum cache size in bytes.|  |  |  |  | | --- | --- | --- | --- | | [text\_index\_header\_cache\_max\_entries](/docs/operations/server-configuration-parameters/settings#text_index_header_cache_max_entries) Maximum number of deserialized headers in cache.|  |  | | --- | --- | | [text\_index\_header\_cache\_size\_ratio](/docs/operations/server-configuration-parameters/settings#text_index_header_cache_size_ratio) The size of the protected queue in the text index header cache relative to the cache's total size. | | | | | | | | | |

#### Posting lists cache settings[​](#caching-posting-lists "Direct link to Posting lists cache settings")

|  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Setting Description|  |  |  |  |  |  |  |  | | --- | --- | --- | --- | --- | --- | --- | --- | | [text\_index\_postings\_cache\_policy](/docs/operations/server-configuration-parameters/settings#text_index_postings_cache_policy) Text index postings cache policy name.|  |  |  |  |  |  | | --- | --- | --- | --- | --- | --- | | [text\_index\_postings\_cache\_size](/docs/operations/server-configuration-parameters/settings#text_index_postings_cache_size) Maximum cache size in bytes.|  |  |  |  | | --- | --- | --- | --- | | [text\_index\_postings\_cache\_max\_entries](/docs/operations/server-configuration-parameters/settings#text_index_postings_cache_max_entries) Maximum number of deserialized postings in cache.|  |  | | --- | --- | | [text\_index\_postings\_cache\_size\_ratio](/docs/operations/server-configuration-parameters/settings#text_index_postings_cache_size_ratio) The size of the protected queue in the text index postings cache relative to the cache's total size. | | | | | | | | | |

## Limitations[​](#limitations "Direct link to Limitations")

The text index currently has the following limitations:

- The materialization of text indexes with a high number of tokens (e.g. 10 billion tokens) can consume significant amounts of memory. Text
  index materialization can happen directly (`ALTER TABLE <table> MATERIALIZE INDEX <index>`) or indirectly in part merges.
- It is not possible to materialize text indexes on parts with more than 4.294.967.296 (= 2^32 = ca. 4.2 billion) rows. Without a materialized text index, queries fall back to slow brute-force search within the part. As a worst case estimation, assume a part contains a single column of type String and MergeTree setting `max_bytes_to_merge_at_max_space_in_pool` (default: 150 GB) was not changed. In this case, the situation happens if the column contains less than 29.5 characters per row on average. In practice, tables also contain other columns and the threshold is multiples times smaller than that (depending on the number, type and size of the other columns).

## Text Indexes vs Bloom-Filter-Based Indexes[​](#text-index-vs-bloom-filter-indexes "Direct link to Text Indexes vs Bloom-Filter-Based Indexes")

String predicates can be sped up using text indexes and bloom-filter-based based indexes (index type `bloom_filter`, `ngrambf_v1`, `tokenbf_v1`, `sparse_grams`), yet both are fundamentally different in their design and intended use cases:

**Bloom filter indexes**

- Are based on probabilistic data structures which may produce false positives.
- Are only able to answer set membership questions, i.e. the column may contain token X vs. definitely does not contain X.
- Store granule-level information to enable skipping coarse ranges during query execution.
- Are hard to tune properly (see [here](/docs/engines/table-engines/mergetree-family/mergetree#n-gram-bloom-filter) for an example).
- Are rather compact (a few kilobytes or megabytes per part).

**Text indexes**

- Build a deterministic inverted index over tokens. No false positives are possible by the index itself.
- Are specifically optimized for text search workloads.
- Store row-level information which enables efficient term lookup.
- Are rather large (dozens to hundreds of megabytes per part).

Bloom-filter-based indexes support full-text search only as a "side effect":

- They do not support advanced tokenization and preprocessing.
- They do not support multi-token search.
- They do not provide the performance characteristics expected from an inverted index.

Text indexes, in contrast, are purpose-built for full-text search:

- They provide tokenization and preprocessing
- They provide efficient support for `hasAllTokens`, `LIKE`, `match`, and similar text-search functions.
- They have significantly better scalability for large text corpora.

## Implementation Details[​](#implementation "Direct link to Implementation Details")

Each text index consists of two (abstract) data structures:

- a dictionary which maps each token to a postings list, and
- a set of postings lists, each representing a set of row numbers.

Text index is built for the whole part.
Unlike other skip indexes, text index can be merged instead of rebuilt on merge of the data parts (see below).

During index creation, three files are created (per part):

**Dictionary blocks file (.dct)**

The tokens in the text index are sorted and stored in dictionary blocks of 512 tokens each (the block size is configurable by parameter `dictionary_block_size`).
A dictionary blocks file (.dct) consists all the dictionary blocks of all index granules in a part.

**Index header file (.idx)**

The index header file contains for each dictionary block the block's first token and its relative offset in the dictionary blocks file.

This sparse index structure is similar to ClickHouse's [sparse primary key index](https://clickhouse.com/docs/guides/best-practices/sparse-primary-indexes)).

**Postings lists file (.pst)**

The posting lists for all tokens are laid out sequentially in the postings list file.
To save space while still allowing fast intersection and union operations, the posting lists are stored as [roaring bitmaps](https://roaringbitmap.org/).
If the posting list is larger than `posting_list_block_size`, it is split into multiple blocks that are stored sequentially to the postings lists file.

**Merging of text indexes**

When data parts are merged, the text index does not need to be rebuilt from scratch; instead, it can be merged efficiently in a separate step of the merge process.
During this step, the sorted dictionaries of the text indexes of each input part are read and combined into a new unified dictionary.
The row numbers in the postings lists are also recalculated to reflect their new positions in the merged data part, using a mapping of old to new row numbers that is created during the initial merge phase.
This method of merging text indexes is similar to how [projections](/docs/sql-reference/statements/alter/projection#projection-indexes) with `_part_offset` column are merged.
If index is not materialized in the source part, it is built, written into a temporary file and then merged together with indexes from the other parts and from other temporary index files.

**Debugging**

Table function [mergeTreeTextIndex](/docs/sql-reference/table-functions/mergeTreeTextIndex) can be used to introspect text indexes.

## Example: Hackernews dataset[​](#hacker-news-dataset "Direct link to Example: Hackernews dataset")

Let's look at the performance improvements of text indexes on a large dataset with lots of text.
We will use 28.7M rows of comments on the popular Hacker News website.
Here is the table without text index: