Make fast admin check table support multi-value index
- 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
Assessment
This issue has not been assessed yet.