ブログ@nnaka2992

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

CMU_Advanced_Database_Systems

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

この記事の趣旨 2020年に発表されたBigQueryの元となったGoogle内で利用されている分析向けデータベースであるDremel の実装を解説した論文を読みました。 Dremel: A Decade of Interactive SQL Analysis at Web Scale 著者について Sergey Melnik, Andrey G…

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

この記事の趣旨 2015年に発表されたクエリオプティマイザにおけるカーディナリティ推定とコストモデル、列挙アルゴリズムの貢献度を 評価した論文を読んでいきます。 How Good Are Query Optimizers, Really? 著者について Viktor Leis、Andrey Gubichev、At…

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

この記事の趣旨 1998年に発表されたクエリオプティマイザの基礎としてとくに重要な手法をまとめた 論文を読みました。 An Overview of Query Optimization in Relational Systems 著者について Surajit Chaudhuriによる論文 Microsoft所属の研究者でRDBMSの…

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

この記事の趣旨 2017年に出版されたリモートDBMSとクライアント間の大量データ転送を最適化する 手法を提案する論文を読みました。 Don’t Hold My Data Hostage – A Case For Client Protocol Redesign 著者について Mark Raasveldt、Hannes Muhleisenらのグ…

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

この記事の趣旨 2017年に発表されたSQL ServerでUDFを最適化しているFroidという手法についての論文を読みました。 Froid: Optimization of Imperative Programs in a Relational Database 著者について Karthik Ramachandra、Kwanghyun Park、K. Venkatesh …

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

この記事の趣旨 2018年に発表された分析ワークロードなどで発生しがちな最終結果に比べ、非常に大きな中間結果を 作成してしまうクエリを多方向結合で最適化する論文を読みました。 Adopting Worst-Case Optimal Joins in Relational Database Systems 著者…

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

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

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

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

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

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

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

この記事の趣旨 2020年に提案された"Make the most out of your SIMD investments: counter control flow divergence in compiled query pipelines"という論文を読みました。 SIMDによるベクトル処理の最適化とRDBでの応用について扱った、最適化に関する論…

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

この記事の趣旨 "Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age"という2014年に発表された、多コアサーバにおけるクエリ最適化 手法をあつかった論文を読みました。 [Morsel-Driven Parallelism: A NUMA-Aware…

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

この記事の趣旨 "MonetDB/X100: Hyper-Pipelining Query Execution"という2005年に発表された、 列指向DBMSを提案した論文を読んでいきます。 分析ワークロード向けRDBMSにおける初期実装であるMonetDBを扱った論文で、提案時期が 2005年と古くはあるものの…

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

この記事の趣旨 "Integrating Compression and Execution in Column-Oriented Database Systems"とい う2006年に発表されたそれまで行指向DBMSで培われてきた圧縮方法による、検索高速化手 法を列指向DBMSに適用・評価した論文を読んで行きます。 Integratin…

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

この記事の趣旨 前回と同様に CMU Advanced Databas Systems Spring2023のReading Assignmentとして出ている論文を 読んで行きます。最近論文を読めてなかったのですが、この記事 でモーベーションが上がったので再開しました。 ころころやり方を変えるのは…

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

この記事の趣旨 前回と同様に CMU Advanced Databas Systems Spring2023のReading Assignmentとして出ている論文を 読み論文紹介のやり方 / How to review で紹介されている方法をまとめていきます。 今回はBigQueryやSnowflake、Amazon Redshiftといった分…

Snowflakeの論文を読む

この記事の趣旨 前回と同様に CMU Advanced Databas Systems Spring2023のReading Assignmentとして出ている論文を 読み、感想と抄訳のようなものにまとめます。まとめていたのですが、 そもそも全体をまとめてしまっていいのか? 文量もふえてしまうので 論…

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

CMU Advanced Database Systems Spring2023とは カーネギメロン大学(CMU)ではAdvanced Database Systemsという講義が開講されており、特に2023年1月始まりの講義です。 講義の内容はモダンなDBMSの内部実装を学んで行くコースとなっており、データベースの歴…