データ基盤

列指向データベースは、なぜ大きな表を速く読めるのか

2026/10/5 シリーズ「データ基盤はなぜ作り直されてきたか」 第3回 / 全4回

🤖 AIが執筆しています

行ごとに保存すると集計は使わない列まで読み、行を一つずつ処理する実行は一行ごとの手間を払う

データを一行ごとにまとめて保存する形を行指向、列ごとにまとめて保存する形を列指向と呼ぶ。行指向の利点と限界を、列指向のデータベース C-Store を作った Stonebraker らは 2005 年の論文で整理した¹。行ごとの保存では、一回のディスクへの書き込みで一行の全部の項目を書けるので、書き込みが速い。著者らはこれを「書き込みに最適化した」形と呼び、データウェアハウスには逆に「読み込みに最適化した」形が要ると論じた。CPU の速さはディスクの読み出しの速さよりずっと速く伸びているので、豊富な CPU の計算を使ってでも、不足するディスクの読み出し量を減らすほうが得だ、というのが著者らの考えである。

遅さの原因は、読む量だけではない。Boncz らは 2005 年の論文で、TPC-H の 1 番目の問い合わせ（大量の明細を読んで集計する）を MySQL で動かしたときの時間の内訳を測った²。足し算や掛け算のような実際の計算に使われた時間は、全体の 10% だった。28% は集計に使うハッシュ表（値から格納先を引く作業用の表）の作成と探索に、残りの 62% は一行のデータの中から項目を取り出してコピーする処理に使われていた。著者らは原因を、行を一つずつ取り出して解釈しながら処理する実行の仕組みにあるとした。この手間は保存の形ではなく実行の仕組みから来る。著者らが作った MonetDB/X100 は、多数の値をまとめて処理する方式で、同じ問い合わせを MySQL の約 50 分の 1 の時間で終えた。ただし、これは二つの別々のデータベースの比較であり、保存の形だけの差ではない。同じ論文は、列ごとに保存した X100 のままでも、一度に処理する値を 1 個に絞ると MySQL と同じく解釈の手間を強く受けて遅くなり、まとめる数を増やすと時間が急に縮むことも示した。

列ごとに並べると読む量が減り、圧縮したまま計算できる

列ごとに並べると、圧縮が効きやすくなる。Abadi らは 2006 年の論文で、列ごとの保存では隣り合う値が互いに似ているので、行ごとの保存より圧縮の機会が大きく増えると書いた³。同じ値が続く部分を「値と続く数」の組で表すランレングス符号化では、ある列に 42 という値が 1000 回続くなら、合計を求める処理は 42 と 1000 を掛けるだけで済み、元の 1000 個の値に戻す必要がない。同じ論文は、圧縮したまま計算する方式が、元に戻してから計算する方式より速いことを測った。一方で、データに合わない圧縮の方式を選ぶと、圧縮しない場合より 1 桁遅くなる例も示している。どの圧縮が効くかは、データの並びと問い合わせで決まる。

列ごとに並べる利点は、保存の形だけからは得られない。Abadi らは 2008 年の論文で、行ごとに保存するデータベースの中で列ごとの保存をまねる方法を試した⁴。表を列ごとの小さな表に分ける方法と、全部の列に索引を付ける方法である。星形の表を使う性能測定（Star Schema Benchmark、規模 10）で、列ごとに保存する C-Store は平均で約 4 秒、まねた方法は 80 秒から 220 秒かかり、何もしない行ごとの保存のほうが、まねた方法の最良の結果より平均で約 3 倍速かった。著者らは遅さの原因を、分けた小さな表の一行ごとに付く管理用の情報で読む量がかえって増えたことと、分けた列から行を組み立て直す費用が大きかったことに求めた。ただし約 4 秒との差は別々のデータベースの比較で、著者ら自身が絶対値の差を読みすぎないよう断っている。

著者らは C-Store の各技術の効き目も測った。結果の行を最後の段階まで組み立てない工夫が約 3 倍、圧縮が平均で約 2 倍（並べた列では約 10 倍）、値をまとめて処理する工夫などが約 1.5 倍だった。著者らは、まねることが不可能だとは言わず、行ごとのデータベースが列ごとの保存の利点を十分に得るには、保存の層と実行の仕組みの両方を変える必要があると結論している。

製品になった後の数字もある。C-Store の考え方を製品にした Vertica の開発者は 2012 年の論文で、ある顧客の計測データ 2 億行を例に挙げた⁵。カンマで区切った文字のファイルでは一行 32 バイト（合計 6,200 MB）、gzip で圧縮すると 1,050 MB、列ごとに並べ替えて圧縮した Vertica では 418 MB で、一行あたり約 2 バイトになった。この数字は開発元自身の報告である。

多数の機械に分けて読むと速くなるが、偏りと転送が速さを削る

一台の機械で読める量には限りがある。DeWitt と Gray は 1992 年の論文で、多数の機械で一つのデータベースを動かす設計を整理した⁶。各機械が自分のディスクとメモリを持ち、何も共有しない形を、シェアードナッシングと呼ぶ。表の行は各機械のディスクに分けて置かれ、各機械が自分の分を並列に読む。この形では、各機械が自分のディスクを手元で読み、ネットワークには主に問い合わせと各機械で絞り込んだ結果を流す。ただし後で述べるように、結合のために行を機械の間で送り直すこともある。この設計を大規模に並列化したデータベースを、MPP（大規模並列処理）のデータベースと呼ぶ。シェアードナッシングは、列ごとの保存より前から行ごとのデータベースで使われてきた設計で、列指向とは別の軸である。現在の分析用データベースの多くは、この二つを組み合わせている。

二人は、機械を N 倍にしたとき同じ仕事が N 倍速くなることを線形のスピードアップと呼び、それを妨げる要因を三つ挙げた⁶。並列の処理を始めるまでの時間、共有する資源を取り合うことによる遅れ、そして仕事の偏り（スキュー）である。偏りについて二人は、仕事全体の時間は最も遅い部分の時間で決まると書き、結合で多くの行が同じ値を持つ極端な場合には、速くする方法は知られていないとした。

現在の製品も、同じ制約を利用者に課している。Amazon Redshift の文書によれば、各行をどの機械に置くかを決める列（分散キー）を利用者が選ぶこともでき（現在の既定は自動の選択）、データが偏ると一部の機械が他より多くの仕事をして性能が落ちると書く⁷。結合のために行を機械の間で送り直すことが、問い合わせの費用の大きな部分を占めることもあるという。

Airbnb の技術ブログは 2013 年に、Redshift を試した結果を報告した⁸。30 億行の表に対する範囲の問い合わせは、それまで使っていた Hive で 28 分、Redshift で 6 分未満だった。二つの結合を含む問い合わせは、182 秒から 8 秒になった。比べた二つの環境は機械の台数も種類も違い、Redshift は 16 台、Hive は 1 台あたりの CPU とメモリがより大きい 44 台だった。著者自身も予備的な実験と書いている。同じ記事は、分散キーは一つしか指定できず、複数の列で大きな結合をすると遅くなること、数十億行の大きな結合はなお長くかかり、それには Hadoop に戻るつもりであることも書いている。

列ごとに保存する代わりに、一行ずつの書き込みと特定の行の取り出しを手放す

列ごとに並べた形は、一行を書き込むのが苦手である。一行の値は、列ごとに別々の場所に分かれて置かれる。C-Store の論文によれば、入った順に並べておけば末尾への挿入は効率よくできるが、検索に向く別の順に保つと挿入が非常に難しく高くつく。C-Store は検索に向く順を選び、書き込み用の小さな領域で新しい行を受け、後でまとめて読み込み用の領域へ移す構成を取った¹。C-Store の論文が示した数字は読み込みだけの測定で、著者ら自身が非常に予備的だと書いている。

行ごとのデータベースの側からの応答もある。Microsoft の Larson らは 2011 年の論文で、行ごとに保存する SQL Server に、列ごとに保存する索引を加えた⁹。1 TB の TPC-DS の一つの問い合わせで、この索引と行をまとめて処理する新しい演算は、実行を 10 倍（キャッシュに載った状態）から 25 倍（載っていない状態）速くした。この数字も、開発元が自社の製品について示したものである。同じ論文は、この索引が特定の行の取り出しや範囲の読み出しには向かず、そうした問い合わせでは行ごとの保存が引き続き有利だと書く。最初の版では、この索引を持つ表を直接更新することもできなかった。

行ごとの保存が勝つ条件も測られている。Harizopoulos らは 2006 年の論文で、保存の形以外を同じにした二つのデータベースを作って比べた¹⁰。ディスクの読み出しが速さを決める既定の構成では、一行の幅の 85% を超える列を読む問い合わせで、列ごとの保存のほうが遅くなった。列ごとの保存は、列と列の間でディスクの読み出し位置を移す必要があるからである。CPU が速さを決める条件では、一行の幅が狭く、絞り込みの効かない問い合わせで、行ごとの保存が勝つ場合もあった。ただし著者らは、適切な先読みがあれば列ごとの保存はほぼ常にディスクの読み出しをよく使え、CPU の面で劣るのは限られた状況だと結論している。圧縮したまま計算する工夫や X100 のような値をまとめて処理する工夫といった他の利点が無くても、列ごとの保存は今後さらに有利になると見ている。Redshift の文書も、一度に一行か数行の全項目を読み書きする業務の処理には、行ごとの保存が最適だと書く⁷。

列ごとに保存する考え方は、データベースの外にも広がった。Google は 2010 年の論文で、入れ子になったデータを列ごとに保存して読む Dremel を発表し、読む列が少ないときは列ごとの保存が約 1 桁速く、有利さが逆転する点は多くの場合で数十の列のあたりにあると報告した¹¹。ファイルの形式である Parquet は、Dremel の論文の方法で入れ子のデータを列に分けると、自らの仕様に書いている¹²。列ごとに並べる考え方は、データベースの中の工夫から、ファイルの形式そのものになった。

この記事はAIが執筆しています。内容には誤りが含まれる可能性があります。ご注意ください。