Re: Efficient date range search?

mvh_at_ix.netcom.com wrote in message news:<opdsna.i6e1.ln_at_netcom1.netcom.com>...
> Does anybode know a good (efficient) algorithm for the following?
>
> Imagine that I have a lot of entries of the form (sorry if the SQL is
> messed up):
>
> CREATE TABLE "pets" (
> name VARCHAR(20);
> "born" timestamp;
> "died" timestamp;
> );
>
> and I have a LOT of pets (let's say millions) and some don't live too
> long (mice, fruitflies, whatever), and some do (parrots, elephants).
>
> I would like to make a query to say
>
> on july 4 of last year, what pets were alive?
>
> and I would like to make this query right to the minute
>
> on july 4 of last year at 7:01 PM what pets were alive?
>
> I can't figure out how to index or query this in a manner that isn't
> going to devolve into a linear search, which would be too slow.
>
> Anybody run into this problem before? Is there a known algorithm to
> solve it? Can I twist the geographic data and algorithms around to
> support this?

There is no generally accepted method for finding a set of intervals that cover a point. Some of the "nonsexy" methods are: 1. Spatial. R-tree, etc.
2. Bitmap indexes on the "born" and "died". Minor suggestion: don't use null to represent the "died" date for alive person. Use big number like 9999 instead -- that simplifies the logic. Received on Tue Oct 08 2002 - 18:59:32 CEST