我有一张表，其中包含大量按类型/命名的项，我想创建一个（物化？）视图把它们聚合起来，以便以后通过界面让用户更容易选择。

描述

目标是：

如果有N 个相同类型的元素，就把它们分成sqrt(N) 组，每组大小为sqrt(N)。这样就不会出现要滚动查看成千上万条元素的情况，比如有1 万条，界面将显示100行分组，每组再展开成100行组内项。多点击一次即可，但滚动量会大幅减少。

界面将把组名显示为包含其中命名元素的区间。
例如，如果某组包含所有以A 和B 开头的项（但不包含C 及以后），那么该分组的名称应该是 A-B。
如果某组包含所有以C 开头直到如EG，但以EH开头的元素属于下一组，则该分组的名称应为 C-EG。

思路是：

不再通过比较文本来决定列表应该如何分组，而是用一个函数来对项进行评分。这样做的原因，稍后会明白。

无论如何，启发式方法把这一团乱麻转化为一个相对常见的问题，即寻找一个函数的局部最小值。

这里的twist（解释为什么我要用一个函数）：

我本可以令每个分组的大小恰好相同（忽略sqrt(N) 四舍五入到最接近的整数），但我更想在分组大小和分组名长度之间找到一个折衷。由于分组名的模式是 <start of group> - <end of group>，我理想地希望 <start of group> 和 <end of group> 的长度至多为3 个字符。
因为我对计数可以“相对”偏离sqrt(N) 愿意接受，所以也接受它们略有滞后。因此我的想法是把这个查询的结果写入一个物化视图，例如每天夜里刷新一次。

该函数的工作原理如下：

1. 对每个项，统计它与前一个项在首字母上共有多少个相同的字母。
2. 取一个sin^2函数作为分数，设定参数使其在区间 [1-N] 内大致在sqrt(N) 次振荡。
3. 将上面两步中的参数化引入（加入常数、乘以常数、再乘方……等，以获得更好的效果）。
4. 将两者相乘得到一个“分数”。
5. 寻找最小分数，它将作为分组的结束点。

如果这对你有帮助，下面是在100项时的效果（名称用下述查询随机生成），其中SIN用蓝色，分数用黑色。

如果我想要例如在保持组大小一致的前提下让组名更短，可以调整分数，使SIN不再只是平方，而是提升到更高的幂次：这会让正弦波的谷部变平、峰部变尖。
这样一来，更多项会落在谷部，因此我会更有机会让较短但边界略偏离的分组优先于跨越sqrt(N) 的较长边界的分组。

以下是两张图的放大版本：

在这里，启发式决定列表应在 rtetx 附近分割。分割点前的分组将命名为 [...] - RC，分割点后的分组将命名为 RT - [...]。

将SIN函数提升到更高的幂次（注：我用来绘制图表的软件会把点插值成平滑曲线。该曲线只在点位上正确，点与点之间并不严格）会增加容忍度。现在，分组也可以在 rcEYu 或 slkkE 附近均匀分割。
现在，分组名称将是以下两种情形之一：

• [...] - Q 和 R - [...]
• 或 [...] - R 和 S - [...]

现在，对于两个分组的公共边界只需要1 个字母，而此前需要2 个字母。

查询

我尝试了以下查询

1. 使用随机数据构建数据样本

CREATE TABLE Test (
 ItemType INTEGER,
 ItemName VARCHAR
);

WITH Chars(chars) AS (
 SELECT ARRAY[
     'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
     'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
     'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
     'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
     'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
     'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
 ]
)
INSERT INTO Test
SELECT t, string_agg(chars[random(0, 165)], '')
FROM chars
CROSS JOIN generate_series(1, 3) t
CROSS JOIN generate_series(1, 5) l
CROSS JOIN generate_series(1, 400) i
GROUP BY t, i;

1. 查找用于分组名称的文本（查询耗时 <5秒，表明需要一个物化视图）。

WITH Items(ItemType, ItemName) AS (
 SELECT ItemType, TRIM(BOTH FROM upper(ItemName)) FROM Test
), stats1(ItemType, NameStarts) AS (
 SELECT DISTINCT Items.ItemType, TRIM(BOTH FROM upper(left(ItemName, generate_series(1, 3)))) AS btrim
 FROM Items
 ), stats2(ItemType, NameStarts, NameCount) AS (
SELECT s1.ItemType, s1.NameStarts,
 count(*) FILTER (WHERE left(i.ItemName, length(s1.NameStarts)) <= s1.NameStarts) AS count
 FROM stats1 s1
 JOIN items i ON s1.ItemType = i.ItemType
 GROUP BY s1.ItemType, s1.NameStarts
), stats3(ItemType, NameStarts, NameCount, totalnamecount) AS (
SELECT stats2.ItemType,
 min(stats2.NameStarts) AS min,
 stats2.NameCount,
 max(stats2.NameCount) OVER (PARTITION BY stats2.ItemType) AS max
 FROM stats2
 GROUP BY stats2.ItemType, stats2.NameCount
), stats4(ItemType, NameStarts, NameCount, score, groupnumber) AS (
 SELECT stats3.ItemType,
 stats3.NameStarts,
 stats3.NameCount,
     length(stats3.NameStarts) * (.05 + .95 * power(sin(pi() * stats3.NameCount / sqrt(stats3.totalnamecount)::integer), 2)),
 ((stats3.NameCount - sqrt(stats3.totalnamecount) / 2) / sqrt(stats3.totalnamecount))::integer AS int4
 FROM stats3
 WHERE stats3.NameCount > 4 AND (stats3.totalnamecount - stats3.NameCount) > 4 AND stats3.totalnamecount > 50
)
SELECT s1.ItemType, s1.NameStarts, s1.NameCount
FROM stats4 s1
JOIN (
 SELECT stats4.ItemType, min(stats4.score) AS bestscore, stats4.groupnumber
 FROM stats4
 GROUP BY stats4.ItemType, stats4.groupnumber
) s2 ON s1.ItemType = s2.ItemType AND s1.groupnumber = s2.groupnumber
WHERE s1.score = s2.bestscore

问题

在上面的查询中，我添加了 NameCount 列以追踪每个分组包含多少项。由于示例数据由3 组、每组400项组成，我预计会有3 种类型，每种类型有20个分组，每组大约20项（因此第3 列应显示0、20、40、60、……）。
然而，当我得到正确的行时，还会出现额外的分组，其中包含1-2条项。举例来说，我会看到：

• 第一组：NameCount = 20
• 第二组：NameCount = 39
• 第三组：NameCount = 41

发生这种情况时，意味着该函数计算出两个值相等的分界点；其中一个需要去掉。

我似乎找不到一个简单的方法来移除这些多余的记录。有人有点子吗？

编辑：为澄清我的需求（其中一些会有重复，请见谅）：

1. 一个应用在UI上显示查询结果。它可以（并且很可能会）处理查询的输出。
2. 最终目标是通过将项分组成二级层次结构来减少查看列表中任意项所需的滚动量。
3. 对于N 项，分组应有sqrt(N) 组，每组大约sqrt(N) 项。每组项的数量取决于启发式在严格（目标为sqrt(N)）或容忍（在sqrt(N) 与分组名长度之间折衷）之间的取舍。
4. sqrt(N) 不一定是整数。
5. 对于10000，我期望恰好有100组，每组100项。
6. 对于10001，可以接受有100或 101组。如果你创建101组，我也不介意把项分布到所有这些组里。
   这也就是我查询中的做法（至少在修复问题前的一个版本中）——完全忽略这个问题：第一百组每组100项，最后一组只有1 项（毕竟最后一组出现在末尾，需要更多滚动才能到达，比其他组都要多）。
7. 数据来自真实世界的名称，因此list中所有项都共享相同前3 个字母的情况基本不存在。即使存在如3 组项共享同一前三字母的情形，返回1 组也是可以的。应用将处理其余部分。
8. 目前把数据保存在物化视图中的有3 个原因： 1) 对应用来说更快。
   2) 新数据在表中不经常插入，因此对分组没有太大影响（例如在一个10k的表中插入10条记录，通常不会改变分组）。
   3) 用户在同一天多次查看同一列表时，可以确保得到相同的分组。只有他们睡觉后，界面的分组才会不同。
9. 由于数据插入和分组更新之间存在延迟，查询不需要（也可能不应）返回每个分组的下界和上界。举例来说，如果两个相邻分组是 A-B 和 E-F，应用将显示连续的片段，如 A-D 和 E-F。如果不是，那么以 C 开头的项就无法定位。

解决方案

我加入了一些性能改进：

• 将 TRIM(UPPER()) 物化后再对其建立索引
• 避免对 generate(1,3) 进行CROSS JOIN
• 使用窗口函数替代连接和聚合，避免联接与聚合
• 尽量让WINDOW子句与索引匹配

它要解决的两个主要逻辑问题是

• 避免分割点彼此太接近
• 避免在一个“分组”中选出两个最小值

第一个问题 通过将所有项偏移一个“半页”的距离来解决，并且不在第一页或最后一页处断开。

（这些都是虚构的数值，用以说明变化。）

旧方法在两页各断一次，总共产生三页，其中一页很小：

• aaa -> eee
• fff -> fff
• ggg -> jjj

新方法少断一页，并将断点偏置到中心：

• aaa -> fff
• ggg -> jjj

第二个问题 通过使用 ROW_NUMBER() = 1 取代 score = MIN(score) 来解决。

CREATE TABLE Items (
  item_type       INTEGER,
  item_name       VARCHAR(8),
  item_name_upper VARCHAR(8) GENERATED ALWAYS AS (TRIM(BOTH FROM UPPER(item_name))) STORED
);
CREATE INDEX ix_test_type_nameUpper ON items(item_type, item_name_upper);

SET LOCAL SEED = 0.5;

WITH Chars(chars) AS (
 SELECT ARRAY[
     'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
     'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
     'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
     'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
     'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
     'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
     'a', 'b', 'c', 'd', 'e',
     'a', 'b', 'c', 'd', 'e',
     'a', 'b', 'c', 'd', 'e',
     'a', 'b', 'c', 'd', 'e',
     'a', 'b', 'c', 'd', 'e'
 ]
)
INSERT INTO items
SELECT t, string_agg(chars[random(0, 300)], '')
FROM chars
CROSS JOIN generate_series(1, 3) t
CROSS JOIN generate_series(1, 5) l
CROSS JOIN generate_series(1, 421) i
GROUP BY t, i;

CREATE VIEW
  items_paginated AS
WITH
  look_around(item_type, item_name, type_row_count, rn, prev_name)
AS
(
  SELECT
    item_type,
    item_name_upper,
    COUNT(*) OVER (PARTITION BY item_type),
    ROW_NUMBER()                OVER (PARTITION BY item_type ORDER BY item_name_upper),
    LAG(item_name_upper, 1, '') OVER (PARTITION BY item_type ORDER BY item_name_upper)
  FROM
    items
),
  prefixed(item_type, item_name, type_row_count, rn, prev_name, name_prefix)
AS
(
  SELECT
    *,
    prefix
  FROM
    look_around
  CROSS JOIN LATERAL
  (
    SELECT
      CASE
        WHEN LEFT(item_name, 3) = LEFT(prev_name, 3) THEN NULL
        WHEN LEFT(item_name, 2) = LEFT(prev_name, 2) THEN LEFT(item_name, 3)
        WHEN LEFT(item_name, 1) = LEFT(prev_name, 1) THEN LEFT(item_name, 2)
                                                     ELSE LEFT(item_name, 1)
      END
  )
    AS prefix(prefix)
),
  paginated_and_scored(item_type, item_name, type_row_count, rn, name_prefix, group_count, group_size, theta, naive_group_id, score, new_group_marker, min_score)
AS
(
  SELECT
    item_type,
    item_name,
    type_row_count,
    rn,
    name_prefix,
    group_count,
    group_size,
    theta,
    page.id,
    page.score,
    -- Mark as new page start if lowest score in prelimary group
    -- > But never mark a new page start in first or last group
    CASE
      WHEN page.id = 0                                                                     THEN 0
      WHEN page.id = group_count                                                           THEN 0
      WHEN 1 = ROW_NUMBER() OVER (PARTITION BY item_type, page.id ORDER BY page.score)     THEN 1
                                                                                           ELSE 0
    END,
    MIN(page.score) OVER (PARTITION BY item_type, page.id)
  FROM
    prefixed
  CROSS JOIN LATERAL
  (
    -- Calculate the integer number of expected output groups
    -- > a group either exists, or it doesn't, so it has to be an integer value
    SELECT
      CASE
        WHEN type_row_count < 20
        THEN 1
        ELSE SQRT(type_row_count)
     END::INT
  )
    AS group_count(group_count)
  CROSS JOIN LATERAL
  (
    -- Calculate the average number of rows per group
    -- > FLOAT so that different groups can be different sizes such as 2,2,3
    -- > Later code takes care of "carrying the remainder" to augment subsequent group sizes
    SELECT
      type_row_count::FLOAT / group_count
  )
    AS group_size(group_size)
  CROSS JOIN LATERAL
  (
    SELECT
      -- Calculate the phase angle for the current row
      -- > Used by scoring function
      -- > start at pi()
      -- > complete one cycle (2*pi()) every `group_size` rows
      pi() * 2 * (rn-1) / group_size + pi()
  )
    AS theta(theta)
  CROSS JOIN LATERAL
  (
    SELECT
      -- Calculate the provisional page id
      -- > page 0 = first (group size / 2) rows
      -- > page 1 = next (group size) rows
      -- > page n = last (group size / 2) rows
      FLOOR(theta / pi())::INT / 2,

      -- arbitrary scoring
      -- > lower is better
      -- > biased towards every `group_size` rows, through cosine function
      -- > biased towards shorter prefixes by mutiplying by prefix length
      (LENGTH(name_prefix) + 1)
      *
      (POWER((COS(theta) + 1) / 2, 2) + 0.5) -- `+ 1` and `/ 2` to make cosine give values 0..1
  )
    AS page(id, score)
)
SELECT
  *,
  -- cumulative sum to derive new page_id
  SUM(new_group_marker) OVER (PARTITION BY item_type ORDER BY item_name)  AS page_id
FROM
  paginated_and_scored

/*
 * Summary info, for debugging
 */
SELECT
  item_type,
  page_id,
  MIN(name_prefix)           AS first_prefix,
  MAX(name_prefix)           AS last_prefix,
  COUNT(*)                   AS page_size
FROM
  items_paginated
GROUP BY
  item_type,
  page_id
ORDER BY
  1, 2
;

/*
 * Final output for actual use.
 */

SELECT
  item_type,
  page_id,
  name_prefix   AS first_prefix
FROM
  items_paginated
WHERE
  new_group_marker = 1
ORDER BY
  1, 2
;

fiddle