To: Ty Busby <tybusby@gmail.com>
cc: pgsql-sql@postgresql.org
Subject: Re: optimize self-join query 
In-reply-to: <BFC71945-8821-4BC9-8430-A8CACF8F3794@gmail.com> 
References: <BFC71945-8821-4BC9-8430-A8CACF8F3794@gmail.com>
Comments: In-reply-to Ty Busby <tybusby@gmail.com>
	message dated "Tue, 25 Oct 2011 14:37:02 -0400"
Date: Thu, 27 Oct 2011 20:26:44 -0400
Message-ID: <9300.1319761604@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

Ty Busby <tybusby@gmail.com> writes:
> I have a table that stores a very large starting number called epc_start_numeric and a quantity.  I've apparently built the most inefficient query possible for doing the job I need: find out if any records overlap.  Imagine the epc_start_numeric + quantity representing a block of numbers.  I need to find out if any of these blocks overlap.

Yeah, overlap is a hard problem.  Basically, Postgres doesn't have any
way to do your query short of comparing each row to each other row,
so the cost goes up as O(N^2).

If you know more than you've let on about the properties of the
intervals, you might be able to improve things.  For instance
if the intervals fall into nonoverlapping buckets then you could
add a constraint that the buckets of the two sides are equal.
Postgres is a lot better with equality join constraints than it
is with range constraints, so it would be able to match up rows
and only do the O(N^2) work within each bucket.

In the long run we might have better answers --- Jeff Davis has been
working on range types for years now, and one of the long-range goals
of that is to have smarter support for this type of problem.  But for
now, it's going to be painful.

			regards, tom lane