查询基数估计与相关列

知道三分之二的人戴帽子、三分之二的人穿外套，不足以知道两者同时出现多少。它们可能常常一起出现，也可能尽量错开。把两个比例直接相乘是在添加一种假设。

优化器通常没有时间重新扫描全部数据算精确频数，所以用统计摘要作预测。这份预测可以很有用，但不是查询正确性的证明，也不是最坏复杂度上界。

同一DB-4的两种低估 ​

R的(x,y)依次为(1,1),(1,1),(1,1),(0,0),(1,1),(0,0)，故x与y完全相同。P(x=1)=P(y=1)=4/6。独立估计筛选后的行数为6×(2/3)²=8/3，真实为4；真实条件概率P(y=1|x=1)=1。

DB-4的键频数为R:{1:2,2:2,3:1,4:1}，S:{1:2,2:3,3:1,4:1,5:1}，故精确连接为4+6+1+1=12。V_R=4、V_S=5，均匀/包含近似得到6×8/5=9.6。值域包含在这里成立，错误来自不均匀频数。

过滤x=y=1之后，R只剩键1、2各两份，与S真实连接为4+6=10。若沿用独立筛选预测8/3，并给过滤后NDV预测2、S的NDV5，再作均匀估计，得到(8/3)×8/5=64/15。筛选误差与join分布误差叠加，但仍不应把它们混称一个“随机误差率”。

按两条/页向上取整，8/3和4都预测为2页。因此DB-4这一个小例并未仅因相关列误差改变分块连接的扫描轮数；声称已经翻转计划选择会超过证据。

真正越过内存阈值的另一个输入 ​

另取100条R，前10条x=y=1、其余90条x=y=0，各条键不同；固定每条64B，hash build预算2个128B帧，至多4条含开销的记录。独立假设预测100×0.1²=1条，而真实10条，占5页。预测的内存hash计划能装1条，实际不能装10条。运行时必须扩额、溢写或换算法，不能按原预算继续写出界。

这只证明算法分支/资源预测错误，不凭空给出额外I/O数。要计算溢写账本，还需给probe表、分区函数、最大分区和尾页大小，正如分区hash页理路分区哈希连接与倾斜退路Grace hash join · Partitioned hash join · Hash join以同键同分区和完整重复链证明bag正确性，精确计算分区尾页、哈希内存开销与热键无法递归拆散的边界。所做。

同NDV也能完全不相交 ​

R键为1,2，S键为3,4，各频数1。NDV都是2，套包含公式估计2份，实际0。把S改成1,2又得到2份。表大小和NDV完全相同，却有不同答案，说明摘要缺了重叠信息。

多列统计可记录联合频数、常见值组合或函数依赖，从而修复某些相关性；样本也可直接估计联合谓词。它们仍受样本量、罕见组合、参数值和统计过期影响。一个全相关例子被修好，不表示所有表达式都估准。

直方图中的重键宜单独保存，否则桶平均值会把热点抹平；hash build的资源风险尤其取决于最大键组，而不仅是总行数。预测范围比单个均值更能显示“可能溢写”的风险。

连接顺序DP理路连接顺序动态规划与物理属性Join order dynamic programming · Selinger optimization · Interesting orders明确搜索空间、子集状态与成本充分性，完整填三表连接表，并用有序子计划反例说明何时不能每子集只留一个方案。可以穷尽指定搜索空间，却只对输入给它的成本模型最优。系统应同时保留estimated rows与actual rows，定位误差最早出现的算子，再判断它如何影响后续成本；不能看到最终运行慢就归咎于枚举算法。

完成本页后，可用DB-4完整终点核对12份bag输出、三个I/O账本与两种恢复结果。