Статьи

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

Сентябрь 10, 2017

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

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

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

Эта проблема

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


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

И…


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и разрешить только те суммы, которые могут появляться в этом конкретном порядке. То есть:


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. Мы видели это раньше в этом блоге, это называется промежуточной суммой , и ее лучше всего вычислять с помощью оконных функций следующим образом:


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, 19800, и 27511ближайшее значение SUBSET_SUM. В некотором смысле, мы пытаемся минимизировать выражение ABS(SUBSET_SUM - ASSIGN_AMT).

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

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


-- 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меньше или равна всем другим возможным различиям.

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


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

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

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


        UNION ALL SELECT 4 , 0     FROM DUAL

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


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

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


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 (пока), который сообщит об ошибке:


ORA-01796: this operator cannot be used with lists

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

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

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


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

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

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


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

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

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


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

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


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 ROWin SUMS, упорядоченные по обычным критериям. Нам нужно LATERAL(или APPLY), потому что это позволяет нам ссылаться на столбцы с левой стороны от JOINвыражения также в правой части , которая не была бы возможно в противном случае.

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

Боковой может быть очень полезен, когда правая сторона a JOINзависит от левой стороны. В отличие от обычных объединений, это означает, что 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генерирует рекурсию на основе a, SELECTкоторый выбирает из объявленной таблицы рекурсивно.

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


-- 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:


        SELECT 
            WORK_AMT, 
            ID
        FROM 
            WORK

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


        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значений база данных рассчитала:


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

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


    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
    ),

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


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

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


-- 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

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


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

Вывод

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

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

Тебе понравилась эта статья? Хотите узнать больше о продвинутом SQL? Свяжитесь с нами, чтобы узнать о наших продвинутых учебных курсах по SQL , где мы поможем вам понять простоту ориентированного на множество мышления и расчетов с помощью SQL.

Мы хотели бы отметить, что все эти решения могут быть написаны на Java с использованием jOOQ также безопасным способом.

41
Share: