Code:
/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / PreProcessor.cs / 2 / PreProcessor.cs
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....], [....]
//---------------------------------------------------------------------
using System;
using System.Collections.Generic;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Linq;
using System.Data.Common;
using md = System.Data.Metadata.Edm;
using System.Data.Query.InternalTrees;
using System.Data.Metadata.Edm;
using System.Data.Common.Utils;
//
// The PreProcessor module is responsible for performing any required preprocessing
// on the tree (and gathering information) before subsequent phases mess with the tree.
// The main aspects of preprocessing we perform here are
// (a) gathering information about all structured types and entitysets referenced in the
// query
// (b) Normalization of queries. Currently, we only handle scalar subqueries, and these
// are converted into outer-apply subqueries
// (c) Translation of multiset constructors into subqueries of the form
// "select a from dual union all select b from dual ..."
//
namespace System.Data.Query.PlanCompiler
{
internal class DiscriminatorMapInfo {
internal EntityTypeBase RootEntityType;
internal bool IncludesSubTypes;
internal ExplicitDiscriminatorMap DiscriminatorMap;
internal DiscriminatorMapInfo(EntityTypeBase rootEntityType, bool includesSubTypes, ExplicitDiscriminatorMap discriminatorMap)
{
RootEntityType = rootEntityType;
IncludesSubTypes = includesSubTypes;
DiscriminatorMap = discriminatorMap;
}
///
/// Merge the discriminatorMap info we just found with what we've already found.
///
/// In practice, if either the current or the new map is from an OfTypeOnly view, we
/// have to avoid the optimizations.
///
/// If we have a new map that is a superset of the current map, then we can just swap
/// the new map for the current one.
///
/// If the current map is tha super set of the new one ther's nothing to do.
///
/// (Of course, if neither has changed, then we really don't need to look)
///
internal void Merge(EntityTypeBase neededRootEntityType, bool includesSubtypes, ExplicitDiscriminatorMap discriminatorMap)
{
// If what we've found doesn't exactly match what we are looking for we have more work to do
if (RootEntityType != neededRootEntityType || IncludesSubTypes != includesSubtypes)
{
if (!IncludesSubTypes || !includesSubtypes)
{
// If either the original or the new map is from an of-type-only view we can't
// merge, we just have to not optimize this case.
DiscriminatorMap = null;
}
if (TypeSemantics.IsSubTypeOf(RootEntityType, neededRootEntityType))
{
// we're asking for a super type of existing type, and what we had is a proper
// subset of it -we can replace the existing item.
RootEntityType = neededRootEntityType;
DiscriminatorMap = discriminatorMap;
}
if (!TypeSemantics.IsSubTypeOf(neededRootEntityType, RootEntityType))
{
// If either the original or the new map is from an of-type-only view we can't
// merge, we just have to not optimize this case.
DiscriminatorMap = null;
}
}
}
}
///
/// The PreProcessor performs preprocessing of the ITree to facilitate processing
/// by later modules.
///
internal class PreProcessor : BasicOpVisitorOfNode
{
#region private state
private PlanCompiler m_compilerState;
private Command m_command { get { return m_compilerState.Command; } }
// nested subquery tracking
private Stack m_ancestors;
private Dictionary> m_nodeSubqueries;
// current nested view depth (0 for top-level query)
private int m_viewNestingLevel;
// track list of referenced types, entitysets and entitycontainers
private HashSet m_referencedEntityContainers;
private List m_referencedEntitySets;
private List m_referencedTypes;
private List m_freeFloatingEntityConstructorTypes;
private HashSet m_typesNeedingNullSentinel;
// helper for rel properties
private RelPropertyHelper m_relPropertyHelper;
// track discriminator metadata
private bool m_suppressDiscriminatorMaps;
private readonly Dictionary m_discriminatorMaps;
#endregion
#region constructors
private PreProcessor(PlanCompiler planCompilerState)
{
m_compilerState = planCompilerState;
m_ancestors = new Stack();
m_nodeSubqueries = new Dictionary>();
m_viewNestingLevel = 0;
m_referencedEntitySets = new List();
m_referencedTypes = new List();
m_freeFloatingEntityConstructorTypes = new List();
m_referencedEntityContainers = new HashSet();
m_relPropertyHelper = new RelPropertyHelper(m_command.MetadataWorkspace, m_command.ReferencedRelProperties);
m_discriminatorMaps = new Dictionary();
m_typesNeedingNullSentinel = new HashSet();
}
#endregion
#region public methods
///
/// The driver routine. "Normalizes" the command;
///
/// plan compiler state
/// type information about all types/sets referenced in the query
internal static void Process(PlanCompiler planCompilerState,
out StructuredTypeInfo typeInfo)
{
PreProcessor preProcessor = new PreProcessor(planCompilerState);
preProcessor.Process();
StructuredTypeInfo.Process(planCompilerState.Command,
preProcessor.m_referencedTypes,
preProcessor.m_referencedEntitySets,
preProcessor.m_freeFloatingEntityConstructorTypes,
preProcessor.m_suppressDiscriminatorMaps ? null : preProcessor.m_discriminatorMaps,
preProcessor.m_relPropertyHelper,
preProcessor.m_typesNeedingNullSentinel,
out typeInfo);
}
#endregion
#region private methods
#region driver
internal void Process()
{
m_command.Root = VisitNode(m_command.Root);
//
// Add any Vars that are of structured type - if the Vars aren't
// referenced via a VarRefOp, we end up losing them...
//
foreach (Var v in m_command.Vars)
{
AddTypeReference(v.Type);
}
//
// If we have any "structured" types, then we need to run through NTE
//
if (m_referencedTypes.Count > 0)
{
m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NTE);
//
// Find any structured types that are projected at the top level, and
// ensure that we can handle their nullability.
//
PhysicalProjectOp ppOp = (PhysicalProjectOp)m_command.Root.Op; // this better be the case or we have other problems.
ppOp.ColumnMap.Accept(StructuredTypeNullabilityAnalyzer.Instance, m_typesNeedingNullSentinel);
}
}
#endregion
#region private state maintenance
#region type and set information
///
/// Mark this EntitySet as referenced in the query
///
///
private void AddEntitySetReference(EntitySet entitySet)
{
m_referencedEntitySets.Add(entitySet);
if (!m_referencedEntityContainers.Contains(entitySet.EntityContainer))
{
m_referencedEntityContainers.Add(entitySet.EntityContainer);
}
}
///
/// Mark this type as being referenced in the query, if it is a structured
/// type or a collection of structured type
///
/// type to reference
private void AddTypeReference(TypeUsage type)
{
if (TypeUtils.IsStructuredType(type) || TypeUtils.IsCollectionType(type))
{
m_referencedTypes.Add(type);
}
}
///
/// Get the list of relationshipsets that can hold instances of the given relationshiptype
///
/// We identify the list of relationshipsets in the current list of entitycontainers that are
/// of the given type. Since we don't yet support relationshiptype subtyping, this is a little
/// easier than the entity version
///
/// the relationship type to look for
/// the list of relevant relationshipsets
private List GetRelationshipSets(RelationshipType relType)
{
List relSets = new List();
foreach (EntityContainer entityContainer in m_referencedEntityContainers)
{
foreach (EntitySetBase set in entityContainer.BaseEntitySets)
{
RelationshipSet relSet = set as RelationshipSet;
if (relSet != null &&
relSet.ElementType.Equals(relType))
{
relSets.Add(relSet);
}
}
}
return relSets;
}
///
/// Find all entitysets (that are reachable in the current query) that can hold instances that
/// are *at least* of type "entityType".
/// An entityset ES of type T1 can hold instances that are at least of type T2, if one of the following
/// is true
/// - T1 is a subtype of T2
/// - T2 is a subtype of T1
/// - T1 is equal to T2
///
/// the desired entity type
/// list of all entitysets of the desired shape
private List GetEntitySets(TypeUsage entityType)
{
List sets = new List();
foreach (EntityContainer container in m_referencedEntityContainers)
{
foreach (EntitySetBase baseSet in container.BaseEntitySets)
{
EntitySet set = baseSet as EntitySet;
if (set != null &&
(set.ElementType.Equals(entityType.EdmType) ||
TypeSemantics.IsSubTypeOf(entityType.EdmType, set.ElementType) ||
TypeSemantics.IsSubTypeOf(set.ElementType, entityType.EdmType)))
{
sets.Add(set);
}
}
}
return sets;
}
#endregion
#region Subquery Handling
///
/// Adds a subquery to the list of subqueries for the relOpNode
///
/// the RelOp node
/// the subquery
private void AddSubqueryToRelOpNode(Node relOpNode, Node subquery)
{
List nestedSubqueries;
// Create an entry in the map if there isn't one already
if (!m_nodeSubqueries.TryGetValue(relOpNode, out nestedSubqueries))
{
nestedSubqueries = new List();
m_nodeSubqueries[relOpNode] = nestedSubqueries;
}
// add this subquery to the list of currently tracked subqueries
nestedSubqueries.Add(subquery);
}
///
/// Add a subquery to the "parent" relop node
///
/// the output var to be used - at the current location - in lieu of the subquery
/// the subquery to move
/// a var ref node for the var returned from the subquery
private Node AddSubqueryToParentRelOp(Var outputVar, Node subquery)
{
Node ancestor = FindRelOpAncestor();
PlanCompiler.Assert(ancestor != null, "no ancestors found?");
AddSubqueryToRelOpNode(ancestor, subquery);
subquery = m_command.CreateNode(m_command.CreateVarRefOp(outputVar));
return subquery;
}
///
/// Find the first RelOp node that is in my ancestral path.
/// If I see a PhysicalOp, then I don't have a RelOp parent
///
/// the first RelOp node
private Node FindRelOpAncestor()
{
foreach (Node n in m_ancestors)
{
if (n.Op.IsRelOp)
{
return n;
}
else if (n.Op.IsPhysicalOp)
{
return null;
}
}
return null;
}
#endregion
#endregion
#region View Expansion
///
/// Gets the "defining" query for an S-Space entityset.
/// We simply convert this into
/// select Type(c1, c2, ...) from Set
///
/// A *key* assumption here is that the set is not polymorphic - otherwise, our smplistic
/// constructor model above does not suffice
///
/// current scan table node
/// the ScanTableOp
/// the defining query for this set
private Node GetDefiningQueryForSSpaceSet(Node node, ScanTableOp scanTableOp)
{
//
// We have an S-Space entityset. Build up a simple "select * from T"
// node tree on top of the base entityset
//
EntitySetBase entitySet = scanTableOp.Table.TableMetadata.Extent;
EntityType entityType = entitySet.ElementType as EntityType;
// For relationshipsets, do nothing
if (entityType != null)
{
Table baseTable = m_command.CreateTableInstance(scanTableOp.Table.TableMetadata);
ScanTableOp baseTableOp = m_command.CreateScanTableOp(baseTable);
Node baseTableNode = m_command.CreateNode(baseTableOp);
Var col = baseTable.Columns[0];
List constructorArgs = new List();
foreach (EdmProperty p in entityType.Properties)
{
Node arg = m_command.CreateNode(m_command.CreatePropertyOp(p),
m_command.CreateNode(m_command.CreateVarRefOp(col)));
constructorArgs.Add(arg);
}
Node constructor = m_command.CreateNode(
m_command.CreateNewInstanceOp(TypeUsage.Create(entityType)),
constructorArgs);
Var projectVar;
node = m_command.BuildProject(baseTableNode, constructor, out projectVar);
}
return node;
}
///
/// Convert a CQT command into an IQT subtree.
/// We expect the CQT command to be a query command tree. This is a 3-step
/// process
/// * We first run through the standard CQT-IQT convertor.
/// * We then strip off the root of the IQT (the PhysicalProjectOp)
/// * Finally, we copy the IQT into our current IQT
///
/// When we have metadata caching of IQTs (for views), instead of CQTs,
/// we can get rid of steps 1 and 2.
///
/// the view
/// an IQT subtree in the current command
private Node ConvertToInternalTree(System.Data.Mapping.ViewGeneration.GeneratedView generatedView)
{
Node ret;
Node sourceIqt = generatedView.GetInternalTree(m_command.MetadataWorkspace);
ret = OpCopier.Copy(m_command, sourceIqt);
return ret;
}
///
/// Gets the "expanded" query mapping view for the specified C-Space entity set
///
/// The current node
/// The scanTableOp that references the entity set
///
/// An optional type filter to apply to the generated view.
/// Set to null on return if the generated view renders the type filter superfluous.
///
/// A node that is the root of the new expanded view
private Node ExpandView(Node node, ScanTableOp scanTableOp, ref IsOfOp typeFilter)
{
EntitySetBase entitySet = scanTableOp.Table.TableMetadata.Extent;
PlanCompiler.Assert(entitySet != null, "The target of a ScanTableOp must reference an EntitySet to be used with ExpandView");
PlanCompiler.Assert(entitySet.EntityContainer.DataSpace == DataSpace.CSpace, "Store entity sets cannot have Query Mapping Views and should not be used with ExpandView");
if(typeFilter != null &&
!typeFilter.IsOfOnly &&
TypeSemantics.IsSubTypeOf(entitySet.ElementType, typeFilter.IsOfType.EdmType))
{
//
// If a type filter is being applied to the ScanTableOp, but that filter is asking
// for all elements that are the same type or a supertype of the element type of the
// target entity set, then the type filter is a no-op and can safely be discarded -
// IF AND ONLY IF the type filter is 'OfType' - which includes subtypes - and NOT
// 'IsOfOnly' - which requires an exact type match, and so does not include subtypes.
//
typeFilter = null;
}
//
// Call the GetGeneratedView method to retrieve the query mapping view for the extent referenced
// by the ScanTableOp. The actual method used to do this differs depending on whether the default
// Query Mapping View is sufficient or a targeted view that only filters by element type is required.
//
System.Data.Mapping.ViewGeneration.GeneratedView definingQuery = null;
EntityTypeBase requiredType = scanTableOp.Table.TableMetadata.Extent.ElementType;
bool includeSubtypes = true;
if(typeFilter != null)
{
//
// A type filter is being applied to the ScanTableOp; it may be possible to produce
// an optimized expansion of the view based on type-specific views generated for the
// C-Space entity set.
// The type for which the view should be tuned is the 'OfType' specified on the type filter.
// If the type filter is an 'IsOfOnly' filter then the view should NOT include subtypes of the required type.
//
requiredType = (EntityTypeBase)typeFilter.IsOfType.EdmType;
includeSubtypes = !typeFilter.IsOfOnly;
if(m_command.MetadataWorkspace.TryGetGeneratedViewOfType(entitySet, requiredType, includeSubtypes, out definingQuery))
{
//
// At this point a type-specific view was found that satisifies the type filter's
// constraints in terms of required type and whether subtypes should be included;
// the type filter itself is now unnecessary and should be set to null indicating
// that it can be safely removed (see ProcessScanTableOp and Visit(FilterOp) for this).
//
typeFilter = null;
}
}
//
// If a generated view has not been obtained at this point then either:
// - A type filter was specified but no type-specific view exists that satisfies its constraints.
// OR
// - No type filter was specified.
// In either case the default query mapping view for the referenced entity set should now be retrieved.
//
if(null == definingQuery)
{
definingQuery = m_command.MetadataWorkspace.GetGeneratedView(entitySet);
}
//
// If even the default query mapping view was not found then we cannot continue.
// This implies that the set was not mapped, which should not be allowed, therefore
// a retail assert is used here instead of a regular exception.
//
PlanCompiler.Assert(definingQuery != null, Entity.Strings.ADP_NoQueryMappingView(entitySet.EntityContainer.Name, entitySet.Name));
//
// At this point we're guaranteed to have found a defining query for the view.
// We're now going to convert this into an IQT, and then copy it into our own IQT.
//
Node ret = ConvertToInternalTree(definingQuery);
//
// Make sure we're tracking what we've asked any discriminator maps to contain.
//
DetermineDiscriminatorMapUsage(ret, entitySet, requiredType, includeSubtypes);
//
// Build up a ScanViewOp to "cap" the defining query below
//
ScanViewOp scanViewOp = m_command.CreateScanViewOp(scanTableOp.Table);
ret = m_command.CreateNode(scanViewOp, ret);
return ret;
}
///
/// If the discrminator map we're already tracking for this type (in this entityset)
/// isn't already rooted at our required type, then we have to suppress the use of
/// the descriminator maps when we constrct the structuredtypes; see SQLBUDT #615744
///
private void DetermineDiscriminatorMapUsage(Node viewNode, EntitySetBase entitySet, EntityTypeBase rootEntityType, bool includeSubtypes) {
ExplicitDiscriminatorMap discriminatorMap = null;
// we expect the view to be capped with a project; we're just being careful here.
if (viewNode.Op.OpType == OpType.Project)
{
DiscriminatedNewEntityOp discriminatedNewEntityOp = viewNode.Child1.Child0.Child0.Op as DiscriminatedNewEntityOp;
if (null != discriminatedNewEntityOp)
{
discriminatorMap = discriminatedNewEntityOp.DiscriminatorMap;
}
}
DiscriminatorMapInfo discriminatorMapInfo;
if (!m_discriminatorMaps.TryGetValue(entitySet, out discriminatorMapInfo))
{
if (null == rootEntityType)
{
rootEntityType = entitySet.ElementType;
includeSubtypes = true;
}
discriminatorMapInfo = new DiscriminatorMapInfo(rootEntityType, includeSubtypes, discriminatorMap);
m_discriminatorMaps.Add(entitySet, discriminatorMapInfo);
}
else
{
discriminatorMapInfo.Merge(rootEntityType, includeSubtypes, discriminatorMap);
}
}
#endregion
#region NavigateOp rewrites
///
/// Rewrites a NavigateOp tree in the following fashion
/// SELECT VALUE r.ToEnd
/// FROM (SELECT VALUE r1 FROM RS1 as r1
/// UNION ALL
/// SELECT VALUE r2 FROM RS2 as r2
/// ...
/// SELECT VALUE rN FROM RSN as rN) as r
/// WHERE r.FromEnd = sourceRef
///
/// RS1, RS2 etc. are the set of all relationshipsets that can hold instances of the specified
/// relationship type. "sourceRef" is the single (ref-type) argument to the NavigateOp that
/// represents the from-end of the navigation traversal
/// If the toEnd is multi-valued, then we stick a Collect(PhysicalProject( over the subquery above
///
/// A couple of special cases.
/// If no relationship sets can be found, we return a NULL (if the
/// toEnd is single-valued), or an empty multiset (if the toEnd is multi-valued)
///
/// If the toEnd is single-valued, *AND* the input Op is a GetEntityRefOp, then
/// we convert the NavigateOp into a RelPropertyOp over the entity.
///
/// the navigateOp tree
/// the navigateOp
/// the output var produced by the subquery (ONLY if the to-End is single-valued)
/// the resulting node
private Node RewriteNavigateOp(Node navigateOpNode, NavigateOp navigateOp, out Var outputVar)
{
outputVar = null;
//
// Currently, navigation of composition relationships is not supported.
//
if (!Helper.IsAssociationType(navigateOp.Relationship))
{
throw EntityUtil.NotSupported(System.Data.Entity.Strings.Cqt_RelNav_NoCompositions);
}
//
// If the input to the navigateOp is a GetEntityRefOp, and the navigation
// is to the 1-end of the relationship, convert this into a RelPropertyOp instead - operating on the
// input child to the GetEntityRefOp
//
if (navigateOpNode.Child0.Op.OpType == OpType.GetEntityRef &&
(navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne ||
navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One))
{
PlanCompiler.Assert(m_command.IsRelPropertyReferenced(navigateOp.RelProperty),
"Unreferenced rel property? " + navigateOp.RelProperty);
Op relPropertyOp = m_command.CreateRelPropertyOp(navigateOp.RelProperty);
Node relPropertyNode = m_command.CreateNode(relPropertyOp,
navigateOpNode.Child0.Child0);
return relPropertyNode;
}
List relationshipSets = GetRelationshipSets(navigateOp.Relationship);
//
// Special case: when no relationshipsets can be found. Return NULL or an empty multiset,
// depending on the multiplicity of the toEnd
//
if (relationshipSets.Count == 0)
{
//
// If we're navigating to the 1-end of the relationship, then simply return a null constant
//
if (navigateOp.ToEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many)
{
return m_command.CreateNode(m_command.CreateNullOp(navigateOp.Type));
}
else // return an empty set
{
return m_command.CreateNode(m_command.CreateNewMultisetOp(navigateOp.Type));
}
}
//
// Build up a UNION-ALL ladder over all the relationshipsets
//
List scanTableNodes = new List();
List scanTableVars = new List();
foreach (RelationshipSet relSet in relationshipSets)
{
TableMD tableMD = Command.CreateTableDefinition(relSet);
ScanTableOp tableOp = m_command.CreateScanTableOp(tableMD);
Node branchNode = m_command.CreateNode(tableOp);
Var branchVar = tableOp.Table.Columns[0];
scanTableVars.Add(branchVar);
scanTableNodes.Add(branchNode);
}
Node unionAllNode = null;
Var unionAllVar;
m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar);
//
// Now build up the predicate
//
Node targetEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.ToEnd),
m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar)));
Node sourceEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.FromEnd),
m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar)));
Node predicateNode = m_command.BuildComparison(OpType.EQ, navigateOpNode.Child0, sourceEnd);
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
unionAllNode, predicateNode);
Var projectVar;
Node projectNode = m_command.BuildProject(filterNode, targetEnd, out projectVar);
//
// Finally, some magic about single-valued vs collection-valued ends
//
Node ret;
if (navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many)
{
ret = m_command.BuildCollect(projectNode, projectVar);
}
else
{
ret = projectNode;
outputVar = projectVar;
}
return ret;
}
#endregion
#region DerefOp Rewrites
///
/// Build up a node tree that represents the set of instances from the given table that are at least
/// of the specified type ("ofType"). If "ofType" is NULL, then all rows are returned
///
/// Return the outputVar from the nodetree
///
/// the entityset or relationshipset to scan over
/// the element types we're interested in
/// the output var produced by this node tree
/// the node tree
private Node BuildOfTypeTable(EntitySetBase entitySet, TypeUsage ofType, out Var resultVar)
{
TableMD tableMetadata = Command.CreateTableDefinition(entitySet);
ScanTableOp tableOp = m_command.CreateScanTableOp(tableMetadata);
Node tableNode = m_command.CreateNode(tableOp);
Var tableVar = tableOp.Table.Columns[0];
Node resultNode;
//
// Build a logical "oftype" expression - simply a filter predicate
//
if ((ofType != null) && !entitySet.ElementType.EdmEquals(ofType.EdmType))
{
m_command.BuildOfTypeTree(tableNode, tableVar, ofType, true, out resultNode, out resultVar);
}
else
{
resultNode = tableNode;
resultVar = tableVar;
}
return resultNode;
}
///
/// Produces a relop tree that "logically" produces the target of the derefop. In essence, this gets rewritten
/// into
/// SELECT VALUE e
/// FROM (SELECT VALUE e0 FROM OFTYPE(ES0, T) as e0
/// UNION ALL
/// SELECT VALUE e1 FROM OFTYPE(ES1, T) as e1
/// ...
/// SELECT VALUE eN from OFTYPE(ESN, T) as eN)) as e
/// WHERE REF(e) = myRef
///
/// "T" is the target type of the Deref, and myRef is the (single) argument to the DerefOp
///
/// ES0, ES1 etc. are all the EntitySets that could hold instances that are at least of type "T". We identify this list of sets
/// by looking at all entitycontainers referenced in the query, and looking at all entitysets in those
/// containers that are of the right type
/// An EntitySet ES (of entity type X) can hold instances of T, if one of the following is true
/// - T is a subtype of X
/// - X is equal to T
/// Our situation is a little trickier, since we also need to look for cases where X is a subtype of T.
///
/// the derefOp subtree
/// the derefOp
/// output var produced
/// the subquery described above
private Node RewriteDerefOp(Node derefOpNode, DerefOp derefOp, out Var outputVar)
{
TypeUsage entityType = derefOp.Type;
List targetEntitySets = GetEntitySets(entityType);
if (targetEntitySets.Count == 0)
{
// We didn't find any entityset that could match this. Simply return a null-value
outputVar = null;
return m_command.CreateNode(m_command.CreateNullOp(entityType));
}
List scanTableNodes = new List();
List scanTableVars = new List();
foreach (EntitySet entitySet in targetEntitySets)
{
Var tableVar;
Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar);
scanTableNodes.Add(tableNode);
scanTableVars.Add(tableVar);
}
Node unionAllNode;
Var unionAllVar;
m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar);
//
// Finally build up the key comparison predicate
//
Node entityRefNode = m_command.CreateNode(
m_command.CreateGetEntityRefOp(derefOpNode.Child0.Op.Type),
m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar)));
Node keyComparisonPred = m_command.BuildComparison(OpType.EQ, derefOpNode.Child0, entityRefNode);
Node filterNode = m_command.CreateNode(
m_command.CreateFilterOp(),
unionAllNode,
keyComparisonPred);
outputVar = unionAllVar;
return filterNode;
}
#endregion
#region NavigationProperty Rewrites
///
/// Find the entityset that corresponds to the specified end of the relationship.
///
/// We must find one - else we assert.
///
/// the relationshipset
/// the destination end of the relationship traversal
/// the entityset corresponding to the target end
private static EntitySetBase FindTargetEntitySet(RelationshipSet relationshipSet, RelationshipEndMember targetEnd)
{
EntitySetBase entitySet = null;
AssociationSet associationSet = (AssociationSet)relationshipSet;
// find the corresponding entityset
entitySet = null;
foreach (AssociationSetEnd e in associationSet.AssociationSetEnds)
{
if (e.CorrespondingAssociationEndMember.EdmEquals(targetEnd))
{
entitySet = e.EntitySet;
break;
}
}
PlanCompiler.Assert(entitySet != null, "Could not find entityset for relationshipset " + relationshipSet + ";association end " + targetEnd);
return entitySet;
}
///
/// Builds up a join between the relationshipset and the entityset corresponding to its toEnd. In essence,
/// we produce
/// SELECT r, e
/// FROM RS as r, OFTYPE(ES, T) as e
/// WHERE r.ToEnd = Ref(e)
///
/// "T" is the entity type of the toEnd of the relationship.
///
/// the relationshipset
/// the toEnd of the relationship
/// the var representing the relationship instance ("r") in the output subquery
/// the var representing the entity instance ("e") in the output subquery
/// the join subquery described above
private Node BuildJoinForNavProperty(RelationshipSet relSet, RelationshipEndMember end,
out Var rsVar, out Var esVar)
{
EntitySetBase entitySet = FindTargetEntitySet(relSet, end);
//
// Build out the ScanTable ops for the relationshipset and the entityset. Add the
//
Node asTableNode = BuildOfTypeTable(relSet, null, out rsVar);
Node esTableNode = BuildOfTypeTable(entitySet, TypeHelpers.GetElementTypeUsage(end.TypeUsage), out esVar);
//
// Build up a join between the entityset and the associationset; join on the to-end
//
Node joinPredicate = m_command.BuildComparison(OpType.EQ,
m_command.CreateNode(m_command.CreateGetEntityRefOp(end.TypeUsage), m_command.CreateNode(m_command.CreateVarRefOp(esVar))),
m_command.CreateNode(m_command.CreatePropertyOp(end), m_command.CreateNode(m_command.CreateVarRefOp(rsVar)))
);
Node joinNode = m_command.CreateNode(m_command.CreateInnerJoinOp(),
asTableNode, esTableNode, joinPredicate);
return joinNode;
}
///
/// Rewrite a NavPropertyOp when the target end of the nav property has multiplicity
/// of one (or zero..one).
/// We simply pick up the corresponding rel property from the input entity, and
/// apply a deref operation
/// NavProperty(e, n) => deref(relproperty(e, r))
/// where e is the entity expression, n is the nav-property, and r is the corresponding
/// rel-property
///
/// the rel-property describing the navigation
/// entity instance that we're starting the traversal from
/// type of the target entity
/// a rewritten subtree
private Node RewriteToOneNavigationProperty(RelProperty relProperty,
Node sourceEntityNode, TypeUsage resultType)
{
RelPropertyOp relPropertyOp = m_command.CreateRelPropertyOp(relProperty);
Node relPropertyNode = m_command.CreateNode(relPropertyOp, sourceEntityNode);
DerefOp derefOp = m_command.CreateDerefOp(resultType);
Node derefNode = m_command.CreateNode(derefOp, relPropertyNode);
return derefNode;
}
///
/// Rewrite a NavigationProperty when the relationship is a 1:N relationship.
/// In essence, we find all the relevant target entitysets, and then compare the
/// rel-property on the target end with the source ref
///
/// Converts
/// NavigationProperty(e, r)
/// into
/// SELECT VALUE t
/// FROM (SELECT VALUE e1 FROM ES1 as e1
/// UNION ALL
/// SELECT VALUE e2 FROM ES2 as e2
/// UNION ALL
/// ...
/// ) as t
/// WHERE RelProperty(t, r') = GetEntityRef(e)
///
/// r' is the inverse-relproperty for r
///
/// We also build out a CollectOp over the subquery above, and return that
///
/// the rel-property describing the relationship traversal
/// the list of relevant relationshipsets
/// node tree corresponding to the source entity ref
/// type of the result
/// the rewritten subtree
private Node RewriteOneToManyNavigationProperty(RelProperty relProperty,
List relationshipSets,
Node sourceRefNode, TypeUsage resultType)
{
PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here");
PlanCompiler.Assert(relProperty.FromEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many,
"Expected source end multiplicity to be one. Found 'Many' instead " + relProperty);
Node ret = null;
//
// We convert the
//
TypeUsage entityType = TypeHelpers.GetElementTypeUsage(relProperty.ToEnd.TypeUsage);
List scanTableNodes = new List(relationshipSets.Count);
List scanTableVars = new List(relationshipSets.Count);
foreach (RelationshipSet r in relationshipSets)
{
EntitySetBase entitySet = FindTargetEntitySet(r, relProperty.ToEnd);
Var tableVar;
Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar);
scanTableNodes.Add(tableNode);
scanTableVars.Add(tableVar);
}
//
// Build the union-all node
//
Node unionAllNode;
Var unionAllVar;
m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar);
//
// Now build up the appropriate filter. Select out the relproperty from the other end
//
RelProperty inverseRelProperty = new RelProperty(relProperty.Relationship, relProperty.ToEnd, relProperty.FromEnd);
PlanCompiler.Assert(m_command.IsRelPropertyReferenced(inverseRelProperty),
"Unreferenced rel property? " + inverseRelProperty);
Node inverseRelPropertyNode = m_command.CreateNode(
m_command.CreateRelPropertyOp(inverseRelProperty),
m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar)));
Node predicateNode = m_command.BuildComparison(OpType.EQ,
sourceRefNode, inverseRelPropertyNode);
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
unionAllNode, predicateNode);
//
// The magic of collections...
//
ret = m_command.BuildCollect(filterNode, unionAllVar);
return ret;
}
///
/// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r))
/// where "r" is a many-to-many relationship
///
/// We essentially produce the following subquery
/// SELECT VALUE x.e
/// FROM (SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1)
/// UNION ALL
/// SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1)
/// ...
/// ) as x
/// WHERE x.r.FromEnd = sourceRef
///
/// RS1, RS2 etc. are the relevant relationshipsets
/// ES1, ES2 etc. are the corresponding entitysets for the toEnd of the relationship
/// sourceRef is the ref argument
/// T is the type of the target-end of the relationship
///
/// We then build a CollectOp over the subquery above
///
/// the rel property to traverse
/// list of relevant relationshipsets
/// source ref
/// type of the result
/// relationshipSets,
Node sourceRefNode, TypeUsage resultType)
{
PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here");
PlanCompiler.Assert(relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many &&
relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many,
"Expected target end multiplicity to be 'many'. Found " + relProperty + "; multiplicity = " + relProperty.ToEnd.RelationshipMultiplicity);
Node ret = null;
List joinNodes = new List(relationshipSets.Count);
List outputVars = new List(relationshipSets.Count * 2);
foreach (RelationshipSet r in relationshipSets)
{
Var rsVar;
Var esVar;
Node joinNode = BuildJoinForNavProperty(r, relProperty.ToEnd, out rsVar, out esVar);
joinNodes.Add(joinNode);
outputVars.Add(rsVar);
outputVars.Add(esVar);
}
//
// Build the union-all node
//
Node unionAllNode;
IList unionAllVars;
m_command.BuildUnionAllLadder(joinNodes, outputVars, out unionAllNode, out unionAllVars);
//
// Now build out the filterOp over the left-side var
//
Node rsSourceRefNode = m_command.CreateNode(m_command.CreatePropertyOp(relProperty.FromEnd),
m_command.CreateNode(m_command.CreateVarRefOp(unionAllVars[0])));
Node predicate = m_command.BuildComparison(OpType.EQ,
sourceRefNode, rsSourceRefNode);
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
unionAllNode, predicate);
//
// Finally, build out a project node that only projects out the entity side
//
Node projectNode = m_command.BuildProject(filterNode, new Var[] { unionAllVars[1] }, new Node[] { });
//
// Build a collectOp over the project node
//
ret = m_command.BuildCollect(projectNode, unionAllVars[1]);
return ret;
}
///
/// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r))
///
/// We handle three cases here, depending on the kind of relationship we're
/// dealing with.
/// - *:1 relationships
/// - N:1 relationships
/// - N:M relationships
///
///
/// the navigation property
/// the input ref to start the traversal
/// the result type of the expression
/// the rewritten tree
private Node RewriteNavigationProperty(NavigationProperty navProperty,
Node sourceEntityNode, TypeUsage resultType)
{
Node ret = null;
RelProperty relProperty = new RelProperty(navProperty.RelationshipType, navProperty.FromEndMember, navProperty.ToEndMember);
PlanCompiler.Assert(m_command.IsRelPropertyReferenced(relProperty) || (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many),
"Unreferenced rel property? " + relProperty);
//
// Case 1: The (target end of the) nav property has a multiplicity of 1 (or 0..1)
// (doesn't matter what the sourceEnd multiplicity is)
//
if (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One ||
relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne)
{
ret = RewriteToOneNavigationProperty(relProperty, sourceEntityNode, resultType);
return ret;
}
//
// Otherwise, the target end is multi-valued. We need to deal with
// 2 cases here. A N:1 relationship or a N:M relationship
//
//
// Find the list of all relationships that could satisfy this relationship
// If we find no matching relationship set, simply return an empty collection
//
List relationshipSets = GetRelationshipSets(relProperty.Relationship);
if (relationshipSets.Count == 0)
{
// return an empty set
return m_command.CreateNode(m_command.CreateNewMultisetOp(resultType));
}
//
// Build out a ref over the source entity now
//
Node sourceRefNode = m_command.CreateNode(
m_command.CreateGetEntityRefOp(relProperty.FromEnd.TypeUsage),
sourceEntityNode);
//
// Are we dealing with a many-to-many relationship ?
//
if (relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many)
{
ret = RewriteManyToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode, resultType);
}
else
{
ret = RewriteOneToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode, resultType);
}
return ret;
}
#endregion
#region visitor helpers
///
/// Extends the base class implementation of VisitChildren.
/// Wraps the call to visitchildren() by first adding the current node
/// to the stack of "ancestors", and then popping back the node at the end
///
/// Current node
protected override void VisitChildren(Node n)
{
// Push the current node onto the stack
m_ancestors.Push(n);
for (int i = 0; i < n.Children.Count; i++)
{
n.Children[i] = VisitNode(n.Children[i]);
}
m_ancestors.Pop();
}
#endregion
#region visitor methods
#region ScalarOps
///
/// Default handler for scalar Ops. Simply traverses the children,
/// and also identifies any structured types along the way
///
/// the ScalarOp
/// current subtree
/// the possibly modified node
protected override Node VisitScalarOpDefault(ScalarOp op, Node n)
{
VisitChildren(n); // visit my children
// keep track of referenced types
AddTypeReference(op.Type);
return n;
}
///
/// Rewrite a DerefOp subtree. We have two cases to consider here.
/// We call RewriteDerefOp to return a subtree (and an optional outputVar).
/// If the outputVar is null, then we simply return the subtree produced by those calls.
/// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar
/// in its place.
///
/// As an example,
/// select deref(e) from T
/// gets rewritten into
/// select v from T OuterApply X
/// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X
///
///
/// the derefOp
/// the deref subtree
/// the rewritten tree
public override Node Visit(DerefOp op, Node n)
{
Var outputVar;
VisitScalarOpDefault(op, n);
Node ret = RewriteDerefOp(n, op, out outputVar);
ret = VisitNode(ret);
if (outputVar != null)
{
ret = AddSubqueryToParentRelOp(outputVar, ret);
}
return ret;
}
///
/// Processing for an ElementOp. Replaces this by the corresponding Var from
/// the subquery, and adds the subquery to the list of currently tracked subqueries
///
/// the elementOp
/// current subtree
/// the Var from the subquery
public override Node Visit(ElementOp op, Node n)
{
VisitScalarOpDefault(op, n); // default processing
// get to the subquery...
Node subQueryRelOp = n.Child0;
ProjectOp projectOp = (ProjectOp)subQueryRelOp.Op;
PlanCompiler.Assert(projectOp.Outputs.Count == 1, "input to ElementOp has more than one output var?");
Var projectVar = projectOp.Outputs.First;
Node ret = AddSubqueryToParentRelOp(projectVar, subQueryRelOp);
return ret;
}
///
/// Translate Exists(X) into Exists(select 0 from X)
///
///
///
///
/// Build Project(select 0 from child).
///
///
///
/// Build up an unnest above a scalar op node
/// X => unnest(X)
///
/// the scalarop collection node
/// the unnest node
private Node BuildUnnest(Node collectionNode)
{
PlanCompiler.Assert(collectionNode.Op.IsScalarOp, "non-scalar usage of Unnest?");
PlanCompiler.Assert(md.TypeSemantics.IsCollectionType(collectionNode.Op.Type), "non-collection usage for Unnest?");
Var newVar;
Node varDefNode = m_command.CreateVarDefNode(collectionNode, out newVar);
UnnestOp unnestOp = m_command.CreateUnnestOp(newVar);
Node unnestNode = m_command.CreateNode(unnestOp, varDefNode);
return unnestNode;
}
///
/// Is this function a TVF?
///
/// current function op
/// true, if the function returns a collection
private static bool IsCollectionFunction(FunctionOp op)
{
return md.TypeSemantics.IsCollectionType(op.Type);
}
///
/// Converts a reference to a TVF, by the following
/// Collect(PhysicalProject(Unnest(Func)))
///
/// current function op
/// current function subtree
/// the new expression that corresponds to the TVF
private Node VisitCollectionFunction(FunctionOp op, Node n)
{
PlanCompiler.Assert(IsCollectionFunction(op), "non-TVF function?");
Node unnestNode = BuildUnnest(n);
UnnestOp unnestOp = unnestNode.Op as UnnestOp;
PhysicalProjectOp projectOp = m_command.CreatePhysicalProjectOp(unnestOp.Table.Columns[0]);
Node projectNode = m_command.CreateNode(projectOp, unnestNode);
CollectOp collectOp = m_command.CreateCollectOp(n.Op.Type);
Node collectNode = m_command.CreateNode(collectOp, projectNode);
m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NestPullup);
return collectNode;
}
///
/// Is this function a collection aggregate function. It is, if
/// - it has exactly one child
/// - that child is a collection type
/// - and the function has been marked with the aggregate attribute
///
/// the function op
/// the current subtree
/// true, if this was a collection aggregate function
private static bool IsCollectionAggregateFunction(FunctionOp op, Node n)
{
return ((n.Children.Count == 1) &&
md.TypeSemantics.IsCollectionType(n.Child0.Op.Type) &&
md.TypeSemantics.IsAggregateFunction(op.Function));
}
///
/// Converts a collection aggregate function count(X), where X is a collection into
/// two parts. Part A is a groupby subquery that looks like
/// GroupBy(Unnest(X), empty, count(y))
/// where "empty" describes the fact that the groupby has no keys, and y is an
/// element var of the Unnest
///
/// Part 2 is a VarRef that refers to the aggregate var for count(y) described above.
///
/// Logically, we would replace the entire functionOp by element(GroupBy...). However,
/// since we also want to translate element() into single-row-subqueries, we do this
/// here as well.
///
/// The function itself is replaced by the VarRef, and the GroupBy is added to the list
/// of scalar subqueries for the current relOp node on the stack
///
///
/// the functionOp for the collection agg
/// current subtree
/// the VarRef node that should replace the function
private Node VisitCollectionAggregateFunction(FunctionOp op, Node n)
{
md.TypeUsage softCastType = null;
Node argNode = n.Child0;
if (OpType.SoftCast == argNode.Op.OpType)
{
softCastType = TypeHelpers.GetEdmType(argNode.Op.Type).TypeUsage;
argNode = argNode.Child0;
while (OpType.SoftCast == argNode.Op.OpType)
{
argNode = argNode.Child0;
}
}
Node unnestNode = BuildUnnest(argNode);
UnnestOp unnestOp = unnestNode.Op as UnnestOp;
Var unnestOutputVar = unnestOp.Table.Columns[0];
AggregateOp aggregateOp = m_command.CreateAggregateOp(op.Function, false);
VarRefOp unnestVarRefOp = m_command.CreateVarRefOp(unnestOutputVar);
Node unnestVarRefNode = m_command.CreateNode(unnestVarRefOp);
if (softCastType != null)
{
unnestVarRefNode = m_command.CreateNode(m_command.CreateSoftCastOp(softCastType), unnestVarRefNode);
}
Node aggExprNode = m_command.CreateNode(aggregateOp, unnestVarRefNode);
VarVec keyVars = m_command.CreateVarVec(); // empty keys
Node keyVarDefListNode = m_command.CreateNode(m_command.CreateVarDefListOp());
VarVec gbyOutputVars = m_command.CreateVarVec();
Var aggVar;
Node aggVarDefListNode = m_command.CreateVarDefListNode(aggExprNode, out aggVar);
gbyOutputVars.Set(aggVar);
GroupByOp gbyOp = m_command.CreateGroupByOp(keyVars, gbyOutputVars);
Node gbySubqueryNode = m_command.CreateNode(gbyOp, unnestNode, keyVarDefListNode, aggVarDefListNode);
// "Move" this subquery to my parent relop
Node ret = AddSubqueryToParentRelOp(aggVar, gbySubqueryNode);
return ret;
}
///
/// Pre-processing for a function. Does the default thing. In addition, if the
/// function is a TVF (ie) returns a collection, convert this expression into
/// Nest(select value p from unnest(f) as p)
///
///
///
///
/// Default processing.
/// In addition, if the case statement is of the shape
/// case when X then NULL else Y, or
/// case when X then Y else NULL,
/// where Y is of row type and the types of the input CaseOp, the NULL and Y are the same,
/// marks that type as needing a null sentinel.
/// This allows in NominalTypeElimination the case op to be pushed inside Y's null sentinel.
///
///
///
///
/// If it is a IsNull op over a row type, mark the row type as needing a null sentinel.
///
///
///
///
/// Validates that the nav property agrees with the underlying relationship
///
/// the Nav PropertyOp
/// the subtree
private void ValidateNavPropertyOp(PropertyOp op, Node n)
{
NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo;
//
// If the result of the expanded form of the navigation property is not compatible with
// the declared type of the property, then the navigation property is invalid in the
// context of this command tree's metadata workspace.
//
md.TypeUsage resultType = navProperty.ToEndMember.TypeUsage;
if (TypeSemantics.IsReferenceType(resultType))
{
resultType = TypeHelpers.GetElementTypeUsage(resultType);
}
if (navProperty.ToEndMember.RelationshipMultiplicity == RelationshipMultiplicity.Many)
{
resultType = TypeUsage.Create(resultType.EdmType.GetCollectionType());
}
if (!TypeSemantics.IsEquivalentOrPromotableTo(resultType, op.Type))
{
throw EntityUtil.Metadata(System.Data.Entity.Strings.EntityClient_IncompatibleNavigationPropertyResult(
navProperty.DeclaringType.FullName,
navProperty.Name
)
);
}
}
///
/// Rewrite a PropertyOp subtree for a nav property
///
/// We call RewriteNavigationPropertyOp to return a subtree (and an
/// optional outputVar). If the outputVar is null, then we simply return the subtree produced by those calls.
/// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar
/// in its place.
///
/// As an example,
/// select e.NP from T
/// gets rewritten into
/// select v from T OuterApply X
/// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X
///
/// the PropertyOp
/// the current node
/// the rewritten subtree
private Node VisitNavPropertyOp(PropertyOp op, Node n)
{
ValidateNavPropertyOp(op, n);
//
// This is a bit weird. Ideally, I would always visit the child first (ie) a bottom-up traversal,
// but there's some weird gotchas in the elinq tests ("SelectManyNullResult531057")
//
bool visitChildFirst = (n.Child0.Op.OpType != OpType.Property);
if (visitChildFirst)
{
VisitScalarOpDefault(op, n);
}
NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo;
Node ret = RewriteNavigationProperty(navProperty, n.Child0, op.Type);
ret = VisitNode(ret);
return ret;
}
///
/// Rewrite a PropertyOp subtree.
///
/// If the PropertyOp represents a simple property (ie) not a navigation property, we simply call
/// VisitScalarOpDefault() and return. Otherwise, we call VisitNavPropertyOp and return the result from
/// that function
///
///
/// the PropertyOp
/// the PropertyOp subtree
/// the rewritten tree
public override Node Visit(PropertyOp op, Node n)
{
Node ret;
if (Helper.IsNavigationProperty(op.PropertyInfo))
{
ret = VisitNavPropertyOp(op, n);
}
else
{
ret = VisitScalarOpDefault(op, n);
}
return ret;
}
#endregion
///
/// Handler for a RefOp.
/// Keeps track of the entityset
///
/// the RefOp
/// current RefOp subtree
/// current subtree
public override Node Visit(RefOp op, Node n)
{
VisitScalarOpDefault(op, n); // use default processing
AddEntitySetReference(op.EntitySet); // add to list of references
return n;
}
///
/// Handler for a TreatOp.
/// Rewrites the operator if the argument is guaranteed to be of type
/// op.
///
/// Current TreatOp
/// Current subtree
/// Current subtree
public override Node Visit(TreatOp op, Node n)
{
n = base.Visit(op, n);
// See if TreatOp can be rewritten (if it's not polymorphic)
if (CanRewriteTypeTest(op.Type.EdmType, n.Child0.Op.Type.EdmType))
{
// Return argument directly (if the argument is null, 'treat as' also returns null;
// if the argument is not null, it's guaranteed to be of the correct type)
return n.Child0;
}
return n;
}
///
/// Handler for an IsOfOp.
/// Keeps track of the IsOfType (if it is a structured type) and rewrites the
/// operator if the argument is guaranteed to be of type op.IsOfType
///
/// Current IsOfOp
/// Current subtree
/// Current subtree
public override Node Visit(IsOfOp op, Node n)
{
n = VisitScalarOpDefault(op, n); // default handling first
// keep track of any structured types
AddTypeReference(op.IsOfType);
// See if the IsOfOp can be rewritten (if it's not polymorphic)
if (CanRewriteTypeTest(op.IsOfType.EdmType, n.Child0.Op.Type.EdmType))
{
n = RewriteIsOfAsIsNull(op, n);
}
// For IsOfOnly(abstract type), suppress DiscriminatorMaps since no explicit type id is available for
// abstract types.
if (op.IsOfOnly && op.IsOfType.EdmType.Abstract)
{
m_suppressDiscriminatorMaps = true;
}
return n;
}
// Determines whether a type test expression can be rewritten. Returns true of the
// argument type is guaranteed to implement "testType" (if the argument is non-null).
private bool CanRewriteTypeTest(EdmType testType, EdmType argumentType)
{
// The rewrite only proceeds if the types are the same. If they are not,
// it suggests either that the input result is polymorphic (in which case if OfType
// should be preserved) or the types are incompatible (which is caught
// elsewhere)
if (!testType.EdmEquals(argumentType))
{
return false;
}
// If the IsOfType is non-polymorphic (no base or derived types) the rewrite
// is possible.
if (null != testType.BaseType)
{
return false;
}
// Count sub types
int subTypeCount = 0;
foreach (EdmType subType in MetadataHelper.GetTypeAndSubtypesOf(testType, m_command.MetadataWorkspace, true /*includeAbstractTypes*/))
{
subTypeCount++;
if (2 == subTypeCount) { break; }
}
return 1 == subTypeCount; // no children types
}
// Translates
// 'R is of T'
// to
// '(case when not (R is null) then True else null end) = True'
//
// Input requirements:
//
// - IsOfOp and argument to same must be in the same hierarchy.
// - IsOfOp and argument must have the same type
// - IsOfOp.IsOfType may not have super- or sub- types (validate
// using CanRewriteTypeTest)
//
// Design requirements:
//
// - Must return true if the record exists
// - Must return null if it does not
// - Must be in predicate form to avoid confusing SQL gen
//
// The translation assumes R is of T when R is non null.
private Node RewriteIsOfAsIsNull(IsOfOp op, Node n)
{
// construct 'R is null' predicate
ConditionalOp isNullOp = m_command.CreateConditionalOp(OpType.IsNull);
Node isNullNode = m_command.CreateNode(isNullOp, n.Child0);
// construct 'not (R is null)' predicate
ConditionalOp notOp = m_command.CreateConditionalOp(OpType.Not);
Node notNode = m_command.CreateNode(notOp, isNullNode);
// construct 'True' result
ConstantBaseOp trueOp = m_command.CreateConstantOp(op.Type, true);
Node trueNode = m_command.CreateNode(trueOp);
// construct 'null' default result
NullOp nullOp = m_command.CreateNullOp(op.Type);
Node nullNode = m_command.CreateNode(nullOp);
// create case statement
CaseOp caseOp = m_command.CreateCaseOp(op.Type);
Node caseNode = m_command.CreateNode(caseOp, notNode, trueNode, nullNode);
// create 'case = true' operator
ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ);
Node equalsNode = m_command.CreateNode(equalsOp, caseNode, trueNode);
return equalsNode;
}
///
/// Rewrite a NavigateOp subtree.
/// We call RewriteNavigateOp to return a subtree (and an optional outputVar).
/// If the outputVar is null, then we simply return the subtree produced by those calls.
/// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar
/// in its place.
///
/// As an example,
/// select navigate(e) from T
/// gets rewritten into
/// select v from T OuterApply X
/// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X
///
///
/// the navigateOp
/// the navigateOp subtree
/// the rewritten tree
public override Node Visit(NavigateOp op, Node n)
{
VisitScalarOpDefault(op, n);
Var outputVar;
Node ret = RewriteNavigateOp(n, op, out outputVar);
ret = VisitNode(ret);
// Move subquery to parent relop if necessary
if (outputVar != null)
{
ret = AddSubqueryToParentRelOp(outputVar, ret);
}
return ret;
}
///
/// Find the "current" enclosing entityset
///
/// the enclosing entityset (if any)
private EntitySetBase FindEnclosingEntitySetView()
{
if (m_viewNestingLevel == 0)
{
return null;
}
//
// Walk up the stack of ancestors until we find the appropriate ScanViewOp
//
foreach (Node n in m_ancestors)
{
if (n.Op.OpType == OpType.ScanView)
{
ScanViewOp op = (ScanViewOp)n.Op;
return op.Table.TableMetadata.Extent;
}
}
PlanCompiler.Assert(false, "found no enclosing view - but view-nesting level is greater than zero");
return null;
}
///
/// Find the relationshipset that matches the current entityset + from/to roles
///
///
///
///
/// Find the position of a property in a type.
/// Positions start at zero, and a supertype's properties precede the current
/// type's properties
///
/// the type in question
/// the member to lookup
/// the position of the member in the type (0-based)
private int FindPosition(EdmType type, EdmMember member)
{
int pos = 0;
foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(type))
{
if (m.EdmEquals(member))
{
return pos;
}
pos++;
}
PlanCompiler.Assert(false, "Could not find property " + member + " in type " + type.Name);
return -1;
}
///
/// Build out an expression (NewRecord) that corresponds to the key properties
/// of the passed-in entity constructor
///
/// This function simply looks up the key properties of the entity type, and then
/// identifies the arguments to the constructor corresponding to those
/// properties, and then slaps on a record wrapper over those expressions.
///
/// No copies/clones are performed. That's the responsibility of the caller
///
///
/// the entity constructor op
/// the corresponding subtree
/// the key expression
private Node BuildKeyExpressionForNewEntityOp(Op op, Node n)
{
PlanCompiler.Assert(op.OpType == OpType.NewEntity || op.OpType == OpType.DiscriminatedNewEntity,
"BuildKeyExpression: Unexpected OpType:" + op.OpType);
int offset = (op.OpType == OpType.DiscriminatedNewEntity) ? 1 : 0;
EntityTypeBase entityType = (EntityTypeBase)op.Type.EdmType;
List keyFields = new List();
List> keyFieldTypes = new List>();
foreach (EdmMember k in entityType.KeyMembers)
{
int pos = FindPosition(entityType, k) + offset;
PlanCompiler.Assert(n.Children.Count > pos, "invalid position " + pos + "; total count = " + n.Children.Count);
keyFields.Add(n.Children[pos]);
keyFieldTypes.Add(new KeyValuePair(k.Name, k.TypeUsage));
}
TypeUsage keyExprType = TypeHelpers.CreateRowTypeUsage(keyFieldTypes, true);
NewRecordOp keyOp = m_command.CreateNewRecordOp(keyExprType);
Node keyNode = m_command.CreateNode(keyOp, keyFields);
return keyNode;
}
///
/// Build out an expression corresponding to the rel-property.
///
/// We create a subquery that looks like
/// (select r
/// from RS r
/// where GetRefKey(r.FromEnd) = myKey)
///
/// RS is the single relationship set that corresponds to the given entityset/rel-property pair
/// FromEnd - is the source end of the relationship
/// myKey - is the key expression of the entity being constructed
///
/// NOTE: We always clone "myKey" before use.
///
/// We then convert it into a scalar subquery, and extract out the ToEnd property from
/// the output var of the subquery. (Should we do this inside the subquery itself?)
///
/// If no single relationship-set is found, we return a NULL instead.
///
/// entity set that logically holds instances of the entity we're building
/// the rel-property we're trying to build up
/// the "key" of the entity instance
/// the rel-property expression
private Node BuildRelPropertyExpression(EntitySetBase entitySet, RelProperty relProperty,
Node keyExpr)
{
//
// Make a copy of the current key expression
//
keyExpr = OpCopier.Copy(m_command, keyExpr);
//
// Find the relationship set corresponding to this entityset (and relProperty)
// Return a null ref, if we can't find one
//
RelationshipSet relSet = FindRelationshipSet(entitySet, relProperty);
if (relSet == null)
{
return m_command.CreateNode(m_command.CreateNullOp(relProperty.ToEnd.TypeUsage));
}
ScanTableOp scanTableOp = m_command.CreateScanTableOp(Command.CreateTableDefinition(relSet));
PlanCompiler.Assert(scanTableOp.Table.Columns.Count == 1,
"Unexpected column count for table:" + scanTableOp.Table.TableMetadata.Extent + "=" + scanTableOp.Table.Columns.Count);
Var scanTableVar = scanTableOp.Table.Columns[0];
Node scanNode = m_command.CreateNode(scanTableOp);
Node sourceEndNode = m_command.CreateNode(
m_command.CreatePropertyOp(relProperty.FromEnd),
m_command.CreateNode(m_command.CreateVarRefOp(scanTableVar)));
Node predicateNode = m_command.BuildComparison(OpType.EQ,
keyExpr,
m_command.CreateNode(m_command.CreateGetRefKeyOp(keyExpr.Op.Type), sourceEndNode));
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
scanNode, predicateNode);
//
// Process the node, and then add this as a subquery to the parent relop
//
Node ret = VisitNode(filterNode);
ret = AddSubqueryToParentRelOp(scanTableVar, ret);
//
// Now extract out the target end property
//
ret = m_command.CreateNode(
m_command.CreatePropertyOp(relProperty.ToEnd),
ret);
return ret;
}
///
/// Given an entity constructor (NewEntityOp, DiscriminatedNewEntityOp), build up
/// the list of rel-property expressions.
///
/// Walks through the list of relevant rel-properties, and builds up expressions
/// (using BuildRelPropertyExpression) for each rel-property that does not have
/// an expression already built (preBuiltExpressions)
///
/// entity set that holds instances of the entity we're building
/// the list of relevant rel-properties for this entity type
/// the prebuilt rel-property expressions
/// the key of the entity instance
/// a list of rel-property expressions (lines up 1-1 with 'relPropertyList')
private IEnumerable BuildAllRelPropertyExpressions(EntitySetBase entitySet,
List relPropertyList,
Dictionary prebuiltExpressions,
Node keyExpr)
{
foreach (RelProperty r in relPropertyList)
{
Node relPropNode;
if (!prebuiltExpressions.TryGetValue(r, out relPropNode))
{
relPropNode = BuildRelPropertyExpression(entitySet, r, keyExpr);
}
yield return relPropNode;
}
}
///
/// Handler for NewEntityOp.
/// If this is an EntityConstructor, and the current view nesting level is 0
/// (ie) this is an EntityConstructor at the top-level query, then add
/// the type to the list of "free-floating" entity constructor types
///
/// the NewEntityOp
/// the node tree corresponding to the op
/// rewritten tree
public override Node Visit(NewEntityOp op, Node n)
{
//
// The default processing first
//
VisitScalarOpDefault(op, n);
md.EntityType entityType = op.Type.EdmType as md.EntityType;
md.EntitySetBase entitySet = FindEnclosingEntitySetView();
if (entitySet == null)
{
if (entityType != null)
{
m_freeFloatingEntityConstructorTypes.Add(entityType);
}
// SQLBUDT #546546: Qmv/Umv tests Assert and throws in plan compiler in association tests.
// If this Entity constructor is not within a view then there should not be any RelProps
// specified on the NewEntityOp - the eSQL WITH RELATIONSHIPS clause that would cause such
// RelProps to be added is only enabled when parsing in the user or generated view mode.
PlanCompiler.Assert(op.RelationshipProperties == null ||
op.RelationshipProperties.Count == 0,
"Related Entities cannot be specified for Entity constructors that are not part of the Query Mapping View for an Entity Set.");
return n;
}
//
// Find the relationship properties for this entitytype (and entity set)
//
List relProperties = new List(m_relPropertyHelper.GetRelProperties(entityType));
//
// Ok, now, I have to build out some relationship properties that
// haven't been specified
//
Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n);
//
// Find the list of rel properties that have already been specified
//
Dictionary prebuiltRelPropertyExprs = new Dictionary();
int j = 0;
for (int i = entityType.Properties.Count; i < n.Children.Count; i++, j++)
{
prebuiltRelPropertyExprs[op.RelationshipProperties[j]] = n.Children[i];
}
//
// Fill in the missing pieces
//
//
// Next, rebuild the list of children - includes expressions for each rel property
//
List newChildren = new List();
for (int i = 0; i < entityType.Properties.Count; i++)
{
newChildren.Add(n.Children[i]);
}
foreach (Node relPropNode in BuildAllRelPropertyExpressions(entitySet, relProperties, prebuiltRelPropertyExprs, keyExpr))
{
newChildren.Add(relPropNode);
}
//
// finally, build out the newOp
//
Op newEntityOp = m_command.CreateNewEntityOp(op.Type, relProperties, entitySet);
Node newNode = m_command.CreateNode(newEntityOp, newChildren);
return newNode;
}
///
/// Tracks discriminator metadata so that is can be used when constructing
/// StructuredTypeInfo.
///
public override Node Visit(DiscriminatedNewEntityOp op, Node n)
{
PlanCompiler.Assert(0 < m_viewNestingLevel, "DiscriminatedNewInstanceOp may appear only within view definition");
HashSet relPropertyHashSet = new HashSet();
List relProperties = new List();
//
// add references to each type produced by this node
// Also, get the set of rel-properties for each of the types
//
foreach (var discriminatorTypePair in op.DiscriminatorMap.TypeMap)
{
EntityTypeBase entityType = discriminatorTypePair.Value;
AddTypeReference(TypeUsage.Create(entityType));
foreach (RelProperty relProperty in m_relPropertyHelper.GetRelProperties(entityType))
{
relPropertyHashSet.Add(relProperty);
}
}
relProperties = new List(relPropertyHashSet);
VisitScalarOpDefault(op, n);
//
// Now build out the set of missing rel-properties (if any)
//
// first, build the key expression
Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n);
List newChildren = new List();
int firstRelPropertyNodeOffset = n.Children.Count - op.RelationshipProperties.Count;
for (int i = 0; i < firstRelPropertyNodeOffset; i++)
{
newChildren.Add(n.Children[i]);
}
//
// Find the list of rel properties that have already been specified
//
Dictionary prebuiltRelPropertyExprs = new Dictionary();
for (int i = firstRelPropertyNodeOffset, j =0; i < n.Children.Count; i++, j++ )
{
prebuiltRelPropertyExprs[op.RelationshipProperties[j]] = n.Children[i];
}
//
// Fill in the missing pieces
//
foreach (Node relPropNode in BuildAllRelPropertyExpressions(op.EntitySet, relProperties, prebuiltRelPropertyExprs, keyExpr))
{
newChildren.Add(relPropNode);
}
Op newEntityOp = m_command.CreateDiscriminatedNewEntityOp(op.Type, op.DiscriminatorMap, op.EntitySet, relProperties);
Node newNode = m_command.CreateNode(newEntityOp, newChildren);
return newNode;
}
///
/// Handles a newMultiset constructor. Converts this into
/// select a from dual union all select b from dual union all ...
/// Handles a NewMultiset constructor, i.e. {x, y, z}
/// 1. Empty multiset constructors are simply converted into:
///
/// select x from singlerowtable as x where false
///
/// 2. Mulltset constructors with only one element or with multiple elements all of
/// which are constants or nulls are converted into:
///
/// select x from dual union all select y from dual union all select z
///
/// 3. All others are converted into:
///
/// select case when d = 0 then x when d = 1 then y else z end
/// from ( select 0 as d from single_row_table
/// union all
/// select 1 as d from single_row_table
/// union all
/// select 2 as d from single_row_table )
///
/// NOTE: The translation for 2 is valid for 3 too. We choose different translation
/// in order to avoid correlation inside the union all,
/// which would prevent us from removing apply operators
///
/// Do this before processing the children, and then
/// call Visit on the result to handle the elements
///
/// the new instance op
/// the current subtree
/// the modified subtree
public override Node Visit(NewMultisetOp op, Node n)
{
Node resultNode = null;
Var resultVar = null;
md.CollectionType collectionType = TypeHelpers.GetEdmType(op.Type);
//
// Empty multiset constructors are simply converted into
// Project(Filter(SingleRowTableOp(), false)
//
if (!n.HasChild0)
{
Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
singleRowTableNode,
m_command.CreateNode(m_command.CreateFalseOp()));
Node fakeChild = m_command.CreateNode(m_command.CreateNullOp(collectionType.TypeUsage));
Var newVar;
Node projectNode = m_command.BuildProject(filterNode, fakeChild, out newVar);
resultNode = projectNode;
resultVar = newVar;
}
//
// Multiset constructors with only one elment or with multiple elments all of
// which are constants or nulls are converted into:
//
// UnionAll(Project(SingleRowTable, e1), Project(SingleRowTable, e2), ...)
//
// The degenerate case when the collection has only one element does not require an
// outer unionAll node
//
else if (n.Children.Count == 1 || AreAllConstantsOrNulls(n.Children))
{
List inputNodes = new List();
List inputVars = new List();
foreach (Node chi in n.Children)
{
Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
Var newVar;
Node projectNode = m_command.BuildProject(singleRowTableNode, chi, out newVar);
inputNodes.Add(projectNode);
inputVars.Add(newVar);
}
// Build the union-all ladder
m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar);
}
//
// All other cases:
//
// select case when d = 0 then x when d = 1 then y else z end
// from ( select 0 as d from single_row_table
// union all
// select 1 as d from single_row_table
// union all
// select 2 as d from single_row_table )
//
else
{
List inputNodes = new List();
List inputVars = new List();
//Create the union all lather first
for (int i = 0; i < n.Children.Count; i++)
{
Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
// the discriminator for this branch
Node discriminatorNode = m_command.CreateNode(m_command.CreateInternalConstantOp(m_command.IntegerType, i));
Var newVar;
Node projectNode = m_command.BuildProject(singleRowTableNode, discriminatorNode, out newVar);
inputNodes.Add(projectNode);
inputVars.Add(newVar);
}
// Build the union-all ladder now
m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar);
//Now create the case statement for the projection
List caseArgNodes = new List(n.Children.Count * 2 + 1);
for (int i = 0; i < n.Children.Count; i++)
{
//For all but the last we need a when
if (i != (n.Children.Count - 1))
{
ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ);
Node whenNode = m_command.CreateNode(equalsOp,
m_command.CreateNode(m_command.CreateVarRefOp(resultVar)),
m_command.CreateNode(
m_command.CreateConstantOp(m_command.IntegerType, i)));
caseArgNodes.Add(whenNode);
}
//Add the then/else node
caseArgNodes.Add(n.Children[i]);
}
//Create the project
Node caseNode = m_command.CreateNode(m_command.CreateCaseOp(collectionType.TypeUsage), caseArgNodes);
resultNode = m_command.BuildProject(resultNode, caseNode, out resultVar);
}
// So, I've finally built up a complex query corresponding to the constructor.
// Now, cap this with a physicalprojectOp, and then with a CollectOp
PhysicalProjectOp physicalProjectOp = m_command.CreatePhysicalProjectOp(resultVar);
Node physicalProjectNode = m_command.CreateNode(physicalProjectOp, resultNode);
CollectOp collectOp = m_command.CreateCollectOp(op.Type);
Node collectNode = m_command.CreateNode(collectOp, physicalProjectNode);
return VisitNode(collectNode);
}
///
/// Returns true if each node in the list is either a constant or a null
///
///
/// nodes)
{
foreach (Node node in nodes)
{
if (node.Op.OpType != OpType.Constant && node.Op.OpType != OpType.Null)
{
return false;
}
}
return true;
}
///
/// Default processing for a CollectOp. But make sure that we
/// go through the NestPullUp phase
///
///
///
///
/// Augments a node with a number of OuterApply's - one for each subquery
/// If S1, S2, ... are the list of subqueries for the node, and D is the
/// original (driver) input, we convert D into
/// OuterApply(OuterApply(D, S1), S2), ...
///
/// the input (driver) node
/// List of subqueries
/// should the input node be first in the apply chain, or the last?
/// The resulting node tree
private Node AugmentWithSubqueries(Node input, List subqueries, bool inputFirst)
{
Node newNode;
int subqueriesStartPos;
if (inputFirst)
{
newNode = input;
subqueriesStartPos = 0;
}
else
{
newNode = subqueries[0];
subqueriesStartPos = 1;
}
for (int i =subqueriesStartPos; i < subqueries.Count; i++)
{
OuterApplyOp op = m_command.CreateOuterApplyOp();
newNode = m_command.CreateNode(op, newNode, subqueries[i]);
}
if (!inputFirst)
{
newNode = m_command.CreateNode(m_command.CreateOuterApplyOp(), newNode, input);
}
// We may need to perform join elimination
m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination);
return newNode;
}
///
/// Default processing for RelOps.
/// - First, we mark the current node as its own ancestor (so that any
/// subqueries that we detect internally will be added to this node's list)
/// - then, visit each child
/// - finally, accumulate all nested subqueries.
/// - if the current RelOp has only one input, then add the nested subqueries via
/// Outer apply nodes to this input.
///
/// The interesting RelOps are
/// Project, Filter, GroupBy, Sort,
/// Should we break this out into separate functions instead?
///
/// Current RelOp
/// Node to process
/// Current subtree
protected override Node VisitRelOpDefault(RelOp op, Node n)
{
VisitChildren(n); // visit all my children first
// Then identify all the subqueries that have shown up as part of my node
// Create Apply Nodes for each of these.
List nestedSubqueries;
if (m_nodeSubqueries.TryGetValue(n, out nestedSubqueries) && nestedSubqueries.Count > 0)
{
// Validate - this must only apply to the following nodes
PlanCompiler.Assert(
n.Op.OpType == OpType.Project || n.Op.OpType == OpType.Filter ||
n.Op.OpType == OpType.GroupBy,
"VisitRelOpDefault: Unexpected op?" + n.Op.OpType);
Node newInputNode = AugmentWithSubqueries(n.Child0, nestedSubqueries, true);
// Now make this the new input child
n.Child0 = newInputNode;
}
return n;
}
private void HandleTableOpMetadata(ScanTableBaseOp op)
{
// add to the list of referenced entitysets
md.EntitySet entitySet = op.Table.TableMetadata.Extent as md.EntitySet;
if (entitySet != null)
{
AddEntitySetReference(entitySet);
}
md.TypeUsage elementType = TypeUsage.Create(op.Table.TableMetadata.Extent.ElementType);
// add to the list of structured types
AddTypeReference(elementType);
}
///
/// Visits a "table" expression - performs view expansion on the table (if appropriate),
/// and then some additional book-keeping.
///
/// The "ofType" and "includeSubtypes" parameters are optional hints for view expansion, allowing
/// for more customized (and hopefully, more optimal) views. The wasOfTypeSatisfied out parameter
/// tells whether the ofType filter was already handled by the view expansion, or if the caller still
/// needs to deal with it.
///
/// If the "table" is a C-space entityset, then we produce a ScanViewOp
/// tree with the defining query as the only child of the ScanViewOp
///
/// If the table is an S-space entityset, then we still produce a ScanViewOp, but this
/// time, we produce a simple "select * from BaseTable" as the defining
/// query
///
/// the scanTable node tree
/// the scanTableOp
///
/// An optional IsOfOp representing a type filter to apply to the scan table; will be set to null
/// if the scan target is expanded to a view that renders the type filter superfluous.
///
///
/// Processes a ScanTableOp - simply delegates to ProcessScanTableOp
///
/// the view op
/// current node tree
/// the transformed view-op
public override Node Visit(ScanTableOp op, Node n)
{
IsOfOp nullFilter = null;
return ProcessScanTable(n, op, ref nullFilter);
}
///
/// Visitor for a ScanViewOp
///
///
///
///
/// Processing for all JoinOps
///
/// JoinOp
/// Current subtree
/// nestedSubqueries;
if (m_nodeSubqueries.TryGetValue(n, out nestedSubqueries))
{
PlanCompiler.Assert(n.Op.OpType == OpType.InnerJoin ||
n.Op.OpType == OpType.LeftOuterJoin ||
n.Op.OpType == OpType.FullOuterJoin, "unexpected op?");
PlanCompiler.Assert(n.HasChild2, "missing second child to JoinOp?");
Node joinCondition = n.Child2;
Node inputNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
inputNode = AugmentWithSubqueries(inputNode, nestedSubqueries, true);
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), inputNode, joinCondition);
// update the join condition
// #479372: Build up a dummy project node over the input, as we always wrap the child of exists
Node projectNode = BuildDummyProjectForExists(filterNode);
Node existsNode = m_command.CreateNode(m_command.CreateExistsOp(), projectNode);
n.Child2 = existsNode;
}
return n;
}
///
/// Perform default relop processing; Also "require" the join-elimination phase
///
///
///
///
/// Visitor for UnnestOp. If the child has any subqueries, we need to convert this
/// into an
/// OuterApply(S, Unnest)
/// unlike the other cases where the OuterApply will appear as the input of the node
///
/// the unnestOp
/// current subtree
/// modified subtree
public override Node Visit(UnnestOp op, Node n)
{
VisitChildren(n); // visit all my children first
List nestedSubqueries;
if (m_nodeSubqueries.TryGetValue(n, out nestedSubqueries))
{
Node newNode = AugmentWithSubqueries(n, nestedSubqueries, false);
return newNode;
}
else
{
return n;
}
}
///
/// Can I eliminate this sort? I can, if the current path is *not* one of the
/// following
/// TopN(Sort)
/// PhysicalProject(Sort)
///
/// We don't yet handle the TopN variant
///
///
/// Visit a SortOp. Eliminate it if the path to this node is not one of
/// PhysicalProject(Sort) or
/// TopN(Sort)
///
/// Otherwise, simply visit the child RelOp
///
///
/// Current sortOp
/// current subtree
/// possibly transformed subtree
public override Node Visit(SortOp op, Node n)
{
// can I eliminate this sort
if (this.IsSortUnnecessary())
{
return VisitNode(n.Child0);
}
// perform default processing
return VisitRelOpDefault(op, n);
}
///
/// Checks to see if this filterOp represents an IS OF (or IS OF ONLY) filter over a ScanTableOp
///
/// the filterOp node
/// (OUT) the Type to restrict to
/// (OUT) was an ONLY clause specified
///
/// Handler for a FilterOp. Usually delegates to VisitRelOpDefault.
///
/// There's one special case - where we have an ISOF predicate over a ScanTable. In that case, we attempt
/// to get a more "optimal" view; and return that optimal view
///
///
/// the filterOp
/// the node tree
///
/// Visit a ProjectOp; if the input is a SortOp, we pullup the sort over
/// the ProjectOp to ensure that we don't have nested sorts;
///
///
///
/// sortChildren = new List();
sortChildren.Add(n);
//A ConstrainedSort has two other children besides the input and it needs to keep them.
for (int i = 1; i < n.Child0.Children.Count; i++)
{
sortChildren.Add(n.Child0.Children[i]);
}
// Replace the ProjectOp input (currently the Sort node) with the input to the Sort.
n.Child0 = n.Child0.Child0;
// Vars produced by the Sort input and used as SortKeys should be considered outputs
// of the ProjectOp that now operates over what was the Sort input.
foreach (SortKey key in sort.Keys)
{
op.Outputs.Set(key.Var);
}
// Finally, pull the Sort over the Project by creating a new Sort node with the original
// Sort as its Op and the Project node as its only child. This is sufficient because
// the ITreeGenerator ensures that the SortOp does not have any local VarDefs.
return VisitNode(m_command.CreateNode(sort, sortChildren));
}
// perform default processing
Node newNode = VisitRelOpDefault(op, n);
return newNode;
}
#endregion
#endregion
#endregion
}
///
/// Finds the record (Row) types that we're projecting out of the query, and
/// ensures that we mark them as needing a nullable sentinel, so when we
/// flatten them later we'll have one added.
///
internal class StructuredTypeNullabilityAnalyzer : ColumnMapVisitor>
{
static internal StructuredTypeNullabilityAnalyzer Instance = new StructuredTypeNullabilityAnalyzer();
///
/// VarRefColumnMap
///
///
///
/// typesNeedingNullSentinel)
{
AddTypeNeedingNullSentinel(typesNeedingNullSentinel, columnMap.Type);
base.Visit(columnMap, typesNeedingNullSentinel);
}
///
/// Recursively add any Row types to the list of types needing a sentinel.
///
///
///
private static void AddTypeNeedingNullSentinel(HashSet typesNeedingNullSentinel, TypeUsage typeUsage)
{
if (md.TypeSemantics.IsCollectionType(typeUsage))
{
AddTypeNeedingNullSentinel(typesNeedingNullSentinel, TypeHelpers.GetElementTypeUsage(typeUsage));
}
else
{
if (md.TypeSemantics.IsRowType(typeUsage) || md.TypeSemantics.IsComplexType(typeUsage))
{
MarkAsNeedingNullSentinel(typesNeedingNullSentinel, typeUsage);
}
foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(typeUsage))
{
AddTypeNeedingNullSentinel(typesNeedingNullSentinel, m.TypeUsage);
}
}
}
///
/// Marks the given typeUsage as needing a null sentinel.
/// Call this method instead of calling Add over the HashSet directly, to ensure consistency.
///
///
///
internal static void MarkAsNeedingNullSentinel(HashSet typesNeedingNullSentinel, TypeUsage typeUsage)
{
typesNeedingNullSentinel.Add(typeUsage.EdmType.Identity);
}
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....], [....]
//---------------------------------------------------------------------
using System;
using System.Collections.Generic;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Linq;
using System.Data.Common;
using md = System.Data.Metadata.Edm;
using System.Data.Query.InternalTrees;
using System.Data.Metadata.Edm;
using System.Data.Common.Utils;
//
// The PreProcessor module is responsible for performing any required preprocessing
// on the tree (and gathering information) before subsequent phases mess with the tree.
// The main aspects of preprocessing we perform here are
// (a) gathering information about all structured types and entitysets referenced in the
// query
// (b) Normalization of queries. Currently, we only handle scalar subqueries, and these
// are converted into outer-apply subqueries
// (c) Translation of multiset constructors into subqueries of the form
// "select a from dual union all select b from dual ..."
//
namespace System.Data.Query.PlanCompiler
{
internal class DiscriminatorMapInfo {
internal EntityTypeBase RootEntityType;
internal bool IncludesSubTypes;
internal ExplicitDiscriminatorMap DiscriminatorMap;
internal DiscriminatorMapInfo(EntityTypeBase rootEntityType, bool includesSubTypes, ExplicitDiscriminatorMap discriminatorMap)
{
RootEntityType = rootEntityType;
IncludesSubTypes = includesSubTypes;
DiscriminatorMap = discriminatorMap;
}
///
/// Merge the discriminatorMap info we just found with what we've already found.
///
/// In practice, if either the current or the new map is from an OfTypeOnly view, we
/// have to avoid the optimizations.
///
/// If we have a new map that is a superset of the current map, then we can just swap
/// the new map for the current one.
///
/// If the current map is tha super set of the new one ther's nothing to do.
///
/// (Of course, if neither has changed, then we really don't need to look)
///
internal void Merge(EntityTypeBase neededRootEntityType, bool includesSubtypes, ExplicitDiscriminatorMap discriminatorMap)
{
// If what we've found doesn't exactly match what we are looking for we have more work to do
if (RootEntityType != neededRootEntityType || IncludesSubTypes != includesSubtypes)
{
if (!IncludesSubTypes || !includesSubtypes)
{
// If either the original or the new map is from an of-type-only view we can't
// merge, we just have to not optimize this case.
DiscriminatorMap = null;
}
if (TypeSemantics.IsSubTypeOf(RootEntityType, neededRootEntityType))
{
// we're asking for a super type of existing type, and what we had is a proper
// subset of it -we can replace the existing item.
RootEntityType = neededRootEntityType;
DiscriminatorMap = discriminatorMap;
}
if (!TypeSemantics.IsSubTypeOf(neededRootEntityType, RootEntityType))
{
// If either the original or the new map is from an of-type-only view we can't
// merge, we just have to not optimize this case.
DiscriminatorMap = null;
}
}
}
}
///
/// The PreProcessor performs preprocessing of the ITree to facilitate processing
/// by later modules.
///
internal class PreProcessor : BasicOpVisitorOfNode
{
#region private state
private PlanCompiler m_compilerState;
private Command m_command { get { return m_compilerState.Command; } }
// nested subquery tracking
private Stack m_ancestors;
private Dictionary> m_nodeSubqueries;
// current nested view depth (0 for top-level query)
private int m_viewNestingLevel;
// track list of referenced types, entitysets and entitycontainers
private HashSet m_referencedEntityContainers;
private List m_referencedEntitySets;
private List m_referencedTypes;
private List m_freeFloatingEntityConstructorTypes;
private HashSet m_typesNeedingNullSentinel;
// helper for rel properties
private RelPropertyHelper m_relPropertyHelper;
// track discriminator metadata
private bool m_suppressDiscriminatorMaps;
private readonly Dictionary m_discriminatorMaps;
#endregion
#region constructors
private PreProcessor(PlanCompiler planCompilerState)
{
m_compilerState = planCompilerState;
m_ancestors = new Stack();
m_nodeSubqueries = new Dictionary>();
m_viewNestingLevel = 0;
m_referencedEntitySets = new List();
m_referencedTypes = new List();
m_freeFloatingEntityConstructorTypes = new List();
m_referencedEntityContainers = new HashSet();
m_relPropertyHelper = new RelPropertyHelper(m_command.MetadataWorkspace, m_command.ReferencedRelProperties);
m_discriminatorMaps = new Dictionary();
m_typesNeedingNullSentinel = new HashSet();
}
#endregion
#region public methods
///
/// The driver routine. "Normalizes" the command;
///
/// plan compiler state
/// type information about all types/sets referenced in the query
internal static void Process(PlanCompiler planCompilerState,
out StructuredTypeInfo typeInfo)
{
PreProcessor preProcessor = new PreProcessor(planCompilerState);
preProcessor.Process();
StructuredTypeInfo.Process(planCompilerState.Command,
preProcessor.m_referencedTypes,
preProcessor.m_referencedEntitySets,
preProcessor.m_freeFloatingEntityConstructorTypes,
preProcessor.m_suppressDiscriminatorMaps ? null : preProcessor.m_discriminatorMaps,
preProcessor.m_relPropertyHelper,
preProcessor.m_typesNeedingNullSentinel,
out typeInfo);
}
#endregion
#region private methods
#region driver
internal void Process()
{
m_command.Root = VisitNode(m_command.Root);
//
// Add any Vars that are of structured type - if the Vars aren't
// referenced via a VarRefOp, we end up losing them...
//
foreach (Var v in m_command.Vars)
{
AddTypeReference(v.Type);
}
//
// If we have any "structured" types, then we need to run through NTE
//
if (m_referencedTypes.Count > 0)
{
m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NTE);
//
// Find any structured types that are projected at the top level, and
// ensure that we can handle their nullability.
//
PhysicalProjectOp ppOp = (PhysicalProjectOp)m_command.Root.Op; // this better be the case or we have other problems.
ppOp.ColumnMap.Accept(StructuredTypeNullabilityAnalyzer.Instance, m_typesNeedingNullSentinel);
}
}
#endregion
#region private state maintenance
#region type and set information
///
/// Mark this EntitySet as referenced in the query
///
///
private void AddEntitySetReference(EntitySet entitySet)
{
m_referencedEntitySets.Add(entitySet);
if (!m_referencedEntityContainers.Contains(entitySet.EntityContainer))
{
m_referencedEntityContainers.Add(entitySet.EntityContainer);
}
}
///
/// Mark this type as being referenced in the query, if it is a structured
/// type or a collection of structured type
///
/// type to reference
private void AddTypeReference(TypeUsage type)
{
if (TypeUtils.IsStructuredType(type) || TypeUtils.IsCollectionType(type))
{
m_referencedTypes.Add(type);
}
}
///
/// Get the list of relationshipsets that can hold instances of the given relationshiptype
///
/// We identify the list of relationshipsets in the current list of entitycontainers that are
/// of the given type. Since we don't yet support relationshiptype subtyping, this is a little
/// easier than the entity version
///
/// the relationship type to look for
/// the list of relevant relationshipsets
private List GetRelationshipSets(RelationshipType relType)
{
List relSets = new List();
foreach (EntityContainer entityContainer in m_referencedEntityContainers)
{
foreach (EntitySetBase set in entityContainer.BaseEntitySets)
{
RelationshipSet relSet = set as RelationshipSet;
if (relSet != null &&
relSet.ElementType.Equals(relType))
{
relSets.Add(relSet);
}
}
}
return relSets;
}
///
/// Find all entitysets (that are reachable in the current query) that can hold instances that
/// are *at least* of type "entityType".
/// An entityset ES of type T1 can hold instances that are at least of type T2, if one of the following
/// is true
/// - T1 is a subtype of T2
/// - T2 is a subtype of T1
/// - T1 is equal to T2
///
/// the desired entity type
/// list of all entitysets of the desired shape
private List GetEntitySets(TypeUsage entityType)
{
List sets = new List();
foreach (EntityContainer container in m_referencedEntityContainers)
{
foreach (EntitySetBase baseSet in container.BaseEntitySets)
{
EntitySet set = baseSet as EntitySet;
if (set != null &&
(set.ElementType.Equals(entityType.EdmType) ||
TypeSemantics.IsSubTypeOf(entityType.EdmType, set.ElementType) ||
TypeSemantics.IsSubTypeOf(set.ElementType, entityType.EdmType)))
{
sets.Add(set);
}
}
}
return sets;
}
#endregion
#region Subquery Handling
///
/// Adds a subquery to the list of subqueries for the relOpNode
///
/// the RelOp node
/// the subquery
private void AddSubqueryToRelOpNode(Node relOpNode, Node subquery)
{
List nestedSubqueries;
// Create an entry in the map if there isn't one already
if (!m_nodeSubqueries.TryGetValue(relOpNode, out nestedSubqueries))
{
nestedSubqueries = new List();
m_nodeSubqueries[relOpNode] = nestedSubqueries;
}
// add this subquery to the list of currently tracked subqueries
nestedSubqueries.Add(subquery);
}
///
/// Add a subquery to the "parent" relop node
///
/// the output var to be used - at the current location - in lieu of the subquery
/// the subquery to move
/// a var ref node for the var returned from the subquery
private Node AddSubqueryToParentRelOp(Var outputVar, Node subquery)
{
Node ancestor = FindRelOpAncestor();
PlanCompiler.Assert(ancestor != null, "no ancestors found?");
AddSubqueryToRelOpNode(ancestor, subquery);
subquery = m_command.CreateNode(m_command.CreateVarRefOp(outputVar));
return subquery;
}
///
/// Find the first RelOp node that is in my ancestral path.
/// If I see a PhysicalOp, then I don't have a RelOp parent
///
/// the first RelOp node
private Node FindRelOpAncestor()
{
foreach (Node n in m_ancestors)
{
if (n.Op.IsRelOp)
{
return n;
}
else if (n.Op.IsPhysicalOp)
{
return null;
}
}
return null;
}
#endregion
#endregion
#region View Expansion
///
/// Gets the "defining" query for an S-Space entityset.
/// We simply convert this into
/// select Type(c1, c2, ...) from Set
///
/// A *key* assumption here is that the set is not polymorphic - otherwise, our smplistic
/// constructor model above does not suffice
///
/// current scan table node
/// the ScanTableOp
/// the defining query for this set
private Node GetDefiningQueryForSSpaceSet(Node node, ScanTableOp scanTableOp)
{
//
// We have an S-Space entityset. Build up a simple "select * from T"
// node tree on top of the base entityset
//
EntitySetBase entitySet = scanTableOp.Table.TableMetadata.Extent;
EntityType entityType = entitySet.ElementType as EntityType;
// For relationshipsets, do nothing
if (entityType != null)
{
Table baseTable = m_command.CreateTableInstance(scanTableOp.Table.TableMetadata);
ScanTableOp baseTableOp = m_command.CreateScanTableOp(baseTable);
Node baseTableNode = m_command.CreateNode(baseTableOp);
Var col = baseTable.Columns[0];
List constructorArgs = new List();
foreach (EdmProperty p in entityType.Properties)
{
Node arg = m_command.CreateNode(m_command.CreatePropertyOp(p),
m_command.CreateNode(m_command.CreateVarRefOp(col)));
constructorArgs.Add(arg);
}
Node constructor = m_command.CreateNode(
m_command.CreateNewInstanceOp(TypeUsage.Create(entityType)),
constructorArgs);
Var projectVar;
node = m_command.BuildProject(baseTableNode, constructor, out projectVar);
}
return node;
}
///
/// Convert a CQT command into an IQT subtree.
/// We expect the CQT command to be a query command tree. This is a 3-step
/// process
/// * We first run through the standard CQT-IQT convertor.
/// * We then strip off the root of the IQT (the PhysicalProjectOp)
/// * Finally, we copy the IQT into our current IQT
///
/// When we have metadata caching of IQTs (for views), instead of CQTs,
/// we can get rid of steps 1 and 2.
///
/// the view
/// an IQT subtree in the current command
private Node ConvertToInternalTree(System.Data.Mapping.ViewGeneration.GeneratedView generatedView)
{
Node ret;
Node sourceIqt = generatedView.GetInternalTree(m_command.MetadataWorkspace);
ret = OpCopier.Copy(m_command, sourceIqt);
return ret;
}
///
/// Gets the "expanded" query mapping view for the specified C-Space entity set
///
/// The current node
/// The scanTableOp that references the entity set
///
/// An optional type filter to apply to the generated view.
/// Set to null on return if the generated view renders the type filter superfluous.
///
/// A node that is the root of the new expanded view
private Node ExpandView(Node node, ScanTableOp scanTableOp, ref IsOfOp typeFilter)
{
EntitySetBase entitySet = scanTableOp.Table.TableMetadata.Extent;
PlanCompiler.Assert(entitySet != null, "The target of a ScanTableOp must reference an EntitySet to be used with ExpandView");
PlanCompiler.Assert(entitySet.EntityContainer.DataSpace == DataSpace.CSpace, "Store entity sets cannot have Query Mapping Views and should not be used with ExpandView");
if(typeFilter != null &&
!typeFilter.IsOfOnly &&
TypeSemantics.IsSubTypeOf(entitySet.ElementType, typeFilter.IsOfType.EdmType))
{
//
// If a type filter is being applied to the ScanTableOp, but that filter is asking
// for all elements that are the same type or a supertype of the element type of the
// target entity set, then the type filter is a no-op and can safely be discarded -
// IF AND ONLY IF the type filter is 'OfType' - which includes subtypes - and NOT
// 'IsOfOnly' - which requires an exact type match, and so does not include subtypes.
//
typeFilter = null;
}
//
// Call the GetGeneratedView method to retrieve the query mapping view for the extent referenced
// by the ScanTableOp. The actual method used to do this differs depending on whether the default
// Query Mapping View is sufficient or a targeted view that only filters by element type is required.
//
System.Data.Mapping.ViewGeneration.GeneratedView definingQuery = null;
EntityTypeBase requiredType = scanTableOp.Table.TableMetadata.Extent.ElementType;
bool includeSubtypes = true;
if(typeFilter != null)
{
//
// A type filter is being applied to the ScanTableOp; it may be possible to produce
// an optimized expansion of the view based on type-specific views generated for the
// C-Space entity set.
// The type for which the view should be tuned is the 'OfType' specified on the type filter.
// If the type filter is an 'IsOfOnly' filter then the view should NOT include subtypes of the required type.
//
requiredType = (EntityTypeBase)typeFilter.IsOfType.EdmType;
includeSubtypes = !typeFilter.IsOfOnly;
if(m_command.MetadataWorkspace.TryGetGeneratedViewOfType(entitySet, requiredType, includeSubtypes, out definingQuery))
{
//
// At this point a type-specific view was found that satisifies the type filter's
// constraints in terms of required type and whether subtypes should be included;
// the type filter itself is now unnecessary and should be set to null indicating
// that it can be safely removed (see ProcessScanTableOp and Visit(FilterOp) for this).
//
typeFilter = null;
}
}
//
// If a generated view has not been obtained at this point then either:
// - A type filter was specified but no type-specific view exists that satisfies its constraints.
// OR
// - No type filter was specified.
// In either case the default query mapping view for the referenced entity set should now be retrieved.
//
if(null == definingQuery)
{
definingQuery = m_command.MetadataWorkspace.GetGeneratedView(entitySet);
}
//
// If even the default query mapping view was not found then we cannot continue.
// This implies that the set was not mapped, which should not be allowed, therefore
// a retail assert is used here instead of a regular exception.
//
PlanCompiler.Assert(definingQuery != null, Entity.Strings.ADP_NoQueryMappingView(entitySet.EntityContainer.Name, entitySet.Name));
//
// At this point we're guaranteed to have found a defining query for the view.
// We're now going to convert this into an IQT, and then copy it into our own IQT.
//
Node ret = ConvertToInternalTree(definingQuery);
//
// Make sure we're tracking what we've asked any discriminator maps to contain.
//
DetermineDiscriminatorMapUsage(ret, entitySet, requiredType, includeSubtypes);
//
// Build up a ScanViewOp to "cap" the defining query below
//
ScanViewOp scanViewOp = m_command.CreateScanViewOp(scanTableOp.Table);
ret = m_command.CreateNode(scanViewOp, ret);
return ret;
}
///
/// If the discrminator map we're already tracking for this type (in this entityset)
/// isn't already rooted at our required type, then we have to suppress the use of
/// the descriminator maps when we constrct the structuredtypes; see SQLBUDT #615744
///
private void DetermineDiscriminatorMapUsage(Node viewNode, EntitySetBase entitySet, EntityTypeBase rootEntityType, bool includeSubtypes) {
ExplicitDiscriminatorMap discriminatorMap = null;
// we expect the view to be capped with a project; we're just being careful here.
if (viewNode.Op.OpType == OpType.Project)
{
DiscriminatedNewEntityOp discriminatedNewEntityOp = viewNode.Child1.Child0.Child0.Op as DiscriminatedNewEntityOp;
if (null != discriminatedNewEntityOp)
{
discriminatorMap = discriminatedNewEntityOp.DiscriminatorMap;
}
}
DiscriminatorMapInfo discriminatorMapInfo;
if (!m_discriminatorMaps.TryGetValue(entitySet, out discriminatorMapInfo))
{
if (null == rootEntityType)
{
rootEntityType = entitySet.ElementType;
includeSubtypes = true;
}
discriminatorMapInfo = new DiscriminatorMapInfo(rootEntityType, includeSubtypes, discriminatorMap);
m_discriminatorMaps.Add(entitySet, discriminatorMapInfo);
}
else
{
discriminatorMapInfo.Merge(rootEntityType, includeSubtypes, discriminatorMap);
}
}
#endregion
#region NavigateOp rewrites
///
/// Rewrites a NavigateOp tree in the following fashion
/// SELECT VALUE r.ToEnd
/// FROM (SELECT VALUE r1 FROM RS1 as r1
/// UNION ALL
/// SELECT VALUE r2 FROM RS2 as r2
/// ...
/// SELECT VALUE rN FROM RSN as rN) as r
/// WHERE r.FromEnd = sourceRef
///
/// RS1, RS2 etc. are the set of all relationshipsets that can hold instances of the specified
/// relationship type. "sourceRef" is the single (ref-type) argument to the NavigateOp that
/// represents the from-end of the navigation traversal
/// If the toEnd is multi-valued, then we stick a Collect(PhysicalProject( over the subquery above
///
/// A couple of special cases.
/// If no relationship sets can be found, we return a NULL (if the
/// toEnd is single-valued), or an empty multiset (if the toEnd is multi-valued)
///
/// If the toEnd is single-valued, *AND* the input Op is a GetEntityRefOp, then
/// we convert the NavigateOp into a RelPropertyOp over the entity.
///
/// the navigateOp tree
/// the navigateOp
/// the output var produced by the subquery (ONLY if the to-End is single-valued)
/// the resulting node
private Node RewriteNavigateOp(Node navigateOpNode, NavigateOp navigateOp, out Var outputVar)
{
outputVar = null;
//
// Currently, navigation of composition relationships is not supported.
//
if (!Helper.IsAssociationType(navigateOp.Relationship))
{
throw EntityUtil.NotSupported(System.Data.Entity.Strings.Cqt_RelNav_NoCompositions);
}
//
// If the input to the navigateOp is a GetEntityRefOp, and the navigation
// is to the 1-end of the relationship, convert this into a RelPropertyOp instead - operating on the
// input child to the GetEntityRefOp
//
if (navigateOpNode.Child0.Op.OpType == OpType.GetEntityRef &&
(navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne ||
navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One))
{
PlanCompiler.Assert(m_command.IsRelPropertyReferenced(navigateOp.RelProperty),
"Unreferenced rel property? " + navigateOp.RelProperty);
Op relPropertyOp = m_command.CreateRelPropertyOp(navigateOp.RelProperty);
Node relPropertyNode = m_command.CreateNode(relPropertyOp,
navigateOpNode.Child0.Child0);
return relPropertyNode;
}
List relationshipSets = GetRelationshipSets(navigateOp.Relationship);
//
// Special case: when no relationshipsets can be found. Return NULL or an empty multiset,
// depending on the multiplicity of the toEnd
//
if (relationshipSets.Count == 0)
{
//
// If we're navigating to the 1-end of the relationship, then simply return a null constant
//
if (navigateOp.ToEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many)
{
return m_command.CreateNode(m_command.CreateNullOp(navigateOp.Type));
}
else // return an empty set
{
return m_command.CreateNode(m_command.CreateNewMultisetOp(navigateOp.Type));
}
}
//
// Build up a UNION-ALL ladder over all the relationshipsets
//
List scanTableNodes = new List();
List scanTableVars = new List();
foreach (RelationshipSet relSet in relationshipSets)
{
TableMD tableMD = Command.CreateTableDefinition(relSet);
ScanTableOp tableOp = m_command.CreateScanTableOp(tableMD);
Node branchNode = m_command.CreateNode(tableOp);
Var branchVar = tableOp.Table.Columns[0];
scanTableVars.Add(branchVar);
scanTableNodes.Add(branchNode);
}
Node unionAllNode = null;
Var unionAllVar;
m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar);
//
// Now build up the predicate
//
Node targetEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.ToEnd),
m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar)));
Node sourceEnd = m_command.CreateNode(m_command.CreatePropertyOp(navigateOp.FromEnd),
m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar)));
Node predicateNode = m_command.BuildComparison(OpType.EQ, navigateOpNode.Child0, sourceEnd);
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
unionAllNode, predicateNode);
Var projectVar;
Node projectNode = m_command.BuildProject(filterNode, targetEnd, out projectVar);
//
// Finally, some magic about single-valued vs collection-valued ends
//
Node ret;
if (navigateOp.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many)
{
ret = m_command.BuildCollect(projectNode, projectVar);
}
else
{
ret = projectNode;
outputVar = projectVar;
}
return ret;
}
#endregion
#region DerefOp Rewrites
///
/// Build up a node tree that represents the set of instances from the given table that are at least
/// of the specified type ("ofType"). If "ofType" is NULL, then all rows are returned
///
/// Return the outputVar from the nodetree
///
/// the entityset or relationshipset to scan over
/// the element types we're interested in
/// the output var produced by this node tree
/// the node tree
private Node BuildOfTypeTable(EntitySetBase entitySet, TypeUsage ofType, out Var resultVar)
{
TableMD tableMetadata = Command.CreateTableDefinition(entitySet);
ScanTableOp tableOp = m_command.CreateScanTableOp(tableMetadata);
Node tableNode = m_command.CreateNode(tableOp);
Var tableVar = tableOp.Table.Columns[0];
Node resultNode;
//
// Build a logical "oftype" expression - simply a filter predicate
//
if ((ofType != null) && !entitySet.ElementType.EdmEquals(ofType.EdmType))
{
m_command.BuildOfTypeTree(tableNode, tableVar, ofType, true, out resultNode, out resultVar);
}
else
{
resultNode = tableNode;
resultVar = tableVar;
}
return resultNode;
}
///
/// Produces a relop tree that "logically" produces the target of the derefop. In essence, this gets rewritten
/// into
/// SELECT VALUE e
/// FROM (SELECT VALUE e0 FROM OFTYPE(ES0, T) as e0
/// UNION ALL
/// SELECT VALUE e1 FROM OFTYPE(ES1, T) as e1
/// ...
/// SELECT VALUE eN from OFTYPE(ESN, T) as eN)) as e
/// WHERE REF(e) = myRef
///
/// "T" is the target type of the Deref, and myRef is the (single) argument to the DerefOp
///
/// ES0, ES1 etc. are all the EntitySets that could hold instances that are at least of type "T". We identify this list of sets
/// by looking at all entitycontainers referenced in the query, and looking at all entitysets in those
/// containers that are of the right type
/// An EntitySet ES (of entity type X) can hold instances of T, if one of the following is true
/// - T is a subtype of X
/// - X is equal to T
/// Our situation is a little trickier, since we also need to look for cases where X is a subtype of T.
///
/// the derefOp subtree
/// the derefOp
/// output var produced
/// the subquery described above
private Node RewriteDerefOp(Node derefOpNode, DerefOp derefOp, out Var outputVar)
{
TypeUsage entityType = derefOp.Type;
List targetEntitySets = GetEntitySets(entityType);
if (targetEntitySets.Count == 0)
{
// We didn't find any entityset that could match this. Simply return a null-value
outputVar = null;
return m_command.CreateNode(m_command.CreateNullOp(entityType));
}
List scanTableNodes = new List();
List scanTableVars = new List();
foreach (EntitySet entitySet in targetEntitySets)
{
Var tableVar;
Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar);
scanTableNodes.Add(tableNode);
scanTableVars.Add(tableVar);
}
Node unionAllNode;
Var unionAllVar;
m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar);
//
// Finally build up the key comparison predicate
//
Node entityRefNode = m_command.CreateNode(
m_command.CreateGetEntityRefOp(derefOpNode.Child0.Op.Type),
m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar)));
Node keyComparisonPred = m_command.BuildComparison(OpType.EQ, derefOpNode.Child0, entityRefNode);
Node filterNode = m_command.CreateNode(
m_command.CreateFilterOp(),
unionAllNode,
keyComparisonPred);
outputVar = unionAllVar;
return filterNode;
}
#endregion
#region NavigationProperty Rewrites
///
/// Find the entityset that corresponds to the specified end of the relationship.
///
/// We must find one - else we assert.
///
/// the relationshipset
/// the destination end of the relationship traversal
/// the entityset corresponding to the target end
private static EntitySetBase FindTargetEntitySet(RelationshipSet relationshipSet, RelationshipEndMember targetEnd)
{
EntitySetBase entitySet = null;
AssociationSet associationSet = (AssociationSet)relationshipSet;
// find the corresponding entityset
entitySet = null;
foreach (AssociationSetEnd e in associationSet.AssociationSetEnds)
{
if (e.CorrespondingAssociationEndMember.EdmEquals(targetEnd))
{
entitySet = e.EntitySet;
break;
}
}
PlanCompiler.Assert(entitySet != null, "Could not find entityset for relationshipset " + relationshipSet + ";association end " + targetEnd);
return entitySet;
}
///
/// Builds up a join between the relationshipset and the entityset corresponding to its toEnd. In essence,
/// we produce
/// SELECT r, e
/// FROM RS as r, OFTYPE(ES, T) as e
/// WHERE r.ToEnd = Ref(e)
///
/// "T" is the entity type of the toEnd of the relationship.
///
/// the relationshipset
/// the toEnd of the relationship
/// the var representing the relationship instance ("r") in the output subquery
/// the var representing the entity instance ("e") in the output subquery
/// the join subquery described above
private Node BuildJoinForNavProperty(RelationshipSet relSet, RelationshipEndMember end,
out Var rsVar, out Var esVar)
{
EntitySetBase entitySet = FindTargetEntitySet(relSet, end);
//
// Build out the ScanTable ops for the relationshipset and the entityset. Add the
//
Node asTableNode = BuildOfTypeTable(relSet, null, out rsVar);
Node esTableNode = BuildOfTypeTable(entitySet, TypeHelpers.GetElementTypeUsage(end.TypeUsage), out esVar);
//
// Build up a join between the entityset and the associationset; join on the to-end
//
Node joinPredicate = m_command.BuildComparison(OpType.EQ,
m_command.CreateNode(m_command.CreateGetEntityRefOp(end.TypeUsage), m_command.CreateNode(m_command.CreateVarRefOp(esVar))),
m_command.CreateNode(m_command.CreatePropertyOp(end), m_command.CreateNode(m_command.CreateVarRefOp(rsVar)))
);
Node joinNode = m_command.CreateNode(m_command.CreateInnerJoinOp(),
asTableNode, esTableNode, joinPredicate);
return joinNode;
}
///
/// Rewrite a NavPropertyOp when the target end of the nav property has multiplicity
/// of one (or zero..one).
/// We simply pick up the corresponding rel property from the input entity, and
/// apply a deref operation
/// NavProperty(e, n) => deref(relproperty(e, r))
/// where e is the entity expression, n is the nav-property, and r is the corresponding
/// rel-property
///
/// the rel-property describing the navigation
/// entity instance that we're starting the traversal from
/// type of the target entity
/// a rewritten subtree
private Node RewriteToOneNavigationProperty(RelProperty relProperty,
Node sourceEntityNode, TypeUsage resultType)
{
RelPropertyOp relPropertyOp = m_command.CreateRelPropertyOp(relProperty);
Node relPropertyNode = m_command.CreateNode(relPropertyOp, sourceEntityNode);
DerefOp derefOp = m_command.CreateDerefOp(resultType);
Node derefNode = m_command.CreateNode(derefOp, relPropertyNode);
return derefNode;
}
///
/// Rewrite a NavigationProperty when the relationship is a 1:N relationship.
/// In essence, we find all the relevant target entitysets, and then compare the
/// rel-property on the target end with the source ref
///
/// Converts
/// NavigationProperty(e, r)
/// into
/// SELECT VALUE t
/// FROM (SELECT VALUE e1 FROM ES1 as e1
/// UNION ALL
/// SELECT VALUE e2 FROM ES2 as e2
/// UNION ALL
/// ...
/// ) as t
/// WHERE RelProperty(t, r') = GetEntityRef(e)
///
/// r' is the inverse-relproperty for r
///
/// We also build out a CollectOp over the subquery above, and return that
///
/// the rel-property describing the relationship traversal
/// the list of relevant relationshipsets
/// node tree corresponding to the source entity ref
/// type of the result
/// the rewritten subtree
private Node RewriteOneToManyNavigationProperty(RelProperty relProperty,
List relationshipSets,
Node sourceRefNode, TypeUsage resultType)
{
PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here");
PlanCompiler.Assert(relProperty.FromEnd.RelationshipMultiplicity != RelationshipMultiplicity.Many,
"Expected source end multiplicity to be one. Found 'Many' instead " + relProperty);
Node ret = null;
//
// We convert the
//
TypeUsage entityType = TypeHelpers.GetElementTypeUsage(relProperty.ToEnd.TypeUsage);
List scanTableNodes = new List(relationshipSets.Count);
List scanTableVars = new List(relationshipSets.Count);
foreach (RelationshipSet r in relationshipSets)
{
EntitySetBase entitySet = FindTargetEntitySet(r, relProperty.ToEnd);
Var tableVar;
Node tableNode = BuildOfTypeTable(entitySet, entityType, out tableVar);
scanTableNodes.Add(tableNode);
scanTableVars.Add(tableVar);
}
//
// Build the union-all node
//
Node unionAllNode;
Var unionAllVar;
m_command.BuildUnionAllLadder(scanTableNodes, scanTableVars, out unionAllNode, out unionAllVar);
//
// Now build up the appropriate filter. Select out the relproperty from the other end
//
RelProperty inverseRelProperty = new RelProperty(relProperty.Relationship, relProperty.ToEnd, relProperty.FromEnd);
PlanCompiler.Assert(m_command.IsRelPropertyReferenced(inverseRelProperty),
"Unreferenced rel property? " + inverseRelProperty);
Node inverseRelPropertyNode = m_command.CreateNode(
m_command.CreateRelPropertyOp(inverseRelProperty),
m_command.CreateNode(m_command.CreateVarRefOp(unionAllVar)));
Node predicateNode = m_command.BuildComparison(OpType.EQ,
sourceRefNode, inverseRelPropertyNode);
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
unionAllNode, predicateNode);
//
// The magic of collections...
//
ret = m_command.BuildCollect(filterNode, unionAllVar);
return ret;
}
///
/// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r))
/// where "r" is a many-to-many relationship
///
/// We essentially produce the following subquery
/// SELECT VALUE x.e
/// FROM (SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1)
/// UNION ALL
/// SELECT r1 as r, e1 as e FROM RS1 as r1 INNER JOIN OFTYPE(ES1, T) as e1 on r1.ToEnd = Ref(e1)
/// ...
/// ) as x
/// WHERE x.r.FromEnd = sourceRef
///
/// RS1, RS2 etc. are the relevant relationshipsets
/// ES1, ES2 etc. are the corresponding entitysets for the toEnd of the relationship
/// sourceRef is the ref argument
/// T is the type of the target-end of the relationship
///
/// We then build a CollectOp over the subquery above
///
/// the rel property to traverse
/// list of relevant relationshipsets
/// source ref
/// type of the result
/// relationshipSets,
Node sourceRefNode, TypeUsage resultType)
{
PlanCompiler.Assert(relationshipSets.Count > 0, "expected at least one relationshipset here");
PlanCompiler.Assert(relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many &&
relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many,
"Expected target end multiplicity to be 'many'. Found " + relProperty + "; multiplicity = " + relProperty.ToEnd.RelationshipMultiplicity);
Node ret = null;
List joinNodes = new List(relationshipSets.Count);
List outputVars = new List(relationshipSets.Count * 2);
foreach (RelationshipSet r in relationshipSets)
{
Var rsVar;
Var esVar;
Node joinNode = BuildJoinForNavProperty(r, relProperty.ToEnd, out rsVar, out esVar);
joinNodes.Add(joinNode);
outputVars.Add(rsVar);
outputVars.Add(esVar);
}
//
// Build the union-all node
//
Node unionAllNode;
IList unionAllVars;
m_command.BuildUnionAllLadder(joinNodes, outputVars, out unionAllNode, out unionAllVars);
//
// Now build out the filterOp over the left-side var
//
Node rsSourceRefNode = m_command.CreateNode(m_command.CreatePropertyOp(relProperty.FromEnd),
m_command.CreateNode(m_command.CreateVarRefOp(unionAllVars[0])));
Node predicate = m_command.BuildComparison(OpType.EQ,
sourceRefNode, rsSourceRefNode);
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
unionAllNode, predicate);
//
// Finally, build out a project node that only projects out the entity side
//
Node projectNode = m_command.BuildProject(filterNode, new Var[] { unionAllVars[1] }, new Node[] { });
//
// Build a collectOp over the project node
//
ret = m_command.BuildCollect(projectNode, unionAllVars[1]);
return ret;
}
///
/// Rewrite a NavProperty; more generally, consider this a rewrite of DEREF(NAVIGATE(r))
///
/// We handle three cases here, depending on the kind of relationship we're
/// dealing with.
/// - *:1 relationships
/// - N:1 relationships
/// - N:M relationships
///
///
/// the navigation property
/// the input ref to start the traversal
/// the result type of the expression
/// the rewritten tree
private Node RewriteNavigationProperty(NavigationProperty navProperty,
Node sourceEntityNode, TypeUsage resultType)
{
Node ret = null;
RelProperty relProperty = new RelProperty(navProperty.RelationshipType, navProperty.FromEndMember, navProperty.ToEndMember);
PlanCompiler.Assert(m_command.IsRelPropertyReferenced(relProperty) || (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many),
"Unreferenced rel property? " + relProperty);
//
// Case 1: The (target end of the) nav property has a multiplicity of 1 (or 0..1)
// (doesn't matter what the sourceEnd multiplicity is)
//
if (relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.One ||
relProperty.ToEnd.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne)
{
ret = RewriteToOneNavigationProperty(relProperty, sourceEntityNode, resultType);
return ret;
}
//
// Otherwise, the target end is multi-valued. We need to deal with
// 2 cases here. A N:1 relationship or a N:M relationship
//
//
// Find the list of all relationships that could satisfy this relationship
// If we find no matching relationship set, simply return an empty collection
//
List relationshipSets = GetRelationshipSets(relProperty.Relationship);
if (relationshipSets.Count == 0)
{
// return an empty set
return m_command.CreateNode(m_command.CreateNewMultisetOp(resultType));
}
//
// Build out a ref over the source entity now
//
Node sourceRefNode = m_command.CreateNode(
m_command.CreateGetEntityRefOp(relProperty.FromEnd.TypeUsage),
sourceEntityNode);
//
// Are we dealing with a many-to-many relationship ?
//
if (relProperty.FromEnd.RelationshipMultiplicity == RelationshipMultiplicity.Many)
{
ret = RewriteManyToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode, resultType);
}
else
{
ret = RewriteOneToManyNavigationProperty(relProperty, relationshipSets, sourceRefNode, resultType);
}
return ret;
}
#endregion
#region visitor helpers
///
/// Extends the base class implementation of VisitChildren.
/// Wraps the call to visitchildren() by first adding the current node
/// to the stack of "ancestors", and then popping back the node at the end
///
/// Current node
protected override void VisitChildren(Node n)
{
// Push the current node onto the stack
m_ancestors.Push(n);
for (int i = 0; i < n.Children.Count; i++)
{
n.Children[i] = VisitNode(n.Children[i]);
}
m_ancestors.Pop();
}
#endregion
#region visitor methods
#region ScalarOps
///
/// Default handler for scalar Ops. Simply traverses the children,
/// and also identifies any structured types along the way
///
/// the ScalarOp
/// current subtree
/// the possibly modified node
protected override Node VisitScalarOpDefault(ScalarOp op, Node n)
{
VisitChildren(n); // visit my children
// keep track of referenced types
AddTypeReference(op.Type);
return n;
}
///
/// Rewrite a DerefOp subtree. We have two cases to consider here.
/// We call RewriteDerefOp to return a subtree (and an optional outputVar).
/// If the outputVar is null, then we simply return the subtree produced by those calls.
/// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar
/// in its place.
///
/// As an example,
/// select deref(e) from T
/// gets rewritten into
/// select v from T OuterApply X
/// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X
///
///
/// the derefOp
/// the deref subtree
/// the rewritten tree
public override Node Visit(DerefOp op, Node n)
{
Var outputVar;
VisitScalarOpDefault(op, n);
Node ret = RewriteDerefOp(n, op, out outputVar);
ret = VisitNode(ret);
if (outputVar != null)
{
ret = AddSubqueryToParentRelOp(outputVar, ret);
}
return ret;
}
///
/// Processing for an ElementOp. Replaces this by the corresponding Var from
/// the subquery, and adds the subquery to the list of currently tracked subqueries
///
/// the elementOp
/// current subtree
/// the Var from the subquery
public override Node Visit(ElementOp op, Node n)
{
VisitScalarOpDefault(op, n); // default processing
// get to the subquery...
Node subQueryRelOp = n.Child0;
ProjectOp projectOp = (ProjectOp)subQueryRelOp.Op;
PlanCompiler.Assert(projectOp.Outputs.Count == 1, "input to ElementOp has more than one output var?");
Var projectVar = projectOp.Outputs.First;
Node ret = AddSubqueryToParentRelOp(projectVar, subQueryRelOp);
return ret;
}
///
/// Translate Exists(X) into Exists(select 0 from X)
///
///
///
///
/// Build Project(select 0 from child).
///
///
///
/// Build up an unnest above a scalar op node
/// X => unnest(X)
///
/// the scalarop collection node
/// the unnest node
private Node BuildUnnest(Node collectionNode)
{
PlanCompiler.Assert(collectionNode.Op.IsScalarOp, "non-scalar usage of Unnest?");
PlanCompiler.Assert(md.TypeSemantics.IsCollectionType(collectionNode.Op.Type), "non-collection usage for Unnest?");
Var newVar;
Node varDefNode = m_command.CreateVarDefNode(collectionNode, out newVar);
UnnestOp unnestOp = m_command.CreateUnnestOp(newVar);
Node unnestNode = m_command.CreateNode(unnestOp, varDefNode);
return unnestNode;
}
///
/// Is this function a TVF?
///
/// current function op
/// true, if the function returns a collection
private static bool IsCollectionFunction(FunctionOp op)
{
return md.TypeSemantics.IsCollectionType(op.Type);
}
///
/// Converts a reference to a TVF, by the following
/// Collect(PhysicalProject(Unnest(Func)))
///
/// current function op
/// current function subtree
/// the new expression that corresponds to the TVF
private Node VisitCollectionFunction(FunctionOp op, Node n)
{
PlanCompiler.Assert(IsCollectionFunction(op), "non-TVF function?");
Node unnestNode = BuildUnnest(n);
UnnestOp unnestOp = unnestNode.Op as UnnestOp;
PhysicalProjectOp projectOp = m_command.CreatePhysicalProjectOp(unnestOp.Table.Columns[0]);
Node projectNode = m_command.CreateNode(projectOp, unnestNode);
CollectOp collectOp = m_command.CreateCollectOp(n.Op.Type);
Node collectNode = m_command.CreateNode(collectOp, projectNode);
m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.NestPullup);
return collectNode;
}
///
/// Is this function a collection aggregate function. It is, if
/// - it has exactly one child
/// - that child is a collection type
/// - and the function has been marked with the aggregate attribute
///
/// the function op
/// the current subtree
/// true, if this was a collection aggregate function
private static bool IsCollectionAggregateFunction(FunctionOp op, Node n)
{
return ((n.Children.Count == 1) &&
md.TypeSemantics.IsCollectionType(n.Child0.Op.Type) &&
md.TypeSemantics.IsAggregateFunction(op.Function));
}
///
/// Converts a collection aggregate function count(X), where X is a collection into
/// two parts. Part A is a groupby subquery that looks like
/// GroupBy(Unnest(X), empty, count(y))
/// where "empty" describes the fact that the groupby has no keys, and y is an
/// element var of the Unnest
///
/// Part 2 is a VarRef that refers to the aggregate var for count(y) described above.
///
/// Logically, we would replace the entire functionOp by element(GroupBy...). However,
/// since we also want to translate element() into single-row-subqueries, we do this
/// here as well.
///
/// The function itself is replaced by the VarRef, and the GroupBy is added to the list
/// of scalar subqueries for the current relOp node on the stack
///
///
/// the functionOp for the collection agg
/// current subtree
/// the VarRef node that should replace the function
private Node VisitCollectionAggregateFunction(FunctionOp op, Node n)
{
md.TypeUsage softCastType = null;
Node argNode = n.Child0;
if (OpType.SoftCast == argNode.Op.OpType)
{
softCastType = TypeHelpers.GetEdmType(argNode.Op.Type).TypeUsage;
argNode = argNode.Child0;
while (OpType.SoftCast == argNode.Op.OpType)
{
argNode = argNode.Child0;
}
}
Node unnestNode = BuildUnnest(argNode);
UnnestOp unnestOp = unnestNode.Op as UnnestOp;
Var unnestOutputVar = unnestOp.Table.Columns[0];
AggregateOp aggregateOp = m_command.CreateAggregateOp(op.Function, false);
VarRefOp unnestVarRefOp = m_command.CreateVarRefOp(unnestOutputVar);
Node unnestVarRefNode = m_command.CreateNode(unnestVarRefOp);
if (softCastType != null)
{
unnestVarRefNode = m_command.CreateNode(m_command.CreateSoftCastOp(softCastType), unnestVarRefNode);
}
Node aggExprNode = m_command.CreateNode(aggregateOp, unnestVarRefNode);
VarVec keyVars = m_command.CreateVarVec(); // empty keys
Node keyVarDefListNode = m_command.CreateNode(m_command.CreateVarDefListOp());
VarVec gbyOutputVars = m_command.CreateVarVec();
Var aggVar;
Node aggVarDefListNode = m_command.CreateVarDefListNode(aggExprNode, out aggVar);
gbyOutputVars.Set(aggVar);
GroupByOp gbyOp = m_command.CreateGroupByOp(keyVars, gbyOutputVars);
Node gbySubqueryNode = m_command.CreateNode(gbyOp, unnestNode, keyVarDefListNode, aggVarDefListNode);
// "Move" this subquery to my parent relop
Node ret = AddSubqueryToParentRelOp(aggVar, gbySubqueryNode);
return ret;
}
///
/// Pre-processing for a function. Does the default thing. In addition, if the
/// function is a TVF (ie) returns a collection, convert this expression into
/// Nest(select value p from unnest(f) as p)
///
///
///
///
/// Default processing.
/// In addition, if the case statement is of the shape
/// case when X then NULL else Y, or
/// case when X then Y else NULL,
/// where Y is of row type and the types of the input CaseOp, the NULL and Y are the same,
/// marks that type as needing a null sentinel.
/// This allows in NominalTypeElimination the case op to be pushed inside Y's null sentinel.
///
///
///
///
/// If it is a IsNull op over a row type, mark the row type as needing a null sentinel.
///
///
///
///
/// Validates that the nav property agrees with the underlying relationship
///
/// the Nav PropertyOp
/// the subtree
private void ValidateNavPropertyOp(PropertyOp op, Node n)
{
NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo;
//
// If the result of the expanded form of the navigation property is not compatible with
// the declared type of the property, then the navigation property is invalid in the
// context of this command tree's metadata workspace.
//
md.TypeUsage resultType = navProperty.ToEndMember.TypeUsage;
if (TypeSemantics.IsReferenceType(resultType))
{
resultType = TypeHelpers.GetElementTypeUsage(resultType);
}
if (navProperty.ToEndMember.RelationshipMultiplicity == RelationshipMultiplicity.Many)
{
resultType = TypeUsage.Create(resultType.EdmType.GetCollectionType());
}
if (!TypeSemantics.IsEquivalentOrPromotableTo(resultType, op.Type))
{
throw EntityUtil.Metadata(System.Data.Entity.Strings.EntityClient_IncompatibleNavigationPropertyResult(
navProperty.DeclaringType.FullName,
navProperty.Name
)
);
}
}
///
/// Rewrite a PropertyOp subtree for a nav property
///
/// We call RewriteNavigationPropertyOp to return a subtree (and an
/// optional outputVar). If the outputVar is null, then we simply return the subtree produced by those calls.
/// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar
/// in its place.
///
/// As an example,
/// select e.NP from T
/// gets rewritten into
/// select v from T OuterApply X
/// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X
///
/// the PropertyOp
/// the current node
/// the rewritten subtree
private Node VisitNavPropertyOp(PropertyOp op, Node n)
{
ValidateNavPropertyOp(op, n);
//
// This is a bit weird. Ideally, I would always visit the child first (ie) a bottom-up traversal,
// but there's some weird gotchas in the elinq tests ("SelectManyNullResult531057")
//
bool visitChildFirst = (n.Child0.Op.OpType != OpType.Property);
if (visitChildFirst)
{
VisitScalarOpDefault(op, n);
}
NavigationProperty navProperty = (NavigationProperty)op.PropertyInfo;
Node ret = RewriteNavigationProperty(navProperty, n.Child0, op.Type);
ret = VisitNode(ret);
return ret;
}
///
/// Rewrite a PropertyOp subtree.
///
/// If the PropertyOp represents a simple property (ie) not a navigation property, we simply call
/// VisitScalarOpDefault() and return. Otherwise, we call VisitNavPropertyOp and return the result from
/// that function
///
///
/// the PropertyOp
/// the PropertyOp subtree
/// the rewritten tree
public override Node Visit(PropertyOp op, Node n)
{
Node ret;
if (Helper.IsNavigationProperty(op.PropertyInfo))
{
ret = VisitNavPropertyOp(op, n);
}
else
{
ret = VisitScalarOpDefault(op, n);
}
return ret;
}
#endregion
///
/// Handler for a RefOp.
/// Keeps track of the entityset
///
/// the RefOp
/// current RefOp subtree
/// current subtree
public override Node Visit(RefOp op, Node n)
{
VisitScalarOpDefault(op, n); // use default processing
AddEntitySetReference(op.EntitySet); // add to list of references
return n;
}
///
/// Handler for a TreatOp.
/// Rewrites the operator if the argument is guaranteed to be of type
/// op.
///
/// Current TreatOp
/// Current subtree
/// Current subtree
public override Node Visit(TreatOp op, Node n)
{
n = base.Visit(op, n);
// See if TreatOp can be rewritten (if it's not polymorphic)
if (CanRewriteTypeTest(op.Type.EdmType, n.Child0.Op.Type.EdmType))
{
// Return argument directly (if the argument is null, 'treat as' also returns null;
// if the argument is not null, it's guaranteed to be of the correct type)
return n.Child0;
}
return n;
}
///
/// Handler for an IsOfOp.
/// Keeps track of the IsOfType (if it is a structured type) and rewrites the
/// operator if the argument is guaranteed to be of type op.IsOfType
///
/// Current IsOfOp
/// Current subtree
/// Current subtree
public override Node Visit(IsOfOp op, Node n)
{
n = VisitScalarOpDefault(op, n); // default handling first
// keep track of any structured types
AddTypeReference(op.IsOfType);
// See if the IsOfOp can be rewritten (if it's not polymorphic)
if (CanRewriteTypeTest(op.IsOfType.EdmType, n.Child0.Op.Type.EdmType))
{
n = RewriteIsOfAsIsNull(op, n);
}
// For IsOfOnly(abstract type), suppress DiscriminatorMaps since no explicit type id is available for
// abstract types.
if (op.IsOfOnly && op.IsOfType.EdmType.Abstract)
{
m_suppressDiscriminatorMaps = true;
}
return n;
}
// Determines whether a type test expression can be rewritten. Returns true of the
// argument type is guaranteed to implement "testType" (if the argument is non-null).
private bool CanRewriteTypeTest(EdmType testType, EdmType argumentType)
{
// The rewrite only proceeds if the types are the same. If they are not,
// it suggests either that the input result is polymorphic (in which case if OfType
// should be preserved) or the types are incompatible (which is caught
// elsewhere)
if (!testType.EdmEquals(argumentType))
{
return false;
}
// If the IsOfType is non-polymorphic (no base or derived types) the rewrite
// is possible.
if (null != testType.BaseType)
{
return false;
}
// Count sub types
int subTypeCount = 0;
foreach (EdmType subType in MetadataHelper.GetTypeAndSubtypesOf(testType, m_command.MetadataWorkspace, true /*includeAbstractTypes*/))
{
subTypeCount++;
if (2 == subTypeCount) { break; }
}
return 1 == subTypeCount; // no children types
}
// Translates
// 'R is of T'
// to
// '(case when not (R is null) then True else null end) = True'
//
// Input requirements:
//
// - IsOfOp and argument to same must be in the same hierarchy.
// - IsOfOp and argument must have the same type
// - IsOfOp.IsOfType may not have super- or sub- types (validate
// using CanRewriteTypeTest)
//
// Design requirements:
//
// - Must return true if the record exists
// - Must return null if it does not
// - Must be in predicate form to avoid confusing SQL gen
//
// The translation assumes R is of T when R is non null.
private Node RewriteIsOfAsIsNull(IsOfOp op, Node n)
{
// construct 'R is null' predicate
ConditionalOp isNullOp = m_command.CreateConditionalOp(OpType.IsNull);
Node isNullNode = m_command.CreateNode(isNullOp, n.Child0);
// construct 'not (R is null)' predicate
ConditionalOp notOp = m_command.CreateConditionalOp(OpType.Not);
Node notNode = m_command.CreateNode(notOp, isNullNode);
// construct 'True' result
ConstantBaseOp trueOp = m_command.CreateConstantOp(op.Type, true);
Node trueNode = m_command.CreateNode(trueOp);
// construct 'null' default result
NullOp nullOp = m_command.CreateNullOp(op.Type);
Node nullNode = m_command.CreateNode(nullOp);
// create case statement
CaseOp caseOp = m_command.CreateCaseOp(op.Type);
Node caseNode = m_command.CreateNode(caseOp, notNode, trueNode, nullNode);
// create 'case = true' operator
ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ);
Node equalsNode = m_command.CreateNode(equalsOp, caseNode, trueNode);
return equalsNode;
}
///
/// Rewrite a NavigateOp subtree.
/// We call RewriteNavigateOp to return a subtree (and an optional outputVar).
/// If the outputVar is null, then we simply return the subtree produced by those calls.
/// Otherwise, we add the subtree to the "parent" relop (to be outer-applied), and then use the outputVar
/// in its place.
///
/// As an example,
/// select navigate(e) from T
/// gets rewritten into
/// select v from T OuterApply X
/// where X is the subtree returned from the RewriteXXX calls, and "v" is the output var produced by X
///
///
/// the navigateOp
/// the navigateOp subtree
/// the rewritten tree
public override Node Visit(NavigateOp op, Node n)
{
VisitScalarOpDefault(op, n);
Var outputVar;
Node ret = RewriteNavigateOp(n, op, out outputVar);
ret = VisitNode(ret);
// Move subquery to parent relop if necessary
if (outputVar != null)
{
ret = AddSubqueryToParentRelOp(outputVar, ret);
}
return ret;
}
///
/// Find the "current" enclosing entityset
///
/// the enclosing entityset (if any)
private EntitySetBase FindEnclosingEntitySetView()
{
if (m_viewNestingLevel == 0)
{
return null;
}
//
// Walk up the stack of ancestors until we find the appropriate ScanViewOp
//
foreach (Node n in m_ancestors)
{
if (n.Op.OpType == OpType.ScanView)
{
ScanViewOp op = (ScanViewOp)n.Op;
return op.Table.TableMetadata.Extent;
}
}
PlanCompiler.Assert(false, "found no enclosing view - but view-nesting level is greater than zero");
return null;
}
///
/// Find the relationshipset that matches the current entityset + from/to roles
///
///
///
///
/// Find the position of a property in a type.
/// Positions start at zero, and a supertype's properties precede the current
/// type's properties
///
/// the type in question
/// the member to lookup
/// the position of the member in the type (0-based)
private int FindPosition(EdmType type, EdmMember member)
{
int pos = 0;
foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(type))
{
if (m.EdmEquals(member))
{
return pos;
}
pos++;
}
PlanCompiler.Assert(false, "Could not find property " + member + " in type " + type.Name);
return -1;
}
///
/// Build out an expression (NewRecord) that corresponds to the key properties
/// of the passed-in entity constructor
///
/// This function simply looks up the key properties of the entity type, and then
/// identifies the arguments to the constructor corresponding to those
/// properties, and then slaps on a record wrapper over those expressions.
///
/// No copies/clones are performed. That's the responsibility of the caller
///
///
/// the entity constructor op
/// the corresponding subtree
/// the key expression
private Node BuildKeyExpressionForNewEntityOp(Op op, Node n)
{
PlanCompiler.Assert(op.OpType == OpType.NewEntity || op.OpType == OpType.DiscriminatedNewEntity,
"BuildKeyExpression: Unexpected OpType:" + op.OpType);
int offset = (op.OpType == OpType.DiscriminatedNewEntity) ? 1 : 0;
EntityTypeBase entityType = (EntityTypeBase)op.Type.EdmType;
List keyFields = new List();
List> keyFieldTypes = new List>();
foreach (EdmMember k in entityType.KeyMembers)
{
int pos = FindPosition(entityType, k) + offset;
PlanCompiler.Assert(n.Children.Count > pos, "invalid position " + pos + "; total count = " + n.Children.Count);
keyFields.Add(n.Children[pos]);
keyFieldTypes.Add(new KeyValuePair(k.Name, k.TypeUsage));
}
TypeUsage keyExprType = TypeHelpers.CreateRowTypeUsage(keyFieldTypes, true);
NewRecordOp keyOp = m_command.CreateNewRecordOp(keyExprType);
Node keyNode = m_command.CreateNode(keyOp, keyFields);
return keyNode;
}
///
/// Build out an expression corresponding to the rel-property.
///
/// We create a subquery that looks like
/// (select r
/// from RS r
/// where GetRefKey(r.FromEnd) = myKey)
///
/// RS is the single relationship set that corresponds to the given entityset/rel-property pair
/// FromEnd - is the source end of the relationship
/// myKey - is the key expression of the entity being constructed
///
/// NOTE: We always clone "myKey" before use.
///
/// We then convert it into a scalar subquery, and extract out the ToEnd property from
/// the output var of the subquery. (Should we do this inside the subquery itself?)
///
/// If no single relationship-set is found, we return a NULL instead.
///
/// entity set that logically holds instances of the entity we're building
/// the rel-property we're trying to build up
/// the "key" of the entity instance
/// the rel-property expression
private Node BuildRelPropertyExpression(EntitySetBase entitySet, RelProperty relProperty,
Node keyExpr)
{
//
// Make a copy of the current key expression
//
keyExpr = OpCopier.Copy(m_command, keyExpr);
//
// Find the relationship set corresponding to this entityset (and relProperty)
// Return a null ref, if we can't find one
//
RelationshipSet relSet = FindRelationshipSet(entitySet, relProperty);
if (relSet == null)
{
return m_command.CreateNode(m_command.CreateNullOp(relProperty.ToEnd.TypeUsage));
}
ScanTableOp scanTableOp = m_command.CreateScanTableOp(Command.CreateTableDefinition(relSet));
PlanCompiler.Assert(scanTableOp.Table.Columns.Count == 1,
"Unexpected column count for table:" + scanTableOp.Table.TableMetadata.Extent + "=" + scanTableOp.Table.Columns.Count);
Var scanTableVar = scanTableOp.Table.Columns[0];
Node scanNode = m_command.CreateNode(scanTableOp);
Node sourceEndNode = m_command.CreateNode(
m_command.CreatePropertyOp(relProperty.FromEnd),
m_command.CreateNode(m_command.CreateVarRefOp(scanTableVar)));
Node predicateNode = m_command.BuildComparison(OpType.EQ,
keyExpr,
m_command.CreateNode(m_command.CreateGetRefKeyOp(keyExpr.Op.Type), sourceEndNode));
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
scanNode, predicateNode);
//
// Process the node, and then add this as a subquery to the parent relop
//
Node ret = VisitNode(filterNode);
ret = AddSubqueryToParentRelOp(scanTableVar, ret);
//
// Now extract out the target end property
//
ret = m_command.CreateNode(
m_command.CreatePropertyOp(relProperty.ToEnd),
ret);
return ret;
}
///
/// Given an entity constructor (NewEntityOp, DiscriminatedNewEntityOp), build up
/// the list of rel-property expressions.
///
/// Walks through the list of relevant rel-properties, and builds up expressions
/// (using BuildRelPropertyExpression) for each rel-property that does not have
/// an expression already built (preBuiltExpressions)
///
/// entity set that holds instances of the entity we're building
/// the list of relevant rel-properties for this entity type
/// the prebuilt rel-property expressions
/// the key of the entity instance
/// a list of rel-property expressions (lines up 1-1 with 'relPropertyList')
private IEnumerable BuildAllRelPropertyExpressions(EntitySetBase entitySet,
List relPropertyList,
Dictionary prebuiltExpressions,
Node keyExpr)
{
foreach (RelProperty r in relPropertyList)
{
Node relPropNode;
if (!prebuiltExpressions.TryGetValue(r, out relPropNode))
{
relPropNode = BuildRelPropertyExpression(entitySet, r, keyExpr);
}
yield return relPropNode;
}
}
///
/// Handler for NewEntityOp.
/// If this is an EntityConstructor, and the current view nesting level is 0
/// (ie) this is an EntityConstructor at the top-level query, then add
/// the type to the list of "free-floating" entity constructor types
///
/// the NewEntityOp
/// the node tree corresponding to the op
/// rewritten tree
public override Node Visit(NewEntityOp op, Node n)
{
//
// The default processing first
//
VisitScalarOpDefault(op, n);
md.EntityType entityType = op.Type.EdmType as md.EntityType;
md.EntitySetBase entitySet = FindEnclosingEntitySetView();
if (entitySet == null)
{
if (entityType != null)
{
m_freeFloatingEntityConstructorTypes.Add(entityType);
}
// SQLBUDT #546546: Qmv/Umv tests Assert and throws in plan compiler in association tests.
// If this Entity constructor is not within a view then there should not be any RelProps
// specified on the NewEntityOp - the eSQL WITH RELATIONSHIPS clause that would cause such
// RelProps to be added is only enabled when parsing in the user or generated view mode.
PlanCompiler.Assert(op.RelationshipProperties == null ||
op.RelationshipProperties.Count == 0,
"Related Entities cannot be specified for Entity constructors that are not part of the Query Mapping View for an Entity Set.");
return n;
}
//
// Find the relationship properties for this entitytype (and entity set)
//
List relProperties = new List(m_relPropertyHelper.GetRelProperties(entityType));
//
// Ok, now, I have to build out some relationship properties that
// haven't been specified
//
Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n);
//
// Find the list of rel properties that have already been specified
//
Dictionary prebuiltRelPropertyExprs = new Dictionary();
int j = 0;
for (int i = entityType.Properties.Count; i < n.Children.Count; i++, j++)
{
prebuiltRelPropertyExprs[op.RelationshipProperties[j]] = n.Children[i];
}
//
// Fill in the missing pieces
//
//
// Next, rebuild the list of children - includes expressions for each rel property
//
List newChildren = new List();
for (int i = 0; i < entityType.Properties.Count; i++)
{
newChildren.Add(n.Children[i]);
}
foreach (Node relPropNode in BuildAllRelPropertyExpressions(entitySet, relProperties, prebuiltRelPropertyExprs, keyExpr))
{
newChildren.Add(relPropNode);
}
//
// finally, build out the newOp
//
Op newEntityOp = m_command.CreateNewEntityOp(op.Type, relProperties, entitySet);
Node newNode = m_command.CreateNode(newEntityOp, newChildren);
return newNode;
}
///
/// Tracks discriminator metadata so that is can be used when constructing
/// StructuredTypeInfo.
///
public override Node Visit(DiscriminatedNewEntityOp op, Node n)
{
PlanCompiler.Assert(0 < m_viewNestingLevel, "DiscriminatedNewInstanceOp may appear only within view definition");
HashSet relPropertyHashSet = new HashSet();
List relProperties = new List();
//
// add references to each type produced by this node
// Also, get the set of rel-properties for each of the types
//
foreach (var discriminatorTypePair in op.DiscriminatorMap.TypeMap)
{
EntityTypeBase entityType = discriminatorTypePair.Value;
AddTypeReference(TypeUsage.Create(entityType));
foreach (RelProperty relProperty in m_relPropertyHelper.GetRelProperties(entityType))
{
relPropertyHashSet.Add(relProperty);
}
}
relProperties = new List(relPropertyHashSet);
VisitScalarOpDefault(op, n);
//
// Now build out the set of missing rel-properties (if any)
//
// first, build the key expression
Node keyExpr = BuildKeyExpressionForNewEntityOp(op, n);
List newChildren = new List();
int firstRelPropertyNodeOffset = n.Children.Count - op.RelationshipProperties.Count;
for (int i = 0; i < firstRelPropertyNodeOffset; i++)
{
newChildren.Add(n.Children[i]);
}
//
// Find the list of rel properties that have already been specified
//
Dictionary prebuiltRelPropertyExprs = new Dictionary();
for (int i = firstRelPropertyNodeOffset, j =0; i < n.Children.Count; i++, j++ )
{
prebuiltRelPropertyExprs[op.RelationshipProperties[j]] = n.Children[i];
}
//
// Fill in the missing pieces
//
foreach (Node relPropNode in BuildAllRelPropertyExpressions(op.EntitySet, relProperties, prebuiltRelPropertyExprs, keyExpr))
{
newChildren.Add(relPropNode);
}
Op newEntityOp = m_command.CreateDiscriminatedNewEntityOp(op.Type, op.DiscriminatorMap, op.EntitySet, relProperties);
Node newNode = m_command.CreateNode(newEntityOp, newChildren);
return newNode;
}
///
/// Handles a newMultiset constructor. Converts this into
/// select a from dual union all select b from dual union all ...
/// Handles a NewMultiset constructor, i.e. {x, y, z}
/// 1. Empty multiset constructors are simply converted into:
///
/// select x from singlerowtable as x where false
///
/// 2. Mulltset constructors with only one element or with multiple elements all of
/// which are constants or nulls are converted into:
///
/// select x from dual union all select y from dual union all select z
///
/// 3. All others are converted into:
///
/// select case when d = 0 then x when d = 1 then y else z end
/// from ( select 0 as d from single_row_table
/// union all
/// select 1 as d from single_row_table
/// union all
/// select 2 as d from single_row_table )
///
/// NOTE: The translation for 2 is valid for 3 too. We choose different translation
/// in order to avoid correlation inside the union all,
/// which would prevent us from removing apply operators
///
/// Do this before processing the children, and then
/// call Visit on the result to handle the elements
///
/// the new instance op
/// the current subtree
/// the modified subtree
public override Node Visit(NewMultisetOp op, Node n)
{
Node resultNode = null;
Var resultVar = null;
md.CollectionType collectionType = TypeHelpers.GetEdmType(op.Type);
//
// Empty multiset constructors are simply converted into
// Project(Filter(SingleRowTableOp(), false)
//
if (!n.HasChild0)
{
Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(),
singleRowTableNode,
m_command.CreateNode(m_command.CreateFalseOp()));
Node fakeChild = m_command.CreateNode(m_command.CreateNullOp(collectionType.TypeUsage));
Var newVar;
Node projectNode = m_command.BuildProject(filterNode, fakeChild, out newVar);
resultNode = projectNode;
resultVar = newVar;
}
//
// Multiset constructors with only one elment or with multiple elments all of
// which are constants or nulls are converted into:
//
// UnionAll(Project(SingleRowTable, e1), Project(SingleRowTable, e2), ...)
//
// The degenerate case when the collection has only one element does not require an
// outer unionAll node
//
else if (n.Children.Count == 1 || AreAllConstantsOrNulls(n.Children))
{
List inputNodes = new List();
List inputVars = new List();
foreach (Node chi in n.Children)
{
Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
Var newVar;
Node projectNode = m_command.BuildProject(singleRowTableNode, chi, out newVar);
inputNodes.Add(projectNode);
inputVars.Add(newVar);
}
// Build the union-all ladder
m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar);
}
//
// All other cases:
//
// select case when d = 0 then x when d = 1 then y else z end
// from ( select 0 as d from single_row_table
// union all
// select 1 as d from single_row_table
// union all
// select 2 as d from single_row_table )
//
else
{
List inputNodes = new List();
List inputVars = new List();
//Create the union all lather first
for (int i = 0; i < n.Children.Count; i++)
{
Node singleRowTableNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
// the discriminator for this branch
Node discriminatorNode = m_command.CreateNode(m_command.CreateInternalConstantOp(m_command.IntegerType, i));
Var newVar;
Node projectNode = m_command.BuildProject(singleRowTableNode, discriminatorNode, out newVar);
inputNodes.Add(projectNode);
inputVars.Add(newVar);
}
// Build the union-all ladder now
m_command.BuildUnionAllLadder(inputNodes, inputVars, out resultNode, out resultVar);
//Now create the case statement for the projection
List caseArgNodes = new List(n.Children.Count * 2 + 1);
for (int i = 0; i < n.Children.Count; i++)
{
//For all but the last we need a when
if (i != (n.Children.Count - 1))
{
ComparisonOp equalsOp = m_command.CreateComparisonOp(OpType.EQ);
Node whenNode = m_command.CreateNode(equalsOp,
m_command.CreateNode(m_command.CreateVarRefOp(resultVar)),
m_command.CreateNode(
m_command.CreateConstantOp(m_command.IntegerType, i)));
caseArgNodes.Add(whenNode);
}
//Add the then/else node
caseArgNodes.Add(n.Children[i]);
}
//Create the project
Node caseNode = m_command.CreateNode(m_command.CreateCaseOp(collectionType.TypeUsage), caseArgNodes);
resultNode = m_command.BuildProject(resultNode, caseNode, out resultVar);
}
// So, I've finally built up a complex query corresponding to the constructor.
// Now, cap this with a physicalprojectOp, and then with a CollectOp
PhysicalProjectOp physicalProjectOp = m_command.CreatePhysicalProjectOp(resultVar);
Node physicalProjectNode = m_command.CreateNode(physicalProjectOp, resultNode);
CollectOp collectOp = m_command.CreateCollectOp(op.Type);
Node collectNode = m_command.CreateNode(collectOp, physicalProjectNode);
return VisitNode(collectNode);
}
///
/// Returns true if each node in the list is either a constant or a null
///
///
/// nodes)
{
foreach (Node node in nodes)
{
if (node.Op.OpType != OpType.Constant && node.Op.OpType != OpType.Null)
{
return false;
}
}
return true;
}
///
/// Default processing for a CollectOp. But make sure that we
/// go through the NestPullUp phase
///
///
///
///
/// Augments a node with a number of OuterApply's - one for each subquery
/// If S1, S2, ... are the list of subqueries for the node, and D is the
/// original (driver) input, we convert D into
/// OuterApply(OuterApply(D, S1), S2), ...
///
/// the input (driver) node
/// List of subqueries
/// should the input node be first in the apply chain, or the last?
/// The resulting node tree
private Node AugmentWithSubqueries(Node input, List subqueries, bool inputFirst)
{
Node newNode;
int subqueriesStartPos;
if (inputFirst)
{
newNode = input;
subqueriesStartPos = 0;
}
else
{
newNode = subqueries[0];
subqueriesStartPos = 1;
}
for (int i =subqueriesStartPos; i < subqueries.Count; i++)
{
OuterApplyOp op = m_command.CreateOuterApplyOp();
newNode = m_command.CreateNode(op, newNode, subqueries[i]);
}
if (!inputFirst)
{
newNode = m_command.CreateNode(m_command.CreateOuterApplyOp(), newNode, input);
}
// We may need to perform join elimination
m_compilerState.MarkPhaseAsNeeded(PlanCompilerPhase.JoinElimination);
return newNode;
}
///
/// Default processing for RelOps.
/// - First, we mark the current node as its own ancestor (so that any
/// subqueries that we detect internally will be added to this node's list)
/// - then, visit each child
/// - finally, accumulate all nested subqueries.
/// - if the current RelOp has only one input, then add the nested subqueries via
/// Outer apply nodes to this input.
///
/// The interesting RelOps are
/// Project, Filter, GroupBy, Sort,
/// Should we break this out into separate functions instead?
///
/// Current RelOp
/// Node to process
/// Current subtree
protected override Node VisitRelOpDefault(RelOp op, Node n)
{
VisitChildren(n); // visit all my children first
// Then identify all the subqueries that have shown up as part of my node
// Create Apply Nodes for each of these.
List nestedSubqueries;
if (m_nodeSubqueries.TryGetValue(n, out nestedSubqueries) && nestedSubqueries.Count > 0)
{
// Validate - this must only apply to the following nodes
PlanCompiler.Assert(
n.Op.OpType == OpType.Project || n.Op.OpType == OpType.Filter ||
n.Op.OpType == OpType.GroupBy,
"VisitRelOpDefault: Unexpected op?" + n.Op.OpType);
Node newInputNode = AugmentWithSubqueries(n.Child0, nestedSubqueries, true);
// Now make this the new input child
n.Child0 = newInputNode;
}
return n;
}
private void HandleTableOpMetadata(ScanTableBaseOp op)
{
// add to the list of referenced entitysets
md.EntitySet entitySet = op.Table.TableMetadata.Extent as md.EntitySet;
if (entitySet != null)
{
AddEntitySetReference(entitySet);
}
md.TypeUsage elementType = TypeUsage.Create(op.Table.TableMetadata.Extent.ElementType);
// add to the list of structured types
AddTypeReference(elementType);
}
///
/// Visits a "table" expression - performs view expansion on the table (if appropriate),
/// and then some additional book-keeping.
///
/// The "ofType" and "includeSubtypes" parameters are optional hints for view expansion, allowing
/// for more customized (and hopefully, more optimal) views. The wasOfTypeSatisfied out parameter
/// tells whether the ofType filter was already handled by the view expansion, or if the caller still
/// needs to deal with it.
///
/// If the "table" is a C-space entityset, then we produce a ScanViewOp
/// tree with the defining query as the only child of the ScanViewOp
///
/// If the table is an S-space entityset, then we still produce a ScanViewOp, but this
/// time, we produce a simple "select * from BaseTable" as the defining
/// query
///
/// the scanTable node tree
/// the scanTableOp
///
/// An optional IsOfOp representing a type filter to apply to the scan table; will be set to null
/// if the scan target is expanded to a view that renders the type filter superfluous.
///
///
/// Processes a ScanTableOp - simply delegates to ProcessScanTableOp
///
/// the view op
/// current node tree
/// the transformed view-op
public override Node Visit(ScanTableOp op, Node n)
{
IsOfOp nullFilter = null;
return ProcessScanTable(n, op, ref nullFilter);
}
///
/// Visitor for a ScanViewOp
///
///
///
///
/// Processing for all JoinOps
///
/// JoinOp
/// Current subtree
/// nestedSubqueries;
if (m_nodeSubqueries.TryGetValue(n, out nestedSubqueries))
{
PlanCompiler.Assert(n.Op.OpType == OpType.InnerJoin ||
n.Op.OpType == OpType.LeftOuterJoin ||
n.Op.OpType == OpType.FullOuterJoin, "unexpected op?");
PlanCompiler.Assert(n.HasChild2, "missing second child to JoinOp?");
Node joinCondition = n.Child2;
Node inputNode = m_command.CreateNode(m_command.CreateSingleRowTableOp());
inputNode = AugmentWithSubqueries(inputNode, nestedSubqueries, true);
Node filterNode = m_command.CreateNode(m_command.CreateFilterOp(), inputNode, joinCondition);
// update the join condition
// #479372: Build up a dummy project node over the input, as we always wrap the child of exists
Node projectNode = BuildDummyProjectForExists(filterNode);
Node existsNode = m_command.CreateNode(m_command.CreateExistsOp(), projectNode);
n.Child2 = existsNode;
}
return n;
}
///
/// Perform default relop processing; Also "require" the join-elimination phase
///
///
///
///
/// Visitor for UnnestOp. If the child has any subqueries, we need to convert this
/// into an
/// OuterApply(S, Unnest)
/// unlike the other cases where the OuterApply will appear as the input of the node
///
/// the unnestOp
/// current subtree
/// modified subtree
public override Node Visit(UnnestOp op, Node n)
{
VisitChildren(n); // visit all my children first
List nestedSubqueries;
if (m_nodeSubqueries.TryGetValue(n, out nestedSubqueries))
{
Node newNode = AugmentWithSubqueries(n, nestedSubqueries, false);
return newNode;
}
else
{
return n;
}
}
///
/// Can I eliminate this sort? I can, if the current path is *not* one of the
/// following
/// TopN(Sort)
/// PhysicalProject(Sort)
///
/// We don't yet handle the TopN variant
///
///
/// Visit a SortOp. Eliminate it if the path to this node is not one of
/// PhysicalProject(Sort) or
/// TopN(Sort)
///
/// Otherwise, simply visit the child RelOp
///
///
/// Current sortOp
/// current subtree
/// possibly transformed subtree
public override Node Visit(SortOp op, Node n)
{
// can I eliminate this sort
if (this.IsSortUnnecessary())
{
return VisitNode(n.Child0);
}
// perform default processing
return VisitRelOpDefault(op, n);
}
///
/// Checks to see if this filterOp represents an IS OF (or IS OF ONLY) filter over a ScanTableOp
///
/// the filterOp node
/// (OUT) the Type to restrict to
/// (OUT) was an ONLY clause specified
///
/// Handler for a FilterOp. Usually delegates to VisitRelOpDefault.
///
/// There's one special case - where we have an ISOF predicate over a ScanTable. In that case, we attempt
/// to get a more "optimal" view; and return that optimal view
///
///
/// the filterOp
/// the node tree
///
/// Visit a ProjectOp; if the input is a SortOp, we pullup the sort over
/// the ProjectOp to ensure that we don't have nested sorts;
///
///
///
/// sortChildren = new List();
sortChildren.Add(n);
//A ConstrainedSort has two other children besides the input and it needs to keep them.
for (int i = 1; i < n.Child0.Children.Count; i++)
{
sortChildren.Add(n.Child0.Children[i]);
}
// Replace the ProjectOp input (currently the Sort node) with the input to the Sort.
n.Child0 = n.Child0.Child0;
// Vars produced by the Sort input and used as SortKeys should be considered outputs
// of the ProjectOp that now operates over what was the Sort input.
foreach (SortKey key in sort.Keys)
{
op.Outputs.Set(key.Var);
}
// Finally, pull the Sort over the Project by creating a new Sort node with the original
// Sort as its Op and the Project node as its only child. This is sufficient because
// the ITreeGenerator ensures that the SortOp does not have any local VarDefs.
return VisitNode(m_command.CreateNode(sort, sortChildren));
}
// perform default processing
Node newNode = VisitRelOpDefault(op, n);
return newNode;
}
#endregion
#endregion
#endregion
}
///
/// Finds the record (Row) types that we're projecting out of the query, and
/// ensures that we mark them as needing a nullable sentinel, so when we
/// flatten them later we'll have one added.
///
internal class StructuredTypeNullabilityAnalyzer : ColumnMapVisitor>
{
static internal StructuredTypeNullabilityAnalyzer Instance = new StructuredTypeNullabilityAnalyzer();
///
/// VarRefColumnMap
///
///
///
/// typesNeedingNullSentinel)
{
AddTypeNeedingNullSentinel(typesNeedingNullSentinel, columnMap.Type);
base.Visit(columnMap, typesNeedingNullSentinel);
}
///
/// Recursively add any Row types to the list of types needing a sentinel.
///
///
///
private static void AddTypeNeedingNullSentinel(HashSet typesNeedingNullSentinel, TypeUsage typeUsage)
{
if (md.TypeSemantics.IsCollectionType(typeUsage))
{
AddTypeNeedingNullSentinel(typesNeedingNullSentinel, TypeHelpers.GetElementTypeUsage(typeUsage));
}
else
{
if (md.TypeSemantics.IsRowType(typeUsage) || md.TypeSemantics.IsComplexType(typeUsage))
{
MarkAsNeedingNullSentinel(typesNeedingNullSentinel, typeUsage);
}
foreach (EdmMember m in TypeHelpers.GetAllStructuralMembers(typeUsage))
{
AddTypeNeedingNullSentinel(typesNeedingNullSentinel, m.TypeUsage);
}
}
}
///
/// Marks the given typeUsage as needing a null sentinel.
/// Call this method instead of calling Add over the HashSet directly, to ensure consistency.
///
///
///
internal static void MarkAsNeedingNullSentinel(HashSet typesNeedingNullSentinel, TypeUsage typeUsage)
{
typesNeedingNullSentinel.Add(typeUsage.EdmType.Identity);
}
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- StringResourceManager.cs
- NameValueFileSectionHandler.cs
- CompoundFileDeflateTransform.cs
- HttpModuleAction.cs
- Point3DIndependentAnimationStorage.cs
- HandledMouseEvent.cs
- ConnectionManagementElementCollection.cs
- FlatButtonAppearance.cs
- MetadataAssemblyHelper.cs
- ProcessHostServerConfig.cs
- ToolStripPanelRow.cs
- PeerToPeerException.cs
- EdgeModeValidation.cs
- WebBrowserEvent.cs
- FlowDocumentReaderAutomationPeer.cs
- ComboBox.cs
- CorrelationTokenTypeConvertor.cs
- TextWriterTraceListener.cs
- regiisutil.cs
- DbMetaDataCollectionNames.cs
- UpdatePanelTrigger.cs
- ListViewUpdateEventArgs.cs
- NativeCompoundFileAPIs.cs
- DefinitionBase.cs
- ApplicationException.cs
- COM2TypeInfoProcessor.cs
- DataServiceHost.cs
- IUnknownConstantAttribute.cs
- ProtocolsConfigurationEntry.cs
- StorageFunctionMapping.cs
- ListDataBindEventArgs.cs
- Dump.cs
- IRCollection.cs
- OneWayElement.cs
- DataKeyArray.cs
- ViewStateException.cs
- FixedSOMPage.cs
- LowerCaseStringConverter.cs
- Quaternion.cs
- ControlValuePropertyAttribute.cs
- CompressedStack.cs
- SubclassTypeValidatorAttribute.cs
- WindowsTokenRoleProvider.cs
- DBParameter.cs
- StringValidatorAttribute.cs
- HebrewNumber.cs
- RouteItem.cs
- BindingWorker.cs
- MsmqMessageProperty.cs
- RSAOAEPKeyExchangeFormatter.cs
- ElementNotEnabledException.cs
- Positioning.cs
- SqlAliaser.cs
- Matrix3D.cs
- RadialGradientBrush.cs
- XmlSchemaElement.cs
- XmlWriter.cs
- ListViewItemMouseHoverEvent.cs
- SchemaUtility.cs
- DesignConnection.cs
- OleDbConnection.cs
- TypeUnloadedException.cs
- Set.cs
- DataKeyCollection.cs
- FilteredAttributeCollection.cs
- XmlUtilWriter.cs
- MulticastDelegate.cs
- PerspectiveCamera.cs
- ArgIterator.cs
- XamlInt32CollectionSerializer.cs
- COM2ICategorizePropertiesHandler.cs
- ChangePasswordAutoFormat.cs
- HttpCapabilitiesBase.cs
- PointAnimationBase.cs
- DynamicResourceExtensionConverter.cs
- SynchronizationContext.cs
- DateTime.cs
- XmlUtil.cs
- Camera.cs
- UserPersonalizationStateInfo.cs
- DataTable.cs
- PackageRelationshipSelector.cs
- HtmlInputFile.cs
- DataGridViewSelectedColumnCollection.cs
- WindowsTokenRoleProvider.cs
- NetCodeGroup.cs
- WebPartConnectionsConfigureVerb.cs
- TimeSpan.cs
- SmtpDateTime.cs
- nulltextcontainer.cs
- PagesSection.cs
- MergablePropertyAttribute.cs
- GridToolTip.cs
- XmlEncodedRawTextWriter.cs
- XsdBuilder.cs
- MediaContextNotificationWindow.cs
- HyperLinkStyle.cs
- MetadataItemCollectionFactory.cs
- ObjectItemCollectionAssemblyCacheEntry.cs
- Transactions.cs