To: "Jim C. Nasby" <jnasby@pervasive.com>
Cc: Mark Fox <mark.fox@gmail.com>, pgsql-performance@postgresql.org
Subject: Re: Performance indexing of a simple query 
In-reply-to: <20050826162801.GF11282@pervasive.com> 
References: <bca49a9f05082413435f737033@mail.gmail.com>
	<16554.1124926920@sss.pgh.pa.us>
	<20050826162801.GF11282@pervasive.com>
Comments: In-reply-to "Jim C. Nasby" <jnasby@pervasive.com>
	message dated "Fri, 26 Aug 2005 11:28:02 -0500"
Date: Fri, 26 Aug 2005 12:42:41 -0400
Message-ID: <9941.1125074561@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

"Jim C. Nasby" <jnasby@pervasive.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