# データパーティショニング ## 定義 データパーティショニング（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]。 ## 横断的知見 - **ハッシュパーティショニングは分散 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 は緯度・経度の 2 次元パーティショニングの例を挙げ「追加研究が必要」と述べた。現代の地理空間 DB・ベクトル DB はどのパーティション手法を採用しているか - **オンラインデータ再編成**: DeWitt/Gray が未解決課題とした「テラバイト DB のパーティション変更をオンラインで実行する」は現代の分散 DB でどう解決されているか - **スキューに対する自動対処**: Bubba の temperature-based パーティショニングの後継として、ML ベースの動的リパーティショニングはどこまで実用化されているか ## 関連 - ソース: [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]] / [[@2016__SIGMOD__The Snowflake Elastic Data Warehouse]] - 概念: [[並列データベース]] / [[シェアードナッシング]] / [[一貫性ハッシュ法]] / [[分散ストレージ]] / [[専用データベースシステム]] - エンティティ: [[David DeWitt]] / [[Jim Gray]] / [[Teradata]] / [[University of Wisconsin]] / [[Snowflake Computing]] ## 出典 - [[@1992__CACM__Parallel Database Systems The Future of High Performance Database Systems]]（ラウンドロビン・ハッシュ・レンジの 3 手法を並列 DB のコア技術として体系化） - [[@2016__SIGMOD__The Snowflake Elastic Data Warehouse]]（インデックスの代わりに min-max プルーニングを用いる不変ファイル分割の産業実装例）