To: Matthew Wakeling <matthew@flymine.org>
cc: pgsql-performance@postgresql.org
Subject: Re: Very specialised query 
In-reply-to: <alpine.DEB.2.00.0903261313290.21772@aragorn.flymine.org> 
References: <alpine.DEB.2.00.0903261313290.21772@aragorn.flymine.org>
Comments: In-reply-to Matthew Wakeling <matthew@flymine.org>
	message dated "Thu, 26 Mar 2009 14:30:55 -0000"
Date: Thu, 26 Mar 2009 11:49:42 -0400
Message-ID: <22529.1238082582@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

Matthew Wakeling <matthew@flymine.org> writes:
> This query takes about two hours.

> Now, it happens that there is an algorithm for calculating overlaps which 
> is really quick. It involves iterating through the table in order of the 
> start variable and keeping a list of ranges which "haven't ended yet". 
> When you read the next range from the table, you firstly purge all the 
> ranges from the list that end before the beginning of the new range. Then, 
> you output a result row for each element in the list combined with the new 
> range, then you add the new range to the list.

> This algorithm just doesn't seem to fit into SQL at all.

No, it doesn't.  Have you thought about coding it in plpgsql?

I have a feeling that it might be possible to do it using SQL:2003
recursive queries, but the procedural coding is likely to be easier
to understand and better-performing.  Not to mention that you won't
have to wait for 8.4...

			regards, tom lane