从表格中找出连续的“n”个空闲数字。

Question

我有一些带有数字的表格，格式如下（状态为FREE或ASSIGNED）：

id_set  number  status         
-----------------------
1       000001  ASSIGNED
1       000002  FREE
1       000003  ASSIGNED
1       000004  FREE
1       000005  FREE
1       000006  ASSIGNED
1       000007  ASSIGNED
1       000008  FREE
1       000009  FREE
1       000010  FREE
1       000011  ASSIGNED
1       000012  ASSIGNED
1       000013  ASSIGNED
1       000014  FREE
1       000015  ASSIGNED

我需要找到连续的“n”个数字，例如当n = 3时，查询应返回：

1       000008  FREE
1       000009  FREE
1       000010  FREE

查询应仅返回每个id_set的第一个可能组（实际上，每次查询只会针对一个id_set执行）。

我在检查WINDOW函数，尝试了一些查询，例如 COUNT(id_number) OVER (PARTITION BY id_set ROWS UNBOUNDED PRECEDING)，但这就是我得到的 :) 我想不出逻辑，如何在Postgres中实现。

我考虑使用WINDOW函数创建虚拟列，对每个状态为'FREE'的数字计算前面的行数，然后选择第一个计数等于我的“n”数字的数字。

或者也许按状态分组数字，但只从一个ASSIGNED到另一个ASSIGNED，并且只选择包含至少“n”个数字的组。

编辑

我找到了这个查询（稍微修改了一下）

WITH q AS
(
  SELECT *,
         ROW_NUMBER() OVER (PARTITION BY id_set, status ORDER BY number) AS rnd,
         ROW_NUMBER() OVER (PARTITION BY id_set ORDER BY number) AS rn
  FROM numbers
)
SELECT id_set,
       MIN(number) AS first_number,
       MAX(number) AS last_number,
       status,
       COUNT(number) AS numbers_count
FROM q
GROUP BY id_set,
         rnd - rn,
         status
ORDER BY
     first_number

它生成了一组免费/分配的数字，但我只想要满足条件的第一组中的所有数字。

SQL Fiddle

- boobiq

Answer 1

这是一个间隙和岛屿问题。假设在同一个id_set集合中没有间隙或重复项：

WITH partitioned AS (
  SELECT
    *,
    number - ROW_NUMBER() OVER (PARTITION BY id_set) AS grp
  FROM atable
  WHERE status = 'FREE'
),
counted AS (
  SELECT
    *,
    COUNT(*) OVER (PARTITION BY id_set, grp) AS cnt
  FROM partitioned
)
SELECT
  id_set,
  number
FROM counted
WHERE cnt >= 3
;

这里有一个SQL Fiddle演示链接^*，用于此查询：http://sqlfiddle.com/#!1/a2633/1。 更新 为了只返回一个集合，你可以再添加一轮排名。

WITH partitioned AS (
  SELECT
    *,
    number - ROW_NUMBER() OVER (PARTITION BY id_set) AS grp
  FROM atable
  WHERE status = 'FREE'
),
counted AS (
  SELECT
    *,
    COUNT(*) OVER (PARTITION BY id_set, grp) AS cnt
  FROM partitioned
),
ranked AS (
  SELECT
    *,
    RANK() OVER (ORDER BY id_set, grp) AS rnk
  FROM counted
  WHERE cnt >= 3
)
SELECT
  id_set,
  number
FROM ranked
WHERE rnk = 1
;

这里也有一个演示：http://sqlfiddle.com/#!1/a2633/2。 如果你需要将其按照每个id_set进行分组，可以像这样修改RANK()函数的调用方式：

RANK() OVER (PARTITION BY id_set ORDER BY grp) AS rnk

此外，您可以使查询返回最小匹配集（即首先尝试返回确切的三个连续数字集合，如果存在，则返回四个、五个等），如下所示：

RANK() OVER (ORDER BY cnt, id_set, grp) AS rnk

或者像这样（每个id_set一个）：

RANK() OVER (PARTITION BY id_set ORDER BY cnt, grp) AS rnk

---

_{* 这个答案中链接的 SQL Fiddle 演示使用9.1.8实例，因为目前似乎9.2.1不可用。}

- Andriy M

---

非常感谢，这看起来很不错，但是有可能将其更改为只返回第一组数字吗？如果我将其更改为cnt >= 2，那么我会得到5个数字（2组=2 + 3个数字）。 - boobiq

@boobiq：你是想要每个id_set一个，还是只需要一个？如果这一开始就是问题的一部分，请更新你的问题。（这样其他人就可以看到完整的需求并提出建议或更新他们的答案。） - Andriy M

我编辑了我的问题（在想要返回之后），它只会针对一个id_set执行，所以只会找到第一个可能的组。 - boobiq

Answer 2

一个简单而快速的变体：

SELECT min(number) AS first_number, count(*) AS ct_free
FROM (
    SELECT *, number - row_number() OVER (PARTITION BY id_set ORDER BY number) AS grp
    FROM   tbl
    WHERE  status = 'FREE'
    ) x
GROUP  BY grp
HAVING count(*) >= 3  -- minimum length of sequence only goes here
ORDER  BY grp
LIMIT  1;

• 需要在number中提供连续的数字序列（如问题中所提供）。
• 适用于除'FREE'以外的任何可能的status值，甚至包括NULL。
• 主要特点是在消除不符合条件的行后，从number中减去row_number()。连续的数字会在同一个grp中结束，并且确保grp也是按照升序排列的。
• 然后您可以按grp进行GROUP BY并计算成员数。由于您似乎想要第一个出现的情况，使用ORDER BY grp LIMIT 1，您将获得序列的起始位置和长度（可以大于等于n）。

一组行

要获取实际的数集，请不要再次查找表格。使用generate_series()更为经济实惠：

SELECT generate_series(first_number, first_number + ct_free - 1)
    -- generate_series(first_number, first_number + 3 - 1) -- only 3
FROM  (
   SELECT min(number) AS first_number, count(*) AS ct_free
   FROM  (
      SELECT *, number - row_number() OVER (PARTITION BY id_set ORDER BY number) AS grp
      FROM   tbl
      WHERE  status = 'FREE'
      ) x
   GROUP  BY grp
   HAVING count(*) >= 3
   ORDER  BY grp
   LIMIT  1
   ) y;

如果你真的想要一个带有前导零的字符串，就像你在示例值中显示的那样，请使用to_char()函数，并加上FM（填充模式）修饰符。

SELECT to_char(generate_series(8, 11), 'FM000000')

SQL Fiddle带有扩展的测试用例和两个查询。

相关的答案如下：

• 选择最长连续序列

- Erwin Brandstetter

Answer 3

这是一种相对通用的做法。

请记住，这取决于您的number列是否连续。如果不是连续的，可能需要使用窗口函数和/或CTE类型的解决方案：

SELECT 
    number
FROM
    mytable m
CROSS JOIN
   (SELECT 3 AS consec) x
WHERE 
    EXISTS
       (SELECT 1 
        FROM mytable
        WHERE number = m.number - x.consec + 1
        AND status = 'FREE')
    AND NOT EXISTS
       (SELECT 1 
        FROM mytable
        WHERE number BETWEEN m.number - x.consec + 1 AND m.number
        AND status = 'ASSIGNED')

- JNK

---

在Postgres中，这样的声明是行不通的。 - user1822

@a_horse_with_no_name 请随意修复它 :) - JNK

没有窗口函数，太好了！虽然我认为应该是M.number-consec+1（例如对于10，它应该是10-3+1=8）。 - Andriy M

@AndriyM 嗯，它不是“好”，而是脆弱的，因为它依赖于number字段的连续值。对数学的正确判断，我会进行修正。 - JNK

我对此没有任何问题。数据样本的外观非常清楚地表明这些数字是唯一且连续的。如果它们不是看起来的那样，那么这是提问者的责任确保我们不被事物的外表所欺骗，尽管明确说明你的假设从来都不是一个坏主意（你已经做到了）。因此，我仍然认为这是一个针对特定设计的不错解决方案。 - Andriy M

是的，一个集合中的数字是唯一的，并且从000到999连续排列，没有任何间隔。我现在没有时间尝试，明天我会试一试。非常感谢你们所有人的帮助，谢谢！ - boobiq

我冒昧地修复了Postgres的语法。第一个EXISTS可以简化。因为我们只需要确保存在任何 n 个之前的行，所以我们可以去掉AND status = 'FREE'。并且我会将第二个EXISTS中的条件改为status <> 'FREE'，以增强其对未来添加选项的适应性。 - Erwin Brandstetter

这个看起来没有使用窗口函数，但它返回了所有可能性的“最后数字”（http://sqlfiddle.com/#!12/13127/10），所以对于n=3，它只返回了000010（我想要返回该组的所有可用数字，所以应该是000008、000009、000010...而且我只想要第一个可能的组）。 - boobiq

Answer 4

这将仅返回3个数字中的第一个。它不要求number的值是连续的。在SQL-Fiddle上进行了测试。

WITH cte3 AS
( SELECT
    *,
    COUNT(CASE WHEN status = 'FREE' THEN 1 END) 
        OVER (PARTITION BY id_set ORDER BY number
              ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING)
      AS cnt
  FROM atable
)
SELECT
  id_set, number
FROM cte3
WHERE cnt = 3 ;

这将显示所有数字（其中有3个或更多连续的'FREE'位置）：

WITH cte3 AS
( SELECT
    *,
    COUNT(CASE WHEN status = 'FREE' THEN 1 END) 
        OVER (PARTITION BY id_set ORDER BY number
              ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING)
      AS cnt
  FROM atable
)
, cte4 AS
( SELECT
    *, 
    MAX(cnt) 
        OVER (PARTITION BY id_set ORDER BY number
              ROWS BETWEEN 2 PRECEDING AND CURRENT ROW)
      AS maxcnt
  FROM cte3
)
SELECT
  id_set, number
FROM cte4
WHERE maxcnt >= 3 ;

- ypercubeᵀᴹ

Answer 5

select r1.number from some_table r1, 
some_table r2,
some_table r3,
some_table r4 
where r3.number <= r2.number 
and r3.number >= r1.number 
and r3.status = 'FREE' 
and r2.number = r1.number + 4 
and r4.number <= r2.number 
and r4.number >= r1.number 
and r4.status = 'ASSIGNED'
group by r1.number, r2.number having count(r3.number) = 5 and count(r4.number) = 0 order by r1.number asc limit 1 ;

在这种情况下，5个连续的数字 - 因此差值必须为4，或者换句话说，count(r3.number) = n和r2.number = r1.number + n - 1。 使用连接操作：

select r1.number 
from some_table r1 join 
 some_table r2 on (r2.number = r1.number + :n -1) join
 some_table r3 on (r3.number <= r2.number and r3.number >= r1.number) join
 some_table r4 on (r4.number <= r2.number and r4.number >= r1.number)
where  
 r3.status = 'FREE' and
 r4.status = 'ASSIGNED'
group by r1.number, r2.number having count(r3.number) = :n and count(r4.number) = 0 order by r1.number asc limit 1 ;

- Ununoctium

---

你认为四路笛卡尔积是一个高效的方法来完成这个任务吗？ - JNK

或者你能用现代的JOIN语法来写吗？ - JNK

我不想依赖窗口函数，所以提供了一个适用于任何SQL数据库的解决方案。 - Ununoctium

Answer 6

CREATE TABLE #ConsecFreeNums
(
     id_set BIGINT
    ,number VARCHAR(10)
    ,status VARCHAR(10)
)

CREATE TABLE #ConsecFreeNumsResult
(
     Seq    INT
    ,id_set BIGINT
    ,number VARCHAR(10)
    ,status VARCHAR(10)
)

INSERT #ConsecFreeNums
SELECT 1, '000002', 'FREE' UNION
SELECT 1, '000003', 'ASSIGNED' UNION
SELECT 1, '000004', 'FREE' UNION
SELECT 1, '000005', 'FREE' UNION
SELECT 1, '000006', 'ASSIGNED' UNION
SELECT 1, '000007', 'ASSIGNED' UNION
SELECT 1, '000008', 'FREE' UNION
SELECT 1, '000009', 'FREE' UNION
SELECT 1, '000010', 'FREE' UNION
SELECT 1, '000011', 'ASSIGNED' UNION
SELECT 1, '000012', 'ASSIGNED' UNION
SELECT 1, '000013', 'ASSIGNED' UNION
SELECT 1, '000014', 'FREE' UNION
SELECT 1, '000015', 'ASSIGNED'

DECLARE @id_set AS BIGINT, @number VARCHAR(10), @status VARCHAR(10), @number_count INT, @number_count_check INT

DECLARE ConsecFreeNumsCursor CURSOR FAST_FORWARD FOR
SELECT
       id_set
      ,number
      ,status
 FROM
      #ConsecFreeNums
WHERE id_set = 1
ORDER BY number

OPEN ConsecFreeNumsCursor

FETCH NEXT FROM ConsecFreeNumsCursor INTO @id_set, @number, @status

SET @number_count_check = 3
SET @number_count = 0

WHILE @@FETCH_STATUS = 0
BEGIN
    IF @status = 'ASSIGNED'
    BEGIN
        IF @number_count = @number_count_check
        BEGIN
            SELECT 'Results'
            SELECT * FROM #ConsecFreeNumsResult ORDER BY number
            BREAK
        END
        SET @number_count = 0
        TRUNCATE TABLE #ConsecFreeNumsResult
    END
    ELSE
    BEGIN
        SET @number_count = @number_count + 1
        INSERT #ConsecFreeNumsResult SELECT @number_count, @id_set, @number, @status
    END
    FETCH NEXT FROM ConsecFreeNumsCursor INTO @id_set, @number, @status
END

CLOSE ConsecFreeNumsCursor
DEALLOCATE ConsecFreeNumsCursor

DROP TABLE #ConsecFreeNums
DROP TABLE #ConsecFreeNumsResult

- Ravi Ramaswamy

---

我正在使用游标以提高性能 - 如果SELECT返回大量行，是否应该使用游标 - Ravi Ramaswamy

我重新格式化了你的答案，通过在编辑器上突出显示代码并按下“{ }”按钮。享受吧！ - jcolebrand

你可能还想编辑你的回答，并解释为什么你认为光标提供更好的性能。 - jcolebrand

游标是一个顺序的过程，几乎就像一次读取平面文件的一条记录。在其中一种情况下，我用一个单独的游标替换了MEM TEMP表。这将处理时间从26小时缩短到6小时。我不得不使用嵌套的WHILE循环遍历结果集。 - Ravi Ramaswamy

你有没有试过对你的假设进行测试用例？也许你会感到惊讶。除了边缘情况，普通的SQL是最快的。 - Erwin Brandstetter

根据情况而定，纯SQL会更快。例如，BULK INSERT将完胜CURSOR。在下面的情况中，我将时间从大约25小时缩短到了6小时：

1. 我们有数千个项目的记录。每个项目都有数百条记录。
2. 为不同的项目编号创建一个内存临时表（MEM TEMP table）。
3. 遍历上述内存临时表。
4. 对于每个项目，创建第二个内存临时表，包含该特定项目的行。
5. 遍历第二个内存临时表，并处理每个项目记录。

- Ravi Ramaswamy