前置き

• Webエンジニアじゃないけど，Webエンジニアが知っておいたほうが良さそうな知識を妄想してまとめました
• 「これだけ分かってれば大丈夫」ではないです
  • 自分のPCの上でコリコリ動くDBの気持ちは分かるようになると思います
  • 本当はネットワーク越しにガリガリ動くDBの気持ちが分からなくちゃいけません
  • 最後の方に今後の勉強の指針なども書きました

自己紹介

• 中谷 翔 (laysakura)
• 東大情報理工M2: (分散DB,ストリーム処理)
• Twitter
• Github
• blog: 俺とお前とlaysakura
• 日本地ビール協会公認 ビアテイスター

最近の活動

• IPA未踏: High Performance SQLite の開発
• 長期インターン: MySQLite (MySQLストレージエンジン) 開発
  • MySQLからSQLiteのDBファイルを，SQLiteよりも高速にアクセス(開発継続中)
• PyPIモジュール: nextversion
  • 次のバージョン番号を出す (1.0.2 -> 1.0.3)
• CPANモジュール: Search::Fulltext, Search::Fulltext::Tokenizer::MeCab
  • らくちん日本語全文検索
  • ブログ記事が177ブクマ(2013/11/02現在), はてなブログ人気エントリー入り(嬉しい)

今日やること

硬派にやります

• SQL
• インデックス
• トランザクション

導入

DB(子供)からRDBMS(大人)へ

• よくDBって言われるものの正式名称: RDBMS (Relational Database Management Systems)
  • テーブル = リレーション
  • SQL = 関係代数演算の記述法のひとつ
  • 関係代数 = リレーションを扱う理論
• とにかく: SQL使って表を書くやつはRDBMSって呼びます!

RDBMSの嬉しさ

• 楽，速い，安心
  • SQLでらくちんデータ検索
  • インデックスで高速データアクセス
  • トランザクションで大事なデータを保護
• (個人的には) SQL, インデックス, トランザクションを使いこなせて初めて「DB触れます〜」って言える (と思う)

SQL

要点: 基本の5操作覚えれば大体書けるようになる

目標: このくらいのクエリはさらっと(書き|読み)たい

-- TPC-H Query#10
select
    c_custkey, c_name,
    sum(l_extendedprice * (1 - l_discount)) as revenue,
    c_acctbal, n_name, c_address, c_phone, c_comment
from
    customer, orders, lineitem, nation
where
    c_custkey = o_custkey
    and l_orderkey = o_orderkey
    and o_orderdate >= date ':1'
    and o_orderdate < date ':1' + interval '3' month
    and l_returnflag = 'R'
    and c_nationkey = n_nationkey
group by
    c_custkey, c_name, c_acctbal, c_phone, n_name, c_address, c_comment
order by
    revenue desc;

関係代数基本の5操作の組み合わせでしかない

関係代数基本の5操作

再掲: TPC-Hクエリ

selection, projection, sort, aggregation, join はどこかな?

-- TPC-H Query#10
select
    c_custkey, c_name,
    sum(l_extendedprice * (1 - l_discount)) as revenue,
    c_acctbal, n_name, c_address, c_phone, c_comment
from
    customer, orders, lineitem, nation
where
    c_custkey = o_custkey
    and l_orderkey = o_orderkey
    and o_orderdate >= date ':1'
    and o_orderdate < date ':1' + interval '3' month
    and l_returnflag = 'R'
    and c_nationkey = n_nationkey
group by
    c_custkey, c_name, c_acctbal, c_phone, n_name, c_address, c_comment
order by
    revenue desc;

自分でSQL書けるようになろう

• SQLZOO
  • クイズ形式でSQLの練習ができる．超おすすめ
  • 「欲しい結果を得るためのクエリ」は書けるようになる
  • でも，速いクエリを書けるようなるのは別の話

遅いクエリ=クソクエリ

• 結果が出れば良いってもんじゃない
  • クソクエリcommitする奴=サービス運用の敵=火炙り
• どうすれば速いクエリ書けるようになる??
  • (色々大事だけど)まずはインデックスを使いこなそう

インデックス

要点: インデックスのデータ構造と使われどころを抑えよう

インデックスの考え方の '基本'

インデックスを貼る = ソート済みの 'リスト' を作る

# インデックスなし:
# scoreが10000より大きい要素を探す => 全探索 O(n)
scores = [300, 500, 200, 15000, 15, ..., 20000, 10, ...]

# インデックスあり = ソート済みのリスト:
# scoreが10000より大きい要素を探す => 二分探索 O(log n)
scores = [10, 15, 200, 300, 500, ..., 15000, 20000, ...]

老婆心

• 万が一 O(log n) とかの話がわからない場合
  • 今すぐアルゴリズムとデータ構造を勉強しましょう
  • 最低限を知らないで「アプリ作れればいいや」だけでは・・・

インデックスのデータ構造

• 「カラムXにインデックス貼ると，カラムXのソート済みリストができるんだ!!」

  • 惜しいけど違う
  • 'リスト' 構造はオンメモリなら十分高速
  • しかし，テーブルがメモリをはみ出すくらいでかいと，インデックスもオンメモリじゃ済まない

• ディスクに置く & 「ソート済み」なデータ構造 => B+Tree

(おまけ1)メモリとディスクの違い

(ディスク ≒ ハードディスクの話)

なぜリスト構造はディスクに置かれるとそのまま使えないのか?

• リストの各要素は飛び飛びのメモリ番地に配置されている

  • リスト要素を読む => 飛び飛びアクセス = ランダムアクセス

• ディスクはランダムアクセスめっちゃ遅い(HDDの物理的構造の話)

• ディスクにはある程度のサイズ一気にブロックアクセスするのが基本
  • ブロックサイズ ≒ セクタサイズの倍数: 4KB, 16KB, 32KB, ...

(おまけ2)RDBMSの高速化 ≒ ディスクアクセスの最小化

• 覚えておくべきコスト感覚(スループットベース):
  • メモリ(DRAM): CPUの1000倍遅い
  • ディスク(HDD): メモリの1000倍遅い
  • (ネットワーク: メモリと同じくらい，ただし近い将来メモリより速いはず)

少なくとも古典的には標題が成り立つ

インデックスの使われどころ

• 先の2例の selection のみならず...
• sort, aggregation, joinにも使われる
• 適切にインデックスを貼ると，様々な処理が高速化する
  • 宿題1: order by key, group by key, join A.key1 on B.key2 のそれぞれで，keyにインデックスがあるときとないときの速度差を見てみる
  • 宿題2: sort, aggregation, join で，インデックスがないときとあるときに利用可能なアルゴリズムを想像&調べてみる

インデックスの貼りすぎに注意

• 「インデックスすごい!もう全部のカラムに貼っちゃう!!」

  • 張っ倒される

• インデックスのデメリット

  • B+Tree分のディスク容量を使う
  • insertは遅くなる
    • ソート済みリストにソート順を崩さず要素を追加するときのコスト: O(log n)
    • ただリストに要素を追加するときのコスト: O(1)

• インデックスを貼るカラムを判断できる => 一人前

トランザクション

要点: 並列処理の '怖さ' を知ろう

トランザクションとは

• 原義: 処理・仕事のひとまとまり
• 複数のクエリを '一度に' 実行するための機能がRDBMSにおけるトランザクション

トランザクションで整合性を保つ

BEGIN;  -- トランザクションの開始

-- ユーザ登録リクエストをDBに反映
insert into User (name, age) values ('たかし', 29);

-- トランザクション中は，外から「この状態」は見られない!
-- (たかしユーザが追加されたことが観測できるのはCOMMIT以後)

-- ユーザ数をサービス統計に反映
update Service set num_users = num_users + 1;

COMMIT;  -- トランザクションの終了

トランザクションのデモ1

client1> select * from User;

client2> insert into User (name, age) values ('たかし', 29);

client1> select * from User;  -- たかしくんは追加されてる

client2> BEGIN;
client2> insert into User (name, age) values ('みか', 27);

client1> select * from User;  -- みかちゃんがいない!!

client2> COMMIT;

client1> select * from User;  -- みかちゃんが見えるように

COMMIT or ROLLBACK !!

(これ書いてる時はハロウィンでした)

• トランザクション発行(BEGIN)の後にやれることは2通り
  • COMMIT: トランザクション中の処理をDBに反映
  • ROLLBACK: トランザクション中の処理をなかったことに

トランザクションのデモ2

client1> select * from User;

client2> insert into User (name, age) values ('たかし', 29);

client1> select * from User;  -- たかしくんは追加されてる

client2> BEGIN;
client2> insert into User (name, age) values ('みか', 27);

client1> select * from User;  -- みかちゃんがいない!!

-- ここまでデモ1と同じ

client2> ROLLBACK;

client1> select * from User;  -- みかちゃんはなかったことに・・・

TIPS: 暗黙のトランザクション

• insertとかupdateとかするとき，「暗黙のトランザクション」が発行されている

  • insertで100byteのレコードを挿入する際，60byte目が挿入された中途半端な状態は他のクライアントから観測できない

• トランザクション貼るのは重たい処理

  • pthread触った人なら分かるかも

• 暗黙のトランザクションよりも自前トランザクションを使ったほうが速いことも

暗黙のトランザクションが遅いデモ

for (my $i = 0; $i < 200; ++$i) {
    $dbh->do('insert into T1 values(777)');  # トランザクションが200回 => 遅い
}

###
$dbh->do('BEGIN');
for (my $i = 0; $i < 200; ++$i) {
    $dbh->do('insert into T2 values(777)');  # トランザクションは1回 => 速い
}
$dbh->do('COMMIT');

トランザクションのACID性

RDBMSのトランザクションはACID性を満たすのが普通

• Atomicity, Consistency, Isolation, Durability
• それぞれちゃんと説明できるようになってるのが望ましい
• Wikipediaの記事がそこそこ分かりやすい

〆

今日やったこと

• SQL(楽さ)

  • selection, projection, sort, aggregation, join
  • 複雑なクエリも怖くない

• インデックス(速さ)

  • 検索を速くする
  • B+Tree, なぜ使われるか
  • インデックス貼りすぎの弊害

• トランザクション(安心さ)

  • 整合性を保つ
  • 暗黙のトランザクション
  • ACID

以上

ありがとうございました!