RSS

日別アーカイブ: 2013/12/22

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

広告
 
コメントする

投稿者: : 2013/12/22 投稿先 .NET, LINQ

 
 
%d人のブロガーが「いいね」をつけました。