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
>
