Re: Number of rows returned by Sort node

Thanks, Tom!

I've found some more information in PostgreSQL source code:

For example, consider the following relations:

         outer: (0 ^1 1 2 5 5 5 6 6 7)    current tuple: 1
         inner: (1 ^3 5 5 5 5 6)          current tuple: 3

...suppose that the executor has
just joined the first outer "5" with the last inner "5". The
next step is of course to join the second outer "5" with all
the inner "5's". This requires repositioning the inner "cursor"
to point at the first inner "5". This is done by "marking" the
first inner 5 so we can restore the "cursor" to it before joining
with the second outer 5. The access method interface provides
routines to mark and restore to a tuple.


Essential operation of the merge join algorithm is as follows:

Join {
     get initial outer and inner tuples INITIALIZE
     do forever {
         while (outer != inner) { SKIP_TEST
             if (outer < inner)
                 advance outer SKIPOUTER_ADVANCE
             else
                 advance inner SKIPINNER_ADVANCE
         }
         mark inner position SKIP_TEST
         do forever {
             while (outer == inner) {
                 join tuples JOINTUPLES
                 advance inner position NEXTINNER
             }
             advance outer position NEXTOUTER
             if (outer == mark) TESTOUTER
                 restore inner position to mark TESTOUTER
             else
                 break    // return to top of outer loop
         }
     }
}


So, even that the Sort node was returning unique values, the join 
algorithm still had to do a lot of mark/restore, which were reflected in 
EXPLAIN's row count. Anyway, that's clear now.

Regards,
Vitaliy

On 2018-01-09 17:23, Tom Lane wrote:
> Vitaliy Garnashevich <vgarnashevich@gmail.com> writes:
>> How, according to EXPLAIN ANALYZE, the Sort node could return more rows
>> as output (rows=767662), than it had for input from its child node
>> (rows=135627)?
> Unsurprising when it's the inner input of a merge join --- that reflects
> the merge join rescanning parts of the inner input.  It has to do that
> whenever the outer input has duplicate keys.
>
>             regards, tom lane
>