『達人に学ぶDB設計徹底指南書』読書メモ: 後半

[前半](https://qiita.com/arene-calix/items/0a1a90bd682b5cc2a156)の続きです。

## 要点まとめ: 後半
前半と同じく、コードブロックに素のテキストを流し込みます。
(個人的には下手なマークダウンよりプレーンテキストの方が見やすいと思っています)

```
## 5章: 論理設計とパフォーマンス
正規化とSQLの処理速度
  検索SQL: 遅くなる。テーブル結合のコストが大きい。
  更新SQL: 速くなる。データの冗長性が排されているため、無駄な更新せずにすむ。

正規化と非正規化
  整合性と検索速度は強いトレードオフ関係
    正規化すると、データ不整合が起こりにくくなる反面、検索SQLが遅くなる
    非正規化すると、検索SQLは早くなるが、データ不整合が起こりやすくなる
  正規化 vs 非正規化は、人によって意見が分かれるポイント
  筆者の立場は以下の通り
    原則として非正規化は許さない。
    他の手段によってパフォーマンス向上が計れないか最後の最後まで検討してください。
    非正規化は、いよいよ切羽詰ったときに取る、最後の手段(しかも劇薬)なのです。

非正規化により検索速度を向上させるパターン
  例(第3正規形を満たした形 / これを非正規化して検索速度を向上させる)
    [受注テーブル]
    受注ID(pk) 受注日     注文者
    --------------------------------
    001       20200303  山田一郎
    002       20200505  田中二郎
    003       20200707  中野三郎
    004       20200909  野村四郎

    [受注明細テーブル]
    受注ID(pk)  注文明細連番(pk)  商品名
    ----------------------------------------
    001        1                紅茶
    001        2                マカロン
    001        3                オリーブオイル
    002        1                クッキー
    002        2                プリン
    003        1                鰹節
    004        1                ワイン
    004        2                ウイスキー
    004        3                ウォッカ
  
  非正規化パターン1: 冗長なサマリデータを持たせる
    受注毎の商品数を知りたいとき、元のテーブルだと、2テーブルを結合する必要がある。
    以下のようにサマリ列をもたせると、1テーブルで検索できる。
    
    [受注テーブル#2]
    受注ID(pk)  受注日     注文者   商品数
    ---------------------------------------
    001        20200303  山田一郎  3
    002        20200505  田中二郎  2
    003        20200707  中野三郎  1
    004        20200909  野村四郎  3
    ※上記は第二正規形({受注日} -> {商品数}に推移的関数従属がある)

  非正規化パターン2: 冗長な検索条件を持たせる
    特定期間に受注された商品を知りたいとき、元のテーブルだと、2テーブルを結合する必要がある。
    以下のように検索条件をもたせると、1テーブルで検索できる。
    
    [受注明細テーブル#2]
    受注ID(pk) 注文明細連番(pk)  商品名         受注日
    --------------------------------------------------------
    001        1               紅茶　　　　    20200303
    001        2               マカロン　　     20200303
    001        3               オリーブオイル 　 20200303
    002        1               クッキー　　     20200505
    002        2               プリン　　　     20200505
    003        1               鰹節　　　　    20200707
    004        1               ワイン　        20200909
    004        2               ウイスキー　     20200909
    004        3               ウォッカ　　　　  20200909
    ※上記は第一正規形({受注ID} -> {受注日}の部分関数従属がある)
  
  正規化は、可能な限り高次にすることが大原則(強調)ではあるが、
  実務における論理設計では性能のために非正規化が必要になる場面が出てくる。
  
  正規化は教科書的/機械的にできるが、
  非正規化は、様々なトレードオフを考慮しながら慎重に行う必要がある、難しい作業。
  
非正規化のリスク
  更新速度の低下
    非正規化によりデータが冗長になるため、更新処理が増える
      ↑の例でいうと、
      受注テーブル#2更新時に、受注明細テーブルBの商品数を集計する必要がある
      受注明細テーブル更新時に、受注テーブル#2も更新する必要がある
  データのリアルタイム性の低下
    サマリデータを即時更新しない場合、
    実データの更新がサマリデータへ反映されるまでにラグが生じる
  設計変更による手戻り
    最初に正規化した状態でリリース -> 性能問題が表出 -> 大改修!
      もちろん、非正規化 -> 正規化の場合も同様の問題が起きる
      論理設計するときは「システムの品質は今ここで決まる!」という気持ちで臨もう

論理設計に潜む"物理"
  論理設計を担当する人間は、単に正規化の理論を理解しているだけでなく、
  上述のトレードオフを熟知し、要件に叶った平衡点を探し出せる能力が必要
  (高い水準の能力が要求される)
  
  パフォーマンスを考慮して論理設計を進めるためには
  残念ながら、どうしても物理設計の知識が必要
  => 次章へ続く




## 6章: データベースとパフォーマンス
DBのパフォーマンスを決める主な要因
  ディスクのI/O分散(RAID) // 既出
  SQLにおける結合(正規化)　// 既出
  インデックス            // 本章で説明
  統計情報              // 本章で説明

インデックス
  なぜインデックスによるパフォーマンス改善が大事なのか
    アプリケーションのコードに影響を与えない(アプリケーション透過的)
    テーブルのデータに影響を与えない(データ透過的)
    それでいて性能改善の効果が大きい
  
  インデックス概説
    キーとデータの配列(js的に書くとdata1 = index[key1])
    効率よくテーブルの実データにアクセスするために使われる
    
    以下の性質が求められる
      均一性　　 各キー値の間で検索速度にバラツキが少ない
      持続性　　 データ量増加に対するパフォーマンス低下が少ない
      処理汎用性 CRUD全てにおいて処理が速い
      非等値性　 不等号を使った検索が速い
      親ソート性  ソートが必要なSQLを高速化できる
    
    いくつか種類はあるが、基本B-Treeしか使わない
      B-Treeインデックス
        5段階評価で全項目4のオールラウンダー
      ビットマップインデックス
        good: OR条件に使える、カーディナリティの低い列でも検索性能が良い
        bad : 更新性能が悪い
      ハッシュインデックス
        good: 等値検索はO(1)
        bad : 等値検索にしか使えない
    
  B-Treeの特徴
    平衡木(Balanced Tree)になっている
      ルートからリーフの距離が、どのリーフもおおむね同じ      　　　　　  (=均一性)
    計算量はO(log n) <-> テーブルフルスキャンはO(n)
      CRUDすべてO(log n)                      　　　         (=処理汎用性)
      log nなのでデータ量が増えても計算量は増えにくい     　　　　　  (=持続性)
    構築時にキー値をソートする
      不等号で検索した場合、欲しいデータが、特定のノードより左か右か分かる (=非等値性、親ソート性)
  
  B-Treeの扱い方
    むやみに作らない
      テーブル更新時にDBMSがインデックスをメンテするため、張りすぎると更新性能が悪くなる
      主キー列、一意制約列の場合自動作成されるので構築不要
    
    大規模なテーブルに対して作成しよう
      理由: nが小さい場合、O(n) < O(log n) だから
    カーディナリティ(≒データのばらつき)の高い列に作成しよう
      例えばBooleanの列に設定しても効果は薄い
      (複合インデックスは列の組み合わせでカーディナリティを考えるため、(Int, Char, Boolean)は効果あり)
    SQLで使われる列に作成しよう
    
    定期的に再構築するのが望ましい
      理由: 挿入、更新、削除を繰り返すと非平衡木になり、性能劣化するため
    
  インデックスが使われないSQL
    値を加工(演算、関数適用)している
      SELECT * FROM tbl1 WHERE percent * 100 > 70;
      SELECT * FROM tbl1 WHERE TO_DATE(start_time) < '20200909';
      
    IS NULL、否定形、OR、後方一致・中間一致のLIKEを使っている
      SELECT * FROM tbl1 WHERE score IS NULL;
      SELECT * FROM tbl1 WHERE score <> 100;
      SELECT * FROM tbl1 WHERE score < 40 OR 60 < score;
      SELECT * FROM tbl1 WHERE name LIKE '%taro';
      SELECT * FROM tbl1 WHERE name LIKE '%da%'; -- ◯田さんを取得

統計情報
  SQLを叩いた時、DBMSがやっていること
    パーサがSQLの構文をチェック
    オプティマイザが統計情報を参考に、実行計画(データの取得経路)を立てる
    実行計画に従って実データにアクセス
    取得結果を加工し、ユーザに返す
    
  統計情報ってどんなデータ?
    ざっくり言えばテーブルのメタ情報
      各テーブルのレコード数、列数
      各列のサイズ、カーディナリティ、値の分布、NULLの数
      インデックス情報
  
  統計情報の扱い方
    データが大きく更新された後、なるべく早く収集する
      理由: 統計情報が古いと、間違った情報を元に実行計画を立ててしまい、SQLが遅くなるため
    原則夜間に収集する
      理由: 相当リソースを喰ううえ、数時間かかるケースもあるため
    データが更新されていないテーブルは収集しなくてOK
      理由: 収集時間を短くするため
    
    実行計画を固定させたい場合は、あえて統計情報を凍結することもある
      結合を使うSQLは、データ量によって結合アルゴリズムが変わる場合が多い
      データ量が増えた結果、結合アルゴリズムが変わり、検索性能がガタ落ちする...はあるあるらしい
      (MySQLの場合、結合アルゴリズムが1つしかないので起こらない現象)
      
      これを防ぐため、サービス終了時に想定されるデータ(量、分布)を用意したうえで統計情報を収集し、
      以後統計情報を変えない、という手法が存在する
      DBMSによっては統計情報をロックし、読み取り専用にすることもできる





## 7章: 論理設計のバッドノウハウ
バッドノウハウとは
  やっちゃいけない設計
  正気の沙汰じゃない(と感じるべき)

いろいろなバッドノウハウ
  非スカラ値
    例
      id(pk)  parent children
      ------------------------
      1       jon    job, alice
      2       bob    ben, tom, wendy
    どんなテーブル?
      1セルに複数の値が入っている
    何が悪い?
      第一正規形すら満たしていない

  ダブルミーニング
    例
      id(pk) name value
      ------------------
      1      jon  23     <- 年齢
      2      bob  45     <- 年齢
      3      tom  93     <- 体重
    どんなテーブル?
      列の意味が行ごとに違う
    何が悪い?
      列の意味が不明確になる
    格言
      列≠変数

  単一参照テーブル
    例
      code_type(pk) code_name(pk) value
      -----------------------------------
      employee      E00001        jon
      employee      E00002        tom
      company       C00001        apple
      company       C00002        google
      item          I00001        apple
      item          I00002        banana
    どんなテーブル?
      各種コードを集約したテーブル
      結合祭りを避ける目的で作成
      (ダブルミーニングの類似系)
    何が悪い?
      余裕を見てかなり長めの可変長文字列型を使う必要がある
      コード体系の種類と量が多くなると、あらゆる検索クエリが遅くなる
      うっかりコードを間違えて使ってもエラーにならないため、バグに気づきにくい
      ER図の可読性を下げる(モデルとして不正確)
    格言
      テーブルにポリモーフィズムはいらない

  水平分割
    例
      [t_value_1991]
      id(pk)   date           value
      ------------------------------
      1        19910101 10:20 200
      2        19910102 12:30 220
      (大量データ)
      9643782  19911230 20:44 2300
      
      [t_value_1999]
      id(pk)   date           value
      ------------------------------
      1        19990101 10:20 20
      2        19990102 12:30 310
      (大量データ)
      53523525 19991230 20:44 63
    どんなテーブル?
      大量データをレコード単位で分割したテーブル郡
      データ量増大に伴うI/O増大を回避する目的で作成
    何が悪い?
      分割する意味的な理由がない
      拡張性に乏しい
        経年変化をあとから分析したくなったら超大変
        1年ごとにテーブル名が変わるので、場合によってはアプリ改修が必要
      代替手段がある
        パーティション(同一テーブル内で、物理的な格納領域を分散)
        マテリアライズドビュー(実体化されたビュー)

  垂直分割
    例
      [employee1]
      id(pk)    name
      --------------
      E0001     jon
      E0002     bob
      
      [employee2]
      id(pk)    age
      --------------
      E0001     23
      E0002     33
    どんなテーブル?
      同じエンティティのデータを列単位で分割したテーブル郡
      SQL文がアクセスするデータ量を減らす目的で作成
    何が悪い?
      分割する意味的な理由がない
      代替手段がある
        集約
          元テーブルの一部列だけを抽出した別テーブルを作る手法
          集約により作られた小規模なテーブルをデータマートと呼ぶ
          元テーブル -> データマートへの、データ同期が必要
          同期頻度(データ鮮度)と同期コスト(サーバ負荷)はトレードオフ

  不適切なキー
    例
      email(pk)    name
      ------------------
      aaa@bbb.com  jon
      ccc@ddd.com  bob
    どんなテーブル?
      可変長文字列型をキーに使ったテーブル
      (名前やメアドなど可変長列然とした値をキーにしているケースを想定)
    何が悪い?
      キーが不変性を備えていない
    
  ダブルマスタ
    どんなテーブル?
      同じものを指し示すマスタテーブル郡(筆者の造語)
      システム統廃合で起きることが多い
    何が悪い?
      マスタテーブルをマージする必要があるため、SQLが複雑になる
      マージ=結合やUNIONなので、当然パフォーマンスも悪化する

バッドノウハウのどこが悪いのか?
  可読性が悪い→開発効率悪化→工数増大、納期逼迫→バグ祭り
  設計変更が難しい
  ひどいデータ構造をもとに綺麗なプログラムを作ることは不可能
  (データ構造がコードを決めるのであって、その逆ではない)


## 8章: 論理設計のグレーノウハウ
グレーノウハウとは
  違法すれすれの「ライン上」に位置する設計(筆者の造語)
  利点欠点を理解した上で、用法用量を守って利用しましょう

いろいろなグレーノウハウ
  代理キー(サロゲートキー)
    例
      id(pk) code value
      ------------------
      1      C001 abc
      2      C002 cde
    どんなもの?
      入力データに存在するキーの「代理」として設定する人工的なキー(ex. 連番)
      対義語は自然キー
    メリット
      自然キーを主キーに選んだ場合に起きる不都合を回避できる
        パターン1: 入力データに主キーにすべき一意なキーがない
        パターン2: 一意キーはあるが、値が循環する (ex. コード体系がC001〜C999で、桁数を拡張できない)
        パターン3: 一意キーはあるが、途中で指す対象が変わる (ex. 歯抜けが許されないコード体系)
      純粋にシステム側の都合だけで値を設定できる(仕様調整不要＆仕様変更の影響を受けない)
      主キーが複合キーとならないため、WHERE句がシンプルになる
    デメリット
      論理的には不要なキーであるため、論理モデルが分かりにくくなる
      (本質的に、使わなくても何とかなる道具)
    回避策
      パターン1は打つ手なし
      パターン2, 3は時刻を主キーに追加すれば自然キーとして問題なく使える
        タイムスタンプ(ex. 登録日、登録年度)を追加
        インターバル(ex. 開始日・終了日)を追加
    
  列持ちテーブル
    例
      [employee_col]
      employee_id(pk) name child1 child2 child3
      -------------------------------------------
      E0001           jon  bob    alice  tom
      E0002           ben
      E0003           greg karen
    メリット
      シンプル＆直感的
      入出力のフォーマットと合わせやすい
    デメリット
      列の増減が難しい
      無用のNULLを使わなくてはならない
    回避策
      行持ちテーブルを使う
      [employee_row]
      employee_id(pk) branch_number(pk) child_name
      -------------------------------------------
      E0001           1                 bob
      E0001           2                 alice
      E0001           3                 tom
      E0003           1                 karen
    列持ち→行持ち変換SQL
      SELECT employee_id, 1, child1 FROM employee_col WHERE child1 IS NOT NULL
       UNION ALL
      SELECT employee_id, 2, child2 FROM employee_col WHERE child2 IS NOT NULL
       UNION ALL
      SELECT employee_id, 3, child3 FROM employee_col WHERE child3 IS NOT NULL
      ;
    行持ち→列持ち変換SQL
      SELECT employee_id
             , MAX(CASE WHEN branch_number = 1 THEN child_name ELSE NULL END)
             , MAX(CASE WHEN branch_number = 2 THEN child_name ELSE NULL END)
             , MAX(CASE WHEN branch_number = 3 THEN child_name ELSE NULL END)
        FROM employee_row
       GROUP BY employee_id
      ;
  
  アドホック(場当たり的)な集計キー
    例
      [prefectures]
      id(pk) name  population additional_code
      ----------------------------------------
      1      北海道 5,500,000  01
      2      青森　 1,300,000  01
      22     愛知　 7,400,000  02
      23     三重　 1,900,000  02
      36     徳島　 1,100,000  03
      37     香川　 1,200,000  03
    どんなもの?
      GROUP BYの集計キーにするためだけに、場当たり的に列を追加する設計
      DWH分野の論理設計でよく問題になる
      (↑では、地方ごとの集計のためregion_codeを追加した想定。地方マスタテーブルは存在しない)
    メリット
      さくっと集計キーを増やせる手軽さ
    デメリット
      (安易に導入する分)短いスパンでコード体系が変わったり、別のコード体系が追加される
      列がどんどん増えていって、パフォーマンスが劣化する
    回避策
      キーを別テーブルに分離する
        結合が必要なので、パフォーマンス改善にはならない
      ビューを使う
        オリジナルのテーブル + アドホックなキーを足したビューを定義
      SQLベタ書き
        SELECT CASE WHEN id IN(1, 2)   THEN '01'
                    WHEN id IN(22, 23) THEN '02'
                    WHEN id IN(36, 37) THEN '03'
               ELSE NULL END AS additional_code
               , SUM(population)
          FROM prefectures
         GROUP BY CASE WHEN id IN(1, 2)   THEN '01'
                       WHEN id IN(22, 23) THEN '02'
                       WHEN id IN(36, 37) THEN '03'
                  ELSE NULL END
        ;
  
  多段ビュー
    どんなもの?
      ビュー1 -> ビュー2 -> ビュー3 -> テーブル
      ...みたいな状態。
    デメリット
      SQLのパフォーマンスが悪くなる
        ビューは「クエリの缶詰」。実行時にSELECT文に展開される。
        多段ビューを使うと、(DBMSの実装にも寄るが)多段サブクエリ的なことになってしまう
        マテビューを使えばこの問題はなくなるが、データ同期の問題が出てくる
      テーブルとビューの依存関係が分かりにくくなる


## 9章: 一歩進んだ論理設計(SQLで木構造を扱う)
木構造はRDBの苦手分野
手段が無いわけではないが、これを使えば万事OK! みたいなモデルは無い
(本書初版が2012年と古いため軽くググってみたが、まだ解決はしていなそう)

  隣接リストモデル
    特徴
      昔からある方法
      更新、参照のクエリが極めて複雑になる(パフォーマンスも悪い)
    例
      child(pk) parent
      -----------------
      person0   NULL     <- ルートノード
      person1   person0
      person2   person0
      person3   person1
      person4   person2
      
  入れ子集合モデル
    特徴
      木構造を入れ子の円(集合)として捉えたモデル
      数直線上に各ノードの始点終点をマッピングし、集合の入れ子関係で、ノードの親子関係を表す
      検索しやすいが、更新しにくい
      1                                    14
      <-------------------------------------> ←ルートノード
       2    3 4                          13
       <----> <--------------------------->   ←子ノード(第1世代)
                5        8 9   10 11  12
                <--------> <----> <---->      ←子ノード(第2世代)
                  6    7
                  <---->                      ←子ノード(第3世代)
    例
      [nodes]
      node(pk) start end
      ----------------------
      node1    1     14
      node11   2     3
      node12   4     13
      node121  5     8
      node1211 6     7
      node122  9     10
      node123  11    12
      
    ルートを求める
      SELECT *
        FROM nodes
       WHERE start = 1
      ;
    リーフ(=自分の中に円を含まないノード)を求める
      SELECT *
        FROM nodes AS parent
        WHERE NOT EXISTS (
                -- 内部にchildを含むノードを除外
                SELECT *
                  FROM nodes AS child
                WHERE parent.start < child.start
                  AND parent.end   > child.start
              )
      ;
    ノードの深さ(=自分を包含するparentが何個あるか)を求める
      SELECT child.node, COUNT(parent.node) AS depth
        FROM nodes AS parent INNER JOIN nodes AS child
          ON child.start BETWEEN parent.start AND parent.end
        GROUP BY child.node
      ;
    ノードの追加(SQLは割愛)
      親ノードの円を広げる→空いたスペースに新しい円を追加...と結構な手間
      更新対象と無関係な円の座標も連動して更新せねばならない点が厄介
      
    ノードの削除
      リーフの削除は、単に消すだけ
      子ノードは残して親ノードを消す場合も、単に消すだけ
      子ノード + 親ノードをまとめて消す場合、以下ように内部円も削除する
      DELETE FROM nodes
       WHERE start BETWEEN (SELECT start FROM nodes WHERE node = '親ノード')
                       AND (SELECT end   FROM nodes WHERE node = '親ノード')
      ;
      
  入れ子区間モデル
    特徴
      入れ子集合モデルの実数版
      実数を使うことで、入れ子集合モデルの「更新時に円を広げる必要がある」問題を克服できる
      あくまで理論上の話(コンピュータにおける実数は有限なので、どこかで破綻する)
  
  経路列挙モデル
    特徴
      ノードをディレクトリとみなし、絶対パスをDBに保存する
      検索のパフォーマンスが良い(ユニークインデックスが効く)
      更新のパフォーマンスが悪い(文字列操作祭りになる)
      => 更新が少なく、大量データの高速な検索が必要なケースに向いている
    例
      [nodes(文字列版)]
      node(pk)  path
      -------------------------------
      node0     /node0/
      node1     /node0/node1/
      node2     /node0/node2/
      node3     /node0/node1/node3/
      node4     /node0/node1/node4/
      
      [nodes(数値版)]
      node(pk)  path
      -------------------------------
      node0     .1.
      node1     .1.1.
      node2     .1.2.
      node3     .1.1.1.
      node4     .1.1.2.

```

## 最後に
本書は2012年初版とけっこう古いですが、そうそう枯れる内容ではないため、
未読の方は一度読んで見ることをおすすめします。

これに加えて『DB設計デザインパターン』みたいな本があると最高なんですが、どなたか知らないでしょうか?
(ユーザー情報、履歴情報など、よくある要件を満たす適切なテーブル設計のカタログが欲しい)