Mysql – How to re-arrange rows to best fit within groups

MySQLselectsubqueryupdate

I categorized a table with the method introduced here to categorize my items to folders with a limit size of 100.

mixing_order  id     num_items  cat order_in_cat cumulative_sum folder
1             1      4          1   1            4              1
2             2      33         1   2            37             1
3             3      74         2   1            74             2
4             4      41         1   3            41             3
5             5      24         1   4            65             3
6             6      44         2   2            44             4
7             7      16         1   5            57             4
8             8      55         1   6            55             5
9             9      11         1   7            66             5
10            10     37         1   8            37             6

Now, I want to go further and re-arrange the rows to better fit within folders. Consider that the records are of two categories (indicated by column cat). We can make a better fit just by altering the order of mixing. Then, we can produce the following table as each folder has a cumulative_sum close to the folder size limit (i.e. 100 here). As you can see, the order in each category (order_in_cat) has not been changed, only the order that the rows from different categories are mixed.

mixing_order  id     num_items  cat  order_in_cat cumulative_sum folder
1             1      4          1    1            4              1
2             2      33         1    2            37             1
3             4      41         1    3            78             1
4             3      74         2    1            74             2
5             5      24         1    4            98             2
6             7      16         1    5            16             3
7             8      55         1    6            67             3
8             9      11         1    7            78             3
9             6      44         2    2            44             4
10            10     37         1    8            81             4

In other words, the mixing_order was random in order of INSERT, but now we want to re-arrange the mixing_order to best fit within folder.

Probably, we need a loop in which re-calculating SUM to find the best match out of possible choices, but I have no idea how to conduct such loop in SQL.

Best Answer

Here it the code from @DTest's Answer

SET @folder = 1;
SET @items = 0;
SELECT
    id, num_items,
    (SELECT IF(((@items:=@items+num_items)>100), @folder:=@folder+1, @folder)) as folder,
    IF(@items>100,@items:=0,@items) as checkItems
FROM foo;

Staring at this query, I would shudder to even think about writing of a Stored Procedure Technique for fitting items in folders. Then, it hit me ...

You could simply take the same query and ORDER BY num_items. That would actually pack as many items into a folder as possible before switching to another folder.

mysql> use ali
Database changed
mysql> CREATE TABLE foo (
    ->   id tinyint unsigned primary key AUTO_INCREMENT,
    ->   num_items tinyint unsigned
    -> );
Query OK, 0 rows affected (0.24 sec)

mysql>
mysql> INSERT INTO foo VALUES (1,4),(2,33),(3,74),(4,44),(5,24),(6,34),(7,46),(8,55),(9,11);
Query OK, 9 rows affected (0.17 sec)
Records: 9  Duplicates: 0  Warnings: 0

mysql> SET @folder = 1;
Query OK, 0 rows affected (0.03 sec)

mysql> SET @items = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT id, num_items, (SELECT IF(((@items:=@items+num_items)>100), 
    -> @folder:=@folder+1, @folder)) as folder,
    -> IF(@items>100,@items:=0,@items) as checkItems
    -> FROM foo ORDER BY num_items;
+----+-----------+--------+------------+
| id | num_items | folder | checkItems |
+----+-----------+--------+------------+
|  1 |         4 |      1 |          4 |
|  9 |        11 |      1 |         15 |
|  5 |        24 |      1 |         39 |
|  2 |        33 |      1 |         72 |
|  6 |        34 |      2 |          0 |
|  4 |        44 |      2 |         44 |
|  7 |        46 |      2 |         90 |
|  8 |        55 |      3 |          0 |
|  3 |        74 |      3 |         74 |
+----+-----------+--------+------------+
9 rows in set (0.08 sec)

mysql>

This packing would be somewhat lopsided in iterms of the number of entries per folder but the sum of the items per folder are pressed as close to 100 as possible.

Please note that if you want later folder with more items, simply change ORDER BY num_items to ORDER BY num_items DESC.

Give it a Try !!!

UPDATE 2013-01-09 12:52 EDT

What you need are three(3) mechanisms:

MECHANISM #1 : You need to imbed the query in a subquery
MECHANISM #2 : Order the subquery output by folder,num_items
MECHANISM #3 : Use a variable to monitor when you change folders from each row. When such a change occurs, you simply reset the folder counter to 1.

Here is the new code:

SET @order_val = 0;
SET @folder = 1;
SET @curr_folder = 1;
SET @items = 0;
SELECT *,
    @order_val:=IF(folder=@curr_folder,@order_val+1,1) ordervalue,
    @curr_folder:=folder current_folder
FROM
(
    SELECT * FROM
    (
        SELECT
            id, num_items,
            (SELECT IF(((@items:=@items+num_items)>100),
            @folder:=@folder+1, @folder)) as folder,
            IF(@items>100,@items:=0,@items) as checkItems
        FROM foo
    ) AA ORDER BY folder,num_items
) A;

Here is it execution:

mysql> SET @order_val = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> SET @folder = 1;
Query OK, 0 rows affected (0.00 sec)

mysql> SET @curr_folder = 1;
Query OK, 0 rows affected (0.00 sec)

mysql> SET @items = 0;
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT *,
    ->     @order_val:=IF(folder=@curr_folder,@order_val+1,1) ordervalue,
    ->     @curr_folder:=folder current_folder
    -> FROM
    -> (
    ->     SELECT * FROM
    ->     (
    ->         SELECT
    ->             id, num_items,
    ->             (SELECT IF(((@items:=@items+num_items)>100),
    ->             @folder:=@folder+1, @folder)) as folder,
    ->             IF(@items>100,@items:=0,@items) as checkItems
    ->         FROM foo
    ->     ) AA ORDER BY folder,num_items
    -> ) A;
+----+-----------+--------+------------+------------+----------------+
| id | num_items | folder | checkItems | ordervalue | current_folder |
+----+-----------+--------+------------+------------+----------------+
|  1 |         4 |      1 |          4 |          1 |              1 |
|  2 |        33 |      1 |         37 |          2 |              1 |
|  5 |        24 |      2 |         68 |          1 |              2 |
|  4 |        44 |      2 |         44 |          2 |              2 |
|  3 |        74 |      2 |          0 |          3 |              2 |
|  6 |        34 |      3 |          0 |          1 |              3 |
|  7 |        46 |      3 |         46 |          2 |              3 |
|  9 |        11 |      4 |         11 |          1 |              4 |
|  8 |        55 |      4 |          0 |          2 |              4 |
+----+-----------+--------+------------+------------+----------------+
9 rows in set (0.00 sec)

mysql>

Give it a Try !!!

Related Solutions

PostgreSQL – Selecting Rows with Repeated Data in a Timeframe

SELECT *
FROM   task t1
WHERE  EXISTS (
   SELECT 1
   FROM   task t2
   WHERE  t2.reference = t1.reference  -- same reference
   AND    t2.task_id  <> t1.task_id    -- different task_id (exclude self-join)
   AND    t2.end_date BETWEEN t1.end_date - 30
                      AND     t1.end_date + 30 
   )

An EXISTS semi-join should be the fastest way to arrive at DISTINCT rows, because you don't get duplicates to begin with. Also, in the event of multiple matching rows (many matching tasks withing 30 days) evaluation can stop after the first match is found. I would expect this query to beat anything you have so far. Test with EXPLAIN ANALYZE.

In a WHERE clause or JOIN condition don't use an expression like:

abs(t1.end_date - t2.end_date) < 30

If you can avoid it. As the left hand expression is derived from values of two tables, the only way for the query planner is to form a limited CROSS JOIN (after applying other conditions) and compute a value for every possible combination. This is a well known anti-pattern for good performance!

As long as there are only few rows per reference, it won't matter much. But the cost grows with O(N²) with more rows per reference. I rewrote the condition to:

t2.end_date BETWEEN t1.end_date - 30 AND t1.end_date + 30

In my tests, the first form went from 5x slower to 500x slower quickly when I narrowed down the id-space for reference (-> more matching rows).

The second form can also more easily use indexes. If you want to select a small sample of the table, with conditions like:

reference > 450
date_end > now()::date

And an index like:

CREATE INDEX test_idx ON task (reference, date_end);
CREATE INDEX test_idx2 ON task (date_end);

The performance gap becomes even more overwhelming.

Mysql – Search within same ID across several rows

This requirement is known as relational division. One popular approach is

SELECT sentence_id
FROM   YourTable
WHERE  meaning_id IN ( 12455, 15333 )
GROUP  BY sentence_id
HAVING COUNT(DISTINCT meaning_id) = 2

SQL Fiddle

If your table has a unique constraint on sentence_id,meaning_id you can drop the DISTINCT in the query above.

Best Answer

UPDATE 2013-01-09 12:52 EDT

Related Solutions

PostgreSQL – Selecting Rows with Repeated Data in a Timeframe

Mysql – Search within same ID across several rows

Related Question