Статьи

Как найти ближайшую сумму подмножества с помощью SQL

Недавно я наткнулся на этот очень интересный вопрос о переполнении стека. Его название:

[Как] сравнить число с суммой подмножества чисел

В этой статье мы сравним императивный подход пользователя с чрезвычайно элегантным (Oracle) подходом SQL. Мы будем использовать любую комбинацию этих замечательных функций SQL:

Эта проблема

Пользователь alhashmiya, который задал этот вопрос, искал решение проблемы поиска «ближайшей» суммы элементов в подмножестве чисел A для набора «ожидаемых» сумм B. Более конкретно, alhasmiya имела следующие два столы:

1
2
3
4
5
ID  ASSIGN_AMT
--------------
1        25150
2        19800
3        27511

И…

01
02
03
04
05
06
07
08
09
10
11
12
ID  WORK_AMT
------------
1       7120
2       8150
3       8255
4       9051
5       1220
6      12515
7      13555
8       5221
9        812
10      6562

Значение ASSIGN_AMT является «ожидаемой» суммой. Алхашмия искала сумму подмножества значений WORK_AMT A, так что эта сумма максимально приближена к любой из «ожидаемых» сумм. Есть два способа понять эту проблему:

  1. Возможные «самые близкие» суммы ограничиваются суммами, полученными в строго определенном порядке, например, по порядку ID . Применение этого понимания заключается в том, чтобы выяснить точный момент, когда четко определенный, упорядоченный промежуточный итог (например, остаток на банковском счете) превысил определенный порог
  2. Возможные «ближайшие» суммы не ограничены. Любое неупорядоченное подмножество может рассчитать такую ​​сумму. Применение этого понимания заключается в том, чтобы найти комбинацию дискретных значений, чтобы максимально приблизиться к целевому значению, например, для оптимизации сделки.

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

Но давайте сначала посмотрим на более простое понимание:

1. Расчет суммы упорядоченного подмножества значений

Под строго упорядоченным мы подразумеваем (в смысле вопроса), что мы хотим упорядочить все значения WORK_AMT , например, по ID , и разрешить только те суммы, которые могут появляться в этом конкретном порядке. Т.е.

01
02
03
04
05
06
07
08
09
10
11
12
ID  WORK_AMT  SUBSET_SUM
------------------------
1       7120        7120 (= WORK_AMT)
2       8150       15270 (= previous SUBSET_SUM + WORK_AMT)     
3       8255       23525 (= previous SUBSET_SUM + WORK_AMT)
4       9051       32576 (= ...)
5       1220       33796
6      12515       46311
7      13555       59866
8       5221       65087
9        812       65899
10      6562       72461

Приведенное выше значение SUBSET_SUM является суммой всех значений WORK_AMT с ID <= "current" ID . Мы видели это раньше в этом блоге, это называется промежуточной суммой , и ее лучше всего вычислять с помощью оконных функций следующим образом:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
WITH
    VALS (ID, WORK_AMT) AS (
                  SELECT 1 , 7120  FROM DUAL
        UNION ALL SELECT 2 , 8150  FROM DUAL
        UNION ALL SELECT 3 , 8255  FROM DUAL
        UNION ALL SELECT 4 , 9051  FROM DUAL
        UNION ALL SELECT 5 , 1220  FROM DUAL
        UNION ALL SELECT 6 , 12515 FROM DUAL
        UNION ALL SELECT 7 , 13555 FROM DUAL
        UNION ALL SELECT 8 , 5221  FROM DUAL
        UNION ALL SELECT 9 , 812   FROM DUAL
        UNION ALL SELECT 10, 6562  FROM DUAL
    )
SELECT
    ID,
    WORK_AMT,
    SUM (WORK_AMT) OVER (ORDER BY ID) AS SUBSET_SUM
FROM
    VALS
ORDER BY
    ID

Вышеупомянутая оконная функция вычисляет сумму всех значений WORK_AMT которые находятся в «окне» значений, где ID меньше или равен текущему ID .

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

Теперь задача состоит в том, чтобы найти для каждого значения ASSIGN_AMT в 25150 , 27511 и 27511 самое близкое значение SUBSET_SUM . В некотором смысле, мы пытаемся минимизировать выражение ABS(SUBSET_SUM - ASSIGN_AMT) .

Однако агрегатная функция MIN() нам здесь не поможет, потому что она просто вернет минимальное значение этой разницы. Мы хотим, чтобы значение SUBSET_SUM эту разницу в первую очередь.

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
-- The common table expressions are the same as
-- in the previous examples
WITH
    ASSIGN(ID, ASSIGN_AMT) AS (
                  SELECT 1, 25150 FROM DUAL
        UNION ALL SELECT 2, 19800 FROM DUAL
        UNION ALL SELECT 3, 27511 FROM DUAL
    ),
    VALS (ID, WORK_AMT) AS (
                  SELECT 1 , 7120  FROM DUAL
        UNION ALL SELECT 2 , 8150  FROM DUAL
        UNION ALL SELECT 3 , 8255  FROM DUAL
        UNION ALL SELECT 4 , 9051  FROM DUAL
        UNION ALL SELECT 5 , 1220  FROM DUAL
        UNION ALL SELECT 6 , 12515 FROM DUAL
        UNION ALL SELECT 7 , 13555 FROM DUAL
        UNION ALL SELECT 8 , 5221  FROM DUAL
        UNION ALL SELECT 9 , 812   FROM DUAL
        UNION ALL SELECT 10, 6562  FROM DUAL
    ),
    SUMS (ID, WORK_AMT, SUBSET_SUM) AS (
        SELECT
            VALS.*,
            SUM (WORK_AMT) OVER (ORDER BY ID)
        FROM
            VALS
    )
 
-- This is now the interesting part, where we
-- calculate the closest sum
SELECT
    ASSIGN.ID,
    ASSIGN.ASSIGN_AMT,
    SUBSET_SUM
FROM
    ASSIGN
JOIN
    SUMS
ON
    ABS (ASSIGN_AMT - SUBSET_SUM) <= ALL (
        SELECT
            ABS (ASSIGN_AMT - SUBSET_SUM)
        FROM
            SUMS
)

Количественный предикат сравнения читается интуитивно. Мы ищем тот конкретный SUBSET_SUM чья разница с «ожидаемым» ASSIGN_AMT меньше или равна всем другим возможным различиям.

Вышеприведенный запрос дает:

1
2
3
4
5
ID  ASSIGN_AMT  SUBSET_SUM
--------------------------
1        25150       23525
2        19800       23525
3        27511       23525

В этом случае это всегда то же самое.

Возможно, вы заметили, что решение не совсем корректно в случае, когда ASSIGN_AMT разрешено быть равным нулю (давайте проигнорируем возможность отрицательных значений) — в случае чего мы создадим повторяющиеся значения в JOIN . Это может быть достигнуто при замене:

1
UNION ALL SELECT 4 , 0     FROM DUAL

Теперь результат:

1
2
3
4
5
6
ID  ASSIGN_AMT  SUBSET_SUM
--------------------------
1        25150       23525
2        19800       23525
2        19800       23525
3        27511       23525

Одним из решений является удаление этих дубликатов с помощью DISTINCT ( это анти-шаблон. См. № 6 в этом списке ). Лучшее решение состоит в том, чтобы сделать предикат JOIN однозначным, сравнивая также значения ID , то есть:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
SELECT
    ASSIGN.ID,
    ASSIGN.ASSIGN_AMT,
    SUBSET_SUM
FROM
    ASSIGN
JOIN
    SUMS
ON
    (ABS (ASSIGN_AMT - SUBSET_SUM), SUMS.ID) <= ALL (
        SELECT
            ABS (ASSIGN_AMT - SUBSET_SUM),
            ID
        FROM
            SUMS
)

Вышеописанное, к сожалению, не работает в Oracle (пока), который сообщит об ошибке:

1
ORA-01796: this operator cannot be used with lists

Oracle поддерживает сравнение выражений кортежей / значений строк только с равными компараторами , а не с компараторами меньше / больше, что является позором. Тот же запрос выполняется в PostgreSQL без сбоев.

Нахождение «ближайшей» из этих сумм с помощью функции Oracle FIRST

В Oracle есть очень интересная функция, позволяющая хранить первые (или последние) значения в наборе агрегатных значений группы при любом конкретном упорядочении и рассчитывать агрегатную функцию только для этих значений в группе. Следующий оператор SQL проиллюстрирует это:

01
02
03
04
05
06
07
08
09
10
11
12
13
SELECT
    ASSIGN.ID,
    ASSIGN.ASSIGN_AMT,
    MIN (SUBSET_SUM) KEEP (
        DENSE_RANK FIRST
        ORDER BY ABS (ASSIGN_AMT - SUBSET_SUM)
    ) AS CLOSEST_SUM
FROM
    ASSIGN
CROSS JOIN
    SUMS
GROUP BY
    ASSIGN.ID, ASSIGN.ASSIGN_AMT

По сути, мы группируем все значения из таблицы ASSIGN_AMT для каждого ASSIGN_AMT . Для каждой из этих групп мы будем искать "FIRST" строку, которая появляется при упорядочении строк в группе по нашим критериям ABS(ASSIGN_AMT - SUBSET_SUM) . Мы "KEEP" только те строки в группе и сохраняем из этих строк минимальный SUBSET_SUM .

Этот запрос снова даст:

1
2
3
4
5
ID  ASSIGN_AMT  SUBSET_SUM
--------------------------
1        25150       23525
2        19800       23525
3        27511       23525

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

Помните, что мы недавно видели похожую функцию в этом блоге, когда искали FIRST_VALUE (или LAST_VALUE ) в пределах PARTITION окна . В стандартном SQL аналогичная вещь может быть достигнута с помощью оконных функций как таковых:

01
02
03
04
05
06
07
08
09
10
11
SELECT DISTINCT
    ASSIGN.ID,
    ASSIGN.ASSIGN_AMT,
    FIRST_VALUE (SUBSET_SUM) OVER (
        PARTITION BY ASSIGN.ID
        ORDER BY ABS (ASSIGN_AMT - SUBSET_SUM)
    ) AS CLOSEST_SUM
FROM
    ASSIGN
CROSS JOIN
    SUMS

К сожалению, все эти решения создают дубликаты, которые мы должны удалить либо с помощью GROUP BY (решение KEEP ), либо с помощью DISTINCT (решение FIRST_VALUE ).

Нахождение «ближайшей» из этих сумм с LATERAL JOIN

Более чистое решение, которое не основано на удалении дубликатов, использует новое предложение Oracle 12c FETCH FIRST вместе с CROSS JOIN LATERAL (или CROSS APPLY , что то же самое)

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
SELECT
    ASSIGN.ID,
    ASSIGN.ASSIGN_AMT,
    CLOSEST_SUM
FROM
    ASSIGN
CROSS JOIN LATERAL (
    SELECT
        SUBSET_SUM AS CLOSEST_SUM
    FROM
        SUMS
    ORDER BY
        ABS (ASSIGN.ASSIGN_AMT - SUBSET_SUM)
    FETCH FIRST 1 ROW ONLY
) SUMS

Что это значит? По сути, мы объединяем для каждого значения в ASSIGN только FIRST 1 ROW в SUMS , упорядоченную по обычным критериям. Нам нужен LATERAL (или APPLY ), потому что это позволяет нам ссылаться на столбцы с левой стороны выражения JOIN также с правой стороны , что иначе было бы невозможно.

Та же функциональность поддерживается в SQL Server (только с использованием CROSS APPLY ) или в PostgreSQL (только с использованием CROSS JOIN LATERAL ).

Боковой может быть очень полезен, когда правая часть JOIN зависит от левой стороны. В отличие от обычных объединений, это означает, что порядок объединения будет установлен слева направо, а оптимизатор имеет сокращенный набор параметров алгоритма объединения. Это полезно в подобных примерах (с ORDER BY и FETCH FIRST ) или при присоединении к необъявленным табличным функциям, о которых мы расскажем в следующем сообщении в блоге.

2. Расчет суммы любого подмножества значений

До сих пор мы работали над упрощенной версией проблемы. Вероятно, это не то, что имел в виду alhashmiya в вопросе переполнения стека. Вероятно, они хотели решить проблему суммы подмножеств , найдя «ближайшую» сумму любого подмножества значений WORK_AMT .

Мы будем использовать рекурсивный SQL для вычисления всех возможных сумм. Прежде всего, давайте вспомним, как работает рекурсивный SQL:

В рекурсивном SQL нам нужен запрос UNION ALL в общем табличном выражении (предложение WITH в Oracle или предложение WITH RECURSIVE в PostgreSQL). Первый подзапрос UNION ALL генерирует «начальную строку (и)» рекурсии, а второй подзапрос UNION ALL генерирует рекурсию на основе SELECT который рекурсивно выбирает из объявленной таблицы.

Итак, наивное решение этой проблемы сумм подмножеств можно увидеть здесь:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
-- Repetition of the previous data
WITH
    ASSIGN (ID, ASSIGN_AMT) AS (
                  SELECT 1, 25150 FROM DUAL
        UNION ALL SELECT 2, 19800 FROM DUAL
        UNION ALL SELECT 3, 27511 FROM DUAL
    ),
    WORK (ID, WORK_AMT) AS (
                  SELECT 1 , 7120  FROM DUAL
        UNION ALL SELECT 2 , 8150  FROM DUAL
        UNION ALL SELECT 3 , 8255  FROM DUAL
        UNION ALL SELECT 4 , 9051  FROM DUAL
        UNION ALL SELECT 5 , 1220  FROM DUAL
        UNION ALL SELECT 6 , 12515 FROM DUAL
        UNION ALL SELECT 7 , 13555 FROM DUAL
        UNION ALL SELECT 8 , 5221  FROM DUAL
        UNION ALL SELECT 9 , 812   FROM DUAL
        UNION ALL SELECT 10, 6562  FROM DUAL
    ),
 
-- A new way of calculating all possible sums by
-- Recursively adding up all the sums
    SUMS (SUBSET_SUM, MAX_ID) AS (
        SELECT
            WORK_AMT,
            ID
        FROM
            WORK
         
        UNION ALL
         
        SELECT
            WORK_AMT + SUBSET_SUM,
            GREATEST (MAX_ID, WORK.ID)
        FROM
            SUMS
        JOIN
            WORK
        ON
            SUMS.MAX_ID < WORK.ID
    )
 
-- The same technique to match the "closest" sum
-- As before
SELECT
    ASSIGN.ID,
    ASSIGN.ASSIGN_AMT,
    MIN (SUBSET_SUM) KEEP (
        DENSE_RANK FIRST
        ORDER BY ABS (ASSIGN_AMT - SUBSET_SUM)
    ) AS CLOSEST_SUM
FROM
    SUMS
CROSS JOIN
    ASSIGN
GROUP BY
    ASSIGN.ID, ASSIGN.ASSIGN_AMT

Рекурсия проста. В первом подзапросе рекурсии («начальный ряд») мы выбираем каждый отдельный ряд в WORK :

1
2
3
4
5
SELECT
            WORK_AMT,
            ID
        FROM
            WORK

Во втором подзапросе рекурсии («строки отказов») мы объединяем значение предыдущего шага рекурсии ( SUMS ) со всеми оставшимися значениями ( WORK ), то есть со всеми значениями с более высоким ID :

1
2
3
4
5
6
7
8
9
SELECT
            WORK_AMT + SUBSET_SUM,
            GREATEST (MAX_ID, WORK.ID)
        FROM
            SUMS
        JOIN
            WORK
        ON
            SUMS.MAX_ID < WORK.ID

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

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

После все еще приемлемых 0,112 с для 10 различных значений WORK_AMT база данных рассчитала:

1
2
3
4
5
ID  ASSIGN_AMT  CLOSEST_SUM
---------------------------
1        25150        25133
2        19800        19768
3        27511        27488

Но будьте осторожны, как только вы начнете добавлять значения в таблицу VALS , этот алгоритм начнет взрываться во времени и в пространстве. Выполнение того же запроса со следующей, только чуть большей таблицей WORK уже требует 16,3 секунды, чтобы получить результат:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
WORK(ID, WORK_AMT) AS (
                  SELECT 1 , 7120  FROM DUAL
        UNION ALL SELECT 2 , 8150  FROM DUAL
        UNION ALL SELECT 3 , 8255  FROM DUAL
        UNION ALL SELECT 4 , 9051  FROM DUAL
        UNION ALL SELECT 5 , 1220  FROM DUAL
        UNION ALL SELECT 6 , 12515 FROM DUAL
        UNION ALL SELECT 7 , 13555 FROM DUAL
        UNION ALL SELECT 8 , 5221  FROM DUAL
        UNION ALL SELECT 9 , 812   FROM DUAL
        UNION ALL SELECT 10, 6562  FROM DUAL
        UNION ALL SELECT 11, 1234  FROM DUAL
        UNION ALL SELECT 12, 61    FROM DUAL
        UNION ALL SELECT 13, 616   FROM DUAL
        UNION ALL SELECT 14, 2456  FROM DUAL
        UNION ALL SELECT 15, 5161  FROM DUAL
        UNION ALL SELECT 16, 414   FROM DUAL
        UNION ALL SELECT 17, 516   FROM DUAL
        UNION ALL SELECT 18, 617   FROM DUAL
        UNION ALL SELECT 19, 146   FROM DUAL
    ),

И результат будет:

1
2
3
4
5
ID  ASSIGN_AMT  CLOSEST_SUM
---------------------------
1        25150        25150
2        19800        19800
3        27511        27511

Хотите доказательства о фактической сумме? Это также легко с рекурсивным SQL:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
-- Repetition of the previous data
WITH
    ASSIGN (ID, ASSIGN_AMT) AS (
                  SELECT 1, 25150 FROM DUAL
        UNION ALL SELECT 2, 19800 FROM DUAL
        UNION ALL SELECT 3, 27511 FROM DUAL
    ),
    WORK (ID, WORK_AMT) AS (
                  SELECT 1 , 7120  FROM DUAL
        UNION ALL SELECT 2 , 8150  FROM DUAL
        UNION ALL SELECT 3 , 8255  FROM DUAL
        UNION ALL SELECT 4 , 9051  FROM DUAL
        UNION ALL SELECT 5 , 1220  FROM DUAL
        UNION ALL SELECT 6 , 12515 FROM DUAL
        UNION ALL SELECT 7 , 13555 FROM DUAL
        UNION ALL SELECT 8 , 5221  FROM DUAL
        UNION ALL SELECT 9 , 812   FROM DUAL
        UNION ALL SELECT 10, 6562  FROM DUAL
    ),
 
-- A new way of calculating all possible sums by
-- Recursively adding up all the sums
    SUMS (SUBSET_SUM, MAX_ID, CALC) AS (
        SELECT
            WORK_AMT,
            ID,
            TO_CHAR(WORK_AMT)
        FROM WORK
         
        UNION ALL
         
        SELECT
            WORK_AMT + SUBSET_SUM,
            GREATEST (MAX_ID, WORK.ID),
            CALC || '+' || WORK_AMT
        FROM
            SUMS
        JOIN
            WORK
        ON
            SUMS.MAX_ID < WORK.ID
    )
 
-- The same technique to match the "closest" sum
-- As before
SELECT
    ASSIGN.ID,
    ASSIGN.ASSIGN_AMT,
    MIN (SUBSET_SUM) KEEP (
        DENSE_RANK FIRST
        ORDER BY ABS (ASSIGN_AMT - SUBSET_SUM)
    ) AS CLOSEST_SUM,
    MIN (CALC) KEEP (
        DENSE_RANK FIRST
        ORDER BY ABS (ASSIGN_AMT - SUBSET_SUM)
    ) AS CALCULATION
FROM
    SUMS
CROSS JOIN
    ASSIGN
GROUP BY
    ASSIGN.ID, ASSIGN.ASSIGN_AMT

Вышеуказанное теперь дает:

1
2
3
4
5
ID  ASSIGN_AMT  CLOSEST_SUM  CALCULATION
------------------------------------------------------------
1        25150        25150  7120 + 8150 + 9051 + 812
2        19800        19800  1220 + 12515 + 5221 + 812
3        27511        27511  8150 + 8255 + 9051 + 1220 + 812

Вывод

SQL мощный Чрезвычайно мощный. В этой статье мы использовали различные методы для вычисления проблемы суммы подмножеств или ее упрощения . Мы показали, как решить эту проблему в Oracle или PostgreSQL, используя комбинацию этих замечательных функций SQL:

  • Оконные функции
  • KEEP FIRST (только в Oracle)
  • LATERAL JOIN (или APPLY
  • Рекурсивный SQL