## 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 modified for MySQL: ``` DROP TABLE IF EXISTS Rooms, Classes; CREATE TABLE Rooms(   room_nbr CHAR(2) NOT NULL PRIMARY KEY, room_size INTEGER NOT NULL ) ENGINE=MyISAM; CREATE TABLE Classes(   class_nbr CHAR(2) NOT NULL PRIMARY KEY, class_size INTEGER NOT NULL ) ENGINE=MyISAM; 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 2005 and 2008: ``` WITH    Matches AS (     SELECT        class_nbr, class_size, room_nbr, room_size,        exact_match = CASE WHEN class_size = room_size THEN 1 ELSE 0 END     FROM Classes, Rooms     WHERE class_size <= room_size   ),   Preferences AS (     SELECT       class_nbr, class_size,        class_room_pref = ROW_NUMBER() OVER (         PARTITION BY class_nbr ORDER BY exact_match, room_size, room_nbr       ),       room_nbr, room_size,        room_class_pref = ROW_NUMBER() OVER (         PARTITION BY room_nbr ORDER BY exact_match, class_size DESC, class_nbr       )     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,       final_pref = ROW_NUMBER() OVER (PARTITION BY class_nbr ORDER BY class_room_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; ``` It quickly 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 ``` As a MySQL user, you may be unfamiliar with two constructs in this query—` ROW_NUMBER() OVER ...[PARTITION]...`, and Common Table Expressions (CTEs) introduced by the keyword `WITH`. `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 SQL Server 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. Can this be done in MySQL? Yes, but not nearly so elegantly. 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?

Return to the Artful Common Queries page