はじめに

本記事はPERSOL PROCESS & TECHNOLOGY Advent Calendar 2020の15日目の記事になります。
偉大な同期・先輩方が色々な面白い記事を書いてくださっているので、ぜひご覧ください！
特にこちらの記事は読みごたえがあり、とても興味深い内容となっています。

記事の概要

この記事では、この1週間でチャレンジしてみた自作(R)DBMSの紹介をします。使っている言語はpythonとなります。
かなり手探りで実装している内容になりますので、どうか暖かな目でご覧ください。
また、これを読んで自作DBMSerが増えてくれればとても嬉しいです。

なんでDBMS？

元はといえば、秋に受けたDB試験の熱がまだあったからですが、
DBMSの自作を思い立ったのは、主にこれらを知りたかった・試してみたかったからです。

どういった方法でクエリを最適化しているのか
トランザクションはどう実装されているのか
実際にパフォーマンスが改善されていく様子を観察したい

この記事は、~~上記をほとんど実装しきれていないので~~、解説というよりは、読んでくださっている皆さんが少しでも自作DBMSに興味を持ってくれることを目的として書いていきます。

DBMSについて

DBMSとは、データベースマネジメントシステムの頭文字を取った略称で、有名なものだとMySQLやPostgreSQL、OracleDBなどがこれに該当します。
DBMSというのはデータベースと切っても切れない関係であり、DBMSも併せて「データベース」と呼んでいる人も多いんじゃないかと思います。少なくとも自分はそうです。

さて、DBMSでは実際にどのような処理を行っているのでしょうか。大きく分けて3つの部品に分けることができます。

１．SQLの構文解析と実行を行う部品

入力されたSQLの構文を解析(パーサ)
最適な実行順序を計画(オプティマイザ)
解析されたクエリを実行

２．データベース内部の情報を管理する部品

テーブルやビュー定義(カタログ情報)
データを読み書きするための一時保存場所(バッファ)。ファイルアクセスがボトルネックなので、ここを最大限使用してファイルアクセス回数を減らす。
ブロックサイズやファイル構造の決定(ストレージ)

３．複数のアプリケーションでの処理を可能にする部品

複数のアプリケーションでのデータベース操作を行い、エラーの際にロールバックを行う(トランザクション)。
複数のアプリケーションから命令を受け付けた場合の干渉を防ぐ。

本記事では「１．SQLの構文解析と実行を行う部品」について触れていきます。~~2と3は未実装のため~~

SQLの構文解析

最初に、SQLの構文解析について説明します。

今回の実装では、SQL文法の構文木を組み立てることで構文解析を行いました。
構文木にした理由は、それぞれの文法を1つのまとまりとして扱うことが可能になるからです。

SQLの文法はある程度形が決まっています。例えばSELECT文の場合、それぞれの句は以下のように分解できます。
・SELECT [カラムのリスト]
・FROM [テーブルのリスト]
・WHERE [条件式]
これをSELECT文の1つの単位として、木構造を作ります。
※今回はORDER BYやGROUP BY、JOINなどは割愛します。

以下が実装例となります。

Parser.py

class Parser:
    def __init__(self):
        # クエリの走査位置
        self.cur = 0

    class SelectNode():
        def __init__(self):
            self.node_name = 'SELECT'
            self.select_list = []
            self.from_list = []
            self.where_list = []

    def parse_select_clause(self, line):
        select_node = self.SelectNode()

        #SELECT句の取得
        select_node.select_list = self.select_parse()
        #FROM句の取得
        select_node.from_list = self.from_parse()
        #WHERE句の取得
        select_node.where_list = self.where_parse()

        return select_node

self.○○_parse()内では各文法のパースを行い、もしサブクエリを発見した場合はparse_select_clause()への再帰処理を行います。
例えばSELECT句のパースは、カンマや演算子などで文字列を分割し、そこからカラム名以外の余分な文字を取り除いていきます。
※それぞれの句のパースはあまりにも冗長になってしまったためカットしました。

ex1.sql

SELECT user_id FROM users WHERE user_id = (SELECT user_id FROM orders WHERE order_id = 1);

例えば上記ex1.sqlのようなSQLがあった場合、上記のパースを適用すると、以下のような構造が出力されます。

SELECT
   user_id
FROM
   users
WHERE
   user_id
   =
   SELECT
      user_id
   FROM
      orders
   WHERE
      order_id
      =
      1

出力結果が少し分かり辛いですが、サブクエリ内はネストが1深くなっていて、問題無くパース出来ていることがわかります。
~~※ただし、これは最低限の実装なので、厳密にやろうとすると苦行を強いられることになります。~~

実行プラン

ここまでの成果として、SQL文で構文木を組み立て、命令の対象と実行順序を扱いやすくすることができました。
次に、効率的に命令を実行するためのプランを考えます。例として結合を挙げてみます。

例えば、以下のSQL文を実行するとします。

ex2.sql

SELECT
 user_id 
FROM
 users
JOIN
 orders
ON 
 users.user_id = orders.user_id
WHERE
 orders.num > 10;

ここで、usersテーブル、ordersテーブルにそれぞれ100万件ずつレコードが存在すると仮定します。
比較的簡単に思いつく実装だと、2つのテーブルそれぞれのレコードでループを回して結合することになると思います。
その結果として、100万×100万=1兆ループが爆誕します。
言語にもよりますがコンピュータは大体1秒間に10⁹回の処理を行うことができるので、約1000秒かかります。

結合実装例

#結合後テーブル
join_table = []

#結合元
for t1 in table_from.table_data:
    #結合先
    for t2 in table_to.table_data:
        if t1.user_id == t2.user_id:
            join_table.append(t1 + t2)

ここで、WHERE句の条件を見てみると、ordersテーブルのみの条件だとわかるので、ordersテーブルだけ予め絞り込んでから結合を行えば、ある程度レコード数を減らすことが出来そうです。
また、後述するソート結合やインデックスなどを使えば全てのデータを走査する必要が無くなる可能性があります。

実行プランの最適化いろいろ

ソート結合

名前の通り、ソートしてから結合を行います。
例えば以下のようなuser_idでソート済みのテーブルとレコードがあるとします。

orderテーブル

order_id	num	shohin_id	user_id
12	1	1	1
3	2	3	2
8	2	1	2
4	4	2	2
1	3	3	3
9	1	2	4
10	5	2	5

userテーブル

user_id	age
1	10
4	40
6	60

これをuser_idが等しいもので結合すると、orderテーブルの1レコード目の走査(orderテーブル：user_id=1、userテーブル：user_id=1,4,6)では、2レコード目からは1より上の値なので、ループを途中で止めることができます。
一見速そうに見えますが、両方のテーブルをソートするのはコストが高いので、使いどころは限定的になります。

インデックス

次に、実際に使う機会が多いと思われるインデックスについてですが、詳細な解説は他のブログを見ていただくのが良いと思います。

RDBMSでは、主にB+ツリーというアルゴリズムを用いたインデックスが採用されています。(単にBツリーと表記されていることもある)
ハードディスクへのアクセスはブロック単位で行うため、複数のブロックをノードに格納できるB+ツリーはデータへのアクセス回数を最小限に抑えることができ、検索処理が高速になります。

まとめ

いかがでしたか？
DBMSを自作する過程で調査した内容や実装方針、実装例などをまとめてみました。
自作をする上でとても困ったことは、パースがなかなか上手くできなかったことです。これに関しては、SQLのパース用ライブラリなどを使用するべきだったと後悔しています。
実装の途中なので、トランザクションまでを目標に実装を続けていきたいと思っています。

また、DBMSに限ったことではありませんが、自作DBMSをすることでコーディング力の向上を感じるだけでなく、知識の獲得や効率的な使い方の発見に繋がることを実感しました。

更に、次のような恩恵を感じています。

実際の処理工程をなぞっていくことで、DBMSに関する理解が深まった。
低レイヤに対する興味が出てきた。
競プロ再開のモチベが湧いた。

このように、自作DBMSには良いことしかありません。自作DBMSはいいぞ。

自作DBMSにチャレンジしてみた