Re: Top-N sorts verses parallelism

On Wed, Dec 13, 2017 at 1:46 AM, Thomas Munro
<thomas(dot)munro(at)enterprisedb(dot)com> wrote:
> Hi hackers,
>
> The start-up cost of bounded (top-N) sorts is sensitive at the small
> end of N, and the
> comparison_cost * tuples * LOG2(2.0 * output_tuples) curve doesn't
> seem to correspond to reality. Here's a contrived example that comes
> from a benchmark:
>
> create table foo as
> select generate_series(1, 1000000)::int a, (random() * 1000)::int b;
> analyze foo;
> select * from foo order by b limit N;
>
> But the actual time doesn't really change on this random development
> system: it's around 300ms. I stopped at limit 133 because for this
> particular query, at 134 a Gather Merge plan kicked in and I got
> degree 3 parallel sorting and I got my answer just shy of three times
> faster. The speed up definitely paid for the parallel_setup_cost and
> only one tuple was sent from each worker to the leader because the
> limit was pushed down.

I get:

rhaas=# explain analyze select * from foo order by b limit 1;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
Limit (cost=19425.00..19425.00 rows=1 width=8) (actual
time=183.129..183.129 rows=1 loops=1)
-> Sort (cost=19425.00..21925.00 rows=1000000 width=8) (actual
time=183.128..183.128 rows=1 loops=1)
Sort Key: b
Sort Method: top-N heapsort Memory: 25kB
-> Seq Scan on foo (cost=0.00..14425.00 rows=1000000
width=8) (actual time=0.046..89.440 rows=1000000 loops=1)
Planning time: 0.083 ms
Execution time: 183.171 ms
(7 rows)

If we assume the costing of the Seq Scan node is right, then the
startup cost of the Sort node is too low. For the Seq Scan node, each
1ms of execution time corresponds to 161.28 cost units. If that were
accurate, then the 183.128 - 89.440 = 93.668 cost units of startup
cost for the Sort ought to have a cost of 14425.00 + (93.668 * 161.28)
= 29531.77504, but the actual cost is only 19425.00. In other words,
the ratio of the startup cost of the sort to the total cost of the seq
scan ought to be about 2:1, to match the ratio of the execution times,
but it's actually more like 4:3.

I also see that it switches to Gather Merge at LIMIT 134, but if I
lower random_page_cost and seq_page_cost from the default values to
0.1, then for me it switches earlier, at 63. Of course, at that point
the sort cost is now 3.5x the Seq Scan cost, so now things have gone
too far in the other direction and we're still not getting the plan
right, but I am out of time to investigate this for the moment.

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