From: Tom Lane <tgl@sss.pgh.pa.us>
To: Ty Busby <tybusby@gmail.com>
Cc: pgsql-sql@postgresql.org
Subject: Re: optimize self-join query
Date: Thu, 27 Oct 2011 20:26:44 -0400
Message-ID: <9300.1319761604@sss.pgh.pa.us> (raw)
In-Reply-To: <BFC71945-8821-4BC9-8430-A8CACF8F3794@gmail.com>
References: <BFC71945-8821-4BC9-8430-A8CACF8F3794@gmail.com>
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-sql@postgresql.org
Cc: tgl@sss.pgh.pa.us, tybusby@gmail.com
Subject: Re: optimize self-join query
In-Reply-To: <9300.1319761604@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox