![Cache2.png](/uploads/Cache2_1bcf1b8ff3.png)

To achieve maximum performance, analytical databases optimize every step of their internal data storage and processing pipeline. But the best kind of work performed by a database is work that is not done at all! Caching is an especially popular technique for avoiding unnecessary work by storing the results of earlier computation or remote data, which is expensive to access. ClickHouse uses caching [extensively](https://clickhouse.com/docs/en/operations/caches/), for example, to cache DNS records, local and remote (S3) data, inferred schemas, compiled queries, and regular expressions. In today's blog post, we introduce the newest member of ClickHouse's cache family, the [query cache](https://clickhouse.com/docs/en/operations/query-cache/), which was recently [added with v23.1](https://github.com/ClickHouse/ClickHouse/pull/43797) as an experimental preview feature.


## The Query Cache
The query cache is based on the idea that sometimes there are situations where it is okay to cache the result of expensive `SELECT` queries such that further executions of the same queries can be served directly from the cache. Depending on the type of queries, this can dramatically reduce the latency and resource consumption of the ClickHouse server. As an example, consider a data visualization tool like Grafana or Apache Superset, which displays a report of aggregated sales figures for the last 24 hours. In most cases, sales numbers within a day will change rather slowly, and we can afford to refresh the report only (for example) every three hours. Starting with ClickHouse v23.1, `SELECT` queries can be provided with a "time-to-live" during which the server will only compute the first execution of the query, and further executions are answered without further computation directly from the cache.

After this brief introduction, let's give the query cache a try. For this, we will use the [GitHub Events](https://ghe.clickhouse.tech/) dataset, which contains all events on the GitHub platform since 2011, comprising 3.1 billion rows in total. If you want to follow along, please make sure to have the dataset imported into ClickHouse using the [import instructions](https://ghe.clickhouse.tech/#download-the-dataset).

Since the query cache is still experimental, we first need to enable it. This step will become obsolete once the query cache is GA.

<pre class='code-with-play'>
<div class='code'>
SET allow_experimental_query_cache = true
</div>
</pre>
</p>

As an example for an expensive query, we now compute the ["repositories with the most stars over one day"](https://ghe.clickhouse.tech/#repositories-with-the-most-stars-over-one-day). On my 32-core server, this query takes about 8 seconds to complete:

<pre class='code-with-play'>
<div class='code'>
SELECT
    repo_name,
    toDate(created_at) AS day,
    count() AS stars
FROM github_events
WHERE event_type = 'WatchEvent'
GROUP BY
    repo_name,
    day
ORDER BY count() DESC
LIMIT 1 BY repo_name
LIMIT 50

<span class="pre-whitespace">
┌─repo_name──────────────────────────────────────┬────────day─┬─stars─┐
│ 996icu/996.ICU                                 │ 2019-03-28 │ 76056 │
│ M4cs/BabySploit                                │ 2019-09-08 │ 46985 │
│ x64dbg/x64dbg                                  │ 2018-01-06 │ 26459 │
│ [...]                                          │ [...]      │ [...] │
└────────────────────────────────────────────────┴────────────┴───────┘
</span>

50 rows in set. Elapsed: 8.998 sec. Processed 232.12 million rows, 2.73 GB (25.80 million rows/s., 303.90 MB/s.)
</div>
</pre>
</p>

To enable caching for a query, run it with the setting [`use_query_cache`](https://clickhouse.com/docs/en/operations/settings/settings#use-query-cache). The query cache uses a default time-to-live (TTL) of 60 seconds for query results. This timeout works just fine for the purpose of this example, but if needed, a different TTL can be specified using setting [`query_cache_ttl`](https://clickhouse.com/docs/en/operations/settings/settings#query-cache-ttl), either at query level (`SELECT ... SETTINGS query_cache_ttl = 300`) or at session level (`SET query_cache_ttl = 300`).

<pre class='code-with-play'>
<div class='code'>
SELECT
    repo_name,
    toDate(created_at) AS day,
    count() AS stars
FROM github_events
WHERE event_type = 'WatchEvent'
GROUP BY
    repo_name,
    day
ORDER BY count() DESC
LIMIT 1 BY repo_name
LIMIT 50
SETTINGS use_query_cache = true

<span class="pre-whitespace">
┌─repo_name──────────────────────────────────────┬────────day─┬─stars─┐
│ 996icu/996.ICU                                 │ 2019-03-28 │ 76056 │
│ [...]                                          │ [...]      │ [...] │
└────────────────────────────────────────────────┴────────────┴───────┘
</span>

50 rows in set. Elapsed: 8.577 sec. Processed 232.12 million rows, 2.73 GB (27.06 million rows/s., 318.81 MB/s.)
</div>
</pre>
</p>

The first run of the query with `SETTINGS use_query_result_cache = true` stores the query results in the query cache. Subsequent executions of the same query (also with setting `use_query_cache = true`) and within the query time-to-live will read the previously computed result from the cache and return it immediately. Let's run the query again:

<pre class='code-with-play'>
<div class='code'>
SELECT
    repo_name,
    toDate(created_at) AS day,
    count() AS stars
FROM github_events
WHERE event_type = 'WatchEvent'
GROUP BY
    repo_name,
    day
ORDER BY count() DESC
LIMIT 1 BY repo_name
LIMIT 50
SETTINGS use_query_cache = true

<span class="pre-whitespace">
┌─repo_name──────────────────────────────────────┬────────day─┬─stars─┐
│ 996icu/996.ICU                                 │ 2019-03-28 │ 76056 │
│ [...]                                          │ [...]      │ [...] │
└────────────────────────────────────────────────┴────────────┴───────┘
</span>

50 rows in set. Elapsed: 8.451 sec. Processed 232.12 million rows, 2.73 GB (27.47 million rows/s., 323.56 MB/s.)
</div>
</pre>
</p>

To our surprise, the second execution of the query took more than 8 seconds again. Apparently, the query cache was not used. Let's dig a bit deeper to understand what happened. To that end, we first check the system table `system.query_cache` to find out which query results are stored in the cache.

<pre class='code-with-play'>
<div class='code'>
SELECT *
FROM system.query_cache

Ok.

0 rows in set. Elapsed: 0.001 sec. 
</div>
</pre>
</p>

The query cache is indeed empty! Running the query again after executing `SET send_logs_level = 'trace'` quickly points to the issue.

<pre class='code-with-play'>
<div class='code'>
2023.01.29 12:15:26.592519 [ 1371064 ] {a645c5b7-09a2-456c-bc8b-c506828d3b69} <Trace> QueryCache: Skipped insert (query result too big), new_entry_size_in_bytes: 1328640, new_entry_size_in_rows: 50, query: SELECT repo_name, toDate(created_at) AS day, count() AS stars FROM github_events WHERE event_type = 'WatchEvent' GROUP BY repo_name, day ORDER BY count() DESC LIMIT 1 BY repo_name LIMIT 50 SETTINGS
[...]
2023.01.29 12:15:40.697761 [ 1373583 ] {af02656c-e3e4-41c9-8f48-b8a1db145841} <Trace> QueryCache: No entry found for query SELECT repo_name, toDate(created_at) AS day, count() AS stars FROM github_events WHERE event_type = 'WatchEvent' GROUP BY repo_name, day ORDER BY count() DESC LIMIT 1 BY repo_name LIMIT 50 SETTINGS
</div>
</pre>
</p>

A cache entry would be at least 1328640 bytes (= ca. 1.26 MiB) in size, whereas the default maximum cache entry size is 1048576 bytes (= 1 MiB). Therefore, the cache considered the query result too big by a narrow margin and did not store it. Fortunately, we can change the size threshold. It is currently available as a server-level setting in ClickHouse's server configuration file:

```xml
<query_cache>
    <size>1073741824</size>
    <max_entries>1024</max_entries>
    <max_entry_size>1048576</max_entry_size>
    <max_entry_records>30000000</max_entry_records>
</query_cache>
```

For the purpose of demonstration, let's change the maximum cache entry size in bytes, i.e., `max_entry_size`, from 1 MiB (= `1'048'576` bytes) to the total query cache size of 1 GiB (= `1'073'741'824` bytes). The new settings take effect after the server restarts. As you can see, we could configure the maximum total cache size in bytes, the maximum number of cache entries, and the maximum number of records per cache entry in the same manner.

If we run our query again, we see that the second invocation is served from the cache and returns immediately.

<pre class='code-with-play'>
<div class='code'>
SELECT
    repo_name,
    toDate(created_at) AS day,
    count() AS stars
FROM github_events
WHERE event_type = 'WatchEvent'
GROUP BY
    repo_name,
    day
ORDER BY count() DESC
LIMIT 1 BY repo_name
LIMIT 50
SETTINGS use_query_cache = true

<span class="pre-whitespace">
┌─repo_name──────────────────────────────────────┬────────day─┬─stars─┐
│ 996icu/996.ICU                                 │ 2019-03-28 │ 76056 │
│ [...]                                          │ [...]      │ [...] │
└────────────────────────────────────────────────┴────────────┴───────┘
</span>

50 rows in set. Elapsed: 0.04 sec.
</div>
</pre>
</p>

## Using logs and settings
We can also investigate the query log for query cache hits and misses and look at `system.query_cache` again:

<pre class='code-with-play'>
<div class='code'>
SELECT                                                                                                                   
    query,                                                                                                               
    ProfileEvents['QueryCacheHits']                                                                                
FROM system.query_log                                                                                                                                                                                            
WHERE (type = 'QueryFinish') AND (query LIKE '%github_events%')

[...]

Row 8:                                              
──────                                              
query:                                               
SELECT                                             
    repo_name,                                      
    toDate(created_at) AS day,                                                                          
    count() AS stars                                
FROM github_events                                  
WHERE event_type = 'WatchEvent'                                                                         
GROUP BY                                            
    repo_name,                                      
    day                                             
ORDER BY count() DESC                               
LIMIT 1 BY repo_name                                
LIMIT 50                                            
SETTINGS use_query_cache = true                                                  
arrayElement(ProfileEvents, 'QueryCacheHits'): 1    

SELECT * FROM system.query_cache

Row 1:
──────
key_hash:    SELECT repo_name, toDate(created_at) AS day, count() AS stars FROM github_events WHERE event_type = 'WatchEvent' GROUP BY repo_name, day ORDER BY count() DESC LIMIT 1 BY repo_name LIMIT 50 SETTINGS
expires_at:  2023-01-29 17:55:29
stale:       1
shared:      0
result_size: 1328640

1 row in set. Elapsed: 0.005 sec.
</div>
</pre>
</p>

As we can see, `system.query_log` now also shows an entry for our query. However, because the time passed since the query result was cached is bigger than the cache entry time-to-live (60 seconds by default), the entry is marked "stale". This means that further runs of the query will not use the cached query result but refresh the cache entry instead. Also, note that the `SETTINGS` clause provided with the query is only shown partially. This is caused by an internal pruning of all query-cache-related settings before the query is used as a key for the query cache. This can be a bit confusing but leads to a more natural caching behavior.

If needed, the cache behavior can be controlled in more detail using the following configuration settings. Unlike the maximum cache entry size, these settings are either per query or per session:

- It is sometimes desirable to utilize the cache only passively (= try to read from it but not write to it) or only actively (= try to write to it but not read from it). This can be achieved using settings `enable_writes_to_query_cache` and
`enable_reads_from_query_cache` which are both `true` by default.

- To cache only expensive (in terms of runtime) or frequent queries, you can specify how long (in milliseconds) and how often queries need to run at least such that their result is cached using the settings `use_query_cache_min_query_duration` and `use_query_cache_min_query_runs`.

- Results of queries with non-deterministic functions such as `rand()` and `now()` are by default not cached. If desired, this can be changed using the setting `query_cache_store_results_of_queries_with_nondeterministic_functions`.

- Finally, entries in the query cache are, by default, not shared between users due to security reasons. However, individual cache entries can be marked readable for other users by running them with the setting `query_cache_share_between_users`.

## Design

Generally speaking, one can distinguish transactionally consistent and inconsistent query caching.

In transactionally consistent caching, the database invalidates a cache entry if the result of the associated `SELECT` query changes or even changes potentially. Obvious operations that can change query results include inserts, updates, and deletes of table data. ClickHouse also has certain housekeeping operations, such as collapsing merges, that potentially modify table data. The concept of transactionally consistent caching especially makes sense for OLTP databases such as MySQL, Postgresql, and Oracle which have strict consistency expectations.

In contrast, ClickHouse, as an OLAP database, uses a query cache that is transactionally inconsistent by design. Slightly inaccurate query results are tolerated, assuming that cache entries are associated with a time-to-live after which they expire and that the underlying data changes only a little during this period. Inserts, updates, deletes, and internal housekeeping operations do not invalidate cache entries. As a result, this design avoids the scalability issues that plagued [MySQL's query cache](https://dev.mysql.com/doc/refman/5.7/en/query-cache.html) in high-throughput scenarios.

Another difference to MySQL's query cache is that ClickHouse's query cache references query results using the [Abstract Syntax Tree (AST)](https://en.wikipedia.org/wiki/Abstract_syntax_tree) of the `SELECT` query instead of their query text. This means that caching is agnostic to upper and lowercase changes e.g. `SELECT 1` and `select 1` are treated as the same query.

## Future improvements

Currently, the cache stores its entries in a simple hash table with at most 1024 elements by default (the exact capacity is configurable). If a new entry is inserted, but the cache is already full, then the map is iterated, and all stale entries are removed. If there is still not enough space, the new entry will not be inserted. Users can also clear the cache's content manually using the statement `SYSTEM DROP QUERY CACHE`. It is planned that we will support more sophisticated eviction strategies in the future, for example, Least Recently Used (LRU) or size-based eviction. This will allow users to specify a minimum "freshness level" for `SELECT` queries reading from the cache (as opposed to specifying a maximum time-to-live for queries writing to the cache) and additionally provide better handling of highly skewed query streams.

Further planned improvements to the query cache are:

1. an ability to compress cache entries, e.g., with the ZSTD codec,
2. paging of cache entries on disk such that they survive server restarts,
3. caching of subqueries and intermediate query results, and
4. more configuration settings to tailor the cache to specific use cases, e.g., per-user cache sizes or partitioned caches.

The feedback on the query cache has been really positive so far, and exciting things lie ahead, stay tuned!

With 23.1 we introduced the Query Cache. Such a feature deserves its own blog post, so read about the design, how to use the cache, and future planned improvements.

large_Cache2.png

medium_Cache2.png

small_Cache2.png

thumbnail_Cache2.png

Cache2.png

Introducing the ClickHouse Query Cache

![inverted_indices.png](/uploads/inverted_indices_75e818d687.png)

## Introduction

After a long time in the making, ClickHouse v23.1 shipped a highly anticipated feature - [experimental support for inverted indexes](https://github.com/ClickHouse/ClickHouse/pull/38667). In this blog post, we will not only explore why the community is so excited about inverted indexes but also discuss in detail how inverted indexes work in ClickHouse. A big "thank you!" to IBM, who developed and contributed the code for inverted indexes over the course of the last six months.

## Inverted Indices

Inverted indexes were invented decades ago, but it's only because of search engines like Google that most people interact with inverted indexes multiple times a day - usually without knowing it. An inverted index is the central data structure that enables fast and powerful searching in vast collections of text documents. The idea underlying inverted indexes is to compile a database of terms with pointers to the documents which contain these terms.

Let's look at a small example with four documents to better understand how inverted indexes work.

```sql
CREATE TABLE docs
(
    `key` UInt64,
    `doc` String
)
ENGINE = MergeTree()
ORDER BY key;

INSERT INTO docs VALUES
    (0, 'Sail against the wind'),
    (1, 'Wait and see'),
    (2, 'Sail the seven seas'),
    (3, 'See how the wind blows');
```

To find all documents which contain the term "wind" we could write the following SQL query:

```sql
SELECT *
FROM docs
WHERE doc LIKE '%wind%';

┌─key─┬─doc────────────────────┐
│   0 │ Sail against the wind  │
│   3 │ See how the wind blows │
└─────┴────────────────────────┘

2 rows in set. Elapsed: 0.006 sec. 
```

As expected, this query returns the first and the last document. However, it quickly becomes expensive: we need to check whether each row of column "doc" matches the search term. This means that the runtime of the search grows proportionally with the table size. To avoid that, we create an inverted index on column `doc`. Since the inverted index is still in an experimental state, we first need to enable it. This step will become obsolete once inverted indexes become GA.

```sql
SET allow_experimental_inverted_index = true;

ALTER TABLE docs ADD INDEX inv_idx(doc) TYPE inverted;

ALTER TABLE docs MATERIALIZE INDEX inv_idx;
```

When creating the index, ClickHouse splits each document in the "docs" column into a list of terms. By default, splitting is done along whitespaces, but it is also possible to tokenize the text into [n-grams](https://clickhouse.com/docs/en/sql-reference/functions/splitting-merging-functions/#ngrams). The resulting index will conceptually look like this:

<table>
<tr>
<th><strong>Dictionary (Terms)</strong></th>
<th><strong>Posting Lists</strong></th>
</tr>

<tr>
<td>and</td>
<td>1</td>
</tr>

<tr>
<td>against</td>
<td>0</td>
</tr>


<tr>
<td>blows</td>
<td>3</td>
</tr>

<tr>
<td>how</td>
<td>3</td>
</tr>

<tr>
<td>Sail</td>
<td>0, 2</td>
</tr>

<tr>
<td>See</td>
<td>3</td>
</tr>

<tr>
<td>see</td>
<td>1</td>
</tr>

<tr>
<td>seas</td>
<td>1</td>
</tr>

<tr>
<td>seven</td>
<td>2</td>
</tr>

<tr>
<td>the</td>
<td>0, 2, 3</td>
</tr>

<tr>
<td>Wait</td>
<td>1</td>
</tr>

<tr>
<td>wind</td>
<td>0, 3</td>
</tr>
</table>
</p>

As we can see, the inverted index associates each term with "postings", i.e., the row positions of the documents which contain the corresponding term.

The dictionary in inverted indexes is usually organized in a way that terms can be found quickly. The simplest method to achieve that is to store the terms in alphabetical sort order and to use binary search for lookups. In contrast to that, ClickHouse stores dictionaries as finite state transducers (FSTs). We will discuss FSTs in more detail below. Their main advantage is that redundancies, e.g., shared prefixes between adjacent terms, can be easily removed. This reduces the memory footprint of the dictionary and improves the overall throughput.

Further interesting extensions of dictionaries that are currently not supported but might be added in the future include the following:
- a removal of stop words that carry no semantic weight like "a", "and", "the" etc., and
- lemmatization and stemming as language-specific techniques to reduce words to their linguistic word root, e.g., "walking" becomes "walk", "went" becomes "go", "driving" becomes "drive" etc.

ClickHouse also stores the posting lists in a compressed format (more specifically as "roaring bitmap") with the goal of reducing their memory consumption. We will dig a bit deeper into posting list compression below. In the initial inverted index version, posting lists refer to the row positions of the documents which contain the corresponding term. This might be extended in the future with additional metadata, for example:
- A document frequency count stored with each posting indicating how often the term occurs in the document. Such information will allow us to calculate the term frequency / inverse document frequency (TF-IDF), which is useful for [ranking search results](https://monkeylearn.com/blog/what-is-tf-idf/).
- Word-level postings, i.e., the exact positions of terms inside documents. Such data allows to answer phrase queries where the user does not search for a single term but for multiple consecutive terms (a "phrase").

If we rerun our query, it will automatically use the index:

```sql
SELECT * from docs WHERE doc LIKE '%wind%';

┌─key─┬─doc────────────────────┐
│   0 │ Sail against the wind  │
│   3 │ See how the wind blows │
└─────┴────────────────────────┘

2 rows in set. Elapsed: 0.007 sec. 
```

We can use `EXPLAIN indexes = 1` to verify that the index was used:

```sql
EXPLAIN indexes = 1
SELECT * from docs WHERE doc LIKE '%wind%';

┌─explain─────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY)) │
│   ReadFromMergeTree (default.docs)          │
│   Indexes:                                  │
│     PrimaryKey                              │
│       Condition: true                       │
│       Parts: 1/1                            │
│       Granules: 1/1                         │
│     Skip                                    │
│       Name: inv_idx                         │
│       Description: inverted GRANULARITY 1   │
│       Parts: 1/1                            │
│       Granules: 1/1                         │
└─────────────────────────────────────────────┘

12 rows in set. Elapsed: 0.006 sec.
```

## Posting Lists

Let's first discuss how posting lists are stored. As you can see in the example above, the postings within a posting list are monotonically increasing. Furthermore, the terms in real-world data are typically distributed in a highly skewed manner. This means that most terms normally occur in only a few documents, whereas a few terms occur in many documents. Traditional implementations of inverted indexes exploit both properties by compressing their posting lists with a combination of [delta encoding](https://en.wikipedia.org/wiki/Delta_encoding) and [Golomb (or Golomb-Rice) encoding](https://en.wikipedia.org/wiki/Golomb_coding). Such compression accomplishes a very high compression rate, but compression and decompression become [rather slow](https://dl.acm.org/doi/10.5555/1012294.1012301).

[Modern posting list compression formats](https://dl.acm.org/doi/10.1145/3035918.3064007) are able to strike a better balance between compression/decompression performance and compression rate. Inverted indexes in ClickHouse utilize the state-of-the-art [roaring bitmaps](https://roaringbitmap.org/) format to compress the posting lists. The main idea of this format is to represent the postings as a bitmap (e.g. [3, 4, 7] becomes [00011001]), which are then divided into chunks and stored in specialized containers.

![roaring_bitmaps.png](/uploads/roaring_bitmaps_5f08ce3cd9.png)

Roaring bitmaps store sorted lists of 32-bit integers, i.e., the maximum value is ca. 4.2 billion. The range of all possible integers is then split into equally large ranges of 2^16 integers. All integers in one chunk share their 16 most significant bits, whereas the 16 least significant bits are kept in a specialized container, depending on the distribution of the values in the range. The available container types include an array (for sparsely distributed values), bitmap (for densely distributed values), and run-length encoded (RLE, for data with long consecutive runs of values). An "array of containers" sorted on the upper 16 bits serves as an entry point into the list of containers. This structure is usually small enough to fit into the CPU cache.

In the context of inverted indexes, it is also important to be able to merge and intersect two posting lists quickly. This becomes necessary when users search for a disjunction (OR) or conjunction (AND) of multiple terms, e.g., `SELECT * from docs WHERE doc IN ('wind', 'blows', 'sail')`. Roaring bitmaps are especially good at this as they come with optimized algorithms to union and intersect every combination of two container types. For more details on roaring bitmaps, we refer to [this publication](https://dl.acm.org/doi/10.1002/spe.2402).

## Dictionary Compression

Now that we have taken a closer look at the posting lists let's turn our attention to the compression of dictionaries. The inverted indexes in ClickHouse use Finite State Transducers (FSTs) to represent dictionaries. Most people are probably unfamiliar with FSTs, but many people know [Finite State Machines](https://en.wikipedia.org/wiki/Finite-state_machine). This type of automata has a set of states and a set of transitions between the states, and depending on whether one ends up in an accepting or a non-accepting state, they accept or reject an input. FSTs work similarly, except that state transitions not only consume input, they also produce output. For this reason, FSTs are a popular tool in computer linguistics to translate between two languages.

![FST.png](/uploads/FST_e320464f13.png)

In ClickHouse's inverted indexes, FSTs "translate" terms to posting list offsets. The FST in the above example accepts the terms "See, "see", "seas", "seven" and "wind". The posting list offset is computed by accumulating the outputs of each transition. For example, the term "seas" produces offset 4 + 5 = 9. The figure shows a compressed FST in which common substrings are removed using the techniques explained [here](https://link.springer.com/chapter/10.1007/3-540-44674-5_18).

## Disk Layout

Before demonstrating inverted indexes on a realistic dataset, we will quickly discuss their construction and on-disk layout.

Inverted index construction, also known as "inversion", is a CPU and time-intensive operation. Inverted indexes in ClickHouse are implemented as secondary indices, and as such, they exist at the granularity of a part. With the current implementation, a merge of two parts re-creates the inverted index on the new part from scratch. This might be optimized in the future with more lightweight incremental index maintenance that is able to merge two existing indexes directly. For now, care was taken to limit the cost of index creation. Out of different possible [index construction methods](https://onlinelibrary.wiley.com/doi/10.1002/asi.10268), ClickHouse uses a strategy ("single-pass in-memory inversion") which
- iterates the underlying column data in a single pass (as opposed to requiring two passes),
- processes a configurable chunk of data (as opposed to allocating memory proportional to the size of the underlying column), and
- constructs the index directly (instead of writing intermediate files to disk, which are subsequently merged in a postprocessing step).

The resulting inverted index is segmented, i.e., consists of multiple smaller sub-indexes. Each segment corresponds to a consecutive row range of the original column. Row ranges can be of different sizes but their approximate size can be controlled by the parameter `max_digestion_size_per_segment`.

![inverted_index_layout.png](/uploads/inverted_index_layout_51921c5459.png)

The index of a part is stored as three files.

The metadata file is an array of segment descriptors, each containing a unique segment id, a start row id, a dictionary offset, and a posting list offset. The start row id represents the starting row of the segment, whereas the dictionary and posting list offsets point to the beginning of the current segment's sections in the posting list and the dictionary files.

The posting list file contains the posting lists of all segments. A segment can have multiple posting lists because it can have multiple terms. Starting from the metadata file, we can use the posting list offset to jump to the first posting list of a segment. But since there can be multiple terms within the segment, we also need to find the correct posting list within the segment.

That is what the dictionary file is for. It contains each segment's dictionary (+ the dictionary size) in the form of a minimized FST. During an index lookup, ClickHouse will use the dictionary and the posting list offset in the metadata file to jump to the right FST and the beginning of the segment's posting lists. It will then use the FST in the dictionary file to calculate the offset from the start of the segment's posting lists to the actual posting list and eventually decompress it. Because of this architecture, the inverted index is never fully read into memory; only pieces of the metadata file, the dictionary file, and the posting list file are read at a time.

## A Real-world Example

Finally, it is time to demonstrate the inverted index. We use the Hacker News dataset, which contains 28.7 million comments posted on [Hacker News](https://news.ycombinator.com/). Let's first import the data:

```sql
CREATE TABLE hackernews
(
    `id` UInt64,
    `deleted` UInt8,
    `type` String,
    `author` String,
    `timestamp` DateTime,
    `comment` String,
    `dead` UInt8,
    `parent` UInt64,
    `poll` UInt64,
    `children` Array(UInt32),
    `url` String,
    `score` UInt32,
    `title` String,
    `parts` Array(UInt32),
    `descendants` UInt32
)
ENGINE = MergeTree
ORDER BY (type, author);

INSERT INTO hackernews
    SELECT * FROM s3(
        'https://datasets-documentation.s3.eu-west-3.amazonaws.com/hackernews/hacknernews.parquet',
        'Parquet',
        'id UInt64,
         deleted UInt8,
         type String,
         by String,
         time DateTime,
         text String,
         dead UInt8,
         parent UInt64,
         poll UInt64,
         kids Array(UInt32),
         url String,
         score UInt32,
         title String,
         parts Array(UInt32),
         descendants UInt32');
```

To find out how many comments mention "ClickHouse", we can run:


```sql
SELECT count(*)
FROM hackernews
WHERE hasToken(lower(comment), 'ClickHouse');

┌─count()─┐
│     516 │
└─────────┘

1 row in set. Elapsed: 0.843 sec. Processed 28.74 million rows, 9.75 GB (34.08 million rows/s., 11.57 GB/s.)
```

On my machine, the query took 0.843 seconds to complete. Let's now create an inverted index on the "comment" column. Note that we index lowercase comments to find terms unrelated to their case.

```sql
ALTER TABLE hackernews ADD INDEX comment_idx(lower(comment)) TYPE inverted;
ALTER TABLE hackernews MATERIALIZE INDEX comment_idx;
```

Materialization of the index takes a while (to check if the index was created, use the system table `system.data_skipping_indices`). Let's run the query again:

```sql
SELECT count(*)
FROM hackernews
WHERE hasToken(lower(comment), 'clickhouse');

┌─count()─┐
│    1145 │
└─────────┘

1 row in set. Elapsed: 0.248 sec. Processed 4.54 million rows, 1.79 GB (18.34 million rows/s., 7.24 GB/s.)

EXPLAIN indexes = 1
SELECT count(*)
FROM hackernews
WHERE hasToken(lower(comment), 'clickhouse')

┌─explain─────────────────────────────────────────┐
│ Expression ((Projection + Before ORDER BY))     │
│   Aggregating                                   │
│     Expression (Before GROUP BY)                │
│       Filter (WHERE)                            │
│         ReadFromMergeTree (default.hackernews)  │
│         Indexes:                                │
│           PrimaryKey                            │
│             Condition: true                     │
│             Parts: 4/4                          │
│             Granules: 3528/3528                 │
│           Skip                                  │
│             Name: comment_idx                   │
│             Description: inverted GRANULARITY 1 │
│             Parts: 4/4                          │
│             Granules: 554/3528                  │
└─────────────────────────────────────────────────┘
```

This is about 3.4x faster than without an index! We can also search for one or all of multiple terms, i.e., disjunctions or conjunctions:

```sql
SELECT count(*)
FROM hackernews
WHERE multiSearchAny(lower(comment), ['oltp', 'olap']);

┌─count()─┐
│    2177 │
└─────────┘

1 row in set. Elapsed: 0.482 sec. Processed 8.84 million rows, 3.47 GB (18.34 million rows/s., 7.19 GB/s.)

SELECT count(*)
FROM hackernews
WHERE hasToken(lower(comment), 'avx') AND hasToken(lower(comment), 'sve');

┌─count()─┐
│      22 │
└─────────┘

1 row in set. Elapsed: 0.240 sec. Processed 663.55 thousand rows, 272.44 MB (2.77 million rows/s., 1.14 GB/s.)
```

In the future, there will hopefully be a dedicated function similar to `multiSearchAny()` to search for multiple AND'ed terms at once.

With that, we wrap our blog post on inverted indexes in ClickHouse. We would be happy to hear back from you, for example, with your own experiences using inverted indexes or ideas for future extensions.

Inverted Indices to ClickHouse? Yes, you read it right. Read on to learn more about how they work and how you can use them to accelerate your string matching.

Robert Schulze

Blog posts by Robert Schulze

Introducing the ClickHouse Query Cache

Introducing Inverted Indices in ClickHouse