Clickhouse and the reason why we implemented or re-implemented and what was the use cases for us
that motivated us to implement the inverted index in the first place.
So before the inverted index, maybe some of you don't know clickhouse, maybe small introduction
about it.
So it is open source database, and I hope it will be our favorite database soon.
And the development of clickhouse started in 2009 in Yandex and then it went to production
in 2012.
Then since 2016 it became open source, so it is mostly used for column oriented data storage
so best for aggregations.
So it means that we have a different files for each column.
So yeah, there are also some sorting and indexes and aggregation, first aggregation implementations.
It's also distributed, so it's replicated, started, moved to the master and cross region.
I think I hope you are familiar with the terms.
Then yeah, it's mostly the allot database, so mostly it's for analytical use cases, aggregations
and so on.
Okay, so we can start with the full text search, the journey that we started.
At clickhouse, so actually the inverted index in clickhouse is not new, so the main development
or experimental development started in 2022 and then in the late 2022 and early 2022
and three, it became or released as an experimental feature.
Then in around February last year we started re-implementation, so I will talk about why we
started re-implement the main reason and then September 2025 we released a private preview
for our cloud customers but it also opensource in the version and then the better version
is just released last month in December.
So the use case, what's the problem that we are trying to solve?
Let's say that we have some observable to table, that has a very large rows, like we have
two billions and some rows in between and you want to search a specific term in this
highlighted row, so you want to search a very something that's term in this very large table.
What's the query? So we have the simple query, we have a select that from logs and where
has contains all tokens and you specify some tokens that we are looking at.
So what's the problem with this query? The problem is it is very small because it's a full
table scan, so you have to iterate all rows in your table and then look for the tokens and it
instantly becomes very small. So before the solution, I want to give some fundamental
knowledge about some parts of the clickhouse, so the granule, what's the granule?
Granule is the representative smallest individual data unit in process by clickhouse,
so by default, we take 8,1292 rows in a single granule, and then we also have a special
index called skipping decks, whenever you skip index instead of skipping the rows, it just
keeps the granules. So afterwards you have to double check your data really exists in this granule
or in each row's in granule or not, and this is also this can be a bottleneck for some index
slackties and but we need a very fast solution that we don't we just skip the unnecessary rows
at maximum level. So another reason or motivation was the tokenizers, so let's take the
simple query that has some timestamps, some to keep it short, I didn't really put a error message,
but some yet this is the second part in the curly brackets is query ID, then we have some
log level, and if you use a different tokenizers like split by non-alpha, so it will, yeah,
it will split like that, it will instead of taking the date column or the date value is as a
single token, it will also split in the two years, months and days, so there's a split by string,
so you can define what's your split points, so you can split that. If you use that, you can
definitely split by dates or date and time separately, also to keep the query. In the first one,
you can also see there's a dash between the in the query ID, so that's why it takes the
it also splits that, and also that you can use ingrants by default, I will three, so this is
how we, the ingram process the token or the text, there's also array tokenizer, but that was
standard demanded by some people, instead of tokenizing it, it does basically nothing, it just
gives the whole text as a single token, okay, and for all these motivations, we need the new
solution, what we call a new full text search, and I will explain its building blocks, so let's start
with the syntax first, how it is different to the other index, so first, you create a table,
you define your columns, and at end you either, you say, I want to have an index, and the index
name and column name, then you specify the type, it's text, now we have a key value pair here,
so you just define your tokenizer, you can use a different tokenizer split by an alpha split by string,
ingrams, sparscrams, and array, and yeah, this is how you can define your text index,
the new text index and clickles, and currently we support this five tokenizers,
that we didn't support in the first version, then the new also the, to use the,
to use an text index, we introduced two new functions called, has any tokens and has all tokens,
so basically it is just search for, and the search stickers in your column data,
so the difference is that, yeah, you can either search for any tokens, it means that if the clickhouse
or first them appears in your row, it will return that, or you can use has all tokens, it means that
both terms need to occur in your row data, okay, so how we implement the full text search,
so it is based on the inverted index, so what's the inverted index, it's the inverted index,
basically I'm mapping to, okay, it's basically mapping to documents, so in the picture in the
left side you can see there's an ID and the content, and the tokens from this content is the
quick-prone folks, and we build the, the inverted index just maps to the, okay, let's say the
problem, token appears in the first and the third document, and we just keep that record,
then also that we, how the data or index data is organized, we build a, or we maintain a
hash table while processing on memory, which is, yeah, this is the picture on the right side,
but once we need to store this hash map to the disk, we split in those three different files,
so it's there next to the column data, let's say text.bin, binary file, so we have a smart index,
we have a dictionary file, and we have a postings, so I will explain what are they,
so just a quick comment, the postings list is just, we are currently using a bitmap,
and it's because it's very smaller, and it's very efficient to process on memory, okay,
let's start with how we build this sparse index and dictionary blocks, if you can see that in this
hash table, the tokens are not sorted, so it means that we first need to sort all these tokens,
so the first process or first step is sorting all tokens, and afterwards we split in the tokens,
or we sort the tokens, then we split them into what we call a dictionary blocks, and the dictionary
blocks are separated by, yeah, I think by default we are using 128 tokens in a single dictionary
block, and we also use a compression called front coding, so on the left side it's a road token,
on the right side we can see we put the sum numbers and characters which is for front coding
compression, afterwards before that we also have a each token points to its postings list,
and we just keep that again, and afterwards we build what we call the sparse index, sparse index
is basically the first points of each or first token of each block, and we use this for finding
it, first data, okay, yeah, okay, so I will have some demo to short it,
okay, hello, okay, this button, I think it's, I will just run the clickhouse,
so that's run there, it's trying to go my laptop, so no tricks does that clickhouse client,
okay, I will use I have a demo, then to use the new text index, we have a called enable full text
index feature, so you have to enable that, then I have three, actually I will use only the first
one, so there's a Hector new status set, and we can see how many, okay,
yeah, they are around the 30 million entries in this one, and if I just want to search
any token from that, let's say I have a token, text, clickhouse, and I will set some settings,
let me show that very condition page, and so in this one I can keep that, so in this first query,
I will disable the skipping this, and I will use disable the query condition cache,
make sure that it doesn't use any cache for condition, so it takes some time, so
for this simple query, it took around four seconds to scan around 30 GB of data,
and it's a scanned whole dataset to answer the query, the interesting thing is what happens if you
if we enable the skipping decks, which I have a text index on it, so you can see that we can
answer this query in seven milliseconds, instead of four seconds, and the interesting part is
we don't need to scan the whole dataset, and we just need to read one point four megabytes
to answer this query, and also the peak memory usage is very low, okay,
now I can continue that, so, okay now the question is what happened, so how we are looking
this term in our in the text index, we have a we need first need to scan our sparse index,
and since the sparse index is contains the first entries from each block and since they are
sorted, we can simply use a binary search, we don't need to scan the whole sparse index,
we just simply use binary search to find the block index, we have a blocks index one for this
click-offs, we found the blocks index one, after do that, we get the block index dictionary block
one, and in this block we have a different tokens, and now we look the click-offs really in this
dictionary block, and if this present we need to read it's post-naclist, and yeah if it's
present, we simply just need the post-naclist that contains some integer seconds that, yeah,
shows, okay, if this token contains in this dictionary document IDs, and afterwards what we are doing
is very interesting is instead of using this raw or document IDs, correctly we build a
what we call a virtual boolean column, so basically we create a very large boolean column with the size
of the column itself, and by default they are zero, and when we find the took, or we fill this, we set
once to the in this virtual column with the raw IDs that we found in our post-naclist, and
afterwards we there's a special optimization, text index optimization, so instead of using the
original filter column, we create this virtual column on background, and we just basically remove
the original filter column and use this virtual column, and this way we really don't need to execute
the original filter column anymore, and this makes it very fast, and this is what happened when I
use this when I use in demo, so, okay, so just putting it all together, so this is the whole
mechanism, so you first we look for a term, we search in a sparse index, then we retrieve the
dictionary block, then if to present in a dictionary block we retrieve the post-naclist and we
create our virtual boolean column, and we use this virtual boolean column just for filtering the data,
okay, this is the summary, and if you say I liked it, you can try it yourself, it's in the open source
click-all since version, actually the version is already enabled by in the 20.5.10, but the better version
is released in 25.12, and we also offer a private preview for our click-all's cloud customers,
and also the more features are coming, so we are planning to implement the phase search, also
cause aka known as a positional queries, and in also this year we are also planning to add the
squarings to the text index, okay, and this is the talk, thank you so much, and if you have
a connection, okay, just one last slide, so we have a designer, we have a community dinner,
if you want to join, just scan the QR code and this evening in Brussels we will have a
community dinner, thanks. Hi, it just wanted to ask you, when you had the tokens,
how did you go about creating that, and I feel, for instance, like, we have a lot of things,
so as you are following the page, you will happen that you are at the version of coming out,
just in case you can look at them, yeah, and if you analyze it, if you analyze it, except the
question mark, then you will have in your sparse index, but if you don't have, you can, it's very,
it's very flexible, so you can just keep on it, how you want to analyze your data, so you define it,
if there's a exclamation mark, we will either use us to move it, or you want to see it.
There's something in the text, if there's something in the text, we need to indicate,
you can use the root for the world, yes, yes, so I have, like, for example, I will click out,
just click with the root, I will be the top zero, and then I will be the one, the first,
you mean the in the sparse index, yes, sparse index, we just basically use a binary search
with upper one, or this means that after this point, this token cannot occur there,
because it's there, sort, it can be only appeared before, but how do you decide which,
like, which token is good enough for when you are a index here, when you have a different block,
the first block was clicked and then you have to take out the data, and say, how do you define
what's in the data, it is an analysis, so, yeah, no, we are just using a sort, we just, we sort them,
or we take it, and then it's the first one in my case, okay, so it's really beneficial if you have a lot of