本記事はこちらのブログを参考にしています。
翻訳にはアリババクラウドのModelStudio(Qwen)を使用しております。

INクエリの最適化と実行計画管理について

方武（Fangwu）による

概要

ユーザーの視点から見ると、INクエリには以下の利点があります：

理解しやすい: INクエリ文はシンプルで直感的であり、理解や記述が容易です。
効率的: 一連の離散値を処理する際、INクエリは複数のOR条件を使用するよりも効率的です。

しかし、INクエリを使用する際に、しばしばクエリのパフォーマンス問題に遭遇します。IN式のパラメータリストがある一定の閾値を超えると、データベースの処理効率が急激に低下する傾向があります。データベースの視点から見ると、INクエリにおける最大の課題は動的なパラメータリストによって引き起こされる不安定性です。例えば、MySQLインスタンスでは、過剰な数のINパラメータがrange_optimizer_max_mem_sizeに基づいてフルテーブルスキャンを引き起こす可能性があります。この閾値を超えると、パフォーマンスが急激に低下します。

PolarDB-Xや他の分散型オンラインビジネスデータベースにおいても、INクエリは以下の課題を提起します：

オプティマイザがコストを計算する際、大量のパラメータが追加のコスト計算オーバーヘッドを発生させます。
INの動的なパラメータリストは様々なSQLテンプレートを生成し、実行計画キャッシュを簡単に埋め尽くしてしまいます。
分散シナリオでは、大量のINパラメータを事前計算によって剪定（プルーニング）する必要があります。これにより、DNでの不要な計算オーバーヘッドを回避できます。

注意: この記事では、INサブクエリを含まないINクエリについて説明します。スペースの制約上、本記事ではPolarDB-XにおけるINクエリの実行計画管理および実行の最適化に焦点を当てています。

INクエリと実行計画管理

異なるデータベースにはさまざまな実行計画管理戦略があります。PolarDB-Xの実行計画タイプはPostgreSQLと似ており、カスタムプランとジェネリックプランが含まれます。準備されたステートメントは、ジェネリックプランまたはカスタムプランのどちらかで実行できます。ジェネリックプランはすべての実行で同じですが、カスタムプランはその呼び出しで与えられたパラメータ値を使用して特定の実行用に生成されます。ジェネリックプランを使用することで計画オーバーヘッドを回避できますが、状況によってはカスタムプランの方が実行効率が高くなる場合があります。これは、オプティマイザがパラメータ値の知識を利用して最適化を行うことができるためです。（もちろん、準備されたステートメントにパラメータがない場合、この議論は無意味で、常にジェネリックプランが使用されます。）

引用元: PostgreSQLドキュメント: https://www.postgresql.org/docs/current/sql-prepare.html

ただし、実行計画のキャッシュ戦略に関して、多くのPolarDB-X顧客はオンラインビジネスでより複雑なSQLテンプレートを使用しています。一方で、データはクラスター内の異なるパーティションに分割されますが、これがオプティマイザが直面する課題を大幅に増加させています。そのため、PostgreSQLのより保守的な実行計画管理戦略とは異なり、PolarDB-Xはできるだけキャッシュされた実行計画を再利用して高いオプティマイザオーバーヘッドを避ける傾向があります。

IN式のパラメータリストは大きな課題を提示します。異なるパラメータリストは異なる実行計画を指すため、プランキャッシュは簡単に満杯になってしまいます。特にアドホッククエリのシナリオでは、異なるINクエリパラメータリストが膨大なSQLテンプレートを簡単に生成します。sql
SELECT order_info FROM orders WHERE item_id IN(?) AND seller_id IN(?) ORDER BY gmt;

上記の簡単な注文クエリリクエストを考えると、もしitem_idとseller_idの両方が10項目ある場合、このSQLは最大で100のSQLテンプレートを生成し、その実行計画は完全に類似しています。これらの実行計画の数を減らすために、PolarDB-XパーサーはIN式のパラメータリストをカプセル化します。IN式内にいくつ動的パラメータがあろうとも、それらはすべてRawStringオブジェクトにカプセル化されます。オプティマイザはRawStringパラメータリストに対するコスト計算に対応するよう調整されています。実行部では、IN式のパラメータリストはパッケージ化され、DNに送信されて計算されます。

このメリットは、INクエリのSQLテンプレートが1つの実行計画に収束できることです。これにより、実行計画のキャッシュ圧力が大幅に軽減されます。PolarDB-Xは現在、高並列INクエリに対して動的なランダムアクセスをサポートしています。

特徴

PolarDB-Xでは、PlanCacheおよびSPMビューを通じて実行計画のキャッシュ状態を観察できます。ここではPlanCacheを通じてキャッシュ状態をデモします。まず、PolarDB-X 2.0インスタンスを購入し、次のSQLステートメントを使用して環境を作成します：sql
// データベースとテーブルの作成
CREATE DATABASE test MODE=AUTO;
use test
CREATE TABLE tb_h(
id bigint not null auto_increment,
bid int,
name varchar(30),
birthday datetime not null,
primary key(id)
)
PARTITION BY HASH(id)
PARTITIONS 8;

次のSQLステートメントを実行します：sql
select * from tb_h where id in(1,2,3,4,5);

plan_cacheビューを通じてプランのキャッシュ状態を観察します：sql
mysql> select * from information_schema.plan_cache where sql like %tb_h% limit 10\G
*************************** 1. row ***************************
COMPUTE_NODE: 10.2.100.161:3021
SCHEMA_NAME: test
TABLE_NAMES: tb_h
ID: 1d4daf02
HIT_COUNT: 0
SQL: SELECT *
FROM tb_h
WHERE id IN (?) TYPE_DIGEST: 1926227933676693664
PLAN:
Gather
LogicalView(tableNames=[[tb_h]])

PARAMETER: [[1,2,3,4,5]]
1 row in set (0.01 sec)

ビューからわかるように、IN式の動的パラメータリストは1つに削減されています。SQLテンプレートが他に変更がない場合、異なるINパラメータリストを持つクエリが何度実行されても、同じ実行計画が再利用されます。sql
mysql> explain select * from tb_h where id in(4566);
+----------------------------------------------------------------------------------------------------------------------------------------------+
| LOGICAL EXECUTIONPLAN |
+----------------------------------------------------------------------------------------------------------------------------------------------+
| Gather(concurrent=true) |
| LogicalView(tables=tb_h[p8], sql=SELECT id, bid, name, birthday FROM tb_h AS tb_h FORCE INDEX(PRIMARY) WHERE (id IN(?))) |
| HitCache:true |
| Source:PLAN_CACHE |
| TemplateId: 1d4daf02 |
+----------------------------------------------------------------------------------------------------------------------------------------------+
5 rows in set (0.00 sec)

mysql> explain select * from tb_h where id in(45, 66);
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| LOGICAL EXECUTIONPLAN |
+

分配法則 p∧(q∨r)≡(p∧q)∨(p∧r)

全体の式によって計算されたシャード集合を K とし、各 Pn 部分句によって計算されたシャード集合を Kn とする場合、OR の関係に基づいて以下を得ることができます。

K=K1 ∪ K2 ∪ K3 ∪ ... ∪ Kn

和集合 K は、それぞれの Kn を個別に計算することによって取得されます。このプロセスにおいて、各 Pn 節に対応するシャードが記録されている場合、現在の連言節（conjunction clause）における各シャードとその対応するパラメータリストを取得できます。

各連言節について、シャードと IN パラメータリスト間の一連の関係を得ることができます。連言節が OR の関係にあるため、これらの集合を各シャードごとにマージして、シャードとパラメータリスト間の最終的な関係を得ることができます。この場合、パラメータリストは枝刈りされます。! および IN は連言節で NOT IN に結合され、NOT IN はフルテーブルスキャンとして計算されます。複数の IN 式が含まれる場合、デカルト積から生じるすべての組み合わせを考慮する必要があります。過度に大きなデカルト積は計算プロセスが長くなる可能性があるため、以下の最適化が行われます：

計算の最大数を設定します。IN 式は最も長いものからデカルト積計算に含められます。最大数を超えた場合、残りの IN 式はまとめて扱われ、それ以上枝刈りされません。
単一の計算で全シャードがカバーされる場合、その式にはシャードの枝刈り能力がないと見なされ、枝刈りを直接終了できます。

特徴

テーブルの作成sql

CREATE TABLE hash_tbl_todays_AutoPruning (
id bigint(20) NOT NULL AUTO_INCREMENT,
bid int(11) DEFAULT NULL,
name varchar(30) DEFAULT NULL,
birthday datetime NOT NULL,
PRIMARY KEY (id),
KEY auto_shard_key_birthday USING BTREE (birthday)
) ENGINE = InnoDB DEFAULT CHARSET = utf8mb4
PARTITION BY HASH(TO_DAYS(birthday))
PARTITIONS 8 ;

EXPLAIN_PRUNING_DETAIL を有効にして IN 枝刈りの効果を観察します。sql

SET GLOBAL EXPLAIN_PRUNING_DETAIL=TRUE;

枝刈り情報の説明sql

mysql> explain select * from hash_tbl_todays_AutoPruning where birthday in (2024-09-08, 2024-09-10, 2024-10-08, 2023-12-30) and bid>100;
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| LOGICAL EXECUTIONPLAN |
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Gather(concurrent=true) |
| LogicalView(tables=hash_tbl_todays_AutoPruning[p1,p4,p7], shardCount=3, sql=SELECT id, bid, name, birthday FROM hash_tbl_todays_AutoPruning AS hash_tbl_todays_AutoPruning WHERE ((birthday IN(?)) AND (bid > ? )), pruningInfo=all size:4*3(part), pruning size:8, pruning time:0ms, pruning detail:(TEST_P00000_GROUP, [hash_tbl_todays_AutoPruning_dn1M_00006])->(PruneRaw(2024-09-10));(TEST_P00000_GROUP, [hash_tbl_todays_AutoPruning_dn1M_00000])->(PruneRaw(2023-12-30));(TEST_P00001_GROUP, [hash_tbl_todays_AutoPruning_dn1M_00003])->(PruneRaw(2024-09-08,2024-10-08))) |
| HitCache:true |
| Source:PLAN_CACHE |
| TemplateId: f36182f0 |
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
5 rows in set (0.00 sec)
pruningInfo で IN 枝刈りの詳細を見ることができます：

all size: 枝刈りされない場合、DN 計算ノードにプッシュされる IN パラメータリストの総数を表します。現在のケースでは、IN 式には 4 つのパラメータがあり、8 シャード中 3 シャードがこのリクエストに関与しているため、合計プッシュダウン数は 4*3=12 です。
pruning size: IN 式によって枝刈りされたパラメータの数を表します。枝刈り後、各パラメータは関連するシャードのみに送信されます。したがって、枝刈り後の数は IN 式パラメータの数と一致します。
pruning time: 枝刈りにかかった時間を表します。
pruning detail: シャード名、シャード化されたテーブル名、枝刈りされた IN パラメータリストなど、具体的な枝刈り情報を表します。

多列 IN 枝刈り

(a, b) in ((xx, xx), (yy, yy)) のような多列 IN 式も枝刈りをサポートしています。sql
mysql> explain select * from hash_tbl_todays_AutoPruning where (name, birthday) in ((xiaoli, 2024-09-08), (ming, 2024-09-10), (xiaoT, 2024-10-08), (yi, 2023-12-30)) and bid>100;
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| LOGICAL EXECUTIONPLAN |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Gather(concurrent=true) |
| LogicalView(tables=hash_tbl_todays_AutoPruning[p1,p4,p7], shardCount=3, sql=SELECT id, bid, name, birthday FROM hash_tbl_todays_AutoPruning AS hash_tbl_todays_AutoPruning WHERE ((((name, birthday)) IN(?)) AND (bid > ? )), pruningInfo=all size:4*3(part), pruning size:8, pruning time:0ms, pruning detail:(TEST_P00000_GROUP, [hash_tbl_todays_AutoPruning_dn1M_00006])->(PruneRaw((ming,2024-09-10)));(TEST_P00000_GROUP, [hash_tbl_todays_AutoPruning_dn1M_00000])->(PruneRaw((yi,2023-12-30)));(TEST_P00001_GROUP, [hash_tbl_todays_AutoPruning_dn1M_00003])->(PruneRaw((xiaoli,2024-09-08),(xiaoT,2024-10-08)))) |
| HitCache:true |
| Source:PLAN_CACHE |
| TemplateId: ce4cba38 |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
5 rows in set (0.00 sec)

複数の IN 式による枝刈り

マルチレベルシャードテーブルの場合、異なるレベルで異なる列が使用されます。ビジネス要件で複数の列に対して同時に IN クエリを実行する必要がある場合でも、枝刈りを適用できます。複数の IN 式がある場合、PolarDB-X はすべての IN パラメータを枝刈りするためにデカルト走査を行います。次の図は例を示しています。

PolarDB-Xインスタンスにおいて、まずレベル2のパーティションテーブルを作成し、その後複数のIN式を持つSQLクエリのEXPLAIN出力を確認します。sql
CREATE TABLE tb_k_k_tp(
id bigint not null auto_increment,
bid int,
name varchar(30),
birthday datetime not null,
primary key(id)
)
PARTITION BY KEY(bid)
PARTITIONS 2
SUBPARTITION BY KEY(id)
SUBPARTITIONS 4;sql
mysql> explain select * from tb_k_k_tp where bid in (1,2,3,4,5,6,7,8,9,10) and id in (11,12,13,14,15,16);
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| LOGICAL EXECUTIONPLAN |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Gather(concurrent=true) |
| LogicalView(tables=tb_k_k_tp[p1sp1,p1sp2,p1sp3,p1sp4,p2sp1,p2sp2,p2sp3,p2sp4], shardCount=8, sql=SELECT id, bid, name, birthday FROM tb_k_k_tp AS tb_k_k_tp FORCE INDEX(PRIMARY) WHERE((id IN(?)) AND (bid IN(? ))), pruningInfo=all size:16*8(part), pruning size:76, pruning time:1ms, pruning detail:(TEST_P00000_GROUP, [tb_k_k_tp_UyWm_00004])->(PruneRaw(1,4,7,8,9,10),PruneRaw(11,12));(TEST_P00001_GROUP, [tb_k_k_tp_UyWm_00005])->(PruneRaw(1,4,7,8,9,10),PruneRaw(13,16));(TEST_P00000_GROUP, [tb_k_k_tp_UyWm_00006])->(PruneRaw(1,4,7,8,9,10),PruneRaw(14));(TEST_P00001_GROUP, [tb_k_k_tp_UyWm_00007])->(PruneRaw(1,4,7,8,9,10),PruneRaw(15));(TEST_P00000_GROUP, [tb_k_k_tp_UyWm_00000])->(PruneRaw(2,3,5,6),PruneRaw(11,12));(TEST_P00000_GROUP, [tb_k_k_tp_UyWm_00002])->(PruneRaw(2,3,5,6),PruneRaw(14));(TEST_P00001_GROUP, [tb_k_k_tp_UyWm_00003])->(PruneRaw(2,3,5,6),PruneRaw(15));(TEST_P00001_GROUP, [tb_k_k_tp_UyWm_00001])->(PruneRaw(2,3,5,6),PruneRaw(13,16))) |
| HitCache:true |
| Source:PLAN_CACHE |
| TemplateId: f70bd95a |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
5 rows in set (0.00 sec)

EXPLAIN出力のプルーニング詳細情報から、元々は各8つのシャードに16個のパラメータが送信されることを意味し、DN（データノード）では128個（16×8＝128）のパラメータ値を処理する必要がありました。プルーニング後は、52個（128 - 76 = 52）のパラメータのみが残り、処理されます。

パフォーマンステスト

環境:

PolarDB-X 8C32G
Sysbench IN値テスト
クエリ：SELECT c FROM sbtest1 WHERE id in (?)
条件：5つのIN値、AUTOテーブル、400並列、プライマリキーとシャードキーはIDで、64のシャードテーブル

QPS結果:

	QPS	CN CPU	DN CPU	DN IOPS
Pruned	20031.74	100%	53%	10%
Not pruned	21322.80	100%	85%	47%

別条件でのQPS結果:

	QPS	CN CPU	DN CPU	DN IOPS
Pruned	7424.55	100%	100%	36%
Not pruned	639.39	20%	74%	100%

クエリ中にINプルーニングを行うことで、CN（コントロールノード）上で事前にパーティションを計算することで、DNにおける冗長な計算オーバーヘッドを回避できます。Sysbench INクエリの負荷テストによると、INプルーニングによりDNのCPU使用量が大幅に削減され、クラスタの容量が拡大します。

INパラメータの数が少ない場合（約5個）：CN CPUが最初にボトルネックとなり、プルーニングなしのQPSはプルーニングありの場合よりも若干高くなります。ただし、プルーニングなしの場合、DNのCPUおよびI/Oの負荷は大幅に高くなります。
INパラメータが増えた場合：プルーニングを行わない場合、DNのCPUおよびI/O負荷が大幅に増加し、プルーニングありの場合に達成可能なQPSを大きく下回ります。

正しさの証明

レベル2のパーティションテーブルTを考えます。各レベルには1つのパーティションキーしか持てないとします。レベル1のパーティションキーをsk1、レベル2のパーティションキーをsk2とします。フィルタ条件Fにはパーティションキーに関する定数IN条件が含まれており、これは線形時間でINプルーニングが可能です。

補題1

レベル2のパーティションテーブルTにおいて、フィルタ条件K内のすべての定数IN条件は、次の3つの集合X、Y、Zに属します：

X={(...,sk1,...) in A}
Y={(...,sk2,...) in B}
Z={(...,sk1,sk2...) in C}

ここでA、B、Cはすべて定数ベクトル集合です。

証明

フィルタ条件内の「m not in M」を「not(m in M)」に置き換えます。「m」がnullの場合、「m not in M」と「not(m in M)」の両方が未定義であることに注意してください。

補題2

n個のパーティションとパーティションキーskを持つパーティションテーブルAがある場合、フィルタ条件Kに条件(...,sk,...) in Sが存在する場合、Sはskのパーティショニング方式に基づいてn個の集合S1、S2、...、Snに分割できます（集合は空でもよい）。この条件は、論理的には異なるパーティションテーブル間で(...,sk,...) in S1、(...,sk,...) in S2、...、(...,sk,...) in Snと等価です。

証明

nullをフィルタリングしても結果に影響しません。i番目のシャードAiを考えます。∀sk ∈ Aiの場合、必ずpartition(sk) = iとなります。もし(...,sk,...) in Sならば、∃s∈ S, sk=sであり、partition(s)=iなので、s∈Siとなります。よって、(...,sk,...) in S => (...,sk,...) in Siです。直感的には、not((...,sk,...) in S) =&gt

INクエリの最適化について

各iに対して、パーティションテーブルTiと条件Y、Ziがある場合、再び補題3により、Y、Zi内のパラメータをプルーニングできます。上記の補題は、すべての式におけるINパラメータがシャーディングルールに基づいてプルーニングできることを証明しています。A IN(1,2,3) OR bid>100のようなケースでも、A内のパラメータは正しさに影響を与えることなくプルーニング可能です。しかし、コストや顧客利益のために、PolarDB-Xは現時点ではOR条件でのINプルーニングをサポートしていません。

まとめ

多数の条件値が関与するシナリオや複雑な分散環境において、SQL文におけるINクエリはそのシンプルさと潜在的な効率の高さから好まれますが、いくつかの固有の制限も持っています。継続的な技術的最適化の実践を通じて、PolarDB-Xは以下の主要な技術手段を探索し、INクエリを効果的に最適化します。これには以下が含まれますが、これらに限定されません：

最適化されたコスト計算メカニズム: 多数のパラメータを持つINクエリの場合、コスト評価アルゴリズムを調整し、リソース消費をより正確に予測し、より合理的な実行パスを選択します。
実行計画キャッシュのインテリジェント管理: パーサー、オプティマイザー、およびエグゼキューターを包括的に変換することで、クエリエンジンはINパラメータによって生成される冗長なSQLテンプレートの数を制御できます。これにより、プランキャッシュのオーバーフローによる全体的なパフォーマンスへの影響を防ぎます。
強化された分散処理能力: 効率的な前処理技術を使用して不要なINパラメータを特定し、削除します。これにより、各DNのワークロードが軽減され、クエリプロセスが加速され、データベースの全体的なパフォーマンスが向上します。

今後も引き続き、価値のあるデータベースエンジンの最適化技術を探求し、共有していきます。