查找整数序列包含给定子序列的行

Question

问题

注意：我指的是数学序列，而不是PostgreSQL的序列机制。

我有一个表示整数序列的表。定义是：

CREATE TABLE sequences
(
  id serial NOT NULL,
  title character varying(255) NOT NULL,
  date date NOT NULL,
  sequence integer[] NOT NULL,
  CONSTRAINT "PRIM_KEY_SEQUENCES" PRIMARY KEY (id)
);

我的目标是使用给定的子序列查找行。也就是说，sequence字段是包含给定子序列的序列的行（在我的情况下，序列是有序的）。

例子

假设该表包含以下数据：

+----+-------+------------+-------------------------------+
| id | title |    date    |           sequence            |
+----+-------+------------+-------------------------------+
|  1 | BG703 | 2004-12-24 | {1,3,17,25,377,424,242,1234}  |
|  2 | BG256 | 2005-05-11 | {5,7,12,742,225,547,2142,223} |
|  3 | BD404 | 2004-10-13 | {3,4,12,5698,526}             |
|  4 | BK956 | 2004-08-17 | {12,4,3,17,25,377,456,25}     |
+----+-------+------------+-------------------------------+

所以如果给定的子序列是{12, 742, 225, 547}，我想找到第 2 行。

同样，如果给定的子序列是{3, 17, 25, 377}，我想找到第 1 行和第 4 行。

最后，如果给定的子序列是{12, 4, 3, 25, 377}，则不返回任何行。

调查

首先，我并不完全确定用数组数据类型表示序列是明智的。虽然这似乎适合这种情况；我担心它会使处理更复杂。也许最好以不同的方式表示序列，使用与另一个表的关系模型。

以同样的方式，我考虑使用unnest数组函数扩展序列，然后添加我的搜索条件。尽管如此，序列中的术语数量是可变的，我不知道如何做到这一点。

我知道也可以使用intarray模块的subarray功能在子序列中切割我的序列，但我看不出它对我的搜索有什么好处。

约束

即使目前我的模型仍在开发中，该表也打算由许多序列组成，行数在 50,000 到 300,000 之间。所以我有很强的性能约束。

在我的例子中，我使用了相对较小的整数。在实践中，这些整数可能会变得更大，直至溢出bigint。在这种情况下，我认为最好将数字存储为字符串（因为没有必要执行这些数学运算序列）。但是，选择此解决方案后，就无法使用上面提到的intarray模块。

Answer 1

当您将数组转换为字符串并用逗号替换大括号时，您可以轻松找到子序列：

translate(cast(sequence as varchar(10000)), '{}',',,')

{1,3,17,25,377,424,242,1234} -> ',1,3,17,25,377,424,242,1234,'

对您要搜索的数组执行相同的操作并添加前导和尾随%：

'%' || translate(cast(searchedarray as varchar(10000)), '{}',',,') || '%'

{3, 17, 25, 377} -> '%,3,17,25,377,%'

现在您可以使用以下方法进行比较LIKE：

WHERE        translate(cast(sequence      as varchar(10000)), '{}',',,')
 LIKE '%' || translate(cast(searchedarray as varchar(10000)), '{}',',,') || '%'

编辑：

小提琴又开始工作了。

如果数组被标准化为每个值一行，您可以应用基于集合的逻辑：

CREATE TABLE sequences
( id int NOT NULL,
  n int not null,
  val numeric not null
);

insert into sequences values(  1, 1,1     );
insert into sequences values(  1, 2,3     );
insert into sequences values(  1, 3,17    );
insert into sequences values(  1, 4,25    );
insert into sequences values(  1, 5,377   );
insert into sequences values(  1, 6,424   );
insert into sequences values(  1, 7,242   );
insert into sequences values(  1, 8,1234  );
insert into sequences values(  2, 1,5     );
insert into sequences values(  2, 2,7     );
insert into sequences values(  2, 3,12    );
insert into sequences values(  2, 4,742   );
insert into sequences values(  2, 5,225   );
insert into sequences values(  2, 6,547   );
insert into sequences values(  2, 7,2142  );
insert into sequences values(  2, 8,223   );
insert into sequences values(  3, 1,3     );
insert into sequences values(  3, 2,4     );
insert into sequences values(  3, 3,12    );
insert into sequences values(  3, 4,5698  );
insert into sequences values(  3, 5,526   );          
insert into sequences values(  4, 1,12    );
insert into sequences values(  4, 2,4     );
insert into sequences values(  4, 3,3     );
insert into sequences values(  4, 4,17    );
insert into sequences values(  4, 5,25    );
insert into sequences values(  4, 6,377   );
insert into sequences values(  4, 7,456   );
insert into sequences values(  4, 8,25    );
insert into sequences values(  5, 1,12    );
insert into sequences values(  5, 2,4     );
insert into sequences values(  5, 3,3     );
insert into sequences values(  5, 4,17    );
insert into sequences values(  5, 5,17    );
insert into sequences values(  5, 6,25    );
insert into sequences values(  5, 7,377   );
insert into sequences values(  5, 8,456   );
insert into sequences values(  5, 9,25    );

n必须是连续的，没有重复，没有间隙。现在加入共同值并利用序列是连续的事实:-)

with searched (n,val) as (
  VALUES
   ( 1,3  ),
   ( 2,17 ),
   ( 3,25 ),
   ( 4,377)
)
select seq.id, 
   -- this will return the same result if the values from both tables are in the same order
   -- it's a meaningless dummy, but the same meaningless value for sequential rows 
   seq.n - s.n as dummy,
   seq.val,
   seq.n,
   s.n 
from sequences as seq join searched as s
on seq.val = s.val
order by seq.id, dummy, seq.n;

最后计算具有相同虚拟值的行数并检查它是否是正确的数字：

with searched (n,val) as (
  VALUES
   ( 1,3  ),
   ( 2,17 ),
   ( 3,25 ),
   ( 4,377)
)
select distinct seq.id
from sequences as seq join searched as s
on seq.val = s.val
group by 
   seq.id,
   seq.n - s.n
having count(*) = (select count(*) from searched)
;

尝试对序列（val，id，n）建立索引。