Re: Performance indexing of a simple query

"Jim C. Nasby" <jnasby(at)pervasive(dot)com> writes:
> Uh, the plain english and the SQL don't match. That query will find
> every job that was NOT running at the time you said.

No, I think it was right. But anyway it was just an example.

> On Wed, Aug 24, 2005 at 07:42:00PM -0400, Tom Lane wrote:
>> AFAIK there is no good way to do this with btree indexes; the problem
>> is that it's fundamentally a 2-dimensional query and btrees are
>> 1-dimensional. There are various hacks you can try if you're willing
>> to constrain the problem (eg, if you can assume some not-very-large
>> maximum on the running time of jobs) but in full generality btrees are
>> just the Wrong Thing.

> Ignoring the SQL and doing what the author actually wanted, wouldn't a
> bitmap combination of indexes work here?

> Or with an index on (start_time, completion_time), start an index scan
> at start_time = SOMEDATE and only include rows where completion_time <
> SOMEDATE. Of course if SOMEDATE is near the beginning of the table that
> wouldn't help.

The trouble with either of those is that you have to scan very large
fractions of the index (if not indeed *all* of it) in order to get your
answer; certainly you hit much more of the index than just the region
containing matching rows. Btree just doesn't have a good way to answer
this type of query.

regards, tom lane