Question Details

No question body available.

Tags

sql postgresql

Answers (1)

May 31, 2026 Score: 0 Rep: 87,950 Quality: Medium Completeness: 100%

My first draft has minor performance improvements:

  • reducing joins by using window functions
  • materialise the TRIM(UPPER()) and then index on it

The two logical issues it addresses are

  • Avoiding the break-points being close to each other
  • Avoiding selecting two minima in a single "group"

The first issue is addressed by offsetting everything by "half a page", and not breaking in the first or last "pages".

string oldgroup old break point new group new break point
aaa 0 0
bbb 0 0
ccc 0 0
ddd 0 1
eee 0 yes 1
fff 1 yes 1 yes
ggg 1 1
hhh 1 1
iii 1 2
jjj 1 2

(These a total fictional values to illustrate the change.)

Old method breaks two pages once each, and yielding three pages, one being tiny:

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

New method breaks one fewer page, and biases the break point the the centre:

  • aaa -> fff
  • ggg -> jjj

The second issue is addressed using FIRSTVALUE() instead of MAX().

CREATE TABLE Items (
  ItemType INTEGER,
  ItemName VARCHAR(512),
  ItemNameUpper VARCHAR(512) GENERATED ALWAYS AS (TRIM(BOTH FROM upper(ItemName))) STORED
);
CREATE INDEX ixtesttypenameUpper ON Items(ItemType, ItemNameUpper);
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'
 ]
)
INSERT INTO Items
SELECT t, stringagg(chars[random(0, 165)], '')
FROM chars
CROSS JOIN generateseries(1, 3) t
CROSS JOIN generateseries(1, 5) l
CROSS JOIN generateseries(1, 400) i
GROUP BY t, i;

WITH
  stats1(ItemType, NameStarts, len, NameCount)
AS
(
  SELECT
    Items.ItemType,
    nameStarts,
    i,
    SUM(COUNT(*)) OVER (PARTITION BY ItemType, i ORDER BY NameStarts)
  FROM
    Items
  CROSS JOIN
    generateseries(1, 3)  AS i
  CROSS JOIN LATERAL
  (
    SELECT LEFT(ItemNameUpper, i)
  )
    AS namestarts(nameStarts)
  GROUP BY
    Items.ItemType,
    nameStarts,
    i    
),
   stats3(ItemType, NameStarts, NameCount, totalnamecount)
AS
(
  SELECT
    ItemType,
    MIN(NameStarts),
    NameCount,
    MAX(NameCount) OVER (PARTITION BY ItemType)
 FROM
    stats1
 GROUP BY
    ItemType,
    NameCount
),
  stats4(ItemType, NameStarts, NameCount, naivegroupid, score, newgroupmarker, minscore)
AS
(
  SELECT
    stats3.ItemType,
    stats3.NameStarts,
    stats3.NameCount,
    page.id,
    page.score,
    CASE
      WHEN page.id IN (0, totalnamecount / groupsize)                                                  THEN 0
      WHEN NameCount = FIRSTVALUE(NameCount) OVER (PARTITION BY ItemType, page.id ORDER BY page.score) THEN 1
                                                                                                        ELSE 0
    END,
    MIN(page.score) OVER (PARTITION BY ItemType, page.id)
  FROM
    stats3
  CROSS JOIN LATERAL
  (
    SELECT
      CASE
        WHEN SQRT(stats3.totalnamecount) < 20
        THEN stats3.totalnamecount
        ELSE SQRT(stats3.totalnamecount)::int
     END
  )
    AS groupsize(groupsize)
  CROSS JOIN LATERAL
  (
    SELECT
      (stats3.NameCount / (groupsize / 2) + 0.5)::int >> 1,
      (LENGTH(stats3.NameStarts) + 3) * (1 + POWER(sin(pi() * stats3.NameCount / groupsize), 2))
  )
    AS page(id, score)
),
  debugdata
AS
(
  SELECT
    itemType,
    nameStarts,
    nameCount,
    naiveGroupid,
    score,
    minscore,
    SUM(newgroupmarker) OVER (PARTITION BY ItemType ORDER BY namecount)  AS groupid
  FROM
    Stats4
  ORDER BY
    1,3,2,4
)
--SELECT * FROM debugdata WHERE ItemType = 2 ORDER BY ItemType, namecount
SELECT ItemType, groupid, MIN(namestarts), MAX(namestarts), COUNT(*) AS groupsize FROM debugdata GROUP BY itemType, groupid ORDER BY 1, 2
;
itemtype groupid min max groupsize
1 0 0 7K 19
1 1 8 AYC 18
1 2 A CX 21
1 3 C DYM 17
1 4 D FGP 23
1 5 F HEH 20
1 6 HF HZE 17
1 7 H JEJ 23
1 8 J KY 20
1 9 K LYP 21
1 10 L MW 17
1 11 M OK 22
1 12 O PJ 20
1 13 P QSC 17
1 14 Q SDO 22
1 15 S TGJ 21
1 16 T UY 19
1 17 U WI 20
1 18 W XT 17
1 19 X ZZF 23
2 0 0 ADL 20
2 1 A BA4 19
2 2 BA BV 20
2 3 B DHM 19
2 4 D EJF 20
2 5 E FT 16
2 6 F HM 21
2 7 H IZH 22
2 8 I JY 16
2 9 J LOA 22
2 10 L MP 20
2 11 M OMB 20
2 12 O PFO 20
2 13 P QYF 21
2 14 Q SO 22
2 15 S UGS 17
2 16 U VR 19
2 17 V XH 21
2 18 X YJB 20
2 19 Y ZZL 21
3 0 1 8V 21
3 1 8 BD8 17
3 2 B CV 21
3 3 C DY 17
3 4 D FP 22
3 5 F GX 17
3 6 G IT 25
3 7 I JT 15
3 8 J LW 24
3 9 L NJ 19
3 10 N OW 18
3 11 O QKC 23
3 12 Q ROB 19
3 13 R SR 19
3 14 S TV 21
3 15 T UXI 18
3 16 U VX 18
3 17 V XV 24
3 18 X YW 17
3 19 Y ZR 21

fiddle

Notes:

  • I've changed the formatting to suit myself, that's optional.
  • I've also started replacing stat1, stat2, stat3 with useful naming, that should never be optional, it made it very hard to initially decipher your code.
  • I change the scoring function to exaggerate the variable group sizes, that should be easy to change to anything else.

I'm certain that this can be optimised significantly further, but I stopped when you commented that you don't care about that.