使用时间戳重叠和"PARTITION BY"加速PostgreSQL查询

Question

我在PostgreSQL 9.0中有一个相当大的表(500K - 1M行)，其中包含通用的"时间片"信息，也就是说，它确定另一个表中的一行("特性")何时有效。定义看起来像这样(稍微简化):

CREATE TABLE feature_timeslice
(
  timeslice_id int NOT NULL,
  feature_id int NOT NULL,
  valid_time_begin timestamp NOT NULL,
  valid_time_end timestamp,
  sequence_number smallint,
  -- Some other columns
  CONSTRAINT pk_feature_timeslice PRIMARY KEY (timeslice_id)
  -- Some other constraints
)
CREATE INDEX ix_feature_timeslice_feature_id
ON feature_timeslice USING btree (feature_id);

许多其他表的特定功能，然后连接到timeslice_id:

CREATE TABLE specific_feature_timeslice
(
  timeslice_id int NOT NULL,
  -- Other columns
  CONSTRAINT pk_specific_feature_timeslice PRIMARY KEY (timeslice_id),
  CONSTRAINT fk_specific_feature_timeslice_feature_timeslice FOREIGN KEY (timeslice_id) REFERENCES feature_timeslice (timeslice_id)
)

可能存在多个具有重叠有效时间段(开始/结束时间)的时间片，但是具有最高sequence_number的时间片具有优先级(再次，稍微简化，但足够接近)。我想有效地找到当前有效的行为每个feature_id，所以我有一个视图定义，像这样:

CREATE VIEW feature_timeslice_id_now
AS
    SELECT timeslice_id
    FROM
    (
        SELECT timeslice_id, rank() OVER
        (
            PARTITION BY feature_id
            ORDER BY sequence_number DESC, timeslice_id DESC
        )
        FROM feature_timeslice
        WHERE (current_timestamp AT TIME ZONE 'UTC', '0'::interval) OVERLAPS (valid_time_begin, COALESCE(valid_time_end, 'infinity'::timestamp))
    ) subq 
    WHERE subq.rank = 1

通常是这样查询的:

SELECT *
FROM specific_feature_timeslice sf
JOIN feature_timeslice_id_now n USING (timeslice_id)
WHERE sf.name = 'SOMETHING'

这是有效的，但它仍然有点太慢-需要1-2秒，即使可能只有1-5行返回，因为specific_feature_timeslice标准通常缩小了很多。(连接多个特性视图的更复杂的查询会变得非常慢。)我不知道如何让PostgreSQL更有效地做到这一点。查询计划如下所示:

   Join Filter: ((r.timeslice_id)::integer = (subq.timeslice_id)::integer)
  ->  Subquery Scan on subq  (cost=32034.36..37876.98 rows=835 width=4) (actual time=2086.125..5243.467 rows=250918 loops=1)
        Filter: (subq.rank = 1)
        ->  WindowAgg  (cost=32034.36..35790.33 rows=166932 width=10) (actual time=2086.110..4066.351 rows=250918 loops=1)
              ->  Sort  (cost=32034.36..32451.69 rows=166932 width=10) (actual time=2086.065..2654.971 rows=250918 loops=1)
                    Sort Key: feature_timeslice.feature_id, feature_timeslice.sequence_number, feature_timeslice.timeslice_id
                    Sort Method:  quicksort  Memory: 13898kB
                    ->  Seq Scan on feature_timeslice  (cost=0.00..17553.93 rows=166932 width=10) (actual time=287.270..1225.595 rows=250918 loops=1)
                          Filter: overlaps(timezone('UTC'::text, now()), (timezone('UTC'::text, now()) + '00:00:00'::interval), (valid_time_begin)::timestamp without time zone, COALESCE((valid_time_end)::timestamp without time zone, 'infinity'::timestamp without time zone))
  ->  Materialize  (cost=0.00..1093.85 rows=2 width=139) (actual time=0.002..0.007 rows=2 loops=250918)
        ->  Seq Scan on specific_feature_timeslice sf  (cost=0.00..1093.84 rows=2 width=139) (actual time=1.958..7.674 rows=2 loops=1)
              Filter: ((name)::text = 'SOMETHING'::text)
Total runtime: 10319.875 ms

实际上，我想对任何给定时间执行此查询，而不仅仅是当前时间。我为此定义了一个函数，它将时间作为参数，但是查询"now"是最常见的场景，所以即使我只能加快速度，这也是一个很大的改进。

== Edit ==

OK，我已经尝试规范化表，这两个答案建议-也就是说，我移动valid_time_begin和valid_time_end到一个单独的表，time_period。我还用WHERE NOT EXISTS ([better candidate time slice])替换了窗口函数。在这个过程中，我也升级到了PostgreSQL 9.1。有了这些，现在一些查询的速度是原来的两倍。查询计划看起来与wildplasser的答案相同。这很好，但没有我希望的那么好——从单个功能表中进行选择仍然需要一秒钟以上的时间。

理想情况下，我希望利用WHERE条件的选择性，如Erwin Brandstetter所说。如果我手工制作一个查询来做这件事，我得到的时间是15-30毫秒。这才像话呢!手工编写的查询看起来像这样:

WITH filtered_feature AS
(
    SELECT *
    FROM specific_feature_timeslice sf
    JOIN feature_timeslice ft USING (timeslice_id)
    WHERE sf.name = 'SOMETHING'
)
SELECT *
FROM filtered_feature ff
JOIN
(
    SELECT timeslice_id
    FROM filtered_feature candidate
    JOIN time_period candidate_time ON candidate.valid_time_period_id = candidate_time.id
    WHERE ('2011-09-26', '0'::interval) OVERLAPS (candidate_time.valid_time_begin, COALESCE(candidate_time.valid_time_end, 'infinity'::timestamp))
        AND NOT EXISTS
        (
            SELECT *
            FROM filtered_feature better
            JOIN time_period better_time ON better.valid_time_period_id = better_time.id
            WHERE ('2011-09-26', '0'::interval) OVERLAPS (better_time.valid_time_begin, COALESCE(better_time.valid_time_end, 'infinity'::timestamp))
                AND better.feature_id = candidate.feature_id AND better.timeslice_id != candidate.timeslice_id
                AND better.sequence_number > candidate.sequence_number
        )
) AS ft ON ff.timeslice_id = ft.timeslice_id

不幸的是，这太大太复杂，不能在普通查询中使用，因为普通查询可能会连接许多其他表。我需要某种方法将这个逻辑封装在一个函数(用于任意时间)或至少一个视图(用于当前时间)中，但是我不知道如何在让查询规划器首先过滤特定特性的同时做到这一点。如果我能传递一个行集到一个函数-但据我所知PostgreSQL不允许这样做。什么好主意吗?

==结论==

我最终使用PostgreSQL继承来解决这个问题(参见我的答案)，但如果不是Erwin Brandstetter的答案，我不会想到这个想法，所以赏金归他。wildplasser的答案也很有帮助，因为它让我消除了不必要的窗口函数，从而进一步加快了速度。非常感谢你们两位!

Answer 1

我最终使用PostgreSQL继承来解决这个问题，所以每个specific_feature_timeslice表都继承自feature_timeslice(而不是像以前那样引用它)。这允许"特性的选择性可以首先生效"——查询计划首先将查询范围缩小到我想要的几行。那么模式现在看起来像这样:

CREATE TABLE feature_timeslice
(
  timeslice_id int NOT NULL,
  feature_id int NOT NULL,
  valid_time_begin timestamp NOT NULL,
  valid_time_end timestamp,
  sequence_number smallint,
  -- Some other columns
  CONSTRAINT pk_feature_timeslice PRIMARY KEY (timeslice_id)
  -- Some other constraints
)
CREATE TABLE specific_feature_timeslice
(
  -- Feature-specific columns only, eg.
  name character varying(100),
  CONSTRAINT pk_specific_feature_timeslice PRIMARY KEY (timeslice_id)
)
INHERITS (feature_timeslice);
CREATE INDEX ix_specific_feature_timeslice_feature_id
ON specific_feature_timeslice (feature_id);

每个这样的派生表都有自己的函数来选择指定时间的当前行:

CREATE FUNCTION specific_feature_asof(effective_time timestamp)
RETURNS SETOF specific_feature_timeslice
AS $BODY$
    SELECT candidate.*
    FROM specific_feature_timeslice candidate
    WHERE ($1, '0'::interval) OVERLAPS (candidate.valid_time_begin, COALESCE(candidate.valid_time_end, 'infinity'::timestamp))
        AND NOT EXISTS
        (
            SELECT *
            FROM specific_feature_timeslice better
            WHERE ($1, '0'::interval) OVERLAPS (better.valid_time_begin, COALESCE(better.valid_time_end, 'infinity'::timestamp))
                AND better.feature_id = candidate.feature_id AND better.timeslice_id != candidate.timeslice_id AND better.sequence_number > candidate.sequence_number
        )
$BODY$ LANGUAGE SQL STABLE;

当然，我自动生成这些函数——除了表名之外，它们是相同的。典型的查询变成:

SELECT *
FROM specific_feature_asof('2011-09-30')
WHERE name = 'SOMETHING'

，查询计划如下所示:

Nested Loop Anti Join  (cost=0.00..412.84 rows=3 width=177) (actual time=0.044..7.038 rows=10 loops=1)
  Join Filter: (((better.timeslice_id)::integer <> (candidate.timeslice_id)::integer) AND ((better.sequence_number)::smallint > (candidate.sequence_number)::smallint))
  ->  Seq Scan on specific_feature_timeslice candidate  (cost=0.00..379.66 rows=3 width=177) (actual time=0.018..6.688 rows=10 loops=1)
        Filter: (((name)::text = 'SOMETHING'::text) AND overlaps(('2011-09-30 00:00:00'::timestamp without time zone)::timestamp without time zone, (('2011-09-30 00:00:00'::timestamp without time zone)::timestamp without time zone + '00:00:00'::interval), (valid_time_begin)::timestamp without time zone, COALESCE((valid_time_end)::timestamp without time zone, 'infinity'::timestamp without time zone)))
  ->  Index Scan using ix_specific_feature_timeslice_feature_id on specific_feature_timeslice better  (cost=0.00..8.28 rows=1 width=14) (actual time=0.008..0.011 rows=1 loops=10)
        Index Cond: ((feature_id)::integer = (candidate.feature_id)::integer)
        Filter: overlaps(('2011-09-30 00:00:00'::timestamp without time zone)::timestamp without time zone, (('2011-09-30 00:00:00'::timestamp without time zone)::timestamp without time zone + '00:00:00'::interval), (valid_time_begin)::timestamp without time zone, COALESCE((valid_time_end)::timestamp without time zone, 'infinity'::timestamp without time zone))
Total runtime: 7.150 ms

性能差异非常显著:像上面的查询这样的简单选择需要30-60毫秒。连接两个这样的函数需要300-400毫秒，这比我预期的要多一点，但仍然是可以接受的。

有了这些变化，我认为不再需要规范化feature_timeslice，即。将有效的开始/结束时间提取到一个单独的表中，所以我没有这样做。

Answer 2

首先规范您的实体。您的设置可能如下所示:

CREATE TABLE feature
( feature_id int primary key,
  name text
  -- Some other columns
);
CREATE TABLE timeslice
( timeslice_id int primary key,
  valid_begin timestamp NOT NULL,
  valid_end timestamp
  -- Some other columns?
);
CREATE TABLE feature_timeslice
( feature_id int references feature (feature_id),
  timeslice_id int references timeslice (timeslice_id),
  sequence_number smallint,             -- guess it should live here?
  -- Some other columns?
  CONSTRAINT pk_feature_timeslice PRIMARY KEY (feature_id, timeslice_id)
);

然后，尝试将两个select合并为一个。因此，特征的选择性可以首先起作用。嘿，别看风景了!

SELECT DISTINCT ON (1) ft.feature_id, first_value(ft.timeslice_id) OVER (PARTITION BY ft.feature_id ORDER BY ft.sequence_number DESC, ft.timeslice_id DESC) AS timeslice_id 
  FROM feature f
  JOIN feature_timeslice ft USING (feature_id)
  JOIN timeslice t USING (timeslice_id)
 WHERE f.name = 'SOMETHING'
AND t.valid_begin <= now()::timestamp
AND (t.valid_end >= now()::timestamp OR t.valid_end IS NULL);

如果该特性如您所暗示的那样具有选择性(max。每个特性10个时间片)，那么valid_begin或sequence_number上的索引就没什么用了。
不过，feature.name上的索引可能会有所帮助!
这里最突出的特点是将DISTINCT与WINDOW函数结合在一起。

Answer 3

你有一个规范化问题。

• timeslice_id是代理键。
• (feature_id, sequence_number}是一个候选键
• (feature_id, valid_time_begin (valid_time_end))也是一个候选键。

你误用了窗口函数，只是为了选择rank=1的候选人。自连接可能更便宜。

编辑:

CREATE index feature_timeslice_alt2 ON feature_timeslice
  ( feature_id,valid_time_begin);
CREATE UNIQUE index feature_timeslice_alt ON feature_timeslice
  ( feature_id,sequence_number);

CREATE VIEW feature_timeslice_id_encore AS
   SELECT timeslice_id FROM feature_timeslice t0
   WHERE (current_timestamp AT TIME ZONE 'UTC', '0'::interval)
          OVERLAPS (t0.valid_time_begin, COALESCE(t0.valid_time_end, 'infinity'::timestamp))
   AND NOT EXISTS ( 
      SELECT timeslice_id FROM feature_timeslice t1
      WHERE (current_timestamp AT TIME ZONE 'UTC', '0'::interval)
             OVERLAPS (t1.valid_time_begin, COALESCE(t1.valid_time_end, 'infinity'::timestamp))
      -- EDIT: forgot this
      AND t1.feature_id = t0.feature_id
      AND t1.sequence_number < t0.sequence_number
  );      

编辑:结果查询计划:

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Hash Anti Join  (cost=9090.62..18428.34 rows=45971 width=4) (actual time=110.053..222.897 rows=9030 loops=1)
   Hash Cond: (t0.feature_id = t1.feature_id)
   Join Filter: (t1.sequence_number < t0.sequence_number)
   ->  Seq Scan on feature_timeslice t0  (cost=0.00..8228.67 rows=68956 width=12) (actual time=0.031..106.646 rows=9030 loops=1)
         Filter: "overlaps"(timezone('UTC'::text, now()), (timezone('UTC'::text, now()) + '00:00:00'::interval), valid_time_begin, COALESCE(valid_time_end, 'infinity'::timestamp without time zone))
   ->  Hash  (cost=8228.67..8228.67 rows=68956 width=8) (actual time=109.979..109.979 rows=9030 loops=1)
         Buckets: 8192  Batches: 1  Memory Usage: 353kB
         ->  Seq Scan on feature_timeslice t1  (cost=0.00..8228.67 rows=68956 width=8) (actual time=0.016..106.995 rows=9030 loops=1)
               Filter: "overlaps"(timezone('UTC'::text, now()), (timezone('UTC'::text, now()) + '00:00:00'::interval), valid_time_begin, COALESCE(valid_time_end, 'infinity'::timestamp without time zone))
 Total runtime: 223.488 ms

OP查询的查询计划与他的相似，并且具有"总运行时间:1404.092 ms"。(但由于排序步骤的原因，它可能会更糟)