|
//---------------------------------------------------------------------
// <copyright file="Predicate.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// </copyright>
//
// @owner Microsoft
// @backupOwner Microsoft
//---------------------------------------------------------------------
using System;
using System.Collections.Generic;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
// It is fine to use Debug.Assert in cases where you assert an obvious thing that is supposed
// to prevent from simple mistakes during development (e.g. method argument validation
// in cases where it was you who created the variables or the variables had already been validated or
// in "else" clauses where due to code changes (e.g. adding a new value to an enum type) the default
// "else" block is chosen why the new condition should be treated separately). This kind of asserts are
// (can be) helpful when developing new code to avoid simple mistakes but have no or little value in
// the shipped product.
// PlanCompiler.Assert *MUST* be used to verify conditions in the trees. These would be assumptions
// about how the tree was built etc. - in these cases we probably want to throw an exception (this is
// what PlanCompiler.Assert does when the condition is not met) if either the assumption is not correct
// or the tree was built/rewritten not the way we thought it was.
// Use your judgment - if you rather remove an assert than ship it use Debug.Assert otherwise use
// PlanCompiler.Assert.
using System.Globalization;
using System.Data.Query.InternalTrees;
namespace System.Data.Query.PlanCompiler
{
/// <summary>
/// The Predicate class represents a condition (predicate) in CNF.
/// A predicate consists of a number of "simple" parts, and the parts are considered to be
/// ANDed together
///
/// This class provides a number of useful functions related to
/// - Single Table predicates
/// - Join predicates
/// - Key preservation
/// - Null preservation
/// etc.
///
/// Note: This class doesn't really convert node trees into CNF form. It looks for
/// basic CNF patterns, and reasons about them. For example,
/// (a AND b) OR c
/// can technically be translated into (a OR c) AND (b OR c),
/// but we don't bother.
/// At some future point of time, it might be appropriate to consider this
///
/// </summary>
internal class Predicate
{
#region private state
private Command m_command;
private List<Node> m_parts;
#endregion
#region constructors
/// <summary>
/// Create an empty predicate
/// </summary>
/// <param name="command"></param>
internal Predicate(Command command)
{
m_command = command;
m_parts = new List<Node>();
}
/// <summary>
/// Create a predicate from a node tree
/// </summary>
/// <param name="command">current iqt command</param>
/// <param name="andTree">the node tree</param>
internal Predicate(Command command, Node andTree)
: this(command)
{
PlanCompiler.Assert(andTree != null, "null node passed to Predicate() constructor");
InitFromAndTree(andTree);
}
#endregion
#region public surface
#region construction APIs
/// <summary>
/// Add a new "part" (simple predicate) to the current list of predicate parts
/// </summary>
/// <param name="n">simple predicate</param>
internal void AddPart(Node n)
{
m_parts.Add(n);
}
#endregion
#region Reconstruction (of node tree)
/// <summary>
/// Build up an AND tree based on the current parts.
/// Specifically, if I have parts (p1, p2, ..., pn), we build up a tree that looks like
/// p1 AND p2 AND ... AND pn
///
/// If we have no parts, we return a null reference
/// If we have only one part, then we return just that part
/// </summary>
/// <returns>the and subtree</returns>
internal Node BuildAndTree()
{
Node andNode = null;
foreach (Node n in m_parts)
{
if (andNode == null)
{
andNode = n;
}
else
{
andNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.And),
andNode, n);
}
}
return andNode;
}
#endregion
#region SingleTable (Filter) Predicates
/// <summary>
/// Partition the current predicate into predicates that only apply
/// to the specified table (single-table-predicates), and others
/// </summary>
/// <param name="tableDefinitions">current columns defined by the table</param>
/// <param name="otherPredicates">non-single-table predicates</param>
/// <returns>single-table-predicates</returns>
internal Predicate GetSingleTablePredicates(VarVec tableDefinitions,
out Predicate otherPredicates)
{
List<VarVec> tableDefinitionList = new List<VarVec>();
tableDefinitionList.Add(tableDefinitions);
List<Predicate> singleTablePredicateList;
GetSingleTablePredicates(tableDefinitionList, out singleTablePredicateList, out otherPredicates);
return singleTablePredicateList[0];
}
#endregion
#region EquiJoins
/// <summary>
/// Get the set of equi-join columns from this predicate
/// </summary>
/// <param name="leftTableDefinitions"></param>
/// <param name="rightTableDefinitions"></param>
/// <param name="leftTableEquiJoinColumns"></param>
/// <param name="rightTableEquiJoinColumns"></param>
/// <param name="otherPredicates"></param>
internal void GetEquiJoinPredicates(VarVec leftTableDefinitions, VarVec rightTableDefinitions,
out List<Var> leftTableEquiJoinColumns, out List<Var> rightTableEquiJoinColumns,
out Predicate otherPredicates)
{
otherPredicates = new Predicate(m_command);
leftTableEquiJoinColumns = new List<Var>();
rightTableEquiJoinColumns = new List<Var>();
foreach (Node part in m_parts)
{
Var leftTableVar;
Var rightTableVar;
if (IsEquiJoinPredicate(part, leftTableDefinitions, rightTableDefinitions, out leftTableVar, out rightTableVar))
{
leftTableEquiJoinColumns.Add(leftTableVar);
rightTableEquiJoinColumns.Add(rightTableVar);
}
else
{
otherPredicates.AddPart(part);
}
}
}
internal Predicate GetJoinPredicates(VarVec leftTableDefinitions, VarVec rightTableDefinitions,
out Predicate otherPredicates)
{
Predicate joinPredicate = new Predicate(m_command);
otherPredicates = new Predicate(m_command);
foreach (Node part in m_parts)
{
Var leftTableVar;
Var rightTableVar;
if (Predicate.IsEquiJoinPredicate(part, leftTableDefinitions, rightTableDefinitions, out leftTableVar, out rightTableVar))
{
joinPredicate.AddPart(part);
}
else
{
otherPredicates.AddPart(part);
}
}
return joinPredicate;
}
#endregion
#region Keys
/// <summary>
/// Is the current predicate a "key-satisfying" predicate?
/// </summary>
/// <param name="keyVars">list of keyVars</param>
/// <param name="definitions">current table definitions</param>
/// <returns>true, if this predicate satisfies the keys</returns>
internal bool SatisfiesKey(VarVec keyVars, VarVec definitions)
{
if (keyVars.Count > 0)
{
VarVec missingKeys = keyVars.Clone();
foreach (Node part in m_parts)
{
if (part.Op.OpType != OpType.EQ)
{
continue;
}
Var keyVar;
if (IsKeyPredicate(part.Child0, part.Child1, keyVars, definitions, out keyVar))
{
missingKeys.Clear(keyVar);
}
else if (IsKeyPredicate(part.Child1, part.Child0, keyVars, definitions, out keyVar))
{
missingKeys.Clear(keyVar);
}
}
return missingKeys.IsEmpty;
}
return false;
}
#endregion
#region Nulls
/// <summary>
/// Does this predicate preserve nulls for the table columns?
///
/// If the ansiNullSemantics parameter is set, then we simply return true
/// always - this shuts off most optimizations
///
/// </summary>
/// <param name="tableColumns">list of columns to consider</param>
/// <param name="ansiNullSemantics">use ansi null semantics</param>
/// <returns>true, if the predicate preserves nulls</returns>
internal bool PreservesNulls(VarVec tableColumns, bool ansiNullSemantics)
{
// Don't mess with non-ansi semantics
if (!ansiNullSemantics)
{
return true;
}
// If at least one part does not preserve nulls, then we simply return false
foreach (Node part in m_parts)
{
if (!PreservesNulls(part, tableColumns))
{
return false;
}
}
return true;
}
#endregion
#endregion
#region private methods
#region construction
private void InitFromAndTree(Node andTree)
{
if (andTree.Op.OpType == OpType.And)
{
InitFromAndTree(andTree.Child0);
InitFromAndTree(andTree.Child1);
}
else
{
m_parts.Add(andTree);
}
}
#endregion
#region Single Table Predicates
private void GetSingleTablePredicates(List<VarVec> tableDefinitions,
out List<Predicate> singleTablePredicates, out Predicate otherPredicates)
{
singleTablePredicates = new List<Predicate>();
foreach (VarVec vec in tableDefinitions)
{
singleTablePredicates.Add(new Predicate(m_command));
}
otherPredicates = new Predicate(m_command);
VarVec externalRefs = m_command.CreateVarVec();
foreach (Node part in m_parts)
{
NodeInfo nodeInfo = m_command.GetNodeInfo(part);
bool singleTablePart = false;
for (int i = 0; i < tableDefinitions.Count; i++)
{
VarVec tableColumns = tableDefinitions[i];
if (tableColumns != null)
{
externalRefs.InitFrom(nodeInfo.ExternalReferences);
externalRefs.Minus(tableColumns);
if (externalRefs.IsEmpty)
{
singleTablePart = true;
singleTablePredicates[i].AddPart(part);
break;
}
}
}
if (!singleTablePart)
{
otherPredicates.AddPart(part);
}
}
}
#endregion
#region EquiJoins
/// <summary>
/// Is this "simple" predicate an equi-join predicate?
/// (ie) is it of the form "var1 = var2"
/// Return "var1" and "var2"
/// </summary>
/// <param name="simplePredicateNode">the simple predicate</param>
/// <param name="leftVar">var on the left-side</param>
/// <param name="rightVar">var on the right</param>
/// <returns>true, if this is an equijoin predicate</returns>
private static bool IsEquiJoinPredicate(Node simplePredicateNode, out Var leftVar, out Var rightVar)
{
leftVar = null;
rightVar = null;
if (simplePredicateNode.Op.OpType != OpType.EQ)
{
return false;
}
VarRefOp leftVarOp = simplePredicateNode.Child0.Op as VarRefOp;
if (leftVarOp == null)
{
return false;
}
VarRefOp rightVarOp = simplePredicateNode.Child1.Op as VarRefOp;
if (rightVarOp == null)
{
return false;
}
leftVar = leftVarOp.Var;
rightVar = rightVarOp.Var;
return true;
}
/// <summary>
/// Is this an equi-join predicate involving columns from the specified tables?
/// On output, if this was indeed an equijoin predicate, "leftVar" is the
/// column of the left table, while "rightVar" is the column of the right table
/// and the predicate itself is of the form "leftVar = rightVar"
/// </summary>
/// <param name="simplePredicateNode">the simple predicate node</param>
/// <param name="leftTableDefinitions">interesting columns of the left table</param>
/// <param name="rightTableDefinitions">interesting columns of the right table</param>
/// <param name="leftVar">join column of the left table</param>
/// <param name="rightVar">join column of the right table</param>
/// <returns>true, if this is an equijoin predicate involving columns from the 2 tables</returns>
private static bool IsEquiJoinPredicate(Node simplePredicateNode,
VarVec leftTableDefinitions, VarVec rightTableDefinitions,
out Var leftVar, out Var rightVar)
{
Var tempLeftVar;
Var tempRightVar;
leftVar = null;
rightVar = null;
if (!Predicate.IsEquiJoinPredicate(simplePredicateNode, out tempLeftVar, out tempRightVar))
{
return false;
}
if (leftTableDefinitions.IsSet(tempLeftVar) &&
rightTableDefinitions.IsSet(tempRightVar))
{
leftVar = tempLeftVar;
rightVar = tempRightVar;
}
else if (leftTableDefinitions.IsSet(tempRightVar) &&
rightTableDefinitions.IsSet(tempLeftVar))
{
leftVar = tempRightVar;
rightVar = tempLeftVar;
}
else
{
return false;
}
return true;
}
#endregion
#region Nulls
/// <summary>
/// Does this predicate preserve nulls on the specified columns of the table?
/// If any of the columns participates in a comparison predicate, or in a
/// not-null predicate, then, nulls are not preserved
/// </summary>
/// <param name="simplePredNode">the "simple" predicate node</param>
/// <param name="tableColumns">list of table columns</param>
/// <returns>true, if nulls are preserved</returns>
private static bool PreservesNulls(Node simplePredNode, VarVec tableColumns)
{
VarRefOp varRefOp;
switch (simplePredNode.Op.OpType)
{
case OpType.EQ:
case OpType.NE:
case OpType.GT:
case OpType.GE:
case OpType.LT:
case OpType.LE:
varRefOp = simplePredNode.Child0.Op as VarRefOp;
if (varRefOp != null && tableColumns.IsSet(varRefOp.Var))
{
return false;
}
varRefOp = simplePredNode.Child1.Op as VarRefOp;
if (varRefOp != null && tableColumns.IsSet(varRefOp.Var))
{
return false;
}
return true;
case OpType.Not:
if (simplePredNode.Child0.Op.OpType != OpType.IsNull)
{
return true;
}
varRefOp = simplePredNode.Child0.Child0.Op as VarRefOp;
return (varRefOp == null || !tableColumns.IsSet(varRefOp.Var));
case OpType.Like:
// If the predicate is "column LIKE constant ...", then the
// predicate does not preserve nulls
ConstantBaseOp constantOp = simplePredNode.Child1.Op as ConstantBaseOp;
if (constantOp == null || (constantOp.OpType == OpType.Null))
{
return true;
}
varRefOp = simplePredNode.Child0.Op as VarRefOp;
if (varRefOp != null && tableColumns.IsSet(varRefOp.Var))
{
return false;
}
return true;
default:
return true;
}
}
#endregion
#region Keys
private bool IsKeyPredicate(Node left, Node right, VarVec keyVars, VarVec definitions, out Var keyVar)
{
keyVar = null;
// If the left-side is not a Var, then return false
if (left.Op.OpType != OpType.VarRef)
{
return false;
}
VarRefOp varRefOp = (VarRefOp)left.Op;
keyVar = varRefOp.Var;
// Not a key of this table?
if (!keyVars.IsSet(keyVar))
{
return false;
}
// Make sure that the other side is either a constant, or has no
// references at all to us
NodeInfo otherNodeInfo = m_command.GetNodeInfo(right);
VarVec otherVarExternalReferences = otherNodeInfo.ExternalReferences.Clone();
otherVarExternalReferences.And(definitions);
return otherVarExternalReferences.IsEmpty;
}
#endregion
#endregion
}
}
|