主页 / dba / 问题 / 35380
Accepted
DaveB
Asked: 2013-02-26 08:06:53 +0800 CST

选择最长的连续序列

  • 772

我正在尝试在 PostgreSQL 9.0 中构建一个查询，以获取特定列的最长连续行序列。

考虑下表：

lap_id (serial), lap_no (int), car_type (enum), race_id (int FK)

每个地方lap_no都是独一无二的(race_id, car_type)。

我希望查询为给定的race_idand生成最长的序列car_type，因此它将返回一个int最高的（或长的）。

使用以下数据：

1, 1, red, 1
2, 2, red, 1
3, 3, red, 1
4, 4, red, 1
5, 1, blue, 1
6, 5, red, 1
7, 2, blue, 1
8, 1, green, 1

因为car_type = red and race_id = 1查询将5作为lap_no字段的最长序列返回。

我在这里发现了一个类似的问题，但是我的情况更简单一些。

（我也想知道car_type所有种族的最长序列，但我打算自己解决这个问题。）

postgresql gaps-and-islands

2 个回答

  1. Best Answer

    您的描述会产生如下表定义：

    CREATE TABLE tbl (
   lap_id   serial PRIMARY KEY
 , lap_no   int NOT NULL
 , car_type enum NOT NULL
 , race_id  int NOT NULL  -- REFERENCES ...
 , UNIQUE(race_id, car_type, lap_no)
);

    此类问题的通用解决方案

    要获得最长的序列（1 个结果，最长的，如果有关系则任意选择）：

    SELECT race_id, car_type, count(*) AS seq_len
FROM  (
   SELECT *, count(*) FILTER (WHERE step)
                      OVER (ORDER BY race_id, car_type, lap_no) AS grp
   FROM  (
      SELECT *, (lag(lap_no) OVER (PARTITION BY race_id, car_type ORDER BY lap_no) + 1)
                 IS DISTINCT FROM lap_no AS step
      FROM   tbl
      ) x
   ) y
GROUP  BY race_id, car_type, grp
ORDER  BY seq_len DESC
LIMIT  1;

    count(*) FILTER (WHERE step)只计算TRUE（= 到下一组），这会为每个新组生成一个新数字。

    与 plpgsql相关的程序解决方案：

    如果最高要求是性能，则plpgsql 函数在这种特殊情况下通常更快，因为它可以在一次扫描中计算结果。

    连续数字更快

    我们可以利用连续 lap_no定义序列的事实，以获得更简单和更快的版本：

    SELECT race_id, car_type, count(*) AS seq_len
FROM  (
   SELECT race_id, car_type
        , row_number() OVER (PARTITION BY race_id, car_type ORDER BY lap_no) - lap_no AS grp
   FROM   tbl
   ) x
GROUP  BY race_id, car_type, grp
ORDER  BY seq_len DESC
LIMIT  1;

    连续的圈数以相同的方式结束grp。每错过一圈都会导致grp每个分区的数量减少。

    这依赖于(race_id, car_type, lap_no)存在UNIQUE NOT NULL。NULL 值或重复值可能会破坏逻辑。

    讨论杰克更简单的替代方案

    @Jack 的版本有效地计算了前一个lap_no具有race_id相同car_type. car_type这更简单、更快、更正确——只要每个race_id.

    但是对于如此简单的任务，查询可能会更简单。从逻辑上讲，所有lap_noper(car_type, race_id)必须是in sequence，我们可以只计算圈数：

    SELECT race_id, car_type, count(*) AS seq_len
FROM   tbl
GROUP  BY race_id, car_type
ORDER  BY seq_len DESC
LIMIT  1;

    另一方面，如果每个race_idcar_type可以有多个单独的序列（并且问题没有另外指定），那么 Jack 的版本将失败。

    对于给定的比赛/汽车类型更快

    回复问题中的评论/澄清：将查询限制为给定 (race_id, car_type)的查询将使其更快，当然：

    SELECT count(*) AS seq_len
FROM  (
   SELECT row_number() OVER (ORDER BY lap_no) - lap_no AS grp
   FROM   tbl
   WHERE  race_id = 1
   AND    car_type = 'red'
   ) x
GROUP  BY grp
ORDER  BY seq_len DESC
LIMIT  1;

    db<>fiddle here
    旧SQL Fiddle

    指数

    最佳性能的关键是合适的索引（除了提到的使用单个顺序扫描的程序解决方案）。像这样的多列索引效果最好：

    CREATE INDEX tbl_mult_idx ON tbl (race_id, car_type, lap_no);

    如果您的表具有UNIQUE我在顶部假设的约束，则在内部仅使用此（唯一）索引实现，并且您不需要创建另一个索引。

    • 21 

  2. create table tbl (lap_no int, car_type text, race_id int);

    insert into tbl values (1,'red',1),(2,'red',1),(3,'red',1),(4,'red',1),
                       (1,'blue',1),(5,'red',1),(2,'blue',1),(1,'green',1);

    select car_type, race_id, sum(case when lap_no=(prev+1) then 1 else 0 end)+1 seq_len
from ( select *, lag(lap_no) over (partition by car_type, race_id order by lap_no) prev 
       from tbl ) z
group by car_type, race_id
order by seq_len desc limit 1;

    /*
|car_type|race_id|seq_len|
|:-------|------:|------:|
|red     |      1|      5|
*/
    • 7

相关问题