From: | Robert Haas <robertmhaas(at)gmail(dot)com> |
---|---|
To: | Thomas Munro <thomas(dot)munro(at)enterprisedb(dot)com> |
Cc: | Rushabh Lathia <rushabh(dot)lathia(at)gmail(dot)com>, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com>, PostgreSQL Hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: Gather Merge |
Date: | 2016-11-04 12:55:04 |
Message-ID: | CA+TgmoakPEN_O--e2E0ZmiZ1TRa1Cbv1sW2CYk5oFKftFidqfw@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
On Thu, Nov 3, 2016 at 11:00 PM, Thomas Munro
<thomas(dot)munro(at)enterprisedb(dot)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
From | Date | Subject | |
---|---|---|---|
Next Message | Andres Freund | 2016-11-04 13:00:48 | Re: Logical Replication WIP |
Previous Message | Andres Freund | 2016-11-04 12:15:58 | Re: Logical Replication WIP |