Usually creating an index on a table that size should be sufficient, but we don't know whether there are any additional JOINs or WHERE terms in the query either.
In a more general sense you are asking how to access arbitrary subsets of the data on demand, which is more in the realm of data warehousing. In fact, you allude to that by mention of separate "cache" tables, often called facts and dimensions (although there is more to that idea).
Here is a simple way that you might do that for your specific example (impromptu, view as pseudo code!)...
Code:
CREATE TABLE doneDateDimension(doneDate INT(11) unsigned PK);
CREATE TABLE jobFact(
jobKey (jobKey type) PK,
doneDate INT(11) unsigned
... other dimension keys here...
);
CREATE INDEX 'job_done_key' ON jobFact (doneDate);
You should have a process to populate these tables periodically, search for ETL, but for simple case...
REPLACE INTO jobFact(SELECT jobKey, UNIX_TIMESTAMP(DATE(doneDate)) FROM jobs);
/* Force date only, not time, assumes datetime type in jobs table */
REPLACE INTO doneDateDimension(SELECT DISTINCT doneDate FROM jobFact);
At this point you have instant access to jobs by date...
Code:
SELECT [job columns]
FROM dateDimension JOIN jobFact USING(doneDate) JOIN jobs USING(jobKey)
WHERE doneDate>=UNIX_TIMESTAMP(startDate) AND doneDate<UNIX_TIMESTAMP(endDate)
ORDER BY doneDate, jobKey;
The use of integer dates as keys in the dimension greatly speeds access so that you rather instantly arrive at the subset of jobKeys, everything after that is simple retreival.
With a suitable ETL process and additional dimensions you will have instant access to jobs by various slices through the data.