mcs/class/referencesource/System.Data.Entity/System/Data/Mapping/ViewGeneration/QueryRewriting/RewritingProcessor.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="RewritingProcessor.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner Microsoft
   7 // @backupOwner Microsoft
   8 //---------------------------------------------------------------------
   9
  10 using System;
  11 using System.Diagnostics;
  12 using System.Collections.Generic;
  13 using System.Text;
  14
  15 namespace System.Data.Mapping.ViewGeneration.QueryRewriting
  16 {
  17     internal abstract class TileProcessor<T_Tile>
  18     {
  19         internal abstract bool IsEmpty(T_Tile tile);
  20         internal abstract T_Tile Union(T_Tile a, T_Tile b);
  21         internal abstract T_Tile Join(T_Tile a, T_Tile b);
  22         internal abstract T_Tile AntiSemiJoin(T_Tile a, T_Tile b);
  23
  24         internal abstract T_Tile GetArg1(T_Tile tile);
  25         internal abstract T_Tile GetArg2(T_Tile tile);
  26         internal abstract TileOpKind GetOpKind(T_Tile tile);
  27     }
  28
  29     internal class RewritingProcessor<T_Tile> : TileProcessor<T_Tile> where T_Tile : class
  30     {
  31         public double PERMUTE_FRACTION = 0.0;
  32         public int MIN_PERMUTATIONS = 0;
  33         public int MAX_PERMUTATIONS = 0;
  34         public bool REORDER_VIEWS = false;
  35
  36         private int m_numSATChecks;
  37         private int m_numIntersection;
  38         private int m_numDifference;
  39         private int m_numUnion;
  40
  41         private int m_numErrors;
  42
  43         private TileProcessor<T_Tile> m_tileProcessor;
  44
  45         public RewritingProcessor(TileProcessor<T_Tile> tileProcessor)
  46         {
  47             m_tileProcessor = tileProcessor;
  48         }
  49
  50         internal TileProcessor<T_Tile> TileProcessor
  51         {
  52             get { return m_tileProcessor; }
  53         }
  54
  55         public void GetStatistics(out int numSATChecks, out int numIntersection, out int numUnion, out int numDifference, out int numErrors)
  56         {
  57             numSATChecks = m_numSATChecks;
  58             numIntersection = m_numIntersection;
  59             numUnion = m_numUnion;
  60             numDifference = m_numDifference;
  61             numErrors = m_numErrors;
  62         }
  63
  64         public void PrintStatistics()
  65         {
  66             Console.WriteLine("{0} containment checks, {4} set operations ({1} intersections + {2} unions + {3} differences)",
  67                 m_numSATChecks, m_numIntersection, m_numUnion, m_numDifference,
  68                                 m_numIntersection + m_numUnion + m_numDifference);
  69             Console.WriteLine("{0} errors", m_numErrors);
  70         }
  71
  72         internal override T_Tile GetArg1(T_Tile tile)
  73         {
  74             return m_tileProcessor.GetArg1(tile);
  75         }
  76
  77         internal override T_Tile GetArg2(T_Tile tile)
  78         {
  79             return m_tileProcessor.GetArg2(tile);
  80         }
  81
  82         internal override TileOpKind GetOpKind(T_Tile tile)
  83         {
  84             return m_tileProcessor.GetOpKind(tile);
  85         }
  86
  87         internal override bool IsEmpty(T_Tile a)
  88         {
  89             m_numSATChecks++;
  90             return m_tileProcessor.IsEmpty(a);
  91         }
  92
  93         public bool IsDisjointFrom(T_Tile a, T_Tile b)
  94         {
  95             return m_tileProcessor.IsEmpty(Join(a, b));
  96         }
  97
  98         internal bool IsContainedIn(T_Tile a, T_Tile b)
  99         {
 100             T_Tile difference = AntiSemiJoin(a, b);
 101             return IsEmpty(difference);
 102         }
 103
 104         internal bool IsEquivalentTo(T_Tile a, T_Tile b)
 105         {
 106             bool aInB = IsContainedIn(a, b);
 107             bool bInA = IsContainedIn(b, a);
 108             return aInB && bInA;
 109         }
 110
 111         internal override T_Tile Union(T_Tile a, T_Tile b)
 112         {
 113             m_numUnion++;
 114             return m_tileProcessor.Union(a, b);
 115         }
 116
 117         internal override T_Tile Join(T_Tile a, T_Tile b)
 118         {
 119             if (a == null)
 120             {
 121                 return b;
 122             }
 123             m_numIntersection++;
 124             return m_tileProcessor.Join(a, b);
 125         }
 126
 127         internal override T_Tile AntiSemiJoin(T_Tile a, T_Tile b)
 128         {
 129             m_numDifference++;
 130             return m_tileProcessor.AntiSemiJoin(a, b);
 131         }
 132
 133         public void AddError()
 134         {
 135             m_numErrors++;
 136         }
 137
 138         public int CountOperators(T_Tile query)
 139         {
 140             int count = 0;
 141             if (query != null)
 142             {
 143                 if (GetOpKind(query) != TileOpKind.Named)
 144                 {
 145                     count++;
 146                     count += CountOperators(GetArg1(query));
 147                     count += CountOperators(GetArg2(query));
 148                 }
 149             }
 150             return count;
 151         }
 152
 153         public int CountViews(T_Tile query)
 154         {
 155             HashSet<T_Tile> views = new HashSet<T_Tile>();
 156             GatherViews(query, views);
 157             return views.Count;
 158         }
 159
 160         public void GatherViews(T_Tile rewriting, HashSet<T_Tile> views)
 161         {
 162             if (rewriting != null)
 163             {
 164                 if (GetOpKind(rewriting) == TileOpKind.Named)
 165                 {
 166                     views.Add(rewriting);
 167                 }
 168                 else
 169                 {
 170                     GatherViews(GetArg1(rewriting), views);
 171                     GatherViews(GetArg2(rewriting), views);
 172                 }
 173             }
 174         }
 175
 176         public static IEnumerable<T> AllButOne<T>(IEnumerable<T> list, int toSkipPosition)
 177         {
 178             int valuePosition = 0;
 179             foreach (T value in list)
 180             {
 181                 if (valuePosition++ != toSkipPosition)
 182                 {
 183                     yield return value;
 184                 }
 185             }
 186         }
 187
 188         public static IEnumerable<T> Concat<T>(T value, IEnumerable<T> rest)
 189         {
 190             yield return value;
 191             foreach (T restValue in rest)
 192             {
 193                 yield return restValue;
 194             }
 195         }
 196
 197         public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> list)
 198         {
 199             IEnumerable<T> rest = null;
 200             int valuePosition = 0;
 201             foreach (T value in list)
 202             {
 203                 rest = AllButOne<T>(list, valuePosition++);
 204                 foreach (IEnumerable<T> restPermutation in Permute<T>(rest))
 205                 {
 206                     yield return Concat<T>(value, restPermutation);
 207                 }
 208             }
 209             if (rest == null)
 210             {
 211                 yield return list; // list is empty enumeration
 212             }
 213         }
 214
 215         static Random rnd = new Random(1507);
 216         public static List<T> RandomPermutation<T>(IEnumerable<T> input)
 217         {
 218             List<T> output = new List<T>(input);
 219             for (int i = 0; i < output.Count; i++)
 220             {
 221                 int j = rnd.Next(output.Count);
 222                 T tmp = output[i];
 223                 output[i] = output[j];
 224                 output[j] = tmp;
 225             }
 226             return output;
 227         }
 228
 229         public static IEnumerable<T> Reverse<T>(IEnumerable<T> input, HashSet<T> filter)
 230         {
 231             List<T> output = new List<T>(input);
 232             output.Reverse();
 233             foreach (T t in output)
 234             {
 235                 if (filter.Contains(t))
 236                 {
 237                     yield return t;
 238                 }
 239             }
 240         }
 241
 242         public bool RewriteQuery(T_Tile toFill, T_Tile toAvoid, IEnumerable<T_Tile> views, out T_Tile rewriting)
 243         {
 244             if (RewriteQueryOnce(toFill, toAvoid, views, out rewriting))
 245             {
 246                 HashSet<T_Tile> usedViews = new HashSet<T_Tile>();
 247                 GatherViews(rewriting, usedViews);
 248                 int opCount = CountOperators(rewriting);
 249
 250                 // try several permutations of views, pick one with fewer operators
 251                 T_Tile newRewriting;
 252                 int permuteTries = 0;
 253                 int numPermutations = Math.Min(MAX_PERMUTATIONS, Math.Max(MIN_PERMUTATIONS, (int)(usedViews.Count * PERMUTE_FRACTION)));
 254                 while (permuteTries++ < numPermutations)
 255                 {
 256                     IEnumerable<T_Tile> permutedViews;
 257                     if (permuteTries == 1)
 258                     {
 259                         permutedViews = Reverse(views, usedViews);
 260                     }
 261                     else
 262                     {
 263                         permutedViews = RandomPermutation(usedViews); // Tradeoff: views vs. usedViews!
 264                     }
 265                     bool succeeded = RewriteQueryOnce(toFill, toAvoid, permutedViews, out newRewriting);
 266                     Debug.Assert(succeeded);
 267                     int newOpCount = CountOperators(newRewriting);
 268                     if (newOpCount < opCount)
 269                     {
 270                         opCount = newOpCount;
 271                         rewriting = newRewriting;
 272                     }
 273                     HashSet<T_Tile> newUsedViews = new HashSet<T_Tile>();
 274                     GatherViews(newRewriting, newUsedViews);
 275                     usedViews = newUsedViews; // can only be fewer!
 276                 }
 277                 return true;
 278             }
 279             return false;
 280         }
 281
 282         public bool RewriteQueryOnce(T_Tile toFill, T_Tile toAvoid, IEnumerable<T_Tile> views, out T_Tile rewriting)
 283         {
 284             List<T_Tile> viewList = new List<T_Tile>(views);
 285             return RewritingPass<T_Tile>.RewriteQuery(toFill, toAvoid, out rewriting, viewList, this);
 286         }
 287     }
 288 }