## Classroom scheduling

### from the Artful Common Queries page

 You have n student classes of known size, and m classrooms of known size, where m>=n. What's the best algorithm for assigning as many classes as possible to rooms of adequate size? 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 40 ``` Can 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 2017