- DBのファイルを管理する - 読み取り・書き込みを独自にスケジューリングする（OSのファイルシステムに任せない） - ページを追跡する ## Page - ページは固定長 - 1ファイルの中に複数のページがあることがあることが一般的 - ページIDという、unique identifierが割り当てられている - 3つの「ページ」という言葉 - Hardware Page (4KB): ストレージのページ - Atomicな書き込みが保証される - OS Page (4KB, [[Huge page]] 2MB, 1GB) - Database Page (512B ~ 32KB) - 製品によって色々なサイズ - 4KB: SQLite, Oracle, DB2など - 8KB: Microsoft SQLServer, PostgreSQL, Ingresなど - 16KB: MySQL - どういうサイズが最適なのか? - Read heavy workloads: ページサイズを大きくする（読み取りスループット向上） - Write heavy workloads: ページサイズを小さくする（ページサイズ大きすぎると、小さなデータ変更でも大量の書き込みが必要になる） ### Page Header - 各ページの先頭には、ページの中身に関するメタデータを持つHeaderが付く - Page Size - Checksum - DBMS Version - Transaction Visibility情報（[[Concurrency Control]]用） - Compression / Encoding Meta-data - Schema Information - Data Summary / Sketches - 一部のシステム（Oracleなど）は、ページ単体で自己完結（self-contained）していることを要求する ## Pageのアーキテクチャ - **Heap File Organization**: ファイルを、ページのUnordered Collectionとして管理する. これが一般的。 - インデックスとストレージが分離している。インデックスのリーフに、ページ番号とスロット番号が入っている。 - **Tree File Organization**: ページ群を[[B+ Tree]]などの木構造で組織化し、ノードをたどりながら必要なページにアクセス - つまりインデックスとストレージが一体化している？B Treeのリーフに、生のタプルが入っている状態。MySQL [[InnoDB]]はこれらしい - **Sequential / Sorted File Organization** ([[ISAM]]): キーの順序に沿ってページやレコードを並べて配置する - **Hashing File Organization**: レコードのハッシュ値で、どこのページに配置すべきか決定する - Page Directory: テーブルごと、該当するページがどのファイルに含まれているか記録しているグローバルな辞書（DB object 1つにつき1エントリ） - ページ$p$にアクセスする場合、まずそのページが含まれているファイルをPage Directoryから特定し、$p * \text{Page size}$でオフセットを計算してアクセスする - Page Directory自体もページとしてディスク上に保持され、データページと同期が取れている必要がある - DBMSはページの中身についてのメタデータも保持する - ページごとの空き容量 - 空き/未使用ページのリスト - ページの種類（データ or メタデータ） ## Page Layout Page Storage Architecture（Heap/Tree/Sequential/Hashing File Organization）が決まったら、次にページ**内部**でデータをどう並べるかを決める必要がある。以下3つのアプローチがある（今回はApproach 1のみ扱う）。 - Approach #1: Tuple-oriented Storage - Approach #2: Log-structured Storage - Approach #3: Index-organized Storage ### Tuple-oriented Storage: Slotted Pages - 素朴な案（Strawman）: ページ内のタプル数を記録しておき、新規タプルは末尾に追記する - 問題点1: タプルを削除した場合、単純に詰めるとタプルの物理的な位置がズレて、既存のRecord IDが無効になってしまう - 問題点2: 可変長属性を持つ場合、タプルサイズが固定にならず扱いづらい - **Slotted Pages**: 上記の問題を解決する、最も一般的なページレイアウト手法 - ページの先頭からHeader・Slot Arrayを書いていき、末尾からタプル本体（固定長・可変長どちらも）を書いていく - Slot Arrayは、各スロット番号をタプルの開始位置オフセットにマッピングする - Headerは以下を追跡する - 使用中のスロット数 - 最後に使用したスロットの開始位置オフセット - タプルを削除する場合、タプル本体を消してSlot Arrayのエントリだけ無効化すればよく、他のタプルのRecord IDには影響しない - 空間の無駄が少なくなる - レコードIDは、ページIDとスロット番号で表現される - DBMSによってサイズが異なる（例: Postgres CTID 6-byte, SQLite ROWID 8-byte, Oracle ROWID 10-byte） - アプリケーション側は、Record IDの値そのものに意味があると期待してはいけない ## タプルのアーキテクチャ - ページ内に書くタプルは、`|ヘッダ|データ1|データ2|...|`と表現できる - タプルのバイト列をどう属性の型・値に解釈するかはDBMS次第で、DBMSのカタログにあるスキーマ情報を使って解釈する ### Tuple Header - 各タプルにもHeaderが付き、以下のようなメタデータを持つ（テーブルのスキーマ情報自体は持たない） - Visibility情報（[[Concurrency Control]]用） - NULL値を表すBit Map ### Tuple Data - 属性は基本的にテーブル作成時に指定した順番で格納される（ソフトウェア工学的な単純さのため） - ただし、後述のword alignmentの都合でより効率的な順序に並べ替えることもある - 各データがワード幅（64bitなど）に収まらない場合、ワード境界をまたがるデータが出ると困る（CPUが余計な処理をせずアクセスできるようにするため）ので、以下のどれかをする - パディングをする（属性の後ろに空きビットを追加し、次のワードサイズまで切り上げる） - いい感じにリオーダーする（属性の物理的な並び順を変えてアラインさせる。それでも余った分はパディングが必要になることがある） ### データ型の表現 - `INTEGER` / `BIGINT` / `SMALLINT` / `TINYINT`: C/C++と同様の表現 - `FLOAT` / `REAL`（可変精度） vs `NUMERIC` / `DECIMAL`（固定精度） - Variable Precision Numbers: [[IEEE 754]]に従ったネイティブ表現。CPU側に専用命令・レジスタがあるため高速だが、正確な値を保証しない（例: `0.1 + 0.2 != 0.3`になりうる） - Fixed Precision Numbers: 丸め誤差が許容できない場合に使う、任意精度・スケールの数値型。可変長のバイナリ表現＋メタデータとして実装されることが多い（例: PostgresのNUMERIC型は`ndigits`, `weight`, `scale`, `sign`, `digits`を持つ構造体） - `VARCHAR` / `VARBINARY` / `TEXT` / `BLOB`: 長さ情報を持つHeader + データバイト列、またはデータが格納された別ページ/オフセットへのポインタ - 照合順序（collation）・ソート順にも注意が必要 - `TIME` / `DATE` / `TIMESTAMP` / `INTERVAL`: Unixエポック（1970年1月1日）からの（マイクロ/ミリ）秒を表す32/64bit整数 ### NULL値の扱い - Choice #1: Null Column Bitmap Header（Tuple Headerに、どの属性がNULLかを示すビットマップを持つ）: Row-storeで最も一般的 - Choice #2: Special Values（例: `INT32_MIN`のような、その型でNULLを表す特別な値を決め打ちする）: Column-storeでよく使われる - Choice #3: Per Attribute Null Flag（属性ごとにNULLフラグを持つ）: 1bitだけだとword alignmentが崩れるため単純な1bitでは済まず、非推奨（Don't Do This） ### 大きな値の扱い - 多くのDBMSでは、タプルが1ページのサイズを超えることを許可しない - ページサイズを超える値は、別途Overflowページに格納する - Postgres: TOAST（2KB超） - MySQL: Overflow（ページサイズの半分超） - SQL Server: Overflow（ページサイズ超） - 元のタプルの属性値部分には、サイズとOverflowページへのlocation（ポインタ）を格納する - 圧縮などの最適化の余地もある（例: German Strings） - External Value Storage: DB外部のファイルに大きな値を保存し、BLOB型として扱う方法もある（Oracle `BFILE`, Microsoft `FILESTREAM`など） - DBMSは外部ファイルの中身を直接操作できない - Durability保証もTransaction保証も効かない