继承表联接优化

动机

我们使用 Postgres 托管一个数据仓库，其中包含生产和销售的每日报告。这些表按天进行分区，如下所示

CREATE TABLE production (id int, date timestamp, bigint quantity, ...);
CREATE TABLE production_jan_1 (
  CHECK ('2009-01-01'<=date AND date<'2009-01-02')
) INHERITS (production);
CREATE TABLE production_jan_2 (
  CHECK ('2009-01-02'<=date AND date<'2009-01-03')
) INHERITS (production);
...

CREATE TABLE sales(id int, date timestamp, price float, ...);
CREATE TABLE sales_jan_1 (
  CHECK ('2009-01-01'<=date AND date<'2009-01-02')
) INHERITS (sales);
CREATE TABLE sales_jan_2 (
  CHECK ('2009-01-02'<=date AND date<'2009-01-03')
) INHERITS (sales);
...

如果我们想知道 1 月 1 日生产了什么，我们会执行

SELECT id, sum(quantity) FROM production 
WHERE '2009-01-01'<=date AND date<'2009-01-02' 
GROUP BY id;

计划程序根据检查约束过滤表，并智能地仅扫描 production_jan_1。

如果我们想知道每天的销售额，查询如下

SELECT p.id, p.date, sum(s.price) FROM production p, sales s
WHERE p.date = s.date AND p.id = s.id
GROUP BY p.id, p.date

然后，计划程序将把每个层次结构视为单个表，并生成以下计划

Group aggregate
 -> merge join
  -> sort
   -> Append
    -> Seq Scan on production
    -> Seq Scan on production_jan_1
    -> Seq Scan on production_jan_2
    -> ...
 -> sort
  -> Append
   -> Seq Scan on sales
   -> Seq Scan on sales_jan_1
   -> Seq Scan on sales_jan_2
   -> ...

我们希望能够使用检查约束直接联接子表，并生成以下计划

Hash aggregate
 -> Append
   -> Hash Join
     -> Seq Scan on production_jan_1
     -> Seq Scan on sales_jan_1
   -> Hash Join
     -> Seq Scan on production_jan_2
     -> Seq Scan on sales_jan_2
   -> ...

解决方案概述

我们算法背后的直觉如下

1. 检查是否可以直接联接子表
2. 获取子表约束
3. 查找可能的子联接
4. 为每个子联接生成计划
5. 组合来自子联接的结果

一个简单的 n^2 实现检查来自每对可能的子表的约束。

另一种方法将约束视为区间，并使用区间树来匹配子表。这提供了 n.log(n) 的复杂度。

下面的图表比较了两种方法在不同数量的子表下的情况

一个常见的情况是父表为空（并且没有约束），因此匹配算法仍然需要将父表与所有子表联接。我们建议在父表中添加一个空约束，以避免不必要的计划和执行工作。此优化的结果显示在下面

实现

建议的补丁已发布在邮件列表中：http://archives.postgresql.org/message-id/[email protected]

性能评估

我们通过改变 3 个因素评估了计划时间和执行时间

• 每个层次结构的子表数量
• 层次结构中的行数
• 查询中的联接数量

第一个图表显示了在每个层次结构中具有不同数量的子表时，使用补丁（功能开启）和不使用补丁（功能关闭）的计划时间差异。这些结果是通过执行联接 3 个层次结构的查询获得的，每个层次结构都分区到固定数量的子表中。

为了更好地了解情况，让我们考虑 730 个子表的情况。我们正在联接 3 个层次结构，每个层次结构都有 730 个子表。在关闭功能的情况下，优化器需要大约 2 秒来执行计划。这段时间用于为 2190 (3*730) 个表扫描找到最佳访问方法，以及为 3 个追加联接找到最佳联接方法。在开启功能的情况下，将完成相同的工作。此外，补丁将查看所有表的检查约束，以确定哪些子表可以联接在一起。在这种情况下，匹配是一对一匹配。因此，计划程序将找到最佳方法来联接每三个子表中的 2190 个不同的联接。所有这些工作都在不到 5 秒的时间内完成，但额外的计划时间在执行过程中获得回报。

以下显示了使用补丁（功能开启）和不使用补丁（功能关闭）的计划时间差异，在每个层次结构中有 730 个子表的情况下，联接 1 到 3 个联接。

最后一个图表显示了使用补丁（功能开启）和不使用补丁（功能关闭）的总执行时间，在进行 2 个联接（每个联接有 3 个层次结构，每个层次结构有 365 个子表）的情况下，总行数从 100K 变化到 500K。