詳盡搜索/生成表達式樹的每個組合

Question

我正在玩一個基本的表達式樹優化器來構建查詢計劃。在解析樹時，我可以根據我可以分配給每個操作的權重來決定如何構建它。

如果我有一個簡單的樹，有2個關於如何執行動作的選擇，我希望能夠生成樹的兩個變體，然後可以比較每個的權重以查看哪些是最高效。

例如，下面的代碼會允許我來構建表達式樹的兩個變化加入操作：一個帶有MergeJoinExpression，一個具有NestedLoopJoinExpression

class Customer 
{ 
     public int Id { get; set; } 
} 
class Orders 
{ 
     public int Id { get; set; } 
     public int CustomerId { get; set; } 
} 

class MergeJoinExpresion : JoinExpression 
{ 
} 

class NestLoopJoinExpresion : JoinExpression 
{ 
} 

class Visitor : ExpressionVisitor 
{ 
    public List<Expression> GetPlans(Expression expr) 
    { 
     // ??? 
    } 

    override VisitJoin(JoinExpression join) 
    { 
     // For this join, I can return the following (trite example) 
     // return MergeJoinExpresion 
     // return NestLoopJoinExpresion 

     return base.VisitJoin(join); 
    } 
} 

我如何構建，將產生每個方法樹的變種並將它們還給我？

class Program 
{ 
     static void Main(string[] args) 
     { 
      var query = from c in customers 
         join o in orders on c.Id equals o.CustomerId 
         select new 
         { 
          CustomerId = c.Id, 
          OrderId = o.Id 
         }; 


      var plans = new Visitor().GetPlans(query); 
     } 
} 

誰能告訴我怎樣才能修改VisitorGetPlans類的方法來產生這些變化？

編輯 - 是這樣的：

class Visitor : ExpressionVisitor 
{ 
    private List<Expression> exprs = new List<Expression>(); 

    public List<Expression> GetPlans(Expression expr) 
    { 
     Visit(expr);  
     return exprs; 
    } 

    override VisitJoin(JoinExpression join) 
    { 
     // For this join, I can return the following (trite example) 
     // return MergeJoinExpresion 
     // return NestLoopJoinExpresion  
     var choices = new Expression[] { MergeJoinExpresion.Create(join), NestLoopJoinExpresion.Create(join) }; 

     foreach(var choice in choices) 
     { 
      var cloned = Cloner.Clone(choice); 
      var newTree = base.VisitJoin(cloned); 
      exprs.Add(newTree); 
     } 

     return base.VisitJoin(join); 
    } 
} 

Answer 1

所以下手，我們將創建一個訪問者，這將只是幫助我們從一個Expression提取JoinExpression對象的列表：

internal class FindJoinsVisitor : ExpressionVisitor 
{ 
    private List<JoinExpression> expressions = new List<JoinExpression>(); 
    protected override Expression VisitJoin(JoinExpression join) 
    { 
     expressions.Add(join); 
     return base.VisitJoin(join); 
    } 
    public IEnumerable<JoinExpression> JoinExpressions 
    { 
     get 
     { 
      return expressions; 
     } 
    } 
} 
public static IEnumerable<JoinExpression> FindJoins(
    this Expression expression) 
{ 
    var visitor = new FindJoinsVisitor(); 
    visitor.Visit(expression); 
    return visitor.JoinExpressions; 
} 

下一步，我們將使用下面的方法，從this blog post拍攝，以獲得序列的序列的笛卡爾乘積：

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    this IEnumerable<IEnumerable<T>> sequences) 
{ 
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
    return sequences.Aggregate( 
     emptyProduct, 
     (accumulator, sequence) => 
      from accseq in accumulator 
      from item in sequence 
      select accseq.Concat(new[] {item})); 
} 

接下來，我們將創建一個訪問者是需要表達對的序列，並替換第一個表達式的所有實例對與第二：

internal class ReplaceVisitor : ExpressionVisitor 
{ 
    private readonly Dictionary<Expression, Expression> lookup; 
    public ReplaceVisitor(Dictionary<Expression, Expression> pairsToReplace) 
    { 
     lookup = pairsToReplace; 
    } 
    public override Expression Visit(Expression node) 
    { 
     if(lookup.ContainsKey(node)) 
      return base.Visit(lookup[node]); 
     else 
      return base.Visit(node); 
    } 
} 

public static Expression ReplaceAll(this Expression expression, 
    Dictionary<Expression, Expression> pairsToReplace) 
{ 
    return new ReplaceVisitor(pairsToReplace).Visit(expression); 
} 

public static Expression ReplaceAll(this Expression expression, 
    IEnumerable<Tuple<Expression, Expression>> pairsToReplace) 
{ 
    var lookup = pairsToReplace.ToDictionary(pair => pair.Item1, pair => pair.Item2); 
    return new ReplaceVisitor(lookup).Visit(expression); 
} 

最後，我們通過尋找所有在我們表達了加入表情把一切融合在一起，項目的出來對的序列，其中的JoinExpression是在對中的第一項，第二是每一個可能的替代值。從那裏我們可以得到它的笛卡爾乘積以獲得表達式替換對的所有組合。最後，我們可以將每個組合的替換投影到實際替換原始表達式中所有這些對的表達式中：

public static IEnumerable<Expression> AllJoinCombinations(Expression expression) 
{ 
    var combinations = expression.FindJoins() 
     .Select(join => new Tuple<Expression, Expression>[] 
     { 
      Tuple.Create<Expression, Expression>(join, new NestLoopJoinExpresion(join)), 
      Tuple.Create<Expression, Expression>(join, new MergeJoinExpresion(join)), 
     }) 
     .CartesianProduct(); 

    return combinations.Select(combination => expression.ReplaceAll(combination)); 
} 

Answer 2

你需要一成不變的樹木肯定。

創建一個類：

class JoinOptionsExpression: JoinExpression { 
    public IEnumerable<JoinExpression> Options {get; private set;} 
    private JoinOptionsExpression(){} 
    public static JoinOptionsExpression Create(IEnumerable<JoinExpression> options){ 
     return new JoinOptionsExpression{Options = options.ToList().AsReadOnly()}; // you can improve this probably 
    } 
} 

然後在您的VisitJoin方法返回的選項，並返回所有的選擇：

private List<Dictionary<JoinOptionsExpression,int>> selections = new List<Dictionary<JoinOptionsExpression,int>>{new Dictionary<JoinOptionsExpression,int>()}; 
override VisitJoin(JoinExpression join) 
{ 
    var choices = new Expression[] { MergeJoinExpresion.Create(join), NestLoopJoinExpresion.Create(join) }; 
    List<Expression> exprs = new List<Expression>(); 
    foreach(var choice in choices) 
    { 
     var cloned = Cloner.Clone(choice); 
     var newTree = base.VisitJoin(cloned); 
     exprs.Add(newTree); 
    } 
    var result = JoinOptionsExpression.Create(exprs); 
    // now add all choices 
    if (exprs.Count > 0) 
     foreach (selection in selections.ToList()) // to make sure your don't modify during enumeration, you can improve this too 
     { 
      selection.Add(result, 0); 
      for (i=1; i<exprs.Count; i++) 
      { 
       var copy= new Dictionary<JoinOptionsExpression, int>(selection); 
       copy[result] = i; 
       selections.Add(copy); 
      } 
     } 
    return result; 
} 

然後你需要一個第二訪問者，從框架遊客派生，並且沒有其他原因，只是提取您的選項：

class OptionsExtractor:ExpressionVisitor 
{ 
    public IEnumerable<Expression> Extract(Expression expression, List<Dictionary<JoinOptionsExpression,int>> selections) 
    { 
     foreach(var selection in selections) 
     { 
      currentSelections = selection; 
      yield return Visit(expression); 
     } 
    } 
    private Dictionary<JoinOptionsExpression,int> currentSelections; 
    override Expression Visit(Expression node) 
    { 
     var opts = node as JoinOptionsExpression; 
     if (opts != null) 
      return base.Visit(opts.Options.ElementAt(currentSelections[opts]); 
     else 
      return base.Visit(node); 
    } 
} 

反正一個詳盡的搜索可以迅速爆炸在你的臉上，我想你知道這一點。 聲明：我只是在這個編輯器中輸入了它，它甚至不會編譯，但你應該能夠明白。