From: Tom Lane <tgl@sss.pgh.pa.us>
To: Andreas Kostyrka <andreas@kostyrka.org>
Cc: Ambrus Wagner (IJ/ETH) <ambrus.wagner@ericsson.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: Merging large volumes of data
Date: Mon, 07 May 2007 11:09:28 -0400
Message-ID: <6357.1178550568@sss.pgh.pa.us> (raw)
In-Reply-To: <463F2D42.4020709@kostyrka.org>
References: <53CCFDD6E346CB43994852666C210E91C7AEE8@esealmw116.eemea.ericsson.se>
<463F2D42.4020709@kostyrka.org>
Andreas Kostyrka <andreas@kostyrka.org> writes:
> Ambrus Wagner (IJ/ETH) wrote:
>> Is there a way to prevent PostgreSQL from doing a full sort on the result set after the unions have been completed? Even if I write
>>
>> (select a,b,c,d,e from table1 order by a,b) union all
>> (select a,b,c,d,e from table2 order by a,b) union all
>> etc...
>> (select a,b,c,d,e from tablen order by a,b) order by a,b;
>>
>> PostgreSQL does not seem to realise (maybe it should not be able to do this trick anyway) that the last "order by" clause is merely a final merge step on the ordered data sets.
At least to a first-order approximation, teaching it this would be a
waste of time.
Assume for simplicity that each of your K sub-selects yields N tuples.
Then there are KN items altogether, so if we just sort the big data set
it takes O(KN*log(KN)) time ... which is the same as O(KN*(log K + log N)).
OTOH, if we sort each sub-select by itself, that takes O(N*log N) time,
or O(KN*log N) for all K sub-sorts. Now we've got to do a K-way merge,
which will take O(log K) comparisons for each of the KN tuples, ie,
O(KN*log K)). Net result: exactly the same runtime.
Of course this argument fails if you have some way of obtaining the
sub-select values pre-sorted for free. But it's never really free.
Historical experience is that full-table indexscans often underperform
explicit sorts, at least when there are enough tuples involved to
make the problem interesting.
So the bottom line is that the use-case for this optimization seems
far too narrow to justify the implementation effort.
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-performance@postgresql.org
Cc: tgl@sss.pgh.pa.us, andreas@kostyrka.org, ambrus.wagner@ericsson.com
Subject: Re: Merging large volumes of data
In-Reply-To: <6357.1178550568@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