Rows vs Columns: How different are they, really?
Rows vs. Columns: How different are they, really? (spiraldb.com)
要約
この記事では、データベースにおける行指向ストレージ(Row Store)と列指向ストレージ(Column Store)の根本的な違いを解説しています。行指向は個々のレコードへのアクセスや更新に適していますが、列指向は大量のデータを集計・分析するクエリ(OLAP)において、必要な列のみを効率的に読み込み、ベクトル化実行や圧縮などの最適化を可能にすることで、大幅なパフォーマンス向上をもたらします。このストレージ形式の選択は、データベースの設計思想や得意とするワークロードに深く影響します。
全文翻訳
Rows vs Columns: How different are they, really?
Connor Tsui
Published Nov 11, 2026 · 12 min read
構造化データについて考えるとき、私たちは一般的に行単位で考えます。ニューヨーク市のシェアサイクルアプリの走行データを記録した、このシンプルなCSVファイルを見てみましょう。
ride_id,started_at,ended_at,start_area,end_area,bike_type,duration_min
1001,2023-01-01 00:00:00,2023-01-01 00:05:00,1,2,classic,5
1002,2023-01-01 00:01:00,2023-01-01 00:10:00,2,3,electric,9
1003,2023-01-01 00:02:00,2023-01-01 00:07:00,1,3,classic,5
1004,2023-01-01 00:03:00,2023-01-01 00:15:00,3,2,electric,12
このCSVファイル内のデータは行単位で整理されており、各行はデータのレコードに対応します。ここでの各レコードは1回のライド、つまり「モノ」であり、それに関するすべての情報が1行にまとめられています。スプレッドシート、JSONオブジェクト、配列内のC言語スタイルの構造体、SQLテーブルなどを考えてみてください。私たちはほとんどどこでもデータをこのように整理する傾向があります。なぜなら、それは私たちの思考様式に合致するからです:一つの「モノ」と、その「モノ」に関するすべての詳細です。
この考え方は、私たちが書く多くのソフトウェアに適合します。アプリにログインしたり、動画にコメントを投稿したり、ショッピングカートに商品を追加したり、銀行送金をしたり、ライドを予約したりするとき、アプリケーションは1つのレコード(または最大でも数個)を変更するだけです。そのため、PostgresやMySQLのようなデータベースも行を中心に「考え」、つまり行を中心にモデル化されているのは理にかなっています。それらは各レコードの詳細をまとめて保持するため、レコードを見つけたり、更新したり、作成したりすることは、1つの場所に行くことを意味します。
しかし、データベースに求めることがすべて1つのレコードに限定されるわけではありません。
もし上記のCSVファイルを生成したシェアサイクルサービスを実行しているなら、最終的には収集したすべてのデータから何かを学びたいと思うでしょう。この種の作業は分析と呼ばれます。例えば、月曜日と金曜日の午前中に最も賑わう地域はどこか?電動自転車のライドはクラシック自転車のライドよりも時間がかかるか?これらの質問には単一のレコードでは答えられないことに注意してください。回答はデータセット全体から得られるため、それらを得る唯一の方法はすべてのレコードを見ることです。[1]
しかし、これらの質問で必要とされないものに注目してください。最も賑わう地域を見つけるには、start_areaとstarted_atの列だけが必要であり、自転車の種類を比較するにはbike_typeとduration_minだけが必要です。各質問はすべての行を見る必要があるかもしれませんが、各行から数個の列しか必要としません。そして、各レコードの詳細をまとめて保持するデータベースは、その利点を活かすことができません。2つの列を読み取るために、5つすべてを読み取る必要があります。私たちは行単位で考えるかもしれませんが、これらの質問に迅速に答えるためには、列単位でプログラムする必要があります。
列単位でのプログラミングはデータの保存方法から始まりますが、それは始まりに過ぎません。データが列単位で保存されると、データベースがクエリを実行する方法は劇的に変化します。読み取るデータの量、一度に処理する値の数、CPUが1つの命令で処理できる値の数、データの圧縮効率などが変わります。
この記事ではこれらの変化について説明します。最後まで読めば、列単位でデータを保存するという「単純な」選択から、どれほど多くのことが派生するかを理解できるでしょう。
行ストアと列ストア
何が変わらないかから始めましょう。データベースが行を保存するか列を保存するかに関わらず、SELECT * FROM rides;を実行したときに表示されるテーブルは同じです。同じSQLで作成し、同じSQLでクエリを実行し、同じ結果を得ます。この2つのテーブルは論理的に同等であると言えます。
行と列の違いは論理的な区別ではなく、物理的な区別です。データは同じものを表現しますが、そのデータがメモリやディスク上に実際に配置される方法は異なります。
データベースはその選択したグループ化にちなんで名付けられます。行ストアは、私たちが最初に見たCSVファイルのように、各レコードの値をお互いの隣に保持します。前述のPostgresやMySQLは、どちらも行ストアです。それらはアプリケーションの背後にある小規模な読み書き、つまりオンライン・トランザクション処理(OLTP)[2]のために構築されています。
列ストアは逆のことを行います。各レコードを分解し、各列の値を互いの隣に保持します[3]。DuckDBやClickHouseは列ストアの例です。それらは分析のために構築されており、オンライン・アナリティカル処理(OLAP)[4]と呼ばれます。
メモリ内の行と列
具体的にするために、ライドデータを自分たちでメモリに保持する必要があると想像してみましょう。これは実際のデータベースの実装方法ではありませんが、各レイアウトがデータをどのように配置するかをよく近似しています。Rustでは、行ストアは構造体のVecになります。
struct Ride {
ride_id: u64,
started_at: u64, // Unix timestamp
ended_at: u64, // Unix timestamp
start_area: String,
end_area: String,
bike_type: u8, // 0 for classic, 1 for electric
duration_min: u32,
}
let rides: Vec<Ride> = ...;
列ストアは同じフィールドを持ちますが、Vecの構造体のように見えます。
struct Rides {
ride_ids: Vec<u64>,
started_ats: Vec<u64>,
ended_ats: Vec<u64>,
start_areas: Vec<String>,
end_areas: Vec<String>,
bike_types: Vec<u8>,
duration_mins: Vec<u32>,
}
let rides: Rides = ...;
これらのデータレイアウトを並べて表示すると、以下のようになります。
Rows layout:
[Ride { ride_id: 1001, ..., duration_min: 5 }, Ride { ride_id: 1002, ..., duration_min: 9 }, ...]
Columns layout:
Rides {
ride_ids: [1001, 1002, ...],
started_ats: [..., ...],
duration_mins: [5, 9, ...],
...
}
これら両方の形式は同じ論理値を表しますが、そのレイアウトは劇的に異なります。
必要な列のみを読み取る
楽しい演習をしましょう[5]。これらは上記の2つのSQLクエリです。どちらのレイアウトがそれぞれの実行に適しているでしょうか?
AVGクエリの場合、それを計算するにはすべてのライドのduration_minのみが必要で、それ以外は何も必要ありません。Columnsレイアウトでは、値は単一のVec<u32>にまとめて保存されているため、クエリはその配列だけをスキャンでき、他の4つには触れません。Vec<Ride>(Rowsレイアウト)の場合、期間だけを読み取る方法はまったくありません。各期間はRide内に保存されているため、クエリはすべてのRideを読み取り、毎回他の4つのフィールドをスキップする必要があります。
コードはそれらの他のフィールドを「無視」できるかもしれませんが、ハードウェアはできません。CPUはメモリを一度に1つの値ずつフェッチするわけではありません。固定サイズのブロックをキャッシュライン(ほとんどのマシンでは64バイト[6])としてフェッチし、プログラムが数バイトしか必要としない場合でも、ライン全体をフェッチします。Rideは48バイト[7]で、duration_minはそのうちの4バイトにすぎません。そのため、行レイアウトでは、それらの4バイトを読み取るために48バイトすべてをフェッチする必要があり、実際に必要な量の12倍になります。CPUはこれらのラインをスキップすることもできません。なぜなら、Rideはキャッシュラインよりも小さいため、配列の各キャッシュラインにはどこかに期間が含まれているからです。
この図は簡単のために8回のライドのみを示していますが(そのためduration_minの行は半分空いています)、12倍という係数はテーブルのサイズに依存しません。100万回のライドがあった場合、48MB対4MBをフェッチすることになるかもしれません。
2番目のクエリは逆です。SELECT * FROM rides WHERE ride_id = 1004は、単一のライドのすべてのフィールドを求めており、1つだけではありません。データベースがそのライドを持つレコードを見つけると(おそらくインデックス[8]経由で)、Vec<Ride>はすべてのフィールドが互いに隣接しているため、それらすべてを読み取ることは1つか2つのキャッシュラインにしか触れません(2つのキャッシュラインにまたがる可能性があります)[9]。一方、Columnsは同じライドを5つの異なる配列に分散させているため、クエリはそれを再構築するために少なくとも5つのキャッシュラインをフェッチする必要があります。このクエリでは、Rowsレイアウトが勝ちます。
これで何が扱えるかについてより良いアイデアが得られたので、列指向データに対するクエリを高速化する方法についてもう少し深く掘り下げてみましょう!分析データ処理は数十年にわたる活発な研究分野であり、すべての最適化を網羅することはできません。それにもかかわらず、この記事の残りの部分では、ほとんどの最新の分析データベースシステムが利用している技術の概要を説明します。
ベクトル化実行
SELECT AVG(duration_min) FROM rides;を実行する最も簡単な方法は、一度に1つのライドを処理することです。ライドを取得し、その期間を追加し、最後に列の長さで割ります。しかし、列ストアが必ずしもこの方法で実行する必要はありません。すべての期間が1つの連続した配列に格納されているため、数千の値のバッチで処理できます。各バッチはCPUキャッシュに収まるのに十分な小ささです[10]。これはベクトル化実行[11]と呼ばれます。
しかし、なぜバッチが一度に1つの値よりも速いのでしょうか?これを理解するには、まずデータベース実行エンジンがこれらのクエリを実際にどのように実行するかを理解する必要があります[12]。
データベースは任意のクエリを実行できる必要があるため、オペレーターと呼ばれる汎用的なピースで各クエリを構築し、計画します。例えば、列を読み取るオペレーター、フィルターを実行するオペレーター、合計を計算するオペレーターなどがあるかもしれません。オペレーターが一度に1つのRideを渡す場合(これはVolcanoモデル[13]と呼ばれます)、データベースは各ライドごとに、次に実行するオペレーター、必要な列、その列の型を特定する必要があります。このすべての管理と解釈のコストは、合計自体よりもはるかに多くの時間を消費する可能性があります[14]。バッチを使用すると、値ごとではなくバッチごとに管理コストを1回だけ支払えばよく、実際の作業は配列に対するタイトなループになります。
では、なぜ数千の値で止まるのではなく、列全体を一度に処理しないのでしょうか?オペレーターは結果を互いに渡すため、結果の小さなバッチは次のオペレーターがそれを取得するまでCPUキャッシュに留まることができます。列全体のサイズの結果は通常CPUキャッシュに収まらないため、CPUはそれをメインメモリに書き戻し、再度読み込む必要があります。
私たちのクエリの場合、各バッチでの作業は単一のループです。
let mut sum = 0u64;
for batch in batches {
for duration in batch {
sum += duration as u64;
}
}
ベクトル化実行がより良いキャッシュ局所性を持つことに加えて、データ並列操作でクエリの実行を高速化できます。最新のCPUは、単一命令、複数データ(SIMD)と呼ばれる、一度に複数の値に操作を行う命令を持っています。それらは、値が同じ型でメモリ上に連続している場合に最も効果的に機能しますが、これはまさに列のバッチがそうである状態です。
したがって、コンパイラが上記のforループを見ると、それ自体でSIMD命令を発行できます。これは自動ベクトル化 [15]と呼ばれる技術であり、LLVMのようなコンパイラバックエンドでよくサポートされています[16]。
AVX-512(一度に512ビットをロードできる)を使用すると、1つのvpaddq命令が一度に8つの64ビット期間を加算します[17]。vpaddqがそれら8つの期間を互いに加算するのではなく、64ビットの8つのスロットを持つ512ビットレジスタがあり、各スロットは独自の実行中の合計を保持します。最初の期間は最初スロットに、2番目の期間は2番目のスロットに、というように追加されます。ループの後で、最終的な合計を得るためにスロットを加算します(以下の図は最後のステップを省略しています)。
; LLVM IR and AVX-512 assembly
; Note that the code can "ignore" those other fields, but the hardware cannot. A CPU doesn't fetch memory one value at a time: it will fetch fixed-size blocks called *cache lines* (which are 64 bytes on most machines[6]), fetching the whole line even when the program needs only a few bytes of it. A `Ride` is 48 bytes[7] and `duration_min` is only 4 of them, so with the row layout, we have to fetch all 48 bytes to read those 4, which is 12x the amount that we actually need. The CPU can't skip any of these lines either because a `Ride` is smaller than a cache line, so every cache line of the array has a duration somewhere in it.
; This diagram only shows 8 rides for simplicity (which is why the `duration_min` line is half empty), but the factor of 12 doesn't depend on the size of the table. With one million rides, we might be fetching 48 MB vs 4 MB.
; The second query goes the other way. `SELECT * FROM rides WHERE ride_id = 1004` wants *every* field of a single ride, not just one. Once the database finds the record with that ride (probably via an index[8](https://en.wikipedia.org/wiki/Database_index)), `Vec<Ride>` has all of its fields next to each other, so reading all of them touches only one or two cache lines (it might overlap two cache lines).[9](https://spiraldb.com/blog/rows-vs-columns#user-content-fn-string-text) On the other hand, `Columns` has spread the same ride over five different arrays, so the query has to fetch at least five cache lines to put it back together. For this query, the `Rows` layout wins.
; This is the output of `rustc` 1.99.1 with `-C opt-level=3 -C target-feature=+avx512f`, with the attributes, metadata, and assembler directives removed.
; Note that the compiler keeps four registers of running sums (`zmm0` to `zmm3` in the assembly) instead of one. This is a separate optimization from SIMD called *loop unrolling*:[18](https://spiraldb.com/blog/rows-vs-columns#user-content-fn-unrolling) the 8 slots in each register come from SIMD, and the four registers come from the compiler doing four steps of the loop in every pass. Together, every pass of the loop adds 4 × 8 = 32 durations.
; This is the optimized LLVM IR:
; ... (LLVM IR omitted for brevity)
; This is the x86-64 assembly that LLVM generates:
; ... (Assembly omitted for brevity)
コンパイラは、1つのレジスタではなく4つの実行中の合計レジスタ(アセンブリではzmm0からzmm3)を保持します。これはSIMDとは別の最適化であるループ展開 [18]です。各レジスタの8つのスロットはSIMDから来ており、4つのレジスタはコンパイラがループの4ステップを各パスで実行することから来ています。合計すると、ループの各パスは4 × 8 = 32の期間を加算します。
自動ベクトル化は合計だけに限られるわけではありません。クエリを実行する時間の多く(特に比較的単純なクエリ)は、このようなバッチに対するタイトなループで費やされており、コンパイラは手動でSIMD命令を記述することなく、同様の方法で多くをベクトル化できます。
圧縮
これまでは、メモリ上にあるデータのみを見てきました。ほとんどのデータベースシステムでは、データは永続ストレージ(ディスク、SSD、またはS3のようなオブジェクトストレージ)に存在し、それをメモリにロードすることがクエリ実行のボトルネックとなることがよくあります(つまり、クエリはI/Oバウンドです)。したがって、データのサイズは非常に重要です。クエリが読み取るバイト数が少なければ少ないほど、I/Oを待つ時間は短くなります。
データを小さくする最も単純な方法は、各ブロックを取得し、汎用圧縮アルゴリズムで実行することです[19]。この種の圧縮は、zipファイルに触れたことがある人なら誰でも知っているはずです!それはデータをバイトの大きな山として扱い、それらのバイトが実際に何を意味するかを気にしないため、すべて(行と列の両方)で機能します。
問題は、この種の圧縮は「ブラックボックス」であるということです。ブロックが圧縮されると、データベースはそれ以上中を見ることができません。例えば、zipされたCSVファイルの100万行目を読み取りたい場合、その行に直接ジャンプする方法はないため、単一の行にアクセスするためにそれより前のすべてを解凍(非圧縮)する必要があるでしょう[20]。データの任意の1つの部分を、残りの部分を読み取らずに読み取る能力はランダムアクセスと呼ばれ、この種の圧縮は高速なランダムアクセスをサポートできません。
データベースシステムは、ブラックボックスで圧縮されたデータブロックでも同様の問題を抱えます。ライド1004の期間を読み取るために、そのライドが含まれるブロック全体(場合によっては複数のブロック!)を解凍する必要があります。
これも列が役立つ場所です。列の値はすべて同じ型を持ち、互いに似ている傾向があるため、列は行よりもはるかにうまく圧縮できます。例で既にこれを見ることができます。start_areaには3つの異なる値しかなく、bike_typeには2つしかなく、ride_idは常に増加しています。
さらに重要なのは、ブラックボックス圧縮を使用する必要がまったくないことです。代わりに、軽量エンコーディングを使用できます。これは、データの構造と意味を保持しながらデータを圧縮する単純なスキームです[21]。列をバイトの大きな山に変えるのではなく、軽量エンコーディングはその列にある特定のパターン(例えば、異なる値が少ない列、またはすべて小さい数値の列)を利用して、同じ値をより少ないスペースに保存します。
構造を保持することは、ランダムアクセスを維持できることを意味します。ほとんどの軽量エンコーディングでは、データベースシステムは、周囲のすべてをデコードせずに目的の値に直接ジャンプできます。
意味を保持することも役立ちます。軽量エンコーディングはブラックボックス圧縮よりも「軽量」ですが、デコードにはCPU時間が必要なため、無料ではありません。しかし、エンコードされた値は依然として意味を持つため、クエリは多くの場合、最初にデコードせずにエンコードされたデータで直接作業を行うことができ、そのコストの多くをスキップできます。圧縮データでのこの計算は、「遅延マテリアライゼーション」[22]の一種です。
これはまさに、私たちがVortexを構築した方法です。Vortexはオープンソースの拡張可能な列指向ファイルフォーマットおよびデータ処理ライブラリです。これは多くの軽量エンコーディングを備えており、それらを積み重ねてデータをさらに小さくすることができます。
これがどのように機能するかについて、私たちは多くのことを書いてきました。他のブログもチェックしてください!
- Vortex: One Format for Any Shape Vortexの仕組みの概要
- FastLanes 整数について
- ALP 浮動小数点数について
- FSST 文字列について
- BtrBlocks 各列のエンコーディングの選択について
- Push-down compute 圧縮データでの作業について
- [LIKE] on compressed strings](https://spiraldb.com/blog/pattern-matching-strings-without-decompression) 非圧縮での文字列パターンマッチングについて
列単位で考える
CSVファイルからのデータと、行か列かの「単純な」1つの選択から始めました。それでも、その選択からどれほど多くのことが派生するか、そしてどちらか一方を選択した場合の結果を目の当たりにしました[23]。
その結果が、ほとんどのデータベースシステムがトランザクションまたは分析のいずれかのために構築されており、両方のためではない理由です[24]。データベースがクエリを実行する方法と、データを圧縮する方法は、この1つの選択の上に構築されているため、システムが後で切り替えられるものではありません。列ストアが分析クエリを提供する上での強みは、まさに1つのレコードを一度に読み書きすることに対してそれを悪くするものであり、行ストアではその逆が当てはまります。
また、列指向データには、単一の入門記事に収まる以上のことがたくさんあります。例えば、列ストアが永続ストレージ上でどのようにデータを整理するか[25]、クエリが必要としないデータをどのように読み取らないようにするか[26]、ベクトル化実行だけがクエリをより効率的に実行する方法ではないこと[27]、そしてデータの書き込みや変更については完全に無視しました![28]これらのトピックのそれぞれが、活発な研究の全領域です。さらに進みたい場合は、CMUのデータベースコースが素晴らしい出発点であり、それらの講義はすべてオンラインで無料で見ることができます[29]。
将来的には、Spiralでの仕事でこれらのトピックに多く関わるため、このようなトピックについてさらに投稿したいと考えています!
フットノート
- 実際には、データベースはインデックスや各データブロックの最小値と最大値(ゾーンマップ)を使用して、必要のないレコードをスキップできることがよくあります。しかし、論理的には、回答は依然としてすべてのレコードに依存します。 ↩︎
- 銀行振込や航空券予約のようなものを考えてみてください。大量の小さな操作(トランザクション)が数個のレコードを読み書きし、すべてが並行して発生し、おそらく1秒あたり数千回発生します。 ↩︎
- このアイデアは、それらのシステムのどちらよりもはるかに古いものです。A Decomposition Storage Model(SIGMOD 1985)は、各列を独自に保存することを既に提案していました。CMU 15-445のストレージモデルに関する講義ノートは、これら2つのレイアウトをより詳細に比較しています。 ↩︎
- これらは一般的に、データセットの大部分を読み取り、通常は数個の列のみに関心があり、カウント、合計、平均でデータを要約するクエリです。 ↩︎
- 個人的には、これらは楽しいと思います... ↩︎
- AppleのMシリーズチップは128バイトのキャッシュラインを使用しますが、ポイントは同じです。 ↩︎
- これは、
ride_idとstarted_at(64ビットタイムスタンプ)がそれぞれ8バイト、String(テキストへのポインタ、長さ、容量)が24バイト、bike_typeが1バイト、アライメントのためのパディングが3バイト、duration_minが4バイトです。start_areaの24バイトはRustのStringに固有のものであることに注意してください。実際のデータベースは文字列を異なる方法で保存します。また、Rustは構造体のフィールドの順序を自由に変更できますが、#[repr(C)]を追加しない限り、rustc1.99.1はstart_areaを先頭に、パディングを末尾に移動します。どちらの場合でも構造体は3バイトのパディングで48バイトのままなので、記述した順序でフィールドを描画します。 ↩︎ - インデックスは、個別のデータ構造(通常はB+ツリー)であり、「キー」(通常は一意の主キー)を
1004のような値として、格納されているレコードの場所にマッピングします。これにより、データベースはテーブル全体をスキャンして検索するのではなく、データを迅速に見つけることができます。詳細については、CMU 15-445のインデックスに関する講義ノートを参照してください。 ↩︎ - これらのカウントには
start_areaのテキストは含まれていません。Stringの24バイトはテキストへのポインタのみであり、テキストはメモリの別の場所に存在するため、実際の地域名の読み取りには少なくともさらに1つのキャッシュラインが必要です。これはどちらのレイアウトでも同様ですが、どちらが勝つかという点には影響しません。 ↩︎ - MonetDB/X100(この設計を導入したシステム)は、デフォルトでバッチあたり1024値を使用します。DuckDBは2048、DataFusionは8192を使用します。 ↩︎
- また、実際のデータベーステーブルは、データがメモリよりも大きい場合、通常は永続ストレージ(HDD、SSD)上に存在するため、データベースはたとえ望んだとしても列全体を一度にロードすることはできません。したがって、クエリはいずれにしても列を断片的に読み取る必要があります。 ↩︎
- CMU 15-445のクエリ実行に関する講義ノートはさらに詳しく説明しており、CMU 15-721のクエリ処理とベクトル化実行に関するノートはさらに踏み込んでいます。 ↩︎
- 90年代初頭のGoetz GraefeによるクエリエンジンVolcanoにちなんで名付けられました。これは「イテレータ」モデルとも呼ばれ、ほとんどすべての行ストアは依然としてこの方法でクエリを実行します。 ↩︎
- ベクトル化実行はMonetDB/X100: Hyper-Pipelining Query Execution(CIDR 2005)に由来します。この論文はMySQLを分析クエリでプロファイリングし、実際の作業を行う操作が実行時間の約10%しか占めないことを発見しました。X100は、各オペレーターを値の小さなベクトルで実行しました。これが名前の由来です。 ↩︎
- ベクトル化実行はデータベースが値をバッチで処理することであり、自動ベクトル化はコンパイラがSIMD命令を発行することに注意してください。これらは別個ですが似たような考え方です。 ↩︎
- ただし、自動ベクトル化は壊れやすいです。もし
duration_minが浮動小数点数だった場合、LLVMはデフォルトではこの合計をベクトル化しません。一度に8つの値を加算すると加算の順序が変わりますが、浮動小数点数の加算は結合法則を満たさないため、結果が変わる可能性があります。 ↩︎ - 8ではなく16なのは、32ビットの各期間が64ビットに拡張されるため、合計がオーバーフローしないようにするためです。 ↩︎
- ここでのループ展開は役立ちます。なぜなら、各
vpaddqは同じレジスタに書き込んだ前のvpaddqを待つ必要があるため、レジスタが1つしかない場合、加算は逐次実行されることになります。4つの独立したレジスタがあれば、CPUはそれらのいくつかを同時に実行できます。 ↩︎ - zipファイルはDEFLATEというアルゴリズムを使用しています。データベースは一般的にZstandardやLZ4のような新しいものを使用しますが、アイデアは同じです。 ↩︎
- これは少し嘘です。通常のCSVファイルには実際のランダムアクセスがありません。なぜなら、行の長さが異なるため、100万行目がどこから始まるかを数えずに知ることはできないからです。より良い例は、期間の
Vec<u32>をブラックボックス圧縮することです。この場合、N番目の値は常にバイト4×Nで始まります。配列がブロックボックス圧縮されると、ランダムアクセスでベクトルにインデックスを付けることができなくなります。 ↩︎ - 軽量エンコーディングに関する最近の2つの論文は、The FastLanes Compression Layout(VLDB 2023)とBtrBlocks: Efficient Columnar Compression for Data Lakes(SIGMOD 2023)です。CMU 15-721のデータフォーマットとエンコーディングに関する講義ノート(パート1、パート2)は、実際のファイルフォーマットがこれらのエンコーディングをどのように活用しているかを示しています。 ↩︎
- この用語は列ストアの研究から来ており、実質的には行の列を再構築する(マテリアライズする)までできるだけ長く待つ(遅延)ことを意味します。Materialization Strategies in a Column-Oriented DBMSを参照してください。圧縮データでの計算は、値を解凍するまでできるだけ長く待つという同じアイデアを、より低いレベルで実現したものです。圧縮された列でクエリを実行することは、Integrating Compression and Execution in Column-Oriented Database Systems(SIGMOD 2006)まで遡りますが、Vortexはこの概念をさらに一歩進めています。 ↩︎
- Column-Stores vs. Row-Stores: How Different Are They Really?(SIGMOD 2008)は、ストレージを変更した場合に何が起こるかを調べています。 ↩︎
- 過去には、両方を実行できる1つのシステムを構築しようとする試みがありました(HTAP、またはハイブリッドトランザクション/アナリティカル処理)が、それらの試みは一般的にうまくいきませんでした。しかし、いくつかの新しいシステムがそのギャップを埋めているようです。CedarDB(TU Munichの研究システムであるUmbraの商用版)は、単一のエンジンと単一のデータコピーでトランザクションと分析を実行します。DatabricksのLakebaseは、トランザクションクエリのエンジンとしてPostgres(行ストア)を維持しますが、そのストレージレイヤーはバックグラウンドで同じデータを列指向フォーマットに書き換え、分析エンジンがそれをクエリできるようにします。 ↩︎
- ほとんどのフォーマットは、テーブルを大きな行のグループに分割し、各グループ内で列を別々に保存します(これは「行グループ」として知られています)。このアイデアは、Weaving Relations for Cache Performance(VLDB 2001)のPAXに遡り、今日のApache Parquetファイルが機能する方法です。An Empirical Evaluation of Columnar Storage Formats(VLDB 2024)は、これらのフォーマットが最新のハードウェアとワークロードでどの程度うまく機能するかを調べています。メモリ内の列(ディスク上ではなく)の場合、標準はApache Arrow列指向フォーマットです。 ↩︎
- 最も一般的なトリックは、各データブロックの最小値と最大値の「ゾーンマップ」を保持することです。これにより、クエリは特定のデータを含み得ないブロックを完全にスキップできます。これについてはZone maps, or “queries go brrr”で説明しました。 ↩︎
- もう1つの大きなアプローチは、各クエリをそのクエリ専用に最適化されたマシンコードにコンパイルすることです。Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask(VLDB 2018)は、これら2つのアプローチを比較しており、どちらも明確な勝者ではありません。 ↩︎
- 列ストアでは、単一の新しいレコードが各列に対して異なる場所に行く必要があるため、データの変更は高価になる可能性があります。C-Store(VLDB 2005)は、書き込みに適した小さなストアを、読み取りに適した大きなストアの隣に配置し、バックグラウンドでデータを移動させることでこれを処理します。 ↩︎
- CMU 15-445は入門コース(2025年秋の講義ビデオ)であり、CMU 15-721は上級コース(講義ビデオ)です。この投稿の著者は、これらの資料のほとんどをCMUのコースで学んだことに注意してください!もし読む方がよければ、The Design and Implementation of Modern Column-Oriented Database Systems(2013)は、この分野全体のサーベイです。 ↩︎