書籍

配布ソース

http://www.cs.bc.edu/~sciore/simpledb/

取り組み方

章ごとの要点をまとめる
インターフェースとテストコードから実装をイメージする
実装を読み解いてコメントを書きながら写経する
Suggested Reading は気になる資料のリストアップまで

Exercises はどこまでやるか悩ましい。
割とボリューミーなので、1周目は読むだけに留めて、2周目で取り組むくらいの気持ちで。

全体に対するメモ

実装パートは事前に解説した内容まで踏み込まない
- Exerciseパートで、追加で取り組む課題として設定されてたりする
扱える値
- string, integer
buffer replacement
- clock まで解説 & 実装はナイーブなもの
recovery
- 記録する log の種類は、ファイル末尾への block の追加まで解説 & 実装するのは以下
  - CHECKPOINT
  - (transactionの) START, COMMIT, ROLLBACK
  - SETINT, SETSTRING
- undo-redo まで解説 & 実装は undo-only
- nonquiescent chckpointing まで解説 & 実装は quiescent
transaction
- 4 つの分離レベルやレベルごとの slock の利用方法について解説 & 実装は serializable
- deadlock 検出は解説のみ
- multiversion lock は解説のみ
- lock の粒度の解説 & 実装は block 単位のみ
record 表現
- spanned/unspanned record を解説 & 実装は unspanned
- homogeneous/nonhomogeneous file を解説 & 実装は homogeneous
- fixed-length/variable-length field を解説 & 実装は fixed-length
metadata
- 4種類の metadata を解説 & 実装
- table metadata
- view metadata
- index metadata
- statistical metadata
query processing
- 関係代数はかなりライトに解説
  - 演算子は select, project, product のみ
  - 実装するのも上記の演算子のみ
- select のための predicate も実装
  - 構造
    - predicate
    - terms
    - expression
    - constant
  - フィールド、定数の等価比較まで
planning
- 基本的な計画作成プロセスのみ(最適な計画作成は最終章でカバー)
- 単純な SQL のサブセットをサポートするだけなので select, project, product のみを使用したクエリツリーで実装
  - 計算、ソート、グループ化、入れ子、名前の変更は含まず
indexing
- static hashing, extendable hashing, B-trees を解説
- static hashing, B-trees を実装
- B-trees の実装は簡易的なもの
  - merge は実装しない
  - latch, lock は実装しない
    - 実装済の block 単位の lock にて一貫性を担保？
materialization & sorting
- 一時テーブルを利用して sort, groupby, mergejoin を実装
- 一時テーブルの破棄タイミングは DB 起動時のみ
- sort は素朴な mergesort + α
  - 解説では一度に merge する run の数を増やしたり、初期の run の数を減らすような改善を紹介しているが、実装はしない
- groupby の集計式は count, max のみ実装
- mergejoin は sort を利用して効率化 & 駆動表に join 値が重複する際の内部表の読み直しも想定
効果的なバッファ使用手法
- 関係演算子によって使用可能なバッファの割り当て方法を変えると、効率化できることを解説
  - 例: merge sort は一度に複数の run を merge 出来ると良い(multibuffer sorting)
  - SimpleDB では Multibuffer Product のみを実装
  - バッファ数の割り当て方法としては、ルート計算、因子計算を実装
    - multibuffer sort ではルートを利用(解説のみ)
    - multibuffer product では因子を利用(実装まで)
- join アルゴリズムの比較が面白かった
  - mergejoin, hashjoin, indexjoin がユースケースによって、効率が変わることが説明されていた
クエリ最適化
- 最適化のための個々の操作を解説
  - products の並び替え
  - select の分割
  - select の移動
  - select-product の join への変換
  - projection の追加
- クエリ最適化のステップをヒューリスティクなものを中心に解説
  - そのうち一部を使ったものを実装

hmatui66

Chapter 1: Database Systems

Database Systems の概要説明の章。

Database に求められるもの
- Record Storage
  - update / read を効率良くおこなえるような構造で記録
- Multi-user Access
  - 複数ユーザーが同時に操作でき、かつ不整合な状態にならないようにする
- Dealing with Catastrophe
  - クラッシュからリカバリー可能にする
- Memory Management
  - disk/flash の操作は遅いのでメモリーへのキャッシュする
- Usability
  - query language をサポートすることで usability を提供
Java-based な database system として Derby が参考になる
- 洗練されている代わりに複雑
この本では Java でシンプルな実装の database system を実装していく
- ソースはここからダウンロード可能
- embedded, server-based のどちらもサポート
- query はかなり制限
  - select: フィールド名称のリストのみ
  - from: テーブル名称のリストのみ
  - where: boolean オペレータと and のみ
  - その他には、 * なし、null なし、join なし、union なし、insert は明示的な値のみ、update での set 対象は 1 つのみ

hmatui66

Chapter 2: JDBC

JDBC の説明が主なので省略。

hmatui66

Chapter 3: Disk and File Management - 要点

Disk ドライブの説明
- 物理的な構造: Platters, Tracks, Spindle, Actuator などなど
- 回転スピード: 5,400 rpm - 15,000 rpm
- 転送速度: 100MB/s など(回転スピードと Track あたりのバイト数による)
- seek time: Actuator が Disk ヘッドを動かす時間(平均 5ms ほど)
- RAID の話
Flash ドライブの説明
Disk のブロックレベルのインターフェース
- 割り当て可能なブロックの記録方法のベーシックなストラテジー
  - disk map
    - ブロックに対応する bit の値で free/allocated を管理
  - free list
    - チャンクのチェーンの方式で管理
      - チャンク: 連続した未割り当てのブロックかたまり
    - チャンクの先頭ブロックに自身のチャンクの長さと、次のチャンクの位置が記録
- Disk のファイルレベルのインターフェース
  - OS はファイルシステムと呼ばれる Disk への高レベルなインターフェースも提供
- Database エンジンを実装する際に上記のどちらを選ぶべきか？
  - ブロックレベルを使うと
    - Disk ブロックを完全にコントロールできる
      - 例えば、よく使うブロックをシーク時間が短い位置に配置するなど
    - OS の制限を超えるサイズや複数ディスクドライブにまたがるデータをサポートできる
    - disadvantage もある
      - 実装が複雑になる
      - database 管理者もブロックアクセスパターンについての幅広い知識が要求される
  - ファイルシステムをフルに利用すると
    - 実装が簡単だが、2 つの理由から受け入れがたい
      - database システムはブロックの境界を把握できないとデータを効率良く扱えない
      - OS の I/O バッファの管理方法はデータベースクエリに適してない
  - 妥協案: データを OS ファイルに格納し、そのファイルを raw disk と同じように扱う
    - 多くの database システムで採用されている
      - Microsoft Access, Oracle, Derby, SimpleDB

hmatui66

Chapter 3: Disk and File Management - 実装

実装対象: BlockId, Page, FileMgr

BlockId

ファイル名と論理的なブロックナンバーから特定のブロックを識別

BlockId blk = new BlockId("student.tbl", 23)

Page

Disk ブロックの内容を保持
Buffer Manager, Log Manager から使われるコンストラクタをそれぞれ用意
ページ内の特定の位置に値を格納したりアクセスするための get/set メソッドを実装
- 例 getString, setString
3 つの値のタイプを保持可能とする
- int, string, blob
クライアントは任意の場所に値を格納できるが、どこに何の値を格納したか把握しておく必要がある
- setString した場所に対しては getString で値を取得する必要あり
setString, getString はそれぞれ内部で setBytes, getBytes を呼び出し
setBytes は先頭にバイト配列の長さをセットしつつ、バイト配列自体もセット

private ByteBuffer bb; // Page のコンストラクタで生成

public void setBytes(int offset, byte[] b) {
    bb.position(offset);
    bb.putInt(b.length);
    bb.put(b);
}

FileMgr

OS ファイルシステムとのインタラクションをハンドリング
database システムが扱うファイルを格納するディレクトリ名と、ブロックのサイズを保持
database システム起動時に 1 つの FileMgr オブジェクトを生成して保持
read, write は synchronized 指定

public synchronized void read(BlockId blk, Page p) {
    try {
        RandomAccessFile f = getFile(blk.fileName()); // ここで Map<String,RandomAccessFile> openFiles から該当の File を取得
        f.seek(blk.number() * blocksize); 
        f.getChannel().read(p.contents());
    } catch (IOException e) {
        throw new RuntimeException("cannot read block " + blk); // e を握りつぶしている感
    }
}

synchronized 指定は内部的にオープン済の RandomAccessFile オブジェクトを Map にキャッシュしているため？

hmatui66

Chapter 4: Memory Management

Two Principles of Database Memory Management
- Principle 1: Minimize Disk Accesses
  - RAM は速い
  - flash に比べて 1000 倍
  - disk に比べて 100,000 倍
- Principle 2: Dont't Rely on Virtual Memory
  - OS に Memory Management を委ねると 2 つの問題が発生する
    - database engine のクラッシュリカバリー能力が損なわれる(可能性がある)
      - ページ更新前にログレコードに書き込むべきだが、その前にページが swap out される可能性がある
    - OS が間違った推測をして不必要なディスクアクセスが発生する可能性がある
      - database engine がどのページを使っていて、どのページは気にしていないかを知るすべがないため

Managing Log Information

database を変更するたびに、その変更を取り消す必要がある場合に備えてログレコードを記録
Log Manager はログの中身は把握せず、ただログをファイルに書き出す役割
素朴に実装するとログを追加するたびに disk read/write が発生して非効率
- disk read は単に current のログのページを保持しておくだけで減らせる
- disk write は、ログのページがいっぱいになるまで遅延させることで減らせる
  - が、それでは問題がある
    - ログが書き込まれないと、database への変更も disk に書き込むことができないため、「ログのページがいっぱいになるまで」待つ必要があるのは問題
      - ログに適したバッファ管理はもうひと工夫必要
    - Chap.5 でも取り上げる話

Managing User Data

ログレコードの使われ方は well-understood なので、Log Manager は細かくチューニングできる
一方 JDBC アプリケーションからのアクセスは完全には予期できない
The Buffer Manager
- バッファープールと呼ばれる固定的なページを保持
  - バッファプールはコンピューターの物理メモリーに収める必要あり
- バッファープール内のページは pinned、もしくは unpinned 状態となる
  - pinned 状態である限りバッファプール内に保持
- クライアントがあるブロックに対応するページに pin する時
  - すでにバッファプールに該当ページが存在したら pinned をインクリメント
  - バッファプールに存在しない場合
    - プールに空きがある、もしくは unpinned 状態のページがあればブロックからページに読み込みを行う
      - reuse する対象のページを選択するための主要な Strategies は後述
    - プールに空きがなく、unpinned 状態のページもない場合はクライアントを wait list に追加して unpinned 状態のページが出てくるまで待ってもらう
Buffer Replacement Strategies
- Buffer Manager はどのページが次にアクセスされるか予期できないが、できるだけ長い時間再度読み込む必要がないものを選択したい
  - database のライフタイムを通じて常に使用されるページ(e.g. カタログファイル) などもある
- 主要な 4 つの戦略
  - ナイーブ: シンプルにシーケンシャルに unpinned 状態のページを探す
    - SimpleDB はこれを実装
  - FIFO
  - LRU: least recently used
  - Clock: バッファプールをリング状にスキャン & スキャン開始場所は前回の置換した場所の後ろから

メモ

ここで言うログは WAL と同一なのか？
- おそらく同一
- ↑にも記載があるように、Chap.5 で取り上げられていそうではある
参考資料
- バッファ管理とWAL
- PostgreSQL 13.1文書 - 第29章信頼性とログ先行書き込み

hmatui66

Chapter 4: Memory Management(Log) - 実装

実装対象: LogMgr, LogIterator

LogMgr

append: ログレコードをページの先頭に向かって書き込み、そのログシーケンスナンバー(LSN)を返す
- 唯一の制限: ログレコードの配列がページに収まる必要あり
- synchronized 指定
- 追加するログがページに収まりきらない場合は、flush して次のブロックに移動
- ページの先頭に、最後に書き込んだログレコードの pos を記録

public synchronized int append(byte[] logrec) {
    int boundary = logpage.getInt(0);
    int recsize = logrec.length;
    int bytesneeded = recsize + Integer.BYTES;
    if (boundary - bytesneeded < Integer.BYTES){// It doesn't fit
        flush(); // so move to the next block.
        currentblk = appendNewBlock();
        boundary = logpage.getInt(0);
    }
    int recpos = boundary - bytesneeded;
    logpage.setBytes(recpos, logrec);
    logpage.setInt(0, recpos); // the new boundary latestLSN += 1;
    return latestLSN;
}

flush: ログレコードを確実に disk に書き込む
iterator: ログレコードを逆順に返す iterator を取得
constructor
- ログファイルが存在しない場合は1つめのブロックを発行
- ログファイルが存在する場合は、一番最後のブロックを読み込み

LogIterator

ブロック内のログレコードをブロックの先頭から読み込み
- ログレコードは後ろから先頭に向けて書き込まれるため、先頭から読み込むと書き込みと逆順となる
ページに読み込んだブロックの先頭まで達したら、次のブロックに移動

hmatui66

Chapter 4: Memory Management(Buffer) - 実装

実装対象: Buffer, BufferMgr

Buffer

ページを読み込み
pin 数を保持
変更に関わる情報も保持
- トランザクション識別番号と、ページ変更時に生成されたログレコードの LSN を記録
flush
- disk write を行って、バッファが割り当てられた disk ブロックと、バッファが保持するページの値を一致させる
- 先にページ変更時に生成されたログレコードを flush して disk に記録した上で実施

BufferMgr

pin: 内部的に tryToPin を呼び出し
- tryToPin
  - 2 つのパートがある
    - findExistingBuffer: すでに該当のブロックにに割り当てられた buffer を探す
    - chooseUnpinnedBuffer: ナイーブな方法で unpinned buffer を探す
  - tryToPin が null を返した場合、pin メソッドは wait する
    - unpin されたら notifyAll が呼び出される
    - タイムアウトも設定

public synchronized Buffer pin(BlockId blk) {
    try {
        long timestamp = System.currentTimeMillis();
        Buffer buff = tryToPin(blk);
        while (buff == null && !waitingTooLong(timestamp)) {
            wait(MAX_TIME);
            buff = tryToPin(blk);
        }
        if (buff == null)
            throw new BufferAbortException();
        return buff;  
    } catch(InterruptedException e) {
        throw new BufferAbortException();
    }
}

public synchronized void unpin(Buffer buff) {
    buff.unpin();
    if (!buff.isPinned()) {
        numAvailable++;
        notifyAll();
    }
}

hmatui66

Chapter 5: Transaction Management

buffer manager は複数のクライアントが同じ buffer に並行アクセスすることを許容
- 結果はカオスになり得る
concurrency manager
- トランザクションが一貫して動くように実行を制御
recovery manager
- ログレコードを読み取り/書き込み
  - コミットされていないトランザクションを必要に応じて取り消し可能にする

Transactions

単一の操作として動作する操作のグループ
- ACID 特定によって特徴づけられる
atomicity and durability
- commited, rollback 操作の適切な動作を記述
- recovery manager の責務
consistency and isolation
- 並行アクセス時の適切な動作を記述
- conflict する操作を防ぐ
  - 典型的な戦略は、conflict を検知したら一方のクライアントを wait させる
- concurrency manager の責務

hmatui66

Chapter 5: Transaction Management - Recovery Manager

log record の書き込み
transaction の rollback
システムクラッシュ後の復旧

Log Records

loggable activity が発生した際に log record を書き込み
基本的な 4 タイプのレコード
- start
- commit
- rollback
- update
  - SimpleDB では integer, string の 2 種類に対応
潜在的な loggable activity はファイル末尾への block の追加
- transaction が rollback した際、追加された block の割り当て解除
- 簡単のため SimpleDB では対応しない
record に含む情報
- record のタイプ
  - START, SETINT, SETSTRING, COMMIT, ROLLBACK
- transaction の ID
- update の record のみ追加の 5 つの値
  - 変更対象のファイルの名称
  - ブロックナンバー
  - 変更箇所の offset
  - 変更箇所の old value
  - 変更箇所の new value
複数の transaction が同時に log に書き込まれるため、log record は散在

Rolback

変更を元に戻すことで transaction を rollback
update の record を追加した逆順で値を古い値に更新していく

Recovery

リカバリは database engine 起動時に実行
目的は database を「合理的な状態」に復元すること
「合理的な状態」とは
- すべての未完了のトランザクションは rollback
- すべての commit 済みのトランザクションは変更が disk に書かれている
正常なシャットダウン後の起動時にはすでに合理的な状態になっている
- トランザクションの完了とバッファの flush が完了するまで wait するため
予期せずクラッシュした場合は処理が必要
recovery manager はログファイルに記録された情報をもとにリカバリを実行
- コミット操作を完了する前に確実にログレコードをフラッシュする必要がある
undo-redo algorithm
- undo
  - すべてのログを逆順に読む
  - committed, rollback のログであればそれぞれのリストに追加
  - committed, rollback のリストに含まれないトランザクションの update ログであれば、指定の箇所に古い値を格納
- redo
  - 全てのログを先頭から読む
  - committed のリスト上のトランザクションの update ログであれば、指定の箇所に新しい値を格納

Undo-Only and Redo-Only Recovery

undo もしくは redo のみを実行することでアルゴリズムをシンプルにできる
undo のみのアルゴリズム
- commit record 書き込み前に disk に書き込むことを保証すれば redo は不要になる
- 良い点: リカバリはログファイルを 1 回読めば終わるので高速 & 更新レコードの new value は不要
- 悪い点: commit 操作は buffer flush を伴うので非常に遅くなる
  - クラッシュ頻度が低い場合は、redo した方が効率良くなる
redo のみのアルゴリズム
- commit されていない buffer が disk に書き込まれないのであれば undo は不要になる
- transaction が完了するまで buffer を pin 留め
- 良い点: リカバリは undo 処理がない分高速
- 悪い点: transaction が変更するブロックをすべて buffer に pin 留めするので buffer の競合を増加させる

Write-Ahead Logging

リカバリ時に未完了の transaction の undo が必要 -> 未完了の transaction のすべての更新は log ファイル内に対応する log record を持つ必要がある
上記を満たす方法
- 更新 log record が書き込まれたらすぐに disk に flush
- が、非常に非効率的
未完了 transaction が page を更新した際にシステムクラッシュした場合の 4 パターン
- (a) page と log record が両方 disk に書き込まれた
- (b) page だけが disk に書き込まれた
- (c) log record だけが disk に書き込まれた
- (d) どちらも disk に書き込まれなかった
↑のうち (b) が問題となる
- database エンジンは buffer page を flush する際に更新 log record を flush することで回避
  - Write Ahead Log と呼ばれる

Quiescent Checkpointing

log ファイルには database に対する全ての変更の履歴が含まれる
- database ファイルよりも大きくなることもある
リカバリ作業は労力が必要になるので、 log の一部だけを読み出す手法が考案された
- ある log について、それより前に commit されていない transaction が存在しなければ undo を停止できる
- 完了した transaction の buffer が disk に flush されていれば redo は停止できる
quiescent checkpoint は log 内の目印として機能
- undo 時に checkpoint log に遭遇 -> redo はその log 以降のみ処理可能
アルゴリズム
1. Stop accepting new transactions.
2. Wait for existing transaction to finish.
3. Flush all modified buffers.
4. Append a quiescent checkpoint record to the log and flush it to disk.
5. Start accepting new transactions.
quiescent checkpoint log record の書き込みに適したタイミングはシステム起動時のリカバリが終わり、新しい transaction が開始される前

Nonquiescent Checkpoiting

quiescent checkpointing はシンプルで理解しやすい
- が、recovery manager が transaction の完了を待っている間 database が利用できないようにする必要がある
  - 許容できないケースも多い
    - quiescent(静的)な状態を必要としないアルゴリズムが開発された
アルゴリズム
1. Let T1,...,Tk be the currently running transactions.
2. Stop accepting new transactions.
3. Flush all modified buffers
4. Write the record <NQCKPT T1,...,Tk> into the log.
5. Start accepting new transactions.
実行中のトランザクションを NQCKPT レコードに記録しておき、リカバリ時の undo をその場所で止めることができる
- NQCKPT ログに到達したら、そこに記録されているトランザクションの状況を確認
- 残っていたトランザクションの開始レコードの開始レコードより前のログは無視できる

Data item Granularity

granularity(粒度)
- log record に含むデータ項目の大きさ
- ここまでの説明における granularity は変更された値だったが、他にも block またはファイル単位の選択肢もある
block
- block が変更されるたびに更新 log record 作成
- block の以前の値、新しい値が log record に含まれる
- log record の数は少なくなるが、更新 log record が非常に大きくなってしまう
ファイル
- 変更したファイルに対して 1 つの更新 log record を生成
- log record にはファイルの元の内容全体が含まれる
- 値がいくつ変更されても、ファイル全体のコピーを作成するため実用的ではない
- ワープロソフトなどは採用している

hmatui66

Chapter 5: Transaction Management - Recovery Manager 実装

実装対象: 各種 LogRecord, RecoveryMgr

LogRecords

各 log record は共通のインターフェースを実装

public interface LogRecord {
    static final int CHECKPOINT = 0, START = 1, COMMIT = 2,
        ROLLBACK = 3, SETINT = 4, SETSTRING = 5;
    int op();
    int txNumber();
    void undo(int txnum);
    // ...省略
}

LogRecord を実装した SetStringRecord
- コンストラクタ: バイト配列から↑の6つの値を抽出
- writeToLog: SETSTRINGログレコードの6つの値をバイト配列にエンコードする静的メソッド
- undo: undo を実行する transaction を受け取り、対象の block を pin し、old value を書き込み、unpin する
  - 呼び出し側が disk に flush する責務を持つ

public class SetStringRecord implements LogRecord {
    private int txnum, offset;
    private String val;
    private BlockId blk;

    public SetStringRecord(Page p) {
        int tpos = Integer.BYTES;
        txnum = p.getInt(tpos);
        int fpos = tpos + Integer.BYTES;
        String filename = p.getString(fpos);
        int bpos = fpos + Page.maxLength(filename.length());
        int blknum = p.getInt(bpos);
        blk = new BlockId(filename, blknum);
        int opos = bpos + Integer.BYTES;
        offset = p.getInt(opos);
        int vpos = opos + Integer.BYTES;
        val = p.getString(vpos);
    }

    // ...省略

    @Override
    public void undo(Transaction tx) {
        tx.pin(blk);
        tx.setString(blk, offset, val, false); // don't log the undo!
        tx.unpin(blk);
    }

    public static int writeToLog(LogMgr lm, int txnum, BlockId blk, int offset, String val) {
        int tpos = Integer.BYTES;
        int fpos = tpos + Integer.BYTES;
        int bpos = fpos + Page.maxLength(blk.fileName().length());
        int opos = bpos + Integer.BYTES;
        int vpos = opos + Integer.BYTES;
        int reclen = vpos + Page.maxLength(val.length());
        byte[] rec = new byte[reclen];
        Page p = new Page(rec);
        p.setInt(0, SETSTRING);
        p.setInt(tpos, txnum);
        p.setString(fpos, blk.fileName());
        p.setInt(bpos, blk.number());
        p.setInt(opos, offset);
        p.setString(vpos, val);
        return lm.append(rec);
    }
}

RecoveryMgr

undo-only リカバリーを実装
commit, rollback は log record 書き込み前に transaction の buffer を flush
- ここでいう log record は commit, rollback のタイプのもの
  - 更新 log record はすでに記録されている
(private method) doRecover, doRollback
- ログレコードを後方からたどる
- 該当の transaction の log record を見つけるたびに、undo を呼び出し
- 停止条件
  - doRecover: checkpoint log を読む or 終端に達する
  - doRollback: 該当 transaction の start log を読んだ時

public class RecoveryMgr {
    // ...省略

    public void commit() {
        bm.flushAll(txnum);
        int lsn = CommitRecord.writeToLog(lm, txnum);
        lm.flush(lsn);
    }

    public void rollback() {
        doRollback();
        bm.flushAll(txnum);
        int lsn = RollbackRecord.writeToLog(lm, txnum);
        lm.flush(lsn);
    }

    public void recover() {
        doRecover();
        bm.flushAll(txnum);
        int lsn = CheckpointRecord.writeToLog(lm);
        lm.flush(lsn);
    }

    // ...省略

    private void doRollback() {
        Iterator<byte[]> iter = lm.iterator();
        while (iter.hasNext()) {
            byte[] bytes = iter.next();
            LogRecord rec = LogRecord.createLogRecord(bytes);
            if (rec.txNumber() == txnum) {
                if (rec.op() == LogRecord.START)
                    return;
                rec.undo(tx);;
            }
        }
    }

    private void doRecover() {
        Collection<Integer> finishedTxs = new ArrayList<Integer>();
        Iterator<byte[]> iter = lm.iterator();
        while (iter.hasNext()) {
            byte[] bytes = iter.next();
            LogRecord rec = LogRecord.createLogRecord(bytes);
            if (rec.op() == LogRecord.CHECKPOINT)
                return;
            if (rec.op() == LogRecord.COMMIT || rec.op() == LogRecord.ROLLBACK)
                finishedTxs.add(rec.txNumber());
            else if (!finishedTxs.contains(rec.txNumber()))
                rec.undo(tx);
        }
    }
}

hmatui66

Chapter 5: Transaction Management - Concurrency Manager

Concurrency Manager は同時実行 transaction の正しい実行に責任を持つ
このセクションでは
- 「実行が正しい」とはどういうことかを検討
- 正しさを保証するいくつかのアルゴリズムをとりあげる

Serializable Schedules

transaction の履歴は database ファイルにアクセスするメソッド(get/set など)の呼び出しのシーケンス
database 操作の粒度はさまざま
- 値単位
- block 単位
- その他もある(後述)
複数の transaction が同時実行されている場合
- database エンジンはそれらのスレッドの実行をインターリーブ
  - SimpleDB では Java ランタイムが自動的におこなう
- transaction の履歴は予測不可能なインターリブになる
  - -> スケジュールと呼ばれる
concurrency control の目的は、正しいスケジュールだけが実行されることを保証
- 正しいとは？を以下で見ていく
すべての transaction が直列に実行されるスケジュールを考えると
- インターリーブされない
- スケジュールは back-to-back 履歴となる
- このようなスケジュールは serial schedule と呼ばれる
同一の transaction であっても serial schedule が異なれば異なる結果になり得る
- 以下のような transaction を考える
  - T1: W(b1); W(b2)
  - T2: W(b1); W(b2)
- どちらも b1 block を書いた後に b2 block を書くため、block 単位の操作については同一の履歴を持つ
  - ただ、transaction としては必ずしも同一ではない
    - T1 はブロックの先頭に X を書き込み、T2 は Y と書き込む場合など
    - T1, T2 の順番が変わると、結果が変わる
      - どちらの serial schedule についても database エンジンは正しいものとして扱う
non-serial schedule であっても、ある serial schedule と同じ結果を出す場合、serializable という
non-serial schedule である以下のような transaction を考える
- W1(b1); W2(b1); W1(b2); W2(b2)
  - T1 の前半、T2 の前半、T1 の後半、T2 の後半を実行した結果
- このスケジュールは T1 を実行し、T2 を実行することと等価なので serializable
以下のようなnon-serial schedule の場合は non-serializable
- W1(b1); W2(b1); W2(b2); W1(b2)
  - T1 の前半、T2 の前半、T2 の後半、T1 の後半
- b1 block には T2 の値が書き込まれるが、b2 block には T1 の値が書き込まれる
ACID の isolation の性質
- 各トランザクションがあたかもシステムにおける唯一のトランザクションであるかのように実行されるべき
- non-serializable では↑の性質をもたないので、non-serializable なスケジュールは正しくない
  - schedule は serializable である場合のみ「正しい」

The Lock Table

database エンジンは全てのスケジュールが serializable を保証する責任がある
一般的なテクニック: locking を利用して transaction の実行を延期
このセクションでは lock がどう機能するかを説明
各 block に対する lock
- 共有 lock(slock)
  - 他の transaction は共有 lock を持つことはできる
- 排他 lock(xlock)
  - 他の transaction はいかなる lock も持てない
1 つの transaction で 1 つの block に対して共有 lock と排他 lock を持つことはできる

The Lock Protocol

すべてのスケジュールが serializable であることを保証する
以下の transaction を考える
- T1: R(b1); W(b2)
- T2: W(b1); W(b2)
serial schedule が異なる結果になる原因
- 両方とも同じ b2 block に書き込むため、順序によって値が変わる
  - 一般的に、実行順序によって異なる結果を生む可能性がある場合、「競合」する
- 読み書きの衝突もある
  - T1 の R(b1) の実行が、T2 の W(b1) の先か後かで結果が変わる
non-serial schedule で競合する操作が実行される順序は、同等の serial schedule がどうあるべきかを決定
↑の例では W2(b1) が R1(b1) より先に実行される場合、同等の serial schedule は T1 より先に T2 が実行されなければならない
- 衝突するすべての操作を考えると、T1 完了後に T2 実行、もしくは T2 完了後に T1 実行のどちらかとなる
- 衝突しない操作は任意の順序で発生させることができる
lock プロトコル
1. ある block を読む前に共有 lock を取得する
2. ある block を変更する前に排他 lock を取得する
3. commit or rollback 後に全ての lock を開放する
↑のプロトコルから 2 つの推論ができる
1. ある transaction が block の共有 lock を取得した場合、他の transaction はその block に書き込んでいない
2. ある transaction が block の排他 lock を取得した場合、他の transaction はその block にアクセスしていない
つまり、ある transaction が実行した操作は、他のアクティブな transaction による以前の操作と衝突しないことを意味する
- 結果として、得られるスケジュールは常に serializable となる
- 等価な serial schedule は transaction のコミット順序によって決定される
lock protocol システムの並行性を大幅に制限する
- transaction が完了するまで lock を保持するため
- 不要になった時点で lock を解放できれば、他の transaction の待ち時間は短くなる
  - が、transaction 完了前に lock を解放すると 2 つの深刻な問題が起きる(後述)

hmatui66

Chapter 5: Transaction Management - Concurrency Manager Part2

(Chapter 5 が長いので分割)

Serializability Problems

transaction が block の lock を解放すると、serializability への影響無しに別の block を lock できなくなる
以下の transaction T1 を考える
- T1: ...R(x); UL(x); SL(y); R(y);...
  - R: read, UL: unlock, SL: shared lock
x の unlock と y の共有 lock の間において T1 は非常に脆弱となる
- その間に T2 が割り込んで x, y に排他 lock をかけて書き込み、commit & unlock したとする
- T1 は T2 書き込み前の x を読んだので serial order は T2 より前に来る必要がある
  - が、T1 はその後 T2 が書き込んだ y を読むので T1 は T2 より後に来なければならない
- 結果、スケジュールは non-serializable となる
逆に transaction が unlock する前に全ての lock を取得する場合のスケジュールは serializable となる
- 2 phase lock と呼ばれる
- lock を蓄積するフェーズと、lock を解放するフェーズがあるため
2 phase lock は database エンジンで簡単には利用できない
- 通常、最終 block にアクセスし終わる頃には transaction は commit する準備ができている
  - (意味が取れてない)

Reading Uncommitted Data

lock を早期に解放することのもう一つの問題は、transaction が commit されてないデータを読み取れてしまうこと
以下の部分的なスケジュールを考える
- ...W1(b); UL1(b); SL2(b); R2(b);
T1 が b block に書き込み & unlock、T2 が b block を共有 lock して読み込み、をしたとする
- T1 が rollback すると、 T2 は存在しない変更に基づいた読み込みをしているため rollback が必要になる
- -> rollback の連鎖が起きる(カスケードロールバック)
transaction に commit されていないデータの読み取りを許可すると
- より多くの同時実行を可能にする
- が、データを書き込んだ transaction が commit されないリスクを負う
ほとんどの商用 DB は transaction 完了するまで常に排他 lock 解放を待つ

Deadlock

lock protocol は全ての transaction が commit されることを保証しているわけではない
- 保証するのは、スケジュールが serializable となること
- 特に、deadlock になる可能性がある
以下の transaction の履歴を考える
- T1: W(b1); W(b2)
- T2: W(b2); W(b1)
T1 が先行している状態で、T1 が b2 の lock 取得前に T2 が b2 の lock を取得すると deadlock となる
concurrency manager は waits-for グラフを保持することで deadlock を検出
- 各 transaction に 1 つのノードを持つ
- T1 が T2 の持つ lock を待っている場合、T1 から T2 へのエッジを持つ
- 各エッジには transaction が待っている block のラベルが貼られる
- lock が要求、または解放されるたびにグラフは更新
waits-for グラフがサイクルを持つする場合 deadlock が発生
transaction manager は deadlock を検出するとサイクル内の transaction を 1 つ選択して rollback
- サイクル発生の原因となった lock を要求した transaction を選択
  - 選択する戦略は他にもある
lock 待ちのスレッドだけでなく buffer 待ちのスレッドも考慮すると、deadlock は複雑になる
以下のシナリオを考える
- T1: xlock(b1); pin(b4)
- T2: pin(b2); pin(b3); xlock(b1)
T1 が b1 の lock を取得したのちに中断し、その間に T2 が b2, b3 を pin し b1 の lock 取得待ちに入る場合
- T1 が b4 の buffer 取得待ちに入り、他に unpin されることがなければ deadlock
lock manager は waits-for グラフを保持するだけでなく、transaction の buffer 待ちも考慮するのはかなり困難
waits-for グラフ使用の問題点
- グラフの維持がやや困難
- サイクル検出に時間がかかる
deadlock 検出を近似的におこなう、より単純な戦略もある
- 常に deadlock を検出 & deadlock ではない状況も deadlock 判定されることがあるもの
- wait-die
  - T1 の lock 要求が T2 が保持する lock と競合した時を考える
  - T1 が T2 よりも古い transaction であれば wait する
  - そうでなければ rollback する
- use time limit
  - T1 の lock 要求が T2 が保持する lock と競合した時を考える
  - T1 は lock 取得待ちをする
  - wait list 上に一定時間以上いたら rollback される

File-Level Conflicts and Phantoms

これまで block の読み書きに起因する競合を見てみた
ファイルの終端マーカーの読み書きをする size, append メソッドの衝突もある
以下の transaction を考える
- T1: ...; append; ...
- T2: ...; size; ...
T1 が T2 の size 呼び出し前に append を呼び出すとすると、serial order 上 T1 は T2 より前に来る必要がある
phantom 問題: ↑の衝突の結果の 1 つ
- T2 がファイルの全内容を繰り返し読み、その度に size を呼び出す場合
- T2 が size を呼び出した後、T1 が append した場合、T2 が次にファイルを読み込むとき、T2 は追加された値を見ることになる
  - ACID の分離の性質に違反
- 解決策
  - end-of-file マーカーを lock 可能にする
    - append するためには xlock、size を呼び出すためには slock を実施

Multiversion Locking

待ち時間を減らすための戦略
- 読み取りと更新 transaction は先にロックを取得した transaction が完了するまで、もう一方は待たされる

The Principle of Multiversion Locking

各 block に複数のバージョンを保存
基本的なアイデアは以下
- block の各バージョンにはそれを書き込んだ transaction の commit 時刻のタイムスタンプが付けられる
- 読み取り専用の transaction が block から値を要求すると concurrency manager は transaction の開始時に最も最近 commit された block のバージョンを使用する
読み取り専用 transaction は transaction の開始時に見えたであろう commit された block のバージョンを使用
- 読み取り専用 transaction は commit されたデータのスナップショットを見ることになる
- それ以降の transaction によって書き込まれたデータを見ることはない
次の multiversion lock の例を考える
- T1: W(b1); W(b2)
- T2: W(b1); W(b2)
- T3: R(b1); R(b2)
- T4: W(b2)
スケジュール
- W1(b1); W1(b2); C1; W2(b1); R3(b1); W4(b2); C4; R3(b2); C3; W2(b1); C2
- Ci: commit タイミングで、i は transaction の番号に対応
更新 transaction である T1, T2, T4 は lock protocol に従う
- それぞれの transaction ごとに block のバージョンが保存される
- time は transaction が commit した時間
読み取り専用 transaction である T3 は lock protocol に従わない
- R3(b1) で読み取られるのは直前に commit されている T1 が書き込んだ値
- R3(b2) は T4 の transaction が commit された後にスケジュールされているが time=7 のバージョンは表示されない
multiversion lock の優れた点
- 読み取り専用の transaction が lock を取得する必要がなく、待つ必要がない
- 更新する transaction が比較的少ないと仮定すると、待機の頻度はかなり低くなる

5.4.6.2 Implementing Multiversion Locking

各 block のバージョンをどのように管理するか
- バージョンファイルを明示的に保存する方法
  - シンプルだけどやや難しい方法
- ログを使用して block の任意の望ましいバージョンを再構築する方法
ログを使用して再構築する方法の実装
- 読み取り専用 transaction 開始時にタイムスタンプを付与
- 更新トランザクションは commit する時にタイムスタンプを付与
- commit 方法は以下
  - recovery manager は commit log record の一部として transaction のタイムスタンプを書き込む
  - transaction が保持する各 xlock について、concurrency manager が block をピン留めし、タイムスタンプを block の先頭に書き込み、buffer を unpin する
- 適切なバージョン再構築のステップ
  - block の現在のバージョンを新しいページをコピーする
  - 次のように log を3回逆向きに読む
    - 読み取り transaction が持つタイムスタンプ t の後に commit された transaction のリストを構築
      - t よりも小さいタイムスタンプの commit record まで達したら log 読み込みをストップ
    - 未完了の transaction リストを構築
      - commit or rollback record がないものは未完了の transaction
      - quiescent checkpoint の場合: checkpoint record に達した時点で log 読み込みをストップ
      - nonquiescent checkpoint の場合: checkpoint record に含まれる transaction の最も古い開始 record に達した時点で log 読み込みをストップ
    - 上記のリストのいずれかにある transaction による更新を巻き戻す
    - 更新を巻き戻した block の情報を返す
読み取り専用 transaction は JDBC においては setReadOnly というメソッドで指定

Transaction Isolation Levels

serializabitily を強制することはかなりの待ち時間を発生させる
multiversion lock は読み取り専用 transaction においては待ち時間が無く魅力的
- 実装はやや複雑
- version を作成するために追加のディスクアクセスが必要
- 更新 transaction には適用できない
待ち時間を短縮する方法: 完全な serializability を目指さない
transaction 分離レベルと共有 lock の使用方法のまとめ
- serializable
  - problems: none
  - lock usage
    - transaction 完了まで共有 lock を保持
    - EOF マーカーに対しても共有 lock 取得
- repeatable read
  - problems: phantoms
  - lock usage
    - transaction 完了まで共有 lock を保持
    - EOF マーカーに対しては共有 lock はとらない
- read committed
  - problems: phantoms, 値が変わりうる
  - lock usage
    - 共有 lock を早めに解放
    - EOF マーカーに対しては共有 lock はとらない
- read uncommitted
  - problems: phantoms, 値が変わりうる, ダーティリード
  - lock usage
    - 共有 lock をとらない
↑のどの分離レベルでもデータの書き込みに関しては正しく振る舞うべき
- 適切な排他 lock(EOF マーカー含む)を取得し、完了するまで保持
read uncomitted isolation と multiversion locking の比較
- どちらも読み取り専用の transaction に適用 & lock 無しで動作
- read uncommitted は各 block の現在の値を見れてしまう
  - serializable とは程遠い
- multiversion locking は transaction 開始時点で commit されていた値を見るので serializable

Data Item Granularity

ここまで block 単位で lock することを想定してきたが、他の粒度も可能
粒度(=concurrency data item と呼ばれる)
- 値
- ファイル
- database 全体
concurrency control の原則は粒度に影響されない
- 定義、プロトコル、アルゴリズムはどの粒度にも適用される
- 粒度の選択は実用性をもとに判断
粒度選択におけるトレードオフ
- 粒度のサイズを小さい場合
  - より多くの同時実行が可能になる
  - より多くの lock が必要となる
- 粒度のサイズを大きい場合
  - 同時実行性が悪化する
  - より少ない lock で扱える
- -> 結果、block 粒度は妥当な選択といえる
データレコードの粒度を扱える database もある
- 魅力的だが phantom に関する新たな問題が発生する
  - 新しいデータレコードは既存の block に挿入される場合 phantom リードが起こる
  - 解決策は block やファイルレベルの粒度もサポート

hmatui66

Chapter 5: Transaction Management - Concurrency Manager 実装

実装対象: LockTable, ConcurrencyMgr

ConcurrencyMgr

各 transaction が CocurrencyMgr を持つ
- 各 ConcurrencyMgr は同じ LockTable を使用する必要がある
CocurrencyMgr はその transaction が保持する lock を追跡
sLock メソッド
- transaction がすでにblock を lock していたら何もしない
- ロックしていない場合 LockTable の sLock メソッドを呼び出し
  - 許可されるのを待つ

    public void sLock(BlockId blk) {
        if (locks.get(blk) == null) {
            locktbl.sLock(blk);
            locks.put(blk, "S");
        }
    }

xLock メソッド
- すでに block に対する xLock を保持している場合は何もしない
- まず sLock を呼び出して、ロックが許可されるのを待つ
  - LockTable の xLock メソッドは transaction が block に対する slock を持っていることを仮定

    public void xLock(BlockId blk) {
        if (!hasXLock(blk)) {
            sLock(blk);
            locktbl.xLock(blk);
            locks.put(blk, "X");
        }
    }

LockTable

locks
- 現在 lock が割り当てられている各 block のエントリーを含む
  - エントリ: 排他 lock では -1, 正の値は共有 lock 数
sLock メソッド
- BufferMgr の pin メソッドと似た動作
- xlock がある場合は待ち続ける
- xlock がない場合は locks の該当 block の値をインクリメント

    private final Map<BlockId, Integer> locks = new HashMap<>();
    public synchronized void sLock(BlockId blk) {
        try {
            long timestamp = System.currentTimeMillis();
            while (hasXlock(blk) && !waitingTooLong(timestamp))
                wait(MAX_TIME);
            if (hasXlock(blk))
                throw new LockAbortException();
            int val = getLockVal(blk); // will not be negative
            locks.put(blk, val + 1);
        } catch (InterruptedException e) {
            throw new LockAbortException();
        }
    }

xLock メソッド
- BufferMgr の pin メソッドと似た動作
- 該当 block に 2 つ以上の slock がかかっている場合 while ループで待つ
  - hasOtherSLocks は locks の値 > 1 を返す
  - ConcurrencyMgr は xlock 要求前に slock を取得するため該当 block に対する slock 数は少なくとも 1 ある
- 他の transaction の slock がなければ locks の該当 block の値を -1 に上書き
- なぜこのような実装になっているか？
  - -> ある block に対して複数の transaction が xlock を取ろうとした場合の制御のため。
    - slock は xlock がない場合のみ取得できるので xlock を取る際も事前に slock を取っている

    public synchronized void xLock(BlockId blk) {
        try {
            long timestamp = System.currentTimeMillis();
            while (hasOtherSLocks(blk) && !waitingTooLong(timestamp))
                wait(MAX_TIME);
            if (hasOtherSLocks(blk))
                throw new LockAbortException();
            locks.put(blk, -1);
        } catch (InterruptedException e) {
            throw new LockAbortException();
        }
    }

unlock メソッド
- 指定された lock をコレクションから削除 or decrement
- コレクションから削除された場合、待機中のスレッドに通知

hmatui66

Chapter 5: Transaction Management - Transaction 実装

実装対象: Transaction, BufferList

Transaction

BufferList を使用して pin 留めした buffer を管理
各 Transaction オブジェクトはそれぞれ recovery manager と concurrency manager を生成
commit, rollback メソッド
- 残りの buffer を unpin
- recovery manager を呼び出して commit/rollback
- concurrency manager を呼び出して lock を解放

    public void commit() {
        recoveryMgr.commit();
        concurMgr.release();
        mybuffers.unpinAll();
        System.out.println("transaction " + txnum + " committed");
    }

    public void rollback() {
        recoveryMgr.rollback();
        concurMgr.release();
        mybuffers.unpinAll();
        System.out.println("transaction " + txnum + " roll back");
    }

getInt, getString メソッド
- 指定された block の slock を取得
- buffer から値を返す

    public int getInt(BlockId blk, int offset) {
        concurMgr.sLock(blk);
        Buffer buff = mybuffers.getBuffer(blk);
        return buff.contents().getInt(offset);
    }

    public String getString(BlockId blk, int offset) {
        concurMgr.sLock(blk);
        Buffer buff = mybuffers.getBuffer(blk);
        return buff.contents().getString(offset);
    }

setInt, setString メソッド
- concurrencyMgr から xlock 取得
- log record 作成 & lsn 取得
- buffer の setModified に lsn を記録

    public void setInt(BlockId blk, int offset, int val, boolean okToLog) {
        concurMgr.xLock(blk);
        Buffer buff = mybuffers.getBuffer(blk);
        int lsn = -1;
        if (okToLog)
            lsn = recoveryMgr.setInt(buff, offset, val);
        Page p = buff.contents();
        p.setInt(offset, val);
        buff.setModified(txnum, lsn);
    }

    public void setString(BlockId blk, int offset, String val, boolean okToLog) {
        concurMgr.xLock(blk);
        Buffer buff = mybuffers.getBuffer(blk);
        int lsn = -1;
        if (okToLog)
            lsn = recoveryMgr.setString(buff, offset, val);
        Page p = buff.contents();
        p.setString(offset, val);
        buff.setModified(txnum, lsn);
    }

size, append メソッド
- EOF マーカーを block number -1 として扱う
- size は↑の block の slock を取得し block 数を返す
- append は ↑の block の xlock を取得し block を追加する

    public int size(String filename) {
        BlockId dummyblk = new BlockId(filename, END_OF_FILE);
        concurMgr.sLock(dummyblk);
        return fm.length(filename);
    }

    public BlockId append(String filename) {
        BlockId dummyblk = new BlockId(filename, END_OF_FILE);
        concurMgr.xLock(dummyblk);
        return fm.append(filename);
    }

BufferList

ある transaction に対して pin 留めされている buffer のリストを管理
block の buffer 割り当てや pin 留め数を管理

hmatui66

Chapter 6: Record Management

record manager は block 内の値の配置に責務を持つ

Record Manager の設計

以下のような問題に対処する必要がある
- 各レコードは 1 つの block 内に配置する必要があるか
- block 内のレコードはすべて同じテーブルのものか
- 各フィールドはあらかじめ決められたバイト数で表現できるか
- 各フィールドの値はそのレコードのどこに配置すべきか
問題点の詳細とトレードオフは後述

Spanned or Unspanned Records

spanned record: 値が 2 つ以上の block にまたがる record
unspanned だと
disk スペースを浪費
- 例: block の 51 % の容量の record を連続して配置すると 49 % 分が使われない状態になる
block より大きなサイズの record は記録できない
spanned だと
record へのアクセスが複雑になる
メモリ上での record の再構築も必要

Homogeneous or Nonhomogeneous Files

homogeneous file: ファイル内の全ての record が同じテーブルのもの
homogeneous だと
単一テーブルに対するクエリは簡単に返せる
複数テーブルに対するクエリは効率が悪くなる
nonhomogeneous file: 同じファイル内にクラスタリングしたレコードを一緒に格納
nonhomogeneous だと
クラスタリングされたテーブルを結合するクエリの効率が向上
- 単一テーブルのクエリの効率は低下
  - 各テーブルのレコードがより多くのブロックに分散するため

Fixed-Length Versus Variable-Length Fields

ほとんどの型は固定長
整数、浮動小数点、日付/時刻型、...
可変長の表現は複雑
フィールドの変更時にレコードの大きさが変わると再配置が必要となることもある
文字列の3つの表現
a: 可変長表現
- 文字列が必要とする正確な量のスペースをレコードに割り当て
b: 固定長表現1
- 文字列をレコードの外部の場所に格納し、レコード内には固定長の参照を保持
c: 固定長表現2
- 各文字列に対して、長さに関係なく同じ量のスペースを割り当て
- スペースが無駄になりがち
上記の表現は SQL 標準の char, varchar, clob に対応
char: c
varchar: a
clob: b

Placing Fields in Records

固定長のレコードの場合、最も簡単な位置決め方法: 隣り合わせに格納
レコードのサイズは各フィールドのサイズの合計
オフセットは前のフィールドの終端
大抵のコンピューターでは整数はメモリ上の4の倍数の位置にある必要がある
record manager は全ての整数が 4 バイト境界にアラインされていることを確認
- 前のフィールドが 4 の倍数でない場所で終わっている場合パディングする
型が異なると必要とするパディングも変わることもある
倍精度浮動小数点数は 8 バイト境界にアライン
例: create table T (A smallint, B double precision, C smallint, D int, E int)
- B は倍精度浮動小数点数なので A は 6 バイトパディングをして B の開始位置を 8 の倍数に合わせる必要がある
- D は整数なので C は 2 バイトパディングして D の開始位置を 4 の倍数に合わせる必要がある
- -> 合計 28 バイト必要
パディングが最小になるようにフィールドを並び替える方法もある
↑の例だと [B, D, A, C, E] の順で格納すればパディングは不要となる
- -> 合計 20 バイト必要
フィールドだけでなくレコードのパディングもおこなう
[A, B, C, D, E] の順で格納する場合、2 レコード目の開始位置は 28 バイト目となるが、2 レコード目の B の開始位置が 36 (=28 + 8) バイト目となり、倍精度浮動小数点の 8 バイト境界に違反
1 レコードが 28 バイトの場合、レコードとしては 4 バイトのパディングが必要となる
Java ではバイト配列内の数値に直接アクセスできないので考慮不要
ByteBuffer.getInt は整数取得の機械語は使わないので(非効率だが)アライメント問題を回避できる

レコードファイルの実装についての考察

設計上の決定が実装にどのような影響を及ぼすかを考える

A Straightforward Implementation

homogeneous, unspanned, fixed-length なファイルを作る
- unspanned
  - ファイルを block のシーケンスとして扱うことができる
  - 各 block はそれ自身のレコードを含んでいる
- homogeneous & fixed-length
  - block 内の各レコードに同じ量のスペースを割り当てることができる
    - 各 block はレコードの配列として扱うことができる
  - -> SimpleDB ではこのような block を record page と呼ぶ
record page の実装
- block を slot に分割
- slot はレコード + 1 バイトを保持
  - 上記の 1 バイトは slot が空か使用中かを示すフラグ
    - 0: 空, 1: 使用中
  - 例: block サイズが 400, レコードサイズが 26 の場合
    - 各 slock は 27 バイトで、block には 14 個の slock があり、22 バイトの無駄なスペースがある
record page 内のレコードを insert, delete, modify するにはレコードに関する以下の情報が必要
- slock のサイズ
- レコードの各フィールドの name, type, length, offset
- -> これらを「レイアウト」と呼ぶ
レイアウトが与えられれば page 内の各値の位置を決定できる
- 新しいレコードを挿入
  - slock の空フラグを探して、使用中に変更
    - すべてのフラグが使用中であれば挿入は不可能
- レコードの削除
  - フラグを空に変更
- レコードの値の変更
  - 対象のフィールドの場所を特定し、その場所に値を書き込む
- レコードの取り出し
  - 使用中フラグを探す
  - レコードの識別
    - record page の場合は slot 番号で識別可能

Implementing Variable-Length Fields

variable-length フィールドを導入
問題1: レコード内のフィールドの offset が固定ではなくなる
- 特に variable-length フィールドに続くすべてのフィールドの offset はレコードごとに異なる
offset を決定するには、前のフィールドを読み、どこで終わるかを確認する必要がある
- 各レコードの先頭に fixed-length フィールド、末尾に variable-length フィールドを配置すると効率よくアクセスできる
問題2: フィールドの値を変更するとレコードの長さが変わる
- 新しい値が大きい場合、変更された値の後ろの block の内容をシフトする必要がある
- 極端なケースではシフトされたレコードが block から溢れる
  - overflow block を確保することで対処する
  - overflow block は複数になることもある
問題3: レコードの識別子に slot 番号を使用できない
- そもそも slot 番号が分かっていても variable-length なので slot サイズ * slot 番号 をしても slot の offset は計算できない
  - 先頭からレコードを読み込む必要あり
- variable-length なのでレコード削除後に slot のスペースが再利用できない状態(断片化)になる可能性があり、デフラグすると slot 番号が変わってしまう
- 解決方法は ID テーブルを使って ID と slot の位置を管理
- block 内の配置
  - block の一方の端に ID テーブル、もう一方の端にレコードを置く
    - 互いに向かいあって成長

Implementing Spanned Records

unspanned なレコードであれば各 block の最初のレコードは同じ位置から始まる
spanned なレコードでは状況が違う
- 各 block の先頭に整数を格納して、最初のレコードの offset を保持
spanned レコードの分割方法 2 パターン
1. block を可能な限り埋めて block 境界で分割し、残りのバイトをファイルの次の block に配置
  - こちらはスペースを無駄にしないが、block 間で値が分割されるので 2 つの block を連携して値を再構築する必要あり
2. レコードを値ごとに書き込み、ページが一杯になったら新しいページに書き込む

Implementing Nonhomogeneous Records

nonhomogeneous レコードをサポートする場合、variable-length レコードもサポートする必要がある
- 異なるテーブルのレコードはサイズも異なる可能性があるため
2 つの問題がある
1. block 内の各レコードのレイアウトを知る必要がある
2. 各レコードがどのテーブル由来のものであるかを知る必要がある
上記の 1 つ目の問題はレイアウトの配列を保持することで対処
2 つ目の問題は各レコードの先頭に タグ値 と呼ばれる値を追加することで対処
- タグ値: レイアウト配列のインデックス

hmatui66

Chapter 6 Record Management: Record Pages 実装

実装対象: Schema, Layout, RecordPage

Schema

[fieldname, type, length] の triple のリストを保持
フィールド追加や取得のメソッドを実装

Layout

レコードに関する物理的な情報も含む
フィールド, slot サイズ, フィールド offset を計算
コンストラクタは 2 つ
1. テーブル作成時に利用し、レイアウト情報を計算
2. テーブル作成後に呼び出され、以前計算された値を提供
slot の先頭には 空/使用フラグ のための 4 バイトを確保

RecordPage

ページ内のレコードを管理

getInt, getString: 指定された slot 番号のレコードのフィールドの値を返す

public int getInt(int slot, String fldname) {  
	int fldpos = offset(slot) + layout.offset(fldname);  
	return tx.getInt(blk, fldpos);  
}  
  
public String getString(int slot, String fldname) {  
	int fldpos = offset(slot) + layout.offset(fldname);  
	return tx.getString(blk, fldpos);  
}

slot 自体の offset とレコード内でのフィールドの offset を足して block 内での pos を算出して取得

nextAfter, insertAfter: ページ内の対象のレコードを検索
- nextAfter: 指定された slot に続く最初の空でない slot を探す
- insertAfter: 指定された slot に続く最初の空である slot を探す
- 空の slot が見つかったらフラグを 使用中 に変更して slot 番号を返す
- 内部で searchAfter というメソッドを利用
```
private int searchAfter(int slot, int used) {  
    slot++;  
    while(isValidSlot(slot)) {  
        if (tx.getInt(blk, offset(slot)) == used) {  
            return slot;  
        }  
        slot++;  
    }  
    return -1;  
}
```
- isValidSlot は指定された slot が block サイズ内に収まっている場合 true を返す
- used: EMPTY=0, USED=1

hmatui66

Chapter 6 Record Management: Table Scans 実装

実装対象: TableScan

TableScan

テーブルのレコードを管理するクラス

beforeFirst: 操作対象のレコードをファイルの最初の block の最初のレコードの 1 つ前へ

(分かりにくい...)

public void beforeFirst() {  
    moveToBlock(0);  
}  
  
private void moveToBlock(int blknum) {  
    close();  
    BlockId blk = new BlockId(filename, blknum);  
    rp = new RecordPage(tx, blk, layout);  
    currentslot = -1;  
}

next: 操作対象のレコードを 1 つ後ろにずらす

public boolean next() {  
    currentslot = rp.nextAfter(currentslot);  
    while (currentslot < 0) {  
        if (atLastBlock()) {  
            return false;  
        }  
        moveToBlock(rp.block().number() + 1);  
        currentslot = rp.nextAfter(currentslot);  
    }  
    return true;  
}

現在の block にそれ以上レコードがない場合、後続の block を読み込む

get/set/delete: 操作対象のレコードに対して実施
TableScan クラスは block 構造をクライアントから隠す

insert: 現在の slot より後ろの空 slot の位置に移動

public void insert() {  
    currentslot = rp.insertAfter(currentslot);  
    while (currentslot < 0) {  
        if (atLastBlock()) {  
            moveToNewBlock();  
        } else {  
            moveToBlock(rp.block().number() + 1);  
        }  
        currentslot = rp.insertAfter(currentslot);  
    }  
}

同一 block 内に空きがない場合は後続の block の空きを探す

hmatui66

Chapter 7 Metadata Management

レコードのレイアウトなどメタデータも管理する必要がある

The Metadata Manager

メタデータの種類
- テーブルのレコードの構造
- View のプロパティ
  - その定義や作成者など
- Index の記述
- 統計的な情報
  - 各テーブルのサイズとそのフィールド値の分布
  - クエリオプティマイザがクエリのコストを推定するのに利用
  - database が更新される度に生成

Table Metadata

※SimpleDB の TableMgr クラスを説明しているので、一般的な内容ではない

テーブル生成時にテーブル名とスキーマの情報と、レコードの offset を計算してカタログに保存
一般的なカタログの管理方法は database テーブルに格納
- tableCatalog(tablename varchar, slotsize int)
  - テーブルごとに 1 レコード
- filedCatalog(tablename varchar, fieldname varchar, type int, length int, offset int)
  - 各テーブルのフィールドごとに 1 レコード
TableScan を利用してテーブル情報登録 & 読み込み

View Metadata

View: クエリから動的に計算されるレコードを持つテーブル
- このクエリ = View の定義
- 定義を保存しておき、リクエスト時に定義を取得して処理
SimpleDB では ViewMgr が定義の管理をおこなう(情報は database テーブルに格納)
- viewCatalog(viewName, viewDef)
  - SimpleDB の制約上、viewDef は 100 文字以内
TableScan を利用してテーブル情報登録 & 読み込み

Statistical Metadata

統計情報: database 内の各テーブルのレコード数やフィールド値の分布など
- クエリプランナーがコストを見積もるために使用
- 優れた統計情報を使うとクエリの実行時間を大幅に改善できる
SimpleDB では 3 種類をピックアップ
- 各テーブルが使用する block 数
- 各テーブルのレコード数
- テーブルの各フィールドについてのカーディナリティ
統計情報の管理方法
1. database カタログに情報を格納し、database が変更されるたびに情報を更新
  - 統計情報を最新に保つためのコストが問題
    - insert, delete, setInt, setString の度にテーブルを更新
    - 同時実行性が低下
      - 統計情報を更新する際に xlock が取られる
      - 同一のテーブルに対する更新だけでなく、読み取り(slock取得)も lock 待ち
        
        厳密性は求められないので読み取り時に slock を取らない方法もとれる
2. 情報をメモリに保持し、エンジンの初期化時に計算する
  - 統計情報は比較的小さいのでメモリに収まるはず
  - 起動時に統計情報をゼロから計算する必要があるのが問題
  - 2 つのオプションがある
    1. database を更新する度に統計情報を更新
    2. 定期的にゼロから統計情報を再計算
      - SimpleDB ではこちらを採用

StatMgr 実装

getStatInfo

呼び出される度にカウンターをインクリメント
カウンターが特定の値に達すると統計情報をリフレッシュ

public synchronized StatInfo getStatInfo(String tableName, Layout layout, Transaction tx) {  
    numCalls++;  
    if (numCalls > 100)  
        refreshStatistics(tx);  
    StatInfo si = tableStats.get(tableName);  
    if (si == null) {  
        si = calcTableStats(tableName, layout, tx);  
        tableStats.put(tableName, si);  
    }  
    return si;  
}

refreshStatistics

テーブル情報が記録された tableCatalog テーブルをループ
テーブルごとにテーブルの統計情報を計算
簡略化のためフィールド値はカウントしない

private synchronized void refreshStatistics(Transaction tx) {  
    tableStats = new HashMap<>();  
    numCalls = 0;  
    Layout tableCatalogLayout = tblMgr.getLayout("tableCatalog", tx);  
    TableScan ts = new TableScan(tx, "tableCatalog", tableCatalogLayout);  
    while (ts.next()) {  
        String tableName = ts.getString("tableName");  
        Layout layout = tblMgr.getLayout(tableName, tx);  
        StatInfo si = calcTableStats(tableName, layout, tx);  
        tableStats.put(tableName, si);  
    }  
    ts.close();  
}  
  
private synchronized StatInfo calcTableStats(String tableName, Layout layout, Transaction tx) {  
    int numRecs = 0;  
    int numBlocks = 0;  
    TableScan ts = new TableScan(tx, tableName, layout);  
    while (ts.next()) {  
        numRecs++;  
        numBlocks = ts.getRid().blockNumber() + 1;  
    }  
    ts.close();  
    return new StatInfo(numBlocks, numRecs);  
}

Index Metadata

Index metadata の構成
- Index の名前
- Index 対象のテーブル名
- Index 対象のフィールドのリスト
Index Manager は上記の metadata を保存したり取得したりするコンポーネント
- metadata をカタログテーブルに格納 & 取得

IndexMgr 実装

コンストラクタ
- システム起動時に呼び出される
createIndex
- TableScan を用いて Index metadata をカタログテーブルに格納
getIndexInfo
- TableScan を用いて指定されたテーブルの Index metadata を取得
- Index の対象フィールドに対する IndexInfo クラス(詳細は後述)の Map を返す

IndexInfo 実装

コンストラクタ
- Index の名前、Index されたフィールド、関連するテーブルのレイアウト、統計 metadata を受け取る
- 統計 metadata によって Index レコードのスキーマを構築 & Index ファイルのサイズを推定
open
- HashIndex コンストラクタに Index の名前とスキーマを渡して Index を open
- HashIndex については後の章で説明
blocksAccessed
- Index を検索するために必要なブロックアクセス数の見積もりを返す
  - Index のサイズではない、とのこと
```
public int blocksAccessed() {  
    int rpb = tx.blockSize() / idxLayout.slotSize();  
    int numBlocks = si.recordsOutput() / rpb;  
    return HashIndex.searchCost(numBlocks, rpb);  
}
```
- rpb: おそらく record per block, si: 前節で実装した StatInfo
- Index ファイルのブロック数を算出した上で、HashIndex クラスの searchCost メソッドに渡してコストを返す
  - コスト: Indexを探索するためのブロックアクセス数
recordsOutput
- 検索キーを持つレコードの推定件数を返す
- テーブル内のレコード数を Index 付きフィールドの異なる値の数で割った値
```
public int recordsOutput() {  
    return si.recordsOutput() / si.distinctValues(fieldName);  
}
```
distinctValues
- 指定されたフィールドの個別値を返す
- また、Index 付きフィールドの場合は 1 を返す

Metadata Manager

これまで見てきた 4 つのマネージャクラスをラップ
metadata の種類毎に metadata を生成・保存、取得
- 統計 metadata は例外

hmatui66

Chapter 8 Query Processing

Database エンジンは SQL を関係代数(relational algebra)クエリに変換し、実行
この章では関係代数のクエリとその実装を紹介
- 次の 2 つの章では SQL から関係代数への変換を扱う

Relational Algebra

関係代数は演算子の集合で構成
各演算子は 1 つ以上のテーブルを入力 & 1 つ以上の出力テーブルを生成するという特殊なタスクを実行
これらの演算子を組み合わせることで複雑なクエリを構築
SimpleDB 版の SQL は 3 つの演算子を用いて実装
- select
  - 出力テーブルが入力テーブルと同じカラムを持ち、いくつかの行が削除されたもの
- project
  - 出力テーブルが入力テーブルと同じ行を持ち、いくつかの列が削除されたもの
- product
  - 出力テーブルが、2 つの入力テーブルのレコードのすべての可能な組み合わせから構成されるもの

Select

select 演算子
- 入力テーブルと述語の 2 つの引数を取る
- 例: select(STUDENT, GradYear=2019)
出力テーブル
- 述語を満たす入力レコードで構成される
- 常に入力テーブルと同じスキーマを持つ
select クエリ
- レコードのサブセットを持つテーブルを返す
例
- クエリ Q1: select(STUDENT, GradYear=2019)
  - 2019 年に卒業した生徒を見つける
- クエリ Q2: select(STUDENT, GradYear=2019 and (MajorId=10 or MajorId = 20))
  - 述語は、任意の真偽値の組み合わせが可能( SQL の where 句に相当)
  - 2019 年に卒業し、専攻が学科10または20のどちらかの生徒を見つける
- クエリ Q3: select(select(STUDENT, GradYear=2019), MajorId=10 or MajorId=20)
  - あるクエリの出力テーブルを別のクエリの入力にすることができる
  - Query2 と同等の結果となる
- クエリ Q4: select(Q1, MajorId=10 or MajorId=20)
  - Q3 の一部を Q1 を使用して表現したパターン
関係代数のクエリはクエリツリーとして絵として表現できる
- テーブルはリーフノード、演算子は内部ノード

Project

project 演算子
- 入力テーブルとフィールド名のセットという 2 つの引数を取る
- 例: project(STUDENT, {SName, GradYear})
出力テーブル
- 入力テーブルと同じレコードを持つが、スキーマには指定されたフィールドのみが含まれる
- 重複したレコードが含まれることがある
project クエリ
- project 演算子と select 演算子の両方で構成できる
例
- クエリ Q5: project(STUDENT, {SName, GradYear})
  - すべての学生の名前と卒業年を返す
- クエリ Q6: project(select(STUDENT, MajorId=10), {SName})
  - select 演算子も利用したパターン
  - 学科10 を先行しているすべての学生の名前をリストしたテーブルを返す

Product

product 演算子
- 複数のテーブルから情報を組み合わせて比較できる
- 例: product(STUDENT, DEPT)
出力テーブル
- 入力テーブルのレコードのすべての組み合わせ
- スキーマは入力スキーマのフィールドの和集合
  - 同じ名前の2つのフィールドを持たないよう、入力テーブルのフィールド名はバラバラである必要あり
例
- クエリ Q8: product(STUDENT, DEPT)
  - STUDENTに N レコード、DEPT に M レコードある場合、出力テーブルには NM レコードが含まれる
- クエリ Q9: select(product(STUDENT, DEPT), MajorId=Did)
  - DEPT テーブルの id で絞り込み

Scans

Scan: 関係代数クエリの出力を表す
以下は、SimpleDB における話
Scan は TableScan のサブセット
- クエリ、テーブルどちらも表せる
Scan オブジェクトはクエリツリーのノードに対応
- リレーショナル演算子ごとに Scan クラスがある
  - SelectScan, ProjectScan, ProductScan
- ツリーのリーフは TableScan となる

Update Scans

クエリは仮想テーブルを定義
Scan は仮想テーブルからの読み取りはできるるが、更新はできないメソッドを持つ
- すべての Scan が意味のある更新を行えるわけではない
Scan が更新可能な場合は？
- 出力レコードのすべてが、基礎となる database テーブルに対応するレコードをもつ場合
更新可能 Scan の場合、UpdateScan インターフェースをサポート
- 5 つの変更操作のメソッド
SimpleDB では TableScan と SelectScan が UpdateScan インターフェースを実装

Scan の実装

Scan (インターフェース)

各 Scan クラスが実装するインターフェース
レコードを読み取るメソッドを定義
- beforeFirst, next, getInt, getString, hasField, close

UpdateScan (インターフェース)

SelectScan など更新可能な Scan が実装するインターフェース
Scan インターフェースを拡張して、レコードを更新するメソッドを定義
- setInt, setString, insert, delete, getRid, moveToRid
レコードを読み取るメソッドを定義
- beforeFirst, next, getInt, getString, hasField, close

SelectScan

UpdateScan インターフェースを実装

constructor

基礎となる Scan と Predicate (述語) を受け取る

public SelectScan(Scan s, Predicate pred) {  
    this.s = s;  
    this.pred = pred;  
}

beforeFirst, getInt, getString, hasField
- 基礎となる Scan の対応するメソッドを呼び出すのみ

Predicate が満足するレコードを探す

public boolean next() {  
    while (s.next())  
        if (pred.isSatisfied(s))  
            return true;  
    return false;}

setInt (setString, insert, delete, getRid, moveToRid も同様)
- 基礎となる Scan を UpdateScan にキャストした上で、対応するメソッドを呼び出す
```
public void setInt(String fieldName, int val) {  
    UpdateScan us = (UpdateScan) s;  
    us.setInt(fieldName, val);  
}
```
- ClassCastException は起きないようにプランナーが Scan のツリーを作成することを前提とする

ProjectScan

Scan インターフェースを実装
projection は更新可能であるにも関わらず、実装する ProjectScan は UpdateScan を実装しない
- Exercise で実装を完成させる

constructor

基礎となる Scan と出力フィールドのリストを受け取る

public ProjectScan(Scan s, List<String> fieldList) {  
    this.s = s;  
    this.fieldList = fieldList;  
}

beforeFirst, next, getInt, getString,
- 基礎となる Scan の対応するメソッドを呼び出すのみ

hasField

出力フィールドのリストに含まれるフィールドかどうかを判定

public boolean hasField(String fieldName) {  
    return fieldList.contains(fieldName);  
}

ProductScan

Scan インターフェースを実装
コンストラクタで受け取る 2 つの Scan について多重にループしつつ結果を返す

constructor

基礎となる Scan s1, s2 を受け取り、beforeFirst を呼び出し

public ProductScan(Scan s1, Scan s2) {  
    this.s1 = s1;  
    this.s2 = s2;  
    beforeFirst();  
}

beforeFirst

s1 の 1 件目、s2 の 0 件目のレコードに index をセット

public void beforeFirst() {  
    s1.beforeFirst();  
    s1.next();  
    s2.beforeFirst();  
}

s2 のレコードが尽きたら s1 のレコードを進めて s2 を先頭レコードに戻す

if (s2.next())  
    return true;  
  
s2.beforeFirst();  
return s2.next() && s1.next();

getInt, getString

対象のフィールドを持っている Scan を確認して返す

public int getInt(String fieldName) {  
    if (s1.hasField(fieldName))  
        return s1.getInt(fieldName);  
  
    return s2.getInt(fieldName);  
}

hasField

s1, s2 の hasField を用いて結果を返す

public boolean hasField(String fieldName) {  
    return s1.hasField(fieldName) || s2.hasField(fieldName);  
}

close
- s1, s2 両方の close を呼び出す

Pipelined Query Processing

前項の 3 つの関係代数演算子の実装には 2 つの共通点がある
- 出力レコードは必要に応じて一度に 1 つずつ生成される
- 出力レコードを保存せず、また中間の計算も保存しない
これらの実装はパイプライン型と呼ばれる
パイプライン化された実装は効率的
- Project, Select の場合
  - 対象のテーブルのスキャンは 1 回だけ
- Product の場合
  - 対象のテーブルのスキャンが複数回実行されうるため、出力レコードを一時テーブルに格納する実装などもある(後述されるとのこと)

Predicates(述語)

与えられた Scan の各行に対して、真か偽かを返す条件
Predicate の構造
- Predicate は Term(項)や Term の boolean 結合
- Term は 2 つの Expression(式)の間の比較
- Expression は Constans(定数)とフィールド名に対する操作で構成
- Constans は整数や文字列などあらかじめ決められた型の値
SimpleDB では許容する表現を単純化

Constant の実装

public class Constant implements Comparable<Constant> {  
    private Integer iVal = null;  
    private String sVal = null;  
  
    public Constant(Integer iVal) {  
        this.iVal = iVal;  
    }  
  
    public Constant(String sVal) {  
        this.sVal = sVal;  
    }
    // equals, hashCode, compareTo, toString などを実装
}

Interger か String を持つ

Expression の実装

public class Expression {  
    private Constant val = null;  
    private String fieldName = null;  
  
    public Expression(Constant val) {  
        this.val = val;  
    }  
  
    public Expression(String fieldName ) {
	    this.fieldName = fieldName;  
	}
}

定数かフィールド名を持つ
evalute
- スキャンの現在の出力レコードに関する式の値を返す
```
public Constant evaluate(Scan s) {  
    return (val != null) ? val : s.getVal(fieldName);  
}
```
- 式が定数の場合は Scan は無視
- 式がフィールドである場合 Scan からフィールドの値を返す

appliesTo

式のスコープを決定するために利用

public boolean appliesTo(Schema sch) {  
    return val != null || sch.hasField(fieldName);  
}

Term の実装

constructor

左辺の式と右辺の式を受け取る

public Term(Expression lhs, Expression rhs) {  
    this.lhs = lhs;  
    this.rhs = rhs;  
}

isSatisfied

与えられた Scan で左辺の式と右辺の式が同じ値に評価された場合に true を返す

public boolean isSatisfied(Scan s) {  
    Constant lhsVal = lhs.evaluate(s);  
    Constant rhsVal = rhs.evaluate(s);  
    return rhsVal.equals(lhsVal);  
}

残りのメソッドは query planner 向けのもの
- reductionFactor
  - 述語を満たすレコードの予想数を決定
    - 後述
- equatesWithConstant, equatesWithField
  - query planner がいつ index を使用するかを決定するのを助ける
    - 後述

Predicate の実装

Term のリストを保持

各 Term の対応するメソッドを呼び出す

public boolean isSatisfied(Scan s) {  
    for (Term t : terms)  
        if (!t.isSatisfied(s))  
            return false;  
    return true;
}
public int reductionFactor(Plan p) {  
    int factor = 1;  
    for (Term t : terms) {  
        factor *= t.reductionFactor(p);  
    }  
    return factor;  
}
// ...

hmatui66

Chapter 9 Parsing

パーザは言語の構文解析器
metadata については何も知らないので SQL の意味を評価することはできない
- metadata を調べる責任は planner
  - 後述

Lexical Analysis

入力文字列をトークンに分割
- トークンには型と値がある
SimpleDB の lexical analyzer は 5 つのトークンタイプをサポート
- カンマなどの1文字の区切り文字
- 整数定数
- 文字列定数
- キーワード(select, from, where, ...)
- 識別子(テーブル名, フィールド名, ...)

Lexer 実装

java.io.StreamTokenizer を利用

delimiter, int, String, keyword, id などを判定したり eat(consume)して返すメソッドを実装

一部抜粋

public boolean matchDelim(char d) {  
   return d == (char)tok.ttype;  
}
public void eatDelim(char d) {  
   if (!matchDelim(d))  
      throw new BadSyntaxException();  
   nextToken();  
}
public boolean matchKeyword(String w) {  
   return tok.ttype == StreamTokenizer.TT_WORD && tok.sval.equals(w);  
}
public void eatKeyword(String w) {  
   if (!matchKeyword(w))  
      throw new BadSyntaxException();  
   nextToken();  
}
public boolean matchId() {  
    return tok.ttype == StreamTokenizer.TT_WORD
	    && !keywords.contains(tok.sval);  
}
public String eatId() {  
    if (!matchId())  
        throw new BadSyntaxException();  
    String s = tok.sval;  
    nextToken();  
    return s;  
}
// ...
private void initKeywords() {  
    keywords = Arrays.asList(
        "select", "from", "where", "and",
        "insert", "into", "values", "delete", "update", "set", 
        "create", "table", "int", "varchar",
        "view", "as", "index", "on"
    );  
}

keywords リストは id に指定された文字が keyword ではないことを確認することにしか使ってないが、matchKeyword でも使った方が良い気がする

Grammer

トークンをどのように組み合わせることができるかを記述したルールセット
文法規則の例
- <Field> := IdTok
- 左辺は構文カテゴリ: <Field> はフィールド名という概念を表す
- 右辺は構文カテゴリに属する文字列の集合を指定するパターン
SimpleDB がサポートする文法規則
- <Field> := IdTok
- <Constant> := StrTok | IntTok
- <Expression> := <Field> | <Constant>
- <Term> := <Expression> = <Expression>
- <Predicate> := <Term> [ AND <Predicate> ]
- <Query> := SELECT <SelectList> FROM <TableList> [ WHERE <Predicate> ]
- <SelectList> := <Field> [ , <SelectList> ]
- <TableList> := IdTok [ , <TableList> ]
- <UpdateCmd> := <Insert> | <Delete> | <Modify> | <Create>
- <Create> := <CreateTable> | <CreateView> | <CreateIndex>
- <Insert> := INSERT INTO IdTok ( <FieldList> ) VALUES ( <ConstList> )
- <FieldList> := <Field> [ , <FieldList> ]
- <ConstList> := <Constant> [ , <ConstList> ]
- <Delete> := DELETE FROM IdTok [ WHERE <Predicate> ]
- <Modify> := UPDATE IdTok SET <Field> = <Expression> [ WHERE <Predicate> ]
- <CreateTable> := CREATE TABLE IdTok ( <FieldDefs> )
- <FieldDefs> := <FieldDef> [ , <FieldDefs> ]
- <FieldDef>:= IdTok <TypeDef>
- <TypeDef> := INT | VARCHAR ( IntTok )
- <CreateView> := CREATE VIEW IdTok AS <Query>
- <CreateIndex> := CREATE INDEX IdTok ON IdTok ( <Field> )

Recursive-Descent Parsers

SimpleDB の SQL の文法は単純で再帰下降構文解析で解析できる
基本的なパーザは解析のみ
- query planner が必要とする情報を返すように変更する必要がある
  - adding actions to the parser
SQL パーザは SQL 文から情報を抽出する
- テーブル名、フィールド名、述語、定数など

Parsing Predicate

SimpleDB がサポートするPredicate の文法に従ってパーズ

expression までの処理の抜粋

public Expression expression() {  
    if (lex.matchId())  
        return new Expression(field());  
    else        
	    return new Expression(constant());  
}  
  
public Term term() {  
    Expression lhs = expression();  
    lex.eatDelim('=');  
    Expression rhs = expression();  
    return new Term(lhs, rhs);  
}  
  
public Predicate predicate() {  
    Predicate pred = new Predicate(term());  
    if (lex.matchKeyword("and")) {  
        lex.eatKeyword("and");  
        pred.conjoinWith(predicate());  
    }  
    return pred;  
}

Parsing Queries

SimpleDB がサポートする Query の文法に従ってパーズ

public QueryData query() {  
    lex.eatKeyword("select");  
    List<String> fields = selectList();  
    lex.eatKeyword("from");  
    Collection<String> tables = tableList();  
    Predicate pred = new Predicate();  
    if (lex.matchKeyword("where")) {  
        lex.eatKeyword("where");  
        pred = predicate();  
    }  
    return new QueryData(fields, tables, pred);  
}

Parsing Updates

SimpleDB がサポートする UpdateCmd の文法に従ってパーズ
文字列の最初のトークンをもとに各パーズ処理にディスパッチ

public Object updateCmd() {  
    if (lex.matchKeyword("insert"))  
        return insert();  
    else if (lex.matchKeyword("delete"))  
        return delete();  
    else if (lex.matchKeyword("update"))  
        return modify();  
    else
        return create();  
}  
private InsertData insert() {  
    lex.eatKeyword("insert");  
    lex.eatKeyword("into");  
    String tblName = lex.eatId();  
    lex.eatDelim('(');  
    List<String> fields = fieldList();  
    lex.eatDelim(')');  
    lex.eatKeyword("values");  
    lex.eatDelim('(');  
    List<Constant> vals = constList();  
    lex.eatDelim(')');  
    return new InsertData(tblName, fields, vals);  
}

// ... delete, update

private Object create() {  
    lex.eatKeyword("create");  
    if (lex.matchKeyword("table"))  
        return createTable();  
    else if (lex.matchKeyword("view"))  
        return createView();  
    else
        return createIndex();  
}
private CreateTableData createTable() {  
    lex.eatKeyword("table");  
    String tblName = lex.eatId();  
    lex.eatDelim('(');  
    Schema sch = fieldDefs();  
    lex.eatDelim(')');  
    return new CreateTableData(tblName, sch);  
}

// .. createView, createIndex

hmatui66

Chapter 10 Planning

パーズの次のステップは、抽出したデータを関係代数クエリツリーに変換すること
このステップを計画と呼ぶ
等価なクエリツリーは複数あるがコストが異なる
- この章では基本的な計画作成プロセスについて検討
- 15 章で最適な計画を作成するトピックを扱う

Verification

planner の最初の責務は、SQL 文が意味があるかの判断
以下を確認
- 言及されたテーブルとフィールドがカタログに存在
- 言及されたフィールドは曖昧ではない
- フィールドに対するアクションは正しい型である
- すべての定数は、そのフィールドに対して正しいサイズと型である
SmpleDB の planner は上記の検証はしていない
- Exercise 対象

The Cost of Evaluating a Query Tree

planner の第2の責務は、関係代数クエリツリーを構築すること
クエリの実行時間に対する重要な寄与はブロックアクセス数
各関係演算子はそれぞれの独自のコスト算出式を持っている

s	B(s)	R(s)	V(s, F)
TableScan(T)	B(T)	R(T)	V(T, F)
SelectScan(s1, A=c)	B(s1)	R(s1)/V(s1, A)	1 if F = A V(s1, F) if F ≠ A
SelectScan(s1, A=B)	B(s1)	R(s1)/max{V(s1, A), V(s1, B)}	min{V(s1, A), V(s1, B)} if F = A,B V(s1, F) if F ≠ A,B
ProjectScan(s1, L)	B(s1)	R(s1)	V(s1, F)
ProductScan(s1, s2)	B(s1) + R(s1)*B(s2)	R(s1)*R(s2)	V(s1, F) if F is in s1 V(s2, F) if F in s2

B(s): Scan の出力を構成するのに必要なブロックアクセス数
R(s): Scan の出力に含まれるレコード数
V(s, F): Scan に出力に含まれる異なる F の値(F-values)の個数
- F の値とは?
  - F値 (曖昧さ回避): wikipediaの中の「F検定」...?後で調べる
  - 単に F というフィールドの値という意味っぽい
planner はそれぞれの値をどのように計算するか？
- product の場合、B(s) の値は 2 つのテーブルのブロック数とその左側の Scan のレコード数に依存
- select の場合、R(s) は Predicate で言及されたフィールドの異なる値の数に依存

Table Scan のコスト

B(s), R(s), V(s, F) の値は基礎となるテーブルのブロック数、レコード数、個別の値となる

Select Scan のコスト

B(s) は基礎となる Scan(s1) と全く同じ数のブロックアクセスが必要なので B(s1) と同様
R(s), V(s, F) の計算は Predicate に依存
- 定数に対する選択: SelectScan(s1, A=c)
  - A の値が等しく分布していると仮定するとマッチするのは R(s1)/V(s1, A) のレコード
  - 均等に分布する仮定は、出力において他のフィールドの値も均等に分布していることを意味する
    - V(s, A) = 1
      - A は定数マッチしているもののみ
    - V(s, F) = V(s1, F)
      - A のフィールドでマッチさせても分布は変わらない
- フィールドに対する選択: SelectScan(s1, A=B)
  - このケースでは A と B は何らかの関係があると考えられる
  - R(s) = R(s1) / max{V(s1, A), V(s1, B)} となる理由
    - もし B の値が A の値よりも多い場合、すべての A の値は B 内にあると仮定する
    - もし A の値が B の値よりも多い場合、すべての B の値は A 内にあると仮定する
    - (上記の仮定は A と B がキーと外部キーの関係の場合は確実に成り立つ)
    - s1 のレコードを考える
      - B の値が A の値より多いと仮定すると
        
        A の値が B の値と一致する確率は 1/V(s1, B)
      - A の値が B の値より多いと仮定すると
        
        B の値が A の値と一致する確率は 1/V(s1, A)
    - 上記の確率の大きな方で R(s1) を割ると R(s) となる
  - V(s, F) の値は等分布を仮定すると
    - min(V(s1, A), V(s1, B)} for F = A or B
      - それはそう
    - V(s1, F) for all fields F other than A or B
      - こちらも等分布なので絞り込んで変わらない

Project Scan のコスト

B(s) = B(s1), R(s) = R(s1), V(s, F) = V(s1, F) for all fields F
- 基礎となる Scan(s1) で必要とされる以上の追加のブロックアクセスは必要ではない
- project 操作はレコードの数、値を変更しない

Product Scan のコスト

基礎となる Scan は s1, s2 の2つで出力はそれらのすべての組み合わせ
B(s) = B(s1) + (R(s1) * B(s2))
- ProductScan(s1, s2) と ProductScan(s2, s1) のブロックアクセス数は異なることがある
- 論理的にはどちらも一緒なので、上記の式で算出したブロックアクセス数が少ない方を利用した方がコストが低い
R(s) = R(s1) * R(s2), V(s, F) = V(s1, F) or V(s2, F), depending on which schema F belongs to
- これらは自明

Plan の実装

Plan インターフェース

public interface Plan {  
	// Plant に対応する Scan を開く
	public Scan open();  

	// ブロックアクセス数
	public int blockAccessed();  

	// レコード数
	public int recordsOutput();  

	// 値の数
	public int distinctValues(String fieldName);  

	public Schema schema();  
}

TablePlan

基礎となるテーブルスキャンのプラン

constructor

public TablePlan(Transaction tx, String tblName, MetadataMgr md) {  
    this.tblName = tblName;  
    this.tx = tx;  
    layout = md.getLayout(tblName, tx);  
    si = md.getStatInfo(tblName, layout, tx);  
}

metadata マネージャーを受け取って、レイアウトや統計情報を取得して保持

blockAccessed, recordOutput, distinctValues
- 統計情報 si の対応するメソッドを呼び出して返す

SelectPlan

constructor

public SelectPlan(Plan p, Predicate pred) {  
    this.p = p;  
    this.pred = pred;  
}

基礎となる Plan と Predicate を受け取る

blockAccessed

public int blockAccessed() {  
    return p.blockAccessed();  
}

基礎となる Plan と同じ値

recordsOutput

public int recordsOutput() {  
    return p.recordsOutput() / pred.reductionFactor(p);  
}

基礎となる Plan を Predicate で絞り込む

distinctValues

public int distinctValues(String fieldName) {  
    if (pred.equatesWithConstant(fieldName) != null)  
        return 1;  
    else {  
        String fieldName2 = pred.equatesWithField(fieldName);  
        if (fieldName2 != null)  
            return Math.min(  
                    p.distinctValues(fieldName),  
                    p.distinctValues(fieldName2)  
            );  
        else
	        return p.distinctValues(fieldName);  
    }  
}

定数によって選択される場合: 1
他のフィールドによって選択される場合: 2 つのフィールドのうち値が少ない方の数
それ以外の場合は基礎となる Plan と同じ値

ProjectPlan

blockAccessed, recordOutput, distinctValues
- 基礎となる Plan の対応するメソッドを呼び出して返す

ProductPlan

constructor

public ProductPlan(Plan p1, Plan p2) {  
    this.p1 = p1;  
    this.p2 = p2;  
    schema.addAll(p1.schema());  
    schema.addAll(p2.schema());  
}

基礎となる 2 つの Plan を受け取る

blockAccessed
```
public int blockAccessed() {  
    return p1.blockAccessed() + p1.recordsOutput() * p2.blockAccessed();  
}
```
- 前節で検討した通り、基礎となる Plan のブロックアクセス数、レコード数を用いて算出

recordsOutput

public int recordsOutput() {  
    return p1.recordsOutput() * p2.recordsOutput();  
}

前節で検討した通り、基礎となる Plan のレコード数を用いて算出

distinctValues

public int distinctValues(String fieldName) {

    if (p1.schema().hasField(fieldName))
        return p1.distinctValues(fieldName);
    else
		return p2.distinctValues(fieldName);
}

対象のフィールドを保持する Plan に基づいて返す

Query Planning

SimpleDB は単純化された SQL のサブセットのみをサポート
- 計算、ソート、グループ化、入れ子、名前の変更を含まない
- select, project, product の 3 つの演算子のみを使用したクエリツリーで実装
アルゴリズム
1. from 句にある各テーブルに対する Plan を構築
  1. T がテーブルである場合、T に対する Plan
  2. T が View である場合、Plan は T の定義に対してこのアルゴリズムを再帰的に呼び出した結果
2. これらの Plan の product を与えられた順で取る
3. where 句にある述語で select する
4. select 句のフィールドに project する

BasicQueryPlanner 実装

public Plan createPlan(QueryData data, Transaction tx) {  
    // Step 1: Create a plan for each mentioned table or view.  
    List<Plan> plans = new ArrayList<>();  
    for (String tblName : data.tables()) {  
        String viewDef = mdm.getViewDef(tblName, tx);  
        if (viewDef != null) { // Recursively plan the view.  
            Parser parser = new Parser(viewDef);  
            QueryData viewData = parser.query();  
            plans.add(createPlan(viewData, tx));  
        } else {  
            plans.add(new TablePlan(tx, tblName, mdm));  
        }  
    }  
  
    // Step 2: Create the product of all table plans  
    Plan p = plans.remove(0);  
    for (Plan nextPlan : plans)  
        p = new ProductPlan(p, nextPlan);  
  
    // Step 3: Add a selection plan for the predicate  
    p = new SelectPlan(p, data.pred());  
  
    // Step 4: Project on the field names  
    p = new ProjectPlan(p, data.fields());  
    return p;  
}

基本的なクエリプランの作成
QueryData.tables によって返される順序で ProductPlan を作成
metadata は利用しないので、性能は不安定

ProductPlan 作成の小さな改良版

// Step 2: Create the product of all table plans  
Plan p = plans.remove(0);  
for (Plan nextPlan : plans) {  
    // Try both orderings and choose the one having the lowest cost  
    Plan choice1 = new ProductPlan(nextPlan, p);  
    Plan choice2 = new ProductPlan(p, nextPlan);  
    if (choice1.blockAccessed() < choice2.blockAccessed())  
        p = choice1;  
    elsep = choice2;  
}

まだクエリ内のテーブルの順番に依存
商用 DB はより洗練したアルゴリズムを使用
- 最適な Plan の選択は後述

BasicUpdatePlanner 実装

executeDelete, executeModify

SelectPlan を用いて対象のレコードを特定した上で操作を行う

public int executeDelete(DeleteData data, Transaction tx) {  
    Plan p = new TablePlan(tx, data.tableName(), mdm);  
    p = new SelectPlan(p, data.pred());  
    UpdateScan us = (UpdateScan) p.open();  
    int count = 0;  
    while (us.next()) {  
        us.delete();  
        count++;  
    }  
    us.close();  
    return count;  
}

executeInsert

TablePlan を用いて insert 操作を行う

public int executeInsert(InsertData data, Transaction tx) {  
    Plan p = new TablePlan(tx, data.tableName(), mdm);  
    UpdateScan us = (UpdateScan) p.open();  
    us.insert();  
    Iterator<Constant> iter = data.vals().iterator();  
    for (String fieldName : data.fields()) {  
        Constant val = iter.next();  
        us.setVal(fieldName, val);  
    }  
    us.close();  
    return 1;  
}

executeCreateTable, executeCreateView, executeCreateIndex

metadata manager の対応するメソッドを呼ぶのみ

public int executeCreateTable(CreateTableData data, Transaction tx) {  
    mdm.createTable(data.tableName(), data.newSchema(), tx);  
    return 0;  
}

Planner

SQL 文を Plan に変換するコンポーネント
- Parser を用いて SQL 文を QueryData や ModifyData(, DeleteData, ...) に変換
- QueryPlanner , UpdatePlanner に処理を委譲
createQueryPlan
- Plan を作成して返す
executeUpdate
- Plan を作成して実行して影響を受けたレコード数を返す

使用感

public static void main(String[] args) {  
    SimpleDB db = new SimpleDB("dbdir/plannertest1");  
    Transaction tx = db.newTx();  
    Planner planner = db.planner();  
    String cmd = "create table T1(A int, B varchar(9))";  
    planner.executeUpdate(cmd, tx);  
  
    int n = 200;  
    System.out.println("Inserting " + n + " random records into T1.");  
    for (int i = 0; i < n; i++) {  
        int a = (int) Math.round(Math.random() * 50);  
        String b = "bbb" + a + "(idx=" + i + ")";  
        cmd = "insert into T1(A, B) values(" + a + ", '" + b + "')";  
        planner.executeUpdate(cmd, tx);  
    }  
  
    cmd = "create table T2(C int, D varchar(9))";  
    planner.executeUpdate(cmd, tx);  
    System.out.println("Inserting " + n + " records into T2.");  
    for (int i = 0; i < n; i++) {  
        int c = n - i -1;  
        String d = "ddd" + c + "(idx=" + i + ")";  
        cmd = "insert into T2(C,D) values(" + c + ", '" + d + "')";  
        planner.executeUpdate(cmd, tx);  
    }  
  
    String query = "select B,D from T1,T2 where A=C";  
    Plan p = planner.createQueryPlan(query, tx);  
    Scan s = p.open();  
    while (s.next())  
        System.out.println(s.getString("b") + " " + s.getString("d"));  
    s.close();  
    tx.commit();  
}

create table, insert, select などの SQL 文を実行できるようになっている
- 2 テーブルのフィールド値の一致条件も使えている

hmatui66

Chapter 11 JDBC Interfaces

後回し

hmatui66

Chapter 12 Indexing

static hashing, extendable hashing, B-trees について取り上げる
index を利用した関係代数演算も開発

Index の価値

絞り込み対象のフィールドの値でソートされていれば、バイナリサーチでレコードを特定できる
- テーブルは複数の index を持てる
index は役に立たないこともある
- フィールド A に対する index の有用性は、テーブル内の異なる A の値の数に比例
- index されたフィールドがテーブルの PrimaryKey である場合、最も有用
- 異なる A の値の数がブロックごとのレコード数より少ない場合、役に立たない

SimpleDB の index

Index インターフェースにおける宣言メソッドは TableScan のメソッドと似ている
- well-known な特定の方法で使用されるため、より明確
  - index を検索する際は常に値(検索キー)を指定
  - すべての index レコードは同じ 2 つのフィールドを持つので、汎用の値の Getter が不要になる

Static Hash Indexes

最もシンプルな index の実装
最も効率的とは言えないが理解しやすく、原理も明確
0 から N-1 までの固定数 N のバケットを使用
各 index レコードは dataVal を hash 化した結果のバケットに割り当てられる
- index レコードの格納するには
  - hash 関数によって割り当てられたバケットに入れる
- index レコードを見つけるには
  - 検索キーを hash 化して対応するバケットを調べる
- index レコードを削除するには
  - index レコードを見つけてからバケットから削除する
hash index の検索コスト
- バケットの数に反比例
- index が B ブロックを含む & バケットが N 個ある場合
  - バケットを検索するには B/N ブロックアクセスが必要
例: ブロックサイズが 4k バイト, バケット数が 1024, dataVal が varchar(10) の場合
- index レコードは 23 バイト(dataVal + dataRid + 空/使用フラグ )
- ブロックには 178 の index レコードが収まる
- -> 2 回のブロックアクセスを想定すると 364,544 レコード(=178 * 1024 * 2)を検索できる

Static Hash Indexes 実装

各バケットを別々のテーブルに格納
- 名称: index 名 + バケット番号

beforeFirst

検索キーを hash 化し、バケットに対する TableScan を開く

public void beforeFirst(Constant searchKey) {  
    close();  
    this.searchKey = searchKey;  
    int bucket = searchKey.hashCode() % NUM_BUCKETS;  
    String tblName = idxName + bucket;  
    this.ts = new TableScan(tx, tblName, layout);  
}

TableScan の現在の位置から開始し、検索キーを持つレコードが見つかるまで読み進める

public boolean next() {  
    while (ts.next())  
        if (ts.getVal("dataVal").equals(searchKey))  
            return true;  
    return false;
}

searchCost
- IndexInfo.blocksAccessed によって呼び出される
```
public static int searchCost(int numBlocks, int rpb) {  
    return numBlocks / HashIndex.NUM_BUCKETS;  
}
```
- 第二引数はブロックごとに index レコード数だが、HashIndex では使われない

Extendable Hash Indexes

Static Hash Index の検索コストはバケットの数に反比例
- バケットを多く使えば使うほど各バケットのブロック数は少なくなる
- 最も望ましいのは各バケットがちょうど 1 ブロックの長さになること
将来の必要性に基づいてバケットを多く用意すると、初期は無駄なスペースとなる
Extendable hashing(拡張可能ハッシュ)は上記の問題を解決
- 各バケットが 1 ブロックより長くならないことを保証
- 複数のバケットが同じブロックを共有できるようにすることで、無駄なスペースを無くす
2 つのファイルによって実現
- バケットファイル
  - index ブロックが格納されている
- バケットディレクトリ
  - バケットとブロックの対応付けを行う
  - 整数の配列と考えることができる
    - 検索キーの hash 値とバケットファイル(の番号)のマッピング情報を保持
  - index レコードが少ないうちは、異なる hash 値(hash 化 & mod 計算結果) を同一のブロックに割り当てることができる
    - (レコードが溢れた場合は再配置が必要になりそう)
バケットファイルの特定方法
1. 検索キーを hash 化
  - 例: hash 値=12
2. 上記の値をバケットディレクトリ(整数配列)の長さで mod 計算
  - 例: バケットディレクトリの長さが 8 の場合は 4
3. 上記の値をバケットディレクトリの index として値を取得
  - 例: バケットディレクトリの index=4 の値が 1
4. 上記の値が対応するバケット
  - 例: バケットファイルの番号は 1
複数のバケットでブロックを共有するためのパケットディレクトリの設定方法はたくさんあるので後述

$2^M$ のバケットを持つバケットディレクトリは M ビットの長さの hash 値をサポートできる
- M: 整数 & index の最大深度と呼ばれる
- 整数値は 32 ビットなので M=32 が妥当
初期状態はすべてのディレクトリエントリは 1 つのブロックを指す
- 新しい index レコードはすべてのこのブロックに挿入
バケットファイル内のすべてのブロックはローカル深度を持つ
- ローカル深度L とは
  - ブロック内のすべてのレコードの hash 値が同じ右端の L ビットを持つことを意味する
- ファイルの最初のブロックは任意の hash 値を持つことができるので L = 0 となる
ある index レコードが割り当てられたブロックに収まらない場合
- ブロックは分割されレコードは分配される
  - 再分配のアルゴリズムはブロックのローカル深度に基づく
    - ブロック内のすべてのレコードは右端の L ビットが同じ
    - L+1 ビットが 0 ならばもとのブロック、1 ならば新しいブロックに移動
    - -> ブロックのローカル深度は 1 増加
- 分配後、バケットディレクトリを調整する
  - もとのブロックを指すディレクトリエントリを特定
  - 右端から L+1 ビットが1であるものは追加されたブロックを指すように変更
分割の例:
どのような hash 法でもレコードが均等に分散される保証はない
- ブロックが分割される時、該当のブロックが含むレコードは同じブロックに割り当たるかもしれない
- ローカル深度が最大深度に達するとそれ以上の分割は不可能
  - オーバーフローブロックを作成する必要がある

Compacting the Bucket Directory

バケットディレクトリも必要に応じて拡張できる
↑の図のバケットディレクトリのエントリーは特定のパターンになっている
- あるブロックのローカル深度が0であれば、すべてのバケットエントリーはそのブロックを指す
- あるブロックのローカル深度が2であれば、バケットは4つごとにそのブロックを指す
一般的に、あるブロックのローカル深度が L であれば $2^L$ 個のバケットがそのブロックを指していることになる
- ローカル深度が最も深いものがディレクトリの周期を決定
- ディレクトリのエントリーが繰り返される=ディレクトリ全体を保存する必要はない
  - 最も深いローカル深度 d に対して $2^d$ エントリー分だけを保持すれば良い
    - d: インデックスのグローバル深度、という
インデックスを検索するアルゴリズムの修正点
- 検索キーをハッシュ化後に右端 d ビットを利用してバケットを特定
- 挿入時、ブロックの分割によってローカル深度がグローバル深度よりも大きくなる場合はグローバル深度をインクリメント
  - バケットディレクトのサイズが2倍になる
    - エントリは繰り返されるため、前半の情報を後半にコピーするので OK
参考
- https://en.wikipedia.org/wiki/Extendible_hashing

hmatui66

Chapter 12 Indexing: B-Tree Indexes

図の説明
- (a)ソート済の index のファイル
- (b) index ファイルのレベル 0 のディレクトリ
  - ディレクトリ内のレコードを dataVal (amy, bob, max など) 順に並べると隣接するディレクトリのエントリを比較してブロックの値の範囲を決定できる
- (c) ディレクトリと index ブロックをツリーとして表現したもの
B-tree が大きく成長した際に対処する必要がある 3 つの問題
- ディレクトリが数ブロックになる可能性がある
- 新しく挿入された index レコードはブロックに収まらないかもしれない
- 同じ dataVal を持つ index レコードが複数存在する可能性がある

A Directory Tree

図の説明
- ディレクトリブロックは 2 つのレベルに分かれている
- Level 0: index ブロックを指し示すブロックが含まれる
- Level 1: Level 0 のブロックを指し示すブロックが含まれる
- ディレクトリレコードにおける名前の分布の注意
  - "eli" は Level1 には現れるが Level 0 には現れない
  - 各 index ブロックの dataVal は B-tree のあるレベルのディレクトリブロックに一度だけ現れる
検索コストはディレクトリのレベルの数に 1 を加えたものとなる
例
- 4K バイトのブロック
  - 22 バイトのインデックスレコードだと 178 個収まる
  - 18 バイトのディレクトリレコードだと 227 個収まる
- Level 0 の B-tree は 2 回のブロックアクセスで 40,406 index レコードにアクセスできる
  - 227 * 178
- Level 1 の B-tree は 3 回のブロックアクセスで 9,172,162 index レコードにアクセスできる
  - 227 * 227 * 178
- Level 2 の B-tree は 4 回のブロックアクセスで 2,082,080,774 index レコードにアクセスできる
  - 227 * 227 * 227 * 178

Inserting Records

挿入時にブロックに空きが無い場合はブロックを分割
- index ファイルに新しいブロックを割り当てる
- index レコードの高い値側の半分を新しいブロックに移動
- 新しいブロックのディレクトリレコードを生成
- 新しいディレクトリレコードをもとの index ブロックを指したのと同じ Level 0 ディレクトリブロックに挿入
  - ディレクトリブロックに空きが無い場合は、そのディレクトリブロックも分割

Duplicate Datavals

同じ dataVal の index レコードは同じブロックに配置される必要がある
- ディレクトリから辿れなくなるため
同じ dataVal が多すぎて 1 つのブロックに収まらない場合はオーバーフローブロックを利用する

Implementing B-Tree

SimpleDB における主要な 4 つのクラス
- BTreeIndex
- BTreeDir
- BTreeLeaf
- BTPage

BTPage

B-Tree page のレコード
- レコードはソートされた順序で管理される必要がある
- レコードは永続的な ID を持つ必要はなく、必要に応じてページ内で移動できる
- ページはそのレコードを他のページと分割できる必要がある
- 各ページはフラグとなる整数が必要である
  - ディレクトリページはフラグを利用してそのレベルを保持
  - リーフページはそのオーバーフローブロックを指し示すためにフラグを使用する
B-Tree page
- ソートされたレコードのリストを保持
- 新しいレコードがページに挿入されると、そのソート順の位置が決定され、それに続くレコードが 1 つ右に移動して場所を確保
- レコードが削除されると、それに続くレコードは左側に移動して穴を埋める

findSlotBefore

public int findSlotBefore(Constant searchKey) {  
    int slot = 0;  
    while (slot < getNumRecs() && getDataVal(slot).compareTo(searchKey) < 0)  
        slot++;  
    return slot - 1;  
}

検索キーを引数に取り、検索キー <= dataVal(x) となるような最小の slot を見つけて、その前の slot を返す

BTreeLeaf

constructor

public BTreeLeaf(Transaction tx, BlockId blk, Layout layout, Constant searchKey) {  
    this.tx = tx;  
    this.layout = layout;  
    this.searchKey = searchKey;  
    contents = new BTPage(tx, blk, layout);  
    currentSlot = contents.findSlotBefore(searchKey);  
    fileName = blk.fileName();  
}

指定されたブロックの BTreePage を作成し findSlotBefore を呼び出す
- 検索キーを含む最初のレコードの直前に自分自身を配置

public boolean next() {  
    currentSlot++;  
    if (currentSlot >= contents.getNumRecs())  
        return tryOverflow();  
    else if (contents.getDataVal(currentSlot).equals(searchKey))  
        return true;  
    else
        return tryOverflow();  
}

次のレコードに移動し、そのレコードが目的の検索キーを持っているかを返す
overflow ブロックがあれば、それも検索する

insert

指定された dataRID を持つ leaf レコードを挿入する
レコードがページにフィットしない場合、ページを split してディレクトリエントリーを返す(フィットする場合は null を返す)
ページが同じ dataVal を保つ場合は overflow block を生成する

public DirEntry insert(RID dataRid) {  
    if (contents.getFlag() >= 0 && contents.getDataVal(0).compareTo(searchKey) > 0) {  
        // overflow ブロックが存在し、searchKey が挿入対象のブロックが持つ最初の dataVal よりも前に配置されるものの場合は split 
        Constant firstVal = contents.getDataVal(0);  
        BlockId newBlk = contents.split(0, contents.getFlag());  
        currentSlot = 0;  
        contents.setFlag(-1);  
        contents.insertLeaf(currentSlot, searchKey, dataRid);  
        return new DirEntry(firstVal, newBlk.number());  
    }  
  
    currentSlot++;  
    contents.insertLeaf(currentSlot, searchKey, dataRid);  
    if (!contents.isFull())  
        return null;  
    // ページが full の場合、split する  
    Constant firstKey = contents.getDataVal(0);  
    Constant lastKey = contents.getDataVal(contents.getNumRecs()-1);  
    if (lastKey.equals(firstKey)) {  
        // overflow ブロックを生成して、2件目以降のレコードを移す  
        BlockId newBlk = contents.split(1, contents.getFlag());  
        contents.setFlag(newBlk.number());  
        return null;    } else {  
        int splitPos = contents.getNumRecs() / 2;  
        Constant splitKey = contents.getDataVal(splitPos);  
        if (splitKey.equals(firstKey)) {  
            // next key を探すために右へ移動  
            while (contents.getDataVal(splitPos).equals(splitKey))  
                splitPos++;  
            splitKey = contents.getDataVal(splitPos);  
        } else {  
            // key を持つ最初の entry を探すために左へ移動  
            while (contents.getDataVal(splitPos-1).equals(splitKey))  
                splitPos--;  
        }  
        BlockId newBlk = contents.split(splitPos, -1);  
        return new DirEntry(splitKey, newBlk.number());  
    }  
}

BTreeDir

ディレクトリブロックを実装

ルートから検索キーに関連する level 0 のディレクトリブロックが見つかるまでツリーを下っていく

public int search(Constant searchKey) {  
    BlockId childBlk = findChildBlock(searchKey);  
    while (contents.getFlag() > 0) {  
        contents.close();  
        contents = new BTPage(tx, childBlk, layout);  
        childBlk = findChildBlock(searchKey);  
    }  
    return childBlk.number();  
}

insert

新しいディレクトリエントリーを挿入
ブロックが level 0 ならエントリーはそこに挿入
そうでない場合は適切な子ノードに挿入
non-null な値を返す場合は子ノードは split され返されたエントリーはそのブロックに挿入されたことを示す

public DirEntry insert(DirEntry e) {  
    if (contents.getFlag() == 0)  
        return insertEntry(e);  
    BlockId childBlk = findChildBlock(e.dataVal());  
    BTreeDir child = new BTreeDir(tx, childBlk, layout);  
    DirEntry myEntry = child.insert(e);  
    child.close();  
    return (myEntry != null) ? insertEntry(myEntry) : null;  
}
private DirEntry insertEntry(DirEntry e) {  
    int newSlot = 1 + contents.findSlotBefore(e.dataVal());  
    contents.insertDir(newSlot, e.dataVal(), e.blockNumber());  
    if (!contents.isFull())  
        return null;  
    // ページが full の場合 split する  
    int level = contents.getFlag();  
    int splitPos = contents.getNumRecs() / 2;  
    Constant splitVal = contents.getDataVal(splitPos);  
    BlockId newBlk = contents.split(splitPos, level);  
    return new DirEntry(splitVal, newBlk.number());  
}

makeNewRoot
- ルートページでの挿入の呼び出しが non-null を返すときに呼び出される
- ルートは常にディレクトリファイルのブロック0にある必要がある
  - このメソッドは新しいブロックを割り当て、ブロック0の内容を新しいブロックにコピーし、ブロック0を新しいルートとして初期化
- 新しいルートは常に 2 つのエントリを持つ
  - 古いルート
  - 新しく分割されたブロック

public void makeNewRoot(DirEntry e) {  
    Constant firstVal = contents.getDataVal(0);  
    int level = contents.getFlag();  
    BlockId newBlk = contents.split(0, level);  
    DirEntry oldRoot = new DirEntry(firstVal, newBlk.number());  
    insertEntry(oldRoot);  
    insertEntry(e);  
    contents.setFlag(level + 1);  
}

B-Tree Index

constructor

与えられたスキーマオブジェクトからリーフレコードのレイアウトを構築
リーフスキーマから対応する情報を抽出することによってディレクトリレコードのスキーマを構築し、レイアウトを構築
必要に応じてルートをフォーマットし、リーフファイルのブロック0を指すエントリを挿入

public BTreeIndex(Transaction tx, String idxName, Layout leafLayout) {  
    this.tx = tx;  
    leafTbl = idxName + "leaf";  
    this.leafLayout = leafLayout;  
    if (tx.size(leafTbl) == 0) {  
        BlockId blk = tx.append(leafTbl);  
        BTPage node = new BTPage(tx, blk, leafLayout);  
        node.format(blk, -1);  
    }  
  
    Schema dirSch = new Schema();  
    dirSch.add("block", leafLayout.schema());  
    dirSch.add("dataVal", leafLayout.schema());  
    String dirTbl = idxName + "dir";  
    dirLayout = new Layout(dirSch);  
    rootBlk = new BlockId(dirTbl, 0);  
    if (tx.size(dirTbl) == 0) {  
        // 新しいルートブロックを生成  
        tx.append(dirTbl);  
        BTPage node = new BTPage(tx, rootBlk, dirLayout);  
        node.format(rootBlk, 0);  
        // 最初のディレクトリエントリーを挿入  
        int fieldType = dirSch.type("dataVal");  
        Constant minVal = (fieldType == INTEGER) ? new Constant(Integer.MIN_VALUE) : new Constant("");  
        node.insertDir(0, minVal, 0);  
        node.close();  
    }  
}

beforeFirst

指定した検索キーに関連する leaf ブロックを探す
探しだした leaf を open して next, getDataRid を実行可能な状態にしておく

public void beforeFirst(Constant searchKey) {  
    close();  
    BTreeDir root = new BTreeDir(tx, rootBlk, dirLayout);  
    int blkNum = root.search(searchKey);  
    root.close();  
    BlockId leafBlk = new BlockId(leafTbl, blkNum);  
    leaf = new BTreeLeaf(tx, leafBlk, leafLayout, searchKey);  
}

insert

適切な leaf ページを探して index レコードを挿入
leaf ページが分割された場合、新しい leaf の index レコードをディレクトリに挿入
ルートに挿入した結果、ルートが分割されたら BTreeDir の makeNewRoot を呼び出す

public void insert(Constant dataVal, RID dataRid) {  
    beforeFirst(dataVal);  
    DirEntry e = leaf.insert(dataRid);  
    leaf.close();  
    if (e == null)  
        return;  
    BTreeDir root = new BTreeDir(tx, rootBlk, dirLayout);  
    DirEntry e2 = root.insert(e);  
    if (e2 != null)  
        root.makeNewRoot(e2);  
    root.close();  
}

delete
- leaf から index レコードを削除
- ディレクトリは変更しない
  - ディレクトリブロックが十分に空いた場合 merge させることができるが、SimpleDB では実装しない
  - DB が小さくなることはほとんどなく、削除の後に別の挿入が続くのが普通

index を使った Select の実装

IndexSelectPlan

select 演算子を実装

constructor

public IndexSelectPlan(Plan p, IndexInfo ii, Constant val) {  
   this.p = p;  
   this.ii = ii;  
   this.val = val;  
}

基礎となる TablePlan, index 情報, 選択定数を受け取る

open

public Scan open() {  
   TableScan ts = (TableScan) p.open();  
   Index idx = ii.open();  
   return new IndexSelectScan(ts, idx, val);  
}

index を open し、IndexSelectScan のコンストラクタに渡す

IndexSelectScan

public boolean next() {  
   boolean ok = idx.next();  
   if (ok) {  
      RID rid = idx.getDataRid();  
      ts.moveToRid(rid);  
   }  
   return ok;  
}

IndexSelectPlan から受け取った index を用いて RID を取得
TableScan を該当の RID まで進める

index を使った Join の実装

Join の実装では内部テーブルを繰り返しスキャンする必要があったが、IndexJoin では代わりに index を繰り返し検索
- 2 つのテーブルの積を取るよりもかなり効率的

IndexJoinScan

constructor

public IndexJoinScan(Scan lhs, Index idx, String joinField, TableScan rhs) {  
    this.lhs = lhs;  
    this.idx = idx;  
    this.joinField = joinField;  
    this.rhs = rhs;  
    beforeFirst();  
}
public void beforeFirst() {  
    lhs.beforeFirst();  
    lhs.next();  
    resetIndex();  
}
private void resetIndex() {  
    Constant searchKey = lhs.getVal(joinField);  
    idx.beforeFirst(searchKey);  
}

constructor 内で beforeFirst を呼び出すと lhs の joinField の値を searchKey として index を検索

public boolean next() {  
    while (true) {  
        if (idx.next()) {  
            rhs.moveToRid(idx.getDataRid());  
            return true;        }  
        if (!lhs.next())  
            return false;  
        resetIndex();  
    }  
}

lhs のレコードがある限り index を繰り返しリセットしつつ rhs のレコードの位置を該当の RID にセット
- index は rhs のテーブルから作成されている前提

Index Update Planning 実装

database が index 作成をサポートする場合、レコードが更新される度に対応する index レコードの変更も必要

executeInsert

テーブルの index 情報を取得し、値をセットしつつ index が存在したら挿入

public int executeInsert(InsertData data, Transaction tx) {  
    String tableName = data.tableName();  
    Plan p = new TablePlan(tx, tableName, mdm);  
  
    // 始めにレコードを挿入
    UpdateScan s = (UpdateScan) p.open();  
    s.insert();  
    RID rid = s.getRid();  
  
    // 値をセットしつつ、index が存在したら挿入
    Map<String, IndexInfo> indexes = mdm.getIndexInfo(tableName, tx);  
    Iterator<Constant> varIter = data.vals().iterator();  
    for (String fieldName : data.fields()) {  
        Constant val = varIter.next();  
        s.setVal(fieldName, val);  
  
        IndexInfo ii = indexes.get(fieldName);  
        if (ii != null) {  
            Index idx = ii.open();  
            idx.insert(val, rid);  
            idx.close();  
        }  
    }  
    s.close();  
    return 1;  
}

executeDelete

レコードを削除する前にレコードのフィールドの値を使って index を削除

public int executeDelete(DeleteData data, Transaction tx) {  
    String tableName = data.tableName();  
    Plan p = new TablePlan(tx, tableName, mdm);  
    p = new SelectPlan(p, data.pred());  
    Map<String, IndexInfo> indexes = mdm.getIndexInfo(tableName, tx);  
  
    UpdateScan s = (UpdateScan) p.open();  
    int count = 0;  
    while (s.next()) {  
        // 始めにすべての index のレコードが存在したら削除
        RID rid = s.getRid();  
        for (String fieldName : indexes.keySet()) {  
            Constant val = s.getVal(fieldName);  
            Index idx = indexes.get(fieldName).open();  
            idx.delete(val, rid);  
            idx.close();  
        }  
        // その後レコード自体を削除
        s.delete();  
        count++;  
    }  
    s.close();  
    return count;  
}

executeModify

レコードを更新しつつ index が存在したら delete & insert する

public int executeModify(ModifyData data, Transaction tx) {  
    String tableName = data.tableName();  
    String fieldName = data.targetField();  
    Plan p = new TablePlan(tx, tableName, mdm);  
    p = new SelectPlan(p, data.pred());  
  
    IndexInfo ii = mdm.getIndexInfo(tableName, tx).get(fieldName);  
    Index idx = (ii == null) ? null : ii.open();  
  
    UpdateScan s = (UpdateScan) p.open();  
    int count = 0;  
    while (s.next()) {  
        // 始めにレコードを更新
        Constant newVal = data.newVal().evaluate(s);  
        Constant oldVal = s.getVal(fieldName);  
        s.setVal(data.targetField(), newVal);  
  
        // index が存在したら delete & insert
        if (idx != null) {  
            RID rid = s.getRid();  
            idx.delete(oldVal, rid);  
            idx.insert(newVal, rid);  
        }  
        count++;  
    }  
    if (idx != null) idx.close();  
    s.close();  
    return count;  
}

hmatui66

Chapter 13: Materialization and Sorting

materialize, sort, groupby, mergejoin について考察
入力レコードを一時テーブルに保存することで実体化
- パイプライン演算子のみを使用した場合もよりはるかに効率の良い問い合わせ実装を実現

Materialization の価値

これまでに見てきた演算子の実装の特徴
- レコードは必要に応じて計算され、保存されない
- 前のレコードにアクセスするには演算全体を最初から再計算
この章では入力を実体化する演算子について考える
- 前処理により、出力レコードを一時テーブルに保存
例: groupby
- 指定されたグループ化フィールドに従って入力レコードをグループ化 & 各グループに対して集計関数を計算
- グループを決定する最も簡単な方法はレコードをグループ化フィールドでソートすること
  - ソートしたレコードは一時テーブルに保存しておく
  - 集計関数の計算はこの一時テーブルを一回通過させることで行う
materialization は両刃の剣
- scan 効率を大幅に向上
- 一時テーブルの書き込みと読み込みでオーバーヘッドが発生
  - クライアントが必要とする出力レコードよりも多くのレコードを一時テーブルに書き込む必要がある
- 上記のコストが scan の効率化で相殺される場合のみ有用

一時テーブル

一時テーブルと通常のテーブルとの違い
- TableManager の createTable では作成されず、metadata も catalog に表示されない
  - SimpleDB では一時テーブルの独自の metadata を管理
- 一時テーブルは不要になった時点で database システムによって自動的に削除
  - SimpleDB ではシステムの初期化時に削除
- RecoveryManager は一時テーブルの変更を記録しない

Materizliation

materialize 演算子
- サブクエリの出力を一時テーブルに保存
- レコードが何度も計算されないようにする

Materialization の例

(a)
- Product では左の部分木の各レコードに対して右の部分木の各レコードを検査
  - 右のサブツリーは何度もアクセスされる
  - その際に Grade='A' が何度も計算される
  - 例
    - STUDENT: 900 人
    - ENROLL テーブル: 50,000 ブロック
    - Product 時のアクセス: $50,000 * 900 = 45,000,000$ ブロック
(b)
- 2 つの materialize ノードがある
- 右の Select ノード
  - Grade='A' の ENROLL レコードを含む一時テーブルを作成
  - 例
    - 一時テーブルは元のテーブルの 1/14 になる場合: 3,572 ブロック
    - 一時テーブル作成時のアクセス: 50,000(読み込み) + 3,572(書き込み) ブロック
    - Product 時のアクセス: $3,572 * 900 = 3,214,800$ ブロック
      - materialization により (a) よりも 80 % 以上削減
- 左の Select ノード
  - 一時テーブル作成時のブロックアクセス + Product 時の一時テーブルのブロックアクセスが発生
  - (a) に比べてコストが増加
  - → materialize はそのノードの出力が繰り返し計算される場合にのみ有用

Materialization のコスト

入力の前処理コストと scan 実行コストに分けることができる
前処理コスト: 対象のテーブルの読み取りコストと一時テーブルへの書き込みコスト
scan コスト: 一時テーブルからレコードを読み出すコスト

Materialize Operator の実装

MaterializePlan のみ実装
- Scan は TempTable の TableScan を使う

open

ソースから読み取りを行いつつ一時テーブルへの書き込みを行う
返り値は一時テーブルに対する Scan

public Scan open() {  
    Schema sch = srcPlan.schema();  
    TempTable temp = new TempTable(tx, sch);  
    Scan src = srcPlan.open();  
    UpdateScan dest = temp.open();  
    while (src.next()) {  
        dest.insert();  
        for (String fieldName: sch.fields()) {  
            dest.setVal(fieldName, src.getVal(fieldName));  
        }  
    }  
    src.close();  
    dest.beforeFirst();  
    return dest;  
}

blocksAccessed

materialized テーブルの推定サイズを返す
ソースのレコード数をブロック辺りのレコード数で割ることで算出
前処理コストは含まれていない
- 一時テーブルの構築は1回で、Scan は複数回されることを想定して無視

public int blockAccessed() {  
    // レコードの長さを計算するためにダミーレイアウトを作成  
    Layout layout = new Layout(srcPlan.schema());  
    double rpb = (double) (tx.blockSize() / layout.slotSize());  
    return (int) Math.ceil(srcPlan.recordsOutput() / rpb);  
}

recordsOutput, distinctValues の値はソースの値と同じものを返す

Sorting

sort 演算子
- 関係代数のもう一つの便利な演算子
- 入力テーブルとフィールドのリストという 2 つの引数を取る
- 出力テーブルは入力テーブルと同じレコードを持つ
  - フィールドのリストに従って sort されたものになる
- groupBy, mergeJoin という演算子を実装するためにも使用される

なぜ Sort は入力レコードを Materialize する必要があるか

Materialize を使用にせずに実装することも可能
- next が呼ばれる度に入力レコードを 2 回反復する必要があるので非効率
  - 次に大きな値を見つける & その値を持つレコードに移動する
Materialize 実装
- open メソッドが入力レコードを前処理
- sort された順序で一時テーブルに保存
- next の呼び出しは、単に一時テーブルから次のレコードを取得
一時テーブルの作成と sort が比較的効率的に実行できるのであれば Materialize 実装は、コストが低くなる

基本的な Mergesort アルゴリズム

insertion sort, quick sort などはすべてのレコードがメモリ内に存在する必要がある
- internal sort アルゴリズムと呼ばれる
DB においてはテーブルがメモリに収まると仮定することはできない
- external sort アルゴリズムを使う必要がある
  - 最も単純かつ一般的なアルゴリズムは mergesort
run(ソート済みの部分列、連)という概念に基づいていいる
- ソートされてないテーブルは複数の run を持つ
- ソートされたテーブルは 1 つの run を持つ
2 つのフェーズ
- split
  - 入力レコードを scan
  - 各 run を一時テーブルに格納
- merge
  - run が一つになるまで merge を繰り返す
初期の run の数を $R$ とした時、 $log_2 R$ 回のマージの反復が必要となる
参考: wikipedia: マージソート

Mergesort アルゴリズムの改善

効率を上げる 3 つの方法
- 一度に merge される run の数を増やす
- 初期の run の数を減らす
- 最終的なソートされたテーブルを write しない
merge される run の数を増やす
- 一度に 3 つ以上の run をマージすることすることができる
- 一度に $k$ 個の scan を開始し、各ステップでそれぞれの scan のレコードの中で最も値が小さいものを出力
  - $log_k R$ の反復回数で完了
  - 最適な $k$ の値の選択は後述
初期の run の数の削減
- 1 回の実行あたりのレコード数を増やす必要がある
- アルゴリズム 1
  - 1 ブロック分の入力レコードを新しい一時テーブルに読み取る
    - メモリ上のバッファページに配置されるのでディスク書き込みは発生しない
  - 内部ソート(クイックソートなど)を用いてこれらのレコードをソートする
  - 1 ブロックの一時テーブルをディスクに保存する
- アルゴリズム 2
  - 1 ブロック分のステージングエリアを入力レコードで埋める
  - 新しい run を開始
  - ステージングエリアが空になるまで繰り返す
    - ステージングエリアのレコードがどれも現在の run に適合しない場合、run を終了し、新しい run を開始
    - 現在の run の最後のレコードより高い最小値を持つステージングエリアからレコードを選択
    - このレコードを現在の run にコピー
    - ステージングエリアからそのレコードを削除
    - 次の入力レコードをステージングエリアに追加
  - 現在の run を終了する
  - (例)
    - 入力レコード: 2 6 20 4 1 16 19 3 18, ブロックは 3 レコードまで保持
    1. 入力レコードをステージングエリアに読み込み
      - Staging: 2 6 20
      - Run1:
    2. ステージングエリアの最小値を選択し run に移動 & 入力レコードを 1 つ読み込み
      - Staging: 6 20 4
      - Run1: 2
    3. ステージングエリアの最小値を選択し run に移動 & 入力レコードを 1 つ読み込み
      - Staging: 6 20 1
      - Run1: 2 4
    4. 最小値は 1 だが現在の run には追加できないので 6 を移動
      - Staging: 20 1 16
      - Run1: 2 4 6
    5. 現在の run へ追加できるものを移動し終える
      - Staging: 1 3 8
      - Run1: 2 4 6 16 19 20
    6. 新しい run を開始して追加を実施
      - Staging:
      - Run1: 2 4 6 16 19 20, Run2: 1 3 18
最終的なソートされたテーブルを write しない
- 1 つの一時テーブルにマージする前段階で前処理を終了
  - 一時テーブルは $k$ 個ある状態
- scan 時に $k$ 個の一時テーブルに対する scan を開き、最小の値を特定しつつ返す

Mergesort のコスト

前処理コストと scan コストに分けることができる
前処理コスト
- 対象のテーブルスキャンのコスト
- レコードを run に分割するコスト
- マージコスト
scan コスト
- 一時テーブルのレコードから最終的なマージを実行するためのコスト
以下を仮定して説明
- 一度に $k$ 個の run をマージ
- $R$ 個の初期 run がある
- materialized な入力レコードは B ブロックを必要とする
- 前処理コスト
  - $2B log_k R - B + inputのコスト$
    - 分割には B ブロックのアクセスに加えて入力のコストが必要
    - レコードのソートは $log_k R$ 回の繰り返し
      - 繰り返しのうち 1 回は scan 段階で実施
    - 各繰り返しの間、各 run のレコードは 1 回読み・書きされる
      - $2B$ のブロックアクセスが必要
    - 最終的なマージは scan 時に行えば良いので $-B$
- scan コスト
  - $B$
    - 各 run のレコードが 1 回ずつ読まれ、 $B$ ブロックのアクセスが必要
例
- 1000 ブロックのテーブルに $1000$ 個の初期 run があるケース
- 一度に $2$ 個の run をマージをすると、 $コスト \risingdotseq 21,000$
  - 前処理コスト
    - 10 回のマージの繰り返しが必要
      - $log_2 1000 \leq 10$ であるため
    - $20,000 = 2 * 1000 * 10$ ブロックアクセスが必要
  - scan のコスト
    - $1000$ ブロックアクセスが必要
- 一度に $10$ 個の run をマージをすると、 $コスト \risingdotseq 7,000$
  - 前処理コスト
    - 3 回のマージの繰り返しが必要
      - $log_{10} 1000 = 3$ であるため
    - $6,000 = 2 * 1000 * 3$ ブロックアクセスが必要
  - scan のコスト
    - $1000$ ブロックアクセスが必要
- 一度に $1000$ 個の run をマージをすると、 $コスト \risingdotseq 3,000$
  - 前処理コスト
    - 1 回のマージの繰り返しが必要
      - $log_{1000} 1000 = 1$ であるため
    - $2,000 = 2 * 1000$ ブロックアクセスが必要
  - scan のコスト
    - $1000$ ブロックアクセスが必要

Mergesort の実装

SortPlan

open

mergesort を実行する
一度に 2 個の run をマージ
初期実行回数は減らさない

public Scan open() {  
    Scan src = p.open();  
    List<TempTable> runs = splintIntoRuns(src);  
    src.close();  
    while (runs.size() > 2)  
        runs = doAMergeIteration(runs);  
    return new SortScan(runs, comp);  
}

splitIntRuns

src を run に分割して、それぞれを一時テーブルに格納

private List<TempTable> splintIntoRuns(Scan src) {  
    List<TempTable> temps = new ArrayList<>();  
    src.beforeFirst();  
    if (!src.next())  
        return temps;  
    TempTable currentTemp = new TempTable(tx, sch);  
    temps.add(currentTemp);  
    UpdateScan currentScan = currentTemp.open();  
    while (copy(src, currentScan))  
        if (comp.compare(src, currentScan) < 0) {  
            // start a new run  
            currentScan.close();  
            currentTemp = new TempTable(tx, sch);  
            temps.add(currentTemp);  
            currentScan = (UpdateScan) currentTemp.open();
        }  
    currentScan.close();  
    return temps;  
}

doMergeIteration

2 つずつ run をマージしていき、sort 結果の一時テーブルを含むリストを返す
- 初期 run が 2 つ以上ある場合、返り値のリストのサイズは 2 になる

private List<TempTable> doAMergeIteration(List<TempTable> runs) {  
    List<TempTable> result = new ArrayList<>();  
    while (runs.size() > 1) {  
        TempTable p1 = runs.remove(0);  
        TempTable p2 = runs.remove(0);  
        result.add(mergeTwoRuns(p1, p2));  
    }  
    if (runs.size() == 1)  
        result.add(runs.get(0));  
    return result;  
}

mergeTwoRuns
- 2 つの run の一時テーブルを open し、比較しつつマージ
recordsOutput, distinctValues
- 入力テーブルと同じ値を返す
blocksAccessed
- Materialized されたテーブルのブロック数を返す
- Mergesort の前処理コストは含まない

RecordComparator
- 上記のコードで comp として記載されているもの
- 各 scan の現在のレコードの値をソート対象のフィールドで比較
SortScan
- constructor
  - 1 つまたは 2 つの run のリストを受け取り、それぞれの scan を open する
- next
  - 2 つの scan の現在のレコードを比較して currentScan を設定する
- get 系メソッド
  - currentScan の値を返す
- savePosition
  - 2 つの scan の現在のレコードの RID を保存
  - 後述の mergejoin で利用
```
public void savePosition() {  
    RID rid1 = s1.getRid();  
    RID rid2 = (s2 == null) ? null : s2.getRid();  
    savedPosition = Arrays.asList(rid1, rid2);  
}
```

Grouping and Aggregation

groupby 演算子
- 入力テーブル、グループ化フィールドの集合、集計式の集合の 3 つ引数を取る
- グループ化フィールドに同じ値を持つレコードを同じグループにまとめる
- 出力テーブルにはグループごとに 1 つの行がある
  - グループ化フィールドと集計式ごとに 1 つの列がある
レコードのグループをどのように作成するか
- 最適な方法は、グループ化フィールドでレコードをソートした一時テーブルを作成
- 各グループのレコードは隣り合うのでソートされたテーブルを一回通過するだけでグループの情報を計算可能
アルゴリズム
- 1. グループ化フィールドでソートされた入力レコードを含む一時テーブルを作成
- 1. テーブルの最初のレコードに移動
- 1. 以下を一時テーブルがなくなるまで繰り返し
  - 現在のレコードのグループ化フィールドの値を "グループ値" とする
  - "グループ値" と同じグループ化フィールドを持つレコードをグループリストに読み込む
  - グループリストのレコードに対して指定された集計式を計算する
コスト
- 前処理コスト
  - ソートのコスト
- scan コスト
  - ソートされた一時テーブルのレコードを 1 回反復するコスト

GroupByPlan

constructor

基礎となる plan とグループ化フィールドのリストと集計式のリストを受け取る
グループ化フィールドと集計式の名称からスキーマを構築

public GroupByPlan(Transaction tx, Plan p, List<String> groupFields, List<AggregateFn> aggFns) {  
    this.p = new SortPlan(tx, p, groupFields);  
    this.groupFields = groupFields;  
    this.aggFns = aggFns;  
    for (String fieldName : groupFields)  
        schema.add(fieldName, p.schema());  
    for (AggregateFn fn: aggFns) {  
        schema.addIntField(fn.fieldName());  
    }  
}

open
- GroupByScan を生成して返す

recordsOutput

グループの数を返す
均等に分布していることを仮定して、グループ化フィールドごとの distinct values の数の積を返す

public int recordsOutput() {  
    int numGroups = 1;  
    for (String fieldName : groupFields)  
        numGroups *= p.distinctValues(fieldName);  
    return numGroups;  
}

GroupByScan

constructor
- 基礎となる scan とグループ化フィールドのリストと集計式のリストを受け取る

異なる "グループ値" が現れるまでレコードを読みつつ集計

public boolean next() {  
    if (!moreGroups) {  
        return false;  
    }  
    for (AggregateFn fn : aggFns) {  
        fn.processFirst(s);  
    }  
    groupVal = new GroupValue(s, groupFields);  
    while (moreGroups = s.next()) {  
        GroupValue gv = new GroupValue(s, groupFields);  
        if (!groupVal.equals(gv)) {  
            break;  
        }  
        for (AggregateFn fn : aggFns)  
            fn.processNext(s);  
    }  
  
    return true;  
}

getVal

指定されたフィールドがグループ化フィールドであればその値を返す
集計式の名称と一致する場合は集計値を返す

public Constant getVal(String fieldName) {  
    if (groupFields.contains(fieldName)) {  
        return groupVal.getVal(fieldName);  
    }  
    for (AggregateFn fn : aggFns) {  
        if (fn.fieldName().equals(fieldName)) {  
            return fn.value();  
        }  
    }  
    throw new RuntimeException("field " + fieldName + " not found.");  
}

AggregateFn

MaxFn

processFirst, processNext
- 前者で初期化、後者で比較しつつ大きければ差し替え

public void processFirst(Scan s) {  
    val = s.getVal(fieldName);  
}  
  
public void processNext(Scan s) {  
    Constant newVal = s.getVal(fieldName);  
    if (newVal.compareTo(val) > 0) {  
        val = newVal;  
    }  
}

CountFn
- processFirst, processNext
  - 前者で counter を 1 にセット、後者でインクリメント

Merge Joins

効率的な join 演算子
アルゴリズム
- 1. それぞれの input テーブルをソート
  - join フィールドを sort フィールドとして用いる
- 1. sort したテーブルを並列に scan し、join フィールドのマッチングを探す
結合の左側にあるテーブルのレコードごとに右側のテーブルのレコードを探す際、sort されていると検索は単純化する
ポイント
- 一致する右側のレコードは、直前の左側のレコードの後に開始しなければならない
- 一致するレコードはテーブル内で隣り合っている
右側のテーブルの scan は一度だけでよい
- 新しい左側のレコードが考慮されるたびに、右側テーブルの中断したところから scan
- 左側の join 値より大きい join 値に達した時点で停止
左側のテーブルに重複する join 値がある場合
- アルゴリズムは対象の join 値にマッチした右側の最初のレコードに戻る必要がある
- 一致するレコードを含む全ての右側ブロックを再読み込みする必要があり、コストが増加
- 幸い、左側の値が重複することはほとんどない
  - (そんなこと無い気がするが...)
Mergejoin のコスト
- 前処理: 2 つのテーブルのソートコスト
- scan: ソートされたテーブルサイズの合計

Mergejoin の実装

MergeJoinPlan

constructor

指定された 2 つの Plan をそれぞれ sort

public MergeJoinPlan(Transaction tx, Plan p1, Plan p2, String fieldName1, String fieldName2) {  
    this.fieldName1 = fieldName1;  
    List<String> sortList1 = Arrays.asList(fieldName1);  
    this.p1 = new SortPlan(tx, p1, sortList1);  
  
    this.fieldName2 = fieldName2;  
    List<String> sortList2 = Arrays.asList(fieldName2);  
    this.p2 = new SortPlan(tx, p2, sortList2);  
  
    sch.addAll(p1.schema());  
    sch.addAll(p2.schema());  
}

recordsOutput

一様分布を仮定して $R(join(p1, p2)) = R(p1)*R(p2)/max{V(p1, F1), V(p2, F2)}$ で算出

public int recordsOutput() {  
    int maxVals = Math.max(p1.distinctValues(fieldName1),  
            p2.distinctValues(fieldName2));  
    return (p1.recordsOutput() * p2.recordsOutput()) / maxVals;  
}

MergeJoinScan

1 つ前の next 呼び出し時に決まった join 値を利用
右側の scan が join 値と一致する間、そちらの next を呼び出して true を返す
右側の scan が join 値と一致しない場合で、左側の scan が join 値と一致する場合、右側の scan の位置を戻して true を返す
- 左側の scan に join 値が重複するケース
- 右側を読み直す必要がある
  - SortScan は読み直しのための位置を記録する機能を実装している前提
どちらの scan も join 値と一致しない場合は左右の scan を進めて、次に一致する値を探す
- 一致する値が見つかったら、右側の位置を記録
  - 左側に join 値が重複するケースに備える
- join 値を上書き

public boolean next() {  
    boolean hasMore2 = s2.next();  
    if (hasMore2 && s2.getVal(fieldName2).equals(joinVal)) {  
        return true;  
    }  
  
    boolean hasMore1 = s1.next();  
    if (hasMore1 && s1.getVal(fieldName1).equals(joinVal)) {  
        s2.restorePosition();  
        return true;    }  
  
    while (hasMore1 && hasMore2) {  
        Constant v1 = s1.getVal(fieldName1);  
        Constant v2 = s2.getVal(fieldName2);  
        if (v1.compareTo(v2) < 0) {  
            hasMore1 = s1.next();  
        } else if (v1.compareTo(v2) > 0) {  
            hasMore2 = s2.next();  
        } else {  
            s2.savePosition();  
            joinVal = s2.getVal(fieldName2);  
            return true;        }  
    }  
    return false;  
}

hmatui66

Chapter 14 Effective Buffer Utilization

演算子の実装が異なると必要なバッファも異なる
- select は単一のバッファを効率的に使用でき、追加のバッファは必要ない
- sort の materialize 実装は一度に複数の run を merge し、それぞれにバッファが必要
演算子の実装が追加のバッファを使用できる方法を検討
sort, product, join の効率的なバッファアルゴリズムを提供

Query プランにおけるバッファの使用

select, project, product の各 scan では対象のテーブルのブロック分のバッファしか固定されない
index 実装においても同様
- static hash index では各バケットを順次 scan して 1 ブロックずつ固定
- B-tree index ではルートから始まり、ディレクトリブロックや子ブロックを順次 scan して 1 ブロックずつ固定
materialize 実装は異なる
- materialize
  - 入力 query に必要なバッファに加えて、一時テーブル用のバッファが 1 つ必要
- sort
  - 1 つまたは 2 つのバッファが必要(staging エリアを使うかどうかによって変わる)
  - merge フェーズでは $k+1$ 個のバッファが必要
- groupby, mergejoin
  - sort に使用するものを除いて、追加のバッファはない
利用可能なバッファの数
- 400 MB をバッファに使用する場合、バッファの数は 10 万個の $4k$ バイトのバッファを持つ
- query プランがこれらを効率的に使うことができれば、数千の同時接続をサポートしても十分なサイズ

Multibuffer Sorting

Mergesort の 2 つの段階を復習
- 最初のフェーズ: レコードを run に split
- 2 番目のフェーズ: テーブルが sort されるまで run を merge
k 個のバッファが利用可能な場合を考える
split フェーズでは
- テーブルの k ブロックを一度に k 個のバッファに読み込み
- それぞれを内部ソートして k ブロックの run を生成
- run を一時テーブルに書き込み
- → k が十分に大きい場合、split フェーズでは k 個以上の初期 run は生成しないので、分割以外には何もしなくても良い
例: テーブルが B ブロックの場合
- split フェーズで $B/k$ 個の初期 run が生成される
  - (一時テーブル書き出し時に merge もする？)
- その後の merge フェーズは $log_k (B/k)$ 回の merge イテレーションが必要となる
  - 基本的な mergesort に比べてイテレーションが 1 回少なくなる
    - 基本的な mergesort $2Blog_k R$
    - $2B$ ブロックのアクセスを節約
- コスト
  - 前処理: $2Blog_k B - 3B$
  - scan: $B$
k の最適値の選び方
- $k = \sqrt{B}$ の場合: merge イテレーションは不要
  - split フェーズでサイズが k の k 個の run を生成するためマージは scan フェーズで実施すればよい
- $k = \sqrt[3]{B}$ の場合: merge イテレーションは 1
  - split フェーズでサイズが k の $k^2$ 個の run を生成
  - 1 イテレーション実行後にサイズが $k^2$ の k 個の run が生成
  - k 個の run は scan フェーズでマージ
- $k = \sqrt[4]{B}$ の場合: merge イテレーションは 2
- 例
  - 4GB のテーブルを sort
  - ブロックは 4KB
    - テーブルは 1000,000 ブロックとなる
  - buffer 数 : iteration 数
    - 1000 : 0
    - 100 : 1
    - 32 : 2
    - 16 : 3
    - 10 : 4
    - ...
    - 2 : 18
- 上記の例で、あるテーブルのサイズ B に対し、multibuffer mergesort では buffer 数が $\sqrt{B}, \sqrt[3]{B}, \sqrt[4]{B}, ...$ の場合に効率的であることが分かる
- buffer 数が 100 の場合は 1 イテレーションだったが、500 の場合は？
  - split フェーズで 500 ブロックの 2000 個の run が生成される
  - 最初のイテレーションでは 500 個の run を 4 個の run にマージ
  - scan フェーズで 4 個の run をマージする必要があるので、buffer 数 100 だった時とイテレーション数が変わっていない
- 結論
  - B ブロックのテーブルを sort するために k 個の buffer を使用する場合、k は B のルートでなければならない

Multibuffer Product

SimpleDB の product(T1, T2) の実装では単一の buffer を使用している
- 場合によっては T2 の各ブロックは T1 のレコード数と同じ回数読み込まれる可能性がある
- T1, T2 がともに 1000 ブロックのテーブルだった場合
  - 1 ブロックに 20 レコードがあると 20,001,000 回のブロックアクセスが必要
仮に T2 のブロックの pin を解除しないと？
- T1 の各ブロックを 1 回、 T2 の各ブロックを 1 回読み取るだけで良いので非常に効率的
T2 が大きすぎる場合は？
- T2 が 1000 ブロックで buffer が 500 個のケースで考える
- T2 を 2 段階で処理
  - 最初の 500 ブロックを buffer に読み込んで T1 との product を計算
  - 次に残りの 500 ブロックを buffer に読み込んで T1 との product を計算
- T1 は 2 回、T2 は 1 回読まれるだけなので 3000 回のブロックアクセスで済む
multibuffer product は上記の考えを一般化
- T1 のブロックを B1, T2 のブロックを B2 とする
- T2 のブロック B2 をチャンクに分ける
  - チャンク内のブロック数 = buffer 数 k となるようにする
  - →チャンク数は B2/k 個となる
- product には $B2 + (B1B2/k)$ のブロックアクセスが必要となる
- 8 章の実装では T1 の scan は 1 回だったが multibuffer product だと複数回になる
例
- T1, T2 がともに 1000 ブロック
- buffer 数 : チャンク数 : ブロックアクセス数
  - 1000 : 1 : 2000
  - 500 : 2 : 4000
  - 334 : 3 : 5000
  - 250 : 4 : 6000
    - T2 を 250 ブロックの 4 つのチャンクに分割
    - $1000 + (1000 * 4)$ を計算すると 6000 となる
  - ...
  - 100 : 10 : 11000
- これらの値はすべて基本的な product 実装が必要とするブロックアクセス数よりもはるかに小さい
- sort と同様に k のすべての値が有用ではない
  - 300 個の buffer が利用可能でも multibuffer product では 250 個しか利用できない

Determining Buffer Allocation

multibuffer アルゴリズムのための buffer 数 k の適切な値は以下の要素で決定される
- 利用可能な buffer の数
- 入力テーブルのサイズ
- 関係演算子
  - sort の場合は入力テーブルのサイズのルート
  - product の場合はテーブルのサイズのファクタ

バッファー数を計算する BufferNeeds の実装

bestRoot

利用可能な buffer 数と入力テーブルのサイズを受け取って取りうる root を返す

public static int bestRoot(int available, int size) {  
   int avail = available - 2; //reserve a couple  
   if (avail <= 1)  
      return 1;  
   int k = Integer.MAX_VALUE;  
   double i = 1.0;  
   while (k > avail) {  
      i++;  
      k = (int)Math.ceil(Math.pow(size, 1/i));  
   }  
   return k;  
}

bestFactor

利用可能な buffer 数と入力テーブルのサイズを受け取って取りうる factor を返す

public static int bestFactor(int available, int size) {  
   int avail = available - 2;  //reserve a couple   
if (avail <= 1)  
      return 1;  
   int k = size;  
   double i = 1.0;  
   while (k > avail) {  
      i++;  
      k = (int)Math.ceil(size / i);  
   }  
   return k;  
}

上記の実装は実際には buffer manager から buffer を予約することはない
- 単に数を返すだけ
- multibuffer アルゴリズムが返された数の buffer を pin しようとしても利用できない可能性がある
  - その場合は wait

Multibuffer Sorting の実装

SimpleDB の配布ソースには実装は含まれていない
以下は実装済の SortPlan の変更方針を記載
splitIntoRuns
- テーブルがまだ作成されていないのでサイズが分からない
- blocksAccessed を用いて推定することはできる
- 以下のようなコードを利用
```
int size = blocksAccessed();
int available = tx.availableBuffs();
int numbuffs = BufferNeeds.bestRoot(available, size);
```
- numbuffs を pin して入力レコードで満たして内部ソートして一時テーブルに書き込めばよい
doAMergeIteration
- 最適な戦略はこのメソッドが run リストから k 個の一時テーブルを削除すること
```
int available = tx.availableBuffs();  
int numbuffs = BufferNeeds.bestRoot(available, runs.size()); List<TempTable> runsToMerge = new ArrayList<>();  
for (int i=0; i<numbuffs; i++)

   runsToMerge.add(runs.remove(0));
```
- runsToMerge リストを mergeTwoRuns (mergeSeveralRuns にリネーム)に渡して 1 つの run にマージすればよい
GroupByPlan, MergeJoinPlan は内部で使用する SortPlan が通常のアルゴリズムと mulitibuffer のアルゴリズムのどちらをつかっているかは見分けられない

ChunkScan

チャンク実装
すべてのブロックが利用可能な buffer に収まる特性を持つ

constructor

チャンクの最初と最後のブロックのブロック番号が与えられる
チャンク内の各ブロックのレコードページを開き、リストに格納

public ChunkScan(Transaction tx, String fileName, Layout layout, int startBNum, int endBNum) {  
    this.tx = tx;  
    this.fileName = fileName;  
    this.layout = layout;  
    this.startBNum = startBNum;  
    this.endBNum = endBNum;  
    for (int i = startBNum; i<= endBNum; i++) {  
        BlockId blk= new BlockId(fileName, i);  
        buffs.add(new RecordPage(tx, blk, layout));  
    }  
    moveToBlock(startBNum);  
}

現在のページにレコードが無い場合、リストの次のページがカレントとなる
TableScan と異なり、ブロック間を移動しても前のページを close しない(unpin しない)

public boolean next() {  
    currentSlot = rp.nextAfter(currentSlot);  
    while (currentSlot < 0) {  
        if (currentBNum == endBNum) {  
            return false;  
        }  
        moveToBlock(rp.block().number()+1);  
        currentSlot = rp.nextAfter(currentSlot);  
    }  
    return true;  
}

MultiBufferProductPlan

open

LHS は MaterializeScan として、RHS は一時テーブルとして実体化する

public Scan open() {  
    Scan leftScan = lhs.open();  
    TempTable tt = copyRecordsFrom(rhs);  
    return new MultiBufferProductScan(tx, leftScan, tt.tableName(), tt.getLayout());  
}

private TempTable copyRecordsFrom(Plan p) {  
    Scan src = p.open();  
    Schema sch = p.schema();  
    TempTable t = new TempTable(tx, sch);  
    UpdateScan dest = (UpdateScan) t.open();  
    while (src.next()) {  
        dest.insert();  
        for (String fieldName : sch.fields()) {  
            dest.setVal(fieldName, src.getVal(fieldName));  
        }  
    }  
    src.close();  
    dest.close();  
    return t;  
}

blocksAccessed

チャンクのサイズを計算するために RHS のテーブルのサイズを知る必要があるため MaterializePlan を用いて推定

public int blockAccessed() {  
    int avail = this.tx.availableBuffs();  
    int size = new MaterializePlan(tx, rhs).blockAccessed();  
    int numChunks = size / avail;  
    return rhs.blockAccessed() +  
            (lhs.blockAccessed() * numChunks);  
}

MultiBufferProductScan

constructor

BufferNeed.bestFactor を呼び出してチャンクサイズを決定
RHS の ChunkScan を open し、LHS との ProductScan を作成

public MultiBufferProductScan(Transaction tx, Scan lhsScan, String tblName, Layout layout) {  
    this.tx = tx;  
    this.lhsScan = lhsScan;  
    this.fileName = tblName + ".tbl";  
    this.layout = layout;  
    fileSize = tx.size(fileName);  
    int available = tx.availableBuffs();  
    chunkSize = BufferNeeds.bestFactor(available, fileSize);  
    beforeFirst();  
}

ProductScan にレコードが無い場合、新しい ProductScan を作成しする

public boolean next() {  
    while (!prodScan.next()) {  
        if (!useNextScan()) {  
            return false;  
        }  
    }  
    return true;  
}
private boolean useNextScan() {  
    if (nextBlkNum >= fileSize) {  
        return false;  
    }  
    if (rhsScan != null) {  
        rhsScan.close();  
    }  
    int end = nextBlkNum + chunkSize - 1;  
    if (end >= fileSize) {  
        end = fileSize - 1;  
    }  
    rhsScan = new ChunkScan(tx, fileName, layout, nextBlkNum, end);  
    lhsScan.beforeFirst();  
    prodScan = new ProductScan(lhsScan, rhsScan);  
    nextBlkNum = end + 1;  
    return true;
}

Hash Joins

mergejoin アルゴリズムは両方の入力テーブルを sort
- コストは大きい方の入力テーブルのサイズで決まる
hashjoin アルゴリズムではコストは小さい方の入力テーブルのサイズで決まる
入力テーブルのサイズが非常に異なる場合、mergejoin よりも好ましい

Hashjoin アルゴリズム

T2 のサイズに基づいて再帰的に実行
- T2のサイズが利用可能な buffer に収まる場合は multibuffer product を使って T1, T2 を結合
- T2 のサイズが大きい場合は T2 のサイズを小さくするために hash を使用

アルゴリズム
- 利用可能な buffer 数以下の値 k を選択
- T2 が k ブロックに収まる場合
  - multibuffer product を使用して T1, T2 を結合して返す
- 0 から k-1 の間の値を返す hash 関数を選択する
- T1 の各レコードを join field で hash 化し、hash 値に関連する一時テーブルにレコードをコピーする
  - T1 を hash 値で分類した一時テーブルの集合ができる
- T2 も同様に hash 化する
  - T2 を hash 値で分類した一時テーブルの集合ができる
- 0 から k-1 の間の値 i に対して
  - T1 の i 番目の一時テーブルと、T2 の i 番目の一時テーブルに対して hashjoin を再帰的に実行

コスト分析

前提
- テーブル T1 のブロック数を B1、テーブル T2 のブロック数を B2 とする
- $B2 = k^n$ のような k を選ぶ
- レコードが均等に hash 化されると仮定
コストを計算するための整理
- 最初の hash ラウンドでは k 個の一時テーブルが作成される
  - それぞれの一時テーブルは $k^{n-1}$ のブロック数
- 上記を再帰的に hash 化すると $k^2$ 個の一時テーブルが残る
  - それぞれの一時テーブルは $k^{n-2}$ のブロック数
- 最終的に T2 は k ブロックをもつ $k^{n-1}$ 個の一時テーブルを持つことになる
  - これらは multibuffer product を用いて T1 の対応するテーブルと結合
コスト内訳
- 最初のラウンドのコストは B1 + B2 + 入力の読み込みコスト
- その後のラウンドでも 2(B1 + B2) のコストが必要
  - 各一時テーブルの各ブロックが 1 回ずつ読み込みされ書き込まれる
- scan 時の multibuffer product によって B1 + B2 のコストが必要
コスト
- 前処理: $(2B_1log_k B_2 - 3B_1) + (2B_2log_k B_1 - 3B_2) + 入力コスト$
  - 1 つ目の対数の引数は $B_2$ であることに注意！
- scan: $B_1 + B_2$
上記は multibuffer mergejoin のコストとほぼ同じ
- 違いは mergejoin の場合は 1 つ目の対数の引数が $B_1$ となる
- hashjoin では hash ラウンド数が T2 によってのみ決まる
- mergejoin は T1, T2 それぞれを sort するため
T1, T2 のサイズが近い場合は mergejoin を使用したほうが良い
- hashjoin はレコードを均等に hash するという仮定に依存しているため
  - 均等にならない場合、より多くのラウンドが必要になる可能性がある
メモ
- 分割は T2 だけ実施して、その過程で使用した hash 方式を記録しておけば T1 を分割する必要はないのでは？
  - join 時に T2 のレコードにランダムアクセスすることになるのでダメ

Join アルゴリズムの比較

mergejoin, hashjoin, indexjoin を比較

比較1

検討対象
- クエリ: select SName, Grade from STUDENT, ENROLL where SId=StudentId
- STUDENT
  - 4500 ブロック
- ENROLL
  - 50000 ブロック
  - StudentId に対する index を持っている
- 利用可能な buffer: 200
mergejoin
- ENROLL の sort
  - 平方根は 224 なので buffer 数よりも大きい & 立方根は 37 を使う
  - イテレーションは 2 回でそれぞれ読み込みと書き込みが発生
    - 200,000 ブロックアクセスが必要
- STUDENT の sort
  - 平方根は 68 なので buffer 数に収まる
  - イテレーションは 1 回
    - 9,000 ブロックアクセスが必要
- merge
  - 読み込みのために 54,500 ブロックのアクセスが必要
- 合計 263,500 ブロックアクセス
hashjoin
- 最小のテーブルが右側にある場合に効率的なので STUDENT を右側のテーブルとする
- STUDENT の hash
  - 68 個の buffer を使用して 68 個のバケットに hash
    - それぞれのバケットは 68 個のブロックを持つ
  - 上記の処理はブロックの読み込みと書き込みが発生
    - 9,000 ブロックアクセスが必要
- ENROLL の hash
  - 68 個の buffer を使用して 68 個のバケットに hash
    - それぞれのバケットは 736 個のブロックを持つ
  - 上記の処理はブロックの読み込みと書き込みが発生
    - 100,000 ブロックアクセスが必要
- バケットを multibuffer product で結合
  - 各バケットは 1 回ずつ読み込まれる
  - 54,500 ブロックアクセスが必要
- 合計 163,500 ブロックアクセス
indexjoin
- STUDENT テーブルの各レコードに対してそのレコードの SID を使って ENROLL インデックスを検索し一致する ENROLL レコードを探す
- STUDENT の scan は 1 回
  - 4,500 ブロックアクセスが必要
- ENROLL の scan は最大 1,500,000 (STUDENT レコード数)
- 合計 1504,500 ブロックアクセス
  - インデックス検査時のブロックアクセスは省略
join アルゴリズムの比較
- hashjoin が効率的な理由
  - 利用可能な buffer の数に比べて小さい方のテーブルが適度に小さく、もう一方が遥かに大きいため
- mergejoin はもっと buffer 数が多ければ hashjoin と同等になる
  - 1000 個の buffer が利用可能場合、イテレーションなしで ENROLL を sort ができる
- indexjoin は圧倒的に効率が悪いのは、ENROLL の全レコードが処理対象だから

比較2

クエリを変更して STUDENT レコードが絞り込まれる場合で再検討
- select SName, Grade from STUDENT, ENROLL where SId=StudentId and GradYear=2020
- STUDENT レコードは 90 ブロックに収まるまで絞られるとする
mergejoin
- STUDENT を 90 個の buffer に読み込んで内部 sort ができる
  - 必要なブロックアクセスは 4,500
- ENROLL を処理するコストは変わらない
  - 200,000 ブロックアクセスが必要
- 合計 204,500 ブロックアクセス
  - わずかに改善
hashjoin
- STUDENT テーブルは 90 個の buffer に収まるのでバケット分割は不要
  - 必要なブロックアクセスは 4,500
- ENROLL テーブルも分割不要で 1 回読めば良い
  - 必要なブロックアクセスは 50,000
- 合計 54,500 ブロックアクセス
indexjoin
- STUDENT テーブルは 1 回読む
  - 必要なブロックアクセスは 4,500
- ENROLL テーブルは絞られた STUDENT レコードに一致する分アクセスされる
  - 900 人の STUDENT に対応する ENROLL レコードが 50,000 件とする
  - 必要なブロックアクセスは 50,000
- 合計 54,500 ブロックアクセス
  - インデックス検査時のブロックアクセスは省略
join アルゴリズムの比較
- hashjoin, indexjoin は同等、mergejoin は劣っている
- 片方のテーブルがかなり小さい場合に mergejoin は不利

比較3

クエリを変更して STUDENT レコードが 1 件に絞り込まれる場合で再検討
- select SName, Grade from STUDENT, ENROLL where SId=StudentId and SId=3
indexjoin
- STUDENT テーブルは 1 回読む
  - 必要なブロックアクセスは 4,500
- ENROLL テーブルは絞られた STUDENT レコードに一致する分アクセスされる
  - 1 人の STUDENT に対応する ENROLL レコードが 34 件とする
  - 必要なブロックアクセスは 34
- 合計 4,534 ブロックアクセス
  - インデックス検査時のブロックアクセスは省略
hashjoin, mergejoin は比較2 の場合と変わらない

分析結果

mergejoin は両方の入力テーブルが比較的同じサイズの時に最も効率的
hashjoin は入力テーブルのサイズが異なる場合に有効
indexjoin は出力レコードの数が少ない場合に有効

hmatui66

Chapter 15 Query Optimization

効率的な計画を生成するとナイーブな計画に比べて数桁速くなることもある

関係代数 query の等価性

関係代数の query は木として表現される
等価性はその木の間の変換と考えることができる
以下、変換を考察

Products の並び替え

product 操作はどのような順序でも実行可能
- product 演算は可換性を持つ
  - $product(T1, T2) = product(T2, T1)$
- product 演算は結合性を持つ
  - $product(product(T1, T2), T3) = product(T1, product(T2, T3))$

Splitting Selections

select は predicate の接続語で分割できる
- $select(T, p1, p2) = select(select(T, p1), p2)$
select ノードを分割するとクエリツリー内の最適な位置に独立して配置可能
クエリオプティマイザはできるだけ多くの接続語に分割
- 各 predicate を CNF (Conjunctive Normal Form: 連言標準形)に変換することで実現
  - AND 演算子を含まない部分述語の組み合わせであれば CFN になる
  - AND 演算子は常に一番外側に置く
- select SName from STUDENT where (MajorId=10 and SId=3) or (GradYear=2018)
  - AND が OR の中にあるので CNF ではない
- select SName from STUDENT where (MajorId=10 or GradYear=2018) and (SId=3 or GradYear=2018)
  - このように変換すると CNF となる
参考
- wikipedia: 連言標準形

ツリー内での Selections の移動

クエリツリーにおいて select ノードを移動させることができる
- predicate は select 対象のサブツリーのフィールドのみに言及している前提で
- 例
  - $select(product(T1, T2), p) = product(select(T1, p), T2)$

Join 演算子の特定

select-product ノードのペアを単一の join に変換可能
$join(T1, T2, p) = select(product(T1, T2), p)$

Projection の追加

project ノードは祖先ノードに project 対象のフィールドが含まれている限り、ツリー内で移動できる
materialize を行う際に入力サイズを小さくするために使用できる

クエリ最適化の必要性

プランナーがクエリに対する計画作成ステップ
- クエリに対応する関係代数クエリツリーを選択
- クエリツリーの各ノードに対する実装を選択
SQL クエリは多くの等価なクエリツリーに変換可能
最適な計画を選択したいが、そのためには多くの作業を伴う可能性があるが労力に見合うのか？
- 同じ結果を返す計画であっても、ブロックアクセス数が極端に異なる可能性がある
- 例としては以下のようなケースがある
  - 対象テーブルをすべて product した後に select で絞り込み
    - 56兆回のアクセス
      - 1 ブロックアクセス 1ms とすると 1780 年かかる
  - select や join による絞り込みを先に実施
    - 139,500 回のアクセス
      - 1 ブロックアクセス 1ms とすると 2.3 分かかる
    - 更に工夫すると 7134 回のアクセス
      - 7 秒

クエリオプティマイザの構造

すべての計画を網羅的に列挙するのは大変
- n 個の積演算がある場合、配置方法は $(2n)!/n!$ 通りある
  - n 個のノードの木構造の作り方は $\frac{(2n)}{(n+1)!n!}$
    - https://www.geeksforgeeks.org/program-nth-catalan-number/
- 他の演算子を配置したり、各演算ノードに実装を割り当てる必要もある
最適化は 2 つの独立したステージで実施
- ステージ1: 問い合わせに対して最も有望なクエリツリーを見つける
  - この時点では実際のコスト情報は考慮しない
  - コスト情報はステージ2のプランに関連付く
- ステージ2: ツリー内の各ノードに対して最適なプランを選択する
考慮するツリーとプランのセットを制限するためにヒューリスティックを使用できる
- 例: select は可能な限り早期に実行する
  - データ数が削減されるため

最も有望なクエリツリーの発見

ツリーのコスト

最適化の最初の段階は、プランナが最も低コストな計画を持つと考えるツリーを見つけること
- プランナは最良のツリーを決定することはできないのがポイント
- ブロックアクセスを計算することなくツリーを比較する必要がある
  - コスト情報はこの段階では利用できないため
  - ブロックアクセスはプランに関連付けられる
洞察
- クエリにおけるブロックアクセスはほぼ product, join 操作によるもの
- 上記の演算が必要とするブロックアクセスは入力サイズに関係
プランナはクエリツリーのコストを ツリーにある各 product, join ノードへの入力サイズの合計 と定義
- 実際の実行時間の "quick and dirty" な近似値となる
- ブロックアクセスの見積もりには役立たないが、ツリー間の相対見積もりに役立つ
- 経験上、だいたい正しい

Select ノードをツリーの下に押し出す

プランナは有望なクエリツリーを探索するためにヒューリスティクスを使用
select ノードは述語が許す限りはツリー内のどこにでも配置できる
product, join の内部に配置すれば入力サイズが減り、コストが削減される
ヒューリスティック1: プランナは select が可能な限り押し下げられたクエリツリーだけを考慮

JoinによるSelect-Productノードの置き換え

ヒューリスティック2: プランナはクエリツリー内の各 select-product ノードを 1 つの join ノードに置き換える
上記はクエリツリーのコストを変えるものではないが、最適なプランを見つけるために重要なステップ

Left-Deep なクエリツリーを使用

left-deep
- 各 product, join ノードの右側に他の product, join ノードがない状態
right-deep
- 各 product, join ノードの左側に他の product, join ノードがない状態
bushy
- left-deep, right-deep でないもの
ヒューリスティック3: プランナは left-deep なクエリツリーだけを考慮
↑の理由は明白ではない
- コストでは bushy なものが低い場合もある
- 1 つ目の理由: left-deep なツリーはコストが最も低くなくても、最も効率的なプランを立てる傾向がある
  - join アルゴリズムは右側が stored テーブルである場合にうまく機能
    - multi-buffer product では右側のテーブルが materialized なものである必要がある
- 2つ目の理由: 利便性
  - クエリに n 個の product/join ノードがある場合、left-deep ツリーだけであれば $n!$ 通りに絞れる

ヒューリスティックに Join 順を選択

最適な join 順を見つける作業は最も重要なプロセス
- 結果として得られるクエリツリーのコストに劇的に影響
- 選択可能な join 順は非常に多く全てを検証することは不可能なためスマートである必要がある
2 つのアプローチ
- 1: ヒューリスティクスを使用
- 2: すべての join 順を考慮
この節ではヒューリスティクスを検討
ヒューリスティック4: join 順の各テーブルは、可能な限り前に選んだテーブルと結合すべき
- product は述語がないため出力レコードがフィルタリングされない
- join の述語に出会うまで無意味なレコードが伝搬されることになる
次はどのテーブルを最初に選ぶかを考える
- DB 業界では多くのヒューリスティクスが提案されているが、どれが最も適切かについてのコンセンサスはほとんどない
- 以下、2 つを取り上げる
ヒューリスティック5a: 最小の出力をするテーブルを選択
- 最も直感的
ヒューリスティック5b: 最も限定的な select の述語を持つテーブルを選ぶ
- クエリツリーの下位にある select の述語はコストに最も大きな影響を与える
5a は直感的だが 5b によるものよりもコストが高くなる傾向がある

網羅的な列挙による Join 順の選択

確実に最適な join 順を見つけたい場合の戦略
n 個の join 順は $n!$ 通りあるが、動的計画法で $O(2^n)$ ^[1]まで短縮できる
- n が 20 以下など適度に小さい場合は実用的
lowest という配列変数を使用
- S をテーブルのセットとする
- lowest[S] には 3 つの値を含む
  - S のテーブルを含む最もコストの低い結合順
  - その結合順に対応するクエリツリーのコスト
  - そのクエリツリーが出力するレコードの数
アルゴリズム
- まず 2 個のテーブルの集合ごとに lowest[S] を計算
- 次に 3 個のテーブルの集合ごとに計算
- テーブルの数を増やしていってクエリ内の全テーブルの集合に到達するまで続ける
例
- 2 個のテーブルの lowest[S] の計算
  - {T1, T2} の集合を考える
  - どちらのテーブルが先であってもコストは同じ
  - 最初のテーブルはヒューリスティック 5a または 5b で決定
- 3 個のテーブルの lowest[S] の計算
  - {T1, T2, T3} の集合を考える
  - 最もコストが低い join 順は以下を考慮することで計算できる
    - lowest [{T2, T3}] joined with T1
    - lowest [{T1, T3}] joined with T2
    - lowest [{T1, T2}] joined with T3
  - 結果は lowest[{T1, T2, T3}] として保存
- n 個のテーブルの lowest[S] の計算
  - {T1, T2, ..., Tn} の集合を考える
  - 最もコストが低い join 順は以下を考慮することで計算できる
    - lowest [{T2, T3, ..., Tn}] joined with T1
    - lowest [{T1, T3, ..., Tn}] joined with T2
    - ...
    - lowest [{T2, T3, ..., Tn-1}] joined with Tn
  - 結果は与えられたクエリに最適な join 順となる

最も効率的なプランの発見

クエリ最適化の第2段階はクエリツリーを効率的なプランに変換
プランナは leaf から順にボトムアップでプランを選択していく
- あるノードを考慮する時、そのサブツリーのブロックアクセス数がわかっている状態になる
プランナは各ノードの実装を他のノードとは無関係に選択
- サブツリーがどのように実装されているかを気にせず、実装のコストだけを知れればよい
- ノード間の相互作用がないので、プラン生成の複雑度が低減される
プラン生成を高速化するためのヒューリスティックもある
- ヒューリスティック6: 可能であれば select ノードの実装として IndexSelect を使用
- ヒューリスティック7: 以下の優先順位に従って join ノードを実装する
  - 可能であれば IndexJoin を使用
  - 入力テーブルの 1 つが小さい場合 HashJoin を使用
  - それ以外の場合は MergeJoin を使用
- ヒューリスティック8: プランナは各 materialized ノードの子として project ノードを追加して不要なフィールドを削除
  - 一時テーブルを可能な限り小さくすることで、create/scan 時のブロックアクセスを削減
  - プランナは materialized ノードとその祖先が必要とするフィールドを決定し、それ以外を削除する project ノードを挿入

最適化の2つのステージの組み合わせ

クエリツリーの構築ステージと、クエリツリーからのプラン構築ステージは、実際にはしばしば組み合わされる
利点
- 利便性: 直接計画を作成できる
- 正確さ: 実際のブロックアクセスを元にツリーのコストを計算できる
複合最適化の 2 つの例
- ヒューリスティックベース
  - SimpleDB ではこちらを実装
- 列挙ベース("Selinger-style" など)

ヒューリスティックベースの SimpleDB Optimizer

HeuristicQueryPlanner

join 順を決定するためにヒューリスティック 5a を使用
最初のテーブルを決める(H1: 最も小さいものを選択)
join 順を決める(H2: 最も小さい出力となるものを選択)

public Plan createPlan(QueryData data, Transaction tx) {  
    // Step 1: それぞれのテーブルの TablePlanner を生成  
    for (String tblName : data.tables()) {  
        TablePlanner tp = new TablePlanner(tblName, data.pred(), tx, mdm);  
        tablePlanners.add(tp);  
    }  
  
    // Step 2: lowest-size プランを選択  
    Plan currentPlan = getLowestSelectPlan();  
  
    // Step 3: join order に繰り返しプランを追加  
    while (!tablePlanners.isEmpty()) {  
        Plan p = getLowestJoinPlan(currentPlan);  
        if (p != null) {  
            currentPlan = p;  
        } else {  
            currentPlan = getLowestProductPlan(currentPlan);  
        }  
    }  
  
    // Step 4: Project on the field names and return  
    return new ProjectPlan(currentPlan, data.fields());  
}

TablePlanner
- 1 つのテーブルに対する計画を作成
- constructor
  - 指定されたテーブルの TablePlan を作成、index に関する情報を取得、predicate を保存
- makeSelectPlan
  - そのテーブルの SelectPlan を作成
  - index が使用可能な場合は IndexSelect を作成
  - 最後に addSelectPred を呼び出してテーブルに適用される predicate を決定し、SelectPlan を作成
    - IndexSelect は index が使われるだけなので predicate は改めて適用する必要がある
```
public Plan makeSelectPlan() {  
    Plan p = makeIndexSelect();  
    if (p == null) {  
        p = myPlan;  
    }  
    return addSelectPred(p);  
}
```
- makeProductPlan
  - MultiBufferProductPlan を生成
- makeJoinPlan
  - IndexJoin が生成できればそれを返す
  - そうでなければ ProductJoin を返す

Selinger-Style 最適化

Pat Selinger さんが主導して考案
動的計画法とプラン生成を組み合わせたもの
lowest[S] に結合順を保存するのではなく、最もコストの低いプランを保存
アルゴリズム
- テーブルの各ペアについて最低コストのプランを計算
- 上記のプランを使用して 3 つのテーブルの各組の最低コストのプランを計算
- 全体の最低コストのプランが計算されるまで繰り返す
コスト計算時にブロックアクセスを考慮するのがポイント
- 出力レコードが最も少ないプランではない
- なぜブロックアクセスが使えるのか？
  - ヒューリスティックな最適化と異なり、部分的な結合順序を捨てないため
- より詳細なコスト分析ができる
  - 例えばソートのコストを考慮することができる
  - ソート済みであれば hashjoin よりも mergejoin が低コスト、といったケースにも対応できる

Merging Query Blocks

view に言及するクエリの最適化について検討
基本的なクエリプランナは、view の定義とクエリを別々に計画してから結合する
- view の定義、クエリそれぞれに関するプランをクエリブロックと呼ぶ
- 個別に最適化すると、必ずしも良いものとはならない
クエリブロックをマージして1つのクエリとして計画することで、効率の良い計画になる可能性がある
- view が複雑な場合マージが不可能になることもある

脚注

2023/04/01 指摘を受けて $O(2n)$ → $O(2^n)$ と修正 ↩︎

hmatui66

Chapter 11 JDBC Interfaces

組み込みインターフェースの作成は比較的簡単
サーバーベースのインターフェースを書くにはサーバーを実行し、JDBC 要求を処理するための追加コードが必要
- Java RMI を使う方法説明

Emmbedded JDBC

JDBC Driver のインターフェースを実装
- 合わせて java.sql 系のインターフェースも実装
  - Connection
  - Statement
  - MetaData,
  - ResultSet
- 上記は基本空実装で、SimpleDB で対応している箇所だけ追加実装

SimpleIJ の実装

Derby の ij というクライアントツールの簡易版

public class SimpleIJ {  
    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  
        System.out.println("Connect> ");  
        String s = sc.nextLine();  
        Driver d = new EmbeddedDriver();  
  
        try (Connection conn = d.connect(s, null); Statement stmt = conn.createStatement()) {  
            System.out.print("\nSQL> ");  
            while (sc.hasNextLine()) {  
                // process one line of input  
                String cmd = sc.nextLine().trim();  
                if (cmd.startsWith("exit"))  
                    break;  
                else if (cmd.startsWith("select"))  
                    doQuery(stmt, cmd);  
                else                    doUpdate(stmt, cmd);  
                System.out.print("\nSQL> ");  
            }  
        } catch (SQLException e) {  
            e.printStackTrace();  
        }  
        sc.close();  
    }  
  
    private static void doQuery(Statement stmt, String cmd) {  
        try (ResultSet rs = stmt.executeQuery(cmd)) {  
            ResultSetMetaData md = rs.getMetaData();  
            int numcols = md.getColumnCount();  
            int totalwidth = 0;  
  
            // print header  
            for (int i = 1; i <= numcols; i++) {  
                String fldname = md.getColumnName(i);  
                int width = md.getColumnDisplaySize(i);  
                totalwidth += width;  
                String fmt = "%" + width + "s";  
                System.out.format(fmt, fldname);  
            }  
            System.out.println();  
            for (int i = 0; i < totalwidth; i++)  
                System.out.print("-");  
            System.out.println();  
  
            // print records  
            while (rs.next()) {  
                for (int i = 1; i <= numcols; i++) {  
                    String fldname = md.getColumnName(i);  
                    int fldtype = md.getColumnType(i);  
                    String fmt = "%" + md.getColumnDisplaySize(i);  
                    if (fldtype == Types.INTEGER) {  
                        int ival = rs.getInt(fldname);  
                        System.out.format(fmt + "d", ival);  
                    } else {  
                        String sval = rs.getString(fldname);  
                        System.out.format(fmt + "s", sval);  
                    }  
                }  
                System.out.println();  
            }  
        } catch (SQLException e) {  
            System.out.println("SQL Exception: " + e.getMessage());  
        }  
    }  
  
    private static void doUpdate(Statement stmt, String cmd) {  
        try {  
            int howmany = stmt.executeUpdate(cmd);  
            System.out.println(howmany + " records processed");  
        } catch (SQLException e) {  
            System.out.println("SQL Exception: " + e.getMessage());  
        }  
    }
}

使用感

Connect> 
foodb
new transaction: 1
creating new database
transaction 1 committed
new transaction: 2

SQL> create table T1(A int, B varchar(9));
transaction 2 committed
new transaction: 3
0 records processed

SQL> insert into T1(A, B) values(1, 'b');
transaction 3 committed
new transaction: 4
1 records processed

SQL> select A, B from T1;
      a         b
-----------------
      1         b
transaction 4 committed
new transaction: 5

Remote Method Invocation

SimpleDB は Java RMI を使って DB サーバーを実装
クライアント、サーバーがそれぞれ異なるスレッドで動作することを意識する必要がある
- (実装予定の)RemoteDriver オブジェクトはクライアントから呼び出されるまで休止

Remote Interface の実装

RemoteDriverImpl
- SimpleDB サーバーへのエントリポイント
- DB サーバーによって生成され RMI レジストリで公開される
- 接続メソッドが呼ばれるたびに、RemoteConnectionImpl を生成し、新しいスレッドで実行
- RMI は透過的に RemoteConnection スタブオブジェクトを生成をクライントに返す
- 上記のタスクは UnicastRemoteObject が実施(実装には表れない)
合わせて以下も実装
- RemoteConnection
- RemoteStatement
  - executeUpdate を実装するたびにトランザクションは commit する実装
- RemoteMetaData
- RemoteResultSet
上記は java.sql の対応インターフェースは実装しておらず、あくまで RMI に対応するためのもの
- それぞれの実装クラスは UnicastRemoteObject を継承

例: RemoteConnectionImpl

public class RemoteConnectionImpl extends UnicastRemoteObject implements RemoteConnection {  
    private SimpleDB db;  
    private Transaction currentTx;  
    private Planner planner;  
    public RemoteConnectionImpl(SimpleDB db) throws RemoteException {  
        this.db = db;  
        currentTx = db.newTx();  
        planner = db.planner();  
    }
    // 省略
}

java.sql.Connection は実装していない
- RemoteConnection は自分で定義したインターフェース

JDBC Interface の実装

RMI のリモートクラスの実装は java.sql の JDBC インターフェースを満たせていない
- SQLException を投げることや、java.sql の Driver, Connection インターフェースを実装する必要がある
Remote*** に対する JDBC インターフェースを満たすラッパークラスを実装
- NetworkConnection
- NetworkStatement
- NetworkMetaData
- NetworkResultSet

例: NetworkConnection

public class NetworkConnection extends ConnectionAdapter {  
    private RemoteConnection rConn;  
    public NetworkConnection(RemoteConnection rConn) {  
        this.rConn = rConn;  
    }  
  
    @Override  
    public Statement createStatement() throws SQLException {  
        try {  
            RemoteStatement rStmt = rConn.createStatement();  
            return new NetworkStatement(rStmt);  
        } catch (Exception e) {  
            throw new SQLException(e);  
        }  
    }
    // 省略
}

ConnectionAdaptor は java.sql.Connection を実装した抽象クラス
- 実装はほぼ空でインターフェースを満たすためだけに配置

NetworkDriver の実装

SimpleIJ で利用するドライバー
RMI の registry を用いて RemoteDriver を取得して java.sql.Connection を実装した NetworkConnection を生成して返す

public class NetworkDriver extends DriverAdapter {  
    public Connection connect(String url, Properties prop) throws SQLException {  
        try {  
            String host = url.replace("jdbc:simpledb://", "");  
            Registry reg = LocateRegistry.getRegistry(host, 1099);  
            RemoteDriver rDrv = (RemoteDriver) reg.lookup("simpledb");  
            RemoteConnection rConn = rDrv.connect();  
            return new NetworkConnection(rConn);  
        } catch (Exception e) {  
            throw new SQLException(e);  
        }  
    }  
}

使用感
- サーバー起動
- クライアント起動

ryo_grid

"網羅的な列挙によるJoin順の選択" というセクションのところのオーダーの記述ですが O(2n) は O(2^n) の誤りではないでしょうか？

hmatui66

書籍確認したところ、ご指摘の通り正しくは O(2^n) でした。
ありがとうございます！

→修正して注釈をつけました

このスクラップは2023/09/02にクローズされました