dive into mark

Suppose, for the sake of argument, that we have a series of tasks. Each of which has a begin date/time and an end date/time. Each task is run only once, and the results of the completed tasks are stored in a separate table along with various result data. Thus:

select * from task;

task_uid  begin_date               end_date
========= ======================== ========================
1         2003-04-04 00:30:00.000  2003-04-04 01:00:00.000
2         2003-04-04 00:45:00.000  2003-04-04 01:15:00.000
3         2003-04-04 01:00:00.000  2003-04-04 01:30:00.000
4         2003-04-05 10:00:00.000  2003-04-05 10:30:00.000

(4 row(s) affected)


select * from result;

result_uid  task_uid
=========-- =========
1           1

(1 row(s) affected)

(The result table also contains other data pertaining to the results of the completed task, but it’s irrelevant to our current assignment.)

As you will see in a minute, we will need to know what time it is. No two DBMSes have the same syntax for this; here we’ll be using Microsoft SQL Server 2000. Oracle weenies will select sysdate your ridiculous little dual table. Other DBMSes have a variety of maddeningly inconsistently named functions for the purpose.

It is currently 12:49 AM on April 4, 2003:

select current_timestamp;

========================
2003-04-04 00:49:23.597

(1 row(s) affected)

We are writing a scheduler, which needs to decide which tasks to run. The scheduler is run once a day. Tasks which have not been started, should be run now, along with all the other tasks whose starting date will come up before the scheduler is run again. Tasks that were never completed but whose end date has already passed, should not be run. (Yes, this means that some tasks may end up being skipped altogether, if the scheduler slips. For reasons known only to management, this is acceptable and even desired.)

Furthermore, we shall ignore the possibility of racing conditions, where a task is still “in progress” but not completed by the time the scheduler runs again. Tasks are assumed to run instantaneously. This assumption gives us the willies, and the dangers of said assumption have been brought up in numerous meetings and have been the subject of numerous CYA memos, but for now we are simply going to proceed without worrying about it.

However—and I am so incredibly not making this up—we are not allowed to assume that tasks set to begin in the future have not been completed. The only indication of whether a task has been completed or not is whether it is listed in the result table. This is affectionately known as the E-TWAP (Evan’s Time Warp Requirement).

Now, here’s our assignment: we need to find the first non-completed task that should have begun by now but hasn’t ended yet (i.e. the current time is between the task’s begin date and end date), plus all other non-completed tasks due to start within the next 24 hours of the first task.

This is a real-world example. I couldn’t possibly make up something this contrived.

First, let’s focus on figuring out the date of the first task we want to run. We can use the handy (but little-used) between keyword to find only tasks where the current time is between the begin_date and end_date, then use the min function on begin_date to find the earliest date among those tasks:

select min(t.begin_date) as first_date
from task t
where current_timestamp between t.begin_date and t.end_date
;

first_date
========================
2003-04-04 00:30:00.000

(1 row(s) affected)

Of course, this doesn’t take into account the tasks that have already completed. For that, we’ll need to add a where not exists clause and do a subquery on the result table:

select min(t.begin_date) as first_date
from task t
where not exists (
  select r.task_uid
  from result r
  where t.task_uid = r.task_uid
)
and current_timestamp between t.begin_date and t.end_date
;

first_date
========================
2003-04-04 00:45:00.000

(1 row(s) affected)

Now we‘re going to use this date to do calcuations against every other begin_date in the task table (to find all the tasks within the next 24 hours of this date). For this we use a CROSS JOIN. For larger result sets (more than one row), CROSS JOIN will give you what’s called a Cartesian Product: every row of the first table crossed with every row of the second table. And that’s technically what we’ll get here, but since the second table will only have one row and one column in it, it’s a trivial case: that value just kind of gets “tacked on” as an extra column to the first table.

(Note that we‘re going to take our previous SELECT statement, give it a name (m), and use it inline in a larger SELECT statement. This is called a derived table, and not all databases can do it. An alternative for those that can’t: turn the previous statement into a view and then CROSS JOIN with the view.)

select t.task_uid
, t.begin_date
, m.first_date
from task t
cross join (
  select min(t.begin_date) as first_date
  from task t
  where not exists (
    select r.task_uid
    from result r
    where t.task_uid = r.task_uid
  )
  and current_timestamp between t.begin_date and t.end_date
) m
;

task_uid  begin_date               first_date
========= ======================== ========================
1         2003-04-04 00:30:00.000  2003-04-04 00:45:00.000
2         2003-04-04 00:45:00.000  2003-04-04 00:45:00.000
3         2003-04-04 01:00:00.000  2003-04-04 00:45:00.000
4         2003-04-05 10:00:00.000  2003-04-04 00:45:00.000

(4 row(s) affected)

This is great as far as it goes, but once again we‘re going to need to look at the result table to see which of these tasks have already been completed. We did this once before, to figure out the date of the first non-completed task that we cared about, but now we’ll have to do it again to filter out the tasks in the outer portion of the SELECT.

select t.task_uid
, t.begin_date
, m.first_date
from task t
cross join (
  select min(t.begin_date) as first_date
  from task t
  where not exists (
    select r.task_uid
    from result r
    where t.task_uid = r.task_uid
  )
  and current_timestamp between t.begin_date and t.end_date
) m
where not exists (
  select r.task_uid
  from result r
  where t.task_uid = r.task_uid
)
;

task_uid  begin_date               first_date
========= ======================== ========================
2         2003-04-04 00:45:00.000  2003-04-04 00:45:00.000
3         2003-04-04 01:00:00.000  2003-04-04 00:45:00.000
4         2003-04-05 10:00:00.000  2003-04-04 00:45:00.000

(3 row(s) affected)

The final step is to compare each task’s begin_date to first_date. Specifically, we want all tasks whose begin_date is between first_date and first_date + 1 day. No two DBMSes use the same date functions; here I’m using Microsoft SQL Server’s DATEADD function. Oracle weenies would use ADD_DAYS, and so forth.

select t.task_uid
, t.begin_date
, m.first_date
from task t
cross join (
  select min(t.begin_date) as first_date
  from task t
  where not exists (
    select r.task_uid
    from result r
    where t.task_uid = r.task_uid
  )
  and current_timestamp between t.begin_date and t.end_date
) m
where not exists (
  select r.task_uid
  from result r
  where t.task_uid = r.task_uid
)
and t.begin_date between m.first_date and dateadd(day, 1, m.first_date)
;

task_uid  begin_date               first_date
========= ======================== ========================
2         2003-04-04 00:45:00.000  2003-04-04 00:45:00.000
3         2003-04-04 01:00:00.000  2003-04-04 00:45:00.000

(2 row(s) affected)