1. イントロダクション#
ストレージ方法：
- ページはどのようにディスク上に保存されるか
高速な操作：
- DBMS では、データを操作する前に、すべてのデータをディスクからメモリに移動する必要があります。
2. ロックとラッチ#
3. バッファプール#
メモリには固定サイズのページが格納されます。
各レコードは「フレーム」と呼ばれます。
ページが必要な場合、フレームをすぐにコピーします。
Dirty ページはすぐに書き戻されません。（Write-Back キャッシュ）
バッファプールメタデータ#
ページテーブルはメモリ内のどのページが追跡されているかを追跡するために使用されます。
通常、ページテーブルには他の情報も保存されます。
- Dirty フラグ
- Pin / 参照カウンタ
Dirty フラグは、ページが書き込まれたかどうかを示すために使用されます。
Pin / 参照カウンタは、ページがディスクに戻されないようにフレームを固定するために使用されます。
ページディレクトリは、ページ ID をページの場所にマッピングするマッピングです。すべての情報はディスクに保存する必要があり、DBMS がそれを見つけることができます。
ページテーブルは、ページ ID をバッファプール内のフレームにマッピングするマッピングです。これはディスク上に保存する必要のないインメモリのデータ構造です。
メモリ割り当てポリシー#
グローバルポリシー
- すべての操作に責任を持ち、グローバルな最適化を確保します。
ローカルポリシー
- 現在のクエリの効率のみを考慮し、グローバルな影響を考慮しません。
4. バッファプールの最適化#
複数のバッファプール#
通常、DBMS には 1 つのバッファプールだけではありません。
DBMS は、さまざまな目的（たとえば、データベースごとのバッファプール、ページタイプごとのバッファプール）のために複数のバッファプールを維持します。そして、各バッファプールは、その中に格納されている数に対してカスタムのローカルポリシーを持つことができます。
異なるバッファプールにアクセスするための 2 つの主要な方法があります。
- オブジェクト ID
オブジェクト ID を使用して異なるバッファプールを識別します。
！オブジェクト ID - ハッシング
ページ ID のハッシュを使用して異なるバッファプールを識別します。
！ハッシュ
プリフェッチ#
DBMS は、クエリに基づいてページを事前に交換することができます。特に、
- 順次クエリ
- インデックスクエリ
ページ 1 にクエリが到達すると、バッファプールは次に解析する必要があるページをバッファプールにロードします。
同様に、事前にロードすることもできます。
スキャン共有（同期スキャン）#
通常、同じものを複数回クエリする場合に発生します。
最初のクエリがテーブルをスキャンし、しばらくしてから 2 番目のクエリも同じテーブルをスキャンする場合、最終的に 2 番目のクエリは最初のクエリと同期してスキャンします。最初のクエリが終了した後、2 番目のクエリは欠落したデータを補完します。
Q1 が半分までクエリを実行しているときに、Q2 も同じクエリを実行します
Q1 が一部の距離をクエリしたため、バッファプールにページ 0 を再度ロードするのは非常に無駄です。したがって、Q1 と一緒にクエリを実行できます。
一緒にクエリを実行した後、Q2 の残りのページ 0〜ページ 2 をクエリします
このようなクエリを実行する場合、最終的な結果は異なる可能性があります。クエリは順不同です。順序が非常に重要で確定的な構造に対しては、このようなクエリは使用されません。
バッファプールバイパス#
一部の操作はバッファプールに保存されない場合があります。これにより、オーバーヘッドが削減されます。
5. OS ページキャッシュ#
通常、DBMS では直接 OS のファイル管理を使用しません。
- ページの多重コピーを減らす
- ページのキャッシュアウトポリシーを減らす
- I/O の制御を強化する
6. バッファ置換ポリシー#
DBMS がバッファプール内のフレームをクリアする必要がある場合、どのページを置換するかを決定する必要があります。
したがって、バッファ置換ポリシーはフレームのクリアに関するアルゴリズムです。
その主な目標は
- 正確
- 一貫性
- 速度
- メタデータのオーバーヘッド
最近使用された（LRU）#
最後にアクセスされたページを記録するためのタイムテーブルを維持し、フレームを置換する必要がある場合は、最後にアクセスされたページを置換します。
CLOCK#
クロックアルゴリズムは、LRU の近似です。利点は、各ページの時間表を記録する必要がなく、ビットの形式で記録することです。
クロックは、すべてのページを特定の順序で記録し、その順序はリング状になります。初期状態では、すべてのページのビットを 0 にマークします。ページがアクセスされると、そのページのビットを 1 にマークします。置換するページを検索するときは、順番に検索し、ページのビットが 1 であれば、そのビットを 0 にマークします。ページのビットが 0 であれば、そのページを置換します。
page_id clock_page() {
static page_id ref = 0;
for ( ; ; ref ++ ) {
if(ref >= BUFFER_POOL_SIZE) ref = 0;
if (bit[ref])
bit[ref] = 0;
else
return ref;
}
return -1;
}
代替案#
LRUやCLOCKのいずれも、シーケンシャルフラッディング操作に対しては影響が大きいです。
- 一連のページを順番にクエリする操作
- この操作は一度だけ実行され、二度とアクセスされません
これにより、バッファプールに格納されるデータは次に必要なデータではありません。
このような状況を避けるために、通常は LRU-K を使用して置換します。
各ページの最近の K 回のアクセスを追跡します。DBMS はこの記録に基づいてアクセスの優先順位を決定します。
Dirty Page#
非 Dirty ページの場合、ページを破棄するだけで済みますが、Dirty ページの場合は永続性を保つためにディスクに書き戻す必要があります。
この現象を回避するために、バッファプール内の Dirty ページを定期的にスキャンし、ディスクに書き戻すことで、Dirty ピンフラグを安全に削除できます。