pingcap / pingcap/tidb

Make fast admin check table support multi-value index

Open
#60,649 0 comments 0 reactions 0 assignees View on GitHub
type/enhancement
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Enhancement

https://github.com/pingcap/tidb/pull/43694 has support fast table check, but we need to further extend it to support multi-value index.

To help the code review, I will add some simple introduction here.

## Core Concept

Fast data consistency checks are currently implemented using SQL queries. Below is a simple example to illustrate the rationale:

```SQL
CREATE TABLE t(i INT PRIMARY KEY, j CHAR(120), KEY k(j));

-- Table checksum via table scan:
SELECT BIT_XOR(CRC32(CONCAT(i, j))) FROM t USE INDEX();

-- Index checksum via index scan:
SELECT BIT_XOR(CRC32(CONCAT(i, j))) FROM t USE INDEX(k);
```

However, this method becomes problematic for **multi-value indexes (MVIndex)** when supporting checksum calculations for JSON array elements in both table scans and index scans.

### Challenge with Multi-Value Indexes

The core principle of fast consistency checks is calculating **per-record** checksums and aggregating them via BIT_XOR. Then results from index and table scans are then compared for validation.

However, this approach is impractical for MVIndexes because **deriving a per-record checksum from the index side** is quite difficult. Consider this example:

``` SQL
CREATE TABLE t(
i INT PRIMARY KEY,
j JSON,
KEY mvi((CAST(j AS UNSIGNED ARRAY)))
);

INSERT INTO t VALUES (1, "[5, 7]"), (4, "[0, 8]");
```

`mvi` will store four index entries: `(0, 4)`, `(5, 1)`, `(7, 1)`, `(8, 4)`. To reconstruct per-record checksums from these entries, we need to use `GROUP BY` on the primary key. And it's an expensive operation for large datasets because it may consume too many memories.

Additionally, it's also impossible to decompose JSON arrays into distinct records for table scan. So we need an alternative solution for MVIndex consistency checks.

### Proposed Solution

We propose shifting from per-record to per-index-entry checksums using operations that satisfy the distributive property.

We propose changing **per-record** checksums to **per-index-entry** checksums using operations that satisfy the distributive property. This property enables equivalent results from both index and table scans through algebraic equivalence:

$$
f(x, g(y, z)) = g(f(x, z), f(y, z))
$$

> Although this is not a formal definition, but I think you can understand.

Only a few operations comply with the this law, such as the well-known distributed property of multiplication, which will be used here. Let's still take the same table as example:

```SQL
CREATE TABLE t(i INT PRIMARY KEY, j JSON, KEY mvi((CAST(j AS UNSIGNED ARRAY)));
INSERT INTO t VALUES (1, "[5, 7]"), (4, "[0, 8]");
```

From index side, we can calculate checksums for each index entry (four entries in this case), and final result is the sum of these values:

```
Index Checksum =
[CRC32(0) × CRC32(4)] +
[CRC32(5) × CRC32(1)] +
[CRC32(7) × CRC32(1)] +
[CRC32(8) × CRC32(4)]
```

From table side, we can also get the result by:
```
Table Checksum =
CRC32(4) × [CRC32(0) + CRC32(8)] +
CRC32(1) × [CRC32(5) + CRC32(7)]
```

The only things we need to consider here is overflow handling.

### New JSON function

Here we implemented a new function `JSON_SUM_CRC32` to calculate the following CRC32 value, whose grammar is almost the same as `CAST`:

``` SQL
mysql> CREATE TABLE t(i INT PRIMARY KEY, j JSON, INDEX mvi((CAST(j AS UNSIGNED ARRAY))));
mysql> INSERT INTO t VALUES(2, "[4, 2, 1]");
mysql> SELECT JSON_SUM_CRC32(j AS UNSIGNED ARRAY) from t;
+-------------------------------------+
| json_sum_crc32(j as unsigned array) |
+-------------------------------------+
| 6751308028 |
+-------------------------------------+
mysql> SELECT CRC32(4)+CRC32(2)+CRC32(1) as sum;
+------------+
| sum |
+------------+
| 6751308028 |
+------------+
```

The subsequent process is not much different from normal index, so I won't elaborate it here.

## PR

- [x] Add new function for table side https://github.com/pingcap/tidb/pull/60728
- [ ] Support fast table check for MV Index https://github.com/pingcap/tidb/pull/60650

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.