Zenn
🐼

TiDB Index について - How TiDB Index works and tuning? -

に公開
MySQL
index
分散システム
TiDB
tuning
tech

はじめに

TiDB は分散型アーキテクチャでありデータの実体は Key-Value Store である TiKV(RocksDB) です。従って、テーブルデータもインデックスデータも MySQL のデータの持ち方と全く異なり、加えて Index データの探索方法が全く異なります。今回は Index データの実体とデータの探索方法を理解し、Tuning に役立てるという趣旨で解説をしていきます。

TL;DR

TiDB は基本的に下記の順番でデータ探索が効率的に行われます。内部動作は後述しますが、TiDB のチューニングポイントをざっくり理解したい場合には、なるべく下記の順番でインデックス設計とSQL設計をすれば初手としては問題ないと考えています。

  1. Primary Index によるデータ検索
  2. Unique Index によるデータ検索
  3. Non-Unique Index によるデータ探索
  4. Index なしのデータ探索

TiDB の各 Index 構造と実行計画について

ここから実際のテーブルを例として内部構造と実行計画を確認していきます。今回下記のような payment テーブルをベースに説明していきます。

CREATE TABLE `payment` (
  `id` smallint NOT NULL,
  `receipt_id` smallint NOT NULL,
  `name` varchar(255) NOT NULL,
  PRIMARY KEY (`id`) /*T![clustered_index] CLUSTERED */,
  UNIQUE KEY `idx_receipt` (`receipt_id`),
  KEY `idx_name` (`name`)
)

用意したテーブルデータは下記になります。

id receipt_id name
1 423 Tom
2 311 Tom
3 98 Jack

1. Primary Index によるデータ検索

TiDB の世界において一般的な int の Primary Key の場合、Primary Key = rowID となり、テーブルデータは下記のように TiKV に格納されています。テーブルデータは下記のようなルールで Key-Value で格納されます。

Key: tablePrefix{tableID}_recordPrefixSep{rowID}
Value: [col1, col2, col3, col4]

今回のデータは Key-Value で下記のように格納されています。tableID=1 と各行の rowID を以て各々の行が格納されています。

# tableID=1, rowID=PrimaryKey=1
Key: t1_r1
Value: [1, 423, 'Tom']

# tableID=1, rowID=PrimaryKey=2
Key: t1_r2
Value: [2, 311, 'Tom']

# tableID=1, rowID=PrimaryKey=3
Key: t1_r3
Value: [3, 98, 'Jack']

Primary Key ベースの検索をした場合、「Point_Get_1」となりシンプルな実行計画になります。今回 Primary Key である id = rowID = 2 で検索しているので、tablePrefix{tableID}_recordPrefixSep{rowID} = t1_r2 を一意で検索することが可能になります。このような実行計画を「Point_Get_1」と呼び、TiDB では最も高速な実行計画になります。

mysql> explain select * from payment where id = 2;
+-------------+---------+------+---------------+---------------+
| id          | estRows | task | access object | operator info |
+-------------+---------+------+---------------+---------------+
| Point_Get_1 | 1.00    | root | table:payment | handle:2      |
+-------------+---------+------+---------------+---------------+

2. Unique Index によるデータ検索

Unique Index データは下記のように Key-Value で格納されます。Suffixの「indexedColumnsValue」は Unique Index が貼られた列の実際の値であり、この値はテーブル内で必ず一意になります。従って、tableID+indexID+indexedColumnsValue の情報があれば、対象のテーブルの1行を一意に特定することが可能なる、よって値には rowID を格納しています。

Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue
Value: rowID

今回のデータでは、Unique Index のデータが下記のように格納されています。今回、indexedColumnsValue には receipt_id の実際の値が Suffix として付与されます。

# Key: tableID=1, indexIDy=1, receipt_id=423
# Value: rowID=PrimaryKey=1
Key: t1_i1_423
Value: 1

# Key: tableID=1, indexID=1, receipt_id=311
# Value: rowID=PrimaryKey=2
Key: t1_i1_311
Value: 2

# Key: tableID=1, indexID=1, receipt_id=98
# Value: rowID=PrimaryKey=3
Key: t1_i1_98
Value: 3

Unique Key である receipt_id で検索した場合には、こちらも「Point_Get_1」となりシンプルな実行計画になります。内部的な動作としては Unique Index で rowID を特定し、その rowID を以てテーブルデータを検索するという動作になります。実行計画的には「Point_Get_1」であり Primary Key による検索と似ていますが、Unique Key の場合には、①Index 検索による rowID 取得、②rowID によるテーブルデータの検索、で TiKV へのアクセスが2回になります。但し、今回のようなシンプルなケースでは Primary Key とほぼ同等に高速です。

mysql> explain select * from payment where receipt_id = 432;
+-------------+---------+------+----------------------------------------------+---------------+
| id          | estRows | task | access object                                | operator info |
+-------------+---------+------+----------------------------------------------+---------------+
| Point_Get_1 | 1.00    | root | table:payment, index:idx_receipt(receipt_id) |               |
+-------------+---------+------+----------------------------------------------+---------------+

3. Non-Unique Index によるデータ探索

Non-Unique Index データは下記のように Key-Value で格納されます。Unique Index と比較して、rowID の suffix が追加されています。これは TiDB の Index は対象テーブルの各行と1対1で紐づく構造なのですが、Non-Unique Index の indexedColumnsValue は一意であることが保証されません。(今回のデータでは複数行に Tom が存在しています)。従って、rowID の suffix を持ち対象行を一意に特定している、という構造になります。

Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue_rowID
Value: null

また、Value には null が格納されています。null が入っている Index に意味があるのか？と思うのかもしれませんが、問題ありません。
Non-Unique Index 検索時は t1_i2_Tom の Index Key の前方一致で対象 Index を検索します。その後、前方一致で Hit した Index Key に1対1で紐づく各行を取得して結果を返します。この検索方法で Value を参照する必要はないため、Null で問題ないといった挙動になります。

文章のみだとわかりにくいと思うので下記に図示しておきます。

前提の説明が長くなりましたが、今回のデータでの Non-Unique Index のデータは下記のように格納されています。

# Key: tableID=1, indexID=2, receipt_id=423, rowID=1
Key: t1_i2_Tom_1
Value: null

# Key: tableID=1, indexID=2, receipt_id=311, rowID=2
Key: t1_i2_Tom_2
Value: null

# Key: tableID=1, indexID=2, receipt_id=311, rowID=3
Key: t1_i2_Jack_3
Value: null

Non-Unique Key である name で検索した場合、まず「IndexRangeScan_5」で上述の Index Key の前方一致の scan が実行されます。その後、合致する Index Key に含まれる rowID を使用して、対象のテーブルデータを取得するという動作になります。

この動作は Index Key を range scan するという動作上、相対的には Primary Key, Unique Key 検索よりも遅くはなりますが、特に問題ないレベルでは高速です。但し、意図せず Non-Uqniue になっている場合には、Unique Key に変更することをお勧めします。

mysql> explain select * from payment where name = 'Tom';
+-------------------------------+---------+-----------+-------------------------------------+-----------------------------------------------------+
| id                            | estRows | task      | access object                       | operator info                                       |
+-------------------------------+---------+-----------+-------------------------------------+-----------------------------------------------------+
| IndexLookUp_7                 | 0.00    | root      |                                     |                                                     |
| ├─IndexRangeScan_5(Build)     | 0.00    | cop[tikv] | table:payment, index:idx_name(name) | range:["Tom","Tom"], keep order:false, stats:pseudo |
| └─TableRowIDScan_6(Probe)     | 0.00    | cop[tikv] | table:payment                       | keep order:false, stats:pseudo                      |
+-------------------------------+---------+-----------+-------------------------------------+-----------------------------------------------------+

4. Index なしのデータ探索

こちらはいうまでもなく「TableFullScan」になります。

mysql> explain select * from payment;
+-----------------------+---------+-----------+---------------+--------------------------------+
| id                    | estRows | task      | access object | operator info                  |
+-----------------------+---------+-----------+---------------+--------------------------------+
| TableReader_5         | 3.00    | root      |               | data:TableFullScan_4           |
| └─TableFullScan_4     | 3.00    | cop[tikv] | table:payment | keep order:false, stats:pseudo |
+-----------------------+---------+-----------+---------------+--------------------------------+

まとめ

TiDB は MySQL 互換で Index も同様に作成することができますが、内部的な構造は MySQL のそれとは全く異なります。但し、考え方的にはシンプルで Primary Key, Unique Key での検索を心がけることです。この2つは速度的にはほぼほぼ変わらない印象です。次点で Non-Unique Index 利用になりますが、Non-Unique Index 利用の場合には Latency も数 msec のオーダーで変わってくる、かつ Thoughput にも影響を与える可能性があるため、可能な限り Unique Index 利用をお勧めします。

Discussion