Advent LINQ (22) : 解釈するクエリの範囲

LINQプロバイダーがクエリを解釈する範囲を定める必要がある。以下のLINQクエリについて考えてみる。

var r = new Random();
// 乱数から、5で割り切れる数を抽出
var div5 =
    from index in Enumerable.Range(0, 100000)
    let value = r.Next()
    where (value % 5) == 0
    select value;
// 更に3で割り切れる数を抽出
var div5and3 =
    from value in div5
    where (value % 3) == 0
    select value;

これは「人類の英知」によって、以下のクエリに変形できる。

// 乱数から、5と3で割り切れる数を抽出
var div5and3 =
    from index in Enumerable.Range(0, 100000)
    let value = r.Next()
    where ((value % 5) == 0) && ((value % 3) == 0)
    select value;

最初のクエリ例は、そのまま実行される事になる。注目するのは、クエリ全体でwhere条件が2回実行されることだ。人間がこのクエリを見れば、等価な後の例に変形する事が出来る。そして、LINQクエリがIQueryableによるExpressionであった場合、記述通りの式が得られる。つまり、where条件が2回記述された式だ。後の例に変形する必要がある場合、それはLINQプロバイダーの責任となる。
TerraServerのサンプル例では、このような最適化を諦めている。つまり、仮にwhere条件が2回以上現れても、最適化を行わない。実際にはどのような結果となるだろうか?
この挙動を決定しているのが、「InnerMostWhereFinder」クラスだ。
InnerMostWhereFinderの話をする前に、クエリとExpressionの対応を再確認しよう。

// LINQ to Entitiesによるクエリの例
using (var context = new AdventureWorksLT2012_DataEntities())
{
    var addresses =
        from customerAddress in context.CustomerAddress
        where customerAddress.AddressType == "Shipping"
        select customerAddress;
}

もう何度も出ている例だが、実はまだこれをメソッド形式で例示していない。

// メソッド形式に変更
using (var context = new AdventureWorksLT2012_DataEntities())
{
    var addresses =
        context.CustomerAddress.
        Where(customerAddress => customerAddress.AddressType == "Shipping");
}

select句はそのまま射影しているだけなので省く。ところでこれは、C#の拡張メソッドで記述している。そのため、「本当のところのメソッド呼び出し」と同じではない。更に書き換えると、以下のようになる。

// 本当のメソッド呼び出し
using (var context = new AdventureWorksLT2012_DataEntities())
{
    var addresses =
        Queryable.Where(
            context.CustomerAddress.
            customerAddress => customerAddress.AddressType == "Shipping");
}

Where拡張メソッドは、元々Queryableクラスのstaticなメソッドだ。第一引数はIQueryableのインスタンス(context.CustomerAddress)、第二引数がWhere条件を示すラムダ式(そして、これをExpressionで受ける)だ。
つまり、結果の「addresses」は、上記のQueryable.Where呼び出しがExpressionとして表現されたもの、となる。確かめたい場合は、addressesがIQueryableなので、Expressionプロパティを見てみると良い。
さて、仮にWhere条件が2つに分かれていたら、どうだろうか。

// Where条件が2つ存在する
using (var context = new AdventureWorksLT2012_DataEntities())
{
    // Shippingとマークされた住所を抽出
    var addresses =
        Queryable.Where(
            context.CustomerAddress.
            customerAddress => customerAddress.AddressType == "Shipping");
    // 更にそこから2003年以降のものを抽出
    var addresses2003 =
        Queryable.Where(
            addresses.
            customerAddress => customerAddress.ModifiedDate >= new DateTime(2003, 1, 1));
}

これを、Expressionとして分かりやすくするために、一つの式にまとめる(Where条件は分けたまま)。

// Where条件が2つ存在する
using (var context = new AdventureWorksLT2012_DataEntities())
{
    // Shippingとマークされた住所を抽出し、更にそこから2003年以降のものを抽出
    var addresses2003 =
        Queryable.Where(
            Queryable.Where(
                context.CustomerAddress.
                customerAddress => customerAddress.AddressType == "Shipping"),
            customerAddress => customerAddress.ModifiedDate >= new DateTime(2003, 1, 1));
}

ここまで変形すれば、Expressionがどのような構造になっているのか、何となく想像がつくと思う。Whereメソッドの呼び出しはネストしていて、「内側」の条件式と「外側」の条件式は、明確に分かれている。
さて、TerraServerのウェブサービスで利用できる検索機能は、LINQクエリのそれと比べて非常に単純なものとなる。恐らく殆どのストレージサービスは、LINQクエリの検索条件の柔軟性と比べて、著しく劣るはずだ。逆に、SQL ServerとLINQ to SQL(またはLINQ to Entitites)とを比較すると、LINQクエリの検索条件の表現力は劣る。Transact-SQLで記述できるクエリははるかに柔軟であり、LINQクエリで表現可能な範囲は狭い。
このギャップをどのように埋めるかと言う事を考える必要がある。TerraServerに絞って考えるなら、仮にLINQクエリで必要以上に複雑な検索条件を指定された場合、それをどこまで再現するかだ。
最初の例で示したように、人間が柔軟に考えるのと同じような最適化を、Expressionを探索する事によって実現する事は不可能ではない。ただ、それは相当大変なことだ。
そこで(かどうかは分からないが)、TerraServerのサンプルでは大胆に割り切っている。LINQクエリの全体の式から、最も内側の検索条件を探し出し、その条件だけを解釈してサービスに送る、というものだ。そして、サービスから結果が返ってきたら、その後はLINQ to Objectsで処理させる、つまりインメモリで絞り込ませる。
そのために、Expressionのツリーから、最も内側のWhere句の位置を探し出す必要がある。この処理を行うのが、「InnerMostWhereFinder」クラスだ。このクラスはExpressionVisitorを継承し、与えられたExpressionからWhere句(Whereメソッド)を探し出す。そして、最も内側にあったWhere句呼び出しのExpressionを記憶しておき、探索が終わったらそれを返す。
もし、この動作に不満があるなら、人間の手で単一のWhere句に置き換えればよい。人間にやらせるか、または複雑な最適化まで含めて自動的に処理を行わせるか、という選択肢が考えられるが、私ならサンプル通り妥協しても良いかと思う。
#Where句の合成だけなら、AND条件として処理すれば良い。しかし、ネストしたExpressionが
#上記のように単純であるとは限らない。その部分まで担保するのはかなり大変だ。

投稿者:

kekyo

A strawberry red slime mold. Likes metaprogramming. MA. Bicycle rider. http://amzn.to/1SeuUwD