Re: Severe performance problems for simple query

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.

You can achieve that to some degree by using Postgres' geometric indexes,
but it's ugly. Note that the following is completely untested and may not
work with int8 values.

Firstly, you need to create the index. The index will contain fake "boxes"
that stretch from ipFrom to ipTo.

CREATE INDEX index_name ON table_name ((box '((ipFrom, 0), (ipTo, 1))'))

Then, instead of querying simply for fromIp and toIp, query on whether the
fake box overlaps with a point representing val.

SELECT blah FROM table_name
WHERE (box '((ipFrom, 0), (ipTo, 2))') @> (point '(val, 1)');

Or alternatively you could adapt the "seg" GiST index to int8 values.

Hope you get this sorted out - it's something I'll have to do at some
point soon too.

Matthew

--
I wouldn't be so paranoid if you weren't all out to get me!!