List:General Discussion« Previous MessageNext Message »
From:Dan Nelson Date:December 4 2004 4:49am
Subject:Re: Performance and indexing for time intervals...
View as plain text  
In the last episode (Dec 03), FFF FFF said:
> I'm running into some performance problems with a table of time
> intervals.  I'd like to look up the record that covers/overlaps a
> given instant, and I was hoping that someone might help me out.
> 
> Consider these tables:
> 
> create table items (
>                item_id integer auto_increment not null,
>                item_name varchar(40),
>                primary key(item_id)
> );
> 
> create table price_intervals (
>                item_id integer not null,
>                beginning datetime not null,
>                end datetime not null,
>                price decimal(6,2) not null,
>                primary key(item_id, beginning, end)
> );
> 
> Items contains a list of 100,000 items.  Price_intervals contains a
> list of 1,000,000 item prices and the intervals during which they are
> valid.  The intervals over which they are valid are continuous and of
> varying lengths.
> 
> Given a point in time, I'd like to be able to look up a price for each
> of the items at that moment.  To do this, I'll need to know the record
> in the price_intervals table that begins most recently before my
> sample point.
> 
> Since I need to do this performantly, I'd ideally like to do it using
> an index in O(1) time.
> 
> My initial attempt at this was the following:
> 
> SELECT item_name, price from
>       items join price_intervals on
>         (items.item_id = price_intervals.item_id)
> WHERE
>       price_intervals.beginning <= '11-01-01T00:00:00' AND
>       price_intervals.end > '11-01-01T00:00:00';
> 
> This query works, but it only uses the item_id portion of the
> price_interval primary key, and it ends up scanning through all of the
> 1,000,000 price_intervals for each journey (this sort of makes sense
> since the 'less than' and 'greater than' can't be combined on the same
> index).

> (explain plan)
A regular horizontal explain is easier to read imho.

> *************************** 1. row ***************************
> id: 1
> select_type: SIMPLE
> table: price_intervals

Note that mysql picked price_intervals as the driving table.  This
means it is going to find the records that match your WHERE clause,
than find the items that match as a 2nd step.  Try creating an index on
(beginning, end).  Or, try changing your JOIN to a STRAIGHT JOIN, which
will force mysql to use the tables in the order you list them.


-- 
	Dan Nelson
	dnelson@stripped
Thread
Performance and indexing for time intervals...FFF FFF4 Dec
  • Re: Performance and indexing for time intervals...Dan Nelson4 Dec