SELECT rows WHERE next n rows satisfy CONDITIONS

Question

Let's say we have this resource availability table:

+-----------+-----------------------------------------------------------+
| date      | obvious, the date                                         |
| timeslot  | we have 12 fixed 2-hour timeslots so this will be 1 to 12 |
| r1        | number of resource type 1 available during this timeslot  |
| r2        | same, for resource type 2                                 |
| r3        | same, for resource type 3                                 |
+-----------+-----------------------------------------------------------+

Now, I want to see all the available timeslots I can use to do job #43. For this job I need 2 units of r1, one unit of r2, and three units of r3. Assuming the job will need one timeslot I can use this query:

SELECT `date`, `timeslot` FROM `resource_availability` 
WHERE
  `r1` > '1' AND
  `r2` > '0' AND
  `r3` > '2'
ORDER BY 'date`, `timeslot`;

However, if I have another job, job #86 which takes 3 timeslots to complete and could not be stopped-restarted, then is it possible to get safe start times with a query?

I am currently checking continuity in my while loop, but thought it might be possible to have the query do that.

If that is possible, I would like to know which is quicker and more efficient. For efficacy evaluation, it should be noted that this table, being a sort of bitmap gets updated quite frequently - i.e. with each job being scheduled the resource availability columns get updated.

Also, it is fairly obvious the purpose of this system is to allow examining what-ifs. If my approach is not optimal, what better alternatives there are?

Should the last question be one too many, please ignore it, or let me know in the comments and I'd delete it.

Answer 1

Whew... I put together an idea that may get you what you want. Forgive me if it takes a bit to understand, but I hope you see that it's actually a fairly straightforward solution to a moderately complex problem.

I would build the query (in PHP) to have n self-joins where n is the number of time slots needed for the job. The self-joins join the next consecutive timeslot, and the results are thinned based on resources being available in all the slots. Note that you could move the dynamically-created WHERE clauses into the JOIN conditions... I have seen versions of MySQL which will improve speed that way.

php code:

// $r1, $r3, and $r3 are the required resources for this job.

$join_format = 'JOIN timeslots AS %s ON %date = %s.date AND %s.timeslot+1 = %s.timeslot';
$where_format = '(%s.r1 >= '.$r1.' AND %s.r2 >= '.$r2.' AND %s.r3 >= '.$r3.')';

$joins = array();
$wheres = array("block1.date > CURDATE()",
                sprintf($where_format, "block1", "block1", "block1")
                );
$select_list = 'block1.date, block1.timeslot as starting_time, block' . $slots_needed . '.timeslot as ending_time';

for($block = 2; $block <= $slots_needed; $block++) {
  $join_alias = "block" . $block;
  $previous_alias = "block" . ($block-1);
  $joins[] = sprintf($join_format, $join_alias, $previous_alias,$join_alias, $previous_alias, $join_alias);
  $wheres[] = sprintf($where_format, $join_alias, $join_alias, $join_alias);
}

$query_format = 'SELECT %s FROM timeslots as block1 %s WHERE %s GROUP BY block1.date, block1.timeslot ORDER BY block1.date ASC, block1.timeslot ASC';
$joins_string = implode(' ', $joins);
$wheres_string = implode(' AND ', $wheres);
$query = sprintf($query_format, $select_list, $joins_string, $wheres_string);

To the best of my intention, that should yield a query like this (for 2 needed blocks with 1 each of the resources needed:

resultant SQL:

SELECT 
  block1.date,
  block1.timeslot as starting_time, 
  block2.timeslot as ending_time
FROM 
  timeslots AS block1
  JOIN timeslots AS block2
    ON block1.date = block2.date AND block1.timeslot+1 = block2.timeslot
WHERE
  block1.date > CURDATE()
  AND (block1.r1 >= 1 AND block1.r2 >= 1 AND block1.r3 >= 1)
  AND (block2.r1 >= 1 AND block2.r2 >= 1 AND block2.r3 >= 1)
GROUP BY
  block1.date, block1.timeslot
ORDER BY
  block1.date ASC, block1.timeslot ASC

and it should yield results such as:

expected result set:

+------------+---------------+-------------+
|    date    | starting_time | ending_time |
+------------+---------------+-------------+
| 2001-01-01 |       1       |      2      |
+------------+---------------+-------------+
| 2001-01-01 |       2       |      3      |
+------------+---------------+-------------+
| 2001-01-01 |       7       |      8      |
+------------+---------------+-------------+
| 2001-01-01 |       8       |      9      |
+------------+---------------+-------------+
| 2001-01-02 |       4       |      5      |
+------------+---------------+-------------+

Notice that if there are 2 blocks needed, but 3 available (consecutively), the query will return both options (the first and second OR the second and third available times).