mcs/class/referencesource/System.Data.Entity/System/Data/Query/PlanCompiler/Predicate.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="Predicate.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.Collections.Generic;
  12 //using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
  13
  14 // It is fine to use Debug.Assert in cases where you assert an obvious thing that is supposed
  15 // to prevent from simple mistakes during development (e.g. method argument validation
  16 // in cases where it was you who created the variables or the variables had already been validated or
  17 // in "else" clauses where due to code changes (e.g. adding a new value to an enum type) the default
  18 // "else" block is chosen why the new condition should be treated separately). This kind of asserts are
  19 // (can be) helpful when developing new code to avoid simple mistakes but have no or little value in
  20 // the shipped product.
  21 // PlanCompiler.Assert *MUST* be used to verify conditions in the trees. These would be assumptions
  22 // about how the tree was built etc. - in these cases we probably want to throw an exception (this is
  23 // what PlanCompiler.Assert does when the condition is not met) if either the assumption is not correct
  24 // or the tree was built/rewritten not the way we thought it was.
  25 // Use your judgment - if you rather remove an assert than ship it use Debug.Assert otherwise use
  26 // PlanCompiler.Assert.
  27
  28 using System.Globalization;
  29
  30 using System.Data.Query.InternalTrees;
  31
  32 namespace System.Data.Query.PlanCompiler
  33 {
  34     /// <summary>
  35     /// The Predicate class represents a condition (predicate) in CNF.
  36     /// A predicate consists of a number of "simple" parts, and the parts are considered to be
  37     /// ANDed together
  38     ///
  39     /// This class provides a number of useful functions related to
  40     ///   - Single Table predicates
  41     ///   - Join predicates
  42     ///   - Key preservation
  43     ///   - Null preservation
  44     /// etc.
  45     ///
  46     /// Note: This class doesn't really convert node trees into CNF form. It looks for
  47     /// basic CNF patterns, and reasons about them. For example,
  48     ///    (a AND b) OR c
  49     /// can technically be translated into (a OR c) AND (b OR c),
  50     /// but we don't bother.
  51     /// At some future point of time, it might be appropriate to consider this
  52     ///
  53     /// </summary>
  54     internal class Predicate
  55     {
  56         #region private state
  57         private Command m_command;
  58         private List<Node> m_parts;
  59         #endregion
  60
  61         #region constructors
  62         /// <summary>
  63         /// Create an empty predicate
  64         /// </summary>
  65         /// <param name="command"></param>
  66         internal Predicate(Command command)
  67         {
  68             m_command = command;
  69             m_parts = new List<Node>();
  70         }
  71
  72         /// <summary>
  73         /// Create a predicate from a node tree
  74         /// </summary>
  75         /// <param name="command">current iqt command</param>
  76         /// <param name="andTree">the node tree</param>
  77         internal Predicate(Command command, Node andTree)
  78             : this(command)
  79         {
  80             PlanCompiler.Assert(andTree != null, "null node passed to Predicate() constructor");
  81             InitFromAndTree(andTree);
  82         }
  83         #endregion
  84
  85         #region public surface
  86
  87         #region construction APIs
  88         /// <summary>
  89         /// Add a new "part" (simple predicate) to the current list of predicate parts
  90         /// </summary>
  91         /// <param name="n">simple predicate</param>
  92         internal void AddPart(Node n)
  93         {
  94             m_parts.Add(n);
  95         }
  96         #endregion
  97
  98         #region Reconstruction (of node tree)
  99         /// <summary>
 100         /// Build up an AND tree based on the current parts.
 101         /// Specifically, if I have parts (p1, p2, ..., pn), we build up a tree that looks like
 102         ///    p1 AND p2 AND ... AND pn
 103         ///
 104         /// If we have no parts, we return a null reference
 105         /// If we have only one part, then we return just that part
 106         /// </summary>
 107         /// <returns>the and subtree</returns>
 108         internal Node BuildAndTree()
 109         {
 110             Node andNode = null;
 111             foreach (Node n in m_parts)
 112             {
 113                 if (andNode == null)
 114                 {
 115                     andNode = n;
 116                 }
 117                 else
 118                 {
 119                     andNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.And),
 120                         andNode, n);
 121                 }
 122             }
 123             return andNode;
 124         }
 125         #endregion
 126
 127         #region SingleTable (Filter) Predicates
 128
 129         /// <summary>
 130         /// Partition the current predicate into predicates that only apply
 131         /// to the specified table (single-table-predicates), and others
 132         /// </summary>
 133         /// <param name="tableDefinitions">current columns defined by the table</param>
 134         /// <param name="otherPredicates">non-single-table predicates</param>
 135         /// <returns>single-table-predicates</returns>
 136         internal Predicate GetSingleTablePredicates(VarVec tableDefinitions,
 137             out Predicate otherPredicates)
 138         {
 139             List<VarVec> tableDefinitionList = new List<VarVec>();
 140             tableDefinitionList.Add(tableDefinitions);
 141             List<Predicate> singleTablePredicateList;
 142             GetSingleTablePredicates(tableDefinitionList, out singleTablePredicateList, out otherPredicates);
 143             return singleTablePredicateList[0];
 144         }
 145         #endregion
 146
 147         #region EquiJoins
 148         /// <summary>
 149         /// Get the set of equi-join columns from this predicate
 150         /// </summary>
 151         /// <param name="leftTableDefinitions"></param>
 152         /// <param name="rightTableDefinitions"></param>
 153         /// <param name="leftTableEquiJoinColumns"></param>
 154         /// <param name="rightTableEquiJoinColumns"></param>
 155         /// <param name="otherPredicates"></param>
 156         internal void GetEquiJoinPredicates(VarVec leftTableDefinitions, VarVec rightTableDefinitions,
 157             out List<Var> leftTableEquiJoinColumns, out List<Var> rightTableEquiJoinColumns,
 158             out Predicate otherPredicates)
 159         {
 160             otherPredicates = new Predicate(m_command);
 161             leftTableEquiJoinColumns = new List<Var>();
 162             rightTableEquiJoinColumns = new List<Var>();
 163             foreach (Node part in m_parts)
 164             {
 165                 Var leftTableVar;
 166                 Var rightTableVar;
 167
 168                 if (IsEquiJoinPredicate(part, leftTableDefinitions, rightTableDefinitions, out leftTableVar, out rightTableVar))
 169                 {
 170                     leftTableEquiJoinColumns.Add(leftTableVar);
 171                     rightTableEquiJoinColumns.Add(rightTableVar);
 172                 }
 173                 else
 174                 {
 175                     otherPredicates.AddPart(part);
 176                 }
 177             }
 178         }
 179
 180         internal Predicate GetJoinPredicates(VarVec leftTableDefinitions, VarVec rightTableDefinitions,
 181             out Predicate otherPredicates)
 182         {
 183             Predicate joinPredicate = new Predicate(m_command);
 184             otherPredicates = new Predicate(m_command);
 185
 186             foreach (Node part in m_parts)
 187             {
 188                 Var leftTableVar;
 189                 Var rightTableVar;
 190
 191                 if (Predicate.IsEquiJoinPredicate(part, leftTableDefinitions, rightTableDefinitions, out leftTableVar, out rightTableVar))
 192                 {
 193                     joinPredicate.AddPart(part);
 194                 }
 195                 else
 196                 {
 197                     otherPredicates.AddPart(part);
 198                 }
 199             }
 200             return joinPredicate;
 201         }
 202         #endregion
 203
 204         #region Keys
 205         /// <summary>
 206         /// Is the current predicate a "key-satisfying" predicate?
 207         /// </summary>
 208         /// <param name="keyVars">list of keyVars</param>
 209         /// <param name="definitions">current table definitions</param>
 210         /// <returns>true, if this predicate satisfies the keys</returns>
 211         internal bool SatisfiesKey(VarVec keyVars, VarVec definitions)
 212         {
 213             if (keyVars.Count > 0)
 214             {
 215                 VarVec missingKeys = keyVars.Clone();
 216                 foreach (Node part in m_parts)
 217                 {
 218                     if (part.Op.OpType != OpType.EQ)
 219                     {
 220                         continue;
 221                     }
 222                     Var keyVar;
 223                     if (IsKeyPredicate(part.Child0, part.Child1, keyVars, definitions, out keyVar))
 224                     {
 225                         missingKeys.Clear(keyVar);
 226                     }
 227                     else if (IsKeyPredicate(part.Child1, part.Child0, keyVars, definitions, out keyVar))
 228                     {
 229                         missingKeys.Clear(keyVar);
 230                     }
 231                 }
 232
 233                 return missingKeys.IsEmpty;
 234             }
 235             return false;
 236         }
 237         #endregion
 238
 239         #region Nulls
 240         /// <summary>
 241         /// Does this predicate preserve nulls for the table columns?
 242         ///
 243         /// If the ansiNullSemantics parameter is set, then we simply return true
 244         /// always - this shuts off most optimizations
 245         ///
 246         /// </summary>
 247         /// <param name="tableColumns">list of columns to consider</param>
 248         /// <param name="ansiNullSemantics">use ansi null semantics</param>
 249         /// <returns>true, if the predicate preserves nulls</returns>
 250         internal bool PreservesNulls(VarVec tableColumns, bool ansiNullSemantics)
 251         {
 252             // Don't mess with non-ansi semantics
 253             if (!ansiNullSemantics)
 254             {
 255                 return true;
 256             }
 257
 258             // If at least one part does not preserve nulls, then we simply return false
 259             foreach (Node part in m_parts)
 260             {
 261                 if (!PreservesNulls(part, tableColumns))
 262                 {
 263                     return false;
 264                 }
 265             }
 266             return true;
 267         }
 268         #endregion
 269
 270         #endregion
 271
 272         #region private methods
 273         #region construction
 274         private void InitFromAndTree(Node andTree)
 275         {
 276             if (andTree.Op.OpType == OpType.And)
 277             {
 278                 InitFromAndTree(andTree.Child0);
 279                 InitFromAndTree(andTree.Child1);
 280             }
 281             else
 282             {
 283                 m_parts.Add(andTree);
 284             }
 285         }
 286         #endregion
 287
 288         #region Single Table Predicates
 289
 290         private void GetSingleTablePredicates(List<VarVec> tableDefinitions,
 291             out List<Predicate> singleTablePredicates, out Predicate otherPredicates)
 292         {
 293             singleTablePredicates = new List<Predicate>();
 294             foreach (VarVec vec in tableDefinitions)
 295             {
 296                 singleTablePredicates.Add(new Predicate(m_command));
 297             }
 298             otherPredicates = new Predicate(m_command);
 299             VarVec externalRefs = m_command.CreateVarVec();
 300
 301             foreach (Node part in m_parts)
 302             {
 303                 NodeInfo nodeInfo = m_command.GetNodeInfo(part);
 304
 305                 bool singleTablePart = false;
 306                 for (int i = 0; i < tableDefinitions.Count; i++)
 307                 {
 308                     VarVec tableColumns = tableDefinitions[i];
 309                     if (tableColumns != null)
 310                     {
 311                         externalRefs.InitFrom(nodeInfo.ExternalReferences);
 312                         externalRefs.Minus(tableColumns);
 313                         if (externalRefs.IsEmpty)
 314                         {
 315                             singleTablePart = true;
 316                             singleTablePredicates[i].AddPart(part);
 317                             break;
 318                         }
 319                     }
 320                 }
 321                 if (!singleTablePart)
 322                 {
 323                     otherPredicates.AddPart(part);
 324                 }
 325             }
 326         }
 327
 328         #endregion
 329
 330         #region EquiJoins
 331         /// <summary>
 332         /// Is this "simple" predicate an equi-join predicate?
 333         ///   (ie) is it of the form "var1 = var2"
 334         /// Return "var1" and "var2"
 335         /// </summary>
 336         /// <param name="simplePredicateNode">the simple predicate</param>
 337         /// <param name="leftVar">var on the left-side</param>
 338         /// <param name="rightVar">var on the right</param>
 339         /// <returns>true, if this is an equijoin predicate</returns>
 340         private static bool IsEquiJoinPredicate(Node simplePredicateNode, out Var leftVar, out Var rightVar)
 341         {
 342             leftVar = null;
 343             rightVar = null;
 344             if (simplePredicateNode.Op.OpType != OpType.EQ)
 345             {
 346                 return false;
 347             }
 348
 349             VarRefOp leftVarOp = simplePredicateNode.Child0.Op as VarRefOp;
 350             if (leftVarOp == null)
 351             {
 352                 return false;
 353             }
 354             VarRefOp rightVarOp = simplePredicateNode.Child1.Op as VarRefOp;
 355             if (rightVarOp == null)
 356             {
 357                 return false;
 358             }
 359
 360             leftVar = leftVarOp.Var;
 361             rightVar = rightVarOp.Var;
 362             return true;
 363         }
 364
 365         /// <summary>
 366         /// Is this an equi-join predicate involving columns from the specified tables?
 367         /// On output, if this was indeed an equijoin predicate, "leftVar" is the
 368         /// column of the left table, while "rightVar" is the column of the right table
 369         /// and the predicate itself is of the form "leftVar = rightVar"
 370         /// </summary>
 371         /// <param name="simplePredicateNode">the simple predicate node</param>
 372         /// <param name="leftTableDefinitions">interesting columns of the left table</param>
 373         /// <param name="rightTableDefinitions">interesting columns of the right table</param>
 374         /// <param name="leftVar">join column of the left table</param>
 375         /// <param name="rightVar">join column of the right table</param>
 376         /// <returns>true, if this is an equijoin predicate involving columns from the 2 tables</returns>
 377         private static bool IsEquiJoinPredicate(Node simplePredicateNode,
 378             VarVec leftTableDefinitions, VarVec rightTableDefinitions,
 379             out Var leftVar, out Var rightVar)
 380         {
 381             Var tempLeftVar;
 382             Var tempRightVar;
 383
 384             leftVar = null;
 385             rightVar = null;
 386             if (!Predicate.IsEquiJoinPredicate(simplePredicateNode, out tempLeftVar, out tempRightVar))
 387             {
 388                 return false;
 389             }
 390
 391             if (leftTableDefinitions.IsSet(tempLeftVar) &&
 392                 rightTableDefinitions.IsSet(tempRightVar))
 393             {
 394                 leftVar = tempLeftVar;
 395                 rightVar = tempRightVar;
 396             }
 397             else if (leftTableDefinitions.IsSet(tempRightVar) &&
 398                      rightTableDefinitions.IsSet(tempLeftVar))
 399             {
 400                 leftVar = tempRightVar;
 401                 rightVar = tempLeftVar;
 402             }
 403             else
 404             {
 405                 return false;
 406             }
 407
 408             return true;
 409         }
 410         #endregion
 411
 412         #region Nulls
 413         /// <summary>
 414         /// Does this predicate preserve nulls on the specified columns of the table?
 415         /// If any of the columns participates in a comparison predicate, or in a
 416         /// not-null predicate, then, nulls are not preserved
 417         /// </summary>
 418         /// <param name="simplePredNode">the "simple" predicate node</param>
 419         /// <param name="tableColumns">list of table columns</param>
 420         /// <returns>true, if nulls are preserved</returns>
 421         private static bool PreservesNulls(Node simplePredNode, VarVec tableColumns)
 422         {
 423             VarRefOp varRefOp;
 424
 425             switch (simplePredNode.Op.OpType)
 426             {
 427                 case OpType.EQ:
 428                 case OpType.NE:
 429                 case OpType.GT:
 430                 case OpType.GE:
 431                 case OpType.LT:
 432                 case OpType.LE:
 433                     varRefOp = simplePredNode.Child0.Op as VarRefOp;
 434                     if (varRefOp != null && tableColumns.IsSet(varRefOp.Var))
 435                     {
 436                         return false;
 437                     }
 438                     varRefOp = simplePredNode.Child1.Op as VarRefOp;
 439                     if (varRefOp != null && tableColumns.IsSet(varRefOp.Var))
 440                     {
 441                         return false;
 442                     }
 443                     return true;
 444
 445                 case OpType.Not:
 446                     if (simplePredNode.Child0.Op.OpType != OpType.IsNull)
 447                     {
 448                         return true;
 449                     }
 450                     varRefOp = simplePredNode.Child0.Child0.Op as VarRefOp;
 451                     return (varRefOp == null || !tableColumns.IsSet(varRefOp.Var));
 452
 453                 case OpType.Like:
 454                     // If the predicate is "column LIKE constant ...", then the
 455                     // predicate does not preserve nulls
 456                     ConstantBaseOp constantOp = simplePredNode.Child1.Op as ConstantBaseOp;
 457                     if (constantOp == null || (constantOp.OpType == OpType.Null))
 458                     {
 459                         return true;
 460                     }
 461                     varRefOp = simplePredNode.Child0.Op as VarRefOp;
 462                     if (varRefOp != null && tableColumns.IsSet(varRefOp.Var))
 463                     {
 464                         return false;
 465                     }
 466                     return true;
 467
 468                 default:
 469                     return true;
 470             }
 471         }
 472         #endregion
 473
 474         #region Keys
 475         private bool IsKeyPredicate(Node left, Node right, VarVec keyVars, VarVec definitions, out Var keyVar)
 476         {
 477             keyVar = null;
 478
 479             // If the left-side is not a Var, then return false
 480             if (left.Op.OpType != OpType.VarRef)
 481             {
 482                 return false;
 483             }
 484             VarRefOp varRefOp = (VarRefOp)left.Op;
 485             keyVar = varRefOp.Var;
 486
 487             // Not a key of this table?
 488             if (!keyVars.IsSet(keyVar))
 489             {
 490                 return false;
 491             }
 492
 493             // Make sure that the other side is either a constant, or has no
 494             // references at all to us
 495             NodeInfo otherNodeInfo = m_command.GetNodeInfo(right);
 496             VarVec otherVarExternalReferences = otherNodeInfo.ExternalReferences.Clone();
 497             otherVarExternalReferences.And(definitions);
 498             return otherVarExternalReferences.IsEmpty;
 499         }
 500         #endregion
 501
 502         #endregion
 503     }
 504 }