1

私は非常に単純なデータベースを C++ でゼロから SQL パーサーと共にプログラミングしています。私はすべてをやった。したがって、次のような SQL 入力があるとします。

SELECT * FROM table WHERE `First Name`="John" AND `Last Name`="Doe"

パーサーはこれを解析します。今の問題は、その情報を使って何かをすることです。テーブルを調べて、名が John で姓が Doe であるすべてのレコードを実際に見つける必要があります。

AND をメイン ノードとし、子ノードとするツリーを実装できると考えてい==ました。左の子がファーストネーム、右の子がラストネームです。そして、それが true の場合はいつでも、そのレコードをベクターにプッシュし、最後にベクターを出力します。

これはすべて理論的には素晴らしいように思えますが、実際にこれをどのように実装するかはわかりません。次のようなifステートメントがある場合

if(record.firstname == "John")

動的に変更するにはどうすればよいです==か!=。

4

1 に答える 1

7

必要なのは、SQL を直接実行できる言語に変換することです。これの専門用語は「クエリ プラン」です。クエリ プランは、データベース エンジンが実行する低レベルの操作 (インデックス検索、結合、並べ替えなど) と、操作がどのように組み合わされるかです。

適切なデータベース エンジンであれば、クエリ プランを確認できます。SQL システムの場合、通常は と呼ばれEXPLAINます。お気に入りの DBMS を入手し (お気に入りがない場合は、MySQL や PostgreSQL を含む、適切なオープン ソース DBMS のすべてがそれを実行します)、さまざまなクエリの計画を調べて、「実際の」操作の種類を確認することをお勧めします。 」 システムを実装します。

また、関係代数を調べることをお勧めします。品揃えの豊富なライブラリにアクセスできる場合、データベースに関するまともな教科書にはセクションまたは章がありますが、Google に尋ねると、かなりの数の優れた参考文献が返されます。リレーショナル代数には、理論的に優れているという利点と、低レベルのデータベース操作を使用してそれを実装する「明白な」方法があるという利点があります。認識を超えて変更することになるかもしれませんが、これは良いスタートになるはずです。

それでは、基本的な概要を見てみましょう。最初に関係代数について読んでから読み進めてください。

実装する必要がある主なデータ構造は、タプルのストリームです。ストリーム内の各タプルは異なりますが、形状はすべて同じです。タプルの各フィールドには名前と型があります。クエリ操作は、タプルの 1 つ以上のストリーム (ちなみに、テーブルはタプルのストリームと考えることができます) を取り、タプルの単一のストリームを返します。

次の形式の基本的な SQLSELECTステートメントを考えてみましょう。

SELECT fields
FROM table1,table2
WHERE select_conditions, join_conditions

ここでは、 フィールドが定数と比較されるやselect_conditionsなどの条件があります。あるテーブルのフィールドを別のテーブルのフィールドと照合する条件です。(当面は、同じテーブルの 2 つのフィールドを比較するケースは無視します。)gender='F'age > 18join_conditions

次に、単純なクエリ プランは次のようになります。

s1 := Select(table1, select_conditions_1)
s2 := Select(table2, select_conditions_2)
j := Join(join_conditions, s1, s2)
res := Project(fields, j)

このSelect操作はタプルのストリームを受け取り、同じ形状のタプルのストリームを返します。条件に一致しないタプルはすべて削除されます。このProject操作はタプルのストリームを受け取り、異なるタイプのタプルのストリームを返します。フィールドを削除、再配置、または複製するだけです。最後に、Join操作はタプルの 2 つのストリームを結合し、結合条件に一致する任意の 2 つのタプルを結合します。(データベース結合操作が何であるかを知らない場合は、これを知る必要があります。Google に尋ねて、Unix の「結合」コマンドも調べてください。)

したがって、この場合、s1は、テーブル 1 に適用される選択条件に一致するテーブル 1 からのタプルを表すタプルのストリームですs2。ストリームjはストリームs1でありs2、結合条件に従って結合されます。最後に、クエリで言及されているフィールドのみを射影します。

SQL をリレーショナル代数のような中間形式に変換するのは、実際には非常に簡単です。ただし、単純な翻訳は非常に効率が悪い傾向があります。ここでは、テーブル内のすべてのレコードを調べて、一致するものだけを返すことにより、選択操作を実装します。そのため、クエリの構造とテーブルで利用可能な情報の両方に基づいて、クエリを最適化する必要があります。

たとえば、table1にフィールドageおよびgenderがあり、選択条件age > 18およびがあるとしますgender = 'F'。さらに、 がフィールドにtable1インデックス ( と呼ばれるtable1_age_idx) を持っているが、ageフィールドにインデックスを持っていないとしgenderます。明らかに、インデックスを使用する必要があります。これを行うには、操作をさらに 2 つの基本的な操作に分割します。

s1a := IndexSelect(table1_age_idx, age > 18)
s2b := FilterSelect(s1a, gender = 'F')

ここでは、選択操作を 2 つに分割しました。最初の select はインデックス クエリを使用して実装されます (select はテーブルではなくインデックス上にあることに注意してください! gender) 'F'。

結合の実装は、さまざまな方法で行うことができます (ソートマージ結合とハッシュ結合が一般的です)。どちらが最適かは、クエリとデータベースによって異なります。一部のインデックス (B ツリーなど) はキーでソートされたレコードを返すため、IndexSelect後で結合するフィールドに対して既に を実行している場合は、ソートが不要なため、おそらくソートマージ結合の方が適しています。ORDER BY結合フィールドに句がある場合も同様です。

ご覧のとおり、ここで本当に巧妙なことが起こります。実際のクエリ オプティマイザは、計算の一部として、テーブルのサイズと中間タプル ストリームの予想サイズに関する統計を使用します。ここで、コンパイラについて少し知っておくと役に立ちます。

于 2013-02-21T05:37:02.420 に答える