制限およびオフセット ページング シナリオを使用すると速度が遅くなるのはなぜですか?

質問から始めましょう

5 年前、私が Tencent にいたとき、ページング シナリオでは MySQL のリクエスト速度が非常に遅いことに気付きました。データ量が 10w しかない場合、単一のマシンから xx を選択するのに約 2 ～ 3 秒かかります。

私は師匠にその理由を尋ねたところ、彼はこう尋ねました。「インデックスのシナリオでは、MySQL で n 番目に大きい数値を取得するのにかかる時間はどれくらいですか?」

答えの探求

シナリオを確認する

ステータスにインデックスがあると仮定します。ステータス = xx 制限 10 オフセット 10000 のテーブルから * を選択します。

とても遅くなります。データ量が多くない場合は、数秒の遅延が発生します。

小白が答える

当時、私はとても安心していました。何が起こっても先生が面倒を見てくれるからです。私の技術力はグループ内で一番下だったので、私は推測で、ノードを見つけるのは log(N) だけだと考えました。当然、師匠は私に独学をさせてくれました。

このステージは10分かかりました。

回答を続ける

よく分析してみると、インデックスを検索するのは面倒だということがわかります。左のサブツリーと右のサブツリーの最初の 100 個の数字の分布がわからないため、バイナリ ツリーの検索特性を使用することはできません。

学習を通じて、MySQL のインデックスは B+ ツリーであることがわかりました。

この写真を見た後、すべてが明らかになりました。 100番目に大きいツリーは、複雑度がO(n)のリーフノードで構成されたリンクリストを通じて直接見つけることができます。しかし、O(n) だとしても、法外に遅いというわけではありません。何か理由があるのでしょうか?

この段階では、主にオンラインで情報を検索し、断続的に 10 日間かかりました。

システム学習

おすすめの本を 2 冊紹介します。1 冊は「MySQL Technology Insider InnoDB Storage Engine」で、mvcc、インデックス実装、ファイル ストレージなど、InnoDB の実装メカニズムをより深く理解できます。

2 つ目は「High Performance MySQL」です。これは使用レベルから始まりますが、詳細に説明され、多くの設計アイデアについて言及されています。

2 冊の本を組み合わせて繰り返し学習すれば、MySQL をほぼマスターできます。

ここでは 2 つの重要な概念があります。

• クラスター化インデックス: 主キー インデックスと対応する実際のデータが含まれます。インデックスのリーフ ノードはデータ ノードです。
• 補助インデックス: セカンダリ ノードとして理解でき、そのリーフ ノードはインデックス ノードでもあり、主キー ID が含まれています。

最初の 10,000 は捨てられるとしても、MySQL はセカンダリ インデックスのプライマリ キー ID を使用して、クラスター化インデックスのデータをチェックします。これは 10,000 のランダム IO なので、当然ハスキー犬と同じくらい遅くなります。

なぜこのような動作が発生するのか疑問に思うかもしれません。これは MySQL の階層化に関連しています。制限オフセットは、エンジン レイヤーによって返される結果セットにのみ使用できます。つまり、エンジン層も無実であり、この1万個が捨てられることになるとは知らないのだ。

以下はMySQLの階層化の図です。エンジン層とサーバー層が実際には分離していることがわかります。

ここまでで、遅くなる理由が大体分かりました。この段階は1年かかりました。

類推によって理解する

当時私は3年間働いており、ソースコードを調べ始めました。 etcd を読んだ後、tidb のソースコードをいくつか読みました。データベースの種類に関係なく、クエリ ステートメントは実際には論理演算子で構成されます。

論理演算子の紹介

具体的な最適化ルールを記述する前に、クエリ プランの論理演算子について簡単に紹介します。

• DataSource はデータ ソース、つまり select * from t のテーブル t です。
• 選択範囲は、たとえば、フィルター条件が xx = 5 である t から xxx を選択します。
• 投影、クエリ「select c from t」で t から c を選択することは投影操作です。
• 結合接続、t1、t2 から xx を選択します。ここで、t1.c = t2.c は、2 つのテーブル t1 と t2 を結合することを意味します。

選択、投影、結合 (略して SPJ) は、最も基本的な演算子です。内部結合、左外部結合、右外部結合など、さまざまな結合モードがあります。

select b from t1, t2 where t1.c = t2.c and t1.a > 5 が論理クエリ プランになった後、t1 t2 に対応する DataSource がデータの取得を担当します。

上記に結合演算子を追加して、t1.c = t2.c に従って 2 つのテーブルの結果を接続し、次に t1.a > 5 に従って選択フィルターを実行し、最後に列 b が投影されます。

次の図は最適化されていない表現です。

つまり、MySQL がエンジン層に制限とオフセットを渡したくないわけではなく、論理演算子が分割されているため、特定の演算子にどれだけの修飾データが含まれているかを知ることが不可能なのです。

解決方法

「高性能MySQL」では2つのソリューションについて言及している

解決策1

実際のビジネスニーズに応じて、特に前の完全なページングが一般的ではなかった iOS と Android で、次のページと前のページの機能に置き換えることができるかどうかを確認します。

ここで、limit と offset は補助インデックス (つまり、検索条件) id に置き換えられます。 ID が再度呼び出された場合は、フロントエンドに返す必要があります。

解決策2

正面から向き合ってください。ここで、インデックス カバレッジという概念について説明します。補助インデックスによってクエリされるデータに ID と補助インデックス自体のみが含まれる場合、クラスター化インデックスをクエリする必要はありません。

考え方は次のとおりです: select xxx,xxx from in (select id from table where second_index = xxx limit 10 offset 10000) この文は、まず条件クエリからのデータに対応する一意のデータベース ID 値を検索することを意味します。主キーはすでにセカンダリ インデックス上にあるため、クラスター化インデックスのディスクに戻ってそれを取得する必要はありません。次に、これらの 10 個の限定された主キー ID を使用して、クラスター化インデックスをクエリします。これにより、ランダムな IO が 10 回のみ実行されます。

ビジネスでページングが本当に必要な場合は、このソリューションを使用するとパフォーマンスが大幅に向上します。通常、パフォーマンス要件を満たします。

最後に

卒業までの3年間、ご指導とご忍耐をいただいた先生に、心から感謝しています。彼は休日に私に読書課題を与え、昼休みに私の学習進捗状況を確認し、質問をして問題の探求を導いてくれました。テンセントを卒業した後も、会うたびにたくさんのアドバイスをくれ、知識を伝え、私の質問に答えてくれて、あらゆる面で最善を尽くしてくれました。

以上がこの記事の全内容です。皆様の勉強のお役に立てれば幸いです。また、123WORDPRESS.COM を応援していただければ幸いです。