Optimize query execution based on two datetime columns I've been struggling all day long against this.

We have a very busy database (still on development) and we have records being inserted very frequently. The record logs have a start time and a end time.

If I want to select something between col1(datetime) and col2(datetime) MySQL can't use indexes properly because it will search the index for col1 but will never look into col2.
The database engine is InnoDB. What happens is for example that MySQL will search 80 thousand rows when the interval requested should only return two rows.

My biggest problem is that I'm trying to do some aggregate functions on this time ranges and its taking a very long time when it should be really fast considering how many rows it is actually counting.

Also note that I can't do dateStart between col1 and col2 nor dateEnd between col1 and col2 because dateStart can be lower than col1 and dateEnd can also be lower than col2.

Lets assume this sample data:

     col1      |     col2
---------------+---------------
date 10:20:00  |date 10:21:00
date 10:21:00  |date 10:22:00
date 10:22:00  |date 10:23:00
date 10:23:00  |date 10:24:00
date 10:24:00  |date 10:25:00
date 10:25:00  |date 10:26:00
date 10:26:00  |date 10:27:00


If I need the rows that range between 10:21:30 and 10:25:30 I need to do something like this:

'10:25:30' &lt;= col1 AND '10:21:30' &gt;= col2.


So how do I index these columns properly? MySQL only picks up one of the date columns in the index.
Thanks to everyone who took the time to respond.
I got it fixed in a different way.
Since the values can't overlap and mysql is efficient using one single index for ranges, what i did was find the first col1 and last col1 and use a select between. This turned out really fast because mysql now analyses only the lines in the range.

As for the aggregates which were causing problems I still had to go round them anyways because I had to execute it separately or otherwise MySQL optimizer was really inefficient. The way I did it was by selecting the results into a temporary memory table and then loop those results (cursor wasn't a choice because I already had a loop) and doing the 3 aggregate functions at once. This is was the final result (just the loop part):

myLoop: LOOP

IF (SELECT COUNT(*) FROM (SELECT
    @CarrId := carrier_id,
    @FistVTime := firstValidTIME,
    @LastVTime := lastValidTIME
FROM startStopReportTable
WHERE maxSpeed = -1) AS dummyTbl) &lt; 1 THEN
    LEAVE myLoop;
END IF;

UPDATE startStopReportTable AS t0,
    (SELECT
        SUM(l0.distance) AS distance,
        AVG(l0.speed) AS avgspeed,
        MAX(l0.speed) AS maxspeed
        FROM
            pcoarg AS l0
        WHERE
            l0.carrier_id = @CarrId
        AND
            l0.lastValidTIME BETWEEN @FistVTime AND @LastVTime
    ) AS t1
SET
    t0.distance = t1.distance,
    t0.averageSpeed = t1.avgspeed,
    t0.maxSpeed = t1.maxspeed
WHERE t0.carrier_id = @CarrId AND t0.firstValidTIME = @FistVTime AND t0.lastValidTIME = @LastVTime;
END LOOP;


LastValidTIME is col1
startStopReportTable is temporary table

Profiling results:

96  0.00058100  UPDATE startStopReportTable AS t0,
      (SELECT
       SUM(l0.distance) AS distance,
       AVG(l0.speed) AS avgspeed,
       MAX(l0.speed) AS maxspeed
       FROM
        pcoarg AS l0
       WHERE
        l0.carrier_id = @CarrId
       AND
        l0.lastValidTI...
97  0.00045100  UPDATE startStopReportTable AS t0,
      (SELECT
       SUM(l0.distance) AS distance,
       AVG(l0.speed) AS avgspeed,
       MAX(l0.speed) AS maxspeed
       FROM
        pcoarg AS l0
       WHERE
        l0.carrier_id = @CarrId
       AND
        l0.lastValidTI...
98  0.00094900  UPDATE startStopReportTable AS t0,
      (SELECT
       SUM(l0.distance) AS distance,
       AVG(l0.speed) AS avgspeed,
       MAX(l0.speed) AS maxspeed
       FROM
        pcoarg AS l0
       WHERE
        l0.carrier_id = @CarrId
       AND
        l0.lastValidTI...


It's really a shame that the optimizer can't combine sub query aggregates in one query while it can combine them in one query.