Re: Query execution for intervals

frebe73_at_gmail.com wrote:
> Hi,
> I have a table representing events in a calendar
> event(id, start, end, ....)
>
> I have two indexes, one on the start column and one on the end column.
>
> I have a select query for finding all events containing a given time
> select *
> from event
> where start <= :time and end >= :time
>
> Is it possible for the DBMS to execute this query faster than linear
> time? From my understanding the DBMS can use one of the indexes, lets
> say the start index, to find every event starting before the given
> time. Then all these events has to be traversed to check if the end
> time is after the given time. The only thing the query optimizer migth
> do is to choose to use the the start index or the end index depending
> on the time value. But it will still be a linear search.
>
> Are my assumptions correct? Are any way to change the database
> structure to enable a search faster than linear time.

There is no satisfactory index structure for spatial/temporal type of queries (by satisfactory I mean something as ubiqutos as B-Tree). Among the solutions often mentined is R-Tree. You can try bitmapped index too. Received on Sun Feb 05 2006 - 20:20:37 CET