mcs/class/referencesource/System.Data.Entity/System/Data/Query/InternalTrees/NodeInfo.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="NodeInfo.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner  Microsoft
   7 // @backupOwner Microsoft
   8 //---------------------------------------------------------------------
   9
  10 using System;
  11 using System.Collections.Generic;
  12 using System.Globalization;
  13 using System.Diagnostics;
  14 using System.Data.Common;
  15 using md=System.Data.Metadata.Edm;
  16
  17 namespace System.Data.Query.InternalTrees
  18 {
  19     /// <summary>
  20     /// The KeySet class encapsulates all information about the keys of a RelOp node in
  21     /// the query tree.
  22     /// A KeyVec is logically a set of vars that uniquely identify the row of the current
  23     /// RelOp. Some RelOps may have no unique keys - such a state is identified by the
  24     /// "NoKeys" property
  25     /// </summary>
  26     internal class KeyVec
  27     {
  28         #region private state
  29         private VarVec m_keys;
  30         private bool m_noKeys;
  31         #endregion
  32
  33         #region constructors
  34         internal KeyVec(Command itree)
  35         {
  36             m_keys = itree.CreateVarVec();
  37             m_noKeys = true;
  38         }
  39         #endregion
  40
  41         internal void InitFrom(KeyVec keyset)
  42         {
  43             m_keys.InitFrom(keyset.m_keys);
  44             m_noKeys = keyset.m_noKeys;
  45         }
  46
  47         internal void InitFrom(IEnumerable<Var> varSet)
  48         {
  49             InitFrom(varSet, false);
  50         }
  51
  52         internal void InitFrom(IEnumerable<Var> varSet, bool ignoreParameters)
  53         {
  54             m_keys.InitFrom(varSet, ignoreParameters);
  55             // Bug 434541: An empty set of keys is not the same as "no" keys.
  56             // Caveat Emptor
  57             m_noKeys = false;
  58         }
  59         internal void InitFrom(KeyVec left, KeyVec right)
  60         {
  61             if (left.m_noKeys || right.m_noKeys)
  62             {
  63                 m_noKeys = true;
  64             }
  65             else
  66             {
  67                 m_noKeys = false;
  68                 m_keys.InitFrom(left.m_keys);
  69                 m_keys.Or(right.m_keys);
  70             }
  71         }
  72         internal void InitFrom(List<KeyVec> keyVecList)
  73         {
  74             m_noKeys = false;
  75             m_keys.Clear();
  76             foreach (KeyVec keyVec in keyVecList)
  77             {
  78                 if (keyVec.m_noKeys)
  79                 {
  80                     m_noKeys = true;
  81                     return;
  82                 }
  83                 m_keys.Or(keyVec.m_keys);
  84             }
  85         }
  86         internal void Clear()
  87         {
  88             m_noKeys = true;
  89             m_keys.Clear();
  90         }
  91
  92         internal VarVec KeyVars { get { return m_keys; } }
  93         internal bool NoKeys { get { return m_noKeys; } set { m_noKeys = value; } }
  94     }
  95
  96     /// <summary>
  97     /// The NodeInfo class represents additional information about a node in the tree.
  98     /// By default, this includes a set of external references for each node (ie) references
  99     /// to Vars that are not defined in the same subtree
 100     /// The NodeInfo class also includes a "hashValue" that is a hash value for the entire
 101     /// subtree rooted at this node
 102     /// NOTE: When adding a new member to track inforation, make sure to update the Clear method
 103     /// in this class to set that member to the default value.
 104     /// </summary>
 105     internal class NodeInfo
 106     {
 107         #region private state
 108         private VarVec m_externalReferences;
 109         protected int m_hashValue; // hash value for the node
 110         #endregion
 111
 112         #region constructors
 113         internal NodeInfo(Command cmd)
 114         {
 115             m_externalReferences = cmd.CreateVarVec();
 116         }
 117         #endregion
 118
 119         #region public methods
 120         /// <summary>
 121         /// Clear out all information - usually used by a Recompute
 122         /// </summary>
 123         internal virtual void Clear()
 124         {
 125             m_externalReferences.Clear();
 126             m_hashValue = 0;
 127         }
 128
 129         /// <summary>
 130         /// All external references from this node
 131         /// </summary>
 132         internal VarVec ExternalReferences
 133         {
 134             get { return m_externalReferences; }
 135         }
 136
 137         /// <summary>
 138         /// Get the hash value for this nodeInfo
 139         /// </summary>
 140         internal int HashValue
 141         {
 142             get { return m_hashValue; }
 143         }
 144
 145         /// <summary>
 146         /// Compute the hash value for a Vec
 147         /// </summary>
 148         /// <param name="vec"></param>
 149         /// <returns></returns>
 150         internal static int GetHashValue(VarVec vec)
 151         {
 152             int hashValue = 0;
 153             foreach (Var v in vec)
 154             {
 155                 hashValue ^= v.GetHashCode();
 156             }
 157             return hashValue;
 158         }
 159
 160         /// <summary>
 161         /// Computes the hash value for this node. The hash value is simply the
 162         /// local hash value for this node info added with the hash values of the child
 163         /// nodes
 164         /// </summary>
 165         /// <param name="cmd">current command</param>
 166         /// <param name="n">current node</param>
 167         internal virtual void ComputeHashValue(Command cmd, Node n)
 168         {
 169             m_hashValue = 0;
 170             foreach (Node chi in n.Children)
 171             {
 172                 NodeInfo chiNodeInfo = cmd.GetNodeInfo(chi);
 173                 m_hashValue ^= chiNodeInfo.HashValue;
 174             }
 175
 176             m_hashValue = (m_hashValue << 4) ^ ((int)n.Op.OpType); // include the optype somehow
 177             // Now compute my local hash value
 178             m_hashValue = (m_hashValue << 4) ^ GetHashValue(m_externalReferences);
 179         }
 180         #endregion
 181     }
 182
 183     /// <summary>
 184     /// Enum describing row counts
 185     /// </summary>
 186     internal enum RowCount : byte
 187     {
 188         /// <summary>
 189         /// Zero rows
 190         /// </summary>
 191         Zero = 0,
 192
 193         /// <summary>
 194         /// One row
 195         /// </summary>
 196         One = 1,
 197
 198         /// <summary>
 199         /// Unbounded (unknown number of rows)
 200         /// </summary>
 201         Unbounded = 2,
 202     }
 203
 204     /// <summary>
 205     /// An ExtendedNodeInfo class adds additional information to a standard NodeInfo.
 206     /// This class is usually applicable only to RelOps and PhysicalOps.
 207     /// The ExtendedNodeInfo class has in addition to the information maintained by NodeInfo
 208     /// the following
 209     /// - a set of local definitions
 210     /// - a set of definitions
 211     /// - a set of keys
 212     /// - a set of non-nullable definitions
 213     /// - a set of non-nullable definitions that are visible at this node
 214     /// NOTE: When adding a new member to track inforation, make sure to update the Clear method
 215     /// in this class to set that member to the default value.
 216     /// </summary>
 217     internal class ExtendedNodeInfo : NodeInfo
 218     {
 219         #region private
 220         private VarVec m_localDefinitions;
 221         private VarVec m_definitions;
 222         private KeyVec m_keys;
 223         private VarVec m_nonNullableDefinitions;
 224         private VarVec m_nonNullableVisibleDefinitions;
 225         private RowCount m_minRows;
 226         private RowCount m_maxRows;
 227         #endregion
 228
 229         #region constructors
 230         internal ExtendedNodeInfo(Command cmd)
 231             : base(cmd)
 232         {
 233             m_localDefinitions = cmd.CreateVarVec();
 234             m_definitions = cmd.CreateVarVec();
 235             m_nonNullableDefinitions = cmd.CreateVarVec();
 236             m_nonNullableVisibleDefinitions = cmd.CreateVarVec();
 237             m_keys = new KeyVec(cmd);
 238             m_minRows = RowCount.Zero;
 239             m_maxRows = RowCount.Unbounded;
 240         }
 241         #endregion
 242
 243         #region public methods
 244
 245         internal override void Clear()
 246         {
 247             base.Clear();
 248             m_definitions.Clear();
 249             m_localDefinitions.Clear();
 250             m_nonNullableDefinitions.Clear();
 251             m_nonNullableVisibleDefinitions.Clear();
 252             m_keys.Clear();
 253             m_minRows = RowCount.Zero;
 254             m_maxRows = RowCount.Unbounded;
 255         }
 256
 257         /// <summary>
 258         /// Compute the hash value for this node
 259         /// </summary>
 260         /// <param name="cmd"></param>
 261         /// <param name="n"></param>
 262         internal override void ComputeHashValue(Command cmd, Node n)
 263         {
 264             base.ComputeHashValue(cmd, n);
 265             m_hashValue = (m_hashValue << 4) ^ NodeInfo.GetHashValue(this.Definitions);
 266             m_hashValue = (m_hashValue << 4) ^ NodeInfo.GetHashValue(this.Keys.KeyVars);
 267             return;
 268         }
 269
 270         /// <summary>
 271         /// Definitions made specifically by this node
 272         /// </summary>
 273         internal VarVec LocalDefinitions { get { return m_localDefinitions; } }
 274         /// <summary>
 275         /// All definitions visible as outputs of this node
 276         /// </summary>
 277         internal VarVec Definitions { get { return m_definitions; } }
 278         /// <summary>
 279         /// The keys for this node
 280         /// </summary>
 281         internal KeyVec Keys { get { return m_keys; } }
 282         /// <summary>
 283         /// The definitions of vars that are guaranteed to be non-nullable when output from this node
 284         /// </summary>
 285         internal VarVec NonNullableDefinitions { get { return m_nonNullableDefinitions; } }
 286         /// <summary>
 287         /// The definitions that come from the rel-op inputs of this node that are guaranteed to be non-nullable
 288         /// </summary>
 289         internal VarVec NonNullableVisibleDefinitions { get { return m_nonNullableVisibleDefinitions; } }
 290         /// <summary>
 291         /// Min number of rows returned from this node
 292         /// </summary>
 293         internal RowCount MinRows
 294         {
 295             get { return m_minRows; }
 296             set { m_minRows = value; ValidateRowCount(); }
 297         }
 298         /// <summary>
 299         /// Max rows returned from this node
 300         /// </summary>
 301         internal RowCount MaxRows
 302         {
 303             get { return m_maxRows; }
 304             set { m_maxRows = value; ValidateRowCount(); }
 305         }
 306
 307         /// <summary>
 308         /// Set the rowcount for this node
 309         /// </summary>
 310         /// <param name="minRows">min rows produced by this node</param>
 311         /// <param name="maxRows">max rows produced by this node</param>
 312         internal void SetRowCount(RowCount minRows, RowCount maxRows)
 313         {
 314             m_minRows = minRows;
 315             m_maxRows = maxRows;
 316             ValidateRowCount();
 317         }
 318
 319         /// <summary>
 320         /// Initialize the rowcounts for this node from the source node
 321         /// </summary>
 322         /// <param name="source">nodeinfo of source</param>
 323         internal void InitRowCountFrom(ExtendedNodeInfo source)
 324         {
 325             m_minRows = source.m_minRows;
 326             m_maxRows = source.m_maxRows;
 327         }
 328
 329         #endregion
 330
 331         #region private methods
 332         private void ValidateRowCount()
 333         {
 334             Debug.Assert(m_maxRows >= m_minRows, "MaxRows less than MinRows?");
 335         }
 336         #endregion
 337     }
 338
 339     /// <summary>
 340     /// The NodeInfoVisitor is a simple class (ab)using the Visitor pattern to define
 341     /// NodeInfo semantics for various nodes in the tree
 342     /// </summary>
 343     internal class NodeInfoVisitor : BasicOpVisitorOfT<NodeInfo>
 344     {
 345         #region public methods
 346         /// <summary>
 347         /// The only public method. Recomputes the nodeInfo for a node in the tree,
 348         /// but only if the node info has already been computed.
 349         /// Assumes that the NodeInfo for each child (if computed already) is valid
 350         /// </summary>
 351         /// <param name="n">Node to get NodeInfo for</param>
 352         internal void RecomputeNodeInfo(Node n)
 353         {
 354             if (n.IsNodeInfoInitialized)
 355             {
 356                 NodeInfo nodeInfo = VisitNode(n);
 357                 nodeInfo.ComputeHashValue(this.m_command, n); // compute the hash value for this node
 358             }
 359         }
 360         #endregion
 361
 362         #region constructors
 363         /// <summary>
 364         /// Basic constructor
 365         /// </summary>
 366         /// <param name="command"></param>
 367         internal NodeInfoVisitor(Command command)
 368         {
 369             m_command = command;
 370         }
 371         #endregion
 372
 373         #region private state
 374         private Command m_command;
 375         #endregion
 376
 377         #region private methods
 378         private NodeInfo GetNodeInfo(Node n)
 379         {
 380             return n.GetNodeInfo(m_command);
 381         }
 382         private ExtendedNodeInfo GetExtendedNodeInfo(Node n)
 383         {
 384             return n.GetExtendedNodeInfo(m_command);
 385         }
 386         private NodeInfo InitNodeInfo(Node n)
 387         {
 388             NodeInfo nodeInfo = GetNodeInfo(n);
 389             nodeInfo.Clear();
 390             return nodeInfo;
 391         }
 392         private ExtendedNodeInfo InitExtendedNodeInfo(Node n)
 393         {
 394             ExtendedNodeInfo nodeInfo = GetExtendedNodeInfo(n);
 395             nodeInfo.Clear();
 396             return nodeInfo;
 397         }
 398         #endregion
 399
 400         #region VisitorHelpers
 401         /// <summary>
 402         /// Default implementation for scalarOps. Simply adds up external references
 403         /// from each child
 404         /// </summary>
 405         /// <param name="n"></param>
 406         /// <returns></returns>
 407         protected override NodeInfo VisitDefault(Node n)
 408         {
 409             Debug.Assert(n.Op.IsScalarOp || n.Op.IsAncillaryOp, "not a supported optype");
 410
 411             NodeInfo nodeInfo = InitNodeInfo(n);
 412             // My external references are simply the combination of external references
 413             // of all my children
 414             foreach (Node chi in n.Children)
 415             {
 416                 NodeInfo childNodeInfo = GetNodeInfo(chi);
 417                 nodeInfo.ExternalReferences.Or(childNodeInfo.ExternalReferences);
 418             }
 419             return nodeInfo;
 420         }
 421
 422         /// <summary>
 423         /// The given definition is non nullable if it is a non-null constant
 424         /// or a reference to non-nullable input
 425         /// </summary>
 426         /// <param name="definition"></param>
 427         /// <param name="nonNullableInputs"></param>
 428         /// <returns></returns>
 429         private bool IsDefinitionNonNullable(Node definition, VarVec nonNullableInputs)
 430         {
 431             return (definition.Op.OpType == OpType.Constant
 432                 || definition.Op.OpType == OpType.InternalConstant
 433                 || definition.Op.OpType == OpType.NullSentinel
 434                 || definition.Op.OpType == OpType.VarRef
 435                     && nonNullableInputs.IsSet(((VarRefOp)definition.Op).Var));
 436         }
 437         #endregion
 438
 439         #region IOpVisitor<NodeInfo> Members
 440
 441         #region MiscOps
 442         #endregion
 443
 444         #region AncillarOps
 445         #endregion
 446
 447         #region ScalarOps
 448         /// <summary>
 449         /// The only special case among all scalar and ancillaryOps. Simply adds
 450         /// its var to the list of unreferenced Ops
 451         /// </summary>
 452         /// <param name="op">The VarRefOp</param>
 453         /// <param name="n">Current node</param>
 454         /// <returns></returns>
 455         public override NodeInfo Visit(VarRefOp op, Node n)
 456         {
 457             NodeInfo nodeInfo = InitNodeInfo(n);
 458             nodeInfo.ExternalReferences.Set(op.Var);
 459             return nodeInfo;
 460         }
 461
 462         #endregion
 463
 464         #region RelOps
 465         protected override NodeInfo VisitRelOpDefault(RelOp op, Node n)
 466         {
 467             return Unimplemented(n);
 468         }
 469
 470         /// <summary>
 471         /// Definitions = Local Definitions = referenced table columns
 472         /// External References = none
 473         /// Keys = keys of entity type
 474         /// RowCount (default): MinRows = 0, MaxRows = *
 475         /// NonNullableDefinitions : non nullable table columns that are definitions
 476         /// NonNullableInputDefinitions : default(empty) because cannot be used
 477         /// </summary>
 478         /// <param name="op">ScanTable/ScanView op</param>
 479         /// <param name="n">current subtree</param>
 480         /// <returns>nodeinfo for this subtree</returns>
 481         protected override NodeInfo VisitTableOp(ScanTableBaseOp op, Node n)
 482         {
 483             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
 484             // #479372 - only the "referenced" columns of the table should
 485             // show up in the definitions
 486             nodeInfo.LocalDefinitions.Or(op.Table.ReferencedColumns);
 487             nodeInfo.Definitions.Or(op.Table.ReferencedColumns);
 488
 489             // get table's keys - but only if the key columns have been referenced
 490             if (op.Table.ReferencedColumns.Subsumes(op.Table.Keys))
 491             {
 492                 nodeInfo.Keys.InitFrom(op.Table.Keys);
 493             }
 494             // no external references
 495
 496             //non-nullable definitions
 497             nodeInfo.NonNullableDefinitions.Or(op.Table.NonNullableColumns);
 498             nodeInfo.NonNullableDefinitions.And(nodeInfo.Definitions);
 499
 500             return nodeInfo;
 501         }
 502
 503         /// <summary>
 504         /// Computes a NodeInfo for an UnnestOp.
 505         /// Definitions = columns of the table produced by this Op
 506         /// Keys = none
 507         /// External References = the unnestVar + any external references of the
 508         ///   computed Var (if any)
 509         /// RowCount (default): MinRows = 0; MaxRows = *
 510         /// NonNullableDefinitions: default(empty)
 511         /// NonNullableInputDefinitions : default(empty) because cannot be used
 512         /// </summary>
 513         /// <param name="op"></param>
 514         /// <param name="n"></param>
 515         /// <returns></returns>
 516         public override NodeInfo Visit(UnnestOp op, Node n)
 517         {
 518             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
 519             foreach (Var v in op.Table.Columns)
 520             {
 521                 nodeInfo.LocalDefinitions.Set(v);
 522                 nodeInfo.Definitions.Set(v);
 523             }
 524
 525             // Process keys if it's a TVF with inferred keys, otherwise - no keys.
 526             if (n.Child0.Op.OpType == OpType.VarDef && n.Child0.Child0.Op.OpType == OpType.Function && op.Table.Keys.Count > 0)
 527             {
 528                 // This is a TVF case.
 529                 // Get table's keys - but only if they have been referenced.
 530                 if (op.Table.ReferencedColumns.Subsumes(op.Table.Keys))
 531                 {
 532                     nodeInfo.Keys.InitFrom(op.Table.Keys);
 533                 }
 534             }
 535             else
 536             {
 537                 // no keys
 538                 Debug.Assert(nodeInfo.Keys.NoKeys, "UnnestOp should have no keys in all cases except TVFs mapped to entities.");
 539             }
 540
 541             // If I have a child, then my external references are my child's external references.
 542             // Otherwise, my external reference is my unnestVar
 543             if (n.HasChild0)
 544             {
 545                 NodeInfo childNodeInfo = GetNodeInfo(n.Child0);
 546                 nodeInfo.ExternalReferences.Or(childNodeInfo.ExternalReferences);
 547             }
 548             else
 549             {
 550                 nodeInfo.ExternalReferences.Set(op.Var);
 551             }
 552
 553             return nodeInfo;
 554         }
 555
 556         /// <summary>
 557         /// Walk through the computed vars defined by a VarDefListNode, and look for
 558         /// "simple" Var renames. Build up a mapping from original Vars to the renamed Vars
 559         /// </summary>
 560         /// <param name="varDefListNode">the varDefListNode subtree</param>
 561         /// <returns>A dictionary of Var->Var renames</returns>
 562         internal static Dictionary<Var, Var> ComputeVarRemappings(Node varDefListNode)
 563         {
 564             Debug.Assert(varDefListNode.Op.OpType == OpType.VarDefList);
 565
 566             Dictionary<Var, Var> varMap = new Dictionary<Var, Var>();
 567             foreach (Node varDefNode in varDefListNode.Children)
 568             {
 569                 VarRefOp varRefOp = varDefNode.Child0.Op as VarRefOp;
 570                 if (varRefOp != null)
 571                 {
 572                     VarDefOp varDefOp = varDefNode.Op as VarDefOp;
 573                     Debug.Assert(varDefOp != null);
 574                     varMap[varRefOp.Var] = varDefOp.Var;
 575                 }
 576             }
 577             return varMap;
 578         }
 579
 580         /// <summary>
 581         /// Computes a NodeInfo for a ProjectOp.
 582         /// Definitions = the Vars property of this Op
 583         /// LocalDefinitions = list of computed Vars produced by this node
 584         /// Keys = Keys of the input Relop (if they are all preserved)
 585         /// External References = any external references from the computed Vars
 586         /// RowCount = Input's RowCount
 587         /// NonNullabeDefinitions = Outputs that are either among the NonNullableDefinitions of the child or
 588         ///                         are constants defined on this node
 589         /// NonNullableInputDefinitions = NonNullableDefinitions of the child
 590         /// </summary>
 591         /// <param name="op">The ProjectOp</param>
 592         /// <param name="n">corresponding Node</param>
 593         /// <returns></returns>
 594         public override NodeInfo Visit(ProjectOp op, Node n)
 595         {
 596             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
 597
 598             // Walk through my outputs and identify my "real" definitions
 599             ExtendedNodeInfo relOpChildNodeInfo = GetExtendedNodeInfo(n.Child0);
 600             // In the first pass, only definitions of the child are considered
 601             // to be definitions - everything else is an external reference
 602             foreach (Var v in op.Outputs)
 603             {
 604                 if (relOpChildNodeInfo.Definitions.IsSet(v))
 605                 {
 606                     nodeInfo.Definitions.Set(v);
 607                 }
 608                 else
 609                 {
 610                     nodeInfo.ExternalReferences.Set(v);
 611                 }
 612             }
 613
 614             //Nonnullable definitions
 615             nodeInfo.NonNullableDefinitions.InitFrom(relOpChildNodeInfo.NonNullableDefinitions);
 616             nodeInfo.NonNullableDefinitions.And(op.Outputs);
 617             nodeInfo.NonNullableVisibleDefinitions.InitFrom(relOpChildNodeInfo.NonNullableDefinitions);
 618
 619             // Local definitions
 620             foreach (Node chi in n.Child1.Children)
 621             {
 622                 VarDefOp varDefOp = chi.Op as VarDefOp;
 623                 NodeInfo chiNodeInfo = GetNodeInfo(chi.Child0);
 624                 nodeInfo.LocalDefinitions.Set(varDefOp.Var);
 625                 nodeInfo.ExternalReferences.Clear(varDefOp.Var);
 626                 nodeInfo.Definitions.Set(varDefOp.Var);
 627                 nodeInfo.ExternalReferences.Or(chiNodeInfo.ExternalReferences);
 628
 629                 if (IsDefinitionNonNullable(chi.Child0, nodeInfo.NonNullableVisibleDefinitions))
 630                 {
 631                     nodeInfo.NonNullableDefinitions.Set(varDefOp.Var);
 632                 }
 633             }
 634             nodeInfo.ExternalReferences.Minus(relOpChildNodeInfo.Definitions);
 635             nodeInfo.ExternalReferences.Or(relOpChildNodeInfo.ExternalReferences);
 636
 637             // Get the set of keys - simply the list of my child's keys, unless
 638             // they're not all defined
 639             nodeInfo.Keys.NoKeys = true;
 640             if (!relOpChildNodeInfo.Keys.NoKeys)
 641             {
 642                 // Check to see if any of my child's keys have been left by the wayside
 643                 // in that case, mark this node as having no keys
 644                 VarVec keyVec = m_command.CreateVarVec(relOpChildNodeInfo.Keys.KeyVars);
 645                 Dictionary<Var, Var> varRenameMap = ComputeVarRemappings(n.Child1);
 646                 VarVec mappedKeyVec = keyVec.Remap(varRenameMap);
 647                 VarVec mappedKeyVecClone = mappedKeyVec.Clone();
 648                 VarVec opVars = m_command.CreateVarVec(op.Outputs);
 649                 mappedKeyVec.Minus(opVars);
 650                 if (mappedKeyVec.IsEmpty)
 651                 {
 652                     nodeInfo.Keys.InitFrom(mappedKeyVecClone);
 653                 }
 654             }
 655
 656             nodeInfo.InitRowCountFrom(relOpChildNodeInfo);
 657             return nodeInfo;
 658         }
 659
 660         /// <summary>
 661         /// Computes a NodeInfo for a FilterOp.
 662         /// Definitions = Definitions of the input Relop
 663         /// LocalDefinitions = None
 664         /// Keys = Keys of the input Relop
 665         /// External References = any external references from the input + any external
 666         ///    references from the predicate
 667         /// MaxOneRow = Input's RowCount
 668         ///    If the predicate is a "false" predicate, then max RowCount is zero
 669         ///    If we can infer additional info from the key-selector, we may be
 670         ///     able to get better estimates
 671         /// NonNullabeDefinitions = NonNullabeDefinitions of the input RelOp
 672         /// NonNullableInputDefinitions = NonNullabeDefinitions of the input RelOp
 673         /// </summary>
 674         /// <param name="op">The FilterOp</param>
 675         /// <param name="n">corresponding Node</param>
 676         /// <returns></returns>
 677         public override NodeInfo Visit(FilterOp op, Node n)
 678         {
 679             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
 680             ExtendedNodeInfo relOpChildNodeInfo = GetExtendedNodeInfo(n.Child0);
 681             NodeInfo predNodeInfo = GetNodeInfo(n.Child1);
 682
 683             // definitions are my child's definitions
 684             nodeInfo.Definitions.Or(relOpChildNodeInfo.Definitions);
 685             // No local definitions
 686
 687             // My external references are my child's external references + those made
 688             // by my predicate
 689             nodeInfo.ExternalReferences.Or(relOpChildNodeInfo.ExternalReferences);
 690             nodeInfo.ExternalReferences.Or(predNodeInfo.ExternalReferences);
 691             nodeInfo.ExternalReferences.Minus(relOpChildNodeInfo.Definitions);
 692
 693             // my keys are my child's keys
 694             nodeInfo.Keys.InitFrom(relOpChildNodeInfo.Keys);
 695
 696             //The non-nullable definitions are same as these of the child
 697             nodeInfo.NonNullableDefinitions.InitFrom(relOpChildNodeInfo.NonNullableDefinitions);
 698             nodeInfo.NonNullableVisibleDefinitions.InitFrom(relOpChildNodeInfo.NonNullableDefinitions);
 699
 700             // inherit max RowCount from child; set min RowCount to 0, because
 701             // we require way more analysis to do anything smarter
 702             nodeInfo.MinRows = RowCount.Zero;
 703             // If the predicate is a "false" predicate, then we know that MaxRows
 704             // is zero as well
 705             ConstantPredicateOp predicate = n.Child1.Op as ConstantPredicateOp;
 706             if (predicate != null && predicate.IsFalse)
 707             {
 708                 nodeInfo.MaxRows = RowCount.Zero;
 709             }
 710             else
 711             {
 712                 nodeInfo.MaxRows = relOpChildNodeInfo.MaxRows;
 713             }
 714             return nodeInfo;
 715         }
 716
 717         /// <summary>
 718         /// Computes a NodeInfo for a GroupByOp.
 719         /// Definitions = Keys + aggregates
 720         /// LocalDefinitions = Keys + Aggregates
 721         /// Keys = GroupBy Keys
 722         /// External References = any external references from the input + any external
 723         ///    references from the local computed Vars
 724         /// RowCount =
 725         ///          (1,1) if no group-by keys;
 726         ///          otherwise if input MinRows is 1 then (1, input MaxRows);
 727         ///          otherwise (0, input MaxRows)
 728         /// NonNullableDefinitions: non-nullable keys
 729         /// NonNullableInputDefinitions : default(empty)
 730         /// </summary>
 731         /// <param name="op">The GroupByOp</param>
 732         /// <param name="n">corresponding Node</param>
 733         /// <returns></returns>
 734         protected override NodeInfo VisitGroupByOp(GroupByBaseOp op, Node n)
 735         {
 736             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
 737             ExtendedNodeInfo relOpChildNodeInfo = GetExtendedNodeInfo(n.Child0);
 738
 739             // all definitions are my outputs
 740             nodeInfo.Definitions.InitFrom(op.Outputs);
 741             nodeInfo.LocalDefinitions.InitFrom(nodeInfo.Definitions);
 742             // my definitions are the keys and aggregates I define myself
 743
 744             // My references are my child's external references + those made
 745             // by my keys and my aggregates
 746             nodeInfo.ExternalReferences.Or(relOpChildNodeInfo.ExternalReferences);
 747             foreach (Node chi in n.Child1.Children)
 748             {
 749                 NodeInfo keyExprNodeInfo = GetNodeInfo(chi.Child0);
 750                 nodeInfo.ExternalReferences.Or(keyExprNodeInfo.ExternalReferences);
 751                 if (IsDefinitionNonNullable(chi.Child0, relOpChildNodeInfo.NonNullableDefinitions))
 752                 {
 753                     nodeInfo.NonNullableDefinitions.Set(((VarDefOp)chi.Op).Var);
 754                 }
 755             }
 756
 757             // Non-nullable definitions: also all the keys that come from the input
 758             nodeInfo.NonNullableDefinitions.Or(relOpChildNodeInfo.NonNullableDefinitions);
 759             nodeInfo.NonNullableDefinitions.And(op.Keys);
 760
 761             //Handle all aggregates
 762             for (int i = 2; i < n.Children.Count; i++)
 763             {
 764                 foreach (Node chi in n.Children[i].Children)
 765                 {
 766                     NodeInfo aggExprNodeInfo = GetNodeInfo(chi.Child0);
 767                     nodeInfo.ExternalReferences.Or(aggExprNodeInfo.ExternalReferences);
 768                 }
 769             }
 770
 771             // eliminate definitions of my input
 772             nodeInfo.ExternalReferences.Minus(relOpChildNodeInfo.Definitions);
 773
 774             // my keys are my grouping keys
 775             nodeInfo.Keys.InitFrom(op.Keys);
 776
 777             // row counts
 778             nodeInfo.MinRows = op.Keys.IsEmpty ? RowCount.One : (relOpChildNodeInfo.MinRows == RowCount.One ? RowCount.One : RowCount.Zero);
 779             nodeInfo.MaxRows = op.Keys.IsEmpty ? RowCount.One : relOpChildNodeInfo.MaxRows;
 780
 781             return nodeInfo;
 782         }
 783
 784         /// <summary>
 785         /// Computes a NodeInfo for a CrossJoinOp.
 786         /// Definitions = Definitions of my children
 787         /// LocalDefinitions = None
 788         /// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
 789         /// External References = any external references from the inputs
 790         /// RowCount: MinRows: min(min-rows of each child)
 791         ///              MaxRows: max(max-rows of each child)
 792         /// NonNullableDefinitions : The NonNullableDefinitions of the children
 793         /// NonNullableInputDefinitions : default(empty) because cannot be used
 794         /// </summary>
 795         /// <param name="op">The CrossJoinOp</param>
 796         /// <param name="n">corresponding Node</param>
 797         /// <returns></returns>
 798         public override NodeInfo Visit(CrossJoinOp op, Node n)
 799         {
 800             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
 801
 802             // No definitions of my own. Simply inherit from my children
 803             // My external references are the union of my children's external
 804             // references
 805             // And my keys are the concatenation of the keys of each of my
 806             // inputs
 807             List<KeyVec> keyVecList = new List<KeyVec>();
 808             RowCount maxCard = RowCount.Zero;
 809             RowCount minCard = RowCount.One;
 810             foreach (Node chi in n.Children)
 811             {
 812                 ExtendedNodeInfo chiNodeInfo = GetExtendedNodeInfo(chi);
 813                 nodeInfo.Definitions.Or(chiNodeInfo.Definitions);
 814                 nodeInfo.ExternalReferences.Or(chiNodeInfo.ExternalReferences);
 815                 keyVecList.Add(chiNodeInfo.Keys);
 816
 817                 nodeInfo.NonNullableDefinitions.Or(chiNodeInfo.NonNullableDefinitions);
 818
 819                 // Not entirely precise, but good enough
 820                 if (chiNodeInfo.MaxRows > maxCard)
 821                 {
 822                     maxCard = chiNodeInfo.MaxRows;
 823                 }
 824                 if (chiNodeInfo.MinRows < minCard)
 825                 {
 826                     minCard = chiNodeInfo.MinRows;
 827                 }
 828             }
 829             nodeInfo.Keys.InitFrom(keyVecList);
 830
 831             nodeInfo.SetRowCount(minCard, maxCard);
 832
 833             return nodeInfo;
 834         }
 835
 836         /// <summary>
 837         /// Computes a NodeInfo for an Inner/LeftOuter/FullOuter JoinOp.
 838         /// Definitions = Definitions of my children
 839         /// LocalDefinitions = None
 840         /// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
 841         /// External References = any external references from the inputs + any external
 842         ///    references from the join predicates
 843         /// RowCount:
 844         ///    FullOuterJoin: MinRows = 0, MaxRows = N
 845         ///    InnerJoin: MinRows = 0;
 846         ///               MaxRows = N; if both inputs have RowCount lesser than (or equal to) 1, then maxCard = 1
 847         ///    OuterJoin: MinRows = leftInput.MinRows
 848         ///               MaxRows = N; if both inputs have RowCount lesser than (or equal to) 1, then maxCard = 1
 849         /// NonNullableDefinitions:
 850         ///    FullOuterJoin: None.
 851         ///    InnerJoin: NonNullableDefinitions of both children
 852         ///    LeftOuterJoin: NonNullableDefinitions of the left child
 853         /// NonNullableInputDefinitions : NonNullabeDefinitions of both children
 854         /// </summary>
 855         /// <param name="op">The JoinOp</param>
 856         /// <param name="n">corresponding Node</param>
 857         /// <returns></returns>
 858         protected override NodeInfo VisitJoinOp(JoinBaseOp op, Node n)
 859         {
 860             if (!(op.OpType == OpType.InnerJoin ||
 861                   op.OpType == OpType.LeftOuterJoin ||
 862                   op.OpType == OpType.FullOuterJoin))
 863             {
 864                 return Unimplemented(n);
 865             }
 866
 867             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
 868
 869             // No definitions of my own. Simply inherit from my children
 870             // My external references are the union of my children's external
 871             // references
 872             // And my keys are the concatenation of the keys of each of my
 873             // inputs
 874             ExtendedNodeInfo leftRelOpNodeInfo = GetExtendedNodeInfo(n.Child0);
 875             ExtendedNodeInfo rightRelOpNodeInfo = GetExtendedNodeInfo(n.Child1);
 876             NodeInfo predNodeInfo = GetNodeInfo(n.Child2);
 877
 878             nodeInfo.Definitions.Or(leftRelOpNodeInfo.Definitions);
 879             nodeInfo.Definitions.Or(rightRelOpNodeInfo.Definitions);
 880
 881             nodeInfo.ExternalReferences.Or(leftRelOpNodeInfo.ExternalReferences);
 882             nodeInfo.ExternalReferences.Or(rightRelOpNodeInfo.ExternalReferences);
 883             nodeInfo.ExternalReferences.Or(predNodeInfo.ExternalReferences);
 884             nodeInfo.ExternalReferences.Minus(nodeInfo.Definitions);
 885
 886             nodeInfo.Keys.InitFrom(leftRelOpNodeInfo.Keys, rightRelOpNodeInfo.Keys);
 887
 888             //Non-nullable definitions
 889             if (op.OpType == OpType.InnerJoin || op.OpType == OpType.LeftOuterJoin)
 890             {
 891                 nodeInfo.NonNullableDefinitions.InitFrom(leftRelOpNodeInfo.NonNullableDefinitions);
 892             }
 893             if (op.OpType == OpType.InnerJoin)
 894             {
 895                 nodeInfo.NonNullableDefinitions.Or(rightRelOpNodeInfo.NonNullableDefinitions);
 896             }
 897             nodeInfo.NonNullableVisibleDefinitions.InitFrom(leftRelOpNodeInfo.NonNullableDefinitions);
 898             nodeInfo.NonNullableVisibleDefinitions.Or(rightRelOpNodeInfo.NonNullableDefinitions);
 899
 900             RowCount maxRows;
 901             RowCount minRows;
 902             if (op.OpType == OpType.FullOuterJoin)
 903             {
 904                 minRows = RowCount.Zero;
 905                 maxRows = RowCount.Unbounded;
 906             }
 907             else
 908             {
 909                 if ((leftRelOpNodeInfo.MaxRows > RowCount.One) ||
 910                     (rightRelOpNodeInfo.MaxRows > RowCount.One))
 911                 {
 912                     maxRows = RowCount.Unbounded;
 913                 }
 914                 else
 915                 {
 916                     maxRows = RowCount.One;
 917                 }
 918
 919                 if (op.OpType == OpType.LeftOuterJoin)
 920                 {
 921                     minRows = leftRelOpNodeInfo.MinRows;
 922                 }
 923                 else
 924                 {
 925                     minRows = RowCount.Zero;
 926                 }
 927             }
 928
 929             nodeInfo.SetRowCount(minRows, maxRows);
 930
 931             return nodeInfo;
 932         }
 933
 934         /// <summary>
 935         /// Computes a NodeInfo for a CrossApply/OuterApply op.
 936         /// Definitions = Definitions of my children
 937         /// LocalDefinitions = None
 938         /// Keys = Concatenation of the keys of my children (if every one of them has keys; otherwise, null)
 939         /// External References = any external references from the inputs
 940         /// RowCount:
 941         ///    CrossApply: minRows=0; MaxRows=Unbounded
 942         ///         (MaxRows = 1, if both inputs have MaxRow less than or equal to 1)
 943         ///    OuterApply: minRows=leftInput.MinRows; MaxRows=Unbounded
 944         ///         (MaxRows = 1, if both inputs have MaxRow less than or equal to 1)
 945         /// NonNullableDefinitions =
 946         ///    CrossApply: NonNullableDefinitions of both children
 947         ///    OuterApply: NonNullableDefinitions of the left child
 948         /// NonNullableInputDefinitions = NonNullabeDefinitions of both children
 949         /// </summary>
 950         /// <param name="op">The ApplyOp</param>
 951         /// <param name="n">corresponding Node</param>
 952         /// <returns></returns>
 953         protected override NodeInfo VisitApplyOp(ApplyBaseOp op, Node n)
 954         {
 955             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
 956
 957             ExtendedNodeInfo leftRelOpNodeInfo = GetExtendedNodeInfo(n.Child0);
 958             ExtendedNodeInfo rightRelOpNodeInfo = GetExtendedNodeInfo(n.Child1);
 959
 960             nodeInfo.Definitions.Or(leftRelOpNodeInfo.Definitions);
 961             nodeInfo.Definitions.Or(rightRelOpNodeInfo.Definitions);
 962
 963             nodeInfo.ExternalReferences.Or(leftRelOpNodeInfo.ExternalReferences);
 964             nodeInfo.ExternalReferences.Or(rightRelOpNodeInfo.ExternalReferences);
 965             nodeInfo.ExternalReferences.Minus(nodeInfo.Definitions);
 966
 967             nodeInfo.Keys.InitFrom(leftRelOpNodeInfo.Keys, rightRelOpNodeInfo.Keys);
 968
 969             //NonNullableDefinitions
 970             nodeInfo.NonNullableDefinitions.InitFrom(leftRelOpNodeInfo.NonNullableDefinitions);
 971             if (op.OpType == OpType.CrossApply)
 972             {
 973                 nodeInfo.NonNullableDefinitions.Or(rightRelOpNodeInfo.NonNullableDefinitions);
 974             }
 975             nodeInfo.NonNullableVisibleDefinitions.InitFrom(leftRelOpNodeInfo.NonNullableDefinitions);
 976             nodeInfo.NonNullableVisibleDefinitions.Or(rightRelOpNodeInfo.NonNullableDefinitions);
 977
 978             RowCount maxRows;
 979             if (leftRelOpNodeInfo.MaxRows <= RowCount.One &&
 980                 rightRelOpNodeInfo.MaxRows <= RowCount.One)
 981             {
 982                 maxRows = RowCount.One;
 983             }
 984             else
 985             {
 986                 maxRows = RowCount.Unbounded;
 987             }
 988             RowCount minRows = (op.OpType == OpType.CrossApply) ? RowCount.Zero : leftRelOpNodeInfo.MinRows;
 989             nodeInfo.SetRowCount(minRows, maxRows);
 990
 991             return nodeInfo;
 992         }
 993
 994         /// <summary>
 995         /// Computes a NodeInfo for SetOps (UnionAll, Intersect, Except).
 996         /// Definitions = OutputVars
 997         /// LocalDefinitions = OutputVars
 998         /// Keys = Output Vars for Intersect, Except. For UnionAll ??
 999         /// External References = any external references from the inputs
1000         /// RowCount: Min = 0, Max = unbounded.
1001         ///    For UnionAlls, MinRows = max(MinRows of left and right inputs)
1002         /// NonNullable definitions =
1003         ///     UnionAll - Columns that are NonNullableDefinitions on both (children) sides
1004         ///     Except  - Columns that are NonNullableDefinitions on the left child side
1005         ///     Intersect - Columns that are NonNullableDefinitions on either side
1006         /// NonNullableInputDefinitions = default(empty) because cannot be used
1007         /// </summary>
1008         /// <param name="op">The SetOp</param>
1009         /// <param name="n">corresponding Node</param>
1010         /// <returns></returns>
1011         protected override NodeInfo VisitSetOp(SetOp op, Node n)
1012         {
1013             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
1014
1015             // My definitions and my "all" definitions are simply my outputs
1016             nodeInfo.Definitions.InitFrom(op.Outputs);
1017             nodeInfo.LocalDefinitions.InitFrom(op.Outputs);
1018
1019             ExtendedNodeInfo leftChildNodeInfo = GetExtendedNodeInfo(n.Child0);
1020             ExtendedNodeInfo rightChildNodeInfo = GetExtendedNodeInfo(n.Child1);
1021
1022             RowCount minRows = RowCount.Zero;
1023
1024             // My external references are the external references of both of
1025             // my inputs
1026             nodeInfo.ExternalReferences.Or(leftChildNodeInfo.ExternalReferences);
1027             nodeInfo.ExternalReferences.Or(rightChildNodeInfo.ExternalReferences);
1028
1029             if (op.OpType == OpType.UnionAll)
1030             {
1031                 minRows = (leftChildNodeInfo.MinRows > rightChildNodeInfo.MinRows) ? leftChildNodeInfo.MinRows  : rightChildNodeInfo.MinRows;
1032             }
1033
1034             // for intersect, and exceptOps, the keys are simply the outputs.
1035             if (op.OpType == OpType.Intersect || op.OpType == OpType.Except)
1036             {
1037                 nodeInfo.Keys.InitFrom(op.Outputs);
1038             }
1039             else
1040             {
1041                 // UnionAlls are a lot more complicated.  If we've gone through
1042                 // keyPullup, we will have set some keys on it's input branches and
1043                 // what we need to do here is get the keys from each branch and re-map
1044                 // them to the output vars.
1045                 //
1046                 // If the branchDiscriminator is not set on the unionAllOp, then
1047                 // we haven't been through key pullup and we can't look at the keys
1048                 // that the child nodes have, because they're not discriminated.
1049                 //
1050                 // See the logic in KeyPullup, where we make sure that there are
1051                 // actually branch discriminators on the input branches.
1052                 UnionAllOp unionAllOp = (UnionAllOp)op;
1053
1054                 if (null == unionAllOp.BranchDiscriminator)
1055                 {
1056                     nodeInfo.Keys.NoKeys = true;
1057                 }
1058                 else
1059                 {
1060                     VarVec nodeKeys = m_command.CreateVarVec();
1061                     VarVec mappedKeyVec;
1062                     for (int i = 0; i < n.Children.Count; i++)
1063                     {
1064                         ExtendedNodeInfo childNodeInfo = n.Children[i].GetExtendedNodeInfo(m_command);
1065                         if (!childNodeInfo.Keys.NoKeys && !childNodeInfo.Keys.KeyVars.IsEmpty)
1066                         {
1067                             mappedKeyVec = childNodeInfo.Keys.KeyVars.Remap(unionAllOp.VarMap[i].GetReverseMap());
1068                             nodeKeys.Or(mappedKeyVec);
1069                         }
1070                         else
1071                         {
1072                             // Each branch had better have keys, or we can't continue.
1073                             nodeKeys.Clear();
1074                             break;
1075                         }
1076                     }
1077
1078                     // You might be tempted to ask: "Don't we need to add the branch discriminator
1079                     // to the keys as well?"  The reason we don't is that we wouldn't be here unless
1080                     // we have a branch discriminator variable, which implies we've pulled up keys on
1081                     // the inputs, and they'll already have the branch descriminator set in the keys
1082                     // of each input, so we don't need to add that...
1083                     if (nodeKeys.IsEmpty)
1084                     {
1085                         nodeInfo.Keys.NoKeys = true;
1086                     }
1087                     else
1088                     {
1089                         nodeInfo.Keys.InitFrom(nodeKeys);
1090                     }
1091                 }
1092             }
1093
1094             //Non-nullable definitions
1095             VarVec leftNonNullableVars = leftChildNodeInfo.NonNullableDefinitions.Remap(op.VarMap[0].GetReverseMap());
1096             nodeInfo.NonNullableDefinitions.InitFrom(leftNonNullableVars);
1097
1098             if (op.OpType != OpType.Except)
1099             {
1100                 VarVec rightNonNullableVars = rightChildNodeInfo.NonNullableDefinitions.Remap(op.VarMap[1].GetReverseMap());
1101                 if (op.OpType == OpType.Intersect)
1102                 {
1103                     nodeInfo.NonNullableDefinitions.Or(rightNonNullableVars);
1104                 }
1105                 else  //Union all
1106                 {
1107                     nodeInfo.NonNullableDefinitions.And(rightNonNullableVars);
1108                 }
1109             }
1110
1111             nodeInfo.NonNullableDefinitions.And(op.Outputs);
1112
1113             nodeInfo.MinRows = minRows;
1114             return nodeInfo;
1115         }
1116
1117         /// <summary>
1118         /// Computes a NodeInfo for a ConstrainedSortOp/SortOp.
1119         /// Definitions = Definitions of the input Relop
1120         /// LocalDefinitions = not allowed
1121         /// Keys = Keys of the input Relop
1122         /// External References = any external references from the input + any external
1123         ///    references from the keys
1124         /// RowCount = Input's RowCount
1125         /// NonNullabeDefinitions = NonNullabeDefinitions of the input RelOp
1126         /// NonNullableInputDefinitions = NonNullabeDefinitions of the input RelOp
1127         /// </summary>
1128         /// <param name="op">The SortOp</param>
1129         /// <param name="n">corresponding Node</param>
1130         /// <returns></returns>
1131         protected override NodeInfo VisitSortOp(SortBaseOp op, Node n)
1132         {
1133             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
1134             ExtendedNodeInfo relOpChildNodeInfo = GetExtendedNodeInfo(n.Child0);
1135
1136             // definitions are my child's definitions
1137             nodeInfo.Definitions.Or(relOpChildNodeInfo.Definitions);
1138
1139             // My references are my child's external references + those made
1140             // by my sort keys
1141             nodeInfo.ExternalReferences.Or(relOpChildNodeInfo.ExternalReferences);
1142             nodeInfo.ExternalReferences.Minus(relOpChildNodeInfo.Definitions);
1143
1144             // my keys are my child's keys
1145             nodeInfo.Keys.InitFrom(relOpChildNodeInfo.Keys);
1146
1147             //Non-nullable definitions are same as the input
1148             nodeInfo.NonNullableDefinitions.InitFrom(relOpChildNodeInfo.NonNullableDefinitions);
1149             nodeInfo.NonNullableVisibleDefinitions.InitFrom(relOpChildNodeInfo.NonNullableDefinitions);
1150
1151             //Row counts are same as the input
1152             nodeInfo.InitRowCountFrom(relOpChildNodeInfo);
1153
1154             // For constrained sort, if the Limit value is Constant(1) and WithTies is false,
1155             // then MinRows and MaxRows can be adjusted to 0, 1.
1156             if (OpType.ConstrainedSort == op.OpType &&
1157                 OpType.Constant == n.Child2.Op.OpType &&
1158                 !((ConstrainedSortOp)op).WithTies)
1159             {
1160                 ConstantBaseOp constOp = (ConstantBaseOp)n.Child2.Op;
1161                 if(TypeHelpers.IsIntegerConstant(constOp.Type, constOp.Value, 1))
1162                 {
1163                     nodeInfo.SetRowCount(RowCount.Zero, RowCount.One);
1164                 }
1165             }
1166
1167             return nodeInfo;
1168         }
1169
1170         /// <summary>
1171         /// Computes a NodeInfo for Distinct.
1172         /// Definitions = OutputVars that are not external references
1173         /// LocalDefinitions = None
1174         /// Keys = Output Vars
1175         /// External References = any external references from the inputs
1176         /// RowCount = Input's RowCount
1177         /// NonNullabeDefinitions : NonNullabeDefinitions of the input RelOp that are outputs
1178         /// NonNullableInputDefinitions : default(empty) because cannot be used
1179         /// </summary>
1180         /// <param name="op">The DistinctOp</param>
1181         /// <param name="n">corresponding Node</param>
1182         /// <returns></returns>
1183         public override NodeInfo Visit(DistinctOp op, Node n)
1184         {
1185             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
1186
1187             //#497217 - The parameters should not be included as keys
1188             nodeInfo.Keys.InitFrom(op.Keys, true);
1189
1190             // external references - inherit from child
1191             ExtendedNodeInfo childNodeInfo = GetExtendedNodeInfo(n.Child0);
1192             nodeInfo.ExternalReferences.InitFrom(childNodeInfo.ExternalReferences);
1193
1194             // no local definitions - definitions are just the keys that are not external references
1195             foreach (Var v in op.Keys)
1196             {
1197                 if (childNodeInfo.Definitions.IsSet(v))
1198                 {
1199                     nodeInfo.Definitions.Set(v);
1200                 }
1201                 else
1202                 {
1203                     nodeInfo.ExternalReferences.Set(v);
1204                 }
1205             }
1206
1207             //Non-nullable definitions
1208             nodeInfo.NonNullableDefinitions.InitFrom(childNodeInfo.NonNullableDefinitions);
1209             nodeInfo.NonNullableDefinitions.And(op.Keys);
1210
1211             nodeInfo.InitRowCountFrom(childNodeInfo);
1212             return nodeInfo;
1213         }
1214
1215         /// <summary>
1216         /// Compute NodeInfo for a SingleRowOp.
1217         /// Definitions = child's definitions
1218         /// Keys = child's keys
1219         /// Local Definitions = none
1220         /// External references = child's external references
1221         /// RowCount=(0,1)
1222         /// NonNullabeDefinitions = NonNullabeDefinitions of the input RelOp
1223         /// NonNullableInputDefinitions : default(empty) because cannot be used
1224         /// </summary>
1225         /// <param name="op">The SingleRowOp</param>
1226         /// <param name="n">current subtree</param>
1227         /// <returns>NodeInfo for this node</returns>
1228         public override NodeInfo Visit(SingleRowOp op, Node n)
1229         {
1230             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
1231             ExtendedNodeInfo childNodeInfo = GetExtendedNodeInfo(n.Child0);
1232             nodeInfo.Definitions.InitFrom(childNodeInfo.Definitions);
1233             nodeInfo.Keys.InitFrom(childNodeInfo.Keys);
1234             nodeInfo.ExternalReferences.InitFrom(childNodeInfo.ExternalReferences);
1235             nodeInfo.NonNullableDefinitions.InitFrom(childNodeInfo.NonNullableDefinitions);
1236             nodeInfo.SetRowCount(RowCount.Zero, RowCount.One);
1237             return nodeInfo;
1238         }
1239
1240         /// <summary>
1241         /// SingleRowTableOp
1242         /// No definitions, external references, non-nullable definitions
1243         /// Keys = empty list (not the same as "no keys")
1244         /// RowCount = (1,1)
1245         /// </summary>
1246         /// <param name="op">the SingleRowTableOp</param>
1247         /// <param name="n">current subtree</param>
1248         /// <returns>nodeInfo for this subtree</returns>
1249         public override NodeInfo Visit(SingleRowTableOp op, Node n)
1250         {
1251             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
1252             nodeInfo.Keys.NoKeys = false;
1253             nodeInfo.SetRowCount(RowCount.One, RowCount.One);
1254             return nodeInfo;
1255         }
1256
1257         #endregion
1258
1259         #region PhysicalOps
1260         /// <summary>
1261         /// Computes a NodeInfo for a PhysicalProjectOp.
1262         /// Definitions = OutputVars
1263         /// LocalDefinitions = None
1264         /// Keys = None
1265         /// External References = any external references from the inputs
1266         /// RowCount=default
1267         /// NonNullabeDefinitions = NonNullabeDefinitions of the input RelOp that are among the definitions
1268         /// NonNullableInputDefinitions = NonNullabeDefinitions of the input RelOp
1269         /// </summary>
1270         /// <param name="op">The PhysicalProjectOp</param>
1271         /// <param name="n">corresponding Node</param>
1272         /// <returns></returns>
1273         public override NodeInfo Visit(PhysicalProjectOp op, Node n)
1274         {
1275             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
1276             foreach (Node chi in n.Children)
1277             {
1278                 NodeInfo childNodeInfo = GetNodeInfo(chi);
1279                 nodeInfo.ExternalReferences.Or(childNodeInfo.ExternalReferences);
1280             }
1281             nodeInfo.Definitions.InitFrom(op.Outputs);
1282             nodeInfo.LocalDefinitions.InitFrom(nodeInfo.Definitions);
1283
1284             //
1285             // Inherit the keys from the child - but only if all the columns were projected
1286             // out
1287             //
1288             ExtendedNodeInfo driverChildNodeInfo = GetExtendedNodeInfo(n.Child0);
1289             if (!driverChildNodeInfo.Keys.NoKeys)
1290             {
1291                 VarVec missingKeys = m_command.CreateVarVec(driverChildNodeInfo.Keys.KeyVars);
1292                 missingKeys.Minus(nodeInfo.Definitions);
1293                 if (missingKeys.IsEmpty)
1294                 {
1295                     nodeInfo.Keys.InitFrom(driverChildNodeInfo.Keys);
1296                 }
1297             }
1298
1299             //Non-nullable definitions
1300             nodeInfo.NonNullableDefinitions.Or(driverChildNodeInfo.NonNullableDefinitions);
1301             nodeInfo.NonNullableDefinitions.And(nodeInfo.Definitions);
1302             nodeInfo.NonNullableVisibleDefinitions.Or(driverChildNodeInfo.NonNullableVisibleDefinitions);
1303
1304             return nodeInfo;
1305         }
1306
1307         /// <summary>
1308         /// Computes a NodeInfo for a NestOp (SingleStream/MultiStream).
1309         /// Definitions = OutputVars
1310         /// LocalDefinitions = Collection Vars
1311         /// Keys = Keys of my child
1312         /// External References = any external references from the inputs
1313         /// RowCount=default
1314         /// </summary>
1315         /// <param name="op">The NestOp</param>
1316         /// <param name="n">corresponding Node</param>
1317         /// <returns></returns>
1318         protected override NodeInfo VisitNestOp(NestBaseOp op, Node n)
1319         {
1320             SingleStreamNestOp ssnOp = op as SingleStreamNestOp;
1321             ExtendedNodeInfo nodeInfo = InitExtendedNodeInfo(n);
1322
1323             foreach (CollectionInfo ci in op.CollectionInfo)
1324             {
1325                 nodeInfo.LocalDefinitions.Set(ci.CollectionVar);
1326             }
1327             nodeInfo.Definitions.InitFrom(op.Outputs);
1328
1329             // get external references from each child
1330             foreach (Node chi in n.Children)
1331             {
1332                 nodeInfo.ExternalReferences.Or(GetExtendedNodeInfo(chi).ExternalReferences);
1333             }
1334
1335             // eliminate things I may have defined already (left correlation)
1336             nodeInfo.ExternalReferences.Minus(nodeInfo.Definitions);
1337
1338             // Keys are from the driving node only.
1339             if (ssnOp == null)
1340             {
1341                 nodeInfo.Keys.InitFrom(GetExtendedNodeInfo(n.Child0).Keys);
1342             }
1343             else
1344             {
1345                 nodeInfo.Keys.InitFrom(ssnOp.Keys);
1346             }
1347             return nodeInfo;
1348         }
1349
1350         #endregion
1351
1352         #endregion
1353     }
1354 }