🤴🏻 😻 🙍🏻 3週間でDBMSを所有します。毎日少し時間が必要です... ⏲️ 🆚 🤛🏽

3週間でDBMSを所有します。毎日少しの時間を建築に費やすだけです。残りの時間は、結果に熱心に取り組み、数百行のコードを印刷して再入力します。

マーフィーの法則によると、選択するプロジェクトが複数ある場合は、提案されているプロジェクトのうち最も難しいものを引き受けます。これは、データベース管理システム（DBMS）のコースの最後のタスクで発生しました。

問題の声明

作業指示書によると、Vanilla Python 3.6でDBMSをゼロから作成する必要がありました（サードパーティライブラリなし）。最終製品には次のプロパティが必要です。

データベースを単一のファイルにバイナリ形式で保存します
DDL：整数、浮動、および可変長文字（N）の3つのデータ型をサポートします。簡単にするために、それらはすべて固定長です。
DML：基本的なSQL操作をサポートします。
- 挿入
- 更新
- 削除
- WHEREおよびJOINを使用したSELECT。どのJOINに正確に参加したかは示されていないため、CROSSとINNERの両方を行った場合に備えて
100'000レコードに耐える

設計アプローチ

DBMSをゼロから開発することは、重要なタスクのように思えました（奇妙なことに、そのようになりました）。したがって、我々 -ecat3と@ratijas-はこの問題に科学的にアプローチしました。チームには2人しかいません（自分自身と私の人員は考慮していません）。つまり、タスクを実際に実行するよりも、タスクを調整して実装を調整する方がはるかに簡単です。カットの終わりに、次のことが起こりました。

挑戦する	請負業者
パーサー+ AST + REPL	ratijas、あらゆる種類のlex / yaccについて複数の計算機を書いた
基本ファイル構造	ファイルシステムでecat3を食べる犬
エンジン（低レベルのデータベース操作）	ecat3
インターフェース（高レベルの接着）	一緒に

当初は2週間が割り当てられていたため、個々のタスクを1週間で完了することになっており、残りの時間は共同で接着とテストに充てられます。

正式な部分が終了したら、実用に移りましょう。 DBMSは最新かつ適切なものでなければなりません。現代のイノポリスでは、テレグラムのメッセンジャー、チャットボット、および「/スラッシュタグ」を使用したグループ通信が関連しています（これは＃ハッシュタグのようなもので、/スラッシュで始まります）。したがって、SQLによく似たクエリ言語では大文字と小文字が区別されないだけでなく、大文字と小文字も区別されません。さらに、大学生と同様に、各言語のステートメント（ステートメント）は「/ドロップ」で終わる必要があります。（もちろん、登録簿に関係なく。そのような状況で一般的に誰がそこの登録簿を気にしますか？）

典型的な/日中/チャット

そこで、名前のアイデアが生まれました： dropSQL 。実際に/ドロップ 'thは、大学からの学生の追放と呼ばれています。何らかの理由で、この言葉は私たちのイノポリスで広まっています。（別の局所現象：自閉症、またはより正確には、/自閉症。しかし、私たちは特別なケースのためにそれを予約しました。）

まず、dropSQL文法をBNFに分解しました（そして、無駄なことに、左再帰は降順パーサーには適していません）。

BNF文法dropSQL

完全版はこちら

/stmt : /create_stmt | /drop_stmt | /insert_stmt | /update_stmt | /delete_stmt | /select_stmt ; /create_stmt : "/create" "table" existence /table_name "(" /columns_def ")" "/drop" ; existence : /* empty */ | "if" "not" "exists" ; /table_name : /identifier ; /columns_def : /column_def | /columns_def "," /column_def ; /column_def : /column_name type /primary_key ; ...

製品オンラインヘルプの有効なdropSQLコマンドの例

 /create table t(a integer, b float, c varchar(42)) /drop /insert into t (a, c, b) values (42, 'morty', 13.37), (?1, ?2, ?3) /drop /select *, a, 2 * b, c /as d from t Alias /where (a < 100) /and (c /= '') /drop /update t set c = 'rick', a = a + 1 /drop /delete from t where c > 'r' /drop /drop table if exists t /drop

私たちは結果のために働きます！例外なし！

Rustをメイン言語として数ヶ月過ごした後、私は本当に例外処理で再び行き詰まりたくありませんでした。例外に対する明白な議論は、それらを投げるのに費用がかかるということであり、キャッチは扱いにくいです。 Pythonは、Java自体とは異なり、Type Annotationsを備えたバージョン3.6でも、メソッドから飛び出す可能性のある例外のタイプを指定できないという事実によって状況が悪化しています。つまり、メソッドのシグネチャを見ると、メソッドに何が期待できるかが明らかになるはずです。それでは、これらのタイプを「enum Error」と呼ばれる1つの屋根の下で組み合わせてみませんかそしてこの上に、Resultという別の「屋根」を作成します。以下で説明します。もちろん、標準ライブラリには「爆発」できる場所があります。しかし、コード内のこのような呼び出しは、すべての側からtry'iによって確実に課されます。これにより、例外を減らしてエラーを返すため、実行中の緊急事態の発生が最小限に抑えられます。

そのため、結果の代数型（hello、Rust）を自転車に乗せることが決定されました。代数型のpythonでは、すべてが悪いです。標準のenumライブラリのモジュールは、きれいな小腸のようなものです。

最悪のOOPの伝統では、継承を使用して結果コンストラクターOkとErrを定義します。そして、静的型付けを忘れないでください（ まあ、私はすでに3番目のバージョンを持っています！最終的にPythonで静的型付けをしてもいいですか？ ）：

result.py

 import abc from typing import * class Result(Generic[T, E], metaclass=abc.ABCMeta): """ enum Result< T > { Ok(T), Err(E), } """ #        def is_ok(self) -> bool: return False def is_err(self) -> bool: return False def ok(self) -> T: raise NotImplementedError def err(self) -> E: raise NotImplementedError ... class Ok(Generic[T, E], Result[T, E]): def __init__(self, ok: T) -> None: self._ok = ok def is_ok(self) -> bool: return True def ok(self) -> T: return self._ok ... class Err(Generic[T, E], Result[T, E]): def __init__(self, error: E) -> None: self._err = error def is_err(self) -> bool: return True def err(self) -> E: return self._err ...

いいね！機能的な変換から作られた小さなソースで味付けします。すべてが必要なわけではありませんので、必要最小限をとってください。

result.py（続き）

 class Result(Generic[T, E], metaclass=abc.ABCMeta): ... def ok_or(self, default: T) -> T: ... def err_or(self, default: E) -> E: ... def map(self, f: Callable[[T], U]) -> 'Result[U, E]': # -!           ? # ,   Python    "forward declaration". #    -.    PEP 484: # https://www.python.org/dev/peps/pep-0484/#forward-references ... def and_then(self, f: Callable[[T], 'Result[U, E]']) -> 'Result[U, E]': ... def __bool__(self) -> bool: #    `if` return self.is_ok()

そしてすぐに使用例：

結果の例

 def try_int(x: str) -> Result[int, str]: try: return Ok(int(x)) except ValueError as e: return Err(str(e)) def fn(arg: str) -> None: r = try_int(arg) # 'r' for 'Result' if not r: return print(r.err()) # one-liner, shortcut for `if r.is_err()` index = r.ok() print(index) # do something with index

このスタイルでの落書きは、各チャレンジに対して3行必要です。しかし、その後、どのエラーが発生した可能性があり、どのようなエラーが発生するかを明確に理解できます。さらに、コードは同じレベルのネストで継続されます。メソッドに半ダースの同種の呼び出しが含まれる場合、これは非常に重要な品質です。

パーサー、IResult、エラー:: {空、不完全、構文}、REPL、9600ボー、すべてすべて

パーサーは開発時間のかなりの部分を占めました。適切に設計されたパーサーは、製品のフロントエンドを使用する利便性をユーザーに提供する必要があります。パーサーの最も重要なタスクは次のとおりです。

エラー報告をクリアする
インタラクティブなインクリメンタルライン入力、またはより単純にREPL

「全体の」標準Pythonライブラリだけでなく、パーサー作成の控えめな知識もあるため、袖をまくり上げて手動の再帰下降パーサー（Eng。Recursive descent parser）を作成する必要があることに気付きました。これは長く退屈なビジネスですが、状況を高度に制御できます。

答えられるべき最初の質問の1つ：間違いをどうするか？どうなるか-すでに上で考え出した。しかし、間違いは何ですか？たとえば、「/ create table」の後に「if not exists」が存在する場合もあれば、存在しない場合もあります-これは間違いですか？もしそうなら、どのような？どこで処理する必要がありますか？（「一時停止」し、コメントでオプションを提案します。）

パーサーの最初のバージョンは、 2つのタイプのエラーを区別しました：予期された（1つを期待しますが、何か他のものを受け取りました）およびEOF（ファイルの終わり）前のサブクラスとして。 REPLに到達するまでは、すべて問題ありません。このようなパーサーは、部分的な入力（コマンドの開始）と何も存在しないこと（EOF、端末からの対話型入力について言えば）を区別しません。わずか1週間後、試行錯誤を繰り返して、ドメイン領域を満たすスキームを見つけることができました。

スキームは、すべてがストリームであり、パーサーはストリーム上のささやかなnext（）メソッドであるというものです。また、エラークラスは（Resultなどの）代数に書き換える必要があり、 EOFの代わりにEmptyオプションとIncompleteオプションが導入されます。

新しいタイプのエラー

 class Error(metaclass=abc.ABCMeta): """ enum Error { Empty, Incomplete, Syntax { expected: str, got: str }, } """ def empty_to_incomplete(self) -> 'Error': if isinstance(self, Empty): return Incomplete() else: return self class Empty(Error): ... class Incomplete(Error): ... class Syntax(Error): def __init__(self, expected: str, got: str) -> None: ... # stream-specific result type alias IResult = Result[T, Error] IOk = Ok[T, Error] IErr = Err[T, Error]

ストリームインターフェース

 class Stream(Generic[T], metaclass=abc.ABCMeta): def current(self) -> IResult[T]: ... def next(self) -> IResult[T]: ... def collect(self) -> IResult[List[T]]: ... def peek(self) -> IResult[T]: ... def back(self, n: int = 1) -> None: ... @abc.abstractmethod def next_impl(self) -> IResult[T]: ...

フローは抽象化です。ストリームは、どの要素を生成するかを気にしません。ストリームはいつ停止するかを知っています。ストリームを実装するために必要なことは、抽象メソッドnext_impl（）-> IResult [T]のみを書き換えることです。このメソッドを返すものは何ですか？トークンストリームの例を考えてみましょう。

次は何ですか	例（入力）	結果タイプ	例（結果）
すべてがうまくいく、別の要素	/ tから削除...	IOk（トークン）	IOk（削除（））
ギャップとコメントのみが残っています	\ n-ワバ -ルバ -ダブダブ！	IErr（空（））	IErr（空（））
もっと何かの始まり	'文字列... （閉じ引用符なし）	IErr（不完全（））	IErr（不完全（））
あなたは私にいくつかのゲームをこする	＃$％	IErr（構文（...））	IErr（構文（expected = 'token'、got = '＃'））

ストリームは階層構造になっています。各レベルには独自のバッファーが含まれており、必要に応じて先読み（ peek（）-> IResult [T] ）およびロールバック（ back（n：int = 1）-> None ）が可能です。

そして、最良の部分は、ストリームをすべてのIOk（要素）の 1つの大きなリストに「アセンブル」できることです。これにより、 next（） -もちろん最初のIErr（）までが得られます。 IErrにEmptyが含まれている場合にのみ、リストは何を返しますか。そうでない場合、エラーはより高くスローされます。この設計により、REPLを簡単かつエレガントに構築できます。

REPL Foundation

 class Repl: def reset(self): self.buffer = '' self.PS = self.PS1 def start(self): self.reset() while True: self.buffer += input(self.PS) self.buffer += '\n' stmts = Statements.from_str(self.buffer).collect() if stmts.is_ok(): ... # execute one-by-one self.reset() elif stmts.err().is_incomplete(): self.PS = self.PS2 # read more elif stmts.err().is_syntax(): print(stmts.err()) self.reset() else: pass # ignore Err(Empty())

キャラクター

このストリームは、文字列の文字を通過します。唯一のタイプのエラー：行の最後が空です。

トークン

トークンフロー。彼のミドルネームはレクサーです。エラー、閉じ引用符のない行、およびすべてがあります...

各キーワードを個別に含むトークンの各タイプは、抽象トークンクラスの個別のバリアントクラスで表されます（または、列挙型トークンと考える方がよいでしょうか？）これは、ステートメントパーサーがトークンを特定のタイプにキャストするのに便利です。

典型的な字句解析部

  def next_impl(self, ...) -> IResult[Token]: ... char = self.characters.current().ok() if char == ',': self.characters.next() return IOk(Comma()) elif char == '(': self.characters.next() return IOk(LParen()) elif ...

声明

クライマックス、パーサー。数千の単語の代わりに、いくつかのスニペット：

ストリーム/statements.py

 class Statements(Stream[AstStmt]): def __init__(self, tokens: Stream[Token]) -> None: super().__init__() self.tokens = tokens @classmethod def from_str(cls, source: str) -> 'Statements': return Statements(Tokens.from_str(source)) def next_impl(self) -> IResult[AstStmt]: t = self.tokens.peek() if not t: return Err(t.err()) tok = t.ok() if isinstance(tok, Create): return CreateTable.from_sql(self.tokens) if isinstance(tok, Drop): return DropTable.from_sql(self.tokens) if isinstance(tok, Insert): return InsertInto.from_sql(self.tokens) if isinstance(tok, Delete): return DeleteFrom.from_sql(self.tokens) if isinstance(tok, Update): return UpdateSet.from_sql(self.tokens) if isinstance(tok, Select): return SelectFrom.from_sql(self.tokens) return Err(Syntax('/create, /drop, /insert, /delete, /update or /select', str(tok)))

ast / delete_from.py

 class DeleteFrom(AstStmt): def __init__(self, table: Identifier, where: Optional[Expression]) -> None: super().__init__() self.table = table self.where = where @classmethod def from_sql(cls, tokens: Stream[Token]) -> IResult['DeleteFrom']: """ /delete_stmt : "/delete" "from" /table_name /where_clause /drop ; """ # next item must be the "/delete" token t = tokens.next().and_then(Cast(Delete)) if not t: return IErr(t.err()) t = tokens.next().and_then(Cast(From)) if not t: return IErr(t.err().empty_to_incomplete()) t = tokens.next().and_then(Cast(Identifier)) if not t: return IErr(t.err().empty_to_incomplete()) table = t.ok() t = WhereFromSQL.from_sql(tokens) if not t: return IErr(t.err().empty_to_incomplete()) where = t.ok() t = tokens.next().and_then(Cast(Drop)) if not t: return IErr(t.err().empty_to_incomplete()) return IOk(DeleteFrom(table, where))

REPLが正しく機能するためには、最初のパーサーを除き、タイプがEmptyのエラーはすべてパーサーがIncompleteに変換する必要があることに注意することが重要です。これには補助関数empty_to_incomplete（）-> Errorがあります 。マクロではありません。マクロはありません。t：if IErr（t.err（）。Empty_to_incomplete（））は、コードベースで少なくとも50回発生し、何も実行されません。真剣に、ある時点で、Syshnyプリプロセッサを使用したかったのです。

プロバイナリ形式

グローバルに、データベースファイルはブロックに分割され、ファイルサイズはブロックのサイズの倍数になります。デフォルトのブロックサイズは12 KiBですが、オプションで18、24、または36 KiBに増やすことができます。あなたが魔術の悪魔主義者であり、あなたが非常に大きなデータを持っているなら、あなたはそれを42 KiBまで上げることさえできます。

ブロックには最初から番号が付けられます。ゼロブロックには、データベース全体に関するメタデータが含まれています。その背後には、テーブルメタデータ用の16ブロックがあります。ブロック＃17はデータブロックで始まります。 ブロックへのポインタは、 ブロックシーケンス番号と呼ばれます。

現在、データベースメタデータはそれほど多くはありません。名前は最大256バイトで、データブロックの数です。

テーブルのメタブロックは最も困難です。ここには、テーブルの名前、すべての列とそのタイプのリスト、レコード数、およびデータブロックへのポインターが保存されます。

テーブルの数はコードで固定されています。ただし、データベースのメタブロックにテーブルのメタブロックへのポインタを格納すると、これは比較的簡単に修正できます。

ブロックへのポインタは、iノード内のポインタの原理で機能します。 Tanenbaumと他の何十人もの尊敬される人々は、このことについて美しく書きました。したがって、テーブルはデータブロックを「ページ」と見なします。違いは、テーブルの観点から順番に来るページが、神が魂を置くようにファイル内に物理的に配置されることです。 OSの仮想メモリとの類似性の描画、ページ：仮想ページ番号、ブロック：物理ページ番号。

データブロック自体には特定の構造はありません。しかし、ポインタによって指示された順序で結合されると、固定長のレコード（レコード/タプル）の連続ストリームとして表示されます。したがって、レコードのシリアル番号を知り、それを抽出または書き込むことは、ほぼ一定時間O（1 ^* ）の操作であり、必要に応じて新しいブロックの割り当てを減価します。

レコードの最初のバイトには、このレコードが生きているか削除されたかに関する情報が含まれています。データのパックとアンパックに関する残りの作業は、標準のstructモジュールによって行われます。

/更新操作は常に「インプレース」を上書きし、/ deleteは最初のバイトのみを置き換えます。 VACUUM操作はサポートされていません。

テーブル操作、RowSet、および結合について

テープのいくつかのかせで2つの世界のベストをしっかりと固定する時です。

左側のMC -ASTトップレベルノード（AstStmtサブクラス）。それらの実行は、データベースへの接続のコンテキストで発生します。位置引数もサポートされています-リクエスト本文の式にある「？N」トークン。たとえば、「/ delete from student / where name =？1 / drop」。式自体は再帰的であり、その計算は科学的なブレークスルーを構成しません。

右側のMCは、テーブル内のシーケンス番号を識別子として使用して、レコードを1つずつ操作するデータベースドライバーです。彼が知っているのは、どのテーブルが存在し、どのようにテーブルを操作するかを知っていることだけです。

行こう！

創造性に関する彼らの最初の共同シングル。新しいテーブルを作成するのは、最初の空の記述子である16を見つけてそこに名前と列のリストを入力するのと同じくらい簡単です。

次に、シンボリック名/ドロップのトラック。デモレコードのホームバージョンでは、次のことが起こります。1）名前でテーブル記述子を見つけます。 2）ゼロにリセットします。誰がデータページの未リリースブロックを気にしますか？

挿入は列の順序に違反しているため、書き込み用のタプルを送信する前に、特別なフィルターtransition_vectorを通過します。

さらに、テーブルエントリの操作について説明しますので、すぐに審判RowSetを紹介します。

真空中の球状RowSet

 class RowSet(metaclass=abc.ABCMeta): @abc.abstractmethod def columns(self) -> List[Column]: """ Describe columns in this row set. """ @abc.abstractmethod def iter(self) -> Iterator['Row']: """ Return a generator which yields rows from the underlying row stream or a table. """

この獣の主な特定の亜種-TableRowSet-は、すべてのライブ（削除されていない）レコードを順番に選択します。 dropSQLの他の種類のRowSetは、必要な最小の関係代数を実装します。

関係代数演算子	指定	クラス
投影	π _{（ID、NAME）} expr	ProjectionRowSet
名前を変更	ρa _{/ b} expr	ProjectionRowSet + RenameTableRowSet
サンプリング	σ _{（PRICE> 90）} expr	FilteredRowSet
デカルト積	製品×販売者	CrossJoinRowSet
内部結合（拡張機能と呼びます）	σ _（条件）（A x B）	InnerJoinRowSet = FilteredRowSet（ CrossJoinRowSet（...））

さらに、プログラム可能なMockRowSetもあります。テストに適しています。また、その助けを借りて、「 / autism 」と呼ばれるマスターテーブルにアクセスできます。

美しさは、さまざまなRowSetsを自由に組み合わせることができることです。「学生」テーブルを選択し、エイリアス「S」を指定し、「/ where scholarship> '12k'」を除外し、別のテーブル「courses」を選択し、「/ on（course / sid = S / id）/ and（course / grade <'B'） "、project into" S / id、S / first_name / as / name "-これは次の階層で表されます。

 ProjectionRowSet([S/id, S/first_name/as/name]) FilteredRowSet((course/sid = S/id) /and (course/grade < 'B')) CrossJoinRowSet FilteredRowSet(scholarship > '12k') RenameTableRowSet('S') TableRowSet('student') TableRowSet('courses')

そのため、このような強力な楽器を装備して、16世紀のリュート音楽に戻ります...

4番目のトラック/ selectについて、これ以上追加するものはありません。 RowSetsの交響曲は、魂を魅了するようなものです。これにより、実装は非常に簡潔になりました。

実装/選択...から

 class SelectFrom(AstStmt): ... def execute(self, db: 'fs.DBFile', args: ARGS_TYPE = ()) -> Result['RowSet', str]: r = self.table.row_set(db) if not r: return Err(r.err()) rs = r.ok() for join in self.joins: r = join.join(rs, db, args) if not r: return Err(r.err()) rs = r.ok() if self.where is not None: rs = FilteredRowSet(rs, self.where, args) rs = ProjectionRowSet(rs, self.columns, args) return Ok(rs)

最後の2つ： / updateおよび/ deleteは、前任者の実績を使用します。さらに、/ updateは、上記のtransition_vectorに似た手法を使用します。

こんなコンサート！ご清聴ありがとうございました！カーテン！..

ウィッシュリスト

まだ実現していない夢：

サポート/パーサーだけでなく主キー
単項演算子
ネストされたクエリ
式の型推論
Python用の便利なAPI

これはトレーニングプロジェクトであったため、私たちはそれに対してペニーを得ることができませんでした。しかし、slocの統計から判断すると、彼らは今では赤キャビアを食べることができました。

Sloccountレポート

 Have a non-directory at the top, so creating directory top_dir Creating filelist for dropSQL Creating filelist for tests Creating filelist for util Categorizing files. Finding a working MD5 command.... Found a working MD5 command. Computing results. SLOC Directory SLOC-by-Language (Sorted) 2764 dropSQL python=2764 675 tests python=675 28 util python=28 Totals grouped by language (dominant language first): python: 3467 (100.00%) Total Physical Source Lines of Code (SLOC) = 3,467 Development Effort Estimate, Person-Years (Person-Months) = 0.74 (8.85) (Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05)) Schedule Estimate, Years (Months) = 0.48 (5.73) (Basic COCOMO model, Months = 2.5 * (person-months**0.38)) Estimated Average Number of Developers (Effort/Schedule) = 1.55 Total Estimated Cost to Develop = $ 99,677 (average salary = $56,286/year, overhead = 2.40). SLOCCount, Copyright (C) 2001-2004 David A. Wheeler SLOCCount is Open Source Software/Free Software, licensed under the GNU GPL. SLOCCount comes with ABSOLUTELY NO WARRANTY, and you are welcome to redistribute it under certain conditions as specified by the GNU GPL license; see the documentation for details. Please credit this data as "generated using David A. Wheeler's 'SLOCCount'."

謝辞

イノポリス大学の居心地の良い環境と素晴らしい出会い
コンパイラ全般に関するコース、特にパーサーに関する講義については、Yevgeny Zuev教授
DBMSコースについては、Manuel Mazzara教授とTA Ruslan教授に。 / GodBlessMazzara

そして次回は、パイプラインとトランザクションを集約した非リレーショナルモードを実装します。そしてそれを呼び出す-/ noDropSQL！

3週間でDBMSを所有します。 毎日少し時間が必要です...