| From: | Peter Geoghegan <pg(at)heroku(dot)com> |
|---|---|
| To: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
| Cc: | Greg Stark <stark(at)mit(dot)edu>, Pg Hackers <pgsql-hackers(at)postgresql(dot)org>, Heikki Linnakangas <hlinnaka(at)iki(dot)fi>, Robert Haas <robertmhaas(at)gmail(dot)com>, Simon Riggs <simon(at)2ndquadrant(dot)com> |
| Subject: | Re: Using quicksort for every external sort run |
| Date: | 2015-08-20 17:13:13 |
| Message-ID: | CAM3SWZQzY6V2+mXYHxHy06rQbEx3zyFoUNecXnRMSyBZvMLfRg@mail.gmail.com |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
On Thu, Aug 20, 2015 at 6:54 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Greg Stark <stark(at)mit(dot)edu> writes:
>> Alternately, has anyone tested whether Timsort would work well?
>
> I think that was proposed a few years ago and did not look so good
> in simple testing.
I tested it in 2012. I got as far as writing a patch.
Timsort is very good where comparisons are expensive -- that's why
it's especially compelling when your comparator is written in Python.
However, when testing it with text, even though there were
significantly fewer comparisons, it was still slower than quicksort.
Quicksort is cache oblivious, and that's an enormous advantage. This
was before abbreviated keys; these days, the difference must be
larger.
--
Peter Geoghegan
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Josh Berkus | 2015-08-20 17:36:11 | Re: Declarative partitioning |
| Previous Message | Alvaro Herrera | 2015-08-20 16:46:14 | Re: deparsing utility commands |