機械学習を使用してPostgreSQLの生産性を向上させる

機械学習は、データの隠れたパターンを検索します。 ITコミュニティでのこのトピックへの関心の高まりは、それが生み出した例外的な結果に関連しています。 音声およびスキャンされたドキュメント、検索エンジンの認識-これらはすべて機械学習を使用して作成されます。 この記事では、私たちの会社の現在のプロジェクト、つまりDBMSの生産性を向上させるために機械学習法を適用する方法についてお話します。
この記事の最初の部分では、既存のPostgreSQLスケジューラメカニズムを分析し、2番目の部分では、機械学習を使用してそれを改善する可能性について説明します。

SQLクエリ実行プランとは何ですか？

SQLは宣言型言語であることを思い出してください。 これは、ユーザーがデータに対して実行する操作のみを示すことを意味します。 DBMSは、これらの操作を実行する方法を選択する責任があります。 たとえば、リクエスト

SELECT name FROM users WHERE age > 25; 

これを行うには2つの方法があります。usersテーブルからすべてのエントリを読み取り、25歳以上の条件が満たされているかどうかを確認するか、ageフィールドのインデックスを使用します。 2番目のケースでは、余分なレコードを調べませんが、インデックスを使用した操作のために1つのレコードの処理により多くの時間を費やします。



より複雑なクエリを検討する

 SELECT messages.text FROM users, messages WHERE users.id = messages.sender_id; 

このJOINは、次の3つの方法で完了できます。

• ネストループ（NestedLoopJoin）は、2つのテーブルからすべての可能なレコードペアをスキャンし、条件が満たされている各条件をチェックします。
• Merge（MergeJoin）は両方のテーブルをidフィールドとsender_idフィールドでそれぞれソートし、2ポインターメソッドを使用して条件を満たすすべてのレコードのペアを見つけます。 このメソッドは、マージソートメソッド（MergeSort）に似ています。
• ハッシュ（HashJoin）は、最小のテーブルのフィールドにハッシュテーブルを作成します（この場合、これはusers.idフィールドです）。 ハッシュテーブルにより、各メッセージエントリは、users.id = messages.sender_idのエントリをすばやく見つけることができます。

リクエストに複数のJoin操作が必要な場合、リクエスト内など、別の順序で実行することもできます

 SELECT u1.name, u2.name, m.text FROM users as u1, messages as m, users as u2 WHERE u1.id = m.sender_id AND u2.id = m.reciever_id; 

クエリ実行ツリーは、クエリ実行プランと呼ばれます。

explainコマンドを使用して、DBMSが特定のクエリに対して選択したプランを確認できます。

 EXPLAIN SELECT u1.name, u2.name, m.text FROM users as u1, messages as m, users as u2 WHERE u1.id = m.sender_id AND u2.id = m.reciever_id; 

要求を実行し、選択された計画を表示するには、 explain analyseコマンドを使用できます。

 EXPLAIN ANALYSE SELECT u1.name, u2.name, m.text FROM users as u1, messages as m, users as u2 WHERE u1.id = m.sender_id AND u2.id = m.reciever_id; 

同じリクエストの異なるプランの実行時間は、桁違いに異なる場合があります。 したがって、クエリ実行プランの正しい選択は、DBMSのパフォーマンスに重大な影響を及ぼします。 PostgreSQLが今どのように計画を選択するかを詳しく見てみましょう。

DBMSは最適なクエリ実行プランをどのように探しますか？

最適なプランを見つけるプロセスを2つの部分に分けることができます。

まず、計画の価値、つまり計画を完了するために必要なリソースの量を評価できる必要があります。 サーバーで他のタスクやクエリが実行されない場合、クエリの推定実行時間は、それに費やされるリソースの量に正比例します。 したがって、プランのコストは、任意の単位での実行時間であると想定できます。

第二に、最小コストの見積もりで計画を選択する必要があります。 リクエストの複雑さが増すにつれて、プランの数が指数関数的に増えていることを示すのは簡単です。したがって、すべてのプランを調べて、それぞれのコストを見積もり、最も安いプランを選択することはできません。 最適なプランを見つけるために、より複雑な離散最適化アルゴリズムが使用されます。単純なクエリには動的サブセットプログラミング、複雑なクエリには遺伝的アルゴリズムです。



このプロジェクトでは、最初のタスクに焦点を当てました。この計画に従って、その価値を予測する必要があります。 実行計画を起動せずにこれを行うにはどうすればよいですか？


このタスクは、2つのサブタスクにも分かれています。 最初に、各計画ノードについて、その中で選択されるタプルの数が予測されます。 次に、この情報に基づいて、各頂点のコスト、したがって計画全体が推定されます。



PostgreSQLの2つのサブタスクのどちらが悪化しているかを調べるために、少し調査しました。
以下の図の各点は、計画の1つの頂点に対応しています。 各頂点について、その頂点で選択されたタプルの数とその実行のコストが予測され、その後、選択されたタプルの実際の数と実行時間が測定されました。 右の図には、タプル数が正しく予測されている頂点のみが表示されているため、コスト推定の品質を判断するために使用できます。

予測されるタプルの真の数の依存性	計画の時間のコストへの依存 タプルの数が正しく予測されている場合

最初の図は、最初のサブタスクを解決した結果が真のサブタスクと数桁異なることを示しています。 2番目の図は、実行時間と強い相関関係が見られるため、最初のサブタスクの正しい解決策で、PostgreSQLモデルが1つまたは別の計画を実行するコストを適切に推定することを示しています。 その結果、DBMSのパフォーマンスは両方のサブタスクの不正確な解決策に苦しむことがわかりましたが、各頂点に誤って設定されたタプルの数に苦しむことがわかりました。

PostgreSQLで使用される最初のサブタスクのソリューションを検討してください。

DBMSは頂点のタプル数をどのように推定しますか？

最初に、簡単なクエリで選択されたタプルの数を予測してみましょう。

 SELECT name FROM users WHERE age < 25; 

少なくともこれを行う機会を得るために、データに関するいくつかの情報、その統計が必要です。 PostgreSQLは、このデータ情報としてヒストグラムを使用します。



ヒストグラムを使用すると、25歳未満のユーザーの割合を簡単に復元できます。 計画の各頂点について、処理されたすべてのタプルに対する選択されたすべてのタプルの割合は、 選択性と呼ばれます。 上記の例では、SeqScan選択性は約0.3です。 頂点によって選択されたタプルの数を取得するには、頂点の選択性に処理されたタプルの数を掛けるだけで十分です（SeqScanの場合、これはテーブル内のレコードの数になります）。

より複雑なクエリを検討する

 SELECT name FROM users WHERE age < 25 AND city = 'Moscow'; 

この場合、年齢と都市ごとのヒストグラムを使用すると、 限界サンプル、つまり25歳未満のユーザーの割合とユーザー間の白雲母の割合のみを取得できます。 PostgreSQLモデルでは、すべての条件（ 5 < a AND a < 7形式の条件のペアを除き、条件5 < a < 7自動的に変わります）は独立と見なされます。 数学者は、両方の条件が同時に満たされる確率が確率の積に等しい場合、2つの条件AおよびBを独立して呼び出します。P（AおよびB）= P（A）P（B）。 ただし、適用された意味では、2つの量の独立性は、別の量の分布が1つの量の値に依存しないという事実として理解できます。

問題は何ですか？

場合によっては、独立性の仮定が満たされないことがあります。 このような場合、PostgreSQLモデルはあまりうまく機能しません。 この問題に対処するには2つの方法があります。

最初の方法は、多次元ヒストグラムを作成することです。 この方法の問題は、次元の増加に伴い、多次元ヒストグラムが同じ精度を維持するために指数関数的に増加するリソース量を必要とすることです。 したがって、小さな次元のヒストグラムに限定する必要があります（2〜8回の測定）。 ここから、このメソッドの2番目の問題が続きます。多次元ヒストグラムを構築することが理にかなっている列のペア（またはトリプル、または4 ...）について、どういうわけかを理解する必要があります。
この問題を解決するには、リソースを集中的に使用するクエリの計画を調査し、列間の相関を判断し、どのヒストグラムを完了する必要があるかを手動で示す優れた管理者、または統計テストを使用して互いに依存している列を見つけようとするソフトウェアツールが必要です。 ただし、すべての依存列のヒストグラムをプロットすることは意味がないため、ソフトウェアはクエリ内の列の同時発生も分析する必要があります。 現在、PostgreSQLで多次元ヒストグラムを使用できるパッチがありますが、管理者はこれらの多次元ヒストグラムを作成する列を手動で設定する必要があります。

機械学習を使用して選択性を評価する

ただし、この記事では別のアプローチに焦点を当てています。 別のアプローチは、いくつかの条件の共同選択性を見つけるための機械学習の使用です。 前述のように、機械学習はデータのパターンを探します。 データはオブジェクトのコレクションです。 この例では、オブジェクトは計画の1つの頂点にある条件のセットです。 これらの条件とその限界選択性の下で、共同選択性を予測する必要があります。

計画の最上部で観察される兆候は、そのすべての条件の限界選択性です。 定数のみが異なるすべての条件は互いに同等であると仮定します。 この仮定は、空間の次元を削減するために適用される典型的な機械学習手法（ハッシングトリック）と考えることができます。 ただし、この背後にはさらに強力な動機があります。条件定数を予測するために必要なすべての情報は、その限界選択性に含まれていると想定しています。 これは、a <const：という形式の単純な条件に対して厳密に示すことができます。ここでは、条件の選択性から、定数の値を復元できます。つまり、情報の損失は発生しません。

結果の機械学習タスクは、図に示すようになります。


他のすべての列の既知の値によって、左端の列を予測する必要があります。 特定の実数を予測する必要があるこのようなタスクは、機械学習の回帰問題と呼ばれます。 それを解決するメソッドは、それぞれリグレッサーと呼ばれます。

すべての列の対数に移りましょう。 線形回帰を使用する場合、特別なケースとして現在のPostgreSQLモデルを取得することに注意してください。

線形回帰：


すべての構成可能なパラメーターが1に等しい場合、標準のPostgreSQL選択モデルを取得します。


標準的なリッジ回帰法では、次の機能を最小化することでパラメーターを検索することをお勧めします。


さまざまなアプローチをテストするために、TPC-Hベンチマークを使用しました。

次のメソッドが単純なリグレッサーとして使用されました。

• リッジ線形回帰+確率的勾配降下。 この方法は、動的学習（オンライン学習）を使用できるという点で優れているため、監視可能なオブジェクトを保存する必要はありません。
• 多くの紋付き線形回帰+確率的勾配降下。 ここでは、条件のセットごとに個別のリッジ線形リグレッサーが作成されると想定しています。 このメソッドは、前のメソッドと同様に、動的学習を使用できる点で優れているため、監視可能なオブジェクトを保存する必要はありませんが、大幅に構成可能なパラメーターが含まれているため、前のメソッドよりも多少正確に機能します。
• 多くのリッジ線形回帰+ガウス法による解析解。 この方法では、すべてのオブザーバブルオブジェクトを保存する必要がありますが、同時に、前の2つのオブジェクトとは異なり、はるかに高速にデータ用に構成されます。
  ただし、これはマイナスでもあります。動作はかなり不安定です。
  

分析ソリューションで生じる不安定性の性質を説明しましょう。 リグレッサーの応答は、最適なプランを探しているオプティマイザーの入力値です。 観察するオブジェクト（実行可能プラン）は、オプティマイザーの出力値です。 したがって、観察するオブジェクトは、リグレッサーの応答に依存します。 このようなフィードバックシステムは、リグレッサーが環境に影響を与えないシステムよりも研究がはるかに困難です。 これらの用語では、ガウス法による分析ソリューションは不安定です-すぐに学習しますが、よりリスクの高いソリューションを提供するため、システム全体が悪化します。



線形モデルの詳細な調査の結果、データが適切に記述されていないことがわかりました。 したがって、テストした方法の最良の結果がkNNによって示されました。

• kNN。 この方法の大きなマイナス点は、すべてのオブジェクトをメモリに保存する必要があることです。その後、オブジェクトをすばやく検索して整理します。 この状況は、オブジェクト選択アルゴリズムを使用して大幅に改善できます。 オブジェクトを選択するための単純なアルゴリズムのアイデア：オブジェクトの予測が十分であれば、このオブジェクトを覚える必要はありません。

また、この方法は線形回帰よりも安定しています。TPC-Hベンチマークでの収束には、上の図に示すように2トレーニングサイクルのみが必要です。

機械学習の使用がもたらすもの

kNNアルゴリズムで得られた結果を示します。

機械学習の前に	機械学習の後

提案されたアプローチは、実際にDBMSの時間を短縮することがわかります。 ベンチマークリクエストのタイプの1つでは、加速は30〜45％で、もう1つは2〜4倍です。

開発の方法は何ですか？

既存のプロトタイプをさらに改善するには、さらに多くの指示があります。

1. 計画を見つける問題。 現在のアルゴリズムは、アルゴリズムが収束する計画において、選択性予測が正しいことを保証します。 ただし、これは選択した計画の全体的な最適性を保証するものではありません。 グローバルに最適な計画または少なくとも最適なローカル最適計画の検索は、個別のタスクです。
2. 失敗した計画の実行を終了する割り込みモード。 標準のPostgreSQLモデルでは、最適なプランは1つしかなく、変更されないため、プランの実行を中断することは意味がありません。 機械学習の導入により、選択性の予測に重大な誤りがあった計画の実行を中断し、受け取った情報を考慮して、実装に最適な新しい計画を選択できます。 ほとんどの場合、新しい計画は以前の計画と大きく異なります。
3. 情報の陳腐化のモード。 DBMSの動作中に、データと一般的なクエリが変更されます。 したがって、過去に取得されたデータはもはや関連性がない可能性があります。 現在、当社は情報の関連性を判断し、それに応じて古い情報を「忘れる」ための優れたシステムに取り組んでいます。

あれは何だった？

この記事では：

• PostgreSQLスケジューラのメカニズムを分解しました。
• 現在の選択性評価アルゴリズムで指摘された問題。
• 機械学習法を使用して選択性を評価する方法を示しました。
• 機械学習を使用すると、スケジューラの作業が改善され、それに応じてDBMSの作業が加速されることが実験的に確立されました。

ご清聴ありがとうございました！

文学

• PostgreSQLスケジューラー
  
  • Postgres Query Optimizer、Bruce Momjianの説明
  • PostgreSQL開発者向け資料
  • PostgreSQL内部デバイスレポート、Neil Conway
  
  
• 機械学習について（K.V. Vorontsovの講義コースから）
  
  • 機械学習の概要
  • メトリック方式
  • 線形モデルと確率的勾配