Citation

@inproceedings{10.1145/2213836.2213864,
author = {Alagiannis, Ioannis and Borovica, Renata and Branco, Miguel and Idreos, Stratos and Ailamaki, Anastasia},
title = {NoDB: Efficient Query Execution on Raw Data Files},
year = {2012},
isbn = {9781450312479},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/2213836.2213864},
doi = {10.1145/2213836.2213864},
booktitle = {Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data},
pages = {241–252},
numpages = {12},
keywords = {in situ querying, positional map, adaptive loading},
location = {Scottsdale, Arizona, USA},
series = {SIGMOD ’12}
}

どんなもの？

巨大なデータを扱うにあたって、 DB に読み込む（インポートする）という処理に時間がかかる。そこで、生のデータ、例えば CSV や、天文学の分野で使われる画像とメタデータの形式を、そのまま利用しようという取り組みの導入と、プロトタイプ実装の紹介。

Figure 1 を見るとわかりやすいが、 DB に読み込む時間を削減して、さらにクエリ実行中に、入力データに適応していくことで、その後のクエリを速くしていこうという思想。

先行研究と比べてどこがすごい？

従来の DBMS でも CSV ファイルの読み込み機能はあったが、簡易的なもので、ただ単に順番にデータを読んでいくことしかできなかった。本論文では、「NoDB」の指針（すべてのデータを DB に読み込ませずとも、 DBMS の持つクエリ実行エンジンを活用できる）を示し、実際に PostgreSQL に組み込んだ例を示した。

技術や手法のキモはどこ？

次の4点を実際に実装した。

  1. オンザフライ読み取り: CSV を例に挙げると、クエリ実行に必要となる列だけ真面目に読み取って、後は改行まで適当に読み飛ばせば CPU 時間を削減できる。
  2. 索引（Positional Map）: 最初に、クエリに使用するすべての行の必要な列の、生データにおける位置を記録しておく。これはキャッシュされる。該当列のデータを読み取りたいときや、別のクエリw実行して他の列の Positional Map が必要になったときは、この Positional Map を用いて生データ内からデータを読み取る。
  3. キャッシュ: 例えば CSV はすべて文字列だが、数値セルは数値として扱う必要があるように、データの変換が必要になる。生データへのアクセスを減らす目的と、データの変換を減らす目的のため、読み取ったデータはキャッシュしておく。
  4. 統計: DBMS は、テーブルにどのようなデータが含まれるかの統計を持っており、これによってクエリ実行計画を作成する。本実装では、クエリ実行中に参照した列について、統計データを作成しておくことで、その後のクエリ実行を高速化することができる。このことによって多少オーバーヘッドはあるが、実際2回目以降のクエリ時間には結構差が出る（Figure 12）。

どうやって有効だと検証した？

  • Positional Map・キャッシュがそれぞれ有効に働いているのかの確認（Figure 5）
  • MySQL, DBMS X, PostgreSQL との比較（Figure 7～10）
    • 実際にデータ読み込み時間を削減したことで、他の DBMS より速くクエリを終えられている。ただし、最初のクエリの実行は遅いので、それが読み込み時間とも取れる……。

議論はある？

  • 通常の列指向の DBMS で列が大量にあるテーブルを作ると、ページサイズをいじらないといけないことになりがち。本論文の手法なら、そんなこと気にしなくてもいいし、列が増えても線形にしか処理時間が変わらないことが確認できている（Figure 4） → 確かに！
  • クエリに対して自動で索引を作成するやつとかも組み合わせられるよね

次に読むべき論文は？