pgsql: Account for startup rows when costing WindowAggs

Account for startup rows when costing WindowAggs

Here we adjust the costs for WindowAggs so that they properly take into
account how much of their subnode they must read before outputting the
first row.  Without this, we always assumed that the startup cost for the
WindowAgg was not much more expensive than the startup cost of its
subnode, however, that's going to be completely wrong in many cases.  The
WindowAgg may have to read *all* of its subnode to output a single row
with certain window bound options.

Here we estimate how many rows we'll need to read from the WindowAgg's
subnode and proportionally add more of the subnode's run costs onto the
WindowAgg's startup costs according to how much of it we expect to have to
read in order to produce the first WindowAgg row.

The reason this is more important than we might have initially thought is
that we may end up making use of a path from the lower planner that works
well as a cheap startup plan when the query has a LIMIT clause, however,
the WindowAgg might mean we need to read far more rows than what the LIMIT
specifies.

No backpatch on this so as not to cause plan changes in released
versions.

Bug: #17862
Reported-by: Tim Palmer
Author: David Rowley
Reviewed-by: Andy Fan
Discussion: https://postgr.es/m/17862-1ab8f74b0f7b0611@postgresql.org
Discussion: https://postgr.es/m/CAApHDvrB0S5BMv+0-wTTqWFE-BJ0noWqTnDu9QQfjZ2VSpLv_g@mail.gmail.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/3900a02c97c7cc0e211578dc733cff0f4a2b2213

Modified Files
--------------
src/backend/optimizer/path/costsize.c | 249 +++++++++++++++++++++++++++++++++-
src/backend/optimizer/util/pathnode.c |   3 +-
src/include/optimizer/cost.h          |   2 +-
src/test/regress/expected/window.out  |  74 ++++++++++
src/test/regress/sql/window.sql       |  34 +++++
5 files changed, 358 insertions(+), 4 deletions(-)