Closed12

「SQL実践入門」を読む

shira79shira79

DBMSのアーキテクチャ

クエリ評価エンジン

クエリ評価エンジンは、ユーザーから受け取った SQLを解釈しどのような手順で記憶装置のデータへアクセスするか決定する。ここで決定された手順を実行計画と呼ぶ。

バッファマネージャー

DBMSはバッファという特別な用途に使うメモリ領域を確保します。そのバッファを管理するのがバッファマネージャー。ディスク容量マネージャーと連携しながら動く。

ディスク容量マネージャー

DBは永続的にデータを保存しなければならないからですが、ディスク容量マネージャーはどこにどのようなデータ保存するかを管理し、それに対する読み出し書き込みを制御する。

トランザクションマネージャとロックマネージャー

トランザクション同士を上手くデータの整合性を保ちながら実行させ、必要とあらばデータにロックをかけて誰かを待機させるといった仕事する。

リカバリマネージャ

障害に備えて定期的にバックアップを取得し、いざという時にデータ復旧する機能を司る

https://mura-hiro.com/dbms-architecture/

shira79shira79

DBMSとバッファ

バッファはパフォーマンスに対して重要な役割を担っています。メモリという希少資源に対してデータベースが保有するデータ量が圧倒的に多くどのようなデータをバッファに確保すべくかに対するトレードを発生させる。

記憶装置は記憶コストに応じて三つの階層に分類される。PC の HDD は平均何テラバイトでも増設するがメモリアル2 GB 買うだけでも結構悩む。これはそれだけ HDD が安価で大容量データを保存できることを意味する。上位層のメモリであればアクセスが早いが大量データを永続的に保持するには向いていない。海藻のメモリであれば永続的に大量データを保持するには向いているがアクセスは遅い。
つまり容量&永続性と速度はトレードオフの関係にある。

  • 一時記憶装置(レジスタ、メモリなど)
  • 二次記憶装置 (HDD CD DVD フラッシュメモリなど)
  • 三時記憶装置(テープなど)

DBMSは重要なデータ保存するとことを主目的としたミドルウェアの為、記憶装置とは切っても切れない関係にあるDBMDSが使う代表的な記憶装置はHDD、メモリの2つです。

HDD(Hard Disk Drive)

データを保存するストレージはほとんどが HDD ですHDD は記憶装置の回送で言うと真ん中の2次記憶装置に分類されますいいところがない代わりに大きな欠点もない媒体ということです。

メモリ

メモリーはディスクに比べるとコストが高いため1台のハードウェアに搭載できる量が多くありません。データベースサーバーの場合搭載されるメモリはせいぜい数GB から数十GB ほど。よほどの大規模向けでないと100GB を超えることはないでしょう。当たり前のように TB の容量を持つ HDDとは桁違いに小さいサイズです。

一部のデータをメモリに乗せている理由はパフォーマンス向上つまり SQL 文の実行速度を早くするため。
一般的に SQL 文の実行時間のほとんどはストレージに対する I/O に費やされるがメモリに保存しておくことでリスクへのアクセスを回避しパフォーマンスを改善する。

この世にパフォーマンスを向上を目的としてデータを保存するメモリをバッファとかキャッシュと呼ぶ。大高速アクセス可能なバッファにどのようなデータをどの程度の期間の置いておくかといったことを管理する機能が バッファマネージャー。

メモリにはデータの永続性がなくハードウェアの電源落とすがメモリ上に乗っていたデータは消えてなくなる。これを揮発性と呼ぶ。

揮発性の一番困るのは障害時にメモリ上のデータが消失しまうことでデータ不整合の原因になることデータキャッシュであれば障害によってメモリ上のデータが失われたとしてもオリジナルのデータディスク上に残っている。しかしログバッファに存在するデータがディスク上のログファイルへ反映する前に障害によって消えてしまった場合そのデータは復旧できない。これを回避するためにデータベースはコミットのタイミングで必ず更新情報をログファイルに書き込む事によって整合性を担保しているちなみにこのログファイルは永続的なストレージに存在する。逆に言うとコミットの際はディスクへの同期アクセスをしている。

※ 再起動でキャッシュを失うことでパフォーマンスが下がる事象を解決するために、キャッシュウォームアップという機能も存在する。
https://dev.classmethod.jp/articles/warmup-cache-for-mysql-and-aurora/

データベースがデータを保存するために使うメモリには大きくデータキャッシュとログバッファの2種類があります。

データキャッシュ

MySQL ではバッファプールと呼ぶ。MySQLでの初期値は128 MB。

データキャッシュはディスクにあるデータの一部を保存するためのメモリ領域。もし自分で選択したいデータが運良くこのデータキャッシュの中に存在した場合高速なレスポンスが期待できる。

ログバッファよりデータキャッシュの方がサイズが大きいがこれはデータベースが基本的に検索をメインの処理と想定していることに起因するそのため更新にメモリを多くさとよりは検索処理でヒットしそうなデータキャッシュに乗せておく方が得策という考え。

もしシステムが検索に比べて更新量の多い特性を持っている場合はログバッファに多くのメモリを割り当てると言ったチューニングをしてもいいかもしれない

InnoDB は、LRU (Least Recently Used) アルゴリズムのバリエーションを使用して、プールをリストとして管理します。

https://dev.mysql.com/doc/refman/5.6/ja/innodb-buffer-pool.html

LRUとは、広さの限られた一時的な保管場所が満杯になったとき何を棄てるか決定する基準の一つで、最も過去に使用されたものから順に破棄する方式。IT分野以外でも書類の整理方法などに応用されている。

https://e-words.jp/w/LRU.html

ログバッファ

MySQL ではそのままログバッファと呼ぶ。MySQLでの初期値は8 MB。

データベースはこうした更新のSQL 文を受け取った時に即座にストレージ上のデータを更新しているわけではなく、一度このログバッファ上に更新情報を貯めてディスクへの更新は後でまとめて行なっている。

つまりデータベースの更新処理は SQL 文の実行タイミングとストレージへの更新タイミングにズレがある非同期処理なのです。わざわざタイミングをずらしているのはパフォーマンスを良くしたいから。一度メモリで更新情報を受けた時点でユーザーにはその更新 SQL 文は終わったと通知している。

ワーキングメモリ

ソートやハッシュなどの特定の処理に利用される作業用の領域のこと。MySQL ではソートバッファと呼ぶ。

shira79shira79

実行計画

クエリ評価エンジンはデータアクセスの手続きを決めるモジュールであり SQL 文の最初に受け取る。パーサやオプティマイザといったサブモジュールから構成されます。

https://qiita.com/NagaokaKenichi/items/5b6eb9887f88046a594d

クエリ処理の流れ

  1. パーサ
  2. オプティマイザ(プラン生成、コスト評価を担当)
  3. カタログマネージャ
  4. プラン評価

パーサ

もうその役割は名前の通り構文解析です。SQL 文をバラバラの要素に分解しそれを処理しやすい形式に変換する。ユーザーが患部を書き忘れたり存在しないテーブル名を指定してきたらここでエラーを出す。

オプティマイザ

パーサを通過したクエリは オプティマイザ に送られます。ここで最適なデータアクセスの方法が決定される。
インデックスの有無、データの分散、偏りの度合い、内部パラメーターなどの条件を考慮して選択可能な多くの実行計画を作成し、それらのコストを計算してその低コストな一つに絞り込みます。

カタログマネージャ

オプティマイザーが実行計画を立てる際に、重要な情報を提供するのがカタログマネージャ。カタログとはDBMSの内部情報を集めたテーブルでテーブルやインデックスの統計情報が格納されています。このカタログの情報を「統計情報」とも呼びます。

プラン評価

オプティマイザが複数の実行計画を立てた後それを受け取って最適な実行計画を選択するのがプラン評価です。実行計画というのは人間が読むことのできる計画書。したがってパフォーマンスの悪い部分についてはこの実行計画をエンジニアがやることになって補正案を考えることもできる。

shira79shira79

オプティマイザとの付き合い

データベースのユーザーとしてはこのオプティマイザーを上手く使う事が大事。オプティマイザは放っておけば万事よろしくやってくれるほど万能ではないので、特にカタログマネージャーが管理する統計情報を気にする必要がある。これはお任せにしている場合適切なプランが選ばれない事が多々あるからです。よくありがちなのは統計情報が不適切なケースです。

統計情報とは次のようなものです

  • 各テーブルのレコード数
  • 各テーブルの列数と列 のサイズ
  • 列値の値の個数
  • 列値のヒストグラム
  • 列内にあるNULLの数
  • インデックス情報

これらの情報から実行計画を作るがこの統計情報が実態と一致しないが場合に問題が起きる。テーブルに対してデータの更新が行われたのに統計情報が更新されてないと古い情報をもとに実行計画を作ろうとする。

テーブルのデータが大きく変更されたらカタログの統計情報もセットで更新するとパフォーマンスは良くなるかも。
MySQLはANALYZE TABLEコマンドで統計情報が更新できる。

確認のコマンドは以下を参考
https://yohei-a.hatenablog.jp/entry/20180610/1528664051

shira79shira79

実行計画について

SQL の遅延が発生したときに最初に調べるべき対象は実行計画となる。

  • 操作対象のオブジェクト
  • オブジェクトに対する操作の種類
  • 操作の対象となるレコード数
    各操作でどれだけのレコードが処理されるかが、SQL 文の実行コストを把握するために重要となる。このレコード数は、統計情報が元になっている。
shira79shira79

SQL に置ける条件分岐

UNIONはテーブルに対するアクセスが増えるので基本的には冗長でありコストが高い。簡単にレコード集合をマージできるという点でユニオンは便利だが、無駄なアクセスを発生させてパフォーマンスを悪化させてしまうのでアンチパターン。

同じテーブルをUNIONするんだったら、INやCASE式を検討してみてもいいかも。

ユニオンを使わなければ分岐が表現できないパターンとして最もわかりやすくかつ多いのがマージされる select 文同士で使用するテーブルが異なる場合。

また UNION を使った方がパフォーマンスが良いケースもある。それはインデックスが関係する場合。うまく絞り込みの効くインデックスを利用できて且つユニオン以外の手段ではそうしたインデックスが使用できない場合はパフォーマンスが良くなる可能性がある

shira79shira79

集約とカット

GROUP BY句やウィンドウ関数は内部的に ハッシュ かソートの処理が実行されている。
ハッシュ やソートはメモリを多く使用するのだがもしメモリが不足した場合は一時領域としてストレージが使用されてパフォーマンスが悪化するかも。

集約関数とGROUP BY句の実行計画はハッシュやソートに使用するワーキングメモリの容量に注意すること以外、特にパフォーマンスにおいて気にすることはない。またケース式や関数を使ったところで実行計画には影響ない。

MySQLは集約関数とGROUP BY句においては、ソートが使われている。(実行計画のextraでusing filesort;が出る。)
https://qiita.com/lastcat_/items/de7b530a94fbcf9ba646

GROUP BY句やウィンドウ関数とCASE式を組み合わせると非常に強力な表現力を持つ。

nameの一文字目でグループ化。

SELECT SUBSTRING(name,1,1) AS label
        count(*)
FROM Persons
GROUP BY SYBSTRING(name,1,1)

年齢による区分を実施。カット基準となるキーをGROUP BY句とSELECT句の両方に書いている。

SELECT CASE WHEN age < 20 THEN '子供'
       CASE WHEN age BETWEEN 20 AND 69 THEN '成人'
       CASE WHEN age >= 70 THEN '老人'
       ELSE NULL END AS age_classs,
count(*)
FROM Persons
GROUP BY CASE WHEN age < 20 THEN '子供'
         CASE WHEN age BETWEEN 20 AND 69 THEN '成人'
         CASE WHEN age >= 70 THEN '老人'
         ELSE NULL END,
shira79shira79

ループ

SQL ループがない。SQLはそもそもループをなくそうという発想で作られた言語。

RDB考案者のコッドの発言。

“リレーショナルな処理は関係全体を操作対象とする。その主要な目的は、ループを なくすことである。これはエンドユーザーの生産性を高めるためには必須の要件であった。 そして、これがアプリケーションプログラマの生産性向上にも寄与することは明らかである。”

https://eh-career.com/engineerhub/entry/2017/11/22/110000

ミドルウェアやORMなどのフレームワークを使うと内部で自動的にループの SQL が発行されることもありエンジニア側に選択の余地がないケースもある。DBMSの外部キー制約において CASCADE DELETE、CASCADE UPDATEを利用した場合など小テーブルの更新は1行を更新する。SQL が繰り返し発行されるという内部データをするため大量データの更新時には性能問題になることがある。

ループ ⇄ 複数行一度に処理。
ループがパフォーマンス的に良くない理由は

SQL実行のオーバーヘッド。

SQL の実行っていっても実際はいろんな処理がその前後で行われている。データベースのへの接続、SQL 文のパース、SQL文の実行計画生成評価など。ループが多ければ多いほどオーバーヘッドの占める割合が多くなりがち。

分散処理がやりにくい

データベースの進化による恩恵を受けられない

dbms のベンダーは複雑な SQL をいかに高速に実行するかということに心血を注いでいるため、バージョンがアップするほど複雑な SQL のパフォーマンスは上がっていく。一方で単純な SQLが速くなる望みは薄い。そのためmiddleware の進化による恩恵もあまり得られない。物理リソースがボトルネックになってるわけではないので特に早くならない。
ループの場合はチューニングポテンシャルがほとんどない。

shira79shira79

結合

https://qiita.com/aki3061/items/e9e7c37d59991c7aa3c2#参考文献

クロス結合

クロス結合は結合対象となる二つのテーブルのレコードから可能なすべての組み合わせを網羅する演算。
社員テーブル6行と部署テーブル4行があった場合、24行が結果として得られる。

クロス結合が実に使われることはないが、内部結合と外部結合はこのクロス結合基準にすると理解がしやすい。

内部結合

クロス結合の結果からさらに、結合条件の部分集合が結果となる。

内部結合という言葉の由来は、ここにあって、内部というのは「直積の部分集合」という意味。内部結合の演算を行うアルゴリズムとしても一度クロス結合の結果を作ってから結合条件でフィルタリングをxという方法が最も単純。とはいえ実際に dbms が内部結合を実行するアルゴリズムはクロス結合の実行コストは並外れて高いため、これと異なります。実際は最初から結合対象になるべく絞り込むように動作している。

外部結合

外部とは「直積の部分集合」にならないという意味。

外部結合の結果にはマスター側のテーブルだけに存在する気があった場合そのキーを削除する結果に保存するよう動作する。
上記のパターンで保存された結果は、内部結合はもちろんクロス結合の結果のどの行とも一致しない。いわば「外部」にはみ出ている。

外部結合のパターンは3つある。

  • 左外部結合
  • 右外部結合
  • 完全外部結合

結合のアルゴリズムとパフォーマンス

オプティマイザが選択可能な結合アルゴリズムは大きく次の三つがある。

  • Nested Loops
  • Hash
  • Sort Merge

データサイズや結合系の分散といった要因にも依存するが最も頻繁に見るのはNested Loops。

ちなみにMySQLではNested Loopsのみ
https://dev.mysql.com/doc/refman/5.6/ja/nested-loop-joins.html
https://qiita.com/yuku_t/items/208be188eef17699c7a5

Nested Loops

Nested Loopsは入れ子のループを扱うアルゴリズム。
https://nishinatoshiharu.com/overview-nested-loopjoin/

TableAとTableBがあった場合に、結合対象となるTableAを一行ずつループする。これを駆動表や外部表と呼ぶ。もう一方のTableBを内部表と呼ぶ。駆動表の1行について、内部表を1行ずつスキャンして結合条件に合致すればそれを返却する。これを駆動表すべてに繰りかえすというアルゴリズム。

以下が特徴

  • TableAとTableBの行数をかけたものがアクセスされる行数。実行時間はこれに比例。
  • ひとつのステップで処理する行数が少ないためHash、Sort Mergeに比べてメモリを消費しない
  • どの DBMS でも必ずサポートしている

TableAとTableBのどちらのテーブルを駆動表にするかが性能のカギを握っている。

内部表の結合キーの列にインデックスが存在するという前提を満たす場合、駆動表が小さいほど性能が良くなる

内部表の結合キーの列にインデックスが存在する場合、インデックスを参照することによってループある程度スキップできる。逆に言えば内部表のループを大きくしてインデックスによるループをスキップのさせようという話。

結合キーが内部表に対して一意でない場合は、インデックス出ない行にアクセスする場合であっても内部表がヒットする可能性がある。、この場合はヒットした複数行に対してループする必要があり、ループの回数が多くなり性能は悪くなる。

Hash

入力に対してなるべく一意性と一様性を持った値を出力する関数をハッシュ関数と呼びます。ハッシュ結合はまだ小さいテーブルをスキャンして結合金に対してハッシュ関数を適用することでハッシュ値に変換します。その次にもう一つの大きなテーブルをスキャンして結合きりがそのハッシュ値に存在するかどうかを調べるという方法で結合を行う。

特徴は以下。

  • 結合テーブルからハッシュテーブルを作るためにNested Loopsに比べるとメモリを多く消費する
  • メモリ内にハッシュテーブルが収まらないとストレージを使用するため遅延する
  • 出力となるハッシュ値は入力生の順序を保存しないため等値結合でしか使用できない

Hashが有効なケースとしては次が考えられる。一言で言えばNested Loopsが効率的に動作しない次善策。

  • Nested Loopsで適切な駆動表、すなわち十分に小さいテーブルが存在しない場合
  • 小さいテーブルは存在するがない内部表のヒット件数が多い場合
  • Nested Loopsの内部表にインデックスが存在しない場合

ハッシュ結合では両方のテーブルのレコードを全件読み込む必要があるためテーブルのフルスキャンが採用されることが多い><.

Sort Merge

Nested Loopsが非効率だった場合Hashと並んで選択肢になるのがSort Mergeというアルゴリズム。

結合対象のテーブルをそれぞれ結合キーでソートを行い一致する結合器を見つけたらそれを結果セットに含めるというもの。

特徴は以下

  • 対象テーブルをどちらも相当するためメモリを消費するメモリ不足のTEMP落ちも起きるかも
  • ハッシュと違い等値結合だけじゃなく不等号でも利用できる。ただし否定条件では利用できない。
  • テーブルをソートするため片方のテーブルを全てスキャンしたところで結合を終了できる。

テーブルの相当スキップできるかなり例外的なケースで考慮されるが基本的にはNested LoopがHashが使われる。

shira79shira79

インデックス

RDSのチューニングにおいて indexは 最もポピュラーな方法。アプリケーションの変更が不要で純粋にデータベースが伸びる性能を改善できる利便性の高さと効果の高さ。

https://dev.mysql.com/doc/refman/8.0/ja/mysql-indexes.html

インデックスを使わない場合は、線形探索になる。

rdb で使われるインデックスには三つある

  • B-treeインデックス
  • ビットマップインデックス
  • ハッシュインデックス

一般的に使用されているのがB-tree。(Mysqlでも)

B-treeインデックス

https://qiita.com/kiyodori/items/f66a545a47dc59dd8839

いいかんじのYoutube動画
SQL を速くするインデックス入門 : B-Tree や複合インデックスが理解できる

データベースにおいてインデックスといえばB-treeインデックスを指すくらい。B-treeが、検索のアルゴリズムとしては飛び抜けて性能がいいわけではないが、rds における主力である理由はバランスの取れた秀才型でであることによる。

実際には多くのデータベースではツリーのリーフノードにだけキー値を保存する B+treeというB-treeの修正バージョンに対応している(Mysql含む)。とは言え本質的な特徴は B+treeもB-treeも変わらない。

インデックスを有効活用するためにはいくつかのポイントを考慮する必要がある。

インデックスを作成するときのポイント

カーディナリティと選択率

カーディナリティとは値のばらつき具合を示す概念。最も高いのはユニークキー。最も低いのは値が1種類の場合。
選択率とは、特定の列の値を指定した時に行のテーブル全体の母集団からどの程度絞り込めるかを示す概念。

index を作成する奴集合の条件は二つの指標から判断する

  • カーディナリティが高いこと
  • 選択率が低いこと(少ない行に絞り込めること)

選択率の低さの閾値は、ストレージ性能などの条件によっても異なるが最近の dbms ではだいたい5から10%前後というのが目安。つまり5%未満に絞り込める条件ならその列2合に対してはインデックスを作る価値があるかもしれない。それ以上の場合はフルスキャンの方が早い可能性がある。

インデックスによる性能向上が難しいケース

絞り込み条件が存在しないパターン

テーブルフルスキャン以外ありえない。おそらくバッチ処理なのであるかもしれない。

ほとんどレコードを絞り込めないパターン

これが最も合って厄介なパターン.
なんらかの絞り込みパターンの結果、テーブル1億行の中から8000万件ほどの結果が得られるパターンがあったとする。この場合の選択率は80%。インデックスが使われたとしてもフルスキャンよりは遅くなる可能性が高い。インデックスが有効なのは大きくレコードを絞り込める検索条件が存在する場合だけ。

また入力パラメーターによって選択率が変動する場合も問題。
注文を店舗で絞り込む場合、大型店舗と小規模店舗で選択率が変わってくる。

SELECT COUNT(*) FROM Orders WHERE shop_id = :sid;

選択率が大きい場合フルスキャンが好ましく、小さい場合は、インデックスが好ましい。

オプティマイザーが前者についてフルスキャンを後者についてはインデックスのレンジスキャンを選択してくれる場合がそうはいかないパターンもある。

インデックスが使えない検索条件

中間一致、後方一致のLIKE述語

インデックスを使用できるのは前方一致のみ。どれだけ選択率の良い検索条件であってもフルスキャンを使わなくちゃいけなくなる。

索引列で演算を行っている

SELECT * FROM Sometable WHERE col_1 * 1.1 >  100;

上記のような文は、以下のように条件の右側で式を用いればインデックスが使用される。

SELECT * FROM Sometable WHERE col_1  >  100/1.1;

#### IS NULLを使ってる
NULLに対する検索条件でインデックスが使用されないのは通常索引データの中にNULLできたとしてもは存在しないから。

#### 否定型を用いている
否定型(<>,!=,NOT IN)は。インデックスを使用できない。

IS NULLは使われる。否定形はいまどうなんだろう??><
https://techblog.istyle.co.jp/archives/1514

インデックスが使用できない場合の対処

アプリケーション設計で対処

例えば選択率が低くなる可能性がある検索条件が指定された場合、セットで別の列の検索も押すことができないという必須入力制御が行われていれば絞込みがかなり効くようになる。

どういうクエリが投げられるかはアプリケーションの機能と UI 設計に大きく依存する。そのためどういう UI でどういう入力制限を設けるかをユーザーや業務がのエンジニアと一緒になって考えなきゃいけない。

インデックスオンリースキャン

インデックス Only スキャンは名前の通りインデックスを使った高速化の一手段ではあるのですが使い方は従来のインデックスの利用法とは大きく異なります。

この SQL はフルスキャンにはなるが、その対象をテーブルからインデックスに変えることができる

SELECT order_id, recieve_date FROM Orders;

order_id, reciieve_dateの2列は、select 句に含まれているだけなので通常はインデックスの列候補にはならない。しかしこの2列をカバーするインデックスが存在することでインデックスだけをスキャン対象にするような検索、インデックスオンリースキャンが可能になる。いわば SQL 文に必要な列をインデックスだけで充足できる場合にテーブルへのアクセスとスキップすることでI/Oを削減する。

注意点としては以下

  • 一つのインデックスに含められる列数には限度がある.(インデックスのサイズは無制限ではなく頭痛やサイズに上限が決められている、またインデックスのサイズが大きくなるとI/Oを減らすという当初の目的に対する効果が薄くなってしまうので意味がなくなる。)
  • 更新のオーバーヘッドが増える
  • SELECT句に新たな列が追加されたら使えない
CREATE INDEX covering_index_sample On Orders(order_id, reciieve_date);
shira79shira79

インデックスついて(本の内容以外)

複合インデックスは順番が大事^^。 複合インデックスはカラム1つ目、2つ目..の順で使われる。(2つ目以降を最初の条件に使うことはできない。)
https://qiita.com/Sayatam/items/9c1f125cc97b9e9183a4

むやみやたらにインデックスをつくると更新時のコストが上がってしまう。テーブルのデータが更新された場合、インデックスも更新しなくちゃなため。
https://recruit.gmo.jp/engineer/jisedai/blog/mysql-index-training/

パラメーター設定のベストプラクエティス(AWS RDS for Mysql)
https://aws.amazon.com/jp/blogs/news/best-practices-for-configuring-parameters-for-amazon-rds-for-mysql-part-1-parameters-related-to-performance/

innodb_buffer_pool_size
テーブルおよびインデックスデータをキャッシュするメモリ領域のサイズ (バイト単位) を決定

shira79shira79

以下の3つはまた時間のある時にw
7章・サブクエリ
8章・SQL における順序
9章・更新とデータモデル

このスクラップは2022/04/27にクローズされました