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.
>
> Best regards,
> frebe
>

I really don't see how how there can be a short answer to this question.

Don't know much about current products but assuming the indexes you mention are dense ones 'on top' of a row-based store, an optimizer might use both indexes perhaps transforming the 'where clause' into something like 'NOT (start > time or end < time)' or equivalent.

Am assuming that by 'intervals' you mean 'overlapping intervals' and by   'linear' you mean that physical 'rows' (as compared to indexes) are swept or scanned that are not returned by the query. Also, not clear if the meaning of 'linear' is being polluted by disk-based 'rows' that aren't clustered in a helpful way. It might help if we knew more about all the queries in the app, - eg., if the mentioned one is not the frequent one or if the mentioned one is not a final result but rather a kind of intermediate query, or the product in question, then it might be clearer whether the events table could be laid out differently, maybe as two tables if the product used is so strange that it handles joins better than multiple indexes. Also, what is an overlapping interval for everybody might not be an overlapping interval for an individual. Just guessing, not enough info really ...

pc Received on Tue Feb 07 2006 - 15:44:09 CET