JOIN 查询的行估计

Question

PostgreSQL 如何估计 JOIN 查询中的行数，例如：

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

Answer 1

假设涉及到的数据类型是timestamp with time time zone（其实并不重要，我们会看到），join选择性估计函数可以用：

SELECT oprjoin
FROM pg_operator
WHERE oprname = '<'
  AND oprleft = 'timestamptz'::regtype
  AND oprright = 'timestamptz'::regtype;

     oprjoin     
═════════════════
 scalarltjoinsel
(1 row)

那个函数定义在src/backend/utils/adt/selfuncs.c:

/*
 *      scalarltjoinsel - Join selectivity of "<" for scalars
 */
Datum
scalarltjoinsel(PG_FUNCTION_ARGS)
{
    PG_RETURN_FLOAT8(DEFAULT_INEQ_SEL);
}

这在src/include/utils/selfuncs.h中定义为

/* default selectivity estimate for inequalities such as "A < b" */
#define DEFAULT_INEQ_SEL  0.3333333333333333

因此，听起来很简单，PostgreSQL 将估计一个不等式连接条件将过滤掉三分之二的行。由于有两个这样的条件，选择性成倍增加，PostgreSQL会估计结果的行数为

(#rows in R) * (#rows in S) / 9

到目前为止，PostgreSQL 没有任何交叉table 的统计数据可以使它不那么粗糙。

Answer 2

手册中有一章恰好解决了您的问题：

Row Estimation Examples

其中包括对 Laurenz 提供的内容的解释。

但这还不是全部。我们还需要基础 table 的行数（基数）。 Postgres 使用 src/backend/utils/adt/plancat.c 中定义的 estimate_rel_size():

 /*
  * estimate_rel_size - estimate # pages and # tuples in a table or index
  *
  * We also estimate the fraction of the pages that are marked all-visible in
  * the visibility map, for use in estimation of index-only scans.
  *
  * If attr_widths isn't NULL, it points to the zero-index entry of the
  * relation's attr_widths[] cache; we fill this in if we have need to compute
  * the attribute widths for estimation purposes.
  */
 void
 estimate_rel_size(Relation rel, int32 *attr_widths,
                   BlockNumber *pages, double *tuples, double *allvisfrac)
 ...

这是一个最小的 SQL 查询来重现计算（忽略一些特殊情况）：

SELECT (reltuples / relpages * (pg_relation_size(oid) / 8192))::bigint
FROM   pg_class
WHERE  oid = 'mytable'::regclass;  -- your table here

更多详情：

Fast way to discover the row count of a table in PostgreSQL

例子

CREATE TEMP TABLE r(id serial, start_time timestamptz, end_time timestamptz);
CREATE TEMP TABLE s(id serial, start_time timestamptz, end_time timestamptz);

INSERT INTO r(start_time, end_time)
SELECT now(), now()  -- actual values don't matter for this particular case
FROM generate_series (1, 5000);

INSERT INTO s(start_time, end_time)
SELECT now(), now()
FROM generate_series (1, 10000);

VACUUM r, s;  -- set reltuples & relpages in pg_class

-- add 2000 rows to S
INSERT INTO s(start_time, end_time)
SELECT now(), now()
FROM generate_series (1, 2000);

pg_class 仍然有 5000 和 10000 个 reltuples，但我们知道 R 和 S 中有 5000 和 12000 行。（因为这些是临时 tables，它们不在 autovacuum 范围内，因此数字永远不会自动更新。）检查：

SELECT relname, reltuples, relpages  -- 5000 | 10000
FROM   pg_class c
WHERE  c.oid IN ('pg_temp.r'::regclass, 'pg_temp.s'::regclass);

SELECT count(*) FROM r; -- 5000
SELECT count(*) FROM s; -- 12000

查询计划：

EXPLAIN
SELECT *
FROM r, s
WHERE (r.start_time < s.end_time) AND (s.start_time < r.end_time);

'Nested Loop  (cost=0.00..1053004.31 rows=6683889 width=40)'
'  Join Filter: ((r.start_time < s.end_time) AND (s.start_time < r.end_time))'
'  ->  Seq Scan on s  (cost=0.00..197.31 rows=12031 width=20)'
'  ->  Materialize  (cost=0.00..107.00 rows=5000 width=20)'
'        ->  Seq Scan on r  (cost=0.00..82.00 rows=5000 width=20)'
'JIT:'
'  Functions: 6'
'  Options: Inlining true, Optimization true, Expressions true, Deforming true'

Postgres 估计 rows=12031 table s。一个很好的估计，算法有效。
由于 table 的物理大小不会自动缩小，因此删除行更容易导致估计值丢失。在主要 DELETE 之后 VACUUM ANALYZE 是个好主意。甚至 VACUUM FULL ANALYZE。参见：

VACUUM returning disk space to operating system

Postgres 期望 rows=6683889，这符合我们的期望（根据 Laurenz 的解释）：

SELECT 5000 * 12031 * 0.3333333333333333^2  -- 6683888.89

更好的查询

您的示例查询只是一个示例。但它恰好是一个糟糕的，因为同样可以通过 范围类型 和运算符更有效地实现。特别是 tstzrange and &&:

&& 的选择性？

SELECT oprjoin  -- areajoinsel
FROM pg_operator
WHERE oprname = '&&'
AND oprleft = 'anyrange'::regtype
AND oprright = 'anyrange'::regtype;

`src/backend/utils/adt/geoselfuncs.c中的源代码：

 Datum
 areajoinsel(PG_FUNCTION_ARGS)
 {
     PG_RETURN_FLOAT8(0.005);
 }

更多更具选择性 0.005 << 0.333！而且通常更现实。

EXPLAIN
SELECT *
FROM r, s
WHERE tstzrange(r.start_time, r.end_time) && tstzrange(s.start_time, s.end_time);

恰好是等价的，因为 tstzrange 默认包含下限并排除上限。我得到这个查询计划：

'Nested Loop  (cost=0.00..1203391.81 rows=300775 width=40)'
'  Join Filter: (tstzrange(r.start_time, r.end_time) && tstzrange(s.start_time, s.end_time))'
'  ->  Seq Scan on s  (cost=0.00..197.31 rows=12031 width=20)'
'  ->  Materialize  (cost=0.00..107.00 rows=5000 width=20)'
'        ->  Seq Scan on r  (cost=0.00..82.00 rows=5000 width=20)'
'JIT:'
'  Functions: 6'
'  Options: Inlining true, Optimization true, Expressions true, Deforming true'

我们的期望：

SELECT 5000 * 12031 * 0.005  -- 300775.000

这是宾果游戏！
并且可以通过索引有效地支持此查询，从而改变游戏规则...

JOIN 查询的行估计

Row estimation for JOIN queries

postgresql

statistics

histogram

sql-execution-plan

例子

更好的查询