# データパーティショニング ## 定義 データパーティショニング（Data Partitioning）とは、リレーショナル・データベースのリレーション（テーブル）のタプルを複数のディスク・ノードに分散配置する手法の総称である。[[David DeWitt]] と [[Jim Gray]] が [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]]（CACM 1992）において、並列データベースにおけるパーティション並列化の基盤として体系化した。3 つの基本手法——ラウンドロビン・ハッシュ・レンジ——を定義し、各手法がスキャン性能・連想アクセス性能・データ歪み耐性のトレードオフにおいて異なる特性を持つことを示した。 ## 3 手法の比較 | 手法 | 原理 | 最適アクセスパターン | 弱点 | |---|---|---|---| | **ラウンドロビン** | タプルを順番に各ディスクへ均等配分 | 全スキャン（I/O 帯域最大化） | 連想アクセス（特定値の検索）で全ディスクを走査 | | **ハッシュ** | 属性のハッシュ値でディスクを決定 | 連想アクセス（等値結合・ポイントルックアップ） | データをランダム化し範囲検索に不向き | | **レンジ** | 属性値の連続範囲を各ディスクに割当 | 範囲クエリ・連想アクセス・クラスタリング | データ歪み（一部パーティションに集中）リスク | ハッシュとラウンドロビンは歪みに強いが、レンジパーティショニングではデータ分布が偏ると特定ノードが高負荷になる（**data skew**）。Bubba はアクセス頻度（temperature）を重みとするハイブリッドレンジパーティショニングで歪みを軽減した [6]。 ## 横断的知見 - **3つ目の独立した教科書(詳説 データベース)が、レンジ/ハッシュの2系統への収斂を裏付ける**: [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.6 は、DeWitt/Gray(1992)のラウンドロビン・ハッシュ・レンジの3分類とは独立に、実務上のパーティショニングを「レンジ(シャーディング)」と「ハッシュ」の2方式で説明し、DDIA第7章が示す2系統への再編([[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]])と同じ結論に達する。1992年の理論的3分類・2026年のDDIA・2019年原著の詳説 データベースという時期の異なる3ソースが揃って「ラウンドロビンは現代の実装から実質的に脱落した」ことを示しており、DDIA単独の再編ではなく分野で共有された収斂であることが確認できる。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]], [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]], [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.6) - **コンシステントハッシュ法の「K/n 再配置」原則は、詳説 データベースが DeWitt/Gray の枠組みに明示的に接続する形で再定式化される**: 詳説 データベース §13.6.1 は、単純な `hash(v) mod N` 方式がクラスタサイズ変更のたびに大半のデータ移動を要すると指摘したうえで、コンシステントハッシュ法(Apache Cassandra・Riak が採用)がこれを緩和し「K 個の取り得るハッシュキーと n 個のノードがあるならば、平均すると K/n 個のキーしか再配置の必要がない」と明記する。これは本 concept が既に記録する一貫性ハッシュ法の定義と完全に一致する定量的主張であり、DeWitt/Gray が 1992 年に定式化した「ハッシュは連想アクセスに最適」という原則の上に、コンシステントハッシュ法が「再配置コストの最小化」という別の目的を積み増した歴史的順序を、詳説 データベースが分散システムの教科書の立場から追認する。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]], [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]] §13.6.1) - **ハッシュパーティショニングは分散 KVS・NoSQL の普遍的手法に収斂した**: DeWitt/Gray が 1992 年に「ハッシュは連想アクセスに最適」と定式化した原則は、Amazon Dynamo（2007）の一貫性ハッシュリング・Cassandra（2010）のパーティショナー・Google Bigtable の tablet 範囲分割の設計原則と直接対応する。Dynamo は「データをランダム化する」というハッシュの性質を意図的に利用し、特定キーへの集中アクセスを防止した。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]], [[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]], [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]) - **[[一貫性ハッシュ法]]はラウンドロビン/ハッシュ/レンジのどれに当たるか**: 一貫性ハッシュ（consistent hashing）はハッシュリング上で各ノードが担当範囲を持つため、**ハッシュとレンジの融合**に位置づけられる。ノード追加・削除時に再配置が最小化される点は DeWitt/Gray の分類には含まれていなかった（1992 年時点ではノードの動的追加を考慮した設計手法が未成熟）。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]]) - **パーティション数の最適化は現代クラウド DB でも継続課題**: DeWitt/Gray は「パーティション数が増えるとスキャンは改善するが、連想スキャンは起動コストとのクロスオーバーで悪化しうる [6, 11]」と述べた。Snowflake のマイクロパーティション・BigQuery のクラスタリングも同様のトレードオフを内包しており、自動最適化の研究が続く。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]]) - **Snowflake（SIGMOD 2016）はテーブルを「巨大な不変ファイル」に水平パーティショニングし、インデックスの代わりに min-max 統計によるプルーニングでレンジパーティショニングの目的を代替する**: 一次資料である [[@2016__SIGMOD__The Snowflake Elastic Data Warehouse]] には「マイクロパーティション」という語は登場しない（同用語は後年の Snowflake ドキュメントで使われる呼称）。本論文が実際に述べるのは、テーブルを S3 上の不変な大ファイル群に分割し、ファイル内は列ごとに圧縮するハイブリッドカラムナ(PAX)形式を採用し、ファイル単位の min-max 統計（zone maps 相当）でクエリに無関係なファイルをスキャン対象から除外する設計である。これは DeWitt/Gray のレンジパーティショニングが担っていた「範囲述語による対象データの絞り込み」という役割を、明示的なパーティションキー指定なしに達成する代替手段であり、パーティション手法というより**インデックスなしプルーニング**という別カテゴリの技法として位置づけるべきである。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]], [[@2016__SIGMOD__The Snowflake Elastic Data Warehouse]]) - **Snowflake のキャッシュ配置は一貫性ハッシュを「ノード間のデータ本体の配置」ではなく「ワーカーノードのキャッシュ割当」に使う**: DeWitt/Gray やハッシュパーティショニングの伝統的な用法はディスク上のタプル配置そのものを決定するが、Snowflake はテーブルファイル名に対する一貫性ハッシュで各ワーカーノードへの入力ファイル割当を決めるのみであり、ファイル自体は S3 上の単一の場所に存在し続ける。ノード集合変化時も lazy（LRU 置換に委ねる）に再配置される点は、既存 [[一貫性ハッシュ法]] の知見（ノード追加・削除時の再配置最小化）と一致するが、対象が「データそのもの」ではなく「キャッシュ配置というメタレベルの決定」である点が新規。(Source: [[@2016__SIGMOD__The Snowflake Elastic Data Warehouse]]) - **到着順を保証しない「追記専用の時間ウィンドウ・パーティショニング」は、DeWitt/Gray の3手法(ラウンドロビン・ハッシュ・レンジ)のいずれとも異なる第4の手法であり、書き込み時ソートのコストを読み取り側に転嫁する**: Honeycomb Retriever(→ [[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]])は、イベントのタイムスタンプでレンジパーティショニングするのではなく、到着順にイベントを追記しつつセグメントごとに最古・最新タイムスタンプだけをメタデータとして記録する。レンジパーティショニングは値でソートされた連続範囲を各パーティションに割り当てる前提を持つため、分散システムで避けられないイベントの遅延到着(out-of-order arrival)に対応するには挿入位置を探して書き換える必要が生じる。Retriever はこの書き換えコストを完全に回避し、代わりにクエリ時にウィンドウが重なる全セグメントを読んでから時間範囲でフィルタする(→ [[Zonemap]] のようなメタデータ絞り込みに近い)。Snowflake の min-max ファイルプルーニングが「インデックスなしプルーニング」としてレンジパーティショニングの目的を代替するのと同様、Retriever のセグメントタイムスタンプメタデータも「厳密な範囲分割」ではなく「大まかな重なり判定によるプルーニング」でレンジパーティショニングの目的を代替している。両者に共通するのは、パーティション手法の設計目標が「データをどこに置くか」から「クエリ時にどれだけ読み飛ばせるか」へ変化している点である。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]], [[@2016__SIGMOD__The Snowflake Elastic Data Warehouse]], [[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]]) - **ClickHouseの`PARTITION BY`は、DeWitt/Grayの3手法とは異なる第5の目的――「クエリ時の絞り込み」ではなく「ライフサイクル操作の単位」としてのパーティション――を持つ**: ClickHouse([[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]])はパートを「パーティション」というフォルダにグルーピングし、パートはパーティションをまたいでマージされないという制約を持つ。本章は低カーディナリティかつ粗粒度な列(例: `toStartOfDay(Timestamp)`)をパーティションキーに選ぶべきだと明示的に推奨し、細粒度なパーティションはパートの最適化(マージ)を妨げると警告する。これはクエリの選択性を高めるための絞り込み(Retrieverの時間ウィンドウやSnowflakeのmin-maxファイルプルーニング)とは異なり、TTLベースのデータ削除・階層移動を「パート単位の一括操作」として高速化するための単位である(`ttl_only_drop_parts=1`はパーティション内のパートを丸ごと削除する)。同じ「時間で切る」という操作でも、Retrieverはセグメント境界そのものをクエリプルーニングの単位として使うのに対し、ClickHouseはパーティションプルーニングを4段階絞り込みの最初の粗いフィルタとしてのみ使い、パーティションの主目的はむしろライフサイクル管理(TTL移動・削除の一括実行単位)にあると位置づけている点で、パーティショニングという同一の技法が異なる主目的(クエリ高速化 対 運用操作の単位化)のために使われる例を示す。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]], [[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]], [[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]]) - **DDIA 2E(2026)は「partitioning」ではなく「sharding」という語を意図的に選び、DeWitt/Grayの3手法をハッシュ系とレンジ系の2系統へ再編する**: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]]は用語選択の理由を明示しないが、キーレンジシャーディング(DeWitt/Grayのレンジパーティショニングに相当)とキーのハッシュによるシャーディング(ハッシュパーティショニングに相当)の2系統だけを軸に据え、ラウンドロビンには触れない。これはDeWitt/Grayが「ラウンドロビンは全スキャンに最適だが連想アクセスに弱い」と位置づけた手法が、シャーディングの主目的(個々のレコードへの高速アクセス経路の提供)には合わないため章の構成から自然に脱落したと解釈できる——1992年の3分類のうち現代のシャーディング実装で生き残ったのは2系統のみという点が、30年を隔てた教科書の再定式化から確認できる。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]], [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]]) - **「固定シャード数 + ノード単位の再割当」は、DeWitt/Grayが想定していなかった第3のリバランシング戦略である**: DeWitt/Grayのレンジ/ハッシュパーティショニングはいずれもパーティション境界そのものの変更(分割・併合)を再編成の単位として暗黙に想定していたが、DDIA第7章の固定シャード数方式(Citus・Riak・Elasticsearch・Couchbase)はシャード境界を一切変えず、既存シャードをノード間で丸ごと移動するだけでリバランシングを完了する。これはシャードの生成コスト(データ再書き込み)とノード間移動コスト(ネットワーク転送のみ)を分離する設計であり、1992年の分類が「パーティション方式」と「再配置方式」を一体として扱っていたのに対し、DDIA第7章はこの2つを独立した設計軸として切り出している。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]], [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]]) - **DDIA第7章は本 concept の「多次元パーティショニング」という未解決の問いには踏み込まず、代わりに「1次元パーティションキーの先頭部分によるシャード決定 + 残りの列でのソート」という限定的な複合キー戦略のみを示す**: 章はレンジクエリを保ちたい場合、パーティションキーを複合キーの先頭列のみとし、残りの列でシャード内ソートすることで「同一パーティションキー内では効率的なレンジクエリが可能」と述べるにとどまり、緯度・経度のような真の多次元パーティショニングには言及しない。DeWitt/Grayが1992年に「追加研究が必要」とした多次元パーティショニングは、2026年の教科書時点でも汎用シャーディング機構としては標準化されていないことが確認できる。(Source: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]], [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]]) ## 未解決の問い - **多次元パーティショニング**: DeWitt/Gray は緯度・経度の 2 次元パーティショニングの例を挙げ「追加研究が必要」と述べた。DDIA 2E(2026)第7章も複合キーの先頭列によるシャーディングを示すのみで真の多次元分割には踏み込んでいない。現代の地理空間 DB・ベクトル DB はどのパーティション手法を採用しているか - **オンラインデータ再編成**: DeWitt/Gray が未解決課題とした「テラバイト DB のパーティション変更をオンラインで実行する」は現代の分散 DB でどう解決されているか - **スキューに対する自動対処**: Bubba の temperature-based パーティショニングの後継として、ML ベースの動的リパーティショニングはどこまで実用化されているか - Retriever の時間ウィンドウ・パーティショニングは、バックフィルデータ(数時間〜数日前のタイムスタンプを持つバッチ処理結果)が現在のセグメントに混入すると、セグメントのタイムスタンプ範囲が不必要に広がりプルーニング効果が下がるという弱点を本章自身が認めている。DeWitt/Gray のレンジパーティショニングにおける data skew 対策(Bubba の temperature-based ハイブリッド)は、この「時間ウィンドウの歪み」問題にも応用できるか。 - DDIA第7章の固定シャード数方式は「事前見積りを誤ると高価なリシャーディングが必要」と述べるが、見積り誤りをオンラインで検知し、ダウンタイムなくシャード数を増やす一般的手法はDeWitt/Gray以来未解決のままか。Citus・Elasticsearch等の実装ごとの解決度合いを比較した文献はあるか。 - 詳説 データベース13章はレンジパーティショニングの負荷偏り対策として「頻繁にアクセスされる範囲を小さいパーティションに分割する」運用的な対処のみを述べ、Bubbaのtemperatureベース手法のような自動化には踏み込まない。分散SQLデータベース(Spanner・CockroachDB)の実装では、この動的分割はどこまで自動化されているか。 ## 関連 - ソース: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]] / [[@2016__SIGMOD__The Snowflake Elastic Data Warehouse]] / [[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]] / [[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]] / [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]] - 概念: [[並列データベース]] / [[シェアードナッシング]] / [[一貫性ハッシュ法]] / [[分散ストレージ]] / [[専用データベースシステム]] / [[Zonemap]] / [[列指向OLAPデータベース]] / [[マルチテナンシーのためのシャーディング]] / [[二次インデックスのシャーディング戦略]] - エンティティ: [[David DeWitt]] / [[Jim Gray]] / [[Teradata]] / [[University of Wisconsin-Madison]] / [[Snowflake Computing]] / [[Retriever]] / [[Honeycomb.io]] / [[ClickHouse]] / [[Apache Cassandra]] / [[Riak]] ## 出典 - [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]]（ラウンドロビン・ハッシュ・レンジの 3 手法を並列 DB のコア技術として体系化） - [[@2016__SIGMOD__The Snowflake Elastic Data Warehouse]]（インデックスの代わりに min-max プルーニングを用いる不変ファイル分割の産業実装例） - [[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]]（到着順追記+セグメントタイムスタンプメタデータによる時間ウィンドウ・パーティショニング） - [[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]]（PARTITION BYによる、クエリプルーニングよりむしろTTLライフサイクル操作単位としてのパーティション設計） - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]]（キーレンジ/ハッシュの2系統への再編、固定シャード数方式によるリバランシングとパーティション境界の分離） - [[@2021__OReillyJapan__詳説 データベース - Chapter 13 分散トランザクション]]（§13.6 レンジ/ハッシュパーティショニング、§13.6.1 コンシステントハッシュ法の K/n 再配置原則）