B-Tree - ページ単位の入出力に合わせた索引の木
B-Tree は、1 つのノードに数百件のキーを並べることで、木の段数を数段に抑えた探索木です。ノードとは木を構成する 1 つの箱を指します。この構造が最もよく使われるのは、RDB(リレーショナルデータベース)の索引(インデックス)の実装です。CREATE INDEX で作る一般的な索引も、主キーや一意制約を支える索引も、多くは B-Tree 系の構造です。 ...
B-Tree は、1 つのノードに数百件のキーを並べることで、木の段数を数段に抑えた探索木です。ノードとは木を構成する 1 つの箱を指します。この構造が最もよく使われるのは、RDB(リレーショナルデータベース)の索引(インデックス)の実装です。CREATE INDEX で作る一般的な索引も、主キーや一意制約を支える索引も、多くは B-Tree 系の構造です。 ...
機材の予約サービスを考えます。予約を取り消すと、予約のレコードは消えずに deleted_at に取り消した日時が入ります。商品はカメラ・三脚・レンズの 3 つで、カメラには予約が 1 件も無く、三脚には有効な予約が 1 件、レンズには取り消した予約が 1 件だけあります。商品ごとに有効な予約の数 active_count を出すため、次の SQL を書きました。結果は何行になるでしょうか。 ...
SQL には欲しい結果だけを書き、どの索引をどの順に読むかは DB(データベース)に任せます。DB が決めたこの手順が、実行計画です。任せた部分の中身を知らないままアプリケーションから SQL を書いていると、次のような前提を置きがちです。 ...
PostgreSQL を速くする設定として、次の 2 つがよく紹介されます。テスト用の DB(データベース)を Testcontainers で立てる エムスリーのテックブログでも、2 つが並んで使われています。 synchronous_commit = off fsync = off どちらか一方だけを設定した PostgreSQL に 1 行ずつ INSERT を送り続け、途中で docker kill を使ってプロセスごと強制終了したとします。起動し直した時、成功が返ったはずの行が消えているのは、どちらの設定でしょうか。 ...
Index Scan は、索引(インデックス)を辿って条件に一致するレコードの在り処を求め、そこから表のレコードを読み出す方法です。DB(データベース)が 1 つの表からレコードを取り出す手段の 1 つで、表を先頭から順に読むシーケンシャルスキャン(sequential scan)と対になります。 ...
会員の表に、紹介してくれた会員の id を入れる referred_by というカラムがあります。紹介を受けずに入会した会員は NULL です。この表から「まだ誰も紹介していない会員」を数える SQL を書きました。何件返るか、予想してみてください。 ...
Transaction Isolation(分離)は、複数のトランザクションを同時に実行した時に、互いの読み書きがどのように観測され、どのような結果まで許されるかを定める規則です。ACID(Atomicity、Consistency、Isolation、Durability。原子性・一貫性・分離・耐久性)の I です。 ...
Snapshot Isolation は、トランザクションごとに 1 つのスナップショットを固定して読み、書き込みが重なった時に片方を中止する分離の方式です。分離とは、同時に走るトランザクションどうしが互いの途中の変更をどこまで見るかを決めることを指します。スナップショットは、ある時点までにコミット(commit)した変更だけを含むデータの見え方です。 ...
外部キー制約(foreign key constraint)は、ある表のカラムに入っている値が、別の表に実在するレコードを指していることを DB(データベース)に保証させる仕組みです。PostgreSQL の定義では、1 つのカラムまたは複数のカラムの組の値が、別の表のいずれかのレコードに現れる値と一致する必要があります。この保証が保たれている状態を参照整合性(referential integrity)と呼びます。 ...
一意制約(unique constraint)は、あるカラム、または複数のカラムの組に入っている値が表の中で重複しないことを DB(データベース)に保証させる仕組みです。SQL では、カラムの定義に UNIQUE を書くか、表に対して UNIQUE (カラム名, ...) を書いて宣言します。 ...
Transaction Scope(トランザクションの範囲)は、BEGIN から COMMIT までの間にどの処理を入れるかの決め方です。DB(データベース)のトランザクションが巻き戻せるのは、その DB 内の更新です。外部 API の呼び出しまで取り消せるわけではありません。 ...
Deadlock(デッドロック)は、2 本以上のトランザクションが互いのロックの解放を待ち、どれも先に進めなくなる状態です。レコードを更新すると DBMS(Database Management System)はそのレコードにロックを取り、通常はトランザクションが終わるまで解放しません。 ...
LSM-Tree(Log-Structured Merge-Tree)は、更新をメモリに貯めてから、キーの順に並べたファイルとしてディスクにまとめて書く索引です。同じキーを更新すると新しいバージョンを別のファイルに足し、古いバージョンは後から行うコンパクション(compaction)で捨てます。 ...
Partitioning(パーティショニング)は、あるカラムの値によって、1 つの論理的な表を複数の物理的な表に分けて保存する技術です。分ける基準にするカラムをパーティションキー、分けた先の 1 つ 1 つの表をパーティションと呼びます。アプリケーションは今まで通り親の表に SQL を発行し、DB(データベース)がキーの値からレコードの行き先や、読む先のパーティションを選びます。 ...
Query Plan Cache(実行計画のキャッシュ)は、DB(データベース)が同じ形の SQL を受け取るたびに構文解析と実行計画の作成をやり直さず、前に作った結果を使い回す仕組みです。実行計画(query plan)は、どの表をどの順に読み、どの索引を使うかという DB 内部の手順で、作り方は Query Processing のノートで説明しています。 ...
Columnar Storage(列指向ストレージ)は、表のデータを行(レコード)ごとではなく列(カラム)ごとに連続して格納する方式です。この方式で格納する DB(データベース)を Column Store、行ごとに格納する一般的な RDB(リレーショナル DB)を Row Store と呼びます。分析用の DB や、Apache Parquet のようなファイル形式がこの方式を使っています。 ...
Materialized View(マテリアライズドビュー)は、問い合わせの結果を表として DB(データベース)に保存し、読む時には保存した結果を返す仕組みです。普通の view(ビュー)は SELECT の定義だけを持ち、参照される度に元の表から計算し直します。materialized view は計算済みの結果を持つので、読む時は計算しません。 ...
セマンティックレイヤー(semantic layer)は、「売上」「販売点数」のような指標の計算式と、テーブル同士のつなぎ方を一箇所に定義しておき、問い合わせのたびにその定義から集計の SQL を組み立てる層です。ダッシュボード、表計算、LLM(Large Language Model、大規模言語モデル)のエージェントは、テーブルに SQL を書く代わりに「どの指標を、どの切り口(地域別・月別のような集計の分け方)で」とだけ問い合わせます。実装には、SQL でテーブルの変換を定義・管理するツールの dbt の Semantic Layer(エンジンは OSS の MetricFlow で、手元の dbt Core と組み合わせても動く)、Looker の LookML、Cube などがあります。 ...
ページング(pagination)は、一覧の結果を 20 件ずつのように区切って返す仕組みです。SNS のタイムライン、管理画面の一覧、API の一覧取得など、件数が多い一覧のほとんどで使われます。SQL で書く方法は大きく 2 つあり、1 つは LIMIT 20 OFFSET 40 のように先頭から何件を飛ばすかを指定する OFFSET、もう 1 つは前のページの最後のレコードの値を覚えておき、その続きから読むキーセット(keyset pagination、seek method とも呼ばれる)です。 ...
UUID(Universally Unique Identifier)は、128 ビットの識別子です。DB(データベース)に問い合わせずにアプリ側で ID を作れること、複数の DB で作った ID が衝突しないこと、URL に出しても件数や順番が推測されにくいことから、表の主キーに使われます。一方で、「UUID を主キーにすると索引が遅くなる」という話もよく聞きます。 ...
MVCC(Multiversion Concurrency Control)は、レコードを更新しても古い内容をすぐには消さず、複数の版を並べて持つことで、読み手と書き手が互いを待たずに済むようにする仕組みです。PostgreSQL では、UPDATE は古い版の隣に新しい版を足し、DELETE は版に「消した」という印を付けるだけです。誰からも見えなくなった古い版を後で回収するのが、VACUUM という処理です。 ...
接続プール(connection pool)は、アプリが DB(データベース)への接続を何本か張ったまま持っておき、問い合わせのたびに 1 本を貸し出して、終わったら返してもらう仕組みです。Java の HikariCP、Go の標準ライブラリ database/sql のように、アプリの中に持つ実装と、PgBouncer のように、アプリと DB の間に置く実装があります。 ...