It's a version of the combinatorial knapsack problem. It's known to be NP-complete, which means it's possible to verify any correct solution but there is no known algorithm for quickly finding a correct solution. How then to proceed?
Early in 2010 Joe Celko resurrected the problem in a Simple Talk column, and challenged readers to improve on SQL Server solutions he'd published in the third edition of his "SQL for Smarties". Here's his small version of the problem in MySQL syntax:
DROP TABLE IF EXISTS Rooms, Classes;
CREATE TABLE Rooms(
room_nbr CHAR(2) NOT NULL PRIMARY KEY,
room_size INTEGER NOT NULL
) ;
CREATE TABLE Classes(
class_nbr CHAR(2) NOT NULL PRIMARY KEY,
class_size INTEGER NOT NULL
);
INSERT INTO Classes
VALUES ('c1', 80),('c2', 70),('c3', 65),
('c4', 55),('c5', 50),('c6', 40);
INSERT INTO Rooms
VALUES ('r1', 70),('r2', 40),('r3', 50),
('r4', 85),('r5', 30),('r6', 65),('r7', 55);
And here is the best solution posted by his contributors. It works in SQL Server since 2005, MySQL since version 8.0.2, and MariaDB since 10.2.6:
WITH
Matches AS (
SELECT
class_nbr, class_size, room_nbr, room_size,
CASE WHEN class_size = room_size THEN 1
ELSE 0
END AS exact_match
FROM Classes
JOIN Rooms ON class_size <= room_size
),
Preferences AS (
SELECT
class_nbr, class_size,
ROW_NUMBER() OVER (
PARTITION BY class_nbr
ORDER BY exact_match, room_size, room_nbr
) AS class_room_pref,
room_nbr, room_size,
ROW_NUMBER() OVER (
PARTITION BY room_nbr
ORDER BY exact_match, class_size DESC, class_nbr
) AS room_class_pref
FROM Matches m
WHERE NOT EXISTS (
SELECT 1 FROM Matches
WHERE room_nbr = m.room_nbr
AND class_size > m.class_size
)
),
Final AS (
SELECT
class_nbr, class_size, room_nbr, room_size,
ROW_NUMBER() OVER (
PARTITION BY class_nbr
ORDER BY class_room_pref
) AS final_pref
FROM Preferences p
WHERE NOT EXISTS (
SELECT 1 FROM Preferences
WHERE room_nbr = p.room_nbr
AND class_room_pref = room_class_pref
AND room_class_pref < p.room_class_pref
)
)
SELECT c.class_nbr, c.class_size, f.room_nbr, f.room_size
FROM Classes c
LEFT JOIN Final f ON c.class_nbr=f.class_nbr AND f.final_pref=1
ORDER BY 1;
In MySQL 8.0.2 it immediately yields this correct answer:
class_nbr class_size room_nbr room_size c1 80 r4 85 c2 70 r1 70 c3 65 r6 65 c4 55 r7 55 c5 50 r3 50 c6 40 r2 40Can we do the job without CTEs and analytic functions, i.e., if we're using MySQL before 8.0.2, or MariaDB before 10.2.6? Yes, but not nearly so elegantly.
ROW_NUMBER() numbers resultset rows based on row values. This entry shows two MySQL equivalents for it, one relying on user variables, the other on aggregation. For this problem we will use the user variable method.
CTEs provide an elegant syntax for building derived tables. The above CTE/Analytic query builds the derived table Matches, from which it builds the derived table Preferences, from which it builds the table Final, which it joins with Classes for the final result.
Here we'll lay out an unoptimised step-by-step. Basically, we build the Matches, Preferences and Final tables, one at a time, then copy the final step of the SQL Server query. First the Matches table:
DROP TABLE IF EXISTS Matches;
CREATE TABLE Matches
SELECT
class_nbr, class_size, room_nbr, room_size,
IF(class_size=room_size,1,0) AS exact_match
FROM Classes
JOIN Rooms ON class_size <= room_size;
The Preferences table has two Row_Number() expressions to port, so we build each, then join them:
DROP TABLE IF EXISTS room_prefs;
SET @class_nbr_prev='', @ordPrev=0;
CREATE TABLE room_prefs
SELECT
ID, class_nbr, class_size, room_nbr,
room_size, class_room_pref
FROM (
SELECT
ID, class_size, room_nbr, room_size,
@ordPrev := IF( @class_nbr_prev=class_nbr,
@ordPrev+1, 1
) as class_room_pref,
@class_nbr_prev := class_nbr AS class_nbr
FROM Matches m
WHERE NOT EXISTS (
SELECT 1 FROM Matches
WHERE room_nbr = m.room_nbr
AND class_size > m.class_size
)
ORDER BY class_nbr, exact_match, room_size, room_nbr
) AS tmp ;
DROP TABLE IF EXISTS class_prefs;
SET @room_nbr_prev = '', @ordPrev=0;
CREATE TABLE class_prefs
SELECT ID, room_class_pref
FROM (
SELECT
ID,
@ordPrev := IF( @room_nbr_prev=room_nbr,
@ordPrev+1, 1
) as room_class_pref,
@room_nbr_prev := room_nbr AS room_nbr
FROM Matches m
WHERE NOT EXISTS (
SELECT 1 FROM Matches
WHERE room_nbr = m.room_nbr
AND class_size > m.class_size )
ORDER BY room_nbr, exact_match, class_size DESC, class_nbr
) AS tmp ;
DROP TABLE IF EXISTS Preferences;
CREATE TABLE Preferences
SELECT
a.class_nbr, a.class_size, a.room_nbr,
a.class_room_pref, a.room_size, b.room_class_pref
FROM room_prefs a
JOIN class_prefs b USING(ID);
Now build the Final table from Preferences:
DROP TABLE IF EXISTS Final;
SET @class_nbr_prev = '', @ordPrev=0;
CREATE TABLE Final
SELECT
room_nbr, room_size, class_size,
@ordPrev := IF( @class_nbr_prev=class_nbr,
@ordPrev+1, 1
) as final_pref,
@class_nbr_prev := class_nbr AS class_nbr
FROM Preferences p
WHERE NOT EXISTS (
SELECT 1 FROM Preferences
WHERE room_nbr = p.room_nbr
AND class_room_pref = room_class_pref
AND room_class_pref < p.room_class_pref
)
ORDER BY class_nbr;
The final step is identical to the last step in the SQL Server version:
SELECT c.class_nbr, c.class_size, f.room_nbr, f.room_size FROM Classes c LEFT JOIN Final f ON c.class_nbr = f.class_nbr AND f.final_pref = 1 ORDER BY 1; +-----------+------------+----------+-----------+ | class_nbr | class_size | room_nbr | room_size | +-----------+------------+----------+-----------+ | c1 | 80 | r4 | 85 | | c2 | 70 | r1 | 70 | | c3 | 65 | r6 | 65 | | c4 | 55 | r7 | 55 | | c5 | 50 | r3 | 50 | | c6 | 40 | r2 | 40 | +-----------+------------+----------+-----------+Looking for a juicy query optimisation problem?
Last updated 23 Jul 2024
