#presentation
## What is this
Carnegie Mellon 大学のDatabase Management Systemの講義
[このブログ](https://buildersbox.corp-sansan.com/entry/2019/10/24/110000) で見たので見てみた。
[https://www.youtube.com/playlist?list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7](https://www.youtube.com/playlist?list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7)
## _#1
[https://www.youtube.com/watch?v=vyVGm_2iFwU&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=2&t=0s](https://www.youtube.com/watch?v=vyVGm_2iFwU&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=2&t=0s)
- CSV形式のファイルでは、厳しい
- マルチスレッド
- 単純にファイルの上書き
- 探索が厳しい
- Early DBMSは、DBが扱うデータ構造とアプリケーションが扱うデータ構造を密結合にしないといけずデータ構造が柔軟に変更することはできなかった
- 1960, 70sに Ted Coddによってリレーショナルモデルが提唱された
- Store database in simple data structure
- より高級な言語でアクセス
- DBMSの要素
- Data Model
- Relational, Key/Value, Graph, Document, Column-familiy, Array/Matrix, Hierarchical, Network
- データの関係や構造のこと
- ほとんどのDBMSはRelational
- Scheme
- データモデルの関係や定義を記述する
- Relational Model
- Structure
- データの型や要素など
- Integirity
- タプルなどの制約など
- Manipulation
- how to access relation and data
- Relation
- unrodered set that contain the releationship of attiributes
- Tuple
- Set of attribute values
- Data Manipuation Languages (DML)
- Procedural
- Relational Algebra
- RelationをInputとして 受けて Relation をOutputする
- 計算規則は、内側の式から計算して展開していく
- [[Select]] : $\sigma_{predicates} (R)$
- predicates acts as a filter to retain ny tuples that fulfill its qualifying
- combineできる
- [[Projection]] : $\pi_{A1, A2, ..., An} (R)$
- Generate a relation with tuples that contains only the specified attributes
- 要素の順序を変更できる、要素の値を変更できる
- [[Union]] : $R \cup S$
- 2つのrelationをとって全てのtupleを含むrelationを返す
- RとSのattributesは同じであるべき
- [[Intersection]] : $R \cap S$
- 2つのrelationにどちらも登場するようなtupleを含んだrelationを返す
- RとSのattributesは同じであるべき
- [[Difference]] : $R - S$
- RからSに含まれるtupleを引いたものを返す
- [[Product]] : $R \times S$
- RとSで可能なtupleを全て組み合わせたRelationを返す
- AttributesはR + Sになる
- [[Join]] : $R \Join S$
- R のattributesに一致するものをSと組み合わせて出力する
- RとSのattributesが同じ場合はIntersectionと結果が同じになる
- Extra Operators
- orginal paperには定義されていなかったがあとで定義された Operator
- [[Rename]] : $\rho$
- [[Assignment]] : $R \leftarrow S$
- [[Duplicate Eliminations]] : $\delta$
- [[Aggregation]] : $\gamma$
- [[Sorting]] : $\tau$
- [[Division]] : $R \div S$
- Non-Procedural
- どのようなデータが欲しいかを記述して自動的にクエリを発行する。
- Procedural よりも具体的かつ高級
- GraphQLとかがこれに近い?
- Observation
- Relational algebraは、高級言語を定義しているだけでありどのように実装するかは特に触れられていない
- 順序やどのようにするかによってランタイムのパフォーマンス影響がでることがある
- これらはRelationa Algebraではなく、DBMSの責任において Query Optimizer で効率的なクエリの実行にする
## _#2
[https://www.youtube.com/watch?v=80atcA6gBU8&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=2](https://www.youtube.com/watch?v=80atcA6gBU8&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=2)
- SQL History
- もともとはIBMの "SEQUEL" からきてる (1970's)
- Structured English Query Language
- SQLはそのあと、Structured Query Languageになった
- SQLは2016年版スタンダードもあるので死んだ言語ではない
- しかしほとんどのDBMSは、ベースラインをSQL-92を実装しているという意味なので注意が必要
- Relational Languageはいくつかの言語の集合を指す
- Data ManipulationLanguage (DML)
- INSERTやSELECTなど実際のクエリを表現する言語
- Data Definition Language (DDL)
- Dataの定義をするような言語、スキーマファイルなど
- Data Control Language (DCL)
- 権限など
- SQLはbag based
- Listは、ordered and enable duplicates
- Setは、non ordered and no duplicates
- Bagは、non ordered and enable duplicates
- Aggregates
- Input : Bag of tuples
- Output : Single Value
- e.g AVG(col) -> Return average column Value
- [[Distinct]]
- COUNT, SUM, AVG はユニークキーでのDISTICTIONをサポートしている
- [[Group By]]
- Aggregationをした時には、フィールドは1つに絞れないので全てはGroup BYしないといけない。
sql
```
SELECT AVG(s.gpa), e.cid
FROM enrolled AS e, student AS s
WHERE e.sid = s.sid
GROUP BY e.cid; #これがないと、どのe.cidを出力すべきかわからない
```
- Group By をするとグループごとのAVGとなる
- [[Having]]
- Aggregationの結果をFilterする
sql
```
SELECT AVG(s.gpa) AS avg_gpa, e.cid
FROM enrolled AS e, student AS s
WHERE e.sid = s.sid
GROUP BY
HAVING avg_gpa > 3.9;
```
- String Operations
- 観点
- String Case (Sensitive/Insensitive)
- MySQLは珍しくCase Insensitive
- String Quotes (Single/Double)
- [[LIKE]]
- `%` 空文字列を含む部分文字列に一致
- `_` 1字に一致
- Date/Time Operatons
- DBMSでいろんなバリエーションがある部分でカオスになっている
- Output Control
- [[ORDER BY]]
- [[LIMIT]], [[OFFSET]]
- Advanced SQL
- Nested Queries
- Query in Query
- optimizeが難しい
- Inner と Outer をつなぐのは [[IN]]
- [[ALL]], [[ANY]], [[EXISTS]] もある
sql
```
SELECT * FROM course
WHERE NOT EXISTS(
SELECT * FROM enrolled
WHERE course.cid = enrolled.cid
)
```
- Window Function
- Aggregationに似てるが、Valueではなくrelationを返すときに情報を付随したりする
sql
```
SELECT cid, sid, ROW_NUMBER() OVER (PARTITION BY cid)
FROM enrolled
ORDER BY cid
```
- OVER () がwindow
- Common Table Expressions
- Nested Queryの代替の書き方
sql
```
WITH cteName AS (
SELECT 1
)
SELECT * FROM cteName
```
## _#3
[https://www.youtube.com/watch?v=uuX4PQXBeos&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=3](https://www.youtube.com/watch?v=uuX4PQXBeos&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=3)
- Disk Oriented Architecture
- Disk から データを メモリに持ってきて、やりたいことをマネージするというアーキテクチャ
- Storage Hierarchy
- 
- Volatile
- Random Access Byte-Addressable
- Random Access用のAPIが必要
- Non-Volatile
- Sequential Access Block Addressable
- Sequential Access 用のAPIが必要
- DRAMを一般名称でMemoryと呼び、Memoryは一般的にVolatileだったがIntelによればNon-VolatileなMemoryがあるので必ずしもこれだけではない。
- Traditional な DBMSは、Sequential Accessを最大化する努力がされていた
- なるべくデータが一塊になるように工夫
- mmap (OSのシステムコール)
- 
- Virtual MemoryにアクセスするとOSがプロセスを奪い取って、実際の物理メモリにディスクからデータをロードさせる
- Read-onlyには向いてるが、書き込みなどをするたびにこのようにすぐにスレッドを待ち状態にしてしまうので遅い
- DBMSは、高速にするためにコントロールできるようにしたいし、大体の場合にはOSよりも良いやり方があるのでOSの機能は使わずにStorage Managerをうまく作る
- Database Storage
- Problem1 : How the DBMS represents the database in file on disk -> No3とNo4ではこれにフォーカス
- Problem2 : How the DBMS manages its memory and move data back-and-forth from disk
- Storage Manager
- DBMS stores data in multiple storage files
- responsible for mainaing database's files
- Pageという抽象概念としてfileを扱う
- どのPageへの書き込み、読み込みか
- どれくらいスペースがあるか
- Pageは固定長のブロック
- tuple, meta-data, index, logなどあらゆるデータを保持する
- それぞれのpageはユニークな識別子を持つ
- 固定長であることでpageから格納場所が計算可能になる
- いろんな種類のPageがある
- Hardware Page (usually 4KB)
- OS Page (usually 4KB)
- Database Page (1-16KB)
- Page Storage Architecture
- Heap File Organization
- Heap Fileは順序保証がないページの集合でtupleも順序非保証で保存されている
- 必要なAPIなど
- Get/Delete Page
- 全てのページをiterateする機能
- どんなページがあるかのmeta dataのマネジメント
- ページの残り要領
- 実装方針は、Linked List か Page Directoryがある
- Linked List
- 
- Headerは、空いてるページとデータが入ってるページそれぞれのリストへのポインタを持つ
- それぞれのシーンにおいては、全てのページをトラバースする
- meta dataなどはpageなどに含まれている
- 悪くはないけど、全てをトラバースしたり、meta dataへのアクセスを分散して管理しないといけなかったりと非効率な部分も多いのでPage Directoryの方が有効
- Page Directory
- 
- Directoryがどんなページがあるかを全て管理して、実際のページの情報は問い合わせをする
- Directoryがどれだけスペースがあるかなども管理する
- DBMSはDirectoryとPageの間で同期しないといけない
- Page Layout
- Page Header
- Page Size, Checksum, DBMS version, Transaction Visiblity, Compression Information etc..
- Data Block
- Tuple Oriented Approach
- Strawman Idea
- Tupleを固定長にしてどんどんappendしていく
- appendだと間を消したときに隙間があく
- Slotted Page
- Slot ArrayをHeaderに用意して先頭へのoffsetのmapを固定長で用意する
- ポイントは、スロットはファイルの上から増えていき、実際のデータは下から増えていくのでこれ以上データが保存できなくなったらいっぱいになると表現できること
- Compactionなどもスロットのoffsetをいじるだけで表現できる
- Log Structured Approach
- レコードへの変更を保存する
- ログを溜めていくので、削除がなく難しいことを考えずにappendしていくだけである
- 単純にReadするときにデータを再構築しないといけないので難しい
- これを避けるためにindexを用意したり
- compactionをしたり
- Log Strctured Comapction
- level compaction
- Universal Compaction
- Tuple Layout
- ただのバイト列
- バイト列をデータとして解釈するのがDBMSの責任
- 
- a, b, c, d, eというのは物理レイヤーではこの順序を守る必要はない
- ロジカルレイヤーで順序を入れ替えて返せばよい
- Pageは通常、1つのテーブルに対して複数あるが、複数のテーブルに渡るようなこともできる
- JOINを毎回するとパフォーマンス的に悪いので、物理レイヤーでJOINしてしまうというテクニックもある
- これはReadは速いけど、Updateが少し遅くなる
- DBMSでは、Recordにidを内部的につけるけど、これはいつでも変化しうるものなのでアプリケーションはこれに依存してはいけない。sqliteのrowidとか
## _#4
[https://www.youtube.com/watch?v=NXRgIsH83xE&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=4](https://www.youtube.com/watch?v=NXRgIsH83xE&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=4)
- Data Representation
- INTEGER/BIGINT/SMALLINT/TINYINT
- Primitive type in laguage you use
- FLOAT/REAL vs NUMERIC/DECIMAL
- IEEE-754 Standard / Fixed-Point Decimal
- WARCHAR/VARBINARY/TEXT/BLOB
- Header with length
- TIME/DATE/TIMESTAMP
- 32/64-it integer of seconds since Unix epoch
- Large Values
- Overflow page
- Pageのサイズに収まらないような大きなデータはOverflow pageを用意してTupleにそのページへのポインタを格納する
- External Value Storage
- Pageとしてではなく、完全にファイルとして扱う
- DBMSは、external fileを更新することができない
- System Catalog
- DBMS stores meta-data about database
- INFORMATION_SCHEMA のこと
- N-Ary Storage Model
- DBMSがtupleをページに連続的に保存するモデル
- 現状の講義ではこれを前提にして設計をしている
- データを見に行くなどはPageを見に行って、Tupleを見にいけばいいのでReadの回数が少ない
- しかしデータの解析など大きな範囲をReadする場合には、コストが高くなってしまう (On-line Analytical Processing (OLAP))
- Decompotion Storage Model (DSM)
- N-AryがRow Orientedに対してこれは、Column Oriented
- Tupleを再構築しないといけない
- Fixed-length Offsets
- 長さを同じにして計算をする
- Embedded Tuple Ids
- idを保持する
- 分散してるのでselctやinsertsなどが遅い
- N-Ary と DSM を両方サポートするには
- データを複製して2つのDBを作る
- Elastic Searchとかはデータを複製している?indexを工夫してるだけ?
## _#5
[https://www.youtube.com/watch?v=_vRG1ksPlXs&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=5](https://www.youtube.com/watch?v=_vRG1ksPlXs&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=5)
- Database Storage
- Problem 1 : How the DBMS represents the database in files on disk
- 3 ~ 4はこっち
- Problem 2 : How the DBMS manages its memory and move data back and forth from disk
- 5はこっち
- Spatial Control
- Where to write page on disk
- 一緒に扱うようなデータは近くに書き込めると嬉しい
- Temporal Control
- When to read page into memory and when to write them to disk
- DBまで行く数をなるべく少なくできると嬉しい
- Buffer Pool
- 
- 仮想メモリっぽい
- Buffer Pageは、ただの大きなArray
- Arrayの要素はframeと呼ばれる
- DBMSはDsikからPageを取得するときには、frameにコピーをする
- Page TableがDBMSにあるかどうかあればどこにあるかというのを記録している
- Dirty Flag -> いつBuffer Poolをリフレッシュするか
- Pin/Reference Counter -> マルチスレッドのための機構
- Locks and Latches
- LockはLatchesよりもハイレベルなロック概念
- Latchesはいわゆるmutexやsyncronizedな小さな項目へのロック
- Page Directory and Page Table
- Page Directory : Database fileのmapping構造
- Page Table : Memory上のmapping構造
- Optimization for Buffer Page
- Multiple Buffer Poolsを採用してるDBMSもある
- Prefetching
- OSではこういうことがアプリケーションの知識がないのでできない
- Scan Sharing
- 次のクエリのためにデータの一部を再利用する
- Buffer Pook Bypass
- OS Page Cache
- ファイルのキャッシュがOSとDBMSでそれぞれ生成されてしまう問題
- `EXPLAIN (ANALYSE, BUFFER) ~ ` BUFFERというフラグはBuffer Poolにどれくらいあるかなど教えてくれる
- Buffer Replacement Policies
- ページをBuffer Poolから削除するときにどのページを削除するかという戦略
- 遅すぎても結局DBが遅くなるから意味がないが正確でないと意味がない
- Least Recently Used (LRU)
- 古いものから削除していく
- Clock
- ある時間範囲の中でアクセスがあったかどうかを見て削除する
- GCみたいなイメージ
- LRUとClockの問題 Sequential Flooding
- 順番にページをアクセスするようなクエリの時にはそれぞれでBuffer Poolが埋まってしまう。
- その結果、読んだら捨てるようなページでBuffer Boolが埋まってしまう
- クエリ will read n pagesのせいで発生する
- LRU-K
- アクセスの履歴を見てintervalで判定するようにする
- 単純な時間よりも頻度でみるようにする
- k = 1で2回の頻度だけでみるのがcommon
- Localization
- Priority Hints
- Dirty Pages
- FAST : dirtyになった瞬間ページをbufferから捨てる
- SLOW : 毎回updateをDBにする
- Background Writing
- Page Tableを定期的に監視して、dirty pageで更新が必要なら更新する
- Allocation Policies
- Global Policies
- Local Policies
- Other Memory Pools
- データのtupleのプールだけでなく、様々なものにMemory Poolが必要
- Sorting + Join Buffers
- Quey Caches
- Maintenance Buffers
- Log Buffers
- Dictionary Caches
DBMSは常にOSよりもいい仕事ができるのでmmapやfile cacheなどのOSの機能に頼らずに自前でマネージするべき。
[[Intro to Database System #Project1]] が宿題に出た
多分6を見てからの方が良さそう。
## _#6
[https://www.youtube.com/watch?v=ByG1IMM6Ua8&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=6](https://www.youtube.com/watch?v=ByG1IMM6Ua8&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7&index=6)
- supporting the DBMS's execution
- Hash Tables
- Trees
- Data Structure for DBMS
- Internal Meta-data
- Core Data Stroage
- Temporary Data Structures
- Table Indexes