2020 CPU15-721 reading list

Topic 25: Databases on New Hardware - 2022/02/28

Paper : J. Arulraj, et al., Write-Behind Logging, in VLDB, 2016

Commit protocol

Group commitはシステム内で高々1個しか走っていないことを前提としている(?)

変更毎にlog recordを作成する必要は無く、group commit毎に1 record作成すれば良い

Note

2022現在、WBLの恩恵にあずかれそうなNVMは登場していないように思われる。 Intel Optane Persistent Memory (DCPMM)はrandom access速くない。

Topic 24: Server-side Logic Execution - 2022/02/14

Paper : K. Ramachandra, et al., Froid: Optimization of Imperative Programs in a Relational Database, in VLDB, 2017

Topic 23: Larger-than-Memory Databases - 2022/02/07

Paper : V. Leis, et al., LeanStore: In-Memory Data Management beyond Main Memory, in ICDE, 2018

実験結果から、バッファプールからのRandom evictionとLeanEvictの差がそれほど大きくない（最大0.5%）。 それならRandomでよいのでは？

Topic 22: Cost Models - 2022/01/31

Paper : V. Leis, et al., How Good are Query Optimizers, Really?, in VLDB, 2015

Summary

relational database systems produce large estimation errors that quickly grow as the number of joins increases, and that these errors are usually the reason for bad plans. In contrast to cardinality estimation, the contribution of the cost model to the overall query performance is limited.

Estimates for Joins

we observed different cardinality estimates of the same simple 2-join query depending on the syntactic order of the relations in the from and/or the join predicates in the where clauses!

Maybe because of calculation errors?

Better Statistics for PostgreSQL

the trend to underestimate cardinalities becomes even more pronounced. The reason is that the original, underestimated distinct counts resulted in higher estimates, which, accidentally, are closer to the truth. This is an example for the proverbial “two wrongs that make a right”, i.e., two errors that (partially) cancel each other out. Such behavior makes analyzing and fixing query optimizer problems very frustrating because fixing one query might break another.

join cardinarityの推定誤差が大きいため、各カラムが正しいdomain cardinarityを持っていても、最終的なjoin cardinarityの推定誤差は安定しない。 こうした挙動が、クエリオプティマイザの修正結果の予測を難しくし、分析を複雑化する要因となっている。

Notes

Topic 21: Optimizer Implementation (Alternative Approaches) - 2022/03/28

Paper : B. Ding, et al., Plan Stitch: Harnessing the Best of Many Plans, in VLDB, 2018

Assumptions

Automated Indexing continuously monitors and analyzes query workloads, and periodically recommends index configurations. As indexes are incrementally implemented, different plans get executed

Note

Topic 20: Optimizer Implementation (Top-Down vs. Bottom-Up) - 2022/01/17

Paper : Yongwen Xu, Efficiency in the Columbia Database Query Optimizer (pages 1-35), in Portland State University, 1998

Topic 19: Optimizer Implementation (Overview) - 2021/12/20

Paper : S. Chaudhuri, An Overview of Query Optimization in Relational Systems, in PODS, 1998

Optimizer Generator

Cascade Optimizer

Topic 18: Parallel Join Algorithms (Sorting) - 2021/12/13

Paper : C. Balkesen, et al., Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited, in VLDB, 2013

Multi-way mergingのway数を増加することで、メモリ帯域の負荷を軽減しコンピュート負荷を増大する方向にチューニングできる。

Topic 17: Parallel Join Algorithms (Hashing) - 2021/12/06

Paper : S. Schuh, et al., An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory, in SIGMOD, 2016

Summary

We immediately observe that even for this relatively simple query a major part of the runtime is spent in the non-join parts of the query. The time spent in the actual join is only about 10%–15% of the total runtime

Notes

Topic 16: Vectorization vs. Compilation - 2021/11/22

Paper : T. Kersten, et al., Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask, in VLDB, 2018

Topic 15: Vectorized Execution - 2021/11/29

Paper : O. Polychroniou, et al., Rethinking SIMD Vectorization for In-Memory Databases, in SIGMOD, 2015

SIMDは実世界のRDBMSでどの程度使用されているか? -> vector wiseやDB2のカナムナストアで使用されている

Topic 14: Query Compilation - 2021/11/15

Paper : T. Neumann, Efficiently Compiling Efficient Query Plans for Modern Hardware, in VLDB, 2011

Reference

my note

Topic 13: Query Execution & Processing - 2021/11/01, 08

Paper : M. Kester, et al., Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?, in SIGMOD, 2017

Modeling In-Memory Shared Scan

Topic 11: Networking Protocols - 2021/10/18

Paper : M. Raasveldt, et al., Don’t Hold My Data Hostage: A Case for Client Protocol Redesign, in VLDB, 2017

Result Set Serialization

postgres result set wire format

Hive result set wrire format

Topic 10: Recovery Protocols - 2021/10/11

Paper : P. Antonopoulos, et al., Constant Time Recovery in Azure SQL Database, in VLDB, 2019

Compensation log records (CLR)

Undo処理中のcrash発生時に処理済みのUndoをreplayするためのlog

Recovery protocol

2a Redo lock acquisitionはactive txのロックを獲得する -> Redo後にtxを受け付けるため。

Instant recovery: Redo対象のロックを獲得し、Redo開始と共にtxを受け付ける。 本論文のSQL serverの例ではcheckpoint頻度が高いのでRedoはあまり多くない。

Redo -> parallel Undo -> おそらくparallel?

Oldest Dirty Page LSNはどの時点のLSNか -> ?

Checkpointing

ARIESはDirty Page TableとTransaction Tableを書き出す。Dirty Page自体はcheckpointでは書き出さない。(fuzzy checkpoint)

CTR

Checkpointログの直後に前回のcheckpointからの間に生じたSLogを集約したログを書く。 -> Oldest Transaction Begin LSN -> Min(..)間のlogを処理せず済む

UndoはSLogのみ。Undoは対象のversionにmarkするだけで後でGCする

GCはpage単位

Logical Revert

各versionはstateを持っている Active / Committed / Aborted

Abort処理時は書いたversionをAbortedにするのみ。

Redo Locking Optimization

Recovery中にLockを取りたいケースがある

Questions

constantに近いrecovery timeを実現するために、頻繁にcheckpointをやっているがcheckpointが遅れることはないか?

Topic 9: Database Compression - 2022/03/14

Paper : D. Abadi, et al., Integrating Compression and Execution in Column-Oriented Database Systems, in SIGMOD, 2006

Note

Topic 8: Storage Models, Data Layout, & System Catalogs - 2021/09/27

Paper : M. Athanassoulis, et al., Optimal Column Layout for Hybrid Workloads, in VLDB, 2019

slide

Topic 7: OLTP Indexes (Trie Data Structures) - 2021/09/13

Paper : V. Alvarez, et al., A Comparison of Adaptive Radix Trees and Hash Tables, in ICDE, 2015

奇数木の特徴

JudyL

Bitmap nodeがポインタをインターリーブしている理由は、子ノードへのポインタの追加を高速に行うため。

Quadratic Probing

Open Addressing scheme: ハッシュ値が衝突した時、規則に従ってハッシュテーブルの別の要素をプローブして最初に見つかった空き位置に格納する。

Cuckoo Hash

ハッシュテーブルの枚数を増やすことで、負荷率（ハッシュテーブルの充填率）を上げられメモリ効率がよくなる。 トレードオフとしてread速度が遅くなる。

Bucketingによるメモリ効率の向上はないが、ハッシュの充填率をあげることができることを確認している。 これにより、リハッシュの頻度を下げられる。

Topic 6: OLTP Indexes (B+Tree Data Structures) - 2021/09/06

Paper : Z. Wang, et al., Building A Bw-Tree Takes More Than Just Buzz Words, in SIGMOD, 2018

Bw-Tree

Node search shortcut

Narrowing down search range by the key and the offset attribute of delta while traversing the chain.

Optimistic lock coupling

ロックとバージョンカウンタを使用する。

reference: Viktor Leis, Florian Scheibner, Alfons Kemper, and Thomas Neumann. 2016. The ART of practical synchronization. In DaMoN.

Topic 5: Multi-Version Concurrency Control (Garbage Collection) - 2021/08/30

Paper : J. Böttcher, et al., Scalable Garbage Collection for In-Memory MVCC Systems, in VLDB, 2019

Problem

MVCCシステムにおいて、ロングトランザクションによってGCできず、バージョンチェインが伸びることで 生じる性能低下の問題。 従来のハイウォーターマークのみを管理する手法では、バージョンチェインの途中のガーベジを回収できない。

GC Tracking level

epoch based systemはOLTPのシステムでGCのオーバーヘッドを軽減するのに相性が良い。

Topic 4: Multi-Version Concurrency Control (Protocols) - 2021/08/23

Paper : T. Neumann, et al., Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems, in SIGMOD, 2015

Version access

startTimeを払い出すタイミングをtxの開始時ではなく、最初のread時に払い出すことで、 新しいバージョンを読める可能性が上がり、readの性能が向上する可能性がある。

Serializability Validation

Summary

Read intensiveなワークロードでは、自txのread predicateと他txのWrite setを比較することで、 自分のRead setを再スキャンするよりvalidationのオーバーヘッドを計算量、スペース共に低減することができる。

Misc

SIGMOD 2019の AOCC (adaptive optimistic concurrency control) という論文で、hyperのconflict checkの方式を部分的に採用してる。 Read setが大きくなるような (OLAPもあるような) ワークロードでは有利だが、Read setが小さいOLTP的なワークロードだと Predicate setの並行制御がボトルネックになることがある。

Topic 3: Multi-Version Concurrency Control (Design Decisions) - 2021/08/16

Paper : Y. Wu, et al., An Empirical Evaluation of In-Memory Multi-Version Concurrency Control, in VLDB, 2017

Summary

従来はOLTPのスケーラビリティ向上のためにはConcurrency control protocolが最重要と考えられていたが、 実はVersion Storageの設計がより性能に大きな影響を与えていると考えられる。

Concurrency Control Protocol

MVTO

MVOCC

MV2PL + WAIT_DIE

Serialization Certifier (SI + SSN)

Garbage Collection

Epoch-based memory management

Background Vacuuming

定期的にDBをフルスキャンしてガーベジを回収する方法は、大規模DBではスケールしにくい。 latch-freeデータ構造でガーベジを管理し、epochベースで回収する方法や、dirty blockのビットマップを用いて ガーベジの存在するブロックのみをスキャンする（postgresのvisibility mapなど）方法など、ガーベジの 探索方法の工夫が必要。

Cooperative Vacuuming

version chainの走査時に、ガーベジの検出を同時に行う。O2N append onlyストレージのみで使用できる。 スキャン頻度が低いタプルがGCされないdusty corners問題が発生する。

Topic 2: In-Memory Databases - 2021/08/02

Paper : X. Yu, et al., Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores, in VLDB, 2014

Basic T/O

トランザクションtがタプルxに対して、read/writeを行う際に x.MAX_READ_TS/x.MAX_WRITE_TSとtのタイムスタンプを比較して、大きい場合のみread/writeができる。 Repeatable Readのためread時にスレッドローカルにデータをコピーする。

Timestamp Allocation

5.2 write-intensive workload

fig.9b: Useful worklockが多いが、ロックグラフの生成に時間を消費しており、thrashingによって性能が落ちた。

Topic 1: Course Introduction and History of Databases - 2021/07/26

Paper : A. Pavlo, et al., What’s New with NewSQL?, in SIGMOD Record (vol. 45, iss. 2), 2016

背景

2000年代、インターネットアプリケーションの台頭で、同時接続数の大幅な増加や常時オンラインの要件が必要とされるようになり、 DBがボトルネックとなることが多くなりました。 DBのスケールアップでは費用対効果が悪く、スケールアウトにより処理能力を向上する方法が模索されました。 そうした中で現れたのがNoSQLのデータストアです。 トラディショナルなDBMSのモデルでは、性能と可用性を犠牲に一貫性と正確性が重視されましたが、 このトレードオフは多くのWebアプリケーションでは妥当ではないと考えられました。 また、キーによる単純な検索クエリにはSQLはオーバーキルであるという見方もありました。 NoSQLを使う利点は、スケーラビリティのことは気にせず、アプリケーションの開発に専念でき、 高い生産性を実現できることにあると考えられていました。

しかし結局のところ、多くのアプリケーションではトランザクションや一貫性の保証が重要であることがわかってきました。 アプリケーションで一貫性を保証するコストは高く、またトランザクションによる抽象化が人の理解を容易にするため、 生産性が高くなるという意見もあります。 そこで、2010年代になると、NoSQL並みのスケーラビリティを確保しつつ、ACIDを保証するNewSQLが現れました。 2000年代中盤から、VerticaやGreenplumといったOLAP向けDBMSで、スケールアウトに対応するものはありましたが、 これらはOLAP特化のため、この論文ではNewSQLには含めないと述べられています。 NewSQLは、トランザクショナルな読み書き必要とし、データ全体の一部をインデックス走査で読む短時間のクエリが、 異なるインプットに対して繰り返し実行されるといったワークロードをもつアプリケーションに特化しています。

NewSQLの分類

この論文では、NewSQLを以下の3種類に分類にしています。 （ScaleDB, Hekaton, CitusDB, VitesseなどのシングルノードDBMSのストレージエンジン拡張はNewSQLに含めない）

Main memory storage

メモリの大容量化、低価格化を背景に、NewSQLでもメモリベースアーキテクチャのDBが見られるようになってきました。 メモリベースアーキテクチャのアイディア自体は、1980年代から見られましたが、NewSQLで目新しいのは、 メモリフットプリントを抑えるため、2次記憶へのデータの部分書き出しをサポートするといった工夫がみられる点です。

トラディショナルなDBMSでは、トランザクション処理等で大半の処理時間を専有しており、 意味のあるデータ処理を実行している時間は10%以下だった、などといった研究も見られており、 現代のハードウェアに合わせたアーキテクチャの見直しによって、DBMSの大幅な性能向上も期待されるところです。 OLTP Through the Looking Glass, and What We Found There

Sharding / Partitioning

ともにホモジニアスなクラスタ構成をとる、NuoDBとMemSQLのシャーディング戦略について解説しています。 NuoDBでは、Transaction Engine（TE）が、Storage Manager（SM）によって分割されたデータブロック（atom）をキャッシュしており、 またデータが同じTEによって処理されやすくなるようなロードバランシングを行っています。 結果として、NuoDBでは事前のパーティショニングやテーブル間の関係なくして、他の分散DBMSと同様のパーティショニングを実現しています。

また、MemSQLでは、クエリ実行のみの集約ノードと、データを格納するリーフノードという構成をとり、リーフノードにクエリをプッシュダウン することで、ノード間のデータ転送量を削減しています。

これらのNewSQLでは再パーティショニングなしで、ノード追加が可能です。（NuoDBのTE、MemSQLの集約ノード）

また、パーティションのライブマイグレーションといった、再パーティショニングの運用負荷を低減する仕組みもNoSQL / NewSQLではみられます。

Concurrency control

ほとんどのNewSQLは、デッドロック検知の難しさから2PLを避ける傾向にあります。 最近では代わりに、Timestamp Ordering（TO）をベースにしたものが多いです。 NewSQLで広く用いられるプロトコルとして、ロングランニングなリードオンリークエリを、ライトをブロックせずに 実行できるという利点から、decentralized multi-version concurrency controlが用いられています。

Google Spannerのコンカレンシコントロール実装は一石を投じるもので、ベースは2PL + MVCCですが、ユニークな点として GPSや原子時計といったハードウェアにより、高精度の時刻同期を実現しています。 Spannerの登場により、従来は分散DBMSに向かないと考えられていたTOが見直されました。 CockroachDBは、hybrid clock protocolによって原子時計無しで、Spannerと同等のコンカレンシコントロールを実現しています。 Hybrid clock protocol of CockroachDB

まとめと今後の展望

NewSQLで用いられている技術の多くは、過去に発見されたものですが、それらの技術は個々のシステムで単発で 実装されたもので、1つのプラットフォームとして組み合わされたものではありませんでした。 NewSQLの革新性は、ハードウェアの進歩や、高並列度のOLTP、大規模データのOLAPを必要とする アプリケーションが増加したことにより、膨大なエンジニアリングによってプラットフォームとして 作りあげられたことにあります。

NewSQLの台頭により、今後は分散DBMSがコモディティ化していくのではないかと考えられます。 これからは、リアルタイムデータ分析やhybrid transaction-analytics processing（HTAP）といった、 過去データと新しいデータの組み合わせから知見を得るためのシステムへと進化していくと著者達は予測しています。

memo

General Notes