Implement binary heap replace-top operation in a smarter way.
In external sort's merge phase, we maintain a binary heap holding the next
tuple from each input tape. On each step, the topmost tuple is returned,
and replaced with the next tuple from the same tape. We were doing the
replacement by deleting the top node in one operation, and inserting the
next tuple after that. However, you can do a "replace-top" operation more
efficiently, in one "sift-up". A deletion will always walk the heap from
top to bottom, but in a replacement, we can stop as soon as we find the
right place for the new tuple. This is particularly helpful, if the tapes
are not in completely random order, so that the next tuple from a tape is
likely to land near the top of the heap.
Peter Geoghegan, reviewed by Claudio Freire, with some editing by me.
Discussion: <CAM3SWZRhBhiknTF_=NjDSnNZ11hx=U_SEYwbc5vd=x7M4mMiCw@mail.gmail.com>
Branch
------
master
Details
-------
http://git.postgresql.org/pg/commitdiff/24598337c8d214ba8dcf354130b72c49636bba69
Modified Files
--------------
src/backend/utils/sort/tuplesort.c | 182 ++++++++++++++++++++++---------------
1 file changed, 109 insertions(+), 73 deletions(-)