如何获取简单的哈希联接查询以及复杂的排序合并查询

Question

我有一个记录有关正在运行的进程的信息的系统。每个正在运行的进程都包含一系列步骤，这些步骤可能会也可能不会并行运行。系统将有关进程及其步骤的信息记录到两个单独的表中：

CREATE TABLE pid (
  pid         integer,
  start_time  timestamp,
  end_time    timestamp,
  elapsed     bigint,
  aborted     integer,
  label       char(30)
);
CREATE TABLE pid_step (
  pid         integer,
  step        integer,
  start_time  timestamp,
  end_time    timestamp,
  elapsed     bigint,
  mem         bigint,
  ...
);

pid_step表包含有关每个步骤的一堆资源使用情况统计信息，我在此处将其简化为记录为该步骤分配的内存 # 字节的 mem 列。我想按进程标签对内存分配进行采样，也许每隔 5 秒一次，这样我就可以绘制它。我需要类似于以下内容的结果：

tick                    label  mem
----------------------- ------ -----------
2014-11-04 05:37:40.0   foo      328728576
2014-11-04 05:37:40.0   bar         248436
2014-11-04 05:37:40.0   baz        1056144
2014-11-04 05:37:45.0   foo     1158807552
2014-11-04 05:37:45.0   bar         632822
2014-11-04 05:37:45.0   baz         854398

由于日志仅提供每个进程和步骤的开始和结束时间戳，而不是以 5 秒间隔提供资源使用情况示例，因此我需要找到最有效的方法来确定每个 5 秒间隔 （tick） 运行哪些进程步骤，然后聚合其分配的内存。我进行了 3 次单独的尝试，这些尝试都以不同的性能水平产生相同的结果。为了简洁起见，我将把每个查询及其解释计划放在一个要点（https://gist.github.com/anonymous/3b57f70015b0d234a2de）中，但我会解释我的方法：

1. 这是我的第一次尝试，它绝对是最直观和最容易维护的。它将不同的流程标签与generate_series交叉连接，为每个标签生成 5 秒的刻度，然后在pid表和pid_step表上左连接。左连接创建"零填充"效果，并确保我们不会丢弃任何没有关联数据的即时报价。不幸的是，这种方法表现最差（请参阅下面的基准链接），我相信这是由于使用了哈希连接，其中between t2.start_time and t2.end_time谓词作为连接过滤器而不是连接条件进行处理。

2. 这是我的第二次尝试，它的性能更好，但不太直观和可维护。"零填充"方法与查询 1 中的方法相同。但是，在执行 pid 和 pid_step 的左连接之前，我根据最大流程运行时间和流程步骤开始和结束时间预先计算了具有关联数据的刻度。这允许排序合并联接，其中刻度和标签谓词都可以表示为联接条件，并且不使用联接筛选器。

3. 这是我的最后一次尝试，它的性能最好，具有与查询 2 大致相同的直观性和可维护性。这里的优化是，我使用最大流程步骤经过时间，该时间保证小于最大流程经过时间，因此在 CTE t3 开始时创建一个较小的嵌套循环。

理想情况下，我希望 SQL 像查询 1 一样简单且可维护，但执行与查询 3 一样好。我是否可以以索引或稍微重写查询 1 的方式做些什么来提高性能？

基准测试结果：https://i.stack.imgur.com/9SZWS.png

Answer 1

这是一个使用PostgreSQL范围（SQLFiddle）功能的解决方案。

CREATE TABLE pid (
  pid         integer PRIMARY KEY,
  label       char(30)
);
CREATE TABLE pid_step (
  pid         integer,
  step        serial,
  start_time  timestamp,
  end_time    timestamp,
  mem         bigint,
  PRIMARY KEY (pid, step)
);

采样方法是个好主意，但在我看来，这是一种优化。这是我的解决方案：

假设我们要绘制一天的数据，我们将这一天分成多个时间片，每个时间片持续 5 秒。对于一个进程和一个时间片，我们希望检索在这 5 秒内运行的所有步骤的平均内存。因此，我们不是每 5 秒采样一次（这可能会隐藏数据峰值），而是显示这 5 秒的相关数据的聚合。聚合可以是可用的任何 PostgreSQL 聚合函数。

第一步是生成这些时间片（就像您在不使用范围数据类型时所做的那样）：

-- list of time ranges of 5 seconds interval
-- inclusive lower bound, exclusive upper bound
SELECT 
  tsrange(tick, tick + '5 seconds'::interval, '[)') as time_range
FROM generate_series(
  '2001-02-16 21:28:30'::timestamp, 
  '2001-02-16 22:28:30'::timestamp, 
  '5 seconds'::interval
) AS tick

请注意，这些切片不会相互重叠，因为下限是包含的，上限是独占的。

这是棘手的部分，我们不想通过删除start_time和end_time并为此数据创建范围列来更改表架构。幸运的是，PostgreSQL 允许在表达式上使用索引：

-- create index on range (inclusive on upper and lower) 
CREATE INDEX pid_step_tstzrange_index ON pid_step 
USING gist (tsrange(start_time, end_time, '()'));

有了这个索引，我们现在能够以一小部分的处理成本使用各种各样的 PostgreSQL 范围运算符，唯一需要注意的是，为了使用此索引，我们必须在查询中使用完全相同的函数。

正如您可能已经猜到的那样，索引将用于连接时间片和步骤，因为如果步骤"虚拟"范围与时间片重叠，我们需要连接。

这是最后一个查询：

WITH
time_range AS (
  -- list of time ranges of 5 seconds interval
  -- inclusive lower bound, exclusive upper bound
  SELECT 
    tsrange(tick, tick + '5 seconds'::interval, '[)') as time_range
  FROM generate_series(
    '2001-02-16 21:28:30'::timestamp, 
    '2001-02-16 22:28:30'::timestamp, 
    '5 seconds'::interval
  ) AS tick
),
-- associate each pid_step with the matching time_range
-- aggregate the average memory usage for each pid for each time slice
avg_memory_by_pid_by_time_range AS (
  SELECT 
    time_range,
    pid,
    avg(mem) avg_memory
  FROM 
    time_range
    JOIN pid_step 
      ON tsrange(pid_step.start_time, pid_step.end_time, '()') && time_range.time_range
  GROUP BY
    time_range,
    pid
)
-- embellish the result with some additional data from pid
SELECT 
  lower(time_range) AS tick,
  pid.label AS label,
  trunc(avg_memory) AS mem
FROM
  avg_memory_by_pid_by_time_range
  JOIN pid ON avg_memory_by_pid_by_time_range.pid = pid.pid
ORDER BY
  lower(time_range),
  pid.label
;

我希望您的生产数据的性能仍然很好（查询规划方程中有很多细节）。