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

On Mon, Mar 30, 2020 at 9:14 PM Tomas Vondra
<tomas(dot)vondra(at)2ndquadrant(dot)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