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: Alvaro Herrera <alvherre@2ndquadrant.com>, Michael Paquier <michael@paquier.xyz>, Rafia Sabih <rafia.pghackers@gmail.com>, Peter Geoghegan <pg@bowt.ie>, Simon Riggs <simon@2ndquadrant.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>, Andreas Karlsson <andreas@proxel.se>
Date: 2020-03-31T18:23:15Z
Lists: pgsql-hackers

Attachments

On Mon, Mar 30, 2020 at 9:14 PM Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
>
> The main thing I've been working on today is benchmarking how this
> affects planning. And I'm seeing a regression that worries me a bit,
> unfortunately.
>
> The test I'm doing is pretty simple - build a small table with a bunch
> of columns:
>
>    create table t (a int, b int, c int, d int, e int, f int, g int);
>
>    insert into t select 100*random(), 100*random(), 100*random(),
>      100*random(), 100*random(), 100*random(), 100*random()
>    from generate_series(1,100000) s(i);
>
> and then a number of indexes on subsets of up to 3 columns, as generated
> using the attached build-indexes.py script. And then run a bunch of
> explains (so no actual execution) sorting the data by at least 4 columns
> (to trigger incremental sort paths), measuring timing of the script.
>
> I did a bunch of runs on current master and v46 with incremental sort
> disabled and enabled, and the results look like this:
>
>      master       off        on
>      --------------------------
>      34.609    37.463    37.729
>
> which means about 8-9% regression with incremental sort. Of course, this
> is only for planning time, for execution the impact is going to be much
> smaller. But it's still a bit annoying.
>
> I've suspected this might be either due to the add_partial_path changes
> or the patch adding incremental sort to additional places, so I tested
> those parts individually and the answer is no - add_partial_path changes
> have very small impact (~1%, which might be noise). The regression comes
> mostly from the 0002 part that adds incremental sort. At least in this
> particular test - different tests might behave differently, of course.
>
> The annoying bit is that the overhead does not disappear after disabling
> incremental sort. That suggests this is not merely due to considering
> and creating higher number of paths, but due to something that happens
> before we even look at the GUC ...
>
> I think I've found one such place - if you look at compare_pathkeys, it
> has this check right before the forboth() loop:
>
>      if (keys1 == keys2)
>          return PATHKEYS_EQUAL;
>
> But with incremental sort we don't call pathkeys_contained_in, we call
> pathkeys_common_contained_in instead. And that does not call
> compare_pathkeys and does not have the simple equality check. Adding
> the following check seems to cut the overhead in half, which is nice:
>
>      if (keys1 == keys2)
>      {
>          *n_common = list_length(keys1);
>         return true;
>      }
>
> Not sure where the rest of the regression comes from yet.

I noticed in the other function we also optimize by checking if either
keys list is NIL, so I tried adding that, and it might have made a
minor difference, but it's hard to tell as it was under 1%.

I also ran perf with a slightly modified version of your test that
uses psql, and after the above changes was seeing something like a
3.5% delta between master and this patch series. Nothing obvious in
the perf report though.

This test is intended to be somewhat worst case, no? At what point do
we consider the trade-off worth it (given that it's not plausible to
have zero impact)?

> Also, while looking at pathkeys_common_contained_in(), I've been a bit
> puzzled why does is this correct:
>
>      return (key1 == NULL);
>
> It's easy to not notice it's key1 and not keys1, so I suggest we add a
> comment 'key1 == NULL' means we've processed whole keys1 list.

Done.

I've included fixes for Alvaro's comments in this patch series also.

James

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.