DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;
	h=message-id:date:from:organization:user-agent:mime-version:to:cc:subject:references:in-reply-to:content-type:content-transfer-encoding:sender;
	b=ZnX4aR++YHkiy8th8mbYknwnqRAlq3fVuSTYt4oX46+1bKiU/EGPxNDJIj4Wn2MoWYl5dMTbDA/bwTPc/HkjtzAIvbo+H/ZEBgLmpY3MylFhkEm+kC7GPrYzlx2lqX+5sB1mVRlZjZrl5bptvbz+PBCTyIB2IfA2oxBApqNiSTE=
Message-ID: <47FA4C96.3090808@enterprisedb.com>
Date: Mon, 07 Apr 2008 17:32:22 +0100
From: Heikki Linnakangas <heikki@enterprisedb.com>
Organization: EnterpriseDB
User-Agent: Mozilla-Thunderbird 2.0.0.9 (X11/20080110)
MIME-Version: 1.0
To: Matthew <matthew@flymine.org>
CC: pgsql-performance@postgresql.org
Subject: Re: Severe performance problems for simple query
References: <1207581719.5399.119.camel@dimi.lattica.com>
	<Pine.LNX.4.64.0804071656130.20402@aragorn.flymine.org>
In-Reply-To: <Pine.LNX.4.64.0804071656130.20402@aragorn.flymine.org>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Matthew wrote:
> On Mon, 7 Apr 2008, Dimi Paun wrote:
>>  * bad performance on queries of the form:
>>    select * from ipTable where  ipFrom <= val and val <= ipTo
> 
> This type of query is very hard for a normal B-tree index to answer. For 
> example, say val is half-way between min and max values. If you have an 
> index on ipFrom, it will be able to restrict the entries to about half 
> of them, which is no real benefit over a sequential scan. Likewise, an 
> index on ipTo will be able to restrict the entries to half of them, with 
> no benefit. The intersection of these two halves may be just one entry, 
> but finding that out is non-trivial. An index bitmap scan would do it if 
> you can persuade Postgres to do that, but really you want an R-tree 
> index on the two columns, like I have requested in the past.

If I understood the original post correctly, the ipFrom and ipTo columns 
actually split a single linear ip address space into non-overlapping 
chunks. Something like this:

ipFrom	ipTo
1	10
10	20
20	50
50	60
...

In that case, a regular index on (ipFrom, ipTo) should work just fine, 
and that's what he's got. Actually, an index on just ipFrom would 
probably work just as well. The problem is that the planner doesn't know 
about that special relationship between ipFrom and ipTo. Perhaps it 
could be hinted by explicitly specifying "AND ipTo > ipFrom" in the query?

I don't know why the single index lookup took > 300ms, though. That does 
seem high to me.

-- 
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com