PostgreSQL如何对带时间区间重叠条件的JOIN查询做行数估算

你提到的查询语句如下：

EXPLAIN 
SELECT * 
FROM R, S 
WHERE (R.StartTime < S.EndTime) AND (S.StartTime < R.EndTime);

这是典型的判断两个时间区间重叠的不等值连接查询，PostgreSQL的估算流程分为以下几步：

• 第一步：读取基础统计信息
  首先从系统统计视图中获取两张表和关联字段的核心统计值：
  • 两张表的总行数：记R表行数为N_R，S表行数为N_S，数值来自pg_class.reltuples
  • 四个时间字段的取值范围、空值率、分布特征：R.StartTime、R.EndTime、S.StartTime、S.EndTime的最小值、最大值、直方图信息，数值来自pg_stats系统视图
• 第二步：计算单个不等值条件的选择率
  这类不等值连接不会用到等值连接常用的最常见值（MCV）统计，默认假设字段值在各自的取值区间内均匀分布，对于A.col < B.col类的跨表比较条件，单条件选择率的计算公式为：

  单条件选择率 = (B.col的最大值 - A.col的最小值) / (B.col的取值区间长度 + A.col的取值区间长度)
  

  计算结果会被限制在0到1之间，同时会扣除空值占比（空值无法满足比较条件，会被直接排除）。如果字段有直方图统计，会优先使用直方图的分布数据代替均匀分布假设，进一步提升准确率。
• 第三步：合并得到总选择率
  默认情况下PostgreSQL会假设两个条件相互独立，总选择率为两个单条件选择率的乘积。如果创建了关联字段的多列扩展统计信息，会用扩展统计的相关性数据修正总选择率，避免因为字段相关导致的估算偏差。
• 第四步：计算最终估算行数
  最终估算行数为两张表笛卡尔积的总行数乘以总选择率，公式为：

  估算行数 = N_R * N_S * 总选择率
  

补充说明：如果时间区间的分布极不均匀，又没有对应的直方图或扩展统计，这个估算结果可能会出现较大偏差，可以通过手动ANALYZE表、创建多列统计信息的方式提升估算准确率。

内容的提问来源于stack exchange，提问作者liana