EXPLAIN EXTENDED

Answering questions asked on the site.

Greg asks:

I have two tables, tasks and resources.

Tasks contains cost of each task: first requires 5 people to complete, second requires 3 people etc.

Resources is just a list of people.

How do I assign people to tasks?

This is in MySQL.

Thanks for a nice question, Greg.

Unfortunately, you haven’t sent your table structure, so I will have to make it up.

Let’s create the tables:

Table creation details

CREATE TABLE tasks (
        id INT NOT NULL PRIMARY KEY,
        cost INT NOT NULL,
        value VARCHAR(50) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=UTF8;

CREATE TABLE resources (
        id INT NOT NULL PRIMARY KEY,
        name VARCHAR(50) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=UTF8;

DELIMITER $$

CREATE PROCEDURE prc_filler(cnt INT)
BEGIN
        DECLARE _cnt INT;
        SET _cnt = 1;
        WHILE _cnt <= cnt DO
                INSERT
                INTO    filler
                SELECT  _cnt;
                SET _cnt = _cnt + 1;
        END WHILE;
END
$$

DELIMITER ;

START TRANSACTION;
CALL prc_filler(10000);
COMMIT;

INSERT
INTO    tasks
SELECT  id * 13, FLOOR(RAND(20090504) * 9) + 1, CONCAT('Task ', id * 13)
FROM    filler
LIMIT 100;

INSERT
INTO    resources
SELECT  id * 17, CONCAT('Employee ', id * 17)
FROM    filler;

I created 100 tasks with random costs from 1 to 10, and 10000 people. This should be enough for any real-world task management system.

I also made the id‘s in tasks and resources sparse to avoid confusion.

Now, we have a set of tasks ordered by some criteria (priority, probably), and a set of people ordered by some other criteria. And we need to assign people to tasks.

It will probably be best to use a queue like algorithm: first bunch of people from the list go to the first task, the next bunch to the second task, etc.

What we need is to assign the queue number to the list of resource’s, and then calculate which resource goes to which task.

To assign the queue number to people we will use an incrementing session variable:

SELECT  r.*,
        @s := @s + 1 AS res
FROM    (
        SELECT  @s := 0
        ) vars,
        resources r

Column res in the query above shows the position in the queue.

To select what number in the queue goes to what task, we will also use the session variables, but will increment them by cost, and not by one:

SELECT  t.*,
        @r AS s_res,
        (@r := @r + cost) - 1 AS e_res
FROM    (
        SELECT  @r := 1
        ) vars,
        tasks t

Task 13, which goes first in the task list, requires 9 people, that’s why people with queue numbers from 1 to 9 go to this task. Task 26, which goes second, requires 6 people, and the next bunch (from 10 to 15) goes to this task. Et cetera.

In the query above, we got the starting and ending queue position for each task.

Now, we just need to join the tables so that the queue position for each resource goes between the starting and ending positions for each task:

SELECT  *
FROM    (
        SELECT  t.*,
                @r AS s_res,
                (@r := @r + cost) - 1 AS e_res
        FROM    (
                SELECT  @r := 1
                ) vars,
                tasks t
        ) tq
LEFT JOIN
        (
        SELECT  r.*,
                @s := @s + 1 AS res
        FROM    (
                SELECT  @s := 0
                ) vars,
                resources r
        ) rq
ON      rq.res BETWEEN tq.s_res AND tq.e_res

The first task got 9 people, the second one got 6 people, etc.

This is quite a universal decision: you can put anything you like into the subqueries.

You can use your own ordering schemas by adding ORDER BY into the subqueries above, add arbitrary WHERE conditions to filter the tasks or people, etc.

Hope that helps.

Ask me a question