pgsql: Consider explicit incremental sort for mergejoins

Consider explicit incremental sort for mergejoins

For a mergejoin, if the given outer path or inner path is not already
well enough ordered, we need to do an explicit sort. Currently, we
only consider explicit full sort and do not account for incremental
sort.

In this patch, for the outer path of a mergejoin, we choose to use
explicit incremental sort if it is enabled and there are presorted
keys. For the inner path, though, we cannot use incremental sort
because it does not support mark/restore at present.

The rationale is based on the assumption that incremental sort is
always faster than full sort when there are presorted keys, a premise
that has been applied in various parts of the code. In addition, the
current cost model tends to favor incremental sort as being cheaper
than full sort in the presence of presorted keys, making it reasonable
not to consider full sort in such cases.

It could be argued that what if a mergejoin with an incremental sort
as the outer path is selected as the inner path of another mergejoin.
However, this should not be a problem, because mergejoin itself does
not support mark/restore either, and we will add a Material node on
top of it anyway in this case (see final_cost_mergejoin).

There is one ensuing plan change in the regression tests, and we have
to modify that test case to ensure that it continues to test what it
is intended to.

No backpatch as this could result in plan changes.

Author: Richard Guo
Reviewed-by: David Rowley, Tomas Vondra
Discussion: https://postgr.es/m/CAMbWs49x425QrX7h=Ux05WEnt8GS757H-jOP3_xsX5t1FoUsZw@mail.gmail.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/828e94c9d2fd87c06a75354361543119d9937068

Modified Files
--------------
src/backend/optimizer/path/costsize.c | 69 ++++++++++++++++----
src/backend/optimizer/plan/createplan.c | 89 +++++++++++++++++++++++---
src/test/regress/expected/aggregates.out | 34 +++++-----
src/test/regress/expected/incremental_sort.out | 21 ++++++
src/test/regress/sql/aggregates.sql | 6 +-
src/test/regress/sql/incremental_sort.sql | 6 ++
6 files changed, 184 insertions(+), 41 deletions(-)