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(at)gmail(dot)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
>