概要 †

  • RDB 周りの基本知識
↑

目次 †

↑

参考 †

↑

インデックス †

  • レコード = SSD 内に格納された行
  • インデックスの内部実装
    • インデックスは、SSD 上に埋め込まれた (column -> record pointer の) 順序付き辞書
    • 複合インデックスは column -> record pointer の辞書ではなく、tuple(column, column) -> record pointer になっているだけ。
    • 関数インデックスは、column -> record pointer の辞書ではなく、f(column) -> record pointer になっているだけ。
    • B+木という平衡多分木が SSD に埋め込まれている。これは毎回の SSD ランダムアクセスが遅いので、多分木のノードリストを一括で取りたいから。
  • インデックスも SSD に埋め込まれているのは、インメモリで全レコードのカラムを展開することが不可能だと推定すべきため。
  • それ以上でもそれ以下でもない。これ以上、変な議論をしている複合インデックスの説明は、読み飛ばすこと。有害。
  • 用語
    • カーディナリティ: 男女のようなものは低く、ID のようなものは高い。要するに、インデックスを張って単一の値を指定した時にどれくらい範囲を絞れるかという話。カーディナリティが高い＝インデックスを張って一つ値を決めときにほぼ一意に定まる。
      • なので、**カーディナリティの高い順に複合インデックスの順番を決めると良い**と言われているが、完全に用途次第
↑

実行計画 †

  • 実行計画の表示は、DB によって全然変わってくるので、それぞれについて勉強しなければならない。
    • だが、Oracle の実行計画が読みやすく理解しやすいので、その用語で一旦説明して、最後に他の DB との関わりについて議論する
  • 実行計画の流れ
    • 1 テーブルに対する取得: SCAN (= レコードを読み込む範囲を指定すること) -> TABLE ACCESS (= 指定された範囲を読み込むこと。途中で WHERE 句に指定された条件で Filter などを行うことも) -> SORT / LIMIT
    • 2 テーブルの JOIN: 特定の条件のもとでテーブル 2 つを結合
      • JOIN は同時に 3 つを JOIN することはできないことに注意
      • JOIN には nested-loop, hash, sort-merge の三つの種類がある。
  • 実行計画中の用語
    • ACCESS = 平衡二分木の Search によって、操作範囲の初めと終わりを確定させること。
    • FILTER = TABLE ACCESS で範囲のデータを辞書の NEXT 操作で全列挙する際、特定の条件で無視すること。
  • 実行計画の読み方
    • Operation が木構造で依存関係を表している。インデントが深いところを解決しないと、インデントが浅いところが解決できない。
    • 今回であれば、Id 2 -> Id 1 -> Id 0 という順番で解決されていく。
    • Predicate Information には、Id で行われている ACCESS, FILTER が何かという参考情報が記載されている。
    • Rows, Cost は*見積もりであって実際に読む行数や時間を表していない*。実行する前にいろいろなパターンを試して、合計コストが最小のものを選んで実行するようになっている。その過程で、インデックスフルスキャンよりもテーブルフルスキャンの方がマシみたいなものが自動的に出てくる。
      • この見積もりには、統計情報による予測も含まれており、統計情報を更新する方法には UPDATE STATISTICS というコマンドが提供されている。これによって実行計画が変更され、高速になる可能性がある（インデックスの再構築をしたら統計情報は自動で更新されるので意味がない）
---------------------------------------------------------------
|Id |Operation                   | Name         | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT            |              |    1 |    2 |
| 1 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES    |    1 |    2 |
|*2 |  INDEX UNIQUE SCAN         | EMPLOYEES_PK |    1 |    1 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("EMPLOYEE_ID"=123)
↑

単一インデックス †

  • 事前知識
    • UNIQUE 制約がついているカラムでは、その値はテーブルワイドで一意であることが保証される。
    • PRIMARY キーにはインデックスがデフォルトで張られている。
    • PRIMARY キーには UNIQUE 制約が自動で付いているとは限らない
  • SCAN の種類
    • INDEX UNIQUE SCAN: 辞書によりノードが一意に確定する時の SCAN。インデックスが UNIQUE 制約がついたカラムに付いている場合、そのカラムに対する = 演算子での WHERE 句で使われる（超早い）
    • INDEX RANGE SCAN: 辞書により選択されるノードの範囲が確定し、1 個以上のノードが選択される場合に使われる。
  • TABLE ACCESS の種類
    • TABLE ACCESS BY INDEX ROWID: SCAN で得られたノード範囲から、実際にレコードポインタを辿って SSD アクセスして読み込むこと。この時に、いくつかの WHERE で指定された条件で間引かれることがあり、これが FILTER と呼ばれる。
↑

INDEX UNIQUE SCAN - PRIMARY Key †

  • 以下では、PRIMARY キーにはデフォルトでインデックスが張られている。PRIMARY インデックスが UNIQUE である保証はないが、今回は UNIQUE とする。
    • (2) で INDEX UNIQUE SCAN している。
    • (1) で、ただし、辞書に乗っている情報だけでは first_name, last_name を取得できないので TABLE ACCESS が必要になっている。
  • スキーマ、クエリ、実行計画
CREATE TABLE employees (
   employee_id   NUMBER         NOT NULL,
   first_name    VARCHAR2(1000) NOT NULL,
   last_name     VARCHAR2(1000) NOT NULL,
   CONSTRAINT employees_pk PRIMARY KEY (employee_id)
)
SELECT first_name, last_name
  FROM employees
 WHERE employee_id = 123
---------------------------------------------------------------
|Id |Operation                   | Name         | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT            |              |    1 |    2 |
| 1 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES    |    1 |    2 |
|*2 |  INDEX UNIQUE SCAN         | EMPLOYEES_PK |    1 |    1 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("EMPLOYEE_ID"=123)
↑

INDEX RANGE SCAN - 複合インデックス †

  • 以下の例では、(subsidiary_id, employee_id) = (子会社の ID, 子会社での社員 ID) で社員を一意に定めている。
    • WHERE で subsidiary_id を指定しても、その子会社の全ての社員が返ってくることになる。この場合、SUBSIDIARY_ID が先頭のインデックスが定義されているので、問題なく INDEX が使われる。アクセスでは、(SUBSIDIARY_ID, -inf) ~ (SUBSIDIARY_ID, +inf) の範囲が指定される。
  • スキーマ、インデックス、クエリ、実行計画
CREATE TABLE employees (
   employee_id   NUMBER         NOT NULL,
   subsidiary_id   NUMBER         NOT NULL,
   first_name    VARCHAR2(1000) NOT NULL,
   last_name     VARCHAR2(1000) NOT NULL,
   CONSTRAINT employees_pk PRIMARY KEY (employee_id)
)
CREATE UNIQUE INDEX EMPLOYEES_PK 
    ON EMPLOYEES (SUBSIDIARY_ID, EMPLOYEE_ID)
SELECT first_name, last_name
  FROM employees
 WHERE subsidiary_id = 20
---------------------------------------------------------------
|Id |Operation                   | Name         | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT            |              |  106 |   75 |
| 1 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES    |  106 |   75 |
|*2 |  INDEX RANGE SCAN          | EMPLOYEES_PK |  106 |    2 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("SUBSIDIARY_ID"=20)
↑

TABLE ACCESS FULL - インデックスを指定すると探索範囲が限定される †

  • 上のクエリでは、subsidiary_id がインデックスに含まれるが、last_name はインデックスが張られていないので subsidiary_id = 30 となるようなレコードを全て調べて last_name が特定の値になっているもの以外を無視しなければならない。
    • 「subsidiary_id = 30 となるようなレコードを全て調べて」が 2 - access("SUBSIDIARY_ID"=30)
    • 「last_name が特定の値になっているもの以外を無視」が 1 - filter("LAST_NAME"='WINAND')
  • 下のクエリでは、Oracle では、NO_INDEX でクエリオプティマイザにインデックスの不使用を指示している。
    • すると、SUBSIDIARY_ID=30 となる最初のレコードと最後のレコードがわからなくなるので、テーブル全てをスキャンする必要がある
    • 上のクエリでは ACCESS で探索範囲を制限する段階で SUBSIDIARY_ID=30 を担保できていた。
    • 下のクエリではそれができないので、TABLE ACCESS の Filter で 1 - filter("LAST_NAME"='WINAND' AND "SUBSIDIARY_ID"=30) のように無視すべきレコードを判断しなければいけない。
  • スキーマ、インデックス、クエリ、実行計画、クエリ、実行計画
CREATE TABLE employees (
   employee_id   NUMBER         NOT NULL,
   subsidiary_id   NUMBER         NOT NULL,
   first_name    VARCHAR2(1000) NOT NULL,
   last_name     VARCHAR2(1000) NOT NULL,
   CONSTRAINT employees_pk PRIMARY KEY (employee_id)
)
SELECT first_name, last_name, subsidiary_id
  FROM employees
 WHERE last_name  = 'WINAND'
   AND subsidiary_id = 30
---------------------------------------------------------------
|Id |Operation                   | Name         | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT            |              |    1 |   30 |
|*1 | TABLE ACCESS BY INDEX ROWID| EMPLOYEES    |    1 |   30 |
|*2 |  INDEX RANGE SCAN          | EMPLOYEES_PK |   40 |    2 |
---------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
  1 - filter("LAST_NAME"='WINAND')
  2 - access("SUBSIDIARY_ID"=30)
SELECT /*+ NO_INDEX(EMPLOYEES EMPLOYEES_PK) */ 
      first_name, last_name, subsidiary_id
 FROM employees
WHERE last_name  = 'WINAND'
  AND subsidiary_id = 30
----------------------------------------------------
| Id | Operation         | Name      | Rows | Cost |
----------------------------------------------------
|  0 | SELECT STATEMENT  |           |    1 |  477 |
|* 1 |  TABLE ACCESS FULL| EMPLOYEES |    1 |  477 |
----------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter("LAST_NAME"='WINAND' AND "SUBSIDIARY_ID"=30)
↑

プレイスホルダー †

  • SQL のパラメータをいい感じに決めるためのもの
  • 疑問符(?)は、SQL標準で唯一定義されている、 プレースホルダの文字
    • 疑問符で、左から右に向って番号が付けられます。値を特定の疑問符に割り当てたい場合、 その番号を指定します。
    • しかし、プレースホルダを追加したり削除したりする際に番号付けを変えなければならないので、超めんどい
    • 多くのデータベースでは、この問題を解決するため、 アットマーク(@name)を使ったり、コロン(:name)を 使ったりと、パラメータに名前をつけられるよう独自の拡張をしています。
  • バインドパラメータは、テーブル名や列名にバインドパラメータを使用することはできない
    • 実行時にSQL文の構造も変える必要がある場合には、動的SQLを使いましょう。
↑

LIKE 演算子での INDEX RANGE SCAN の ACCESS †

  • INDEX RANGE SCAN の有効なヒントとして LIKE を使う方法として、LIKE の先頭に何文字かワイルドカード以外の文字を書くという方法がある
    • LIKE 演算子で、例えば"A%"なら A から始まらないものは無視するし、"AB%"なら AB から始まらないものを無視する。
    • LIKE 演算子で、%から始まるものを使うとインデックスが効かなくなるので遅くなりがち。
  • PostgreSQL での注意
    • PostgreSQLにおいては、LIKE式にバインドパラメータを 使った場合、PostgreSQLはその先頭にワイルドカードが 存在すると仮定してしまうので、実際の 検索語をオプティマイザに見せる必要がある。バインドパラメータを使わずに検索語をSQL文に直接書き込むと、SQLインジェクション攻撃に 対する予防措置を別に行わなければならないという不便がある。
  • スキーマ、インデックス、クエリ、実行計画 
    CREATE TABLE employees (
   employee_id   NUMBER         NOT NULL,
   subsidiary_id   NUMBER         NOT NULL,
   first_name    VARCHAR2(1000) NOT NULL,
   last_name     VARCHAR2(1000) NOT NULL,
   date_of_birth DATE           NOT NULL,
   CONSTRAINT employees_pk PRIMARY KEY (employee_id)
)
CREATE INDEX emp_up_name 
    ON employees (UPPER(last_name))
SELECT first_name, last_name, date_of_birth
 FROM employees
WHERE UPPER(last_name) LIKE 'WIN%D'
---------------------------------------------------------------
|Id | Operation                   | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT            |             |    1 |    4 |
| 1 |  TABLE ACCESS BY INDEX ROWID| EMPLOYEES   |    1 |    4 |
|*2 |   INDEX RANGE SCAN          | EMP_UP_NAME |    1 |    2 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access(UPPER("LAST_NAME") LIKE 'WIN%D')
       filter(UPPER("LAST_NAME") LIKE 'WIN%D')
↑

インデックスは各行に 1 個作るより全部まとめたほうが更新が早い †

  • 当たり前（インデックス 1 本は順序付き辞書なので）
↑

部分インデックス †

  • よく使う行集合（例: Closed ではないメッセージのみ）についてインデックスを張ることができる。具体的には、以下のようにできる
CREATE INDEX messages_todo
          ON messages (receiver)
       WHERE processed = 'N'
↑

結合 †

  • 結合には以下の三種類がある
    • NESTED LOOPS OUTER: 片方のレコードを全て読み込み、そのそれぞれに対して別の表にクエリする (N+1 問題の解決をデータベースエンジン内でやっている)
    • HASHMAP
    • SORT-MERGE
  • MySQL では NESTED LOOP しかないはず？（要出典）
  • 外部表と内部表
    • 例: SELECT * FROM table1 t1 INNER JOIN table2 t2 on t1.id = t2.id;
    • 外部表(駆動表)
      • JOINするときのベースになる表。JOIN 演算子の左。table1
    • 内部表
      • 外部表にくっつける表。JOIN 演算子の右。table2
↑

結合: NESTED LOOPS OUTER †

  • テーブルA, B がある。A の一部 X 個を抽出し、そのそれぞれに対して B のテーブルをスキャンする方法が NESTERD LOOPS OUTER
    • N+1 問題をデータベース内でやっているだけ、通信とクエリ開始のオーバーヘッドがない分まだマシ
  • 内部表のデータ量とヒット数が小さくないと時間がかかると言われているけど、外部表のサイズ m, 内部表のサイズ n だとして O(nm) だからどこに非対称性があってそんなことを言っているのか理解できない
  • 外部表・内部表の両方でインデックスが効くので、JOIN の ON での条件でインデックスを使えると高速に計算ができると、O(k log m) とか O((log n) k) とか O(log n log m) にできて高速になる
  • クエリ、実行計画
CREATE TABLE employees (
   employee_id   NUMBER         NOT NULL,
   subsidiary_id   NUMBER         NOT NULL,
   first_name    VARCHAR2(1000) NOT NULL,
   last_name     VARCHAR2(1000) NOT NULL,
   CONSTRAINT employees_pk PRIMARY KEY (employee_id)
)
CREATE TABLE SALES (
   employee_id   NUMBER         NOT NULL,
   subsidiary_id   NUMBER         NOT NULL,
   sales_id   NUMBER         NOT NULL, 
)
select this_.subsidiary_id as subsidiary1_0_1_
    , this_.employee_id as employee2_0_1_
      -- MORE this_ columns on employees
    , sales2_.sale_id as sale1_3_
      -- MORE sales2_ columns on sales
 from employees this_ 
 left outer join sales sales2_ 
         on this_.subsidiary_id=sales2_.subsidiary_id 
        and this_.employee_id=sales2_.employee_id 
where lower(this_.last_name) like ?
---------------------------------------------------------------
|Id |Operation                    | Name        | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT             |             |  822 |   38 |
| 1 | NESTED LOOPS OUTER          |             |  822 |   38 |
| 2 |  TABLE ACCESS BY INDEX ROWID| EMPLOYEES   |    1 |    4 |
|*3 |   INDEX RANGE SCAN          | EMP_UP_NAME |    1 |      |
| 4 |  TABLE ACCESS BY INDEX ROWID| SALES       |  821 |   34 |
|*5 |   INDEX RANGE SCAN          | SALES_EMP   |   31 |      |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
  3 - access(UPPER("LAST_NAME") LIKE 'WIN%')
      filter(UPPER("LAST_NAME") LIKE 'WIN%')
  5 - access("E0_"."SUBSIDIARY_ID"="S1_"."SUBSIDIARY_ID"(+) 
        AND  "E0_"."EMPLOYEE_ID"  ="S1_"."EMPLOYEE_ID"(+))
↑

ORM を開発中に使うときはロギングを ON にしましょう †

開発中はSQLのロギングを有効にし、 生成されたSQL文のレビューをしましょう。

  • DBIx::Class
    • export DBIC_TRACE=1をシェルで 実行。
  • Doctrine
    • ソースコードレベルでのみ設定可。本番環境で出力しないようにするのを忘れずに。設定変更可能なロガーを自分で 実装することも考えた方がよいでしょう。
$logger = new \Doctrine\DBAL\Logging\EchoSqlLogger;
$config->setSQLLogger($logger);
  • Hibernate (ネイティブ)
    • App.configあるいは hibernate.cfg.xmlで、<property name="show_sql">true</property>を設定。
  • JPA
    • eclipselink, Hibernate and OpenJPAといった JPAプロバイダに依存しますが、persistence.xmlで以下を設定。
<property name="eclipselink.logging.level" value="FINE"/>
<property name="hibernate.show_sql" value="TRUE"/>
<property name="openjpa.Log" value="SQL=TRACE"/>
↑

結合: Hashmap †

  • ON での結合がイコールで結ばれている時にのみ使えるインデックス不要の JOIN 方法
  • 二つのテーブルを結合する。
  • 手順
    • オプティマイザが結合する表の件数を比較して、小さい方の表を全件読み取る
    • 1.で選択された表の結合条キー列(=JOIN の ON のキー)の値をハッシュ関数にかけてハッシュテーブルを作成する
    • 外部表の結合キー列を同じハッシュ関数で変換->作成したハッシュテーブルを検索
    • ハッシュが同じ列同士を**直積で**結合する
      • バケット i に Table 1 が x 個 Table 2 が y 入ったとすると、(Table 1, Table 2) のペアで xy 個の出力が発生する。
  • 特徴
    • ハッシュ関数で処理する都合上、等価結合(=)の場合のみ使用可能
    • 結合キー列にインデックスがなくても大丈夫
    • 対象件数が増えても結合の負荷が増えにくい
  • (クエリ、実行計画)、(インデックス、クエリ、実行計画)
    • Hashmap でもマージ前の表の作成のためにインデックスを効かせることはできる
SELECT *
  FROM sales s
  JOIN employees e ON (s.subsidiary_id = e.subsidiary_id
                  AND  s.employee_id   = e.employee_id  )
 WHERE s.sale_date > trunc(sysdate) - INTERVAL '6' MONTH
--------------------------------------------------------------
| Id | Operation          | Name      | Rows  | Bytes | Cost |
--------------------------------------------------------------
|  0 | SELECT STATEMENT   |           | 49244 |    59M| 12049|
|* 1 |  HASH JOIN         |           | 49244 |    59M| 12049|
|  2 |   TABLE ACCESS FULL| EMPLOYEES | 10000 |     9M|   478|
|* 3 |   TABLE ACCESS FULL| SALES     | 49244 |    10M| 10521|
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("S"."SUBSIDIARY_ID"="E"."SUBSIDIARY_ID"
          AND "S"."EMPLOYEE_ID"  ="E"."EMPLOYEE_ID")
   3 - filter("S"."SALE_DATE">TRUNC(SYSDATE@!)
                           -INTERVAL'+00-06' YEAR(2) TO MONTH)
CREATE INDEX sales_date ON sales (sale_date)
SELECT *
  FROM sales s
  JOIN employees e ON (s.subsidiary_id = e.subsidiary_id
                  AND  s.employee_id   = e.employee_id  )
 WHERE s.sale_date > trunc(sysdate) - INTERVAL '6' MONTH
--------------------------------------------------------------
| Id | Operation                    | Name      | Bytes| Cost|
--------------------------------------------------------------
|  0 | SELECT STATEMENT             |           |   59M| 3252|
|* 1 |  HASH JOIN                   |           |   59M| 3252|
|  2 |   TABLE ACCESS FULL          | EMPLOYEES |    9M|  478|
|  3 |   TABLE ACCESS BY INDEX ROWID| SALES     |   10M| 1724|
|* 4 |    INDEX RANGE SCAN          | SALES_DATE|      |     |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("S"."SUBSIDIARY_ID"="E"."SUBSIDIARY_ID"
          AND "S"."EMPLOYEE_ID"  ="E"."EMPLOYEE_ID"  )
   4 - access("S"."SALE_DATE" > TRUNC(SYSDATE@!)
                           -INTERVAL'+00-06' YEAR(2) TO MONTH)
↑

結合: SORT-MERGE †

  • 両方のテーブルがソートされているとマージソートの容量で簡単にマージできる。
    • ただ、MySQL ではサポートされていない上、毎回ソートするのも重いのであまり使われない
↑

他の DB との関係 †

↑

MySQL †

  • INDEX UNIQUE SCAN = type const = UNIQUE 制約のついた行に対するアクセス
+----+-----------+-------+---------+---------+------+-------+
| id | table     | type  | key     | key_len | rows | Extra |
+----+-----------+-------+---------+---------+------+-------+
|  1 | employees | const | PRIMARY | 5       |    1 |       |
+----+-----------+-------+---------+---------+------+-------+
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS