Re: Gather Merge

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.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company