SQL HowTo: ускоряем запрос в 32 раза (Advent of Code 2025, Day 8: Playground) / Хабр

Осторожно, спойлеры! Не читайте, пока хотите решить задачу самостоятельно.

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

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

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

Advent of Code 2025, Day 8: Playground

--- День 8: Детская площадка ---

Обладая новыми знаниями в области обслуживания телепортов, вы уверенно ступаете на отремонтированную площадку телепорта.

Вы материализуетесь на незнакомой телепортационной площадке и оказываетесь в огромном подземном пространстве, где находится гигантская игровая площадка!

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

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

Эльфы пытаются выяснить, какие распределительные коробки нужно соединить, чтобы электричество дошло до каждой из них. У них даже есть спис��к всех положений распределительных коробок в трехмерном пространстве (ваш ввод в головоломку).

Например:

162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689

В этом списке указано расположение 20 распределительных коробок, по одной на каждую линию. Каждое положение указано в X,Y,Zкоординатах. Таким образом, первая распределительная коробка в списке находится по адресу X=162, Y=817, Z=812.

Чтобы сэкономить на гирляндах, эльфы хотели бы сосредоточиться на соединении пар распределительных коробок, расположенных как можно ближе друг к другу по прямой линии. В этом примере двумя наиболее близкими друг к другу распределительными коробками являются 162,817,812и 425,690,689.

Соединив эти две распределительные коробки вместе, поскольку между ними может протекать электрический ток, они становятся частью одной цепи. После их соединения образуется единая цепь, содержащая две распределительные коробки, а остальные 18 распределительных коробок остаются в своих собственных индивидуальных цепях.

Теперь две ближайшие друг к другу распределительные коробки, которые еще не соединены напрямую, это 162,817,812и 431,825,988. После их соединения, поскольку 162,817,812уже соединена с другой распределительной коробкой, остается одна цепь, содержащая три распределительные коробки, и еще 17 цепей, каждая из которых содержит одну распределительную коробку.

Следующие две распределительные коробки, которые необходимо соединить, это 906,360,560и 805,96,715. После их соединения получается цепь, содержащая 3 распределительные коробки, цепь, содержащая 2 распределительные коробки, и 15 цепей, каждая из которых содержит одну распределительную коробку.

Следующие две распределительные коробки — это 431,825,988и 425,690,689. Поскольку эти две распределительные коробки уже находились в одной цепи , ничего не происходит!

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

После выполнения десяти кратчайших соединений остается 11 цепей: одна цепь, содержащая 5 распределительных коробок, одна цепь, содержащая 4 распределительные коробки, две цепи, содержащие по 2 распределительные коробки каждая, и семь цепей, каждая из которых содержит одну распределительную коробку. Перемножив размеры трех самых больших цепей (5, 4 и одной из цепей размером 2), получаем 40.

В вашем списке много распределительных коробок; соедините вместе 1000 пар распределительных коробок, расположенных ближе всего друг к другу. После этого, что получится, если перемножить размеры трех самых больших цепей?

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

Эльфы были правы; у них определенно не хватает удлинительных кабелей. Вам придется соединять распределительные коробки между собой, пока все они не окажутся в одной большой цепи.

Продолжая приведенный выше пример, первое соединение, которое приводит к образованию единой цепи из всех распределительных коробок, находится между распределительными коробками в точках 216,146,977и 117,168,530. Эльфам необходимо знать, как далеко эти распределительные коробки находятся от стены, чтобы выбрать правильный удлинительный кабель; умножение координат X этих двух распределительных коробок ( 216и 117) дает 25272.

Продолжайте соединять ближайшие неподключенные пары распределительных коробок, пока все они не окажутся в одной цепи . Что получится, если перемножить координаты X последних двух распределительных коробок, которые нужно соединить?

Часть 1

Проще всего решить эту задачу аккуратным прямым моделированием - то есть просто перебрать те самые "1000 кратчайших" (или 10 в исходном примере) расстояний и посмотреть, какие цепи получатся в результате их соединения.

Сначала приведем в приемлемый вид исходные данные - преобразуем информацию о распределительных коробках в наборы их координат:

WITH RECURSIVE boxes AS(
  SELECT
    idb
  , line[1]::bigint x
  , line[2]::bigint y
  , line[3]::bigint z
  FROM
    regexp_matches($$
162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689
    $$, '(\d+),(\d+),(\d+)', 'g')
      WITH ORDINALITY T(line, idb)
)

Пронумеруем в порядке возрастания расстояния все пары соединительных коробок, для определенности принимая, что ID первой в каждой паре меньше ID второй, и оставим только первые 10 пар, которые нас и просят соединить:

, lines AS (
  SELECT
    row_number() OVER(
      ORDER BY sqrt(
        pow((s.x - d.x), 2) +
        pow((s.y - d.y), 2) +
        pow((s.z - d.z), 2)
      )
    ) idl -- нумерация по возрастанию расстояния
  , s.idb src
  , d.idb dst
  FROM
    boxes s
  JOIN
    boxes d
      ON s.idb < d.idb -- из (id1, id2) и (id2, id1) оставляем только первую
  ORDER BY
    idl
  LIMIT 10 -- оставляем только первые 10 самых коротких связей
)

idl | src | dst
  1 |   1 |  20
  2 |   1 |   8
  3 |   3 |  14
  4 |   8 |  20
  5 |  18 |  19
  6 |  10 |  13
  7 |  12 |  17
  8 |   3 |   9
  9 |  15 |  20
 10 |   3 |  19

Теперь нам надо связать между собой все эти линии. Но вместо того, чтобы пытаться "прицепить" каждую следующую к уже имеющимся, поступим наоборот - предположим, что у нас сначала есть все эт�� 10 отдельных линий, и попробуем найти среди них те, которые уже имеют точки пересечения.

Давайте сначала простроим алгоритм шага рекурсии на основе стартового состояния, а уже потом сделаем на его основе рекурсивную CTE.

Во-первых, нам понадобится "сохранить" внутри рекурсивного шага "вход", чтобы иметь возможность многократного обращения к нему:

, r AS (
  SELECT
    0 i
  , ARRAY[src, dst] chain -- стартовый шаг рекурсии - все линии как отдельные цепочки
  FROM
    lines
)
, T AS ( -- сохраняем "вход" рекурсии для многократного обращения
  TABLE r
)

Вторым шагом для каждой имеющейся цепочки соберем воедино все пересекающиеся с ней (понятно, что она сама тоже войдет в этот набор).

Заметим, что для пары пересекающихся цепочек объединенная будет сгенерирована дважды, поэтому оставим из них какую-то одну с помощью DISTINCT - ради этого мы их и упорядочивали при объединении:

, chains_pre AS (
  SELECT DISTINCT         -- оставляем по единственному экземпляру каждой цепочки
    T1.i + 1 i
  , ARRAY(                -- собираем сразу все пересекающиеся с текущей
      SELECT DISTINCT
        id
      FROM
        T T2
      , unnest(chain) id
      WHERE
        T2.chain && T1.chain
      ORDER BY
        1
    ) chain
  FROM
    T T1
)

i | chain
1 | {1,8,15,20}    -- {1,20} + {1,8} + {8,20} + {15,20}
1 | {1,8,20}       -- {1,8}  + {8,20}
1 | {3,9,14,18,19} -- {3,19} + {3,14} + {18,19} + {3,9}
1 | {3,9,14,19}    -- {3,14} + {3,9} + {3,19}
1 | {3,18,19}      -- {18,19} + {3,19}
1 | {10,13}
1 | {12,17}

Давайте оставим только те цепочки, которые не входят в какую-то из объединенных - то есть отсеются все, соединившиеся хоть с кем-то:

, chains_new AS (
  SELECT
    i
  , chain
  FROM
    chains_pre X
  WHERE
    NOT EXISTS(
      SELECT
        NULL
      FROM
        chains_pre Y
      WHERE
        X.chain <> Y.chain AND -- есть несовпадающая цепочка,
        X.chain <@ Y.chain     -- включающая эту
      LIMIT 1
    )
)

i | chain
1 | {1,8,15,20}
1 | {3,9,14,18,19}
1 | {10,13}
1 | {12,17}

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

, r AS (
  SELECT
    0 i
  , ARRAY[src, dst] chain -- стартовый шаг рекурсии - все линии как отдельные цепочки
  FROM
    lines
UNION ALL
  (
    WITH T AS ( -- сохраняем "вход" рекурсии для многократного обращения
      TABLE r
    )
    , chains_pre AS (
      SELECT DISTINCT         -- оставляем по единственному экземпляру каждой цепочки
        T1.i + 1 i
      , ARRAY(                -- собираем сразу все пересекающиеся с текущей
          SELECT DISTINCT
            id
          FROM
            T T2
          , unnest(chain) id
          WHERE
            T2.chain && T1.chain
          ORDER BY
            1
        ) chain
      FROM
        T T1
    )
    , chains_new AS (
      SELECT
        i
      , chain
      FROM
        chains_pre X
      WHERE
        NOT EXISTS(
          SELECT
            NULL
          FROM
            chains_pre Y
          WHERE
            X.chain <> Y.chain AND -- есть несовпадающая цепочка,
            X.chain <@ Y.chain     -- включающая эту
          LIMIT 1
        )
    )
    SELECT
      *
    FROM
      chains_new
    WHERE
      (SELECT count(*) FROM chains_new) < (SELECT count(*) FROM T) -- цепочки убывают
  )
)

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

i | chain
0 | {1,20}
0 | {1,8}
0 | {3,14}
0 | {8,20}
0 | {18,19}
0 | {10,13}
0 | {12,17}
0 | {3,9}
0 | {15,20}
0 | {3,19}
1 | {1,8,15,20}
1 | {3,9,14,18,19}
1 | {10,13}
1 | {12,17}

Остается лишь найти 3 самые длинные цепочки с последнего шага рекурсии и перемножить их длины:

SELECT
  exp(sum(ln(len)))::bigint -- произведение через сумму логарифмов
FROM
  (
    SELECT
      array_length(chain, 1) len
    FROM
      r
    WHERE
      i = (SELECT max(i) FROM r) -- последний шаг рекурсии
    ORDER BY
      len DESC                   -- самые длинные цепочки
    LIMIT 3
  ) T;

Итоговый запрос решает задачу примерно за пару секунд

WITH RECURSIVE boxes AS(
  SELECT
    idb
  , line[1]::bigint x
  , line[2]::bigint y
  , line[3]::bigint z
  FROM
    regexp_matches($$
162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689
    $$, '(\d+),(\d+),(\d+)', 'g')
      WITH ORDINALITY T(line, idb)
)
, lines AS (
  SELECT
    row_number() OVER(
      ORDER BY sqrt(
        pow((s.x - d.x), 2) +
        pow((s.y - d.y), 2) +
        pow((s.z - d.z), 2)
      )
    ) idl -- нумерация по возрастанию расстояния
  , s.idb src
  , d.idb dst
  FROM
    boxes s
  JOIN
    boxes d
      ON s.idb < d.idb -- из (id1, id2) и (id2, id1) оставляем только первую
  ORDER BY
    idl
  LIMIT 10 -- оставляем только первые 10 самых коротких связей
)
, r AS (
  SELECT
    0 i
  , ARRAY[src, dst] chain -- стартовый шаг рекурсии - все линии как отдельные цепочки
  FROM
    lines
UNION ALL
  (
    WITH T AS ( -- сохраняем "вход" рекурсии для многократного обращения
      TABLE r
    )
    , chains_pre AS (
      SELECT DISTINCT         -- оставляем по единственному экземпляру каждой цепочки
        T1.i + 1 i
      , ARRAY(                -- собираем сразу все пересекающиеся с текущей
          SELECT DISTINCT
            id
          FROM
            T T2
          , unnest(chain) id
          WHERE
            T2.chain && T1.chain
          ORDER BY
            1
        ) chain
      FROM
        T T1
    )
    , chains_new AS (
      SELECT
        i
      , chain
      FROM
        chains_pre X
      WHERE
        NOT EXISTS(
          SELECT
            NULL
          FROM
            chains_pre Y
          WHERE
            X.chain <> Y.chain AND -- есть несовпадающая цепочка,
            X.chain <@ Y.chain     -- включающая эту
          LIMIT 1
        )
    )
    SELECT
      *
    FROM
      chains_new
    WHERE
      (SELECT count(*) FROM chains_new) < (SELECT count(*) FROM T) -- цепочки убывают
  )
)
SELECT
  exp(sum(ln(len)))::bigint -- произведение через сумму логарифмов
FROM
  (
    SELECT
      array_length(chain, 1) len
    FROM
      r
    WHERE
      i = (SELECT max(i) FROM r) -- последний шаг рекурсии
    ORDER BY
      len DESC                   -- самые длинные цепочки
    LIMIT 3
  ) T;

Часть 2

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

Сначала немного изменим хранение "ближайших" линий - сразу сделаем из них "цепочки":

, lines AS (
  SELECT
    row_number() OVER(
      ORDER BY sqrt(
        pow((s.x - d.x), 2) +
        pow((s.y - d.y), 2) +
        pow((s.z - d.z), 2)
      )
    ) idl -- нумерация по возрастанию расстояния
  , ARRAY[s.idb, d.idb] line -- сразу цепочка из пары ближайших коробок
  FROM
    boxes s
  JOIN
    boxes d
      ON s.idb < d.idb -- из (id1, id2) и (id2, id1) оставляем только первую
  ORDER BY
    idl
)

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

На каждом шаге у нас происходит следующее:

сохраняются все цепочки, которые не имеют с добавляемой ничего общего
добавляется сама входящая цепочка, если она не сцепляется ни с кем из существующих
а если с кем-то зацепление возникает - объединяем их все "в одну кучу"
когда первая (и тогда уже единственная) цепочка включает все коробки - пора останавливаться

Вот так это выглядит на SQL:

, r AS (
  SELECT
    0 i
  , '{}'::text[] chains -- стартовый шаг рекурсии - пустой набор цепочек
UNION ALL
  SELECT
    i + 1
  , T.chains
  FROM
    r
  JOIN
    lines
      ON idl = i + 1
  , LATERAL (
      WITH chains AS ( -- восстанавливаем список цепочек из массива строк
        SELECT
          string_to_array(chain, ',')::bigint[] chain
        FROM
          unnest(chains) chain
      )
      , chk AS ( -- есть ли среди существующих цепочек пересекающаяся с добавляемой?
        SELECT
          EXISTS(
            SELECT
              NULL
            FROM
              chains
            WHERE
              chain && line
            LIMIT 1
          )
      )
      SELECT
        array_agg(array_to_string(chain, ',')) chains -- преобразуем список цепочек в массив строк
      FROM
        (
          SELECT
            chain           -- все непересекающиеся с добавляемой цепочки
          FROM
            chains
          WHERE
            NOT(chain && line)
        UNION ALL
          SELECT
            line chain      -- входящая цепочка, ...
          WHERE
            NOT (TABLE chk) -- ... если она ни с кем не сцепляется
        UNION ALL
          SELECT
            ARRAY(          -- объединенная цепочка, ...
              SELECT DISTINCT
                id
              FROM
                chains
              , unnest(chain || line) id
              WHERE
                chain && line
              ORDER BY
                id
            )
          WHERE
            (TABLE chk)     -- ... когда есть с кем зацепиться
       ) T
    ) T
  WHERE
    array_length(r.chains, 1) IS NULL OR -- стартовый шаг
    array_length(string_to_array(r.chains[1], ','), 1) < (SELECT count(*) FROM boxes) -- пока не соединились все коробки
)

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

 i | line    | chains
 1 | {1,20}  | {"1,20"}
 2 | {1,8}   | {"1,8,20"}
 3 | {3,14}  | {"1,8,20"
               ,"3,14"}
 4 | {8,20}  | {"3,14"
               ,"1,8,20"}
 5 | {18,19} | {"3,14"
               ,"1,8,20"
               ,"18,19"}
 6 | {10,13} | {"3,14"
               ,"1,8,20"
               ,"18,19"
               ,"10,13"}
 7 | {12,17} | {"3,14"
               ,"1,8,20"
               ,"18,19"
               ,"10,13"
               ,"12,17"}
 8 | {3,9}   | {"1,8,20"
               ,"18,19"
               ,"10,13"
               ,"12,17"
               ,"3,9,14"}
 9 | {15,20} | {"18,19"
               ,"10,13"
               ,"12,17"
               ,"3,9,14"
               ,"1,8,15,20"}
10 | {3,19}  | {"10,13"
               ,"12,17"
               ,"1,8,15,20"
               ,"3,9,14,18,19"}
11 | {4,20}  | {"10,13"
               ,"12,17"
               ,"3,9,14,18,19"
               ,"1,4,8,15,20"}
12 | {5,7}   | {"10,13"
               ,"12,17"
               ,"3,9,14,18,19"
               ,"1,4,8,15,20"
               ,"5,7"}
13 | {5,13}  | {"12,17"
               ,"3,9,14,18,19"
               ,"1,4,8,15,20"
               ,"5,7,10,13"}
14 | {5,6}   | {"12,17"
               ,"3,9,14,18,19"
               ,"1,4,8,15,20"
               ,"5,6,7,10,13"}
15 | {7,18}  | {"12,17"
               ,"1,4,8,15,20"
               ,"3,5,6,7,9,10,13,14,18,19"}
16 | {4,8}   | {"12,17"
               ,"3,5,6,7,9,10,13,14,18,19"
               ,"1,4,8,15,20"}
17 | {9,20}  | {"12,17"
               ,"1,3,4,5,6,7,8,9,10,13,14,15,18,19,20"}
18 | {1,10}  | {"12,17"
               ,"1,3,4,5,6,7,8,9,10,13,14,15,18,19,20"}
19 | {12,16} | {"1,3,4,5,6,7,8,9,10,13,14,15,18,19,20"
               ,"12,16,17"}
20 | {14,19} | {"12,16,17"
               ,"1,3,4,5,6,7,8,9,10,13,14,15,18,19,20"}
21 | {6,9}   | {"12,16,17"
               ,"1,3,4,5,6,7,8,9,10,13,14,15,18,19,20"}
22 | {1,15}  | {"12,16,17"
               ,"1,3,4,5,6,7,8,9,10,13,14,15,18,19,20"}
23 | {9,17}  | {"1,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20"}
24 | {2,6}   | {"1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20"}
25 | {10,20} | {"1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20"}
26 | {6,15}  | {"1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20"}
27 | {9,16}  | {"1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20"}
28 | {16,17} | {"1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20"}
29 | {11,13} | {"1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20"}

Остается лишь перемножить X-координаты входящих в последнюю добавленную линию коробок:

SELECT
  exp(sum(ln(x)))::bigint
FROM
  boxes
WHERE
  idb = ANY((
    SELECT
      line
    FROM
      lines
    WHERE
      idl = (SELECT max(i) FROM r)
  )::bigint[]);

Итоговый запрос

WITH RECURSIVE boxes AS(
  SELECT
    idb
  , line[1]::bigint x
  , line[2]::bigint y
  , line[3]::bigint z
  FROM
    regexp_matches($$
162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689
    $$, '(\d+),(\d+),(\d+)', 'g')
      WITH ORDINALITY T(line, idb)
)
, lines AS (
  SELECT
    row_number() OVER(
      ORDER BY sqrt(
        pow((s.x - d.x), 2) +
        pow((s.y - d.y), 2) +
        pow((s.z - d.z), 2)
      )
    ) idl -- нумерация по возрастанию расстояния
  , ARRAY[s.idb, d.idb] line
  FROM
    boxes s
  JOIN
    boxes d
      ON s.idb < d.idb -- из (id1, id2) и (id2, id1) оставляем только первую
  ORDER BY
    idl
)
, r AS (
  SELECT
    0 i
  , '{}'::text[] chains -- стартовый шаг рекурсии - пустой набор цепочек
UNION ALL
  SELECT
    i + 1
  , T.chains
  FROM
    r
  JOIN
    lines
      ON idl = i + 1
  , LATERAL (
      WITH chains AS ( -- восстанавливаем список цепочек из массива строк
        SELECT
          string_to_array(chain, ',')::bigint[] chain
        FROM
          unnest(chains) chain
      )
      , chk AS ( -- есть ли среди существующих цепочек пересекающаяся с добавляемой?
        SELECT
          EXISTS(
            SELECT
              NULL
            FROM
              chains
            WHERE
              chain && line
            LIMIT 1
          )
      )
      SELECT
        array_agg(array_to_string(chain, ',')) chains -- преобразуем список цепочек в массив строк
      FROM
        (
          SELECT
            chain           -- все непересекающиеся с добавляемой цепочки
          FROM
            chains
          WHERE
            NOT(chain && line)
        UNION ALL
          SELECT
            line chain      -- входящая цепочка, ...
          WHERE
            NOT (TABLE chk) -- ... если она ни с кем не сцепляется
        UNION ALL
          SELECT
            ARRAY(          -- объединенная цепочка, ...
              SELECT DISTINCT
                id
              FROM
                chains
              , unnest(chain || line) id
              WHERE
                chain && line
              ORDER BY
                id
            )
          WHERE
            (TABLE chk)     -- ... когда есть с кем зацепиться
       ) T
    ) T
  WHERE
    array_length(r.chains, 1) IS NULL OR -- стартовый шаг
    array_length(string_to_array(r.chains[1], ','), 1) < (SELECT count(*) FROM boxes) -- пока не соединились все коробки
)
SELECT
  exp(sum(ln(x)))::bigint
FROM
  boxes
WHERE
  idb = ANY((
    SELECT
      line
    FROM
      lines
    WHERE
      idl = (SELECT max(i) FROM r)
  )::bigint[]);

Bonus

Несложно заметить, в данном случае массу времени из почти 14 минут у нас занимают обращения к CTE lines и преобразование строк в массивы и обратно:

Давайте попробуем ускорить весь этот процесс - откажемся от пробегов по CTE и от преобразований в строки.

Массив вместо CTE

Заменим CTE на массив - для это необходимо внести правки всего в 3 местах:

, lines AS (
  SELECT
    array_agg(ARRAY[s.idb, d.idb]::text
      ORDER BY sqrt(
        pow((s.x - d.x), 2) +
        pow((s.y - d.y), 2) +
        pow((s.z - d.z), 2)
      )
    ) lines -- порядок по возрастанию расстояния
  FROM
    boxes s
  JOIN
    boxes d
      ON s.idb < d.idb -- из (id1, id2) и (id2, id1) оставляем только первую
)
...
  FROM
    r
  , LATERAL (
      SELECT
        lines[i + 1]::bigint[] line -- получаем i-ю линию
      FROM
        lines
    ) l
...
SELECT
  exp(sum(ln(x)))::bigint
FROM
  boxes
WHERE
  idb = ANY((
    SELECT
      lines[(SELECT max(i) FROM r)]
    FROM
      lines
  )::bigint[]);

Такая нехитрая замена сразу дает потрясающий эффект - ускорение в 15 раз!

Расширяем work_mem

Но почему у нас по-прежнему присутствует масса чтений временных файлов с диска? А потому что нам не хватило памяти на сортировку всех связей между каждой парой коробок (все-таки их почти 500K):

Sort Method: external merge  Disk: 40112kB

Нам понадобилось на сортировку ~40MB. Давайте увеличим эту память с запасом:

SET work_mem = '128MB';

И мы ускорили запрос еще в 2 раза!

Оптимизации с массивом и памятью

SET work_mem = '128MB';
-- explain (analyze, buffers, costs off)
WITH RECURSIVE boxes AS(
  SELECT
    idb
  , line[1]::bigint x
  , line[2]::bigint y
  , line[3]::bigint z
  FROM
    regexp_matches($$
162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689
    $$, '(\d+),(\d+),(\d+)', 'g')
      WITH ORDINALITY T(line, idb)
)
, lines AS (
  SELECT
    array_agg(ARRAY[s.idb, d.idb]::text
      ORDER BY sqrt(
        pow((s.x - d.x), 2) +
        pow((s.y - d.y), 2) +
        pow((s.z - d.z), 2)
      )
    ) lines -- порядок по возрастанию расстояния
  FROM
    boxes s
  JOIN
    boxes d
      ON s.idb < d.idb -- из (id1, id2) и (id2, id1) оставляем только первую
)
, r AS (
  SELECT
    0 i
  , '{}'::text[] chains -- стартовый шаг рекурсии - пустой набор цепочек
UNION ALL
  SELECT
    i + 1
  , T.chains
  FROM
    r
  , LATERAL (
      SELECT
        lines[i + 1]::bigint[] line -- получаем i-ю линию
      FROM
        lines
    ) l
  , LATERAL (
      WITH chains AS ( -- восстанавливаем список цепочек из массива строк
        SELECT
          string_to_array(chain, ',')::bigint[] chain
        FROM
          unnest(chains) chain
      )
      , chk AS ( -- есть ли среди существующих цепочек пересекающаяся с добавляемой?
        SELECT
          EXISTS(
            SELECT
              NULL
            FROM
              chains
            WHERE
              chain && line
            LIMIT 1
          )
      )
      SELECT
        array_agg(array_to_string(chain, ',')) chains -- преобразуем список цепочек в массив строк
      FROM
        (
          SELECT
            chain           -- все непересекающиеся с добавляемой цепочки
          FROM
            chains
          WHERE
            NOT(chain && line)
        UNION ALL
          SELECT
            line chain      -- входящая цепочка, ...
          WHERE
            NOT (TABLE chk) -- ... если она ни с кем не сцепляется
        UNION ALL
          SELECT
            ARRAY(          -- объединенная цепочка, ...
              SELECT DISTINCT
                id
              FROM
                chains
              , unnest(chain || line) id
              WHERE
                chain && line
              ORDER BY
                id
            )
          WHERE
            (TABLE chk)     -- ... когда есть с кем зацепиться
       ) T
    ) T
  WHERE
  i < 1 and
    array_length(r.chains, 1) IS NULL OR -- стартовый шаг
    array_length(string_to_array(r.chains[1], ','), 1) < (SELECT count(*) FROM boxes) -- пока не соединились все коробки
)
SELECT
  exp(sum(ln(x)))::bigint
FROM
  boxes
WHERE
  idb = ANY((
    SELECT
      lines[(SELECT max(i) FROM r)]
    FROM
      lines
  )::bigint[]);

Отказ от преобразований в текст

Осталось сделать последнее усилие - избавиться от постоянного преобразования на каждом шаге накопленных цепочек в текстовое представление и обратно. Для этого будем вместо элементов массива генерировать непосредственно строки самой CTE r.

Для этого нам всего лишь надо заменить процедуру формирования CTE chains и немного подкорректировать условие продолжения рекурсии:

, r AS (
  SELECT
    0 i
  , '{}'::bigint[] chain -- стартовый шаг рекурсии - все линии как отдельные цепочки
UNION ALL
  (
    WITH chains AS ( -- сохраняем входящий в шаг рекурсии набор цепочек
      TABLE r
    )
    SELECT
      i + 1
    , T.chain
    FROM
      (
        SELECT
          i
        , lines[i + 1]::bigint[] line      -- получаем i-ю линию как пару bigint
        FROM
          lines
        , (SELECT i FROM chains LIMIT 1) i -- извлекаем номер шага
      ) l
    , LATERAL (
        WITH chk AS ( -- есть ли среди существующих цепочек пересекающаяся с добавляемой?
          SELECT
            EXISTS(
              SELECT
                NULL
              FROM
                chains
              WHERE
                chain && line
              LIMIT 1
            )
        )
        SELECT
          *
        FROM
          (
            SELECT
              chain           -- все непересекающиеся с добавляемой цепочки
            FROM
              chains
            WHERE
              chain <> '{}' AND
              NOT(chain && line)
          UNION ALL
            SELECT
              line chain      -- входящая цепочка, ...
            WHERE
              NOT (TABLE chk) -- ... если она ни с кем не сцепляется
          UNION ALL
            SELECT
              ARRAY(          -- объединенная цепочка, ...
                SELECT DISTINCT
                  id
                FROM
                  chains
                , unnest(chain || line) id
                WHERE
                  chain && line
                ORDER BY
                  id
              )
            WHERE
              (TABLE chk)     -- ... когда есть с кем зацепиться
          ) T
        WHERE
          coalesce(array_length((SELECT chain FROM chains LIMIT 1), 1), 0) < (SELECT count(*) FROM boxes) -- пока не соединились все коробки
      ) T
  )
)

 i | chain
 0 | {}
 1 | {1,20}
 2 | {1,8,20}
 3 | {1,8,20}
 3 | {3,14}
 4 | {3,14}
 4 | {1,8,20}
 5 | {3,14}
 5 | {1,8,20}
 5 | {18,19}
 6 | {3,14}
 6 | {1,8,20}
 6 | {18,19}
 6 | {10,13}
 7 | {3,14}
 7 | {1,8,20}
 7 | {18,19}
 7 | {10,13}
 7 | {12,17}
 8 | {1,8,20}
 8 | {18,19}
 8 | {10,13}
 8 | {12,17}
 8 | {3,9,14}
 9 | {18,19}
 9 | {10,13}
 9 | {12,17}
 9 | {3,9,14}
 9 | {1,8,15,20}
10 | {10,13}
10 | {12,17}
10 | {1,8,15,20}
10 | {3,9,14,18,19}
11 | {10,13}
11 | {12,17}
11 | {3,9,14,18,19}
11 | {1,4,8,15,20}
12 | {10,13}
12 | {12,17}
12 | {3,9,14,18,19}
12 | {1,4,8,15,20}
12 | {5,7}
13 | {12,17}
13 | {3,9,14,18,19}
13 | {1,4,8,15,20}
13 | {5,7,10,13}
14 | {12,17}
14 | {3,9,14,18,19}
14 | {1,4,8,15,20}
14 | {5,6,7,10,13}
15 | {12,17}
15 | {1,4,8,15,20}
15 | {3,5,6,7,9,10,13,14,18,19}
16 | {12,17}
16 | {3,5,6,7,9,10,13,14,18,19}
16 | {1,4,8,15,20}
17 | {12,17}
17 | {1,3,4,5,6,7,8,9,10,13,14,15,18,19,20}
18 | {12,17}
18 | {1,3,4,5,6,7,8,9,10,13,14,15,18,19,20}
19 | {1,3,4,5,6,7,8,9,10,13,14,15,18,19,20}
19 | {12,16,17}
20 | {12,16,17}
20 | {1,3,4,5,6,7,8,9,10,13,14,15,18,19,20}
21 | {12,16,17}
21 | {1,3,4,5,6,7,8,9,10,13,14,15,18,19,20}
22 | {12,16,17}
22 | {1,3,4,5,6,7,8,9,10,13,14,15,18,19,20}
23 | {1,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20}
24 | {1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20}
25 | {1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20}
26 | {1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20}
27 | {1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20}
28 | {1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20}
29 | {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}

Теперь каждая запись представляет отдельную цепочку на соответствующем шаге рекурсивного соединения.

Эта модификация дает нам не настолько большое ускорение, как предыдущие, но еще почти 20% удается отыграть:

Итоговый запрос со всеми оптимизациями

SET work_mem = '128MB';

WITH RECURSIVE boxes AS(
  SELECT
    idb
  , line[1]::bigint x
  , line[2]::bigint y
  , line[3]::bigint z
  FROM
    regexp_matches($$
162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689
    $$, '(\d+),(\d+),(\d+)', 'g')
      WITH ORDINALITY T(line, idb)
)
, lines AS (
  SELECT
    array_agg(ARRAY[s.idb, d.idb]::text
      ORDER BY sqrt(
        pow((s.x - d.x), 2) +
        pow((s.y - d.y), 2) +
        pow((s.z - d.z), 2)
      )
    ) lines -- порядок по возрастанию расстояния
  FROM
    boxes s
  JOIN
    boxes d
      ON s.idb < d.idb -- из (id1, id2) и (id2, id1) оставляем только первую
)
, r AS (
  SELECT
    0 i
  , '{}'::bigint[] chain -- стартовый шаг рекурсии - все линии как отдельные цепочки
UNION ALL
  (
    WITH chains AS ( -- сохраняем входящий в шаг рекурсии набор цепочек
      TABLE r
    )
    SELECT
      i + 1
    , T.chain
    FROM
      (
        SELECT
          i
        , lines[i + 1]::bigint[] line      -- получаем i-ю линию как пару bigint
        FROM
          lines
        , (SELECT i FROM chains LIMIT 1) i -- извлекаем номер шага
      ) l
    , LATERAL (
        WITH chk AS ( -- есть ли среди существующих цепочек пересекающаяся с добавляемой?
          SELECT
            EXISTS(
              SELECT
                NULL
              FROM
                chains
              WHERE
                chain && line
              LIMIT 1
            )
        )
        SELECT
          *
        FROM
          (
            SELECT
              chain           -- все непересекающиеся с добавляемой цепочки
            FROM
              chains
            WHERE
              chain <> '{}' AND
              NOT(chain && line)
          UNION ALL
            SELECT
              line chain      -- входящая цепочка, ...
            WHERE
              NOT (TABLE chk) -- ... если она ни с кем не сцепляется
          UNION ALL
            SELECT
              ARRAY(          -- объединенная цепочка, ...
                SELECT DISTINCT
                  id
                FROM
                  chains
                , unnest(chain || line) id
                WHERE
                  chain && line
                ORDER BY
                  id
              )
            WHERE
              (TABLE chk)     -- ... когда есть с кем зацепиться
          ) T
        WHERE
          coalesce(array_length((SELECT chain FROM chains LIMIT 1), 1), 0) < (SELECT count(*) FROM boxes) -- пока не соединились все коробки
      ) T
  )
)
SELECT
  exp(sum(ln(x)))::bigint
FROM
  boxes
WHERE
  idb = ANY((
    SELECT
      lines[(SELECT max(i) FROM r)]
    FROM
      lines
  )::bigint[]);

В общем-то, у нас осталось последнее "слабое звено" - обращения к массиву lines из 500K элементов, которые... совсем небыстрые (4711 обращений заняли 17683.342ms, или 3.75ms на каждое!).

Но тут пора остановиться и идти готовить салатики. С наступающим Новым годом!

SQL HowTo: ускоряем запрос в 32 раза (Advent of Code 2025, Day 8: Playground)