| From: | Robert Haas <robertmhaas(at)gmail(dot)com> |
|---|---|
| To: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
| Cc: | Greg Stark <stark(at)mit(dot)edu>, Jeff Janes <jeff(dot)janes(at)gmail(dot)com>, Hitoshi Harada <umi(dot)tanuki(at)gmail(dot)com>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
| Subject: | Re: Memory usage during sorting |
| Date: | 2012-03-20 16:20:29 |
| Message-ID: | CA+TgmoaQm08b+G4knDQy3BVXA_jZ3-PN0c6wJSMLJSLwfCM=xQ@mail.gmail.com |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
On Tue, Mar 20, 2012 at 12:12 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Greg Stark <stark(at)mit(dot)edu> writes:
>> http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
>
> Interesting. I'm pretty sure that idea appears nowhere in Knuth
> (which might mean it's new enough to have a live patent on it ...
> anybody know who invented this?).
It's in every introductory algorithms textbook; I'd be shocked if
anyone could make an IP claim on it.
> But it seems like that should buy
> back enough comparisons to justify leaving the next-run tuples out of
> the heap (unordered) until the heap becomes empty. You still want to
> insert new tuples into the heap if they can go to the current run, of
> course.
It seems like it should, but if you read (or reread) my long boring
analysis upthread, you'll learn that it doesn't. It's slower even if
the cost of building a heap is zero.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Tom Lane | 2012-03-20 16:33:33 | Re: Memory usage during sorting |
| Previous Message | Robert Haas | 2012-03-20 16:17:31 | Re: Memory usage during sorting |