| From: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
|---|---|
| To: | Greg Stark <stark(at)mit(dot)edu> |
| Cc: | Robert Haas <robertmhaas(at)gmail(dot)com>, 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:12:37 |
| Message-ID: | 26643.1332259957@sss.pgh.pa.us |
| Views: | Raw Message | Whole Thread | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
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?). 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.
regards, tom lane
| From | Date | Subject | |
|---|---|---|---|
| Next Message | Robert Haas | 2012-03-20 16:17:31 | Re: Memory usage during sorting |
| Previous Message | Alvaro Herrera | 2012-03-20 16:05:25 | Re: Regarding column reordering project for GSoc 2012 |