SubqueryTrackingVisitor.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / SubqueryTrackingVisitor.cs / 1305376 / SubqueryTrackingVisitor.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System; 
using System.Collections.Generic;
using System.Data.Query.InternalTrees;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
 
namespace System.Data.Query.PlanCompiler
{ 
    ///  
    /// The SubqueryTracking Visitor serves as a base class for the visitors that may turn
    /// scalar subqueryies into outer-apply subqueries. 
    /// 
    internal abstract class SubqueryTrackingVisitor : BasicOpVisitorOfNode
    {
        #region Private State 
        protected readonly PlanCompiler m_compilerState;
        protected Command m_command { get { return m_compilerState.Command; } } 
 
        // nested subquery tracking
        protected readonly Stack m_ancestors = new Stack(); 
        private readonly Dictionary> m_nodeSubqueries = new Dictionary>();
        #endregion

        #region Constructor 
        protected SubqueryTrackingVisitor(PlanCompiler planCompilerState)
        { 
            this.m_compilerState = planCompilerState; 
        }
        #endregion 

        #region Subquery Handling
        /// 
        /// Adds a subquery to the list of subqueries for the relOpNode 
        /// 
        /// the RelOp node 
        /// the subquery 
        protected 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 
        protected 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 
        protected Node FindRelOpAncestor() 
        {
            foreach (Node n in m_ancestors) 
            {
                if (n.Op.IsRelOp)
                {
                    return n; 
                }
                else if (n.Op.IsPhysicalOp) 
                { 
                    return null;
                } 
            }
            return null;
        }
        #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 RelOps 

        ///  
        /// 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) 
            {
                // The driver node uses a cross apply to ensure that no results are produced
                // for an empty driver.
                newNode = m_command.CreateNode(m_command.CreateCrossApplyOp(), 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 || n.Op.OpType == OpType.GroupByInto, 
                    "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;
        } 

        ///  
        /// Processing for all JoinOps 
        /// 
        /// JoinOp 
        /// Current subtree
        /// Whether the node was modified
        protected bool ProcessJoinOp(JoinBaseOp op, Node n)
        { 
            VisitChildren(n); // visit all my children first
 
            // then check to see if we have any nested subqueries. This can only 
            // occur in the join condition.
            // What we'll do in this case is to convert the join condition - "p" into 
            //    p -> Exists(Filter(SingleRowTableOp, p))
            // We will then move the subqueries into an outerApply on the SingleRowTable
            List nestedSubqueries;
            if (!m_nodeSubqueries.TryGetValue(n, out nestedSubqueries)) 
            {
                return false; 
            } 

            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);
            Node existsNode = m_command.CreateNode(m_command.CreateExistsOp(), filterNode); 

            n.Child2 = existsNode;
            return true;
        } 

        ///  
        /// 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))
            {
                // We pass 'inputFirst = false' since the subqueries contribute to the driver in the unnest, 
                // they are not generated by the unnest.
                Node newNode = AugmentWithSubqueries(n, nestedSubqueries, false /* inputFirst */); 
                return newNode; 
            }
            else 
            {
                return n;
            }
        } 

        #endregion 
 
        #endregion
 
    }
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner  [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System; 
using System.Collections.Generic;
using System.Data.Query.InternalTrees;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
 
namespace System.Data.Query.PlanCompiler
{ 
    ///  
    /// The SubqueryTracking Visitor serves as a base class for the visitors that may turn
    /// scalar subqueryies into outer-apply subqueries. 
    /// 
    internal abstract class SubqueryTrackingVisitor : BasicOpVisitorOfNode
    {
        #region Private State 
        protected readonly PlanCompiler m_compilerState;
        protected Command m_command { get { return m_compilerState.Command; } } 
 
        // nested subquery tracking
        protected readonly Stack m_ancestors = new Stack(); 
        private readonly Dictionary> m_nodeSubqueries = new Dictionary>();
        #endregion

        #region Constructor 
        protected SubqueryTrackingVisitor(PlanCompiler planCompilerState)
        { 
            this.m_compilerState = planCompilerState; 
        }
        #endregion 

        #region Subquery Handling
        /// 
        /// Adds a subquery to the list of subqueries for the relOpNode 
        /// 
        /// the RelOp node 
        /// the subquery 
        protected 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 
        protected 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 
        protected Node FindRelOpAncestor() 
        {
            foreach (Node n in m_ancestors) 
            {
                if (n.Op.IsRelOp)
                {
                    return n; 
                }
                else if (n.Op.IsPhysicalOp) 
                { 
                    return null;
                } 
            }
            return null;
        }
        #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 RelOps 

        ///  
        /// 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) 
            {
                // The driver node uses a cross apply to ensure that no results are produced
                // for an empty driver.
                newNode = m_command.CreateNode(m_command.CreateCrossApplyOp(), 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 || n.Op.OpType == OpType.GroupByInto, 
                    "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;
        } 

        ///  
        /// Processing for all JoinOps 
        /// 
        /// JoinOp 
        /// Current subtree
        /// Whether the node was modified
        protected bool ProcessJoinOp(JoinBaseOp op, Node n)
        { 
            VisitChildren(n); // visit all my children first
 
            // then check to see if we have any nested subqueries. This can only 
            // occur in the join condition.
            // What we'll do in this case is to convert the join condition - "p" into 
            //    p -> Exists(Filter(SingleRowTableOp, p))
            // We will then move the subqueries into an outerApply on the SingleRowTable
            List nestedSubqueries;
            if (!m_nodeSubqueries.TryGetValue(n, out nestedSubqueries)) 
            {
                return false; 
            } 

            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);
            Node existsNode = m_command.CreateNode(m_command.CreateExistsOp(), filterNode); 

            n.Child2 = existsNode;
            return true;
        } 

        ///  
        /// 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))
            {
                // We pass 'inputFirst = false' since the subqueries contribute to the driver in the unnest, 
                // they are not generated by the unnest.
                Node newNode = AugmentWithSubqueries(n, nestedSubqueries, false /* inputFirst */); 
                return newNode; 
            }
            else 
            {
                return n;
            }
        } 

        #endregion 
 
        #endregion
 
    }
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK