A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://clickhouse.com/docs/guides/best-practices/sparse-primary-indexes below:

A Practical Introduction to Primary Indexes in ClickHouse

A practical introduction to primary indexes in ClickHouse Introduction​

In this guide we are going to do a deep dive into ClickHouse indexing. We will illustrate and discuss in detail:

You can optionally execute all ClickHouse SQL statements and queries given in this guide by yourself on your own machine. For installation of ClickHouse and getting started instructions, see the Quick Start.

Data set​

Throughout this guide we will use a sample anonymized web traffic data set.

With these three columns we can already formulate some typical web analytics queries such as:

Test machine​

All runtime numbers given in this document are based on running ClickHouse 22.2.1 locally on a MacBook Pro with the Apple M1 Pro chip and 16GB of RAM.

A full table scan​

In order to see how a query is executed over our data set without a primary key, we create a table (with a MergeTree table engine) by executing the following SQL DDL statement:

Next insert a subset of the hits data set into the table with the following SQL insert statement. This uses the URL table function in order to load a subset of the full dataset hosted remotely at clickhouse.com:

The response is:

ClickHouse client's result output shows us that the statement above inserted 8.87 million rows into the table.

Lastly, in order to simplify the discussions later on in this guide and to make the diagrams and results reproducible, we optimize the table using the FINAL keyword:

Note

In general it is not required nor recommended to immediately optimize a table after loading data into it. Why this is necessary for this example will become apparent.

Now we execute our first web analytics query. The following is calculating the top 10 most clicked urls for the internet user with the UserID 749927693:

The response is:

ClickHouse client's result output indicates that ClickHouse executed a full table scan! Each single row of the 8.87 million rows of our table was streamed into ClickHouse. That doesn't scale.

To make this (way) more efficient and (much) faster, we need to use a table with a appropriate primary key. This will allow ClickHouse to automatically (based on the primary key's column(s)) create a sparse primary index which can then be used to significantly speed up the execution of our example query.

ClickHouse index design​ An index design for massive data scales​

In traditional relational database management systems, the primary index would contain one entry per table row. This would result in the primary index containing 8.87 million entries for our data set. Such an index allows the fast location of specific rows, resulting in high efficiency for lookup queries and point updates. Searching an entry in a B(+)-Tree data structure has an average time complexity of O(log n); more precisely, log_b n = log_2 n / log_2 b where b is the branching factor of the B(+)-Tree and n is the number of indexed rows. Because b is typically between several hundred and several thousand, B(+)-Trees are very shallow structures, and few disk-seeks are required to locate records. With 8.87 million rows and a branching factor of 1000, 2.3 disk seeks are needed on average. This capability comes at a cost: additional disk and memory overheads, higher insertion costs when adding new rows to the table and entries to the index, and sometimes rebalancing of the B-Tree.

Considering the challenges associated with B-Tree indexes, table engines in ClickHouse utilise a different approach. The ClickHouse MergeTree Engine Family has been designed and optimized to handle massive data volumes. These tables are designed to receive millions of row inserts per second and store very large (100s of Petabytes) volumes of data. Data is quickly written to a table part by part, with rules applied for merging the parts in the background. In ClickHouse each part has its own primary index. When parts are merged, then the merged part's primary indexes are also merged. At the very large scale that ClickHouse is designed for, it is paramount to be very disk and memory efficient. Therefore, instead of indexing every row, the primary index for a part has one index entry (known as a 'mark') per group of rows (called 'granule') - this technique is called sparse index.

Sparse indexing is possible because ClickHouse is storing the rows for a part on disk ordered by the primary key column(s). Instead of directly locating single rows (like a B-Tree based index), the sparse primary index allows it to quickly (via a binary search over index entries) identify groups of rows that could possibly match the query. The located groups of potentially matching rows (granules) are then in parallel streamed into the ClickHouse engine in order to find the matches. This index design allows for the primary index to be small (it can, and must, completely fit into the main memory), whilst still significantly speeding up query execution times: especially for range queries that are typical in data analytics use cases.

The following illustrates in detail how ClickHouse is building and using its sparse primary index. Later on in the article, we will discuss some best practices for choosing, removing, and ordering the table columns that are used to build the index (primary key columns).

A table with a primary key​

Create a table that has a compound primary key with key columns UserID and URL:

DDL Statement Details

In order to simplify the discussions later on in this guide, as well as make the diagrams and results reproducible, the DDL statement:

The primary key in the DDL statement above causes the creation of the primary index based on the two specified key columns.

Next insert the data:

The response looks like:

And optimize the table:

We can use the following query to obtain metadata about our table:

The response is:

The output of the ClickHouse client shows:

Data is stored on disk ordered by primary key column(s)​

Our table that we created above has

Note

The inserted rows are stored on disk in lexicographical order (ascending) by the primary key columns (and the additional EventTime column from the sorting key).

Note

ClickHouse allows inserting multiple rows with identical primary key column values. In this case (see row 1 and row 2 in the diagram below), the final order is determined by the specified sorting key and therefore the value of the EventTime column.

ClickHouse is a column-oriented database management system. As shown in the diagram below

UserID.bin, URL.bin, and EventTime.bin are the data files on disk where the values of the UserID, URL, and EventTime columns are stored.

Note

Data is organized into granules for parallel data processing​

For data processing purposes, a table's column values are logically divided into granules. A granule is the smallest indivisible data set that is streamed into ClickHouse for data processing. This means that instead of reading individual rows, ClickHouse is always reading (in a streaming fashion and in parallel) a whole group (granule) of rows.

Note

Column values are not physically stored inside granules: granules are just a logical organization of the column values for query processing.

The following diagram shows how the (column values of) 8.87 million rows of our table are organized into 1083 granules, as a result of the table's DDL statement containing the setting index_granularity (set to its default value of 8192).

The first (based on physical order on disk) 8192 rows (their column values) logically belong to granule 0, then the next 8192 rows (their column values) belong to granule 1 and so on.

Note

The primary index has one entry per granule​

The primary index is created based on the granules shown in the diagram above. This index is an uncompressed flat array file (primary.idx), containing so-called numerical index marks starting at 0.

The diagram below shows that the index stores the primary key column values (the values marked in orange in the diagram above) for each first row for each granule. Or in other words: the primary index stores the primary key column values from each 8192nd row of the table (based on the physical row order defined by the primary key columns). For example

In total the index has 1083 entries for our table with 8.87 million rows and 1083 granules:

Note

Inspecting the content of the primary index

On a self-managed ClickHouse cluster we can use the file table function for inspecting the content of the primary index of our example table.

For that we first need to copy the primary index file into the user_files_path of a node from the running cluster:

Now we can inspect the content of the primary index via SQL:

This matches exactly our diagram of the primary index content for our example table:

The primary key entries are called index marks because each index entry is marking the start of a specific data range. Specifically for the example table:

As we will see later, this global order enables ClickHouse to use a binary search algorithm over the index marks for the first key column when a query is filtering on the first column of the primary key.

The primary index is used for selecting granules​

We can now execute our queries with support from the primary index.

The following calculates the top 10 most clicked urls for the UserID 749927693.

The response is:

The output for the ClickHouse client is now showing that instead of doing a full table scan, only 8.19 thousand rows were streamed into ClickHouse.

If trace logging is enabled then the ClickHouse server log file shows that ClickHouse was running a binary search over the 1083 UserID index marks, in order to identify granules that possibly can contain rows with a UserID column value of 749927693. This requires 19 steps with an average time complexity of O(log2 n):

We can see in the trace log above, that one mark out of the 1083 existing marks satisfied the query.

Trace Log Details

Mark 176 was identified (the 'found left boundary mark' is inclusive, the 'found right boundary mark' is exclusive), and therefore all 8192 rows from granule 176 (which starts at row 1.441.792 - we will see that later on in this guide) are then streamed into ClickHouse in order to find the actual rows with a UserID column value of 749927693.

We can also reproduce this by using the EXPLAIN clause in our example query:

The response looks like:

The client output is showing that one out of the 1083 granules was selected as possibly containing rows with a UserID column value of 749927693.

Conclusion

When a query is filtering on a column that is part of a compound key and is the first key column, then ClickHouse is running the binary search algorithm over the key column's index marks.

As discussed above, ClickHouse is using its sparse primary index for quickly (via binary search) selecting granules that could possibly contain rows that match a query.

This is the first stage (granule selection) of ClickHouse query execution.

In the second stage (data reading), ClickHouse is locating the selected granules in order to stream all their rows into the ClickHouse engine in order to find the rows that are actually matching the query.

We discuss that second stage in more detail in the following section.

Mark files are used for locating granules​

The following diagram illustrates a part of the primary index file for our table.

As discussed above, via a binary search over the index's 1083 UserID marks, mark 176 was identified. Its corresponding granule 176 can therefore possibly contain rows with a UserID column value of 749.927.693.

Granule Selection Details

The diagram above shows that mark 176 is the first index entry where both the minimum UserID value of the associated granule 176 is smaller than 749.927.693, and the minimum UserID value of granule 177 for the next mark (mark 177) is greater than this value. Therefore only the corresponding granule 176 for mark 176 can possibly contain rows with a UserID column value of 749.927.693.

In order to confirm (or not) that some row(s) in granule 176 contain a UserID column value of 749.927.693, all 8192 rows belonging to this granule need to be streamed into ClickHouse.

To achieve this, ClickHouse needs to know the physical location of granule 176.

In ClickHouse the physical locations of all granules for our table are stored in mark files. Similar to data files, there is one mark file per table column.

The following diagram shows the three mark files UserID.mrk, URL.mrk, and EventTime.mrk that store the physical locations of the granules for the table's UserID, URL, and EventTime columns.

We have discussed how the primary index is a flat uncompressed array file (primary.idx), containing index marks that are numbered starting at 0.

Similarly, a mark file is also a flat uncompressed array file (*.mrk) containing marks that are numbered starting at 0.

Once ClickHouse has identified and selected the index mark for a granule that can possibly contain matching rows for a query, a positional array lookup can be performed in the mark files in order to obtain the physical locations of the granule.

Each mark file entry for a specific column is storing two locations in the form of offsets:

All the 8192 rows belonging to the located uncompressed granule are then streamed into ClickHouse for further processing.

Note

Index granularity is adaptive by default, but for our example table we disabled adaptive index granularity (in order to simplify the discussions in this guide, as well as make the diagrams and results reproducible). Our table is using wide format because the size of the data is larger than min_bytes_for_wide_part (which is 10 MB by default for self-managed clusters).

Why Mark Files

Why does the primary index not directly contain the physical locations of the granules that are corresponding to index marks?

Because at that very large scale that ClickHouse is designed for, it is important to be very disk and memory efficient.

The primary index file needs to fit into the main memory.

For our example query, ClickHouse used the primary index and selected a single granule that can possibly contain rows matching our query. Only for that one granule does ClickHouse then need the physical locations in order to stream the corresponding rows for further processing.

Furthermore, this offset information is only needed for the UserID and URL columns.

Offset information is not needed for columns that are not used in the query e.g. the EventTime.

For our sample query, ClickHouse needs only the two physical location offsets for granule 176 in the UserID data file (UserID.bin) and the two physical location offsets for granule 176 in the URL data file (URL.bin).

The indirection provided by mark files avoids storing, directly within the primary index, entries for the physical locations of all 1083 granules for all three columns: thus avoiding having unnecessary (potentially unused) data in main memory.

The following diagram and the text below illustrate how for our example query ClickHouse locates granule 176 in the UserID.bin data file.

We discussed earlier in this guide that ClickHouse selected the primary index mark 176 and therefore granule 176 as possibly containing matching rows for our query.

ClickHouse now uses the selected mark number (176) from the index for a positional array lookup in the UserID.mrk mark file in order to get the two offsets for locating granule 176.

As shown, the first offset is locating the compressed file block within the UserID.bin data file that in turn contains the compressed version of granule 176.

Once the located file block is uncompressed into the main memory, the second offset from the mark file can be used to locate granule 176 within the uncompressed data.

ClickHouse needs to locate (and stream all values from) granule 176 from both the UserID.bin data file and the URL.bin data file in order to execute our example query (top 10 most clicked URLs for the internet user with the UserID 749.927.693).

The diagram above shows how ClickHouse is locating the granule for the UserID.bin data file.

In parallel, ClickHouse is doing the same for granule 176 for the URL.bin data file. The two respective granules are aligned and streamed into the ClickHouse engine for further processing i.e. aggregating and counting the URL values per group for all rows where the UserID is 749.927.693, before finally outputting the 10 largest URL groups in descending count order.

Using multiple primary indexes​ Secondary key columns can (not) be inefficient​

When a query is filtering on a column that is part of a compound key and is the first key column, then ClickHouse is running the binary search algorithm over the key column's index marks.

But what happens when a query is filtering on a column that is part of a compound key, but is not the first key column?

Note

We discuss a scenario when a query is explicitly not filtering on the first key column, but on a secondary key column.

When a query is filtering on both the first key column and on any key column(s) after the first then ClickHouse is running binary search over the first key column's index marks.

We use a query that calculates the top 10 users that have most frequently clicked on the URL "http://public_search":

The response is:

The client output indicates that ClickHouse almost executed a full table scan despite the URL column being part of the compound primary key! ClickHouse reads 8.81 million rows from the 8.87 million rows of the table.

If trace_logging is enabled then the ClickHouse server log file shows that ClickHouse used a generic exclusion search over the 1083 URL index marks in order to identify those granules that possibly can contain rows with a URL column value of "http://public_search":

We can see in the sample trace log above, that 1076 (via the marks) out of 1083 granules were selected as possibly containing rows with a matching URL value.

This results in 8.81 million rows being streamed into the ClickHouse engine (in parallel by using 10 streams), in order to identify the rows that are actually contain the URL value "http://public_search".

However, as we will see later, only 39 granules out of that selected 1076 granules actually contain matching rows.

Whilst the primary index based on the compound primary key (UserID, URL) was very useful for speeding up queries filtering for rows with a specific UserID value, the index is not providing significant help with speeding up the query that filters for rows with a specific URL value.

The reason for this is that the URL column is not the first key column and therefore ClickHouse is using a generic exclusion search algorithm (instead of binary search) over the URL column's index marks, and the effectiveness of that algorithm is dependant on the cardinality difference between the URL column and its predecessor key column UserID.

In order to illustrate that, we give some details about how the generic exclusion search works.

Generic exclusion search algorithm​

The following is illustrating how the ClickHouse generic exclusion search algorithm works when granules are selected via a secondary column where the predecessor key column has a low(er) or high(er) cardinality.

As an example for both cases we will assume:

We have marked the key column values for the first table rows for each granule in orange in the diagrams below..

Predecessor key column has low(er) cardinality

Suppose UserID had low cardinality. In this case it would be likely that the same UserID value is spread over multiple table rows and granules and therefore index marks. For index marks with the same UserID, the URL values for the index marks are sorted in ascending order (because the table rows are ordered first by UserID and then by URL). This allows efficient filtering as described below:

There are three different scenarios for the granule selection process for our abstract sample data in the diagram above:

  1. Index mark 0 for which the URL value is smaller than W3 and for which the URL value of the directly succeeding index mark is also smaller than W3 can be excluded because mark 0, and 1 have the same UserID value. Note that this exclusion-precondition ensures that granule 0 is completely composed of U1 UserID values so that ClickHouse can assume that also the maximum URL value in granule 0 is smaller than W3 and exclude the granule.

  2. Index mark 1 for which the URL value is smaller (or equal) than W3 and for which the URL value of the directly succeeding index mark is greater (or equal) than W3 is selected because it means that granule 1 can possibly contain rows with URL W3.

  3. Index marks 2 and 3 for which the URL value is greater than W3 can be excluded, since index marks of a primary index store the key column values for the first table row for each granule and the table rows are sorted on disk by the key column values, therefore granule 2 and 3 can't possibly contain URL value W3.

Predecessor key column has high(er) cardinality

When the UserID has high cardinality then it is unlikely that the same UserID value is spread over multiple table rows and granules. This means the URL values for the index marks are not monotonically increasing:

As we can see in the diagram above, all shown marks whose URL values are smaller than W3 are getting selected for streaming its associated granule's rows into the ClickHouse engine.

This is because whilst all index marks in the diagram fall into scenario 1 described above, they do not satisfy the mentioned exclusion-precondition that the directly succeeding index mark has the same UserID value as the current mark and thus can't be excluded.

For example, consider index mark 0 for which the URL value is smaller than W3 and for which the URL value of the directly succeeding index mark is also smaller than W3. This can not be excluded because the directly succeeding index mark 1 does not have the same UserID value as the current mark 0.

This ultimately prevents ClickHouse from making assumptions about the maximum URL value in granule 0. Instead it has to assume that granule 0 potentially contains rows with URL value W3 and is forced to select mark 0.

The same scenario is true for mark 1, 2, and 3.

Conclusion

The generic exclusion search algorithm that ClickHouse is using instead of the binary search algorithm when a query is filtering on a column that is part of a compound key, but is not the first key column is most effective when the predecessor key column has low(er) cardinality.

In our sample data set both key columns (UserID, URL) have similar high cardinality, and, as explained, the generic exclusion search algorithm is not very effective when the predecessor key column of the URL column has a high(er) or similar cardinality.

Note about data skipping index​

Because of the similarly high cardinality of UserID and URL, our query filtering on URL also wouldn't benefit much from creating a secondary data skipping index on the URL column of our table with compound primary key (UserID, URL).

For example this two statements create and populate a minmax data skipping index on the URL column of our table:

ClickHouse now created an additional index that is storing - per group of 4 consecutive granules (note the GRANULARITY 4 clause in the ALTER TABLE statement above) - the minimum and maximum URL value:

The first index entry ('mark 0' in the diagram above) is storing the minimum and maximum URL values for the rows belonging to the first 4 granules of our table.

The second index entry ('mark 1') is storing the minimum and maximum URL values for the rows belonging to the next 4 granules of our table, and so on.

(ClickHouse also created a special mark file for to the data skipping index for locating the groups of granules associated with the index marks.)

Because of the similarly high cardinality of UserID and URL, this secondary data skipping index can't help with excluding granules from being selected when our query filtering on URL is executed.

The specific URL value that the query is looking for (i.e. 'http://public_search') very likely is between the minimum and maximum value stored by the index for each group of granules resulting in ClickHouse being forced to select the group of granules (because they might contain row(s) matching the query).

A need to use multiple primary indexes​

As a consequence, if we want to significantly speed up our sample query that filters for rows with a specific URL then we need to use a primary index optimized to that query.

If in addition we want to keep the good performance of our sample query that filters for rows with a specific UserID then we need to use multiple primary indexes.

The following is showing ways for achieving that.

Options for creating additional primary indexes​

If we want to significantly speed up both of our sample queries - the one that filters for rows with a specific UserID and the one that filters for rows with a specific URL - then we need to use multiple primary indexes by using one of these three options:

All three options will effectively duplicate our sample data into a additional table in order to reorganize the table primary index and row sort order.

However, the three options differ in how transparent that additional table is to the user with respect to the routing of queries and insert statements.

When creating a second table with a different primary key then queries must be explicitly send to the table version best suited for the query, and new data must be inserted explicitly into both tables in order to keep the tables in sync:

With a materialized view the additional table is implicitly created and data is automatically kept in sync between both tables:

And the projection is the most transparent option because next to automatically keeping the implicitly created (and hidden) additional table in sync with data changes, ClickHouse will automatically choose the most effective table version for queries:

In the following we discuss this three options for creating and using multiple primary indexes in more detail and with real examples.

Option 1: Secondary Tables​

We are creating a new additional table where we switch the order of the key columns (compared to our original table) in the primary key:

Insert all 8.87 million rows from our original table into the additional table:

The response looks like:

And finally optimize the table:

Because we switched the order of the columns in the primary key, the inserted rows are now stored on disk in a different lexicographical order (compared to our original table) and therefore also the 1083 granules of that table are containing different values than before:

This is the resulting primary key:

That can now be used to significantly speed up the execution of our example query filtering on the URL column in order to calculate the top 10 users that most frequently clicked on the URL "http://public_search":

The response is:

Now, instead of almost doing a full table scan, ClickHouse executed that query much more effectively.

With the primary index from the original table where UserID was the first, and URL the second key column, ClickHouse used a generic exclusion search over the index marks for executing that query and that was not very effective because of the similarly high cardinality of UserID and URL.

With URL as the first column in the primary index, ClickHouse is now running binary search over the index marks. The corresponding trace log in the ClickHouse server log file confirms that:

ClickHouse selected only 39 index marks, instead of 1076 when generic exclusion search was used.

Note that the additional table is optimized for speeding up the execution of our example query filtering on URLs.

Similar to the bad performance of that query with our original table, our example query filtering on UserIDs will not run very effectively with the new additional table, because UserID is now the second key column in the primary index of that table and therefore ClickHouse will use generic exclusion search for granule selection, which is not very effective for similarly high cardinality of UserID and URL. Open the details box for specifics.

Query filtering on UserIDs now has bad performance

The response is:

Server Log:

We now have two tables. Optimized for speeding up queries filtering on UserIDs, and speeding up queries filtering on URLs, respectively:

Option 2: Materialized Views​

Create a materialized view on our existing table.

The response looks like:

Note

ClickHouse is storing the column data files (.bin), the mark files (.mrk2) and the primary index (primary.idx) of the implicitly created table in a special folder withing the ClickHouse server's data directory:

The implicitly created table (and its primary index) backing the materialized view can now be used to significantly speed up the execution of our example query filtering on the URL column:

The response is:

Because effectively the implicitly created table (and its primary index) backing the materialized view is identical to the secondary table that we created explicitly, the query is executed in the same effective way as with the explicitly created table.

The corresponding trace log in the ClickHouse server log file confirms that ClickHouse is running binary search over the index marks:

Option 3: Projections​

Create a projection on our existing table:

And materialize the projection:

Note

ClickHouse is storing the column data files (.bin), the mark files (.mrk2) and the primary index (primary.idx) of the hidden table in a special folder (marked in orange in the screenshot below) next to the source table's data files, mark files, and primary index files:

The hidden table (and its primary index) created by the projection can now be (implicitly) used to significantly speed up the execution of our example query filtering on the URL column. Note that the query is syntactically targeting the source table of the projection.

The response is:

Because effectively the hidden table (and its primary index) created by the projection is identical to the secondary table that we created explicitly, the query is executed in the same effective way as with the explicitly created table.

The corresponding trace log in the ClickHouse server log file confirms that ClickHouse is running binary search over the index marks:

Summary​

The primary index of our table with compound primary key (UserID, URL) was very useful for speeding up a query filtering on UserID. But that index is not providing significant help with speeding up a query filtering on URL, despite the URL column being part of the compound primary key.

And vice versa: The primary index of our table with compound primary key (URL, UserID) was speeding up a query filtering on URL, but didn't provide much support for a query filtering on UserID.

Because of the similarly high cardinality of the primary key columns UserID and URL, a query that filters on the second key column doesn't benefit much from the second key column being in the index.

Therefore it makes sense to remove the second key column from the primary index (resulting in less memory consumption of the index) and to use multiple primary indexes instead.

However if the key columns in a compound primary key have big differences in cardinality, then it is beneficial for queries to order the primary key columns by cardinality in ascending order.

The higher the cardinality difference between the key columns is, the more the order of those columns in the key matters. We will demonstrate that in the next section.

Ordering key columns efficiently​

In a compound primary key the order of the key columns can significantly influence both:

In order to demonstrate that, we will use a version of our web traffic sample data set where each row contains three columns that indicate whether or not the access by an internet 'user' (UserID column) to a URL (URL column) got marked as bot traffic (IsRobot column).

We will use a compound primary key containing all three aforementioned columns that could be used to speed up typical web analytics queries that calculate

We use this query for calculating the cardinalities of the three columns that we want to use as key columns in a compound primary key (note that we are using the URL table function for querying TSV data ad hoc without having to create a local table). Run this query in clickhouse client:

The response is:

We can see that there is a big difference between the cardinalities, especially between the URL and IsRobot columns, and therefore the order of these columns in a compound primary key is significant for both the efficient speed up of queries filtering on that columns and for achieving optimal compression ratios for the table's column data files.

In order to demonstrate that we are creating two table versions for our bot traffic analysis data:

Create the table hits_URL_UserID_IsRobot with the compound primary key (URL, UserID, IsRobot):

And populate it with 8.87 million rows:

This is the response:

Next, create the table hits_IsRobot_UserID_URL with the compound primary key (IsRobot, UserID, URL):

And populate it with the same 8.87 million rows that we used to populate the previous table:

The response is:

Efficient filtering on secondary key columns​

When a query is filtering on at least one column that is part of a compound key, and is the first key column, then ClickHouse is running the binary search algorithm over the key column's index marks.

When a query is filtering (only) on a column that is part of a compound key, but is not the first key column, then ClickHouse is using the generic exclusion search algorithm over the key column's index marks.

For the second case the ordering of the key columns in the compound primary key is significant for the effectiveness of the generic exclusion search algorithm.

This is a query that is filtering on the UserID column of the table where we ordered the key columns (URL, UserID, IsRobot) by cardinality in descending order:

The response is:

This is the same query on the table where we ordered the key columns (IsRobot, UserID, URL) by cardinality in ascending order:

The response is:

We can see that the query execution is significantly more effective and faster on the table where we ordered the key columns by cardinality in ascending order.

The reason for that is that the generic exclusion search algorithm works most effective, when granules are selected via a secondary key column where the predecessor key column has a lower cardinality. We illustrated that in detail in a previous section of this guide.

Optimal compression ratio of data files​

This query compares the compression ratio of the UserID column between the two tables that we created above:

This is the response:

We can see that the compression ratio for the UserID column is significantly higher for the table where we ordered the key columns (IsRobot, UserID, URL) by cardinality in ascending order.

Although in both tables exactly the same data is stored (we inserted the same 8.87 million rows into both tables), the order of the key columns in the compound primary key has a significant influence on how much disk space the compressed data in the table's column data files requires:

Having a good compression ratio for the data of a table's column on disk not only saves space on disk, but also makes queries (especially analytical ones) that require the reading of data from that column faster, as less i/o is required for moving the column's data from disk to the main memory (the operating system's file cache).

In the following we illustrate why it's beneficial for the compression ratio of a table's columns to order the primary key columns by cardinality in ascending order.

The diagram below sketches the on-disk order of rows for a primary key where the key columns are ordered by cardinality in ascending order:

We discussed that the table's row data is stored on disk ordered by primary key columns.

In the diagram above, the table's rows (their column values on disk) are first ordered by their cl value, and rows that have the same cl value are ordered by their ch value. And because the first key column cl has low cardinality, it is likely that there are rows with the same cl value. And because of that it is also likely that ch values are ordered (locally - for rows with the same cl value).

If in a column, similar data is placed close to each other, for example via sorting, then that data will be compressed better. In general, a compression algorithm benefits from the run length of data (the more data it sees the better for compression) and locality (the more similar the data is, the better the compression ratio is).

In contrast to the diagram above, the diagram below sketches the on-disk order of rows for a primary key where the key columns are ordered by cardinality in descending order:

Now the table's rows are first ordered by their ch value, and rows that have the same ch value are ordered by their cl value. But because the first key column ch has high cardinality, it is unlikely that there are rows with the same ch value. And because of that is is also unlikely that cl values are ordered (locally - for rows with the same ch value).

Therefore the cl values are most likely in random order and therefore have a bad locality and compression ration, respectively.

Summary​

For both the efficient filtering on secondary key columns in queries and the compression ratio of a table's column data files it is beneficial to order the columns in a primary key by their cardinality in ascending order.

Identifying single rows efficiently​

Although in general it is not the best use case for ClickHouse, sometimes applications built on top of ClickHouse require to identify single rows of a ClickHouse table.

An intuitive solution for that might be to use a UUID column with a unique value per row and for fast retrieval of rows to use that column as a primary key column.

For the fastest retrieval, the UUID column would need to be the first key column.

We discussed that because a ClickHouse table's row data is stored on disk ordered by primary key column(s), having a very high cardinality column (like a UUID column) in a primary key or in a compound primary key before columns with lower cardinality is detrimental for the compression ratio of other table columns.

A compromise between fastest retrieval and optimal data compression is to use a compound primary key where the UUID is the last key column, after low(er) cardinality key columns that are used to ensure a good compression ratio for some of the table's columns.

A concrete example​

One concrete example is a the plaintext paste service https://pastila.nl that Alexey Milovidov developed and blogged about.

On every change to the text-area, the data is saved automatically into a ClickHouse table row (one row per change).

And one way to identify and retrieve (a specific version of) the pasted content is to use a hash of the content as the UUID for the table row that contains the content.

The following diagram shows

Because the hash column is used as the primary key column

In order to significantly improve the compression ratio for the content column while still achieving fast retrieval of specific rows, pastila.nl is using two hashes (and a compound primary key) for identifying a specific row:

The following diagram shows

Now the rows on disk are first ordered by fingerprint, and for rows with the same fingerprint value, their hash value determines the final order.

Because data that differs only in small changes is getting the same fingerprint value, similar data is now stored on disk close to each other in the content column. And that is very good for the compression ratio of the content column, as a compression algorithm in general benefits from data locality (the more similar the data is the better the compression ratio is).

The compromise is that two fields (fingerprint and hash) are required for the retrieval of a specific row in order to optimally utilise the primary index that results from the compound PRIMARY KEY (fingerprint, hash).

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4