### Re: [HACKERS] EXPLAIN ANALYZE output weird for Top-N Sort

```On 14/11/14 00:46, Simon Riggs wrote:
Limit  (cost= rows=20 width=175) (actual time= rows=20 loops=1)
-  Sort  (cost= rows=568733 width=175) (actual time=
rows=20 loops=1)
Sort Method: top-N heapsort

Going off on a tangent, when I was playing with a merge-sort
implementation I propagated limit information into the sort
node, for a significant win.  Eliding the Limit node gave
a further slight win.

I wasn't convinced the use-case was common enough to justify
the replacement of quicksort (despite having consistently
fewer compares, the merge sort was slightly slower.  I never
understood why) - but I never asked.  Is there any appetite
for supporting alternate sort algorithms?
--
Cheers,
Jeremy

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

```

### Re: [HACKERS] EXPLAIN ANALYZE output weird for Top-N Sort

```Jeremy Harris j...@wizmail.org writes:
On 14/11/14 00:46, Simon Riggs wrote:
Limit  (cost= rows=20 width=175) (actual time= rows=20 loops=1)
-  Sort  (cost= rows=568733 width=175) (actual time=
rows=20 loops=1)
Sort Method: top-N heapsort

Going off on a tangent, when I was playing with a merge-sort
implementation I propagated limit information into the sort
node, for a significant win.

I'm not entirely following.  The top-N heapsort approach already
makes use of the limit info.

If the limit is so large that the sort spills to disk, then we
stop thinking about the limit.  But I'm finding it doubtful either
that that's a case worthy of extra code or that you could get very
much win if you did add code for it.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

```

### Re: [HACKERS] EXPLAIN ANALYZE output weird for Top-N Sort

```On 14/11/14 14:54, Tom Lane wrote:
Jeremy Harris j...@wizmail.org writes:
On 14/11/14 00:46, Simon Riggs wrote:
Limit  (cost= rows=20 width=175) (actual time= rows=20 loops=1)
-  Sort  (cost= rows=568733 width=175) (actual time=
rows=20 loops=1)
Sort Method: top-N heapsort

Going off on a tangent, when I was playing with a merge-sort
implementation I propagated limit information into the sort
node, for a significant win.

I'm not entirely following.  The top-N heapsort approach already
makes use of the limit info.

Having gone back to look, you're right.  It was Uniq nodes I merged
(the sort handles both bounded-output and dedup).
--
Cheers,
Jeremy

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

```

### [HACKERS] EXPLAIN ANALYZE output weird for Top-N Sort

```Limit  (cost= rows=20 width=175) (actual time= rows=20 loops=1)
-  Sort  (cost= rows=568733 width=175) (actual time=
rows=20 loops=1)
Sort Method: top-N heapsort

The Sort estimate shows 568733 rows, whereas the actual rows are 20.

Both are correct, in a way.

The node feeding the Sort shows an actual of 379114 rows.

If we are looking at rows returned, then the Sort node estimate should say 20
If we are looking at rows processed, then the Sort node should have
actual rows=379114

I think we should say the latter; i,e, the Sort node should report
379114 rows, not 20 rows.

Thoughts?

--
PostgreSQL Development, 24x7 Support, Training  Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

```

### Re: [HACKERS] EXPLAIN ANALYZE output weird for Top-N Sort

```Simon Riggs si...@2ndquadrant.com writes:
Limit  (cost= rows=20 width=175) (actual time= rows=20 loops=1)
-  Sort  (cost= rows=568733 width=175) (actual time=
rows=20 loops=1)
Sort Method: top-N heapsort

The Sort estimate shows 568733 rows, whereas the actual rows are 20.

[ shrug... ]  The estimated value is the planner's estimate of what would
happen *if you ran the node to completion*, which in practice doesn't
happen because of the LIMIT.  The actual value is, well, the actual value.
We certainly should not munge around the actual value.

We could imagine munging the reported estimates to account for the parent
LIMIT, but that would make it a lot harder to understand the planner's
thought processes, because the reported estimates would have that much
less to do with the numbers actually used in the internal calculations.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

```

### Re: [HACKERS] EXPLAIN ANALYZE output weird for Top-N Sort

```Tom Lane-2 wrote
Simon Riggs lt;

simon@

gt; writes:
Limit  (cost= rows=20 width=175) (actual time= rows=20 loops=1)
-  Sort  (cost= rows=568733 width=175) (actual time=
rows=20 loops=1)
Sort Method: top-N heapsort

The Sort estimate shows 568733 rows, whereas the actual rows are 20.

[ shrug... ]  The estimated value is the planner's estimate of what would
happen *if you ran the node to completion*, which in practice doesn't
happen because of the LIMIT.  The actual value is, well, the actual value.
We certainly should not munge around the actual value.

We could imagine munging the reported estimates to account for the parent
LIMIT, but that would make it a lot harder to understand the planner's
thought processes, because the reported estimates would have that much
less to do with the numbers actually used in the internal calculations.

Is it even possible for a sort node directly under a limit to output (as
nebulous as that term is in this context) more rows that desired by the
limit?

The interesting thing about a sort node is not its output but its input -
i.e., the number of rows being fed to it via the node nested under it.
Which prompts the question whether it would be good to show that value as an
attribute of the sort node during EXPLAIN ANALYZE instead of having to scan
down to the child node.  I guess you can argue that we are currently since
that is the same value as the estimated rows returned.  If you were to
change that to reflect the impact of the parent limit node you'd probably
want to add something else to reflect the child input size (in rows, not
memory).

From a pure theory standpoint having the estimated rows reflect the input
size instead of the output size seems wrong.  In the presence of limit it
won't output more than N rows whereas in all other cases the input and the
output will be identical.  That said I am only pondering this concept
because of this thread - it would help to know what sparked all of this in
the first place.  From a practical perspective the current behavior captures
the most important aspect of the sort - the size of the input - and the user
knowing of the limit isn't likely to wonder whether we are somehow being
wasteful by returning the extra rows; which are not returned so much as
scanned over in place by the parent node.

David J.

--
View this message in context:
http://postgresql.nabble.com/EXPLAIN-ANALYZE-output-weird-for-Top-N-Sort-tp5826922p5826935.html
Sent from the PostgreSQL - hackers mailing list archive at Nabble.com.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

```

### Re: [HACKERS] EXPLAIN ANALYZE output weird for Top-N Sort

```David G Johnston david.g.johns...@gmail.com writes:
Tom Lane-2 wrote
[ shrug... ]  The estimated value is the planner's estimate of what would
happen *if you ran the node to completion*, which in practice doesn't
happen because of the LIMIT.

I don't see how a sort node cannot run to completion...

The sort must have read all of its *input*, or it can't be sure it's
giving the correct first result row.  But run to completion means
that it delivered all of its *output*, which obviously does not happen
when under a LIMIT.

It's entirely possible BTW that the sort's internal processing is not
complete when it starts returning rows.  For example, when we do a
spill-to-disk merge sort, the final merge pass is typically done
on-the-fly while returning rows, and so some fraction of that processing
may never be completed if the query stops early.  It's still seen all the
input rows, but it hasn't completely determined their ordering.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

```