クエリパワーを解き放つ：TiDBにおける高度なマルチカラムインデックスの最適化

今日のデータ駆動型の世界では、大規模なデータセットに対して複雑なクエリを効率的に処理することが、アプリケーションの応答性とパフォーマンスを維持するために不可欠です。大規模で高負荷な環境を管理するように設計された分散SQLデータベースであるTiDBにとって、データへのアクセスパスの最適化はスムーズで効率的なクエリを提供するために不可欠です。このブログでは、マルチカラムインデックスを最適化するTiDBの高度なアプローチについて掘り下げます。これは、分散クラスタ間でのデータ検索の速度と精度を大幅に向上させる強力な機能です。

TiDBのクエリオプティマイザは、マルチカラムインデックスを活用してデータを効果的にフィルタリングし、MySQLのような従来のデータベースでは処理しきれなかった複雑なクエリ条件を効率的に処理します。ここでは、マルチカラムインデックスがどのように機能するのか、なぜ重要なのか、そしてTiDBの最適化が複雑な検索条件を効率的なアクセスパスにどのように変換するのかを説明します。これにより、レスポンス速度の向上、テーブルスキャンの最小化、そして大規模な環境においてもスムーズなパフォーマンスが実現されます。

これらの最適化がなければ、大規模なTiDBデータベースのクエリパフォーマンスは急速に低下する可能性があります。テーブルのフルスキャンや不十分なフィルタリングは、ミリ秒を数分にまで引き延ばすことがあります。さらに、メモリ使用量が過剰になると、特に制約の多い環境ではメモリ不足 (OOM) エラーにつながる可能性があります。TiDBの的を絞ったアプローチは、関連するデータのみにアクセスすることを保証します。これにより、最も複雑なクエリであっても、レイテンシを低く保ち、メモリ使用量を効率的に抑えることができます。TiDBがどのようにこれを実現しているのか、詳しく見ていきましょう。

背景：マルチカラムインデックス

インデックスは、テーブル内のすべての行をスキャンする必要性を回避することで、クエリのパフォーマンスを向上させる強力なツールです。以下のように定義された賃貸物件テーブルを例にしてみましょう。この例では、各物件には一意のID、都市、寝室数、家賃、入居可能日が含まれます：

CREATE TABLE listings (
    listing_id INT PRIMARY KEY AUTO_INCREMENT,
    city VARCHAR(100) NOT NULL,
    bedrooms INT NOT NULL,
    price DECIMAL(10, 2) NOT NULL,
    availability_date DATE NOT NULL
);

このテーブルには全米で2,000万件の賃貸物件があるとします。もし、家賃が2,000ドル未満のすべての賃貸物件を探したい場合、price (家賃) カラムにインデックスを追加することができます。このインデックスにより、オプティマイザは行をフィルタリングし、レンジ [ -inf, 2000.00 ) のみをスキャンすることができます。これにより、検索対象が約1400万行に絞られます (賃貸物件の70％が$2,000以上であると仮定した場合)。クエリの実行計画では、TiDBは家賃に対してインデックスレンジスキャンを実行します。これにより、フルテーブルスキャンの必要性が削減され、効率が向上します。

"Q1" 
explain FORMAT=BRIEF
    SELECT * FROM listings WHERE price < 2000;
-----+------------------------------------------------------+--------------------------
| id  task                | access object                        | operator info   
+-----------------------------+---------+-----------+-----------------------------------
| IndexLookUp             | root                                 | 
| ├─IndexRangeScan(Build) | table:listings,index:price_idx(price)| range:[-inf,2000.00) 
| └─TableRowIDScan(Probe) | table:listings                       | 
+-----------------------------+---------+-----------+-----------------------------------

このフィルターはパフォーマンスを改善しますが、それでも大量の行が返される可能性があります。これは、より具体的な物件を探しているユーザーには理想的ではありません。例えば、都市、寝室数、家賃の上限などのフィルターを追加することで、結果を大幅に絞り込むことができます。例えば、「サンフランシスコで、2ベッドルームで2,000ドル未満の物件」を検索するクエリは、非常に有用であり、おそらく数十行のみが返されるでしょう。

このクエリを最適化するためには、都市、寝室数、家賃についてマルチカラムインデックスを作成します：

CREATE INDEX idx_city_bedrooms_price ON listings (city, bedrooms, price);

SQLにおけるマルチカラムインデックスは、辞書順 (lexicographically) で順序付けられています。つまり、最初に都市、次にその都市内の寝室数、最後に都市と寝室数の組み合わせごとに家賃でソートされます。この順序付けにより、TiDBは各条件に基づいて効率的に行をアクセスできます：

1. 都市を主なフィルターとして絞り込む。
2. オプションで、その都市内の寝室数でフィルタリングする。
3. オプションで、都市と寝室数の組み合わせ内で家賃によるフィルタリングを行う。

サンプルデータ

マルチカラムインデックスがどのように検索結果を絞り込むかを説明するために、サンプルデータセットを見てみましょう：

都市	寝室数	家賃
サンディエゴ	1	1000
サンディエゴ	1	1500
サンディエゴ	2	1000
サンディエゴ	2	2500
サンディエゴ	3	1000
サンディエゴ	3	2500
サンフランシスコ	1	1000
サンフランシスコ	1	1500
サンフランシスコ	2	1000
サンフランシスコ	2	1500
サンフランシスコ	3	2500
サンフランシスコ	3	3000

最適化されたクエリと結果

マルチカラムインデックスを使用することで、TiDBは効率的に範囲を絞り込み、サンフランシスコの2ベッドルームで家賃が2,000ドル以下の物件を見つけることができます：

"Q2"

EXPLAIN FORMAT=BRIEF 
    SELECT * FROM listings 
    WHERE city = 'San Francisco' AND bedrooms = 2 AND price < 2000;

"Q2" plan. 
explain format=brief 
    select * from listings 
    where city = 'San Francisco' and bedrooms = 2 and price < 2000;
-----+------------------------------------------------------+--------------------------
| id  task                | access object                | operator info   
+-----------------------------+---------+-----------+-----------------------------------
| IndexLookUp             | root                         | 
| ├─IndexRangeScan(Build) | table:listings,              | range:
                          | index:idx_city_bedrooms_price| ["San Francisco" 2 -inf,
                          | (city, bedrooms, price)      | "San Francisco" 2 2000.00)
| └─TableRowIDScan(Probe) | table:listings               | 
+-----------------------------+---------+-----------+-----------------------------------

このクエリは、サンプルデータから以下のフィルタリングされた結果を返します：

都市	寝室数	家賃
サンフランシスコ	2	1000
サンフランシスコ	2	1500

マルチカラムインデックスを使用することで、TiDBは不要な行の読み込みを削減し、クエリのパフォーマンスを大幅に向上させます。

インデックスレンジの生成

TiDBオプティマイザには、強力なレンジ生成コンポーネントが含まれています。これは、クエリの条件と関連するインデックスカラムを受け取り、テーブルアクセスのための効率的なインデックスレンジを生成するように設計されています。この算出されたレンジは、TiDBのテーブルアクセスコンポーネントに供給され、テーブルへのアクセス方法が最もリソース効率の良い方法で決定されます。

クエリ内の各テーブルに対して、テーブルアクセスコンポーネントは、適用可能なすべてのインデックスを評価し、最適なアクセス方法 (フルテーブルスキャンかインデックススキャンか) を識別します。関連する各インデックスのレンジを計算し、アクセスコストを評価し、最もコストの低いパスを選択します。このプロセスでは、レンジ生成とコスト評価のサブシステムを組み合わせて、パフォーマンスとリソース使用量のバランスをとりながら、最も効率的なデータ取得方法を見つけます。

下図は、TiDBのテーブルアクセスロジックの中で、レンジ生成とコスト評価がどのように連携し、最適なデータ取得を実現しているかを示しています。

マルチカラムフィルターは、前述の基本的な例よりも複雑になることがよくあります。AND条件、OR条件、あるいはその両方の組み合わせを含むこともあります。TiDBのレンジ生成サブシステムは、このようなケースを効率的に処理し、最も選択的な (つまり、最も効果的な) インデックスレンジを生成するように設計されています。

一般的に、このサブシステムは、OR条件から生成されたレンジに対してUNION演算を適用し、AND条件から生成されたレンジにはINTERSECT演算を適用します。このアプローチにより、複雑なフィルタリングロジックであっても、TiDBは可能な限り正確にデータをフィルタリングすることができます。

マルチカラムインデックスにおける論理和条件 (OR条件)

クエリにOR条件が含まれている場合 (これを「論理和述語 (disjunctive predicates)」と言います)、オプティマイザは各条件を個別に処理し、OR条件のそれぞれの部分に対してレンジを作成します。これらのレンジが重複している場合、オプティマイザはそれらを1つの連続したレンジに統合します。重複していない場合、それぞれのレンジは別々のレンジとして残り、両方ともインデックススキャンで使用することができます。

例1：重複するレンジ

ニューヨークで2ベッドルームの物件を探すクエリを考えてみましょう。家賃が次の2つの重複する範囲のいずれかに該当する場合です：

• 家賃が1,000ドルから2,000ドルの間
• 家賃が1,500ドルから2,500ドルの間

この場合、2つの範囲は重複しているため、オプティマイザはそれらを1つの範囲、1,000ドルから2,500ドルに統合します。以下にクエリとその実行計画を示します：

"Q3"
EXPLAIN FORMAT=BRIEF 
    SELECT * FROM listings 
    WHERE (city = 'New York' AND bedrooms = 2 AND price >= 1000 AND price < 2000) 
       OR (city = 'New York' AND bedrooms = 2 AND price >= 1500 AND price < 2500);
 -----+------------------------------------------------------+--------------------------
| id  task                | access object                | operator info   
+-----------------------------+---------+-----------+-----------------------------------
| IndexLookUp             | root                         | 
| ├─IndexRangeScan(Build) | table:listings,              | range:
                          | index:idx_city_bedrooms_price| ["New York" 2 1000.00,
                          | (city, bedrooms, price)      |  "New York" 2 2500.00)
| └─TableRowIDScan(Probe) | table:listings               | 
+-----------------------------+---------+-----------+-----------------------------------

例2：重複しないレンジ

別のシナリオとして、サンフランシスコまたはサンディエゴの手頃な価格の1ベッドルームの物件を探すクエリを想像してください。この場合、OR条件は異なる都市に対して2つの異なるレンジを指定します：

• サンフランシスコの物件、1ベッドルーム、家賃$1,500～$2,500
• サンディエゴの物件、1ベッドルーム、家賃は$1,000から$1,500の間

これらのレンジは重複しないため、実行計画ではそれぞれ別々のレンジとして扱われ、各都市に独自のインデックスレンジが適用されます：

"Q4"

EXPLAIN FORMAT=BRIEF 
    SELECT * FROM listings 
    WHERE
        (city = 'San Francisco' AND bedrooms = 1 AND price >= 1500 AND price < 2500) 
     OR (city = 'San Diego' AND bedrooms = 1 AND price >= 1000 AND price < 1500);
 -----+------------------------------------------------------+--------------------------
| id  task                | access object                | operator info   
+-----------------------------+---------+-----------+-----------------------------------
| IndexLookUp             | root                         | 
| ├─IndexRangeScan(Build) | table:listings,              | range:
                          | index:idx_city_bedrooms_price| ["San Francisco" 1 1500.00,
                          | (city, bedrooms, price)      |  "San Francisco" 1 2500.00) 
                          |                              | ["San Diego" 1 1000.00,
                          |                              |   "San Diego" 1 1500.00)
| └─TableRowIDScan(Probe) | table:listings               | 
+-----------------------------+---------+-----------+-----------------------------------

重複に基づいてマージされたレンジまたは別々のレンジを作成することで、オプティマイザはOR条件に対してインデックスを効率的に利用でき、不要なスキャンを避けてクエリのパフォーマンスを向上させることができます。

マルチカラムインデックスにおける論理積条件 (AND条件)

AND条件 (論理積条件) を含むクエリにおいて、TiDBのオプティマイザは各条件に対してレンジを作成します。そして、インデックスアクセスのために正確な結果を得るために、これらのレンジの重複 (交差部分) を見つけます。各条件が1つのレンジのみの場合は単純ですが、条件の中に複数のレンジが含まれている場合は、より複雑になります。そのような場合、TiDBはこれらのレンジを組み合わせて、最も選択的で効率的な結果を生成します。

例

以下のように定義されたテーブルt1を考えてみましょう：

CREATE TABLE t1 (
    a1 INT,
    b1 INT,
    c1 INT, 
    KEY iab (a1,b1)
);

次のような条件のクエリーがあるとします：

• (a1, b1) > (1, 10) AND (a1, b1) < (10, 20)

このクエリでは複数の列を比較するため、処理に2つのステップが必要です：

ステップ1：式の変換：

TiDBのオプティマイザは、この複雑な条件をよりシンプルな条件に分解します。

• (a1, b1) > (1, 10)を (a1 > 1) OR (a1 = 1 AND b1 > 10)に変換, つまり、a1が1より大きい場合、またはa1がちょうど1でb1が10より大きい場合をすべて含みます。
• (a1, b1) < (10, 20)を(a1 < 10) OR (a1 = 10 AND b1 < 20)に変換, a1が10未満、またはa1がちょうど10でb1が20未満の場合をカバーします。

これらの式はANDで結合されます：

((a1 > 1) OR (a1 = 1 AND b1 > 10)) AND ((a1 < 10) OR (a1 = 10 AND b1 < 20))

ステップ2：レンジの生成と結合：

条件を分解した後、TiDBのオプティマイザは各部分のレンジを生成し、それらを結合します。この例では、次のように算出します：

• (a1, b1) > (1, 10)の場合：a1 > 1 aの場合には (1, +inf] のようなレンジを作成し、 a1 = 1 かつb1 > 10の場合には(1, 10, 1, +inf] のようなレンジを作成します。
• (a1, b1) < (10, 20)の場合：a1 < 10 の場合には [-inf, 10) のようなレンジを作成し、a1 = 10 かつ b1 < 20の場合には [10, -inf, 10, 20) のようなレンジを作成します。

最終的な結果は、これらを組み合わせて最適化されたレンジです：(1, 10, 1, +inf] UNION (1, 10) UNION [10, -inf, 10, 20)

クエリプランの例

こちらが、生成されたレンジを示すクエリプランです：

"Q5"
EXPLAIN FORMAT=BRIEF 
    SELECT * FROM t1 
    WHERE (a1, b1) > (1, 10) AND (a1, b1) < (10, 20);
 -----+------------------------------------------------------+--------------------------
| id  task                | access object                | operator info   
+-----------------------------+---------+-----------+-----------------------------------
| IndexLookUp             | root                       | 
| ├─IndexRangeScan(Build) | table:t1,index:iab(a1, b1) | range:(1 10,1 +inf],
                          |                            |       (1,10)
                          |                            |       [10 -inf,10 20)
| └─TableRowIDScan(Probe) | table:t1                   | 
+-----------------------------+---------+-----------+-----------------------------------

この例では、テーブルには約5億行のデータがあります。しかし、この最適化により、TiDBはアクセス対象を約4,000行 (全データのわずか0.0008%) に絞り込むことができます。この絞り込みにより、最適化なしでは2分以上かかっていたクエリの待機時間が、数ミリ秒に劇的に短縮されました。

MySQLではこのような条件に対してフルテーブルスキャンが必要ですが、TiDBのオプティマイザはこれらの生成されたレンジを活用することで、複雑な行の式を効率的に処理することができます。

結論

TiDBのオプティマイザは、マルチカラムインデックスと進化したなレンジ生成を使用して、複雑なSQLクエリのデータアクセスコストを大幅に削減します。論理積条件 (AND) と論理和条件 (OR) の両方を効果的に処理することで、TiDBは行ベースの式を最適なアクセスパスに変換し、クエリ時間を短縮してパフォーマンスを向上させます。MySQLとは異なり、TiDBはマルチカラムインデックス対してユニオンおよびインターセクション操作をサポートし、複雑なフィルタを効率的に処理することができます。実際に使用してみると、この最適化により、TiDBはわずか数ミリ秒でクエリを完了することができ、最適化なしでは2分以上かかるのに比べて、レイテンシを大幅に削減することが示されています。

MySQLとTiDBのアーキテクチャのさらなる違いや、スケーラビリティ、信頼性、トランザクションと分析のハイブリッドなワークロードにおいてなぜこれが重要なのかを理解するために、ぜひ私たちの比較分析ホワイトペーパーをご覧ください。