Database Management Systemsの16章。 やっと Transaction に突入。 マインドマップから再構成したまとめ DB は ACID を維持する Atomic トランザクションは全てのアクションが実行される or 全く実行されないのどちらかしかありえない 中途半端に実行される…

小さな課題を設定し読み進める事で PostgreSQL のソースを読みに慣れよう。昨日設定した課題は「/tcop/postgres.c にある exec_simple_query(const char *query_string) から大まかに処理を追い、結果をまとめる」。結果は以下の通り。PostgreSQL のソースは…

おおまかな構造の把握をしよう。 流れは以下の通りと予想。 クライアントの接続 => postmaster postermaster => postgres : postermaster Query のコンパイル : backend/parser 実行計画 : backend/optimizer 最適化 : backend/optimizer インデックスあれば…

Database Management Systemsの15章。 マインドマップから再構成したまとめ SQL -> ALGEBRA 流れ：SQL => 分解 => Blocks => Algebra Block とは： 1つの Select, 1つの from 。 Block -> Algebra select => projection from => cross product where => sele…

まずは読むところから。興味のあるのは 基本データ構造 Backup Transaction Index 特にClustred Index の扱い Buffer management Disk space management Optimizer など。 読み方は、ざっくりとテーマ毎に 概要 該当するソースファイル or モジュール データ…

ソースコードの入手 postgresql-8.3.5.tar.bz2 を公式サイトから入手。 解凍して、GNU Global で gtags -v しておく。（Emacs から簡単にコードを読めるように） コードの行数を見る 規模を把握しておけば、読み方も自ずと決まる。 % sudo port install cccc…

PostgreSQL のソースコードを読む事になりました。pgsql-hackers の ML を購読。 PostgreSQL コミュニティの皆さんよろしくお願いします。 追記 ソースコードを読んだ結果を Web 上にまとめたいのだけど何か良いのあるかな。 Pukiwiki は使い慣れていて良い…

Database Management Systemsの14章。 マインドマップから再構成したまとめ Set Union と Difference 方法 2つ Sort & Merge Partitioning (h & h2) Aggregate AVG, MIN, MAX など。 group by が付加する事も。 Basic な方法：Scan + 必要な情報を保持 Group…

Database Management Systemsの14章。 マインドマップから再構成したまとめ Nested Loop Join simple, but slow I/O 多すぎる Block Nested Loop Join 前提：B バッファページ利用可能 R を B に読み込み、S の tuple と比較 R を読み込むのではなく B にメ…

Database Management Systemsの14章。 マインドマップから再構成したまとめ Projection の手順 不要 attribute を削除 重複 tuple の削除 Projection based on Sorting Scan して attribute 削除 tuple を Sort sort result を scan して重複を削除 External…

Database Management Systemsの14章。 マインドマップから再構成したまとめ 簡単な Selection reserves (100件/page, 1000 pages) select * from reserves where rname = 'Joe' 何も考えない方法：1000 I/O No Index, Sorted Data: log2(1000) = 10 I/O prac…

Database Management Systemsの13章。 マインドマップから再構成したまとめ 背景 データ量 > メモリ メモリ上でソートできない I/O を最小にするアルゴリズムが必要 Two way merge sort 学習用の例。書き込みに 1 ページ、読み込み用に 2 ページの計 3 ペー…

Database Management Systemsの12章。 マインドマップから再構成したまとめ Selection clustered index あり => index を読むだけ un-clustered index あり => index + match した tuple の data を read index なし => full scan Projection 特徴1：出力を …

Database Management Systemsの12章。 マインドマップから再構成したまとめ Overview of Query Evaluation CNF(Conjunctive Normal Form) 複数の attr op value 形式の条件の結合したもの - Hash Index は CNF が attr = value で attr が key のときにマッ…

Database Management Systemsの11章。 マインドマップから再構成したまとめ Linear Hashing 特徴 Extendible Hashing と違い、ディレクトリを持たない（仮想的に考える事はできる） bucket は徐々に増加する（Extendible Hashing 一度に2倍になる） space 効…

Database Management Systemsの11章。 マインドマップから再構成したまとめ Hash-Based Indexing 特徴 search= が速い 1 I/O sarch range ができない 総合的には Tree-Based Indexing が上 Static Hashing ISAM と同様の考え方で Hash-Based 1 〜 N - 1 の p…

Database Management Systemsの10章。 マインドマップから再構成したまとめ Bulk loading 複数のデータから B+-Tree を 1 から構築するとき。 通常の insert アルゴリズムだと root から 1 データずつ insert。効率悪い ある程度まとめてデータを insert す…

Database Management Systems の 9章。 Heap file フォーマット。 ページ管理 Linked List レコードが可変長だと不利 Directory of pages レコード管理 fixed-length bitmap そのまま並べる variable-length slot direcotry で length, offset 管理 レコード…

Database Management Systems の 10章。ISAM(Indexed Sequential Access Method) 読み方は「あいさむ」 構造が「ほぼ」Static Page が物理的に整列されるように構築 データは Leaf Node と Overflow pages へ。 Overflow pages が大きくなると速度的に不利 T…

Database の中身を実装できるほど知りたいのだけど良い本はないだろうか。本当に初歩の初歩から学びたい。 mumurikさんのおすすめの↓はなのだが Amazon では売り切れだ。 Database Management Systems: Raghu Ramakrishnan, Johannes Gehrke http://www.amaz…

1.ソースコードの入手と規模の把握 2.読み方と読むところを決める 3.課題を設定しよう 4.ソース読みに慣れよう 5.PL/Proxy 5.次の課題は CLUSTER コマンド 6. clustered index の威力を知るための準備 7. clustered index の威力を知るための準備2 8. cluste…

1章 Overview Of Database Systems 2-3章 Introduction to Database Design, The Relational ModelOverview Of Database Systems 4-7章 Comparison of File Orgnization Storing data disk and files Heap file format ISAM B+-Tree in Practice Hash-Based …