PlanCompiler.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

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

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

using System; 
using System.Collections.Generic;
using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...

using cqt = System.Data.Common.CommandTrees; 
using md = System.Data.Metadata.Edm;
using System.Data.Query.InternalTrees; 
using System.Data.Query.PlanCompiler; 

namespace System.Data.Query.PlanCompiler 
{
    /// 
    /// The PlanCompiler class is used by the BridgeCommand to produce an
    /// execution plan - this execution plan is the plan object. The plan compilation 
    /// process takes as input a command tree (in C space), and then runs through a
    /// set of changes before the final plan is produced. The final plan contains 
    /// one or more command trees (commands?) (in S space), with a set of assembly 
    /// instructions.
    /// The compiler phases include 
    /// * Convert the command tree (CTree) into an internal tree (an ITree)
    /// * Run initializations on the ITree.
    /// * Eliminate structured types from the tree
    ///    * Eliminating named type references, refs and records from the tree 
    ///    At the end of this phase, we still may have collections (and record
    ///    arguments to collections) in the tree. 
    /// * Projection pruning (ie) eliminating unused references 
    /// * Tree transformations. Various transformations are run on the ITree to
    ///      (ostensibly) optimize the tree. These transformations are represented as 
    ///      rules, and a rule processor is invoked.
    /// * Nest elimination. At this point, we try to get pull up nest operations
    ///      as high up the tree as possible
    /// * Code Generation. This phase produces a plan object with various subpieces 
    ///      of the ITree represented as commands (in S space).
    ///    * The subtrees of the ITree are then converted into the corresponding CTrees 
    ///      and converted into S space as part of the CTree creation. 
    ///    * A plan object is created and returned.
    ///  
    internal class PlanCompiler
    {

        #region private state 

        ///  
        /// Bid Counter object 
        /// 
        private static int _objectTypeCount; 

        /// 
        /// The object Id of this instance, for BID tracing.
        ///  
        internal readonly int ObjectID = System.Threading.Interlocked.Increment(ref _objectTypeCount);
 
        ///  
        /// A boolean switch indicating whether we should apply transformation rules regardless of the size of the Iqt.
        /// By default, the Enabled property of a boolean switch is set using the value specified in the configuration file. 
        /// Configuring the switch with a value of 0 sets the Enabled property to false; configuring the switch with a nonzero
        /// value to set the Enabled property to true. If the BooleanSwitch constructor cannot find initial switch settings
        /// in the configuration file, the Enabled property of the new switch is set to false by default.
        ///  
        private static BooleanSwitch _applyTransformationsRegardlessOfSize = new BooleanSwitch("System.Data.EntityClient.IgnoreOptimizationLimit", "The Entity Framework should try to optimize the query regardless of its size");
 
        ///  
        /// Determines the maximum size of the query in terms of Iqt nodes for which we attempt to do transformation rules.
        /// This number is ignored if applyTransformationsRegardlessOfSize is enabled. 
        /// 
        private const int MaxNodeCountForTransformations = 100000;

        ///  
        /// The CTree we're compiling a plan for.
        ///  
        private cqt.DbCommandTree m_ctree; 

        ///  
        /// The ITree we're working on.
        /// 
        private Command m_command;
 
        /// 
        /// The phase of the process we're currently in. 
        ///  
        private PlanCompilerPhase m_phase;
 
        /// 
        /// Set of phases we need to go through
        /// 
        private int m_neededPhases; 

        ///  
        /// Keeps track of foreign key relationships. Needed by Join Elimination 
        /// 
        private ConstraintManager m_constraintManager; 

        /// 
        /// Can transformation rules be applied
        ///  
        private Nullable m_mayApplyTransformationRules = null;
 
        ///  
        /// Does the command include any sort key that represents a null sentinel
        /// This may only be set to true in NominalTypeElimination and is used 
        /// in Transformation Rules
        /// 
        private bool m_hasSortingOnNullSentinels = false;
        #endregion 

        #region constructors 
 
        /// 
        /// private constructor 
        /// 
        /// the input cqt
        private PlanCompiler(cqt.DbCommandTree ctree)
        { 
            m_ctree = ctree; // the input command tree
        } 
 
        #endregion
 
        #region public interfaces

        /// 
        /// Retail Assertion code. 
        ///
        /// Provides the ability to have retail asserts. 
        ///  
        /// 
        ///  
        internal static void Assert(bool condition, string message)
        {
            if (!condition)
            { 
                System.Diagnostics.Debug.Fail(message);
 
                // NOTE: I considered, at great length, whether to have the assertion message text 
                //       included in the exception we throw; in the end, there really isn't a reliable
                //       equivalent to the C++ __LINE__ and __FILE__ macros in C# (at least not without 
                //       using the C++ PreProcessor...ick)  The StackTrace object comes close but
                //       doesn't handle inlined callers properly for our needs (MethodA() calls MethodB()
                //       calls us, but MethodB() is inlined, so we'll get MethodA() info instead), and
                //       since these are retail "Asserts" (as in: we're not supposed to get them in our 
                //       shipping code, and we're doing this to avoid a null-ref which is even worse) I
                //       elected to simplify this by just including them as the additional info. 
                throw EntityUtil.InternalError(EntityUtil.InternalErrorCode.AssertionFailed, 0, message); 
            }
        } 

        /// 
        /// Compile a query, and produce a plan
        ///  
        /// the input CQT
        /// list of provider commands 
        /// column map for result assembly 
        /// the entity sets referenced in this query
        /// a compiled plan object 
        internal static void Compile(cqt.DbCommandTree ctree, out List providerCommands, out ColumnMap resultColumnMap, out int columnCount, out Common.Utils.Set entitySets)
        {
            PlanCompiler.Assert(ctree != null, "Expected a valid, non-null Command Tree input");
            PlanCompiler pc = new PlanCompiler(ctree); 
            pc.Compile(out providerCommands, out resultColumnMap, out columnCount, out entitySets);
        } 
 

        ///  
        /// Get the current command
        /// 
        internal Command Command { get { return m_command; } }
 
        /// 
        /// Does the command include any sort key that represents a null sentinel 
        /// This may only be set to true in NominalTypeElimination and is used 
        /// in Transformation Rules
        ///  
        internal bool HasSortingOnNullSentinels
        {
            get { return m_hasSortingOnNullSentinels; }
            set { m_hasSortingOnNullSentinels = value; } 
        }
 
        ///  
        /// Keeps track of foreign key relationships. Needed by  Join Elimination
        ///  
        internal ConstraintManager ConstraintManager
        {
            get
            { 
                if (m_constraintManager == null)
                { 
                    m_constraintManager = new ConstraintManager(); 
                }
                return m_constraintManager; 
            }
        }

#if DEBUG 
        /// 
        /// Get the current plan compiler phase 
        ///  
        internal PlanCompilerPhase Phase { get { return m_phase; } }
 
        /// 
        /// Sets the current plan compiler trace function to , enabling plan compiler tracing
        /// 
        internal static void TraceOn(Action traceCallback) 
        {
            s_traceCallback = traceCallback; 
        } 

        ///  
        /// Sets the current plan compiler trace function to null, disabling plan compiler tracing
        /// 
        internal static void TraceOff()
        { 
            s_traceCallback = null;
        } 
 
        private static Action s_traceCallback;
#endif 
        /// 
        /// The MetadataWorkspace
        /// 
        internal md.MetadataWorkspace MetadataWorkspace { get { return m_ctree.MetadataWorkspace; } } 

        ///  
        /// Is the specified phase needed for this query? 
        /// 
        /// the phase in question 
        /// 
        internal bool IsPhaseNeeded(PlanCompilerPhase phase)
        {
            return ((m_neededPhases & (1 << (int)phase)) != 0); 
        }
 
        ///  
        /// Mark the specified phase as needed
        ///  
        /// plan compiler phase
        internal void MarkPhaseAsNeeded(PlanCompilerPhase phase)
        {
            m_neededPhases = m_neededPhases | (1 << (int)phase); 
        }
 
        #endregion 

        #region private methods 

        /// 
        /// The real driver.
        ///  
        /// list of provider commands
        /// column map for the result 
        /// the entity sets exposed in this query 
        private void Compile(out List providerCommands, out ColumnMap resultColumnMap, out int columnCount, out Common.Utils.Set entitySets)
        { 
            EntityBid.Trace(" %d# Compiling Plan for DbCommandTree=%d#\n", ObjectID, m_ctree.ObjectId);

            Initialize(); // initialize the ITree
 
            string beforePreProcessor = String.Empty;
            string beforeAggregatePushdown = String.Empty; 
            string beforeNormalization = String.Empty; 
            string beforeNTE = String.Empty;
            string beforeProjectionPruning1 = String.Empty; 
            string beforeNestPullup = String.Empty;
            string beforeProjectionPruning2 = String.Empty;
            string beforeTransformationRules1 = String.Empty;
            string beforeProjectionPruning3 = String.Empty; 
            string beforeTransformationRules2 = String.Empty;
            string beforeJoinElimination1 = String.Empty; 
            string beforeTransformationRules3 = String.Empty; 
            string beforeJoinElimination2 = String.Empty;
            string beforeTransformationRules4 = String.Empty; 
            string beforeCodeGen = String.Empty;

            //
            // We always need the pre-processor and the codegen phases. 
            // It is generally a good thing to run through the transformation rules, and
            // the projection pruning phases. 
            // The "optional" phases are AggregatePushdown, Normalization, NTE, NestPullup and JoinElimination 
            //
            m_neededPhases = (1 << (int)PlanCompilerPhase.PreProcessor) | 
                // (1 << (int)PlanCompilerPhase.AggregatePushdown) |
                // (1 << (int)PlanCompilerPhase.Normalization) |
                // (1 << (int)PlanCompilerPhase.NTE) |
                (1 << (int)PlanCompilerPhase.ProjectionPruning) | 
                // (1 << (int)PlanCompilerPhase.NestPullup) |
                (1 << (int)PlanCompilerPhase.Transformations) | 
                // (1 << (int)PlanCompilerPhase.JoinElimination) | 
                (1 << (int)PlanCompilerPhase.CodeGen);
 
            // Perform any necessary preprocessing
            StructuredTypeInfo typeInfo = null;
            beforePreProcessor = SwitchToPhase(PlanCompilerPhase.PreProcessor);
            PreProcessor.Process(this, out typeInfo); 
            entitySets = typeInfo.GetEntitySets();
 
            if (IsPhaseNeeded(PlanCompilerPhase.AggregatePushdown)) 
            {
                beforeAggregatePushdown = SwitchToPhase(PlanCompilerPhase.AggregatePushdown); 
                AggregatePushdown.Process(this);
            }

            if (IsPhaseNeeded(PlanCompilerPhase.Normalization)) 
            {
                beforeNormalization = SwitchToPhase(PlanCompilerPhase.Normalization); 
                Normalizer.Process(this); 
            }
 
            // Eliminate "structured" types.
            if (IsPhaseNeeded(PlanCompilerPhase.NTE))
            {
                beforeNTE = SwitchToPhase(PlanCompilerPhase.NTE); 
                NominalTypeEliminator.Process(this, typeInfo);
            } 
 
            // Projection pruning - eliminate unreferenced expressions
            if (IsPhaseNeeded(PlanCompilerPhase.ProjectionPruning)) 
            {
                beforeProjectionPruning1 = SwitchToPhase(PlanCompilerPhase.ProjectionPruning);
                ProjectionPruner.Process(this);
            } 

            // Nest Pull-up on the ITree 
            if (IsPhaseNeeded(PlanCompilerPhase.NestPullup)) 
            {
                beforeNestPullup = SwitchToPhase(PlanCompilerPhase.NestPullup); 

                NestPullup.Process(this);

                //If we do Nest Pull-up, we should again do projection pruning 
                beforeProjectionPruning2 = SwitchToPhase(PlanCompilerPhase.ProjectionPruning);
                ProjectionPruner.Process(this); 
            } 

            // Run transformations on the tree 
            if (IsPhaseNeeded(PlanCompilerPhase.Transformations))
            {
                bool projectionPrunningNeeded = ApplyTransformations(ref beforeTransformationRules1, TransformationRulesGroup.All);
 
                if (projectionPrunningNeeded)
                { 
                    beforeProjectionPruning3 = SwitchToPhase(PlanCompilerPhase.ProjectionPruning); 
                    ProjectionPruner.Process(this);
                    ApplyTransformations(ref beforeTransformationRules2, TransformationRulesGroup.Project); 
                }
            }

            // Join elimination 
            if (IsPhaseNeeded(PlanCompilerPhase.JoinElimination))
            { 
                beforeJoinElimination1 = SwitchToPhase(PlanCompilerPhase.JoinElimination); 
                bool modified = JoinElimination.Process(this);
                if (modified) 
                {
                    ApplyTransformations(ref beforeTransformationRules3, TransformationRulesGroup.PostJoinElimination);
                    beforeJoinElimination2 = SwitchToPhase(PlanCompilerPhase.JoinElimination);
                    modified = JoinElimination.Process(this); 
                    if (modified)
                    { 
                        ApplyTransformations(ref beforeTransformationRules4, TransformationRulesGroup.PostJoinElimination); 
                    }
                } 
            }

            // Code generation
            beforeCodeGen = SwitchToPhase(PlanCompilerPhase.CodeGen); 
            CodeGen.Process(this, out providerCommands, out resultColumnMap, out columnCount);
 
#if DEBUG 
            // GC.KeepAlive makes FxCop Grumpy.
            int size = beforePreProcessor.Length; 
            size = beforeAggregatePushdown.Length;
            size = beforeNormalization.Length;
            size = beforeNTE.Length;
            size = beforeProjectionPruning1.Length; 
            size = beforeNestPullup.Length;
            size = beforeProjectionPruning2.Length; 
            size = beforeTransformationRules1.Length; 
            size = beforeProjectionPruning3.Length;
            size = beforeTransformationRules2.Length; 
            size = beforeJoinElimination1.Length;
            size = beforeTransformationRules3.Length;
            size = beforeJoinElimination2.Length;
            size = beforeTransformationRules4.Length; 
            size = beforeCodeGen.Length;
#endif 
            if (EntityBid.TraceOn) 
            {
                int i = 0; 
                foreach (ProviderCommandInfo pi in providerCommands)
                {
                    EntityBid.Trace(" %d# resulting command %d with DbCommandTree=%d#\n", ObjectID, i++, pi.CommandTree.ObjectId);
                } 
            }
 
            // All done 
            return;
        } 

        /// 
        /// Helper method for applying transformation rules
        ///  
        /// 
        ///  
        ///  
        private bool ApplyTransformations(ref string dumpString, TransformationRulesGroup rulesGroup)
        { 
            if (MayApplyTransformationRules)
            {
                dumpString = SwitchToPhase(PlanCompilerPhase.Transformations);
                return TransformationRules.Process(this, rulesGroup); 
            }
            return false; 
        } 

        ///  
        /// Logic to perform between each compile phase
        /// 
        /// 
        ///  
        private string SwitchToPhase(PlanCompilerPhase newPhase)
        { 
            string iqtDumpResult = string.Empty; 

            m_phase = newPhase; 

            if (EntityBid.PlanCompilerOn)
            {
                iqtDumpResult = Dump.ToXml(m_command); 
                EntityBid.PlanCompilerTrace(" %d# phase=%d\n", ObjectID, (int)newPhase);
                EntityBid.PlanCompilerPutStr(iqtDumpResult); 
            } 
#if DEBUG
            else if (s_traceCallback != null) 
            {
                s_traceCallback(Enum.GetName(typeof(PlanCompilerPhase), newPhase), m_command);
            }
            else 
            {
                iqtDumpResult = Dump.ToXml(m_command); 
            } 

            Validator.Validate(this); 
#endif
            return iqtDumpResult;
        }
 
        /// 
        /// To avoid processing huge trees, transformation rules are applied only if the number of nodes 
        /// is less than MaxNodeCountForTransformations 
        /// or if it is specified that they should be applied regardless of the size of the query.
        /// Whether to apply transformations is only computed the first time this property is requested, 
        /// and is cached afterwards. This is because we don't expect the tree to get larger
        /// from applying transformations.
        /// 
        private bool MayApplyTransformationRules 
        {
            get 
            { 
                if (m_mayApplyTransformationRules == null)
                { 
                    m_mayApplyTransformationRules = ComputeMayApplyTransformations();
                }
                return m_mayApplyTransformationRules.Value;
            } 
        }
 
        ///  
        /// Compute whether transformations may be applied.
        /// Transformation rules may be applied only if the number of nodes is less than 
        /// MaxNodeCountForTransformations or if it is specified that they should be applied
        /// regardless of the size of the query.
        /// 
        ///  
        private bool ComputeMayApplyTransformations()
        { 
            // 
            // If the nextNodeId is less than MaxNodeCountForTransformations then we don't need to
            // calculate the acutal node count, it must be less than  MaxNodeCountForTransformations 
            //
            if (_applyTransformationsRegardlessOfSize.Enabled || this.m_command.NextNodeId < MaxNodeCountForTransformations)
            {
                return true; 
            }
 
            //Compute the actual node count 
            int actualCount = NodeCounter.Count(this.m_command.Root);
            return (actualCount < MaxNodeCountForTransformations); 
        }

        /// 
        /// Converts the CTree into an ITree, and initializes the plan 
        /// 
        private void Initialize() 
        { 
            // Only support queries for now
            cqt.DbQueryCommandTree cqtree = m_ctree as cqt.DbQueryCommandTree; 
            PlanCompiler.Assert(cqtree != null, "Unexpected command tree kind. Only query command tree is supported.");

            // Generate the ITree
            m_command = ITreeGenerator.Generate(cqtree); 
            PlanCompiler.Assert(m_command != null, "Unable to generate internal tree from Command Tree");
        } 
 
        #endregion
    } 


    /// 
    /// Enum describing which phase of plan compilation we're currently in 
    /// 
    internal enum PlanCompilerPhase 
    { 
        /// 
        /// Just entering the PreProcessor phase 
        /// 
        PreProcessor = 0,

        ///  
        /// Entering the AggregatePushdown phase
        ///  
        AggregatePushdown = 1, 

        ///  
        /// Entering the Normalization phase
        /// 
        Normalization = 2,
 
        /// 
        /// Entering the NTE (Nominal Type Eliminator) phase 
        ///  
        NTE = 3,
 
        /// 
        /// Entering the Projection pruning phase
        /// 
        ProjectionPruning = 4, 

        ///  
        /// Entering the Nest Pullup phase 
        /// 
        NestPullup = 5, 

        /// 
        /// Entering the Transformations phase
        ///  
        Transformations = 6,
 
        ///  
        /// Entering the JoinElimination phase
        ///  
        JoinElimination = 7,

        /// 
        /// Entering the codegen phase 
        /// 
        CodeGen = 8, 
 
        /// 
        /// We're almost done 
        /// 
        PostCodeGen = 9,

        ///  
        /// Marker
        ///  
        MaxMarker = 10 
    }
} 

// 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