Re: LIMIT/SORT optimization

"Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> Bruce Momjian <bruce(at)momjian(dot)us> writes:
>> I did some performance testing of the patch, and the results were good.
>> I did this:
>
>> test=> CREATE TABLE test (x INTEGER);
>> test=> INSERT INTO test SELECT * FROM generate_series(1, 1000000);
>> test=> SET log_min_duration_statement = 0;
>> test=> SELECT * FROM test ORDER BY x LIMIT 3;
>
> LIMIT 3 seems an awfully favorable case; if the patch can only manage a
> factor of 4 speedup there, what happens at limit 10, 20, 100?

I did a whole bunch of benchmarking and spent a pile of time gathering numbers
in gnumeric to make some pretty graphs. Then gnumeric crashed :( It's days
like this that make me appreciate our own code review process even if I'm
usually wishing it were a bit looser.

Until I gather all those numbers together again I'll just describe the
executive summary. I found that the limit of a factor of 4 improvement was
mostly an artifact of the very narrow and cheap to sort keys. When more of the
time is spent pushing around large tuples or in even moderately expensive
comparisons the speedup is much greater.

When I tested with narrow tuples consisting of only a single integer I found
that the maximum speedup was, as Bruce found, about 4x. I think what's going
on is that the overhead in the linear factor of just reading in all those
tuples is large enough to hide the improvements in sorting. Especially since
with such narrow tuples the resulting data is just too small to overflow
filesystem cache where the big benefits come.

When I tested with text strings ranging from 0-97 characters long in locale
en_GB.UTF-8 I found that the speedup kept going up as the input data set grew.

Sorting the top 1,000 strings from an input set of 1,000,000 strings went from
8m11s in stock Postgres to 12s using the bounded heapsort.

(Which was an even better result than I had prior to fully randomizing the
data. It probably just got packed better on disk in the source table.)

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com