Re: Improve eviction algorithm in ReorderBuffer

On Thu, Apr 11, 2024 at 10:32 AM Masahiko Sawada <sawada.mshk@gmail.com> wrote:
>
> Hi,
>
> Sorry for the late reply, I took two days off.
>
> On Thu, Apr 11, 2024 at 6:20 AM Heikki Linnakangas <hlinnaka@iki.fi> wrote:
> >
> > On 10/04/2024 08:31, Amit Kapila wrote:
> > > On Wed, Apr 10, 2024 at 11:00 AM Heikki Linnakangas <hlinnaka@iki.fi> wrote:
> > >>
> > >> On 10/04/2024 07:45, Michael Paquier wrote:
> > >>> On Tue, Apr 09, 2024 at 09:16:53PM -0700, Jeff Davis wrote:
> > >>>> On Wed, 2024-04-10 at 12:13 +0900, Michael Paquier wrote:
> > >>>>> Wouldn't the best way forward be to revert
> > >>>>> 5bec1d6bc5e3 and revisit the whole in v18?
> > >>>>
> > >>>> Also consider commits b840508644 and bcb14f4abc.
> > >>>
> > >>> Indeed.  These are also linked.
> > >>
> > >> I don't feel the urge to revert this:
> > >>
> > >> - It's not broken as such, we're just discussing better ways to
> > >> implement it. We could also do nothing, and revisit this in v18. The
> > >> only must-fix issue is some compiler warnings IIUC.
> > >>
> > >> - It's a pretty localized change in reorderbuffer.c, so it's not in the
> > >> way of other patches or reverts. Nothing else depends on the binaryheap
> > >> changes yet either.
> > >>
> > >> - It seems straightforward to repeat the performance tests with whatever
> > >> alternative implementations we want to consider.
> > >>
> > >> My #1 choice would be to write a patch to switch the pairing heap,
> > >> performance test that, and revert the binary heap changes.
> > >>
> > >
> > > +1.
> >
> > To move this forward, here's a patch to switch to a pairing heap. In my
> > very quick testing, with the performance test cases posted earlier in
> > this thread [1] [2], I'm seeing no meaningful performance difference
> > between this and what's in master currently.
> >
> > Sawada-san, what do you think of this? To be sure, if you could also
> > repeat the performance tests you performed earlier, that'd be great. If
> > you agree with this direction, and you're happy with this patch, feel
> > free take it from here and commit this, and also revert commits
> > b840508644 and bcb14f4abc.
> >
>
> Thank you for the patch!
>
> I agree with the direction that we replace binaryheap + index with the
> existing pairing heap and revert the changes for binaryheap. Regarding
> the patch, I'm not sure we can remove the MAX_HEAP_TXN_COUNT_THRESHOLD
> logic because otherwise we need to remove and add the txn node (i.e.
> O(log n)) for every memory update. I'm concerned it could cause some
> performance degradation in a case where there are not many
> transactions being decoded.
>
> I'll do performance tests, and share the results soon.
>

Here are some performance test results.

* test case 1 (many subtransactions)

test script:

create or replace function testfn (cnt int) returns void as $$
begin
  for i in 1..cnt loop
    begin
      insert into test values (i);
    exception when division_by_zero then
      raise notice 'caught error';
      return;
    end;
  end loop;
end;
$$
language plpgsql;
select pg_create_logical_replication_slot('s', 'test_decoding');
select testfn(1000000);
set logical_decoding_work_mem to '4MB';
select from pg_logical_slot_peek_changes('s', null, null);

HEAD:

43128.266 ms
40116.313 ms
38790.666 ms

Patched:

43626.316 ms
44456.234 ms
39899.753 ms


* test case 2 (single big insertion)

test script:

create table test (c int);
select pg_create_logical_replication_slot('s', 'test_decoding');
insert into test select generate_series(1, 10000000);
set logical_decoding_work_mem to '10GB'; -- avoid data spill
select from pg_logical_slot_peek_changes('s', null, null);

HEAD:

7996.476 ms
8034.022 ms
8005.583 ms

Patched:

8153.500 ms
8121.588 ms
8121.538 ms


* test case 3 (many small transactions)

test script:

pgbench -s -i 300
psql -c "select pg_create_replication_slot('s', 'test_decoding')";
pgbench -t 100000 -c 32
psql -c "set logical_decoding_work_mem to '10GB'; select count(*) from
pg_logical_slot_peek_changes('s', null, null)"

HEAD:

22586.343 ms
22507.905 ms
22504.133 ms

Patched:

23365.142 ms
23110.651 ms
23102.170 ms

We can see 2% ~ 3% performance regressions compared to the current
HEAD, but it's much smaller than I expected. Given that we can make
the code simple, I think we can go with this direction.

Regards,

--
Masahiko Sawada
Amazon Web Services: https://aws.amazon.com