はじめに
現在、さまざまなDBMSでの作業を最適化するという点で非常に人気があります。 「世界で最高のDBMS」について多くのフォーラムで議論がありますが、多くの場合、これらすべては「人生の意味を理解し、最高のデータウェアハウスはXであることに気づきました」という不合理な叫びに流れます。
はい、もちろん、今では多くのことができるNoSQLソリューションの積極的な開発を見ることができます。 しかし、この記事はそれらについてのものではありません。 私は自分の仕事を変えて、たくさんのphp + MySQLで非常に興味深いプロジェクトを手に入れたことがわかりました。 多くの良い決定がありますが、多くの聴衆を考慮せずに書かれました。 数年にわたって、アクティブユーザーの数は7ゼロの数字に近づき始めました。 このプロジェクトは、ゲーム要素を備えたソーシャルネットワークのように見えるため、ユーザーを含むテーブルは、最も「難しい」ものではありませんでした。 数千万のユーザーアイテム、プライベートメッセージ、請求レコードなどを含むテーブルを継承しました。プロジェクトはリファクタリングを開始し、複数のサーバーに分割し、重要な結果を達成しました。 これですべてが安定しました。
しかし、最近、新しいタスクがメールに送信されました。 一番下の行は、統計を収集することでした。 要件を分析した後、実行するだけで、ディメンションが印象的なテーブルで3つの内部結合を実行する1つのクエリを作成するだけで十分であることがわかりました。 各テーブルの平均レコード数は4,000万レコードです。 一時テーブルは、4 * 4 * 4 * 10 ^ 21 = 64 * 10 ^ 21エントリで構成されることがわかりました。 これは巨大な数字です。 そして、統計を収集するためにそのようなクエリでDBMSをロードすることは許されない贅沢です。
さらに、実際には、大学での1年生のときにコンピュータサイエンスの授業を思い出したときに生じたこの抽象的な問題の解決策を提示したいと思います。
（プロジェクトではMySQL DBMSを使用していますが、アルゴリズムには特定の機能はありません）
バイナリ検索とは何ですか？
あなたの多くは、バイナリアルゴリズムを使用して配列内の要素を見つけることに専念するラボを書いたと思います。 その本質を要約しようと思います。
n個の要素のソートされた配列があると仮定します。
配列の最初の要素= 1
最後の配列要素= n
値fを持つ要素のインデックスを見つける必要があります。
各ステップでは、配列の中央を計算します。
Mid-Array = round（最初の要素+最後の要素）/ 2
次に、この要素の値を計算し、取得した値が目的のfと比較して多かれ少なかれチェックします。 検索範囲は2倍に削減されます。
<midpoint >> fの場合、
最後の配列要素=中間値
そうでなければ
配列の最初の要素=中間値
これらのステップは、条件のいずれかになるまで繰り返されます。
- 平均値とf値の差のモジュラスは、 イプシロンよりも小さい（イプシロン、エラー）
- 反復回数がlog2の値（配列内の要素の数）を超えました
その点は明らかだと思います。 したがって、検索範囲を縮小することで目的の要素の検索を大幅に高速化しますが、計算の精度を犠牲にします（統計については、数百万の要素を数個考慮しない場合、これは重要ではありません。ツリー）。
練習に移りましょう
したがって、INNER JOINを3つのテーブルに作成し、条件「列xの範囲が10〜20」に設定する必要があるとします。 さらに、列xにはインデックスがありません。 非常に長くなります。 これは簡単な方法が救助に来るところです。
この同じ列を持つテーブルを取得し、バイナリ検索を使用して、10 <= x <= 20の条件を満たす主キーの範囲を検索します。 そのような選択にはインデックスのみを使用することを考えると、すぐに目的の値のペアを取得します。
バイナリ検索は範囲ではなく1つの要素を見つけるために使用されますが、10の値を持つ最初の要素と20の値を持つ最後の要素を見つけることを誰も気にしません。それらの主キーは範囲の制限になります。
この範囲でクエリに戻りますが、ここでWHERE x> = 10 AND x <= 20条件の代わりに、 WHERE id_x BETWEEN min_id_x AND max_id_xを記述します 。ここで、 min_id_xとmax_id_xは、条件を満たす範囲の下端と上端の値です。
取得するもの：ここで、列xに従って選択するのではなく、主キーに従って選択します。 1つのテーブルのクロールにかかる時間が節約されます。 リクエスト内の他の条件でも同様の手順を実行できます。
バイナリ検索コードはウィキペディアで見つけることができ、リクエスト自体は不自然なものではないため、ここにコードを持ち込む意味はありません。
結論
このアルゴリズムにより、インデックスのないフィールドから主キーに条件を転送できるため、クエリが大幅に高速化されます。 しかし、この方法は万能薬とは見なされません。
第一に 、すべての要求に対して普遍的なソリューションを準備することは困難です。 いずれにしても、特定のテーブルの実装の詳細を考慮する必要があり、その結果、毎回最適化に時間を費やす必要があります。
第二に 、この方法はすべてのソリューションに適しているわけではありません。テーブル内の行を何らかの順序でソートする必要があるためです。