はじめに
Part 5でトランザクションとWALを実装した。
でも今のままだと、10万件のデータから1件探すのに10万件全部見る必要がある。遅い。
今回はインデックスとクエリ最適化を実装して、大量データでも高速に検索できるようにする。
インデックスって何？
本の索引（index）と同じ。
本で「Rust」について書かれているページを探すとき、最初から全部読む？読まない。索引を見て「Rust → p.42, p.128」ってすぐ分かる。
データベースのインデックスも同じ。
インデックスなし: 全件スキャン O(n)
インデックスあり: ツリー探索 O(log n)
100万件のデータで、20回の比較で見つかる vs 100万回の比較。圧倒的。
B+Tree インデックス
データベースでよく使われるのはB+Tree。Part 1で作ったB-Treeの改良版：
- 全てのデータはリーフノードにある
- リーフノードがリンクリストでつながってる
- 範囲検索が高速
今回は簡易版を実装：
/// B+Tree インデックス（簡易実装）
#[derive(Debug)]
pub struct BPlusTreeIndex {
name: String,
table_name: String,
column_name: String,
/// キー → 行IDのリスト
entries: HashMap<IndexKey, Vec<u64>>,
/// ソートされたキーリスト（範囲検索用）
sorted_keys: Vec<IndexKey>,
needs_sort: bool,
}
entriesでキーから行IDを引ける。同じキーに複数の行がある場合（例：年齢30の人が複数）、Vec<u64>で持つ。
キーの変換
値をバイト列に変換してキーにする：
fn value_to_key(value: &Value) -> IndexKey {
match value {
Value::Integer(i) => i.to_be_bytes().to_vec(), // ビッグエンディアン
Value::Real(f) => f.to_be_bytes().to_vec(),
Value::Text(s) => s.as_bytes().to_vec(),
Value::Boolean(b) => vec![if *b { 1 } else { 0 }],
Value::Null => vec![],
}
}
ビッグエンディアンを使うのがポイント。バイト列として辞書順ソートしたときに、数値としても正しい順序になる。
基本操作
impl BPlusTreeIndex {
/// エントリを追加
pub fn insert(&mut self, value: &Value, row_id: u64) {
let key = Self::value_to_key(value);
self.entries.entry(key).or_insert_with(Vec::new).push(row_id);
self.needs_sort = true;
}
/// 完全一致検索
pub fn lookup(&self, value: &Value) -> Option<&Vec<u64>> {
let key = Self::value_to_key(value);
self.entries.get(&key)
}
/// 範囲検索（開始キー以上）
pub fn range_from(&mut self, from: &Value) -> Vec<u64> {
self.ensure_sorted();
let from_key = Self::value_to_key(from);
let mut result = Vec::new();
for key in &self.sorted_keys {
if key >= &from_key {
if let Some(ids) = self.entries.get(key) {
result.extend(ids);
}
}
}
result
}
}
ensure_sorted()で必要なときだけキーをソートする遅延評価。
インデックスマネージャ
テーブルとカラムでインデックスを管理：
pub struct IndexManager {
/// テーブル名 → カラム名 → インデックス
indexes: HashMap<String, HashMap<String, BPlusTreeIndex>>,
}
impl IndexManager {
/// インデックスを作成
pub fn create_index(&mut self, name: &str, table: &str, column: &str) {
let table_indexes = self.indexes.entry(table.to_string())
.or_insert_with(HashMap::new);
let index = BPlusTreeIndex::new(name, table, column);
table_indexes.insert(column.to_string(), index);
}
/// インデックスを取得
pub fn get_index(&self, table: &str, column: &str) -> Option<&BPlusTreeIndex> {
self.indexes.get(table).and_then(|t| t.get(column))
}
}
クエリプラン
オプティマイザが出力する実行計画：
/// クエリプラン
#[derive(Debug, Clone)]
pub enum QueryPlan {
/// テーブルフルスキャン
TableScan {
table: String,
filter: Option<Expression>,
},
/// インデックスシーク（完全一致）
IndexSeek {
table: String,
index_column: String,
value: Value,
additional_filter: Option<Expression>,
},
/// インデックスレンジスキャン
IndexRangeScan {
table: String,
index_column: String,
from: Option<Value>,
to: Option<Value>,
additional_filter: Option<Expression>,
},
}
3種類のプラン：
- TableScan: 全行読む（最悪）
- IndexSeek: インデックスで1件特定（最速）
- IndexRangeScan: インデックスで範囲検索
クエリオプティマイザ
SELECT文を解析して、最適なプランを選ぶ：
pub struct QueryOptimizer<'a> {
index_manager: &'a IndexManager,
}
impl<'a> QueryOptimizer<'a> {
/// SELECTクエリを最適化
pub fn optimize_select(&self, stmt: &SelectStatement) -> QueryPlan {
let table = &stmt.from;
// WHERE句がなければフルスキャン
let Some(ref where_clause) = stmt.where_clause else {
return QueryPlan::TableScan {
table: table.clone(),
filter: None,
};
};
// WHERE句を解析してインデックスを使えるか判断
if let Some(plan) = self.try_use_index(table, where_clause) {
return plan;
}
// インデックスが使えなければフルスキャン + フィルタ
QueryPlan::TableScan {
table: table.clone(),
filter: Some(where_clause.clone()),
}
}
}
インデックス利用判定
fn try_use_index(&self, table: &str, expr: &Expression) -> Option<QueryPlan> {
match expr {
// column = value の形
Expression::BinaryOp { left, op: BinaryOperator::Eq, right } => {
if let (Expression::Column(col), Expression::Literal(val)) =
(left.as_ref(), right.as_ref())
{
// このカラムにインデックスがあるか？
if self.index_manager.get_index(table, col).is_some() {
return Some(QueryPlan::IndexSeek {
table: table.to_string(),
index_column: col.clone(),
value: val.clone(),
additional_filter: None,
});
}
}
}
// column > value または column >= value
Expression::BinaryOp { left, op, right }
if matches!(op, BinaryOperator::Gt | BinaryOperator::GtEq) =>
{
if let (Expression::Column(col), Expression::Literal(val)) =
(left.as_ref(), right.as_ref())
{
if self.index_manager.get_index(table, col).is_some() {
return Some(QueryPlan::IndexRangeScan {
table: table.to_string(),
index_column: col.clone(),
from: Some(val.clone()),
to: None,
additional_filter: None,
});
}
}
}
_ => {}
}
None
}
WHERE句の形を見て：
-
id = 1→ IndexSeek -
age > 25→ IndexRangeScan - その他 → TableScan
コスト見積もり
複数のプランがあったとき、どっちが速いか判断するのがコスト見積もり：
pub fn estimate_cost(&self, plan: &QueryPlan, table_row_count: usize) -> Cost {
match plan {
QueryPlan::TableScan { filter, .. } => {
// フルスキャンは全行読む
let io_cost = table_row_count as f64;
let cpu_cost = if filter.is_some() {
table_row_count as f64 * 0.1
} else {
0.0
};
Cost { io_cost, cpu_cost, total: io_cost + cpu_cost }
}
QueryPlan::IndexSeek { .. } => {
// インデックスシークは非常に高速（固定コスト）
Cost { io_cost: 2.0, cpu_cost: 0.1, total: 2.1 }
}
QueryPlan::IndexRangeScan { .. } => {
// 範囲スキャンは選択率に依存（仮に10%と仮定）
let estimated_rows = (table_row_count as f64 * 0.1).max(1.0);
let io_cost = estimated_rows + 2.0;
let cpu_cost = estimated_rows * 0.05;
Cost { io_cost, cpu_cost, total: io_cost + cpu_cost }
}
}
}
10,000行のテーブルだと：
- TableScan: コスト約11,000
- IndexSeek: コスト約2
- IndexRangeScan: コスト約1,050
動かしてみる
$ cargo run
=== Query Optimizer デモ ===
--- Creating Indexes ---
Created index: idx_users_id on users(id)
Created index: idx_users_age on users(age)
--- Index Statistics ---
idx_users_age: 5 unique keys, 5 entries
idx_users_id: 5 unique keys, 5 entries
--- Query Plan Selection ---
Query: SELECT * FROM users WHERE id = 1
Plan: INDEX SEEK on 'users.id' = Integer(1)
Cost: 2.10 (IO: 2.00, CPU: 0.10)
Query: SELECT * FROM users WHERE age > 25
Plan: INDEX RANGE SCAN on 'users.age': x >= Integer(25)
Cost: 1052.00 (IO: 1002.00, CPU: 50.00)
Query: SELECT * FROM users WHERE name = 'Alice'
Plan: TABLE SCAN on 'users' with filter
Cost: 11000.00 (IO: 10000.00, CPU: 1000.00)
--- Index Lookup Demo ---
Lookup id=3: Some([2])
Range age >= 28: [3, 1, 2]
おおお：
-
id = 1: インデックスあり → IndexSeek（コスト2.1） -
age > 25: インデックスあり → IndexRangeScan（コスト1052） -
name = 'Alice': インデックスなし → TableScan（コスト11000）
5000倍以上のコスト差。これがインデックスの威力。
インデックスの統計情報
本格的なオプティマイザは統計情報を使う：
pub struct IndexStats {
pub name: String,
pub column: String,
pub unique_keys: usize, // ユニークなキーの数
pub total_entries: usize, // 全エントリ数
}
- カーディナリティ: ユニークな値の数。高いほど選択性が良い
- 選択率: 条件に合う行の割合。低いほどインデックスが有効
例えば：
-
gender列（男/女の2値）: カーディナリティ低い → インデックス効果薄い -
email列（ユニーク）: カーディナリティ高い → インデックス効果大
実際のDBMSとの比較
PostgreSQLのEXPLAINを見てみよう：
EXPLAIN SELECT * FROM users WHERE id = 1;
-- Index Scan using users_pkey on users (cost=0.15..8.17 rows=1 width=...)
EXPLAIN SELECT * FROM users WHERE name = 'Alice';
-- Seq Scan on users (cost=0.00..35.00 rows=1 width=...)
-- Filter: (name = 'Alice'::text)
今回の実装と似たような出力が出る。
本格的なオプティマイザへの道
今回の実装は簡易版。本格的にはもっと色々必要：
1. 複合インデックス
CREATE INDEX idx_name_age ON users(name, age);
複数カラムでインデックスを作る。
2. カバリングインデックス
CREATE INDEX idx_covering ON users(id) INCLUDE (name, age);
インデックスだけで結果を返せる（テーブルにアクセスしない）。
3. ジョイン最適化
SELECT * FROM users u JOIN orders o ON u.id = o.user_id;
- Nested Loop Join
- Hash Join
- Merge Join
どれを使うか決める。
4. 統計情報の自動収集
PostgreSQLのANALYZEやMySQLのANALYZE TABLEのように、定期的にデータ分布を収集。
5. プランキャッシュ
同じクエリを何度も最適化するのは無駄。プランをキャッシュする。
まとめ
Part 6では：
- B+Treeインデックス: キーから行IDを高速に引ける
- インデックスマネージャ: テーブル×カラムでインデックスを管理
- クエリプラン: TableScan/IndexSeek/IndexRangeScan
- クエリオプティマイザ: WHERE句を解析して最適プランを選択
- コスト見積もり: IO/CPUコストで比較
これで全6回のシリーズ完結！
作ったもの：
- Part 1: B-Tree
- Part 2: ページ管理とバッファプール
- Part 3: SQLパーサー
- Part 4: クエリ実行エンジン
- Part 5: トランザクションとWAL
- Part 6: インデックスとクエリ最適化
フルスクラッチでデータベースの基本要素が揃った。もちろん本物のPostgreSQLやMySQLに比べたら全然機能足りないけど、仕組みを理解するにはこれで十分。