Re: Gather Merge

On Sat, Nov 5, 2016 at 1:55 AM, Robert Haas <robertmhaas@gmail.com> wrote:
> On Thu, Nov 3, 2016 at 11:00 PM, Thomas Munro
> <thomas.munro@enterprisedb.com> wrote:
>> + /*
>> + * Avoid log(0)...
>> + */
>> + N = (path->num_workers < 2) ? 2.0 : (double) path->num_workers;
>> + logN = LOG2(N);
>> ...
>> + /* Per-tuple heap maintenance cost */
>> + run_cost += path->path.rows * comparison_cost * 2.0 * logN;
>>
>> Why multiply by two?  The comment above this code says "about log2(N)
>> comparisons to delete the top heap entry and another log2(N)
>> comparisons to insert its successor".  In fact gather_merge_getnext
>> calls binaryheap_replace_first, which replaces the top element without
>> any comparisons at all and then performs a sift-down in log2(N)
>> comparisons to find its new position.  There is no per-tuple "delete"
>> involved.  We "replace" the top element with the value it already had,
>> just to trigger the sift-down, because we know that our comparator
>> function might have a new opinion of the sort order of this element.
>> Very clever!  The comment and the 2.0 factor in cost_gather_merge seem
>> to be wrong though -- or am I misreading the code?
>
> See cost_merge_append, and the header comments threreto.

I see.  So commit 7a2fe9bd got rid of the delete/insert code
(heap_siftup_slot and heap_insert_slot) and introduced
binaryheap_replace_first which does it in one step, but the costing
wasn't adjusted and still thinks we pay comparison_cost * logN twice.

-- 
Thomas Munro
http://www.enterprisedb.com