在C.c_id>N过滤条件下，c_id.Min会增大到N，c_id.Max保持不变。而过滤后总行数c_id.distinct(after_filter)=(c_id.Max– N)/(c_id.Max–c_id.Min)*c_id.distinct(before_filter)
简单吧，但是注意哈，上面计算是在假设数据分布均匀的前提下完成的，而实际场景中数据分布很显然不可能均衡。数据分布通常 成概率分布，histograms在这里就要登场了，说白了它就是一个柱状分布图，如下图：
柱状图横坐标表示列值大小分布，纵坐标表示频率。假设N在如图所示位置，那过滤后总行数c_id.distinct(after_filter)＝ height(>N)/height(All)*c_id.distinct(before_filter)。
当然，上述所有计算都只是示意性计算，真实算法会复杂很多。另外，如果大家对group by 、limit等谓词的评估规则比较感兴趣 的话，可以阅读SparkSQL CBO的设计文档，这里就不再赘述。至此，通过各种评估规则以及原始表统计信息就可以计算出语法树 中所有中间节点的基本统计信息了，这是万里长征的第二步，也是至关重要的一步。接下来继续往前走，看看如何计算每种核心算 子的实际代价。
因为实现的原因设置的比较简单，有的会比较复杂。这一节主要来简单聊聊每个节点的执行代价，上文说了，一条执行路径的总代 价就是这条路径上所有节点的代价累加之和。
通常来讲，节点实际执行代价主要从两个维度来定义：CPU Cost以及IO Cost。为后续讲解方便起见，需要先行定义一些基本参数：
Hr：从HDFS上读取1byte数据所需代价
Hw：往HDFS上写入1byte数据所需代价
Tr：数据总条数（the number of tuples in the relation ）
Tsz：数据平均大小（Average size of the tuple in the relation
）
CPUc ： 两 值 比 较 所 需 CPU 资 源 代 价 （ CPU cost for a comparison in nano seconds ）
NEt：1byte数据通过网络在集群节点间传输花费代价（the average cost of transferring 1 byte over network in the Hadoop cluster from any node to any node ）
……
上文说过，每种算子的实际执行代价计算方式都不同，在此不可 能列举所有算子，就挑两个比较简单、容易理解的来分析，第一 个是Table Scan算子，第二个是Hash Join算子。
Table Scan算子 Scan算子一般位于语法树的叶子结点，直观上来讲这类算子只有IO Cost，CPU Cost为0。Table Scan Cost = IO Cost = Tr * Tsz * Hr，很简单，Tr * Tsz表示需要scan的数据总大小，再乘以Hr就是所需代价。OK，很直观，很简单。
Hash Join算子 以Broadcast Hash Join为例（如果看官对Broadcast Hash Join工作原理还不了解，可戳这里），假设大表分布在n个节点上，每 个 节 点 的 数 据 条 数 \ 平 均 大 小 分 别 为 Tr(R1)\Tsz(R1) ， Tr(R2)\Tsz(R2), … Tr(Rn)\Tsz(Rn) ， 小 表 数 据 条 数 为 Tr(Rsmall)\Tsz(Rsmall)，那么CPU代价和IO代价分别为：
CPU Cost = 小表构建Hash Table代价 ＋ 大表探测代价 ＝ Tr(Rsmall) * CPUc + (Tr(R1) + Tr(R2) + … + Tr(Rn)) * N * CPUc，此 处假设HashTable构建所需CPU资源远远高于两值简单比较代价，为N * CPUc
IO Cost = 小表scan代价 ＋ 小表广播代价 ＋ 大表scan代价 ＝ Tr(Rsmall) * Tsz(Rsmall) * Hr + n * Tr(Rsmall) * Tsz(Rsmall) * NEt + (Tr(R1)* Tsz(R1) + … + Tr(Rn) * Tsz(Rn)) * Hr
很显然，Hash Join算子相比Table Scan算子来讲稍稍复杂了一点，但是无论哪种算子，代价计算都和参与的数据总条数、数据平 均大小等因素直接相关，这也就是为什么在之前两个步骤中要不懈余力地计算中间结果相关详细的真正原因。可谓是步步为营、环 环相扣。这下好了，任意节点的实际代价都能评估出来，那么给定任意执行路径的代价必然也就很简单喽。
第四步：选择最优执行路径（代价最小执行路径）
这个思路很容易理解的，经过上述三步的努力，可以很容易地计算出任意一条给定路径的代价。那么你只需要找出所有可行的执行 路径，一个一个计算，就必然能找到一个代价最小的，也就是最优的执行路径。
这条路看起来确实很简单，但实际做起来却并不那么容易，为什么？所有可行的执行路径实在太多，所有路径都计算一遍，黄花菜 都凉了。那么有什么好的解决方案么？当然，其实看到这个标题－选择代价最小执行路径，就应该很容易想到－动态规划，如果你 没有想到，那只能说明你没有读过《数学之美》、没刷过LeetCode、没玩过ACM，ACM、LeetCode如果觉得太枯燥，那就去看 看《数学之美》，它会告诉你从当前这个你所在的地方开车去北京，如何使用动态规划选择一条最短的路线。在此不再赘述。