SQL HowTo: оптимизируем рекурсию (Advent of Code 2024, Day 9: Disk Fragmenter)15.01.2025 13:45

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

В этой части рассмотрим некоторые «грабли», на которые можно наступить, реализуя рекурсивные алгоритмы на SQL… Которые иногда можно сделать вовсе нерекурсивными, ускоряя запрос в десятки раз!

6ea1fadef8554c68eeee6218a7763373.jpg

Оригинальная постановка задачи и ее перевод:

Advent of Code 2024, Day 9: Disk Fragmenter

--- День 9: Фрагментатор диска ---

Еще одно нажатие кнопки оставляет вас в знакомых коридорах дружелюбных амфипод! Хорошо, что каждый из вас каким-то образом получил свою собственную мини-подводную лодку. Историки улетают на поиски Шефа, в основном врезаясь прямо в стены.

Пока Историки быстро разбираются, как управлять этими штуками, вы замечаете в углу амфипода, который борется со своим компьютером. Он пытается сделать больше непрерывного свободного пространства, сжимая все файлы, но его программа не работает; вы предлагаете помочь.

Он показывает вам карту диска (ваши входные данные для головоломки), которую он уже сгенерировал. Например: 

2333133121414131402

Карта диска использует плотный формат для представления расположения файлов и свободного пространства на диске. Цифры попеременно указывают на длину файла и длину свободного пространства.

Итак, карта диска подобная 12345будет представлять файл из одного блока, два блока свободного пространства, файл из трех блоков, четыре блока свободного пространства и затем файл из пяти блоков. Карта диска подобная 90909будет представлять три файла из девяти блоков подряд (без свободного пространства между ними).

Каждый файл на диске также имеет идентификационный номер,  основанный на порядке файлов, как они появляются до того, как они были переупорядочены, начиная с ID 0. Таким образом, карта диска 12345имеет три файла: файл из одного блока с ID 0, файл из трех блоков с ID 1и файл из пяти блоков с ID 2. Используя один символ для каждого блока, где цифры — это идентификатор файла, а . — свободное пространство, карта диска 12345представляет такие отдельные блоки: 

0..111....22222

Первый пример выше,  2333133121414131402представляет собой такие отдельные блоки: 

00...111...2...333.44.5555.6666.777.888899

Амфипод хотел бы перемещать блоки файлов по одному за раз с конца диска в самый левый блок свободного пространства (пока не останется пробелов между блоками файлов). Для карты диска 12345процесс выглядит следующим образом: 

0..111....22222
02.111....2222.
022111....222..
0221112...22...
02211122..2....
022111222......

Первый пример требует еще нескольких шагов: 

00...111...2...333.44.5555.6666.777.888899
009..111...2...333.44.5555.6666.777.88889.
0099.111...2...333.44.5555.6666.777.8888..
00998111...2...333.44.5555.6666.777.888...
009981118..2...333.44.5555.6666.777.88....
0099811188.2...333.44.5555.6666.777.8.....
009981118882...333.44.5555.6666.777.......
0099811188827..333.44.5555.6666.77........
00998111888277.333.44.5555.6666.7.........
009981118882777333.44.5555.6666...........
009981118882777333644.5555.666............
00998111888277733364465555.66.............
0099811188827773336446555566..............

Последним шагом этого процесса сжатия файлов является обновление контрольной суммы файловой системы. Чтобы вычислить контрольную сумму, сложите результат умножения позиции каждого из этих блоков на номер идентификатора файла, который он содержит. Самый левый блок находится в позиции 0. Если блок содержит свободное пространство, пропустите его.

Продолжая первый пример, позиция первых нескольких блоков, умноженная на номер идентификатора файла, равна 0 * 0 = 0,  1 * 0 = 0,  2 * 9 = 18,  3 * 9 = 27,  4 * 8 = 32, и т. д. В этом примере контрольная сумма представляет собой сумму этих значений,  1928.

Упакуйте жесткий диск амфипода,  используя запрошенный им процесс. Какова итоговая контрольная сумма файловой системы? (Будьте осторожны при копировании/вставке входных данных для этой головоломки; это одна очень длинная строка.)

Ваш ответ на головоломку был 6307275788409.

--- Часть вторая ---

После завершения сразу же становятся ясны две вещи. Во-первых, на диске определенно гораздо больше непрерывного свободного пространства, как и надеялся амфипод. Во-вторых, компьютер работает гораздо медленнее! Может быть, введение всей этой фрагментации файловой системы было плохой идеей?

У предприимчивого амфипода уже есть новый план: вместо того, чтобы перемещать отдельные блоки, он хотел бы попробовать уплотнить файлы на своем диске, перемещая целые файлы.

На этот раз попытайтесь переместить целые файлы в самый левый диапазон блоков свободного пространства, в которые может поместиться файл. Попытайтесь переместить каждый файл ровно один раз в порядке убывания номера идентификатора файла, начиная с файла с самым большим номером идентификатора файла. Если слева от файла нет диапазона свободного пространства, достаточно большого для размещения файла, файл не перемещается.

Первый пример из предыдущего теперь выглядит иначе: 

00...111...2...333.44.5555.6666.777.888899
0099.111...2...333.44.5555.6666.777.8888..
0099.1117772...333.44.5555.6666.....8888..
0099.111777244.333....5555.6666.....8888..
00992111777.44.333....5555.6666.....8888..

Процесс обновления контрольной суммы файловой системы тот же самый; теперь контрольная сумма этого примера будет 2858.

Начать заново, теперь сжимая жесткий диск амфипода, используя этот новый метод. Какова итоговая контрольная сумма файловой системы?

Часть 1

Решение этой задачи достаточно сложно для понимания «сходу», поэтому давайте разберем его детально пошагово.

Для начала получим из входной «карты» занятых блоков. Автонумерацию строк нам поможет получить уже знакомый по решениям предыдущих задач функционал WITH ORDINALITY, а ID файла — половина номера в каждой нечетной позиции: 

WITH map AS (
  SELECT
    sz::::integer -- размер сегмента
  , n             -- порядковый номер сегмента
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid       -- ID файла
  FROM
    regexp_split_to_table( -- разбиение в таблицу ...
      '2333133121414131402'
    , ''                   -- ... по отдельным символам
    )
      WITH ORDINALITY T(sz, n)
)
sz |  n | fid
 2 |  1 |   0
 3 |  2 |
 3 |  3 |   1
 3 |  4 |
 1 |  5 |   2
 3 |  6 |
 3 |  7 |   3
 1 |  8 |
 2 |  9 |   4
 1 | 10 |
 4 | 11 |   5
 1 | 12 |
 4 | 13 |   6
 1 | 14 |
 3 | 15 |   7
 1 | 16 |
 4 | 17 |   8
 0 | 18 |
 2 | 19 |   9

Теперь превратим нашу карту сегментов в две карты-массива отдельных блоков — представления дискового пространства и «файловых» блоков в порядке перемещения (обратном): 

, blk AS (
  SELECT
    array_agg(fid ORDER BY n) blkdsk       -- собираем все блоки в прямом порядке
  , array_agg(fid ORDER BY n DESC)         -- собираем в обратном порядке ...
      FILTER(WHERE fid IS NOT NULL) blkfil -- ... только занятые файлами блоки
  FROM
    map
  , unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
)
blkdsk : {0,0,NULL,NULL,NULL,1,1,1,NULL,NULL,NULL,2,NULL,NULL,NULL,3,3,3,NULL,4,4,NULL,5,5,5,5,NULL,6,6,6,6,NULL,7,7,7,NULL,8,8,8,8,9,9}
blkfil : {9,9,8,8,8,8,7,7,7,6,6,6,6,5,5,5,5,4,4,3,3,3,2,1,1,1,0,0}

Здесь мы воспользовались array_fill для формирования заполненного NULL массива длины sz для каждой записи сегмента, и тут же «развернули» его в sz записей, «размножив» исходный сегмент нужное нам число раз.

Собственно, остается лишь вычислить искомую контрольную сумму, используя в рекурсивном (не забываем добавить WITH RECURSIVE перед map) «цикле» два указателя на позиции в каждом из массивов: 

, r AS (
  SELECT
    1 posdsk -- позиция блока "на диске"
  , 1 posfil -- позиция "перемещаемого" файлового блока
  , 0::bigint checksum
UNION ALL
  SELECT
    posdsk + 1 -- позиция "на диске" увеличивается каждый раз
  , posfil + (blkdsk[posdsk] IS NULL)::integer -- позиция "файла" - только если "дисковый" блок пуст
  , checksum + (posdsk - 1) * coalesce(blkdsk[posdsk], blkfil[posfil])
  FROM
    r
  , blk
  WHERE
    posdsk <= array_length(blkfil, 1) -- вычислять надо до исчерпания всех файловых блоков
)
posdsk | posfil | checksum
     1 |      1 |        0
     2 |      1 |        0
     3 |      1 |        0
     4 |      2 |       18
     5 |      3 |       45
     6 |      4 |       77
     7 |      4 |       82
     8 |      4 |       88
     9 |      4 |       95
    10 |      5 |      159
    11 |      6 |      231
    12 |      7 |      311
    13 |      7 |      333
    14 |      8 |      417
    15 |      9 |      508
    16 |     10 |      606
    17 |     10 |      651
    18 |     10 |      699
    19 |     10 |      750
    20 |     11 |      858
    21 |     11 |      934
    22 |     11 |     1014
    23 |     12 |     1140
    24 |     12 |     1250
    25 |     12 |     1365
    26 |     12 |     1485
    27 |     12 |     1610
    28 |     13 |     1766
    29 |     13 |     1928

Из полученной выборки остается лишь взять «последнее» (с наибольшим posdsk) значение checksum. В целом, наш итоговый запрос принимает следующий вид: 

WITH RECURSIVE map AS (
  SELECT
    sz::integer -- размер сегмента
  , n           -- порядковый номер сегмента
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid     -- ID файла
  FROM
    regexp_split_to_table( -- разбиение в таблицу ...
      '2333133121414131402'
    , ''                   -- ... по отдельным символам
    )
      WITH ORDINALITY T(sz, n)
)
, blk AS (
  SELECT
    array_agg(fid ORDER BY n) blkdsk
  , array_agg(fid ORDER BY n DESC) FILTER(WHERE fid IS NOT NULL) blkfil
  FROM
    map
  , unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
)
, r AS (
  SELECT
    1 posdsk -- позиция блока "на диске"
  , 1 posfil -- позиция "перемещаемого" файлового блока
  , 0::bigint checksum
UNION ALL
  SELECT
    posdsk + 1 -- позиция "на диске" увеличивается каждый раз
  , posfil + (blkdsk[posdsk] IS NULL)::integer -- позиция "файла" - только если "дисковый" блок пуст
  , checksum + (posdsk - 1) * coalesce(blkdsk[posdsk], blkfil[posfil])
  FROM
    r
  , blk
  WHERE
    posdsk <= array_length(blkfil, 1) -- вычислять надо до исчерпания всех файловых блоков
)
SELECT
  checksum
FROM
  r
ORDER BY
  posdsk DESC
LIMIT 1;

В принципе, этот запрос решает задачу, но при вводе целевой последовательности (а там 20 тысяч цифр-сегментов) уходит считать долго-долго…

Давайте посмотрим на план «маленького» запроса, чтобы заметить причину:

e8efbdc4c0958f963ff1a7c8d4366390.png

Оказывается, у нас вообще нет никаких промежуточных CTE map и blk! Чрезмерно «умный» PostgreSQL «заинлайнил» их вычисление, поскольку они используются по ходу запроса лишь однократно. Только вот из-за этого условие выхода из рекурсии (Join Filter в узле Nested Loop (#4)) ему приходится перевычислять на каждом шаге!

А оно ни разу не простое! Приведем его в минимально-читаемый вид: 

Join Filter: (
  r_1.posdsk <= array_length(
    (
      array_agg(
        CASE WHEN ((t.n % '2'::bigint) = 1) THEN (t.n / 2) ELSE NULL::bigint END
        ORDER BY t.n DESC
      )
      FILTER (
        WHERE (
          CASE WHEN ((t.n % '2'::bigint) = 1) THEN (t.n / 2) ELSE NULL::bigint END IS NOT NULL
        )
      )
    )
  , 1
  )
)

Чтобы PostgreSQL не слишком умничал, достаточно лишь добавить MATERIALIZED у CTE blk: 

WITH RECURSIVE map AS (
  SELECT
    sz::integer -- размер сегмента
  , n           -- порядковый номер сегмента
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid     -- ID файла
  FROM
    regexp_split_to_table( -- разбиение в таблицу ...
      '2333133121414131402'
    , ''                   -- ... по отдельным символам
    )
      WITH ORDINALITY T(sz, n)
)
, blk AS MATERIALIZED (
  SELECT
    array_agg(fid ORDER BY n) blkdsk
  , array_agg(fid ORDER BY n DESC) FILTER(WHERE fid IS NOT NULL) blkfil
  FROM
    map
  , unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
)
, r AS (
  SELECT
    1 posdsk -- позиция блока "на диске"
  , 1 posfil -- позиция "перемещаемого" файлового блока
  , 0::bigint checksum
UNION ALL
  SELECT
    posdsk + 1 -- позиция "на диске" увеличивается каждый раз
  , posfil + (blkdsk[posdsk] IS NULL)::integer -- позиция "файла" - только если "дисковый" блок пуст
  , checksum + (posdsk - 1) * coalesce(blkdsk[posdsk], blkfil[posfil])
  FROM
    r
  , blk
  WHERE
    posdsk <= array_length(blkfil, 1) -- вычислять надо до исчерпания всех файловых блоков
)
SELECT
  checksum
FROM
  r
ORDER BY
  posdsk DESC
LIMIT 1;

Тогда план выправляется, и результат вычисляется всего за 8 с небольшим секунд:

7ad02e7f44da936aa1cae139300a2770.png

А теперь — без рекурсии!

Давайте задумаемся — нужна ли нам тут рекурсия вообще, что мы с ее помощью делали?…

По сути, мы пронумеровали все блоки диска, а затем поставили соответствие между свободными блоками и занятыми файловыми в обратном порядке -, но это можно сделать и без всякой рекурсии! 

, blk AS (
  SELECT
    posdsk
  , fid
  , CASE
      WHEN fid IS NULL THEN
        count(*) FILTER(WHERE fid IS NULL) OVER(ORDER BY posdsk)
    END posfiln -- "пронумеруем" свободные блоки в прямом порядке
  , CASE
      WHEN fid IS NOT NULL THEN
        count(*) FILTER(WHERE fid IS NOT NULL) OVER(ORDER BY posdsk DESC)
    END posfilo -- "пронумеруем" занятые блоки в обратном порядке
  FROM
    (
      SELECT
        row_number() OVER() posdsk -- пронумеруем все блоки
      , map.*
      FROM
        map
      , unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
    ) T
)
posdsk | fid | posfiln | posfilo
     1 |   0 |         |      28
     2 |   0 |         |      27
     3 |     |       1 |
     4 |     |       2 |
     5 |     |       3 |
     6 |   1 |         |      26
     7 |   1 |         |      25
     8 |   1 |         |      24
     9 |     |       4 |
    10 |     |       5 |
    11 |     |       6 |
    12 |   2 |         |      23
    13 |     |       7 |
    14 |     |       8 |
    15 |     |       9 |
    16 |   3 |         |      22
    17 |   3 |         |      21
    18 |   3 |         |      20
    19 |     |      10 |
    20 |   4 |         |      19
    21 |   4 |         |      18
    22 |     |      11 |
    23 |   5 |         |      17
    24 |   5 |         |      16
    25 |   5 |         |      15
    26 |   5 |         |      14
    27 |     |      12 |
    28 |   6 |         |      13
    29 |   6 |         |      12
    30 |   6 |         |      11
    31 |   6 |         |      10
    32 |     |      13 |
    33 |   7 |         |       9
    34 |   7 |         |       8
    35 |   7 |         |       7
    36 |     |      14 |
    37 |   8 |         |       6
    38 |   8 |         |       5
    39 |   8 |         |       4
    40 |   8 |         |       3
    41 |   9 |         |       2
    42 |   9 |         |       1

Собственно, остается лишь совместить полученную выборку с собой же, стыкуя новую позицию перемещаемого файлового блока к старой через LEFT JOIN, и вычислить чек-сумму. Не забываем ограничить подсчет количеством занятых блоков: 

SELECT
  sum((n.posdsk - 1) * coalesce(n.fid, o.fid)) -- не забываем -1!
FROM
  blk n
LEFT JOIN
  blk o
    ON n.posfiln = o.posfilo -- совмещаем новую/старую позицию файлового блока
WHERE
  n.posdsk <= (SELECT sum(sz) FILTER(WHERE fid IS NOT NULL) FROM map); -- ограничиваемся только занятыми блоками

Полностью наш запрос теперь выглядит так: 

WITH map AS (
  SELECT
    sz::integer -- размер сегмента
  , n           -- порядковый номер сегмента
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid     -- ID файла
  FROM
    regexp_split_to_table( -- разбиение в таблицу ...
      '2333133121414131402'
    , ''                   -- ... по отдельным символам
    )
      WITH ORDINALITY T(sz, n)
)
, blk AS (
  SELECT
    posdsk
  , fid
  , CASE
      WHEN fid IS NULL THEN
        count(*) FILTER(WHERE fid IS NULL) OVER(ORDER BY posdsk)
    END posfiln -- "пронумеруем" свободные блоки в прямом порядке
  , CASE
      WHEN fid IS NOT NULL THEN
        count(*) FILTER(WHERE fid IS NOT NULL) OVER(ORDER BY posdsk DESC)
    END posfilo -- "пронумеруем" занятые блоки в обратном порядке
  FROM
    (
      SELECT
        row_number() OVER() posdsk -- пронумеруем все блоки
      , map.*
      FROM
        map
      , unnest(array_fill(NULL::integer, ARRAY[sz::integer])) -- размножим запись sz раз
    ) T
)
SELECT
  sum((n.posdsk - 1) * coalesce(n.fid, o.fid)) -- не забываем -1!
FROM
  blk n
LEFT JOIN
  blk o
    ON n.posfiln = o.posfilo -- совмещаем новую/старую позицию файлового блока
WHERE
  n.posdsk <= (SELECT sum(sz) FILTER(WHERE fid IS NOT NULL) FROM map); -- ограничиваемся только занятыми блоками

Нельзя сказать, что мы переписали запрос как-то слишком уж сложно, но его быстродействие увеличилось в 25 раз:

b70769705f1bdca1d8e13402e5e80d5d.png

Часть 2

Во второй части нас просят перемещать файлы на свободное место уже не отдельными блоками, а целиковыми сегментами.

Добавим вычисление позиции каждого такого сегмента в самое начало нашего запроса: 

WITH map AS (
  SELECT
    sz::integer -- размер сегмента
  , n           -- порядковый номер сегмента
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid     -- ID файла
  , sum(sz::bigint) OVER(ORDER BY n) - sz::bigint pos -- позиция начала сегмента
  FROM
    regexp_split_to_table( -- разбиение в таблицу ...
      '2333133121414131402'
    , ''                   -- ... по отдельным символам
    )
      WITH ORDINALITY T(sz, n)
)
sz |  n | fid | pos
 2 |  1 |   0 |   0
 3 |  2 |     |   2
 3 |  3 |   1 |   5
 3 |  4 |     |   8
 1 |  5 |   2 |  11
 3 |  6 |     |  12
 3 |  7 |   3 |  15
 1 |  8 |     |  18
 2 |  9 |   4 |  19
 1 | 10 |     |  21
 4 | 11 |   5 |  22
 1 | 12 |     |  26
 4 | 13 |   6 |  27
 1 | 14 |     |  31
 3 | 15 |   7 |  32
 1 | 16 |     |  35
 4 | 17 |   8 |  36
 0 | 18 |     |  40
 2 | 19 |   9 |  40

Поскольку тут остающееся после переноса конкретного файла свободное место влияет на возможность переноса следующего, без рекурсии обойтись будет слишком уж сложно. Поэтому сразу соберем две «карты» сегментов с парами позиций начала/конца: для заполненных файлами и для свободных (сразу укажем MATERIALIZED, чтобы не наступить на те же грабли): 

, seg AS MATERIALIZED (
  SELECT
    array_agg(ARRAY[pos, pos + sz]::integer[] ORDER BY n DESC)
      FILTER(WHERE fid IS NOT NULL) segfile -- карта файлов
  , array_agg(ARRAY[pos, pos + sz]::integer[] ORDER BY n)
      FILTER(WHERE fid IS NULL) segfree     -- карта свободных сегментов
  FROM
    map
)
segfile : {{40,42},{36,40},{32,35},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
segfree : {{2,5},{8,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}

Теперь самое сложное — на каждом шаге рекурсии найти переносимый файл, последовательно «примеряя» его к каждому «свободному» сегменту: 

, r AS (
  SELECT
    1 i
  , *
  FROM
    seg
UNION ALL
  SELECT
    i + 1
  , coalesce(T.segfile, r.segfile) -- если нашли возможный перенос для файла - используем его ...
  , coalesce(T.segfree, r.segfree) -- ... если нет - сохраняем прежние состояния
  FROM
    r
  LEFT JOIN
    LATERAL (
      SELECT -- реконструкция массивов-карт с учетом переноса
        segfile[:i - 1]
        || ARRAY[segfree[j][1], segfree[j][1] + segfile[i][2] - segfile[i][1]]
        || segfile[i + 1:] segfile
      , segfree[:j - 1]
        || ARRAY[segfree[j][1] + segfile[i][2] - segfile[i][1], segfree[j][2]]
        || segfree[j + 1:] segfree
      FROM
        generate_subscripts(segfree, 1) j -- перебор свободных сегментов
      WHERE
        segfree[j][1] < segfile[i][1] AND -- проверка возможности переноса
        segfree[j][2] - segfree[j][1] >= segfile[i][2] - segfile[i][1]
      LIMIT 1 -- ищем до первой возможности
    ) T
      ON TRUE
  WHERE
    i <= array_length(r.segfile, 1) -- ограничиваемся количеством файлов
)
 i | segfile/segfree
 1 | {{40,42},{36,40},{32,35},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
     {{2,5},{8,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 2 | {{2,4},{36,40},{32,35},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{8,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 3 | {{2,4},{36,40},{32,35},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{8,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 4 | {{2,4},{36,40},{8,11},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{11,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 5 | {{2,4},{36,40},{8,11},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{11,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 6 | {{2,4},{36,40},{8,11},{27,31},{22,26},{19,21},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{11,11},{12,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 7 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 8 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{11,12},{5,8},{0,2}}
     {{4,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
 9 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{4,5},{5,8},{0,2}}
     {{5,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
10 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{4,5},{5,8},{0,2}}
     {{5,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}
11 | {{2,4},{36,40},{8,11},{27,31},{22,26},{12,14},{15,18},{4,5},{5,8},{0,2}}
     {{5,5},{11,11},{14,15},{18,19},{21,22},{26,27},{31,32},{35,36},{40,40}}

Собственно, на последнем шаге мы и получаем целевое расположение файлов, которые необходимо пронумеровать в обратном порядке и пронумеровать каждый его сегмент: 

SELECT
  sum(fid * i) -- контрольная сумма
FROM
  (
    SELECT
      segfile -- состояние после последнего переноса
    FROM
      r
    ORDER BY
      i DESC
    LIMIT 1
  ) T
, array_length(segfile, 1) files -- общее количество файлов
, generate_series(
    files - 1
  , 0
  , -1
  ) fid -- нумерация файлов в обратном порядке
, generate_series(
    segfile[files - fid][1]
  , segfile[files - fid][2] - 1
  ) i; -- нумерация блоков внутри файла

Итоговый запрос принимает следующий вид: 

WITH RECURSIVE map AS (
  SELECT
    sz::integer -- размер сегмента
  , n           -- порядковый номер сегмента
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid     -- ID файла
  , sum(sz::bigint) OVER(ORDER BY n) - sz::bigint pos -- позиция начала сегмента
  FROM
    regexp_split_to_table( -- разбиение в таблицу ...
      '2333133121414131402'
    , ''                   -- ... по отдельным символам
    )
      WITH ORDINALITY T(sz, n)
)
, seg AS MATERIALIZED (
  SELECT
    array_agg(ARRAY[pos, pos + sz]::integer[] ORDER BY n DESC)
      FILTER(WHERE fid IS NOT NULL) segfile -- карта файлов
  , array_agg(ARRAY[pos, pos + sz]::integer[] ORDER BY n)
      FILTER(WHERE fid IS NULL) segfree     -- карта свободных сегментов
  FROM
    map
)
, r AS (
  SELECT
    1 i
  , *
  FROM
    seg
UNION ALL
  SELECT
    i + 1
  , coalesce(T.segfile, r.segfile) -- если нашли возможный перенос для файла - используем его ...
  , coalesce(T.segfree, r.segfree) -- ... если нет - сохраняем прежние состояния
  FROM
    r
  LEFT JOIN
    LATERAL (
      SELECT -- реконструкция массивов-карт с учетом переноса
        segfile[:i - 1]
        || ARRAY[segfree[j][1], segfree[j][1] + segfile[i][2] - segfile[i][1]]
        || segfile[i + 1:] segfile
      , segfree[:j - 1]
        || ARRAY[segfree[j][1] + segfile[i][2] - segfile[i][1], segfree[j][2]]
        || segfree[j + 1:] segfree
      FROM
        generate_subscripts(segfree, 1) j -- перебор свободных сегментов
      WHERE
        segfree[j][1] < segfile[i][1] AND -- проверка возможности переноса
        segfree[j][2] - segfree[j][1] >= segfile[i][2] - segfile[i][1]
      LIMIT 1 -- ищем до первой возможности
    ) T
      ON TRUE
  WHERE
    i <= array_length(r.segfile, 1) -- ограничиваемся количеством файлов
)
SELECT
  sum(fid * i) -- контрольная сумма
FROM
  (
    SELECT
      segfile -- состояние после последнего переноса
    FROM
      r
    ORDER BY
      i DESC
    LIMIT 1
  ) T
, array_length(segfile, 1) files -- общее количество файлов
, generate_series(
    files - 1
  , 0
  , -1
  ) fid -- нумерация файлов в обратном порядке
, generate_series(
    segfile[files - fid][1]
  , segfile[files - fid][2] - 1
  ) i; -- нумерация блоков внутри файла

Логично, что в этот раз вычисления заняли побольше времени — порядка 22.5 секунд, а 90% времени — поиски подходящего для переноса сегмента:

2659a49aae9c9c9ab08c9ca83dd566e0.png

Этот момент, конечно, тоже можно оптимизировать, раскладывая свободные сегменты «на кучки» по длине, и сразу вместо перебора брать первый из сегментов длины не меньше необходимой. Но на SQL этот вариант не дает существенной оптимизации из-за слишком больших накладных расходов из-за «протаскивания» большого количества записей с массивами сквозь рекурсию.

© Habrahabr.ru