表达式树依赖性分析器

Question

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

也就是说，我有一个 IQueryable，其中包含一些元素，可以针对某个任意提供程序（例如实体框架）在内存中本地执行。 IQueryable 中的一些其他元素与我需要进行远程 WCF 调用的实体相冲突。 WCF 操作采用序列化表达式树，将其反序列化，针对其自己的本地数据存储（也可以说实体框架）执行 LINQ 查询，然后将结果发回给我（尽管此机制可以很容易地成为 WCF 数据服务） DataServiceQuery...但我没有使用它，因为它的功能支持水平是有限的...充其量）。一旦我从 WCF 服务返回结果，我将根据本地执行的 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 是一个简单的可查询包装器，带有我自己的提供程序，它有机会解析树并弄清楚在使用不同的查询提供程序交换根之前要做什么。因此，在上述情况下，我需要：

1. 使用本地对象上下文对 MyEntityA 执行查询，并仅应用 myEntityX.SomeProperty == "Hello" 标准。也就是说，在本地运行以下命令：

   // 假定替换新 Query的功能与新
// ObjectContext() 已经存在...
var resultX =（来自新查询中的entityX（）
其中entityX.SomeProperty == "Hello").ToList().AsQueryable();

2. 发送以下序列化内容并让它在我的远程WCF服务上执行，然后返回结果。

   // 通过线路发送前面的表达式
// 并获取结果（相信我的话，这已经有效了）
变量结果Y = （来自 new Query() 中的实体Y
其中entityY.SomeOtherProperty == "Hello 2").ToList().AsQueryable();

3. 在内存中执行以下内容：

   var 最终结果 = （来自 resultX 中的实体X
来自结果Y中的实体Y
其中entityX.SomeProperty == "Hello" &&
entityY.SomeOtherProperty ==“你好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 而另一个条件适用于另一个条件...这样我就可以弄清楚什么我可以对数据存储 1 执行操作、对数据存储 2 执行操作以及需要在内存中执行操作，并相应地执行树的不同部分。它有点像 Funcletizer，但更复杂一点......

感谢您的帮助。

Answer 1

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

1. 表达式树的表达式分析（可能是自下而上）以及将节点标记为“远程”、“本地”和“中性”
2. 自上而下识别“远程”子表达式
3. 远程查询执行（子表达式消除）
4. 本地查询执行

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

免责声明：我的回答相当示意性，我确信它没有涵盖与表达式树中允许的各个操作的语义相关的许多方面和情况。我认为必须做出某些妥协才能使实施变得相当简单。

阶段 1：表达式分析和标记

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

• “远程”节点对应于必须远程执行的操作；
• “本地”节点对应于必须在本地执行的操作；
• “中性”节点对应于可以由任何查询处理器执行的操作。

用于遍历和处理表达式树的自下而上的方法似乎适合这种情况。原因是当处理给定节点X时，具有子节点Y_1至Y_n，节点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)))

如您所见，对于每个运算符，您的分析器必须根据其类别来决定类别它的子节点。在上面的例子中：

• 对一个对象进行属性访问将产生与该对象相同的类别；
• 字符串文字将是中性的；
• 本地和远程子表达式的相等比较将具有本地类别；
• 和 操作员将再次青睐本地而不是远程。

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

第 2 阶段：识别远程子表达式

在下一阶段，将自上而下处理标记的表达式树，并将每个标记为远程的子表达式从树中取出，并列入为远程数据中的每个项目远程评估的表达式组中放。

从上面可以清楚地看出，某些远程子表达式将封装本地子表达式。因此，本地子表达式可能包含远程子表达式。只有中性节点才应表示在类别方面同质的子表达式。

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

第 3 阶段：远程查询执行

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

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

第 4 阶段：本地查询执行

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

备注

• 您最终可能需要限制“远程”子树中仅允许某些操作，以降低处理复杂性 - 这将是实现查询预处理器所花费的功能和时间之间的权衡。< /p>

• 要处理数据别名（如您提供的 PropX =entityX … i.PropX.SomeProperty == "Hello" 示例中的情况），您必须执行数据流分析。在这里，您很可能会遇到一组过于复杂而不值得处理的情况。