カテゴリー: .NET

前回のLocationFinderクラスによって、検索条件となる文字列の一覧が得られた。この検索条件をTerraServer WCFインターフェイスを使用して、サービスに送信する。すると、結果レコードがPlaceクラスに入れられて返される。結果が複数のレコードとなる可能性があり、WCFメソッドの戻り値はPlaceの配列で定義されている。

とうとう結果が得られたのだ。これをそのまま返せばよい。が、しかし、今まで扱ってきたのは、あくまでIQueryableによるLINQクエリだ。IEnumerableならそのまま返せばよい（配列はIEnumerableを実装しているので）が、少なくともIQueryableでなければならない。
であれば話は簡単だ。配列をAsQueryableすれば良い。

// Get the place name(s) to query the Web service with.
LocationFinder lf = new LocationFinder(lambdaExpression.Body);
List<string> locations = lf.Locations;
if (locations.Count == 0)
    throw new InvalidQueryException("You must specify at least one place name in your query.");
// Call the Web service and get the results.
Place[] places = WebServiceHelper.GetPlacesFromTerraServer(locations);
// Copy the IEnumerable places to an IQueryable.
IQueryable<Place> queryablePlaces = places.AsQueryable<Place>();

結果のIQueryableは、もはやTerraServer LINQプロバイダーの手を離れ、LINQ to ObjectsのLINQプロバイダーが処理を行うようになる。

まだ終わりではない

最初にInnerMostWhereFinderクラスで、最も内側のWhereを探索した事を覚えているだろうか？ いま、一息ついたところだが、ここまでの処理で実現したのは、その「最も内側のWhere条件」だ。その外側のLINQクエリは放置されている。これを処理しなければならない。
しかし、前述のようにもうTerraServerは関係ないため、配列をAsQueryableした結果を使って続きのクエリを実行させる必要がある。これを行わせるのが、「ExpressionTreeModifier」クラスだ。このクラスもExpressionVisitorを継承している。やっていることは単純だ。TerraServerのコンテキストクラスのインスタンスを、上記配列をAsQueryableしたものに挿げ替える。
生成されたExpressionは、もはやTerraServerコンテキストを含まない。かつ、サービスから得られた結果を配列で含んでいるため、Expressionツリー全体がLINQ to Objectsで評価可能な状態にある。CreateQueryを呼び出してIQueryableを生成すれば、そのインスタンスはLINQ to ObjectsのLINQプロバイダーが管理する。
こうして、LINQ to TerraServerが完成した。

とうとう、LINQプロバイダーの中心部へと来た。今までIQueryableが収集したExpressionを探索したり変形したりしたが、結局まだ検索条件の解析をしていなかった。ここで「LocationFinder」クラスを使用して、検索条件の解析を行う。名前からはピンと来ないが、このクラスが中心的存在だ。

このクラスは例によってExpressionVisitorクラスを継承しており、前述のInnerMostWhereFinderクラスとEvaluatorクラスによって得られたExpressionを探索する。
TerraServerサービスから返される結果は、「Place」クラスに格納される。Placeクラスはエンティティクラスであり、「Name」プロパティと「State」プロパティを持つ。TerraServerのサービスは、任意の場所を示す文字列を与えることで、その場所に応じたレコード群が返される。そこで、Placeクラスのプロパティにアクセスする式を書けば、それが検索条件として反映されるようにすればよい。

// コンテキストを生成
var terraPlaces = new QueryableTerraServerData<Place>();
// コンテキストに検索条件を与え、TerraServerサービスにクエリを発行し、結果を取得する
var query =
    from place in terraPlaces
    where place.Name == "Johannesburg"
    select place;

上記の例は、Nameプロパティが”Johannesburg”と一致するかどうかを確認している。同様に、

// Stateで検索
var query =
    from place in terraPlaces
    where place.State == "Kentucky"
    select place;

でも検索できるようにする。

BinaryExpressionの解析

上記のクエリ構文をメソッド構文、かつ拡張メソッドではない構文に直すと、以下のようになる。

// 拡張メソッドではないメソッド構文
var query =
    Queryable.Where(
        terraPlaces,
        place => place.Name == "Johannesburg");

これらとExpressionがどのように対応するかを示したのが、以下の図だ。

さて、ここで注意点がある。比較演算子の場合、右辺と左辺は入れ替えることが可能だ。つまり、

// コンテキストに検索条件を与え、TerraServerサービスにクエリを発行し、結果を取得する
var query =
    from place in terraPlaces
    where "Johannesburg" == place.Name    // 右辺と左辺が逆
    select place;

のようなクエリを記述しても、これを許容しなければならない。BinaryExpressionクラスには「Right」と「Left」プロパティがあり、演算子の右辺と左辺のExpressionに対応している。従って、これらに設定されているExpressionが逆であっても、正しく識別しなければならない。
サンプルコード中では「ExpressionTreeHelpers」クラスの「IsMemberEqualsValueExpression」メソッドや「GetValueFromEqualsExpression」メソッドが該当する。逆に定義されていても問題がないように実装されている事が分かる。
まとめると：

1. 二項演算子(BinaryExpression)であり、
2. 二項の片方がPlace.Name、又はPlace.Stateプロパティであり、
3. もう片方が固定値（Constant）

であれば、この固定値が検索したい値と言う事になる。LocationFinderクラスはこのような探索を行い、用意しておいたリストに加える。
全てのExpressionノードを探索すれば、リストに検索条件となる値群が抽出されていることになる。

IQueryableで表現されるクエリに、事前評価可能な式が含まれることがある。

using (var context = new AdventureWorksLT2012_DataEntities())
{
    // 検索条件を変数で与える
    var selectType = "Shipping";
    var addresses =
        from customerAddress in context.CustomerAddress
        where customerAddress.AddressType == selectType
        select customerAddress;

}

上記のselectTypeは、LINQクエリ中の条件式に与えられる。これはメソッド構文で言う所のラムダ式に変換されるため、このローカル変数は暗黙のクロージャーのメンバーフィールドとして定義される。この式のExpressionをダンプすると、以下の結果が得られる。

<Call value="value(System.Data.Entity.Core.Objects.ObjectQuery1[ShowQueryInLinqToEntities.CustomerAddress]).MergeAs(AppendOnly).Where(customerAddress =&gt; (customerAddress.AddressType == value(ShowQueryInLinqToEntities.Program+&lt;&gt;c__DisplayClassd).selectType))">
    <Null />
    <Call value="value(System.Data.Entity.Core.Objects.ObjectQuery1[ShowQueryInLinqToEntities.CustomerAddress]).MergeAs(AppendOnly)">
        <Constant value="value(System.Data.Entity.Core.Objects.ObjectQuery`1[ShowQueryInLinqToEntities.CustomerAddress])" />
        <Constant value="AppendOnly" />
    </Call>
    <Lambda value="customerAddress => (customerAddress.AddressType == value(ShowQueryInLinqToEntities.Program+<>c__DisplayClassd).selectType)">
        <Equal value="(customerAddress.AddressType == value(ShowQueryInLinqToEntities.Program+<>c__DisplayClassd).selectType)">
            <MemberAccess value="customerAddress.AddressType">
                <Parameter value="customerAddress" />
            </MemberAccess>
            <MemberAccess value="value(ShowQueryInLinqToEntities.Program+<>c__DisplayClassd).selectType">
                <Constant value="value(ShowQueryInLinqToEntities.Program+<>c__DisplayClassd)" />
            </MemberAccess>
        </Equal>
        <Parameter value="customerAddress" />
    </Lambda>
</Call>

少々長い（そして、ノード毎の出力がいい加減なので醜い）が、Equalノード下に二つのMemberAccessノードがあり、片方はcustomerAddress.AddressTypeを示している。と言う事は、もう片方のConstantノードが、クロージャーのメンバーフィールドを示していると言えそうだ。
このLINQクエリは、例によって「人類の英知」を使えば、以下のように単純化できる。

using (var context = new AdventureWorksLT2012_DataEntities())
{
    // 検索条件をクエリの式中に直接埋め込む
    var addresses =
        from customerAddress in context.CustomerAddress
        where customerAddress.AddressType == "Shipping"
        select customerAddress;
}

こうすると：

<Call value="value(System.Data.Entity.Core.Objects.ObjectQuery1[ShowQueryInLinqToEntities.CustomerAddress]).MergeAs(AppendOnly).Where(customerAddress =&gt; (customerAddress.AddressType == &quot;Shipping&quot;))">
    <Null />
    <Call value="value(System.Data.Entity.Core.Objects.ObjectQuery1[ShowQueryInLinqToEntities.CustomerAddress]).MergeAs(AppendOnly)">
        <Constant value="value(System.Data.Entity.Core.Objects.ObjectQuery`1[ShowQueryInLinqToEntities.CustomerAddress])" />
        <Constant value="AppendOnly" />
    </Call>
    <Lambda value="customerAddress => (customerAddress.AddressType == "Shipping")">
        <Equal value="(customerAddress.AddressType == "Shipping")">
            <MemberAccess value="customerAddress.AddressType">
                <Parameter value="customerAddress" />
            </MemberAccess>
            <Constant value=""Shipping"" />
        </Equal>
        <Parameter value="customerAddress" />
    </Lambda>
</Call>

Equalノード配下の二つ目のノードが、MemberAccessから直接的なConstantの文字列に置き換わっている。
さて、最適化の概要を見たが、このような事が出来れば良い事は分かるが、実際必要なのだろうか？ 今回の最適化作業は前回と異なり、「行わなければならない」最適化となる。もしこれを実行しないと、LINQプロバイダーがExpressionを処理する際に、「customerAddress.AddressType == selectType」という式をサービス側に解釈可能な形で変換しなければならない。selectTypeはクロージャーのメンバーフィールドだ。サービスはこのクロージャーのメンバーフィールドに「リモート」から直接アクセス出来るだろうか？
もちろん、出来る訳がない。出来ないとしたら、取りうる手段は以下の二つだ。

• クエリのエラーとする。
  但し、エラーとしてしまうと、クエリを非常に簡潔に書かなくてはならないという制約が生じる。上記のような、ちょっとした（ローカル変数への参照）式でさえ、NGとなってしまう。これは厳しい制約だ。
• 事前にこのフィールドを解釈し、サービスに提供出来る検索条件にする。
  もし、注目している式がConstantな値（固定値）に変換出来るのであれば、あらかじめ変換してしまえば良い。上記の例のように、ローカル変数への参照（クロージャーのメンバーフィールドへの参照）を事前に解釈して、単なる「Shipping」文字列に出来てしまえば、サービス側に送ることが可能となる。

そういったわけで、Constantに事前変換可能な式を見つけ出して、変換する事が必要となる。この操作を行うのは、「Evaluator」クラスだ。このクラスは内部に「Nominator」クラスと「SubtreeEvaluator」クラスを含む。どちらもExpressionVisitorクラスを継承していて、Expressionの探索を行う。

最初のステップ (Nominator)

「Nominator」クラスは、Expressionを探索して、Expressionノードの末端(Leaf)から逆順で、Constantに変換可能かを見る。変換可能かどうかは、そのExpressionノードが「Parameter」かどうかで判断する。Parameterでなければ変換可能とみるが、ノードのチェインのどこかにParameterノードが存在すれば、そのノードより上(Root側)のノードは、全て変換不可とみなされる。
Parameterノードが含まれているツリーの枝は、何らかのメソッド呼び出しを実行しないと、結果が得られない可能性がある。しかし、LINQクエリ中にメソッド呼び出しが記述されていると言う事は、単にサービスの向うの機能を仮想的に表現したものであるかもしれない。そうであれば、ローカル環境で実行しても無意味となるので、実行してConstantに変換する事は出来ない。
このような判断を下しつつ、変換可能なExpressionノードをHashSetに収集する。
＃上の図では、変換不可とみなされたノードにチェックを付けている。
＃また、HashSetに収集されるExpressionを、〇で囲った。

変換のステップ (SubtreeEvaluator)

Nominatorで収集したExpression群は変換可能候補のリストであるので、SubtreeEvaluatorクラスの探索でこのリストをチェックし、該当するノードを見つけたらそのノード以下をConstantに変換する。既にConstantであるExpressionやnullのExpressionは無視する。
変換方法は簡単だ。まず、そのExpressionをラムダ式に変換する（Expression.Lambdaメソッドを使う）。次に、そのLambdaExpressionをコンパイルし、出来上がったデリゲートをコールする。すると、実際に式が実行されて、式の評価結果が固定値として返って来る。あとは、Expression.Constantメソッドで、Expressionに変換すれば完了だ。
ExpressionVisitorは、探索だけではなく、Expressionツリーの変更もサポートする。本来、Expressionはイミュータブル（変更出来ないクラス・例えばSystem.Stringのような）なので変更出来ないが、Visitメソッドの戻り値として新しいExpressionを返すことで、Expressionのツリーを変更（サブツリーの置き換え）する事が出来る。
探索だけ行う場合は、元のExpressionを返せば、式の変形は行われない。なので、Expression.Constantで新しいExpressionを作ったら、単にそれを返却すればよい。これで注目している式をConstantに置き換える事が出来た。

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が
＃上記のように単純であるとは限らない。その部分まで担保するのはかなり大変だ。

IQueryableには、何らかのLINQプロバイダーが関連付けられている。AsQueryableを使用してIQueryableに変換したクエリは、以下のように「EnumerableQuery<T>」というLINQプロバイダーが割り当てられている。

IQueryableインターフェイスとLINQプロバイダーの関係や、プロバイダーの作成方法については、チュートリアル : IQueryable LINQ プロバイダの作成にまとまっている。やや難解であるので、読み合わせ的に補足していこうと思う。

想定しているシナリオ

「TerraServer-USA Web Services」というサービスが存在したとして（実際あるようだが、何故か応答が返ってこない）、そのウェブサービスに対してクエリを発行し、結果を取得出来る。何もない状態では、WCFで定義されたインターフェイスに従って、メソッド呼び出しのような形式でサービスを利用するが、このサービスに対応するLINQプロバイダを書けば、LINQクエリの記述でサービスを利用する事が可能になる。つまり、既存のWCFインターフェイスを使用して、「LINQ to TerraServer」を作ると言う事になる。

全体的な構造

LINQクエリを記述する側は、IEnumerableやIQueryableといったインターフェイスにだけ注目する。LINQプロバイダーを作る場合（そして、LINQ to SQLやLINQ to Entities）は、IQueryableインターフェイスを実装した独自のクラスを用意する。と同時に、LINQプロバイダーとなる「IQueryProvider」インターフェイスを実装したクラスも用意する。このクラスが、LINQクエリーのExpressionを解釈し、SQL文を生成したりする。今回はWCFを使用して、TerraServerのサービスにアクセスする。

また、LINQクエリの記述を成立させるには、結果を格納するエンティティとなるクラスが必要だ。例えば、

using (var context = new AdventureWorksLT2012_DataEntities())
{
    // CustomerAddressエンティティクラスが受け皿となるクエリ
    IQueryable<CustomerAddress> persons =
        from customerAddress in context.CustomerAddress
        where customerAddress.AddressType == "Shipping"
        select customerAddress;
}

このようなクエリが（RDBやWCFを通じてサーバーで）実行され、結果が返される。その結果をこのクラス（CustomerAddress）に格納する。そのため、クラスの定義が必要となる。
もう一つ、LINQ to SQLやLINQ to Entitiesでは、「コンテキスト」と呼ばれるRDBへの接続を管理するクラスも必要だ。これがないと、LINQソースとなる端点（上記の例であれば、context.CustomerAddress）が提供出来ないので、クエリが書けない。但し、別の方法もある。普通の列挙子をAsQueryableでIQueryableに変換した場合は、コンテキストとなるクラスは存在しない。つまり、何らかの方法で、LINQソースとなる端点が提供できれば良いと言う事だ。

IEnumerableとIQueryableの相互変換は可能だ。その意味について考えてみる。

var r = new Random();
// 1: IEnumerable<int>をIQueryable<int>に変換する
IEnumerable<int> randomDatas =
    from index in Enumerable.Range(0, 100000)
    select r.Next();
IQueryable<int> queryableIntDatas = randomDatas.AsQueryable();
// 2: IQueryable<Customer>をIEnumerable<Customer>に変換する
using (var context = new AdventureWorksLT2012_DataEntities())
{
    IQueryable<Customer> queryableCustomers =
        from customer in context.Customer
        select customer;
    IEnumerable<Customer> enumerableCustomer = queryableCustomer.AsEnumerable();
    // IEnumerable<Customer> enumerableCustomer = (IEnumerable<Customer>)queryableCustomer;
}

先に2番目の変換を見てみる。
IQueryable<T>は、IEnumerable<T>を継承している。そのため、2番目の変換は、単にキャストするのと変わらない（AsEnumerableの実装はキャストしているだけだ）。
IEnumerable<T>にキャストしてforeach等で列挙した場合、IQueryable<T>の実装が持つGetEnumerator()を呼び出していることになる。これは擬似的に、以下のようなコードだ。

// queryableの列挙子を取得する擬似コード
public static IEnumerable<T> PseudoAsEnumerable<T>(this IQueryable<T> queryable)
{
    // queryableで示されるクエリを実行し、結果群が返される（GetEnumeratorの呼び出し）
    foreach (var value in queryable)
    {
        yield return value;
    }
}

queryableは普通の列挙子ではない。LINQ to SQLやLINQ to Entitiesで示される、何らかのストレージとのインターフェイスを抽象化したものだ。そのため、このforeachによって何が引き起こされるのかは、queryableが何を対象にしているのかによって異なる。LINQ to SQLやLINQ to Entitiesでは、RDBに対してSQL文が発行され、結果が返って来るだろう。そのレコード群がforeachで列挙される。

では1番目の変換はどうだろう。
randomDatasはLINQ to Objectsのクエリ式だ。IQueryableで表現するためには、このクエリ全体が「記述的」になる必要がある。つまり、randomDatasクエリ式を「呼び出す式」がIQueryableで表現される。
IQueryableがGetEnumeratorによって列挙される時、randomDatasクエリ式を解釈する「LINQプロバイダー」が動作し、プロバイダーがrandomDatasクエリ式を列挙する。
当然ながら、この例ではRDBにアクセスするわけではないので、queryableIntDatasは「SQL文」を表している訳ではない。以下はデバッガのスナップショットだ。

IQueryableインターフェイスには、「Expression」プロパティが存在する。このプロパティは、例の「Expression」だ。IQueryableが表現するクエリ式全体が、このExpressionプロパティから公開される。そこで、このExpressionがどうなっているのか、Expressionの探索で示したFlatDumpExpressionVisitorを使ってXMLにダンプすると、以下のような単一のノードが返される。

<Constant value="System.Linq.Enumerable+WhereSelectEnumerableIterator`2[System.Int32,System.Int32]" />

結局、IQueryableが指す参照先は、IEnumerableのベールに包まれたrandomDatasであり、固定値（Constant）として認識されている。同じIQueryableを基礎としているのに、これは明らかにLINQ to SQLやLINQ to Entitiesとは異なる。
この違いは、LINQソースから生まれる。LINQ to Entitiesの例では、AdventureWorksLT2012_DataEntitiesクラスのCustomerプロパティからクエリを開始している。AsQueryableは、LINQ to Objectsのクエリを変換する。この違いによって、IQueryableの評価を受け持つ「LINQプロバイダー」が異なり、SQL文に変換されたり、列挙子の呼び出しに変換されたりする。

Expressionを取得するには、ラムダ式から生成するのが簡単だ。他にExpressionクラスに定義されている静的メソッドを使用して生成する事もできる。どちらにしても、LINQ to Objectsで使ってきたデリゲート（Func<T, U>）と異なり、Expressionを実行する事は出来ない。あくまでExpressionVisitorを使うなどして、式の構造を解析できるだけだ。しかし、ラムダ式に対応するLambdaExpressionは、「コンパイル」が可能だ。

// Expressionを生成
Expression<Func<bool>> func12 = () => "ABCDEFG".StartsWith("ABC") == true;
// Expressionをコンパイルし、デリゲートを生成
var func12Compiled = func12.Compile();
// 実行する
var result = func12Compiled();

「コンパイル」とは、実際にコンパイルされることだ。コンパイルされたデリゲートを使えば、任意の式を高速に実行出来る。便利そうであるが、実は複雑な問題が絡んでいる。Expressionを生成した際にあまり意識していないと思うが、Expressionのノードには「クロージャ」が含まれる場合がある。これは、ラムダ式を使うときには自然な概念として理解されていると思う。

public static Func<string> CreateClosure()
{
    // 暗黙のクロージャ（デリゲートを返す）
    var localVariable = 123;
    return () => localVariable.ToString();
}

localVariableはCreateClosureメソッドのローカル変数だ。常識的には、ローカル変数の内容は、メソッドを抜ける時に破棄される。上のコードではローカル変数を参照する「デリゲート」が、メソッドから返される。メソッドから返されたデリゲートは、果たして安全に実行できるだろうか？
C言語でローカル変数へのポインタを返してバグを招いたことは無いだろうか？しかし、上記のコードは問題なく動作する。localVariableが定数だから問題ないのだろうか？仮に定数ではなくても、このコードは正しく動作する。何故か？コンパイル時に生成される「クロージャクラス」のメンバフィールドが、localVariableに対応するように、コードが変更されてコンパイルされるからだ。
以下はこれを概念的に示したものだ。

// 不可視でコンパイラが自動的に生成するクロージャクラス
internal sealed class TemporaryClosureClass
{
    public int localVariable;
    public string Execute()
    {
        return localVariable.ToString();
    }
}
public static Func<string> CreateClosure()
{
    // 暗黙のクロージャ（デリゲートを返す）
    var closure = new TemporaryClosureClass();
    closure.localVariable = 123;
    return closure.Execute;
}

CreateClosureが返すデリゲートには、暗黙にTemporaryClosureClassクラスのインスタンスへの参照が含まれる。そのため、このインスタンスがGCに回収されることはなく、CreateClosureを抜けてからでも、問題なく実行する事が出来る。
では、デリゲートではなくExpressionならどうだろうか？

public static Expression<Func<string>> CreateClosure()
{
    // 暗黙のクロージャ（Expression）
    var closure = new TemporaryClosureClass();
    closure.localVariable = 123;
    return closure.Execute;     // <-- 構文エラー
}

残念ながら、「closure.Execute」はラムダ式ではないので、このコードはコンパイルして検証出来ない。しかし、式がMethodCallExpressionであるとして想像すると、次のようになるはずだ。

• Method: TemporaryClosureClassクラスのExecuteメソッドを示す。
• Arguments: Executeの引数（引数なしなので、空の配列）。
• Object: closure変数への参照、つまりTemporaryClosureClassクラスのインスタンス。

このExpressionを前回のXML出力に掛けた場合、正しくXMLに変換できるだろうか？問題があるとすれば、Objectプロパティ、つまり、TemporaryClosureClassのインスタンスをどうやってXMLに変換するかだ。このようなクラスは、当然ToStringの明示的な実装を行っていない。そのため、残念ながら可読可能な状態での変換は望めないことになる。
そして、Expressionは暗黙的に、何らかのインスタンスに対しての参照を内包している可能性があることになる。そのため、Expressionを「コンパイル」出来たとしても、参照を内包している限りそれはその場限りでしか使えず、再利用して高速化するのは難しい。もし、再利用したい場合は、クロージャや外部インスタンスへの参照を暗黙に含まないように、注意してExpressionを組み立てる必要がある。

Expressionは、代入されたラムダ式の構造によっていくらでも変化する。そのため、例で見せたように、あらかじめどの種類のExpressionがやってくるかを予想する事は難しい。そういった構造を解析する方法はいくつか考えられる。単に一つ一つの構造をswitch文のような分岐で処理する事もできるが、標準的な方法として「ExpressionVisitor」クラスが用意されている。
ExpressionVisitorクラスは、Visitorパターンを使用してExpressionを解析する。例えばMethodCallExpressionは、インスタンスを示す「Object」、対象のメンバを示す「Method」、引数群を示す「Arguments」が存在するが、これらもまたExpressionであるので、再帰的に呼び出される。このクラスを継承して、関心のある種類のExpressionのメソッドをオーバーライドしてチェックできる。
特に再帰の入り口となるのが「Visit」メソッドだ。このメソッドの基底の実装が、細分化された「Visit～」メソッドをコールする。試しにVisitをオーバーライドしたのが、以下の例だ。

// ExpressionVisitorクラスを継承する
public sealed class FlatDumpExpressionVisitor : ExpressionVisitor
{
    public FlatDumpExpressionVisitor()
    {
    }

    // 再起処理の入り口となるメソッド
    public override Expression Visit(Expression node)
    {
        // 引数で渡されたExpressionをダンプする
        Debug.WriteLine("{0}: {1}", node.NodeType, node.ToString());
        // デフォルトの実装を呼び出す（細分化されたVisitメソッドを呼び分け、再帰処理する）
        return base.Visit(node);
    }
}

これを実行すると、以下のような出力が得られる。

// ダンプ対象の式を定義
Expression<Func<bool>> func12 = () => "ABCDEFG".StartsWith("ABC") == true;
// ダンプを実行
var visitor = new FlatDumpExpressionVisitor();
visitor.Visit(func12);
// Lambda: () => ("ABCDEFG".StartsWith("ABC") == True)
// Equal: ("ABCDEFG".StartsWith("ABC") == True)
// Call: "ABCDEFG".StartsWith("ABC")
// Constant: "ABCDEFG"
// Constant: "ABC"
// Constant: True

ツリーの階層構造は明確ではないが、ラムダ式から始まって、式の細部を探索していることが読み取れる。また、このFlatDumpExpressionVisitorによって、すべての式の要素がダンプされていそうだ。式中に与えたStartsWithの呼び出しや、固定的な文字列、右辺の「true」も列挙されている。
もう少し、何とかしたい。そこで、以下のようなコードを書いてみる。

public sealed class FlatDumpExpressionVisitor : ExpressionVisitor
{
    private readonly Stack<XElement> elementStack_ = new Stack<XElement>();
    public FlatDumpExpressionVisitor()
    {
    }
    public XElement CurrentElement
    {
        get;
        private set;
    }
    public override Expression Visit(Expression node)
    {
        elementStack_.Push(this.CurrentElement);
        var element = new XElement(node.NodeType.ToString());
        element.Add(new XAttribute("value", node.ToString()));
        if (this.CurrentElement != null)
        {
            this.CurrentElement.Add(element);
        }
        this.CurrentElement = element;
        var result = base.Visit(node);
        this.CurrentElement = elementStack_.Pop() ?? this.CurrentElement;
        return result;
    }
}

これは、再帰的にVisitが呼び出されたときに、XElementを使って階層構造を組み立てるExpressionVisitorの実装だ。まだ式の出力（value属性）が読みにくいが、どのような階層構造になっているのかは把握できる。

<Lambda value="() =&gt; (&quot;ABCDEFG&quot;.StartsWith(&quot;ABC&quot;) == True)">
    <Equal value="(&quot;ABCDEFG&quot;.StartsWith(&quot;ABC&quot;) == True)">
        <Call value="&quot;ABCDEFG&quot;.StartsWith(&quot;ABC&quot;)">
            <Constant value="&quot;ABCDEFG&quot;" />
            <Constant value="&quot;ABC&quot;" />
        </Call>
        <Constant value="True" />
    </Equal>
</Lambda>

ExpressionVisitorクラスには、「VisitBinary」のような細分化されたメソッドが用意されている。これらのノード別メソッドはかなりの種類があるため、すべてを細かく制御するのは骨が折れる。だが、正しく制御すれば、Expressionをより良いXML形式に変換できるだろう。

ラムダ式をExpressionとして評価するとき、ほんの些細な記述の違いも、Expressionの中には忠実に再現される。string.StartsWithをSQL文に変換する際に、StartsWithの戻り値を明示的に判定する式を書いた。すると、明らかに異なるSQL文が生成された。たとえ意味的に同じ式であっても、Expressionでは異なる表現とみなされる。
以下に、明示的な判定を行わない式のExpressionを確認するコードを示す。

// StartsWithの戻り値をそのまま返す
Expression<Func<bool>> func11 = () => "ABCDEFG".StartsWith("ABC");

// 1.ラムダ式である
var lambdaExpression11 = (LambdaExpression)func11;

// 2.ラムダ式の本体はメソッド呼び出しである
var methodCallExpression11 = (MethodCallExpression)lambdaExpression11.Body;

// 3.メソッド名はStartsWithである
var methodInfo11 = methodCallExpression11.Method;
Debug.Assert(methodInfo11.Name == "StartsWith");

// 4.メソッド呼び出しのインスタンスはリテラル文字列"ABCDEFG"である
var instance11 = (ConstantExpression)methodCallExpression11.Object;
Debug.Assert(instance11.Value.Equals("ABCDEFG"));

// 5.メソッド呼び出しの引数は1個存在する
var arguments11 = methodCallExpression11.Arguments;
Debug.Assert(arguments11.Count == 1);

// 6.その引数の式はリテラル文字列で"ABC"である
var argument011 = (ConstantExpression)arguments11[0];
Debug.Assert(argument011.Value.Equals("ABC"));

ラムダ式からExpressionを得た場合、Expressionは「LambdaExpression」クラスで表現される。このクラスにはラムダ式本体を示す「Body」というプロパティがあり、これがまたExpressionを示している。上では示さなかったが、ReturnTypeやParameters（ラムダ式の引数群）を示すプロパティが定義されている。
次にBodyの中身だが、記述したラムダ式の本体は、string.StartsWithメソッドの呼び出しになっている。なので、Bodyは「MethodCallExpression」クラスで表現されている。対象のメソッドを示す「Method」を見ると、リフレクションのMethodInfoが返される。ここからメソッド名（Name）が”StartsWith”である事が分かる。
string.StartsWithはインスタンスメソッドであるので、「Object」を参照するとインスタンスを特定するExpressionが得られる。この例では”ABCDEFG”というリテラル文字列から直接メソッド呼び出ししているので、「ConstantExpression」にキャストし、「Value」プロパティを確認する事でこの文字列が得られる。
メソッドの引数は「Arguments」で、コレクションが返される。これらの一つ一つの要素もまたExpressionであるので、目的の具象クラスにキャストする必要がある。今回は引数がリテラル文字列であることが分かっているので、「ConstantExpression」にキャストして「Value」にアクセスすると、引数に指定した”ABC”が得られる。
では、明示的に判定を行う式の場合はどうなるだろうか？

// StartsWithの戻り値に、明示的な判定式を記述した場合
Expression<Func<bool>> func12 = () => "ABCDEFG".StartsWith("ABC") == true;

// 1.ラムダ式である
var lambdaExpression12 = (LambdaExpression)func12;

// 2.ラムダ式の本体は二項演算子である
var binaryExpression12 = (BinaryExpression)lambdaExpression12.Body;

// 3.二項演算子の種類はイコールである
Debug.Assert(binaryExpression12.NodeType == ExpressionType.Equal);

// 4.二項演算子の右側はboolリテラル値でtrueである
var rightExpression12 = (ConstantExpression)binaryExpression12.Right;
Debug.Assert(rightExpression12.Value.Equals(true));

// 5.二項演算子の左側はメソッド呼び出しで、メソッド名はStartsWithである
var leftExpression12 = (MethodCallExpression)binaryExpression12.Left;
Debug.Assert(leftExpression12.Method.Name == "StartsWith");

StartsWithの中身は同じなので省略する。つまり、ラムダ式に記述した通りの構造がExpressionに再現される。無意味だからと言って、特に省略されたりすることはない。そして、LINQ to Entitiesではこの違いが、あのようなSQL文の違いとなって表れたと思われる。
同時に、ここまで解析できれば、「メソッド呼び出しの戻り値がboolである」「比較演算子を使用し、右辺（または左辺）が同じ型のリテラル」であれば、式自体を最適化可能であろうことが見えてくる。あとはどこまで実行するかということだ。