NAKADATE Naoki

今年に入ってからCarnegie Mellon UniversityのAdvanced Database SystemsでReading Assignmentとして出ている論文リストで必須とされているものや講義資料を読みました。https://nnaka2992.hatenablog.com/archive/category/論文この記事では紹介されていた論文やAdvanced Database Systemsの講義資料・動画を振り替えることで、BigQueryやRedShift、Snowflakeといった最新の分析用データベースがどのように優れたパフォーマンスを実現しているかを考え...

OLAPデータベースを支える技術

この記事の趣旨2020年に発表されたBigQueryの元となったGoogle内で利用されている分析向けデータベースであるDremelの実装を解説した論文を読みました。Dremel: A Decade of Interactive SQL Analysis at Web Scale著者についてSergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton,Theo Vassilakisら2010年のDremel発表論文の著者らと、Hossein Ahmadi, Dan Delorey, Slava Min, Mosha Pasumansky, Jeff ShuteらGoogleで分析ワークロードと分散処理に関わる著者らによる論文。概要BigQueryの元となったGoogleのDremelの10年間を振り替えってアーキテクチャについて説明した論文。Dremelは現代のクラウドネイティブ分析ツールで一般的になっている、計算リソースとストレージの分解、カラムナストレージ、in situデータ分析などを統合した最初のツールである。手法SQLの採用Googleでは殆どのデータはBigTableなどNoSQLデータベースで管理されていたため、SQLを用いないデータアクセスが主流であった。しかしトランザクション型ビッグデータシステムにおける、SQLの採用に共ないDremelでもSQLを採用した。ストレージの分離メモリの分離MapReduceのシャッフルのボトルネックを回避するためにDisaggregated Memory Shuffle Systemを採用した。In situデータ分析への対応DBMSへのデータロードを必要としないデータ分析のことで、DremelではGFSに移行するときにGoogle内で共有のストレージフォーマットを使用することでGoogle内のデータに対応した。加えてGoogle Cloud StorageやGoogle Drive、MySQL、BigTableなどからのデータ取得もフェデレーションとして対応した。サーバレスアーキテクチャフォールトトレラントリスタート、仮想スケジューリングユニットによりマルチテナントかつオンデマンドなリソースを提供可能とし、低価格な利用を可能とした。現在ではサーバレスアーキテクチャを進化させ、集中型スケジューリングやShuffle Persistent Layer、柔軟なDAG実行、動的クエリ実行などを実装することでより優れたサーバレスアーキテクチャを実現した。ネストデータにおけるカラムナストレージ[[32])]Figure 5Figure 6Figure 7クエリレイテンシの最小化インタラクティブな実行のレイテンシは大きくなる。それを解決するためにDremelではスタンバイサーバプール、マルチレベル実行ツリー、列指向スキーマ表現、CPUとIO負荷のバランス調整、ファイルオペレーションの再利用、保証されたキャパシティ、適合的なクエリスケーリングにより実現している。作業時間read27:5027:50author32:024:12summary68:5026:48

現在のDremelの実装を解説した論文を読みました 

はじめにこの記事ではNewSQLの特徴であるノード間の分散とトランザクションや分断耐性などがTiDBではどのような技術によって実現されているかを説明することを目的としています。Spannerの論文が2012年に発表されてから10年以上の年月が流れ、優れた論文や実装ドキュメント、個人による解説ブログなど技術的詳細について述べた資料は多くあります。加えてこの記事を入門的なものと位置づけているため各コンポーネントを網羅的に解説するというよりは、キーコンセプトをどのように実装しているのかを実験を混じえながら動作の実現方法の解説を中心に扱います。また今回はTiDBをベースに説明し...

TiDBで学ぶNewSQLのアーキテクチャ for Beginners

この記事の趣旨2015年に発表されたクエリオプティマイザにおけるカーディナリティ推定とコストモデル、列挙アルゴリズムの貢献度を評価した論文を読んでいきます。How Good Are Query Optimizers, Really?著者についてViktor Leis、Andrey Gubichev、Atanas Mirchev、Peter Boncz、Alfons Kemper、Thomas Neumannらのグループによる論文。ほとんどのメンバーはDBMSにおける最適化について研究しているが、Atanas Mirchevはより統計や探索といった最適化よりの研究をしている。問題意識良い結合順序を見つけることはクエリの性能に対して大きな影響を与えるため、熱心に研究されてきた。古典的なクエリ最適化のアプローチでは以下のステップで動的計画方に基づいた最適化を行なう。1. 有効な結合順序の列挙1. カーディナリティ推定値を入力としたコストモデルの選択理論的にはカーディナリティとコストモデルの推定値が正確であれば、最適なクエリプランを選択することができる。しかし現実にはカーディナリティ推定は一様性や独立性といった単純化された仮定に基づいており、しばしばそのような仮定は間違っているため悲惨な計画を作成する。手法この論文ではカーディナリティ推定器の評価と正確なコストモデルの重要性の評価、そして列挙された結合順序の空間がどの程度影響するのかを以下の方法で検証し、貢献を行なっている。1. IMDBデータを用いたJoin Order BenchmarkというJOINにフォーカスしたベンチマークによる評価を行なう1. 実世界のデータセットにおける現実的なクエリを用いたE2Eの検証を行なう。1. クエリ性能に対するカーディナリティ・コストモデル・列挙アルゴリズムの貢献度を定量化し、最適なクエリプラン生成のためのガイドラインを策定している。作業時間read29:3829:38author33:083:30summary48:4414:36感想時間が無くまとめ途中で切り上げてしまった。やらないよりマシではあるものの、ちゃんと纏めるときにくらべて理解度に影響が出そうなので時間に余裕を持っておきたい。内容自体はGW中にPostgreSQLの実装を読んでいたこともあり、わりと理解しやすかった。

クエリオプティマイザの精度を検証した論文を読みました

この記事の趣旨1998年に発表されたクエリオプティマイザの基礎としてとくに重要な手法をまとめた論文を読みました。An Overview of Query Optimization in Relational Systems著者についてSurajit Chaudhuriによる論文Microsoft所属の研究者でRDBMSの研究を行なっており、近年ではCloudにおけるDBMSの研究を行なっている。概要RDBMSが提案された1970年代からクエリ最適化は大規模で幅の広く研究が行なわれてきた。この論文では執筆当時(1998年)までの重要な研究の基礎を説明している。手法探索空間統計情報とコストの推定列挙アルゴリズムアルゴリズムについて説明している。論文内では拡張可能なオプティマイザとして、StarburstとVolcano/Cascadeの2種類のオプティマイザの詳細を論じている。最新(当時)の最適化リアライズドビューについて説明している。作業時間read31:4031:40author33:402:00summary52:5519:15感想ベクトル化やパラレルジョインで扱われていたVolcanoオプティマイザの端に触れることが出来ました。内容としては基礎的な内容が多いものの、知らない概念もいくつかあり引用している論文も読みたいです。クエリ最適化の基礎を学ぶのに非常にいい内容でした。

現代のクエリオプティマイザの基礎となる技術をまとめた論文を読みました

この記事の趣旨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 10Table 11Table 12PostgreSQLに比べMonetDBが優れている理由はPostgreSQLの行指向データを列指向に変換するコストのためである。作業時間read31:2131:21author35:384:17summary70:1334:35感想論文出版時にはTPC/IPプロトコルが前提でQuic登場前のため、ネットワークプロトコル自体は考慮されていない。現在であればTPC/IPとQuicに適合した手法の比較が行なわれると思うので気になるところ。

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

この記事の趣旨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命令が一般SQLに置き換えられることでUDFに対して、SQLに用いられていた高度な最適化を導入することが出来る。また提案手法ではい以下の理由から、SQLとして命令を置換するときにクエリ最適化時に行なうのではなくバインド時に置換をしている。1. 実際のワークロードでの実験ではほぼ全てのケースでバインド時のほうが性能がよかった1. クエリオプティマイザの変更が不要1. バインディング時に特定の最適化を行なえるとくにクエリオプティマイザの変更はSQL Serverが商用データベースなため重要であった。作業時間read28:5028:50author32:103:20summary57:0024:50

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

この記事はDBMSの登場以前から現代のDBMSを取り巻く環境までを振り返ることで、なぜNewSQLが必要とされ登場したのかをまとめます。 おことわり筆者はあくまでDBMSユーザーであり、研究者ではないため内容は個人の見解です。また対象読者はある程度DBMSに関わりがあり、OLTPやOLAP、列指向や行指向といった基本的な単語を理解しているものとします。またNewSQLの技術的詳細はスコープ外とします。 DBMS以前データベースという言葉は1950年代に米軍が情報基地を集約したことに由来します。一方で学術的なデータベースの起源はW. C. McGeeが1959年に発表...

DBMSの歴史とNewSQL

この記事の趣旨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の「実行中に効率的に実行でき、ディスクのに永続化する必要のないパフォーマントインデックスを必要とする。」という要素の考慮を除いている。またオプティマイザについては既存のコストベースのものを拡張し適応している。提案手法では潜在的に成長している結合のカスケードを最悪の場合の最適結合に置き換えることで、最適化されたバイナリ結合計画を洗練させるヒューリスティックなアプローチを提案している。通常の結合順序最適化で使用されるのと同じカーディナリティ推定値に基づいて、中間テーブルが膨大になる結合を特定する。作業時間read22:1322:13author25:483:35summary52:5826:50感想とても難しい内容に感じてしまい、殆ど頭を通りすぎてしまった気がする。今まで最適化は触れずに来たため、理解が浅い領域だった。よくよく考えるとDBMSの話しに最適化が登場するのはあたりまえなので、今後はその方面にも触れて行きたい。

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

この記事の趣旨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. ソートフェーズの評価SIMDソートアルゴリズムとC++のSTLソートアルゴリズムを比較している。マージフェーズの評価入力サイズの調整によるマージフェーズの最適化パーマンスを検証している。ソートマージジョインにおける影響要因の特定結果結合対象のデータサイズに拘わらずハッシュによる結合がソートベースの結合のパフォーマンスを上回っている。Figure 14ソートマージによる結合は入力サイズが著しく大きくなったときのみハッシュ結合のパフォーマンスに近づく。Figure 15ソートマージ、ハッシュ結合におけるデータの偏りはパフォーマンスに大きな影響を及ぼさなかった。Figure 16いずれのアルゴリズムも物理的なコア数では線形にスケールした。Figure 17作業時間read23:1123:11author27:093:58summary60:1232:57

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

この記事の趣旨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. パーティションベースハッシュジョインパーティションに分割し結合する手法。ハッシュテーブルの構築と結合されるデータの探索のキャッシュミスを最小にする事を目的としている。非パーティションベースハッシュジョインパーティションテーブルを構築しながら結合を行なう手法で、マルチスレッドと順番に依存しない実行によりキャッシュミスのパフォーマンス劣化を隠蔽している。ソートマージジョインSIMDによりベクトル化される。検証ではこれらの結合方法を以下の3つのテストで使用するために、全部で13のアルゴリズムを検証している。1. ブラックボックス比較ブラックボックス的に比較する。ホワイトボックス比較ブラックボックス比較で検証する結合方法に先行研究で示された最適化を施した上で比較を行なう。パラレルラディックスジョイン比較Table 2結果パーティション結合の一種であるリモート書込みを排除したCPR系アルゴリズムは小さな入力に対して有効ではないスケールの大きい結合ではとくに理由が無い場合、パーティションベースのジョインを利用する大きなサイズのページを利用するソフトウェアライトコンバインバッファ()を利用するパーティションジョインでは適切なパーティションビットを利用するできるかぎりシンプルなアルゴリズムを利用するNUMAを考慮したアルゴリズムを利用する実行時間とクエリ時間は同一ではない作業時間read31:3431:34author35:183:46summary77:5042:32

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

この記事の趣旨2018年に発表された"Everything You Always Wanted to Know AboutCompiled and Vectorized Queries But Were Afraid to Ask"という論文を読みました。最新のクエリエンジンの特性をまとめ、どのようなワークロードに向くのかという指針を示すないようです。Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to AskTimo 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. 異なるハードウェアでのパフォーマンス結果インメモリOLAPワークロードでのマイクロアーキテクチャ分析Figure 3: Performance – TPC-H SF=1, 1 threadSIMDの利点の検証SIMDを評価するにはTectorwiseのみを用いた。SIMDではスカラーなデータをベクトルに変換するペナルティは少く、最大8.4倍の性能向上が確認された。Figure 6: Scalar vs. SIMD Selection in TectorwiseマルチコアCPUにおけるクエリ並列化異なるハードウェアでのパフォーマンスIntel Skylake、Intel Knights Landing、AMD Ryzenで対照実験を行なったものの、いずれのハードウェアでもTyper、Tectorwiseともに有効に動作した。作業時間read29:2629:26author33:233:57summary76:3742:44感想VoectorwiseとHyperのいずれを使うべきか。どちらが優れているかといった疑問に答えるないようだった。

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

この記事の趣旨2020年に提案された"Make the most out of your SIMD investments: counter control flowdivergence in compiled query pipelines"という論文を読みました。SIMDによるベクトル処理の最適化とRDBでの応用について扱った、最適化に関する論文です。Make the most out of your SIMD investments: counter control flow divergence in compiled query pipelinesHarald 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()コードを入力の一部に適用する方法で、制御フローを前のオペレータに戻し、アクティブなデータ断片のみをベクトルレジスタに残すことで実行を延期している。作業時間read29:4029:40author33:404:00summary60:0426:36感想前回に引続き個人的には難しいと感じる論文だった。2000年前後の提案にくらべ、2015年前後の論文ではハードウェアアーキテクチャを中心とした手法がピックアップされている。単純に自分の知識不足、理解力不足なので勉強するしかない。

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

この記事の趣旨"Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework forthe Many-Core Age"という2014年に発表された、多コアサーバにおけるクエリ最適化手法をあつかった論文を読みました。[Morsel-Driven Parallelism: A NUMA-Aware QueryEvaluation Framework for the Many-Core Age](https://15721.courses.cs.cmu.edu/spring2023/papers/07-scheduling/p743-leis.pdf)Viktor Leis, Peter Boncz, Alfons Kemper, Thomas Neumann著者についてViktor Leis、 Peter Boncz、 Alfons Kemper、Thomas Neumannのグループによる研究いずれもデータベースと 高速化かを中心に研究している。問題意識コンピュータアーキテクチャの進化にともない、二つのあたらしい問題が生じた。多コアを利用するためにクエリを数百のスレッドに均等に分散させるそれをNUMA(Non-Uniform Memory Access)による順序通りではないメモリアクセスで実現する必要がある。これらの要因からplanベースの並列処理による不可分散とコンテキストスイッチとボトルネックが問題になりスケールが難しかった。NUMAによってデータとアクセススレッドがどのチップに配置されるかによって、データ項目のアクセスコストが異なるため、コンピュータ自体がネットワークになっており、多コア並列化では、RAMやキャッシュ階層を考慮する必要がある。この論文ではMoral-drivenクエリ実行フレームワークを提案している。手法提案手法は並列クエリ処理のため、morselドリブンクエリ評価フレームワークを提示した。これはメニーコア時代の分析クエリ性能の主要なボトルネックである負荷分散、スレッド同期、メモリアクセス局所性およびリソース弾力性を解決することを目的としている。ベースとなるアイデアは以下の2つに分けられる。メモリ上のデータをmorselと呼ばれる小さなバッチに分割し、バッチごとに処理を実行したあとにそれぞれの処理結果をグローバルハッシュテーブルとしてまとめる。Figure 3: NUMA-aware processing of the build-phaseディスパッチャと呼ばれる並行パイプライン制御を行ない、ワーカースレッドをタスクに割り当てるFigure 5: Dispatcher assigns pipeline-jobs on morsels to threads depending on the coreまとめとして著者はきめ細かいスケジューリング、完全演算子並列化、低オーバーヘッド同期、NUMA対応スケジューリングの原理を用いて、他のシステムでもメニーコアスケーリングを改善できると示唆している。作業時間read28:3628:36author32:453:09summary60:3727:52感想近現代のサーバアーキテクチャで主流になっているNUMAでのクエリパフォーマンス向上のための論文のため、古典的なものに比べ概念が難しいものが多い。もう少し理解を深めたい。

NUMAアーキテクチャでのクエリ最適化に関する論文を読みました

この記事の趣旨"MonetDB/X100: Hyper-Pipelining Query Execution"という2005年に発表された、列指向DBMSを提案した論文を読んでいきます。分析ワークロード向けRDBMSにおける初期実装であるMonetDBを扱った論文で、提案時期が2005年と古くはあるものの現代のDWHの礎となる内容です。MonetDB/X100: Hyper-Pipelining Query ExecutionPeter Boncz, Marcin Zukowski, Niels Nes著者についてPeter Boncz、Marcin Zukowski、Niels Nseのグループによる論文。いずれの著者も機械学習や分析におけるDBMSについて研究している。問題意識2005年当時のDBMSは他のアプリケーションに比べ、IPCが低くなる傾向にあった。原因はほとんどのDBMSがコンパイラの最適化を阻害する実装だったためである。これはRDBMSが実装された当時に比べCPUやコンパイラが発達したためで、この論文ではC-store DBMSであるMonetDBと従来のR-store DBMSをそれぞれTPC-Hで評価を行い、パフォーマンス阻害要件と最適化方法を提案している。手法CPUによるIF文の処理方法はDBMSにとっては選択性が低く、そういった実行は予測不可能でありクエリ実行を著しく劣らせた。提案手法ではMonetDB/X100として効率的なシーケンシャルアクセスに向けた、C-storeストレージとクエリエンジンを実装した。RAMは提案手法のデータアクセスと同様の方法で圧縮して保存し、Cacheではなベクトル化された処理にもとづくパイプライン実装を使用した。CPUにおいてもベクトル型における式計算を提供し、コンパイラが高効率な処理を生成した。結果として提案手法は従来のDBMS実行に比べTPC-Hで優れた性能をしめした。作業時間read21:3221:32author29:007:28summary56:2027:20感想2005年と古く、またVolcano-likeなど知らない概念も登場した。提案内容としては現代のDWHが採用しているものだった。論文外の感想今回本文を読む時間を大幅に短くしてみたが、それにともない理解度も低下した気がする。やっぱり30分以上で読むのがよさそう。

列指向DBMSにおけるデータを提案した論文を読みました

この記事の趣旨"Integrating Compression and Execution in Column-Oriented Database Systems"という2006年に発表されたそれまで行指向DBMSで培われてきた圧縮方法による、検索高速化手法を列指向DBMSに適用・評価した論文を読んで行きます。Integrating Compression and Execution in Column-Oriented Database SystemsDaniel J. Abadi, Samuel R. Madden, Miguel C. Ferreira著者についてDaniel J. Abadi、Samuel R. Madden、Miguel C. Ferreiraのグループ。それぞれDBMSやデータ分析に関連する手法やパフォーマンスについて研究している。問題意識2006年ごろの研究ということもありC-storeデータベースの研究が少なかった時期の論文。既に検索パフォーマンスに寄与することがしられていたR-storeデータベースの圧縮手法を、C-storeへ応用や評価を行なった。手法提案手法は以下の圧縮技術の組み合わせからなる。Null圧縮辞書エンコーディングRun Lengthエンコーディングビットベクターエンコーディングエンコーディングで、それぞれのカテゴリに属するかどうかをバイナリで表現する圧縮方法Lempel-ZivエンコーディングGZIPでも使用されている圧縮方式。データの非重複ブロックを解析して既存のデータは対応するブロックへのポインタに、それ以外のみを新規に追加する。提案手法は圧縮方式が増えてもアクセスパターンをシンプルに留めるためにアクセス方法をAPIとして隠蔽した。そのため異なるエンコーディングも同一のAPIで保存でき、同一のAPIでも取得できる。当然ながら一つのエンコーディングで全てのデータに対応することは難しく、論文では使用すべき圧縮スキームの選び方を以下のようにまとめている。Figure10感想C-storeにおける古典的な圧縮手法がまとまった論文だった。近代DWHを利用する側では意識することが少ない部分だったためあたらしい知識も多かった。作業時間read26:5026:50author33:306:40summary58:2024:50

列指向DBMSにおけるデータ圧縮手法の論文を読みました

この記事の趣旨前回と同様にCMU Advanced Databas Systems Spring2023のReading Assignmentとして出ている論文を読んで行きます。最近論文を読めてなかったのですが、この記事でモーベーションが上がったので再開しました。ころころやり方を変えるのはよろしくないものの、モチベーションのために先の記事のやり方でやります。今回はColumn Sketchという名前のIndex手法を提案した論文です。Lossy Compressionを採用した当手法がどのように、高速で堅牢な検索を実現しているのかについて述べています。Column Sketches: A Scan Accelerator for Rapid and Robust Predicate EvaluationBrian Hentschel, Michael S. Kester, Stratos Idreos著者についてBrain、Michael、Stratosのグループによる論文。いずれも機械学習とデータアクセスについて研究している。問題意識既存のindex手法ではそれぞれに得意/不得意があり多くのアクセスパターンに対応できる方法がなかった。またデータ分析で用いられるような列指向ストレージに対応しているものが少なかった。Column SketchはデータをLossy Compressionを使用してindexを作成する手法でこれらの問題を解決した。手法提案手法はデータを任意のbit長に変換し、bitで表わされたデータに対して初回の検索を行なうことで大幅に検索速度を向上させた。またこの手法は数値型のみではなく、varcharなどで表わされたカテゴリカルタイプを数値として扱うことで、データ分析に必要なデータタイプに対応している。提案手法は8bit数値型であれば以下のようなマッピングによって達成される。for x, y ∈ I8, S (x) ≠ S (y) ⇒ x ≠ yfor x, y ∈ I8, S (x) < S (y) ⇒ x < y以下の図は8bitデータに対してWHERE x < 90がどのようにindex作成され評価されるかの例である。Figure2: Column Sketchindex作成段階では数値をレンジベースで任意の個数のbitに圧縮する。そして評価時には90を含むデータより大きい値をすべて取得し、90を含むレンジに対しては個別に評価を行なう。感想読んでいる段階では数値型のみに対応したindexであれば、B-treeで十分ではないかと思ったものの読み進めていくと限定的ながらも文字型にも対応していて、分析用途では必要な機能が備わっているなと思った。全文テキスト検索のような用途には応用が難しそうで、銀の弾丸はないなと感じた。作業時間read27 min27 minauthor32 min5 minsummary58 min26 min論文以外への感想今回採用した論文の読み方をやってみた思ったのは事前に1時間で読んでまとめるぞと決めたことで随分集中して論文を読めました。あと今まで論文を原文で読まなきゃという個人的な使命感があったのですが、翻訳することで随分効率があがったので今後は翻訳してしまおうと思いました。Readableは文末のrea-dableのような表記や翻訳されない部分(おそらく数式を含む文章？)があるものの、フォーマットが維持されているため原文と照しあわせながら読めば非常に効率がよかったです。毎日論文読むなら正直買いです。毎日論文読みたいので課金しました。がんばるぞ!

Column Sketchesというindex手法の論文を読みました

この記事の趣旨前回と同様にCMU Advanced Databas Systems Spring2023のReading Assignmentとして出ている論文を読み論文紹介のやり方 / How to reviewで紹介されている方法をまとめていきます。今回はBigQueryやSnowflake、Amazon Redshiftといった分析向けデータベースが採用している行指向ストア(Column-store)と列指向ストア(Row-store)の差と行指向ストアがのどうのような最適化がパフォーマンスに影響を与えているかについて扱った論文を読んで行きます。Column-Stores vs. Row-Stores: How Different Are They Really?研究全体の背景行指向データベースシステムは分析用ワークロードで列指向データベースシステムより優れたパフォーマンスを発揮することで知られている。なぜなら行指向ストアはクエリ実行に必要なデータのみをディスクまたはメモリから取得するため、優れたI/Oパフォーマンスを達成できるからである。問題意識垂直パーティショニングや全ての行をパーティショニングすることで、列指向データベースで行指向データベースのようなパフォーマンスを実現できるだろうか？ また行指向データベースが高速に動作するのはどのような最適化手法の影響が大きいのか？論文の目的列指向データベースで垂直パーティショニングやクエリ実行で使われる全ての行にインデックスを張るなどして、擬似的に行指向データベースを再現することで分析用途でのパフォーマンスが向上するのか？ また行指向データベースの高速化に用いられるテクニックを一つずつ無効化し、パフォーマンスを比較することでどのような要素が行指向データベースのパフォーマンスを向上させているかを検証しする。手法の説明Star Schema Benchmarkを用いてC-Storeと商用列指向データベースの比較を行う。リアライゼーション、ブロックプロセッシングをそれぞれ無効化しどの要素の影響が最も大きいか。またこの論文で提案されたinvisible joinの評価を行なう。結果列指向ストアに置けるマテリアライズトビューリアライズドビュー(MV)に比べ非常に優れたパフォーマンスを発揮する。一方でCSの一つの行にMVとして期待するアウトプットのタプルをStringとして保存すると、普通のRSよりも低いパフォーマンスとなる。 RS MV > RS > CS MVとなる。列指向ストアに行指向ストアを再現する一般的な列指向のアプローチを適用し、効果的であればbitmap1またはbloom filter2を適用する(T)一般的な列指向のアプローチを適用するが、bitmapを積極的に使用する(T(B))一つのテーブルを複数のテーブルとして垂直分割を行う(VP)全ての行にインデックスを貼り、値の読み込みは全てインデックス経由で行う(AI)結果としては平均してMV > T > T(B) > VP > AIとなる。列指向ストアに置ける最適化手法とその影響列指向ストアの最適化手法においてどの影響が大きいかを測定するためそれぞれを無効化することで検証を行なう。測定対象の最適化項目としては以下の4つを対象とする。ブロックプロセッシングの有効化(B)または無効化(b)Invisible joinの有効化(I)または無効化(i)保存時のデータ圧縮の有効化(C)または無効化(c)遅延マテリアライゼーションの有効化(L)または無効化(l)結果は平均するとBICL > bICL > BiCL > biCL > BicL > bicL > biclとなる。まとめと考察既に知られていたように行指向ストアは列指向ストアに対して常に優れたパフォーマンスを発揮した。リアライゼーションとデータの圧縮はパフォーマンスの改善に大きく影響した。ブロックプロセッシングやInvisible Joinも上記の二つに比べると影響は小さいものの最適化として有効に働いた。Oracle Document 索引↩Bloom Filters↩

行指向と列指向の違いについての論文を読む

この記事の趣旨前回と同様にCMU Advanced Databas Systems Spring2023のReading Assignmentとして出ている論文を読み、感想と抄訳のようなものにまとめます。まとめていたのですが、そもそも全体をまとめてしまっていいのか？ 文量もふえてしまうので論文紹介のやり方 / How to reviewで紹介されている方法を参考にやっていきます。ただし実装論文が対象なので手法の説明は厚めにとりあげ、結果については省略します。今回は近年DWHとして存在感を増しているSnowflakeがどのようなアーキテクチャを取っているか、そしてどのように分散システムの上にデータベースシステムを構築しているかについての内容になります。https://15721.courses.cs.cmu.edu/spring2023/papers/02-modern/vuppalapati-nsdi22.pdfBuilding An Elastic Query Engine on Disaggregated Storage研究全体の背景Cloud技術をベースとしたデータウェアハウス(DWH)であるSnowflakeの運用経験に基づいた論文。Snowflakeは計算リソースとストレージの柔軟性、マルチテナント、高いパフォーマンスを目的にデザインされている。この論文ではSnowflakeが設計と実装においてどのようにCloud技術を応用し目的を達成しているかについて書かれている。問題意識既存のクエリ実行エンジンやDWHではShared-nothing方式を採用することでデータをノードに分散させ、処理をスケールさせたり高いパフォーマンスを実現していた。一方でワークロードによって要求のことなる各種コンピュータリソースを適切に分配することが難しい、Shared-nothingによる静的にパーティションされたデータでは要求によってノードを増減させることが難しいという問題があった。論文の目的SnowflakeがどのようなアーキテクチャによってShared-nothingが抱える問題を解決し、またクエリプランニングと最適化、同時実行制御を行っているのかの実装をまとめ、紹介している。手法の説明設計の概要Snowflakeでは永続(persistent)データと中間(intermediate)データで扱かいを変えている。Figure1: Snowflake (Virtual) Warehouse Architecture一時ストレージの設計SSDで構成されている。一時データは可能な限りメモリに保存されメモリで保持しきれないデータはスワップ領域のようにSSDに保存される。さらにSSDの空き容量が枯渇した場合、一時的に永続ストレージに保存される。一時ストレージは永続化が不要なデータの保管以外にも永続化データのキャッシュとしても機能する。このキャッシュは日和見的(opportunistically)キャッシュと呼ばれており、その理由は中間データを常に優先するからである。クエリスケジューリングユーザーからのクエリはサービスエンドポイントでパース、実行計画の生成、最適化、実行に必要タスクの生成が行なわれ、ここで生成されたread/writeを含むタスクは計算リソースに割り振られ、計算リソースから必要に応じて一時、永続ストレージからのデータ取得が行なわれる。このときタスクの割り振りは一時ストレージが対象の永続データをキャッシュしているかも考慮される。またSnowflakeは Work stealingという他ノードに割り振られたタスクをあるノードの方が速く処理できる場合、臨機応変にタスクを実行するしくみがある。リソースの柔軟性ストレージと計算リソースを分離することでSnowflakeはそれぞれを独立してスケールアウトさせている。ストレージの柔軟性はデータストアであるS3に委任している一方で、計算リソースの柔軟性は事前に暖気運転されたノードプールによって実現している。Snowflakeでは永続データのキャッシュ時に保存されるノードが決っている一方で、対象となるデータをキャッシュするノードがない場合、一時的にほかのノードにタスクを割り振り計算リソースがスケールし対象となるデータがキャッシュされた時に再度タスクを割り当てるという機能が存在する。まとめと考察SnowflakeはS3を永続ストレージとして使用、VM全体を計算リソースとそのメモリ、スワップ領域とみなすことでスケーラビリティと高いパフォーマンスを実現した。とくに日和見的キャッシュとタスクスケジューリングメカニズムはShared-nothing方式の抱えていた、リバランスの問題を解決した。Snowflakeが現在達成できていないマルチテナントや計算リソースの高いユーティリゼーションの実現方法としてあげている手法をとっているため、今後の機能追加が競争力維持のために重要となる。

Snowflakeの論文を読む

CMU Advanced Database Systems Spring2023のReading Assignmentを読む part1

SQL*Loaderで複数の文字コードが混ざったデータをロードする 概要単一のテキストファイル内で特定のカラムのみ文字コードが違うファイルをSQL*Loaderでデータベースに取り込む方法 注意本記事で扱っている対処方法はおそらく紛れ込んだ文字コードが本来あるべき文字コードの一部として解釈できない場合使用できないと思います。(未検証)最低限文字化けしながらも読み込める状態を想定しています。 結論コントロールファイル内で文字コードの変換が必要なカラムに以下の関数を適用する。column "CONVERT(:column, 'target_charset', 's...

SQL*Loaderで複数の文字コードが混ざったデータをロードする

Oracleインストール中にでたSysctl系エラーであたったkernel parameterについてTable of ContentsOracleインストール中にでたSysctl系エラーであたったkernel parameterについてMotivationそもそもsysctlとは何なのか？Oracleセットアップ中に遭遇したkernel parameterssemopm変更方法セマフォ(semaphore)とは？SEMSMLSEMMNSSEMOPMSEMMNIfile-max変更方法rem_default/rem_max/...