c# - 表达式树依赖分析器

Question

我正在为跨数据源IQueryProvider构建表达式树相关性分析器。

也就是说，我有一个带有一些元素的IQueryable，可以针对任意提供程序(例如Entity Framework)在内存中本地执行这些元素。 IQueryable中的其他一些元素与我需要进行远程WCF调用的实体相抵触。 WCF操作采用序列化的表达式树，将其反序列化，对它自己的本地数据存储执行LINQ查询(也称为Entity Framework)，然后将结果发送给我(尽管这种机制很容易成为WCF数据服务DataServiceQuery ...但是我不使用它，因为它的功能支持级别是有限的(最好)。一旦从WCF服务获得了结果，就将针对本地执行的LINQ查询在内存中执行LINQ查询的结果。

那么，这有什么难呢？好吧，我需要确定表达式树的依赖关系，以便我的本地基础查询提供程序不会爆炸，以执行我的LINQ查询，而该LINQ查询具有只能在远程WCF服务上执行的组件……反之亦然。

让我们来看一个简单的场景:

  var result = 
   (from entityX in new Query<MyEntityX>()
   from entityY in new Query<MyEntityY>()
   where entityX.SomeProperty == "Hello" &&
   entityY.SomeOtherProperty == "Hello 2" && entityX.Id == entityY.XId).ToList();

Query<T>是我自己的提供程序的一个简单的可查询包装器，它有机会在将根换成其他查询提供程序之前解析树以弄清楚该怎么做。因此，在上述情况下，我需要:

使用本地对象上下文对MyEntityA执行查询，并且仅应用myEntityX.SomeProperty == "Hello"条件。即，在本地运行以下命令:
// assume the functionality for replacing new Query<MyEntityA> with new
// ObjectContext<MyEntityA>() is already there...
var resultX = (from entityX in new Query<MyEntityX>()
where entityX.SomeProperty == "Hello").ToList().AsQueryable();

发送以下序列化的序列，并使其在我的远程WCF服务上执行，然后返回结果。
// Send the preceeding expression over the over the wire
// and get the results back (just take my word this already works)
var resultY = (from entityY in new Query<MyEntityY>()
where entityY.SomeOtherProperty == "Hello 2").ToList().AsQueryable();

在内存中执行以下操作:
var finalResult = (from entityX in resultX
from entityY in resultY
where entityX.SomeProperty == "Hello" &&
entityY.SomeOtherProperty == "Hello 2" &&
entityX.Id == entityY.XId).ToList();

请注意，解决方案还必须包含一种累积标准的方式，该标准也是从投影中指定的...

var result = 
(from i in  
  (from entityX in new Query<MyEntityX>()  
   from entityY in new Query<MyEntityY>()  
   select new { PropX = entityX, PropY = entityY })  
where  
   i.PropX.SomeProperty == "Hello" && i.PropY.SomeOtherProperty == "Hello 2"  
   && i.PropX.Id == i.PropY.XId  
select i)  
.ToList();

这将导致在内存中其余部分进行评估之前，实际发出与上面相同的两个单独查询。无关紧要的是，我想我可能会使用PLINQ和/或DRYAD来运行内存操作，从而提高性能。

因此，我有一些想法(例如与访问者在树上进行一些传递，并为给定的实体类型积累候选者)，但是我正在寻找其他人的建议，该建议涉及如何积累表达树中可以包含的部分在给定的上下文中执行...也就是说，知道其中一个条件适用于一个基础新Query<T>，另一个条件适用于另一个不同......，以便我可以弄清楚我可以对数据存储1做些什么可以针对数据存储2和我需要在内存中执行的操作，并相应地执行树的不同部分。有点像Funcletizer，但是有点复杂...

感谢您的协助。

Answer 1

这是一个有趣的问题。我将考虑一种由几个阶段组成的方法:

表达式树的

表达式分析(可能是自下而上的)，并将节点标记为“远程”，“本地”和“中性”

自上而下标识“远程”子表达式

远程查询执行(消除子表达式)

本地查询执行

下面提供了每个阶段的更多详细信息。我的答案末尾的“备注”部分提供了一些需要考虑的重要注意事项。

免责声明:我的回答是示意性的，我确定它不会涉及在表达式树中允许的各个操作的语义方面可能发生的很多方面和情况。我认为，必须做出某些折衷才能使实现过程相当简单。

阶段1:表达分析和标记

表达式树中的每个节点都可以认为属于以下类别:

“远程”节点对应于必须远程执行和的操作；

“本地”节点对应于必须在本地执行的操作；

“中性”节点对应于可以由任何查询处理器执行的操作。

一种自下而上的遍历和处理表达式树的方法似乎适合这种情况。原因是在处理具有子节点Y_1至Y_n的给定节点X时，节点X的类别很大程度上取决于其子节点Y_1至T_n的类别。

让我们重写您提供的示例:

entityX.SomeProperty == "Hello" &&
entityY.SomeOtherProperty == "Hello 2" && 
entityX.Id == entityY.Id

放入相应的表达式树的轮廓中:

&&(&&(==(Member(SomeProperty, Var(entityX)), "Hello"), 
      ==(Member(SomeOtherProperty, Var(entityY)), "Hello 2")),
   ==(Member(Id, Var(entityX)), Member(Id, Var(entityY)))

然后，该表达式树将被标记为自下而上。 R表示“远程”，L表示“本地”，N表示“中性”。如果entityX是远程的，而entityY是本地的，则结果将如下所示:

L:&&(L:&&(R:==(R:Member(SomeProperty, R:Var(entityX)), N:"Hello"), 
          L:==(L:Member(SomeOtherProperty, L:Var(entityY)), N:"Hello 2")),
     L:==(R:Member(Id, R:Var(entityX)), L:Member(Id, L:Var(entityY)))

如您所见，对于每个运算符(operator)，分析仪都必须根据其子节点的类别来确定类别。在上面的示例中:

对对象进行属性访问将产生与对象相同的类别。

字符串文字将是中性的；

本地和远程子表达式的相等性比较将具有本地类别；

和and运算符将再次偏爱本地而不是远程。

但是，您可以考虑将自下而上的方法与自上而下的优化过程结合使用，以获得更好的结果。考虑以下(符号):R == R + L。您要如何执行相等性比较？使用纯自下而上的方法，您可以在本地执行它。但是，在某些情况下，最好在本地预先计算L，用实际值(即中性)替换子表达式，然后远程执行相等比较。换句话说，您可以最终实现查询计划优化器。

阶段2:识别远程子表达式

在下一阶段，将对标记的表达式树进行自顶向下的处理，并将每个标记为remote的子表达式从树中删除，并征集为远程数据集中每个项目进行远程评估的表达式集。

从上面可以明显看出，某些远程子表达式将封装本地子表达式。因此，本地子表达式可能包含远程子表达式。仅中性节点应代表与类别术语同质的子表达式。

因此，可能有必要通过多次往返远程查询处理器来执行给定查询。一种替代方法是允许查询处理器之间进行双向通信，以便“远程”处理器可以标识“本地”(实际上从其角度来看实际上是“远程”)子表达式并回调“本地”处理器执行它。

阶段3:远程查询执行

在第三阶段，远程子表达式列表将发送到“远程”查询处理器以执行。 (另请参见上一阶段的讨论。)

问题还在于，如何识别可用于有效限制远程查询处理器返回的结果数据集的子表达式。为此，必须考虑表达式树中顶级运算符的语义(通常是&&和||)。对&&和||进行短路评估会使事情变得有些复杂，因为查询预处理器可能不会对操作数进行重新排序。

阶段4:本地查询执行

执行所有远程子表达式后，它们在原始表达式树中的出现将被收集的结果替换。

评论

您可能最终有必要限制“远程”子树中只允许某些操作以降低处理复杂性—这将是在功能和实现查询预处理器所花费的时间之间的权衡。

要处理数据别名(例如在您提供的PropX = entityX … i.PropX.SomeProperty == "Hello"示例中)，您将必须执行数据流分析。在这里，您很可能会遇到一系列复杂的案例，值得处理。