CMU Database Systems をひたすら追っていく ~10 Query Processing~
この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」19日目の記事です
はじめに
どうも、最近という出だしでブログ記事を 19 個も連続で書くと流石にそろそろネタがなくなってくるけんつです。
今回は SQL の実行周りに関連する話で、久々に CMU の講義に戻ってきます。
Query Processing
Query Plan
Query がどのように実行されるかというと、まず SQL が DBMS に投げられるとそれを構文解析に通してツリー構造を作る。
そのツリー構造をもとにどのように実行するか決定する。このとき、実行計画では可能な限りインデックススキャンを利用する必要がある。
Processing Model
DBMSではどのようにクエリプランを実行するかということを定義する。ワークロードに対して色々なトレードオフをもつ様々なモデルが存在する。
ここではそれらについて解説する。
Access Methods
Access Methods とはそのままで、SQL を解析した結果のクエリプランに基づいてクエリを実行する際にどうやってテーブルにアクセスするかという話
大きく分けて２つある。
Sequential Scan
これは順番にアクセスしていくやつ。
- Prefetch: 各ページにアクセスする際に、DBMS がディスクからのロードなどを極力挟まないように事前に数ページまとめて保持しておく
- 並列化： 複数のスレッドやプロセスをつかって並行スキャンしていく。
- Zone Map: 各タプル属性の集計を事前に計算しておく。DBMS はゾーンマップを最初にチェックすることで、ページにアクセスする必要があるかどうかを判断できる。検索するページの総数を減らす目的がある
- Late Materialization: 各オペレータは次のオペレータが必要する最小限の情報を渡す。
- Heap Clustering: タプルをクラスタインデックスで指定された順序を使用して、ページに格納する。
Index Scan
一つ以上のインデックスを選択して、クエリに必要なタプルを見つける。
複数のインデックスを使用する場合、DBMS は一致するレコードIDの集合を生成する。Bitmap, Hash Table, Bloom Filter などを使用することが多い。
おわりに
書かれていることが少なかったので自分で調べていく必要がありそう。
OLTP を目指していきたいので Iterator Model を実装する必要があるのかな？
SystemPage の実装
この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 18 日目の記事です。
はじめに
どうも、最近ダクソリマスタードで RTA をやりはじめたけんつです。黒騎士斧槍めちゃ強いですね。
今回もめちゃくちゃ短いが、SystemPageの実装についてです。
SystemPage と言っているけどおそらく catalog といったほうがよくてテーブルの情報を持っているやつです
実装
import "encoding/json" type SystemPage struct { MaxPageId uint64 `json:"MaxPageId"` TableName string `json:"TableName"` ColumnTypes []string `json:"ColumnType"` ColumnNames []string `json:"ColumnName"` } func NewSystemPage(tableName string) *SystemPage { return &SystemPage{ MaxPageId: 0, TableName: tableName, ColumnTypes: []string{}, ColumnNames: []string{}, } } func SerializeSystemPage(s *SystemPage) []byte { buf, err := json.Marshal(*s) if err != nil { panic(err) } return buf } func DeserializeSystemPage(data []byte) (*SystemPage, error) { var sys SystemPage err := json.Unmarshal(data, &sys) if err != nil { return nil, err } return &sys, nil }
これに関しては語ることがない。
テーブルの情報を持っていたかった。以上。
おわりに
こんな短くていいのか？
Disk Manager の実装について
この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」17 日目の記事です。
はじめに
どうも、最近そろそろ DBMS 作るのでなく MySQL とかの勉強をしたいなと思い始めたけんつです。
今日はディスク周りの話です。
といってもすることがあまりないのでめちゃくちゃ短くなりそうです。
データの永続化
実装
今回は Direct I/O を使っていない
やっていることも簡単でファイルの RW だけ
一応 Page, SysPage 毎に分けているけどこれを書いていて、もう少し抽象化した方がいいなと思った
package storage import ( "io/ioutil" "os" "path" "path/filepath" "strconv" ) type DiskManager struct { } const ( RootDir = ".toybox" PagePrefix = "page_" SystemPageDirectory = "sys" SystemPageFileExt = ".json" ) func NewDisk() *DiskManager { return &DiskManager{} } func (d *DiskManager) SavePage(tableName string, pageId uint64, page *Page) error { buf, err := SerializePage(page) if err != nil { return err } tablePath := filepath.Join(RootDir, tableName) _, err = os.Stat(tablePath) if os.IsNotExist(err) { err := os.MkdirAll(tablePath, 0777) if err != nil { panic(err) } } pid := strconv.FormatUint(pageId, 10) pagePath := path.Join(RootDir, tableName, PagePrefix+pid) return ioutil.WriteFile(pagePath, buf[:], 0777) } func (d *DiskManager) SaveSystemPage(tableName string, sysPage *SystemPage) error { json := SerializeSystemPage(sysPage) tablePath := filepath.Join(RootDir, SystemPageDirectory) _, err := os.Stat(tablePath) if os.IsNotExist(err) { err := os.MkdirAll(tablePath, 0777) if err != nil { panic(err) } } sysPagePath := path.Join(RootDir, SystemPageDirectory, tableName+SystemPageFileExt) return ioutil.WriteFile(sysPagePath, json, 0777) } func (d *DiskManager) LoadPage(tableName string, pageId uint64) (*Page, error) { pid := strconv.FormatUint(pageId, 10) pagePath := path.Join(RootDir, tableName, PagePrefix+pid) _, err := os.Stat(pagePath) if os.IsNotExist(err) { return nil, err } bytes, err := ioutil.ReadFile(pagePath) if err != nil { return nil, err } var buf [PageByteSize]byte copy(buf[:], bytes) return DeserializePage(buf) } func (d *DiskManager) LoadSystemPage(tableName string) (*SystemPage, error) { pagePath := path.Join(RootDir, SystemPageDirectory, tableName+SystemPageFileExt) _, err := os.Stat(pagePath) if err != nil { return nil, err } bytes, err := ioutil.ReadFile(pagePath) if err != nil { return nil, err } return DeserializeSystemPage(bytes) } func (d *DiskManager) LoadAllSystemPage() (map[string]*SystemPage, error) { path := path.Join(RootDir, SystemPageDirectory) files, err := ioutil.ReadDir(path) if err != nil { return nil, err } systems := make(map[string]*SystemPage) for _, file := range files { p := filepath.Join(path, file.Name()) bytes, err := ioutil.ReadFile(p) if err != nil { return nil, err } sysPage, err := DeserializeSystemPage(bytes) if err != nil { return nil, err } systems[file.Name()[:len(file.Name())-5]] = sysPage } return systems, nil }
おわりに
次は、SystemPage (Catalog) の話なのでまた短い。
Buffer Pool を実装する。
この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 16 日目の記事です。
はじめに
どうも、最近 co shu nie*1 にめちゃくちゃハマっているけんつです。
「asphyxia piano ver」 がめっちゃいいので聴いてください。壊れそうなぐらい綺麗な透き通った声がめちゃくちゃ好きです。
今回はくそがつくほど苦戦した Buffer Pool の実装についてです。
もう解説するのが非常に厳しいので単純に紹介していきます。
普段は MySQL に寄せようと頑張って来ましたが、いよいよ資料がなさすぎてついに PostgreSQL のおそらく Ver 8.x 系の文献を参考にしています。
http://www.interdb.jp/pg/pgsql08.html
CMU の講義に拠らない感じのできになっています。
Buffer Pool の実装
Buffer Pool が持つべき責務を考える
これができなくてめちゃくちゃ苦戦した。というのも、この後に DB Storage 全体を管理する Storage Manager を実装するから
どこからどこまでを Buffer Pool の責務として保証するのかが微妙に噛み合わなくて苦戦した。
その上で、Storage Manager はメモリ上の Buffer Pool とディスク周りの処理を担保する Disk Manager を操作するメソッドをコールするだけ*2にしようということになった。
どういうことかというと、例えばページが Buffer Pool 上に存在しない場合ディスクから読み取る必要があるがこれは Buffer Pool と Disk Manager 両方の機能を必要とするため Buffer Pool で簡潔させるのではなく
Storage Manager に該当する双方の処理を呼ばせて実現することにした。
Buffer Pool 全体の仕様
Buffer Pool とさっきからいっているが実際は Buffer Manager であり、そいつが Buffer Pool を内包している。
全体的には以下のようになっている。
Hash Table は可変長の map[string]*BufferTag を使っている。ここでこの Hash Table 、 Buffer Descriptor が Clock Sweep を使って Descriptor を開放したらそれに対応する hash が開放されない実装もれがあることを思い出した。
Buffer Descriptor は Clock Sweep によって開放されるキャッシュライクなもので、固定長の配列をベースにしている。
Buffer Pool は単に Page 構造体の参照を配列でもっているだけ。
ここに出てくる固定長の配列は全て同じサイズで宣言されている。
基本的に Descriptor が持っているインデックスを参照して、 Buffer Pool 内の Page を取得するがこの時にどちらかがスライスだと、ハッシュテーブルからディスクリプタ、ディスクリプタからプールのどちらかの処理をインデックスベースで行う事が面倒になるので
すべて固定長としている。
またハッシュテーブルは uint64 の pageId と string の tableName から SHA1 を計算している。
それをキーとして Buffer Tag を見つけ、その buffer tag が持っているインデックスを元にページを参照することができるという仕組み。
Buffer Pool で持つ他の情報
Buffer Pool では他の DBMS がそうなっているようにインデックスを持っている。また今回これより重要となるのがカタログと言われるテーブル情報を格納している代物で SystemPage と呼ばれているが、PageId の管理などを行っている。
これによってテーブル毎に 0 スタートで一意な pageid を割り振れるようにしている。
構造体
type BufferManager struct { Table map[string]*BufferTag Descriptors *ClockSweep Pools [BufferPoolLimitSize]*Page SysPage map[string]*SystemPage Indexes map[string]*BTree } type BufferTag struct { TableName string PageId uint64 Index int } type BufferDescriptor struct { Ref int Usage int Dirty bool Index int Mutex sync.RWMutex }
Buffer Pool の操作
Append, Read Page だけコードを載せておくけどこんな感じになった。要リファクタリング。
func (b *BufferManager) AppendPage(tableName string, p *Page) { sys := b.ReadSystemPage(tableName) pageId := sys.MaxPageId + uint64(1) sys.MaxPageId = pageId sha := Hash(tableName, pageId) newDesc := NewBufferDescriptor() victim, index := b.Descriptors.AppendPage(newDesc) if victim != nil { b.Pools[victim.Index] = nil } b.Pools[index] = p newDesc.Index = index tag := NewBufferTag(tableName, pageId) tag.Index = index b.Table[sha] = tag } func (b *BufferManager) ReadPage(tableName string, pageId uint64) (*Page, *BufferDescriptor) { hash := Hash(tableName, pageId) t, exist := b.Table[hash] if exist { desc := b.Descriptors.GetDescriptor(t.Index) //desc.IncreaseRef() desc.IncreaseUsage() return b.Pools[desc.Index], desc } // if page is null, storage manager read page from disk return nil, nil }
おわりに
ここから怒涛の勢いで Storage Manager を実装する
B Tree Index を実装する
この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 15 日目の記事です。
はじめに
どうも、最近眼精疲労がひどすぎるけど眼球ってどうやって休めたらいいかわからないけんつです。
今日明日は現状最も苦戦した B Tree Index と Buffer Pool の実装話になります。
B Tree を実装する
今回は B+ Tree でなく B Tree を実装する。また削除は考慮しない。
完全に考慮しない訳ではなくて一応削除を実装することを考慮はしている。ただ物理削除ではなく論理削除としている。
というのもなぜかと言うと、B Tree のなかで最もコストの高い動作が発生するのが物理削除であるという理由から。
どのように論理削除するというとフラグを立てて探索をスキップするという単純なものを実装している。
インデックスの色々
インデックスと言っても色々あってここではその話をする。あくまでも MySQL が前提。
クラスタインデックス
MySQL のインデックスには２種類あってクラスタインデックスとセカンダリインデックスというものが存在する。クラスタインデックスは雑に言うと主キーで構成されたインデックスで暗黙的に構築される。 PK が定義されていないなら全てのカラムから NOT NULL な UNIQUE インデックスを最初に検索し、それを元に構成する。それすらもない場合は InnoDB が内部的に行に自動で付与されるインクリメントカラムを追加しその値で構成する。
セカンダリインデックス
クラスタインデックス以外のインデックスを全てセカンダリインデックスと呼ぶ。これは特定のカラムに貼るものと思って間違いは無いはず。
そして実際にセカンダリインデックスとクラスタインデックスがどのように関連しているかというと、セカンダリインデックスで探索するものは主キー、つまりクラスタインデックスであることが多く
セカンダリインデックスで探すべき主キーを見つけ、そのあとクラスタインデックスを探索してその主キーに紐付いている行を見つけている。
しかし、セカンダリインデックスに必要な情報が全て格納されていれば、クラスタインデックスによる探索をスキップできるため高速に動作させることができる。
B Tree アルゴリズム
「B Tree 実装」とかってググるとなぜか MySQL のインデックスなどが引っかかってきてハイパーわかりにくかったのでアルゴリズムの手順的なものは以下のスライドを参考にした。
これを見れば大体行ける。
そして、以下のデモサイトを見ると困った時に B Tree がどのように処理を行っていくかが試せるからすごく良かった。
www.cs.usfca.edu
実装するにあたっての知見・感想
アイテムの閾値
ノードが最大何個までアイテムを持つかという値を決める必要があるが、これは間違いなく奇数がいい。
なぜかというと、閾値を 3 にした場合を例に説明するならばノードが持つアイテムが３つになった段階で最大値・最小値を2番目のアイテムの子ノードにする必要があるから。
偶数にする場合はまた何かしら別に処理する必要があるっぽいが単純に面倒くさいので 3, 5, 7 あたりの真ん中の値が一意に求まるものにすると実装しやすい。
ラッチの実装
CMU の講義でも言われているが、ノードを探索、追加、更新する場合にはラッチを利用するのがよいと言われている。
例えば探索なら、まずルートノードのロック*2をとり、探索する前に子ノードのロックも確保する。
ルートノードの探索が終わったら、ロックを開放して子ノードの更に子ノードのロックを取得する、というプロセスを値が見つかるまで繰り返す。
今回は Github の PR でもわかる通り、今回はラッチをノードレベルではなくインデックスのツリー構造単位でかけている。
これはめちゃくちゃパフォーマンスが悪いのは知っているけど、↑のようにロックをノードレベルで取得がめちゃくちゃめんどくさくて*3 そうなってしまった。
Golang の interface を上手く使う
ノードが保持するアイテムを Item という以下の interface として宣言している
type Item interface { Less(itm Item) bool Equal(itm Item) bool IsSkip() bool }
そのため B Tree で使うデータ型は上記のメソッドを実装していればいいから、データ型によって異なる大小比較とかが抽象化できて
B Tree 自体のコードがあまり複雑にならなかった。
データ型の宣言は以下の様になっている。
package storage type IntItem struct { Value int32 Delete bool } type StringItem struct { Value string Delete bool } type Item interface { Less(itm Item) bool Equal(itm Item) bool IsSkip() bool } func (i IntItem) Less(itm Item) bool { v, ok := itm.(IntItem) if !ok { return false } return i.Value < v.Value } func (i IntItem) Equal(itm Item) bool { v, ok := itm.(IntItem) if !ok { return false } return i.Value == v.Value } func (i IntItem) IsSkip() bool { return i.Delete } func (s StringItem) Less(itm Item) bool { v, ok := itm.(StringItem) if !ok { return false } return s.Value < v.Value } func (s StringItem) Equal(itm Item) bool { v, ok := itm.(StringItem) if !ok { return false } return s.Value == v.Value } func (s StringItem) IsSkip() bool { return s.Delete }
B Tree の実装
もう解説がめんどくさくなったので、これは本当に自信が無いが*4 コード載せて終わりとする
package storage import ( "sort" "sync" ) const ( MergeThreshold = 3 ) type Items []Item type Node struct { Items Items Children []*Node } type BTree struct { Top *Node Mutex sync.RWMutex } func NewBTree() *BTree { return &BTree{ Top: nil, Mutex: sync.RWMutex{}, } } func (b *BTree) Insert(item Item) { b.Mutex.Lock() defer b.Mutex.Unlock() if b.Top == nil { node := new(Node) node.Items.InsertAt(item, 0) b.Top = node } else { b.Top.Insert(item) } } func (n *Node) Insert(item Item) { _, index := n.Items.Find(item) if len(n.Children) == 0 { n.Items.InsertAt(item, index) if len(n.Items) == MergeThreshold { n.Split() } return } if len(n.Children[index].Items) == MergeThreshold - 1 { n.SplitChildren(item, index) if len(n.Items) == MergeThreshold { n.Split() } return } n.Children[index].Insert(item) } func (n *Node) SplitChildren(item Item, index int) { _, i := n.Children[index].Items.Find(item) n.Children[index].Items.InsertAt(item, i) leftItem := n.Children[index].Items[MergeThreshold/2-1] middleItem := n.Children[index].Items[MergeThreshold/2] rightItem := n.Children[index].Items[MergeThreshold/2+1] n.Children = append(n.Children[:index], n.Children[index+1:]...) _, middleIndex := n.Items.Find(middleItem) n.Items.InsertAt(middleItem, middleIndex) leftNode := new(Node) rightNode := new(Node) leftNode.Insert(leftItem) rightNode.Insert(rightItem) n.Children = append(n.Children, leftNode) n.Children = append(n.Children, rightNode) sort.Slice(n.Children, func(i, j int) bool { return n.Children[i].Items[0].Less(n.Children[j].Items[0]) }) } func (n *Node) Split() { left := new(Node) middle := n.Items[MergeThreshold/2] right := new(Node) left.Items.InsertAt(n.Items[MergeThreshold/2-1], 0) right.Items.InsertAt(n.Items[MergeThreshold/2+1], 0) n.Items = append([]Item{}, middle) if len(n.Children) == MergeThreshold + 1 { var nodes []*Node left.Children = append(left.Children, []*Node{n.Children[0], n.Children[1]}...) right.Children = append(right.Children, []*Node{n.Children[2], n.Children[3]}...) nodes = append(nodes, left) nodes = append(nodes, right) n.Children = nodes return } n.Children = append(n.Children, left) n.Children = append(n.Children, right) } func (b *BTree) Find(item Item) (bool, int) { b.Mutex.RLock() defer b.Mutex.RUnlock() if b.Top == nil { return false, -1 } return b.Top.Find(item) } func (n *Node) Find(item Item) (bool, int) { ok, index := n.Items.Find(item) if ok { return ok, index } if len(n.Children) == 0 { return false, -1 } return n.Children[index].Find(item) } func (i *Items) Find(item Item) (bool, int) { for index,itm := range *i { if itm.IsSkip() { continue } if itm.Equal(item) { return true, index } if !itm.Less(item) { return false, index } } return false, len(*i) } func (i *Items) InsertAt(item Item, index int) { *i = append(*i, nil) if index < len(*i) { copy((*i)[index+1:], (*i)[index:]) } (*i)[index] = item } func (b *BTree) Get(item Item) Item { b.Mutex.RLock() defer b.Mutex.RUnlock() if b.Top == nil { return nil } return b.Top.Get(item) } func (n *Node) Get(item Item) Item { found, i := n.Items.Find(item) if found { return n.Items[i] } else if len(n.Children) > 0 { return n.Children[i].Get(item) } return nil }
終わりに
次は、インデックスより苦戦した Buffer Pool について
Clock Sweep と LRU Cache を実装する
この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」の 14 日目の記事です。
DBMSのキャッシュ
これは MySQL と PostgreSQL でかなり違いがある。
少し前に記事でもまとめたが、MySQL は LRU で PostgreSQL はクロックスイープを使っている。
MySQL の LRU キャッシュ
MySQL では List 構造を２つ持っていて、LRU 全体サイズの 5/8 が New List、3/8 が Old List となっている。
最初に要素が LRU キャッシュに追加されるときは Old List に追加され、再度参照されることで New List に移動される。
これによって追加されて以降参照されていない要素を優先的に開放する仕組みが構築される。
PostgreSQL の Clock Sweep
こちらはクロックスイープで実装されている。
クロックスイープではそれぞれの要素が参照された総数を持っている。リストがいっぱいになった場合、この参照回数をそれぞれ１ずつ減算し、0 になったものを開放するという仕組みを取っている。
実装
とりあえず両方とも実装してみた。
LRU
LRU は要素に key, value のセットを持つようにしている。
type Lru struct { Size int NewSublist LruCache OldSublist LruCache Mutex sync.RWMutex } type Entry struct { Key interface{} Value interface{} } type LruCache []Entry
この構造体とデータ型を宣言している。
LRU に対する要素の追加と取得は次のように実装している。
func (l *Lru) Append(key interface{}, value interface{}) { if OldSublistSizeLimit < len(l.OldSublist) { l.OldSublist.RemoveOldest() } l.OldSublist.Append(key, value) } func (l *Lru) Get(key interface{}) interface{} { e := l.NewSublist.Get(key) if e != nil { return e.Value } e = l.OldSublist.Get(key) if e != nil { if NewSublistSizeLimit < len(l.NewSublist) { l.NewSublist.RemoveOldest() } l.NewSublist.Append(key, e.Value) l.OldSublist.RemoveFirst() return e.Value } return nil }
それぞれのリストに対する一番最後に参照された要素を削除するコードは雑に次のようになっている。
func (l *LruCache) MoveToFront(index int) { e := (*l)[index] *l = append((*l)[:index], (*l)[index+1:]...) *l = append(LruCache{e}, (*l)[0:]...) } // fix return value func (l *LruCache) RemoveOldest() *Entry { e := l.Last() *l = (*l)[:len(*l)-1] return e } // fix return value func (l *LruCache) RemoveFirst() *Entry { e := l.First() *l = (*l)[1:] return e }
今回実装した LRU キャッシュはサブリストを２つ保持するようになっているからすこし Append 周りが複雑になってしまった。
Clock Sweep
クロックスイープは以下のような構造体として宣言されている。
type ClockSweep struct { Cap int Cache Clocks } type Clocks [BufferPoolLimitSize]*BufferDescriptor
ここで登場する BufferDescripor とは明日紹介する BufferPool において、ページの情報や Pin/Referrence Counter などを持っている構造体のこと。
今回実装する Clock Sweep では基本的に固定長の配列を構造体で保持していて、空きスロットに追加していく形となる。
スロットを開放する必要がある場合は、Usage を１ずつ減算していく。ただしこの時参照カウンタが1以上の場合は探索をスキップする必要がある。
おわりに
LRU, Clock Sweep の実装はこれにて終わり。
結構使いやすいデータ構造がなくて作るはめになってしまったけど、おそらく Clock Sweep の方が実装が簡単なので
それをベースに Buffer Pool のキャッシュを作れるとよさそう。
Page を実装する
この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 13 日目の記事です。
はじめに
どうも、なんかブログ記事を書きまくってたら右手親指の付け根が痛くてたまらないけんつです。
今日は Page の実装に関する話です。
BufferPool あたりの実装が完了した段階で思ったことなどなど書いていきます。
Page の実装
基本的に Page Header と Tuple の塊となっている。
先頭 4byte を Page Header として、残りの領域で Tuple を追加された順番で保持する単純な構造になっている。
全体の容量は約 16 KB で固定。mmap は使用しない。
バイナリへのシリアライズなどなどは、前回実装したタプルのシリアライズをそのまま使う。
というのも、Page Header が今のところ 4 byte しかなく、あとはタプルが列挙するだけどとわかっているからバイナリにシリアライズするのは比較的簡単にできるようになっている。
また、ページは単にテーブル毎のディレクトリに格納されているだけでヒープや単方向リストを使って参照を持っているわけではない。
削除を考慮しない
削除を考慮しないのであれば、ただタプルを列挙すればいいだけとなる。
しかし、これで削除を考えようとすると一気に考えることが多くなる。
というのも、テーブル単位でそれぞれページを複数もっているが、タプルが追加されるだけとわかっていれば既に存在しているページを探索して空きスロットを探すとかしなくても良いため。
もしも削除を考慮するとするなら、同時実行制御をどのように実装するかを考える必要がある。
というのも、仮にデータを追加・更新する際に、PostgreSQL のように追記型を採用しているなら単にページを追加していき、タプルを末尾に追加すればいいだけとなる。削除なら単に論理削除すればいいだけなのでそこまで難しくない。
しかし MySQL の様に、更新型を取る場合は削除を考慮すると空きスロットが発生する可能性がある。
これを単にタプルを並べただけの構造から見つけ出すのは明らかにコストとなる。
これは CMU の講義のなかでも触れられている。
それらの問題を解決するために Slotted Page や Log-Structured File Organization などがある。
今回はそういった実装を現段階ではしないこととしている。
番外
特にタプルとページは愚直に実装したので特に話すことがない。
だから少しだけ Golang でこまった配列、スライス周りの話をする。
これら固定長のページやタプルを実現するために、固定長の配列を基本的には使用している。
例えばページを扱う構造体はこうなっている。
// Max Size: 16KB type Page struct { Header PageHeader // 4byte Tuples [PageBodySize]Tuple // 128 byte per Tuple }
そう、ここから固定長にしている。
ただこれの問題は色々あって、この配列を扱う場合はその関数やメソッドの引数や戻り値の型を全て固定長にしないといけない。
そのため、スライスで扱ったあり配列として扱ったりとかなり処理が忙しないことになっている。
Golang, 排他制御とかめちゃくちゃ便利なのに配列、スライスまわりとリスト、循環リストなど
データ構造に関わる部分が柔軟でないから少し実装にこまるときがある。
これは Clock Sweep の実装と、 Buffer Pool の実装でも同様に頭を悩ませた。
おわりに
次は Clock Sweep だったかな、そろそろメモリ上でページやタプルを管理する話になる。
