kekyoの丼

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である」「比較演算子を使用し、右辺（または左辺）が同じ型のリテラル」であれば、式自体を最適化可能であろうことが見えてくる。あとはどこまで実行するかということだ。

SQL文に変換可能かどうかを、もう少し見てみる。以下のやや複雑なLINQクエリは変換できるだろうか？

using (var context = new AdventureWorksLT2012_DataEntities())
{
    // カスタマーとカスタマー住所を内部結合し、カスタマー住所が"Shipping"のものを抽出
    var customer =
        from customer in context.Customer
        join customerAddress in context.CustomerAddress on
            customer.CustomerID equals customerAddress.CustomerID
        where customerAddress.AddressType == "Shipping"
        select new
        {
            Customer = customer,
            CustomerAddress = customerAddress
        };

    Debug.WriteLine(customer.ToString());
}

このLINQクエリはもちろん成功し、以下のように変換される。

SELECT
    [Extent1].[CustomerID] AS [CustomerID],
    [Extent1].[NameStyle] AS [NameStyle],
    [Extent1].[Title] AS [Title],
    [Extent1].[FirstName] AS [FirstName],
    [Extent1].[MiddleName] AS [MiddleName],
    [Extent1].[LastName] AS [LastName],
    [Extent1].[Suffix] AS [Suffix],
    [Extent1].[CompanyName] AS [CompanyName],
    [Extent1].[SalesPerson] AS [SalesPerson],
    [Extent1].[EmailAddress] AS [EmailAddress],
    [Extent1].[Phone] AS [Phone],
    [Extent1].[PasswordHash] AS [PasswordHash],
    [Extent1].[PasswordSalt] AS [PasswordSalt],
    [Extent1].[rowguid] AS [rowguid],
    [Extent1].[ModifiedDate] AS [ModifiedDate],
    [Extent2].[CustomerID] AS [CustomerID1],
    [Extent2].[AddressID] AS [AddressID],
    [Extent2].[AddressType] AS [AddressType],
    [Extent2].[rowguid] AS [rowguid1],
    [Extent2].[ModifiedDate] AS [ModifiedDate1]
FROM  [SalesLT].[Customer] AS [Extent1]
INNER JOIN [SalesLT].[CustomerAddress] AS [Extent2] ON
    [Extent1].[CustomerID] = [Extent2].[CustomerID]
WHERE N'Shipping' = [Extent2].[AddressType]

完璧に意図通りだ。しかも、匿名クラスへの射影の概念は.NET CLR固有のものだが、SELECT句でカラムに別名を適用して全て吸い上げている。SQL文には表れないが、結果が返された時点で匿名クラスのそれぞれのプロパティに格納されるのだろう。
LINQクエリのjoinは、内部結合に該当する。残念ながら左・右結合、外部結合に対応する予約語は存在しない。これは同時に、LINQ to Objectsでのjoinにも、そのような演算が無いことを意味する。
但し、そもそも左・右結合は、RDBが「表形式」でしか結果を表現できないために存在するものだと分かれば、大した問題ではない。これらの結合は、対応する値が存在しない場合でも、結果表中の該当するカラムに何らかの値を置く必要があり（そうしないと「表」にならない）、仕方がないので「NULL」を返すのだ。
しかし、LINQの世界は表形式だけではなく、（XMLのように）構造化された要素を自在に扱う事が出来る。だから、そこに結果が存在しな場合はNULLで表現しなくても、はじめから存在しない状態を作り出せる。

using (var context = new AdventureWorksLT2012_DataEntities())
{
    // 製品情報をカテゴリー別に集約する
    var productsByProductCategory =
        from product in context.Product
        group product by product.ProductCategoryID;

    Debug.WriteLine(productsByProductCategory.ToString());
}

LINQクエリの「group ～ by」は、名称からSQL分のGROUP BY句を彷彿とさせる。実際、レコード結果をセレクタに従って集約するという点では、GROUP BY句と同じように動作する。
LINQ to Objectsであれば、IGrouping<T, U>インターフェイスの列挙子が返される。このインターフェイスは、IDictionary<T, U>が構造化されたような形をしている。つまり、一つのキー値（T）に対して、n個の要素値（IEnumerable<U>）が格納される。
IDictionaryが「表形式」と考えるなら、IGrouping（IGroupingの列挙子）は「構造化形式」だ。
ただ、得られるSQL文は分かりにくい。

SELECT
    [Project2].[C1] AS [C1],
    [Project2].[ProductCategoryID] AS [ProductCategoryID],
    [Project2].[C2] AS [C2],
    [Project2].[ProductID] AS [ProductID],
    [Project2].[Name] AS [Name],
    [Project2].[ProductNumber] AS [ProductNumber],
    [Project2].[Color] AS [Color],
    [Project2].[StandardCost] AS [StandardCost],
    [Project2].[ListPrice] AS [ListPrice],
    [Project2].[Size] AS [Size],
    [Project2].[Weight] AS [Weight],
    [Project2].[ProductCategoryID1] AS [ProductCategoryID1],
    [Project2].[ProductModelID] AS [ProductModelID],
    [Project2].[SellStartDate] AS [SellStartDate],
    [Project2].[SellEndDate] AS [SellEndDate],
    [Project2].[DiscontinuedDate] AS [DiscontinuedDate],
    [Project2].[ThumbNailPhoto] AS [ThumbNailPhoto],
    [Project2].[ThumbnailPhotoFileName] AS [ThumbnailPhotoFileName],
    [Project2].[rowguid] AS [rowguid],
    [Project2].[ModifiedDate] AS [ModifiedDate]
FROM ( SELECT
    [Distinct1].[ProductCategoryID] AS [ProductCategoryID],
    1 AS [C1],
    [Extent2].[ProductID] AS [ProductID],
    [Extent2].[Name] AS [Name],
    [Extent2].[ProductNumber] AS [ProductNumber],
    [Extent2].[Color] AS [Color],
    [Extent2].[StandardCost] AS [StandardCost],
    [Extent2].[ListPrice] AS [ListPrice],
    [Extent2].[Size] AS [Size],
    [Extent2].[Weight] AS [Weight],
    [Extent2].[ProductCategoryID] AS [ProductCategoryID1],
    [Extent2].[ProductModelID] AS [ProductModelID],
    [Extent2].[SellStartDate] AS [SellStartDate],
    [Extent2].[SellEndDate] AS [SellEndDate],
    [Extent2].[DiscontinuedDate] AS [DiscontinuedDate],
    [Extent2].[ThumbNailPhoto] AS [ThumbNailPhoto],
    [Extent2].[ThumbnailPhotoFileName] AS [ThumbnailPhotoFileName],
    [Extent2].[rowguid] AS [rowguid],
    [Extent2].[ModifiedDate] AS [ModifiedDate],
    CASE WHEN ([Extent2].[ProductID] IS NULL) THEN CAST(NULL AS int) ELSE 1 END AS [C2]
    FROM   (SELECT DISTINCT
        [Extent1].[ProductCategoryID] AS [ProductCategoryID]
        FROM [SalesLT].[Product] AS [Extent1] ) AS [Distinct1]
    LEFT OUTER JOIN [SalesLT].[Product] AS [Extent2] ON
        ([Distinct1].[ProductCategoryID] = [Extent2].[ProductCategoryID]) OR
        (([Distinct1].[ProductCategoryID] IS NULL) AND ([Extent2].[ProductCategoryID] IS NULL))
    )  AS [Project2]
ORDER BY [Project2].[ProductCategoryID] ASC, [Project2].[C2] ASC

サブクエリバリバリな、読みにくいSQL文が出力された。

1. ProductCategoryIDをDISTINCTしたリストを作る（一番内側のクエリ）
   つまり、カテゴリーIDの重複のないリストを作る。
2. 次に、そのリストを使って左結合でCustomerAddressを抽出する（LEFT OUTER JOINのクエリ）
   ここでC1とC2という付加情報を加えている。C1は1固定なので用途が分からないが、C2はカテゴリーに該当するレコードが存在したかどうかを表しているように見える。
3. 最後に、結合結果をカテゴリーIDとC2でソートする。

このようなSQL文となる理由はあまり思いつかず、はっきりとした理由は不明だ。最終的にカテゴリーID毎に集約しなければならないため、カテゴリーIDでソートするのは理に適っているように思える（逆シリアル化してインスタンスに格納するときに、ソートされていれば順序実行すれば良くなる。件数が莫大かもしれないため、返却後にインメモリでソートしない方が良いだろう）。
何れにしても、このSQL文はLINQ to Entitiesのバージョンが上がる時に変更される可能性があるので深入りしないが、重要なのは、RDBとのやりとりはどうしても「表形式」とするしかないが、結果が戻ってきたら、「構造化形式」に集約出来ると言う事だ。構造化されていれば、結合結果としてカラムチェックに頼らなければならないような、書きにくいコードから解放される。

using (var context = new AdventureWorksLT2012_DataEntities())
{
    // 製品情報をカテゴリー別に集約する
    var productsByProductCategory =
        from product in context.Product
        group product by product.ProductCategoryID;

    // カテゴリー別に製品情報を出力する
    foreach (var categorizedProducts in productsByProductCategory)
    {
        Console.WriteLine("CategoryID: {0}", categorizedProducts.Key);
        foreach (var product in categorizedProducts)
        {
            Console.WriteLine("   Product: {0}, {1}, {2}",
                product.ProductNumber,
                product.Name,
                product.ListPrice);
        }
    }
}

もちろん、LINQクエリなので、パイプライン実行される。SQL Server上ではORDER BYが実行されるので一時リソースを消費するが、.NET側では結果のレコード群が逐次処理される。最終出力はConsoleに出しているだけなので、結果が何千万行あってもメモリは圧迫されない。
今まで苦労してきた開発手法は一体何だったのか、と思わずにはいられないかもしれない。集約の簡便さもさることながら、コードを一瞥しただけで処理内容が把握できるため、保守も容易だ。このコードにはforeach以外に制御構文が存在しない。サイクロマティック複雑度は十分に小さい。それはつまり、テストに掛かるコストも小さいと言う事だ。
最後に、結果をXMLに変換するのに、制御構造が不要である例を示そう。

using (var context = new AdventureWorksLT2012_DataEntities())
{
    // 製品情報をカテゴリー別に集約する
    var productsByProductCategory =
        from product in context.Product
        group product by product.ProductCategoryID;

    // カテゴリー別に製品情報をXMLで出力する
    var categoriesXml = new XElement("Categories",
        from categorizedProducts in productsByProductCategory.AsEnumerable()   // <-- ゲート
        select new XElement(
            "Category",
            new XAttribute("id", categorizedProducts.Key),
            from product in categorizedProducts
            select new XElement("Product",
                new XAttribute("name", product.Name),
                new XAttribute("number", product.ProductNumber),
                new XAttribute("price", product.ListPrice))));

    Debug.WriteLine(categoriesXml);
}

「AsEnumerable」でLINQ to EntitiesとLINQ to XMLの間にゲートを作っていることに注意。これがないと、LINQ to XMLのクエリがLINQ to Entitiesの一部とみなされ、SQL文に変換しようとして失敗する。
このコードのユニットテストの想像が付くだろうか？ 従来の制御構文によるロジックバリバリのコードのユニットテストと異なり、このコードのテストは純粋なインターフェイス境界のテストとして非常に設計しやすいはずだ。この事を知っていれば、機能設計の段階から設計方針が異なってくる。
（但し、ユニットテストとして成立させるためには、DataContextを分離する必要がある事に注意。このままではデータベースが存在しないとテスト出来ないので良くない）。

前回、LINQ to SQLまたはLINQ to Entitiesは、どんなラムダ式でもSQLに変換できるわけではない事を示した。では、どのような式なら変換できるのだろうか？
例えば、stringクラスにはStartsWithメソッドがある。これを使って：

using (var context = new AdventureWorksLT2012_DataEntities())
{
    // Johnで始まる苗字のレコードを抽出
    var customer0 =
        from customer in context.Customer
        where customer.LastName.StartsWith("John")
        select customer;

    Debug.WriteLine(customer0.ToString());
}

実行すると、エラーとはならない。そして以下のSQL文が出力される。

SELECT
    [Extent1].[CustomerID] AS [CustomerID],
    [Extent1].[NameStyle] AS [NameStyle],
    [Extent1].[Title] AS [Title],
    [Extent1].[FirstName] AS [FirstName],
    [Extent1].[MiddleName] AS [MiddleName],
    [Extent1].[LastName] AS [LastName],
    [Extent1].[Suffix] AS [Suffix],
    [Extent1].[CompanyName] AS [CompanyName],
    [Extent1].[SalesPerson] AS [SalesPerson],
    [Extent1].[EmailAddress] AS [EmailAddress],
    [Extent1].[Phone] AS [Phone],
    [Extent1].[PasswordHash] AS [PasswordHash],
    [Extent1].[PasswordSalt] AS [PasswordSalt],
    [Extent1].[rowguid] AS [rowguid],
    [Extent1].[ModifiedDate] AS [ModifiedDate]
FROM [SalesLT].[Customer] AS [Extent1]
WHERE [Extent1].[LastName] LIKE N'John%'

SQL文にはStartsWithメソッドなど存在しない。だからエラーになるかと思いきや、LIKE句に置き換わって、結果として意図通りの抽出が実行されるSQL文が組み立てられた。
これは明らかに、string.StartsWithメソッドを認識し、等価なLIKE句に置き換えていることが伺える。つまり、与えられたExpressionを解析し、その式の中にStartsWithメソッドの呼び出しが含まれていれば、LIKE句を組み立ててSQL文に追加する、と言う事をしているのだろうと予想できる。それならば、EndsWithも同じようにLIKE句に置き換えられるはずだ。実際に試して確認してほしい。
なお、以下のような式を記述すると、生成されるSQL文も変化する。

using (var context = new AdventureWorksLT2012_DataEntities())
{
    // Johnで始まる苗字のレコードを抽出
    var customer1 =
        from customer in context.Customer
        where customer.LastName.StartsWith("John") == true   // <-- 明示的にtrueで判定
        select customer;

    Debug.WriteLine(customer1.ToString());
}

生成されるSQL文はこうだ：

SELECT
    [Extent1].[CustomerID] AS [CustomerID],
    [Extent1].[NameStyle] AS [NameStyle],
    [Extent1].[Title] AS [Title],
    [Extent1].[FirstName] AS [FirstName],
    [Extent1].[MiddleName] AS [MiddleName],
    [Extent1].[LastName] AS [LastName],
    [Extent1].[Suffix] AS [Suffix],
    [Extent1].[CompanyName] AS [CompanyName],
    [Extent1].[SalesPerson] AS [SalesPerson],
    [Extent1].[EmailAddress] AS [EmailAddress],
    [Extent1].[Phone] AS [Phone],
    [Extent1].[PasswordHash] AS [PasswordHash],
    [Extent1].[PasswordSalt] AS [PasswordSalt],
    [Extent1].[rowguid] AS [rowguid],
    [Extent1].[ModifiedDate] AS [ModifiedDate]
FROM [SalesLT].[Customer] AS [Extent1]
WHERE (1 = (CASE WHEN ([Extent1].[LastName] LIKE N'John%') THEN cast(1 as bit) WHEN ( NOT ([Extent1].[LastName] LIKE N'John%')) THEN cast(0 as bit) END)) AND (CASE WHEN ([Extent1].[LastName] LIKE N'John%') THEN cast(1 as bit) WHEN ( NOT ([Extent1].[LastName] LIKE N'John%')) THEN cast(0 as bit) END IS NOT NULL)

かなりのクソ真面目ぶりだ。SQL Serverのクエリオプティマイザーがこの式をどう評価するか分からないが、LINQクエリを記述する際は、それがどのようなSQL文として実行されるのかは気にかけておいた方が良い。書き方一つでこれだけ変わってしまうのは、人によってはLINQクエリで書く事に抵抗を感じるかもしれない。しかし、長い目で見れば、新しい.NET FrameworkではExpressionの評価次第でシンプルなクエリに変換されるようになるかもしれないし、タイプセーフである事は変わらない。
他にも特別に解釈され、SQL文にマッピングされるLINQ拡張メソッド群が存在する。Sum, Count, Average, Min, Maxといった集計を行うメソッドは、対応するSQL文に変換可能だ。また、Skip, Takeメソッドを使って、抽出結果の部分レコード抽出も可能だ。これらはOFFSET句とFETCH句に変換される。