Недавно я наткнулся на этот очень интересный вопрос о переполнении стека. Его название:
В этой статье мы сравним императивный подход пользователя с чрезвычайно элегантным (Oracle) подходом SQL. Мы будем использовать любую комбинацию этих замечательных функций SQL:
- Оконные функции
- ПЕРВЫЕ и ПОСЛЕДНИЕ функции с использованием специфичного для Oracle синтаксиса
-
LATERAL JOIN(илиAPPLY - Рекурсивный SQL
Эта проблема
Пользователь alhashmiya, который задал этот вопрос, искал решение проблемы поиска «ближайшей» суммы элементов в подмножестве чисел A для набора «ожидаемых» сумм B. Более конкретно, alhasmiya имела следующие два столы:
|
1
2
3
4
5
|
ID ASSIGN_AMT--------------1 251502 198003 27511 |
И…
|
01
02
03
04
05
06
07
08
09
10
11
12
|
ID WORK_AMT------------1 71202 81503 82554 90515 12206 125157 135558 52219 81210 6562 |
Значение ASSIGN_AMT является «ожидаемой» суммой. Алхашмия искала сумму подмножества значений WORK_AMT A, так что эта сумма максимально приближена к любой из «ожидаемых» сумм. Есть два способа понять эту проблему:
- Возможные «самые близкие» суммы ограничиваются суммами, полученными в строго определенном порядке, например, по порядку
ID. Применение этого понимания заключается в том, чтобы выяснить точный момент, когда четко определенный, упорядоченный промежуточный итог (например, остаток на банковском счете) превысил определенный порог - Возможные «ближайшие» суммы не ограничены. Любое неупорядоченное подмножество может рассчитать такую сумму. Применение этого понимания заключается в том, чтобы найти комбинацию дискретных значений, чтобы максимально приблизиться к целевому значению, например, для оптимизации сделки.
Второе понимание называется «проблемой суммы подмножеств» , для которой существуют только экспоненциальные алгоритмы, если вы ищете точное решение. Важно отметить, что этот алгоритм НЕ будет хорошо масштабироваться, независимо от метода решения!
Но давайте сначала посмотрим на более простое понимание:
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 337966 12515 463117 13555 598668 5221 650879 812 6589910 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_SUMFROM VALSORDER 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 examplesWITH 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 sumSELECT ASSIGN.ID, ASSIGN.ASSIGN_AMT, SUBSET_SUMFROM ASSIGNJOIN 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 235252 19800 235253 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 235252 19800 235252 19800 235253 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_SUMFROM ASSIGNJOIN 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_SUMFROM ASSIGNCROSS JOIN SUMSGROUP 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 235252 19800 235253 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_SUMFROM ASSIGNCROSS 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_SUMFROM ASSIGNCROSS 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:
Слайд взят из jOOQ Advanced SQL Training . Свяжитесь с нами, чтобы узнать больше .
В рекурсивном 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 dataWITH 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 beforeSELECT ASSIGN.ID, ASSIGN.ASSIGN_AMT, MIN (SUBSET_SUM) KEEP ( DENSE_RANK FIRST ORDER BY ABS (ASSIGN_AMT - SUBSET_SUM) ) AS CLOSEST_SUMFROM SUMSCROSS JOIN ASSIGNGROUP 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 251332 19800 197683 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 251502 19800 198003 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 dataWITH 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 beforeSELECT 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 CALCULATIONFROM SUMSCROSS JOIN ASSIGNGROUP BY ASSIGN.ID, ASSIGN.ASSIGN_AMT |
Вышеуказанное теперь дает:
|
1
2
3
4
5
|
ID ASSIGN_AMT CLOSEST_SUM CALCULATION------------------------------------------------------------1 25150 25150 7120 + 8150 + 9051 + 8122 19800 19800 1220 + 12515 + 5221 + 8123 27511 27511 8150 + 8255 + 9051 + 1220 + 812 |
Вывод
SQL мощный Чрезвычайно мощный. В этой статье мы использовали различные методы для вычисления проблемы суммы подмножеств или ее упрощения . Мы показали, как решить эту проблему в Oracle или PostgreSQL, используя комбинацию этих замечательных функций SQL:
- Оконные функции
-
KEEP FIRST(только в Oracle) -
LATERAL JOIN(илиAPPLY - Рекурсивный SQL
| Ссылка: | Как найти ближайшую сумму подмножества с помощью SQL от нашего партнера по JCG Лукаса Эдера в блоге JAVA, SQL и JOOQ . |