3

インデックスを持つデータベース テーブルのインメモリ アナログを設計しようとしています。このようなテーブルをクエリするためのきちんとしたDSLを実装しました

table.select do
  age > 44
  name == "Adam"
end

などのConditionクラスのインスタンスの束を生成します。まあ、それは簡単な部分です。これらの条件を調べて、クエリを実行する適切なインデックスを選択します。私が立ち往生しているのは、どのような種類のパラメーターを受け入れる必要があるのですか? テーブルの select メソッドと同じパラメーターを受け入れると、同じ作業が 2 回行われます。年齢が 25 歳以上の全員を選択する必要があるとします。最初に、Table クラスは (年齢、名前) に使用できるインデックスがあることを確認します。次に、インデックスは、これがキーの一部のみを含む範囲クエリであると判断し、それに応じて実行する必要があります。EqConditionGteConditionTableIndex#select

これを適切に設計する方法についていくつかのアイデアを求めています (実際のデータベースで行われている方法のより単純なバージョンかもしれません)。

PS。それはRubyですが、関係ないと思います。Java/C# では、次のようになります。table.select(new GtCondition("age", 44), new EqCondition("name", "Adam"))

4

1 に答える 1

0

DBMS でのインデックスの意図は次のとおりであることを考慮してください。

  • IOを減らす
  • 結合を最適化する
  • 副作用として: いくつかの制約 (PK/FK など) を強制するのに役立ちます。

メモリ内のすべてのデータを操作している場合、線形スキャンを実行するだけで十分な場合があります:)

確信が持てない場合は、プロファイラーを使用してください...たとえば、1000 個の要素のメモリ内コレクションが小さいことがわかります。コードに JOIN がない場合は、単純なものを使用するcollection.filter(condition)だけでおそらく十分です。

しかし、データベースではどのように機能するのでしょうか? 大まかなアイデアは次のとおりです。

  • まず、SELECT 式が「正規ツリー」に変換されます。たとえば、次のSELECT A.NAME,B.SOMETHING FROM A, B WHERE A.NAME=B.NAME AND B.OTHER > 10ように表すことができます。

    PROJECT(A.NAME, B.SOMETHING)
           |
FILTER(A.NAME=B.NAME, B.OTHER>10)
           |
    CARTESIAN PRODUCT
     |              |
PROJECT(A.NAME)     PROJECT(B.OTHER,B.SOMETHING)

  • その式ツリーから、適用できるいくつかの代数規則があります。目標は、非常に非効率的なため、デカルト積を回避することです。

    PROJECT(A.NAME, B.SOMETHING)
           |
    EQ-JOIN A,B USING NAME
     |              |
PROJECT(A.NAME)     FILTER B.OTHER>10     
                    |
       PROJECT(B.OTHER,B.SOMETHING)

  • DBMS エンジンは、ツリーとデータベースのメタデータ (インデックスの種類、レコード数など) を分析し、ツリーを変更して最適化します (つまり、クエリ プラン)。たとえば、B が OTHER でソートされている場合は、最初に FILTER を実行することをお勧めします。

    PROJECT(A.NAME, B.SOMETHING)
           |
    EQ-JOIN A,B USING NAME (NESTED LOOP JOIN)
     |              |
 PROJECT(A.NAME)    PROJECT(B.OTHER,B.SOMETHING)
                    |
                  FILTER B.OTHER>10 (UNSING INDEX ON OTHER)

  • しかし、それを行うと、メモリに B のバッファーがあり、インデックス情報が失われ、インデックスを使用できなくなる可能性があります (結合の唯一のオプションは、ネストされたループを使用することです)。したがって、エンジンはそれを検出し、より良い計画を選択できます。

    PROJECT(A.NAME, B.SOMETHING)
           |
     FILTER B.OTHER>10
           |
    EQ-JOIN A,B USING NAME (HASH INDEX EQ-JOIN)
     |              |
 PROJECT(A.NAME)    PROJECT(B.OTHER,B.SOMETHING)

これでプランの準備は完了です。それはプログラムのようなものです。エンジンは盲目的にそれに従います。

インメモリエンジンでそれをどのように使用できますか? EQUI JOINS を検出し、ハッシュ テーブルを使用するように「計画」を変換できます。バランスの取れたツリーを使用して他の種類のインデックスを実装できるかもしれませんが、おそらくあまり役​​に立ちません: メモリ内の O(n) アルゴリズムは問題ありません。O(nxm) オーダーは避ける必要があります。つまり、デカルト積を避けることを意味します。

あなたができるヒューリスティックはこれです：

  • すべての等しいフィルター (つまり、name=="Adam") を検出し、テーブルにフィールドのハッシュ インデックスがある場合は、最初にそれを使用しますtable.findUsingHash('name', 'Adam')。

  • 次に、結果をスキャンしてフィルタリングします (つまり、年齢 > 44):filter(table.findUsingHash('name', 'Adam'), function (e) { return e.age > 44 })

アイデアは、最も選択的なインデックスを最初に実行することです。そのため、O(n) スキャンの n は小さくなります。

注:私は長い間、この種の DBMS を行っていません。そのため、私のツリー ダイアグラムには間違いが含まれている可能性があります。より適切な情報源については、DBMS の本 (このようなもの) を参照してください。

于 2013-01-18T01:21:31.470 に答える