1. イントロダクション#
ストレージ方法：
- ページはどのようにディスクに保存されるか
高速な操作：
- DBMS では、データを操作する前に、すべてのデータをディスクからメモリに移動する必要があります。
2. ロックとラッチ#
3. バッファプール#
メモリには固定サイズのページが格納されています。
それぞれのレコードは フレーム と呼ばれます。
ページが必要な場合、フレームをすぐにコピーします。
Dirty ページはすぐに書き戻されません。（Write-Back キャッシュ）
バッファプールメタデータ#
ページテーブルは、メモリ内のどのページが追跡されているかを追跡するために使用されます。
通常、ページテーブルには他の情報も保存されます。
- Dirty フラグ
- Pin/Reference カウンター
Dirty フラグは、ページが書き込まれたかどうかを示すために使用されます。
Pin/Reference カウンターは、フレームを固定して、そのページがディスクに戻されないようにします。
ページディレクトリは、ページ ID をページの場所にマッピングするマッピングです。すべての情報はディスクに保存する必要があり、DBMS がそれを見つけることができます。
ページテーブルは、ページ ID をバッファプール内のフレームにマッピングするマッピングです。これはディスクに保存する必要のないインメモリのデータ構造です。
メモリ割り当てポリシー#
グローバルポリシー
- すべての操作に責任を持ち、グローバルな最適化を保証します。
ローカルポリシー
- 現在のクエリの効率のみを考慮し、グローバルな影響を考慮しません。
4. バッファプールの最適化#
複数のバッファプール#
通常、DBMS には 1 つのバッファプールだけではありません。
DBMS は、さまざまな目的（たとえば、データベースごとのバッファプール、ページタイプごとのバッファプール）のために複数のバッファプールを維持します。そして、各バッファプールは、その中に格納されている数に対してカスタマイズされたローカルポリシーを持つことができます。
異なるバッファプールにアクセスするための主な方法は 2 つあります。
- オブジェクト 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#
clock アルゴリズムは LRU の近似です。利点は、各ページの記録をタイムテーブルで記録する必要がないことです。代わりにビットの形式で記録します。
Clock は、すべてのページを特定の順序で記録し、その順序は環状になります。初期状態では、すべてのページのビットを 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 ページ#
Dirty でないページの場合、ページを破棄するだけですが、Dirty ページの場合は永続性を保つためにディスクに書き戻す必要があります。
この現象を回避するために、バッファプール内の Dirty ページを定期的にスキャンしてディスクに書き戻すことができます。これにより、Dirty ピンフラグを安全に削除できます。