When you query massive data, performance may decrease because a full column scan is required to match the WHERE clause. To solve this problem, ByteHouse provides the data skipping index feature. It greatly improves query efficiency by skipping data blocks that do not contain matching values. This article will introduce the basic concepts and usage of the data skipping index.

Create a data skipping index #

You can only apply the data skipping index to the CnchMergeTree table series. These indexes involve four main parameters:

1. Index name: Used as the identifier for creating the index file. It is a necessary parameter for operations such as deleting or materializing the index and other operations.
2. Index expression: The index expression is the formula used to calculate and determine the range of values stored in the index. It can include a combination of columns, basic operators, and a specified subset of functions defined by the index type.
3. Type: The index type defines the calculation method used to skip reading and evaluating each index block.
4. Granularity: Each index block consists of a defined number of granules, determined by the granularity parameter. For example, if the primary table index granularity is 8,192 rows and the index granularity is set to 4, then each index "block" will contain 32,768 rows (8,192 rows x 4 granularity).

Data skipping index syntax example #

/*Index Name: key_i_idxIndex expression: key_iType: minmaxGranularity: 1*/
INDEX key_i_idx key_i TYPE minmax GRANULARITY 1, 

Supported data types #

Minmax

This efficient index method operates without any specific parameter. It retains the minimum and maximum values of the index expression for each block. For tuple expressions, it separately retains the minimum and maximum values of each element in the tuple. It is most effective for columns that tend to be loosely sorted by values. Among various index types, this index type is usually the most cost-effective during query execution. However, it should be noted that this index is only applicable to scalar or tuple expressions and cannot be used with expressions that generate array or map data types.

Set

This lightweight index type allows the use of a single parameter, max_size, which is the value set configured for each block. When set to 0, it can accommodate an unlimited number of distinct values within the block. The set contains all values in the block (or is empty if the number of values exceeds max_size). Although the overall cardinality is high, this index type is particularly effective for columns where values are clustered together within each granule.
The cost, performance, and effectiveness of this index depend on the cardinality within these blocks. If each block contains a large number of unique values, the cost of evaluating search conditions against a large index set becomes very high. Alternatively, if the set is empty because it exceeds the specified max_size, the index will not be applied.

Bloom filter types

A Bloom filter is a compact data structure designed to judge the validity of members in a set, with a very small possibility of false positives. In the use of skip indexes, this is not a major problem, as it only leads to reading some additional, unnecessary blocks. However, it is worth noting that potential false positives mean the index expression should be true. Otherwise, valid data may be inadvertently skipped. Caution should be exercised in designing index expressions to minimize the risk of false positives and ensure that irrelevant blocks are accurately skipped.
Bloom filters are highly effective for efficiently testing a large number of discrete values and are suitable for scenarios that generate a large number of condition expression judgments. Specifically, Bloom filter indexes can be applied to arrays, and each value in the array will be tested. This adjustment allows the validity of members in arrays or mappings to be judged, thereby enhancing the indexing functionality of such data structures.

• The dedicated tokenbf_v1 index is customized for enhanced Bloom filter functionality and requires the adjustment of three related parameters:
  • Filter size (in bytes): This parameter controls the size of the Bloom filter (in bytes). A larger filter can reduce the likelihood of false positives, at the cost of increased storage space.
  • Number of hash functions: The number of hash functions applied to the Bloom filter. Using more hash functions helps reduce false positives.
  • Seed for hash functions: The seed used to generate the hash functions for the Bloom filter.
  • This index is only applicable to Data of the String and FixedString Type. The input Expression is split into sequences of characters separated by non-alphanumeric characters. For example, the Column Value This is a candidate for a "full text" search will be split into This is a candidate for full text search.
  • This index is used for searching words and other Values in long strings using LIKE, EQUALS, in, hasToken(), and similar operations. For example, one possible purpose is to search for a small number of class names or line numbers in unstructured application log line Columns.
• A more specialized ngrambf_v1. The Function of this index is the same as tokenbf_v1. An additional Param is required before the Bloom filter settings, which is the size of the ngram to be indexed. An ngram is any String of length n. For example, if n is 4, A short string will be split into A sh, shor, hort, ort s, or st, r str, stri, trin, ring. This index is also useful for text Search, especially for languages without word boundaries, such as Chinese.
• Optionally, the false_positive Param can be used to specify the probability of receiving a false positive response from this filter, with a Value between 0 and 1. The Default is 0.025. Supported Data types include: Int*, UInt*, Float*, Enum, Date, DateTime, String, FixedString, Array, LowCardinality, Nullable, UUID.
  Syntax:

  bloom_filter([false_positive])
  

Usage example #

Load the Data set into ByteHouse #

DROP DATABASE IF EXISTS test_si;
CREATE DATABASE test_si;

--Create a table for loading the numbers_source.csv dataset
CREATE TABLE test_si.numbers
(
    `number` UInt64
)
ENGINE = CnchMergeTree
ORDER BY number;

Download the following File and use the Data loading feature to load the Data set into the test_si.numbers Table.

numbers_source.csv

Unknown size

Create a Table without an index #

USE test_si;

--Create table
CREATE TABLE test_skipindex
(
    `id` UInt64,
    `key_i` UInt64,
    `p_date` Date
)
ENGINE = CnchMergeTree
PARTITION BY p_date
ORDER BY id;

--Insert the test dataset into the table
INSERT INTO test_skipindex SELECT
    number,
    number,
    today()
FROM test_si.numbers
LIMIT 1000000;

--Query data to check if it was inserted successfully
SELECT sum(id) FROM test_skipindex WHERE key_i = 1;

If we Run the following command:

--Simple query: From the test_skipindex table, filter all rows where the key_i column value is 200 or 700
SELECT * FROM `test_skipindex` WHERE key_i IN (200, 700);

As a result, it shows that 1 million rows of Data were processed without an index.

Add an index #

Add an index to the new Table

DROP TABLE if EXISTS test_si.test_skipindex;

USE test_si;

--Add index when creating the table
CREATE TABLE test_skipindex
(
    `id` UInt64,
    `key_i` UInt64,
    `p_date` Date,
    INDEX key_i_idx key_i TYPE minmax GRANULARITY 1
)
ENGINE = CnchMergeTree
PARTITION BY p_date
ORDER BY id
--index_granularity default value is 8192
SETTINGS index_granularity = 8192;

--Insert the test dataset into the table
INSERT INTO test_skipindex SELECT
    number,
    number,
    today()
FROM test_si.numbers
LIMIT 1000000;

--Query data to check if it was inserted successfully
SELECT sum(id) FROM test_skipindex WHERE key_i = 1;

Run the same command as above,

--Simple query: From the test_skipindex table, filter all rows where the key_i column value is 200 or 700
SELECT * FROM `test_skipindex` WHERE key_i IN (200, 700); 

As a result, it shows that only 8,192 rows of Data were processed when using the index, and the execution was faster.

Add an index to subsequent Data in an existing Table

DROP TABLE if EXISTS test_si.test_skipindex;
USE test_si;

--Create table
CREATE TABLE test_skipindex
(
    `id` UInt64,
    `key_i` UInt64,
    `p_date` Date
)
ENGINE = CnchMergeTree
PARTITION BY p_date
ORDER BY id;

--Insert the test dataset into the table
INSERT INTO test_skipindex SELECT
    number,
    number,
    today()
FROM test_si.numbers
LIMIT 1000000;

--Add index after creating the table
ALTER TABLE test_si.test_skipindex ADD index key_i_idx key_i TYPE minmax GRANULARITY 1;

--Query whether data has been successfully inserted
SELECT sum(id) FROM test_skipindex WHERE key_i = 1;

If we run the same command, the result will be processing one million rows.

This is because the data added before creating the index is considered historical data. For historical data, refer to the following steps to build the index.

Add an index to historical data

To build an index for historical data, you need to use the MATERIALIZE INDEX command. If you only use the ALTER TABLE...ADD command without running MATERIALIZE INDEX, the index will only be generated for newly written data.

--Execute the following additional code block
ALTER TABLE test_si.test_skipindex MATERIALIZE INDEX key_i_idx;

Query results indicate that the historical data index was added successfully. The query only processes 8192 rows, and it is faster.

Add an index to historical data partitions

By default, MATERIALIZE INDEX will generate indexes for all historical data. To generate an index for a specific historical data partition, use the IN PARTITION clause together with the MATERIALIZE INDEX command. This will generate the index only for the specified partition.

DROP TABLE if EXISTS test_si.test_skipindex;
USE test_si; 
--Create a table
CREATE TABLE test_skipindex
(
    `id` UInt64,
    `key_i` UInt64,
    `p_date` Date
)
ENGINE = CnchMergeTree
PARTITION BY p_date
ORDER BY id;

--Insert the test dataset into the table
INSERT INTO test_skipindex SELECT
    number,
    number,
    today()
FROM test_si.numbers
LIMIT 1000000;

--Insert the test dataset into the table
INSERT INTO test_skipindex SELECT
    number,
    number,
    today()-1
FROM test_si.numbers
LIMIT 1000000;

ALTER TABLE test_si.test_skipindex ADD index key_i_idx key_i TYPE minmax GRANULARITY 1;

--Assuming the previous day's date is 20230927, then generate index only for the 20230927 date partition
ALTER TABLE test_si.test_skipindex MATERIALIZE INDEX key_i_idx IN PARTITION '20230927';

--Query whether data has been successfully inserted
SELECT sum(id) FROM test_skipindex WHERE key_i = 1 AND p_date = today()-1;

--Query whether data has been successfully inserted
SELECT sum(id) FROM test_skipindex WHERE key_i = 1 AND p_date = today();

If we run the simple query shown below, we can see that an index has been generated for the historical data in partition 20230927 [today() - 1].

No index is generated for historical data in unspecified partitions.

Delete index #

ALTER TABLE test_si.test_skipindex DROP INDEX key_i_idx;

SHOW CREATE TABLE test_skipindex;

SELECT sum(id) FROM test_skipindex WHERE key_i = 1;

Usage suggestions #

Generally, when the amount of data is small, the cost of building an index is not high. However, if you want to build an index for all historical data and the data volume is very large, directly using MATERIALIZE INDEX to add an index for all historical data may put some load on the cluster. In this case, we recommend using IN PARTITION to build indexes by partition.