ブログ@nnaka2992

データベースってなんだよ

DBMSとクライアント間におけるデータ転送を最適化する論文を読みました

CMU_Advanced_Database_Systems DB 論文

この記事の趣旨

2017年に出版されたリモートDBMSとクライアント間の大量データ転送を最適化する 手法を提案する論文を読みました。

Don’t Hold My Data Hostage – A Case For Client Protocol Redesign

著者について

Mark Raasveldt、Hannes Muhleisenらのグループによる論文。 いずれもCentrum Wiskunde & Informaticaの所属で、DuckDBのCxO。 DBMSと分析システムにおけるパフォーマンス最適化を研究している。

問題意識

DBMSからクライアントプログラムに大量のデータを転送することは一般的なタスクである。 例えばRやPythonなどを用いた分析システムはしばしばデータベース・インターフェースを利用してデータの取得 を行なっている。

一方でネットワーク越しにデータを転送することはレイテンシを増加させ、転送時間を長引かせる要因である。 そのため分析用途で大量のデータ転送を避け、一部のデータをサンプルとして利用するに止まることが多い。 このアプローチはパフォーマンスの低下を押さえられるものの、分析や機械学習の精度を下げることに繋がる。

とくに既存のクライアントではネットワークによるレイテンシとスループットの制限に大きな影響を受けパフォーマンス を劣化させる。 この問題はデータベースが別マシンやクラウドで動作するときにより大きな問題となる。

手法

本論文では既存のシリアライズ手法と圧縮手法によるパフォーマンスへの影響を計測し、新しいプロトコルとして以下の特性を持つ 手法を提案している。 1. チャンク毎のデータ転送と(デ)シリアライゼーション 1. ヒューリスティックによる圧縮方法の決定 1. text/binaryによるカスタムシリアライゼーションを使用する 1. NULL終端によるテキストの取り扱い

実験結果

提案手法を実装したMonetDB(表内ではMonetDB++)とPostgreSQL(表内ではPostgreSQL++)を既存のDBMSやnetcatと比較することで 評価を行なっている。

TCP-Hのlineitem、American Community Survay、Airline On-Time Statisticsの3つのデータセットで評価を行なったところ、 ローカル通信における非圧縮netcatを除き殆どのケースでMonetDB++系が最良のパフォーマンスを発揮し 次点でPostgreSQL++系が優れた結果を残している。

Table 10: Results of transferring the SF10 lineitem table for different network configurations.
Table 10
Table 11: Results of transferring the ACS table for different network configurations.
Table 11
Table 12: Results of transferring the ontime table for different network configurations.
Table 12

PostgreSQLに比べMonetDBが優れている理由はPostgreSQLの行指向データを列指向に変換するコストのためである。

作業時間

  • read
    • 31:21
    • 31:21
  • author
    • 35:38
    • 4:17
  • summary
    • 70:13
    • 34:35

感想

論文出版時にはTPC/IPプロトコルが前提でQuic登場前のため、ネットワークプロトコル自体は考慮されていない。 現在であればTPC/IPとQuicに適合した手法の比較が行なわれると思うので気になるところ。

SQL ServerにおけるUDF最適化の論文を読みました

CMU_Advanced_Database_Systems DB 論文

この記事の趣旨

2017年に発表されたSQL ServerでUDFを最適化しているFroidという手法についての論文を読みました。

Froid: Optimization of Imperative Programs in a Relational Database

著者について

Karthik Ramachandra、Kwanghyun Park、K. Venkatesh Emani、Alan Halverson、Cesar Galindo-Legaria、Conor Cunninghamの グループによる論文。 ほとんどの著者はMicrosoftに所属しており、いずれもトランザクショナルワークロードでの RDBMSの最適化や分析ワークロードにおけるRDBMS最適化の研究をしている。

問題意識

RDBMSではSQLによるデータ処理アプローチと、UDFやストアドプロシージャなどによる命令型のデータ処理アプローチを提供している。 SQLによるデータアクセスは高度に最適化されてきた一方で、命令型のデータ処理は非効率なため性能を阻害し利用を禁止している 組織すらある。

UDFによるデータアクセスは非効率であるものの、SQLに比べ下記のような利点を提供するため幅広く利用されているのも事実である。 1. SQL間でコードの再利用方法を提供する 1. 複雑なビジネスロジックやMLアルゴリズムなどSQLでは難しい表現を可能にする 1. 単純なSQLの組み合わせのため、ユーザーの意図が明確に表現できる

これらのメリットを享受するためにRDBMSにおける命令型データアクセス手法のパフォーマンスを向上しする必要があった。

手法

提案手法であるFroidはMicrosoft SQL Serverにおける命令型コードのパフォーマンス向上の手法として、 UDFを複雑なサブクエリとしてみなすアプローチを取っている。

UDFを構成する命令はDECLARE、SELECT、IF/ELSE、RETURN、他のUDF、リレーショナルオペレーションの6つ に分ることができる。 提案手法ではこれらの命令を一般的なT-SQLに置き換え、Apply演算により一つの関係式に結合する方法で実現している。

Table 1: Relational algebraic expressions for imperative statements (using standard T-SQL notation)
Table 1

命令が一般SQLに置き換えられることでUDFに対して、SQLに用いられていた高度な最適化を導入することが出来る。

また提案手法ではい以下の理由から、SQLとして命令を置換するときにクエリ最適化時に行なうのではなく バインド時に置換をしている。 1. 実際のワークロードでの実験ではほぼ全てのケースでバインド時のほうが性能がよかった 1. クエリオプティマイザの変更が不要 1. バインディング時に特定の最適化を行なえる とくにクエリオプティマイザの変更はSQL Serverが商用データベースなため重要であった。

作業時間

  • read
    • 28:50
    • 28:50
  • author
    • 32:10
    • 3:20
  • summary
    • 57:00
    • 24:50

中間結果が莫大になるときの結合を最適化する最悪ケース最適化結合をRDBMSに適応する論文を読みました

CMU_Advanced_Database_Systems DB 論文

この記事の趣旨

2018年に発表された分析ワークロードなどで発生しがちな最終結果に比べ、非常に大きな中間結果を 作成してしまうクエリを多方向結合で最適化する論文を読みました。

Adopting Worst-Case Optimal Joins in Relational Database Systems

著者について

Michael Freitag、Maximilian Bandle、Tobias Schmidt、Alfons Kemper、Thomas Neumannによるグループの論文 いずれの著者もDBMSにおける最適化を中心に研究しており、それぞれ分析ワークロードにおける最適化や 最新のハードウェアにおける最適化などを研究している。

問題意識

従来のRDBMSにおける結合処理のほとんどはバイナリ結合に依存して複数のリレーションにまたがるクエリを処理してきた。 数十年に渡る研究によりバイナリ結合は幅広い柔軟性と優れた性能を発揮するようになった。

その一方でバイナリ結合による実行計画は特定のワークロードでは最適ではないケースを示すことが知られている。 主な原因として実際のクエリ結果に比べて非常に大きな中間結果を生成するためである。 とくにPK以外のキーによる結合が多くなる分析ワークロードではそのような状態を避けることが難しく、 またグラフ分析のようなクエリパターンでも多く見られる。

近年の論理的な進歩により中間結果の列挙を避ける多方向結合のアルゴリズムが開発可能になった。 この手法はバイナリ結合計画より優れた実行時間を保証できるため、RDBMSの堅牢性を大幅に向上させる 可能性を持っている。

しかし現状最悪ケース最適化結合アルゴリズムでは以下のような問題を抱えている。 1. 膨大なストレージとメンテナンスを必要とする結合に参加出来るカラムを含むインデックスを必要とする。 1. RDBMSは挿入と更新のサポートが必要なものの、既存のアルゴリズムは高価な事前計算を必要とする。

そのため本論文は以下の制約を満たすアプローチを提案している 1. 多方向結合が有益な場合のみ多方向結合を使用するオプティマイザを必要とする。 1. 実行中に効率的に実行でき、ディスクのに永続化する必要のないパフォーマントインデックスを必要とする。

手法

提案手法では比較ベースではなくハッシュベースの結合のため、2の「実行中に効率的に実行でき、 ディスクのに永続化する必要のないパフォーマントインデックスを必要とする。」という要素の考慮を除いている。

またオプティマイザについては既存のコストベースのものを拡張し適応している。 提案手法では潜在的に成長している結合のカスケードを最悪の場合の最適結合に置き換えることで、 最適化されたバイナリ結合計画を洗練させるヒューリスティックなアプローチを提案している。

通常の結合順序最適化で使用されるのと同じカーディナリティ推定値に基づいて、中間テーブルが膨大になる結合を 特定する。

作業時間

  • read
    • 22:13
    • 22:13
  • author
    • 25:48
    • 3:35
  • summary
    • 52:58
    • 26:50

感想

とても難しい内容に感じてしまい、殆ど頭を通りすぎてしまった気がする。

今まで最適化は触れずに来たため、理解が浅い領域だった。よくよく考えるとDBMSの 話しに最適化が登場するのはあたりまえなので、今後はその方面にも触れて行きたい。

マルチコアメインメモリにおけるソートジョインとハッシュジョインのパフォーマンスを検証した論文を読みました

CMU_Advanced_Database_Systems DB 論文

この記事の趣旨

2013年に発表された"Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited"という論文を読みました。 当時最新のアルゴリズムとハードウェアにおける、ソートとハッシュによる結合のパフォーマンスを比べた論文です。

Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited

著者について

Cagri Balkesen、Gustavo Alonso、Jens Teubner、M. Tamer Ozsuらのグループによる論文 いずれもDBMSにおけるクエリ最適化やビッグデータにおけるパフォーマンスを研究している。 またGustavo Alonsoはハードウェアや分散システムもメインのフィールドとしている。

問題意識

DBMSにおいて常にソートマージとハッシュ結合の性能比較が行われており、 最新の研究ではSIMDやNUMAへの適正に基づいてソートマージがより優れている と結論づけられていた。

しかしこれらの分野は常に研究が重ねられ、過去の検証時には登場していなったハッシュ結合の 最適化手法が生れた。

この論文ではそれらを適用し再度ソートマージとハッシュ結合の性能比較を行なう。

手法

本論文では以下に分けて結合手法の評価を行なっている。 1. ソートフェーズの評価
AVXを用いて実装したSIMDソートアルゴリズムとC++のSTLソートアルゴリズムを比較している。

  1. マージフェーズの評価
    異なる入力サイズにおけるマージのパフォーマンスを検証している。

  2. 入力サイズの調整によるマージフェーズの最適化
    入力サイズとパーティショニングによるソートのパーマンスを検証している。

  3. ソートマージジョインにおける影響要因の特定
    ソートマージジョインにおける性能に影響を与える要因を特定し、あらたな最適化方法を 検討している。

結果

  • 結合対象のデータサイズに拘わらずハッシュによる結合がソートベースの結合のパフォーマンスを上回っている。

    Figure 14: Comparison of best sort vs. best hash join algorithms with cycles per output tuple metric under different workloads. Using 64 threads.
    Figure 14

  • ソートマージによる結合は入力サイズが著しく大きくなったときのみハッシュ結合のパフォーマンスに近づく。

    Figure 15: Sort vs. hash with increasing input table sizes (|R| = |S|). Throughput metric is total output tuples per second, i.e. |S|/execution time.
    Figure 15

  • ソートマージ、ハッシュ結合におけるデータの偏りはパフォーマンスに大きな影響を及ぼさなかった。

    Figure 16: Join performance when foreign key references follow a Zipfian distribution. Workload B.
    Figure 16

  • いずれのアルゴリズムも物理的なコア数では線形にスケールした。

    Figure 17: Scalability of sort vs. hash join. Throughput is in output tuples per second, i.e. |S|/execution time.
    Figure 17

作業時間

  • read
    • 23:11
    • 23:11
  • author
    • 27:09
    • 3:58
  • summary
    • 60:12
    • 32:57

RDBでの結合手法を比較した論文を読みました

CMU_Advanced_Database_Systems DB 論文

この記事の趣旨

2016年に発表された"An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory"という 論文を読みました。 様々な結合手法を包括的に比較した論文でどのような結合方法がどのような時に適しているかを示しています。

An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory

著者について

Stefan Schuh、Xiao Chen、Jens Dittrichのグループによる論文。 いずれもDBMSや分析システム、Hadoopなどにおける検索高速化・最適化の研究を行なっている。

問題意識

関係結合はほとんど全てのクエリプランにおいて中核をなす処理であり、定期的に研究・改良され再検討 されてきた。 新たな手法が提案され実験を行なわれるものの、それぞれ結果において比較を困難にする要素や 幾らかの矛盾を孕んでいた。

例えば同じハッシュベースの結合アルゴリズムの比較でも実装が異なったり、複数の論文でパフォーマンス比較で 正反対の結果を示しているためである。

そのため単純に論文執筆時点で最も高速な結合アルゴリズムを結論づけることが困難であった。

手法

本論文では結合方法を以下の3つに分類した 1. パーティションベースハッシュジョイン
結合対象となるリレーションをペアとなるキャッシュに収まる小さなパーティションに分割し結合する手法。 ハッシュテーブルの構築と結合されるデータの探索のキャッシュミスを最小にする事を目的としている。

  1. 非パーティションベースハッシュジョイン
    1つのグローバルパーティションテーブルを構築しながら結合を行なう手法で、マルチスレッドと順番に依存しない 実行によりキャッシュミスのパフォーマンス劣化を隠蔽している。

  2. ソートマージジョイン
    結合対象となるリレーションを結合キーでソートし、結合を行なう手法。 ソートはSIMDによりベクトル化される。

検証ではこれらの結合方法を以下の3つのテストで使用するために、全部で13のアルゴリズムを検証している。 1. ブラックボックス比較
基本となる3種4実装の結合方法をブラックボックス的に比較する。

  1. ホワイトボックス比較
    ブラックボックス比較で検証する結合方法に先行研究で示された最適化を施した上で比較を行なう。

  2. パラレルラディックスジョイン比較
    NUMAを考慮した結合におけるそれぞれのパフォーマンスを比較する。

Table 2: reference table for the algorithms evaluated in this paper
Table 2

結果

  1. パーティション結合の一種であるリモート書込みを排除したCPR系アルゴリズムは小さな入力に対して有効ではない
  2. スケールの大きい結合ではとくに理由が無い場合、パーティションベースのジョインを利用する
  3. 大きなサイズのページを利用する
  4. ソフトウェアライトコンバインバッファ()を利用する
  5. パーティションジョインでは適切なパーティションビットを利用する
  6. できるかぎりシンプルなアルゴリズムを利用する
  7. NUMAを考慮したアルゴリズムを利用する
  8. 実行時間とクエリ時間は同一ではない

作業時間

  • read
    • 31:34
    • 31:34
  • author
    • 35:18
    • 3:46
  • summary
    • 77:50
    • 42:32

コンパイルとベクトル化による最適化のパフォーマンスを比較した論文を読みました

CMU_Advanced_Database_Systems DB 論文

この記事の趣旨

2018年に発表された"Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask"という論文を読みました。 最新のクエリエンジンの特性をまとめ、どのようなワークロードに向くのかという指針を示すないようです。

Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask

Timo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo, Peter Boncz

著者について

Timo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo, Peter Bonczのグループによる 論文。

いずれも大規模データにおけるクエリパフォーマスや最適化に関する研究を行なっている。

問題意識

分析ワークロードに向いた最新のクエリエンジンはベクトル化またはデータ中心のコード生成に基づいている。 どちらのモデルも従来のエンジンに比べオーバーヘッドが少く、非常に効率的なものの概念的には 大きく異なっている。

この2つのモデルの違いは、DBMSの実行エンジンのソースコードの構成とその性能 特性を決定する基本的なもので、クエリ実行モデルを超える多くの設計で異なる。

本論文はことなる2つのモデルを再実装し、環境差異のないマシンで実行することで それぞれのモデルがどのように違うのか。どのような用途に最適なのかを検証している。

手法

検証手法は著者らがC++で再実装したデータ中心モデルの「Taper」とベクトル化中心の「Tectorwise」を 同一のマシンでパフォーマンス検証を行っている。

検証項目は以下から成る 1. インメモリOLAPワークロードでのマイクロアーキテクチャ分析 1. SIMDの利点の検証 1. マルチコアCPUにおけるクエリ並列化 1. 異なるハードウェアでのパフォーマンス

結果

  1. インメモリOLAPワークロードでのマイクロアーキテクチャ分析
    全体的にはほぼ同レベルのパフォーマンスを発揮する一方で、対象となるクエリによって異なる特徴を示した。 アグリゲーション処理ではTectorwiseが優位になるが、ハッシュ処理がメインになる処理ではTaperが優位性を示す。 これはTectorwiseのベクトル化処理ではキャッシュミスを隠しパフォーマンスを向上させる一方で、 ハッシュ処理は単純なループなためである。 Taperはハッシュ処理において複雑なループを行なう一方、ブランチミスによるキャッシュ失敗に大きなペナルティがあるため である。

    Figure 3: Performance – TPC-H SF=1, 1 thread
    Figure 3: Performance – TPC-H SF=1, 1 thread

  2. SIMDの利点の検証
    SIMDを評価するにはTectorwiseのみを用いた。 SIMDではスカラーなデータをベクトルに変換するペナルティは少く、最大8.4倍の性能向上が確認された。
    しかし複雑なクエリでは少ない性能向上に留まった。 これはOLAPクエリのパフォーマンス向上はデータアクセスに縛られる為である。

    Figure 6: Scalar vs. SIMD Selection in Tectorwise – (a) 40% selectivity. (b) Secondary selection: Input selection vector selects 40% and selection selects 40%. (c) Runtime of TPC-H Q6, SF=1
    Figure 6: Scalar vs. SIMD Selection in Tectorwise

  3. マルチコアCPUにおけるクエリ並列化
    TyperとTectorwiseの比較に用いたクエリで実験したところ、Hyperでは11.7倍、Tectorwise7.2倍の平均高速化が測定された。 いずれのモデルもスケールに対応している。またインメモリワークロードにおける実験で示された、それぞれのクエリの得意不得意 はマルチコアにも引きつがれている。

  4. 異なるハードウェアでのパフォーマンス
    Intel Skylake、Intel Knights Landing、AMD Ryzenで対照実験を行なったものの、 いずれのハードウェアでもTyper、Tectorwiseともに有効に動作した。

作業時間

  • read
    • 29:26
    • 29:26
  • author
    • 33:23
    • 3:57
  • summary
    • 76:37
    • 42:44

感想

VoectorwiseとHyperのいずれを使うべきか。どちらが優れているかといった疑問に答えるないようだった。

SIMDによるベクトル処理の最適化とRDBでの応用について扱った、最適化に関する論文を読みました

CMU_Advanced_Database_Systems DB 論文

この記事の趣旨

2020年に提案された"Make the most out of your SIMD investments: counter control flow divergence in compiled query pipelines"という論文を読みました。

SIMDによるベクトル処理の最適化とRDBでの応用について扱った、最適化に関する論文です。

Make the most out of your SIMD investments: counter control flow divergence in compiled query pipelines

Harald Lang, Linnea Passing, Andreas Kipf, Peter Boncz, Thomas Neumann, Alfons Kemper

著者について

Harald Lang、 Linnea Passing、 Andreas Kipf、 Peter Boncz、 Thomas Neumann、 Alfons Kemperのグループ による研究

いずれも最新のアーキテクチャでのクエリ最適化やデータ分析における検索手法などを研究している。

問題意識

CPUの発展にともないあたらしいCPUアーキテクチャが登場した。Single Instruction Multiple Data(SIMD)では RDBはSIMDによるベクトル処理能力の向上により、クエリコンパイラの実行パイプライン全体をベクトル化して 高度なデータ並列性の恩恵を受けることが出来るようになった。

一方でクエリ全体をベクトル化して実行することで、SIMDによるクエリ評価が忙しくなる。 SIMD評価で結果に寄与しない評価が単純にオーバーヘッドとなってしまう。

手法

本論文ではリフィルアルゴリズムとそのアルゴリズムをクエリパイプラインプランに統合する手法 で上記の問題の解決を試みている。

リフィルアルゴリズムは基本的に新しい要素を宛先レジスタの希望する位置にコピーするアルゴリズムで、 メモリからレジスタとレジスタからレジスタへのコピーの2パターンが存在する。

クエリパイプラインプランに統合するリフィル戦略ではConsume EverythingパターンとPartial Consumeパターンが 存在する。

Consum Everything戦略は、タプルをバッファリングするために使用される追加のベクターレジスタを割り当てる方法で 利用率が低い場合、オペレータはこれらのタプルの処理を延期する。つまり、この反復ではボディは実行されず(条件が 満たされない場合)、代わりにアクティブなタプルがこれらのバッファレジスタに移動することになる。

Partial Consume戦略ではconsume()コードを入力の一部に適用する方法で、制御フローを前のオペレータに戻し、アクティブな データ断片のみをベクトルレジスタに残すことで実行を延期している。

作業時間

  • read
    • 29:40
    • 29:40
  • author
    • 33:40
    • 4:00
  • summary
    • 60:04
    • 26:36

感想

前回に引続き個人的には難しいと感じる論文だった。 2000年前後の提案にくらべ、2015年前後の論文ではハードウェアアーキテクチャを中心とした手法がピックアップされている。 単純に自分の知識不足、理解力不足なので勉強するしかない。