勉強日記

毎日投稿

SQL Antipatterns ch5 Keyless Entry

pragprog.com


Make your database mistake-proof with constraints.

Keyless Entry

  • FK制約を使わなかったところDBに齟齬が生じた話
  • 品質管理スクリプトを定期実行
    • 孤立した子レコードを探し、見つけたらメール通知
    • レコードが増えるにつれ処理時間もレポート内容も長くなっていった...
  • 真に必要だったのは、不正な入力があった時点で早々にアプリケーションを落とすこと

Objective: Simplify Database Architecture

  • 参照整合性は、DB設計やDB運用において重要な位置をしめる
  • これを確保するのがFK制約
  • しかし下記理由をつけて忌避されることがある
    • データ更新が制約とぶつかる
    • 柔軟な設計につき、FK制約を適用できない
    • 暗黙に作成されるインデックスがパフォーマンスに悪影響を及ぼす
    • FKをサポートしていない製品を使用している
    • FK宣言のシンタックスをいちいち調べなければならない

Antipattern: Leave Out the Constraints

  • メリット
    • 設計の単純化
    • 柔軟性の向上
    • 高速化
  • デメリット
    • 参照整合性を自前で確保しなければならない

Assuming Flawless Code

  • アプリケーション側で参照整合性の確保を自前実装しなければならない
    • INSERT前に親をSELECT
    • DELETE前に子をSELECT
  • ロック等しない限り、race condition (競合状態)にはなりうる

One in a million is next Tuesday. (Gordon Letwin)

  • ロックは並列制御やスケーラビリティと相性悪い

Checking for Mistakes

  • 孤児レコードを探す
    • LEFT OUTER JOINで駆動表側がNULLになる行 = 内部表側が孤児
  • 疑問
    • どれだけの頻度で実行すればいいの?
    • 見つかったらどうすればいいの?修正できる?
  • そもそも孤児が生じないのが一番

"It's Not My Fault!"

  • DBのデータはつねに一貫性のある状態でなければならない
    • アプリケーションコードに変更を加えた後でも
    • DBを直接触った後でも

Catch-22 Updates

  • 親子を別々に更新できなくなることがある
    • 親を更新しないと子を更新できない
      • 子は親にない値に変更できない
    • 子を更新しないと親を更新できない
      • 親は子から参照されている値を変更できない

How to Recognize the Antipattern

  • こんなのが聞こえてきたら注意
    • 「一方のテーブルに存在する値が、他方のテーブルに存在しないことを確認するには、どうクエリすればいい?」
      • 孤児レコードを探そうとしている
    • 「INSERTしようとしている値が他方のテーブルに存在することを確認する高速な方法は?」
      • 親レコードが存在することを確認しようとしている
      • FK使え
    • 「FKはDBを遅くするから使うなと習った」
      • より大きな問題を生じる
        • パフォーマンス問題が生じることも

Legitimate Uses of the Antipattern

  • 製品がFK制約をサポートしていない場合
  • FK制約を適用できない、柔軟な設計の場合

Solution: Declare Constraints

  • FK制約使え
    • アプリケーション/DB直操作に共通の制限をかけられる
    • コード減る
      • バグも減る

Supporting Multitable Changes

  • 複数テーブルの更新をAtomicに行える
    • 親子同時更新
      • "Catch-22 Updates"にて挙げた、「親子を別々には更新できない状況」の打破
  • ON UPDATE/ON DELETE句を利用可能
    • テーブル追加時なども、アプリケーションコードの変更不要

Overhead? Not Really

  • 少しのオーバーヘッドがあるのは確か
  • だが、トータルで見るとむしろ効率が上がる説
    • INSERT/UPDATE/DELETE前のSELECT確認が不要に
    • 複数テーブル更新時のロックが不要に
    • 孤児レコードの修正のための定期スクリプトが不要に

SQL Antipatterns ch4 ID Required

pragprog.com


Conventions are goot only if they are helpful.

ID Required

  • 交差テーブルにサロゲートキーidをつけてしまい、エンティティの関連が重複してしまう

コラム: Do I Really Need a Primary Key?

  • 主キーがないと
    • 重複チェックを自前で書く必要がある
      • HAVING COUNT(*) > 1
    • 重複が見つかったらどうするの
  • 主キーのないテーブルは、タイトルのないMP3集のようなもの
    • 音楽は聴ける
    • が、聴きたいものは探せないし重複も防げない

Objective: Establish Primary Key Conventions

  • すべてのテーブルに主キーを持たせようという目的やよし
  • しかし主キーについての誤解がアンチパターンを生む
  • 主キーの選定は難しい
    • あらゆる属性値が重複しうる
      • 「名前」は教科書的な例
      • eメールアドレスや社会保障番号とて厳密にユニークではない
        • 【補】ISBNなんかは運用をしくじって一意性を欠いているらしいですね
  • ドメインモデル上意味のない人工的な値が必要に
  • 方言が激しいが自動増加整数が有用
    • ドランザクションの外側で管理
    • Abort時も巻き戻らない

Antipattern: One Size Fits All

  • 主キーとサロゲートキーとの混同
    • idなる32bitないし64bit整数の自動増加カラム=主キーという誤解
  • すべてのテーブルにidカラムを追加してしまうと...

Making a Redundant Key

Allowing Duplicate Rows

  • 交差テーブルでやらかすやつ
  • (複合)自然キーにUNIQUE制約を付けなかったためにテーブルの意味が変わってしまう
    • 関連の重複が許されてしまう
  • UNIQUE制約をつければ重複を回避できるが、サロゲートキーは冗長となる

Obscuring the Meaning of the Key

  • idでは何を特定するものなのか読み取れない
  • あるエンティティのレコードを特定するものなれば、カラム名にエンティティ名を盛り込むべきである
    • 例: bugsエンティティのIDならばbug_id

Using USING

  • JOIN ONのショートハンド的なやつ
  • 同じ名前のカラムを=で結合
  • idという名前を使ってしまうと運用できなくなる
    • PKとFKとで名前被りするから

Compound Keys Are Hard

  • 「複合キーは扱うのが大変だ」という主張
  • 数学者が2次元や3次元を扱うのを面倒くさがって数直線しか使わないようなもの
    • 世界を正しく表現できない

コラム: Special Scope for Sequences

  • 自動増加キーを使わないと、下記クエリを複数のクライアントで発行するとnext_bug_idに重複が生じうる
SELECT MAX(bug_id) + 1 AS next_bug_id FROM Bugs;
  • 自動増加キーを使い、「最後の番号」を意味する関数を呼び出すことで回避可能
    • MySQL: LAST_INSERT_ID()
    • ほかベンダー方言

How to Recognize the Antipattern

  • こんなのが聞こえてきたら注意
    • 「このテーブルに主キーは必要ないと思う」
      • おそらく「主キー」という言葉をサロゲートキーと混同している
        • 「自然キーでよくない?」という意味合いだろう
    • 「多対多の関連で重複データが得られてしまったんだが?」
      • 交差テーブルにサロゲートキーを追加し、かつ自然キー(外部キーのペア)にUNIQUE制約を付けなかったおそれがある
    • 「DB理論によると、値はルックアップテーブルに置いてIDで参照すべきとのことだが、毎度JOINしなければならないのは嫌だ」
      • 正規化理論を誤解している
        • 【補】正規化は自然キーに対して行うもの
          • さらにいうと主キーではなく「候補キー」に対して行うもの

Legitimate Uses of the Antipattern

  • CoCなフレームワークのConventionに乗っかるとき
    • とはいえ主キー名をoverrideできるのが普通
  • 主キーが長すぎる場合
    • 例: パス列挙モデル
      • バスは自然キー
      • 主キーにするには長過ぎる

Solution: Tailored to Fit

  • 主キーと自動増加整数とは独立した概念である
    • 主キーはデータ型ではなく、制約である
    • 自動増加整数はデータ型であり、主キーにせずとも使用できる
  • 柔軟でない既約に縛られぬよう

Tell It Like It Is

  • 名で体を表すよう
    • bugsエンティティのPKをbug_idという名前にする
    • 主キーと外部キーとは同じ名前する
      • 例外: 関連の性質を名前に盛り込む
        • reported_byとか
    • ISO/IEC11179で標準化されている
      • Joe Celko氏による実践: SQL Programming Style

Be Unconventional

  • CoCなフレームワークで、想定している主キー名をoverrideできたりする
  • レガシーなDB用の互換のためだけの機能と思われがち
  • 新しいプロジェクトでもわかりやすいカラム名をつけるために重要な機能である

Embrace Natural Keys and Compound Keys

  • 適切な自然キーがあるならばサロゲートキーをつける必要はない
  • 必要な例:
    • すべてのカラムに変更の可能性がある
    • 行がユニークでない
    • 当初は一意に見えたものが、後になって一意ではないとわかった
  • 複合主キーを参照する外部キーもまた複合キーとなる
    • 良し悪し
      • キーの値自体が欲しい場合はJOIN不要

SQL Antipatterns ch3 Naive Trees

pragprog.com


A hierarchy consists of entries and relationships. Model both of these to suit your work.

Naive Trees

  • 再帰データ構造をSQLで表現
    • 例: コメントの返信スレッド
comment_id parent_id comment
...
  • すぐ思いつくこの構造には問題がある
    • 長いコメントチェーンを1クエリで取得するのが困難
      • 子の取得はJOIN
      • コメントチェーンの長さは無制限
      • SQLのJOIN数は固定長
    • 全エントリ取得してアプリケーション側で木を構築するのも計算量・リソース的に非現実

Objective: Store and Query Hierarchies

  • データに再帰関連をもたせるのは普遍的なアイデア
    • ノード
      • エントリ
    • ルート
      • 親のないエントリ
    • リーフノード
      • 子のないエントリ
    • ノンリーフノード
      • 中間のノード
  • 木構造データの例
    • 組織図
    • コメント返信スレッド

Antipattern: Always Depend on One's Parent

@startuml
class 1
class 2
class 3
class 4
class 5
class 6
class 7

1 -- 2
2 -- 3
1 -- 4
4 -- 5
4 -- 6
6 -- 7
@enduml

tree

  • 隣接リスト
comment_id parent_id author comment
1 NULL Fran What's the cause of this bug?
2 1 Ollie I think it's a null pointer.
3 2 Fran No, I checked for that.
4 1 Kukla We neet to check for invalid input.
5 4 Ollie Yes, that's a bug.
6 4 Fran Yes, please add a check.
7 6 Kukla That fixed it.

Query a Tree with Adjacency List

  • JOIN句では固定の深さまでしかデータを取得できない
  • 全データ取得してアプリケーション側で木を構築するのも非効率
    • 部分木で十分
    • 必要なのはレコードの中身ではなく集約した結果のみ
      • COUNT()とか

Mantaining a Tree with Adjacency List

  • いくつかの操作は単純に実現できる
    • 葉ノードの追加
    • 単ノードや部分木の再配置
  • 削除は複雑
    1. 部分木のノードを特定
    2. 葉側から順に削除
      • FK制約違反をさけるため
      • 子孫を昇格したり再配置したりしないならばON DELETE CASCADEで自動化できる

How to Recognize the Antipatterns

  • こんなのが聞こえてきたら注意
    • 「木の深さはどれだけ深くまでサポートすればいい?」
      • 全子孫を取得できないから生じる質問
    • 木構造を管理するコードを触るのが怖い」
      • しんどい方法を選んでしまった
    • 「孤立したノードを掃除するためにスクリプトを定期実行する必要がある」
      • ノンリーフノードを削除した時に孤立ノードが生ずる
      • 後述の方法 + トリガー・FK制約のカスケーディングを用いることで弾力性をもたせることができる

Legitimate Uses of the Antipattern

  • 隣接リスト方式の強み
    • あるノードの直接の親/子を容易に取得
    • 列の追加が容易
  • 操作がこれだけならうまくいくだろう
  • 再帰クエリがあればそれを使える

Don't Over-Engineer

  • 「任意の深さの木構造データを扱えるよう」
  • 子が1世代しかないことに顧客が気づかず
  • 任意の深さの木構造データを扱えるものを何週間もかけて作ってしまった

Solution: Use Alternative Tree Models

Which Design Should You Use?

設計 テーブル数 子取得 部分木取得 INSERT DELETE 参照整合性
隣接リスト 1 easy hard easy easy yes
再帰クエリ 1 easy easy easy easy yes
パス列挙 1 easy easy easy easy no
入れ子集合 1 hard hard hard hard no
クロージャテーブル 2 easy easy easy easy yes
  • クロージャテーブルのテーブル構成
    • Nodesテーブル
    • TreePathsテーブル
  • ノードの複数の木に所属させたりできる

ガルパンコラボカフェのランダムコースター(12種)を25枚ツモってもコンプできなかった話


背景

sega-collabocafe.com

  • ガルパン最終章第2話が上映される
  • セガコラボカフェでガルパンコラボが行われる
  • ドリンク(600円)を飲むとコースター(12種類)がランダムで1枚もらえる
  • コンプしたくもなるよなぁ?
    • なるべく自力で

経済回した結果

f:id:wand_ta:20190714023816j:plain

いや5枚被りはおかしいだろ
ケイさん好きだけどさ

f:id:wand_ta:20190714024738j:plain

下の塊がランダムでもらえるコースター
秋山殿以外被ってるっておかしくないか

25枚ツモって10/12種類って屑運なのでは

  • 12の2倍以上ツモってるんだぜ?コンプできてても不思議ではないのでは
  • 確率分布が知りたくなる
  • 数式で簡単に算出できそうに見えて、そうでもなかったので動的計画法で解いた

f:id:wand_ta:20190714024922j:plain

数年ぶりにC++書いてみる

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
#include <iomanip>
#include <array>

namespace mp = boost::multiprecision;

constexpr int NUM_COASTER_TYPES = 12;

// コースターの種類は[0, NUM_COASTER_TYPES + 1)
// さらなる+1は番兵
using histogram_t = std::array<mp::cpp_int, NUM_COASTER_TYPES + 2>;


void show_probability(int trial, const histogram_t& histogram) {
  // 確率の分母
  mp::cpp_int denominator = mp::pow((mp::cpp_int)NUM_COASTER_TYPES, trial);
  
  std::cout << "----------------------------------------" << std::endl
            << trial << "th trial" << std::endl
            << "----------------------------------------"  << std::endl;

  // 見出し
  for(int i = 0; i <= NUM_COASTER_TYPES; ++i) {
    std::cout << std::setw(4) << i << "    ";
  }
  std::cout << std::endl;

  // 確率
  for(auto column: histogram) {
    // XXX.X%という感じに表示する
    double probability = (double)(column * 10000 / denominator) / 100;
    std::cout << std::fixed
              << std::setw(5)
              << std::setprecision(1)
              << probability
              << "%, ";
  }
  std::cout << std::endl << std::endl;
}


int main() {
  int coaster_num;
  std::cin >> coaster_num;

  // 初期条件
  // 0枚数ツモ時点で0種1通り
  histogram_t histogram{};
  histogram.fill(0);
  histogram[0] = 1;

  // 計算結果一時格納
  histogram_t work{};

  for (int trial = 1; trial <= coaster_num;  ++trial) {
    work.fill(0);

    // 動的計画法
    for (int type_num = 0; type_num <= NUM_COASTER_TYPES; ++type_num) {
      const auto column = histogram[type_num];
      work[type_num] += column * type_num;
      work[type_num + 1] += column * (NUM_COASTER_TYPES - type_num);
    }

    std::swap(histogram, work);

    show_probability(trial, histogram);
  }

  return 0;
}

wandbox

出力結果

全出力(クリックで展開)

----------------------------------------
1th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%, 100.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%, 

----------------------------------------
2th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   8.3%,  91.7%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%, 

----------------------------------------
3th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.7%,  22.9%,  76.4%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%, 

----------------------------------------
4th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.1%,   4.5%,  38.2%,  57.3%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%, 

----------------------------------------
5th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.8%,  13.3%,  47.7%,  38.2%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%, 

----------------------------------------
6th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.1%,   4.0%,  25.9%,  47.7%,  22.3%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%, 

----------------------------------------
7th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   1.1%,  11.6%,  37.1%,  39.0%,  11.1%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%, 

----------------------------------------
8th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.3%,   4.7%,  23.2%,  41.1%,  26.0%,   4.6%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%, 

----------------------------------------
9th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.1%,   1.8%,  12.8%,  34.1%,  35.7%,  13.9%,   1.5%,   0.0%,   0.0%,   0.0%,   0.0%, 

----------------------------------------
10th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.7%,   6.5%,  24.5%,  37.9%,  24.2%,   5.8%,   0.4%,   0.0%,   0.0%,   0.0%, 

----------------------------------------
11th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.2%,   3.1%,  16.1%,  34.4%,  31.9%,  12.4%,   1.8%,   0.1%,   0.0%,   0.0%, 

----------------------------------------
12th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.1%,   1.5%,   9.9%,  28.1%,  35.6%,  19.9%,   4.6%,   0.3%,   0.0%,   0.0%, 

----------------------------------------
13th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.7%,   5.8%,  21.3%,  35.4%,  26.8%,   8.8%,   1.1%,   0.0%,   0.0%, 

----------------------------------------
14th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.3%,   3.3%,  15.3%,  32.5%,  31.9%,  14.0%,   2.5%,   0.1%,   0.0%, 

----------------------------------------
15th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.1%,   1.8%,  10.6%,  28.1%,  34.8%,  19.7%,   4.6%,   0.3%,   0.0%, 

----------------------------------------
16th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.1%,   1.0%,   7.1%,  23.1%,  35.4%,  25.1%,   7.5%,   0.7%,   0.0%, 

----------------------------------------
17th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.5%,   4.6%,  18.4%,  34.3%,  29.8%,  11.1%,   1.3%,   0.0%, 

----------------------------------------
18th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.3%,   3.0%,  14.2%,  31.8%,  33.4%,  15.1%,   2.3%,   0.0%, 

----------------------------------------
19th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.1%,   1.9%,  10.7%,  28.6%,  35.8%,  19.4%,   3.5%,   0.0%, 

----------------------------------------
20th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.1%,   1.2%,   7.9%,  25.0%,  37.0%,  23.7%,   5.1%,   0.0%, 

----------------------------------------
21th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.7%,   5.7%,  21.4%,  37.0%,  27.9%,   7.1%,   0.0%, 

----------------------------------------
22th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.4%,   4.1%,  18.0%,  36.2%,  31.8%,   9.4%,   0.0%, 

----------------------------------------
23th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.3%,   2.9%,  14.8%,  34.7%,  35.2%,  12.1%,   0.0%, 

----------------------------------------
24th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.1%,   2.1%,  12.1%,  32.6%,  38.0%,  15.0%,   0.0%, 

----------------------------------------
25th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.1%,   1.4%,   9.8%,  30.2%,  40.3%,  18.2%,   0.0%, 

----------------------------------------
26th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.1%,   1.0%,   7.8%,  27.6%,  42.0%,  21.5%,   0.0%, 

----------------------------------------
27th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.7%,   6.2%,  25.0%,  43.1%,  25.0%,   0.0%, 

----------------------------------------
28th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.5%,   4.9%,  22.4%,  43.6%,  28.6%,   0.0%, 

----------------------------------------
29th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.3%,   3.8%,  19.8%,  43.7%,  32.3%,   0.0%, 

----------------------------------------
30th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.2%,   3.0%,  17.5%,  43.4%,  35.9%,   0.0%, 

----------------------------------------
31th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.1%,   2.3%,  15.3%,  42.7%,  39.5%,   0.0%, 

----------------------------------------
32th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.1%,   1.8%,  13.3%,  41.7%,  43.1%,   0.0%, 

----------------------------------------
33th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.1%,   1.4%,  11.6%,  40.4%,  46.6%,   0.0%, 

----------------------------------------
34th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   1.0%,  10.0%,  39.0%,  49.9%,   0.0%, 

----------------------------------------
35th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.8%,   8.6%,  37.4%,  53.2%,   0.0%, 

----------------------------------------
36th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.6%,   7.3%,  35.7%,  56.3%,   0.0%, 

考察

25枚ツモったときの確率分布

----------------------------------------
25th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.1%,   1.4%,   9.8%,  30.2%,  40.3%,  18.2%,   0.0%, 
  • 10種類以下しか揃わない確率は約42%
  • 11種類ちょうど揃う確率は約40%
  • 12種類コンプできる確率は約18%
  • うーん、妥当!w
    • 強いて言えば11種類揃ってないのが若干運悪いですね

Q. コンプ率5割超えるためには何枚ツモらないといけないの

----------------------------------------
34th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   1.0%,  10.0%,  39.0%,  49.9%,   0.0%, 

----------------------------------------
35th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.8%,   8.6%,  37.4%,  53.2%,   0.0%, 

----------------------------------------
36th trial
----------------------------------------
   0       1       2       3       4       5       6       7       8       9      10      11      12    
  0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.0%,   0.6%,   7.3%,  35.7%,  56.3%,   0.0%, 

A. 35枚

  • あと10杯飲んでもコンプできるか五分五分
    • これも戦車道…

理論から学ぶデータベース実践入門 ch14 トランザクションの本質

gihyo.jp


まとめ

  • DBにおいてデータの整合性はきわめて重要
    • Principle of Explosion定期
  • リレーショナルモデルだけではなくトランザクション理論も不可欠
    • 分離レベル
    • ロック
    • MVCC
    • 制約

トランザクション

  • データを正しく保つために考案された手法
    • DBからは独立した理論体系
    • 正規化理論と目的は同じだが着眼点は異なる
      • 双方が必要

トランザクションの機能

  • 下記のようなケースで生じうる不整合からデータを守る
    • DBサーバに対して多数のクライアントから同時にアクセスが発生
    • DBサーバあるいはアプリケーションが更新処理の途中でクラッシュ
  • よく聞く例: 預金操作
  • 機能

トランザクションの鍵、スケジュール

  • 同時実行に不整合を起こさないためには?
    • 同時実行しない
      • リソースを使い切れないので非現実的
    • 同時実行しつつなんとかする
  • トランザクションとは、複数のデータアイテムの操作をまとめたもの
    • 操作によっては他の操作に影響を及ぼす
      • 特に書き込み処理
    • どのようにスケジュールを組めばデータの正しさを保証できるのかが課題
      • どのような処理が互いに干渉するのか、しないのかを踏まえる

「データの正しさ」の定義

  • 「直列化されたスケジュール」
  • データが正しいとは?
    • 直列化されたスケジュールと同じ結果になること
    • 【補】= SERIALIZABLE
  • 「データが正しい」スケジュールは多数存在しうる
  • その中から良い物を選択するのがスケジューラの任務

スケジューラの性能

  • 性能項目
    • いかに多くのトランザクションを並列化できるか
    • いかに低コストで最適なスケジュールを探し出せるか
      • 組み合わせ最適化問題なので計算コスト甚大
      • そこそこのコストでそこそこ良いものを得るのが現実解

トランザクションの特徴

ACIDとは

原子性(Atomicity)

  • トランザクションの結果がCommitかAbortのいずれかになる性質
    • Commit: すべての操作が成功
    • Abort: すべての操作が失敗
      • SQLでは「ROLLBACK」
  • 必ず成功することが保証されているわけではないことに注意
    • エラー処理(リトライ)を実装していないアプリケーションはトランザクションの使い方を本質的に間違えている
      • ままある(残念)

一貫性(Consistensy)

  • トランザクションを実行すると、ある一貫性のある状態から別の一貫性のある状態へと遷移
  • 「一貫性のある状態」とは?
    • RDBは知らない
    • データに意味を与えるのはアプリケーション

分離性(Isolation)

  • 同時に実行している複数のトランザクションが互いに影響を与えない
    • 影響を与えないとは?
    • 直列に実行した場合と結果が同じ

永続性(Durability)

さまざまな異常

  • 具体的にどのような異常(Anomaly)があるの?

ダーティリード

TR1 TR2 データX
1000
BEGIN
X読み取り: 1000
X更新: 1300 1300
BEGIN
X読み取り: 1300
ROLLBACK 1000
Xから200引く: 1100
X更新 1100
COMMIT

インコンシステントリード

TR1 TR2 データX データY
1000 1000
BEGIN
X読み取り: 1000
Xから100引く: 900
X更新 900
BEGIN
X読み取り: 900
Y読み取り: 1000
X+Y: 1900
COMMIT
Y読み取り: 1000
Yに100足す: 1100
Y更新 1100
COMMIT
  • 100円送金する例
  • 新旧データ(新:X,旧:Y)を読み取ってしまう不整合
    • X+Y=2000でないといけない

ロストアップデート

TR1 TR2 データX
1000
BEGIN
X読み取り: 1000
BEGIN
X読み取り: 1000
Xに300加算: 1300
X更新
COMMIT 1300
Xから200引く: 800
X更新 800
COMMIT
  • 更新が後勝ちしちゃうやつ

ノンリピータブルリード(ファジーリード)

TR1 TR2 データX
1000
BEGIN
X読み取り: 1000
BEGIN
X読み取り: 1000
Xから200引く: 800
X更新
COMMIT
X読み取り: 800
COMMIT
  • 同じデータアイテムを複数回読み取った時に異なる結果が得られてしまう

ファントムリード

TR1 TR2 データX
1000
BEGIN
件数読み取り: 1
BEGIN
X追加: 2000
COMMIT 1000,2000
件数読み取り: 2
COMMIT
  • SQLなどのように範囲検索がある場合に起こる
  • 他のトランザクションで追加されたデータを読み取れてしまう

スケジュールとロック

  • 前述のスケジュールは実行してはいけないもの
  • ロッキングスケジューラ
    • ポピュラー
    • ロックによる排他制御で前述のスケジュールを防ぐ
      • 操作の対象となる行に対して、操作前にロックをかける
      • 競合するデータアイテムへのアクセスを必要とするトランザクションはブロックされる
TR1 TR2 データX データY
1000 1000
BEGIN
Xをロック
X読み取り: 1000
Xから100引く: 900
X更新 900
Yをロック
BEGIN
Yをロック
ブロック
Y読み取り: 1000
Yに100足す: 1100
Y更新 1100
COMMIT
Yをアンロック
Xをアンロック
Y読み取り: 1100
Yから100引く: 1000
Y更新: 1000 1000
Xをロック
X読み取り: 900
Xに100足す: 1000
X更新 1000
COMMIT
Xをアンロック
Yをアンロック

デッドロック

トランザクションの分離レベル

分離レベル Dirty Read Inconsistent Read Fuzzy Read Lost Update Phantom Read
READ-UNCOMMITED o o o o o
READ-COMMITED x o o o o
REPEATABLE-READ x x x o o
SERIALIZABLE x x x x x
  • x: 起きない
    • 【補】o: 起きる とは限らない(製品依存だったはず)
  • 【補】ノンリピータブルリード(ファジーリード)は別資料より
  • SERIALIZABLEが最も分離性が高い
  • が、性能は低い
  • 性能のために分離レベルを下げることがある
    • 異常を回避するために余計に手間がかかる
    • ロックの挙動や構文は製品依存
      • 移植性低い

MVCC: MultiVersion Concurrency Control

  • 非ロックスケジューリング
TR1 TR2 データX(最新) データX(古) データY
1000 1000
BEGIN
X読み取り: 1000
Xから100引く: 900
X更新 900 1000
BEGIN
X読み取り: 1000
Y読み取り: 1000
X+Y: 2000
COMMIT
Y読み取り: 1000
Yに100足す: 1100
Y更新 1100
COMMIT
  • 古いバージョンの値を参照できるため、インコンシステントリードが生じない
  • ロールバックセグメント
    • 古いバージョンの値の格納領域
    • 通常通りSELECTを記述すれば自動的に参照される
  • SERIALIZABLE以外の分離レベルを採用する動機

クラッシュリカバリ

DBサーバのコンポーネント

  • トランザクション理論上のコンポーネント
    • ステーブルDB
      • 不揮発ストレージ上のDB
    • DBキャッシュ
      • 揮発メモリ上の、DBのサブセット
      • ステーブルDBからデータフェッチ
      • DBキャッシュ上で変更操作
      • ステーブルDBへフラッシュして反映
    • ステーブルログ
      • 不揮発ストレージ上ログ
      • DBキャッシュ上で行われた操作の履歴
        • COMMIT
        • ROLLBACK
    • ログバッファ
      • ステーブルログに書き込みを行う前に利用されるバッファ
  • クラッシュリカバリ
    1. ステーブルログに記録されているログエントリをREDO
    2. クラッシュする瞬間に完了していなかったトランザクションによる更新をUNDO

トランザクションとデータモデルの融合

リレーショナルモデルとACIDの「C」

  • 一貫性(Consistency)のためにはデータモデルへの理解が不可欠

リレーショナルモデルと異常

  • トランザクションにおける異常
    • 同時に複数の処理を実行したときに生じる異常
      • 個々の行の値がいきなり変わる
      • 行そのものが増減する
  • リレーションの演算の正しさを保証するためには上記異常が起こらないことが不可欠

正規化と直交性

  • リレーショナルモデルにおける異常
    • データそのものに矛盾が生じる
      • 重複データの一部のみ更新
  • スケジュールに問題がなくても、DBに重複があり更新時異常が起きたら意味がない

制約

データモデルだけでは不十分

  • 述語論理、あるいは集合演算の外のビジネスロジックはアプリケーションに記述する
  • アプリケーションの「バグ」が生じることを前提でRDBを守らなければならない
    • 二重三重の防御策が必要

制約を活用してデータを守る

  • NOT NULL
    • 正規化するときは必ずつけよう(1NFの条件)
  • 一意性制約
    • 候補キーすべてに主キーorユニークインデックスをつけよう
  • CREATE TYPE
    • SQLがサポートしているデータ型よりもドメインを狭めたい時に
    • 方言が激しい
  • CHECK制約
    • カラムが取りうるデータの範囲を細やかに・現時点でのテーブルの状態に合わせて制限するのに役立つ
    • 製品によりサポート状況異なる
      • SQL標準が実装されていなかったり
  • 外部キー制約
    • 子テーブルに存在するキーと同じ値のキーが親テーブルに存在する
    • 痛い目を観たくなければ使っておけ
      • ほんの少しの性能の低下や運用の手間に比べるとはるかに重要
    • 【補】論理削除の場合はつけられない
  • トリガー
    • 外部キーで表現できない制約を表現する
      • 子テーブルに存在するキーと同じ値のキーが親テーブルに存在しない(NOT)
      • 子テーブルに存在するキーと同じ値のキーが複数の親テーブルのいずれかに存在する(OR)
        • 【補】「現在単価」と「単価履歴」をFKで参照する場合
      • 子テーブルに存在するキーと同じ値のキーが複数の親テーブルのいずれかだけに存在する(XOR)
        • 【補】「ユーザマスタ」と「削除済みユーザ」をFKで参照する場合
      • 子テーブルに存在するキーと同じ値のキーが複数の親テーブルのうちN個以上/未満存在する
  • リレーションの演算でない操作を使用する
      • 集計
      • ストアドファンクション
    • 集合論で表現できないロジックを記述するので当然
  • 行トリガー/文トリガーがある
  • 1行ごとの制約の記述に向いているのは行トリガー
  • 複数行にわたる値の検査はアプリケーション側でトランザクション内で行うとよい

理論から学ぶデータベース実践入門 ch13 リファクタリングの最適解

gihyo.jp


まとめ

リファクタリング

  • DBリファクタリング: 1つ以上のテーブルの設計を変更する
  • 定義変更自体はALTERコマンド一撃
  • 現実、そんなに簡単な話ではない
    • アプリケーションはリリース済、運用中
      • テーブルにデータ格納済
      • テーブルアクセス依存の処理がある

DBのリファクタリングは大変

  • 影響範囲甚大
    • クエリの書き換え
    • 各種制約の確認
    • ビューの修正
    • トリガーの修正
    • ストアドプロシージャの修正

マルチアプリケーションにおけるDB環境

  • 共通のDBを複数のアプリケーションから参照するのはよくあること

なぜリファクタリングが必要なのか

  • アプリケーションが変化する以上、本質的に必要
  • しかし大変なので「やらない理由」を探して放置しがち
    • 負債は貯まるばかり
  • 負債を返済するにはリファクタリングするほかない

リファクタリングの手順

  • アプリケーションへの影響を抑えつつ、アプリケーションのペースに合わせた移行をするための手順
    1. 作業前後のバックアップ
    2. スキーマの変更
    3. データの移行
    4. アプリケーション移行のためのトリガーの作成
    5. アプリケーションのデプロイ
    6. 移行のためのトリガーの削除
    7. 移行のためのカラムの削除

スキーマの移行期間

  • 移行期間を設けるケース
  • 古いロジックのアプリケーションが一定期間残る
  • そのため、元のスキーマと変更後のスキーマが共存する必要がある

反復的なリファクタリング

回帰テスト

  • 十分なテストケースが存在していることが前提
    • アプリケーションの機能が損われたらリファクタリングではない、破壊しているだけ
    • 機能が損われていないことを確認する方法はテストしかない

ベンチマークテスト

  • リファクタリングの結果、パフォーマンスが著しく低下するケースは珍しくない
  • パフォーマンスが低下していないことを確認する方法はベンチマークテストしかない
  • 本番に忠実な環境を用意すること

マイグレーション利用のススメ

  • スキーマのバージョン管理
    • RoRのActive Recordで導入されたしくみ
    • 【補】Laravelでもおなじみ
    • 制限: バージョン分岐ができない
  • 戻す場合のロジックもテストすること
  • バックアップじゃダメなの?
    • ダメ
    • データも巻き戻ってしまう

トリガーを使って2つのテーブル間で同期を取る

  • 移行期間中、新旧テーブルのデータの整合性を確保するために使う
    • 循環に注意
    • 移行が完了したらトリガーを削除する
    • トリガーのテストも忘れずに

リファクタリングの種類

インデックスの追加・削除

  • 軽微
    • クエリ書き換え生じない
  • テーブルが持つ論理的な意味が変更されうることに注意
    • 主キーやユニークインデックスによる一意性制約の導入/削除
  • ベンチマークテストで性能劣化のなきことを確認せよ

カラム名の変更

  • 過渡
    • 異なる名前で同じデータを持ったカラムを2つ持たせる
    • 行単位のトリガーで同期
      • MySQLなどの製品でサポート

NOT NULL制約の導入

  • 1NFにするために後からでもNOT NULLをつけることは大切
    • あるいはリレーション分割
  • NOT NULLをつけるにあたり、既存のデータにNULLが含まれていたら若干の調整が必要
    • NULLだった個所の値がデフォルト値でもNULLでも動くようにクエリを書き換える

主キーの定義変更

  • 変更が必要になるケース
    • 主キーが既約ではない場合
    • 主キーから別のカラムへの関数従属性がなくなってしまった
    • サロゲートキーからナチュラルキーへの変更、あるいはその逆

無損失分解

  • 移行期間が必要な場合は面倒
    1. 元のテーブルを残しつつ新しいテーブルを作成
    2. 双方のテーブルでデータの同期
      • トリガー
      • カスケード

テーブルの垂直分割と統合

  • 複数のテーブルで直交性が満たされていない場合、テーブルの統合が必要

コラム: 関連テーブルの実態

  • 1:N -> M:N
  • 2段階のリファクタリングのショートカットと考えられる
    1. 主キーを変更して行持ち
    2. 第2正規化

リファクタリングのためのベストプラクティス

正規化と直交性

カラムではなくテーブルを追加する

  • カラムを追加する前に熟考せよ:
    • カラムの初期値はあるか
    • 主キーに対して関数従属しているか
  • これらを満たすならカラムを追加して問題ない
  • テーブルを追加するというアプローチも
    • メリット
      • 既存のテーブルを変更しなくてよい
    • デメリット
      • JOIN増える
        • 内部表に対して主キーでアクセスできる実行計画ならば、パフォーマンスペナルティは存外小さい

SELECT * を使わない

  • 1NF崩れる
    • 順序を持ち込むことにほかならないため

アプリケーションを疎結合

  • データへアクセスするロジックを共通化する
    • アプリケーション側の修正個所が少なくなるよう

理論から学ぶデータベース実践入門 ch12 Webアプリケーションのためのデータ構造 (2/2)

gihyo.jp


タグ

  • RDBにとって頭の痛いデータ
  • データ構造(スキーマ)に問題はない
  • データ自体に問題がある
    • タグのデータはとても大きい
    • クエリ結果も大量の行となる
    • 複数タグを指定すると、大量の行の積集合演算となる(高コスト)
  • キャッシュテーブルを作ろう
    • {tag1, tag2, item_name, score} みたいな
      • score: 人気度
    • PK: {tag1, tag2, item_name}
    • 正規形でない
      • 繰り返しパターンなので1NFでない
      • {item_name} -> {score} なる関数従属性がある
    • が、キャッシュなので問題ない
    • 重複をなくすために、 tag1 < tag2といった条件をつけること
    • インデックス{tag1, tag2, score}なるインデックスがあれば上位のアイテムを高速に取得できる
      • {tag1, tag2, score, item_name}としてカヴァリングインデックスを狙うのも良い
  • メリット
    • 上位コンテンツの取得が速い
  • デメリット
    • 行数が多い
      • アイテムにn個のタグがついていて、うちm個で検索する組み合わせはnCm通り
        • 階乗オーダー
      • 要件として検索可能なタグ数を制限できない場合は諦めよう

コラム: 転置インデックスを使用して検索を高速化する

  • RDB製品によっては、配列型カラムがサポートされる
  • タグ配列に対して転値インデックスをつけることでタグ検索高速化
  • ただし、本質は巨大な集合同士の結合のままであることに注意
    • 通常のB+木インデックスよりもデータがコンパクトなだけ

スケールアウト

レプリケーション

  • 参照処理性能の物理的な限界を突破
  • 参照負荷を複数のDBサーバへ分散

スレーブへの問い合わせ方式

データの論理的整合性と非同期レプリケーション

  • データの論理的整合性
    • スレーブに対して問い合わせをする場合、マスタに対して行うのと全く同じクエリを記述できる
    • マスタの完全なコピーを持っているため
  • 非同期レプリケーション
    • 完全コピーはオーバヘッドが大きいため、同期レプリケーションは使用不可
    • スレーブ上のデータはマスタのものと比べて古い可能性がある
      • もっとも、1秒未満になることがほとんど
    • 少しの時間差も許されない場合はレプリケーションによるスケールアウトは使用できないことに注意する

シャーディング

  • 更新処理性能の物理的な限界を突破
  • 別々のDBサーバにデータを水平分割
    • cf. パーティショニングは同一DBサーバ
    • 典型的には別々マシン
  • アプリケーションのロジックは複雑化する
    • どのデータがどのシャードに格納されるべきかの判別
  • 参照処理性能もスケールさせたい場合、レプリケーションと組み合わせるのが一般的

問題点

  • シャードをまたいだクエリを実行できない
    • DBサーバをまたいでJOINできない
  • 管理のオーバヘッド増える
    • スキーマ構造のシャード間同期は管理者が行う必要がある

NoSQLのシャーディング

  • 自動的にシャーディングできるNoSQL製品が人気を博している
  • が、RDBの代わりにはならない
    • データモデルの違いは重大
    • 整合性を保証する道具がない
  • 内部的なシャーディングに対応したRDB製品もあり、そちらを先に検討すべき