Re: overlaps performance

Hey guys,

I am asking here, because I know there is bunch of people here that know
the topic very well.
I need to use few 'overlaps' for timedate in my query. And I guess it is
quite inefficient there. So my question would be, why isn't postgresql
using indexes for OVERLAPS, and why optimizer doesn't substitute it with
something like:

(c <= a AND d > a) OR ( c >= a AND c < b)

instead of

(a,b) overlaps (c,d)

any corner cases, or particular reasons ?

(source of example)
http://www.depesz.com/index.php/2007/11/21/find-overlapping-time-ranges/

thanks.

Grzegorz Jaśkiewicz <gj(at)pointblue(dot)com(dot)pl> writes:

> So my question would be, why isn't postgresql using indexes for OVERLAPS,
> and why optimizer doesn't substitute it with something like:
>
> (c <= a AND d > a) OR ( c >= a AND c < b)

How would you use an index for that?

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Get trained by Bruce Momjian - ask me about EnterpriseDB's PostgreSQL training!

Gregory Stark pisze:
> Grzegorz Jaśkiewicz <gj(at)pointblue(dot)com(dot)pl> writes:
>
>> So my question would be, why isn't postgresql using indexes for OVERLAPS,
>> and why optimizer doesn't substitute it with something like:
>>
>> (c <= a AND d > a) OR ( c >= a AND c < b)
>
> How would you use an index for that?
>
check Depesz'es article for that. I included it at the bottom of my email.

Gregory Stark <stark(at)enterprisedb(dot)com> writes:
> Grzegorz Jakiewicz <gj(at)pointblue(dot)com(dot)pl> writes:
>> So my question would be, why isn't postgresql using indexes for OVERLAPS,
>> and why optimizer doesn't substitute it with something like:
>>
>> (c <= a AND d > a) OR ( c >= a AND c < b)

> How would you use an index for that?

I believe you can index overlaps-like tests using GIST on an
interval-like data type --- look at contrib/seg for an example.

The reason we don't automatically translate OVERLAPS is that the spec's
definition of OVERLAPS is too weird for that to work; in particular
it demands a true result for some cases in which one of the four
endpoints is NULL, which'd be pretty hard to do with an interval-style
index.

regards, tom lane

Tom Lane pisze:
> The reason we don't automatically translate OVERLAPS is that the spec's
> definition of OVERLAPS is too weird for that to work; in particular
> it demands a true result for some cases in which one of the four
> endpoints is NULL, which'd be pretty hard to do with an interval-style
> index.
shame, I just work on a thing that would benefit from index that could
be used in OVERLAPS. I don't know psql internals , except for how GiST
works, hence my question.

thanks for the answer.

Grzegorz Jaśkiewicz <gj(at)pointblue(dot)com(dot)pl> writes:

> Tom Lane pisze:
>> The reason we don't automatically translate OVERLAPS is that the spec's
>> definition of OVERLAPS is too weird for that to work; in particular
>> it demands a true result for some cases in which one of the four
>> endpoints is NULL, which'd be pretty hard to do with an interval-style
>> index.
>
> shame, I just work on a thing that would benefit from index that could be used
> in OVERLAPS. I don't know psql internals , except for how GiST works, hence my
> question.

Ah, but the transformation given is actually a bit of a red herring. If you
look at the plan it's doing two bitmap index scans which together are actually
effectively doing a full index scan. The benefit comes from applying the full
overlap condition to the index tuples and only scanning the heap for matching
tuples. Presumably this index is much smaller than the table and/or cached in
memory so the random accesses are outweighed by the lower i/o.

This does raise the possibility that we should check for index scan paths if
we have selective enough columns even if the pathkeys aren't a prefix of the
index pathkeys. We would have to do a full index scan but the cost might still
be lower.

I think the reason we don't (aside from it not being at all useful in he past)
is that it would lead to a lot of possible index scans being considered.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's Slony Replication support!