Horton

Re: [PATCH] Incremental sort (was: PoC: Partial sort)

James Coleman <jtc331@gmail.com>

View thread View on postgr.es
From: James Coleman <jtc331@gmail.com>
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Peter Geoghegan <pg@bowt.ie>, Simon Riggs <simon@2ndquadrant.com>, Rafia Sabih <rafia.pghackers@gmail.com>, Shaun Thomas <shaun.thomas@2ndquadrant.com>, Dmitry Dolgov <9erthalion6@gmail.com>, Alexander Korotkov <a.korotkov@postgrespro.ru>, Tom Lane <tgl@sss.pgh.pa.us>, PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>
Date: 2019-07-08T13:22:39Z
Lists: pgsql-hackers 
On Sun, Jul 7, 2019 at 5:02 PM Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
> We're running query like this:
>
>   SELECT a, sum(b), count(*) FROM pagg_tab_ml GROUP BY a HAVING avg(b) < 3 ORDER BY 1, 2, 3
>
> but we're trying to add the incremental sort *before* the aggregation,
> because the optimizer also considers group aggregate with a sorted
> input. And (a) is a prefix of (a,sum(b),count(b)) so we think we
> actually can do this, but clearly that's nonsense, because we can't
> possibly know the aggregates yet. Hence the error.
>
> If this is the actual issue, we need to ensure we actually can evaluate
> all the pathkeys. I don't know how to do that yet. I thought that maybe
> we should modify pathkeys_common_contained_in() to set presorted_keys to
> 0 in this case.
>
> But then I started wondering why we don't see this issue even for
> regular (non-incremental-sort) paths built in create_ordered_paths().
> How come we don't see these failures there? I've modified costing to
> make all incremental sort paths very cheap, and still nothing.

I assume you mean you modified costing to make regular sort paths very cheap?

> So presumably there's a check elsewhere (either implicit or explicit),
> because create_ordered_paths() uses pathkeys_common_contained_in() and
> does not have the same issue.

Given this comment in create_ordered_paths():

  generate_gather_paths() will have already generated a simple Gather
  path for the best parallel path, if any, and the loop above will have
  considered sorting it.  Similarly, generate_gather_paths() will also
  have generated order-preserving Gather Merge plans which can be used
  without sorting if they happen to match the sort_pathkeys, and the loop
  above will have handled those as well.  However, there's one more
  possibility: it may make sense to sort the cheapest partial path
  according to the required output order and then use Gather Merge.

my understanding is that generate_gather_paths() only considers paths
that already happen to be sorted (not explicit sorts), so I'm
wondering if it would make more sense for the incremental sort path
creation for this case to live alongside the explicit ordered path
creation in create_ordered_paths() rather than in
generate_gather_paths().

If I'm understanding what you're saying properly, I think you'd
expected create_ordered_paths() to be roughly similar in what it
considers as partial paths and so have the same problem, and I haven't
yet read enough of the code to understand if my proposed change
actually has any impact on the issue we're discussing, but it seems to
me that it at least fits more with what the comments imply.

I'll try to look at it a bit more later also, but at the moment other
work calls.

James Coleman

Commits

  1. Further adjustments to Hashagg EXPLAIN ANALYZE output

  2. Rework EXPLAIN format for incremental sort

  3. Fix typos and improve incremental sort comments

  4. Stabilize incremental_sort tests

  5. Minor improvements in Incremental Sort explain

  6. Consider Incremental Sort paths at additional places

  7. Fix representation of SORT_TYPE_STILL_IN_PROGRESS.

  8. Fix failures in incremental_sort due to number of workers

  9. Fix show_incremental_sort_info with force_parallel_mode

  10. Implement Incremental Sort

  11. Fix handling of "Subplans Removed" field in EXPLAIN output.

  12. Fix EXPLAIN (SETTINGS) to follow policy about when to print empty fields.

  13. Ensure plpgsql result tuples have the right composite type marking.

  14. Propagate sort instrumentation from workers back to leader.

  15. Make new regression test case parallel-safe, and improve its output.

  16. Push limit through subqueries to underlying sort, where possible.

  17. Fix inappropriate printing of never-measured times in EXPLAIN.

  18. Fix some infelicities in EXPLAIN output for parallel query plans.