6

我有一个这种形式的 PostgreSQL 表:

base_id int | mods smallint[]
     3      |   {7,15,48}

我需要填充这种形式的表格:

combo_id int | base_id int | mods smallint[]
     1       |     3       |      
     2       |     3       |      {7}
     3       |     3       |      {7,15}   
     4       |     3       |      {7,48}   
     5       |     3       |      {7,15,48}
     6       |     3       |      {15}
     7       |     3       |      {15,48}
     8       |     3       |      {48}

我想我可以使用一个几乎完全完成此操作的函数来完成此操作,迭代第一个表并将组合写入第二个表: 在 SQL 中生成所有组合

但是,我是 Postgres 新手,我一辈子都无法弄清楚如何使用 plpgsql 来做到这一点。它不需要特别快;它只会在后端定期运行。第一个表大约有 80 条记录,粗略计算表明我们可以预期第二个表大约有 2600 条记录。

谁能至少指出我正确的方向?

编辑:克雷格:我有 PostgreSQL 9.0。我成功地使用了 UNNEST():

FOR messvar IN SELECT * FROM UNNEST(mods) AS mod WHERE mod BETWEEN 0 AND POWER(2, @n) - 1
LOOP
    RAISE NOTICE '%', messvar;
END LOOP;

但后来不知道下一步该去哪里。

编辑:作为参考,我最终使用了 Erwin 的解决方案,添加了一行以向每个集合添加空结果 ('{}'),并且 Erwin 所指的特殊情况已删除:

CREATE OR REPLACE FUNCTION f_combos(_arr integer[], _a integer[] DEFAULT '{}'::integer[], _z integer[] DEFAULT '{}'::integer[])
RETURNS SETOF integer[] LANGUAGE plpgsql AS
$BODY$
DECLARE
 i int;
 j int;
 _up int;
BEGIN
 IF array_length(_arr,1) > 0 THEN 
    _up := array_upper(_arr, 1);

    IF _a = '{}' AND _z = '{}' THEN RETURN QUERY SELECT '{}'::int[]; END IF;
    FOR i IN array_lower(_arr, 1) .. _up LOOP
       FOR j IN i .. _up  LOOP
          CASE j-i
          WHEN 0,1 THEN
             RETURN NEXT _a || _arr[i:j] || _z;
          ELSE
             RETURN NEXT _a || _arr[i:i] || _arr[j:j] || _z;
             RETURN QUERY SELECT *
             FROM f_combos(_arr[i+1:j-1], _a || _arr[i], _arr[j] || _z);
          END CASE;
       END LOOP;
    END LOOP;
 ELSE
    RETURN NEXT _arr;
 END IF;
END;
$BODY$

然后,我使用该函数来填充我的表:

INSERT INTO e_ecosystem_modified (ide_ecosystem, modifiers) 
(SELECT ide_ecosystem, f_combos(modifiers) AS modifiers FROM e_ecosystem WHERE ecosystemgroup <> 'modifier' ORDER BY ide_ecosystem, modifiers);

从我的源表中的 79 行和修饰符数组中最多 7 个项目开始,查询花费了 250 毫秒来填充我的输出表中的 2630 行。极好的。

4

2 回答 2

5

在我睡过之后,我有了一个全新的、更简单、更快的想法:

CREATE OR REPLACE FUNCTION f_combos(_arr anyarray)
  RETURNS TABLE (combo anyarray) LANGUAGE plpgsql AS
$BODY$
BEGIN
    IF array_upper(_arr, 1) IS NULL THEN
        combo := _arr; RETURN NEXT; RETURN;
    END IF;

    CASE array_upper(_arr, 1)
--  WHEN 0 THEN -- does not exist
    WHEN 1 THEN
        RETURN QUERY VALUES ('{}'), (_arr);
    WHEN 2 THEN
        RETURN QUERY VALUES ('{}'), (_arr[1:1]), (_arr), (_arr[2:2]);
    ELSE
        RETURN QUERY
        WITH x AS (
            SELECT f.combo FROM f_combos(_arr[1:array_upper(_arr, 1)-1]) f
            )
        SELECT x.combo FROM x
        UNION ALL
        SELECT x.combo || _arr[array_upper(_arr, 1)] FROM x;
    END CASE;
END
$BODY$;

称呼:

SELECT * FROM f_combos('{1,2,3,4,5,6,7,8,9}'::int[]) ORDER BY 1;

512 行,总运行时间:2.899 毫秒

解释

  • NULL用空数组处理特殊情况。
  • 为两个原始数组构建组合。
  • 任何更长的数组都分解为:
    • 长度为 n-1 的相同数组的组合
    • 加上所有与元素 n .. 结合的递归

真的很简单,一旦掌握。

  • 适用于以下标 1开头的一维整数数组(见下文)。
  • 比旧解决方案快 2-3 倍,扩展性更好。
  • 再次适用于任何元素类型(使用多态类型)。
  • 在问题中显示的结果中包含空数组(正如@Craig 在评论中向我指出的那样)。
  • 更短,更优雅。

这假定数组下标1(默认)开始。如果您不确定自己的值,请调用如下函数进行标准化:

SELECT * FROM  f_combos(_arr[array_lower(_arr, 1):array_upper(_arr, 1)]);

不确定是否有更优雅的方法来规范化数组下标。我发布了一个问题:
Normalize array subscripts for 1-dimensional array so they start with 1

旧解决方案(较慢)

CREATE OR REPLACE FUNCTION f_combos2(_arr int[], _a int[] = '{}', _z int[] = '{}')
 RETURNS SETOF int[] LANGUAGE plpgsql AS
$BODY$
DECLARE
   i int;
   j int;
   _up int;
BEGIN
   IF array_length(_arr,1) > 0 THEN 
      _up := array_upper(_arr, 1);

      FOR i IN array_lower(_arr, 1) .. _up LOOP
         FOR j IN i .. _up  LOOP
            CASE j-i
            WHEN 0,1 THEN
               RETURN NEXT _a || _arr[i:j] || _z;
            WHEN 2 THEN
               RETURN NEXT _a || _arr[i:i] || _arr[j:j] || _z;
               RETURN NEXT _a || _arr[i:j] || _z;
            ELSE
               RETURN NEXT _a || _arr[i:i] || _arr[j:j] || _z;
               RETURN QUERY SELECT *
               FROM f_combos2(_arr[i+1:j-1], _a || _arr[i], _arr[j] || _z);
            END CASE;
         END LOOP;
      END LOOP;
   ELSE
      RETURN NEXT _arr;
   END IF;
END;
$BODY$;

称呼:

SELECT * FROM f_combos2('{7,15,48}'::int[]) ORDER BY 1;

适用于一维整数数组。这可以进一步优化,但这当然不是这个问题的范围所需要的。
ORDER BY强加问题中显示的顺序。

NULL如评论中所述,提供 NULL 或空数组。

使用 PostgreSQL 9.1 测试,但应该适用于任何半现代版本。 array_lower()并且array_upper()至少从 PostgreSQL 7.4 开始就已经存在了。只有参数默认值在 8.4 版中是新的。可以轻松更换。

性能不错。

SELECT DISTINCT * FROM f_combos('{1,2,3,4,5,6,7,8,9}'::int[]) ORDER BY 1;

511 行,总运行时间:7.729 毫秒

解释

它建立在这种简单的形式之上,它只创建相邻元素的所有组合:

CREATE FUNCTION f_combos(_arr int[])
  RETURNS SETOF int[] LANGUAGE plpgsql AS
$BODY$
DECLARE
   i  int;
   j  int;
  _up int;
BEGIN
   _up := array_upper(_arr, 1);

   FOR i in array_lower(_arr, 1) .. _up LOOP
      FOR j in i .. _up LOOP
         RETURN NEXT _arr[i:j];
      END LOOP;
   END LOOP;
END;
$BODY$;

但是对于具有两个以上元素的子数组,这将失败。所以:

  • 对于任何具有 3 个元素的子数组,添加一个仅具有外部两个元素的数组。这是这种特殊情况的捷径,可以提高性能,但并非绝对需要

  • 对于具有超过 3 个元素的任何子数组,我采用外部两个元素并用同一函数递归构建的内部元素的所有组合填充。

于 2012-08-17T01:16:59.190 回答
3

一种方法是使用递归 CTE。不过,Erwin 更新后的递归函数明显更快并且可扩展性更好,因此这作为一种有趣的不同方法非常有用。Erwin 的更新版本更加实用。

我尝试了一种计数方法(见最后),但没有一种快速的方法从数组中提取任意元素,结果证明它比递归方法慢。

递归 CTE 组合函数

CREATE OR REPLACE FUNCTION combinations(anyarray) RETURNS SETOF anyarray AS $$
WITH RECURSIVE
    items AS (
            SELECT row_number() OVER (ORDER BY item) AS rownum, item
            FROM (SELECT unnest($1) AS item) unnested
    ),
    q AS (
            SELECT 1 AS i, $1[1:0] arr
            UNION ALL
            SELECT (i+1), CASE x
                    WHEN 1 THEN array_append(q.arr,(SELECT item FROM items WHERE rownum = i))
                    ELSE q.arr END
            FROM generate_series(0,1) x CROSS JOIN q WHERE i <= array_upper($1,1)
    )
SELECT q.arr AS mods
FROM q WHERE i = array_upper($1,1)+1;
$$ LANGUAGE 'sql';

它是一个多态函数,因此它适用于任何类型的数组。

逻辑是使用工作表迭代未嵌套输入集中的每个项目。从工作表中的一个空数组开始,代号为 1。对于输入集中的每个条目,将两个新数组插入到工作表中,代号递增。两者中的一个是上一代输入数组的副本,另一个是输入数组中附加了输入集中第 (generation-number) 项的输入数组。当世代数超过输入集中的项目数时,返回上一代。

用法

您可以使用该combinations(smallint[])函数来产生您想要的结果,将其用作与row_number窗口函数结合的集合返回函数。

-- assuming table structure
regress=# \d comb
       Table "public.comb"
 Column  |    Type    | Modifiers 
---------+------------+-----------
 base_id | integer    | 
 mods    | smallint[] | 


SELECT base_id, row_number() OVER (ORDER BY mod) AS mod_id, mod 
FROM (SELECT base_id, combinations(mods) AS mod FROM comb WHERE base_id = 3) x
ORDER BY mod;

结果

regress=# SELECT base_id, row_number() OVER (ORDER BY mod) AS mod_id, mod 
regress-# FROM (SELECT base_id, combinations(mods) AS mod FROM comb WHERE base_id = 3) x
regress-# ORDER BY mod;
 base_id | mod_id |    mod    
---------+--------+-----------
       3 |      1 | {}
       3 |      2 | {7}
       3 |      3 | {7,15}
       3 |      4 | {7,15,48}
       3 |      5 | {7,48}
       3 |      6 | {15}
       3 |      7 | {15,48}
       3 |      8 | {48}
(8 rows)

Time: 2.121 ms

零元素数组产生空结果。如果你想combinations({})返回一行{},那么UNION ALLwith{}将完成这项工作。

理论

看来您想要k-multicombination 中所有 k 的 k-combinations,而不是简单的组合。请参阅重复组合的数量

换句话说,您需要集合中元素的所有 k 组合,对于从 0 到 n 的所有 k,其中 n 是集合大小。

相关的 SO 问题:SQL - Find all possible combination,其中有关于位计数的非常有趣的答案。

Pg中存在位操作,因此应该可以使用位计数方法。您希望它更有效,但由于从数组中选择分散的元素子集非常慢,它实际上运行起来更慢

CREATE OR REPLACE FUNCTION bitwise_subarray(arr anyarray, elements integer)
RETURNS anyarray AS $$
SELECT array_agg($1[n+1]) 
FROM generate_series(0,array_upper($1,1)-1) n WHERE ($2>>n) & 1 = 1;
$$ LANGUAGE sql;

COMMENT ON FUNCTION bitwise_subarray(anyarray,integer) IS 'Return the elements from $1 where the corresponding bit in $2 is set';

CREATE OR REPLACE FUNCTION comb_bits(anyarray) RETURNS SETOF anyarray AS $$ 
SELECT bitwise_subarray($1, x) 
FROM generate_series(0,pow(2,array_upper($1,1))::integer-1) x;
$$ LANGUAGE 'sql';

如果你能找到一种更快的写作方式,bitwise_subarraycomb_bits将会非常快。比如说,一个小的 C 扩展函数,但我只是疯狂地写一个这样的答案

于 2012-08-17T02:14:05.137 回答