Re: Severe performance problems for simple query

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