2024/6に出版された[What Goes Around Comes Around... And Around...](https://db.cs.cmu.edu/papers/2024/whatgoesaround-sigmodrec2024.pdf)という論文の日本語メモです。

# Introduction

* 2005に[What Goes Around Comes Around](https://people.cs.umass.edu/~yanlei/courses/CS691LL-f06/papers/SH05.pdf "https://people.cs.umass.edu/~yanlei/courses/CS691LL-f06/papers/SH05.pdf")という論文を書いた人が20年後の現在にアップデートしたものを書き直した
* SQLと関係モデル（リレーショナルモデル＝RM）をリプレイスしようとする動きはまたまたあったが、RMはまだ優勢的なモデルであるし、SQLが外部からの良いアイディアを取り組んでいる
* 前回の論文からは色んな変化があった
* DBMSはビジネスデータの処理からほぼどのデータの種類に使われるようになっている
* 2010sはビッグデータの時代があった
* 最近のトレンドはML系機能をDBMSに統合すること
* 主張：SQL / RMから乖離したシステムは最終的に優勢でない状態で、ニッチな市場でしか成功していない
* NoSQLのような「RMから卒業するぜ」というシステムは結局SQLライクなインターフェースを提供している
* 一方でSQLが市場からのベストなアイディアを取り入れてモダンなアプリケーションに新しい価値を提供できる
* RMの基礎自体は特に変わっていないが、システムの内部実装は大きく変化している

# Data Models & Query Languages

## MapReduce Systems

* MapReduce (MR) はGoogleがウェブクローリング処理用に2003に開発した
* [MapReduce: Simplified Data Processing on Large Clusters](https://research.google/pubs/mapreduce-simplified-data-processing-on-large-clusters/)
* DBで言うと
* **Map**は[user-defined function](https://en.wikipedia.org/wiki/User-defined_function#Databases "https://en.wikipedia.org/wiki/User-defined_function#Databases")
* [What are user-defined functions (UDFs) in SQL, and why should you care?](https://www.cockroachlabs.com/blog/udfs-in-sql/)
* **Reduce**は`GROUP BY`
* `SELECT map() FROM crawl_table GROUP BY reduce()`
* GoogleのMRは特定なデータモデルやクエリ言語を定義しなかった
* 2005にYahoo!がMRシステムである[Hadoop](https://hadoop.apache.org/ "https://hadoop.apache.org/")を開発した
* [HDFS](https://hadoop.apache.org/docs/r1.2.1/hdfs_design.html "https://hadoop.apache.org/docs/r1.2.1/hdfs_design.html")という分散ファイルシステム上に走る技術
* 2010年ごろにGoogleとDBMSコミュニティの論文バトル
* [MapReduce and Parallel DBMSs: Friends or Foes?](https://web.stanford.edu/class/cs345d-01/rl/PDBMSvsMR.pdf "https://web.stanford.edu/class/cs345d-01/rl/PDBMSvsMR.pdf") vs. [MapReduce: A Flexible Data Processing Tool](https://web.stanford.edu/class/cs345d-01/rl/MRvsPDBMS.pdf "https://web.stanford.edu/class/cs345d-01/rl/MRvsPDBMS.pdf")
* DBMSコミュニティ：並列DBMSでMRのユースケースをカバーできるのでは
Google：柔軟なfault tolerance（再開可能な処理）、複数なストレージシステムのデータ処理、DBMSになかなか対応されない複雑な関数（Map）が利用可能
* 2010年代にHadoopの利用が普及する
* 開発者がMR/Hadoopの制約と戦う
* RMインターフェイスが結局導入される（特にMetaが出した[Hive](https://hive.apache.org/ "https://hive.apache.org/")）
* 同じ2010年に[Google SearchがMapReduceからBigTableに移行する](https://www.theregister.com/2010/09/09/google_caffeine_explained/ "https://www.theregister.com/2010/09/09/google_caffeine_explained/")
* インデックスをバッチ処理じゃなくリアルタイム処理で更新したいから
* 2014年にGoogle全体がMRを完全に捨てた ([アナリティクスはCloud Dataflowに移行](https://www.datacenterknowledge.com/hyperscalers/google-dumps-mapreduce-in-favor-of-new-hyper-scale-analytics-system "https://www.datacenterknowledge.com/hyperscalers/google-dumps-mapreduce-in-favor-of-new-hyper-scale-analytics-system"))
* ClouderaなどのMRベンダーが困ることに
* MetaがSQLベースの[Presto](https://prestodb.io/ "https://prestodb.io/")にHiveをリプレイス
* レガシーなHDFSシステムが未だに残る
* fault tolerance、スケーラビリティ、elasticityなどのMR系機能がRDBMSに吸収される
* Hadoopの失敗はより良いMR実装である[Spark](https://spark.apache.org/ "https://spark.apache.org/")や[Flink](https://flink.apache.org/ "https://flink.apache.org/")の普及への道を開いた
* 結局SparkやFlinkもSQLのAPIを導入している

## Key/Value Stores

* Key/value（KV）モデルは最もシンプルなモデル
* `(key, value)`のバイナリ関係でしかない
* KV DBMSはデータの集合をassociative arrayとして表現する
* 多くのKV DBMSはget/set/deleteのオプしか提供しない
* 2000年代にKV DBMS系のプロダクトが登場
* キャッシュとしてはMemcachedが最も普及する
* Redisは機能豊富なMemcachedの入れ替えとして訴求される
* 2007年：永続化のユースケースにはAmazonのDynamo KV Storeがリリース
* RDBMSに比べたら、KVシステムはより高いかつ予測可能なパフォーマンスを提供するが、機能群が大きく制限される
* 他に「embeddedストレージマネージャー」である、アプリケーションと同一アドレス空間で実行される前提のシステムが登場
* 1990年代からも[Berkeley DB](https://www.oracle.com/database/technologies/related/berkeleydb.html "https://www.oracle.com/database/technologies/related/berkeleydb.html")
* Googleの[LevelDB](https://github.com/google/leveldb "https://github.com/google/leveldb")とそのフォークであるMetaの[RocksDB](https://rocksdb.org/ "https://rocksdb.org/")
* KV系のシステムはエンジニアに使いやすいが、複雑なデータモデルには推奨しがたい
* アプリーけション側でスキーマをパースしないといけない
* 二次的なインデックスはなし
* JOINやMULTI GETの操作も基本アプリケーション側で実装しないといけない
* 👆🏻の制約の関係でKVモデルでスタートし、レコードストアに変換したシステムもある
* Ex：Dynamo→DynamoDBや[Aerospike](https://aerospike.com/ "https://aerospike.com/")
* KVシステムにはRDBMSチクな機能が入れ難いが、その逆は難なく再現可能
* [SQLite](https://www.sqlite.org/ "https://www.sqlite.org/")や[DuckDB](https://duckdb.org/ "https://duckdb.org/")は「embeddedストレージマネージャー」として利用可能
* ここ20年間のアーキテクチャトレンドとしては、embeddedなKVストアをRDBMSのストレージマネージャーに利用するのがある
* それ以前はRDBMSごとにストレージエンジンを一緒に開発する必要があった
* MySQLが初めてストレージエンジンを変更するAPIを提供した
* おかげでMetaがInnoDBの代わりにMySQLにRocksDBが利用できた
* MongoDBも2014年に（[memory-mapped file](https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%A2%E3%83%AA%E3%83%9E%E3%83%83%E3%83%97%E3%83%88%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB)ベースの）[MMAPエンジン](https://www.mongodb.com/docs/v4.0/core/mmapv1/ "https://www.mongodb.com/docs/v4.0/core/mmapv1/")を[WiredTiger’s KV Store](https://www.mongodb.com/docs/manual/core/wiredtiger/ "https://www.mongodb.com/docs/manual/core/wiredtiger/")にリプレイス
* 既存KVストアを利用することで、DBMSはより早く開発できるようになった

## Document Databases

* [Documentデータモデル](https://aws.amazon.com/nosql/document/ "https://aws.amazon.com/nosql/document/")はDBをレコードオブジェクトのコレクションとして表現する
* フィールド/バリューの構造である
* 各フィールドは名前というidentifierがある
* バリューはスカラーか配列かドキュメントかのどれかになる

  { “name”: “First Last”,
  “orders”: [ { “id”: 123, “items”: [...] },
              { “id”: 456, “items”: [...] }, ] }

* [SGML](https://ja.wikipedia.org/wiki/Standard_Generalized_Markup_Language "https://ja.wikipedia.org/wiki/Standard_Generalized_Markup_Language")やXMLをはじめとしてDocumentモデルは古くからある
* XMLの代わりにJSONがウェブのスタンダートになった
* JSONの人気で複数社がJSONベースのdocument-oriented DBMSを開発した
* 2000年代のOLTP RDBMSのスケール問題により、document DBMSが流行ることになった
* NoSQLという呼び名ができた
* 「SQLとJOINが重い！」というキャッチコピーがあった
* ACIDはモダンなアプリケーションに不要という推しも
* **「NoSQL」**はTXなしのJSONベースdocument/recordを保存するDBMSという意味合いがついた
* Document DBMSは1980年代の[オブジェクト指向データベース](https://ja.wikipedia.org/wiki/%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9 "https://ja.wikipedia.org/wiki/%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9")と1990年代のXML DBMSとほぼ同じもの
* 「データモデルとアプリケーションモデルのミスマッチを解消する！」という主張が一緒
* 「非正規化がパフォーマンスにいいよ！」というスタンスも一緒
* SQLの批判があったにしても、2010年代の最後までほとんどのシステムがSQLライクなインターフェイスを導入した
* DynamoDBの[PartiQL](https://docs.aws.amazon.com/ja_jp/amazondynamodb/latest/developerguide/ql-reference.html "https://docs.aws.amazon.com/ja_jp/amazondynamodb/latest/developerguide/ql-reference.html")、Cassandra [CQL](https://cassandra.apache.org/doc/stable/cassandra/cql/ "https://cassandra.apache.org/doc/stable/cassandra/cql/")、Aerospike [AQL](https://aerospike.com/docs/tools/aql "https://aerospike.com/docs/tools/aql")、Couchbase [SQL++](https://www.couchbase.com/products/n1ql/ "https://www.couchbase.com/products/n1ql/")、そして最後にMongoDBの[SQLサポート](https://www.mongodb.com/docs/manual/reference/sql-comparison/ "https://www.mongodb.com/docs/manual/reference/sql-comparison/")
* 多くのNoSQL DBMSがACID TXも導入した
* NoSQLは「SQLはもう古いぜ！」のノリからNo(t only)SQL（SQLも場合によってOK）に変化してきた
* SQLとACIDを導入することで、RDBMSとNoSQLと本質的な違いが薄くなったし、これからほぼ一緒になるであろう
* SQLはoptimizerが一番困難であるし、初期のものは重くて効果的じゃなかったから、元々のNoSQLには「SQLは利用しないぜ！」という思想が強めたであろう

## Column-Family Databases

* NoSQLのカテゴリとして、column-family (通称wide-column)というデータモデルがある
* [Columnar（列指向）データモデル](https://ja.wikipedia.org/wiki/%E5%88%97%E6%8C%87%E5%90%91%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9%E7%AE%A1%E7%90%86%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0 "https://ja.wikipedia.org/wiki/%E5%88%97%E6%8C%87%E5%90%91%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9%E7%AE%A1%E7%90%86%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0")とは違う
* [Documentデータモデル](https://aws.amazon.com/nosql/document/ "https://aws.amazon.com/nosql/document/")の一種で、ネストは利用できない（＝フラットな構造）

    User1000 → { “name”: “Alice”,
                 “accounts”: [ 123, 456 ],
                 “email”: "[e-mail]” } 
    User1001 → { “name”: “Bob”,
                 “email”: [ “[e-mail]”, “[e-mail]” ] }

* 最初のcolumn-familyモデルDBMSは2004年の[Google BigTable](https://cloud.google.com/bigtable?hl=en "https://cloud.google.com/bigtable?hl=en")
* Cassandraや[HBase](https://hbase.apache.org/ "https://hbase.apache.org/")もcolumn-familyモデルを採用した
* JOINのなさや2次的インデックスのなさといったBigTableの制約も採用してしまった
* 上記のDocumentモデルの話は基本ここにも当てはまる
* Googleが[Megastore](https://research.google/pubs/megastore-providing-scalable-highly-available-storage-for-interactive-services/ "https://research.google/pubs/megastore-providing-scalable-highly-available-storage-for-interactive-services/")と初期の[Spanner](https://cloud.google.com/spanner?hl=en "https://cloud.google.com/spanner?hl=en")をはじめとしてBigTable上にRDBMSを開発した
* その後SpannerからBigTableの部分を剥がした
* BigTableはまだクラウドサービスとして提供されているが、NoSQLと同じ短所がある
* Cassandraが[CQL](https://cassandra.apache.org/doc/stable/cassandra/cql/ "https://cassandra.apache.org/doc/stable/cassandra/cql/")、HBaseが[Phoenix](https://phoenix.apache.org/ "https://phoenix.apache.org/")というSQLインターフェイスを結局適用している

## Text Search Engines

* [全文検索](https://ja.wikipedia.org/wiki/%E5%85%A8%E6%96%87%E6%A4%9C%E7%B4%A2)は1960年代からあるもの
* SMARTというシステムが現在当たり前になっている[Inverted index (転置インデックス)](https://ja.wikipedia.org/wiki/%E8%BB%A2%E7%BD%AE%E3%82%A4%E3%83%B3%E3%83%87%E3%83%83%E3%82%AF%E3%82%B9)を創始した
* the、aなどの「ノイズワード」、キーワード、「距離」の概念（「地球温暖化」と「かんばつ」の近さ）は実装されていた
* 今時は[Lucene](https://lucene.apache.org/)ベースの[Elasticsearch](https://www.elastic.co/elasticsearch)や[Solr](https://solr.apache.org/)が主流となっている
* テキストデータの保存・インデックスのサポートが優れているが、トランスアクション機能は基本ない
* このせいでデータ不整合からの復活はDBMSによるインデックスの再作成が必要になる（＝ダウンタイムが長くなりがち）
* Oracle、MSSQL Server、MySQLをはじめとしてメジャーのRDBMSが全文検索の機能を提供している
* 主流の全文検索システムに近いところまで進化しているが、SQLベースの操作にはぎこちない部分がある
* テキストデータは本質的に構造化されていないため、データモデルはない
* DBMSはそれでもフルスキャンを避けるため、メタデータやインデックスなどの構造化に依存する
* アプリケーションではテキストデータを管理する方法は主に３つある
1. 複数のシステムを管理する（Ex: MySQL ＋ Elasticsearch）
* ユースケースごとの最適なシステムが利用できる
* RDBMSから全文検索システムへのETLパイプラインやクエリのルーティングが必要になる
2. 全文検索機能がついているが、ユースケースごとにSQLのAPIが乖離するRDBMSを利用する
* APIの違いをアプリケーション側で隠蔽する
3. 統一されたインターフェイスをミドルウェアにより提供する[polystore](https://wp.sigmod.org/?p=1629)を利用する

## Array Databases

* ここで言う配列というのは1次元のvector、2次元のmatrix、3次元以上のtensorということを指す
* arrayデータモデルを利用するDBMSは1980年代のPICDMSが初めてだった
* よりモダンなarray DBMSには[SciDB](https://dbdb.io/db/scidb) and [TileDB](https://tiledb.com/)がある
* [HDF5](https://www.hdfgroup.org/solutions/hdf5/)と[NetCDF](https://www.unidata.ucar.edu/software/netcdf/)はscientific dataに人気の配列ベースファイル形式
* 配列データはアプリケーション側のマッピングが難しい
* マッピングできるようにメタデータを一緒に保存することが多い
* 次元の分からない配列データをクエリするのは困難
* 多次元配列データを効率的に走査できるインデックスやデータ構造が重要になる
* Array DBMSはニッチ市場である
* ゲノミクスなどの特定なユースケースに人気がある
* HDF5は衛星画像データなどに人気がある
* メジャーなクラウドベンダーは提供していない
* RDBMSの対応が進んでいるのもArray DBMSのベンダーにとってはチャレンジである
* SQL:1999が1次元の固定長配列に対応した
* SQL:2003は固定長じゃないものに拡張した
* SQL:2023スタンダートには多次元配列のサポートが入っている
* [SQL Support for Multidimensional Arrays (PDF)](https://d-nb.info/1137054492/34)

## Vector Databases

* Column-familyデータモデルがDocumentモデルを簡易化する（最大1階層まで）と同じように、VectorデータモデルがArrayデータモデルを簡易化する（最大1次元まで）
* 最近開発者と投資家に注目されている（NoSQLファッドのように）
* AIツールに生成される1次元embeddingsの保存に利用されるからだ
* このツールはlearned transformationsを使ってレコードのデータ（テキスト、画像など）を（そのデータの）本質的なsemanticsを表現するvectorに変換する
* Ex: [Google BERT](https://aisuite.jp/column/bert/)を利用し、Wikipediaの記事をembeddingに変換してvector DBに保存できる
* `(title, date, author, [embedding-vector])`
* これらのembedding vectorは簡易的なtransformerの100単位からモデルの1000単位のディメンションからできている（将来の進化で大きくなっていく）
* Vector DBはRDBと違うクエリパターンがある
* Vector DBは入力のvectorに一番近いvectorを検索する
* 入力のvectorもDBデータを生成した同じtransformerに生成されたembedding
* Array DBと違ってオフセットを使ったりスライスを抽出したりしない
* 主にsimilarity searchに利用される
* フルスキャンを避けるため、[approximate nearest neighbor (ANN)](https://www.elastic.co/blog/understanding-ann)の探索を効率化するインデックスがある
* クエリの条件はembeddingインデックスとメタデータのインデックスの項がそれぞれある
* DBMSが各項をフィルター前かフィルター後かのいつに当てはめるかを決定
* このカテゴリのDBMSがたくさん登場している
* リーダーとしては[Pinecone](https://www.pinecone.io/)、[Milvus](https://milvus.io/)、[Weaviate](https://weaviate.io/)
* テキスト検索エンジンであるElasticsearch、Solr、Vespaもvector探索機能を導入している
* [kdb+](https://kx.com/products/kdb/)のような、トレンドに乗っけれるようにリブランドしたものもある
* Vector DBの大きなメリットはembeddingのネイティブ対応
* RDBの場合はアプリケーションレイヤーで入出力の変換処理が必要
* Vector DBMSはArray DBMSと違って特殊なストレージマネージャーや実行エンジンは不要
* 多次元のデータに対応しなくてもいいため
* 基本特化したANNインデックスのあるdocument-oriented DBMSになる
* 2022年後半のChapGPT爆発の1年後にいくつかのRDBMSがvector探索の拡張機能をさっそく導入した
* Oracle、SingleStore、Rockset、 Clickhouse
* NoSQLで流行ったJSONサポートのRDBへの導入はもっと遅いペースで進んだ
* vector探索が早かった理由：ユースケースとしてはニーズがありすぎる＋開発工数が比較的小さい
* 予想：vector DBMSがrelationalライク機能（SQL、TX）を導入しながら、RDBがvector機能を充実化してから次のトレンドに移っていく

## Graph Databases

* グラフの表現方法として[Resource Description Framework (RDF)](https://ja.wikipedia.org/wiki/Resource_Description_Framework)と[Property Graphs](https://docs.oracle.com/cd/F47674_01/spgdg/what-are-property-graphs.html)が主流
* Property graphsの場合はDBMSがnode/edgeのkey/valueラベルに対応する「有向マルチグラフ構造」を管理する
* RDF DB (通称triplestores) はedgeのラベルのみに対応した有向グラフになる
* OLTPのユースケース
* このユースケースに[Neo4j](https://neo4j.com/)がもっとも人気なDBMS
* edgeはポインター ([CODASYL](https://ja.wikipedia.org/wiki/CODASYL)) により対応されるが、ノードは“親”と“子”と一緒にクラスター構造にならない
* このアーキテクチャはa→b→c→dのようにチェーンが長い走査に有効
* RDBはJOINを利用するしかない
* 市場での成功はRDBをあえて使わない「長いチェーン」のユースケースがどこまであるか次第
* アナリティクスのユースケース
* グラフから情報を算出する処理
* [Tigergraph](https://www.tigergraph.com/)や[JanusGraph](https://janusgraph.org/)はグラフ系のクエリ言語とストレージに集中している
* GiraphやTuri (旧Graphlab) はグラフ志向プログラムの並列処理を可能にする「fabric (仕組み/platform)」を提供する
* JOINが特徴になるRDBのクエリと違って、グラフ系のクエリは[最短経路](https://ja.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E5%95%8F%E9%A1%8C)、[カットセット](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%83%E3%83%88_(%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96))、[クリーク特定](https://ja.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E3%82%AF%E3%83%AA%E3%83%BC%E3%82%AF%E5%95%8F%E9%A1%8C)などの操作がある
* グラフDBMSのパフォーマンスはアルゴリズムの選定とデータ構造の表現にかかる
* 開発者が自身でアルゴリズムが書ける抽象化のある仕組みが要される
* 分散アルゴリズムは通信コストにより不利になるため、マシン1台に入れるような圧縮グラフ構造が好ましい
* OLTPとOLAPを問わずグラフ構造をRDBのテーブルで表現できるという事実からグラフDBベンダーは認めないといけない

  Node (node_id, node_data)
  Edge (node_id_1, node_id_2, edge_data)

* なので、RDBMSはグラフのユースケースに選択肢になる
* ただ、SQLの表現力は限られている
* MSSQLやOracleはグラフ専用のSQL拡張機能を提供している
* 他のDBMSは「変換レイヤ」を利用してRDB上のグラフDBを提供している
* [AWS Neptune](https://aws.amazon.com/neptune/)はAurora MySQL上のグラフ専用インターフェイスでしかない
* [Apache AGE](https://age.apache.org/)はPostgres上のグラフ系DB
* 最近で言うとSQL:2023がグラフを定義・走査できるproperty graphクエリ (SQL/PGQ)を導入している（[Ref](https://www.cidrdb.org/cidr2023/papers/p66-wolde.pdf)）
* Neo4jのCypher、OracleのPGQL、TigerGraphのGSQLなどの言語から概念を継承している
* グラフDBとRDBのギャップが更に縮まる
* Graph DBMSがグラフ専用のシステムを高速化できるかが将来がかかるのであろう
* [DuckDB](https://duckdb.org/)でのSQL/PGQが主流グラフDBに比べて10倍のパフォーマンスが出せるという事例もある（[Ref](https://www.cidrdb.org/cidr2023/papers/p66-wolde.pdf)）
* 今後もRDBのグラフ関連性能が上がっていく

## Summary

* 非SQLシステムがニッチ市場向けか、SQL・リレーショナルシステムに変化しているかというトレンドがある

# System Architectures

## Coming Soon!